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;
179 HARD_REG_SET regs_seen;
180 CLEAR_HARD_REG_SET (regs_seen);
183 id_to_chain = VEC_alloc (du_head_p, heap, 0);
185 CLEAR_HARD_REG_SET (unavailable);
188 fprintf (dump_file, "\nBasic block %d:\n", bb->index);
190 all_chains = build_def_use (bb);
193 dump_def_use_chain (all_chains);
195 CLEAR_HARD_REG_SET (unavailable);
196 /* Don't clobber traceback for noreturn functions. */
197 if (frame_pointer_needed)
199 add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
200 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
201 add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
207 int new_reg, best_new_reg, best_nregs;
209 struct du_head *this_head = all_chains;
210 struct du_chain *tmp;
211 HARD_REG_SET this_unavailable;
212 int reg = this_head->regno;
215 all_chains = this_head->next_chain;
217 if (this_head->cannot_rename)
221 best_nregs = this_head->nregs;
223 #if 0 /* This just disables optimization opportunities. */
224 /* Only rename once we've seen the reg more than once. */
225 if (! TEST_HARD_REG_BIT (regs_seen, reg))
227 SET_HARD_REG_BIT (regs_seen, reg);
232 if (fixed_regs[reg] || global_regs[reg]
233 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
234 || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
236 || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
241 COPY_HARD_REG_SET (this_unavailable, unavailable);
243 /* Count number of uses, and narrow the set of registers we can
246 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
248 if (DEBUG_INSN_P (tmp->insn))
251 IOR_COMPL_HARD_REG_SET (this_unavailable,
252 reg_class_contents[tmp->cl]);
258 if (this_head->need_caller_save_reg)
259 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
261 merge_overlapping_regs (&this_unavailable, this_head);
263 /* Now potential_regs is a reasonable approximation, let's
264 have a closer look at each register still in there. */
265 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
267 enum machine_mode mode = GET_MODE (*this_head->first->loc);
268 int nregs = hard_regno_nregs[new_reg][mode];
270 for (i = nregs - 1; i >= 0; --i)
271 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
272 || fixed_regs[new_reg + i]
273 || global_regs[new_reg + i]
274 /* Can't use regs which aren't saved by the prologue. */
275 || (! df_regs_ever_live_p (new_reg + i)
276 && ! call_used_regs[new_reg + i])
277 #ifdef LEAF_REGISTERS
278 /* We can't use a non-leaf register if we're in a
280 || (current_function_is_leaf
281 && !LEAF_REGISTERS[new_reg + i])
283 #ifdef HARD_REGNO_RENAME_OK
284 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
291 /* See whether it accepts all modes that occur in
292 definition and uses. */
293 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
294 if ((! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
295 && ! DEBUG_INSN_P (tmp->insn))
296 || (this_head->need_caller_save_reg
297 && ! (HARD_REGNO_CALL_PART_CLOBBERED
298 (reg, GET_MODE (*tmp->loc)))
299 && (HARD_REGNO_CALL_PART_CLOBBERED
300 (new_reg, GET_MODE (*tmp->loc)))))
304 if (tick[best_new_reg] > tick[new_reg])
306 best_new_reg = new_reg;
314 fprintf (dump_file, "Register %s in insn %d",
315 reg_names[reg], INSN_UID (this_head->first->insn));
316 if (this_head->need_caller_save_reg)
317 fprintf (dump_file, " crosses a call");
320 if (best_new_reg == reg)
322 tick[reg] = ++this_tick;
324 fprintf (dump_file, "; no available better choice\n");
329 fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
331 do_replace (this_head, best_new_reg);
332 this_head->regno = best_new_reg;
333 this_head->nregs = best_nregs;
334 tick[best_new_reg] = ++this_tick;
335 df_set_regs_ever_live (best_new_reg, true);
339 obstack_free (&rename_obstack, first_obj);
342 obstack_free (&rename_obstack, NULL);
345 fputc ('\n', dump_file);
351 do_replace (struct du_head *head, int reg)
353 struct du_chain *chain;
354 unsigned int base_regno = head->regno;
355 bool found_note = false;
357 gcc_assert (! DEBUG_INSN_P (head->first->insn));
359 for (chain = head->first; chain; chain = chain->next_use)
361 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
362 struct reg_attrs *attr = REG_ATTRS (*chain->loc);
363 int reg_ptr = REG_POINTER (*chain->loc);
365 if (DEBUG_INSN_P (chain->insn) && REGNO (*chain->loc) != base_regno)
366 INSN_VAR_LOCATION_LOC (chain->insn) = gen_rtx_UNKNOWN_VAR_LOC ();
371 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
372 if (regno >= FIRST_PSEUDO_REGISTER)
373 ORIGINAL_REGNO (*chain->loc) = regno;
374 REG_ATTRS (*chain->loc) = attr;
375 REG_POINTER (*chain->loc) = reg_ptr;
377 for (note = REG_NOTES (chain->insn); note; note = XEXP (note, 1))
379 enum reg_note kind = REG_NOTE_KIND (note);
380 if (kind == REG_DEAD || kind == REG_UNUSED)
382 rtx reg = XEXP (note, 0);
383 gcc_assert (HARD_REGISTER_P (reg));
385 if (REGNO (reg) == base_regno)
389 && reg_set_p (*chain->loc, chain->insn))
390 remove_note (chain->insn, note);
392 XEXP (note, 0) = *chain->loc;
399 df_insn_rescan (chain->insn);
403 /* If the chain's first insn is the same as the last, we should have
404 found a REG_UNUSED note. */
405 gcc_assert (head->first->insn != head->last->insn);
406 if (!reg_set_p (*head->last->loc, head->last->insn))
407 add_reg_note (head->last->insn, REG_DEAD, *head->last->loc);
412 /* Walk all chains starting with CHAINS and record that they conflict with
413 another chain whose id is ID. */
416 mark_conflict (struct du_head *chains, unsigned id)
420 bitmap_set_bit (&chains->conflicts, id);
421 chains = chains->next_chain;
425 /* True if we found a register with a size mismatch, which means that we
426 can't track its lifetime accurately. If so, we abort the current block
428 static bool fail_current_block;
430 /* The id to be given to the next opened chain. */
431 static unsigned current_id;
433 /* List of currently open chains, and closed chains that can be renamed. */
434 static struct du_head *open_chains;
435 static struct du_head *closed_chains;
437 /* Conflict bitmaps, tracking the live chains and the live hard registers.
438 The bits set in open_chains_set always match the list found in
440 static bitmap_head open_chains_set;
441 static HARD_REG_SET live_hard_regs;
443 /* Record the registers being tracked in open_chains. The intersection
444 between this and live_hard_regs is empty. */
445 static HARD_REG_SET live_in_chains;
447 /* Return true if OP is a reg that is being tracked already in some form.
448 May set fail_current_block if it sees an unhandled case of overlap. */
451 verify_reg_tracked (rtx op)
453 unsigned regno, nregs;
454 bool all_live, all_dead;
459 nregs = hard_regno_nregs[regno][GET_MODE (op)];
460 all_live = all_dead = true;
462 if (TEST_HARD_REG_BIT (live_hard_regs, regno + nregs))
466 if (!all_dead && !all_live)
468 fail_current_block = true;
475 nregs = hard_regno_nregs[regno][GET_MODE (op)];
476 all_live = all_dead = true;
478 if (TEST_HARD_REG_BIT (live_in_chains, regno + nregs))
482 if (!all_dead && !all_live)
484 fail_current_block = true;
491 /* Called through note_stores. DATA points to a rtx_code, either SET or
492 CLOBBER, which tells us which kind of rtx to look at. If we have a
493 match, record the set register in live_hard_regs and in the hard_conflicts
494 bitmap of open chains. */
497 note_sets_clobbers (rtx x, const_rtx set, void *data)
499 enum rtx_code code = *(enum rtx_code *)data;
500 struct du_head *chain;
502 if (GET_CODE (x) == SUBREG)
504 if (!REG_P (x) || GET_CODE (set) != code)
506 /* There must not be pseudos at this point. */
507 gcc_assert (HARD_REGISTER_P (x));
508 add_to_hard_reg_set (&live_hard_regs, GET_MODE (x), REGNO (x));
509 for (chain = open_chains; chain; chain = chain->next_chain)
510 add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x));
514 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
519 enum machine_mode mode = GET_MODE (x);
520 unsigned this_regno = REGNO (x);
521 unsigned this_nregs = hard_regno_nregs[this_regno][mode];
523 if (action == mark_write)
527 struct du_head *head = XOBNEW (&rename_obstack, struct du_head);
528 struct du_chain *this_du = XOBNEW (&rename_obstack, struct du_chain);
531 head->next_chain = open_chains;
533 head->first = head->last = this_du;
534 head->regno = this_regno;
535 head->nregs = this_nregs;
536 head->need_caller_save_reg = 0;
537 head->cannot_rename = 0;
538 head->terminated = 0;
540 VEC_safe_push (du_head_p, heap, id_to_chain, head);
541 head->id = current_id++;
543 bitmap_initialize (&head->conflicts, &bitmap_default_obstack);
544 bitmap_copy (&head->conflicts, &open_chains_set);
545 mark_conflict (open_chains, head->id);
547 /* Since we're tracking this as a chain now, remove it from the
548 list of conflicting live hard registers and track it in
549 live_in_chains instead. */
553 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
554 CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
557 COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs);
558 bitmap_set_bit (&open_chains_set, head->id);
562 this_du->next_use = 0;
564 this_du->insn = insn;
569 "Creating chain %s (%d) at insn %d (%s)\n",
570 reg_names[head->regno], head->id, INSN_UID (insn),
571 scan_actions_name[(int) action]);
576 if ((type == OP_OUT) != (action == terminate_write || action == mark_access))
579 for (p = &open_chains; *p;)
581 struct du_head *head = *p;
582 struct du_head *next = head->next_chain;
583 int exact_match = (head->regno == this_regno
584 && head->nregs == this_nregs);
585 int superset = (this_regno <= head->regno
586 && this_regno + this_nregs >= head->regno + head->nregs);
589 || head->regno + head->nregs <= this_regno
590 || this_regno + this_nregs <= head->regno)
592 p = &head->next_chain;
596 if (action == mark_read || action == mark_access)
598 /* ??? Class NO_REGS can happen if the md file makes use of
599 EXTRA_CONSTRAINTS to match registers. Which is arguably
600 wrong, but there we are. */
602 if (cl == NO_REGS || (!exact_match && !DEBUG_INSN_P (insn)))
606 "Cannot rename chain %s (%d) at insn %d (%s)\n",
607 reg_names[head->regno], head->id, INSN_UID (insn),
608 scan_actions_name[(int) action]);
609 head->cannot_rename = 1;
613 struct du_chain *this_du;
614 this_du = XOBNEW (&rename_obstack, struct du_chain);
615 this_du->next_use = 0;
617 this_du->insn = insn;
619 head->last->next_use = this_du;
620 head->last = this_du;
623 /* Avoid adding the same location in a DEBUG_INSN multiple times,
624 which could happen with non-exact overlap. */
625 if (DEBUG_INSN_P (insn))
627 /* Otherwise, find any other chains that do not match exactly;
628 ensure they all get marked unrenamable. */
629 p = &head->next_chain;
633 /* Whether the terminated chain can be used for renaming
634 depends on the action and this being an exact match.
635 In either case, we remove this element from open_chains. */
637 if ((action == terminate_dead || action == terminate_write)
642 head->terminated = 1;
643 head->next_chain = closed_chains;
644 closed_chains = head;
645 bitmap_clear_bit (&open_chains_set, head->id);
649 CLEAR_HARD_REG_BIT (live_in_chains, head->regno + nregs);
654 "Closing chain %s (%d) at insn %d (%s)\n",
655 reg_names[head->regno], head->id, INSN_UID (insn),
656 scan_actions_name[(int) action]);
658 else if (action == terminate_dead || action == terminate_write)
660 /* In this case, tracking liveness gets too hard. Fail the
661 entire basic block. */
664 "Failing basic block due to unhandled overlap\n");
665 fail_current_block = true;
670 head->cannot_rename = 1;
673 "Cannot rename chain %s (%d) at insn %d (%s)\n",
674 reg_names[head->regno], head->id, INSN_UID (insn),
675 scan_actions_name[(int) action]);
676 p = &head->next_chain;
681 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
682 BASE_REG_CLASS depending on how the register is being considered. */
685 scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl,
686 enum scan_actions action, enum machine_mode mode)
689 RTX_CODE code = GET_CODE (x);
693 if (action == mark_write || action == mark_access)
700 rtx orig_op0 = XEXP (x, 0);
701 rtx orig_op1 = XEXP (x, 1);
702 RTX_CODE code0 = GET_CODE (orig_op0);
703 RTX_CODE code1 = GET_CODE (orig_op1);
708 enum rtx_code index_code = SCRATCH;
710 if (GET_CODE (op0) == SUBREG)
712 op0 = SUBREG_REG (op0);
713 code0 = GET_CODE (op0);
716 if (GET_CODE (op1) == SUBREG)
718 op1 = SUBREG_REG (op1);
719 code1 = GET_CODE (op1);
722 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
723 || code0 == ZERO_EXTEND || code1 == MEM)
727 index_code = GET_CODE (*locI);
729 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
730 || code1 == ZERO_EXTEND || code0 == MEM)
734 index_code = GET_CODE (*locI);
736 else if (code0 == CONST_INT || code0 == CONST
737 || code0 == SYMBOL_REF || code0 == LABEL_REF)
740 index_code = GET_CODE (XEXP (x, 0));
742 else if (code1 == CONST_INT || code1 == CONST
743 || code1 == SYMBOL_REF || code1 == LABEL_REF)
746 index_code = GET_CODE (XEXP (x, 1));
748 else if (code0 == REG && code1 == REG)
751 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
753 if (REGNO_OK_FOR_INDEX_P (regno1)
754 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
756 else if (REGNO_OK_FOR_INDEX_P (regno0)
757 && regno_ok_for_base_p (regno1, mode, PLUS, REG))
759 else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
760 || REGNO_OK_FOR_INDEX_P (regno1))
762 else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
767 locI = &XEXP (x, index_op);
768 locB = &XEXP (x, !index_op);
769 index_code = GET_CODE (*locI);
771 else if (code0 == REG)
775 index_code = GET_CODE (*locI);
777 else if (code1 == REG)
781 index_code = GET_CODE (*locI);
785 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
787 scan_rtx_address (insn, locB, base_reg_class (mode, PLUS, index_code),
800 /* If the target doesn't claim to handle autoinc, this must be
801 something special, like a stack push. Kill this chain. */
802 action = mark_all_read;
807 scan_rtx_address (insn, &XEXP (x, 0),
808 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
813 scan_rtx_reg (insn, loc, cl, action, OP_IN);
820 fmt = GET_RTX_FORMAT (code);
821 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
824 scan_rtx_address (insn, &XEXP (x, i), cl, action, mode);
825 else if (fmt[i] == 'E')
826 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
827 scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode);
832 scan_rtx (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
837 enum rtx_code code = GET_CODE (x);
855 scan_rtx_reg (insn, loc, cl, action, type);
859 scan_rtx_address (insn, &XEXP (x, 0),
860 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
865 scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN);
866 scan_rtx (insn, &SET_DEST (x), cl, action,
867 (GET_CODE (PATTERN (insn)) == COND_EXEC
868 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
871 case STRICT_LOW_PART:
872 scan_rtx (insn, &XEXP (x, 0), cl, action, OP_INOUT);
877 scan_rtx (insn, &XEXP (x, 0), cl, action,
878 type == OP_IN ? OP_IN : OP_INOUT);
879 scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN);
880 scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN);
889 /* Should only happen inside MEM. */
893 scan_rtx (insn, &SET_DEST (x), cl, action,
894 (GET_CODE (PATTERN (insn)) == COND_EXEC
895 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
899 scan_rtx (insn, &XEXP (x, 0), cl, action, type);
901 scan_rtx (insn, &XEXP (x, 1), cl, action, type);
908 fmt = GET_RTX_FORMAT (code);
909 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
912 scan_rtx (insn, &XEXP (x, i), cl, action, type);
913 else if (fmt[i] == 'E')
914 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
915 scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type);
919 /* Hide operands of the current insn (of which there are N_OPS) by
920 substituting cc0 for them.
921 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
922 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
923 and earlyclobbers. */
926 hide_operands (int n_ops, rtx *old_operands, rtx *old_dups,
927 bool inout_and_ec_only)
930 int alt = which_alternative;
931 for (i = 0; i < n_ops; i++)
933 old_operands[i] = recog_data.operand[i];
934 /* Don't squash match_operator or match_parallel here, since
935 we don't know that all of the contained registers are
936 reachable by proper operands. */
937 if (recog_data.constraints[i][0] == '\0')
939 if (!inout_and_ec_only || recog_data.operand_type[i] == OP_INOUT
940 || recog_op_alt[i][alt].earlyclobber)
941 *recog_data.operand_loc[i] = cc0_rtx;
943 for (i = 0; i < recog_data.n_dups; i++)
945 int opn = recog_data.dup_num[i];
946 old_dups[i] = *recog_data.dup_loc[i];
947 if (!inout_and_ec_only || recog_data.operand_type[opn] == OP_INOUT
948 || recog_op_alt[opn][alt].earlyclobber)
949 *recog_data.dup_loc[i] = cc0_rtx;
953 /* Undo the substitution performed by hide_operands. INSN is the insn we
954 are processing; the arguments are the same as in hide_operands. */
957 restore_operands (rtx insn, int n_ops, rtx *old_operands, rtx *old_dups)
960 for (i = 0; i < recog_data.n_dups; i++)
961 *recog_data.dup_loc[i] = old_dups[i];
962 for (i = 0; i < n_ops; i++)
963 *recog_data.operand_loc[i] = old_operands[i];
964 if (recog_data.n_dups)
965 df_insn_rescan (insn);
968 /* For each output operand of INSN, call scan_rtx to create a new
969 open chain. Do this only for normal or earlyclobber outputs,
970 depending on EARLYCLOBBER. */
973 record_out_operands (rtx insn, bool earlyclobber)
975 int n_ops = recog_data.n_operands;
976 int alt = which_alternative;
980 for (i = 0; i < n_ops + recog_data.n_dups; i++)
982 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
983 rtx *loc = (i < n_ops
984 ? recog_data.operand_loc[opn]
985 : recog_data.dup_loc[i - n_ops]);
987 enum reg_class cl = recog_op_alt[opn][alt].cl;
989 struct du_head *prev_open;
991 if (recog_data.operand_type[opn] != OP_OUT
992 || recog_op_alt[opn][alt].earlyclobber != earlyclobber)
995 prev_open = open_chains;
996 scan_rtx (insn, loc, cl, mark_write, OP_OUT);
998 /* ??? Many targets have output constraints on the SET_DEST
999 of a call insn, which is stupid, since these are certainly
1000 ABI defined hard registers. For these, and for asm operands
1001 that originally referenced hard registers, we must record that
1002 the chain cannot be renamed. */
1004 || (asm_noperands (PATTERN (insn)) > 0
1006 && REGNO (op) == ORIGINAL_REGNO (op)))
1008 if (prev_open != open_chains)
1009 open_chains->cannot_rename = 1;
1014 /* Build def/use chain. */
1016 static struct du_head *
1017 build_def_use (basic_block bb)
1022 open_chains = closed_chains = NULL;
1024 fail_current_block = false;
1027 bitmap_initialize (&open_chains_set, &bitmap_default_obstack);
1028 CLEAR_HARD_REG_SET (live_in_chains);
1029 REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb));
1030 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1032 df_ref def = *def_rec;
1033 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
1034 SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def));
1037 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
1039 if (NONDEBUG_INSN_P (insn))
1043 rtx old_operands[MAX_RECOG_OPERANDS];
1044 rtx old_dups[MAX_DUP_OPERANDS];
1048 enum rtx_code set_code = SET;
1049 enum rtx_code clobber_code = CLOBBER;
1051 /* Process the insn, determining its effect on the def-use
1052 chains and live hard registers. We perform the following
1053 steps with the register references in the insn, simulating
1055 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1056 by creating chains and marking hard regs live.
1057 (2) Any read outside an operand causes any chain it overlaps
1058 with to be marked unrenamable.
1059 (3) Any read inside an operand is added if there's already
1060 an open chain for it.
1061 (4) For any REG_DEAD note we find, close open chains that
1063 (5) For any non-earlyclobber write we find, close open chains
1065 (6) For any non-earlyclobber write we find in an operand, make
1066 a new chain or mark the hard register as live.
1067 (7) For any REG_UNUSED, close any chains we just opened.
1069 We cannot deal with situations where we track a reg in one mode
1070 and see a reference in another mode; these will cause the chain
1071 to be marked unrenamable or even cause us to abort the entire
1074 extract_insn (insn);
1075 if (! constrain_operands (1))
1076 fatal_insn_not_found (insn);
1077 preprocess_constraints ();
1078 alt = which_alternative;
1079 n_ops = recog_data.n_operands;
1081 /* Simplify the code below by rewriting things to reflect
1082 matching constraints. Also promote OP_OUT to OP_INOUT in
1083 predicated instructions, but only for register operands
1084 that are already tracked, so that we can create a chain
1085 when the first SET makes a register live. */
1087 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1088 for (i = 0; i < n_ops; ++i)
1090 int matches = recog_op_alt[i][alt].matches;
1092 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
1093 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
1094 || (predicated && recog_data.operand_type[i] == OP_OUT
1095 && verify_reg_tracked (recog_data.operand[i])))
1097 recog_data.operand_type[i] = OP_INOUT;
1099 && (GET_MODE_SIZE (recog_data.operand_mode[i])
1100 != GET_MODE_SIZE (recog_data.operand_mode[matches])))
1101 fail_current_block = true;
1105 if (fail_current_block)
1108 /* Step 1a: Mark hard registers that are clobbered in this insn,
1109 outside an operand, as live. */
1110 hide_operands (n_ops, old_operands, old_dups, false);
1111 note_stores (PATTERN (insn), note_sets_clobbers, &clobber_code);
1112 restore_operands (insn, n_ops, old_operands, old_dups);
1114 /* Step 1b: Begin new chains for earlyclobbered writes inside
1116 record_out_operands (insn, true);
1118 /* Step 2: Mark chains for which we have reads outside operands
1120 We do this by munging all operands into CC0, and closing
1121 everything remaining. */
1123 hide_operands (n_ops, old_operands, old_dups, false);
1124 scan_rtx (insn, &PATTERN (insn), NO_REGS, mark_all_read, OP_IN);
1125 restore_operands (insn, n_ops, old_operands, old_dups);
1127 /* Step 2B: Can't rename function call argument registers. */
1128 if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
1129 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
1130 NO_REGS, mark_all_read, OP_IN);
1132 /* Step 2C: Can't rename asm operands that were originally
1134 if (asm_noperands (PATTERN (insn)) > 0)
1135 for (i = 0; i < n_ops; i++)
1137 rtx *loc = recog_data.operand_loc[i];
1141 && REGNO (op) == ORIGINAL_REGNO (op)
1142 && (recog_data.operand_type[i] == OP_IN
1143 || recog_data.operand_type[i] == OP_INOUT))
1144 scan_rtx (insn, loc, NO_REGS, mark_all_read, OP_IN);
1147 /* Step 3: Append to chains for reads inside operands. */
1148 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1150 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1151 rtx *loc = (i < n_ops
1152 ? recog_data.operand_loc[opn]
1153 : recog_data.dup_loc[i - n_ops]);
1154 enum reg_class cl = recog_op_alt[opn][alt].cl;
1155 enum op_type type = recog_data.operand_type[opn];
1157 /* Don't scan match_operand here, since we've no reg class
1158 information to pass down. Any operands that we could
1159 substitute in will be represented elsewhere. */
1160 if (recog_data.constraints[opn][0] == '\0')
1163 if (recog_op_alt[opn][alt].is_address)
1164 scan_rtx_address (insn, loc, cl, mark_read, VOIDmode);
1166 scan_rtx (insn, loc, cl, mark_read, type);
1169 /* Step 3B: Record updates for regs in REG_INC notes, and
1170 source regs in REG_FRAME_RELATED_EXPR notes. */
1171 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1172 if (REG_NOTE_KIND (note) == REG_INC
1173 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1174 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
1177 /* Step 4: Close chains for registers that die here. */
1178 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1179 if (REG_NOTE_KIND (note) == REG_DEAD)
1181 remove_from_hard_reg_set (&live_hard_regs,
1182 GET_MODE (XEXP (note, 0)),
1183 REGNO (XEXP (note, 0)));
1184 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1188 /* Step 4B: If this is a call, any chain live at this point
1189 requires a caller-saved reg. */
1193 for (p = open_chains; p; p = p->next_chain)
1194 p->need_caller_save_reg = 1;
1197 /* Step 5: Close open chains that overlap writes. Similar to
1198 step 2, we hide in-out operands, since we do not want to
1199 close these chains. We also hide earlyclobber operands,
1200 since we've opened chains for them in step 1, and earlier
1201 chains they would overlap with must have been closed at
1202 the previous insn at the latest, as such operands cannot
1203 possibly overlap with any input operands. */
1205 hide_operands (n_ops, old_operands, old_dups, true);
1206 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN);
1207 restore_operands (insn, n_ops, old_operands, old_dups);
1209 /* Step 6a: Mark hard registers that are set in this insn,
1210 outside an operand, as live. */
1211 hide_operands (n_ops, old_operands, old_dups, false);
1212 note_stores (PATTERN (insn), note_sets_clobbers, &set_code);
1213 restore_operands (insn, n_ops, old_operands, old_dups);
1215 /* Step 6b: Begin new chains for writes inside operands. */
1216 record_out_operands (insn, false);
1218 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1219 notes for update. */
1220 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1221 if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1222 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
1225 /* Step 7: Close chains for registers that were never
1226 really used here. */
1227 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1228 if (REG_NOTE_KIND (note) == REG_UNUSED)
1230 remove_from_hard_reg_set (&live_hard_regs,
1231 GET_MODE (XEXP (note, 0)),
1232 REGNO (XEXP (note, 0)));
1233 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1237 else if (DEBUG_INSN_P (insn)
1238 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)))
1240 scan_rtx (insn, &INSN_VAR_LOCATION_LOC (insn),
1241 ALL_REGS, mark_read, OP_IN);
1243 if (insn == BB_END (bb))
1247 bitmap_clear (&open_chains_set);
1249 if (fail_current_block)
1252 /* Since we close every chain when we find a REG_DEAD note, anything that
1253 is still open lives past the basic block, so it can't be renamed. */
1254 return closed_chains;
1257 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
1258 printed in reverse order as that's how we build them. */
1261 dump_def_use_chain (struct du_head *head)
1265 struct du_chain *this_du = head->first;
1266 fprintf (dump_file, "Register %s (%d):",
1267 reg_names[head->regno], head->nregs);
1270 fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
1271 reg_class_names[this_du->cl]);
1272 this_du = this_du->next_use;
1274 fprintf (dump_file, "\n");
1275 head = head->next_chain;
1281 gate_handle_regrename (void)
1283 return (optimize > 0 && (flag_rename_registers));
1286 struct rtl_opt_pass pass_regrename =
1291 gate_handle_regrename, /* gate */
1292 regrename_optimize, /* execute */
1295 0, /* static_pass_number */
1296 TV_RENAME_REGISTERS, /* tv_id */
1297 0, /* properties_required */
1298 0, /* properties_provided */
1299 0, /* properties_destroyed */
1300 0, /* todo_flags_start */
1301 TODO_df_finish | TODO_verify_rtl_sharing |
1302 TODO_dump_func /* todo_flags_finish */