Daily bump.
[official-gcc.git] / gcc / bt-load.c
blobc30f2c3342e75edc5eabe49eba1625a8e1d8bc72
1 /* Perform branch target register load optimizations.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "hard-reg-set.h"
27 #include "regs.h"
28 #include "fibheap.h"
29 #include "output.h"
30 #include "target.h"
31 #include "expr.h"
32 #include "flags.h"
33 #include "insn-attr.h"
34 #include "function.h"
35 #include "except.h"
36 #include "tm_p.h"
37 #include "toplev.h"
38 #include "tree-pass.h"
39 #include "recog.h"
40 #include "df.h"
42 /* Target register optimizations - these are performed after reload. */
44 typedef struct btr_def_group_s
46 struct btr_def_group_s *next;
47 rtx src;
48 struct btr_def_s *members;
49 } *btr_def_group;
51 typedef struct btr_user_s
53 struct btr_user_s *next;
54 basic_block bb;
55 int luid;
56 rtx insn;
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,
60 then USE is NULL. */
61 rtx use;
62 int n_reaching_defs;
63 int first_reaching_def;
64 char other_use_this_block;
65 } *btr_user;
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;
80 basic_block bb;
81 int luid;
82 rtx insn;
83 int btr;
84 int cost;
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. */
89 btr_def_group group;
90 btr_user uses;
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
102 as appropriate. */
103 char other_btr_uses_before_def;
104 char other_btr_uses_after_use;
105 /* We set own_end when we have moved a definition into a dominator.
106 Thus, when a later combination removes this definition again, we know
107 to clear out trs_live_at_end again. */
108 char own_end;
109 bitmap live_range;
110 } *btr_def;
112 static int issue_rate;
114 static int basic_block_freq (const_basic_block);
115 static int insn_sets_btr_p (const_rtx, int, int *);
116 static rtx *find_btr_use (rtx);
117 static int btr_referenced_p (rtx, rtx *);
118 static int find_btr_reference (rtx *, void *);
119 static void find_btr_def_group (btr_def_group *, btr_def);
120 static btr_def add_btr_def (fibheap_t, basic_block, int, rtx,
121 unsigned int, int, btr_def_group *);
122 static btr_user new_btr_user (basic_block, int, rtx);
123 static void dump_hard_reg_set (HARD_REG_SET);
124 static void dump_btrs_live (int);
125 static void note_other_use_this_block (unsigned int, btr_user);
126 static void compute_defs_uses_and_gen (fibheap_t, btr_def *,btr_user *,
127 sbitmap *, sbitmap *, HARD_REG_SET *);
128 static void compute_kill (sbitmap *, sbitmap *, HARD_REG_SET *);
129 static void compute_out (sbitmap *bb_out, sbitmap *, sbitmap *, int);
130 static void link_btr_uses (btr_def *, btr_user *, sbitmap *, sbitmap *, int);
131 static void build_btr_def_use_webs (fibheap_t);
132 static int block_at_edge_of_live_range_p (int, btr_def);
133 static void clear_btr_from_live_range (btr_def def);
134 static void add_btr_to_live_range (btr_def, int);
135 static void augment_live_range (bitmap, HARD_REG_SET *, basic_block,
136 basic_block, int);
137 static int choose_btr (HARD_REG_SET);
138 static void combine_btr_defs (btr_def, HARD_REG_SET *);
139 static void btr_def_live_range (btr_def, HARD_REG_SET *);
140 static void move_btr_def (basic_block, int, btr_def, bitmap, HARD_REG_SET *);
141 static int migrate_btr_def (btr_def, int);
142 static void migrate_btr_defs (enum reg_class, int);
143 static int can_move_up (const_basic_block, const_rtx, int);
144 static void note_btr_set (rtx, const_rtx, void *);
146 /* The following code performs code motion of target load instructions
147 (instructions that set branch target registers), to move them
148 forward away from the branch instructions and out of loops (or,
149 more generally, from a more frequently executed place to a less
150 frequently executed place).
151 Moving target load instructions further in front of the branch
152 instruction that uses the target register value means that the hardware
153 has a better chance of preloading the instructions at the branch
154 target by the time the branch is reached. This avoids bubbles
155 when a taken branch needs to flush out the pipeline.
156 Moving target load instructions out of loops means they are executed
157 less frequently. */
159 /* An obstack to hold the def-use web data structures built up for
160 migrating branch target load instructions. */
161 static struct obstack migrate_btrl_obstack;
163 /* Array indexed by basic block number, giving the set of registers
164 live in that block. */
165 static HARD_REG_SET *btrs_live;
167 /* Array indexed by basic block number, giving the set of registers live at
168 the end of that block, including any uses by a final jump insn, if any. */
169 static HARD_REG_SET *btrs_live_at_end;
171 /* Set of all target registers that we are willing to allocate. */
172 static HARD_REG_SET all_btrs;
174 /* Provide lower and upper bounds for target register numbers, so that
175 we don't need to search through all the hard registers all the time. */
176 static int first_btr, last_btr;
180 /* Return an estimate of the frequency of execution of block bb. */
181 static int
182 basic_block_freq (const_basic_block bb)
184 return bb->frequency;
187 static rtx *btr_reference_found;
189 /* A subroutine of btr_referenced_p, called through for_each_rtx.
190 PREG is a pointer to an rtx that is to be excluded from the
191 traversal. If we find a reference to a target register anywhere
192 else, return 1, and put a pointer to it into btr_reference_found. */
193 static int
194 find_btr_reference (rtx *px, void *preg)
196 rtx x;
198 if (px == preg)
199 return -1;
200 x = *px;
201 if (!REG_P (x))
202 return 0;
203 if (overlaps_hard_reg_set_p (all_btrs, GET_MODE (x), REGNO (x)))
205 btr_reference_found = px;
206 return 1;
208 return -1;
211 /* Return nonzero if X references (sets or reads) any branch target register.
212 If EXCLUDEP is set, disregard any references within the rtx pointed to
213 by it. If returning nonzero, also set btr_reference_found as above. */
214 static int
215 btr_referenced_p (rtx x, rtx *excludep)
217 return for_each_rtx (&x, find_btr_reference, excludep);
220 /* Return true if insn is an instruction that sets a target register.
221 if CHECK_CONST is true, only return true if the source is constant.
222 If such a set is found and REGNO is nonzero, assign the register number
223 of the destination register to *REGNO. */
224 static int
225 insn_sets_btr_p (const_rtx insn, int check_const, int *regno)
227 rtx set;
229 if (NONJUMP_INSN_P (insn)
230 && (set = single_set (insn)))
232 rtx dest = SET_DEST (set);
233 rtx src = SET_SRC (set);
235 if (GET_CODE (dest) == SUBREG)
236 dest = XEXP (dest, 0);
238 if (REG_P (dest)
239 && TEST_HARD_REG_BIT (all_btrs, REGNO (dest)))
241 gcc_assert (!btr_referenced_p (src, NULL));
243 if (!check_const || CONSTANT_P (src))
245 if (regno)
246 *regno = REGNO (dest);
247 return 1;
251 return 0;
254 /* Find and return a use of a target register within an instruction INSN. */
255 static rtx *
256 find_btr_use (rtx insn)
258 return btr_referenced_p (insn, NULL) ? btr_reference_found : NULL;
261 /* Find the group that the target register definition DEF belongs
262 to in the list starting with *ALL_BTR_DEF_GROUPS. If no such
263 group exists, create one. Add def to the group. */
264 static void
265 find_btr_def_group (btr_def_group *all_btr_def_groups, btr_def def)
267 if (insn_sets_btr_p (def->insn, 1, NULL))
269 btr_def_group this_group;
270 rtx def_src = SET_SRC (single_set (def->insn));
272 /* ?? This linear search is an efficiency concern, particularly
273 as the search will almost always fail to find a match. */
274 for (this_group = *all_btr_def_groups;
275 this_group != NULL;
276 this_group = this_group->next)
277 if (rtx_equal_p (def_src, this_group->src))
278 break;
280 if (!this_group)
282 this_group = obstack_alloc (&migrate_btrl_obstack,
283 sizeof (struct btr_def_group_s));
284 this_group->src = def_src;
285 this_group->members = NULL;
286 this_group->next = *all_btr_def_groups;
287 *all_btr_def_groups = this_group;
289 def->group = this_group;
290 def->next_this_group = this_group->members;
291 this_group->members = def;
293 else
294 def->group = NULL;
297 /* Create a new target register definition structure, for a definition in
298 block BB, instruction INSN, and insert it into ALL_BTR_DEFS. Return
299 the new definition. */
300 static btr_def
301 add_btr_def (fibheap_t all_btr_defs, basic_block bb, int insn_luid, rtx insn,
302 unsigned int dest_reg, int other_btr_uses_before_def,
303 btr_def_group *all_btr_def_groups)
305 btr_def this
306 = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_def_s));
307 this->bb = bb;
308 this->luid = insn_luid;
309 this->insn = insn;
310 this->btr = dest_reg;
311 this->cost = basic_block_freq (bb);
312 this->has_ambiguous_use = 0;
313 this->other_btr_uses_before_def = other_btr_uses_before_def;
314 this->other_btr_uses_after_use = 0;
315 this->next_this_bb = NULL;
316 this->next_this_group = NULL;
317 this->uses = NULL;
318 this->live_range = NULL;
319 find_btr_def_group (all_btr_def_groups, this);
321 fibheap_insert (all_btr_defs, -this->cost, this);
323 if (dump_file)
324 fprintf (dump_file,
325 "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n",
326 dest_reg, bb->index, INSN_UID (insn), (this->group ? "" : ":not const"),
327 this->cost);
329 return this;
332 /* Create a new target register user structure, for a use in block BB,
333 instruction INSN. Return the new user. */
334 static btr_user
335 new_btr_user (basic_block bb, int insn_luid, rtx insn)
337 /* This instruction reads target registers. We need
338 to decide whether we can replace all target register
339 uses easily.
341 rtx *usep = find_btr_use (PATTERN (insn));
342 rtx use;
343 btr_user user = NULL;
345 if (usep)
347 int unambiguous_single_use;
349 /* We want to ensure that USE is the only use of a target
350 register in INSN, so that we know that to rewrite INSN to use
351 a different target register, all we have to do is replace USE. */
352 unambiguous_single_use = !btr_referenced_p (PATTERN (insn), usep);
353 if (!unambiguous_single_use)
354 usep = NULL;
356 use = usep ? *usep : NULL_RTX;
357 user = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_user_s));
358 user->bb = bb;
359 user->luid = insn_luid;
360 user->insn = insn;
361 user->use = use;
362 user->other_use_this_block = 0;
363 user->next = NULL;
364 user->n_reaching_defs = 0;
365 user->first_reaching_def = -1;
367 if (dump_file)
369 fprintf (dump_file, "Uses target reg: { bb %d, insn %d }",
370 bb->index, INSN_UID (insn));
372 if (user->use)
373 fprintf (dump_file, ": unambiguous use of reg %d\n",
374 REGNO (user->use));
377 return user;
380 /* Write the contents of S to the dump file. */
381 static void
382 dump_hard_reg_set (HARD_REG_SET s)
384 int reg;
385 for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
386 if (TEST_HARD_REG_BIT (s, reg))
387 fprintf (dump_file, " %d", reg);
390 /* Write the set of target regs live in block BB to the dump file. */
391 static void
392 dump_btrs_live (int bb)
394 fprintf (dump_file, "BB%d live:", bb);
395 dump_hard_reg_set (btrs_live[bb]);
396 fprintf (dump_file, "\n");
399 /* REGNO is the number of a branch target register that is being used or
400 set. USERS_THIS_BB is a list of preceding branch target register users;
401 If any of them use the same register, set their other_use_this_block
402 flag. */
403 static void
404 note_other_use_this_block (unsigned int regno, btr_user users_this_bb)
406 btr_user user;
408 for (user = users_this_bb; user != NULL; user = user->next)
409 if (user->use && REGNO (user->use) == regno)
410 user->other_use_this_block = 1;
413 typedef struct {
414 btr_user users_this_bb;
415 HARD_REG_SET btrs_written_in_block;
416 HARD_REG_SET btrs_live_in_block;
417 sbitmap bb_gen;
418 sbitmap *btr_defset;
419 } defs_uses_info;
421 /* Called via note_stores or directly to register stores into /
422 clobbers of a branch target register DEST that are not recognized as
423 straightforward definitions. DATA points to information about the
424 current basic block that needs updating. */
425 static void
426 note_btr_set (rtx dest, const_rtx set ATTRIBUTE_UNUSED, void *data)
428 defs_uses_info *info = data;
429 int regno, end_regno;
431 if (!REG_P (dest))
432 return;
433 regno = REGNO (dest);
434 end_regno = END_HARD_REGNO (dest);
435 for (; regno < end_regno; regno++)
436 if (TEST_HARD_REG_BIT (all_btrs, regno))
438 note_other_use_this_block (regno, info->users_this_bb);
439 SET_HARD_REG_BIT (info->btrs_written_in_block, regno);
440 SET_HARD_REG_BIT (info->btrs_live_in_block, regno);
441 sbitmap_difference (info->bb_gen, info->bb_gen,
442 info->btr_defset[regno - first_btr]);
446 static void
447 compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array,
448 btr_user *use_array, sbitmap *btr_defset,
449 sbitmap *bb_gen, HARD_REG_SET *btrs_written)
451 /* Scan the code building up the set of all defs and all uses.
452 For each target register, build the set of defs of that register.
453 For each block, calculate the set of target registers
454 written in that block.
455 Also calculate the set of btrs ever live in that block.
457 int i;
458 int insn_luid = 0;
459 btr_def_group all_btr_def_groups = NULL;
460 defs_uses_info info;
462 sbitmap_vector_zero (bb_gen, n_basic_blocks);
463 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
465 basic_block bb = BASIC_BLOCK (i);
466 int reg;
467 btr_def defs_this_bb = NULL;
468 rtx insn;
469 rtx last;
470 int can_throw = 0;
472 info.users_this_bb = NULL;
473 info.bb_gen = bb_gen[i];
474 info.btr_defset = btr_defset;
476 CLEAR_HARD_REG_SET (info.btrs_live_in_block);
477 CLEAR_HARD_REG_SET (info.btrs_written_in_block);
478 for (reg = first_btr; reg <= last_btr; reg++)
479 if (TEST_HARD_REG_BIT (all_btrs, reg)
480 && REGNO_REG_SET_P (df_get_live_in (bb), reg))
481 SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
483 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
484 insn != last;
485 insn = NEXT_INSN (insn), insn_luid++)
487 if (INSN_P (insn))
489 int regno;
490 int insn_uid = INSN_UID (insn);
492 if (insn_sets_btr_p (insn, 0, &regno))
494 btr_def def = add_btr_def (
495 all_btr_defs, bb, insn_luid, insn, regno,
496 TEST_HARD_REG_BIT (info.btrs_live_in_block, regno),
497 &all_btr_def_groups);
499 def_array[insn_uid] = def;
500 SET_HARD_REG_BIT (info.btrs_written_in_block, regno);
501 SET_HARD_REG_BIT (info.btrs_live_in_block, regno);
502 sbitmap_difference (bb_gen[i], bb_gen[i],
503 btr_defset[regno - first_btr]);
504 SET_BIT (bb_gen[i], insn_uid);
505 def->next_this_bb = defs_this_bb;
506 defs_this_bb = def;
507 SET_BIT (btr_defset[regno - first_btr], insn_uid);
508 note_other_use_this_block (regno, info.users_this_bb);
510 /* Check for the blockage emitted by expand_nl_goto_receiver. */
511 else if (current_function_has_nonlocal_label
512 && GET_CODE (PATTERN (insn)) == UNSPEC_VOLATILE)
514 btr_user user;
516 /* Do the equivalent of calling note_other_use_this_block
517 for every target register. */
518 for (user = info.users_this_bb; user != NULL;
519 user = user->next)
520 if (user->use)
521 user->other_use_this_block = 1;
522 IOR_HARD_REG_SET (info.btrs_written_in_block, all_btrs);
523 IOR_HARD_REG_SET (info.btrs_live_in_block, all_btrs);
524 sbitmap_zero (info.bb_gen);
526 else
528 if (btr_referenced_p (PATTERN (insn), NULL))
530 btr_user user = new_btr_user (bb, insn_luid, insn);
532 use_array[insn_uid] = user;
533 if (user->use)
534 SET_HARD_REG_BIT (info.btrs_live_in_block,
535 REGNO (user->use));
536 else
538 int reg;
539 for (reg = first_btr; reg <= last_btr; reg++)
540 if (TEST_HARD_REG_BIT (all_btrs, reg)
541 && refers_to_regno_p (reg, reg + 1, user->insn,
542 NULL))
544 note_other_use_this_block (reg,
545 info.users_this_bb);
546 SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
548 note_stores (PATTERN (insn), note_btr_set, &info);
550 user->next = info.users_this_bb;
551 info.users_this_bb = user;
553 if (CALL_P (insn))
555 HARD_REG_SET *clobbered = &call_used_reg_set;
556 HARD_REG_SET call_saved;
557 rtx pat = PATTERN (insn);
558 int i;
560 /* Check for sibcall. */
561 if (GET_CODE (pat) == PARALLEL)
562 for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
563 if (GET_CODE (XVECEXP (pat, 0, i)) == RETURN)
565 COMPL_HARD_REG_SET (call_saved,
566 call_used_reg_set);
567 clobbered = &call_saved;
570 for (regno = first_btr; regno <= last_btr; regno++)
571 if (TEST_HARD_REG_BIT (*clobbered, regno))
572 note_btr_set (regno_reg_rtx[regno], NULL_RTX, &info);
578 COPY_HARD_REG_SET (btrs_live[i], info.btrs_live_in_block);
579 COPY_HARD_REG_SET (btrs_written[i], info.btrs_written_in_block);
581 REG_SET_TO_HARD_REG_SET (btrs_live_at_end[i], df_get_live_out (bb));
582 /* If this block ends in a jump insn, add any uses or even clobbers
583 of branch target registers that it might have. */
584 for (insn = BB_END (bb); insn != BB_HEAD (bb) && ! INSN_P (insn); )
585 insn = PREV_INSN (insn);
586 /* ??? for the fall-through edge, it would make sense to insert the
587 btr set on the edge, but that would require to split the block
588 early on so that we can distinguish between dominance from the fall
589 through edge - which can use the call-clobbered registers - from
590 dominance by the throw edge. */
591 if (can_throw_internal (insn))
593 HARD_REG_SET tmp;
595 COPY_HARD_REG_SET (tmp, call_used_reg_set);
596 AND_HARD_REG_SET (tmp, all_btrs);
597 IOR_HARD_REG_SET (btrs_live_at_end[i], tmp);
598 can_throw = 1;
600 if (can_throw || JUMP_P (insn))
602 int regno;
604 for (regno = first_btr; regno <= last_btr; regno++)
605 if (refers_to_regno_p (regno, regno+1, insn, NULL))
606 SET_HARD_REG_BIT (btrs_live_at_end[i], regno);
609 if (dump_file)
610 dump_btrs_live(i);
614 static void
615 compute_kill (sbitmap *bb_kill, sbitmap *btr_defset,
616 HARD_REG_SET *btrs_written)
618 int i;
619 int regno;
621 /* For each basic block, form the set BB_KILL - the set
622 of definitions that the block kills. */
623 sbitmap_vector_zero (bb_kill, n_basic_blocks);
624 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
626 for (regno = first_btr; regno <= last_btr; regno++)
627 if (TEST_HARD_REG_BIT (all_btrs, regno)
628 && TEST_HARD_REG_BIT (btrs_written[i], regno))
629 sbitmap_a_or_b (bb_kill[i], bb_kill[i],
630 btr_defset[regno - first_btr]);
634 static void
635 compute_out (sbitmap *bb_out, sbitmap *bb_gen, sbitmap *bb_kill, int max_uid)
637 /* Perform iterative dataflow:
638 Initially, for all blocks, BB_OUT = BB_GEN.
639 For each block,
640 BB_IN = union over predecessors of BB_OUT(pred)
641 BB_OUT = (BB_IN - BB_KILL) + BB_GEN
642 Iterate until the bb_out sets stop growing. */
643 int i;
644 int changed;
645 sbitmap bb_in = sbitmap_alloc (max_uid);
647 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
648 sbitmap_copy (bb_out[i], bb_gen[i]);
650 changed = 1;
651 while (changed)
653 changed = 0;
654 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
656 sbitmap_union_of_preds (bb_in, bb_out, i);
657 changed |= sbitmap_union_of_diff_cg (bb_out[i], bb_gen[i],
658 bb_in, bb_kill[i]);
661 sbitmap_free (bb_in);
664 static void
665 link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out,
666 sbitmap *btr_defset, int max_uid)
668 int i;
669 sbitmap reaching_defs = sbitmap_alloc (max_uid);
671 /* Link uses to the uses lists of all of their reaching defs.
672 Count up the number of reaching defs of each use. */
673 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
675 basic_block bb = BASIC_BLOCK (i);
676 rtx insn;
677 rtx last;
679 sbitmap_union_of_preds (reaching_defs, bb_out, i);
680 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
681 insn != last;
682 insn = NEXT_INSN (insn))
684 if (INSN_P (insn))
686 int insn_uid = INSN_UID (insn);
688 btr_def def = def_array[insn_uid];
689 btr_user user = use_array[insn_uid];
690 if (def != NULL)
692 /* Remove all reaching defs of regno except
693 for this one. */
694 sbitmap_difference (reaching_defs, reaching_defs,
695 btr_defset[def->btr - first_btr]);
696 SET_BIT(reaching_defs, insn_uid);
699 if (user != NULL)
701 /* Find all the reaching defs for this use. */
702 sbitmap reaching_defs_of_reg = sbitmap_alloc(max_uid);
703 unsigned int uid = 0;
704 sbitmap_iterator sbi;
706 if (user->use)
707 sbitmap_a_and_b (
708 reaching_defs_of_reg,
709 reaching_defs,
710 btr_defset[REGNO (user->use) - first_btr]);
711 else
713 int reg;
715 sbitmap_zero (reaching_defs_of_reg);
716 for (reg = first_btr; reg <= last_btr; reg++)
717 if (TEST_HARD_REG_BIT (all_btrs, reg)
718 && refers_to_regno_p (reg, reg + 1, user->insn,
719 NULL))
720 sbitmap_a_or_b_and_c (reaching_defs_of_reg,
721 reaching_defs_of_reg,
722 reaching_defs,
723 btr_defset[reg - first_btr]);
725 EXECUTE_IF_SET_IN_SBITMAP (reaching_defs_of_reg, 0, uid, sbi)
727 btr_def def = def_array[uid];
729 /* We now know that def reaches user. */
731 if (dump_file)
732 fprintf (dump_file,
733 "Def in insn %d reaches use in insn %d\n",
734 uid, insn_uid);
736 user->n_reaching_defs++;
737 if (!user->use)
738 def->has_ambiguous_use = 1;
739 if (user->first_reaching_def != -1)
740 { /* There is more than one reaching def. This is
741 a rare case, so just give up on this def/use
742 web when it occurs. */
743 def->has_ambiguous_use = 1;
744 def_array[user->first_reaching_def]
745 ->has_ambiguous_use = 1;
746 if (dump_file)
747 fprintf (dump_file,
748 "(use %d has multiple reaching defs)\n",
749 insn_uid);
751 else
752 user->first_reaching_def = uid;
753 if (user->other_use_this_block)
754 def->other_btr_uses_after_use = 1;
755 user->next = def->uses;
756 def->uses = user;
758 sbitmap_free (reaching_defs_of_reg);
761 if (CALL_P (insn))
763 int regno;
765 for (regno = first_btr; regno <= last_btr; regno++)
766 if (TEST_HARD_REG_BIT (all_btrs, regno)
767 && TEST_HARD_REG_BIT (call_used_reg_set, regno))
768 sbitmap_difference (reaching_defs, reaching_defs,
769 btr_defset[regno - first_btr]);
774 sbitmap_free (reaching_defs);
777 static void
778 build_btr_def_use_webs (fibheap_t all_btr_defs)
780 const int max_uid = get_max_uid ();
781 btr_def *def_array = XCNEWVEC (btr_def, max_uid);
782 btr_user *use_array = XCNEWVEC (btr_user, max_uid);
783 sbitmap *btr_defset = sbitmap_vector_alloc (
784 (last_btr - first_btr) + 1, max_uid);
785 sbitmap *bb_gen = sbitmap_vector_alloc (n_basic_blocks, max_uid);
786 HARD_REG_SET *btrs_written = XCNEWVEC (HARD_REG_SET, n_basic_blocks);
787 sbitmap *bb_kill;
788 sbitmap *bb_out;
790 sbitmap_vector_zero (btr_defset, (last_btr - first_btr) + 1);
792 compute_defs_uses_and_gen (all_btr_defs, def_array, use_array, btr_defset,
793 bb_gen, btrs_written);
795 bb_kill = sbitmap_vector_alloc (n_basic_blocks, max_uid);
796 compute_kill (bb_kill, btr_defset, btrs_written);
797 free (btrs_written);
799 bb_out = sbitmap_vector_alloc (n_basic_blocks, max_uid);
800 compute_out (bb_out, bb_gen, bb_kill, max_uid);
802 sbitmap_vector_free (bb_gen);
803 sbitmap_vector_free (bb_kill);
805 link_btr_uses (def_array, use_array, bb_out, btr_defset, max_uid);
807 sbitmap_vector_free (bb_out);
808 sbitmap_vector_free (btr_defset);
809 free (use_array);
810 free (def_array);
813 /* Return true if basic block BB contains the start or end of the
814 live range of the definition DEF, AND there are other live
815 ranges of the same target register that include BB. */
816 static int
817 block_at_edge_of_live_range_p (int bb, btr_def def)
819 if (def->other_btr_uses_before_def && BASIC_BLOCK (bb) == def->bb)
820 return 1;
821 else if (def->other_btr_uses_after_use)
823 btr_user user;
824 for (user = def->uses; user != NULL; user = user->next)
825 if (BASIC_BLOCK (bb) == user->bb)
826 return 1;
828 return 0;
831 /* We are removing the def/use web DEF. The target register
832 used in this web is therefore no longer live in the live range
833 of this web, so remove it from the live set of all basic blocks
834 in the live range of the web.
835 Blocks at the boundary of the live range may contain other live
836 ranges for the same target register, so we have to be careful
837 to remove the target register from the live set of these blocks
838 only if they do not contain other live ranges for the same register. */
839 static void
840 clear_btr_from_live_range (btr_def def)
842 unsigned bb;
843 bitmap_iterator bi;
845 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
847 if ((!def->other_btr_uses_before_def
848 && !def->other_btr_uses_after_use)
849 || !block_at_edge_of_live_range_p (bb, def))
851 CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr);
852 CLEAR_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
853 if (dump_file)
854 dump_btrs_live (bb);
857 if (def->own_end)
858 CLEAR_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr);
862 /* We are adding the def/use web DEF. Add the target register used
863 in this web to the live set of all of the basic blocks that contain
864 the live range of the web.
865 If OWN_END is set, also show that the register is live from our
866 definitions at the end of the basic block where it is defined. */
867 static void
868 add_btr_to_live_range (btr_def def, int own_end)
870 unsigned bb;
871 bitmap_iterator bi;
873 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
875 SET_HARD_REG_BIT (btrs_live[bb], def->btr);
876 SET_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
877 if (dump_file)
878 dump_btrs_live (bb);
880 if (own_end)
882 SET_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr);
883 def->own_end = 1;
887 /* Update a live range to contain the basic block NEW_BLOCK, and all
888 blocks on paths between the existing live range and NEW_BLOCK.
889 HEAD is a block contained in the existing live range that dominates
890 all other blocks in the existing live range.
891 Also add to the set BTRS_LIVE_IN_RANGE all target registers that
892 are live in the blocks that we add to the live range.
893 If FULL_RANGE is set, include the full live range of NEW_BB;
894 otherwise, if NEW_BB dominates HEAD_BB, only add registers that
895 are life at the end of NEW_BB for NEW_BB itself.
896 It is a precondition that either NEW_BLOCK dominates HEAD,or
897 HEAD dom NEW_BLOCK. This is used to speed up the
898 implementation of this function. */
899 static void
900 augment_live_range (bitmap live_range, HARD_REG_SET *btrs_live_in_range,
901 basic_block head_bb, basic_block new_bb, int full_range)
903 basic_block *worklist, *tos;
905 tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1);
907 if (dominated_by_p (CDI_DOMINATORS, new_bb, head_bb))
909 if (new_bb == head_bb)
911 if (full_range)
912 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_bb->index]);
913 free (tos);
914 return;
916 *tos++ = new_bb;
918 else
920 edge e;
921 edge_iterator ei;
922 int new_block = new_bb->index;
924 gcc_assert (dominated_by_p (CDI_DOMINATORS, head_bb, new_bb));
926 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[head_bb->index]);
927 bitmap_set_bit (live_range, new_block);
928 /* A previous btr migration could have caused a register to be
929 live just at the end of new_block which we need in full, so
930 use trs_live_at_end even if full_range is set. */
931 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live_at_end[new_block]);
932 if (full_range)
933 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]);
934 if (dump_file)
936 fprintf (dump_file,
937 "Adding end of block %d and rest of %d to live range\n",
938 new_block, head_bb->index);
939 fprintf (dump_file,"Now live btrs are ");
940 dump_hard_reg_set (*btrs_live_in_range);
941 fprintf (dump_file, "\n");
943 FOR_EACH_EDGE (e, ei, head_bb->preds)
944 *tos++ = e->src;
947 while (tos != worklist)
949 basic_block bb = *--tos;
950 if (!bitmap_bit_p (live_range, bb->index))
952 edge e;
953 edge_iterator ei;
955 bitmap_set_bit (live_range, bb->index);
956 IOR_HARD_REG_SET (*btrs_live_in_range,
957 btrs_live[bb->index]);
958 /* A previous btr migration could have caused a register to be
959 live just at the end of a block which we need in full. */
960 IOR_HARD_REG_SET (*btrs_live_in_range,
961 btrs_live_at_end[bb->index]);
962 if (dump_file)
964 fprintf (dump_file,
965 "Adding block %d to live range\n", bb->index);
966 fprintf (dump_file,"Now live btrs are ");
967 dump_hard_reg_set (*btrs_live_in_range);
968 fprintf (dump_file, "\n");
971 FOR_EACH_EDGE (e, ei, bb->preds)
973 basic_block pred = e->src;
974 if (!bitmap_bit_p (live_range, pred->index))
975 *tos++ = pred;
980 free (worklist);
983 /* Return the most desirable target register that is not in
984 the set USED_BTRS. */
985 static int
986 choose_btr (HARD_REG_SET used_btrs)
988 int i;
990 if (!hard_reg_set_subset_p (all_btrs, used_btrs))
991 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
993 #ifdef REG_ALLOC_ORDER
994 int regno = reg_alloc_order[i];
995 #else
996 int regno = i;
997 #endif
998 if (TEST_HARD_REG_BIT (all_btrs, regno)
999 && !TEST_HARD_REG_BIT (used_btrs, regno))
1000 return regno;
1002 return -1;
1005 /* Calculate the set of basic blocks that contain the live range of
1006 the def/use web DEF.
1007 Also calculate the set of target registers that are live at time
1008 in this live range, but ignore the live range represented by DEF
1009 when calculating this set. */
1010 static void
1011 btr_def_live_range (btr_def def, HARD_REG_SET *btrs_live_in_range)
1013 if (!def->live_range)
1015 btr_user user;
1017 def->live_range = BITMAP_ALLOC (NULL);
1019 bitmap_set_bit (def->live_range, def->bb->index);
1020 COPY_HARD_REG_SET (*btrs_live_in_range,
1021 (flag_btr_bb_exclusive
1022 ? btrs_live : btrs_live_at_end)[def->bb->index]);
1024 for (user = def->uses; user != NULL; user = user->next)
1025 augment_live_range (def->live_range, btrs_live_in_range,
1026 def->bb, user->bb,
1027 (flag_btr_bb_exclusive
1028 || user->insn != BB_END (def->bb)
1029 || !JUMP_P (user->insn)));
1031 else
1033 /* def->live_range is accurate, but we need to recompute
1034 the set of target registers live over it, because migration
1035 of other PT instructions may have affected it.
1037 unsigned bb;
1038 unsigned def_bb = flag_btr_bb_exclusive ? -1 : def->bb->index;
1039 bitmap_iterator bi;
1041 CLEAR_HARD_REG_SET (*btrs_live_in_range);
1042 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
1044 IOR_HARD_REG_SET (*btrs_live_in_range,
1045 (def_bb == bb
1046 ? btrs_live_at_end : btrs_live) [bb]);
1049 if (!def->other_btr_uses_before_def &&
1050 !def->other_btr_uses_after_use)
1051 CLEAR_HARD_REG_BIT (*btrs_live_in_range, def->btr);
1054 /* Merge into the def/use web DEF any other def/use webs in the same
1055 group that are dominated by DEF, provided that there is a target
1056 register available to allocate to the merged web. */
1057 static void
1058 combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range)
1060 btr_def other_def;
1062 for (other_def = def->group->members;
1063 other_def != NULL;
1064 other_def = other_def->next_this_group)
1066 if (other_def != def
1067 && other_def->uses != NULL
1068 && ! other_def->has_ambiguous_use
1069 && dominated_by_p (CDI_DOMINATORS, other_def->bb, def->bb))
1071 /* def->bb dominates the other def, so def and other_def could
1072 be combined. */
1073 /* Merge their live ranges, and get the set of
1074 target registers live over the merged range. */
1075 int btr;
1076 HARD_REG_SET combined_btrs_live;
1077 bitmap combined_live_range = BITMAP_ALLOC (NULL);
1078 btr_user user;
1080 if (other_def->live_range == NULL)
1082 HARD_REG_SET dummy_btrs_live_in_range;
1083 btr_def_live_range (other_def, &dummy_btrs_live_in_range);
1085 COPY_HARD_REG_SET (combined_btrs_live, *btrs_live_in_range);
1086 bitmap_copy (combined_live_range, def->live_range);
1088 for (user = other_def->uses; user != NULL; user = user->next)
1089 augment_live_range (combined_live_range, &combined_btrs_live,
1090 def->bb, user->bb,
1091 (flag_btr_bb_exclusive
1092 || user->insn != BB_END (def->bb)
1093 || !JUMP_P (user->insn)));
1095 btr = choose_btr (combined_btrs_live);
1096 if (btr != -1)
1098 /* We can combine them. */
1099 if (dump_file)
1100 fprintf (dump_file,
1101 "Combining def in insn %d with def in insn %d\n",
1102 INSN_UID (other_def->insn), INSN_UID (def->insn));
1104 def->btr = btr;
1105 user = other_def->uses;
1106 while (user != NULL)
1108 btr_user next = user->next;
1110 user->next = def->uses;
1111 def->uses = user;
1112 user = next;
1114 /* Combining def/use webs can make target registers live
1115 after uses where they previously were not. This means
1116 some REG_DEAD notes may no longer be correct. We could
1117 be more precise about this if we looked at the combined
1118 live range, but here I just delete any REG_DEAD notes
1119 in case they are no longer correct. */
1120 for (user = def->uses; user != NULL; user = user->next)
1121 remove_note (user->insn,
1122 find_regno_note (user->insn, REG_DEAD,
1123 REGNO (user->use)));
1124 clear_btr_from_live_range (other_def);
1125 other_def->uses = NULL;
1126 bitmap_copy (def->live_range, combined_live_range);
1127 if (other_def->btr == btr && other_def->other_btr_uses_after_use)
1128 def->other_btr_uses_after_use = 1;
1129 COPY_HARD_REG_SET (*btrs_live_in_range, combined_btrs_live);
1131 /* Delete the old target register initialization. */
1132 delete_insn (other_def->insn);
1135 BITMAP_FREE (combined_live_range);
1140 /* Move the definition DEF from its current position to basic
1141 block NEW_DEF_BB, and modify it to use branch target register BTR.
1142 Delete the old defining insn, and insert a new one in NEW_DEF_BB.
1143 Update all reaching uses of DEF in the RTL to use BTR.
1144 If this new position means that other defs in the
1145 same group can be combined with DEF then combine them. */
1146 static void
1147 move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range,
1148 HARD_REG_SET *btrs_live_in_range)
1150 /* We can move the instruction.
1151 Set a target register in block NEW_DEF_BB to the value
1152 needed for this target register definition.
1153 Replace all uses of the old target register definition by
1154 uses of the new definition. Delete the old definition. */
1155 basic_block b = new_def_bb;
1156 rtx insp = BB_HEAD (b);
1157 rtx old_insn = def->insn;
1158 rtx src;
1159 rtx btr_rtx;
1160 rtx new_insn;
1161 enum machine_mode btr_mode;
1162 btr_user user;
1163 rtx set;
1165 if (dump_file)
1166 fprintf(dump_file, "migrating to basic block %d, using reg %d\n",
1167 new_def_bb->index, btr);
1169 clear_btr_from_live_range (def);
1170 def->btr = btr;
1171 def->bb = new_def_bb;
1172 def->luid = 0;
1173 def->cost = basic_block_freq (new_def_bb);
1174 bitmap_copy (def->live_range, live_range);
1175 combine_btr_defs (def, btrs_live_in_range);
1176 btr = def->btr;
1177 def->other_btr_uses_before_def
1178 = TEST_HARD_REG_BIT (btrs_live[b->index], btr) ? 1 : 0;
1179 add_btr_to_live_range (def, 1);
1180 if (LABEL_P (insp))
1181 insp = NEXT_INSN (insp);
1182 /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some
1183 optimizations can result in insp being both first and last insn of
1184 its basic block. */
1185 /* ?? some assertions to check that insp is sensible? */
1187 if (def->other_btr_uses_before_def)
1189 insp = BB_END (b);
1190 for (insp = BB_END (b); ! INSN_P (insp); insp = PREV_INSN (insp))
1191 gcc_assert (insp != BB_HEAD (b));
1193 if (JUMP_P (insp) || can_throw_internal (insp))
1194 insp = PREV_INSN (insp);
1197 set = single_set (old_insn);
1198 src = SET_SRC (set);
1199 btr_mode = GET_MODE (SET_DEST (set));
1200 btr_rtx = gen_rtx_REG (btr_mode, btr);
1202 new_insn = gen_move_insn (btr_rtx, src);
1204 /* Insert target register initialization at head of basic block. */
1205 def->insn = emit_insn_after (new_insn, insp);
1207 df_set_regs_ever_live (btr, true);
1209 if (dump_file)
1210 fprintf (dump_file, "New pt is insn %d, inserted after insn %d\n",
1211 INSN_UID (def->insn), INSN_UID (insp));
1213 /* Delete the old target register initialization. */
1214 delete_insn (old_insn);
1216 /* Replace each use of the old target register by a use of the new target
1217 register. */
1218 for (user = def->uses; user != NULL; user = user->next)
1220 /* Some extra work here to ensure consistent modes, because
1221 it seems that a target register REG rtx can be given a different
1222 mode depending on the context (surely that should not be
1223 the case?). */
1224 rtx replacement_rtx;
1225 if (GET_MODE (user->use) == GET_MODE (btr_rtx)
1226 || GET_MODE (user->use) == VOIDmode)
1227 replacement_rtx = btr_rtx;
1228 else
1229 replacement_rtx = gen_rtx_REG (GET_MODE (user->use), btr);
1230 validate_replace_rtx (user->use, replacement_rtx, user->insn);
1231 user->use = replacement_rtx;
1235 /* We anticipate intra-block scheduling to be done. See if INSN could move
1236 up within BB by N_INSNS. */
1237 static int
1238 can_move_up (const_basic_block bb, const_rtx insn, int n_insns)
1240 while (insn != BB_HEAD (bb) && n_insns > 0)
1242 insn = PREV_INSN (insn);
1243 /* ??? What if we have an anti-dependency that actually prevents the
1244 scheduler from doing the move? We'd like to re-allocate the register,
1245 but not necessarily put the load into another basic block. */
1246 if (INSN_P (insn))
1247 n_insns--;
1249 return n_insns <= 0;
1252 /* Attempt to migrate the target register definition DEF to an
1253 earlier point in the flowgraph.
1255 It is a precondition of this function that DEF is migratable:
1256 i.e. it has a constant source, and all uses are unambiguous.
1258 Only migrations that reduce the cost of DEF will be made.
1259 MIN_COST is the lower bound on the cost of the DEF after migration.
1260 If we migrate DEF so that its cost falls below MIN_COST,
1261 then we do not attempt to migrate further. The idea is that
1262 we migrate definitions in a priority order based on their cost,
1263 when the cost of this definition falls below MIN_COST, then
1264 there is another definition with cost == MIN_COST which now
1265 has a higher priority than this definition.
1267 Return nonzero if there may be benefit from attempting to
1268 migrate this DEF further (i.e. we have reduced the cost below
1269 MIN_COST, but we may be able to reduce it further).
1270 Return zero if no further migration is possible. */
1271 static int
1272 migrate_btr_def (btr_def def, int min_cost)
1274 bitmap live_range;
1275 HARD_REG_SET btrs_live_in_range;
1276 int btr_used_near_def = 0;
1277 int def_basic_block_freq;
1278 basic_block try;
1279 int give_up = 0;
1280 int def_moved = 0;
1281 btr_user user;
1282 int def_latency;
1284 if (dump_file)
1285 fprintf (dump_file,
1286 "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ",
1287 INSN_UID (def->insn), def->cost, min_cost);
1289 if (!def->group || def->has_ambiguous_use)
1290 /* These defs are not migratable. */
1292 if (dump_file)
1293 fprintf (dump_file, "it's not migratable\n");
1294 return 0;
1297 if (!def->uses)
1298 /* We have combined this def with another in the same group, so
1299 no need to consider it further.
1302 if (dump_file)
1303 fprintf (dump_file, "it's already combined with another pt\n");
1304 return 0;
1307 btr_def_live_range (def, &btrs_live_in_range);
1308 live_range = BITMAP_ALLOC (NULL);
1309 bitmap_copy (live_range, def->live_range);
1311 #ifdef INSN_SCHEDULING
1312 def_latency = insn_default_latency (def->insn) * issue_rate;
1313 #else
1314 def_latency = issue_rate;
1315 #endif
1317 for (user = def->uses; user != NULL; user = user->next)
1319 if (user->bb == def->bb
1320 && user->luid > def->luid
1321 && (def->luid + def_latency) > user->luid
1322 && ! can_move_up (def->bb, def->insn,
1323 (def->luid + def_latency) - user->luid))
1325 btr_used_near_def = 1;
1326 break;
1330 def_basic_block_freq = basic_block_freq (def->bb);
1332 for (try = get_immediate_dominator (CDI_DOMINATORS, def->bb);
1333 !give_up && try && try != ENTRY_BLOCK_PTR && def->cost >= min_cost;
1334 try = get_immediate_dominator (CDI_DOMINATORS, try))
1336 /* Try to move the instruction that sets the target register into
1337 basic block TRY. */
1338 int try_freq = basic_block_freq (try);
1339 edge_iterator ei;
1340 edge e;
1342 /* If TRY has abnormal edges, skip it. */
1343 FOR_EACH_EDGE (e, ei, try->succs)
1344 if (e->flags & EDGE_COMPLEX)
1345 break;
1346 if (e)
1347 continue;
1349 if (dump_file)
1350 fprintf (dump_file, "trying block %d ...", try->index);
1352 if (try_freq < def_basic_block_freq
1353 || (try_freq == def_basic_block_freq && btr_used_near_def))
1355 int btr;
1356 augment_live_range (live_range, &btrs_live_in_range, def->bb, try,
1357 flag_btr_bb_exclusive);
1358 if (dump_file)
1360 fprintf (dump_file, "Now btrs live in range are: ");
1361 dump_hard_reg_set (btrs_live_in_range);
1362 fprintf (dump_file, "\n");
1364 btr = choose_btr (btrs_live_in_range);
1365 if (btr != -1)
1367 move_btr_def (try, btr, def, live_range, &btrs_live_in_range);
1368 bitmap_copy(live_range, def->live_range);
1369 btr_used_near_def = 0;
1370 def_moved = 1;
1371 def_basic_block_freq = basic_block_freq (def->bb);
1373 else
1375 /* There are no free target registers available to move
1376 this far forward, so give up */
1377 give_up = 1;
1378 if (dump_file)
1379 fprintf (dump_file,
1380 "giving up because there are no free target registers\n");
1385 if (!def_moved)
1387 give_up = 1;
1388 if (dump_file)
1389 fprintf (dump_file, "failed to move\n");
1391 BITMAP_FREE (live_range);
1392 return !give_up;
1395 /* Attempt to move instructions that set target registers earlier
1396 in the flowgraph, away from their corresponding uses. */
1397 static void
1398 migrate_btr_defs (enum reg_class btr_class, int allow_callee_save)
1400 fibheap_t all_btr_defs = fibheap_new ();
1401 int reg;
1403 gcc_obstack_init (&migrate_btrl_obstack);
1404 if (dump_file)
1406 int i;
1408 for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
1410 basic_block bb = BASIC_BLOCK (i);
1411 fprintf(dump_file,
1412 "Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC
1413 " loop-depth = %d idom = %d\n",
1414 i, (HOST_WIDEST_INT) bb->count, bb->loop_depth,
1415 get_immediate_dominator (CDI_DOMINATORS, bb)->index);
1419 CLEAR_HARD_REG_SET (all_btrs);
1420 for (first_btr = -1, reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
1421 if (TEST_HARD_REG_BIT (reg_class_contents[(int) btr_class], reg)
1422 && (allow_callee_save || call_used_regs[reg]
1423 || df_regs_ever_live_p (reg)))
1425 SET_HARD_REG_BIT (all_btrs, reg);
1426 last_btr = reg;
1427 if (first_btr < 0)
1428 first_btr = reg;
1431 btrs_live = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET));
1432 btrs_live_at_end = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET));
1434 build_btr_def_use_webs (all_btr_defs);
1436 while (!fibheap_empty (all_btr_defs))
1438 btr_def def = fibheap_extract_min (all_btr_defs);
1439 int min_cost = -fibheap_min_key (all_btr_defs);
1440 if (migrate_btr_def (def, min_cost))
1442 fibheap_insert (all_btr_defs, -def->cost, (void *) def);
1443 if (dump_file)
1445 fprintf (dump_file,
1446 "Putting insn %d back on queue with priority %d\n",
1447 INSN_UID (def->insn), def->cost);
1450 else
1451 BITMAP_FREE (def->live_range);
1454 free (btrs_live);
1455 free (btrs_live_at_end);
1456 obstack_free (&migrate_btrl_obstack, NULL);
1457 fibheap_delete (all_btr_defs);
1460 static void
1461 branch_target_load_optimize (bool after_prologue_epilogue_gen)
1463 enum reg_class class = targetm.branch_target_register_class ();
1464 if (class != NO_REGS)
1466 /* Initialize issue_rate. */
1467 if (targetm.sched.issue_rate)
1468 issue_rate = targetm.sched.issue_rate ();
1469 else
1470 issue_rate = 1;
1472 if (!after_prologue_epilogue_gen)
1474 /* Build the CFG for migrate_btr_defs. */
1475 #if 1
1476 /* This may or may not be needed, depending on where we
1477 run this phase. */
1478 cleanup_cfg (optimize ? CLEANUP_EXPENSIVE : 0);
1479 #endif
1481 df_analyze ();
1484 /* Dominator info is also needed for migrate_btr_def. */
1485 calculate_dominance_info (CDI_DOMINATORS);
1486 migrate_btr_defs (class,
1487 (targetm.branch_target_register_callee_saved
1488 (after_prologue_epilogue_gen)));
1490 free_dominance_info (CDI_DOMINATORS);
1494 static bool
1495 gate_handle_branch_target_load_optimize1 (void)
1497 return flag_branch_target_load_optimize;
1501 static unsigned int
1502 rest_of_handle_branch_target_load_optimize1 (void)
1504 branch_target_load_optimize (epilogue_completed);
1505 return 0;
1508 struct tree_opt_pass pass_branch_target_load_optimize1 =
1510 "btl1", /* name */
1511 gate_handle_branch_target_load_optimize1, /* gate */
1512 rest_of_handle_branch_target_load_optimize1, /* execute */
1513 NULL, /* sub */
1514 NULL, /* next */
1515 0, /* static_pass_number */
1516 0, /* tv_id */
1517 0, /* properties_required */
1518 0, /* properties_provided */
1519 0, /* properties_destroyed */
1520 0, /* todo_flags_start */
1521 TODO_dump_func |
1522 TODO_verify_rtl_sharing |
1523 TODO_ggc_collect, /* todo_flags_finish */
1524 'd' /* letter */
1527 static bool
1528 gate_handle_branch_target_load_optimize2 (void)
1530 return (optimize > 0 && flag_branch_target_load_optimize2);
1534 static unsigned int
1535 rest_of_handle_branch_target_load_optimize2 (void)
1537 static int warned = 0;
1539 /* Leave this a warning for now so that it is possible to experiment
1540 with running this pass twice. In 3.6, we should either make this
1541 an error, or use separate dump files. */
1542 if (flag_branch_target_load_optimize
1543 && flag_branch_target_load_optimize2
1544 && !warned)
1546 warning (0, "branch target register load optimization is not intended "
1547 "to be run twice");
1549 warned = 1;
1552 branch_target_load_optimize (epilogue_completed);
1553 return 0;
1556 struct tree_opt_pass pass_branch_target_load_optimize2 =
1558 "btl2", /* name */
1559 gate_handle_branch_target_load_optimize2, /* gate */
1560 rest_of_handle_branch_target_load_optimize2, /* execute */
1561 NULL, /* sub */
1562 NULL, /* next */
1563 0, /* static_pass_number */
1564 0, /* tv_id */
1565 0, /* properties_required */
1566 0, /* properties_provided */
1567 0, /* properties_destroyed */
1568 0, /* todo_flags_start */
1569 TODO_dump_func |
1570 TODO_ggc_collect, /* todo_flags_finish */
1571 'd' /* letter */