-/* Move constant computations out of loops.
- Copyright (C) 1987, 1988, 1989, 1991, 1992 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
Therefore, at all times, == 0 indicates an invariant register;
< 0 a conditionally invariant one. */
-static short *n_times_set;
+static int *n_times_set;
/* Original value of n_times_set; same except that this value
is not set negative for a reg whose sets have been made candidates
and not set to 0 for a reg that is moved. */
-static short *n_times_used;
+static int *n_times_used;
/* Index by register number, 1 indicates that the register
cannot be moved or strength reduced. */
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. */
static void check_final_value ();
static void record_giv ();
static void update_giv_derive ();
-static void delete_insn_forces ();
static int basic_induction_var ();
static rtx simplify_giv_expr ();
static int general_induction_var ();
init_loop ()
{
char *free_point = (char *) oballoc (1);
- rtx reg = gen_rtx (REG, word_mode, 0);
- rtx pow2 = GEN_INT (32);
- rtx lea;
- int i;
+ rtx reg = gen_rtx (REG, word_mode, LAST_VIRTUAL_REGISTER + 1);
add_cost = rtx_cost (gen_rtx (PLUS, word_mode, reg, reg), SET);
{
register rtx insn;
register int i;
- rtx end;
rtx last_insn;
loop_dump_stream = dumpfile;
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))
uid_luid = (int *) alloca (max_uid_for_loop * sizeof (int));
uid_loop_num = (int *) alloca (max_uid_for_loop * sizeof (int));
- bzero (uid_luid, max_uid_for_loop * sizeof (int));
- bzero (uid_loop_num, max_uid_for_loop * sizeof (int));
+ bzero ((char *) uid_luid, max_uid_for_loop * sizeof (int));
+ bzero ((char *) uid_loop_num, max_uid_for_loop * sizeof (int));
/* Allocate tables for recording each loop. We set each entry, so they need
not be zeroed. */
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. */
if it was used exactly once; contains const0_rtx if it was used more
than once. */
rtx *reg_single_usage = 0;
+ /* Nonzero if we are scanning instructions in a sub-loop. */
+ int loop_depth = 0;
- n_times_set = (short *) alloca (nregs * sizeof (short));
- n_times_used = (short *) alloca (nregs * sizeof (short));
+ n_times_set = (int *) alloca (nregs * sizeof (int));
+ n_times_used = (int *) alloca (nregs * sizeof (int));
may_not_optimize = (char *) alloca (nregs);
/* Determine whether this loop starts with a jump down to a test at
the setting of register I. If this loop has calls, set
reg_single_usage[I]. */
- bzero (n_times_set, nregs * sizeof (short));
+ bzero ((char *) n_times_set, nregs * sizeof (int));
bzero (may_not_optimize, nregs);
if (loop_has_call)
{
reg_single_usage = (rtx *) alloca (nregs * sizeof (rtx));
- bzero (reg_single_usage, nregs * sizeof (rtx));
+ bzero ((char *) reg_single_usage, nregs * sizeof (rtx));
}
count_loop_regs_set (loop_top ? loop_top : loop_start, end,
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
may_not_optimize[i] = 1, n_times_set[i] = 1;
- bcopy (n_times_set, n_times_used, nregs * sizeof (short));
+ bcopy ((char *) n_times_set, (char *) n_times_used, nregs * sizeof (int));
if (loop_dump_stream)
{
if (p == end)
{
if (loop_top != 0)
- p = NEXT_INSN (loop_top);
+ p = loop_top;
else
break;
if (p == scan_start)
;
/* In order to move a register, we need to have one of three cases:
(1) it is used only in the same basic block as the set
- (2) it is not a user variable.
+ (2) it is not a user variable and it is not used in the
+ exit test (this can cause the variable to be used
+ before it is set just like a user-variable).
(3) the set is guaranteed to be executed once the loop starts,
and the reg is not used until after that. */
else if (! ((! maybe_never
&& ! loop_reg_used_before_p (set, p, loop_start,
scan_start, end))
- || ! REG_USERVAR_P (SET_DEST (PATTERN (p)))
- || reg_in_basic_block_p (p, SET_DEST (PATTERN (p)))))
+ || (! REG_USERVAR_P (SET_DEST (set))
+ && ! REG_LOOP_TEST_P (SET_DEST (set)))
+ || reg_in_basic_block_p (p, SET_DEST (set))))
;
else if ((tem = invariant_p (src))
&& (dependencies == 0
if (reg_single_usage && reg_single_usage[regno] != 0
&& reg_single_usage[regno] != const0_rtx
- && regno_first_uid[regno] == INSN_UID (p)
- && (regno_last_uid[regno]
+ && REGNO_FIRST_UID (regno) == INSN_UID (p)
+ && (REGNO_LAST_UID (regno)
== INSN_UID (reg_single_usage[regno]))
&& n_times_set[REGNO (SET_DEST (set))] == 1
&& ! 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
a call-clobbered register and the life of REGNO
might span a call. */
&& ! modified_between_p (SET_SRC (set), p,
- reg_single_usage[regno])
+ reg_single_usage[regno])
+ && no_labels_between_p (p, reg_single_usage[regno])
&& 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;
/* Set M->cond if either invariant_p or consec_sets_invariant_p
returned 2 (only conditionally invariant). */
m->cond = ((tem | tem1 | tem2) > 1);
- m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end)
- || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start));
+ m->global = (uid_luid[REGNO_LAST_UID (regno)] > INSN_LUID (end)
+ || uid_luid[REGNO_FIRST_UID (regno)] < INSN_LUID (loop_start));
m->match = 0;
- m->lifetime = (uid_luid[regno_last_uid[regno]]
- - uid_luid[regno_first_uid[regno]]);
+ m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
+ - uid_luid[REGNO_FIRST_UID (regno)]);
m->savings = n_times_used[regno];
if (find_reg_note (p, REG_RETVAL, NULL_RTX))
m->savings += libcall_benefit (p);
if (m->consec > 0)
{
/* Skip this insn, not checking REG_LIBCALL notes. */
- p = NEXT_INSN (p);
+ p = next_nonnote_insn (p);
/* Skip the consecutive insns, if there are any. */
p = skip_consec_insns (p, m->consec);
/* Back up to the last insn of the consecutive group. */
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]]
+ || (uid_luid[REGNO_LAST_UID (regno)]
> INSN_LUID (end))
- || (uid_luid[regno_first_uid[regno]]
+ || (uid_luid[REGNO_FIRST_UID (regno)]
< INSN_LUID (p))
|| (labels_in_range_p
- (p, uid_luid[regno_first_uid[regno]])));
+ (p, uid_luid[REGNO_FIRST_UID (regno)])));
if (maybe_never && m->global)
m->savemode = GET_MODE (SET_SRC (set1));
else
m->regno = regno;
m->cond = 0;
m->match = 0;
- m->lifetime = (uid_luid[regno_last_uid[regno]]
- - uid_luid[regno_first_uid[regno]]);
+ m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
+ - uid_luid[REGNO_FIRST_UID (regno)]);
m->savings = 1;
n_times_set[regno] = -1;
/* Add M to the end of the chain MOVABLES. */
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
&& NEXT_INSN (NEXT_INSN (p)) == end
&& simplejump_p (p)))
maybe_never = 1;
- /* At the virtual top of a converted loop, insns are again known to
- be executed: logically, the loop begins here even though the exit
- code has been duplicated. */
- else if (GET_CODE (p) == NOTE
- && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
- maybe_never = call_passed = 0;
+ else if (GET_CODE (p) == NOTE)
+ {
+ /* At the virtual top of a converted loop, insns are again known to
+ be executed: logically, the loop begins here even though the exit
+ code has been duplicated. */
+ if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
+ maybe_never = call_passed = 0;
+ else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
+ loop_depth++;
+ else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
+ loop_depth--;
+ }
}
/* If one movable subsumes another, ignore that other. */
int regno = REGNO (reg);
rtx p;
- if (regno_first_uid[regno] != INSN_UID (insn))
+ if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
return 0;
/* Search this basic block for the already recorded last use of the reg. */
case INSN:
case CALL_INSN:
/* Ordinary insn: if this is the last use, we win. */
- if (regno_last_uid[regno] == INSN_UID (p))
+ if (REGNO_LAST_UID (regno) == INSN_UID (p))
return 1;
break;
case JUMP_INSN:
/* Jump insn: if this is the last use, we win. */
- if (regno_last_uid[regno] == INSN_UID (p))
+ if (REGNO_LAST_UID (regno) == INSN_UID (p))
return 1;
/* Otherwise, it's the end of the basic block, so we lose. */
return 0;
{
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)
this insn M->insn might not be where it dies.
But very likely this doesn't matter; what matters is
that M's reg is computed from M1's reg. */
- if (INSN_UID (m->insn) == regno_last_uid[regno]
+ if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
&& !m->done)
break;
if (m != 0 && m->set_src == m1->set_dest
{
register struct movable *m1;
int regno = m->regno;
- rtx reg_note, reg_note1;
bzero (matched_regs, nregs);
matched_regs[regno] = 1;
&& mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
{
register struct movable *m1;
- int first = uid_luid[regno_first_uid[m->regno]];
- int last = uid_luid[regno_last_uid[m->regno]];
+ int first = uid_luid[REGNO_FIRST_UID (m->regno)];
+ int last = uid_luid[REGNO_LAST_UID (m->regno)];
if (m0 == 0)
{
already combined together. */
for (m1 = movables; m1 != m; m1 = m1->next)
if (m1 == m0 || (m1->partial && m1->match == m0))
- if (! (uid_luid[regno_first_uid[m1->regno]] > last
- || uid_luid[regno_last_uid[m1->regno]] < first))
+ if (! (uid_luid[REGNO_FIRST_UID (m1->regno)] > last
+ || uid_luid[REGNO_LAST_UID (m1->regno)] < first))
goto overlap;
/* No overlap: we can combine this with the others. */
if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
{
- for (insn = insns; insn; insn = NEXT_INSN (insn))
- if (reg_mentioned_p (XEXP (x, 0), insn))
- REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL, XEXP (x, 0),
- REG_NOTES (insn));
+ rtx next = next_real_insn (XEXP (x, 0));
+
+ /* Don't record labels that refer to dispatch tables.
+ This is not necessary, since the tablejump references the same label.
+ And if we did record them, flow.c would make worse code. */
+ if (next == 0
+ || ! (GET_CODE (next) == JUMP_INSN
+ && (GET_CODE (PATTERN (next)) == ADDR_VEC
+ || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC)))
+ {
+ for (insn = insns; insn; insn = NEXT_INSN (insn))
+ if (reg_mentioned_p (XEXP (x, 0), insn))
+ REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL, XEXP (x, 0),
+ REG_NOTES (insn));
+ }
return;
}
char *already_moved = (char *) alloca (nregs);
bzero (already_moved, nregs);
- bzero (reg_map, nregs * sizeof (rtx));
+ bzero ((char *) reg_map, nregs * sizeof (rtx));
num_movables = 0;
}
p = delete_insn (p);
+ while (p && GET_CODE (p) == NOTE)
+ p = NEXT_INSN (p);
}
start_sequence ();
{
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
fn_address_insn);
if (GET_CODE (temp) == CALL_INSN)
- i1 = emit_call_insn_before (body, loop_start);
+ {
+ i1 = emit_call_insn_before (body, loop_start);
+ /* Because the USAGE information potentially
+ 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));
+ }
else
i1 = emit_insn_before (body, loop_start);
if (first == 0)
i1 = emit_insn_before (sequence, loop_start);
}
else if (GET_CODE (p) == CALL_INSN)
- i1 = emit_call_insn_before (PATTERN (p), loop_start);
+ {
+ i1 = emit_call_insn_before (PATTERN (p), loop_start);
+ /* Because the USAGE information potentially
+ 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));
+ }
else
i1 = emit_insn_before (PATTERN (p), loop_start);
REG_NOTES (i1) = REG_NOTES (p);
+ /* If there is a REG_EQUAL note present whose value is
+ not loop invariant, then delete it, since it may
+ cause problems with later optimization passes.
+ It is possible for cse to create such notes
+ like this as a result of record_jump_cond. */
+
+ if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
+ && ! invariant_p (XEXP (temp, 0)))
+ remove_note (i1, temp);
+
if (new_start == 0)
new_start = i1;
/* 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))))
to say it lives at least the full length of this loop.
This will help guide optimizations in outer loops. */
- if (uid_luid[regno_first_uid[regno]] > INSN_LUID (loop_start))
+ if (uid_luid[REGNO_FIRST_UID (regno)] > INSN_LUID (loop_start))
/* This is the old insn before all the moved insns.
We can't use the moved insn because it is out of range
in uid_luid. Only the old insns have luids. */
- regno_first_uid[regno] = INSN_UID (loop_start);
- if (uid_luid[regno_last_uid[regno]] < INSN_LUID (end))
- regno_last_uid[regno] = INSN_UID (end);
+ REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
+ if (uid_luid[REGNO_LAST_UID (regno)] < INSN_LUID (end))
+ REGNO_LAST_UID (regno) = INSN_UID (end);
/* Combine with this moved insn any other matching movables. */
{
replace_regs (PATTERN (p), reg_map, nregs, 0);
replace_regs (REG_NOTES (p), reg_map, nregs, 0);
+ INSN_CODE (p) = -1;
}
}
\f
find_and_verify_loops (f)
rtx f;
{
- rtx insn;
+ rtx insn, label;
int current_loop = -1;
int next_loop = -1;
int loop;
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;
uid_loop_num[INSN_UID (insn)] = current_loop;
}
- /* Now scan all JUMP_INSN's in the function. If any branches into a loop
- that it is not contained within, that loop is marked invalid.
+ /* Any loop containing a label used in an initializer must be invalidated,
+ because it can be jumped into from anywhere. */
+
+ for (label = forced_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;
+ }
+
+ /* 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
+ that label is marked invalid, because it could be jumped into from
+ anywhere.
Also look for blocks of code ending in an unconditional branch that
exits the loop. If such a block is surrounded by a conditional
possible second cse pass. */
for (insn = f; insn; insn = NEXT_INSN (insn))
- if (GET_CODE (insn) == JUMP_INSN)
+ if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
int this_loop_num = uid_loop_num[INSN_UID (insn)];
+ if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
+ {
+ rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
+ if (note)
+ {
+ int loop_num;
+
+ for (loop_num = uid_loop_num[INSN_UID (XEXP (note, 0))];
+ loop_num != -1;
+ loop_num = loop_outer_loop[loop_num])
+ loop_invalid[loop_num] = 1;
+ }
+ }
+
+ if (GET_CODE (insn) != JUMP_INSN)
+ continue;
+
mark_loop_jump (PATTERN (insn), this_loop_num);
/* See if this is an unconditional branch outside the loop. */
{
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 ();
}
if (--LABEL_NUSES (cond_label) == 0)
delete_insn (cond_label);
+
+ /* This loop will be continued with NEXT_INSN (insn). */
+ insn = PREV_INSN (insn);
}
}
}
case PLUS:
case MINUS:
case MULT:
- case LSHIFT:
mark_loop_jump (XEXP (x, 0), loop_num);
mark_loop_jump (XEXP (x, 1), loop_num);
return;
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
return;
default:
- /* Nothing else should occur in a JUMP_INSN. */
- abort ();
+ /* Treat anything else (such as a symbol_ref)
+ as a branch out of this loop, but not into any loop. */
+
+ if (loop_num != -1)
+ {
+ 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;
}
}
\f
This affects heuristics in strength_reduce. */
num_mem_sets++;
+ /* BLKmode MEM means all memory is clobbered. */
+ if (GET_MODE (x) == BLKmode)
+ unknown_address_altered = 1;
+
if (unknown_address_altered)
return;
&& MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (loop_store_mems[i]))
{
/* We are storing at the same address as previously noted. Save the
- wider reference, treating BLKmode as wider. */
- if (GET_MODE (x) == BLKmode
- || (GET_MODE_SIZE (GET_MODE (x))
- > GET_MODE_SIZE (GET_MODE (loop_store_mems[i]))))
+ wider reference. */
+ if (GET_MODE_SIZE (GET_MODE (x))
+ > GET_MODE_SIZE (GET_MODE (loop_store_mems[i])))
loop_store_mems[i] = x;
break;
}
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 == 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. */
return 1 + conditional;
}
-/* Return 1 if OTHER (a mem ref) overlaps the area of memory
- which is SIZE bytes starting at BASE. */
-
-int
-addr_overlap_p (other, base, size)
- rtx other;
- rtx base;
- HOST_WIDE_INT size;
-{
- HOST_WIDE_INT start = 0, end;
-
- if (GET_CODE (base) == CONST)
- base = XEXP (base, 0);
- if (GET_CODE (base) == PLUS
- && GET_CODE (XEXP (base, 1)) == CONST_INT)
- {
- start = INTVAL (XEXP (base, 1));
- base = XEXP (base, 0);
- }
-
- end = start + size;
- return refers_to_mem_p (other, base, start, end);
-}
\f
/* Return nonzero if all the insns in the loop that set REG
are INSN and the immediately following insns,
value |= this;
else if (temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
{
- this = invariant_p (XEXP (temp, 0));
+ /* If this is a libcall, then any invariant REG_EQUAL note is OK.
+ If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
+ notes are OK. */
+ this = (CONSTANT_P (XEXP (temp, 0))
+ || (find_reg_note (p, REG_RETVAL, NULL_RTX)
+ && invariant_p (XEXP (temp, 0))));
if (this != 0)
value |= this;
}
register int count = 0;
register rtx dest;
- bzero (last_set, nregs * sizeof (rtx));
+ bzero ((char *) last_set, nregs * sizeof (rtx));
for (insn = from; insn != to; insn = NEXT_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
}
}
}
+
if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
- bzero (last_set, nregs * sizeof (rtx));
+ bzero ((char *) last_set, nregs * sizeof (rtx));
}
*count_ptr = count;
}
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.
int call_seen;
rtx test;
rtx end_insert_before;
+ int loop_depth = 0;
reg_iv_type = (enum iv_mode *) alloca (max_reg_before_loop
* sizeof (enum iv_mode *));
/* Save insn immediately after the loop_end. Insns inserted after loop_end
must be put before this insn, so that they will appear in the right
- order (i.e. loop order). */
+ order (i.e. loop order).
- end_insert_before = NEXT_INSN (loop_end);
+ If loop_end is the end of the current function, then emit a
+ NOTE_INSN_DELETED after loop_end and set end_insert_before to the
+ dummy note insn. */
+ if (NEXT_INSN (loop_end) != 0)
+ end_insert_before = NEXT_INSN (loop_end);
+ else
+ end_insert_before = emit_note_after (NOTE_INSN_DELETED, loop_end);
/* Scan through loop to find all possible bivs. */
if (p == end)
{
if (loop_top != 0)
- p = NEXT_INSN (loop_top);
+ p = loop_top;
else
break;
if (p == scan_start)
&& REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
&& reg_iv_type[REGNO (dest_reg)] != NOT_BASIC_INDUCT)
{
- if (basic_induction_var (SET_SRC (set), dest_reg, p,
- &inc_val, &mult_val))
+ if (basic_induction_var (SET_SRC (set), GET_MODE (SET_SRC (set)),
+ dest_reg, p, &inc_val, &mult_val))
{
/* It is a possible basic induction variable.
Create and initialize an induction structure for it. */
/* 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)
{
if (insn == end)
{
if (loop_top != 0)
- insn = NEXT_INSN (loop_top);
+ insn = loop_top;
else
break;
if (insn == scan_start)
&& 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;
- /* At the virtual top of a converted loop, insns are again known to
- be executed each iteration: logically, the loop begins here
- even though the exit code has been duplicated. */
+ /* 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
- && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
- not_every_iteration = 0;
+ else if (GET_CODE (p) == NOTE)
+ {
+ /* At the virtual top of a converted loop, insns are again known to
+ be executed each iteration: logically, the loop begins here
+ even though the exit code has been duplicated. */
+ if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
+ not_every_iteration = 0;
+ else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
+ loop_depth++;
+ else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
+ loop_depth--;
+ }
/* Unlike in the code motion pass where MAYBE_NEVER indicates that
an insn may never be executed, NOT_EVERY_ITERATION indicates whether
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))
"Biv %d initialized at insn %d: initial value ",
bl->regno, INSN_UID (bl->init_insn));
- if (valid_initial_value_p (src, bl->init_insn, call_seen, loop_start))
+ if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
+ || GET_MODE (src) == VOIDmode)
+ && valid_initial_value_p (src, bl->init_insn, call_seen, loop_start))
{
bl->initial_value = src;
biv and a constant (or invariant), and it is not a biv. */
not_every_iteration = 0;
+ loop_depth = 0;
p = scan_start;
while (1)
{
if (p == end)
{
if (loop_top != 0)
- p = NEXT_INSN (loop_top);
+ p = loop_top;
else
break;
if (p == scan_start)
((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;
- /* At the virtual top of a converted loop, insns are again known to
- be executed each iteration: logically, the loop begins here
- even though the exit code has been duplicated. */
+ /* 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
- && NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP)
- not_every_iteration = 0;
+ else if (GET_CODE (p) == NOTE)
+ {
+ /* At the virtual top of a converted loop, insns are again known to
+ be executed each iteration: logically, the loop begins here
+ even though the exit code has been duplicated. */
+ if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
+ not_every_iteration = 0;
+ else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
+ loop_depth++;
+ else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
+ loop_depth--;
+ }
/* Unlike in the code motion pass where MAYBE_NEVER indicates that
an insn may never be executed, NOT_EVERY_ITERATION indicates whether
long as init_insn doesn't use the biv itself.
March 14, 1989 -- self@bayes.arc.nasa.gov */
- if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end)
+ if ((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]] >= INSN_LUID (bl->init_insn)
+ && uid_luid[REGNO_FIRST_UID (bl->regno)] >= INSN_LUID (bl->init_insn)
#ifdef HAVE_decrement_and_branch_until_zero
&& ! bl->nonneg
#endif
bl->regno);
fprintf (loop_dump_stream,
"First use: insn %d, last use: insn %d.\n",
- regno_first_uid[bl->regno],
- regno_last_uid[bl->regno]);
+ REGNO_FIRST_UID (bl->regno),
+ REGNO_LAST_UID (bl->regno));
}
}
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. */
- if (v->lifetime * threshold * benefit < insn_count)
+ /* A giv that depends on a reversed biv must be reduced if it is
+ used after the loop exit, otherwise, it would have the wrong
+ value after the loop exit. To make it simple, just reduce all
+ of such giv's whether or not we know they are used after the loop
+ exit. */
+
+ if (v->lifetime * threshold * benefit < insn_count
+ && ! bl->reversed)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
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. */
continue;
if (v->giv_type == DEST_REG
- && regno_first_uid[REGNO (v->dest_reg)] == INSN_UID (v->insn))
+ && REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
{
struct induction *v1;
for (v1 = bl->giv; v1; v1 = v1->next_iv)
- if (regno_last_uid[REGNO (v->dest_reg)] == INSN_UID (v1->insn))
+ if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
v->maybe_dead = 1;
}
if (v->giv_type == DEST_ADDR)
/* Store reduced reg as the address in the memref where we found
this giv. */
- *v->location = v->new_reg;
+ validate_change (v->insn, v->location, v->new_reg, 0);
else if (v->replaceable)
{
reg_map[REGNO (v->dest_reg)] = v->new_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;
{
replace_regs (PATTERN (p), reg_map, max_reg_before_loop, 0);
replace_regs (REG_NOTES (p), reg_map, max_reg_before_loop, 0);
+ INSN_CODE (p) = -1;
}
/* Unroll loops from within strength reduction so that we can use the
/* 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);
{
v->mode = GET_MODE (SET_DEST (set));
- v->lifetime = (uid_luid[regno_last_uid[REGNO (dest_reg)]]
- - uid_luid[regno_first_uid[REGNO (dest_reg)]]);
+ v->lifetime = (uid_luid[REGNO_LAST_UID (REGNO (dest_reg))]
+ - uid_luid[REGNO_FIRST_UID (REGNO (dest_reg))]);
v->times_used = n_times_used[REGNO (dest_reg)];
/* 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;
- the giv is not used outside the loop
- no assignments to the biv occur during the giv's lifetime. */
- if (regno_first_uid[REGNO (dest_reg)] == INSN_UID (insn)
+ if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
/* Previous line always fails if INSN was moved by loop opt. */
- && uid_luid[regno_last_uid[REGNO (dest_reg)]] < INSN_LUID (loop_end)
+ && uid_luid[REGNO_LAST_UID (REGNO (dest_reg))] < INSN_LUID (loop_end)
&& (! not_every_iteration
|| last_use_this_basic_block (dest_reg, insn)))
{
{
if (INSN_UID (b->insn) >= max_uid_for_loop
|| ((uid_luid[INSN_UID (b->insn)]
- >= uid_luid[regno_first_uid[REGNO (dest_reg)]])
+ >= uid_luid[REGNO_FIRST_UID (REGNO (dest_reg))])
&& (uid_luid[INSN_UID (b->insn)]
- <= uid_luid[regno_last_uid[REGNO (dest_reg)]])))
+ <= uid_luid[REGNO_LAST_UID (REGNO (dest_reg))])))
{
v->replaceable = 0;
v->not_replaceable = 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
{
{
struct iv_class *bl;
rtx final_value = 0;
- rtx tem;
bl = reg_biv_class[REGNO (v->src_reg)];
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))))
{
}
\f
/* Check whether an insn is an increment legitimate for a basic induction var.
- X is the source of insn P.
+ X is the source of insn P, or a part of it.
+ MODE is the mode in which X should be interpreted.
+
DEST_REG is the putative biv, also the destination of the insn.
We accept patterns of these forms:
REG = REG + INVARIANT (includes REG = REG - CONSTANT)
If we cannot find a biv, we return 0. */
static int
-basic_induction_var (x, dest_reg, p, inc_val, mult_val)
+basic_induction_var (x, mode, dest_reg, p, inc_val, mult_val)
register rtx x;
+ enum machine_mode mode;
rtx p;
rtx dest_reg;
rtx *inc_val;
if (invariant_p (arg) != 1)
return 0;
- *inc_val = convert_to_mode (GET_MODE (dest_reg), arg, 0);;
+ *inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
*mult_val = const1_rtx;
return 1;
/* If this is a SUBREG for a promoted variable, check the inner
value. */
if (SUBREG_PROMOTED_VAR_P (x))
- return basic_induction_var (SUBREG_REG (x), dest_reg, p,
- inc_val, mult_val);
+ 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
if (insn)
set = single_set (insn);
- if (set != 0 && SET_DEST (set) == x)
- return basic_induction_var (SET_SRC (set), dest_reg, insn,
+ if (set != 0
+ && (SET_DEST (set) == x
+ || (GET_CODE (SET_DEST (set)) == SUBREG
+ && (GET_MODE_SIZE (GET_MODE (SET_DEST (set)))
+ <= UNITS_PER_WORD)
+ && SUBREG_REG (SET_DEST (set)) == x)))
+ return basic_induction_var (SET_SRC (set),
+ (GET_MODE (SET_SRC (set)) == VOIDmode
+ ? GET_MODE (x)
+ : 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
case CONST:
if (loops_enclosed == 1)
{
- *inc_val = convert_to_mode (GET_MODE (dest_reg), x, 0);;
+ /* Possible bug here? Perhaps we don't know the mode of X. */
+ *inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
*mult_val = const0_rtx;
return 1;
}
return 0;
case SIGN_EXTEND:
- return basic_induction_var (XEXP (x, 0), dest_reg, p,
- inc_val, mult_val);
+ return basic_induction_var (XEXP (x, 0), GET_MODE (XEXP (x, 0)),
+ dest_reg, p, inc_val, mult_val);
case ASHIFTRT:
/* Similar, since this can be a sign extension. */
for (insn = PREV_INSN (p);
&& INTVAL (XEXP (x, 1)) >= 0
&& GET_CODE (SET_SRC (set)) == ASHIFT
&& XEXP (x, 1) == XEXP (SET_SRC (set), 1))
- return basic_induction_var (XEXP (SET_SRC (set), 0), dest_reg, insn,
- inc_val, mult_val);
+ return basic_induction_var (XEXP (SET_SRC (set), 0),
+ GET_MODE (XEXP (x, 0)),
+ dest_reg, insn, inc_val, mult_val);
return 0;
default:
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:
}
case ASHIFT:
- case LSHIFT:
/* Shift by constant is multiply by power of two. */
if (GET_CODE (XEXP (x, 1)) != CONST_INT)
return 0;
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;
rtx jump_label;
rtx final_value;
rtx start_value;
- enum rtx_code branch_code;
rtx new_add_val;
rtx comparison;
rtx before_comparison;
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;
+ /* 1 if the loop has no memory store, or it has a single memory store
+ which is reversible. */
+ int reversible_mem_store = 1;
for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
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];
}
}
+ /* If the loop has a single store, and the destination address is
+ invariant, then we can't reverse the loop, because this address
+ might then have the wrong value at loop exit.
+ This would work if the source was invariant also, however, in that
+ case, the insn should have been moved out of the loop. */
+
+ if (num_mem_sets == 1)
+ reversible_mem_store
+ = (! unknown_address_altered
+ && ! invariant_p (XEXP (loop_store_mems[0], 0)));
+
/* This code only acts for innermost loops. Also it simplifies
the memory address check by only reversing loops with
zero or one memory access.
if (num_nonfixed_reads <= 1
&& !loop_has_call
&& !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 condition = get_condition_for_loop (PREV_INSN (loop_end));
- int win;
rtx tem;
/* Loop can be reversed. */
/* 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);
/* Emit an insn after the end of the loop to set the biv's
proper exit value if it is used anywhere outside the loop. */
- if ((regno_last_uid[bl->regno]
+ if ((REGNO_LAST_UID (bl->regno)
!= INSN_UID (PREV_INSN (PREV_INSN (loop_end))))
|| ! bl->init_insn
- || regno_first_uid[bl->regno] != INSN_UID (bl->init_insn))
+ || REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
emit_insn_after (gen_move_insn (reg, final_value),
loop_end);
{
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,
int threshold, insn_count;
{
rtx reg = bl->biv->dest_reg;
- rtx p, set;
- struct induction *v;
+ rtx p;
/* Scan all insns in the loop, stopping if we find one that uses the
biv in a way that we cannot eliminate. */
{
/* 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->mode == mode)
+ && ! v->ignore && ! v->maybe_dead && v->always_computable
+ && 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->mode == mode)
+ && ! v->ignore && ! v->maybe_dead && v->always_computable
+ && 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;
emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
where);
- if (validate_change (insn, &SET_SRC (PATTERN (insn)),
- gen_rtx (COMPARE, VOIDmode,
- v->new_reg, tem), 0))
+ /* Substitute the new register for its invariant value in
+ the compare expression. */
+ XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
+ if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
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)
- && ! v->ignore && ! v->maybe_dead
+ && (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->mode == mode)
+ && ! v->ignore && ! v->maybe_dead && v->always_computable
+ && 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->mode == mode)
+ && ! v->ignore && ! v->maybe_dead && v->always_computable
+ && 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;
n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
n = NEXT_INSN (n))
{
- if (regno_last_uid[REGNO (reg)] == INSN_UID (n))
+ if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
return 1;
}
return 0;
and hence this insn will never be the last use of x. */
if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
&& INSN_UID (insn) < max_uid_for_loop
- && uid_luid[regno_last_uid[REGNO (x)]] < uid_luid[INSN_UID (insn)])
- regno_last_uid[REGNO (x)] = INSN_UID (insn);
+ && uid_luid[REGNO_LAST_UID (REGNO (x))] < uid_luid[INSN_UID (insn)])
+ REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
else
{
register int i, j;
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));
reverse_code = 1;
x = SET_SRC (set);
}
+ else
+ break;
}
else if (reg_set_p (op0, prev))
if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
return 0;
- /* Canonicalize any ordered comparison with integers involving equality. */
- if (GET_CODE (op1) == CONST_INT)
+ /* Canonicalize any ordered comparison with integers involving equality
+ if we can do computations in the relevant mode and we do not
+ overflow. */
+
+ if (GET_CODE (op1) == CONST_INT
+ && GET_MODE (op0) != VOIDmode
+ && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
{
HOST_WIDE_INT const_val = INTVAL (op1);
unsigned HOST_WIDE_INT uconst_val = const_val;
+ unsigned HOST_WIDE_INT max_val
+ = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
switch (code)
- {
- case LE:
- code = LT;
- op1 = GEN_INT (const_val + 1);
- break;
+ {
+ case LE:
+ if (const_val != max_val >> 1)
+ code = LT, op1 = GEN_INT (const_val + 1);
+ break;
- case GE:
- code = GT;
- op1 = GEN_INT (const_val - 1);
- break;
+ case GE:
+ if (const_val
+ != (((HOST_WIDE_INT) 1
+ << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
+ code = GT, op1 = GEN_INT (const_val - 1);
+ break;
- case LEU:
- code = LTU;
- op1 = GEN_INT (uconst_val + 1);
- break;
+ case LEU:
+ if (uconst_val != max_val)
+ code = LTU, op1 = GEN_INT (uconst_val + 1);
+ break;
- case GEU:
- code = GTU;
- op1 = GEN_INT (uconst_val - 1);
- break;
- }
+ case GEU:
+ if (uconst_val != 0)
+ code = GTU, op1 = GEN_INT (uconst_val - 1);
+ break;
+ }
}
/* If this was floating-point and we reversed anything other than an
EQ or NE, return zero. */
if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
&& did_reverse_condition && code != NE && code != EQ
+ && ! flag_fast_math
&& GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
return 0;
OSDN Git Service
