1 /* Perform branch target register load optimizations.
2 Copyright (C) 2001, 2002, 2003 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"
40 /* Target register optimizations - these are performed after reload. */
42 typedef struct btr_def_group_s
44 struct btr_def_group_s *next;
46 struct btr_def_s *members;
49 typedef struct btr_user_s
51 struct btr_user_s *next;
55 /* If INSN has a single use of a single branch register, then
56 USE points to it within INSN. If there is more than
57 one branch register use, or the use is in some way ambiguous,
61 int first_reaching_def;
62 char other_use_this_block;
65 /* btr_def structs appear on three lists:
66 1. A list of all btr_def structures (head is
67 ALL_BTR_DEFS, linked by the NEXT field).
68 2. A list of branch reg definitions per basic block (head is
69 BB_BTR_DEFS[i], linked by the NEXT_THIS_BB field).
70 3. A list of all branch reg definitions belonging to the same
71 group (head is in a BTR_DEF_GROUP struct, linked by
72 NEXT_THIS_GROUP field). */
74 typedef struct btr_def_s
76 struct btr_def_s *next_this_bb;
77 struct btr_def_s *next_this_group;
83 /* For a branch register setting insn that has a constant
84 source (i.e. a label), group links together all the
85 insns with the same source. For other branch register
86 setting insns, group is NULL. */
89 /* If this def has a reaching use which is not a simple use
90 in a branch instruction, then has_ambiguous_use will be true,
91 and we will not attempt to migrate this definition. */
92 char has_ambiguous_use;
93 /* live_range is an approximation to the true live range for this
94 def/use web, because it records the set of blocks that contain
95 the live range. There could be other live ranges for the same
96 branch register in that set of blocks, either in the block
97 containing the def (before the def), or in a block containing
98 a use (after the use). If there are such other live ranges, then
99 other_btr_uses_before_def or other_btr_uses_after_use must be set true
101 char other_btr_uses_before_def;
102 char other_btr_uses_after_use;
106 static int issue_rate;
108 static int basic_block_freq (basic_block);
109 static int insn_sets_btr_p (rtx, int, int *);
110 static rtx *find_btr_use (rtx);
111 static int btr_referenced_p (rtx, rtx *);
112 static int find_btr_reference (rtx *, void *);
113 static void find_btr_def_group (btr_def_group *, btr_def);
114 static btr_def add_btr_def (fibheap_t, basic_block, int, rtx,
115 unsigned int, int, btr_def_group *);
116 static btr_user new_btr_user (basic_block, int, rtx);
117 static void dump_hard_reg_set (HARD_REG_SET);
118 static void dump_btrs_live (int);
119 static void note_other_use_this_block (unsigned int, btr_user);
120 static void compute_defs_uses_and_gen (fibheap_t, btr_def *,btr_user *,
121 sbitmap *, sbitmap *, HARD_REG_SET *);
122 static void compute_kill (sbitmap *, sbitmap *, HARD_REG_SET *);
123 static void compute_out (sbitmap *bb_out, sbitmap *, sbitmap *, int);
124 static void link_btr_uses (btr_def *, btr_user *, sbitmap *, sbitmap *, int);
125 static void build_btr_def_use_webs (fibheap_t);
126 static int block_at_edge_of_live_range_p (int, btr_def);
127 static void clear_btr_from_live_range (btr_def def);
128 static void add_btr_to_live_range (btr_def);
129 static void augment_live_range (bitmap, HARD_REG_SET *, basic_block,
131 static int choose_btr (HARD_REG_SET);
132 static void combine_btr_defs (btr_def, HARD_REG_SET *);
133 static void btr_def_live_range (btr_def, HARD_REG_SET *);
134 static void move_btr_def (basic_block, int, btr_def, bitmap, HARD_REG_SET *);
135 static int migrate_btr_def (btr_def, int);
136 static void migrate_btr_defs (enum reg_class, int);
137 static int can_move_up (basic_block, rtx, int);
138 static void note_btr_set (rtx, rtx, void *);
140 /* The following code performs code motion of target load instructions
141 (instructions that set branch target registers), to move them
142 forward away from the branch instructions and out of loops (or,
143 more generally, from a more frequently executed place to a less
144 frequently executed place).
145 Moving target load instructions further in front of the branch
146 instruction that uses the target register value means that the hardware
147 has a better chance of preloading the instructions at the branch
148 target by the time the branch is reached. This avoids bubbles
149 when a taken branch needs to flush out the pipeline.
150 Moving target load instructions out of loops means they are executed
153 /* An obstack to hold the def-use web data structures built up for
154 migrating branch target load instructions. */
155 static struct obstack migrate_btrl_obstack;
157 /* Basic block dominator information used when migrating PT instructions */
158 static dominance_info dom;
160 /* Array indexed by basic block number, giving the set of registers
161 live in that block. */
162 static HARD_REG_SET *btrs_live;
164 /* Set of all target registers that we are willing to allocate. */
165 static HARD_REG_SET all_btrs;
167 /* Provide lower and upper bounds for target register numbers, so that
168 we don't need to search through all the hard registers all the time. */
169 static int first_btr, last_btr;
173 /* Return an estimate of the frequency of execution of block bb.
174 If we have a profiling count available, we could use it here. */
176 basic_block_freq (basic_block bb)
178 return bb->frequency;
181 static rtx *btr_reference_found;
183 /* A subroutine of btr_referenced_p, called through for_each_rtx.
184 PREG is a pointer to an rtx that is to be excluded from the
185 traversal. If we find a reference to a target register anywhere
186 else, return 1, and put a pointer to it into btr_reference_found. */
188 find_btr_reference (rtx *px, void *preg)
196 if (GET_CODE (x) != REG)
199 for (i = HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1; i >= 0; i--)
200 if (TEST_HARD_REG_BIT (all_btrs, regno+i))
202 btr_reference_found = px;
208 /* Return nonzero if X references (sets or reads) any branch target register.
209 If EXCLUDEP is set, disregard any references within the rtx pointed to
210 by it. If returning nonzero, also set btr_reference_found as above. */
212 btr_referenced_p (rtx x, rtx *excludep)
214 return for_each_rtx (&x, find_btr_reference, excludep);
217 /* Return true if insn is an instruction that sets a target register.
218 if CHECK_CONST is true, only return true if the source is constant.
219 If such a set is found and REGNO is nonzero, assign the register number
220 of the destination register to *REGNO. */
222 insn_sets_btr_p (rtx insn, int check_const, int *regno)
226 if (GET_CODE (insn) == INSN
227 && (set = single_set (insn)))
229 rtx dest = SET_DEST (set);
230 rtx src = SET_SRC (set);
232 if (GET_CODE (dest) == SUBREG)
233 dest = XEXP (dest, 0);
235 if (GET_CODE (dest) == REG
236 && TEST_HARD_REG_BIT (all_btrs, REGNO (dest)))
238 if (btr_referenced_p (src, NULL))
240 if (!check_const || CONSTANT_P (src))
243 *regno = REGNO (dest);
251 /* Find and return a use of a target register within an instruction INSN. */
253 find_btr_use (rtx insn)
255 return btr_referenced_p (insn, NULL) ? btr_reference_found : NULL;
258 /* Find the group that the target register definition DEF belongs
259 to in the list starting with *ALL_BTR_DEF_GROUPS. If no such
260 group exists, create one. Add def to the group. */
262 find_btr_def_group (btr_def_group *all_btr_def_groups, btr_def def)
264 if (insn_sets_btr_p (def->insn, 1, NULL))
266 btr_def_group this_group;
267 rtx def_src = SET_SRC (single_set (def->insn));
269 /* ?? This linear search is an efficiency concern, particularly
270 as the search will almost always fail to find a match. */
271 for (this_group = *all_btr_def_groups;
273 this_group = this_group->next)
274 if (rtx_equal_p (def_src, this_group->src))
279 this_group = (btr_def_group)
280 obstack_alloc (&migrate_btrl_obstack,
281 sizeof (struct btr_def_group_s));
282 this_group->src = def_src;
283 this_group->members = NULL;
284 this_group->next = *all_btr_def_groups;
285 *all_btr_def_groups = this_group;
287 def->group = this_group;
288 def->next_this_group = this_group->members;
289 this_group->members = def;
295 /* Create a new target register definition structure, for a definition in
296 block BB, instruction INSN, and insert it into ALL_BTR_DEFS. Return
297 the new definition. */
299 add_btr_def (fibheap_t all_btr_defs, basic_block bb, int insn_luid, rtx insn,
300 unsigned int dest_reg, int other_btr_uses_before_def,
301 btr_def_group *all_btr_def_groups)
303 btr_def this = (btr_def)
304 obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_def_s));
306 this->luid = insn_luid;
308 this->btr = dest_reg;
309 this->cost = basic_block_freq (bb);
310 this->has_ambiguous_use = 0;
311 this->other_btr_uses_before_def = other_btr_uses_before_def;
312 this->other_btr_uses_after_use = 0;
313 this->next_this_bb = NULL;
314 this->next_this_group = NULL;
316 this->live_range = NULL;
317 find_btr_def_group (all_btr_def_groups, this);
319 fibheap_insert (all_btr_defs, -this->cost, this);
322 fprintf (rtl_dump_file,
323 "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n",
324 dest_reg, bb->index, INSN_UID (insn), (this->group ? "" : ":not const"),
330 /* Create a new target register user structure, for a use in block BB,
331 instruction INSN. Return the new user. */
333 new_btr_user (basic_block bb, int insn_luid, rtx insn)
335 /* This instruction reads target registers. We need
336 to decide whether we can replace all target register
339 rtx *usep = find_btr_use (PATTERN (insn));
341 btr_user user = NULL;
345 int unambiguous_single_use;
347 /* We want to ensure that USE is the only use of a target
348 register in INSN, so that we know that to rewrite INSN to use
349 a different target register, all we have to do is replace USE. */
350 unambiguous_single_use = !btr_referenced_p (PATTERN (insn), usep);
351 if (!unambiguous_single_use)
354 use = usep ? *usep : NULL_RTX;
356 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;
470 info.users_this_bb = NULL;
471 info.bb_gen = bb_gen[i];
472 info.btr_defset = btr_defset;
474 CLEAR_HARD_REG_SET (info.btrs_live_in_block);
475 CLEAR_HARD_REG_SET (info.btrs_written_in_block);
476 for (reg = first_btr; reg <= last_btr; reg++)
477 if (TEST_HARD_REG_BIT (all_btrs, reg)
478 && REGNO_REG_SET_P (bb->global_live_at_start, reg))
479 SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
481 for (insn = bb->head, last = NEXT_INSN (bb->end);
483 insn = NEXT_INSN (insn), insn_luid++)
488 int insn_uid = INSN_UID (insn);
490 if (insn_sets_btr_p (insn, 0, ®no))
492 btr_def def = add_btr_def (
493 all_btr_defs, bb, insn_luid, insn, regno,
494 TEST_HARD_REG_BIT (info.btrs_live_in_block, regno),
495 &all_btr_def_groups);
497 def_array[insn_uid] = def;
498 SET_HARD_REG_BIT (info.btrs_written_in_block, regno);
499 SET_HARD_REG_BIT (info.btrs_live_in_block, regno);
500 sbitmap_difference (bb_gen[i], bb_gen[i],
501 btr_defset[regno - first_btr]);
502 SET_BIT (bb_gen[i], insn_uid);
503 def->next_this_bb = defs_this_bb;
505 SET_BIT (btr_defset[regno - first_btr], insn_uid);
506 note_other_use_this_block (regno, info.users_this_bb);
510 if (btr_referenced_p (PATTERN (insn), NULL))
512 btr_user user = new_btr_user (bb, insn_luid, insn);
514 use_array[insn_uid] = user;
516 SET_HARD_REG_BIT (info.btrs_live_in_block,
521 for (reg = first_btr; reg <= last_btr; reg++)
522 if (TEST_HARD_REG_BIT (all_btrs, reg)
523 && refers_to_regno_p (reg, reg + 1, user->insn,
526 note_other_use_this_block (reg,
528 SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
530 note_stores (PATTERN (insn), note_btr_set, &info);
532 user->next = info.users_this_bb;
533 info.users_this_bb = user;
535 if (GET_CODE (insn) == CALL_INSN)
537 HARD_REG_SET *clobbered = &call_used_reg_set;
538 HARD_REG_SET call_saved;
539 rtx pat = PATTERN (insn);
542 /* Check for sibcall. */
543 if (GET_CODE (pat) == PARALLEL)
544 for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
545 if (GET_CODE (XVECEXP (pat, 0, i)) == RETURN)
547 COMPL_HARD_REG_SET (call_saved,
549 clobbered = &call_saved;
552 for (regno = first_btr; regno <= last_btr; regno++)
553 if (TEST_HARD_REG_BIT (*clobbered, regno))
554 note_btr_set (regno_reg_rtx[regno], NULL_RTX, &info);
560 COPY_HARD_REG_SET (btrs_live[i], info.btrs_live_in_block);
561 COPY_HARD_REG_SET (btrs_written[i], info.btrs_written_in_block);
568 compute_kill (sbitmap *bb_kill, sbitmap *btr_defset,
569 HARD_REG_SET *btrs_written)
574 /* For each basic block, form the set BB_KILL - the set
575 of definitions that the block kills. */
576 sbitmap_vector_zero (bb_kill, n_basic_blocks);
577 for (i = 0; i < n_basic_blocks; i++)
579 for (regno = first_btr; regno <= last_btr; regno++)
580 if (TEST_HARD_REG_BIT (all_btrs, regno)
581 && TEST_HARD_REG_BIT (btrs_written[i], regno))
582 sbitmap_a_or_b (bb_kill[i], bb_kill[i],
583 btr_defset[regno - first_btr]);
588 compute_out (sbitmap *bb_out, sbitmap *bb_gen, sbitmap *bb_kill, int max_uid)
590 /* Perform iterative dataflow:
591 Initially, for all blocks, BB_OUT = BB_GEN.
593 BB_IN = union over predecessors of BB_OUT(pred)
594 BB_OUT = (BB_IN - BB_KILL) + BB_GEN
595 Iterate until the bb_out sets stop growing. */
598 sbitmap bb_in = sbitmap_alloc (max_uid);
600 for (i = 0; i < n_basic_blocks; i++)
601 sbitmap_copy (bb_out[i], bb_gen[i]);
607 for (i = 0; i < n_basic_blocks; i++)
609 sbitmap_union_of_preds (bb_in, bb_out, i);
610 changed |= sbitmap_union_of_diff_cg (bb_out[i], bb_gen[i],
614 sbitmap_free (bb_in);
618 link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out,
619 sbitmap *btr_defset, int max_uid)
622 sbitmap reaching_defs = sbitmap_alloc (max_uid);
624 /* Link uses to the uses lists of all of their reaching defs.
625 Count up the number of reaching defs of each use. */
626 for (i = 0; i < n_basic_blocks; i++)
628 basic_block bb = BASIC_BLOCK (i);
632 sbitmap_union_of_preds (reaching_defs, bb_out, i);
633 for (insn = bb->head, last = NEXT_INSN (bb->end);
635 insn = NEXT_INSN (insn))
639 int insn_uid = INSN_UID (insn);
641 btr_def def = def_array[insn_uid];
642 btr_user user = use_array[insn_uid];
645 /* Remove all reaching defs of regno except
647 sbitmap_difference (reaching_defs, reaching_defs,
648 btr_defset[def->btr - first_btr]);
649 SET_BIT(reaching_defs, insn_uid);
654 /* Find all the reaching defs for this use */
655 sbitmap reaching_defs_of_reg = sbitmap_alloc(max_uid);
660 reaching_defs_of_reg,
662 btr_defset[REGNO (user->use) - first_btr]);
667 sbitmap_zero (reaching_defs_of_reg);
668 for (reg = first_btr; reg <= last_btr; reg++)
669 if (TEST_HARD_REG_BIT (all_btrs, reg)
670 && refers_to_regno_p (reg, reg + 1, user->insn,
672 sbitmap_a_or_b_and_c (reaching_defs_of_reg,
673 reaching_defs_of_reg,
675 btr_defset[reg - first_btr]);
677 EXECUTE_IF_SET_IN_SBITMAP (reaching_defs_of_reg, 0, uid,
679 btr_def def = def_array[uid];
681 /* We now know that def reaches user */
684 fprintf (rtl_dump_file,
685 "Def in insn %d reaches use in insn %d\n",
688 user->n_reaching_defs++;
690 def->has_ambiguous_use = 1;
691 if (user->first_reaching_def != -1)
692 { /* There is more than one reaching def. This is
693 a rare case, so just give up on this def/use
694 web when it occurs. */
695 def->has_ambiguous_use = 1;
696 def_array[user->first_reaching_def]
697 ->has_ambiguous_use = 1;
699 fprintf (rtl_dump_file,
700 "(use %d has multiple reaching defs)\n",
704 user->first_reaching_def = uid;
705 if (user->other_use_this_block)
706 def->other_btr_uses_after_use = 1;
707 user->next = def->uses;
710 sbitmap_free (reaching_defs_of_reg);
713 if (GET_CODE (insn) == CALL_INSN)
717 for (regno = first_btr; regno <= last_btr; regno++)
718 if (TEST_HARD_REG_BIT (all_btrs, regno)
719 && TEST_HARD_REG_BIT (call_used_reg_set, regno))
720 sbitmap_difference (reaching_defs, reaching_defs,
721 btr_defset[regno - first_btr]);
726 sbitmap_free (reaching_defs);
730 build_btr_def_use_webs (fibheap_t all_btr_defs)
732 const int max_uid = get_max_uid ();
733 btr_def *def_array = xcalloc (max_uid, sizeof (btr_def));
734 btr_user *use_array = xcalloc (max_uid, sizeof (btr_user));
735 sbitmap *btr_defset = sbitmap_vector_alloc (
736 (last_btr - first_btr) + 1, max_uid);
737 sbitmap *bb_gen = sbitmap_vector_alloc (n_basic_blocks, max_uid);
738 HARD_REG_SET *btrs_written = (HARD_REG_SET *) xcalloc (
739 n_basic_blocks, sizeof (HARD_REG_SET));
743 sbitmap_vector_zero (btr_defset, (last_btr - first_btr) + 1);
745 compute_defs_uses_and_gen (all_btr_defs, def_array, use_array, btr_defset,
746 bb_gen, btrs_written);
748 bb_kill = sbitmap_vector_alloc (n_basic_blocks, max_uid);
749 compute_kill (bb_kill, btr_defset, btrs_written);
752 bb_out = sbitmap_vector_alloc (n_basic_blocks, max_uid);
753 compute_out (bb_out, bb_gen, bb_kill, max_uid);
755 sbitmap_vector_free (bb_gen);
756 sbitmap_vector_free (bb_kill);
758 link_btr_uses (def_array, use_array, bb_out, btr_defset, max_uid);
760 sbitmap_vector_free (bb_out);
761 sbitmap_vector_free (btr_defset);
766 /* Return true if basic block BB contains the start or end of the
767 live range of the definition DEF, AND there are other live
768 ranges of the same target register that include BB. */
770 block_at_edge_of_live_range_p (int bb, btr_def def)
772 if (def->other_btr_uses_before_def && BASIC_BLOCK (bb) == def->bb)
774 else if (def->other_btr_uses_after_use)
777 for (user = def->uses; user != NULL; user = user->next)
778 if (BASIC_BLOCK (bb) == user->bb)
784 /* We are removing the def/use web DEF. The target register
785 used in this web is therefore no longer live in the live range
786 of this web, so remove it from the live set of all basic blocks
787 in the live range of the web.
788 Blocks at the boundary of the live range may contain other live
789 ranges for the same target register, so we have to be careful
790 to remove the target register from the live set of these blocks
791 only if they do not contain other live ranges for the same register. */
793 clear_btr_from_live_range (btr_def def)
797 EXECUTE_IF_SET_IN_BITMAP
798 (def->live_range, 0, bb,
800 if ((!def->other_btr_uses_before_def
801 && !def->other_btr_uses_after_use)
802 || !block_at_edge_of_live_range_p (bb, def))
804 CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr);
812 /* We are adding the def/use web DEF. Add the target register used
813 in this web to the live set of all of the basic blocks that contain
814 the live range of the web. */
816 add_btr_to_live_range (btr_def def)
819 EXECUTE_IF_SET_IN_BITMAP
820 (def->live_range, 0, bb,
822 SET_HARD_REG_BIT (btrs_live[bb], def->btr);
828 /* Update a live range to contain the basic block NEW_BLOCK, and all
829 blocks on paths between the existing live range and NEW_BLOCK.
830 HEAD is a block contained in the existing live range that dominates
831 all other blocks in the existing live range.
832 Also add to the set BTRS_LIVE_IN_RANGE all target registers that
833 are live in the blocks that we add to the live range.
834 It is a precondition that either NEW_BLOCK dominates HEAD,or
835 HEAD dom NEW_BLOCK. This is used to speed up the
836 implementation of this function. */
838 augment_live_range (bitmap live_range, HARD_REG_SET *btrs_live_in_range,
839 basic_block head_bb, basic_block new_bb)
841 basic_block *worklist, *tos;
844 (basic_block *) xmalloc (sizeof (basic_block) * (n_basic_blocks + 1));
846 if (dominated_by_p (dom, new_bb, head_bb))
848 else if (dominated_by_p (dom, head_bb, new_bb))
851 int new_block = new_bb->index;
853 bitmap_set_bit (live_range, new_block);
854 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]);
857 fprintf (rtl_dump_file,
858 "Adding block %d to live range\n", new_block);
859 fprintf (rtl_dump_file,"Now live btrs are ");
860 dump_hard_reg_set (*btrs_live_in_range);
861 fprintf (rtl_dump_file, "\n");
863 for (e = head_bb->pred; e; e = e->pred_next)
869 while (tos != worklist)
871 basic_block bb = *--tos;
872 if (!bitmap_bit_p (live_range, bb->index))
876 bitmap_set_bit (live_range, bb->index);
877 IOR_HARD_REG_SET (*btrs_live_in_range,
878 btrs_live[bb->index]);
881 fprintf (rtl_dump_file,
882 "Adding block %d to live range\n", bb->index);
883 fprintf (rtl_dump_file,"Now live btrs are ");
884 dump_hard_reg_set (*btrs_live_in_range);
885 fprintf (rtl_dump_file, "\n");
888 for (e = bb->pred; e != NULL; e = e->pred_next)
890 basic_block pred = e->src;
891 if (!bitmap_bit_p (live_range, pred->index))
900 /* Return the most desirable target register that is not in
901 the set USED_BTRS. */
903 choose_btr (HARD_REG_SET used_btrs)
906 GO_IF_HARD_REG_SUBSET (all_btrs, used_btrs, give_up);
908 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
910 #ifdef REG_ALLOC_ORDER
911 int regno = reg_alloc_order[i];
915 if (TEST_HARD_REG_BIT (all_btrs, regno)
916 && !TEST_HARD_REG_BIT (used_btrs, regno))
923 /* Calculate the set of basic blocks that contain the live range of
925 Also calculate the set of target registers that are live at time
926 in this live range, but ignore the live range represented by DEF
927 when calculating this set. */
929 btr_def_live_range (btr_def def, HARD_REG_SET *btrs_live_in_range)
931 if (!def->live_range)
935 def->live_range = BITMAP_XMALLOC ();
937 bitmap_set_bit (def->live_range, def->bb->index);
938 COPY_HARD_REG_SET (*btrs_live_in_range, btrs_live[def->bb->index]);
940 for (user = def->uses; user != NULL; user = user->next)
941 augment_live_range (def->live_range, btrs_live_in_range,
946 /* def->live_range is accurate, but we need to recompute
947 the set of target registers live over it, because migration
948 of other PT instructions may have affected it.
952 CLEAR_HARD_REG_SET (*btrs_live_in_range);
953 EXECUTE_IF_SET_IN_BITMAP
954 (def->live_range, 0, bb,
956 IOR_HARD_REG_SET (*btrs_live_in_range,
960 if (!def->other_btr_uses_before_def &&
961 !def->other_btr_uses_after_use)
962 CLEAR_HARD_REG_BIT (*btrs_live_in_range, def->btr);
965 /* Merge into the def/use web DEF any other def/use webs in the same
966 group that are dominated by DEF, provided that there is a target
967 register available to allocate to the merged web. */
969 combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range)
973 for (other_def = def->group->members;
975 other_def = other_def->next_this_group)
978 && other_def->uses != NULL
979 && ! other_def->has_ambiguous_use
980 && dominated_by_p (dom, other_def->bb, def->bb))
982 /* def->bb dominates the other def, so def and other_def could
984 /* Merge their live ranges, and get the set of
985 target registers live over the merged range. */
987 HARD_REG_SET combined_btrs_live;
988 bitmap combined_live_range = BITMAP_XMALLOC ();
991 if (other_def->live_range == NULL)
993 HARD_REG_SET dummy_btrs_live_in_range;
994 btr_def_live_range (other_def, &dummy_btrs_live_in_range);
996 COPY_HARD_REG_SET (combined_btrs_live, *btrs_live_in_range);
997 bitmap_copy (combined_live_range, def->live_range);
999 for (user = other_def->uses; user != NULL; user = user->next)
1000 augment_live_range (combined_live_range, &combined_btrs_live,
1003 btr = choose_btr (combined_btrs_live);
1006 /* We can combine them */
1008 fprintf (rtl_dump_file,
1009 "Combining def in insn %d with def in insn %d\n",
1010 INSN_UID (other_def->insn), INSN_UID (def->insn));
1013 user = other_def->uses;
1014 while (user != NULL)
1016 btr_user next = user->next;
1018 user->next = def->uses;
1022 /* Combining def/use webs can make target registers live
1023 after uses where they previously were not. This means
1024 some REG_DEAD notes may no longer be correct. We could
1025 be more precise about this if we looked at the combined
1026 live range, but here I just delete any REG_DEAD notes
1027 in case they are no longer correct. */
1028 for (user = def->uses; user != NULL; user = user->next)
1029 remove_note (user->insn,
1030 find_regno_note (user->insn, REG_DEAD,
1031 REGNO (user->use)));
1032 clear_btr_from_live_range (other_def);
1033 other_def->uses = NULL;
1034 bitmap_copy (def->live_range, combined_live_range);
1035 if (other_def->other_btr_uses_after_use)
1036 def->other_btr_uses_after_use = 1;
1037 COPY_HARD_REG_SET (*btrs_live_in_range, combined_btrs_live);
1039 /* Delete the old target register initialization */
1040 delete_insn (other_def->insn);
1043 BITMAP_XFREE (combined_live_range);
1048 /* Move the definition DEF from its current position to basic
1049 block NEW_DEF_BB, and modify it to use branch target register BTR.
1050 Delete the old defining insn, and insert a new one in NEW_DEF_BB.
1051 Update all reaching uses of DEF in the RTL to use BTR.
1052 If this new position means that other defs in the
1053 same group can be combined with DEF then combine them. */
1055 move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range,
1056 HARD_REG_SET *btrs_live_in_range)
1058 /* We can move the instruction.
1059 Set a target register in block NEW_DEF_BB to the value
1060 needed for this target register definition.
1061 Replace all uses of the old target register definition by
1062 uses of the new definition. Delete the old definition. */
1063 basic_block b = new_def_bb;
1065 rtx old_insn = def->insn;
1069 enum machine_mode btr_mode;
1074 fprintf(rtl_dump_file, "migrating to basic block %d, using reg %d\n",
1075 new_def_bb->index, btr);
1077 clear_btr_from_live_range (def);
1079 def->bb = new_def_bb;
1081 def->cost = basic_block_freq (new_def_bb);
1082 def->other_btr_uses_before_def = 0;
1083 bitmap_copy (def->live_range, live_range);
1084 combine_btr_defs (def, btrs_live_in_range);
1086 add_btr_to_live_range (def);
1087 if (GET_CODE (insp) == CODE_LABEL)
1088 insp = NEXT_INSN (insp);
1089 /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some
1090 optimizations can result in insp being both first and last insn of
1092 /* ?? some assertions to check that insp is sensible? */
1094 set = single_set (old_insn);
1095 src = SET_SRC (set);
1096 btr_mode = GET_MODE (SET_DEST (set));
1097 btr_rtx = gen_rtx (REG, btr_mode, btr);
1099 new_insn = gen_move_insn (btr_rtx, src);
1101 /* Insert target register initialization at head of basic block. */
1102 def->insn = emit_insn_after (new_insn, insp);
1104 regs_ever_live[btr] = 1;
1107 fprintf (rtl_dump_file, "New pt is insn %d, inserted after insn %d\n",
1108 INSN_UID (def->insn), INSN_UID (insp));
1110 /* Delete the old target register initialization */
1111 delete_insn (old_insn);
1113 /* Replace each use of the old target register by a use of the new target
1115 for (user = def->uses; user != NULL; user = user->next)
1117 /* Some extra work here to ensure consistent modes, because
1118 it seems that a target register REG rtx can be given a different
1119 mode depending on the context (surely that should not be
1121 rtx replacement_rtx;
1122 if (GET_MODE (user->use) == GET_MODE (btr_rtx)
1123 || GET_MODE (user->use) == VOIDmode)
1124 replacement_rtx = btr_rtx;
1126 replacement_rtx = gen_rtx (REG, GET_MODE (user->use), btr);
1127 replace_rtx (user->insn, user->use, replacement_rtx);
1128 user->use = replacement_rtx;
1132 /* We anticipate intra-block scheduling to be done. See if INSN could move
1133 up within BB by N_INSNS. */
1135 can_move_up (basic_block bb, rtx insn, int n_insns)
1137 while (insn != bb->head && n_insns > 0)
1139 insn = PREV_INSN (insn);
1140 /* ??? What if we have an anti-dependency that actually prevents the
1141 scheduler from doing the move? We'd like to re-allocate the register,
1142 but not necessarily put the load into another basic block. */
1146 return n_insns <= 0;
1149 /* Attempt to migrate the target register definition DEF to an
1150 earlier point in the flowgraph.
1152 It is a precondition of this function that DEF is migratable:
1153 i.e. it has a constant source, and all uses are unambiguous.
1155 Only migrations that reduce the cost of DEF will be made.
1156 MIN_COST is the lower bound on the cost of the DEF after migration.
1157 If we migrate DEF so that its cost falls below MIN_COST,
1158 then we do not attempt to migrate further. The idea is that
1159 we migrate defintions in a priority order based on their cost,
1160 when the cost of this definition falls below MIN_COST, then
1161 there is another definition with cost == MIN_COST which now
1162 has a higher priority than this definition.
1164 Return non-zero if there may be benefit from attempting to
1165 migrate this DEF further (i.e. we have reduced the cost below
1166 MIN_COST, but we may be able to reduce it further).
1167 Return zero if no further migration is possible. */
1169 migrate_btr_def (btr_def def, int min_cost)
1172 HARD_REG_SET btrs_live_in_range;
1173 int btr_used_near_def = 0;
1174 int def_basic_block_freq;
1179 int def_latency = 1;
1182 fprintf (rtl_dump_file,
1183 "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ",
1184 INSN_UID (def->insn), def->cost, min_cost);
1186 if (!def->group || def->has_ambiguous_use)
1187 /* These defs are not migratable */
1190 fprintf (rtl_dump_file, "it's not migratable\n");
1195 /* We have combined this def with another in the same group, so
1196 no need to consider it further.
1200 fprintf (rtl_dump_file, "it's already combined with another pt\n");
1204 btr_def_live_range (def, &btrs_live_in_range);
1205 live_range = BITMAP_XMALLOC ();
1206 bitmap_copy (live_range, def->live_range);
1208 #ifdef INSN_SCHEDULING
1209 if ((*targetm.sched.use_dfa_pipeline_interface) ())
1210 def_latency = insn_default_latency (def->insn);
1212 def_latency = result_ready_cost (def->insn);
1215 def_latency *= issue_rate;
1217 for (user = def->uses; user != NULL; user = user->next)
1219 if (user->bb == def->bb
1220 && user->luid > def->luid
1221 && (def->luid + def_latency) > user->luid
1222 && ! can_move_up (def->bb, def->insn,
1223 (def->luid + def_latency) - user->luid))
1225 btr_used_near_def = 1;
1230 def_basic_block_freq = basic_block_freq (def->bb);
1232 for (try = get_immediate_dominator (dom, def->bb);
1233 !give_up && try && try != ENTRY_BLOCK_PTR && def->cost >= min_cost;
1234 try = get_immediate_dominator (dom, try))
1236 /* Try to move the instruction that sets the target register into
1238 int try_freq = basic_block_freq (try);
1241 fprintf (rtl_dump_file, "trying block %d ...", try->index);
1243 if (try_freq < def_basic_block_freq
1244 || (try_freq == def_basic_block_freq && btr_used_near_def))
1247 augment_live_range (live_range, &btrs_live_in_range, def->bb, try);
1250 fprintf (rtl_dump_file, "Now btrs live in range are: ");
1251 dump_hard_reg_set (btrs_live_in_range);
1252 fprintf (rtl_dump_file, "\n");
1254 btr = choose_btr (btrs_live_in_range);
1257 move_btr_def (try, btr, def, live_range, &btrs_live_in_range);
1258 bitmap_copy(live_range, def->live_range);
1259 btr_used_near_def = 0;
1261 def_basic_block_freq = basic_block_freq (def->bb);
1265 /* There are no free target registers available to move
1266 this far forward, so give up */
1269 fprintf (rtl_dump_file,
1270 "giving up because there are no free target registers\n");
1279 fprintf (rtl_dump_file, "failed to move\n");
1281 BITMAP_XFREE (live_range);
1285 /* Attempt to move instructions that set target registers earlier
1286 in the flowgraph, away from their corresponding uses. */
1288 migrate_btr_defs (enum reg_class btr_class, int allow_callee_save)
1290 fibheap_t all_btr_defs = fibheap_new ();
1293 gcc_obstack_init (&migrate_btrl_obstack);
1298 for (i = 0; i < n_basic_blocks; i++)
1300 basic_block bb = BASIC_BLOCK (i);
1301 fprintf(rtl_dump_file,
1302 "Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC
1303 " loop-depth = %d idom = %d\n",
1304 i, (HOST_WIDEST_INT) bb->count, bb->loop_depth,
1305 get_immediate_dominator (dom, bb)->index);
1309 CLEAR_HARD_REG_SET (all_btrs);
1310 for (first_btr = -1, reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
1311 if (TEST_HARD_REG_BIT (reg_class_contents[(int) btr_class], reg)
1312 && (allow_callee_save || call_used_regs[reg] || regs_ever_live[reg]))
1314 SET_HARD_REG_BIT (all_btrs, reg);
1321 (HARD_REG_SET *) xcalloc (n_basic_blocks, sizeof (HARD_REG_SET));
1323 build_btr_def_use_webs (all_btr_defs);
1325 while (!fibheap_empty (all_btr_defs))
1328 (btr_def) fibheap_extract_min (all_btr_defs);
1329 int min_cost = -fibheap_min_key (all_btr_defs);
1330 if (migrate_btr_def (def, min_cost))
1332 fibheap_insert (all_btr_defs, -def->cost, (void *) def);
1335 fprintf (rtl_dump_file,
1336 "Putting insn %d back on queue with priority %d\n",
1337 INSN_UID (def->insn), def->cost);
1342 if (def->live_range)
1343 BITMAP_XFREE (def->live_range);
1348 obstack_free (&migrate_btrl_obstack, NULL);
1349 fibheap_delete (all_btr_defs);
1353 branch_target_load_optimize (rtx insns, bool after_prologue_epilogue_gen)
1355 enum reg_class class = (*targetm.branch_target_register_class) ();
1356 if (class != NO_REGS)
1358 /* Initialize issue_rate. */
1359 if (targetm.sched.issue_rate)
1360 issue_rate = (*targetm.sched.issue_rate) ();
1364 /* Build the CFG for migrate_btr_defs. */
1366 /* This may or may not be needed, depending on where we
1368 cleanup_cfg (optimize ? CLEANUP_EXPENSIVE : 0);
1371 life_analysis (insns, NULL, 0);
1373 /* Dominator info is also needed for migrate_btr_def. */
1374 dom = calculate_dominance_info (CDI_DOMINATORS);
1375 migrate_btr_defs (class,
1376 ((*targetm.branch_target_register_callee_saved)
1377 (after_prologue_epilogue_gen)));
1379 free_dominance_info (dom);
1381 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
1382 PROP_DEATH_NOTES | PROP_REG_INFO);