/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992, 1993, 1994, 1995, 1997, 1998, 1999, 2000, 2001, 2002
+ Copyright (C) 1992, 1993, 1994, 1995, 1997, 1998, 1999, 2000, 2001,
+ 2002, 2003
Free Software Foundation, Inc.
Contributed by James E. Wilson, Cygnus Support/UC Berkeley.
/* Forward declarations. */
-static rtx simplify_cmp_and_jump_insns PARAMS ((enum rtx_code,
- enum machine_mode,
- rtx, rtx, rtx));
-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 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, int));
-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 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));
+static rtx simplify_cmp_and_jump_insns (enum rtx_code, enum machine_mode,
+ rtx, rtx, rtx);
+static void init_reg_map (struct inline_remap *, int);
+static rtx calculate_giv_inc (rtx, rtx, unsigned int);
+static rtx initial_reg_note_copy (rtx, struct inline_remap *);
+static void final_reg_note_copy (rtx *, struct inline_remap *);
+static void copy_loop_body (struct loop *, rtx, rtx,
+ struct inline_remap *, rtx, int,
+ enum unroll_types, rtx, rtx, rtx, rtx);
+static int find_splittable_regs (const struct loop *, enum unroll_types,
+ int);
+static int find_splittable_givs (const struct loop *, struct iv_class *,
+ enum unroll_types, rtx, int);
+static int reg_dead_after_loop (const struct loop *, rtx);
+static rtx fold_rtx_mult_add (rtx, rtx, rtx, enum machine_mode);
+static rtx remap_split_bivs (struct loop *, rtx);
+static rtx find_common_reg_term (rtx, rtx);
+static rtx subtract_reg_term (rtx, rtx);
+static rtx loop_find_equiv_value (const struct loop *, rtx);
+static rtx ujump_to_loop_cont (rtx, rtx);
/* Try to unroll one loop and split induction variables in the loop.
in loop.c. */
void
-unroll_loop (loop, insn_count, strength_reduce_p)
- struct loop *loop;
- int insn_count;
- int strength_reduce_p;
+unroll_loop (struct loop *loop, int insn_count, int strength_reduce_p)
{
struct loop_info *loop_info = LOOP_INFO (loop);
struct loop_ivs *ivs = LOOP_IVS (loop);
without initializing fields within the map structure.
To be safe, we use xcalloc to zero the memory. */
- map = (struct inline_remap *) xcalloc (1, sizeof (struct inline_remap));
+ map = xcalloc (1, sizeof (struct inline_remap));
/* Allocate the label map. */
if (max_labelno > 0)
{
- map->label_map = (rtx *) xcalloc (max_labelno, sizeof (rtx));
- local_label = (char *) xcalloc (max_labelno, sizeof (char));
+ map->label_map = xcalloc (max_labelno, sizeof (rtx));
+ local_label = xcalloc (max_labelno, sizeof (char));
}
/* Search the loop and mark all local labels, i.e. the ones which have to
/* Allocate space for the insn map. */
- map->insn_map = (rtx *) xmalloc (max_insnno * sizeof (rtx));
+ map->insn_map = xmalloc (max_insnno * sizeof (rtx));
/* Set this to zero, to indicate that we are doing loop unrolling,
not function inlining. */
preconditioning code and find_splittable_regs will never be used
to access the splittable_regs[] and addr_combined_regs[] arrays. */
- splittable_regs = (rtx *) xcalloc (maxregnum, sizeof (rtx));
- splittable_regs_updates = (int *) xcalloc (maxregnum, sizeof (int));
- addr_combined_regs
- = (struct induction **) xcalloc (maxregnum, sizeof (struct induction *));
- local_regno = (char *) xcalloc (maxregnum, sizeof (char));
+ splittable_regs = xcalloc (maxregnum, sizeof (rtx));
+ splittable_regs_updates = xcalloc (maxregnum, sizeof (int));
+ addr_combined_regs = xcalloc (maxregnum, sizeof (struct induction *));
+ local_regno = xcalloc (maxregnum, sizeof (char));
/* Mark all local registers, i.e. the ones which are referenced only
inside the loop. */
/* We must limit the generic test to max_reg_before_loop, because only
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
+ if (REGNO_FIRST_UID (r) > 0 && REGNO_FIRST_UID (r) < max_uid_for_loop
&& REGNO_FIRST_LUID (r) >= copy_start_luid
- && REGNO_LAST_UID (r) > 0 && REGNO_LAST_UID (r) <= max_uid_for_loop
+ && REGNO_LAST_UID (r) > 0 && REGNO_LAST_UID (r) < max_uid_for_loop
&& REGNO_LAST_LUID (r) <= copy_end_luid)
{
/* However, we must also check for loop-carried dependencies.
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));
+ map->reg_map = xmalloc (maxregnum * sizeof (rtx));
VARRAY_CONST_EQUIV_INIT (map->const_equiv_varray, maxregnum,
"unroll_loop_precondition");
/* Now emit a sequence of branches to jump to the proper precond
loop entry point. */
- labels = (rtx *) xmalloc (sizeof (rtx) * unroll_number);
+ labels = xmalloc (sizeof (rtx) * unroll_number);
for (i = 0; i < unroll_number; i++)
labels[i] = gen_label_rtx ();
emit_label_after (labels[unroll_number - i],
PREV_INSN (loop_start));
- memset ((char *) map->insn_map, 0, max_insnno * sizeof (rtx));
- memset ((char *) &VARRAY_CONST_EQUIV (map->const_equiv_varray, 0),
+ memset (map->insn_map, 0, max_insnno * sizeof (rtx));
+ memset (&VARRAY_CONST_EQUIV (map->const_equiv_varray, 0),
0, (VARRAY_SIZE (map->const_equiv_varray)
* sizeof (struct const_equiv_data)));
map->const_age = 0;
the constant maps also. */
maxregnum = max_reg_num ();
- map->reg_map = (rtx *) xmalloc (maxregnum * sizeof (rtx));
+ map->reg_map = xmalloc (maxregnum * sizeof (rtx));
init_reg_map (map, maxregnum);
for (i = 0; i < unroll_number; i++)
{
- memset ((char *) map->insn_map, 0, max_insnno * sizeof (rtx));
- memset ((char *) &VARRAY_CONST_EQUIV (map->const_equiv_varray, 0), 0,
+ memset (map->insn_map, 0, max_insnno * sizeof (rtx));
+ memset (&VARRAY_CONST_EQUIV (map->const_equiv_varray, 0), 0,
VARRAY_SIZE (map->const_equiv_varray) * sizeof (struct const_equiv_data));
map->const_age = 0;
free (map);
}
-/* A helper function for unroll_loop. Emit a compare and branch to
+/* A helper function for unroll_loop. Emit a compare and branch to
satisfy (CMP OP1 OP2), but pass this through the simplifier first.
If the branch turned out to be conditional, return it, otherwise
return NULL. */
static rtx
-simplify_cmp_and_jump_insns (code, mode, op0, op1, label)
- enum rtx_code code;
- enum machine_mode mode;
- rtx op0, op1, label;
+simplify_cmp_and_jump_insns (enum rtx_code code, enum machine_mode mode,
+ rtx op0, rtx op1, rtx label)
{
rtx t, insn;
reflected in RTX_COST. */
int
-precondition_loop_p (loop, initial_value, final_value, increment, mode)
- const struct loop *loop;
- rtx *initial_value, *final_value, *increment;
- enum machine_mode *mode;
+precondition_loop_p (const struct loop *loop, rtx *initial_value,
+ rtx *final_value, rtx *increment,
+ enum machine_mode *mode)
{
rtx loop_start = loop->start;
struct loop_info *loop_info = LOOP_INFO (loop);
modes. */
static void
-init_reg_map (map, maxregnum)
- struct inline_remap *map;
- int maxregnum;
+init_reg_map (struct inline_remap *map, int maxregnum)
{
int i;
The return value is the amount that the giv is incremented by. */
static rtx
-calculate_giv_inc (pattern, src_insn, regno)
- rtx pattern, src_insn;
- unsigned int regno;
+calculate_giv_inc (rtx pattern, rtx src_insn, unsigned int regno)
{
rtx increment;
rtx increment_total = 0;
the reg_map entries can change during copying. */
static rtx
-initial_reg_note_copy (notes, map)
- rtx notes;
- struct inline_remap *map;
+initial_reg_note_copy (rtx notes, struct inline_remap *map)
{
rtx copy;
/* Fixup insn references in copied REG_NOTES. */
static void
-final_reg_note_copy (notesp, map)
- rtx *notesp;
- struct inline_remap *map;
+final_reg_note_copy (rtx *notesp, struct inline_remap *map)
{
while (*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)
+ 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)
{
- *notesp = XEXP (note, 1);
- continue;
+ if (REG_NOTE_KIND (note) != REG_LABEL)
+ abort ();
}
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;
- }
+ XEXP (note, 0) = insn;
}
notesp = &XEXP (note, 1);
This is very similar to a loop in expand_inline_function. */
static void
-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;
- int last_iteration;
- enum unroll_types unroll_type;
- rtx start_label, loop_end, insert_before, copy_notes_from;
+copy_loop_body (struct loop *loop, rtx copy_start, rtx copy_end,
+ struct inline_remap *map, rtx exit_label,
+ int last_iteration, enum unroll_types unroll_type,
+ rtx start_label, rtx loop_end, rtx insert_before,
+ rtx copy_notes_from)
{
struct loop_ivs *ivs = LOOP_IVS (loop);
rtx insn, pattern;
copy = emit_insn (pattern);
}
REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
- INSN_SCOPE (copy) = INSN_SCOPE (insn);
+ INSN_LOCATOR (copy) = INSN_LOCATOR (insn);
/* If there is a REG_EQUAL note present whose value
is not loop invariant, then delete it, since it
pattern = copy_rtx_and_substitute (PATTERN (insn), map, 0);
copy = emit_jump_insn (pattern);
REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
- INSN_SCOPE (copy) = INSN_SCOPE (insn);
+ INSN_LOCATOR (copy) = INSN_LOCATOR (insn);
if (JUMP_LABEL (insn))
{
pattern = copy_rtx_and_substitute (PATTERN (insn), map, 0);
copy = emit_call_insn (pattern);
REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
- INSN_SCOPE (copy) = INSN_SCOPE (insn);
+ INSN_LOCATOR (copy) = INSN_LOCATOR (insn);
SIBLING_CALL_P (copy) = SIBLING_CALL_P (insn);
CONST_OR_PURE_CALL_P (copy) = CONST_OR_PURE_CALL_P (insn);
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)
- || (last_iteration && unroll_type != UNROLL_COMPLETELY)))
- copy = emit_note (NOTE_SOURCE_FILE (insn),
- NOTE_LINE_NUMBER (insn));
+ && 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)
+ || (last_iteration
+ && unroll_type != UNROLL_COMPLETELY)))
+ copy = emit_note_copy (insn);
else
copy = 0;
break;
can be a NOTE_INSN_LOOP_CONT note if there is no VTOP note,
as in a do .. while loop. */
if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_VTOP
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_CONT)
- emit_note (NOTE_SOURCE_FILE (insn), NOTE_LINE_NUMBER (insn));
+ && ((NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_VTOP
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_CONT)))
+ emit_note_copy (insn);
}
}
won't fit in the immediate field of a PLUS insns. */
void
-emit_unrolled_add (dest_reg, src_reg, increment)
- rtx dest_reg, src_reg, increment;
+emit_unrolled_add (rtx dest_reg, rtx src_reg, rtx increment)
{
rtx result;
and uses a negligible amount of CPU time on average. */
int
-back_branch_in_range_p (loop, insn)
- const struct loop *loop;
- rtx insn;
+back_branch_in_range_p (const struct loop *loop, rtx insn)
{
rtx p, q, target_insn;
rtx loop_start = loop->start;
value of giv's. */
static rtx
-fold_rtx_mult_add (mult1, mult2, add1, mode)
- rtx mult1, mult2, add1;
- enum machine_mode mode;
+fold_rtx_mult_add (rtx mult1, rtx mult2, rtx add1, enum machine_mode mode)
{
rtx temp, mult_res;
rtx result;
if it can be calculated. Otherwise, returns 0. */
rtx
-biv_total_increment (bl)
- const struct iv_class *bl;
+biv_total_increment (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, unroll_number)
- const struct loop *loop;
- enum unroll_types unroll_type;
- int unroll_number;
+find_splittable_regs (const struct loop *loop,
+ enum unroll_types unroll_type, int unroll_number)
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
Return the number of instructions that set splittable registers. */
static int
-find_splittable_givs (loop, bl, unroll_type, increment, unroll_number)
- const struct loop *loop;
- struct iv_class *bl;
- enum unroll_types unroll_type;
- rtx increment;
- int unroll_number ATTRIBUTE_UNUSED;
+find_splittable_givs (const struct loop *loop, struct iv_class *bl,
+ enum unroll_types unroll_type, rtx increment,
+ int unroll_number ATTRIBUTE_UNUSED)
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct induction *v, *v2;
it can search past if statements and other similar structures. */
static int
-reg_dead_after_loop (loop, reg)
- const struct loop *loop;
- rtx reg;
+reg_dead_after_loop (const struct loop *loop, rtx reg)
{
rtx insn, label;
enum rtx_code code;
code = GET_CODE (insn);
if (GET_RTX_CLASS (code) == 'i')
{
- rtx set;
+ rtx set, note;
if (reg_referenced_p (reg, PATTERN (insn)))
return 0;
+ note = find_reg_equal_equiv_note (insn);
+ if (note && reg_overlap_mentioned_p (reg, XEXP (note, 0)))
+ return 0;
+
set = single_set (insn);
if (set && rtx_equal_p (SET_DEST (set), reg))
break;
the end of the loop. If we can do it, return that value. */
rtx
-final_biv_value (loop, bl)
- const struct loop *loop;
- struct iv_class *bl;
+final_biv_value (const struct loop *loop, struct iv_class *bl)
{
unsigned HOST_WIDE_INT n_iterations = LOOP_INFO (loop)->n_iterations;
rtx increment, tem;
the end of the loop. If we can do it, return that value. */
rtx
-final_giv_value (loop, v)
- const struct loop *loop;
- struct induction *v;
+final_giv_value (const struct loop *loop, struct induction *v)
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
the SET_SRC of REG. */
static rtx
-loop_find_equiv_value (loop, reg)
- const struct loop *loop;
- rtx reg;
+loop_find_equiv_value (const struct loop *loop, rtx reg)
{
rtx loop_start = loop->start;
rtx insn, set;
the proper form. */
static rtx
-subtract_reg_term (op, reg)
- rtx op, reg;
+subtract_reg_term (rtx op, rtx reg)
{
if (op == reg)
return const0_rtx;
REG or a PLUS of a REG. */
static rtx
-find_common_reg_term (op0, op1)
- rtx op0, op1;
+find_common_reg_term (rtx op0, rtx op1)
{
if ((GET_CODE (op0) == REG || GET_CODE (op0) == PLUS)
&& (GET_CODE (op1) == REG || GET_CODE (op1) == PLUS))
be calculated, otherwise returns zero. */
unsigned HOST_WIDE_INT
-loop_iterations (loop)
- struct loop *loop;
+loop_iterations (struct loop *loop)
{
struct loop_info *loop_info = LOOP_INFO (loop);
struct loop_ivs *ivs = LOOP_IVS (loop);
if (find_common_reg_term (temp, reg2))
initial_value = temp;
- else
+ else if (loop_invariant_p (loop, reg2))
{
/* Find what reg2 is equivalent to. Hopefully it will
either be reg1 or reg1 plus a constant. Let's ignore
copying. */
static rtx
-remap_split_bivs (loop, x)
- struct loop *loop;
- rtx x;
+remap_split_bivs (struct loop *loop, rtx x)
{
struct loop_ivs *ivs = LOOP_IVS (loop);
enum rtx_code code;
must dominate LAST_UID. */
int
-set_dominates_use (regno, first_uid, last_uid, copy_start, copy_end)
- int regno;
- int first_uid;
- int last_uid;
- rtx copy_start;
- rtx copy_end;
+set_dominates_use (int regno, int first_uid, int last_uid, rtx copy_start,
+ rtx copy_end)
{
int passed_jump = 0;
rtx p = NEXT_INSN (copy_start);
deleted so that we execute the single iteration. */
static rtx
-ujump_to_loop_cont (loop_start, loop_cont)
- rtx loop_start;
- rtx loop_cont;
+ujump_to_loop_cont (rtx loop_start, rtx loop_cont)
{
rtx x, label, label_ref;