/* Allocate registers within a basic block, for GNU compiler.
- Copyright (C) 1987, 1988, 1991, 1993 Free Software Foundation, Inc.
+ Copyright (C) 1987, 1988, 1991, 1993, 1994 Free Software Foundation, Inc.
This file is part of GNU CC.
You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
/* Allocation of hard register numbers to pseudo registers is done in
static HARD_REG_SET *qty_phys_sugg;
-/* Element Q is non-zero if there is a suggested register in
- qty_phys_copy_sugg. */
+/* Element Q is the number of suggested registers in qty_phys_copy_sugg. */
-static char *qty_phys_has_copy_sugg;
+static short *qty_phys_num_copy_sugg;
-/* Element Q is non-zero if there is a suggested register in qty_phys_sugg. */
+/* Element Q is the number of suggested registers in qty_phys_sugg. */
-static char *qty_phys_has_sugg;
+static short *qty_phys_num_sugg;
/* Element Q is the number of refs to quantity Q. */
static rtx *qty_scratch_rtx;
+/* Element Q is nonzero if this quantity has been used in a SUBREG
+ that changes its size. */
+
+static char *qty_changes_size;
+
/* Element Q is the register number of one pseudo register whose
reg_qty value is Q, or -1 is this quantity is for a SCRATCH. This
register should be the head of the chain maintained in reg_next_in_qty. */
static int this_insn_number;
static rtx this_insn;
-static void block_alloc ();
-static void update_equiv_regs ();
-static int no_conflict_p ();
-static int combine_regs ();
-static void wipe_dead_reg ();
-static int find_free_reg ();
-static void reg_is_born ();
-static void reg_is_set ();
-static void mark_life ();
-static void post_mark_life ();
-static int qty_compare ();
-static int qty_compare_1 ();
-static int reg_meets_class_p ();
-static void update_qty_class ();
-static int requires_inout_p ();
+static void alloc_qty PROTO((int, enum machine_mode, int, int));
+static void alloc_qty_for_scratch PROTO((rtx, int, rtx, int, int));
+static void validate_equiv_mem_from_store PROTO((rtx, rtx));
+static int validate_equiv_mem PROTO((rtx, rtx, rtx));
+static int memref_referenced_p PROTO((rtx, rtx));
+static int memref_used_between_p PROTO((rtx, rtx, rtx));
+static void optimize_reg_copy_1 PROTO((rtx, rtx, rtx));
+static void optimize_reg_copy_2 PROTO((rtx, rtx, rtx));
+static void update_equiv_regs PROTO((void));
+static void block_alloc PROTO((int));
+static int qty_sugg_compare PROTO((int, int));
+static int qty_sugg_compare_1 PROTO((int *, int *));
+static int qty_compare PROTO((int, int));
+static int qty_compare_1 PROTO((int *, int *));
+static int combine_regs PROTO((rtx, rtx, int, int, rtx, int));
+static int reg_meets_class_p PROTO((int, enum reg_class));
+static int reg_classes_overlap_p PROTO((enum reg_class, enum reg_class,
+ int));
+static void update_qty_class PROTO((int, int));
+static void reg_is_set PROTO((rtx, rtx));
+static void reg_is_born PROTO((rtx, int));
+static void wipe_dead_reg PROTO((rtx, int));
+static int find_free_reg PROTO((enum reg_class, enum machine_mode,
+ int, int, int, int, int));
+static void mark_life PROTO((int, enum machine_mode, int));
+static void post_mark_life PROTO((int, enum machine_mode, int, int, int));
+static int no_conflict_p PROTO((rtx, rtx, rtx));
+static int requires_inout PROTO((char *));
\f
/* Allocate a new quantity (new within current basic block)
for register number REGNO which is born at index BIRTH
qty_min_class[qty] = reg_preferred_class (regno);
qty_alternate_class[qty] = reg_alternate_class (regno);
qty_n_refs[qty] = reg_n_refs[regno];
+ qty_changes_size[qty] = reg_changes_size[regno];
}
\f
/* Similar to `alloc_qty', but allocates a quantity for a SCRATCH rtx
qty_min_class[qty] = class;
qty_alternate_class[qty] = NO_REGS;
qty_n_refs[qty] = 1;
+ qty_changes_size[qty] = 0;
}
\f
/* Main entry point of this file. */
scratch_list_length = max_qty;
scratch_list = (rtx *) xmalloc (scratch_list_length * sizeof (rtx));
- bzero (scratch_list, scratch_list_length * sizeof (rtx));
+ bzero ((char *) scratch_list, scratch_list_length * sizeof (rtx));
scratch_block = (int *) xmalloc (scratch_list_length * sizeof (int));
- bzero (scratch_block, scratch_list_length * sizeof (int));
+ bzero ((char *) scratch_block, scratch_list_length * sizeof (int));
scratch_index = 0;
qty_phys_reg = (short *) alloca (max_qty * sizeof (short));
- qty_phys_copy_sugg = (HARD_REG_SET *) alloca (max_qty * sizeof (HARD_REG_SET));
- qty_phys_has_copy_sugg = (char *) alloca (max_qty * sizeof (char));
+ qty_phys_copy_sugg
+ = (HARD_REG_SET *) alloca (max_qty * sizeof (HARD_REG_SET));
+ qty_phys_num_copy_sugg = (short *) alloca (max_qty * sizeof (short));
qty_phys_sugg = (HARD_REG_SET *) alloca (max_qty * sizeof (HARD_REG_SET));
- qty_phys_has_sugg = (char *) alloca (max_qty * sizeof (char));
+ qty_phys_num_sugg = (short *) alloca (max_qty * sizeof (short));
qty_birth = (int *) alloca (max_qty * sizeof (int));
qty_death = (int *) alloca (max_qty * sizeof (int));
qty_scratch_rtx = (rtx *) alloca (max_qty * sizeof (rtx));
qty_first_reg = (int *) alloca (max_qty * sizeof (int));
qty_size = (int *) alloca (max_qty * sizeof (int));
- qty_mode = (enum machine_mode *) alloca (max_qty * sizeof (enum machine_mode));
+ qty_mode
+ = (enum machine_mode *) alloca (max_qty * sizeof (enum machine_mode));
qty_n_calls_crossed = (int *) alloca (max_qty * sizeof (int));
- qty_min_class = (enum reg_class *) alloca (max_qty * sizeof (enum reg_class));
- qty_alternate_class = (enum reg_class *) alloca (max_qty * sizeof (enum reg_class));
+ qty_min_class
+ = (enum reg_class *) alloca (max_qty * sizeof (enum reg_class));
+ qty_alternate_class
+ = (enum reg_class *) alloca (max_qty * sizeof (enum reg_class));
qty_n_refs = (int *) alloca (max_qty * sizeof (int));
+ qty_changes_size = (char *) alloca (max_qty * sizeof (char));
reg_qty = (int *) alloca (max_regno * sizeof (int));
reg_offset = (char *) alloca (max_regno * sizeof (char));
{
qty_scratch_rtx[i] = 0;
CLEAR_HARD_REG_SET (qty_phys_copy_sugg[i]);
- qty_phys_has_copy_sugg[i] = 0;
+ qty_phys_num_copy_sugg[i] = 0;
CLEAR_HARD_REG_SET (qty_phys_sugg[i]);
- qty_phys_has_sugg[i] = 0;
+ qty_phys_num_sugg[i] = 0;
}
}
else
{
#define CLEAR(vector) \
- bzero ((vector), (sizeof (*(vector))) * next_qty);
+ bzero ((char *) (vector), (sizeof (*(vector))) * next_qty);
CLEAR (qty_scratch_rtx);
CLEAR (qty_phys_copy_sugg);
- CLEAR (qty_phys_has_copy_sugg);
+ CLEAR (qty_phys_num_copy_sugg);
CLEAR (qty_phys_sugg);
- CLEAR (qty_phys_has_sugg);
+ CLEAR (qty_phys_num_sugg);
}
next_qty = 0;
if (dest_death)
d_length++;
- if (GET_CODE (q) == CALL_INSN)
+ /* If the insn in which SRC dies is a CALL_INSN, don't count it
+ as a call that has been crossed. Otherwise, count it. */
+ if (q != p && GET_CODE (q) == CALL_INSN)
{
n_calls++;
if (dest_death)
rtx *reg_equiv_replacement = (rtx *) alloca (max_regno * sizeof (rtx *));
rtx insn;
- bzero (reg_equiv_init_insn, max_regno * sizeof (rtx *));
- bzero (reg_equiv_replacement, max_regno * sizeof (rtx *));
+ bzero ((char *) reg_equiv_init_insn, max_regno * sizeof (rtx *));
+ bzero ((char *) reg_equiv_replacement, max_regno * sizeof (rtx *));
init_alias_analysis ();
the birth of a CLOBBER in the first insn. */
regs_live_at = (HARD_REG_SET *) alloca ((2 * insn_count + 2)
* sizeof (HARD_REG_SET));
- bzero (regs_live_at, (2 * insn_count + 2) * sizeof (HARD_REG_SET));
+ bzero ((char *) regs_live_at, (2 * insn_count + 2) * sizeof (HARD_REG_SET));
/* Initialize table of hardware registers currently live. */
)
{
#ifdef REGISTER_CONSTRAINTS
+ /* If non-negative, is an operand that must match operand 0. */
int must_match_0 = -1;
-
+ /* Counts number of alternatives that require a match with
+ operand 0. */
+ int n_matching_alts = 0;
for (i = 1; i < insn_n_operands[insn_code_number]; i++)
- if (requires_inout_p
- (insn_operand_constraint[insn_code_number][i]))
- must_match_0 = i;
+ {
+ char *p = insn_operand_constraint[insn_code_number][i];
+ int this_match = (requires_inout (p));
+
+ n_matching_alts += this_match;
+ if (this_match == insn_n_alternatives[insn_code_number])
+ must_match_0 = i;
+ }
#endif
r0 = recog_operand[0];
&& ! (i == must_match_0 - 1
&& insn_operand_constraint[insn_code_number][i][0] == '%'))
continue;
+
+ /* Likewise if each alternative has some operand that
+ must match operand zero. In that case, skip any
+ operand that doesn't list operand 0 since we know that
+ the operand always conflicts with operand 0. We
+ ignore commutatity in this case to keep things simple. */
+ if (n_matching_alts == insn_n_alternatives[insn_code_number]
+ && (0 == requires_inout
+ (insn_operand_constraint[insn_code_number][i])))
+ continue;
#endif
r1 = recog_operand[i];
win = combine_regs (r1, r0, may_save_copy,
insn_number, insn, 0);
}
+ if (win)
+ break;
}
}
should have been given a quantity, or else -1 meaning ignore it.
Every quantity should have a known birth and death.
- Order the qtys so we assign them registers in order of
- decreasing length of life. Normally call qsort, but if we
- have only a very small number of quantities, sort them ourselves. */
+ Order the qtys so we assign them registers in order of the
+ number of suggested registers they need so we allocate those with
+ the most restrictive needs first. */
qty_order = (int *) alloca (next_qty * sizeof (int));
for (i = 0; i < next_qty; i++)
{
case 3:
/* Make qty_order[2] be the one to allocate last. */
- if (qty_compare (0, 1) > 0)
+ if (qty_sugg_compare (0, 1) > 0)
EXCHANGE (0, 1);
- if (qty_compare (1, 2) > 0)
+ if (qty_sugg_compare (1, 2) > 0)
EXCHANGE (2, 1);
/* ... Fall through ... */
case 2:
/* Put the best one to allocate in qty_order[0]. */
- if (qty_compare (0, 1) > 0)
+ if (qty_sugg_compare (0, 1) > 0)
EXCHANGE (0, 1);
/* ... Fall through ... */
break;
default:
- qsort (qty_order, next_qty, sizeof (int), qty_compare_1);
+ qsort (qty_order, next_qty, sizeof (int), qty_sugg_compare_1);
}
/* Try to put each quantity in a suggested physical register, if it has one.
for (i = 0; i < next_qty; i++)
{
q = qty_order[i];
- if (qty_phys_has_sugg[q] || qty_phys_has_copy_sugg[q])
+ if (qty_phys_num_sugg[q] != 0 || qty_phys_num_copy_sugg[q] != 0)
qty_phys_reg[q] = find_free_reg (qty_min_class[q], qty_mode[q], q,
0, 1, qty_birth[q], qty_death[q]);
else
qty_phys_reg[q] = -1;
}
+ /* Order the qtys so we assign them registers in order of
+ decreasing length of life. Normally call qsort, but if we
+ have only a very small number of quantities, sort them ourselves. */
+
+ for (i = 0; i < next_qty; i++)
+ qty_order[i] = i;
+
+#define EXCHANGE(I1, I2) \
+ { i = qty_order[I1]; qty_order[I1] = qty_order[I2]; qty_order[I2] = i; }
+
+ switch (next_qty)
+ {
+ case 3:
+ /* Make qty_order[2] be the one to allocate last. */
+ if (qty_compare (0, 1) > 0)
+ EXCHANGE (0, 1);
+ if (qty_compare (1, 2) > 0)
+ EXCHANGE (2, 1);
+
+ /* ... Fall through ... */
+ case 2:
+ /* Put the best one to allocate in qty_order[0]. */
+ if (qty_compare (0, 1) > 0)
+ EXCHANGE (0, 1);
+
+ /* ... Fall through ... */
+
+ case 1:
+ case 0:
+ /* Nothing to do here. */
+ break;
+
+ default:
+ qsort (qty_order, next_qty, sizeof (int), qty_compare_1);
+ }
+
/* Now for each qty that is not a hardware register,
look for a hardware register to put it in.
First try the register class that is cheapest for this qty,
times a register can occur in one insn (surely less than 100).
Multiplying this by 10000 can't overflow. */
register int pri1
- = (((double) (floor_log2 (qty_n_refs[q1]) * qty_n_refs[q1])
- / ((qty_death[q1] - qty_birth[q1]) * qty_size[q1]))
+ = (((double) (floor_log2 (qty_n_refs[q1]) * qty_n_refs[q1] * qty_size[q1])
+ / (qty_death[q1] - qty_birth[q1]))
* 10000);
register int pri2
- = (((double) (floor_log2 (qty_n_refs[q2]) * qty_n_refs[q2])
- / ((qty_death[q2] - qty_birth[q2]) * qty_size[q2]))
+ = (((double) (floor_log2 (qty_n_refs[q2]) * qty_n_refs[q2] * qty_size[q2])
+ / (qty_death[q2] - qty_birth[q2]))
* 10000);
return pri2 - pri1;
}
times a register can occur in one insn (surely less than 100).
Multiplying this by 10000 can't overflow. */
register int pri1
- = (((double) (floor_log2 (qty_n_refs[*q1]) * qty_n_refs[*q1])
- / ((qty_death[*q1] - qty_birth[*q1]) * qty_size[*q1]))
+ = (((double) (floor_log2 (qty_n_refs[*q1]) * qty_n_refs[*q1]
+ * qty_size[*q1])
+ / (qty_death[*q1] - qty_birth[*q1]))
* 10000);
register int pri2
- = (((double) (floor_log2 (qty_n_refs[*q2]) * qty_n_refs[*q2])
- / ((qty_death[*q2] - qty_birth[*q2]) * qty_size[*q2]))
+ = (((double) (floor_log2 (qty_n_refs[*q2]) * qty_n_refs[*q2]
+ * qty_size[*q2])
+ / (qty_death[*q2] - qty_birth[*q2]))
* 10000);
tem = pri2 - pri1;
return *q1 - *q2;
}
\f
+/* Compare two quantities' priority for getting real registers. This version
+ is called for quantities that have suggested hard registers. First priority
+ goes to quantities that have copy preferences, then to those that have
+ normal preferences. Within those groups, quantities with the lower
+ number of preferences have the highest priority. Of those, we use the same
+ algorithm as above. */
+
+static int
+qty_sugg_compare (q1, q2)
+ int q1, q2;
+{
+ register int sugg1 = (qty_phys_num_copy_sugg[q1]
+ ? qty_phys_num_copy_sugg[q1]
+ : qty_phys_num_sugg[q1] * FIRST_PSEUDO_REGISTER);
+ register int sugg2 = (qty_phys_num_copy_sugg[q2]
+ ? qty_phys_num_copy_sugg[q2]
+ : qty_phys_num_sugg[q2] * FIRST_PSEUDO_REGISTER);
+ /* Note that the quotient will never be bigger than
+ the value of floor_log2 times the maximum number of
+ times a register can occur in one insn (surely less than 100).
+ Multiplying this by 10000 can't overflow. */
+ register int pri1
+ = (((double) (floor_log2 (qty_n_refs[q1]) * qty_n_refs[q1] * qty_size[q1])
+ / (qty_death[q1] - qty_birth[q1]))
+ * 10000);
+ register int pri2
+ = (((double) (floor_log2 (qty_n_refs[q2]) * qty_n_refs[q2] * qty_size[q2])
+ / (qty_death[q2] - qty_birth[q2]))
+ * 10000);
+
+ if (sugg1 != sugg2)
+ return sugg1 - sugg2;
+
+ return pri2 - pri1;
+}
+
+static int
+qty_sugg_compare_1 (q1, q2)
+ int *q1, *q2;
+{
+ register int sugg1 = (qty_phys_num_copy_sugg[*q1]
+ ? qty_phys_num_copy_sugg[*q1]
+ : qty_phys_num_sugg[*q1] * FIRST_PSEUDO_REGISTER);
+ register int sugg2 = (qty_phys_num_copy_sugg[*q2]
+ ? qty_phys_num_copy_sugg[*q2]
+ : qty_phys_num_sugg[*q2] * FIRST_PSEUDO_REGISTER);
+
+ /* Note that the quotient will never be bigger than
+ the value of floor_log2 times the maximum number of
+ times a register can occur in one insn (surely less than 100).
+ Multiplying this by 10000 can't overflow. */
+ register int pri1
+ = (((double) (floor_log2 (qty_n_refs[*q1]) * qty_n_refs[*q1]
+ * qty_size[*q1])
+ / (qty_death[*q1] - qty_birth[*q1]))
+ * 10000);
+ register int pri2
+ = (((double) (floor_log2 (qty_n_refs[*q2]) * qty_n_refs[*q2]
+ * qty_size[*q2])
+ / (qty_death[*q2] - qty_birth[*q2]))
+ * 10000);
+
+ if (sugg1 != sugg2)
+ return sugg1 - sugg2;
+
+ if (pri1 != pri2)
+ return pri2 - pri1;
+
+ /* If qtys are equally good, sort by qty number,
+ so that the results of qsort leave nothing to chance. */
+ return *q1 - *q2;
+}
+\f
/* Attempt to combine the two registers (rtx's) USEDREG and SETREG.
Returns 1 if have done so, or 0 if cannot.
if (reg_qty[sreg] >= 0)
{
- if (may_save_copy)
+ if (may_save_copy
+ && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg))
{
SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[sreg]], ureg);
- qty_phys_has_copy_sugg[reg_qty[sreg]] = 1;
+ qty_phys_num_copy_sugg[reg_qty[sreg]]++;
}
- else
+ else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg))
{
SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[sreg]], ureg);
- qty_phys_has_sugg[reg_qty[sreg]] = 1;
+ qty_phys_num_sugg[reg_qty[sreg]]++;
}
}
return 0;
if (sreg < FIRST_PSEUDO_REGISTER)
{
- if (may_save_copy)
+ if (may_save_copy
+ && ! TEST_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg))
{
SET_HARD_REG_BIT (qty_phys_copy_sugg[reg_qty[ureg]], sreg);
- qty_phys_has_copy_sugg[reg_qty[ureg]] = 1;
+ qty_phys_num_copy_sugg[reg_qty[ureg]]++;
}
- else
+ else if (! TEST_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg))
{
SET_HARD_REG_BIT (qty_phys_sugg[reg_qty[ureg]], sreg);
- qty_phys_has_sugg[reg_qty[ureg]] = 1;
+ qty_phys_num_sugg[reg_qty[ureg]]++;
}
return 0;
}
rclass = reg_alternate_class (reg);
if (reg_class_subset_p (rclass, qty_alternate_class[qty]))
qty_alternate_class[qty] = rclass;
+
+ if (reg_changes_size[reg])
+ qty_changes_size[qty] = 1;
}
\f
/* Handle something which alters the value of an rtx REG.
born_index, dead_index)
enum reg_class class;
enum machine_mode mode;
+ int qty;
int accept_call_clobbered;
int just_try_suggested;
- int qty;
int born_index, dead_index;
{
register int i, ins;
SET_HARD_REG_BIT (used, FRAME_POINTER_REGNUM);
#endif
+#ifdef CLASS_CANNOT_CHANGE_SIZE
+ if (qty_changes_size[qty])
+ IOR_HARD_REG_SET (used,
+ reg_class_contents[(int) CLASS_CANNOT_CHANGE_SIZE]);
+#endif
+
/* Normally, the registers that can be used for the first register in
a multi-register quantity are the same as those that can be used for
subsequent registers. However, if just trying suggested registers,
if (just_try_suggested)
{
- if (qty_phys_has_copy_sugg[qty])
+ if (qty_phys_num_copy_sugg[qty] != 0)
IOR_COMPL_HARD_REG_SET (first_used, qty_phys_copy_sugg[qty]);
else
IOR_COMPL_HARD_REG_SET (first_used, qty_phys_sugg[qty]);
/* If it would be profitable to allocate a call-clobbered register
and save and restore it around calls, do that. */
- if (just_try_suggested && qty_phys_has_copy_sugg[qty]
- && qty_phys_has_sugg[qty])
+ if (just_try_suggested && qty_phys_num_copy_sugg[qty] != 0
+ && qty_phys_num_sugg[qty] != 0)
{
/* Don't try the copy-suggested regs again. */
- qty_phys_has_copy_sugg[qty] = 0;
+ qty_phys_num_copy_sugg[qty] = 0;
return find_free_reg (class, mode, qty, accept_call_clobbered, 1,
born_index, dead_index);
}
static void
post_mark_life (regno, mode, life, birth, death)
- register int regno, life, birth;
+ int regno;
enum machine_mode mode;
- int death;
+ int life, birth, death;
{
register int j = HARD_REGNO_NREGS (regno, mode);
#ifdef HARD_REG_SET
\f
#ifdef REGISTER_CONSTRAINTS
-/* Return 1 if the constraint string P indicates that the a the operand
- must be equal to operand 0 and that no register is acceptable. */
+/* Return the number of alternatives for which the constraint string P
+ indicates that the operand must be equal to operand 0 and that no register
+ is acceptable. */
static int
-requires_inout_p (p)
+requires_inout (p)
char *p;
{
char c;
int found_zero = 0;
+ int reg_allowed = 0;
+ int num_matching_alts = 0;
while (c = *p++)
switch (c)
{
- case '0':
- found_zero = 1;
- break;
-
case '=': case '+': case '?':
case '#': case '&': case '!':
- case '*': case '%': case ',':
+ case '*': case '%':
case '1': case '2': case '3': case '4':
case 'm': case '<': case '>': case 'V': case 'o':
case 'E': case 'F': case 'G': case 'H':
/* These don't say anything we care about. */
break;
+ case ',':
+ if (found_zero && ! reg_allowed)
+ num_matching_alts++;
+
+ found_zero = reg_allowed = 0;
+ break;
+
+ case '0':
+ found_zero = 1;
+ break;
+
case 'p':
case 'g': case 'r':
default:
- /* These mean a register is allowed. Fail if so. */
- return 0;
+ reg_allowed = 1;
+ break;
}
- return found_zero;
+ if (found_zero && ! reg_allowed)
+ num_matching_alts++;
+
+ return num_matching_alts;
}
#endif /* REGISTER_CONSTRAINTS */
\f
OSDN Git Service
