gcc/
[official-gcc.git] / gcc / bt-load.c
blob9c1d04e1173997d2530813a777cd4461923103e6
2 /* Perform branch target register load optimizations.
3 Copyright (C) 2001-2015 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 "target.h"
29 #include "symtab.h"
30 #include "function.h"
31 #include "flags.h"
32 #include "alias.h"
33 #include "tree.h"
34 #include "insn-config.h"
35 #include "expmed.h"
36 #include "dojump.h"
37 #include "explow.h"
38 #include "calls.h"
39 #include "emit-rtl.h"
40 #include "varasm.h"
41 #include "stmt.h"
42 #include "expr.h"
43 #include "insn-attr.h"
44 #include "except.h"
45 #include "tm_p.h"
46 #include "diagnostic-core.h"
47 #include "tree-pass.h"
48 #include "recog.h"
49 #include "dominance.h"
50 #include "cfg.h"
51 #include "cfgrtl.h"
52 #include "cfganal.h"
53 #include "cfgcleanup.h"
54 #include "predict.h"
55 #include "basic-block.h"
56 #include "df.h"
57 #include "cfgloop.h"
58 #include "rtl-iter.h"
59 #include "fibonacci_heap.h"
61 /* Target register optimizations - these are performed after reload. */
63 typedef struct btr_def_group_s
65 struct btr_def_group_s *next;
66 rtx src;
67 struct btr_def_s *members;
68 } *btr_def_group;
70 typedef struct btr_user_s
72 struct btr_user_s *next;
73 basic_block bb;
74 int luid;
75 rtx_insn *insn;
76 /* If INSN has a single use of a single branch register, then
77 USE points to it within INSN. If there is more than
78 one branch register use, or the use is in some way ambiguous,
79 then USE is NULL. */
80 rtx use;
81 int n_reaching_defs;
82 int first_reaching_def;
83 char other_use_this_block;
84 } *btr_user;
86 /* btr_def structs appear on three lists:
87 1. A list of all btr_def structures (head is
88 ALL_BTR_DEFS, linked by the NEXT field).
89 2. A list of branch reg definitions per basic block (head is
90 BB_BTR_DEFS[i], linked by the NEXT_THIS_BB field).
91 3. A list of all branch reg definitions belonging to the same
92 group (head is in a BTR_DEF_GROUP struct, linked by
93 NEXT_THIS_GROUP field). */
95 typedef struct btr_def_s
97 struct btr_def_s *next_this_bb;
98 struct btr_def_s *next_this_group;
99 basic_block bb;
100 int luid;
101 rtx_insn *insn;
102 int btr;
103 int cost;
104 /* For a branch register setting insn that has a constant
105 source (i.e. a label), group links together all the
106 insns with the same source. For other branch register
107 setting insns, group is NULL. */
108 btr_def_group group;
109 btr_user uses;
110 /* If this def has a reaching use which is not a simple use
111 in a branch instruction, then has_ambiguous_use will be true,
112 and we will not attempt to migrate this definition. */
113 char has_ambiguous_use;
114 /* live_range is an approximation to the true live range for this
115 def/use web, because it records the set of blocks that contain
116 the live range. There could be other live ranges for the same
117 branch register in that set of blocks, either in the block
118 containing the def (before the def), or in a block containing
119 a use (after the use). If there are such other live ranges, then
120 other_btr_uses_before_def or other_btr_uses_after_use must be set true
121 as appropriate. */
122 char other_btr_uses_before_def;
123 char other_btr_uses_after_use;
124 /* We set own_end when we have moved a definition into a dominator.
125 Thus, when a later combination removes this definition again, we know
126 to clear out trs_live_at_end again. */
127 char own_end;
128 bitmap live_range;
129 } *btr_def;
131 typedef fibonacci_heap <long, btr_def_s> btr_heap_t;
132 typedef fibonacci_node <long, btr_def_s> btr_heap_node_t;
134 static int issue_rate;
136 static int basic_block_freq (const_basic_block);
137 static int insn_sets_btr_p (const rtx_insn *, int, int *);
138 static void find_btr_def_group (btr_def_group *, btr_def);
139 static btr_def add_btr_def (btr_heap_t *, basic_block, int, rtx_insn *,
140 unsigned int, int, btr_def_group *);
141 static btr_user new_btr_user (basic_block, int, rtx_insn *);
142 static void dump_hard_reg_set (HARD_REG_SET);
143 static void dump_btrs_live (int);
144 static void note_other_use_this_block (unsigned int, btr_user);
145 static void compute_defs_uses_and_gen (btr_heap_t *, btr_def *,btr_user *,
146 sbitmap *, sbitmap *, HARD_REG_SET *);
147 static void compute_kill (sbitmap *, sbitmap *, HARD_REG_SET *);
148 static void compute_out (sbitmap *bb_out, sbitmap *, sbitmap *, int);
149 static void link_btr_uses (btr_def *, btr_user *, sbitmap *, sbitmap *, int);
150 static void build_btr_def_use_webs (btr_heap_t *);
151 static int block_at_edge_of_live_range_p (int, btr_def);
152 static void clear_btr_from_live_range (btr_def def);
153 static void add_btr_to_live_range (btr_def, int);
154 static void augment_live_range (bitmap, HARD_REG_SET *, basic_block,
155 basic_block, int);
156 static int choose_btr (HARD_REG_SET);
157 static void combine_btr_defs (btr_def, HARD_REG_SET *);
158 static void btr_def_live_range (btr_def, HARD_REG_SET *);
159 static void move_btr_def (basic_block, int, btr_def, bitmap, HARD_REG_SET *);
160 static int migrate_btr_def (btr_def, int);
161 static void migrate_btr_defs (enum reg_class, int);
162 static int can_move_up (const_basic_block, const rtx_insn *, int);
163 static void note_btr_set (rtx, const_rtx, void *);
165 /* The following code performs code motion of target load instructions
166 (instructions that set branch target registers), to move them
167 forward away from the branch instructions and out of loops (or,
168 more generally, from a more frequently executed place to a less
169 frequently executed place).
170 Moving target load instructions further in front of the branch
171 instruction that uses the target register value means that the hardware
172 has a better chance of preloading the instructions at the branch
173 target by the time the branch is reached. This avoids bubbles
174 when a taken branch needs to flush out the pipeline.
175 Moving target load instructions out of loops means they are executed
176 less frequently. */
178 /* An obstack to hold the def-use web data structures built up for
179 migrating branch target load instructions. */
180 static struct obstack migrate_btrl_obstack;
182 /* Array indexed by basic block number, giving the set of registers
183 live in that block. */
184 static HARD_REG_SET *btrs_live;
186 /* Array indexed by basic block number, giving the set of registers live at
187 the end of that block, including any uses by a final jump insn, if any. */
188 static HARD_REG_SET *btrs_live_at_end;
190 /* Set of all target registers that we are willing to allocate. */
191 static HARD_REG_SET all_btrs;
193 /* Provide lower and upper bounds for target register numbers, so that
194 we don't need to search through all the hard registers all the time. */
195 static int first_btr, last_btr;
199 /* Return an estimate of the frequency of execution of block bb. */
200 static int
201 basic_block_freq (const_basic_block bb)
203 return bb->frequency;
206 /* If X references (sets or reads) any branch target register, return one
207 such register. If EXCLUDEP is set, disregard any references within
208 that location. */
209 static rtx *
210 find_btr_use (rtx x, rtx *excludep = 0)
212 subrtx_ptr_iterator::array_type array;
213 FOR_EACH_SUBRTX_PTR (iter, array, &x, NONCONST)
215 rtx *loc = *iter;
216 if (loc == excludep)
217 iter.skip_subrtxes ();
218 else
220 const_rtx x = *loc;
221 if (REG_P (x)
222 && overlaps_hard_reg_set_p (all_btrs, GET_MODE (x), REGNO (x)))
223 return loc;
226 return 0;
229 /* Return true if insn is an instruction that sets a target register.
230 if CHECK_CONST is true, only return true if the source is constant.
231 If such a set is found and REGNO is nonzero, assign the register number
232 of the destination register to *REGNO. */
233 static int
234 insn_sets_btr_p (const rtx_insn *insn, int check_const, int *regno)
236 rtx set;
238 if (NONJUMP_INSN_P (insn)
239 && (set = single_set (insn)))
241 rtx dest = SET_DEST (set);
242 rtx src = SET_SRC (set);
244 if (GET_CODE (dest) == SUBREG)
245 dest = XEXP (dest, 0);
247 if (REG_P (dest)
248 && TEST_HARD_REG_BIT (all_btrs, REGNO (dest)))
250 gcc_assert (!find_btr_use (src));
252 if (!check_const || CONSTANT_P (src))
254 if (regno)
255 *regno = REGNO (dest);
256 return 1;
260 return 0;
263 /* Find the group that the target register definition DEF belongs
264 to in the list starting with *ALL_BTR_DEF_GROUPS. If no such
265 group exists, create one. Add def to the group. */
266 static void
267 find_btr_def_group (btr_def_group *all_btr_def_groups, btr_def def)
269 if (insn_sets_btr_p (def->insn, 1, NULL))
271 btr_def_group this_group;
272 rtx def_src = SET_SRC (single_set (def->insn));
274 /* ?? This linear search is an efficiency concern, particularly
275 as the search will almost always fail to find a match. */
276 for (this_group = *all_btr_def_groups;
277 this_group != NULL;
278 this_group = this_group->next)
279 if (rtx_equal_p (def_src, this_group->src))
280 break;
282 if (!this_group)
284 this_group = XOBNEW (&migrate_btrl_obstack, struct btr_def_group_s);
285 this_group->src = def_src;
286 this_group->members = NULL;
287 this_group->next = *all_btr_def_groups;
288 *all_btr_def_groups = this_group;
290 def->group = this_group;
291 def->next_this_group = this_group->members;
292 this_group->members = def;
294 else
295 def->group = NULL;
298 /* Create a new target register definition structure, for a definition in
299 block BB, instruction INSN, and insert it into ALL_BTR_DEFS. Return
300 the new definition. */
301 static btr_def
302 add_btr_def (btr_heap_t *all_btr_defs, basic_block bb, int insn_luid,
303 rtx_insn *insn,
304 unsigned int dest_reg, int other_btr_uses_before_def,
305 btr_def_group *all_btr_def_groups)
307 btr_def this_def = XOBNEW (&migrate_btrl_obstack, struct btr_def_s);
308 this_def->bb = bb;
309 this_def->luid = insn_luid;
310 this_def->insn = insn;
311 this_def->btr = dest_reg;
312 this_def->cost = basic_block_freq (bb);
313 this_def->has_ambiguous_use = 0;
314 this_def->other_btr_uses_before_def = other_btr_uses_before_def;
315 this_def->other_btr_uses_after_use = 0;
316 this_def->next_this_bb = NULL;
317 this_def->next_this_group = NULL;
318 this_def->uses = NULL;
319 this_def->live_range = NULL;
320 find_btr_def_group (all_btr_def_groups, this_def);
322 all_btr_defs->insert (-this_def->cost, this_def);
324 if (dump_file)
325 fprintf (dump_file,
326 "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n",
327 dest_reg, bb->index, INSN_UID (insn),
328 (this_def->group ? "" : ":not const"), this_def->cost);
330 return this_def;
333 /* Create a new target register user structure, for a use in block BB,
334 instruction INSN. Return the new user. */
335 static btr_user
336 new_btr_user (basic_block bb, int insn_luid, rtx_insn *insn)
338 /* This instruction reads target registers. We need
339 to decide whether we can replace all target register
340 uses easily.
342 rtx *usep = find_btr_use (PATTERN (insn));
343 rtx use;
344 btr_user user = NULL;
346 if (usep)
348 int unambiguous_single_use;
350 /* We want to ensure that USE is the only use of a target
351 register in INSN, so that we know that to rewrite INSN to use
352 a different target register, all we have to do is replace USE. */
353 unambiguous_single_use = !find_btr_use (PATTERN (insn), usep);
354 if (!unambiguous_single_use)
355 usep = NULL;
357 use = usep ? *usep : NULL_RTX;
358 user = XOBNEW (&migrate_btrl_obstack, struct btr_user_s);
359 user->bb = bb;
360 user->luid = insn_luid;
361 user->insn = insn;
362 user->use = use;
363 user->other_use_this_block = 0;
364 user->next = NULL;
365 user->n_reaching_defs = 0;
366 user->first_reaching_def = -1;
368 if (dump_file)
370 fprintf (dump_file, "Uses target reg: { bb %d, insn %d }",
371 bb->index, INSN_UID (insn));
373 if (user->use)
374 fprintf (dump_file, ": unambiguous use of reg %d\n",
375 REGNO (user->use));
378 return user;
381 /* Write the contents of S to the dump file. */
382 static void
383 dump_hard_reg_set (HARD_REG_SET s)
385 int reg;
386 for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
387 if (TEST_HARD_REG_BIT (s, reg))
388 fprintf (dump_file, " %d", reg);
391 /* Write the set of target regs live in block BB to the dump file. */
392 static void
393 dump_btrs_live (int bb)
395 fprintf (dump_file, "BB%d live:", bb);
396 dump_hard_reg_set (btrs_live[bb]);
397 fprintf (dump_file, "\n");
400 /* REGNO is the number of a branch target register that is being used or
401 set. USERS_THIS_BB is a list of preceding branch target register users;
402 If any of them use the same register, set their other_use_this_block
403 flag. */
404 static void
405 note_other_use_this_block (unsigned int regno, btr_user users_this_bb)
407 btr_user user;
409 for (user = users_this_bb; user != NULL; user = user->next)
410 if (user->use && REGNO (user->use) == regno)
411 user->other_use_this_block = 1;
414 typedef struct {
415 btr_user users_this_bb;
416 HARD_REG_SET btrs_written_in_block;
417 HARD_REG_SET btrs_live_in_block;
418 sbitmap bb_gen;
419 sbitmap *btr_defset;
420 } defs_uses_info;
422 /* Called via note_stores or directly to register stores into /
423 clobbers of a branch target register DEST that are not recognized as
424 straightforward definitions. DATA points to information about the
425 current basic block that needs updating. */
426 static void
427 note_btr_set (rtx dest, const_rtx set ATTRIBUTE_UNUSED, void *data)
429 defs_uses_info *info = (defs_uses_info *) data;
430 int regno, end_regno;
432 if (!REG_P (dest))
433 return;
434 regno = REGNO (dest);
435 end_regno = END_REGNO (dest);
436 for (; regno < end_regno; regno++)
437 if (TEST_HARD_REG_BIT (all_btrs, regno))
439 note_other_use_this_block (regno, info->users_this_bb);
440 SET_HARD_REG_BIT (info->btrs_written_in_block, regno);
441 SET_HARD_REG_BIT (info->btrs_live_in_block, regno);
442 bitmap_and_compl (info->bb_gen, info->bb_gen,
443 info->btr_defset[regno - first_btr]);
447 static void
448 compute_defs_uses_and_gen (btr_heap_t *all_btr_defs, btr_def *def_array,
449 btr_user *use_array, sbitmap *btr_defset,
450 sbitmap *bb_gen, HARD_REG_SET *btrs_written)
452 /* Scan the code building up the set of all defs and all uses.
453 For each target register, build the set of defs of that register.
454 For each block, calculate the set of target registers
455 written in that block.
456 Also calculate the set of btrs ever live in that block.
458 int i;
459 int insn_luid = 0;
460 btr_def_group all_btr_def_groups = NULL;
461 defs_uses_info info;
463 bitmap_vector_clear (bb_gen, last_basic_block_for_fn (cfun));
464 for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++)
466 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
467 int reg;
468 btr_def defs_this_bb = NULL;
469 rtx_insn *insn;
470 rtx_insn *last;
471 int can_throw = 0;
473 info.users_this_bb = NULL;
474 info.bb_gen = bb_gen[i];
475 info.btr_defset = btr_defset;
477 CLEAR_HARD_REG_SET (info.btrs_live_in_block);
478 CLEAR_HARD_REG_SET (info.btrs_written_in_block);
479 for (reg = first_btr; reg <= last_btr; reg++)
480 if (TEST_HARD_REG_BIT (all_btrs, reg)
481 && REGNO_REG_SET_P (df_get_live_in (bb), reg))
482 SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
484 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
485 insn != last;
486 insn = NEXT_INSN (insn), insn_luid++)
488 if (INSN_P (insn))
490 int regno;
491 int insn_uid = INSN_UID (insn);
493 if (insn_sets_btr_p (insn, 0, &regno))
495 btr_def def = add_btr_def (
496 all_btr_defs, bb, insn_luid, insn, regno,
497 TEST_HARD_REG_BIT (info.btrs_live_in_block, regno),
498 &all_btr_def_groups);
500 def_array[insn_uid] = def;
501 SET_HARD_REG_BIT (info.btrs_written_in_block, regno);
502 SET_HARD_REG_BIT (info.btrs_live_in_block, regno);
503 bitmap_and_compl (bb_gen[i], bb_gen[i],
504 btr_defset[regno - first_btr]);
505 bitmap_set_bit (bb_gen[i], insn_uid);
506 def->next_this_bb = defs_this_bb;
507 defs_this_bb = def;
508 bitmap_set_bit (btr_defset[regno - first_btr], insn_uid);
509 note_other_use_this_block (regno, info.users_this_bb);
511 /* Check for the blockage emitted by expand_nl_goto_receiver. */
512 else if (cfun->has_nonlocal_label
513 && GET_CODE (PATTERN (insn)) == UNSPEC_VOLATILE)
515 btr_user user;
517 /* Do the equivalent of calling note_other_use_this_block
518 for every target register. */
519 for (user = info.users_this_bb; user != NULL;
520 user = user->next)
521 if (user->use)
522 user->other_use_this_block = 1;
523 IOR_HARD_REG_SET (info.btrs_written_in_block, all_btrs);
524 IOR_HARD_REG_SET (info.btrs_live_in_block, all_btrs);
525 bitmap_clear (info.bb_gen);
527 else
529 if (find_btr_use (PATTERN (insn)))
531 btr_user user = new_btr_user (bb, insn_luid, insn);
533 use_array[insn_uid] = user;
534 if (user->use)
535 SET_HARD_REG_BIT (info.btrs_live_in_block,
536 REGNO (user->use));
537 else
539 int reg;
540 for (reg = first_btr; reg <= last_btr; reg++)
541 if (TEST_HARD_REG_BIT (all_btrs, reg)
542 && refers_to_regno_p (reg, user->insn))
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 (ANY_RETURN_P (XVECEXP (pat, 0, i)))
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, insn))
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 bitmap_vector_clear (bb_kill, last_basic_block_for_fn (cfun));
624 for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); 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 bitmap_ior (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 < last_basic_block_for_fn (cfun); i++)
648 bitmap_copy (bb_out[i], bb_gen[i]);
650 changed = 1;
651 while (changed)
653 changed = 0;
654 for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++)
656 bitmap_union_of_preds (bb_in, bb_out, BASIC_BLOCK_FOR_FN (cfun, i));
657 changed |= bitmap_ior_and_compl (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 < last_basic_block_for_fn (cfun); i++)
675 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
676 rtx_insn *insn;
677 rtx_insn *last;
679 bitmap_union_of_preds (reaching_defs, bb_out, BASIC_BLOCK_FOR_FN (cfun, 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 bitmap_and_compl (reaching_defs, reaching_defs,
695 btr_defset[def->btr - first_btr]);
696 bitmap_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 bitmap_and (
708 reaching_defs_of_reg,
709 reaching_defs,
710 btr_defset[REGNO (user->use) - first_btr]);
711 else
713 int reg;
715 bitmap_clear (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, user->insn))
719 bitmap_or_and (reaching_defs_of_reg,
720 reaching_defs_of_reg,
721 reaching_defs,
722 btr_defset[reg - first_btr]);
724 EXECUTE_IF_SET_IN_BITMAP (reaching_defs_of_reg, 0, uid, sbi)
726 btr_def def = def_array[uid];
728 /* We now know that def reaches user. */
730 if (dump_file)
731 fprintf (dump_file,
732 "Def in insn %d reaches use in insn %d\n",
733 uid, insn_uid);
735 user->n_reaching_defs++;
736 if (!user->use)
737 def->has_ambiguous_use = 1;
738 if (user->first_reaching_def != -1)
739 { /* There is more than one reaching def. This is
740 a rare case, so just give up on this def/use
741 web when it occurs. */
742 def->has_ambiguous_use = 1;
743 def_array[user->first_reaching_def]
744 ->has_ambiguous_use = 1;
745 if (dump_file)
746 fprintf (dump_file,
747 "(use %d has multiple reaching defs)\n",
748 insn_uid);
750 else
751 user->first_reaching_def = uid;
752 if (user->other_use_this_block)
753 def->other_btr_uses_after_use = 1;
754 user->next = def->uses;
755 def->uses = user;
757 sbitmap_free (reaching_defs_of_reg);
760 if (CALL_P (insn))
762 int regno;
764 for (regno = first_btr; regno <= last_btr; regno++)
765 if (TEST_HARD_REG_BIT (all_btrs, regno)
766 && TEST_HARD_REG_BIT (call_used_reg_set, regno))
767 bitmap_and_compl (reaching_defs, reaching_defs,
768 btr_defset[regno - first_btr]);
773 sbitmap_free (reaching_defs);
776 static void
777 build_btr_def_use_webs (btr_heap_t *all_btr_defs)
779 const int max_uid = get_max_uid ();
780 btr_def *def_array = XCNEWVEC (btr_def, max_uid);
781 btr_user *use_array = XCNEWVEC (btr_user, max_uid);
782 sbitmap *btr_defset = sbitmap_vector_alloc (
783 (last_btr - first_btr) + 1, max_uid);
784 sbitmap *bb_gen = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
785 max_uid);
786 HARD_REG_SET *btrs_written = XCNEWVEC (HARD_REG_SET,
787 last_basic_block_for_fn (cfun));
788 sbitmap *bb_kill;
789 sbitmap *bb_out;
791 bitmap_vector_clear (btr_defset, (last_btr - first_btr) + 1);
793 compute_defs_uses_and_gen (all_btr_defs, def_array, use_array, btr_defset,
794 bb_gen, btrs_written);
796 bb_kill = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), max_uid);
797 compute_kill (bb_kill, btr_defset, btrs_written);
798 free (btrs_written);
800 bb_out = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), max_uid);
801 compute_out (bb_out, bb_gen, bb_kill, max_uid);
803 sbitmap_vector_free (bb_gen);
804 sbitmap_vector_free (bb_kill);
806 link_btr_uses (def_array, use_array, bb_out, btr_defset, max_uid);
808 sbitmap_vector_free (bb_out);
809 sbitmap_vector_free (btr_defset);
810 free (use_array);
811 free (def_array);
814 /* Return true if basic block BB contains the start or end of the
815 live range of the definition DEF, AND there are other live
816 ranges of the same target register that include BB. */
817 static int
818 block_at_edge_of_live_range_p (int bb, btr_def def)
820 if (def->other_btr_uses_before_def
821 && BASIC_BLOCK_FOR_FN (cfun, bb) == def->bb)
822 return 1;
823 else if (def->other_btr_uses_after_use)
825 btr_user user;
826 for (user = def->uses; user != NULL; user = user->next)
827 if (BASIC_BLOCK_FOR_FN (cfun, bb) == user->bb)
828 return 1;
830 return 0;
833 /* We are removing the def/use web DEF. The target register
834 used in this web is therefore no longer live in the live range
835 of this web, so remove it from the live set of all basic blocks
836 in the live range of the web.
837 Blocks at the boundary of the live range may contain other live
838 ranges for the same target register, so we have to be careful
839 to remove the target register from the live set of these blocks
840 only if they do not contain other live ranges for the same register. */
841 static void
842 clear_btr_from_live_range (btr_def def)
844 unsigned bb;
845 bitmap_iterator bi;
847 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
849 if ((!def->other_btr_uses_before_def
850 && !def->other_btr_uses_after_use)
851 || !block_at_edge_of_live_range_p (bb, def))
853 CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr);
854 CLEAR_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
855 if (dump_file)
856 dump_btrs_live (bb);
859 if (def->own_end)
860 CLEAR_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr);
864 /* We are adding the def/use web DEF. Add the target register used
865 in this web to the live set of all of the basic blocks that contain
866 the live range of the web.
867 If OWN_END is set, also show that the register is live from our
868 definitions at the end of the basic block where it is defined. */
869 static void
870 add_btr_to_live_range (btr_def def, int own_end)
872 unsigned bb;
873 bitmap_iterator bi;
875 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
877 SET_HARD_REG_BIT (btrs_live[bb], def->btr);
878 SET_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
879 if (dump_file)
880 dump_btrs_live (bb);
882 if (own_end)
884 SET_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr);
885 def->own_end = 1;
889 /* Update a live range to contain the basic block NEW_BLOCK, and all
890 blocks on paths between the existing live range and NEW_BLOCK.
891 HEAD is a block contained in the existing live range that dominates
892 all other blocks in the existing live range.
893 Also add to the set BTRS_LIVE_IN_RANGE all target registers that
894 are live in the blocks that we add to the live range.
895 If FULL_RANGE is set, include the full live range of NEW_BB;
896 otherwise, if NEW_BB dominates HEAD_BB, only add registers that
897 are life at the end of NEW_BB for NEW_BB itself.
898 It is a precondition that either NEW_BLOCK dominates HEAD,or
899 HEAD dom NEW_BLOCK. This is used to speed up the
900 implementation of this function. */
901 static void
902 augment_live_range (bitmap live_range, HARD_REG_SET *btrs_live_in_range,
903 basic_block head_bb, basic_block new_bb, int full_range)
905 basic_block *worklist, *tos;
907 tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1);
909 if (dominated_by_p (CDI_DOMINATORS, new_bb, head_bb))
911 if (new_bb == head_bb)
913 if (full_range)
914 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_bb->index]);
915 free (tos);
916 return;
918 *tos++ = new_bb;
920 else
922 edge e;
923 edge_iterator ei;
924 int new_block = new_bb->index;
926 gcc_assert (dominated_by_p (CDI_DOMINATORS, head_bb, new_bb));
928 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[head_bb->index]);
929 bitmap_set_bit (live_range, new_block);
930 /* A previous btr migration could have caused a register to be
931 live just at the end of new_block which we need in full, so
932 use trs_live_at_end even if full_range is set. */
933 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live_at_end[new_block]);
934 if (full_range)
935 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]);
936 if (dump_file)
938 fprintf (dump_file,
939 "Adding end of block %d and rest of %d to live range\n",
940 new_block, head_bb->index);
941 fprintf (dump_file,"Now live btrs are ");
942 dump_hard_reg_set (*btrs_live_in_range);
943 fprintf (dump_file, "\n");
945 FOR_EACH_EDGE (e, ei, head_bb->preds)
946 *tos++ = e->src;
949 while (tos != worklist)
951 basic_block bb = *--tos;
952 if (!bitmap_bit_p (live_range, bb->index))
954 edge e;
955 edge_iterator ei;
957 bitmap_set_bit (live_range, bb->index);
958 IOR_HARD_REG_SET (*btrs_live_in_range,
959 btrs_live[bb->index]);
960 /* A previous btr migration could have caused a register to be
961 live just at the end of a block which we need in full. */
962 IOR_HARD_REG_SET (*btrs_live_in_range,
963 btrs_live_at_end[bb->index]);
964 if (dump_file)
966 fprintf (dump_file,
967 "Adding block %d to live range\n", bb->index);
968 fprintf (dump_file,"Now live btrs are ");
969 dump_hard_reg_set (*btrs_live_in_range);
970 fprintf (dump_file, "\n");
973 FOR_EACH_EDGE (e, ei, bb->preds)
975 basic_block pred = e->src;
976 if (!bitmap_bit_p (live_range, pred->index))
977 *tos++ = pred;
982 free (worklist);
985 /* Return the most desirable target register that is not in
986 the set USED_BTRS. */
987 static int
988 choose_btr (HARD_REG_SET used_btrs)
990 int i;
992 if (!hard_reg_set_subset_p (all_btrs, used_btrs))
993 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
995 #ifdef REG_ALLOC_ORDER
996 int regno = reg_alloc_order[i];
997 #else
998 int regno = i;
999 #endif
1000 if (TEST_HARD_REG_BIT (all_btrs, regno)
1001 && !TEST_HARD_REG_BIT (used_btrs, regno))
1002 return regno;
1004 return -1;
1007 /* Calculate the set of basic blocks that contain the live range of
1008 the def/use web DEF.
1009 Also calculate the set of target registers that are live at time
1010 in this live range, but ignore the live range represented by DEF
1011 when calculating this set. */
1012 static void
1013 btr_def_live_range (btr_def def, HARD_REG_SET *btrs_live_in_range)
1015 if (!def->live_range)
1017 btr_user user;
1019 def->live_range = BITMAP_ALLOC (NULL);
1021 bitmap_set_bit (def->live_range, def->bb->index);
1022 COPY_HARD_REG_SET (*btrs_live_in_range,
1023 (flag_btr_bb_exclusive
1024 ? btrs_live : btrs_live_at_end)[def->bb->index]);
1026 for (user = def->uses; user != NULL; user = user->next)
1027 augment_live_range (def->live_range, btrs_live_in_range,
1028 def->bb, user->bb,
1029 (flag_btr_bb_exclusive
1030 || user->insn != BB_END (def->bb)
1031 || !JUMP_P (user->insn)));
1033 else
1035 /* def->live_range is accurate, but we need to recompute
1036 the set of target registers live over it, because migration
1037 of other PT instructions may have affected it.
1039 unsigned bb;
1040 unsigned def_bb = flag_btr_bb_exclusive ? -1 : def->bb->index;
1041 bitmap_iterator bi;
1043 CLEAR_HARD_REG_SET (*btrs_live_in_range);
1044 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
1046 IOR_HARD_REG_SET (*btrs_live_in_range,
1047 (def_bb == bb
1048 ? btrs_live_at_end : btrs_live) [bb]);
1051 if (!def->other_btr_uses_before_def &&
1052 !def->other_btr_uses_after_use)
1053 CLEAR_HARD_REG_BIT (*btrs_live_in_range, def->btr);
1056 /* Merge into the def/use web DEF any other def/use webs in the same
1057 group that are dominated by DEF, provided that there is a target
1058 register available to allocate to the merged web. */
1059 static void
1060 combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range)
1062 btr_def other_def;
1064 for (other_def = def->group->members;
1065 other_def != NULL;
1066 other_def = other_def->next_this_group)
1068 if (other_def != def
1069 && other_def->uses != NULL
1070 && ! other_def->has_ambiguous_use
1071 && dominated_by_p (CDI_DOMINATORS, other_def->bb, def->bb))
1073 /* def->bb dominates the other def, so def and other_def could
1074 be combined. */
1075 /* Merge their live ranges, and get the set of
1076 target registers live over the merged range. */
1077 int btr;
1078 HARD_REG_SET combined_btrs_live;
1079 bitmap combined_live_range = BITMAP_ALLOC (NULL);
1080 btr_user user;
1082 if (other_def->live_range == NULL)
1084 HARD_REG_SET dummy_btrs_live_in_range;
1085 btr_def_live_range (other_def, &dummy_btrs_live_in_range);
1087 COPY_HARD_REG_SET (combined_btrs_live, *btrs_live_in_range);
1088 bitmap_copy (combined_live_range, def->live_range);
1090 for (user = other_def->uses; user != NULL; user = user->next)
1091 augment_live_range (combined_live_range, &combined_btrs_live,
1092 def->bb, user->bb,
1093 (flag_btr_bb_exclusive
1094 || user->insn != BB_END (def->bb)
1095 || !JUMP_P (user->insn)));
1097 btr = choose_btr (combined_btrs_live);
1098 if (btr != -1)
1100 /* We can combine them. */
1101 if (dump_file)
1102 fprintf (dump_file,
1103 "Combining def in insn %d with def in insn %d\n",
1104 INSN_UID (other_def->insn), INSN_UID (def->insn));
1106 def->btr = btr;
1107 user = other_def->uses;
1108 while (user != NULL)
1110 btr_user next = user->next;
1112 user->next = def->uses;
1113 def->uses = user;
1114 user = next;
1116 /* Combining def/use webs can make target registers live
1117 after uses where they previously were not. This means
1118 some REG_DEAD notes may no longer be correct. We could
1119 be more precise about this if we looked at the combined
1120 live range, but here I just delete any REG_DEAD notes
1121 in case they are no longer correct. */
1122 for (user = def->uses; user != NULL; user = user->next)
1123 remove_note (user->insn,
1124 find_regno_note (user->insn, REG_DEAD,
1125 REGNO (user->use)));
1126 clear_btr_from_live_range (other_def);
1127 other_def->uses = NULL;
1128 bitmap_copy (def->live_range, combined_live_range);
1129 if (other_def->btr == btr && other_def->other_btr_uses_after_use)
1130 def->other_btr_uses_after_use = 1;
1131 COPY_HARD_REG_SET (*btrs_live_in_range, combined_btrs_live);
1133 /* Delete the old target register initialization. */
1134 delete_insn (other_def->insn);
1137 BITMAP_FREE (combined_live_range);
1142 /* Move the definition DEF from its current position to basic
1143 block NEW_DEF_BB, and modify it to use branch target register BTR.
1144 Delete the old defining insn, and insert a new one in NEW_DEF_BB.
1145 Update all reaching uses of DEF in the RTL to use BTR.
1146 If this new position means that other defs in the
1147 same group can be combined with DEF then combine them. */
1148 static void
1149 move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range,
1150 HARD_REG_SET *btrs_live_in_range)
1152 /* We can move the instruction.
1153 Set a target register in block NEW_DEF_BB to the value
1154 needed for this target register definition.
1155 Replace all uses of the old target register definition by
1156 uses of the new definition. Delete the old definition. */
1157 basic_block b = new_def_bb;
1158 rtx_insn *insp = BB_HEAD (b);
1159 rtx_insn *old_insn = def->insn;
1160 rtx src;
1161 rtx btr_rtx;
1162 rtx_insn *new_insn;
1163 machine_mode btr_mode;
1164 btr_user user;
1165 rtx set;
1167 if (dump_file)
1168 fprintf(dump_file, "migrating to basic block %d, using reg %d\n",
1169 new_def_bb->index, btr);
1171 clear_btr_from_live_range (def);
1172 def->btr = btr;
1173 def->bb = new_def_bb;
1174 def->luid = 0;
1175 def->cost = basic_block_freq (new_def_bb);
1176 bitmap_copy (def->live_range, live_range);
1177 combine_btr_defs (def, btrs_live_in_range);
1178 btr = def->btr;
1179 def->other_btr_uses_before_def
1180 = TEST_HARD_REG_BIT (btrs_live[b->index], btr) ? 1 : 0;
1181 add_btr_to_live_range (def, 1);
1182 if (LABEL_P (insp))
1183 insp = NEXT_INSN (insp);
1184 /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some
1185 optimizations can result in insp being both first and last insn of
1186 its basic block. */
1187 /* ?? some assertions to check that insp is sensible? */
1189 if (def->other_btr_uses_before_def)
1191 insp = BB_END (b);
1192 for (insp = BB_END (b); ! INSN_P (insp); insp = PREV_INSN (insp))
1193 gcc_assert (insp != BB_HEAD (b));
1195 if (JUMP_P (insp) || can_throw_internal (insp))
1196 insp = PREV_INSN (insp);
1199 set = single_set (old_insn);
1200 src = SET_SRC (set);
1201 btr_mode = GET_MODE (SET_DEST (set));
1202 btr_rtx = gen_rtx_REG (btr_mode, btr);
1204 new_insn = gen_move_insn (btr_rtx, src);
1206 /* Insert target register initialization at head of basic block. */
1207 def->insn = emit_insn_after (new_insn, insp);
1209 df_set_regs_ever_live (btr, true);
1211 if (dump_file)
1212 fprintf (dump_file, "New pt is insn %d, inserted after insn %d\n",
1213 INSN_UID (def->insn), INSN_UID (insp));
1215 /* Delete the old target register initialization. */
1216 delete_insn (old_insn);
1218 /* Replace each use of the old target register by a use of the new target
1219 register. */
1220 for (user = def->uses; user != NULL; user = user->next)
1222 /* Some extra work here to ensure consistent modes, because
1223 it seems that a target register REG rtx can be given a different
1224 mode depending on the context (surely that should not be
1225 the case?). */
1226 rtx replacement_rtx;
1227 if (GET_MODE (user->use) == GET_MODE (btr_rtx)
1228 || GET_MODE (user->use) == VOIDmode)
1229 replacement_rtx = btr_rtx;
1230 else
1231 replacement_rtx = gen_rtx_REG (GET_MODE (user->use), btr);
1232 validate_replace_rtx (user->use, replacement_rtx, user->insn);
1233 user->use = replacement_rtx;
1237 /* We anticipate intra-block scheduling to be done. See if INSN could move
1238 up within BB by N_INSNS. */
1239 static int
1240 can_move_up (const_basic_block bb, const rtx_insn *insn, int n_insns)
1242 while (insn != BB_HEAD (bb) && n_insns > 0)
1244 insn = PREV_INSN (insn);
1245 /* ??? What if we have an anti-dependency that actually prevents the
1246 scheduler from doing the move? We'd like to re-allocate the register,
1247 but not necessarily put the load into another basic block. */
1248 if (INSN_P (insn))
1249 n_insns--;
1251 return n_insns <= 0;
1254 /* Attempt to migrate the target register definition DEF to an
1255 earlier point in the flowgraph.
1257 It is a precondition of this function that DEF is migratable:
1258 i.e. it has a constant source, and all uses are unambiguous.
1260 Only migrations that reduce the cost of DEF will be made.
1261 MIN_COST is the lower bound on the cost of the DEF after migration.
1262 If we migrate DEF so that its cost falls below MIN_COST,
1263 then we do not attempt to migrate further. The idea is that
1264 we migrate definitions in a priority order based on their cost,
1265 when the cost of this definition falls below MIN_COST, then
1266 there is another definition with cost == MIN_COST which now
1267 has a higher priority than this definition.
1269 Return nonzero if there may be benefit from attempting to
1270 migrate this DEF further (i.e. we have reduced the cost below
1271 MIN_COST, but we may be able to reduce it further).
1272 Return zero if no further migration is possible. */
1273 static int
1274 migrate_btr_def (btr_def def, int min_cost)
1276 bitmap live_range;
1277 HARD_REG_SET btrs_live_in_range;
1278 int btr_used_near_def = 0;
1279 int def_basic_block_freq;
1280 basic_block attempt;
1281 int give_up = 0;
1282 int def_moved = 0;
1283 btr_user user;
1284 int def_latency;
1286 if (dump_file)
1287 fprintf (dump_file,
1288 "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ",
1289 INSN_UID (def->insn), def->cost, min_cost);
1291 if (!def->group || def->has_ambiguous_use)
1292 /* These defs are not migratable. */
1294 if (dump_file)
1295 fprintf (dump_file, "it's not migratable\n");
1296 return 0;
1299 if (!def->uses)
1300 /* We have combined this def with another in the same group, so
1301 no need to consider it further.
1304 if (dump_file)
1305 fprintf (dump_file, "it's already combined with another pt\n");
1306 return 0;
1309 btr_def_live_range (def, &btrs_live_in_range);
1310 live_range = BITMAP_ALLOC (NULL);
1311 bitmap_copy (live_range, def->live_range);
1313 #ifdef INSN_SCHEDULING
1314 def_latency = insn_default_latency (def->insn) * issue_rate;
1315 #else
1316 def_latency = issue_rate;
1317 #endif
1319 for (user = def->uses; user != NULL; user = user->next)
1321 if (user->bb == def->bb
1322 && user->luid > def->luid
1323 && (def->luid + def_latency) > user->luid
1324 && ! can_move_up (def->bb, def->insn,
1325 (def->luid + def_latency) - user->luid))
1327 btr_used_near_def = 1;
1328 break;
1332 def_basic_block_freq = basic_block_freq (def->bb);
1334 for (attempt = get_immediate_dominator (CDI_DOMINATORS, def->bb);
1335 !give_up && attempt && attempt != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1336 && def->cost >= min_cost;
1337 attempt = get_immediate_dominator (CDI_DOMINATORS, attempt))
1339 /* Try to move the instruction that sets the target register into
1340 basic block ATTEMPT. */
1341 int try_freq = basic_block_freq (attempt);
1342 edge_iterator ei;
1343 edge e;
1345 /* If ATTEMPT has abnormal edges, skip it. */
1346 FOR_EACH_EDGE (e, ei, attempt->succs)
1347 if (e->flags & EDGE_COMPLEX)
1348 break;
1349 if (e)
1350 continue;
1352 if (dump_file)
1353 fprintf (dump_file, "trying block %d ...", attempt->index);
1355 if (try_freq < def_basic_block_freq
1356 || (try_freq == def_basic_block_freq && btr_used_near_def))
1358 int btr;
1359 augment_live_range (live_range, &btrs_live_in_range, def->bb, attempt,
1360 flag_btr_bb_exclusive);
1361 if (dump_file)
1363 fprintf (dump_file, "Now btrs live in range are: ");
1364 dump_hard_reg_set (btrs_live_in_range);
1365 fprintf (dump_file, "\n");
1367 btr = choose_btr (btrs_live_in_range);
1368 if (btr != -1)
1370 move_btr_def (attempt, btr, def, live_range, &btrs_live_in_range);
1371 bitmap_copy (live_range, def->live_range);
1372 btr_used_near_def = 0;
1373 def_moved = 1;
1374 def_basic_block_freq = basic_block_freq (def->bb);
1376 else
1378 /* There are no free target registers available to move
1379 this far forward, so give up */
1380 give_up = 1;
1381 if (dump_file)
1382 fprintf (dump_file,
1383 "giving up because there are no free target registers\n");
1388 if (!def_moved)
1390 give_up = 1;
1391 if (dump_file)
1392 fprintf (dump_file, "failed to move\n");
1394 BITMAP_FREE (live_range);
1395 return !give_up;
1398 /* Attempt to move instructions that set target registers earlier
1399 in the flowgraph, away from their corresponding uses. */
1400 static void
1401 migrate_btr_defs (enum reg_class btr_class, int allow_callee_save)
1403 btr_heap_t all_btr_defs (LONG_MIN);
1404 int reg;
1406 gcc_obstack_init (&migrate_btrl_obstack);
1407 if (dump_file)
1409 int i;
1411 for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++)
1413 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1414 fprintf (dump_file,
1415 "Basic block %d: count = %" PRId64
1416 " loop-depth = %d idom = %d\n",
1417 i, (int64_t) bb->count, bb_loop_depth (bb),
1418 get_immediate_dominator (CDI_DOMINATORS, bb)->index);
1422 CLEAR_HARD_REG_SET (all_btrs);
1423 for (first_btr = -1, reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
1424 if (TEST_HARD_REG_BIT (reg_class_contents[(int) btr_class], reg)
1425 && (allow_callee_save || call_used_regs[reg]
1426 || df_regs_ever_live_p (reg)))
1428 SET_HARD_REG_BIT (all_btrs, reg);
1429 last_btr = reg;
1430 if (first_btr < 0)
1431 first_btr = reg;
1434 btrs_live = XCNEWVEC (HARD_REG_SET, last_basic_block_for_fn (cfun));
1435 btrs_live_at_end = XCNEWVEC (HARD_REG_SET, last_basic_block_for_fn (cfun));
1437 build_btr_def_use_webs (&all_btr_defs);
1439 while (!all_btr_defs.empty ())
1441 int min_cost = -all_btr_defs.min_key ();
1442 btr_def def = all_btr_defs.extract_min ();
1443 if (migrate_btr_def (def, min_cost))
1445 all_btr_defs.insert (-def->cost, def);
1446 if (dump_file)
1448 fprintf (dump_file,
1449 "Putting insn %d back on queue with priority %d\n",
1450 INSN_UID (def->insn), def->cost);
1453 else
1454 BITMAP_FREE (def->live_range);
1457 free (btrs_live);
1458 free (btrs_live_at_end);
1459 obstack_free (&migrate_btrl_obstack, NULL);
1462 static void
1463 branch_target_load_optimize (bool after_prologue_epilogue_gen)
1465 enum reg_class klass
1466 = (enum reg_class) targetm.branch_target_register_class ();
1467 if (klass != NO_REGS)
1469 /* Initialize issue_rate. */
1470 if (targetm.sched.issue_rate)
1471 issue_rate = targetm.sched.issue_rate ();
1472 else
1473 issue_rate = 1;
1475 if (!after_prologue_epilogue_gen)
1477 /* Build the CFG for migrate_btr_defs. */
1478 #if 1
1479 /* This may or may not be needed, depending on where we
1480 run this phase. */
1481 cleanup_cfg (optimize ? CLEANUP_EXPENSIVE : 0);
1482 #endif
1484 df_analyze ();
1487 /* Dominator info is also needed for migrate_btr_def. */
1488 calculate_dominance_info (CDI_DOMINATORS);
1489 migrate_btr_defs (klass,
1490 (targetm.branch_target_register_callee_saved
1491 (after_prologue_epilogue_gen)));
1493 free_dominance_info (CDI_DOMINATORS);
1497 namespace {
1499 const pass_data pass_data_branch_target_load_optimize1 =
1501 RTL_PASS, /* type */
1502 "btl1", /* name */
1503 OPTGROUP_NONE, /* optinfo_flags */
1504 TV_NONE, /* tv_id */
1505 0, /* properties_required */
1506 0, /* properties_provided */
1507 0, /* properties_destroyed */
1508 0, /* todo_flags_start */
1509 0, /* todo_flags_finish */
1512 class pass_branch_target_load_optimize1 : public rtl_opt_pass
1514 public:
1515 pass_branch_target_load_optimize1 (gcc::context *ctxt)
1516 : rtl_opt_pass (pass_data_branch_target_load_optimize1, ctxt)
1519 /* opt_pass methods: */
1520 virtual bool gate (function *) { return flag_branch_target_load_optimize; }
1521 virtual unsigned int execute (function *)
1523 branch_target_load_optimize (epilogue_completed);
1524 return 0;
1527 }; // class pass_branch_target_load_optimize1
1529 } // anon namespace
1531 rtl_opt_pass *
1532 make_pass_branch_target_load_optimize1 (gcc::context *ctxt)
1534 return new pass_branch_target_load_optimize1 (ctxt);
1538 namespace {
1540 const pass_data pass_data_branch_target_load_optimize2 =
1542 RTL_PASS, /* type */
1543 "btl2", /* name */
1544 OPTGROUP_NONE, /* optinfo_flags */
1545 TV_NONE, /* tv_id */
1546 0, /* properties_required */
1547 0, /* properties_provided */
1548 0, /* properties_destroyed */
1549 0, /* todo_flags_start */
1550 0, /* todo_flags_finish */
1553 class pass_branch_target_load_optimize2 : public rtl_opt_pass
1555 public:
1556 pass_branch_target_load_optimize2 (gcc::context *ctxt)
1557 : rtl_opt_pass (pass_data_branch_target_load_optimize2, ctxt)
1560 /* opt_pass methods: */
1561 virtual bool gate (function *)
1563 return (optimize > 0 && flag_branch_target_load_optimize2);
1566 virtual unsigned int execute (function *);
1568 }; // class pass_branch_target_load_optimize2
1570 unsigned int
1571 pass_branch_target_load_optimize2::execute (function *)
1573 static int warned = 0;
1575 /* Leave this a warning for now so that it is possible to experiment
1576 with running this pass twice. In 3.6, we should either make this
1577 an error, or use separate dump files. */
1578 if (flag_branch_target_load_optimize
1579 && flag_branch_target_load_optimize2
1580 && !warned)
1582 warning (0, "branch target register load optimization is not intended "
1583 "to be run twice");
1585 warned = 1;
1588 branch_target_load_optimize (epilogue_completed);
1589 return 0;
1592 } // anon namespace
1594 rtl_opt_pass *
1595 make_pass_branch_target_load_optimize2 (gcc::context *ctxt)
1597 return new pass_branch_target_load_optimize2 (ctxt);