]>
Commit | Line | Data |
---|---|---|
fe3ad572 | 1 | /* Perform branch target register load optimizations. |
1194fc79 | 2 | Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. |
fe3ad572 SC |
3 | |
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify it under | |
7 | the terms of the GNU General Public License as published by the Free | |
8 | Software Foundation; either version 2, or (at your option) any later | |
9 | version. | |
10 | ||
11 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
12 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GCC; see the file COPYING. If not, write to the Free | |
18 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "bitmap.h" | |
26 | #include "sbitmap.h" | |
27 | #include "rtl.h" | |
28 | #include "hard-reg-set.h" | |
29 | #include "basic-block.h" | |
30 | #include "regs.h" | |
31 | #include "obstack.h" | |
32 | #include "fibheap.h" | |
33 | #include "output.h" | |
34 | #include "target.h" | |
35 | #include "expr.h" | |
36 | #include "flags.h" | |
37 | #include "insn-attr.h" | |
38 | #include "function.h" | |
1194fc79 | 39 | #include "except.h" |
8f7193b8 | 40 | #include "tm_p.h" |
fe3ad572 SC |
41 | |
42 | /* Target register optimizations - these are performed after reload. */ | |
43 | ||
44 | typedef struct btr_def_group_s | |
45 | { | |
46 | struct btr_def_group_s *next; | |
47 | rtx src; | |
48 | struct btr_def_s *members; | |
49 | } *btr_def_group; | |
50 | ||
51 | typedef struct btr_user_s | |
52 | { | |
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; | |
66 | ||
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). */ | |
75 | ||
76 | typedef struct btr_def_s | |
77 | { | |
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, | |
f9da5064 | 93 | and we will not attempt to migrate this definition. */ |
fe3ad572 SC |
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 | |
71c0e7fc | 102 | as appropriate. */ |
fe3ad572 SC |
103 | char other_btr_uses_before_def; |
104 | char other_btr_uses_after_use; | |
105 | bitmap live_range; | |
106 | } *btr_def; | |
107 | ||
108 | static int issue_rate; | |
109 | ||
110 | static int basic_block_freq (basic_block); | |
111 | static int insn_sets_btr_p (rtx, int, int *); | |
112 | static rtx *find_btr_use (rtx); | |
113 | static int btr_referenced_p (rtx, rtx *); | |
114 | static int find_btr_reference (rtx *, void *); | |
115 | static void find_btr_def_group (btr_def_group *, btr_def); | |
116 | static btr_def add_btr_def (fibheap_t, basic_block, int, rtx, | |
117 | unsigned int, int, btr_def_group *); | |
118 | static btr_user new_btr_user (basic_block, int, rtx); | |
119 | static void dump_hard_reg_set (HARD_REG_SET); | |
120 | static void dump_btrs_live (int); | |
121 | static void note_other_use_this_block (unsigned int, btr_user); | |
122 | static void compute_defs_uses_and_gen (fibheap_t, btr_def *,btr_user *, | |
123 | sbitmap *, sbitmap *, HARD_REG_SET *); | |
124 | static void compute_kill (sbitmap *, sbitmap *, HARD_REG_SET *); | |
125 | static void compute_out (sbitmap *bb_out, sbitmap *, sbitmap *, int); | |
126 | static void link_btr_uses (btr_def *, btr_user *, sbitmap *, sbitmap *, int); | |
127 | static void build_btr_def_use_webs (fibheap_t); | |
128 | static int block_at_edge_of_live_range_p (int, btr_def); | |
129 | static void clear_btr_from_live_range (btr_def def); | |
130 | static void add_btr_to_live_range (btr_def); | |
131 | static void augment_live_range (bitmap, HARD_REG_SET *, basic_block, | |
132 | basic_block); | |
133 | static int choose_btr (HARD_REG_SET); | |
134 | static void combine_btr_defs (btr_def, HARD_REG_SET *); | |
135 | static void btr_def_live_range (btr_def, HARD_REG_SET *); | |
136 | static void move_btr_def (basic_block, int, btr_def, bitmap, HARD_REG_SET *); | |
137 | static int migrate_btr_def (btr_def, int); | |
138 | static void migrate_btr_defs (enum reg_class, int); | |
139 | static int can_move_up (basic_block, rtx, int); | |
140 | static void note_btr_set (rtx, rtx, void *); | |
141 | \f | |
142 | /* The following code performs code motion of target load instructions | |
143 | (instructions that set branch target registers), to move them | |
144 | forward away from the branch instructions and out of loops (or, | |
145 | more generally, from a more frequently executed place to a less | |
146 | frequently executed place). | |
147 | Moving target load instructions further in front of the branch | |
148 | instruction that uses the target register value means that the hardware | |
149 | has a better chance of preloading the instructions at the branch | |
150 | target by the time the branch is reached. This avoids bubbles | |
151 | when a taken branch needs to flush out the pipeline. | |
152 | Moving target load instructions out of loops means they are executed | |
153 | less frequently. */ | |
154 | ||
155 | /* An obstack to hold the def-use web data structures built up for | |
156 | migrating branch target load instructions. */ | |
157 | static struct obstack migrate_btrl_obstack; | |
158 | ||
fe3ad572 SC |
159 | /* Array indexed by basic block number, giving the set of registers |
160 | live in that block. */ | |
161 | static HARD_REG_SET *btrs_live; | |
162 | ||
1194fc79 R |
163 | /* Array indexed by basic block number, giving the set of registers live at |
164 | the end of that block, including any uses by a final jump insn, if any. */ | |
165 | static HARD_REG_SET *btrs_live_at_end; | |
166 | ||
fe3ad572 SC |
167 | /* Set of all target registers that we are willing to allocate. */ |
168 | static HARD_REG_SET all_btrs; | |
169 | ||
170 | /* Provide lower and upper bounds for target register numbers, so that | |
171 | we don't need to search through all the hard registers all the time. */ | |
172 | static int first_btr, last_btr; | |
173 | ||
174 | ||
175 | ||
1194fc79 | 176 | /* Return an estimate of the frequency of execution of block bb. */ |
fe3ad572 SC |
177 | static int |
178 | basic_block_freq (basic_block bb) | |
179 | { | |
180 | return bb->frequency; | |
181 | } | |
182 | ||
183 | static rtx *btr_reference_found; | |
184 | ||
185 | /* A subroutine of btr_referenced_p, called through for_each_rtx. | |
186 | PREG is a pointer to an rtx that is to be excluded from the | |
187 | traversal. If we find a reference to a target register anywhere | |
188 | else, return 1, and put a pointer to it into btr_reference_found. */ | |
189 | static int | |
190 | find_btr_reference (rtx *px, void *preg) | |
191 | { | |
192 | rtx x; | |
193 | int regno, i; | |
194 | ||
195 | if (px == preg) | |
196 | return -1; | |
197 | x = *px; | |
198 | if (GET_CODE (x) != REG) | |
199 | return 0; | |
200 | regno = REGNO (x); | |
66fd46b6 | 201 | for (i = hard_regno_nregs[regno][GET_MODE (x)] - 1; i >= 0; i--) |
fe3ad572 SC |
202 | if (TEST_HARD_REG_BIT (all_btrs, regno+i)) |
203 | { | |
204 | btr_reference_found = px; | |
205 | return 1; | |
206 | } | |
207 | return -1; | |
208 | } | |
209 | ||
210 | /* Return nonzero if X references (sets or reads) any branch target register. | |
211 | If EXCLUDEP is set, disregard any references within the rtx pointed to | |
212 | by it. If returning nonzero, also set btr_reference_found as above. */ | |
213 | static int | |
214 | btr_referenced_p (rtx x, rtx *excludep) | |
215 | { | |
216 | return for_each_rtx (&x, find_btr_reference, excludep); | |
217 | } | |
218 | ||
219 | /* Return true if insn is an instruction that sets a target register. | |
220 | if CHECK_CONST is true, only return true if the source is constant. | |
221 | If such a set is found and REGNO is nonzero, assign the register number | |
222 | of the destination register to *REGNO. */ | |
223 | static int | |
224 | insn_sets_btr_p (rtx insn, int check_const, int *regno) | |
225 | { | |
226 | rtx set; | |
227 | ||
228 | if (GET_CODE (insn) == INSN | |
229 | && (set = single_set (insn))) | |
230 | { | |
231 | rtx dest = SET_DEST (set); | |
232 | rtx src = SET_SRC (set); | |
233 | ||
234 | if (GET_CODE (dest) == SUBREG) | |
235 | dest = XEXP (dest, 0); | |
236 | ||
237 | if (GET_CODE (dest) == REG | |
238 | && TEST_HARD_REG_BIT (all_btrs, REGNO (dest))) | |
239 | { | |
240 | if (btr_referenced_p (src, NULL)) | |
241 | abort(); | |
242 | if (!check_const || CONSTANT_P (src)) | |
243 | { | |
244 | if (regno) | |
245 | *regno = REGNO (dest); | |
246 | return 1; | |
247 | } | |
248 | } | |
249 | } | |
250 | return 0; | |
251 | } | |
252 | ||
71c0e7fc | 253 | /* Find and return a use of a target register within an instruction INSN. */ |
fe3ad572 SC |
254 | static rtx * |
255 | find_btr_use (rtx insn) | |
256 | { | |
257 | return btr_referenced_p (insn, NULL) ? btr_reference_found : NULL; | |
258 | } | |
259 | ||
260 | /* Find the group that the target register definition DEF belongs | |
261 | to in the list starting with *ALL_BTR_DEF_GROUPS. If no such | |
262 | group exists, create one. Add def to the group. */ | |
263 | static void | |
264 | find_btr_def_group (btr_def_group *all_btr_def_groups, btr_def def) | |
265 | { | |
266 | if (insn_sets_btr_p (def->insn, 1, NULL)) | |
267 | { | |
268 | btr_def_group this_group; | |
269 | rtx def_src = SET_SRC (single_set (def->insn)); | |
270 | ||
271 | /* ?? This linear search is an efficiency concern, particularly | |
272 | as the search will almost always fail to find a match. */ | |
273 | for (this_group = *all_btr_def_groups; | |
274 | this_group != NULL; | |
275 | this_group = this_group->next) | |
276 | if (rtx_equal_p (def_src, this_group->src)) | |
277 | break; | |
278 | ||
279 | if (!this_group) | |
280 | { | |
703ad42b KG |
281 | this_group = obstack_alloc (&migrate_btrl_obstack, |
282 | sizeof (struct btr_def_group_s)); | |
fe3ad572 SC |
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; | |
287 | } | |
288 | def->group = this_group; | |
289 | def->next_this_group = this_group->members; | |
290 | this_group->members = def; | |
291 | } | |
292 | else | |
293 | def->group = NULL; | |
294 | } | |
295 | ||
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) | |
303 | { | |
703ad42b KG |
304 | btr_def this |
305 | = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_def_s)); | |
fe3ad572 SC |
306 | this->bb = bb; |
307 | this->luid = insn_luid; | |
308 | this->insn = insn; | |
309 | this->btr = dest_reg; | |
310 | this->cost = basic_block_freq (bb); | |
311 | this->has_ambiguous_use = 0; | |
312 | this->other_btr_uses_before_def = other_btr_uses_before_def; | |
313 | this->other_btr_uses_after_use = 0; | |
314 | this->next_this_bb = NULL; | |
315 | this->next_this_group = NULL; | |
316 | this->uses = NULL; | |
317 | this->live_range = NULL; | |
318 | find_btr_def_group (all_btr_def_groups, this); | |
319 | ||
320 | fibheap_insert (all_btr_defs, -this->cost, this); | |
321 | ||
c263766c RH |
322 | if (dump_file) |
323 | fprintf (dump_file, | |
fe3ad572 SC |
324 | "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n", |
325 | dest_reg, bb->index, INSN_UID (insn), (this->group ? "" : ":not const"), | |
326 | this->cost); | |
327 | ||
328 | return this; | |
329 | } | |
330 | ||
331 | /* Create a new target register user structure, for a use in block BB, | |
332 | instruction INSN. Return the new user. */ | |
333 | static btr_user | |
334 | new_btr_user (basic_block bb, int insn_luid, rtx insn) | |
335 | { | |
336 | /* This instruction reads target registers. We need | |
337 | to decide whether we can replace all target register | |
338 | uses easily. | |
339 | */ | |
340 | rtx *usep = find_btr_use (PATTERN (insn)); | |
341 | rtx use; | |
342 | btr_user user = NULL; | |
343 | ||
344 | if (usep) | |
345 | { | |
346 | int unambiguous_single_use; | |
347 | ||
348 | /* We want to ensure that USE is the only use of a target | |
349 | register in INSN, so that we know that to rewrite INSN to use | |
350 | a different target register, all we have to do is replace USE. */ | |
351 | unambiguous_single_use = !btr_referenced_p (PATTERN (insn), usep); | |
352 | if (!unambiguous_single_use) | |
353 | usep = NULL; | |
354 | } | |
355 | use = usep ? *usep : NULL_RTX; | |
703ad42b | 356 | user = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_user_s)); |
fe3ad572 SC |
357 | user->bb = bb; |
358 | user->luid = insn_luid; | |
359 | user->insn = insn; | |
360 | user->use = use; | |
361 | user->other_use_this_block = 0; | |
362 | user->next = NULL; | |
363 | user->n_reaching_defs = 0; | |
364 | user->first_reaching_def = -1; | |
365 | ||
c263766c | 366 | if (dump_file) |
fe3ad572 | 367 | { |
c263766c | 368 | fprintf (dump_file, "Uses target reg: { bb %d, insn %d }", |
fe3ad572 SC |
369 | bb->index, INSN_UID (insn)); |
370 | ||
371 | if (user->use) | |
c263766c | 372 | fprintf (dump_file, ": unambiguous use of reg %d\n", |
fe3ad572 SC |
373 | REGNO (user->use)); |
374 | } | |
375 | ||
376 | return user; | |
377 | } | |
378 | ||
71c0e7fc | 379 | /* Write the contents of S to the dump file. */ |
fe3ad572 SC |
380 | static void |
381 | dump_hard_reg_set (HARD_REG_SET s) | |
382 | { | |
383 | int reg; | |
384 | for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++) | |
385 | if (TEST_HARD_REG_BIT (s, reg)) | |
c263766c | 386 | fprintf (dump_file, " %d", reg); |
fe3ad572 SC |
387 | } |
388 | ||
71c0e7fc | 389 | /* Write the set of target regs live in block BB to the dump file. */ |
fe3ad572 SC |
390 | static void |
391 | dump_btrs_live (int bb) | |
392 | { | |
c263766c | 393 | fprintf (dump_file, "BB%d live:", bb); |
fe3ad572 | 394 | dump_hard_reg_set (btrs_live[bb]); |
c263766c | 395 | fprintf (dump_file, "\n"); |
fe3ad572 SC |
396 | } |
397 | ||
398 | /* REGNO is the number of a branch target register that is being used or | |
399 | set. USERS_THIS_BB is a list of preceding branch target register users; | |
400 | If any of them use the same register, set their other_use_this_block | |
401 | flag. */ | |
402 | static void | |
403 | note_other_use_this_block (unsigned int regno, btr_user users_this_bb) | |
404 | { | |
405 | btr_user user; | |
406 | ||
407 | for (user = users_this_bb; user != NULL; user = user->next) | |
408 | if (user->use && REGNO (user->use) == regno) | |
409 | user->other_use_this_block = 1; | |
410 | } | |
411 | ||
412 | typedef struct { | |
413 | btr_user users_this_bb; | |
414 | HARD_REG_SET btrs_written_in_block; | |
415 | HARD_REG_SET btrs_live_in_block; | |
416 | sbitmap bb_gen; | |
417 | sbitmap *btr_defset; | |
418 | } defs_uses_info; | |
419 | ||
420 | /* Called via note_stores or directly to register stores into / | |
421 | clobbers of a branch target register DEST that are not recognized as | |
422 | straightforward definitions. DATA points to information about the | |
f9da5064 | 423 | current basic block that needs updating. */ |
fe3ad572 SC |
424 | static void |
425 | note_btr_set (rtx dest, rtx set ATTRIBUTE_UNUSED, void *data) | |
426 | { | |
427 | defs_uses_info *info = data; | |
428 | int regno, end_regno; | |
429 | ||
430 | if (GET_CODE (dest) != REG) | |
431 | return; | |
432 | regno = REGNO (dest); | |
66fd46b6 | 433 | end_regno = regno + hard_regno_nregs[regno][GET_MODE (dest)]; |
fe3ad572 SC |
434 | for (; regno < end_regno; regno++) |
435 | if (TEST_HARD_REG_BIT (all_btrs, regno)) | |
436 | { | |
437 | note_other_use_this_block (regno, info->users_this_bb); | |
438 | SET_HARD_REG_BIT (info->btrs_written_in_block, regno); | |
439 | SET_HARD_REG_BIT (info->btrs_live_in_block, regno); | |
440 | sbitmap_difference (info->bb_gen, info->bb_gen, | |
441 | info->btr_defset[regno - first_btr]); | |
442 | } | |
443 | } | |
444 | ||
445 | static void | |
446 | compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array, | |
447 | btr_user *use_array, sbitmap *btr_defset, | |
448 | sbitmap *bb_gen, HARD_REG_SET *btrs_written) | |
449 | { | |
450 | /* Scan the code building up the set of all defs and all uses. | |
451 | For each target register, build the set of defs of that register. | |
452 | For each block, calculate the set of target registers | |
453 | written in that block. | |
454 | Also calculate the set of btrs ever live in that block. | |
455 | */ | |
456 | int i; | |
457 | int insn_luid = 0; | |
458 | btr_def_group all_btr_def_groups = NULL; | |
459 | defs_uses_info info; | |
460 | ||
461 | sbitmap_vector_zero (bb_gen, n_basic_blocks); | |
462 | for (i = 0; i < n_basic_blocks; i++) | |
463 | { | |
464 | basic_block bb = BASIC_BLOCK (i); | |
465 | int reg; | |
466 | btr_def defs_this_bb = NULL; | |
467 | rtx insn; | |
468 | rtx last; | |
1194fc79 | 469 | int can_throw = 0; |
fe3ad572 SC |
470 | |
471 | info.users_this_bb = NULL; | |
472 | info.bb_gen = bb_gen[i]; | |
473 | info.btr_defset = btr_defset; | |
474 | ||
475 | CLEAR_HARD_REG_SET (info.btrs_live_in_block); | |
476 | CLEAR_HARD_REG_SET (info.btrs_written_in_block); | |
477 | for (reg = first_btr; reg <= last_btr; reg++) | |
478 | if (TEST_HARD_REG_BIT (all_btrs, reg) | |
479 | && REGNO_REG_SET_P (bb->global_live_at_start, reg)) | |
480 | SET_HARD_REG_BIT (info.btrs_live_in_block, reg); | |
481 | ||
a813c111 | 482 | for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); |
fe3ad572 SC |
483 | insn != last; |
484 | insn = NEXT_INSN (insn), insn_luid++) | |
485 | { | |
486 | if (INSN_P (insn)) | |
487 | { | |
488 | int regno; | |
489 | int insn_uid = INSN_UID (insn); | |
490 | ||
491 | if (insn_sets_btr_p (insn, 0, ®no)) | |
492 | { | |
493 | btr_def def = add_btr_def ( | |
494 | all_btr_defs, bb, insn_luid, insn, regno, | |
495 | TEST_HARD_REG_BIT (info.btrs_live_in_block, regno), | |
496 | &all_btr_def_groups); | |
497 | ||
498 | def_array[insn_uid] = def; | |
499 | SET_HARD_REG_BIT (info.btrs_written_in_block, regno); | |
500 | SET_HARD_REG_BIT (info.btrs_live_in_block, regno); | |
501 | sbitmap_difference (bb_gen[i], bb_gen[i], | |
502 | btr_defset[regno - first_btr]); | |
503 | SET_BIT (bb_gen[i], insn_uid); | |
504 | def->next_this_bb = defs_this_bb; | |
505 | defs_this_bb = def; | |
506 | SET_BIT (btr_defset[regno - first_btr], insn_uid); | |
507 | note_other_use_this_block (regno, info.users_this_bb); | |
508 | } | |
509 | else | |
510 | { | |
511 | if (btr_referenced_p (PATTERN (insn), NULL)) | |
512 | { | |
513 | btr_user user = new_btr_user (bb, insn_luid, insn); | |
514 | ||
515 | use_array[insn_uid] = user; | |
516 | if (user->use) | |
517 | SET_HARD_REG_BIT (info.btrs_live_in_block, | |
518 | REGNO (user->use)); | |
519 | else | |
520 | { | |
521 | int reg; | |
522 | for (reg = first_btr; reg <= last_btr; reg++) | |
523 | if (TEST_HARD_REG_BIT (all_btrs, reg) | |
524 | && refers_to_regno_p (reg, reg + 1, user->insn, | |
525 | NULL)) | |
526 | { | |
527 | note_other_use_this_block (reg, | |
528 | info.users_this_bb); | |
529 | SET_HARD_REG_BIT (info.btrs_live_in_block, reg); | |
530 | } | |
531 | note_stores (PATTERN (insn), note_btr_set, &info); | |
532 | } | |
533 | user->next = info.users_this_bb; | |
534 | info.users_this_bb = user; | |
535 | } | |
536 | if (GET_CODE (insn) == CALL_INSN) | |
537 | { | |
538 | HARD_REG_SET *clobbered = &call_used_reg_set; | |
539 | HARD_REG_SET call_saved; | |
540 | rtx pat = PATTERN (insn); | |
541 | int i; | |
542 | ||
543 | /* Check for sibcall. */ | |
544 | if (GET_CODE (pat) == PARALLEL) | |
545 | for (i = XVECLEN (pat, 0) - 1; i >= 0; i--) | |
546 | if (GET_CODE (XVECEXP (pat, 0, i)) == RETURN) | |
547 | { | |
548 | COMPL_HARD_REG_SET (call_saved, | |
549 | call_used_reg_set); | |
550 | clobbered = &call_saved; | |
551 | } | |
1194fc79 | 552 | |
fe3ad572 SC |
553 | for (regno = first_btr; regno <= last_btr; regno++) |
554 | if (TEST_HARD_REG_BIT (*clobbered, regno)) | |
555 | note_btr_set (regno_reg_rtx[regno], NULL_RTX, &info); | |
556 | } | |
557 | } | |
558 | } | |
559 | } | |
560 | ||
561 | COPY_HARD_REG_SET (btrs_live[i], info.btrs_live_in_block); | |
562 | COPY_HARD_REG_SET (btrs_written[i], info.btrs_written_in_block); | |
1194fc79 R |
563 | |
564 | REG_SET_TO_HARD_REG_SET (btrs_live_at_end[i], bb->global_live_at_end); | |
565 | /* If this block ends in a jump insn, add any uses or even clobbers | |
566 | of branch target registers that it might have. */ | |
567 | for (insn = BB_END (bb); insn != BB_HEAD (bb) && ! INSN_P (insn); ) | |
568 | insn = PREV_INSN (insn); | |
569 | /* ??? for the fall-through edge, it would make sense to insert the | |
570 | btr set on the edge, but that would require to split the block | |
571 | early on so that we can distinguish between dominance from the fall | |
572 | through edge - which can use the call-clobbered registers - from | |
573 | dominance by the throw edge. */ | |
574 | if (can_throw_internal (insn)) | |
575 | { | |
576 | HARD_REG_SET tmp; | |
577 | ||
578 | COPY_HARD_REG_SET (tmp, call_used_reg_set); | |
579 | AND_HARD_REG_SET (tmp, all_btrs); | |
580 | IOR_HARD_REG_SET (btrs_live_at_end[i], tmp); | |
581 | can_throw = 1; | |
582 | } | |
583 | if (can_throw || GET_CODE (insn) == JUMP_INSN) | |
584 | { | |
585 | int regno; | |
586 | ||
587 | for (regno = first_btr; regno <= last_btr; regno++) | |
588 | if (refers_to_regno_p (regno, regno+1, insn, NULL)) | |
589 | SET_HARD_REG_BIT (btrs_live_at_end[i], regno); | |
590 | } | |
591 | ||
c263766c | 592 | if (dump_file) |
fe3ad572 SC |
593 | dump_btrs_live(i); |
594 | } | |
595 | } | |
596 | ||
597 | static void | |
598 | compute_kill (sbitmap *bb_kill, sbitmap *btr_defset, | |
599 | HARD_REG_SET *btrs_written) | |
600 | { | |
601 | int i; | |
602 | int regno; | |
603 | ||
604 | /* For each basic block, form the set BB_KILL - the set | |
71c0e7fc | 605 | of definitions that the block kills. */ |
fe3ad572 SC |
606 | sbitmap_vector_zero (bb_kill, n_basic_blocks); |
607 | for (i = 0; i < n_basic_blocks; i++) | |
608 | { | |
609 | for (regno = first_btr; regno <= last_btr; regno++) | |
610 | if (TEST_HARD_REG_BIT (all_btrs, regno) | |
611 | && TEST_HARD_REG_BIT (btrs_written[i], regno)) | |
612 | sbitmap_a_or_b (bb_kill[i], bb_kill[i], | |
613 | btr_defset[regno - first_btr]); | |
614 | } | |
615 | } | |
616 | ||
617 | static void | |
618 | compute_out (sbitmap *bb_out, sbitmap *bb_gen, sbitmap *bb_kill, int max_uid) | |
619 | { | |
620 | /* Perform iterative dataflow: | |
621 | Initially, for all blocks, BB_OUT = BB_GEN. | |
622 | For each block, | |
623 | BB_IN = union over predecessors of BB_OUT(pred) | |
624 | BB_OUT = (BB_IN - BB_KILL) + BB_GEN | |
f9da5064 | 625 | Iterate until the bb_out sets stop growing. */ |
fe3ad572 SC |
626 | int i; |
627 | int changed; | |
628 | sbitmap bb_in = sbitmap_alloc (max_uid); | |
629 | ||
630 | for (i = 0; i < n_basic_blocks; i++) | |
631 | sbitmap_copy (bb_out[i], bb_gen[i]); | |
632 | ||
633 | changed = 1; | |
634 | while (changed) | |
635 | { | |
636 | changed = 0; | |
637 | for (i = 0; i < n_basic_blocks; i++) | |
638 | { | |
639 | sbitmap_union_of_preds (bb_in, bb_out, i); | |
640 | changed |= sbitmap_union_of_diff_cg (bb_out[i], bb_gen[i], | |
641 | bb_in, bb_kill[i]); | |
642 | } | |
643 | } | |
644 | sbitmap_free (bb_in); | |
645 | } | |
646 | ||
647 | static void | |
648 | link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out, | |
649 | sbitmap *btr_defset, int max_uid) | |
650 | { | |
651 | int i; | |
652 | sbitmap reaching_defs = sbitmap_alloc (max_uid); | |
653 | ||
654 | /* Link uses to the uses lists of all of their reaching defs. | |
71c0e7fc | 655 | Count up the number of reaching defs of each use. */ |
fe3ad572 SC |
656 | for (i = 0; i < n_basic_blocks; i++) |
657 | { | |
658 | basic_block bb = BASIC_BLOCK (i); | |
659 | rtx insn; | |
660 | rtx last; | |
661 | ||
662 | sbitmap_union_of_preds (reaching_defs, bb_out, i); | |
a813c111 | 663 | for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); |
fe3ad572 SC |
664 | insn != last; |
665 | insn = NEXT_INSN (insn)) | |
666 | { | |
667 | if (INSN_P (insn)) | |
668 | { | |
669 | int insn_uid = INSN_UID (insn); | |
670 | ||
671 | btr_def def = def_array[insn_uid]; | |
672 | btr_user user = use_array[insn_uid]; | |
673 | if (def != NULL) | |
674 | { | |
675 | /* Remove all reaching defs of regno except | |
71c0e7fc | 676 | for this one. */ |
fe3ad572 SC |
677 | sbitmap_difference (reaching_defs, reaching_defs, |
678 | btr_defset[def->btr - first_btr]); | |
679 | SET_BIT(reaching_defs, insn_uid); | |
680 | } | |
681 | ||
682 | if (user != NULL) | |
683 | { | |
f9da5064 | 684 | /* Find all the reaching defs for this use. */ |
fe3ad572 SC |
685 | sbitmap reaching_defs_of_reg = sbitmap_alloc(max_uid); |
686 | int uid; | |
687 | ||
688 | if (user->use) | |
689 | sbitmap_a_and_b ( | |
690 | reaching_defs_of_reg, | |
691 | reaching_defs, | |
692 | btr_defset[REGNO (user->use) - first_btr]); | |
693 | else | |
694 | { | |
695 | int reg; | |
696 | ||
697 | sbitmap_zero (reaching_defs_of_reg); | |
698 | for (reg = first_btr; reg <= last_btr; reg++) | |
699 | if (TEST_HARD_REG_BIT (all_btrs, reg) | |
700 | && refers_to_regno_p (reg, reg + 1, user->insn, | |
701 | NULL)) | |
702 | sbitmap_a_or_b_and_c (reaching_defs_of_reg, | |
703 | reaching_defs_of_reg, | |
704 | reaching_defs, | |
705 | btr_defset[reg - first_btr]); | |
706 | } | |
707 | EXECUTE_IF_SET_IN_SBITMAP (reaching_defs_of_reg, 0, uid, | |
708 | { | |
709 | btr_def def = def_array[uid]; | |
710 | ||
f9da5064 | 711 | /* We now know that def reaches user. */ |
fe3ad572 | 712 | |
c263766c RH |
713 | if (dump_file) |
714 | fprintf (dump_file, | |
fe3ad572 SC |
715 | "Def in insn %d reaches use in insn %d\n", |
716 | uid, insn_uid); | |
717 | ||
718 | user->n_reaching_defs++; | |
719 | if (!user->use) | |
720 | def->has_ambiguous_use = 1; | |
721 | if (user->first_reaching_def != -1) | |
722 | { /* There is more than one reaching def. This is | |
723 | a rare case, so just give up on this def/use | |
71c0e7fc | 724 | web when it occurs. */ |
fe3ad572 SC |
725 | def->has_ambiguous_use = 1; |
726 | def_array[user->first_reaching_def] | |
727 | ->has_ambiguous_use = 1; | |
c263766c RH |
728 | if (dump_file) |
729 | fprintf (dump_file, | |
fe3ad572 SC |
730 | "(use %d has multiple reaching defs)\n", |
731 | insn_uid); | |
732 | } | |
733 | else | |
734 | user->first_reaching_def = uid; | |
735 | if (user->other_use_this_block) | |
736 | def->other_btr_uses_after_use = 1; | |
737 | user->next = def->uses; | |
738 | def->uses = user; | |
739 | }); | |
740 | sbitmap_free (reaching_defs_of_reg); | |
741 | } | |
742 | ||
743 | if (GET_CODE (insn) == CALL_INSN) | |
744 | { | |
745 | int regno; | |
746 | ||
747 | for (regno = first_btr; regno <= last_btr; regno++) | |
748 | if (TEST_HARD_REG_BIT (all_btrs, regno) | |
749 | && TEST_HARD_REG_BIT (call_used_reg_set, regno)) | |
750 | sbitmap_difference (reaching_defs, reaching_defs, | |
751 | btr_defset[regno - first_btr]); | |
752 | } | |
753 | } | |
754 | } | |
755 | } | |
756 | sbitmap_free (reaching_defs); | |
757 | } | |
758 | ||
759 | static void | |
760 | build_btr_def_use_webs (fibheap_t all_btr_defs) | |
761 | { | |
762 | const int max_uid = get_max_uid (); | |
763 | btr_def *def_array = xcalloc (max_uid, sizeof (btr_def)); | |
764 | btr_user *use_array = xcalloc (max_uid, sizeof (btr_user)); | |
765 | sbitmap *btr_defset = sbitmap_vector_alloc ( | |
766 | (last_btr - first_btr) + 1, max_uid); | |
767 | sbitmap *bb_gen = sbitmap_vector_alloc (n_basic_blocks, max_uid); | |
703ad42b | 768 | HARD_REG_SET *btrs_written = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET)); |
fe3ad572 SC |
769 | sbitmap *bb_kill; |
770 | sbitmap *bb_out; | |
771 | ||
772 | sbitmap_vector_zero (btr_defset, (last_btr - first_btr) + 1); | |
773 | ||
774 | compute_defs_uses_and_gen (all_btr_defs, def_array, use_array, btr_defset, | |
775 | bb_gen, btrs_written); | |
776 | ||
777 | bb_kill = sbitmap_vector_alloc (n_basic_blocks, max_uid); | |
778 | compute_kill (bb_kill, btr_defset, btrs_written); | |
779 | free (btrs_written); | |
780 | ||
781 | bb_out = sbitmap_vector_alloc (n_basic_blocks, max_uid); | |
782 | compute_out (bb_out, bb_gen, bb_kill, max_uid); | |
783 | ||
784 | sbitmap_vector_free (bb_gen); | |
785 | sbitmap_vector_free (bb_kill); | |
786 | ||
787 | link_btr_uses (def_array, use_array, bb_out, btr_defset, max_uid); | |
788 | ||
789 | sbitmap_vector_free (bb_out); | |
790 | sbitmap_vector_free (btr_defset); | |
791 | free (use_array); | |
792 | free (def_array); | |
793 | } | |
794 | ||
795 | /* Return true if basic block BB contains the start or end of the | |
796 | live range of the definition DEF, AND there are other live | |
797 | ranges of the same target register that include BB. */ | |
798 | static int | |
799 | block_at_edge_of_live_range_p (int bb, btr_def def) | |
800 | { | |
801 | if (def->other_btr_uses_before_def && BASIC_BLOCK (bb) == def->bb) | |
802 | return 1; | |
803 | else if (def->other_btr_uses_after_use) | |
804 | { | |
805 | btr_user user; | |
806 | for (user = def->uses; user != NULL; user = user->next) | |
807 | if (BASIC_BLOCK (bb) == user->bb) | |
808 | return 1; | |
809 | } | |
810 | return 0; | |
811 | } | |
812 | ||
813 | /* We are removing the def/use web DEF. The target register | |
814 | used in this web is therefore no longer live in the live range | |
815 | of this web, so remove it from the live set of all basic blocks | |
816 | in the live range of the web. | |
817 | Blocks at the boundary of the live range may contain other live | |
818 | ranges for the same target register, so we have to be careful | |
819 | to remove the target register from the live set of these blocks | |
71c0e7fc | 820 | only if they do not contain other live ranges for the same register. */ |
fe3ad572 SC |
821 | static void |
822 | clear_btr_from_live_range (btr_def def) | |
823 | { | |
824 | int bb; | |
825 | ||
826 | EXECUTE_IF_SET_IN_BITMAP | |
827 | (def->live_range, 0, bb, | |
828 | { | |
829 | if ((!def->other_btr_uses_before_def | |
830 | && !def->other_btr_uses_after_use) | |
831 | || !block_at_edge_of_live_range_p (bb, def)) | |
832 | { | |
833 | CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr); | |
1194fc79 | 834 | CLEAR_HARD_REG_BIT (btrs_live_at_end[bb], def->btr); |
c263766c | 835 | if (dump_file) |
fe3ad572 SC |
836 | dump_btrs_live (bb); |
837 | } | |
838 | }); | |
839 | } | |
840 | ||
841 | ||
842 | /* We are adding the def/use web DEF. Add the target register used | |
843 | in this web to the live set of all of the basic blocks that contain | |
844 | the live range of the web. */ | |
845 | static void | |
846 | add_btr_to_live_range (btr_def def) | |
847 | { | |
848 | int bb; | |
849 | EXECUTE_IF_SET_IN_BITMAP | |
850 | (def->live_range, 0, bb, | |
851 | { | |
852 | SET_HARD_REG_BIT (btrs_live[bb], def->btr); | |
1194fc79 | 853 | SET_HARD_REG_BIT (btrs_live_at_end[bb], def->btr); |
c263766c | 854 | if (dump_file) |
fe3ad572 SC |
855 | dump_btrs_live (bb); |
856 | }); | |
857 | } | |
858 | ||
859 | /* Update a live range to contain the basic block NEW_BLOCK, and all | |
860 | blocks on paths between the existing live range and NEW_BLOCK. | |
861 | HEAD is a block contained in the existing live range that dominates | |
862 | all other blocks in the existing live range. | |
863 | Also add to the set BTRS_LIVE_IN_RANGE all target registers that | |
864 | are live in the blocks that we add to the live range. | |
865 | It is a precondition that either NEW_BLOCK dominates HEAD,or | |
866 | HEAD dom NEW_BLOCK. This is used to speed up the | |
867 | implementation of this function. */ | |
868 | static void | |
869 | augment_live_range (bitmap live_range, HARD_REG_SET *btrs_live_in_range, | |
870 | basic_block head_bb, basic_block new_bb) | |
871 | { | |
872 | basic_block *worklist, *tos; | |
873 | ||
703ad42b | 874 | tos = worklist = xmalloc (sizeof (basic_block) * (n_basic_blocks + 1)); |
fe3ad572 | 875 | |
d47cc544 | 876 | if (dominated_by_p (CDI_DOMINATORS, new_bb, head_bb)) |
fe3ad572 | 877 | *tos++ = new_bb; |
d47cc544 | 878 | else if (dominated_by_p (CDI_DOMINATORS, head_bb, new_bb)) |
fe3ad572 SC |
879 | { |
880 | edge e; | |
881 | int new_block = new_bb->index; | |
882 | ||
883 | bitmap_set_bit (live_range, new_block); | |
1194fc79 R |
884 | if (flag_btr_bb_exclusive) |
885 | IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]); | |
886 | else | |
887 | { | |
888 | IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live_at_end[new_block]); | |
889 | IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[head_bb->index]); | |
890 | } | |
c263766c | 891 | if (dump_file) |
fe3ad572 | 892 | { |
c263766c | 893 | fprintf (dump_file, |
1194fc79 R |
894 | "Adding end of block %d and rest of %d to live range\n", |
895 | new_block, head_bb->index); | |
c263766c | 896 | fprintf (dump_file,"Now live btrs are "); |
fe3ad572 | 897 | dump_hard_reg_set (*btrs_live_in_range); |
c263766c | 898 | fprintf (dump_file, "\n"); |
fe3ad572 SC |
899 | } |
900 | for (e = head_bb->pred; e; e = e->pred_next) | |
901 | *tos++ = e->src; | |
902 | } | |
903 | else | |
904 | abort(); | |
905 | ||
906 | while (tos != worklist) | |
907 | { | |
908 | basic_block bb = *--tos; | |
909 | if (!bitmap_bit_p (live_range, bb->index)) | |
910 | { | |
911 | edge e; | |
912 | ||
913 | bitmap_set_bit (live_range, bb->index); | |
914 | IOR_HARD_REG_SET (*btrs_live_in_range, | |
915 | btrs_live[bb->index]); | |
c263766c | 916 | if (dump_file) |
fe3ad572 | 917 | { |
c263766c | 918 | fprintf (dump_file, |
fe3ad572 | 919 | "Adding block %d to live range\n", bb->index); |
c263766c | 920 | fprintf (dump_file,"Now live btrs are "); |
fe3ad572 | 921 | dump_hard_reg_set (*btrs_live_in_range); |
c263766c | 922 | fprintf (dump_file, "\n"); |
fe3ad572 SC |
923 | } |
924 | ||
925 | for (e = bb->pred; e != NULL; e = e->pred_next) | |
926 | { | |
927 | basic_block pred = e->src; | |
928 | if (!bitmap_bit_p (live_range, pred->index)) | |
929 | *tos++ = pred; | |
930 | } | |
931 | } | |
932 | } | |
933 | ||
934 | free (worklist); | |
935 | } | |
936 | ||
937 | /* Return the most desirable target register that is not in | |
938 | the set USED_BTRS. */ | |
939 | static int | |
940 | choose_btr (HARD_REG_SET used_btrs) | |
941 | { | |
942 | int i; | |
943 | GO_IF_HARD_REG_SUBSET (all_btrs, used_btrs, give_up); | |
944 | ||
945 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) | |
946 | { | |
947 | #ifdef REG_ALLOC_ORDER | |
948 | int regno = reg_alloc_order[i]; | |
949 | #else | |
950 | int regno = i; | |
951 | #endif | |
952 | if (TEST_HARD_REG_BIT (all_btrs, regno) | |
953 | && !TEST_HARD_REG_BIT (used_btrs, regno)) | |
954 | return regno; | |
955 | } | |
956 | give_up: | |
957 | return -1; | |
958 | } | |
959 | ||
960 | /* Calculate the set of basic blocks that contain the live range of | |
961 | the def/use web DEF. | |
962 | Also calculate the set of target registers that are live at time | |
963 | in this live range, but ignore the live range represented by DEF | |
964 | when calculating this set. */ | |
965 | static void | |
966 | btr_def_live_range (btr_def def, HARD_REG_SET *btrs_live_in_range) | |
967 | { | |
968 | if (!def->live_range) | |
969 | { | |
970 | btr_user user; | |
971 | ||
972 | def->live_range = BITMAP_XMALLOC (); | |
973 | ||
974 | bitmap_set_bit (def->live_range, def->bb->index); | |
1194fc79 R |
975 | if (flag_btr_bb_exclusive) |
976 | COPY_HARD_REG_SET (*btrs_live_in_range, btrs_live[def->bb->index]); | |
977 | else | |
978 | COPY_HARD_REG_SET (*btrs_live_in_range, | |
979 | btrs_live_at_end[def->bb->index]); | |
fe3ad572 SC |
980 | |
981 | for (user = def->uses; user != NULL; user = user->next) | |
982 | augment_live_range (def->live_range, btrs_live_in_range, | |
983 | def->bb, user->bb); | |
984 | } | |
985 | else | |
986 | { | |
987 | /* def->live_range is accurate, but we need to recompute | |
988 | the set of target registers live over it, because migration | |
989 | of other PT instructions may have affected it. | |
990 | */ | |
991 | int bb; | |
1194fc79 | 992 | int def_bb = def->bb->index; |
fe3ad572 SC |
993 | |
994 | CLEAR_HARD_REG_SET (*btrs_live_in_range); | |
1194fc79 R |
995 | if (flag_btr_bb_exclusive) |
996 | EXECUTE_IF_SET_IN_BITMAP | |
997 | (def->live_range, 0, bb, | |
998 | { | |
999 | IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[bb]); | |
1000 | }); | |
1001 | else | |
1002 | EXECUTE_IF_SET_IN_BITMAP | |
1003 | (def->live_range, 0, bb, | |
1004 | { | |
1005 | IOR_HARD_REG_SET (*btrs_live_in_range, | |
1006 | (def_bb == bb | |
1007 | ? btrs_live_at_end : btrs_live) [bb]); | |
1008 | }); | |
fe3ad572 SC |
1009 | } |
1010 | if (!def->other_btr_uses_before_def && | |
1011 | !def->other_btr_uses_after_use) | |
1012 | CLEAR_HARD_REG_BIT (*btrs_live_in_range, def->btr); | |
1013 | } | |
1014 | ||
1015 | /* Merge into the def/use web DEF any other def/use webs in the same | |
1016 | group that are dominated by DEF, provided that there is a target | |
1017 | register available to allocate to the merged web. */ | |
1018 | static void | |
1019 | combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range) | |
1020 | { | |
1021 | btr_def other_def; | |
1022 | ||
1023 | for (other_def = def->group->members; | |
1024 | other_def != NULL; | |
1025 | other_def = other_def->next_this_group) | |
1026 | { | |
1027 | if (other_def != def | |
1028 | && other_def->uses != NULL | |
1029 | && ! other_def->has_ambiguous_use | |
d47cc544 | 1030 | && dominated_by_p (CDI_DOMINATORS, other_def->bb, def->bb)) |
fe3ad572 SC |
1031 | { |
1032 | /* def->bb dominates the other def, so def and other_def could | |
71c0e7fc | 1033 | be combined. */ |
fe3ad572 | 1034 | /* Merge their live ranges, and get the set of |
71c0e7fc | 1035 | target registers live over the merged range. */ |
fe3ad572 SC |
1036 | int btr; |
1037 | HARD_REG_SET combined_btrs_live; | |
1038 | bitmap combined_live_range = BITMAP_XMALLOC (); | |
1039 | btr_user user; | |
1040 | ||
1041 | if (other_def->live_range == NULL) | |
1042 | { | |
1043 | HARD_REG_SET dummy_btrs_live_in_range; | |
1044 | btr_def_live_range (other_def, &dummy_btrs_live_in_range); | |
1045 | } | |
1046 | COPY_HARD_REG_SET (combined_btrs_live, *btrs_live_in_range); | |
1047 | bitmap_copy (combined_live_range, def->live_range); | |
1048 | ||
1049 | for (user = other_def->uses; user != NULL; user = user->next) | |
1050 | augment_live_range (combined_live_range, &combined_btrs_live, | |
1051 | def->bb, user->bb); | |
1052 | ||
1053 | btr = choose_btr (combined_btrs_live); | |
1054 | if (btr != -1) | |
1055 | { | |
f9da5064 | 1056 | /* We can combine them. */ |
c263766c RH |
1057 | if (dump_file) |
1058 | fprintf (dump_file, | |
fe3ad572 SC |
1059 | "Combining def in insn %d with def in insn %d\n", |
1060 | INSN_UID (other_def->insn), INSN_UID (def->insn)); | |
1061 | ||
1062 | def->btr = btr; | |
1063 | user = other_def->uses; | |
1064 | while (user != NULL) | |
1065 | { | |
1066 | btr_user next = user->next; | |
1067 | ||
1068 | user->next = def->uses; | |
1069 | def->uses = user; | |
1070 | user = next; | |
1071 | } | |
1072 | /* Combining def/use webs can make target registers live | |
1073 | after uses where they previously were not. This means | |
1074 | some REG_DEAD notes may no longer be correct. We could | |
1075 | be more precise about this if we looked at the combined | |
1076 | live range, but here I just delete any REG_DEAD notes | |
71c0e7fc | 1077 | in case they are no longer correct. */ |
fe3ad572 SC |
1078 | for (user = def->uses; user != NULL; user = user->next) |
1079 | remove_note (user->insn, | |
1080 | find_regno_note (user->insn, REG_DEAD, | |
1081 | REGNO (user->use))); | |
1082 | clear_btr_from_live_range (other_def); | |
1083 | other_def->uses = NULL; | |
1084 | bitmap_copy (def->live_range, combined_live_range); | |
1085 | if (other_def->other_btr_uses_after_use) | |
1086 | def->other_btr_uses_after_use = 1; | |
1087 | COPY_HARD_REG_SET (*btrs_live_in_range, combined_btrs_live); | |
1088 | ||
f9da5064 | 1089 | /* Delete the old target register initialization. */ |
fe3ad572 SC |
1090 | delete_insn (other_def->insn); |
1091 | ||
1092 | } | |
1093 | BITMAP_XFREE (combined_live_range); | |
1094 | } | |
1095 | } | |
1096 | } | |
1097 | ||
1098 | /* Move the definition DEF from its current position to basic | |
1099 | block NEW_DEF_BB, and modify it to use branch target register BTR. | |
1100 | Delete the old defining insn, and insert a new one in NEW_DEF_BB. | |
1101 | Update all reaching uses of DEF in the RTL to use BTR. | |
1102 | If this new position means that other defs in the | |
1103 | same group can be combined with DEF then combine them. */ | |
1104 | static void | |
1105 | move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range, | |
1106 | HARD_REG_SET *btrs_live_in_range) | |
1107 | { | |
1108 | /* We can move the instruction. | |
1109 | Set a target register in block NEW_DEF_BB to the value | |
1110 | needed for this target register definition. | |
1111 | Replace all uses of the old target register definition by | |
71c0e7fc | 1112 | uses of the new definition. Delete the old definition. */ |
fe3ad572 | 1113 | basic_block b = new_def_bb; |
a813c111 | 1114 | rtx insp = BB_HEAD (b); |
fe3ad572 SC |
1115 | rtx old_insn = def->insn; |
1116 | rtx src; | |
1117 | rtx btr_rtx; | |
1118 | rtx new_insn; | |
1119 | enum machine_mode btr_mode; | |
1120 | btr_user user; | |
1121 | rtx set; | |
1122 | ||
c263766c RH |
1123 | if (dump_file) |
1124 | fprintf(dump_file, "migrating to basic block %d, using reg %d\n", | |
fe3ad572 SC |
1125 | new_def_bb->index, btr); |
1126 | ||
1127 | clear_btr_from_live_range (def); | |
1128 | def->btr = btr; | |
1129 | def->bb = new_def_bb; | |
1130 | def->luid = 0; | |
1131 | def->cost = basic_block_freq (new_def_bb); | |
1194fc79 R |
1132 | def->other_btr_uses_before_def |
1133 | = TEST_HARD_REG_BIT (btrs_live[b->index], btr) ? 1 : 0; | |
fe3ad572 SC |
1134 | bitmap_copy (def->live_range, live_range); |
1135 | combine_btr_defs (def, btrs_live_in_range); | |
1136 | btr = def->btr; | |
1137 | add_btr_to_live_range (def); | |
1138 | if (GET_CODE (insp) == CODE_LABEL) | |
1139 | insp = NEXT_INSN (insp); | |
1140 | /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some | |
1141 | optimizations can result in insp being both first and last insn of | |
1142 | its basic block. */ | |
1143 | /* ?? some assertions to check that insp is sensible? */ | |
1144 | ||
1194fc79 R |
1145 | if (def->other_btr_uses_before_def) |
1146 | { | |
1147 | insp = BB_END (b); | |
1148 | for (insp = BB_END (b); ! INSN_P (insp); insp = PREV_INSN (insp)) | |
1149 | if (insp == BB_HEAD (b)) | |
1150 | abort (); | |
1151 | if (GET_CODE (insp) == JUMP_INSN || can_throw_internal (insp)) | |
1152 | insp = PREV_INSN (insp); | |
1153 | } | |
1154 | ||
fe3ad572 SC |
1155 | set = single_set (old_insn); |
1156 | src = SET_SRC (set); | |
1157 | btr_mode = GET_MODE (SET_DEST (set)); | |
f84d109f | 1158 | btr_rtx = gen_rtx_REG (btr_mode, btr); |
fe3ad572 SC |
1159 | |
1160 | new_insn = gen_move_insn (btr_rtx, src); | |
1161 | ||
71c0e7fc | 1162 | /* Insert target register initialization at head of basic block. */ |
fe3ad572 SC |
1163 | def->insn = emit_insn_after (new_insn, insp); |
1164 | ||
1165 | regs_ever_live[btr] = 1; | |
1166 | ||
c263766c RH |
1167 | if (dump_file) |
1168 | fprintf (dump_file, "New pt is insn %d, inserted after insn %d\n", | |
fe3ad572 SC |
1169 | INSN_UID (def->insn), INSN_UID (insp)); |
1170 | ||
f9da5064 | 1171 | /* Delete the old target register initialization. */ |
fe3ad572 SC |
1172 | delete_insn (old_insn); |
1173 | ||
1174 | /* Replace each use of the old target register by a use of the new target | |
71c0e7fc | 1175 | register. */ |
fe3ad572 SC |
1176 | for (user = def->uses; user != NULL; user = user->next) |
1177 | { | |
1178 | /* Some extra work here to ensure consistent modes, because | |
1179 | it seems that a target register REG rtx can be given a different | |
1180 | mode depending on the context (surely that should not be | |
71c0e7fc | 1181 | the case?). */ |
fe3ad572 SC |
1182 | rtx replacement_rtx; |
1183 | if (GET_MODE (user->use) == GET_MODE (btr_rtx) | |
1184 | || GET_MODE (user->use) == VOIDmode) | |
1185 | replacement_rtx = btr_rtx; | |
1186 | else | |
f84d109f | 1187 | replacement_rtx = gen_rtx_REG (GET_MODE (user->use), btr); |
fe3ad572 SC |
1188 | replace_rtx (user->insn, user->use, replacement_rtx); |
1189 | user->use = replacement_rtx; | |
1190 | } | |
1191 | } | |
1192 | ||
1193 | /* We anticipate intra-block scheduling to be done. See if INSN could move | |
1194 | up within BB by N_INSNS. */ | |
1195 | static int | |
1196 | can_move_up (basic_block bb, rtx insn, int n_insns) | |
1197 | { | |
a813c111 | 1198 | while (insn != BB_HEAD (bb) && n_insns > 0) |
fe3ad572 SC |
1199 | { |
1200 | insn = PREV_INSN (insn); | |
1201 | /* ??? What if we have an anti-dependency that actually prevents the | |
1202 | scheduler from doing the move? We'd like to re-allocate the register, | |
1203 | but not necessarily put the load into another basic block. */ | |
1204 | if (INSN_P (insn)) | |
1205 | n_insns--; | |
1206 | } | |
1207 | return n_insns <= 0; | |
1208 | } | |
1209 | ||
1210 | /* Attempt to migrate the target register definition DEF to an | |
1211 | earlier point in the flowgraph. | |
1212 | ||
1213 | It is a precondition of this function that DEF is migratable: | |
1214 | i.e. it has a constant source, and all uses are unambiguous. | |
1215 | ||
1216 | Only migrations that reduce the cost of DEF will be made. | |
1217 | MIN_COST is the lower bound on the cost of the DEF after migration. | |
1218 | If we migrate DEF so that its cost falls below MIN_COST, | |
1219 | then we do not attempt to migrate further. The idea is that | |
4d6922ee | 1220 | we migrate definitions in a priority order based on their cost, |
fe3ad572 SC |
1221 | when the cost of this definition falls below MIN_COST, then |
1222 | there is another definition with cost == MIN_COST which now | |
1223 | has a higher priority than this definition. | |
1224 | ||
cc0efd0b | 1225 | Return nonzero if there may be benefit from attempting to |
fe3ad572 SC |
1226 | migrate this DEF further (i.e. we have reduced the cost below |
1227 | MIN_COST, but we may be able to reduce it further). | |
71c0e7fc | 1228 | Return zero if no further migration is possible. */ |
fe3ad572 SC |
1229 | static int |
1230 | migrate_btr_def (btr_def def, int min_cost) | |
1231 | { | |
1232 | bitmap live_range; | |
1233 | HARD_REG_SET btrs_live_in_range; | |
1234 | int btr_used_near_def = 0; | |
1235 | int def_basic_block_freq; | |
1236 | basic_block try; | |
1237 | int give_up = 0; | |
1238 | int def_moved = 0; | |
1239 | btr_user user; | |
5a9384dd | 1240 | int def_latency = 1; |
fe3ad572 | 1241 | |
c263766c RH |
1242 | if (dump_file) |
1243 | fprintf (dump_file, | |
fe3ad572 SC |
1244 | "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ", |
1245 | INSN_UID (def->insn), def->cost, min_cost); | |
1246 | ||
1247 | if (!def->group || def->has_ambiguous_use) | |
f9da5064 | 1248 | /* These defs are not migratable. */ |
fe3ad572 | 1249 | { |
c263766c RH |
1250 | if (dump_file) |
1251 | fprintf (dump_file, "it's not migratable\n"); | |
fe3ad572 SC |
1252 | return 0; |
1253 | } | |
1254 | ||
1255 | if (!def->uses) | |
1256 | /* We have combined this def with another in the same group, so | |
1257 | no need to consider it further. | |
1258 | */ | |
1259 | { | |
c263766c RH |
1260 | if (dump_file) |
1261 | fprintf (dump_file, "it's already combined with another pt\n"); | |
fe3ad572 SC |
1262 | return 0; |
1263 | } | |
1264 | ||
1265 | btr_def_live_range (def, &btrs_live_in_range); | |
1266 | live_range = BITMAP_XMALLOC (); | |
1267 | bitmap_copy (live_range, def->live_range); | |
1268 | ||
5a9384dd | 1269 | #ifdef INSN_SCHEDULING |
fe3ad572 SC |
1270 | if ((*targetm.sched.use_dfa_pipeline_interface) ()) |
1271 | def_latency = insn_default_latency (def->insn); | |
1272 | else | |
1273 | def_latency = result_ready_cost (def->insn); | |
5a9384dd HPN |
1274 | #endif |
1275 | ||
fe3ad572 SC |
1276 | def_latency *= issue_rate; |
1277 | ||
1278 | for (user = def->uses; user != NULL; user = user->next) | |
1279 | { | |
1280 | if (user->bb == def->bb | |
1281 | && user->luid > def->luid | |
1282 | && (def->luid + def_latency) > user->luid | |
1283 | && ! can_move_up (def->bb, def->insn, | |
1284 | (def->luid + def_latency) - user->luid)) | |
1285 | { | |
1286 | btr_used_near_def = 1; | |
1287 | break; | |
1288 | } | |
1289 | } | |
1290 | ||
1291 | def_basic_block_freq = basic_block_freq (def->bb); | |
1292 | ||
d47cc544 | 1293 | for (try = get_immediate_dominator (CDI_DOMINATORS, def->bb); |
fe3ad572 | 1294 | !give_up && try && try != ENTRY_BLOCK_PTR && def->cost >= min_cost; |
d47cc544 | 1295 | try = get_immediate_dominator (CDI_DOMINATORS, try)) |
fe3ad572 SC |
1296 | { |
1297 | /* Try to move the instruction that sets the target register into | |
71c0e7fc | 1298 | basic block TRY. */ |
fe3ad572 SC |
1299 | int try_freq = basic_block_freq (try); |
1300 | ||
c263766c RH |
1301 | if (dump_file) |
1302 | fprintf (dump_file, "trying block %d ...", try->index); | |
fe3ad572 SC |
1303 | |
1304 | if (try_freq < def_basic_block_freq | |
1305 | || (try_freq == def_basic_block_freq && btr_used_near_def)) | |
1306 | { | |
1307 | int btr; | |
1308 | augment_live_range (live_range, &btrs_live_in_range, def->bb, try); | |
c263766c | 1309 | if (dump_file) |
fe3ad572 | 1310 | { |
c263766c | 1311 | fprintf (dump_file, "Now btrs live in range are: "); |
fe3ad572 | 1312 | dump_hard_reg_set (btrs_live_in_range); |
c263766c | 1313 | fprintf (dump_file, "\n"); |
fe3ad572 SC |
1314 | } |
1315 | btr = choose_btr (btrs_live_in_range); | |
1316 | if (btr != -1) | |
1317 | { | |
1318 | move_btr_def (try, btr, def, live_range, &btrs_live_in_range); | |
1319 | bitmap_copy(live_range, def->live_range); | |
1320 | btr_used_near_def = 0; | |
1321 | def_moved = 1; | |
1322 | def_basic_block_freq = basic_block_freq (def->bb); | |
1323 | } | |
1324 | else | |
1325 | { | |
1326 | /* There are no free target registers available to move | |
1327 | this far forward, so give up */ | |
1328 | give_up = 1; | |
c263766c RH |
1329 | if (dump_file) |
1330 | fprintf (dump_file, | |
fe3ad572 SC |
1331 | "giving up because there are no free target registers\n"); |
1332 | } | |
1333 | ||
1334 | } | |
1335 | } | |
1336 | if (!def_moved) | |
1337 | { | |
1338 | give_up = 1; | |
c263766c RH |
1339 | if (dump_file) |
1340 | fprintf (dump_file, "failed to move\n"); | |
fe3ad572 SC |
1341 | } |
1342 | BITMAP_XFREE (live_range); | |
1343 | return !give_up; | |
1344 | } | |
1345 | ||
1346 | /* Attempt to move instructions that set target registers earlier | |
71c0e7fc | 1347 | in the flowgraph, away from their corresponding uses. */ |
fe3ad572 SC |
1348 | static void |
1349 | migrate_btr_defs (enum reg_class btr_class, int allow_callee_save) | |
1350 | { | |
1351 | fibheap_t all_btr_defs = fibheap_new (); | |
1352 | int reg; | |
1353 | ||
1354 | gcc_obstack_init (&migrate_btrl_obstack); | |
c263766c | 1355 | if (dump_file) |
fe3ad572 SC |
1356 | { |
1357 | int i; | |
1358 | ||
1359 | for (i = 0; i < n_basic_blocks; i++) | |
1360 | { | |
1361 | basic_block bb = BASIC_BLOCK (i); | |
c263766c | 1362 | fprintf(dump_file, |
551dc360 AJ |
1363 | "Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC |
1364 | " loop-depth = %d idom = %d\n", | |
1365 | i, (HOST_WIDEST_INT) bb->count, bb->loop_depth, | |
d47cc544 | 1366 | get_immediate_dominator (CDI_DOMINATORS, bb)->index); |
fe3ad572 SC |
1367 | } |
1368 | } | |
1369 | ||
1370 | CLEAR_HARD_REG_SET (all_btrs); | |
1371 | for (first_btr = -1, reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++) | |
1372 | if (TEST_HARD_REG_BIT (reg_class_contents[(int) btr_class], reg) | |
1373 | && (allow_callee_save || call_used_regs[reg] || regs_ever_live[reg])) | |
1374 | { | |
1375 | SET_HARD_REG_BIT (all_btrs, reg); | |
1376 | last_btr = reg; | |
1377 | if (first_btr < 0) | |
1378 | first_btr = reg; | |
1379 | } | |
1380 | ||
703ad42b | 1381 | btrs_live = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET)); |
1194fc79 | 1382 | btrs_live_at_end = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET)); |
fe3ad572 SC |
1383 | |
1384 | build_btr_def_use_webs (all_btr_defs); | |
1385 | ||
1386 | while (!fibheap_empty (all_btr_defs)) | |
1387 | { | |
1388 | btr_def def = | |
1389 | (btr_def) fibheap_extract_min (all_btr_defs); | |
1390 | int min_cost = -fibheap_min_key (all_btr_defs); | |
1391 | if (migrate_btr_def (def, min_cost)) | |
1392 | { | |
1393 | fibheap_insert (all_btr_defs, -def->cost, (void *) def); | |
c263766c | 1394 | if (dump_file) |
fe3ad572 | 1395 | { |
c263766c | 1396 | fprintf (dump_file, |
fe3ad572 SC |
1397 | "Putting insn %d back on queue with priority %d\n", |
1398 | INSN_UID (def->insn), def->cost); | |
1399 | } | |
1400 | } | |
1401 | else | |
1402 | { | |
1403 | if (def->live_range) | |
1404 | BITMAP_XFREE (def->live_range); | |
1405 | } | |
1406 | } | |
1407 | ||
1408 | free (btrs_live); | |
1194fc79 | 1409 | free (btrs_live_at_end); |
fe3ad572 SC |
1410 | obstack_free (&migrate_btrl_obstack, NULL); |
1411 | fibheap_delete (all_btr_defs); | |
1412 | } | |
1413 | ||
1414 | void | |
1415 | branch_target_load_optimize (rtx insns, bool after_prologue_epilogue_gen) | |
1416 | { | |
1417 | enum reg_class class = (*targetm.branch_target_register_class) (); | |
1418 | if (class != NO_REGS) | |
1419 | { | |
1420 | /* Initialize issue_rate. */ | |
1421 | if (targetm.sched.issue_rate) | |
1422 | issue_rate = (*targetm.sched.issue_rate) (); | |
1423 | else | |
1424 | issue_rate = 1; | |
1425 | ||
71c0e7fc | 1426 | /* Build the CFG for migrate_btr_defs. */ |
fe3ad572 SC |
1427 | #if 1 |
1428 | /* This may or may not be needed, depending on where we | |
71c0e7fc | 1429 | run this phase. */ |
fe3ad572 SC |
1430 | cleanup_cfg (optimize ? CLEANUP_EXPENSIVE : 0); |
1431 | #endif | |
1432 | ||
1433 | life_analysis (insns, NULL, 0); | |
1434 | ||
71c0e7fc | 1435 | /* Dominator info is also needed for migrate_btr_def. */ |
d47cc544 | 1436 | calculate_dominance_info (CDI_DOMINATORS); |
fe3ad572 SC |
1437 | migrate_btr_defs (class, |
1438 | ((*targetm.branch_target_register_callee_saved) | |
1439 | (after_prologue_epilogue_gen))); | |
1440 | ||
d47cc544 | 1441 | free_dominance_info (CDI_DOMINATORS); |
fe3ad572 SC |
1442 | |
1443 | update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES, | |
1444 | PROP_DEATH_NOTES | PROP_REG_INFO); | |
1445 | } | |
1446 | } |