]>
Commit | Line | Data |
---|---|---|
7b82b5da | 1 | /* Register renaming for the GNU compiler. |
23a5b65a | 2 | Copyright (C) 2000-2014 Free Software Foundation, Inc. |
7b82b5da | 3 | |
1322177d | 4 | This file is part of GCC. |
7b82b5da | 5 | |
1322177d LB |
6 | GCC is free software; you can redistribute it and/or modify it |
7 | under the terms of the GNU General Public License as published by | |
9dcd6f09 | 8 | the Free Software Foundation; either version 3, or (at your option) |
7b82b5da SC |
9 | any later version. |
10 | ||
1322177d LB |
11 | GCC is distributed in the hope that it will be useful, but WITHOUT |
12 | ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
13 | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public | |
14 | License for more details. | |
7b82b5da SC |
15 | |
16 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
7b82b5da SC |
19 | |
20 | #include "config.h" | |
21 | #include "system.h" | |
4977bab6 ZW |
22 | #include "coretypes.h" |
23 | #include "tm.h" | |
0cbd9993 | 24 | #include "rtl-error.h" |
541f7d56 | 25 | #include "tm_p.h" |
7b82b5da SC |
26 | #include "insn-config.h" |
27 | #include "regs.h" | |
c4963a0a | 28 | #include "addresses.h" |
541f7d56 BS |
29 | #include "hard-reg-set.h" |
30 | #include "basic-block.h" | |
31 | #include "reload.h" | |
7b82b5da | 32 | #include "output.h" |
83685514 AM |
33 | #include "hashtab.h" |
34 | #include "hash-set.h" | |
35 | #include "vec.h" | |
36 | #include "machmode.h" | |
37 | #include "input.h" | |
7b82b5da SC |
38 | #include "function.h" |
39 | #include "recog.h" | |
541f7d56 BS |
40 | #include "flags.h" |
41 | #include "obstack.h" | |
ef330312 | 42 | #include "tree-pass.h" |
6fb5fa3c | 43 | #include "df.h" |
5f286f4a | 44 | #include "target.h" |
1f234b83 BS |
45 | #include "emit-rtl.h" |
46 | #include "regrename.h" | |
541f7d56 | 47 | |
6656b2ac EB |
48 | /* This file implements the RTL register renaming pass of the compiler. It is |
49 | a semi-local pass whose goal is to maximize the usage of the register file | |
50 | of the processor by substituting registers for others in the solution given | |
51 | by the register allocator. The algorithm is as follows: | |
52 | ||
53 | 1. Local def/use chains are built: within each basic block, chains are | |
54 | opened and closed; if a chain isn't closed at the end of the block, | |
8ffa0351 BS |
55 | it is dropped. We pre-open chains if we have already examined a |
56 | predecessor block and found chains live at the end which match | |
57 | live registers at the start of the new block. | |
6656b2ac | 58 | |
8ffa0351 BS |
59 | 2. We try to combine the local chains across basic block boundaries by |
60 | comparing chains that were open at the start or end of a block to | |
61 | those in successor/predecessor blocks. | |
62 | ||
63 | 3. For each chain, the set of possible renaming registers is computed. | |
6656b2ac EB |
64 | This takes into account the renaming of previously processed chains. |
65 | Optionally, a preferred class is computed for the renaming register. | |
66 | ||
8ffa0351 | 67 | 4. The best renaming register is computed for the chain in the above set, |
6656b2ac EB |
68 | using a round-robin allocation. If a preferred class exists, then the |
69 | round-robin allocation is done within the class first, if possible. | |
70 | The round-robin allocation of renaming registers itself is global. | |
71 | ||
8ffa0351 | 72 | 5. If a renaming register has been found, it is substituted in the chain. |
6656b2ac EB |
73 | |
74 | Targets can parameterize the pass by specifying a preferred class for the | |
75 | renaming register for a given (super)class of registers to be renamed. */ | |
76 | ||
d435810e BS |
77 | #if HOST_BITS_PER_WIDE_INT <= MAX_RECOG_OPERANDS |
78 | #error "Use a different bitmap implementation for untracked_operands." | |
79 | #endif | |
6656b2ac | 80 | |
541f7d56 BS |
81 | enum scan_actions |
82 | { | |
541f7d56 BS |
83 | terminate_write, |
84 | terminate_dead, | |
a96caf80 | 85 | mark_all_read, |
541f7d56 | 86 | mark_read, |
cb110f3d AM |
87 | mark_write, |
88 | /* mark_access is for marking the destination regs in | |
89 | REG_FRAME_RELATED_EXPR notes (as if they were read) so that the | |
90 | note is updated properly. */ | |
91 | mark_access | |
541f7d56 BS |
92 | }; |
93 | ||
94 | static const char * const scan_actions_name[] = | |
95 | { | |
541f7d56 BS |
96 | "terminate_write", |
97 | "terminate_dead", | |
a96caf80 | 98 | "mark_all_read", |
541f7d56 | 99 | "mark_read", |
cb110f3d AM |
100 | "mark_write", |
101 | "mark_access" | |
541f7d56 BS |
102 | }; |
103 | ||
d3e80850 BS |
104 | /* TICK and THIS_TICK are used to record the last time we saw each |
105 | register. */ | |
106 | static int tick[FIRST_PSEUDO_REGISTER]; | |
107 | static int this_tick = 0; | |
108 | ||
541f7d56 BS |
109 | static struct obstack rename_obstack; |
110 | ||
1f234b83 BS |
111 | /* If nonnull, the code calling into the register renamer requested |
112 | information about insn operands, and we store it here. */ | |
9771b263 | 113 | vec<insn_rr_info> insn_rr; |
1f234b83 | 114 | |
a755f004 | 115 | static void scan_rtx (rtx_insn *, rtx *, enum reg_class, enum scan_actions, |
6bda9bdf | 116 | enum op_type); |
8ffa0351 | 117 | static bool build_def_use (basic_block); |
fe08a886 | 118 | |
d3e80850 BS |
119 | /* The id to be given to the next opened chain. */ |
120 | static unsigned current_id; | |
121 | ||
122 | /* A mapping of unique id numbers to chains. */ | |
9771b263 | 123 | static vec<du_head_p> id_to_chain; |
fe08a886 | 124 | |
8ffa0351 | 125 | /* List of currently open chains. */ |
d3e80850 | 126 | static struct du_head *open_chains; |
d3e80850 BS |
127 | |
128 | /* Bitmap of open chains. The bits set always match the list found in | |
129 | open_chains. */ | |
130 | static bitmap_head open_chains_set; | |
131 | ||
132 | /* Record the registers being tracked in open_chains. */ | |
133 | static HARD_REG_SET live_in_chains; | |
134 | ||
135 | /* Record the registers that are live but not tracked. The intersection | |
136 | between this and live_in_chains is empty. */ | |
137 | static HARD_REG_SET live_hard_regs; | |
138 | ||
1f234b83 BS |
139 | /* Set while scanning RTL if INSN_RR is nonnull, i.e. if the current analysis |
140 | is for a caller that requires operand data. Used in | |
141 | record_operand_use. */ | |
142 | static operand_rr_info *cur_operand; | |
143 | ||
8ffa0351 BS |
144 | /* Return the chain corresponding to id number ID. Take into account that |
145 | chains may have been merged. */ | |
1f234b83 BS |
146 | du_head_p |
147 | regrename_chain_from_id (unsigned int id) | |
8ffa0351 | 148 | { |
9771b263 | 149 | du_head_p first_chain = id_to_chain[id]; |
8ffa0351 BS |
150 | du_head_p chain = first_chain; |
151 | while (chain->id != id) | |
152 | { | |
153 | id = chain->id; | |
9771b263 | 154 | chain = id_to_chain[id]; |
8ffa0351 BS |
155 | } |
156 | first_chain->id = id; | |
157 | return chain; | |
158 | } | |
159 | ||
160 | /* Dump all def/use chains, starting at id FROM. */ | |
d3e80850 BS |
161 | |
162 | static void | |
8ffa0351 | 163 | dump_def_use_chain (int from) |
d3e80850 | 164 | { |
8ffa0351 BS |
165 | du_head_p head; |
166 | int i; | |
9771b263 | 167 | FOR_EACH_VEC_ELT_FROM (id_to_chain, i, head, from) |
d3e80850 BS |
168 | { |
169 | struct du_chain *this_du = head->first; | |
8ffa0351 | 170 | |
d3e80850 BS |
171 | fprintf (dump_file, "Register %s (%d):", |
172 | reg_names[head->regno], head->nregs); | |
173 | while (this_du) | |
174 | { | |
175 | fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn), | |
176 | reg_class_names[this_du->cl]); | |
177 | this_du = this_du->next_use; | |
178 | } | |
179 | fprintf (dump_file, "\n"); | |
180 | head = head->next_chain; | |
181 | } | |
182 | } | |
183 | ||
fe08a886 | 184 | static void |
a96caf80 | 185 | free_chain_data (void) |
fe08a886 | 186 | { |
a96caf80 BS |
187 | int i; |
188 | du_head_p ptr; | |
9771b263 | 189 | for (i = 0; id_to_chain.iterate (i, &ptr); i++) |
a96caf80 | 190 | bitmap_clear (&ptr->conflicts); |
226c62c7 | 191 | |
9771b263 | 192 | id_to_chain.release (); |
fe08a886 BS |
193 | } |
194 | ||
f24acbef BS |
195 | /* Walk all chains starting with CHAINS and record that they conflict with |
196 | another chain whose id is ID. */ | |
197 | ||
198 | static void | |
199 | mark_conflict (struct du_head *chains, unsigned id) | |
200 | { | |
201 | while (chains) | |
202 | { | |
203 | bitmap_set_bit (&chains->conflicts, id); | |
204 | chains = chains->next_chain; | |
205 | } | |
206 | } | |
207 | ||
1f234b83 BS |
208 | /* Examine cur_operand, and if it is nonnull, record information about the |
209 | use THIS_DU which is part of the chain HEAD. */ | |
210 | ||
211 | static void | |
212 | record_operand_use (struct du_head *head, struct du_chain *this_du) | |
213 | { | |
214 | if (cur_operand == NULL) | |
215 | return; | |
216 | gcc_assert (cur_operand->n_chains < MAX_REGS_PER_ADDRESS); | |
217 | cur_operand->heads[cur_operand->n_chains] = head; | |
218 | cur_operand->chains[cur_operand->n_chains++] = this_du; | |
219 | } | |
220 | ||
f24acbef BS |
221 | /* Create a new chain for THIS_NREGS registers starting at THIS_REGNO, |
222 | and record its occurrence in *LOC, which is being written to in INSN. | |
223 | This access requires a register of class CL. */ | |
224 | ||
8ffa0351 | 225 | static du_head_p |
f24acbef | 226 | create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc, |
a755f004 | 227 | rtx_insn *insn, enum reg_class cl) |
f24acbef BS |
228 | { |
229 | struct du_head *head = XOBNEW (&rename_obstack, struct du_head); | |
230 | struct du_chain *this_du; | |
231 | int nregs; | |
232 | ||
233 | head->next_chain = open_chains; | |
f24acbef BS |
234 | head->regno = this_regno; |
235 | head->nregs = this_nregs; | |
236 | head->need_caller_save_reg = 0; | |
237 | head->cannot_rename = 0; | |
238 | ||
9771b263 | 239 | id_to_chain.safe_push (head); |
f24acbef BS |
240 | head->id = current_id++; |
241 | ||
242 | bitmap_initialize (&head->conflicts, &bitmap_default_obstack); | |
243 | bitmap_copy (&head->conflicts, &open_chains_set); | |
244 | mark_conflict (open_chains, head->id); | |
245 | ||
246 | /* Since we're tracking this as a chain now, remove it from the | |
247 | list of conflicting live hard registers and track it in | |
248 | live_in_chains instead. */ | |
249 | nregs = head->nregs; | |
250 | while (nregs-- > 0) | |
251 | { | |
252 | SET_HARD_REG_BIT (live_in_chains, head->regno + nregs); | |
253 | CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs); | |
254 | } | |
255 | ||
256 | COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs); | |
257 | bitmap_set_bit (&open_chains_set, head->id); | |
258 | ||
259 | open_chains = head; | |
260 | ||
261 | if (dump_file) | |
262 | { | |
263 | fprintf (dump_file, "Creating chain %s (%d)", | |
264 | reg_names[head->regno], head->id); | |
265 | if (insn != NULL_RTX) | |
266 | fprintf (dump_file, " at insn %d", INSN_UID (insn)); | |
267 | fprintf (dump_file, "\n"); | |
268 | } | |
269 | ||
270 | if (insn == NULL_RTX) | |
271 | { | |
272 | head->first = head->last = NULL; | |
8ffa0351 | 273 | return head; |
f24acbef BS |
274 | } |
275 | ||
276 | this_du = XOBNEW (&rename_obstack, struct du_chain); | |
277 | head->first = head->last = this_du; | |
278 | ||
279 | this_du->next_use = 0; | |
280 | this_du->loc = loc; | |
281 | this_du->insn = insn; | |
282 | this_du->cl = cl; | |
1f234b83 | 283 | record_operand_use (head, this_du); |
8ffa0351 | 284 | return head; |
f24acbef BS |
285 | } |
286 | ||
a96caf80 BS |
287 | /* For a def-use chain HEAD, find which registers overlap its lifetime and |
288 | set the corresponding bits in *PSET. */ | |
fe08a886 BS |
289 | |
290 | static void | |
a96caf80 | 291 | merge_overlapping_regs (HARD_REG_SET *pset, struct du_head *head) |
fe08a886 | 292 | { |
a96caf80 BS |
293 | bitmap_iterator bi; |
294 | unsigned i; | |
295 | IOR_HARD_REG_SET (*pset, head->hard_conflicts); | |
296 | EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi) | |
32fc3abf | 297 | { |
1f234b83 | 298 | du_head_p other = regrename_chain_from_id (i); |
a96caf80 | 299 | unsigned j = other->nregs; |
8ffa0351 | 300 | gcc_assert (other != head); |
a96caf80 BS |
301 | while (j-- > 0) |
302 | SET_HARD_REG_BIT (*pset, other->regno + j); | |
fe08a886 BS |
303 | } |
304 | } | |
305 | ||
5f286f4a YQ |
306 | /* Check if NEW_REG can be the candidate register to rename for |
307 | REG in THIS_HEAD chain. THIS_UNAVAILABLE is a set of unavailable hard | |
308 | registers. */ | |
309 | ||
310 | static bool | |
6a68a5c3 JJ |
311 | check_new_reg_p (int reg ATTRIBUTE_UNUSED, int new_reg, |
312 | struct du_head *this_head, HARD_REG_SET this_unavailable) | |
5f286f4a YQ |
313 | { |
314 | enum machine_mode mode = GET_MODE (*this_head->first->loc); | |
315 | int nregs = hard_regno_nregs[new_reg][mode]; | |
316 | int i; | |
317 | struct du_chain *tmp; | |
318 | ||
319 | for (i = nregs - 1; i >= 0; --i) | |
320 | if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i) | |
321 | || fixed_regs[new_reg + i] | |
322 | || global_regs[new_reg + i] | |
323 | /* Can't use regs which aren't saved by the prologue. */ | |
324 | || (! df_regs_ever_live_p (new_reg + i) | |
325 | && ! call_used_regs[new_reg + i]) | |
326 | #ifdef LEAF_REGISTERS | |
327 | /* We can't use a non-leaf register if we're in a | |
328 | leaf function. */ | |
416ff32e | 329 | || (crtl->is_leaf |
5f286f4a YQ |
330 | && !LEAF_REGISTERS[new_reg + i]) |
331 | #endif | |
332 | #ifdef HARD_REGNO_RENAME_OK | |
333 | || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i) | |
334 | #endif | |
335 | ) | |
336 | return false; | |
337 | ||
338 | /* See whether it accepts all modes that occur in | |
339 | definition and uses. */ | |
340 | for (tmp = this_head->first; tmp; tmp = tmp->next_use) | |
341 | if ((! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc)) | |
342 | && ! DEBUG_INSN_P (tmp->insn)) | |
343 | || (this_head->need_caller_save_reg | |
344 | && ! (HARD_REGNO_CALL_PART_CLOBBERED | |
345 | (reg, GET_MODE (*tmp->loc))) | |
346 | && (HARD_REGNO_CALL_PART_CLOBBERED | |
347 | (new_reg, GET_MODE (*tmp->loc))))) | |
348 | return false; | |
349 | ||
350 | return true; | |
351 | } | |
352 | ||
1f234b83 BS |
353 | /* For the chain THIS_HEAD, compute and return the best register to |
354 | rename to. SUPER_CLASS is the superunion of register classes in | |
355 | the chain. UNAVAILABLE is a set of registers that cannot be used. | |
356 | OLD_REG is the register currently used for the chain. */ | |
357 | ||
358 | int | |
359 | find_best_rename_reg (du_head_p this_head, enum reg_class super_class, | |
360 | HARD_REG_SET *unavailable, int old_reg) | |
361 | { | |
362 | bool has_preferred_class; | |
363 | enum reg_class preferred_class; | |
364 | int pass; | |
365 | int best_new_reg = old_reg; | |
366 | ||
367 | /* Further narrow the set of registers we can use for renaming. | |
368 | If the chain needs a call-saved register, mark the call-used | |
369 | registers as unavailable. */ | |
370 | if (this_head->need_caller_save_reg) | |
371 | IOR_HARD_REG_SET (*unavailable, call_used_reg_set); | |
372 | ||
373 | /* Mark registers that overlap this chain's lifetime as unavailable. */ | |
374 | merge_overlapping_regs (unavailable, this_head); | |
375 | ||
376 | /* Compute preferred rename class of super union of all the classes | |
377 | in the chain. */ | |
378 | preferred_class | |
379 | = (enum reg_class) targetm.preferred_rename_class (super_class); | |
380 | ||
381 | /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass | |
382 | over registers that belong to PREFERRED_CLASS and try to find the | |
383 | best register within the class. If that failed, we iterate in | |
384 | the second pass over registers that don't belong to the class. | |
385 | If PREFERRED_CLASS is NO_REGS, we iterate over all registers in | |
386 | ascending order without any preference. */ | |
387 | has_preferred_class = (preferred_class != NO_REGS); | |
388 | for (pass = (has_preferred_class ? 0 : 1); pass < 2; pass++) | |
389 | { | |
390 | int new_reg; | |
391 | for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++) | |
392 | { | |
393 | if (has_preferred_class | |
394 | && (pass == 0) | |
395 | != TEST_HARD_REG_BIT (reg_class_contents[preferred_class], | |
396 | new_reg)) | |
397 | continue; | |
398 | ||
399 | /* In the first pass, we force the renaming of registers that | |
400 | don't belong to PREFERRED_CLASS to registers that do, even | |
401 | though the latters were used not very long ago. */ | |
402 | if (check_new_reg_p (old_reg, new_reg, this_head, | |
403 | *unavailable) | |
404 | && ((pass == 0 | |
405 | && !TEST_HARD_REG_BIT (reg_class_contents[preferred_class], | |
406 | best_new_reg)) | |
407 | || tick[best_new_reg] > tick[new_reg])) | |
408 | best_new_reg = new_reg; | |
409 | } | |
410 | if (pass == 0 && best_new_reg != old_reg) | |
411 | break; | |
412 | } | |
413 | return best_new_reg; | |
414 | } | |
415 | ||
8ffa0351 | 416 | /* Perform register renaming on the current function. */ |
d3e80850 | 417 | static void |
8ffa0351 | 418 | rename_chains (void) |
d3e80850 BS |
419 | { |
420 | HARD_REG_SET unavailable; | |
8ffa0351 BS |
421 | du_head_p this_head; |
422 | int i; | |
423 | ||
424 | memset (tick, 0, sizeof tick); | |
d3e80850 BS |
425 | |
426 | CLEAR_HARD_REG_SET (unavailable); | |
427 | /* Don't clobber traceback for noreturn functions. */ | |
428 | if (frame_pointer_needed) | |
429 | { | |
430 | add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM); | |
431 | #if !HARD_FRAME_POINTER_IS_FRAME_POINTER | |
432 | add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM); | |
433 | #endif | |
434 | } | |
435 | ||
9771b263 | 436 | FOR_EACH_VEC_ELT (id_to_chain, i, this_head) |
d3e80850 | 437 | { |
1f234b83 | 438 | int best_new_reg; |
d3e80850 | 439 | int n_uses; |
d3e80850 BS |
440 | struct du_chain *tmp; |
441 | HARD_REG_SET this_unavailable; | |
442 | int reg = this_head->regno; | |
d3e80850 | 443 | enum reg_class super_class = NO_REGS; |
d3e80850 | 444 | |
d3e80850 BS |
445 | if (this_head->cannot_rename) |
446 | continue; | |
447 | ||
d3e80850 BS |
448 | if (fixed_regs[reg] || global_regs[reg] |
449 | #if !HARD_FRAME_POINTER_IS_FRAME_POINTER | |
450 | || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM) | |
451 | #else | |
452 | || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM) | |
453 | #endif | |
454 | ) | |
455 | continue; | |
456 | ||
457 | COPY_HARD_REG_SET (this_unavailable, unavailable); | |
458 | ||
459 | /* Iterate over elements in the chain in order to: | |
460 | 1. Count number of uses, and narrow the set of registers we can | |
461 | use for renaming. | |
462 | 2. Compute the superunion of register classes in this chain. */ | |
463 | n_uses = 0; | |
464 | super_class = NO_REGS; | |
465 | for (tmp = this_head->first; tmp; tmp = tmp->next_use) | |
466 | { | |
467 | if (DEBUG_INSN_P (tmp->insn)) | |
468 | continue; | |
469 | n_uses++; | |
470 | IOR_COMPL_HARD_REG_SET (this_unavailable, | |
471 | reg_class_contents[tmp->cl]); | |
472 | super_class | |
473 | = reg_class_superunion[(int) super_class][(int) tmp->cl]; | |
474 | } | |
475 | ||
476 | if (n_uses < 2) | |
477 | continue; | |
478 | ||
1f234b83 BS |
479 | best_new_reg = find_best_rename_reg (this_head, super_class, |
480 | &this_unavailable, reg); | |
d3e80850 BS |
481 | |
482 | if (dump_file) | |
483 | { | |
484 | fprintf (dump_file, "Register %s in insn %d", | |
485 | reg_names[reg], INSN_UID (this_head->first->insn)); | |
486 | if (this_head->need_caller_save_reg) | |
487 | fprintf (dump_file, " crosses a call"); | |
488 | } | |
489 | ||
490 | if (best_new_reg == reg) | |
491 | { | |
492 | tick[reg] = ++this_tick; | |
493 | if (dump_file) | |
494 | fprintf (dump_file, "; no available better choice\n"); | |
495 | continue; | |
496 | } | |
497 | ||
498 | if (dump_file) | |
499 | fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]); | |
500 | ||
1f234b83 | 501 | regrename_do_replace (this_head, best_new_reg); |
d3e80850 BS |
502 | tick[best_new_reg] = ++this_tick; |
503 | df_set_regs_ever_live (best_new_reg, true); | |
504 | } | |
505 | } | |
506 | ||
8ffa0351 BS |
507 | /* A structure to record information for each hard register at the start of |
508 | a basic block. */ | |
509 | struct incoming_reg_info { | |
510 | /* Holds the number of registers used in the chain that gave us information | |
511 | about this register. Zero means no information known yet, while a | |
512 | negative value is used for something that is part of, but not the first | |
513 | register in a multi-register value. */ | |
514 | int nregs; | |
515 | /* Set to true if we have accesses that conflict in the number of registers | |
516 | used. */ | |
517 | bool unusable; | |
518 | }; | |
519 | ||
520 | /* A structure recording information about each basic block. It is saved | |
521 | and restored around basic block boundaries. | |
522 | A pointer to such a structure is stored in each basic block's aux field | |
523 | during regrename_analyze, except for blocks we know can't be optimized | |
524 | (such as entry and exit blocks). */ | |
525 | struct bb_rename_info | |
526 | { | |
527 | /* The basic block corresponding to this structure. */ | |
528 | basic_block bb; | |
529 | /* Copies of the global information. */ | |
530 | bitmap_head open_chains_set; | |
531 | bitmap_head incoming_open_chains_set; | |
532 | struct incoming_reg_info incoming[FIRST_PSEUDO_REGISTER]; | |
533 | }; | |
534 | ||
535 | /* Initialize a rename_info structure P for basic block BB, which starts a new | |
536 | scan. */ | |
537 | static void | |
538 | init_rename_info (struct bb_rename_info *p, basic_block bb) | |
539 | { | |
540 | int i; | |
292321a5 | 541 | df_ref def; |
8ffa0351 BS |
542 | HARD_REG_SET start_chains_set; |
543 | ||
544 | p->bb = bb; | |
545 | bitmap_initialize (&p->open_chains_set, &bitmap_default_obstack); | |
546 | bitmap_initialize (&p->incoming_open_chains_set, &bitmap_default_obstack); | |
547 | ||
548 | open_chains = NULL; | |
549 | bitmap_clear (&open_chains_set); | |
550 | ||
551 | CLEAR_HARD_REG_SET (live_in_chains); | |
552 | REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb)); | |
292321a5 RS |
553 | FOR_EACH_ARTIFICIAL_DEF (def, bb->index) |
554 | if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) | |
555 | SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def)); | |
8ffa0351 BS |
556 | |
557 | /* Open chains based on information from (at least one) predecessor | |
558 | block. This gives us a chance later on to combine chains across | |
559 | basic block boundaries. Inconsistencies (in access sizes) will | |
560 | be caught normally and dealt with conservatively by disabling the | |
561 | chain for renaming, and there is no risk of losing optimization | |
562 | opportunities by opening chains either: if we did not open the | |
563 | chains, we'd have to track the live register as a hard reg, and | |
564 | we'd be unable to rename it in any case. */ | |
565 | CLEAR_HARD_REG_SET (start_chains_set); | |
566 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) | |
567 | { | |
568 | struct incoming_reg_info *iri = p->incoming + i; | |
569 | if (iri->nregs > 0 && !iri->unusable | |
570 | && range_in_hard_reg_set_p (live_hard_regs, i, iri->nregs)) | |
571 | { | |
572 | SET_HARD_REG_BIT (start_chains_set, i); | |
573 | remove_range_from_hard_reg_set (&live_hard_regs, i, iri->nregs); | |
574 | } | |
575 | } | |
576 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) | |
577 | { | |
578 | struct incoming_reg_info *iri = p->incoming + i; | |
579 | if (TEST_HARD_REG_BIT (start_chains_set, i)) | |
580 | { | |
581 | du_head_p chain; | |
582 | if (dump_file) | |
583 | fprintf (dump_file, "opening incoming chain\n"); | |
a755f004 | 584 | chain = create_new_chain (i, iri->nregs, NULL, NULL, NO_REGS); |
8ffa0351 BS |
585 | bitmap_set_bit (&p->incoming_open_chains_set, chain->id); |
586 | } | |
587 | } | |
588 | } | |
589 | ||
590 | /* Record in RI that the block corresponding to it has an incoming | |
591 | live value, described by CHAIN. */ | |
592 | static void | |
593 | set_incoming_from_chain (struct bb_rename_info *ri, du_head_p chain) | |
594 | { | |
595 | int i; | |
596 | int incoming_nregs = ri->incoming[chain->regno].nregs; | |
597 | int nregs; | |
598 | ||
599 | /* If we've recorded the same information before, everything is fine. */ | |
600 | if (incoming_nregs == chain->nregs) | |
601 | { | |
602 | if (dump_file) | |
603 | fprintf (dump_file, "reg %d/%d already recorded\n", | |
604 | chain->regno, chain->nregs); | |
605 | return; | |
606 | } | |
607 | ||
608 | /* If we have no information for any of the involved registers, update | |
609 | the incoming array. */ | |
610 | nregs = chain->nregs; | |
611 | while (nregs-- > 0) | |
612 | if (ri->incoming[chain->regno + nregs].nregs != 0 | |
613 | || ri->incoming[chain->regno + nregs].unusable) | |
614 | break; | |
615 | if (nregs < 0) | |
616 | { | |
617 | nregs = chain->nregs; | |
618 | ri->incoming[chain->regno].nregs = nregs; | |
619 | while (nregs-- > 1) | |
620 | ri->incoming[chain->regno + nregs].nregs = -nregs; | |
621 | if (dump_file) | |
622 | fprintf (dump_file, "recorded reg %d/%d\n", | |
623 | chain->regno, chain->nregs); | |
624 | return; | |
625 | } | |
626 | ||
627 | /* There must be some kind of conflict. Prevent both the old and | |
628 | new ranges from being used. */ | |
629 | if (incoming_nregs < 0) | |
630 | ri->incoming[chain->regno + incoming_nregs].unusable = true; | |
631 | for (i = 0; i < chain->nregs; i++) | |
632 | ri->incoming[chain->regno + i].unusable = true; | |
633 | } | |
634 | ||
635 | /* Merge the two chains C1 and C2 so that all conflict information is | |
636 | recorded and C1, and the id of C2 is changed to that of C1. */ | |
637 | static void | |
638 | merge_chains (du_head_p c1, du_head_p c2) | |
639 | { | |
640 | if (c1 == c2) | |
641 | return; | |
642 | ||
643 | if (c2->first != NULL) | |
644 | { | |
645 | if (c1->first == NULL) | |
646 | c1->first = c2->first; | |
647 | else | |
648 | c1->last->next_use = c2->first; | |
649 | c1->last = c2->last; | |
650 | } | |
651 | ||
652 | c2->first = c2->last = NULL; | |
653 | c2->id = c1->id; | |
654 | ||
655 | IOR_HARD_REG_SET (c1->hard_conflicts, c2->hard_conflicts); | |
656 | bitmap_ior_into (&c1->conflicts, &c2->conflicts); | |
657 | ||
658 | c1->need_caller_save_reg |= c2->need_caller_save_reg; | |
659 | c1->cannot_rename |= c2->cannot_rename; | |
660 | } | |
661 | ||
662 | /* Analyze the current function and build chains for renaming. */ | |
663 | ||
1f234b83 BS |
664 | void |
665 | regrename_analyze (bitmap bb_mask) | |
8ffa0351 BS |
666 | { |
667 | struct bb_rename_info *rename_info; | |
668 | int i; | |
669 | basic_block bb; | |
670 | int n_bbs; | |
671 | int *inverse_postorder; | |
672 | ||
8b1c6fd7 | 673 | inverse_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun)); |
8ffa0351 BS |
674 | n_bbs = pre_and_rev_post_order_compute (NULL, inverse_postorder, false); |
675 | ||
676 | /* Gather some information about the blocks in this function. */ | |
0cae8d31 | 677 | rename_info = XCNEWVEC (struct bb_rename_info, n_basic_blocks_for_fn (cfun)); |
8ffa0351 | 678 | i = 0; |
11cd3bed | 679 | FOR_EACH_BB_FN (bb, cfun) |
8ffa0351 BS |
680 | { |
681 | struct bb_rename_info *ri = rename_info + i; | |
682 | ri->bb = bb; | |
1f234b83 BS |
683 | if (bb_mask != NULL && !bitmap_bit_p (bb_mask, bb->index)) |
684 | bb->aux = NULL; | |
685 | else | |
686 | bb->aux = ri; | |
8ffa0351 BS |
687 | i++; |
688 | } | |
689 | ||
690 | current_id = 0; | |
9771b263 | 691 | id_to_chain.create (0); |
8ffa0351 BS |
692 | bitmap_initialize (&open_chains_set, &bitmap_default_obstack); |
693 | ||
694 | /* The order in which we visit blocks ensures that whenever | |
695 | possible, we only process a block after at least one of its | |
696 | predecessors, which provides a "seeding" effect to make the logic | |
697 | in set_incoming_from_chain and init_rename_info useful. */ | |
698 | ||
699 | for (i = 0; i < n_bbs; i++) | |
700 | { | |
06e28de2 | 701 | basic_block bb1 = BASIC_BLOCK_FOR_FN (cfun, inverse_postorder[i]); |
8ffa0351 BS |
702 | struct bb_rename_info *this_info; |
703 | bool success; | |
704 | edge e; | |
705 | edge_iterator ei; | |
9771b263 | 706 | int old_length = id_to_chain.length (); |
8ffa0351 BS |
707 | |
708 | this_info = (struct bb_rename_info *) bb1->aux; | |
709 | if (this_info == NULL) | |
710 | continue; | |
711 | ||
712 | if (dump_file) | |
713 | fprintf (dump_file, "\nprocessing block %d:\n", bb1->index); | |
714 | ||
715 | init_rename_info (this_info, bb1); | |
716 | ||
717 | success = build_def_use (bb1); | |
718 | if (!success) | |
719 | { | |
720 | if (dump_file) | |
721 | fprintf (dump_file, "failed\n"); | |
722 | bb1->aux = NULL; | |
9771b263 | 723 | id_to_chain.truncate (old_length); |
8ffa0351 BS |
724 | current_id = old_length; |
725 | bitmap_clear (&this_info->incoming_open_chains_set); | |
726 | open_chains = NULL; | |
9771b263 | 727 | if (insn_rr.exists ()) |
1f234b83 | 728 | { |
a755f004 | 729 | rtx_insn *insn; |
1f234b83 BS |
730 | FOR_BB_INSNS (bb1, insn) |
731 | { | |
9771b263 | 732 | insn_rr_info *p = &insn_rr[INSN_UID (insn)]; |
1f234b83 BS |
733 | p->op_info = NULL; |
734 | } | |
735 | } | |
8ffa0351 BS |
736 | continue; |
737 | } | |
738 | ||
739 | if (dump_file) | |
740 | dump_def_use_chain (old_length); | |
741 | bitmap_copy (&this_info->open_chains_set, &open_chains_set); | |
742 | ||
743 | /* Add successor blocks to the worklist if necessary, and record | |
744 | data about our own open chains at the end of this block, which | |
745 | will be used to pre-open chains when processing the successors. */ | |
746 | FOR_EACH_EDGE (e, ei, bb1->succs) | |
747 | { | |
748 | struct bb_rename_info *dest_ri; | |
749 | struct du_head *chain; | |
750 | ||
751 | if (dump_file) | |
752 | fprintf (dump_file, "successor block %d\n", e->dest->index); | |
753 | ||
754 | if (e->flags & (EDGE_EH | EDGE_ABNORMAL)) | |
755 | continue; | |
756 | dest_ri = (struct bb_rename_info *)e->dest->aux; | |
757 | if (dest_ri == NULL) | |
758 | continue; | |
759 | for (chain = open_chains; chain; chain = chain->next_chain) | |
760 | set_incoming_from_chain (dest_ri, chain); | |
761 | } | |
762 | } | |
763 | ||
764 | free (inverse_postorder); | |
765 | ||
766 | /* Now, combine the chains data we have gathered across basic block | |
767 | boundaries. | |
768 | ||
769 | For every basic block, there may be chains open at the start, or at the | |
770 | end. Rather than exclude them from renaming, we look for open chains | |
771 | with matching registers at the other side of the CFG edge. | |
772 | ||
773 | For a given chain using register R, open at the start of block B, we | |
774 | must find an open chain using R on the other side of every edge leading | |
775 | to B, if the register is live across this edge. In the code below, | |
776 | N_PREDS_USED counts the number of edges where the register is live, and | |
777 | N_PREDS_JOINED counts those where we found an appropriate chain for | |
778 | joining. | |
779 | ||
780 | We perform the analysis for both incoming and outgoing edges, but we | |
781 | only need to merge once (in the second part, after verifying outgoing | |
782 | edges). */ | |
11cd3bed | 783 | FOR_EACH_BB_FN (bb, cfun) |
8ffa0351 BS |
784 | { |
785 | struct bb_rename_info *bb_ri = (struct bb_rename_info *) bb->aux; | |
786 | unsigned j; | |
787 | bitmap_iterator bi; | |
788 | ||
789 | if (bb_ri == NULL) | |
790 | continue; | |
791 | ||
792 | if (dump_file) | |
793 | fprintf (dump_file, "processing bb %d in edges\n", bb->index); | |
794 | ||
795 | EXECUTE_IF_SET_IN_BITMAP (&bb_ri->incoming_open_chains_set, 0, j, bi) | |
796 | { | |
797 | edge e; | |
798 | edge_iterator ei; | |
1f234b83 | 799 | struct du_head *chain = regrename_chain_from_id (j); |
8ffa0351 BS |
800 | int n_preds_used = 0, n_preds_joined = 0; |
801 | ||
802 | FOR_EACH_EDGE (e, ei, bb->preds) | |
803 | { | |
804 | struct bb_rename_info *src_ri; | |
805 | unsigned k; | |
806 | bitmap_iterator bi2; | |
807 | HARD_REG_SET live; | |
808 | bool success = false; | |
809 | ||
810 | REG_SET_TO_HARD_REG_SET (live, df_get_live_out (e->src)); | |
811 | if (!range_overlaps_hard_reg_set_p (live, chain->regno, | |
812 | chain->nregs)) | |
813 | continue; | |
814 | n_preds_used++; | |
815 | ||
816 | if (e->flags & (EDGE_EH | EDGE_ABNORMAL)) | |
817 | continue; | |
818 | ||
819 | src_ri = (struct bb_rename_info *)e->src->aux; | |
820 | if (src_ri == NULL) | |
821 | continue; | |
822 | ||
823 | EXECUTE_IF_SET_IN_BITMAP (&src_ri->open_chains_set, | |
824 | 0, k, bi2) | |
825 | { | |
1f234b83 | 826 | struct du_head *outgoing_chain = regrename_chain_from_id (k); |
8ffa0351 BS |
827 | |
828 | if (outgoing_chain->regno == chain->regno | |
829 | && outgoing_chain->nregs == chain->nregs) | |
830 | { | |
831 | n_preds_joined++; | |
832 | success = true; | |
833 | break; | |
834 | } | |
835 | } | |
836 | if (!success && dump_file) | |
837 | fprintf (dump_file, "failure to match with pred block %d\n", | |
838 | e->src->index); | |
839 | } | |
840 | if (n_preds_joined < n_preds_used) | |
841 | { | |
842 | if (dump_file) | |
843 | fprintf (dump_file, "cannot rename chain %d\n", j); | |
844 | chain->cannot_rename = 1; | |
845 | } | |
846 | } | |
847 | } | |
11cd3bed | 848 | FOR_EACH_BB_FN (bb, cfun) |
8ffa0351 BS |
849 | { |
850 | struct bb_rename_info *bb_ri = (struct bb_rename_info *) bb->aux; | |
851 | unsigned j; | |
852 | bitmap_iterator bi; | |
853 | ||
854 | if (bb_ri == NULL) | |
855 | continue; | |
856 | ||
857 | if (dump_file) | |
858 | fprintf (dump_file, "processing bb %d out edges\n", bb->index); | |
859 | ||
860 | EXECUTE_IF_SET_IN_BITMAP (&bb_ri->open_chains_set, 0, j, bi) | |
861 | { | |
862 | edge e; | |
863 | edge_iterator ei; | |
1f234b83 | 864 | struct du_head *chain = regrename_chain_from_id (j); |
8ffa0351 BS |
865 | int n_succs_used = 0, n_succs_joined = 0; |
866 | ||
867 | FOR_EACH_EDGE (e, ei, bb->succs) | |
868 | { | |
869 | bool printed = false; | |
870 | struct bb_rename_info *dest_ri; | |
871 | unsigned k; | |
872 | bitmap_iterator bi2; | |
873 | HARD_REG_SET live; | |
874 | ||
875 | REG_SET_TO_HARD_REG_SET (live, df_get_live_in (e->dest)); | |
876 | if (!range_overlaps_hard_reg_set_p (live, chain->regno, | |
877 | chain->nregs)) | |
878 | continue; | |
879 | ||
880 | n_succs_used++; | |
881 | ||
882 | dest_ri = (struct bb_rename_info *)e->dest->aux; | |
883 | if (dest_ri == NULL) | |
884 | continue; | |
885 | ||
886 | EXECUTE_IF_SET_IN_BITMAP (&dest_ri->incoming_open_chains_set, | |
887 | 0, k, bi2) | |
888 | { | |
1f234b83 | 889 | struct du_head *incoming_chain = regrename_chain_from_id (k); |
8ffa0351 BS |
890 | |
891 | if (incoming_chain->regno == chain->regno | |
892 | && incoming_chain->nregs == chain->nregs) | |
893 | { | |
894 | if (dump_file) | |
895 | { | |
896 | if (!printed) | |
897 | fprintf (dump_file, | |
898 | "merging blocks for edge %d -> %d\n", | |
899 | e->src->index, e->dest->index); | |
900 | printed = true; | |
901 | fprintf (dump_file, | |
902 | " merging chains %d (->%d) and %d (->%d) [%s]\n", | |
903 | k, incoming_chain->id, j, chain->id, | |
904 | reg_names[incoming_chain->regno]); | |
905 | } | |
906 | ||
907 | merge_chains (chain, incoming_chain); | |
908 | n_succs_joined++; | |
909 | break; | |
910 | } | |
911 | } | |
912 | } | |
913 | if (n_succs_joined < n_succs_used) | |
914 | { | |
915 | if (dump_file) | |
916 | fprintf (dump_file, "cannot rename chain %d\n", | |
917 | j); | |
918 | chain->cannot_rename = 1; | |
919 | } | |
920 | } | |
921 | } | |
922 | ||
923 | free (rename_info); | |
924 | ||
11cd3bed | 925 | FOR_EACH_BB_FN (bb, cfun) |
8ffa0351 BS |
926 | bb->aux = NULL; |
927 | } | |
928 | ||
1f234b83 BS |
929 | void |
930 | regrename_do_replace (struct du_head *head, int reg) | |
7b82b5da | 931 | { |
9d324dde BS |
932 | struct du_chain *chain; |
933 | unsigned int base_regno = head->regno; | |
1f234b83 | 934 | enum machine_mode mode; |
b5b8b0ac | 935 | |
9d324dde | 936 | for (chain = head->first; chain; chain = chain->next_use) |
7b82b5da | 937 | { |
08394eef | 938 | unsigned int regno = ORIGINAL_REGNO (*chain->loc); |
9d324dde | 939 | struct reg_attrs *attr = REG_ATTRS (*chain->loc); |
b41310e2 | 940 | int reg_ptr = REG_POINTER (*chain->loc); |
d1d3c9a6 | 941 | |
b5b8b0ac AO |
942 | if (DEBUG_INSN_P (chain->insn) && REGNO (*chain->loc) != base_regno) |
943 | INSN_VAR_LOCATION_LOC (chain->insn) = gen_rtx_UNKNOWN_VAR_LOC (); | |
944 | else | |
945 | { | |
946 | *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg); | |
947 | if (regno >= FIRST_PSEUDO_REGISTER) | |
948 | ORIGINAL_REGNO (*chain->loc) = regno; | |
949 | REG_ATTRS (*chain->loc) = attr; | |
950 | REG_POINTER (*chain->loc) = reg_ptr; | |
951 | } | |
952 | ||
8e4bf5c7 | 953 | df_insn_rescan (chain->insn); |
7b82b5da | 954 | } |
1f234b83 BS |
955 | |
956 | mode = GET_MODE (*head->first->loc); | |
957 | head->regno = reg; | |
958 | head->nregs = hard_regno_nregs[reg][mode]; | |
7b82b5da SC |
959 | } |
960 | ||
7b82b5da | 961 | |
a96caf80 BS |
962 | /* True if we found a register with a size mismatch, which means that we |
963 | can't track its lifetime accurately. If so, we abort the current block | |
964 | without renaming. */ | |
965 | static bool fail_current_block; | |
966 | ||
d435810e BS |
967 | /* Return true if OP is a reg for which all bits are set in PSET, false |
968 | if all bits are clear. | |
969 | In other cases, set fail_current_block and return false. */ | |
1f924675 BS |
970 | |
971 | static bool | |
d435810e | 972 | verify_reg_in_set (rtx op, HARD_REG_SET *pset) |
1f924675 BS |
973 | { |
974 | unsigned regno, nregs; | |
975 | bool all_live, all_dead; | |
976 | if (!REG_P (op)) | |
977 | return false; | |
978 | ||
979 | regno = REGNO (op); | |
980 | nregs = hard_regno_nregs[regno][GET_MODE (op)]; | |
981 | all_live = all_dead = true; | |
982 | while (nregs-- > 0) | |
d435810e | 983 | if (TEST_HARD_REG_BIT (*pset, regno + nregs)) |
1f924675 BS |
984 | all_dead = false; |
985 | else | |
986 | all_live = false; | |
987 | if (!all_dead && !all_live) | |
988 | { | |
989 | fail_current_block = true; | |
990 | return false; | |
991 | } | |
d435810e BS |
992 | return all_live; |
993 | } | |
1f924675 | 994 | |
d435810e BS |
995 | /* Return true if OP is a reg that is being tracked already in some form. |
996 | May set fail_current_block if it sees an unhandled case of overlap. */ | |
1f924675 | 997 | |
d435810e BS |
998 | static bool |
999 | verify_reg_tracked (rtx op) | |
1000 | { | |
1001 | return (verify_reg_in_set (op, &live_hard_regs) | |
1002 | || verify_reg_in_set (op, &live_in_chains)); | |
1f924675 BS |
1003 | } |
1004 | ||
a96caf80 BS |
1005 | /* Called through note_stores. DATA points to a rtx_code, either SET or |
1006 | CLOBBER, which tells us which kind of rtx to look at. If we have a | |
1007 | match, record the set register in live_hard_regs and in the hard_conflicts | |
1008 | bitmap of open chains. */ | |
1009 | ||
1010 | static void | |
1011 | note_sets_clobbers (rtx x, const_rtx set, void *data) | |
1012 | { | |
1013 | enum rtx_code code = *(enum rtx_code *)data; | |
1014 | struct du_head *chain; | |
1015 | ||
1016 | if (GET_CODE (x) == SUBREG) | |
1017 | x = SUBREG_REG (x); | |
1018 | if (!REG_P (x) || GET_CODE (set) != code) | |
1019 | return; | |
1020 | /* There must not be pseudos at this point. */ | |
1021 | gcc_assert (HARD_REGISTER_P (x)); | |
1022 | add_to_hard_reg_set (&live_hard_regs, GET_MODE (x), REGNO (x)); | |
1023 | for (chain = open_chains; chain; chain = chain->next_chain) | |
1024 | add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x)); | |
1025 | } | |
1026 | ||
541f7d56 | 1027 | static void |
a755f004 | 1028 | scan_rtx_reg (rtx_insn *insn, rtx *loc, enum reg_class cl, enum scan_actions action, |
6bda9bdf | 1029 | enum op_type type) |
7b82b5da | 1030 | { |
9d324dde | 1031 | struct du_head **p; |
541f7d56 BS |
1032 | rtx x = *loc; |
1033 | enum machine_mode mode = GET_MODE (x); | |
9d324dde | 1034 | unsigned this_regno = REGNO (x); |
8ffa0351 | 1035 | int this_nregs = hard_regno_nregs[this_regno][mode]; |
541f7d56 | 1036 | |
541f7d56 | 1037 | if (action == mark_write) |
7b82b5da | 1038 | { |
541f7d56 | 1039 | if (type == OP_OUT) |
e33c42db | 1040 | create_new_chain (this_regno, this_nregs, loc, insn, cl); |
541f7d56 | 1041 | return; |
7b82b5da | 1042 | } |
1a43c33f | 1043 | |
cb110f3d | 1044 | if ((type == OP_OUT) != (action == terminate_write || action == mark_access)) |
541f7d56 | 1045 | return; |
5fa41e13 | 1046 | |
541f7d56 | 1047 | for (p = &open_chains; *p;) |
5fa41e13 | 1048 | { |
9d324dde | 1049 | struct du_head *head = *p; |
a96caf80 BS |
1050 | struct du_head *next = head->next_chain; |
1051 | int exact_match = (head->regno == this_regno | |
1052 | && head->nregs == this_nregs); | |
1053 | int superset = (this_regno <= head->regno | |
1054 | && this_regno + this_nregs >= head->regno + head->nregs); | |
d435810e BS |
1055 | int subset = (this_regno >= head->regno |
1056 | && this_regno + this_nregs <= head->regno + head->nregs); | |
a96caf80 | 1057 | |
d3e80850 | 1058 | if (!bitmap_bit_p (&open_chains_set, head->id) |
a96caf80 BS |
1059 | || head->regno + head->nregs <= this_regno |
1060 | || this_regno + this_nregs <= head->regno) | |
1061 | { | |
1062 | p = &head->next_chain; | |
1063 | continue; | |
1064 | } | |
541f7d56 | 1065 | |
a96caf80 | 1066 | if (action == mark_read || action == mark_access) |
3b03c671 | 1067 | { |
a96caf80 BS |
1068 | /* ??? Class NO_REGS can happen if the md file makes use of |
1069 | EXTRA_CONSTRAINTS to match registers. Which is arguably | |
1070 | wrong, but there we are. */ | |
695e4773 | 1071 | |
a96caf80 | 1072 | if (cl == NO_REGS || (!exact_match && !DEBUG_INSN_P (insn))) |
a125d855 | 1073 | { |
a96caf80 BS |
1074 | if (dump_file) |
1075 | fprintf (dump_file, | |
1076 | "Cannot rename chain %s (%d) at insn %d (%s)\n", | |
1077 | reg_names[head->regno], head->id, INSN_UID (insn), | |
1078 | scan_actions_name[(int) action]); | |
1079 | head->cannot_rename = 1; | |
d435810e BS |
1080 | if (superset) |
1081 | { | |
1082 | unsigned nregs = this_nregs; | |
1083 | head->regno = this_regno; | |
1084 | head->nregs = this_nregs; | |
1085 | while (nregs-- > 0) | |
1086 | SET_HARD_REG_BIT (live_in_chains, head->regno + nregs); | |
1087 | if (dump_file) | |
1088 | fprintf (dump_file, | |
1089 | "Widening register in chain %s (%d) at insn %d\n", | |
1090 | reg_names[head->regno], head->id, INSN_UID (insn)); | |
1091 | } | |
1092 | else if (!subset) | |
1093 | { | |
1094 | fail_current_block = true; | |
1095 | if (dump_file) | |
1096 | fprintf (dump_file, | |
1097 | "Failing basic block due to unhandled overlap\n"); | |
1098 | } | |
a125d855 | 1099 | } |
a96caf80 | 1100 | else |
541f7d56 | 1101 | { |
a96caf80 BS |
1102 | struct du_chain *this_du; |
1103 | this_du = XOBNEW (&rename_obstack, struct du_chain); | |
1104 | this_du->next_use = 0; | |
1105 | this_du->loc = loc; | |
1106 | this_du->insn = insn; | |
1107 | this_du->cl = cl; | |
e33c42db BS |
1108 | if (head->first == NULL) |
1109 | head->first = this_du; | |
1110 | else | |
1111 | head->last->next_use = this_du; | |
1f234b83 | 1112 | record_operand_use (head, this_du); |
a96caf80 | 1113 | head->last = this_du; |
541f7d56 | 1114 | } |
a96caf80 BS |
1115 | /* Avoid adding the same location in a DEBUG_INSN multiple times, |
1116 | which could happen with non-exact overlap. */ | |
1117 | if (DEBUG_INSN_P (insn)) | |
1118 | return; | |
1119 | /* Otherwise, find any other chains that do not match exactly; | |
1120 | ensure they all get marked unrenamable. */ | |
1121 | p = &head->next_chain; | |
1122 | continue; | |
1123 | } | |
a125d855 | 1124 | |
a96caf80 BS |
1125 | /* Whether the terminated chain can be used for renaming |
1126 | depends on the action and this being an exact match. | |
1127 | In either case, we remove this element from open_chains. */ | |
695e4773 | 1128 | |
a96caf80 | 1129 | if ((action == terminate_dead || action == terminate_write) |
998c75b6 | 1130 | && (superset || subset)) |
a96caf80 | 1131 | { |
1f924675 BS |
1132 | unsigned nregs; |
1133 | ||
998c75b6 BS |
1134 | if (subset && !superset) |
1135 | head->cannot_rename = 1; | |
a96caf80 | 1136 | bitmap_clear_bit (&open_chains_set, head->id); |
1f924675 BS |
1137 | |
1138 | nregs = head->nregs; | |
1139 | while (nregs-- > 0) | |
998c75b6 BS |
1140 | { |
1141 | CLEAR_HARD_REG_BIT (live_in_chains, head->regno + nregs); | |
1142 | if (subset && !superset | |
1143 | && (head->regno + nregs < this_regno | |
1144 | || head->regno + nregs >= this_regno + this_nregs)) | |
1145 | SET_HARD_REG_BIT (live_hard_regs, head->regno + nregs); | |
1146 | } | |
1f924675 | 1147 | |
a96caf80 BS |
1148 | *p = next; |
1149 | if (dump_file) | |
1150 | fprintf (dump_file, | |
998c75b6 | 1151 | "Closing chain %s (%d) at insn %d (%s%s)\n", |
a96caf80 | 1152 | reg_names[head->regno], head->id, INSN_UID (insn), |
998c75b6 BS |
1153 | scan_actions_name[(int) action], |
1154 | superset ? ", superset" : subset ? ", subset" : ""); | |
a96caf80 BS |
1155 | } |
1156 | else if (action == terminate_dead || action == terminate_write) | |
1157 | { | |
1158 | /* In this case, tracking liveness gets too hard. Fail the | |
1159 | entire basic block. */ | |
1160 | if (dump_file) | |
1161 | fprintf (dump_file, | |
1162 | "Failing basic block due to unhandled overlap\n"); | |
1163 | fail_current_block = true; | |
1164 | return; | |
1165 | } | |
1166 | else | |
1167 | { | |
1168 | head->cannot_rename = 1; | |
1169 | if (dump_file) | |
1170 | fprintf (dump_file, | |
1171 | "Cannot rename chain %s (%d) at insn %d (%s)\n", | |
1172 | reg_names[head->regno], head->id, INSN_UID (insn), | |
1173 | scan_actions_name[(int) action]); | |
1174 | p = &head->next_chain; | |
541f7d56 | 1175 | } |
541f7d56 | 1176 | } |
7b82b5da SC |
1177 | } |
1178 | ||
e3a64162 | 1179 | /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or |
541f7d56 | 1180 | BASE_REG_CLASS depending on how the register is being considered. */ |
7b82b5da | 1181 | |
4ca0f257 | 1182 | static void |
a755f004 | 1183 | scan_rtx_address (rtx_insn *insn, rtx *loc, enum reg_class cl, |
86fc3d06 UW |
1184 | enum scan_actions action, enum machine_mode mode, |
1185 | addr_space_t as) | |
7b82b5da | 1186 | { |
541f7d56 BS |
1187 | rtx x = *loc; |
1188 | RTX_CODE code = GET_CODE (x); | |
1189 | const char *fmt; | |
1190 | int i, j; | |
7b82b5da | 1191 | |
cb110f3d | 1192 | if (action == mark_write || action == mark_access) |
541f7d56 | 1193 | return; |
7b82b5da | 1194 | |
541f7d56 | 1195 | switch (code) |
7b82b5da | 1196 | { |
541f7d56 BS |
1197 | case PLUS: |
1198 | { | |
1199 | rtx orig_op0 = XEXP (x, 0); | |
1200 | rtx orig_op1 = XEXP (x, 1); | |
1201 | RTX_CODE code0 = GET_CODE (orig_op0); | |
1202 | RTX_CODE code1 = GET_CODE (orig_op1); | |
1203 | rtx op0 = orig_op0; | |
1204 | rtx op1 = orig_op1; | |
1205 | rtx *locI = NULL; | |
1206 | rtx *locB = NULL; | |
84c9cb12 | 1207 | enum rtx_code index_code = SCRATCH; |
541f7d56 BS |
1208 | |
1209 | if (GET_CODE (op0) == SUBREG) | |
1210 | { | |
1211 | op0 = SUBREG_REG (op0); | |
1212 | code0 = GET_CODE (op0); | |
1213 | } | |
7b82b5da | 1214 | |
541f7d56 BS |
1215 | if (GET_CODE (op1) == SUBREG) |
1216 | { | |
1217 | op1 = SUBREG_REG (op1); | |
1218 | code1 = GET_CODE (op1); | |
1219 | } | |
7b82b5da | 1220 | |
541f7d56 BS |
1221 | if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE |
1222 | || code0 == ZERO_EXTEND || code1 == MEM) | |
1223 | { | |
1224 | locI = &XEXP (x, 0); | |
1225 | locB = &XEXP (x, 1); | |
c4963a0a | 1226 | index_code = GET_CODE (*locI); |
541f7d56 BS |
1227 | } |
1228 | else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE | |
1229 | || code1 == ZERO_EXTEND || code0 == MEM) | |
1230 | { | |
1231 | locI = &XEXP (x, 1); | |
1232 | locB = &XEXP (x, 0); | |
c4963a0a | 1233 | index_code = GET_CODE (*locI); |
541f7d56 BS |
1234 | } |
1235 | else if (code0 == CONST_INT || code0 == CONST | |
1236 | || code0 == SYMBOL_REF || code0 == LABEL_REF) | |
c4963a0a BS |
1237 | { |
1238 | locB = &XEXP (x, 1); | |
1239 | index_code = GET_CODE (XEXP (x, 0)); | |
1240 | } | |
541f7d56 BS |
1241 | else if (code1 == CONST_INT || code1 == CONST |
1242 | || code1 == SYMBOL_REF || code1 == LABEL_REF) | |
c4963a0a BS |
1243 | { |
1244 | locB = &XEXP (x, 0); | |
1245 | index_code = GET_CODE (XEXP (x, 1)); | |
1246 | } | |
541f7d56 BS |
1247 | else if (code0 == REG && code1 == REG) |
1248 | { | |
1249 | int index_op; | |
c4963a0a | 1250 | unsigned regno0 = REGNO (op0), regno1 = REGNO (op1); |
541f7d56 | 1251 | |
bd379f73 | 1252 | if (REGNO_OK_FOR_INDEX_P (regno1) |
86fc3d06 | 1253 | && regno_ok_for_base_p (regno0, mode, as, PLUS, REG)) |
bd379f73 PH |
1254 | index_op = 1; |
1255 | else if (REGNO_OK_FOR_INDEX_P (regno0) | |
86fc3d06 | 1256 | && regno_ok_for_base_p (regno1, mode, as, PLUS, REG)) |
541f7d56 | 1257 | index_op = 0; |
86fc3d06 | 1258 | else if (regno_ok_for_base_p (regno0, mode, as, PLUS, REG) |
bd379f73 | 1259 | || REGNO_OK_FOR_INDEX_P (regno1)) |
541f7d56 | 1260 | index_op = 1; |
86fc3d06 | 1261 | else if (regno_ok_for_base_p (regno1, mode, as, PLUS, REG)) |
541f7d56 | 1262 | index_op = 0; |
541f7d56 | 1263 | else |
bd379f73 | 1264 | index_op = 1; |
541f7d56 BS |
1265 | |
1266 | locI = &XEXP (x, index_op); | |
c4963a0a BS |
1267 | locB = &XEXP (x, !index_op); |
1268 | index_code = GET_CODE (*locI); | |
541f7d56 BS |
1269 | } |
1270 | else if (code0 == REG) | |
1271 | { | |
1272 | locI = &XEXP (x, 0); | |
1273 | locB = &XEXP (x, 1); | |
c4963a0a | 1274 | index_code = GET_CODE (*locI); |
541f7d56 BS |
1275 | } |
1276 | else if (code1 == REG) | |
1277 | { | |
1278 | locI = &XEXP (x, 1); | |
1279 | locB = &XEXP (x, 0); | |
c4963a0a | 1280 | index_code = GET_CODE (*locI); |
541f7d56 | 1281 | } |
7b82b5da | 1282 | |
541f7d56 | 1283 | if (locI) |
86fc3d06 | 1284 | scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode, as); |
541f7d56 | 1285 | if (locB) |
86fc3d06 UW |
1286 | scan_rtx_address (insn, locB, |
1287 | base_reg_class (mode, as, PLUS, index_code), | |
1288 | action, mode, as); | |
c4963a0a | 1289 | |
541f7d56 BS |
1290 | return; |
1291 | } | |
7b82b5da | 1292 | |
541f7d56 BS |
1293 | case POST_INC: |
1294 | case POST_DEC: | |
1295 | case POST_MODIFY: | |
1296 | case PRE_INC: | |
1297 | case PRE_DEC: | |
1298 | case PRE_MODIFY: | |
1299 | #ifndef AUTO_INC_DEC | |
ce73761f RH |
1300 | /* If the target doesn't claim to handle autoinc, this must be |
1301 | something special, like a stack push. Kill this chain. */ | |
a96caf80 | 1302 | action = mark_all_read; |
541f7d56 BS |
1303 | #endif |
1304 | break; | |
7b82b5da | 1305 | |
541f7d56 | 1306 | case MEM: |
3dcc68a4 | 1307 | scan_rtx_address (insn, &XEXP (x, 0), |
86fc3d06 UW |
1308 | base_reg_class (GET_MODE (x), MEM_ADDR_SPACE (x), |
1309 | MEM, SCRATCH), | |
1310 | action, GET_MODE (x), MEM_ADDR_SPACE (x)); | |
541f7d56 | 1311 | return; |
1a43c33f | 1312 | |
541f7d56 | 1313 | case REG: |
6bda9bdf | 1314 | scan_rtx_reg (insn, loc, cl, action, OP_IN); |
4ca0f257 | 1315 | return; |
1a43c33f | 1316 | |
541f7d56 BS |
1317 | default: |
1318 | break; | |
4ca0f257 | 1319 | } |
541f7d56 BS |
1320 | |
1321 | fmt = GET_RTX_FORMAT (code); | |
1322 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
4ca0f257 | 1323 | { |
541f7d56 | 1324 | if (fmt[i] == 'e') |
86fc3d06 | 1325 | scan_rtx_address (insn, &XEXP (x, i), cl, action, mode, as); |
541f7d56 BS |
1326 | else if (fmt[i] == 'E') |
1327 | for (j = XVECLEN (x, i) - 1; j >= 0; j--) | |
86fc3d06 | 1328 | scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode, as); |
4ca0f257 | 1329 | } |
7b82b5da SC |
1330 | } |
1331 | ||
541f7d56 | 1332 | static void |
a755f004 | 1333 | scan_rtx (rtx_insn *insn, rtx *loc, enum reg_class cl, enum scan_actions action, |
6bda9bdf | 1334 | enum op_type type) |
7b82b5da | 1335 | { |
541f7d56 BS |
1336 | const char *fmt; |
1337 | rtx x = *loc; | |
1338 | enum rtx_code code = GET_CODE (x); | |
1339 | int i, j; | |
7b82b5da | 1340 | |
541f7d56 BS |
1341 | code = GET_CODE (x); |
1342 | switch (code) | |
7b82b5da | 1343 | { |
541f7d56 | 1344 | case CONST: |
d8116890 | 1345 | CASE_CONST_ANY: |
541f7d56 BS |
1346 | case SYMBOL_REF: |
1347 | case LABEL_REF: | |
1348 | case CC0: | |
1349 | case PC: | |
1350 | return; | |
055be976 | 1351 | |
541f7d56 | 1352 | case REG: |
6bda9bdf | 1353 | scan_rtx_reg (insn, loc, cl, action, type); |
541f7d56 | 1354 | return; |
7b82b5da | 1355 | |
541f7d56 | 1356 | case MEM: |
3dcc68a4 | 1357 | scan_rtx_address (insn, &XEXP (x, 0), |
86fc3d06 UW |
1358 | base_reg_class (GET_MODE (x), MEM_ADDR_SPACE (x), |
1359 | MEM, SCRATCH), | |
1360 | action, GET_MODE (x), MEM_ADDR_SPACE (x)); | |
541f7d56 | 1361 | return; |
7b82b5da | 1362 | |
541f7d56 | 1363 | case SET: |
6bda9bdf | 1364 | scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN); |
4e5813dd | 1365 | scan_rtx (insn, &SET_DEST (x), cl, action, |
1f924675 BS |
1366 | (GET_CODE (PATTERN (insn)) == COND_EXEC |
1367 | && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT); | |
541f7d56 | 1368 | return; |
7b82b5da | 1369 | |
541f7d56 | 1370 | case STRICT_LOW_PART: |
c4137918 BS |
1371 | scan_rtx (insn, &XEXP (x, 0), cl, action, |
1372 | verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT); | |
541f7d56 | 1373 | return; |
7b82b5da | 1374 | |
541f7d56 | 1375 | case ZERO_EXTRACT: |
3b03c671 | 1376 | case SIGN_EXTRACT: |
e3a64162 | 1377 | scan_rtx (insn, &XEXP (x, 0), cl, action, |
c4137918 BS |
1378 | (type == OP_IN ? OP_IN : |
1379 | verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT)); | |
6bda9bdf BS |
1380 | scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN); |
1381 | scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN); | |
541f7d56 | 1382 | return; |
7b82b5da | 1383 | |
541f7d56 BS |
1384 | case POST_INC: |
1385 | case PRE_INC: | |
1386 | case POST_DEC: | |
1387 | case PRE_DEC: | |
1388 | case POST_MODIFY: | |
1389 | case PRE_MODIFY: | |
1390 | /* Should only happen inside MEM. */ | |
41374e13 | 1391 | gcc_unreachable (); |
541f7d56 BS |
1392 | |
1393 | case CLOBBER: | |
4e5813dd | 1394 | scan_rtx (insn, &SET_DEST (x), cl, action, |
1f924675 BS |
1395 | (GET_CODE (PATTERN (insn)) == COND_EXEC |
1396 | && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT); | |
541f7d56 | 1397 | return; |
7b82b5da | 1398 | |
541f7d56 | 1399 | case EXPR_LIST: |
6bda9bdf | 1400 | scan_rtx (insn, &XEXP (x, 0), cl, action, type); |
541f7d56 | 1401 | if (XEXP (x, 1)) |
6bda9bdf | 1402 | scan_rtx (insn, &XEXP (x, 1), cl, action, type); |
541f7d56 | 1403 | return; |
7b82b5da | 1404 | |
541f7d56 BS |
1405 | default: |
1406 | break; | |
1407 | } | |
7b82b5da | 1408 | |
541f7d56 BS |
1409 | fmt = GET_RTX_FORMAT (code); |
1410 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
7b82b5da SC |
1411 | { |
1412 | if (fmt[i] == 'e') | |
6bda9bdf | 1413 | scan_rtx (insn, &XEXP (x, i), cl, action, type); |
7b82b5da SC |
1414 | else if (fmt[i] == 'E') |
1415 | for (j = XVECLEN (x, i) - 1; j >= 0; j--) | |
6bda9bdf BS |
1416 | scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type); |
1417 | } | |
1418 | } | |
1419 | ||
1420 | /* Hide operands of the current insn (of which there are N_OPS) by | |
1421 | substituting cc0 for them. | |
1422 | Previous values are stored in the OLD_OPERANDS and OLD_DUPS. | |
d435810e | 1423 | For every bit set in DO_NOT_HIDE, we leave the operand alone. |
a96caf80 BS |
1424 | If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands |
1425 | and earlyclobbers. */ | |
6bda9bdf BS |
1426 | |
1427 | static void | |
1428 | hide_operands (int n_ops, rtx *old_operands, rtx *old_dups, | |
d435810e | 1429 | unsigned HOST_WIDE_INT do_not_hide, bool inout_and_ec_only) |
6bda9bdf BS |
1430 | { |
1431 | int i; | |
5efe5dec | 1432 | const operand_alternative *op_alt = which_op_alt (); |
6bda9bdf BS |
1433 | for (i = 0; i < n_ops; i++) |
1434 | { | |
1435 | old_operands[i] = recog_data.operand[i]; | |
1436 | /* Don't squash match_operator or match_parallel here, since | |
1437 | we don't know that all of the contained registers are | |
1438 | reachable by proper operands. */ | |
1439 | if (recog_data.constraints[i][0] == '\0') | |
1440 | continue; | |
d435810e BS |
1441 | if (do_not_hide & (1 << i)) |
1442 | continue; | |
a96caf80 | 1443 | if (!inout_and_ec_only || recog_data.operand_type[i] == OP_INOUT |
29d70a0f | 1444 | || op_alt[i].earlyclobber) |
6bda9bdf BS |
1445 | *recog_data.operand_loc[i] = cc0_rtx; |
1446 | } | |
1447 | for (i = 0; i < recog_data.n_dups; i++) | |
1448 | { | |
1449 | int opn = recog_data.dup_num[i]; | |
1450 | old_dups[i] = *recog_data.dup_loc[i]; | |
d435810e BS |
1451 | if (do_not_hide & (1 << opn)) |
1452 | continue; | |
a96caf80 | 1453 | if (!inout_and_ec_only || recog_data.operand_type[opn] == OP_INOUT |
29d70a0f | 1454 | || op_alt[opn].earlyclobber) |
6bda9bdf BS |
1455 | *recog_data.dup_loc[i] = cc0_rtx; |
1456 | } | |
1457 | } | |
1458 | ||
1459 | /* Undo the substitution performed by hide_operands. INSN is the insn we | |
1460 | are processing; the arguments are the same as in hide_operands. */ | |
1461 | ||
1462 | static void | |
a755f004 | 1463 | restore_operands (rtx_insn *insn, int n_ops, rtx *old_operands, rtx *old_dups) |
6bda9bdf BS |
1464 | { |
1465 | int i; | |
1466 | for (i = 0; i < recog_data.n_dups; i++) | |
1467 | *recog_data.dup_loc[i] = old_dups[i]; | |
1468 | for (i = 0; i < n_ops; i++) | |
1469 | *recog_data.operand_loc[i] = old_operands[i]; | |
1470 | if (recog_data.n_dups) | |
1471 | df_insn_rescan (insn); | |
1472 | } | |
1473 | ||
1474 | /* For each output operand of INSN, call scan_rtx to create a new | |
a96caf80 | 1475 | open chain. Do this only for normal or earlyclobber outputs, |
1f234b83 BS |
1476 | depending on EARLYCLOBBER. If INSN_INFO is nonnull, use it to |
1477 | record information about the operands in the insn. */ | |
6bda9bdf BS |
1478 | |
1479 | static void | |
a755f004 | 1480 | record_out_operands (rtx_insn *insn, bool earlyclobber, insn_rr_info *insn_info) |
6bda9bdf BS |
1481 | { |
1482 | int n_ops = recog_data.n_operands; | |
5efe5dec | 1483 | const operand_alternative *op_alt = which_op_alt (); |
6bda9bdf BS |
1484 | |
1485 | int i; | |
1486 | ||
1487 | for (i = 0; i < n_ops + recog_data.n_dups; i++) | |
1488 | { | |
1489 | int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; | |
1490 | rtx *loc = (i < n_ops | |
1491 | ? recog_data.operand_loc[opn] | |
1492 | : recog_data.dup_loc[i - n_ops]); | |
1493 | rtx op = *loc; | |
5efe5dec | 1494 | enum reg_class cl = alternative_class (op_alt, opn); |
6bda9bdf BS |
1495 | |
1496 | struct du_head *prev_open; | |
1497 | ||
a96caf80 | 1498 | if (recog_data.operand_type[opn] != OP_OUT |
29d70a0f | 1499 | || op_alt[opn].earlyclobber != earlyclobber) |
6bda9bdf BS |
1500 | continue; |
1501 | ||
1f234b83 BS |
1502 | if (insn_info) |
1503 | cur_operand = insn_info->op_info + i; | |
1504 | ||
6bda9bdf BS |
1505 | prev_open = open_chains; |
1506 | scan_rtx (insn, loc, cl, mark_write, OP_OUT); | |
1507 | ||
1508 | /* ??? Many targets have output constraints on the SET_DEST | |
1509 | of a call insn, which is stupid, since these are certainly | |
1510 | ABI defined hard registers. For these, and for asm operands | |
1511 | that originally referenced hard registers, we must record that | |
1512 | the chain cannot be renamed. */ | |
1513 | if (CALL_P (insn) | |
1514 | || (asm_noperands (PATTERN (insn)) > 0 | |
1515 | && REG_P (op) | |
1516 | && REGNO (op) == ORIGINAL_REGNO (op))) | |
1517 | { | |
1518 | if (prev_open != open_chains) | |
a96caf80 | 1519 | open_chains->cannot_rename = 1; |
6bda9bdf | 1520 | } |
7b82b5da | 1521 | } |
1f234b83 | 1522 | cur_operand = NULL; |
7b82b5da SC |
1523 | } |
1524 | ||
3eae4643 | 1525 | /* Build def/use chain. */ |
7b82b5da | 1526 | |
8ffa0351 | 1527 | static bool |
0c20a65f | 1528 | build_def_use (basic_block bb) |
7b82b5da | 1529 | { |
a755f004 | 1530 | rtx_insn *insn; |
d435810e | 1531 | unsigned HOST_WIDE_INT untracked_operands; |
1a43c33f | 1532 | |
a96caf80 BS |
1533 | fail_current_block = false; |
1534 | ||
a813c111 | 1535 | for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) |
541f7d56 | 1536 | { |
b5b8b0ac | 1537 | if (NONDEBUG_INSN_P (insn)) |
541f7d56 BS |
1538 | { |
1539 | int n_ops; | |
1540 | rtx note; | |
1541 | rtx old_operands[MAX_RECOG_OPERANDS]; | |
1542 | rtx old_dups[MAX_DUP_OPERANDS]; | |
0f900dfa | 1543 | int i; |
541f7d56 | 1544 | int predicated; |
a96caf80 BS |
1545 | enum rtx_code set_code = SET; |
1546 | enum rtx_code clobber_code = CLOBBER; | |
1f234b83 | 1547 | insn_rr_info *insn_info = NULL; |
541f7d56 | 1548 | |
541f7d56 | 1549 | /* Process the insn, determining its effect on the def-use |
a96caf80 BS |
1550 | chains and live hard registers. We perform the following |
1551 | steps with the register references in the insn, simulating | |
1552 | its effect: | |
1553 | (1) Deal with earlyclobber operands and CLOBBERs of non-operands | |
1554 | by creating chains and marking hard regs live. | |
541f7d56 | 1555 | (2) Any read outside an operand causes any chain it overlaps |
a96caf80 | 1556 | with to be marked unrenamable. |
541f7d56 BS |
1557 | (3) Any read inside an operand is added if there's already |
1558 | an open chain for it. | |
1559 | (4) For any REG_DEAD note we find, close open chains that | |
1560 | overlap it. | |
a96caf80 BS |
1561 | (5) For any non-earlyclobber write we find, close open chains |
1562 | that overlap it. | |
1563 | (6) For any non-earlyclobber write we find in an operand, make | |
1564 | a new chain or mark the hard register as live. | |
1565 | (7) For any REG_UNUSED, close any chains we just opened. | |
1566 | ||
1567 | We cannot deal with situations where we track a reg in one mode | |
1568 | and see a reference in another mode; these will cause the chain | |
1569 | to be marked unrenamable or even cause us to abort the entire | |
1570 | basic block. */ | |
541f7d56 BS |
1571 | |
1572 | extract_insn (insn); | |
4be9e9cb | 1573 | if (! constrain_operands (1)) |
3b03c671 | 1574 | fatal_insn_not_found (insn); |
1145837d | 1575 | preprocess_constraints (insn); |
5efe5dec | 1576 | const operand_alternative *op_alt = which_op_alt (); |
541f7d56 | 1577 | n_ops = recog_data.n_operands; |
d435810e | 1578 | untracked_operands = 0; |
541f7d56 | 1579 | |
9771b263 | 1580 | if (insn_rr.exists ()) |
1f234b83 | 1581 | { |
9771b263 | 1582 | insn_info = &insn_rr[INSN_UID (insn)]; |
1f234b83 BS |
1583 | insn_info->op_info = XOBNEWVEC (&rename_obstack, operand_rr_info, |
1584 | recog_data.n_operands); | |
1585 | memset (insn_info->op_info, 0, | |
1586 | sizeof (operand_rr_info) * recog_data.n_operands); | |
1587 | } | |
1588 | ||
5efe5dec | 1589 | /* Simplify the code below by promoting OP_OUT to OP_INOUT in |
1f924675 BS |
1590 | predicated instructions, but only for register operands |
1591 | that are already tracked, so that we can create a chain | |
1592 | when the first SET makes a register live. */ | |
541f7d56 BS |
1593 | |
1594 | predicated = GET_CODE (PATTERN (insn)) == COND_EXEC; | |
1595 | for (i = 0; i < n_ops; ++i) | |
7b82b5da | 1596 | { |
e33c42db | 1597 | rtx op = recog_data.operand[i]; |
29d70a0f | 1598 | int matches = op_alt[i].matches; |
29d70a0f | 1599 | if (matches >= 0 || op_alt[i].matched >= 0 |
e33c42db | 1600 | || (predicated && recog_data.operand_type[i] == OP_OUT)) |
a96caf80 BS |
1601 | { |
1602 | recog_data.operand_type[i] = OP_INOUT; | |
d435810e BS |
1603 | /* A special case to deal with instruction patterns that |
1604 | have matching operands with different modes. If we're | |
1605 | not already tracking such a reg, we won't start here, | |
1606 | and we must instead make sure to make the operand visible | |
1607 | to the machinery that tracks hard registers. */ | |
a96caf80 BS |
1608 | if (matches >= 0 |
1609 | && (GET_MODE_SIZE (recog_data.operand_mode[i]) | |
d435810e BS |
1610 | != GET_MODE_SIZE (recog_data.operand_mode[matches])) |
1611 | && !verify_reg_in_set (op, &live_in_chains)) | |
1612 | { | |
1613 | untracked_operands |= 1 << i; | |
1614 | untracked_operands |= 1 << matches; | |
1615 | } | |
a96caf80 | 1616 | } |
c4137918 | 1617 | /* If there's an in-out operand with a register that is not |
e33c42db | 1618 | being tracked at all yet, open a chain. */ |
c4137918 BS |
1619 | if (recog_data.operand_type[i] == OP_INOUT |
1620 | && !(untracked_operands & (1 << i)) | |
e33c42db BS |
1621 | && REG_P (op) |
1622 | && !verify_reg_tracked (op)) | |
c4137918 | 1623 | { |
e33c42db BS |
1624 | enum machine_mode mode = GET_MODE (op); |
1625 | unsigned this_regno = REGNO (op); | |
1626 | unsigned this_nregs = hard_regno_nregs[this_regno][mode]; | |
a755f004 | 1627 | create_new_chain (this_regno, this_nregs, NULL, NULL, |
e33c42db | 1628 | NO_REGS); |
c4137918 | 1629 | } |
7b82b5da | 1630 | } |
1a43c33f | 1631 | |
a96caf80 BS |
1632 | if (fail_current_block) |
1633 | break; | |
1634 | ||
1635 | /* Step 1a: Mark hard registers that are clobbered in this insn, | |
1636 | outside an operand, as live. */ | |
d435810e BS |
1637 | hide_operands (n_ops, old_operands, old_dups, untracked_operands, |
1638 | false); | |
a96caf80 BS |
1639 | note_stores (PATTERN (insn), note_sets_clobbers, &clobber_code); |
1640 | restore_operands (insn, n_ops, old_operands, old_dups); | |
1641 | ||
1642 | /* Step 1b: Begin new chains for earlyclobbered writes inside | |
1643 | operands. */ | |
1f234b83 | 1644 | record_out_operands (insn, true, insn_info); |
1a43c33f | 1645 | |
a96caf80 BS |
1646 | /* Step 2: Mark chains for which we have reads outside operands |
1647 | as unrenamable. | |
3b03c671 | 1648 | We do this by munging all operands into CC0, and closing |
541f7d56 | 1649 | everything remaining. */ |
7b82b5da | 1650 | |
d435810e BS |
1651 | hide_operands (n_ops, old_operands, old_dups, untracked_operands, |
1652 | false); | |
a96caf80 | 1653 | scan_rtx (insn, &PATTERN (insn), NO_REGS, mark_all_read, OP_IN); |
6bda9bdf | 1654 | restore_operands (insn, n_ops, old_operands, old_dups); |
7b82b5da | 1655 | |
541f7d56 | 1656 | /* Step 2B: Can't rename function call argument registers. */ |
4b4bf941 | 1657 | if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn)) |
541f7d56 | 1658 | scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn), |
a96caf80 | 1659 | NO_REGS, mark_all_read, OP_IN); |
7b82b5da | 1660 | |
3ada20ee RH |
1661 | /* Step 2C: Can't rename asm operands that were originally |
1662 | hard registers. */ | |
1663 | if (asm_noperands (PATTERN (insn)) > 0) | |
1664 | for (i = 0; i < n_ops; i++) | |
1665 | { | |
1666 | rtx *loc = recog_data.operand_loc[i]; | |
1667 | rtx op = *loc; | |
1668 | ||
f8cfc6aa | 1669 | if (REG_P (op) |
3ada20ee RH |
1670 | && REGNO (op) == ORIGINAL_REGNO (op) |
1671 | && (recog_data.operand_type[i] == OP_IN | |
1672 | || recog_data.operand_type[i] == OP_INOUT)) | |
a96caf80 | 1673 | scan_rtx (insn, loc, NO_REGS, mark_all_read, OP_IN); |
3ada20ee RH |
1674 | } |
1675 | ||
541f7d56 BS |
1676 | /* Step 3: Append to chains for reads inside operands. */ |
1677 | for (i = 0; i < n_ops + recog_data.n_dups; i++) | |
1678 | { | |
1679 | int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; | |
1680 | rtx *loc = (i < n_ops | |
1681 | ? recog_data.operand_loc[opn] | |
1682 | : recog_data.dup_loc[i - n_ops]); | |
5efe5dec | 1683 | enum reg_class cl = alternative_class (op_alt, opn); |
541f7d56 BS |
1684 | enum op_type type = recog_data.operand_type[opn]; |
1685 | ||
1686 | /* Don't scan match_operand here, since we've no reg class | |
1687 | information to pass down. Any operands that we could | |
1688 | substitute in will be represented elsewhere. */ | |
d435810e BS |
1689 | if (recog_data.constraints[opn][0] == '\0' |
1690 | || untracked_operands & (1 << opn)) | |
541f7d56 | 1691 | continue; |
7b82b5da | 1692 | |
1f234b83 BS |
1693 | if (insn_info) |
1694 | cur_operand = i == opn ? insn_info->op_info + i : NULL; | |
29d70a0f | 1695 | if (op_alt[opn].is_address) |
86fc3d06 UW |
1696 | scan_rtx_address (insn, loc, cl, mark_read, |
1697 | VOIDmode, ADDR_SPACE_GENERIC); | |
541f7d56 | 1698 | else |
6bda9bdf | 1699 | scan_rtx (insn, loc, cl, mark_read, type); |
541f7d56 | 1700 | } |
1f234b83 | 1701 | cur_operand = NULL; |
7b82b5da | 1702 | |
cb110f3d AM |
1703 | /* Step 3B: Record updates for regs in REG_INC notes, and |
1704 | source regs in REG_FRAME_RELATED_EXPR notes. */ | |
541f7d56 | 1705 | for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) |
cb110f3d AM |
1706 | if (REG_NOTE_KIND (note) == REG_INC |
1707 | || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR) | |
1708 | scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read, | |
6bda9bdf | 1709 | OP_INOUT); |
cb110f3d | 1710 | |
c664546f JL |
1711 | /* Step 4: Close chains for registers that die here, unless |
1712 | the register is mentioned in a REG_UNUSED note. In that | |
1713 | case we keep the chain open until step #7 below to ensure | |
1714 | it conflicts with other output operands of this insn. | |
1715 | See PR 52573. Arguably the insn should not have both | |
1716 | notes; it has proven difficult to fix that without | |
1717 | other undesirable side effects. */ | |
cb110f3d | 1718 | for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) |
c664546f JL |
1719 | if (REG_NOTE_KIND (note) == REG_DEAD |
1720 | && !find_regno_note (insn, REG_UNUSED, REGNO (XEXP (note, 0)))) | |
a96caf80 BS |
1721 | { |
1722 | remove_from_hard_reg_set (&live_hard_regs, | |
1723 | GET_MODE (XEXP (note, 0)), | |
1724 | REGNO (XEXP (note, 0))); | |
1725 | scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, | |
1726 | OP_IN); | |
1727 | } | |
1a43c33f | 1728 | |
541f7d56 BS |
1729 | /* Step 4B: If this is a call, any chain live at this point |
1730 | requires a caller-saved reg. */ | |
4b4bf941 | 1731 | if (CALL_P (insn)) |
541f7d56 | 1732 | { |
9d324dde | 1733 | struct du_head *p; |
541f7d56 | 1734 | for (p = open_chains; p; p = p->next_chain) |
fe08a886 | 1735 | p->need_caller_save_reg = 1; |
541f7d56 | 1736 | } |
7b82b5da | 1737 | |
541f7d56 BS |
1738 | /* Step 5: Close open chains that overlap writes. Similar to |
1739 | step 2, we hide in-out operands, since we do not want to | |
a96caf80 BS |
1740 | close these chains. We also hide earlyclobber operands, |
1741 | since we've opened chains for them in step 1, and earlier | |
1742 | chains they would overlap with must have been closed at | |
1743 | the previous insn at the latest, as such operands cannot | |
1744 | possibly overlap with any input operands. */ | |
7b82b5da | 1745 | |
d435810e BS |
1746 | hide_operands (n_ops, old_operands, old_dups, untracked_operands, |
1747 | true); | |
6bda9bdf BS |
1748 | scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN); |
1749 | restore_operands (insn, n_ops, old_operands, old_dups); | |
7b82b5da | 1750 | |
a96caf80 BS |
1751 | /* Step 6a: Mark hard registers that are set in this insn, |
1752 | outside an operand, as live. */ | |
d435810e BS |
1753 | hide_operands (n_ops, old_operands, old_dups, untracked_operands, |
1754 | false); | |
a96caf80 BS |
1755 | note_stores (PATTERN (insn), note_sets_clobbers, &set_code); |
1756 | restore_operands (insn, n_ops, old_operands, old_dups); | |
7b82b5da | 1757 | |
a96caf80 | 1758 | /* Step 6b: Begin new chains for writes inside operands. */ |
1f234b83 | 1759 | record_out_operands (insn, false, insn_info); |
a96caf80 BS |
1760 | |
1761 | /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR | |
cb110f3d AM |
1762 | notes for update. */ |
1763 | for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) | |
1764 | if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR) | |
1765 | scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access, | |
6bda9bdf | 1766 | OP_INOUT); |
cb110f3d | 1767 | |
541f7d56 BS |
1768 | /* Step 7: Close chains for registers that were never |
1769 | really used here. */ | |
1770 | for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) | |
1771 | if (REG_NOTE_KIND (note) == REG_UNUSED) | |
a96caf80 BS |
1772 | { |
1773 | remove_from_hard_reg_set (&live_hard_regs, | |
1774 | GET_MODE (XEXP (note, 0)), | |
1775 | REGNO (XEXP (note, 0))); | |
1776 | scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, | |
1777 | OP_IN); | |
1778 | } | |
541f7d56 | 1779 | } |
b5b8b0ac AO |
1780 | else if (DEBUG_INSN_P (insn) |
1781 | && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn))) | |
1782 | { | |
1783 | scan_rtx (insn, &INSN_VAR_LOCATION_LOC (insn), | |
6bda9bdf | 1784 | ALL_REGS, mark_read, OP_IN); |
b5b8b0ac | 1785 | } |
a813c111 | 1786 | if (insn == BB_END (bb)) |
541f7d56 BS |
1787 | break; |
1788 | } | |
7b82b5da | 1789 | |
a96caf80 | 1790 | if (fail_current_block) |
8ffa0351 | 1791 | return false; |
a96caf80 | 1792 | |
8ffa0351 | 1793 | return true; |
541f7d56 | 1794 | } |
ef330312 | 1795 | \f |
1f234b83 BS |
1796 | /* Initialize the register renamer. If INSN_INFO is true, ensure that |
1797 | insn_rr is nonnull. */ | |
1798 | void | |
1799 | regrename_init (bool insn_info) | |
1800 | { | |
1801 | gcc_obstack_init (&rename_obstack); | |
9771b263 | 1802 | insn_rr.create (0); |
1f234b83 | 1803 | if (insn_info) |
9771b263 | 1804 | insn_rr.safe_grow_cleared (get_max_uid ()); |
1f234b83 BS |
1805 | } |
1806 | ||
1807 | /* Free all global data used by the register renamer. */ | |
1808 | void | |
1809 | regrename_finish (void) | |
1810 | { | |
9771b263 | 1811 | insn_rr.release (); |
1f234b83 BS |
1812 | free_chain_data (); |
1813 | obstack_free (&rename_obstack, NULL); | |
1814 | } | |
1815 | ||
f24acbef BS |
1816 | /* Perform register renaming on the current function. */ |
1817 | ||
1818 | static unsigned int | |
1819 | regrename_optimize (void) | |
1820 | { | |
f24acbef BS |
1821 | df_set_flags (DF_LR_RUN_DCE); |
1822 | df_note_add_problem (); | |
1823 | df_analyze (); | |
1824 | df_set_flags (DF_DEFER_INSN_RESCAN); | |
1825 | ||
1f234b83 | 1826 | regrename_init (false); |
f24acbef | 1827 | |
1f234b83 | 1828 | regrename_analyze (NULL); |
f24acbef | 1829 | |
8ffa0351 | 1830 | rename_chains (); |
f24acbef | 1831 | |
1f234b83 | 1832 | regrename_finish (); |
f24acbef | 1833 | |
f24acbef BS |
1834 | return 0; |
1835 | } | |
1836 | \f | |
27a4cd48 DM |
1837 | namespace { |
1838 | ||
1839 | const pass_data pass_data_regrename = | |
ef330312 | 1840 | { |
27a4cd48 DM |
1841 | RTL_PASS, /* type */ |
1842 | "rnreg", /* name */ | |
1843 | OPTGROUP_NONE, /* optinfo_flags */ | |
27a4cd48 DM |
1844 | TV_RENAME_REGISTERS, /* tv_id */ |
1845 | 0, /* properties_required */ | |
1846 | 0, /* properties_provided */ | |
1847 | 0, /* properties_destroyed */ | |
1848 | 0, /* todo_flags_start */ | |
3bea341f | 1849 | TODO_df_finish, /* todo_flags_finish */ |
6fb5fa3c | 1850 | }; |
27a4cd48 DM |
1851 | |
1852 | class pass_regrename : public rtl_opt_pass | |
1853 | { | |
1854 | public: | |
c3284718 RS |
1855 | pass_regrename (gcc::context *ctxt) |
1856 | : rtl_opt_pass (pass_data_regrename, ctxt) | |
27a4cd48 DM |
1857 | {} |
1858 | ||
1859 | /* opt_pass methods: */ | |
1a3d085c TS |
1860 | virtual bool gate (function *) |
1861 | { | |
1862 | return (optimize > 0 && (flag_rename_registers)); | |
1863 | } | |
1864 | ||
be55bfe6 | 1865 | virtual unsigned int execute (function *) { return regrename_optimize (); } |
27a4cd48 DM |
1866 | |
1867 | }; // class pass_regrename | |
1868 | ||
1869 | } // anon namespace | |
1870 | ||
1871 | rtl_opt_pass * | |
1872 | make_pass_regrename (gcc::context *ctxt) | |
1873 | { | |
1874 | return new pass_regrename (ctxt); | |
1875 | } |