/* 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
Free Software Foundation, Inc.
Contributed by James E. Wilson, Cygnus Support/UC Berkeley.
#include "toplev.h"
#include "hard-reg-set.h"
#include "basic-block.h"
+#include "predict.h"
/* This controls which loops are unrolled, and by how much we unroll
them. */
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);
}
}
}
- 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));
}
emit_cmp_and_jump_insns (initial_value, final_value,
neg_inc ? LE : GE,
NULL_RTX, mode, 0, 0, labels[1]);
+ predict_insn_def (get_last_insn (), PRED_LOOP_CONDITION, NOT_TAKEN);
JUMP_LABEL (get_last_insn ()) = labels[1];
LABEL_NUSES (labels[1])++;
}
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,
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,
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
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,
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))];
- 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))];
+ /* If we failed to remap the note, something is awry. */
+ if (!insn)
+ abort ();
+
+ XEXP (note, 0) = insn;
+ }
+ }
+
+ notesp = &XEXP (note, 1);
+ }
}
/* Copy each instruction in the loop, substituting from map as appropriate.
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
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->list; bl; bl = bl->next)
{
biv_final_value = 0;
if (unroll_type != UNROLL_COMPLETELY
&& (loop->exit_count || unroll_type == UNROLL_NAIVE)
- && (REGNO_LAST_LUID (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
|| (REGNO_FIRST_LUID (bl->regno)
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",
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;
}
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. */
+ We must calculate it from NEW_REG. */
delete_insn (PREV_INSN (loop->start));
start_sequence ();
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,
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;
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 (extend_value_for_giv (v, 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;
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,
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;
/* Grab initial value, only useful if it is a constant. */
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);
}
if (REGNO (v->src_reg) >= ivs->n_regs)
abort ();
+ 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. */
{
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
OSDN Git Service
