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 is finished; zero if it is still open. */
89 unsigned int terminated:1;
90 /* Nonzero if the chain crosses a call. */
91 unsigned int need_caller_save_reg:1;
92 /* Nonzero if the register is used in a way that prevents renaming,
93 such as the SET_DEST of a CALL_INSN or an asm operand that used
94 to be a hard register. */
95 unsigned int cannot_rename:1;
98 /* This struct describes a single occurrence of a register. */
101 /* Links to the next occurrence of the register. */
102 struct du_chain *next_use;
104 /* The insn where the register appears. */
106 /* The location inside the insn. */
108 /* The register class required by the insn at this location. */
109 ENUM_BITFIELD(reg_class) cl : 16;
119 /* mark_access is for marking the destination regs in
120 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
121 note is updated properly. */
125 static const char * const scan_actions_name[] =
135 static struct obstack rename_obstack;
137 static void do_replace (struct du_head *, int);
138 static void scan_rtx_reg (rtx, rtx *, enum reg_class,
139 enum scan_actions, enum op_type);
140 static void scan_rtx_address (rtx, rtx *, enum reg_class,
141 enum scan_actions, enum machine_mode);
142 static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
144 static struct du_head *build_def_use (basic_block);
145 static void dump_def_use_chain (struct du_head *);
147 typedef struct du_head *du_head_p;
148 DEF_VEC_P (du_head_p);
149 DEF_VEC_ALLOC_P (du_head_p, heap);
150 static VEC(du_head_p, heap) *id_to_chain;
153 free_chain_data (void)
157 for (i = 0; VEC_iterate(du_head_p, id_to_chain, i, ptr); i++)
158 bitmap_clear (&ptr->conflicts);
160 VEC_free (du_head_p, heap, id_to_chain);
163 /* For a def-use chain HEAD, find which registers overlap its lifetime and
164 set the corresponding bits in *PSET. */
167 merge_overlapping_regs (HARD_REG_SET *pset, struct du_head *head)
171 IOR_HARD_REG_SET (*pset, head->hard_conflicts);
172 EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi)
174 du_head_p other = VEC_index (du_head_p, id_to_chain, i);
175 unsigned j = other->nregs;
177 SET_HARD_REG_BIT (*pset, other->regno + j);
181 /* Check if NEW_REG can be the candidate register to rename for
182 REG in THIS_HEAD chain. THIS_UNAVAILABLE is a set of unavailable hard
186 check_new_reg_p (int reg ATTRIBUTE_UNUSED, int new_reg,
187 struct du_head *this_head, HARD_REG_SET this_unavailable)
189 enum machine_mode mode = GET_MODE (*this_head->first->loc);
190 int nregs = hard_regno_nregs[new_reg][mode];
192 struct du_chain *tmp;
194 for (i = nregs - 1; i >= 0; --i)
195 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
196 || fixed_regs[new_reg + i]
197 || global_regs[new_reg + i]
198 /* Can't use regs which aren't saved by the prologue. */
199 || (! df_regs_ever_live_p (new_reg + i)
200 && ! call_used_regs[new_reg + i])
201 #ifdef LEAF_REGISTERS
202 /* We can't use a non-leaf register if we're in a
204 || (current_function_is_leaf
205 && !LEAF_REGISTERS[new_reg + i])
207 #ifdef HARD_REGNO_RENAME_OK
208 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
213 /* See whether it accepts all modes that occur in
214 definition and uses. */
215 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
216 if ((! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
217 && ! DEBUG_INSN_P (tmp->insn))
218 || (this_head->need_caller_save_reg
219 && ! (HARD_REGNO_CALL_PART_CLOBBERED
220 (reg, GET_MODE (*tmp->loc)))
221 && (HARD_REGNO_CALL_PART_CLOBBERED
222 (new_reg, GET_MODE (*tmp->loc)))))
228 /* Perform register renaming on the current function. */
231 regrename_optimize (void)
233 int tick[FIRST_PSEUDO_REGISTER];
238 df_set_flags (DF_LR_RUN_DCE);
239 df_note_add_problem ();
241 df_set_flags (DF_DEFER_INSN_RESCAN);
243 memset (tick, 0, sizeof tick);
245 gcc_obstack_init (&rename_obstack);
246 first_obj = XOBNEWVAR (&rename_obstack, char, 0);
250 struct du_head *all_chains = 0;
251 HARD_REG_SET unavailable;
253 HARD_REG_SET regs_seen;
254 CLEAR_HARD_REG_SET (regs_seen);
257 id_to_chain = VEC_alloc (du_head_p, heap, 0);
259 CLEAR_HARD_REG_SET (unavailable);
262 fprintf (dump_file, "\nBasic block %d:\n", bb->index);
264 all_chains = build_def_use (bb);
267 dump_def_use_chain (all_chains);
269 CLEAR_HARD_REG_SET (unavailable);
270 /* Don't clobber traceback for noreturn functions. */
271 if (frame_pointer_needed)
273 add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
274 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
275 add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
281 int new_reg, best_new_reg, best_nregs;
283 struct du_head *this_head = all_chains;
284 struct du_chain *tmp;
285 HARD_REG_SET this_unavailable;
286 int reg = this_head->regno;
288 enum reg_class super_class = NO_REGS;
289 enum reg_class preferred_class;
290 bool has_preferred_class;
292 all_chains = this_head->next_chain;
294 if (this_head->cannot_rename)
298 best_nregs = this_head->nregs;
300 #if 0 /* This just disables optimization opportunities. */
301 /* Only rename once we've seen the reg more than once. */
302 if (! TEST_HARD_REG_BIT (regs_seen, reg))
304 SET_HARD_REG_BIT (regs_seen, reg);
309 if (fixed_regs[reg] || global_regs[reg]
310 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
311 || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
313 || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
318 COPY_HARD_REG_SET (this_unavailable, unavailable);
320 /* Iterate over elements in the chain in order to:
321 1. Count number of uses, and narrow the set of registers we can
323 2. Compute the superunion of register classes in this chain. */
325 super_class = NO_REGS;
326 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
328 if (DEBUG_INSN_P (tmp->insn))
331 IOR_COMPL_HARD_REG_SET (this_unavailable,
332 reg_class_contents[tmp->cl]);
334 = reg_class_superunion[(int) super_class][(int) tmp->cl];
340 /* Further narrow the set of registers we can use for renaming.
341 If the chain needs a call-saved register, mark the call-used
342 registers as unavailable. */
343 if (this_head->need_caller_save_reg)
344 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
346 /* And mark registers that overlap its lifetime as unavailable. */
347 merge_overlapping_regs (&this_unavailable, this_head);
349 /* Compute preferred rename class of super union of all the classes
352 = (enum reg_class) targetm.preferred_rename_class (super_class);
354 /* If PREFERRED_CLASS is not NO_REGS, we iterate in the first pass
355 over registers that belong to PREFERRED_CLASS and try to find the
356 best register within the class. If that failed, we iterate in
357 the second pass over registers that don't belong to the class.
358 If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
359 ascending order without any preference. */
360 has_preferred_class = (preferred_class != NO_REGS);
361 for (pass = (has_preferred_class ? 0 : 1); pass < 2; pass++)
363 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
365 if (has_preferred_class
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 obstack_free (&rename_obstack, first_obj);
422 obstack_free (&rename_obstack, NULL);
425 fputc ('\n', dump_file);
431 do_replace (struct du_head *head, int reg)
433 struct du_chain *chain;
434 unsigned int base_regno = head->regno;
436 gcc_assert (! DEBUG_INSN_P (head->first->insn));
438 for (chain = head->first; chain; chain = chain->next_use)
440 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
441 struct reg_attrs *attr = REG_ATTRS (*chain->loc);
442 int reg_ptr = REG_POINTER (*chain->loc);
444 if (DEBUG_INSN_P (chain->insn) && REGNO (*chain->loc) != base_regno)
445 INSN_VAR_LOCATION_LOC (chain->insn) = gen_rtx_UNKNOWN_VAR_LOC ();
448 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
449 if (regno >= FIRST_PSEUDO_REGISTER)
450 ORIGINAL_REGNO (*chain->loc) = regno;
451 REG_ATTRS (*chain->loc) = attr;
452 REG_POINTER (*chain->loc) = reg_ptr;
455 df_insn_rescan (chain->insn);
460 /* Walk all chains starting with CHAINS and record that they conflict with
461 another chain whose id is ID. */
464 mark_conflict (struct du_head *chains, unsigned id)
468 bitmap_set_bit (&chains->conflicts, id);
469 chains = chains->next_chain;
473 /* True if we found a register with a size mismatch, which means that we
474 can't track its lifetime accurately. If so, we abort the current block
476 static bool fail_current_block;
478 /* The id to be given to the next opened chain. */
479 static unsigned current_id;
481 /* List of currently open chains, and closed chains that can be renamed. */
482 static struct du_head *open_chains;
483 static struct du_head *closed_chains;
485 /* Bitmap of open chains. The bits set always match the list found in
487 static bitmap_head open_chains_set;
489 /* Record the registers being tracked in open_chains. */
490 static HARD_REG_SET live_in_chains;
492 /* Record the registers that are live but not tracked. The intersection
493 between this and live_in_chains is empty. */
494 static HARD_REG_SET live_hard_regs;
496 /* Return true if OP is a reg for which all bits are set in PSET, false
497 if all bits are clear.
498 In other cases, set fail_current_block and return false. */
501 verify_reg_in_set (rtx op, HARD_REG_SET *pset)
503 unsigned regno, nregs;
504 bool all_live, all_dead;
509 nregs = hard_regno_nregs[regno][GET_MODE (op)];
510 all_live = all_dead = true;
512 if (TEST_HARD_REG_BIT (*pset, regno + nregs))
516 if (!all_dead && !all_live)
518 fail_current_block = true;
524 /* Return true if OP is a reg that is being tracked already in some form.
525 May set fail_current_block if it sees an unhandled case of overlap. */
528 verify_reg_tracked (rtx op)
530 return (verify_reg_in_set (op, &live_hard_regs)
531 || verify_reg_in_set (op, &live_in_chains));
534 /* Called through note_stores. DATA points to a rtx_code, either SET or
535 CLOBBER, which tells us which kind of rtx to look at. If we have a
536 match, record the set register in live_hard_regs and in the hard_conflicts
537 bitmap of open chains. */
540 note_sets_clobbers (rtx x, const_rtx set, void *data)
542 enum rtx_code code = *(enum rtx_code *)data;
543 struct du_head *chain;
545 if (GET_CODE (x) == SUBREG)
547 if (!REG_P (x) || GET_CODE (set) != code)
549 /* There must not be pseudos at this point. */
550 gcc_assert (HARD_REGISTER_P (x));
551 add_to_hard_reg_set (&live_hard_regs, GET_MODE (x), REGNO (x));
552 for (chain = open_chains; chain; chain = chain->next_chain)
553 add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x));
556 /* Create a new chain for THIS_NREGS registers starting at THIS_REGNO,
557 and record its occurrence in *LOC, which is being written to in INSN.
558 This access requires a register of class CL. */
561 create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc,
562 rtx insn, enum reg_class cl)
564 struct du_head *head = XOBNEW (&rename_obstack, struct du_head);
565 struct du_chain *this_du;
568 head->next_chain = open_chains;
570 head->regno = this_regno;
571 head->nregs = this_nregs;
572 head->need_caller_save_reg = 0;
573 head->cannot_rename = 0;
574 head->terminated = 0;
576 VEC_safe_push (du_head_p, heap, id_to_chain, head);
577 head->id = current_id++;
579 bitmap_initialize (&head->conflicts, &bitmap_default_obstack);
580 bitmap_copy (&head->conflicts, &open_chains_set);
581 mark_conflict (open_chains, head->id);
583 /* Since we're tracking this as a chain now, remove it from the
584 list of conflicting live hard registers and track it in
585 live_in_chains instead. */
589 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
590 CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
593 COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs);
594 bitmap_set_bit (&open_chains_set, head->id);
600 fprintf (dump_file, "Creating chain %s (%d)",
601 reg_names[head->regno], head->id);
602 if (insn != NULL_RTX)
603 fprintf (dump_file, " at insn %d", INSN_UID (insn));
604 fprintf (dump_file, "\n");
607 if (insn == NULL_RTX)
609 head->first = head->last = NULL;
613 this_du = XOBNEW (&rename_obstack, struct du_chain);
614 head->first = head->last = this_du;
616 this_du->next_use = 0;
618 this_du->insn = insn;
623 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
628 enum machine_mode mode = GET_MODE (x);
629 unsigned this_regno = REGNO (x);
630 unsigned this_nregs = hard_regno_nregs[this_regno][mode];
632 if (action == mark_write)
635 create_new_chain (this_regno, this_nregs, loc, insn, cl);
639 if ((type == OP_OUT) != (action == terminate_write || action == mark_access))
642 for (p = &open_chains; *p;)
644 struct du_head *head = *p;
645 struct du_head *next = head->next_chain;
646 int exact_match = (head->regno == this_regno
647 && head->nregs == this_nregs);
648 int superset = (this_regno <= head->regno
649 && this_regno + this_nregs >= head->regno + head->nregs);
650 int subset = (this_regno >= head->regno
651 && this_regno + this_nregs <= head->regno + head->nregs);
654 || head->regno + head->nregs <= this_regno
655 || this_regno + this_nregs <= head->regno)
657 p = &head->next_chain;
661 if (action == mark_read || action == mark_access)
663 /* ??? Class NO_REGS can happen if the md file makes use of
664 EXTRA_CONSTRAINTS to match registers. Which is arguably
665 wrong, but there we are. */
667 if (cl == NO_REGS || (!exact_match && !DEBUG_INSN_P (insn)))
671 "Cannot rename chain %s (%d) at insn %d (%s)\n",
672 reg_names[head->regno], head->id, INSN_UID (insn),
673 scan_actions_name[(int) action]);
674 head->cannot_rename = 1;
677 unsigned nregs = this_nregs;
678 head->regno = this_regno;
679 head->nregs = this_nregs;
681 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
684 "Widening register in chain %s (%d) at insn %d\n",
685 reg_names[head->regno], head->id, INSN_UID (insn));
689 fail_current_block = true;
692 "Failing basic block due to unhandled overlap\n");
697 struct du_chain *this_du;
698 this_du = XOBNEW (&rename_obstack, struct du_chain);
699 this_du->next_use = 0;
701 this_du->insn = insn;
703 if (head->first == NULL)
704 head->first = this_du;
706 head->last->next_use = this_du;
707 head->last = this_du;
709 /* Avoid adding the same location in a DEBUG_INSN multiple times,
710 which could happen with non-exact overlap. */
711 if (DEBUG_INSN_P (insn))
713 /* Otherwise, find any other chains that do not match exactly;
714 ensure they all get marked unrenamable. */
715 p = &head->next_chain;
719 /* Whether the terminated chain can be used for renaming
720 depends on the action and this being an exact match.
721 In either case, we remove this element from open_chains. */
723 if ((action == terminate_dead || action == terminate_write)
724 && (superset || subset))
728 head->terminated = 1;
729 if (subset && !superset)
730 head->cannot_rename = 1;
731 head->next_chain = closed_chains;
732 closed_chains = head;
733 bitmap_clear_bit (&open_chains_set, head->id);
738 CLEAR_HARD_REG_BIT (live_in_chains, head->regno + nregs);
739 if (subset && !superset
740 && (head->regno + nregs < this_regno
741 || head->regno + nregs >= this_regno + this_nregs))
742 SET_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
748 "Closing chain %s (%d) at insn %d (%s%s)\n",
749 reg_names[head->regno], head->id, INSN_UID (insn),
750 scan_actions_name[(int) action],
751 superset ? ", superset" : subset ? ", subset" : "");
753 else if (action == terminate_dead || action == terminate_write)
755 /* In this case, tracking liveness gets too hard. Fail the
756 entire basic block. */
759 "Failing basic block due to unhandled overlap\n");
760 fail_current_block = true;
765 head->cannot_rename = 1;
768 "Cannot rename chain %s (%d) at insn %d (%s)\n",
769 reg_names[head->regno], head->id, INSN_UID (insn),
770 scan_actions_name[(int) action]);
771 p = &head->next_chain;
776 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
777 BASE_REG_CLASS depending on how the register is being considered. */
780 scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl,
781 enum scan_actions action, enum machine_mode mode)
784 RTX_CODE code = GET_CODE (x);
788 if (action == mark_write || action == mark_access)
795 rtx orig_op0 = XEXP (x, 0);
796 rtx orig_op1 = XEXP (x, 1);
797 RTX_CODE code0 = GET_CODE (orig_op0);
798 RTX_CODE code1 = GET_CODE (orig_op1);
803 enum rtx_code index_code = SCRATCH;
805 if (GET_CODE (op0) == SUBREG)
807 op0 = SUBREG_REG (op0);
808 code0 = GET_CODE (op0);
811 if (GET_CODE (op1) == SUBREG)
813 op1 = SUBREG_REG (op1);
814 code1 = GET_CODE (op1);
817 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
818 || code0 == ZERO_EXTEND || code1 == MEM)
822 index_code = GET_CODE (*locI);
824 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
825 || code1 == ZERO_EXTEND || code0 == MEM)
829 index_code = GET_CODE (*locI);
831 else if (code0 == CONST_INT || code0 == CONST
832 || code0 == SYMBOL_REF || code0 == LABEL_REF)
835 index_code = GET_CODE (XEXP (x, 0));
837 else if (code1 == CONST_INT || code1 == CONST
838 || code1 == SYMBOL_REF || code1 == LABEL_REF)
841 index_code = GET_CODE (XEXP (x, 1));
843 else if (code0 == REG && code1 == REG)
846 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
848 if (REGNO_OK_FOR_INDEX_P (regno1)
849 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
851 else if (REGNO_OK_FOR_INDEX_P (regno0)
852 && regno_ok_for_base_p (regno1, mode, PLUS, REG))
854 else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
855 || REGNO_OK_FOR_INDEX_P (regno1))
857 else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
862 locI = &XEXP (x, index_op);
863 locB = &XEXP (x, !index_op);
864 index_code = GET_CODE (*locI);
866 else if (code0 == REG)
870 index_code = GET_CODE (*locI);
872 else if (code1 == REG)
876 index_code = GET_CODE (*locI);
880 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
882 scan_rtx_address (insn, locB, base_reg_class (mode, PLUS, index_code),
895 /* If the target doesn't claim to handle autoinc, this must be
896 something special, like a stack push. Kill this chain. */
897 action = mark_all_read;
902 scan_rtx_address (insn, &XEXP (x, 0),
903 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
908 scan_rtx_reg (insn, loc, cl, action, OP_IN);
915 fmt = GET_RTX_FORMAT (code);
916 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
919 scan_rtx_address (insn, &XEXP (x, i), cl, action, mode);
920 else if (fmt[i] == 'E')
921 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
922 scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode);
927 scan_rtx (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
932 enum rtx_code code = GET_CODE (x);
950 scan_rtx_reg (insn, loc, cl, action, type);
954 scan_rtx_address (insn, &XEXP (x, 0),
955 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
960 scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN);
961 scan_rtx (insn, &SET_DEST (x), cl, action,
962 (GET_CODE (PATTERN (insn)) == COND_EXEC
963 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
966 case STRICT_LOW_PART:
967 scan_rtx (insn, &XEXP (x, 0), cl, action,
968 verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT);
973 scan_rtx (insn, &XEXP (x, 0), cl, action,
974 (type == OP_IN ? OP_IN :
975 verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT));
976 scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN);
977 scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN);
986 /* Should only happen inside MEM. */
990 scan_rtx (insn, &SET_DEST (x), cl, action,
991 (GET_CODE (PATTERN (insn)) == COND_EXEC
992 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
996 scan_rtx (insn, &XEXP (x, 0), cl, action, type);
998 scan_rtx (insn, &XEXP (x, 1), cl, action, type);
1005 fmt = GET_RTX_FORMAT (code);
1006 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1009 scan_rtx (insn, &XEXP (x, i), cl, action, type);
1010 else if (fmt[i] == 'E')
1011 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1012 scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type);
1016 /* Hide operands of the current insn (of which there are N_OPS) by
1017 substituting cc0 for them.
1018 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
1019 For every bit set in DO_NOT_HIDE, we leave the operand alone.
1020 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
1021 and earlyclobbers. */
1024 hide_operands (int n_ops, rtx *old_operands, rtx *old_dups,
1025 unsigned HOST_WIDE_INT do_not_hide, bool inout_and_ec_only)
1028 int alt = which_alternative;
1029 for (i = 0; i < n_ops; i++)
1031 old_operands[i] = recog_data.operand[i];
1032 /* Don't squash match_operator or match_parallel here, since
1033 we don't know that all of the contained registers are
1034 reachable by proper operands. */
1035 if (recog_data.constraints[i][0] == '\0')
1037 if (do_not_hide & (1 << i))
1039 if (!inout_and_ec_only || recog_data.operand_type[i] == OP_INOUT
1040 || recog_op_alt[i][alt].earlyclobber)
1041 *recog_data.operand_loc[i] = cc0_rtx;
1043 for (i = 0; i < recog_data.n_dups; i++)
1045 int opn = recog_data.dup_num[i];
1046 old_dups[i] = *recog_data.dup_loc[i];
1047 if (do_not_hide & (1 << opn))
1049 if (!inout_and_ec_only || recog_data.operand_type[opn] == OP_INOUT
1050 || recog_op_alt[opn][alt].earlyclobber)
1051 *recog_data.dup_loc[i] = cc0_rtx;
1055 /* Undo the substitution performed by hide_operands. INSN is the insn we
1056 are processing; the arguments are the same as in hide_operands. */
1059 restore_operands (rtx insn, int n_ops, rtx *old_operands, rtx *old_dups)
1062 for (i = 0; i < recog_data.n_dups; i++)
1063 *recog_data.dup_loc[i] = old_dups[i];
1064 for (i = 0; i < n_ops; i++)
1065 *recog_data.operand_loc[i] = old_operands[i];
1066 if (recog_data.n_dups)
1067 df_insn_rescan (insn);
1070 /* For each output operand of INSN, call scan_rtx to create a new
1071 open chain. Do this only for normal or earlyclobber outputs,
1072 depending on EARLYCLOBBER. */
1075 record_out_operands (rtx insn, bool earlyclobber)
1077 int n_ops = recog_data.n_operands;
1078 int alt = which_alternative;
1082 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1084 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1085 rtx *loc = (i < n_ops
1086 ? recog_data.operand_loc[opn]
1087 : recog_data.dup_loc[i - n_ops]);
1089 enum reg_class cl = recog_op_alt[opn][alt].cl;
1091 struct du_head *prev_open;
1093 if (recog_data.operand_type[opn] != OP_OUT
1094 || recog_op_alt[opn][alt].earlyclobber != earlyclobber)
1097 prev_open = open_chains;
1098 scan_rtx (insn, loc, cl, mark_write, OP_OUT);
1100 /* ??? Many targets have output constraints on the SET_DEST
1101 of a call insn, which is stupid, since these are certainly
1102 ABI defined hard registers. For these, and for asm operands
1103 that originally referenced hard registers, we must record that
1104 the chain cannot be renamed. */
1106 || (asm_noperands (PATTERN (insn)) > 0
1108 && REGNO (op) == ORIGINAL_REGNO (op)))
1110 if (prev_open != open_chains)
1111 open_chains->cannot_rename = 1;
1116 /* Build def/use chain. */
1118 static struct du_head *
1119 build_def_use (basic_block bb)
1123 unsigned HOST_WIDE_INT untracked_operands;
1125 open_chains = closed_chains = NULL;
1127 fail_current_block = false;
1130 bitmap_initialize (&open_chains_set, &bitmap_default_obstack);
1131 CLEAR_HARD_REG_SET (live_in_chains);
1132 REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb));
1133 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1135 df_ref def = *def_rec;
1136 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
1137 SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def));
1140 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
1142 if (NONDEBUG_INSN_P (insn))
1146 rtx old_operands[MAX_RECOG_OPERANDS];
1147 rtx old_dups[MAX_DUP_OPERANDS];
1151 enum rtx_code set_code = SET;
1152 enum rtx_code clobber_code = CLOBBER;
1154 /* Process the insn, determining its effect on the def-use
1155 chains and live hard registers. We perform the following
1156 steps with the register references in the insn, simulating
1158 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1159 by creating chains and marking hard regs live.
1160 (2) Any read outside an operand causes any chain it overlaps
1161 with to be marked unrenamable.
1162 (3) Any read inside an operand is added if there's already
1163 an open chain for it.
1164 (4) For any REG_DEAD note we find, close open chains that
1166 (5) For any non-earlyclobber write we find, close open chains
1168 (6) For any non-earlyclobber write we find in an operand, make
1169 a new chain or mark the hard register as live.
1170 (7) For any REG_UNUSED, close any chains we just opened.
1172 We cannot deal with situations where we track a reg in one mode
1173 and see a reference in another mode; these will cause the chain
1174 to be marked unrenamable or even cause us to abort the entire
1177 extract_insn (insn);
1178 if (! constrain_operands (1))
1179 fatal_insn_not_found (insn);
1180 preprocess_constraints ();
1181 alt = which_alternative;
1182 n_ops = recog_data.n_operands;
1183 untracked_operands = 0;
1185 /* Simplify the code below by rewriting things to reflect
1186 matching constraints. Also promote OP_OUT to OP_INOUT in
1187 predicated instructions, but only for register operands
1188 that are already tracked, so that we can create a chain
1189 when the first SET makes a register live. */
1191 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1192 for (i = 0; i < n_ops; ++i)
1194 rtx op = recog_data.operand[i];
1195 int matches = recog_op_alt[i][alt].matches;
1197 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
1198 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
1199 || (predicated && recog_data.operand_type[i] == OP_OUT))
1201 recog_data.operand_type[i] = OP_INOUT;
1202 /* A special case to deal with instruction patterns that
1203 have matching operands with different modes. If we're
1204 not already tracking such a reg, we won't start here,
1205 and we must instead make sure to make the operand visible
1206 to the machinery that tracks hard registers. */
1208 && (GET_MODE_SIZE (recog_data.operand_mode[i])
1209 != GET_MODE_SIZE (recog_data.operand_mode[matches]))
1210 && !verify_reg_in_set (op, &live_in_chains))
1212 untracked_operands |= 1 << i;
1213 untracked_operands |= 1 << matches;
1216 /* If there's an in-out operand with a register that is not
1217 being tracked at all yet, open a chain. */
1218 if (recog_data.operand_type[i] == OP_INOUT
1219 && !(untracked_operands & (1 << i))
1221 && !verify_reg_tracked (op))
1223 enum machine_mode mode = GET_MODE (op);
1224 unsigned this_regno = REGNO (op);
1225 unsigned this_nregs = hard_regno_nregs[this_regno][mode];
1226 create_new_chain (this_regno, this_nregs, NULL, NULL_RTX,
1231 if (fail_current_block)
1234 /* Step 1a: Mark hard registers that are clobbered in this insn,
1235 outside an operand, as live. */
1236 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1238 note_stores (PATTERN (insn), note_sets_clobbers, &clobber_code);
1239 restore_operands (insn, n_ops, old_operands, old_dups);
1241 /* Step 1b: Begin new chains for earlyclobbered writes inside
1243 record_out_operands (insn, true);
1245 /* Step 2: Mark chains for which we have reads outside operands
1247 We do this by munging all operands into CC0, and closing
1248 everything remaining. */
1250 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1252 scan_rtx (insn, &PATTERN (insn), NO_REGS, mark_all_read, OP_IN);
1253 restore_operands (insn, n_ops, old_operands, old_dups);
1255 /* Step 2B: Can't rename function call argument registers. */
1256 if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
1257 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
1258 NO_REGS, mark_all_read, OP_IN);
1260 /* Step 2C: Can't rename asm operands that were originally
1262 if (asm_noperands (PATTERN (insn)) > 0)
1263 for (i = 0; i < n_ops; i++)
1265 rtx *loc = recog_data.operand_loc[i];
1269 && REGNO (op) == ORIGINAL_REGNO (op)
1270 && (recog_data.operand_type[i] == OP_IN
1271 || recog_data.operand_type[i] == OP_INOUT))
1272 scan_rtx (insn, loc, NO_REGS, mark_all_read, OP_IN);
1275 /* Step 3: Append to chains for reads inside operands. */
1276 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1278 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1279 rtx *loc = (i < n_ops
1280 ? recog_data.operand_loc[opn]
1281 : recog_data.dup_loc[i - n_ops]);
1282 enum reg_class cl = recog_op_alt[opn][alt].cl;
1283 enum op_type type = recog_data.operand_type[opn];
1285 /* Don't scan match_operand here, since we've no reg class
1286 information to pass down. Any operands that we could
1287 substitute in will be represented elsewhere. */
1288 if (recog_data.constraints[opn][0] == '\0'
1289 || untracked_operands & (1 << opn))
1292 if (recog_op_alt[opn][alt].is_address)
1293 scan_rtx_address (insn, loc, cl, mark_read, VOIDmode);
1295 scan_rtx (insn, loc, cl, mark_read, type);
1298 /* Step 3B: Record updates for regs in REG_INC notes, and
1299 source regs in REG_FRAME_RELATED_EXPR notes. */
1300 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1301 if (REG_NOTE_KIND (note) == REG_INC
1302 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1303 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
1306 /* Step 4: Close chains for registers that die here. */
1307 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1308 if (REG_NOTE_KIND (note) == REG_DEAD)
1310 remove_from_hard_reg_set (&live_hard_regs,
1311 GET_MODE (XEXP (note, 0)),
1312 REGNO (XEXP (note, 0)));
1313 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1317 /* Step 4B: If this is a call, any chain live at this point
1318 requires a caller-saved reg. */
1322 for (p = open_chains; p; p = p->next_chain)
1323 p->need_caller_save_reg = 1;
1326 /* Step 5: Close open chains that overlap writes. Similar to
1327 step 2, we hide in-out operands, since we do not want to
1328 close these chains. We also hide earlyclobber operands,
1329 since we've opened chains for them in step 1, and earlier
1330 chains they would overlap with must have been closed at
1331 the previous insn at the latest, as such operands cannot
1332 possibly overlap with any input operands. */
1334 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1336 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN);
1337 restore_operands (insn, n_ops, old_operands, old_dups);
1339 /* Step 6a: Mark hard registers that are set in this insn,
1340 outside an operand, as live. */
1341 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1343 note_stores (PATTERN (insn), note_sets_clobbers, &set_code);
1344 restore_operands (insn, n_ops, old_operands, old_dups);
1346 /* Step 6b: Begin new chains for writes inside operands. */
1347 record_out_operands (insn, false);
1349 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1350 notes for update. */
1351 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1352 if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1353 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
1356 /* Step 7: Close chains for registers that were never
1357 really used here. */
1358 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1359 if (REG_NOTE_KIND (note) == REG_UNUSED)
1361 remove_from_hard_reg_set (&live_hard_regs,
1362 GET_MODE (XEXP (note, 0)),
1363 REGNO (XEXP (note, 0)));
1364 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1368 else if (DEBUG_INSN_P (insn)
1369 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)))
1371 scan_rtx (insn, &INSN_VAR_LOCATION_LOC (insn),
1372 ALL_REGS, mark_read, OP_IN);
1374 if (insn == BB_END (bb))
1378 bitmap_clear (&open_chains_set);
1380 if (fail_current_block)
1383 /* Since we close every chain when we find a REG_DEAD note, anything that
1384 is still open lives past the basic block, so it can't be renamed. */
1385 return closed_chains;
1388 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
1389 printed in reverse order as that's how we build them. */
1392 dump_def_use_chain (struct du_head *head)
1396 struct du_chain *this_du = head->first;
1397 fprintf (dump_file, "Register %s (%d):",
1398 reg_names[head->regno], head->nregs);
1401 fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
1402 reg_class_names[this_du->cl]);
1403 this_du = this_du->next_use;
1405 fprintf (dump_file, "\n");
1406 head = head->next_chain;
1412 gate_handle_regrename (void)
1414 return (optimize > 0 && (flag_rename_registers));
1417 struct rtl_opt_pass pass_regrename =
1422 gate_handle_regrename, /* gate */
1423 regrename_optimize, /* execute */
1426 0, /* static_pass_number */
1427 TV_RENAME_REGISTERS, /* tv_id */
1428 0, /* properties_required */
1429 0, /* properties_provided */
1430 0, /* properties_destroyed */
1431 0, /* todo_flags_start */
1432 TODO_df_finish | TODO_verify_rtl_sharing |
1433 0 /* todo_flags_finish */