1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
3 2010 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"
25 #include "rtl-error.h"
27 #include "insn-config.h"
29 #include "addresses.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
39 #include "tree-pass.h"
43 #if HOST_BITS_PER_WIDE_INT <= MAX_RECOG_OPERANDS
44 #error "Use a different bitmap implementation for untracked_operands."
47 /* We keep linked lists of DU_HEAD structures, each of which describes
48 a chain of occurrences of a reg. */
52 struct du_head *next_chain;
53 /* The first and last elements of this chain. */
54 struct du_chain *first, *last;
55 /* The number of elements of this chain, excluding those corresponding
56 to references of the register in debug insns. The du_head linked
57 list can be sorted by this, and register-rename can prefer
58 register classes according to this order. */
60 /* Describes the register being tracked. */
61 unsigned regno, nregs;
63 /* A unique id to be used as an index into the conflicts bitmaps. */
65 /* A bitmap to record conflicts with other chains. */
66 bitmap_head conflicts;
67 /* Conflicts with untracked hard registers. */
68 HARD_REG_SET hard_conflicts;
70 /* Nonzero if the chain is finished; zero if it is still open. */
71 unsigned int terminated:1;
72 /* Nonzero if the chain crosses a call. */
73 unsigned int need_caller_save_reg:1;
74 /* Nonzero if the register is used in a way that prevents renaming,
75 such as the SET_DEST of a CALL_INSN or an asm operand that used
76 to be a hard register. */
77 unsigned int cannot_rename:1;
80 /* This struct describes a single occurrence of a register. */
83 /* Links to the next occurrence of the register. */
84 struct du_chain *next_use;
86 /* The insn where the register appears. */
88 /* The location inside the insn. */
90 /* The register class required by the insn at this location. */
91 ENUM_BITFIELD(reg_class) cl : 16;
101 /* mark_access is for marking the destination regs in
102 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
103 note is updated properly. */
107 static const char * const scan_actions_name[] =
117 static struct obstack rename_obstack;
119 static void do_replace (struct du_head *, int);
120 static void scan_rtx_reg (rtx, rtx *, enum reg_class,
121 enum scan_actions, enum op_type);
122 static void scan_rtx_address (rtx, rtx *, enum reg_class,
123 enum scan_actions, enum machine_mode);
124 static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions,
126 static struct du_head *build_def_use (basic_block);
127 static void dump_def_use_chain (struct du_head *);
129 typedef struct du_head *du_head_p;
130 DEF_VEC_P (du_head_p);
131 DEF_VEC_ALLOC_P (du_head_p, heap);
132 static VEC(du_head_p, heap) *id_to_chain;
135 free_chain_data (void)
139 for (i = 0; VEC_iterate(du_head_p, id_to_chain, i, ptr); i++)
140 bitmap_clear (&ptr->conflicts);
142 VEC_free (du_head_p, heap, id_to_chain);
145 /* For a def-use chain HEAD, find which registers overlap its lifetime and
146 set the corresponding bits in *PSET. */
149 merge_overlapping_regs (HARD_REG_SET *pset, struct du_head *head)
153 IOR_HARD_REG_SET (*pset, head->hard_conflicts);
154 EXECUTE_IF_SET_IN_BITMAP (&head->conflicts, 0, i, bi)
156 du_head_p other = VEC_index (du_head_p, id_to_chain, i);
157 unsigned j = other->nregs;
159 SET_HARD_REG_BIT (*pset, other->regno + j);
163 /* Return the Nth element in LIST. If LIST contains less than N
164 elements, return the last one. */
165 static struct du_head *
166 get_element (struct du_head *list, int n)
168 while (n-- && list->next_chain != NULL)
169 list = list->next_chain;
174 /* Comparison function of merge sort. Return true if A is less than
175 B, otherwise return false. */
177 merge_sort_comparison(const struct du_head *a,
178 const struct du_head *b)
180 return a->length < b->length;
183 /* Merge the first 2 sub-lists of LENGTH nodes contained in the
184 linked list pointed to by START_NODE. Update START_NODE to point
185 to the merged nodes, and return a pointer to the last merged
186 node. Return NULL if START_NODE doesn't contain enough
187 elements, or this pass of merge is done. */
189 static struct du_head *
190 merge(struct du_head **start_node, int length)
192 int i, left_count, right_count;
193 struct du_head *left, *right;
194 /* Current node of sort result. */
195 struct du_head *current_sorted_node;
196 /* Tail node of sort, used to connect with next piece of list. */
197 struct du_head *current_tail_node;
199 if (*start_node == NULL)
202 left = right = *start_node;
203 right_count = left_count = 0;
205 /* Step RIGHT along the list by LENGTH places. */
206 for (i = 0; i < length; i++)
208 right = right->next_chain;
215 /* Initialize current_sorted_node. */
216 if (merge_sort_comparison (left, right))
219 current_sorted_node = right;
221 right = right->next_chain;
226 current_sorted_node = left;
227 left = left->next_chain;
232 /* Choose LEFT or RIGHT to take the next element from. If
233 either is empty, choose from the other one. */
234 if (left_count == length || left == NULL)
236 current_sorted_node->next_chain = right;
237 current_tail_node = get_element (current_sorted_node,
238 length - right_count);
242 else if (right_count == length || right == NULL)
244 /* Save the head node of next piece of linked list. */
245 struct du_head *tmp = current_sorted_node->next_chain;
247 current_sorted_node->next_chain = left;
249 = get_element (current_sorted_node,
250 length - left_count);
251 /* Connect sorted list to next piece of list. */
252 current_tail_node->next_chain = tmp;
257 /* Normal merge operations. If both LEFT and RIGHT are
258 non-empty, compare the first element of each and choose
260 if (merge_sort_comparison (left, right))
263 current_sorted_node->next_chain = right;
264 right = right->next_chain;
269 current_sorted_node->next_chain = left;
270 left = left->next_chain;
272 current_sorted_node = current_sorted_node->next_chain;
275 /* Return NULL if this pass of merge is done. */
276 return (current_tail_node->next_chain ? current_tail_node : NULL);
279 /* Sort the linked list pointed to by HEAD. The algorithm is a
280 non-recursive merge sort to linked list. */
283 sort_du_head (struct du_head **head)
285 int current_length = 1;
286 struct du_head *last_tail;
288 /* In each pass, lists of size current_length is merged to
289 lists of size 2xcurrent_length (Initially current_length
293 last_tail = merge(head, current_length);
294 if (last_tail != NULL)
297 last_tail = merge (&last_tail->next_chain, current_length);
298 while (last_tail != NULL);
307 /* Check if NEW_REG can be the candidate register to rename for
308 REG in THIS_HEAD chain. THIS_UNAVAILABLE is a set of unavailable hard
312 check_new_reg_p (int reg ATTRIBUTE_UNUSED, int new_reg,
313 struct du_head *this_head, HARD_REG_SET this_unavailable)
315 enum machine_mode mode = GET_MODE (*this_head->first->loc);
316 int nregs = hard_regno_nregs[new_reg][mode];
318 struct du_chain *tmp;
320 for (i = nregs - 1; i >= 0; --i)
321 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i)
322 || fixed_regs[new_reg + i]
323 || global_regs[new_reg + i]
324 /* Can't use regs which aren't saved by the prologue. */
325 || (! df_regs_ever_live_p (new_reg + i)
326 && ! call_used_regs[new_reg + i])
327 #ifdef LEAF_REGISTERS
328 /* We can't use a non-leaf register if we're in a
330 || (current_function_is_leaf
331 && !LEAF_REGISTERS[new_reg + i])
333 #ifdef HARD_REGNO_RENAME_OK
334 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i)
339 /* See whether it accepts all modes that occur in
340 definition and uses. */
341 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
342 if ((! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))
343 && ! DEBUG_INSN_P (tmp->insn))
344 || (this_head->need_caller_save_reg
345 && ! (HARD_REGNO_CALL_PART_CLOBBERED
346 (reg, GET_MODE (*tmp->loc)))
347 && (HARD_REGNO_CALL_PART_CLOBBERED
348 (new_reg, GET_MODE (*tmp->loc)))))
354 /* Perform register renaming on the current function. */
357 regrename_optimize (void)
359 int tick[FIRST_PSEUDO_REGISTER];
364 df_set_flags (DF_LR_RUN_DCE);
365 df_note_add_problem ();
367 df_set_flags (DF_DEFER_INSN_RESCAN);
369 memset (tick, 0, sizeof tick);
371 gcc_obstack_init (&rename_obstack);
372 first_obj = XOBNEWVAR (&rename_obstack, char, 0);
376 struct du_head *all_chains = 0;
377 HARD_REG_SET unavailable;
379 HARD_REG_SET regs_seen;
380 CLEAR_HARD_REG_SET (regs_seen);
383 id_to_chain = VEC_alloc (du_head_p, heap, 0);
385 CLEAR_HARD_REG_SET (unavailable);
388 fprintf (dump_file, "\nBasic block %d:\n", bb->index);
390 all_chains = build_def_use (bb);
393 dump_def_use_chain (all_chains);
395 sort_du_head (&all_chains);
397 CLEAR_HARD_REG_SET (unavailable);
398 /* Don't clobber traceback for noreturn functions. */
399 if (frame_pointer_needed)
401 add_to_hard_reg_set (&unavailable, Pmode, FRAME_POINTER_REGNUM);
402 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
403 add_to_hard_reg_set (&unavailable, Pmode, HARD_FRAME_POINTER_REGNUM);
409 int new_reg, best_new_reg, best_nregs;
411 struct du_head *this_head = all_chains;
412 struct du_chain *tmp;
413 HARD_REG_SET this_unavailable;
414 int reg = this_head->regno;
416 enum reg_class superunion_class = NO_REGS;
417 enum reg_class preferred_class;
419 all_chains = this_head->next_chain;
421 if (this_head->cannot_rename)
425 best_nregs = this_head->nregs;
427 #if 0 /* This just disables optimization opportunities. */
428 /* Only rename once we've seen the reg more than once. */
429 if (! TEST_HARD_REG_BIT (regs_seen, reg))
431 SET_HARD_REG_BIT (regs_seen, reg);
436 if (fixed_regs[reg] || global_regs[reg]
437 #if !HARD_FRAME_POINTER_IS_FRAME_POINTER
438 || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM)
440 || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM)
445 COPY_HARD_REG_SET (this_unavailable, unavailable);
447 /* Iterate elements in chain in order to:
448 1. Count number of uses, and narrow the set of registers we can
450 2. Compute the superunion of register classes in this chain. */
452 superunion_class = NO_REGS;
453 for (tmp = this_head->first; tmp; tmp = tmp->next_use)
455 if (DEBUG_INSN_P (tmp->insn))
459 IOR_COMPL_HARD_REG_SET (this_unavailable,
460 reg_class_contents[tmp->cl]);
463 = reg_class_superunion[(int) superunion_class][(int) tmp->cl];
469 if (this_head->need_caller_save_reg)
470 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set);
472 merge_overlapping_regs (&this_unavailable, this_head);
473 /* Compute preferred rename class of super union of all the classes
476 = (enum reg_class) targetm.preferred_rename_class(superunion_class);
478 /* The register iteration order here is "preferred-register-first".
479 Firstly(pass == 0), we iterate registers belong to PREFERRED_CLASS,
480 if we find a new register, we stop immeidately.
481 Otherwise, we iterate over registers that don't belong to
483 If PREFERRED_CLASS is NO_REGS, we iterate over all registers in
484 ascending order without any preference. */
485 for (pass = (preferred_class == NO_REGS ? 1 : 0); pass < 2; pass++)
488 /* Now potential_regs is a reasonable approximation, let's
489 have a closer look at each register still in there. */
490 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++)
492 /* Iterate registers first in prefered class. */
494 && !TEST_HARD_REG_BIT (reg_class_contents[preferred_class],
498 if (check_new_reg_p (reg, new_reg, this_head,
501 if (tick[best_new_reg] > tick[new_reg])
503 enum machine_mode mode
504 = GET_MODE (*this_head->first->loc);
505 best_new_reg = new_reg;
506 best_nregs = hard_regno_nregs[new_reg][mode];
507 /* If we find a new reg in our preferred class,
509 if (best_new_reg != reg && pass == 0)
522 fprintf (dump_file, "Register %s in insn %d",
523 reg_names[reg], INSN_UID (this_head->first->insn));
524 if (this_head->need_caller_save_reg)
525 fprintf (dump_file, " crosses a call");
528 if (best_new_reg == reg)
530 tick[reg] = ++this_tick;
532 fprintf (dump_file, "; no available better choice\n");
537 fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]);
539 do_replace (this_head, best_new_reg);
540 this_head->regno = best_new_reg;
541 this_head->nregs = best_nregs;
542 tick[best_new_reg] = ++this_tick;
543 df_set_regs_ever_live (best_new_reg, true);
547 obstack_free (&rename_obstack, first_obj);
550 obstack_free (&rename_obstack, NULL);
553 fputc ('\n', dump_file);
559 do_replace (struct du_head *head, int reg)
561 struct du_chain *chain;
562 unsigned int base_regno = head->regno;
563 bool found_note = false;
565 gcc_assert (! DEBUG_INSN_P (head->first->insn));
567 for (chain = head->first; chain; chain = chain->next_use)
569 unsigned int regno = ORIGINAL_REGNO (*chain->loc);
570 struct reg_attrs *attr = REG_ATTRS (*chain->loc);
571 int reg_ptr = REG_POINTER (*chain->loc);
573 if (DEBUG_INSN_P (chain->insn) && REGNO (*chain->loc) != base_regno)
574 INSN_VAR_LOCATION_LOC (chain->insn) = gen_rtx_UNKNOWN_VAR_LOC ();
579 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg);
580 if (regno >= FIRST_PSEUDO_REGISTER)
581 ORIGINAL_REGNO (*chain->loc) = regno;
582 REG_ATTRS (*chain->loc) = attr;
583 REG_POINTER (*chain->loc) = reg_ptr;
585 for (note = REG_NOTES (chain->insn); note; note = XEXP (note, 1))
587 enum reg_note kind = REG_NOTE_KIND (note);
588 if (kind == REG_DEAD || kind == REG_UNUSED)
590 rtx reg = XEXP (note, 0);
591 gcc_assert (HARD_REGISTER_P (reg));
593 if (REGNO (reg) == base_regno)
597 && reg_set_p (*chain->loc, chain->insn))
598 remove_note (chain->insn, note);
600 XEXP (note, 0) = *chain->loc;
607 df_insn_rescan (chain->insn);
611 /* If the chain's first insn is the same as the last, we should have
612 found a REG_UNUSED note. */
613 gcc_assert (head->first->insn != head->last->insn);
614 if (!reg_set_p (*head->last->loc, head->last->insn))
615 add_reg_note (head->last->insn, REG_DEAD, *head->last->loc);
620 /* Walk all chains starting with CHAINS and record that they conflict with
621 another chain whose id is ID. */
624 mark_conflict (struct du_head *chains, unsigned id)
628 bitmap_set_bit (&chains->conflicts, id);
629 chains = chains->next_chain;
633 /* True if we found a register with a size mismatch, which means that we
634 can't track its lifetime accurately. If so, we abort the current block
636 static bool fail_current_block;
638 /* The id to be given to the next opened chain. */
639 static unsigned current_id;
641 /* List of currently open chains, and closed chains that can be renamed. */
642 static struct du_head *open_chains;
643 static struct du_head *closed_chains;
645 /* Bitmap of open chains. The bits set always match the list found in
647 static bitmap_head open_chains_set;
649 /* Record the registers being tracked in open_chains. */
650 static HARD_REG_SET live_in_chains;
652 /* Record the registers that are live but not tracked. The intersection
653 between this and live_in_chains is empty. */
654 static HARD_REG_SET live_hard_regs;
656 /* Return true if OP is a reg for which all bits are set in PSET, false
657 if all bits are clear.
658 In other cases, set fail_current_block and return false. */
661 verify_reg_in_set (rtx op, HARD_REG_SET *pset)
663 unsigned regno, nregs;
664 bool all_live, all_dead;
669 nregs = hard_regno_nregs[regno][GET_MODE (op)];
670 all_live = all_dead = true;
672 if (TEST_HARD_REG_BIT (*pset, regno + nregs))
676 if (!all_dead && !all_live)
678 fail_current_block = true;
684 /* Return true if OP is a reg that is being tracked already in some form.
685 May set fail_current_block if it sees an unhandled case of overlap. */
688 verify_reg_tracked (rtx op)
690 return (verify_reg_in_set (op, &live_hard_regs)
691 || verify_reg_in_set (op, &live_in_chains));
694 /* Called through note_stores. DATA points to a rtx_code, either SET or
695 CLOBBER, which tells us which kind of rtx to look at. If we have a
696 match, record the set register in live_hard_regs and in the hard_conflicts
697 bitmap of open chains. */
700 note_sets_clobbers (rtx x, const_rtx set, void *data)
702 enum rtx_code code = *(enum rtx_code *)data;
703 struct du_head *chain;
705 if (GET_CODE (x) == SUBREG)
707 if (!REG_P (x) || GET_CODE (set) != code)
709 /* There must not be pseudos at this point. */
710 gcc_assert (HARD_REGISTER_P (x));
711 add_to_hard_reg_set (&live_hard_regs, GET_MODE (x), REGNO (x));
712 for (chain = open_chains; chain; chain = chain->next_chain)
713 add_to_hard_reg_set (&chain->hard_conflicts, GET_MODE (x), REGNO (x));
716 /* Create a new chain for THIS_NREGS registers starting at THIS_REGNO,
717 and record its occurrence in *LOC, which is being written to in INSN.
718 This access requires a register of class CL. */
721 create_new_chain (unsigned this_regno, unsigned this_nregs, rtx *loc,
722 rtx insn, enum reg_class cl)
724 struct du_head *head = XOBNEW (&rename_obstack, struct du_head);
725 struct du_chain *this_du;
728 head->next_chain = open_chains;
730 head->regno = this_regno;
731 head->nregs = this_nregs;
732 head->need_caller_save_reg = 0;
733 head->cannot_rename = 0;
734 head->terminated = 0;
737 VEC_safe_push (du_head_p, heap, id_to_chain, head);
738 head->id = current_id++;
740 bitmap_initialize (&head->conflicts, &bitmap_default_obstack);
741 bitmap_copy (&head->conflicts, &open_chains_set);
742 mark_conflict (open_chains, head->id);
744 /* Since we're tracking this as a chain now, remove it from the
745 list of conflicting live hard registers and track it in
746 live_in_chains instead. */
750 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
751 CLEAR_HARD_REG_BIT (live_hard_regs, head->regno + nregs);
754 COPY_HARD_REG_SET (head->hard_conflicts, live_hard_regs);
755 bitmap_set_bit (&open_chains_set, head->id);
761 fprintf (dump_file, "Creating chain %s (%d)",
762 reg_names[head->regno], head->id);
763 if (insn != NULL_RTX)
764 fprintf (dump_file, " at insn %d", INSN_UID (insn));
765 fprintf (dump_file, "\n");
768 if (insn == NULL_RTX)
770 head->first = head->last = NULL;
774 this_du = XOBNEW (&rename_obstack, struct du_chain);
775 head->first = head->last = this_du;
777 this_du->next_use = 0;
779 this_du->insn = insn;
786 scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
791 enum machine_mode mode = GET_MODE (x);
792 unsigned this_regno = REGNO (x);
793 unsigned this_nregs = hard_regno_nregs[this_regno][mode];
795 if (action == mark_write)
798 create_new_chain (this_regno, this_nregs, loc, insn, cl);
802 if ((type == OP_OUT) != (action == terminate_write || action == mark_access))
805 for (p = &open_chains; *p;)
807 struct du_head *head = *p;
808 struct du_head *next = head->next_chain;
809 int exact_match = (head->regno == this_regno
810 && head->nregs == this_nregs);
811 int superset = (this_regno <= head->regno
812 && this_regno + this_nregs >= head->regno + head->nregs);
813 int subset = (this_regno >= head->regno
814 && this_regno + this_nregs <= head->regno + head->nregs);
817 || head->regno + head->nregs <= this_regno
818 || this_regno + this_nregs <= head->regno)
820 p = &head->next_chain;
824 if (action == mark_read || action == mark_access)
826 /* ??? Class NO_REGS can happen if the md file makes use of
827 EXTRA_CONSTRAINTS to match registers. Which is arguably
828 wrong, but there we are. */
830 if (cl == NO_REGS || (!exact_match && !DEBUG_INSN_P (insn)))
834 "Cannot rename chain %s (%d) at insn %d (%s)\n",
835 reg_names[head->regno], head->id, INSN_UID (insn),
836 scan_actions_name[(int) action]);
837 head->cannot_rename = 1;
840 unsigned nregs = this_nregs;
841 head->regno = this_regno;
842 head->nregs = this_nregs;
844 SET_HARD_REG_BIT (live_in_chains, head->regno + nregs);
847 "Widening register in chain %s (%d) at insn %d\n",
848 reg_names[head->regno], head->id, INSN_UID (insn));
852 fail_current_block = true;
855 "Failing basic block due to unhandled overlap\n");
860 struct du_chain *this_du;
861 this_du = XOBNEW (&rename_obstack, struct du_chain);
862 this_du->next_use = 0;
864 this_du->insn = insn;
866 if (head->first == NULL)
867 head->first = this_du;
869 head->last->next_use = this_du;
870 head->last = this_du;
872 if (!DEBUG_INSN_P (insn))
875 /* Avoid adding the same location in a DEBUG_INSN multiple times,
876 which could happen with non-exact overlap. */
877 if (DEBUG_INSN_P (insn))
879 /* Otherwise, find any other chains that do not match exactly;
880 ensure they all get marked unrenamable. */
881 p = &head->next_chain;
885 /* Whether the terminated chain can be used for renaming
886 depends on the action and this being an exact match.
887 In either case, we remove this element from open_chains. */
889 if ((action == terminate_dead || action == terminate_write)
894 head->terminated = 1;
895 head->next_chain = closed_chains;
896 closed_chains = head;
897 bitmap_clear_bit (&open_chains_set, head->id);
901 CLEAR_HARD_REG_BIT (live_in_chains, head->regno + nregs);
906 "Closing chain %s (%d) at insn %d (%s)\n",
907 reg_names[head->regno], head->id, INSN_UID (insn),
908 scan_actions_name[(int) action]);
910 else if (action == terminate_dead || action == terminate_write)
912 /* In this case, tracking liveness gets too hard. Fail the
913 entire basic block. */
916 "Failing basic block due to unhandled overlap\n");
917 fail_current_block = true;
922 head->cannot_rename = 1;
925 "Cannot rename chain %s (%d) at insn %d (%s)\n",
926 reg_names[head->regno], head->id, INSN_UID (insn),
927 scan_actions_name[(int) action]);
928 p = &head->next_chain;
933 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
934 BASE_REG_CLASS depending on how the register is being considered. */
937 scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl,
938 enum scan_actions action, enum machine_mode mode)
941 RTX_CODE code = GET_CODE (x);
945 if (action == mark_write || action == mark_access)
952 rtx orig_op0 = XEXP (x, 0);
953 rtx orig_op1 = XEXP (x, 1);
954 RTX_CODE code0 = GET_CODE (orig_op0);
955 RTX_CODE code1 = GET_CODE (orig_op1);
960 enum rtx_code index_code = SCRATCH;
962 if (GET_CODE (op0) == SUBREG)
964 op0 = SUBREG_REG (op0);
965 code0 = GET_CODE (op0);
968 if (GET_CODE (op1) == SUBREG)
970 op1 = SUBREG_REG (op1);
971 code1 = GET_CODE (op1);
974 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE
975 || code0 == ZERO_EXTEND || code1 == MEM)
979 index_code = GET_CODE (*locI);
981 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE
982 || code1 == ZERO_EXTEND || code0 == MEM)
986 index_code = GET_CODE (*locI);
988 else if (code0 == CONST_INT || code0 == CONST
989 || code0 == SYMBOL_REF || code0 == LABEL_REF)
992 index_code = GET_CODE (XEXP (x, 0));
994 else if (code1 == CONST_INT || code1 == CONST
995 || code1 == SYMBOL_REF || code1 == LABEL_REF)
998 index_code = GET_CODE (XEXP (x, 1));
1000 else if (code0 == REG && code1 == REG)
1003 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1);
1005 if (REGNO_OK_FOR_INDEX_P (regno1)
1006 && regno_ok_for_base_p (regno0, mode, PLUS, REG))
1008 else if (REGNO_OK_FOR_INDEX_P (regno0)
1009 && regno_ok_for_base_p (regno1, mode, PLUS, REG))
1011 else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)
1012 || REGNO_OK_FOR_INDEX_P (regno1))
1014 else if (regno_ok_for_base_p (regno1, mode, PLUS, REG))
1019 locI = &XEXP (x, index_op);
1020 locB = &XEXP (x, !index_op);
1021 index_code = GET_CODE (*locI);
1023 else if (code0 == REG)
1025 locI = &XEXP (x, 0);
1026 locB = &XEXP (x, 1);
1027 index_code = GET_CODE (*locI);
1029 else if (code1 == REG)
1031 locI = &XEXP (x, 1);
1032 locB = &XEXP (x, 0);
1033 index_code = GET_CODE (*locI);
1037 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode);
1039 scan_rtx_address (insn, locB, base_reg_class (mode, PLUS, index_code),
1051 #ifndef AUTO_INC_DEC
1052 /* If the target doesn't claim to handle autoinc, this must be
1053 something special, like a stack push. Kill this chain. */
1054 action = mark_all_read;
1059 scan_rtx_address (insn, &XEXP (x, 0),
1060 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
1065 scan_rtx_reg (insn, loc, cl, action, OP_IN);
1072 fmt = GET_RTX_FORMAT (code);
1073 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1076 scan_rtx_address (insn, &XEXP (x, i), cl, action, mode);
1077 else if (fmt[i] == 'E')
1078 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1079 scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode);
1084 scan_rtx (rtx insn, rtx *loc, enum reg_class cl, enum scan_actions action,
1089 enum rtx_code code = GET_CODE (x);
1092 code = GET_CODE (x);
1107 scan_rtx_reg (insn, loc, cl, action, type);
1111 scan_rtx_address (insn, &XEXP (x, 0),
1112 base_reg_class (GET_MODE (x), MEM, SCRATCH), action,
1117 scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN);
1118 scan_rtx (insn, &SET_DEST (x), cl, action,
1119 (GET_CODE (PATTERN (insn)) == COND_EXEC
1120 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
1123 case STRICT_LOW_PART:
1124 scan_rtx (insn, &XEXP (x, 0), cl, action,
1125 verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT);
1130 scan_rtx (insn, &XEXP (x, 0), cl, action,
1131 (type == OP_IN ? OP_IN :
1132 verify_reg_tracked (XEXP (x, 0)) ? OP_INOUT : OP_OUT));
1133 scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN);
1134 scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN);
1143 /* Should only happen inside MEM. */
1147 scan_rtx (insn, &SET_DEST (x), cl, action,
1148 (GET_CODE (PATTERN (insn)) == COND_EXEC
1149 && verify_reg_tracked (SET_DEST (x))) ? OP_INOUT : OP_OUT);
1153 scan_rtx (insn, &XEXP (x, 0), cl, action, type);
1155 scan_rtx (insn, &XEXP (x, 1), cl, action, type);
1162 fmt = GET_RTX_FORMAT (code);
1163 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1166 scan_rtx (insn, &XEXP (x, i), cl, action, type);
1167 else if (fmt[i] == 'E')
1168 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1169 scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type);
1173 /* Hide operands of the current insn (of which there are N_OPS) by
1174 substituting cc0 for them.
1175 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
1176 For every bit set in DO_NOT_HIDE, we leave the operand alone.
1177 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
1178 and earlyclobbers. */
1181 hide_operands (int n_ops, rtx *old_operands, rtx *old_dups,
1182 unsigned HOST_WIDE_INT do_not_hide, bool inout_and_ec_only)
1185 int alt = which_alternative;
1186 for (i = 0; i < n_ops; i++)
1188 old_operands[i] = recog_data.operand[i];
1189 /* Don't squash match_operator or match_parallel here, since
1190 we don't know that all of the contained registers are
1191 reachable by proper operands. */
1192 if (recog_data.constraints[i][0] == '\0')
1194 if (do_not_hide & (1 << i))
1196 if (!inout_and_ec_only || recog_data.operand_type[i] == OP_INOUT
1197 || recog_op_alt[i][alt].earlyclobber)
1198 *recog_data.operand_loc[i] = cc0_rtx;
1200 for (i = 0; i < recog_data.n_dups; i++)
1202 int opn = recog_data.dup_num[i];
1203 old_dups[i] = *recog_data.dup_loc[i];
1204 if (do_not_hide & (1 << opn))
1206 if (!inout_and_ec_only || recog_data.operand_type[opn] == OP_INOUT
1207 || recog_op_alt[opn][alt].earlyclobber)
1208 *recog_data.dup_loc[i] = cc0_rtx;
1212 /* Undo the substitution performed by hide_operands. INSN is the insn we
1213 are processing; the arguments are the same as in hide_operands. */
1216 restore_operands (rtx insn, int n_ops, rtx *old_operands, rtx *old_dups)
1219 for (i = 0; i < recog_data.n_dups; i++)
1220 *recog_data.dup_loc[i] = old_dups[i];
1221 for (i = 0; i < n_ops; i++)
1222 *recog_data.operand_loc[i] = old_operands[i];
1223 if (recog_data.n_dups)
1224 df_insn_rescan (insn);
1227 /* For each output operand of INSN, call scan_rtx to create a new
1228 open chain. Do this only for normal or earlyclobber outputs,
1229 depending on EARLYCLOBBER. */
1232 record_out_operands (rtx insn, bool earlyclobber)
1234 int n_ops = recog_data.n_operands;
1235 int alt = which_alternative;
1239 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1241 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1242 rtx *loc = (i < n_ops
1243 ? recog_data.operand_loc[opn]
1244 : recog_data.dup_loc[i - n_ops]);
1246 enum reg_class cl = recog_op_alt[opn][alt].cl;
1248 struct du_head *prev_open;
1250 if (recog_data.operand_type[opn] != OP_OUT
1251 || recog_op_alt[opn][alt].earlyclobber != earlyclobber)
1254 prev_open = open_chains;
1255 scan_rtx (insn, loc, cl, mark_write, OP_OUT);
1257 /* ??? Many targets have output constraints on the SET_DEST
1258 of a call insn, which is stupid, since these are certainly
1259 ABI defined hard registers. For these, and for asm operands
1260 that originally referenced hard registers, we must record that
1261 the chain cannot be renamed. */
1263 || (asm_noperands (PATTERN (insn)) > 0
1265 && REGNO (op) == ORIGINAL_REGNO (op)))
1267 if (prev_open != open_chains)
1268 open_chains->cannot_rename = 1;
1273 /* Build def/use chain. */
1275 static struct du_head *
1276 build_def_use (basic_block bb)
1280 unsigned HOST_WIDE_INT untracked_operands;
1282 open_chains = closed_chains = NULL;
1284 fail_current_block = false;
1287 bitmap_initialize (&open_chains_set, &bitmap_default_obstack);
1288 CLEAR_HARD_REG_SET (live_in_chains);
1289 REG_SET_TO_HARD_REG_SET (live_hard_regs, df_get_live_in (bb));
1290 for (def_rec = df_get_artificial_defs (bb->index); *def_rec; def_rec++)
1292 df_ref def = *def_rec;
1293 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
1294 SET_HARD_REG_BIT (live_hard_regs, DF_REF_REGNO (def));
1297 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
1299 if (NONDEBUG_INSN_P (insn))
1303 rtx old_operands[MAX_RECOG_OPERANDS];
1304 rtx old_dups[MAX_DUP_OPERANDS];
1308 enum rtx_code set_code = SET;
1309 enum rtx_code clobber_code = CLOBBER;
1311 /* Process the insn, determining its effect on the def-use
1312 chains and live hard registers. We perform the following
1313 steps with the register references in the insn, simulating
1315 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1316 by creating chains and marking hard regs live.
1317 (2) Any read outside an operand causes any chain it overlaps
1318 with to be marked unrenamable.
1319 (3) Any read inside an operand is added if there's already
1320 an open chain for it.
1321 (4) For any REG_DEAD note we find, close open chains that
1323 (5) For any non-earlyclobber write we find, close open chains
1325 (6) For any non-earlyclobber write we find in an operand, make
1326 a new chain or mark the hard register as live.
1327 (7) For any REG_UNUSED, close any chains we just opened.
1329 We cannot deal with situations where we track a reg in one mode
1330 and see a reference in another mode; these will cause the chain
1331 to be marked unrenamable or even cause us to abort the entire
1334 extract_insn (insn);
1335 if (! constrain_operands (1))
1336 fatal_insn_not_found (insn);
1337 preprocess_constraints ();
1338 alt = which_alternative;
1339 n_ops = recog_data.n_operands;
1340 untracked_operands = 0;
1342 /* Simplify the code below by rewriting things to reflect
1343 matching constraints. Also promote OP_OUT to OP_INOUT in
1344 predicated instructions, but only for register operands
1345 that are already tracked, so that we can create a chain
1346 when the first SET makes a register live. */
1348 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC;
1349 for (i = 0; i < n_ops; ++i)
1351 rtx op = recog_data.operand[i];
1352 int matches = recog_op_alt[i][alt].matches;
1354 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl;
1355 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0
1356 || (predicated && recog_data.operand_type[i] == OP_OUT))
1358 recog_data.operand_type[i] = OP_INOUT;
1359 /* A special case to deal with instruction patterns that
1360 have matching operands with different modes. If we're
1361 not already tracking such a reg, we won't start here,
1362 and we must instead make sure to make the operand visible
1363 to the machinery that tracks hard registers. */
1365 && (GET_MODE_SIZE (recog_data.operand_mode[i])
1366 != GET_MODE_SIZE (recog_data.operand_mode[matches]))
1367 && !verify_reg_in_set (op, &live_in_chains))
1369 untracked_operands |= 1 << i;
1370 untracked_operands |= 1 << matches;
1373 /* If there's an in-out operand with a register that is not
1374 being tracked at all yet, open a chain. */
1375 if (recog_data.operand_type[i] == OP_INOUT
1376 && !(untracked_operands & (1 << i))
1378 && !verify_reg_tracked (op))
1380 enum machine_mode mode = GET_MODE (op);
1381 unsigned this_regno = REGNO (op);
1382 unsigned this_nregs = hard_regno_nregs[this_regno][mode];
1383 create_new_chain (this_regno, this_nregs, NULL, NULL_RTX,
1388 if (fail_current_block)
1391 /* Step 1a: Mark hard registers that are clobbered in this insn,
1392 outside an operand, as live. */
1393 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1395 note_stores (PATTERN (insn), note_sets_clobbers, &clobber_code);
1396 restore_operands (insn, n_ops, old_operands, old_dups);
1398 /* Step 1b: Begin new chains for earlyclobbered writes inside
1400 record_out_operands (insn, true);
1402 /* Step 2: Mark chains for which we have reads outside operands
1404 We do this by munging all operands into CC0, and closing
1405 everything remaining. */
1407 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1409 scan_rtx (insn, &PATTERN (insn), NO_REGS, mark_all_read, OP_IN);
1410 restore_operands (insn, n_ops, old_operands, old_dups);
1412 /* Step 2B: Can't rename function call argument registers. */
1413 if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn))
1414 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn),
1415 NO_REGS, mark_all_read, OP_IN);
1417 /* Step 2C: Can't rename asm operands that were originally
1419 if (asm_noperands (PATTERN (insn)) > 0)
1420 for (i = 0; i < n_ops; i++)
1422 rtx *loc = recog_data.operand_loc[i];
1426 && REGNO (op) == ORIGINAL_REGNO (op)
1427 && (recog_data.operand_type[i] == OP_IN
1428 || recog_data.operand_type[i] == OP_INOUT))
1429 scan_rtx (insn, loc, NO_REGS, mark_all_read, OP_IN);
1432 /* Step 3: Append to chains for reads inside operands. */
1433 for (i = 0; i < n_ops + recog_data.n_dups; i++)
1435 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops];
1436 rtx *loc = (i < n_ops
1437 ? recog_data.operand_loc[opn]
1438 : recog_data.dup_loc[i - n_ops]);
1439 enum reg_class cl = recog_op_alt[opn][alt].cl;
1440 enum op_type type = recog_data.operand_type[opn];
1442 /* Don't scan match_operand here, since we've no reg class
1443 information to pass down. Any operands that we could
1444 substitute in will be represented elsewhere. */
1445 if (recog_data.constraints[opn][0] == '\0'
1446 || untracked_operands & (1 << opn))
1449 if (recog_op_alt[opn][alt].is_address)
1450 scan_rtx_address (insn, loc, cl, mark_read, VOIDmode);
1452 scan_rtx (insn, loc, cl, mark_read, type);
1455 /* Step 3B: Record updates for regs in REG_INC notes, and
1456 source regs in REG_FRAME_RELATED_EXPR notes. */
1457 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1458 if (REG_NOTE_KIND (note) == REG_INC
1459 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1460 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read,
1463 /* Step 4: Close chains for registers that die here. */
1464 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1465 if (REG_NOTE_KIND (note) == REG_DEAD)
1467 remove_from_hard_reg_set (&live_hard_regs,
1468 GET_MODE (XEXP (note, 0)),
1469 REGNO (XEXP (note, 0)));
1470 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1474 /* Step 4B: If this is a call, any chain live at this point
1475 requires a caller-saved reg. */
1479 for (p = open_chains; p; p = p->next_chain)
1480 p->need_caller_save_reg = 1;
1483 /* Step 5: Close open chains that overlap writes. Similar to
1484 step 2, we hide in-out operands, since we do not want to
1485 close these chains. We also hide earlyclobber operands,
1486 since we've opened chains for them in step 1, and earlier
1487 chains they would overlap with must have been closed at
1488 the previous insn at the latest, as such operands cannot
1489 possibly overlap with any input operands. */
1491 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1493 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN);
1494 restore_operands (insn, n_ops, old_operands, old_dups);
1496 /* Step 6a: Mark hard registers that are set in this insn,
1497 outside an operand, as live. */
1498 hide_operands (n_ops, old_operands, old_dups, untracked_operands,
1500 note_stores (PATTERN (insn), note_sets_clobbers, &set_code);
1501 restore_operands (insn, n_ops, old_operands, old_dups);
1503 /* Step 6b: Begin new chains for writes inside operands. */
1504 record_out_operands (insn, false);
1506 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1507 notes for update. */
1508 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1509 if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR)
1510 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access,
1513 /* Step 7: Close chains for registers that were never
1514 really used here. */
1515 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1516 if (REG_NOTE_KIND (note) == REG_UNUSED)
1518 remove_from_hard_reg_set (&live_hard_regs,
1519 GET_MODE (XEXP (note, 0)),
1520 REGNO (XEXP (note, 0)));
1521 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead,
1525 else if (DEBUG_INSN_P (insn)
1526 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn)))
1528 scan_rtx (insn, &INSN_VAR_LOCATION_LOC (insn),
1529 ALL_REGS, mark_read, OP_IN);
1531 if (insn == BB_END (bb))
1535 bitmap_clear (&open_chains_set);
1537 if (fail_current_block)
1540 /* Since we close every chain when we find a REG_DEAD note, anything that
1541 is still open lives past the basic block, so it can't be renamed. */
1542 return closed_chains;
1545 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
1546 printed in reverse order as that's how we build them. */
1549 dump_def_use_chain (struct du_head *head)
1553 struct du_chain *this_du = head->first;
1554 fprintf (dump_file, "Register %s (%d):",
1555 reg_names[head->regno], head->nregs);
1558 fprintf (dump_file, " %d [%s]", INSN_UID (this_du->insn),
1559 reg_class_names[this_du->cl]);
1560 this_du = this_du->next_use;
1562 fprintf (dump_file, "\n");
1563 head = head->next_chain;
1569 gate_handle_regrename (void)
1571 return (optimize > 0 && (flag_rename_registers));
1574 struct rtl_opt_pass pass_regrename =
1579 gate_handle_regrename, /* gate */
1580 regrename_optimize, /* execute */
1583 0, /* static_pass_number */
1584 TV_RENAME_REGISTERS, /* tv_id */
1585 0, /* properties_required */
1586 0, /* properties_provided */
1587 0, /* properties_destroyed */
1588 0, /* todo_flags_start */
1589 TODO_df_finish | TODO_verify_rtl_sharing |
1590 TODO_dump_func /* todo_flags_finish */