-/* Move constant computations out of loops.
- Copyright (C) 1987, 88, 89, 91, 92, 93, 1994 Free Software Foundation, Inc.
+/* Perform various loop optimizations, including strength reduction.
+ Copyright (C) 1987, 88, 89, 91-6, 1997 Free Software Foundation, Inc.
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. */
/* This is the loop optimization pass of the compiler.
#include "flags.h"
#include "real.h"
#include "loop.h"
+#include "except.h"
/* Vector mapping INSN_UIDs to luids.
The luids are like uids but increase monotonically always.
rtx *loop_number_exit_labels;
+/* Indexed by loop number, counts the number of LABEL_REFs on
+ loop_number_exit_labels for this loop and all loops nested inside it. */
+
+int *loop_number_exit_count;
+
/* Holds the number of loop iterations. It is zero if the number could not be
calculated. Must be unsigned since the number of iterations can
be as high as 2^wordsize-1. For loops with a wider iterator, this number
struct movable
{
rtx insn; /* A movable insn */
- rtx set_src; /* The expression this reg is set from. */
- rtx set_dest; /* The destination of this SET. */
+ rtx set_src; /* The expression this reg is set from. */
+ rtx set_dest; /* The destination of this SET. */
rtx dependencies; /* When INSN is libcall, this is an EXPR_LIST
- of any registers used within the LIBCALL. */
+ of any registers used within the LIBCALL. */
int consec; /* Number of consecutive following insns
that must be moved with this one. */
int regno; /* The register it sets */
invariant. */
unsigned int move_insn : 1; /* 1 means that we call emit_move_insn to
load SRC, rather than copying INSN. */
- unsigned int is_equiv : 1; /* 1 means a REG_EQUIV is present on INSN. */
+ unsigned int is_equiv : 1; /* 1 means a REG_EQUIV is present on INSN. */
enum machine_mode savemode; /* Nonzero means it is a mode for a low part
that we should avoid changing when clearing
the rest of the reg. */
init_loop ()
{
char *free_point = (char *) oballoc (1);
- rtx reg = gen_rtx (REG, word_mode, 0);
+ rtx reg = gen_rtx (REG, word_mode, LAST_VIRTUAL_REGISTER + 1);
add_cost = rtx_cost (gen_rtx (PLUS, word_mode, reg, reg), SET);
regs_may_share = 0;
- /* Count the number of loops. */
+ /* Count the number of loops. */
max_loop_num = 0;
for (insn = f; insn; insn = NEXT_INSN (insn))
loop_outer_loop = (int *) alloca (max_loop_num * sizeof (int));
loop_invalid = (char *) alloca (max_loop_num * sizeof (char));
loop_number_exit_labels = (rtx *) alloca (max_loop_num * sizeof (rtx));
+ loop_number_exit_count = (int *) alloca (max_loop_num * sizeof (int));
/* Find and process each loop.
First, find them, and record them in order of their beginnings. */
&& ! side_effects_p (SET_SRC (set))
&& ! find_reg_note (p, REG_RETVAL, NULL_RTX)
#ifdef SMALL_REGISTER_CLASSES
- && ! (GET_CODE (SET_SRC (set)) == REG
+ && ! (SMALL_REGISTER_CLASSES
+ && GET_CODE (SET_SRC (set)) == REG
&& REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)
#endif
/* This test is not redundant; SET_SRC (set) might be
&& validate_replace_rtx (SET_DEST (set), SET_SRC (set),
reg_single_usage[regno]))
{
- /* Replace any usage in a REG_EQUAL note. */
+ /* Replace any usage in a REG_EQUAL note. Must copy the
+ new source, so that we don't get rtx sharing between the
+ SET_SOURCE and REG_NOTES of insn p. */
REG_NOTES (reg_single_usage[regno])
= replace_rtx (REG_NOTES (reg_single_usage[regno]),
- SET_DEST (set), SET_SRC (set));
+ SET_DEST (set), copy_rtx (SET_SRC (set)));
PUT_CODE (p, NOTE);
NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
If this insn was made by loop, we don't know its
INSN_LUID and hence must make a conservative
- assumption. */
+ assumption. */
m->global = (INSN_UID (p) >= max_uid_for_loop
|| (uid_luid[regno_last_uid[regno]]
> INSN_LUID (end))
executed during each iteration. Therefore, we can
only move out sets of trivial variables
(those not used after the loop). */
- /* This code appears in three places, once in scan_loop, and twice
- in strength_reduce. */
+ /* Similar code appears twice in strength_reduce. */
else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
/* If we enter the loop in the middle, and scan around to the
beginning, don't set maybe_never for that. This must be an
{
if (GET_CODE (insn) == CALL_INSN)
benefit += 10; /* Assume at least this many insns in a library
- routine. */
+ routine. */
else if (GET_CODE (insn) == INSN
&& GET_CODE (PATTERN (insn)) != USE
&& GET_CODE (PATTERN (insn)) != CLOBBER)
{
rtx i1, temp;
- /* If first insn of libcall sequence, skip to end. */
+ /* If first insn of libcall sequence, skip to end. */
/* Do this at start of loop, since p is guaranteed to
be an insn here. */
if (GET_CODE (p) != NOTE
contains objects other than hard registers
we need to copy it. */
if (CALL_INSN_FUNCTION_USAGE (temp))
- CALL_INSN_FUNCTION_USAGE (i1) =
- copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
+ CALL_INSN_FUNCTION_USAGE (i1)
+ = copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
}
else
i1 = emit_insn_before (body, loop_start);
contains objects other than hard registers
we need to copy it. */
if (CALL_INSN_FUNCTION_USAGE (p))
- CALL_INSN_FUNCTION_USAGE (i1) =
- copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
+ CALL_INSN_FUNCTION_USAGE (i1)
+ = copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
}
else
i1 = emit_insn_before (PATTERN (p), loop_start);
/* This isn't needed because REG_NOTES is copied
below and is wrong since P might be a PARALLEL. */
if (REG_NOTES (i1) == 0
- && ! m->partial /* But not if it's a zero-extend clr. */
+ && ! m->partial /* But not if it's a zero-extend clr. */
&& ! m->global /* and not if used outside the loop
(since it might get set outside). */
&& CONSTANT_P (SET_SRC (PATTERN (p))))
loop_outer_loop[next_loop] = current_loop;
loop_invalid[next_loop] = 0;
loop_number_exit_labels[next_loop] = 0;
+ loop_number_exit_count[next_loop] = 0;
current_loop = next_loop;
break;
loop_invalid[loop_num] = 1;
}
+ /* Any loop containing a label used for an exception handler must be
+ invalidated, because it can be jumped into from anywhere. */
+
+ for (label = exception_handler_labels; label; label = XEXP (label, 1))
+ {
+ int loop_num;
+
+ for (loop_num = uid_loop_num[INSN_UID (XEXP (label, 0))];
+ loop_num != -1;
+ loop_num = loop_outer_loop[loop_num])
+ loop_invalid[loop_num] = 1;
+ }
+
/* Now scan all insn's in the function. If any JUMP_INSN branches into a
loop that it is not contained within, that loop is marked invalid.
If any INSN or CALL_INSN uses a label's address, then the loop containing
{
rtx p;
rtx our_next = next_real_insn (insn);
+ int dest_loop;
+ int outer_loop = -1;
/* Go backwards until we reach the start of the loop, a label,
or a JUMP_INSN. */
p = PREV_INSN (p))
;
+ /* Check for the case where we have a jump to an inner nested
+ loop, and do not perform the optimization in that case. */
+
+ if (JUMP_LABEL (insn))
+ {
+ dest_loop = uid_loop_num[INSN_UID (JUMP_LABEL (insn))];
+ if (dest_loop != -1)
+ {
+ for (outer_loop = dest_loop; outer_loop != -1;
+ outer_loop = loop_outer_loop[outer_loop])
+ if (outer_loop == this_loop_num)
+ break;
+ }
+ }
+
+ /* Make sure that the target of P is within the current loop. */
+
+ if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
+ && uid_loop_num[INSN_UID (JUMP_LABEL (p))] != this_loop_num)
+ outer_loop = this_loop_num;
+
/* If we stopped on a JUMP_INSN to the next insn after INSN,
we have a block of code to try to move.
of the block, invert the jump in P and point it to that label,
and move the block of code to the spot we found. */
- if (GET_CODE (p) == JUMP_INSN
+ if (outer_loop == -1
+ && GET_CODE (p) == JUMP_INSN
&& JUMP_LABEL (p) != 0
/* Just ignore jumps to labels that were never emitted.
These always indicate compilation errors. */
LABEL_NUSES (cond_label)++;
/* Verify that uid_loop_num is large enough and that
- we can invert P. */
+ we can invert P. */
if (invert_jump (p, new_label))
{
rtx q, r;
LABEL_OUTSIDE_LOOP_P bit. */
if (JUMP_LABEL (insn))
{
+ int loop_num;
+
for (q = 0,
r = loop_number_exit_labels[this_loop_num];
r; q = r, r = LABEL_NEXTREF (r))
break;
}
- /* If we didn't find it, then something is wrong. */
+ for (loop_num = this_loop_num;
+ loop_num != -1 && loop_num != target_loop_num;
+ loop_num = loop_outer_loop[loop_num])
+ loop_number_exit_count[loop_num]--;
+
+ /* If we didn't find it, then something is wrong. */
if (! r)
abort ();
}
mark this LABEL_REF so we know that this branch should predict
false. */
- if (dest_loop != loop_num && loop_num != -1)
+ /* A check to make sure the label is not in an inner nested loop,
+ since this does not count as a loop exit. */
+ if (dest_loop != -1)
+ {
+ for (outer_loop = dest_loop; outer_loop != -1;
+ outer_loop = loop_outer_loop[outer_loop])
+ if (outer_loop == loop_num)
+ break;
+ }
+ else
+ outer_loop = -1;
+
+ if (loop_num != -1 && outer_loop == -1)
{
LABEL_OUTSIDE_LOOP_P (x) = 1;
LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
loop_number_exit_labels[loop_num] = x;
+
+ for (outer_loop = loop_num;
+ outer_loop != -1 && outer_loop != dest_loop;
+ outer_loop = loop_outer_loop[outer_loop])
+ loop_number_exit_count[outer_loop]++;
}
/* If this is inside a loop, but not in the current loop or one enclosed
if (loop_num != -1)
{
- LABEL_OUTSIDE_LOOP_P (x) = 1;
- LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
loop_number_exit_labels[loop_num] = x;
- }
+ for (outer_loop = loop_num; outer_loop != -1;
+ outer_loop = loop_outer_loop[outer_loop])
+ loop_number_exit_count[outer_loop]++;
+ }
return;
}
}
case REG:
/* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
since the reg might be set by initialization within the loop. */
- if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
- || x == arg_pointer_rtx)
+
+ if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
+ || x == arg_pointer_rtx)
+ && ! current_function_has_nonlocal_goto)
return 1;
+
if (loop_has_call
&& REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
return 0;
+
if (n_times_set[REGNO (x)] < 0)
return 2;
+
return n_times_set[REGNO (x)] == 0;
case MEM:
+ /* Volatile memory references must be rejected. Do this before
+ checking for read-only items, so that volatile read-only items
+ will be rejected also. */
+ if (MEM_VOLATILE_P (x))
+ return 0;
+
/* Read-only items (such as constants in a constant pool) are
invariant if their address is. */
if (RTX_UNCHANGING_P (x))
/* If we filled the table (or had a subroutine call), any location
in memory could have been clobbered. */
- if (unknown_address_altered
- /* Don't mess with volatile memory references. */
- || MEM_VOLATILE_P (x))
+ if (unknown_address_altered)
return 0;
/* See if there is any dependence between a store and this load. */
it is safe to keep the value in a register for the duration of the
loop. One tricky thing is that the copying of the value back from the
register has to be done on all exits from the loop. You need to check that
- all the exits from the loop go to the same place. */
+ all the exits from the loop go to the same place. */
/* ??? The interaction of biv elimination, and recognition of 'constant'
- bivs, may cause problems. */
+ bivs, may cause problems. */
/* ??? Add heuristics so that DEST_ADDR strength reduction does not cause
performance problems.
/* Past CODE_LABEL, we get to insns that may be executed multiple
times. The only way we can be sure that they can't is if every
every jump insn between here and the end of the loop either
- returns, exits the loop, or is a forward jump. */
+ returns, exits the loop, is a forward jump, or is a jump
+ to the loop start. */
if (GET_CODE (p) == CODE_LABEL)
{
&& GET_CODE (PATTERN (insn)) != RETURN
&& (! condjump_p (insn)
|| (JUMP_LABEL (insn) != 0
+ && JUMP_LABEL (insn) != scan_start
&& (INSN_UID (JUMP_LABEL (insn)) >= max_uid_for_loop
|| INSN_UID (insn) >= max_uid_for_loop
|| (INSN_LUID (JUMP_LABEL (insn))
< INSN_LUID (insn))))))
- {
- maybe_multiple = 1;
- break;
- }
+ {
+ maybe_multiple = 1;
+ break;
+ }
}
}
- /* Past a label or a jump, we get to insns for which we can't count
- on whether or how many times they will be executed during each
- iteration. */
- /* This code appears in three places, once in scan_loop, and twice
- in strength_reduce. */
- if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
+ /* Past a jump, we get to insns for which we can't count
+ on whether they will be executed during each iteration. */
+ /* This code appears twice in strength_reduce. There is also similar
+ code in scan_loop. */
+ if (GET_CODE (p) == JUMP_INSN
/* If we enter the loop in the middle, and scan around to the
beginning, don't set not_every_iteration for that.
This can be any kind of jump, since we want to know if insns
will be executed if the loop is executed. */
- && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
+ && ! (JUMP_LABEL (p) == loop_top
&& ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
|| (NEXT_INSN (p) == loop_end && condjump_p (p)))))
- not_every_iteration = 1;
+ {
+ rtx label = 0;
+
+ /* If this is a jump outside the loop, then it also doesn't
+ matter. Check to see if the target of this branch is on the
+ loop_number_exits_labels list. */
+
+ for (label = loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]];
+ label;
+ label = LABEL_NEXTREF (label))
+ if (XEXP (label, 0) == JUMP_LABEL (p))
+ break;
+
+ if (! label)
+ not_every_iteration = 1;
+ }
else if (GET_CODE (p) == NOTE)
{
Therefore, if we have just passed a label and have no more labels
between here and the test insn of the loop, we know these insns
- will be executed each iteration. This can also happen if we
- have just passed a jump, for example, when there are nested loops. */
+ will be executed each iteration. */
if (not_every_iteration && GET_CODE (p) == CODE_LABEL
&& no_labels_between_p (p, loop_end))
((benefit = general_induction_var (SET_SRC (set),
&src_reg, &add_val,
&mult_val))
- /* Equivalent expression is a giv. */
+ /* Equivalent expression is a giv. */
|| ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
&& (benefit = general_induction_var (XEXP (regnote, 0),
&src_reg,
&& dest_reg != src_reg
/* This must be the only place where the register is set. */
&& (n_times_set[REGNO (dest_reg)] == 1
- /* or all sets must be consecutive and make a giv. */
+ /* or all sets must be consecutive and make a giv. */
|| (benefit = consec_sets_giv (benefit, p,
src_reg, dest_reg,
&add_val, &mult_val))))
|| GET_CODE (p) == CODE_LABEL)
update_giv_derive (p);
- /* Past a label or a jump, we get to insns for which we can't count
- on whether or how many times they will be executed during each
- iteration. */
- /* This code appears in three places, once in scan_loop, and twice
- in strength_reduce. */
- if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
- /* If we enter the loop in the middle, and scan around
- to the beginning, don't set not_every_iteration for that.
+ /* Past a jump, we get to insns for which we can't count
+ on whether they will be executed during each iteration. */
+ /* This code appears twice in strength_reduce. There is also similar
+ code in scan_loop. */
+ if (GET_CODE (p) == JUMP_INSN
+ /* If we enter the loop in the middle, and scan around to the
+ beginning, don't set not_every_iteration for that.
This can be any kind of jump, since we want to know if insns
will be executed if the loop is executed. */
- && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
+ && ! (JUMP_LABEL (p) == loop_top
&& ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
|| (NEXT_INSN (p) == loop_end && condjump_p (p)))))
- not_every_iteration = 1;
+ {
+ rtx label = 0;
+
+ /* If this is a jump outside the loop, then it also doesn't
+ matter. Check to see if the target of this branch is on the
+ loop_number_exits_labels list. */
+
+ for (label = loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]];
+ label;
+ label = LABEL_NEXTREF (label))
+ if (XEXP (label, 0) == JUMP_LABEL (p))
+ break;
+
+ if (! label)
+ not_every_iteration = 1;
+ }
else if (GET_CODE (p) == NOTE)
{
unchanged (recompute it from the biv each time it is used).
This decision can be made independently for each giv. */
- /* ??? Perhaps attempt to guess whether autoincrement will handle
- some of the new add insns; if so, can increase BENEFIT
- (undo the subtraction of add_cost that was done above). */
+#ifdef AUTO_INC_DEC
+ /* Attempt to guess whether autoincrement will handle some of the
+ new add insns; if so, increase BENEFIT (undo the subtraction of
+ add_cost that was done above). */
+ if (v->giv_type == DEST_ADDR
+ && GET_CODE (v->mult_val) == CONST_INT)
+ {
+#if defined (HAVE_POST_INCREMENT) || defined (HAVE_PRE_INCREMENT)
+ if (INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
+ benefit += add_cost * bl->biv_count;
+#endif
+#if defined (HAVE_POST_DECREMENT) || defined (HAVE_PRE_DECREMENT)
+ if (-INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
+ benefit += add_cost * bl->biv_count;
+#endif
+ }
+#endif
/* If an insn is not to be strength reduced, then set its ignore
flag, and clear all_reduced. */
struct induction *tv;
if (! v->ignore && v->same == 0)
{
+ int auto_inc_opt = 0;
+
v->new_reg = gen_reg_rtx (v->mode);
- /* For each place where the biv is incremented,
- add an insn to increment the new, reduced reg for the giv. */
+#ifdef AUTO_INC_DEC
+ /* If the target has auto-increment addressing modes, and
+ this is an address giv, then try to put the increment
+ immediately after its use, so that flow can create an
+ auto-increment addressing mode. */
+ if (v->giv_type == DEST_ADDR && bl->biv_count == 1
+ && bl->biv->always_executed && ! bl->biv->maybe_multiple
+ /* We don't handle reversed biv's because bl->biv->insn
+ does not have a valid INSN_LUID. */
+ && ! bl->reversed
+ && v->always_executed && ! v->maybe_multiple)
+ {
+ /* If other giv's have been combined with this one, then
+ this will work only if all uses of the other giv's occur
+ before this giv's insn. This is difficult to check.
+
+ We simplify this by looking for the common case where
+ there is one DEST_REG giv, and this giv's insn is the
+ last use of the dest_reg of that DEST_REG giv. If the
+ the increment occurs after the address giv, then we can
+ perform the optimization. (Otherwise, the increment
+ would have to go before other_giv, and we would not be
+ able to combine it with the address giv to get an
+ auto-inc address.) */
+ if (v->combined_with)
+ {
+ struct induction *other_giv = 0;
+
+ for (tv = bl->giv; tv; tv = tv->next_iv)
+ if (tv->same == v)
+ {
+ if (other_giv)
+ break;
+ else
+ other_giv = tv;
+ }
+ if (! tv && other_giv
+ && (regno_last_uid[REGNO (other_giv->dest_reg)]
+ == INSN_UID (v->insn))
+ && INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
+ auto_inc_opt = 1;
+ }
+ /* Check for case where increment is before the the address
+ giv. */
+ else if (INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn))
+ auto_inc_opt = -1;
+ else
+ auto_inc_opt = 1;
+
+#ifdef HAVE_cc0
+ {
+ rtx prev;
+
+ /* We can't put an insn immediately after one setting
+ cc0, or immediately before one using cc0. */
+ if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
+ || (auto_inc_opt == -1
+ && (prev = prev_nonnote_insn (v->insn)) != 0
+ && GET_RTX_CLASS (GET_CODE (prev)) == 'i'
+ && sets_cc0_p (PATTERN (prev))))
+ auto_inc_opt = 0;
+ }
+#endif
+
+ if (auto_inc_opt)
+ v->auto_inc_opt = 1;
+ }
+#endif
+
+ /* For each place where the biv is incremented, add an insn
+ to increment the new, reduced reg for the giv. */
for (tv = bl->biv; tv; tv = tv->next_iv)
{
+ rtx insert_before;
+
+ if (! auto_inc_opt)
+ insert_before = tv->insn;
+ else if (auto_inc_opt == 1)
+ insert_before = NEXT_INSN (v->insn);
+ else
+ insert_before = v->insn;
+
if (tv->mult_val == const1_rtx)
emit_iv_add_mult (tv->add_val, v->mult_val,
- v->new_reg, v->new_reg, tv->insn);
+ v->new_reg, v->new_reg, insert_before);
else /* tv->mult_val == const0_rtx */
/* A multiply is acceptable here
since this is presumed to be seldom executed. */
emit_iv_add_mult (tv->add_val, v->mult_val,
- v->add_val, v->new_reg, tv->insn);
+ v->add_val, v->new_reg, insert_before);
}
/* Add code at loop start to initialize giv's reduced reg. */
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)]])
insert_before = loop_start;
else
insert_before = end_insert_before;
or otherwise drop straight in, based on this test, then
we might want to rewrite it also. This way some later
pass has more hope of removing the initialization of this
- biv entirely. */
+ biv entirely. */
/* If final_value != 0, then the biv may be used after loop end
and we must emit an insn to set it just in case.
Reversed bivs already have an insn after the loop setting their
value, so we don't need another one. We can't calculate the
- proper final value for such a biv here anyways. */
+ proper final value for such a biv here anyways. */
if (final_value != 0 && ! bl->reversed)
{
rtx insert_before;
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)]])
insert_before = loop_start;
else
insert_before = end_insert_before;
/* Don't use call-clobbered registers across a call which clobbers it. On
some machines, don't use any hard registers at all. */
if (REGNO (x) < FIRST_PSEUDO_REGISTER
-#ifndef SMALL_REGISTER_CLASSES
- && call_used_regs[REGNO (x)] && call_seen
+ && (
+#ifdef SMALL_REGISTER_CLASSES
+ SMALL_REGISTER_CLASSES
+#else
+ 0
#endif
+ || (call_used_regs[REGNO (x)] && call_seen))
)
return 0;
v->add_val = inc_val;
v->mode = GET_MODE (dest_reg);
v->always_computable = ! not_every_iteration;
+ v->always_executed = ! not_every_iteration;
v->maybe_multiple = maybe_multiple;
/* Add this to the reg's iv_class, creating a class
v->ignore = 0;
v->new_reg = 0;
v->final_value = 0;
+ v->same_insn = 0;
+ v->auto_inc_opt = 0;
/* The v->always_computable field is used in update_giv_derive, to
determine whether a giv can be used to derive another giv. For a
else
v->always_computable = ! not_every_iteration;
+ v->always_executed = ! not_every_iteration;
+
if (type == DEST_ADDR)
{
v->mode = GET_MODE (*location);
/* If the lifetime is zero, it means that this register is
really a dead store. So mark this as a giv that can be
- ignored. This will not prevent the biv from being eliminated. */
+ ignored. This will not prevent the biv from being eliminated. */
if (v->lifetime == 0)
v->ignore = 1;
}
}
- /* Check each insn between the first and last use of the giv,
- and fail if any of them are branches that jump to a named label
- outside this range, but still inside the loop. This catches
- cases of spaghetti code where the execution order of insns
- is not linear, and hence the above test fails. For example,
- in the following code, j is not replaceable:
- for (i = 0; i < 100; ) {
- L0: j = 4*i; goto L1;
- L2: k = j; goto L3;
- L1: i++; goto L2;
- L3: ; }
- printf ("k = %d\n", k); }
- This test is conservative, but this test succeeds rarely enough
- that it isn't a problem. See also check_final_value below. */
-
+ /* If there are any backwards branches that go from after the
+ biv update to before it, then this giv is not replaceable. */
if (v->replaceable)
- for (p = insn;
- INSN_UID (p) >= max_uid_for_loop
- || INSN_LUID (p) < uid_luid[regno_last_uid[REGNO (dest_reg)]];
- p = NEXT_INSN (p))
- {
- if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
- && LABEL_NAME (JUMP_LABEL (p))
- && ((INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start)
- && (INSN_LUID (JUMP_LABEL (p))
- < uid_luid[regno_first_uid[REGNO (dest_reg)]]))
- || (INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end)
- && (INSN_LUID (JUMP_LABEL (p))
- > uid_luid[regno_last_uid[REGNO (dest_reg)]]))))
- {
- v->replaceable = 0;
- v->not_replaceable = 1;
-
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Found branch outside giv lifetime.\n");
-
- break;
- }
- }
+ for (b = bl->biv; b; b = b->next_iv)
+ if (back_branch_in_range_p (b->insn, loop_start, loop_end))
+ {
+ v->replaceable = 0;
+ v->not_replaceable = 1;
+ break;
+ }
}
else
{
if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
&& LABEL_NAME (JUMP_LABEL (p))
- && ((INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (v->insn)
- && INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start))
+ && ((INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop)
+ || (INSN_UID (v->insn) >= max_uid_for_loop)
+ || (INSN_UID (last_giv_use) >= max_uid_for_loop)
+ || (INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (v->insn)
+ && INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop_start))
|| (INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (last_giv_use)
&& INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop_end))))
{
if (SUBREG_PROMOTED_VAR_P (x))
return basic_induction_var (SUBREG_REG (x), GET_MODE (SUBREG_REG (x)),
dest_reg, p, inc_val, mult_val);
+ return 0;
case REG:
/* If this register is assigned in the previous insn, look at its
: GET_MODE (SET_SRC (set))),
dest_reg, insn,
inc_val, mult_val);
- /* ... fall through ... */
+ /* ... fall through ... */
/* Can accept constant setting of biv only when inside inner most loop.
Otherwise, a biv of an inner loop may be incorrectly recognized
benefit);
case MINUS:
- /* Handle "a - b" as "a + b * (-1)". */
+ /* Handle "a - b" as "a + b * (-1)". */
return simplify_giv_expr (gen_rtx (PLUS, mode,
XEXP (x, 0),
gen_rtx (MULT, mode,
return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
case USE:
- /* invar * invar. Not giv. */
+ /* invar * invar. Not giv. */
return 0;
case MULT:
return 0;
}
\f
+#ifdef GIV_SORT_CRITERION
+/* Compare two givs and sort the most desirable one for combinations first.
+ This is used only in one qsort call below. */
+
+static int
+giv_sort (x, y)
+ struct induction **x, **y;
+{
+ GIV_SORT_CRITERION (*x, *y);
+
+ return 0;
+}
+#endif
+
/* Check all pairs of givs for iv_class BL and see if any can be combined with
any other. If so, point SAME to the giv combined with and set NEW_REG to
be an expression (in terms of the other giv's DEST_REG) equivalent to the
combine_givs (bl)
struct iv_class *bl;
{
- struct induction *g1, *g2;
- int pass;
+ struct induction *g1, *g2, **giv_array, *temp_iv;
+ int i, j, giv_count, pass;
+
+ /* Count givs, because bl->giv_count is incorrect here. */
+ giv_count = 0;
+ for (g1 = bl->giv; g1; g1 = g1->next_iv)
+ giv_count++;
+ giv_array
+ = (struct induction **) alloca (giv_count * sizeof (struct induction *));
+ i = 0;
for (g1 = bl->giv; g1; g1 = g1->next_iv)
- for (pass = 0; pass <= 1; pass++)
- for (g2 = bl->giv; g2; g2 = g2->next_iv)
- if (g1 != g2
- /* First try to combine with replaceable givs, then all givs. */
- && (g1->replaceable || pass == 1)
- /* If either has already been combined or is to be ignored, can't
- combine. */
- && ! g1->ignore && ! g2->ignore && ! g1->same && ! g2->same
- /* If something has been based on G2, G2 cannot itself be based
- on something else. */
- && ! g2->combined_with
- && combine_givs_p (g1, g2))
+ giv_array[i++] = g1;
+
+#ifdef GIV_SORT_CRITERION
+ /* Sort the givs if GIV_SORT_CRITERION is defined.
+ This is usually defined for processors which lack
+ negative register offsets so more givs may be combined. */
+
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream, "%d givs counted, sorting...\n", giv_count);
+
+ qsort (giv_array, giv_count, sizeof (struct induction *), giv_sort);
+#endif
+
+ for (i = 0; i < giv_count; i++)
+ {
+ g1 = giv_array[i];
+ for (pass = 0; pass <= 1; pass++)
+ for (j = 0; j < giv_count; j++)
{
- /* g2->new_reg set by `combine_givs_p' */
- g2->same = g1;
- g1->combined_with = 1;
- g1->benefit += g2->benefit;
- /* ??? The new final_[bg]iv_value code does a much better job
- of finding replaceable giv's, and hence this code may no
- longer be necessary. */
- if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
- g1->benefit -= copy_cost;
- g1->lifetime += g2->lifetime;
- g1->times_used += g2->times_used;
-
- if (loop_dump_stream)
- fprintf (loop_dump_stream, "giv at %d combined with giv at %d\n",
- INSN_UID (g2->insn), INSN_UID (g1->insn));
+ g2 = giv_array[j];
+ if (g1 != g2
+ /* First try to combine with replaceable givs, then all givs. */
+ && (g1->replaceable || pass == 1)
+ /* If either has already been combined or is to be ignored, can't
+ combine. */
+ && ! g1->ignore && ! g2->ignore && ! g1->same && ! g2->same
+ /* If something has been based on G2, G2 cannot itself be based
+ on something else. */
+ && ! g2->combined_with
+ && combine_givs_p (g1, g2))
+ {
+ /* g2->new_reg set by `combine_givs_p' */
+ g2->same = g1;
+ g1->combined_with = 1;
+
+ /* If one of these givs is a DEST_REG that was only used
+ once, by the other giv, this is actually a single use.
+ The DEST_REG has the correct cost, while the other giv
+ counts the REG use too often. */
+ if (g2->giv_type == DEST_REG
+ && n_times_used[REGNO (g2->dest_reg)] == 1
+ && reg_mentioned_p (g2->dest_reg, PATTERN (g1->insn)))
+ g1->benefit = g2->benefit;
+ else if (g1->giv_type != DEST_REG
+ || n_times_used[REGNO (g1->dest_reg)] != 1
+ || ! reg_mentioned_p (g1->dest_reg,
+ PATTERN (g2->insn)))
+ {
+ g1->benefit += g2->benefit;
+ g1->times_used += g2->times_used;
+ }
+ /* ??? The new final_[bg]iv_value code does a much better job
+ of finding replaceable giv's, and hence this code may no
+ longer be necessary. */
+ if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
+ g1->benefit -= copy_cost;
+ g1->lifetime += g2->lifetime;
+
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream, "giv at %d combined with giv at %d\n",
+ INSN_UID (g2->insn), INSN_UID (g1->insn));
+ }
}
+ }
}
\f
/* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
a = copy_rtx (a);
b = copy_rtx (b);
- /* Increase the lifetime of any invariants moved further in code. */
+ /* Increase the lifetime of any invariants moved further in code. */
update_reg_last_use (a, insert_before);
update_reg_last_use (b, insert_before);
update_reg_last_use (m, insert_before);
char *storage = (char *) obstack_alloc (&temp_obstack, 0);
int win = 1;
- /* If only one is constant, make it B. */
+ /* If only one is constant, make it B. */
if (GET_CODE (a) == CONST_INT)
tmp = a, a = b, b = tmp;
if (GET_CODE (bl->initial_value) == CONST_INT
&& INTVAL (bl->initial_value) > 0
- && (INTVAL (bl->initial_value) %
- (-INTVAL (bl->biv->add_val))) == 0)
+ && (INTVAL (bl->initial_value)
+ % (-INTVAL (bl->biv->add_val))) == 0)
{
/* register always nonnegative, add REG_NOTE to branch */
REG_NOTES (PREV_INSN (loop_end))
all memory references have non-overlapping addresses
(obviously true if only one write)
allow 2 insns for the compare/jump at the end of the loop. */
+ /* Also, we must avoid any instructions which use both the reversed
+ biv and another biv. Such instructions will fail if the loop is
+ reversed. We meet this condition by requiring that either
+ no_use_except_counting is true, or else that there is only
+ one biv. */
int num_nonfixed_reads = 0;
/* 1 if the iteration var is used only to count iterations. */
int no_use_except_counting = 0;
num_nonfixed_reads += count_nonfixed_reads (PATTERN (p));
if (bl->giv_count == 0
- && ! loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]])
+ && ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
{
rtx bivreg = regno_reg_rtx[bl->regno];
&& !loop_has_volatile
&& reversible_mem_store
&& (no_use_except_counting
- || (bl->giv_count + bl->biv_count + num_mem_sets
- + num_movables + 2 == insn_count)))
+ || ((bl->giv_count + bl->biv_count + num_mem_sets
+ + num_movables + 2 == insn_count)
+ && (bl == loop_iv_list && bl->next == 0))))
{
rtx tem;
/* Save some info needed to produce the new insns. */
reg = bl->biv->dest_reg;
jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
+ if (jump_label == pc_rtx)
+ jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
new_add_val = GEN_INT (- INTVAL (bl->biv->add_val));
final_value = XEXP (comparison, 1);
{
JUMP_LABEL (tem) = XEXP (jump_label, 0);
- /* Increment of LABEL_NUSES done above. */
+ /* Increment of LABEL_NUSES done above. */
/* Register is now always nonnegative,
so add REG_NONNEG note to the branch. */
REG_NOTES (tem) = gen_rtx (EXPR_LIST, REG_NONNEG, NULL_RTX,
{
/* Can replace with any giv that was reduced and
that has (MULT_VAL != 0) and (ADD_VAL == 0).
- Require a constant for MULT_VAL, so we know it's nonzero. */
+ Require a constant for MULT_VAL, so we know it's nonzero.
+ ??? We disable this optimization to avoid potential
+ overflows. */
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
&& v->add_val == const0_rtx
&& ! v->ignore && ! v->maybe_dead && v->always_computable
- && v->mode == mode)
+ && v->mode == mode
+ && 0)
{
+ /* If the giv V had the auto-inc address optimization applied
+ to it, and INSN occurs between the giv insn and the biv
+ insn, then we must adjust the value used here.
+ This is rare, so we don't bother to do so. */
+ if (v->auto_inc_opt
+ && ((INSN_LUID (v->insn) < INSN_LUID (insn)
+ && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
+ || (INSN_LUID (v->insn) > INSN_LUID (insn)
+ && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
+ continue;
+
if (! eliminate_p)
return 1;
/* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0);
replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL).
- Require a constant for MULT_VAL, so we know it's nonzero. */
+ Require a constant for MULT_VAL, so we know it's nonzero.
+ ??? Do this only if ADD_VAL is a pointer to avoid a potential
+ overflow problem. */
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
&& ! v->ignore && ! v->maybe_dead && v->always_computable
- && v->mode == mode)
+ && v->mode == mode
+ && (GET_CODE (v->add_val) == SYMBOL_REF
+ || GET_CODE (v->add_val) == LABEL_REF
+ || GET_CODE (v->add_val) == CONST
+ || (GET_CODE (v->add_val) == REG
+ && REGNO_POINTER_FLAG (REGNO (v->add_val)))))
{
+ /* If the giv V had the auto-inc address optimization applied
+ to it, and INSN occurs between the giv insn and the biv
+ insn, then we must adjust the value used here.
+ This is rare, so we don't bother to do so. */
+ if (v->auto_inc_opt
+ && ((INSN_LUID (v->insn) < INSN_LUID (insn)
+ && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
+ || (INSN_LUID (v->insn) > INSN_LUID (insn)
+ && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
+ continue;
+
if (! eliminate_p)
return 1;
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
- && CONSTANT_P (v->add_val)
+ && (GET_CODE (v->add_val) == SYMBOL_REF
+ || GET_CODE (v->add_val) == LABEL_REF
+ || GET_CODE (v->add_val) == CONST
+ || (GET_CODE (v->add_val) == REG
+ && REGNO_POINTER_FLAG (REGNO (v->add_val))))
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode)
{
+ /* If the giv V had the auto-inc address optimization applied
+ to it, and INSN occurs between the giv insn and the biv
+ insn, then we must adjust the value used here.
+ This is rare, so we don't bother to do so. */
+ if (v->auto_inc_opt
+ && ((INSN_LUID (v->insn) < INSN_LUID (insn)
+ && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
+ || (INSN_LUID (v->insn) > INSN_LUID (insn)
+ && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
+ continue;
+
if (! eliminate_p)
return 1;
}
/* Look for giv with positive constant mult_val and nonconst add_val.
- Insert insns to calculate new compare value. */
+ Insert insns to calculate new compare value.
+ ??? Turn this off due to possible overflow. */
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
&& ! v->ignore && ! v->maybe_dead && v->always_computable
- && v->mode == mode)
+ && v->mode == mode
+ && 0)
{
rtx tem;
+ /* If the giv V had the auto-inc address optimization applied
+ to it, and INSN occurs between the giv insn and the biv
+ insn, then we must adjust the value used here.
+ This is rare, so we don't bother to do so. */
+ if (v->auto_inc_opt
+ && ((INSN_LUID (v->insn) < INSN_LUID (insn)
+ && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
+ || (INSN_LUID (v->insn) > INSN_LUID (insn)
+ && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
+ continue;
+
if (! eliminate_p)
return 1;
if (invariant_p (arg) == 1)
{
/* Look for giv with constant positive mult_val and nonconst
- add_val. Insert insns to compute new compare value. */
+ add_val. Insert insns to compute new compare value.
+ ??? Turn this off due to possible overflow. */
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
&& ! v->ignore && ! v->maybe_dead && v->always_computable
- && v->mode == mode)
+ && v->mode == mode
+ && 0)
{
rtx tem;
+ /* If the giv V had the auto-inc address optimization applied
+ to it, and INSN occurs between the giv insn and the biv
+ insn, then we must adjust the value used here.
+ This is rare, so we don't bother to do so. */
+ if (v->auto_inc_opt
+ && ((INSN_LUID (v->insn) < INSN_LUID (insn)
+ && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
+ || (INSN_LUID (v->insn) > INSN_LUID (insn)
+ && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
+ continue;
+
if (! eliminate_p)
return 1;
&& rtx_equal_p (tv->add_val, v->add_val)
&& tv->mode == mode)
{
+ /* If the giv V had the auto-inc address optimization applied
+ to it, and INSN occurs between the giv insn and the biv
+ insn, then we must adjust the value used here.
+ This is rare, so we don't bother to do so. */
+ if (v->auto_inc_opt
+ && ((INSN_LUID (v->insn) < INSN_LUID (insn)
+ && INSN_LUID (insn) < INSN_LUID (bl->biv->insn))
+ || (INSN_LUID (v->insn) > INSN_LUID (insn)
+ && INSN_LUID (insn) > INSN_LUID (bl->biv->insn))))
+ continue;
+
if (! eliminate_p)
return 1;
the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
in cse.c */
- while (GET_RTX_CLASS (code) == '<' && op1 == const0_rtx)
+ while (GET_RTX_CLASS (code) == '<' && op1 == CONST0_RTX (GET_MODE (op0)))
{
/* Set non-zero when we find something of interest. */
rtx x = 0;
/* If this is setting OP0, get what it sets it to if it looks
relevant. */
- if (SET_DEST (set) == op0)
+ if (rtx_equal_p (SET_DEST (set), op0))
{
enum machine_mode inner_mode = GET_MODE (SET_SRC (set));
OSDN Git Service
