1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000-2015 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
)
208 gcc_assert (cur_operand
->n_chains
< MAX_REGS_PER_ADDRESS
);
209 cur_operand
->heads
[cur_operand
->n_chains
] = head
;
210 cur_operand
->chains
[cur_operand
->n_chains
++] = this_du
;
213 /* Create a new chain for THIS_NREGS registers starting at THIS_REGNO,
214 and record its occurrence in *LOC, which is being written to in INSN.
215 This access requires a register of class CL. */
218 create_new_chain (unsigned this_regno
, unsigned this_nregs
, rtx
*loc
,
219 rtx_insn
*insn
, enum reg_class cl
)
221 struct du_head
*head
= XOBNEW (&rename_obstack
, struct du_head
);
222 struct du_chain
*this_du
;
225 head
->next_chain
= open_chains
;
226 head
->regno
= this_regno
;
227 head
->nregs
= this_nregs
;
228 head
->need_caller_save_reg
= 0;
229 head
->cannot_rename
= 0;
231 head
->tied_chain
= NULL
;
233 id_to_chain
.safe_push (head
);
234 head
->id
= current_id
++;
236 bitmap_initialize (&head
->conflicts
, &bitmap_default_obstack
);
237 bitmap_copy (&head
->conflicts
, &open_chains_set
);
238 mark_conflict (open_chains
, head
->id
);
240 /* Since we're tracking this as a chain now, remove it from the
241 list of conflicting live hard registers and track it in
242 live_in_chains instead. */
246 SET_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
247 CLEAR_HARD_REG_BIT (live_hard_regs
, head
->regno
+ nregs
);
250 COPY_HARD_REG_SET (head
->hard_conflicts
, live_hard_regs
);
251 bitmap_set_bit (&open_chains_set
, head
->id
);
257 fprintf (dump_file
, "Creating chain %s (%d)",
258 reg_names
[head
->regno
], head
->id
);
259 if (insn
!= NULL_RTX
)
260 fprintf (dump_file
, " at insn %d", INSN_UID (insn
));
261 fprintf (dump_file
, "\n");
264 if (insn
== NULL_RTX
)
266 head
->first
= head
->last
= NULL
;
270 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
271 head
->first
= head
->last
= this_du
;
273 this_du
->next_use
= 0;
275 this_du
->insn
= insn
;
277 record_operand_use (head
, this_du
);
281 /* For a def-use chain HEAD, find which registers overlap its lifetime and
282 set the corresponding bits in *PSET. */
285 merge_overlapping_regs (HARD_REG_SET
*pset
, struct du_head
*head
)
289 IOR_HARD_REG_SET (*pset
, head
->hard_conflicts
);
290 EXECUTE_IF_SET_IN_BITMAP (&head
->conflicts
, 0, i
, bi
)
292 du_head_p other
= regrename_chain_from_id (i
);
293 unsigned j
= other
->nregs
;
294 gcc_assert (other
!= head
);
296 SET_HARD_REG_BIT (*pset
, other
->regno
+ j
);
300 /* Check if NEW_REG can be the candidate register to rename for
301 REG in THIS_HEAD chain. THIS_UNAVAILABLE is a set of unavailable hard
305 check_new_reg_p (int reg ATTRIBUTE_UNUSED
, int new_reg
,
306 struct du_head
*this_head
, HARD_REG_SET this_unavailable
)
308 machine_mode mode
= GET_MODE (*this_head
->first
->loc
);
309 int nregs
= hard_regno_nregs
[new_reg
][mode
];
311 struct du_chain
*tmp
;
313 for (i
= nregs
- 1; i
>= 0; --i
)
314 if (TEST_HARD_REG_BIT (this_unavailable
, new_reg
+ i
)
315 || fixed_regs
[new_reg
+ i
]
316 || global_regs
[new_reg
+ i
]
317 /* Can't use regs which aren't saved by the prologue. */
318 || (! df_regs_ever_live_p (new_reg
+ i
)
319 && ! call_used_regs
[new_reg
+ i
])
320 #ifdef LEAF_REGISTERS
321 /* We can't use a non-leaf register if we're in a
324 && !LEAF_REGISTERS
[new_reg
+ i
])
326 || ! HARD_REGNO_RENAME_OK (reg
+ i
, new_reg
+ i
))
329 /* See whether it accepts all modes that occur in
330 definition and uses. */
331 for (tmp
= this_head
->first
; tmp
; tmp
= tmp
->next_use
)
332 if ((! HARD_REGNO_MODE_OK (new_reg
, GET_MODE (*tmp
->loc
))
333 && ! DEBUG_INSN_P (tmp
->insn
))
334 || (this_head
->need_caller_save_reg
335 && ! (HARD_REGNO_CALL_PART_CLOBBERED
336 (reg
, GET_MODE (*tmp
->loc
)))
337 && (HARD_REGNO_CALL_PART_CLOBBERED
338 (new_reg
, GET_MODE (*tmp
->loc
)))))
344 /* For the chain THIS_HEAD, compute and return the best register to
345 rename to. SUPER_CLASS is the superunion of register classes in
346 the chain. UNAVAILABLE is a set of registers that cannot be used.
347 OLD_REG is the register currently used for the chain. BEST_RENAME
348 controls whether the register chosen must be better than the
349 current one or just respect the given constraint. */
352 find_rename_reg (du_head_p this_head
, enum reg_class super_class
,
353 HARD_REG_SET
*unavailable
, int old_reg
, bool best_rename
)
355 bool has_preferred_class
;
356 enum reg_class preferred_class
;
358 int best_new_reg
= old_reg
;
360 /* Further narrow the set of registers we can use for renaming.
361 If the chain needs a call-saved register, mark the call-used
362 registers as unavailable. */
363 if (this_head
->need_caller_save_reg
)
364 IOR_HARD_REG_SET (*unavailable
, call_used_reg_set
);
366 /* Mark registers that overlap this chain's lifetime as unavailable. */
367 merge_overlapping_regs (unavailable
, this_head
);
369 /* Compute preferred rename class of super union of all the classes
372 = (enum reg_class
) targetm
.preferred_rename_class (super_class
);
374 /* Pick and check the register from the tied chain iff the tied chain
376 if (this_head
->tied_chain
&& !this_head
->tied_chain
->renamed
377 && check_new_reg_p (old_reg
, this_head
->tied_chain
->regno
,
378 this_head
, *unavailable
))
379 return this_head
->tied_chain
->regno
;
381 /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
382 over registers that belong to PREFERRED_CLASS and try to find the
383 best register within the class. If that failed, we iterate in
384 the second pass over registers that don't belong to the class.
385 If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
386 ascending order without any preference. */
387 has_preferred_class
= (preferred_class
!= NO_REGS
);
388 for (pass
= (has_preferred_class
? 0 : 1); pass
< 2; pass
++)
391 for (new_reg
= 0; new_reg
< FIRST_PSEUDO_REGISTER
; new_reg
++)
393 if (has_preferred_class
395 != TEST_HARD_REG_BIT (reg_class_contents
[preferred_class
],
399 if (!check_new_reg_p (old_reg
, new_reg
, this_head
, *unavailable
))
405 /* In the first pass, we force the renaming of registers that
406 don't belong to PREFERRED_CLASS to registers that do, even
407 though the latters were used not very long ago. */
409 && !TEST_HARD_REG_BIT (reg_class_contents
[preferred_class
],
411 || tick
[best_new_reg
] > tick
[new_reg
])
412 best_new_reg
= new_reg
;
414 if (pass
== 0 && best_new_reg
!= old_reg
)
420 /* Perform register renaming on the current function. */
424 HARD_REG_SET unavailable
;
428 memset (tick
, 0, sizeof tick
);
430 CLEAR_HARD_REG_SET (unavailable
);
431 /* Don't clobber traceback for noreturn functions. */
432 if (frame_pointer_needed
)
434 add_to_hard_reg_set (&unavailable
, Pmode
, FRAME_POINTER_REGNUM
);
435 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
)
436 add_to_hard_reg_set (&unavailable
, Pmode
, HARD_FRAME_POINTER_REGNUM
);
439 FOR_EACH_VEC_ELT (id_to_chain
, i
, this_head
)
443 struct du_chain
*tmp
;
444 HARD_REG_SET this_unavailable
;
445 int reg
= this_head
->regno
;
446 enum reg_class super_class
= NO_REGS
;
448 if (this_head
->cannot_rename
)
451 if (fixed_regs
[reg
] || global_regs
[reg
]
452 || (!HARD_FRAME_POINTER_IS_FRAME_POINTER
&& frame_pointer_needed
453 && reg
== HARD_FRAME_POINTER_REGNUM
)
454 || (HARD_FRAME_POINTER_REGNUM
&& frame_pointer_needed
455 && reg
== FRAME_POINTER_REGNUM
))
458 COPY_HARD_REG_SET (this_unavailable
, unavailable
);
460 /* Iterate over elements in the chain in order to:
461 1. Count number of uses, and narrow the set of registers we can
463 2. Compute the superunion of register classes in this chain. */
465 super_class
= NO_REGS
;
466 for (tmp
= this_head
->first
; tmp
; tmp
= tmp
->next_use
)
468 if (DEBUG_INSN_P (tmp
->insn
))
471 IOR_COMPL_HARD_REG_SET (this_unavailable
,
472 reg_class_contents
[tmp
->cl
]);
474 = reg_class_superunion
[(int) super_class
][(int) tmp
->cl
];
480 best_new_reg
= find_rename_reg (this_head
, super_class
,
481 &this_unavailable
, reg
, true);
485 fprintf (dump_file
, "Register %s in insn %d",
486 reg_names
[reg
], INSN_UID (this_head
->first
->insn
));
487 if (this_head
->need_caller_save_reg
)
488 fprintf (dump_file
, " crosses a call");
491 if (best_new_reg
== reg
)
493 tick
[reg
] = ++this_tick
;
495 fprintf (dump_file
, "; no available better choice\n");
499 if (regrename_do_replace (this_head
, best_new_reg
))
502 fprintf (dump_file
, ", renamed as %s\n", reg_names
[best_new_reg
]);
503 tick
[best_new_reg
] = ++this_tick
;
504 df_set_regs_ever_live (best_new_reg
, true);
509 fprintf (dump_file
, ", renaming as %s failed\n",
510 reg_names
[best_new_reg
]);
511 tick
[reg
] = ++this_tick
;
516 /* A structure to record information for each hard register at the start of
518 struct incoming_reg_info
{
519 /* Holds the number of registers used in the chain that gave us information
520 about this register. Zero means no information known yet, while a
521 negative value is used for something that is part of, but not the first
522 register in a multi-register value. */
524 /* Set to true if we have accesses that conflict in the number of registers
529 /* A structure recording information about each basic block. It is saved
530 and restored around basic block boundaries.
531 A pointer to such a structure is stored in each basic block's aux field
532 during regrename_analyze, except for blocks we know can't be optimized
533 (such as entry and exit blocks). */
534 struct bb_rename_info
536 /* The basic block corresponding to this structure. */
538 /* Copies of the global information. */
539 bitmap_head open_chains_set
;
540 bitmap_head incoming_open_chains_set
;
541 struct incoming_reg_info incoming
[FIRST_PSEUDO_REGISTER
];
544 /* Initialize a rename_info structure P for basic block BB, which starts a new
547 init_rename_info (struct bb_rename_info
*p
, basic_block bb
)
551 HARD_REG_SET start_chains_set
;
554 bitmap_initialize (&p
->open_chains_set
, &bitmap_default_obstack
);
555 bitmap_initialize (&p
->incoming_open_chains_set
, &bitmap_default_obstack
);
558 bitmap_clear (&open_chains_set
);
560 CLEAR_HARD_REG_SET (live_in_chains
);
561 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_in (bb
));
562 FOR_EACH_ARTIFICIAL_DEF (def
, bb
->index
)
563 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
564 SET_HARD_REG_BIT (live_hard_regs
, DF_REF_REGNO (def
));
566 /* Open chains based on information from (at least one) predecessor
567 block. This gives us a chance later on to combine chains across
568 basic block boundaries. Inconsistencies (in access sizes) will
569 be caught normally and dealt with conservatively by disabling the
570 chain for renaming, and there is no risk of losing optimization
571 opportunities by opening chains either: if we did not open the
572 chains, we'd have to track the live register as a hard reg, and
573 we'd be unable to rename it in any case. */
574 CLEAR_HARD_REG_SET (start_chains_set
);
575 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
577 struct incoming_reg_info
*iri
= p
->incoming
+ i
;
578 if (iri
->nregs
> 0 && !iri
->unusable
579 && range_in_hard_reg_set_p (live_hard_regs
, i
, iri
->nregs
))
581 SET_HARD_REG_BIT (start_chains_set
, i
);
582 remove_range_from_hard_reg_set (&live_hard_regs
, i
, iri
->nregs
);
585 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
587 struct incoming_reg_info
*iri
= p
->incoming
+ i
;
588 if (TEST_HARD_REG_BIT (start_chains_set
, i
))
592 fprintf (dump_file
, "opening incoming chain\n");
593 chain
= create_new_chain (i
, iri
->nregs
, NULL
, NULL
, NO_REGS
);
594 bitmap_set_bit (&p
->incoming_open_chains_set
, chain
->id
);
599 /* Record in RI that the block corresponding to it has an incoming
600 live value, described by CHAIN. */
602 set_incoming_from_chain (struct bb_rename_info
*ri
, du_head_p chain
)
605 int incoming_nregs
= ri
->incoming
[chain
->regno
].nregs
;
608 /* If we've recorded the same information before, everything is fine. */
609 if (incoming_nregs
== chain
->nregs
)
612 fprintf (dump_file
, "reg %d/%d already recorded\n",
613 chain
->regno
, chain
->nregs
);
617 /* If we have no information for any of the involved registers, update
618 the incoming array. */
619 nregs
= chain
->nregs
;
621 if (ri
->incoming
[chain
->regno
+ nregs
].nregs
!= 0
622 || ri
->incoming
[chain
->regno
+ nregs
].unusable
)
626 nregs
= chain
->nregs
;
627 ri
->incoming
[chain
->regno
].nregs
= nregs
;
629 ri
->incoming
[chain
->regno
+ nregs
].nregs
= -nregs
;
631 fprintf (dump_file
, "recorded reg %d/%d\n",
632 chain
->regno
, chain
->nregs
);
636 /* There must be some kind of conflict. Prevent both the old and
637 new ranges from being used. */
638 if (incoming_nregs
< 0)
639 ri
->incoming
[chain
->regno
+ incoming_nregs
].unusable
= true;
640 for (i
= 0; i
< chain
->nregs
; i
++)
641 ri
->incoming
[chain
->regno
+ i
].unusable
= true;
644 /* Merge the two chains C1 and C2 so that all conflict information is
645 recorded and C1, and the id of C2 is changed to that of C1. */
647 merge_chains (du_head_p c1
, du_head_p c2
)
652 if (c2
->first
!= NULL
)
654 if (c1
->first
== NULL
)
655 c1
->first
= c2
->first
;
657 c1
->last
->next_use
= c2
->first
;
661 c2
->first
= c2
->last
= NULL
;
664 IOR_HARD_REG_SET (c1
->hard_conflicts
, c2
->hard_conflicts
);
665 bitmap_ior_into (&c1
->conflicts
, &c2
->conflicts
);
667 c1
->need_caller_save_reg
|= c2
->need_caller_save_reg
;
668 c1
->cannot_rename
|= c2
->cannot_rename
;
671 /* Analyze the current function and build chains for renaming. */
674 regrename_analyze (bitmap bb_mask
)
676 struct bb_rename_info
*rename_info
;
680 int *inverse_postorder
;
682 inverse_postorder
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
683 n_bbs
= pre_and_rev_post_order_compute (NULL
, inverse_postorder
, false);
685 /* Gather some information about the blocks in this function. */
686 rename_info
= XCNEWVEC (struct bb_rename_info
, n_basic_blocks_for_fn (cfun
));
688 FOR_EACH_BB_FN (bb
, cfun
)
690 struct bb_rename_info
*ri
= rename_info
+ i
;
692 if (bb_mask
!= NULL
&& !bitmap_bit_p (bb_mask
, bb
->index
))
700 id_to_chain
.create (0);
701 bitmap_initialize (&open_chains_set
, &bitmap_default_obstack
);
703 /* The order in which we visit blocks ensures that whenever
704 possible, we only process a block after at least one of its
705 predecessors, which provides a "seeding" effect to make the logic
706 in set_incoming_from_chain and init_rename_info useful. */
708 for (i
= 0; i
< n_bbs
; i
++)
710 basic_block bb1
= BASIC_BLOCK_FOR_FN (cfun
, inverse_postorder
[i
]);
711 struct bb_rename_info
*this_info
;
715 int old_length
= id_to_chain
.length ();
717 this_info
= (struct bb_rename_info
*) bb1
->aux
;
718 if (this_info
== NULL
)
722 fprintf (dump_file
, "\nprocessing block %d:\n", bb1
->index
);
724 init_rename_info (this_info
, bb1
);
726 success
= build_def_use (bb1
);
730 fprintf (dump_file
, "failed\n");
732 id_to_chain
.truncate (old_length
);
733 current_id
= old_length
;
734 bitmap_clear (&this_info
->incoming_open_chains_set
);
736 if (insn_rr
.exists ())
739 FOR_BB_INSNS (bb1
, insn
)
741 insn_rr_info
*p
= &insn_rr
[INSN_UID (insn
)];
749 dump_def_use_chain (old_length
);
750 bitmap_copy (&this_info
->open_chains_set
, &open_chains_set
);
752 /* Add successor blocks to the worklist if necessary, and record
753 data about our own open chains at the end of this block, which
754 will be used to pre-open chains when processing the successors. */
755 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
757 struct bb_rename_info
*dest_ri
;
758 struct du_head
*chain
;
761 fprintf (dump_file
, "successor block %d\n", e
->dest
->index
);
763 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
765 dest_ri
= (struct bb_rename_info
*)e
->dest
->aux
;
768 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
769 set_incoming_from_chain (dest_ri
, chain
);
773 free (inverse_postorder
);
775 /* Now, combine the chains data we have gathered across basic block
778 For every basic block, there may be chains open at the start, or at the
779 end. Rather than exclude them from renaming, we look for open chains
780 with matching registers at the other side of the CFG edge.
782 For a given chain using register R, open at the start of block B, we
783 must find an open chain using R on the other side of every edge leading
784 to B, if the register is live across this edge. In the code below,
785 N_PREDS_USED counts the number of edges where the register is live, and
786 N_PREDS_JOINED counts those where we found an appropriate chain for
789 We perform the analysis for both incoming and outgoing edges, but we
790 only need to merge once (in the second part, after verifying outgoing
792 FOR_EACH_BB_FN (bb
, cfun
)
794 struct bb_rename_info
*bb_ri
= (struct bb_rename_info
*) bb
->aux
;
802 fprintf (dump_file
, "processing bb %d in edges\n", bb
->index
);
804 EXECUTE_IF_SET_IN_BITMAP (&bb_ri
->incoming_open_chains_set
, 0, j
, bi
)
808 struct du_head
*chain
= regrename_chain_from_id (j
);
809 int n_preds_used
= 0, n_preds_joined
= 0;
811 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
813 struct bb_rename_info
*src_ri
;
817 bool success
= false;
819 REG_SET_TO_HARD_REG_SET (live
, df_get_live_out (e
->src
));
820 if (!range_overlaps_hard_reg_set_p (live
, chain
->regno
,
825 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
828 src_ri
= (struct bb_rename_info
*)e
->src
->aux
;
832 EXECUTE_IF_SET_IN_BITMAP (&src_ri
->open_chains_set
,
835 struct du_head
*outgoing_chain
= regrename_chain_from_id (k
);
837 if (outgoing_chain
->regno
== chain
->regno
838 && outgoing_chain
->nregs
== chain
->nregs
)
845 if (!success
&& dump_file
)
846 fprintf (dump_file
, "failure to match with pred block %d\n",
849 if (n_preds_joined
< n_preds_used
)
852 fprintf (dump_file
, "cannot rename chain %d\n", j
);
853 chain
->cannot_rename
= 1;
857 FOR_EACH_BB_FN (bb
, cfun
)
859 struct bb_rename_info
*bb_ri
= (struct bb_rename_info
*) bb
->aux
;
867 fprintf (dump_file
, "processing bb %d out edges\n", bb
->index
);
869 EXECUTE_IF_SET_IN_BITMAP (&bb_ri
->open_chains_set
, 0, j
, bi
)
873 struct du_head
*chain
= regrename_chain_from_id (j
);
874 int n_succs_used
= 0, n_succs_joined
= 0;
876 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
878 bool printed
= false;
879 struct bb_rename_info
*dest_ri
;
884 REG_SET_TO_HARD_REG_SET (live
, df_get_live_in (e
->dest
));
885 if (!range_overlaps_hard_reg_set_p (live
, chain
->regno
,
891 dest_ri
= (struct bb_rename_info
*)e
->dest
->aux
;
895 EXECUTE_IF_SET_IN_BITMAP (&dest_ri
->incoming_open_chains_set
,
898 struct du_head
*incoming_chain
= regrename_chain_from_id (k
);
900 if (incoming_chain
->regno
== chain
->regno
901 && incoming_chain
->nregs
== chain
->nregs
)
907 "merging blocks for edge %d -> %d\n",
908 e
->src
->index
, e
->dest
->index
);
911 " merging chains %d (->%d) and %d (->%d) [%s]\n",
912 k
, incoming_chain
->id
, j
, chain
->id
,
913 reg_names
[incoming_chain
->regno
]);
916 merge_chains (chain
, incoming_chain
);
922 if (n_succs_joined
< n_succs_used
)
925 fprintf (dump_file
, "cannot rename chain %d\n",
927 chain
->cannot_rename
= 1;
934 FOR_EACH_BB_FN (bb
, cfun
)
938 /* Attempt to replace all uses of the register in the chain beginning with
939 HEAD with REG. Returns true on success and false if the replacement is
940 rejected because the insns would not validate. The latter can happen
941 e.g. if a match_parallel predicate enforces restrictions on register
942 numbering in its subpatterns. */
945 regrename_do_replace (struct du_head
*head
, int reg
)
947 struct du_chain
*chain
;
948 unsigned int base_regno
= head
->regno
;
951 for (chain
= head
->first
; chain
; chain
= chain
->next_use
)
953 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
954 struct reg_attrs
*attr
= REG_ATTRS (*chain
->loc
);
955 int reg_ptr
= REG_POINTER (*chain
->loc
);
957 if (DEBUG_INSN_P (chain
->insn
) && REGNO (*chain
->loc
) != base_regno
)
958 validate_change (chain
->insn
, &(INSN_VAR_LOCATION_LOC (chain
->insn
)),
959 gen_rtx_UNKNOWN_VAR_LOC (), true);
962 validate_change (chain
->insn
, chain
->loc
,
963 gen_raw_REG (GET_MODE (*chain
->loc
), reg
), true);
964 if (regno
>= FIRST_PSEUDO_REGISTER
)
965 ORIGINAL_REGNO (*chain
->loc
) = regno
;
966 REG_ATTRS (*chain
->loc
) = attr
;
967 REG_POINTER (*chain
->loc
) = reg_ptr
;
971 if (!apply_change_group ())
974 mode
= GET_MODE (*head
->first
->loc
);
977 head
->nregs
= hard_regno_nregs
[reg
][mode
];
982 /* True if we found a register with a size mismatch, which means that we
983 can't track its lifetime accurately. If so, we abort the current block
985 static bool fail_current_block
;
987 /* Return true if OP is a reg for which all bits are set in PSET, false
988 if all bits are clear.
989 In other cases, set fail_current_block and return false. */
992 verify_reg_in_set (rtx op
, HARD_REG_SET
*pset
)
994 unsigned regno
, nregs
;
995 bool all_live
, all_dead
;
1000 nregs
= REG_NREGS (op
);
1001 all_live
= all_dead
= true;
1003 if (TEST_HARD_REG_BIT (*pset
, regno
+ nregs
))
1007 if (!all_dead
&& !all_live
)
1009 fail_current_block
= true;
1015 /* Return true if OP is a reg that is being tracked already in some form.
1016 May set fail_current_block if it sees an unhandled case of overlap. */
1019 verify_reg_tracked (rtx op
)
1021 return (verify_reg_in_set (op
, &live_hard_regs
)
1022 || verify_reg_in_set (op
, &live_in_chains
));
1025 /* Called through note_stores. DATA points to a rtx_code, either SET or
1026 CLOBBER, which tells us which kind of rtx to look at. If we have a
1027 match, record the set register in live_hard_regs and in the hard_conflicts
1028 bitmap of open chains. */
1031 note_sets_clobbers (rtx x
, const_rtx set
, void *data
)
1033 enum rtx_code code
= *(enum rtx_code
*)data
;
1034 struct du_head
*chain
;
1036 if (GET_CODE (x
) == SUBREG
)
1038 if (!REG_P (x
) || GET_CODE (set
) != code
)
1040 /* There must not be pseudos at this point. */
1041 gcc_assert (HARD_REGISTER_P (x
));
1042 add_to_hard_reg_set (&live_hard_regs
, GET_MODE (x
), REGNO (x
));
1043 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
1044 add_to_hard_reg_set (&chain
->hard_conflicts
, GET_MODE (x
), REGNO (x
));
1048 scan_rtx_reg (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
1053 unsigned this_regno
= REGNO (x
);
1054 int this_nregs
= REG_NREGS (x
);
1056 if (action
== mark_write
)
1061 rtx pat
= PATTERN (insn
);
1063 c
= create_new_chain (this_regno
, this_nregs
, loc
, insn
, cl
);
1065 /* We try to tie chains in a move instruction for
1067 if (recog_data
.n_operands
== 2
1068 && GET_CODE (pat
) == SET
1069 && GET_CODE (SET_DEST (pat
)) == REG
1070 && GET_CODE (SET_SRC (pat
)) == REG
1071 && terminated_this_insn
1072 && terminated_this_insn
->nregs
1073 == REG_NREGS (recog_data
.operand
[1]))
1075 gcc_assert (terminated_this_insn
->regno
1076 == REGNO (recog_data
.operand
[1]));
1078 c
->tied_chain
= terminated_this_insn
;
1079 terminated_this_insn
->tied_chain
= c
;
1082 fprintf (dump_file
, "Tying chain %s (%d) with %s (%d)\n",
1083 reg_names
[c
->regno
], c
->id
,
1084 reg_names
[terminated_this_insn
->regno
],
1085 terminated_this_insn
->id
);
1092 if ((type
== OP_OUT
) != (action
== terminate_write
|| action
== mark_access
))
1095 for (p
= &open_chains
; *p
;)
1097 struct du_head
*head
= *p
;
1098 struct du_head
*next
= head
->next_chain
;
1099 int exact_match
= (head
->regno
== this_regno
1100 && head
->nregs
== this_nregs
);
1101 int superset
= (this_regno
<= head
->regno
1102 && this_regno
+ this_nregs
>= head
->regno
+ head
->nregs
);
1103 int subset
= (this_regno
>= head
->regno
1104 && this_regno
+ this_nregs
<= head
->regno
+ head
->nregs
);
1106 if (!bitmap_bit_p (&open_chains_set
, head
->id
)
1107 || head
->regno
+ head
->nregs
<= this_regno
1108 || this_regno
+ this_nregs
<= head
->regno
)
1110 p
= &head
->next_chain
;
1114 if (action
== mark_read
|| action
== mark_access
)
1116 /* ??? Class NO_REGS can happen if the md file makes use of
1117 EXTRA_CONSTRAINTS to match registers. Which is arguably
1118 wrong, but there we are. */
1120 if (cl
== NO_REGS
|| (!exact_match
&& !DEBUG_INSN_P (insn
)))
1124 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1125 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1126 scan_actions_name
[(int) action
]);
1127 head
->cannot_rename
= 1;
1130 unsigned nregs
= this_nregs
;
1131 head
->regno
= this_regno
;
1132 head
->nregs
= this_nregs
;
1134 SET_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
1137 "Widening register in chain %s (%d) at insn %d\n",
1138 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
));
1142 fail_current_block
= true;
1145 "Failing basic block due to unhandled overlap\n");
1150 struct du_chain
*this_du
;
1151 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
1152 this_du
->next_use
= 0;
1154 this_du
->insn
= insn
;
1156 if (head
->first
== NULL
)
1157 head
->first
= this_du
;
1159 head
->last
->next_use
= this_du
;
1160 record_operand_use (head
, this_du
);
1161 head
->last
= this_du
;
1163 /* Avoid adding the same location in a DEBUG_INSN multiple times,
1164 which could happen with non-exact overlap. */
1165 if (DEBUG_INSN_P (insn
))
1167 /* Otherwise, find any other chains that do not match exactly;
1168 ensure they all get marked unrenamable. */
1169 p
= &head
->next_chain
;
1173 /* Whether the terminated chain can be used for renaming
1174 depends on the action and this being an exact match.
1175 In either case, we remove this element from open_chains. */
1177 if ((action
== terminate_dead
|| action
== terminate_write
)
1178 && (superset
|| subset
))
1182 if (subset
&& !superset
)
1183 head
->cannot_rename
= 1;
1184 bitmap_clear_bit (&open_chains_set
, head
->id
);
1186 nregs
= head
->nregs
;
1189 CLEAR_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
1190 if (subset
&& !superset
1191 && (head
->regno
+ nregs
< this_regno
1192 || head
->regno
+ nregs
>= this_regno
+ this_nregs
))
1193 SET_HARD_REG_BIT (live_hard_regs
, head
->regno
+ nregs
);
1196 if (action
== terminate_dead
)
1197 terminated_this_insn
= *p
;
1201 "Closing chain %s (%d) at insn %d (%s%s)\n",
1202 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1203 scan_actions_name
[(int) action
],
1204 superset
? ", superset" : subset
? ", subset" : "");
1206 else if (action
== terminate_dead
|| action
== terminate_write
)
1208 /* In this case, tracking liveness gets too hard. Fail the
1209 entire basic block. */
1212 "Failing basic block due to unhandled overlap\n");
1213 fail_current_block
= true;
1218 head
->cannot_rename
= 1;
1221 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1222 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1223 scan_actions_name
[(int) action
]);
1224 p
= &head
->next_chain
;
1229 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1230 BASE_REG_CLASS depending on how the register is being considered. */
1233 scan_rtx_address (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
,
1234 enum scan_actions action
, machine_mode mode
,
1238 RTX_CODE code
= GET_CODE (x
);
1242 if (action
== mark_write
|| action
== mark_access
)
1249 rtx orig_op0
= XEXP (x
, 0);
1250 rtx orig_op1
= XEXP (x
, 1);
1251 RTX_CODE code0
= GET_CODE (orig_op0
);
1252 RTX_CODE code1
= GET_CODE (orig_op1
);
1257 enum rtx_code index_code
= SCRATCH
;
1259 if (GET_CODE (op0
) == SUBREG
)
1261 op0
= SUBREG_REG (op0
);
1262 code0
= GET_CODE (op0
);
1265 if (GET_CODE (op1
) == SUBREG
)
1267 op1
= SUBREG_REG (op1
);
1268 code1
= GET_CODE (op1
);
1271 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
1272 || code0
== ZERO_EXTEND
|| code1
== MEM
)
1274 locI
= &XEXP (x
, 0);
1275 locB
= &XEXP (x
, 1);
1276 index_code
= GET_CODE (*locI
);
1278 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
1279 || code1
== ZERO_EXTEND
|| code0
== MEM
)
1281 locI
= &XEXP (x
, 1);
1282 locB
= &XEXP (x
, 0);
1283 index_code
= GET_CODE (*locI
);
1285 else if (code0
== CONST_INT
|| code0
== CONST
1286 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
1288 locB
= &XEXP (x
, 1);
1289 index_code
= GET_CODE (XEXP (x
, 0));
1291 else if (code1
== CONST_INT
|| code1
== CONST
1292 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
1294 locB
= &XEXP (x
, 0);
1295 index_code
= GET_CODE (XEXP (x
, 1));
1297 else if (code0
== REG
&& code1
== REG
)
1300 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
1302 if (REGNO_OK_FOR_INDEX_P (regno1
)
1303 && regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
))
1305 else if (REGNO_OK_FOR_INDEX_P (regno0
)
1306 && regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
1308 else if (regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
)
1309 || REGNO_OK_FOR_INDEX_P (regno1
))
1311 else if (regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
1316 locI
= &XEXP (x
, index_op
);
1317 locB
= &XEXP (x
, !index_op
);
1318 index_code
= GET_CODE (*locI
);
1320 else if (code0
== REG
)
1322 locI
= &XEXP (x
, 0);
1323 locB
= &XEXP (x
, 1);
1324 index_code
= GET_CODE (*locI
);
1326 else if (code1
== REG
)
1328 locI
= &XEXP (x
, 1);
1329 locB
= &XEXP (x
, 0);
1330 index_code
= GET_CODE (*locI
);
1334 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
, as
);
1336 scan_rtx_address (insn
, locB
,
1337 base_reg_class (mode
, as
, PLUS
, index_code
),
1349 /* If the target doesn't claim to handle autoinc, this must be
1350 something special, like a stack push. Kill this chain. */
1352 action
= mark_all_read
;
1357 scan_rtx_address (insn
, &XEXP (x
, 0),
1358 base_reg_class (GET_MODE (x
), MEM_ADDR_SPACE (x
),
1360 action
, GET_MODE (x
), MEM_ADDR_SPACE (x
));
1364 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
);
1371 fmt
= GET_RTX_FORMAT (code
);
1372 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1375 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
, as
);
1376 else if (fmt
[i
] == 'E')
1377 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1378 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
, as
);
1383 scan_rtx (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
1388 enum rtx_code code
= GET_CODE (x
);
1391 code
= GET_CODE (x
);
1403 scan_rtx_reg (insn
, loc
, cl
, action
, type
);
1407 scan_rtx_address (insn
, &XEXP (x
, 0),
1408 base_reg_class (GET_MODE (x
), MEM_ADDR_SPACE (x
),
1410 action
, GET_MODE (x
), MEM_ADDR_SPACE (x
));
1414 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
);
1415 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
1416 (GET_CODE (PATTERN (insn
)) == COND_EXEC
1417 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
1420 case STRICT_LOW_PART
:
1421 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
1422 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
);
1427 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
1428 (type
== OP_IN
? OP_IN
:
1429 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
));
1430 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
);
1431 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
);
1440 /* Should only happen inside MEM. */
1444 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
1445 (GET_CODE (PATTERN (insn
)) == COND_EXEC
1446 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
1450 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
);
1452 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
);
1459 fmt
= GET_RTX_FORMAT (code
);
1460 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1463 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
);
1464 else if (fmt
[i
] == 'E')
1465 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1466 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
);
1470 /* Hide operands of the current insn (of which there are N_OPS) by
1471 substituting cc0 for them.
1472 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
1473 For every bit set in DO_NOT_HIDE, we leave the operand alone.
1474 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
1475 and earlyclobbers. */
1478 hide_operands (int n_ops
, rtx
*old_operands
, rtx
*old_dups
,
1479 unsigned HOST_WIDE_INT do_not_hide
, bool inout_and_ec_only
)
1482 const operand_alternative
*op_alt
= which_op_alt ();
1483 for (i
= 0; i
< n_ops
; i
++)
1485 old_operands
[i
] = recog_data
.operand
[i
];
1486 /* Don't squash match_operator or match_parallel here, since
1487 we don't know that all of the contained registers are
1488 reachable by proper operands. */
1489 if (recog_data
.constraints
[i
][0] == '\0')
1491 if (do_not_hide
& (1 << i
))
1493 if (!inout_and_ec_only
|| recog_data
.operand_type
[i
] == OP_INOUT
1494 || op_alt
[i
].earlyclobber
)
1495 *recog_data
.operand_loc
[i
] = cc0_rtx
;
1497 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1499 int opn
= recog_data
.dup_num
[i
];
1500 old_dups
[i
] = *recog_data
.dup_loc
[i
];
1501 if (do_not_hide
& (1 << opn
))
1503 if (!inout_and_ec_only
|| recog_data
.operand_type
[opn
] == OP_INOUT
1504 || op_alt
[opn
].earlyclobber
)
1505 *recog_data
.dup_loc
[i
] = cc0_rtx
;
1509 /* Undo the substitution performed by hide_operands. INSN is the insn we
1510 are processing; the arguments are the same as in hide_operands. */
1513 restore_operands (rtx_insn
*insn
, int n_ops
, rtx
*old_operands
, rtx
*old_dups
)
1516 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1517 *recog_data
.dup_loc
[i
] = old_dups
[i
];
1518 for (i
= 0; i
< n_ops
; i
++)
1519 *recog_data
.operand_loc
[i
] = old_operands
[i
];
1520 if (recog_data
.n_dups
)
1521 df_insn_rescan (insn
);
1524 /* For each output operand of INSN, call scan_rtx to create a new
1525 open chain. Do this only for normal or earlyclobber outputs,
1526 depending on EARLYCLOBBER. If INSN_INFO is nonnull, use it to
1527 record information about the operands in the insn. */
1530 record_out_operands (rtx_insn
*insn
, bool earlyclobber
, insn_rr_info
*insn_info
)
1532 int n_ops
= recog_data
.n_operands
;
1533 const operand_alternative
*op_alt
= which_op_alt ();
1537 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1539 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1540 rtx
*loc
= (i
< n_ops
1541 ? recog_data
.operand_loc
[opn
]
1542 : recog_data
.dup_loc
[i
- n_ops
]);
1544 enum reg_class cl
= alternative_class (op_alt
, opn
);
1546 struct du_head
*prev_open
;
1548 if (recog_data
.operand_type
[opn
] != OP_OUT
1549 || op_alt
[opn
].earlyclobber
!= earlyclobber
)
1553 cur_operand
= insn_info
->op_info
+ i
;
1555 prev_open
= open_chains
;
1556 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
);
1558 /* ??? Many targets have output constraints on the SET_DEST
1559 of a call insn, which is stupid, since these are certainly
1560 ABI defined hard registers. For these, and for asm operands
1561 that originally referenced hard registers, we must record that
1562 the chain cannot be renamed. */
1564 || (asm_noperands (PATTERN (insn
)) > 0
1566 && REGNO (op
) == ORIGINAL_REGNO (op
)))
1568 if (prev_open
!= open_chains
)
1569 open_chains
->cannot_rename
= 1;
1575 /* Build def/use chain. */
1578 build_def_use (basic_block bb
)
1581 unsigned HOST_WIDE_INT untracked_operands
;
1583 fail_current_block
= false;
1585 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1587 if (NONDEBUG_INSN_P (insn
))
1591 rtx old_operands
[MAX_RECOG_OPERANDS
];
1592 rtx old_dups
[MAX_DUP_OPERANDS
];
1595 enum rtx_code set_code
= SET
;
1596 enum rtx_code clobber_code
= CLOBBER
;
1597 insn_rr_info
*insn_info
= NULL
;
1598 terminated_this_insn
= NULL
;
1600 /* Process the insn, determining its effect on the def-use
1601 chains and live hard registers. We perform the following
1602 steps with the register references in the insn, simulating
1604 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1605 by creating chains and marking hard regs live.
1606 (2) Any read outside an operand causes any chain it overlaps
1607 with to be marked unrenamable.
1608 (3) Any read inside an operand is added if there's already
1609 an open chain for it.
1610 (4) For any REG_DEAD note we find, close open chains that
1612 (5) For any non-earlyclobber write we find, close open chains
1614 (6) For any non-earlyclobber write we find in an operand, make
1615 a new chain or mark the hard register as live.
1616 (7) For any REG_UNUSED, close any chains we just opened.
1618 We cannot deal with situations where we track a reg in one mode
1619 and see a reference in another mode; these will cause the chain
1620 to be marked unrenamable or even cause us to abort the entire
1623 extract_constrain_insn (insn
);
1624 preprocess_constraints (insn
);
1625 const operand_alternative
*op_alt
= which_op_alt ();
1626 n_ops
= recog_data
.n_operands
;
1627 untracked_operands
= 0;
1629 if (insn_rr
.exists ())
1631 insn_info
= &insn_rr
[INSN_UID (insn
)];
1632 insn_info
->op_info
= XOBNEWVEC (&rename_obstack
, operand_rr_info
,
1633 recog_data
.n_operands
);
1634 memset (insn_info
->op_info
, 0,
1635 sizeof (operand_rr_info
) * recog_data
.n_operands
);
1638 /* Simplify the code below by promoting OP_OUT to OP_INOUT in
1639 predicated instructions, but only for register operands
1640 that are already tracked, so that we can create a chain
1641 when the first SET makes a register live. */
1643 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1644 for (i
= 0; i
< n_ops
; ++i
)
1646 rtx op
= recog_data
.operand
[i
];
1647 int matches
= op_alt
[i
].matches
;
1648 if (matches
>= 0 || op_alt
[i
].matched
>= 0
1649 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1651 recog_data
.operand_type
[i
] = OP_INOUT
;
1652 /* A special case to deal with instruction patterns that
1653 have matching operands with different modes. If we're
1654 not already tracking such a reg, we won't start here,
1655 and we must instead make sure to make the operand visible
1656 to the machinery that tracks hard registers. */
1658 && (GET_MODE_SIZE (recog_data
.operand_mode
[i
])
1659 != GET_MODE_SIZE (recog_data
.operand_mode
[matches
]))
1660 && !verify_reg_in_set (op
, &live_in_chains
))
1662 untracked_operands
|= 1 << i
;
1663 untracked_operands
|= 1 << matches
;
1666 /* If there's an in-out operand with a register that is not
1667 being tracked at all yet, open a chain. */
1668 if (recog_data
.operand_type
[i
] == OP_INOUT
1669 && !(untracked_operands
& (1 << i
))
1671 && !verify_reg_tracked (op
))
1672 create_new_chain (REGNO (op
), REG_NREGS (op
), NULL
, NULL
,
1676 if (fail_current_block
)
1679 /* Step 1a: Mark hard registers that are clobbered in this insn,
1680 outside an operand, as live. */
1681 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1683 note_stores (PATTERN (insn
), note_sets_clobbers
, &clobber_code
);
1684 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1686 /* Step 1b: Begin new chains for earlyclobbered writes inside
1688 record_out_operands (insn
, true, insn_info
);
1690 /* Step 2: Mark chains for which we have reads outside operands
1692 We do this by munging all operands into CC0, and closing
1693 everything remaining. */
1695 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1697 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, mark_all_read
, OP_IN
);
1698 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1700 /* Step 2B: Can't rename function call argument registers. */
1701 if (CALL_P (insn
) && CALL_INSN_FUNCTION_USAGE (insn
))
1702 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
1703 NO_REGS
, mark_all_read
, OP_IN
);
1705 /* Step 2C: Can't rename asm operands that were originally
1707 if (asm_noperands (PATTERN (insn
)) > 0)
1708 for (i
= 0; i
< n_ops
; i
++)
1710 rtx
*loc
= recog_data
.operand_loc
[i
];
1714 && REGNO (op
) == ORIGINAL_REGNO (op
)
1715 && (recog_data
.operand_type
[i
] == OP_IN
1716 || recog_data
.operand_type
[i
] == OP_INOUT
))
1717 scan_rtx (insn
, loc
, NO_REGS
, mark_all_read
, OP_IN
);
1720 /* Step 3: Append to chains for reads inside operands. */
1721 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1723 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1724 rtx
*loc
= (i
< n_ops
1725 ? recog_data
.operand_loc
[opn
]
1726 : recog_data
.dup_loc
[i
- n_ops
]);
1727 enum reg_class cl
= alternative_class (op_alt
, opn
);
1728 enum op_type type
= recog_data
.operand_type
[opn
];
1730 /* Don't scan match_operand here, since we've no reg class
1731 information to pass down. Any operands that we could
1732 substitute in will be represented elsewhere. */
1733 if (recog_data
.constraints
[opn
][0] == '\0'
1734 || untracked_operands
& (1 << opn
))
1738 cur_operand
= i
== opn
? insn_info
->op_info
+ i
: NULL
;
1739 if (op_alt
[opn
].is_address
)
1740 scan_rtx_address (insn
, loc
, cl
, mark_read
,
1741 VOIDmode
, ADDR_SPACE_GENERIC
);
1743 scan_rtx (insn
, loc
, cl
, mark_read
, type
);
1747 /* Step 3B: Record updates for regs in REG_INC notes, and
1748 source regs in REG_FRAME_RELATED_EXPR notes. */
1749 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1750 if (REG_NOTE_KIND (note
) == REG_INC
1751 || REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1752 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
1755 /* Step 4: Close chains for registers that die here, unless
1756 the register is mentioned in a REG_UNUSED note. In that
1757 case we keep the chain open until step #7 below to ensure
1758 it conflicts with other output operands of this insn.
1759 See PR 52573. Arguably the insn should not have both
1760 notes; it has proven difficult to fix that without
1761 other undesirable side effects. */
1762 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1763 if (REG_NOTE_KIND (note
) == REG_DEAD
1764 && !find_regno_note (insn
, REG_UNUSED
, REGNO (XEXP (note
, 0))))
1766 remove_from_hard_reg_set (&live_hard_regs
,
1767 GET_MODE (XEXP (note
, 0)),
1768 REGNO (XEXP (note
, 0)));
1769 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1773 /* Step 4B: If this is a call, any chain live at this point
1774 requires a caller-saved reg. */
1778 for (p
= open_chains
; p
; p
= p
->next_chain
)
1779 p
->need_caller_save_reg
= 1;
1782 /* Step 5: Close open chains that overlap writes. Similar to
1783 step 2, we hide in-out operands, since we do not want to
1784 close these chains. We also hide earlyclobber operands,
1785 since we've opened chains for them in step 1, and earlier
1786 chains they would overlap with must have been closed at
1787 the previous insn at the latest, as such operands cannot
1788 possibly overlap with any input operands. */
1790 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1792 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
);
1793 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1795 /* Step 6a: Mark hard registers that are set in this insn,
1796 outside an operand, as live. */
1797 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1799 note_stores (PATTERN (insn
), note_sets_clobbers
, &set_code
);
1800 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1802 /* Step 6b: Begin new chains for writes inside operands. */
1803 record_out_operands (insn
, false, insn_info
);
1805 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1806 notes for update. */
1807 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1808 if (REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1809 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_access
,
1812 /* Step 7: Close chains for registers that were never
1813 really used here. */
1814 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1815 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
1817 remove_from_hard_reg_set (&live_hard_regs
,
1818 GET_MODE (XEXP (note
, 0)),
1819 REGNO (XEXP (note
, 0)));
1820 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1824 else if (DEBUG_INSN_P (insn
)
1825 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn
)))
1827 scan_rtx (insn
, &INSN_VAR_LOCATION_LOC (insn
),
1828 ALL_REGS
, mark_read
, OP_IN
);
1830 if (insn
== BB_END (bb
))
1834 if (fail_current_block
)
1840 /* Initialize the register renamer. If INSN_INFO is true, ensure that
1841 insn_rr is nonnull. */
1843 regrename_init (bool insn_info
)
1845 gcc_obstack_init (&rename_obstack
);
1848 insn_rr
.safe_grow_cleared (get_max_uid ());
1851 /* Free all global data used by the register renamer. */
1853 regrename_finish (void)
1857 obstack_free (&rename_obstack
, NULL
);
1860 /* Perform register renaming on the current function. */
1863 regrename_optimize (void)
1865 df_set_flags (DF_LR_RUN_DCE
);
1866 df_note_add_problem ();
1868 df_set_flags (DF_DEFER_INSN_RESCAN
);
1870 regrename_init (false);
1872 regrename_analyze (NULL
);
1876 regrename_finish ();
1883 const pass_data pass_data_regrename
=
1885 RTL_PASS
, /* type */
1887 OPTGROUP_NONE
, /* optinfo_flags */
1888 TV_RENAME_REGISTERS
, /* tv_id */
1889 0, /* properties_required */
1890 0, /* properties_provided */
1891 0, /* properties_destroyed */
1892 0, /* todo_flags_start */
1893 TODO_df_finish
, /* todo_flags_finish */
1896 class pass_regrename
: public rtl_opt_pass
1899 pass_regrename (gcc::context
*ctxt
)
1900 : rtl_opt_pass (pass_data_regrename
, ctxt
)
1903 /* opt_pass methods: */
1904 virtual bool gate (function
*)
1906 return (optimize
> 0 && (flag_rename_registers
));
1909 virtual unsigned int execute (function
*) { return regrename_optimize (); }
1911 }; // class pass_regrename
1916 make_pass_regrename (gcc::context
*ctxt
)
1918 return new pass_regrename (ctxt
);