/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992 Free Software Foundation, Inc.
+ Copyright (C) 1992, 93, 94, 95, 97, 98, 1999 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. */
static int *splittable_regs_updates;
-/* 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;
-
/* 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 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));
+static void iteration_info PROTO((rtx, rtx *, rtx *, rtx, rtx));
+static int find_splittable_regs PROTO((enum unroll_types, rtx, rtx, rtx, int,
+ unsigned HOST_WIDE_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.
void
unroll_loop (loop_end, insn_count, loop_start, end_insert_before,
- strength_reduce_p)
+ loop_info, strength_reduce_p)
rtx loop_end;
int insn_count;
rtx loop_start;
rtx end_insert_before;
+ struct loop_info *loop_info;
int strength_reduce_p;
{
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;
/* Determine type of unroll to perform. Depends on the number of iterations
and the size of the loop. */
- /* If there is no strength reduce info, then set loop_n_iterations to zero.
- This can happen if strength_reduce can't find any bivs in the loop.
- A value of zero indicates that the number of iterations could not be
- calculated. */
+ /* If there is no strength reduce info, then set
+ loop_info->n_iterations to zero. This can happen if
+ strength_reduce can't find any bivs in the loop. A value of zero
+ indicates that the number of iterations could not be calculated. */
if (! strength_reduce_p)
- loop_n_iterations = 0;
+ loop_info->n_iterations = 0;
- if (loop_dump_stream && loop_n_iterations > 0)
- fprintf (loop_dump_stream,
- "Loop unrolling: %d iterations.\n", loop_n_iterations);
+ if (loop_dump_stream && loop_info->n_iterations > 0)
+ {
+ fputs ("Loop unrolling: ", loop_dump_stream);
+ fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
+ loop_info->n_iterations);
+ fputs (" iterations.\n", loop_dump_stream);
+ }
/* Find and save a pointer to the last nonnote insn in the loop. */
/* Calculate how many times to unroll the loop. Indicate whether or
not the loop is being completely unrolled. */
- if (loop_n_iterations == 1)
+ if (loop_info->n_iterations == 1)
{
/* If number of iterations is exactly 1, then eliminate the compare and
branch at the end of the loop since they will never be taken.
}
return;
}
- else if (loop_n_iterations > 0
- && loop_n_iterations * insn_count < MAX_UNROLLED_INSNS)
+ else if (loop_info->n_iterations > 0
+ && loop_info->n_iterations * insn_count < MAX_UNROLLED_INSNS)
{
- unroll_number = loop_n_iterations;
+ unroll_number = loop_info->n_iterations;
unroll_type = UNROLL_COMPLETELY;
}
- else if (loop_n_iterations > 0)
+ else if (loop_info->n_iterations > 0)
{
/* Try to factor the number of iterations. Don't bother with the
general case, only using 2, 3, 5, and 7 will get 75% of all
for (i = 0; i < NUM_FACTORS; i++)
factors[i].count = 0;
- temp = loop_n_iterations;
+ temp = loop_info->n_iterations;
for (i = NUM_FACTORS - 1; i >= 0; i--)
while (temp % factors[i].factor == 0)
{
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. */
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.
if (unroll_type == UNROLL_NAIVE && ! splitting_not_safe && strength_reduce_p)
{
rtx initial_value, final_value, increment;
+ enum machine_mode mode;
- if (precondition_loop_p (&initial_value, &final_value, &increment,
- loop_start, loop_end))
+ if (precondition_loop_p (loop_start, loop_info,
+ &initial_value, &final_value, &increment,
+ &mode))
{
- register rtx diff, temp;
- enum machine_mode mode;
+ register rtx diff ;
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);
start_sequence ();
- /* Decide what mode to do these calculations in. Choose the larger
- of final_value's mode and initial_value's mode, or a full-word if
- both are constants. */
- mode = GET_MODE (final_value);
- if (mode == VOIDmode)
- {
- mode = GET_MODE (initial_value);
- if (mode == VOIDmode)
- mode = word_mode;
- }
- else if (mode != GET_MODE (initial_value)
- && (GET_MODE_SIZE (mode)
- < GET_MODE_SIZE (GET_MODE (initial_value))))
- mode = GET_MODE (initial_value);
-
/* Calculate the difference between the final and initial values.
Final value may be a (plus (reg x) (const_int 1)) rtx.
Let the following cse pass simplify this if initial value is
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_info->comparison_code != NE)
+ {
+ emit_cmp_and_jump_insns (initial_value, final_value,
+ neg_inc ? LE : GE,
+ NULL_RTX, mode, 0, 0, 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;
-
- emit_cmp_insn (diff, GEN_INT (abs_inc * cmp_const),
- EQ, NULL_RTX, mode, 0, 0);
+ {
+ cmp_const = i;
+ cmp_code = LE;
+ }
- if (i == 0)
- emit_jump_insn (gen_beq (labels[i]));
- else if (neg_inc)
- emit_jump_insn (gen_bge (labels[i]));
- else
- emit_jump_insn (gen_ble (labels[i]));
+ emit_cmp_and_jump_insns (diff, GEN_INT (abs_inc * cmp_const),
+ cmp_code, NULL_RTX, mode, 0, 0,
+ labels[i]);
JUMP_LABEL (get_last_insn ()) = labels[i];
LABEL_NUSES (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;
-
- emit_cmp_insn (diff, GEN_INT (cmp_const), EQ, NULL_RTX,
- mode, 0, 0);
+ {
+ cmp_const = abs_inc * (unroll_number - 1) + 1;
+ cmp_code = GE;
+ }
- if (neg_inc)
- emit_jump_insn (gen_ble (labels[0]));
- else
- emit_jump_insn (gen_bge (labels[0]));
+ emit_cmp_and_jump_insns (diff, GEN_INT (cmp_const), cmp_code,
+ NULL_RTX, mode, 0, 0, labels[0]);
JUMP_LABEL (get_last_insn ()) = labels[0];
LABEL_NUSES (labels[0])++;
}
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 the loop. */
+ if (unroll_type == UNROLL_COMPLETELY)
+ loop_info->unroll_number = -1;
+ else
+ loop_info->unroll_number = 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
temp = 0;
else
temp = find_splittable_regs (unroll_type, loop_start, loop_end,
- end_insert_before, unroll_number);
+ end_insert_before, unroll_number,
+ loop_info->n_iterations);
/* find_splittable_regs may have created some new registers, so must
reallocate the reg_map with the new larger size, and must realloc
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 unroll_number times, make a copy of each instruction
between copy_start and copy_end, and insert these new instructions
before the end of the loop. */
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. */
/* ??? If the loop is known to be executed very many times, or the machine
has a very cheap divide instruction, then preconditioning is a win even
when the increment is not a power of 2. Use RTX_COST to compute
- whether divide is cheap. */
-
-static int
-precondition_loop_p (initial_value, final_value, increment, loop_start,
- loop_end)
+ whether divide is cheap.
+ ??? A divide by constant doesn't actually need a divide, look at
+ expand_divmod. The reduced cost of this optimized modulo is not
+ reflected in RTX_COST. */
+
+int
+precondition_loop_p (loop_start, loop_info,
+ initial_value, final_value, increment, mode)
+ rtx loop_start;
+ struct loop_info *loop_info;
rtx *initial_value, *final_value, *increment;
- rtx loop_start, loop_end;
+ enum machine_mode *mode;
{
- int unsigned_compare, compare_dir;
- if (loop_n_iterations > 0)
+ if (loop_info->n_iterations > 0)
{
*initial_value = const0_rtx;
*increment = const1_rtx;
- *final_value = GEN_INT (loop_n_iterations);
+ *final_value = GEN_INT (loop_info->n_iterations);
+ *mode = word_mode;
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_info->n_iterations);
+ fputs (".\n", loop_dump_stream);
+ }
return 1;
}
- if (loop_initial_value == 0)
+ if (loop_info->initial_value == 0)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Preconditioning: Could not find initial value.\n");
return 0;
}
- else if (loop_increment == 0)
+ else if (loop_info->increment == 0)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Preconditioning: Could not find increment value.\n");
return 0;
}
- else if (GET_CODE (loop_increment) != CONST_INT)
+ else if (GET_CODE (loop_info->increment) != CONST_INT)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Preconditioning: Increment not a constant.\n");
return 0;
}
- else if ((exact_log2 (INTVAL (loop_increment)) < 0)
- && (exact_log2 (- INTVAL (loop_increment)) < 0))
+ else if ((exact_log2 (INTVAL (loop_info->increment)) < 0)
+ && (exact_log2 (- INTVAL (loop_info->increment)) < 0))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
/* Unsigned_compare and compare_dir can be ignored here, since they do
not matter for preconditioning. */
- if (loop_final_value == 0)
+ if (loop_info->final_value == 0)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
to make sure that the register is in the range covered by invariant_p.
If it isn't, then it is most likely a biv/giv which by definition are
not invariant. */
- if ((GET_CODE (loop_final_value) == REG
- && REGNO (loop_final_value) >= max_reg_before_loop)
- || (GET_CODE (loop_final_value) == PLUS
- && REGNO (XEXP (loop_final_value, 0)) >= max_reg_before_loop)
- || ! invariant_p (loop_final_value))
+ if ((GET_CODE (loop_info->final_value) == REG
+ && REGNO (loop_info->final_value) >= max_reg_before_loop)
+ || (GET_CODE (loop_info->final_value) == PLUS
+ && REGNO (XEXP (loop_info->final_value, 0)) >= max_reg_before_loop)
+ || ! invariant_p (loop_info->final_value))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
/* Fail for floating point values, since the caller of this function
does not have code to deal with them. */
- if (GET_MODE_CLASS (GET_MODE (loop_final_value)) == MODE_FLOAT
- || GET_MODE_CLASS (GET_MODE (loop_initial_value)) == MODE_FLOAT)
+ if (GET_MODE_CLASS (GET_MODE (loop_info->final_value)) == MODE_FLOAT
+ || GET_MODE_CLASS (GET_MODE (loop_info->initial_value)) == MODE_FLOAT)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
return 0;
}
- /* Now set initial_value to be the iteration_var, since that may be a
- simpler expression, and is guaranteed to be correct if all of the
- above tests succeed.
+ /* Fail if loop_info->iteration_var is not live before loop_start,
+ since we need to test its value in the preconditioning code. */
- We can not use the initial_value as calculated, because it will be
- one too small for loops of the form "while (i-- > 0)". We can not
- emit code before the loop_skip_over insns to fix this problem as this
- will then give a number one too large for loops of the form
- "while (--i > 0)".
-
- Note that all loops that reach here are entered at the top, because
- this function is not called if the loop starts with a jump. */
-
- /* 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_info->iteration_var))]
> INSN_LUID (loop_start))
{
if (loop_dump_stream)
return 0;
}
- *initial_value = loop_iteration_var;
- *increment = loop_increment;
- *final_value = loop_final_value;
+ /* ??? Note that if iteration_info is modifed to allow GIV iterators
+ such as "while (i-- > 0)", the initial value will be one too small.
+ In this case, loop_iteration_var could be used to determine
+ the correct initial value, provided the loop has not been reversed.
+
+ Also note that the absolute values of initial_value and
+ final_value are unimportant as only their difference is used for
+ calculating the number of loop iterations. */
+ *initial_value = loop_info->initial_value;
+ *increment = loop_info->increment;
+ *final_value = loop_info->final_value;
+
+ /* Decide what mode to do these calculations in. Choose the larger
+ of final_value's mode and initial_value's mode, or a full-word if
+ both are constants. */
+ *mode = GET_MODE (*final_value);
+ if (*mode == VOIDmode)
+ {
+ *mode = GET_MODE (*initial_value);
+ if (*mode == VOIDmode)
+ *mode = word_mode;
+ }
+ else if (*mode != GET_MODE (*initial_value)
+ && (GET_MODE_SIZE (*mode)
+ < GET_MODE_SIZE (GET_MODE (*initial_value))))
+ *mode = GET_MODE (*initial_value);
/* Success! */
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. */
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. */
- if (! invert_exp (pattern, copy)
- || ! redirect_exp (&pattern,
- map->label_map[CODE_LABEL_NUMBER
- (JUMP_LABEL (insn))],
- exit_label, copy))
- abort ();
+ 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 ();
+ }
}
#ifdef HAVE_cc0
/* 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)
label = XEXP (tem, 0);
else if (GET_CODE (tem) == IF_THEN_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). */
for (v = bl->biv; v; v = v->next_iv)
{
if (v->always_computable && v->mult_val == const1_rtx
- && ! back_branch_in_range_p (v->insn, loop_start, loop_end))
+ && ! v->maybe_multiple)
result = fold_rtx_mult_add (result, const1_rtx, v->add_val, v->mode);
else
return 0;
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_info->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)
}
}
-/* Calculate the approximate final value of the iteration variable
- which has an loop exit test with code COMPARISON_CODE and comparison value
- of COMPARISON_VALUE. Also returns an indication of whether the comparison
- was signed or unsigned, and the direction of the comparison. This info is
- needed to calculate the number of loop iterations. */
-
-static rtx
-approx_final_value (comparison_code, comparison_value, unsigned_p, compare_dir)
- enum rtx_code comparison_code;
- rtx comparison_value;
- int *unsigned_p;
- int *compare_dir;
-{
- /* Calculate the final value of the induction variable.
- The exact final value depends on the branch operator, and increment sign.
- This is only an approximate value. It will be wrong if the iteration
- variable is not incremented by one each time through the loop, and
- approx final value - start value % increment != 0. */
-
- *unsigned_p = 0;
- switch (comparison_code)
- {
- case LEU:
- *unsigned_p = 1;
- case LE:
- *compare_dir = 1;
- return plus_constant (comparison_value, 1);
- case GEU:
- *unsigned_p = 1;
- case GE:
- *compare_dir = -1;
- return plus_constant (comparison_value, -1);
- case EQ:
- /* Can not calculate a final value for this case. */
- *compare_dir = 0;
- return 0;
- case LTU:
- *unsigned_p = 1;
- case LT:
- *compare_dir = 1;
- return comparison_value;
- break;
- case GTU:
- *unsigned_p = 1;
- case GT:
- *compare_dir = -1;
- return comparison_value;
- case NE:
- *compare_dir = 0;
- return comparison_value;
- default:
- abort ();
- }
-}
/* For each biv and giv, determine whether it can be safely split into
a different variable for each unrolled copy of the loop body. If it
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
static int
find_splittable_regs (unroll_type, loop_start, loop_end, end_insert_before,
- unroll_number)
+ unroll_number, n_iterations)
enum unroll_types unroll_type;
rtx loop_start, loop_end;
rtx end_insert_before;
int unroll_number;
+ unsigned HOST_WIDE_INT n_iterations;
{
struct iv_class *bl;
struct induction *v;
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_final_value = final_biv_value (bl, loop_start, loop_end,
+ n_iterations)))
biv_splittable = 0;
/* If any of the insns setting the BIV don't do so with a simple
{
/* 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;
{
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;
{
/* 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)
+ /* If the memory references have different modes,
+ then the address may not be valid and we must
+ not share registers. */
+ && verify_addresses (v, giv_inc, unroll_number))
+ {
+ 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->mem_mode, v->dest_reg)
- && memory_address_p (v->mem_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->mem_mode, v->dest_reg)
- || ! memory_address_p (v->mem_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)) < 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->mem_mode, v->dest_reg)
- || ! memory_address_p (v->mem_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
the end of the loop. If we can do it, return that value. */
rtx
-final_biv_value (bl, loop_start, loop_end)
+final_biv_value (bl, loop_start, loop_end, n_iterations)
struct iv_class *bl;
rtx loop_start, loop_end;
+ unsigned HOST_WIDE_INT n_iterations;
{
rtx increment, tem;
it may not have its final value when the loop exits), and the initial
value of the biv must be invariant. */
- if (loop_n_iterations != 0
- && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]
+ if (n_iterations != 0
+ && ! 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),
+ emit_iv_add_mult (increment, GEN_INT (n_iterations),
bl->initial_value, tem, NEXT_INSN (loop_end));
if (loop_dump_stream)
the end of the loop. If we can do it, return that value. */
rtx
-final_giv_value (v, loop_start, loop_end)
+final_giv_value (v, loop_start, loop_end, n_iterations)
struct induction *v;
rtx loop_start, loop_end;
+ unsigned HOST_WIDE_INT n_iterations;
{
struct iv_class *bl;
rtx insn;
rtx increment, tem;
- enum rtx_code code;
rtx insert_before, seq;
bl = reg_biv_class[REGNO (v->src_reg)];
only one exit for this to work, but the loop iterations does not need
to be known. */
- if (loop_n_iterations != 0
- && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
+ if (n_iterations != 0
+ && ! 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 */
+ (n_iterations * increment) + initial_value */
/* The loop exit value of the giv is then
(final_biv_value - extra increments) * mult_val + add_val.
/* Put the final biv value in tem. */
tem = gen_reg_rtx (bl->biv->mode);
- emit_iv_add_mult (increment, GEN_INT (loop_n_iterations),
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
+ emit_iv_add_mult (increment, GEN_INT (n_iterations),
bl->initial_value, tem, insert_before);
/* Subtract off extra increments as we find them. */
}
+/* Look back before LOOP_START for then insn that sets REG and return
+ the equivalent constant if there is a REG_EQUAL note otherwise just
+ the SET_SRC of REG. */
+
+static rtx
+loop_find_equiv_value (loop_start, reg)
+ rtx loop_start;
+ rtx reg;
+{
+ rtx insn, set;
+ rtx ret;
+
+ ret = reg;
+ for (insn = PREV_INSN (loop_start); insn ; insn = PREV_INSN (insn))
+ {
+ if (GET_CODE (insn) == CODE_LABEL)
+ break;
+
+ else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
+ && reg_set_p (reg, insn))
+ {
+ /* 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) == reg))
+ {
+ 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)))
+ ret = XEXP (note, 0);
+ else
+ ret = SET_SRC (set);
+ }
+ break;
+ }
+ }
+ return ret;
+}
+
+
+/* Return a simplified rtx for the expression OP - REG.
+
+ REG must appear in OP, and OP must be a register or the sum of a register
+ and a second term.
+
+ Thus, the return value must be const0_rtx or the second term.
+
+ The caller is responsible for verifying that REG appears in OP and OP has
+ the proper form. */
+
+static rtx
+subtract_reg_term (op, reg)
+ rtx op, reg;
+{
+ if (op == reg)
+ return const0_rtx;
+ if (GET_CODE (op) == PLUS)
+ {
+ if (XEXP (op, 0) == reg)
+ return XEXP (op, 1);
+ else if (XEXP (op, 1) == reg)
+ return XEXP (op, 0);
+ }
+ /* OP does not contain REG as a term. */
+ abort ();
+}
+
+
+/* Find and return register term common to both expressions OP0 and
+ OP1 or NULL_RTX if no such term exists. Each expression must be a
+ REG or a PLUS of a REG. */
+
+static rtx
+find_common_reg_term (op0, op1)
+ rtx op0, op1;
+{
+ if ((GET_CODE (op0) == REG || GET_CODE (op0) == PLUS)
+ && (GET_CODE (op1) == REG || GET_CODE (op1) == PLUS))
+ {
+ rtx op00;
+ rtx op01;
+ rtx op10;
+ rtx op11;
+
+ if (GET_CODE (op0) == PLUS)
+ op01 = XEXP (op0, 1), op00 = XEXP (op0, 0);
+ else
+ op01 = const0_rtx, op00 = op0;
+
+ if (GET_CODE (op1) == PLUS)
+ op11 = XEXP (op1, 1), op10 = XEXP (op1, 0);
+ else
+ op11 = const0_rtx, op10 = op1;
+
+ /* Find and return common register term if present. */
+ if (REG_P (op00) && (op00 == op10 || op00 == op11))
+ return op00;
+ else if (REG_P (op01) && (op01 == op10 || op01 == op11))
+ return op01;
+ }
+
+ /* No common register term found. */
+ return NULL_RTX;
+}
+
+
/* Calculate the number of loop iterations. Returns the exact number of loop
iterations if it can be calculated, otherwise returns zero. */
unsigned HOST_WIDE_INT
-loop_iterations (loop_start, loop_end)
+loop_iterations (loop_start, loop_end, loop_info)
rtx loop_start, loop_end;
+ struct loop_info *loop_info;
{
rtx comparison, comparison_value;
rtx iteration_var, initial_value, increment, final_value;
enum rtx_code comparison_code;
- HOST_WIDE_INT i;
+ HOST_WIDE_INT abs_inc;
+ unsigned HOST_WIDE_INT abs_diff;
+ int off_by_one;
int increment_dir;
- int unsigned_compare, compare_dir, final_larger;
- unsigned long tempu;
+ int unsigned_p, compare_dir, final_larger;
rtx last_loop_insn;
+ rtx vtop;
+ rtx reg_term;
+
+ loop_info->n_iterations = 0;
+ loop_info->initial_value = 0;
+ loop_info->initial_equiv_value = 0;
+ loop_info->comparison_value = 0;
+ loop_info->final_value = 0;
+ loop_info->final_equiv_value = 0;
+ loop_info->increment = 0;
+ loop_info->iteration_var = 0;
+ loop_info->unroll_number = 1;
+ loop_info->vtop = 0;
/* First find the iteration variable. If the last insn is a conditional
branch, and the insn before tests a register value, make that the
iteration variable. */
- loop_initial_value = 0;
- loop_increment = 0;
- loop_final_value = 0;
- loop_iteration_var = 0;
-
- last_loop_insn = prev_nonnote_insn (loop_end);
+ /* We used to use prev_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)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "Loop unrolling: No final conditional branch found.\n");
+ "Loop iterations: No final conditional branch found.\n");
return 0;
}
comparison_code = GET_CODE (comparison);
iteration_var = XEXP (comparison, 0);
comparison_value = XEXP (comparison, 1);
+
+ /* Check if there is a NOTE_INSN_LOOP_VTOP note. If there is,
+ that means that this is a for or while style loop, with
+ a loop exit test at the start. Thus, we can assume that
+ the loop condition was true when the loop was entered.
+
+ We start at the end and search backwards for the previous
+ NOTE. If there is no NOTE_INSN_LOOP_VTOP for this loop,
+ the search will stop at the NOTE_INSN_LOOP_CONT. */
+ vtop = loop_end;
+ do
+ vtop = PREV_INSN (vtop);
+ while (GET_CODE (vtop) != NOTE
+ || NOTE_LINE_NUMBER (vtop) > 0
+ || NOTE_LINE_NUMBER (vtop) == NOTE_REPEATED_LINE_NUMBER
+ || NOTE_LINE_NUMBER (vtop) == NOTE_INSN_DELETED);
+ if (NOTE_LINE_NUMBER (vtop) != NOTE_INSN_LOOP_VTOP)
+ vtop = NULL_RTX;
+ loop_info->vtop = vtop;
if (GET_CODE (iteration_var) != REG)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "Loop unrolling: Comparison not against register.\n");
+ "Loop iterations: Comparison not against register.\n");
return 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)
+ unsigned_p = 0;
+ off_by_one = 0;
+ switch (comparison_code)
{
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Initial value not constant.\n");
- return 0;
+ case LEU:
+ unsigned_p = 1;
+ case LE:
+ compare_dir = 1;
+ off_by_one = 1;
+ break;
+ case GEU:
+ unsigned_p = 1;
+ case GE:
+ compare_dir = -1;
+ off_by_one = -1;
+ break;
+ case EQ:
+ /* Cannot determine loop iterations with this case. */
+ compare_dir = 0;
+ break;
+ case LTU:
+ unsigned_p = 1;
+ case LT:
+ compare_dir = 1;
+ break;
+ case GTU:
+ unsigned_p = 1;
+ case GT:
+ compare_dir = -1;
+ case NE:
+ compare_dir = 0;
+ break;
+ default:
+ abort ();
}
/* If the comparison value is an invariant register, then try to find
its value from the insns before the start of the loop. */
+ final_value = comparison_value;
if (GET_CODE (comparison_value) == REG && invariant_p (comparison_value))
{
- rtx insn, set;
-
- for (insn = PREV_INSN (loop_start); insn ; insn = PREV_INSN (insn))
+ final_value = loop_find_equiv_value (loop_start, comparison_value);
+ /* If we don't get an invariant final value, we are better
+ off with the original register. */
+ if (!invariant_p (final_value))
+ final_value = comparison_value;
+ }
+
+ /* Calculate the approximate final value of the induction variable
+ (on the last successful iteration). The exact final value
+ depends on the branch operator, and increment sign. It will be
+ wrong if the iteration variable is not incremented by one each
+ time through the loop and (comparison_value + off_by_one -
+ initial_value) % increment != 0.
+ ??? Note that the final_value may overflow and thus final_larger
+ will be bogus. A potentially infinite loop will be classified
+ as immediate, e.g. for (i = 0x7ffffff0; i <= 0x7fffffff; i++) */
+ if (off_by_one)
+ final_value = plus_constant (final_value, off_by_one);
+
+ /* Save the calculated values describing this loop's bounds, in case
+ precondition_loop_p will need them later. These values can not be
+ recalculated inside precondition_loop_p because strength reduction
+ optimizations may obscure the loop's structure.
+
+ These values are only required by precondition_loop_p and insert_bct
+ whenever the number of iterations cannot be computed at compile time.
+ Only the difference between final_value and initial_value is
+ important. Note that final_value is only approximate. */
+ loop_info->initial_value = initial_value;
+ loop_info->comparison_value = comparison_value;
+ loop_info->final_value = plus_constant (comparison_value, off_by_one);
+ loop_info->increment = increment;
+ loop_info->iteration_var = iteration_var;
+ loop_info->comparison_code = comparison_code;
+
+ /* Try to determine the iteration count for loops such
+ as (for i = init; i < init + const; i++). When running the
+ loop optimization twice, the first pass often converts simple
+ loops into this form. */
+
+ if (REG_P (initial_value))
+ {
+ rtx reg1;
+ rtx reg2;
+ rtx const2;
+
+ reg1 = initial_value;
+ if (GET_CODE (final_value) == PLUS)
+ reg2 = XEXP (final_value, 0), const2 = XEXP (final_value, 1);
+ else
+ reg2 = final_value, const2 = const0_rtx;
+
+ /* Check for initial_value = reg1, final_value = reg2 + const2,
+ where reg1 != reg2. */
+ if (REG_P (reg2) && reg2 != reg1)
{
- if (GET_CODE (insn) == CODE_LABEL)
- break;
+ rtx temp;
- else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
- && reg_set_p (comparison_value, insn))
+ /* Find what reg1 is equivalent to. Hopefully it will
+ either be reg2 or reg2 plus a constant. */
+ temp = loop_find_equiv_value (loop_start, reg1);
+ if (find_common_reg_term (temp, reg2))
+ initial_value = temp;
+ else
{
- /* 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);
+ /* Find what reg2 is equivalent to. Hopefully it will
+ either be reg1 or reg1 plus a constant. Let's ignore
+ the latter case for now since it is not so common. */
+ temp = loop_find_equiv_value (loop_start, reg2);
+ if (temp == loop_info->iteration_var)
+ temp = initial_value;
+ if (temp == reg1)
+ final_value = (const2 == const0_rtx)
+ ? reg1 : gen_rtx_PLUS (GET_MODE (reg1), reg1, const2);
+ }
+ }
+ else if (loop_info->vtop && GET_CODE (reg2) == CONST_INT)
+ {
+ rtx temp;
- if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
- comparison_value = XEXP (note, 0);
- }
- break;
+ /* When running the loop optimizer twice, check_dbra_loop
+ further obfuscates reversible loops of the form:
+ for (i = init; i < init + const; i++). We often end up with
+ final_value = 0, initial_value = temp, temp = temp2 - init,
+ where temp2 = init + const. If the loop has a vtop we
+ can replace initial_value with const. */
+
+ temp = loop_find_equiv_value (loop_start, reg1);
+ if (GET_CODE (temp) == MINUS && REG_P (XEXP (temp, 0)))
+ {
+ rtx temp2 = loop_find_equiv_value (loop_start, XEXP (temp, 0));
+ if (GET_CODE (temp2) == PLUS
+ && XEXP (temp2, 0) == XEXP (temp, 1))
+ initial_value = XEXP (temp2, 1);
}
}
}
+
+ /* If have initial_value = reg + const1 and final_value = reg +
+ const2, then replace initial_value with const1 and final_value
+ with const2. This should be safe since we are protected by the
+ initial comparison before entering the loop if we have a vtop.
+ For example, a + b < a + c is not equivalent to b < c for all a
+ when using modulo arithmetic.
+
+ ??? Without a vtop we could still perform the optimization if we check
+ the initial and final values carefully. */
+ if (loop_info->vtop
+ && (reg_term = find_common_reg_term (initial_value, final_value)))
+ {
+ initial_value = subtract_reg_term (initial_value, reg_term);
+ final_value = subtract_reg_term (final_value, reg_term);
+ }
- final_value = approx_final_value (comparison_code, comparison_value,
- &unsigned_compare, &compare_dir);
+ loop_info->initial_equiv_value = initial_value;
+ loop_info->final_equiv_value = final_value;
+
+ if (increment == 0)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Increment value can't be calculated.\n");
+ return 0;
+ }
- /* Save the calculated values describing this loop's bounds, in case
- precondition_loop_p will need them later. These values can not be
- recalculated inside precondition_loop_p because strength reduction
- optimizations may obscure the loop's structure. */
+ if (GET_CODE (increment) != CONST_INT)
+ {
+ increment = loop_find_equiv_value (loop_start, increment);
- loop_iteration_var = iteration_var;
- loop_initial_value = initial_value;
- loop_increment = increment;
- loop_final_value = final_value;
+ if (GET_CODE (increment) != CONST_INT)
+ {
+ if (loop_dump_stream)
+ {
+ fprintf (loop_dump_stream,
+ "Loop iterations: Increment value not constant ");
+ print_rtl (loop_dump_stream, increment);
+ fprintf (loop_dump_stream, ".\n");
+ }
+ return 0;
+ }
+ loop_info->increment = increment;
+ }
- if (final_value == 0)
+ if (GET_CODE (initial_value) != CONST_INT)
+ {
+ if (loop_dump_stream)
+ {
+ fprintf (loop_dump_stream,
+ "Loop iterations: Initial value not constant ");
+ print_rtl (loop_dump_stream, initial_value);
+ fprintf (loop_dump_stream, ".\n");
+ }
+ return 0;
+ }
+ else if (comparison_code == EQ)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "Loop unrolling: EQ comparison loop.\n");
+ "Loop iterations: EQ comparison loop.\n");
return 0;
}
else if (GET_CODE (final_value) != CONST_INT)
{
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Final value not constant.\n");
+ {
+ fprintf (loop_dump_stream,
+ "Loop iterations: Final value not constant ");
+ print_rtl (loop_dump_stream, final_value);
+ fprintf (loop_dump_stream, ".\n");
+ }
return 0;
}
- /* ?? Final value and initial value do not have to be constants.
- Only their difference has to be constant. When the iteration variable
- is an array address, the final value and initial value might both
- be addresses with the same base but different constant offsets.
- Final value must be invariant for this to work.
-
- To do this, need some way to find the values of registers which are
- invariant. */
-
/* Final_larger is 1 if final larger, 0 if they are equal, otherwise -1. */
- if (unsigned_compare)
+ if (unsigned_p)
final_larger
= ((unsigned HOST_WIDE_INT) INTVAL (final_value)
> (unsigned HOST_WIDE_INT) INTVAL (initial_value))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "Loop unrolling: Not normal loop.\n");
+ "Loop iterations: Not normal loop.\n");
return 0;
}
/* Calculate the number of iterations, final_value is only an approximation,
- so correct for that. Note that tempu and loop_n_iterations are
+ so correct for that. Note that abs_diff and n_iterations are
unsigned, because they can be as large as 2^n - 1. */
- i = INTVAL (increment);
- if (i > 0)
- tempu = INTVAL (final_value) - INTVAL (initial_value);
- else if (i < 0)
+ abs_inc = INTVAL (increment);
+ if (abs_inc > 0)
+ abs_diff = INTVAL (final_value) - INTVAL (initial_value);
+ else if (abs_inc < 0)
{
- tempu = INTVAL (initial_value) - INTVAL (final_value);
- i = -i;
+ abs_diff = INTVAL (initial_value) - INTVAL (final_value);
+ abs_inc = -abs_inc;
}
else
abort ();
- /* For NE tests, make sure that the iteration variable won't miss the
- final value. If tempu mod i is not zero, then the iteration variable
- will overflow before the loop exits, and we can not calculate the
- number of iterations. */
- if (compare_dir == 0 && (tempu % i) != 0)
+ /* For NE tests, make sure that the iteration variable won't miss
+ the final value. If abs_diff mod abs_incr is not zero, then the
+ iteration variable will overflow before the loop exits, and we
+ can not calculate the number of iterations. */
+ if (compare_dir == 0 && (abs_diff % abs_inc) != 0)
+ return 0;
+
+ /* Note that the number of iterations could be calculated using
+ (abs_diff + abs_inc - 1) / abs_inc, provided care was taken to
+ handle potential overflow of the summation. */
+ loop_info->n_iterations = abs_diff / abs_inc + ((abs_diff % abs_inc) != 0);
+ return loop_info->n_iterations;
+}
+
+
+/* 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;
- return tempu / i + ((tempu % i) != 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;
}
projects / gcc.git / blobdiff