]>
Commit | Line | Data |
---|---|---|
2b4e6bf1 | 1 | |
fe3ad572 | 2 | /* Perform branch target register load optimizations. |
5624e564 | 3 | Copyright (C) 2001-2015 Free Software Foundation, Inc. |
fe3ad572 SC |
4 | |
5 | This file is part of GCC. | |
6 | ||
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 | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
fe3ad572 SC |
10 | version. |
11 | ||
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. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
fe3ad572 SC |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
fe3ad572 SC |
25 | #include "rtl.h" |
26 | #include "hard-reg-set.h" | |
fe3ad572 | 27 | #include "regs.h" |
fe3ad572 | 28 | #include "target.h" |
40e23961 | 29 | #include "symtab.h" |
fe3ad572 SC |
30 | #include "expr.h" |
31 | #include "flags.h" | |
32 | #include "insn-attr.h" | |
83685514 AM |
33 | #include "hashtab.h" |
34 | #include "hash-set.h" | |
35 | #include "vec.h" | |
36 | #include "machmode.h" | |
37 | #include "input.h" | |
fe3ad572 | 38 | #include "function.h" |
1194fc79 | 39 | #include "except.h" |
8f7193b8 | 40 | #include "tm_p.h" |
718f9c0f | 41 | #include "diagnostic-core.h" |
ef330312 | 42 | #include "tree-pass.h" |
6fb5fa3c | 43 | #include "recog.h" |
60393bbc AM |
44 | #include "dominance.h" |
45 | #include "cfg.h" | |
46 | #include "cfgrtl.h" | |
47 | #include "cfganal.h" | |
48 | #include "cfgcleanup.h" | |
49 | #include "predict.h" | |
50 | #include "basic-block.h" | |
6fb5fa3c | 51 | #include "df.h" |
391886c8 | 52 | #include "cfgloop.h" |
b8ec23ac | 53 | #include "rtl-iter.h" |
b5bfe5bd | 54 | #include "fibonacci_heap.h" |
fe3ad572 SC |
55 | |
56 | /* Target register optimizations - these are performed after reload. */ | |
57 | ||
58 | typedef struct btr_def_group_s | |
59 | { | |
60 | struct btr_def_group_s *next; | |
61 | rtx src; | |
62 | struct btr_def_s *members; | |
63 | } *btr_def_group; | |
64 | ||
65 | typedef struct btr_user_s | |
66 | { | |
67 | struct btr_user_s *next; | |
68 | basic_block bb; | |
69 | int luid; | |
fd6657fb | 70 | rtx_insn *insn; |
fe3ad572 SC |
71 | /* If INSN has a single use of a single branch register, then |
72 | USE points to it within INSN. If there is more than | |
73 | one branch register use, or the use is in some way ambiguous, | |
74 | then USE is NULL. */ | |
75 | rtx use; | |
76 | int n_reaching_defs; | |
77 | int first_reaching_def; | |
78 | char other_use_this_block; | |
79 | } *btr_user; | |
80 | ||
81 | /* btr_def structs appear on three lists: | |
82 | 1. A list of all btr_def structures (head is | |
83 | ALL_BTR_DEFS, linked by the NEXT field). | |
84 | 2. A list of branch reg definitions per basic block (head is | |
85 | BB_BTR_DEFS[i], linked by the NEXT_THIS_BB field). | |
86 | 3. A list of all branch reg definitions belonging to the same | |
87 | group (head is in a BTR_DEF_GROUP struct, linked by | |
88 | NEXT_THIS_GROUP field). */ | |
89 | ||
90 | typedef struct btr_def_s | |
91 | { | |
92 | struct btr_def_s *next_this_bb; | |
93 | struct btr_def_s *next_this_group; | |
94 | basic_block bb; | |
95 | int luid; | |
fd6657fb | 96 | rtx_insn *insn; |
fe3ad572 SC |
97 | int btr; |
98 | int cost; | |
99 | /* For a branch register setting insn that has a constant | |
100 | source (i.e. a label), group links together all the | |
101 | insns with the same source. For other branch register | |
102 | setting insns, group is NULL. */ | |
103 | btr_def_group group; | |
104 | btr_user uses; | |
105 | /* If this def has a reaching use which is not a simple use | |
106 | in a branch instruction, then has_ambiguous_use will be true, | |
f9da5064 | 107 | and we will not attempt to migrate this definition. */ |
fe3ad572 SC |
108 | char has_ambiguous_use; |
109 | /* live_range is an approximation to the true live range for this | |
110 | def/use web, because it records the set of blocks that contain | |
111 | the live range. There could be other live ranges for the same | |
112 | branch register in that set of blocks, either in the block | |
113 | containing the def (before the def), or in a block containing | |
114 | a use (after the use). If there are such other live ranges, then | |
115 | other_btr_uses_before_def or other_btr_uses_after_use must be set true | |
71c0e7fc | 116 | as appropriate. */ |
fe3ad572 SC |
117 | char other_btr_uses_before_def; |
118 | char other_btr_uses_after_use; | |
ff8b369a R |
119 | /* We set own_end when we have moved a definition into a dominator. |
120 | Thus, when a later combination removes this definition again, we know | |
121 | to clear out trs_live_at_end again. */ | |
122 | char own_end; | |
fe3ad572 SC |
123 | bitmap live_range; |
124 | } *btr_def; | |
125 | ||
b5bfe5bd ML |
126 | typedef fibonacci_heap <long, btr_def_s> btr_heap_t; |
127 | typedef fibonacci_node <long, btr_def_s> btr_heap_node_t; | |
128 | ||
fe3ad572 SC |
129 | static int issue_rate; |
130 | ||
ed7a4b4b | 131 | static int basic_block_freq (const_basic_block); |
fd6657fb | 132 | static int insn_sets_btr_p (const rtx_insn *, int, int *); |
fe3ad572 | 133 | static void find_btr_def_group (btr_def_group *, btr_def); |
b5bfe5bd | 134 | static btr_def add_btr_def (btr_heap_t *, basic_block, int, rtx_insn *, |
fe3ad572 | 135 | unsigned int, int, btr_def_group *); |
fd6657fb | 136 | static btr_user new_btr_user (basic_block, int, rtx_insn *); |
fe3ad572 SC |
137 | static void dump_hard_reg_set (HARD_REG_SET); |
138 | static void dump_btrs_live (int); | |
139 | static void note_other_use_this_block (unsigned int, btr_user); | |
b5bfe5bd | 140 | static void compute_defs_uses_and_gen (btr_heap_t *, btr_def *,btr_user *, |
fe3ad572 SC |
141 | sbitmap *, sbitmap *, HARD_REG_SET *); |
142 | static void compute_kill (sbitmap *, sbitmap *, HARD_REG_SET *); | |
143 | static void compute_out (sbitmap *bb_out, sbitmap *, sbitmap *, int); | |
144 | static void link_btr_uses (btr_def *, btr_user *, sbitmap *, sbitmap *, int); | |
b5bfe5bd | 145 | static void build_btr_def_use_webs (btr_heap_t *); |
fe3ad572 SC |
146 | static int block_at_edge_of_live_range_p (int, btr_def); |
147 | static void clear_btr_from_live_range (btr_def def); | |
ff8b369a | 148 | static void add_btr_to_live_range (btr_def, int); |
fe3ad572 | 149 | static void augment_live_range (bitmap, HARD_REG_SET *, basic_block, |
ff8b369a | 150 | basic_block, int); |
fe3ad572 SC |
151 | static int choose_btr (HARD_REG_SET); |
152 | static void combine_btr_defs (btr_def, HARD_REG_SET *); | |
153 | static void btr_def_live_range (btr_def, HARD_REG_SET *); | |
154 | static void move_btr_def (basic_block, int, btr_def, bitmap, HARD_REG_SET *); | |
155 | static int migrate_btr_def (btr_def, int); | |
156 | static void migrate_btr_defs (enum reg_class, int); | |
fd6657fb | 157 | static int can_move_up (const_basic_block, const rtx_insn *, int); |
7bc980e1 | 158 | static void note_btr_set (rtx, const_rtx, void *); |
fe3ad572 SC |
159 | \f |
160 | /* The following code performs code motion of target load instructions | |
161 | (instructions that set branch target registers), to move them | |
162 | forward away from the branch instructions and out of loops (or, | |
163 | more generally, from a more frequently executed place to a less | |
164 | frequently executed place). | |
165 | Moving target load instructions further in front of the branch | |
166 | instruction that uses the target register value means that the hardware | |
167 | has a better chance of preloading the instructions at the branch | |
168 | target by the time the branch is reached. This avoids bubbles | |
169 | when a taken branch needs to flush out the pipeline. | |
170 | Moving target load instructions out of loops means they are executed | |
171 | less frequently. */ | |
172 | ||
173 | /* An obstack to hold the def-use web data structures built up for | |
174 | migrating branch target load instructions. */ | |
175 | static struct obstack migrate_btrl_obstack; | |
176 | ||
fe3ad572 SC |
177 | /* Array indexed by basic block number, giving the set of registers |
178 | live in that block. */ | |
179 | static HARD_REG_SET *btrs_live; | |
180 | ||
1194fc79 R |
181 | /* Array indexed by basic block number, giving the set of registers live at |
182 | the end of that block, including any uses by a final jump insn, if any. */ | |
183 | static HARD_REG_SET *btrs_live_at_end; | |
184 | ||
fe3ad572 SC |
185 | /* Set of all target registers that we are willing to allocate. */ |
186 | static HARD_REG_SET all_btrs; | |
187 | ||
188 | /* Provide lower and upper bounds for target register numbers, so that | |
189 | we don't need to search through all the hard registers all the time. */ | |
190 | static int first_btr, last_btr; | |
191 | ||
192 | ||
193 | ||
1194fc79 | 194 | /* Return an estimate of the frequency of execution of block bb. */ |
fe3ad572 | 195 | static int |
ed7a4b4b | 196 | basic_block_freq (const_basic_block bb) |
fe3ad572 SC |
197 | { |
198 | return bb->frequency; | |
199 | } | |
200 | ||
b8ec23ac RS |
201 | /* If X references (sets or reads) any branch target register, return one |
202 | such register. If EXCLUDEP is set, disregard any references within | |
203 | that location. */ | |
204 | static rtx * | |
205 | find_btr_use (rtx x, rtx *excludep = 0) | |
fe3ad572 | 206 | { |
b8ec23ac RS |
207 | subrtx_ptr_iterator::array_type array; |
208 | FOR_EACH_SUBRTX_PTR (iter, array, &x, NONCONST) | |
09e18274 | 209 | { |
b8ec23ac RS |
210 | rtx *loc = *iter; |
211 | if (loc == excludep) | |
212 | iter.skip_subrtxes (); | |
213 | else | |
214 | { | |
215 | const_rtx x = *loc; | |
216 | if (REG_P (x) | |
217 | && overlaps_hard_reg_set_p (all_btrs, GET_MODE (x), REGNO (x))) | |
218 | return loc; | |
219 | } | |
09e18274 | 220 | } |
b8ec23ac | 221 | return 0; |
fe3ad572 SC |
222 | } |
223 | ||
224 | /* Return true if insn is an instruction that sets a target register. | |
225 | if CHECK_CONST is true, only return true if the source is constant. | |
226 | If such a set is found and REGNO is nonzero, assign the register number | |
227 | of the destination register to *REGNO. */ | |
228 | static int | |
fd6657fb | 229 | insn_sets_btr_p (const rtx_insn *insn, int check_const, int *regno) |
fe3ad572 SC |
230 | { |
231 | rtx set; | |
232 | ||
4b4bf941 | 233 | if (NONJUMP_INSN_P (insn) |
fe3ad572 SC |
234 | && (set = single_set (insn))) |
235 | { | |
236 | rtx dest = SET_DEST (set); | |
237 | rtx src = SET_SRC (set); | |
238 | ||
239 | if (GET_CODE (dest) == SUBREG) | |
240 | dest = XEXP (dest, 0); | |
241 | ||
f8cfc6aa | 242 | if (REG_P (dest) |
fe3ad572 SC |
243 | && TEST_HARD_REG_BIT (all_btrs, REGNO (dest))) |
244 | { | |
b8ec23ac | 245 | gcc_assert (!find_btr_use (src)); |
c22cacf3 | 246 | |
fe3ad572 SC |
247 | if (!check_const || CONSTANT_P (src)) |
248 | { | |
249 | if (regno) | |
250 | *regno = REGNO (dest); | |
251 | return 1; | |
252 | } | |
253 | } | |
254 | } | |
255 | return 0; | |
256 | } | |
257 | ||
fe3ad572 SC |
258 | /* Find the group that the target register definition DEF belongs |
259 | to in the list starting with *ALL_BTR_DEF_GROUPS. If no such | |
260 | group exists, create one. Add def to the group. */ | |
261 | static void | |
262 | find_btr_def_group (btr_def_group *all_btr_def_groups, btr_def def) | |
263 | { | |
264 | if (insn_sets_btr_p (def->insn, 1, NULL)) | |
265 | { | |
266 | btr_def_group this_group; | |
267 | rtx def_src = SET_SRC (single_set (def->insn)); | |
268 | ||
269 | /* ?? This linear search is an efficiency concern, particularly | |
270 | as the search will almost always fail to find a match. */ | |
271 | for (this_group = *all_btr_def_groups; | |
272 | this_group != NULL; | |
273 | this_group = this_group->next) | |
274 | if (rtx_equal_p (def_src, this_group->src)) | |
275 | break; | |
276 | ||
277 | if (!this_group) | |
278 | { | |
f883e0a7 | 279 | this_group = XOBNEW (&migrate_btrl_obstack, struct btr_def_group_s); |
fe3ad572 SC |
280 | this_group->src = def_src; |
281 | this_group->members = NULL; | |
282 | this_group->next = *all_btr_def_groups; | |
283 | *all_btr_def_groups = this_group; | |
284 | } | |
285 | def->group = this_group; | |
286 | def->next_this_group = this_group->members; | |
287 | this_group->members = def; | |
288 | } | |
289 | else | |
290 | def->group = NULL; | |
291 | } | |
292 | ||
293 | /* Create a new target register definition structure, for a definition in | |
294 | block BB, instruction INSN, and insert it into ALL_BTR_DEFS. Return | |
295 | the new definition. */ | |
296 | static btr_def | |
b5bfe5bd | 297 | add_btr_def (btr_heap_t *all_btr_defs, basic_block bb, int insn_luid, |
fd6657fb | 298 | rtx_insn *insn, |
fe3ad572 SC |
299 | unsigned int dest_reg, int other_btr_uses_before_def, |
300 | btr_def_group *all_btr_def_groups) | |
301 | { | |
32e9fa48 KG |
302 | btr_def this_def = XOBNEW (&migrate_btrl_obstack, struct btr_def_s); |
303 | this_def->bb = bb; | |
304 | this_def->luid = insn_luid; | |
305 | this_def->insn = insn; | |
306 | this_def->btr = dest_reg; | |
307 | this_def->cost = basic_block_freq (bb); | |
308 | this_def->has_ambiguous_use = 0; | |
309 | this_def->other_btr_uses_before_def = other_btr_uses_before_def; | |
310 | this_def->other_btr_uses_after_use = 0; | |
311 | this_def->next_this_bb = NULL; | |
312 | this_def->next_this_group = NULL; | |
313 | this_def->uses = NULL; | |
314 | this_def->live_range = NULL; | |
315 | find_btr_def_group (all_btr_def_groups, this_def); | |
316 | ||
b5bfe5bd | 317 | all_btr_defs->insert (-this_def->cost, this_def); |
fe3ad572 | 318 | |
c263766c RH |
319 | if (dump_file) |
320 | fprintf (dump_file, | |
fe3ad572 | 321 | "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n", |
32e9fa48 KG |
322 | dest_reg, bb->index, INSN_UID (insn), |
323 | (this_def->group ? "" : ":not const"), this_def->cost); | |
fe3ad572 | 324 | |
32e9fa48 | 325 | return this_def; |
fe3ad572 SC |
326 | } |
327 | ||
328 | /* Create a new target register user structure, for a use in block BB, | |
329 | instruction INSN. Return the new user. */ | |
330 | static btr_user | |
fd6657fb | 331 | new_btr_user (basic_block bb, int insn_luid, rtx_insn *insn) |
fe3ad572 SC |
332 | { |
333 | /* This instruction reads target registers. We need | |
334 | to decide whether we can replace all target register | |
335 | uses easily. | |
336 | */ | |
337 | rtx *usep = find_btr_use (PATTERN (insn)); | |
338 | rtx use; | |
339 | btr_user user = NULL; | |
340 | ||
341 | if (usep) | |
342 | { | |
343 | int unambiguous_single_use; | |
344 | ||
345 | /* We want to ensure that USE is the only use of a target | |
346 | register in INSN, so that we know that to rewrite INSN to use | |
347 | a different target register, all we have to do is replace USE. */ | |
b8ec23ac | 348 | unambiguous_single_use = !find_btr_use (PATTERN (insn), usep); |
fe3ad572 SC |
349 | if (!unambiguous_single_use) |
350 | usep = NULL; | |
351 | } | |
352 | use = usep ? *usep : NULL_RTX; | |
f883e0a7 | 353 | user = XOBNEW (&migrate_btrl_obstack, struct btr_user_s); |
fe3ad572 SC |
354 | user->bb = bb; |
355 | user->luid = insn_luid; | |
356 | user->insn = insn; | |
357 | user->use = use; | |
358 | user->other_use_this_block = 0; | |
359 | user->next = NULL; | |
360 | user->n_reaching_defs = 0; | |
361 | user->first_reaching_def = -1; | |
362 | ||
c263766c | 363 | if (dump_file) |
fe3ad572 | 364 | { |
c263766c | 365 | fprintf (dump_file, "Uses target reg: { bb %d, insn %d }", |
fe3ad572 SC |
366 | bb->index, INSN_UID (insn)); |
367 | ||
368 | if (user->use) | |
c263766c | 369 | fprintf (dump_file, ": unambiguous use of reg %d\n", |
fe3ad572 SC |
370 | REGNO (user->use)); |
371 | } | |
372 | ||
373 | return user; | |
374 | } | |
375 | ||
71c0e7fc | 376 | /* Write the contents of S to the dump file. */ |
fe3ad572 SC |
377 | static void |
378 | dump_hard_reg_set (HARD_REG_SET s) | |
379 | { | |
380 | int reg; | |
381 | for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++) | |
382 | if (TEST_HARD_REG_BIT (s, reg)) | |
c263766c | 383 | fprintf (dump_file, " %d", reg); |
fe3ad572 SC |
384 | } |
385 | ||
71c0e7fc | 386 | /* Write the set of target regs live in block BB to the dump file. */ |
fe3ad572 SC |
387 | static void |
388 | dump_btrs_live (int bb) | |
389 | { | |
c263766c | 390 | fprintf (dump_file, "BB%d live:", bb); |
fe3ad572 | 391 | dump_hard_reg_set (btrs_live[bb]); |
c263766c | 392 | fprintf (dump_file, "\n"); |
fe3ad572 SC |
393 | } |
394 | ||
395 | /* REGNO is the number of a branch target register that is being used or | |
396 | set. USERS_THIS_BB is a list of preceding branch target register users; | |
397 | If any of them use the same register, set their other_use_this_block | |
398 | flag. */ | |
399 | static void | |
400 | note_other_use_this_block (unsigned int regno, btr_user users_this_bb) | |
401 | { | |
402 | btr_user user; | |
403 | ||
404 | for (user = users_this_bb; user != NULL; user = user->next) | |
405 | if (user->use && REGNO (user->use) == regno) | |
406 | user->other_use_this_block = 1; | |
407 | } | |
408 | ||
409 | typedef struct { | |
410 | btr_user users_this_bb; | |
411 | HARD_REG_SET btrs_written_in_block; | |
412 | HARD_REG_SET btrs_live_in_block; | |
413 | sbitmap bb_gen; | |
414 | sbitmap *btr_defset; | |
415 | } defs_uses_info; | |
416 | ||
417 | /* Called via note_stores or directly to register stores into / | |
418 | clobbers of a branch target register DEST that are not recognized as | |
419 | straightforward definitions. DATA points to information about the | |
f9da5064 | 420 | current basic block that needs updating. */ |
fe3ad572 | 421 | static void |
7bc980e1 | 422 | note_btr_set (rtx dest, const_rtx set ATTRIBUTE_UNUSED, void *data) |
fe3ad572 | 423 | { |
f883e0a7 | 424 | defs_uses_info *info = (defs_uses_info *) data; |
fe3ad572 SC |
425 | int regno, end_regno; |
426 | ||
f8cfc6aa | 427 | if (!REG_P (dest)) |
fe3ad572 SC |
428 | return; |
429 | regno = REGNO (dest); | |
09e18274 | 430 | end_regno = END_HARD_REGNO (dest); |
fe3ad572 SC |
431 | for (; regno < end_regno; regno++) |
432 | if (TEST_HARD_REG_BIT (all_btrs, regno)) | |
433 | { | |
434 | note_other_use_this_block (regno, info->users_this_bb); | |
435 | SET_HARD_REG_BIT (info->btrs_written_in_block, regno); | |
436 | SET_HARD_REG_BIT (info->btrs_live_in_block, regno); | |
f61e445a | 437 | bitmap_and_compl (info->bb_gen, info->bb_gen, |
fe3ad572 SC |
438 | info->btr_defset[regno - first_btr]); |
439 | } | |
440 | } | |
441 | ||
442 | static void | |
b5bfe5bd | 443 | compute_defs_uses_and_gen (btr_heap_t *all_btr_defs, btr_def *def_array, |
fe3ad572 SC |
444 | btr_user *use_array, sbitmap *btr_defset, |
445 | sbitmap *bb_gen, HARD_REG_SET *btrs_written) | |
446 | { | |
447 | /* Scan the code building up the set of all defs and all uses. | |
448 | For each target register, build the set of defs of that register. | |
449 | For each block, calculate the set of target registers | |
450 | written in that block. | |
451 | Also calculate the set of btrs ever live in that block. | |
452 | */ | |
453 | int i; | |
454 | int insn_luid = 0; | |
455 | btr_def_group all_btr_def_groups = NULL; | |
456 | defs_uses_info info; | |
457 | ||
8b1c6fd7 DM |
458 | bitmap_vector_clear (bb_gen, last_basic_block_for_fn (cfun)); |
459 | for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++) | |
fe3ad572 | 460 | { |
06e28de2 | 461 | basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i); |
fe3ad572 SC |
462 | int reg; |
463 | btr_def defs_this_bb = NULL; | |
fd6657fb DM |
464 | rtx_insn *insn; |
465 | rtx_insn *last; | |
1194fc79 | 466 | int can_throw = 0; |
fe3ad572 SC |
467 | |
468 | info.users_this_bb = NULL; | |
469 | info.bb_gen = bb_gen[i]; | |
470 | info.btr_defset = btr_defset; | |
471 | ||
472 | CLEAR_HARD_REG_SET (info.btrs_live_in_block); | |
473 | CLEAR_HARD_REG_SET (info.btrs_written_in_block); | |
474 | for (reg = first_btr; reg <= last_btr; reg++) | |
475 | if (TEST_HARD_REG_BIT (all_btrs, reg) | |
89a95777 | 476 | && REGNO_REG_SET_P (df_get_live_in (bb), reg)) |
fe3ad572 SC |
477 | SET_HARD_REG_BIT (info.btrs_live_in_block, reg); |
478 | ||
a813c111 | 479 | for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); |
fe3ad572 SC |
480 | insn != last; |
481 | insn = NEXT_INSN (insn), insn_luid++) | |
482 | { | |
483 | if (INSN_P (insn)) | |
484 | { | |
485 | int regno; | |
486 | int insn_uid = INSN_UID (insn); | |
487 | ||
488 | if (insn_sets_btr_p (insn, 0, ®no)) | |
489 | { | |
490 | btr_def def = add_btr_def ( | |
491 | all_btr_defs, bb, insn_luid, insn, regno, | |
492 | TEST_HARD_REG_BIT (info.btrs_live_in_block, regno), | |
493 | &all_btr_def_groups); | |
494 | ||
495 | def_array[insn_uid] = def; | |
496 | SET_HARD_REG_BIT (info.btrs_written_in_block, regno); | |
497 | SET_HARD_REG_BIT (info.btrs_live_in_block, regno); | |
f61e445a | 498 | bitmap_and_compl (bb_gen[i], bb_gen[i], |
fe3ad572 | 499 | btr_defset[regno - first_btr]); |
d7c028c0 | 500 | bitmap_set_bit (bb_gen[i], insn_uid); |
fe3ad572 SC |
501 | def->next_this_bb = defs_this_bb; |
502 | defs_this_bb = def; | |
d7c028c0 | 503 | bitmap_set_bit (btr_defset[regno - first_btr], insn_uid); |
fe3ad572 SC |
504 | note_other_use_this_block (regno, info.users_this_bb); |
505 | } | |
2d6c85d3 | 506 | /* Check for the blockage emitted by expand_nl_goto_receiver. */ |
e3b5732b | 507 | else if (cfun->has_nonlocal_label |
6fb5fa3c | 508 | && GET_CODE (PATTERN (insn)) == UNSPEC_VOLATILE) |
2d6c85d3 R |
509 | { |
510 | btr_user user; | |
511 | ||
512 | /* Do the equivalent of calling note_other_use_this_block | |
513 | for every target register. */ | |
514 | for (user = info.users_this_bb; user != NULL; | |
515 | user = user->next) | |
516 | if (user->use) | |
517 | user->other_use_this_block = 1; | |
518 | IOR_HARD_REG_SET (info.btrs_written_in_block, all_btrs); | |
519 | IOR_HARD_REG_SET (info.btrs_live_in_block, all_btrs); | |
f61e445a | 520 | bitmap_clear (info.bb_gen); |
2d6c85d3 | 521 | } |
fe3ad572 SC |
522 | else |
523 | { | |
b8ec23ac | 524 | if (find_btr_use (PATTERN (insn))) |
fe3ad572 SC |
525 | { |
526 | btr_user user = new_btr_user (bb, insn_luid, insn); | |
527 | ||
528 | use_array[insn_uid] = user; | |
529 | if (user->use) | |
530 | SET_HARD_REG_BIT (info.btrs_live_in_block, | |
531 | REGNO (user->use)); | |
532 | else | |
533 | { | |
534 | int reg; | |
535 | for (reg = first_btr; reg <= last_btr; reg++) | |
536 | if (TEST_HARD_REG_BIT (all_btrs, reg) | |
c9bd6bcd | 537 | && refers_to_regno_p (reg, user->insn)) |
fe3ad572 SC |
538 | { |
539 | note_other_use_this_block (reg, | |
540 | info.users_this_bb); | |
541 | SET_HARD_REG_BIT (info.btrs_live_in_block, reg); | |
542 | } | |
543 | note_stores (PATTERN (insn), note_btr_set, &info); | |
544 | } | |
545 | user->next = info.users_this_bb; | |
546 | info.users_this_bb = user; | |
547 | } | |
4b4bf941 | 548 | if (CALL_P (insn)) |
fe3ad572 SC |
549 | { |
550 | HARD_REG_SET *clobbered = &call_used_reg_set; | |
551 | HARD_REG_SET call_saved; | |
552 | rtx pat = PATTERN (insn); | |
553 | int i; | |
554 | ||
555 | /* Check for sibcall. */ | |
556 | if (GET_CODE (pat) == PARALLEL) | |
557 | for (i = XVECLEN (pat, 0) - 1; i >= 0; i--) | |
26898771 | 558 | if (ANY_RETURN_P (XVECEXP (pat, 0, i))) |
fe3ad572 SC |
559 | { |
560 | COMPL_HARD_REG_SET (call_saved, | |
561 | call_used_reg_set); | |
562 | clobbered = &call_saved; | |
563 | } | |
1194fc79 | 564 | |
fe3ad572 SC |
565 | for (regno = first_btr; regno <= last_btr; regno++) |
566 | if (TEST_HARD_REG_BIT (*clobbered, regno)) | |
567 | note_btr_set (regno_reg_rtx[regno], NULL_RTX, &info); | |
568 | } | |
569 | } | |
570 | } | |
571 | } | |
572 | ||
573 | COPY_HARD_REG_SET (btrs_live[i], info.btrs_live_in_block); | |
574 | COPY_HARD_REG_SET (btrs_written[i], info.btrs_written_in_block); | |
1194fc79 | 575 | |
89a95777 | 576 | REG_SET_TO_HARD_REG_SET (btrs_live_at_end[i], df_get_live_out (bb)); |
1194fc79 R |
577 | /* If this block ends in a jump insn, add any uses or even clobbers |
578 | of branch target registers that it might have. */ | |
579 | for (insn = BB_END (bb); insn != BB_HEAD (bb) && ! INSN_P (insn); ) | |
580 | insn = PREV_INSN (insn); | |
581 | /* ??? for the fall-through edge, it would make sense to insert the | |
582 | btr set on the edge, but that would require to split the block | |
583 | early on so that we can distinguish between dominance from the fall | |
584 | through edge - which can use the call-clobbered registers - from | |
585 | dominance by the throw edge. */ | |
586 | if (can_throw_internal (insn)) | |
587 | { | |
588 | HARD_REG_SET tmp; | |
589 | ||
590 | COPY_HARD_REG_SET (tmp, call_used_reg_set); | |
591 | AND_HARD_REG_SET (tmp, all_btrs); | |
592 | IOR_HARD_REG_SET (btrs_live_at_end[i], tmp); | |
593 | can_throw = 1; | |
594 | } | |
4b4bf941 | 595 | if (can_throw || JUMP_P (insn)) |
1194fc79 R |
596 | { |
597 | int regno; | |
598 | ||
599 | for (regno = first_btr; regno <= last_btr; regno++) | |
c9bd6bcd | 600 | if (refers_to_regno_p (regno, insn)) |
1194fc79 R |
601 | SET_HARD_REG_BIT (btrs_live_at_end[i], regno); |
602 | } | |
603 | ||
c263766c | 604 | if (dump_file) |
c3284718 | 605 | dump_btrs_live (i); |
fe3ad572 SC |
606 | } |
607 | } | |
608 | ||
609 | static void | |
610 | compute_kill (sbitmap *bb_kill, sbitmap *btr_defset, | |
611 | HARD_REG_SET *btrs_written) | |
612 | { | |
613 | int i; | |
614 | int regno; | |
615 | ||
616 | /* For each basic block, form the set BB_KILL - the set | |
71c0e7fc | 617 | of definitions that the block kills. */ |
8b1c6fd7 DM |
618 | bitmap_vector_clear (bb_kill, last_basic_block_for_fn (cfun)); |
619 | for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++) | |
fe3ad572 SC |
620 | { |
621 | for (regno = first_btr; regno <= last_btr; regno++) | |
622 | if (TEST_HARD_REG_BIT (all_btrs, regno) | |
623 | && TEST_HARD_REG_BIT (btrs_written[i], regno)) | |
f61e445a | 624 | bitmap_ior (bb_kill[i], bb_kill[i], |
fe3ad572 SC |
625 | btr_defset[regno - first_btr]); |
626 | } | |
627 | } | |
628 | ||
629 | static void | |
630 | compute_out (sbitmap *bb_out, sbitmap *bb_gen, sbitmap *bb_kill, int max_uid) | |
631 | { | |
632 | /* Perform iterative dataflow: | |
633 | Initially, for all blocks, BB_OUT = BB_GEN. | |
634 | For each block, | |
635 | BB_IN = union over predecessors of BB_OUT(pred) | |
636 | BB_OUT = (BB_IN - BB_KILL) + BB_GEN | |
f9da5064 | 637 | Iterate until the bb_out sets stop growing. */ |
fe3ad572 SC |
638 | int i; |
639 | int changed; | |
640 | sbitmap bb_in = sbitmap_alloc (max_uid); | |
641 | ||
8b1c6fd7 | 642 | for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++) |
f61e445a | 643 | bitmap_copy (bb_out[i], bb_gen[i]); |
fe3ad572 SC |
644 | |
645 | changed = 1; | |
646 | while (changed) | |
647 | { | |
648 | changed = 0; | |
8b1c6fd7 | 649 | for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++) |
fe3ad572 | 650 | { |
06e28de2 | 651 | bitmap_union_of_preds (bb_in, bb_out, BASIC_BLOCK_FOR_FN (cfun, i)); |
f61e445a | 652 | changed |= bitmap_ior_and_compl (bb_out[i], bb_gen[i], |
fe3ad572 SC |
653 | bb_in, bb_kill[i]); |
654 | } | |
655 | } | |
656 | sbitmap_free (bb_in); | |
657 | } | |
658 | ||
659 | static void | |
660 | link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out, | |
661 | sbitmap *btr_defset, int max_uid) | |
662 | { | |
663 | int i; | |
664 | sbitmap reaching_defs = sbitmap_alloc (max_uid); | |
665 | ||
666 | /* Link uses to the uses lists of all of their reaching defs. | |
71c0e7fc | 667 | Count up the number of reaching defs of each use. */ |
8b1c6fd7 | 668 | for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++) |
fe3ad572 | 669 | { |
06e28de2 | 670 | basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i); |
fd6657fb DM |
671 | rtx_insn *insn; |
672 | rtx_insn *last; | |
fe3ad572 | 673 | |
06e28de2 | 674 | bitmap_union_of_preds (reaching_defs, bb_out, BASIC_BLOCK_FOR_FN (cfun, i)); |
a813c111 | 675 | for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); |
fe3ad572 SC |
676 | insn != last; |
677 | insn = NEXT_INSN (insn)) | |
678 | { | |
679 | if (INSN_P (insn)) | |
680 | { | |
681 | int insn_uid = INSN_UID (insn); | |
682 | ||
683 | btr_def def = def_array[insn_uid]; | |
684 | btr_user user = use_array[insn_uid]; | |
685 | if (def != NULL) | |
686 | { | |
687 | /* Remove all reaching defs of regno except | |
71c0e7fc | 688 | for this one. */ |
f61e445a | 689 | bitmap_and_compl (reaching_defs, reaching_defs, |
fe3ad572 | 690 | btr_defset[def->btr - first_btr]); |
c3284718 | 691 | bitmap_set_bit (reaching_defs, insn_uid); |
fe3ad572 SC |
692 | } |
693 | ||
694 | if (user != NULL) | |
695 | { | |
f9da5064 | 696 | /* Find all the reaching defs for this use. */ |
c3284718 | 697 | sbitmap reaching_defs_of_reg = sbitmap_alloc (max_uid); |
dfea6c85 | 698 | unsigned int uid = 0; |
b6e7e9af | 699 | sbitmap_iterator sbi; |
fe3ad572 SC |
700 | |
701 | if (user->use) | |
f61e445a | 702 | bitmap_and ( |
fe3ad572 SC |
703 | reaching_defs_of_reg, |
704 | reaching_defs, | |
705 | btr_defset[REGNO (user->use) - first_btr]); | |
706 | else | |
707 | { | |
708 | int reg; | |
709 | ||
f61e445a | 710 | bitmap_clear (reaching_defs_of_reg); |
fe3ad572 SC |
711 | for (reg = first_btr; reg <= last_btr; reg++) |
712 | if (TEST_HARD_REG_BIT (all_btrs, reg) | |
c9bd6bcd | 713 | && refers_to_regno_p (reg, user->insn)) |
f61e445a | 714 | bitmap_or_and (reaching_defs_of_reg, |
fe3ad572 SC |
715 | reaching_defs_of_reg, |
716 | reaching_defs, | |
717 | btr_defset[reg - first_btr]); | |
718 | } | |
d4ac4ce2 | 719 | EXECUTE_IF_SET_IN_BITMAP (reaching_defs_of_reg, 0, uid, sbi) |
fe3ad572 SC |
720 | { |
721 | btr_def def = def_array[uid]; | |
722 | ||
f9da5064 | 723 | /* We now know that def reaches user. */ |
fe3ad572 | 724 | |
c263766c RH |
725 | if (dump_file) |
726 | fprintf (dump_file, | |
fe3ad572 SC |
727 | "Def in insn %d reaches use in insn %d\n", |
728 | uid, insn_uid); | |
729 | ||
730 | user->n_reaching_defs++; | |
731 | if (!user->use) | |
732 | def->has_ambiguous_use = 1; | |
733 | if (user->first_reaching_def != -1) | |
734 | { /* There is more than one reaching def. This is | |
735 | a rare case, so just give up on this def/use | |
71c0e7fc | 736 | web when it occurs. */ |
fe3ad572 SC |
737 | def->has_ambiguous_use = 1; |
738 | def_array[user->first_reaching_def] | |
739 | ->has_ambiguous_use = 1; | |
c263766c RH |
740 | if (dump_file) |
741 | fprintf (dump_file, | |
fe3ad572 SC |
742 | "(use %d has multiple reaching defs)\n", |
743 | insn_uid); | |
744 | } | |
745 | else | |
746 | user->first_reaching_def = uid; | |
747 | if (user->other_use_this_block) | |
748 | def->other_btr_uses_after_use = 1; | |
749 | user->next = def->uses; | |
750 | def->uses = user; | |
b6e7e9af | 751 | } |
fe3ad572 SC |
752 | sbitmap_free (reaching_defs_of_reg); |
753 | } | |
754 | ||
4b4bf941 | 755 | if (CALL_P (insn)) |
fe3ad572 SC |
756 | { |
757 | int regno; | |
758 | ||
759 | for (regno = first_btr; regno <= last_btr; regno++) | |
760 | if (TEST_HARD_REG_BIT (all_btrs, regno) | |
761 | && TEST_HARD_REG_BIT (call_used_reg_set, regno)) | |
f61e445a | 762 | bitmap_and_compl (reaching_defs, reaching_defs, |
fe3ad572 SC |
763 | btr_defset[regno - first_btr]); |
764 | } | |
765 | } | |
766 | } | |
767 | } | |
768 | sbitmap_free (reaching_defs); | |
769 | } | |
770 | ||
771 | static void | |
b5bfe5bd | 772 | build_btr_def_use_webs (btr_heap_t *all_btr_defs) |
fe3ad572 SC |
773 | { |
774 | const int max_uid = get_max_uid (); | |
5ed6ace5 MD |
775 | btr_def *def_array = XCNEWVEC (btr_def, max_uid); |
776 | btr_user *use_array = XCNEWVEC (btr_user, max_uid); | |
fe3ad572 SC |
777 | sbitmap *btr_defset = sbitmap_vector_alloc ( |
778 | (last_btr - first_btr) + 1, max_uid); | |
8b1c6fd7 DM |
779 | sbitmap *bb_gen = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), |
780 | max_uid); | |
781 | HARD_REG_SET *btrs_written = XCNEWVEC (HARD_REG_SET, | |
782 | last_basic_block_for_fn (cfun)); | |
fe3ad572 SC |
783 | sbitmap *bb_kill; |
784 | sbitmap *bb_out; | |
785 | ||
f61e445a | 786 | bitmap_vector_clear (btr_defset, (last_btr - first_btr) + 1); |
fe3ad572 SC |
787 | |
788 | compute_defs_uses_and_gen (all_btr_defs, def_array, use_array, btr_defset, | |
789 | bb_gen, btrs_written); | |
790 | ||
8b1c6fd7 | 791 | bb_kill = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), max_uid); |
fe3ad572 SC |
792 | compute_kill (bb_kill, btr_defset, btrs_written); |
793 | free (btrs_written); | |
794 | ||
8b1c6fd7 | 795 | bb_out = sbitmap_vector_alloc (last_basic_block_for_fn (cfun), max_uid); |
fe3ad572 SC |
796 | compute_out (bb_out, bb_gen, bb_kill, max_uid); |
797 | ||
798 | sbitmap_vector_free (bb_gen); | |
799 | sbitmap_vector_free (bb_kill); | |
800 | ||
801 | link_btr_uses (def_array, use_array, bb_out, btr_defset, max_uid); | |
802 | ||
803 | sbitmap_vector_free (bb_out); | |
804 | sbitmap_vector_free (btr_defset); | |
805 | free (use_array); | |
806 | free (def_array); | |
807 | } | |
808 | ||
809 | /* Return true if basic block BB contains the start or end of the | |
810 | live range of the definition DEF, AND there are other live | |
811 | ranges of the same target register that include BB. */ | |
812 | static int | |
813 | block_at_edge_of_live_range_p (int bb, btr_def def) | |
814 | { | |
06e28de2 DM |
815 | if (def->other_btr_uses_before_def |
816 | && BASIC_BLOCK_FOR_FN (cfun, bb) == def->bb) | |
fe3ad572 SC |
817 | return 1; |
818 | else if (def->other_btr_uses_after_use) | |
819 | { | |
820 | btr_user user; | |
821 | for (user = def->uses; user != NULL; user = user->next) | |
06e28de2 | 822 | if (BASIC_BLOCK_FOR_FN (cfun, bb) == user->bb) |
fe3ad572 SC |
823 | return 1; |
824 | } | |
825 | return 0; | |
826 | } | |
827 | ||
828 | /* We are removing the def/use web DEF. The target register | |
829 | used in this web is therefore no longer live in the live range | |
830 | of this web, so remove it from the live set of all basic blocks | |
831 | in the live range of the web. | |
832 | Blocks at the boundary of the live range may contain other live | |
833 | ranges for the same target register, so we have to be careful | |
834 | to remove the target register from the live set of these blocks | |
71c0e7fc | 835 | only if they do not contain other live ranges for the same register. */ |
fe3ad572 SC |
836 | static void |
837 | clear_btr_from_live_range (btr_def def) | |
838 | { | |
3cd8c58a | 839 | unsigned bb; |
87c476a2 | 840 | bitmap_iterator bi; |
fe3ad572 | 841 | |
87c476a2 ZD |
842 | EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi) |
843 | { | |
844 | if ((!def->other_btr_uses_before_def | |
845 | && !def->other_btr_uses_after_use) | |
846 | || !block_at_edge_of_live_range_p (bb, def)) | |
847 | { | |
848 | CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr); | |
849 | CLEAR_HARD_REG_BIT (btrs_live_at_end[bb], def->btr); | |
850 | if (dump_file) | |
851 | dump_btrs_live (bb); | |
852 | } | |
853 | } | |
ff8b369a R |
854 | if (def->own_end) |
855 | CLEAR_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr); | |
fe3ad572 SC |
856 | } |
857 | ||
858 | ||
859 | /* We are adding the def/use web DEF. Add the target register used | |
860 | in this web to the live set of all of the basic blocks that contain | |
ff8b369a R |
861 | the live range of the web. |
862 | If OWN_END is set, also show that the register is live from our | |
863 | definitions at the end of the basic block where it is defined. */ | |
fe3ad572 | 864 | static void |
ff8b369a | 865 | add_btr_to_live_range (btr_def def, int own_end) |
fe3ad572 | 866 | { |
3cd8c58a | 867 | unsigned bb; |
87c476a2 ZD |
868 | bitmap_iterator bi; |
869 | ||
870 | EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi) | |
871 | { | |
872 | SET_HARD_REG_BIT (btrs_live[bb], def->btr); | |
873 | SET_HARD_REG_BIT (btrs_live_at_end[bb], def->btr); | |
874 | if (dump_file) | |
875 | dump_btrs_live (bb); | |
876 | } | |
ff8b369a R |
877 | if (own_end) |
878 | { | |
879 | SET_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr); | |
880 | def->own_end = 1; | |
881 | } | |
fe3ad572 SC |
882 | } |
883 | ||
884 | /* Update a live range to contain the basic block NEW_BLOCK, and all | |
885 | blocks on paths between the existing live range and NEW_BLOCK. | |
886 | HEAD is a block contained in the existing live range that dominates | |
887 | all other blocks in the existing live range. | |
888 | Also add to the set BTRS_LIVE_IN_RANGE all target registers that | |
889 | are live in the blocks that we add to the live range. | |
ff8b369a R |
890 | If FULL_RANGE is set, include the full live range of NEW_BB; |
891 | otherwise, if NEW_BB dominates HEAD_BB, only add registers that | |
892 | are life at the end of NEW_BB for NEW_BB itself. | |
fe3ad572 SC |
893 | It is a precondition that either NEW_BLOCK dominates HEAD,or |
894 | HEAD dom NEW_BLOCK. This is used to speed up the | |
895 | implementation of this function. */ | |
896 | static void | |
897 | augment_live_range (bitmap live_range, HARD_REG_SET *btrs_live_in_range, | |
ff8b369a | 898 | basic_block head_bb, basic_block new_bb, int full_range) |
fe3ad572 SC |
899 | { |
900 | basic_block *worklist, *tos; | |
901 | ||
0cae8d31 | 902 | tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1); |
fe3ad572 | 903 | |
d47cc544 | 904 | if (dominated_by_p (CDI_DOMINATORS, new_bb, head_bb)) |
ff8b369a R |
905 | { |
906 | if (new_bb == head_bb) | |
907 | { | |
908 | if (full_range) | |
909 | IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_bb->index]); | |
a14df7da | 910 | free (tos); |
ff8b369a R |
911 | return; |
912 | } | |
913 | *tos++ = new_bb; | |
914 | } | |
298e6adc | 915 | else |
fe3ad572 SC |
916 | { |
917 | edge e; | |
628f6a4e | 918 | edge_iterator ei; |
fe3ad572 SC |
919 | int new_block = new_bb->index; |
920 | ||
298e6adc | 921 | gcc_assert (dominated_by_p (CDI_DOMINATORS, head_bb, new_bb)); |
c22cacf3 | 922 | |
ff8b369a | 923 | IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[head_bb->index]); |
fe3ad572 | 924 | bitmap_set_bit (live_range, new_block); |
ff8b369a | 925 | /* A previous btr migration could have caused a register to be |
c22cacf3 MS |
926 | live just at the end of new_block which we need in full, so |
927 | use trs_live_at_end even if full_range is set. */ | |
ff8b369a R |
928 | IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live_at_end[new_block]); |
929 | if (full_range) | |
1194fc79 | 930 | IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]); |
c263766c | 931 | if (dump_file) |
fe3ad572 | 932 | { |
c263766c | 933 | fprintf (dump_file, |
1194fc79 R |
934 | "Adding end of block %d and rest of %d to live range\n", |
935 | new_block, head_bb->index); | |
c263766c | 936 | fprintf (dump_file,"Now live btrs are "); |
fe3ad572 | 937 | dump_hard_reg_set (*btrs_live_in_range); |
c263766c | 938 | fprintf (dump_file, "\n"); |
fe3ad572 | 939 | } |
628f6a4e | 940 | FOR_EACH_EDGE (e, ei, head_bb->preds) |
fe3ad572 SC |
941 | *tos++ = e->src; |
942 | } | |
fe3ad572 SC |
943 | |
944 | while (tos != worklist) | |
945 | { | |
946 | basic_block bb = *--tos; | |
947 | if (!bitmap_bit_p (live_range, bb->index)) | |
948 | { | |
949 | edge e; | |
628f6a4e | 950 | edge_iterator ei; |
fe3ad572 SC |
951 | |
952 | bitmap_set_bit (live_range, bb->index); | |
953 | IOR_HARD_REG_SET (*btrs_live_in_range, | |
954 | btrs_live[bb->index]); | |
ff8b369a R |
955 | /* A previous btr migration could have caused a register to be |
956 | live just at the end of a block which we need in full. */ | |
957 | IOR_HARD_REG_SET (*btrs_live_in_range, | |
958 | btrs_live_at_end[bb->index]); | |
c263766c | 959 | if (dump_file) |
fe3ad572 | 960 | { |
c263766c | 961 | fprintf (dump_file, |
fe3ad572 | 962 | "Adding block %d to live range\n", bb->index); |
c263766c | 963 | fprintf (dump_file,"Now live btrs are "); |
fe3ad572 | 964 | dump_hard_reg_set (*btrs_live_in_range); |
c263766c | 965 | fprintf (dump_file, "\n"); |
fe3ad572 SC |
966 | } |
967 | ||
628f6a4e | 968 | FOR_EACH_EDGE (e, ei, bb->preds) |
fe3ad572 SC |
969 | { |
970 | basic_block pred = e->src; | |
971 | if (!bitmap_bit_p (live_range, pred->index)) | |
972 | *tos++ = pred; | |
973 | } | |
974 | } | |
975 | } | |
976 | ||
977 | free (worklist); | |
978 | } | |
979 | ||
980 | /* Return the most desirable target register that is not in | |
981 | the set USED_BTRS. */ | |
982 | static int | |
983 | choose_btr (HARD_REG_SET used_btrs) | |
984 | { | |
985 | int i; | |
fe3ad572 | 986 | |
56b138ae RS |
987 | if (!hard_reg_set_subset_p (all_btrs, used_btrs)) |
988 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) | |
989 | { | |
fe3ad572 | 990 | #ifdef REG_ALLOC_ORDER |
56b138ae | 991 | int regno = reg_alloc_order[i]; |
fe3ad572 | 992 | #else |
56b138ae | 993 | int regno = i; |
fe3ad572 | 994 | #endif |
56b138ae RS |
995 | if (TEST_HARD_REG_BIT (all_btrs, regno) |
996 | && !TEST_HARD_REG_BIT (used_btrs, regno)) | |
997 | return regno; | |
998 | } | |
fe3ad572 SC |
999 | return -1; |
1000 | } | |
1001 | ||
1002 | /* Calculate the set of basic blocks that contain the live range of | |
1003 | the def/use web DEF. | |
1004 | Also calculate the set of target registers that are live at time | |
1005 | in this live range, but ignore the live range represented by DEF | |
1006 | when calculating this set. */ | |
1007 | static void | |
1008 | btr_def_live_range (btr_def def, HARD_REG_SET *btrs_live_in_range) | |
1009 | { | |
1010 | if (!def->live_range) | |
1011 | { | |
1012 | btr_user user; | |
1013 | ||
8bdbfff5 | 1014 | def->live_range = BITMAP_ALLOC (NULL); |
fe3ad572 SC |
1015 | |
1016 | bitmap_set_bit (def->live_range, def->bb->index); | |
3cd8c58a NS |
1017 | COPY_HARD_REG_SET (*btrs_live_in_range, |
1018 | (flag_btr_bb_exclusive | |
1019 | ? btrs_live : btrs_live_at_end)[def->bb->index]); | |
fe3ad572 SC |
1020 | |
1021 | for (user = def->uses; user != NULL; user = user->next) | |
1022 | augment_live_range (def->live_range, btrs_live_in_range, | |
ff8b369a R |
1023 | def->bb, user->bb, |
1024 | (flag_btr_bb_exclusive | |
1025 | || user->insn != BB_END (def->bb) | |
2ca202e7 | 1026 | || !JUMP_P (user->insn))); |
fe3ad572 SC |
1027 | } |
1028 | else | |
1029 | { | |
1030 | /* def->live_range is accurate, but we need to recompute | |
1031 | the set of target registers live over it, because migration | |
1032 | of other PT instructions may have affected it. | |
1033 | */ | |
3cd8c58a NS |
1034 | unsigned bb; |
1035 | unsigned def_bb = flag_btr_bb_exclusive ? -1 : def->bb->index; | |
87c476a2 | 1036 | bitmap_iterator bi; |
fe3ad572 SC |
1037 | |
1038 | CLEAR_HARD_REG_SET (*btrs_live_in_range); | |
3cd8c58a | 1039 | EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi) |
87c476a2 | 1040 | { |
3cd8c58a NS |
1041 | IOR_HARD_REG_SET (*btrs_live_in_range, |
1042 | (def_bb == bb | |
1043 | ? btrs_live_at_end : btrs_live) [bb]); | |
87c476a2 | 1044 | } |
fe3ad572 SC |
1045 | } |
1046 | if (!def->other_btr_uses_before_def && | |
1047 | !def->other_btr_uses_after_use) | |
1048 | CLEAR_HARD_REG_BIT (*btrs_live_in_range, def->btr); | |
1049 | } | |
1050 | ||
1051 | /* Merge into the def/use web DEF any other def/use webs in the same | |
1052 | group that are dominated by DEF, provided that there is a target | |
1053 | register available to allocate to the merged web. */ | |
1054 | static void | |
1055 | combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range) | |
1056 | { | |
1057 | btr_def other_def; | |
1058 | ||
1059 | for (other_def = def->group->members; | |
1060 | other_def != NULL; | |
1061 | other_def = other_def->next_this_group) | |
1062 | { | |
1063 | if (other_def != def | |
1064 | && other_def->uses != NULL | |
1065 | && ! other_def->has_ambiguous_use | |
d47cc544 | 1066 | && dominated_by_p (CDI_DOMINATORS, other_def->bb, def->bb)) |
fe3ad572 SC |
1067 | { |
1068 | /* def->bb dominates the other def, so def and other_def could | |
71c0e7fc | 1069 | be combined. */ |
fe3ad572 | 1070 | /* Merge their live ranges, and get the set of |
71c0e7fc | 1071 | target registers live over the merged range. */ |
fe3ad572 SC |
1072 | int btr; |
1073 | HARD_REG_SET combined_btrs_live; | |
8bdbfff5 | 1074 | bitmap combined_live_range = BITMAP_ALLOC (NULL); |
fe3ad572 SC |
1075 | btr_user user; |
1076 | ||
1077 | if (other_def->live_range == NULL) | |
1078 | { | |
1079 | HARD_REG_SET dummy_btrs_live_in_range; | |
1080 | btr_def_live_range (other_def, &dummy_btrs_live_in_range); | |
1081 | } | |
1082 | COPY_HARD_REG_SET (combined_btrs_live, *btrs_live_in_range); | |
1083 | bitmap_copy (combined_live_range, def->live_range); | |
1084 | ||
1085 | for (user = other_def->uses; user != NULL; user = user->next) | |
1086 | augment_live_range (combined_live_range, &combined_btrs_live, | |
ff8b369a R |
1087 | def->bb, user->bb, |
1088 | (flag_btr_bb_exclusive | |
1089 | || user->insn != BB_END (def->bb) | |
2ca202e7 | 1090 | || !JUMP_P (user->insn))); |
fe3ad572 SC |
1091 | |
1092 | btr = choose_btr (combined_btrs_live); | |
1093 | if (btr != -1) | |
1094 | { | |
f9da5064 | 1095 | /* We can combine them. */ |
c263766c RH |
1096 | if (dump_file) |
1097 | fprintf (dump_file, | |
fe3ad572 SC |
1098 | "Combining def in insn %d with def in insn %d\n", |
1099 | INSN_UID (other_def->insn), INSN_UID (def->insn)); | |
1100 | ||
1101 | def->btr = btr; | |
1102 | user = other_def->uses; | |
1103 | while (user != NULL) | |
1104 | { | |
1105 | btr_user next = user->next; | |
1106 | ||
1107 | user->next = def->uses; | |
1108 | def->uses = user; | |
1109 | user = next; | |
1110 | } | |
1111 | /* Combining def/use webs can make target registers live | |
1112 | after uses where they previously were not. This means | |
1113 | some REG_DEAD notes may no longer be correct. We could | |
1114 | be more precise about this if we looked at the combined | |
1115 | live range, but here I just delete any REG_DEAD notes | |
71c0e7fc | 1116 | in case they are no longer correct. */ |
fe3ad572 SC |
1117 | for (user = def->uses; user != NULL; user = user->next) |
1118 | remove_note (user->insn, | |
1119 | find_regno_note (user->insn, REG_DEAD, | |
1120 | REGNO (user->use))); | |
1121 | clear_btr_from_live_range (other_def); | |
1122 | other_def->uses = NULL; | |
1123 | bitmap_copy (def->live_range, combined_live_range); | |
ff8b369a | 1124 | if (other_def->btr == btr && other_def->other_btr_uses_after_use) |
fe3ad572 SC |
1125 | def->other_btr_uses_after_use = 1; |
1126 | COPY_HARD_REG_SET (*btrs_live_in_range, combined_btrs_live); | |
1127 | ||
f9da5064 | 1128 | /* Delete the old target register initialization. */ |
fe3ad572 SC |
1129 | delete_insn (other_def->insn); |
1130 | ||
1131 | } | |
8bdbfff5 | 1132 | BITMAP_FREE (combined_live_range); |
fe3ad572 SC |
1133 | } |
1134 | } | |
1135 | } | |
1136 | ||
1137 | /* Move the definition DEF from its current position to basic | |
1138 | block NEW_DEF_BB, and modify it to use branch target register BTR. | |
1139 | Delete the old defining insn, and insert a new one in NEW_DEF_BB. | |
1140 | Update all reaching uses of DEF in the RTL to use BTR. | |
1141 | If this new position means that other defs in the | |
1142 | same group can be combined with DEF then combine them. */ | |
1143 | static void | |
1144 | move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range, | |
1145 | HARD_REG_SET *btrs_live_in_range) | |
1146 | { | |
1147 | /* We can move the instruction. | |
1148 | Set a target register in block NEW_DEF_BB to the value | |
1149 | needed for this target register definition. | |
1150 | Replace all uses of the old target register definition by | |
71c0e7fc | 1151 | uses of the new definition. Delete the old definition. */ |
fe3ad572 | 1152 | basic_block b = new_def_bb; |
fd6657fb DM |
1153 | rtx_insn *insp = BB_HEAD (b); |
1154 | rtx_insn *old_insn = def->insn; | |
fe3ad572 SC |
1155 | rtx src; |
1156 | rtx btr_rtx; | |
fd6657fb | 1157 | rtx_insn *new_insn; |
ef4bddc2 | 1158 | machine_mode btr_mode; |
fe3ad572 SC |
1159 | btr_user user; |
1160 | rtx set; | |
1161 | ||
c263766c RH |
1162 | if (dump_file) |
1163 | fprintf(dump_file, "migrating to basic block %d, using reg %d\n", | |
fe3ad572 SC |
1164 | new_def_bb->index, btr); |
1165 | ||
1166 | clear_btr_from_live_range (def); | |
1167 | def->btr = btr; | |
1168 | def->bb = new_def_bb; | |
1169 | def->luid = 0; | |
1170 | def->cost = basic_block_freq (new_def_bb); | |
fe3ad572 SC |
1171 | bitmap_copy (def->live_range, live_range); |
1172 | combine_btr_defs (def, btrs_live_in_range); | |
1173 | btr = def->btr; | |
ff8b369a R |
1174 | def->other_btr_uses_before_def |
1175 | = TEST_HARD_REG_BIT (btrs_live[b->index], btr) ? 1 : 0; | |
1176 | add_btr_to_live_range (def, 1); | |
4b4bf941 | 1177 | if (LABEL_P (insp)) |
fe3ad572 SC |
1178 | insp = NEXT_INSN (insp); |
1179 | /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some | |
1180 | optimizations can result in insp being both first and last insn of | |
1181 | its basic block. */ | |
1182 | /* ?? some assertions to check that insp is sensible? */ | |
1183 | ||
1194fc79 R |
1184 | if (def->other_btr_uses_before_def) |
1185 | { | |
1186 | insp = BB_END (b); | |
1187 | for (insp = BB_END (b); ! INSN_P (insp); insp = PREV_INSN (insp)) | |
298e6adc | 1188 | gcc_assert (insp != BB_HEAD (b)); |
c22cacf3 | 1189 | |
4b4bf941 | 1190 | if (JUMP_P (insp) || can_throw_internal (insp)) |
1194fc79 R |
1191 | insp = PREV_INSN (insp); |
1192 | } | |
1193 | ||
fe3ad572 SC |
1194 | set = single_set (old_insn); |
1195 | src = SET_SRC (set); | |
1196 | btr_mode = GET_MODE (SET_DEST (set)); | |
f84d109f | 1197 | btr_rtx = gen_rtx_REG (btr_mode, btr); |
fe3ad572 | 1198 | |
fd6657fb | 1199 | new_insn = as_a <rtx_insn *> (gen_move_insn (btr_rtx, src)); |
fe3ad572 | 1200 | |
71c0e7fc | 1201 | /* Insert target register initialization at head of basic block. */ |
fe3ad572 SC |
1202 | def->insn = emit_insn_after (new_insn, insp); |
1203 | ||
6fb5fa3c | 1204 | df_set_regs_ever_live (btr, true); |
fe3ad572 | 1205 | |
c263766c RH |
1206 | if (dump_file) |
1207 | fprintf (dump_file, "New pt is insn %d, inserted after insn %d\n", | |
fe3ad572 SC |
1208 | INSN_UID (def->insn), INSN_UID (insp)); |
1209 | ||
f9da5064 | 1210 | /* Delete the old target register initialization. */ |
fe3ad572 SC |
1211 | delete_insn (old_insn); |
1212 | ||
1213 | /* Replace each use of the old target register by a use of the new target | |
71c0e7fc | 1214 | register. */ |
fe3ad572 SC |
1215 | for (user = def->uses; user != NULL; user = user->next) |
1216 | { | |
1217 | /* Some extra work here to ensure consistent modes, because | |
1218 | it seems that a target register REG rtx can be given a different | |
1219 | mode depending on the context (surely that should not be | |
71c0e7fc | 1220 | the case?). */ |
fe3ad572 SC |
1221 | rtx replacement_rtx; |
1222 | if (GET_MODE (user->use) == GET_MODE (btr_rtx) | |
1223 | || GET_MODE (user->use) == VOIDmode) | |
1224 | replacement_rtx = btr_rtx; | |
1225 | else | |
f84d109f | 1226 | replacement_rtx = gen_rtx_REG (GET_MODE (user->use), btr); |
a8d8890a | 1227 | validate_replace_rtx (user->use, replacement_rtx, user->insn); |
fe3ad572 SC |
1228 | user->use = replacement_rtx; |
1229 | } | |
1230 | } | |
1231 | ||
1232 | /* We anticipate intra-block scheduling to be done. See if INSN could move | |
1233 | up within BB by N_INSNS. */ | |
1234 | static int | |
fd6657fb | 1235 | can_move_up (const_basic_block bb, const rtx_insn *insn, int n_insns) |
fe3ad572 | 1236 | { |
a813c111 | 1237 | while (insn != BB_HEAD (bb) && n_insns > 0) |
fe3ad572 SC |
1238 | { |
1239 | insn = PREV_INSN (insn); | |
1240 | /* ??? What if we have an anti-dependency that actually prevents the | |
1241 | scheduler from doing the move? We'd like to re-allocate the register, | |
1242 | but not necessarily put the load into another basic block. */ | |
1243 | if (INSN_P (insn)) | |
1244 | n_insns--; | |
1245 | } | |
1246 | return n_insns <= 0; | |
1247 | } | |
1248 | ||
1249 | /* Attempt to migrate the target register definition DEF to an | |
1250 | earlier point in the flowgraph. | |
1251 | ||
1252 | It is a precondition of this function that DEF is migratable: | |
1253 | i.e. it has a constant source, and all uses are unambiguous. | |
1254 | ||
1255 | Only migrations that reduce the cost of DEF will be made. | |
1256 | MIN_COST is the lower bound on the cost of the DEF after migration. | |
1257 | If we migrate DEF so that its cost falls below MIN_COST, | |
1258 | then we do not attempt to migrate further. The idea is that | |
4d6922ee | 1259 | we migrate definitions in a priority order based on their cost, |
fe3ad572 SC |
1260 | when the cost of this definition falls below MIN_COST, then |
1261 | there is another definition with cost == MIN_COST which now | |
1262 | has a higher priority than this definition. | |
1263 | ||
cc0efd0b | 1264 | Return nonzero if there may be benefit from attempting to |
fe3ad572 SC |
1265 | migrate this DEF further (i.e. we have reduced the cost below |
1266 | MIN_COST, but we may be able to reduce it further). | |
71c0e7fc | 1267 | Return zero if no further migration is possible. */ |
fe3ad572 SC |
1268 | static int |
1269 | migrate_btr_def (btr_def def, int min_cost) | |
1270 | { | |
1271 | bitmap live_range; | |
1272 | HARD_REG_SET btrs_live_in_range; | |
1273 | int btr_used_near_def = 0; | |
1274 | int def_basic_block_freq; | |
32e9fa48 | 1275 | basic_block attempt; |
fe3ad572 SC |
1276 | int give_up = 0; |
1277 | int def_moved = 0; | |
1278 | btr_user user; | |
fa0aee89 | 1279 | int def_latency; |
fe3ad572 | 1280 | |
c263766c RH |
1281 | if (dump_file) |
1282 | fprintf (dump_file, | |
fe3ad572 SC |
1283 | "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ", |
1284 | INSN_UID (def->insn), def->cost, min_cost); | |
1285 | ||
1286 | if (!def->group || def->has_ambiguous_use) | |
f9da5064 | 1287 | /* These defs are not migratable. */ |
fe3ad572 | 1288 | { |
c263766c RH |
1289 | if (dump_file) |
1290 | fprintf (dump_file, "it's not migratable\n"); | |
fe3ad572 SC |
1291 | return 0; |
1292 | } | |
1293 | ||
1294 | if (!def->uses) | |
1295 | /* We have combined this def with another in the same group, so | |
1296 | no need to consider it further. | |
1297 | */ | |
1298 | { | |
c263766c RH |
1299 | if (dump_file) |
1300 | fprintf (dump_file, "it's already combined with another pt\n"); | |
fe3ad572 SC |
1301 | return 0; |
1302 | } | |
1303 | ||
1304 | btr_def_live_range (def, &btrs_live_in_range); | |
8bdbfff5 | 1305 | live_range = BITMAP_ALLOC (NULL); |
fe3ad572 SC |
1306 | bitmap_copy (live_range, def->live_range); |
1307 | ||
5a9384dd | 1308 | #ifdef INSN_SCHEDULING |
fa0aee89 PB |
1309 | def_latency = insn_default_latency (def->insn) * issue_rate; |
1310 | #else | |
1311 | def_latency = issue_rate; | |
5a9384dd HPN |
1312 | #endif |
1313 | ||
fe3ad572 SC |
1314 | for (user = def->uses; user != NULL; user = user->next) |
1315 | { | |
1316 | if (user->bb == def->bb | |
1317 | && user->luid > def->luid | |
1318 | && (def->luid + def_latency) > user->luid | |
1319 | && ! can_move_up (def->bb, def->insn, | |
1320 | (def->luid + def_latency) - user->luid)) | |
1321 | { | |
1322 | btr_used_near_def = 1; | |
1323 | break; | |
1324 | } | |
1325 | } | |
1326 | ||
1327 | def_basic_block_freq = basic_block_freq (def->bb); | |
1328 | ||
32e9fa48 | 1329 | for (attempt = get_immediate_dominator (CDI_DOMINATORS, def->bb); |
fefa31b5 DM |
1330 | !give_up && attempt && attempt != ENTRY_BLOCK_PTR_FOR_FN (cfun) |
1331 | && def->cost >= min_cost; | |
32e9fa48 | 1332 | attempt = get_immediate_dominator (CDI_DOMINATORS, attempt)) |
fe3ad572 SC |
1333 | { |
1334 | /* Try to move the instruction that sets the target register into | |
32e9fa48 KG |
1335 | basic block ATTEMPT. */ |
1336 | int try_freq = basic_block_freq (attempt); | |
a1709769 KK |
1337 | edge_iterator ei; |
1338 | edge e; | |
1339 | ||
32e9fa48 KG |
1340 | /* If ATTEMPT has abnormal edges, skip it. */ |
1341 | FOR_EACH_EDGE (e, ei, attempt->succs) | |
a1709769 KK |
1342 | if (e->flags & EDGE_COMPLEX) |
1343 | break; | |
1344 | if (e) | |
1345 | continue; | |
fe3ad572 | 1346 | |
c263766c | 1347 | if (dump_file) |
32e9fa48 | 1348 | fprintf (dump_file, "trying block %d ...", attempt->index); |
fe3ad572 SC |
1349 | |
1350 | if (try_freq < def_basic_block_freq | |
1351 | || (try_freq == def_basic_block_freq && btr_used_near_def)) | |
1352 | { | |
1353 | int btr; | |
32e9fa48 | 1354 | augment_live_range (live_range, &btrs_live_in_range, def->bb, attempt, |
ff8b369a | 1355 | flag_btr_bb_exclusive); |
c263766c | 1356 | if (dump_file) |
fe3ad572 | 1357 | { |
c263766c | 1358 | fprintf (dump_file, "Now btrs live in range are: "); |
fe3ad572 | 1359 | dump_hard_reg_set (btrs_live_in_range); |
c263766c | 1360 | fprintf (dump_file, "\n"); |
fe3ad572 SC |
1361 | } |
1362 | btr = choose_btr (btrs_live_in_range); | |
1363 | if (btr != -1) | |
1364 | { | |
32e9fa48 | 1365 | move_btr_def (attempt, btr, def, live_range, &btrs_live_in_range); |
c3284718 | 1366 | bitmap_copy (live_range, def->live_range); |
fe3ad572 SC |
1367 | btr_used_near_def = 0; |
1368 | def_moved = 1; | |
1369 | def_basic_block_freq = basic_block_freq (def->bb); | |
1370 | } | |
1371 | else | |
1372 | { | |
1373 | /* There are no free target registers available to move | |
1374 | this far forward, so give up */ | |
1375 | give_up = 1; | |
c263766c RH |
1376 | if (dump_file) |
1377 | fprintf (dump_file, | |
fe3ad572 SC |
1378 | "giving up because there are no free target registers\n"); |
1379 | } | |
1380 | ||
1381 | } | |
1382 | } | |
1383 | if (!def_moved) | |
1384 | { | |
1385 | give_up = 1; | |
c263766c RH |
1386 | if (dump_file) |
1387 | fprintf (dump_file, "failed to move\n"); | |
fe3ad572 | 1388 | } |
8bdbfff5 | 1389 | BITMAP_FREE (live_range); |
fe3ad572 SC |
1390 | return !give_up; |
1391 | } | |
1392 | ||
1393 | /* Attempt to move instructions that set target registers earlier | |
71c0e7fc | 1394 | in the flowgraph, away from their corresponding uses. */ |
fe3ad572 SC |
1395 | static void |
1396 | migrate_btr_defs (enum reg_class btr_class, int allow_callee_save) | |
1397 | { | |
b5bfe5bd | 1398 | btr_heap_t all_btr_defs (LONG_MIN); |
fe3ad572 SC |
1399 | int reg; |
1400 | ||
1401 | gcc_obstack_init (&migrate_btrl_obstack); | |
c263766c | 1402 | if (dump_file) |
fe3ad572 SC |
1403 | { |
1404 | int i; | |
1405 | ||
8b1c6fd7 | 1406 | for (i = NUM_FIXED_BLOCKS; i < last_basic_block_for_fn (cfun); i++) |
fe3ad572 | 1407 | { |
06e28de2 | 1408 | basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i); |
c3284718 | 1409 | fprintf (dump_file, |
a9243bfc | 1410 | "Basic block %d: count = %" PRId64 |
c3284718 | 1411 | " loop-depth = %d idom = %d\n", |
a9243bfc | 1412 | i, (int64_t) bb->count, bb_loop_depth (bb), |
c3284718 | 1413 | get_immediate_dominator (CDI_DOMINATORS, bb)->index); |
fe3ad572 SC |
1414 | } |
1415 | } | |
1416 | ||
1417 | CLEAR_HARD_REG_SET (all_btrs); | |
1418 | for (first_btr = -1, reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++) | |
1419 | if (TEST_HARD_REG_BIT (reg_class_contents[(int) btr_class], reg) | |
b8698a0f | 1420 | && (allow_callee_save || call_used_regs[reg] |
6fb5fa3c | 1421 | || df_regs_ever_live_p (reg))) |
fe3ad572 SC |
1422 | { |
1423 | SET_HARD_REG_BIT (all_btrs, reg); | |
1424 | last_btr = reg; | |
1425 | if (first_btr < 0) | |
1426 | first_btr = reg; | |
1427 | } | |
1428 | ||
8b1c6fd7 DM |
1429 | btrs_live = XCNEWVEC (HARD_REG_SET, last_basic_block_for_fn (cfun)); |
1430 | btrs_live_at_end = XCNEWVEC (HARD_REG_SET, last_basic_block_for_fn (cfun)); | |
fe3ad572 | 1431 | |
b5bfe5bd | 1432 | build_btr_def_use_webs (&all_btr_defs); |
fe3ad572 | 1433 | |
b5bfe5bd | 1434 | while (!all_btr_defs.empty ()) |
fe3ad572 | 1435 | { |
b5bfe5bd | 1436 | int min_cost = -all_btr_defs.min_key (); |
37513299 | 1437 | btr_def def = all_btr_defs.extract_min (); |
fe3ad572 SC |
1438 | if (migrate_btr_def (def, min_cost)) |
1439 | { | |
b5bfe5bd | 1440 | all_btr_defs.insert (-def->cost, def); |
c263766c | 1441 | if (dump_file) |
fe3ad572 | 1442 | { |
c263766c | 1443 | fprintf (dump_file, |
fe3ad572 SC |
1444 | "Putting insn %d back on queue with priority %d\n", |
1445 | INSN_UID (def->insn), def->cost); | |
1446 | } | |
1447 | } | |
1448 | else | |
8bdbfff5 | 1449 | BITMAP_FREE (def->live_range); |
fe3ad572 SC |
1450 | } |
1451 | ||
1452 | free (btrs_live); | |
1194fc79 | 1453 | free (btrs_live_at_end); |
fe3ad572 | 1454 | obstack_free (&migrate_btrl_obstack, NULL); |
fe3ad572 SC |
1455 | } |
1456 | ||
6fb5fa3c | 1457 | static void |
827c06b6 | 1458 | branch_target_load_optimize (bool after_prologue_epilogue_gen) |
fe3ad572 | 1459 | { |
a87cf97e JR |
1460 | enum reg_class klass |
1461 | = (enum reg_class) targetm.branch_target_register_class (); | |
32e9fa48 | 1462 | if (klass != NO_REGS) |
fe3ad572 SC |
1463 | { |
1464 | /* Initialize issue_rate. */ | |
1465 | if (targetm.sched.issue_rate) | |
5fd9b178 | 1466 | issue_rate = targetm.sched.issue_rate (); |
fe3ad572 SC |
1467 | else |
1468 | issue_rate = 1; | |
1469 | ||
6fb5fa3c DB |
1470 | if (!after_prologue_epilogue_gen) |
1471 | { | |
1472 | /* Build the CFG for migrate_btr_defs. */ | |
fe3ad572 | 1473 | #if 1 |
6fb5fa3c DB |
1474 | /* This may or may not be needed, depending on where we |
1475 | run this phase. */ | |
1476 | cleanup_cfg (optimize ? CLEANUP_EXPENSIVE : 0); | |
fe3ad572 | 1477 | #endif |
6fb5fa3c DB |
1478 | } |
1479 | df_analyze (); | |
fe3ad572 | 1480 | |
fe3ad572 | 1481 | |
71c0e7fc | 1482 | /* Dominator info is also needed for migrate_btr_def. */ |
d47cc544 | 1483 | calculate_dominance_info (CDI_DOMINATORS); |
32e9fa48 | 1484 | migrate_btr_defs (klass, |
245f1bfa | 1485 | (targetm.branch_target_register_callee_saved |
fe3ad572 SC |
1486 | (after_prologue_epilogue_gen))); |
1487 | ||
d47cc544 | 1488 | free_dominance_info (CDI_DOMINATORS); |
fe3ad572 SC |
1489 | } |
1490 | } | |
ef330312 | 1491 | \f |
27a4cd48 DM |
1492 | namespace { |
1493 | ||
1494 | const pass_data pass_data_branch_target_load_optimize1 = | |
6fb5fa3c | 1495 | { |
27a4cd48 DM |
1496 | RTL_PASS, /* type */ |
1497 | "btl1", /* name */ | |
1498 | OPTGROUP_NONE, /* optinfo_flags */ | |
27a4cd48 DM |
1499 | TV_NONE, /* tv_id */ |
1500 | 0, /* properties_required */ | |
1501 | 0, /* properties_provided */ | |
1502 | 0, /* properties_destroyed */ | |
1503 | 0, /* todo_flags_start */ | |
3bea341f | 1504 | 0, /* todo_flags_finish */ |
6fb5fa3c DB |
1505 | }; |
1506 | ||
27a4cd48 DM |
1507 | class pass_branch_target_load_optimize1 : public rtl_opt_pass |
1508 | { | |
1509 | public: | |
c3284718 RS |
1510 | pass_branch_target_load_optimize1 (gcc::context *ctxt) |
1511 | : rtl_opt_pass (pass_data_branch_target_load_optimize1, ctxt) | |
27a4cd48 DM |
1512 | {} |
1513 | ||
1514 | /* opt_pass methods: */ | |
1a3d085c | 1515 | virtual bool gate (function *) { return flag_branch_target_load_optimize; } |
be55bfe6 TS |
1516 | virtual unsigned int execute (function *) |
1517 | { | |
1518 | branch_target_load_optimize (epilogue_completed); | |
1519 | return 0; | |
1520 | } | |
27a4cd48 DM |
1521 | |
1522 | }; // class pass_branch_target_load_optimize1 | |
1523 | ||
1524 | } // anon namespace | |
1525 | ||
1526 | rtl_opt_pass * | |
1527 | make_pass_branch_target_load_optimize1 (gcc::context *ctxt) | |
1528 | { | |
1529 | return new pass_branch_target_load_optimize1 (ctxt); | |
1530 | } | |
1531 | ||
ef330312 | 1532 | |
27a4cd48 DM |
1533 | namespace { |
1534 | ||
1535 | const pass_data pass_data_branch_target_load_optimize2 = | |
ef330312 | 1536 | { |
27a4cd48 DM |
1537 | RTL_PASS, /* type */ |
1538 | "btl2", /* name */ | |
1539 | OPTGROUP_NONE, /* optinfo_flags */ | |
27a4cd48 DM |
1540 | TV_NONE, /* tv_id */ |
1541 | 0, /* properties_required */ | |
1542 | 0, /* properties_provided */ | |
1543 | 0, /* properties_destroyed */ | |
1544 | 0, /* todo_flags_start */ | |
1545 | 0, /* todo_flags_finish */ | |
ef330312 | 1546 | }; |
27a4cd48 DM |
1547 | |
1548 | class pass_branch_target_load_optimize2 : public rtl_opt_pass | |
1549 | { | |
1550 | public: | |
c3284718 RS |
1551 | pass_branch_target_load_optimize2 (gcc::context *ctxt) |
1552 | : rtl_opt_pass (pass_data_branch_target_load_optimize2, ctxt) | |
27a4cd48 DM |
1553 | {} |
1554 | ||
1555 | /* opt_pass methods: */ | |
1a3d085c TS |
1556 | virtual bool gate (function *) |
1557 | { | |
1558 | return (optimize > 0 && flag_branch_target_load_optimize2); | |
1559 | } | |
1560 | ||
be55bfe6 | 1561 | virtual unsigned int execute (function *); |
27a4cd48 DM |
1562 | |
1563 | }; // class pass_branch_target_load_optimize2 | |
1564 | ||
be55bfe6 TS |
1565 | unsigned int |
1566 | pass_branch_target_load_optimize2::execute (function *) | |
1567 | { | |
1568 | static int warned = 0; | |
1569 | ||
1570 | /* Leave this a warning for now so that it is possible to experiment | |
1571 | with running this pass twice. In 3.6, we should either make this | |
1572 | an error, or use separate dump files. */ | |
1573 | if (flag_branch_target_load_optimize | |
1574 | && flag_branch_target_load_optimize2 | |
1575 | && !warned) | |
1576 | { | |
1577 | warning (0, "branch target register load optimization is not intended " | |
1578 | "to be run twice"); | |
1579 | ||
1580 | warned = 1; | |
1581 | } | |
1582 | ||
1583 | branch_target_load_optimize (epilogue_completed); | |
1584 | return 0; | |
1585 | } | |
1586 | ||
27a4cd48 DM |
1587 | } // anon namespace |
1588 | ||
1589 | rtl_opt_pass * | |
1590 | make_pass_branch_target_load_optimize2 (gcc::context *ctxt) | |
1591 | { | |
1592 | return new pass_branch_target_load_optimize2 (ctxt); | |
1593 | } |