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_reg (rtx, rtx *, enum reg_class,
142 enum scan_actions, enum op_type);
143 static void scan_rtx_address (rtx, rtx *, enum reg_class,
144 enum scan_actions, enum machine_mode);
145 static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
147 static struct du_head *build_def_use (basic_block);
148 static void dump_def_use_chain (struct du_head *);
150 typedef struct du_head *du_head_p;
151 DEF_VEC_P (du_head_p);
152 DEF_VEC_ALLOC_P (du_head_p, heap);
154 /* The id to be given to the next opened chain. */
155 static unsigned current_id;
157 /* A mapping of unique id numbers to chains. */
158 static VEC(du_head_p, heap) *id_to_chain;
160 /* List of currently open chains, and closed chains that can be renamed. */
161 static struct du_head *open_chains;
162 static struct du_head *closed_chains;
164 /* Bitmap of open chains. The bits set always match the list found in
166 static bitmap_head open_chains_set;
168 /* Record the registers being tracked in open_chains. */
169 static HARD_REG_SET live_in_chains;
171 /* Record the registers that are live but not tracked. The intersection
172 between this and live_in_chains is empty. */
173 static HARD_REG_SET live_hard_regs;
175 /* Dump all def/use chains in CHAINS to DUMP_FILE. */
178 dump_def_use_chain (struct du_head *head)
182 struct du_chain *this_du = head->first;
183 fprintf (dump_file, "Register %s (%d):",
184 reg_names[head->regno], head->nregs);
187 fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
188 reg_class_names[this_du->cl]);
189 this_du = this_du->next_use;
191 fprintf (dump_file, "\n");
192 head = head->next_chain;
197 free_chain_data (void)
201 for (i = 0; VEC_iterate(du_head_p, id_to_chain, i, ptr); i++)
202 bitmap_clear (&ptr->conflicts);
204 VEC_free (du_head_p, heap, id_to_chain);
207 /* For a def-use chain HEAD, find which registers overlap its lifetime and
208 set the corresponding bits in *PSET. */
211 merge_overlapping_regs (HARD_REG_SET *pset, struct du_head *head)
215 IOR_HARD_REG_SET (*pset, head->hard_conflicts);
216 EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi)
218 du_head_p other = VEC_index (du_head_p, id_to_chain, i);
219 unsigned j = other->nregs;
221 SET_HARD_REG_BIT (*pset, other->regno + j);
225 /* Check if NEW_REG can be the candidate register to rename for
226 REG in THIS_HEAD chain. THIS_UNAVAILABLE is a set of unavailable hard
230 check_new_reg_p (int reg ATTRIBUTE_UNUSED, int new_reg,
231 struct du_head *this_head, HARD_REG_SET this_unavailable)
233 enum machine_mode mode = GET_MODE (*this_head->first->loc);
234 int nregs = hard_regno_nregs[new_reg][mode];
236 struct du_chain *tmp;
238 for (i = nregs - 1; i >= 0; --i)
239 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
240 || fixed_regs[new_reg + i]
241 || global_regs[new_reg + i]
242 /* Can't use regs which aren't saved by the prologue. */
243 || (! df_regs_ever_live_p (new_reg + i)
244 && ! call_used_regs[new_reg + i])
245 #ifdef LEAF_REGISTERS
246 /* We can't use a non-leaf register if we're in a
248 || (current_function_is_leaf
249 && !LEAF_REGISTERS[new_reg + i])
251 #ifdef HARD_REGNO_RENAME_OK
252 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
257 /* See whether it accepts all modes that occur in
258 definition and uses. */
259 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
260 if ((! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
261 && ! DEBUG_INSN_P (tmp->insn))
262 || (this_head->need_caller_save_reg
263 && ! (HARD_REGNO_CALL_PART_CLOBBERED
264 (reg, GET_MODE (*tmp->loc)))
265 && (HARD_REGNO_CALL_PART_CLOBBERED
266 (new_reg, GET_MODE (*tmp->loc)))))
272 /* Process the closed chains starting with ALL_CHAINS and rename
273 registers if possible. */
275 rename_chains (du_head_p all_chains)
277 HARD_REG_SET unavailable;
279 CLEAR_HARD_REG_SET (unavailable);
280 /* Don't clobber traceback for noreturn functions. */
281 if (frame_pointer_needed)
283 add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
284 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
285 add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
291 int new_reg, best_new_reg, best_nregs;
293 struct du_head *this_head = all_chains;
294 struct du_chain *tmp;
295 HARD_REG_SET this_unavailable;
296 int reg = this_head->regno;
298 enum reg_class super_class = NO_REGS;
299 enum reg_class preferred_class;
300 bool has_preferred_class;
302 all_chains = this_head->next_chain;
304 if (this_head->cannot_rename)
308 best_nregs = this_head->nregs;
310 if (fixed_regs[reg] || global_regs[reg]
311 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
312 || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
314 || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
319 COPY_HARD_REG_SET (this_unavailable, unavailable);
321 /* Iterate over elements in the chain in order to:
322 1. Count number of uses, and narrow the set of registers we can
324 2. Compute the superunion of register classes in this chain. */
326 super_class = NO_REGS;
327 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
329 if (DEBUG_INSN_P (tmp->insn))
332 IOR_COMPL_HARD_REG_SET (this_unavailable,
333 reg_class_contents[tmp->cl]);
335 = reg_class_superunion[(int) super_class][(int) tmp->cl];
341 /* Further narrow the set of registers we can use for renaming.
342 If the chain needs a call-saved register, mark the call-used
343 registers as unavailable. */
344 if (this_head->need_caller_save_reg)
345 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
347 /* And mark registers that overlap its lifetime as unavailable. */
348 merge_overlapping_regs (&this_unavailable, this_head);
350 /* Compute preferred rename class of super union of all the classes
353 = (enum reg_class) targetm.preferred_rename_class (super_class);
355 /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
356 over registers that belong to PREFERRED_CLASS and try to find the
357 best register within the class. If that failed, we iterate in
358 the second pass over registers that don't belong to the class.
359 If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
360 ascending order without any preference. */
361 has_preferred_class = (preferred_class != NO_REGS);
362 for (pass = (has_preferred_class ? 0 : 1); pass < 2; pass++)
364 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
366 if (has_preferred_class
367 && ((pass == 0) != TEST_HARD_REG_BIT
368 (reg_class_contents[preferred_class], new_reg)))
371 /* In the first pass, we force the renaming of registers that
372 don't belong to PREFERRED_CLASS to registers that do, even
373 though the latters were used not very long ago. */
374 if (check_new_reg_p (reg, new_reg, this_head,
377 && (!TEST_HARD_REG_BIT
378 (reg_class_contents[preferred_class],
380 || tick[best_new_reg] > tick[new_reg]))
382 enum machine_mode mode
383 = GET_MODE (*this_head->first->loc);
384 best_new_reg = new_reg;
385 best_nregs = hard_regno_nregs[new_reg][mode];
388 if (pass == 0 && best_new_reg != reg)
394 fprintf (dump_file, "Register %s in insn %d",
395 reg_names[reg], INSN_UID (this_head->first->insn));
396 if (this_head->need_caller_save_reg)
397 fprintf (dump_file, " crosses a call");
400 if (best_new_reg == reg)
402 tick[reg] = ++this_tick;
404 fprintf (dump_file, "; no available better choice\n");
409 fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
411 do_replace (this_head, best_new_reg);
412 this_head->regno = best_new_reg;
413 this_head->nregs = best_nregs;
414 tick[best_new_reg] = ++this_tick;
415 df_set_regs_ever_live (best_new_reg, true);
419 /* Perform register renaming on the current function. */
422 regrename_optimize (void)
427 df_set_flags (DF_LR_RUN_DCE);
428 df_note_add_problem ();
430 df_set_flags (DF_DEFER_INSN_RESCAN);
432 memset (tick, 0, sizeof tick);
434 gcc_obstack_init (&rename_obstack);
435 first_obj = XOBNEWVAR (&rename_obstack, char, 0);
439 struct du_head *all_chains = 0;
441 id_to_chain = VEC_alloc (du_head_p, heap, 0);
444 fprintf (dump_file, "\nBasic block %d:\n", bb->index);
446 all_chains = build_def_use (bb);
449 dump_def_use_chain (all_chains);
451 rename_chains (all_chains);
454 obstack_free (&rename_obstack, first_obj);
457 obstack_free (&rename_obstack, NULL);
460 fputc ('\n', dump_file);
466 do_replace (struct du_head *head, int reg)
468 struct du_chain *chain;
469 unsigned int base_regno = head->regno;
471 gcc_assert (! DEBUG_INSN_P (head->first->insn));
473 for (chain = head->first; chain; chain = chain->next_use)
475 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
476 struct reg_attrs *attr = REG_ATTRS (*chain->loc);
477 int reg_ptr = REG_POINTER (*chain->loc);
479 if (DEBUG_INSN_P (chain->insn) && REGNO (*chain->loc) != base_regno)
480 INSN_VAR_LOCATION_LOC (chain->insn) = gen_rtx_UNKNOWN_VAR_LOC ();
483 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
484 if (regno >= FIRST_PSEUDO_REGISTER)
485 ORIGINAL_REGNO (*chain->loc) = regno;
486 REG_ATTRS (*chain->loc) = attr;
487 REG_POINTER (*chain->loc) = reg_ptr;
490 df_insn_rescan (chain->insn);
495 /* Walk all chains starting with CHAINS and record that they conflict with
496 another chain whose id is ID. */
499 mark_conflict (struct du_head *chains, unsigned id)
503 bitmap_set_bit (&chains->conflicts, id);
504 chains = chains->next_chain;
508 /* True if we found a register with a size mismatch, which means that we
509 can't track its lifetime accurately. If so, we abort the current block
511 static bool fail_current_block;
513 /* Return true if OP is a reg for which all bits are set in PSET, false
514 if all bits are clear.
515 In other cases, set fail_current_block and return false. */
518 verify_reg_in_set (rtx op, HARD_REG_SET *pset)
520 unsigned regno, nregs;
521 bool all_live, all_dead;
526 nregs = hard_regno_nregs[regno][GET_MODE (op)];
527 all_live = all_dead = true;
529 if (TEST_HARD_REG_BIT (*pset, regno + nregs))
533 if (!all_dead && !all_live)
535 fail_current_block = true;
541 /* Return true if OP is a reg that is being tracked already in some form.
542 May set fail_current_block if it sees an unhandled case of overlap. */
545 verify_reg_tracked (rtx op)
547 return (verify_reg_in_set (op, &live_hard_regs)
548 || verify_reg_in_set (op, &live_in_chains));
551 /* Called through note_stores. DATA points to a rtx_code, either SET or
552 CLOBBER, which tells us which kind of rtx to look at. If we have a
553 match, record the set register in live_hard_regs and in the hard_conflicts
554 bitmap of open chains. */
557 note_sets_clobbers (rtx x, const_rtx set, void *data)
559 enum rtx_code code = *(enum rtx_code *)data;
560 struct du_head *chain;
562 if (GET_CODE (x) == SUBREG)
564 if (!REG_P (x) || GET_CODE (set) != code)
566 /* There must not be pseudos at this point. */
567 gcc_assert (HARD_REGISTER_P (x));
568 add_to_hard_reg_set (&live_hard_regs, GET_MODE (x), REGNO (x));
569 for (chain = open_chains; chain; chain = chain->next_chain)
570 add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x));
573 /* Create a new chain for THIS_NREGS registers starting at THIS_REGNO,
574 and record its occurrence in *LOC, which is being written to in INSN.
575 This access requires a register of class CL. */
578 create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc,
579 rtx insn, enum reg_class cl)
581 struct du_head *head = XOBNEW (&rename_obstack, struct du_head);
582 struct du_chain *this_du;
585 head->next_chain = open_chains;
587 head->regno = this_regno;
588 head->nregs = this_nregs;
589 head->need_caller_save_reg = 0;
590 head->cannot_rename = 0;
592 VEC_safe_push (du_head_p, heap, id_to_chain, head);
593 head->id = current_id++;
595 bitmap_initialize (&head->conflicts, &bitmap_default_obstack);
596 bitmap_copy (&head->conflicts, &open_chains_set);
597 mark_conflict (open_chains, head->id);
599 /* Since we're tracking this as a chain now, remove it from the
600 list of conflicting live hard registers and track it in
601 live_in_chains instead. */
605 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
606 CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
609 COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs);
610 bitmap_set_bit (&open_chains_set, head->id);
616 fprintf (dump_file, "Creating chain %s (%d)",
617 reg_names[head->regno], head->id);
618 if (insn != NULL_RTX)
619 fprintf (dump_file, " at insn %d", INSN_UID (insn));
620 fprintf (dump_file, "\n");
623 if (insn == NULL_RTX)
625 head->first = head->last = NULL;
629 this_du = XOBNEW (&rename_obstack, struct du_chain);
630 head->first = head->last = this_du;
632 this_du->next_use = 0;
634 this_du->insn = insn;
639 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
644 enum machine_mode mode = GET_MODE (x);
645 unsigned this_regno = REGNO (x);
646 unsigned this_nregs = hard_regno_nregs[this_regno][mode];
648 if (action == mark_write)
651 create_new_chain (this_regno, this_nregs, loc, insn, cl);
655 if ((type == OP_OUT) != (action == terminate_write || action == mark_access))
658 for (p = &open_chains; *p;)
660 struct du_head *head = *p;
661 struct du_head *next = head->next_chain;
662 int exact_match = (head->regno == this_regno
663 && head->nregs == this_nregs);
664 int superset = (this_regno <= head->regno
665 && this_regno + this_nregs >= head->regno + head->nregs);
666 int subset = (this_regno >= head->regno
667 && this_regno + this_nregs <= head->regno + head->nregs);
669 if (!bitmap_bit_p (&open_chains_set, head->id)
670 || head->regno + head->nregs <= this_regno
671 || this_regno + this_nregs <= head->regno)
673 p = &head->next_chain;
677 if (action == mark_read || action == mark_access)
679 /* ??? Class NO_REGS can happen if the md file makes use of
680 EXTRA_CONSTRAINTS to match registers. Which is arguably
681 wrong, but there we are. */
683 if (cl == NO_REGS || (!exact_match && !DEBUG_INSN_P (insn)))
687 "Cannot rename chain %s (%d) at insn %d (%s)\n",
688 reg_names[head->regno], head->id, INSN_UID (insn),
689 scan_actions_name[(int) action]);
690 head->cannot_rename = 1;
693 unsigned nregs = this_nregs;
694 head->regno = this_regno;
695 head->nregs = this_nregs;
697 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
700 "Widening register in chain %s (%d) at insn %d\n",
701 reg_names[head->regno], head->id, INSN_UID (insn));
705 fail_current_block = true;
708 "Failing basic block due to unhandled overlap\n");
713 struct du_chain *this_du;
714 this_du = XOBNEW (&rename_obstack, struct du_chain);
715 this_du->next_use = 0;
717 this_du->insn = insn;
719 if (head->first == NULL)
720 head->first = this_du;
722 head->last->next_use = this_du;
723 head->last = this_du;
725 /* Avoid adding the same location in a DEBUG_INSN multiple times,
726 which could happen with non-exact overlap. */
727 if (DEBUG_INSN_P (insn))
729 /* Otherwise, find any other chains that do not match exactly;
730 ensure they all get marked unrenamable. */
731 p = &head->next_chain;
735 /* Whether the terminated chain can be used for renaming
736 depends on the action and this being an exact match.
737 In either case, we remove this element from open_chains. */
739 if ((action == terminate_dead || action == terminate_write)
740 && (superset || subset))
744 if (subset && !superset)
745 head->cannot_rename = 1;
746 head->next_chain = closed_chains;
747 closed_chains = head;
748 bitmap_clear_bit (&open_chains_set, head->id);
753 CLEAR_HARD_REG_BIT (live_in_chains, head->regno + nregs);
754 if (subset && !superset
755 && (head->regno + nregs < this_regno
756 || head->regno + nregs >= this_regno + this_nregs))
757 SET_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
763 "Closing chain %s (%d) at insn %d (%s%s)\n",
764 reg_names[head->regno], head->id, INSN_UID (insn),
765 scan_actions_name[(int) action],
766 superset ? ", superset" : subset ? ", subset" : "");
768 else if (action == terminate_dead || action == terminate_write)
770 /* In this case, tracking liveness gets too hard. Fail the
771 entire basic block. */
774 "Failing basic block due to unhandled overlap\n");
775 fail_current_block = true;
780 head->cannot_rename = 1;
783 "Cannot rename chain %s (%d) at insn %d (%s)\n",
784 reg_names[head->regno], head->id, INSN_UID (insn),
785 scan_actions_name[(int) action]);
786 p = &head->next_chain;
791 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
792 BASE_REG_CLASS depending on how the register is being considered. */
795 scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl,
796 enum scan_actions action, enum machine_mode mode)
799 RTX_CODE code = GET_CODE (x);
803 if (action == mark_write || action == mark_access)
810 rtx orig_op0 = XEXP (x, 0);
811 rtx orig_op1 = XEXP (x, 1);
812 RTX_CODE code0 = GET_CODE (orig_op0);
813 RTX_CODE code1 = GET_CODE (orig_op1);
818 enum rtx_code index_code = SCRATCH;
820 if (GET_CODE (op0) == SUBREG)
822 op0 = SUBREG_REG (op0);
823 code0 = GET_CODE (op0);
826 if (GET_CODE (op1) == SUBREG)
828 op1 = SUBREG_REG (op1);
829 code1 = GET_CODE (op1);
832 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
833 || code0 == ZERO_EXTEND || code1 == MEM)
837 index_code = GET_CODE (*locI);
839 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
840 || code1 == ZERO_EXTEND || code0 == MEM)
844 index_code = GET_CODE (*locI);
846 else if (code0 == CONST_INT || code0 == CONST
847 || code0 == SYMBOL_REF || code0 == LABEL_REF)
850 index_code = GET_CODE (XEXP (x, 0));
852 else if (code1 == CONST_INT || code1 == CONST
853 || code1 == SYMBOL_REF || code1 == LABEL_REF)
856 index_code = GET_CODE (XEXP (x, 1));
858 else if (code0 == REG && code1 == REG)
861 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
863 if (REGNO_OK_FOR_INDEX_P (regno1)
864 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
866 else if (REGNO_OK_FOR_INDEX_P (regno0)
867 && regno_ok_for_base_p (regno1, mode, PLUS, REG))
869 else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
870 || REGNO_OK_FOR_INDEX_P (regno1))
872 else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
877 locI = &XEXP (x, index_op);
878 locB = &XEXP (x, !index_op);
879 index_code = GET_CODE (*locI);
881 else if (code0 == REG)
885 index_code = GET_CODE (*locI);
887 else if (code1 == REG)
891 index_code = GET_CODE (*locI);
895 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
897 scan_rtx_address (insn, locB, base_reg_class (mode, PLUS, index_code),
910 /* If the target doesn't claim to handle autoinc, this must be
911 something special, like a stack push. Kill this chain. */
912 action = mark_all_read;
917 scan_rtx_address (insn, &XEXP (x, 0),
918 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
923 scan_rtx_reg (insn, loc, cl, action, OP_IN);
930 fmt = GET_RTX_FORMAT (code);
931 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
934 scan_rtx_address (insn, &XEXP (x, i), cl, action, mode);
935 else if (fmt[i] == 'E')
936 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
937 scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode);
942 scan_rtx (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
947 enum rtx_code code = GET_CODE (x);
965 scan_rtx_reg (insn, loc, cl, action, type);
969 scan_rtx_address (insn, &XEXP (x, 0),
970 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
975 scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN);
976 scan_rtx (insn, &SET_DEST (x), cl, action,
977 (GET_CODE (PATTERN (insn)) == COND_EXEC
978 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
981 case STRICT_LOW_PART:
982 scan_rtx (insn, &XEXP (x, 0), cl, action,
983 verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT);
988 scan_rtx (insn, &XEXP (x, 0), cl, action,
989 (type == OP_IN ? OP_IN :
990 verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT));
991 scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN);
992 scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN);
1001 /* Should only happen inside MEM. */
1005 scan_rtx (insn, &SET_DEST (x), cl, action,
1006 (GET_CODE (PATTERN (insn)) == COND_EXEC
1007 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
1011 scan_rtx (insn, &XEXP (x, 0), cl, action, type);
1013 scan_rtx (insn, &XEXP (x, 1), cl, action, type);
1020 fmt = GET_RTX_FORMAT (code);
1021 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1024 scan_rtx (insn, &XEXP (x, i), cl, action, type);
1025 else if (fmt[i] == 'E')
1026 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1027 scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type);
1031 /* Hide operands of the current insn (of which there are N_OPS) by
1032 substituting cc0 for them.
1033 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
1034 For every bit set in DO_NOT_HIDE, we leave the operand alone.
1035 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
1036 and earlyclobbers. */
1039 hide_operands (int n_ops, rtx *old_operands, rtx *old_dups,
1040 unsigned HOST_WIDE_INT do_not_hide, bool inout_and_ec_only)
1043 int alt = which_alternative;
1044 for (i = 0; i < n_ops; i++)
1046 old_operands[i] = recog_data.operand[i];
1047 /* Don't squash match_operator or match_parallel here, since
1048 we don't know that all of the contained registers are
1049 reachable by proper operands. */
1050 if (recog_data.constraints[i][0] == '\0')
1052 if (do_not_hide & (1 << i))
1054 if (!inout_and_ec_only || recog_data.operand_type[i] == OP_INOUT
1055 || recog_op_alt[i][alt].earlyclobber)
1056 *recog_data.operand_loc[i] = cc0_rtx;
1058 for (i = 0; i < recog_data.n_dups; i++)
1060 int opn = recog_data.dup_num[i];
1061 old_dups[i] = *recog_data.dup_loc[i];
1062 if (do_not_hide & (1 << opn))
1064 if (!inout_and_ec_only || recog_data.operand_type[opn] == OP_INOUT
1065 || recog_op_alt[opn][alt].earlyclobber)
1066 *recog_data.dup_loc[i] = cc0_rtx;
1070 /* Undo the substitution performed by hide_operands. INSN is the insn we
1071 are processing; the arguments are the same as in hide_operands. */
1074 restore_operands (rtx insn, int n_ops, rtx *old_operands, rtx *old_dups)
1077 for (i = 0; i < recog_data.n_dups; i++)
1078 *recog_data.dup_loc[i] = old_dups[i];
1079 for (i = 0; i < n_ops; i++)
1080 *recog_data.operand_loc[i] = old_operands[i];
1081 if (recog_data.n_dups)
1082 df_insn_rescan (insn);
1085 /* For each output operand of INSN, call scan_rtx to create a new
1086 open chain. Do this only for normal or earlyclobber outputs,
1087 depending on EARLYCLOBBER. */
1090 record_out_operands (rtx insn, bool earlyclobber)
1092 int n_ops = recog_data.n_operands;
1093 int alt = which_alternative;
1097 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1099 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1100 rtx *loc = (i < n_ops
1101 ? recog_data.operand_loc[opn]
1102 : recog_data.dup_loc[i - n_ops]);
1104 enum reg_class cl = recog_op_alt[opn][alt].cl;
1106 struct du_head *prev_open;
1108 if (recog_data.operand_type[opn] != OP_OUT
1109 || recog_op_alt[opn][alt].earlyclobber != earlyclobber)
1112 prev_open = open_chains;
1113 scan_rtx (insn, loc, cl, mark_write, OP_OUT);
1115 /* ??? Many targets have output constraints on the SET_DEST
1116 of a call insn, which is stupid, since these are certainly
1117 ABI defined hard registers. For these, and for asm operands
1118 that originally referenced hard registers, we must record that
1119 the chain cannot be renamed. */
1121 || (asm_noperands (PATTERN (insn)) > 0
1123 && REGNO (op) == ORIGINAL_REGNO (op)))
1125 if (prev_open != open_chains)
1126 open_chains->cannot_rename = 1;
1131 /* Build def/use chain. */
1133 static struct du_head *
1134 build_def_use (basic_block bb)
1138 unsigned HOST_WIDE_INT untracked_operands;
1140 open_chains = closed_chains = NULL;
1142 fail_current_block = false;
1145 bitmap_initialize (&open_chains_set, &bitmap_default_obstack);
1146 CLEAR_HARD_REG_SET (live_in_chains);
1147 REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb));
1148 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1150 df_ref def = *def_rec;
1151 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
1152 SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def));
1155 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
1157 if (NONDEBUG_INSN_P (insn))
1161 rtx old_operands[MAX_RECOG_OPERANDS];
1162 rtx old_dups[MAX_DUP_OPERANDS];
1166 enum rtx_code set_code = SET;
1167 enum rtx_code clobber_code = CLOBBER;
1169 /* Process the insn, determining its effect on the def-use
1170 chains and live hard registers. We perform the following
1171 steps with the register references in the insn, simulating
1173 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1174 by creating chains and marking hard regs live.
1175 (2) Any read outside an operand causes any chain it overlaps
1176 with to be marked unrenamable.
1177 (3) Any read inside an operand is added if there's already
1178 an open chain for it.
1179 (4) For any REG_DEAD note we find, close open chains that
1181 (5) For any non-earlyclobber write we find, close open chains
1183 (6) For any non-earlyclobber write we find in an operand, make
1184 a new chain or mark the hard register as live.
1185 (7) For any REG_UNUSED, close any chains we just opened.
1187 We cannot deal with situations where we track a reg in one mode
1188 and see a reference in another mode; these will cause the chain
1189 to be marked unrenamable or even cause us to abort the entire
1192 extract_insn (insn);
1193 if (! constrain_operands (1))
1194 fatal_insn_not_found (insn);
1195 preprocess_constraints ();
1196 alt = which_alternative;
1197 n_ops = recog_data.n_operands;
1198 untracked_operands = 0;
1200 /* Simplify the code below by rewriting things to reflect
1201 matching constraints. Also promote OP_OUT to OP_INOUT in
1202 predicated instructions, but only for register operands
1203 that are already tracked, so that we can create a chain
1204 when the first SET makes a register live. */
1206 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1207 for (i = 0; i < n_ops; ++i)
1209 rtx op = recog_data.operand[i];
1210 int matches = recog_op_alt[i][alt].matches;
1212 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
1213 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
1214 || (predicated && recog_data.operand_type[i] == OP_OUT))
1216 recog_data.operand_type[i] = OP_INOUT;
1217 /* A special case to deal with instruction patterns that
1218 have matching operands with different modes. If we're
1219 not already tracking such a reg, we won't start here,
1220 and we must instead make sure to make the operand visible
1221 to the machinery that tracks hard registers. */
1223 && (GET_MODE_SIZE (recog_data.operand_mode[i])
1224 != GET_MODE_SIZE (recog_data.operand_mode[matches]))
1225 && !verify_reg_in_set (op, &live_in_chains))
1227 untracked_operands |= 1 << i;
1228 untracked_operands |= 1 << matches;
1231 /* If there's an in-out operand with a register that is not
1232 being tracked at all yet, open a chain. */
1233 if (recog_data.operand_type[i] == OP_INOUT
1234 && !(untracked_operands & (1 << i))
1236 && !verify_reg_tracked (op))
1238 enum machine_mode mode = GET_MODE (op);
1239 unsigned this_regno = REGNO (op);
1240 unsigned this_nregs = hard_regno_nregs[this_regno][mode];
1241 create_new_chain (this_regno, this_nregs, NULL, NULL_RTX,
1246 if (fail_current_block)
1249 /* Step 1a: Mark hard registers that are clobbered in this insn,
1250 outside an operand, as live. */
1251 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1253 note_stores (PATTERN (insn), note_sets_clobbers, &clobber_code);
1254 restore_operands (insn, n_ops, old_operands, old_dups);
1256 /* Step 1b: Begin new chains for earlyclobbered writes inside
1258 record_out_operands (insn, true);
1260 /* Step 2: Mark chains for which we have reads outside operands
1262 We do this by munging all operands into CC0, and closing
1263 everything remaining. */
1265 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1267 scan_rtx (insn, &PATTERN (insn), NO_REGS, mark_all_read, OP_IN);
1268 restore_operands (insn, n_ops, old_operands, old_dups);
1270 /* Step 2B: Can't rename function call argument registers. */
1271 if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
1272 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
1273 NO_REGS, mark_all_read, OP_IN);
1275 /* Step 2C: Can't rename asm operands that were originally
1277 if (asm_noperands (PATTERN (insn)) > 0)
1278 for (i = 0; i < n_ops; i++)
1280 rtx *loc = recog_data.operand_loc[i];
1284 && REGNO (op) == ORIGINAL_REGNO (op)
1285 && (recog_data.operand_type[i] == OP_IN
1286 || recog_data.operand_type[i] == OP_INOUT))
1287 scan_rtx (insn, loc, NO_REGS, mark_all_read, OP_IN);
1290 /* Step 3: Append to chains for reads inside operands. */
1291 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1293 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1294 rtx *loc = (i < n_ops
1295 ? recog_data.operand_loc[opn]
1296 : recog_data.dup_loc[i - n_ops]);
1297 enum reg_class cl = recog_op_alt[opn][alt].cl;
1298 enum op_type type = recog_data.operand_type[opn];
1300 /* Don't scan match_operand here, since we've no reg class
1301 information to pass down. Any operands that we could
1302 substitute in will be represented elsewhere. */
1303 if (recog_data.constraints[opn][0] == '\0'
1304 || untracked_operands & (1 << opn))
1307 if (recog_op_alt[opn][alt].is_address)
1308 scan_rtx_address (insn, loc, cl, mark_read, VOIDmode);
1310 scan_rtx (insn, loc, cl, mark_read, type);
1313 /* Step 3B: Record updates for regs in REG_INC notes, and
1314 source regs in REG_FRAME_RELATED_EXPR notes. */
1315 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1316 if (REG_NOTE_KIND (note) == REG_INC
1317 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1318 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
1321 /* Step 4: Close chains for registers that die here. */
1322 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1323 if (REG_NOTE_KIND (note) == REG_DEAD)
1325 remove_from_hard_reg_set (&live_hard_regs,
1326 GET_MODE (XEXP (note, 0)),
1327 REGNO (XEXP (note, 0)));
1328 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1332 /* Step 4B: If this is a call, any chain live at this point
1333 requires a caller-saved reg. */
1337 for (p = open_chains; p; p = p->next_chain)
1338 p->need_caller_save_reg = 1;
1341 /* Step 5: Close open chains that overlap writes. Similar to
1342 step 2, we hide in-out operands, since we do not want to
1343 close these chains. We also hide earlyclobber operands,
1344 since we've opened chains for them in step 1, and earlier
1345 chains they would overlap with must have been closed at
1346 the previous insn at the latest, as such operands cannot
1347 possibly overlap with any input operands. */
1349 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1351 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN);
1352 restore_operands (insn, n_ops, old_operands, old_dups);
1354 /* Step 6a: Mark hard registers that are set in this insn,
1355 outside an operand, as live. */
1356 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1358 note_stores (PATTERN (insn), note_sets_clobbers, &set_code);
1359 restore_operands (insn, n_ops, old_operands, old_dups);
1361 /* Step 6b: Begin new chains for writes inside operands. */
1362 record_out_operands (insn, false);
1364 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1365 notes for update. */
1366 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1367 if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1368 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
1371 /* Step 7: Close chains for registers that were never
1372 really used here. */
1373 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1374 if (REG_NOTE_KIND (note) == REG_UNUSED)
1376 remove_from_hard_reg_set (&live_hard_regs,
1377 GET_MODE (XEXP (note, 0)),
1378 REGNO (XEXP (note, 0)));
1379 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1383 else if (DEBUG_INSN_P (insn)
1384 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)))
1386 scan_rtx (insn, &INSN_VAR_LOCATION_LOC (insn),
1387 ALL_REGS, mark_read, OP_IN);
1389 if (insn == BB_END (bb))
1393 bitmap_clear (&open_chains_set);
1395 if (fail_current_block)
1398 /* Since we close every chain when we find a REG_DEAD note, anything that
1399 is still open lives past the basic block, so it can't be renamed. */
1400 return closed_chains;
1404 gate_handle_regrename (void)
1406 return (optimize > 0 && (flag_rename_registers));
1409 struct rtl_opt_pass pass_regrename =
1414 gate_handle_regrename, /* gate */
1415 regrename_optimize, /* execute */
1418 0, /* static_pass_number */
1419 TV_RENAME_REGISTERS, /* tv_id */
1420 0, /* properties_required */
1421 0, /* properties_provided */
1422 0, /* properties_destroyed */
1423 0, /* todo_flags_start */
1424 TODO_df_finish | TODO_verify_rtl_sharing |
1425 0 /* todo_flags_finish */