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)
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/>. */
22 #include "coretypes.h"
29 #include "insn-config.h"
33 #include "addresses.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."
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. */
88 static const char * const scan_actions_name
[] =
98 /* TICK and THIS_TICK are used to record the last time we saw each
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
,
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
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. */
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
)
151 chain
= id_to_chain
[id
];
153 first_chain
->id
= id
;
157 /* Dump all def/use chains, starting at id FROM. */
160 dump_def_use_chain (int from
)
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
);
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
;
182 free_chain_data (void)
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. */
196 mark_conflict (class du_head
*chains
, unsigned id
)
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. */
209 record_operand_use (class du_head
*head
, struct du_chain
*this_du
)
211 if (cur_operand
== NULL
|| cur_operand
->failed
)
213 if (head
->cannot_rename
)
215 cur_operand
->failed
= true;
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. */
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
;
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. */
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
);
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
;
277 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
278 head
->first
= head
->last
= this_du
;
280 this_du
->next_use
= 0;
282 this_du
->insn
= insn
;
284 record_operand_use (head
, this_du
);
288 /* For a def-use chain HEAD, find which registers overlap its lifetime and
289 set the corresponding bits in *PSET. */
292 merge_overlapping_regs (HARD_REG_SET
*pset
, class du_head
*head
)
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
);
303 SET_HARD_REG_BIT (*pset
, other
->regno
+ j
);
307 /* Return true if (reg:MODE REGNO) would be clobbered by a call covered
311 call_clobbered_in_chain_p (du_head
*this_head
, machine_mode mode
,
314 return call_clobbered_in_region_p (this_head
->call_abis
,
315 this_head
->call_clobber_mask
,
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
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
);
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
343 && !LEAF_REGISTERS
[new_reg
+ i
])
345 || ! HARD_REGNO_RENAME_OK (reg
+ i
, new_reg
+ i
))
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
))
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
),
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
;
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
388 = (enum reg_class
) targetm
.preferred_rename_class (super_class
);
390 /* Pick and check the register from the tied chain iff the tied chain
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 this insn is a noop move, then do not rename in this chain as doing so
398 would inhibit removal of the noop move. */
399 if (noop_move_p (this_head
->first
->insn
))
402 /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
403 over registers that belong to PREFERRED_CLASS and try to find the
404 best register within the class. If that failed, we iterate in
405 the second pass over registers that don't belong to the class.
406 If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
407 ascending order without any preference. */
408 has_preferred_class
= (preferred_class
!= NO_REGS
);
409 for (pass
= (has_preferred_class
? 0 : 1); pass
< 2; pass
++)
412 for (new_reg
= 0; new_reg
< FIRST_PSEUDO_REGISTER
; new_reg
++)
414 if (has_preferred_class
416 != TEST_HARD_REG_BIT (reg_class_contents
[preferred_class
],
420 if (!check_new_reg_p (old_reg
, new_reg
, this_head
, *unavailable
))
426 /* In the first pass, we force the renaming of registers that
427 don't belong to PREFERRED_CLASS to registers that do, even
428 though the latters were used not very long ago. */
430 && !TEST_HARD_REG_BIT (reg_class_contents
[preferred_class
],
432 || tick
[best_new_reg
] > tick
[new_reg
])
433 best_new_reg
= new_reg
;
435 if (pass
== 0 && best_new_reg
!= old_reg
)
441 /* Iterate over elements in the chain HEAD in order to:
442 1. Count number of uses, storing it in *PN_USES.
443 2. Narrow the set of registers we can use for renaming, adding
444 unavailable registers to *PUNAVAILABLE, which must be
445 initialized by the caller.
446 3. Compute the superunion of register classes in this chain
449 regrename_find_superclass (du_head_p head
, int *pn_uses
,
450 HARD_REG_SET
*punavailable
)
453 reg_class super_class
= NO_REGS
;
454 for (du_chain
*tmp
= head
->first
; tmp
; tmp
= tmp
->next_use
)
456 if (DEBUG_INSN_P (tmp
->insn
))
459 *punavailable
|= ~reg_class_contents
[tmp
->cl
];
461 = reg_class_superunion
[(int) super_class
][(int) tmp
->cl
];
467 /* Perform register renaming on the current function. */
471 HARD_REG_SET unavailable
;
475 memset (tick
, 0, sizeof tick
);
477 CLEAR_HARD_REG_SET (unavailable
);
478 /* Don't clobber traceback for noreturn functions. */
479 if (frame_pointer_needed
)
481 add_to_hard_reg_set (&unavailable
, Pmode
, FRAME_POINTER_REGNUM
);
482 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
)
483 add_to_hard_reg_set (&unavailable
, Pmode
, HARD_FRAME_POINTER_REGNUM
);
486 FOR_EACH_VEC_ELT (id_to_chain
, i
, this_head
)
490 HARD_REG_SET this_unavailable
;
491 int reg
= this_head
->regno
;
493 if (this_head
->cannot_rename
)
496 if (fixed_regs
[reg
] || global_regs
[reg
]
497 || (!HARD_FRAME_POINTER_IS_FRAME_POINTER
&& frame_pointer_needed
498 && reg
== HARD_FRAME_POINTER_REGNUM
)
499 || (HARD_FRAME_POINTER_IS_FRAME_POINTER
&& frame_pointer_needed
500 && reg
== FRAME_POINTER_REGNUM
))
503 this_unavailable
= unavailable
;
505 reg_class super_class
= regrename_find_superclass (this_head
, &n_uses
,
510 best_new_reg
= find_rename_reg (this_head
, super_class
,
511 &this_unavailable
, reg
, true);
515 fprintf (dump_file
, "Register %s in insn %d",
516 reg_names
[reg
], INSN_UID (this_head
->first
->insn
));
517 if (this_head
->call_abis
)
518 fprintf (dump_file
, " crosses a call");
521 if (best_new_reg
== reg
)
523 tick
[reg
] = ++this_tick
;
525 fprintf (dump_file
, "; no available better choice\n");
529 if (regrename_do_replace (this_head
, best_new_reg
))
532 fprintf (dump_file
, ", renamed as %s\n", reg_names
[best_new_reg
]);
533 tick
[best_new_reg
] = ++this_tick
;
534 df_set_regs_ever_live (best_new_reg
, true);
539 fprintf (dump_file
, ", renaming as %s failed\n",
540 reg_names
[best_new_reg
]);
541 tick
[reg
] = ++this_tick
;
546 /* A structure to record information for each hard register at the start of
548 struct incoming_reg_info
{
549 /* Holds the number of registers used in the chain that gave us information
550 about this register. Zero means no information known yet, while a
551 negative value is used for something that is part of, but not the first
552 register in a multi-register value. */
554 /* Set to true if we have accesses that conflict in the number of registers
559 /* A structure recording information about each basic block. It is saved
560 and restored around basic block boundaries.
561 A pointer to such a structure is stored in each basic block's aux field
562 during regrename_analyze, except for blocks we know can't be optimized
563 (such as entry and exit blocks). */
567 /* The basic block corresponding to this structure. */
569 /* Copies of the global information. */
570 bitmap_head open_chains_set
;
571 bitmap_head incoming_open_chains_set
;
572 struct incoming_reg_info incoming
[FIRST_PSEUDO_REGISTER
];
575 /* Initialize a rename_info structure P for basic block BB, which starts a new
578 init_rename_info (class bb_rename_info
*p
, basic_block bb
)
582 HARD_REG_SET start_chains_set
;
585 bitmap_initialize (&p
->open_chains_set
, &bitmap_default_obstack
);
586 bitmap_initialize (&p
->incoming_open_chains_set
, &bitmap_default_obstack
);
589 bitmap_clear (&open_chains_set
);
591 CLEAR_HARD_REG_SET (live_in_chains
);
592 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_in (bb
));
593 FOR_EACH_ARTIFICIAL_DEF (def
, bb
->index
)
594 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
595 SET_HARD_REG_BIT (live_hard_regs
, DF_REF_REGNO (def
));
597 /* Open chains based on information from (at least one) predecessor
598 block. This gives us a chance later on to combine chains across
599 basic block boundaries. Inconsistencies (in access sizes) will
600 be caught normally and dealt with conservatively by disabling the
601 chain for renaming, and there is no risk of losing optimization
602 opportunities by opening chains either: if we did not open the
603 chains, we'd have to track the live register as a hard reg, and
604 we'd be unable to rename it in any case. */
605 CLEAR_HARD_REG_SET (start_chains_set
);
606 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
608 struct incoming_reg_info
*iri
= p
->incoming
+ i
;
609 if (iri
->nregs
> 0 && !iri
->unusable
610 && range_in_hard_reg_set_p (live_hard_regs
, i
, iri
->nregs
))
612 SET_HARD_REG_BIT (start_chains_set
, i
);
613 remove_range_from_hard_reg_set (&live_hard_regs
, i
, iri
->nregs
);
616 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
618 struct incoming_reg_info
*iri
= p
->incoming
+ i
;
619 if (TEST_HARD_REG_BIT (start_chains_set
, i
))
623 fprintf (dump_file
, "opening incoming chain\n");
624 chain
= create_new_chain (i
, iri
->nregs
, NULL
, NULL
, NO_REGS
);
625 bitmap_set_bit (&p
->incoming_open_chains_set
, chain
->id
);
630 /* Record in RI that the block corresponding to it has an incoming
631 live value, described by CHAIN. */
633 set_incoming_from_chain (class bb_rename_info
*ri
, du_head_p chain
)
636 int incoming_nregs
= ri
->incoming
[chain
->regno
].nregs
;
639 /* If we've recorded the same information before, everything is fine. */
640 if (incoming_nregs
== chain
->nregs
)
643 fprintf (dump_file
, "reg %d/%d already recorded\n",
644 chain
->regno
, chain
->nregs
);
648 /* If we have no information for any of the involved registers, update
649 the incoming array. */
650 nregs
= chain
->nregs
;
652 if (ri
->incoming
[chain
->regno
+ nregs
].nregs
!= 0
653 || ri
->incoming
[chain
->regno
+ nregs
].unusable
)
657 nregs
= chain
->nregs
;
658 ri
->incoming
[chain
->regno
].nregs
= nregs
;
660 ri
->incoming
[chain
->regno
+ nregs
].nregs
= -nregs
;
662 fprintf (dump_file
, "recorded reg %d/%d\n",
663 chain
->regno
, chain
->nregs
);
667 /* There must be some kind of conflict. Prevent both the old and
668 new ranges from being used. */
669 if (incoming_nregs
< 0)
670 ri
->incoming
[chain
->regno
+ incoming_nregs
].unusable
= true;
671 for (i
= 0; i
< chain
->nregs
; i
++)
672 ri
->incoming
[chain
->regno
+ i
].unusable
= true;
675 /* Merge the two chains C1 and C2 so that all conflict information is
676 recorded and C1, and the id of C2 is changed to that of C1. */
678 merge_chains (du_head_p c1
, du_head_p c2
)
683 if (c2
->first
!= NULL
)
685 if (c1
->first
== NULL
)
686 c1
->first
= c2
->first
;
688 c1
->last
->next_use
= c2
->first
;
692 c2
->first
= c2
->last
= NULL
;
695 c1
->hard_conflicts
|= c2
->hard_conflicts
;
696 bitmap_ior_into (&c1
->conflicts
, &c2
->conflicts
);
698 c1
->call_clobber_mask
|= c2
->call_clobber_mask
;
699 c1
->call_abis
|= c2
->call_abis
;
700 c1
->cannot_rename
|= c2
->cannot_rename
;
703 /* Analyze the current function and build chains for renaming.
704 If INCLUDE_ALL_BLOCKS_P is set to true, process all blocks,
705 ignoring BB_DISABLE_SCHEDULE. The default value is true. */
708 regrename_analyze (bitmap bb_mask
, bool include_all_block_p
)
710 class bb_rename_info
*rename_info
;
714 int *inverse_postorder
;
716 inverse_postorder
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
717 n_bbs
= pre_and_rev_post_order_compute (NULL
, inverse_postorder
, false);
719 /* Gather some information about the blocks in this function. */
720 rename_info
= XCNEWVEC (class bb_rename_info
, n_basic_blocks_for_fn (cfun
));
722 FOR_EACH_BB_FN (bb
, cfun
)
724 class bb_rename_info
*ri
= rename_info
+ i
;
726 if (bb_mask
!= NULL
&& !bitmap_bit_p (bb_mask
, bb
->index
))
734 id_to_chain
.create (0);
735 bitmap_initialize (&open_chains_set
, &bitmap_default_obstack
);
737 /* The order in which we visit blocks ensures that whenever
738 possible, we only process a block after at least one of its
739 predecessors, which provides a "seeding" effect to make the logic
740 in set_incoming_from_chain and init_rename_info useful. */
742 for (i
= 0; i
< n_bbs
; i
++)
744 basic_block bb1
= BASIC_BLOCK_FOR_FN (cfun
, inverse_postorder
[i
]);
745 class bb_rename_info
*this_info
;
749 int old_length
= id_to_chain
.length ();
751 this_info
= (class bb_rename_info
*) bb1
->aux
;
752 if (this_info
== NULL
)
756 fprintf (dump_file
, "\nprocessing block %d:\n", bb1
->index
);
758 if (!include_all_block_p
&& (bb1
->flags
& BB_DISABLE_SCHEDULE
) != 0)
761 fprintf (dump_file
, "avoid disrupting the sms schedule of bb %d\n",
766 init_rename_info (this_info
, bb1
);
768 success
= build_def_use (bb1
);
772 fprintf (dump_file
, "failed\n");
774 id_to_chain
.truncate (old_length
);
775 current_id
= old_length
;
776 bitmap_clear (&this_info
->incoming_open_chains_set
);
778 if (insn_rr
.exists ())
781 FOR_BB_INSNS (bb1
, insn
)
783 insn_rr_info
*p
= &insn_rr
[INSN_UID (insn
)];
791 dump_def_use_chain (old_length
);
792 bitmap_copy (&this_info
->open_chains_set
, &open_chains_set
);
794 /* Add successor blocks to the worklist if necessary, and record
795 data about our own open chains at the end of this block, which
796 will be used to pre-open chains when processing the successors. */
797 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
799 class bb_rename_info
*dest_ri
;
800 class du_head
*chain
;
803 fprintf (dump_file
, "successor block %d\n", e
->dest
->index
);
805 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
807 dest_ri
= (class bb_rename_info
*)e
->dest
->aux
;
810 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
811 set_incoming_from_chain (dest_ri
, chain
);
815 free (inverse_postorder
);
817 /* Now, combine the chains data we have gathered across basic block
820 For every basic block, there may be chains open at the start, or at the
821 end. Rather than exclude them from renaming, we look for open chains
822 with matching registers at the other side of the CFG edge.
824 For a given chain using register R, open at the start of block B, we
825 must find an open chain using R on the other side of every edge leading
826 to B, if the register is live across this edge. In the code below,
827 N_PREDS_USED counts the number of edges where the register is live, and
828 N_PREDS_JOINED counts those where we found an appropriate chain for
831 We perform the analysis for both incoming and outgoing edges, but we
832 only need to merge once (in the second part, after verifying outgoing
834 FOR_EACH_BB_FN (bb
, cfun
)
836 class bb_rename_info
*bb_ri
= (class bb_rename_info
*) bb
->aux
;
844 fprintf (dump_file
, "processing bb %d in edges\n", bb
->index
);
846 EXECUTE_IF_SET_IN_BITMAP (&bb_ri
->incoming_open_chains_set
, 0, j
, bi
)
850 class du_head
*chain
= regrename_chain_from_id (j
);
851 int n_preds_used
= 0, n_preds_joined
= 0;
853 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
855 class bb_rename_info
*src_ri
;
859 bool success
= false;
861 REG_SET_TO_HARD_REG_SET (live
, df_get_live_out (e
->src
));
862 if (!range_overlaps_hard_reg_set_p (live
, chain
->regno
,
867 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
870 src_ri
= (class bb_rename_info
*)e
->src
->aux
;
874 EXECUTE_IF_SET_IN_BITMAP (&src_ri
->open_chains_set
,
877 class du_head
*outgoing_chain
= regrename_chain_from_id (k
);
879 if (outgoing_chain
->regno
== chain
->regno
880 && outgoing_chain
->nregs
== chain
->nregs
)
887 if (!success
&& dump_file
)
888 fprintf (dump_file
, "failure to match with pred block %d\n",
891 if (n_preds_joined
< n_preds_used
)
894 fprintf (dump_file
, "cannot rename chain %d\n", j
);
895 chain
->cannot_rename
= 1;
899 FOR_EACH_BB_FN (bb
, cfun
)
901 class bb_rename_info
*bb_ri
= (class bb_rename_info
*) bb
->aux
;
909 fprintf (dump_file
, "processing bb %d out edges\n", bb
->index
);
911 EXECUTE_IF_SET_IN_BITMAP (&bb_ri
->open_chains_set
, 0, j
, bi
)
915 class du_head
*chain
= regrename_chain_from_id (j
);
916 int n_succs_used
= 0, n_succs_joined
= 0;
918 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
920 bool printed
= false;
921 class bb_rename_info
*dest_ri
;
926 REG_SET_TO_HARD_REG_SET (live
, df_get_live_in (e
->dest
));
927 if (!range_overlaps_hard_reg_set_p (live
, chain
->regno
,
933 dest_ri
= (class bb_rename_info
*)e
->dest
->aux
;
937 EXECUTE_IF_SET_IN_BITMAP (&dest_ri
->incoming_open_chains_set
,
940 class du_head
*incoming_chain
= regrename_chain_from_id (k
);
942 if (incoming_chain
->regno
== chain
->regno
943 && incoming_chain
->nregs
== chain
->nregs
)
949 "merging blocks for edge %d -> %d\n",
950 e
->src
->index
, e
->dest
->index
);
953 " merging chains %d (->%d) and %d (->%d) [%s]\n",
954 k
, incoming_chain
->id
, j
, chain
->id
,
955 reg_names
[incoming_chain
->regno
]);
958 merge_chains (chain
, incoming_chain
);
964 if (n_succs_joined
< n_succs_used
)
967 fprintf (dump_file
, "cannot rename chain %d\n",
969 chain
->cannot_rename
= 1;
976 FOR_EACH_BB_FN (bb
, cfun
)
980 /* Attempt to replace all uses of the register in the chain beginning with
981 HEAD with REG. Returns true on success and false if the replacement is
982 rejected because the insns would not validate. The latter can happen
983 e.g. if a match_parallel predicate enforces restrictions on register
984 numbering in its subpatterns. */
987 regrename_do_replace (class du_head
*head
, int reg
)
989 struct du_chain
*chain
;
990 unsigned int base_regno
= head
->regno
;
992 rtx last_reg
= NULL_RTX
, last_repl
= NULL_RTX
;
994 for (chain
= head
->first
; chain
; chain
= chain
->next_use
)
996 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
997 class reg_attrs
*attr
= REG_ATTRS (*chain
->loc
);
998 int reg_ptr
= REG_POINTER (*chain
->loc
);
1000 if (DEBUG_INSN_P (chain
->insn
) && REGNO (*chain
->loc
) != base_regno
)
1001 validate_change (chain
->insn
, &(INSN_VAR_LOCATION_LOC (chain
->insn
)),
1002 gen_rtx_UNKNOWN_VAR_LOC (), true);
1005 if (*chain
->loc
!= last_reg
)
1007 last_repl
= gen_raw_REG (GET_MODE (*chain
->loc
), reg
);
1008 if (regno
>= FIRST_PSEUDO_REGISTER
)
1009 ORIGINAL_REGNO (last_repl
) = regno
;
1010 REG_ATTRS (last_repl
) = attr
;
1011 REG_POINTER (last_repl
) = reg_ptr
;
1012 last_reg
= *chain
->loc
;
1014 validate_change (chain
->insn
, chain
->loc
, last_repl
, true);
1018 if (!apply_change_group ())
1021 mode
= GET_MODE (*head
->first
->loc
);
1024 head
->nregs
= hard_regno_nregs (reg
, mode
);
1029 /* True if we found a register with a size mismatch, which means that we
1030 can't track its lifetime accurately. If so, we abort the current block
1031 without renaming. */
1032 static bool fail_current_block
;
1034 /* Return true if OP is a reg for which all bits are set in PSET, false
1035 if all bits are clear.
1036 In other cases, set fail_current_block and return false. */
1039 verify_reg_in_set (rtx op
, HARD_REG_SET
*pset
)
1041 unsigned regno
, nregs
;
1042 bool all_live
, all_dead
;
1047 nregs
= REG_NREGS (op
);
1048 all_live
= all_dead
= true;
1050 if (TEST_HARD_REG_BIT (*pset
, regno
+ nregs
))
1054 if (!all_dead
&& !all_live
)
1056 fail_current_block
= true;
1062 /* Return true if OP is a reg that is being tracked already in some form.
1063 May set fail_current_block if it sees an unhandled case of overlap. */
1066 verify_reg_tracked (rtx op
)
1068 return (verify_reg_in_set (op
, &live_hard_regs
)
1069 || verify_reg_in_set (op
, &live_in_chains
));
1072 /* Called through note_stores. DATA points to a rtx_code, either SET or
1073 CLOBBER, which tells us which kind of rtx to look at. If we have a
1074 match, record the set register in live_hard_regs and in the hard_conflicts
1075 bitmap of open chains. */
1078 note_sets_clobbers (rtx x
, const_rtx set
, void *data
)
1080 enum rtx_code code
= *(enum rtx_code
*)data
;
1081 class du_head
*chain
;
1083 if (GET_CODE (x
) == SUBREG
)
1085 if (!REG_P (x
) || GET_CODE (set
) != code
)
1087 /* There must not be pseudos at this point. */
1088 gcc_assert (HARD_REGISTER_P (x
));
1089 add_to_hard_reg_set (&live_hard_regs
, GET_MODE (x
), REGNO (x
));
1090 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
1091 add_to_hard_reg_set (&chain
->hard_conflicts
, GET_MODE (x
), REGNO (x
));
1095 scan_rtx_reg (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
1100 unsigned this_regno
= REGNO (x
);
1101 int this_nregs
= REG_NREGS (x
);
1103 if (action
== mark_write
)
1108 rtx pat
= PATTERN (insn
);
1110 c
= create_new_chain (this_regno
, this_nregs
, loc
, insn
, cl
);
1112 /* We try to tie chains in a move instruction for
1114 if (recog_data
.n_operands
== 2
1115 && GET_CODE (pat
) == SET
1116 && GET_CODE (SET_DEST (pat
)) == REG
1117 && GET_CODE (SET_SRC (pat
)) == REG
1118 && terminated_this_insn
1119 && terminated_this_insn
->nregs
1120 == REG_NREGS (recog_data
.operand
[1]))
1122 gcc_assert (terminated_this_insn
->regno
1123 == REGNO (recog_data
.operand
[1]));
1125 c
->tied_chain
= terminated_this_insn
;
1126 terminated_this_insn
->tied_chain
= c
;
1129 fprintf (dump_file
, "Tying chain %s (%d) with %s (%d)\n",
1130 reg_names
[c
->regno
], c
->id
,
1131 reg_names
[terminated_this_insn
->regno
],
1132 terminated_this_insn
->id
);
1139 if ((type
== OP_OUT
) != (action
== terminate_write
|| action
== mark_access
))
1142 for (p
= &open_chains
; *p
;)
1144 class du_head
*head
= *p
;
1145 class du_head
*next
= head
->next_chain
;
1146 int exact_match
= (head
->regno
== this_regno
1147 && head
->nregs
== this_nregs
);
1148 int superset
= (this_regno
<= head
->regno
1149 && this_regno
+ this_nregs
>= head
->regno
+ head
->nregs
);
1150 int subset
= (this_regno
>= head
->regno
1151 && this_regno
+ this_nregs
<= head
->regno
+ head
->nregs
);
1153 if (!bitmap_bit_p (&open_chains_set
, head
->id
)
1154 || head
->regno
+ head
->nregs
<= this_regno
1155 || this_regno
+ this_nregs
<= head
->regno
)
1157 p
= &head
->next_chain
;
1161 if (action
== mark_read
|| action
== mark_access
)
1163 /* ??? Class NO_REGS can happen if the md file makes use of
1164 EXTRA_CONSTRAINTS to match registers. Which is arguably
1165 wrong, but there we are. */
1167 if (cl
== NO_REGS
|| (!exact_match
&& !DEBUG_INSN_P (insn
)))
1171 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1172 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1173 scan_actions_name
[(int) action
]);
1174 head
->cannot_rename
= 1;
1177 unsigned nregs
= this_nregs
;
1178 head
->regno
= this_regno
;
1179 head
->nregs
= this_nregs
;
1181 SET_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
1184 "Widening register in chain %s (%d) at insn %d\n",
1185 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
));
1189 fail_current_block
= true;
1192 "Failing basic block due to unhandled overlap\n");
1197 struct du_chain
*this_du
;
1198 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
1199 this_du
->next_use
= 0;
1201 this_du
->insn
= insn
;
1203 if (head
->first
== NULL
)
1204 head
->first
= this_du
;
1206 head
->last
->next_use
= this_du
;
1207 record_operand_use (head
, this_du
);
1208 head
->last
= this_du
;
1210 /* Avoid adding the same location in a DEBUG_INSN multiple times,
1211 which could happen with non-exact overlap. */
1212 if (DEBUG_INSN_P (insn
))
1214 /* Otherwise, find any other chains that do not match exactly;
1215 ensure they all get marked unrenamable. */
1216 p
= &head
->next_chain
;
1220 /* Whether the terminated chain can be used for renaming
1221 depends on the action and this being an exact match.
1222 In either case, we remove this element from open_chains. */
1224 if ((action
== terminate_dead
|| action
== terminate_write
)
1225 && (superset
|| subset
))
1229 if (subset
&& !superset
)
1230 head
->cannot_rename
= 1;
1231 bitmap_clear_bit (&open_chains_set
, head
->id
);
1233 nregs
= head
->nregs
;
1236 CLEAR_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
1237 if (subset
&& !superset
1238 && (head
->regno
+ nregs
< this_regno
1239 || head
->regno
+ nregs
>= this_regno
+ this_nregs
))
1240 SET_HARD_REG_BIT (live_hard_regs
, head
->regno
+ nregs
);
1243 if (action
== terminate_dead
)
1244 terminated_this_insn
= *p
;
1248 "Closing chain %s (%d) at insn %d (%s%s)\n",
1249 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1250 scan_actions_name
[(int) action
],
1251 superset
? ", superset" : subset
? ", subset" : "");
1253 else if (action
== terminate_dead
|| action
== terminate_write
)
1255 /* In this case, tracking liveness gets too hard. Fail the
1256 entire basic block. */
1259 "Failing basic block due to unhandled overlap\n");
1260 fail_current_block
= true;
1265 head
->cannot_rename
= 1;
1268 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1269 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1270 scan_actions_name
[(int) action
]);
1271 p
= &head
->next_chain
;
1276 /* A wrapper around base_reg_class which returns ALL_REGS if INSN is a
1277 DEBUG_INSN. The arguments MODE, AS, CODE and INDEX_CODE are as for
1281 base_reg_class_for_rename (rtx_insn
*insn
, machine_mode mode
, addr_space_t as
,
1282 rtx_code code
, rtx_code index_code
)
1284 if (DEBUG_INSN_P (insn
))
1286 return base_reg_class (mode
, as
, code
, index_code
);
1289 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1290 BASE_REG_CLASS depending on how the register is being considered. */
1293 scan_rtx_address (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
,
1294 enum scan_actions action
, machine_mode mode
,
1298 RTX_CODE code
= GET_CODE (x
);
1302 if (action
== mark_write
|| action
== mark_access
)
1309 rtx orig_op0
= XEXP (x
, 0);
1310 rtx orig_op1
= XEXP (x
, 1);
1311 RTX_CODE code0
= GET_CODE (orig_op0
);
1312 RTX_CODE code1
= GET_CODE (orig_op1
);
1317 enum rtx_code index_code
= SCRATCH
;
1319 if (GET_CODE (op0
) == SUBREG
)
1321 op0
= SUBREG_REG (op0
);
1322 code0
= GET_CODE (op0
);
1325 if (GET_CODE (op1
) == SUBREG
)
1327 op1
= SUBREG_REG (op1
);
1328 code1
= GET_CODE (op1
);
1331 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
1332 || code0
== ZERO_EXTEND
|| code1
== MEM
)
1334 locI
= &XEXP (x
, 0);
1335 locB
= &XEXP (x
, 1);
1336 index_code
= GET_CODE (*locI
);
1338 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
1339 || code1
== ZERO_EXTEND
|| code0
== MEM
)
1341 locI
= &XEXP (x
, 1);
1342 locB
= &XEXP (x
, 0);
1343 index_code
= GET_CODE (*locI
);
1345 else if (code0
== CONST_INT
|| code0
== CONST
1346 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
1348 locB
= &XEXP (x
, 1);
1349 index_code
= GET_CODE (XEXP (x
, 0));
1351 else if (code1
== CONST_INT
|| code1
== CONST
1352 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
1354 locB
= &XEXP (x
, 0);
1355 index_code
= GET_CODE (XEXP (x
, 1));
1357 else if (code0
== REG
&& code1
== REG
)
1360 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
1362 if (REGNO_OK_FOR_INDEX_P (regno1
)
1363 && regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
))
1365 else if (REGNO_OK_FOR_INDEX_P (regno0
)
1366 && regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
1368 else if (regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
)
1369 || REGNO_OK_FOR_INDEX_P (regno1
))
1371 else if (regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
1376 locI
= &XEXP (x
, index_op
);
1377 locB
= &XEXP (x
, !index_op
);
1378 index_code
= GET_CODE (*locI
);
1380 else if (code0
== REG
)
1382 locI
= &XEXP (x
, 0);
1383 locB
= &XEXP (x
, 1);
1384 index_code
= GET_CODE (*locI
);
1386 else if (code1
== REG
)
1388 locI
= &XEXP (x
, 1);
1389 locB
= &XEXP (x
, 0);
1390 index_code
= GET_CODE (*locI
);
1395 reg_class iclass
= DEBUG_INSN_P (insn
) ? ALL_REGS
: INDEX_REG_CLASS
;
1396 scan_rtx_address (insn
, locI
, iclass
, action
, mode
, as
);
1400 reg_class bclass
= base_reg_class_for_rename (insn
, mode
, as
, PLUS
,
1402 scan_rtx_address (insn
, locB
, bclass
, action
, mode
, as
);
1413 /* If the target doesn't claim to handle autoinc, this must be
1414 something special, like a stack push. Kill this chain. */
1416 action
= mark_all_read
;
1422 reg_class bclass
= base_reg_class_for_rename (insn
, GET_MODE (x
),
1425 scan_rtx_address (insn
, &XEXP (x
, 0), bclass
, action
, GET_MODE (x
),
1426 MEM_ADDR_SPACE (x
));
1431 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
);
1438 fmt
= GET_RTX_FORMAT (code
);
1439 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1442 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
, as
);
1443 else if (fmt
[i
] == 'E')
1444 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1445 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
, as
);
1450 scan_rtx (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
1457 enum rtx_code code
= GET_CODE (x
);
1468 scan_rtx_reg (insn
, loc
, cl
, action
, type
);
1473 reg_class bclass
= base_reg_class_for_rename (insn
, GET_MODE (x
),
1477 scan_rtx_address (insn
, &XEXP (x
, 0), bclass
, action
, GET_MODE (x
),
1478 MEM_ADDR_SPACE (x
));
1483 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
);
1484 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
1485 (GET_CODE (PATTERN (insn
)) == COND_EXEC
1486 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
1489 case STRICT_LOW_PART
:
1490 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
1491 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
);
1496 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
1497 (type
== OP_IN
? OP_IN
:
1498 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
));
1499 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
);
1500 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
);
1509 /* Should only happen inside MEM. */
1513 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
1514 (GET_CODE (PATTERN (insn
)) == COND_EXEC
1515 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
1519 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
);
1521 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
);
1528 fmt
= GET_RTX_FORMAT (code
);
1529 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1532 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
);
1533 else if (fmt
[i
] == 'E')
1534 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1535 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
);
1539 /* Hide operands of the current insn (of which there are N_OPS) by
1540 substituting pc for them.
1541 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
1542 For every bit set in DO_NOT_HIDE, we leave the operand alone.
1543 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
1544 and earlyclobbers. */
1547 hide_operands (int n_ops
, rtx
*old_operands
, rtx
*old_dups
,
1548 unsigned HOST_WIDE_INT do_not_hide
, bool inout_and_ec_only
)
1551 const operand_alternative
*op_alt
= which_op_alt ();
1552 for (i
= 0; i
< n_ops
; i
++)
1554 old_operands
[i
] = recog_data
.operand
[i
];
1555 /* Don't squash match_operator or match_parallel here, since
1556 we don't know that all of the contained registers are
1557 reachable by proper operands. */
1558 if (recog_data
.constraints
[i
][0] == '\0')
1560 if (do_not_hide
& (1 << i
))
1562 if (!inout_and_ec_only
|| recog_data
.operand_type
[i
] == OP_INOUT
1563 || op_alt
[i
].earlyclobber
)
1564 *recog_data
.operand_loc
[i
] = pc_rtx
;
1566 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1568 int opn
= recog_data
.dup_num
[i
];
1569 old_dups
[i
] = *recog_data
.dup_loc
[i
];
1570 if (do_not_hide
& (1 << opn
))
1572 if (!inout_and_ec_only
|| recog_data
.operand_type
[opn
] == OP_INOUT
1573 || op_alt
[opn
].earlyclobber
)
1574 *recog_data
.dup_loc
[i
] = pc_rtx
;
1578 /* Undo the substitution performed by hide_operands. INSN is the insn we
1579 are processing; the arguments are the same as in hide_operands. */
1582 restore_operands (rtx_insn
*insn
, int n_ops
, rtx
*old_operands
, rtx
*old_dups
)
1585 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1586 *recog_data
.dup_loc
[i
] = old_dups
[i
];
1587 for (i
= 0; i
< n_ops
; i
++)
1588 *recog_data
.operand_loc
[i
] = old_operands
[i
];
1589 if (recog_data
.n_dups
)
1590 df_insn_rescan (insn
);
1593 /* For each output operand of INSN, call scan_rtx to create a new
1594 open chain. Do this only for normal or earlyclobber outputs,
1595 depending on EARLYCLOBBER. If INSN_INFO is nonnull, use it to
1596 record information about the operands in the insn. */
1599 record_out_operands (rtx_insn
*insn
, bool earlyclobber
, insn_rr_info
*insn_info
)
1601 int n_ops
= recog_data
.n_operands
;
1602 const operand_alternative
*op_alt
= which_op_alt ();
1606 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1608 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1609 rtx
*loc
= (i
< n_ops
1610 ? recog_data
.operand_loc
[opn
]
1611 : recog_data
.dup_loc
[i
- n_ops
]);
1613 enum reg_class cl
= alternative_class (op_alt
, opn
);
1615 class du_head
*prev_open
;
1617 if (recog_data
.operand_type
[opn
] != OP_OUT
1618 || op_alt
[opn
].earlyclobber
!= earlyclobber
)
1622 cur_operand
= insn_info
->op_info
+ i
;
1624 prev_open
= open_chains
;
1626 scan_rtx (insn
, loc
, cl
, terminate_write
, OP_OUT
);
1627 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
);
1629 /* ??? Many targets have output constraints on the SET_DEST
1630 of a call insn, which is stupid, since these are certainly
1631 ABI defined hard registers. For these, and for asm operands
1632 that originally referenced hard registers, we must record that
1633 the chain cannot be renamed. */
1635 || (asm_noperands (PATTERN (insn
)) > 0
1637 && REGNO (op
) == ORIGINAL_REGNO (op
)))
1639 if (prev_open
!= open_chains
)
1640 open_chains
->cannot_rename
= 1;
1646 /* Build def/use chain. */
1649 build_def_use (basic_block bb
)
1652 unsigned HOST_WIDE_INT untracked_operands
;
1654 fail_current_block
= false;
1656 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1658 if (NONDEBUG_INSN_P (insn
))
1662 rtx old_operands
[MAX_RECOG_OPERANDS
];
1663 rtx old_dups
[MAX_DUP_OPERANDS
];
1666 enum rtx_code set_code
= SET
;
1667 enum rtx_code clobber_code
= CLOBBER
;
1668 insn_rr_info
*insn_info
= NULL
;
1669 terminated_this_insn
= NULL
;
1671 /* Process the insn, determining its effect on the def-use
1672 chains and live hard registers. We perform the following
1673 steps with the register references in the insn, simulating
1675 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1676 by creating chains and marking hard regs live.
1677 (2) Any read outside an operand causes any chain it overlaps
1678 with to be marked unrenamable.
1679 (3) Any read inside an operand is added if there's already
1680 an open chain for it.
1681 (4) For any REG_DEAD note we find, close open chains that
1683 (5) For any non-earlyclobber write we find, close open chains
1685 (6) For any non-earlyclobber write we find in an operand, make
1686 a new chain or mark the hard register as live.
1687 (7) For any REG_UNUSED, close any chains we just opened.
1688 (8) For any REG_CFA_RESTORE or REG_CFA_REGISTER, kill any chain
1689 containing its dest.
1691 We cannot deal with situations where we track a reg in one mode
1692 and see a reference in another mode; these will cause the chain
1693 to be marked unrenamable or even cause us to abort the entire
1696 extract_constrain_insn (insn
);
1697 preprocess_constraints (insn
);
1698 const operand_alternative
*op_alt
= which_op_alt ();
1699 n_ops
= recog_data
.n_operands
;
1700 untracked_operands
= 0;
1702 if (insn_rr
.exists ())
1704 insn_info
= &insn_rr
[INSN_UID (insn
)];
1705 insn_info
->op_info
= XOBNEWVEC (&rename_obstack
, operand_rr_info
,
1706 recog_data
.n_operands
);
1707 memset (insn_info
->op_info
, 0,
1708 sizeof (operand_rr_info
) * recog_data
.n_operands
);
1711 /* Simplify the code below by promoting OP_OUT to OP_INOUT in
1712 predicated instructions, but only for register operands
1713 that are already tracked, so that we can create a chain
1714 when the first SET makes a register live. */
1716 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1717 for (i
= 0; i
< n_ops
; ++i
)
1719 rtx op
= recog_data
.operand
[i
];
1720 int matches
= op_alt
[i
].matches
;
1721 if (matches
>= 0 || op_alt
[i
].matched
>= 0
1722 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1724 recog_data
.operand_type
[i
] = OP_INOUT
;
1725 /* A special case to deal with instruction patterns that
1726 have matching operands with different modes. If we're
1727 not already tracking such a reg, we won't start here,
1728 and we must instead make sure to make the operand visible
1729 to the machinery that tracks hard registers. */
1730 machine_mode i_mode
= recog_data
.operand_mode
[i
];
1733 machine_mode matches_mode
1734 = recog_data
.operand_mode
[matches
];
1736 if (maybe_ne (GET_MODE_SIZE (i_mode
),
1737 GET_MODE_SIZE (matches_mode
))
1738 && !verify_reg_in_set (op
, &live_in_chains
))
1740 untracked_operands
|= 1 << i
;
1741 untracked_operands
|= 1 << matches
;
1746 if (regstack_completed
1748 && IN_RANGE (REGNO (op
), FIRST_STACK_REG
, LAST_STACK_REG
))
1749 untracked_operands
|= 1 << i
;
1751 /* If there's an in-out operand with a register that is not
1752 being tracked at all yet, open a chain. */
1753 if (recog_data
.operand_type
[i
] == OP_INOUT
1754 && !(untracked_operands
& (1 << i
))
1756 && !verify_reg_tracked (op
))
1757 create_new_chain (REGNO (op
), REG_NREGS (op
), NULL
, NULL
,
1761 if (fail_current_block
)
1764 /* Step 1a: Mark hard registers that are clobbered in this insn,
1765 outside an operand, as live. */
1766 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1768 note_stores (insn
, note_sets_clobbers
, &clobber_code
);
1769 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1771 /* Step 1b: Begin new chains for earlyclobbered writes inside
1773 record_out_operands (insn
, true, insn_info
);
1775 /* Step 2: Mark chains for which we have reads outside operands
1777 We do this by munging all operands into PC, and closing
1778 everything remaining. */
1780 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1782 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, mark_all_read
, OP_IN
);
1783 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1785 /* Step 2B: Can't rename function call argument registers. */
1786 if (CALL_P (insn
) && CALL_INSN_FUNCTION_USAGE (insn
))
1787 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
1788 NO_REGS
, mark_all_read
, OP_IN
);
1790 /* Step 2C: Can't rename asm operands that were originally
1792 if (asm_noperands (PATTERN (insn
)) > 0)
1793 for (i
= 0; i
< n_ops
; i
++)
1795 rtx
*loc
= recog_data
.operand_loc
[i
];
1799 && REGNO (op
) == ORIGINAL_REGNO (op
)
1800 && (recog_data
.operand_type
[i
] == OP_IN
1801 || recog_data
.operand_type
[i
] == OP_INOUT
))
1802 scan_rtx (insn
, loc
, NO_REGS
, mark_all_read
, OP_IN
);
1805 /* Step 3: Append to chains for reads inside operands. */
1806 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1808 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1809 rtx
*loc
= (i
< n_ops
1810 ? recog_data
.operand_loc
[opn
]
1811 : recog_data
.dup_loc
[i
- n_ops
]);
1812 enum reg_class cl
= alternative_class (op_alt
, opn
);
1813 enum op_type type
= recog_data
.operand_type
[opn
];
1815 /* Don't scan match_operand here, since we've no reg class
1816 information to pass down. Any operands that we could
1817 substitute in will be represented elsewhere. */
1818 if (recog_data
.constraints
[opn
][0] == '\0'
1819 || untracked_operands
& (1 << opn
))
1823 cur_operand
= i
== opn
? insn_info
->op_info
+ i
: NULL
;
1824 if (op_alt
[opn
].is_address
)
1825 scan_rtx_address (insn
, loc
, cl
, mark_read
,
1826 VOIDmode
, ADDR_SPACE_GENERIC
);
1828 scan_rtx (insn
, loc
, cl
, mark_read
, type
);
1832 /* Step 3B: Record updates for regs in REG_INC notes, and
1833 source regs in REG_FRAME_RELATED_EXPR notes. */
1834 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1835 if (REG_NOTE_KIND (note
) == REG_INC
1836 || REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1837 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
1840 /* Step 4: Close chains for registers that die here, unless
1841 the register is mentioned in a REG_UNUSED note. In that
1842 case we keep the chain open until step #7 below to ensure
1843 it conflicts with other output operands of this insn.
1844 See PR 52573. Arguably the insn should not have both
1845 notes; it has proven difficult to fix that without
1846 other undesirable side effects. */
1847 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1848 if (REG_NOTE_KIND (note
) == REG_DEAD
1849 && !find_regno_note (insn
, REG_UNUSED
, REGNO (XEXP (note
, 0))))
1851 remove_from_hard_reg_set (&live_hard_regs
,
1852 GET_MODE (XEXP (note
, 0)),
1853 REGNO (XEXP (note
, 0)));
1854 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1858 /* Step 4B: If this is a call, any chain live at this point
1859 requires a caller-saved reg. */
1862 function_abi callee_abi
= insn_callee_abi (insn
);
1864 for (p
= open_chains
; p
; p
= p
->next_chain
)
1866 p
->call_abis
|= (1 << callee_abi
.id ());
1867 p
->call_clobber_mask
1868 |= callee_abi
.full_and_partial_reg_clobbers ();
1869 p
->hard_conflicts
|= callee_abi
.full_reg_clobbers ();
1873 /* Step 5: Close open chains that overlap writes. Similar to
1874 step 2, we hide in-out operands, since we do not want to
1875 close these chains. We also hide earlyclobber operands,
1876 since we've opened chains for them in step 1, and earlier
1877 chains they would overlap with must have been closed at
1878 the previous insn at the latest, as such operands cannot
1879 possibly overlap with any input operands. */
1881 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1883 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
);
1884 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1886 /* Step 6a: Mark hard registers that are set in this insn,
1887 outside an operand, as live. */
1888 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1890 note_stores (insn
, note_sets_clobbers
, &set_code
);
1891 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1893 /* Step 6b: Begin new chains for writes inside operands. */
1894 record_out_operands (insn
, false, insn_info
);
1896 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1897 notes for update. */
1898 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1899 if (REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1900 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_access
,
1903 /* Step 7: Close chains for registers that were never
1904 really used here. */
1905 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1906 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
1908 remove_from_hard_reg_set (&live_hard_regs
,
1909 GET_MODE (XEXP (note
, 0)),
1910 REGNO (XEXP (note
, 0)));
1911 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1915 /* Step 8: Kill the chains involving register restores. Those
1916 should restore _that_ register. Similar for REG_CFA_REGISTER. */
1917 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1918 if (REG_NOTE_KIND (note
) == REG_CFA_RESTORE
1919 || REG_NOTE_KIND (note
) == REG_CFA_REGISTER
)
1921 rtx
*x
= &XEXP (note
, 0);
1923 x
= &PATTERN (insn
);
1924 if (GET_CODE (*x
) == PARALLEL
)
1925 x
= &XVECEXP (*x
, 0, 0);
1926 if (GET_CODE (*x
) == SET
)
1928 scan_rtx (insn
, x
, NO_REGS
, mark_all_read
, OP_IN
);
1931 else if (DEBUG_BIND_INSN_P (insn
)
1932 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn
)))
1934 scan_rtx (insn
, &INSN_VAR_LOCATION_LOC (insn
),
1935 ALL_REGS
, mark_read
, OP_IN
);
1937 if (insn
== BB_END (bb
))
1941 if (fail_current_block
)
1947 /* Initialize the register renamer. If INSN_INFO is true, ensure that
1948 insn_rr is nonnull. */
1950 regrename_init (bool insn_info
)
1952 gcc_obstack_init (&rename_obstack
);
1955 insn_rr
.safe_grow_cleared (get_max_uid (), true);
1958 /* Free all global data used by the register renamer. */
1960 regrename_finish (void)
1964 obstack_free (&rename_obstack
, NULL
);
1967 /* Perform register renaming on the current function. */
1970 regrename_optimize (void)
1972 df_set_flags (DF_LR_RUN_DCE
);
1973 df_note_add_problem ();
1975 df_set_flags (DF_DEFER_INSN_RESCAN
);
1977 regrename_init (false);
1979 regrename_analyze (NULL
, false);
1983 regrename_finish ();
1990 const pass_data pass_data_regrename
=
1992 RTL_PASS
, /* type */
1994 OPTGROUP_NONE
, /* optinfo_flags */
1995 TV_RENAME_REGISTERS
, /* tv_id */
1996 0, /* properties_required */
1997 0, /* properties_provided */
1998 0, /* properties_destroyed */
1999 0, /* todo_flags_start */
2000 TODO_df_finish
, /* todo_flags_finish */
2003 class pass_regrename
: public rtl_opt_pass
2006 pass_regrename (gcc::context
*ctxt
)
2007 : rtl_opt_pass (pass_data_regrename
, ctxt
)
2010 /* opt_pass methods: */
2011 virtual bool gate (function
*)
2013 return (optimize
> 0 && (flag_rename_registers
));
2016 virtual unsigned int execute (function
*) { return regrename_optimize (); }
2018 }; // class pass_regrename
2023 make_pass_regrename (gcc::context
*ctxt
)
2025 return new pass_regrename (ctxt
);