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 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));
+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,
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;
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. */
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)
- local_regno[j] = 1;
+ 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
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. */
+ /* 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. */
- 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])++;
+ 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:
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]);
+ }
/* The last copy needs the compare/branch insns at the end,
so reset copy_end here if the loop ends with a conditional
branch. */
/* Set unroll type to MODULO now. */
unroll_type = UNROLL_MODULO;
loop_preconditioned = 1;
+#ifdef HAIFA
+ if (loop_n_iterations > 0)
+ loop_unroll_iter[ loop_number(loop_start, loop_end) ]
+ = (loop_n_iterations
+ - loop_n_iterations % (abs_inc * unroll_number));
+ else
+ /* inform loop.c about the new initial value */
+ loop_start_value[loop_number(loop_start, loop_end)] = initial_value;
+#endif
+
}
}
/* At this point, we are guaranteed to unroll the loop. */
+#ifdef HAIFA
+ /* inform loop.c about the factor of unrolling */
+ if (unroll_type == UNROLL_COMPLETELY)
+ loop_unroll_factor[ loop_number(loop_start, loop_end) ] = -1;
+ else
+ loop_unroll_factor[ loop_number(loop_start, loop_end) ] = unroll_number;
+#endif /* HAIFA */
+
+
/* 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 = 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]);
+ }
/* 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. */
/* 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)
if (GET_CODE (increment) == LO_SUM)
increment = XEXP (increment, 1);
else if (GET_CODE (increment) == IOR
- || GET_CODE (increment) == ASHIFT)
+ || GET_CODE (increment) == ASHIFT
+ || GET_CODE (increment) == PLUS)
{
/* The rs6000 port loads some constants with IOR.
- The alpha port loads some constants with ASHIFT. */
+ The alpha port loads some constants with ASHIFT and PLUS. */
rtx second_part = XEXP (increment, 1);
enum rtx_code code = GET_CODE (increment);
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));
}
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));
/* Check for shared address givs, and avoid
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
tem = gen_reg_rtx (GET_MODE (giv_src_reg));
giv_dest_reg = tem;
map->reg_map[regno] = tem;
+ record_base_value (REGNO (tem), giv_src_reg);
}
else
map->reg_map[regno] = giv_src_reg;
/* 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)
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;
"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)
if (unroll_type != UNROLL_COMPLETELY
&& (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)))
|| ! invariant_p (bl->initial_value)))
{
rtx tem = gen_reg_rtx (bl->biv->mode);
-
+
+ record_base_value (REGNO (tem), bl->biv->add_val);
emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
loop_start);
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);
+
emit_insn_before (gen_move_insn (tem, bl->biv->src_reg),
loop_start);
emit_insn_before (gen_move_insn (bl->biv->src_reg,
&& (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)
+ && ((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)]
+ || (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);
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);
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 pseudo
- 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);
+ v->unrolled = 1;
/* 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 (! verify_addresses (v, giv_inc, unroll_number))
+ 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
#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++;
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
case it is needed later. */
tem = gen_reg_rtx (bl->biv->mode);
+ record_base_value (REGNO (tem), bl->biv->add_val);
/* Make sure loop_end is not the last insn. */
if (NEXT_INSN (loop_end) == 0)
emit_note_after (NOTE_INSN_DELETED, loop_end);
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);
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 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
