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