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"
26 #include "hard-reg-set.h"
33 #include "insn-attr.h"
38 /* Target register optimizations - these are performed after reload. */
40 typedef struct btr_def_group_s
42 struct btr_def_group_s *next;
44 struct btr_def_s *members;
47 typedef struct btr_user_s
49 struct btr_user_s *next;
53 /* If INSN has a single use of a single branch register, then
54 USE points to it within INSN. If there is more than
55 one branch register use, or the use is in some way ambiguous,
59 int first_reaching_def;
60 char other_use_this_block;
63 /* btr_def structs appear on three lists:
64 1. A list of all btr_def structures (head is
65 ALL_BTR_DEFS, linked by the NEXT field).
66 2. A list of branch reg definitions per basic block (head is
67 BB_BTR_DEFS[i], linked by the NEXT_THIS_BB field).
68 3. A list of all branch reg definitions belonging to the same
69 group (head is in a BTR_DEF_GROUP struct, linked by
70 NEXT_THIS_GROUP field). */
72 typedef struct btr_def_s
74 struct btr_def_s *next_this_bb;
75 struct btr_def_s *next_this_group;
81 /* For a branch register setting insn that has a constant
82 source (i.e. a label), group links together all the
83 insns with the same source. For other branch register
84 setting insns, group is NULL. */
87 /* If this def has a reaching use which is not a simple use
88 in a branch instruction, then has_ambiguous_use will be true,
89 and we will not attempt to migrate this definition. */
90 char has_ambiguous_use;
91 /* live_range is an approximation to the true live range for this
92 def/use web, because it records the set of blocks that contain
93 the live range. There could be other live ranges for the same
94 branch register in that set of blocks, either in the block
95 containing the def (before the def), or in a block containing
96 a use (after the use). If there are such other live ranges, then
97 other_btr_uses_before_def or other_btr_uses_after_use must be set true
99 char other_btr_uses_before_def;
100 char other_btr_uses_after_use;
104 static int issue_rate;
106 static int basic_block_freq (basic_block);
107 static int insn_sets_btr_p (rtx, int, int *);
108 static rtx *find_btr_use (rtx);
109 static int btr_referenced_p (rtx, rtx *);
110 static int find_btr_reference (rtx *, void *);
111 static void find_btr_def_group (btr_def_group *, btr_def);
112 static btr_def add_btr_def (fibheap_t, basic_block, int, rtx,
113 unsigned int, int, btr_def_group *);
114 static btr_user new_btr_user (basic_block, int, rtx);
115 static void dump_hard_reg_set (HARD_REG_SET);
116 static void dump_btrs_live (int);
117 static void note_other_use_this_block (unsigned int, btr_user);
118 static void compute_defs_uses_and_gen (fibheap_t, btr_def *,btr_user *,
119 sbitmap *, sbitmap *, HARD_REG_SET *);
120 static void compute_kill (sbitmap *, sbitmap *, HARD_REG_SET *);
121 static void compute_out (sbitmap *bb_out, sbitmap *, sbitmap *, int);
122 static void link_btr_uses (btr_def *, btr_user *, sbitmap *, sbitmap *, int);
123 static void build_btr_def_use_webs (fibheap_t);
124 static int block_at_edge_of_live_range_p (int, btr_def);
125 static void clear_btr_from_live_range (btr_def def);
126 static void add_btr_to_live_range (btr_def);
127 static void augment_live_range (bitmap, HARD_REG_SET *, basic_block,
129 static int choose_btr (HARD_REG_SET);
130 static void combine_btr_defs (btr_def, HARD_REG_SET *);
131 static void btr_def_live_range (btr_def, HARD_REG_SET *);
132 static void move_btr_def (basic_block, int, btr_def, bitmap, HARD_REG_SET *);
133 static int migrate_btr_def (btr_def, int);
134 static void migrate_btr_defs (enum reg_class, int);
135 static int can_move_up (basic_block, rtx, int);
136 static void note_btr_set (rtx, rtx, void *);
138 /* The following code performs code motion of target load instructions
139 (instructions that set branch target registers), to move them
140 forward away from the branch instructions and out of loops (or,
141 more generally, from a more frequently executed place to a less
142 frequently executed place).
143 Moving target load instructions further in front of the branch
144 instruction that uses the target register value means that the hardware
145 has a better chance of preloading the instructions at the branch
146 target by the time the branch is reached. This avoids bubbles
147 when a taken branch needs to flush out the pipeline.
148 Moving target load instructions out of loops means they are executed
151 /* An obstack to hold the def-use web data structures built up for
152 migrating branch target load instructions. */
153 static struct obstack migrate_btrl_obstack;
155 /* Array indexed by basic block number, giving the set of registers
156 live in that block. */
157 static HARD_REG_SET *btrs_live;
159 /* Array indexed by basic block number, giving the set of registers live at
160 the end of that block, including any uses by a final jump insn, if any. */
161 static HARD_REG_SET *btrs_live_at_end;
163 /* Set of all target registers that we are willing to allocate. */
164 static HARD_REG_SET all_btrs;
166 /* Provide lower and upper bounds for target register numbers, so that
167 we don't need to search through all the hard registers all the time. */
168 static int first_btr, last_btr;
172 /* Return an estimate of the frequency of execution of block bb. */
174 basic_block_freq (basic_block bb)
176 return bb->frequency;
179 static rtx *btr_reference_found;
181 /* A subroutine of btr_referenced_p, called through for_each_rtx.
182 PREG is a pointer to an rtx that is to be excluded from the
183 traversal. If we find a reference to a target register anywhere
184 else, return 1, and put a pointer to it into btr_reference_found. */
186 find_btr_reference (rtx *px, void *preg)
197 for (i = hard_regno_nregs[regno][GET_MODE (x)] - 1; i >= 0; i--)
198 if (TEST_HARD_REG_BIT (all_btrs, regno+i))
200 btr_reference_found = px;
206 /* Return nonzero if X references (sets or reads) any branch target register.
207 If EXCLUDEP is set, disregard any references within the rtx pointed to
208 by it. If returning nonzero, also set btr_reference_found as above. */
210 btr_referenced_p (rtx x, rtx *excludep)
212 return for_each_rtx (&x, find_btr_reference, excludep);
215 /* Return true if insn is an instruction that sets a target register.
216 if CHECK_CONST is true, only return true if the source is constant.
217 If such a set is found and REGNO is nonzero, assign the register number
218 of the destination register to *REGNO. */
220 insn_sets_btr_p (rtx insn, int check_const, int *regno)
224 if (NONJUMP_INSN_P (insn)
225 && (set = single_set (insn)))
227 rtx dest = SET_DEST (set);
228 rtx src = SET_SRC (set);
230 if (GET_CODE (dest) == SUBREG)
231 dest = XEXP (dest, 0);
234 && TEST_HARD_REG_BIT (all_btrs, REGNO (dest)))
236 gcc_assert (!btr_referenced_p (src, NULL));
238 if (!check_const || CONSTANT_P (src))
241 *regno = REGNO (dest);
249 /* Find and return a use of a target register within an instruction INSN. */
251 find_btr_use (rtx insn)
253 return btr_referenced_p (insn, NULL) ? btr_reference_found : NULL;
256 /* Find the group that the target register definition DEF belongs
257 to in the list starting with *ALL_BTR_DEF_GROUPS. If no such
258 group exists, create one. Add def to the group. */
260 find_btr_def_group (btr_def_group *all_btr_def_groups, btr_def def)
262 if (insn_sets_btr_p (def->insn, 1, NULL))
264 btr_def_group this_group;
265 rtx def_src = SET_SRC (single_set (def->insn));
267 /* ?? This linear search is an efficiency concern, particularly
268 as the search will almost always fail to find a match. */
269 for (this_group = *all_btr_def_groups;
271 this_group = this_group->next)
272 if (rtx_equal_p (def_src, this_group->src))
277 this_group = obstack_alloc (&migrate_btrl_obstack,
278 sizeof (struct btr_def_group_s));
279 this_group->src = def_src;
280 this_group->members = NULL;
281 this_group->next = *all_btr_def_groups;
282 *all_btr_def_groups = this_group;
284 def->group = this_group;
285 def->next_this_group = this_group->members;
286 this_group->members = def;
292 /* Create a new target register definition structure, for a definition in
293 block BB, instruction INSN, and insert it into ALL_BTR_DEFS. Return
294 the new definition. */
296 add_btr_def (fibheap_t all_btr_defs, basic_block bb, int insn_luid, rtx insn,
297 unsigned int dest_reg, int other_btr_uses_before_def,
298 btr_def_group *all_btr_def_groups)
301 = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_def_s));
303 this->luid = insn_luid;
305 this->btr = dest_reg;
306 this->cost = basic_block_freq (bb);
307 this->has_ambiguous_use = 0;
308 this->other_btr_uses_before_def = other_btr_uses_before_def;
309 this->other_btr_uses_after_use = 0;
310 this->next_this_bb = NULL;
311 this->next_this_group = NULL;
313 this->live_range = NULL;
314 find_btr_def_group (all_btr_def_groups, this);
316 fibheap_insert (all_btr_defs, -this->cost, this);
320 "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n",
321 dest_reg, bb->index, INSN_UID (insn), (this->group ? "" : ":not const"),
327 /* Create a new target register user structure, for a use in block BB,
328 instruction INSN. Return the new user. */
330 new_btr_user (basic_block bb, int insn_luid, rtx insn)
332 /* This instruction reads target registers. We need
333 to decide whether we can replace all target register
336 rtx *usep = find_btr_use (PATTERN (insn));
338 btr_user user = NULL;
342 int unambiguous_single_use;
344 /* We want to ensure that USE is the only use of a target
345 register in INSN, so that we know that to rewrite INSN to use
346 a different target register, all we have to do is replace USE. */
347 unambiguous_single_use = !btr_referenced_p (PATTERN (insn), usep);
348 if (!unambiguous_single_use)
351 use = usep ? *usep : NULL_RTX;
352 user = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_user_s));
354 user->luid = insn_luid;
357 user->other_use_this_block = 0;
359 user->n_reaching_defs = 0;
360 user->first_reaching_def = -1;
364 fprintf (dump_file, "Uses target reg: { bb %d, insn %d }",
365 bb->index, INSN_UID (insn));
368 fprintf (dump_file, ": unambiguous use of reg %d\n",
375 /* Write the contents of S to the dump file. */
377 dump_hard_reg_set (HARD_REG_SET s)
380 for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
381 if (TEST_HARD_REG_BIT (s, reg))
382 fprintf (dump_file, " %d", reg);
385 /* Write the set of target regs live in block BB to the dump file. */
387 dump_btrs_live (int bb)
389 fprintf (dump_file, "BB%d live:", bb);
390 dump_hard_reg_set (btrs_live[bb]);
391 fprintf (dump_file, "\n");
394 /* REGNO is the number of a branch target register that is being used or
395 set. USERS_THIS_BB is a list of preceding branch target register users;
396 If any of them use the same register, set their other_use_this_block
399 note_other_use_this_block (unsigned int regno, btr_user users_this_bb)
403 for (user = users_this_bb; user != NULL; user = user->next)
404 if (user->use && REGNO (user->use) == regno)
405 user->other_use_this_block = 1;
409 btr_user users_this_bb;
410 HARD_REG_SET btrs_written_in_block;
411 HARD_REG_SET btrs_live_in_block;
416 /* Called via note_stores or directly to register stores into /
417 clobbers of a branch target register DEST that are not recognized as
418 straightforward definitions. DATA points to information about the
419 current basic block that needs updating. */
421 note_btr_set (rtx dest, rtx set ATTRIBUTE_UNUSED, void *data)
423 defs_uses_info *info = data;
424 int regno, end_regno;
428 regno = REGNO (dest);
429 end_regno = regno + hard_regno_nregs[regno][GET_MODE (dest)];
430 for (; regno < end_regno; regno++)
431 if (TEST_HARD_REG_BIT (all_btrs, regno))
433 note_other_use_this_block (regno, info->users_this_bb);
434 SET_HARD_REG_BIT (info->btrs_written_in_block, regno);
435 SET_HARD_REG_BIT (info->btrs_live_in_block, regno);
436 sbitmap_difference (info->bb_gen, info->bb_gen,
437 info->btr_defset[regno - first_btr]);
442 compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array,
443 btr_user *use_array, sbitmap *btr_defset,
444 sbitmap *bb_gen, HARD_REG_SET *btrs_written)
446 /* Scan the code building up the set of all defs and all uses.
447 For each target register, build the set of defs of that register.
448 For each block, calculate the set of target registers
449 written in that block.
450 Also calculate the set of btrs ever live in that block.
454 btr_def_group all_btr_def_groups = NULL;
457 sbitmap_vector_zero (bb_gen, n_basic_blocks);
458 for (i = 0; i < n_basic_blocks; i++)
460 basic_block bb = BASIC_BLOCK (i);
462 btr_def defs_this_bb = NULL;
467 info.users_this_bb = NULL;
468 info.bb_gen = bb_gen[i];
469 info.btr_defset = btr_defset;
471 CLEAR_HARD_REG_SET (info.btrs_live_in_block);
472 CLEAR_HARD_REG_SET (info.btrs_written_in_block);
473 for (reg = first_btr; reg <= last_btr; reg++)
474 if (TEST_HARD_REG_BIT (all_btrs, reg)
475 && REGNO_REG_SET_P (bb->global_live_at_start, reg))
476 SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
478 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
480 insn = NEXT_INSN (insn), insn_luid++)
485 int insn_uid = INSN_UID (insn);
487 if (insn_sets_btr_p (insn, 0, ®no))
489 btr_def def = add_btr_def (
490 all_btr_defs, bb, insn_luid, insn, regno,
491 TEST_HARD_REG_BIT (info.btrs_live_in_block, regno),
492 &all_btr_def_groups);
494 def_array[insn_uid] = def;
495 SET_HARD_REG_BIT (info.btrs_written_in_block, regno);
496 SET_HARD_REG_BIT (info.btrs_live_in_block, regno);
497 sbitmap_difference (bb_gen[i], bb_gen[i],
498 btr_defset[regno - first_btr]);
499 SET_BIT (bb_gen[i], insn_uid);
500 def->next_this_bb = defs_this_bb;
502 SET_BIT (btr_defset[regno - first_btr], insn_uid);
503 note_other_use_this_block (regno, info.users_this_bb);
507 if (btr_referenced_p (PATTERN (insn), NULL))
509 btr_user user = new_btr_user (bb, insn_luid, insn);
511 use_array[insn_uid] = user;
513 SET_HARD_REG_BIT (info.btrs_live_in_block,
518 for (reg = first_btr; reg <= last_btr; reg++)
519 if (TEST_HARD_REG_BIT (all_btrs, reg)
520 && refers_to_regno_p (reg, reg + 1, user->insn,
523 note_other_use_this_block (reg,
525 SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
527 note_stores (PATTERN (insn), note_btr_set, &info);
529 user->next = info.users_this_bb;
530 info.users_this_bb = user;
534 HARD_REG_SET *clobbered = &call_used_reg_set;
535 HARD_REG_SET call_saved;
536 rtx pat = PATTERN (insn);
539 /* Check for sibcall. */
540 if (GET_CODE (pat) == PARALLEL)
541 for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
542 if (GET_CODE (XVECEXP (pat, 0, i)) == RETURN)
544 COMPL_HARD_REG_SET (call_saved,
546 clobbered = &call_saved;
549 for (regno = first_btr; regno <= last_btr; regno++)
550 if (TEST_HARD_REG_BIT (*clobbered, regno))
551 note_btr_set (regno_reg_rtx[regno], NULL_RTX, &info);
557 COPY_HARD_REG_SET (btrs_live[i], info.btrs_live_in_block);
558 COPY_HARD_REG_SET (btrs_written[i], info.btrs_written_in_block);
560 REG_SET_TO_HARD_REG_SET (btrs_live_at_end[i], bb->global_live_at_end);
561 /* If this block ends in a jump insn, add any uses or even clobbers
562 of branch target registers that it might have. */
563 for (insn = BB_END (bb); insn != BB_HEAD (bb) && ! INSN_P (insn); )
564 insn = PREV_INSN (insn);
565 /* ??? for the fall-through edge, it would make sense to insert the
566 btr set on the edge, but that would require to split the block
567 early on so that we can distinguish between dominance from the fall
568 through edge - which can use the call-clobbered registers - from
569 dominance by the throw edge. */
570 if (can_throw_internal (insn))
574 COPY_HARD_REG_SET (tmp, call_used_reg_set);
575 AND_HARD_REG_SET (tmp, all_btrs);
576 IOR_HARD_REG_SET (btrs_live_at_end[i], tmp);
579 if (can_throw || JUMP_P (insn))
583 for (regno = first_btr; regno <= last_btr; regno++)
584 if (refers_to_regno_p (regno, regno+1, insn, NULL))
585 SET_HARD_REG_BIT (btrs_live_at_end[i], regno);
594 compute_kill (sbitmap *bb_kill, sbitmap *btr_defset,
595 HARD_REG_SET *btrs_written)
600 /* For each basic block, form the set BB_KILL - the set
601 of definitions that the block kills. */
602 sbitmap_vector_zero (bb_kill, n_basic_blocks);
603 for (i = 0; i < n_basic_blocks; i++)
605 for (regno = first_btr; regno <= last_btr; regno++)
606 if (TEST_HARD_REG_BIT (all_btrs, regno)
607 && TEST_HARD_REG_BIT (btrs_written[i], regno))
608 sbitmap_a_or_b (bb_kill[i], bb_kill[i],
609 btr_defset[regno - first_btr]);
614 compute_out (sbitmap *bb_out, sbitmap *bb_gen, sbitmap *bb_kill, int max_uid)
616 /* Perform iterative dataflow:
617 Initially, for all blocks, BB_OUT = BB_GEN.
619 BB_IN = union over predecessors of BB_OUT(pred)
620 BB_OUT = (BB_IN - BB_KILL) + BB_GEN
621 Iterate until the bb_out sets stop growing. */
624 sbitmap bb_in = sbitmap_alloc (max_uid);
626 for (i = 0; i < n_basic_blocks; i++)
627 sbitmap_copy (bb_out[i], bb_gen[i]);
633 for (i = 0; i < n_basic_blocks; i++)
635 sbitmap_union_of_preds (bb_in, bb_out, i);
636 changed |= sbitmap_union_of_diff_cg (bb_out[i], bb_gen[i],
640 sbitmap_free (bb_in);
644 link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out,
645 sbitmap *btr_defset, int max_uid)
648 sbitmap reaching_defs = sbitmap_alloc (max_uid);
650 /* Link uses to the uses lists of all of their reaching defs.
651 Count up the number of reaching defs of each use. */
652 for (i = 0; i < n_basic_blocks; i++)
654 basic_block bb = BASIC_BLOCK (i);
658 sbitmap_union_of_preds (reaching_defs, bb_out, i);
659 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
661 insn = NEXT_INSN (insn))
665 int insn_uid = INSN_UID (insn);
667 btr_def def = def_array[insn_uid];
668 btr_user user = use_array[insn_uid];
671 /* Remove all reaching defs of regno except
673 sbitmap_difference (reaching_defs, reaching_defs,
674 btr_defset[def->btr - first_btr]);
675 SET_BIT(reaching_defs, insn_uid);
680 /* Find all the reaching defs for this use. */
681 sbitmap reaching_defs_of_reg = sbitmap_alloc(max_uid);
686 reaching_defs_of_reg,
688 btr_defset[REGNO (user->use) - first_btr]);
693 sbitmap_zero (reaching_defs_of_reg);
694 for (reg = first_btr; reg <= last_btr; reg++)
695 if (TEST_HARD_REG_BIT (all_btrs, reg)
696 && refers_to_regno_p (reg, reg + 1, user->insn,
698 sbitmap_a_or_b_and_c (reaching_defs_of_reg,
699 reaching_defs_of_reg,
701 btr_defset[reg - first_btr]);
703 EXECUTE_IF_SET_IN_SBITMAP (reaching_defs_of_reg, 0, uid,
705 btr_def def = def_array[uid];
707 /* We now know that def reaches user. */
711 "Def in insn %d reaches use in insn %d\n",
714 user->n_reaching_defs++;
716 def->has_ambiguous_use = 1;
717 if (user->first_reaching_def != -1)
718 { /* There is more than one reaching def. This is
719 a rare case, so just give up on this def/use
720 web when it occurs. */
721 def->has_ambiguous_use = 1;
722 def_array[user->first_reaching_def]
723 ->has_ambiguous_use = 1;
726 "(use %d has multiple reaching defs)\n",
730 user->first_reaching_def = uid;
731 if (user->other_use_this_block)
732 def->other_btr_uses_after_use = 1;
733 user->next = def->uses;
736 sbitmap_free (reaching_defs_of_reg);
743 for (regno = first_btr; regno <= last_btr; regno++)
744 if (TEST_HARD_REG_BIT (all_btrs, regno)
745 && TEST_HARD_REG_BIT (call_used_reg_set, regno))
746 sbitmap_difference (reaching_defs, reaching_defs,
747 btr_defset[regno - first_btr]);
752 sbitmap_free (reaching_defs);
756 build_btr_def_use_webs (fibheap_t all_btr_defs)
758 const int max_uid = get_max_uid ();
759 btr_def *def_array = xcalloc (max_uid, sizeof (btr_def));
760 btr_user *use_array = xcalloc (max_uid, sizeof (btr_user));
761 sbitmap *btr_defset = sbitmap_vector_alloc (
762 (last_btr - first_btr) + 1, max_uid);
763 sbitmap *bb_gen = sbitmap_vector_alloc (n_basic_blocks, max_uid);
764 HARD_REG_SET *btrs_written = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET));
768 sbitmap_vector_zero (btr_defset, (last_btr - first_btr) + 1);
770 compute_defs_uses_and_gen (all_btr_defs, def_array, use_array, btr_defset,
771 bb_gen, btrs_written);
773 bb_kill = sbitmap_vector_alloc (n_basic_blocks, max_uid);
774 compute_kill (bb_kill, btr_defset, btrs_written);
777 bb_out = sbitmap_vector_alloc (n_basic_blocks, max_uid);
778 compute_out (bb_out, bb_gen, bb_kill, max_uid);
780 sbitmap_vector_free (bb_gen);
781 sbitmap_vector_free (bb_kill);
783 link_btr_uses (def_array, use_array, bb_out, btr_defset, max_uid);
785 sbitmap_vector_free (bb_out);
786 sbitmap_vector_free (btr_defset);
791 /* Return true if basic block BB contains the start or end of the
792 live range of the definition DEF, AND there are other live
793 ranges of the same target register that include BB. */
795 block_at_edge_of_live_range_p (int bb, btr_def def)
797 if (def->other_btr_uses_before_def && BASIC_BLOCK (bb) == def->bb)
799 else if (def->other_btr_uses_after_use)
802 for (user = def->uses; user != NULL; user = user->next)
803 if (BASIC_BLOCK (bb) == user->bb)
809 /* We are removing the def/use web DEF. The target register
810 used in this web is therefore no longer live in the live range
811 of this web, so remove it from the live set of all basic blocks
812 in the live range of the web.
813 Blocks at the boundary of the live range may contain other live
814 ranges for the same target register, so we have to be careful
815 to remove the target register from the live set of these blocks
816 only if they do not contain other live ranges for the same register. */
818 clear_btr_from_live_range (btr_def def)
823 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
825 if ((!def->other_btr_uses_before_def
826 && !def->other_btr_uses_after_use)
827 || !block_at_edge_of_live_range_p (bb, def))
829 CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr);
830 CLEAR_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
838 /* We are adding the def/use web DEF. Add the target register used
839 in this web to the live set of all of the basic blocks that contain
840 the live range of the web. */
842 add_btr_to_live_range (btr_def def)
847 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
849 SET_HARD_REG_BIT (btrs_live[bb], def->btr);
850 SET_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
856 /* Update a live range to contain the basic block NEW_BLOCK, and all
857 blocks on paths between the existing live range and NEW_BLOCK.
858 HEAD is a block contained in the existing live range that dominates
859 all other blocks in the existing live range.
860 Also add to the set BTRS_LIVE_IN_RANGE all target registers that
861 are live in the blocks that we add to the live range.
862 It is a precondition that either NEW_BLOCK dominates HEAD,or
863 HEAD dom NEW_BLOCK. This is used to speed up the
864 implementation of this function. */
866 augment_live_range (bitmap live_range, HARD_REG_SET *btrs_live_in_range,
867 basic_block head_bb, basic_block new_bb)
869 basic_block *worklist, *tos;
871 tos = worklist = xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
873 if (dominated_by_p (CDI_DOMINATORS, new_bb, head_bb))
879 int new_block = new_bb->index;
881 gcc_assert (dominated_by_p (CDI_DOMINATORS, head_bb, new_bb));
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]);
894 "Adding end of block %d and rest of %d to live range\n",
895 new_block, head_bb->index);
896 fprintf (dump_file,"Now live btrs are ");
897 dump_hard_reg_set (*btrs_live_in_range);
898 fprintf (dump_file, "\n");
900 FOR_EACH_EDGE (e, ei, head_bb->preds)
904 while (tos != worklist)
906 basic_block bb = *--tos;
907 if (!bitmap_bit_p (live_range, bb->index))
912 bitmap_set_bit (live_range, bb->index);
913 IOR_HARD_REG_SET (*btrs_live_in_range,
914 btrs_live[bb->index]);
918 "Adding block %d to live range\n", bb->index);
919 fprintf (dump_file,"Now live btrs are ");
920 dump_hard_reg_set (*btrs_live_in_range);
921 fprintf (dump_file, "\n");
924 FOR_EACH_EDGE (e, ei, bb->preds)
926 basic_block pred = e->src;
927 if (!bitmap_bit_p (live_range, pred->index))
936 /* Return the most desirable target register that is not in
937 the set USED_BTRS. */
939 choose_btr (HARD_REG_SET used_btrs)
942 GO_IF_HARD_REG_SUBSET (all_btrs, used_btrs, give_up);
944 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
946 #ifdef REG_ALLOC_ORDER
947 int regno = reg_alloc_order[i];
951 if (TEST_HARD_REG_BIT (all_btrs, regno)
952 && !TEST_HARD_REG_BIT (used_btrs, regno))
959 /* Calculate the set of basic blocks that contain the live range of
961 Also calculate the set of target registers that are live at time
962 in this live range, but ignore the live range represented by DEF
963 when calculating this set. */
965 btr_def_live_range (btr_def def, HARD_REG_SET *btrs_live_in_range)
967 if (!def->live_range)
971 def->live_range = BITMAP_XMALLOC ();
973 bitmap_set_bit (def->live_range, def->bb->index);
974 COPY_HARD_REG_SET (*btrs_live_in_range,
975 (flag_btr_bb_exclusive
976 ? btrs_live : btrs_live_at_end)[def->bb->index]);
978 for (user = def->uses; user != NULL; user = user->next)
979 augment_live_range (def->live_range, btrs_live_in_range,
984 /* def->live_range is accurate, but we need to recompute
985 the set of target registers live over it, because migration
986 of other PT instructions may have affected it.
989 unsigned def_bb = flag_btr_bb_exclusive ? -1 : def->bb->index;
992 CLEAR_HARD_REG_SET (*btrs_live_in_range);
993 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
995 IOR_HARD_REG_SET (*btrs_live_in_range,
997 ? btrs_live_at_end : btrs_live) [bb]);
1000 if (!def->other_btr_uses_before_def &&
1001 !def->other_btr_uses_after_use)
1002 CLEAR_HARD_REG_BIT (*btrs_live_in_range, def->btr);
1005 /* Merge into the def/use web DEF any other def/use webs in the same
1006 group that are dominated by DEF, provided that there is a target
1007 register available to allocate to the merged web. */
1009 combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range)
1013 for (other_def = def->group->members;
1015 other_def = other_def->next_this_group)
1017 if (other_def != def
1018 && other_def->uses != NULL
1019 && ! other_def->has_ambiguous_use
1020 && dominated_by_p (CDI_DOMINATORS, other_def->bb, def->bb))
1022 /* def->bb dominates the other def, so def and other_def could
1024 /* Merge their live ranges, and get the set of
1025 target registers live over the merged range. */
1027 HARD_REG_SET combined_btrs_live;
1028 bitmap combined_live_range = BITMAP_XMALLOC ();
1031 if (other_def->live_range == NULL)
1033 HARD_REG_SET dummy_btrs_live_in_range;
1034 btr_def_live_range (other_def, &dummy_btrs_live_in_range);
1036 COPY_HARD_REG_SET (combined_btrs_live, *btrs_live_in_range);
1037 bitmap_copy (combined_live_range, def->live_range);
1039 for (user = other_def->uses; user != NULL; user = user->next)
1040 augment_live_range (combined_live_range, &combined_btrs_live,
1043 btr = choose_btr (combined_btrs_live);
1046 /* We can combine them. */
1049 "Combining def in insn %d with def in insn %d\n",
1050 INSN_UID (other_def->insn), INSN_UID (def->insn));
1053 user = other_def->uses;
1054 while (user != NULL)
1056 btr_user next = user->next;
1058 user->next = def->uses;
1062 /* Combining def/use webs can make target registers live
1063 after uses where they previously were not. This means
1064 some REG_DEAD notes may no longer be correct. We could
1065 be more precise about this if we looked at the combined
1066 live range, but here I just delete any REG_DEAD notes
1067 in case they are no longer correct. */
1068 for (user = def->uses; user != NULL; user = user->next)
1069 remove_note (user->insn,
1070 find_regno_note (user->insn, REG_DEAD,
1071 REGNO (user->use)));
1072 clear_btr_from_live_range (other_def);
1073 other_def->uses = NULL;
1074 bitmap_copy (def->live_range, combined_live_range);
1075 if (other_def->other_btr_uses_after_use)
1076 def->other_btr_uses_after_use = 1;
1077 COPY_HARD_REG_SET (*btrs_live_in_range, combined_btrs_live);
1079 /* Delete the old target register initialization. */
1080 delete_insn (other_def->insn);
1083 BITMAP_XFREE (combined_live_range);
1088 /* Move the definition DEF from its current position to basic
1089 block NEW_DEF_BB, and modify it to use branch target register BTR.
1090 Delete the old defining insn, and insert a new one in NEW_DEF_BB.
1091 Update all reaching uses of DEF in the RTL to use BTR.
1092 If this new position means that other defs in the
1093 same group can be combined with DEF then combine them. */
1095 move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range,
1096 HARD_REG_SET *btrs_live_in_range)
1098 /* We can move the instruction.
1099 Set a target register in block NEW_DEF_BB to the value
1100 needed for this target register definition.
1101 Replace all uses of the old target register definition by
1102 uses of the new definition. Delete the old definition. */
1103 basic_block b = new_def_bb;
1104 rtx insp = BB_HEAD (b);
1105 rtx old_insn = def->insn;
1109 enum machine_mode btr_mode;
1114 fprintf(dump_file, "migrating to basic block %d, using reg %d\n",
1115 new_def_bb->index, btr);
1117 clear_btr_from_live_range (def);
1119 def->bb = new_def_bb;
1121 def->cost = basic_block_freq (new_def_bb);
1122 def->other_btr_uses_before_def
1123 = TEST_HARD_REG_BIT (btrs_live[b->index], btr) ? 1 : 0;
1124 bitmap_copy (def->live_range, live_range);
1125 combine_btr_defs (def, btrs_live_in_range);
1127 add_btr_to_live_range (def);
1129 insp = NEXT_INSN (insp);
1130 /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some
1131 optimizations can result in insp being both first and last insn of
1133 /* ?? some assertions to check that insp is sensible? */
1135 if (def->other_btr_uses_before_def)
1138 for (insp = BB_END (b); ! INSN_P (insp); insp = PREV_INSN (insp))
1139 gcc_assert (insp != BB_HEAD (b));
1141 if (JUMP_P (insp) || can_throw_internal (insp))
1142 insp = PREV_INSN (insp);
1145 set = single_set (old_insn);
1146 src = SET_SRC (set);
1147 btr_mode = GET_MODE (SET_DEST (set));
1148 btr_rtx = gen_rtx_REG (btr_mode, btr);
1150 new_insn = gen_move_insn (btr_rtx, src);
1152 /* Insert target register initialization at head of basic block. */
1153 def->insn = emit_insn_after (new_insn, insp);
1155 regs_ever_live[btr] = 1;
1158 fprintf (dump_file, "New pt is insn %d, inserted after insn %d\n",
1159 INSN_UID (def->insn), INSN_UID (insp));
1161 /* Delete the old target register initialization. */
1162 delete_insn (old_insn);
1164 /* Replace each use of the old target register by a use of the new target
1166 for (user = def->uses; user != NULL; user = user->next)
1168 /* Some extra work here to ensure consistent modes, because
1169 it seems that a target register REG rtx can be given a different
1170 mode depending on the context (surely that should not be
1172 rtx replacement_rtx;
1173 if (GET_MODE (user->use) == GET_MODE (btr_rtx)
1174 || GET_MODE (user->use) == VOIDmode)
1175 replacement_rtx = btr_rtx;
1177 replacement_rtx = gen_rtx_REG (GET_MODE (user->use), btr);
1178 replace_rtx (user->insn, user->use, replacement_rtx);
1179 user->use = replacement_rtx;
1183 /* We anticipate intra-block scheduling to be done. See if INSN could move
1184 up within BB by N_INSNS. */
1186 can_move_up (basic_block bb, rtx insn, int n_insns)
1188 while (insn != BB_HEAD (bb) && n_insns > 0)
1190 insn = PREV_INSN (insn);
1191 /* ??? What if we have an anti-dependency that actually prevents the
1192 scheduler from doing the move? We'd like to re-allocate the register,
1193 but not necessarily put the load into another basic block. */
1197 return n_insns <= 0;
1200 /* Attempt to migrate the target register definition DEF to an
1201 earlier point in the flowgraph.
1203 It is a precondition of this function that DEF is migratable:
1204 i.e. it has a constant source, and all uses are unambiguous.
1206 Only migrations that reduce the cost of DEF will be made.
1207 MIN_COST is the lower bound on the cost of the DEF after migration.
1208 If we migrate DEF so that its cost falls below MIN_COST,
1209 then we do not attempt to migrate further. The idea is that
1210 we migrate definitions in a priority order based on their cost,
1211 when the cost of this definition falls below MIN_COST, then
1212 there is another definition with cost == MIN_COST which now
1213 has a higher priority than this definition.
1215 Return nonzero if there may be benefit from attempting to
1216 migrate this DEF further (i.e. we have reduced the cost below
1217 MIN_COST, but we may be able to reduce it further).
1218 Return zero if no further migration is possible. */
1220 migrate_btr_def (btr_def def, int min_cost)
1223 HARD_REG_SET btrs_live_in_range;
1224 int btr_used_near_def = 0;
1225 int def_basic_block_freq;
1234 "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ",
1235 INSN_UID (def->insn), def->cost, min_cost);
1237 if (!def->group || def->has_ambiguous_use)
1238 /* These defs are not migratable. */
1241 fprintf (dump_file, "it's not migratable\n");
1246 /* We have combined this def with another in the same group, so
1247 no need to consider it further.
1251 fprintf (dump_file, "it's already combined with another pt\n");
1255 btr_def_live_range (def, &btrs_live_in_range);
1256 live_range = BITMAP_XMALLOC ();
1257 bitmap_copy (live_range, def->live_range);
1259 #ifdef INSN_SCHEDULING
1260 def_latency = insn_default_latency (def->insn) * issue_rate;
1262 def_latency = issue_rate;
1265 for (user = def->uses; user != NULL; user = user->next)
1267 if (user->bb == def->bb
1268 && user->luid > def->luid
1269 && (def->luid + def_latency) > user->luid
1270 && ! can_move_up (def->bb, def->insn,
1271 (def->luid + def_latency) - user->luid))
1273 btr_used_near_def = 1;
1278 def_basic_block_freq = basic_block_freq (def->bb);
1280 for (try = get_immediate_dominator (CDI_DOMINATORS, def->bb);
1281 !give_up && try && try != ENTRY_BLOCK_PTR && def->cost >= min_cost;
1282 try = get_immediate_dominator (CDI_DOMINATORS, try))
1284 /* Try to move the instruction that sets the target register into
1286 int try_freq = basic_block_freq (try);
1289 fprintf (dump_file, "trying block %d ...", try->index);
1291 if (try_freq < def_basic_block_freq
1292 || (try_freq == def_basic_block_freq && btr_used_near_def))
1295 augment_live_range (live_range, &btrs_live_in_range, def->bb, try);
1298 fprintf (dump_file, "Now btrs live in range are: ");
1299 dump_hard_reg_set (btrs_live_in_range);
1300 fprintf (dump_file, "\n");
1302 btr = choose_btr (btrs_live_in_range);
1305 move_btr_def (try, btr, def, live_range, &btrs_live_in_range);
1306 bitmap_copy(live_range, def->live_range);
1307 btr_used_near_def = 0;
1309 def_basic_block_freq = basic_block_freq (def->bb);
1313 /* There are no free target registers available to move
1314 this far forward, so give up */
1318 "giving up because there are no free target registers\n");
1327 fprintf (dump_file, "failed to move\n");
1329 BITMAP_XFREE (live_range);
1333 /* Attempt to move instructions that set target registers earlier
1334 in the flowgraph, away from their corresponding uses. */
1336 migrate_btr_defs (enum reg_class btr_class, int allow_callee_save)
1338 fibheap_t all_btr_defs = fibheap_new ();
1341 gcc_obstack_init (&migrate_btrl_obstack);
1346 for (i = 0; i < n_basic_blocks; i++)
1348 basic_block bb = BASIC_BLOCK (i);
1350 "Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC
1351 " loop-depth = %d idom = %d\n",
1352 i, (HOST_WIDEST_INT) bb->count, bb->loop_depth,
1353 get_immediate_dominator (CDI_DOMINATORS, bb)->index);
1357 CLEAR_HARD_REG_SET (all_btrs);
1358 for (first_btr = -1, reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
1359 if (TEST_HARD_REG_BIT (reg_class_contents[(int) btr_class], reg)
1360 && (allow_callee_save || call_used_regs[reg] || regs_ever_live[reg]))
1362 SET_HARD_REG_BIT (all_btrs, reg);
1368 btrs_live = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET));
1369 btrs_live_at_end = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET));
1371 build_btr_def_use_webs (all_btr_defs);
1373 while (!fibheap_empty (all_btr_defs))
1375 btr_def def = fibheap_extract_min (all_btr_defs);
1376 int min_cost = -fibheap_min_key (all_btr_defs);
1377 if (migrate_btr_def (def, min_cost))
1379 fibheap_insert (all_btr_defs, -def->cost, (void *) def);
1383 "Putting insn %d back on queue with priority %d\n",
1384 INSN_UID (def->insn), def->cost);
1388 BITMAP_XFREE (def->live_range);
1392 free (btrs_live_at_end);
1393 obstack_free (&migrate_btrl_obstack, NULL);
1394 fibheap_delete (all_btr_defs);
1398 branch_target_load_optimize (bool after_prologue_epilogue_gen)
1400 enum reg_class class = targetm.branch_target_register_class ();
1401 if (class != NO_REGS)
1403 /* Initialize issue_rate. */
1404 if (targetm.sched.issue_rate)
1405 issue_rate = targetm.sched.issue_rate ();
1409 /* Build the CFG for migrate_btr_defs. */
1411 /* This may or may not be needed, depending on where we
1413 cleanup_cfg (optimize ? CLEANUP_EXPENSIVE : 0);
1416 life_analysis (NULL, 0);
1418 /* Dominator info is also needed for migrate_btr_def. */
1419 calculate_dominance_info (CDI_DOMINATORS);
1420 migrate_btr_defs (class,
1421 (targetm.branch_target_register_callee_saved
1422 (after_prologue_epilogue_gen)));
1424 free_dominance_info (CDI_DOMINATORS);
1426 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
1427 PROP_DEATH_NOTES | PROP_REG_INFO);