Daily bump.
[official-gcc.git] / gcc / regrename.c
blobb8a9ca36f225cc9f74ea7c26964cdedfb1ab5948
1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
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"
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:
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.
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.
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.
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.
63 5. If a renaming register has been found, it is substituted in the chain.
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.
68 DEBUG_INSNs are treated specially, in particular registers occurring inside
69 them are treated as requiring ALL_REGS as a class. */
71 #if HOST_BITS_PER_WIDE_INT <= MAX_RECOG_OPERANDS
72 #error "Use a different bitmap implementation for untracked_operands."
73 #endif
75 enum scan_actions
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
88 static const char * const scan_actions_name[] =
90 "terminate_write",
91 "terminate_dead",
92 "mark_all_read",
93 "mark_read",
94 "mark_write",
95 "mark_access"
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;
103 static struct obstack rename_obstack;
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;
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);
113 /* The id to be given to the next opened chain. */
114 static unsigned current_id;
116 /* A mapping of unique id numbers to chains. */
117 static vec<du_head_p> id_to_chain;
119 /* List of currently open chains. */
120 static class du_head *open_chains;
122 /* Bitmap of open chains. The bits set always match the list found in
123 open_chains. */
124 static bitmap_head open_chains_set;
126 /* Record the registers being tracked in open_chains. */
127 static HARD_REG_SET live_in_chains;
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;
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;
138 /* Set while scanning RTL if a register dies. Used to tie chains. */
139 static class du_head *terminated_this_insn;
141 /* Return the chain corresponding to id number ID. Take into account that
142 chains may have been merged. */
143 du_head_p
144 regrename_chain_from_id (unsigned int id)
146 du_head_p first_chain = id_to_chain[id];
147 du_head_p chain = first_chain;
148 while (chain->id != id)
150 id = chain->id;
151 chain = id_to_chain[id];
153 first_chain->id = id;
154 return chain;
157 /* Dump all def/use chains, starting at id FROM. */
159 static void
160 dump_def_use_chain (int from)
162 du_head_p head;
163 int i;
164 FOR_EACH_VEC_ELT_FROM (id_to_chain, i, head, from)
166 struct du_chain *this_du = head->first;
168 fprintf (dump_file, "Register %s (%d):",
169 reg_names[head->regno], head->nregs);
170 while (this_du)
172 fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
173 reg_class_names[this_du->cl]);
174 this_du = this_du->next_use;
176 fprintf (dump_file, "\n");
177 head = head->next_chain;
181 static void
182 free_chain_data (void)
184 int i;
185 du_head_p ptr;
186 for (i = 0; id_to_chain.iterate (i, &ptr); i++)
187 bitmap_clear (&ptr->conflicts);
189 id_to_chain.release ();
192 /* Walk all chains starting with CHAINS and record that they conflict with
193 another chain whose id is ID. */
195 static void
196 mark_conflict (class du_head *chains, unsigned id)
198 while (chains)
200 bitmap_set_bit (&chains->conflicts, id);
201 chains = chains->next_chain;
205 /* Examine cur_operand, and if it is nonnull, record information about the
206 use THIS_DU which is part of the chain HEAD. */
208 static void
209 record_operand_use (class du_head *head, struct du_chain *this_du)
211 if (cur_operand == NULL || cur_operand->failed)
212 return;
213 if (head->cannot_rename)
215 cur_operand->failed = true;
216 return;
218 gcc_assert (cur_operand->n_chains < MAX_REGS_PER_ADDRESS);
219 cur_operand->heads[cur_operand->n_chains] = head;
220 cur_operand->chains[cur_operand->n_chains++] = this_du;
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. */
227 static du_head_p
228 create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc,
229 rtx_insn *insn, enum reg_class cl)
231 class du_head *head = XOBNEW (&rename_obstack, class du_head);
232 struct du_chain *this_du;
233 int nregs;
235 memset ((void *)head, 0, sizeof *head);
236 head->next_chain = open_chains;
237 head->regno = this_regno;
238 head->nregs = this_nregs;
240 id_to_chain.safe_push (head);
241 head->id = current_id++;
243 bitmap_initialize (&head->conflicts, &bitmap_default_obstack);
244 bitmap_copy (&head->conflicts, &open_chains_set);
245 mark_conflict (open_chains, head->id);
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 nregs = head->nregs;
251 while (nregs-- > 0)
253 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
254 CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
257 head->hard_conflicts = live_hard_regs;
258 bitmap_set_bit (&open_chains_set, head->id);
260 open_chains = head;
262 if (dump_file)
264 fprintf (dump_file, "Creating chain %s (%d)",
265 reg_names[head->regno], head->id);
266 if (insn != NULL_RTX)
267 fprintf (dump_file, " at insn %d", INSN_UID (insn));
268 fprintf (dump_file, "\n");
271 if (insn == NULL_RTX)
273 head->first = head->last = NULL;
274 return head;
277 this_du = XOBNEW (&rename_obstack, struct du_chain);
278 head->first = head->last = this_du;
280 this_du->next_use = 0;
281 this_du->loc = loc;
282 this_du->insn = insn;
283 this_du->cl = cl;
284 record_operand_use (head, this_du);
285 return head;
288 /* For a def-use chain HEAD, find which registers overlap its lifetime and
289 set the corresponding bits in *PSET. */
291 static void
292 merge_overlapping_regs (HARD_REG_SET *pset, class du_head *head)
294 bitmap_iterator bi;
295 unsigned i;
296 *pset |= head->hard_conflicts;
297 EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi)
299 du_head_p other = regrename_chain_from_id (i);
300 unsigned j = other->nregs;
301 gcc_assert (other != head);
302 while (j-- > 0)
303 SET_HARD_REG_BIT (*pset, other->regno + j);
307 /* Return true if (reg:MODE REGNO) would be clobbered by a call covered
308 by THIS_HEAD. */
310 static bool
311 call_clobbered_in_chain_p (du_head *this_head, machine_mode mode,
312 unsigned int regno)
314 return call_clobbered_in_region_p (this_head->call_abis,
315 this_head->call_clobber_mask,
316 mode, regno);
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. */
323 static bool
324 check_new_reg_p (int reg ATTRIBUTE_UNUSED, int new_reg,
325 class du_head *this_head, HARD_REG_SET this_unavailable)
327 machine_mode mode = GET_MODE (*this_head->first->loc);
328 int nregs = hard_regno_nregs (new_reg, mode);
329 int i;
330 struct du_chain *tmp;
332 for (i = nregs - 1; i >= 0; --i)
333 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
334 || fixed_regs[new_reg + i]
335 || global_regs[new_reg + i]
336 /* Can't use regs which aren't saved by the prologue. */
337 || (! df_regs_ever_live_p (new_reg + i)
338 && ! crtl->abi->clobbers_full_reg_p (new_reg + i))
339 #ifdef LEAF_REGISTERS
340 /* We can't use a non-leaf register if we're in a
341 leaf function. */
342 || (crtl->is_leaf
343 && !LEAF_REGISTERS[new_reg + i])
344 #endif
345 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i))
346 return false;
348 /* See whether it accepts all modes that occur in
349 definition and uses. */
350 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
352 /* Completely ignore DEBUG_INSNs, otherwise we can get
353 -fcompare-debug failures. */
354 if (DEBUG_INSN_P (tmp->insn))
355 continue;
357 if (!targetm.hard_regno_mode_ok (new_reg, GET_MODE (*tmp->loc))
358 || call_clobbered_in_chain_p (this_head, GET_MODE (*tmp->loc),
359 new_reg))
360 return false;
363 return true;
366 /* For the chain THIS_HEAD, compute and return the best register to
367 rename to. SUPER_CLASS is the superunion of register classes in
368 the chain. UNAVAILABLE is a set of registers that cannot be used.
369 OLD_REG is the register currently used for the chain. BEST_RENAME
370 controls whether the register chosen must be better than the
371 current one or just respect the given constraint. */
374 find_rename_reg (du_head_p this_head, enum reg_class super_class,
375 HARD_REG_SET *unavailable, int old_reg, bool best_rename)
377 bool has_preferred_class;
378 enum reg_class preferred_class;
379 int pass;
380 int best_new_reg = old_reg;
382 /* Mark registers that overlap this chain's lifetime as unavailable. */
383 merge_overlapping_regs (unavailable, this_head);
385 /* Compute preferred rename class of super union of all the classes
386 in the chain. */
387 preferred_class
388 = (enum reg_class) targetm.preferred_rename_class (super_class);
390 /* Pick and check the register from the tied chain iff the tied chain
391 is not renamed. */
392 if (this_head->tied_chain && !this_head->tied_chain->renamed
393 && check_new_reg_p (old_reg, this_head->tied_chain->regno,
394 this_head, *unavailable))
395 return this_head->tied_chain->regno;
397 /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
398 over registers that belong to PREFERRED_CLASS and try to find the
399 best register within the class. If that failed, we iterate in
400 the second pass over registers that don't belong to the class.
401 If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
402 ascending order without any preference. */
403 has_preferred_class = (preferred_class != NO_REGS);
404 for (pass = (has_preferred_class ? 0 : 1); pass < 2; pass++)
406 int new_reg;
407 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
409 if (has_preferred_class
410 && (pass == 0)
411 != TEST_HARD_REG_BIT (reg_class_contents[preferred_class],
412 new_reg))
413 continue;
415 if (!check_new_reg_p (old_reg, new_reg, this_head, *unavailable))
416 continue;
418 if (!best_rename)
419 return new_reg;
421 /* In the first pass, we force the renaming of registers that
422 don't belong to PREFERRED_CLASS to registers that do, even
423 though the latters were used not very long ago. */
424 if ((pass == 0
425 && !TEST_HARD_REG_BIT (reg_class_contents[preferred_class],
426 best_new_reg))
427 || tick[best_new_reg] > tick[new_reg])
428 best_new_reg = new_reg;
430 if (pass == 0 && best_new_reg != old_reg)
431 break;
433 return best_new_reg;
436 /* Iterate over elements in the chain HEAD in order to:
437 1. Count number of uses, storing it in *PN_USES.
438 2. Narrow the set of registers we can use for renaming, adding
439 unavailable registers to *PUNAVAILABLE, which must be
440 initialized by the caller.
441 3. Compute the superunion of register classes in this chain
442 and return it. */
443 reg_class
444 regrename_find_superclass (du_head_p head, int *pn_uses,
445 HARD_REG_SET *punavailable)
447 int n_uses = 0;
448 reg_class super_class = NO_REGS;
449 for (du_chain *tmp = head->first; tmp; tmp = tmp->next_use)
451 if (DEBUG_INSN_P (tmp->insn))
452 continue;
453 n_uses++;
454 *punavailable |= ~reg_class_contents[tmp->cl];
455 super_class
456 = reg_class_superunion[(int) super_class][(int) tmp->cl];
458 *pn_uses = n_uses;
459 return super_class;
462 /* Perform register renaming on the current function. */
463 static void
464 rename_chains (void)
466 HARD_REG_SET unavailable;
467 du_head_p this_head;
468 int i;
470 memset (tick, 0, sizeof tick);
472 CLEAR_HARD_REG_SET (unavailable);
473 /* Don't clobber traceback for noreturn functions. */
474 if (frame_pointer_needed)
476 add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
477 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER)
478 add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
481 FOR_EACH_VEC_ELT (id_to_chain, i, this_head)
483 int best_new_reg;
484 int n_uses;
485 HARD_REG_SET this_unavailable;
486 int reg = this_head->regno;
488 if (this_head->cannot_rename)
489 continue;
491 if (fixed_regs[reg] || global_regs[reg]
492 || (!HARD_FRAME_POINTER_IS_FRAME_POINTER && frame_pointer_needed
493 && reg == HARD_FRAME_POINTER_REGNUM)
494 || (HARD_FRAME_POINTER_IS_FRAME_POINTER && frame_pointer_needed
495 && reg == FRAME_POINTER_REGNUM))
496 continue;
498 this_unavailable = unavailable;
500 reg_class super_class = regrename_find_superclass (this_head, &n_uses,
501 &this_unavailable);
502 if (n_uses < 2)
503 continue;
505 best_new_reg = find_rename_reg (this_head, super_class,
506 &this_unavailable, reg, true);
508 if (dump_file)
510 fprintf (dump_file, "Register %s in insn %d",
511 reg_names[reg], INSN_UID (this_head->first->insn));
512 if (this_head->call_abis)
513 fprintf (dump_file, " crosses a call");
516 if (best_new_reg == reg)
518 tick[reg] = ++this_tick;
519 if (dump_file)
520 fprintf (dump_file, "; no available better choice\n");
521 continue;
524 if (regrename_do_replace (this_head, best_new_reg))
526 if (dump_file)
527 fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
528 tick[best_new_reg] = ++this_tick;
529 df_set_regs_ever_live (best_new_reg, true);
531 else
533 if (dump_file)
534 fprintf (dump_file, ", renaming as %s failed\n",
535 reg_names[best_new_reg]);
536 tick[reg] = ++this_tick;
541 /* A structure to record information for each hard register at the start of
542 a basic block. */
543 struct incoming_reg_info {
544 /* Holds the number of registers used in the chain that gave us information
545 about this register. Zero means no information known yet, while a
546 negative value is used for something that is part of, but not the first
547 register in a multi-register value. */
548 int nregs;
549 /* Set to true if we have accesses that conflict in the number of registers
550 used. */
551 bool unusable;
554 /* A structure recording information about each basic block. It is saved
555 and restored around basic block boundaries.
556 A pointer to such a structure is stored in each basic block's aux field
557 during regrename_analyze, except for blocks we know can't be optimized
558 (such as entry and exit blocks). */
559 class bb_rename_info
561 public:
562 /* The basic block corresponding to this structure. */
563 basic_block bb;
564 /* Copies of the global information. */
565 bitmap_head open_chains_set;
566 bitmap_head incoming_open_chains_set;
567 struct incoming_reg_info incoming[FIRST_PSEUDO_REGISTER];
570 /* Initialize a rename_info structure P for basic block BB, which starts a new
571 scan. */
572 static void
573 init_rename_info (class bb_rename_info *p, basic_block bb)
575 int i;
576 df_ref def;
577 HARD_REG_SET start_chains_set;
579 p->bb = bb;
580 bitmap_initialize (&p->open_chains_set, &bitmap_default_obstack);
581 bitmap_initialize (&p->incoming_open_chains_set, &bitmap_default_obstack);
583 open_chains = NULL;
584 bitmap_clear (&open_chains_set);
586 CLEAR_HARD_REG_SET (live_in_chains);
587 REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb));
588 FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
589 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
590 SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def));
592 /* Open chains based on information from (at least one) predecessor
593 block. This gives us a chance later on to combine chains across
594 basic block boundaries. Inconsistencies (in access sizes) will
595 be caught normally and dealt with conservatively by disabling the
596 chain for renaming, and there is no risk of losing optimization
597 opportunities by opening chains either: if we did not open the
598 chains, we'd have to track the live register as a hard reg, and
599 we'd be unable to rename it in any case. */
600 CLEAR_HARD_REG_SET (start_chains_set);
601 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
603 struct incoming_reg_info *iri = p->incoming + i;
604 if (iri->nregs > 0 && !iri->unusable
605 && range_in_hard_reg_set_p (live_hard_regs, i, iri->nregs))
607 SET_HARD_REG_BIT (start_chains_set, i);
608 remove_range_from_hard_reg_set (&live_hard_regs, i, iri->nregs);
611 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
613 struct incoming_reg_info *iri = p->incoming + i;
614 if (TEST_HARD_REG_BIT (start_chains_set, i))
616 du_head_p chain;
617 if (dump_file)
618 fprintf (dump_file, "opening incoming chain\n");
619 chain = create_new_chain (i, iri->nregs, NULL, NULL, NO_REGS);
620 bitmap_set_bit (&p->incoming_open_chains_set, chain->id);
625 /* Record in RI that the block corresponding to it has an incoming
626 live value, described by CHAIN. */
627 static void
628 set_incoming_from_chain (class bb_rename_info *ri, du_head_p chain)
630 int i;
631 int incoming_nregs = ri->incoming[chain->regno].nregs;
632 int nregs;
634 /* If we've recorded the same information before, everything is fine. */
635 if (incoming_nregs == chain->nregs)
637 if (dump_file)
638 fprintf (dump_file, "reg %d/%d already recorded\n",
639 chain->regno, chain->nregs);
640 return;
643 /* If we have no information for any of the involved registers, update
644 the incoming array. */
645 nregs = chain->nregs;
646 while (nregs-- > 0)
647 if (ri->incoming[chain->regno + nregs].nregs != 0
648 || ri->incoming[chain->regno + nregs].unusable)
649 break;
650 if (nregs < 0)
652 nregs = chain->nregs;
653 ri->incoming[chain->regno].nregs = nregs;
654 while (nregs-- > 1)
655 ri->incoming[chain->regno + nregs].nregs = -nregs;
656 if (dump_file)
657 fprintf (dump_file, "recorded reg %d/%d\n",
658 chain->regno, chain->nregs);
659 return;
662 /* There must be some kind of conflict. Prevent both the old and
663 new ranges from being used. */
664 if (incoming_nregs < 0)
665 ri->incoming[chain->regno + incoming_nregs].unusable = true;
666 for (i = 0; i < chain->nregs; i++)
667 ri->incoming[chain->regno + i].unusable = true;
670 /* Merge the two chains C1 and C2 so that all conflict information is
671 recorded and C1, and the id of C2 is changed to that of C1. */
672 static void
673 merge_chains (du_head_p c1, du_head_p c2)
675 if (c1 == c2)
676 return;
678 if (c2->first != NULL)
680 if (c1->first == NULL)
681 c1->first = c2->first;
682 else
683 c1->last->next_use = c2->first;
684 c1->last = c2->last;
687 c2->first = c2->last = NULL;
688 c2->id = c1->id;
690 c1->hard_conflicts |= c2->hard_conflicts;
691 bitmap_ior_into (&c1->conflicts, &c2->conflicts);
693 c1->call_clobber_mask |= c2->call_clobber_mask;
694 c1->call_abis |= c2->call_abis;
695 c1->cannot_rename |= c2->cannot_rename;
698 /* Analyze the current function and build chains for renaming.
699 If INCLUDE_ALL_BLOCKS_P is set to true, process all blocks,
700 ignoring BB_DISABLE_SCHEDULE. The default value is true. */
702 void
703 regrename_analyze (bitmap bb_mask, bool include_all_block_p)
705 class bb_rename_info *rename_info;
706 int i;
707 basic_block bb;
708 int n_bbs;
709 int *inverse_postorder;
711 inverse_postorder = XNEWVEC (int, last_basic_block_for_fn (cfun));
712 n_bbs = pre_and_rev_post_order_compute (NULL, inverse_postorder, false);
714 /* Gather some information about the blocks in this function. */
715 rename_info = XCNEWVEC (class bb_rename_info, n_basic_blocks_for_fn (cfun));
716 i = 0;
717 FOR_EACH_BB_FN (bb, cfun)
719 class bb_rename_info *ri = rename_info + i;
720 ri->bb = bb;
721 if (bb_mask != NULL && !bitmap_bit_p (bb_mask, bb->index))
722 bb->aux = NULL;
723 else
724 bb->aux = ri;
725 i++;
728 current_id = 0;
729 id_to_chain.create (0);
730 bitmap_initialize (&open_chains_set, &bitmap_default_obstack);
732 /* The order in which we visit blocks ensures that whenever
733 possible, we only process a block after at least one of its
734 predecessors, which provides a "seeding" effect to make the logic
735 in set_incoming_from_chain and init_rename_info useful. */
737 for (i = 0; i < n_bbs; i++)
739 basic_block bb1 = BASIC_BLOCK_FOR_FN (cfun, inverse_postorder[i]);
740 class bb_rename_info *this_info;
741 bool success;
742 edge e;
743 edge_iterator ei;
744 int old_length = id_to_chain.length ();
746 this_info = (class bb_rename_info *) bb1->aux;
747 if (this_info == NULL)
748 continue;
750 if (dump_file)
751 fprintf (dump_file, "\nprocessing block %d:\n", bb1->index);
753 if (!include_all_block_p && (bb1->flags & BB_DISABLE_SCHEDULE) != 0)
755 if (dump_file)
756 fprintf (dump_file, "avoid disrupting the sms schedule of bb %d\n",
757 bb1->index);
758 continue;
761 init_rename_info (this_info, bb1);
763 success = build_def_use (bb1);
764 if (!success)
766 if (dump_file)
767 fprintf (dump_file, "failed\n");
768 bb1->aux = NULL;
769 id_to_chain.truncate (old_length);
770 current_id = old_length;
771 bitmap_clear (&this_info->incoming_open_chains_set);
772 open_chains = NULL;
773 if (insn_rr.exists ())
775 rtx_insn *insn;
776 FOR_BB_INSNS (bb1, insn)
778 insn_rr_info *p = &insn_rr[INSN_UID (insn)];
779 p->op_info = NULL;
782 continue;
785 if (dump_file)
786 dump_def_use_chain (old_length);
787 bitmap_copy (&this_info->open_chains_set, &open_chains_set);
789 /* Add successor blocks to the worklist if necessary, and record
790 data about our own open chains at the end of this block, which
791 will be used to pre-open chains when processing the successors. */
792 FOR_EACH_EDGE (e, ei, bb1->succs)
794 class bb_rename_info *dest_ri;
795 class du_head *chain;
797 if (dump_file)
798 fprintf (dump_file, "successor block %d\n", e->dest->index);
800 if (e->flags & (EDGE_EH | EDGE_ABNORMAL))
801 continue;
802 dest_ri = (class bb_rename_info *)e->dest->aux;
803 if (dest_ri == NULL)
804 continue;
805 for (chain = open_chains; chain; chain = chain->next_chain)
806 set_incoming_from_chain (dest_ri, chain);
810 free (inverse_postorder);
812 /* Now, combine the chains data we have gathered across basic block
813 boundaries.
815 For every basic block, there may be chains open at the start, or at the
816 end. Rather than exclude them from renaming, we look for open chains
817 with matching registers at the other side of the CFG edge.
819 For a given chain using register R, open at the start of block B, we
820 must find an open chain using R on the other side of every edge leading
821 to B, if the register is live across this edge. In the code below,
822 N_PREDS_USED counts the number of edges where the register is live, and
823 N_PREDS_JOINED counts those where we found an appropriate chain for
824 joining.
826 We perform the analysis for both incoming and outgoing edges, but we
827 only need to merge once (in the second part, after verifying outgoing
828 edges). */
829 FOR_EACH_BB_FN (bb, cfun)
831 class bb_rename_info *bb_ri = (class bb_rename_info *) bb->aux;
832 unsigned j;
833 bitmap_iterator bi;
835 if (bb_ri == NULL)
836 continue;
838 if (dump_file)
839 fprintf (dump_file, "processing bb %d in edges\n", bb->index);
841 EXECUTE_IF_SET_IN_BITMAP (&bb_ri->incoming_open_chains_set, 0, j, bi)
843 edge e;
844 edge_iterator ei;
845 class du_head *chain = regrename_chain_from_id (j);
846 int n_preds_used = 0, n_preds_joined = 0;
848 FOR_EACH_EDGE (e, ei, bb->preds)
850 class bb_rename_info *src_ri;
851 unsigned k;
852 bitmap_iterator bi2;
853 HARD_REG_SET live;
854 bool success = false;
856 REG_SET_TO_HARD_REG_SET (live, df_get_live_out (e->src));
857 if (!range_overlaps_hard_reg_set_p (live, chain->regno,
858 chain->nregs))
859 continue;
860 n_preds_used++;
862 if (e->flags & (EDGE_EH | EDGE_ABNORMAL))
863 continue;
865 src_ri = (class bb_rename_info *)e->src->aux;
866 if (src_ri == NULL)
867 continue;
869 EXECUTE_IF_SET_IN_BITMAP (&src_ri->open_chains_set,
870 0, k, bi2)
872 class du_head *outgoing_chain = regrename_chain_from_id (k);
874 if (outgoing_chain->regno == chain->regno
875 && outgoing_chain->nregs == chain->nregs)
877 n_preds_joined++;
878 success = true;
879 break;
882 if (!success && dump_file)
883 fprintf (dump_file, "failure to match with pred block %d\n",
884 e->src->index);
886 if (n_preds_joined < n_preds_used)
888 if (dump_file)
889 fprintf (dump_file, "cannot rename chain %d\n", j);
890 chain->cannot_rename = 1;
894 FOR_EACH_BB_FN (bb, cfun)
896 class bb_rename_info *bb_ri = (class bb_rename_info *) bb->aux;
897 unsigned j;
898 bitmap_iterator bi;
900 if (bb_ri == NULL)
901 continue;
903 if (dump_file)
904 fprintf (dump_file, "processing bb %d out edges\n", bb->index);
906 EXECUTE_IF_SET_IN_BITMAP (&bb_ri->open_chains_set, 0, j, bi)
908 edge e;
909 edge_iterator ei;
910 class du_head *chain = regrename_chain_from_id (j);
911 int n_succs_used = 0, n_succs_joined = 0;
913 FOR_EACH_EDGE (e, ei, bb->succs)
915 bool printed = false;
916 class bb_rename_info *dest_ri;
917 unsigned k;
918 bitmap_iterator bi2;
919 HARD_REG_SET live;
921 REG_SET_TO_HARD_REG_SET (live, df_get_live_in (e->dest));
922 if (!range_overlaps_hard_reg_set_p (live, chain->regno,
923 chain->nregs))
924 continue;
926 n_succs_used++;
928 dest_ri = (class bb_rename_info *)e->dest->aux;
929 if (dest_ri == NULL)
930 continue;
932 EXECUTE_IF_SET_IN_BITMAP (&dest_ri->incoming_open_chains_set,
933 0, k, bi2)
935 class du_head *incoming_chain = regrename_chain_from_id (k);
937 if (incoming_chain->regno == chain->regno
938 && incoming_chain->nregs == chain->nregs)
940 if (dump_file)
942 if (!printed)
943 fprintf (dump_file,
944 "merging blocks for edge %d -> %d\n",
945 e->src->index, e->dest->index);
946 printed = true;
947 fprintf (dump_file,
948 " merging chains %d (->%d) and %d (->%d) [%s]\n",
949 k, incoming_chain->id, j, chain->id,
950 reg_names[incoming_chain->regno]);
953 merge_chains (chain, incoming_chain);
954 n_succs_joined++;
955 break;
959 if (n_succs_joined < n_succs_used)
961 if (dump_file)
962 fprintf (dump_file, "cannot rename chain %d\n",
964 chain->cannot_rename = 1;
969 free (rename_info);
971 FOR_EACH_BB_FN (bb, cfun)
972 bb->aux = NULL;
975 /* Attempt to replace all uses of the register in the chain beginning with
976 HEAD with REG. Returns true on success and false if the replacement is
977 rejected because the insns would not validate. The latter can happen
978 e.g. if a match_parallel predicate enforces restrictions on register
979 numbering in its subpatterns. */
981 bool
982 regrename_do_replace (class du_head *head, int reg)
984 struct du_chain *chain;
985 unsigned int base_regno = head->regno;
986 machine_mode mode;
987 rtx last_reg = NULL_RTX, last_repl = NULL_RTX;
989 for (chain = head->first; chain; chain = chain->next_use)
991 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
992 class reg_attrs *attr = REG_ATTRS (*chain->loc);
993 int reg_ptr = REG_POINTER (*chain->loc);
995 if (DEBUG_INSN_P (chain->insn) && REGNO (*chain->loc) != base_regno)
996 validate_change (chain->insn, &(INSN_VAR_LOCATION_LOC (chain->insn)),
997 gen_rtx_UNKNOWN_VAR_LOC (), true);
998 else
1000 if (*chain->loc != last_reg)
1002 last_repl = gen_raw_REG (GET_MODE (*chain->loc), reg);
1003 if (regno >= FIRST_PSEUDO_REGISTER)
1004 ORIGINAL_REGNO (last_repl) = regno;
1005 REG_ATTRS (last_repl) = attr;
1006 REG_POINTER (last_repl) = reg_ptr;
1007 last_reg = *chain->loc;
1009 validate_change (chain->insn, chain->loc, last_repl, true);
1013 if (!apply_change_group ())
1014 return false;
1016 mode = GET_MODE (*head->first->loc);
1017 head->renamed = 1;
1018 head->regno = reg;
1019 head->nregs = hard_regno_nregs (reg, mode);
1020 return true;
1024 /* True if we found a register with a size mismatch, which means that we
1025 can't track its lifetime accurately. If so, we abort the current block
1026 without renaming. */
1027 static bool fail_current_block;
1029 /* Return true if OP is a reg for which all bits are set in PSET, false
1030 if all bits are clear.
1031 In other cases, set fail_current_block and return false. */
1033 static bool
1034 verify_reg_in_set (rtx op, HARD_REG_SET *pset)
1036 unsigned regno, nregs;
1037 bool all_live, all_dead;
1038 if (!REG_P (op))
1039 return false;
1041 regno = REGNO (op);
1042 nregs = REG_NREGS (op);
1043 all_live = all_dead = true;
1044 while (nregs-- > 0)
1045 if (TEST_HARD_REG_BIT (*pset, regno + nregs))
1046 all_dead = false;
1047 else
1048 all_live = false;
1049 if (!all_dead && !all_live)
1051 fail_current_block = true;
1052 return false;
1054 return all_live;
1057 /* Return true if OP is a reg that is being tracked already in some form.
1058 May set fail_current_block if it sees an unhandled case of overlap. */
1060 static bool
1061 verify_reg_tracked (rtx op)
1063 return (verify_reg_in_set (op, &live_hard_regs)
1064 || verify_reg_in_set (op, &live_in_chains));
1067 /* Called through note_stores. DATA points to a rtx_code, either SET or
1068 CLOBBER, which tells us which kind of rtx to look at. If we have a
1069 match, record the set register in live_hard_regs and in the hard_conflicts
1070 bitmap of open chains. */
1072 static void
1073 note_sets_clobbers (rtx x, const_rtx set, void *data)
1075 enum rtx_code code = *(enum rtx_code *)data;
1076 class du_head *chain;
1078 if (GET_CODE (x) == SUBREG)
1079 x = SUBREG_REG (x);
1080 if (!REG_P (x) || GET_CODE (set) != code)
1081 return;
1082 /* There must not be pseudos at this point. */
1083 gcc_assert (HARD_REGISTER_P (x));
1084 add_to_hard_reg_set (&live_hard_regs, GET_MODE (x), REGNO (x));
1085 for (chain = open_chains; chain; chain = chain->next_chain)
1086 add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x));
1089 static void
1090 scan_rtx_reg (rtx_insn *insn, rtx *loc, enum reg_class cl, enum scan_actions action,
1091 enum op_type type)
1093 class du_head **p;
1094 rtx x = *loc;
1095 unsigned this_regno = REGNO (x);
1096 int this_nregs = REG_NREGS (x);
1098 if (action == mark_write)
1100 if (type == OP_OUT)
1102 du_head_p c;
1103 rtx pat = PATTERN (insn);
1105 c = create_new_chain (this_regno, this_nregs, loc, insn, cl);
1107 /* We try to tie chains in a move instruction for
1108 a single output. */
1109 if (recog_data.n_operands == 2
1110 && GET_CODE (pat) == SET
1111 && GET_CODE (SET_DEST (pat)) == REG
1112 && GET_CODE (SET_SRC (pat)) == REG
1113 && terminated_this_insn
1114 && terminated_this_insn->nregs
1115 == REG_NREGS (recog_data.operand[1]))
1117 gcc_assert (terminated_this_insn->regno
1118 == REGNO (recog_data.operand[1]));
1120 c->tied_chain = terminated_this_insn;
1121 terminated_this_insn->tied_chain = c;
1123 if (dump_file)
1124 fprintf (dump_file, "Tying chain %s (%d) with %s (%d)\n",
1125 reg_names[c->regno], c->id,
1126 reg_names[terminated_this_insn->regno],
1127 terminated_this_insn->id);
1131 return;
1134 if ((type == OP_OUT) != (action == terminate_write || action == mark_access))
1135 return;
1137 for (p = &open_chains; *p;)
1139 class du_head *head = *p;
1140 class du_head *next = head->next_chain;
1141 int exact_match = (head->regno == this_regno
1142 && head->nregs == this_nregs);
1143 int superset = (this_regno <= head->regno
1144 && this_regno + this_nregs >= head->regno + head->nregs);
1145 int subset = (this_regno >= head->regno
1146 && this_regno + this_nregs <= head->regno + head->nregs);
1148 if (!bitmap_bit_p (&open_chains_set, head->id)
1149 || head->regno + head->nregs <= this_regno
1150 || this_regno + this_nregs <= head->regno)
1152 p = &head->next_chain;
1153 continue;
1156 if (action == mark_read || action == mark_access)
1158 /* ??? Class NO_REGS can happen if the md file makes use of
1159 EXTRA_CONSTRAINTS to match registers. Which is arguably
1160 wrong, but there we are. */
1162 if (cl == NO_REGS || (!exact_match && !DEBUG_INSN_P (insn)))
1164 if (dump_file)
1165 fprintf (dump_file,
1166 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1167 reg_names[head->regno], head->id, INSN_UID (insn),
1168 scan_actions_name[(int) action]);
1169 head->cannot_rename = 1;
1170 if (superset)
1172 unsigned nregs = this_nregs;
1173 head->regno = this_regno;
1174 head->nregs = this_nregs;
1175 while (nregs-- > 0)
1176 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
1177 if (dump_file)
1178 fprintf (dump_file,
1179 "Widening register in chain %s (%d) at insn %d\n",
1180 reg_names[head->regno], head->id, INSN_UID (insn));
1182 else if (!subset)
1184 fail_current_block = true;
1185 if (dump_file)
1186 fprintf (dump_file,
1187 "Failing basic block due to unhandled overlap\n");
1190 else
1192 struct du_chain *this_du;
1193 this_du = XOBNEW (&rename_obstack, struct du_chain);
1194 this_du->next_use = 0;
1195 this_du->loc = loc;
1196 this_du->insn = insn;
1197 this_du->cl = cl;
1198 if (head->first == NULL)
1199 head->first = this_du;
1200 else
1201 head->last->next_use = this_du;
1202 record_operand_use (head, this_du);
1203 head->last = this_du;
1205 /* Avoid adding the same location in a DEBUG_INSN multiple times,
1206 which could happen with non-exact overlap. */
1207 if (DEBUG_INSN_P (insn))
1208 return;
1209 /* Otherwise, find any other chains that do not match exactly;
1210 ensure they all get marked unrenamable. */
1211 p = &head->next_chain;
1212 continue;
1215 /* Whether the terminated chain can be used for renaming
1216 depends on the action and this being an exact match.
1217 In either case, we remove this element from open_chains. */
1219 if ((action == terminate_dead || action == terminate_write)
1220 && (superset || subset))
1222 unsigned nregs;
1224 if (subset && !superset)
1225 head->cannot_rename = 1;
1226 bitmap_clear_bit (&open_chains_set, head->id);
1228 nregs = head->nregs;
1229 while (nregs-- > 0)
1231 CLEAR_HARD_REG_BIT (live_in_chains, head->regno + nregs);
1232 if (subset && !superset
1233 && (head->regno + nregs < this_regno
1234 || head->regno + nregs >= this_regno + this_nregs))
1235 SET_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
1238 if (action == terminate_dead)
1239 terminated_this_insn = *p;
1240 *p = next;
1241 if (dump_file)
1242 fprintf (dump_file,
1243 "Closing chain %s (%d) at insn %d (%s%s)\n",
1244 reg_names[head->regno], head->id, INSN_UID (insn),
1245 scan_actions_name[(int) action],
1246 superset ? ", superset" : subset ? ", subset" : "");
1248 else if (action == terminate_dead || action == terminate_write)
1250 /* In this case, tracking liveness gets too hard. Fail the
1251 entire basic block. */
1252 if (dump_file)
1253 fprintf (dump_file,
1254 "Failing basic block due to unhandled overlap\n");
1255 fail_current_block = true;
1256 return;
1258 else
1260 head->cannot_rename = 1;
1261 if (dump_file)
1262 fprintf (dump_file,
1263 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1264 reg_names[head->regno], head->id, INSN_UID (insn),
1265 scan_actions_name[(int) action]);
1266 p = &head->next_chain;
1271 /* A wrapper around base_reg_class which returns ALL_REGS if INSN is a
1272 DEBUG_INSN. The arguments MODE, AS, CODE and INDEX_CODE are as for
1273 base_reg_class. */
1275 static reg_class
1276 base_reg_class_for_rename (rtx_insn *insn, machine_mode mode, addr_space_t as,
1277 rtx_code code, rtx_code index_code)
1279 if (DEBUG_INSN_P (insn))
1280 return ALL_REGS;
1281 return base_reg_class (mode, as, code, index_code);
1284 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1285 BASE_REG_CLASS depending on how the register is being considered. */
1287 static void
1288 scan_rtx_address (rtx_insn *insn, rtx *loc, enum reg_class cl,
1289 enum scan_actions action, machine_mode mode,
1290 addr_space_t as)
1292 rtx x = *loc;
1293 RTX_CODE code = GET_CODE (x);
1294 const char *fmt;
1295 int i, j;
1297 if (action == mark_write || action == mark_access)
1298 return;
1300 switch (code)
1302 case PLUS:
1304 rtx orig_op0 = XEXP (x, 0);
1305 rtx orig_op1 = XEXP (x, 1);
1306 RTX_CODE code0 = GET_CODE (orig_op0);
1307 RTX_CODE code1 = GET_CODE (orig_op1);
1308 rtx op0 = orig_op0;
1309 rtx op1 = orig_op1;
1310 rtx *locI = NULL;
1311 rtx *locB = NULL;
1312 enum rtx_code index_code = SCRATCH;
1314 if (GET_CODE (op0) == SUBREG)
1316 op0 = SUBREG_REG (op0);
1317 code0 = GET_CODE (op0);
1320 if (GET_CODE (op1) == SUBREG)
1322 op1 = SUBREG_REG (op1);
1323 code1 = GET_CODE (op1);
1326 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
1327 || code0 == ZERO_EXTEND || code1 == MEM)
1329 locI = &XEXP (x, 0);
1330 locB = &XEXP (x, 1);
1331 index_code = GET_CODE (*locI);
1333 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
1334 || code1 == ZERO_EXTEND || code0 == MEM)
1336 locI = &XEXP (x, 1);
1337 locB = &XEXP (x, 0);
1338 index_code = GET_CODE (*locI);
1340 else if (code0 == CONST_INT || code0 == CONST
1341 || code0 == SYMBOL_REF || code0 == LABEL_REF)
1343 locB = &XEXP (x, 1);
1344 index_code = GET_CODE (XEXP (x, 0));
1346 else if (code1 == CONST_INT || code1 == CONST
1347 || code1 == SYMBOL_REF || code1 == LABEL_REF)
1349 locB = &XEXP (x, 0);
1350 index_code = GET_CODE (XEXP (x, 1));
1352 else if (code0 == REG && code1 == REG)
1354 int index_op;
1355 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
1357 if (REGNO_OK_FOR_INDEX_P (regno1)
1358 && regno_ok_for_base_p (regno0, mode, as, PLUS, REG))
1359 index_op = 1;
1360 else if (REGNO_OK_FOR_INDEX_P (regno0)
1361 && regno_ok_for_base_p (regno1, mode, as, PLUS, REG))
1362 index_op = 0;
1363 else if (regno_ok_for_base_p (regno0, mode, as, PLUS, REG)
1364 || REGNO_OK_FOR_INDEX_P (regno1))
1365 index_op = 1;
1366 else if (regno_ok_for_base_p (regno1, mode, as, PLUS, REG))
1367 index_op = 0;
1368 else
1369 index_op = 1;
1371 locI = &XEXP (x, index_op);
1372 locB = &XEXP (x, !index_op);
1373 index_code = GET_CODE (*locI);
1375 else if (code0 == REG)
1377 locI = &XEXP (x, 0);
1378 locB = &XEXP (x, 1);
1379 index_code = GET_CODE (*locI);
1381 else if (code1 == REG)
1383 locI = &XEXP (x, 1);
1384 locB = &XEXP (x, 0);
1385 index_code = GET_CODE (*locI);
1388 if (locI)
1390 reg_class iclass = DEBUG_INSN_P (insn) ? ALL_REGS : INDEX_REG_CLASS;
1391 scan_rtx_address (insn, locI, iclass, action, mode, as);
1393 if (locB)
1395 reg_class bclass = base_reg_class_for_rename (insn, mode, as, PLUS,
1396 index_code);
1397 scan_rtx_address (insn, locB, bclass, action, mode, as);
1399 return;
1402 case POST_INC:
1403 case POST_DEC:
1404 case POST_MODIFY:
1405 case PRE_INC:
1406 case PRE_DEC:
1407 case PRE_MODIFY:
1408 /* If the target doesn't claim to handle autoinc, this must be
1409 something special, like a stack push. Kill this chain. */
1410 if (!AUTO_INC_DEC)
1411 action = mark_all_read;
1413 break;
1415 case MEM:
1417 reg_class bclass = base_reg_class_for_rename (insn, GET_MODE (x),
1418 MEM_ADDR_SPACE (x),
1419 MEM, SCRATCH);
1420 scan_rtx_address (insn, &XEXP (x, 0), bclass, action, GET_MODE (x),
1421 MEM_ADDR_SPACE (x));
1423 return;
1425 case REG:
1426 scan_rtx_reg (insn, loc, cl, action, OP_IN);
1427 return;
1429 default:
1430 break;
1433 fmt = GET_RTX_FORMAT (code);
1434 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1436 if (fmt[i] == 'e')
1437 scan_rtx_address (insn, &XEXP (x, i), cl, action, mode, as);
1438 else if (fmt[i] == 'E')
1439 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1440 scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode, as);
1444 static void
1445 scan_rtx (rtx_insn *insn, rtx *loc, enum reg_class cl, enum scan_actions action,
1446 enum op_type type)
1448 const char *fmt;
1449 rtx x = *loc;
1450 int i, j;
1452 enum rtx_code code = GET_CODE (x);
1453 switch (code)
1455 case CONST:
1456 CASE_CONST_ANY:
1457 case SYMBOL_REF:
1458 case LABEL_REF:
1459 case PC:
1460 return;
1462 case REG:
1463 scan_rtx_reg (insn, loc, cl, action, type);
1464 return;
1466 case MEM:
1468 reg_class bclass = base_reg_class_for_rename (insn, GET_MODE (x),
1469 MEM_ADDR_SPACE (x),
1470 MEM, SCRATCH);
1472 scan_rtx_address (insn, &XEXP (x, 0), bclass, action, GET_MODE (x),
1473 MEM_ADDR_SPACE (x));
1475 return;
1477 case SET:
1478 scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN);
1479 scan_rtx (insn, &SET_DEST (x), cl, action,
1480 (GET_CODE (PATTERN (insn)) == COND_EXEC
1481 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
1482 return;
1484 case STRICT_LOW_PART:
1485 scan_rtx (insn, &XEXP (x, 0), cl, action,
1486 verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT);
1487 return;
1489 case ZERO_EXTRACT:
1490 case SIGN_EXTRACT:
1491 scan_rtx (insn, &XEXP (x, 0), cl, action,
1492 (type == OP_IN ? OP_IN :
1493 verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT));
1494 scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN);
1495 scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN);
1496 return;
1498 case POST_INC:
1499 case PRE_INC:
1500 case POST_DEC:
1501 case PRE_DEC:
1502 case POST_MODIFY:
1503 case PRE_MODIFY:
1504 /* Should only happen inside MEM. */
1505 gcc_unreachable ();
1507 case CLOBBER:
1508 scan_rtx (insn, &SET_DEST (x), cl, action,
1509 (GET_CODE (PATTERN (insn)) == COND_EXEC
1510 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
1511 return;
1513 case EXPR_LIST:
1514 scan_rtx (insn, &XEXP (x, 0), cl, action, type);
1515 if (XEXP (x, 1))
1516 scan_rtx (insn, &XEXP (x, 1), cl, action, type);
1517 return;
1519 default:
1520 break;
1523 fmt = GET_RTX_FORMAT (code);
1524 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1526 if (fmt[i] == 'e')
1527 scan_rtx (insn, &XEXP (x, i), cl, action, type);
1528 else if (fmt[i] == 'E')
1529 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1530 scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type);
1534 /* Hide operands of the current insn (of which there are N_OPS) by
1535 substituting pc for them.
1536 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
1537 For every bit set in DO_NOT_HIDE, we leave the operand alone.
1538 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
1539 and earlyclobbers. */
1541 static void
1542 hide_operands (int n_ops, rtx *old_operands, rtx *old_dups,
1543 unsigned HOST_WIDE_INT do_not_hide, bool inout_and_ec_only)
1545 int i;
1546 const operand_alternative *op_alt = which_op_alt ();
1547 for (i = 0; i < n_ops; i++)
1549 old_operands[i] = recog_data.operand[i];
1550 /* Don't squash match_operator or match_parallel here, since
1551 we don't know that all of the contained registers are
1552 reachable by proper operands. */
1553 if (recog_data.constraints[i][0] == '\0')
1554 continue;
1555 if (do_not_hide & (1 << i))
1556 continue;
1557 if (!inout_and_ec_only || recog_data.operand_type[i] == OP_INOUT
1558 || op_alt[i].earlyclobber)
1559 *recog_data.operand_loc[i] = pc_rtx;
1561 for (i = 0; i < recog_data.n_dups; i++)
1563 int opn = recog_data.dup_num[i];
1564 old_dups[i] = *recog_data.dup_loc[i];
1565 if (do_not_hide & (1 << opn))
1566 continue;
1567 if (!inout_and_ec_only || recog_data.operand_type[opn] == OP_INOUT
1568 || op_alt[opn].earlyclobber)
1569 *recog_data.dup_loc[i] = pc_rtx;
1573 /* Undo the substitution performed by hide_operands. INSN is the insn we
1574 are processing; the arguments are the same as in hide_operands. */
1576 static void
1577 restore_operands (rtx_insn *insn, int n_ops, rtx *old_operands, rtx *old_dups)
1579 int i;
1580 for (i = 0; i < recog_data.n_dups; i++)
1581 *recog_data.dup_loc[i] = old_dups[i];
1582 for (i = 0; i < n_ops; i++)
1583 *recog_data.operand_loc[i] = old_operands[i];
1584 if (recog_data.n_dups)
1585 df_insn_rescan (insn);
1588 /* For each output operand of INSN, call scan_rtx to create a new
1589 open chain. Do this only for normal or earlyclobber outputs,
1590 depending on EARLYCLOBBER. If INSN_INFO is nonnull, use it to
1591 record information about the operands in the insn. */
1593 static void
1594 record_out_operands (rtx_insn *insn, bool earlyclobber, insn_rr_info *insn_info)
1596 int n_ops = recog_data.n_operands;
1597 const operand_alternative *op_alt = which_op_alt ();
1599 int i;
1601 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1603 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1604 rtx *loc = (i < n_ops
1605 ? recog_data.operand_loc[opn]
1606 : recog_data.dup_loc[i - n_ops]);
1607 rtx op = *loc;
1608 enum reg_class cl = alternative_class (op_alt, opn);
1610 class du_head *prev_open;
1612 if (recog_data.operand_type[opn] != OP_OUT
1613 || op_alt[opn].earlyclobber != earlyclobber)
1614 continue;
1616 if (insn_info)
1617 cur_operand = insn_info->op_info + i;
1619 prev_open = open_chains;
1620 if (earlyclobber)
1621 scan_rtx (insn, loc, cl, terminate_write, OP_OUT);
1622 scan_rtx (insn, loc, cl, mark_write, OP_OUT);
1624 /* ??? Many targets have output constraints on the SET_DEST
1625 of a call insn, which is stupid, since these are certainly
1626 ABI defined hard registers. For these, and for asm operands
1627 that originally referenced hard registers, we must record that
1628 the chain cannot be renamed. */
1629 if (CALL_P (insn)
1630 || (asm_noperands (PATTERN (insn)) > 0
1631 && REG_P (op)
1632 && REGNO (op) == ORIGINAL_REGNO (op)))
1634 if (prev_open != open_chains)
1635 open_chains->cannot_rename = 1;
1638 cur_operand = NULL;
1641 /* Build def/use chain. */
1643 static bool
1644 build_def_use (basic_block bb)
1646 rtx_insn *insn;
1647 unsigned HOST_WIDE_INT untracked_operands;
1649 fail_current_block = false;
1651 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
1653 if (NONDEBUG_INSN_P (insn))
1655 int n_ops;
1656 rtx note;
1657 rtx old_operands[MAX_RECOG_OPERANDS];
1658 rtx old_dups[MAX_DUP_OPERANDS];
1659 int i;
1660 int predicated;
1661 enum rtx_code set_code = SET;
1662 enum rtx_code clobber_code = CLOBBER;
1663 insn_rr_info *insn_info = NULL;
1664 terminated_this_insn = NULL;
1666 /* Process the insn, determining its effect on the def-use
1667 chains and live hard registers. We perform the following
1668 steps with the register references in the insn, simulating
1669 its effect:
1670 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1671 by creating chains and marking hard regs live.
1672 (2) Any read outside an operand causes any chain it overlaps
1673 with to be marked unrenamable.
1674 (3) Any read inside an operand is added if there's already
1675 an open chain for it.
1676 (4) For any REG_DEAD note we find, close open chains that
1677 overlap it.
1678 (5) For any non-earlyclobber write we find, close open chains
1679 that overlap it.
1680 (6) For any non-earlyclobber write we find in an operand, make
1681 a new chain or mark the hard register as live.
1682 (7) For any REG_UNUSED, close any chains we just opened.
1683 (8) For any REG_CFA_RESTORE or REG_CFA_REGISTER, kill any chain
1684 containing its dest.
1686 We cannot deal with situations where we track a reg in one mode
1687 and see a reference in another mode; these will cause the chain
1688 to be marked unrenamable or even cause us to abort the entire
1689 basic block. */
1691 extract_constrain_insn (insn);
1692 preprocess_constraints (insn);
1693 const operand_alternative *op_alt = which_op_alt ();
1694 n_ops = recog_data.n_operands;
1695 untracked_operands = 0;
1697 if (insn_rr.exists ())
1699 insn_info = &insn_rr[INSN_UID (insn)];
1700 insn_info->op_info = XOBNEWVEC (&rename_obstack, operand_rr_info,
1701 recog_data.n_operands);
1702 memset (insn_info->op_info, 0,
1703 sizeof (operand_rr_info) * recog_data.n_operands);
1706 /* Simplify the code below by promoting OP_OUT to OP_INOUT in
1707 predicated instructions, but only for register operands
1708 that are already tracked, so that we can create a chain
1709 when the first SET makes a register live. */
1711 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1712 for (i = 0; i < n_ops; ++i)
1714 rtx op = recog_data.operand[i];
1715 int matches = op_alt[i].matches;
1716 if (matches >= 0 || op_alt[i].matched >= 0
1717 || (predicated && recog_data.operand_type[i] == OP_OUT))
1719 recog_data.operand_type[i] = OP_INOUT;
1720 /* A special case to deal with instruction patterns that
1721 have matching operands with different modes. If we're
1722 not already tracking such a reg, we won't start here,
1723 and we must instead make sure to make the operand visible
1724 to the machinery that tracks hard registers. */
1725 machine_mode i_mode = recog_data.operand_mode[i];
1726 if (matches >= 0)
1728 machine_mode matches_mode
1729 = recog_data.operand_mode[matches];
1731 if (maybe_ne (GET_MODE_SIZE (i_mode),
1732 GET_MODE_SIZE (matches_mode))
1733 && !verify_reg_in_set (op, &live_in_chains))
1735 untracked_operands |= 1 << i;
1736 untracked_operands |= 1 << matches;
1740 #ifdef STACK_REGS
1741 if (regstack_completed
1742 && REG_P (op)
1743 && IN_RANGE (REGNO (op), FIRST_STACK_REG, LAST_STACK_REG))
1744 untracked_operands |= 1 << i;
1745 #endif
1746 /* If there's an in-out operand with a register that is not
1747 being tracked at all yet, open a chain. */
1748 if (recog_data.operand_type[i] == OP_INOUT
1749 && !(untracked_operands & (1 << i))
1750 && REG_P (op)
1751 && !verify_reg_tracked (op))
1752 create_new_chain (REGNO (op), REG_NREGS (op), NULL, NULL,
1753 NO_REGS);
1756 if (fail_current_block)
1757 break;
1759 /* Step 1a: Mark hard registers that are clobbered in this insn,
1760 outside an operand, as live. */
1761 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1762 false);
1763 note_stores (insn, note_sets_clobbers, &clobber_code);
1764 restore_operands (insn, n_ops, old_operands, old_dups);
1766 /* Step 1b: Begin new chains for earlyclobbered writes inside
1767 operands. */
1768 record_out_operands (insn, true, insn_info);
1770 /* Step 2: Mark chains for which we have reads outside operands
1771 as unrenamable.
1772 We do this by munging all operands into PC, and closing
1773 everything remaining. */
1775 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1776 false);
1777 scan_rtx (insn, &PATTERN (insn), NO_REGS, mark_all_read, OP_IN);
1778 restore_operands (insn, n_ops, old_operands, old_dups);
1780 /* Step 2B: Can't rename function call argument registers. */
1781 if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
1782 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
1783 NO_REGS, mark_all_read, OP_IN);
1785 /* Step 2C: Can't rename asm operands that were originally
1786 hard registers. */
1787 if (asm_noperands (PATTERN (insn)) > 0)
1788 for (i = 0; i < n_ops; i++)
1790 rtx *loc = recog_data.operand_loc[i];
1791 rtx op = *loc;
1793 if (REG_P (op)
1794 && REGNO (op) == ORIGINAL_REGNO (op)
1795 && (recog_data.operand_type[i] == OP_IN
1796 || recog_data.operand_type[i] == OP_INOUT))
1797 scan_rtx (insn, loc, NO_REGS, mark_all_read, OP_IN);
1800 /* Step 3: Append to chains for reads inside operands. */
1801 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1803 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1804 rtx *loc = (i < n_ops
1805 ? recog_data.operand_loc[opn]
1806 : recog_data.dup_loc[i - n_ops]);
1807 enum reg_class cl = alternative_class (op_alt, opn);
1808 enum op_type type = recog_data.operand_type[opn];
1810 /* Don't scan match_operand here, since we've no reg class
1811 information to pass down. Any operands that we could
1812 substitute in will be represented elsewhere. */
1813 if (recog_data.constraints[opn][0] == '\0'
1814 || untracked_operands & (1 << opn))
1815 continue;
1817 if (insn_info)
1818 cur_operand = i == opn ? insn_info->op_info + i : NULL;
1819 if (op_alt[opn].is_address)
1820 scan_rtx_address (insn, loc, cl, mark_read,
1821 VOIDmode, ADDR_SPACE_GENERIC);
1822 else
1823 scan_rtx (insn, loc, cl, mark_read, type);
1825 cur_operand = NULL;
1827 /* Step 3B: Record updates for regs in REG_INC notes, and
1828 source regs in REG_FRAME_RELATED_EXPR notes. */
1829 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1830 if (REG_NOTE_KIND (note) == REG_INC
1831 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1832 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
1833 OP_INOUT);
1835 /* Step 4: Close chains for registers that die here, unless
1836 the register is mentioned in a REG_UNUSED note. In that
1837 case we keep the chain open until step #7 below to ensure
1838 it conflicts with other output operands of this insn.
1839 See PR 52573. Arguably the insn should not have both
1840 notes; it has proven difficult to fix that without
1841 other undesirable side effects. */
1842 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1843 if (REG_NOTE_KIND (note) == REG_DEAD
1844 && !find_regno_note (insn, REG_UNUSED, REGNO (XEXP (note, 0))))
1846 remove_from_hard_reg_set (&live_hard_regs,
1847 GET_MODE (XEXP (note, 0)),
1848 REGNO (XEXP (note, 0)));
1849 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1850 OP_IN);
1853 /* Step 4B: If this is a call, any chain live at this point
1854 requires a caller-saved reg. */
1855 if (CALL_P (insn))
1857 function_abi callee_abi = insn_callee_abi (insn);
1858 class du_head *p;
1859 for (p = open_chains; p; p = p->next_chain)
1861 p->call_abis |= (1 << callee_abi.id ());
1862 p->call_clobber_mask
1863 |= callee_abi.full_and_partial_reg_clobbers ();
1864 p->hard_conflicts |= callee_abi.full_reg_clobbers ();
1868 /* Step 5: Close open chains that overlap writes. Similar to
1869 step 2, we hide in-out operands, since we do not want to
1870 close these chains. We also hide earlyclobber operands,
1871 since we've opened chains for them in step 1, and earlier
1872 chains they would overlap with must have been closed at
1873 the previous insn at the latest, as such operands cannot
1874 possibly overlap with any input operands. */
1876 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1877 true);
1878 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN);
1879 restore_operands (insn, n_ops, old_operands, old_dups);
1881 /* Step 6a: Mark hard registers that are set in this insn,
1882 outside an operand, as live. */
1883 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1884 false);
1885 note_stores (insn, note_sets_clobbers, &set_code);
1886 restore_operands (insn, n_ops, old_operands, old_dups);
1888 /* Step 6b: Begin new chains for writes inside operands. */
1889 record_out_operands (insn, false, insn_info);
1891 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1892 notes for update. */
1893 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1894 if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1895 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
1896 OP_INOUT);
1898 /* Step 7: Close chains for registers that were never
1899 really used here. */
1900 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1901 if (REG_NOTE_KIND (note) == REG_UNUSED)
1903 remove_from_hard_reg_set (&live_hard_regs,
1904 GET_MODE (XEXP (note, 0)),
1905 REGNO (XEXP (note, 0)));
1906 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1907 OP_IN);
1910 /* Step 8: Kill the chains involving register restores. Those
1911 should restore _that_ register. Similar for REG_CFA_REGISTER. */
1912 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1913 if (REG_NOTE_KIND (note) == REG_CFA_RESTORE
1914 || REG_NOTE_KIND (note) == REG_CFA_REGISTER)
1916 rtx *x = &XEXP (note, 0);
1917 if (!*x)
1918 x = &PATTERN (insn);
1919 if (GET_CODE (*x) == PARALLEL)
1920 x = &XVECEXP (*x, 0, 0);
1921 if (GET_CODE (*x) == SET)
1922 x = &SET_DEST (*x);
1923 scan_rtx (insn, x, NO_REGS, mark_all_read, OP_IN);
1926 else if (DEBUG_BIND_INSN_P (insn)
1927 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)))
1929 scan_rtx (insn, &INSN_VAR_LOCATION_LOC (insn),
1930 ALL_REGS, mark_read, OP_IN);
1932 if (insn == BB_END (bb))
1933 break;
1936 if (fail_current_block)
1937 return false;
1939 return true;
1942 /* Initialize the register renamer. If INSN_INFO is true, ensure that
1943 insn_rr is nonnull. */
1944 void
1945 regrename_init (bool insn_info)
1947 gcc_obstack_init (&rename_obstack);
1948 insn_rr.create (0);
1949 if (insn_info)
1950 insn_rr.safe_grow_cleared (get_max_uid (), true);
1953 /* Free all global data used by the register renamer. */
1954 void
1955 regrename_finish (void)
1957 insn_rr.release ();
1958 free_chain_data ();
1959 obstack_free (&rename_obstack, NULL);
1962 /* Perform register renaming on the current function. */
1964 static unsigned int
1965 regrename_optimize (void)
1967 df_set_flags (DF_LR_RUN_DCE);
1968 df_note_add_problem ();
1969 df_analyze ();
1970 df_set_flags (DF_DEFER_INSN_RESCAN);
1972 regrename_init (false);
1974 regrename_analyze (NULL, false);
1976 rename_chains ();
1978 regrename_finish ();
1980 return 0;
1983 namespace {
1985 const pass_data pass_data_regrename =
1987 RTL_PASS, /* type */
1988 "rnreg", /* name */
1989 OPTGROUP_NONE, /* optinfo_flags */
1990 TV_RENAME_REGISTERS, /* tv_id */
1991 0, /* properties_required */
1992 0, /* properties_provided */
1993 0, /* properties_destroyed */
1994 0, /* todo_flags_start */
1995 TODO_df_finish, /* todo_flags_finish */
1998 class pass_regrename : public rtl_opt_pass
2000 public:
2001 pass_regrename (gcc::context *ctxt)
2002 : rtl_opt_pass (pass_data_regrename, ctxt)
2005 /* opt_pass methods: */
2006 virtual bool gate (function *)
2008 return (optimize > 0 && (flag_rename_registers));
2011 virtual unsigned int execute (function *) { return regrename_optimize (); }
2013 }; // class pass_regrename
2015 } // anon namespace
2017 rtl_opt_pass *
2018 make_pass_regrename (gcc::context *ctxt)
2020 return new pass_regrename (ctxt);