1 /* Register renaming for the GNU compiler.
2 Copyright (C) 2000 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
27 #include "insn-config.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
38 #define obstack_chunk_alloc xmalloc
39 #define obstack_chunk_free free
41 #ifndef REGNO_MODE_OK_FOR_BASE_P
42 #define REGNO_MODE_OK_FOR_BASE_P(REGNO, MODE) REGNO_OK_FOR_BASE_P (REGNO)
45 #ifndef REG_MODE_OK_FOR_BASE_P
46 #define REG_MODE_OK_FOR_BASE_P(REGNO, MODE) REG_OK_FOR_BASE_P (REGNO)
49 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
53 struct du_chain
*next_chain
;
54 struct du_chain
*next_use
;
59 unsigned int need_caller_save_reg
:1;
66 terminate_overlapping_read
,
73 static const char * const scan_actions_name
[] =
77 "terminate_overlapping_read",
84 static struct obstack rename_obstack
;
86 static void do_replace
PARAMS ((struct du_chain
*, int));
87 static void scan_rtx_reg
PARAMS ((rtx
, rtx
*, enum reg_class
,
88 enum scan_actions
, enum op_type
));
89 static void scan_rtx_address
PARAMS ((rtx
, rtx
*, enum reg_class
,
90 enum scan_actions
, enum machine_mode
));
91 static void scan_rtx
PARAMS ((rtx
, rtx
*, enum reg_class
,
92 enum scan_actions
, enum op_type
));
93 static struct du_chain
*build_def_use
PARAMS ((basic_block
, HARD_REG_SET
*));
94 static void dump_def_use_chain
PARAMS ((struct du_chain
*));
102 gcc_obstack_init (&rename_obstack
);
103 first_obj
= (char *) obstack_alloc (&rename_obstack
, 0);
105 for (b
= 0; b
< n_basic_blocks
; b
++)
107 basic_block bb
= BASIC_BLOCK (b
);
108 struct du_chain
*all_chains
= 0;
109 HARD_REG_SET regs_used
;
110 HARD_REG_SET unavailable
;
111 HARD_REG_SET regs_seen
;
113 CLEAR_HARD_REG_SET (regs_used
);
114 CLEAR_HARD_REG_SET (unavailable
);
117 fprintf (rtl_dump_file
, "\nBasic block %d:\n", b
);
119 all_chains
= build_def_use (bb
, ®s_used
);
122 dump_def_use_chain (all_chains
);
124 /* Available registers are not: used in the block, live at the start
125 live at the end, a register we've renamed to. */
126 REG_SET_TO_HARD_REG_SET (unavailable
, bb
->global_live_at_start
);
127 REG_SET_TO_HARD_REG_SET (regs_seen
, bb
->global_live_at_end
);
128 IOR_HARD_REG_SET (unavailable
, regs_seen
);
129 IOR_HARD_REG_SET (unavailable
, regs_used
);
131 /* Don't clobber traceback for noreturn functions. */
132 if (frame_pointer_needed
)
134 SET_HARD_REG_BIT (unavailable
, FRAME_POINTER_REGNUM
);
135 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
136 SET_HARD_REG_BIT (unavailable
, HARD_FRAME_POINTER_REGNUM
);
140 CLEAR_HARD_REG_SET (regs_seen
);
144 struct du_chain
*this = all_chains
;
145 struct du_chain
*tmp
, *last
;
146 HARD_REG_SET this_unavailable
;
147 int reg
= REGNO (*this->loc
), treg
;
148 int nregs
= HARD_REGNO_NREGS (reg
, GET_MODE (*this->loc
));
151 all_chains
= this->next_chain
;
153 /* Only rename once we've seen the reg more than once. */
154 if (! TEST_HARD_REG_BIT (regs_seen
, reg
))
156 SET_HARD_REG_BIT (regs_seen
, reg
);
160 if (fixed_regs
[reg
] || global_regs
[reg
])
163 COPY_HARD_REG_SET (this_unavailable
, unavailable
);
165 /* Find last entry on chain (which has the need_caller_save bit),
166 count number of uses, and narrow the set of registers we can
169 for (last
= this; last
->next_use
; last
= last
->next_use
)
172 IOR_COMPL_HARD_REG_SET (this_unavailable
,
173 reg_class_contents
[last
->class]);
178 IOR_COMPL_HARD_REG_SET (this_unavailable
,
179 reg_class_contents
[last
->class]);
181 if (last
->need_caller_save_reg
)
182 IOR_HARD_REG_SET (this_unavailable
, call_used_reg_set
);
184 /* Now potential_regs is a reasonable approximation, let's
185 have a closer look at each register still in there. */
186 for (treg
= 0; treg
< FIRST_PSEUDO_REGISTER
; treg
++)
188 for (i
= nregs
- 1; i
>= 0; --i
)
189 if (TEST_HARD_REG_BIT (this_unavailable
, treg
+i
)
190 || fixed_regs
[treg
+i
]
191 || global_regs
[treg
+i
]
192 /* Can't use regs which aren't saved by the prologue. */
193 || (! regs_ever_live
[treg
+i
] && ! call_used_regs
[treg
+i
])
194 #ifdef HARD_REGNO_RENAME_OK
195 || ! HARD_REGNO_RENAME_OK (reg
+i
, treg
+i
)
202 /* See whether it accepts all modes that occur in
203 definition and uses. */
204 for (tmp
= this; tmp
; tmp
= tmp
->next_use
)
205 if (! HARD_REGNO_MODE_OK (treg
, GET_MODE (*tmp
->loc
)))
213 fprintf (rtl_dump_file
, "Register %s in insn %d",
214 reg_names
[reg
], INSN_UID (last
->insn
));
215 if (last
->need_caller_save_reg
)
216 fprintf (rtl_dump_file
, " crosses a call");
219 if (treg
== FIRST_PSEUDO_REGISTER
)
222 fprintf (rtl_dump_file
, "; no available registers\n");
227 for (i
= nregs
- 1; i
>= 0; --i
)
228 SET_HARD_REG_BIT (unavailable
, treg
+i
);
229 do_replace (this, treg
);
232 fprintf (rtl_dump_file
, ", renamed as %s\n", reg_names
[treg
]);
235 obstack_free (&rename_obstack
, first_obj
);
238 obstack_free (&rename_obstack
, NULL
);
241 fputc ('\n', rtl_dump_file
);
243 count_or_remove_death_notes (NULL
, 1);
244 update_life_info (NULL
, UPDATE_LIFE_LOCAL
,
245 PROP_REG_INFO
| PROP_DEATH_NOTES
);
249 do_replace (chain
, reg
)
250 struct du_chain
*chain
;
255 *chain
->loc
= gen_rtx_REG (GET_MODE (*chain
->loc
), reg
);
256 chain
= chain
->next_use
;
261 static HARD_REG_SET
*referenced_regs
;
262 static struct du_chain
*open_chains
;
263 static struct du_chain
*closed_chains
;
266 scan_rtx_reg (insn
, loc
, class, action
, type
)
269 enum reg_class
class;
270 enum scan_actions action
;
275 enum machine_mode mode
= GET_MODE (x
);
276 int this_regno
= REGNO (x
);
277 int this_nregs
= HARD_REGNO_NREGS (this_regno
, mode
);
279 if (action
== note_reference
)
281 while (this_nregs
-- > 0)
282 SET_HARD_REG_BIT (*referenced_regs
, this_regno
+ this_nregs
);
286 if (action
== mark_write
)
290 struct du_chain
*this = (struct du_chain
*)
291 obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
293 this->next_chain
= open_chains
;
297 this->need_caller_save_reg
= 0;
303 if ((type
== OP_OUT
&& action
!= terminate_write
)
304 || (type
!= OP_OUT
&& action
== terminate_write
))
307 for (p
= &open_chains
; *p
;)
309 struct du_chain
*this = *p
;
311 /* Check if the chain has been terminated if it has then skip to
314 This can happen when we've already appended the location to
315 the chain in Step 3, but are trying to hide in-out operands
316 from terminate_write in Step 5. */
318 if (*this->loc
== cc0_rtx
)
319 p
= &this->next_chain
;
322 int regno
= REGNO (*this->loc
);
323 int nregs
= HARD_REGNO_NREGS (regno
, GET_MODE (*this->loc
));
324 int exact_match
= (regno
== this_regno
&& nregs
== this_nregs
);
326 if (regno
+ nregs
<= this_regno
327 || this_regno
+ this_nregs
<= regno
)
328 p
= &this->next_chain
;
329 else if (action
== mark_read
)
333 if (class == NO_REGS
)
336 this = (struct du_chain
*)
337 obstack_alloc (&rename_obstack
, sizeof (struct du_chain
));
339 this->next_chain
= (*p
)->next_chain
;
343 this->need_caller_save_reg
= 0;
347 else if (action
!= terminate_overlapping_read
|| ! exact_match
)
349 struct du_chain
*next
= this->next_chain
;
351 /* Whether the terminated chain can be used for renaming
352 depends on the action and this being an exact match.
353 In either case, we remove this element from open_chains. */
355 if ((action
== terminate_dead
|| action
== terminate_write
)
358 this->next_chain
= closed_chains
;
359 closed_chains
= this;
361 fprintf (rtl_dump_file
,
362 "Closing chain %s at insn %d (%s)\n",
363 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
364 scan_actions_name
[(int) action
]);
369 fprintf (rtl_dump_file
,
370 "Discarding chain %s at insn %d (%s)\n",
371 reg_names
[REGNO (*this->loc
)], INSN_UID (insn
),
372 scan_actions_name
[(int) action
]);
377 p
= &this->next_chain
;
382 /* Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or
383 BASE_REG_CLASS depending on how the register is being considered. */
386 scan_rtx_address (insn
, loc
, class, action
, mode
)
389 enum reg_class
class;
390 enum scan_actions action
;
391 enum machine_mode mode
;
394 RTX_CODE code
= GET_CODE (x
);
398 if (action
== mark_write
)
405 rtx orig_op0
= XEXP (x
, 0);
406 rtx orig_op1
= XEXP (x
, 1);
407 RTX_CODE code0
= GET_CODE (orig_op0
);
408 RTX_CODE code1
= GET_CODE (orig_op1
);
414 if (GET_CODE (op0
) == SUBREG
)
416 op0
= SUBREG_REG (op0
);
417 code0
= GET_CODE (op0
);
420 if (GET_CODE (op1
) == SUBREG
)
422 op1
= SUBREG_REG (op1
);
423 code1
= GET_CODE (op1
);
426 if (code0
== MULT
|| code0
== SIGN_EXTEND
|| code0
== TRUNCATE
427 || code0
== ZERO_EXTEND
|| code1
== MEM
)
432 else if (code1
== MULT
|| code1
== SIGN_EXTEND
|| code1
== TRUNCATE
433 || code1
== ZERO_EXTEND
|| code0
== MEM
)
438 else if (code0
== CONST_INT
|| code0
== CONST
439 || code0
== SYMBOL_REF
|| code0
== LABEL_REF
)
441 else if (code1
== CONST_INT
|| code1
== CONST
442 || code1
== SYMBOL_REF
|| code1
== LABEL_REF
)
444 else if (code0
== REG
&& code1
== REG
)
448 if (REG_OK_FOR_INDEX_P (op0
)
449 && REG_MODE_OK_FOR_BASE_P (op1
, mode
))
451 else if (REG_OK_FOR_INDEX_P (op1
)
452 && REG_MODE_OK_FOR_BASE_P (op0
, mode
))
454 else if (REG_MODE_OK_FOR_BASE_P (op1
, mode
))
456 else if (REG_MODE_OK_FOR_BASE_P (op0
, mode
))
458 else if (REG_OK_FOR_INDEX_P (op1
))
463 locI
= &XEXP (x
, index_op
);
464 locB
= &XEXP (x
, !index_op
);
466 else if (code0
== REG
)
471 else if (code1
== REG
)
478 scan_rtx_address (insn
, locI
, INDEX_REG_CLASS
, action
, mode
);
480 scan_rtx_address (insn
, locB
, BASE_REG_CLASS
, action
, mode
);
491 /* If the target doesn't claim to handle autoinc, this must be
492 something special, like a stack push. Kill this chain. */
493 action
= terminate_all_read
;
498 scan_rtx_address (insn
, &XEXP (x
, 0), BASE_REG_CLASS
, action
,
503 scan_rtx_reg (insn
, loc
, class, action
, OP_IN
);
510 fmt
= GET_RTX_FORMAT (code
);
511 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
514 scan_rtx_address (insn
, &XEXP (x
, i
), class, action
, mode
);
515 else if (fmt
[i
] == 'E')
516 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
517 scan_rtx_address (insn
, &XVECEXP (x
, i
, j
), class, action
, mode
);
522 scan_rtx (insn
, loc
, class, action
, type
)
525 enum reg_class
class;
526 enum scan_actions action
;
531 enum rtx_code code
= GET_CODE (x
);
547 scan_rtx_reg (insn
, loc
, class, action
, type
);
551 scan_rtx_address (insn
, &XEXP (x
, 0), BASE_REG_CLASS
, action
,
556 scan_rtx (insn
, &SET_SRC (x
), class, action
, OP_IN
);
557 scan_rtx (insn
, &SET_DEST (x
), class, action
, OP_OUT
);
560 case STRICT_LOW_PART
:
561 scan_rtx (insn
, &XEXP (x
, 0), class, action
, OP_INOUT
);
566 scan_rtx (insn
, &XEXP (x
, 0), class, action
,
567 type
== OP_IN
? OP_IN
: OP_INOUT
);
568 scan_rtx (insn
, &XEXP (x
, 1), class, action
, OP_IN
);
569 scan_rtx (insn
, &XEXP (x
, 2), class, action
, OP_IN
);
578 /* Should only happen inside MEM. */
582 scan_rtx (insn
, &SET_DEST (x
), class, action
, OP_OUT
);
586 scan_rtx (insn
, &XEXP (x
, 0), class, action
, type
);
588 scan_rtx (insn
, &XEXP (x
, 1), class, action
, type
);
595 fmt
= GET_RTX_FORMAT (code
);
596 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
599 scan_rtx (insn
, &XEXP (x
, i
), class, action
, type
);
600 else if (fmt
[i
] == 'E')
601 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
602 scan_rtx (insn
, &XVECEXP (x
, i
, j
), class, action
, type
);
606 /* Build def/use chain */
608 static struct du_chain
*
609 build_def_use (bb
, regs_used
)
611 HARD_REG_SET
*regs_used
;
615 open_chains
= closed_chains
= NULL
;
616 referenced_regs
= regs_used
;
618 for (insn
= bb
->head
; ; insn
= NEXT_INSN (insn
))
624 rtx old_operands
[MAX_RECOG_OPERANDS
];
625 rtx old_dups
[MAX_DUP_OPERANDS
];
630 /* Record all mentioned registers in regs_used. */
631 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, note_reference
, OP_IN
);
633 /* Process the insn, determining its effect on the def-use
634 chains. We perform the following steps with the register
635 references in the insn:
636 (1) Any read that overlaps an open chain, but doesn't exactly
637 match, causes that chain to be closed. We can't deal
639 (2) Any read outside an operand causes any chain it overlaps
640 with to be closed, since we can't replace it.
641 (3) Any read inside an operand is added if there's already
642 an open chain for it.
643 (4) For any REG_DEAD note we find, close open chains that
645 (5) For any write we find, close open chains that overlap it.
646 (6) For any write we find in an operand, make a new chain.
647 (7) For any REG_UNUSED, close any chains we just opened. */
650 constrain_operands (1);
651 preprocess_constraints ();
652 alt
= which_alternative
;
653 n_ops
= recog_data
.n_operands
;
655 /* Simplify the code below by rewriting things to reflect
656 matching constraints. Also promote OP_OUT to OP_INOUT
657 in predicated instructions. */
659 predicated
= GET_CODE (PATTERN (insn
)) == COND_EXEC
;
660 for (i
= 0; i
< n_ops
; ++i
)
662 int matches
= recog_op_alt
[i
][alt
].matches
;
664 recog_op_alt
[i
][alt
].class = recog_op_alt
[matches
][alt
].class;
665 if (matches
>= 0 || recog_op_alt
[i
][alt
].matched
>= 0
666 || (predicated
&& recog_data
.operand_type
[i
] == OP_OUT
))
667 recog_data
.operand_type
[i
] = OP_INOUT
;
670 /* Step 1: Close chains for which we have overlapping reads. */
671 for (i
= 0; i
< n_ops
; i
++)
672 scan_rtx (insn
, recog_data
.operand_loc
[i
],
673 NO_REGS
, terminate_overlapping_read
,
674 recog_data
.operand_type
[i
]);
676 /* Step 2: Close chains for which we have reads outside operands.
677 We do this by munging all operands into CC0, and closing
678 everything remaining. */
680 for (i
= 0; i
< n_ops
; i
++)
682 old_operands
[i
] = recog_data
.operand
[i
];
683 /* Don't squash match_operator or match_parallel here, since
684 we don't know that all of the contained registers are
685 reachable by proper operands. */
686 if (recog_data
.constraints
[i
][0] == '\0')
688 *recog_data
.operand_loc
[i
] = cc0_rtx
;
690 for (i
= 0; i
< recog_data
.n_dups
; i
++)
692 old_dups
[i
] = *recog_data
.dup_loc
[i
];
693 *recog_data
.dup_loc
[i
] = cc0_rtx
;
696 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_all_read
, OP_IN
);
698 for (i
= 0; i
< recog_data
.n_dups
; i
++)
699 *recog_data
.dup_loc
[i
] = old_dups
[i
];
700 for (i
= 0; i
< n_ops
; i
++)
701 *recog_data
.operand_loc
[i
] = old_operands
[i
];
703 /* Step 2B: Can't rename function call argument registers. */
704 if (GET_CODE (insn
) == CALL_INSN
&& CALL_INSN_FUNCTION_USAGE (insn
))
705 scan_rtx (insn
, &CALL_INSN_FUNCTION_USAGE (insn
),
706 NO_REGS
, terminate_all_read
, OP_IN
);
708 /* Step 3: Append to chains for reads inside operands. */
709 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
711 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
712 rtx
*loc
= (i
< n_ops
713 ? recog_data
.operand_loc
[opn
]
714 : recog_data
.dup_loc
[i
- n_ops
]);
715 enum reg_class
class = recog_op_alt
[opn
][alt
].class;
716 enum op_type type
= recog_data
.operand_type
[opn
];
718 /* Don't scan match_operand here, since we've no reg class
719 information to pass down. Any operands that we could
720 substitute in will be represented elsewhere. */
721 if (recog_data
.constraints
[opn
][0] == '\0')
724 if (recog_op_alt
[opn
][alt
].is_address
)
725 scan_rtx_address (insn
, loc
, class, mark_read
, VOIDmode
);
727 scan_rtx (insn
, loc
, class, mark_read
, type
);
730 /* Step 4: Close chains for registers that die here.
731 Also record updates for REG_INC notes. */
732 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
734 if (REG_NOTE_KIND (note
) == REG_DEAD
)
735 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
, OP_IN
);
736 else if (REG_NOTE_KIND (note
) == REG_INC
)
737 scan_rtx (insn
, &XEXP (note
, 0), ALL_REGS
, mark_read
, OP_INOUT
);
740 /* Step 4B: If this is a call, any chain live at this point
741 requires a caller-saved reg. */
742 if (GET_CODE (insn
) == CALL_INSN
)
745 for (p
= open_chains
; p
; p
= p
->next_chain
)
748 for (p2
= p
; p2
->next_use
; p2
= p2
->next_use
)
750 p2
->need_caller_save_reg
= 1;
754 /* Step 5: Close open chains that overlap writes. Similar to
755 step 2, we hide in-out operands, since we do not want to
756 close these chains. */
758 for (i
= 0; i
< n_ops
; i
++)
760 old_operands
[i
] = recog_data
.operand
[i
];
761 if (recog_data
.operand_type
[i
] == OP_INOUT
)
762 *recog_data
.operand_loc
[i
] = cc0_rtx
;
764 for (i
= 0; i
< recog_data
.n_dups
; i
++)
766 int opn
= recog_data
.dup_num
[i
];
767 old_dups
[i
] = *recog_data
.dup_loc
[i
];
768 if (recog_data
.operand_type
[opn
] == OP_INOUT
)
769 *recog_data
.dup_loc
[i
] = cc0_rtx
;
772 scan_rtx (insn
, &PATTERN (insn
), NO_REGS
, terminate_write
, OP_IN
);
774 for (i
= 0; i
< recog_data
.n_dups
; i
++)
775 *recog_data
.dup_loc
[i
] = old_dups
[i
];
776 for (i
= 0; i
< n_ops
; i
++)
777 *recog_data
.operand_loc
[i
] = old_operands
[i
];
779 /* Step 6: Begin new chains for writes inside operands. */
780 /* ??? Many targets have output constraints on the SET_DEST
781 of a call insn, which is stupid, since these are certainly
782 ABI defined hard registers. Don't change calls at all. */
783 if (GET_CODE (insn
) != CALL_INSN
)
784 for (i
= 0; i
< n_ops
+ recog_data
.n_dups
; i
++)
786 int opn
= i
< n_ops
? i
: recog_data
.dup_num
[i
- n_ops
];
787 rtx
*loc
= (i
< n_ops
788 ? recog_data
.operand_loc
[opn
]
789 : recog_data
.dup_loc
[i
- n_ops
]);
790 enum reg_class
class = recog_op_alt
[opn
][alt
].class;
792 if (recog_data
.operand_type
[opn
] == OP_OUT
)
793 scan_rtx (insn
, loc
, class, mark_write
, OP_OUT
);
796 /* Step 7: Close chains for registers that were never
798 for (note
= REG_NOTES (insn
); note
; note
= XEXP (note
, 1))
799 if (REG_NOTE_KIND (note
) == REG_UNUSED
)
800 scan_rtx (insn
, &XEXP (note
, 0), NO_REGS
, terminate_dead
, OP_IN
);
806 /* Since we close every chain when we find a REG_DEAD note, anything that
807 is still open lives past the basic block, so it can't be renamed. */
808 return closed_chains
;
811 /* Dump all def/use chains in CHAINS to RTL_DUMP_FILE. They are
812 printed in reverse order as that's how we build them. */
815 dump_def_use_chain (chains
)
816 struct du_chain
*chains
;
820 struct du_chain
*this = chains
;
821 int r
= REGNO (*this->loc
);
822 int nregs
= HARD_REGNO_NREGS (r
, GET_MODE (*this->loc
));
823 fprintf (rtl_dump_file
, "Register %s (%d):", reg_names
[r
], nregs
);
826 fprintf (rtl_dump_file
, " %d [%s]", INSN_UID (this->insn
),
827 reg_class_names
[this->class]);
828 this = this->next_use
;
830 fprintf (rtl_dump_file
, "\n");
831 chains
= chains
->next_chain
;