/* Allocate registers within a basic block, for GNU compiler.
- Copyright (C) 1987, 1988, 1991 Free Software Foundation, Inc.
+ Copyright (C) 1987, 88, 91, 93, 94, 95, 1996 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
But this is currently disabled since tying in global_alloc is not
yet implemented. */
+/* Pseudos allocated here cannot be reallocated by global.c if the hard
+ register is used as a spill register. So we don't allocate such pseudos
+ here if their preferred class is likely to be used by spills. */
+
#include <stdio.h>
#include "config.h"
#include "rtl.h"
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 short *qty_n_refs;
+static int *qty_n_refs;
/* Element Q is a reg class contained in (smaller than) the
preferred classes of all the pseudo regs that are tied in 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 short *qty_first_reg;
+static int *qty_first_reg;
/* If (REG N) has been assigned a quantity number, is a register number
of another register assigned the same quantity number, or -1 for the
end of the chain. qty_first_reg point to the head of this chain. */
-static short *reg_next_in_qty;
+static int *reg_next_in_qty;
/* reg_qty[N] (where N is a pseudo reg number) is the qty number of that reg
if it is >= 0,
static HARD_REG_SET *regs_live_at;
+int *scratch_block;
+rtx *scratch_list;
+int scratch_list_length;
+static int scratch_index;
+
/* Communicate local vars `insn_number' and `insn'
from `block_alloc' to `reg_is_set', `wipe_dead_reg', and `alloc_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 ();
+/* Used to communicate changes made by update_equiv_regs to
+ memref_referenced_p. reg_equiv_replacement is set for any REG_EQUIV note
+ found or created, so that we can keep track of what memory accesses might
+ be created later, e.g. by reload. */
+
+static rtx *reg_equiv_replacement;
+
+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
break;
}
- /* If CLASS has only one register, don't allocate the SCRATCH here since
- it will prevent that register from being used as a spill register.
- reload will do the allocation. */
-
- if (class == NO_REGS || reg_class_size[(int) class] == 1)
+ if (class == NO_REGS)
return;
#else /* REGISTER_CONSTRAINTS */
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. */
See the declarations of these variables, above,
for what they mean. */
+ /* There can be up to MAX_SCRATCH * N_BASIC_BLOCKS SCRATCHes to allocate.
+ Instead of allocating this much memory from now until the end of
+ reload, only allocate space for MAX_QTY SCRATCHes. If there are more
+ reload will allocate them. */
+
+ scratch_list_length = max_qty;
+ scratch_list = (rtx *) xmalloc (scratch_list_length * sizeof (rtx));
+ bzero ((char *) scratch_list, scratch_list_length * sizeof (rtx));
+ scratch_block = (int *) xmalloc (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 = (short *) alloca (max_qty * sizeof (short));
+ 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_n_refs = (short *) alloca (max_qty * sizeof (short));
+ 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));
- reg_next_in_qty = (short *) alloca (max_regno * sizeof (short));
+ reg_next_in_qty = (int *) alloca (max_regno * sizeof (int));
reg_renumber = (short *) oballoc (max_regno * sizeof (short));
for (i = 0; i < max_regno; i++)
/* Determine which pseudo-registers can be allocated by local-alloc.
In general, these are the registers used only in a single block and
which only die once. However, if a register's preferred class has only
- one entry, don't allocate this register here unless it is preferred
+ a few entries, don't allocate this register here unless it is preferred
or nothing since retry_global_alloc won't be able to move it to
GENERAL_REGS if a reload register of this class is needed.
{
if (reg_basic_block[i] >= 0 && reg_n_deaths[i] == 1
&& (reg_alternate_class (i) == NO_REGS
- || reg_class_size[(int) reg_preferred_class (i)] > 1))
+ || ! CLASS_LIKELY_SPILLED_P (reg_preferred_class (i))))
reg_qty[i] = -2;
else
reg_qty[i] = -1;
{
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;
switch (code)
{
- case REG:
case CONST_INT:
case CONST:
case LABEL_REF:
case LO_SUM:
return 0;
+ case REG:
+ return (reg_equiv_replacement[REGNO (x)]
+ && memref_referenced_p (memref,
+ reg_equiv_replacement[REGNO (x)]));
+
case MEM:
if (true_dependence (memref, x))
return 1;
&& reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0))))
break;
- if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0)
+ /* See if all of SRC dies in P. This test is slightly more
+ conservative than it needs to be. */
+ if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0
+ && GET_MODE (XEXP (note, 0)) == GET_MODE (src))
{
int failed = 0;
int length = 0;
+ int d_length = 0;
int n_calls = 0;
+ int d_n_calls = 0;
/* We can do the optimization. Scan forward from INSN again,
replacing regs as we go. Set FAILED if a replacement can't
q != next_real_insn (p);
q = next_real_insn (q))
{
- if (reg_mentioned_p (src, PATTERN (q)))
+ if (reg_overlap_mentioned_p (src, PATTERN (q)))
{
- if (validate_replace_rtx (src, dest, q))
+ /* If SRC is a hard register, we might miss some
+ overlapping registers with validate_replace_rtx,
+ so we would have to undo it. We can't if DEST is
+ present in the insn, so fail in that combination
+ of cases. */
+ if (sregno < FIRST_PSEUDO_REGISTER
+ && reg_mentioned_p (dest, PATTERN (q)))
+ failed = 1;
+
+ /* Replace all uses and make sure that the register
+ isn't still present. */
+ else if (validate_replace_rtx (src, dest, q)
+ && (sregno >= FIRST_PSEUDO_REGISTER
+ || ! reg_overlap_mentioned_p (src,
+ PATTERN (q))))
{
/* We assume that a register is used exactly once per
insn in the updates below. If this is not correct,
reg_n_refs[dregno] += loop_depth;
}
else
- failed = 1;
+ {
+ validate_replace_rtx (dest, src, q);
+ failed = 1;
+ }
}
/* Count the insns and CALL_INSNs passed. If we passed the
death note of DEST, show increased live length. */
length++;
if (dest_death)
- reg_live_length[dregno]++;
+ 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)
- reg_n_calls_crossed[dregno]++;
+ d_n_calls++;
}
/* If DEST dies here, remove the death note and save it for
- later. */
+ later. Make sure ALL of DEST dies here; again, this is
+ overly conservative. */
if (dest_death == 0
- && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0)
+ && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0
+ && GET_MODE (XEXP (dest_death, 0)) == GET_MODE (dest))
remove_note (q, dest_death);
}
{
if (sregno >= FIRST_PSEUDO_REGISTER)
{
- reg_live_length[sregno] -= length;
+ if (reg_live_length[sregno] >= 0)
+ {
+ reg_live_length[sregno] -= length;
+ /* reg_live_length is only an approximation after
+ combine if sched is not run, so make sure that we
+ still have a reasonable value. */
+ if (reg_live_length[sregno] < 2)
+ reg_live_length[sregno] = 2;
+ }
+
reg_n_calls_crossed[sregno] -= n_calls;
}
+ if (dregno >= FIRST_PSEUDO_REGISTER)
+ {
+ if (reg_live_length[dregno] >= 0)
+ reg_live_length[dregno] += d_length;
+
+ reg_n_calls_crossed[dregno] += d_n_calls;
+ }
+
/* Move death note of SRC from P to INSN. */
remove_note (p, note);
XEXP (note, 1) = REG_NOTES (insn);
return;
}
+
+ /* If SRC is a hard register which is set or killed in some other
+ way, we can't do this optimization. */
+ else if (sregno < FIRST_PSEUDO_REGISTER
+ && dead_or_set_p (p, src))
+ break;
}
}
\f
In that case, we can replace all uses of DEST, starting with INSN and
ending with the set of SRC to DEST, with SRC. We do not do this
optimization if a CALL_INSN is crossed unless SRC already crosses a
- call.
+ call or if DEST dies before the copy back to SRC.
It is assumed that DEST and SRC are pseudos; it is too complicated to do
this for hard registers since the substitutions we may make might fail. */
/* We assume that a register is used exactly once per
insn in the updates below. If this is not correct,
no great harm is done. */
- reg_n_refs[sregno] -= loop_depth;
- reg_n_refs[dregno] += loop_depth;
+ reg_n_refs[dregno] -= loop_depth;
+ reg_n_refs[sregno] += loop_depth;
}
}
if (reg_set_p (src, p)
+ || find_reg_note (p, REG_DEAD, dest)
|| (GET_CODE (p) == CALL_INSN && reg_n_calls_crossed[sregno] == 0))
break;
}
update_equiv_regs ()
{
rtx *reg_equiv_init_insn = (rtx *) alloca (max_regno * sizeof (rtx *));
- rtx *reg_equiv_replacement = (rtx *) alloca (max_regno * sizeof (rtx *));
+ /* Set when an attempt should be made to replace a register with the
+ associated reg_equiv_replacement entry at the end of this function. */
+ char *reg_equiv_replace
+ = (char *) alloca (max_regno * sizeof *reg_equiv_replace);
rtx insn;
- bzero (reg_equiv_init_insn, max_regno * sizeof (rtx *));
- bzero (reg_equiv_replacement, max_regno * sizeof (rtx *));
+ reg_equiv_replacement = (rtx *) alloca (max_regno * sizeof (rtx *));
+
+ bzero ((char *) reg_equiv_init_insn, max_regno * sizeof (rtx *));
+ bzero ((char *) reg_equiv_replacement, max_regno * sizeof (rtx *));
+ bzero ((char *) reg_equiv_replace, max_regno * sizeof *reg_equiv_replace);
init_alias_analysis ();
{
rtx note;
rtx set = single_set (insn);
- rtx dest;
+ rtx dest, src;
int regno;
if (GET_CODE (insn) == NOTE)
continue;
dest = SET_DEST (set);
+ src = SET_SRC (set);
/* If this sets a MEM to the contents of a REG that is only used
in a single basic block, see if the register is always equivalent
optimize_reg_copy_2 (insn, dest, SET_SRC (set));
/* Otherwise, we only handle the case of a pseudo register being set
- once. */
+ once and only if neither the source nor the destination are
+ in a register class that's likely to be spilled. */
if (GET_CODE (dest) != REG
|| (regno = REGNO (dest)) < FIRST_PSEUDO_REGISTER
- || reg_n_sets[regno] != 1)
+ || reg_n_sets[regno] != 1
+ || CLASS_LIKELY_SPILLED_P (reg_preferred_class (REGNO (dest)))
+ || (GET_CODE (src) == REG
+ && REGNO (src) >= FIRST_PSEUDO_REGISTER
+ && CLASS_LIKELY_SPILLED_P (reg_preferred_class (REGNO (src)))))
continue;
note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
REG_NOTES (insn) = note = gen_rtx (EXPR_LIST, REG_EQUIV, SET_SRC (set),
REG_NOTES (insn));
- /* Don't mess with things live during setjmp. */
- if (note && reg_live_length[regno] >= 0)
+ if (note)
{
int regno = REGNO (dest);
- /* Note that the statement below does not affect the priority
- in local-alloc! */
- reg_live_length[regno] *= 2;
+ reg_equiv_replacement[regno] = XEXP (note, 0);
+
+ /* Don't mess with things live during setjmp. */
+ if (reg_live_length[regno] >= 0)
+ {
+ /* Note that the statement below does not affect the priority
+ in local-alloc! */
+ reg_live_length[regno] *= 2;
+
- /* If the register is referenced exactly twice, meaning it is set
- once and used once, indicate that the reference may be replaced
- by the equivalence we computed above. If the register is only
- used in one basic block, this can't succeed or combine would
- have done it.
+ /* If the register is referenced exactly twice, meaning it is
+ set once and used once, indicate that the reference may be
+ replaced by the equivalence we computed above. If the
+ register is only used in one basic block, this can't succeed
+ or combine would have done it.
- It would be nice to use "loop_depth * 2" in the compare
- below. Unfortunately, LOOP_DEPTH need not be constant within
- a basic block so this would be too complicated.
+ It would be nice to use "loop_depth * 2" in the compare
+ below. Unfortunately, LOOP_DEPTH need not be constant within
+ a basic block so this would be too complicated.
- This case normally occurs when a parameter is read from memory
- and then used exactly once, not in a loop. */
+ This case normally occurs when a parameter is read from
+ memory and then used exactly once, not in a loop. */
- if (reg_n_refs[regno] == 2
- && reg_basic_block[regno] < 0
- && rtx_equal_p (XEXP (note, 0), SET_SRC (set)))
- reg_equiv_replacement[regno] = SET_SRC (set);
+ if (reg_n_refs[regno] == 2
+ && reg_basic_block[regno] < 0
+ && rtx_equal_p (XEXP (note, 0), SET_SRC (set)))
+ reg_equiv_replace[regno] = 1;
+ }
}
}
{
int regno = REGNO (XEXP (link, 0));
- if (reg_equiv_replacement[regno]
+ if (reg_equiv_replace[regno]
&& validate_replace_rtx (regno_reg_rtx[regno],
reg_equiv_replacement[regno], insn))
{
int insn_number = 0;
int insn_count = 0;
int max_uid = get_max_uid ();
- short *qty_order;
+ int *qty_order;
int no_conflict_combined_regno = -1;
+ /* Counter to prevent allocating more SCRATCHes than can be stored
+ in SCRATCH_LIST. */
+ int scratches_allocated = scratch_index;
/* Count the instructions in the basic block. */
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. */
Suitable insns are those with at least two operands and where
operand 0 is an output that is a register that is not
earlyclobber.
- For a commutative operation, try (set reg0 (arithop ... reg1)).
+
+ We can tie operand 0 with some operand that dies in this insn.
+ First look for operands that are required to be in the same
+ register as operand 0. If we find such, only try tying that
+ operand or one that can be put into that operand if the
+ operation is commutative. If we don't find an operand
+ that is required to be in the same register as operand 0,
+ we can tie with any operand.
+
Subregs in place of regs are also ok.
If tying is done, WIN is set nonzero. */
#endif
)
{
- r0 = recog_operand[0];
- r1 = recog_operand[1];
-
- /* If the first operand is an address, find a register in it.
- There may be more than one register, but we only try one of
- them. */
- if (
#ifdef REGISTER_CONSTRAINTS
- insn_operand_constraint[insn_code_number][1][0] == 'p'
-#else
- insn_operand_address_p[insn_code_number][1]
+ /* 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++)
+ {
+ 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
- )
- while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT)
- r1 = XEXP (r1, 0);
- if (GET_CODE (r0) == REG || GET_CODE (r0) == SUBREG)
+ r0 = recog_operand[0];
+ for (i = 1; i < insn_n_operands[insn_code_number]; i++)
{
- /* We have two priorities for hard register preferences.
- If we have a move insn or an insn whose first input can
- only be in the same register as the output, give
- priority to an equivalence found from that insn. */
#ifdef REGISTER_CONSTRAINTS
- int may_save_copy
- = ((SET_DEST (body) == r0 && SET_SRC (body) == r1)
- || (r1 == recog_operand[1]
- && (requires_inout_p (insn_operand_constraint[insn_code_number][1]))));
-#else
- int may_save_copy = 0;
+ /* Skip this operand if we found an operand that
+ must match operand 0 and this operand isn't it
+ and can't be made to be it by commutativity. */
+
+ if (must_match_0 >= 0 && i != must_match_0
+ && ! (i == must_match_0 + 1
+ && insn_operand_constraint[insn_code_number][i-1][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
- if (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)
- win = combine_regs (r1, r0, may_save_copy,
- insn_number, insn, 0);
+ r1 = recog_operand[i];
- if (win == 0
- && insn_n_operands[insn_code_number] > 2
+ /* If the operand is an address, find a register in it.
+ There may be more than one register, but we only try one
+ of them. */
+ if (
#ifdef REGISTER_CONSTRAINTS
- && insn_operand_constraint[insn_code_number][1][0] == '%'
+ insn_operand_constraint[insn_code_number][i][0] == 'p'
#else
- && GET_CODE (PATTERN (insn)) == SET
- && (GET_RTX_CLASS (GET_CODE (SET_SRC (PATTERN (insn))))
- == 'c')
- && rtx_equal_p (recog_operand[2],
- XEXP (SET_SRC (PATTERN (insn)), 0))
+ insn_operand_address_p[insn_code_number][i]
#endif
- && (r1 = recog_operand[2],
- GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG))
- win = combine_regs (r1, r0, may_save_copy,
- insn_number, insn, 0);
+ )
+ while (GET_CODE (r1) == PLUS || GET_CODE (r1) == MULT)
+ r1 = XEXP (r1, 0);
+
+ if (GET_CODE (r0) == REG || GET_CODE (r0) == SUBREG)
+ {
+ /* We have two priorities for hard register preferences.
+ If we have a move insn or an insn whose first input
+ can only be in the same register as the output, give
+ priority to an equivalence found from that insn. */
+ int may_save_copy
+ = ((SET_DEST (body) == r0 && SET_SRC (body) == r1)
+#ifdef REGISTER_CONSTRAINTS
+ || (r1 == recog_operand[i] && must_match_0 >= 0)
+#endif
+ );
+
+ if (GET_CODE (r1) == REG || GET_CODE (r1) == SUBREG)
+ win = combine_regs (r1, r0, may_save_copy,
+ insn_number, insn, 0);
+ }
+ if (win)
+ break;
}
}
&& (r0 = XEXP (PATTERN (insn), 0),
GET_CODE (r0) == REG)
&& (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0
+ && XEXP (link, 0) != 0
&& GET_CODE (XEXP (link, 0)) == INSN
&& (set = single_set (XEXP (link, 0))) != 0
&& SET_DEST (set) == r0 && SET_SRC (set) == r0
&& GET_CODE (XEXP (link, 0)) == REG)
wipe_dead_reg (XEXP (link, 0), 1);
-#ifndef SMALL_REGISTER_CLASSES
- /* Allocate quantities for any SCRATCH operands of this insn. We
- don't do this for machines with small register classes because
- those machines can use registers explicitly mentioned in the
- RTL as spill registers and our usage of hard registers
- explicitly for SCRATCH operands will conflict. On those machines,
- reload will allocate the SCRATCH. */
+ /* Allocate quantities for any SCRATCH operands of this insn. */
if (insn_code_number >= 0)
for (i = 0; i < insn_n_operands[insn_code_number]; i++)
- if (GET_CODE (recog_operand[i]) == SCRATCH)
+ if (GET_CODE (recog_operand[i]) == SCRATCH
+ && scratches_allocated++ < scratch_list_length)
alloc_qty_for_scratch (recog_operand[i], i, insn,
insn_code_number, insn_number);
-#endif
/* If this is an insn that has a REG_RETVAL note pointing at a
CLOBBER insn, we have reached the end of a REG_NO_CONFLICT
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 = (short *) alloca (next_qty * sizeof (short));
+ qty_order = (int *) alloca (next_qty * sizeof (int));
for (i = 0; i < next_qty; i++)
qty_order[i] = 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 ... */
+ /* ... 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 ... */
+ /* ... Fall through ... */
case 1:
case 0:
break;
default:
- qsort (qty_order, next_qty, sizeof (short), 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,
reg_renumber[i] = qty_phys_reg[q] + reg_offset[i];
if (qty_scratch_rtx[q])
{
+ if (GET_CODE (qty_scratch_rtx[q]) == REG)
+ abort ();
PUT_CODE (qty_scratch_rtx[q], REG);
REGNO (qty_scratch_rtx[q]) = qty_phys_reg[q];
- for (i = HARD_REGNO_NREGS (qty_phys_reg[q],
- GET_MODE (qty_scratch_rtx[q])) - 1;
- i >= 0; i--)
- regs_ever_live[qty_phys_reg[q] + i] = 1;
+ scratch_block[scratch_index] = b;
+ scratch_list[scratch_index++] = qty_scratch_rtx[q];
/* Must clear the USED field, because it will have been set by
copy_rtx_if_shared, but the leaf_register code expects that
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;
}
static int
qty_compare_1 (q1, q2)
- short *q1, *q2;
+ int *q1, *q2;
{
register int tem;
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.
|| (offset > 0 && usize + offset > ssize)
|| (offset < 0 && usize + offset < ssize)
/* Do not combine with a smaller already-assigned object
- if that smaller object is already combined with something bigger. */
+ if that smaller object is already combined with something bigger. */
|| (ssize > usize && ureg >= FIRST_PSEUDO_REGISTER
&& usize < qty_size[reg_qty[ureg]])
/* Can't combine if SREG is not a register we can allocate. */
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.
}
}
+ /* If this register is used in an auto-increment address, then extend its
+ life to after this insn, so that it won't get allocated together with
+ the result of this insn. */
+ if (! output_p && find_regno_note (this_insn, REG_INC, regno))
+ output_p = 1;
+
if (regno < FIRST_PSEUDO_REGISTER)
{
mark_life (regno, GET_MODE (reg), 0);
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;
else
COPY_HARD_REG_SET (used, call_used_reg_set);
+ if (accept_call_clobbered)
+ IOR_HARD_REG_SET (used, losing_caller_save_reg_set);
+
for (ins = born_index; ins < dead_index; ins++)
IOR_HARD_REG_SET (used, regs_live_at[ins]);
#ifdef ELIMINABLE_REGS
for (i = 0; i < sizeof eliminables / sizeof eliminables[0]; i++)
SET_HARD_REG_BIT (used, eliminables[i].from);
+#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
+ /* If FRAME_POINTER_REGNUM is not a real register, then protect the one
+ that it might be eliminated into. */
+ SET_HARD_REG_BIT (used, HARD_FRAME_POINTER_REGNUM);
+#endif
#else
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);
}
+ /* We need not check to see if the current function has nonlocal
+ labels because we don't put any pseudos that are live over calls in
+ registers in that case. */
+
if (! accept_call_clobbered
&& flag_caller_saves
&& ! just_try_suggested
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