/* 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.
-This file is part of GNU CC.
+This file is part of GCC.
-GNU CC is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
-any later version.
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
-GNU CC is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
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, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
/* Try to unroll a loop, and split induction variables.
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 "optabs.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 ujump = ujump_to_loop_cont (loop->start, loop->cont);
if (ujump)
- delete_insn (ujump);
+ delete_related_insns (ujump);
/* 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.
if (GET_CODE (last_loop_insn) == BARRIER)
{
/* Delete the jump insn. This will delete the barrier also. */
- delete_insn (PREV_INSN (last_loop_insn));
+ delete_related_insns (PREV_INSN (last_loop_insn));
}
else if (GET_CODE (last_loop_insn) == JUMP_INSN)
{
#ifdef HAVE_cc0
rtx prev = PREV_INSN (last_loop_insn);
#endif
- delete_insn (last_loop_insn);
+ delete_related_insns (last_loop_insn);
#ifdef HAVE_cc0
/* The immediately preceding insn may be a compare which must be
deleted. */
- if (sets_cc0_p (prev))
- delete_insn (prev);
+ if (only_sets_cc0_p (prev))
+ delete_related_insns (prev);
#endif
}
/* Remove the loop notes since this is no longer a loop. */
if (loop->vtop)
- delete_insn (loop->vtop);
+ delete_related_insns (loop->vtop);
if (loop->cont)
- delete_insn (loop->cont);
+ delete_related_insns (loop->cont);
if (loop_start)
- delete_insn (loop_start);
+ delete_related_insns (loop_start);
if (loop_end)
- delete_insn (loop_end);
+ delete_related_insns (loop_end);
return;
}
&initial_value, &final_value, &increment,
&mode))
{
- register rtx diff;
+ 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_binop (mode, sub_optab, 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. */
- diff = expand_binop (GET_MODE (diff), and_optab, diff,
- GEN_INT (unroll_number * abs_inc - 1),
- NULL_RTX, 0, OPTAB_LIB_WIDEN);
+ diff = expand_simple_binop (GET_MODE (diff), AND, diff,
+ GEN_INT (unroll_number * abs_inc - 1),
+ NULL_RTX, 0, OPTAB_LIB_WIDEN);
/* Now emit a sequence of branches to jump to the proper precond
loop entry point. */
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, 0, labels[1]);
- predict_insn_def (get_last_insn (), PRED_LOOP_CONDITION, NOT_TAKEN);
+ 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,
+ TAKEN);
JUMP_LABEL (get_last_insn ()) = labels[1];
LABEL_NUSES (labels[1])++;
}
}
emit_cmp_and_jump_insns (diff, GEN_INT (abs_inc * cmp_const),
- cmp_code, NULL_RTX, mode, 0, 0,
- labels[i]);
+ cmp_code, NULL_RTX, mode, 0, labels[i]);
JUMP_LABEL (get_last_insn ()) = labels[i];
LABEL_NUSES (labels[i])++;
predict_insn (get_last_insn (), PRED_LOOP_PRECONDITIONING,
}
emit_cmp_and_jump_insns (diff, GEN_INT (cmp_const), cmp_code,
- NULL_RTX, mode, 0, 0, labels[0]);
+ NULL_RTX, mode, 0, labels[0]);
JUMP_LABEL (get_last_insn ()) = labels[0];
LABEL_NUSES (labels[0])++;
}
&& ! (GET_CODE (insn) == CODE_LABEL && LABEL_NAME (insn))
&& ! (GET_CODE (insn) == NOTE
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED_LABEL))
- insn = delete_insn (insn);
+ insn = delete_related_insns (insn);
else
insn = NEXT_INSN (insn);
}
/* Can now delete the 'safety' label emitted to protect us from runaway
- delete_insn calls. */
+ delete_related_insns calls. */
if (INSN_DELETED_P (safety_label))
abort ();
- delete_insn (safety_label);
+ delete_related_insns (safety_label);
/* If exit_label exists, emit it after the loop. Doing the emit here
forces it to have a higher INSN_UID than any insn in the unrolled loop.
{
/* Remove the loop notes since this is no longer a loop. */
if (loop->vtop)
- delete_insn (loop->vtop);
+ delete_related_insns (loop->vtop);
if (loop->cont)
- delete_insn (loop->cont);
+ delete_related_insns (loop->cont);
if (loop_start)
- delete_insn (loop_start);
+ delete_related_insns (loop_start);
if (loop_end)
- delete_insn (loop_end);
+ delete_related_insns (loop_end);
}
if (map->const_equiv_varray)
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)
/* SR sometimes computes the new giv value in a temp, then copies it
to the new_reg. */
src_insn = PREV_INSN (src_insn);
- pattern = PATTERN (src_insn);
+ pattern = single_set (src_insn);
if (GET_CODE (SET_SRC (pattern)) != PLUS)
abort ();
/* The last insn emitted is not needed, so delete it to avoid confusing
the second cse pass. This insn sets the giv unnecessarily. */
- delete_insn (get_last_insn ());
+ delete_related_insns (get_last_insn ());
}
/* Verify that we have a constant as the second operand of the plus. */
{
/* SR sometimes puts the constant in a register, especially if it is
too big to be an add immed operand. */
- src_insn = PREV_INSN (src_insn);
- increment = SET_SRC (PATTERN (src_insn));
+ increment = find_last_value (increment, &src_insn, NULL_RTX, 0);
/* 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
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));
+ increment = find_last_value (XEXP (increment, 0),
+ &src_insn, NULL_RTX, 0);
/* Don't need the last insn anymore. */
- delete_insn (get_last_insn ());
+ delete_related_insns (get_last_insn ());
if (GET_CODE (second_part) != CONST_INT
|| GET_CODE (increment) != CONST_INT)
/* The insn loading the constant into a register is no longer needed,
so delete it. */
- delete_insn (get_last_insn ());
+ delete_related_insns (get_last_insn ());
}
if (increment_total)
tries++;
src_insn = PREV_INSN (src_insn);
- pattern = PATTERN (src_insn);
+ pattern = single_set (src_insn);
- delete_insn (get_last_insn ());
+ delete_related_insns (get_last_insn ());
goto retry;
}
{
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.
jump_insn after COPY, and redirect the jump around
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;
{
#ifdef HAVE_cc0
/* If the previous insn set cc0 for us, delete it. */
- if (sets_cc0_p (PREV_INSN (copy)))
- delete_insn (PREV_INSN (copy));
+ if (only_sets_cc0_p (PREV_INSN (copy)))
+ delete_related_insns (PREV_INSN (copy));
#endif
/* 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
{
rtx result;
- result = expand_binop (GET_MODE (dest_reg), add_optab, src_reg, increment,
- dest_reg, 0, OPTAB_LIB_WIDEN);
+ result = expand_simple_binop (GET_MODE (dest_reg), PLUS, src_reg, increment,
+ dest_reg, 0, OPTAB_LIB_WIDEN);
if (dest_reg != result)
emit_move_insn (dest_reg, result);
/* 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. */
- delete_insn (PREV_INSN (loop->start));
+ delete_related_insns (PREV_INSN (loop->start));
start_sequence ();
ret = force_operand (v->new_reg, tem);
if (biv->insn == insn)
{
start_sequence ();
- tem = expand_binop (GET_MODE (tem), sub_optab, tem,
- biv->add_val, NULL_RTX, 0,
- OPTAB_LIB_WIDEN);
+ tem = expand_simple_binop (GET_MODE (tem), MINUS, tem,
+ biv->add_val, NULL_RTX, 0,
+ OPTAB_LIB_WIDEN);
seq = gen_sequence ();
end_sequence ();
loop_insn_sink (loop, seq);
return 0;
}
-/* Look back before LOOP->START for then insn that sets REG and return
+/* Look back before LOOP->START for the insn that sets REG and return
the equivalent constant if there is a REG_EQUAL note otherwise just
the SET_SRC of REG. */
return 0;
}
+ /* If there are multiple conditionalized loop exit tests, they may jump
+ back to differing CODE_LABELs. */
+ if (loop->top && loop->cont)
+ {
+ rtx temp = PREV_INSN (last_loop_insn);
+
+ do
+ {
+ if (GET_CODE (temp) == JUMP_INSN)
+ {
+ /* 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);
+ }
+
/* 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. */
increment = fold_rtx_mult_add (v->mult_val,
extend_value_for_giv (v, increment),
const0_rtx, v->mode);
- /* The caller assumes that one full increment has occured at the
+ /* The caller assumes that one full increment has occurred at the
first loop test. But that's not true when the biv is incremented
after the giv is set (which is the usual case), e.g.:
i = 6; do {;} while (i++ < 9) .
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;
rtx x;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
- register enum rtx_code code;
- register int i;
- register const char *fmt;
+ enum rtx_code code;
+ int i;
+ const char *fmt;
if (x == 0)
return x;
XEXP (x, i) = remap_split_bivs (loop, XEXP (x, i));
else if (fmt[i] == 'E')
{
- register int j;
+ int j;
for (j = 0; j < XVECLEN (x, i); j++)
XVECEXP (x, i, j) = remap_split_bivs (loop, XVECEXP (x, i, j));
}
OSDN Git Service
