/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992, 1993, 1994 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.
/* 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;
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--;
+
+ 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)
+ local_regno[j] = 1;
+ }
/* 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.
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. */
/* 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)
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 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))
+ if (! tv->same_insn)
{
/* tv->dest_reg may actually be a (PLUS (REG)
(CONST)) here, so we must call plus_constant
case to be a branch past the end of the loop, and the
original jump label case to fall_through. */
- if (! invert_exp (pattern, copy)
- || ! redirect_exp (&pattern,
- map->label_map[CODE_LABEL_NUMBER
- (JUMP_LABEL (insn))],
- exit_label, copy))
- abort ();
+ 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 becasue we
+ couln'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
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)
try_constants (cc0_insn, map);
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;
rtx increment;
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)
{
rtx giv_inc, value;
{
/* 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. */
v->const_adjust = 0;
- if (v->same && v->same->insn == v->insn
- && v->new_reg == v->same->new_reg)
+ if (v->same_insn)
{
- v->dest_reg = v->same->dest_reg;
+ v->dest_reg = v->same_insn->dest_reg;
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "Sharing address givs with reg %d\n",
- REGNO (v->dest_reg));
+ "Sharing address givs in insn %d\n",
+ INSN_UID (v->insn));
}
else if (unroll_type != UNROLL_COMPLETELY)
{
{
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;
}
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 the resulting address would be invalid. */
if (! memory_address_p (v->mem_mode, v->dest_reg)
|| ! memory_address_p (v->mem_mode,
plus_constant (v->dest_reg,
{
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_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. */
{
rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
- if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
+ /* 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_increment = increment;
loop_final_value = final_value;
- 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 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
