1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
3 2010 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
25 #include "rtl-error.h"
27 #include "insn-config.h"
29 #include "addresses.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
39 #include "tree-pass.h"
43 /* This file implements the RTL register renaming pass of the compiler. It is
44 a semi-local pass whose goal is to maximize the usage of the register file
45 of the processor by substituting registers for others in the solution given
46 by the register allocator. The algorithm is as follows:
48 1. Local def/use chains are built: within each basic block, chains are
49 opened and closed; if a chain isn't closed at the end of the block,
52 2. 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 3. 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 4. 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."
70 /* We keep linked lists of DU_HEAD structures, each of which describes
71 a chain of occurrences of a reg. */
75 struct du_head
*next_chain
;
76 /* The first and last elements of this chain. */
77 struct du_chain
*first
, *last
;
78 /* Describes the register being tracked. */
79 unsigned regno
, nregs
;
81 /* A unique id to be used as an index into the conflicts bitmaps. */
83 /* A bitmap to record conflicts with other chains. */
84 bitmap_head conflicts
;
85 /* Conflicts with untracked hard registers. */
86 HARD_REG_SET hard_conflicts
;
88 /* Nonzero if the chain crosses a call. */
89 unsigned int need_caller_save_reg
:1;
90 /* Nonzero if the register is used in a way that prevents renaming,
91 such as the SET_DEST of a CALL_INSN or an asm operand that used
92 to be a hard register. */
93 unsigned int cannot_rename
:1;
96 /* This struct describes a single occurrence of a register. */
99 /* Links to the next occurrence of the register. */
100 struct du_chain
*next_use
;
102 /* The insn where the register appears. */
104 /* The location inside the insn. */
106 /* The register class required by the insn at this location. */
107 ENUM_BITFIELD(reg_class
) cl
: 16;
117 /* mark_access is for marking the destination regs in
118 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
119 note is updated properly. */
123 static const char * const scan_actions_name
[] =
133 /* TICK and THIS_TICK are used to record the last time we saw each
135 static int tick
[FIRST_PSEUDO_REGISTER
];
136 static int this_tick
= 0;
138 static struct obstack rename_obstack
;
140 static void do_replace (struct du_head
*, int);
141 static void scan_rtx (rtx
, rtx
*, enum reg_class
, enum scan_actions
,
144 typedef struct du_head
*du_head_p
;
145 DEF_VEC_P (du_head_p
);
146 DEF_VEC_ALLOC_P (du_head_p
, heap
);
148 /* The id to be given to the next opened chain. */
149 static unsigned current_id
;
151 /* A mapping of unique id numbers to chains. */
152 static VEC(du_head_p
, heap
) *id_to_chain
;
154 /* List of currently open chains, and closed chains that can be renamed. */
155 static struct du_head
*open_chains
;
156 static struct du_head
*closed_chains
;
158 /* Bitmap of open chains. The bits set always match the list found in
160 static bitmap_head open_chains_set
;
162 /* Record the registers being tracked in open_chains. */
163 static HARD_REG_SET live_in_chains
;
165 /* Record the registers that are live but not tracked. The intersection
166 between this and live_in_chains is empty. */
167 static HARD_REG_SET live_hard_regs
;
169 /* Dump all def/use chains in CHAINS to DUMP_FILE. */
172 dump_def_use_chain (struct du_head
*head
)
176 struct du_chain
*this_du
= head
->first
;
177 fprintf (dump_file
, "Register %s (%d):",
178 reg_names
[head
->regno
], head
->nregs
);
181 fprintf (dump_file
, " %d [%s]", INSN_UID (this_du
->insn
),
182 reg_class_names
[this_du
->cl
]);
183 this_du
= this_du
->next_use
;
185 fprintf (dump_file
, "\n");
186 head
= head
->next_chain
;
191 free_chain_data (void)
195 for (i
= 0; VEC_iterate(du_head_p
, id_to_chain
, i
, ptr
); i
++)
196 bitmap_clear (&ptr
->conflicts
);
198 VEC_free (du_head_p
, heap
, id_to_chain
);
201 /* Walk all chains starting with CHAINS and record that they conflict with
202 another chain whose id is ID. */
205 mark_conflict (struct du_head
*chains
, unsigned id
)
209 bitmap_set_bit (&chains
->conflicts
, id
);
210 chains
= chains
->next_chain
;
214 /* Create a new chain for THIS_NREGS registers starting at THIS_REGNO,
215 and record its occurrence in *LOC, which is being written to in INSN.
216 This access requires a register of class CL. */
219 create_new_chain (unsigned this_regno
, unsigned this_nregs
, rtx
*loc
,
220 rtx insn
, enum reg_class cl
)
222 struct du_head
*head
= XOBNEW (&rename_obstack
, struct du_head
);
223 struct du_chain
*this_du
;
226 head
->next_chain
= open_chains
;
228 head
->regno
= this_regno
;
229 head
->nregs
= this_nregs
;
230 head
->need_caller_save_reg
= 0;
231 head
->cannot_rename
= 0;
233 VEC_safe_push (du_head_p
, heap
, id_to_chain
, 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
;
279 /* For a def-use chain HEAD, find which registers overlap its lifetime and
280 set the corresponding bits in *PSET. */
283 merge_overlapping_regs (HARD_REG_SET
*pset
, struct du_head
*head
)
287 IOR_HARD_REG_SET (*pset
, head
->hard_conflicts
);
288 EXECUTE_IF_SET_IN_BITMAP (&head
->conflicts
, 0, i
, bi
)
290 du_head_p other
= VEC_index (du_head_p
, id_to_chain
, i
);
291 unsigned j
= other
->nregs
;
293 SET_HARD_REG_BIT (*pset
, other
->regno
+ j
);
297 /* Check if NEW_REG can be the candidate register to rename for
298 REG in THIS_HEAD chain. THIS_UNAVAILABLE is a set of unavailable hard
302 check_new_reg_p (int reg ATTRIBUTE_UNUSED
, int new_reg
,
303 struct du_head
*this_head
, HARD_REG_SET this_unavailable
)
305 enum machine_mode mode
= GET_MODE (*this_head
->first
->loc
);
306 int nregs
= hard_regno_nregs
[new_reg
][mode
];
308 struct du_chain
*tmp
;
310 for (i
= nregs
- 1; i
>= 0; --i
)
311 if (TEST_HARD_REG_BIT (this_unavailable
, new_reg
+ i
)
312 || fixed_regs
[new_reg
+ i
]
313 || global_regs
[new_reg
+ i
]
314 /* Can't use regs which aren't saved by the prologue. */
315 || (! df_regs_ever_live_p (new_reg
+ i
)
316 && ! call_used_regs
[new_reg
+ i
])
317 #ifdef LEAF_REGISTERS
318 /* We can't use a non-leaf register if we're in a
320 || (current_function_is_leaf
321 && !LEAF_REGISTERS
[new_reg
+ i
])
323 #ifdef HARD_REGNO_RENAME_OK
324 || ! 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 /* Process the closed chains starting with ALL_CHAINS and rename
345 registers if possible. */
347 rename_chains (du_head_p all_chains
)
349 HARD_REG_SET unavailable
;
351 CLEAR_HARD_REG_SET (unavailable
);
352 /* Don't clobber traceback for noreturn functions. */
353 if (frame_pointer_needed
)
355 add_to_hard_reg_set (&unavailable
, Pmode
, FRAME_POINTER_REGNUM
);
356 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
357 add_to_hard_reg_set (&unavailable
, Pmode
, HARD_FRAME_POINTER_REGNUM
);
363 int new_reg
, best_new_reg
, best_nregs
;
365 struct du_head
*this_head
= all_chains
;
366 struct du_chain
*tmp
;
367 HARD_REG_SET this_unavailable
;
368 int reg
= this_head
->regno
;
370 enum reg_class super_class
= NO_REGS
;
371 enum reg_class preferred_class
;
372 bool has_preferred_class
;
374 all_chains
= this_head
->next_chain
;
376 if (this_head
->cannot_rename
)
380 best_nregs
= this_head
->nregs
;
382 if (fixed_regs
[reg
] || global_regs
[reg
]
383 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
384 || (frame_pointer_needed
&& reg
== HARD_FRAME_POINTER_REGNUM
)
386 || (frame_pointer_needed
&& reg
== FRAME_POINTER_REGNUM
)
391 COPY_HARD_REG_SET (this_unavailable
, unavailable
);
393 /* Iterate over elements in the chain in order to:
394 1. Count number of uses, and narrow the set of registers we can
396 2. Compute the superunion of register classes in this chain. */
398 super_class
= NO_REGS
;
399 for (tmp
= this_head
->first
; tmp
; tmp
= tmp
->next_use
)
401 if (DEBUG_INSN_P (tmp
->insn
))
404 IOR_COMPL_HARD_REG_SET (this_unavailable
,
405 reg_class_contents
[tmp
->cl
]);
407 = reg_class_superunion
[(int) super_class
][(int) tmp
->cl
];
413 /* Further narrow the set of registers we can use for renaming.
414 If the chain needs a call-saved register, mark the call-used
415 registers as unavailable. */
416 if (this_head
->need_caller_save_reg
)
417 IOR_HARD_REG_SET (this_unavailable
, call_used_reg_set
);
419 /* And mark registers that overlap its lifetime as unavailable. */
420 merge_overlapping_regs (&this_unavailable
, this_head
);
422 /* Compute preferred rename class of super union of all the classes
425 = (enum reg_class
) targetm
.preferred_rename_class (super_class
);
427 /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
428 over registers that belong to PREFERRED_CLASS and try to find the
429 best register within the class. If that failed, we iterate in
430 the second pass over registers that don't belong to the class.
431 If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
432 ascending order without any preference. */
433 has_preferred_class
= (preferred_class
!= NO_REGS
);
434 for (pass
= (has_preferred_class
? 0 : 1); pass
< 2; pass
++)
436 for (new_reg
= 0; new_reg
< FIRST_PSEUDO_REGISTER
; new_reg
++)
438 if (has_preferred_class
439 && ((pass
== 0) != TEST_HARD_REG_BIT
440 (reg_class_contents
[preferred_class
], new_reg
)))
443 /* In the first pass, we force the renaming of registers that
444 don't belong to PREFERRED_CLASS to registers that do, even
445 though the latters were used not very long ago. */
446 if (check_new_reg_p (reg
, new_reg
, this_head
,
449 && (!TEST_HARD_REG_BIT
450 (reg_class_contents
[preferred_class
],
452 || tick
[best_new_reg
] > tick
[new_reg
]))
454 enum machine_mode mode
455 = GET_MODE (*this_head
->first
->loc
);
456 best_new_reg
= new_reg
;
457 best_nregs
= hard_regno_nregs
[new_reg
][mode
];
460 if (pass
== 0 && best_new_reg
!= reg
)
466 fprintf (dump_file
, "Register %s in insn %d",
467 reg_names
[reg
], INSN_UID (this_head
->first
->insn
));
468 if (this_head
->need_caller_save_reg
)
469 fprintf (dump_file
, " crosses a call");
472 if (best_new_reg
== reg
)
474 tick
[reg
] = ++this_tick
;
476 fprintf (dump_file
, "; no available better choice\n");
481 fprintf (dump_file
, ", renamed as %s\n", reg_names
[best_new_reg
]);
483 do_replace (this_head
, best_new_reg
);
484 this_head
->regno
= best_new_reg
;
485 this_head
->nregs
= best_nregs
;
486 tick
[best_new_reg
] = ++this_tick
;
487 df_set_regs_ever_live (best_new_reg
, true);
492 do_replace (struct du_head
*head
, int reg
)
494 struct du_chain
*chain
;
495 unsigned int base_regno
= head
->regno
;
497 gcc_assert (! DEBUG_INSN_P (head
->first
->insn
));
499 for (chain
= head
->first
; chain
; chain
= chain
->next_use
)
501 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
502 struct reg_attrs
*attr
= REG_ATTRS (*chain
->loc
);
503 int reg_ptr
= REG_POINTER (*chain
->loc
);
505 if (DEBUG_INSN_P (chain
->insn
) && REGNO (*chain
->loc
) != base_regno
)
506 INSN_VAR_LOCATION_LOC (chain
->insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
509 *chain
->loc
= gen_raw_REG (GET_MODE (*chain
->loc
), reg
);
510 if (regno
>= FIRST_PSEUDO_REGISTER
)
511 ORIGINAL_REGNO (*chain
->loc
) = regno
;
512 REG_ATTRS (*chain
->loc
) = attr
;
513 REG_POINTER (*chain
->loc
) = reg_ptr
;
516 df_insn_rescan (chain
->insn
);
521 /* True if we found a register with a size mismatch, which means that we
522 can't track its lifetime accurately. If so, we abort the current block
524 static bool fail_current_block
;
526 /* Return true if OP is a reg for which all bits are set in PSET, false
527 if all bits are clear.
528 In other cases, set fail_current_block and return false. */
531 verify_reg_in_set (rtx op
, HARD_REG_SET
*pset
)
533 unsigned regno
, nregs
;
534 bool all_live
, all_dead
;
539 nregs
= hard_regno_nregs
[regno
][GET_MODE (op
)];
540 all_live
= all_dead
= true;
542 if (TEST_HARD_REG_BIT (*pset
, regno
+ nregs
))
546 if (!all_dead
&& !all_live
)
548 fail_current_block
= true;
554 /* Return true if OP is a reg that is being tracked already in some form.
555 May set fail_current_block if it sees an unhandled case of overlap. */
558 verify_reg_tracked (rtx op
)
560 return (verify_reg_in_set (op
, &live_hard_regs
)
561 || verify_reg_in_set (op
, &live_in_chains
));
564 /* Called through note_stores. DATA points to a rtx_code, either SET or
565 CLOBBER, which tells us which kind of rtx to look at. If we have a
566 match, record the set register in live_hard_regs and in the hard_conflicts
567 bitmap of open chains. */
570 note_sets_clobbers (rtx x
, const_rtx set
, void *data
)
572 enum rtx_code code
= *(enum rtx_code
*)data
;
573 struct du_head
*chain
;
575 if (GET_CODE (x
) == SUBREG
)
577 if (!REG_P (x
) || GET_CODE (set
) != code
)
579 /* There must not be pseudos at this point. */
580 gcc_assert (HARD_REGISTER_P (x
));
581 add_to_hard_reg_set (&live_hard_regs
, GET_MODE (x
), REGNO (x
));
582 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
583 add_to_hard_reg_set (&chain
->hard_conflicts
, GET_MODE (x
), REGNO (x
));
587 scan_rtx_reg (rtx insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
592 enum machine_mode mode
= GET_MODE (x
);
593 unsigned this_regno
= REGNO (x
);
594 unsigned this_nregs
= hard_regno_nregs
[this_regno
][mode
];
596 if (action
== mark_write
)
599 create_new_chain (this_regno
, this_nregs
, loc
, insn
, cl
);
603 if ((type
== OP_OUT
) != (action
== terminate_write
|| action
== mark_access
))
606 for (p
= &open_chains
; *p
;)
608 struct du_head
*head
= *p
;
609 struct du_head
*next
= head
->next_chain
;
610 int exact_match
= (head
->regno
== this_regno
611 && head
->nregs
== this_nregs
);
612 int superset
= (this_regno
<= head
->regno
613 && this_regno
+ this_nregs
>= head
->regno
+ head
->nregs
);
614 int subset
= (this_regno
>= head
->regno
615 && this_regno
+ this_nregs
<= head
->regno
+ head
->nregs
);
617 if (!bitmap_bit_p (&open_chains_set
, head
->id
)
618 || head
->regno
+ head
->nregs
<= this_regno
619 || this_regno
+ this_nregs
<= head
->regno
)
621 p
= &head
->next_chain
;
625 if (action
== mark_read
|| action
== mark_access
)
627 /* ??? Class NO_REGS can happen if the md file makes use of
628 EXTRA_CONSTRAINTS to match registers. Which is arguably
629 wrong, but there we are. */
631 if (cl
== NO_REGS
|| (!exact_match
&& !DEBUG_INSN_P (insn
)))
635 "Cannot rename chain %s (%d) at insn %d (%s)\n",
636 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
637 scan_actions_name
[(int) action
]);
638 head
->cannot_rename
= 1;
641 unsigned nregs
= this_nregs
;
642 head
->regno
= this_regno
;
643 head
->nregs
= this_nregs
;
645 SET_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
648 "Widening register in chain %s (%d) at insn %d\n",
649 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
));
653 fail_current_block
= true;
656 "Failing basic block due to unhandled overlap\n");
661 struct du_chain
*this_du
;
662 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
663 this_du
->next_use
= 0;
665 this_du
->insn
= insn
;
667 if (head
->first
== NULL
)
668 head
->first
= this_du
;
670 head
->last
->next_use
= this_du
;
671 head
->last
= this_du
;
673 /* Avoid adding the same location in a DEBUG_INSN multiple times,
674 which could happen with non-exact overlap. */
675 if (DEBUG_INSN_P (insn
))
677 /* Otherwise, find any other chains that do not match exactly;
678 ensure they all get marked unrenamable. */
679 p
= &head
->next_chain
;
683 /* Whether the terminated chain can be used for renaming
684 depends on the action and this being an exact match.
685 In either case, we remove this element from open_chains. */
687 if ((action
== terminate_dead
|| action
== terminate_write
)
688 && (superset
|| subset
))
692 if (subset
&& !superset
)
693 head
->cannot_rename
= 1;
694 head
->next_chain
= closed_chains
;
695 closed_chains
= head
;
696 bitmap_clear_bit (&open_chains_set
, head
->id
);
701 CLEAR_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
702 if (subset
&& !superset
703 && (head
->regno
+ nregs
< this_regno
704 || head
->regno
+ nregs
>= this_regno
+ this_nregs
))
705 SET_HARD_REG_BIT (live_hard_regs
, head
->regno
+ nregs
);
711 "Closing chain %s (%d) at insn %d (%s%s)\n",
712 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
713 scan_actions_name
[(int) action
],
714 superset
? ", superset" : subset
? ", subset" : "");
716 else if (action
== terminate_dead
|| action
== terminate_write
)
718 /* In this case, tracking liveness gets too hard. Fail the
719 entire basic block. */
722 "Failing basic block due to unhandled overlap\n");
723 fail_current_block
= true;
728 head
->cannot_rename
= 1;
731 "Cannot rename chain %s (%d) at insn %d (%s)\n",
732 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
733 scan_actions_name
[(int) action
]);
734 p
= &head
->next_chain
;
739 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
740 BASE_REG_CLASS depending on how the register is being considered. */
743 scan_rtx_address (rtx insn
, rtx
*loc
, enum reg_class cl
,
744 enum scan_actions action
, enum machine_mode mode
)
747 RTX_CODE code
= GET_CODE (x
);
751 if (action
== mark_write
|| action
== mark_access
)
758 rtx orig_op0
= XEXP (x
, 0);
759 rtx orig_op1
= XEXP (x
, 1);
760 RTX_CODE code0
= GET_CODE (orig_op0
);
761 RTX_CODE code1
= GET_CODE (orig_op1
);
766 enum rtx_code index_code
= SCRATCH
;
768 if (GET_CODE (op0
) == SUBREG
)
770 op0
= SUBREG_REG (op0
);
771 code0
= GET_CODE (op0
);
774 if (GET_CODE (op1
) == SUBREG
)
776 op1
= SUBREG_REG (op1
);
777 code1
= GET_CODE (op1
);
780 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
781 || code0
== ZERO_EXTEND
|| code1
== MEM
)
785 index_code
= GET_CODE (*locI
);
787 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
788 || code1
== ZERO_EXTEND
|| code0
== MEM
)
792 index_code
= GET_CODE (*locI
);
794 else if (code0
== CONST_INT
|| code0
== CONST
795 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
798 index_code
= GET_CODE (XEXP (x
, 0));
800 else if (code1
== CONST_INT
|| code1
== CONST
801 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
804 index_code
= GET_CODE (XEXP (x
, 1));
806 else if (code0
== REG
&& code1
== REG
)
809 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
811 if (REGNO_OK_FOR_INDEX_P (regno1
)
812 && regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
814 else if (REGNO_OK_FOR_INDEX_P (regno0
)
815 && regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
817 else if (regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
)
818 || REGNO_OK_FOR_INDEX_P (regno1
))
820 else if (regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
825 locI
= &XEXP (x
, index_op
);
826 locB
= &XEXP (x
, !index_op
);
827 index_code
= GET_CODE (*locI
);
829 else if (code0
== REG
)
833 index_code
= GET_CODE (*locI
);
835 else if (code1
== REG
)
839 index_code
= GET_CODE (*locI
);
843 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
);
845 scan_rtx_address (insn
, locB
, base_reg_class (mode
, PLUS
, index_code
),
858 /* If the target doesn't claim to handle autoinc, this must be
859 something special, like a stack push. Kill this chain. */
860 action
= mark_all_read
;
865 scan_rtx_address (insn
, &XEXP (x
, 0),
866 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
871 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
);
878 fmt
= GET_RTX_FORMAT (code
);
879 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
882 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
);
883 else if (fmt
[i
] == 'E')
884 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
885 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
);
890 scan_rtx (rtx insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
895 enum rtx_code code
= GET_CODE (x
);
913 scan_rtx_reg (insn
, loc
, cl
, action
, type
);
917 scan_rtx_address (insn
, &XEXP (x
, 0),
918 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
923 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
);
924 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
925 (GET_CODE (PATTERN (insn
)) == COND_EXEC
926 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
929 case STRICT_LOW_PART
:
930 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
931 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
);
936 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
937 (type
== OP_IN
? OP_IN
:
938 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
));
939 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
);
940 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
);
949 /* Should only happen inside MEM. */
953 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
954 (GET_CODE (PATTERN (insn
)) == COND_EXEC
955 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
959 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
);
961 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
);
968 fmt
= GET_RTX_FORMAT (code
);
969 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
972 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
);
973 else if (fmt
[i
] == 'E')
974 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
975 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
);
979 /* Hide operands of the current insn (of which there are N_OPS) by
980 substituting cc0 for them.
981 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
982 For every bit set in DO_NOT_HIDE, we leave the operand alone.
983 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
984 and earlyclobbers. */
987 hide_operands (int n_ops
, rtx
*old_operands
, rtx
*old_dups
,
988 unsigned HOST_WIDE_INT do_not_hide
, bool inout_and_ec_only
)
991 int alt
= which_alternative
;
992 for (i
= 0; i
< n_ops
; i
++)
994 old_operands
[i
] = recog_data
.operand
[i
];
995 /* Don't squash match_operator or match_parallel here, since
996 we don't know that all of the contained registers are
997 reachable by proper operands. */
998 if (recog_data
.constraints
[i
][0] == '\0')
1000 if (do_not_hide
& (1 << i
))
1002 if (!inout_and_ec_only
|| recog_data
.operand_type
[i
] == OP_INOUT
1003 || recog_op_alt
[i
][alt
].earlyclobber
)
1004 *recog_data
.operand_loc
[i
] = cc0_rtx
;
1006 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1008 int opn
= recog_data
.dup_num
[i
];
1009 old_dups
[i
] = *recog_data
.dup_loc
[i
];
1010 if (do_not_hide
& (1 << opn
))
1012 if (!inout_and_ec_only
|| recog_data
.operand_type
[opn
] == OP_INOUT
1013 || recog_op_alt
[opn
][alt
].earlyclobber
)
1014 *recog_data
.dup_loc
[i
] = cc0_rtx
;
1018 /* Undo the substitution performed by hide_operands. INSN is the insn we
1019 are processing; the arguments are the same as in hide_operands. */
1022 restore_operands (rtx insn
, int n_ops
, rtx
*old_operands
, rtx
*old_dups
)
1025 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1026 *recog_data
.dup_loc
[i
] = old_dups
[i
];
1027 for (i
= 0; i
< n_ops
; i
++)
1028 *recog_data
.operand_loc
[i
] = old_operands
[i
];
1029 if (recog_data
.n_dups
)
1030 df_insn_rescan (insn
);
1033 /* For each output operand of INSN, call scan_rtx to create a new
1034 open chain. Do this only for normal or earlyclobber outputs,
1035 depending on EARLYCLOBBER. */
1038 record_out_operands (rtx insn
, bool earlyclobber
)
1040 int n_ops
= recog_data
.n_operands
;
1041 int alt
= which_alternative
;
1045 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1047 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1048 rtx
*loc
= (i
< n_ops
1049 ? recog_data
.operand_loc
[opn
]
1050 : recog_data
.dup_loc
[i
- n_ops
]);
1052 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
1054 struct du_head
*prev_open
;
1056 if (recog_data
.operand_type
[opn
] != OP_OUT
1057 || recog_op_alt
[opn
][alt
].earlyclobber
!= earlyclobber
)
1060 prev_open
= open_chains
;
1061 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
);
1063 /* ??? Many targets have output constraints on the SET_DEST
1064 of a call insn, which is stupid, since these are certainly
1065 ABI defined hard registers. For these, and for asm operands
1066 that originally referenced hard registers, we must record that
1067 the chain cannot be renamed. */
1069 || (asm_noperands (PATTERN (insn
)) > 0
1071 && REGNO (op
) == ORIGINAL_REGNO (op
)))
1073 if (prev_open
!= open_chains
)
1074 open_chains
->cannot_rename
= 1;
1079 /* Build def/use chain. */
1081 static struct du_head
*
1082 build_def_use (basic_block bb
)
1086 unsigned HOST_WIDE_INT untracked_operands
;
1088 open_chains
= closed_chains
= NULL
;
1090 fail_current_block
= false;
1093 bitmap_initialize (&open_chains_set
, &bitmap_default_obstack
);
1094 CLEAR_HARD_REG_SET (live_in_chains
);
1095 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_in (bb
));
1096 for (def_rec
= df_get_artificial_defs (bb
->index
); *def_rec
; def_rec
++)
1098 df_ref def
= *def_rec
;
1099 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
1100 SET_HARD_REG_BIT (live_hard_regs
, DF_REF_REGNO (def
));
1103 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1105 if (NONDEBUG_INSN_P (insn
))
1109 rtx old_operands
[MAX_RECOG_OPERANDS
];
1110 rtx old_dups
[MAX_DUP_OPERANDS
];
1114 enum rtx_code set_code
= SET
;
1115 enum rtx_code clobber_code
= CLOBBER
;
1117 /* Process the insn, determining its effect on the def-use
1118 chains and live hard registers. We perform the following
1119 steps with the register references in the insn, simulating
1121 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1122 by creating chains and marking hard regs live.
1123 (2) Any read outside an operand causes any chain it overlaps
1124 with to be marked unrenamable.
1125 (3) Any read inside an operand is added if there's already
1126 an open chain for it.
1127 (4) For any REG_DEAD note we find, close open chains that
1129 (5) For any non-earlyclobber write we find, close open chains
1131 (6) For any non-earlyclobber write we find in an operand, make
1132 a new chain or mark the hard register as live.
1133 (7) For any REG_UNUSED, close any chains we just opened.
1135 We cannot deal with situations where we track a reg in one mode
1136 and see a reference in another mode; these will cause the chain
1137 to be marked unrenamable or even cause us to abort the entire
1140 extract_insn (insn
);
1141 if (! constrain_operands (1))
1142 fatal_insn_not_found (insn
);
1143 preprocess_constraints ();
1144 alt
= which_alternative
;
1145 n_ops
= recog_data
.n_operands
;
1146 untracked_operands
= 0;
1148 /* Simplify the code below by rewriting things to reflect
1149 matching constraints. Also promote OP_OUT to OP_INOUT in
1150 predicated instructions, but only for register operands
1151 that are already tracked, so that we can create a chain
1152 when the first SET makes a register live. */
1154 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1155 for (i
= 0; i
< n_ops
; ++i
)
1157 rtx op
= recog_data
.operand
[i
];
1158 int matches
= recog_op_alt
[i
][alt
].matches
;
1160 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
1161 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
1162 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1164 recog_data
.operand_type
[i
] = OP_INOUT
;
1165 /* A special case to deal with instruction patterns that
1166 have matching operands with different modes. If we're
1167 not already tracking such a reg, we won't start here,
1168 and we must instead make sure to make the operand visible
1169 to the machinery that tracks hard registers. */
1171 && (GET_MODE_SIZE (recog_data
.operand_mode
[i
])
1172 != GET_MODE_SIZE (recog_data
.operand_mode
[matches
]))
1173 && !verify_reg_in_set (op
, &live_in_chains
))
1175 untracked_operands
|= 1 << i
;
1176 untracked_operands
|= 1 << matches
;
1179 /* If there's an in-out operand with a register that is not
1180 being tracked at all yet, open a chain. */
1181 if (recog_data
.operand_type
[i
] == OP_INOUT
1182 && !(untracked_operands
& (1 << i
))
1184 && !verify_reg_tracked (op
))
1186 enum machine_mode mode
= GET_MODE (op
);
1187 unsigned this_regno
= REGNO (op
);
1188 unsigned this_nregs
= hard_regno_nregs
[this_regno
][mode
];
1189 create_new_chain (this_regno
, this_nregs
, NULL
, NULL_RTX
,
1194 if (fail_current_block
)
1197 /* Step 1a: Mark hard registers that are clobbered in this insn,
1198 outside an operand, as live. */
1199 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1201 note_stores (PATTERN (insn
), note_sets_clobbers
, &clobber_code
);
1202 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1204 /* Step 1b: Begin new chains for earlyclobbered writes inside
1206 record_out_operands (insn
, true);
1208 /* Step 2: Mark chains for which we have reads outside operands
1210 We do this by munging all operands into CC0, and closing
1211 everything remaining. */
1213 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1215 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, mark_all_read
, OP_IN
);
1216 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1218 /* Step 2B: Can't rename function call argument registers. */
1219 if (CALL_P (insn
) && CALL_INSN_FUNCTION_USAGE (insn
))
1220 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
1221 NO_REGS
, mark_all_read
, OP_IN
);
1223 /* Step 2C: Can't rename asm operands that were originally
1225 if (asm_noperands (PATTERN (insn
)) > 0)
1226 for (i
= 0; i
< n_ops
; i
++)
1228 rtx
*loc
= recog_data
.operand_loc
[i
];
1232 && REGNO (op
) == ORIGINAL_REGNO (op
)
1233 && (recog_data
.operand_type
[i
] == OP_IN
1234 || recog_data
.operand_type
[i
] == OP_INOUT
))
1235 scan_rtx (insn
, loc
, NO_REGS
, mark_all_read
, OP_IN
);
1238 /* Step 3: Append to chains for reads inside operands. */
1239 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1241 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1242 rtx
*loc
= (i
< n_ops
1243 ? recog_data
.operand_loc
[opn
]
1244 : recog_data
.dup_loc
[i
- n_ops
]);
1245 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
1246 enum op_type type
= recog_data
.operand_type
[opn
];
1248 /* Don't scan match_operand here, since we've no reg class
1249 information to pass down. Any operands that we could
1250 substitute in will be represented elsewhere. */
1251 if (recog_data
.constraints
[opn
][0] == '\0'
1252 || untracked_operands
& (1 << opn
))
1255 if (recog_op_alt
[opn
][alt
].is_address
)
1256 scan_rtx_address (insn
, loc
, cl
, mark_read
, VOIDmode
);
1258 scan_rtx (insn
, loc
, cl
, mark_read
, type
);
1261 /* Step 3B: Record updates for regs in REG_INC notes, and
1262 source regs in REG_FRAME_RELATED_EXPR notes. */
1263 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1264 if (REG_NOTE_KIND (note
) == REG_INC
1265 || REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1266 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
1269 /* Step 4: Close chains for registers that die here. */
1270 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1271 if (REG_NOTE_KIND (note
) == REG_DEAD
)
1273 remove_from_hard_reg_set (&live_hard_regs
,
1274 GET_MODE (XEXP (note
, 0)),
1275 REGNO (XEXP (note
, 0)));
1276 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1280 /* Step 4B: If this is a call, any chain live at this point
1281 requires a caller-saved reg. */
1285 for (p
= open_chains
; p
; p
= p
->next_chain
)
1286 p
->need_caller_save_reg
= 1;
1289 /* Step 5: Close open chains that overlap writes. Similar to
1290 step 2, we hide in-out operands, since we do not want to
1291 close these chains. We also hide earlyclobber operands,
1292 since we've opened chains for them in step 1, and earlier
1293 chains they would overlap with must have been closed at
1294 the previous insn at the latest, as such operands cannot
1295 possibly overlap with any input operands. */
1297 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1299 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
);
1300 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1302 /* Step 6a: Mark hard registers that are set in this insn,
1303 outside an operand, as live. */
1304 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1306 note_stores (PATTERN (insn
), note_sets_clobbers
, &set_code
);
1307 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1309 /* Step 6b: Begin new chains for writes inside operands. */
1310 record_out_operands (insn
, false);
1312 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1313 notes for update. */
1314 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1315 if (REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1316 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_access
,
1319 /* Step 7: Close chains for registers that were never
1320 really used here. */
1321 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1322 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
1324 remove_from_hard_reg_set (&live_hard_regs
,
1325 GET_MODE (XEXP (note
, 0)),
1326 REGNO (XEXP (note
, 0)));
1327 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1331 else if (DEBUG_INSN_P (insn
)
1332 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn
)))
1334 scan_rtx (insn
, &INSN_VAR_LOCATION_LOC (insn
),
1335 ALL_REGS
, mark_read
, OP_IN
);
1337 if (insn
== BB_END (bb
))
1341 bitmap_clear (&open_chains_set
);
1343 if (fail_current_block
)
1346 /* Since we close every chain when we find a REG_DEAD note, anything that
1347 is still open lives past the basic block, so it can't be renamed. */
1348 return closed_chains
;
1351 /* Perform register renaming on the current function. */
1354 regrename_optimize (void)
1359 df_set_flags (DF_LR_RUN_DCE
);
1360 df_note_add_problem ();
1362 df_set_flags (DF_DEFER_INSN_RESCAN
);
1364 memset (tick
, 0, sizeof tick
);
1366 gcc_obstack_init (&rename_obstack
);
1367 first_obj
= XOBNEWVAR (&rename_obstack
, char, 0);
1371 struct du_head
*all_chains
= 0;
1373 id_to_chain
= VEC_alloc (du_head_p
, heap
, 0);
1376 fprintf (dump_file
, "\nBasic block %d:\n", bb
->index
);
1378 all_chains
= build_def_use (bb
);
1381 dump_def_use_chain (all_chains
);
1383 rename_chains (all_chains
);
1386 obstack_free (&rename_obstack
, first_obj
);
1389 obstack_free (&rename_obstack
, NULL
);
1392 fputc ('\n', dump_file
);
1398 gate_handle_regrename (void)
1400 return (optimize
> 0 && (flag_rename_registers
));
1403 struct rtl_opt_pass pass_regrename
=
1408 gate_handle_regrename
, /* gate */
1409 regrename_optimize
, /* execute */
1412 0, /* static_pass_number */
1413 TV_RENAME_REGISTERS
, /* tv_id */
1414 0, /* properties_required */
1415 0, /* properties_provided */
1416 0, /* properties_destroyed */
1417 0, /* todo_flags_start */
1418 TODO_df_finish
| TODO_verify_rtl_sharing
|
1419 0 /* todo_flags_finish */