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 #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 /* Describes the register being tracked. */
56 unsigned regno
, nregs
;
58 /* A unique id to be used as an index into the conflicts bitmaps. */
60 /* A bitmap to record conflicts with other chains. */
61 bitmap_head conflicts
;
62 /* Conflicts with untracked hard registers. */
63 HARD_REG_SET hard_conflicts
;
65 /* Nonzero if the chain is finished; zero if it is still open. */
66 unsigned int terminated
:1;
67 /* Nonzero if the chain crosses a call. */
68 unsigned int need_caller_save_reg
:1;
69 /* Nonzero if the register is used in a way that prevents renaming,
70 such as the SET_DEST of a CALL_INSN or an asm operand that used
71 to be a hard register. */
72 unsigned int cannot_rename
:1;
75 /* This struct describes a single occurrence of a register. */
78 /* Links to the next occurrence of the register. */
79 struct du_chain
*next_use
;
81 /* The insn where the register appears. */
83 /* The location inside the insn. */
85 /* The register class required by the insn at this location. */
86 ENUM_BITFIELD(reg_class
) cl
: 16;
96 /* mark_access is for marking the destination regs in
97 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the
98 note is updated properly. */
102 static const char * const scan_actions_name
[] =
112 static struct obstack rename_obstack
;
114 static void do_replace (struct du_head
*, int);
115 static void scan_rtx_reg (rtx
, rtx
*, enum reg_class
,
116 enum scan_actions
, enum op_type
);
117 static void scan_rtx_address (rtx
, rtx
*, enum reg_class
,
118 enum scan_actions
, enum machine_mode
);
119 static void scan_rtx (rtx
, rtx
*, enum reg_class
, enum scan_actions
,
121 static struct du_head
*build_def_use (basic_block
);
122 static void dump_def_use_chain (struct du_head
*);
124 typedef struct du_head
*du_head_p
;
125 DEF_VEC_P (du_head_p
);
126 DEF_VEC_ALLOC_P (du_head_p
, heap
);
127 static VEC(du_head_p
, heap
) *id_to_chain
;
130 free_chain_data (void)
134 for (i
= 0; VEC_iterate(du_head_p
, id_to_chain
, i
, ptr
); i
++)
135 bitmap_clear (&ptr
->conflicts
);
137 VEC_free (du_head_p
, heap
, id_to_chain
);
140 /* For a def-use chain HEAD, find which registers overlap its lifetime and
141 set the corresponding bits in *PSET. */
144 merge_overlapping_regs (HARD_REG_SET
*pset
, struct du_head
*head
)
148 IOR_HARD_REG_SET (*pset
, head
->hard_conflicts
);
149 EXECUTE_IF_SET_IN_BITMAP (&head
->conflicts
, 0, i
, bi
)
151 du_head_p other
= VEC_index (du_head_p
, id_to_chain
, i
);
152 unsigned j
= other
->nregs
;
154 SET_HARD_REG_BIT (*pset
, other
->regno
+ j
);
158 /* Perform register renaming on the current function. */
161 regrename_optimize (void)
163 int tick
[FIRST_PSEUDO_REGISTER
];
168 df_set_flags (DF_LR_RUN_DCE
);
169 df_note_add_problem ();
171 df_set_flags (DF_DEFER_INSN_RESCAN
);
173 memset (tick
, 0, sizeof tick
);
175 gcc_obstack_init (&rename_obstack
);
176 first_obj
= XOBNEWVAR (&rename_obstack
, char, 0);
180 struct du_head
*all_chains
= 0;
181 HARD_REG_SET unavailable
;
183 HARD_REG_SET regs_seen
;
184 CLEAR_HARD_REG_SET (regs_seen
);
187 id_to_chain
= VEC_alloc (du_head_p
, heap
, 0);
189 CLEAR_HARD_REG_SET (unavailable
);
192 fprintf (dump_file
, "\nBasic block %d:\n", bb
->index
);
194 all_chains
= build_def_use (bb
);
197 dump_def_use_chain (all_chains
);
199 CLEAR_HARD_REG_SET (unavailable
);
200 /* Don't clobber traceback for noreturn functions. */
201 if (frame_pointer_needed
)
203 add_to_hard_reg_set (&unavailable
, Pmode
, FRAME_POINTER_REGNUM
);
204 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
205 add_to_hard_reg_set (&unavailable
, Pmode
, HARD_FRAME_POINTER_REGNUM
);
211 int new_reg
, best_new_reg
, best_nregs
;
213 struct du_head
*this_head
= all_chains
;
214 struct du_chain
*tmp
;
215 HARD_REG_SET this_unavailable
;
216 int reg
= this_head
->regno
;
219 all_chains
= this_head
->next_chain
;
221 if (this_head
->cannot_rename
)
225 best_nregs
= this_head
->nregs
;
227 #if 0 /* This just disables optimization opportunities. */
228 /* Only rename once we've seen the reg more than once. */
229 if (! TEST_HARD_REG_BIT (regs_seen
, reg
))
231 SET_HARD_REG_BIT (regs_seen
, reg
);
236 if (fixed_regs
[reg
] || global_regs
[reg
]
237 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
238 || (frame_pointer_needed
&& reg
== HARD_FRAME_POINTER_REGNUM
)
240 || (frame_pointer_needed
&& reg
== FRAME_POINTER_REGNUM
)
245 COPY_HARD_REG_SET (this_unavailable
, unavailable
);
247 /* Count number of uses, and narrow the set of registers we can
250 for (tmp
= this_head
->first
; tmp
; tmp
= tmp
->next_use
)
252 if (DEBUG_INSN_P (tmp
->insn
))
255 IOR_COMPL_HARD_REG_SET (this_unavailable
,
256 reg_class_contents
[tmp
->cl
]);
262 if (this_head
->need_caller_save_reg
)
263 IOR_HARD_REG_SET (this_unavailable
, call_used_reg_set
);
265 merge_overlapping_regs (&this_unavailable
, this_head
);
267 /* Now potential_regs is a reasonable approximation, let's
268 have a closer look at each register still in there. */
269 for (new_reg
= 0; new_reg
< FIRST_PSEUDO_REGISTER
; new_reg
++)
271 enum machine_mode mode
= GET_MODE (*this_head
->first
->loc
);
272 int nregs
= hard_regno_nregs
[new_reg
][mode
];
274 for (i
= nregs
- 1; i
>= 0; --i
)
275 if (TEST_HARD_REG_BIT (this_unavailable
, new_reg
+ i
)
276 || fixed_regs
[new_reg
+ i
]
277 || global_regs
[new_reg
+ i
]
278 /* Can't use regs which aren't saved by the prologue. */
279 || (! df_regs_ever_live_p (new_reg
+ i
)
280 && ! call_used_regs
[new_reg
+ i
])
281 #ifdef LEAF_REGISTERS
282 /* We can't use a non-leaf register if we're in a
284 || (current_function_is_leaf
285 && !LEAF_REGISTERS
[new_reg
+ i
])
287 #ifdef HARD_REGNO_RENAME_OK
288 || ! HARD_REGNO_RENAME_OK (reg
+ i
, new_reg
+ i
)
295 /* See whether it accepts all modes that occur in
296 definition and uses. */
297 for (tmp
= this_head
->first
; tmp
; tmp
= tmp
->next_use
)
298 if ((! HARD_REGNO_MODE_OK (new_reg
, GET_MODE (*tmp
->loc
))
299 && ! DEBUG_INSN_P (tmp
->insn
))
300 || (this_head
->need_caller_save_reg
301 && ! (HARD_REGNO_CALL_PART_CLOBBERED
302 (reg
, GET_MODE (*tmp
->loc
)))
303 && (HARD_REGNO_CALL_PART_CLOBBERED
304 (new_reg
, GET_MODE (*tmp
->loc
)))))
308 if (tick
[best_new_reg
] > tick
[new_reg
])
310 best_new_reg
= new_reg
;
318 fprintf (dump_file
, "Register %s in insn %d",
319 reg_names
[reg
], INSN_UID (this_head
->first
->insn
));
320 if (this_head
->need_caller_save_reg
)
321 fprintf (dump_file
, " crosses a call");
324 if (best_new_reg
== reg
)
326 tick
[reg
] = ++this_tick
;
328 fprintf (dump_file
, "; no available better choice\n");
333 fprintf (dump_file
, ", renamed as %s\n", reg_names
[best_new_reg
]);
335 do_replace (this_head
, best_new_reg
);
336 this_head
->regno
= best_new_reg
;
337 this_head
->nregs
= best_nregs
;
338 tick
[best_new_reg
] = ++this_tick
;
339 df_set_regs_ever_live (best_new_reg
, true);
343 obstack_free (&rename_obstack
, first_obj
);
346 obstack_free (&rename_obstack
, NULL
);
349 fputc ('\n', dump_file
);
355 do_replace (struct du_head
*head
, int reg
)
357 struct du_chain
*chain
;
358 unsigned int base_regno
= head
->regno
;
359 bool found_note
= false;
361 gcc_assert (! DEBUG_INSN_P (head
->first
->insn
));
363 for (chain
= head
->first
; chain
; chain
= chain
->next_use
)
365 unsigned int regno
= ORIGINAL_REGNO (*chain
->loc
);
366 struct reg_attrs
*attr
= REG_ATTRS (*chain
->loc
);
367 int reg_ptr
= REG_POINTER (*chain
->loc
);
369 if (DEBUG_INSN_P (chain
->insn
) && REGNO (*chain
->loc
) != base_regno
)
370 INSN_VAR_LOCATION_LOC (chain
->insn
) = gen_rtx_UNKNOWN_VAR_LOC ();
375 *chain
->loc
= gen_raw_REG (GET_MODE (*chain
->loc
), reg
);
376 if (regno
>= FIRST_PSEUDO_REGISTER
)
377 ORIGINAL_REGNO (*chain
->loc
) = regno
;
378 REG_ATTRS (*chain
->loc
) = attr
;
379 REG_POINTER (*chain
->loc
) = reg_ptr
;
381 for (note
= REG_NOTES (chain
->insn
); note
; note
= XEXP (note
, 1))
383 enum reg_note kind
= REG_NOTE_KIND (note
);
384 if (kind
== REG_DEAD
|| kind
== REG_UNUSED
)
386 rtx reg
= XEXP (note
, 0);
387 gcc_assert (HARD_REGISTER_P (reg
));
389 if (REGNO (reg
) == base_regno
)
393 && reg_set_p (*chain
->loc
, chain
->insn
))
394 remove_note (chain
->insn
, note
);
396 XEXP (note
, 0) = *chain
->loc
;
403 df_insn_rescan (chain
->insn
);
407 /* If the chain's first insn is the same as the last, we should have
408 found a REG_UNUSED note. */
409 gcc_assert (head
->first
->insn
!= head
->last
->insn
);
410 if (!reg_set_p (*head
->last
->loc
, head
->last
->insn
))
411 add_reg_note (head
->last
->insn
, REG_DEAD
, *head
->last
->loc
);
416 /* Walk all chains starting with CHAINS and record that they conflict with
417 another chain whose id is ID. */
420 mark_conflict (struct du_head
*chains
, unsigned id
)
424 bitmap_set_bit (&chains
->conflicts
, id
);
425 chains
= chains
->next_chain
;
429 /* True if we found a register with a size mismatch, which means that we
430 can't track its lifetime accurately. If so, we abort the current block
432 static bool fail_current_block
;
434 /* The id to be given to the next opened chain. */
435 static unsigned current_id
;
437 /* List of currently open chains, and closed chains that can be renamed. */
438 static struct du_head
*open_chains
;
439 static struct du_head
*closed_chains
;
441 /* Bitmap of open chains. The bits set always match the list found in
443 static bitmap_head open_chains_set
;
445 /* Record the registers being tracked in open_chains. */
446 static HARD_REG_SET live_in_chains
;
448 /* Record the registers that are live but not tracked. The intersection
449 between this and live_in_chains is empty. */
450 static HARD_REG_SET live_hard_regs
;
452 /* Return true if OP is a reg for which all bits are set in PSET, false
453 if all bits are clear.
454 In other cases, set fail_current_block and return false. */
457 verify_reg_in_set (rtx op
, HARD_REG_SET
*pset
)
459 unsigned regno
, nregs
;
460 bool all_live
, all_dead
;
465 nregs
= hard_regno_nregs
[regno
][GET_MODE (op
)];
466 all_live
= all_dead
= true;
468 if (TEST_HARD_REG_BIT (*pset
, regno
+ nregs
))
472 if (!all_dead
&& !all_live
)
474 fail_current_block
= true;
480 /* Return true if OP is a reg that is being tracked already in some form.
481 May set fail_current_block if it sees an unhandled case of overlap. */
484 verify_reg_tracked (rtx op
)
486 return (verify_reg_in_set (op
, &live_hard_regs
)
487 || verify_reg_in_set (op
, &live_in_chains
));
490 /* Called through note_stores. DATA points to a rtx_code, either SET or
491 CLOBBER, which tells us which kind of rtx to look at. If we have a
492 match, record the set register in live_hard_regs and in the hard_conflicts
493 bitmap of open chains. */
496 note_sets_clobbers (rtx x
, const_rtx set
, void *data
)
498 enum rtx_code code
= *(enum rtx_code
*)data
;
499 struct du_head
*chain
;
501 if (GET_CODE (x
) == SUBREG
)
503 if (!REG_P (x
) || GET_CODE (set
) != code
)
505 /* There must not be pseudos at this point. */
506 gcc_assert (HARD_REGISTER_P (x
));
507 add_to_hard_reg_set (&live_hard_regs
, GET_MODE (x
), REGNO (x
));
508 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
509 add_to_hard_reg_set (&chain
->hard_conflicts
, GET_MODE (x
), REGNO (x
));
513 scan_rtx_reg (rtx insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
518 enum machine_mode mode
= GET_MODE (x
);
519 unsigned this_regno
= REGNO (x
);
520 unsigned this_nregs
= hard_regno_nregs
[this_regno
][mode
];
522 if (action
== mark_write
)
526 struct du_head
*head
= XOBNEW (&rename_obstack
, struct du_head
);
527 struct du_chain
*this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
530 head
->next_chain
= open_chains
;
532 head
->first
= head
->last
= this_du
;
533 head
->regno
= this_regno
;
534 head
->nregs
= this_nregs
;
535 head
->need_caller_save_reg
= 0;
536 head
->cannot_rename
= 0;
537 head
->terminated
= 0;
539 VEC_safe_push (du_head_p
, heap
, id_to_chain
, head
);
540 head
->id
= current_id
++;
542 bitmap_initialize (&head
->conflicts
, &bitmap_default_obstack
);
543 bitmap_copy (&head
->conflicts
, &open_chains_set
);
544 mark_conflict (open_chains
, head
->id
);
546 /* Since we're tracking this as a chain now, remove it from the
547 list of conflicting live hard registers and track it in
548 live_in_chains instead. */
552 SET_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
553 CLEAR_HARD_REG_BIT (live_hard_regs
, head
->regno
+ nregs
);
556 COPY_HARD_REG_SET (head
->hard_conflicts
, live_hard_regs
);
557 bitmap_set_bit (&open_chains_set
, head
->id
);
561 this_du
->next_use
= 0;
563 this_du
->insn
= insn
;
568 "Creating chain %s (%d) at insn %d (%s)\n",
569 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
570 scan_actions_name
[(int) action
]);
575 if ((type
== OP_OUT
) != (action
== terminate_write
|| action
== mark_access
))
578 for (p
= &open_chains
; *p
;)
580 struct du_head
*head
= *p
;
581 struct du_head
*next
= head
->next_chain
;
582 int exact_match
= (head
->regno
== this_regno
583 && head
->nregs
== this_nregs
);
584 int superset
= (this_regno
<= head
->regno
585 && this_regno
+ this_nregs
>= head
->regno
+ head
->nregs
);
586 int subset
= (this_regno
>= head
->regno
587 && this_regno
+ this_nregs
<= head
->regno
+ head
->nregs
);
590 || head
->regno
+ head
->nregs
<= this_regno
591 || this_regno
+ this_nregs
<= head
->regno
)
593 p
= &head
->next_chain
;
597 if (action
== mark_read
|| action
== mark_access
)
599 /* ??? Class NO_REGS can happen if the md file makes use of
600 EXTRA_CONSTRAINTS to match registers. Which is arguably
601 wrong, but there we are. */
603 if (cl
== NO_REGS
|| (!exact_match
&& !DEBUG_INSN_P (insn
)))
607 "Cannot rename chain %s (%d) at insn %d (%s)\n",
608 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
609 scan_actions_name
[(int) action
]);
610 head
->cannot_rename
= 1;
613 unsigned nregs
= this_nregs
;
614 head
->regno
= this_regno
;
615 head
->nregs
= this_nregs
;
617 SET_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
620 "Widening register in chain %s (%d) at insn %d\n",
621 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
));
625 fail_current_block
= true;
628 "Failing basic block due to unhandled overlap\n");
633 struct du_chain
*this_du
;
634 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
635 this_du
->next_use
= 0;
637 this_du
->insn
= insn
;
639 head
->last
->next_use
= this_du
;
640 head
->last
= this_du
;
643 /* Avoid adding the same location in a DEBUG_INSN multiple times,
644 which could happen with non-exact overlap. */
645 if (DEBUG_INSN_P (insn
))
647 /* Otherwise, find any other chains that do not match exactly;
648 ensure they all get marked unrenamable. */
649 p
= &head
->next_chain
;
653 /* Whether the terminated chain can be used for renaming
654 depends on the action and this being an exact match.
655 In either case, we remove this element from open_chains. */
657 if ((action
== terminate_dead
|| action
== terminate_write
)
662 head
->terminated
= 1;
663 head
->next_chain
= closed_chains
;
664 closed_chains
= head
;
665 bitmap_clear_bit (&open_chains_set
, head
->id
);
669 CLEAR_HARD_REG_BIT (live_in_chains
, head
->regno
+ nregs
);
674 "Closing chain %s (%d) at insn %d (%s)\n",
675 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
676 scan_actions_name
[(int) action
]);
678 else if (action
== terminate_dead
|| action
== terminate_write
)
680 /* In this case, tracking liveness gets too hard. Fail the
681 entire basic block. */
684 "Failing basic block due to unhandled overlap\n");
685 fail_current_block
= true;
690 head
->cannot_rename
= 1;
693 "Cannot rename chain %s (%d) at insn %d (%s)\n",
694 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
695 scan_actions_name
[(int) action
]);
696 p
= &head
->next_chain
;
701 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
702 BASE_REG_CLASS depending on how the register is being considered. */
705 scan_rtx_address (rtx insn
, rtx
*loc
, enum reg_class cl
,
706 enum scan_actions action
, enum machine_mode mode
)
709 RTX_CODE code
= GET_CODE (x
);
713 if (action
== mark_write
|| action
== mark_access
)
720 rtx orig_op0
= XEXP (x
, 0);
721 rtx orig_op1
= XEXP (x
, 1);
722 RTX_CODE code0
= GET_CODE (orig_op0
);
723 RTX_CODE code1
= GET_CODE (orig_op1
);
728 enum rtx_code index_code
= SCRATCH
;
730 if (GET_CODE (op0
) == SUBREG
)
732 op0
= SUBREG_REG (op0
);
733 code0
= GET_CODE (op0
);
736 if (GET_CODE (op1
) == SUBREG
)
738 op1
= SUBREG_REG (op1
);
739 code1
= GET_CODE (op1
);
742 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
743 || code0
== ZERO_EXTEND
|| code1
== MEM
)
747 index_code
= GET_CODE (*locI
);
749 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
750 || code1
== ZERO_EXTEND
|| code0
== MEM
)
754 index_code
= GET_CODE (*locI
);
756 else if (code0
== CONST_INT
|| code0
== CONST
757 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
760 index_code
= GET_CODE (XEXP (x
, 0));
762 else if (code1
== CONST_INT
|| code1
== CONST
763 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
766 index_code
= GET_CODE (XEXP (x
, 1));
768 else if (code0
== REG
&& code1
== REG
)
771 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
773 if (REGNO_OK_FOR_INDEX_P (regno1
)
774 && regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
776 else if (REGNO_OK_FOR_INDEX_P (regno0
)
777 && regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
779 else if (regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
)
780 || REGNO_OK_FOR_INDEX_P (regno1
))
782 else if (regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
787 locI
= &XEXP (x
, index_op
);
788 locB
= &XEXP (x
, !index_op
);
789 index_code
= GET_CODE (*locI
);
791 else if (code0
== REG
)
795 index_code
= GET_CODE (*locI
);
797 else if (code1
== REG
)
801 index_code
= GET_CODE (*locI
);
805 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
);
807 scan_rtx_address (insn
, locB
, base_reg_class (mode
, PLUS
, index_code
),
820 /* If the target doesn't claim to handle autoinc, this must be
821 something special, like a stack push. Kill this chain. */
822 action
= mark_all_read
;
827 scan_rtx_address (insn
, &XEXP (x
, 0),
828 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
833 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
);
840 fmt
= GET_RTX_FORMAT (code
);
841 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
844 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
);
845 else if (fmt
[i
] == 'E')
846 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
847 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
);
852 scan_rtx (rtx insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
857 enum rtx_code code
= GET_CODE (x
);
875 scan_rtx_reg (insn
, loc
, cl
, action
, type
);
879 scan_rtx_address (insn
, &XEXP (x
, 0),
880 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
885 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
);
886 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
887 (GET_CODE (PATTERN (insn
)) == COND_EXEC
888 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
891 case STRICT_LOW_PART
:
892 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
893 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
);
898 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
899 (type
== OP_IN
? OP_IN
:
900 verify_reg_tracked (XEXP (x
, 0)) ? OP_INOUT
: OP_OUT
));
901 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
);
902 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
);
911 /* Should only happen inside MEM. */
915 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
916 (GET_CODE (PATTERN (insn
)) == COND_EXEC
917 && verify_reg_tracked (SET_DEST (x
))) ? OP_INOUT
: OP_OUT
);
921 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
);
923 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
);
930 fmt
= GET_RTX_FORMAT (code
);
931 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
934 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
);
935 else if (fmt
[i
] == 'E')
936 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
937 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
);
941 /* Hide operands of the current insn (of which there are N_OPS) by
942 substituting cc0 for them.
943 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
944 For every bit set in DO_NOT_HIDE, we leave the operand alone.
945 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
946 and earlyclobbers. */
949 hide_operands (int n_ops
, rtx
*old_operands
, rtx
*old_dups
,
950 unsigned HOST_WIDE_INT do_not_hide
, bool inout_and_ec_only
)
953 int alt
= which_alternative
;
954 for (i
= 0; i
< n_ops
; i
++)
956 old_operands
[i
] = recog_data
.operand
[i
];
957 /* Don't squash match_operator or match_parallel here, since
958 we don't know that all of the contained registers are
959 reachable by proper operands. */
960 if (recog_data
.constraints
[i
][0] == '\0')
962 if (do_not_hide
& (1 << i
))
964 if (!inout_and_ec_only
|| recog_data
.operand_type
[i
] == OP_INOUT
965 || recog_op_alt
[i
][alt
].earlyclobber
)
966 *recog_data
.operand_loc
[i
] = cc0_rtx
;
968 for (i
= 0; i
< recog_data
.n_dups
; i
++)
970 int opn
= recog_data
.dup_num
[i
];
971 old_dups
[i
] = *recog_data
.dup_loc
[i
];
972 if (do_not_hide
& (1 << opn
))
974 if (!inout_and_ec_only
|| recog_data
.operand_type
[opn
] == OP_INOUT
975 || recog_op_alt
[opn
][alt
].earlyclobber
)
976 *recog_data
.dup_loc
[i
] = cc0_rtx
;
980 /* Undo the substitution performed by hide_operands. INSN is the insn we
981 are processing; the arguments are the same as in hide_operands. */
984 restore_operands (rtx insn
, int n_ops
, rtx
*old_operands
, rtx
*old_dups
)
987 for (i
= 0; i
< recog_data
.n_dups
; i
++)
988 *recog_data
.dup_loc
[i
] = old_dups
[i
];
989 for (i
= 0; i
< n_ops
; i
++)
990 *recog_data
.operand_loc
[i
] = old_operands
[i
];
991 if (recog_data
.n_dups
)
992 df_insn_rescan (insn
);
995 /* For each output operand of INSN, call scan_rtx to create a new
996 open chain. Do this only for normal or earlyclobber outputs,
997 depending on EARLYCLOBBER. */
1000 record_out_operands (rtx insn
, bool earlyclobber
)
1002 int n_ops
= recog_data
.n_operands
;
1003 int alt
= which_alternative
;
1007 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1009 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1010 rtx
*loc
= (i
< n_ops
1011 ? recog_data
.operand_loc
[opn
]
1012 : recog_data
.dup_loc
[i
- n_ops
]);
1014 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
1016 struct du_head
*prev_open
;
1018 if (recog_data
.operand_type
[opn
] != OP_OUT
1019 || recog_op_alt
[opn
][alt
].earlyclobber
!= earlyclobber
)
1022 prev_open
= open_chains
;
1023 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
);
1025 /* ??? Many targets have output constraints on the SET_DEST
1026 of a call insn, which is stupid, since these are certainly
1027 ABI defined hard registers. For these, and for asm operands
1028 that originally referenced hard registers, we must record that
1029 the chain cannot be renamed. */
1031 || (asm_noperands (PATTERN (insn
)) > 0
1033 && REGNO (op
) == ORIGINAL_REGNO (op
)))
1035 if (prev_open
!= open_chains
)
1036 open_chains
->cannot_rename
= 1;
1041 /* Build def/use chain. */
1043 static struct du_head
*
1044 build_def_use (basic_block bb
)
1048 unsigned HOST_WIDE_INT untracked_operands
;
1050 open_chains
= closed_chains
= NULL
;
1052 fail_current_block
= false;
1055 bitmap_initialize (&open_chains_set
, &bitmap_default_obstack
);
1056 CLEAR_HARD_REG_SET (live_in_chains
);
1057 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_in (bb
));
1058 for (def_rec
= df_get_artificial_defs (bb
->index
); *def_rec
; def_rec
++)
1060 df_ref def
= *def_rec
;
1061 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
1062 SET_HARD_REG_BIT (live_hard_regs
, DF_REF_REGNO (def
));
1065 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
1067 if (NONDEBUG_INSN_P (insn
))
1071 rtx old_operands
[MAX_RECOG_OPERANDS
];
1072 bool has_dup
[MAX_RECOG_OPERANDS
];
1073 rtx old_dups
[MAX_DUP_OPERANDS
];
1077 enum rtx_code set_code
= SET
;
1078 enum rtx_code clobber_code
= CLOBBER
;
1080 /* Process the insn, determining its effect on the def-use
1081 chains and live hard registers. We perform the following
1082 steps with the register references in the insn, simulating
1084 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
1085 by creating chains and marking hard regs live.
1086 (2) Any read outside an operand causes any chain it overlaps
1087 with to be marked unrenamable.
1088 (3) Any read inside an operand is added if there's already
1089 an open chain for it.
1090 (4) For any REG_DEAD note we find, close open chains that
1092 (5) For any non-earlyclobber write we find, close open chains
1094 (6) For any non-earlyclobber write we find in an operand, make
1095 a new chain or mark the hard register as live.
1096 (7) For any REG_UNUSED, close any chains we just opened.
1098 We cannot deal with situations where we track a reg in one mode
1099 and see a reference in another mode; these will cause the chain
1100 to be marked unrenamable or even cause us to abort the entire
1103 extract_insn (insn
);
1104 if (! constrain_operands (1))
1105 fatal_insn_not_found (insn
);
1106 preprocess_constraints ();
1107 alt
= which_alternative
;
1108 n_ops
= recog_data
.n_operands
;
1109 untracked_operands
= 0;
1111 memset (has_dup
, 0, sizeof has_dup
);
1112 for (i
= 0; i
< recog_data
.n_dups
; i
++)
1113 has_dup
[(int)recog_data
.dup_num
[i
]] = true;
1115 /* Simplify the code below by rewriting things to reflect
1116 matching constraints. Also promote OP_OUT to OP_INOUT in
1117 predicated instructions, but only for register operands
1118 that are already tracked, so that we can create a chain
1119 when the first SET makes a register live. */
1121 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1122 for (i
= 0; i
< n_ops
; ++i
)
1124 int matches
= recog_op_alt
[i
][alt
].matches
;
1126 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
1127 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
1128 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
1129 && verify_reg_tracked (recog_data
.operand
[i
])))
1131 rtx op
= recog_data
.operand
[i
];
1132 recog_data
.operand_type
[i
] = OP_INOUT
;
1133 /* A special case to deal with instruction patterns that
1134 have matching operands with different modes. If we're
1135 not already tracking such a reg, we won't start here,
1136 and we must instead make sure to make the operand visible
1137 to the machinery that tracks hard registers. */
1139 && (GET_MODE_SIZE (recog_data
.operand_mode
[i
])
1140 != GET_MODE_SIZE (recog_data
.operand_mode
[matches
]))
1141 && !verify_reg_in_set (op
, &live_in_chains
))
1143 untracked_operands
|= 1 << i
;
1144 untracked_operands
|= 1 << matches
;
1147 /* If there's an in-out operand with a register that is not
1148 being tracked at all yet, convert it to an earlyclobber
1150 This only works if the operand isn't duplicated, i.e. for
1151 a ZERO_EXTRACT in a SET_DEST. */
1152 if (recog_data
.operand_type
[i
] == OP_INOUT
1153 && !(untracked_operands
& (1 << i
))
1154 && !verify_reg_tracked (recog_data
.operand
[i
]))
1157 fail_current_block
= true;
1158 recog_data
.operand_type
[i
] = OP_OUT
;
1159 recog_op_alt
[i
][alt
].earlyclobber
= 1;
1163 if (fail_current_block
)
1166 /* Step 1a: Mark hard registers that are clobbered in this insn,
1167 outside an operand, as live. */
1168 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1170 note_stores (PATTERN (insn
), note_sets_clobbers
, &clobber_code
);
1171 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1173 /* Step 1b: Begin new chains for earlyclobbered writes inside
1175 record_out_operands (insn
, true);
1177 /* Step 2: Mark chains for which we have reads outside operands
1179 We do this by munging all operands into CC0, and closing
1180 everything remaining. */
1182 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1184 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, mark_all_read
, OP_IN
);
1185 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1187 /* Step 2B: Can't rename function call argument registers. */
1188 if (CALL_P (insn
) && CALL_INSN_FUNCTION_USAGE (insn
))
1189 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
1190 NO_REGS
, mark_all_read
, OP_IN
);
1192 /* Step 2C: Can't rename asm operands that were originally
1194 if (asm_noperands (PATTERN (insn
)) > 0)
1195 for (i
= 0; i
< n_ops
; i
++)
1197 rtx
*loc
= recog_data
.operand_loc
[i
];
1201 && REGNO (op
) == ORIGINAL_REGNO (op
)
1202 && (recog_data
.operand_type
[i
] == OP_IN
1203 || recog_data
.operand_type
[i
] == OP_INOUT
))
1204 scan_rtx (insn
, loc
, NO_REGS
, mark_all_read
, OP_IN
);
1207 /* Step 3: Append to chains for reads inside operands. */
1208 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1210 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1211 rtx
*loc
= (i
< n_ops
1212 ? recog_data
.operand_loc
[opn
]
1213 : recog_data
.dup_loc
[i
- n_ops
]);
1214 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
1215 enum op_type type
= recog_data
.operand_type
[opn
];
1217 /* Don't scan match_operand here, since we've no reg class
1218 information to pass down. Any operands that we could
1219 substitute in will be represented elsewhere. */
1220 if (recog_data
.constraints
[opn
][0] == '\0'
1221 || untracked_operands
& (1 << opn
))
1224 if (recog_op_alt
[opn
][alt
].is_address
)
1225 scan_rtx_address (insn
, loc
, cl
, mark_read
, VOIDmode
);
1227 scan_rtx (insn
, loc
, cl
, mark_read
, type
);
1230 /* Step 3B: Record updates for regs in REG_INC notes, and
1231 source regs in REG_FRAME_RELATED_EXPR notes. */
1232 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1233 if (REG_NOTE_KIND (note
) == REG_INC
1234 || REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1235 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
1238 /* Step 4: Close chains for registers that die here. */
1239 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1240 if (REG_NOTE_KIND (note
) == REG_DEAD
)
1242 remove_from_hard_reg_set (&live_hard_regs
,
1243 GET_MODE (XEXP (note
, 0)),
1244 REGNO (XEXP (note
, 0)));
1245 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1249 /* Step 4B: If this is a call, any chain live at this point
1250 requires a caller-saved reg. */
1254 for (p
= open_chains
; p
; p
= p
->next_chain
)
1255 p
->need_caller_save_reg
= 1;
1258 /* Step 5: Close open chains that overlap writes. Similar to
1259 step 2, we hide in-out operands, since we do not want to
1260 close these chains. We also hide earlyclobber operands,
1261 since we've opened chains for them in step 1, and earlier
1262 chains they would overlap with must have been closed at
1263 the previous insn at the latest, as such operands cannot
1264 possibly overlap with any input operands. */
1266 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1268 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
);
1269 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1271 /* Step 6a: Mark hard registers that are set in this insn,
1272 outside an operand, as live. */
1273 hide_operands (n_ops
, old_operands
, old_dups
, untracked_operands
,
1275 note_stores (PATTERN (insn
), note_sets_clobbers
, &set_code
);
1276 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1278 /* Step 6b: Begin new chains for writes inside operands. */
1279 record_out_operands (insn
, false);
1281 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1282 notes for update. */
1283 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1284 if (REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1285 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_access
,
1288 /* Step 7: Close chains for registers that were never
1289 really used here. */
1290 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1291 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
1293 remove_from_hard_reg_set (&live_hard_regs
,
1294 GET_MODE (XEXP (note
, 0)),
1295 REGNO (XEXP (note
, 0)));
1296 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1300 else if (DEBUG_INSN_P (insn
)
1301 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn
)))
1303 scan_rtx (insn
, &INSN_VAR_LOCATION_LOC (insn
),
1304 ALL_REGS
, mark_read
, OP_IN
);
1306 if (insn
== BB_END (bb
))
1310 bitmap_clear (&open_chains_set
);
1312 if (fail_current_block
)
1315 /* Since we close every chain when we find a REG_DEAD note, anything that
1316 is still open lives past the basic block, so it can't be renamed. */
1317 return closed_chains
;
1320 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
1321 printed in reverse order as that's how we build them. */
1324 dump_def_use_chain (struct du_head
*head
)
1328 struct du_chain
*this_du
= head
->first
;
1329 fprintf (dump_file
, "Register %s (%d):",
1330 reg_names
[head
->regno
], head
->nregs
);
1333 fprintf (dump_file
, " %d [%s]", INSN_UID (this_du
->insn
),
1334 reg_class_names
[this_du
->cl
]);
1335 this_du
= this_du
->next_use
;
1337 fprintf (dump_file
, "\n");
1338 head
= head
->next_chain
;
1344 gate_handle_regrename (void)
1346 return (optimize
> 0 && (flag_rename_registers
));
1349 struct rtl_opt_pass pass_regrename
=
1354 gate_handle_regrename
, /* gate */
1355 regrename_optimize
, /* execute */
1358 0, /* static_pass_number */
1359 TV_RENAME_REGISTERS
, /* tv_id */
1360 0, /* properties_required */
1361 0, /* properties_provided */
1362 0, /* properties_destroyed */
1363 0, /* todo_flags_start */
1364 TODO_df_finish
| TODO_verify_rtl_sharing
|
1365 TODO_dump_func
/* todo_flags_finish */