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. */
25 #include "hard-reg-set.h"
26 #include "basic-block.h"
27 #include "insn-config.h"
35 static const char *const reg_class_names
[] = REG_CLASS_NAMES
;
37 /* ??? Consider a more sparse data structure? */
38 typedef struct def_uses
40 /* high bound of defs and uses */
43 /* 1 if insn y defines a reg whose use crosses a call
44 y is the ordinal position of the insn within the block */
45 sbitmap require_call_save_reg
;
47 /* REGNO x INSN y 1 if insn y sets reg x */
50 /* REGNO x INSN y The register class for this def */
51 enum reg_class
*def_class
;
53 /* REGNO x INSN y 1 if insn y uses reg x */
56 /* REGNO x INSN y The register class for this use */
57 enum reg_class
*use_class
;
61 #define DU_REG_CLASS(rc,r,high_bound,i) (rc[r * high_bound + i])
63 typedef struct ext_basic_blocks
65 /* n_basic_blocks x n_basic_blocks y 1 if bb y is in extended bb
69 /* n_basic_blocks x n_basic_blocks y 1 if bb y is an exit block */
74 #define UID_RUID_HIGH_BOUND 64
78 static void build_def_use
PARAMS ((int, ext_basic_blocks
*,
79 HARD_REG_SET
*, def_uses
*,
81 static int replace_reg_in_block
PARAMS ((def_uses
*, varray_type
*,
82 int, rtx
, unsigned int));
83 static int consider_def
PARAMS ((rtx
, int, def_uses
*, int));
84 static int consider_available
PARAMS ((rtx
, int, HARD_REG_SET
*,
85 int, def_uses
*, int));
86 static rtx rr_replace_reg
PARAMS ((rtx
, rtx
, rtx
, int, rtx
,
88 static int consider_use
PARAMS ((rtx
, int, int, int));
89 static int condmove_p
PARAMS ((rtx
));
90 static void dump_def_use_chain
PARAMS ((HARD_REG_SET
*, def_uses
*,
92 static void dump_ext_bb_info
PARAMS ((int, ext_basic_blocks
*));
93 static void find_ext_basic_blocks
PARAMS ((ext_basic_blocks
*));
94 static void find_one_ext_basic_block
PARAMS ((int, basic_block
, sbitmap
*,
96 static enum reg_class get_reg_class
PARAMS ((rtx
, rtx
, int,
98 static rtx regno_first_use_in
PARAMS ((unsigned int, rtx
));
101 regrename_optimize ()
103 int b
, eb
, i
, inum
, r
, rc
, replace_ok
;
106 ext_basic_blocks ebb
;
108 /* Registers used in a given class */
109 HARD_REG_SET class_regs
;
111 /* Registers available for use as renaming registers */
112 HARD_REG_SET avail_regs
;
114 /* Registers used in the block */
115 HARD_REG_SET regs_used
;
117 /* Registers which have been used as renaming registers */
118 HARD_REG_SET renamed_regs
;
120 HARD_REG_SET global_live_at_end
, global_live_at_start
;
122 HARD_REG_SET null_bitmap
, tmp_bitmap
;
124 /* 1 if insn y sets a register which is live at the end of the block */
125 sbitmap defs_live_exit
;
127 /* Mapping from insn y (ordinal position in block) to INSN_UID */
128 varray_type uid_ruid
;
130 /* Mapping from insn y (ordinal position in block) to block id */
131 varray_type uid_rbid
;
133 /* Ordinal position in block of defining insn */
136 VARRAY_RTX_INIT (uid_ruid
, UID_RUID_HIGH_BOUND
+ 1, "uid_ruid");
137 VARRAY_LONG_INIT (uid_rbid
, UID_RUID_HIGH_BOUND
+ 1, "uid_rbid");
140 = sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
141 sbitmap_vector_zero (ebb
.basic_block
, n_basic_blocks
);
143 = sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
144 sbitmap_vector_zero (ebb
.exit
, n_basic_blocks
);
146 find_ext_basic_blocks (&ebb
);
148 du
.def_class
= du
.use_class
= 0;
150 /* Build uid_ruid and uid_rbid for this extended basic block */
151 for (b
= 0; b
< n_basic_blocks
; b
++)
152 if (TEST_BIT (ebb
.basic_block
[b
], b
))
154 for (eb
= du
.high_bound
= 0; eb
< n_basic_blocks
; eb
++)
155 if (TEST_BIT (ebb
.basic_block
[b
], eb
))
157 basic_block bb
= BASIC_BLOCK (eb
);
159 /* Calculate high bound for uid_ruid and allocate if necessary */
160 for (insn
= bb
->head
;
161 insn
!= NEXT_INSN (bb
->end
);
162 du
.high_bound
++, insn
= NEXT_INSN (insn
))
164 int uid_ruid_high_bound
= VARRAY_SIZE (uid_ruid
);
166 if (du
.high_bound
+ 4 >= uid_ruid_high_bound
)
168 VARRAY_GROW (uid_ruid
, uid_ruid_high_bound
* 2);
169 VARRAY_GROW (uid_rbid
, uid_ruid_high_bound
* 2);
172 VARRAY_RTX (uid_ruid
, du
.high_bound
) = insn
;
173 VARRAY_LONG (uid_rbid
, du
.high_bound
) = eb
;
177 CLEAR_HARD_REG_SET (null_bitmap
);
178 CLEAR_HARD_REG_SET (class_regs
);
179 CLEAR_HARD_REG_SET (regs_used
);
180 CLEAR_HARD_REG_SET (avail_regs
);
181 CLEAR_HARD_REG_SET (tmp_bitmap
);
182 CLEAR_HARD_REG_SET (renamed_regs
);
185 = sbitmap_vector_alloc (FIRST_PSEUDO_REGISTER
, du
.high_bound
+ 1);
186 sbitmap_vector_zero (du
.defs
, FIRST_PSEUDO_REGISTER
);
188 = sbitmap_vector_alloc (FIRST_PSEUDO_REGISTER
, du
.high_bound
+ 1);
189 sbitmap_vector_zero (du
.uses
, FIRST_PSEUDO_REGISTER
);
190 du
.require_call_save_reg
= sbitmap_alloc (du
.high_bound
+ 1);
191 sbitmap_zero (du
.require_call_save_reg
);
192 defs_live_exit
= sbitmap_alloc (du
.high_bound
+ 1);
193 sbitmap_zero (defs_live_exit
);
196 = xrealloc (du
.def_class
,
197 (sizeof (enum reg_class
) * FIRST_PSEUDO_REGISTER
201 = xrealloc (du
.use_class
,
202 (sizeof (enum reg_class
) * FIRST_PSEUDO_REGISTER
205 build_def_use (b
, &ebb
, ®s_used
, &du
, &defs_live_exit
);
209 dump_ext_bb_info (b
, &ebb
);
210 dump_def_use_chain (&global_live_at_end
, &du
, &uid_ruid
);
213 /* Available registers are not: used in the block, live at the start,
214 live at the end, a register we've renamed to. */
215 /* ??? The current algorithm is pessimistic for extended basic blocks
216 as it just treats them as a big basic block. */
218 COPY_HARD_REG_SET (tmp_bitmap
, regs_used
);
219 REG_SET_TO_HARD_REG_SET (global_live_at_start
,
220 BASIC_BLOCK (b
)->global_live_at_start
);
221 IOR_HARD_REG_SET (tmp_bitmap
, global_live_at_start
);
222 for (eb
= 0; eb
< n_basic_blocks
; eb
++)
223 if (TEST_BIT (ebb
.basic_block
[b
], eb
))
225 basic_block bb
= BASIC_BLOCK (eb
);
227 REG_SET_TO_HARD_REG_SET (global_live_at_end
,
228 bb
->global_live_at_end
);
229 IOR_HARD_REG_SET (tmp_bitmap
, global_live_at_end
);
232 def_idx
= xcalloc (du
.high_bound
, sizeof (int));
234 /* Only consider registers in this extended block and in this class
235 that are defined more than once. Replace them if permissible. */
236 for (r
= 0; r
< FIRST_PSEUDO_REGISTER
; r
++)
238 int avail_reg
, ar_idx
, def
, def_cnt
= 0, use_idx
, call_idx
;
240 if (!TEST_HARD_REG_BIT (regs_used
, r
)
242 || r
== FRAME_POINTER_REGNUM
)
245 /* Find def_idx[N] where hbound of N is the number of
246 definitions of this register in this block. and def_idx
247 is the ordinal position of this insn in the block. */
248 for (i
= 0, def_idx
[def_cnt
] = 0; i
< du
.high_bound
; i
++)
249 if (TEST_BIT (du
.defs
[r
], i
)
250 && consider_def (VARRAY_RTX (uid_ruid
, i
), r
, &du
, i
))
253 def_idx
[def_cnt
] = i
;
255 /* Only consider definitions that have a use. */
256 for (use_idx
= i
+ 1; use_idx
< du
.high_bound
; use_idx
++)
258 if (TEST_BIT (du
.uses
[r
], use_idx
))
260 if (consider_use (VARRAY_RTX (uid_ruid
, use_idx
), r
,
261 VARRAY_LONG (uid_rbid
, i
),
262 VARRAY_LONG (uid_rbid
, use_idx
)))
272 /* Don't consider def if we don't want this
281 if (TEST_BIT (du
.defs
[r
], use_idx
))
285 /* Scan until the next def to avoid renaming
286 parameter registers. */
287 /* ??? consider using CALL_INSN_FUNCTION_USAGE */
288 for (call_idx
= i
; call_idx
<= use_idx
; call_idx
++)
289 if (VARRAY_RTX (uid_ruid
, call_idx
)
290 && (GET_CODE (VARRAY_RTX (uid_ruid
, call_idx
))
292 SET_BIT (du
.require_call_save_reg
, i
);
298 /* We have more than one def so rename until we exhaust
299 renaming registers. */
300 /* ??? Should we continue renaming round robin when we exhaust
301 renaming registers? */
302 for (def
= 0; def
< def_cnt
- 1; def
++)
304 if (!TEST_BIT (defs_live_exit
, def_idx
[def
])
306 (GET_CODE (VARRAY_RTX (uid_ruid
,
307 def_idx
[def
]))) == 'i'))
311 (r
, PATTERN (VARRAY_RTX (uid_ruid
, def_idx
[def
])));
316 /* Don't bother with stacked float registers */
317 if (GET_MODE_CLASS (GET_MODE (reg_use
)) == MODE_FLOAT
)
320 rc
= (int) DU_REG_CLASS (du
.def_class
,
321 r
, du
.high_bound
, def_idx
[def
]);
322 COPY_HARD_REG_SET (avail_regs
,
323 reg_class_contents
[(enum reg_class
) rc
]);
324 AND_COMPL_HARD_REG_SET (avail_regs
, tmp_bitmap
);
325 AND_COMPL_HARD_REG_SET (avail_regs
, renamed_regs
);
327 /* No available registers in this class */
328 GO_IF_HARD_REG_EQUAL (avail_regs
, null_bitmap
,
331 for (ar_idx
= 0; ar_idx
< FIRST_PSEUDO_REGISTER
332 && TEST_HARD_REG_BIT (avail_regs
, ar_idx
); ar_idx
++)
335 if (ar_idx
== FIRST_PSEUDO_REGISTER
)
336 goto no_available_regs
;
338 /* Only try register renaming if there is an available
339 register in this class. */
340 for (ar_idx
= 0; ar_idx
< FIRST_PSEUDO_REGISTER
; ar_idx
++)
342 #ifdef REG_ALLOC_ORDER
343 avail_reg
= reg_alloc_order
[ar_idx
];
347 if (consider_available (reg_use
, avail_reg
,
348 &avail_regs
, rc
, &du
,
350 goto found_avail_reg
;
355 fprintf (rtl_dump_file
, "Register %s in class %s",
356 reg_names
[r
], reg_class_names
[rc
]);
357 fprintf (rtl_dump_file
, " in insn %d",
358 INSN_UID (VARRAY_RTX (uid_ruid
,
361 if (TEST_BIT (du
.require_call_save_reg
,
363 fprintf (rtl_dump_file
, " crosses a call");
365 fprintf (rtl_dump_file
, ". No available registers\n");
370 SET_HARD_REG_BIT (renamed_regs
, avail_reg
);
371 CLEAR_HARD_REG_BIT (avail_regs
, avail_reg
);
373 /* Replace in destination. Replace in source for
374 remainder of block until new register is defined
377 = replace_reg_in_block (&du
, &uid_ruid
, def_idx
[def
],
380 /* Replace failed, so restore previous register */
383 replace_reg_in_block (&du
, &uid_ruid
, def_idx
[def
],
384 gen_rtx_REG (GET_MODE (reg_use
),
390 fprintf (rtl_dump_file
,
391 "Register %s in class %s Renaming as %s ",
392 reg_names
[r
], reg_class_names
[rc
],
393 reg_names
[avail_reg
]);
394 fprintf (rtl_dump_file
,
395 "would not satisfy constraints\n");
399 else if (rtl_dump_file
)
401 fprintf (rtl_dump_file
,
402 "Register %s in class %s Renamed as %s ",
403 reg_names
[r
], reg_class_names
[rc
],
404 reg_names
[avail_reg
]);
405 fprintf (rtl_dump_file
, "at insn %d\n",
406 INSN_UID (VARRAY_RTX (uid_ruid
,
415 sbitmap_zero (du
.defs
[r
]);
422 sbitmap_vector_free (du
.defs
);
423 sbitmap_vector_free (du
.uses
);
424 sbitmap_free (du
.require_call_save_reg
);
425 sbitmap_free (defs_live_exit
);
426 CLEAR_HARD_REG_SET (regs_used
);
427 CLEAR_HARD_REG_SET (renamed_regs
);
429 for (inum
= 0; inum
< (int) VARRAY_SIZE (uid_ruid
); inum
++)
430 VARRAY_RTX (uid_ruid
, inum
) = (rtx
) 0;
433 sbitmap_vector_free (ebb
.basic_block
);
434 sbitmap_vector_free (ebb
.exit
);
437 /* Build def/use chain DU for extended basic block EBB having root B.
438 Also determine which regs are used, REGS_USED, and which insns define
439 a live at exit def, DEFS_LIVE_EXIT */
442 build_def_use (b
, ebb
, regs_used
, du
, defs_live_exit
)
444 ext_basic_blocks
*ebb
;
445 HARD_REG_SET
*regs_used
;
447 sbitmap
*defs_live_exit
;
454 for (eb
= 0; eb
< n_basic_blocks
; eb
++)
456 basic_block bb
= BASIC_BLOCK (eb
);
458 if (!TEST_BIT (ebb
->basic_block
[b
], eb
))
461 for (insn
= bb
->head
;
462 insn
!= NEXT_INSN (bb
->end
);
463 inum
++, insn
= NEXT_INSN (insn
))
465 struct resources insn_res
;
466 struct resources insn_sets
;
471 CLEAR_RESOURCE (&insn_sets
);
472 mark_set_resources (insn
, &insn_sets
, 0, MARK_DEST
);
474 for (r
= 0; r
< FIRST_PSEUDO_REGISTER
; r
++)
476 if (!TEST_HARD_REG_BIT (insn_sets
.regs
, r
))
479 SET_HARD_REG_BIT (*regs_used
, r
);
480 if (REGNO_REG_SET_P (bb
->global_live_at_end
, r
))
481 SET_BIT (*defs_live_exit
, inum
);
483 if (!insn_sets
.memory
)
484 SET_BIT (du
->defs
[r
], inum
);
486 DU_REG_CLASS (du
->def_class
, r
, du
->high_bound
, inum
)
487 = get_reg_class (insn
, regno_first_use_in (r
, PATTERN (insn
)),
488 DESTINATION
, NO_REGS
);
491 CLEAR_RESOURCE (&insn_res
);
492 mark_referenced_resources (insn
, &insn_res
, 0);
494 for (r
= 0; r
< FIRST_PSEUDO_REGISTER
; r
++)
496 if (!TEST_HARD_REG_BIT (insn_res
.regs
, r
))
499 SET_HARD_REG_BIT (*regs_used
, r
);
500 SET_BIT (du
->uses
[r
], inum
);
501 DU_REG_CLASS (du
->use_class
, r
, du
->high_bound
, inum
)
502 = get_reg_class (insn
, regno_use_in (r
, PATTERN (insn
)),
508 free_resource_info ();
511 /* Return nonzero if regno AVAIL_REG can replace REG_DEF for insns in UID_RUID
512 starting at insn DEF in def/use chain DU. */
515 replace_reg_in_block (du
, uid_ruid
, def
, reg_def
, avail_reg
)
517 varray_type
*uid_ruid
;
520 unsigned int avail_reg
;
522 int du_idx
, status
= 1;
523 int last_replaced_insn
;
524 unsigned int r
= REGNO (reg_def
);
528 rtx new_reg
= gen_rtx_REG (GET_MODE (reg_def
), avail_reg
);
530 rr_replace_reg (PATTERN (VARRAY_RTX (*uid_ruid
, def
)), reg_def
, new_reg
,
531 DESTINATION
, VARRAY_RTX (*uid_ruid
, def
), &status
);
537 /* This typically happens if a constraint check failed and the register
538 changes are being reversed. */
539 for (reg_notes
= REG_NOTES (VARRAY_RTX (*uid_ruid
, def
));
540 reg_notes
; reg_notes
= XEXP (reg_notes
, 1))
542 if (REG_NOTE_KIND (reg_notes
) == REG_DEAD
543 && REGNO (XEXP (reg_notes
, 0)) == avail_reg
)
544 death_note
= reg_notes
;
548 remove_note (VARRAY_RTX (*uid_ruid
, def
), death_note
);
550 /* The old destination is now dead if it is also a source. */
551 if (regno_use_in (r
, PATTERN (VARRAY_RTX (*uid_ruid
, def
))))
552 REG_NOTES (VARRAY_RTX (*uid_ruid
, def
))
553 = gen_rtx_EXPR_LIST (REG_DEAD
, reg_def
,
554 REG_NOTES (VARRAY_RTX (*uid_ruid
,
557 last_replaced_insn
= 0;
559 /* Now replace in the uses. */
560 for (du_idx
= def
+ 1; du_idx
< du
->high_bound
; du_idx
++)
562 if (! INSN_P (VARRAY_RTX (*uid_ruid
, du_idx
)))
565 reg_use
= regno_use_in (r
, PATTERN (VARRAY_RTX (*uid_ruid
, du_idx
)));
567 if (reg_use
&& TEST_BIT (du
->uses
[r
], du_idx
))
569 new_reg
= gen_rtx_REG (GET_MODE (reg_use
), avail_reg
);
571 rr_replace_reg (PATTERN (VARRAY_RTX (*uid_ruid
, du_idx
)), reg_use
,
572 new_reg
, SOURCE
, VARRAY_RTX (*uid_ruid
, du_idx
),
574 death_note
= find_reg_note (VARRAY_RTX (*uid_ruid
, du_idx
),
578 REG_NOTES (VARRAY_RTX (*uid_ruid
, du_idx
))
579 = gen_rtx_EXPR_LIST (REG_DEAD
, new_reg
,
580 REG_NOTES (VARRAY_RTX (*uid_ruid
,
582 remove_note (VARRAY_RTX (*uid_ruid
, du_idx
),
583 find_reg_note (VARRAY_RTX (*uid_ruid
, du_idx
),
588 /* This insn may contain shared rtl replaced in the previous iteration.
589 Treat this equivalent to the rr_replace_reg case. */
590 if (TEST_BIT (du
->uses
[r
], du_idx
))
592 last_replaced_insn
= du_idx
;
594 SET_BIT (du
->uses
[avail_reg
], du_idx
);
595 RESET_BIT (du
->uses
[r
], du_idx
);
600 if (TEST_BIT (du
->defs
[r
], du_idx
))
604 /* Add REG_DEAD note for replaced register at last use. */
606 if (last_replaced_insn
)
608 new_reg
= regno_use_in (avail_reg
,
609 PATTERN (VARRAY_RTX (*uid_ruid
,
610 last_replaced_insn
)));
612 && ! find_reg_note (VARRAY_RTX (*uid_ruid
, last_replaced_insn
),
615 REG_NOTES (VARRAY_RTX (*uid_ruid
, last_replaced_insn
))
616 = gen_rtx_EXPR_LIST (REG_DEAD
, new_reg
,
617 REG_NOTES (VARRAY_RTX (*uid_ruid
,
618 last_replaced_insn
)));
619 remove_note (VARRAY_RTX (*uid_ruid
, last_replaced_insn
),
620 find_reg_note (VARRAY_RTX (*uid_ruid
, last_replaced_insn
),
628 /* Try to replace REG_USE in X with REG_SUB if INSN has a REPLACE_TYPE.
629 STATUS is zero if the resulting pattern is not valid. */
632 rr_replace_reg (x
, reg_use
, reg_sub
, replace_type
, insn
, status
)
652 if (REGNO (x
) == REGNO (reg_use
))
654 if (GET_MODE (x
) == GET_MODE (reg_use
))
657 return gen_rtx_REG (GET_MODE (x
), REGNO (reg_sub
));
663 if (replace_type
== DESTINATION
)
664 SET_DEST (x
) = rr_replace_reg (SET_DEST (x
), reg_use
, reg_sub
,
665 replace_type
, insn
, status
);
666 else if (replace_type
== SOURCE
)
668 unsigned int dest_subregno
= 0;
669 int had_subreg
= GET_CODE (SET_DEST (x
)) == SUBREG
;
672 dest_subregno
= REGNO (XEXP (SET_DEST (x
), 0));
674 SET_SRC (x
) = rr_replace_reg (SET_SRC (x
), reg_use
, reg_sub
,
675 replace_type
, insn
, status
);
677 /* If the replacement register is not part of the source
678 then it may be part of a source mem operand. */
679 if (GET_CODE (SET_DEST (x
)) == MEM
680 || GET_CODE (SET_DEST (x
)) == ZERO_EXTRACT
681 || GET_CODE (SET_DEST (x
)) == SIGN_EXTRACT
682 || GET_CODE (SET_DEST (x
)) == STRICT_LOW_PART
)
683 SET_DEST (x
) = rr_replace_reg (SET_DEST (x
), reg_use
, reg_sub
,
684 replace_type
, insn
, status
);
685 /* Shared rtl sanity check. */
686 if (had_subreg
&& dest_subregno
!= REGNO (XEXP (SET_DEST (x
), 0)))
693 n
= recog_memoized (insn
);
700 /* Any MATCH_DUP's which are REGs must still match */
701 for (id
= insn_data
[n
].n_dups
- 1; id
>= 0; id
--)
703 int opno
= recog_data
.dup_num
[id
];
705 if (GET_CODE (*recog_data
.dup_loc
[id
]) == REG
706 && GET_CODE (*recog_data
.operand_loc
[opno
]) == REG
707 && (REGNO (*recog_data
.dup_loc
[id
])
708 != REGNO (*recog_data
.operand_loc
[opno
])))
712 if (!constrain_operands (1))
715 validate_replace_rtx (reg_sub
, reg_use
, insn
);
727 fmt
= GET_RTX_FORMAT (code
);
728 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
731 XEXP (x
, i
) = rr_replace_reg (XEXP (x
, i
), reg_use
, reg_sub
,
732 replace_type
, insn
, status
);
737 for (xv
= 0; xv
< XVECLEN (x
, i
); xv
++)
739 XVECEXP (x
, i
, xv
) = rr_replace_reg (XVECEXP (x
, i
, xv
), reg_use
,
740 reg_sub
, replace_type
, insn
,
742 n
= recog_memoized (insn
);
746 if (!constrain_operands (1))
749 validate_replace_rtx (reg_sub
, reg_use
, insn
);
761 /* Can REGNO in INSN be considered for renaming, given def INUM in d/u
765 consider_def (insn
, regno
, du
, inum
)
768 def_uses
*du ATTRIBUTE_UNUSED
;
769 int inum ATTRIBUTE_UNUSED
;
771 /* Don't rename windowed registers across a call */
772 #ifdef INCOMING_REGNO
773 if (TEST_BIT (du
->require_call_save_reg
, inum
)
774 && INCOMING_REGNO (regno
) != regno
)
778 /* Don't consider conditional moves. Predicate architectures may
779 use two complementary conditional moves and the regno shouldn't change */
780 if (condmove_p (insn
))
783 /* Don't rename call used registers across a call */
784 if (!(GET_CODE (insn
) == CALL_INSN
785 && TEST_HARD_REG_BIT (call_used_reg_set
, regno
)))
791 /* Can the use of REGNO in INSN of block USE_BLOCK be considered for renaming
792 for a def in def_block? */
795 consider_use (insn
, regno
, def_block
, use_block
)
803 basic_block ub
= BASIC_BLOCK (use_block
);
808 /* If a use's basic block is different than the def's basic block,
809 then insure another predecessor does not also define this register */
810 if (def_block
!= use_block
)
811 for (e
= ub
->pred
; e
; e
= e
->pred_next
)
812 if (e
->src
->index
!= def_block
813 && e
->src
->index
!= -1
814 && REGNO_REG_SET_P (BASIC_BLOCK (e
->src
->index
)->global_live_at_end
,
818 /* Don't consider conditional moves. Predicate architectures may
819 use two complementary conditional moves and the regno shouldn't change */
821 if (condmove_p (insn
))
824 reg_use
= regno_first_use_in (regno
, PATTERN (insn
));
827 /* Don't consider multi-reg values. */
828 if (HARD_REGNO_NREGS (regno
, GET_MODE (reg_use
)) != 1
829 && GET_MODE (reg_use
) != CCmode
)
832 /* Don't consider register if the only use is in a USE */
833 return ! reg_mentioned_p (gen_rtx_USE (VOIDmode
, reg_use
),
840 /* Can REG_USE be replaced by regno AVAIL_REG if it is in AVAIL_REGS
841 and it is in regclass RC, given insn INUM of def/use chain DU? */
844 consider_available (reg_use
, avail_reg
, avail_regs
, rc
, du
, inum
)
847 HARD_REG_SET
*avail_regs
;
852 if (!TEST_HARD_REG_BIT (*avail_regs
, avail_reg
))
855 if (fixed_regs
[avail_reg
])
858 #ifdef HARD_REGNO_RENAME_OK
859 if (!HARD_REGNO_RENAME_OK (REGNO (reg_use
), avail_reg
))
863 /* Don't consider windowed leaf registers which will be renamed by
864 leaf_renumber_regs */
865 #ifdef LEAF_REG_REMAP
866 if (current_function_uses_only_leaf_regs
)
867 if (LEAF_REG_REMAP (avail_reg
) < 0)
871 /* A register is considered available if it is available at the beginning of
872 the basic block. We may want to refine this to when a register becomes
873 available within the block. We don't consider multi-reg values. */
874 /* ??? Consider a representation that would allow multi-reg support? */
875 if (!TEST_HARD_REG_BIT (reg_class_contents
[(enum reg_class
) rc
], avail_reg
)
876 || !HARD_REGNO_MODE_OK (avail_reg
, GET_MODE (reg_use
))
877 || (HARD_REGNO_NREGS (avail_reg
, GET_MODE (reg_use
)) != 1
878 && GET_MODE (reg_use
) != CCmode
)
879 || (call_fixed_regs
[avail_reg
]
880 #ifdef HARD_REGNO_RENAME_OK
881 && !HARD_REGNO_RENAME_OK (REGNO (reg_use
), avail_reg
)
884 || (TEST_BIT (du
->require_call_save_reg
, inum
)
885 && (call_used_regs
[avail_reg
] || call_used_regs
[REGNO (reg_use
)])))
888 /* If register is a callee-saved register it must be saved in the frame.
889 call saved registers can not be added to regs_ever_live after reload,
890 as it would invalidate most elimination offsets */
891 return regs_ever_live
[avail_reg
] || call_used_regs
[avail_reg
];
894 /* Return 1 if INSN is a conditional move */
900 return (GET_CODE (insn
) == INSN
901 && GET_CODE (PATTERN (insn
)) == SET
902 && GET_CODE (SET_SRC (PATTERN (insn
))) == IF_THEN_ELSE
);
905 /* Searches X for the first reference to REGNO, returning the rtx of the
906 reference found if any. Otherwise, returns NULL_RTX. */
909 regno_first_use_in (regno
, x
)
913 register const char *fmt
;
917 if (GET_CODE (x
) == REG
&& REGNO (x
) == regno
)
920 fmt
= GET_RTX_FORMAT (GET_CODE (x
));
921 for (i
= 0; i
<= GET_RTX_LENGTH (GET_CODE (x
)) - 1; i
++)
925 if ((tem
= regno_first_use_in (regno
, XEXP (x
, i
))))
929 else if (fmt
[i
] == 'E')
930 for (j
= XVECLEN (x
, i
) - 1; j
>= 0; j
--)
931 if ((tem
= regno_first_use_in (regno
, XVECEXP (x
, i
, j
))))
938 /* Dump def/use chain DU to RTL_DUMP_FILE, given insns in UID_RUID and
939 which regs are live at end, GLOBAL_LIVE_AT_END */
942 dump_def_use_chain (global_live_at_end
, du
, uid_ruid
)
943 HARD_REG_SET
*global_live_at_end
;
945 varray_type
*uid_ruid
;
950 for (r
= 0; r
< FIRST_PSEUDO_REGISTER
; r
++)
954 for (inum
= 0; inum
<= du
->high_bound
; inum
++)
956 rtx insn
= VARRAY_RTX (*uid_ruid
, inum
);
959 || GET_RTX_CLASS (GET_CODE
963 reg_use
= regno_first_use_in (r
, PATTERN (insn
));
967 if (!set
&& (TEST_BIT (du
->defs
[r
], inum
)
968 || TEST_BIT (du
->uses
[r
], inum
)))
970 fprintf (rtl_dump_file
, "Register %s: ", reg_names
[r
]);
972 fprintf (rtl_dump_file
, "Fixed ");
973 else if (call_fixed_regs
[r
])
974 fprintf (rtl_dump_file
, "Call Fixed ");
975 if (TEST_HARD_REG_BIT (*global_live_at_end
, r
))
976 fprintf (rtl_dump_file
, "Live at Exit ");
980 if (TEST_BIT (du
->defs
[r
], inum
))
981 fprintf (rtl_dump_file
, "=%d ", INSN_UID (insn
));
982 if (TEST_BIT (du
->uses
[r
], inum
))
983 fprintf (rtl_dump_file
, "%d ", INSN_UID (insn
));
987 fprintf (rtl_dump_file
, "\n");
991 /* Dump info for extended basic block EBB having root EB */
994 dump_ext_bb_info (eb
, ebb
)
996 ext_basic_blocks
*ebb
;
1001 for (b
= 0; b
< n_basic_blocks
; b
++)
1003 if (TEST_BIT (ebb
->basic_block
[eb
], b
))
1007 #ifndef RENAME_EXTENDED_BLOCKS
1008 fprintf (rtl_dump_file
, "\nBasic block %d: ", b
);
1010 fprintf (rtl_dump_file
, "\nExtended basic block %d: ", b
);
1014 fprintf (rtl_dump_file
, "%d ", b
);
1017 if (TEST_BIT (ebb
->exit
[eb
], b
))
1018 fprintf (rtl_dump_file
, "(exit) ");
1022 fprintf (rtl_dump_file
, "\n");
1025 /* Initialize EBB with extended basic block info if RENAME_EXTENDED_BLOCKS is
1026 defined. Otherwise just use basic blocks */
1029 find_ext_basic_blocks (ebb
)
1030 ext_basic_blocks
*ebb
;
1032 sbitmap bb_processed
;
1035 bb_processed
= sbitmap_alloc (n_basic_blocks
);
1036 sbitmap_zero (bb_processed
);
1038 #ifndef RENAME_EXTENDED_BLOCKS
1039 for (b
= 0; b
< n_basic_blocks
; b
++)
1041 basic_block bb
= BASIC_BLOCK (b
);
1042 SET_BIT (ebb
->basic_block
[bb
->index
], bb
->index
);
1045 for (b
= 0; b
< n_basic_blocks
; b
++)
1048 basic_block bb
= BASIC_BLOCK (b
);
1049 if (!TEST_BIT (bb_processed
, b
))
1051 find_one_ext_basic_block (bb
->index
, bb
, &bb_processed
, ebb
);
1055 sbitmap_free (bb_processed
);
1058 /* Find one extended basic block EBB having root ENTRY containing block
1062 find_one_ext_basic_block (entry
, bb
, bb_processed
, ebb
)
1065 sbitmap
*bb_processed
;
1066 ext_basic_blocks
*ebb
;
1070 if (!TEST_BIT (*bb_processed
, bb
->index
))
1072 SET_BIT (ebb
->basic_block
[entry
], bb
->index
);
1073 SET_BIT (*bb_processed
, bb
->index
);
1076 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
1077 if (!TEST_BIT (*bb_processed
, e
->dest
->index
))
1079 if (!e
->dest
->pred
->pred_next
1080 && (!TEST_BIT (*bb_processed
, e
->dest
->index
)))
1081 find_one_ext_basic_block (entry
, e
->dest
, bb_processed
, ebb
);
1083 SET_BIT (ebb
->exit
[entry
], bb
->index
);
1087 /* Find the register class for register REG_USE having TYPE (DESTINATION or
1088 SOURCE) in INSN. Use DEFAULT_CLASS if we cannot determine a class. */
1090 static enum reg_class
1091 get_reg_class (insn
, reg_use
, type
, default_class
)
1095 enum reg_class default_class
;
1099 extract_insn (insn
);
1100 constrain_operands (1);
1101 alt
= which_alternative
;
1103 preprocess_constraints ();
1105 if (type
== DESTINATION
)
1107 for (id
= 0; id
< recog_data
.n_operands
; id
++)
1108 if (rtx_equal_p (recog_data
.operand
[id
], reg_use
))
1112 else if (type
== SOURCE
)
1113 for (id
= recog_data
.n_operands
- 1; id
>= 0; id
--)
1114 if (rtx_equal_p (recog_data
.operand
[id
], reg_use
))
1117 if (id
== -1 || id
== recog_data
.n_operands
)
1118 return default_class
;
1120 return recog_op_alt
[id
][alt
].class;