1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000-2016 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"
28 #include "insn-config.h"
32 #include "addresses.h"
34 #include "tree-pass.h"
35 #include "regrename.h"
37 /* This file implements the RTL register renaming pass of the compiler. It is
38 a semi-local pass whose goal is to maximize the usage of the register file
39 of the processor by substituting registers for others in the solution given
40 by the register allocator. The algorithm is as follows:
42 1. Local def/use chains are built: within each basic block, chains are
43 opened and closed; if a chain isn't closed at the end of the block,
44 it is dropped. We pre-open chains if we have already examined a
45 predecessor block and found chains live at the end which match
46 live registers at the start of the new block.
48 2. We try to combine the local chains across basic block boundaries by
49 comparing chains that were open at the start or end of a block to
50 those in successor/predecessor blocks.
52 3. For each chain, the set of possible renaming registers is computed.
53 This takes into account the renaming of previously processed chains.
54 Optionally, a preferred class is computed for the renaming register.
56 4. The best renaming register is computed for the chain in the above set,
57 using a round-robin allocation. If a preferred class exists, then the
58 round-robin allocation is done within the class first, if possible.
59 The round-robin allocation of renaming registers itself is global.
61 5. If a renaming register has been found, it is substituted in the chain.
63 Targets can parameterize the pass by specifying a preferred class for the
64 renaming register for a given (super)class of registers to be renamed. */
66 #if HOST_BITS_PER_WIDE_INT <= MAX_RECOG_OPERANDS
67 #error "Use a different bitmap implementation for untracked_operands."
77 /* mark_access is for marking the destination regs in
78 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
79 note is updated properly. */
83 static const char * const scan_actions_name
[] =
93 /* TICK and THIS_TICK are used to record the last time we saw each
95 static int tick
[FIRST_PSEUDO_REGISTER
];
96 static int this_tick
= 0;
98 static struct obstack rename_obstack
;
100 /* If nonnull, the code calling into the register renamer requested
101 information about insn operands, and we store it here. */
102 vec
<insn_rr_info
> insn_rr
;
104 static void scan_rtx (rtx_insn
*, rtx
*, enum reg_class
, enum scan_actions
,
106 static bool build_def_use (basic_block
);
108 /* The id to be given to the next opened chain. */
109 static unsigned current_id
;
111 /* A mapping of unique id numbers to chains. */
112 static vec
<du_head_p
> id_to_chain
;
114 /* List of currently open chains. */
115 static struct du_head
*open_chains
;
117 /* Bitmap of open chains. The bits set always match the list found in
119 static bitmap_head open_chains_set
;
121 /* Record the registers being tracked in open_chains. */
122 static HARD_REG_SET live_in_chains
;
124 /* Record the registers that are live but not tracked. The intersection
125 between this and live_in_chains is empty. */
126 static HARD_REG_SET live_hard_regs
;
128 /* Set while scanning RTL if INSN_RR is nonnull, i.e. if the current analysis
129 is for a caller that requires operand data. Used in
130 record_operand_use. */
131 static operand_rr_info
*cur_operand
;
133 /* Set while scanning RTL if a register dies. Used to tie chains. */
134 static struct du_head
*terminated_this_insn
;
136 /* Return the chain corresponding to id number ID. Take into account that
137 chains may have been merged. */
139 regrename_chain_from_id (unsigned int id
)
141 du_head_p first_chain
= id_to_chain
[id
];
142 du_head_p chain
= first_chain
;
143 while (chain
->id
!= id
)
146 chain
= id_to_chain
[id
];
148 first_chain
->id
= id
;
152 /* Dump all def/use chains, starting at id FROM. */
155 dump_def_use_chain (int from
)
159 FOR_EACH_VEC_ELT_FROM (id_to_chain
, i
, head
, from
)
161 struct du_chain
*this_du
= head
->first
;
163 fprintf (dump_file
, "Register %s (%d):",
164 reg_names
[head
->regno
], head
->nregs
);
167 fprintf (dump_file
, " %d [%s]", INSN_UID (this_du
->insn
),
168 reg_class_names
[this_du
->cl
]);
169 this_du
= this_du
->next_use
;
171 fprintf (dump_file
, "\n");
172 head
= head
->next_chain
;
177 free_chain_data (void)
181 for (i
= 0; id_to_chain
.iterate (i
, &ptr
); i
++)
182 bitmap_clear (&ptr
->conflicts
);
184 id_to_chain
.release ();
187 /* Walk all chains starting with CHAINS and record that they conflict with
188 another chain whose id is ID. */
191 mark_conflict (struct du_head
*chains
, unsigned id
)
195 bitmap_set_bit (&chains
->conflicts
, id
);
196 chains
= chains
->next_chain
;
200 /* Examine cur_operand, and if it is nonnull, record information about the
201 use THIS_DU which is part of the chain HEAD. */
204 record_operand_use (struct du_head
*head
, struct du_chain
*this_du
)
206 if (cur_operand
== NULL
|| cur_operand
->failed
)
208 if (head
->cannot_rename
)
210 cur_operand
->failed
= true;
213 gcc_assert (cur_operand
->n_chains
< MAX_REGS_PER_ADDRESS
);
214 cur_operand
->heads
[cur_operand
->n_chains
] = head
;
215 cur_operand
->chains
[cur_operand
->n_chains
++] = this_du
;
218 /* Create a new chain for THIS_NREGS registers starting at THIS_REGNO,
219 and record its occurrence in *LOC, which is being written to in INSN.
220 This access requires a register of class CL. */
223 create_new_chain (unsigned this_regno
, unsigned this_nregs
, rtx
*loc
,
224 rtx_insn
*insn
, enum reg_class cl
)
226 struct du_head
*head
= XOBNEW (&rename_obstack
, struct du_head
);
227 struct du_chain
*this_du
;
230 memset (head
, 0, sizeof *head
);
231 head
->next_chain
= open_chains
;
232 head
->regno
= this_regno
;
233 head
->nregs
= this_nregs
;
235 id_to_chain
.safe_push (head
);
236 head
->id
= current_id
++;
238 bitmap_initialize (&head
->conflicts
, &bitmap_default_obstack
);
239 bitmap_copy (&head
->conflicts
, &open_chains_set
);
240 mark_conflict (open_chains
, head
->id
);
242 /* Since we're tracking this as a chain now, remove it from the
243 list of conflicting live hard registers and track it in
244 live_in_chains instead. */
248 SET_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
249 CLEAR_HARD_REG_BIT (live_hard_regs
, head
->regno
+ nregs
);
252 COPY_HARD_REG_SET (head
->hard_conflicts
, live_hard_regs
);
253 bitmap_set_bit (&open_chains_set
, head
->id
);
259 fprintf (dump_file
, "Creating chain %s (%d)",
260 reg_names
[head
->regno
], head
->id
);
261 if (insn
!= NULL_RTX
)
262 fprintf (dump_file
, " at insn %d", INSN_UID (insn
));
263 fprintf (dump_file
, "\n");
266 if (insn
== NULL_RTX
)
268 head
->first
= head
->last
= NULL
;
272 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
273 head
->first
= head
->last
= this_du
;
275 this_du
->next_use
= 0;
277 this_du
->insn
= insn
;
279 record_operand_use (head
, this_du
);
283 /* For a def-use chain HEAD, find which registers overlap its lifetime and
284 set the corresponding bits in *PSET. */
287 merge_overlapping_regs (HARD_REG_SET
*pset
, struct du_head
*head
)
291 IOR_HARD_REG_SET (*pset
, head
->hard_conflicts
);
292 EXECUTE_IF_SET_IN_BITMAP (&head
->conflicts
, 0, i
, bi
)
294 du_head_p other
= regrename_chain_from_id (i
);
295 unsigned j
= other
->nregs
;
296 gcc_assert (other
!= head
);
298 SET_HARD_REG_BIT (*pset
, other
->regno
+ j
);
302 /* Check if NEW_REG can be the candidate register to rename for
303 REG in THIS_HEAD chain. THIS_UNAVAILABLE is a set of unavailable hard
307 check_new_reg_p (int reg ATTRIBUTE_UNUSED
, int new_reg
,
308 struct du_head
*this_head
, HARD_REG_SET this_unavailable
)
310 machine_mode mode
= GET_MODE (*this_head
->first
->loc
);
311 int nregs
= hard_regno_nregs
[new_reg
][mode
];
313 struct du_chain
*tmp
;
315 for (i
= nregs
- 1; i
>= 0; --i
)
316 if (TEST_HARD_REG_BIT (this_unavailable
, new_reg
+ i
)
317 || fixed_regs
[new_reg
+ i
]
318 || global_regs
[new_reg
+ i
]
319 /* Can't use regs which aren't saved by the prologue. */
320 || (! df_regs_ever_live_p (new_reg
+ i
)
321 && ! call_used_regs
[new_reg
+ i
])
322 #ifdef LEAF_REGISTERS
323 /* We can't use a non-leaf register if we're in a
326 && !LEAF_REGISTERS
[new_reg
+ i
])
328 || ! HARD_REGNO_RENAME_OK (reg
+ i
, new_reg
+ i
))
331 /* See whether it accepts all modes that occur in
332 definition and uses. */
333 for (tmp
= this_head
->first
; tmp
; tmp
= tmp
->next_use
)
334 if ((! HARD_REGNO_MODE_OK (new_reg
, GET_MODE (*tmp
->loc
))
335 && ! DEBUG_INSN_P (tmp
->insn
))
336 || (this_head
->need_caller_save_reg
337 && ! (HARD_REGNO_CALL_PART_CLOBBERED
338 (reg
, GET_MODE (*tmp
->loc
)))
339 && (HARD_REGNO_CALL_PART_CLOBBERED
340 (new_reg
, GET_MODE (*tmp
->loc
)))))
346 /* For the chain THIS_HEAD, compute and return the best register to
347 rename to. SUPER_CLASS is the superunion of register classes in
348 the chain. UNAVAILABLE is a set of registers that cannot be used.
349 OLD_REG is the register currently used for the chain. BEST_RENAME
350 controls whether the register chosen must be better than the
351 current one or just respect the given constraint. */
354 find_rename_reg (du_head_p this_head
, enum reg_class super_class
,
355 HARD_REG_SET
*unavailable
, int old_reg
, bool best_rename
)
357 bool has_preferred_class
;
358 enum reg_class preferred_class
;
360 int best_new_reg
= old_reg
;
362 /* Further narrow the set of registers we can use for renaming.
363 If the chain needs a call-saved register, mark the call-used
364 registers as unavailable. */
365 if (this_head
->need_caller_save_reg
)
366 IOR_HARD_REG_SET (*unavailable
, call_used_reg_set
);
368 /* Mark registers that overlap this chain's lifetime as unavailable. */
369 merge_overlapping_regs (unavailable
, this_head
);
371 /* Compute preferred rename class of super union of all the classes
374 = (enum reg_class
) targetm
.preferred_rename_class (super_class
);
376 /* Pick and check the register from the tied chain iff the tied chain
378 if (this_head
->tied_chain
&& !this_head
->tied_chain
->renamed
379 && check_new_reg_p (old_reg
, this_head
->tied_chain
->regno
,
380 this_head
, *unavailable
))
381 return this_head
->tied_chain
->regno
;
383 /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
384 over registers that belong to PREFERRED_CLASS and try to find the
385 best register within the class. If that failed, we iterate in
386 the second pass over registers that don't belong to the class.
387 If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
388 ascending order without any preference. */
389 has_preferred_class
= (preferred_class
!= NO_REGS
);
390 for (pass
= (has_preferred_class
? 0 : 1); pass
< 2; pass
++)
393 for (new_reg
= 0; new_reg
< FIRST_PSEUDO_REGISTER
; new_reg
++)
395 if (has_preferred_class
397 != TEST_HARD_REG_BIT (reg_class_contents
[preferred_class
],
401 if (!check_new_reg_p (old_reg
, new_reg
, this_head
, *unavailable
))
407 /* In the first pass, we force the renaming of registers that
408 don't belong to PREFERRED_CLASS to registers that do, even
409 though the latters were used not very long ago. */
411 && !TEST_HARD_REG_BIT (reg_class_contents
[preferred_class
],
413 || tick
[best_new_reg
] > tick
[new_reg
])
414 best_new_reg
= new_reg
;
416 if (pass
== 0 && best_new_reg
!= old_reg
)
422 /* Iterate over elements in the chain HEAD in order to:
423 1. Count number of uses, storing it in *PN_USES.
424 2. Narrow the set of registers we can use for renaming, adding
425 unavailable registers to *PUNAVAILABLE, which must be
426 initialized by the caller.
427 3. Compute the superunion of register classes in this chain
430 regrename_find_superclass (du_head_p head
, int *pn_uses
,
431 HARD_REG_SET
*punavailable
)
434 reg_class super_class
= NO_REGS
;
435 for (du_chain
*tmp
= head
->first
; tmp
; tmp
= tmp
->next_use
)
437 if (DEBUG_INSN_P (tmp
->insn
))
440 IOR_COMPL_HARD_REG_SET (*punavailable
,
441 reg_class_contents
[tmp
->cl
]);
443 = reg_class_superunion
[(int) super_class
][(int) tmp
->cl
];
449 /* Perform register renaming on the current function. */
453 HARD_REG_SET unavailable
;
457 memset (tick
, 0, sizeof tick
);
459 CLEAR_HARD_REG_SET (unavailable
);
460 /* Don't clobber traceback for noreturn functions. */
461 if (frame_pointer_needed
)
463 add_to_hard_reg_set (&unavailable
, Pmode
, FRAME_POINTER_REGNUM
);
464 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
)
465 add_to_hard_reg_set (&unavailable
, Pmode
, HARD_FRAME_POINTER_REGNUM
);
468 FOR_EACH_VEC_ELT (id_to_chain
, i
, this_head
)
472 HARD_REG_SET this_unavailable
;
473 int reg
= this_head
->regno
;
475 if (this_head
->cannot_rename
)
478 if (fixed_regs
[reg
] || global_regs
[reg
]
479 || (!HARD_FRAME_POINTER_IS_FRAME_POINTER
&& frame_pointer_needed
480 && reg
== HARD_FRAME_POINTER_REGNUM
)
481 || (HARD_FRAME_POINTER_REGNUM
&& frame_pointer_needed
482 && reg
== FRAME_POINTER_REGNUM
))
485 COPY_HARD_REG_SET (this_unavailable
, unavailable
);
487 reg_class super_class
= regrename_find_superclass (this_head
, &n_uses
,
492 best_new_reg
= find_rename_reg (this_head
, super_class
,
493 &this_unavailable
, reg
, true);
497 fprintf (dump_file
, "Register %s in insn %d",
498 reg_names
[reg
], INSN_UID (this_head
->first
->insn
));
499 if (this_head
->need_caller_save_reg
)
500 fprintf (dump_file
, " crosses a call");
503 if (best_new_reg
== reg
)
505 tick
[reg
] = ++this_tick
;
507 fprintf (dump_file
, "; no available better choice\n");
511 if (regrename_do_replace (this_head
, best_new_reg
))
514 fprintf (dump_file
, ", renamed as %s\n", reg_names
[best_new_reg
]);
515 tick
[best_new_reg
] = ++this_tick
;
516 df_set_regs_ever_live (best_new_reg
, true);
521 fprintf (dump_file
, ", renaming as %s failed\n",
522 reg_names
[best_new_reg
]);
523 tick
[reg
] = ++this_tick
;
528 /* A structure to record information for each hard register at the start of
530 struct incoming_reg_info
{
531 /* Holds the number of registers used in the chain that gave us information
532 about this register. Zero means no information known yet, while a
533 negative value is used for something that is part of, but not the first
534 register in a multi-register value. */
536 /* Set to true if we have accesses that conflict in the number of registers
541 /* A structure recording information about each basic block. It is saved
542 and restored around basic block boundaries.
543 A pointer to such a structure is stored in each basic block's aux field
544 during regrename_analyze, except for blocks we know can't be optimized
545 (such as entry and exit blocks). */
546 struct bb_rename_info
548 /* The basic block corresponding to this structure. */
550 /* Copies of the global information. */
551 bitmap_head open_chains_set
;
552 bitmap_head incoming_open_chains_set
;
553 struct incoming_reg_info incoming
[FIRST_PSEUDO_REGISTER
];
556 /* Initialize a rename_info structure P for basic block BB, which starts a new
559 init_rename_info (struct bb_rename_info
*p
, basic_block bb
)
563 HARD_REG_SET start_chains_set
;
566 bitmap_initialize (&p
->open_chains_set
, &bitmap_default_obstack
);
567 bitmap_initialize (&p
->incoming_open_chains_set
, &bitmap_default_obstack
);
570 bitmap_clear (&open_chains_set
);
572 CLEAR_HARD_REG_SET (live_in_chains
);
573 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_in (bb
));
574 FOR_EACH_ARTIFICIAL_DEF (def
, bb
->index
)
575 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
576 SET_HARD_REG_BIT (live_hard_regs
, DF_REF_REGNO (def
));
578 /* Open chains based on information from (at least one) predecessor
579 block. This gives us a chance later on to combine chains across
580 basic block boundaries. Inconsistencies (in access sizes) will
581 be caught normally and dealt with conservatively by disabling the
582 chain for renaming, and there is no risk of losing optimization
583 opportunities by opening chains either: if we did not open the
584 chains, we'd have to track the live register as a hard reg, and
585 we'd be unable to rename it in any case. */
586 CLEAR_HARD_REG_SET (start_chains_set
);
587 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
589 struct incoming_reg_info
*iri
= p
->incoming
+ i
;
590 if (iri
->nregs
> 0 && !iri
->unusable
591 && range_in_hard_reg_set_p (live_hard_regs
, i
, iri
->nregs
))
593 SET_HARD_REG_BIT (start_chains_set
, i
);
594 remove_range_from_hard_reg_set (&live_hard_regs
, i
, iri
->nregs
);
597 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
599 struct incoming_reg_info
*iri
= p
->incoming
+ i
;
600 if (TEST_HARD_REG_BIT (start_chains_set
, i
))
604 fprintf (dump_file
, "opening incoming chain\n");
605 chain
= create_new_chain (i
, iri
->nregs
, NULL
, NULL
, NO_REGS
);
606 bitmap_set_bit (&p
->incoming_open_chains_set
, chain
->id
);
611 /* Record in RI that the block corresponding to it has an incoming
612 live value, described by CHAIN. */
614 set_incoming_from_chain (struct bb_rename_info
*ri
, du_head_p chain
)
617 int incoming_nregs
= ri
->incoming
[chain
->regno
].nregs
;
620 /* If we've recorded the same information before, everything is fine. */
621 if (incoming_nregs
== chain
->nregs
)
624 fprintf (dump_file
, "reg %d/%d already recorded\n",
625 chain
->regno
, chain
->nregs
);
629 /* If we have no information for any of the involved registers, update
630 the incoming array. */
631 nregs
= chain
->nregs
;
633 if (ri
->incoming
[chain
->regno
+ nregs
].nregs
!= 0
634 || ri
->incoming
[chain
->regno
+ nregs
].unusable
)
638 nregs
= chain
->nregs
;
639 ri
->incoming
[chain
->regno
].nregs
= nregs
;
641 ri
->incoming
[chain
->regno
+ nregs
].nregs
= -nregs
;
643 fprintf (dump_file
, "recorded reg %d/%d\n",
644 chain
->regno
, chain
->nregs
);
648 /* There must be some kind of conflict. Prevent both the old and
649 new ranges from being used. */
650 if (incoming_nregs
< 0)
651 ri
->incoming
[chain
->regno
+ incoming_nregs
].unusable
= true;
652 for (i
= 0; i
< chain
->nregs
; i
++)
653 ri
->incoming
[chain
->regno
+ i
].unusable
= true;
656 /* Merge the two chains C1 and C2 so that all conflict information is
657 recorded and C1, and the id of C2 is changed to that of C1. */
659 merge_chains (du_head_p c1
, du_head_p c2
)
664 if (c2
->first
!= NULL
)
666 if (c1
->first
== NULL
)
667 c1
->first
= c2
->first
;
669 c1
->last
->next_use
= c2
->first
;
673 c2
->first
= c2
->last
= NULL
;
676 IOR_HARD_REG_SET (c1
->hard_conflicts
, c2
->hard_conflicts
);
677 bitmap_ior_into (&c1
->conflicts
, &c2
->conflicts
);
679 c1
->need_caller_save_reg
|= c2
->need_caller_save_reg
;
680 c1
->cannot_rename
|= c2
->cannot_rename
;
683 /* Analyze the current function and build chains for renaming. */
686 regrename_analyze (bitmap bb_mask
)
688 struct bb_rename_info
*rename_info
;
692 int *inverse_postorder
;
694 inverse_postorder
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
695 n_bbs
= pre_and_rev_post_order_compute (NULL
, inverse_postorder
, false);
697 /* Gather some information about the blocks in this function. */
698 rename_info
= XCNEWVEC (struct bb_rename_info
, n_basic_blocks_for_fn (cfun
));
700 FOR_EACH_BB_FN (bb
, cfun
)
702 struct bb_rename_info
*ri
= rename_info
+ i
;
704 if (bb_mask
!= NULL
&& !bitmap_bit_p (bb_mask
, bb
->index
))
712 id_to_chain
.create (0);
713 bitmap_initialize (&open_chains_set
, &bitmap_default_obstack
);
715 /* The order in which we visit blocks ensures that whenever
716 possible, we only process a block after at least one of its
717 predecessors, which provides a "seeding" effect to make the logic
718 in set_incoming_from_chain and init_rename_info useful. */
720 for (i
= 0; i
< n_bbs
; i
++)
722 basic_block bb1
= BASIC_BLOCK_FOR_FN (cfun
, inverse_postorder
[i
]);
723 struct bb_rename_info
*this_info
;
727 int old_length
= id_to_chain
.length ();
729 this_info
= (struct bb_rename_info
*) bb1
->aux
;
730 if (this_info
== NULL
)
734 fprintf (dump_file
, "\nprocessing block %d:\n", bb1
->index
);
736 init_rename_info (this_info
, bb1
);
738 success
= build_def_use (bb1
);
742 fprintf (dump_file
, "failed\n");
744 id_to_chain
.truncate (old_length
);
745 current_id
= old_length
;
746 bitmap_clear (&this_info
->incoming_open_chains_set
);
748 if (insn_rr
.exists ())
751 FOR_BB_INSNS (bb1
, insn
)
753 insn_rr_info
*p
= &insn_rr
[INSN_UID (insn
)];
761 dump_def_use_chain (old_length
);
762 bitmap_copy (&this_info
->open_chains_set
, &open_chains_set
);
764 /* Add successor blocks to the worklist if necessary, and record
765 data about our own open chains at the end of this block, which
766 will be used to pre-open chains when processing the successors. */
767 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
769 struct bb_rename_info
*dest_ri
;
770 struct du_head
*chain
;
773 fprintf (dump_file
, "successor block %d\n", e
->dest
->index
);
775 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
777 dest_ri
= (struct bb_rename_info
*)e
->dest
->aux
;
780 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
781 set_incoming_from_chain (dest_ri
, chain
);
785 free (inverse_postorder
);
787 /* Now, combine the chains data we have gathered across basic block
790 For every basic block, there may be chains open at the start, or at the
791 end. Rather than exclude them from renaming, we look for open chains
792 with matching registers at the other side of the CFG edge.
794 For a given chain using register R, open at the start of block B, we
795 must find an open chain using R on the other side of every edge leading
796 to B, if the register is live across this edge. In the code below,
797 N_PREDS_USED counts the number of edges where the register is live, and
798 N_PREDS_JOINED counts those where we found an appropriate chain for
801 We perform the analysis for both incoming and outgoing edges, but we
802 only need to merge once (in the second part, after verifying outgoing
804 FOR_EACH_BB_FN (bb
, cfun
)
806 struct bb_rename_info
*bb_ri
= (struct bb_rename_info
*) bb
->aux
;
814 fprintf (dump_file
, "processing bb %d in edges\n", bb
->index
);
816 EXECUTE_IF_SET_IN_BITMAP (&bb_ri
->incoming_open_chains_set
, 0, j
, bi
)
820 struct du_head
*chain
= regrename_chain_from_id (j
);
821 int n_preds_used
= 0, n_preds_joined
= 0;
823 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
825 struct bb_rename_info
*src_ri
;
829 bool success
= false;
831 REG_SET_TO_HARD_REG_SET (live
, df_get_live_out (e
->src
));
832 if (!range_overlaps_hard_reg_set_p (live
, chain
->regno
,
837 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
840 src_ri
= (struct bb_rename_info
*)e
->src
->aux
;
844 EXECUTE_IF_SET_IN_BITMAP (&src_ri
->open_chains_set
,
847 struct du_head
*outgoing_chain
= regrename_chain_from_id (k
);
849 if (outgoing_chain
->regno
== chain
->regno
850 && outgoing_chain
->nregs
== chain
->nregs
)
857 if (!success
&& dump_file
)
858 fprintf (dump_file
, "failure to match with pred block %d\n",
861 if (n_preds_joined
< n_preds_used
)
864 fprintf (dump_file
, "cannot rename chain %d\n", j
);
865 chain
->cannot_rename
= 1;
869 FOR_EACH_BB_FN (bb
, cfun
)
871 struct bb_rename_info
*bb_ri
= (struct bb_rename_info
*) bb
->aux
;
879 fprintf (dump_file
, "processing bb %d out edges\n", bb
->index
);
881 EXECUTE_IF_SET_IN_BITMAP (&bb_ri
->open_chains_set
, 0, j
, bi
)
885 struct du_head
*chain
= regrename_chain_from_id (j
);
886 int n_succs_used
= 0, n_succs_joined
= 0;
888 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
890 bool printed
= false;
891 struct bb_rename_info
*dest_ri
;
896 REG_SET_TO_HARD_REG_SET (live
, df_get_live_in (e
->dest
));
897 if (!range_overlaps_hard_reg_set_p (live
, chain
->regno
,
903 dest_ri
= (struct bb_rename_info
*)e
->dest
->aux
;
907 EXECUTE_IF_SET_IN_BITMAP (&dest_ri
->incoming_open_chains_set
,
910 struct du_head
*incoming_chain
= regrename_chain_from_id (k
);
912 if (incoming_chain
->regno
== chain
->regno
913 && incoming_chain
->nregs
== chain
->nregs
)
919 "merging blocks for edge %d -> %d\n",
920 e
->src
->index
, e
->dest
->index
);
923 " merging chains %d (->%d) and %d (->%d) [%s]\n",
924 k
, incoming_chain
->id
, j
, chain
->id
,
925 reg_names
[incoming_chain
->regno
]);
928 merge_chains (chain
, incoming_chain
);
934 if (n_succs_joined
< n_succs_used
)
937 fprintf (dump_file
, "cannot rename chain %d\n",
939 chain
->cannot_rename
= 1;
946 FOR_EACH_BB_FN (bb
, cfun
)
950 /* Attempt to replace all uses of the register in the chain beginning with
951 HEAD with REG. Returns true on success and false if the replacement is
952 rejected because the insns would not validate. The latter can happen
953 e.g. if a match_parallel predicate enforces restrictions on register
954 numbering in its subpatterns. */
957 regrename_do_replace (struct du_head
*head
, int reg
)
959 struct du_chain
*chain
;
960 unsigned int base_regno
= head
->regno
;
963 for (chain
= head
->first
; chain
; chain
= chain
->next_use
)
965 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
966 struct reg_attrs
*attr
= REG_ATTRS (*chain
->loc
);
967 int reg_ptr
= REG_POINTER (*chain
->loc
);
969 if (DEBUG_INSN_P (chain
->insn
) && REGNO (*chain
->loc
) != base_regno
)
970 validate_change (chain
->insn
, &(INSN_VAR_LOCATION_LOC (chain
->insn
)),
971 gen_rtx_UNKNOWN_VAR_LOC (), true);
974 validate_change (chain
->insn
, chain
->loc
,
975 gen_raw_REG (GET_MODE (*chain
->loc
), reg
), true);
976 if (regno
>= FIRST_PSEUDO_REGISTER
)
977 ORIGINAL_REGNO (*chain
->loc
) = regno
;
978 REG_ATTRS (*chain
->loc
) = attr
;
979 REG_POINTER (*chain
->loc
) = reg_ptr
;
983 if (!apply_change_group ())
986 mode
= GET_MODE (*head
->first
->loc
);
989 head
->nregs
= hard_regno_nregs
[reg
][mode
];
994 /* True if we found a register with a size mismatch, which means that we
995 can't track its lifetime accurately. If so, we abort the current block
997 static bool fail_current_block
;
999 /* Return true if OP is a reg for which all bits are set in PSET, false
1000 if all bits are clear.
1001 In other cases, set fail_current_block and return false. */
1004 verify_reg_in_set (rtx op
, HARD_REG_SET
*pset
)
1006 unsigned regno
, nregs
;
1007 bool all_live
, all_dead
;
1012 nregs
= REG_NREGS (op
);
1013 all_live
= all_dead
= true;
1015 if (TEST_HARD_REG_BIT (*pset
, regno
+ nregs
))
1019 if (!all_dead
&& !all_live
)
1021 fail_current_block
= true;
1027 /* Return true if OP is a reg that is being tracked already in some form.
1028 May set fail_current_block if it sees an unhandled case of overlap. */
1031 verify_reg_tracked (rtx op
)
1033 return (verify_reg_in_set (op
, &live_hard_regs
)
1034 || verify_reg_in_set (op
, &live_in_chains
));
1037 /* Called through note_stores. DATA points to a rtx_code, either SET or
1038 CLOBBER, which tells us which kind of rtx to look at. If we have a
1039 match, record the set register in live_hard_regs and in the hard_conflicts
1040 bitmap of open chains. */
1043 note_sets_clobbers (rtx x
, const_rtx set
, void *data
)
1045 enum rtx_code code
= *(enum rtx_code
*)data
;
1046 struct du_head
*chain
;
1048 if (GET_CODE (x
) == SUBREG
)
1050 if (!REG_P (x
) || GET_CODE (set
) != code
)
1052 /* There must not be pseudos at this point. */
1053 gcc_assert (HARD_REGISTER_P (x
));
1054 add_to_hard_reg_set (&live_hard_regs
, GET_MODE (x
), REGNO (x
));
1055 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
1056 add_to_hard_reg_set (&chain
->hard_conflicts
, GET_MODE (x
), REGNO (x
));
1060 scan_rtx_reg (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
1065 unsigned this_regno
= REGNO (x
);
1066 int this_nregs
= REG_NREGS (x
);
1068 if (action
== mark_write
)
1073 rtx pat
= PATTERN (insn
);
1075 c
= create_new_chain (this_regno
, this_nregs
, loc
, insn
, cl
);
1077 /* We try to tie chains in a move instruction for
1079 if (recog_data
.n_operands
== 2
1080 && GET_CODE (pat
) == SET
1081 && GET_CODE (SET_DEST (pat
)) == REG
1082 && GET_CODE (SET_SRC (pat
)) == REG
1083 && terminated_this_insn
1084 && terminated_this_insn
->nregs
1085 == REG_NREGS (recog_data
.operand
[1]))
1087 gcc_assert (terminated_this_insn
->regno
1088 == REGNO (recog_data
.operand
[1]));
1090 c
->tied_chain
= terminated_this_insn
;
1091 terminated_this_insn
->tied_chain
= c
;
1094 fprintf (dump_file
, "Tying chain %s (%d) with %s (%d)\n",
1095 reg_names
[c
->regno
], c
->id
,
1096 reg_names
[terminated_this_insn
->regno
],
1097 terminated_this_insn
->id
);
1104 if ((type
== OP_OUT
) != (action
== terminate_write
|| action
== mark_access
))
1107 for (p
= &open_chains
; *p
;)
1109 struct du_head
*head
= *p
;
1110 struct du_head
*next
= head
->next_chain
;
1111 int exact_match
= (head
->regno
== this_regno
1112 && head
->nregs
== this_nregs
);
1113 int superset
= (this_regno
<= head
->regno
1114 && this_regno
+ this_nregs
>= head
->regno
+ head
->nregs
);
1115 int subset
= (this_regno
>= head
->regno
1116 && this_regno
+ this_nregs
<= head
->regno
+ head
->nregs
);
1118 if (!bitmap_bit_p (&open_chains_set
, head
->id
)
1119 || head
->regno
+ head
->nregs
<= this_regno
1120 || this_regno
+ this_nregs
<= head
->regno
)
1122 p
= &head
->next_chain
;
1126 if (action
== mark_read
|| action
== mark_access
)
1128 /* ??? Class NO_REGS can happen if the md file makes use of
1129 EXTRA_CONSTRAINTS to match registers. Which is arguably
1130 wrong, but there we are. */
1132 if (cl
== NO_REGS
|| (!exact_match
&& !DEBUG_INSN_P (insn
)))
1136 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1137 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1138 scan_actions_name
[(int) action
]);
1139 head
->cannot_rename
= 1;
1142 unsigned nregs
= this_nregs
;
1143 head
->regno
= this_regno
;
1144 head
->nregs
= this_nregs
;
1146 SET_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
1149 "Widening register in chain %s (%d) at insn %d\n",
1150 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
));
1154 fail_current_block
= true;
1157 "Failing basic block due to unhandled overlap\n");
1162 struct du_chain
*this_du
;
1163 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
1164 this_du
->next_use
= 0;
1166 this_du
->insn
= insn
;
1168 if (head
->first
== NULL
)
1169 head
->first
= this_du
;
1171 head
->last
->next_use
= this_du
;
1172 record_operand_use (head
, this_du
);
1173 head
->last
= this_du
;
1175 /* Avoid adding the same location in a DEBUG_INSN multiple times,
1176 which could happen with non-exact overlap. */
1177 if (DEBUG_INSN_P (insn
))
1179 /* Otherwise, find any other chains that do not match exactly;
1180 ensure they all get marked unrenamable. */
1181 p
= &head
->next_chain
;
1185 /* Whether the terminated chain can be used for renaming
1186 depends on the action and this being an exact match.
1187 In either case, we remove this element from open_chains. */
1189 if ((action
== terminate_dead
|| action
== terminate_write
)
1190 && (superset
|| subset
))
1194 if (subset
&& !superset
)
1195 head
->cannot_rename
= 1;
1196 bitmap_clear_bit (&open_chains_set
, head
->id
);
1198 nregs
= head
->nregs
;
1201 CLEAR_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
1202 if (subset
&& !superset
1203 && (head
->regno
+ nregs
< this_regno
1204 || head
->regno
+ nregs
>= this_regno
+ this_nregs
))
1205 SET_HARD_REG_BIT (live_hard_regs
, head
->regno
+ nregs
);
1208 if (action
== terminate_dead
)
1209 terminated_this_insn
= *p
;
1213 "Closing chain %s (%d) at insn %d (%s%s)\n",
1214 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1215 scan_actions_name
[(int) action
],
1216 superset
? ", superset" : subset
? ", subset" : "");
1218 else if (action
== terminate_dead
|| action
== terminate_write
)
1220 /* In this case, tracking liveness gets too hard. Fail the
1221 entire basic block. */
1224 "Failing basic block due to unhandled overlap\n");
1225 fail_current_block
= true;
1230 head
->cannot_rename
= 1;
1233 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1234 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1235 scan_actions_name
[(int) action
]);
1236 p
= &head
->next_chain
;
1241 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1242 BASE_REG_CLASS depending on how the register is being considered. */
1245 scan_rtx_address (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
,
1246 enum scan_actions action
, machine_mode mode
,
1250 RTX_CODE code
= GET_CODE (x
);
1254 if (action
== mark_write
|| action
== mark_access
)
1261 rtx orig_op0
= XEXP (x
, 0);
1262 rtx orig_op1
= XEXP (x
, 1);
1263 RTX_CODE code0
= GET_CODE (orig_op0
);
1264 RTX_CODE code1
= GET_CODE (orig_op1
);
1269 enum rtx_code index_code
= SCRATCH
;
1271 if (GET_CODE (op0
) == SUBREG
)
1273 op0
= SUBREG_REG (op0
);
1274 code0
= GET_CODE (op0
);
1277 if (GET_CODE (op1
) == SUBREG
)
1279 op1
= SUBREG_REG (op1
);
1280 code1
= GET_CODE (op1
);
1283 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
1284 || code0
== ZERO_EXTEND
|| code1
== MEM
)
1286 locI
= &XEXP (x
, 0);
1287 locB
= &XEXP (x
, 1);
1288 index_code
= GET_CODE (*locI
);
1290 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
1291 || code1
== ZERO_EXTEND
|| code0
== MEM
)
1293 locI
= &XEXP (x
, 1);
1294 locB
= &XEXP (x
, 0);
1295 index_code
= GET_CODE (*locI
);
1297 else if (code0
== CONST_INT
|| code0
== CONST
1298 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
1300 locB
= &XEXP (x
, 1);
1301 index_code
= GET_CODE (XEXP (x
, 0));
1303 else if (code1
== CONST_INT
|| code1
== CONST
1304 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
1306 locB
= &XEXP (x
, 0);
1307 index_code
= GET_CODE (XEXP (x
, 1));
1309 else if (code0
== REG
&& code1
== REG
)
1312 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
1314 if (REGNO_OK_FOR_INDEX_P (regno1
)
1315 && regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
))
1317 else if (REGNO_OK_FOR_INDEX_P (regno0
)
1318 && regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
1320 else if (regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
)
1321 || REGNO_OK_FOR_INDEX_P (regno1
))
1323 else if (regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
1328 locI
= &XEXP (x
, index_op
);
1329 locB
= &XEXP (x
, !index_op
);
1330 index_code
= GET_CODE (*locI
);
1332 else if (code0
== REG
)
1334 locI
= &XEXP (x
, 0);
1335 locB
= &XEXP (x
, 1);
1336 index_code
= GET_CODE (*locI
);
1338 else if (code1
== REG
)
1340 locI
= &XEXP (x
, 1);
1341 locB
= &XEXP (x
, 0);
1342 index_code
= GET_CODE (*locI
);
1346 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
, as
);
1348 scan_rtx_address (insn
, locB
,
1349 base_reg_class (mode
, as
, PLUS
, index_code
),
1361 /* If the target doesn't claim to handle autoinc, this must be
1362 something special, like a stack push. Kill this chain. */
1364 action
= mark_all_read
;
1369 scan_rtx_address (insn
, &XEXP (x
, 0),
1370 base_reg_class (GET_MODE (x
), MEM_ADDR_SPACE (x
),
1372 action
, GET_MODE (x
), MEM_ADDR_SPACE (x
));
1376 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
);
1383 fmt
= GET_RTX_FORMAT (code
);
1384 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1387 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
, as
);
1388 else if (fmt
[i
] == 'E')
1389 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1390 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
, as
);
1395 scan_rtx (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
1400 enum rtx_code code
= GET_CODE (x
);
1403 code
= GET_CODE (x
);
1415 scan_rtx_reg (insn
, loc
, cl
, action
, type
);
1419 scan_rtx_address (insn
, &XEXP (x
, 0),
1420 base_reg_class (GET_MODE (x
), MEM_ADDR_SPACE (x
),
1422 action
, GET_MODE (x
), MEM_ADDR_SPACE (x
));
1426 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
);
1427 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
1428 (GET_CODE (PATTERN (insn
)) == COND_EXEC
1429 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
1432 case STRICT_LOW_PART
:
1433 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
1434 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
);
1439 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
1440 (type
== OP_IN
? OP_IN
:
1441 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
));
1442 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
);
1443 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
);
1452 /* Should only happen inside MEM. */
1456 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
1457 (GET_CODE (PATTERN (insn
)) == COND_EXEC
1458 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
1462 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
);
1464 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
);
1471 fmt
= GET_RTX_FORMAT (code
);
1472 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1475 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
);
1476 else if (fmt
[i
] == 'E')
1477 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1478 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
);
1482 /* Hide operands of the current insn (of which there are N_OPS) by
1483 substituting cc0 for them.
1484 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
1485 For every bit set in DO_NOT_HIDE, we leave the operand alone.
1486 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
1487 and earlyclobbers. */
1490 hide_operands (int n_ops
, rtx
*old_operands
, rtx
*old_dups
,
1491 unsigned HOST_WIDE_INT do_not_hide
, bool inout_and_ec_only
)
1494 const operand_alternative
*op_alt
= which_op_alt ();
1495 for (i
= 0; i
< n_ops
; i
++)
1497 old_operands
[i
] = recog_data
.operand
[i
];
1498 /* Don't squash match_operator or match_parallel here, since
1499 we don't know that all of the contained registers are
1500 reachable by proper operands. */
1501 if (recog_data
.constraints
[i
][0] == '\0')
1503 if (do_not_hide
& (1 << i
))
1505 if (!inout_and_ec_only
|| recog_data
.operand_type
[i
] == OP_INOUT
1506 || op_alt
[i
].earlyclobber
)
1507 *recog_data
.operand_loc
[i
] = cc0_rtx
;
1509 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1511 int opn
= recog_data
.dup_num
[i
];
1512 old_dups
[i
] = *recog_data
.dup_loc
[i
];
1513 if (do_not_hide
& (1 << opn
))
1515 if (!inout_and_ec_only
|| recog_data
.operand_type
[opn
] == OP_INOUT
1516 || op_alt
[opn
].earlyclobber
)
1517 *recog_data
.dup_loc
[i
] = cc0_rtx
;
1521 /* Undo the substitution performed by hide_operands. INSN is the insn we
1522 are processing; the arguments are the same as in hide_operands. */
1525 restore_operands (rtx_insn
*insn
, int n_ops
, rtx
*old_operands
, rtx
*old_dups
)
1528 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1529 *recog_data
.dup_loc
[i
] = old_dups
[i
];
1530 for (i
= 0; i
< n_ops
; i
++)
1531 *recog_data
.operand_loc
[i
] = old_operands
[i
];
1532 if (recog_data
.n_dups
)
1533 df_insn_rescan (insn
);
1536 /* For each output operand of INSN, call scan_rtx to create a new
1537 open chain. Do this only for normal or earlyclobber outputs,
1538 depending on EARLYCLOBBER. If INSN_INFO is nonnull, use it to
1539 record information about the operands in the insn. */
1542 record_out_operands (rtx_insn
*insn
, bool earlyclobber
, insn_rr_info
*insn_info
)
1544 int n_ops
= recog_data
.n_operands
;
1545 const operand_alternative
*op_alt
= which_op_alt ();
1549 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1551 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1552 rtx
*loc
= (i
< n_ops
1553 ? recog_data
.operand_loc
[opn
]
1554 : recog_data
.dup_loc
[i
- n_ops
]);
1556 enum reg_class cl
= alternative_class (op_alt
, opn
);
1558 struct du_head
*prev_open
;
1560 if (recog_data
.operand_type
[opn
] != OP_OUT
1561 || op_alt
[opn
].earlyclobber
!= earlyclobber
)
1565 cur_operand
= insn_info
->op_info
+ i
;
1567 prev_open
= open_chains
;
1569 scan_rtx (insn
, loc
, cl
, terminate_write
, OP_OUT
);
1570 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
);
1572 /* ??? Many targets have output constraints on the SET_DEST
1573 of a call insn, which is stupid, since these are certainly
1574 ABI defined hard registers. For these, and for asm operands
1575 that originally referenced hard registers, we must record that
1576 the chain cannot be renamed. */
1578 || (asm_noperands (PATTERN (insn
)) > 0
1580 && REGNO (op
) == ORIGINAL_REGNO (op
)))
1582 if (prev_open
!= open_chains
)
1583 open_chains
->cannot_rename
= 1;
1589 /* Build def/use chain. */
1592 build_def_use (basic_block bb
)
1595 unsigned HOST_WIDE_INT untracked_operands
;
1597 fail_current_block
= false;
1599 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1601 if (NONDEBUG_INSN_P (insn
))
1605 rtx old_operands
[MAX_RECOG_OPERANDS
];
1606 rtx old_dups
[MAX_DUP_OPERANDS
];
1609 enum rtx_code set_code
= SET
;
1610 enum rtx_code clobber_code
= CLOBBER
;
1611 insn_rr_info
*insn_info
= NULL
;
1612 terminated_this_insn
= NULL
;
1614 /* Process the insn, determining its effect on the def-use
1615 chains and live hard registers. We perform the following
1616 steps with the register references in the insn, simulating
1618 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1619 by creating chains and marking hard regs live.
1620 (2) Any read outside an operand causes any chain it overlaps
1621 with to be marked unrenamable.
1622 (3) Any read inside an operand is added if there's already
1623 an open chain for it.
1624 (4) For any REG_DEAD note we find, close open chains that
1626 (5) For any non-earlyclobber write we find, close open chains
1628 (6) For any non-earlyclobber write we find in an operand, make
1629 a new chain or mark the hard register as live.
1630 (7) For any REG_UNUSED, close any chains we just opened.
1632 We cannot deal with situations where we track a reg in one mode
1633 and see a reference in another mode; these will cause the chain
1634 to be marked unrenamable or even cause us to abort the entire
1637 extract_constrain_insn (insn
);
1638 preprocess_constraints (insn
);
1639 const operand_alternative
*op_alt
= which_op_alt ();
1640 n_ops
= recog_data
.n_operands
;
1641 untracked_operands
= 0;
1643 if (insn_rr
.exists ())
1645 insn_info
= &insn_rr
[INSN_UID (insn
)];
1646 insn_info
->op_info
= XOBNEWVEC (&rename_obstack
, operand_rr_info
,
1647 recog_data
.n_operands
);
1648 memset (insn_info
->op_info
, 0,
1649 sizeof (operand_rr_info
) * recog_data
.n_operands
);
1652 /* Simplify the code below by promoting OP_OUT to OP_INOUT in
1653 predicated instructions, but only for register operands
1654 that are already tracked, so that we can create a chain
1655 when the first SET makes a register live. */
1657 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1658 for (i
= 0; i
< n_ops
; ++i
)
1660 rtx op
= recog_data
.operand
[i
];
1661 int matches
= op_alt
[i
].matches
;
1662 if (matches
>= 0 || op_alt
[i
].matched
>= 0
1663 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1665 recog_data
.operand_type
[i
] = OP_INOUT
;
1666 /* A special case to deal with instruction patterns that
1667 have matching operands with different modes. If we're
1668 not already tracking such a reg, we won't start here,
1669 and we must instead make sure to make the operand visible
1670 to the machinery that tracks hard registers. */
1672 && (GET_MODE_SIZE (recog_data
.operand_mode
[i
])
1673 != GET_MODE_SIZE (recog_data
.operand_mode
[matches
]))
1674 && !verify_reg_in_set (op
, &live_in_chains
))
1676 untracked_operands
|= 1 << i
;
1677 untracked_operands
|= 1 << matches
;
1681 if (regstack_completed
1683 && IN_RANGE (REGNO (op
), FIRST_STACK_REG
, LAST_STACK_REG
))
1684 untracked_operands
|= 1 << i
;
1686 /* If there's an in-out operand with a register that is not
1687 being tracked at all yet, open a chain. */
1688 if (recog_data
.operand_type
[i
] == OP_INOUT
1689 && !(untracked_operands
& (1 << i
))
1691 && !verify_reg_tracked (op
))
1692 create_new_chain (REGNO (op
), REG_NREGS (op
), NULL
, NULL
,
1696 if (fail_current_block
)
1699 /* Step 1a: Mark hard registers that are clobbered in this insn,
1700 outside an operand, as live. */
1701 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1703 note_stores (PATTERN (insn
), note_sets_clobbers
, &clobber_code
);
1704 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1706 /* Step 1b: Begin new chains for earlyclobbered writes inside
1708 record_out_operands (insn
, true, insn_info
);
1710 /* Step 2: Mark chains for which we have reads outside operands
1712 We do this by munging all operands into CC0, and closing
1713 everything remaining. */
1715 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1717 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, mark_all_read
, OP_IN
);
1718 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1720 /* Step 2B: Can't rename function call argument registers. */
1721 if (CALL_P (insn
) && CALL_INSN_FUNCTION_USAGE (insn
))
1722 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
1723 NO_REGS
, mark_all_read
, OP_IN
);
1725 /* Step 2C: Can't rename asm operands that were originally
1727 if (asm_noperands (PATTERN (insn
)) > 0)
1728 for (i
= 0; i
< n_ops
; i
++)
1730 rtx
*loc
= recog_data
.operand_loc
[i
];
1734 && REGNO (op
) == ORIGINAL_REGNO (op
)
1735 && (recog_data
.operand_type
[i
] == OP_IN
1736 || recog_data
.operand_type
[i
] == OP_INOUT
))
1737 scan_rtx (insn
, loc
, NO_REGS
, mark_all_read
, OP_IN
);
1740 /* Step 3: Append to chains for reads inside operands. */
1741 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1743 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1744 rtx
*loc
= (i
< n_ops
1745 ? recog_data
.operand_loc
[opn
]
1746 : recog_data
.dup_loc
[i
- n_ops
]);
1747 enum reg_class cl
= alternative_class (op_alt
, opn
);
1748 enum op_type type
= recog_data
.operand_type
[opn
];
1750 /* Don't scan match_operand here, since we've no reg class
1751 information to pass down. Any operands that we could
1752 substitute in will be represented elsewhere. */
1753 if (recog_data
.constraints
[opn
][0] == '\0'
1754 || untracked_operands
& (1 << opn
))
1758 cur_operand
= i
== opn
? insn_info
->op_info
+ i
: NULL
;
1759 if (op_alt
[opn
].is_address
)
1760 scan_rtx_address (insn
, loc
, cl
, mark_read
,
1761 VOIDmode
, ADDR_SPACE_GENERIC
);
1763 scan_rtx (insn
, loc
, cl
, mark_read
, type
);
1767 /* Step 3B: Record updates for regs in REG_INC notes, and
1768 source regs in REG_FRAME_RELATED_EXPR notes. */
1769 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1770 if (REG_NOTE_KIND (note
) == REG_INC
1771 || REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1772 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
1775 /* Step 4: Close chains for registers that die here, unless
1776 the register is mentioned in a REG_UNUSED note. In that
1777 case we keep the chain open until step #7 below to ensure
1778 it conflicts with other output operands of this insn.
1779 See PR 52573. Arguably the insn should not have both
1780 notes; it has proven difficult to fix that without
1781 other undesirable side effects. */
1782 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1783 if (REG_NOTE_KIND (note
) == REG_DEAD
1784 && !find_regno_note (insn
, REG_UNUSED
, REGNO (XEXP (note
, 0))))
1786 remove_from_hard_reg_set (&live_hard_regs
,
1787 GET_MODE (XEXP (note
, 0)),
1788 REGNO (XEXP (note
, 0)));
1789 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1793 /* Step 4B: If this is a call, any chain live at this point
1794 requires a caller-saved reg. */
1798 for (p
= open_chains
; p
; p
= p
->next_chain
)
1799 p
->need_caller_save_reg
= 1;
1802 /* Step 5: Close open chains that overlap writes. Similar to
1803 step 2, we hide in-out operands, since we do not want to
1804 close these chains. We also hide earlyclobber operands,
1805 since we've opened chains for them in step 1, and earlier
1806 chains they would overlap with must have been closed at
1807 the previous insn at the latest, as such operands cannot
1808 possibly overlap with any input operands. */
1810 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1812 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
);
1813 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1815 /* Step 6a: Mark hard registers that are set in this insn,
1816 outside an operand, as live. */
1817 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1819 note_stores (PATTERN (insn
), note_sets_clobbers
, &set_code
);
1820 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1822 /* Step 6b: Begin new chains for writes inside operands. */
1823 record_out_operands (insn
, false, insn_info
);
1825 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1826 notes for update. */
1827 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1828 if (REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1829 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_access
,
1832 /* Step 7: Close chains for registers that were never
1833 really used here. */
1834 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1835 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
1837 remove_from_hard_reg_set (&live_hard_regs
,
1838 GET_MODE (XEXP (note
, 0)),
1839 REGNO (XEXP (note
, 0)));
1840 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1844 else if (DEBUG_INSN_P (insn
)
1845 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn
)))
1847 scan_rtx (insn
, &INSN_VAR_LOCATION_LOC (insn
),
1848 ALL_REGS
, mark_read
, OP_IN
);
1850 if (insn
== BB_END (bb
))
1854 if (fail_current_block
)
1860 /* Initialize the register renamer. If INSN_INFO is true, ensure that
1861 insn_rr is nonnull. */
1863 regrename_init (bool insn_info
)
1865 gcc_obstack_init (&rename_obstack
);
1868 insn_rr
.safe_grow_cleared (get_max_uid ());
1871 /* Free all global data used by the register renamer. */
1873 regrename_finish (void)
1877 obstack_free (&rename_obstack
, NULL
);
1880 /* Perform register renaming on the current function. */
1883 regrename_optimize (void)
1885 df_set_flags (DF_LR_RUN_DCE
);
1886 df_note_add_problem ();
1888 df_set_flags (DF_DEFER_INSN_RESCAN
);
1890 regrename_init (false);
1892 regrename_analyze (NULL
);
1896 regrename_finish ();
1903 const pass_data pass_data_regrename
=
1905 RTL_PASS
, /* type */
1907 OPTGROUP_NONE
, /* optinfo_flags */
1908 TV_RENAME_REGISTERS
, /* tv_id */
1909 0, /* properties_required */
1910 0, /* properties_provided */
1911 0, /* properties_destroyed */
1912 0, /* todo_flags_start */
1913 TODO_df_finish
, /* todo_flags_finish */
1916 class pass_regrename
: public rtl_opt_pass
1919 pass_regrename (gcc::context
*ctxt
)
1920 : rtl_opt_pass (pass_data_regrename
, ctxt
)
1923 /* opt_pass methods: */
1924 virtual bool gate (function
*)
1926 return (optimize
> 0 && (flag_rename_registers
));
1929 virtual unsigned int execute (function
*) { return regrename_optimize (); }
1931 }; // class pass_regrename
1936 make_pass_regrename (gcc::context
*ctxt
)
1938 return new pass_regrename (ctxt
);