1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005
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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
28 #include "insn-config.h"
30 #include "addresses.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
41 #include "tree-pass.h"
45 struct du_chain *next_chain;
46 struct du_chain *next_use;
50 ENUM_BITFIELD(reg_class) cl : 16;
51 unsigned int need_caller_save_reg:1;
52 unsigned int earlyclobber:1;
58 terminate_overlapping_read,
63 /* mark_access is for marking the destination regs in
64 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
65 note is updated properly. */
69 static const char * const scan_actions_name[] =
72 "terminate_overlapping_read",
80 static struct obstack rename_obstack;
82 static void do_replace (struct du_chain *, int);
83 static void scan_rtx_reg (rtx, rtx *, enum reg_class,
84 enum scan_actions, enum op_type, int);
85 static void scan_rtx_address (rtx, rtx *, enum reg_class,
86 enum scan_actions, enum machine_mode);
87 static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
89 static struct du_chain *build_def_use (basic_block);
90 static void dump_def_use_chain (struct du_chain *);
91 static void note_sets (rtx, rtx, void *);
92 static void clear_dead_regs (HARD_REG_SET *, enum machine_mode, rtx);
93 static void merge_overlapping_regs (basic_block, HARD_REG_SET *,
96 /* Called through note_stores from update_life. Find sets of registers, and
97 record them in *DATA (which is actually a HARD_REG_SET *). */
100 note_sets (rtx x, rtx set ATTRIBUTE_UNUSED, void *data)
102 HARD_REG_SET *pset = (HARD_REG_SET *) data;
104 if (GET_CODE (x) == SUBREG)
108 /* There must not be pseudos at this point. */
109 gcc_assert (HARD_REGISTER_P (x));
110 add_to_hard_reg_set (pset, GET_MODE (x), REGNO (x));
113 /* Clear all registers from *PSET for which a note of kind KIND can be found
114 in the list NOTES. */
117 clear_dead_regs (HARD_REG_SET *pset, enum machine_mode kind, rtx notes)
120 for (note = notes; note; note = XEXP (note, 1))
121 if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0)))
123 rtx reg = XEXP (note, 0);
124 /* There must not be pseudos at this point. */
125 gcc_assert (HARD_REGISTER_P (reg));
126 remove_from_hard_reg_set (pset, GET_MODE (reg), REGNO (reg));
130 /* For a def-use chain CHAIN in basic block B, find which registers overlap
131 its lifetime and set the corresponding bits in *PSET. */
134 merge_overlapping_regs (basic_block b, HARD_REG_SET *pset,
135 struct du_chain *chain)
137 struct du_chain *t = chain;
141 REG_SET_TO_HARD_REG_SET (live, b->il.rtl->global_live_at_start);
145 /* Search forward until the next reference to the register to be
147 while (insn != t->insn)
151 clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn));
152 note_stores (PATTERN (insn), note_sets, (void *) &live);
153 /* Only record currently live regs if we are inside the
156 IOR_HARD_REG_SET (*pset, live);
157 clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn));
159 insn = NEXT_INSN (insn);
162 IOR_HARD_REG_SET (*pset, live);
164 /* For the last reference, also merge in all registers set in the
166 @@@ We only have take earlyclobbered sets into account. */
168 note_stores (PATTERN (insn), note_sets, (void *) pset);
174 /* Perform register renaming on the current function. */
177 regrename_optimize (void)
179 int tick[FIRST_PSEUDO_REGISTER];
184 memset (tick, 0, sizeof tick);
186 gcc_obstack_init (&rename_obstack);
187 first_obj = obstack_alloc (&rename_obstack, 0);
191 struct du_chain *all_chains = 0;
192 HARD_REG_SET unavailable;
193 HARD_REG_SET regs_seen;
195 CLEAR_HARD_REG_SET (unavailable);
198 fprintf (dump_file, "\nBasic block %d:\n", bb->index);
200 all_chains = build_def_use (bb);
203 dump_def_use_chain (all_chains);
205 CLEAR_HARD_REG_SET (unavailable);
206 /* Don't clobber traceback for noreturn functions. */
207 if (frame_pointer_needed)
209 add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
210 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
211 add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
215 CLEAR_HARD_REG_SET (regs_seen);
218 int new_reg, best_new_reg;
220 struct du_chain *this = all_chains;
221 struct du_chain *tmp, *last;
222 HARD_REG_SET this_unavailable;
223 int reg = REGNO (*this->loc);
226 all_chains = this->next_chain;
230 #if 0 /* This just disables optimization opportunities. */
231 /* Only rename once we've seen the reg more than once. */
232 if (! TEST_HARD_REG_BIT (regs_seen, reg))
234 SET_HARD_REG_BIT (regs_seen, reg);
239 if (fixed_regs[reg] || global_regs[reg]
240 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
241 || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
243 || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
248 COPY_HARD_REG_SET (this_unavailable, unavailable);
250 /* Find last entry on chain (which has the need_caller_save bit),
251 count number of uses, and narrow the set of registers we can
254 for (last = this; last->next_use; last = last->next_use)
257 IOR_COMPL_HARD_REG_SET (this_unavailable,
258 reg_class_contents[last->cl]);
263 IOR_COMPL_HARD_REG_SET (this_unavailable,
264 reg_class_contents[last->cl]);
266 if (this->need_caller_save_reg)
267 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
269 merge_overlapping_regs (bb, &this_unavailable, this);
271 /* Now potential_regs is a reasonable approximation, let's
272 have a closer look at each register still in there. */
273 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
275 int nregs = hard_regno_nregs[new_reg][GET_MODE (*this->loc)];
277 for (i = nregs - 1; i >= 0; --i)
278 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
279 || fixed_regs[new_reg + i]
280 || global_regs[new_reg + i]
281 /* Can't use regs which aren't saved by the prologue. */
282 || (! regs_ever_live[new_reg + i]
283 && ! call_used_regs[new_reg + i])
284 #ifdef LEAF_REGISTERS
285 /* We can't use a non-leaf register if we're in a
287 || (current_function_is_leaf
288 && !LEAF_REGISTERS[new_reg + i])
290 #ifdef HARD_REGNO_RENAME_OK
291 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
298 /* See whether it accepts all modes that occur in
299 definition and uses. */
300 for (tmp = this; tmp; tmp = tmp->next_use)
301 if (! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
302 || (tmp->need_caller_save_reg
303 && ! (HARD_REGNO_CALL_PART_CLOBBERED
304 (reg, GET_MODE (*tmp->loc)))
305 && (HARD_REGNO_CALL_PART_CLOBBERED
306 (new_reg, GET_MODE (*tmp->loc)))))
310 if (tick[best_new_reg] > tick[new_reg])
311 best_new_reg = new_reg;
317 fprintf (dump_file, "Register %s in insn %d",
318 reg_names[reg], INSN_UID (last->insn));
319 if (last->need_caller_save_reg)
320 fprintf (dump_file, " crosses a call");
323 if (best_new_reg == reg)
325 tick[reg] = ++this_tick;
327 fprintf (dump_file, "; no available better choice\n");
331 do_replace (this, best_new_reg);
332 tick[best_new_reg] = ++this_tick;
333 regs_ever_live[best_new_reg] = 1;
336 fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
339 obstack_free (&rename_obstack, first_obj);
342 obstack_free (&rename_obstack, NULL);
345 fputc ('\n', dump_file);
347 count_or_remove_death_notes (NULL, 1);
348 update_life_info (NULL, UPDATE_LIFE_LOCAL,
353 do_replace (struct du_chain *chain, int reg)
357 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
358 struct reg_attrs * attr = REG_ATTRS (*chain->loc);
360 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
361 if (regno >= FIRST_PSEUDO_REGISTER)
362 ORIGINAL_REGNO (*chain->loc) = regno;
363 REG_ATTRS (*chain->loc) = attr;
364 chain = chain->next_use;
369 static struct du_chain *open_chains;
370 static struct du_chain *closed_chains;
373 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl,
374 enum scan_actions action, enum op_type type, int earlyclobber)
378 enum machine_mode mode = GET_MODE (x);
379 int this_regno = REGNO (x);
380 int this_nregs = hard_regno_nregs[this_regno][mode];
382 if (action == mark_write)
386 struct du_chain *this
387 = obstack_alloc (&rename_obstack, sizeof (struct du_chain));
389 this->next_chain = open_chains;
393 this->need_caller_save_reg = 0;
394 this->earlyclobber = earlyclobber;
400 if ((type == OP_OUT) != (action == terminate_write || action == mark_access))
403 for (p = &open_chains; *p;)
405 struct du_chain *this = *p;
407 /* Check if the chain has been terminated if it has then skip to
410 This can happen when we've already appended the location to
411 the chain in Step 3, but are trying to hide in-out operands
412 from terminate_write in Step 5. */
414 if (*this->loc == cc0_rtx)
415 p = &this->next_chain;
418 int regno = REGNO (*this->loc);
419 int nregs = hard_regno_nregs[regno][GET_MODE (*this->loc)];
420 int exact_match = (regno == this_regno && nregs == this_nregs);
422 if (regno + nregs <= this_regno
423 || this_regno + this_nregs <= regno)
425 p = &this->next_chain;
429 if (action == mark_read || action == mark_access)
431 gcc_assert (exact_match);
433 /* ??? Class NO_REGS can happen if the md file makes use of
434 EXTRA_CONSTRAINTS to match registers. Which is arguably
435 wrong, but there we are. Since we know not what this may
436 be replaced with, terminate the chain. */
439 this = obstack_alloc (&rename_obstack, sizeof (struct du_chain));
441 this->next_chain = (*p)->next_chain;
445 this->need_caller_save_reg = 0;
453 if (action != terminate_overlapping_read || ! exact_match)
455 struct du_chain *next = this->next_chain;
457 /* Whether the terminated chain can be used for renaming
458 depends on the action and this being an exact match.
459 In either case, we remove this element from open_chains. */
461 if ((action == terminate_dead || action == terminate_write)
464 this->next_chain = closed_chains;
465 closed_chains = this;
468 "Closing chain %s at insn %d (%s)\n",
469 reg_names[REGNO (*this->loc)], INSN_UID (insn),
470 scan_actions_name[(int) action]);
476 "Discarding chain %s at insn %d (%s)\n",
477 reg_names[REGNO (*this->loc)], INSN_UID (insn),
478 scan_actions_name[(int) action]);
483 p = &this->next_chain;
488 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
489 BASE_REG_CLASS depending on how the register is being considered. */
492 scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl,
493 enum scan_actions action, enum machine_mode mode)
496 RTX_CODE code = GET_CODE (x);
500 if (action == mark_write || action == mark_access)
507 rtx orig_op0 = XEXP (x, 0);
508 rtx orig_op1 = XEXP (x, 1);
509 RTX_CODE code0 = GET_CODE (orig_op0);
510 RTX_CODE code1 = GET_CODE (orig_op1);
515 enum rtx_code index_code = SCRATCH;
517 if (GET_CODE (op0) == SUBREG)
519 op0 = SUBREG_REG (op0);
520 code0 = GET_CODE (op0);
523 if (GET_CODE (op1) == SUBREG)
525 op1 = SUBREG_REG (op1);
526 code1 = GET_CODE (op1);
529 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
530 || code0 == ZERO_EXTEND || code1 == MEM)
534 index_code = GET_CODE (*locI);
536 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
537 || code1 == ZERO_EXTEND || code0 == MEM)
541 index_code = GET_CODE (*locI);
543 else if (code0 == CONST_INT || code0 == CONST
544 || code0 == SYMBOL_REF || code0 == LABEL_REF)
547 index_code = GET_CODE (XEXP (x, 0));
549 else if (code1 == CONST_INT || code1 == CONST
550 || code1 == SYMBOL_REF || code1 == LABEL_REF)
553 index_code = GET_CODE (XEXP (x, 1));
555 else if (code0 == REG && code1 == REG)
558 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
560 if (REGNO_OK_FOR_INDEX_P (regno0)
561 && regno_ok_for_base_p (regno1, mode, PLUS, REG))
563 else if (REGNO_OK_FOR_INDEX_P (regno1)
564 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
566 else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
568 else if (regno_ok_for_base_p (regno0, mode, PLUS, REG))
570 else if (REGNO_OK_FOR_INDEX_P (regno1))
575 locI = &XEXP (x, index_op);
576 locB = &XEXP (x, !index_op);
577 index_code = GET_CODE (*locI);
579 else if (code0 == REG)
583 index_code = GET_CODE (*locI);
585 else if (code1 == REG)
589 index_code = GET_CODE (*locI);
593 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
595 scan_rtx_address (insn, locB, base_reg_class (mode, PLUS, index_code),
608 /* If the target doesn't claim to handle autoinc, this must be
609 something special, like a stack push. Kill this chain. */
610 action = terminate_all_read;
615 scan_rtx_address (insn, &XEXP (x, 0),
616 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
621 scan_rtx_reg (insn, loc, cl, action, OP_IN, 0);
628 fmt = GET_RTX_FORMAT (code);
629 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
632 scan_rtx_address (insn, &XEXP (x, i), cl, action, mode);
633 else if (fmt[i] == 'E')
634 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
635 scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode);
640 scan_rtx (rtx insn, rtx *loc, enum reg_class cl,
641 enum scan_actions action, enum op_type type, int earlyclobber)
645 enum rtx_code code = GET_CODE (x);
662 scan_rtx_reg (insn, loc, cl, action, type, earlyclobber);
666 scan_rtx_address (insn, &XEXP (x, 0),
667 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
672 scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN, 0);
673 scan_rtx (insn, &SET_DEST (x), cl, action,
674 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0);
677 case STRICT_LOW_PART:
678 scan_rtx (insn, &XEXP (x, 0), cl, action, OP_INOUT, earlyclobber);
683 scan_rtx (insn, &XEXP (x, 0), cl, action,
684 type == OP_IN ? OP_IN : OP_INOUT, earlyclobber);
685 scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN, 0);
686 scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN, 0);
695 /* Should only happen inside MEM. */
699 scan_rtx (insn, &SET_DEST (x), cl, action,
700 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0);
704 scan_rtx (insn, &XEXP (x, 0), cl, action, type, 0);
706 scan_rtx (insn, &XEXP (x, 1), cl, action, type, 0);
713 fmt = GET_RTX_FORMAT (code);
714 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
717 scan_rtx (insn, &XEXP (x, i), cl, action, type, 0);
718 else if (fmt[i] == 'E')
719 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
720 scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type, 0);
724 /* Build def/use chain. */
726 static struct du_chain *
727 build_def_use (basic_block bb)
731 open_chains = closed_chains = NULL;
733 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
739 rtx old_operands[MAX_RECOG_OPERANDS];
740 rtx old_dups[MAX_DUP_OPERANDS];
745 /* Process the insn, determining its effect on the def-use
746 chains. We perform the following steps with the register
747 references in the insn:
748 (1) Any read that overlaps an open chain, but doesn't exactly
749 match, causes that chain to be closed. We can't deal
751 (2) Any read outside an operand causes any chain it overlaps
752 with to be closed, since we can't replace it.
753 (3) Any read inside an operand is added if there's already
754 an open chain for it.
755 (4) For any REG_DEAD note we find, close open chains that
757 (5) For any write we find, close open chains that overlap it.
758 (6) For any write we find in an operand, make a new chain.
759 (7) For any REG_UNUSED, close any chains we just opened. */
761 icode = recog_memoized (insn);
763 if (! constrain_operands (1))
764 fatal_insn_not_found (insn);
765 preprocess_constraints ();
766 alt = which_alternative;
767 n_ops = recog_data.n_operands;
769 /* Simplify the code below by rewriting things to reflect
770 matching constraints. Also promote OP_OUT to OP_INOUT
771 in predicated instructions. */
773 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
774 for (i = 0; i < n_ops; ++i)
776 int matches = recog_op_alt[i][alt].matches;
778 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
779 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
780 || (predicated && recog_data.operand_type[i] == OP_OUT))
781 recog_data.operand_type[i] = OP_INOUT;
784 /* Step 1: Close chains for which we have overlapping reads. */
785 for (i = 0; i < n_ops; i++)
786 scan_rtx (insn, recog_data.operand_loc[i],
787 NO_REGS, terminate_overlapping_read,
788 recog_data.operand_type[i], 0);
790 /* Step 2: Close chains for which we have reads outside operands.
791 We do this by munging all operands into CC0, and closing
792 everything remaining. */
794 for (i = 0; i < n_ops; i++)
796 old_operands[i] = recog_data.operand[i];
797 /* Don't squash match_operator or match_parallel here, since
798 we don't know that all of the contained registers are
799 reachable by proper operands. */
800 if (recog_data.constraints[i][0] == '\0')
802 *recog_data.operand_loc[i] = cc0_rtx;
804 for (i = 0; i < recog_data.n_dups; i++)
806 int dup_num = recog_data.dup_num[i];
808 old_dups[i] = *recog_data.dup_loc[i];
809 *recog_data.dup_loc[i] = cc0_rtx;
811 /* For match_dup of match_operator or match_parallel, share
812 them, so that we don't miss changes in the dup. */
814 && insn_data[icode].operand[dup_num].eliminable == 0)
815 old_dups[i] = recog_data.operand[dup_num];
818 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read,
821 for (i = 0; i < recog_data.n_dups; i++)
822 *recog_data.dup_loc[i] = old_dups[i];
823 for (i = 0; i < n_ops; i++)
824 *recog_data.operand_loc[i] = old_operands[i];
826 /* Step 2B: Can't rename function call argument registers. */
827 if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
828 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
829 NO_REGS, terminate_all_read, OP_IN, 0);
831 /* Step 2C: Can't rename asm operands that were originally
833 if (asm_noperands (PATTERN (insn)) > 0)
834 for (i = 0; i < n_ops; i++)
836 rtx *loc = recog_data.operand_loc[i];
840 && REGNO (op) == ORIGINAL_REGNO (op)
841 && (recog_data.operand_type[i] == OP_IN
842 || recog_data.operand_type[i] == OP_INOUT))
843 scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0);
846 /* Step 3: Append to chains for reads inside operands. */
847 for (i = 0; i < n_ops + recog_data.n_dups; i++)
849 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
850 rtx *loc = (i < n_ops
851 ? recog_data.operand_loc[opn]
852 : recog_data.dup_loc[i - n_ops]);
853 enum reg_class cl = recog_op_alt[opn][alt].cl;
854 enum op_type type = recog_data.operand_type[opn];
856 /* Don't scan match_operand here, since we've no reg class
857 information to pass down. Any operands that we could
858 substitute in will be represented elsewhere. */
859 if (recog_data.constraints[opn][0] == '\0')
862 if (recog_op_alt[opn][alt].is_address)
863 scan_rtx_address (insn, loc, cl, mark_read, VOIDmode);
865 scan_rtx (insn, loc, cl, mark_read, type, 0);
868 /* Step 3B: Record updates for regs in REG_INC notes, and
869 source regs in REG_FRAME_RELATED_EXPR notes. */
870 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
871 if (REG_NOTE_KIND (note) == REG_INC
872 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
873 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
876 /* Step 4: Close chains for registers that die here. */
877 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
878 if (REG_NOTE_KIND (note) == REG_DEAD)
879 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
882 /* Step 4B: If this is a call, any chain live at this point
883 requires a caller-saved reg. */
887 for (p = open_chains; p; p = p->next_chain)
888 p->need_caller_save_reg = 1;
891 /* Step 5: Close open chains that overlap writes. Similar to
892 step 2, we hide in-out operands, since we do not want to
893 close these chains. */
895 for (i = 0; i < n_ops; i++)
897 old_operands[i] = recog_data.operand[i];
898 if (recog_data.operand_type[i] == OP_INOUT)
899 *recog_data.operand_loc[i] = cc0_rtx;
901 for (i = 0; i < recog_data.n_dups; i++)
903 int opn = recog_data.dup_num[i];
904 old_dups[i] = *recog_data.dup_loc[i];
905 if (recog_data.operand_type[opn] == OP_INOUT)
906 *recog_data.dup_loc[i] = cc0_rtx;
909 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0);
911 for (i = 0; i < recog_data.n_dups; i++)
912 *recog_data.dup_loc[i] = old_dups[i];
913 for (i = 0; i < n_ops; i++)
914 *recog_data.operand_loc[i] = old_operands[i];
916 /* Step 6: Begin new chains for writes inside operands. */
917 /* ??? Many targets have output constraints on the SET_DEST
918 of a call insn, which is stupid, since these are certainly
919 ABI defined hard registers. Don't change calls at all.
920 Similarly take special care for asm statement that originally
921 referenced hard registers. */
922 if (asm_noperands (PATTERN (insn)) > 0)
924 for (i = 0; i < n_ops; i++)
925 if (recog_data.operand_type[i] == OP_OUT)
927 rtx *loc = recog_data.operand_loc[i];
929 enum reg_class cl = recog_op_alt[i][alt].cl;
932 && REGNO (op) == ORIGINAL_REGNO (op))
935 scan_rtx (insn, loc, cl, mark_write, OP_OUT,
936 recog_op_alt[i][alt].earlyclobber);
939 else if (!CALL_P (insn))
940 for (i = 0; i < n_ops + recog_data.n_dups; i++)
942 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
943 rtx *loc = (i < n_ops
944 ? recog_data.operand_loc[opn]
945 : recog_data.dup_loc[i - n_ops]);
946 enum reg_class cl = recog_op_alt[opn][alt].cl;
948 if (recog_data.operand_type[opn] == OP_OUT)
949 scan_rtx (insn, loc, cl, mark_write, OP_OUT,
950 recog_op_alt[opn][alt].earlyclobber);
953 /* Step 6B: Record destination regs in REG_FRAME_RELATED_EXPR
955 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
956 if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
957 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
960 /* Step 7: Close chains for registers that were never
962 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
963 if (REG_NOTE_KIND (note) == REG_UNUSED)
964 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
967 if (insn == BB_END (bb))
971 /* Since we close every chain when we find a REG_DEAD note, anything that
972 is still open lives past the basic block, so it can't be renamed. */
973 return closed_chains;
976 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
977 printed in reverse order as that's how we build them. */
980 dump_def_use_chain (struct du_chain *chains)
984 struct du_chain *this = chains;
985 int r = REGNO (*this->loc);
986 int nregs = hard_regno_nregs[r][GET_MODE (*this->loc)];
987 fprintf (dump_file, "Register %s (%d):", reg_names[r], nregs);
990 fprintf (dump_file, " %d [%s]", INSN_UID (this->insn),
991 reg_class_names[this->cl]);
992 this = this->next_use;
994 fprintf (dump_file, "\n");
995 chains = chains->next_chain;
999 /* The following code does forward propagation of hard register copies.
1000 The object is to eliminate as many dependencies as possible, so that
1001 we have the most scheduling freedom. As a side effect, we also clean
1002 up some silly register allocation decisions made by reload. This
1003 code may be obsoleted by a new register allocator. */
1005 /* For each register, we have a list of registers that contain the same
1006 value. The OLDEST_REGNO field points to the head of the list, and
1007 the NEXT_REGNO field runs through the list. The MODE field indicates
1008 what mode the data is known to be in; this field is VOIDmode when the
1009 register is not known to contain valid data. */
1011 struct value_data_entry
1013 enum machine_mode mode;
1014 unsigned int oldest_regno;
1015 unsigned int next_regno;
1020 struct value_data_entry e[FIRST_PSEUDO_REGISTER];
1021 unsigned int max_value_regs;
1024 static void kill_value_one_regno (unsigned, struct value_data *);
1025 static void kill_value_regno (unsigned, unsigned, struct value_data *);
1026 static void kill_value (rtx, struct value_data *);
1027 static void set_value_regno (unsigned, enum machine_mode, struct value_data *);
1028 static void init_value_data (struct value_data *);
1029 static void kill_clobbered_value (rtx, rtx, void *);
1030 static void kill_set_value (rtx, rtx, void *);
1031 static int kill_autoinc_value (rtx *, void *);
1032 static void copy_value (rtx, rtx, struct value_data *);
1033 static bool mode_change_ok (enum machine_mode, enum machine_mode,
1035 static rtx maybe_mode_change (enum machine_mode, enum machine_mode,
1036 enum machine_mode, unsigned int, unsigned int);
1037 static rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *);
1038 static bool replace_oldest_value_reg (rtx *, enum reg_class, rtx,
1039 struct value_data *);
1040 static bool replace_oldest_value_addr (rtx *, enum reg_class,
1041 enum machine_mode, rtx,
1042 struct value_data *);
1043 static bool replace_oldest_value_mem (rtx, rtx, struct value_data *);
1044 static bool copyprop_hardreg_forward_1 (basic_block, struct value_data *);
1045 extern void debug_value_data (struct value_data *);
1046 #ifdef ENABLE_CHECKING
1047 static void validate_value_data (struct value_data *);
1050 /* Kill register REGNO. This involves removing it from any value
1051 lists, and resetting the value mode to VOIDmode. This is only a
1052 helper function; it does not handle any hard registers overlapping
1056 kill_value_one_regno (unsigned int regno, struct value_data *vd)
1058 unsigned int i, next;
1060 if (vd->e[regno].oldest_regno != regno)
1062 for (i = vd->e[regno].oldest_regno;
1063 vd->e[i].next_regno != regno;
1064 i = vd->e[i].next_regno)
1066 vd->e[i].next_regno = vd->e[regno].next_regno;
1068 else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM)
1070 for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno)
1071 vd->e[i].oldest_regno = next;
1074 vd->e[regno].mode = VOIDmode;
1075 vd->e[regno].oldest_regno = regno;
1076 vd->e[regno].next_regno = INVALID_REGNUM;
1078 #ifdef ENABLE_CHECKING
1079 validate_value_data (vd);
1083 /* Kill the value in register REGNO for NREGS, and any other registers
1084 whose values overlap. */
1087 kill_value_regno (unsigned int regno, unsigned int nregs,
1088 struct value_data *vd)
1092 /* Kill the value we're told to kill. */
1093 for (j = 0; j < nregs; ++j)
1094 kill_value_one_regno (regno + j, vd);
1096 /* Kill everything that overlapped what we're told to kill. */
1097 if (regno < vd->max_value_regs)
1100 j = regno - vd->max_value_regs;
1101 for (; j < regno; ++j)
1104 if (vd->e[j].mode == VOIDmode)
1106 n = hard_regno_nregs[j][vd->e[j].mode];
1108 for (i = 0; i < n; ++i)
1109 kill_value_one_regno (j + i, vd);
1113 /* Kill X. This is a convenience function wrapping kill_value_regno
1114 so that we mind the mode the register is in. */
1117 kill_value (rtx x, struct value_data *vd)
1121 if (GET_CODE (x) == SUBREG)
1123 x = simplify_subreg (GET_MODE (x), SUBREG_REG (x),
1124 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x));
1126 x = SUBREG_REG (orig_rtx);
1130 unsigned int regno = REGNO (x);
1131 unsigned int n = hard_regno_nregs[regno][GET_MODE (x)];
1133 kill_value_regno (regno, n, vd);
1137 /* Remember that REGNO is valid in MODE. */
1140 set_value_regno (unsigned int regno, enum machine_mode mode,
1141 struct value_data *vd)
1145 vd->e[regno].mode = mode;
1147 nregs = hard_regno_nregs[regno][mode];
1148 if (nregs > vd->max_value_regs)
1149 vd->max_value_regs = nregs;
1152 /* Initialize VD such that there are no known relationships between regs. */
1155 init_value_data (struct value_data *vd)
1158 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1160 vd->e[i].mode = VOIDmode;
1161 vd->e[i].oldest_regno = i;
1162 vd->e[i].next_regno = INVALID_REGNUM;
1164 vd->max_value_regs = 0;
1167 /* Called through note_stores. If X is clobbered, kill its value. */
1170 kill_clobbered_value (rtx x, rtx set, void *data)
1172 struct value_data *vd = data;
1173 if (GET_CODE (set) == CLOBBER)
1177 /* Called through note_stores. If X is set, not clobbered, kill its
1178 current value and install it as the root of its own value list. */
1181 kill_set_value (rtx x, rtx set, void *data)
1183 struct value_data *vd = data;
1184 if (GET_CODE (set) != CLOBBER)
1188 set_value_regno (REGNO (x), GET_MODE (x), vd);
1192 /* Called through for_each_rtx. Kill any register used as the base of an
1193 auto-increment expression, and install that register as the root of its
1197 kill_autoinc_value (rtx *px, void *data)
1200 struct value_data *vd = data;
1202 if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
1206 set_value_regno (REGNO (x), Pmode, vd);
1213 /* Assert that SRC has been copied to DEST. Adjust the data structures
1214 to reflect that SRC contains an older copy of the shared value. */
1217 copy_value (rtx dest, rtx src, struct value_data *vd)
1219 unsigned int dr = REGNO (dest);
1220 unsigned int sr = REGNO (src);
1221 unsigned int dn, sn;
1224 /* ??? At present, it's possible to see noop sets. It'd be nice if
1225 this were cleaned up beforehand... */
1229 /* Do not propagate copies to the stack pointer, as that can leave
1230 memory accesses with no scheduling dependency on the stack update. */
1231 if (dr == STACK_POINTER_REGNUM)
1234 /* Likewise with the frame pointer, if we're using one. */
1235 if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM)
1238 /* Do not propagate copies to fixed or global registers, patterns
1239 can be relying to see particular fixed register or users can
1240 expect the chosen global register in asm. */
1241 if (fixed_regs[dr] || global_regs[dr])
1244 /* If SRC and DEST overlap, don't record anything. */
1245 dn = hard_regno_nregs[dr][GET_MODE (dest)];
1246 sn = hard_regno_nregs[sr][GET_MODE (dest)];
1247 if ((dr > sr && dr < sr + sn)
1248 || (sr > dr && sr < dr + dn))
1251 /* If SRC had no assigned mode (i.e. we didn't know it was live)
1252 assign it now and assume the value came from an input argument
1254 if (vd->e[sr].mode == VOIDmode)
1255 set_value_regno (sr, vd->e[dr].mode, vd);
1257 /* If we are narrowing the input to a smaller number of hard regs,
1258 and it is in big endian, we are really extracting a high part.
1259 Since we generally associate a low part of a value with the value itself,
1260 we must not do the same for the high part.
1261 Note we can still get low parts for the same mode combination through
1262 a two-step copy involving differently sized hard regs.
1263 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each:
1264 (set (reg:DI r0) (reg:DI fr0))
1265 (set (reg:SI fr2) (reg:SI r0))
1266 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while:
1267 (set (reg:SI fr2) (reg:SI fr0))
1268 loads the high part of (reg:DI fr0) into fr2.
1270 We can't properly represent the latter case in our tables, so don't
1271 record anything then. */
1272 else if (sn < (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode]
1273 && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD
1274 ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN))
1277 /* If SRC had been assigned a mode narrower than the copy, we can't
1278 link DEST into the chain, because not all of the pieces of the
1279 copy came from oldest_regno. */
1280 else if (sn > (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode])
1283 /* Link DR at the end of the value chain used by SR. */
1285 vd->e[dr].oldest_regno = vd->e[sr].oldest_regno;
1287 for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno)
1289 vd->e[i].next_regno = dr;
1291 #ifdef ENABLE_CHECKING
1292 validate_value_data (vd);
1296 /* Return true if a mode change from ORIG to NEW is allowed for REGNO. */
1299 mode_change_ok (enum machine_mode orig_mode, enum machine_mode new_mode,
1300 unsigned int regno ATTRIBUTE_UNUSED)
1302 if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode))
1305 #ifdef CANNOT_CHANGE_MODE_CLASS
1306 return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode);
1312 /* Register REGNO was originally set in ORIG_MODE. It - or a copy of it -
1313 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed
1315 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */
1318 maybe_mode_change (enum machine_mode orig_mode, enum machine_mode copy_mode,
1319 enum machine_mode new_mode, unsigned int regno,
1320 unsigned int copy_regno ATTRIBUTE_UNUSED)
1322 if (orig_mode == new_mode)
1323 return gen_rtx_raw_REG (new_mode, regno);
1324 else if (mode_change_ok (orig_mode, new_mode, regno))
1326 int copy_nregs = hard_regno_nregs[copy_regno][copy_mode];
1327 int use_nregs = hard_regno_nregs[copy_regno][new_mode];
1329 = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs);
1331 = GET_MODE_SIZE (orig_mode) - GET_MODE_SIZE (new_mode) - copy_offset;
1332 int byteoffset = offset % UNITS_PER_WORD;
1333 int wordoffset = offset - byteoffset;
1335 offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0)
1336 + (BYTES_BIG_ENDIAN ? byteoffset : 0));
1337 return gen_rtx_raw_REG (new_mode,
1338 regno + subreg_regno_offset (regno, orig_mode,
1345 /* Find the oldest copy of the value contained in REGNO that is in
1346 register class CL and has mode MODE. If found, return an rtx
1347 of that oldest register, otherwise return NULL. */
1350 find_oldest_value_reg (enum reg_class cl, rtx reg, struct value_data *vd)
1352 unsigned int regno = REGNO (reg);
1353 enum machine_mode mode = GET_MODE (reg);
1356 /* If we are accessing REG in some mode other that what we set it in,
1357 make sure that the replacement is valid. In particular, consider
1358 (set (reg:DI r11) (...))
1359 (set (reg:SI r9) (reg:SI r11))
1360 (set (reg:SI r10) (...))
1361 (set (...) (reg:DI r9))
1362 Replacing r9 with r11 is invalid. */
1363 if (mode != vd->e[regno].mode)
1365 if (hard_regno_nregs[regno][mode]
1366 > hard_regno_nregs[regno][vd->e[regno].mode])
1370 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno)
1372 enum machine_mode oldmode = vd->e[i].mode;
1375 if (!in_hard_reg_set_p (reg_class_contents[cl], mode, i))
1378 new = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno);
1381 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg);
1382 REG_ATTRS (new) = REG_ATTRS (reg);
1390 /* If possible, replace the register at *LOC with the oldest register
1391 in register class CL. Return true if successfully replaced. */
1394 replace_oldest_value_reg (rtx *loc, enum reg_class cl, rtx insn,
1395 struct value_data *vd)
1397 rtx new = find_oldest_value_reg (cl, *loc, vd);
1401 fprintf (dump_file, "insn %u: replaced reg %u with %u\n",
1402 INSN_UID (insn), REGNO (*loc), REGNO (new));
1404 validate_change (insn, loc, new, 1);
1410 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1411 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
1412 BASE_REG_CLASS depending on how the register is being considered. */
1415 replace_oldest_value_addr (rtx *loc, enum reg_class cl,
1416 enum machine_mode mode, rtx insn,
1417 struct value_data *vd)
1420 RTX_CODE code = GET_CODE (x);
1423 bool changed = false;
1429 rtx orig_op0 = XEXP (x, 0);
1430 rtx orig_op1 = XEXP (x, 1);
1431 RTX_CODE code0 = GET_CODE (orig_op0);
1432 RTX_CODE code1 = GET_CODE (orig_op1);
1437 enum rtx_code index_code = SCRATCH;
1439 if (GET_CODE (op0) == SUBREG)
1441 op0 = SUBREG_REG (op0);
1442 code0 = GET_CODE (op0);
1445 if (GET_CODE (op1) == SUBREG)
1447 op1 = SUBREG_REG (op1);
1448 code1 = GET_CODE (op1);
1451 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
1452 || code0 == ZERO_EXTEND || code1 == MEM)
1454 locI = &XEXP (x, 0);
1455 locB = &XEXP (x, 1);
1456 index_code = GET_CODE (*locI);
1458 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
1459 || code1 == ZERO_EXTEND || code0 == MEM)
1461 locI = &XEXP (x, 1);
1462 locB = &XEXP (x, 0);
1463 index_code = GET_CODE (*locI);
1465 else if (code0 == CONST_INT || code0 == CONST
1466 || code0 == SYMBOL_REF || code0 == LABEL_REF)
1468 locB = &XEXP (x, 1);
1469 index_code = GET_CODE (XEXP (x, 0));
1471 else if (code1 == CONST_INT || code1 == CONST
1472 || code1 == SYMBOL_REF || code1 == LABEL_REF)
1474 locB = &XEXP (x, 0);
1475 index_code = GET_CODE (XEXP (x, 1));
1477 else if (code0 == REG && code1 == REG)
1480 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
1482 if (REGNO_OK_FOR_INDEX_P (regno0)
1483 && regno_ok_for_base_p (regno1, mode, PLUS, REG))
1485 else if (REGNO_OK_FOR_INDEX_P (regno1)
1486 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
1488 else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
1490 else if (regno_ok_for_base_p (regno0, mode, PLUS, REG))
1492 else if (REGNO_OK_FOR_INDEX_P (regno1))
1497 locI = &XEXP (x, index_op);
1498 locB = &XEXP (x, !index_op);
1499 index_code = GET_CODE (*locI);
1501 else if (code0 == REG)
1503 locI = &XEXP (x, 0);
1504 locB = &XEXP (x, 1);
1505 index_code = GET_CODE (*locI);
1507 else if (code1 == REG)
1509 locI = &XEXP (x, 1);
1510 locB = &XEXP (x, 0);
1511 index_code = GET_CODE (*locI);
1515 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode,
1518 changed |= replace_oldest_value_addr (locB,
1519 base_reg_class (mode, PLUS,
1534 return replace_oldest_value_mem (x, insn, vd);
1537 return replace_oldest_value_reg (loc, cl, insn, vd);
1543 fmt = GET_RTX_FORMAT (code);
1544 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1547 changed |= replace_oldest_value_addr (&XEXP (x, i), cl, mode,
1549 else if (fmt[i] == 'E')
1550 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1551 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), cl,
1558 /* Similar to replace_oldest_value_reg, but X contains a memory. */
1561 replace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd)
1563 return replace_oldest_value_addr (&XEXP (x, 0),
1564 base_reg_class (GET_MODE (x), MEM,
1566 GET_MODE (x), insn, vd);
1569 /* Perform the forward copy propagation on basic block BB. */
1572 copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd)
1574 bool changed = false;
1577 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
1579 int n_ops, i, alt, predicated;
1580 bool is_asm, any_replacements;
1582 bool replaced[MAX_RECOG_OPERANDS];
1584 if (! INSN_P (insn))
1586 if (insn == BB_END (bb))
1592 set = single_set (insn);
1593 extract_insn (insn);
1594 if (! constrain_operands (1))
1595 fatal_insn_not_found (insn);
1596 preprocess_constraints ();
1597 alt = which_alternative;
1598 n_ops = recog_data.n_operands;
1599 is_asm = asm_noperands (PATTERN (insn)) >= 0;
1601 /* Simplify the code below by rewriting things to reflect
1602 matching constraints. Also promote OP_OUT to OP_INOUT
1603 in predicated instructions. */
1605 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1606 for (i = 0; i < n_ops; ++i)
1608 int matches = recog_op_alt[i][alt].matches;
1610 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
1611 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
1612 || (predicated && recog_data.operand_type[i] == OP_OUT))
1613 recog_data.operand_type[i] = OP_INOUT;
1616 /* For each earlyclobber operand, zap the value data. */
1617 for (i = 0; i < n_ops; i++)
1618 if (recog_op_alt[i][alt].earlyclobber)
1619 kill_value (recog_data.operand[i], vd);
1621 /* Within asms, a clobber cannot overlap inputs or outputs.
1622 I wouldn't think this were true for regular insns, but
1623 scan_rtx treats them like that... */
1624 note_stores (PATTERN (insn), kill_clobbered_value, vd);
1626 /* Kill all auto-incremented values. */
1627 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
1628 for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd);
1630 /* Kill all early-clobbered operands. */
1631 for (i = 0; i < n_ops; i++)
1632 if (recog_op_alt[i][alt].earlyclobber)
1633 kill_value (recog_data.operand[i], vd);
1635 /* Special-case plain move instructions, since we may well
1636 be able to do the move from a different register class. */
1637 if (set && REG_P (SET_SRC (set)))
1639 rtx src = SET_SRC (set);
1640 unsigned int regno = REGNO (src);
1641 enum machine_mode mode = GET_MODE (src);
1645 /* If we are accessing SRC in some mode other that what we
1646 set it in, make sure that the replacement is valid. */
1647 if (mode != vd->e[regno].mode)
1649 if (hard_regno_nregs[regno][mode]
1650 > hard_regno_nregs[regno][vd->e[regno].mode])
1651 goto no_move_special_case;
1654 /* If the destination is also a register, try to find a source
1655 register in the same class. */
1656 if (REG_P (SET_DEST (set)))
1658 new = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd);
1659 if (new && validate_change (insn, &SET_SRC (set), new, 0))
1663 "insn %u: replaced reg %u with %u\n",
1664 INSN_UID (insn), regno, REGNO (new));
1666 goto did_replacement;
1670 /* Otherwise, try all valid registers and see if its valid. */
1671 for (i = vd->e[regno].oldest_regno; i != regno;
1672 i = vd->e[i].next_regno)
1674 new = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode,
1676 if (new != NULL_RTX)
1678 if (validate_change (insn, &SET_SRC (set), new, 0))
1680 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src);
1681 REG_ATTRS (new) = REG_ATTRS (src);
1684 "insn %u: replaced reg %u with %u\n",
1685 INSN_UID (insn), regno, REGNO (new));
1687 goto did_replacement;
1692 no_move_special_case:
1694 any_replacements = false;
1696 /* For each input operand, replace a hard register with the
1697 eldest live copy that's in an appropriate register class. */
1698 for (i = 0; i < n_ops; i++)
1700 replaced[i] = false;
1702 /* Don't scan match_operand here, since we've no reg class
1703 information to pass down. Any operands that we could
1704 substitute in will be represented elsewhere. */
1705 if (recog_data.constraints[i][0] == '\0')
1708 /* Don't replace in asms intentionally referencing hard regs. */
1709 if (is_asm && REG_P (recog_data.operand[i])
1710 && (REGNO (recog_data.operand[i])
1711 == ORIGINAL_REGNO (recog_data.operand[i])))
1714 if (recog_data.operand_type[i] == OP_IN)
1716 if (recog_op_alt[i][alt].is_address)
1718 = replace_oldest_value_addr (recog_data.operand_loc[i],
1719 recog_op_alt[i][alt].cl,
1720 VOIDmode, insn, vd);
1721 else if (REG_P (recog_data.operand[i]))
1723 = replace_oldest_value_reg (recog_data.operand_loc[i],
1724 recog_op_alt[i][alt].cl,
1726 else if (MEM_P (recog_data.operand[i]))
1727 replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
1730 else if (MEM_P (recog_data.operand[i]))
1731 replaced[i] = replace_oldest_value_mem (recog_data.operand[i],
1734 /* If we performed any replacement, update match_dups. */
1740 new = *recog_data.operand_loc[i];
1741 recog_data.operand[i] = new;
1742 for (j = 0; j < recog_data.n_dups; j++)
1743 if (recog_data.dup_num[j] == i)
1744 validate_change (insn, recog_data.dup_loc[j], new, 1);
1746 any_replacements = true;
1750 if (any_replacements)
1752 if (! apply_change_group ())
1754 for (i = 0; i < n_ops; i++)
1757 rtx old = *recog_data.operand_loc[i];
1758 recog_data.operand[i] = old;
1763 "insn %u: reg replacements not verified\n",
1771 /* Clobber call-clobbered registers. */
1773 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1774 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1775 kill_value_regno (i, 1, vd);
1777 /* Notice stores. */
1778 note_stores (PATTERN (insn), kill_set_value, vd);
1780 /* Notice copies. */
1781 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
1782 copy_value (SET_DEST (set), SET_SRC (set), vd);
1784 if (insn == BB_END (bb))
1791 /* Main entry point for the forward copy propagation optimization. */
1794 copyprop_hardreg_forward (void)
1796 struct value_data *all_vd;
1801 need_refresh = false;
1803 all_vd = XNEWVEC (struct value_data, last_basic_block);
1805 visited = sbitmap_alloc (last_basic_block);
1806 sbitmap_zero (visited);
1810 SET_BIT (visited, bb->index);
1812 /* If a block has a single predecessor, that we've already
1813 processed, begin with the value data that was live at
1814 the end of the predecessor block. */
1815 /* ??? Ought to use more intelligent queuing of blocks. */
1816 if (single_pred_p (bb)
1817 && TEST_BIT (visited, single_pred (bb)->index)
1818 && ! (single_pred_edge (bb)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
1819 all_vd[bb->index] = all_vd[single_pred (bb)->index];
1821 init_value_data (all_vd + bb->index);
1823 if (copyprop_hardreg_forward_1 (bb, all_vd + bb->index))
1824 need_refresh = true;
1827 sbitmap_free (visited);
1832 fputs ("\n\n", dump_file);
1834 /* ??? Irritatingly, delete_noop_moves does not take a set of blocks
1835 to scan, so we have to do a life update with no initial set of
1836 blocks Just In Case. */
1837 delete_noop_moves ();
1838 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
1840 | PROP_SCAN_DEAD_CODE
1841 | PROP_KILL_DEAD_CODE);
1847 /* Dump the value chain data to stderr. */
1850 debug_value_data (struct value_data *vd)
1855 CLEAR_HARD_REG_SET (set);
1857 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1858 if (vd->e[i].oldest_regno == i)
1860 if (vd->e[i].mode == VOIDmode)
1862 if (vd->e[i].next_regno != INVALID_REGNUM)
1863 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n",
1864 i, vd->e[i].next_regno);
1868 SET_HARD_REG_BIT (set, i);
1869 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode));
1871 for (j = vd->e[i].next_regno;
1872 j != INVALID_REGNUM;
1873 j = vd->e[j].next_regno)
1875 if (TEST_HARD_REG_BIT (set, j))
1877 fprintf (stderr, "[%u] Loop in regno chain\n", j);
1881 if (vd->e[j].oldest_regno != i)
1883 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n",
1884 j, vd->e[j].oldest_regno);
1887 SET_HARD_REG_BIT (set, j);
1888 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode));
1890 fputc ('\n', stderr);
1893 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1894 if (! TEST_HARD_REG_BIT (set, i)
1895 && (vd->e[i].mode != VOIDmode
1896 || vd->e[i].oldest_regno != i
1897 || vd->e[i].next_regno != INVALID_REGNUM))
1898 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n",
1899 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1900 vd->e[i].next_regno);
1903 #ifdef ENABLE_CHECKING
1905 validate_value_data (struct value_data *vd)
1910 CLEAR_HARD_REG_SET (set);
1912 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1913 if (vd->e[i].oldest_regno == i)
1915 if (vd->e[i].mode == VOIDmode)
1917 if (vd->e[i].next_regno != INVALID_REGNUM)
1918 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1919 i, vd->e[i].next_regno);
1923 SET_HARD_REG_BIT (set, i);
1925 for (j = vd->e[i].next_regno;
1926 j != INVALID_REGNUM;
1927 j = vd->e[j].next_regno)
1929 if (TEST_HARD_REG_BIT (set, j))
1930 internal_error ("validate_value_data: Loop in regno chain (%u)",
1932 if (vd->e[j].oldest_regno != i)
1933 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1934 j, vd->e[j].oldest_regno);
1936 SET_HARD_REG_BIT (set, j);
1940 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1941 if (! TEST_HARD_REG_BIT (set, i)
1942 && (vd->e[i].mode != VOIDmode
1943 || vd->e[i].oldest_regno != i
1944 || vd->e[i].next_regno != INVALID_REGNUM))
1945 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1946 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1947 vd->e[i].next_regno);
1952 gate_handle_regrename (void)
1954 return (optimize > 0 && (flag_rename_registers || flag_cprop_registers));
1958 /* Run the regrename and cprop passes. */
1960 rest_of_handle_regrename (void)
1962 if (flag_rename_registers)
1963 regrename_optimize ();
1964 if (flag_cprop_registers)
1965 copyprop_hardreg_forward ();
1969 struct tree_opt_pass pass_regrename =
1972 gate_handle_regrename, /* gate */
1973 rest_of_handle_regrename, /* execute */
1976 0, /* static_pass_number */
1977 TV_RENAME_REGISTERS, /* tv_id */
1978 0, /* properties_required */
1979 0, /* properties_provided */
1980 0, /* properties_destroyed */
1981 0, /* todo_flags_start */
1982 TODO_dump_func, /* todo_flags_finish */