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