/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992, 1993, 1994, 1995, 1997 Free Software Foundation, Inc.
+ Copyright (C) 1992, 93, 94, 95, 97, 1998 Free Software Foundation, Inc.
Contributed by James E. Wilson, Cygnus Support/UC Berkeley.
This file is part of GNU CC.
enum unroll_types { UNROLL_COMPLETELY, UNROLL_MODULO, UNROLL_NAIVE };
#include "config.h"
-#include <stdio.h>
+#include "system.h"
#include "rtl.h"
#include "insn-config.h"
#include "integrate.h"
#include "flags.h"
#include "expr.h"
#include "loop.h"
+#include "toplev.h"
/* This controls which loops are unrolled, and by how much we unroll
them. */
/* Values describing the current loop's iteration variable. These are set up
by loop_iterations, and used by precondition_loop_p. */
-static rtx loop_iteration_var;
-static rtx loop_initial_value;
-static rtx loop_increment;
-static rtx loop_final_value;
-static enum rtx_code loop_comparison_code;
+rtx loop_iteration_var;
+rtx loop_initial_value;
+rtx loop_increment;
+rtx loop_final_value;
+enum rtx_code loop_comparison_code;
/* Forward declarations. */
static void init_reg_map PROTO((struct inline_remap *, int));
-static int precondition_loop_p PROTO((rtx *, rtx *, rtx *, rtx, rtx));
+static int precondition_loop_p PROTO((rtx *, rtx *, rtx *, rtx));
static rtx calculate_giv_inc PROTO((rtx, rtx, int));
static rtx initial_reg_note_copy PROTO((rtx, struct inline_remap *));
static void final_reg_note_copy PROTO((rtx, struct inline_remap *));
rtx, rtx, rtx, int));
static int reg_dead_after_loop PROTO((rtx, rtx, rtx));
static rtx fold_rtx_mult_add PROTO((rtx, rtx, rtx, enum machine_mode));
+static int verify_addresses PROTO((struct induction *, rtx, int));
static rtx remap_split_bivs PROTO((rtx));
/* Try to unroll one loop and split induction variables in the loop.
int i, j, temp;
int unroll_number = 1;
rtx copy_start, copy_end;
- rtx insn, copy, sequence, pattern, tem;
+ rtx insn, sequence, pattern, tem;
int max_labelno, max_insnno;
rtx insert_before;
struct inline_remap *map;
loop_n_iterations = 0;
if (loop_dump_stream && loop_n_iterations > 0)
- fprintf (loop_dump_stream,
- "Loop unrolling: %d iterations.\n", loop_n_iterations);
+ {
+ fputs ("Loop unrolling: ", loop_dump_stream);
+ fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, loop_n_iterations);
+ fputs (" iterations.\n", loop_dump_stream);
+ }
/* Find and save a pointer to the last nonnote insn in the loop. */
if (unroll_type == UNROLL_COMPLETELY || unroll_type == UNROLL_MODULO)
{
- /* Loops of these types should never start with a jump down to
- the exit condition test. For now, check for this case just to
- be sure. UNROLL_NAIVE loops can be of this form, this case is
- handled below. */
+ /* Loops of these types can start with jump down to the exit condition
+ in rare circumstances.
+
+ Consider a pair of nested loops where the inner loop is part
+ of the exit code for the outer loop.
+
+ In this case jump.c will not duplicate the exit test for the outer
+ loop, so it will start with a jump to the exit code.
+
+ Then consider if the inner loop turns out to iterate once and
+ only once. We will end up deleting the jumps associated with
+ the inner loop. However, the loop notes are not removed from
+ the instruction stream.
+
+ And finally assume that we can compute the number of iterations
+ for the outer loop.
+
+ In this case unroll may want to unroll the outer loop even though
+ it starts with a jump to the outer loop's exit code.
+
+ We could try to optimize this case, but it hardly seems worth it.
+ Just return without unrolling the loop in such cases. */
+
insn = loop_start;
while (GET_CODE (insn) != CODE_LABEL && GET_CODE (insn) != JUMP_INSN)
insn = NEXT_INSN (insn);
if (GET_CODE (insn) == JUMP_INSN)
- abort ();
+ return;
}
if (unroll_type == UNROLL_COMPLETELY)
for (insn = copy_start; insn != loop_end; insn = NEXT_INSN (insn))
{
+ rtx note;
+
if (GET_CODE (insn) == CODE_LABEL)
local_label[CODE_LABEL_NUMBER (insn)] = 1;
else if (GET_CODE (insn) == JUMP_INSN)
{
if (JUMP_LABEL (insn))
- map->label_map[CODE_LABEL_NUMBER (JUMP_LABEL (insn))]
- = JUMP_LABEL (insn);
+ set_label_in_map (map,
+ CODE_LABEL_NUMBER (JUMP_LABEL (insn)),
+ JUMP_LABEL (insn));
else if (GET_CODE (PATTERN (insn)) == ADDR_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
{
for (i = 0; i < len; i++)
{
label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
- map->label_map[CODE_LABEL_NUMBER (label)] = label;
+ set_label_in_map (map,
+ CODE_LABEL_NUMBER (label),
+ label);
}
}
}
+ else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)))
+ set_label_in_map (map, CODE_LABEL_NUMBER (XEXP (note, 0)),
+ XEXP (note, 0));
}
/* Allocate space for the insn map. */
rtx initial_value, final_value, increment;
if (precondition_loop_p (&initial_value, &final_value, &increment,
- loop_start, loop_end))
+ loop_start))
{
- register rtx diff, temp;
+ register rtx diff ;
enum machine_mode mode;
rtx *labels;
int abs_inc, neg_inc;
for (j = 0; j < max_labelno; j++)
if (local_label[j])
- map->label_map[j] = gen_label_rtx ();
+ set_label_in_map (map, j, gen_label_rtx ());
for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
if (local_regno[j])
{
map->reg_map[j] = gen_reg_rtx (GET_MODE (regno_reg_rtx[j]));
record_base_value (REGNO (map->reg_map[j]),
- regno_reg_rtx[j]);
+ regno_reg_rtx[j], 0);
}
/* The last copy needs the compare/branch insns at the end,
so reset copy_end here if the loop ends with a conditional
/* Set unroll type to MODULO now. */
unroll_type = UNROLL_MODULO;
loop_preconditioned = 1;
-
-#ifdef HAIFA
- /* Fix the initial value for the loop as needed. */
- if (loop_n_iterations <= 0)
- loop_start_value [uid_loop_num [INSN_UID (loop_start)]]
- = initial_value;
-#endif
}
}
for (j = 0; j < max_labelno; j++)
if (local_label[j])
- map->label_map[j] = gen_label_rtx ();
+ set_label_in_map (map, j, gen_label_rtx ());
for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; j++)
if (local_regno[j])
{
map->reg_map[j] = gen_reg_rtx (GET_MODE (regno_reg_rtx[j]));
record_base_value (REGNO (map->reg_map[j]),
- regno_reg_rtx[j]);
+ regno_reg_rtx[j], 0);
}
/* If loop starts with a branch to the test, then fix it so that
insn = PREV_INSN (copy_start);
pattern = PATTERN (insn);
- tem = map->label_map[CODE_LABEL_NUMBER
- (XEXP (SET_SRC (pattern), 0))];
- SET_SRC (pattern) = gen_rtx (LABEL_REF, VOIDmode, tem);
+ tem = get_label_from_map (map,
+ CODE_LABEL_NUMBER
+ (XEXP (SET_SRC (pattern), 0)));
+ SET_SRC (pattern) = gen_rtx_LABEL_REF (VOIDmode, tem);
/* Set the jump label so that it can be used by later loop unrolling
passes. */
whether divide is cheap. */
static int
-precondition_loop_p (initial_value, final_value, increment, loop_start,
- loop_end)
+precondition_loop_p (initial_value, final_value, increment, loop_start)
rtx *initial_value, *final_value, *increment;
- rtx loop_start, loop_end;
+ rtx loop_start;
{
if (loop_n_iterations > 0)
*final_value = GEN_INT (loop_n_iterations);
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Preconditioning: Success, number of iterations known, %d.\n",
- loop_n_iterations);
+ {
+ fputs ("Preconditioning: Success, number of iterations known, ",
+ loop_dump_stream);
+ fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
+ loop_n_iterations);
+ fputs (".\n", loop_dump_stream);
+ }
return 1;
}
to the iv. This procedure reconstructs the pattern computing the iv;
verifying that all operands are of the proper form.
+ PATTERN must be the result of single_set.
The return value is the amount that the giv is incremented by. */
static rtx
one of the LO_SUM rtx. */
if (GET_CODE (increment) == LO_SUM)
increment = XEXP (increment, 1);
+
+ /* Some ports store large constants in memory and add a REG_EQUAL
+ note to the store insn. */
+ else if (GET_CODE (increment) == MEM)
+ {
+ rtx note = find_reg_note (src_insn, REG_EQUAL, 0);
+ if (note)
+ increment = XEXP (note, 0);
+ }
+
else if (GET_CODE (increment) == IOR
|| GET_CODE (increment) == ASHIFT
|| GET_CODE (increment) == PLUS)
rtx start_label, loop_end, insert_before, copy_notes_from;
{
rtx insn, pattern;
- rtx tem, copy;
+ rtx set, tem, copy;
int dest_reg_was_split, i;
+#ifdef HAVE_cc0
rtx cc0_insn = 0;
+#endif
rtx final_label = 0;
rtx giv_inc, giv_dest_reg, giv_src_reg;
if (! last_iteration)
{
final_label = gen_label_rtx ();
- map->label_map[CODE_LABEL_NUMBER (start_label)] = final_label;
+ set_label_in_map (map, CODE_LABEL_NUMBER (start_label),
+ final_label);
}
else
- map->label_map[CODE_LABEL_NUMBER (start_label)] = start_label;
+ set_label_in_map (map, CODE_LABEL_NUMBER (start_label), start_label);
start_sequence ();
Do this before splitting the giv, since that may map the
SET_DEST to a new register. */
- if (GET_CODE (pattern) == SET
- && GET_CODE (SET_DEST (pattern)) == REG
- && addr_combined_regs[REGNO (SET_DEST (pattern))])
+ if ((set = single_set (insn))
+ && GET_CODE (SET_DEST (set)) == REG
+ && addr_combined_regs[REGNO (SET_DEST (set))])
{
struct iv_class *bl;
struct induction *v, *tv;
- int regno = REGNO (SET_DEST (pattern));
+ int regno = REGNO (SET_DEST (set));
- v = addr_combined_regs[REGNO (SET_DEST (pattern))];
+ v = addr_combined_regs[REGNO (SET_DEST (set))];
bl = reg_biv_class[REGNO (v->src_reg)];
/* Although the giv_inc amount is not needed here, we must call
we might accidentally delete insns generated immediately
below by emit_unrolled_add. */
- giv_inc = calculate_giv_inc (pattern, 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 = 0;
- if (GET_CODE (pattern) == SET
- && GET_CODE (SET_DEST (pattern)) == REG
- && splittable_regs[REGNO (SET_DEST (pattern))])
+ if ((set = single_set (insn))
+ && GET_CODE (SET_DEST (set)) == REG
+ && splittable_regs[REGNO (SET_DEST (set))])
{
- int regno = REGNO (SET_DEST (pattern));
+ int regno = REGNO (SET_DEST (set));
dest_reg_was_split = 1;
already computed above. */
if (giv_inc == 0)
- giv_inc = calculate_giv_inc (pattern, insn, regno);
- giv_dest_reg = SET_DEST (pattern);
- giv_src_reg = SET_DEST (pattern);
+ giv_inc = calculate_giv_inc (set, insn, regno);
+ giv_dest_reg = SET_DEST (set);
+ giv_src_reg = SET_DEST (set);
if (unroll_type == UNROLL_COMPLETELY)
{
tem = gen_reg_rtx (GET_MODE (giv_src_reg));
giv_dest_reg = tem;
map->reg_map[regno] = tem;
- record_base_value (REGNO (tem), giv_src_reg);
+ record_base_value (REGNO (tem),
+ giv_inc == const0_rtx
+ ? giv_src_reg
+ : gen_rtx_PLUS (GET_MODE (giv_src_reg),
+ giv_src_reg, giv_inc),
+ 1);
}
else
map->reg_map[regno] = giv_src_reg;
if (invert_exp (pattern, copy))
{
if (! redirect_exp (&pattern,
- map->label_map[CODE_LABEL_NUMBER
- (JUMP_LABEL (insn))],
+ get_label_from_map (map,
+ CODE_LABEL_NUMBER
+ (JUMP_LABEL (insn))),
exit_label, copy))
abort ();
}
emit_label_after (lab, jmp);
LABEL_NUSES (lab) = 0;
if (! redirect_exp (&pattern,
- map->label_map[CODE_LABEL_NUMBER
- (JUMP_LABEL (insn))],
+ get_label_from_map (map,
+ CODE_LABEL_NUMBER
+ (JUMP_LABEL (insn))),
lab, copy))
abort ();
}
/* Can't use the label_map for every insn, since this may be
the backward branch, and hence the label was not mapped. */
- if (GET_CODE (pattern) == SET)
+ if ((set = single_set (copy)))
{
- tem = SET_SRC (pattern);
+ tem = SET_SRC (set);
if (GET_CODE (tem) == LABEL_REF)
label = XEXP (tem, 0);
else if (GET_CODE (tem) == IF_THEN_ELSE)
for a switch statement. This label must have been mapped,
so just use the label_map to get the new jump label. */
JUMP_LABEL (copy)
- = map->label_map[CODE_LABEL_NUMBER (JUMP_LABEL (insn))];
+ = get_label_from_map (map,
+ CODE_LABEL_NUMBER (JUMP_LABEL (insn)));
}
/* If this is a non-local jump, then must increase the label
if (insn != start_label)
{
- copy = emit_label (map->label_map[CODE_LABEL_NUMBER (insn)]);
+ copy = emit_label (get_label_from_map (map,
+ CODE_LABEL_NUMBER (insn)));
map->const_age++;
}
break;
rtx loop_start, loop_end;
{
rtx p, q, target_insn;
+ rtx orig_loop_end = loop_end;
/* Stop before we get to the backward branch at the end of the loop. */
loop_end = prev_nonnote_insn (loop_end);
while (INSN_DELETED_P (insn))
insn = NEXT_INSN (insn);
- /* Check for the case where insn is the last insn in the loop. */
- if (insn == loop_end)
+ /* Check for the case where insn is the last insn in the loop. Deal
+ with the case where INSN was a deleted loop test insn, in which case
+ it will now be the NOTE_LOOP_END. */
+ if (insn == loop_end || insn == orig_loop_end)
return 0;
for (p = NEXT_INSN (insn); p != loop_end; p = NEXT_INSN (p))
mult_res = simplify_binary_operation (MULT, mode, mult1, mult2);
if (! mult_res)
- mult_res = gen_rtx (MULT, mode, mult1, mult2);
+ mult_res = gen_rtx_MULT (mode, mult1, mult2);
/* Again, put the constant second. */
if (GET_CODE (add1) == CONST_INT)
result = simplify_binary_operation (PLUS, mode, add1, mult_res);
if (! result)
- result = gen_rtx (PLUS, mode, add1, mult_res);
+ result = gen_rtx_PLUS (mode, add1, mult_res);
return result;
}
/* For increment, must check every instruction that sets it. Each
instruction must be executed only once each time through the loop.
- To verify this, we check that the the insn is always executed, and that
+ To verify this, we check that the insn is always executed, and that
there are no backward branches after the insn that branch to before it.
Also, the insn must have a mult_val of one (to make sure it really is
an increment). */
rtx loop_start, loop_end;
{
struct iv_class *bl;
- struct induction *v, *b;
+#if 0
+ struct induction *v;
+#endif
/* Clear the result values, in case no answer can be found. */
*initial_value = 0;
{
rtx tem = gen_reg_rtx (bl->biv->mode);
- record_base_value (REGNO (tem), bl->biv->add_val);
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
loop_start);
this insn will always be executed, no matter how the loop
exits. */
rtx tem = gen_reg_rtx (bl->biv->mode);
- record_base_value (REGNO (tem), bl->biv->add_val);
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
loop_start);
rtx last_addr = plus_constant (v->dest_reg,
INTVAL (giv_inc) * (unroll_number - 1));
- /* First check to see if either address would fail. */
- if (! validate_change (v->insn, v->location, v->dest_reg, 0)
- || ! validate_change (v->insn, v->location, last_addr, 0))
+ /* First check to see if either address would fail. Handle the fact
+ that we have may have a match_dup. */
+ if (! validate_replace_rtx (*v->location, v->dest_reg, v->insn)
+ || ! validate_replace_rtx (*v->location, last_addr, v->insn))
ret = 0;
- /* Now put things back the way they were before. This will always
+ /* Now put things back the way they were before. This should always
succeed. */
- validate_change (v->insn, v->location, orig_addr, 0);
+ if (! validate_replace_rtx (*v->location, orig_addr, v->insn))
+ abort ();
return ret;
}
&& (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
|| unroll_type == UNROLL_NAIVE)
&& v->giv_type != DEST_ADDR
- && ((REGNO_FIRST_UID (REGNO (v->dest_reg)) != INSN_UID (v->insn)
- /* Check for the case where the pseudo is set by a shift/add
- sequence, in which case the first insn setting the pseudo
- is the first insn of the shift/add sequence. */
- && (! (tem = find_reg_note (v->insn, REG_RETVAL, NULL_RTX))
- || (REGNO_FIRST_UID (REGNO (v->dest_reg))
- != INSN_UID (XEXP (tem, 0)))))
+ /* The next part is true if the pseudo is used outside the loop.
+ We assume that this is true for any pseudo created after loop
+ starts, because we don't have a reg_n_info entry for them. */
+ && (REGNO (v->dest_reg) >= max_reg_before_loop
+ || (REGNO_FIRST_UID (REGNO (v->dest_reg)) != INSN_UID (v->insn)
+ /* Check for the case where the pseudo is set by a shift/add
+ sequence, in which case the first insn setting the pseudo
+ is the first insn of the shift/add sequence. */
+ && (! (tem = find_reg_note (v->insn, REG_RETVAL, NULL_RTX))
+ || (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))]
>= INSN_LUID (loop_end)))
{
rtx tem = gen_reg_rtx (bl->biv->mode);
- record_base_value (REGNO (tem), bl->biv->add_val);
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
loop_start);
biv_initial_value = tem;
|| GET_CODE (XEXP (value, 1)) != CONST_INT))
{
rtx tem = gen_reg_rtx (v->mode);
- record_base_value (REGNO (tem), v->add_val);
+ 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);
value = tem;
Emit insn to initialize its value before loop start. */
rtx tem = gen_reg_rtx (v->mode);
- record_base_value (REGNO (tem), v->add_val);
- v->unrolled = 1;
+ record_base_value (REGNO (tem), v->add_val, 0);
/* If the address giv has a constant in its new_reg value,
then this constant can be pulled out and put in value,
if (v->dest_reg == tem
&& ! verify_addresses (v, giv_inc, unroll_number))
{
+ for (v2 = v->next_iv; v2; v2 = v2->next_iv)
+ if (v2->same_insn == v)
+ v2->same_insn = 0;
+
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Invalid address for giv at insn %d\n",
continue;
}
+ /* We set this after the address check, to guarantee that
+ the register will be initialized. */
+ v->unrolled = 1;
+
/* To initialize the new register, just move the value of
new_reg into it. This is not guaranteed to give a valid
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)),
+ emit_insn_before (gen_rtx_SET (VOIDmode, tem,
+ copy_rtx (v->new_reg)),
loop_start);
if (recog_memoized (PREV_INSN (loop_start)) < 0)
{
if the resulting address would be invalid. */
if (! verify_addresses (v, giv_inc, unroll_number))
{
+ for (v2 = v->next_iv; v2; v2 = v2->next_iv)
+ if (v2->same_insn == v)
+ v2->same_insn = 0;
+
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Invalid address for giv at insn %d\n",
/* HACK: Must also search the loop fall through exit, create a label_ref
here which points to the loop_end, and append the loop_number_exit_labels
list to it. */
- label = gen_rtx (LABEL_REF, VOIDmode, loop_end);
+ label = gen_rtx_LABEL_REF (VOIDmode, loop_end);
LABEL_NEXTREF (label) = loop_number_exit_labels[this_loop_num];
for ( ; label; label = LABEL_NEXTREF (label))
case it is needed later. */
tem = gen_reg_rtx (bl->biv->mode);
- record_base_value (REGNO (tem), bl->biv->add_val);
+ 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);
/* Put the final biv value in tem. */
tem = gen_reg_rtx (bl->biv->mode);
- record_base_value (REGNO (tem), bl->biv->add_val);
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
emit_iv_add_mult (increment, GEN_INT (loop_n_iterations),
bl->initial_value, tem, insert_before);
OSDN Git Service
