1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000, 2001 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
27 #include "insn-config.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
39 #define obstack_chunk_alloc xmalloc
40 #define obstack_chunk_free free
42 #ifndef REGNO_MODE_OK_FOR_BASE_P
43 #define REGNO_MODE_OK_FOR_BASE_P(REGNO, MODE) REGNO_OK_FOR_BASE_P (REGNO)
46 #ifndef REG_MODE_OK_FOR_BASE_P
47 #define REG_MODE_OK_FOR_BASE_P(REGNO, MODE) REG_OK_FOR_BASE_P (REGNO)
50 static const char *const reg_class_names[] = REG_CLASS_NAMES;
54 struct du_chain *next_chain;
55 struct du_chain *next_use;
60 unsigned int need_caller_save_reg:1;
61 unsigned int earlyclobber:1;
67 terminate_overlapping_read,
74 static const char * const scan_actions_name[] =
77 "terminate_overlapping_read",
84 static struct obstack rename_obstack;
86 static void do_replace PARAMS ((struct du_chain *, int));
87 static void scan_rtx_reg PARAMS ((rtx, rtx *, enum reg_class,
88 enum scan_actions, enum op_type, int));
89 static void scan_rtx_address PARAMS ((rtx, rtx *, enum reg_class,
90 enum scan_actions, enum machine_mode));
91 static void scan_rtx PARAMS ((rtx, rtx *, enum reg_class,
92 enum scan_actions, enum op_type, int));
93 static struct du_chain *build_def_use PARAMS ((basic_block));
94 static void dump_def_use_chain PARAMS ((struct du_chain *));
95 static void note_sets PARAMS ((rtx, rtx, void *));
96 static void clear_dead_regs PARAMS ((HARD_REG_SET *, enum machine_mode, rtx));
97 static void merge_overlapping_regs PARAMS ((basic_block, HARD_REG_SET *,
100 /* Called through note_stores from update_life. Find sets of registers, and
101 record them in *DATA (which is actually a HARD_REG_SET *). */
104 note_sets (x, set, data)
106 rtx set ATTRIBUTE_UNUSED;
109 HARD_REG_SET *pset = (HARD_REG_SET *) data;
112 if (GET_CODE (x) != REG)
115 nregs = HARD_REGNO_NREGS (regno, GET_MODE (x));
117 /* There must not be pseudos at this point. */
118 if (regno + nregs > FIRST_PSEUDO_REGISTER)
122 SET_HARD_REG_BIT (*pset, regno + nregs);
125 /* Clear all registers from *PSET for which a note of kind KIND can be found
126 in the list NOTES. */
129 clear_dead_regs (pset, kind, notes)
131 enum machine_mode kind;
135 for (note = notes; note; note = XEXP (note, 1))
136 if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0)))
138 rtx reg = XEXP (note, 0);
139 unsigned int regno = REGNO (reg);
140 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
142 /* There must not be pseudos at this point. */
143 if (regno + nregs > FIRST_PSEUDO_REGISTER)
147 CLEAR_HARD_REG_BIT (*pset, regno + nregs);
151 /* For a def-use chain CHAIN in basic block B, find which registers overlap
152 its lifetime and set the corresponding bits in *PSET. */
155 merge_overlapping_regs (b, pset, chain)
158 struct du_chain *chain;
160 struct du_chain *t = chain;
164 REG_SET_TO_HARD_REG_SET (live, b->global_live_at_start);
168 /* Search forward until the next reference to the register to be
170 while (insn != t->insn)
174 clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn));
175 note_stores (PATTERN (insn), note_sets, (void *) &live);
176 /* Only record currently live regs if we are inside the
179 IOR_HARD_REG_SET (*pset, live);
180 clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn));
182 insn = NEXT_INSN (insn);
185 IOR_HARD_REG_SET (*pset, live);
187 /* For the last reference, also merge in all registers set in the
189 @@@ We only have take earlyclobbered sets into account. */
191 note_stores (PATTERN (insn), note_sets, (void *) pset);
197 /* Perform register renaming on the current function. */
200 regrename_optimize ()
202 int tick[FIRST_PSEUDO_REGISTER];
207 memset (tick, 0, sizeof tick);
209 gcc_obstack_init (&rename_obstack);
210 first_obj = (char *) obstack_alloc (&rename_obstack, 0);
212 for (b = 0; b < n_basic_blocks; b++)
214 basic_block bb = BASIC_BLOCK (b);
215 struct du_chain *all_chains = 0;
216 HARD_REG_SET unavailable;
217 HARD_REG_SET regs_seen;
219 CLEAR_HARD_REG_SET (unavailable);
222 fprintf (rtl_dump_file, "\nBasic block %d:\n", b);
224 all_chains = build_def_use (bb);
227 dump_def_use_chain (all_chains);
229 CLEAR_HARD_REG_SET (unavailable);
230 /* Don't clobber traceback for noreturn functions. */
231 if (frame_pointer_needed)
235 for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;)
236 SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM + i);
238 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
239 for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;)
240 SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM + i);
244 CLEAR_HARD_REG_SET (regs_seen);
247 int new_reg, best_new_reg = -1;
249 struct du_chain *this = all_chains;
250 struct du_chain *tmp, *last;
251 HARD_REG_SET this_unavailable;
252 int reg = REGNO (*this->loc);
255 all_chains = this->next_chain;
257 #if 0 /* This just disables optimization opportunities. */
258 /* Only rename once we've seen the reg more than once. */
259 if (! TEST_HARD_REG_BIT (regs_seen, reg))
261 SET_HARD_REG_BIT (regs_seen, reg);
266 if (fixed_regs[reg] || global_regs[reg]
267 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
268 || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
270 || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
275 COPY_HARD_REG_SET (this_unavailable, unavailable);
277 /* Find last entry on chain (which has the need_caller_save bit),
278 count number of uses, and narrow the set of registers we can
281 for (last = this; last->next_use; last = last->next_use)
284 IOR_COMPL_HARD_REG_SET (this_unavailable,
285 reg_class_contents[last->class]);
290 IOR_COMPL_HARD_REG_SET (this_unavailable,
291 reg_class_contents[last->class]);
293 if (this->need_caller_save_reg)
294 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
296 merge_overlapping_regs (bb, &this_unavailable, this);
298 /* Now potential_regs is a reasonable approximation, let's
299 have a closer look at each register still in there. */
300 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
302 int nregs = HARD_REGNO_NREGS (new_reg, GET_MODE (*this->loc));
304 for (i = nregs - 1; i >= 0; --i)
305 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
306 || fixed_regs[new_reg + i]
307 || global_regs[new_reg + i]
308 /* Can't use regs which aren't saved by the prologue. */
309 || (! regs_ever_live[new_reg + i]
310 && ! call_used_regs[new_reg + i])
311 #ifdef LEAF_REGISTERS
312 /* We can't use a non-leaf register if we're in a
314 || (current_function_is_leaf
315 && !LEAF_REGISTERS[new_reg + i])
317 #ifdef HARD_REGNO_RENAME_OK
318 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
325 /* See whether it accepts all modes that occur in
326 definition and uses. */
327 for (tmp = this; tmp; tmp = tmp->next_use)
328 if (! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc)))
332 if (best_new_reg == -1
333 || tick[best_new_reg] > tick[new_reg])
334 best_new_reg = new_reg;
340 fprintf (rtl_dump_file, "Register %s in insn %d",
341 reg_names[reg], INSN_UID (last->insn));
342 if (last->need_caller_save_reg)
343 fprintf (rtl_dump_file, " crosses a call");
346 if (best_new_reg == -1)
349 fprintf (rtl_dump_file, "; no available registers\n");
353 do_replace (this, best_new_reg);
354 tick[best_new_reg] = this_tick++;
357 fprintf (rtl_dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
360 obstack_free (&rename_obstack, first_obj);
363 obstack_free (&rename_obstack, NULL);
366 fputc ('\n', rtl_dump_file);
368 count_or_remove_death_notes (NULL, 1);
369 update_life_info (NULL, UPDATE_LIFE_LOCAL,
370 PROP_REG_INFO | PROP_DEATH_NOTES);
374 do_replace (chain, reg)
375 struct du_chain *chain;
380 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
381 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
382 if (regno >= FIRST_PSEUDO_REGISTER)
383 ORIGINAL_REGNO (*chain->loc) = regno;
384 chain = chain->next_use;
389 static struct du_chain *open_chains;
390 static struct du_chain *closed_chains;
393 scan_rtx_reg (insn, loc, class, action, type, earlyclobber)
396 enum reg_class class;
397 enum scan_actions action;
403 enum machine_mode mode = GET_MODE (x);
404 int this_regno = REGNO (x);
405 int this_nregs = HARD_REGNO_NREGS (this_regno, mode);
407 if (action == mark_write)
411 struct du_chain *this = (struct du_chain *)
412 obstack_alloc (&rename_obstack, sizeof (struct du_chain));
414 this->next_chain = open_chains;
418 this->need_caller_save_reg = 0;
419 this->earlyclobber = earlyclobber;
425 if ((type == OP_OUT && action != terminate_write)
426 || (type != OP_OUT && action == terminate_write))
429 for (p = &open_chains; *p;)
431 struct du_chain *this = *p;
433 /* Check if the chain has been terminated if it has then skip to
436 This can happen when we've already appended the location to
437 the chain in Step 3, but are trying to hide in-out operands
438 from terminate_write in Step 5. */
440 if (*this->loc == cc0_rtx)
441 p = &this->next_chain;
444 int regno = REGNO (*this->loc);
445 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (*this->loc));
446 int exact_match = (regno == this_regno && nregs == this_nregs);
448 if (regno + nregs <= this_regno
449 || this_regno + this_nregs <= regno)
451 p = &this->next_chain;
455 if (action == mark_read)
460 /* ??? Class NO_REGS can happen if the md file makes use of
461 EXTRA_CONSTRAINTS to match registers. Which is arguably
462 wrong, but there we are. Since we know not what this may
463 be replaced with, terminate the chain. */
464 if (class != NO_REGS)
466 this = (struct du_chain *)
467 obstack_alloc (&rename_obstack, sizeof (struct du_chain));
469 this->next_chain = (*p)->next_chain;
473 this->need_caller_save_reg = 0;
481 if (action != terminate_overlapping_read || ! exact_match)
483 struct du_chain *next = this->next_chain;
485 /* Whether the terminated chain can be used for renaming
486 depends on the action and this being an exact match.
487 In either case, we remove this element from open_chains. */
489 if ((action == terminate_dead || action == terminate_write)
492 this->next_chain = closed_chains;
493 closed_chains = this;
495 fprintf (rtl_dump_file,
496 "Closing chain %s at insn %d (%s)\n",
497 reg_names[REGNO (*this->loc)], INSN_UID (insn),
498 scan_actions_name[(int) action]);
503 fprintf (rtl_dump_file,
504 "Discarding chain %s at insn %d (%s)\n",
505 reg_names[REGNO (*this->loc)], INSN_UID (insn),
506 scan_actions_name[(int) action]);
511 p = &this->next_chain;
516 /* Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
517 BASE_REG_CLASS depending on how the register is being considered. */
520 scan_rtx_address (insn, loc, class, action, mode)
523 enum reg_class class;
524 enum scan_actions action;
525 enum machine_mode mode;
528 RTX_CODE code = GET_CODE (x);
532 if (action == mark_write)
539 rtx orig_op0 = XEXP (x, 0);
540 rtx orig_op1 = XEXP (x, 1);
541 RTX_CODE code0 = GET_CODE (orig_op0);
542 RTX_CODE code1 = GET_CODE (orig_op1);
548 if (GET_CODE (op0) == SUBREG)
550 op0 = SUBREG_REG (op0);
551 code0 = GET_CODE (op0);
554 if (GET_CODE (op1) == SUBREG)
556 op1 = SUBREG_REG (op1);
557 code1 = GET_CODE (op1);
560 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
561 || code0 == ZERO_EXTEND || code1 == MEM)
566 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
567 || code1 == ZERO_EXTEND || code0 == MEM)
572 else if (code0 == CONST_INT || code0 == CONST
573 || code0 == SYMBOL_REF || code0 == LABEL_REF)
575 else if (code1 == CONST_INT || code1 == CONST
576 || code1 == SYMBOL_REF || code1 == LABEL_REF)
578 else if (code0 == REG && code1 == REG)
582 if (REG_OK_FOR_INDEX_P (op0)
583 && REG_MODE_OK_FOR_BASE_P (op1, mode))
585 else if (REG_OK_FOR_INDEX_P (op1)
586 && REG_MODE_OK_FOR_BASE_P (op0, mode))
588 else if (REG_MODE_OK_FOR_BASE_P (op1, mode))
590 else if (REG_MODE_OK_FOR_BASE_P (op0, mode))
592 else if (REG_OK_FOR_INDEX_P (op1))
597 locI = &XEXP (x, index_op);
598 locB = &XEXP (x, !index_op);
600 else if (code0 == REG)
605 else if (code1 == REG)
612 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
614 scan_rtx_address (insn, locB, BASE_REG_CLASS, action, mode);
625 /* If the target doesn't claim to handle autoinc, this must be
626 something special, like a stack push. Kill this chain. */
627 action = terminate_all_read;
632 scan_rtx_address (insn, &XEXP (x, 0), BASE_REG_CLASS, action,
637 scan_rtx_reg (insn, loc, class, action, OP_IN, 0);
644 fmt = GET_RTX_FORMAT (code);
645 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
648 scan_rtx_address (insn, &XEXP (x, i), class, action, mode);
649 else if (fmt[i] == 'E')
650 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
651 scan_rtx_address (insn, &XVECEXP (x, i, j), class, action, mode);
656 scan_rtx (insn, loc, class, action, type, earlyclobber)
659 enum reg_class class;
660 enum scan_actions action;
666 enum rtx_code code = GET_CODE (x);
682 scan_rtx_reg (insn, loc, class, action, type, earlyclobber);
686 scan_rtx_address (insn, &XEXP (x, 0), BASE_REG_CLASS, action,
691 scan_rtx (insn, &SET_SRC (x), class, action, OP_IN, 0);
692 scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 0);
695 case STRICT_LOW_PART:
696 scan_rtx (insn, &XEXP (x, 0), class, action, OP_INOUT, earlyclobber);
701 scan_rtx (insn, &XEXP (x, 0), class, action,
702 type == OP_IN ? OP_IN : OP_INOUT, earlyclobber);
703 scan_rtx (insn, &XEXP (x, 1), class, action, OP_IN, 0);
704 scan_rtx (insn, &XEXP (x, 2), class, action, OP_IN, 0);
713 /* Should only happen inside MEM. */
717 scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 1);
721 scan_rtx (insn, &XEXP (x, 0), class, action, type, 0);
723 scan_rtx (insn, &XEXP (x, 1), class, action, type, 0);
730 fmt = GET_RTX_FORMAT (code);
731 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
734 scan_rtx (insn, &XEXP (x, i), class, action, type, 0);
735 else if (fmt[i] == 'E')
736 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
737 scan_rtx (insn, &XVECEXP (x, i, j), class, action, type, 0);
741 /* Build def/use chain */
743 static struct du_chain *
749 open_chains = closed_chains = NULL;
751 for (insn = bb->head; ; insn = NEXT_INSN (insn))
757 rtx old_operands[MAX_RECOG_OPERANDS];
758 rtx old_dups[MAX_DUP_OPERANDS];
763 /* Process the insn, determining its effect on the def-use
764 chains. We perform the following steps with the register
765 references in the insn:
766 (1) Any read that overlaps an open chain, but doesn't exactly
767 match, causes that chain to be closed. We can't deal
769 (2) Any read outside an operand causes any chain it overlaps
770 with to be closed, since we can't replace it.
771 (3) Any read inside an operand is added if there's already
772 an open chain for it.
773 (4) For any REG_DEAD note we find, close open chains that
775 (5) For any write we find, close open chains that overlap it.
776 (6) For any write we find in an operand, make a new chain.
777 (7) For any REG_UNUSED, close any chains we just opened. */
780 constrain_operands (1);
781 preprocess_constraints ();
782 alt = which_alternative;
783 n_ops = recog_data.n_operands;
785 /* Simplify the code below by rewriting things to reflect
786 matching constraints. Also promote OP_OUT to OP_INOUT
787 in predicated instructions. */
789 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
790 for (i = 0; i < n_ops; ++i)
792 int matches = recog_op_alt[i][alt].matches;
794 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class;
795 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
796 || (predicated && recog_data.operand_type[i] == OP_OUT))
797 recog_data.operand_type[i] = OP_INOUT;
800 /* Step 1: Close chains for which we have overlapping reads. */
801 for (i = 0; i < n_ops; i++)
802 scan_rtx (insn, recog_data.operand_loc[i],
803 NO_REGS, terminate_overlapping_read,
804 recog_data.operand_type[i], 0);
806 /* Step 2: Close chains for which we have reads outside operands.
807 We do this by munging all operands into CC0, and closing
808 everything remaining. */
810 for (i = 0; i < n_ops; i++)
812 old_operands[i] = recog_data.operand[i];
813 /* Don't squash match_operator or match_parallel here, since
814 we don't know that all of the contained registers are
815 reachable by proper operands. */
816 if (recog_data.constraints[i][0] == '\0')
818 *recog_data.operand_loc[i] = cc0_rtx;
820 for (i = 0; i < recog_data.n_dups; i++)
822 old_dups[i] = *recog_data.dup_loc[i];
823 *recog_data.dup_loc[i] = cc0_rtx;
826 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read,
829 for (i = 0; i < recog_data.n_dups; i++)
830 *recog_data.dup_loc[i] = old_dups[i];
831 for (i = 0; i < n_ops; i++)
832 *recog_data.operand_loc[i] = old_operands[i];
834 /* Step 2B: Can't rename function call argument registers. */
835 if (GET_CODE (insn) == CALL_INSN && CALL_INSN_FUNCTION_USAGE (insn))
836 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
837 NO_REGS, terminate_all_read, OP_IN, 0);
839 /* Step 3: Append to chains for reads inside operands. */
840 for (i = 0; i < n_ops + recog_data.n_dups; i++)
842 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
843 rtx *loc = (i < n_ops
844 ? recog_data.operand_loc[opn]
845 : recog_data.dup_loc[i - n_ops]);
846 enum reg_class class = recog_op_alt[opn][alt].class;
847 enum op_type type = recog_data.operand_type[opn];
849 /* Don't scan match_operand here, since we've no reg class
850 information to pass down. Any operands that we could
851 substitute in will be represented elsewhere. */
852 if (recog_data.constraints[opn][0] == '\0')
855 if (recog_op_alt[opn][alt].is_address)
856 scan_rtx_address (insn, loc, class, mark_read, VOIDmode);
858 scan_rtx (insn, loc, class, mark_read, type, 0);
861 /* Step 4: Close chains for registers that die here.
862 Also record updates for REG_INC notes. */
863 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
865 if (REG_NOTE_KIND (note) == REG_DEAD)
866 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
868 else if (REG_NOTE_KIND (note) == REG_INC)
869 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
873 /* Step 4B: If this is a call, any chain live at this point
874 requires a caller-saved reg. */
875 if (GET_CODE (insn) == CALL_INSN)
878 for (p = open_chains; p; p = p->next_chain)
879 p->need_caller_save_reg = 1;
882 /* Step 5: Close open chains that overlap writes. Similar to
883 step 2, we hide in-out operands, since we do not want to
884 close these chains. */
886 for (i = 0; i < n_ops; i++)
888 old_operands[i] = recog_data.operand[i];
889 if (recog_data.operand_type[i] == OP_INOUT)
890 *recog_data.operand_loc[i] = cc0_rtx;
892 for (i = 0; i < recog_data.n_dups; i++)
894 int opn = recog_data.dup_num[i];
895 old_dups[i] = *recog_data.dup_loc[i];
896 if (recog_data.operand_type[opn] == OP_INOUT)
897 *recog_data.dup_loc[i] = cc0_rtx;
900 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0);
902 for (i = 0; i < recog_data.n_dups; i++)
903 *recog_data.dup_loc[i] = old_dups[i];
904 for (i = 0; i < n_ops; i++)
905 *recog_data.operand_loc[i] = old_operands[i];
907 /* Step 6: Begin new chains for writes inside operands. */
908 /* ??? Many targets have output constraints on the SET_DEST
909 of a call insn, which is stupid, since these are certainly
910 ABI defined hard registers. Don't change calls at all. */
911 if (GET_CODE (insn) != CALL_INSN)
912 for (i = 0; i < n_ops + recog_data.n_dups; i++)
914 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
915 rtx *loc = (i < n_ops
916 ? recog_data.operand_loc[opn]
917 : recog_data.dup_loc[i - n_ops]);
918 enum reg_class class = recog_op_alt[opn][alt].class;
920 if (recog_data.operand_type[opn] == OP_OUT)
921 scan_rtx (insn, loc, class, mark_write, OP_OUT,
922 recog_op_alt[opn][alt].earlyclobber);
925 /* Step 7: Close chains for registers that were never
927 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
928 if (REG_NOTE_KIND (note) == REG_UNUSED)
929 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
936 /* Since we close every chain when we find a REG_DEAD note, anything that
937 is still open lives past the basic block, so it can't be renamed. */
938 return closed_chains;
941 /* Dump all def/use chains in CHAINS to RTL_DUMP_FILE. They are
942 printed in reverse order as that's how we build them. */
945 dump_def_use_chain (chains)
946 struct du_chain *chains;
950 struct du_chain *this = chains;
951 int r = REGNO (*this->loc);
952 int nregs = HARD_REGNO_NREGS (r, GET_MODE (*this->loc));
953 fprintf (rtl_dump_file, "Register %s (%d):", reg_names[r], nregs);
956 fprintf (rtl_dump_file, " %d [%s]", INSN_UID (this->insn),
957 reg_class_names[this->class]);
958 this = this->next_use;
960 fprintf (rtl_dump_file, "\n");
961 chains = chains->next_chain;
965 /* The following code does forward propagation of hard register copies.
966 The object is to eliminate as many dependencies as possible, so that
967 we have the most scheduling freedom. As a side effect, we also clean
968 up some silly register allocation decisions made by reload. This
969 code may be obsoleted by a new register allocator. */
971 /* For each register, we have a list of registers that contain the same
972 value. The OLDEST_REGNO field points to the head of the list, and
973 the NEXT_REGNO field runs through the list. The MODE field indicates
974 what mode the data is known to be in; this field is VOIDmode when the
975 register is not known to contain valid data. */
977 struct value_data_entry
979 enum machine_mode mode;
980 unsigned int oldest_regno;
981 unsigned int next_regno;
986 struct value_data_entry e[FIRST_PSEUDO_REGISTER];
989 static void kill_value_regno PARAMS ((unsigned, struct value_data *));
990 static void kill_value PARAMS ((rtx, struct value_data *));
991 static void init_value_data PARAMS ((struct value_data *));
992 static void kill_clobbered_value PARAMS ((rtx, rtx, void *));
993 static void kill_set_value PARAMS ((rtx, rtx, void *));
994 static int kill_autoinc_value PARAMS ((rtx *, void *));
995 static void copy_value PARAMS ((rtx, rtx, struct value_data *));
996 static rtx find_oldest_value_reg PARAMS ((enum reg_class, unsigned int,
998 struct value_data *));
999 static bool replace_oldest_value_reg PARAMS ((rtx *, enum reg_class, rtx,
1000 struct value_data *));
1001 static bool replace_oldest_value_addr PARAMS ((rtx *, enum reg_class,
1002 enum machine_mode, rtx,
1003 struct value_data *));
1004 static bool replace_oldest_value_mem PARAMS ((rtx, rtx, struct value_data *));
1005 static bool copyprop_hardreg_forward_1 PARAMS ((basic_block,
1006 struct value_data *));
1007 extern void debug_value_data PARAMS ((struct value_data *));
1008 #ifdef ENABLE_CHECKING
1009 static void validate_value_data PARAMS ((struct value_data *));
1012 /* Kill register REGNO. This involves removing it from any value lists,
1013 and resetting the value mode to VOIDmode. */
1016 kill_value_regno (regno, vd)
1018 struct value_data *vd;
1020 unsigned int i, next;
1022 if (vd->e[regno].oldest_regno != regno)
1024 for (i = vd->e[regno].oldest_regno;
1025 vd->e[i].next_regno != regno;
1026 i = vd->e[i].next_regno)
1029 next = vd->e[regno].next_regno;
1032 vd->e[i].next_regno = next;
1033 if (next == INVALID_REGNUM)
1036 next = vd->e[next].next_regno;
1039 else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM)
1041 for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno)
1042 vd->e[i].oldest_regno = next;
1045 vd->e[regno].mode = VOIDmode;
1046 vd->e[regno].oldest_regno = regno;
1047 vd->e[regno].next_regno = INVALID_REGNUM;
1049 #ifdef ENABLE_CHECKING
1050 validate_value_data (vd);
1054 /* Kill X. This is a convenience function for kill_value_regno
1055 so that we don't have to check that X is a register first. */
1060 struct value_data *vd;
1063 kill_value_regno (REGNO (x), vd);
1066 /* Initialize VD such that there are no known relationships between regs. */
1069 init_value_data (vd)
1070 struct value_data *vd;
1073 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1075 vd->e[i].mode = VOIDmode;
1076 vd->e[i].oldest_regno = i;
1077 vd->e[i].next_regno = INVALID_REGNUM;
1081 /* Called through note_stores. If X is clobbered, kill its value. */
1084 kill_clobbered_value (x, set, data)
1089 struct value_data *vd = data;
1090 if (GET_CODE (set) == CLOBBER)
1094 /* Called through note_stores. If X is set, not clobbered, kill its
1095 current value and install it as the root of its own value list. */
1098 kill_set_value (x, set, data)
1103 struct value_data *vd = data;
1104 if (GET_CODE (set) != CLOBBER && REG_P (x))
1106 unsigned int regno = REGNO (x);
1107 kill_value_regno (regno, vd);
1108 vd->e[regno].mode = GET_MODE (x);
1112 /* Called through for_each_rtx. Kill any register used as the base of an
1113 auto-increment expression, and install that register as the root of its
1117 kill_autoinc_value (px, data)
1122 struct value_data *vd = data;
1124 if (GET_RTX_CLASS (GET_CODE (x)) == 'a')
1126 unsigned int regno = REGNO (XEXP (x, 0));
1127 kill_value_regno (regno, vd);
1128 vd->e[regno].mode = Pmode;
1135 /* Assert that SRC has been copied to DEST. Adjust the data structures
1136 to reflect that SRC contains an older copy of the shared value. */
1139 copy_value (dest, src, vd)
1142 struct value_data *vd;
1144 unsigned int dr = REGNO (dest);
1145 unsigned int sr = REGNO (src);
1148 /* ??? At present, it's possible to see noop sets. It'd be nice if
1149 this were cleaned up beforehand... */
1153 /* Do not propagate copies to the stack pointer, as that can leave
1154 memory accesses with no scheduling dependancy on the stack update. */
1155 if (dr == STACK_POINTER_REGNUM)
1158 /* Likewise with the frame pointer, if we're using one. */
1159 if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM)
1162 /* If SRC had no assigned mode (i.e. we didn't know it was live)
1163 assign it now and assume the value came from an input argument
1165 if (vd->e[sr].mode == VOIDmode)
1166 vd->e[sr].mode = vd->e[dr].mode;
1168 /* Link DR at the end of the value chain used by SR. */
1170 vd->e[dr].oldest_regno = vd->e[sr].oldest_regno;
1172 for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno)
1174 vd->e[i].next_regno = dr;
1176 #ifdef ENABLE_CHECKING
1177 validate_value_data (vd);
1181 /* Find the oldest copy of the value contained in REGNO that is in
1182 register class CLASS and has mode MODE. If found, return an rtx
1183 of that oldest register, otherwise return NULL. */
1186 find_oldest_value_reg (class, regno, mode, vd)
1187 enum reg_class class;
1189 enum machine_mode mode;
1190 struct value_data *vd;
1194 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno)
1195 if (vd->e[i].mode == mode
1196 && TEST_HARD_REG_BIT (reg_class_contents[class], i))
1197 return gen_rtx_REG (mode, i);
1202 /* If possible, replace the register at *LOC with the oldest register
1203 in register class CLASS. Return true if successfully replaced. */
1206 replace_oldest_value_reg (loc, class, insn, vd)
1208 enum reg_class class;
1210 struct value_data *vd;
1212 rtx new = find_oldest_value_reg (class, REGNO (*loc), GET_MODE (*loc), vd);
1216 fprintf (rtl_dump_file, "insn %u: replaced reg %u with %u\n",
1217 INSN_UID (insn), REGNO (*loc), REGNO (new));
1225 /* Similar to replace_oldest_value_reg, but *LOC contains an address.
1226 Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
1227 BASE_REG_CLASS depending on how the register is being considered. */
1230 replace_oldest_value_addr (loc, class, mode, insn, vd)
1232 enum reg_class class;
1233 enum machine_mode mode;
1235 struct value_data *vd;
1238 RTX_CODE code = GET_CODE (x);
1241 bool changed = false;
1247 rtx orig_op0 = XEXP (x, 0);
1248 rtx orig_op1 = XEXP (x, 1);
1249 RTX_CODE code0 = GET_CODE (orig_op0);
1250 RTX_CODE code1 = GET_CODE (orig_op1);
1256 if (GET_CODE (op0) == SUBREG)
1258 op0 = SUBREG_REG (op0);
1259 code0 = GET_CODE (op0);
1262 if (GET_CODE (op1) == SUBREG)
1264 op1 = SUBREG_REG (op1);
1265 code1 = GET_CODE (op1);
1268 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
1269 || code0 == ZERO_EXTEND || code1 == MEM)
1271 locI = &XEXP (x, 0);
1272 locB = &XEXP (x, 1);
1274 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
1275 || code1 == ZERO_EXTEND || code0 == MEM)
1277 locI = &XEXP (x, 1);
1278 locB = &XEXP (x, 0);
1280 else if (code0 == CONST_INT || code0 == CONST
1281 || code0 == SYMBOL_REF || code0 == LABEL_REF)
1282 locB = &XEXP (x, 1);
1283 else if (code1 == CONST_INT || code1 == CONST
1284 || code1 == SYMBOL_REF || code1 == LABEL_REF)
1285 locB = &XEXP (x, 0);
1286 else if (code0 == REG && code1 == REG)
1290 if (REG_OK_FOR_INDEX_P (op0)
1291 && REG_MODE_OK_FOR_BASE_P (op1, mode))
1293 else if (REG_OK_FOR_INDEX_P (op1)
1294 && REG_MODE_OK_FOR_BASE_P (op0, mode))
1296 else if (REG_MODE_OK_FOR_BASE_P (op1, mode))
1298 else if (REG_MODE_OK_FOR_BASE_P (op0, mode))
1300 else if (REG_OK_FOR_INDEX_P (op1))
1305 locI = &XEXP (x, index_op);
1306 locB = &XEXP (x, !index_op);
1308 else if (code0 == REG)
1310 locI = &XEXP (x, 0);
1311 locB = &XEXP (x, 1);
1313 else if (code1 == REG)
1315 locI = &XEXP (x, 1);
1316 locB = &XEXP (x, 0);
1320 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode,
1323 changed |= replace_oldest_value_addr (locB, BASE_REG_CLASS, mode,
1337 return replace_oldest_value_mem (x, insn, vd);
1340 return replace_oldest_value_reg (loc, class, insn, vd);
1346 fmt = GET_RTX_FORMAT (code);
1347 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1350 changed |= replace_oldest_value_addr (&XEXP (x, i), class, mode,
1352 else if (fmt[i] == 'E')
1353 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1354 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), class,
1361 /* Similar to replace_oldest_value_reg, but X contains a memory. */
1364 replace_oldest_value_mem (x, insn, vd)
1367 struct value_data *vd;
1369 return replace_oldest_value_addr (&XEXP (x, 0), BASE_REG_CLASS,
1370 GET_MODE (x), insn, vd);
1373 /* Perform the forward copy propagation on basic block BB. */
1376 copyprop_hardreg_forward_1 (bb, vd)
1378 struct value_data *vd;
1380 bool changed = false;
1383 for (insn = bb->head; ; insn = NEXT_INSN (insn))
1385 int n_ops, i, alt, predicated;
1388 if (! INSN_P (insn))
1390 if (insn == bb->end)
1396 set = single_set (insn);
1397 extract_insn (insn);
1398 constrain_operands (1);
1399 preprocess_constraints ();
1400 alt = which_alternative;
1401 n_ops = recog_data.n_operands;
1403 /* Simplify the code below by rewriting things to reflect
1404 matching constraints. Also promote OP_OUT to OP_INOUT
1405 in predicated instructions. */
1407 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1408 for (i = 0; i < n_ops; ++i)
1410 int matches = recog_op_alt[i][alt].matches;
1412 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class;
1413 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
1414 || (predicated && recog_data.operand_type[i] == OP_OUT))
1415 recog_data.operand_type[i] = OP_INOUT;
1418 /* For each earlyclobber operand, zap the value data. */
1419 for (i = 0; i < n_ops; i++)
1420 if (recog_op_alt[i][alt].earlyclobber)
1421 kill_value (recog_data.operand[i], vd);
1423 /* Within asms, a clobber cannot overlap inputs or outputs.
1424 I wouldn't think this were true for regular insns, but
1425 scan_rtx treats them like that... */
1426 note_stores (PATTERN (insn), kill_clobbered_value, vd);
1428 /* Kill all auto-incremented values. */
1429 /* ??? REG_INC is useless, since stack pushes aren't done that way. */
1430 for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd);
1432 /* Special-case plain move instructions, since we may well
1433 be able to do the move from a different register class. */
1434 if (set && REG_P (SET_SRC (set)))
1436 unsigned int regno = REGNO (SET_SRC (set));
1437 enum machine_mode mode = GET_MODE (SET_SRC (set));
1441 /* If the destination is also a register, try to find a source
1442 register in the same class. */
1443 if (REG_P (SET_DEST (set)))
1445 new = find_oldest_value_reg (REGNO_REG_CLASS (regno),
1447 if (new && validate_change (insn, &SET_SRC (set), new, 0))
1450 fprintf (rtl_dump_file,
1451 "insn %u: replaced reg %u with %u\n",
1452 INSN_UID (insn), regno, REGNO (new));
1454 goto did_replacement;
1458 /* Otherwise, try all valid registers and see if its valid. */
1459 for (i = vd->e[regno].oldest_regno; i != regno;
1460 i = vd->e[i].next_regno)
1461 if (mode == vd->e[regno].mode)
1463 new = gen_rtx_REG (mode, i);
1464 if (validate_change (insn, &SET_SRC (set), new, 0))
1467 fprintf (rtl_dump_file,
1468 "insn %u: replaced reg %u with %u\n",
1469 INSN_UID (insn), regno, REGNO (new));
1471 goto did_replacement;
1476 /* For each input operand, replace a hard register with the
1477 eldest live copy that's in an appropriate register class. */
1478 for (i = 0; i < n_ops; i++)
1480 bool replaced = false;
1482 /* Don't scan match_operand here, since we've no reg class
1483 information to pass down. Any operands that we could
1484 substitute in will be represented elsewhere. */
1485 if (recog_data.constraints[i][0] == '\0')
1488 if (recog_data.operand_type[i] == OP_IN)
1490 if (recog_op_alt[i][alt].is_address)
1492 = replace_oldest_value_addr (recog_data.operand_loc[i],
1493 recog_op_alt[i][alt].class,
1494 VOIDmode, insn, vd);
1495 else if (REG_P (recog_data.operand[i]))
1497 = replace_oldest_value_reg (recog_data.operand_loc[i],
1498 recog_op_alt[i][alt].class,
1500 else if (GET_CODE (recog_data.operand[i]) == MEM)
1501 replaced = replace_oldest_value_mem (recog_data.operand[i],
1504 else if (GET_CODE (recog_data.operand[i]) == MEM)
1505 replaced = replace_oldest_value_mem (recog_data.operand[i],
1508 /* If we performed any replacement, update match_dups. */
1516 new = *recog_data.operand_loc[i];
1517 recog_data.operand[i] = new;
1518 for (j = 0; j < recog_data.n_dups; j++)
1519 if (recog_data.dup_num[j] == i)
1520 *recog_data.dup_loc[j] = new;
1525 /* Clobber call-clobbered registers. */
1526 if (GET_CODE (insn) == CALL_INSN)
1527 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1528 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1529 kill_value_regno (i, vd);
1531 /* Notice stores. */
1532 note_stores (PATTERN (insn), kill_set_value, vd);
1534 /* Notice copies. */
1535 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set)))
1536 copy_value (SET_DEST (set), SET_SRC (set), vd);
1538 if (insn == bb->end)
1545 /* Main entry point for the forward copy propagation optimization. */
1548 copyprop_hardreg_forward ()
1550 int b, need_refresh;
1551 sbitmap refresh_blocks;
1552 struct value_data *all_vd;
1554 refresh_blocks = sbitmap_alloc (n_basic_blocks);
1555 sbitmap_zero (refresh_blocks);
1558 all_vd = xmalloc (sizeof (struct value_data) * n_basic_blocks);
1560 for (b = 0; b < n_basic_blocks; b++)
1562 basic_block bb = BASIC_BLOCK (b);
1564 /* If a block has a single predecessor, that we've already
1565 processed, begin with the value data that was live at
1566 the end of the predecessor block. */
1567 /* ??? Ought to use more intelligent queueing of blocks. */
1569 && ! bb->pred->pred_next
1570 && bb->pred->src->index != ENTRY_BLOCK
1571 && bb->pred->src->index < b)
1572 all_vd[b] = all_vd[bb->pred->src->index];
1574 init_value_data (all_vd + b);
1576 if (copyprop_hardreg_forward_1 (bb, all_vd + b))
1578 SET_BIT (refresh_blocks, b);
1586 fputs ("\n\n", rtl_dump_file);
1588 update_life_info (refresh_blocks, UPDATE_LIFE_GLOBAL_RM_NOTES,
1590 | PROP_SCAN_DEAD_CODE
1591 | PROP_KILL_DEAD_CODE);
1594 sbitmap_free (refresh_blocks);
1598 /* Dump the value chain data to stderr. */
1601 debug_value_data (vd)
1602 struct value_data *vd;
1607 CLEAR_HARD_REG_SET (set);
1609 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1610 if (vd->e[i].oldest_regno == i)
1612 if (vd->e[i].mode == VOIDmode)
1614 if (vd->e[i].next_regno != INVALID_REGNUM)
1615 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n",
1616 i, vd->e[i].next_regno);
1620 SET_HARD_REG_BIT (set, i);
1621 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode));
1623 for (j = vd->e[i].next_regno;
1624 j != INVALID_REGNUM;
1625 j = vd->e[j].next_regno)
1627 if (TEST_HARD_REG_BIT (set, vd->e[j].next_regno))
1629 fprintf (stderr, "[%u] Loop in regno chain\n", j);
1633 if (vd->e[j].oldest_regno != i)
1635 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n",
1636 j, vd->e[j].oldest_regno);
1639 SET_HARD_REG_BIT (set, j);
1640 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode));
1642 fputc ('\n', stderr);
1645 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1646 if (! TEST_HARD_REG_BIT (set, i)
1647 && (vd->e[i].mode != VOIDmode
1648 || vd->e[i].oldest_regno != i
1649 || vd->e[i].next_regno != INVALID_REGNUM))
1650 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n",
1651 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1652 vd->e[i].next_regno);
1655 #ifdef ENABLE_CHECKING
1657 validate_value_data (vd)
1658 struct value_data *vd;
1663 CLEAR_HARD_REG_SET (set);
1665 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1666 if (vd->e[i].oldest_regno == i)
1668 if (vd->e[i].mode == VOIDmode)
1670 if (vd->e[i].next_regno != INVALID_REGNUM)
1671 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)",
1672 i, vd->e[i].next_regno);
1676 SET_HARD_REG_BIT (set, i);
1678 for (j = vd->e[i].next_regno;
1679 j != INVALID_REGNUM;
1680 j = vd->e[j].next_regno)
1682 if (TEST_HARD_REG_BIT (set, j))
1683 internal_error ("validate_value_data: Loop in regno chain (%u)",
1685 if (vd->e[j].oldest_regno != i)
1686 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)",
1687 j, vd->e[j].oldest_regno);
1689 SET_HARD_REG_BIT (set, j);
1693 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1694 if (! TEST_HARD_REG_BIT (set, i)
1695 && (vd->e[i].mode != VOIDmode
1696 || vd->e[i].oldest_regno != i
1697 || vd->e[i].next_regno != INVALID_REGNUM))
1698 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)",
1699 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno,
1700 vd->e[i].next_regno);