/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992 Free Software Foundation, Inc.
+ Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc.
Contributed by James E. Wilson, Cygnus Support/UC Berkeley.
This file is part of GNU CC.
- On traditional architectures, unrolling a non-constant bound loop
is a win if there is a giv whose only use is in memory addresses, the
- memory addresses can be split, and hence giv incremenets can be
+ memory addresses can be split, and hence giv increments can be
eliminated.
- It is also a win if the loop is executed many times, and preconditioning
can be performed for the loop.
static int find_splittable_regs ();
static int find_splittable_givs ();
static rtx fold_rtx_mult_add ();
+static rtx remap_split_bivs ();
/* Try to unroll one loop and split induction variables in the loop.
The loop is described by the arguments LOOP_END, INSN_COUNT, and
- LOOP_START. END_INSERT_BEDFORE indicates where insns should be added
+ LOOP_START. 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.
rtx exit_label = 0;
rtx start_label;
struct iv_class *bl;
- struct induction *v;
int splitting_not_safe = 0;
enum unroll_types unroll_type;
int loop_preconditioned = 0;
"Unrolling failure: unknown insns between BEG note and loop label.\n");
return;
}
+ if (LABEL_NAME (start_label))
+ {
+ /* The jump optimization pass must have combined the original start label
+ with a named label for a goto. We can't unroll this case because
+ jumps which go to the named label must be handled differently than
+ jumps to the loop start, and it is impossible to differentiate them
+ in this case. */
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Unrolling failure: loop start label is gone\n");
+ return;
+ }
if (unroll_type == UNROLL_NAIVE
&& GET_CODE (last_loop_insn) == BARRIER
map = (struct inline_remap *) alloca (sizeof (struct inline_remap));
+ map->integrating = 0;
+
/* Allocate the label map. */
if (max_labelno > 0)
It is safe to do this here, since the extra registers created by the
preconditioning code and find_splittable_regs will never be used
- to accees the splittable_regs[] and addr_combined_regs[] arrays. */
+ to access the splittable_regs[] and addr_combined_regs[] arrays. */
splittable_regs = (rtx *) alloca (maxregnum * sizeof (rtx));
- bzero (splittable_regs, maxregnum * sizeof (rtx));
+ bzero ((char *) splittable_regs, maxregnum * sizeof (rtx));
splittable_regs_updates = (int *) alloca (maxregnum * sizeof (int));
- bzero (splittable_regs_updates, maxregnum * sizeof (int));
+ bzero ((char *) splittable_regs_updates, maxregnum * sizeof (int));
addr_combined_regs
= (struct induction **) alloca (maxregnum * sizeof (struct induction *));
- bzero (addr_combined_regs, maxregnum * sizeof (struct induction *));
+ bzero ((char *) addr_combined_regs, maxregnum * sizeof (struct induction *));
/* If this loop requires exit tests when unrolled, check to see if we
can precondition the loop so as to make the exit tests unnecessary.
* sizeof (unsigned));
map->const_equiv_map_size = maxregnum;
global_const_equiv_map = map->const_equiv_map;
+ global_const_equiv_map_size = maxregnum;
init_reg_map (map, maxregnum);
improperly shared rtl. */
diff = expand_binop (mode, sub_optab, copy_rtx (final_value),
- copy_rtx (initial_value), 0, 0,
+ copy_rtx (initial_value), NULL_RTX, 0,
OPTAB_LIB_WIDEN);
/* Now calculate (diff % (unroll * abs (increment))) by using an
and instruction. */
diff = expand_binop (GET_MODE (diff), and_optab, diff,
- gen_rtx (CONST_INT, VOIDmode,
- unroll_number * abs_inc - 1),
- 0, 0, OPTAB_LIB_WIDEN);
+ 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. */
else
cmp_const = i;
- emit_cmp_insn (diff, gen_rtx (CONST_INT, VOIDmode,
- abs_inc * cmp_const),
- EQ, 0, mode, 0, 0);
+ emit_cmp_insn (diff, GEN_INT (abs_inc * cmp_const),
+ EQ, NULL_RTX, mode, 0, 0);
if (i == 0)
emit_jump_insn (gen_beq (labels[i]));
else
cmp_const = abs_inc * (unroll_number - 1) + 1;
- emit_cmp_insn (diff, gen_rtx (CONST_INT, VOIDmode, cmp_const),
- EQ, 0, mode, 0, 0);
+ emit_cmp_insn (diff, GEN_INT (cmp_const), EQ, NULL_RTX,
+ mode, 0, 0);
if (neg_inc)
emit_jump_insn (gen_ble (labels[0]));
emit_label_after (labels[unroll_number - i],
PREV_INSN (loop_start));
- bzero (map->insn_map, max_insnno * sizeof (rtx));
- bzero (map->const_equiv_map, maxregnum * sizeof (rtx));
- bzero (map->const_age_map, maxregnum * sizeof (unsigned));
+ bzero ((char *) map->insn_map, max_insnno * sizeof (rtx));
+ bzero ((char *) map->const_equiv_map, maxregnum * sizeof (rtx));
+ bzero ((char *) map->const_age_map,
+ maxregnum * sizeof (unsigned));
map->const_age = 0;
for (j = 0; j < max_labelno; j++)
map->const_equiv_map = (rtx *) alloca (new_maxregnum * sizeof (rtx));
map->const_age_map = (unsigned *) alloca (new_maxregnum * sizeof (unsigned));
+ map->const_equiv_map_size = new_maxregnum;
global_const_equiv_map = map->const_equiv_map;
+ global_const_equiv_map_size = new_maxregnum;
/* Search the list of bivs and givs to find ones which need to be remapped
when split, and set their reg_map entry appropriately. */
/* 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
- the compare instruction at the end of the loop to refer to the new
+ the compare/jump instruction at the end of the loop to refer to the new
registers. This compare isn't copied, so the registers used in it
will never be replaced if it isn't done here. */
if (unroll_type == UNROLL_MODULO)
{
insn = NEXT_INSN (copy_end);
- if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == SET)
- {
-#if 0
- /* If non-reduced/final-value givs were split, then this would also
- have to remap those givs. */
-#endif
-
- tem = SET_SRC (PATTERN (insn));
- /* The set source is a register. */
- if (GET_CODE (tem) == REG)
- {
- if (REGNO (tem) < max_reg_before_loop
- && reg_iv_type[REGNO (tem)] == BASIC_INDUCT)
- SET_SRC (PATTERN (insn))
- = reg_biv_class[REGNO (tem)]->biv->src_reg;
- }
- else
- {
- /* The set source is a compare of some sort. */
- tem = XEXP (SET_SRC (PATTERN (insn)), 0);
- if (GET_CODE (tem) == REG
- && REGNO (tem) < max_reg_before_loop
- && reg_iv_type[REGNO (tem)] == BASIC_INDUCT)
- XEXP (SET_SRC (PATTERN (insn)), 0)
- = reg_biv_class[REGNO (tem)]->biv->src_reg;
-
- tem = XEXP (SET_SRC (PATTERN (insn)), 1);
- if (GET_CODE (tem) == REG
- && REGNO (tem) < max_reg_before_loop
- && reg_iv_type[REGNO (tem)] == BASIC_INDUCT)
- XEXP (SET_SRC (PATTERN (insn)), 1)
- = reg_biv_class[REGNO (tem)]->biv->src_reg;
- }
- }
+ if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
+ PATTERN (insn) = remap_split_bivs (PATTERN (insn));
}
/* For unroll_number - 1 times, make a copy of each instruction
for (i = 0; i < unroll_number; i++)
{
- bzero (map->insn_map, max_insnno * sizeof (rtx));
- bzero (map->const_equiv_map, new_maxregnum * sizeof (rtx));
- bzero (map->const_age_map, new_maxregnum * sizeof (unsigned));
+ bzero ((char *) map->insn_map, max_insnno * sizeof (rtx));
+ bzero ((char *) map->const_equiv_map, new_maxregnum * sizeof (rtx));
+ bzero ((char *) map->const_age_map, new_maxregnum * sizeof (unsigned));
map->const_age = 0;
for (j = 0; j < max_labelno; j++)
not taken. */
if (exit_label)
emit_label_after (exit_label, loop_end);
-
- /* If debugging, we must replicate the tree nodes corresponsing to the blocks
- inside the loop, so that the original one to one mapping will remain. */
-
- if (write_symbols != NO_DEBUG)
- {
- int copies = unroll_number;
-
- if (loop_preconditioned)
- copies += unroll_number - 1;
-
- unroll_block_trees (uid_loop_num[INSN_UID (loop_start)], copies);
- }
}
\f
/* Return true if the loop can be safely, and profitably, preconditioned
rtx *initial_value, *final_value, *increment;
rtx loop_start, loop_end;
{
- int unsigned_compare, compare_dir;
if (loop_n_iterations > 0)
{
*initial_value = const0_rtx;
*increment = const1_rtx;
- *final_value = gen_rtx (CONST_INT, VOIDmode, loop_n_iterations);
+ *final_value = GEN_INT (loop_n_iterations);
if (loop_dump_stream)
fprintf (loop_dump_stream,
/* Must ensure that final_value is invariant, so call invariant_p to
check. Before doing so, must check regno against max_reg_before_loop
- to make sure that the register is in the range convered by invariant_p.
+ to make sure that the register is in the range covered by invariant_p.
If it isn't, then it is most likely a biv/giv which by definition are
not invariant. */
if ((GET_CODE (loop_final_value) == REG
int regno;
{
rtx increment;
+ rtx increment_total = 0;
+ int tries = 0;
+ retry:
/* Verify that we have an increment insn here. First check for a plus
as the set source. */
if (GET_CODE (SET_SRC (pattern)) != PLUS)
{
/* SR sometimes puts the constant in a register, especially if it is
too big to be an add immed operand. */
- increment = SET_SRC (PATTERN (PREV_INSN (src_insn)));
+ src_insn = PREV_INSN (src_insn);
+ increment = SET_SRC (PATTERN (src_insn));
/* 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
one of the LO_SUM rtx. */
if (GET_CODE (increment) == LO_SUM)
increment = XEXP (increment, 1);
+ else if (GET_CODE (increment) == IOR)
+ {
+ /* The rs6000 port loads some constants with IOR. */
+ rtx second_part = XEXP (increment, 1);
+
+ src_insn = PREV_INSN (src_insn);
+ increment = SET_SRC (PATTERN (src_insn));
+ /* Don't need the last insn anymore. */
+ delete_insn (get_last_insn ());
+
+ if (GET_CODE (second_part) != CONST_INT
+ || GET_CODE (increment) != CONST_INT)
+ abort ();
+
+ increment = GEN_INT (INTVAL (increment) | INTVAL (second_part));
+ }
if (GET_CODE (increment) != CONST_INT)
abort ();
- /* The insn loading the constant into a register is not longer needed,
+ /* The insn loading the constant into a register is no longer needed,
so delete it. */
delete_insn (get_last_insn ());
}
- /* Check that the source register is the same as the dest register. */
+ if (increment_total)
+ increment_total = GEN_INT (INTVAL (increment_total) + INTVAL (increment));
+ else
+ increment_total = increment;
+
+ /* Check that the source register is the same as the register we expected
+ to see as the source. If not, something is seriously wrong. */
if (GET_CODE (XEXP (SET_SRC (pattern), 0)) != REG
|| REGNO (XEXP (SET_SRC (pattern), 0)) != regno)
+ {
+ /* Some machines (e.g. the romp), may emit two add instructions for
+ certain constants, so lets try looking for another add immediately
+ before this one if we have only seen one add insn so far. */
+
+ if (tries == 0)
+ {
+ tries++;
+
+ src_insn = PREV_INSN (src_insn);
+ pattern = PATTERN (src_insn);
+
+ delete_insn (get_last_insn ());
+
+ goto retry;
+ }
+
+ abort ();
+ }
+
+ return increment_total;
+}
+
+/* Copy REG_NOTES, except for insn references, because not all insn_map
+ entries are valid yet. We do need to copy registers now though, because
+ the reg_map entries can change during copying. */
+
+static rtx
+initial_reg_note_copy (notes, map)
+ rtx notes;
+ struct inline_remap *map;
+{
+ rtx copy;
+
+ if (notes == 0)
+ return 0;
+
+ copy = rtx_alloc (GET_CODE (notes));
+ PUT_MODE (copy, GET_MODE (notes));
+
+ if (GET_CODE (notes) == EXPR_LIST)
+ XEXP (copy, 0) = copy_rtx_and_substitute (XEXP (notes, 0), map);
+ else if (GET_CODE (notes) == INSN_LIST)
+ /* Don't substitute for these yet. */
+ XEXP (copy, 0) = XEXP (notes, 0);
+ else
abort ();
- return increment;
+ XEXP (copy, 1) = initial_reg_note_copy (XEXP (notes, 1), map);
+
+ return copy;
}
+/* Fixup insn references in copied REG_NOTES. */
+
+static void
+final_reg_note_copy (notes, map)
+ rtx notes;
+ struct inline_remap *map;
+{
+ rtx note;
+
+ 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))];
+}
/* Copy each instruction in the loop, substituting from map as appropriate.
This is very similar to a loop in expand_inline_function. */
copy_notes_from)
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;
for (tv = bl->giv; tv; tv = tv->next_iv)
if (tv->giv_type == DEST_ADDR && tv->same == v)
{
- /* Increment the giv by the amount that was calculated in
- find_splittable_givs, and saved in add_val. */
- tv->dest_reg = plus_constant (tv->dest_reg,
- INTVAL (tv->add_val));
+ int this_giv_inc = INTVAL (giv_inc);
+
+ /* Scale this_giv_inc if the multiplicative factors of
+ the two givs are different. */
+ if (tv->mult_val != v->mult_val)
+ this_giv_inc = (this_giv_inc / INTVAL (v->mult_val)
+ * INTVAL (tv->mult_val));
+
+ tv->dest_reg = plus_constant (tv->dest_reg, this_giv_inc);
*tv->location = tv->dest_reg;
if (last_iteration && unroll_type != UNROLL_COMPLETELY)
else
dest_reg = XEXP (tv->dest_reg, 0);
- /* tv->dest_reg may actually be a (PLUS (REG) (CONST))
- here, so we must call plus_constant to add
- the const_adjust amount before calling
- emit_unrolled_add below. */
- value = plus_constant (tv->dest_reg, tv->const_adjust);
-
- /* The constant could be too large for an add
- immediate, so can't directly emit an insn here. */
- emit_unrolled_add (dest_reg, XEXP (value, 0),
- XEXP (value, 1));
+ /* Check for shared address givs, and avoid
+ incrementing the shared psuedo reg more than
+ once. */
+ if (! (tv != v && tv->insn == v->insn
+ && tv->new_reg == v->new_reg))
+ {
+ /* tv->dest_reg may actually be a (PLUS (REG)
+ (CONST)) here, so we must call plus_constant
+ to add the const_adjust amount before calling
+ emit_unrolled_add below. */
+ value = plus_constant (tv->dest_reg,
+ tv->const_adjust);
+
+ /* The constant could be too large for an add
+ immediate, so can't directly emit an insn
+ here. */
+ emit_unrolled_add (dest_reg, XEXP (value, 0),
+ XEXP (value, 1));
+ }
/* Reset the giv to be just the register again, in case
it is used after the set we have just emitted.
#endif
splittable_regs[regno]
- = gen_rtx (CONST_INT, VOIDmode,
- INTVAL (giv_inc)
+ = GEN_INT (INTVAL (giv_inc)
+ INTVAL (splittable_regs[regno]));
giv_inc = splittable_regs[regno];
pattern = copy_rtx_and_substitute (pattern, map);
copy = emit_insn (pattern);
}
- /* REG_NOTES will be copied later. */
+ REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
#ifdef HAVE_cc0
/* If this insn is setting CC0, it may need to look at
{
int regno = REGNO (SET_DEST (pattern));
- if (map->const_age_map[regno] == map->const_age)
+ if (regno < map->const_equiv_map_size
+ && map->const_age_map[regno] == map->const_age)
map->const_age_map[regno] = -1;
}
break;
case JUMP_INSN:
+ pattern = copy_rtx_and_substitute (PATTERN (insn), map);
+ 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)
{
case to be a branch past the end of the loop, and the
original jump label case to fall_through. */
- int fall_through;
-
- /* Never map the label in this case. */
- pattern = copy_rtx (PATTERN (insn));
-
- /* Assume a conditional branch, since the code above
- does not let unconditional branches be copied. */
- if (! condjump_p (insn))
+ if (! invert_exp (pattern, copy)
+ || ! redirect_exp (&pattern,
+ map->label_map[CODE_LABEL_NUMBER
+ (JUMP_LABEL (insn))],
+ exit_label, copy))
abort ();
- fall_through
- = (XEXP (SET_SRC (PATTERN (insn)), 2) == pc_rtx) + 1;
-
- /* Set the fall through case to the exit label. Must
- create a new label_ref since they can't be shared. */
- XEXP (SET_SRC (pattern), fall_through)
- = gen_rtx (LABEL_REF, VOIDmode, exit_label);
-
- /* Set the original branch case to fall through. */
- XEXP (SET_SRC (pattern), 3 - fall_through)
- = pc_rtx;
}
- else
- pattern = copy_rtx_and_substitute (PATTERN (insn), map);
-
- copy = emit_jump_insn (pattern);
#ifdef HAVE_cc0
if (cc0_insn)
later passes of unroll_loop, if INSN had jump label set. */
if (JUMP_LABEL (insn))
{
+ rtx label = 0;
+
/* 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)
{
tem = SET_SRC (pattern);
if (GET_CODE (tem) == LABEL_REF)
- JUMP_LABEL (copy) = XEXP (tem, 0);
+ label = XEXP (tem, 0);
else if (GET_CODE (tem) == IF_THEN_ELSE)
{
if (XEXP (tem, 1) != pc_rtx)
- JUMP_LABEL (copy) = XEXP (XEXP (tem, 1), 0);
+ label = XEXP (XEXP (tem, 1), 0);
else
- JUMP_LABEL (copy) = XEXP (XEXP (tem, 2), 0);
+ label = XEXP (XEXP (tem, 2), 0);
}
- else
- abort ();
}
+
+ if (label && GET_CODE (label) == CODE_LABEL)
+ JUMP_LABEL (copy) = label;
else
{
/* An unrecognizable jump insn, probably the entry jump
/* 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
case CALL_INSN:
pattern = copy_rtx_and_substitute (PATTERN (insn), map);
copy = emit_call_insn (pattern);
+ REG_NOTES (copy) = initial_reg_note_copy (REG_NOTES (insn), map);
+
+ /* Because the USAGE information potentially contains objects other
+ than hard registers, we need to copy it. */
+ CALL_INSN_FUNCTION_USAGE (copy) =
+ copy_rtx_and_substitute (CALL_INSN_FUNCTION_USAGE (insn), map);
#ifdef HAVE_cc0
if (cc0_insn)
break;
case NOTE:
- if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED)
+ /* VTOP notes are valid only before the loop exit test. If placed
+ anywhere else, loop may generate bad code. */
+
+ if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_DELETED
+ && (NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_VTOP
+ || (last_iteration && unroll_type != UNROLL_COMPLETELY)))
copy = emit_note (NOTE_SOURCE_FILE (insn),
NOTE_LINE_NUMBER (insn));
else
}
while (insn != copy_end);
- /* Now copy the REG_NOTES. */
+ /* Now finish coping the REG_NOTES. */
insn = copy_start;
do
{
if ((GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
|| GET_CODE (insn) == CALL_INSN)
&& map->insn_map[INSN_UID (insn)])
- REG_NOTES (map->insn_map[INSN_UID (insn)])
- = copy_rtx_and_substitute (REG_NOTES (insn), map);
+ final_reg_note_copy (REG_NOTES (map->insn_map[INSN_UID (insn)]), map);
}
while (insn != copy_end);
is a backward branch in that range that branches to somewhere between
LOOP_START and INSN. Returns 0 otherwise. */
-/* ??? This is quadratic algorithm. Could be rewriten to be linear.
+/* ??? This is quadratic algorithm. Could be rewritten to be linear.
In practice, this is not a problem, because this function is seldom called,
and uses a negligible amount of CPU time on average. */
It must be set to the initial value of the induction variable here.
Otherwise, splittable_regs will hold the difference between the current
value of the induction variable and the value the induction variable had
- at the top of the loop. It must be set to the value 0 here. */
+ at the top of the loop. It must be set to the value 0 here.
+
+ Returns the total number of instructions that set registers that are
+ splittable. */
/* ?? If the loop is only unrolled twice, then most of the restrictions to
constant values are unnecessary, since we can easily calculate increment
int unroll_number;
{
struct iv_class *bl;
+ struct induction *v;
rtx increment, tem;
rtx biv_final_value;
int biv_splittable;
&& ! (biv_final_value = final_biv_value (bl, loop_start, loop_end)))
biv_splittable = 0;
+ /* If any of the insns setting the BIV don't do so with a simple
+ PLUS, we don't know how to split it. */
+ for (v = bl->biv; biv_splittable && v; v = v->next_iv)
+ if ((tem = single_set (v->insn)) == 0
+ || GET_CODE (SET_DEST (tem)) != REG
+ || REGNO (SET_DEST (tem)) != bl->regno
+ || GET_CODE (SET_SRC (tem)) != PLUS)
+ biv_splittable = 0;
+
/* If final value is non-zero, then must emit an instruction which sets
the value of the biv to the proper value. This is done after
handling all of the givs, since some of them may need to use the
we can treat the last one specially. */
splittable_regs_updates[bl->regno] = bl->biv_count;
-
- result++;
+ result += bl->biv_count;
if (loop_dump_stream)
fprintf (loop_dump_stream,
depend on it may be splittable if the biv is live outside the
loop, and the givs aren't. */
- result = find_splittable_givs (bl, unroll_type, loop_start, loop_end,
- increment, unroll_number, result);
+ result += find_splittable_givs (bl, unroll_type, loop_start, loop_end,
+ increment, unroll_number);
/* If final value is non-zero, then must emit an instruction which sets
the value of the biv to the proper value. This is done after
}
/* For every giv based on the biv BL, check to determine whether it is
- splittable. This is a subroutine to find_splittable_regs (). */
+ splittable. This is a subroutine to find_splittable_regs ().
+
+ Return the number of instructions that set splittable registers. */
static int
find_splittable_givs (bl, unroll_type, loop_start, loop_end, increment,
- unroll_number, result)
+ unroll_number)
struct iv_class *bl;
enum unroll_types unroll_type;
rtx loop_start, loop_end;
rtx increment;
- int unroll_number, result;
+ int unroll_number;
{
struct induction *v;
rtx final_value;
rtx tem;
+ int result = 0;
for (v = bl->giv; v; v = v->next_iv)
{
/* 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, 0))
+ && (! (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. */
giv's initial value. Otherwise, save the constant zero for it. */
if (unroll_type == UNROLL_COMPLETELY)
- /* It is not safe to use bl->initial_value here, because it may not
- be invariant. It is safe to use the initial value stored in
- the splittable_regs array. */
- value = fold_rtx_mult_add (v->mult_val, splittable_regs[bl->regno],
- v->add_val, v->mode);
+ {
+ /* It is not safe to use bl->initial_value here, because it may not
+ be invariant. It is safe to use the initial value stored in
+ the splittable_regs array if it is set. In rare cases, it won't
+ be set, so then we do exactly the same thing as
+ find_splittable_regs does to get a safe value. */
+ rtx biv_initial_value;
+
+ if (splittable_regs[bl->regno])
+ biv_initial_value = splittable_regs[bl->regno];
+ else if (GET_CODE (bl->initial_value) != REG
+ || (REGNO (bl->initial_value) != bl->regno
+ && REGNO (bl->initial_value) >= FIRST_PSEUDO_REGISTER))
+ biv_initial_value = bl->initial_value;
+ else
+ {
+ rtx tem = gen_reg_rtx (bl->biv->mode);
+
+ emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
+ loop_start);
+ biv_initial_value = tem;
+ }
+ value = fold_rtx_mult_add (v->mult_val, biv_initial_value,
+ v->add_val, v->mode);
+ }
else
value = const0_rtx;
if (v->new_reg)
{
- /* If the giv is an address destination, it could be something other
- than a simple register, these have to be treated differently. */
- if (v->giv_type == DEST_REG)
- splittable_regs[REGNO (v->new_reg)] = value;
-
- /* If an addr giv was combined with another addr giv, then we
- can only split this giv if the addr giv it was combined with
- was reduced. This is because the value of v->new_reg is
- meaningless in this case. (There is no problem if it was
- combined with a dest_reg giv which wasn't reduced, v->new_reg
- is still meaningful in this case.) */
-
- else if (v->same && v->same->giv_type == DEST_ADDR
- && ! v->same->new_reg)
+ /* If a giv was combined with another giv, then we can only split
+ this giv if the giv it was combined with was reduced. This
+ is because the value of v->new_reg is meaningless in this
+ case. */
+ if (v->same && ! v->same->new_reg)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "DEST_ADDR giv not split, because combined with unreduced DEST_ADDR giv.\n");
+ "giv combined with unreduced giv not split.\n");
+ continue;
+ }
+ /* If the giv is an address destination, it could be something other
+ than a simple register, these have to be treated differently. */
+ else if (v->giv_type == DEST_REG)
+ {
+ /* If value is not a constant, register, or register plus
+ constant, then compute its value into a register before
+ loop start. This prevents illegal rtx sharing, and should
+ generate better code. We can use bl->initial_value here
+ instead of splittable_regs[bl->regno] because this code
+ is going before the loop start. */
+ if (unroll_type == UNROLL_COMPLETELY
+ && GET_CODE (value) != CONST_INT
+ && GET_CODE (value) != REG
+ && (GET_CODE (value) != PLUS
+ || GET_CODE (XEXP (value, 0)) != REG
+ || GET_CODE (XEXP (value, 1)) != CONST_INT))
+ {
+ rtx tem = gen_reg_rtx (v->mode);
+ emit_iv_add_mult (bl->initial_value, v->mult_val,
+ v->add_val, tem, loop_start);
+ value = tem;
+ }
+
+ splittable_regs[REGNO (v->new_reg)] = value;
}
else
{
the work of simplifying multiple address givs to the
following cse pass. */
+ /* As a special case, if we have multiple identical address givs
+ within a single instruction, then we do use a single psuedo
+ reg for both. This is necessary in case one is a match_dup
+ of the other. */
+
v->const_adjust = 0;
- if (unroll_type != UNROLL_COMPLETELY)
+
+ if (v->same && v->same->insn == v->insn
+ && v->new_reg == v->same->new_reg)
+ {
+ v->dest_reg = v->same->dest_reg;
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Sharing address givs with reg %d\n",
+ REGNO (v->dest_reg));
+ }
+ else if (unroll_type != UNROLL_COMPLETELY)
{
/* If not completely unrolling the loop, then create a new
register to hold the split value of the DEST_ADDR giv.
Try to validate both the first and the last
address resulting from loop unrolling, if
one fails, then can't do const elim here. */
- if (memory_address_p (v->mode, v->dest_reg)
- && memory_address_p (v->mode,
+ if (memory_address_p (v->mem_mode, v->dest_reg)
+ && memory_address_p (v->mem_mode,
plus_constant (v->dest_reg,
INTVAL (giv_inc)
* (unroll_number - 1))))
now, and fail completely if either the first or the last
unrolled copy of the address is not a valid address. */
if (v->dest_reg == tem
- && (! memory_address_p (v->mode, v->dest_reg)
- || ! memory_address_p (v->mode,
+ && (! memory_address_p (v->mem_mode, v->dest_reg)
+ || ! memory_address_p (v->mem_mode,
plus_constant (v->dest_reg,
INTVAL (giv_inc)
* (unroll_number -1)))))
emit_insn_before (gen_rtx (SET, VOIDmode, tem,
copy_rtx (v->new_reg)),
loop_start);
- if (! recog_memoized (PREV_INSN (loop_start)))
+ 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));
- emit_iv_add_mult (bl->initial_value, v->mult_val,
- v->add_val, tem, loop_start);
+
+ start_sequence ();
+ ret = force_operand (v->new_reg, tem);
+ if (ret != tem)
+ emit_move_insn (tem, ret);
+ sequence = gen_sequence ();
+ end_sequence ();
+ emit_insn_before (sequence, loop_start);
+
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Illegal init insn, rewritten.\n");
/* Check the resulting address for validity, and fail
if the resulting address would be illegal. */
- if (! memory_address_p (v->mode, v->dest_reg)
- || ! memory_address_p (v->mode,
+ if (! memory_address_p (v->mem_mode, v->dest_reg)
+ || ! memory_address_p (v->mem_mode,
plus_constant (v->dest_reg,
INTVAL (giv_inc) *
(unroll_number -1))))
}
}
- /* Overwrite the old add_val, which is no longer needed, and
- substitute the amount that the giv is incremented on each
- iteration. We need to save this somewhere, so we know how
- much to increment split DEST_ADDR giv's in copy_loop_body. */
-
- v->add_val = giv_inc;
-
if (loop_dump_stream)
fprintf (loop_dump_stream, "DEST_ADDR giv being split.\n");
}
case it is needed later. */
tem = gen_reg_rtx (bl->biv->mode);
- emit_iv_add_mult (increment,
- gen_rtx (CONST_INT, VOIDmode, loop_n_iterations),
+ /* 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 (loop_n_iterations),
bl->initial_value, tem, NEXT_INSN (loop_end));
if (loop_dump_stream)
rtx loop_start, loop_end;
{
struct iv_class *bl;
- rtx reg, insn, pattern;
+ rtx insn;
rtx increment, tem;
- enum rtx_code code;
rtx insert_before, seq;
bl = reg_biv_class[REGNO (v->src_reg)];
/* Put the final biv value in tem. */
tem = gen_reg_rtx (bl->biv->mode);
- emit_iv_add_mult (increment,
- gen_rtx (CONST_INT, VOIDmode, loop_n_iterations),
+ emit_iv_add_mult (increment, GEN_INT (loop_n_iterations),
bl->initial_value, tem, insert_before);
/* Subtract off extra increments as we find them. */
for (insn = NEXT_INSN (v->insn); insn != loop_end;
insn = NEXT_INSN (insn))
{
- if (GET_CODE (insn) == INSN
- && GET_CODE (PATTERN (insn)) == SET
- && SET_DEST (PATTERN (insn)) == v->src_reg)
- {
- pattern = PATTERN (insn);
- if (GET_CODE (SET_SRC (pattern)) != PLUS)
- {
- /* Sometimes a biv is computed in a temp reg,
- and then copied into the biv reg. */
- pattern = PATTERN (PREV_INSN (insn));
- if (GET_CODE (SET_SRC (pattern)) != PLUS)
- abort ();
- }
- if (GET_CODE (XEXP (SET_SRC (pattern), 0)) != REG
- || REGNO (XEXP (SET_SRC (pattern), 0)) != bl->regno)
- abort ();
-
- start_sequence ();
- tem = expand_binop (GET_MODE (tem), sub_optab, tem,
- XEXP (SET_SRC (pattern), 1), 0, 0,
- OPTAB_LIB_WIDEN);
- seq = gen_sequence ();
- end_sequence ();
- emit_insn_before (seq, insert_before);
- }
+ struct induction *biv;
+
+ for (biv = bl->biv; biv; biv = biv->next_iv)
+ if (biv->insn == insn)
+ {
+ start_sequence ();
+ tem = expand_binop (GET_MODE (tem), sub_optab, tem,
+ biv->add_val, NULL_RTX, 0,
+ OPTAB_LIB_WIDEN);
+ seq = gen_sequence ();
+ end_sequence ();
+ emit_insn_before (seq, insert_before);
+ }
}
/* Now calculate the giv's final value. */
/* Calculate the number of loop iterations. Returns the exact number of loop
- iterations if it can be calculated, otherwise retusns zero. */
+ iterations if it can be calculated, otherwise returns zero. */
-unsigned long
+unsigned HOST_WIDE_INT
loop_iterations (loop_start, loop_end)
rtx loop_start, loop_end;
{
rtx comparison, comparison_value;
rtx iteration_var, initial_value, increment, final_value;
enum rtx_code comparison_code;
- int i, increment_dir;
+ HOST_WIDE_INT i;
+ int increment_dir;
int unsigned_compare, compare_dir, final_larger;
unsigned long tempu;
rtx last_loop_insn;
loop_final_value = 0;
loop_iteration_var = 0;
- last_loop_insn = prev_nonnote_insn (loop_end);
+ /* We used to use pren_nonnote_insn here, but that fails because it might
+ accidentally get the branch for a contained loop if the branch for this
+ loop was deleted. We can only trust branches immediately before the
+ loop_end. */
+ last_loop_insn = PREV_INSN (loop_end);
comparison = get_condition_for_loop (last_loop_insn);
if (comparison == 0)
break;
else if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
- && (set = single_set (insn))
- && (SET_DEST (set) == comparison_value))
+ && reg_set_p (comparison_value, insn))
{
- rtx note = find_reg_note (insn, REG_EQUAL, 0);
-
- if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
- comparison_value = XEXP (note, 0);
-
+ /* 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) == comparison_value))
+ {
+ rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
+
+ /* Only use the REG_EQUAL note if it is a constant.
+ Other things, divide in particular, will cause
+ problems later if we use them. */
+ if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST
+ && CONSTANT_P (XEXP (note, 0)))
+ comparison_value = XEXP (note, 0);
+ }
break;
}
}
be addresses with the same base but different constant offsets.
Final value must be invariant for this to work.
- To do this, need someway to find the values of registers which are
+ To do this, need some way to find the values of registers which are
invariant. */
/* Final_larger is 1 if final larger, 0 if they are equal, otherwise -1. */
if (unsigned_compare)
final_larger
- = ((unsigned) INTVAL (final_value) > (unsigned) INTVAL (initial_value)) -
- ((unsigned) INTVAL (final_value) < (unsigned) INTVAL (initial_value));
+ = ((unsigned HOST_WIDE_INT) INTVAL (final_value)
+ > (unsigned HOST_WIDE_INT) INTVAL (initial_value))
+ - ((unsigned HOST_WIDE_INT) INTVAL (final_value)
+ < (unsigned HOST_WIDE_INT) INTVAL (initial_value));
else
- final_larger = (INTVAL (final_value) > INTVAL (initial_value)) -
- (INTVAL (final_value) < INTVAL (initial_value));
+ final_larger = (INTVAL (final_value) > INTVAL (initial_value))
+ - (INTVAL (final_value) < INTVAL (initial_value));
if (INTVAL (increment) > 0)
increment_dir = 1;
return tempu / i + ((tempu % i) != 0);
}
+
+/* Replace uses of split bivs with their split psuedo register. This is
+ for original instructions which remain after loop unrolling without
+ copying. */
+
+static rtx
+remap_split_bivs (x)
+ rtx x;
+{
+ register enum rtx_code code;
+ register int i;
+ register char *fmt;
+
+ if (x == 0)
+ return x;
+
+ code = GET_CODE (x);
+ switch (code)
+ {
+ case SCRATCH:
+ case PC:
+ case CC0:
+ case CONST_INT:
+ case CONST_DOUBLE:
+ case CONST:
+ case SYMBOL_REF:
+ case LABEL_REF:
+ return x;
+
+ case REG:
+#if 0
+ /* 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;
+ }
+
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ if (fmt[i] == 'e')
+ XEXP (x, i) = remap_split_bivs (XEXP (x, i));
+ 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));
+ }
+ }
+ return x;
+}
OSDN Git Service
