/* Allocate registers for pseudo-registers that span basic blocks.
Copyright (C) 1987, 1988, 1991, 1994, 1996, 1997, 1998,
- 1999, 2000, 2002, 2003 Free Software Foundation, Inc.
+ 1999, 2000, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-
#include "machmode.h"
#include "hard-reg-set.h"
#include "rtl.h"
#include "tm_p.h"
#include "flags.h"
-#include "basic-block.h"
#include "regs.h"
#include "function.h"
#include "insn-config.h"
+#include "recog.h"
#include "reload.h"
#include "output.h"
#include "toplev.h"
static void dump_conflicts (FILE *);
static void reg_becomes_live (rtx, rtx, void *);
static void reg_dies (int, enum machine_mode, struct insn_chain *);
+
+static void allocate_bb_info (void);
+static void free_bb_info (void);
+static bool check_earlyclobber (rtx);
+static void mark_reg_use_for_earlyclobber_1 (rtx *, void *);
+static int mark_reg_use_for_earlyclobber (rtx *, void *);
+static void calculate_local_reg_bb_info (void);
+static void set_up_bb_rts_numbers (void);
+static int rpost_cmp (const void *, const void *);
+static void calculate_reg_pav (void);
+static void modify_reg_pav (void);
+static void make_accurate_live_analysis (void);
+
\f
+
/* Perform allocation of pseudo-registers not allocated by local_alloc.
FILE is a file to output debugging information on,
or zero if such output is not desired.
size_t i;
rtx x;
+ make_accurate_live_analysis ();
+
max_allocno = 0;
/* A machine may have certain hard registers that
&& (! current_function_has_nonlocal_label
|| REG_N_CALLS_CROSSED (i) == 0))
{
- if (reg_renumber[i] < 0 && reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
+ if (reg_renumber[i] < 0
+ && reg_may_share[i] && reg_allocno[reg_may_share[i]] >= 0)
reg_allocno[i] = reg_allocno[reg_may_share[i]];
else
reg_allocno[i] = max_allocno++;
- if (REG_LIVE_LENGTH (i) == 0)
- abort ();
+ gcc_assert (REG_LIVE_LENGTH (i));
}
else
reg_allocno[i] = -1;
if (reg_renumber[i] >= 0)
{
int regno = reg_renumber[i];
- int endregno = regno + HARD_REGNO_NREGS (regno, PSEUDO_REGNO_MODE (i));
+ int endregno = regno + hard_regno_nregs[regno][PSEUDO_REGNO_MODE (i)];
int j;
for (j = regno; j < endregno; j++)
static void
global_conflicts (void)
{
- int i;
+ unsigned i;
basic_block b;
rtx insn;
int *block_start_allocnos;
since one hard reg can be used with various sizes.
Therefore, we must require that all the hard regs
implicitly live as part of a multi-word hard reg
- are explicitly marked in basic_block_live_at_start. */
+ be explicitly marked in basic_block_live_at_start. */
{
regset old = b->global_live_at_start;
int ax = 0;
+ reg_set_iterator rsi;
REG_SET_TO_HARD_REG_SET (hard_regs_live, old);
- EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i,
- {
- int a = reg_allocno[i];
- if (a >= 0)
- {
- SET_ALLOCNO_LIVE (a);
- block_start_allocnos[ax++] = a;
- }
- else if ((a = reg_renumber[i]) >= 0)
- mark_reg_live_nc
- (a, PSEUDO_REGNO_MODE (i));
- });
+ EXECUTE_IF_SET_IN_REG_SET (old, FIRST_PSEUDO_REGISTER, i, rsi)
+ {
+ int a = reg_allocno[i];
+ if (a >= 0)
+ {
+ SET_ALLOCNO_LIVE (a);
+ block_start_allocnos[ax++] = a;
+ }
+ else if ((a = reg_renumber[i]) >= 0)
+ mark_reg_live_nc (a, PSEUDO_REGNO_MODE (i));
+ }
/* Record that each allocno now live conflicts with each hard reg
now live.
evaluates X.
3. Either X or Y is not evaluated on the path to P
- (ie it is used uninitialized) and thus the
+ (i.e. it is used uninitialized) and thus the
conflict can be ignored.
In cases #1 and #2 the conflict will be recorded when we
regs live across such edges. */
{
edge e;
+ edge_iterator ei;
- for (e = b->pred; e ; e = e->pred_next)
+ FOR_EACH_EDGE (e, ei, b->preds)
if (e->flags & EDGE_ABNORMAL)
break;
{
rtx set = XVECEXP (PATTERN (insn), 0, i);
if (GET_CODE (set) == SET
- && GET_CODE (SET_DEST (set)) != REG
+ && !REG_P (SET_DEST (set))
&& !rtx_equal_p (reg, SET_DEST (set))
&& reg_overlap_mentioned_p (reg, SET_DEST (set)))
used_in_output = 1;
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
if (INSN_P (insn)
&& (set = single_set (insn)) != 0
- && GET_CODE (SET_DEST (set)) == REG
+ && REG_P (SET_DEST (set))
&& reg_allocno[REGNO (SET_DEST (set))] >= 0)
for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
if (REG_NOTE_KIND (link) == REG_DEAD
- && GET_CODE (XEXP (link, 0)) == REG
+ && REG_P (XEXP (link, 0))
&& reg_allocno[REGNO (XEXP (link, 0))] >= 0
&& ! CONFLICTP (reg_allocno[REGNO (SET_DEST (set))],
reg_allocno[REGNO (XEXP (link, 0))]))
|| ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode)))
{
int j;
- int lim = regno + HARD_REGNO_NREGS (regno, mode);
+ int lim = regno + hard_regno_nregs[regno][mode];
for (j = regno + 1;
(j < lim
&& ! TEST_HARD_REG_BIT (used, j));
REGNO_REG_CLASS (i))))
{
int j;
- int lim = i + HARD_REGNO_NREGS (i, mode);
+ int lim = i + hard_regno_nregs[i][mode];
for (j = i + 1;
(j < lim
&& ! TEST_HARD_REG_BIT (used, j)
REGNO_REG_CLASS (i))))
{
int j;
- int lim = i + HARD_REGNO_NREGS (i, mode);
+ int lim = i + hard_regno_nregs[i][mode];
for (j = i + 1;
(j < lim
&& ! TEST_HARD_REG_BIT (used, j)
register, but the check of allocno[num].size above
was not enough. Sometimes we need more than one
register for a single-word value. */
- && HARD_REGNO_NREGS (regno, mode) == 1
+ && hard_regno_nregs[regno][mode] == 1
&& (allocno[num].calls_crossed == 0
|| accept_call_clobbered
|| ! HARD_REGNO_CALL_PART_CLOBBERED (regno, mode))
{
int r = reg_renumber[k];
int endregno
- = r + HARD_REGNO_NREGS (r, PSEUDO_REGNO_MODE (k));
+ = r + hard_regno_nregs[r][PSEUDO_REGNO_MODE (k)];
if (regno >= r && regno < endregno)
reg_renumber[k] = -1;
/* Make a set of the hard regs being allocated. */
CLEAR_HARD_REG_SET (this_reg);
- lim = best_reg + HARD_REGNO_NREGS (best_reg, mode);
+ lim = best_reg + hard_regno_nregs[best_reg][mode];
for (j = best_reg; j < lim; j++)
{
SET_HARD_REG_BIT (this_reg, j);
IOR_HARD_REG_SET (allocno[ialloc].hard_reg_conflicts, hard_regs_live);
for (j = allocno_row_words - 1; j >= 0; j--)
- {
-#if 0
- int k;
- for (k = 0; k < n_no_conflict_pairs; k++)
- if (! ((j == no_conflict_pairs[k].allocno1
- && ialloc == no_conflict_pairs[k].allocno2)
- ||
- (j == no_conflict_pairs[k].allocno2
- && ialloc == no_conflict_pairs[k].allocno1)))
-#endif /* 0 */
- conflicts[ialloc_prod + j] |= allocnos_live[j];
- }
+ conflicts[ialloc_prod + j] |= allocnos_live[j];
}
}
if (GET_CODE (reg) == SUBREG)
reg = SUBREG_REG (reg);
- if (GET_CODE (reg) != REG)
+ if (!REG_P (reg))
return;
regs_set[n_regs_set++] = reg;
/* Handle hardware regs (and pseudos allocated to hard regs). */
if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
{
- int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
while (regno < last)
{
record_one_conflict (regno);
/* Like mark_reg_set except notice just CLOBBERs; ignore SETs. */
static void
-mark_reg_clobber (rtx reg, rtx setter, void *data ATTRIBUTE_UNUSED)
+mark_reg_clobber (rtx reg, rtx setter, void *data)
{
if (GET_CODE (setter) == CLOBBER)
mark_reg_store (reg, setter, data);
if (GET_CODE (reg) == SUBREG)
reg = SUBREG_REG (reg);
- if (GET_CODE (reg) != REG)
+ if (!REG_P (reg))
return;
regno = REGNO (reg);
/* Handle hardware regs (and pseudos allocated to hard regs). */
if (regno < FIRST_PSEUDO_REGISTER && ! fixed_regs[regno])
{
- int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
while (regno < last)
{
record_one_conflict (regno);
{
/* Pseudo regs already assigned hardware regs are treated
almost the same as explicit hardware regs. */
- int last = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
while (regno < last)
{
CLEAR_HARD_REG_BIT (hard_regs_live, regno);
static void
mark_reg_live_nc (int regno, enum machine_mode mode)
{
- int last = regno + HARD_REGNO_NREGS (regno, mode);
+ int last = regno + hard_regno_nregs[regno][mode];
while (regno < last)
{
SET_HARD_REG_BIT (hard_regs_live, regno);
/* Get the reg number for both SRC and DEST.
If neither is a reg, give up. */
- if (GET_CODE (src) == REG)
+ if (REG_P (src))
src_regno = REGNO (src);
- else if (GET_CODE (src) == SUBREG && GET_CODE (SUBREG_REG (src)) == REG)
+ else if (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src)))
{
src_regno = REGNO (SUBREG_REG (src));
else
return;
- if (GET_CODE (dest) == REG)
+ if (REG_P (dest))
dest_regno = REGNO (dest);
- else if (GET_CODE (dest) == SUBREG && GET_CODE (SUBREG_REG (dest)) == REG)
+ else if (GET_CODE (dest) == SUBREG && REG_P (SUBREG_REG (dest)))
{
dest_regno = REGNO (SUBREG_REG (dest));
SET_REGBIT (hard_reg_preferences,
reg_allocno[src_regno], dest_regno);
for (i = dest_regno;
- i < dest_regno + HARD_REGNO_NREGS (dest_regno, GET_MODE (dest));
+ i < dest_regno + hard_regno_nregs[dest_regno][GET_MODE (dest)];
i++)
SET_REGBIT (hard_reg_full_preferences, reg_allocno[src_regno], i);
}
SET_REGBIT (hard_reg_preferences,
reg_allocno[dest_regno], src_regno);
for (i = src_regno;
- i < src_regno + HARD_REGNO_NREGS (src_regno, GET_MODE (src));
+ i < src_regno + hard_regno_nregs[src_regno][GET_MODE (src)];
i++)
SET_REGBIT (hard_reg_full_preferences, reg_allocno[dest_regno], i);
}
if (GET_CODE (reg) == SUBREG)
reg = SUBREG_REG (reg);
- if (GET_CODE (reg) != REG)
+ if (!REG_P (reg))
return;
regno = REGNO (reg);
if (regno < FIRST_PSEUDO_REGISTER)
{
- int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg));
+ int nregs = hard_regno_nregs[regno][GET_MODE (reg)];
while (nregs-- > 0)
{
SET_REGNO_REG_SET (live_relevant_regs, regno);
{
if (regno < FIRST_PSEUDO_REGISTER)
{
- int nregs = HARD_REGNO_NREGS (regno, mode);
+ int nregs = hard_regno_nregs[regno][mode];
while (nregs-- > 0)
{
CLEAR_REGNO_REG_SET (live_relevant_regs, regno);
struct insn_chain **p = &reload_insn_chain;
struct insn_chain *prev = 0;
basic_block b = ENTRY_BLOCK_PTR->next_bb;
- regset_head live_relevant_regs_head;
- live_relevant_regs = INITIALIZE_REG_SET (live_relevant_regs_head);
+ live_relevant_regs = ALLOC_REG_SET (®_obstack);
for (; first; first = NEXT_INSN (first))
{
if (first == BB_HEAD (b))
{
- int i;
+ unsigned i;
+ bitmap_iterator bi;
CLEAR_REG_SET (live_relevant_regs);
- EXECUTE_IF_SET_IN_BITMAP
- (b->global_live_at_start, 0, i,
- {
- if (i < FIRST_PSEUDO_REGISTER
- ? ! TEST_HARD_REG_BIT (eliminable_regset, i)
- : reg_renumber[i] >= 0)
- SET_REGNO_REG_SET (live_relevant_regs, i);
- });
+ EXECUTE_IF_SET_IN_BITMAP (b->global_live_at_start, 0, i, bi)
+ {
+ if (i < FIRST_PSEUDO_REGISTER
+ ? ! TEST_HARD_REG_BIT (eliminable_regset, i)
+ : reg_renumber[i] >= 0)
+ SET_REGNO_REG_SET (live_relevant_regs, i);
+ }
}
- if (GET_CODE (first) != NOTE && GET_CODE (first) != BARRIER)
+ if (!NOTE_P (first) && !BARRIER_P (first))
{
c = new_insn_chain ();
c->prev = prev;
for (link = REG_NOTES (first); link; link = XEXP (link, 1))
if (REG_NOTE_KIND (link) == REG_DEAD
- && GET_CODE (XEXP (link, 0)) == REG)
+ && REG_P (XEXP (link, 0)))
reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
c);
for (link = REG_NOTES (first); link; link = XEXP (link, 1))
if (REG_NOTE_KIND (link) == REG_UNUSED
- && GET_CODE (XEXP (link, 0)) == REG)
+ && REG_P (XEXP (link, 0)))
reg_dies (REGNO (XEXP (link, 0)), GET_MODE (XEXP (link, 0)),
c);
}
the previous real insn is a JUMP_INSN. */
if (b == EXIT_BLOCK_PTR)
{
- for (first = NEXT_INSN (first) ; first; first = NEXT_INSN (first))
- if (INSN_P (first)
- && GET_CODE (PATTERN (first)) != USE
- && ! ((GET_CODE (PATTERN (first)) == ADDR_VEC
- || GET_CODE (PATTERN (first)) == ADDR_DIFF_VEC)
- && prev_real_insn (first) != 0
- && GET_CODE (prev_real_insn (first)) == JUMP_INSN))
- abort ();
+#ifdef ENABLE_CHECKING
+ for (first = NEXT_INSN (first); first; first = NEXT_INSN (first))
+ gcc_assert (!INSN_P (first)
+ || GET_CODE (PATTERN (first)) == USE
+ || ((GET_CODE (PATTERN (first)) == ADDR_VEC
+ || GET_CODE (PATTERN (first)) == ADDR_DIFF_VEC)
+ && prev_real_insn (first) != 0
+ && JUMP_P (prev_real_insn (first))));
+#endif
break;
}
}
fprintf (file, " %d", i);
fprintf (file, "\n\n");
}
+
+\f
+
+/* This page contains code to make live information more accurate.
+ The accurate register liveness at program point P means:
+ o there is a path from P to usage of the register and the
+ register is not redefined or killed on the path.
+ o register at P is partially available, i.e. there is a path from
+ a register definition to the point P and the register is not
+ killed (clobbered) on the path
+
+ The standard GCC live information means only the first condition.
+ Without the partial availability, there will be more register
+ conflicts and as a consequence worse register allocation. The
+ typical example where the information can be different is a
+ register initialized in the loop at the basic block preceding the
+ loop in CFG. */
+
+/* The following structure contains basic block data flow information
+ used to calculate partial availability of registers. */
+
+struct bb_info
+{
+ /* The basic block reverse post-order number. */
+ int rts_number;
+ /* Registers used uninitialized in an insn in which there is an
+ early clobbered register might get the same hard register. */
+ bitmap earlyclobber;
+ /* Registers correspondingly killed (clobbered) and defined but not
+ killed afterward in the basic block. */
+ bitmap killed, avloc;
+ /* Registers partially available and living (in other words whose
+ values were calculated and used) correspondingly at the start
+ and end of the basic block. */
+ bitmap live_pavin, live_pavout;
+};
+
+/* Macros for accessing data flow information of basic blocks. */
+
+#define BB_INFO(BB) ((struct bb_info *) (BB)->aux)
+#define BB_INFO_BY_INDEX(N) BB_INFO (BASIC_BLOCK(N))
+
+/* The function allocates the info structures of each basic block. It
+ also initialized LIVE_PAVIN and LIVE_PAVOUT as if all hard
+ registers were partially available. */
+
+static void
+allocate_bb_info (void)
+{
+ int i;
+ basic_block bb;
+ struct bb_info *bb_info;
+ bitmap init;
+
+ alloc_aux_for_blocks (sizeof (struct bb_info));
+ init = BITMAP_ALLOC (NULL);
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ bitmap_set_bit (init, i);
+ FOR_EACH_BB (bb)
+ {
+ bb_info = bb->aux;
+ bb_info->earlyclobber = BITMAP_ALLOC (NULL);
+ bb_info->avloc = BITMAP_ALLOC (NULL);
+ bb_info->killed = BITMAP_ALLOC (NULL);
+ bb_info->live_pavin = BITMAP_ALLOC (NULL);
+ bb_info->live_pavout = BITMAP_ALLOC (NULL);
+ bitmap_copy (bb_info->live_pavin, init);
+ bitmap_copy (bb_info->live_pavout, init);
+ }
+ BITMAP_FREE (init);
+}
+
+/* The function frees the allocated info of all basic blocks. */
+
+static void
+free_bb_info (void)
+{
+ basic_block bb;
+ struct bb_info *bb_info;
+
+ FOR_EACH_BB (bb)
+ {
+ bb_info = BB_INFO (bb);
+ BITMAP_FREE (bb_info->live_pavout);
+ BITMAP_FREE (bb_info->live_pavin);
+ BITMAP_FREE (bb_info->killed);
+ BITMAP_FREE (bb_info->avloc);
+ BITMAP_FREE (bb_info->earlyclobber);
+ }
+ free_aux_for_blocks ();
+}
+
+/* The function modifies local info for register REG being changed in
+ SETTER. DATA is used to pass the current basic block info. */
+
+static void
+mark_reg_change (rtx reg, rtx setter, void *data)
+{
+ int regno;
+ basic_block bb = data;
+ struct bb_info *bb_info = BB_INFO (bb);
+
+ if (GET_CODE (reg) == SUBREG)
+ reg = SUBREG_REG (reg);
+
+ if (!REG_P (reg))
+ return;
+
+ regno = REGNO (reg);
+ bitmap_set_bit (bb_info->killed, regno);
+
+ if (GET_CODE (setter) != CLOBBER)
+ bitmap_set_bit (bb_info->avloc, regno);
+ else
+ bitmap_clear_bit (bb_info->avloc, regno);
+}
+
+/* Classes of registers which could be early clobbered in the current
+ insn. */
+
+DEF_VEC_P(int);
+DEF_VEC_ALLOC_P(int,heap);
+
+static VEC(int,heap) *earlyclobber_regclass;
+
+/* This function finds and stores register classes that could be early
+ clobbered in INSN. If any earlyclobber classes are found, the function
+ returns TRUE, in all other cases it returns FALSE. */
+
+static bool
+check_earlyclobber (rtx insn)
+{
+ int opno;
+ bool found = false;
+
+ extract_insn (insn);
+
+ VEC_truncate (int, earlyclobber_regclass, 0);
+ for (opno = 0; opno < recog_data.n_operands; opno++)
+ {
+ char c;
+ bool amp_p;
+ int i;
+ enum reg_class class;
+ const char *p = recog_data.constraints[opno];
+
+ class = NO_REGS;
+ amp_p = false;
+ for (;;)
+ {
+ c = *p;
+ switch (c)
+ {
+ case '=': case '+': case '?':
+ case '#': case '!':
+ case '*': case '%':
+ case 'm': case '<': case '>': case 'V': case 'o':
+ case 'E': case 'F': case 'G': case 'H':
+ case 's': case 'i': case 'n':
+ case 'I': case 'J': case 'K': case 'L':
+ case 'M': case 'N': case 'O': case 'P':
+ case 'X':
+ case '0': case '1': case '2': case '3': case '4':
+ case '5': case '6': case '7': case '8': case '9':
+ /* These don't say anything we care about. */
+ break;
+
+ case '&':
+ amp_p = true;
+ break;
+ case '\0':
+ case ',':
+ if (amp_p && class != NO_REGS)
+ {
+ int rc;
+
+ found = true;
+ for (i = 0;
+ VEC_iterate (int, earlyclobber_regclass, i, rc);
+ i++)
+ {
+ if (rc == (int) class)
+ goto found_rc;
+ }
+
+ /* We use VEC_quick_push here because
+ earlyclobber_regclass holds no more than
+ N_REG_CLASSES elements. */
+ VEC_quick_push (int, earlyclobber_regclass, (int) class);
+ found_rc:
+ ;
+ }
+
+ amp_p = false;
+ class = NO_REGS;
+ break;
+
+ case 'r':
+ class = GENERAL_REGS;
+ break;
+
+ default:
+ class = REG_CLASS_FROM_CONSTRAINT (c, p);
+ break;
+ }
+ if (c == '\0')
+ break;
+ p += CONSTRAINT_LEN (c, p);
+ }
+ }
+
+ return found;
+}
+
+/* The function checks that pseudo-register *X has a class
+ intersecting with the class of pseudo-register could be early
+ clobbered in the same insn.
+ This function is a no-op if earlyclobber_regclass is empty. */
+
+static int
+mark_reg_use_for_earlyclobber (rtx *x, void *data ATTRIBUTE_UNUSED)
+{
+ enum reg_class pref_class, alt_class;
+ int i, regno;
+ basic_block bb = data;
+ struct bb_info *bb_info = BB_INFO (bb);
+
+ if (REG_P (*x) && REGNO (*x) >= FIRST_PSEUDO_REGISTER)
+ {
+ int rc;
+
+ regno = REGNO (*x);
+ if (bitmap_bit_p (bb_info->killed, regno)
+ || bitmap_bit_p (bb_info->avloc, regno))
+ return 0;
+ pref_class = reg_preferred_class (regno);
+ alt_class = reg_alternate_class (regno);
+ for (i = 0; VEC_iterate (int, earlyclobber_regclass, i, rc); i++)
+ {
+ if (reg_classes_intersect_p (rc, pref_class)
+ || (rc != NO_REGS
+ && reg_classes_intersect_p (rc, alt_class)))
+ {
+ bitmap_set_bit (bb_info->earlyclobber, regno);
+ break;
+ }
+ }
+ }
+ return 0;
+}
+
+/* The function processes all pseudo-registers in *X with the aid of
+ previous function. */
+
+static void
+mark_reg_use_for_earlyclobber_1 (rtx *x, void *data)
+{
+ for_each_rtx (x, mark_reg_use_for_earlyclobber, data);
+}
+
+/* The function calculates local info for each basic block. */
+
+static void
+calculate_local_reg_bb_info (void)
+{
+ basic_block bb;
+ rtx insn, bound;
+
+ /* We know that earlyclobber_regclass holds no more than
+ N_REG_CLASSES elements. See check_earlyclobber. */
+ earlyclobber_regclass = VEC_alloc (int, heap, N_REG_CLASSES);
+ FOR_EACH_BB (bb)
+ {
+ bound = NEXT_INSN (BB_END (bb));
+ for (insn = BB_HEAD (bb); insn != bound; insn = NEXT_INSN (insn))
+ if (INSN_P (insn))
+ {
+ note_stores (PATTERN (insn), mark_reg_change, bb);
+ if (check_earlyclobber (insn))
+ note_uses (&PATTERN (insn), mark_reg_use_for_earlyclobber_1, bb);
+ }
+ }
+ VEC_free (int, heap, earlyclobber_regclass);
+}
+
+/* The function sets up reverse post-order number of each basic
+ block. */
+
+static void
+set_up_bb_rts_numbers (void)
+{
+ int i;
+ int *rts_order;
+
+ rts_order = xmalloc (sizeof (int) * n_basic_blocks);
+ flow_reverse_top_sort_order_compute (rts_order);
+ for (i = 0; i < n_basic_blocks; i++)
+ BB_INFO_BY_INDEX (rts_order [i])->rts_number = i;
+ free (rts_order);
+}
+
+/* Compare function for sorting blocks in reverse postorder. */
+
+static int
+rpost_cmp (const void *bb1, const void *bb2)
+{
+ basic_block b1 = *(basic_block *) bb1, b2 = *(basic_block *) bb2;
+
+ return BB_INFO (b2)->rts_number - BB_INFO (b1)->rts_number;
+}
+
+/* Temporary bitmap used for live_pavin, live_pavout calculation. */
+static bitmap temp_bitmap;
+
+DEF_VEC_P(basic_block);
+DEF_VEC_ALLOC_P(basic_block,heap);
+
+/* The function calculates partial register availability according to
+ the following equations:
+
+ bb.live_pavin
+ = empty for entry block
+ | union (live_pavout of predecessors) & global_live_at_start
+ bb.live_pavout = union (bb.live_pavin - bb.killed, bb.avloc)
+ & global_live_at_end */
+
+static void
+calculate_reg_pav (void)
+{
+ basic_block bb, succ;
+ edge e;
+ int i, nel;
+ VEC(basic_block,heap) *bbs, *new_bbs, *temp;
+ basic_block *bb_array;
+ sbitmap wset;
+
+ bbs = VEC_alloc (basic_block, heap, n_basic_blocks);
+ new_bbs = VEC_alloc (basic_block, heap, n_basic_blocks);
+ temp_bitmap = BITMAP_ALLOC (NULL);
+ FOR_EACH_BB (bb)
+ {
+ VEC_quick_push (basic_block, bbs, bb);
+ }
+ wset = sbitmap_alloc (n_basic_blocks + 1);
+ while (VEC_length (basic_block, bbs))
+ {
+ bb_array = VEC_address (basic_block, bbs);
+ nel = VEC_length (basic_block, bbs);
+ qsort (bb_array, nel, sizeof (basic_block), rpost_cmp);
+ sbitmap_zero (wset);
+ for (i = 0; i < nel; i++)
+ {
+ edge_iterator ei;
+ struct bb_info *bb_info;
+ bitmap bb_live_pavin, bb_live_pavout;
+
+ bb = bb_array [i];
+ bb_info = BB_INFO (bb);
+ bb_live_pavin = bb_info->live_pavin;
+ bb_live_pavout = bb_info->live_pavout;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ basic_block pred = e->src;
+
+ if (pred->index != ENTRY_BLOCK)
+ bitmap_ior_into (bb_live_pavin, BB_INFO (pred)->live_pavout);
+ }
+ bitmap_and_into (bb_live_pavin, bb->global_live_at_start);
+ bitmap_ior_and_compl (temp_bitmap, bb_info->avloc,
+ bb_live_pavin, bb_info->killed);
+ bitmap_and_into (temp_bitmap, bb->global_live_at_end);
+ if (! bitmap_equal_p (temp_bitmap, bb_live_pavout))
+ {
+ bitmap_copy (bb_live_pavout, temp_bitmap);
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ succ = e->dest;
+ if (succ->index != EXIT_BLOCK
+ && !TEST_BIT (wset, succ->index))
+ {
+ SET_BIT (wset, succ->index);
+ VEC_quick_push (basic_block, new_bbs, succ);
+ }
+ }
+ }
+ }
+ temp = bbs;
+ bbs = new_bbs;
+ new_bbs = temp;
+ VEC_truncate (basic_block, new_bbs, 0);
+ }
+ sbitmap_free (wset);
+ BITMAP_FREE (temp_bitmap);
+ VEC_free (basic_block, heap, new_bbs);
+ VEC_free (basic_block, heap, bbs);
+}
+
+/* The function modifies partial availability information for two
+ special cases to prevent incorrect work of the subsequent passes
+ with the accurate live information based on the partial
+ availability. */
+
+static void
+modify_reg_pav (void)
+{
+ basic_block bb;
+ struct bb_info *bb_info;
+#ifdef STACK_REGS
+ int i;
+ HARD_REG_SET zero, stack_hard_regs, used;
+ bitmap stack_regs;
+
+ CLEAR_HARD_REG_SET (zero);
+ CLEAR_HARD_REG_SET (stack_hard_regs);
+ for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
+ SET_HARD_REG_BIT(stack_hard_regs, i);
+ stack_regs = BITMAP_ALLOC (NULL);
+ for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
+ {
+ COPY_HARD_REG_SET (used, reg_class_contents[reg_preferred_class (i)]);
+ IOR_HARD_REG_SET (used, reg_class_contents[reg_alternate_class (i)]);
+ AND_HARD_REG_SET (used, stack_hard_regs);
+ GO_IF_HARD_REG_EQUAL(used, zero, skip);
+ bitmap_set_bit (stack_regs, i);
+ skip:
+ ;
+ }
+#endif
+ FOR_EACH_BB (bb)
+ {
+ bb_info = BB_INFO (bb);
+
+ /* Reload can assign the same hard register to uninitialized
+ pseudo-register and early clobbered pseudo-register in an
+ insn if the pseudo-register is used first time in given BB
+ and not lived at the BB start. To prevent this we don't
+ change life information for such pseudo-registers. */
+ bitmap_ior_into (bb_info->live_pavin, bb_info->earlyclobber);
+#ifdef STACK_REGS
+ /* We can not use the same stack register for uninitialized
+ pseudo-register and another living pseudo-register because if the
+ uninitialized pseudo-register dies, subsequent pass reg-stack
+ will be confused (it will believe that the other register
+ dies). */
+ bitmap_ior_into (bb_info->live_pavin, stack_regs);
+#endif
+ }
+#ifdef STACK_REGS
+ BITMAP_FREE (stack_regs);
+#endif
+}
+
+/* The following function makes live information more accurate by
+ modifying global_live_at_start and global_live_at_end of basic
+ blocks.
+
+ The standard GCC life analysis permits registers to live
+ uninitialized, for example:
+
+ R is never used
+ .....
+ Loop:
+ R is defined
+ ...
+ R is used.
+
+ With normal life_analysis, R would be live before "Loop:".
+ The result is that R causes many interferences that do not
+ serve any purpose.
+
+ After the function call a register lives at a program point
+ only if it is initialized on a path from CFG entry to the
+ program point. */
+
+static void
+make_accurate_live_analysis (void)
+{
+ basic_block bb;
+ struct bb_info *bb_info;
+
+ max_regno = max_reg_num ();
+ compact_blocks ();
+ allocate_bb_info ();
+ calculate_local_reg_bb_info ();
+ set_up_bb_rts_numbers ();
+ calculate_reg_pav ();
+ modify_reg_pav ();
+ FOR_EACH_BB (bb)
+ {
+ bb_info = BB_INFO (bb);
+
+ bitmap_and_into (bb->global_live_at_start, bb_info->live_pavin);
+ bitmap_and_into (bb->global_live_at_end, bb_info->live_pavout);
+ }
+ free_bb_info ();
+}
OSDN Git Service
