/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992 Free Software Foundation, Inc.
+ Copyright (C) 1992, 93, 94, 95, 97, 1998 Free Software Foundation, Inc.
Contributed by James E. Wilson, Cygnus Support/UC Berkeley.
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. */
/* Try to unroll a loop, and split induction variables.
enum unroll_types { UNROLL_COMPLETELY, UNROLL_MODULO, UNROLL_NAIVE };
#include "config.h"
+#include "system.h"
#include "rtl.h"
#include "insn-config.h"
#include "integrate.h"
#include "regs.h"
+#include "recog.h"
#include "flags.h"
#include "expr.h"
-#include <stdio.h>
#include "loop.h"
+#include "toplev.h"
/* This controls which loops are unrolled, and by how much we unroll
them. */
/* Values describing the current loop's iteration variable. These are set up
by loop_iterations, and used by precondition_loop_p. */
-static rtx loop_iteration_var;
-static rtx loop_initial_value;
-static rtx loop_increment;
-static rtx loop_final_value;
+rtx loop_iteration_var;
+rtx loop_initial_value;
+rtx loop_increment;
+rtx loop_final_value;
+enum rtx_code loop_comparison_code;
/* Forward declarations. */
-static void init_reg_map ();
-static int precondition_loop_p ();
-static void copy_loop_body ();
-static void iteration_info ();
-static rtx approx_final_value ();
-static int find_splittable_regs ();
-static int find_splittable_givs ();
-static rtx fold_rtx_mult_add ();
+static void init_reg_map PROTO((struct inline_remap *, int));
+static int precondition_loop_p PROTO((rtx *, rtx *, rtx *, rtx));
+static rtx calculate_giv_inc PROTO((rtx, rtx, int));
+static rtx initial_reg_note_copy PROTO((rtx, struct inline_remap *));
+static void final_reg_note_copy PROTO((rtx, struct inline_remap *));
+static void copy_loop_body PROTO((rtx, rtx, struct inline_remap *, rtx, int,
+ enum unroll_types, rtx, rtx, rtx, rtx));
+void iteration_info PROTO((rtx, rtx *, rtx *, rtx, rtx));
+static rtx approx_final_value PROTO((enum rtx_code, rtx, int *, int *));
+static int find_splittable_regs PROTO((enum unroll_types, rtx, rtx, rtx, int));
+static int find_splittable_givs PROTO((struct iv_class *,enum unroll_types,
+ rtx, rtx, rtx, int));
+static int reg_dead_after_loop PROTO((rtx, rtx, rtx));
+static rtx fold_rtx_mult_add PROTO((rtx, rtx, rtx, enum machine_mode));
+static int verify_addresses PROTO((struct induction *, rtx, int));
+static rtx remap_split_bivs PROTO((rtx));
/* Try to unroll one loop and split induction variables in the loop.
int i, j, temp;
int unroll_number = 1;
rtx copy_start, copy_end;
- rtx insn, copy, sequence, pattern, tem;
+ rtx insn, sequence, pattern, tem;
int max_labelno, max_insnno;
rtx insert_before;
struct inline_remap *map;
char *local_label;
+ char *local_regno;
int maxregnum;
int new_maxregnum;
rtx exit_label = 0;
rtx start_label;
struct iv_class *bl;
- struct induction *v;
int splitting_not_safe = 0;
enum unroll_types unroll_type;
int loop_preconditioned = 0;
of block_beg and block_end notes, because that would unbalance the block
structure of the function. This can happen as a result of the
"if (foo) bar; else break;" optimization in jump.c. */
+ /* ??? Gcc has a general policy that -g is never supposed to change the code
+ that the compiler emits, so we must disable this optimization always,
+ even if debug info is not being output. This is rare, so this should
+ not be a significant performance problem. */
- if (write_symbols != NO_DEBUG)
+ if (1 /* write_symbols != NO_DEBUG */)
{
int block_begins = 0;
int block_ends = 0;
loop_n_iterations = 0;
if (loop_dump_stream && loop_n_iterations > 0)
- fprintf (loop_dump_stream,
- "Loop unrolling: %d iterations.\n", loop_n_iterations);
+ {
+ fputs ("Loop unrolling: ", loop_dump_stream);
+ fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, loop_n_iterations);
+ fputs (" iterations.\n", loop_dump_stream);
+ }
/* Find and save a pointer to the last nonnote insn in the loop. */
if (unroll_type == UNROLL_COMPLETELY || unroll_type == UNROLL_MODULO)
{
- /* Loops of these types should never start with a jump down to
- the exit condition test. For now, check for this case just to
- be sure. UNROLL_NAIVE loops can be of this form, this case is
- handled below. */
+ /* Loops of these types can start with jump down to the exit condition
+ in rare circumstances.
+
+ Consider a pair of nested loops where the inner loop is part
+ of the exit code for the outer loop.
+
+ In this case jump.c will not duplicate the exit test for the outer
+ loop, so it will start with a jump to the exit code.
+
+ Then consider if the inner loop turns out to iterate once and
+ only once. We will end up deleting the jumps associated with
+ the inner loop. However, the loop notes are not removed from
+ the instruction stream.
+
+ And finally assume that we can compute the number of iterations
+ for the outer loop.
+
+ In this case unroll may want to unroll the outer loop even though
+ it starts with a jump to the outer loop's exit code.
+
+ We could try to optimize this case, but it hardly seems worth it.
+ Just return without unrolling the loop in such cases. */
+
insn = loop_start;
while (GET_CODE (insn) != CODE_LABEL && GET_CODE (insn) != JUMP_INSN)
insn = NEXT_INSN (insn);
if (GET_CODE (insn) == JUMP_INSN)
- abort ();
+ return;
}
if (unroll_type == UNROLL_COMPLETELY)
"Unrolling failure: unknown insns between BEG note and loop label.\n");
return;
}
+ if (LABEL_NAME (start_label))
+ {
+ /* The jump optimization pass must have combined the original start label
+ with a named label for a goto. We can't unroll this case because
+ jumps which go to the named label must be handled differently than
+ jumps to the loop start, and it is impossible to differentiate them
+ in this case. */
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Unrolling failure: loop start label is gone\n");
+ return;
+ }
if (unroll_type == UNROLL_NAIVE
&& GET_CODE (last_loop_insn) == BARRIER
copy_end = last_loop_insn;
}
+ if (unroll_type == UNROLL_NAIVE
+ && GET_CODE (last_loop_insn) == JUMP_INSN
+ && start_label != JUMP_LABEL (last_loop_insn))
+ {
+ /* ??? The loop ends with a conditional branch that does not branch back
+ to the loop start label. In this case, we must emit an unconditional
+ branch to the loop exit after emitting the final branch.
+ copy_loop_body does not have support for this currently, so we
+ give up. It doesn't seem worthwhile to unroll anyways since
+ unrolling would increase the number of branch instructions
+ executed. */
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Unrolling failure: final conditional branch not to loop start\n");
+ return;
+ }
+
/* Allocate a translation table for the labels and insn numbers.
They will be filled in as we copy the insns in the loop. */
map = (struct inline_remap *) alloca (sizeof (struct inline_remap));
+ map->integrating = 0;
+
/* Allocate the label map. */
if (max_labelno > 0)
for (insn = copy_start; insn != loop_end; insn = NEXT_INSN (insn))
{
+ rtx note;
+
if (GET_CODE (insn) == CODE_LABEL)
local_label[CODE_LABEL_NUMBER (insn)] = 1;
else if (GET_CODE (insn) == JUMP_INSN)
{
if (JUMP_LABEL (insn))
- map->label_map[CODE_LABEL_NUMBER (JUMP_LABEL (insn))]
- = JUMP_LABEL (insn);
+ set_label_in_map (map,
+ CODE_LABEL_NUMBER (JUMP_LABEL (insn)),
+ JUMP_LABEL (insn));
else if (GET_CODE (PATTERN (insn)) == ADDR_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
{
for (i = 0; i < len; i++)
{
label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
- map->label_map[CODE_LABEL_NUMBER (label)] = label;
+ set_label_in_map (map,
+ CODE_LABEL_NUMBER (label),
+ label);
}
}
}
+ else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)))
+ set_label_in_map (map, CODE_LABEL_NUMBER (XEXP (note, 0)),
+ XEXP (note, 0));
}
/* Allocate space for the insn map. */
to access the splittable_regs[] and addr_combined_regs[] arrays. */
splittable_regs = (rtx *) alloca (maxregnum * sizeof (rtx));
- bzero (splittable_regs, maxregnum * sizeof (rtx));
+ bzero ((char *) splittable_regs, maxregnum * sizeof (rtx));
splittable_regs_updates = (int *) alloca (maxregnum * sizeof (int));
- bzero (splittable_regs_updates, maxregnum * sizeof (int));
+ bzero ((char *) splittable_regs_updates, maxregnum * sizeof (int));
addr_combined_regs
= (struct induction **) alloca (maxregnum * sizeof (struct induction *));
- bzero (addr_combined_regs, maxregnum * sizeof (struct induction *));
+ bzero ((char *) addr_combined_regs, maxregnum * sizeof (struct induction *));
+ /* We must limit it to max_reg_before_loop, because only these pseudo
+ registers have valid regno_first_uid info. Any register created after
+ that is unlikely to be local to the loop anyways. */
+ local_regno = (char *) alloca (max_reg_before_loop);
+ bzero (local_regno, max_reg_before_loop);
+
+ /* Mark all local registers, i.e. the ones which are referenced only
+ inside the loop. */
+ if (INSN_UID (copy_end) < max_uid_for_loop)
+ {
+ int copy_start_luid = INSN_LUID (copy_start);
+ int copy_end_luid = INSN_LUID (copy_end);
+
+ /* If a register is used in the jump insn, we must not duplicate it
+ since it will also be used outside the loop. */
+ if (GET_CODE (copy_end) == JUMP_INSN)
+ copy_end_luid--;
+ /* If copy_start points to the NOTE that starts the loop, then we must
+ use the next luid, because invariant pseudo-regs moved out of the loop
+ have their lifetimes modified to start here, but they are not safe
+ to duplicate. */
+ if (copy_start == loop_start)
+ copy_start_luid++;
+
+ /* If a pseudo's lifetime is entirely contained within this loop, then we
+ can use a different pseudo in each unrolled copy of the loop. This
+ results in better code. */
+ for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; ++j)
+ if (REGNO_FIRST_UID (j) > 0 && REGNO_FIRST_UID (j) <= max_uid_for_loop
+ && uid_luid[REGNO_FIRST_UID (j)] >= copy_start_luid
+ && REGNO_LAST_UID (j) > 0 && REGNO_LAST_UID (j) <= max_uid_for_loop
+ && uid_luid[REGNO_LAST_UID (j)] <= copy_end_luid)
+ {
+ /* However, we must also check for loop-carried dependencies.
+ If the value the pseudo has at the end of iteration X is
+ used by iteration X+1, then we can not use a different pseudo
+ for each unrolled copy of the loop. */
+ /* A pseudo is safe if regno_first_uid is a set, and this
+ set dominates all instructions from regno_first_uid to
+ regno_last_uid. */
+ /* ??? This check is simplistic. We would get better code if
+ this check was more sophisticated. */
+ if (set_dominates_use (j, REGNO_FIRST_UID (j), REGNO_LAST_UID (j),
+ copy_start, copy_end))
+ local_regno[j] = 1;
+
+ if (loop_dump_stream)
+ {
+ if (local_regno[j])
+ fprintf (loop_dump_stream, "Marked reg %d as local\n", j);
+ else
+ fprintf (loop_dump_stream, "Did not mark reg %d as local\n",
+ j);
+ }
+ }
+ }
/* If this loop requires exit tests when unrolled, check to see if we
can precondition the loop so as to make the exit tests unnecessary.
rtx initial_value, final_value, increment;
if (precondition_loop_p (&initial_value, &final_value, &increment,
- loop_start, loop_end))
+ loop_start))
{
- register rtx diff, temp;
+ register rtx diff ;
enum machine_mode mode;
rtx *labels;
int abs_inc, neg_inc;
* sizeof (unsigned));
map->const_equiv_map_size = maxregnum;
global_const_equiv_map = map->const_equiv_map;
+ global_const_equiv_map_size = maxregnum;
init_reg_map (map, maxregnum);
for (i = 0; i < unroll_number; i++)
labels[i] = gen_label_rtx ();
+ /* Check for the case where the initial value is greater than or
+ equal to the final value. In that case, we want to execute
+ exactly one loop iteration. The code below will fail for this
+ case. This check does not apply if the loop has a NE
+ comparison at the end. */
+
+ if (loop_comparison_code != NE)
+ {
+ emit_cmp_insn (initial_value, final_value, neg_inc ? LE : GE,
+ NULL_RTX, mode, 0, 0);
+ if (neg_inc)
+ emit_jump_insn (gen_ble (labels[1]));
+ else
+ emit_jump_insn (gen_bge (labels[1]));
+ JUMP_LABEL (get_last_insn ()) = labels[1];
+ LABEL_NUSES (labels[1])++;
+ }
+
/* Assuming the unroll_number is 4, and the increment is 2, then
for a negative increment: for a positive increment:
diff = 0,1 precond 0 diff = 0,7 precond 0
for (i = 0; i < unroll_number - 1; i++)
{
int cmp_const;
+ enum rtx_code cmp_code;
/* For negative increments, must invert the constant compared
against, except when comparing against zero. */
if (i == 0)
- cmp_const = 0;
+ {
+ cmp_const = 0;
+ cmp_code = EQ;
+ }
else if (neg_inc)
- cmp_const = unroll_number - i;
+ {
+ cmp_const = unroll_number - i;
+ cmp_code = GE;
+ }
else
- cmp_const = i;
+ {
+ cmp_const = i;
+ cmp_code = LE;
+ }
emit_cmp_insn (diff, GEN_INT (abs_inc * cmp_const),
- EQ, NULL_RTX, mode, 0, 0);
+ cmp_code, NULL_RTX, mode, 0, 0);
if (i == 0)
emit_jump_insn (gen_beq (labels[i]));
if (abs_inc != 1)
{
int cmp_const;
+ enum rtx_code cmp_code;
if (neg_inc)
- cmp_const = abs_inc - 1;
+ {
+ cmp_const = abs_inc - 1;
+ cmp_code = LE;
+ }
else
- cmp_const = abs_inc * (unroll_number - 1) + 1;
+ {
+ cmp_const = abs_inc * (unroll_number - 1) + 1;
+ cmp_code = GE;
+ }
- emit_cmp_insn (diff, GEN_INT (cmp_const), EQ, NULL_RTX,
+ emit_cmp_insn (diff, GEN_INT (cmp_const), cmp_code, NULL_RTX,
mode, 0, 0);
if (neg_inc)
emit_label_after (labels[unroll_number - i],
PREV_INSN (loop_start));
- bzero (map->insn_map, max_insnno * sizeof (rtx));
- bzero (map->const_equiv_map, maxregnum * sizeof (rtx));
- bzero (map->const_age_map, maxregnum * sizeof (unsigned));
+ bzero ((char *) map->insn_map, max_insnno * sizeof (rtx));
+ bzero ((char *) map->const_equiv_map, maxregnum * sizeof (rtx));
+ bzero ((char *) map->const_age_map,
+ maxregnum * sizeof (unsigned));
map->const_age = 0;
for (j = 0; j < max_labelno; j++)
if (local_label[j])
- map->label_map[j] = gen_label_rtx ();
+ set_label_in_map (map, j, gen_label_rtx ());
+ for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
+ if (local_regno[j])
+ {
+ map->reg_map[j] = gen_reg_rtx (GET_MODE (regno_reg_rtx[j]));
+ record_base_value (REGNO (map->reg_map[j]),
+ regno_reg_rtx[j], 0);
+ }
/* The last copy needs the compare/branch insns at the end,
so reset copy_end here if the loop ends with a conditional
branch. */
/* At this point, we are guaranteed to unroll the loop. */
+ /* Keep track of the unroll factor for each loop. */
+ if (unroll_type == UNROLL_COMPLETELY)
+ loop_unroll_factor [uid_loop_num [INSN_UID (loop_start)]] = -1;
+ else
+ loop_unroll_factor [uid_loop_num [INSN_UID (loop_start)]] = unroll_number;
+
+
/* For each biv and giv, determine whether it can be safely split into
a different variable for each unrolled copy of the loop body.
We precalculate and save this info here, since computing it is
map->const_equiv_map = (rtx *) alloca (new_maxregnum * sizeof (rtx));
map->const_age_map = (unsigned *) alloca (new_maxregnum * sizeof (unsigned));
+ map->const_equiv_map_size = new_maxregnum;
global_const_equiv_map = map->const_equiv_map;
+ global_const_equiv_map_size = new_maxregnum;
/* Search the list of bivs and givs to find ones which need to be remapped
when split, and set their reg_map entry appropriately. */
#endif
}
+ /* Use our current register alignment and pointer flags. */
+ map->regno_pointer_flag = regno_pointer_flag;
+ map->regno_pointer_align = regno_pointer_align;
+
/* If the loop is being partially unrolled, and the iteration variables
are being split, and are being renamed for the split, then must fix up
- the compare instruction at the end of the loop to refer to the new
+ the compare/jump instruction at the end of the loop to refer to the new
registers. This compare isn't copied, so the registers used in it
will never be replaced if it isn't done here. */
if (unroll_type == UNROLL_MODULO)
{
insn = NEXT_INSN (copy_end);
- if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == SET)
- {
-#if 0
- /* If non-reduced/final-value givs were split, then this would also
- have to remap those givs. */
-#endif
-
- tem = SET_SRC (PATTERN (insn));
- /* The set source is a register. */
- if (GET_CODE (tem) == REG)
- {
- if (REGNO (tem) < max_reg_before_loop
- && reg_iv_type[REGNO (tem)] == BASIC_INDUCT)
- SET_SRC (PATTERN (insn))
- = reg_biv_class[REGNO (tem)]->biv->src_reg;
- }
- else
- {
- /* The set source is a compare of some sort. */
- tem = XEXP (SET_SRC (PATTERN (insn)), 0);
- if (GET_CODE (tem) == REG
- && REGNO (tem) < max_reg_before_loop
- && reg_iv_type[REGNO (tem)] == BASIC_INDUCT)
- XEXP (SET_SRC (PATTERN (insn)), 0)
- = reg_biv_class[REGNO (tem)]->biv->src_reg;
-
- tem = XEXP (SET_SRC (PATTERN (insn)), 1);
- if (GET_CODE (tem) == REG
- && REGNO (tem) < max_reg_before_loop
- && reg_iv_type[REGNO (tem)] == BASIC_INDUCT)
- XEXP (SET_SRC (PATTERN (insn)), 1)
- = reg_biv_class[REGNO (tem)]->biv->src_reg;
- }
- }
+ if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
+ PATTERN (insn) = remap_split_bivs (PATTERN (insn));
}
/* For unroll_number - 1 times, make a copy of each instruction
for (i = 0; i < unroll_number; i++)
{
- bzero (map->insn_map, max_insnno * sizeof (rtx));
- bzero (map->const_equiv_map, new_maxregnum * sizeof (rtx));
- bzero (map->const_age_map, new_maxregnum * sizeof (unsigned));
+ bzero ((char *) map->insn_map, max_insnno * sizeof (rtx));
+ bzero ((char *) map->const_equiv_map, new_maxregnum * sizeof (rtx));
+ bzero ((char *) map->const_age_map, new_maxregnum * sizeof (unsigned));
map->const_age = 0;
for (j = 0; j < max_labelno; j++)
if (local_label[j])
- map->label_map[j] = gen_label_rtx ();
+ set_label_in_map (map, j, gen_label_rtx ());
+
+ for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
+ if (local_regno[j])
+ {
+ map->reg_map[j] = gen_reg_rtx (GET_MODE (regno_reg_rtx[j]));
+ record_base_value (REGNO (map->reg_map[j]),
+ regno_reg_rtx[j], 0);
+ }
/* If loop starts with a branch to the test, then fix it so that
it points to the test of the first unrolled copy of the loop. */
insn = PREV_INSN (copy_start);
pattern = PATTERN (insn);
- tem = map->label_map[CODE_LABEL_NUMBER
- (XEXP (SET_SRC (pattern), 0))];
- SET_SRC (pattern) = gen_rtx (LABEL_REF, VOIDmode, tem);
+ tem = get_label_from_map (map,
+ CODE_LABEL_NUMBER
+ (XEXP (SET_SRC (pattern), 0)));
+ SET_SRC (pattern) = gen_rtx_LABEL_REF (VOIDmode, tem);
/* Set the jump label so that it can be used by later loop unrolling
passes. */
not taken. */
if (exit_label)
emit_label_after (exit_label, loop_end);
-
- /* If debugging, we must replicate the tree nodes corresponding to the blocks
- inside the loop, so that the original one to one mapping will remain. */
-
- if (write_symbols != NO_DEBUG)
- {
- int copies = unroll_number;
-
- if (loop_preconditioned)
- copies += unroll_number - 1;
-
- unroll_block_trees (uid_loop_num[INSN_UID (loop_start)], copies);
- }
}
\f
/* Return true if the loop can be safely, and profitably, preconditioned
whether divide is cheap. */
static int
-precondition_loop_p (initial_value, final_value, increment, loop_start,
- loop_end)
+precondition_loop_p (initial_value, final_value, increment, loop_start)
rtx *initial_value, *final_value, *increment;
- rtx loop_start, loop_end;
+ rtx loop_start;
{
- int unsigned_compare, compare_dir;
if (loop_n_iterations > 0)
{
*final_value = GEN_INT (loop_n_iterations);
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Preconditioning: Success, number of iterations known, %d.\n",
- loop_n_iterations);
+ {
+ fputs ("Preconditioning: Success, number of iterations known, ",
+ loop_dump_stream);
+ fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
+ loop_n_iterations);
+ fputs (".\n", loop_dump_stream);
+ }
return 1;
}
/* Fail if loop_iteration_var is not live before loop_start, since we need
to test its value in the preconditioning code. */
- if (uid_luid[regno_first_uid[REGNO (loop_iteration_var)]]
+ if (uid_luid[REGNO_FIRST_UID (REGNO (loop_iteration_var))]
> INSN_LUID (loop_start))
{
if (loop_dump_stream)
to the iv. This procedure reconstructs the pattern computing the iv;
verifying that all operands are of the proper form.
+ PATTERN must be the result of single_set.
The return value is the amount that the giv is incremented by. */
static rtx
int regno;
{
rtx increment;
+ rtx increment_total = 0;
+ int tries = 0;
+ retry:
/* Verify that we have an increment insn here. First check for a plus
as the set source. */
if (GET_CODE (SET_SRC (pattern)) != PLUS)
{
/* SR sometimes puts the constant in a register, especially if it is
too big to be an add immed operand. */
- increment = SET_SRC (PATTERN (PREV_INSN (src_insn)));
+ src_insn = PREV_INSN (src_insn);
+ increment = SET_SRC (PATTERN (src_insn));
/* SR may have used LO_SUM to compute the constant if it is too large
for a load immed operand. In this case, the constant is in operand
if (GET_CODE (increment) == LO_SUM)
increment = XEXP (increment, 1);
+ /* Some ports store large constants in memory and add a REG_EQUAL
+ note to the store insn. */
+ else if (GET_CODE (increment) == MEM)
+ {
+ rtx note = find_reg_note (src_insn, REG_EQUAL, 0);
+ if (note)
+ increment = XEXP (note, 0);
+ }
+
+ else if (GET_CODE (increment) == IOR
+ || GET_CODE (increment) == ASHIFT
+ || GET_CODE (increment) == PLUS)
+ {
+ /* The rs6000 port loads some constants with IOR.
+ The alpha port loads some constants with ASHIFT and PLUS. */
+ rtx second_part = XEXP (increment, 1);
+ enum rtx_code code = GET_CODE (increment);
+
+ src_insn = PREV_INSN (src_insn);
+ increment = SET_SRC (PATTERN (src_insn));
+ /* Don't need the last insn anymore. */
+ delete_insn (get_last_insn ());
+
+ if (GET_CODE (second_part) != CONST_INT
+ || GET_CODE (increment) != CONST_INT)
+ abort ();
+
+ if (code == IOR)
+ increment = GEN_INT (INTVAL (increment) | INTVAL (second_part));
+ else if (code == PLUS)
+ increment = GEN_INT (INTVAL (increment) + INTVAL (second_part));
+ else
+ increment = GEN_INT (INTVAL (increment) << INTVAL (second_part));
+ }
+
if (GET_CODE (increment) != CONST_INT)
abort ();
- /* The insn loading the constant into a register is not longer needed,
+ /* The insn loading the constant into a register is no longer needed,
so delete it. */
delete_insn (get_last_insn ());
}
- /* Check that the source register is the same as the dest register. */
+ if (increment_total)
+ increment_total = GEN_INT (INTVAL (increment_total) + INTVAL (increment));
+ else
+ increment_total = increment;
+
+ /* Check that the source register is the same as the register we expected
+ to see as the source. If not, something is seriously wrong. */
if (GET_CODE (XEXP (SET_SRC (pattern), 0)) != REG
|| REGNO (XEXP (SET_SRC (pattern), 0)) != regno)
+ {
+ /* Some machines (e.g. the romp), may emit two add instructions for
+ certain constants, so lets try looking for another add immediately
+ before this one if we have only seen one add insn so far. */
+
+ if (tries == 0)
+ {
+ tries++;
+
+ src_insn = PREV_INSN (src_insn);
+ pattern = PATTERN (src_insn);
+
+ delete_insn (get_last_insn ());
+
+ goto retry;
+ }
+
+ abort ();
+ }
+
+ return increment_total;
+}
+
+/* Copy REG_NOTES, except for insn references, because not all insn_map
+ entries are valid yet. We do need to copy registers now though, because
+ the reg_map entries can change during copying. */
+
+static rtx
+initial_reg_note_copy (notes, map)
+ rtx notes;
+ struct inline_remap *map;
+{
+ rtx copy;
+
+ if (notes == 0)
+ return 0;
+
+ copy = rtx_alloc (GET_CODE (notes));
+ PUT_MODE (copy, GET_MODE (notes));
+
+ if (GET_CODE (notes) == EXPR_LIST)
+ XEXP (copy, 0) = copy_rtx_and_substitute (XEXP (notes, 0), map);
+ else if (GET_CODE (notes) == INSN_LIST)
+ /* Don't substitute for these yet. */
+ XEXP (copy, 0) = XEXP (notes, 0);
+ else
abort ();
- return increment;
+ XEXP (copy, 1) = initial_reg_note_copy (XEXP (notes, 1), map);
+
+ return copy;
}
+/* Fixup insn references in copied REG_NOTES. */
+
+static void
+final_reg_note_copy (notes, map)
+ rtx notes;
+ struct inline_remap *map;
+{
+ rtx note;
+
+ for (note = notes; note; note = XEXP (note, 1))
+ if (GET_CODE (note) == INSN_LIST)
+ XEXP (note, 0) = map->insn_map[INSN_UID (XEXP (note, 0))];
+}
/* Copy each instruction in the loop, substituting from map as appropriate.
This is very similar to a loop in expand_inline_function. */
copy_notes_from)
rtx copy_start, copy_end;
struct inline_remap *map;
+ rtx exit_label;
int last_iteration;
enum unroll_types unroll_type;
rtx start_label, loop_end, insert_before, copy_notes_from;
{
rtx insn, pattern;
- rtx tem, copy;
+ rtx set, tem, copy;
int dest_reg_was_split, i;
+#ifdef HAVE_cc0
rtx cc0_insn = 0;
+#endif
rtx final_label = 0;
rtx giv_inc, giv_dest_reg, giv_src_reg;
if (! last_iteration)
{
final_label = gen_label_rtx ();
- map->label_map[CODE_LABEL_NUMBER (start_label)] = final_label;
+ set_label_in_map (map, CODE_LABEL_NUMBER (start_label),
+ final_label);
}
else
- map->label_map[CODE_LABEL_NUMBER (start_label)] = start_label;
+ set_label_in_map (map, CODE_LABEL_NUMBER (start_label), start_label);
start_sequence ();
Do this before splitting the giv, since that may map the
SET_DEST to a new register. */
- if (GET_CODE (pattern) == SET
- && GET_CODE (SET_DEST (pattern)) == REG
- && addr_combined_regs[REGNO (SET_DEST (pattern))])
+ if ((set = single_set (insn))
+ && GET_CODE (SET_DEST (set)) == REG
+ && addr_combined_regs[REGNO (SET_DEST (set))])
{
struct iv_class *bl;
struct induction *v, *tv;
- int regno = REGNO (SET_DEST (pattern));
+ int regno = REGNO (SET_DEST (set));
- v = addr_combined_regs[REGNO (SET_DEST (pattern))];
+ v = addr_combined_regs[REGNO (SET_DEST (set))];
bl = reg_biv_class[REGNO (v->src_reg)];
/* Although the giv_inc amount is not needed here, we must call
we might accidentally delete insns generated immediately
below by emit_unrolled_add. */
- giv_inc = calculate_giv_inc (pattern, insn, regno);
+ giv_inc = calculate_giv_inc (set, insn, regno);
/* Now find all address giv's that were combined with this
giv 'v'. */
for (tv = bl->giv; tv; tv = tv->next_iv)
if (tv->giv_type == DEST_ADDR && tv->same == v)
{
- int this_giv_inc = INTVAL (giv_inc);
+ int this_giv_inc;
+
+ /* If this DEST_ADDR giv was not split, then ignore it. */
+ if (*tv->location != tv->dest_reg)
+ continue;
/* Scale this_giv_inc if the multiplicative factors of
the two givs are different. */
+ this_giv_inc = INTVAL (giv_inc);
if (tv->mult_val != v->mult_val)
this_giv_inc = (this_giv_inc / INTVAL (v->mult_val)
* INTVAL (tv->mult_val));
else
dest_reg = XEXP (tv->dest_reg, 0);
- /* tv->dest_reg may actually be a (PLUS (REG) (CONST))
- here, so we must call plus_constant to add
- the const_adjust amount before calling
- emit_unrolled_add below. */
- value = plus_constant (tv->dest_reg, tv->const_adjust);
-
- /* The constant could be too large for an add
- immediate, so can't directly emit an insn here. */
- emit_unrolled_add (dest_reg, XEXP (value, 0),
- XEXP (value, 1));
+ /* Check for shared address givs, and avoid
+ incrementing the shared pseudo reg more than
+ once. */
+ if (! tv->same_insn && ! tv->shared)
+ {
+ /* tv->dest_reg may actually be a (PLUS (REG)
+ (CONST)) here, so we must call plus_constant
+ to add the const_adjust amount before calling
+ emit_unrolled_add below. */
+ value = plus_constant (tv->dest_reg,
+ tv->const_adjust);
+
+ /* The constant could be too large for an add
+ immediate, so can't directly emit an insn
+ here. */
+ emit_unrolled_add (dest_reg, XEXP (value, 0),
+ XEXP (value, 1));
+ }
/* Reset the giv to be just the register again, in case
it is used after the set we have just emitted.
dest_reg_was_split = 0;
- if (GET_CODE (pattern) == SET
- && GET_CODE (SET_DEST (pattern)) == REG
- && splittable_regs[REGNO (SET_DEST (pattern))])
+ if ((set = single_set (insn))
+ && GET_CODE (SET_DEST (set)) == REG
+ && splittable_regs[REGNO (SET_DEST (set))])
{
- int regno = REGNO (SET_DEST (pattern));
+ int regno = REGNO (SET_DEST (set));
dest_reg_was_split = 1;
already computed above. */
if (giv_inc == 0)
- giv_inc = calculate_giv_inc (pattern, insn, regno);
- giv_dest_reg = SET_DEST (pattern);
- giv_src_reg = SET_DEST (pattern);
+ giv_inc = calculate_giv_inc (set, insn, regno);
+ giv_dest_reg = SET_DEST (set);
+ giv_src_reg = SET_DEST (set);
if (unroll_type == UNROLL_COMPLETELY)
{
tem = gen_reg_rtx (GET_MODE (giv_src_reg));
giv_dest_reg = tem;
map->reg_map[regno] = tem;
+ record_base_value (REGNO (tem),
+ giv_inc == const0_rtx
+ ? giv_src_reg
+ : gen_rtx_PLUS (GET_MODE (giv_src_reg),
+ giv_src_reg, giv_inc),
+ 1);
}
else
map->reg_map[regno] = giv_src_reg;
pattern = copy_rtx_and_substitute (pattern, map);
copy = emit_insn (pattern);
}
- /* REG_NOTES will be copied later. */
+ REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
#ifdef HAVE_cc0
/* If this insn is setting CC0, it may need to look at
If the previous insn set CC0, substitute constants on it as
well. */
- if (sets_cc0_p (copy) != 0)
+ if (sets_cc0_p (PATTERN (copy)) != 0)
cc0_insn = copy;
else
{
{
int regno = REGNO (SET_DEST (pattern));
- if (map->const_age_map[regno] == map->const_age)
+ if (regno < map->const_equiv_map_size
+ && map->const_age_map[regno] == map->const_age)
map->const_age_map[regno] = -1;
}
break;
case JUMP_INSN:
+ pattern = copy_rtx_and_substitute (PATTERN (insn), map);
+ copy = emit_jump_insn (pattern);
+ REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
+
if (JUMP_LABEL (insn) == start_label && insn == copy_end
&& ! last_iteration)
{
case to be a branch past the end of the loop, and the
original jump label case to fall_through. */
- int fall_through;
-
- /* Never map the label in this case. */
- pattern = copy_rtx (PATTERN (insn));
-
- /* Assume a conditional branch, since the code above
- does not let unconditional branches be copied. */
- if (! condjump_p (insn))
- abort ();
- fall_through
- = (XEXP (SET_SRC (PATTERN (insn)), 2) == pc_rtx) + 1;
-
- /* Set the fall through case to the exit label. Must
- create a new label_ref since they can't be shared. */
- XEXP (SET_SRC (pattern), fall_through)
- = gen_rtx (LABEL_REF, VOIDmode, exit_label);
-
- /* Set the original branch case to fall through. */
- XEXP (SET_SRC (pattern), 3 - fall_through)
- = pc_rtx;
+ if (invert_exp (pattern, copy))
+ {
+ if (! redirect_exp (&pattern,
+ get_label_from_map (map,
+ CODE_LABEL_NUMBER
+ (JUMP_LABEL (insn))),
+ exit_label, copy))
+ abort ();
+ }
+ else
+ {
+ rtx jmp;
+ rtx lab = gen_label_rtx ();
+ /* Can't do it by reversing the jump (probably because we
+ couldn't reverse the conditions), so emit a new
+ jump_insn after COPY, and redirect the jump around
+ that. */
+ jmp = emit_jump_insn_after (gen_jump (exit_label), copy);
+ jmp = emit_barrier_after (jmp);
+ emit_label_after (lab, jmp);
+ LABEL_NUSES (lab) = 0;
+ if (! redirect_exp (&pattern,
+ get_label_from_map (map,
+ CODE_LABEL_NUMBER
+ (JUMP_LABEL (insn))),
+ lab, copy))
+ abort ();
+ }
}
- else
- pattern = copy_rtx_and_substitute (PATTERN (insn), map);
-
- copy = emit_jump_insn (pattern);
#ifdef HAVE_cc0
if (cc0_insn)
later passes of unroll_loop, if INSN had jump label set. */
if (JUMP_LABEL (insn))
{
+ rtx label = 0;
+
/* Can't use the label_map for every insn, since this may be
the backward branch, and hence the label was not mapped. */
- if (GET_CODE (pattern) == SET)
+ if ((set = single_set (copy)))
{
- tem = SET_SRC (pattern);
+ tem = SET_SRC (set);
if (GET_CODE (tem) == LABEL_REF)
- JUMP_LABEL (copy) = XEXP (tem, 0);
+ label = XEXP (tem, 0);
else if (GET_CODE (tem) == IF_THEN_ELSE)
{
if (XEXP (tem, 1) != pc_rtx)
- JUMP_LABEL (copy) = XEXP (XEXP (tem, 1), 0);
+ label = XEXP (XEXP (tem, 1), 0);
else
- JUMP_LABEL (copy) = XEXP (XEXP (tem, 2), 0);
+ label = XEXP (XEXP (tem, 2), 0);
}
- else
- abort ();
}
+
+ if (label && GET_CODE (label) == CODE_LABEL)
+ JUMP_LABEL (copy) = label;
else
{
/* An unrecognizable jump insn, probably the entry jump
for a switch statement. This label must have been mapped,
so just use the label_map to get the new jump label. */
- JUMP_LABEL (copy) = map->label_map[CODE_LABEL_NUMBER
- (JUMP_LABEL (insn))];
+ JUMP_LABEL (copy)
+ = get_label_from_map (map,
+ CODE_LABEL_NUMBER (JUMP_LABEL (insn)));
}
/* If this is a non-local jump, then must increase the label
/* If this is now a no-op, delete it. */
if (map->last_pc_value == pc_rtx)
{
+ /* Don't let delete_insn delete the label referenced here,
+ because we might possibly need it later for some other
+ instruction in the loop. */
+ if (JUMP_LABEL (copy))
+ LABEL_NUSES (JUMP_LABEL (copy))++;
delete_insn (copy);
+ if (JUMP_LABEL (copy))
+ LABEL_NUSES (JUMP_LABEL (copy))--;
copy = 0;
}
else
case CALL_INSN:
pattern = copy_rtx_and_substitute (PATTERN (insn), map);
copy = emit_call_insn (pattern);
+ REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
+
+ /* Because the USAGE information potentially contains objects other
+ than hard registers, we need to copy it. */
+ CALL_INSN_FUNCTION_USAGE (copy)
+ = copy_rtx_and_substitute (CALL_INSN_FUNCTION_USAGE (insn), map);
#ifdef HAVE_cc0
if (cc0_insn)
if (insn != start_label)
{
- copy = emit_label (map->label_map[CODE_LABEL_NUMBER (insn)]);
+ copy = emit_label (get_label_from_map (map,
+ CODE_LABEL_NUMBER (insn)));
map->const_age++;
}
break;
}
while (insn != copy_end);
- /* Now copy the REG_NOTES. */
+ /* Now finish coping the REG_NOTES. */
insn = copy_start;
do
{
if ((GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
|| GET_CODE (insn) == CALL_INSN)
&& map->insn_map[INSN_UID (insn)])
- REG_NOTES (map->insn_map[INSN_UID (insn)])
- = copy_rtx_and_substitute (REG_NOTES (insn), map);
+ final_reg_note_copy (REG_NOTES (map->insn_map[INSN_UID (insn)]), map);
}
while (insn != copy_end);
In practice, this is not a problem, because this function is seldom called,
and uses a negligible amount of CPU time on average. */
-static int
+int
back_branch_in_range_p (insn, loop_start, loop_end)
rtx insn;
rtx loop_start, loop_end;
{
rtx p, q, target_insn;
+ rtx orig_loop_end = loop_end;
/* Stop before we get to the backward branch at the end of the loop. */
loop_end = prev_nonnote_insn (loop_end);
while (INSN_DELETED_P (insn))
insn = NEXT_INSN (insn);
- /* Check for the case where insn is the last insn in the loop. */
- if (insn == loop_end)
+ /* Check for the case where insn is the last insn in the loop. Deal
+ with the case where INSN was a deleted loop test insn, in which case
+ it will now be the NOTE_LOOP_END. */
+ if (insn == loop_end || insn == orig_loop_end)
return 0;
for (p = NEXT_INSN (insn); p != loop_end; p = NEXT_INSN (p))
mult_res = simplify_binary_operation (MULT, mode, mult1, mult2);
if (! mult_res)
- mult_res = gen_rtx (MULT, mode, mult1, mult2);
+ mult_res = gen_rtx_MULT (mode, mult1, mult2);
/* Again, put the constant second. */
if (GET_CODE (add1) == CONST_INT)
result = simplify_binary_operation (PLUS, mode, add1, mult_res);
if (! result)
- result = gen_rtx (PLUS, mode, add1, mult_res);
+ result = gen_rtx_PLUS (mode, add1, mult_res);
return result;
}
/* For increment, must check every instruction that sets it. Each
instruction must be executed only once each time through the loop.
- To verify this, we check that the the insn is always executed, and that
+ To verify this, we check that the insn is always executed, and that
there are no backward branches after the insn that branch to before it.
Also, the insn must have a mult_val of one (to make sure it really is
an increment). */
Initial_value and/or increment are set to zero if their values could not
be calculated. */
-static void
+void
iteration_info (iteration_var, initial_value, increment, loop_start, loop_end)
rtx iteration_var, *initial_value, *increment;
rtx loop_start, loop_end;
{
struct iv_class *bl;
- struct induction *v, *b;
+#if 0
+ struct induction *v;
+#endif
/* Clear the result values, in case no answer can be found. */
*initial_value = 0;
"Loop unrolling: No reg_iv_type entry for iteration var.\n");
return;
}
- /* Reject iteration variables larger than the host long size, since they
+
+ /* Reject iteration variables larger than the host wide int size, since they
could result in a number of iterations greater than the range of our
- `unsigned long' variable loop_n_iterations. */
- else if (GET_MODE_BITSIZE (GET_MODE (iteration_var)) > HOST_BITS_PER_LONG)
+ `unsigned HOST_WIDE_INT' variable loop_n_iterations. */
+ else if ((GET_MODE_BITSIZE (GET_MODE (iteration_var))
+ > HOST_BITS_PER_WIDE_INT))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "Loop unrolling: Iteration var rejected because mode larger than host long.\n");
+ "Loop unrolling: Iteration var rejected because mode too large.\n");
return;
}
else if (GET_MODE_CLASS (GET_MODE (iteration_var)) != MODE_INT)
It must be set to the initial value of the induction variable here.
Otherwise, splittable_regs will hold the difference between the current
value of the induction variable and the value the induction variable had
- at the top of the loop. It must be set to the value 0 here. */
+ at the top of the loop. It must be set to the value 0 here.
+
+ Returns the total number of instructions that set registers that are
+ splittable. */
/* ?? If the loop is only unrolled twice, then most of the restrictions to
constant values are unnecessary, since we can easily calculate increment
int unroll_number;
{
struct iv_class *bl;
+ struct induction *v;
rtx increment, tem;
rtx biv_final_value;
int biv_splittable;
it is unsafe to split the biv since it may not have the proper
value on loop exit. */
- /* loop_number_exit_labels is non-zero if the loop has an exit other than
+ /* loop_number_exit_count is non-zero if the loop has an exit other than
a fall through at the end. */
biv_splittable = 1;
biv_final_value = 0;
if (unroll_type != UNROLL_COMPLETELY
- && (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]
+ && (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
|| unroll_type == UNROLL_NAIVE)
- && (uid_luid[regno_last_uid[bl->regno]] >= INSN_LUID (loop_end)
+ && (uid_luid[REGNO_LAST_UID (bl->regno)] >= INSN_LUID (loop_end)
|| ! bl->init_insn
|| INSN_UID (bl->init_insn) >= max_uid_for_loop
- || (uid_luid[regno_first_uid[bl->regno]]
+ || (uid_luid[REGNO_FIRST_UID (bl->regno)]
< INSN_LUID (bl->init_insn))
|| reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
&& ! (biv_final_value = final_biv_value (bl, loop_start, loop_end)))
biv_splittable = 0;
+ /* If any of the insns setting the BIV don't do so with a simple
+ PLUS, we don't know how to split it. */
+ for (v = bl->biv; biv_splittable && v; v = v->next_iv)
+ if ((tem = single_set (v->insn)) == 0
+ || GET_CODE (SET_DEST (tem)) != REG
+ || REGNO (SET_DEST (tem)) != bl->regno
+ || GET_CODE (SET_SRC (tem)) != PLUS)
+ biv_splittable = 0;
+
/* If final value is non-zero, then must emit an instruction which sets
the value of the biv to the proper value. This is done after
handling all of the givs, since some of them may need to use the
{
/* If the initial value of the biv is itself (i.e. it is too
complicated for strength_reduce to compute), or is a hard
- register, then we must create a new pseudo reg to hold the
- initial value of the biv. */
+ register, or it isn't invariant, then we must create a new
+ pseudo reg to hold the initial value of the biv. */
if (GET_CODE (bl->initial_value) == REG
&& (REGNO (bl->initial_value) == bl->regno
- || REGNO (bl->initial_value) < FIRST_PSEUDO_REGISTER))
+ || REGNO (bl->initial_value) < FIRST_PSEUDO_REGISTER
+ || ! invariant_p (bl->initial_value)))
{
rtx tem = gen_reg_rtx (bl->biv->mode);
-
+
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
loop_start);
we can treat the last one specially. */
splittable_regs_updates[bl->regno] = bl->biv_count;
-
- result++;
+ result += bl->biv_count;
if (loop_dump_stream)
fprintf (loop_dump_stream,
depend on it may be splittable if the biv is live outside the
loop, and the givs aren't. */
- result = find_splittable_givs (bl, unroll_type, loop_start, loop_end,
- increment, unroll_number, result);
+ result += find_splittable_givs (bl, unroll_type, loop_start, loop_end,
+ increment, unroll_number);
/* If final value is non-zero, then must emit an instruction which sets
the value of the biv to the proper value. This is done after
loop to ensure that it will always be executed no matter
how the loop exits. Otherwise emit the insn after the loop,
since this is slightly more efficient. */
- if (! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
+ if (! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
emit_insn_before (gen_move_insn (bl->biv->src_reg,
biv_final_value),
end_insert_before);
this insn will always be executed, no matter how the loop
exits. */
rtx tem = gen_reg_rtx (bl->biv->mode);
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
+
emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
loop_start);
emit_insn_before (gen_move_insn (bl->biv->src_reg,
return result;
}
+/* Return 1 if the first and last unrolled copy of the address giv V is valid
+ for the instruction that is using it. Do not make any changes to that
+ instruction. */
+
+static int
+verify_addresses (v, giv_inc, unroll_number)
+ struct induction *v;
+ rtx giv_inc;
+ int unroll_number;
+{
+ int ret = 1;
+ rtx orig_addr = *v->location;
+ rtx last_addr = plus_constant (v->dest_reg,
+ INTVAL (giv_inc) * (unroll_number - 1));
+
+ /* First check to see if either address would fail. Handle the fact
+ that we have may have a match_dup. */
+ if (! validate_replace_rtx (*v->location, v->dest_reg, v->insn)
+ || ! validate_replace_rtx (*v->location, last_addr, v->insn))
+ ret = 0;
+
+ /* Now put things back the way they were before. This should always
+ succeed. */
+ if (! validate_replace_rtx (*v->location, orig_addr, v->insn))
+ abort ();
+
+ return ret;
+}
+
/* For every giv based on the biv BL, check to determine whether it is
- splittable. This is a subroutine to find_splittable_regs (). */
+ splittable. This is a subroutine to find_splittable_regs ().
+
+ Return the number of instructions that set splittable registers. */
static int
find_splittable_givs (bl, unroll_type, loop_start, loop_end, increment,
- unroll_number, result)
+ unroll_number)
struct iv_class *bl;
enum unroll_types unroll_type;
rtx loop_start, loop_end;
rtx increment;
- int unroll_number, result;
+ int unroll_number;
{
- struct induction *v;
+ struct induction *v, *v2;
rtx final_value;
rtx tem;
+ int result = 0;
+
+ /* Scan the list of givs, and set the same_insn field when there are
+ multiple identical givs in the same insn. */
+ for (v = bl->giv; v; v = v->next_iv)
+ for (v2 = v->next_iv; v2; v2 = v2->next_iv)
+ if (v->insn == v2->insn && rtx_equal_p (v->new_reg, v2->new_reg)
+ && ! v2->same_insn)
+ v2->same_insn = v;
for (v = bl->giv; v; v = v->next_iv)
{
final_value = 0;
if (unroll_type != UNROLL_COMPLETELY
- && (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]
+ && (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
|| unroll_type == UNROLL_NAIVE)
&& v->giv_type != DEST_ADDR
- && ((regno_first_uid[REGNO (v->dest_reg)] != INSN_UID (v->insn)
- /* Check for the case where the pseudo is set by a shift/add
- sequence, in which case the first insn setting the pseudo
- is the first insn of the shift/add sequence. */
- && (! (tem = find_reg_note (v->insn, REG_RETVAL, NULL_RTX))
- || (regno_first_uid[REGNO (v->dest_reg)]
- != INSN_UID (XEXP (tem, 0)))))
+ /* The next part is true if the pseudo is used outside the loop.
+ We assume that this is true for any pseudo created after loop
+ starts, because we don't have a reg_n_info entry for them. */
+ && (REGNO (v->dest_reg) >= max_reg_before_loop
+ || (REGNO_FIRST_UID (REGNO (v->dest_reg)) != INSN_UID (v->insn)
+ /* Check for the case where the pseudo is set by a shift/add
+ sequence, in which case the first insn setting the pseudo
+ is the first insn of the shift/add sequence. */
+ && (! (tem = find_reg_note (v->insn, REG_RETVAL, NULL_RTX))
+ || (REGNO_FIRST_UID (REGNO (v->dest_reg))
+ != INSN_UID (XEXP (tem, 0)))))
/* Line above always fails if INSN was moved by loop opt. */
- || (uid_luid[regno_last_uid[REGNO (v->dest_reg)]]
+ || (uid_luid[REGNO_LAST_UID (REGNO (v->dest_reg))]
>= INSN_LUID (loop_end)))
&& ! (final_value = v->final_value))
continue;
giv's initial value. Otherwise, save the constant zero for it. */
if (unroll_type == UNROLL_COMPLETELY)
- /* It is not safe to use bl->initial_value here, because it may not
- be invariant. It is safe to use the initial value stored in
- the splittable_regs array. */
- value = fold_rtx_mult_add (v->mult_val, splittable_regs[bl->regno],
- v->add_val, v->mode);
+ {
+ /* It is not safe to use bl->initial_value here, because it may not
+ be invariant. It is safe to use the initial value stored in
+ the splittable_regs array if it is set. In rare cases, it won't
+ be set, so then we do exactly the same thing as
+ find_splittable_regs does to get a safe value. */
+ rtx biv_initial_value;
+
+ if (splittable_regs[bl->regno])
+ biv_initial_value = splittable_regs[bl->regno];
+ else if (GET_CODE (bl->initial_value) != REG
+ || (REGNO (bl->initial_value) != bl->regno
+ && REGNO (bl->initial_value) >= FIRST_PSEUDO_REGISTER))
+ biv_initial_value = bl->initial_value;
+ else
+ {
+ rtx tem = gen_reg_rtx (bl->biv->mode);
+
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
+ emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
+ loop_start);
+ biv_initial_value = tem;
+ }
+ value = fold_rtx_mult_add (v->mult_val, biv_initial_value,
+ v->add_val, v->mode);
+ }
else
value = const0_rtx;
{
/* If value is not a constant, register, or register plus
constant, then compute its value into a register before
- loop start. This prevents illegal rtx sharing, and should
+ loop start. This prevents invalid rtx sharing, and should
generate better code. We can use bl->initial_value here
instead of splittable_regs[bl->regno] because this code
is going before the loop start. */
|| GET_CODE (XEXP (value, 1)) != CONST_INT))
{
rtx tem = gen_reg_rtx (v->mode);
+ record_base_value (REGNO (tem), v->add_val, 0);
emit_iv_add_mult (bl->initial_value, v->mult_val,
v->add_val, tem, loop_start);
value = tem;
what we want for split addr regs. We always create a new
register for the split addr giv, just to be safe. */
- /* ??? If there are multiple address givs which have been
- combined with the same dest_reg giv, then we may only need
- one new register for them. Pulling out constants below will
- catch some of the common cases of this. Currently, I leave
- the work of simplifying multiple address givs to the
- following cse pass. */
-
+ /* If we have multiple identical address givs within a
+ single instruction, then use a single pseudo reg for
+ both. This is necessary in case one is a match_dup
+ of the other. */
+
v->const_adjust = 0;
- if (unroll_type != UNROLL_COMPLETELY)
+
+ if (v->same_insn)
+ {
+ v->dest_reg = v->same_insn->dest_reg;
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Sharing address givs in insn %d\n",
+ INSN_UID (v->insn));
+ }
+ /* If multiple address GIVs have been combined with the
+ same dest_reg GIV, do not create a new register for
+ each. */
+ else if (unroll_type != UNROLL_COMPLETELY
+ && v->giv_type == DEST_ADDR
+ && v->same && v->same->giv_type == DEST_ADDR
+ && v->same->unrolled
+ /* combine_givs_p may return true for some cases
+ where the add and mult values are not equal.
+ To share a register here, the values must be
+ equal. */
+ && rtx_equal_p (v->same->mult_val, v->mult_val)
+ && rtx_equal_p (v->same->add_val, v->add_val))
+
+ {
+ v->dest_reg = v->same->dest_reg;
+ v->shared = 1;
+ }
+ else if (unroll_type != UNROLL_COMPLETELY)
{
/* If not completely unrolling the loop, then create a new
register to hold the split value of the DEST_ADDR giv.
Emit insn to initialize its value before loop start. */
- tem = gen_reg_rtx (v->mode);
+
+ rtx tem = gen_reg_rtx (v->mode);
+ record_base_value (REGNO (tem), v->add_val, 0);
/* If the address giv has a constant in its new_reg value,
then this constant can be pulled out and put in value,
{
v->dest_reg
= plus_constant (tem, INTVAL (XEXP (v->new_reg,1)));
-
+
/* Only succeed if this will give valid addresses.
Try to validate both the first and the last
address resulting from loop unrolling, if
one fails, then can't do const elim here. */
- if (memory_address_p (v->mode, v->dest_reg)
- && memory_address_p (v->mode,
- plus_constant (v->dest_reg,
- INTVAL (giv_inc)
- * (unroll_number - 1))))
+ if (verify_addresses (v, giv_inc, unroll_number))
{
/* Save the negative of the eliminated const, so
that we can calculate the dest_reg's increment
/* If the address hasn't been checked for validity yet, do so
now, and fail completely if either the first or the last
- unrolled copy of the address is not a valid address. */
+ unrolled copy of the address is not a valid address
+ for the instruction that uses it. */
if (v->dest_reg == tem
- && (! memory_address_p (v->mode, v->dest_reg)
- || ! memory_address_p (v->mode,
- plus_constant (v->dest_reg,
- INTVAL (giv_inc)
- * (unroll_number -1)))))
+ && ! verify_addresses (v, giv_inc, unroll_number))
{
+ for (v2 = v->next_iv; v2; v2 = v2->next_iv)
+ if (v2->same_insn == v)
+ v2->same_insn = 0;
+
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "Illegal address for giv at insn %d\n",
+ "Invalid address for giv at insn %d\n",
INSN_UID (v->insn));
continue;
}
+ /* We set this after the address check, to guarantee that
+ the register will be initialized. */
+ v->unrolled = 1;
+
/* To initialize the new register, just move the value of
new_reg into it. This is not guaranteed to give a valid
instruction on machines with complex addressing modes.
If we can't recognize it, then delete it and emit insns
to calculate the value from scratch. */
- emit_insn_before (gen_rtx (SET, VOIDmode, tem,
- copy_rtx (v->new_reg)),
+ emit_insn_before (gen_rtx_SET (VOIDmode, tem,
+ copy_rtx (v->new_reg)),
loop_start);
- if (! recog_memoized (PREV_INSN (loop_start)))
+ if (recog_memoized (PREV_INSN (loop_start)) < 0)
{
+ rtx sequence, ret;
+
+ /* We can't use bl->initial_value to compute the initial
+ value, because the loop may have been preconditioned.
+ We must calculate it from NEW_REG. Try using
+ force_operand instead of emit_iv_add_mult. */
delete_insn (PREV_INSN (loop_start));
- emit_iv_add_mult (bl->initial_value, v->mult_val,
- v->add_val, tem, loop_start);
+
+ start_sequence ();
+ ret = force_operand (v->new_reg, tem);
+ if (ret != tem)
+ emit_move_insn (tem, ret);
+ sequence = gen_sequence ();
+ end_sequence ();
+ emit_insn_before (sequence, loop_start);
+
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "Illegal init insn, rewritten.\n");
+ "Invalid init insn, rewritten.\n");
}
}
else
v->dest_reg = value;
/* Check the resulting address for validity, and fail
- if the resulting address would be illegal. */
- if (! memory_address_p (v->mode, v->dest_reg)
- || ! memory_address_p (v->mode,
- plus_constant (v->dest_reg,
- INTVAL (giv_inc) *
- (unroll_number -1))))
+ if the resulting address would be invalid. */
+ if (! verify_addresses (v, giv_inc, unroll_number))
{
+ for (v2 = v->next_iv; v2; v2 = v2->next_iv)
+ if (v2->same_insn == v)
+ v2->same_insn = 0;
+
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "Illegal address for giv at insn %d\n",
+ "Invalid address for giv at insn %d\n",
INSN_UID (v->insn));
continue;
}
#endif
}
- /* Givs are only updated once by definition. Mark it so if this is
+ /* Unreduced givs are only updated once by definition. Reduced givs
+ are updated as many times as their biv is. Mark it so if this is
a splittable register. Don't need to do anything for address givs
where this may not be a register. */
if (GET_CODE (v->new_reg) == REG)
- splittable_regs_updates[REGNO (v->new_reg)] = 1;
+ {
+ int count = 1;
+ if (! v->ignore)
+ count = reg_biv_class[REGNO (v->src_reg)]->biv_count;
+
+ splittable_regs_updates[REGNO (v->new_reg)] = count;
+ }
result++;
rtx insn, label;
enum rtx_code code;
int jump_count = 0;
+ int label_count = 0;
+ int this_loop_num = uid_loop_num[INSN_UID (loop_start)];
+
+ /* In addition to checking all exits of this loop, we must also check
+ all exits of inner nested loops that would exit this loop. We don't
+ have any way to identify those, so we just give up if there are any
+ such inner loop exits. */
+
+ for (label = loop_number_exit_labels[this_loop_num]; label;
+ label = LABEL_NEXTREF (label))
+ label_count++;
+
+ if (label_count != loop_number_exit_count[this_loop_num])
+ return 0;
/* HACK: Must also search the loop fall through exit, create a label_ref
here which points to the loop_end, and append the loop_number_exit_labels
list to it. */
- label = gen_rtx (LABEL_REF, VOIDmode, loop_end);
- LABEL_NEXTREF (label)
- = loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]];
+ label = gen_rtx_LABEL_REF (VOIDmode, loop_end);
+ LABEL_NEXTREF (label) = loop_number_exit_labels[this_loop_num];
for ( ; label; label = LABEL_NEXTREF (label))
{
if (GET_CODE (PATTERN (insn)) == RETURN)
break;
else if (! simplejump_p (insn)
- /* Prevent infinite loop following infinite loops. */
+ /* Prevent infinite loop following infinite loops. */
|| jump_count++ > 20)
return 0;
else
value of the biv must be invariant. */
if (loop_n_iterations != 0
- && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]
+ && ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
&& invariant_p (bl->initial_value))
{
increment = biv_total_increment (bl, loop_start, loop_end);
case it is needed later. */
tem = gen_reg_rtx (bl->biv->mode);
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
+ /* Make sure loop_end is not the last insn. */
+ if (NEXT_INSN (loop_end) == 0)
+ emit_note_after (NOTE_INSN_DELETED, loop_end);
emit_iv_add_mult (increment, GEN_INT (loop_n_iterations),
bl->initial_value, tem, NEXT_INSN (loop_end));
rtx loop_start, loop_end;
{
struct iv_class *bl;
- rtx reg, insn, pattern;
+ rtx insn;
rtx increment, tem;
- enum rtx_code code;
rtx insert_before, seq;
bl = reg_biv_class[REGNO (v->src_reg)];
to be known. */
if (loop_n_iterations != 0
- && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
+ && ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
{
/* ?? It is tempting to use the biv's value here since these insns will
be put after the loop, and hence the biv will have its final value
determine whether giv's are replaceable so that we can use the
biv value here if it is not eliminable. */
+ /* We are emitting code after the end of the loop, so we must make
+ sure that bl->initial_value is still valid then. It will still
+ be valid if it is invariant. */
+
increment = biv_total_increment (bl, loop_start, loop_end);
- if (increment && invariant_p (increment))
+ if (increment && invariant_p (increment)
+ && invariant_p (bl->initial_value))
{
/* Can calculate the loop exit value of its biv as
(loop_n_iterations * increment) + initial_value */
/* Put the final biv value in tem. */
tem = gen_reg_rtx (bl->biv->mode);
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
emit_iv_add_mult (increment, GEN_INT (loop_n_iterations),
bl->initial_value, tem, insert_before);
for (insn = NEXT_INSN (v->insn); insn != loop_end;
insn = NEXT_INSN (insn))
{
- if (GET_CODE (insn) == INSN
- && GET_CODE (PATTERN (insn)) == SET
- && SET_DEST (PATTERN (insn)) == v->src_reg)
- {
- pattern = PATTERN (insn);
- if (GET_CODE (SET_SRC (pattern)) != PLUS)
- {
- /* Sometimes a biv is computed in a temp reg,
- and then copied into the biv reg. */
- pattern = PATTERN (PREV_INSN (insn));
- if (GET_CODE (SET_SRC (pattern)) != PLUS)
- abort ();
- }
- if (GET_CODE (XEXP (SET_SRC (pattern), 0)) != REG
- || REGNO (XEXP (SET_SRC (pattern), 0)) != bl->regno)
- abort ();
-
- start_sequence ();
- tem = expand_binop (GET_MODE (tem), sub_optab, tem,
- XEXP (SET_SRC (pattern), 1), NULL_RTX, 0,
- OPTAB_LIB_WIDEN);
- seq = gen_sequence ();
- end_sequence ();
- emit_insn_before (seq, insert_before);
- }
+ struct induction *biv;
+
+ for (biv = bl->biv; biv; biv = biv->next_iv)
+ if (biv->insn == insn)
+ {
+ start_sequence ();
+ tem = expand_binop (GET_MODE (tem), sub_optab, tem,
+ biv->add_val, NULL_RTX, 0,
+ OPTAB_LIB_WIDEN);
+ seq = gen_sequence ();
+ end_sequence ();
+ emit_insn_before (seq, insert_before);
+ }
}
/* Now calculate the giv's final value. */
loop_final_value = 0;
loop_iteration_var = 0;
- last_loop_insn = prev_nonnote_insn (loop_end);
+ /* We used to use pren_nonnote_insn here, but that fails because it might
+ accidentally get the branch for a contained loop if the branch for this
+ loop was deleted. We can only trust branches immediately before the
+ loop_end. */
+ last_loop_insn = PREV_INSN (loop_end);
comparison = get_condition_for_loop (last_loop_insn);
if (comparison == 0)
/* iteration_info already printed a message. */
return 0;
- if (increment == 0)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Increment value can't be calculated.\n");
- return 0;
- }
- if (GET_CODE (increment) != CONST_INT)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Increment value not constant.\n");
- return 0;
- }
- if (GET_CODE (initial_value) != CONST_INT)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Initial value not constant.\n");
- return 0;
- }
-
/* If the comparison value is an invariant register, then try to find
its value from the insns before the start of the loop. */
break;
else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
- && (set = single_set (insn))
- && (SET_DEST (set) == comparison_value))
+ && reg_set_p (comparison_value, insn))
{
- rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
-
- if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
- comparison_value = XEXP (note, 0);
-
+ /* We found the last insn before the loop that sets the register.
+ If it sets the entire register, and has a REG_EQUAL note,
+ then use the value of the REG_EQUAL note. */
+ if ((set = single_set (insn))
+ && (SET_DEST (set) == comparison_value))
+ {
+ rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
+
+ /* Only use the REG_EQUAL note if it is a constant.
+ Other things, divide in particular, will cause
+ problems later if we use them. */
+ if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST
+ && CONSTANT_P (XEXP (note, 0)))
+ comparison_value = XEXP (note, 0);
+ }
break;
}
}
loop_initial_value = initial_value;
loop_increment = increment;
loop_final_value = final_value;
+ loop_comparison_code = comparison_code;
- if (final_value == 0)
+ if (increment == 0)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop unrolling: Increment value can't be calculated.\n");
+ return 0;
+ }
+ else if (GET_CODE (increment) != CONST_INT)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop unrolling: Increment value not constant.\n");
+ return 0;
+ }
+ else if (GET_CODE (initial_value) != CONST_INT)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop unrolling: Initial value not constant.\n");
+ return 0;
+ }
+ else if (final_value == 0)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
return tempu / i + ((tempu % i) != 0);
}
+
+/* Replace uses of split bivs with their split pseudo register. This is
+ for original instructions which remain after loop unrolling without
+ copying. */
+
+static rtx
+remap_split_bivs (x)
+ rtx x;
+{
+ register enum rtx_code code;
+ register int i;
+ register char *fmt;
+
+ if (x == 0)
+ return x;
+
+ code = GET_CODE (x);
+ switch (code)
+ {
+ case SCRATCH:
+ case PC:
+ case CC0:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ return x;
+
+ case REG:
+#if 0
+ /* If non-reduced/final-value givs were split, then this would also
+ have to remap those givs also. */
+#endif
+ if (REGNO (x) < max_reg_before_loop
+ && reg_iv_type[REGNO (x)] == BASIC_INDUCT)
+ return reg_biv_class[REGNO (x)]->biv->src_reg;
+ break;
+
+ default:
+ break;
+ }
+
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ XEXP (x, i) = remap_split_bivs (XEXP (x, i));
+ if (fmt[i] == 'E')
+ {
+ register int j;
+ for (j = 0; j < XVECLEN (x, i); j++)
+ XVECEXP (x, i, j) = remap_split_bivs (XVECEXP (x, i, j));
+ }
+ }
+ return x;
+}
+
+/* If FIRST_UID is a set of REGNO, and FIRST_UID dominates LAST_UID (e.g.
+ FIST_UID is always executed if LAST_UID is), then return 1. Otherwise
+ return 0. COPY_START is where we can start looking for the insns
+ FIRST_UID and LAST_UID. COPY_END is where we stop looking for these
+ insns.
+
+ If there is no JUMP_INSN between LOOP_START and FIRST_UID, then FIRST_UID
+ must dominate LAST_UID.
+
+ If there is a CODE_LABEL between FIRST_UID and LAST_UID, then FIRST_UID
+ may not dominate LAST_UID.
+
+ If there is no CODE_LABEL between FIRST_UID and LAST_UID, then FIRST_UID
+ must dominate LAST_UID. */
+
+int
+set_dominates_use (regno, first_uid, last_uid, copy_start, copy_end)
+ int regno;
+ int first_uid;
+ int last_uid;
+ rtx copy_start;
+ rtx copy_end;
+{
+ int passed_jump = 0;
+ rtx p = NEXT_INSN (copy_start);
+
+ while (INSN_UID (p) != first_uid)
+ {
+ if (GET_CODE (p) == JUMP_INSN)
+ passed_jump= 1;
+ /* Could not find FIRST_UID. */
+ if (p == copy_end)
+ return 0;
+ p = NEXT_INSN (p);
+ }
+
+ /* Verify that FIRST_UID is an insn that entirely sets REGNO. */
+ if (GET_RTX_CLASS (GET_CODE (p)) != 'i'
+ || ! dead_or_set_regno_p (p, regno))
+ return 0;
+
+ /* FIRST_UID is always executed. */
+ if (passed_jump == 0)
+ return 1;
+
+ while (INSN_UID (p) != last_uid)
+ {
+ /* If we see a CODE_LABEL between FIRST_UID and LAST_UID, then we
+ can not be sure that FIRST_UID dominates LAST_UID. */
+ if (GET_CODE (p) == CODE_LABEL)
+ return 0;
+ /* Could not find LAST_UID, but we reached the end of the loop, so
+ it must be safe. */
+ else if (p == copy_end)
+ return 1;
+ p = NEXT_INSN (p);
+ }
+
+ /* FIRST_UID is always executed if LAST_UID is executed. */
+ return 1;
+}
OSDN Git Service
