1 /* Perform branch target register load optimizations.
2 Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
37 #include "insn-attr.h"
42 /* Target register optimizations - these are performed after reload. */
44 typedef struct btr_def_group_s
46 struct btr_def_group_s
*next
;
48 struct btr_def_s
*members
;
51 typedef struct btr_user_s
53 struct btr_user_s
*next
;
57 /* If INSN has a single use of a single branch register, then
58 USE points to it within INSN. If there is more than
59 one branch register use, or the use is in some way ambiguous,
63 int first_reaching_def
;
64 char other_use_this_block
;
67 /* btr_def structs appear on three lists:
68 1. A list of all btr_def structures (head is
69 ALL_BTR_DEFS, linked by the NEXT field).
70 2. A list of branch reg definitions per basic block (head is
71 BB_BTR_DEFS[i], linked by the NEXT_THIS_BB field).
72 3. A list of all branch reg definitions belonging to the same
73 group (head is in a BTR_DEF_GROUP struct, linked by
74 NEXT_THIS_GROUP field). */
76 typedef struct btr_def_s
78 struct btr_def_s
*next_this_bb
;
79 struct btr_def_s
*next_this_group
;
85 /* For a branch register setting insn that has a constant
86 source (i.e. a label), group links together all the
87 insns with the same source. For other branch register
88 setting insns, group is NULL. */
91 /* If this def has a reaching use which is not a simple use
92 in a branch instruction, then has_ambiguous_use will be true,
93 and we will not attempt to migrate this definition. */
94 char has_ambiguous_use
;
95 /* live_range is an approximation to the true live range for this
96 def/use web, because it records the set of blocks that contain
97 the live range. There could be other live ranges for the same
98 branch register in that set of blocks, either in the block
99 containing the def (before the def), or in a block containing
100 a use (after the use). If there are such other live ranges, then
101 other_btr_uses_before_def or other_btr_uses_after_use must be set true
103 char other_btr_uses_before_def
;
104 char other_btr_uses_after_use
;
108 static int issue_rate
;
110 static int basic_block_freq (basic_block
);
111 static int insn_sets_btr_p (rtx
, int, int *);
112 static rtx
*find_btr_use (rtx
);
113 static int btr_referenced_p (rtx
, rtx
*);
114 static int find_btr_reference (rtx
*, void *);
115 static void find_btr_def_group (btr_def_group
*, btr_def
);
116 static btr_def
add_btr_def (fibheap_t
, basic_block
, int, rtx
,
117 unsigned int, int, btr_def_group
*);
118 static btr_user
new_btr_user (basic_block
, int, rtx
);
119 static void dump_hard_reg_set (HARD_REG_SET
);
120 static void dump_btrs_live (int);
121 static void note_other_use_this_block (unsigned int, btr_user
);
122 static void compute_defs_uses_and_gen (fibheap_t
, btr_def
*,btr_user
*,
123 sbitmap
*, sbitmap
*, HARD_REG_SET
*);
124 static void compute_kill (sbitmap
*, sbitmap
*, HARD_REG_SET
*);
125 static void compute_out (sbitmap
*bb_out
, sbitmap
*, sbitmap
*, int);
126 static void link_btr_uses (btr_def
*, btr_user
*, sbitmap
*, sbitmap
*, int);
127 static void build_btr_def_use_webs (fibheap_t
);
128 static int block_at_edge_of_live_range_p (int, btr_def
);
129 static void clear_btr_from_live_range (btr_def def
);
130 static void add_btr_to_live_range (btr_def
);
131 static void augment_live_range (bitmap
, HARD_REG_SET
*, basic_block
,
133 static int choose_btr (HARD_REG_SET
);
134 static void combine_btr_defs (btr_def
, HARD_REG_SET
*);
135 static void btr_def_live_range (btr_def
, HARD_REG_SET
*);
136 static void move_btr_def (basic_block
, int, btr_def
, bitmap
, HARD_REG_SET
*);
137 static int migrate_btr_def (btr_def
, int);
138 static void migrate_btr_defs (enum reg_class
, int);
139 static int can_move_up (basic_block
, rtx
, int);
140 static void note_btr_set (rtx
, rtx
, void *);
142 /* The following code performs code motion of target load instructions
143 (instructions that set branch target registers), to move them
144 forward away from the branch instructions and out of loops (or,
145 more generally, from a more frequently executed place to a less
146 frequently executed place).
147 Moving target load instructions further in front of the branch
148 instruction that uses the target register value means that the hardware
149 has a better chance of preloading the instructions at the branch
150 target by the time the branch is reached. This avoids bubbles
151 when a taken branch needs to flush out the pipeline.
152 Moving target load instructions out of loops means they are executed
155 /* An obstack to hold the def-use web data structures built up for
156 migrating branch target load instructions. */
157 static struct obstack migrate_btrl_obstack
;
159 /* Array indexed by basic block number, giving the set of registers
160 live in that block. */
161 static HARD_REG_SET
*btrs_live
;
163 /* Array indexed by basic block number, giving the set of registers live at
164 the end of that block, including any uses by a final jump insn, if any. */
165 static HARD_REG_SET
*btrs_live_at_end
;
167 /* Set of all target registers that we are willing to allocate. */
168 static HARD_REG_SET all_btrs
;
170 /* Provide lower and upper bounds for target register numbers, so that
171 we don't need to search through all the hard registers all the time. */
172 static int first_btr
, last_btr
;
176 /* Return an estimate of the frequency of execution of block bb. */
178 basic_block_freq (basic_block bb
)
180 return bb
->frequency
;
183 static rtx
*btr_reference_found
;
185 /* A subroutine of btr_referenced_p, called through for_each_rtx.
186 PREG is a pointer to an rtx that is to be excluded from the
187 traversal. If we find a reference to a target register anywhere
188 else, return 1, and put a pointer to it into btr_reference_found. */
190 find_btr_reference (rtx
*px
, void *preg
)
198 if (GET_CODE (x
) != REG
)
201 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
)) - 1; i
>= 0; i
--)
202 if (TEST_HARD_REG_BIT (all_btrs
, regno
+i
))
204 btr_reference_found
= px
;
210 /* Return nonzero if X references (sets or reads) any branch target register.
211 If EXCLUDEP is set, disregard any references within the rtx pointed to
212 by it. If returning nonzero, also set btr_reference_found as above. */
214 btr_referenced_p (rtx x
, rtx
*excludep
)
216 return for_each_rtx (&x
, find_btr_reference
, excludep
);
219 /* Return true if insn is an instruction that sets a target register.
220 if CHECK_CONST is true, only return true if the source is constant.
221 If such a set is found and REGNO is nonzero, assign the register number
222 of the destination register to *REGNO. */
224 insn_sets_btr_p (rtx insn
, int check_const
, int *regno
)
228 if (GET_CODE (insn
) == INSN
229 && (set
= single_set (insn
)))
231 rtx dest
= SET_DEST (set
);
232 rtx src
= SET_SRC (set
);
234 if (GET_CODE (dest
) == SUBREG
)
235 dest
= XEXP (dest
, 0);
237 if (GET_CODE (dest
) == REG
238 && TEST_HARD_REG_BIT (all_btrs
, REGNO (dest
)))
240 if (btr_referenced_p (src
, NULL
))
242 if (!check_const
|| CONSTANT_P (src
))
245 *regno
= REGNO (dest
);
253 /* Find and return a use of a target register within an instruction INSN. */
255 find_btr_use (rtx insn
)
257 return btr_referenced_p (insn
, NULL
) ? btr_reference_found
: NULL
;
260 /* Find the group that the target register definition DEF belongs
261 to in the list starting with *ALL_BTR_DEF_GROUPS. If no such
262 group exists, create one. Add def to the group. */
264 find_btr_def_group (btr_def_group
*all_btr_def_groups
, btr_def def
)
266 if (insn_sets_btr_p (def
->insn
, 1, NULL
))
268 btr_def_group this_group
;
269 rtx def_src
= SET_SRC (single_set (def
->insn
));
271 /* ?? This linear search is an efficiency concern, particularly
272 as the search will almost always fail to find a match. */
273 for (this_group
= *all_btr_def_groups
;
275 this_group
= this_group
->next
)
276 if (rtx_equal_p (def_src
, this_group
->src
))
281 this_group
= obstack_alloc (&migrate_btrl_obstack
,
282 sizeof (struct btr_def_group_s
));
283 this_group
->src
= def_src
;
284 this_group
->members
= NULL
;
285 this_group
->next
= *all_btr_def_groups
;
286 *all_btr_def_groups
= this_group
;
288 def
->group
= this_group
;
289 def
->next_this_group
= this_group
->members
;
290 this_group
->members
= def
;
296 /* Create a new target register definition structure, for a definition in
297 block BB, instruction INSN, and insert it into ALL_BTR_DEFS. Return
298 the new definition. */
300 add_btr_def (fibheap_t all_btr_defs
, basic_block bb
, int insn_luid
, rtx insn
,
301 unsigned int dest_reg
, int other_btr_uses_before_def
,
302 btr_def_group
*all_btr_def_groups
)
305 = obstack_alloc (&migrate_btrl_obstack
, sizeof (struct btr_def_s
));
307 this->luid
= insn_luid
;
309 this->btr
= dest_reg
;
310 this->cost
= basic_block_freq (bb
);
311 this->has_ambiguous_use
= 0;
312 this->other_btr_uses_before_def
= other_btr_uses_before_def
;
313 this->other_btr_uses_after_use
= 0;
314 this->next_this_bb
= NULL
;
315 this->next_this_group
= NULL
;
317 this->live_range
= NULL
;
318 find_btr_def_group (all_btr_def_groups
, this);
320 fibheap_insert (all_btr_defs
, -this->cost
, this);
323 fprintf (rtl_dump_file
,
324 "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n",
325 dest_reg
, bb
->index
, INSN_UID (insn
), (this->group
? "" : ":not const"),
331 /* Create a new target register user structure, for a use in block BB,
332 instruction INSN. Return the new user. */
334 new_btr_user (basic_block bb
, int insn_luid
, rtx insn
)
336 /* This instruction reads target registers. We need
337 to decide whether we can replace all target register
340 rtx
*usep
= find_btr_use (PATTERN (insn
));
342 btr_user user
= NULL
;
346 int unambiguous_single_use
;
348 /* We want to ensure that USE is the only use of a target
349 register in INSN, so that we know that to rewrite INSN to use
350 a different target register, all we have to do is replace USE. */
351 unambiguous_single_use
= !btr_referenced_p (PATTERN (insn
), usep
);
352 if (!unambiguous_single_use
)
355 use
= usep
? *usep
: NULL_RTX
;
356 user
= obstack_alloc (&migrate_btrl_obstack
, sizeof (struct btr_user_s
));
358 user
->luid
= insn_luid
;
361 user
->other_use_this_block
= 0;
363 user
->n_reaching_defs
= 0;
364 user
->first_reaching_def
= -1;
368 fprintf (rtl_dump_file
, "Uses target reg: { bb %d, insn %d }",
369 bb
->index
, INSN_UID (insn
));
372 fprintf (rtl_dump_file
, ": unambiguous use of reg %d\n",
379 /* Write the contents of S to the dump file. */
381 dump_hard_reg_set (HARD_REG_SET s
)
384 for (reg
= 0; reg
< FIRST_PSEUDO_REGISTER
; reg
++)
385 if (TEST_HARD_REG_BIT (s
, reg
))
386 fprintf (rtl_dump_file
, " %d", reg
);
389 /* Write the set of target regs live in block BB to the dump file. */
391 dump_btrs_live (int bb
)
393 fprintf (rtl_dump_file
, "BB%d live:", bb
);
394 dump_hard_reg_set (btrs_live
[bb
]);
395 fprintf (rtl_dump_file
, "\n");
398 /* REGNO is the number of a branch target register that is being used or
399 set. USERS_THIS_BB is a list of preceding branch target register users;
400 If any of them use the same register, set their other_use_this_block
403 note_other_use_this_block (unsigned int regno
, btr_user users_this_bb
)
407 for (user
= users_this_bb
; user
!= NULL
; user
= user
->next
)
408 if (user
->use
&& REGNO (user
->use
) == regno
)
409 user
->other_use_this_block
= 1;
413 btr_user users_this_bb
;
414 HARD_REG_SET btrs_written_in_block
;
415 HARD_REG_SET btrs_live_in_block
;
420 /* Called via note_stores or directly to register stores into /
421 clobbers of a branch target register DEST that are not recognized as
422 straightforward definitions. DATA points to information about the
423 current basic block that needs updating. */
425 note_btr_set (rtx dest
, rtx set ATTRIBUTE_UNUSED
, void *data
)
427 defs_uses_info
*info
= data
;
428 int regno
, end_regno
;
430 if (GET_CODE (dest
) != REG
)
432 regno
= REGNO (dest
);
433 end_regno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
434 for (; regno
< end_regno
; regno
++)
435 if (TEST_HARD_REG_BIT (all_btrs
, regno
))
437 note_other_use_this_block (regno
, info
->users_this_bb
);
438 SET_HARD_REG_BIT (info
->btrs_written_in_block
, regno
);
439 SET_HARD_REG_BIT (info
->btrs_live_in_block
, regno
);
440 sbitmap_difference (info
->bb_gen
, info
->bb_gen
,
441 info
->btr_defset
[regno
- first_btr
]);
446 compute_defs_uses_and_gen (fibheap_t all_btr_defs
, btr_def
*def_array
,
447 btr_user
*use_array
, sbitmap
*btr_defset
,
448 sbitmap
*bb_gen
, HARD_REG_SET
*btrs_written
)
450 /* Scan the code building up the set of all defs and all uses.
451 For each target register, build the set of defs of that register.
452 For each block, calculate the set of target registers
453 written in that block.
454 Also calculate the set of btrs ever live in that block.
458 btr_def_group all_btr_def_groups
= NULL
;
461 sbitmap_vector_zero (bb_gen
, n_basic_blocks
);
462 for (i
= 0; i
< n_basic_blocks
; i
++)
464 basic_block bb
= BASIC_BLOCK (i
);
466 btr_def defs_this_bb
= NULL
;
471 info
.users_this_bb
= NULL
;
472 info
.bb_gen
= bb_gen
[i
];
473 info
.btr_defset
= btr_defset
;
475 CLEAR_HARD_REG_SET (info
.btrs_live_in_block
);
476 CLEAR_HARD_REG_SET (info
.btrs_written_in_block
);
477 for (reg
= first_btr
; reg
<= last_btr
; reg
++)
478 if (TEST_HARD_REG_BIT (all_btrs
, reg
)
479 && REGNO_REG_SET_P (bb
->global_live_at_start
, reg
))
480 SET_HARD_REG_BIT (info
.btrs_live_in_block
, reg
);
482 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
));
484 insn
= NEXT_INSN (insn
), insn_luid
++)
489 int insn_uid
= INSN_UID (insn
);
491 if (insn_sets_btr_p (insn
, 0, ®no
))
493 btr_def def
= add_btr_def (
494 all_btr_defs
, bb
, insn_luid
, insn
, regno
,
495 TEST_HARD_REG_BIT (info
.btrs_live_in_block
, regno
),
496 &all_btr_def_groups
);
498 def_array
[insn_uid
] = def
;
499 SET_HARD_REG_BIT (info
.btrs_written_in_block
, regno
);
500 SET_HARD_REG_BIT (info
.btrs_live_in_block
, regno
);
501 sbitmap_difference (bb_gen
[i
], bb_gen
[i
],
502 btr_defset
[regno
- first_btr
]);
503 SET_BIT (bb_gen
[i
], insn_uid
);
504 def
->next_this_bb
= defs_this_bb
;
506 SET_BIT (btr_defset
[regno
- first_btr
], insn_uid
);
507 note_other_use_this_block (regno
, info
.users_this_bb
);
511 if (btr_referenced_p (PATTERN (insn
), NULL
))
513 btr_user user
= new_btr_user (bb
, insn_luid
, insn
);
515 use_array
[insn_uid
] = user
;
517 SET_HARD_REG_BIT (info
.btrs_live_in_block
,
522 for (reg
= first_btr
; reg
<= last_btr
; reg
++)
523 if (TEST_HARD_REG_BIT (all_btrs
, reg
)
524 && refers_to_regno_p (reg
, reg
+ 1, user
->insn
,
527 note_other_use_this_block (reg
,
529 SET_HARD_REG_BIT (info
.btrs_live_in_block
, reg
);
531 note_stores (PATTERN (insn
), note_btr_set
, &info
);
533 user
->next
= info
.users_this_bb
;
534 info
.users_this_bb
= user
;
536 if (GET_CODE (insn
) == CALL_INSN
)
538 HARD_REG_SET
*clobbered
= &call_used_reg_set
;
539 HARD_REG_SET call_saved
;
540 rtx pat
= PATTERN (insn
);
543 /* Check for sibcall. */
544 if (GET_CODE (pat
) == PARALLEL
)
545 for (i
= XVECLEN (pat
, 0) - 1; i
>= 0; i
--)
546 if (GET_CODE (XVECEXP (pat
, 0, i
)) == RETURN
)
548 COMPL_HARD_REG_SET (call_saved
,
550 clobbered
= &call_saved
;
553 for (regno
= first_btr
; regno
<= last_btr
; regno
++)
554 if (TEST_HARD_REG_BIT (*clobbered
, regno
))
555 note_btr_set (regno_reg_rtx
[regno
], NULL_RTX
, &info
);
561 COPY_HARD_REG_SET (btrs_live
[i
], info
.btrs_live_in_block
);
562 COPY_HARD_REG_SET (btrs_written
[i
], info
.btrs_written_in_block
);
564 REG_SET_TO_HARD_REG_SET (btrs_live_at_end
[i
], bb
->global_live_at_end
);
565 /* If this block ends in a jump insn, add any uses or even clobbers
566 of branch target registers that it might have. */
567 for (insn
= BB_END (bb
); insn
!= BB_HEAD (bb
) && ! INSN_P (insn
); )
568 insn
= PREV_INSN (insn
);
569 /* ??? for the fall-through edge, it would make sense to insert the
570 btr set on the edge, but that would require to split the block
571 early on so that we can distinguish between dominance from the fall
572 through edge - which can use the call-clobbered registers - from
573 dominance by the throw edge. */
574 if (can_throw_internal (insn
))
578 COPY_HARD_REG_SET (tmp
, call_used_reg_set
);
579 AND_HARD_REG_SET (tmp
, all_btrs
);
580 IOR_HARD_REG_SET (btrs_live_at_end
[i
], tmp
);
583 if (can_throw
|| GET_CODE (insn
) == JUMP_INSN
)
587 for (regno
= first_btr
; regno
<= last_btr
; regno
++)
588 if (refers_to_regno_p (regno
, regno
+1, insn
, NULL
))
589 SET_HARD_REG_BIT (btrs_live_at_end
[i
], regno
);
598 compute_kill (sbitmap
*bb_kill
, sbitmap
*btr_defset
,
599 HARD_REG_SET
*btrs_written
)
604 /* For each basic block, form the set BB_KILL - the set
605 of definitions that the block kills. */
606 sbitmap_vector_zero (bb_kill
, n_basic_blocks
);
607 for (i
= 0; i
< n_basic_blocks
; i
++)
609 for (regno
= first_btr
; regno
<= last_btr
; regno
++)
610 if (TEST_HARD_REG_BIT (all_btrs
, regno
)
611 && TEST_HARD_REG_BIT (btrs_written
[i
], regno
))
612 sbitmap_a_or_b (bb_kill
[i
], bb_kill
[i
],
613 btr_defset
[regno
- first_btr
]);
618 compute_out (sbitmap
*bb_out
, sbitmap
*bb_gen
, sbitmap
*bb_kill
, int max_uid
)
620 /* Perform iterative dataflow:
621 Initially, for all blocks, BB_OUT = BB_GEN.
623 BB_IN = union over predecessors of BB_OUT(pred)
624 BB_OUT = (BB_IN - BB_KILL) + BB_GEN
625 Iterate until the bb_out sets stop growing. */
628 sbitmap bb_in
= sbitmap_alloc (max_uid
);
630 for (i
= 0; i
< n_basic_blocks
; i
++)
631 sbitmap_copy (bb_out
[i
], bb_gen
[i
]);
637 for (i
= 0; i
< n_basic_blocks
; i
++)
639 sbitmap_union_of_preds (bb_in
, bb_out
, i
);
640 changed
|= sbitmap_union_of_diff_cg (bb_out
[i
], bb_gen
[i
],
644 sbitmap_free (bb_in
);
648 link_btr_uses (btr_def
*def_array
, btr_user
*use_array
, sbitmap
*bb_out
,
649 sbitmap
*btr_defset
, int max_uid
)
652 sbitmap reaching_defs
= sbitmap_alloc (max_uid
);
654 /* Link uses to the uses lists of all of their reaching defs.
655 Count up the number of reaching defs of each use. */
656 for (i
= 0; i
< n_basic_blocks
; i
++)
658 basic_block bb
= BASIC_BLOCK (i
);
662 sbitmap_union_of_preds (reaching_defs
, bb_out
, i
);
663 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
));
665 insn
= NEXT_INSN (insn
))
669 int insn_uid
= INSN_UID (insn
);
671 btr_def def
= def_array
[insn_uid
];
672 btr_user user
= use_array
[insn_uid
];
675 /* Remove all reaching defs of regno except
677 sbitmap_difference (reaching_defs
, reaching_defs
,
678 btr_defset
[def
->btr
- first_btr
]);
679 SET_BIT(reaching_defs
, insn_uid
);
684 /* Find all the reaching defs for this use. */
685 sbitmap reaching_defs_of_reg
= sbitmap_alloc(max_uid
);
690 reaching_defs_of_reg
,
692 btr_defset
[REGNO (user
->use
) - first_btr
]);
697 sbitmap_zero (reaching_defs_of_reg
);
698 for (reg
= first_btr
; reg
<= last_btr
; reg
++)
699 if (TEST_HARD_REG_BIT (all_btrs
, reg
)
700 && refers_to_regno_p (reg
, reg
+ 1, user
->insn
,
702 sbitmap_a_or_b_and_c (reaching_defs_of_reg
,
703 reaching_defs_of_reg
,
705 btr_defset
[reg
- first_btr
]);
707 EXECUTE_IF_SET_IN_SBITMAP (reaching_defs_of_reg
, 0, uid
,
709 btr_def def
= def_array
[uid
];
711 /* We now know that def reaches user. */
714 fprintf (rtl_dump_file
,
715 "Def in insn %d reaches use in insn %d\n",
718 user
->n_reaching_defs
++;
720 def
->has_ambiguous_use
= 1;
721 if (user
->first_reaching_def
!= -1)
722 { /* There is more than one reaching def. This is
723 a rare case, so just give up on this def/use
724 web when it occurs. */
725 def
->has_ambiguous_use
= 1;
726 def_array
[user
->first_reaching_def
]
727 ->has_ambiguous_use
= 1;
729 fprintf (rtl_dump_file
,
730 "(use %d has multiple reaching defs)\n",
734 user
->first_reaching_def
= uid
;
735 if (user
->other_use_this_block
)
736 def
->other_btr_uses_after_use
= 1;
737 user
->next
= def
->uses
;
740 sbitmap_free (reaching_defs_of_reg
);
743 if (GET_CODE (insn
) == CALL_INSN
)
747 for (regno
= first_btr
; regno
<= last_btr
; regno
++)
748 if (TEST_HARD_REG_BIT (all_btrs
, regno
)
749 && TEST_HARD_REG_BIT (call_used_reg_set
, regno
))
750 sbitmap_difference (reaching_defs
, reaching_defs
,
751 btr_defset
[regno
- first_btr
]);
756 sbitmap_free (reaching_defs
);
760 build_btr_def_use_webs (fibheap_t all_btr_defs
)
762 const int max_uid
= get_max_uid ();
763 btr_def
*def_array
= xcalloc (max_uid
, sizeof (btr_def
));
764 btr_user
*use_array
= xcalloc (max_uid
, sizeof (btr_user
));
765 sbitmap
*btr_defset
= sbitmap_vector_alloc (
766 (last_btr
- first_btr
) + 1, max_uid
);
767 sbitmap
*bb_gen
= sbitmap_vector_alloc (n_basic_blocks
, max_uid
);
768 HARD_REG_SET
*btrs_written
= xcalloc (n_basic_blocks
, sizeof (HARD_REG_SET
));
772 sbitmap_vector_zero (btr_defset
, (last_btr
- first_btr
) + 1);
774 compute_defs_uses_and_gen (all_btr_defs
, def_array
, use_array
, btr_defset
,
775 bb_gen
, btrs_written
);
777 bb_kill
= sbitmap_vector_alloc (n_basic_blocks
, max_uid
);
778 compute_kill (bb_kill
, btr_defset
, btrs_written
);
781 bb_out
= sbitmap_vector_alloc (n_basic_blocks
, max_uid
);
782 compute_out (bb_out
, bb_gen
, bb_kill
, max_uid
);
784 sbitmap_vector_free (bb_gen
);
785 sbitmap_vector_free (bb_kill
);
787 link_btr_uses (def_array
, use_array
, bb_out
, btr_defset
, max_uid
);
789 sbitmap_vector_free (bb_out
);
790 sbitmap_vector_free (btr_defset
);
795 /* Return true if basic block BB contains the start or end of the
796 live range of the definition DEF, AND there are other live
797 ranges of the same target register that include BB. */
799 block_at_edge_of_live_range_p (int bb
, btr_def def
)
801 if (def
->other_btr_uses_before_def
&& BASIC_BLOCK (bb
) == def
->bb
)
803 else if (def
->other_btr_uses_after_use
)
806 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
807 if (BASIC_BLOCK (bb
) == user
->bb
)
813 /* We are removing the def/use web DEF. The target register
814 used in this web is therefore no longer live in the live range
815 of this web, so remove it from the live set of all basic blocks
816 in the live range of the web.
817 Blocks at the boundary of the live range may contain other live
818 ranges for the same target register, so we have to be careful
819 to remove the target register from the live set of these blocks
820 only if they do not contain other live ranges for the same register. */
822 clear_btr_from_live_range (btr_def def
)
826 EXECUTE_IF_SET_IN_BITMAP
827 (def
->live_range
, 0, bb
,
829 if ((!def
->other_btr_uses_before_def
830 && !def
->other_btr_uses_after_use
)
831 || !block_at_edge_of_live_range_p (bb
, def
))
833 CLEAR_HARD_REG_BIT (btrs_live
[bb
], def
->btr
);
834 CLEAR_HARD_REG_BIT (btrs_live_at_end
[bb
], def
->btr
);
842 /* We are adding the def/use web DEF. Add the target register used
843 in this web to the live set of all of the basic blocks that contain
844 the live range of the web. */
846 add_btr_to_live_range (btr_def def
)
849 EXECUTE_IF_SET_IN_BITMAP
850 (def
->live_range
, 0, bb
,
852 SET_HARD_REG_BIT (btrs_live
[bb
], def
->btr
);
853 SET_HARD_REG_BIT (btrs_live_at_end
[bb
], def
->btr
);
859 /* Update a live range to contain the basic block NEW_BLOCK, and all
860 blocks on paths between the existing live range and NEW_BLOCK.
861 HEAD is a block contained in the existing live range that dominates
862 all other blocks in the existing live range.
863 Also add to the set BTRS_LIVE_IN_RANGE all target registers that
864 are live in the blocks that we add to the live range.
865 It is a precondition that either NEW_BLOCK dominates HEAD,or
866 HEAD dom NEW_BLOCK. This is used to speed up the
867 implementation of this function. */
869 augment_live_range (bitmap live_range
, HARD_REG_SET
*btrs_live_in_range
,
870 basic_block head_bb
, basic_block new_bb
)
872 basic_block
*worklist
, *tos
;
874 tos
= worklist
= xmalloc (sizeof (basic_block
) * (n_basic_blocks
+ 1));
876 if (dominated_by_p (CDI_DOMINATORS
, new_bb
, head_bb
))
878 else if (dominated_by_p (CDI_DOMINATORS
, head_bb
, new_bb
))
881 int new_block
= new_bb
->index
;
883 bitmap_set_bit (live_range
, new_block
);
884 if (flag_btr_bb_exclusive
)
885 IOR_HARD_REG_SET (*btrs_live_in_range
, btrs_live
[new_block
]);
888 IOR_HARD_REG_SET (*btrs_live_in_range
, btrs_live_at_end
[new_block
]);
889 IOR_HARD_REG_SET (*btrs_live_in_range
, btrs_live
[head_bb
->index
]);
893 fprintf (rtl_dump_file
,
894 "Adding end of block %d and rest of %d to live range\n",
895 new_block
, head_bb
->index
);
896 fprintf (rtl_dump_file
,"Now live btrs are ");
897 dump_hard_reg_set (*btrs_live_in_range
);
898 fprintf (rtl_dump_file
, "\n");
900 for (e
= head_bb
->pred
; e
; e
= e
->pred_next
)
906 while (tos
!= worklist
)
908 basic_block bb
= *--tos
;
909 if (!bitmap_bit_p (live_range
, bb
->index
))
913 bitmap_set_bit (live_range
, bb
->index
);
914 IOR_HARD_REG_SET (*btrs_live_in_range
,
915 btrs_live
[bb
->index
]);
918 fprintf (rtl_dump_file
,
919 "Adding block %d to live range\n", bb
->index
);
920 fprintf (rtl_dump_file
,"Now live btrs are ");
921 dump_hard_reg_set (*btrs_live_in_range
);
922 fprintf (rtl_dump_file
, "\n");
925 for (e
= bb
->pred
; e
!= NULL
; e
= e
->pred_next
)
927 basic_block pred
= e
->src
;
928 if (!bitmap_bit_p (live_range
, pred
->index
))
937 /* Return the most desirable target register that is not in
938 the set USED_BTRS. */
940 choose_btr (HARD_REG_SET used_btrs
)
943 GO_IF_HARD_REG_SUBSET (all_btrs
, used_btrs
, give_up
);
945 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
947 #ifdef REG_ALLOC_ORDER
948 int regno
= reg_alloc_order
[i
];
952 if (TEST_HARD_REG_BIT (all_btrs
, regno
)
953 && !TEST_HARD_REG_BIT (used_btrs
, regno
))
960 /* Calculate the set of basic blocks that contain the live range of
962 Also calculate the set of target registers that are live at time
963 in this live range, but ignore the live range represented by DEF
964 when calculating this set. */
966 btr_def_live_range (btr_def def
, HARD_REG_SET
*btrs_live_in_range
)
968 if (!def
->live_range
)
972 def
->live_range
= BITMAP_XMALLOC ();
974 bitmap_set_bit (def
->live_range
, def
->bb
->index
);
975 if (flag_btr_bb_exclusive
)
976 COPY_HARD_REG_SET (*btrs_live_in_range
, btrs_live
[def
->bb
->index
]);
978 COPY_HARD_REG_SET (*btrs_live_in_range
,
979 btrs_live_at_end
[def
->bb
->index
]);
981 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
982 augment_live_range (def
->live_range
, btrs_live_in_range
,
987 /* def->live_range is accurate, but we need to recompute
988 the set of target registers live over it, because migration
989 of other PT instructions may have affected it.
992 int def_bb
= def
->bb
->index
;
994 CLEAR_HARD_REG_SET (*btrs_live_in_range
);
995 if (flag_btr_bb_exclusive
)
996 EXECUTE_IF_SET_IN_BITMAP
997 (def
->live_range
, 0, bb
,
999 IOR_HARD_REG_SET (*btrs_live_in_range
, btrs_live
[bb
]);
1002 EXECUTE_IF_SET_IN_BITMAP
1003 (def
->live_range
, 0, bb
,
1005 IOR_HARD_REG_SET (*btrs_live_in_range
,
1007 ? btrs_live_at_end
: btrs_live
) [bb
]);
1010 if (!def
->other_btr_uses_before_def
&&
1011 !def
->other_btr_uses_after_use
)
1012 CLEAR_HARD_REG_BIT (*btrs_live_in_range
, def
->btr
);
1015 /* Merge into the def/use web DEF any other def/use webs in the same
1016 group that are dominated by DEF, provided that there is a target
1017 register available to allocate to the merged web. */
1019 combine_btr_defs (btr_def def
, HARD_REG_SET
*btrs_live_in_range
)
1023 for (other_def
= def
->group
->members
;
1025 other_def
= other_def
->next_this_group
)
1027 if (other_def
!= def
1028 && other_def
->uses
!= NULL
1029 && ! other_def
->has_ambiguous_use
1030 && dominated_by_p (CDI_DOMINATORS
, other_def
->bb
, def
->bb
))
1032 /* def->bb dominates the other def, so def and other_def could
1034 /* Merge their live ranges, and get the set of
1035 target registers live over the merged range. */
1037 HARD_REG_SET combined_btrs_live
;
1038 bitmap combined_live_range
= BITMAP_XMALLOC ();
1041 if (other_def
->live_range
== NULL
)
1043 HARD_REG_SET dummy_btrs_live_in_range
;
1044 btr_def_live_range (other_def
, &dummy_btrs_live_in_range
);
1046 COPY_HARD_REG_SET (combined_btrs_live
, *btrs_live_in_range
);
1047 bitmap_copy (combined_live_range
, def
->live_range
);
1049 for (user
= other_def
->uses
; user
!= NULL
; user
= user
->next
)
1050 augment_live_range (combined_live_range
, &combined_btrs_live
,
1053 btr
= choose_btr (combined_btrs_live
);
1056 /* We can combine them. */
1058 fprintf (rtl_dump_file
,
1059 "Combining def in insn %d with def in insn %d\n",
1060 INSN_UID (other_def
->insn
), INSN_UID (def
->insn
));
1063 user
= other_def
->uses
;
1064 while (user
!= NULL
)
1066 btr_user next
= user
->next
;
1068 user
->next
= def
->uses
;
1072 /* Combining def/use webs can make target registers live
1073 after uses where they previously were not. This means
1074 some REG_DEAD notes may no longer be correct. We could
1075 be more precise about this if we looked at the combined
1076 live range, but here I just delete any REG_DEAD notes
1077 in case they are no longer correct. */
1078 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
1079 remove_note (user
->insn
,
1080 find_regno_note (user
->insn
, REG_DEAD
,
1081 REGNO (user
->use
)));
1082 clear_btr_from_live_range (other_def
);
1083 other_def
->uses
= NULL
;
1084 bitmap_copy (def
->live_range
, combined_live_range
);
1085 if (other_def
->other_btr_uses_after_use
)
1086 def
->other_btr_uses_after_use
= 1;
1087 COPY_HARD_REG_SET (*btrs_live_in_range
, combined_btrs_live
);
1089 /* Delete the old target register initialization. */
1090 delete_insn (other_def
->insn
);
1093 BITMAP_XFREE (combined_live_range
);
1098 /* Move the definition DEF from its current position to basic
1099 block NEW_DEF_BB, and modify it to use branch target register BTR.
1100 Delete the old defining insn, and insert a new one in NEW_DEF_BB.
1101 Update all reaching uses of DEF in the RTL to use BTR.
1102 If this new position means that other defs in the
1103 same group can be combined with DEF then combine them. */
1105 move_btr_def (basic_block new_def_bb
, int btr
, btr_def def
, bitmap live_range
,
1106 HARD_REG_SET
*btrs_live_in_range
)
1108 /* We can move the instruction.
1109 Set a target register in block NEW_DEF_BB to the value
1110 needed for this target register definition.
1111 Replace all uses of the old target register definition by
1112 uses of the new definition. Delete the old definition. */
1113 basic_block b
= new_def_bb
;
1114 rtx insp
= BB_HEAD (b
);
1115 rtx old_insn
= def
->insn
;
1119 enum machine_mode btr_mode
;
1124 fprintf(rtl_dump_file
, "migrating to basic block %d, using reg %d\n",
1125 new_def_bb
->index
, btr
);
1127 clear_btr_from_live_range (def
);
1129 def
->bb
= new_def_bb
;
1131 def
->cost
= basic_block_freq (new_def_bb
);
1132 def
->other_btr_uses_before_def
1133 = TEST_HARD_REG_BIT (btrs_live
[b
->index
], btr
) ? 1 : 0;
1134 bitmap_copy (def
->live_range
, live_range
);
1135 combine_btr_defs (def
, btrs_live_in_range
);
1137 add_btr_to_live_range (def
);
1138 if (GET_CODE (insp
) == CODE_LABEL
)
1139 insp
= NEXT_INSN (insp
);
1140 /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some
1141 optimizations can result in insp being both first and last insn of
1143 /* ?? some assertions to check that insp is sensible? */
1145 if (def
->other_btr_uses_before_def
)
1148 for (insp
= BB_END (b
); ! INSN_P (insp
); insp
= PREV_INSN (insp
))
1149 if (insp
== BB_HEAD (b
))
1151 if (GET_CODE (insp
) == JUMP_INSN
|| can_throw_internal (insp
))
1152 insp
= PREV_INSN (insp
);
1155 set
= single_set (old_insn
);
1156 src
= SET_SRC (set
);
1157 btr_mode
= GET_MODE (SET_DEST (set
));
1158 btr_rtx
= gen_rtx (REG
, btr_mode
, btr
);
1160 new_insn
= gen_move_insn (btr_rtx
, src
);
1162 /* Insert target register initialization at head of basic block. */
1163 def
->insn
= emit_insn_after (new_insn
, insp
);
1165 regs_ever_live
[btr
] = 1;
1168 fprintf (rtl_dump_file
, "New pt is insn %d, inserted after insn %d\n",
1169 INSN_UID (def
->insn
), INSN_UID (insp
));
1171 /* Delete the old target register initialization. */
1172 delete_insn (old_insn
);
1174 /* Replace each use of the old target register by a use of the new target
1176 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
1178 /* Some extra work here to ensure consistent modes, because
1179 it seems that a target register REG rtx can be given a different
1180 mode depending on the context (surely that should not be
1182 rtx replacement_rtx
;
1183 if (GET_MODE (user
->use
) == GET_MODE (btr_rtx
)
1184 || GET_MODE (user
->use
) == VOIDmode
)
1185 replacement_rtx
= btr_rtx
;
1187 replacement_rtx
= gen_rtx (REG
, GET_MODE (user
->use
), btr
);
1188 replace_rtx (user
->insn
, user
->use
, replacement_rtx
);
1189 user
->use
= replacement_rtx
;
1193 /* We anticipate intra-block scheduling to be done. See if INSN could move
1194 up within BB by N_INSNS. */
1196 can_move_up (basic_block bb
, rtx insn
, int n_insns
)
1198 while (insn
!= BB_HEAD (bb
) && n_insns
> 0)
1200 insn
= PREV_INSN (insn
);
1201 /* ??? What if we have an anti-dependency that actually prevents the
1202 scheduler from doing the move? We'd like to re-allocate the register,
1203 but not necessarily put the load into another basic block. */
1207 return n_insns
<= 0;
1210 /* Attempt to migrate the target register definition DEF to an
1211 earlier point in the flowgraph.
1213 It is a precondition of this function that DEF is migratable:
1214 i.e. it has a constant source, and all uses are unambiguous.
1216 Only migrations that reduce the cost of DEF will be made.
1217 MIN_COST is the lower bound on the cost of the DEF after migration.
1218 If we migrate DEF so that its cost falls below MIN_COST,
1219 then we do not attempt to migrate further. The idea is that
1220 we migrate definitions in a priority order based on their cost,
1221 when the cost of this definition falls below MIN_COST, then
1222 there is another definition with cost == MIN_COST which now
1223 has a higher priority than this definition.
1225 Return nonzero if there may be benefit from attempting to
1226 migrate this DEF further (i.e. we have reduced the cost below
1227 MIN_COST, but we may be able to reduce it further).
1228 Return zero if no further migration is possible. */
1230 migrate_btr_def (btr_def def
, int min_cost
)
1233 HARD_REG_SET btrs_live_in_range
;
1234 int btr_used_near_def
= 0;
1235 int def_basic_block_freq
;
1240 int def_latency
= 1;
1243 fprintf (rtl_dump_file
,
1244 "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ",
1245 INSN_UID (def
->insn
), def
->cost
, min_cost
);
1247 if (!def
->group
|| def
->has_ambiguous_use
)
1248 /* These defs are not migratable. */
1251 fprintf (rtl_dump_file
, "it's not migratable\n");
1256 /* We have combined this def with another in the same group, so
1257 no need to consider it further.
1261 fprintf (rtl_dump_file
, "it's already combined with another pt\n");
1265 btr_def_live_range (def
, &btrs_live_in_range
);
1266 live_range
= BITMAP_XMALLOC ();
1267 bitmap_copy (live_range
, def
->live_range
);
1269 #ifdef INSN_SCHEDULING
1270 if ((*targetm
.sched
.use_dfa_pipeline_interface
) ())
1271 def_latency
= insn_default_latency (def
->insn
);
1273 def_latency
= result_ready_cost (def
->insn
);
1276 def_latency
*= issue_rate
;
1278 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
1280 if (user
->bb
== def
->bb
1281 && user
->luid
> def
->luid
1282 && (def
->luid
+ def_latency
) > user
->luid
1283 && ! can_move_up (def
->bb
, def
->insn
,
1284 (def
->luid
+ def_latency
) - user
->luid
))
1286 btr_used_near_def
= 1;
1291 def_basic_block_freq
= basic_block_freq (def
->bb
);
1293 for (try = get_immediate_dominator (CDI_DOMINATORS
, def
->bb
);
1294 !give_up
&& try && try != ENTRY_BLOCK_PTR
&& def
->cost
>= min_cost
;
1295 try = get_immediate_dominator (CDI_DOMINATORS
, try))
1297 /* Try to move the instruction that sets the target register into
1299 int try_freq
= basic_block_freq (try);
1302 fprintf (rtl_dump_file
, "trying block %d ...", try->index
);
1304 if (try_freq
< def_basic_block_freq
1305 || (try_freq
== def_basic_block_freq
&& btr_used_near_def
))
1308 augment_live_range (live_range
, &btrs_live_in_range
, def
->bb
, try);
1311 fprintf (rtl_dump_file
, "Now btrs live in range are: ");
1312 dump_hard_reg_set (btrs_live_in_range
);
1313 fprintf (rtl_dump_file
, "\n");
1315 btr
= choose_btr (btrs_live_in_range
);
1318 move_btr_def (try, btr
, def
, live_range
, &btrs_live_in_range
);
1319 bitmap_copy(live_range
, def
->live_range
);
1320 btr_used_near_def
= 0;
1322 def_basic_block_freq
= basic_block_freq (def
->bb
);
1326 /* There are no free target registers available to move
1327 this far forward, so give up */
1330 fprintf (rtl_dump_file
,
1331 "giving up because there are no free target registers\n");
1340 fprintf (rtl_dump_file
, "failed to move\n");
1342 BITMAP_XFREE (live_range
);
1346 /* Attempt to move instructions that set target registers earlier
1347 in the flowgraph, away from their corresponding uses. */
1349 migrate_btr_defs (enum reg_class btr_class
, int allow_callee_save
)
1351 fibheap_t all_btr_defs
= fibheap_new ();
1354 gcc_obstack_init (&migrate_btrl_obstack
);
1359 for (i
= 0; i
< n_basic_blocks
; i
++)
1361 basic_block bb
= BASIC_BLOCK (i
);
1362 fprintf(rtl_dump_file
,
1363 "Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC
1364 " loop-depth = %d idom = %d\n",
1365 i
, (HOST_WIDEST_INT
) bb
->count
, bb
->loop_depth
,
1366 get_immediate_dominator (CDI_DOMINATORS
, bb
)->index
);
1370 CLEAR_HARD_REG_SET (all_btrs
);
1371 for (first_btr
= -1, reg
= 0; reg
< FIRST_PSEUDO_REGISTER
; reg
++)
1372 if (TEST_HARD_REG_BIT (reg_class_contents
[(int) btr_class
], reg
)
1373 && (allow_callee_save
|| call_used_regs
[reg
] || regs_ever_live
[reg
]))
1375 SET_HARD_REG_BIT (all_btrs
, reg
);
1381 btrs_live
= xcalloc (n_basic_blocks
, sizeof (HARD_REG_SET
));
1382 btrs_live_at_end
= xcalloc (n_basic_blocks
, sizeof (HARD_REG_SET
));
1384 build_btr_def_use_webs (all_btr_defs
);
1386 while (!fibheap_empty (all_btr_defs
))
1389 (btr_def
) fibheap_extract_min (all_btr_defs
);
1390 int min_cost
= -fibheap_min_key (all_btr_defs
);
1391 if (migrate_btr_def (def
, min_cost
))
1393 fibheap_insert (all_btr_defs
, -def
->cost
, (void *) def
);
1396 fprintf (rtl_dump_file
,
1397 "Putting insn %d back on queue with priority %d\n",
1398 INSN_UID (def
->insn
), def
->cost
);
1403 if (def
->live_range
)
1404 BITMAP_XFREE (def
->live_range
);
1409 free (btrs_live_at_end
);
1410 obstack_free (&migrate_btrl_obstack
, NULL
);
1411 fibheap_delete (all_btr_defs
);
1415 branch_target_load_optimize (rtx insns
, bool after_prologue_epilogue_gen
)
1417 enum reg_class
class = (*targetm
.branch_target_register_class
) ();
1418 if (class != NO_REGS
)
1420 /* Initialize issue_rate. */
1421 if (targetm
.sched
.issue_rate
)
1422 issue_rate
= (*targetm
.sched
.issue_rate
) ();
1426 /* Build the CFG for migrate_btr_defs. */
1428 /* This may or may not be needed, depending on where we
1430 cleanup_cfg (optimize
? CLEANUP_EXPENSIVE
: 0);
1433 life_analysis (insns
, NULL
, 0);
1435 /* Dominator info is also needed for migrate_btr_def. */
1436 calculate_dominance_info (CDI_DOMINATORS
);
1437 migrate_btr_defs (class,
1438 ((*targetm
.branch_target_register_callee_saved
)
1439 (after_prologue_epilogue_gen
)));
1441 free_dominance_info (CDI_DOMINATORS
);
1443 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
1444 PROP_DEATH_NOTES
| PROP_REG_INFO
);