/* 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"
+#include "params.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. */
-
-#ifndef MAX_UNROLLED_INSNS
-#define MAX_UNROLLED_INSNS 100
-#endif
-
/* Indexed by register number, if non-zero, then it contains a pointer
to a struct induction for a DEST_REG giv which has been combined with
one of more address givs. This is needed because whenever such a DEST_REG
if (max_labelno > 0)
{
- map->label_map = (rtx *) xmalloc (max_labelno * sizeof (rtx));
-
+ map->label_map = (rtx *) xcalloc (max_labelno, sizeof (rtx));
local_label = (char *) xcalloc (max_labelno, sizeof (char));
}
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 second_part = XEXP (increment, 1);
enum rtx_code code = GET_CODE (increment);
- increment = find_last_value (XEXP (increment, 0),
+ increment = find_last_value (XEXP (increment, 0),
&src_insn, NULL_RTX, 0);
/* Don't need the last insn anymore. */
delete_related_insns (get_last_insn ());
while (*notesp)
{
rtx note = *notesp;
-
+
if (GET_CODE (note) == INSN_LIST)
{
/* Sometimes, we have a REG_WAS_0 note that points to a
{
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.
that. */
jmp = emit_jump_insn_after (gen_jump (exit_label), copy);
JUMP_LABEL (jmp) = exit_label;
+ LABEL_NUSES (exit_label)++;
jmp = emit_barrier_after (jmp);
emit_label_after (lab, jmp);
LABEL_NUSES (lab) = 0;
pattern = copy_rtx_and_substitute (PATTERN (insn), map, 0);
copy = emit_call_insn (pattern);
REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
+ SIBLING_CALL_P (copy) = SIBLING_CALL_P (insn);
/* Because the USAGE information potentially contains objects other
than hard registers, we need to copy it. */
rtx tem = gen_reg_rtx (bl->biv->mode);
record_base_value (REGNO (tem), bl->biv->add_val, 0);
- loop_insn_hoist (loop,
+ loop_insn_hoist (loop,
gen_move_insn (tem, bl->biv->src_reg));
if (loop_dump_stream)
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);
for (biv_inc = bl->biv; biv_inc; biv_inc = biv_inc->next_iv)
{
if (loop_insn_first_p (v->insn, biv_inc->insn))
- offset -= INTVAL (biv_inc->add_val);
+ {
+ if (REG_P (biv_inc->add_val))
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Basic induction var add_val is REG %d.\n",
+ REGNO (biv_inc->add_val));
+ return 0;
+ }
+
+ offset -= INTVAL (biv_inc->add_val);
+ }
}
}
if (loop_dump_stream)
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
