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 /* Called through note_stores. DATA points to a rtx_code, either SET or
444 CLOBBER, which tells us which kind of rtx to look at. If we have a
445 match, record the set register in live_hard_regs and in the hard_conflicts
446 bitmap of open chains. */
449 note_sets_clobbers (rtx x
, const_rtx set
, void *data
)
451 enum rtx_code code
= *(enum rtx_code
*)data
;
452 struct du_head
*chain
;
454 if (GET_CODE (x
) == SUBREG
)
456 if (!REG_P (x
) || GET_CODE (set
) != code
)
458 /* There must not be pseudos at this point. */
459 gcc_assert (HARD_REGISTER_P (x
));
460 add_to_hard_reg_set (&live_hard_regs
, GET_MODE (x
), REGNO (x
));
461 for (chain
= open_chains
; chain
; chain
= chain
->next_chain
)
462 add_to_hard_reg_set (&chain
->hard_conflicts
, GET_MODE (x
), REGNO (x
));
466 scan_rtx_reg (rtx insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
471 enum machine_mode mode
= GET_MODE (x
);
472 unsigned this_regno
= REGNO (x
);
473 unsigned this_nregs
= hard_regno_nregs
[this_regno
][mode
];
475 if (action
== mark_write
)
479 struct du_head
*head
= XOBNEW (&rename_obstack
, struct du_head
);
480 struct du_chain
*this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
483 head
->next_chain
= open_chains
;
485 head
->first
= head
->last
= this_du
;
486 head
->regno
= this_regno
;
487 head
->nregs
= this_nregs
;
488 head
->need_caller_save_reg
= 0;
489 head
->cannot_rename
= 0;
490 head
->terminated
= 0;
492 VEC_safe_push (du_head_p
, heap
, id_to_chain
, head
);
493 head
->id
= current_id
++;
495 bitmap_initialize (&head
->conflicts
, &bitmap_default_obstack
);
496 bitmap_copy (&head
->conflicts
, &open_chains_set
);
497 mark_conflict (open_chains
, head
->id
);
499 /* Since we're tracking this as a chain now, remove it from the
500 list of conflicting live hard registers. */
503 CLEAR_HARD_REG_BIT (live_hard_regs
, head
->regno
+ nregs
);
505 COPY_HARD_REG_SET (head
->hard_conflicts
, live_hard_regs
);
506 bitmap_set_bit (&open_chains_set
, head
->id
);
510 this_du
->next_use
= 0;
512 this_du
->insn
= insn
;
517 "Creating chain %s (%d) at insn %d (%s)\n",
518 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
519 scan_actions_name
[(int) action
]);
524 if ((type
== OP_OUT
) != (action
== terminate_write
|| action
== mark_access
))
527 for (p
= &open_chains
; *p
;)
529 struct du_head
*head
= *p
;
530 struct du_head
*next
= head
->next_chain
;
531 int exact_match
= (head
->regno
== this_regno
532 && head
->nregs
== this_nregs
);
533 int superset
= (this_regno
<= head
->regno
534 && this_regno
+ this_nregs
>= head
->regno
+ head
->nregs
);
537 || head
->regno
+ head
->nregs
<= this_regno
538 || this_regno
+ this_nregs
<= head
->regno
)
540 p
= &head
->next_chain
;
544 if (action
== mark_read
|| action
== mark_access
)
546 /* ??? Class NO_REGS can happen if the md file makes use of
547 EXTRA_CONSTRAINTS to match registers. Which is arguably
548 wrong, but there we are. */
550 if (cl
== NO_REGS
|| (!exact_match
&& !DEBUG_INSN_P (insn
)))
554 "Cannot rename chain %s (%d) at insn %d (%s)\n",
555 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
556 scan_actions_name
[(int) action
]);
557 head
->cannot_rename
= 1;
561 struct du_chain
*this_du
;
562 this_du
= XOBNEW (&rename_obstack
, struct du_chain
);
563 this_du
->next_use
= 0;
565 this_du
->insn
= insn
;
567 head
->last
->next_use
= this_du
;
568 head
->last
= this_du
;
571 /* Avoid adding the same location in a DEBUG_INSN multiple times,
572 which could happen with non-exact overlap. */
573 if (DEBUG_INSN_P (insn
))
575 /* Otherwise, find any other chains that do not match exactly;
576 ensure they all get marked unrenamable. */
577 p
= &head
->next_chain
;
581 /* Whether the terminated chain can be used for renaming
582 depends on the action and this being an exact match.
583 In either case, we remove this element from open_chains. */
585 if ((action
== terminate_dead
|| action
== terminate_write
)
588 head
->terminated
= 1;
589 head
->next_chain
= closed_chains
;
590 closed_chains
= head
;
591 bitmap_clear_bit (&open_chains_set
, head
->id
);
595 "Closing chain %s (%d) at insn %d (%s)\n",
596 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
597 scan_actions_name
[(int) action
]);
599 else if (action
== terminate_dead
|| action
== terminate_write
)
601 /* In this case, tracking liveness gets too hard. Fail the
602 entire basic block. */
605 "Failing basic block due to unhandled overlap\n");
606 fail_current_block
= true;
611 head
->cannot_rename
= 1;
614 "Cannot rename chain %s (%d) at insn %d (%s)\n",
615 reg_names
[head
->regno
], head
->id
, INSN_UID (insn
),
616 scan_actions_name
[(int) action
]);
617 p
= &head
->next_chain
;
622 /* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or
623 BASE_REG_CLASS depending on how the register is being considered. */
626 scan_rtx_address (rtx insn
, rtx
*loc
, enum reg_class cl
,
627 enum scan_actions action
, enum machine_mode mode
)
630 RTX_CODE code
= GET_CODE (x
);
634 if (action
== mark_write
|| action
== mark_access
)
641 rtx orig_op0
= XEXP (x
, 0);
642 rtx orig_op1
= XEXP (x
, 1);
643 RTX_CODE code0
= GET_CODE (orig_op0
);
644 RTX_CODE code1
= GET_CODE (orig_op1
);
649 enum rtx_code index_code
= SCRATCH
;
651 if (GET_CODE (op0
) == SUBREG
)
653 op0
= SUBREG_REG (op0
);
654 code0
= GET_CODE (op0
);
657 if (GET_CODE (op1
) == SUBREG
)
659 op1
= SUBREG_REG (op1
);
660 code1
= GET_CODE (op1
);
663 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
664 || code0
== ZERO_EXTEND
|| code1
== MEM
)
668 index_code
= GET_CODE (*locI
);
670 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
671 || code1
== ZERO_EXTEND
|| code0
== MEM
)
675 index_code
= GET_CODE (*locI
);
677 else if (code0
== CONST_INT
|| code0
== CONST
678 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
681 index_code
= GET_CODE (XEXP (x
, 0));
683 else if (code1
== CONST_INT
|| code1
== CONST
684 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
687 index_code
= GET_CODE (XEXP (x
, 1));
689 else if (code0
== REG
&& code1
== REG
)
692 unsigned regno0
= REGNO (op0
), regno1
= REGNO (op1
);
694 if (REGNO_OK_FOR_INDEX_P (regno1
)
695 && regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
))
697 else if (REGNO_OK_FOR_INDEX_P (regno0
)
698 && regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
700 else if (regno_ok_for_base_p (regno0
, mode
, PLUS
, REG
)
701 || REGNO_OK_FOR_INDEX_P (regno1
))
703 else if (regno_ok_for_base_p (regno1
, mode
, PLUS
, REG
))
708 locI
= &XEXP (x
, index_op
);
709 locB
= &XEXP (x
, !index_op
);
710 index_code
= GET_CODE (*locI
);
712 else if (code0
== REG
)
716 index_code
= GET_CODE (*locI
);
718 else if (code1
== REG
)
722 index_code
= GET_CODE (*locI
);
726 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
);
728 scan_rtx_address (insn
, locB
, base_reg_class (mode
, PLUS
, index_code
),
741 /* If the target doesn't claim to handle autoinc, this must be
742 something special, like a stack push. Kill this chain. */
743 action
= mark_all_read
;
748 scan_rtx_address (insn
, &XEXP (x
, 0),
749 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
754 scan_rtx_reg (insn
, loc
, cl
, action
, OP_IN
);
761 fmt
= GET_RTX_FORMAT (code
);
762 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
765 scan_rtx_address (insn
, &XEXP (x
, i
), cl
, action
, mode
);
766 else if (fmt
[i
] == 'E')
767 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
768 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), cl
, action
, mode
);
773 scan_rtx (rtx insn
, rtx
*loc
, enum reg_class cl
, enum scan_actions action
,
778 enum rtx_code code
= GET_CODE (x
);
796 scan_rtx_reg (insn
, loc
, cl
, action
, type
);
800 scan_rtx_address (insn
, &XEXP (x
, 0),
801 base_reg_class (GET_MODE (x
), MEM
, SCRATCH
), action
,
806 scan_rtx (insn
, &SET_SRC (x
), cl
, action
, OP_IN
);
807 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
808 GET_CODE (PATTERN (insn
)) == COND_EXEC
? OP_INOUT
: OP_OUT
);
811 case STRICT_LOW_PART
:
812 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, OP_INOUT
);
817 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
,
818 type
== OP_IN
? OP_IN
: OP_INOUT
);
819 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, OP_IN
);
820 scan_rtx (insn
, &XEXP (x
, 2), cl
, action
, OP_IN
);
829 /* Should only happen inside MEM. */
833 scan_rtx (insn
, &SET_DEST (x
), cl
, action
,
834 GET_CODE (PATTERN (insn
)) == COND_EXEC
? OP_INOUT
: OP_OUT
);
838 scan_rtx (insn
, &XEXP (x
, 0), cl
, action
, type
);
840 scan_rtx (insn
, &XEXP (x
, 1), cl
, action
, type
);
847 fmt
= GET_RTX_FORMAT (code
);
848 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
851 scan_rtx (insn
, &XEXP (x
, i
), cl
, action
, type
);
852 else if (fmt
[i
] == 'E')
853 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
854 scan_rtx (insn
, &XVECEXP (x
, i
, j
), cl
, action
, type
);
858 /* Hide operands of the current insn (of which there are N_OPS) by
859 substituting cc0 for them.
860 Previous values are stored in the OLD_OPERANDS and OLD_DUPS.
861 If INOUT_AND_EC_ONLY is set, we only do this for OP_INOUT type operands
862 and earlyclobbers. */
865 hide_operands (int n_ops
, rtx
*old_operands
, rtx
*old_dups
,
866 bool inout_and_ec_only
)
869 int alt
= which_alternative
;
870 for (i
= 0; i
< n_ops
; i
++)
872 old_operands
[i
] = recog_data
.operand
[i
];
873 /* Don't squash match_operator or match_parallel here, since
874 we don't know that all of the contained registers are
875 reachable by proper operands. */
876 if (recog_data
.constraints
[i
][0] == '\0')
878 if (!inout_and_ec_only
|| recog_data
.operand_type
[i
] == OP_INOUT
879 || recog_op_alt
[i
][alt
].earlyclobber
)
880 *recog_data
.operand_loc
[i
] = cc0_rtx
;
882 for (i
= 0; i
< recog_data
.n_dups
; i
++)
884 int opn
= recog_data
.dup_num
[i
];
885 old_dups
[i
] = *recog_data
.dup_loc
[i
];
886 if (!inout_and_ec_only
|| recog_data
.operand_type
[opn
] == OP_INOUT
887 || recog_op_alt
[opn
][alt
].earlyclobber
)
888 *recog_data
.dup_loc
[i
] = cc0_rtx
;
892 /* Undo the substitution performed by hide_operands. INSN is the insn we
893 are processing; the arguments are the same as in hide_operands. */
896 restore_operands (rtx insn
, int n_ops
, rtx
*old_operands
, rtx
*old_dups
)
899 for (i
= 0; i
< recog_data
.n_dups
; i
++)
900 *recog_data
.dup_loc
[i
] = old_dups
[i
];
901 for (i
= 0; i
< n_ops
; i
++)
902 *recog_data
.operand_loc
[i
] = old_operands
[i
];
903 if (recog_data
.n_dups
)
904 df_insn_rescan (insn
);
907 /* For each output operand of INSN, call scan_rtx to create a new
908 open chain. Do this only for normal or earlyclobber outputs,
909 depending on EARLYCLOBBER. */
912 record_out_operands (rtx insn
, bool earlyclobber
)
914 int n_ops
= recog_data
.n_operands
;
915 int alt
= which_alternative
;
919 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
921 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
922 rtx
*loc
= (i
< n_ops
923 ? recog_data
.operand_loc
[opn
]
924 : recog_data
.dup_loc
[i
- n_ops
]);
926 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
928 struct du_head
*prev_open
;
930 if (recog_data
.operand_type
[opn
] != OP_OUT
931 || recog_op_alt
[opn
][alt
].earlyclobber
!= earlyclobber
)
934 prev_open
= open_chains
;
935 scan_rtx (insn
, loc
, cl
, mark_write
, OP_OUT
);
937 /* ??? Many targets have output constraints on the SET_DEST
938 of a call insn, which is stupid, since these are certainly
939 ABI defined hard registers. For these, and for asm operands
940 that originally referenced hard registers, we must record that
941 the chain cannot be renamed. */
943 || (asm_noperands (PATTERN (insn
)) > 0
945 && REGNO (op
) == ORIGINAL_REGNO (op
)))
947 if (prev_open
!= open_chains
)
948 open_chains
->cannot_rename
= 1;
953 /* Build def/use chain. */
955 static struct du_head
*
956 build_def_use (basic_block bb
)
961 open_chains
= closed_chains
= NULL
;
963 fail_current_block
= false;
966 bitmap_initialize (&open_chains_set
, &bitmap_default_obstack
);
967 REG_SET_TO_HARD_REG_SET (live_hard_regs
, df_get_live_in (bb
));
968 for (def_rec
= df_get_artificial_defs (bb
->index
); *def_rec
; def_rec
++)
970 df_ref def
= *def_rec
;
971 if (DF_REF_FLAGS (def
) & DF_REF_AT_TOP
)
972 SET_HARD_REG_BIT (live_hard_regs
, DF_REF_REGNO (def
));
975 for (insn
= BB_HEAD (bb
); ; insn
= NEXT_INSN (insn
))
977 if (NONDEBUG_INSN_P (insn
))
981 rtx old_operands
[MAX_RECOG_OPERANDS
];
982 rtx old_dups
[MAX_DUP_OPERANDS
];
986 enum rtx_code set_code
= SET
;
987 enum rtx_code clobber_code
= CLOBBER
;
989 /* Process the insn, determining its effect on the def-use
990 chains and live hard registers. We perform the following
991 steps with the register references in the insn, simulating
993 (1) Deal with earlyclobber operands and CLOBBERs of non-operands
994 by creating chains and marking hard regs live.
995 (2) Any read outside an operand causes any chain it overlaps
996 with to be marked unrenamable.
997 (3) Any read inside an operand is added if there's already
998 an open chain for it.
999 (4) For any REG_DEAD note we find, close open chains that
1001 (5) For any non-earlyclobber write we find, close open chains
1003 (6) For any non-earlyclobber write we find in an operand, make
1004 a new chain or mark the hard register as live.
1005 (7) For any REG_UNUSED, close any chains we just opened.
1007 We cannot deal with situations where we track a reg in one mode
1008 and see a reference in another mode; these will cause the chain
1009 to be marked unrenamable or even cause us to abort the entire
1012 extract_insn (insn
);
1013 if (! constrain_operands (1))
1014 fatal_insn_not_found (insn
);
1015 preprocess_constraints ();
1016 alt
= which_alternative
;
1017 n_ops
= recog_data
.n_operands
;
1019 /* Simplify the code below by rewriting things to reflect
1020 matching constraints. Also promote OP_OUT to OP_INOUT
1021 in predicated instructions. */
1023 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
1024 for (i
= 0; i
< n_ops
; ++i
)
1026 int matches
= recog_op_alt
[i
][alt
].matches
;
1028 recog_op_alt
[i
][alt
].cl
= recog_op_alt
[matches
][alt
].cl
;
1029 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
1030 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
1032 recog_data
.operand_type
[i
] = OP_INOUT
;
1034 && (GET_MODE_SIZE (recog_data
.operand_mode
[i
])
1035 != GET_MODE_SIZE (recog_data
.operand_mode
[matches
])))
1036 fail_current_block
= true;
1040 if (fail_current_block
)
1043 /* Step 1a: Mark hard registers that are clobbered in this insn,
1044 outside an operand, as live. */
1045 hide_operands (n_ops
, old_operands
, old_dups
, false);
1046 note_stores (PATTERN (insn
), note_sets_clobbers
, &clobber_code
);
1047 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1049 /* Step 1b: Begin new chains for earlyclobbered writes inside
1051 record_out_operands (insn
, true);
1053 /* Step 2: Mark chains for which we have reads outside operands
1055 We do this by munging all operands into CC0, and closing
1056 everything remaining. */
1058 hide_operands (n_ops
, old_operands
, old_dups
, false);
1059 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, mark_all_read
, OP_IN
);
1060 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1062 /* Step 2B: Can't rename function call argument registers. */
1063 if (CALL_P (insn
) && CALL_INSN_FUNCTION_USAGE (insn
))
1064 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
1065 NO_REGS
, mark_all_read
, OP_IN
);
1067 /* Step 2C: Can't rename asm operands that were originally
1069 if (asm_noperands (PATTERN (insn
)) > 0)
1070 for (i
= 0; i
< n_ops
; i
++)
1072 rtx
*loc
= recog_data
.operand_loc
[i
];
1076 && REGNO (op
) == ORIGINAL_REGNO (op
)
1077 && (recog_data
.operand_type
[i
] == OP_IN
1078 || recog_data
.operand_type
[i
] == OP_INOUT
))
1079 scan_rtx (insn
, loc
, NO_REGS
, mark_all_read
, OP_IN
);
1082 /* Step 3: Append to chains for reads inside operands. */
1083 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
1085 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
1086 rtx
*loc
= (i
< n_ops
1087 ? recog_data
.operand_loc
[opn
]
1088 : recog_data
.dup_loc
[i
- n_ops
]);
1089 enum reg_class cl
= recog_op_alt
[opn
][alt
].cl
;
1090 enum op_type type
= recog_data
.operand_type
[opn
];
1092 /* Don't scan match_operand here, since we've no reg class
1093 information to pass down. Any operands that we could
1094 substitute in will be represented elsewhere. */
1095 if (recog_data
.constraints
[opn
][0] == '\0')
1098 if (recog_op_alt
[opn
][alt
].is_address
)
1099 scan_rtx_address (insn
, loc
, cl
, mark_read
, VOIDmode
);
1101 scan_rtx (insn
, loc
, cl
, mark_read
, type
);
1104 /* Step 3B: Record updates for regs in REG_INC notes, and
1105 source regs in REG_FRAME_RELATED_EXPR notes. */
1106 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1107 if (REG_NOTE_KIND (note
) == REG_INC
1108 || REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1109 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
,
1112 /* Step 4: Close chains for registers that die here. */
1113 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1114 if (REG_NOTE_KIND (note
) == REG_DEAD
)
1116 remove_from_hard_reg_set (&live_hard_regs
,
1117 GET_MODE (XEXP (note
, 0)),
1118 REGNO (XEXP (note
, 0)));
1119 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1123 /* Step 4B: If this is a call, any chain live at this point
1124 requires a caller-saved reg. */
1128 for (p
= open_chains
; p
; p
= p
->next_chain
)
1129 p
->need_caller_save_reg
= 1;
1132 /* Step 5: Close open chains that overlap writes. Similar to
1133 step 2, we hide in-out operands, since we do not want to
1134 close these chains. We also hide earlyclobber operands,
1135 since we've opened chains for them in step 1, and earlier
1136 chains they would overlap with must have been closed at
1137 the previous insn at the latest, as such operands cannot
1138 possibly overlap with any input operands. */
1140 hide_operands (n_ops
, old_operands
, old_dups
, true);
1141 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
);
1142 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1144 /* Step 6a: Mark hard registers that are set in this insn,
1145 outside an operand, as live. */
1146 hide_operands (n_ops
, old_operands
, old_dups
, false);
1147 note_stores (PATTERN (insn
), note_sets_clobbers
, &set_code
);
1148 restore_operands (insn
, n_ops
, old_operands
, old_dups
);
1150 /* Step 6b: Begin new chains for writes inside operands. */
1151 record_out_operands (insn
, false);
1153 /* Step 6c: Record destination regs in REG_FRAME_RELATED_EXPR
1154 notes for update. */
1155 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1156 if (REG_NOTE_KIND (note
) == REG_FRAME_RELATED_EXPR
)
1157 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_access
,
1160 /* Step 7: Close chains for registers that were never
1161 really used here. */
1162 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
1163 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
1165 remove_from_hard_reg_set (&live_hard_regs
,
1166 GET_MODE (XEXP (note
, 0)),
1167 REGNO (XEXP (note
, 0)));
1168 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
,
1172 else if (DEBUG_INSN_P (insn
)
1173 && !VAR_LOC_UNKNOWN_P (INSN_VAR_LOCATION_LOC (insn
)))
1175 scan_rtx (insn
, &INSN_VAR_LOCATION_LOC (insn
),
1176 ALL_REGS
, mark_read
, OP_IN
);
1178 if (insn
== BB_END (bb
))
1182 bitmap_clear (&open_chains_set
);
1184 if (fail_current_block
)
1187 /* Since we close every chain when we find a REG_DEAD note, anything that
1188 is still open lives past the basic block, so it can't be renamed. */
1189 return closed_chains
;
1192 /* Dump all def/use chains in CHAINS to DUMP_FILE. They are
1193 printed in reverse order as that's how we build them. */
1196 dump_def_use_chain (struct du_head
*head
)
1200 struct du_chain
*this_du
= head
->first
;
1201 fprintf (dump_file
, "Register %s (%d):",
1202 reg_names
[head
->regno
], head
->nregs
);
1205 fprintf (dump_file
, " %d [%s]", INSN_UID (this_du
->insn
),
1206 reg_class_names
[this_du
->cl
]);
1207 this_du
= this_du
->next_use
;
1209 fprintf (dump_file
, "\n");
1210 head
= head
->next_chain
;
1216 gate_handle_regrename (void)
1218 return (optimize
> 0 && (flag_rename_registers
));
1221 struct rtl_opt_pass pass_regrename
=
1226 gate_handle_regrename
, /* gate */
1227 regrename_optimize
, /* execute */
1230 0, /* static_pass_number */
1231 TV_RENAME_REGISTERS
, /* tv_id */
1232 0, /* properties_required */
1233 0, /* properties_provided */
1234 0, /* properties_destroyed */
1235 0, /* todo_flags_start */
1236 TODO_df_finish
| TODO_verify_rtl_sharing
|
1237 TODO_dump_func
/* todo_flags_finish */