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"
24 #include "rtl-error.h"
26 #include "insn-config.h"
28 #include "addresses.h"
29 #include "hard-reg-set.h"
36 #include "dominance.h"
39 #include "basic-block.h"
45 #include "tree-pass.h"
49 #include "regrename.h"
51 /* This file implements the RTL register renaming pass of the compiler. It is
52 a semi-local pass whose goal is to maximize the usage of the register file
53 of the processor by substituting registers for others in the solution given
54 by the register allocator. The algorithm is as follows:
56 1. Local def/use chains are built: within each basic block, chains are
57 opened and closed; if a chain isn't closed at the end of the block,
58 it is dropped. We pre-open chains if we have already examined a
59 predecessor block and found chains live at the end which match
60 live registers at the start of the new block.
62 2. We try to combine the local chains across basic block boundaries by
63 comparing chains that were open at the start or end of a block to
64 those in successor/predecessor blocks.
66 3. For each chain, the set of possible renaming registers is computed.
67 This takes into account the renaming of previously processed chains.
68 Optionally, a preferred class is computed for the renaming register.
70 4. The best renaming register is computed for the chain in the above set,
71 using a round-robin allocation. If a preferred class exists, then the
72 round-robin allocation is done within the class first, if possible.
73 The round-robin allocation of renaming registers itself is global.
75 5. If a renaming register has been found, it is substituted in the chain.
77 Targets can parameterize the pass by specifying a preferred class for the
78 renaming register for a given (super)class of registers to be renamed. */
80 #if HOST_BITS_PER_WIDE_INT <= MAX_RECOG_OPERANDS
81 #error "Use a different bitmap implementation for untracked_operands."
91 /* mark_access is for marking the destination regs in
92 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
93 note is updated properly. */
97 static const char * const scan_actions_name
[] =
107 /* TICK and THIS_TICK are used to record the last time we saw each
109 static int tick
[FIRST_PSEUDO_REGISTER
];
110 static int this_tick
= 0;
112 static struct obstack rename_obstack
;
114 /* If nonnull, the code calling into the register renamer requested
115 information about insn operands, and we store it here. */
116 vec
<insn_rr_info
> insn_rr
;
118 static void scan_rtx (rtx_insn
*, rtx
*, enum reg_class
, enum scan_actions
,
120 static bool build_def_use (basic_block
);
122 /* The id to be given to the next opened chain. */
123 static unsigned current_id
;
125 /* A mapping of unique id numbers to chains. */
126 static vec
<du_head_p
> id_to_chain
;
128 /* List of currently open chains. */
129 static struct du_head
*open_chains
;
131 /* Bitmap of open chains. The bits set always match the list found in
133 static bitmap_head open_chains_set
;
135 /* Record the registers being tracked in open_chains. */
136 static HARD_REG_SET live_in_chains
;
138 /* Record the registers that are live but not tracked. The intersection
139 between this and live_in_chains is empty. */
140 static HARD_REG_SET live_hard_regs
;
142 /* Set while scanning RTL if INSN_RR is nonnull, i.e. if the current analysis
143 is for a caller that requires operand data. Used in
144 record_operand_use. */
145 static operand_rr_info
*cur_operand
;
147 /* Return the chain corresponding to id number ID. Take into account that
148 chains may have been merged. */
150 regrename_chain_from_id (unsigned int id
)
152 du_head_p first_chain
= id_to_chain
[id
];
153 du_head_p chain
= first_chain
;
154 while (chain
->id
!= id
)
157 chain
= id_to_chain
[id
];
159 first_chain
->id
= id
;
163 /* Dump all def/use chains, starting at id FROM. */
166 dump_def_use_chain (int from
)
170 FOR_EACH_VEC_ELT_FROM (id_to_chain
, i
, head
, from
)
172 struct du_chain
*this_du
= head
->first
;
174 fprintf (dump_file
, "Register %s (%d):",
175 reg_names
[head
->regno
], head
->nregs
);
178 fprintf (dump_file
, " %d [%s]", INSN_UID (this_du
->insn
),
179 reg_class_names
[this_du
->cl
]);
180 this_du
= this_du
->next_use
;
182 fprintf (dump_file
, "\n");
183 head
= head
->next_chain
;
188 free_chain_data (void)
192 for (i
= 0; id_to_chain
.iterate (i
, &ptr
); i
++)
193 bitmap_clear (&ptr
->conflicts
);
195 id_to_chain
.release ();
198 /* Walk all chains starting with CHAINS and record that they conflict with
199 another chain whose id is ID. */
202 mark_conflict (struct du_head
*chains
, unsigned id
)
206 bitmap_set_bit (&chains
->conflicts
, id
);
207 chains
= chains
->next_chain
;
211 /* Examine cur_operand, and if it is nonnull, record information about the
212 use THIS_DU which is part of the chain HEAD. */
215 record_operand_use (struct du_head
*head
, struct du_chain
*this_du
)
217 if (cur_operand
== NULL
)
219 gcc_assert (cur_operand
->n_chains
< MAX_REGS_PER_ADDRESS
);
220 cur_operand
->heads
[cur_operand
->n_chains
] = head
;
221 cur_operand
->chains
[cur_operand
->n_chains
++] = this_du
;
224 /* Create a new chain for THIS_NREGS registers starting at THIS_REGNO,
225 and record its occurrence in *LOC, which is being written to in INSN.
226 This access requires a register of class CL. */
229 create_new_chain (unsigned this_regno
, unsigned this_nregs
, rtx
*loc
,
230 rtx_insn
*insn
, enum reg_class cl
)
232 struct du_head
*head
= XOBNEW (&rename_obstack
, struct du_head
);
233 struct du_chain
*this_du
;
236 head
->next_chain
= open_chains
;
237 head
->regno
= this_regno
;
238 head
->nregs
= this_nregs
;
239 head
->need_caller_save_reg
= 0;
240 head
->cannot_rename
= 0;
242 id_to_chain
.safe_push (head
);
243 head
->id
= current_id
++;
245 bitmap_initialize (&head
->conflicts
, &bitmap_default_obstack
);
246 bitmap_copy (&head
->conflicts
, &open_chains_set
);
247 mark_conflict (open_chains
, head
->id
);
249 /* Since we're tracking this as a chain now, remove it from the
250 list of conflicting live hard registers and track it in
251 live_in_chains instead. */
255 SET_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
256 CLEAR_HARD_REG_BIT (live_hard_regs
, head
->regno
+ nregs
);
259 COPY_HARD_REG_SET (head
->hard_conflicts
, live_hard_regs
);
260 bitmap_set_bit (&open_chains_set
, head
->id
);
266 fprintf (dump_file
, "Creating chain %s (%d)",
267 reg_names
[head
->regno
], head
->id
);
268 if (insn
!= NULL_RTX
)
269 fprintf (dump_file
, " at insn %d", INSN_UID (insn
));
270 fprintf (dump_file
, "\n");
273 if (insn
== NULL_RTX
)
275 head
->first
= head
->last
= NULL
;
279 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
280 head
->first
= head
->last
= this_du
;
282 this_du
->next_use
= 0;
284 this_du
->insn
= insn
;
286 record_operand_use (head
, this_du
);
290 /* For a def-use chain HEAD, find which registers overlap its lifetime and
291 set the corresponding bits in *PSET. */
294 merge_overlapping_regs (HARD_REG_SET
*pset
, struct du_head
*head
)
298 IOR_HARD_REG_SET (*pset
, head
->hard_conflicts
);
299 EXECUTE_IF_SET_IN_BITMAP (&head
->conflicts
, 0, i
, bi
)
301 du_head_p other
= regrename_chain_from_id (i
);
302 unsigned j
= other
->nregs
;
303 gcc_assert (other
!= head
);
305 SET_HARD_REG_BIT (*pset
, other
->regno
+ j
);
309 /* Check if NEW_REG can be the candidate register to rename for
310 REG in THIS_HEAD chain. THIS_UNAVAILABLE is a set of unavailable hard
314 check_new_reg_p (int reg ATTRIBUTE_UNUSED
, int new_reg
,
315 struct du_head
*this_head
, HARD_REG_SET this_unavailable
)
317 machine_mode mode
= GET_MODE (*this_head
->first
->loc
);
318 int nregs
= hard_regno_nregs
[new_reg
][mode
];
320 struct du_chain
*tmp
;
322 for (i
= nregs
- 1; i
>= 0; --i
)
323 if (TEST_HARD_REG_BIT (this_unavailable
, new_reg
+ i
)
324 || fixed_regs
[new_reg
+ i
]
325 || global_regs
[new_reg
+ i
]
326 /* Can't use regs which aren't saved by the prologue. */
327 || (! df_regs_ever_live_p (new_reg
+ i
)
328 && ! call_used_regs
[new_reg
+ i
])
329 #ifdef LEAF_REGISTERS
330 /* We can't use a non-leaf register if we're in a
333 && !LEAF_REGISTERS
[new_reg
+ i
])
335 || ! HARD_REGNO_RENAME_OK (reg
+ i
, new_reg
+ i
))
338 /* See whether it accepts all modes that occur in
339 definition and uses. */
340 for (tmp
= this_head
->first
; tmp
; tmp
= tmp
->next_use
)
341 if ((! HARD_REGNO_MODE_OK (new_reg
, GET_MODE (*tmp
->loc
))
342 && ! DEBUG_INSN_P (tmp
->insn
))
343 || (this_head
->need_caller_save_reg
344 && ! (HARD_REGNO_CALL_PART_CLOBBERED
345 (reg
, GET_MODE (*tmp
->loc
)))
346 && (HARD_REGNO_CALL_PART_CLOBBERED
347 (new_reg
, GET_MODE (*tmp
->loc
)))))
353 /* For the chain THIS_HEAD, compute and return the best register to
354 rename to. SUPER_CLASS is the superunion of register classes in
355 the chain. UNAVAILABLE is a set of registers that cannot be used.
356 OLD_REG is the register currently used for the chain. BEST_RENAME
357 controls whether the register chosen must be better than the
358 current one or just respect the given constraint. */
361 find_rename_reg (du_head_p this_head
, enum reg_class super_class
,
362 HARD_REG_SET
*unavailable
, int old_reg
, bool best_rename
)
364 bool has_preferred_class
;
365 enum reg_class preferred_class
;
367 int best_new_reg
= old_reg
;
369 /* Further narrow the set of registers we can use for renaming.
370 If the chain needs a call-saved register, mark the call-used
371 registers as unavailable. */
372 if (this_head
->need_caller_save_reg
)
373 IOR_HARD_REG_SET (*unavailable
, call_used_reg_set
);
375 /* Mark registers that overlap this chain's lifetime as unavailable. */
376 merge_overlapping_regs (unavailable
, this_head
);
378 /* Compute preferred rename class of super union of all the classes
381 = (enum reg_class
) targetm
.preferred_rename_class (super_class
);
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 /* Perform register renaming on the current function. */
426 HARD_REG_SET unavailable
;
430 memset (tick
, 0, sizeof tick
);
432 CLEAR_HARD_REG_SET (unavailable
);
433 /* Don't clobber traceback for noreturn functions. */
434 if (frame_pointer_needed
)
436 add_to_hard_reg_set (&unavailable
, Pmode
, FRAME_POINTER_REGNUM
);
437 if (!HARD_FRAME_POINTER_IS_FRAME_POINTER
)
438 add_to_hard_reg_set (&unavailable
, Pmode
, HARD_FRAME_POINTER_REGNUM
);
441 FOR_EACH_VEC_ELT (id_to_chain
, i
, this_head
)
445 struct du_chain
*tmp
;
446 HARD_REG_SET this_unavailable
;
447 int reg
= this_head
->regno
;
448 enum reg_class super_class
= NO_REGS
;
450 if (this_head
->cannot_rename
)
453 if (fixed_regs
[reg
] || global_regs
[reg
]
454 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
455 || (frame_pointer_needed
&& reg
== HARD_FRAME_POINTER_REGNUM
)
457 || (frame_pointer_needed
&& reg
== FRAME_POINTER_REGNUM
)
462 COPY_HARD_REG_SET (this_unavailable
, unavailable
);
464 /* Iterate over elements in the chain in order to:
465 1. Count number of uses, and narrow the set of registers we can
467 2. Compute the superunion of register classes in this chain. */
469 super_class
= NO_REGS
;
470 for (tmp
= this_head
->first
; tmp
; tmp
= tmp
->next_use
)
472 if (DEBUG_INSN_P (tmp
->insn
))
475 IOR_COMPL_HARD_REG_SET (this_unavailable
,
476 reg_class_contents
[tmp
->cl
]);
478 = reg_class_superunion
[(int) super_class
][(int) tmp
->cl
];
484 best_new_reg
= find_rename_reg (this_head
, super_class
,
485 &this_unavailable
, reg
, true);
489 fprintf (dump_file
, "Register %s in insn %d",
490 reg_names
[reg
], INSN_UID (this_head
->first
->insn
));
491 if (this_head
->need_caller_save_reg
)
492 fprintf (dump_file
, " crosses a call");
495 if (best_new_reg
== reg
)
497 tick
[reg
] = ++this_tick
;
499 fprintf (dump_file
, "; no available better choice\n");
504 fprintf (dump_file
, ", renamed as %s\n", reg_names
[best_new_reg
]);
506 regrename_do_replace (this_head
, best_new_reg
);
507 tick
[best_new_reg
] = ++this_tick
;
508 df_set_regs_ever_live (best_new_reg
, true);
512 /* A structure to record information for each hard register at the start of
514 struct incoming_reg_info
{
515 /* Holds the number of registers used in the chain that gave us information
516 about this register. Zero means no information known yet, while a
517 negative value is used for something that is part of, but not the first
518 register in a multi-register value. */
520 /* Set to true if we have accesses that conflict in the number of registers
525 /* A structure recording information about each basic block. It is saved
526 and restored around basic block boundaries.
527 A pointer to such a structure is stored in each basic block's aux field
528 during regrename_analyze, except for blocks we know can't be optimized
529 (such as entry and exit blocks). */
530 struct bb_rename_info
532 /* The basic block corresponding to this structure. */
534 /* Copies of the global information. */
535 bitmap_head open_chains_set
;
536 bitmap_head incoming_open_chains_set
;
537 struct incoming_reg_info incoming
[FIRST_PSEUDO_REGISTER
];
540 /* Initialize a rename_info structure P for basic block BB, which starts a new
543 init_rename_info (struct bb_rename_info
*p
, basic_block bb
)
547 HARD_REG_SET start_chains_set
;
550 bitmap_initialize (&p
->open_chains_set
, &bitmap_default_obstack
);
551 bitmap_initialize (&p
->incoming_open_chains_set
, &bitmap_default_obstack
);
554 bitmap_clear (&open_chains_set
);
556 CLEAR_HARD_REG_SET (live_in_chains
);
557 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_in (bb
));
558 FOR_EACH_ARTIFICIAL_DEF (def
, bb
->index
)
559 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
560 SET_HARD_REG_BIT (live_hard_regs
, DF_REF_REGNO (def
));
562 /* Open chains based on information from (at least one) predecessor
563 block. This gives us a chance later on to combine chains across
564 basic block boundaries. Inconsistencies (in access sizes) will
565 be caught normally and dealt with conservatively by disabling the
566 chain for renaming, and there is no risk of losing optimization
567 opportunities by opening chains either: if we did not open the
568 chains, we'd have to track the live register as a hard reg, and
569 we'd be unable to rename it in any case. */
570 CLEAR_HARD_REG_SET (start_chains_set
);
571 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
573 struct incoming_reg_info
*iri
= p
->incoming
+ i
;
574 if (iri
->nregs
> 0 && !iri
->unusable
575 && range_in_hard_reg_set_p (live_hard_regs
, i
, iri
->nregs
))
577 SET_HARD_REG_BIT (start_chains_set
, i
);
578 remove_range_from_hard_reg_set (&live_hard_regs
, i
, iri
->nregs
);
581 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
583 struct incoming_reg_info
*iri
= p
->incoming
+ i
;
584 if (TEST_HARD_REG_BIT (start_chains_set
, i
))
588 fprintf (dump_file
, "opening incoming chain\n");
589 chain
= create_new_chain (i
, iri
->nregs
, NULL
, NULL
, NO_REGS
);
590 bitmap_set_bit (&p
->incoming_open_chains_set
, chain
->id
);
595 /* Record in RI that the block corresponding to it has an incoming
596 live value, described by CHAIN. */
598 set_incoming_from_chain (struct bb_rename_info
*ri
, du_head_p chain
)
601 int incoming_nregs
= ri
->incoming
[chain
->regno
].nregs
;
604 /* If we've recorded the same information before, everything is fine. */
605 if (incoming_nregs
== chain
->nregs
)
608 fprintf (dump_file
, "reg %d/%d already recorded\n",
609 chain
->regno
, chain
->nregs
);
613 /* If we have no information for any of the involved registers, update
614 the incoming array. */
615 nregs
= chain
->nregs
;
617 if (ri
->incoming
[chain
->regno
+ nregs
].nregs
!= 0
618 || ri
->incoming
[chain
->regno
+ nregs
].unusable
)
622 nregs
= chain
->nregs
;
623 ri
->incoming
[chain
->regno
].nregs
= nregs
;
625 ri
->incoming
[chain
->regno
+ nregs
].nregs
= -nregs
;
627 fprintf (dump_file
, "recorded reg %d/%d\n",
628 chain
->regno
, chain
->nregs
);
632 /* There must be some kind of conflict. Prevent both the old and
633 new ranges from being used. */
634 if (incoming_nregs
< 0)
635 ri
->incoming
[chain
->regno
+ incoming_nregs
].unusable
= true;
636 for (i
= 0; i
< chain
->nregs
; i
++)
637 ri
->incoming
[chain
->regno
+ i
].unusable
= true;
640 /* Merge the two chains C1 and C2 so that all conflict information is
641 recorded and C1, and the id of C2 is changed to that of C1. */
643 merge_chains (du_head_p c1
, du_head_p c2
)
648 if (c2
->first
!= NULL
)
650 if (c1
->first
== NULL
)
651 c1
->first
= c2
->first
;
653 c1
->last
->next_use
= c2
->first
;
657 c2
->first
= c2
->last
= NULL
;
660 IOR_HARD_REG_SET (c1
->hard_conflicts
, c2
->hard_conflicts
);
661 bitmap_ior_into (&c1
->conflicts
, &c2
->conflicts
);
663 c1
->need_caller_save_reg
|= c2
->need_caller_save_reg
;
664 c1
->cannot_rename
|= c2
->cannot_rename
;
667 /* Analyze the current function and build chains for renaming. */
670 regrename_analyze (bitmap bb_mask
)
672 struct bb_rename_info
*rename_info
;
676 int *inverse_postorder
;
678 inverse_postorder
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
679 n_bbs
= pre_and_rev_post_order_compute (NULL
, inverse_postorder
, false);
681 /* Gather some information about the blocks in this function. */
682 rename_info
= XCNEWVEC (struct bb_rename_info
, n_basic_blocks_for_fn (cfun
));
684 FOR_EACH_BB_FN (bb
, cfun
)
686 struct bb_rename_info
*ri
= rename_info
+ i
;
688 if (bb_mask
!= NULL
&& !bitmap_bit_p (bb_mask
, bb
->index
))
696 id_to_chain
.create (0);
697 bitmap_initialize (&open_chains_set
, &bitmap_default_obstack
);
699 /* The order in which we visit blocks ensures that whenever
700 possible, we only process a block after at least one of its
701 predecessors, which provides a "seeding" effect to make the logic
702 in set_incoming_from_chain and init_rename_info useful. */
704 for (i
= 0; i
< n_bbs
; i
++)
706 basic_block bb1
= BASIC_BLOCK_FOR_FN (cfun
, inverse_postorder
[i
]);
707 struct bb_rename_info
*this_info
;
711 int old_length
= id_to_chain
.length ();
713 this_info
= (struct bb_rename_info
*) bb1
->aux
;
714 if (this_info
== NULL
)
718 fprintf (dump_file
, "\nprocessing block %d:\n", bb1
->index
);
720 init_rename_info (this_info
, bb1
);
722 success
= build_def_use (bb1
);
726 fprintf (dump_file
, "failed\n");
728 id_to_chain
.truncate (old_length
);
729 current_id
= old_length
;
730 bitmap_clear (&this_info
->incoming_open_chains_set
);
732 if (insn_rr
.exists ())
735 FOR_BB_INSNS (bb1
, insn
)
737 insn_rr_info
*p
= &insn_rr
[INSN_UID (insn
)];
745 dump_def_use_chain (old_length
);
746 bitmap_copy (&this_info
->open_chains_set
, &open_chains_set
);
748 /* Add successor blocks to the worklist if necessary, and record
749 data about our own open chains at the end of this block, which
750 will be used to pre-open chains when processing the successors. */
751 FOR_EACH_EDGE (e
, ei
, bb1
->succs
)
753 struct bb_rename_info
*dest_ri
;
754 struct du_head
*chain
;
757 fprintf (dump_file
, "successor block %d\n", e
->dest
->index
);
759 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
761 dest_ri
= (struct bb_rename_info
*)e
->dest
->aux
;
764 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
765 set_incoming_from_chain (dest_ri
, chain
);
769 free (inverse_postorder
);
771 /* Now, combine the chains data we have gathered across basic block
774 For every basic block, there may be chains open at the start, or at the
775 end. Rather than exclude them from renaming, we look for open chains
776 with matching registers at the other side of the CFG edge.
778 For a given chain using register R, open at the start of block B, we
779 must find an open chain using R on the other side of every edge leading
780 to B, if the register is live across this edge. In the code below,
781 N_PREDS_USED counts the number of edges where the register is live, and
782 N_PREDS_JOINED counts those where we found an appropriate chain for
785 We perform the analysis for both incoming and outgoing edges, but we
786 only need to merge once (in the second part, after verifying outgoing
788 FOR_EACH_BB_FN (bb
, cfun
)
790 struct bb_rename_info
*bb_ri
= (struct bb_rename_info
*) bb
->aux
;
798 fprintf (dump_file
, "processing bb %d in edges\n", bb
->index
);
800 EXECUTE_IF_SET_IN_BITMAP (&bb_ri
->incoming_open_chains_set
, 0, j
, bi
)
804 struct du_head
*chain
= regrename_chain_from_id (j
);
805 int n_preds_used
= 0, n_preds_joined
= 0;
807 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
809 struct bb_rename_info
*src_ri
;
813 bool success
= false;
815 REG_SET_TO_HARD_REG_SET (live
, df_get_live_out (e
->src
));
816 if (!range_overlaps_hard_reg_set_p (live
, chain
->regno
,
821 if (e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
))
824 src_ri
= (struct bb_rename_info
*)e
->src
->aux
;
828 EXECUTE_IF_SET_IN_BITMAP (&src_ri
->open_chains_set
,
831 struct du_head
*outgoing_chain
= regrename_chain_from_id (k
);
833 if (outgoing_chain
->regno
== chain
->regno
834 && outgoing_chain
->nregs
== chain
->nregs
)
841 if (!success
&& dump_file
)
842 fprintf (dump_file
, "failure to match with pred block %d\n",
845 if (n_preds_joined
< n_preds_used
)
848 fprintf (dump_file
, "cannot rename chain %d\n", j
);
849 chain
->cannot_rename
= 1;
853 FOR_EACH_BB_FN (bb
, cfun
)
855 struct bb_rename_info
*bb_ri
= (struct bb_rename_info
*) bb
->aux
;
863 fprintf (dump_file
, "processing bb %d out edges\n", bb
->index
);
865 EXECUTE_IF_SET_IN_BITMAP (&bb_ri
->open_chains_set
, 0, j
, bi
)
869 struct du_head
*chain
= regrename_chain_from_id (j
);
870 int n_succs_used
= 0, n_succs_joined
= 0;
872 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
874 bool printed
= false;
875 struct bb_rename_info
*dest_ri
;
880 REG_SET_TO_HARD_REG_SET (live
, df_get_live_in (e
->dest
));
881 if (!range_overlaps_hard_reg_set_p (live
, chain
->regno
,
887 dest_ri
= (struct bb_rename_info
*)e
->dest
->aux
;
891 EXECUTE_IF_SET_IN_BITMAP (&dest_ri
->incoming_open_chains_set
,
894 struct du_head
*incoming_chain
= regrename_chain_from_id (k
);
896 if (incoming_chain
->regno
== chain
->regno
897 && incoming_chain
->nregs
== chain
->nregs
)
903 "merging blocks for edge %d -> %d\n",
904 e
->src
->index
, e
->dest
->index
);
907 " merging chains %d (->%d) and %d (->%d) [%s]\n",
908 k
, incoming_chain
->id
, j
, chain
->id
,
909 reg_names
[incoming_chain
->regno
]);
912 merge_chains (chain
, incoming_chain
);
918 if (n_succs_joined
< n_succs_used
)
921 fprintf (dump_file
, "cannot rename chain %d\n",
923 chain
->cannot_rename
= 1;
930 FOR_EACH_BB_FN (bb
, cfun
)
935 regrename_do_replace (struct du_head
*head
, int reg
)
937 struct du_chain
*chain
;
938 unsigned int base_regno
= head
->regno
;
941 for (chain
= head
->first
; chain
; chain
= chain
->next_use
)
943 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
944 struct reg_attrs
*attr
= REG_ATTRS (*chain
->loc
);
945 int reg_ptr
= REG_POINTER (*chain
->loc
);
947 if (DEBUG_INSN_P (chain
->insn
) && REGNO (*chain
->loc
) != base_regno
)
948 INSN_VAR_LOCATION_LOC (chain
->insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
951 *chain
->loc
= gen_raw_REG (GET_MODE (*chain
->loc
), reg
);
952 if (regno
>= FIRST_PSEUDO_REGISTER
)
953 ORIGINAL_REGNO (*chain
->loc
) = regno
;
954 REG_ATTRS (*chain
->loc
) = attr
;
955 REG_POINTER (*chain
->loc
) = reg_ptr
;
958 df_insn_rescan (chain
->insn
);
961 mode
= GET_MODE (*head
->first
->loc
);
963 head
->nregs
= hard_regno_nregs
[reg
][mode
];
967 /* True if we found a register with a size mismatch, which means that we
968 can't track its lifetime accurately. If so, we abort the current block
970 static bool fail_current_block
;
972 /* Return true if OP is a reg for which all bits are set in PSET, false
973 if all bits are clear.
974 In other cases, set fail_current_block and return false. */
977 verify_reg_in_set (rtx op
, HARD_REG_SET
*pset
)
979 unsigned regno
, nregs
;
980 bool all_live
, all_dead
;
985 nregs
= REG_NREGS (op
);
986 all_live
= all_dead
= true;
988 if (TEST_HARD_REG_BIT (*pset
, regno
+ nregs
))
992 if (!all_dead
&& !all_live
)
994 fail_current_block
= true;
1000 /* Return true if OP is a reg that is being tracked already in some form.
1001 May set fail_current_block if it sees an unhandled case of overlap. */
1004 verify_reg_tracked (rtx op
)
1006 return (verify_reg_in_set (op
, &live_hard_regs
)
1007 || verify_reg_in_set (op
, &live_in_chains
));
1010 /* Called through note_stores. DATA points to a rtx_code, either SET or
1011 CLOBBER, which tells us which kind of rtx to look at. If we have a
1012 match, record the set register in live_hard_regs and in the hard_conflicts
1013 bitmap of open chains. */
1016 note_sets_clobbers (rtx x
, const_rtx set
, void *data
)
1018 enum rtx_code code
= *(enum rtx_code
*)data
;
1019 struct du_head
*chain
;
1021 if (GET_CODE (x
) == SUBREG
)
1023 if (!REG_P (x
) || GET_CODE (set
) != code
)
1025 /* There must not be pseudos at this point. */
1026 gcc_assert (HARD_REGISTER_P (x
));
1027 add_to_hard_reg_set (&live_hard_regs
, GET_MODE (x
), REGNO (x
));
1028 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
1029 add_to_hard_reg_set (&chain
->hard_conflicts
, GET_MODE (x
), REGNO (x
));
1033 scan_rtx_reg (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
1038 unsigned this_regno
= REGNO (x
);
1039 int this_nregs
= REG_NREGS (x
);
1041 if (action
== mark_write
)
1044 create_new_chain (this_regno
, this_nregs
, loc
, insn
, cl
);
1048 if ((type
== OP_OUT
) != (action
== terminate_write
|| action
== mark_access
))
1051 for (p
= &open_chains
; *p
;)
1053 struct du_head
*head
= *p
;
1054 struct du_head
*next
= head
->next_chain
;
1055 int exact_match
= (head
->regno
== this_regno
1056 && head
->nregs
== this_nregs
);
1057 int superset
= (this_regno
<= head
->regno
1058 && this_regno
+ this_nregs
>= head
->regno
+ head
->nregs
);
1059 int subset
= (this_regno
>= head
->regno
1060 && this_regno
+ this_nregs
<= head
->regno
+ head
->nregs
);
1062 if (!bitmap_bit_p (&open_chains_set
, head
->id
)
1063 || head
->regno
+ head
->nregs
<= this_regno
1064 || this_regno
+ this_nregs
<= head
->regno
)
1066 p
= &head
->next_chain
;
1070 if (action
== mark_read
|| action
== mark_access
)
1072 /* ??? Class NO_REGS can happen if the md file makes use of
1073 EXTRA_CONSTRAINTS to match registers. Which is arguably
1074 wrong, but there we are. */
1076 if (cl
== NO_REGS
|| (!exact_match
&& !DEBUG_INSN_P (insn
)))
1080 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1081 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1082 scan_actions_name
[(int) action
]);
1083 head
->cannot_rename
= 1;
1086 unsigned nregs
= this_nregs
;
1087 head
->regno
= this_regno
;
1088 head
->nregs
= this_nregs
;
1090 SET_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
1093 "Widening register in chain %s (%d) at insn %d\n",
1094 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
));
1098 fail_current_block
= true;
1101 "Failing basic block due to unhandled overlap\n");
1106 struct du_chain
*this_du
;
1107 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
1108 this_du
->next_use
= 0;
1110 this_du
->insn
= insn
;
1112 if (head
->first
== NULL
)
1113 head
->first
= this_du
;
1115 head
->last
->next_use
= this_du
;
1116 record_operand_use (head
, this_du
);
1117 head
->last
= this_du
;
1119 /* Avoid adding the same location in a DEBUG_INSN multiple times,
1120 which could happen with non-exact overlap. */
1121 if (DEBUG_INSN_P (insn
))
1123 /* Otherwise, find any other chains that do not match exactly;
1124 ensure they all get marked unrenamable. */
1125 p
= &head
->next_chain
;
1129 /* Whether the terminated chain can be used for renaming
1130 depends on the action and this being an exact match.
1131 In either case, we remove this element from open_chains. */
1133 if ((action
== terminate_dead
|| action
== terminate_write
)
1134 && (superset
|| subset
))
1138 if (subset
&& !superset
)
1139 head
->cannot_rename
= 1;
1140 bitmap_clear_bit (&open_chains_set
, head
->id
);
1142 nregs
= head
->nregs
;
1145 CLEAR_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
1146 if (subset
&& !superset
1147 && (head
->regno
+ nregs
< this_regno
1148 || head
->regno
+ nregs
>= this_regno
+ this_nregs
))
1149 SET_HARD_REG_BIT (live_hard_regs
, head
->regno
+ nregs
);
1155 "Closing chain %s (%d) at insn %d (%s%s)\n",
1156 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1157 scan_actions_name
[(int) action
],
1158 superset
? ", superset" : subset
? ", subset" : "");
1160 else if (action
== terminate_dead
|| action
== terminate_write
)
1162 /* In this case, tracking liveness gets too hard. Fail the
1163 entire basic block. */
1166 "Failing basic block due to unhandled overlap\n");
1167 fail_current_block
= true;
1172 head
->cannot_rename
= 1;
1175 "Cannot rename chain %s (%d) at insn %d (%s)\n",
1176 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
1177 scan_actions_name
[(int) action
]);
1178 p
= &head
->next_chain
;
1183 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1184 BASE_REG_CLASS depending on how the register is being considered. */
1187 scan_rtx_address (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
,
1188 enum scan_actions action
, machine_mode mode
,
1192 RTX_CODE code
= GET_CODE (x
);
1196 if (action
== mark_write
|| action
== mark_access
)
1203 rtx orig_op0
= XEXP (x
, 0);
1204 rtx orig_op1
= XEXP (x
, 1);
1205 RTX_CODE code0
= GET_CODE (orig_op0
);
1206 RTX_CODE code1
= GET_CODE (orig_op1
);
1211 enum rtx_code index_code
= SCRATCH
;
1213 if (GET_CODE (op0
) == SUBREG
)
1215 op0
= SUBREG_REG (op0
);
1216 code0
= GET_CODE (op0
);
1219 if (GET_CODE (op1
) == SUBREG
)
1221 op1
= SUBREG_REG (op1
);
1222 code1
= GET_CODE (op1
);
1225 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
1226 || code0
== ZERO_EXTEND
|| code1
== MEM
)
1228 locI
= &XEXP (x
, 0);
1229 locB
= &XEXP (x
, 1);
1230 index_code
= GET_CODE (*locI
);
1232 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
1233 || code1
== ZERO_EXTEND
|| code0
== MEM
)
1235 locI
= &XEXP (x
, 1);
1236 locB
= &XEXP (x
, 0);
1237 index_code
= GET_CODE (*locI
);
1239 else if (code0
== CONST_INT
|| code0
== CONST
1240 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
1242 locB
= &XEXP (x
, 1);
1243 index_code
= GET_CODE (XEXP (x
, 0));
1245 else if (code1
== CONST_INT
|| code1
== CONST
1246 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
1248 locB
= &XEXP (x
, 0);
1249 index_code
= GET_CODE (XEXP (x
, 1));
1251 else if (code0
== REG
&& code1
== REG
)
1254 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
1256 if (REGNO_OK_FOR_INDEX_P (regno1
)
1257 && regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
))
1259 else if (REGNO_OK_FOR_INDEX_P (regno0
)
1260 && regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
1262 else if (regno_ok_for_base_p (regno0
, mode
, as
, PLUS
, REG
)
1263 || REGNO_OK_FOR_INDEX_P (regno1
))
1265 else if (regno_ok_for_base_p (regno1
, mode
, as
, PLUS
, REG
))
1270 locI
= &XEXP (x
, index_op
);
1271 locB
= &XEXP (x
, !index_op
);
1272 index_code
= GET_CODE (*locI
);
1274 else if (code0
== REG
)
1276 locI
= &XEXP (x
, 0);
1277 locB
= &XEXP (x
, 1);
1278 index_code
= GET_CODE (*locI
);
1280 else if (code1
== REG
)
1282 locI
= &XEXP (x
, 1);
1283 locB
= &XEXP (x
, 0);
1284 index_code
= GET_CODE (*locI
);
1288 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
, as
);
1290 scan_rtx_address (insn
, locB
,
1291 base_reg_class (mode
, as
, PLUS
, index_code
),
1303 #ifndef AUTO_INC_DEC
1304 /* If the target doesn't claim to handle autoinc, this must be
1305 something special, like a stack push. Kill this chain. */
1306 action
= mark_all_read
;
1311 scan_rtx_address (insn
, &XEXP (x
, 0),
1312 base_reg_class (GET_MODE (x
), MEM_ADDR_SPACE (x
),
1314 action
, GET_MODE (x
), MEM_ADDR_SPACE (x
));
1318 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
);
1325 fmt
= GET_RTX_FORMAT (code
);
1326 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1329 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
, as
);
1330 else if (fmt
[i
] == 'E')
1331 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1332 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
, as
);
1337 scan_rtx (rtx_insn
*insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
1342 enum rtx_code code
= GET_CODE (x
);
1345 code
= GET_CODE (x
);
1357 scan_rtx_reg (insn
, loc
, cl
, action
, type
);
1361 scan_rtx_address (insn
, &XEXP (x
, 0),
1362 base_reg_class (GET_MODE (x
), MEM_ADDR_SPACE (x
),
1364 action
, GET_MODE (x
), MEM_ADDR_SPACE (x
));
1368 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
);
1369 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
1370 (GET_CODE (PATTERN (insn
)) == COND_EXEC
1371 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
1374 case STRICT_LOW_PART
:
1375 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
1376 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
);
1381 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
1382 (type
== OP_IN
? OP_IN
:
1383 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
));
1384 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
);
1385 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
);
1394 /* Should only happen inside MEM. */
1398 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
1399 (GET_CODE (PATTERN (insn
)) == COND_EXEC
1400 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
1404 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
);
1406 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
);
1413 fmt
= GET_RTX_FORMAT (code
);
1414 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1417 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
);
1418 else if (fmt
[i
] == 'E')
1419 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
1420 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
);
1424 /* Hide operands of the current insn (of which there are N_OPS) by
1425 substituting cc0 for them.
1426 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
1427 For every bit set in DO_NOT_HIDE, we leave the operand alone.
1428 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
1429 and earlyclobbers. */
1432 hide_operands (int n_ops
, rtx
*old_operands
, rtx
*old_dups
,
1433 unsigned HOST_WIDE_INT do_not_hide
, bool inout_and_ec_only
)
1436 const operand_alternative
*op_alt
= which_op_alt ();
1437 for (i
= 0; i
< n_ops
; i
++)
1439 old_operands
[i
] = recog_data
.operand
[i
];
1440 /* Don't squash match_operator or match_parallel here, since
1441 we don't know that all of the contained registers are
1442 reachable by proper operands. */
1443 if (recog_data
.constraints
[i
][0] == '\0')
1445 if (do_not_hide
& (1 << i
))
1447 if (!inout_and_ec_only
|| recog_data
.operand_type
[i
] == OP_INOUT
1448 || op_alt
[i
].earlyclobber
)
1449 *recog_data
.operand_loc
[i
] = cc0_rtx
;
1451 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1453 int opn
= recog_data
.dup_num
[i
];
1454 old_dups
[i
] = *recog_data
.dup_loc
[i
];
1455 if (do_not_hide
& (1 << opn
))
1457 if (!inout_and_ec_only
|| recog_data
.operand_type
[opn
] == OP_INOUT
1458 || op_alt
[opn
].earlyclobber
)
1459 *recog_data
.dup_loc
[i
] = cc0_rtx
;
1463 /* Undo the substitution performed by hide_operands. INSN is the insn we
1464 are processing; the arguments are the same as in hide_operands. */
1467 restore_operands (rtx_insn
*insn
, int n_ops
, rtx
*old_operands
, rtx
*old_dups
)
1470 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1471 *recog_data
.dup_loc
[i
] = old_dups
[i
];
1472 for (i
= 0; i
< n_ops
; i
++)
1473 *recog_data
.operand_loc
[i
] = old_operands
[i
];
1474 if (recog_data
.n_dups
)
1475 df_insn_rescan (insn
);
1478 /* For each output operand of INSN, call scan_rtx to create a new
1479 open chain. Do this only for normal or earlyclobber outputs,
1480 depending on EARLYCLOBBER. If INSN_INFO is nonnull, use it to
1481 record information about the operands in the insn. */
1484 record_out_operands (rtx_insn
*insn
, bool earlyclobber
, insn_rr_info
*insn_info
)
1486 int n_ops
= recog_data
.n_operands
;
1487 const operand_alternative
*op_alt
= which_op_alt ();
1491 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1493 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1494 rtx
*loc
= (i
< n_ops
1495 ? recog_data
.operand_loc
[opn
]
1496 : recog_data
.dup_loc
[i
- n_ops
]);
1498 enum reg_class cl
= alternative_class (op_alt
, opn
);
1500 struct du_head
*prev_open
;
1502 if (recog_data
.operand_type
[opn
] != OP_OUT
1503 || op_alt
[opn
].earlyclobber
!= earlyclobber
)
1507 cur_operand
= insn_info
->op_info
+ i
;
1509 prev_open
= open_chains
;
1510 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
);
1512 /* ??? Many targets have output constraints on the SET_DEST
1513 of a call insn, which is stupid, since these are certainly
1514 ABI defined hard registers. For these, and for asm operands
1515 that originally referenced hard registers, we must record that
1516 the chain cannot be renamed. */
1518 || (asm_noperands (PATTERN (insn
)) > 0
1520 && REGNO (op
) == ORIGINAL_REGNO (op
)))
1522 if (prev_open
!= open_chains
)
1523 open_chains
->cannot_rename
= 1;
1529 /* Build def/use chain. */
1532 build_def_use (basic_block bb
)
1535 unsigned HOST_WIDE_INT untracked_operands
;
1537 fail_current_block
= false;
1539 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1541 if (NONDEBUG_INSN_P (insn
))
1545 rtx old_operands
[MAX_RECOG_OPERANDS
];
1546 rtx old_dups
[MAX_DUP_OPERANDS
];
1549 enum rtx_code set_code
= SET
;
1550 enum rtx_code clobber_code
= CLOBBER
;
1551 insn_rr_info
*insn_info
= NULL
;
1553 /* Process the insn, determining its effect on the def-use
1554 chains and live hard registers. We perform the following
1555 steps with the register references in the insn, simulating
1557 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1558 by creating chains and marking hard regs live.
1559 (2) Any read outside an operand causes any chain it overlaps
1560 with to be marked unrenamable.
1561 (3) Any read inside an operand is added if there's already
1562 an open chain for it.
1563 (4) For any REG_DEAD note we find, close open chains that
1565 (5) For any non-earlyclobber write we find, close open chains
1567 (6) For any non-earlyclobber write we find in an operand, make
1568 a new chain or mark the hard register as live.
1569 (7) For any REG_UNUSED, close any chains we just opened.
1571 We cannot deal with situations where we track a reg in one mode
1572 and see a reference in another mode; these will cause the chain
1573 to be marked unrenamable or even cause us to abort the entire
1576 extract_constrain_insn (insn
);
1577 preprocess_constraints (insn
);
1578 const operand_alternative
*op_alt
= which_op_alt ();
1579 n_ops
= recog_data
.n_operands
;
1580 untracked_operands
= 0;
1582 if (insn_rr
.exists ())
1584 insn_info
= &insn_rr
[INSN_UID (insn
)];
1585 insn_info
->op_info
= XOBNEWVEC (&rename_obstack
, operand_rr_info
,
1586 recog_data
.n_operands
);
1587 memset (insn_info
->op_info
, 0,
1588 sizeof (operand_rr_info
) * recog_data
.n_operands
);
1591 /* Simplify the code below by promoting OP_OUT to OP_INOUT in
1592 predicated instructions, but only for register operands
1593 that are already tracked, so that we can create a chain
1594 when the first SET makes a register live. */
1596 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1597 for (i
= 0; i
< n_ops
; ++i
)
1599 rtx op
= recog_data
.operand
[i
];
1600 int matches
= op_alt
[i
].matches
;
1601 if (matches
>= 0 || op_alt
[i
].matched
>= 0
1602 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1604 recog_data
.operand_type
[i
] = OP_INOUT
;
1605 /* A special case to deal with instruction patterns that
1606 have matching operands with different modes. If we're
1607 not already tracking such a reg, we won't start here,
1608 and we must instead make sure to make the operand visible
1609 to the machinery that tracks hard registers. */
1611 && (GET_MODE_SIZE (recog_data
.operand_mode
[i
])
1612 != GET_MODE_SIZE (recog_data
.operand_mode
[matches
]))
1613 && !verify_reg_in_set (op
, &live_in_chains
))
1615 untracked_operands
|= 1 << i
;
1616 untracked_operands
|= 1 << matches
;
1619 /* If there's an in-out operand with a register that is not
1620 being tracked at all yet, open a chain. */
1621 if (recog_data
.operand_type
[i
] == OP_INOUT
1622 && !(untracked_operands
& (1 << i
))
1624 && !verify_reg_tracked (op
))
1625 create_new_chain (REGNO (op
), REG_NREGS (op
), NULL
, NULL
,
1629 if (fail_current_block
)
1632 /* Step 1a: Mark hard registers that are clobbered in this insn,
1633 outside an operand, as live. */
1634 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1636 note_stores (PATTERN (insn
), note_sets_clobbers
, &clobber_code
);
1637 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1639 /* Step 1b: Begin new chains for earlyclobbered writes inside
1641 record_out_operands (insn
, true, insn_info
);
1643 /* Step 2: Mark chains for which we have reads outside operands
1645 We do this by munging all operands into CC0, and closing
1646 everything remaining. */
1648 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1650 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, mark_all_read
, OP_IN
);
1651 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1653 /* Step 2B: Can't rename function call argument registers. */
1654 if (CALL_P (insn
) && CALL_INSN_FUNCTION_USAGE (insn
))
1655 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
1656 NO_REGS
, mark_all_read
, OP_IN
);
1658 /* Step 2C: Can't rename asm operands that were originally
1660 if (asm_noperands (PATTERN (insn
)) > 0)
1661 for (i
= 0; i
< n_ops
; i
++)
1663 rtx
*loc
= recog_data
.operand_loc
[i
];
1667 && REGNO (op
) == ORIGINAL_REGNO (op
)
1668 && (recog_data
.operand_type
[i
] == OP_IN
1669 || recog_data
.operand_type
[i
] == OP_INOUT
))
1670 scan_rtx (insn
, loc
, NO_REGS
, mark_all_read
, OP_IN
);
1673 /* Step 3: Append to chains for reads inside operands. */
1674 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1676 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1677 rtx
*loc
= (i
< n_ops
1678 ? recog_data
.operand_loc
[opn
]
1679 : recog_data
.dup_loc
[i
- n_ops
]);
1680 enum reg_class cl
= alternative_class (op_alt
, opn
);
1681 enum op_type type
= recog_data
.operand_type
[opn
];
1683 /* Don't scan match_operand here, since we've no reg class
1684 information to pass down. Any operands that we could
1685 substitute in will be represented elsewhere. */
1686 if (recog_data
.constraints
[opn
][0] == '\0'
1687 || untracked_operands
& (1 << opn
))
1691 cur_operand
= i
== opn
? insn_info
->op_info
+ i
: NULL
;
1692 if (op_alt
[opn
].is_address
)
1693 scan_rtx_address (insn
, loc
, cl
, mark_read
,
1694 VOIDmode
, ADDR_SPACE_GENERIC
);
1696 scan_rtx (insn
, loc
, cl
, mark_read
, type
);
1700 /* Step 3B: Record updates for regs in REG_INC notes, and
1701 source regs in REG_FRAME_RELATED_EXPR notes. */
1702 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1703 if (REG_NOTE_KIND (note
) == REG_INC
1704 || REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1705 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
1708 /* Step 4: Close chains for registers that die here, unless
1709 the register is mentioned in a REG_UNUSED note. In that
1710 case we keep the chain open until step #7 below to ensure
1711 it conflicts with other output operands of this insn.
1712 See PR 52573. Arguably the insn should not have both
1713 notes; it has proven difficult to fix that without
1714 other undesirable side effects. */
1715 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1716 if (REG_NOTE_KIND (note
) == REG_DEAD
1717 && !find_regno_note (insn
, REG_UNUSED
, REGNO (XEXP (note
, 0))))
1719 remove_from_hard_reg_set (&live_hard_regs
,
1720 GET_MODE (XEXP (note
, 0)),
1721 REGNO (XEXP (note
, 0)));
1722 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1726 /* Step 4B: If this is a call, any chain live at this point
1727 requires a caller-saved reg. */
1731 for (p
= open_chains
; p
; p
= p
->next_chain
)
1732 p
->need_caller_save_reg
= 1;
1735 /* Step 5: Close open chains that overlap writes. Similar to
1736 step 2, we hide in-out operands, since we do not want to
1737 close these chains. We also hide earlyclobber operands,
1738 since we've opened chains for them in step 1, and earlier
1739 chains they would overlap with must have been closed at
1740 the previous insn at the latest, as such operands cannot
1741 possibly overlap with any input operands. */
1743 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1745 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
);
1746 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1748 /* Step 6a: Mark hard registers that are set in this insn,
1749 outside an operand, as live. */
1750 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1752 note_stores (PATTERN (insn
), note_sets_clobbers
, &set_code
);
1753 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1755 /* Step 6b: Begin new chains for writes inside operands. */
1756 record_out_operands (insn
, false, insn_info
);
1758 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1759 notes for update. */
1760 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1761 if (REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1762 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_access
,
1765 /* Step 7: Close chains for registers that were never
1766 really used here. */
1767 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1768 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
1770 remove_from_hard_reg_set (&live_hard_regs
,
1771 GET_MODE (XEXP (note
, 0)),
1772 REGNO (XEXP (note
, 0)));
1773 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1777 else if (DEBUG_INSN_P (insn
)
1778 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn
)))
1780 scan_rtx (insn
, &INSN_VAR_LOCATION_LOC (insn
),
1781 ALL_REGS
, mark_read
, OP_IN
);
1783 if (insn
== BB_END (bb
))
1787 if (fail_current_block
)
1793 /* Initialize the register renamer. If INSN_INFO is true, ensure that
1794 insn_rr is nonnull. */
1796 regrename_init (bool insn_info
)
1798 gcc_obstack_init (&rename_obstack
);
1801 insn_rr
.safe_grow_cleared (get_max_uid ());
1804 /* Free all global data used by the register renamer. */
1806 regrename_finish (void)
1810 obstack_free (&rename_obstack
, NULL
);
1813 /* Perform register renaming on the current function. */
1816 regrename_optimize (void)
1818 df_set_flags (DF_LR_RUN_DCE
);
1819 df_note_add_problem ();
1821 df_set_flags (DF_DEFER_INSN_RESCAN
);
1823 regrename_init (false);
1825 regrename_analyze (NULL
);
1829 regrename_finish ();
1836 const pass_data pass_data_regrename
=
1838 RTL_PASS
, /* type */
1840 OPTGROUP_NONE
, /* optinfo_flags */
1841 TV_RENAME_REGISTERS
, /* tv_id */
1842 0, /* properties_required */
1843 0, /* properties_provided */
1844 0, /* properties_destroyed */
1845 0, /* todo_flags_start */
1846 TODO_df_finish
, /* todo_flags_finish */
1849 class pass_regrename
: public rtl_opt_pass
1852 pass_regrename (gcc::context
*ctxt
)
1853 : rtl_opt_pass (pass_data_regrename
, ctxt
)
1856 /* opt_pass methods: */
1857 virtual bool gate (function
*)
1859 return (optimize
> 0 && (flag_rename_registers
));
1862 virtual unsigned int execute (function
*) { return regrename_optimize (); }
1864 }; // class pass_regrename
1869 make_pass_regrename (gcc::context
*ctxt
)
1871 return new pass_regrename (ctxt
);