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