2014-04-15 Richard Biener <rguenther@suse.de>
[official-gcc.git] / gcc / bt-load.c
blob4fa68f11e98710371074534c1cb2d25cf4e5a04a
2 /* Perform branch target register load optimizations.
3 Copyright (C) 2001-2014 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 "target.h"
30 #include "expr.h"
31 #include "flags.h"
32 #include "insn-attr.h"
33 #include "function.h"
34 #include "except.h"
35 #include "tm_p.h"
36 #include "diagnostic-core.h"
37 #include "tree-pass.h"
38 #include "recog.h"
39 #include "df.h"
40 #include "cfgloop.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 = XOBNEW (&migrate_btrl_obstack, struct btr_def_group_s);
283 this_group->src = def_src;
284 this_group->members = NULL;
285 this_group->next = *all_btr_def_groups;
286 *all_btr_def_groups = this_group;
288 def->group = this_group;
289 def->next_this_group = this_group->members;
290 this_group->members = def;
292 else
293 def->group = NULL;
296 /* Create a new target register definition structure, for a definition in
297 block BB, instruction INSN, and insert it into ALL_BTR_DEFS. Return
298 the new definition. */
299 static btr_def
300 add_btr_def (fibheap_t all_btr_defs, basic_block bb, int insn_luid, rtx insn,
301 unsigned int dest_reg, int other_btr_uses_before_def,
302 btr_def_group *all_btr_def_groups)
304 btr_def this_def = XOBNEW (&migrate_btrl_obstack, struct btr_def_s);
305 this_def->bb = bb;
306 this_def->luid = insn_luid;
307 this_def->insn = insn;
308 this_def->btr = dest_reg;
309 this_def->cost = basic_block_freq (bb);
310 this_def->has_ambiguous_use = 0;
311 this_def->other_btr_uses_before_def = other_btr_uses_before_def;
312 this_def->other_btr_uses_after_use = 0;
313 this_def->next_this_bb = NULL;
314 this_def->next_this_group = NULL;
315 this_def->uses = NULL;
316 this_def->live_range = NULL;
317 find_btr_def_group (all_btr_def_groups, this_def);
319 fibheap_insert (all_btr_defs, -this_def->cost, this_def);
321 if (dump_file)
322 fprintf (dump_file,
323 "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n",
324 dest_reg, bb->index, INSN_UID (insn),
325 (this_def->group ? "" : ":not const"), this_def->cost);
327 return this_def;
330 /* Create a new target register user structure, for a use in block BB,
331 instruction INSN. Return the new user. */
332 static btr_user
333 new_btr_user (basic_block bb, int insn_luid, rtx insn)
335 /* This instruction reads target registers. We need
336 to decide whether we can replace all target register
337 uses easily.
339 rtx *usep = find_btr_use (PATTERN (insn));
340 rtx use;
341 btr_user user = NULL;
343 if (usep)
345 int unambiguous_single_use;
347 /* We want to ensure that USE is the only use of a target
348 register in INSN, so that we know that to rewrite INSN to use
349 a different target register, all we have to do is replace USE. */
350 unambiguous_single_use = !btr_referenced_p (PATTERN (insn), usep);
351 if (!unambiguous_single_use)
352 usep = NULL;
354 use = usep ? *usep : NULL_RTX;
355 user = XOBNEW (&migrate_btrl_obstack, struct btr_user_s);
356 user->bb = bb;
357 user->luid = insn_luid;
358 user->insn = insn;
359 user->use = use;
360 user->other_use_this_block = 0;
361 user->next = NULL;
362 user->n_reaching_defs = 0;
363 user->first_reaching_def = -1;
365 if (dump_file)
367 fprintf (dump_file, "Uses target reg: { bb %d, insn %d }",
368 bb->index, INSN_UID (insn));
370 if (user->use)
371 fprintf (dump_file, ": unambiguous use of reg %d\n",
372 REGNO (user->use));
375 return user;
378 /* Write the contents of S to the dump file. */
379 static void
380 dump_hard_reg_set (HARD_REG_SET s)
382 int reg;
383 for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
384 if (TEST_HARD_REG_BIT (s, reg))
385 fprintf (dump_file, " %d", reg);
388 /* Write the set of target regs live in block BB to the dump file. */
389 static void
390 dump_btrs_live (int bb)
392 fprintf (dump_file, "BB%d live:", bb);
393 dump_hard_reg_set (btrs_live[bb]);
394 fprintf (dump_file, "\n");
397 /* REGNO is the number of a branch target register that is being used or
398 set. USERS_THIS_BB is a list of preceding branch target register users;
399 If any of them use the same register, set their other_use_this_block
400 flag. */
401 static void
402 note_other_use_this_block (unsigned int regno, btr_user users_this_bb)
404 btr_user user;
406 for (user = users_this_bb; user != NULL; user = user->next)
407 if (user->use && REGNO (user->use) == regno)
408 user->other_use_this_block = 1;
411 typedef struct {
412 btr_user users_this_bb;
413 HARD_REG_SET btrs_written_in_block;
414 HARD_REG_SET btrs_live_in_block;
415 sbitmap bb_gen;
416 sbitmap *btr_defset;
417 } defs_uses_info;
419 /* Called via note_stores or directly to register stores into /
420 clobbers of a branch target register DEST that are not recognized as
421 straightforward definitions. DATA points to information about the
422 current basic block that needs updating. */
423 static void
424 note_btr_set (rtx dest, const_rtx set ATTRIBUTE_UNUSED, void *data)
426 defs_uses_info *info = (defs_uses_info *) data;
427 int regno, end_regno;
429 if (!REG_P (dest))
430 return;
431 regno = REGNO (dest);
432 end_regno = END_HARD_REGNO (dest);
433 for (; regno < end_regno; regno++)
434 if (TEST_HARD_REG_BIT (all_btrs, regno))
436 note_other_use_this_block (regno, info->users_this_bb);
437 SET_HARD_REG_BIT (info->btrs_written_in_block, regno);
438 SET_HARD_REG_BIT (info->btrs_live_in_block, regno);
439 bitmap_and_compl (info->bb_gen, info->bb_gen,
440 info->btr_defset[regno - first_btr]);
444 static void
445 compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array,
446 btr_user *use_array, sbitmap *btr_defset,
447 sbitmap *bb_gen, HARD_REG_SET *btrs_written)
449 /* Scan the code building up the set of all defs and all uses.
450 For each target register, build the set of defs of that register.
451 For each block, calculate the set of target registers
452 written in that block.
453 Also calculate the set of btrs ever live in that block.
455 int i;
456 int insn_luid = 0;
457 btr_def_group all_btr_def_groups = NULL;
458 defs_uses_info info;
460 bitmap_vector_clear (bb_gen, last_basic_block_for_fn (cfun));
461 for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++)
463 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
464 int reg;
465 btr_def defs_this_bb = NULL;
466 rtx insn;
467 rtx last;
468 int can_throw = 0;
470 info.users_this_bb = NULL;
471 info.bb_gen = bb_gen[i];
472 info.btr_defset = btr_defset;
474 CLEAR_HARD_REG_SET (info.btrs_live_in_block);
475 CLEAR_HARD_REG_SET (info.btrs_written_in_block);
476 for (reg = first_btr; reg <= last_btr; reg++)
477 if (TEST_HARD_REG_BIT (all_btrs, reg)
478 && REGNO_REG_SET_P (df_get_live_in (bb), reg))
479 SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
481 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
482 insn != last;
483 insn = NEXT_INSN (insn), insn_luid++)
485 if (INSN_P (insn))
487 int regno;
488 int insn_uid = INSN_UID (insn);
490 if (insn_sets_btr_p (insn, 0, &regno))
492 btr_def def = add_btr_def (
493 all_btr_defs, bb, insn_luid, insn, regno,
494 TEST_HARD_REG_BIT (info.btrs_live_in_block, regno),
495 &all_btr_def_groups);
497 def_array[insn_uid] = def;
498 SET_HARD_REG_BIT (info.btrs_written_in_block, regno);
499 SET_HARD_REG_BIT (info.btrs_live_in_block, regno);
500 bitmap_and_compl (bb_gen[i], bb_gen[i],
501 btr_defset[regno - first_btr]);
502 bitmap_set_bit (bb_gen[i], insn_uid);
503 def->next_this_bb = defs_this_bb;
504 defs_this_bb = def;
505 bitmap_set_bit (btr_defset[regno - first_btr], insn_uid);
506 note_other_use_this_block (regno, info.users_this_bb);
508 /* Check for the blockage emitted by expand_nl_goto_receiver. */
509 else if (cfun->has_nonlocal_label
510 && GET_CODE (PATTERN (insn)) == UNSPEC_VOLATILE)
512 btr_user user;
514 /* Do the equivalent of calling note_other_use_this_block
515 for every target register. */
516 for (user = info.users_this_bb; user != NULL;
517 user = user->next)
518 if (user->use)
519 user->other_use_this_block = 1;
520 IOR_HARD_REG_SET (info.btrs_written_in_block, all_btrs);
521 IOR_HARD_REG_SET (info.btrs_live_in_block, all_btrs);
522 bitmap_clear (info.bb_gen);
524 else
526 if (btr_referenced_p (PATTERN (insn), NULL))
528 btr_user user = new_btr_user (bb, insn_luid, insn);
530 use_array[insn_uid] = user;
531 if (user->use)
532 SET_HARD_REG_BIT (info.btrs_live_in_block,
533 REGNO (user->use));
534 else
536 int reg;
537 for (reg = first_btr; reg <= last_btr; reg++)
538 if (TEST_HARD_REG_BIT (all_btrs, reg)
539 && refers_to_regno_p (reg, reg + 1, user->insn,
540 NULL))
542 note_other_use_this_block (reg,
543 info.users_this_bb);
544 SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
546 note_stores (PATTERN (insn), note_btr_set, &info);
548 user->next = info.users_this_bb;
549 info.users_this_bb = user;
551 if (CALL_P (insn))
553 HARD_REG_SET *clobbered = &call_used_reg_set;
554 HARD_REG_SET call_saved;
555 rtx pat = PATTERN (insn);
556 int i;
558 /* Check for sibcall. */
559 if (GET_CODE (pat) == PARALLEL)
560 for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
561 if (ANY_RETURN_P (XVECEXP (pat, 0, i)))
563 COMPL_HARD_REG_SET (call_saved,
564 call_used_reg_set);
565 clobbered = &call_saved;
568 for (regno = first_btr; regno <= last_btr; regno++)
569 if (TEST_HARD_REG_BIT (*clobbered, regno))
570 note_btr_set (regno_reg_rtx[regno], NULL_RTX, &info);
576 COPY_HARD_REG_SET (btrs_live[i], info.btrs_live_in_block);
577 COPY_HARD_REG_SET (btrs_written[i], info.btrs_written_in_block);
579 REG_SET_TO_HARD_REG_SET (btrs_live_at_end[i], df_get_live_out (bb));
580 /* If this block ends in a jump insn, add any uses or even clobbers
581 of branch target registers that it might have. */
582 for (insn = BB_END (bb); insn != BB_HEAD (bb) && ! INSN_P (insn); )
583 insn = PREV_INSN (insn);
584 /* ??? for the fall-through edge, it would make sense to insert the
585 btr set on the edge, but that would require to split the block
586 early on so that we can distinguish between dominance from the fall
587 through edge - which can use the call-clobbered registers - from
588 dominance by the throw edge. */
589 if (can_throw_internal (insn))
591 HARD_REG_SET tmp;
593 COPY_HARD_REG_SET (tmp, call_used_reg_set);
594 AND_HARD_REG_SET (tmp, all_btrs);
595 IOR_HARD_REG_SET (btrs_live_at_end[i], tmp);
596 can_throw = 1;
598 if (can_throw || JUMP_P (insn))
600 int regno;
602 for (regno = first_btr; regno <= last_btr; regno++)
603 if (refers_to_regno_p (regno, regno+1, insn, NULL))
604 SET_HARD_REG_BIT (btrs_live_at_end[i], regno);
607 if (dump_file)
608 dump_btrs_live (i);
612 static void
613 compute_kill (sbitmap *bb_kill, sbitmap *btr_defset,
614 HARD_REG_SET *btrs_written)
616 int i;
617 int regno;
619 /* For each basic block, form the set BB_KILL - the set
620 of definitions that the block kills. */
621 bitmap_vector_clear (bb_kill, last_basic_block_for_fn (cfun));
622 for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++)
624 for (regno = first_btr; regno <= last_btr; regno++)
625 if (TEST_HARD_REG_BIT (all_btrs, regno)
626 && TEST_HARD_REG_BIT (btrs_written[i], regno))
627 bitmap_ior (bb_kill[i], bb_kill[i],
628 btr_defset[regno - first_btr]);
632 static void
633 compute_out (sbitmap *bb_out, sbitmap *bb_gen, sbitmap *bb_kill, int max_uid)
635 /* Perform iterative dataflow:
636 Initially, for all blocks, BB_OUT = BB_GEN.
637 For each block,
638 BB_IN = union over predecessors of BB_OUT(pred)
639 BB_OUT = (BB_IN - BB_KILL) + BB_GEN
640 Iterate until the bb_out sets stop growing. */
641 int i;
642 int changed;
643 sbitmap bb_in = sbitmap_alloc (max_uid);
645 for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++)
646 bitmap_copy (bb_out[i], bb_gen[i]);
648 changed = 1;
649 while (changed)
651 changed = 0;
652 for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++)
654 bitmap_union_of_preds (bb_in, bb_out, BASIC_BLOCK_FOR_FN (cfun, i));
655 changed |= bitmap_ior_and_compl (bb_out[i], bb_gen[i],
656 bb_in, bb_kill[i]);
659 sbitmap_free (bb_in);
662 static void
663 link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out,
664 sbitmap *btr_defset, int max_uid)
666 int i;
667 sbitmap reaching_defs = sbitmap_alloc (max_uid);
669 /* Link uses to the uses lists of all of their reaching defs.
670 Count up the number of reaching defs of each use. */
671 for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++)
673 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
674 rtx insn;
675 rtx last;
677 bitmap_union_of_preds (reaching_defs, bb_out, BASIC_BLOCK_FOR_FN (cfun, i));
678 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
679 insn != last;
680 insn = NEXT_INSN (insn))
682 if (INSN_P (insn))
684 int insn_uid = INSN_UID (insn);
686 btr_def def = def_array[insn_uid];
687 btr_user user = use_array[insn_uid];
688 if (def != NULL)
690 /* Remove all reaching defs of regno except
691 for this one. */
692 bitmap_and_compl (reaching_defs, reaching_defs,
693 btr_defset[def->btr - first_btr]);
694 bitmap_set_bit (reaching_defs, insn_uid);
697 if (user != NULL)
699 /* Find all the reaching defs for this use. */
700 sbitmap reaching_defs_of_reg = sbitmap_alloc (max_uid);
701 unsigned int uid = 0;
702 sbitmap_iterator sbi;
704 if (user->use)
705 bitmap_and (
706 reaching_defs_of_reg,
707 reaching_defs,
708 btr_defset[REGNO (user->use) - first_btr]);
709 else
711 int reg;
713 bitmap_clear (reaching_defs_of_reg);
714 for (reg = first_btr; reg <= last_btr; reg++)
715 if (TEST_HARD_REG_BIT (all_btrs, reg)
716 && refers_to_regno_p (reg, reg + 1, user->insn,
717 NULL))
718 bitmap_or_and (reaching_defs_of_reg,
719 reaching_defs_of_reg,
720 reaching_defs,
721 btr_defset[reg - first_btr]);
723 EXECUTE_IF_SET_IN_BITMAP (reaching_defs_of_reg, 0, uid, sbi)
725 btr_def def = def_array[uid];
727 /* We now know that def reaches user. */
729 if (dump_file)
730 fprintf (dump_file,
731 "Def in insn %d reaches use in insn %d\n",
732 uid, insn_uid);
734 user->n_reaching_defs++;
735 if (!user->use)
736 def->has_ambiguous_use = 1;
737 if (user->first_reaching_def != -1)
738 { /* There is more than one reaching def. This is
739 a rare case, so just give up on this def/use
740 web when it occurs. */
741 def->has_ambiguous_use = 1;
742 def_array[user->first_reaching_def]
743 ->has_ambiguous_use = 1;
744 if (dump_file)
745 fprintf (dump_file,
746 "(use %d has multiple reaching defs)\n",
747 insn_uid);
749 else
750 user->first_reaching_def = uid;
751 if (user->other_use_this_block)
752 def->other_btr_uses_after_use = 1;
753 user->next = def->uses;
754 def->uses = user;
756 sbitmap_free (reaching_defs_of_reg);
759 if (CALL_P (insn))
761 int regno;
763 for (regno = first_btr; regno <= last_btr; regno++)
764 if (TEST_HARD_REG_BIT (all_btrs, regno)
765 && TEST_HARD_REG_BIT (call_used_reg_set, regno))
766 bitmap_and_compl (reaching_defs, reaching_defs,
767 btr_defset[regno - first_btr]);
772 sbitmap_free (reaching_defs);
775 static void
776 build_btr_def_use_webs (fibheap_t all_btr_defs)
778 const int max_uid = get_max_uid ();
779 btr_def *def_array = XCNEWVEC (btr_def, max_uid);
780 btr_user *use_array = XCNEWVEC (btr_user, max_uid);
781 sbitmap *btr_defset = sbitmap_vector_alloc (
782 (last_btr - first_btr) + 1, max_uid);
783 sbitmap *bb_gen = sbitmap_vector_alloc (last_basic_block_for_fn (cfun),
784 max_uid);
785 HARD_REG_SET *btrs_written = XCNEWVEC (HARD_REG_SET,
786 last_basic_block_for_fn (cfun));
787 sbitmap *bb_kill;
788 sbitmap *bb_out;
790 bitmap_vector_clear (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 (last_basic_block_for_fn (cfun), max_uid);
796 compute_kill (bb_kill, btr_defset, btrs_written);
797 free (btrs_written);
799 bb_out = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), 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
820 && BASIC_BLOCK_FOR_FN (cfun, bb) == def->bb)
821 return 1;
822 else if (def->other_btr_uses_after_use)
824 btr_user user;
825 for (user = def->uses; user != NULL; user = user->next)
826 if (BASIC_BLOCK_FOR_FN (cfun, bb) == user->bb)
827 return 1;
829 return 0;
832 /* We are removing the def/use web DEF. The target register
833 used in this web is therefore no longer live in the live range
834 of this web, so remove it from the live set of all basic blocks
835 in the live range of the web.
836 Blocks at the boundary of the live range may contain other live
837 ranges for the same target register, so we have to be careful
838 to remove the target register from the live set of these blocks
839 only if they do not contain other live ranges for the same register. */
840 static void
841 clear_btr_from_live_range (btr_def def)
843 unsigned bb;
844 bitmap_iterator bi;
846 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
848 if ((!def->other_btr_uses_before_def
849 && !def->other_btr_uses_after_use)
850 || !block_at_edge_of_live_range_p (bb, def))
852 CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr);
853 CLEAR_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
854 if (dump_file)
855 dump_btrs_live (bb);
858 if (def->own_end)
859 CLEAR_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr);
863 /* We are adding the def/use web DEF. Add the target register used
864 in this web to the live set of all of the basic blocks that contain
865 the live range of the web.
866 If OWN_END is set, also show that the register is live from our
867 definitions at the end of the basic block where it is defined. */
868 static void
869 add_btr_to_live_range (btr_def def, int own_end)
871 unsigned bb;
872 bitmap_iterator bi;
874 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
876 SET_HARD_REG_BIT (btrs_live[bb], def->btr);
877 SET_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
878 if (dump_file)
879 dump_btrs_live (bb);
881 if (own_end)
883 SET_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr);
884 def->own_end = 1;
888 /* Update a live range to contain the basic block NEW_BLOCK, and all
889 blocks on paths between the existing live range and NEW_BLOCK.
890 HEAD is a block contained in the existing live range that dominates
891 all other blocks in the existing live range.
892 Also add to the set BTRS_LIVE_IN_RANGE all target registers that
893 are live in the blocks that we add to the live range.
894 If FULL_RANGE is set, include the full live range of NEW_BB;
895 otherwise, if NEW_BB dominates HEAD_BB, only add registers that
896 are life at the end of NEW_BB for NEW_BB itself.
897 It is a precondition that either NEW_BLOCK dominates HEAD,or
898 HEAD dom NEW_BLOCK. This is used to speed up the
899 implementation of this function. */
900 static void
901 augment_live_range (bitmap live_range, HARD_REG_SET *btrs_live_in_range,
902 basic_block head_bb, basic_block new_bb, int full_range)
904 basic_block *worklist, *tos;
906 tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1);
908 if (dominated_by_p (CDI_DOMINATORS, new_bb, head_bb))
910 if (new_bb == head_bb)
912 if (full_range)
913 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_bb->index]);
914 free (tos);
915 return;
917 *tos++ = new_bb;
919 else
921 edge e;
922 edge_iterator ei;
923 int new_block = new_bb->index;
925 gcc_assert (dominated_by_p (CDI_DOMINATORS, head_bb, new_bb));
927 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[head_bb->index]);
928 bitmap_set_bit (live_range, new_block);
929 /* A previous btr migration could have caused a register to be
930 live just at the end of new_block which we need in full, so
931 use trs_live_at_end even if full_range is set. */
932 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live_at_end[new_block]);
933 if (full_range)
934 IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]);
935 if (dump_file)
937 fprintf (dump_file,
938 "Adding end of block %d and rest of %d to live range\n",
939 new_block, head_bb->index);
940 fprintf (dump_file,"Now live btrs are ");
941 dump_hard_reg_set (*btrs_live_in_range);
942 fprintf (dump_file, "\n");
944 FOR_EACH_EDGE (e, ei, head_bb->preds)
945 *tos++ = e->src;
948 while (tos != worklist)
950 basic_block bb = *--tos;
951 if (!bitmap_bit_p (live_range, bb->index))
953 edge e;
954 edge_iterator ei;
956 bitmap_set_bit (live_range, bb->index);
957 IOR_HARD_REG_SET (*btrs_live_in_range,
958 btrs_live[bb->index]);
959 /* A previous btr migration could have caused a register to be
960 live just at the end of a block which we need in full. */
961 IOR_HARD_REG_SET (*btrs_live_in_range,
962 btrs_live_at_end[bb->index]);
963 if (dump_file)
965 fprintf (dump_file,
966 "Adding block %d to live range\n", bb->index);
967 fprintf (dump_file,"Now live btrs are ");
968 dump_hard_reg_set (*btrs_live_in_range);
969 fprintf (dump_file, "\n");
972 FOR_EACH_EDGE (e, ei, bb->preds)
974 basic_block pred = e->src;
975 if (!bitmap_bit_p (live_range, pred->index))
976 *tos++ = pred;
981 free (worklist);
984 /* Return the most desirable target register that is not in
985 the set USED_BTRS. */
986 static int
987 choose_btr (HARD_REG_SET used_btrs)
989 int i;
991 if (!hard_reg_set_subset_p (all_btrs, used_btrs))
992 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
994 #ifdef REG_ALLOC_ORDER
995 int regno = reg_alloc_order[i];
996 #else
997 int regno = i;
998 #endif
999 if (TEST_HARD_REG_BIT (all_btrs, regno)
1000 && !TEST_HARD_REG_BIT (used_btrs, regno))
1001 return regno;
1003 return -1;
1006 /* Calculate the set of basic blocks that contain the live range of
1007 the def/use web DEF.
1008 Also calculate the set of target registers that are live at time
1009 in this live range, but ignore the live range represented by DEF
1010 when calculating this set. */
1011 static void
1012 btr_def_live_range (btr_def def, HARD_REG_SET *btrs_live_in_range)
1014 if (!def->live_range)
1016 btr_user user;
1018 def->live_range = BITMAP_ALLOC (NULL);
1020 bitmap_set_bit (def->live_range, def->bb->index);
1021 COPY_HARD_REG_SET (*btrs_live_in_range,
1022 (flag_btr_bb_exclusive
1023 ? btrs_live : btrs_live_at_end)[def->bb->index]);
1025 for (user = def->uses; user != NULL; user = user->next)
1026 augment_live_range (def->live_range, btrs_live_in_range,
1027 def->bb, user->bb,
1028 (flag_btr_bb_exclusive
1029 || user->insn != BB_END (def->bb)
1030 || !JUMP_P (user->insn)));
1032 else
1034 /* def->live_range is accurate, but we need to recompute
1035 the set of target registers live over it, because migration
1036 of other PT instructions may have affected it.
1038 unsigned bb;
1039 unsigned def_bb = flag_btr_bb_exclusive ? -1 : def->bb->index;
1040 bitmap_iterator bi;
1042 CLEAR_HARD_REG_SET (*btrs_live_in_range);
1043 EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
1045 IOR_HARD_REG_SET (*btrs_live_in_range,
1046 (def_bb == bb
1047 ? btrs_live_at_end : btrs_live) [bb]);
1050 if (!def->other_btr_uses_before_def &&
1051 !def->other_btr_uses_after_use)
1052 CLEAR_HARD_REG_BIT (*btrs_live_in_range, def->btr);
1055 /* Merge into the def/use web DEF any other def/use webs in the same
1056 group that are dominated by DEF, provided that there is a target
1057 register available to allocate to the merged web. */
1058 static void
1059 combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range)
1061 btr_def other_def;
1063 for (other_def = def->group->members;
1064 other_def != NULL;
1065 other_def = other_def->next_this_group)
1067 if (other_def != def
1068 && other_def->uses != NULL
1069 && ! other_def->has_ambiguous_use
1070 && dominated_by_p (CDI_DOMINATORS, other_def->bb, def->bb))
1072 /* def->bb dominates the other def, so def and other_def could
1073 be combined. */
1074 /* Merge their live ranges, and get the set of
1075 target registers live over the merged range. */
1076 int btr;
1077 HARD_REG_SET combined_btrs_live;
1078 bitmap combined_live_range = BITMAP_ALLOC (NULL);
1079 btr_user user;
1081 if (other_def->live_range == NULL)
1083 HARD_REG_SET dummy_btrs_live_in_range;
1084 btr_def_live_range (other_def, &dummy_btrs_live_in_range);
1086 COPY_HARD_REG_SET (combined_btrs_live, *btrs_live_in_range);
1087 bitmap_copy (combined_live_range, def->live_range);
1089 for (user = other_def->uses; user != NULL; user = user->next)
1090 augment_live_range (combined_live_range, &combined_btrs_live,
1091 def->bb, user->bb,
1092 (flag_btr_bb_exclusive
1093 || user->insn != BB_END (def->bb)
1094 || !JUMP_P (user->insn)));
1096 btr = choose_btr (combined_btrs_live);
1097 if (btr != -1)
1099 /* We can combine them. */
1100 if (dump_file)
1101 fprintf (dump_file,
1102 "Combining def in insn %d with def in insn %d\n",
1103 INSN_UID (other_def->insn), INSN_UID (def->insn));
1105 def->btr = btr;
1106 user = other_def->uses;
1107 while (user != NULL)
1109 btr_user next = user->next;
1111 user->next = def->uses;
1112 def->uses = user;
1113 user = next;
1115 /* Combining def/use webs can make target registers live
1116 after uses where they previously were not. This means
1117 some REG_DEAD notes may no longer be correct. We could
1118 be more precise about this if we looked at the combined
1119 live range, but here I just delete any REG_DEAD notes
1120 in case they are no longer correct. */
1121 for (user = def->uses; user != NULL; user = user->next)
1122 remove_note (user->insn,
1123 find_regno_note (user->insn, REG_DEAD,
1124 REGNO (user->use)));
1125 clear_btr_from_live_range (other_def);
1126 other_def->uses = NULL;
1127 bitmap_copy (def->live_range, combined_live_range);
1128 if (other_def->btr == btr && other_def->other_btr_uses_after_use)
1129 def->other_btr_uses_after_use = 1;
1130 COPY_HARD_REG_SET (*btrs_live_in_range, combined_btrs_live);
1132 /* Delete the old target register initialization. */
1133 delete_insn (other_def->insn);
1136 BITMAP_FREE (combined_live_range);
1141 /* Move the definition DEF from its current position to basic
1142 block NEW_DEF_BB, and modify it to use branch target register BTR.
1143 Delete the old defining insn, and insert a new one in NEW_DEF_BB.
1144 Update all reaching uses of DEF in the RTL to use BTR.
1145 If this new position means that other defs in the
1146 same group can be combined with DEF then combine them. */
1147 static void
1148 move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range,
1149 HARD_REG_SET *btrs_live_in_range)
1151 /* We can move the instruction.
1152 Set a target register in block NEW_DEF_BB to the value
1153 needed for this target register definition.
1154 Replace all uses of the old target register definition by
1155 uses of the new definition. Delete the old definition. */
1156 basic_block b = new_def_bb;
1157 rtx insp = BB_HEAD (b);
1158 rtx old_insn = def->insn;
1159 rtx src;
1160 rtx btr_rtx;
1161 rtx new_insn;
1162 enum machine_mode btr_mode;
1163 btr_user user;
1164 rtx set;
1166 if (dump_file)
1167 fprintf(dump_file, "migrating to basic block %d, using reg %d\n",
1168 new_def_bb->index, btr);
1170 clear_btr_from_live_range (def);
1171 def->btr = btr;
1172 def->bb = new_def_bb;
1173 def->luid = 0;
1174 def->cost = basic_block_freq (new_def_bb);
1175 bitmap_copy (def->live_range, live_range);
1176 combine_btr_defs (def, btrs_live_in_range);
1177 btr = def->btr;
1178 def->other_btr_uses_before_def
1179 = TEST_HARD_REG_BIT (btrs_live[b->index], btr) ? 1 : 0;
1180 add_btr_to_live_range (def, 1);
1181 if (LABEL_P (insp))
1182 insp = NEXT_INSN (insp);
1183 /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some
1184 optimizations can result in insp being both first and last insn of
1185 its basic block. */
1186 /* ?? some assertions to check that insp is sensible? */
1188 if (def->other_btr_uses_before_def)
1190 insp = BB_END (b);
1191 for (insp = BB_END (b); ! INSN_P (insp); insp = PREV_INSN (insp))
1192 gcc_assert (insp != BB_HEAD (b));
1194 if (JUMP_P (insp) || can_throw_internal (insp))
1195 insp = PREV_INSN (insp);
1198 set = single_set (old_insn);
1199 src = SET_SRC (set);
1200 btr_mode = GET_MODE (SET_DEST (set));
1201 btr_rtx = gen_rtx_REG (btr_mode, btr);
1203 new_insn = gen_move_insn (btr_rtx, src);
1205 /* Insert target register initialization at head of basic block. */
1206 def->insn = emit_insn_after (new_insn, insp);
1208 df_set_regs_ever_live (btr, true);
1210 if (dump_file)
1211 fprintf (dump_file, "New pt is insn %d, inserted after insn %d\n",
1212 INSN_UID (def->insn), INSN_UID (insp));
1214 /* Delete the old target register initialization. */
1215 delete_insn (old_insn);
1217 /* Replace each use of the old target register by a use of the new target
1218 register. */
1219 for (user = def->uses; user != NULL; user = user->next)
1221 /* Some extra work here to ensure consistent modes, because
1222 it seems that a target register REG rtx can be given a different
1223 mode depending on the context (surely that should not be
1224 the case?). */
1225 rtx replacement_rtx;
1226 if (GET_MODE (user->use) == GET_MODE (btr_rtx)
1227 || GET_MODE (user->use) == VOIDmode)
1228 replacement_rtx = btr_rtx;
1229 else
1230 replacement_rtx = gen_rtx_REG (GET_MODE (user->use), btr);
1231 validate_replace_rtx (user->use, replacement_rtx, user->insn);
1232 user->use = replacement_rtx;
1236 /* We anticipate intra-block scheduling to be done. See if INSN could move
1237 up within BB by N_INSNS. */
1238 static int
1239 can_move_up (const_basic_block bb, const_rtx insn, int n_insns)
1241 while (insn != BB_HEAD (bb) && n_insns > 0)
1243 insn = PREV_INSN (insn);
1244 /* ??? What if we have an anti-dependency that actually prevents the
1245 scheduler from doing the move? We'd like to re-allocate the register,
1246 but not necessarily put the load into another basic block. */
1247 if (INSN_P (insn))
1248 n_insns--;
1250 return n_insns <= 0;
1253 /* Attempt to migrate the target register definition DEF to an
1254 earlier point in the flowgraph.
1256 It is a precondition of this function that DEF is migratable:
1257 i.e. it has a constant source, and all uses are unambiguous.
1259 Only migrations that reduce the cost of DEF will be made.
1260 MIN_COST is the lower bound on the cost of the DEF after migration.
1261 If we migrate DEF so that its cost falls below MIN_COST,
1262 then we do not attempt to migrate further. The idea is that
1263 we migrate definitions in a priority order based on their cost,
1264 when the cost of this definition falls below MIN_COST, then
1265 there is another definition with cost == MIN_COST which now
1266 has a higher priority than this definition.
1268 Return nonzero if there may be benefit from attempting to
1269 migrate this DEF further (i.e. we have reduced the cost below
1270 MIN_COST, but we may be able to reduce it further).
1271 Return zero if no further migration is possible. */
1272 static int
1273 migrate_btr_def (btr_def def, int min_cost)
1275 bitmap live_range;
1276 HARD_REG_SET btrs_live_in_range;
1277 int btr_used_near_def = 0;
1278 int def_basic_block_freq;
1279 basic_block attempt;
1280 int give_up = 0;
1281 int def_moved = 0;
1282 btr_user user;
1283 int def_latency;
1285 if (dump_file)
1286 fprintf (dump_file,
1287 "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ",
1288 INSN_UID (def->insn), def->cost, min_cost);
1290 if (!def->group || def->has_ambiguous_use)
1291 /* These defs are not migratable. */
1293 if (dump_file)
1294 fprintf (dump_file, "it's not migratable\n");
1295 return 0;
1298 if (!def->uses)
1299 /* We have combined this def with another in the same group, so
1300 no need to consider it further.
1303 if (dump_file)
1304 fprintf (dump_file, "it's already combined with another pt\n");
1305 return 0;
1308 btr_def_live_range (def, &btrs_live_in_range);
1309 live_range = BITMAP_ALLOC (NULL);
1310 bitmap_copy (live_range, def->live_range);
1312 #ifdef INSN_SCHEDULING
1313 def_latency = insn_default_latency (def->insn) * issue_rate;
1314 #else
1315 def_latency = issue_rate;
1316 #endif
1318 for (user = def->uses; user != NULL; user = user->next)
1320 if (user->bb == def->bb
1321 && user->luid > def->luid
1322 && (def->luid + def_latency) > user->luid
1323 && ! can_move_up (def->bb, def->insn,
1324 (def->luid + def_latency) - user->luid))
1326 btr_used_near_def = 1;
1327 break;
1331 def_basic_block_freq = basic_block_freq (def->bb);
1333 for (attempt = get_immediate_dominator (CDI_DOMINATORS, def->bb);
1334 !give_up && attempt && attempt != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1335 && def->cost >= min_cost;
1336 attempt = get_immediate_dominator (CDI_DOMINATORS, attempt))
1338 /* Try to move the instruction that sets the target register into
1339 basic block ATTEMPT. */
1340 int try_freq = basic_block_freq (attempt);
1341 edge_iterator ei;
1342 edge e;
1344 /* If ATTEMPT has abnormal edges, skip it. */
1345 FOR_EACH_EDGE (e, ei, attempt->succs)
1346 if (e->flags & EDGE_COMPLEX)
1347 break;
1348 if (e)
1349 continue;
1351 if (dump_file)
1352 fprintf (dump_file, "trying block %d ...", attempt->index);
1354 if (try_freq < def_basic_block_freq
1355 || (try_freq == def_basic_block_freq && btr_used_near_def))
1357 int btr;
1358 augment_live_range (live_range, &btrs_live_in_range, def->bb, attempt,
1359 flag_btr_bb_exclusive);
1360 if (dump_file)
1362 fprintf (dump_file, "Now btrs live in range are: ");
1363 dump_hard_reg_set (btrs_live_in_range);
1364 fprintf (dump_file, "\n");
1366 btr = choose_btr (btrs_live_in_range);
1367 if (btr != -1)
1369 move_btr_def (attempt, btr, def, live_range, &btrs_live_in_range);
1370 bitmap_copy (live_range, def->live_range);
1371 btr_used_near_def = 0;
1372 def_moved = 1;
1373 def_basic_block_freq = basic_block_freq (def->bb);
1375 else
1377 /* There are no free target registers available to move
1378 this far forward, so give up */
1379 give_up = 1;
1380 if (dump_file)
1381 fprintf (dump_file,
1382 "giving up because there are no free target registers\n");
1387 if (!def_moved)
1389 give_up = 1;
1390 if (dump_file)
1391 fprintf (dump_file, "failed to move\n");
1393 BITMAP_FREE (live_range);
1394 return !give_up;
1397 /* Attempt to move instructions that set target registers earlier
1398 in the flowgraph, away from their corresponding uses. */
1399 static void
1400 migrate_btr_defs (enum reg_class btr_class, int allow_callee_save)
1402 fibheap_t all_btr_defs = fibheap_new ();
1403 int reg;
1405 gcc_obstack_init (&migrate_btrl_obstack);
1406 if (dump_file)
1408 int i;
1410 for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++)
1412 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
1413 fprintf (dump_file,
1414 "Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC
1415 " loop-depth = %d idom = %d\n",
1416 i, (HOST_WIDEST_INT) bb->count, bb_loop_depth (bb),
1417 get_immediate_dominator (CDI_DOMINATORS, bb)->index);
1421 CLEAR_HARD_REG_SET (all_btrs);
1422 for (first_btr = -1, reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
1423 if (TEST_HARD_REG_BIT (reg_class_contents[(int) btr_class], reg)
1424 && (allow_callee_save || call_used_regs[reg]
1425 || df_regs_ever_live_p (reg)))
1427 SET_HARD_REG_BIT (all_btrs, reg);
1428 last_btr = reg;
1429 if (first_btr < 0)
1430 first_btr = reg;
1433 btrs_live = XCNEWVEC (HARD_REG_SET, last_basic_block_for_fn (cfun));
1434 btrs_live_at_end = XCNEWVEC (HARD_REG_SET, last_basic_block_for_fn (cfun));
1436 build_btr_def_use_webs (all_btr_defs);
1438 while (!fibheap_empty (all_btr_defs))
1440 btr_def def = (btr_def) fibheap_extract_min (all_btr_defs);
1441 int min_cost = -fibheap_min_key (all_btr_defs);
1442 if (migrate_btr_def (def, min_cost))
1444 fibheap_insert (all_btr_defs, -def->cost, (void *) def);
1445 if (dump_file)
1447 fprintf (dump_file,
1448 "Putting insn %d back on queue with priority %d\n",
1449 INSN_UID (def->insn), def->cost);
1452 else
1453 BITMAP_FREE (def->live_range);
1456 free (btrs_live);
1457 free (btrs_live_at_end);
1458 obstack_free (&migrate_btrl_obstack, NULL);
1459 fibheap_delete (all_btr_defs);
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 static bool
1498 gate_handle_branch_target_load_optimize1 (void)
1500 return flag_branch_target_load_optimize;
1504 static unsigned int
1505 rest_of_handle_branch_target_load_optimize1 (void)
1507 branch_target_load_optimize (epilogue_completed);
1508 return 0;
1511 namespace {
1513 const pass_data pass_data_branch_target_load_optimize1 =
1515 RTL_PASS, /* type */
1516 "btl1", /* name */
1517 OPTGROUP_NONE, /* optinfo_flags */
1518 true, /* has_gate */
1519 true, /* has_execute */
1520 TV_NONE, /* tv_id */
1521 0, /* properties_required */
1522 0, /* properties_provided */
1523 0, /* properties_destroyed */
1524 0, /* todo_flags_start */
1525 TODO_verify_rtl_sharing, /* todo_flags_finish */
1528 class pass_branch_target_load_optimize1 : public rtl_opt_pass
1530 public:
1531 pass_branch_target_load_optimize1 (gcc::context *ctxt)
1532 : rtl_opt_pass (pass_data_branch_target_load_optimize1, ctxt)
1535 /* opt_pass methods: */
1536 bool gate () { return gate_handle_branch_target_load_optimize1 (); }
1537 unsigned int execute () {
1538 return rest_of_handle_branch_target_load_optimize1 ();
1541 }; // class pass_branch_target_load_optimize1
1543 } // anon namespace
1545 rtl_opt_pass *
1546 make_pass_branch_target_load_optimize1 (gcc::context *ctxt)
1548 return new pass_branch_target_load_optimize1 (ctxt);
1551 static bool
1552 gate_handle_branch_target_load_optimize2 (void)
1554 return (optimize > 0 && flag_branch_target_load_optimize2);
1558 static unsigned int
1559 rest_of_handle_branch_target_load_optimize2 (void)
1561 static int warned = 0;
1563 /* Leave this a warning for now so that it is possible to experiment
1564 with running this pass twice. In 3.6, we should either make this
1565 an error, or use separate dump files. */
1566 if (flag_branch_target_load_optimize
1567 && flag_branch_target_load_optimize2
1568 && !warned)
1570 warning (0, "branch target register load optimization is not intended "
1571 "to be run twice");
1573 warned = 1;
1576 branch_target_load_optimize (epilogue_completed);
1577 return 0;
1580 namespace {
1582 const pass_data pass_data_branch_target_load_optimize2 =
1584 RTL_PASS, /* type */
1585 "btl2", /* name */
1586 OPTGROUP_NONE, /* optinfo_flags */
1587 true, /* has_gate */
1588 true, /* has_execute */
1589 TV_NONE, /* tv_id */
1590 0, /* properties_required */
1591 0, /* properties_provided */
1592 0, /* properties_destroyed */
1593 0, /* todo_flags_start */
1594 0, /* todo_flags_finish */
1597 class pass_branch_target_load_optimize2 : public rtl_opt_pass
1599 public:
1600 pass_branch_target_load_optimize2 (gcc::context *ctxt)
1601 : rtl_opt_pass (pass_data_branch_target_load_optimize2, ctxt)
1604 /* opt_pass methods: */
1605 bool gate () { return gate_handle_branch_target_load_optimize2 (); }
1606 unsigned int execute () {
1607 return rest_of_handle_branch_target_load_optimize2 ();
1610 }; // class pass_branch_target_load_optimize2
1612 } // anon namespace
1614 rtl_opt_pass *
1615 make_pass_branch_target_load_optimize2 (gcc::context *ctxt)
1617 return new pass_branch_target_load_optimize2 (ctxt);