/* Try to unroll loops, and split induction variables.
- Copyright (C) 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
+ Copyright (C) 1992, 93, 94, 95, 97, 1998 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.
enum unroll_types { UNROLL_COMPLETELY, UNROLL_MODULO, UNROLL_NAIVE };
#include "config.h"
+#include "system.h"
#include "rtl.h"
#include "insn-config.h"
#include "integrate.h"
#include "regs.h"
+#include "recog.h"
#include "flags.h"
#include "expr.h"
-#include <stdio.h>
#include "loop.h"
+#include "toplev.h"
/* This controls which loops are unrolled, and by how much we unroll
them. */
/* Values describing the current loop's iteration variable. These are set up
by loop_iterations, and used by precondition_loop_p. */
-static rtx loop_iteration_var;
-static rtx loop_initial_value;
-static rtx loop_increment;
-static rtx loop_final_value;
+rtx loop_iteration_var;
+rtx loop_initial_value;
+rtx loop_increment;
+rtx loop_final_value;
+enum rtx_code loop_comparison_code;
/* Forward declarations. */
static void init_reg_map PROTO((struct inline_remap *, int));
-static int precondition_loop_p PROTO((rtx *, rtx *, rtx *, rtx, rtx));
+static int precondition_loop_p PROTO((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 int back_branch_in_range_p PROTO((rtx, rtx, rtx));
-static void iteration_info PROTO((rtx, rtx *, rtx *, rtx, rtx));
+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 int verify_addresses PROTO((struct induction *, rtx, int));
static rtx remap_split_bivs PROTO((rtx));
/* Try to unroll one loop and split induction variables in the loop.
int i, j, temp;
int unroll_number = 1;
rtx copy_start, copy_end;
- rtx insn, copy, sequence, pattern, tem;
+ rtx insn, sequence, pattern, tem;
int max_labelno, max_insnno;
rtx insert_before;
struct inline_remap *map;
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;
loop_n_iterations = 0;
if (loop_dump_stream && loop_n_iterations > 0)
- fprintf (loop_dump_stream,
- "Loop unrolling: %d iterations.\n", loop_n_iterations);
+ {
+ fputs ("Loop unrolling: ", loop_dump_stream);
+ fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, loop_n_iterations);
+ fputs (" iterations.\n", loop_dump_stream);
+ }
/* Find and save a pointer to the last nonnote insn in the loop. */
if (unroll_type == UNROLL_COMPLETELY || unroll_type == UNROLL_MODULO)
{
- /* Loops of these types should never start with a jump down to
- the exit condition test. For now, check for this case just to
- be sure. UNROLL_NAIVE loops can be of this form, this case is
- handled below. */
+ /* Loops of these types can start with jump down to the exit condition
+ in rare circumstances.
+
+ Consider a pair of nested loops where the inner loop is part
+ of the exit code for the outer loop.
+
+ In this case jump.c will not duplicate the exit test for the outer
+ loop, so it will start with a jump to the exit code.
+
+ Then consider if the inner loop turns out to iterate once and
+ only once. We will end up deleting the jumps associated with
+ the inner loop. However, the loop notes are not removed from
+ the instruction stream.
+
+ And finally assume that we can compute the number of iterations
+ for the outer loop.
+
+ In this case unroll may want to unroll the outer loop even though
+ it starts with a jump to the outer loop's exit code.
+
+ We could try to optimize this case, but it hardly seems worth it.
+ Just return without unrolling the loop in such cases. */
+
insn = loop_start;
while (GET_CODE (insn) != CODE_LABEL && GET_CODE (insn) != JUMP_INSN)
insn = NEXT_INSN (insn);
if (GET_CODE (insn) == JUMP_INSN)
- abort ();
+ return;
}
if (unroll_type == UNROLL_COMPLETELY)
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. */
for (insn = copy_start; insn != loop_end; insn = NEXT_INSN (insn))
{
+ rtx note;
+
if (GET_CODE (insn) == CODE_LABEL)
local_label[CODE_LABEL_NUMBER (insn)] = 1;
else if (GET_CODE (insn) == JUMP_INSN)
{
if (JUMP_LABEL (insn))
- map->label_map[CODE_LABEL_NUMBER (JUMP_LABEL (insn))]
- = JUMP_LABEL (insn);
+ set_label_in_map (map,
+ CODE_LABEL_NUMBER (JUMP_LABEL (insn)),
+ JUMP_LABEL (insn));
else if (GET_CODE (PATTERN (insn)) == ADDR_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
{
for (i = 0; i < len; i++)
{
label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
- map->label_map[CODE_LABEL_NUMBER (label)] = label;
+ set_label_in_map (map,
+ CODE_LABEL_NUMBER (label),
+ label);
}
}
}
+ else if ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)))
+ set_label_in_map (map, CODE_LABEL_NUMBER (XEXP (note, 0)),
+ XEXP (note, 0));
}
/* Allocate space for the insn map. */
addr_combined_regs
= (struct induction **) alloca (maxregnum * sizeof (struct induction *));
bzero ((char *) addr_combined_regs, maxregnum * sizeof (struct induction *));
- local_regno = (char *) alloca (maxregnum);
- bzero (local_regno, maxregnum);
+ /* 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. */
+ 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);
- for (j = FIRST_PSEUDO_REGISTER; j < maxregnum; ++j)
- {
- int first_uid = regno_first_uid[j];
- int last_uid = regno_last_uid[j];
-
- if (first_uid > 0 && first_uid <= max_uid_for_loop
- && uid_luid[first_uid] >= copy_start_luid
- && last_uid > 0 && last_uid <= max_uid_for_loop
- && uid_luid[last_uid] <= copy_end_luid)
- local_regno[j] = 1;
- }
+ /* 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
rtx initial_value, final_value, increment;
if (precondition_loop_p (&initial_value, &final_value, &increment,
- loop_start, loop_end))
+ loop_start))
{
- register rtx diff, temp;
+ register rtx diff ;
enum machine_mode mode;
rtx *labels;
int abs_inc, neg_inc;
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)
for (j = 0; j < max_labelno; j++)
if (local_label[j])
- map->label_map[j] = gen_label_rtx ();
+ set_label_in_map (map, j, gen_label_rtx ());
- for (j = FIRST_PSEUDO_REGISTER; j < maxregnum; j++)
+ 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]));
-
+ {
+ map->reg_map[j] = gen_reg_rtx (GET_MODE (regno_reg_rtx[j]));
+ record_base_value (REGNO (map->reg_map[j]),
+ regno_reg_rtx[j], 0);
+ }
/* The last copy needs the compare/branch insns at the end,
so reset copy_end here if the loop ends with a conditional
branch. */
/* At this point, we are guaranteed to unroll the loop. */
+ /* Keep track of the unroll factor for each loop. */
+ if (unroll_type == UNROLL_COMPLETELY)
+ loop_unroll_factor [uid_loop_num [INSN_UID (loop_start)]] = -1;
+ else
+ loop_unroll_factor [uid_loop_num [INSN_UID (loop_start)]] = unroll_number;
+
+
/* For each biv and giv, determine whether it can be safely split into
a different variable for each unrolled copy of the loop body.
We precalculate and save this info here, since computing it is
#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/jump instruction at the end of the loop to refer to the new
for (j = 0; j < max_labelno; j++)
if (local_label[j])
- map->label_map[j] = gen_label_rtx ();
+ set_label_in_map (map, j, gen_label_rtx ());
- for (j = FIRST_PSEUDO_REGISTER; j < maxregnum; j++)
+ 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]));
+ {
+ map->reg_map[j] = gen_reg_rtx (GET_MODE (regno_reg_rtx[j]));
+ record_base_value (REGNO (map->reg_map[j]),
+ regno_reg_rtx[j], 0);
+ }
/* 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. */
insn = PREV_INSN (copy_start);
pattern = PATTERN (insn);
- tem = map->label_map[CODE_LABEL_NUMBER
- (XEXP (SET_SRC (pattern), 0))];
- SET_SRC (pattern) = gen_rtx (LABEL_REF, VOIDmode, tem);
+ tem = get_label_from_map (map,
+ CODE_LABEL_NUMBER
+ (XEXP (SET_SRC (pattern), 0)));
+ SET_SRC (pattern) = gen_rtx_LABEL_REF (VOIDmode, tem);
/* Set the jump label so that it can be used by later loop unrolling
passes. */
whether divide is cheap. */
static int
-precondition_loop_p (initial_value, final_value, increment, loop_start,
- loop_end)
+precondition_loop_p (initial_value, final_value, increment, loop_start)
rtx *initial_value, *final_value, *increment;
- rtx loop_start, loop_end;
+ rtx loop_start;
{
if (loop_n_iterations > 0)
*final_value = GEN_INT (loop_n_iterations);
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Preconditioning: Success, number of iterations known, %d.\n",
- loop_n_iterations);
+ {
+ fputs ("Preconditioning: Success, number of iterations known, ",
+ loop_dump_stream);
+ fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
+ loop_n_iterations);
+ fputs (".\n", loop_dump_stream);
+ }
return 1;
}
/* Fail if loop_iteration_var is not live before loop_start, since we need
to test its value in the preconditioning code. */
- if (uid_luid[regno_first_uid[REGNO (loop_iteration_var)]]
+ if (uid_luid[REGNO_FIRST_UID (REGNO (loop_iteration_var))]
> INSN_LUID (loop_start))
{
if (loop_dump_stream)
to the iv. This procedure reconstructs the pattern computing the iv;
verifying that all operands are of the proper form.
+ PATTERN must be the result of single_set.
The return value is the amount that the giv is incremented by. */
static rtx
one of the LO_SUM rtx. */
if (GET_CODE (increment) == LO_SUM)
increment = XEXP (increment, 1);
- else if (GET_CODE (increment) == IOR)
+
+ /* Some ports store large constants in memory and add a REG_EQUAL
+ note to the store insn. */
+ else if (GET_CODE (increment) == MEM)
+ {
+ rtx note = find_reg_note (src_insn, REG_EQUAL, 0);
+ if (note)
+ increment = XEXP (note, 0);
+ }
+
+ else if (GET_CODE (increment) == IOR
+ || GET_CODE (increment) == ASHIFT
+ || GET_CODE (increment) == PLUS)
{
- /* The rs6000 port loads some constants with IOR. */
+ /* The rs6000 port loads some constants with IOR.
+ The alpha port loads some constants with ASHIFT and PLUS. */
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));
|| GET_CODE (increment) != CONST_INT)
abort ();
- increment = GEN_INT (INTVAL (increment) | INTVAL (second_part));
+ if (code == IOR)
+ increment = GEN_INT (INTVAL (increment) | INTVAL (second_part));
+ else if (code == PLUS)
+ increment = GEN_INT (INTVAL (increment) + INTVAL (second_part));
+ else
+ increment = GEN_INT (INTVAL (increment) << INTVAL (second_part));
}
if (GET_CODE (increment) != CONST_INT)
rtx start_label, loop_end, insert_before, copy_notes_from;
{
rtx insn, pattern;
- rtx tem, copy;
+ rtx set, tem, copy;
int dest_reg_was_split, i;
+#ifdef HAVE_cc0
rtx cc0_insn = 0;
+#endif
rtx final_label = 0;
rtx giv_inc, giv_dest_reg, giv_src_reg;
if (! last_iteration)
{
final_label = gen_label_rtx ();
- map->label_map[CODE_LABEL_NUMBER (start_label)] = final_label;
+ set_label_in_map (map, CODE_LABEL_NUMBER (start_label),
+ final_label);
}
else
- map->label_map[CODE_LABEL_NUMBER (start_label)] = start_label;
+ set_label_in_map (map, CODE_LABEL_NUMBER (start_label), start_label);
start_sequence ();
Do this before splitting the giv, since that may map the
SET_DEST to a new register. */
- if (GET_CODE (pattern) == SET
- && GET_CODE (SET_DEST (pattern)) == REG
- && addr_combined_regs[REGNO (SET_DEST (pattern))])
+ if ((set = single_set (insn))
+ && GET_CODE (SET_DEST (set)) == REG
+ && addr_combined_regs[REGNO (SET_DEST (set))])
{
struct iv_class *bl;
struct induction *v, *tv;
- int regno = REGNO (SET_DEST (pattern));
+ int regno = REGNO (SET_DEST (set));
- v = addr_combined_regs[REGNO (SET_DEST (pattern))];
+ v = addr_combined_regs[REGNO (SET_DEST (set))];
bl = reg_biv_class[REGNO (v->src_reg)];
/* Although the giv_inc amount is not needed here, we must call
we might accidentally delete insns generated immediately
below by emit_unrolled_add. */
- giv_inc = calculate_giv_inc (pattern, insn, regno);
+ giv_inc = calculate_giv_inc (set, insn, regno);
/* Now find all address giv's that were combined with this
giv 'v'. */
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));
dest_reg = XEXP (tv->dest_reg, 0);
/* Check for shared address givs, and avoid
- incrementing the shared psuedo reg more than
+ incrementing the shared pseudo reg more than
once. */
- if (! tv->same_insn)
+ if (! tv->same_insn && ! tv->shared)
{
/* tv->dest_reg may actually be a (PLUS (REG)
(CONST)) here, so we must call plus_constant
dest_reg_was_split = 0;
- if (GET_CODE (pattern) == SET
- && GET_CODE (SET_DEST (pattern)) == REG
- && splittable_regs[REGNO (SET_DEST (pattern))])
+ if ((set = single_set (insn))
+ && GET_CODE (SET_DEST (set)) == REG
+ && splittable_regs[REGNO (SET_DEST (set))])
{
- int regno = REGNO (SET_DEST (pattern));
+ int regno = REGNO (SET_DEST (set));
dest_reg_was_split = 1;
already computed above. */
if (giv_inc == 0)
- giv_inc = calculate_giv_inc (pattern, insn, regno);
- giv_dest_reg = SET_DEST (pattern);
- giv_src_reg = SET_DEST (pattern);
+ giv_inc = calculate_giv_inc (set, insn, regno);
+ giv_dest_reg = SET_DEST (set);
+ giv_src_reg = SET_DEST (set);
if (unroll_type == UNROLL_COMPLETELY)
{
tem = gen_reg_rtx (GET_MODE (giv_src_reg));
giv_dest_reg = tem;
map->reg_map[regno] = tem;
+ record_base_value (REGNO (tem),
+ giv_inc == const0_rtx
+ ? giv_src_reg
+ : gen_rtx_PLUS (GET_MODE (giv_src_reg),
+ giv_src_reg, giv_inc),
+ 1);
}
else
map->reg_map[regno] = giv_src_reg;
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
{
if (invert_exp (pattern, copy))
{
if (! redirect_exp (&pattern,
- map->label_map[CODE_LABEL_NUMBER
- (JUMP_LABEL (insn))],
+ get_label_from_map (map,
+ CODE_LABEL_NUMBER
+ (JUMP_LABEL (insn))),
exit_label, copy))
abort ();
}
{
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
+ /* 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);
emit_label_after (lab, jmp);
LABEL_NUSES (lab) = 0;
if (! redirect_exp (&pattern,
- map->label_map[CODE_LABEL_NUMBER
- (JUMP_LABEL (insn))],
+ get_label_from_map (map,
+ CODE_LABEL_NUMBER
+ (JUMP_LABEL (insn))),
lab, copy))
abort ();
}
/* 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)
+ if ((set = single_set (copy)))
{
- tem = SET_SRC (pattern);
+ tem = SET_SRC (set);
if (GET_CODE (tem) == LABEL_REF)
label = XEXP (tem, 0);
else if (GET_CODE (tem) == IF_THEN_ELSE)
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))];
+ = get_label_from_map (map,
+ CODE_LABEL_NUMBER (JUMP_LABEL (insn)));
}
/* If this is a non-local jump, then must increase the label
/* 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);
+ CALL_INSN_FUNCTION_USAGE (copy)
+ = copy_rtx_and_substitute (CALL_INSN_FUNCTION_USAGE (insn), map);
#ifdef HAVE_cc0
if (cc0_insn)
if (insn != start_label)
{
- copy = emit_label (map->label_map[CODE_LABEL_NUMBER (insn)]);
+ copy = emit_label (get_label_from_map (map,
+ CODE_LABEL_NUMBER (insn)));
map->const_age++;
}
break;
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 p, q, target_insn;
+ rtx orig_loop_end = loop_end;
/* Stop before we get to the backward branch at the end of the loop. */
loop_end = prev_nonnote_insn (loop_end);
while (INSN_DELETED_P (insn))
insn = NEXT_INSN (insn);
- /* Check for the case where insn is the last insn in the loop. */
- if (insn == loop_end)
+ /* Check for the case where insn is the last insn in the loop. Deal
+ with the case where INSN was a deleted loop test insn, in which case
+ it will now be the NOTE_LOOP_END. */
+ if (insn == loop_end || insn == orig_loop_end)
return 0;
for (p = NEXT_INSN (insn); p != loop_end; p = NEXT_INSN (p))
mult_res = simplify_binary_operation (MULT, mode, mult1, mult2);
if (! mult_res)
- mult_res = gen_rtx (MULT, mode, mult1, mult2);
+ mult_res = gen_rtx_MULT (mode, mult1, mult2);
/* Again, put the constant second. */
if (GET_CODE (add1) == CONST_INT)
result = simplify_binary_operation (PLUS, mode, add1, mult_res);
if (! result)
- result = gen_rtx (PLUS, mode, add1, mult_res);
+ result = gen_rtx_PLUS (mode, add1, mult_res);
return result;
}
/* For increment, must check every instruction that sets it. Each
instruction must be executed only once each time through the loop.
- To verify this, we check that the the insn is always executed, and that
+ To verify this, we check that the insn is always executed, and that
there are no backward branches after the insn that branch to before it.
Also, the insn must have a mult_val of one (to make sure it really is
an increment). */
Initial_value and/or increment are set to zero if their values could not
be calculated. */
-static void
+void
iteration_info (iteration_var, initial_value, increment, loop_start, loop_end)
rtx iteration_var, *initial_value, *increment;
rtx loop_start, loop_end;
{
struct iv_class *bl;
- struct induction *v, *b;
+#if 0
+ struct induction *v;
+#endif
/* Clear the result values, in case no answer can be found. */
*initial_value = 0;
"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 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)
+ && (uid_luid[REGNO_LAST_UID (bl->regno)] >= INSN_LUID (loop_end)
|| ! bl->init_insn
|| INSN_UID (bl->init_insn) >= max_uid_for_loop
- || (uid_luid[regno_first_uid[bl->regno]]
+ || (uid_luid[REGNO_FIRST_UID (bl->regno)]
< INSN_LUID (bl->init_insn))
|| reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
&& ! (biv_final_value = final_biv_value (bl, loop_start, loop_end)))
{
/* 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);
-
+
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
loop_start);
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);
this insn will always be executed, no matter how the loop
exits. */
rtx tem = gen_reg_rtx (bl->biv->mode);
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
+
emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
loop_start);
emit_insn_before (gen_move_insn (bl->biv->src_reg,
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. Handle the fact
+ that we have may have a match_dup. */
+ if (! validate_replace_rtx (*v->location, v->dest_reg, v->insn)
+ || ! validate_replace_rtx (*v->location, last_addr, v->insn))
+ ret = 0;
+
+ /* Now put things back the way they were before. This should always
+ succeed. */
+ if (! validate_replace_rtx (*v->location, orig_addr, v->insn))
+ abort ();
+
+ 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 ().
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)
- /* 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, NULL_RTX))
- || (regno_first_uid[REGNO (v->dest_reg)]
- != INSN_UID (XEXP (tem, 0)))))
+ /* The next part is true if the pseudo is used outside the loop.
+ We assume that this is true for any pseudo created after loop
+ starts, because we don't have a reg_n_info entry for them. */
+ && (REGNO (v->dest_reg) >= max_reg_before_loop
+ || (REGNO_FIRST_UID (REGNO (v->dest_reg)) != INSN_UID (v->insn)
+ /* 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, 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. */
- || (uid_luid[regno_last_uid[REGNO (v->dest_reg)]]
+ || (uid_luid[REGNO_LAST_UID (REGNO (v->dest_reg))]
>= INSN_LUID (loop_end)))
&& ! (final_value = v->final_value))
continue;
{
rtx tem = gen_reg_rtx (bl->biv->mode);
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
loop_start);
biv_initial_value = tem;
|| GET_CODE (XEXP (value, 1)) != CONST_INT))
{
rtx tem = gen_reg_rtx (v->mode);
+ record_base_value (REGNO (tem), v->add_val, 0);
emit_iv_add_mult (bl->initial_value, v->mult_val,
v->add_val, tem, loop_start);
value = tem;
what we want for split addr regs. We always create a new
register for the split addr giv, just to be safe. */
- /* ??? If there are multiple address givs which have been
- combined with the same dest_reg giv, then we may only need
- one new register for them. Pulling out constants below will
- catch some of the common cases of this. Currently, I leave
- 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
+ /* If we have multiple identical address givs within a
+ single instruction, then use a single pseudo reg for
+ both. This is necessary in case one is a match_dup
of the other. */
v->const_adjust = 0;
"Sharing address givs in insn %d\n",
INSN_UID (v->insn));
}
+ /* If multiple address GIVs have been combined with the
+ same dest_reg GIV, do not create a new register for
+ each. */
+ else if (unroll_type != UNROLL_COMPLETELY
+ && v->giv_type == DEST_ADDR
+ && v->same && v->same->giv_type == DEST_ADDR
+ && v->same->unrolled
+ /* combine_givs_p may return true for some cases
+ where the add and mult values are not equal.
+ To share a register here, the values must be
+ equal. */
+ && rtx_equal_p (v->same->mult_val, v->mult_val)
+ && rtx_equal_p (v->same->add_val, v->add_val))
+
+ {
+ v->dest_reg = v->same->dest_reg;
+ v->shared = 1;
+ }
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.
Emit insn to initialize its value before loop start. */
- tem = gen_reg_rtx (v->mode);
+
+ rtx tem = gen_reg_rtx (v->mode);
+ record_base_value (REGNO (tem), v->add_val, 0);
/* If the address giv has a constant in its new_reg value,
then this constant can be pulled out and put in value,
{
v->dest_reg
= plus_constant (tem, INTVAL (XEXP (v->new_reg,1)));
-
+
/* Only succeed if this will give valid addresses.
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))
{
+ for (v2 = v->next_iv; v2; v2 = v2->next_iv)
+ if (v2->same_insn == v)
+ v2->same_insn = 0;
+
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Invalid address for giv at insn %d\n",
continue;
}
+ /* We set this after the address check, to guarantee that
+ the register will be initialized. */
+ v->unrolled = 1;
+
/* To initialize the new register, just move the value of
new_reg into it. This is not guaranteed to give a valid
instruction on machines with complex addressing modes.
If we can't recognize it, then delete it and emit insns
to calculate the value from scratch. */
- emit_insn_before (gen_rtx (SET, VOIDmode, tem,
- copy_rtx (v->new_reg)),
+ emit_insn_before (gen_rtx_SET (VOIDmode, tem,
+ copy_rtx (v->new_reg)),
loop_start);
if (recog_memoized (PREV_INSN (loop_start)) < 0)
{
/* Check the resulting address for validity, and fail
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,
- INTVAL (giv_inc) *
- (unroll_number -1))))
+ if (! verify_addresses (v, giv_inc, unroll_number))
{
+ for (v2 = v->next_iv; v2; v2 = v2->next_iv)
+ if (v2->same_insn == v)
+ v2->same_insn = 0;
+
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Invalid address for giv at insn %d\n",
#endif
}
- /* Givs are only updated once by definition. Mark it so if this is
+ /* Unreduced givs are only updated once by definition. Reduced givs
+ are updated as many times as their biv is. Mark it so if this is
a splittable register. Don't need to do anything for address givs
where this may not be a register. */
if (GET_CODE (v->new_reg) == REG)
- splittable_regs_updates[REGNO (v->new_reg)] = 1;
+ {
+ int count = 1;
+ if (! v->ignore)
+ count = reg_biv_class[REGNO (v->src_reg)]->biv_count;
+
+ splittable_regs_updates[REGNO (v->new_reg)] = count;
+ }
result++;
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 = gen_rtx_LABEL_REF (VOIDmode, loop_end);
+ 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);
case it is needed later. */
tem = gen_reg_rtx (bl->biv->mode);
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
/* Make sure loop_end is not the last insn. */
if (NEXT_INSN (loop_end) == 0)
emit_note_after (NOTE_INSN_DELETED, loop_end);
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
determine whether giv's are replaceable so that we can use the
biv value here if it is not eliminable. */
+ /* We are emitting code after the end of the loop, so we must make
+ sure that bl->initial_value is still valid then. It will still
+ be valid if it is invariant. */
+
increment = biv_total_increment (bl, loop_start, loop_end);
- if (increment && invariant_p (increment))
+ if (increment && invariant_p (increment)
+ && invariant_p (bl->initial_value))
{
/* Can calculate the loop exit value of its biv as
(loop_n_iterations * increment) + initial_value */
/* Put the final biv value in tem. */
tem = gen_reg_rtx (bl->biv->mode);
+ record_base_value (REGNO (tem), bl->biv->add_val, 0);
emit_iv_add_mult (increment, GEN_INT (loop_n_iterations),
bl->initial_value, tem, insert_before);
loop_initial_value = initial_value;
loop_increment = increment;
loop_final_value = final_value;
+ loop_comparison_code = comparison_code;
if (increment == 0)
{
return tempu / i + ((tempu % i) != 0);
}
-/* Replace uses of split bivs with their split psuedo register. This is
+/* Replace uses of split bivs with their split pseudo register. This is
for original instructions which remain after loop unrolling without
copying. */
if (REGNO (x) < max_reg_before_loop
&& reg_iv_type[REGNO (x)] == BASIC_INDUCT)
return reg_biv_class[REGNO (x)]->biv->src_reg;
+ break;
+
+ default:
+ break;
}
fmt = GET_RTX_FORMAT (code);
}
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
