1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it 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 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
27 #include "insn-config.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
38 #define obstack_chunk_alloc xmalloc
39 #define obstack_chunk_free free
41 #ifndef REGNO_MODE_OK_FOR_BASE_P
42 #define REGNO_MODE_OK_FOR_BASE_P(REGNO, MODE) REGNO_OK_FOR_BASE_P (REGNO)
45 #ifndef REG_MODE_OK_FOR_BASE_P
46 #define REG_MODE_OK_FOR_BASE_P(REGNO, MODE) REG_OK_FOR_BASE_P (REGNO)
49 static const char *const reg_class_names[] = REG_CLASS_NAMES;
53 struct du_chain *next_chain;
54 struct du_chain *next_use;
59 unsigned int need_caller_save_reg:1;
66 terminate_overlapping_read,
73 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));
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));
93 static struct du_chain *build_def_use PARAMS ((basic_block, HARD_REG_SET *));
94 static void dump_def_use_chain PARAMS ((struct du_chain *));
102 gcc_obstack_init (&rename_obstack);
103 first_obj = (char *) obstack_alloc (&rename_obstack, 0);
105 for (b = 0; b < n_basic_blocks; b++)
107 basic_block bb = BASIC_BLOCK (b);
108 struct du_chain *all_chains = 0;
109 HARD_REG_SET regs_used;
110 HARD_REG_SET unavailable;
111 HARD_REG_SET regs_seen;
113 CLEAR_HARD_REG_SET (regs_used);
114 CLEAR_HARD_REG_SET (unavailable);
117 fprintf (rtl_dump_file, "\nBasic block %d:\n", b);
119 all_chains = build_def_use (bb, ®s_used);
122 dump_def_use_chain (all_chains);
124 /* Available registers are not: used in the block, live at the start
125 live at the end, a register we've renamed to. */
126 REG_SET_TO_HARD_REG_SET (unavailable, bb->global_live_at_start);
127 REG_SET_TO_HARD_REG_SET (regs_seen, bb->global_live_at_end);
128 IOR_HARD_REG_SET (unavailable, regs_seen);
129 IOR_HARD_REG_SET (unavailable, regs_used);
131 /* Don't clobber traceback for noreturn functions. */
132 if (frame_pointer_needed)
134 SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM);
135 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
136 SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM);
140 CLEAR_HARD_REG_SET (regs_seen);
144 struct du_chain *this = all_chains;
145 struct du_chain *tmp, *last;
146 HARD_REG_SET this_unavailable;
147 int reg = REGNO (*this->loc), treg;
148 int nregs = HARD_REGNO_NREGS (reg, GET_MODE (*this->loc));
151 all_chains = this->next_chain;
153 /* Only rename once we've seen the reg more than once. */
154 if (! TEST_HARD_REG_BIT (regs_seen, reg))
156 SET_HARD_REG_BIT (regs_seen, reg);
160 if (fixed_regs[reg] || global_regs[reg])
163 COPY_HARD_REG_SET (this_unavailable, unavailable);
165 /* Find last entry on chain (which has the need_caller_save bit),
166 count number of uses, and narrow the set of registers we can
169 for (last = this; last->next_use; last = last->next_use)
172 IOR_COMPL_HARD_REG_SET (this_unavailable,
173 reg_class_contents[last->class]);
178 IOR_COMPL_HARD_REG_SET (this_unavailable,
179 reg_class_contents[last->class]);
181 if (last->need_caller_save_reg)
182 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
184 /* Now potential_regs is a reasonable approximation, let's
185 have a closer look at each register still in there. */
186 for (treg = 0; treg < FIRST_PSEUDO_REGISTER; treg++)
188 for (i = nregs - 1; i >= 0; --i)
189 if (TEST_HARD_REG_BIT (this_unavailable, treg+i)
190 || fixed_regs[treg+i]
191 || global_regs[treg+i]
192 /* Can't use regs which aren't saved by the prologue. */
193 || (! regs_ever_live[treg+i] && ! call_used_regs[treg+i])
194 #ifdef HARD_REGNO_RENAME_OK
195 || ! HARD_REGNO_RENAME_OK (reg+i, treg+i)
202 /* See whether it accepts all modes that occur in
203 definition and uses. */
204 for (tmp = this; tmp; tmp = tmp->next_use)
205 if (! HARD_REGNO_MODE_OK (treg, GET_MODE (*tmp->loc)))
213 fprintf (rtl_dump_file, "Register %s in insn %d",
214 reg_names[reg], INSN_UID (last->insn));
215 if (last->need_caller_save_reg)
216 fprintf (rtl_dump_file, " crosses a call");
219 if (treg == FIRST_PSEUDO_REGISTER)
222 fprintf (rtl_dump_file, "; no available registers\n");
227 for (i = nregs - 1; i >= 0; --i)
228 SET_HARD_REG_BIT (unavailable, treg+i);
229 do_replace (this, treg);
232 fprintf (rtl_dump_file, ", renamed as %s\n", reg_names[treg]);
235 obstack_free (&rename_obstack, first_obj);
238 obstack_free (&rename_obstack, NULL);
241 fputc ('\n', rtl_dump_file);
243 count_or_remove_death_notes (NULL, 1);
244 update_life_info (NULL, UPDATE_LIFE_LOCAL,
245 PROP_REG_INFO | PROP_DEATH_NOTES);
249 do_replace (chain, reg)
250 struct du_chain *chain;
255 *chain->loc = gen_rtx_REG (GET_MODE (*chain->loc), reg);
256 chain = chain->next_use;
261 static HARD_REG_SET *referenced_regs;
262 static struct du_chain *open_chains;
263 static struct du_chain *closed_chains;
266 scan_rtx_reg (insn, loc, class, action, type)
269 enum reg_class class;
270 enum scan_actions action;
275 enum machine_mode mode = GET_MODE (x);
276 int this_regno = REGNO (x);
277 int this_nregs = HARD_REGNO_NREGS (this_regno, mode);
279 if (action == note_reference)
281 while (this_nregs-- > 0)
282 SET_HARD_REG_BIT (*referenced_regs, this_regno + this_nregs);
286 if (action == mark_write)
290 struct du_chain *this = (struct du_chain *)
291 obstack_alloc (&rename_obstack, sizeof (struct du_chain));
293 this->next_chain = open_chains;
297 this->need_caller_save_reg = 0;
303 if ((type == OP_OUT && action != terminate_write)
304 || (type != OP_OUT && action == terminate_write))
307 for (p = &open_chains; *p;)
309 struct du_chain *this = *p;
310 int regno = REGNO (*this->loc);
311 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (*this->loc));
312 int exact_match = (regno == this_regno && nregs == this_nregs);
314 if (regno + nregs <= this_regno
315 || this_regno + this_nregs <= regno)
316 p = &this->next_chain;
317 else if (action == mark_read)
321 if (class == NO_REGS)
324 this = (struct du_chain *)
325 obstack_alloc (&rename_obstack, sizeof (struct du_chain));
327 this->next_chain = (*p)->next_chain;
331 this->need_caller_save_reg = 0;
335 else if (action != terminate_overlapping_read || ! exact_match)
337 struct du_chain *next = this->next_chain;
339 /* Whether the terminated chain can be used for renaming
340 depends on the action and this being an exact match.
341 In either case, we remove this element from open_chains. */
343 if ((action == terminate_dead || action == terminate_write)
346 this->next_chain = closed_chains;
347 closed_chains = this;
349 fprintf (rtl_dump_file,
350 "Closing chain %s at insn %d (%s)\n",
351 reg_names[REGNO (*this->loc)], INSN_UID (insn),
352 scan_actions_name[(int) action]);
357 fprintf (rtl_dump_file,
358 "Discarding chain %s at insn %d (%s)\n",
359 reg_names[REGNO (*this->loc)], INSN_UID (insn),
360 scan_actions_name[(int) action]);
365 p = &this->next_chain;
369 /* Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
370 BASE_REG_CLASS depending on how the register is being considered. */
373 scan_rtx_address (insn, loc, class, action, mode)
376 enum reg_class class;
377 enum scan_actions action;
378 enum machine_mode mode;
381 RTX_CODE code = GET_CODE (x);
385 if (action == mark_write)
392 rtx orig_op0 = XEXP (x, 0);
393 rtx orig_op1 = XEXP (x, 1);
394 RTX_CODE code0 = GET_CODE (orig_op0);
395 RTX_CODE code1 = GET_CODE (orig_op1);
401 if (GET_CODE (op0) == SUBREG)
403 op0 = SUBREG_REG (op0);
404 code0 = GET_CODE (op0);
407 if (GET_CODE (op1) == SUBREG)
409 op1 = SUBREG_REG (op1);
410 code1 = GET_CODE (op1);
413 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
414 || code0 == ZERO_EXTEND || code1 == MEM)
419 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
420 || code1 == ZERO_EXTEND || code0 == MEM)
425 else if (code0 == CONST_INT || code0 == CONST
426 || code0 == SYMBOL_REF || code0 == LABEL_REF)
428 else if (code1 == CONST_INT || code1 == CONST
429 || code1 == SYMBOL_REF || code1 == LABEL_REF)
431 else if (code0 == REG && code1 == REG)
435 if (REG_OK_FOR_INDEX_P (op0)
436 && REG_MODE_OK_FOR_BASE_P (op1, mode))
438 else if (REG_OK_FOR_INDEX_P (op1)
439 && REG_MODE_OK_FOR_BASE_P (op0, mode))
441 else if (REG_MODE_OK_FOR_BASE_P (op1, mode))
443 else if (REG_MODE_OK_FOR_BASE_P (op0, mode))
445 else if (REG_OK_FOR_INDEX_P (op1))
450 locI = &XEXP (x, index_op);
451 locB = &XEXP (x, !index_op);
453 else if (code0 == REG)
458 else if (code1 == REG)
465 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
467 scan_rtx_address (insn, locB, BASE_REG_CLASS, action, mode);
478 /* If the target doesn't claim to handle autoinc, this must be
479 something special, like a stack push. Kill this chain. */
480 action = terminate_all_read;
485 scan_rtx_address (insn, &XEXP (x, 0), BASE_REG_CLASS, action,
490 scan_rtx_reg (insn, loc, class, action, OP_IN);
497 fmt = GET_RTX_FORMAT (code);
498 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
501 scan_rtx_address (insn, &XEXP (x, i), class, action, mode);
502 else if (fmt[i] == 'E')
503 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
504 scan_rtx_address (insn, &XVECEXP (x, i, j), class, action, mode);
509 scan_rtx (insn, loc, class, action, type)
512 enum reg_class class;
513 enum scan_actions action;
518 enum rtx_code code = GET_CODE (x);
534 scan_rtx_reg (insn, loc, class, action, type);
538 scan_rtx_address (insn, &XEXP (x, 0), BASE_REG_CLASS, action,
543 scan_rtx (insn, &SET_SRC (x), class, action, OP_IN);
544 scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT);
547 case STRICT_LOW_PART:
548 scan_rtx (insn, &XEXP (x, 0), class, action, OP_INOUT);
553 scan_rtx (insn, &XEXP (x, 0), class, action,
554 type == OP_IN ? OP_IN : OP_INOUT);
555 scan_rtx (insn, &XEXP (x, 1), class, action, OP_IN);
556 scan_rtx (insn, &XEXP (x, 2), class, action, OP_IN);
565 /* Should only happen inside MEM. */
569 scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT);
573 scan_rtx (insn, &XEXP (x, 0), class, action, type);
575 scan_rtx (insn, &XEXP (x, 1), class, action, type);
582 fmt = GET_RTX_FORMAT (code);
583 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
586 scan_rtx (insn, &XEXP (x, i), class, action, type);
587 else if (fmt[i] == 'E')
588 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
589 scan_rtx (insn, &XVECEXP (x, i, j), class, action, type);
593 /* Build def/use chain */
595 static struct du_chain *
596 build_def_use (bb, regs_used)
598 HARD_REG_SET *regs_used;
602 open_chains = closed_chains = NULL;
603 referenced_regs = regs_used;
605 for (insn = bb->head; ; insn = NEXT_INSN (insn))
611 rtx old_operands[MAX_RECOG_OPERANDS];
612 rtx old_dups[MAX_DUP_OPERANDS];
617 /* Record all mentioned registers in regs_used. */
618 scan_rtx (insn, &PATTERN (insn), NO_REGS, note_reference, OP_IN);
620 /* Process the insn, determining its effect on the def-use
621 chains. We perform the following steps with the register
622 references in the insn:
623 (1) Any read that overlaps an open chain, but doesn't exactly
624 match, causes that chain to be closed. We can't deal
626 (2) Any read outside an operand causes any chain it overlaps
627 with to be closed, since we can't replace it.
628 (3) Any read inside an operand is added if there's already
629 an open chain for it.
630 (4) For any REG_DEAD note we find, close open chains that
632 (5) For any write we find, close open chains that overlap it.
633 (6) For any write we find in an operand, make a new chain.
634 (7) For any REG_UNUSED, close any chains we just opened. */
637 constrain_operands (1);
638 preprocess_constraints ();
639 alt = which_alternative;
640 n_ops = recog_data.n_operands;
642 /* Simplify the code below by rewriting things to reflect
643 matching constraints. Also promote OP_OUT to OP_INOUT
644 in predicated instructions. */
646 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
647 for (i = 0; i < n_ops; ++i)
649 int matches = recog_op_alt[i][alt].matches;
651 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class;
652 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
653 || (predicated && recog_data.operand_type[i] == OP_OUT))
654 recog_data.operand_type[i] = OP_INOUT;
657 /* Step 1: Close chains for which we have overlapping reads. */
658 for (i = 0; i < n_ops; i++)
659 scan_rtx (insn, recog_data.operand_loc[i],
660 NO_REGS, terminate_overlapping_read,
661 recog_data.operand_type[i]);
663 /* Step 2: Close chains for which we have reads outside operands.
664 We do this by munging all operands into CC0, and closing
665 everything remaining. */
667 for (i = 0; i < n_ops; i++)
669 old_operands[i] = recog_data.operand[i];
670 /* Don't squash match_operator or match_parallel here, since
671 we don't know that all of the contained registers are
672 reachable by proper operands. */
673 if (recog_data.constraints[i][0] == '\0')
675 *recog_data.operand_loc[i] = cc0_rtx;
677 for (i = 0; i < recog_data.n_dups; i++)
679 old_dups[i] = *recog_data.dup_loc[i];
680 *recog_data.dup_loc[i] = cc0_rtx;
683 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read, OP_IN);
685 for (i = 0; i < recog_data.n_dups; i++)
686 *recog_data.dup_loc[i] = old_dups[i];
687 for (i = 0; i < n_ops; i++)
688 *recog_data.operand_loc[i] = old_operands[i];
690 /* Step 2B: Can't rename function call argument registers. */
691 if (GET_CODE (insn) == CALL_INSN && CALL_INSN_FUNCTION_USAGE (insn))
692 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
693 NO_REGS, terminate_all_read, OP_IN);
695 /* Step 3: Append to chains for reads inside operands. */
696 for (i = 0; i < n_ops + recog_data.n_dups; i++)
698 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
699 rtx *loc = (i < n_ops
700 ? recog_data.operand_loc[opn]
701 : recog_data.dup_loc[i - n_ops]);
702 enum reg_class class = recog_op_alt[opn][alt].class;
703 enum op_type type = recog_data.operand_type[opn];
705 /* Don't scan match_operand here, since we've no reg class
706 information to pass down. Any operands that we could
707 substitute in will be represented elsewhere. */
708 if (recog_data.constraints[opn][0] == '\0')
711 if (recog_op_alt[opn][alt].is_address)
712 scan_rtx_address (insn, loc, class, mark_read, VOIDmode);
714 scan_rtx (insn, loc, class, mark_read, type);
717 /* Step 4: Close chains for registers that die here.
718 Also record updates for REG_INC notes. */
719 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
721 if (REG_NOTE_KIND (note) == REG_DEAD)
722 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, OP_IN);
723 else if (REG_NOTE_KIND (note) == REG_INC)
724 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read, OP_INOUT);
727 /* Step 4B: If this is a call, any chain live at this point
728 requires a caller-saved reg. */
729 if (GET_CODE (insn) == CALL_INSN)
732 for (p = open_chains; p; p = p->next_chain)
735 for (p2 = p; p2->next_use; p2 = p2->next_use)
737 p2->need_caller_save_reg = 1;
741 /* Step 5: Close open chains that overlap writes. Similar to
742 step 2, we hide in-out operands, since we do not want to
743 close these chains. */
745 for (i = 0; i < n_ops; i++)
747 old_operands[i] = recog_data.operand[i];
748 if (recog_data.operand_type[i] == OP_INOUT)
749 *recog_data.operand_loc[i] = cc0_rtx;
751 for (i = 0; i < recog_data.n_dups; i++)
753 int opn = recog_data.dup_num[i];
754 old_dups[i] = *recog_data.dup_loc[i];
755 if (recog_data.operand_type[opn] == OP_INOUT)
756 *recog_data.dup_loc[i] = cc0_rtx;
759 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN);
761 for (i = 0; i < recog_data.n_dups; i++)
762 *recog_data.dup_loc[i] = old_dups[i];
763 for (i = 0; i < n_ops; i++)
764 *recog_data.operand_loc[i] = old_operands[i];
766 /* Step 6: Begin new chains for writes inside operands. */
767 /* ??? Many targets have output constraints on the SET_DEST
768 of a call insn, which is stupid, since these are certainly
769 ABI defined hard registers. Don't change calls at all. */
770 if (GET_CODE (insn) != CALL_INSN)
771 for (i = 0; i < n_ops + recog_data.n_dups; i++)
773 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
774 rtx *loc = (i < n_ops
775 ? recog_data.operand_loc[opn]
776 : recog_data.dup_loc[i - n_ops]);
777 enum reg_class class = recog_op_alt[opn][alt].class;
779 if (recog_data.operand_type[opn] == OP_OUT)
780 scan_rtx (insn, loc, class, mark_write, OP_OUT);
783 /* Step 7: Close chains for registers that were never
785 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
786 if (REG_NOTE_KIND (note) == REG_UNUSED)
787 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, OP_IN);
793 /* Since we close every chain when we find a REG_DEAD note, anything that
794 is still open lives past the basic block, so it can't be renamed. */
795 return closed_chains;
798 /* Dump all def/use chains in CHAINS to RTL_DUMP_FILE. They are
799 printed in reverse order as that's how we build them. */
802 dump_def_use_chain (chains)
803 struct du_chain *chains;
807 struct du_chain *this = chains;
808 int r = REGNO (*this->loc);
809 int nregs = HARD_REGNO_NREGS (r, GET_MODE (*this->loc));
810 fprintf (rtl_dump_file, "Register %s (%d):", reg_names[r], nregs);
813 fprintf (rtl_dump_file, " %d [%s]", INSN_UID (this->insn),
814 reg_class_names[this->class]);
815 this = this->next_use;
817 fprintf (rtl_dump_file, "\n");
818 chains = chains->next_chain;