/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992, 1993, 1994, 1995, 1997, 1998,
- 1999, 2000 Free Software Foundation, Inc.
+ Copyright (C) 1992, 1993, 1994, 1995, 1997, 1998, 1999, 2000
+ Free Software Foundation, Inc.
Contributed by James E. Wilson, Cygnus Support/UC Berkeley.
This file is part of GNU CC.
#define NUM_FACTORS 4
-struct _factor { int factor, count; } factors[NUM_FACTORS]
- = { {2, 0}, {3, 0}, {5, 0}, {7, 0}};
+struct _factor { int factor, count; }
+factors[NUM_FACTORS] = { {2, 0}, {3, 0}, {5, 0}, {7, 0}};
/* Describes the different types of loop unrolling performed. */
-enum unroll_types { UNROLL_COMPLETELY, UNROLL_MODULO, UNROLL_NAIVE };
+enum unroll_types
+{
+ UNROLL_COMPLETELY,
+ UNROLL_MODULO,
+ UNROLL_NAIVE
+};
#include "config.h"
#include "system.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 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 copy_loop_body PARAMS ((rtx, rtx, struct inline_remap *, rtx, int,
- enum unroll_types, rtx, rtx, rtx, rtx));
-static void iteration_info PARAMS ((const struct loop *, rtx, rtx *, rtx *));
+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));
-static int find_splittable_givs PARAMS ((const struct loop *,
+static int find_splittable_givs PARAMS ((const struct loop *,
struct iv_class *, enum unroll_types,
rtx, int));
static int reg_dead_after_loop PARAMS ((const struct loop *, rtx));
static rtx fold_rtx_mult_add PARAMS ((rtx, rtx, rtx, enum machine_mode));
static int verify_addresses PARAMS ((struct induction *, rtx, int));
-static rtx remap_split_bivs PARAMS ((rtx));
+static rtx remap_split_bivs PARAMS ((struct loop *, rtx));
static rtx find_common_reg_term PARAMS ((rtx, rtx));
static rtx subtract_reg_term PARAMS ((rtx, rtx));
static rtx loop_find_equiv_value PARAMS ((const struct loop *, rtx));
+static rtx ujump_to_loop_cont PARAMS ((rtx, rtx));
/* Try to unroll one loop and split induction variables in the loop.
rtx end_insert_before;
int strength_reduce_p;
{
+ struct loop_info *loop_info = LOOP_INFO (loop);
+ struct loop_ivs *ivs = LOOP_IVS (loop);
int i, j;
unsigned int r;
unsigned HOST_WIDE_INT temp;
rtx last_loop_insn;
rtx loop_start = loop->start;
rtx loop_end = loop->end;
- struct loop_info *loop_info = LOOP_INFO (loop);
/* Don't bother unrolling huge loops. Since the minimum factor is
two, loops greater than one half of MAX_UNROLLED_INSNS will never
if (loop_info->n_iterations == 1)
{
+ /* Handle the case where the loop begins with an unconditional
+ jump to the loop condition. Make sure to delete the jump
+ insn, otherwise the loop body will never execute. */
+
+ rtx ujump = ujump_to_loop_cont (loop->start, loop->cont);
+ if (ujump)
+ delete_insn (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.
Then return, since no other action is needed here. */
return;
}
else if (loop_info->n_iterations > 0
+ /* Avoid overflow in the next expression. */
+ && loop_info->n_iterations < MAX_UNROLLED_INSNS
&& loop_info->n_iterations * insn_count < MAX_UNROLLED_INSNS)
{
unroll_number = loop_info->n_iterations;
if (unroll_number == 1)
{
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: No factors found.\n");
+ fprintf (loop_dump_stream, "Loop unrolling: No factors found.\n");
}
else
unroll_type = UNROLL_MODULO;
}
-
/* Default case, calculate number of times to unroll loop based on its
size. */
if (unroll_type == UNROLL_NAIVE)
/* Now we know how many times to unroll the loop. */
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Unrolling loop %d times.\n", unroll_number);
-
+ fprintf (loop_dump_stream, "Unrolling loop %d times.\n", unroll_number);
if (unroll_type == UNROLL_COMPLETELY || unroll_type == UNROLL_MODULO)
{
for (i = 0; i < len; i++)
{
label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
- set_label_in_map (map,
- CODE_LABEL_NUMBER (label),
- label);
+ set_label_in_map (map, CODE_LABEL_NUMBER (label), label);
}
}
}
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 *));
/* If we have a target that uses cc0, then we also must not duplicate
the insn that sets cc0 before the jump insn, if one is present. */
#ifdef HAVE_cc0
- if (GET_CODE (copy_end) == JUMP_INSN && sets_cc0_p (PREV_INSN (copy_end)))
+ if (GET_CODE (copy_end) == JUMP_INSN
+ && sets_cc0_p (PREV_INSN (copy_end)))
copy_end_luid--;
#endif
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 = first_increment_giv; r <= 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 ;
+ register rtx diff;
rtx *labels;
int abs_inc, neg_inc;
map->reg_map = (rtx *) xmalloc (maxregnum * sizeof (rtx));
VARRAY_CONST_EQUIV_INIT (map->const_equiv_varray, maxregnum,
- "unroll_loop");
+ "unroll_loop_precondition");
global_const_equiv_varray = map->const_equiv_varray;
init_reg_map (map, maxregnum);
abs_inc = INTVAL (increment);
if (abs_inc < 0)
{
- abs_inc = - abs_inc;
+ abs_inc = -abs_inc;
neg_inc = 1;
}
{
copy_end = PREV_INSN (last_loop_insn);
#ifdef HAVE_cc0
- /* The immediately preceding insn may be a compare which we do not
- want to copy. */
+ /* The immediately preceding insn may be a compare which
+ we do not want to copy. */
if (sets_cc0_p (PREV_INSN (copy_end)))
copy_end = PREV_INSN (copy_end);
#endif
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++)
/* None of the copies are the `last_iteration', so just
pass zero for that parameter. */
- copy_loop_body (copy_start, copy_end, map, exit_label, 0,
+ copy_loop_body (loop, copy_start, copy_end, map, exit_label, 0,
unroll_type, start_label, loop_end,
loop_start, copy_end);
}
{
insert_before = last_loop_insn;
#ifdef HAVE_cc0
- /* The instruction immediately before the JUMP_INSN may be a compare
- instruction which we do not want to copy or delete. */
+ /* The instruction immediately before the JUMP_INSN may
+ be a compare instruction which we do not want to copy
+ or delete. */
if (sets_cc0_p (PREV_INSN (insert_before)))
insert_before = PREV_INSN (insert_before);
#endif
if (unroll_type == UNROLL_NAIVE && ! flag_unroll_all_loops)
{
if (loop_dump_stream)
- fprintf (loop_dump_stream, "Unrolling failure: Naive unrolling not being done.\n");
+ fprintf (loop_dump_stream,
+ "Unrolling failure: Naive unrolling not being done.\n");
goto egress;
}
/* 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 = 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
{
insn = NEXT_INSN (copy_end);
if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
- PATTERN (insn) = remap_split_bivs (PATTERN (insn));
+ PATTERN (insn) = remap_split_bivs (loop, PATTERN (insn));
}
/* For unroll_number times, make a copy of each instruction
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++)
LABEL_NUSES (tem)++;
}
- copy_loop_body (copy_start, copy_end, map, exit_label,
+ copy_loop_body (loop, copy_start, copy_end, map, exit_label,
i == unroll_number - 1, unroll_type, start_label,
loop_end, insert_before, insert_before);
}
}
free (map->insn_map);
free (splittable_regs);
- free (derived_regs);
free (splittable_regs_updates);
free (addr_combined_regs);
free (local_regno);
return 0;
}
else if ((exact_log2 (INTVAL (loop_info->increment)) < 0)
- && (exact_log2 (- INTVAL (loop_info->increment)) < 0))
+ && (exact_log2 (-INTVAL (loop_info->increment)) < 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)
return 0;
}
- /* Note that iteration_info biases the initial value for GIV iterators
+ /* Note that loop_iterations biases the initial value for GIV iterators
such as "while (i-- > 0)" so that we can calculate the number of
iterations just like for BIV iterators.
return 1;
}
-
/* All pseudo-registers must be mapped to themselves. Two hard registers
must be mapped, VIRTUAL_STACK_VARS_REGNUM and VIRTUAL_INCOMING_ARGS_
REGNUM, to avoid function-inlining specific conversions of these
This is very similar to a loop in expand_inline_function. */
static void
-copy_loop_body (copy_start, copy_end, map, exit_label, last_iteration,
+copy_loop_body (loop, copy_start, copy_end, map, exit_label, last_iteration,
unroll_type, start_label, loop_end, insert_before,
copy_notes_from)
+ struct loop *loop;
rtx copy_start, copy_end;
struct inline_remap *map;
rtx exit_label;
enum unroll_types unroll_type;
rtx start_label, loop_end, insert_before, copy_notes_from;
{
+ struct loop_ivs *ivs = LOOP_IVS (loop);
rtx insn, pattern;
rtx set, tem, copy = NULL_RTX;
int dest_reg_was_split, i;
if (! last_iteration)
{
final_label = gen_label_rtx ();
- set_label_in_map (map, CODE_LABEL_NUMBER (start_label),
- final_label);
+ set_label_in_map (map, CODE_LABEL_NUMBER (start_label), final_label);
}
else
set_label_in_map (map, CODE_LABEL_NUMBER (start_label), start_label);
unsigned int regno = REGNO (SET_DEST (set));
v = addr_combined_regs[REGNO (SET_DEST (set))];
- bl = 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'. */
We must subtract the const_adjust factor added in
above. */
tv->dest_reg = plus_constant (dest_reg,
- - tv->const_adjust);
+ -tv->const_adjust);
*tv->location = tv->dest_reg;
}
}
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
- && REG_IV_TYPE (regno) == BASIC_INDUCT)
+ if (regno < ivs->n_regs
+ && REG_IV_TYPE (ivs, regno) == BASIC_INDUCT)
{
- giv_src_reg = reg_biv_class[regno]->biv->src_reg;
+ giv_src_reg = REG_IV_CLASS (ivs, regno)->biv->src_reg;
giv_dest_reg = giv_src_reg;
}
#endif
splittable_regs[regno]
- = GEN_INT (INTVAL (giv_inc)
- + INTVAL (splittable_regs[src_regno]));
+ = simplify_gen_binary (PLUS, GET_MODE (giv_src_reg),
+ giv_inc,
+ splittable_regs[src_regno]);
giv_inc = splittable_regs[regno];
/* Now split the induction variable by changing the dest
if (JUMP_LABEL (insn) == start_label && insn == copy_end
&& ! last_iteration)
{
+ /* 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))++;
+
/* 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
case to be a branch past the end of the loop, and the
original jump label case to fall_through. */
- if (invert_exp (pattern, copy))
- {
- if (! redirect_exp (&pattern,
- get_label_from_map (map,
- CODE_LABEL_NUMBER
- (JUMP_LABEL (insn))),
- exit_label, copy))
- abort ();
- }
- else
+ if (!invert_jump (copy, exit_label, 0))
{
rtx jmp;
rtx lab = gen_label_rtx ();
jmp = emit_barrier_after (jmp);
emit_label_after (lab, jmp);
LABEL_NUSES (lab) = 0;
- if (! redirect_exp (&pattern,
- get_label_from_map (map,
- CODE_LABEL_NUMBER
- (JUMP_LABEL (insn))),
- lab, copy))
+ if (!redirect_jump (copy, lab, 0))
abort ();
}
}
/* If this used to be a conditional jump insn but whose branch
direction is now known, we must do something special. */
- if (condjump_p (insn) && !simplejump_p (insn) && map->last_pc_value)
+ if (any_condjump_p (insn) && onlyjump_p (insn) && map->last_pc_value)
{
#ifdef HAVE_cc0
/* If the previous insn set cc0 for us, delete it. */
/* VTOP and CONT notes are valid only before the loop exit test.
If placed anywhere else, loop may generate bad code. */
/* BASIC_BLOCK notes exist to stabilize basic block structures with
- the associated rtl. We do not want to share the structure in
+ the associated rtl. We do not want to share the structure in
this new block. */
if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED_LABEL
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
&& ((NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_VTOP
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_CONT)
return result;
}
-/* Determine the initial value of the iteration variable, and the amount
- that it is incremented each loop. Use the tables constructed by
- the strength reduction pass to calculate these values.
-
- Initial_value and/or increment are set to zero if their values could not
- be calculated. */
-
-static void
-iteration_info (loop, iteration_var, initial_value, increment)
- const struct loop *loop ATTRIBUTE_UNUSED;
- rtx iteration_var, *initial_value, *increment;
-{
- struct iv_class *bl;
-
- /* Clear the result values, in case no answer can be found. */
- *initial_value = 0;
- *increment = 0;
-
- /* The iteration variable can be either a giv or a biv. Check to see
- which it is, and compute the variable's initial value, and increment
- value if possible. */
-
- /* 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) >= reg_iv_type->num_elements)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: No reg_iv_type entry for iteration var.\n");
- return;
- }
-
- /* 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_info->n_iterations. */
- else if ((GET_MODE_BITSIZE (GET_MODE (iteration_var))
- > HOST_BITS_PER_WIDE_INT))
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Iteration var rejected because mode too large.\n");
- return;
- }
- else if (GET_MODE_CLASS (GET_MODE (iteration_var)) != MODE_INT)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Iteration var not an integer.\n");
- return;
- }
- else if (REG_IV_TYPE (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)
- abort ();
-
- /* Grab initial value, only useful if it is a constant. */
- bl = reg_biv_class[REGNO (iteration_var)];
- *initial_value = bl->initial_value;
-
- *increment = biv_total_increment (bl);
- }
- else if (REG_IV_TYPE (REGNO (iteration_var)) == GENERAL_INDUCT)
- {
- HOST_WIDE_INT offset = 0;
- struct induction *v = REG_IV_INFO (REGNO (iteration_var));
-
- if (REGNO (v->src_reg) >= max_reg_before_loop)
- abort ();
-
- bl = reg_biv_class[REGNO (v->src_reg)];
-
- /* Increment value is mult_val times the increment value of the biv. */
-
- *increment = biv_total_increment (bl);
- if (*increment)
- {
- 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
- 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) .
- Therefore, we bias the initial value by subtracting the amount of
- the increment that occurs between the giv set and the giv test. */
- 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);
- }
- offset *= INTVAL (v->mult_val);
- }
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Giv iterator, initial value bias %ld.\n",
- (long) offset);
- /* Initial value is mult_val times the biv's initial value plus
- add_val. Only useful if it is a constant. */
- *initial_value
- = fold_rtx_mult_add (v->mult_val,
- plus_constant (bl->initial_value, offset),
- v->add_val, v->mode);
- }
- else
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Not basic or general induction var.\n");
- return;
- }
-}
-
-
/* 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
is safe to split, then indicate that by saving some useful info
rtx end_insert_before;
int unroll_number;
{
+ struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
struct induction *v;
rtx increment, tem;
rtx loop_start = loop->start;
rtx loop_end = loop->end;
- for (bl = 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)))
loop_start);
if (loop_dump_stream)
- fprintf (loop_dump_stream, "Biv %d initial value remapped to %d.\n",
+ fprintf (loop_dump_stream,
+ "Biv %d initial value remapped to %d.\n",
bl->regno, REGNO (tem));
splittable_regs[bl->regno] = tem;
depend on it may be splittable if the biv is live outside the
loop, and the givs aren't. */
- result += find_splittable_givs (loop, bl, unroll_type, increment,
+ result += find_splittable_givs (loop, bl, unroll_type, increment,
unroll_number);
/* If final value is non-zero, then must emit an instruction which sets
rtx increment;
int unroll_number;
{
+ struct loop_ivs *ivs = LOOP_IVS (loop);
struct induction *v, *v2;
rtx final_value;
rtx tem;
|| (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) < first_increment_giv
- || REGNO (v->dest_reg) > last_increment_giv)
&& ! (final_value = v->final_value))
continue;
loop->start);
biv_initial_value = tem;
}
+ biv_initial_value = extend_value_for_giv (v, biv_initial_value);
value = fold_rtx_mult_add (v->mult_val, biv_initial_value,
v->add_val, v->mode);
}
}
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. */
/* Save the negative of the eliminated const, so
that we can calculate the dest_reg's increment
value later. */
- v->const_adjust = - INTVAL (XEXP (new_reg, 1));
+ v->const_adjust = -INTVAL (XEXP (new_reg, 1));
new_reg = XEXP (new_reg, 0);
if (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 = 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;
}
label = gen_rtx_LABEL_REF (VOIDmode, loop->end);
LABEL_NEXTREF (label) = loop->exit_labels;
- for ( ; label; label = LABEL_NEXTREF (label))
+ for (; label; label = LABEL_NEXTREF (label))
{
/* Succeed if find an insn which sets the biv or if reach end of
function. Fail if find an insn that uses the biv, or if come to
{
if (GET_CODE (PATTERN (insn)) == RETURN)
break;
- else if (! simplejump_p (insn)
+ else if (!any_uncondjump_p (insn)
/* Prevent infinite loop following infinite loops. */
|| jump_count++ > 20)
return 0;
return 0;
/* The final value for reversed bivs must be calculated differently than
- for ordinary bivs. In this case, there is already an insn after the
+ for ordinary bivs. In this case, there is already an insn after the
loop which sets this biv's final value (if necessary), and there are
no other loop exits, so we can return any value. */
if (bl->reversed)
const struct loop *loop;
struct induction *v;
{
+ struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
rtx insn;
rtx increment, tem;
rtx loop_end = loop->end;
unsigned HOST_WIDE_INT n_iterations = LOOP_INFO (loop)->n_iterations;
- bl = 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
insert_before = NEXT_INSN (loop_end);
/* Put the final biv value in tem. */
- tem = gen_reg_rtx (bl->biv->mode);
+ 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),
- bl->initial_value, tem, insert_before);
+ emit_iv_add_mult (extend_value_for_giv (v, increment),
+ GEN_INT (n_iterations),
+ extend_value_for_giv (v, bl->initial_value),
+ tem, insert_before);
/* Subtract off extra increments as we find them. */
for (insn = NEXT_INSN (v->insn); insn != loop_end;
}
/* Now calculate the giv's final value. */
- emit_iv_add_mult (tem, v->mult_val, v->add_val, tem,
- insert_before);
+ emit_iv_add_mult (tem, v->mult_val, v->add_val, tem, insert_before);
if (loop_dump_stream)
fprintf (loop_dump_stream,
return 0;
}
-
/* 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. */
rtx ret;
ret = reg;
- for (insn = PREV_INSN (loop_start); insn ; insn = PREV_INSN (insn))
+ 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))
+ else if (INSN_P (insn) && 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))
+ && (SET_DEST (set) == reg))
{
rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
ret = XEXP (note, 0);
else
ret = SET_SRC (set);
+
+ /* We cannot do this if it changes between the
+ assignment and loop start though. */
+ if (modified_between_p (ret, insn, loop_start))
+ ret = reg;
}
break;
}
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. */
return NULL_RTX;
}
-/* Calculate the number of loop iterations. Returns the exact number of loop
- iterations if it can be calculated, otherwise returns zero. */
+/* Determine the loop iterator and 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)
struct loop *loop;
{
+ struct loop_info *loop_info = LOOP_INFO (loop);
+ struct loop_ivs *ivs = LOOP_IVS (loop);
rtx comparison, comparison_value;
rtx iteration_var, initial_value, increment, final_value;
enum rtx_code comparison_code;
int unsigned_p, compare_dir, final_larger;
rtx last_loop_insn;
rtx reg_term;
- struct loop_info *loop_info = LOOP_INFO (loop);
+ struct iv_class *bl;
loop_info->n_iterations = 0;
loop_info->initial_value = 0;
loop_info->increment = 0;
loop_info->iteration_var = 0;
loop_info->unroll_number = 1;
+ loop_info->iv = 0;
/* 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
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) >= reg_iv_type->num_elements
+ if ((unsigned) REGNO (iteration_var) >= ivs->n_regs
&& ! REG_USERVAR_P (iteration_var))
abort ();
- iteration_info (loop, iteration_var, &initial_value, &increment);
+ /* Determine the initial value of the iteration variable, and the amount
+ that it is incremented each loop. Use the tables constructed by
+ the strength reduction pass to calculate these values. */
+
+ /* Clear the result values, in case no answer can be found. */
+ initial_value = 0;
+ increment = 0;
+
+ /* The iteration variable can be either a giv or a biv. Check to see
+ which it is, and compute the variable's initial value, and increment
+ value if possible. */
+
+ /* 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->n_regs)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: No reg_iv_type entry for iteration var.\n");
+ return 0;
+ }
+
+ /* 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_info->n_iterations. */
+ else if ((GET_MODE_BITSIZE (GET_MODE (iteration_var))
+ > HOST_BITS_PER_WIDE_INT))
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Iteration var rejected because mode too large.\n");
+ return 0;
+ }
+ else if (GET_MODE_CLASS (GET_MODE (iteration_var)) != MODE_INT)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Iteration var not an integer.\n");
+ return 0;
+ }
+ else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
+ {
+ if (REGNO (iteration_var) >= ivs->n_regs)
+ abort ();
+
+ /* Grab initial value, only useful if it is a constant. */
+ bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
+ initial_value = bl->initial_value;
+
+ increment = biv_total_increment (bl);
+ }
+ else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
+ {
+ HOST_WIDE_INT offset = 0;
+ struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
+ rtx biv_initial_value;
+
+ if (REGNO (v->src_reg) >= ivs->n_regs)
+ abort ();
+
+ bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
+
+ /* Increment value is mult_val times the increment value of the biv. */
+
+ increment = biv_total_increment (bl);
+ if (increment)
+ {
+ struct induction *biv_inc;
+
+ 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
+ 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) .
+ Therefore, we bias the initial value by subtracting the amount of
+ the increment that occurs between the giv set and the giv test. */
+ 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);
+ }
+ offset *= INTVAL (v->mult_val);
+ }
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Giv iterator, initial value bias %ld.\n",
+ (long) offset);
+
+ /* Initial value is mult_val times the biv's initial value plus
+ add_val. Only useful if it is a constant. */
+ biv_initial_value = extend_value_for_giv (v, bl->initial_value);
+ initial_value
+ = fold_rtx_mult_add (v->mult_val,
+ plus_constant (biv_initial_value, offset),
+ v->add_val, v->mode);
+ }
+ else
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop iterations: Not basic or general induction var.\n");
+ return 0;
+ }
if (initial_value == 0)
- /* iteration_info already printed a message. */
return 0;
unsigned_p = 0;
its value from the insns before the start of the loop. */
final_value = comparison_value;
- if (GET_CODE (comparison_value) == REG
+ if (GET_CODE (comparison_value) == REG
&& loop_invariant_p (loop, comparison_value))
{
final_value = loop_find_equiv_value (loop, comparison_value);
loop_info->increment = increment;
loop_info->iteration_var = iteration_var;
loop_info->comparison_code = comparison_code;
+ loop_info->iv = bl;
/* Try to determine the iteration count for loops such
as (for i = init; i < init + const; i++). When running the
{
rtx temp;
- /* 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. */
+ /* 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. */
temp = loop_find_equiv_value (loop, reg1);
Check this now so that we won't leave an invalid value if we
return early for any other reason. */
if (comparison_code == EQ)
- loop_info->final_equiv_value = loop_info->final_value = 0;
+ loop_info->final_equiv_value = loop_info->final_value = 0;
if (increment == 0)
{
else if (comparison_code == EQ)
{
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop iterations: EQ comparison loop.\n");
+ fprintf (loop_dump_stream, "Loop iterations: EQ comparison loop.\n");
return 0;
}
else if (GET_CODE (final_value) != CONST_INT)
else
{
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop iterations: Not normal loop.\n");
+ fprintf (loop_dump_stream, "Loop iterations: Not normal loop.\n");
return 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. */
static rtx
-remap_split_bivs (x)
+remap_split_bivs (loop, x)
+ struct loop *loop;
rtx x;
{
+ struct loop_ivs *ivs = LOOP_IVS (loop);
register enum rtx_code code;
register int i;
register const char *fmt;
/* 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
- && REG_IV_TYPE (REGNO (x)) == BASIC_INDUCT)
- return reg_biv_class[REGNO (x)]->biv->src_reg;
+ if (REGNO (x) < ivs->n_regs
+ && REG_IV_TYPE (ivs, REGNO (x)) == BASIC_INDUCT)
+ return REG_IV_CLASS (ivs, REGNO (x))->biv->src_reg;
break;
default:
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
- XEXP (x, i) = remap_split_bivs (XEXP (x, i));
+ XEXP (x, i) = remap_split_bivs (loop, XEXP (x, i));
else if (fmt[i] == 'E')
{
register int j;
for (j = 0; j < XVECLEN (x, i); j++)
- XVECEXP (x, i, j) = remap_split_bivs (XVECEXP (x, i, j));
+ XVECEXP (x, i, j) = remap_split_bivs (loop, XVECEXP (x, i, j));
}
}
return x;
while (INSN_UID (p) != first_uid)
{
if (GET_CODE (p) == JUMP_INSN)
- passed_jump= 1;
+ passed_jump = 1;
/* Could not find FIRST_UID. */
if (p == copy_end)
return 0;
}
/* Verify that FIRST_UID is an insn that entirely sets REGNO. */
- if (GET_RTX_CLASS (GET_CODE (p)) != 'i'
- || ! dead_or_set_regno_p (p, regno))
+ if (! INSN_P (p) || ! dead_or_set_regno_p (p, regno))
return 0;
/* FIRST_UID is always executed. */
/* FIRST_UID is always executed if LAST_UID is executed. */
return 1;
}
+
+/* This routine is called when the number of iterations for the unrolled
+ loop is one. The goal is to identify a loop that begins with an
+ unconditional branch to the loop continuation note (or a label just after).
+ In this case, the unconditional branch that starts the loop needs to be
+ deleted so that we execute the single iteration. */
+
+static rtx
+ujump_to_loop_cont (loop_start, loop_cont)
+ rtx loop_start;
+ rtx loop_cont;
+{
+ rtx x, label, label_ref;
+
+ /* See if loop start, or the next insn is an unconditional jump. */
+ loop_start = next_nonnote_insn (loop_start);
+
+ x = pc_set (loop_start);
+ if (!x)
+ return NULL_RTX;
+
+ label_ref = SET_SRC (x);
+ if (!label_ref)
+ return NULL_RTX;
+
+ /* Examine insn after loop continuation note. Return if not a label. */
+ label = next_nonnote_insn (loop_cont);
+ if (label == 0 || GET_CODE (label) != CODE_LABEL)
+ return NULL_RTX;
+
+ /* Return the loop start if the branch label matches the code label. */
+ if (CODE_LABEL_NUMBER (label) == CODE_LABEL_NUMBER (XEXP (label_ref, 0)))
+ return loop_start;
+ else
+ return NULL_RTX;
+}
OSDN Git Service
