/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992, 93, 94, 95, 97, 1998 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.
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;
-static enum rtx_code loop_comparison_code;
-
/* Forward declarations. */
static void init_reg_map PROTO((struct inline_remap *, int));
-static int precondition_loop_p PROTO((rtx *, 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,
+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));
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;
/* 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)
+ 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_n_iterations);
+ fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
+ loop_info->n_iterations);
fputs (" iterations.\n", loop_dump_stream);
}
/* 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)
}
}
}
- else if (note = find_reg_note (insn, REG_LABEL, NULL_RTX))
+ 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));
}
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 ;
- enum machine_mode mode;
rtx *labels;
int abs_inc, neg_inc;
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
case. This check does not apply if the loop has a NE
comparison at the end. */
- if (loop_comparison_code != NE)
+ if (loop_info->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]));
+ 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])++;
}
cmp_code = LE;
}
- emit_cmp_insn (diff, GEN_INT (abs_inc * cmp_const),
- cmp_code, NULL_RTX, mode, 0, 0);
-
- 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])++;
}
cmp_code = GE;
}
- emit_cmp_insn (diff, GEN_INT (cmp_const), cmp_code, NULL_RTX,
- mode, 0, 0);
-
- 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])++;
}
/* Set unroll type to MODULO now. */
unroll_type = UNROLL_MODULO;
loop_preconditioned = 1;
-
-#ifdef HAIFA
- /* Fix the initial value for the loop as needed. */
- if (loop_n_iterations <= 0)
- loop_start_value [uid_loop_num [INSN_UID (loop_start)]]
- = initial_value;
-#endif
}
}
/* At this point, we are guaranteed to unroll the loop. */
- /* Keep track of the unroll factor for each loop. */
+ /* Keep track of the unroll factor for the loop. */
if (unroll_type == UNROLL_COMPLETELY)
- loop_unroll_factor [uid_loop_num [INSN_UID (loop_start)]] = -1;
+ loop_info->unroll_number = -1;
else
- loop_unroll_factor [uid_loop_num [INSN_UID (loop_start)]] = unroll_number;
+ loop_info->unroll_number = unroll_number;
/* For each biv and giv, determine whether it can be safely split into
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
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. */
/* ??? 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. */
+ 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. */
-static int
-precondition_loop_p (initial_value, final_value, increment, loop_start,
- loop_end)
+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;
{
- 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)
{
fputs ("Preconditioning: Success, number of iterations known, ",
loop_dump_stream);
fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
- loop_n_iterations);
+ 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)
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;
Initial_value and/or increment are set to zero if their values could not
be calculated. */
-void
+static void
iteration_info (iteration_var, initial_value, increment, loop_start, loop_end)
rtx iteration_var, *initial_value, *increment;
rtx loop_start, loop_end;
/* 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 HOST_WIDE_INT' variable loop_n_iterations. */
+ `unsigned HOST_WIDE_INT' variable loop_info->n_iterations. */
else if ((GET_MODE_BITSIZE (GET_MODE (iteration_var))
> HOST_BITS_PER_WIDE_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
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;
|| (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
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))
-
+ && 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;
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
+ if (n_iterations != 0
&& ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
&& invariant_p (bl->initial_value))
{
/* 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;
only one exit for this to work, but the loop iterations does not need
to be known. */
- if (loop_n_iterations != 0
+ 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
&& 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);
record_base_value (REGNO (tem), bl->biv->add_val, 0);
- emit_iv_add_mult (increment, GEN_INT (loop_n_iterations),
+ 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;
-
- /* We used to use pren_nonnote_insn here, but that fails because it might
+ /* 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. */
{
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;
+ unsigned_p = 0;
+ off_by_one = 0;
+ switch (comparison_code)
+ {
+ 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);
-
- /* 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;
+ /* 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;
- final_value = approx_final_value (comparison_code, comparison_value,
- &unsigned_compare, &compare_dir);
+ /* 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. */
- /* 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. */
+ 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.
- loop_iteration_var = iteration_var;
- loop_initial_value = initial_value;
- loop_increment = increment;
- loop_final_value = final_value;
- loop_comparison_code = comparison_code;
+ ??? 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);
+ }
+ 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 unrolling: Increment value can't be calculated.\n");
+ "Loop iterations: Increment value can't be calculated.\n");
return 0;
}
- else if (GET_CODE (increment) != CONST_INT)
+
+ if (GET_CODE (increment) != CONST_INT)
{
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Increment value not constant.\n");
- return 0;
+ increment = loop_find_equiv_value (loop_start, increment);
+
+ 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;
}
- else if (GET_CODE (initial_value) != CONST_INT)
+
+ if (GET_CODE (initial_value) != CONST_INT)
{
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Initial value not constant.\n");
+ {
+ 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 (final_value == 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;
- return tempu / i + ((tempu % i) != 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. */
projects / gcc.git / blobdiff