/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992, 1993, 1994, 1995, 1997, 1998, 1999, 2000, 2001
+ Copyright (C) 1992, 1993, 1994, 1995, 1997, 1998, 1999, 2000, 2001, 2002
Free Software Foundation, Inc.
Contributed by James E. Wilson, Cygnus Support/UC Berkeley.
moving the insn back into the loop, or perhaps replicate the insn before
the loop, one copy for each time the loop is unrolled. */
+#include "config.h"
+#include "system.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "insn-config.h"
+#include "integrate.h"
+#include "regs.h"
+#include "recog.h"
+#include "flags.h"
+#include "function.h"
+#include "expr.h"
+#include "loop.h"
+#include "toplev.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "predict.h"
+
/* The prime factors looked for when trying to unroll a loop by some
number which is modulo the total number of iterations. Just checking
for these 4 prime factors will find at least one factor for 75% of
#define NUM_FACTORS 4
-struct _factor { int factor, count; }
+static struct _factor { const int factor; int count; }
factors[NUM_FACTORS] = { {2, 0}, {3, 0}, {5, 0}, {7, 0}};
/* Describes the different types of loop unrolling performed. */
UNROLL_NAIVE
};
-#include "config.h"
-#include "system.h"
-#include "rtl.h"
-#include "tm_p.h"
-#include "insn-config.h"
-#include "integrate.h"
-#include "regs.h"
-#include "recog.h"
-#include "flags.h"
-#include "function.h"
-#include "expr.h"
-#include "loop.h"
-#include "toplev.h"
-#include "hard-reg-set.h"
-#include "basic-block.h"
-#include "predict.h"
-
/* This controls which loops are unrolled, and by how much we unroll
them. */
rtx diff;
rtx *labels;
int abs_inc, neg_inc;
+ enum rtx_code cc = loop_info->comparison_code;
+ int less_p = (cc == LE || cc == LEU || cc == LT || cc == LTU);
+ int unsigned_p = (cc == LEU || cc == GEU || cc == LTU || cc == GTU);
map->reg_map = (rtx *) xmalloc (maxregnum * sizeof (rtx));
start_sequence ();
+ /* Final value may have form of (PLUS val1 const1_rtx). We need
+ to convert it into general operand, so compute the real value. */
+
+ if (GET_CODE (final_value) == PLUS)
+ {
+ final_value = expand_simple_binop (mode, PLUS,
+ copy_rtx (XEXP (final_value, 0)),
+ copy_rtx (XEXP (final_value, 1)),
+ NULL_RTX, 0, OPTAB_LIB_WIDEN);
+ }
+ if (!nonmemory_operand (final_value, VOIDmode))
+ final_value = force_reg (mode, copy_rtx (final_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
a constant.
We must copy the final and initial values here to avoid
- improperly shared rtl. */
-
- diff = expand_simple_binop (mode, MINUS, copy_rtx (final_value),
- copy_rtx (initial_value), NULL_RTX, 0,
- OPTAB_LIB_WIDEN);
+ improperly shared rtl.
+
+ We have to deal with for (i = 0; --i < 6;) type loops.
+ For such loops the real final value is the first time the
+ loop variable overflows, so the diff we calculate is the
+ distance from the overflow value. This is 0 or ~0 for
+ unsigned loops depending on the direction, or INT_MAX,
+ INT_MAX+1 for signed loops. We really do not need the
+ exact value, since we are only interested in the diff
+ modulo the increment, and the increment is a power of 2,
+ so we can pretend that the overflow value is 0/~0. */
+
+ if (cc == NE || less_p != neg_inc)
+ diff = expand_simple_binop (mode, MINUS, final_value,
+ copy_rtx (initial_value), NULL_RTX, 0,
+ OPTAB_LIB_WIDEN);
+ else
+ diff = expand_simple_unop (mode, neg_inc ? NOT : NEG,
+ copy_rtx (initial_value), NULL_RTX, 0);
/* Now calculate (diff % (unroll * abs (increment))) by using an
and instruction. */
case. This check does not apply if the loop has a NE
comparison at the end. */
- if (loop_info->comparison_code != NE)
+ if (cc != NE)
{
- emit_cmp_and_jump_insns (initial_value, final_value,
- neg_inc ? LE : GE,
- NULL_RTX, mode, 0, labels[1]);
+ rtx incremented_initval;
+ incremented_initval = expand_simple_binop (mode, PLUS,
+ initial_value,
+ increment,
+ NULL_RTX, 0,
+ OPTAB_LIB_WIDEN);
+ emit_cmp_and_jump_insns (incremented_initval, final_value,
+ less_p ? GE : LE, NULL_RTX,
+ mode, unsigned_p, labels[1]);
predict_insn_def (get_last_insn (), PRED_LOOP_CONDITION,
- NOT_TAKEN);
+ TAKEN);
JUMP_LABEL (get_last_insn ()) = labels[1];
LABEL_NUSES (labels[1])++;
}
if (loop_info->n_iterations > 0)
{
- *initial_value = const0_rtx;
- *increment = const1_rtx;
- *final_value = GEN_INT (loop_info->n_iterations);
+ if (INTVAL (loop_info->increment) > 0)
+ {
+ *initial_value = const0_rtx;
+ *increment = const1_rtx;
+ *final_value = GEN_INT (loop_info->n_iterations);
+ }
+ else
+ {
+ *initial_value = GEN_INT (loop_info->n_iterations);
+ *increment = constm1_rtx;
+ *final_value = const0_rtx;
+ }
*mode = word_mode;
if (loop_dump_stream)
{
rtx insn = map->insn_map[INSN_UID (XEXP (note, 0))];
- /* If we failed to remap the note, something is awry. */
+ /* If we failed to remap the note, something is awry.
+ Allow REG_LABEL as it may reference label outside
+ the unrolled loop. */
if (!insn)
- abort ();
-
- XEXP (note, 0) = insn;
+ {
+ if (REG_NOTE_KIND (note) != REG_LABEL)
+ abort ();
+ }
+ else
+ XEXP (note, 0) = insn;
}
}
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)
+ if (JUMP_LABEL (insn))
{
- /* Update JUMP_LABEL make invert_jump work correctly. */
JUMP_LABEL (copy) = get_label_from_map (map,
CODE_LABEL_NUMBER
(JUMP_LABEL (insn)));
LABEL_NUSES (JUMP_LABEL (copy))++;
+ }
+ if (JUMP_LABEL (insn) == start_label && insn == copy_end
+ && ! last_iteration)
+ {
/* This is a branch to the beginning of the loop; this is the
last insn being copied; and this is not the last iteration.
do
{
- if (GET_CODE (temp) == JUMP_INSN
- /* Previous unrolling may have generated new insns not covered
- by the uid_luid array. */
- && INSN_UID (JUMP_LABEL (temp)) < max_uid_for_loop
- /* Check if we jump back into the loop body. */
- && INSN_LUID (JUMP_LABEL (temp)) > INSN_LUID (loop->top)
- && INSN_LUID (JUMP_LABEL (temp)) < INSN_LUID (loop->cont))
+ if (GET_CODE (temp) == JUMP_INSN)
{
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop iterations: Loop has multiple back edges.\n");
- return 0;
+ /* There are some kinds of jumps we can't deal with easily. */
+ if (JUMP_LABEL (temp) == 0)
+ {
+ if (loop_dump_stream)
+ fprintf
+ (loop_dump_stream,
+ "Loop iterations: Jump insn has null JUMP_LABEL.\n");
+ return 0;
+ }
+
+ if (/* Previous unrolling may have generated new insns not
+ covered by the uid_luid array. */
+ INSN_UID (JUMP_LABEL (temp)) < max_uid_for_loop
+ /* Check if we jump back into the loop body. */
+ && INSN_LUID (JUMP_LABEL (temp)) > INSN_LUID (loop->top)
+ && INSN_LUID (JUMP_LABEL (temp)) < INSN_LUID (loop->cont))
+ {
+ if (loop_dump_stream)
+ fprintf
+ (loop_dump_stream,
+ "Loop iterations: Loop has multiple back edges.\n");
+ return 0;
+ }
}
}
while ((temp = PREV_INSN (temp)) != loop->cont);
if (initial_value == 0)
return 0;
- /* Some code transformations can result in code akin to
-
- tmp = i + 1;
- ...
- goto scan_start;
- top:
- tmp = tmp + 1;
- scan_start:
- i = tmp;
- if (i < n) goto top;
-
- We'll have already detected this form of loop in scan_loop,
- and set loop->top and loop->scan_start appropriately.
-
- In this situation, we skip the increment the first time through
- the loop, which results in an incorrect estimate of the number
- of iterations. Adjust the initial value to compensate. */
-
- if (loop->scan_start && loop->cont
- && INSN_LUID (loop->scan_start) < INSN_LUID (loop->cont)
- && INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop iterations: Basic induction var skips initial incr.\n");
- if (GET_CODE (increment) != CONST_INT)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop iterations: Can't adjust with non-constant incr.\n");
- return 0;
- }
- initial_value = plus_constant (initial_value, -INTVAL (increment));
- }
-
unsigned_p = 0;
off_by_one = 0;
switch (comparison_code)
not HOST_WIDE_INT, disregard higher bits that might have come
into the picture due to sign extension of initial and final
values. */
- abs_diff &= ((unsigned HOST_WIDE_INT)1
+ abs_diff &= ((unsigned HOST_WIDE_INT) 1
<< (GET_MODE_BITSIZE (GET_MODE (iteration_var)) - 1)
<< 1) - 1;
OSDN Git Service
