1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 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"
27 #include "insn-config.h"
29 #include "addresses.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
40 #include "tree-pass.h"
43 #if HOST_BITS_PER_WIDE_INT <= MAX_RECOG_OPERANDS
44 #error "Use a different bitmap implementation for untracked_operands."
47 /* We keep linked lists of DU_HEAD structures, each of which describes
48 a chain of occurrences of a reg. */
52 struct du_head *next_chain;
53 /* The first and last elements of this chain. */
54 struct du_chain *first, *last;
55 /* Describes the register being tracked. */
56 unsigned regno, nregs;
58 /* A unique id to be used as an index into the conflicts bitmaps. */
60 /* A bitmap to record conflicts with other chains. */
61 bitmap_head conflicts;
62 /* Conflicts with untracked hard registers. */
63 HARD_REG_SET hard_conflicts;
65 /* Nonzero if the chain is finished; zero if it is still open. */
66 unsigned int terminated:1;
67 /* Nonzero if the chain crosses a call. */
68 unsigned int need_caller_save_reg:1;
69 /* Nonzero if the register is used in a way that prevents renaming,
70 such as the SET_DEST of a CALL_INSN or an asm operand that used
71 to be a hard register. */
72 unsigned int cannot_rename:1;
75 /* This struct describes a single occurrence of a register. */
78 /* Links to the next occurrence of the register. */
79 struct du_chain *next_use;
81 /* The insn where the register appears. */
83 /* The location inside the insn. */
85 /* The register class required by the insn at this location. */
86 ENUM_BITFIELD(reg_class) cl : 16;
96 /* mark_access is for marking the destination regs in
97 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
98 note is updated properly. */
102 static const char * const scan_actions_name[] =
112 static struct obstack rename_obstack;
114 static void do_replace (struct du_head *, int);
115 static void scan_rtx_reg (rtx, rtx *, enum reg_class,
116 enum scan_actions, enum op_type);
117 static void scan_rtx_address (rtx, rtx *, enum reg_class,
118 enum scan_actions, enum machine_mode);
119 static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
121 static struct du_head *build_def_use (basic_block);
122 static void dump_def_use_chain (struct du_head *);
124 typedef struct du_head *du_head_p;
125 DEF_VEC_P (du_head_p);
126 DEF_VEC_ALLOC_P (du_head_p, heap);
127 static VEC(du_head_p, heap) *id_to_chain;
130 free_chain_data (void)
134 for (i = 0; VEC_iterate(du_head_p, id_to_chain, i, ptr); i++)
135 bitmap_clear (&ptr->conflicts);
137 VEC_free (du_head_p, heap, id_to_chain);
140 /* For a def-use chain HEAD, find which registers overlap its lifetime and
141 set the corresponding bits in *PSET. */
144 merge_overlapping_regs (HARD_REG_SET *pset, struct du_head *head)
148 IOR_HARD_REG_SET (*pset, head->hard_conflicts);
149 EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi)
151 du_head_p other = VEC_index (du_head_p, id_to_chain, i);
152 unsigned j = other->nregs;
154 SET_HARD_REG_BIT (*pset, other->regno + j);
158 /* Perform register renaming on the current function. */
161 regrename_optimize (void)
163 int tick[FIRST_PSEUDO_REGISTER];
168 df_set_flags (DF_LR_RUN_DCE);
169 df_note_add_problem ();
171 df_set_flags (DF_DEFER_INSN_RESCAN);
173 memset (tick, 0, sizeof tick);
175 gcc_obstack_init (&rename_obstack);
176 first_obj = XOBNEWVAR (&rename_obstack, char, 0);
180 struct du_head *all_chains = 0;
181 HARD_REG_SET unavailable;
183 HARD_REG_SET regs_seen;
184 CLEAR_HARD_REG_SET (regs_seen);
187 id_to_chain = VEC_alloc (du_head_p, heap, 0);
189 CLEAR_HARD_REG_SET (unavailable);
192 fprintf (dump_file, "\nBasic block %d:\n", bb->index);
194 all_chains = build_def_use (bb);
197 dump_def_use_chain (all_chains);
199 CLEAR_HARD_REG_SET (unavailable);
200 /* Don't clobber traceback for noreturn functions. */
201 if (frame_pointer_needed)
203 add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
204 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
205 add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
211 int new_reg, best_new_reg, best_nregs;
213 struct du_head *this_head = all_chains;
214 struct du_chain *tmp;
215 HARD_REG_SET this_unavailable;
216 int reg = this_head->regno;
219 all_chains = this_head->next_chain;
221 if (this_head->cannot_rename)
225 best_nregs = this_head->nregs;
227 #if 0 /* This just disables optimization opportunities. */
228 /* Only rename once we've seen the reg more than once. */
229 if (! TEST_HARD_REG_BIT (regs_seen, reg))
231 SET_HARD_REG_BIT (regs_seen, reg);
236 if (fixed_regs[reg] || global_regs[reg]
237 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
238 || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
240 || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
245 COPY_HARD_REG_SET (this_unavailable, unavailable);
247 /* Count number of uses, and narrow the set of registers we can
250 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
252 if (DEBUG_INSN_P (tmp->insn))
255 IOR_COMPL_HARD_REG_SET (this_unavailable,
256 reg_class_contents[tmp->cl]);
262 if (this_head->need_caller_save_reg)
263 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
265 merge_overlapping_regs (&this_unavailable, this_head);
267 /* Now potential_regs is a reasonable approximation, let's
268 have a closer look at each register still in there. */
269 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
271 enum machine_mode mode = GET_MODE (*this_head->first->loc);
272 int nregs = hard_regno_nregs[new_reg][mode];
274 for (i = nregs - 1; i >= 0; --i)
275 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
276 || fixed_regs[new_reg + i]
277 || global_regs[new_reg + i]
278 /* Can't use regs which aren't saved by the prologue. */
279 || (! df_regs_ever_live_p (new_reg + i)
280 && ! call_used_regs[new_reg + i])
281 #ifdef LEAF_REGISTERS
282 /* We can't use a non-leaf register if we're in a
284 || (current_function_is_leaf
285 && !LEAF_REGISTERS[new_reg + i])
287 #ifdef HARD_REGNO_RENAME_OK
288 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
295 /* See whether it accepts all modes that occur in
296 definition and uses. */
297 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
298 if ((! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
299 && ! DEBUG_INSN_P (tmp->insn))
300 || (this_head->need_caller_save_reg
301 && ! (HARD_REGNO_CALL_PART_CLOBBERED
302 (reg, GET_MODE (*tmp->loc)))
303 && (HARD_REGNO_CALL_PART_CLOBBERED
304 (new_reg, GET_MODE (*tmp->loc)))))
308 if (tick[best_new_reg] > tick[new_reg])
310 best_new_reg = new_reg;
318 fprintf (dump_file, "Register %s in insn %d",
319 reg_names[reg], INSN_UID (this_head->first->insn));
320 if (this_head->need_caller_save_reg)
321 fprintf (dump_file, " crosses a call");
324 if (best_new_reg == reg)
326 tick[reg] = ++this_tick;
328 fprintf (dump_file, "; no available better choice\n");
333 fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
335 do_replace (this_head, best_new_reg);
336 this_head->regno = best_new_reg;
337 this_head->nregs = best_nregs;
338 tick[best_new_reg] = ++this_tick;
339 df_set_regs_ever_live (best_new_reg, true);
343 obstack_free (&rename_obstack, first_obj);
346 obstack_free (&rename_obstack, NULL);
349 fputc ('\n', dump_file);
355 do_replace (struct du_head *head, int reg)
357 struct du_chain *chain;
358 unsigned int base_regno = head->regno;
359 bool found_note = false;
361 gcc_assert (! DEBUG_INSN_P (head->first->insn));
363 for (chain = head->first; chain; chain = chain->next_use)
365 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
366 struct reg_attrs *attr = REG_ATTRS (*chain->loc);
367 int reg_ptr = REG_POINTER (*chain->loc);
369 if (DEBUG_INSN_P (chain->insn) && REGNO (*chain->loc) != base_regno)
370 INSN_VAR_LOCATION_LOC (chain->insn) = gen_rtx_UNKNOWN_VAR_LOC ();
375 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
376 if (regno >= FIRST_PSEUDO_REGISTER)
377 ORIGINAL_REGNO (*chain->loc) = regno;
378 REG_ATTRS (*chain->loc) = attr;
379 REG_POINTER (*chain->loc) = reg_ptr;
381 for (note = REG_NOTES (chain->insn); note; note = XEXP (note, 1))
383 enum reg_note kind = REG_NOTE_KIND (note);
384 if (kind == REG_DEAD || kind == REG_UNUSED)
386 rtx reg = XEXP (note, 0);
387 gcc_assert (HARD_REGISTER_P (reg));
389 if (REGNO (reg) == base_regno)
393 && reg_set_p (*chain->loc, chain->insn))
394 remove_note (chain->insn, note);
396 XEXP (note, 0) = *chain->loc;
403 df_insn_rescan (chain->insn);
407 /* If the chain's first insn is the same as the last, we should have
408 found a REG_UNUSED note. */
409 gcc_assert (head->first->insn != head->last->insn);
410 if (!reg_set_p (*head->last->loc, head->last->insn))
411 add_reg_note (head->last->insn, REG_DEAD, *head->last->loc);
416 /* Walk all chains starting with CHAINS and record that they conflict with
417 another chain whose id is ID. */
420 mark_conflict (struct du_head *chains, unsigned id)
424 bitmap_set_bit (&chains->conflicts, id);
425 chains = chains->next_chain;
429 /* True if we found a register with a size mismatch, which means that we
430 can't track its lifetime accurately. If so, we abort the current block
432 static bool fail_current_block;
434 /* The id to be given to the next opened chain. */
435 static unsigned current_id;
437 /* List of currently open chains, and closed chains that can be renamed. */
438 static struct du_head *open_chains;
439 static struct du_head *closed_chains;
441 /* Bitmap of open chains. The bits set always match the list found in
443 static bitmap_head open_chains_set;
445 /* Record the registers being tracked in open_chains. */
446 static HARD_REG_SET live_in_chains;
448 /* Record the registers that are live but not tracked. The intersection
449 between this and live_in_chains is empty. */
450 static HARD_REG_SET live_hard_regs;
452 /* Return true if OP is a reg for which all bits are set in PSET, false
453 if all bits are clear.
454 In other cases, set fail_current_block and return false. */
457 verify_reg_in_set (rtx op, HARD_REG_SET *pset)
459 unsigned regno, nregs;
460 bool all_live, all_dead;
465 nregs = hard_regno_nregs[regno][GET_MODE (op)];
466 all_live = all_dead = true;
468 if (TEST_HARD_REG_BIT (*pset, regno + nregs))
472 if (!all_dead && !all_live)
474 fail_current_block = true;
480 /* Return true if OP is a reg that is being tracked already in some form.
481 May set fail_current_block if it sees an unhandled case of overlap. */
484 verify_reg_tracked (rtx op)
486 return (verify_reg_in_set (op, &live_hard_regs)
487 || verify_reg_in_set (op, &live_in_chains));
490 /* Called through note_stores. DATA points to a rtx_code, either SET or
491 CLOBBER, which tells us which kind of rtx to look at. If we have a
492 match, record the set register in live_hard_regs and in the hard_conflicts
493 bitmap of open chains. */
496 note_sets_clobbers (rtx x, const_rtx set, void *data)
498 enum rtx_code code = *(enum rtx_code *)data;
499 struct du_head *chain;
501 if (GET_CODE (x) == SUBREG)
503 if (!REG_P (x) || GET_CODE (set) != code)
505 /* There must not be pseudos at this point. */
506 gcc_assert (HARD_REGISTER_P (x));
507 add_to_hard_reg_set (&live_hard_regs, GET_MODE (x), REGNO (x));
508 for (chain = open_chains; chain; chain = chain->next_chain)
509 add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x));
513 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
518 enum machine_mode mode = GET_MODE (x);
519 unsigned this_regno = REGNO (x);
520 unsigned this_nregs = hard_regno_nregs[this_regno][mode];
522 if (action == mark_write)
526 struct du_head *head = XOBNEW (&rename_obstack, struct du_head);
527 struct du_chain *this_du = XOBNEW (&rename_obstack, struct du_chain);
530 head->next_chain = open_chains;
532 head->first = head->last = this_du;
533 head->regno = this_regno;
534 head->nregs = this_nregs;
535 head->need_caller_save_reg = 0;
536 head->cannot_rename = 0;
537 head->terminated = 0;
539 VEC_safe_push (du_head_p, heap, id_to_chain, head);
540 head->id = current_id++;
542 bitmap_initialize (&head->conflicts, &bitmap_default_obstack);
543 bitmap_copy (&head->conflicts, &open_chains_set);
544 mark_conflict (open_chains, head->id);
546 /* Since we're tracking this as a chain now, remove it from the
547 list of conflicting live hard registers and track it in
548 live_in_chains instead. */
552 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
553 CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
556 COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs);
557 bitmap_set_bit (&open_chains_set, head->id);
561 this_du->next_use = 0;
563 this_du->insn = insn;
568 "Creating chain %s (%d) at insn %d (%s)\n",
569 reg_names[head->regno], head->id, INSN_UID (insn),
570 scan_actions_name[(int) action]);
575 if ((type == OP_OUT) != (action == terminate_write || action == mark_access))
578 for (p = &open_chains; *p;)
580 struct du_head *head = *p;
581 struct du_head *next = head->next_chain;
582 int exact_match = (head->regno == this_regno
583 && head->nregs == this_nregs);
584 int superset = (this_regno <= head->regno
585 && this_regno + this_nregs >= head->regno + head->nregs);
586 int subset = (this_regno >= head->regno
587 && this_regno + this_nregs <= head->regno + head->nregs);
590 || head->regno + head->nregs <= this_regno
591 || this_regno + this_nregs <= head->regno)
593 p = &head->next_chain;
597 if (action == mark_read || action == mark_access)
599 /* ??? Class NO_REGS can happen if the md file makes use of
600 EXTRA_CONSTRAINTS to match registers. Which is arguably
601 wrong, but there we are. */
603 if (cl == NO_REGS || (!exact_match && !DEBUG_INSN_P (insn)))
607 "Cannot rename chain %s (%d) at insn %d (%s)\n",
608 reg_names[head->regno], head->id, INSN_UID (insn),
609 scan_actions_name[(int) action]);
610 head->cannot_rename = 1;
613 unsigned nregs = this_nregs;
614 head->regno = this_regno;
615 head->nregs = this_nregs;
617 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
620 "Widening register in chain %s (%d) at insn %d\n",
621 reg_names[head->regno], head->id, INSN_UID (insn));
625 fail_current_block = true;
628 "Failing basic block due to unhandled overlap\n");
633 struct du_chain *this_du;
634 this_du = XOBNEW (&rename_obstack, struct du_chain);
635 this_du->next_use = 0;
637 this_du->insn = insn;
639 head->last->next_use = this_du;
640 head->last = this_du;
643 /* Avoid adding the same location in a DEBUG_INSN multiple times,
644 which could happen with non-exact overlap. */
645 if (DEBUG_INSN_P (insn))
647 /* Otherwise, find any other chains that do not match exactly;
648 ensure they all get marked unrenamable. */
649 p = &head->next_chain;
653 /* Whether the terminated chain can be used for renaming
654 depends on the action and this being an exact match.
655 In either case, we remove this element from open_chains. */
657 if ((action == terminate_dead || action == terminate_write)
662 head->terminated = 1;
663 head->next_chain = closed_chains;
664 closed_chains = head;
665 bitmap_clear_bit (&open_chains_set, head->id);
669 CLEAR_HARD_REG_BIT (live_in_chains, head->regno + nregs);
674 "Closing chain %s (%d) at insn %d (%s)\n",
675 reg_names[head->regno], head->id, INSN_UID (insn),
676 scan_actions_name[(int) action]);
678 else if (action == terminate_dead || action == terminate_write)
680 /* In this case, tracking liveness gets too hard. Fail the
681 entire basic block. */
684 "Failing basic block due to unhandled overlap\n");
685 fail_current_block = true;
690 head->cannot_rename = 1;
693 "Cannot rename chain %s (%d) at insn %d (%s)\n",
694 reg_names[head->regno], head->id, INSN_UID (insn),
695 scan_actions_name[(int) action]);
696 p = &head->next_chain;
701 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
702 BASE_REG_CLASS depending on how the register is being considered. */
705 scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl,
706 enum scan_actions action, enum machine_mode mode)
709 RTX_CODE code = GET_CODE (x);
713 if (action == mark_write || action == mark_access)
720 rtx orig_op0 = XEXP (x, 0);
721 rtx orig_op1 = XEXP (x, 1);
722 RTX_CODE code0 = GET_CODE (orig_op0);
723 RTX_CODE code1 = GET_CODE (orig_op1);
728 enum rtx_code index_code = SCRATCH;
730 if (GET_CODE (op0) == SUBREG)
732 op0 = SUBREG_REG (op0);
733 code0 = GET_CODE (op0);
736 if (GET_CODE (op1) == SUBREG)
738 op1 = SUBREG_REG (op1);
739 code1 = GET_CODE (op1);
742 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
743 || code0 == ZERO_EXTEND || code1 == MEM)
747 index_code = GET_CODE (*locI);
749 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
750 || code1 == ZERO_EXTEND || code0 == MEM)
754 index_code = GET_CODE (*locI);
756 else if (code0 == CONST_INT || code0 == CONST
757 || code0 == SYMBOL_REF || code0 == LABEL_REF)
760 index_code = GET_CODE (XEXP (x, 0));
762 else if (code1 == CONST_INT || code1 == CONST
763 || code1 == SYMBOL_REF || code1 == LABEL_REF)
766 index_code = GET_CODE (XEXP (x, 1));
768 else if (code0 == REG && code1 == REG)
771 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
773 if (REGNO_OK_FOR_INDEX_P (regno1)
774 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
776 else if (REGNO_OK_FOR_INDEX_P (regno0)
777 && regno_ok_for_base_p (regno1, mode, PLUS, REG))
779 else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
780 || REGNO_OK_FOR_INDEX_P (regno1))
782 else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
787 locI = &XEXP (x, index_op);
788 locB = &XEXP (x, !index_op);
789 index_code = GET_CODE (*locI);
791 else if (code0 == REG)
795 index_code = GET_CODE (*locI);
797 else if (code1 == REG)
801 index_code = GET_CODE (*locI);
805 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
807 scan_rtx_address (insn, locB, base_reg_class (mode, PLUS, index_code),
820 /* If the target doesn't claim to handle autoinc, this must be
821 something special, like a stack push. Kill this chain. */
822 action = mark_all_read;
827 scan_rtx_address (insn, &XEXP (x, 0),
828 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
833 scan_rtx_reg (insn, loc, cl, action, OP_IN);
840 fmt = GET_RTX_FORMAT (code);
841 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
844 scan_rtx_address (insn, &XEXP (x, i), cl, action, mode);
845 else if (fmt[i] == 'E')
846 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
847 scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode);
852 scan_rtx (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
857 enum rtx_code code = GET_CODE (x);
875 scan_rtx_reg (insn, loc, cl, action, type);
879 scan_rtx_address (insn, &XEXP (x, 0),
880 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
885 scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN);
886 scan_rtx (insn, &SET_DEST (x), cl, action,
887 (GET_CODE (PATTERN (insn)) == COND_EXEC
888 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
891 case STRICT_LOW_PART:
892 scan_rtx (insn, &XEXP (x, 0), cl, action, OP_INOUT);
897 scan_rtx (insn, &XEXP (x, 0), cl, action,
898 type == OP_IN ? OP_IN : OP_INOUT);
899 scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN);
900 scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN);
909 /* Should only happen inside MEM. */
913 scan_rtx (insn, &SET_DEST (x), cl, action,
914 (GET_CODE (PATTERN (insn)) == COND_EXEC
915 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
919 scan_rtx (insn, &XEXP (x, 0), cl, action, type);
921 scan_rtx (insn, &XEXP (x, 1), cl, action, type);
928 fmt = GET_RTX_FORMAT (code);
929 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
932 scan_rtx (insn, &XEXP (x, i), cl, action, type);
933 else if (fmt[i] == 'E')
934 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
935 scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type);
939 /* Hide operands of the current insn (of which there are N_OPS) by
940 substituting cc0 for them.
941 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
942 For every bit set in DO_NOT_HIDE, we leave the operand alone.
943 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
944 and earlyclobbers. */
947 hide_operands (int n_ops, rtx *old_operands, rtx *old_dups,
948 unsigned HOST_WIDE_INT do_not_hide, bool inout_and_ec_only)
951 int alt = which_alternative;
952 for (i = 0; i < n_ops; i++)
954 old_operands[i] = recog_data.operand[i];
955 /* Don't squash match_operator or match_parallel here, since
956 we don't know that all of the contained registers are
957 reachable by proper operands. */
958 if (recog_data.constraints[i][0] == '\0')
960 if (do_not_hide & (1 << i))
962 if (!inout_and_ec_only || recog_data.operand_type[i] == OP_INOUT
963 || recog_op_alt[i][alt].earlyclobber)
964 *recog_data.operand_loc[i] = cc0_rtx;
966 for (i = 0; i < recog_data.n_dups; i++)
968 int opn = recog_data.dup_num[i];
969 old_dups[i] = *recog_data.dup_loc[i];
970 if (do_not_hide & (1 << opn))
972 if (!inout_and_ec_only || recog_data.operand_type[opn] == OP_INOUT
973 || recog_op_alt[opn][alt].earlyclobber)
974 *recog_data.dup_loc[i] = cc0_rtx;
978 /* Undo the substitution performed by hide_operands. INSN is the insn we
979 are processing; the arguments are the same as in hide_operands. */
982 restore_operands (rtx insn, int n_ops, rtx *old_operands, rtx *old_dups)
985 for (i = 0; i < recog_data.n_dups; i++)
986 *recog_data.dup_loc[i] = old_dups[i];
987 for (i = 0; i < n_ops; i++)
988 *recog_data.operand_loc[i] = old_operands[i];
989 if (recog_data.n_dups)
990 df_insn_rescan (insn);
993 /* For each output operand of INSN, call scan_rtx to create a new
994 open chain. Do this only for normal or earlyclobber outputs,
995 depending on EARLYCLOBBER. */
998 record_out_operands (rtx insn, bool earlyclobber)
1000 int n_ops = recog_data.n_operands;
1001 int alt = which_alternative;
1005 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1007 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1008 rtx *loc = (i < n_ops
1009 ? recog_data.operand_loc[opn]
1010 : recog_data.dup_loc[i - n_ops]);
1012 enum reg_class cl = recog_op_alt[opn][alt].cl;
1014 struct du_head *prev_open;
1016 if (recog_data.operand_type[opn] != OP_OUT
1017 || recog_op_alt[opn][alt].earlyclobber != earlyclobber)
1020 prev_open = open_chains;
1021 scan_rtx (insn, loc, cl, mark_write, OP_OUT);
1023 /* ??? Many targets have output constraints on the SET_DEST
1024 of a call insn, which is stupid, since these are certainly
1025 ABI defined hard registers. For these, and for asm operands
1026 that originally referenced hard registers, we must record that
1027 the chain cannot be renamed. */
1029 || (asm_noperands (PATTERN (insn)) > 0
1031 && REGNO (op) == ORIGINAL_REGNO (op)))
1033 if (prev_open != open_chains)
1034 open_chains->cannot_rename = 1;
1039 /* Build def/use chain. */
1041 static struct du_head *
1042 build_def_use (basic_block bb)
1046 unsigned HOST_WIDE_INT untracked_operands;
1048 open_chains = closed_chains = NULL;
1050 fail_current_block = false;
1053 bitmap_initialize (&open_chains_set, &bitmap_default_obstack);
1054 CLEAR_HARD_REG_SET (live_in_chains);
1055 REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb));
1056 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1058 df_ref def = *def_rec;
1059 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
1060 SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def));
1063 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
1065 if (NONDEBUG_INSN_P (insn))
1069 rtx old_operands[MAX_RECOG_OPERANDS];
1070 rtx old_dups[MAX_DUP_OPERANDS];
1074 enum rtx_code set_code = SET;
1075 enum rtx_code clobber_code = CLOBBER;
1077 /* Process the insn, determining its effect on the def-use
1078 chains and live hard registers. We perform the following
1079 steps with the register references in the insn, simulating
1081 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1082 by creating chains and marking hard regs live.
1083 (2) Any read outside an operand causes any chain it overlaps
1084 with to be marked unrenamable.
1085 (3) Any read inside an operand is added if there's already
1086 an open chain for it.
1087 (4) For any REG_DEAD note we find, close open chains that
1089 (5) For any non-earlyclobber write we find, close open chains
1091 (6) For any non-earlyclobber write we find in an operand, make
1092 a new chain or mark the hard register as live.
1093 (7) For any REG_UNUSED, close any chains we just opened.
1095 We cannot deal with situations where we track a reg in one mode
1096 and see a reference in another mode; these will cause the chain
1097 to be marked unrenamable or even cause us to abort the entire
1100 extract_insn (insn);
1101 if (! constrain_operands (1))
1102 fatal_insn_not_found (insn);
1103 preprocess_constraints ();
1104 alt = which_alternative;
1105 n_ops = recog_data.n_operands;
1106 untracked_operands = 0;
1108 /* Simplify the code below by rewriting things to reflect
1109 matching constraints. Also promote OP_OUT to OP_INOUT in
1110 predicated instructions, but only for register operands
1111 that are already tracked, so that we can create a chain
1112 when the first SET makes a register live. */
1114 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1115 for (i = 0; i < n_ops; ++i)
1117 int matches = recog_op_alt[i][alt].matches;
1119 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
1120 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
1121 || (predicated && recog_data.operand_type[i] == OP_OUT
1122 && verify_reg_tracked (recog_data.operand[i])))
1124 rtx op = recog_data.operand[i];
1125 recog_data.operand_type[i] = OP_INOUT;
1126 /* A special case to deal with instruction patterns that
1127 have matching operands with different modes. If we're
1128 not already tracking such a reg, we won't start here,
1129 and we must instead make sure to make the operand visible
1130 to the machinery that tracks hard registers. */
1132 && (GET_MODE_SIZE (recog_data.operand_mode[i])
1133 != GET_MODE_SIZE (recog_data.operand_mode[matches]))
1134 && !verify_reg_in_set (op, &live_in_chains))
1136 untracked_operands |= 1 << i;
1137 untracked_operands |= 1 << matches;
1142 if (fail_current_block)
1145 /* Step 1a: Mark hard registers that are clobbered in this insn,
1146 outside an operand, as live. */
1147 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1149 note_stores (PATTERN (insn), note_sets_clobbers, &clobber_code);
1150 restore_operands (insn, n_ops, old_operands, old_dups);
1152 /* Step 1b: Begin new chains for earlyclobbered writes inside
1154 record_out_operands (insn, true);
1156 /* Step 2: Mark chains for which we have reads outside operands
1158 We do this by munging all operands into CC0, and closing
1159 everything remaining. */
1161 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1163 scan_rtx (insn, &PATTERN (insn), NO_REGS, mark_all_read, OP_IN);
1164 restore_operands (insn, n_ops, old_operands, old_dups);
1166 /* Step 2B: Can't rename function call argument registers. */
1167 if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
1168 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
1169 NO_REGS, mark_all_read, OP_IN);
1171 /* Step 2C: Can't rename asm operands that were originally
1173 if (asm_noperands (PATTERN (insn)) > 0)
1174 for (i = 0; i < n_ops; i++)
1176 rtx *loc = recog_data.operand_loc[i];
1180 && REGNO (op) == ORIGINAL_REGNO (op)
1181 && (recog_data.operand_type[i] == OP_IN
1182 || recog_data.operand_type[i] == OP_INOUT))
1183 scan_rtx (insn, loc, NO_REGS, mark_all_read, OP_IN);
1186 /* Step 3: Append to chains for reads inside operands. */
1187 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1189 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1190 rtx *loc = (i < n_ops
1191 ? recog_data.operand_loc[opn]
1192 : recog_data.dup_loc[i - n_ops]);
1193 enum reg_class cl = recog_op_alt[opn][alt].cl;
1194 enum op_type type = recog_data.operand_type[opn];
1196 /* Don't scan match_operand here, since we've no reg class
1197 information to pass down. Any operands that we could
1198 substitute in will be represented elsewhere. */
1199 if (recog_data.constraints[opn][0] == '\0'
1200 || untracked_operands & (1 << opn))
1203 if (recog_op_alt[opn][alt].is_address)
1204 scan_rtx_address (insn, loc, cl, mark_read, VOIDmode);
1206 scan_rtx (insn, loc, cl, mark_read, type);
1209 /* Step 3B: Record updates for regs in REG_INC notes, and
1210 source regs in REG_FRAME_RELATED_EXPR notes. */
1211 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1212 if (REG_NOTE_KIND (note) == REG_INC
1213 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1214 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
1217 /* Step 4: Close chains for registers that die here. */
1218 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1219 if (REG_NOTE_KIND (note) == REG_DEAD)
1221 remove_from_hard_reg_set (&live_hard_regs,
1222 GET_MODE (XEXP (note, 0)),
1223 REGNO (XEXP (note, 0)));
1224 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1228 /* Step 4B: If this is a call, any chain live at this point
1229 requires a caller-saved reg. */
1233 for (p = open_chains; p; p = p->next_chain)
1234 p->need_caller_save_reg = 1;
1237 /* Step 5: Close open chains that overlap writes. Similar to
1238 step 2, we hide in-out operands, since we do not want to
1239 close these chains. We also hide earlyclobber operands,
1240 since we've opened chains for them in step 1, and earlier
1241 chains they would overlap with must have been closed at
1242 the previous insn at the latest, as such operands cannot
1243 possibly overlap with any input operands. */
1245 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1247 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN);
1248 restore_operands (insn, n_ops, old_operands, old_dups);
1250 /* Step 6a: Mark hard registers that are set in this insn,
1251 outside an operand, as live. */
1252 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1254 note_stores (PATTERN (insn), note_sets_clobbers, &set_code);
1255 restore_operands (insn, n_ops, old_operands, old_dups);
1257 /* Step 6b: Begin new chains for writes inside operands. */
1258 record_out_operands (insn, false);
1260 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1261 notes for update. */
1262 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1263 if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1264 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
1267 /* Step 7: Close chains for registers that were never
1268 really used here. */
1269 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1270 if (REG_NOTE_KIND (note) == REG_UNUSED)
1272 remove_from_hard_reg_set (&live_hard_regs,
1273 GET_MODE (XEXP (note, 0)),
1274 REGNO (XEXP (note, 0)));
1275 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1279 else if (DEBUG_INSN_P (insn)
1280 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)))
1282 scan_rtx (insn, &INSN_VAR_LOCATION_LOC (insn),
1283 ALL_REGS, mark_read, OP_IN);
1285 if (insn == BB_END (bb))
1289 bitmap_clear (&open_chains_set);
1291 if (fail_current_block)
1294 /* Since we close every chain when we find a REG_DEAD note, anything that
1295 is still open lives past the basic block, so it can't be renamed. */
1296 return closed_chains;
1299 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
1300 printed in reverse order as that's how we build them. */
1303 dump_def_use_chain (struct du_head *head)
1307 struct du_chain *this_du = head->first;
1308 fprintf (dump_file, "Register %s (%d):",
1309 reg_names[head->regno], head->nregs);
1312 fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
1313 reg_class_names[this_du->cl]);
1314 this_du = this_du->next_use;
1316 fprintf (dump_file, "\n");
1317 head = head->next_chain;
1323 gate_handle_regrename (void)
1325 return (optimize > 0 && (flag_rename_registers));
1328 struct rtl_opt_pass pass_regrename =
1333 gate_handle_regrename, /* gate */
1334 regrename_optimize, /* execute */
1337 0, /* static_pass_number */
1338 TV_RENAME_REGISTERS, /* tv_id */
1339 0, /* properties_required */
1340 0, /* properties_provided */
1341 0, /* properties_destroyed */
1342 0, /* todo_flags_start */
1343 TODO_df_finish | TODO_verify_rtl_sharing |
1344 TODO_dump_func /* todo_flags_finish */