1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
27 #include "insn-config.h"
29 #include "addresses.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
40 #include "tree-pass.h"
43 /* We keep linked lists of DU_HEAD structures, each of which describes
44 a chain of occurrences of a reg. */
48 struct du_head *next_chain;
49 /* The first and last elements of this chain. */
50 struct du_chain *first, *last;
51 /* Describes the register being tracked. */
52 unsigned regno, nregs;
54 /* A unique id to be used as an index into the conflicts bitmaps. */
56 /* A bitmap to record conflicts with other chains. */
57 bitmap_head conflicts;
58 /* Conflicts with untracked hard registers. */
59 HARD_REG_SET hard_conflicts;
61 /* Nonzero if the chain is finished; zero if it is still open. */
62 unsigned int terminated:1;
63 /* Nonzero if the chain crosses a call. */
64 unsigned int need_caller_save_reg:1;
65 /* Nonzero if the register is used in a way that prevents renaming,
66 such as the SET_DEST of a CALL_INSN or an asm operand that used
67 to be a hard register. */
68 unsigned int cannot_rename:1;
71 /* This struct describes a single occurrence of a register. */
74 /* Links to the next occurrence of the register. */
75 struct du_chain *next_use;
77 /* The insn where the register appears. */
79 /* The location inside the insn. */
81 /* The register class required by the insn at this location. */
82 ENUM_BITFIELD(reg_class) cl : 16;
92 /* mark_access is for marking the destination regs in
93 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
94 note is updated properly. */
98 static const char * const scan_actions_name[] =
108 static struct obstack rename_obstack;
110 static void do_replace (struct du_head *, int);
111 static void scan_rtx_reg (rtx, rtx *, enum reg_class,
112 enum scan_actions, enum op_type);
113 static void scan_rtx_address (rtx, rtx *, enum reg_class,
114 enum scan_actions, enum machine_mode);
115 static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
117 static struct du_head *build_def_use (basic_block);
118 static void dump_def_use_chain (struct du_head *);
120 typedef struct du_head *du_head_p;
121 DEF_VEC_P (du_head_p);
122 DEF_VEC_ALLOC_P (du_head_p, heap);
123 static VEC(du_head_p, heap) *id_to_chain;
126 free_chain_data (void)
130 for (i = 0; VEC_iterate(du_head_p, id_to_chain, i, ptr); i++)
131 bitmap_clear (&ptr->conflicts);
133 VEC_free (du_head_p, heap, id_to_chain);
136 /* For a def-use chain HEAD, find which registers overlap its lifetime and
137 set the corresponding bits in *PSET. */
140 merge_overlapping_regs (HARD_REG_SET *pset, struct du_head *head)
144 IOR_HARD_REG_SET (*pset, head->hard_conflicts);
145 EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi)
147 du_head_p other = VEC_index (du_head_p, id_to_chain, i);
148 unsigned j = other->nregs;
150 SET_HARD_REG_BIT (*pset, other->regno + j);
154 /* Perform register renaming on the current function. */
157 regrename_optimize (void)
159 int tick[FIRST_PSEUDO_REGISTER];
164 df_set_flags (DF_LR_RUN_DCE);
165 df_note_add_problem ();
167 df_set_flags (DF_DEFER_INSN_RESCAN);
169 memset (tick, 0, sizeof tick);
171 gcc_obstack_init (&rename_obstack);
172 first_obj = XOBNEWVAR (&rename_obstack, char, 0);
176 struct du_head *all_chains = 0;
177 HARD_REG_SET unavailable;
178 HARD_REG_SET regs_seen;
180 id_to_chain = VEC_alloc (du_head_p, heap, 0);
182 CLEAR_HARD_REG_SET (unavailable);
185 fprintf (dump_file, "\nBasic block %d:\n", bb->index);
187 all_chains = build_def_use (bb);
190 dump_def_use_chain (all_chains);
192 CLEAR_HARD_REG_SET (unavailable);
193 /* Don't clobber traceback for noreturn functions. */
194 if (frame_pointer_needed)
196 add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
197 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
198 add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
202 CLEAR_HARD_REG_SET (regs_seen);
205 int new_reg, best_new_reg, best_nregs;
207 struct du_head *this_head = all_chains;
208 struct du_chain *tmp;
209 HARD_REG_SET this_unavailable;
210 int reg = this_head->regno;
213 all_chains = this_head->next_chain;
215 if (this_head->cannot_rename)
219 best_nregs = this_head->nregs;
221 #if 0 /* This just disables optimization opportunities. */
222 /* Only rename once we've seen the reg more than once. */
223 if (! TEST_HARD_REG_BIT (regs_seen, reg))
225 SET_HARD_REG_BIT (regs_seen, reg);
230 if (fixed_regs[reg] || global_regs[reg]
231 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
232 || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
234 || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
239 COPY_HARD_REG_SET (this_unavailable, unavailable);
241 /* Count number of uses, and narrow the set of registers we can
244 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
246 if (DEBUG_INSN_P (tmp->insn))
249 IOR_COMPL_HARD_REG_SET (this_unavailable,
250 reg_class_contents[tmp->cl]);
256 if (this_head->need_caller_save_reg)
257 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
259 merge_overlapping_regs (&this_unavailable, this_head);
261 /* Now potential_regs is a reasonable approximation, let's
262 have a closer look at each register still in there. */
263 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
265 enum machine_mode mode = GET_MODE (*this_head->first->loc);
266 int nregs = hard_regno_nregs[new_reg][mode];
268 for (i = nregs - 1; i >= 0; --i)
269 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
270 || fixed_regs[new_reg + i]
271 || global_regs[new_reg + i]
272 /* Can't use regs which aren't saved by the prologue. */
273 || (! df_regs_ever_live_p (new_reg + i)
274 && ! call_used_regs[new_reg + i])
275 #ifdef LEAF_REGISTERS
276 /* We can't use a non-leaf register if we're in a
278 || (current_function_is_leaf
279 && !LEAF_REGISTERS[new_reg + i])
281 #ifdef HARD_REGNO_RENAME_OK
282 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
289 /* See whether it accepts all modes that occur in
290 definition and uses. */
291 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
292 if ((! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
293 && ! DEBUG_INSN_P (tmp->insn))
294 || (this_head->need_caller_save_reg
295 && ! (HARD_REGNO_CALL_PART_CLOBBERED
296 (reg, GET_MODE (*tmp->loc)))
297 && (HARD_REGNO_CALL_PART_CLOBBERED
298 (new_reg, GET_MODE (*tmp->loc)))))
302 if (tick[best_new_reg] > tick[new_reg])
304 best_new_reg = new_reg;
312 fprintf (dump_file, "Register %s in insn %d",
313 reg_names[reg], INSN_UID (this_head->first->insn));
314 if (this_head->need_caller_save_reg)
315 fprintf (dump_file, " crosses a call");
318 if (best_new_reg == reg)
320 tick[reg] = ++this_tick;
322 fprintf (dump_file, "; no available better choice\n");
327 fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
329 do_replace (this_head, best_new_reg);
330 this_head->regno = best_new_reg;
331 this_head->nregs = best_nregs;
332 tick[best_new_reg] = ++this_tick;
333 df_set_regs_ever_live (best_new_reg, true);
337 obstack_free (&rename_obstack, first_obj);
340 obstack_free (&rename_obstack, NULL);
343 fputc ('\n', dump_file);
349 do_replace (struct du_head *head, int reg)
351 struct du_chain *chain;
352 unsigned int base_regno = head->regno;
353 bool found_note = false;
355 gcc_assert (! DEBUG_INSN_P (head->first->insn));
357 for (chain = head->first; chain; chain = chain->next_use)
359 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
360 struct reg_attrs *attr = REG_ATTRS (*chain->loc);
361 int reg_ptr = REG_POINTER (*chain->loc);
363 if (DEBUG_INSN_P (chain->insn) && REGNO (*chain->loc) != base_regno)
364 INSN_VAR_LOCATION_LOC (chain->insn) = gen_rtx_UNKNOWN_VAR_LOC ();
369 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
370 if (regno >= FIRST_PSEUDO_REGISTER)
371 ORIGINAL_REGNO (*chain->loc) = regno;
372 REG_ATTRS (*chain->loc) = attr;
373 REG_POINTER (*chain->loc) = reg_ptr;
375 for (note = REG_NOTES (chain->insn); note; note = XEXP (note, 1))
377 enum reg_note kind = REG_NOTE_KIND (note);
378 if (kind == REG_DEAD || kind == REG_UNUSED)
380 rtx reg = XEXP (note, 0);
381 gcc_assert (HARD_REGISTER_P (reg));
383 if (REGNO (reg) == base_regno)
387 && reg_set_p (*chain->loc, chain->insn))
388 remove_note (chain->insn, note);
390 XEXP (note, 0) = *chain->loc;
397 df_insn_rescan (chain->insn);
401 /* If the chain's first insn is the same as the last, we should have
402 found a REG_UNUSED note. */
403 gcc_assert (head->first->insn != head->last->insn);
404 if (!reg_set_p (*head->last->loc, head->last->insn))
405 add_reg_note (head->last->insn, REG_DEAD, *head->last->loc);
410 /* Walk all chains starting with CHAINS and record that they conflict with
411 another chain whose id is ID. */
414 mark_conflict (struct du_head *chains, unsigned id)
418 bitmap_set_bit (&chains->conflicts, id);
419 chains = chains->next_chain;
423 /* True if we found a register with a size mismatch, which means that we
424 can't track its lifetime accurately. If so, we abort the current block
426 static bool fail_current_block;
428 /* The id to be given to the next opened chain. */
429 static unsigned current_id;
431 /* List of currently open chains, and closed chains that can be renamed. */
432 static struct du_head *open_chains;
433 static struct du_head *closed_chains;
435 /* Conflict bitmaps, tracking the live chains and the live hard registers.
436 The bits set in open_chains_set always match the list found in
438 static bitmap_head open_chains_set;
439 static HARD_REG_SET live_hard_regs;
441 /* Called through note_stores. DATA points to a rtx_code, either SET or
442 CLOBBER, which tells us which kind of rtx to look at. If we have a
443 match, record the set register in live_hard_regs and in the hard_conflicts
444 bitmap of open chains. */
447 note_sets_clobbers (rtx x, const_rtx set, void *data)
449 enum rtx_code code = *(enum rtx_code *)data;
450 struct du_head *chain;
452 if (GET_CODE (x) == SUBREG)
454 if (!REG_P (x) || GET_CODE (set) != code)
456 /* There must not be pseudos at this point. */
457 gcc_assert (HARD_REGISTER_P (x));
458 add_to_hard_reg_set (&live_hard_regs, GET_MODE (x), REGNO (x));
459 for (chain = open_chains; chain; chain = chain->next_chain)
460 add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x));
464 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
469 enum machine_mode mode = GET_MODE (x);
470 unsigned this_regno = REGNO (x);
471 unsigned this_nregs = hard_regno_nregs[this_regno][mode];
473 if (action == mark_write)
477 struct du_head *head = XOBNEW (&rename_obstack, struct du_head);
478 struct du_chain *this_du = XOBNEW (&rename_obstack, struct du_chain);
481 head->next_chain = open_chains;
483 head->first = head->last = this_du;
484 head->regno = this_regno;
485 head->nregs = this_nregs;
486 head->need_caller_save_reg = 0;
487 head->cannot_rename = 0;
488 head->terminated = 0;
490 VEC_safe_push (du_head_p, heap, id_to_chain, head);
491 head->id = current_id++;
493 bitmap_initialize (&head->conflicts, &bitmap_default_obstack);
494 bitmap_copy (&head->conflicts, &open_chains_set);
495 mark_conflict (open_chains, head->id);
497 /* Since we're tracking this as a chain now, remove it from the
498 list of conflicting live hard registers. */
501 CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
503 COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs);
504 bitmap_set_bit (&open_chains_set, head->id);
508 this_du->next_use = 0;
510 this_du->insn = insn;
515 "Creating chain %s (%d) at insn %d (%s)\n",
516 reg_names[head->regno], head->id, INSN_UID (insn),
517 scan_actions_name[(int) action]);
522 if ((type == OP_OUT) != (action == terminate_write || action == mark_access))
525 for (p = &open_chains; *p;)
527 struct du_head *head = *p;
528 struct du_head *next = head->next_chain;
529 int exact_match = (head->regno == this_regno
530 && head->nregs == this_nregs);
531 int superset = (this_regno <= head->regno
532 && this_regno + this_nregs >= head->regno + head->nregs);
535 || head->regno + head->nregs <= this_regno
536 || this_regno + this_nregs <= head->regno)
538 p = &head->next_chain;
542 if (action == mark_read || action == mark_access)
544 /* ??? Class NO_REGS can happen if the md file makes use of
545 EXTRA_CONSTRAINTS to match registers. Which is arguably
546 wrong, but there we are. */
548 if (cl == NO_REGS || (!exact_match && !DEBUG_INSN_P (insn)))
552 "Cannot rename chain %s (%d) at insn %d (%s)\n",
553 reg_names[head->regno], head->id, INSN_UID (insn),
554 scan_actions_name[(int) action]);
555 head->cannot_rename = 1;
559 struct du_chain *this_du;
560 this_du = XOBNEW (&rename_obstack, struct du_chain);
561 this_du->next_use = 0;
563 this_du->insn = insn;
565 head->last->next_use = this_du;
566 head->last = this_du;
569 /* Avoid adding the same location in a DEBUG_INSN multiple times,
570 which could happen with non-exact overlap. */
571 if (DEBUG_INSN_P (insn))
573 /* Otherwise, find any other chains that do not match exactly;
574 ensure they all get marked unrenamable. */
575 p = &head->next_chain;
579 /* Whether the terminated chain can be used for renaming
580 depends on the action and this being an exact match.
581 In either case, we remove this element from open_chains. */
583 if ((action == terminate_dead || action == terminate_write)
586 head->terminated = 1;
587 head->next_chain = closed_chains;
588 closed_chains = head;
589 bitmap_clear_bit (&open_chains_set, head->id);
593 "Closing chain %s (%d) at insn %d (%s)\n",
594 reg_names[head->regno], head->id, INSN_UID (insn),
595 scan_actions_name[(int) action]);
597 else if (action == terminate_dead || action == terminate_write)
599 /* In this case, tracking liveness gets too hard. Fail the
600 entire basic block. */
603 "Failing basic block due to unhandled overlap\n");
604 fail_current_block = true;
609 head->cannot_rename = 1;
612 "Cannot rename chain %s (%d) at insn %d (%s)\n",
613 reg_names[head->regno], head->id, INSN_UID (insn),
614 scan_actions_name[(int) action]);
615 p = &head->next_chain;
620 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
621 BASE_REG_CLASS depending on how the register is being considered. */
624 scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl,
625 enum scan_actions action, enum machine_mode mode)
628 RTX_CODE code = GET_CODE (x);
632 if (action == mark_write || action == mark_access)
639 rtx orig_op0 = XEXP (x, 0);
640 rtx orig_op1 = XEXP (x, 1);
641 RTX_CODE code0 = GET_CODE (orig_op0);
642 RTX_CODE code1 = GET_CODE (orig_op1);
647 enum rtx_code index_code = SCRATCH;
649 if (GET_CODE (op0) == SUBREG)
651 op0 = SUBREG_REG (op0);
652 code0 = GET_CODE (op0);
655 if (GET_CODE (op1) == SUBREG)
657 op1 = SUBREG_REG (op1);
658 code1 = GET_CODE (op1);
661 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
662 || code0 == ZERO_EXTEND || code1 == MEM)
666 index_code = GET_CODE (*locI);
668 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
669 || code1 == ZERO_EXTEND || code0 == MEM)
673 index_code = GET_CODE (*locI);
675 else if (code0 == CONST_INT || code0 == CONST
676 || code0 == SYMBOL_REF || code0 == LABEL_REF)
679 index_code = GET_CODE (XEXP (x, 0));
681 else if (code1 == CONST_INT || code1 == CONST
682 || code1 == SYMBOL_REF || code1 == LABEL_REF)
685 index_code = GET_CODE (XEXP (x, 1));
687 else if (code0 == REG && code1 == REG)
690 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
692 if (REGNO_OK_FOR_INDEX_P (regno1)
693 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
695 else if (REGNO_OK_FOR_INDEX_P (regno0)
696 && regno_ok_for_base_p (regno1, mode, PLUS, REG))
698 else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
699 || REGNO_OK_FOR_INDEX_P (regno1))
701 else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
706 locI = &XEXP (x, index_op);
707 locB = &XEXP (x, !index_op);
708 index_code = GET_CODE (*locI);
710 else if (code0 == REG)
714 index_code = GET_CODE (*locI);
716 else if (code1 == REG)
720 index_code = GET_CODE (*locI);
724 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
726 scan_rtx_address (insn, locB, base_reg_class (mode, PLUS, index_code),
739 /* If the target doesn't claim to handle autoinc, this must be
740 something special, like a stack push. Kill this chain. */
741 action = mark_all_read;
746 scan_rtx_address (insn, &XEXP (x, 0),
747 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
752 scan_rtx_reg (insn, loc, cl, action, OP_IN);
759 fmt = GET_RTX_FORMAT (code);
760 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
763 scan_rtx_address (insn, &XEXP (x, i), cl, action, mode);
764 else if (fmt[i] == 'E')
765 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
766 scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode);
771 scan_rtx (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
776 enum rtx_code code = GET_CODE (x);
794 scan_rtx_reg (insn, loc, cl, action, type);
798 scan_rtx_address (insn, &XEXP (x, 0),
799 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
804 scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN);
805 scan_rtx (insn, &SET_DEST (x), cl, action,
806 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT);
809 case STRICT_LOW_PART:
810 scan_rtx (insn, &XEXP (x, 0), cl, action, OP_INOUT);
815 scan_rtx (insn, &XEXP (x, 0), cl, action,
816 type == OP_IN ? OP_IN : OP_INOUT);
817 scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN);
818 scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN);
827 /* Should only happen inside MEM. */
831 scan_rtx (insn, &SET_DEST (x), cl, action,
832 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT);
836 scan_rtx (insn, &XEXP (x, 0), cl, action, type);
838 scan_rtx (insn, &XEXP (x, 1), cl, action, type);
845 fmt = GET_RTX_FORMAT (code);
846 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
849 scan_rtx (insn, &XEXP (x, i), cl, action, type);
850 else if (fmt[i] == 'E')
851 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
852 scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type);
856 /* Hide operands of the current insn (of which there are N_OPS) by
857 substituting cc0 for them.
858 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
859 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
860 and earlyclobbers. */
863 hide_operands (int n_ops, rtx *old_operands, rtx *old_dups,
864 bool inout_and_ec_only)
867 int alt = which_alternative;
868 for (i = 0; i < n_ops; i++)
870 old_operands[i] = recog_data.operand[i];
871 /* Don't squash match_operator or match_parallel here, since
872 we don't know that all of the contained registers are
873 reachable by proper operands. */
874 if (recog_data.constraints[i][0] == '\0')
876 if (!inout_and_ec_only || recog_data.operand_type[i] == OP_INOUT
877 || recog_op_alt[i][alt].earlyclobber)
878 *recog_data.operand_loc[i] = cc0_rtx;
880 for (i = 0; i < recog_data.n_dups; i++)
882 int opn = recog_data.dup_num[i];
883 old_dups[i] = *recog_data.dup_loc[i];
884 if (!inout_and_ec_only || recog_data.operand_type[opn] == OP_INOUT
885 || recog_op_alt[opn][alt].earlyclobber)
886 *recog_data.dup_loc[i] = cc0_rtx;
890 /* Undo the substitution performed by hide_operands. INSN is the insn we
891 are processing; the arguments are the same as in hide_operands. */
894 restore_operands (rtx insn, int n_ops, rtx *old_operands, rtx *old_dups)
897 for (i = 0; i < recog_data.n_dups; i++)
898 *recog_data.dup_loc[i] = old_dups[i];
899 for (i = 0; i < n_ops; i++)
900 *recog_data.operand_loc[i] = old_operands[i];
901 if (recog_data.n_dups)
902 df_insn_rescan (insn);
905 /* For each output operand of INSN, call scan_rtx to create a new
906 open chain. Do this only for normal or earlyclobber outputs,
907 depending on EARLYCLOBBER. */
910 record_out_operands (rtx insn, bool earlyclobber)
912 int n_ops = recog_data.n_operands;
913 int alt = which_alternative;
917 for (i = 0; i < n_ops + recog_data.n_dups; i++)
919 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
920 rtx *loc = (i < n_ops
921 ? recog_data.operand_loc[opn]
922 : recog_data.dup_loc[i - n_ops]);
924 enum reg_class cl = recog_op_alt[opn][alt].cl;
926 struct du_head *prev_open;
928 if (recog_data.operand_type[opn] != OP_OUT
929 || recog_op_alt[opn][alt].earlyclobber != earlyclobber)
932 prev_open = open_chains;
933 scan_rtx (insn, loc, cl, mark_write, OP_OUT);
935 /* ??? Many targets have output constraints on the SET_DEST
936 of a call insn, which is stupid, since these are certainly
937 ABI defined hard registers. For these, and for asm operands
938 that originally referenced hard registers, we must record that
939 the chain cannot be renamed. */
941 || (asm_noperands (PATTERN (insn)) > 0
943 && REGNO (op) == ORIGINAL_REGNO (op)))
945 if (prev_open != open_chains)
946 open_chains->cannot_rename = 1;
951 /* Build def/use chain. */
953 static struct du_head *
954 build_def_use (basic_block bb)
959 open_chains = closed_chains = NULL;
961 fail_current_block = false;
964 bitmap_initialize (&open_chains_set, &bitmap_default_obstack);
965 REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb));
966 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
968 df_ref def = *def_rec;
969 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
970 SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def));
973 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
975 if (NONDEBUG_INSN_P (insn))
979 rtx old_operands[MAX_RECOG_OPERANDS];
980 rtx old_dups[MAX_DUP_OPERANDS];
984 enum rtx_code set_code = SET;
985 enum rtx_code clobber_code = CLOBBER;
987 /* Process the insn, determining its effect on the def-use
988 chains and live hard registers. We perform the following
989 steps with the register references in the insn, simulating
991 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
992 by creating chains and marking hard regs live.
993 (2) Any read outside an operand causes any chain it overlaps
994 with to be marked unrenamable.
995 (3) Any read inside an operand is added if there's already
996 an open chain for it.
997 (4) For any REG_DEAD note we find, close open chains that
999 (5) For any non-earlyclobber write we find, close open chains
1001 (6) For any non-earlyclobber write we find in an operand, make
1002 a new chain or mark the hard register as live.
1003 (7) For any REG_UNUSED, close any chains we just opened.
1005 We cannot deal with situations where we track a reg in one mode
1006 and see a reference in another mode; these will cause the chain
1007 to be marked unrenamable or even cause us to abort the entire
1010 icode = recog_memoized (insn);
1011 extract_insn (insn);
1012 if (! constrain_operands (1))
1013 fatal_insn_not_found (insn);
1014 preprocess_constraints ();
1015 alt = which_alternative;
1016 n_ops = recog_data.n_operands;
1018 /* Simplify the code below by rewriting things to reflect
1019 matching constraints. Also promote OP_OUT to OP_INOUT
1020 in predicated instructions. */
1022 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1023 for (i = 0; i < n_ops; ++i)
1025 int matches = recog_op_alt[i][alt].matches;
1027 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
1028 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
1029 || (predicated && recog_data.operand_type[i] == OP_OUT))
1031 recog_data.operand_type[i] = OP_INOUT;
1033 && (GET_MODE_SIZE (recog_data.operand_mode[i])
1034 != GET_MODE_SIZE (recog_data.operand_mode[matches])))
1035 fail_current_block = true;
1039 if (fail_current_block)
1042 /* Step 1a: Mark hard registers that are clobbered in this insn,
1043 outside an operand, as live. */
1044 hide_operands (n_ops, old_operands, old_dups, false);
1045 note_stores (PATTERN (insn), note_sets_clobbers, &clobber_code);
1046 restore_operands (insn, n_ops, old_operands, old_dups);
1048 /* Step 1b: Begin new chains for earlyclobbered writes inside
1050 record_out_operands (insn, true);
1052 /* Step 2: Mark chains for which we have reads outside operands
1054 We do this by munging all operands into CC0, and closing
1055 everything remaining. */
1057 hide_operands (n_ops, old_operands, old_dups, false);
1058 scan_rtx (insn, &PATTERN (insn), NO_REGS, mark_all_read, OP_IN);
1059 restore_operands (insn, n_ops, old_operands, old_dups);
1061 /* Step 2B: Can't rename function call argument registers. */
1062 if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
1063 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
1064 NO_REGS, mark_all_read, OP_IN);
1066 /* Step 2C: Can't rename asm operands that were originally
1068 if (asm_noperands (PATTERN (insn)) > 0)
1069 for (i = 0; i < n_ops; i++)
1071 rtx *loc = recog_data.operand_loc[i];
1075 && REGNO (op) == ORIGINAL_REGNO (op)
1076 && (recog_data.operand_type[i] == OP_IN
1077 || recog_data.operand_type[i] == OP_INOUT))
1078 scan_rtx (insn, loc, NO_REGS, mark_all_read, OP_IN);
1081 /* Step 3: Append to chains for reads inside operands. */
1082 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1084 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1085 rtx *loc = (i < n_ops
1086 ? recog_data.operand_loc[opn]
1087 : recog_data.dup_loc[i - n_ops]);
1088 enum reg_class cl = recog_op_alt[opn][alt].cl;
1089 enum op_type type = recog_data.operand_type[opn];
1091 /* Don't scan match_operand here, since we've no reg class
1092 information to pass down. Any operands that we could
1093 substitute in will be represented elsewhere. */
1094 if (recog_data.constraints[opn][0] == '\0')
1097 if (recog_op_alt[opn][alt].is_address)
1098 scan_rtx_address (insn, loc, cl, mark_read, VOIDmode);
1100 scan_rtx (insn, loc, cl, mark_read, type);
1103 /* Step 3B: Record updates for regs in REG_INC notes, and
1104 source regs in REG_FRAME_RELATED_EXPR notes. */
1105 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1106 if (REG_NOTE_KIND (note) == REG_INC
1107 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1108 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
1111 /* Step 4: Close chains for registers that die here. */
1112 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1113 if (REG_NOTE_KIND (note) == REG_DEAD)
1115 remove_from_hard_reg_set (&live_hard_regs,
1116 GET_MODE (XEXP (note, 0)),
1117 REGNO (XEXP (note, 0)));
1118 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1122 /* Step 4B: If this is a call, any chain live at this point
1123 requires a caller-saved reg. */
1127 for (p = open_chains; p; p = p->next_chain)
1128 p->need_caller_save_reg = 1;
1131 /* Step 5: Close open chains that overlap writes. Similar to
1132 step 2, we hide in-out operands, since we do not want to
1133 close these chains. We also hide earlyclobber operands,
1134 since we've opened chains for them in step 1, and earlier
1135 chains they would overlap with must have been closed at
1136 the previous insn at the latest, as such operands cannot
1137 possibly overlap with any input operands. */
1139 hide_operands (n_ops, old_operands, old_dups, true);
1140 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN);
1141 restore_operands (insn, n_ops, old_operands, old_dups);
1143 /* Step 6a: Mark hard registers that are set in this insn,
1144 outside an operand, as live. */
1145 hide_operands (n_ops, old_operands, old_dups, false);
1146 note_stores (PATTERN (insn), note_sets_clobbers, &set_code);
1147 restore_operands (insn, n_ops, old_operands, old_dups);
1149 /* Step 6b: Begin new chains for writes inside operands. */
1150 record_out_operands (insn, false);
1152 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1153 notes for update. */
1154 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1155 if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1156 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
1159 /* Step 7: Close chains for registers that were never
1160 really used here. */
1161 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1162 if (REG_NOTE_KIND (note) == REG_UNUSED)
1164 remove_from_hard_reg_set (&live_hard_regs,
1165 GET_MODE (XEXP (note, 0)),
1166 REGNO (XEXP (note, 0)));
1167 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1171 else if (DEBUG_INSN_P (insn)
1172 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)))
1174 scan_rtx (insn, &INSN_VAR_LOCATION_LOC (insn),
1175 ALL_REGS, mark_read, OP_IN);
1177 if (insn == BB_END (bb))
1181 bitmap_clear (&open_chains_set);
1183 if (fail_current_block)
1186 /* Since we close every chain when we find a REG_DEAD note, anything that
1187 is still open lives past the basic block, so it can't be renamed. */
1188 return closed_chains;
1191 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
1192 printed in reverse order as that's how we build them. */
1195 dump_def_use_chain (struct du_head *head)
1199 struct du_chain *this_du = head->first;
1200 fprintf (dump_file, "Register %s (%d):",
1201 reg_names[head->regno], head->nregs);
1204 fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
1205 reg_class_names[this_du->cl]);
1206 this_du = this_du->next_use;
1208 fprintf (dump_file, "\n");
1209 head = head->next_chain;
1215 gate_handle_regrename (void)
1217 return (optimize > 0 && (flag_rename_registers));
1220 struct rtl_opt_pass pass_regrename =
1225 gate_handle_regrename, /* gate */
1226 regrename_optimize, /* execute */
1229 0, /* static_pass_number */
1230 TV_RENAME_REGISTERS, /* tv_id */
1231 0, /* properties_required */
1232 0, /* properties_provided */
1233 0, /* properties_destroyed */
1234 0, /* todo_flags_start */
1235 TODO_df_finish | TODO_verify_rtl_sharing |
1236 TODO_dump_func /* todo_flags_finish */