/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992, 1993, 1994, 1995, 1997, 1998, 1999, 2000
+ 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 "loop.h"
-#include "toplev.h"
-#include "hard-reg-set.h"
-#include "basic-block.h"
-
/* This controls which loops are unrolled, and by how much we unroll
them. */
static rtx *splittable_regs;
/* Indexed by register number, if this is a splittable induction variable,
- this indicates if it was made from a derived giv. */
-static char *derived_regs;
-
-/* Indexed by register number, if this is a splittable induction variable,
then this will hold the number of instructions in the loop that modify
the induction variable. Used to ensure that only the last insn modifying
a split iv will update the original iv of the dest. */
static void init_reg_map PARAMS ((struct inline_remap *, int));
static rtx calculate_giv_inc PARAMS ((rtx, rtx, unsigned int));
static rtx initial_reg_note_copy PARAMS ((rtx, struct inline_remap *));
-static void final_reg_note_copy PARAMS ((rtx, struct inline_remap *));
+static void final_reg_note_copy PARAMS ((rtx *, struct inline_remap *));
static void copy_loop_body PARAMS ((struct loop *, rtx, rtx,
struct inline_remap *, rtx, int,
enum unroll_types, rtx, rtx, rtx, rtx));
static int find_splittable_regs PARAMS ((const struct loop *,
- enum unroll_types, rtx, int));
+ enum unroll_types, int));
static int find_splittable_givs PARAMS ((const struct loop *,
struct iv_class *, enum unroll_types,
rtx, int));
/* Try to unroll one loop and split induction variables in the loop.
The loop is described by the arguments LOOP and INSN_COUNT.
- END_INSERT_BEFORE indicates where insns should be added which need
- to be executed when the loop falls through. STRENGTH_REDUCTION_P
- indicates whether information generated in the strength reduction
- pass is available.
+ STRENGTH_REDUCTION_P indicates whether information generated in the
+ strength reduction pass is available.
This function is intended to be called from within `strength_reduce'
in loop.c. */
void
-unroll_loop (loop, insn_count, end_insert_before, strength_reduce_p)
+unroll_loop (loop, insn_count, strength_reduce_p)
struct loop *loop;
int insn_count;
- rtx end_insert_before;
int strength_reduce_p;
{
struct loop_info *loop_info = LOOP_INFO (loop);
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;
}
}
}
}
- else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)))
+ if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)))
set_label_in_map (map, CODE_LABEL_NUMBER (XEXP (note, 0)),
XEXP (note, 0));
}
to access the splittable_regs[] and addr_combined_regs[] arrays. */
splittable_regs = (rtx *) xcalloc (maxregnum, sizeof (rtx));
- derived_regs = (char *) xcalloc (maxregnum, sizeof (char));
splittable_regs_updates = (int *) xcalloc (maxregnum, sizeof (int));
addr_combined_regs
= (struct induction **) xcalloc (maxregnum, sizeof (struct induction *));
these pseudo registers have valid regno_first_uid info. */
for (r = FIRST_PSEUDO_REGISTER; r < max_reg_before_loop; ++r)
if (REGNO_FIRST_UID (r) > 0 && REGNO_FIRST_UID (r) <= max_uid_for_loop
- && uid_luid[REGNO_FIRST_UID (r)] >= copy_start_luid
+ && REGNO_FIRST_LUID (r) >= copy_start_luid
&& REGNO_LAST_UID (r) > 0 && REGNO_LAST_UID (r) <= max_uid_for_loop
- && uid_luid[REGNO_LAST_UID (r)] <= copy_end_luid)
+ && REGNO_LAST_LUID (r) <= 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
r);
}
}
- /* Givs that have been created from multiple biv increments always have
- local registers. */
- for (r = ivs->first_increment_giv; r <= ivs->last_increment_giv; r++)
- {
- local_regno[r] = 1;
- if (loop_dump_stream)
- fprintf (loop_dump_stream, "Marked reg %d as local\n", r);
- }
}
/* If this loop requires exit tests when unrolled, check to see if we
&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]);
+ 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,
+ REG_BR_PROB_BASE / (unroll_number - i));
}
/* If the increment is greater than one, then we need another branch,
}
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])++;
}
sequence = gen_sequence ();
end_sequence ();
- emit_insn_before (sequence, loop_start);
+ loop_insn_hoist (loop, sequence);
/* Only the last copy of the loop body here needs the exit
test, so set copy_end to exclude the compare/branch here,
emit_label_after (labels[unroll_number - i],
PREV_INSN (loop_start));
- bzero ((char *) map->insn_map, max_insnno * sizeof (rtx));
- bzero ((char *) &VARRAY_CONST_EQUIV (map->const_equiv_varray, 0),
- (VARRAY_SIZE (map->const_equiv_varray)
- * sizeof (struct const_equiv_data)));
+ memset ((char *) map->insn_map, 0, max_insnno * sizeof (rtx));
+ memset ((char *) &VARRAY_CONST_EQUIV (map->const_equiv_varray, 0),
+ 0, (VARRAY_SIZE (map->const_equiv_varray)
+ * sizeof (struct const_equiv_data)));
map->const_age = 0;
for (j = 0; j < max_labelno; j++)
if (splitting_not_safe)
temp = 0;
else
- temp = find_splittable_regs (loop, unroll_type,
- end_insert_before, unroll_number);
+ temp = find_splittable_regs (loop, unroll_type, unroll_number);
/* find_splittable_regs may have created some new registers, so must
reallocate the reg_map with the new larger size, and must realloc
/* Search the list of bivs and givs to find ones which need to be remapped
when split, and set their reg_map entry appropriately. */
- for (bl = ivs->loop_iv_list; bl; bl = bl->next)
+ for (bl = ivs->list; bl; bl = bl->next)
{
if (REGNO (bl->biv->src_reg) != bl->regno)
map->reg_map[bl->regno] = bl->biv->src_reg;
}
/* Use our current register alignment and pointer flags. */
- map->regno_pointer_flag = cfun->emit->regno_pointer_flag;
map->regno_pointer_align = cfun->emit->regno_pointer_align;
+ map->x_regno_reg_rtx = cfun->emit->x_regno_reg_rtx;
/* 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
for (i = 0; i < unroll_number; i++)
{
- bzero ((char *) map->insn_map, max_insnno * sizeof (rtx));
- bzero ((char *) &VARRAY_CONST_EQUIV (map->const_equiv_varray, 0),
- VARRAY_SIZE (map->const_equiv_varray) * sizeof (struct const_equiv_data));
+ memset ((char *) map->insn_map, 0, max_insnno * sizeof (rtx));
+ memset ((char *) &VARRAY_CONST_EQUIV (map->const_equiv_varray, 0), 0,
+ VARRAY_SIZE (map->const_equiv_varray) * sizeof (struct const_equiv_data));
map->const_age = 0;
for (j = 0; j < max_labelno; j++)
&& ! (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)
}
free (map->insn_map);
free (splittable_regs);
- free (derived_regs);
free (splittable_regs_updates);
free (addr_combined_regs);
free (local_regno);
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)
return 1;
}
- if (loop_info->initial_value == 0)
+ if (loop_info->iteration_var == 0)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Preconditioning: Could not find iteration variable.\n");
+ return 0;
+ }
+ else if (loop_info->initial_value == 0)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
/* Fail if loop_info->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_info->iteration_var))]
+ if (REGNO_FIRST_LUID (REGNO (loop_info->iteration_var))
> INSN_LUID (loop_start))
{
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;
}
return 0;
copy = rtx_alloc (GET_CODE (notes));
- PUT_MODE (copy, GET_MODE (notes));
+ PUT_REG_NOTE_KIND (copy, REG_NOTE_KIND (notes));
if (GET_CODE (notes) == EXPR_LIST)
XEXP (copy, 0) = copy_rtx_and_substitute (XEXP (notes, 0), map, 0);
else if (GET_CODE (notes) == INSN_LIST)
/* Don't substitute for these yet. */
- XEXP (copy, 0) = XEXP (notes, 0);
+ XEXP (copy, 0) = copy_rtx (XEXP (notes, 0));
else
abort ();
/* Fixup insn references in copied REG_NOTES. */
static void
-final_reg_note_copy (notes, map)
- rtx notes;
+final_reg_note_copy (notesp, map)
+ rtx *notesp;
struct inline_remap *map;
{
- rtx note;
+ while (*notesp)
+ {
+ rtx note = *notesp;
+
+ if (GET_CODE (note) == INSN_LIST)
+ {
+ /* Sometimes, we have a REG_WAS_0 note that points to a
+ deleted instruction. In that case, we can just delete the
+ note. */
+ if (REG_NOTE_KIND (note) == REG_WAS_0)
+ {
+ *notesp = XEXP (note, 1);
+ continue;
+ }
+ else
+ {
+ rtx insn = map->insn_map[INSN_UID (XEXP (note, 0))];
+
+ /* If we failed to remap the note, something is awry.
+ Allow REG_LABEL as it may reference label outside
+ the unrolled loop. */
+ if (!insn)
+ {
+ if (REG_NOTE_KIND (note) != REG_LABEL)
+ abort ();
+ }
+ else
+ XEXP (note, 0) = insn;
+ }
+ }
- 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))];
+ notesp = &XEXP (note, 1);
+ }
}
/* Copy each instruction in the loop, substituting from map as appropriate.
unsigned int regno = REGNO (SET_DEST (set));
v = addr_combined_regs[REGNO (SET_DEST (set))];
- bl = ivs->reg_biv_class[REGNO (v->src_reg)];
+ bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
/* Although the giv_inc amount is not needed here, we must call
calculate_giv_inc here since it might try to delete the
we might accidentally delete insns generated immediately
below by emit_unrolled_add. */
- if (! derived_regs[regno])
- giv_inc = calculate_giv_inc (set, insn, regno);
+ giv_inc = calculate_giv_inc (set, insn, regno);
/* Now find all address giv's that were combined with this
giv 'v'. */
dest_reg_was_split = 1;
giv_dest_reg = SET_DEST (set);
- if (derived_regs[regno])
- {
- /* ??? This relies on SET_SRC (SET) to be of
- the form (plus (reg) (const_int)), and thus
- forces recombine_givs to restrict the kind
- of giv derivations it does before unrolling. */
- giv_src_reg = XEXP (SET_SRC (set), 0);
- giv_inc = XEXP (SET_SRC (set), 1);
- }
- else
- {
- giv_src_reg = giv_dest_reg;
- /* Compute the increment value for the giv, if it wasn't
- already computed above. */
- if (giv_inc == 0)
- giv_inc = calculate_giv_inc (set, insn, regno);
- }
+ giv_src_reg = giv_dest_reg;
+ /* Compute the increment value for the giv, if it wasn't
+ already computed above. */
+ if (giv_inc == 0)
+ giv_inc = calculate_giv_inc (set, insn, regno);
+
src_regno = REGNO (giv_src_reg);
if (unroll_type == UNROLL_COMPLETELY)
for the biv was stored in the biv's first struct
induction entry by find_splittable_regs. */
- if (regno < max_reg_before_loop
+ if (regno < ivs->n_regs
&& REG_IV_TYPE (ivs, regno) == BASIC_INDUCT)
{
- giv_src_reg = ivs->reg_biv_class[regno]->biv->src_reg;
+ giv_src_reg = REG_IV_CLASS (ivs, regno)->biv->src_reg;
giv_dest_reg = giv_src_reg;
}
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 correctly to make invert_jump working. */
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.
In this case, we want to change the original fall through
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
if ((GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
|| GET_CODE (insn) == CALL_INSN)
&& map->insn_map[INSN_UID (insn)])
- final_reg_note_copy (REG_NOTES (map->insn_map[INSN_UID (insn)]), map);
+ final_reg_note_copy (®_NOTES (map->insn_map[INSN_UID (insn)]), map);
}
while (insn != copy_end);
tem = gen_sequence ();
end_sequence ();
- emit_insn_before (tem, insert_before);
+ loop_insn_emit_before (loop, 0, insert_before, tem);
}
\f
/* Emit an insn, using the expand_binop to ensure that a valid insn is
{
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);
rtx
biv_total_increment (bl)
- struct iv_class *bl;
+ const struct iv_class *bl;
{
struct induction *v;
rtx result;
times, since multiplies by small integers (1,2,3,4) are very cheap. */
static int
-find_splittable_regs (loop, unroll_type, end_insert_before, unroll_number)
+find_splittable_regs (loop, unroll_type, unroll_number)
const struct loop *loop;
enum unroll_types unroll_type;
- rtx end_insert_before;
int unroll_number;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
rtx biv_final_value;
int biv_splittable;
int result = 0;
- rtx loop_start = loop->start;
- rtx loop_end = loop->end;
- for (bl = ivs->loop_iv_list; bl; bl = bl->next)
+ for (bl = ivs->list; bl; bl = bl->next)
{
/* Biv_total_increment must return a constant value,
otherwise we can not calculate the split values. */
biv_final_value = 0;
if (unroll_type != UNROLL_COMPLETELY
&& (loop->exit_count || unroll_type == UNROLL_NAIVE)
- && (uid_luid[REGNO_LAST_UID (bl->regno)] >= INSN_LUID (loop_end)
+ && (REGNO_LAST_LUID (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)]
+ || (REGNO_FIRST_LUID (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 (loop, bl)))
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);
+ loop_insn_hoist (loop,
+ gen_move_insn (tem, bl->biv->src_reg));
if (loop_dump_stream)
fprintf (loop_dump_stream,
how the loop exits. Otherwise emit the insn after the loop,
since this is slightly more efficient. */
if (! loop->exit_count)
- emit_insn_before (gen_move_insn (bl->biv->src_reg,
- biv_final_value),
- end_insert_before);
+ loop_insn_sink (loop, gen_move_insn (bl->biv->src_reg,
+ biv_final_value));
else
{
/* Create a new register to hold the value of the biv, and then
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,
- biv_final_value),
- loop_start);
+ loop_insn_hoist (loop, gen_move_insn (tem, bl->biv->src_reg));
+ loop_insn_hoist (loop, gen_move_insn (bl->biv->src_reg,
+ biv_final_value));
if (loop_dump_stream)
fprintf (loop_dump_stream, "Biv %d mapped to %d for split.\n",
|| (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))]
+ || (REGNO_LAST_LUID (REGNO (v->dest_reg))
>= INSN_LUID (loop->end)))
- /* Givs made from biv increments are missed by the above test, so
- test explicitly for them. */
- && (REGNO (v->dest_reg) < ivs->first_increment_giv
- || REGNO (v->dest_reg) > ivs->last_increment_giv)
&& ! (final_value = v->final_value))
continue;
to its final value before loop start to ensure that this insn
will always be executed, no matter how we exit. */
tem = gen_reg_rtx (v->mode);
- emit_insn_before (gen_move_insn (tem, v->dest_reg), loop_start);
- emit_insn_before (gen_move_insn (v->dest_reg, final_value),
- loop_start);
+ loop_insn_hoist (loop, gen_move_insn (tem, v->dest_reg));
+ loop_insn_hoist (loop, gen_move_insn (v->dest_reg, final_value));
if (loop_dump_stream)
fprintf (loop_dump_stream, "Giv %d mapped to %d for split.\n",
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);
+ loop_insn_hoist (loop, gen_move_insn (tem, bl->biv->src_reg));
biv_initial_value = tem;
}
biv_initial_value = extend_value_for_giv (v, biv_initial_value);
{
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);
+ loop_iv_add_mult_hoist (loop, bl->initial_value, v->mult_val,
+ v->add_val, tem);
value = tem;
}
splittable_regs[REGNO (v->new_reg)] = value;
- derived_regs[REGNO (v->new_reg)] = v->derived_from != 0;
}
else
{
rtx new_reg = v->new_reg;
record_base_value (REGNO (tem), v->add_val, 0);
- if (same && same->derived_from)
- {
- /* calculate_giv_inc doesn't work for derived givs.
- copy_loop_body works around the problem for the
- DEST_REG givs themselves, but it can't handle
- DEST_ADDR givs that have been combined with
- a derived DEST_REG giv.
- So Handle V as if the giv from which V->SAME has
- been derived has been combined with V.
- recombine_givs only derives givs from givs that
- are reduced the ordinary, so we need not worry
- about same->derived_from being in turn derived. */
-
- same = same->derived_from;
- new_reg = express_from (same, v);
- new_reg = replace_rtx (new_reg, same->dest_reg,
- same->new_reg);
- }
-
/* If the address giv has a constant in its new_reg value,
then this constant can be pulled out and put in value,
instead of being part of the initialization code. */
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)),
- loop->start);
+ loop_insn_hoist (loop, gen_rtx_SET (VOIDmode, tem,
+ copy_rtx (v->new_reg)));
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));
+ We must calculate it from NEW_REG. */
+ delete_related_insns (PREV_INSN (loop->start));
start_sequence ();
ret = force_operand (v->new_reg, tem);
emit_move_insn (tem, ret);
sequence = gen_sequence ();
end_sequence ();
- emit_insn_before (sequence, loop->start);
+ loop_insn_hoist (loop, sequence);
if (loop_dump_stream)
fprintf (loop_dump_stream,
INSN_UID (v->insn));
continue;
}
- if (v->same && v->same->derived_from)
- {
- /* Handle V as if the giv from which V->SAME has
- been derived has been combined with V. */
-
- v->same = v->same->derived_from;
- v->new_reg = express_from (v->same, v);
- v->new_reg = replace_rtx (v->new_reg, v->same->dest_reg,
- v->same->new_reg);
- }
-
}
/* Store the value of dest_reg into the insn. This sharing
Make sure that it's giv is marked as splittable here. */
splittable_regs[REGNO (v->new_reg)] = value;
- derived_regs[REGNO (v->new_reg)] = v->derived_from != 0;
/* Make it appear to depend upon itself, so that the
giv will be properly split in the main loop above. */
{
int count = 1;
if (! v->ignore)
- count = ivs->reg_biv_class[REGNO (v->src_reg)]->biv_count;
-
- if (count > 1 && v->derived_from)
- /* In this case, there is one set where the giv insn was and one
- set each after each biv increment. (Most are likely dead.) */
- count++;
+ count = REG_IV_CLASS (ivs, REGNO (v->src_reg))->biv_count;
splittable_regs_updates[REGNO (v->new_reg)] = count;
}
const struct loop *loop;
struct iv_class *bl;
{
- rtx loop_end = loop->end;
unsigned HOST_WIDE_INT n_iterations = LOOP_INFO (loop)->n_iterations;
rtx increment, tem;
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 (n_iterations),
- bl->initial_value, tem, NEXT_INSN (loop_end));
+ loop_iv_add_mult_sink (loop, increment, GEN_INT (n_iterations),
+ bl->initial_value, tem);
if (loop_dump_stream)
fprintf (loop_dump_stream,
struct iv_class *bl;
rtx insn;
rtx increment, tem;
- rtx insert_before, seq;
+ rtx seq;
rtx loop_end = loop->end;
unsigned HOST_WIDE_INT n_iterations = LOOP_INFO (loop)->n_iterations;
- bl = ivs->reg_biv_class[REGNO (v->src_reg)];
+ bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
/* The final value for givs which depend on reversed bivs must be calculated
differently than for ordinary givs. In this case, there is already an
We must search from the insn that sets the giv to the end
of the loop to calculate this value. */
- insert_before = NEXT_INSN (loop_end);
-
/* Put the final biv value in tem. */
tem = gen_reg_rtx (v->mode);
record_base_value (REGNO (tem), bl->biv->add_val, 0);
- emit_iv_add_mult (increment, GEN_INT (n_iterations),
- extend_value_for_giv (v, bl->initial_value),
- tem, insert_before);
+ loop_iv_add_mult_sink (loop, extend_value_for_giv (v, increment),
+ GEN_INT (n_iterations),
+ extend_value_for_giv (v, bl->initial_value),
+ tem);
/* Subtract off extra increments as we find them. */
for (insn = NEXT_INSN (v->insn); insn != loop_end;
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 ();
- emit_insn_before (seq, insert_before);
+ loop_insn_sink (loop, seq);
}
}
/* Now calculate the giv's final value. */
- emit_iv_add_mult (tem, v->mult_val, v->add_val, tem, insert_before);
+ loop_iv_add_mult_sink (loop, tem, v->mult_val, v->add_val, tem);
if (loop_dump_stream)
fprintf (loop_dump_stream,
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. */
rtx comparison, comparison_value;
rtx iteration_var, initial_value, increment, final_value;
enum rtx_code comparison_code;
- HOST_WIDE_INT abs_inc;
+ HOST_WIDE_INT inc;
+ unsigned HOST_WIDE_INT abs_inc;
unsigned HOST_WIDE_INT abs_diff;
int off_by_one;
int increment_dir;
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. */
will propagate a new pseudo into the old iteration register but
this will be marked by having the REG_USERVAR_P bit set. */
- if ((unsigned) REGNO (iteration_var) >= ivs->reg_iv_type->num_elements
+ if ((unsigned) REGNO (iteration_var) >= ivs->n_regs
&& ! REG_USERVAR_P (iteration_var))
abort ();
/* If this is a new register, can't handle it since we don't have any
reg_iv_type entry for it. */
- if ((unsigned) REGNO (iteration_var) >= ivs->reg_iv_type->num_elements)
+ if ((unsigned) REGNO (iteration_var) >= ivs->n_regs)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
}
else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
{
- /* When reg_iv_type / reg_iv_info is resized for biv increments
- that are turned into givs, reg_biv_class is not resized.
- So check here that we don't make an out-of-bounds access. */
- if (REGNO (iteration_var) >= max_reg_before_loop)
+ if (REGNO (iteration_var) >= ivs->n_regs)
abort ();
/* Grab initial value, only useful if it is a constant. */
- bl = ivs->reg_biv_class[REGNO (iteration_var)];
+ bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
initial_value = bl->initial_value;
+ if (!bl->biv->always_executed || bl->biv->maybe_multiple)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Basic induction var not set once in each iteration.\n");
+ return 0;
+ }
increment = biv_total_increment (bl);
}
struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
rtx biv_initial_value;
- if (REGNO (v->src_reg) >= max_reg_before_loop)
+ if (REGNO (v->src_reg) >= ivs->n_regs)
abort ();
- bl = ivs->reg_biv_class[REGNO (v->src_reg)];
+ if (!v->always_executed || v->maybe_multiple)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: General induction var not set once in each iteration.\n");
+ return 0;
+ }
+
+ bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
/* Increment value is mult_val times the increment value of the biv. */
{
struct induction *biv_inc;
- increment
- = fold_rtx_mult_add (v->mult_val, increment, const0_rtx, v->mode);
- /* The caller assumes that one full increment has occured at the
+ 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 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) .
if (loop_insn_first_p (v->insn, biv_inc->insn))
offset -= INTVAL (biv_inc->add_val);
}
- offset *= INTVAL (v->mult_val);
}
if (loop_dump_stream)
fprintf (loop_dump_stream,
{
fprintf (loop_dump_stream,
"Loop iterations: Increment value not constant ");
- print_rtl (loop_dump_stream, increment);
+ print_simple_rtl (loop_dump_stream, increment);
fprintf (loop_dump_stream, ".\n");
}
return 0;
{
fprintf (loop_dump_stream,
"Loop iterations: Initial value not constant ");
- print_rtl (loop_dump_stream, initial_value);
+ print_simple_rtl (loop_dump_stream, initial_value);
fprintf (loop_dump_stream, ".\n");
}
return 0;
{
fprintf (loop_dump_stream,
"Loop iterations: Final value not constant ");
- print_rtl (loop_dump_stream, final_value);
+ print_simple_rtl (loop_dump_stream, final_value);
fprintf (loop_dump_stream, ".\n");
}
return 0;
so correct for that. Note that abs_diff and n_iterations are
unsigned, because they can be as large as 2^n - 1. */
- abs_inc = INTVAL (increment);
- if (abs_inc > 0)
- abs_diff = INTVAL (final_value) - INTVAL (initial_value);
- else if (abs_inc < 0)
+ inc = INTVAL (increment);
+ if (inc > 0)
+ {
+ abs_diff = INTVAL (final_value) - INTVAL (initial_value);
+ abs_inc = inc;
+ }
+ else if (inc < 0)
{
abs_diff = INTVAL (initial_value) - INTVAL (final_value);
- abs_inc = -abs_inc;
+ abs_inc = -inc;
}
else
abort ();
+ /* Given that iteration_var is going to iterate over its own mode,
+ 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
+ << (GET_MODE_BITSIZE (GET_MODE (iteration_var)) - 1)
+ << 1) - 1;
+
/* 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
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;
/* 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
+ if (REGNO (x) < ivs->n_regs
&& REG_IV_TYPE (ivs, REGNO (x)) == BASIC_INDUCT)
- return ivs->reg_biv_class[REGNO (x)]->biv->src_reg;
+ return REG_IV_CLASS (ivs, REGNO (x))->biv->src_reg;
break;
default:
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
