1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000-2018 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 "regrename.h"
38 /* This file implements the RTL register renaming pass of the compiler. It is
39 a semi-local pass whose goal is to maximize the usage of the register file
40 of the processor by substituting registers for others in the solution given
41 by the register allocator. The algorithm is as follows:
43 1. Local def/use chains are built: within each basic block, chains are
44 opened and closed; if a chain isn't closed at the end of the block,
45 it is dropped. We pre-open chains if we have already examined a
46 predecessor block and found chains live at the end which match
47 live registers at the start of the new block.
49 2. We try to combine the local chains across basic block boundaries by
50 comparing chains that were open at the start or end of a block to
51 those in successor/predecessor blocks.
53 3. For each chain, the set of possible renaming registers is computed.
54 This takes into account the renaming of previously processed chains.
55 Optionally, a preferred class is computed for the renaming register.
57 4. The best renaming register is computed for the chain in the above set,
58 using a round-robin allocation. If a preferred class exists, then the
59 round-robin allocation is done within the class first, if possible.
60 The round-robin allocation of renaming registers itself is global.
62 5. If a renaming register has been found, it is substituted in the chain.
64 Targets can parameterize the pass by specifying a preferred class for the
65 renaming register for a given (super)class of registers to be renamed.
67 DEBUG_INSNs are treated specially, in particular registers occurring inside
68 them are treated as requiring ALL_REGS as a class. */
70 #if HOST_BITS_PER_WIDE_INT <= MAX_RECOG_OPERANDS
71 #error "Use a different bitmap implementation for untracked_operands."
81 /* mark_access is for marking the destination regs in
82 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
83 note is updated properly. */
87 static const char * const scan_actions_name
[] =
97 /* TICK and THIS_TICK are used to record the last time we saw each
99 static int tick
[FIRST_PSEUDO_REGISTER
];
100 static int this_tick
= 0;
102 static struct obstack rename_obstack
;
104 /* If nonnull, the code calling into the register renamer requested
105 information about insn operands, and we store it here. */
106 vec
<insn_rr_info
> insn_rr
;
108 static void scan_rtx (rtx_insn
*, rtx
*, enum reg_class
, enum scan_actions
,
110 static bool build_def_use (basic_block
);
112 /* The id to be given to the next opened chain. */
113 static unsigned current_id
;
115 /* A mapping of unique id numbers to chains. */
116 static vec
<du_head_p
> id_to_chain
;
118 /* List of currently open chains. */
119 static struct du_head
*open_chains
;
121 /* Bitmap of open chains. The bits set always match the list found in
123 static bitmap_head open_chains_set
;
125 /* Record the registers being tracked in open_chains. */
126 static HARD_REG_SET live_in_chains
;
128 /* Record the registers that are live but not tracked. The intersection
129 between this and live_in_chains is empty. */
130 static HARD_REG_SET live_hard_regs
;
132 /* Set while scanning RTL if INSN_RR is nonnull, i.e. if the current analysis
133 is for a caller that requires operand data. Used in
134 record_operand_use. */
135 static operand_rr_info
*cur_operand
;
137 /* Set while scanning RTL if a register dies. Used to tie chains. */
138 static struct du_head
*terminated_this_insn
;
140 /* Return the chain corresponding to id number ID. Take into account that
141 chains may have been merged. */
143 regrename_chain_from_id (unsigned int id
)
145 du_head_p first_chain
= id_to_chain
[id
];
146 du_head_p chain
= first_chain
;
147 while (chain
->id
!= id
)
150 chain
= id_to_chain
[id
];
152 first_chain
->id
= id
;
156 /* Dump all def/use chains, starting at id FROM. */
159 dump_def_use_chain (int from
)
163 FOR_EACH_VEC_ELT_FROM (id_to_chain
, i
, head
, from
)
165 struct du_chain
*this_du
= head
->first
;
167 fprintf (dump_file
, "Register %s (%d):",
168 reg_names
[head
->regno
], head
->nregs
);
171 fprintf (dump_file
, " %d [%s]", INSN_UID (this_du
->insn
),
172 reg_class_names
[this_du
->cl
]);
173 this_du
= this_du
->next_use
;
175 fprintf (dump_file
, "\n");
176 head
= head
->next_chain
;
181 free_chain_data (void)
185 for (i
= 0; id_to_chain
.iterate (i
, &ptr
); i
++)
186 bitmap_clear (&ptr
->conflicts
);
188 id_to_chain
.release ();
191 /* Walk all chains starting with CHAINS and record that they conflict with
192 another chain whose id is ID. */
195 mark_conflict (struct du_head
*chains
, unsigned id
)
199 bitmap_set_bit (&chains
->conflicts
, id
);
200 chains
= chains
->next_chain
;
204 /* Examine cur_operand, and if it is nonnull, record information about the
205 use THIS_DU which is part of the chain HEAD. */
208 record_operand_use (struct du_head
*head
, struct du_chain
*this_du
)
210 if (cur_operand
== NULL
|| cur_operand
->failed
)
212 if (head
->cannot_rename
)
214 cur_operand
->failed
= true;
217 gcc_assert (cur_operand
->n_chains
< MAX_REGS_PER_ADDRESS
);
218 cur_operand
->heads
[cur_operand
->n_chains
] = head
;
219 cur_operand
->chains
[cur_operand
->n_chains
++] = this_du
;
222 /* Create a new chain for THIS_NREGS registers starting at THIS_REGNO,
223 and record its occurrence in *LOC, which is being written to in INSN.
224 This access requires a register of class CL. */
227 create_new_chain (unsigned this_regno
, unsigned this_nregs
, rtx
*loc
,
228 rtx_insn
*insn
, enum reg_class cl
)
230 struct du_head
*head
= XOBNEW (&rename_obstack
, struct du_head
);
231 struct du_chain
*this_du
;
234 memset (head
, 0, sizeof *head
);
235 head
->next_chain
= open_chains
;
236 head
->regno
= this_regno
;
237 head
->nregs
= this_nregs
;
239 id_to_chain
.safe_push (head
);
240 head
->id
= current_id
++;
242 bitmap_initialize (&head
->conflicts
, &bitmap_default_obstack
);
243 bitmap_copy (&head
->conflicts
, &open_chains_set
);
244 mark_conflict (open_chains
, head
->id
);
246 /* Since we're tracking this as a chain now, remove it from the
247 list of conflicting live hard registers and track it in
248 live_in_chains instead. */
252 SET_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
253 CLEAR_HARD_REG_BIT (live_hard_regs
, head
->regno
+ nregs
);
256 COPY_HARD_REG_SET (head
->hard_conflicts
, live_hard_regs
);
257 bitmap_set_bit (&open_chains_set
, head
->id
);
263 fprintf (dump_file
, "Creating chain %s (%d)",
264 reg_names
[head
->regno
], head
->id
);
265 if (insn
!= NULL_RTX
)
266 fprintf (dump_file
, " at insn %d", INSN_UID (insn
));
267 fprintf (dump_file
, "\n");
270 if (insn
== NULL_RTX
)
272 head
->first
= head
->last
= NULL
;
276 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
277 head
->first
= head
->last
= this_du
;
279 this_du
->next_use
= 0;
281 this_du
->insn
= insn
;
283 record_operand_use (head
, this_du
);
287 /* For a def-use chain HEAD, find which registers overlap its lifetime and
288 set the corresponding bits in *PSET. */
291 merge_overlapping_regs (HARD_REG_SET
*pset
, struct du_head
*head
)
295 IOR_HARD_REG_SET (*pset
, head
->hard_conflicts
);
296 EXECUTE_IF_SET_IN_BITMAP (&head
->conflicts
, 0, i
, bi
)
298 du_head_p other
= regrename_chain_from_id (i
);
299 unsigned j
= other
->nregs
;
300 gcc_assert (other
!= head
);
302 SET_HARD_REG_BIT (*pset
, other
->regno
+ j
);
306 /* Check if NEW_REG can be the candidate register to rename for
307 REG in THIS_HEAD chain. THIS_UNAVAILABLE is a set of unavailable hard
311 check_new_reg_p (int reg ATTRIBUTE_UNUSED
, int new_reg
,
312 struct du_head
*this_head
, HARD_REG_SET this_unavailable
)
314 machine_mode mode
= GET_MODE (*this_head
->first
->loc
);
315 int nregs
= hard_regno_nregs (new_reg
, mode
);
317 struct du_chain
*tmp
;
319 for (i
= nregs
- 1; i
>= 0; --i
)
320 if (TEST_HARD_REG_BIT (this_unavailable
, new_reg
+ i
)
321 || fixed_regs
[new_reg
+ i
]
322 || global_regs
[new_reg
+ i
]
323 /* Can't use regs which aren't saved by the prologue. */
324 || (! df_regs_ever_live_p (new_reg
+ i
)
325 && ! call_used_regs
[new_reg
+ i
])
326 #ifdef LEAF_REGISTERS
327 /* We can't use a non-leaf register if we're in a
330 && !LEAF_REGISTERS
[new_reg
+ i
])
332 || ! HARD_REGNO_RENAME_OK (reg
+ i
, new_reg
+ i
))
335 /* See whether it accepts all modes that occur in
336 definition and uses. */
337 for (tmp
= this_head
->first
; tmp
; tmp
= tmp
->next_use
)
338 if ((!targetm
.hard_regno_mode_ok (new_reg
, GET_MODE (*tmp
->loc
))
339 && ! DEBUG_INSN_P (tmp
->insn
))
340 || (this_head
->need_caller_save_reg
341 && ! (targetm
.hard_regno_call_part_clobbered
342 (reg
, GET_MODE (*tmp
->loc
)))
343 && (targetm
.hard_regno_call_part_clobbered
344 (new_reg
, GET_MODE (*tmp
->loc
)))))
350 /* For the chain THIS_HEAD, compute and return the best register to
351 rename to. SUPER_CLASS is the superunion of register classes in
352 the chain. UNAVAILABLE is a set of registers that cannot be used.
353 OLD_REG is the register currently used for the chain. BEST_RENAME
354 controls whether the register chosen must be better than the
355 current one or just respect the given constraint. */
358 find_rename_reg (du_head_p this_head
, enum reg_class super_class
,
359 HARD_REG_SET
*unavailable
, int old_reg
, bool best_rename
)
361 bool has_preferred_class
;
362 enum reg_class preferred_class
;
364 int best_new_reg
= old_reg
;
366 /* Further narrow the set of registers we can use for renaming.
367 If the chain needs a call-saved register, mark the call-used
368 registers as unavailable. */
369 if (this_head
->need_caller_save_reg
)
370 IOR_HARD_REG_SET (*unavailable
, call_used_reg_set
);
372 /* Mark registers that overlap this chain's lifetime as unavailable. */
373 merge_overlapping_regs (unavailable
, this_head
);
375 /* Compute preferred rename class of super union of all the classes
378 = (enum reg_class
) targetm
.preferred_rename_class (super_class
);
380 /* Pick and check the register from the tied chain iff the tied chain
382 if (this_head
->tied_chain
&& !this_head
->tied_chain
->renamed
383 && check_new_reg_p (old_reg
, this_head
->tied_chain
->regno
,
384 this_head
, *unavailable
))
385 return this_head
->tied_chain
->regno
;
387 /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
388 over registers that belong to PREFERRED_CLASS and try to find the
389 best register within the class. If that failed, we iterate in
390 the second pass over registers that don't belong to the class.
391 If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
392 ascending order without any preference. */
393 has_preferred_class
= (preferred_class
!= NO_REGS
);
394 for (pass
= (has_preferred_class
? 0 : 1); pass
< 2; pass
++)
397 for (new_reg
= 0; new_reg
< FIRST_PSEUDO_REGISTER
; new_reg
++)
399 if (has_preferred_class
401 != TEST_HARD_REG_BIT (reg_class_contents
[preferred_class
],
405 if (!check_new_reg_p (old_reg
, new_reg
, this_head
, *unavailable
))
411 /* In the first pass, we force the renaming of registers that
412 don't belong to PREFERRED_CLASS to registers that do, even
413 though the latters were used not very long ago. */
415 && !TEST_HARD_REG_BIT (reg_class_contents
[preferred_class
],
417 || tick
[best_new_reg
] > tick
[new_reg
])
418 best_new_reg
= new_reg
;
420 if (pass
== 0 && best_new_reg
!= old_reg
)
426 /* Iterate over elements in the chain HEAD in order to:
427 1. Count number of uses, storing it in *PN_USES.
428 2. Narrow the set of registers we can use for renaming, adding
429 unavailable registers to *PUNAVAILABLE, which must be
430 initialized by the caller.
431 3. Compute the superunion of register classes in this chain
434 regrename_find_superclass (du_head_p head
, int *pn_uses
,
435 HARD_REG_SET
*punavailable
)
438 reg_class super_class
= NO_REGS
;
439 for (du_chain
*tmp
= head
->first
; tmp
; tmp
= tmp
->next_use
)
441 if (DEBUG_INSN_P (tmp
->insn
))
444 IOR_COMPL_HARD_REG_SET (*punavailable
,
445 reg_class_contents
[tmp
->cl
]);
447 = reg_class_superunion
[(int) super_class
][(int) tmp
->cl
];
453 /* Perform register renaming on the current function. */
457 HARD_REG_SET unavailable
;
461 memset (tick
, 0, sizeof tick
);
463 CLEAR_HARD_REG_SET (unavailable
);
464 /* Don't clobber traceback for noreturn functions. */
465 if (frame_pointer_needed
)
467 add_to_hard_reg_set (&unavailable
, Pmode
, FRAME_POINTER_REGNUM
);
468 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
)
469 add_to_hard_reg_set (&unavailable
, Pmode
, HARD_FRAME_POINTER_REGNUM
);
472 FOR_EACH_VEC_ELT (id_to_chain
, i
, this_head
)
476 HARD_REG_SET this_unavailable
;
477 int reg
= this_head
->regno
;
479 if (this_head
->cannot_rename
)
482 if (fixed_regs
[reg
] || global_regs
[reg
]
483 || (!HARD_FRAME_POINTER_IS_FRAME_POINTER
&& frame_pointer_needed
484 && reg
== HARD_FRAME_POINTER_REGNUM
)
485 || (HARD_FRAME_POINTER_IS_FRAME_POINTER
&& frame_pointer_needed
486 && reg
== FRAME_POINTER_REGNUM
))
489 COPY_HARD_REG_SET (this_unavailable
, unavailable
);
491 reg_class super_class
= regrename_find_superclass (this_head
, &n_uses
,
496 best_new_reg
= find_rename_reg (this_head
, super_class
,
497 &this_unavailable
, reg
, true);
501 fprintf (dump_file
, "Register %s in insn %d",
502 reg_names
[reg
], INSN_UID (this_head
->first
->insn
));
503 if (this_head
->need_caller_save_reg
)
504 fprintf (dump_file
, " crosses a call");
507 if (best_new_reg
== reg
)
509 tick
[reg
] = ++this_tick
;
511 fprintf (dump_file
, "; no available better choice\n");
515 if (regrename_do_replace (this_head
, best_new_reg
))
518 fprintf (dump_file
, ", renamed as %s\n", reg_names
[best_new_reg
]);
519 tick
[best_new_reg
] = ++this_tick
;
520 df_set_regs_ever_live (best_new_reg
, true);
525 fprintf (dump_file
, ", renaming as %s failed\n",
526 reg_names
[best_new_reg
]);
527 tick
[reg
] = ++this_tick
;
532 /* A structure to record information for each hard register at the start of
534 struct incoming_reg_info
{
535 /* Holds the number of registers used in the chain that gave us information
536 about this register. Zero means no information known yet, while a
537 negative value is used for something that is part of, but not the first
538 register in a multi-register value. */
540 /* Set to true if we have accesses that conflict in the number of registers
545 /* A structure recording information about each basic block. It is saved
546 and restored around basic block boundaries.
547 A pointer to such a structure is stored in each basic block's aux field
548 during regrename_analyze, except for blocks we know can't be optimized
549 (such as entry and exit blocks). */
550 struct bb_rename_info
552 /* The basic block corresponding to this structure. */
554 /* Copies of the global information. */
555 bitmap_head open_chains_set
;
556 bitmap_head incoming_open_chains_set
;
557 struct incoming_reg_info incoming
[FIRST_PSEUDO_REGISTER
];
560 /* Initialize a rename_info structure P for basic block BB, which starts a new
563 init_rename_info (struct bb_rename_info
*p
, basic_block bb
)
567 HARD_REG_SET start_chains_set
;
570 bitmap_initialize (&p
->open_chains_set
, &bitmap_default_obstack
);
571 bitmap_initialize (&p
->incoming_open_chains_set
, &bitmap_default_obstack
);
574 bitmap_clear (&open_chains_set
);
576 CLEAR_HARD_REG_SET (live_in_chains
);
577 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_in (bb
));
578 FOR_EACH_ARTIFICIAL_DEF (def
, bb
->index
)
579 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
580 SET_HARD_REG_BIT (live_hard_regs
, DF_REF_REGNO (def
));
582 /* Open chains based on information from (at least one) predecessor
583 block. This gives us a chance later on to combine chains across
584 basic block boundaries. Inconsistencies (in access sizes) will
585 be caught normally and dealt with conservatively by disabling the
586 chain for renaming, and there is no risk of losing optimization
587 opportunities by opening chains either: if we did not open the
588 chains, we'd have to track the live register as a hard reg, and
589 we'd be unable to rename it in any case. */
590 CLEAR_HARD_REG_SET (start_chains_set
);
591 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
593 struct incoming_reg_info
*iri
= p
->incoming
+ i
;
594 if (iri
->nregs
> 0 && !iri
->unusable
595 && range_in_hard_reg_set_p (live_hard_regs
, i
, iri
->nregs
))
597 SET_HARD_REG_BIT (start_chains_set
, i
);
598 remove_range_from_hard_reg_set (&live_hard_regs
, i
, iri
->nregs
);
601 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
603 struct incoming_reg_info
*iri
= p
->incoming
+ i
;
604 if (TEST_HARD_REG_BIT (start_chains_set
, i
))
608 fprintf (dump_file
, "opening incoming chain\n");
609 chain
= create_new_chain (i
, iri
->nregs
, NULL
, NULL
, NO_REGS
);
610 bitmap_set_bit (&p
->incoming_open_chains_set
, chain
->id
);
615 /* Record in RI that the block corresponding to it has an incoming
616 live value, described by CHAIN. */
618 set_incoming_from_chain (struct bb_rename_info
*ri
, du_head_p chain
)
621 int incoming_nregs
= ri
->incoming
[chain
->regno
].nregs
;
624 /* If we've recorded the same information before, everything is fine. */
625 if (incoming_nregs
== chain
->nregs
)
628 fprintf (dump_file
, "reg %d/%d already recorded\n",
629 chain
->regno
, chain
->nregs
);
633 /* If we have no information for any of the involved registers, update
634 the incoming array. */
635 nregs
= chain
->nregs
;
637 if (ri
->incoming
[chain
->regno
+ nregs
].nregs
!= 0
638 || ri
->incoming
[chain
->regno
+ nregs
].unusable
)
642 nregs
= chain
->nregs
;
643 ri
->incoming
[chain
->regno
].nregs
= nregs
;
645 ri
->incoming
[chain
->regno
+ nregs
].nregs
= -nregs
;
647 fprintf (dump_file
, "recorded reg %d/%d\n",
648 chain
->regno
, chain
->nregs
);
652 /* There must be some kind of conflict. Prevent both the old and
653 new ranges from being used. */
654 if (incoming_nregs
< 0)
655 ri
->incoming
[chain
->regno
+ incoming_nregs
].unusable
= true;
656 for (i
= 0; i
< chain
->nregs
; i
++)
657 ri
->incoming
[chain
->regno
+ i
].unusable
= true;
660 /* Merge the two chains C1 and C2 so that all conflict information is
661 recorded and C1, and the id of C2 is changed to that of C1. */
663 merge_chains (du_head_p c1
, du_head_p c2
)
668 if (c2
->first
!= NULL
)
670 if (c1
->first
== NULL
)
671 c1
->first
= c2
->first
;
673 c1
->last
->next_use
= c2
->first
;
677 c2
->first
= c2
->last
= NULL
;
680 IOR_HARD_REG_SET (c1
->hard_conflicts
, c2
->hard_conflicts
);
681 bitmap_ior_into (&c1
->conflicts
, &c2
->conflicts
);
683 c1
->need_caller_save_reg
|= c2
->need_caller_save_reg
;
684 c1
->cannot_rename
|= c2
->cannot_rename
;
687 /* Analyze the current function and build chains for renaming. */
690 regrename_analyze (bitmap bb_mask
)
692 struct bb_rename_info
*rename_info
;
696 int *inverse_postorder
;
698 inverse_postorder
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
699 n_bbs
= pre_and_rev_post_order_compute (NULL
, inverse_postorder
, false);
701 /* Gather some information about the blocks in this function. */
702 rename_info
= XCNEWVEC (struct bb_rename_info
, n_basic_blocks_for_fn (cfun
));
704 FOR_EACH_BB_FN (bb
, cfun
)
706 struct bb_rename_info
*ri
= rename_info
+ i
;
708 if (bb_mask
!= NULL
&& !bitmap_bit_p (bb_mask
, bb
->index
))
716 id_to_chain
.create (0);
717 bitmap_initialize (&open_chains_set
, &bitmap_default_obstack
);
719 /* The order in which we visit blocks ensures that whenever
720 possible, we only process a block after at least one of its
721 predecessors, which provides a "seeding" effect to make the logic
722 in set_incoming_from_chain and init_rename_info useful. */
724 for (i
= 0; i
< n_bbs
; i
++)
726 basic_block bb1
= BASIC_BLOCK_FOR_FN (cfun
, inverse_postorder
[i
]);
727 struct bb_rename_info
*this_info
;
731 int old_length
= id_to_chain
.length ();
733 this_info
= (struct bb_rename_info
*) bb1
->aux
;
734 if (this_info
== NULL
)
738 fprintf (dump_file
, "\nprocessing block %d:\n", bb1
->index
);
740 init_rename_info (this_info
, bb1
);
742 success
= build_def_use (bb1
);
746 fprintf (dump_file
, "failed\n");
748 id_to_chain
.truncate (old_length
);
749 current_id
= old_length
;
750 bitmap_clear (&this_info
->incoming_open_chains_set
);
752 if (insn_rr
.exists ())
755 FOR_BB_INSNS (bb1
, insn
)
757 insn_rr_info
*p
= &insn_rr
[INSN_UID (insn
)];
765 dump_def_use_chain (old_length
);
766 bitmap_copy (&this_info
->open_chains_set
, &open_chains_set
);
768 /* Add successor blocks to the worklist if necessary, and record
769 data about our own open chains at the end of this block, which
770 will be used to pre-open chains when processing the successors. */
771 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
773 struct bb_rename_info
*dest_ri
;
774 struct du_head
*chain
;
777 fprintf (dump_file
, "successor block %d\n", e
->dest
->index
);
779 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
781 dest_ri
= (struct bb_rename_info
*)e
->dest
->aux
;
784 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
785 set_incoming_from_chain (dest_ri
, chain
);
789 free (inverse_postorder
);
791 /* Now, combine the chains data we have gathered across basic block
794 For every basic block, there may be chains open at the start, or at the
795 end. Rather than exclude them from renaming, we look for open chains
796 with matching registers at the other side of the CFG edge.
798 For a given chain using register R, open at the start of block B, we
799 must find an open chain using R on the other side of every edge leading
800 to B, if the register is live across this edge. In the code below,
801 N_PREDS_USED counts the number of edges where the register is live, and
802 N_PREDS_JOINED counts those where we found an appropriate chain for
805 We perform the analysis for both incoming and outgoing edges, but we
806 only need to merge once (in the second part, after verifying outgoing
808 FOR_EACH_BB_FN (bb
, cfun
)
810 struct bb_rename_info
*bb_ri
= (struct bb_rename_info
*) bb
->aux
;
818 fprintf (dump_file
, "processing bb %d in edges\n", bb
->index
);
820 EXECUTE_IF_SET_IN_BITMAP (&bb_ri
->incoming_open_chains_set
, 0, j
, bi
)
824 struct du_head
*chain
= regrename_chain_from_id (j
);
825 int n_preds_used
= 0, n_preds_joined
= 0;
827 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
829 struct bb_rename_info
*src_ri
;
833 bool success
= false;
835 REG_SET_TO_HARD_REG_SET (live
, df_get_live_out (e
->src
));
836 if (!range_overlaps_hard_reg_set_p (live
, chain
->regno
,
841 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
844 src_ri
= (struct bb_rename_info
*)e
->src
->aux
;
848 EXECUTE_IF_SET_IN_BITMAP (&src_ri
->open_chains_set
,
851 struct du_head
*outgoing_chain
= regrename_chain_from_id (k
);
853 if (outgoing_chain
->regno
== chain
->regno
854 && outgoing_chain
->nregs
== chain
->nregs
)
861 if (!success
&& dump_file
)
862 fprintf (dump_file
, "failure to match with pred block %d\n",
865 if (n_preds_joined
< n_preds_used
)
868 fprintf (dump_file
, "cannot rename chain %d\n", j
);
869 chain
->cannot_rename
= 1;
873 FOR_EACH_BB_FN (bb
, cfun
)
875 struct bb_rename_info
*bb_ri
= (struct bb_rename_info
*) bb
->aux
;
883 fprintf (dump_file
, "processing bb %d out edges\n", bb
->index
);
885 EXECUTE_IF_SET_IN_BITMAP (&bb_ri
->open_chains_set
, 0, j
, bi
)
889 struct du_head
*chain
= regrename_chain_from_id (j
);
890 int n_succs_used
= 0, n_succs_joined
= 0;
892 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
894 bool printed
= false;
895 struct bb_rename_info
*dest_ri
;
900 REG_SET_TO_HARD_REG_SET (live
, df_get_live_in (e
->dest
));
901 if (!range_overlaps_hard_reg_set_p (live
, chain
->regno
,
907 dest_ri
= (struct bb_rename_info
*)e
->dest
->aux
;
911 EXECUTE_IF_SET_IN_BITMAP (&dest_ri
->incoming_open_chains_set
,
914 struct du_head
*incoming_chain
= regrename_chain_from_id (k
);
916 if (incoming_chain
->regno
== chain
->regno
917 && incoming_chain
->nregs
== chain
->nregs
)
923 "merging blocks for edge %d -> %d\n",
924 e
->src
->index
, e
->dest
->index
);
927 " merging chains %d (->%d) and %d (->%d) [%s]\n",
928 k
, incoming_chain
->id
, j
, chain
->id
,
929 reg_names
[incoming_chain
->regno
]);
932 merge_chains (chain
, incoming_chain
);
938 if (n_succs_joined
< n_succs_used
)
941 fprintf (dump_file
, "cannot rename chain %d\n",
943 chain
->cannot_rename
= 1;
950 FOR_EACH_BB_FN (bb
, cfun
)
954 /* Attempt to replace all uses of the register in the chain beginning with
955 HEAD with REG. Returns true on success and false if the replacement is
956 rejected because the insns would not validate. The latter can happen
957 e.g. if a match_parallel predicate enforces restrictions on register
958 numbering in its subpatterns. */
961 regrename_do_replace (struct du_head
*head
, int reg
)
963 struct du_chain
*chain
;
964 unsigned int base_regno
= head
->regno
;
966 rtx last_reg
= NULL_RTX
, last_repl
= NULL_RTX
;
968 for (chain
= head
->first
; chain
; chain
= chain
->next_use
)
970 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
971 struct reg_attrs
*attr
= REG_ATTRS (*chain
->loc
);
972 int reg_ptr
= REG_POINTER (*chain
->loc
);
974 if (DEBUG_INSN_P (chain
->insn
) && REGNO (*chain
->loc
) != base_regno
)
975 validate_change (chain
->insn
, &(INSN_VAR_LOCATION_LOC (chain
->insn
)),
976 gen_rtx_UNKNOWN_VAR_LOC (), true);
979 if (*chain
->loc
!= last_reg
)
981 last_repl
= gen_raw_REG (GET_MODE (*chain
->loc
), reg
);
982 if (regno
>= FIRST_PSEUDO_REGISTER
)
983 ORIGINAL_REGNO (last_repl
) = regno
;
984 REG_ATTRS (last_repl
) = attr
;
985 REG_POINTER (last_repl
) = reg_ptr
;
986 last_reg
= *chain
->loc
;
988 validate_change (chain
->insn
, chain
->loc
, last_repl
, true);
992 if (!apply_change_group ())
995 mode
= GET_MODE (*head
->first
->loc
);
998 head
->nregs
= hard_regno_nregs (reg
, mode
);
1003 /* True if we found a register with a size mismatch, which means that we
1004 can't track its lifetime accurately. If so, we abort the current block
1005 without renaming. */
1006 static bool fail_current_block
;
1008 /* Return true if OP is a reg for which all bits are set in PSET, false
1009 if all bits are clear.
1010 In other cases, set fail_current_block and return false. */
1013 verify_reg_in_set (rtx op
, HARD_REG_SET
*pset
)
1015 unsigned regno
, nregs
;
1016 bool all_live
, all_dead
;
1021 nregs
= REG_NREGS (op
);
1022 all_live
= all_dead
= true;
1024 if (TEST_HARD_REG_BIT (*pset
, regno
+ nregs
))
1028 if (!all_dead
&& !all_live
)
1030 fail_current_block
= true;
1036 /* Return true if OP is a reg that is being tracked already in some form.
1037 May set fail_current_block if it sees an unhandled case of overlap. */
1040 verify_reg_tracked (rtx op
)
1042 return (verify_reg_in_set (op
, &live_hard_regs
)
1043 || verify_reg_in_set (op
, &live_in_chains
));
1046 /* Called through note_stores. DATA points to a rtx_code, either SET or
1047 CLOBBER, which tells us which kind of rtx to look at. If we have a
1048 match, record the set register in live_hard_regs and in the hard_conflicts
1049 bitmap of open chains. */
1052 note_sets_clobbers (rtx x
, const_rtx set
, void *data
)
1054 enum rtx_code code
= *(enum rtx_code
*)data
;
1055 struct du_head
*chain
;
1057 if (GET_CODE (x
) == SUBREG
)
1059 if (!REG_P (x
) || GET_CODE (set
) != code
)
1061 /* There must not be pseudos at this point. */
1062 gcc_assert (HARD_REGISTER_P (x
));
1063 add_to_hard_reg_set (&live_hard_regs
, GET_MODE (x
), REGNO (x
));
1064 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
1065 add_to_hard_reg_set (&chain
->hard_conflicts
, GET_MODE (x
), REGNO (x
));
1069 scan_rtx_reg (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
1074 unsigned this_regno
= REGNO (x
);
1075 int this_nregs
= REG_NREGS (x
);
1077 if (action
== mark_write
)
1082 rtx pat
= PATTERN (insn
);
1084 c
= create_new_chain (this_regno
, this_nregs
, loc
, insn
, cl
);
1086 /* We try to tie chains in a move instruction for
1088 if (recog_data
.n_operands
== 2
1089 && GET_CODE (pat
) == SET
1090 && GET_CODE (SET_DEST (pat
)) == REG
1091 && GET_CODE (SET_SRC (pat
)) == REG
1092 && terminated_this_insn
1093 && terminated_this_insn
->nregs
1094 == REG_NREGS (recog_data
.operand
[1]))
1096 gcc_assert (terminated_this_insn
->regno
1097 == REGNO (recog_data
.operand
[1]));
1099 c
->tied_chain
= terminated_this_insn
;
1100 terminated_this_insn
->tied_chain
= c
;
1103 fprintf (dump_file
, "Tying chain %s (%d) with %s (%d)\n",
1104 reg_names
[c
->regno
], c
->id
,
1105 reg_names
[terminated_this_insn
->regno
],
1106 terminated_this_insn
->id
);
1113 if ((type
== OP_OUT
) != (action
== terminate_write
|| action
== mark_access
))
1116 for (p
= &open_chains
; *p
;)
1118 struct du_head
*head
= *p
;
1119 struct du_head
*next
= head
->next_chain
;
1120 int exact_match
= (head
->regno
== this_regno
1121 && head
->nregs
== this_nregs
);
1122 int superset
= (this_regno
<= head
->regno
1123 && this_regno
+ this_nregs
>= head
->regno
+ head
->nregs
);
1124 int subset
= (this_regno
>= head
->regno
1125 && this_regno
+ this_nregs
<= head
->regno
+ head
->nregs
);
1127 if (!bitmap_bit_p (&open_chains_set
, head
->id
)
1128 || head
->regno
+ head
->nregs
<= this_regno
1129 || this_regno
+ this_nregs
<= head
->regno
)
1131 p
= &head
->next_chain
;
1135 if (action
== mark_read
|| action
== mark_access
)
1137 /* ??? Class NO_REGS can happen if the md file makes use of
1138 EXTRA_CONSTRAINTS to match registers. Which is arguably
1139 wrong, but there we are. */
1141 if (cl
== NO_REGS
|| (!exact_match
&& !DEBUG_INSN_P (insn
)))
1145 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1146 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1147 scan_actions_name
[(int) action
]);
1148 head
->cannot_rename
= 1;
1151 unsigned nregs
= this_nregs
;
1152 head
->regno
= this_regno
;
1153 head
->nregs
= this_nregs
;
1155 SET_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
1158 "Widening register in chain %s (%d) at insn %d\n",
1159 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
));
1163 fail_current_block
= true;
1166 "Failing basic block due to unhandled overlap\n");
1171 struct du_chain
*this_du
;
1172 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
1173 this_du
->next_use
= 0;
1175 this_du
->insn
= insn
;
1177 if (head
->first
== NULL
)
1178 head
->first
= this_du
;
1180 head
->last
->next_use
= this_du
;
1181 record_operand_use (head
, this_du
);
1182 head
->last
= this_du
;
1184 /* Avoid adding the same location in a DEBUG_INSN multiple times,
1185 which could happen with non-exact overlap. */
1186 if (DEBUG_INSN_P (insn
))
1188 /* Otherwise, find any other chains that do not match exactly;
1189 ensure they all get marked unrenamable. */
1190 p
= &head
->next_chain
;
1194 /* Whether the terminated chain can be used for renaming
1195 depends on the action and this being an exact match.
1196 In either case, we remove this element from open_chains. */
1198 if ((action
== terminate_dead
|| action
== terminate_write
)
1199 && (superset
|| subset
))
1203 if (subset
&& !superset
)
1204 head
->cannot_rename
= 1;
1205 bitmap_clear_bit (&open_chains_set
, head
->id
);
1207 nregs
= head
->nregs
;
1210 CLEAR_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
1211 if (subset
&& !superset
1212 && (head
->regno
+ nregs
< this_regno
1213 || head
->regno
+ nregs
>= this_regno
+ this_nregs
))
1214 SET_HARD_REG_BIT (live_hard_regs
, head
->regno
+ nregs
);
1217 if (action
== terminate_dead
)
1218 terminated_this_insn
= *p
;
1222 "Closing chain %s (%d) at insn %d (%s%s)\n",
1223 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1224 scan_actions_name
[(int) action
],
1225 superset
? ", superset" : subset
? ", subset" : "");
1227 else if (action
== terminate_dead
|| action
== terminate_write
)
1229 /* In this case, tracking liveness gets too hard. Fail the
1230 entire basic block. */
1233 "Failing basic block due to unhandled overlap\n");
1234 fail_current_block
= true;
1239 head
->cannot_rename
= 1;
1242 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1243 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1244 scan_actions_name
[(int) action
]);
1245 p
= &head
->next_chain
;
1250 /* A wrapper around base_reg_class which returns ALL_REGS if INSN is a
1251 DEBUG_INSN. The arguments MODE, AS, CODE and INDEX_CODE are as for
1255 base_reg_class_for_rename (rtx_insn
*insn
, machine_mode mode
, addr_space_t as
,
1256 rtx_code code
, rtx_code index_code
)
1258 if (DEBUG_INSN_P (insn
))
1260 return base_reg_class (mode
, as
, code
, index_code
);
1263 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1264 BASE_REG_CLASS depending on how the register is being considered. */
1267 scan_rtx_address (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
,
1268 enum scan_actions action
, machine_mode mode
,
1272 RTX_CODE code
= GET_CODE (x
);
1276 if (action
== mark_write
|| action
== mark_access
)
1283 rtx orig_op0
= XEXP (x
, 0);
1284 rtx orig_op1
= XEXP (x
, 1);
1285 RTX_CODE code0
= GET_CODE (orig_op0
);
1286 RTX_CODE code1
= GET_CODE (orig_op1
);
1291 enum rtx_code index_code
= SCRATCH
;
1293 if (GET_CODE (op0
) == SUBREG
)
1295 op0
= SUBREG_REG (op0
);
1296 code0
= GET_CODE (op0
);
1299 if (GET_CODE (op1
) == SUBREG
)
1301 op1
= SUBREG_REG (op1
);
1302 code1
= GET_CODE (op1
);
1305 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
1306 || code0
== ZERO_EXTEND
|| code1
== MEM
)
1308 locI
= &XEXP (x
, 0);
1309 locB
= &XEXP (x
, 1);
1310 index_code
= GET_CODE (*locI
);
1312 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
1313 || code1
== ZERO_EXTEND
|| code0
== MEM
)
1315 locI
= &XEXP (x
, 1);
1316 locB
= &XEXP (x
, 0);
1317 index_code
= GET_CODE (*locI
);
1319 else if (code0
== CONST_INT
|| code0
== CONST
1320 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
1322 locB
= &XEXP (x
, 1);
1323 index_code
= GET_CODE (XEXP (x
, 0));
1325 else if (code1
== CONST_INT
|| code1
== CONST
1326 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
1328 locB
= &XEXP (x
, 0);
1329 index_code
= GET_CODE (XEXP (x
, 1));
1331 else if (code0
== REG
&& code1
== REG
)
1334 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
1336 if (REGNO_OK_FOR_INDEX_P (regno1
)
1337 && regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
))
1339 else if (REGNO_OK_FOR_INDEX_P (regno0
)
1340 && regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
1342 else if (regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
)
1343 || REGNO_OK_FOR_INDEX_P (regno1
))
1345 else if (regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
1350 locI
= &XEXP (x
, index_op
);
1351 locB
= &XEXP (x
, !index_op
);
1352 index_code
= GET_CODE (*locI
);
1354 else if (code0
== REG
)
1356 locI
= &XEXP (x
, 0);
1357 locB
= &XEXP (x
, 1);
1358 index_code
= GET_CODE (*locI
);
1360 else if (code1
== REG
)
1362 locI
= &XEXP (x
, 1);
1363 locB
= &XEXP (x
, 0);
1364 index_code
= GET_CODE (*locI
);
1369 reg_class iclass
= DEBUG_INSN_P (insn
) ? ALL_REGS
: INDEX_REG_CLASS
;
1370 scan_rtx_address (insn
, locI
, iclass
, action
, mode
, as
);
1374 reg_class bclass
= base_reg_class_for_rename (insn
, mode
, as
, PLUS
,
1376 scan_rtx_address (insn
, locB
, bclass
, action
, mode
, as
);
1387 /* If the target doesn't claim to handle autoinc, this must be
1388 something special, like a stack push. Kill this chain. */
1390 action
= mark_all_read
;
1396 reg_class bclass
= base_reg_class_for_rename (insn
, GET_MODE (x
),
1399 scan_rtx_address (insn
, &XEXP (x
, 0), bclass
, action
, GET_MODE (x
),
1400 MEM_ADDR_SPACE (x
));
1405 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
);
1412 fmt
= GET_RTX_FORMAT (code
);
1413 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1416 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
, as
);
1417 else if (fmt
[i
] == 'E')
1418 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1419 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
, as
);
1424 scan_rtx (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
1429 enum rtx_code code
= GET_CODE (x
);
1432 code
= GET_CODE (x
);
1444 scan_rtx_reg (insn
, loc
, cl
, action
, type
);
1449 reg_class bclass
= base_reg_class_for_rename (insn
, GET_MODE (x
),
1453 scan_rtx_address (insn
, &XEXP (x
, 0), bclass
, action
, GET_MODE (x
),
1454 MEM_ADDR_SPACE (x
));
1459 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
);
1460 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
1461 (GET_CODE (PATTERN (insn
)) == COND_EXEC
1462 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
1465 case STRICT_LOW_PART
:
1466 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
1467 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
);
1472 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
1473 (type
== OP_IN
? OP_IN
:
1474 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
));
1475 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
);
1476 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
);
1485 /* Should only happen inside MEM. */
1489 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
1490 (GET_CODE (PATTERN (insn
)) == COND_EXEC
1491 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
1495 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
);
1497 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
);
1504 fmt
= GET_RTX_FORMAT (code
);
1505 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1508 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
);
1509 else if (fmt
[i
] == 'E')
1510 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1511 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
);
1515 /* Hide operands of the current insn (of which there are N_OPS) by
1516 substituting cc0 for them.
1517 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
1518 For every bit set in DO_NOT_HIDE, we leave the operand alone.
1519 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
1520 and earlyclobbers. */
1523 hide_operands (int n_ops
, rtx
*old_operands
, rtx
*old_dups
,
1524 unsigned HOST_WIDE_INT do_not_hide
, bool inout_and_ec_only
)
1527 const operand_alternative
*op_alt
= which_op_alt ();
1528 for (i
= 0; i
< n_ops
; i
++)
1530 old_operands
[i
] = recog_data
.operand
[i
];
1531 /* Don't squash match_operator or match_parallel here, since
1532 we don't know that all of the contained registers are
1533 reachable by proper operands. */
1534 if (recog_data
.constraints
[i
][0] == '\0')
1536 if (do_not_hide
& (1 << i
))
1538 if (!inout_and_ec_only
|| recog_data
.operand_type
[i
] == OP_INOUT
1539 || op_alt
[i
].earlyclobber
)
1540 *recog_data
.operand_loc
[i
] = cc0_rtx
;
1542 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1544 int opn
= recog_data
.dup_num
[i
];
1545 old_dups
[i
] = *recog_data
.dup_loc
[i
];
1546 if (do_not_hide
& (1 << opn
))
1548 if (!inout_and_ec_only
|| recog_data
.operand_type
[opn
] == OP_INOUT
1549 || op_alt
[opn
].earlyclobber
)
1550 *recog_data
.dup_loc
[i
] = cc0_rtx
;
1554 /* Undo the substitution performed by hide_operands. INSN is the insn we
1555 are processing; the arguments are the same as in hide_operands. */
1558 restore_operands (rtx_insn
*insn
, int n_ops
, rtx
*old_operands
, rtx
*old_dups
)
1561 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1562 *recog_data
.dup_loc
[i
] = old_dups
[i
];
1563 for (i
= 0; i
< n_ops
; i
++)
1564 *recog_data
.operand_loc
[i
] = old_operands
[i
];
1565 if (recog_data
.n_dups
)
1566 df_insn_rescan (insn
);
1569 /* For each output operand of INSN, call scan_rtx to create a new
1570 open chain. Do this only for normal or earlyclobber outputs,
1571 depending on EARLYCLOBBER. If INSN_INFO is nonnull, use it to
1572 record information about the operands in the insn. */
1575 record_out_operands (rtx_insn
*insn
, bool earlyclobber
, insn_rr_info
*insn_info
)
1577 int n_ops
= recog_data
.n_operands
;
1578 const operand_alternative
*op_alt
= which_op_alt ();
1582 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1584 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1585 rtx
*loc
= (i
< n_ops
1586 ? recog_data
.operand_loc
[opn
]
1587 : recog_data
.dup_loc
[i
- n_ops
]);
1589 enum reg_class cl
= alternative_class (op_alt
, opn
);
1591 struct du_head
*prev_open
;
1593 if (recog_data
.operand_type
[opn
] != OP_OUT
1594 || op_alt
[opn
].earlyclobber
!= earlyclobber
)
1598 cur_operand
= insn_info
->op_info
+ i
;
1600 prev_open
= open_chains
;
1602 scan_rtx (insn
, loc
, cl
, terminate_write
, OP_OUT
);
1603 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
);
1605 /* ??? Many targets have output constraints on the SET_DEST
1606 of a call insn, which is stupid, since these are certainly
1607 ABI defined hard registers. For these, and for asm operands
1608 that originally referenced hard registers, we must record that
1609 the chain cannot be renamed. */
1611 || (asm_noperands (PATTERN (insn
)) > 0
1613 && REGNO (op
) == ORIGINAL_REGNO (op
)))
1615 if (prev_open
!= open_chains
)
1616 open_chains
->cannot_rename
= 1;
1622 /* Build def/use chain. */
1625 build_def_use (basic_block bb
)
1628 unsigned HOST_WIDE_INT untracked_operands
;
1630 fail_current_block
= false;
1632 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1634 if (NONDEBUG_INSN_P (insn
))
1638 rtx old_operands
[MAX_RECOG_OPERANDS
];
1639 rtx old_dups
[MAX_DUP_OPERANDS
];
1642 enum rtx_code set_code
= SET
;
1643 enum rtx_code clobber_code
= CLOBBER
;
1644 insn_rr_info
*insn_info
= NULL
;
1645 terminated_this_insn
= NULL
;
1647 /* Process the insn, determining its effect on the def-use
1648 chains and live hard registers. We perform the following
1649 steps with the register references in the insn, simulating
1651 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1652 by creating chains and marking hard regs live.
1653 (2) Any read outside an operand causes any chain it overlaps
1654 with to be marked unrenamable.
1655 (3) Any read inside an operand is added if there's already
1656 an open chain for it.
1657 (4) For any REG_DEAD note we find, close open chains that
1659 (5) For any non-earlyclobber write we find, close open chains
1661 (6) For any non-earlyclobber write we find in an operand, make
1662 a new chain or mark the hard register as live.
1663 (7) For any REG_UNUSED, close any chains we just opened.
1664 (8) For any REG_CFA_RESTORE, kill any chain containing it.
1666 We cannot deal with situations where we track a reg in one mode
1667 and see a reference in another mode; these will cause the chain
1668 to be marked unrenamable or even cause us to abort the entire
1671 extract_constrain_insn (insn
);
1672 preprocess_constraints (insn
);
1673 const operand_alternative
*op_alt
= which_op_alt ();
1674 n_ops
= recog_data
.n_operands
;
1675 untracked_operands
= 0;
1677 if (insn_rr
.exists ())
1679 insn_info
= &insn_rr
[INSN_UID (insn
)];
1680 insn_info
->op_info
= XOBNEWVEC (&rename_obstack
, operand_rr_info
,
1681 recog_data
.n_operands
);
1682 memset (insn_info
->op_info
, 0,
1683 sizeof (operand_rr_info
) * recog_data
.n_operands
);
1686 /* Simplify the code below by promoting OP_OUT to OP_INOUT in
1687 predicated instructions, but only for register operands
1688 that are already tracked, so that we can create a chain
1689 when the first SET makes a register live. */
1691 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1692 for (i
= 0; i
< n_ops
; ++i
)
1694 rtx op
= recog_data
.operand
[i
];
1695 int matches
= op_alt
[i
].matches
;
1696 if (matches
>= 0 || op_alt
[i
].matched
>= 0
1697 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1699 recog_data
.operand_type
[i
] = OP_INOUT
;
1700 /* A special case to deal with instruction patterns that
1701 have matching operands with different modes. If we're
1702 not already tracking such a reg, we won't start here,
1703 and we must instead make sure to make the operand visible
1704 to the machinery that tracks hard registers. */
1705 machine_mode i_mode
= recog_data
.operand_mode
[i
];
1706 machine_mode matches_mode
= recog_data
.operand_mode
[matches
];
1708 && maybe_ne (GET_MODE_SIZE (i_mode
),
1709 GET_MODE_SIZE (matches_mode
))
1710 && !verify_reg_in_set (op
, &live_in_chains
))
1712 untracked_operands
|= 1 << i
;
1713 untracked_operands
|= 1 << matches
;
1717 if (regstack_completed
1719 && IN_RANGE (REGNO (op
), FIRST_STACK_REG
, LAST_STACK_REG
))
1720 untracked_operands
|= 1 << i
;
1722 /* If there's an in-out operand with a register that is not
1723 being tracked at all yet, open a chain. */
1724 if (recog_data
.operand_type
[i
] == OP_INOUT
1725 && !(untracked_operands
& (1 << i
))
1727 && !verify_reg_tracked (op
))
1728 create_new_chain (REGNO (op
), REG_NREGS (op
), NULL
, NULL
,
1732 if (fail_current_block
)
1735 /* Step 1a: Mark hard registers that are clobbered in this insn,
1736 outside an operand, as live. */
1737 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1739 note_stores (PATTERN (insn
), note_sets_clobbers
, &clobber_code
);
1740 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1742 /* Step 1b: Begin new chains for earlyclobbered writes inside
1744 record_out_operands (insn
, true, insn_info
);
1746 /* Step 2: Mark chains for which we have reads outside operands
1748 We do this by munging all operands into CC0, and closing
1749 everything remaining. */
1751 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1753 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, mark_all_read
, OP_IN
);
1754 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1756 /* Step 2B: Can't rename function call argument registers. */
1757 if (CALL_P (insn
) && CALL_INSN_FUNCTION_USAGE (insn
))
1758 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
1759 NO_REGS
, mark_all_read
, OP_IN
);
1761 /* Step 2C: Can't rename asm operands that were originally
1763 if (asm_noperands (PATTERN (insn
)) > 0)
1764 for (i
= 0; i
< n_ops
; i
++)
1766 rtx
*loc
= recog_data
.operand_loc
[i
];
1770 && REGNO (op
) == ORIGINAL_REGNO (op
)
1771 && (recog_data
.operand_type
[i
] == OP_IN
1772 || recog_data
.operand_type
[i
] == OP_INOUT
))
1773 scan_rtx (insn
, loc
, NO_REGS
, mark_all_read
, OP_IN
);
1776 /* Step 3: Append to chains for reads inside operands. */
1777 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1779 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1780 rtx
*loc
= (i
< n_ops
1781 ? recog_data
.operand_loc
[opn
]
1782 : recog_data
.dup_loc
[i
- n_ops
]);
1783 enum reg_class cl
= alternative_class (op_alt
, opn
);
1784 enum op_type type
= recog_data
.operand_type
[opn
];
1786 /* Don't scan match_operand here, since we've no reg class
1787 information to pass down. Any operands that we could
1788 substitute in will be represented elsewhere. */
1789 if (recog_data
.constraints
[opn
][0] == '\0'
1790 || untracked_operands
& (1 << opn
))
1794 cur_operand
= i
== opn
? insn_info
->op_info
+ i
: NULL
;
1795 if (op_alt
[opn
].is_address
)
1796 scan_rtx_address (insn
, loc
, cl
, mark_read
,
1797 VOIDmode
, ADDR_SPACE_GENERIC
);
1799 scan_rtx (insn
, loc
, cl
, mark_read
, type
);
1803 /* Step 3B: Record updates for regs in REG_INC notes, and
1804 source regs in REG_FRAME_RELATED_EXPR notes. */
1805 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1806 if (REG_NOTE_KIND (note
) == REG_INC
1807 || REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1808 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
1811 /* Step 4: Close chains for registers that die here, unless
1812 the register is mentioned in a REG_UNUSED note. In that
1813 case we keep the chain open until step #7 below to ensure
1814 it conflicts with other output operands of this insn.
1815 See PR 52573. Arguably the insn should not have both
1816 notes; it has proven difficult to fix that without
1817 other undesirable side effects. */
1818 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1819 if (REG_NOTE_KIND (note
) == REG_DEAD
1820 && !find_regno_note (insn
, REG_UNUSED
, REGNO (XEXP (note
, 0))))
1822 remove_from_hard_reg_set (&live_hard_regs
,
1823 GET_MODE (XEXP (note
, 0)),
1824 REGNO (XEXP (note
, 0)));
1825 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1829 /* Step 4B: If this is a call, any chain live at this point
1830 requires a caller-saved reg. */
1834 for (p
= open_chains
; p
; p
= p
->next_chain
)
1835 p
->need_caller_save_reg
= 1;
1838 /* Step 5: Close open chains that overlap writes. Similar to
1839 step 2, we hide in-out operands, since we do not want to
1840 close these chains. We also hide earlyclobber operands,
1841 since we've opened chains for them in step 1, and earlier
1842 chains they would overlap with must have been closed at
1843 the previous insn at the latest, as such operands cannot
1844 possibly overlap with any input operands. */
1846 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1848 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
);
1849 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1851 /* Step 6a: Mark hard registers that are set in this insn,
1852 outside an operand, as live. */
1853 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1855 note_stores (PATTERN (insn
), note_sets_clobbers
, &set_code
);
1856 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1858 /* Step 6b: Begin new chains for writes inside operands. */
1859 record_out_operands (insn
, false, insn_info
);
1861 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1862 notes for update. */
1863 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1864 if (REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1865 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_access
,
1868 /* Step 7: Close chains for registers that were never
1869 really used here. */
1870 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1871 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
1873 remove_from_hard_reg_set (&live_hard_regs
,
1874 GET_MODE (XEXP (note
, 0)),
1875 REGNO (XEXP (note
, 0)));
1876 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1880 /* Step 8: Kill the chains involving register restores. Those
1881 should restore _that_ register. */
1882 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1883 if (REG_NOTE_KIND (note
) == REG_CFA_RESTORE
)
1884 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, mark_all_read
, OP_IN
);
1886 else if (DEBUG_BIND_INSN_P (insn
)
1887 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn
)))
1889 scan_rtx (insn
, &INSN_VAR_LOCATION_LOC (insn
),
1890 ALL_REGS
, mark_read
, OP_IN
);
1892 if (insn
== BB_END (bb
))
1896 if (fail_current_block
)
1902 /* Initialize the register renamer. If INSN_INFO is true, ensure that
1903 insn_rr is nonnull. */
1905 regrename_init (bool insn_info
)
1907 gcc_obstack_init (&rename_obstack
);
1910 insn_rr
.safe_grow_cleared (get_max_uid ());
1913 /* Free all global data used by the register renamer. */
1915 regrename_finish (void)
1919 obstack_free (&rename_obstack
, NULL
);
1922 /* Perform register renaming on the current function. */
1925 regrename_optimize (void)
1927 df_set_flags (DF_LR_RUN_DCE
);
1928 df_note_add_problem ();
1930 df_set_flags (DF_DEFER_INSN_RESCAN
);
1932 regrename_init (false);
1934 regrename_analyze (NULL
);
1938 regrename_finish ();
1945 const pass_data pass_data_regrename
=
1947 RTL_PASS
, /* type */
1949 OPTGROUP_NONE
, /* optinfo_flags */
1950 TV_RENAME_REGISTERS
, /* tv_id */
1951 0, /* properties_required */
1952 0, /* properties_provided */
1953 0, /* properties_destroyed */
1954 0, /* todo_flags_start */
1955 TODO_df_finish
, /* todo_flags_finish */
1958 class pass_regrename
: public rtl_opt_pass
1961 pass_regrename (gcc::context
*ctxt
)
1962 : rtl_opt_pass (pass_data_regrename
, ctxt
)
1965 /* opt_pass methods: */
1966 virtual bool gate (function
*)
1968 return (optimize
> 0 && (flag_rename_registers
));
1971 virtual unsigned int execute (function
*) { return regrename_optimize (); }
1973 }; // class pass_regrename
1978 make_pass_regrename (gcc::context
*ctxt
)
1980 return new pass_regrename (ctxt
);