/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992 Free Software Foundation, Inc.
+ Copyright (C) 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
Contributed by James E. Wilson, Cygnus Support/UC Berkeley.
This file is part of GNU CC.
You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING. If not, write to
-the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
/* Try to unroll a loop, and split induction variables.
static rtx loop_initial_value;
static rtx loop_increment;
static rtx loop_final_value;
+static enum rtx_code loop_comparison_code;
/* Forward declarations. */
-static void init_reg_map ();
-static int precondition_loop_p ();
-static void copy_loop_body ();
-static void iteration_info ();
-static rtx approx_final_value ();
-static int find_splittable_regs ();
-static int find_splittable_givs ();
-static rtx fold_rtx_mult_add ();
+static void init_reg_map PROTO((struct inline_remap *, int));
+static int precondition_loop_p PROTO((rtx *, 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 *));
+static void copy_loop_body PROTO((rtx, rtx, struct inline_remap *, rtx, int,
+ enum unroll_types, rtx, rtx, rtx, rtx));
+static void iteration_info PROTO((rtx, rtx *, rtx *, rtx, rtx));
+static rtx approx_final_value PROTO((enum rtx_code, rtx, int *, int *));
+static int find_splittable_regs PROTO((enum unroll_types, rtx, rtx, rtx, int));
+static int find_splittable_givs PROTO((struct iv_class *,enum unroll_types,
+ 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 rtx remap_split_bivs PROTO((rtx));
/* Try to unroll one loop and split induction variables in the loop.
rtx insert_before;
struct inline_remap *map;
char *local_label;
+ char *local_regno;
int maxregnum;
int new_maxregnum;
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;
of block_beg and block_end notes, because that would unbalance the block
structure of the function. This can happen as a result of the
"if (foo) bar; else break;" optimization in jump.c. */
+ /* ??? Gcc has a general policy that -g is never supposed to change the code
+ that the compiler emits, so we must disable this optimization always,
+ even if debug info is not being output. This is rare, so this should
+ not be a significant performance problem. */
- if (write_symbols != NO_DEBUG)
+ if (1 /* write_symbols != NO_DEBUG */)
{
int block_begins = 0;
int block_ends = 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
copy_end = last_loop_insn;
}
+ if (unroll_type == UNROLL_NAIVE
+ && GET_CODE (last_loop_insn) == JUMP_INSN
+ && start_label != JUMP_LABEL (last_loop_insn))
+ {
+ /* ??? The loop ends with a conditional branch that does not branch back
+ to the loop start label. In this case, we must emit an unconditional
+ branch to the loop exit after emitting the final branch.
+ copy_loop_body does not have support for this currently, so we
+ give up. It doesn't seem worthwhile to unroll anyways since
+ unrolling would increase the number of branch instructions
+ executed. */
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Unrolling failure: final conditional branch not to loop start\n");
+ return;
+ }
+
/* Allocate a translation table for the labels and insn numbers.
They will be filled in as we copy the insns in the loop. */
map = (struct inline_remap *) alloca (sizeof (struct inline_remap));
+ map->integrating = 0;
+
/* Allocate the label map. */
if (max_labelno > 0)
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 *));
+ /* We must limit it to max_reg_before_loop, because only these pseudo
+ registers have valid regno_first_uid info. Any register created after
+ that is unlikely to be local to the loop anyways. */
+ local_regno = (char *) alloca (max_reg_before_loop);
+ bzero (local_regno, max_reg_before_loop);
+
+ /* Mark all local registers, i.e. the ones which are referenced only
+ inside the loop. */
+ if (INSN_UID (copy_end) < max_uid_for_loop)
+ {
+ int copy_start_luid = INSN_LUID (copy_start);
+ int copy_end_luid = INSN_LUID (copy_end);
+
+ /* If a register is used in the jump insn, we must not duplicate it
+ since it will also be used outside the loop. */
+ if (GET_CODE (copy_end) == JUMP_INSN)
+ copy_end_luid--;
+ /* If copy_start points to the NOTE that starts the loop, then we must
+ use the next luid, because invariant pseudo-regs moved out of the loop
+ have their lifetimes modified to start here, but they are not safe
+ to duplicate. */
+ if (copy_start == loop_start)
+ copy_start_luid++;
+
+ /* If a pseudo's lifetime is entirely contained within this loop, then we
+ can use a different pseudo in each unrolled copy of the loop. This
+ results in better code. */
+ for (j = FIRST_PSEUDO_REGISTER; j < max_reg_before_loop; ++j)
+ if (regno_first_uid[j] > 0 && regno_first_uid[j] <= max_uid_for_loop
+ && uid_luid[regno_first_uid[j]] >= copy_start_luid
+ && regno_last_uid[j] > 0 && regno_last_uid[j] <= max_uid_for_loop
+ && uid_luid[regno_last_uid[j]] <= 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
+ used by iteration X+1, then we can not use a different pseudo
+ for each unrolled copy of the loop. */
+ /* A pseudo is safe if regno_first_uid is a set, and this
+ set dominates all instructions from regno_first_uid to
+ regno_last_uid. */
+ /* ??? This check is simplistic. We would get better code if
+ this check was more sophisticated. */
+ if (set_dominates_use (j, regno_first_uid[j], regno_last_uid[j],
+ copy_start, copy_end))
+ local_regno[j] = 1;
+
+ if (loop_dump_stream)
+ {
+ if (local_regno[j])
+ fprintf (loop_dump_stream, "Marked reg %d as local\n", j);
+ else
+ fprintf (loop_dump_stream, "Did not mark reg %d as local\n",
+ j);
+ }
+ }
+ }
/* 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);
for (i = 0; i < unroll_number; i++)
labels[i] = gen_label_rtx ();
+ /* Check for the case where the initial value is greater than or
+ equal to the final value. In that case, we want to execute
+ exactly one loop iteration. The code below will fail for this
+ case. This check does not apply if the loop has a NE
+ comparison at the end. */
+
+ if (loop_comparison_code != NE)
+ {
+ emit_cmp_insn (initial_value, final_value, neg_inc ? LE : GE,
+ NULL_RTX, mode, 0, 0);
+ if (neg_inc)
+ emit_jump_insn (gen_ble (labels[1]));
+ else
+ emit_jump_insn (gen_bge (labels[1]));
+ JUMP_LABEL (get_last_insn ()) = labels[1];
+ LABEL_NUSES (labels[1])++;
+ }
+
/* Assuming the unroll_number is 4, and the increment is 2, then
for a negative increment: for a positive increment:
diff = 0,1 precond 0 diff = 0,7 precond 0
for (i = 0; i < unroll_number - 1; i++)
{
int cmp_const;
+ enum rtx_code cmp_code;
/* For negative increments, must invert the constant compared
against, except when comparing against zero. */
if (i == 0)
- cmp_const = 0;
+ {
+ cmp_const = 0;
+ cmp_code = EQ;
+ }
else if (neg_inc)
- cmp_const = unroll_number - i;
+ {
+ cmp_const = unroll_number - i;
+ cmp_code = GE;
+ }
else
- cmp_const = i;
+ {
+ cmp_const = i;
+ cmp_code = LE;
+ }
emit_cmp_insn (diff, GEN_INT (abs_inc * cmp_const),
- EQ, NULL_RTX, mode, 0, 0);
+ cmp_code, NULL_RTX, mode, 0, 0);
if (i == 0)
emit_jump_insn (gen_beq (labels[i]));
if (abs_inc != 1)
{
int cmp_const;
+ enum rtx_code cmp_code;
if (neg_inc)
- cmp_const = abs_inc - 1;
+ {
+ cmp_const = abs_inc - 1;
+ cmp_code = LE;
+ }
else
- cmp_const = abs_inc * (unroll_number - 1) + 1;
+ {
+ cmp_const = abs_inc * (unroll_number - 1) + 1;
+ cmp_code = GE;
+ }
- emit_cmp_insn (diff, GEN_INT (cmp_const), EQ, NULL_RTX,
+ emit_cmp_insn (diff, GEN_INT (cmp_const), cmp_code, NULL_RTX,
mode, 0, 0);
if (neg_inc)
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++)
if (local_label[j])
map->label_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]));
+
/* The last copy needs the compare/branch insns at the end,
so reset copy_end here if the loop ends with a conditional
branch. */
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. */
#endif
}
+ /* Use our current register alignment and pointer flags. */
+ map->regno_pointer_flag = regno_pointer_flag;
+ map->regno_pointer_align = regno_pointer_align;
+
/* 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++)
if (local_label[j])
map->label_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]));
+
/* If loop starts with a branch to the test, then fix it so that
it points to the test of the first unrolled copy of the loop. */
if (i == 0 && loop_start != copy_start)
rtx *initial_value, *final_value, *increment;
rtx loop_start, loop_end;
{
- int unsigned_compare, compare_dir;
if (loop_n_iterations > 0)
{
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
+ || GET_CODE (increment) == ASHIFT)
+ {
+ /* The rs6000 port loads some constants with IOR.
+ The alpha port loads some constants with ASHIFT. */
+ rtx second_part = XEXP (increment, 1);
+ enum rtx_code code = GET_CODE (increment);
+
+ 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 ();
+
+ if (code == IOR)
+ increment = GEN_INT (INTVAL (increment) | INTVAL (second_part));
+ else
+ 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. */
for (tv = bl->giv; tv; tv = tv->next_iv)
if (tv->giv_type == DEST_ADDR && tv->same == v)
{
- int this_giv_inc = INTVAL (giv_inc);
+ int this_giv_inc;
+
+ /* If this DEST_ADDR giv was not split, then ignore it. */
+ if (*tv->location != tv->dest_reg)
+ continue;
/* Scale this_giv_inc if the multiplicative factors of
the two givs are different. */
+ this_giv_inc = INTVAL (giv_inc);
if (tv->mult_val != v->mult_val)
this_giv_inc = (this_giv_inc / INTVAL (v->mult_val)
* INTVAL (tv->mult_val));
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 pseudo reg more than
+ once. */
+ if (! tv->same_insn)
+ {
+ /* 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.
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
If the previous insn set CC0, substitute constants on it as
well. */
- if (sets_cc0_p (copy) != 0)
+ if (sets_cc0_p (PATTERN (copy)) != 0)
cc0_insn = copy;
else
{
{
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)
{
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. */
- /* Never map the label in this case. */
- pattern = copy_rtx (PATTERN (insn));
- copy = emit_jump_insn (pattern);
-
- if (! invert_exp (pattern, copy)
- || ! redirect_exp (&pattern, JUMP_LABEL (insn),
- exit_label, copy))
- abort ();
- }
- else
- {
- pattern = copy_rtx_and_substitute (PATTERN (insn), map);
- copy = emit_jump_insn (pattern);
+ if (invert_exp (pattern, copy))
+ {
+ if (! redirect_exp (&pattern,
+ map->label_map[CODE_LABEL_NUMBER
+ (JUMP_LABEL (insn))],
+ exit_label, copy))
+ abort ();
+ }
+ else
+ {
+ rtx jmp;
+ rtx lab = gen_label_rtx ();
+ /* Can't do it by reversing the jump (probably because we
+ couldn't reverse the conditions), so emit a new
+ jump_insn after COPY, and redirect the jump around
+ that. */
+ jmp = emit_jump_insn_after (gen_jump (exit_label), copy);
+ jmp = emit_barrier_after (jmp);
+ emit_label_after (lab, jmp);
+ LABEL_NUSES (lab) = 0;
+ if (! redirect_exp (&pattern,
+ map->label_map[CODE_LABEL_NUMBER
+ (JUMP_LABEL (insn))],
+ lab, copy))
+ abort ();
+ }
}
#ifdef HAVE_cc0
/* An unrecognizable jump insn, probably the entry jump
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))];
+ JUMP_LABEL (copy)
+ = map->label_map[CODE_LABEL_NUMBER (JUMP_LABEL (insn))];
}
/* If this is a non-local jump, then must increase the label
/* 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)
}
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);
In practice, this is not a problem, because this function is seldom called,
and uses a negligible amount of CPU time on average. */
-static int
+int
back_branch_in_range_p (insn, loop_start, loop_end)
rtx insn;
rtx loop_start, loop_end;
"Loop unrolling: No reg_iv_type entry for iteration var.\n");
return;
}
- /* Reject iteration variables larger than the host long size, since they
+
+ /* 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 long' variable loop_n_iterations. */
- else if (GET_MODE_BITSIZE (GET_MODE (iteration_var)) > HOST_BITS_PER_LONG)
+ `unsigned HOST_WIDE_INT' variable loop_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 larger than host long.\n");
+ "Loop unrolling: Iteration var rejected because mode too large.\n");
return;
}
else if (GET_MODE_CLASS (GET_MODE (iteration_var)) != MODE_INT)
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
it is unsafe to split the biv since it may not have the proper
value on loop exit. */
- /* loop_number_exit_labels is non-zero if the loop has an exit other than
+ /* loop_number_exit_count is non-zero if the loop has an exit other than
a fall through at the end. */
biv_splittable = 1;
biv_final_value = 0;
if (unroll_type != UNROLL_COMPLETELY
- && (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]
+ && (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
|| unroll_type == UNROLL_NAIVE)
&& (uid_luid[regno_last_uid[bl->regno]] >= INSN_LUID (loop_end)
|| ! bl->init_insn
{
/* If the initial value of the biv is itself (i.e. it is too
complicated for strength_reduce to compute), or is a hard
- register, then we must create a new pseudo reg to hold the
- initial value of the biv. */
+ register, or it isn't invariant, then we must create a new
+ pseudo reg to hold the initial value of the biv. */
if (GET_CODE (bl->initial_value) == REG
&& (REGNO (bl->initial_value) == bl->regno
- || REGNO (bl->initial_value) < FIRST_PSEUDO_REGISTER))
+ || REGNO (bl->initial_value) < FIRST_PSEUDO_REGISTER
+ || ! invariant_p (bl->initial_value)))
{
rtx tem = gen_reg_rtx (bl->biv->mode);
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
loop to ensure that it will always be executed no matter
how the loop exits. Otherwise emit the insn after the loop,
since this is slightly more efficient. */
- if (! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
+ if (! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
emit_insn_before (gen_move_insn (bl->biv->src_reg,
biv_final_value),
end_insert_before);
return result;
}
+/* Return 1 if the first and last unrolled copy of the address giv V is valid
+ for the instruction that is using it. Do not make any changes to that
+ instruction. */
+
+static int
+verify_addresses (v, giv_inc, unroll_number)
+ struct induction *v;
+ rtx giv_inc;
+ int unroll_number;
+{
+ int ret = 1;
+ rtx orig_addr = *v->location;
+ 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))
+ ret = 0;
+
+ /* Now put things back the way they were before. This will always
+ succeed. */
+ validate_change (v->insn, v->location, orig_addr, 0);
+
+ return ret;
+}
+
/* 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;
+ struct induction *v, *v2;
rtx final_value;
rtx tem;
+ int result = 0;
+
+ /* Scan the list of givs, and set the same_insn field when there are
+ multiple identical givs in the same insn. */
+ for (v = bl->giv; v; v = v->next_iv)
+ for (v2 = v->next_iv; v2; v2 = v2->next_iv)
+ if (v->insn == v2->insn && rtx_equal_p (v->new_reg, v2->new_reg)
+ && ! v2->same_insn)
+ v2->same_insn = v;
for (v = bl->giv; v; v = v->next_iv)
{
final_value = 0;
if (unroll_type != UNROLL_COMPLETELY
- && (loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]
+ && (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)
{
/* 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
+ loop start. This prevents invalid 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. */
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 pseudo
+ 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_insn)
+ {
+ v->dest_reg = v->same_insn->dest_reg;
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Sharing address givs in insn %d\n",
+ INSN_UID (v->insn));
+ }
+ 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->mem_mode, v->dest_reg)
- && memory_address_p (v->mem_mode,
- plus_constant (v->dest_reg,
- INTVAL (giv_inc)
- * (unroll_number - 1))))
+ if (verify_addresses (v, giv_inc, unroll_number))
{
/* Save the negative of the eliminated const, so
that we can calculate the dest_reg's increment
/* If the address hasn't been checked for validity yet, do so
now, and fail completely if either the first or the last
- unrolled copy of the address is not a valid address. */
+ unrolled copy of the address is not a valid address
+ for the instruction that uses it. */
if (v->dest_reg == tem
- && (! 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)))))
+ && ! verify_addresses (v, giv_inc, unroll_number))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "Illegal address for giv at insn %d\n",
+ "Invalid address for giv at insn %d\n",
INSN_UID (v->insn));
continue;
}
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");
+ "Invalid init insn, rewritten.\n");
}
}
else
v->dest_reg = value;
/* Check the resulting address for validity, and fail
- if the resulting address would be illegal. */
- 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))))
+ if the resulting address would be invalid. */
+ if (! verify_addresses (v, giv_inc, unroll_number))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "Illegal address for giv at insn %d\n",
+ "Invalid address for giv at insn %d\n",
INSN_UID (v->insn));
continue;
}
rtx insn, label;
enum rtx_code code;
int jump_count = 0;
+ int label_count = 0;
+ int this_loop_num = uid_loop_num[INSN_UID (loop_start)];
+
+ /* In addition to checking all exits of this loop, we must also check
+ all exits of inner nested loops that would exit this loop. We don't
+ have any way to identify those, so we just give up if there are any
+ such inner loop exits. */
+
+ for (label = loop_number_exit_labels[this_loop_num]; label;
+ label = LABEL_NEXTREF (label))
+ label_count++;
+
+ if (label_count != loop_number_exit_count[this_loop_num])
+ return 0;
/* 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_NEXTREF (label)
- = loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]];
+ LABEL_NEXTREF (label) = loop_number_exit_labels[this_loop_num];
for ( ; label; label = LABEL_NEXTREF (label))
{
if (GET_CODE (PATTERN (insn)) == RETURN)
break;
else if (! simplejump_p (insn)
- /* Prevent infinite loop following infinite loops. */
+ /* Prevent infinite loop following infinite loops. */
|| jump_count++ > 20)
return 0;
else
value of the biv must be invariant. */
if (loop_n_iterations != 0
- && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]]
+ && ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]]
&& invariant_p (bl->initial_value))
{
increment = biv_total_increment (bl, loop_start, loop_end);
struct iv_class *bl;
rtx insn;
rtx increment, tem;
- enum rtx_code code;
rtx insert_before, seq;
bl = reg_biv_class[REGNO (v->src_reg)];
to be known. */
if (loop_n_iterations != 0
- && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
+ && ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
{
/* ?? It is tempting to use the biv's value here since these insns will
be put after the loop, and hence the biv will have its final value
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)
/* iteration_info already printed a message. */
return 0;
- if (increment == 0)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Increment value can't be calculated.\n");
- return 0;
- }
- if (GET_CODE (increment) != CONST_INT)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Increment value not constant.\n");
- return 0;
- }
- if (GET_CODE (initial_value) != CONST_INT)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Loop unrolling: Initial value not constant.\n");
- return 0;
- }
-
/* If the comparison value is an invariant register, then try to find
its value from the insns before the start of the loop. */
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, NULL_RTX);
-
- 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;
}
}
loop_initial_value = initial_value;
loop_increment = increment;
loop_final_value = final_value;
+ loop_comparison_code = comparison_code;
- if (final_value == 0)
+ if (increment == 0)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop unrolling: Increment value can't be calculated.\n");
+ return 0;
+ }
+ else if (GET_CODE (increment) != CONST_INT)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop unrolling: Increment value not constant.\n");
+ return 0;
+ }
+ else if (GET_CODE (initial_value) != CONST_INT)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Loop unrolling: Initial value not constant.\n");
+ return 0;
+ }
+ else if (final_value == 0)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
return tempu / i + ((tempu % i) != 0);
}
+
+/* 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)
+ 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;
+}
+
+/* If FIRST_UID is a set of REGNO, and FIRST_UID dominates LAST_UID (e.g.
+ FIST_UID is always executed if LAST_UID is), then return 1. Otherwise
+ return 0. COPY_START is where we can start looking for the insns
+ FIRST_UID and LAST_UID. COPY_END is where we stop looking for these
+ insns.
+
+ If there is no JUMP_INSN between LOOP_START and FIRST_UID, then FIRST_UID
+ must dominate LAST_UID.
+
+ If there is a CODE_LABEL between FIRST_UID and LAST_UID, then FIRST_UID
+ may not dominate LAST_UID.
+
+ If there is no CODE_LABEL between FIRST_UID and LAST_UID, then FIRST_UID
+ 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;
+{
+ int passed_jump = 0;
+ rtx p = NEXT_INSN (copy_start);
+
+ while (INSN_UID (p) != first_uid)
+ {
+ if (GET_CODE (p) == JUMP_INSN)
+ passed_jump= 1;
+ /* Could not find FIRST_UID. */
+ if (p == copy_end)
+ return 0;
+ p = NEXT_INSN (p);
+ }
+
+ /* 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))
+ return 0;
+
+ /* FIRST_UID is always executed. */
+ if (passed_jump == 0)
+ return 1;
+
+ while (INSN_UID (p) != last_uid)
+ {
+ /* If we see a CODE_LABEL between FIRST_UID and LAST_UID, then we
+ can not be sure that FIRST_UID dominates LAST_UID. */
+ if (GET_CODE (p) == CODE_LABEL)
+ return 0;
+ /* Could not find LAST_UID, but we reached the end of the loop, so
+ it must be safe. */
+ else if (p == copy_end)
+ return 1;
+ p = NEXT_INSN (p);
+ }
+
+ /* FIRST_UID is always executed if LAST_UID is executed. */
+ return 1;
+}
OSDN Git Service
