#include "config.h"
#include "system.h"
#include "rtl.h"
+#include "tm_p.h"
#include "obstack.h"
+#include "function.h"
#include "expr.h"
#include "insn-config.h"
#include "insn-flags.h"
#include "except.h"
#include "toplev.h"
+/* Information about the loop being processed used to compute
+ the number of loop iterations for loop unrolling and doloop
+ optimization. */
+static struct loop_info this_loop_info;
+
/* Vector mapping INSN_UIDs to luids.
The luids are like uids but increase monotonically always.
We use them to see whether a jump comes from outside a given loop. */
int *loop_number_exit_count;
-/* Nonzero if there is a subroutine call in the current loop. */
-
-static int loop_has_call;
-
-/* Nonzero if there is a volatile memory reference in the current
- loop. */
-
-static int loop_has_volatile;
-
-/* Nonzero if there is a tablejump in the current loop. */
-
-static int loop_has_tablejump;
-
-/* Added loop_continue which is the NOTE_INSN_LOOP_CONT of the
- current loop. A continue statement will generate a branch to
- NEXT_INSN (loop_continue). */
-
-static rtx loop_continue;
-
/* Indexed by register number, contains the number of times the reg
is set during the loop being scanned.
During code motion, a negative value indicates a reg that has been
static varray_type may_not_optimize;
+/* Contains the insn in which a register was used if it was used
+ exactly once; contains const0_rtx if it was used more than once. */
+
+static varray_type reg_single_usage;
+
/* Nonzero means reg N has already been moved out of one loop.
This reduces the desire to move it out of another. */
static rtx loop_store_mems;
+/* The insn where the first of these was found. */
+static rtx first_loop_store_insn;
+
typedef struct loop_mem_info {
rtx mem; /* The MEM itself. */
rtx reg; /* Corresponding pseudo, if any. */
static int loop_mems_allocated;
-/* Nonzero if we don't know what MEMs were changed in the current loop.
- This happens if the loop contains a call (in which case `loop_has_call'
- will also be set) or if we store into more than NUM_STORES MEMs. */
+/* Nonzero if we don't know what MEMs were changed in the current
+ loop. This happens if the loop contains a call (in which case
+ `loop_info->has_call' will also be set) or if we store into more
+ than NUM_STORES MEMs. */
static int unknown_address_altered;
/* Count of memory write instructions discovered in the loop. */
static int num_mem_sets;
-/* Number of loops contained within the current one, including itself. */
-static int loops_enclosed;
-
/* Bound on pseudo register number before loop optimization.
A pseudo has valid regscan info if its number is < max_reg_before_loop. */
int max_reg_before_loop;
FILE *loop_dump_stream;
+/* For communicating return values from note_set_pseudo_multiple_uses. */
+static int note_set_pseudo_multiple_uses_retval;
+
/* Forward declarations. */
static void verify_dominator PROTO((int));
static void find_and_verify_loops PROTO((rtx));
static void mark_loop_jump PROTO((rtx, int));
-static void prescan_loop PROTO((rtx, rtx));
+static void prescan_loop PROTO((rtx, rtx, struct loop_info *));
static int reg_in_basic_block_p PROTO((rtx, rtx));
static int consec_sets_invariant_p PROTO((rtx, int, rtx));
-static rtx libcall_other_reg PROTO((rtx, rtx));
static int labels_in_range_p PROTO((rtx, int));
static void count_one_set PROTO((rtx, rtx, varray_type, rtx *));
static void count_loop_regs_set PROTO((rtx, rtx, varray_type, varray_type,
int *, int));
static void note_addr_stored PROTO((rtx, rtx));
+static void note_set_pseudo_multiple_uses PROTO((rtx, rtx));
static int loop_reg_used_before_p PROTO((rtx, rtx, rtx, rtx, rtx));
-static void scan_loop PROTO((rtx, rtx, int, int));
+static void scan_loop PROTO((rtx, rtx, rtx, int, int));
#if 0
static void replace_call_address PROTO((rtx, rtx, rtx));
#endif
static void add_label_notes PROTO((rtx, rtx));
static void move_movables PROTO((struct movable *, int, int, rtx, rtx, int));
static int count_nonfixed_reads PROTO((rtx));
-static void strength_reduce PROTO((rtx, rtx, rtx, int, rtx, rtx, int, int));
+static void strength_reduce PROTO((rtx, rtx, rtx, int, rtx, rtx,
+ struct loop_info *, rtx, int, int));
static void find_single_use_in_loop PROTO((rtx, rtx, varray_type));
static int valid_initial_value_p PROTO((rtx, rtx, int, rtx));
-static void find_mem_givs PROTO((rtx, rtx, int, rtx, rtx));
+static void find_mem_givs PROTO((rtx, rtx, int, int, rtx, rtx));
static void record_biv PROTO((struct induction *, rtx, rtx, rtx, rtx, rtx *, int, int));
static void check_final_value PROTO((struct induction *, rtx, rtx,
unsigned HOST_WIDE_INT));
-static void record_giv PROTO((struct induction *, rtx, rtx, rtx, rtx, rtx, int, enum g_types, int, rtx *, rtx, rtx));
+static void record_giv PROTO((struct induction *, rtx, rtx, rtx, rtx, rtx, int, enum g_types, int, int, rtx *, rtx, rtx));
static void update_giv_derive PROTO((rtx));
static int basic_induction_var PROTO((rtx, enum machine_mode, rtx, rtx, rtx *, rtx *, rtx **));
static rtx simplify_giv_expr PROTO((rtx, int *));
static void update_reg_last_use PROTO((rtx, rtx));
static rtx next_insn_in_loop PROTO((rtx, rtx, rtx, rtx));
static void load_mems_and_recount_loop_regs_set PROTO((rtx, rtx, rtx,
- rtx, varray_type,
- int *));
+ rtx, int *));
static void load_mems PROTO((rtx, rtx, rtx, rtx));
static int insert_loop_mem PROTO((rtx *, void *));
static int replace_loop_mem PROTO((rtx *, void *));
int indirect_jump_in_function = 0;
static int indirect_jump_in_function_p PROTO((rtx));
-static int compute_luids PROTO ((rtx, rtx, int));
+static int compute_luids PROTO((rtx, rtx, int));
+
+static int biv_elimination_giv_has_0_offset PROTO((struct induction *,
+ struct induction *, rtx));
\f
/* Relative gain of eliminating various kinds of operations. */
static int add_cost;
for (i = max_loop_num-1; i >= 0; i--)
if (! loop_invalid[i] && loop_number_loop_ends[i])
scan_loop (loop_number_loop_starts[i], loop_number_loop_ends[i],
- unroll_p, bct_p);
+ loop_number_loop_cont[i], unroll_p, bct_p);
/* If debugging and unrolling loops, we must replicate the tree nodes
corresponding to the blocks inside the loop, so that the original one
/* Optimize one loop whose start is LOOP_START and end is END.
LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
- NOTE_INSN_LOOP_END. */
+ NOTE_INSN_LOOP_END.
+ LOOP_CONT is the NOTE_INSN_LOOP_CONT. */
/* ??? Could also move memory writes out of loops if the destination address
is invariant, the source is invariant, the memory write is not volatile,
write, then we can also mark the memory read as invariant. */
static void
-scan_loop (loop_start, end, unroll_p, bct_p)
- rtx loop_start, end;
+scan_loop (loop_start, end, loop_cont, unroll_p, bct_p)
+ rtx loop_start, end, loop_cont;
int unroll_p, bct_p;
{
register int i;
since in that case saving an insn makes more difference
and more registers are available. */
int threshold;
- /* If we have calls, contains the insn in which a register was used
- if it was used exactly once; contains const0_rtx if it was used more
- than once. */
- varray_type reg_single_usage = 0;
/* Nonzero if we are scanning instructions in a sub-loop. */
int loop_depth = 0;
int nregs;
+ struct loop_info *loop_info = &this_loop_info;
/* Determine whether this loop starts with a jump down to a test at
the end. This will occur for a small number of loops with a test
scan_start = p;
/* Set up variables describing this loop. */
- prescan_loop (loop_start, end);
- threshold = (loop_has_call ? 1 : 2) * (1 + n_non_fixed_regs);
+ prescan_loop (loop_start, end, loop_info);
+ threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
/* If loop has a jump before the first label,
the true entry is the target of that jump.
/* Count number of times each reg is set during this loop.
Set VARRAY_CHAR (may_not_optimize, I) if it is not safe to move out
- the setting of register I. If this loop has calls, set
- VARRAY_RTX (reg_single_usage, I). */
+ the setting of register I. Set VARRAY_RTX (reg_single_usage, I). */
/* Allocate extra space for REGS that might be created by
load_mems. We allocate a little extra slop as well, in the hopes
VARRAY_INT_INIT (set_in_loop, nregs, "set_in_loop");
VARRAY_INT_INIT (n_times_set, nregs, "n_times_set");
VARRAY_CHAR_INIT (may_not_optimize, nregs, "may_not_optimize");
-
- if (loop_has_call)
- VARRAY_RTX_INIT (reg_single_usage, nregs, "reg_single_usage");
+ VARRAY_RTX_INIT (reg_single_usage, nregs, "reg_single_usage");
count_loop_regs_set (loop_top ? loop_top : loop_start, end,
may_not_optimize, reg_single_usage, &insn_count, nregs);
{
fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
INSN_UID (loop_start), INSN_UID (end), insn_count);
- if (loop_continue)
+ if (loop_info->cont)
fprintf (loop_dump_stream, "Continue at insn %d.\n",
- INSN_UID (loop_continue));
+ INSN_UID (loop_info->cont));
}
/* Scan through the loop finding insns that are safe to move.
We don't know its life-span, so we can't compute the benefit. */
if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
;
- else if (/* The set is not guaranteed to be executed one
- the loop starts, or the value before the set is
- needed before the set occurs... */
- (maybe_never
- || loop_reg_used_before_p (set, p, loop_start,
- scan_start, end))
- /* And the register is used in basic blocks other
+ else if (/* The register is used in basic blocks other
than the one where it is set (meaning that
something after this point in the loop might
depend on its value before the set). */
- && !reg_in_basic_block_p (p, SET_DEST (set)))
+ ! reg_in_basic_block_p (p, SET_DEST (set))
+ /* And the set is not guaranteed to be executed one
+ the loop starts, or the value before the set is
+ needed before the set occurs...
+
+ ??? Note we have quadratic behaviour here, mitigated
+ by the fact that the previous test will often fail for
+ large loops. Rather than re-scanning the entire loop
+ each time for register usage, we should build tables
+ of the register usage and use them here instead. */
+ && (maybe_never
+ || loop_reg_used_before_p (set, p, loop_start,
+ scan_start, end)))
/* It is unsafe to move the set.
This code used to consider it OK to move a set of a variable
Don't do this if P has a REG_RETVAL note or if we have
SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
- if (reg_single_usage && VARRAY_RTX (reg_single_usage, regno) != 0
+ if (loop_info->has_call
+ && VARRAY_RTX (reg_single_usage, regno) != 0
&& VARRAY_RTX (reg_single_usage, regno) != const0_rtx
&& REGNO_FIRST_UID (regno) == INSN_UID (p)
&& (REGNO_LAST_UID (regno)
VARRAY_INT (set_in_loop, i) = VARRAY_INT (n_times_set, i);
/* Now that we've moved some things out of the loop, we might be able to
- hoist even more memory references. There's no need to pass
- reg_single_usage this time, since we're done with it. */
+ hoist even more memory references. */
load_mems_and_recount_loop_regs_set (scan_start, end, loop_top,
- loop_start, 0,
- &insn_count);
-
- /* set_in_loop is still used by invariant_p, so we can't free it now. */
- VARRAY_FREE (reg_single_usage);
+ loop_start, &insn_count);
if (flag_strength_reduce)
{
the_movables = movables;
strength_reduce (scan_start, end, loop_top,
- insn_count, loop_start, end, unroll_p, bct_p);
+ insn_count, loop_start, end,
+ loop_info, loop_cont, unroll_p, bct_p);
}
+ VARRAY_FREE (reg_single_usage);
VARRAY_FREE (set_in_loop);
VARRAY_FREE (n_times_set);
VARRAY_FREE (may_not_optimize);
rtx *output;
{
enum rtx_code code;
- char *fmt;
+ const char *fmt;
int i;
code = GET_CODE (in_this);
If there are none, return 0.
If there are one or more, return an EXPR_LIST containing all of them. */
-static rtx
+rtx
libcall_other_reg (insn, equiv)
rtx insn, equiv;
{
register int j;
register struct movable *m;
register enum rtx_code code;
- register char *fmt;
+ register const char *fmt;
if (x == y)
return 1;
}
\f
/* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
- insns in INSNS which use thet reference. */
+ insns in INSNS which use the reference. */
static void
add_label_notes (x, insns)
{
enum rtx_code code = GET_CODE (x);
int i, j;
- char *fmt;
+ const char *fmt;
rtx insn;
if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
{
int count;
register struct movable *m1;
- rtx first;
+ rtx first = NULL_RTX;
/* Now move the insns that set the reg. */
/* Schedule the reg loaded by M1
for replacement so that shares the reg of M.
If the modes differ (only possible in restricted
- circumstances, make a SUBREG. */
+ circumstances, make a SUBREG.
+
+ Note this assumes that the target dependent files
+ treat REG and SUBREG equally, including within
+ GO_IF_LEGITIMATE_ADDRESS and in all the
+ predicates since we never verify that replacing the
+ original register with a SUBREG results in a
+ recognizable insn. */
if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
reg_map[m1->regno] = m->set_dest;
else
{
register enum rtx_code code;
register int i;
- register char *fmt;
+ register const char *fmt;
if (x == 0)
return;
{
register enum rtx_code code;
register int i;
- register char *fmt;
+ register const char *fmt;
int value;
if (x == 0)
/* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */
- new = gen_rtx_SET (VOIDmode,
- gen_rtx_STRICT_LOW_PART (VOIDmode,
- gen_rtx_SUBREG (GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)),
- SET_DEST (PATTERN (p)),
- 0)),
- XEXP (SET_SRC (PATTERN (p)), 0));
+ new
+ = gen_rtx_SET
+ (VOIDmode,
+ gen_rtx_STRICT_LOW_PART
+ (VOIDmode,
+ gen_rtx_SUBREG (GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)),
+ SET_DEST (PATTERN (p)), 0)),
+ XEXP (SET_SRC (PATTERN (p)), 0));
+
insn_code_number = recog (new, p);
if (insn_code_number)
register int i;
/* Clear destination register before the loop. */
- emit_insn_before (gen_rtx_SET (VOIDmode, SET_DEST (PATTERN (p)),
- const0_rtx),
+ emit_insn_before (gen_rtx_SET (VOIDmode,
+ SET_DEST (PATTERN (p)), const0_rtx),
loop_start);
/* Inside the loop, just load the low part. */
}
#endif
\f
-/* Scan a loop setting the variables `unknown_address_altered',
- `num_mem_sets', `loop_continue', `loops_enclosed', `loop_has_call',
- `loop_has_volatile', and `loop_has_tablejump'.
- Also, fill in the array `loop_mems' and the list `loop_store_mems'. */
+/* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
+ `has_call', `has_volatile', and `has_tablejump' within LOOP_INFO.
+ Set the global variables `unknown_address_altered' and
+ `num_mem_sets'. Also, fill in the array `loop_mems' and the list
+ `loop_store_mems'. */
static void
-prescan_loop (start, end)
+prescan_loop (start, end, loop_info)
rtx start, end;
+ struct loop_info *loop_info;
{
register int level = 1;
rtx insn;
- int loop_has_multiple_exit_targets = 0;
/* The label after END. Jumping here is just like falling off the
end of the loop. We use next_nonnote_insn instead of next_label
as a hedge against the (pathological) case where some actual insn
might end up between the two. */
rtx exit_target = next_nonnote_insn (end);
- if (exit_target == NULL_RTX || GET_CODE (exit_target) != CODE_LABEL)
- loop_has_multiple_exit_targets = 1;
+
+ loop_info->num = uid_loop_num [INSN_UID (start)];
+ loop_info->has_indirect_jump = indirect_jump_in_function;
+ loop_info->has_call = 0;
+ loop_info->has_volatile = 0;
+ loop_info->has_tablejump = 0;
+ loop_info->loops_enclosed = 1;
+ loop_info->has_multiple_exit_targets = 0;
+ loop_info->cont = 0;
+ loop_info->vtop = 0;
unknown_address_altered = 0;
- loop_has_call = 0;
- loop_has_volatile = 0;
- loop_has_tablejump = 0;
loop_store_mems = NULL_RTX;
+ first_loop_store_insn = NULL_RTX;
loop_mems_idx = 0;
-
num_mem_sets = 0;
- loops_enclosed = 1;
- loop_continue = 0;
for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
insn = NEXT_INSN (insn))
{
++level;
/* Count number of loops contained in this one. */
- loops_enclosed++;
+ loop_info->loops_enclosed++;
}
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
{
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
{
if (level == 1)
- loop_continue = insn;
+ loop_info->cont = insn;
+ }
+ else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP)
+ {
+ /* If there is a NOTE_INSN_LOOP_VTOP, then this is a for
+ or while style loop, with a loop exit test at the
+ start. Thus, we can assume that the loop condition
+ was true when the loop was entered. */
+ if (level == 1)
+ loop_info->vtop = insn;
}
}
else if (GET_CODE (insn) == CALL_INSN)
{
if (! CONST_CALL_P (insn))
unknown_address_altered = 1;
- loop_has_call = 1;
+ loop_info->has_call = 1;
}
else if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
{
rtx label2 = NULL_RTX;
if (volatile_refs_p (PATTERN (insn)))
- loop_has_volatile = 1;
+ loop_info->has_volatile = 1;
if (GET_CODE (insn) == JUMP_INSN
&& (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_VEC))
- loop_has_tablejump = 1;
+ loop_info->has_tablejump = 1;
note_stores (PATTERN (insn), note_addr_stored);
+ if (! first_loop_store_insn && loop_store_mems)
+ first_loop_store_insn = insn;
- if (! loop_has_multiple_exit_targets
+ if (! loop_info->has_multiple_exit_targets
&& GET_CODE (insn) == JUMP_INSN
&& GET_CODE (PATTERN (insn)) == SET
&& SET_DEST (PATTERN (insn)) == pc_rtx)
if (GET_CODE (label1) != LABEL_REF)
{
/* Something tricky. */
- loop_has_multiple_exit_targets = 1;
+ loop_info->has_multiple_exit_targets = 1;
break;
}
else if (XEXP (label1, 0) != exit_target
&& LABEL_OUTSIDE_LOOP_P (label1))
{
/* A jump outside the current loop. */
- loop_has_multiple_exit_targets = 1;
+ loop_info->has_multiple_exit_targets = 1;
break;
}
}
}
}
else if (GET_CODE (insn) == RETURN)
- loop_has_multiple_exit_targets = 1;
+ loop_info->has_multiple_exit_targets = 1;
}
/* Now, rescan the loop, setting up the LOOP_MEMS array. */
!unknown_address_altered
/* An exception thrown by a called function might land us
anywhere. */
- && !loop_has_call
+ && !loop_info->has_call
/* We don't want loads for MEMs moved to a location before the
one at which their stack memory becomes allocated. (Note
that this is not a problem for malloc, etc., since those
&& !current_function_calls_alloca
/* There are ways to leave the loop other than falling off the
end. */
- && !loop_has_multiple_exit_targets)
+ && !loop_info->has_multiple_exit_targets)
for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
insn = NEXT_INSN (insn))
for_each_rtx (&insn, insert_loop_mem, 0);
&& GET_CODE (PATTERN (insn)) != RETURN)
{
rtx label = JUMP_LABEL (insn);
- int label_luid = INSN_LUID (label);
-
- if (! condjump_p (insn)
- && ! condjump_in_parallel_p (insn))
+ int label_luid;
+
+ /* If it is not a jump we can easily understand or for
+ which we do not have jump target information in the JUMP_LABEL
+ field (consider ADDR_VEC and ADDR_DIFF_VEC insns), then clear
+ LOOP_NUMBER_CONT_DOMINATOR. */
+ if ((! condjump_p (insn)
+ && ! condjump_in_parallel_p (insn))
+ || label == NULL_RTX)
{
loop_number_cont_dominator[loop_number] = NULL_RTX;
return;
}
+
+ label_luid = INSN_LUID (label);
if (label_luid < INSN_LUID (loop_number_loop_cont[loop_number])
&& (label_luid
> INSN_LUID (loop_number_cont_dominator[loop_number])))
&& GET_CODE (PATTERN (insn)) != RETURN
&& current_loop >= 0)
{
- int this_loop;
+ int this_loop_num;
rtx label = JUMP_LABEL (insn);
if (! condjump_p (insn) && ! condjump_in_parallel_p (insn))
label = NULL_RTX;
- this_loop = current_loop;
+ this_loop_num = current_loop;
do
{
/* First see if we care about this loop. */
- if (loop_number_loop_cont[this_loop]
- && loop_number_cont_dominator[this_loop] != const0_rtx)
+ if (loop_number_loop_cont[this_loop_num]
+ && loop_number_cont_dominator[this_loop_num] != const0_rtx)
{
/* If the jump destination is not known, invalidate
loop_number_const_dominator. */
if (! label)
- loop_number_cont_dominator[this_loop] = const0_rtx;
+ loop_number_cont_dominator[this_loop_num] = const0_rtx;
else
/* Check if the destination is between loop start and
cont. */
if ((INSN_LUID (label)
- < INSN_LUID (loop_number_loop_cont[this_loop]))
+ < INSN_LUID (loop_number_loop_cont[this_loop_num]))
&& (INSN_LUID (label)
- > INSN_LUID (loop_number_loop_starts[this_loop]))
+ > INSN_LUID (loop_number_loop_starts[this_loop_num]))
/* And if there is no later destination already
recorded. */
- && (! loop_number_cont_dominator[this_loop]
+ && (! loop_number_cont_dominator[this_loop_num]
|| (INSN_LUID (label)
> INSN_LUID (loop_number_cont_dominator
- [this_loop]))))
- loop_number_cont_dominator[this_loop] = label;
+ [this_loop_num]))))
+ loop_number_cont_dominator[this_loop_num] = label;
}
- this_loop = loop_outer_loop[this_loop];
+ this_loop_num = loop_outer_loop[this_loop_num];
}
- while (this_loop >= 0);
+ while (this_loop_num >= 0);
}
/* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
{
rtx p;
rtx our_next = next_real_insn (insn);
+ rtx last_insn_to_move = NEXT_INSN (insn);
int dest_loop;
int outer_loop = -1;
&& INSN_UID (JUMP_LABEL (p)) != 0
&& condjump_p (p)
&& ! simplejump_p (p)
- && next_real_insn (JUMP_LABEL (p)) == our_next)
+ && next_real_insn (JUMP_LABEL (p)) == our_next
+ /* If it's not safe to move the sequence, then we
+ mustn't try. */
+ && insns_safe_to_move_p (p, NEXT_INSN (insn),
+ &last_insn_to_move))
{
rtx target
= JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
int target_loop_num = uid_loop_num[INSN_UID (target)];
- rtx loc;
+ rtx loc, loc2;
for (loc = target; loc; loc = PREV_INSN (loc))
if (GET_CODE (loc) == BARRIER
+ /* Don't move things inside a tablejump. */
+ && ((loc2 = next_nonnote_insn (loc)) == 0
+ || GET_CODE (loc2) != CODE_LABEL
+ || (loc2 = next_nonnote_insn (loc2)) == 0
+ || GET_CODE (loc2) != JUMP_INSN
+ || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
+ && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
&& uid_loop_num[INSN_UID (loc)] == target_loop_num)
break;
if (loc == 0)
for (loc = target; loc; loc = NEXT_INSN (loc))
if (GET_CODE (loc) == BARRIER
+ /* Don't move things inside a tablejump. */
+ && ((loc2 = next_nonnote_insn (loc)) == 0
+ || GET_CODE (loc2) != CODE_LABEL
+ || (loc2 = next_nonnote_insn (loc2)) == 0
+ || GET_CODE (loc2) != JUMP_INSN
+ || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
+ && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
&& uid_loop_num[INSN_UID (loc)] == target_loop_num)
break;
/* Include the BARRIER after INSN and copy the
block after LOC. */
- new_label = squeeze_notes (new_label, NEXT_INSN (insn));
- reorder_insns (new_label, NEXT_INSN (insn), loc);
+ new_label = squeeze_notes (new_label,
+ last_insn_to_move);
+ reorder_insns (new_label, last_insn_to_move, loc);
/* All those insns are now in TARGET_LOOP_NUM. */
- for (q = new_label; q != NEXT_INSN (NEXT_INSN (insn));
+ for (q = new_label;
+ q != NEXT_INSN (last_insn_to_move);
q = NEXT_INSN (q))
uid_loop_num[INSN_UID (q)] = target_loop_num;
mark_loop_jump (XEXP (x, 1), loop_num);
return;
+ case LO_SUM:
+ /* This may refer to a LABEL_REF or SYMBOL_REF. */
+ mark_loop_jump (XEXP (x, 1), loop_num);
+ return;
+
case SIGN_EXTEND:
case ZERO_EXTEND:
mark_loop_jump (XEXP (x, 0), loop_num);
return;
default:
- /* Treat anything else (such as a symbol_ref)
- as a branch out of this loop, but not into any loop. */
-
+ /* Strictly speaking this is not a jump into the loop, only a possible
+ jump out of the loop. However, we have no way to link the destination
+ of this jump onto the list of exit labels. To be safe we mark this
+ loop and any containing loops as invalid. */
if (loop_num != -1)
{
-#ifdef HAVE_decrement_and_branch_on_count
- LABEL_OUTSIDE_LOOP_P (x) = 1;
- LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
-#endif /* HAVE_decrement_and_branch_on_count */
-
- 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]++;
+ {
+ if (loop_dump_stream && ! loop_invalid[outer_loop])
+ fprintf (loop_dump_stream,
+ "\nLoop at %d ignored due to unknown exit jump.\n",
+ INSN_UID (loop_number_loop_starts[outer_loop]));
+ loop_invalid[outer_loop] = 1;
+ }
}
return;
}
loop_store_mems = gen_rtx_EXPR_LIST (VOIDmode, x, loop_store_mems);
}
+
+/* X is a value modified by an INSN that references a biv inside a loop
+ exit test (ie, X is somehow related to the value of the biv). If X
+ is a pseudo that is used more than once, then the biv is (effectively)
+ used more than once. */
+
+static void
+note_set_pseudo_multiple_uses (x, y)
+ rtx x;
+ rtx y ATTRIBUTE_UNUSED;
+{
+ if (x == 0)
+ return;
+
+ while (GET_CODE (x) == STRICT_LOW_PART
+ || GET_CODE (x) == SIGN_EXTRACT
+ || GET_CODE (x) == ZERO_EXTRACT
+ || GET_CODE (x) == SUBREG)
+ x = XEXP (x, 0);
+
+ if (GET_CODE (x) != REG || REGNO (x) < FIRST_PSEUDO_REGISTER)
+ return;
+
+ /* If we do not have usage information, or if we know the register
+ is used more than once, note that fact for check_dbra_loop. */
+ if (REGNO (x) >= max_reg_before_loop
+ || ! VARRAY_RTX (reg_single_usage, REGNO (x))
+ || VARRAY_RTX (reg_single_usage, REGNO (x)) == const0_rtx)
+ note_set_pseudo_multiple_uses_retval = 1;
+}
\f
/* Return nonzero if the rtx X is invariant over the current loop.
{
register int i;
register enum rtx_code code;
- register char *fmt;
+ register const char *fmt;
int conditional = 0;
rtx mem_list_entry;
&& ! current_function_has_nonlocal_goto)
return 1;
- if (loop_has_call
+ if (this_loop_info.has_call
&& REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
return 0;
varray_type usage;
{
enum rtx_code code = GET_CODE (x);
- char *fmt = GET_RTX_FORMAT (code);
+ const char *fmt = GET_RTX_FORMAT (code);
int i, j;
if (code == REG)
{
++count;
- /* If requested, record registers that have exactly one use. */
- if (single_usage)
- {
- find_single_use_in_loop (insn, PATTERN (insn), single_usage);
+ /* Record registers that have exactly one use. */
+ find_single_use_in_loop (insn, PATTERN (insn), single_usage);
- /* Include uses in REG_EQUAL notes. */
- if (REG_NOTES (insn))
- find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
- }
+ /* Include uses in REG_EQUAL notes. */
+ if (REG_NOTES (insn))
+ find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
SCAN_START is the first instruction in the loop, as the loop would
actually be executed. END is the NOTE_INSN_LOOP_END. LOOP_TOP is
the first instruction in the loop, as it is layed out in the
- instruction stream. LOOP_START is the NOTE_INSN_LOOP_BEG. */
+ instruction stream. LOOP_START is the NOTE_INSN_LOOP_BEG.
+ LOOP_CONT is the NOTE_INSN_LOOP_CONT. */
static void
strength_reduce (scan_start, end, loop_top, insn_count,
- loop_start, loop_end, unroll_p, bct_p)
+ loop_start, loop_end, loop_info, loop_cont, unroll_p, bct_p)
rtx scan_start;
rtx end;
rtx loop_top;
int insn_count;
rtx loop_start;
rtx loop_end;
+ struct loop_info *loop_info;
+ rtx loop_cont;
int unroll_p, bct_p ATTRIBUTE_UNUSED;
{
rtx p;
/* This is 1 if current insn may be executed more than once for every
loop iteration. */
int maybe_multiple = 0;
+ /* This is 1 if we have past a branch back to the top of the loop
+ (aka a loop latch). */
+ int past_loop_latch = 0;
/* Temporary list pointers for traversing loop_iv_list. */
struct iv_class *bl, **backbl;
/* Ratio of extra register life span we can justify
since in that case saving an insn makes more difference
and more registers are available. */
/* ??? could set this to last value of threshold in move_movables */
- int threshold = (loop_has_call ? 1 : 2) * (3 + n_non_fixed_regs);
+ int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
/* Map of pseudo-register replacements. */
rtx *reg_map;
int reg_map_size;
rtx end_insert_before;
int loop_depth = 0;
int n_extra_increment;
- struct loop_info loop_iteration_info;
- struct loop_info *loop_info = &loop_iteration_info;
+ int unrolled_insn_copies = 0;
/* If scan_start points to the loop exit test, we have to be wary of
subversive use of gotos inside expression statements. */
&& (! condjump_p (insn)
|| (JUMP_LABEL (insn) != 0
&& JUMP_LABEL (insn) != scan_start
- && (INSN_UID (JUMP_LABEL (insn)) >= max_uid_for_loop
- || (INSN_UID (p) < max_uid_for_loop
- ? (INSN_LUID (JUMP_LABEL (insn))
- <= INSN_LUID (p))
- : (INSN_UID (insn) >= max_uid_for_loop
- || (INSN_LUID (JUMP_LABEL (insn))
- < INSN_LUID (insn))))))))
+ && ! loop_insn_first_p (p, JUMP_LABEL (insn)))))
{
maybe_multiple = 1;
break;
{
/* 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)
+ even though the exit code has been duplicated.
+
+ Insns are also again known to be executed each iteration at
+ the LOOP_CONT note. */
+ if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
+ || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
+ && loop_depth == 0)
not_every_iteration = 0;
else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
loop_depth++;
loop_depth--;
}
+ /* Note if we pass a loop latch. If we do, then we can not clear
+ NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
+ a loop since a jump before the last CODE_LABEL may have started
+ a new loop iteration.
+
+ Note that LOOP_TOP is only set for rotated loops and we need
+ this check for all loops, so compare against the CODE_LABEL
+ which immediately follows LOOP_START. */
+ if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == NEXT_INSN (loop_start))
+ past_loop_latch = 1;
+
/* Unlike in the code motion pass where MAYBE_NEVER indicates that
an insn may never be executed, NOT_EVERY_ITERATION indicates whether
or not an insn is known to be executed each iteration of the
loop, whether or not any iterations are known to occur.
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. */
-
- if (not_every_iteration && GET_CODE (p) == CODE_LABEL
- && no_labels_between_p (p, loop_end))
+ between here and the test insn of the loop, and we have not passed
+ a jump to the top of the loop, then we know these insns will be
+ executed each iteration. */
+
+ if (not_every_iteration
+ && ! past_loop_latch
+ && GET_CODE (p) == CODE_LABEL
+ && no_labels_between_p (p, loop_end)
+ && loop_insn_first_p (p, loop_cont))
not_every_iteration = 0;
}
unroll_loop (loop_end, insn_count, loop_start, end_insert_before,
loop_info, 0);
- return;
+ goto egress;
}
/* Find initial value for each biv by searching backwards from loop_start,
else
{
struct iv_class *bl2 = 0;
- rtx increment;
+ rtx increment = NULL_RTX;
/* Biv initial value is not a simple move. If it is the sum of
another biv and a constant, check if both bivs are incremented
/* The register from BL2 must be set before the register from
BL is set, or we must be able to move the latter set after
the former set. Currently there can't be any labels
- in-between when biv_toal_increment returns nonzero both times
+ in-between when biv_total_increment returns nonzero both times
but we test it here in case some day some real cfg analysis
gets used to set always_computable. */
- && ((insn_first_p (bl2->biv->insn, bl->biv->insn)
- && no_labels_between_p (bl2->biv->insn, bl->biv->insn))
- || (! reg_used_between_p (bl->biv->src_reg, bl->biv->insn,
- bl2->biv->insn)
- && no_jumps_between_p (bl->biv->insn, bl2->biv->insn)))
+ && (loop_insn_first_p (bl2->biv->insn, bl->biv->insn)
+ ? no_labels_between_p (bl2->biv->insn, bl->biv->insn)
+ : (! reg_used_between_p (bl->biv->src_reg, bl->biv->insn,
+ bl2->biv->insn)
+ && no_jumps_between_p (bl->biv->insn, bl2->biv->insn)))
&& validate_change (bl->biv->insn,
&SET_SRC (single_set (bl->biv->insn)),
copy_rtx (src), 0))
fprintf (loop_dump_stream, "is giv of biv %d\n", bl2->regno);
/* Let this giv be discovered by the generic code. */
REG_IV_TYPE (bl->regno) = UNKNOWN_INDUCT;
+ reg_biv_class[bl->regno] = NULL_PTR;
/* We can get better optimization if we can move the giv setting
before the first giv use. */
if (dominator
+ && ! loop_insn_first_p (dominator, scan_start)
&& ! reg_set_between_p (bl2->biv->src_reg, loop_start,
dominator)
&& ! reg_used_between_p (giv, loop_start, dominator)
&& ! reg_used_between_p (giv, bl->init_insn, loop_start))
delete_insn (bl->init_insn);
}
- else if (! insn_first_p (bl2->biv->insn, bl->biv->insn))
+ else if (! loop_insn_first_p (bl2->biv->insn, bl->biv->insn))
{
rtx p = PREV_INSN (giv_insn);
while (INSN_UID (p) >= max_uid_for_loop)
}
/* Remove this biv from the chain. */
if (bl->next)
- *bl = *bl->next;
+ {
+ /* We move the following giv from *bl->next into *bl.
+ We have to update reg_biv_class for that moved biv
+ to point to its new address. */
+ *bl = *bl->next;
+ reg_biv_class[bl->regno] = bl;
+ }
else
{
*backbl = 0;
first_increment_giv = max_reg_num ();
for (n_extra_increment = 0, bl = loop_iv_list; bl; bl = bl->next)
n_extra_increment += bl->biv_count - 1;
- /* XXX Temporary. */
- if (0 && n_extra_increment)
+
+ /* If the loop contains volatile memory references do not allow any
+ replacements to take place, since this could loose the volatile markers. */
+ if (n_extra_increment && ! loop_info->has_volatile)
{
int nregs = first_increment_giv + n_extra_increment;
for (bl = loop_iv_list; bl; bl = bl->next)
{
struct induction **vp, *v, *next;
-
+ int biv_dead_after_loop = 0;
+
/* The biv increments lists are in reverse order. Fix this first. */
for (v = bl->biv, bl->biv = 0; v; v = next)
{
v->next_iv = bl->biv;
bl->biv = v;
}
-
+
+ /* We must guard against the case that an early exit between v->insn
+ and next->insn leaves the biv live after the loop, since that
+ would mean that we'd be missing an increment for the final
+ value. The following test to set biv_dead_after_loop is like
+ the first part of the test to set bl->eliminable.
+ We don't check here if we can calculate the final value, since
+ this can't succeed if we already know that there is a jump
+ between v->insn and next->insn, yet next->always_executed is
+ set and next->maybe_multiple is cleared. Such a combination
+ implies that the jump destination is outside the loop.
+ If we want to make this check more sophisticated, we should
+ check each branch between v->insn and next->insn individually
+ to see if the biv is dead at its destination. */
+
+ 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))
+#ifdef HAVE_decrement_and_branch_until_zero
+ && ! bl->nonneg
+#endif
+ && ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
+ biv_dead_after_loop = 1;
+
for (vp = &bl->biv, next = *vp; v = next, next = v->next_iv;)
{
HOST_WIDE_INT offset;
- rtx set, add_val, old_reg, dest_reg, last_use_insn;
+ rtx set, add_val, old_reg, dest_reg, last_use_insn, note;
int old_regno, new_regno;
-
+
if (! v->always_executed
|| v->maybe_multiple
|| GET_CODE (v->add_val) != CONST_INT
|| ! next->always_executed
|| next->maybe_multiple
- || ! CONSTANT_P (next->add_val))
+ || ! CONSTANT_P (next->add_val)
+ || v->mult_val != const1_rtx
+ || next->mult_val != const1_rtx
+ || ! (biv_dead_after_loop
+ || no_jumps_between_p (v->insn, next->insn)))
{
vp = &v->next_iv;
continue;
VARRAY_GROW (set_in_loop, nregs);
VARRAY_GROW (n_times_set, nregs);
VARRAY_GROW (may_not_optimize, nregs);
+ VARRAY_GROW (reg_single_usage, nregs);
}
- validate_change (v->insn, &SET_DEST (set), dest_reg, 1);
- validate_change (next->insn, next->location, add_val, 1);
- if (! apply_change_group ())
+ if (! validate_change (next->insn, next->location, add_val, 0))
{
vp = &v->next_iv;
continue;
}
+
+ /* Here we can try to eliminate the increment by combining
+ it into the uses. */
+
+ /* Set last_use_insn so that we can check against it. */
+
+ for (last_use_insn = v->insn, p = NEXT_INSN (v->insn);
+ p != next->insn;
+ p = next_insn_in_loop (p, scan_start, end, loop_top))
+ {
+ if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
+ continue;
+ if (reg_mentioned_p (old_reg, PATTERN (p)))
+ {
+ last_use_insn = p;
+ }
+ }
+
+ /* If we can't get the LUIDs for the insns, we can't
+ calculate the lifetime. This is likely from unrolling
+ of an inner loop, so there is little point in making this
+ a DEST_REG giv anyways. */
+ if (INSN_UID (v->insn) >= max_uid_for_loop
+ || INSN_UID (last_use_insn) >= max_uid_for_loop
+ || ! validate_change (v->insn, &SET_DEST (set), dest_reg, 0))
+ {
+ /* Change the increment at NEXT back to what it was. */
+ if (! validate_change (next->insn, next->location,
+ next->add_val, 0))
+ abort ();
+ vp = &v->next_iv;
+ continue;
+ }
next->add_val = add_val;
v->dest_reg = dest_reg;
v->giv_type = DEST_REG;
REG_IV_TYPE (new_regno) = GENERAL_INDUCT;
REG_IV_INFO (new_regno) = v;
-
+
+ /* If next_insn has a REG_EQUAL note that mentiones OLD_REG,
+ it must be replaced. */
+ note = find_reg_note (next->insn, REG_EQUAL, NULL_RTX);
+ if (note && reg_mentioned_p (old_reg, XEXP (note, 0)))
+ XEXP (note, 0) = copy_rtx (SET_SRC (single_set (next->insn)));
+
/* Remove the increment from the list of biv increments,
and record it as a giv. */
*vp = next;
This will not prevent the biv from being eliminated. */
if (v->lifetime == 0)
v->ignore = 1;
+
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Increment %d of biv %d converted to giv %d.\n\n",
+ INSN_UID (v->insn), old_regno, new_regno);
}
}
}
not_every_iteration = 0;
loop_depth = 0;
+ maybe_multiple = 0;
p = scan_start;
while (1)
{
p = last_consec_insn;
record_giv (v, p, src_reg, dest_reg, mult_val, add_val, benefit,
- DEST_REG, not_every_iteration, NULL_PTR, loop_start,
- loop_end);
+ DEST_REG, not_every_iteration, maybe_multiple,
+ NULL_PTR, loop_start, loop_end);
}
}
/* This resulted in worse code on a VAX 8600. I wonder if it
still does. */
if (GET_CODE (p) == INSN)
- find_mem_givs (PATTERN (p), p, not_every_iteration, loop_start,
- loop_end);
+ find_mem_givs (PATTERN (p), p, not_every_iteration, maybe_multiple,
+ loop_start, loop_end);
#endif
/* Update the status of whether giv can derive other givs. This can
|| GET_CODE (p) == CODE_LABEL)
update_giv_derive (p);
+ /* 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, is a forward jump, or is a jump
+ to the loop start. */
+
+ if (GET_CODE (p) == CODE_LABEL)
+ {
+ rtx insn = p;
+
+ maybe_multiple = 0;
+
+ while (1)
+ {
+ insn = NEXT_INSN (insn);
+ if (insn == scan_start)
+ break;
+ if (insn == end)
+ {
+ if (loop_top != 0)
+ insn = loop_top;
+ else
+ break;
+ if (insn == scan_start)
+ break;
+ }
+
+ if (GET_CODE (insn) == JUMP_INSN
+ && 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;
+ }
+ }
+ }
+
/* 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
{
/* 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)
+ even though the exit code has been duplicated.
+
+ Insns are also again known to be executed each iteration at
+ the LOOP_CONT note. */
+ if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
+ || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
+ && loop_depth == 0)
not_every_iteration = 0;
else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
loop_depth++;
will be executed each iteration. */
if (not_every_iteration && GET_CODE (p) == CODE_LABEL
- && no_labels_between_p (p, loop_end))
+ && no_labels_between_p (p, loop_end)
+ && loop_insn_first_p (p, loop_cont))
not_every_iteration = 0;
}
int benefit;
int all_reduced;
rtx final_value = 0;
- unsigned nregs;
+ unsigned int nregs;
/* Test whether it will be possible to eliminate this biv
provided all givs are reduced. This is possible if either
}
}
-#if 0
- /* XXX Temporary. */
+ /* Check for givs whose first use is their definition and whose
+ last use is the definition of another giv. If so, it is likely
+ dead and should not be used to derive another giv nor to
+ eliminate a biv. */
+ for (v = bl->giv; v; v = v->next_iv)
+ {
+ if (v->ignore
+ || (v->same && v->same->ignore))
+ continue;
+
+ if (v->last_use)
+ {
+ struct induction *v1;
+
+ for (v1 = bl->giv; v1; v1 = v1->next_iv)
+ if (v->last_use == v1->insn)
+ v->maybe_dead = 1;
+ }
+ else if (v->giv_type == DEST_REG
+ && 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))
+ v->maybe_dead = 1;
+ }
+ }
+
/* Now that we know which givs will be reduced, try to rearrange the
combinations to reduce register pressure.
recombine_givs calls find_life_end, which needs reg_iv_type and
VARRAY_GROW (reg_iv_info, nregs);
}
recombine_givs (bl, loop_start, loop_end, unroll_p);
-#endif
/* Reduce each giv that we decided to reduce. */
{
int auto_inc_opt = 0;
- v->new_reg = gen_reg_rtx (v->mode);
+ /* If the code for derived givs immediately below has already
+ allocated a new_reg, we must keep it. */
+ if (! v->new_reg)
+ v->new_reg = gen_reg_rtx (v->mode);
if (v->derived_from)
{
+ struct induction *d = v->derived_from;
+
+ /* In case d->dest_reg is not replaceable, we have
+ to replace it in v->insn now. */
+ if (! d->new_reg)
+ d->new_reg = gen_reg_rtx (d->mode);
+ PATTERN (v->insn)
+ = replace_rtx (PATTERN (v->insn), d->dest_reg, d->new_reg);
PATTERN (v->insn)
= replace_rtx (PATTERN (v->insn), v->dest_reg, v->new_reg);
- if (bl->biv_count != 1)
+ /* For each place where the biv is incremented, add an
+ insn to set the new, reduced reg for the giv.
+ We used to do this only for biv_count != 1, but
+ this fails when there is a giv after a single biv
+ increment, e.g. when the last giv was expressed as
+ pre-decrement. */
+ for (tv = bl->biv; tv; tv = tv->next_iv)
{
- /* For each place where the biv is incremented, add an
- insn to set the new, reduced reg for the giv. */
- for (tv = bl->biv; tv; tv = tv->next_iv)
- {
- /* We always emit reduced giv increments before the
- biv increment when bl->biv_count != 1. So by
- emitting the add insns for derived givs after the
- biv increment, they pick up the updated value of
- the reduced giv. */
- emit_insn_after (copy_rtx (PATTERN (v->insn)),
- tv->insn);
-
- }
+ /* We always emit reduced giv increments before the
+ biv increment when bl->biv_count != 1. So by
+ emitting the add insns for derived givs after the
+ biv increment, they pick up the updated value of
+ the reduced giv.
+ If the reduced giv is processed with
+ auto_inc_opt == 1, then it is incremented earlier
+ than the biv, hence we'll still pick up the right
+ value.
+ If it's processed with auto_inc_opt == -1,
+ that implies that the biv increment is before the
+ first reduced giv's use. The derived giv's lifetime
+ is after the reduced giv's lifetime, hence in this
+ case, the biv increment doesn't matter. */
+ emit_insn_after (copy_rtx (PATTERN (v->insn)), tv->insn);
}
continue;
}
For each giv register that can be reduced now: if replaceable,
substitute reduced reg wherever the old giv occurs;
- else add new move insn "giv_reg = reduced_reg".
+ else add new move insn "giv_reg = reduced_reg". */
- Also check for givs whose first use is their definition and whose
- last use is the definition of another giv. If so, it is likely
- dead and should not be used to eliminate a biv. */
for (v = bl->giv; v; v = v->next_iv)
{
if (v->same && v->same->ignore)
if (v->ignore)
continue;
- if (v->last_use)
- {
- struct induction *v1;
-
- for (v1 = bl->giv; v1; v1 = v1->next_iv)
- if (v->last_use == v1->insn)
- v->maybe_dead = 1;
- }
- else if (v->giv_type == DEST_REG
- && 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))
- v->maybe_dead = 1;
- }
-
/* Update expression if this was combined, in case other giv was
replaced. */
if (v->same)
INSN_CODE (p) = -1;
}
+ if (loop_info->n_iterations > 0)
+ {
+ /* When we completely unroll a loop we will likely not need the increment
+ of the loop BIV and we will not need the conditional branch at the
+ end of the loop. */
+ unrolled_insn_copies = insn_count - 2;
+
+#ifdef HAVE_cc0
+ /* When we completely unroll a loop on a HAVE_cc0 machine we will not
+ need the comparison before the conditional branch at the end of the
+ loop. */
+ unrolled_insn_copies -= 1;
+#endif
+
+ /* We'll need one copy for each loop iteration. */
+ unrolled_insn_copies *= loop_info->n_iterations;
+
+ /* A little slop to account for the ability to remove initialization
+ code, better CSE, and other secondary benefits of completely
+ unrolling some loops. */
+ unrolled_insn_copies -= 1;
+
+ /* Clamp the value. */
+ if (unrolled_insn_copies < 0)
+ unrolled_insn_copies = 0;
+ }
+
/* Unroll loops from within strength reduction so that we can use the
induction variable information that strength_reduce has already
- collected. */
-
- if (unroll_p)
+ collected. Always unroll loops that would be as small or smaller
+ unrolled than when rolled. */
+ if (unroll_p
+ || (loop_info->n_iterations > 0
+ && unrolled_insn_copies <= insn_count))
unroll_loop (loop_end, insn_count, loop_start, end_insert_before,
loop_info, 1);
if (loop_dump_stream)
fprintf (loop_dump_stream, "\n");
+
+egress:
VARRAY_FREE (reg_iv_type);
VARRAY_FREE (reg_iv_info);
}
/* Scan X for memory refs and check each memory address
as a possible giv. INSN is the insn whose pattern X comes from.
NOT_EVERY_ITERATION is 1 if the insn might not be executed during
- every loop iteration. */
+ every loop iteration. MAYBE_MULTIPLE is 1 if the insn might be executed
+ more thanonce in each loop iteration. */
static void
-find_mem_givs (x, insn, not_every_iteration, loop_start, loop_end)
+find_mem_givs (x, insn, not_every_iteration, maybe_multiple, loop_start,
+ loop_end)
rtx x;
rtx insn;
- int not_every_iteration;
+ int not_every_iteration, maybe_multiple;
rtx loop_start, loop_end;
{
register int i, j;
register enum rtx_code code;
- register char *fmt;
+ register const char *fmt;
if (x == 0)
return;
record_giv (v, insn, src_reg, addr_placeholder, mult_val,
add_val, benefit, DEST_ADDR, not_every_iteration,
- &XEXP (x, 0), loop_start, loop_end);
+ maybe_multiple, &XEXP (x, 0), loop_start, loop_end);
v->mem_mode = GET_MODE (x);
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
if (fmt[i] == 'e')
- find_mem_givs (XEXP (x, i), insn, not_every_iteration, loop_start,
- loop_end);
+ find_mem_givs (XEXP (x, i), insn, not_every_iteration, maybe_multiple,
+ loop_start, loop_end);
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
find_mem_givs (XVECEXP (x, i, j), insn, not_every_iteration,
- loop_start, loop_end);
+ maybe_multiple, loop_start, loop_end);
}
\f
/* Fill in the data about one biv update.
static void
record_giv (v, insn, src_reg, dest_reg, mult_val, add_val, benefit,
- type, not_every_iteration, location, loop_start, loop_end)
+ type, not_every_iteration, maybe_multiple, location, loop_start,
+ loop_end)
struct induction *v;
rtx insn;
rtx src_reg;
rtx mult_val, add_val;
int benefit;
enum g_types type;
- int not_every_iteration;
+ int not_every_iteration, maybe_multiple;
rtx *location;
rtx loop_start, loop_end;
{
v->location = location;
v->cant_derive = 0;
v->combined_with = 0;
- v->maybe_multiple = 0;
+ v->maybe_multiple = maybe_multiple;
v->maybe_dead = 0;
v->derive_adjustment = 0;
v->same = 0;
if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
&& LABEL_NAME (JUMP_LABEL (p))
- && ((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))))
+ && ((loop_insn_first_p (JUMP_LABEL (p), v->insn)
+ && loop_insn_first_p (loop_start, JUMP_LABEL (p)))
+ || (loop_insn_first_p (last_giv_use, JUMP_LABEL (p))
+ && loop_insn_first_p (JUMP_LABEL (p), loop_end))))
{
v->replaceable = 0;
v->not_replaceable = 1;
&dummy);
if (tem && giv->derive_adjustment)
- tem = simplify_giv_expr (gen_rtx_PLUS (giv->mode, tem,
- giv->derive_adjustment),
- &dummy);
+ tem = simplify_giv_expr
+ (gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
+ &dummy);
+
if (tem)
giv->derive_adjustment = tem;
else
rtx insn, set = 0;
code = GET_CODE (x);
+ *location = NULL;
switch (code)
{
case PLUS:
|| (GET_CODE (SET_DEST (set)) == SUBREG
&& (GET_MODE_SIZE (GET_MODE (SET_DEST (set)))
<= UNITS_PER_WORD)
+ && (GET_MODE_CLASS (GET_MODE (SET_DEST (set)))
+ == MODE_INT)
&& SUBREG_REG (SET_DEST (set)) == x))
&& basic_induction_var (SET_SRC (set),
(GET_MODE (SET_SRC (set)) == VOIDmode
/* convert_modes aborts if we try to convert to or from CCmode, so just
exclude that case. It is very unlikely that a condition code value
would be a useful iterator anyways. */
- if (loops_enclosed == 1
+ if (this_loop_info.loops_enclosed == 1
&& GET_MODE_CLASS (mode) != MODE_CC
&& GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
{
*BENEFIT will be incremented by the benefit of any sub-giv encountered. */
-static rtx sge_plus PROTO ((enum machine_mode, rtx, rtx));
-static rtx sge_plus_constant PROTO ((rtx, rtx));
+static rtx sge_plus PARAMS ((enum machine_mode, rtx, rtx));
+static rtx sge_plus_constant PARAMS ((rtx, rtx));
+static int cmp_combine_givs_stats PARAMS ((const PTR, const PTR));
+static int cmp_recombine_givs_stats PARAMS ((const PTR, const PTR));
static rtx
simplify_giv_expr (x, benefit)
case PLUS:
/* (a + invar_1) + invar_2. Associate. */
- return simplify_giv_expr (
- gen_rtx_PLUS (mode, XEXP (arg0, 0),
- gen_rtx_PLUS (mode, XEXP (arg0, 1), arg1)),
- benefit);
+ return
+ simplify_giv_expr (gen_rtx_PLUS (mode,
+ XEXP (arg0, 0),
+ gen_rtx_PLUS (mode,
+ XEXP (arg0, 1),
+ arg1)),
+ benefit);
default:
abort ();
tem = arg0, arg0 = arg1, arg1 = tem;
if (GET_CODE (arg1) == PLUS)
- return simplify_giv_expr (gen_rtx_PLUS (mode,
- gen_rtx_PLUS (mode, arg0,
- XEXP (arg1, 0)),
- XEXP (arg1, 1)),
- benefit);
+ return
+ simplify_giv_expr (gen_rtx_PLUS (mode,
+ gen_rtx_PLUS (mode, arg0,
+ XEXP (arg1, 0)),
+ XEXP (arg1, 1)),
+ benefit);
/* Now must have MULT + MULT. Distribute if same biv, else not giv. */
if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
/* Handle "a - b" as "a + b * (-1)". */
return simplify_giv_expr (gen_rtx_PLUS (mode,
XEXP (x, 0),
- gen_rtx_MULT (mode, XEXP (x, 1),
+ gen_rtx_MULT (mode,
+ XEXP (x, 1),
constm1_rtx)),
benefit);
case MULT:
/* (a * invar_1) * invar_2. Associate. */
- return simplify_giv_expr (gen_rtx_MULT (mode, XEXP (arg0, 0),
+ return simplify_giv_expr (gen_rtx_MULT (mode,
+ XEXP (arg0, 0),
gen_rtx_MULT (mode,
XEXP (arg0, 1),
arg1)),
if (GET_CODE (XEXP (x, 1)) != CONST_INT)
return 0;
- return simplify_giv_expr (gen_rtx_MULT (mode,
- XEXP (x, 0),
- GEN_INT ((HOST_WIDE_INT) 1
- << INTVAL (XEXP (x, 1)))),
- benefit);
+ return
+ simplify_giv_expr (gen_rtx_MULT (mode,
+ XEXP (x, 0),
+ GEN_INT ((HOST_WIDE_INT) 1
+ << INTVAL (XEXP (x, 1)))),
+ benefit);
case NEG:
/* "-a" is "a * (-1)" */
if (v->cant_derive)
return 0;
- tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode, v->src_reg,
- v->mult_val),
- v->add_val);
+ tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode,
+ v->src_reg, v->mult_val),
+ v->add_val);
+
if (v->derive_adjustment)
tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
return simplify_giv_expr (tem, benefit);
add = express_from_1 (g1->add_val, g2->add_val, mult);
if (add == NULL_RTX)
+ {
+ /* Failed. If we've got a multiplication factor between G1 and G2,
+ scale G1's addend and try again. */
+ if (INTVAL (mult) > 1)
+ {
+ rtx g1_add_val = g1->add_val;
+ if (GET_CODE (g1_add_val) == MULT
+ && GET_CODE (XEXP (g1_add_val, 1)) == CONST_INT)
+ {
+ HOST_WIDE_INT m;
+ m = INTVAL (mult) * INTVAL (XEXP (g1_add_val, 1));
+ g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val),
+ XEXP (g1_add_val, 0), GEN_INT (m));
+ }
+ else
+ {
+ g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val), g1_add_val,
+ mult);
+ }
+
+ add = express_from_1 (g1_add_val, g2->add_val, const1_rtx);
+ }
+ }
+ if (add == NULL_RTX)
return NULL_RTX;
/* Form simplified final result. */
};
static int
-cmp_combine_givs_stats (x, y)
- struct combine_givs_stats *x, *y;
+cmp_combine_givs_stats (xp, yp)
+ const PTR xp;
+ const PTR yp;
{
+ const struct combine_givs_stats * const x =
+ (const struct combine_givs_stats *) xp;
+ const struct combine_givs_stats * const y =
+ (const struct combine_givs_stats *) yp;
int d;
d = y->total_benefit - x->total_benefit;
/* Stabilize the sort. */
return d;
}
-/* If one of these givs is a DEST_REG that was used by the other giv,
- this is actually a single use. Return 0 if this is not
- the case, -1 if g1 is the DEST_REG involved, and 1 if it was g2. */
-
-static int
-combine_givs_used_by_other (g1, g2)
- struct induction *g1, *g2;
-{
- if (g1->giv_type == DEST_REG
- && reg_mentioned_p (g1->dest_reg, PATTERN (g2->insn)))
- return -1;
-
- if (g2->giv_type == DEST_REG
- && reg_mentioned_p (g2->dest_reg, PATTERN (g1->insn)))
- return 1;
-
- return 0;
-}
-
-static int
-combine_givs_benefit_from (g1, g2)
- struct induction *g1, *g2;
-{
- int tmp = combine_givs_used_by_other (g1, g2);
- if (tmp < 0)
- return 0;
- else if (tmp > 0)
- return g2->benefit - g1->benefit;
- else
- return g2->benefit;
-}
-
/* 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;
{
+ /* Additional benefit to add for being combined multiple times. */
+ const int extra_benefit = 3;
+
struct induction *g1, *g2, **giv_array;
int i, j, k, giv_count;
struct combine_givs_stats *stats;
for (i = 0; i < giv_count; i++)
{
int this_benefit;
+ rtx single_use;
g1 = giv_array[i];
+ stats[i].giv_number = i;
+
+ /* If a DEST_REG GIV is used only once, do not allow it to combine
+ with anything, for in doing so we will gain nothing that cannot
+ be had by simply letting the GIV with which we would have combined
+ to be reduced on its own. The losage shows up in particular with
+ DEST_ADDR targets on hosts with reg+reg addressing, though it can
+ be seen elsewhere as well. */
+ if (g1->giv_type == DEST_REG
+ && (single_use = VARRAY_RTX (reg_single_usage, REGNO (g1->dest_reg)))
+ && single_use != const0_rtx)
+ continue;
this_benefit = g1->benefit;
/* Add an additional weight for zero addends. */
if (g1->no_const_addval)
this_benefit += 1;
+
for (j = 0; j < giv_count; j++)
{
rtx this_combine;
&& (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
{
can_combine[i*giv_count + j] = this_combine;
- this_benefit += combine_givs_benefit_from (g1, g2);
- /* Add an additional weight for being reused more times. */
- this_benefit += 3;
+ this_benefit += g2->benefit + extra_benefit;
}
}
- stats[i].giv_number = i;
stats[i].total_benefit = this_benefit;
}
g1->combined_with++;
g1->lifetime += g2->lifetime;
- g1_add_benefit += combine_givs_benefit_from (g1, g2);
+ g1_add_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
{
int m = stats[l].giv_number;
if (can_combine[m*giv_count + j])
- {
- /* Remove additional weight for being reused. */
- stats[l].total_benefit -= 3 +
- combine_givs_benefit_from (giv_array[m], g2);
- }
+ stats[l].total_benefit -= g2->benefit + extra_benefit;
}
if (loop_dump_stream)
for (j = 0; j < giv_count; ++j)
{
int m = stats[j].giv_number;
- if (can_combine[m*giv_count + j])
- {
- /* Remove additional weight for being reused. */
- stats[j].total_benefit -= 3 +
- combine_givs_benefit_from (giv_array[m], g1);
- }
+ if (can_combine[m*giv_count + i])
+ stats[j].total_benefit -= g1->benefit + extra_benefit;
}
g1->benefit += g1_add_benefit;
when scanning the array starting at the end, thus the arguments are
used in reverse. */
static int
-cmp_recombine_givs_stats (x, y)
- struct recombine_givs_stats *x, *y;
+cmp_recombine_givs_stats (xp, yp)
+ const PTR xp;
+ const PTR yp;
{
+ const struct recombine_givs_stats * const x =
+ (const struct recombine_givs_stats *) xp;
+ const struct recombine_givs_stats * const y =
+ (const struct recombine_givs_stats *) yp;
int d;
d = y->start_luid - x->start_luid;
/* Stabilize the sort. */
struct recombine_givs_stats *stats;
{
enum rtx_code code;
- char *fmt;
+ const char *fmt;
int i, j;
int retval;
for (p = v->insn; INSN_UID (p) >= max_uid_for_loop; )
p = PREV_INSN (p);
stats[i].start_luid = INSN_LUID (p);
- v->ix = i;
i++;
}
qsort (stats, giv_count, sizeof(*stats), cmp_recombine_givs_stats);
- /* Do the actual most-recently-used recombination. */
+ /* Set up the ix field for each giv in stats to name
+ the corresponding index into stats, and
+ do the actual most-recently-used recombination. */
for (last_giv = 0, i = giv_count - 1; i >= 0; i--)
{
v = giv_array[stats[i].giv_number];
+ v->ix = i;
if (v->same)
{
struct induction *old_same = v->same;
ends_need_computing = 0;
/* For each DEST_REG giv, compute lifetime starts, and try to compute
lifetime ends from regscan info. */
- for (i = 0, v = bl->giv; v; v = v->next_iv)
+ for (i = giv_count - 1; i >= 0; i--)
{
+ v = giv_array[stats[i].giv_number];
if (v->ignore)
continue;
if (v->giv_type == DEST_ADDR)
}
}
}
- i++;
}
/* If the regscan information was unconclusive for one or more DEST_REG
/* Set start_luid back to the last insn that sets the giv. This allows
more combinations. */
- for (i = 0, v = bl->giv; v; v = v->next_iv)
+ for (i = giv_count - 1; i >= 0; i--)
{
+ v = giv_array[stats[i].giv_number];
if (v->ignore)
continue;
if (INSN_UID (v->insn) < max_uid_for_loop)
stats[i].start_luid = INSN_LUID (v->insn);
- i++;
}
/* Now adjust lifetime ends by taking combined givs into account. */
- for (i = 0, v = bl->giv; v; v = v->next_iv)
+ for (i = giv_count - 1; i >= 0; i--)
{
unsigned luid;
int j;
+ v = giv_array[stats[i].giv_number];
if (v->ignore)
continue;
if (v->same && ! v->same->ignore)
> (unsigned) stats[j].end_luid - stats[j].start_luid)
stats[j].end_luid = luid;
}
- i++;
}
qsort (stats, giv_count, sizeof(*stats), cmp_recombine_givs_stats);
&& GET_CODE (XEXP (sum, 1)) == CONST_INT)
|| ! unroll_p)
&& validate_change (v->insn, &PATTERN (v->insn),
- gen_rtx_SET (GET_MODE (v->dest_reg),
- v->dest_reg, sum), 0))
+ gen_rtx_SET (VOIDmode, v->dest_reg, sum), 0))
{
v->derived_from = last_giv;
- v->new_reg = v->dest_reg;
life_end = stats[i].end_luid;
if (loop_dump_stream)
fprintf (loop_dump_stream,
"giv at %d derived from %d as ",
INSN_UID (v->insn), INSN_UID (last_giv->insn));
- print_rtl (loop_dump_stream, v->new_reg);
+ print_rtl (loop_dump_stream, sum);
putc ('\n', loop_dump_stream);
}
}
}
}
}
- else if (INTVAL (bl->biv->add_val) > 0)
+ else if (GET_CODE (bl->biv->add_val) == CONST_INT
+ && INTVAL (bl->biv->add_val) > 0)
{
/* Try to change inc to dec, so can apply above optimization. */
/* Can do this if:
&& REGNO (SET_DEST (set)) == bl->regno)
/* An insn that sets the biv is okay. */
;
- else if (p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
- || p == prev_nonnote_insn (loop_end))
- /* Don't bother about the end test. */
- ;
+ else if ((p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
+ || p == prev_nonnote_insn (loop_end))
+ && reg_mentioned_p (bivreg, PATTERN (p)))
+ {
+ /* If either of these insns uses the biv and sets a pseudo
+ that has more than one usage, then the biv has uses
+ other than counting since it's used to derive a value
+ that is used more than one time. */
+ note_set_pseudo_multiple_uses_retval = 0;
+ note_stores (PATTERN (p), note_set_pseudo_multiple_uses);
+ if (note_set_pseudo_multiple_uses_retval)
+ {
+ no_use_except_counting = 0;
+ break;
+ }
+ }
else if (reg_mentioned_p (bivreg, PATTERN (p)))
{
no_use_except_counting = 0;
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)));
+ {
+ struct induction *v;
+
+ reversible_mem_store
+ = (! unknown_address_altered
+ && ! invariant_p (XEXP (XEXP (loop_store_mems, 0), 0)));
+
+ /* If the store depends on a register that is set after the
+ store, it depends on the initial value, and is thus not
+ reversible. */
+ for (v = bl->giv; reversible_mem_store && v; v = v->next_iv)
+ {
+ if (v->giv_type == DEST_REG
+ && reg_mentioned_p (v->dest_reg,
+ XEXP (loop_store_mems, 0))
+ && loop_insn_first_p (first_loop_store_insn, v->insn))
+ reversible_mem_store = 0;
+ }
+ }
}
else
return 0;
about all these things. */
if ((num_nonfixed_reads <= 1
- && !loop_has_call
- && !loop_has_volatile
+ && ! loop_info->has_call
+ && ! loop_info->has_volatile
&& reversible_mem_store
&& (bl->giv_count + bl->biv_count + num_mem_sets
+ num_movables + compare_and_branch == insn_count)
|| (GET_CODE (comparison) == LE
&& no_use_except_counting)))
{
- HOST_WIDE_INT add_val, add_adjust, comparison_val;
+ HOST_WIDE_INT add_val, add_adjust, comparison_val = 0;
rtx initial_value, comparison_value;
int nonneg = 0;
enum rtx_code cmp_code;
/* First check if we can do a vanilla loop reversal. */
if (initial_value == const0_rtx
- /* If we have a decrement_and_branch_on_count, prefer
- the NE test, since this will allow that instruction to
- be generated. Note that we must use a vanilla loop
- reversal if the biv is used to calculate a giv or has
- a non-counting use. */
-#if ! defined (HAVE_decrement_and_branch_until_zero) && defined (HAVE_decrement_and_branch_on_count)
+ /* If we have a decrement_and_branch_on_count,
+ prefer the NE test, since this will allow that
+ instruction to be generated. Note that we must
+ use a vanilla loop reversal if the biv is used to
+ calculate a giv or has a non-counting use. */
+#if ! defined (HAVE_decrement_and_branch_until_zero) \
+&& defined (HAVE_decrement_and_branch_on_count)
&& (! (add_val == 1 && loop_info->vtop
&& (bl->biv_count == 0
|| no_use_except_counting)))
enum machine_mode mode = GET_MODE (reg);
enum insn_code icode
= add_optab->handlers[(int) mode].insn_code;
- if (! (*insn_operand_predicate[icode][0]) (reg, mode)
- || ! ((*insn_operand_predicate[icode][1])
+
+ if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
+ || ! ((*insn_data[icode].operand[1].predicate)
(comparison_value, mode))
- || ! (*insn_operand_predicate[icode][2]) (offset, mode))
+ || ! ((*insn_data[icode].operand[2].predicate)
+ (offset, mode)))
return 0;
start_value
= gen_rtx_PLUS (mode, comparison_value, offset);
enum machine_mode mode = GET_MODE (reg);
enum insn_code icode
= sub_optab->handlers[(int) mode].insn_code;
- if (! (*insn_operand_predicate[icode][0]) (reg, mode)
- || ! ((*insn_operand_predicate[icode][1])
+ if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
+ || ! ((*insn_data[icode].operand[1].predicate)
(comparison_value, mode))
- || ! ((*insn_operand_predicate[icode][2])
+ || ! ((*insn_data[icode].operand[2].predicate)
(initial_value, mode)))
return 0;
start_value
bl->nonneg = 1;
}
+ /* No insn may reference both the reversed and another biv or it
+ will fail (see comment near the top of the loop reversal
+ code).
+ Earlier on, we have verified that the biv has no use except
+ counting, or it is the only biv in this function.
+ However, the code that computes no_use_except_counting does
+ not verify reg notes. It's possible to have an insn that
+ references another biv, and has a REG_EQUAL note with an
+ expression based on the reversed biv. To avoid this case,
+ remove all REG_EQUAL notes based on the reversed biv
+ here. */
+ for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
+ if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
+ {
+ rtx *pnote;
+ rtx set = single_set (p);
+ /* If this is a set of a GIV based on the reversed biv, any
+ REG_EQUAL notes should still be correct. */
+ if (! set
+ || GET_CODE (SET_DEST (set)) != REG
+ || (size_t) REGNO (SET_DEST (set)) >= reg_iv_type->num_elements
+ || REG_IV_TYPE (REGNO (SET_DEST (set))) != GENERAL_INDUCT
+ || REG_IV_INFO (REGNO (SET_DEST (set)))->src_reg != bl->biv->src_reg)
+ for (pnote = ®_NOTES (p); *pnote;)
+ {
+ if (REG_NOTE_KIND (*pnote) == REG_EQUAL
+ && reg_mentioned_p (regno_reg_rtx[bl->regno],
+ XEXP (*pnote, 0)))
+ *pnote = XEXP (*pnote, 1);
+ else
+ pnote = &XEXP (*pnote, 1);
+ }
+ }
+
/* Mark that this biv has been reversed. Each giv which depends
on this biv, and which is also live past the end of the loop
will have to be fixed up. */
bl->reversed = 1;
if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "Reversed loop and added reg_nonneg\n");
+ {
+ fprintf (loop_dump_stream, "Reversed loop");
+ if (bl->nonneg)
+ fprintf (loop_dump_stream, " and added reg_nonneg\n");
+ else
+ fprintf (loop_dump_stream, "\n");
+ }
return 1;
}
enum rtx_code code = GET_CODE (p);
rtx where = threshold >= insn_count ? loop_start : p;
+ /* If this is a libcall that sets a giv, skip ahead to its end. */
+ if (GET_RTX_CLASS (code) == 'i')
+ {
+ rtx note = find_reg_note (p, REG_LIBCALL, NULL_RTX);
+
+ if (note)
+ {
+ rtx last = XEXP (note, 0);
+ rtx set = single_set (last);
+
+ if (set && GET_CODE (SET_DEST (set)) == REG)
+ {
+ int regno = REGNO (SET_DEST (set));
+
+ if (regno < max_reg_before_loop
+ && REG_IV_TYPE (regno) == GENERAL_INDUCT
+ && REG_IV_INFO (regno)->src_reg == bl->biv->src_reg)
+ p = last;
+ }
+ }
+ }
if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
&& reg_mentioned_p (reg, PATTERN (p))
&& ! maybe_eliminate_biv_1 (PATTERN (p), p, bl, eliminate_p, where))
return 0;
}
\f
+/* INSN and REFERENCE are instructions in the same insn chain.
+ Return non-zero if INSN is first. */
+
+int
+loop_insn_first_p (insn, reference)
+ rtx insn, reference;
+{
+ rtx p, q;
+
+ for (p = insn, q = reference; ;)
+ {
+ /* Start with test for not first so that INSN == REFERENCE yields not
+ first. */
+ if (q == insn || ! p)
+ return 0;
+ if (p == reference || ! q)
+ return 1;
+
+ /* Either of P or Q might be a NOTE. Notes have the same LUID as the
+ previous insn, hence the <= comparison below does not work if
+ P is a note. */
+ if (INSN_UID (p) < max_uid_for_loop
+ && INSN_UID (q) < max_uid_for_loop
+ && GET_CODE (p) != NOTE)
+ return INSN_LUID (p) <= INSN_LUID (q);
+
+ if (INSN_UID (p) >= max_uid_for_loop
+ || GET_CODE (p) == NOTE)
+ p = NEXT_INSN (p);
+ if (INSN_UID (q) >= max_uid_for_loop)
+ q = NEXT_INSN (q);
+ }
+}
+
+/* We are trying to eliminate BIV in INSN using GIV. Return non-zero if
+ the offset that we have to take into account due to auto-increment /
+ div derivation is zero. */
+static int
+biv_elimination_giv_has_0_offset (biv, giv, insn)
+ struct induction *biv, *giv;
+ rtx insn;
+{
+ /* 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'd have to adjust the value used here.
+ This is rare, so we don't bother to make this possible. */
+ if (giv->auto_inc_opt
+ && ((loop_insn_first_p (giv->insn, insn)
+ && loop_insn_first_p (insn, biv->insn))
+ || (loop_insn_first_p (biv->insn, insn)
+ && loop_insn_first_p (insn, giv->insn))))
+ return 0;
+
+ /* If the giv V was derived from another giv, and INSN does
+ not occur between the giv insn and the biv insn, then we'd
+ have to adjust the value used here. This is rare, so we don't
+ bother to make this possible. */
+ if (giv->derived_from
+ && ! (giv->always_executed
+ && loop_insn_first_p (giv->insn, insn)
+ && loop_insn_first_p (insn, biv->insn)))
+ return 0;
+ if (giv->same
+ && giv->same->derived_from
+ && ! (giv->same->always_executed
+ && loop_insn_first_p (giv->same->insn, insn)
+ && loop_insn_first_p (insn, biv->insn)))
+ return 0;
+
+ return 1;
+}
+
/* If BL appears in X (part of the pattern of INSN), see if we can
eliminate its use. If so, return 1. If not, return 0.
rtx new;
#endif
int arg_operand;
- char *fmt;
+ const char *fmt;
int i, j;
switch (code)
&& 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))))
+ if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
continue;
if (! eliminate_p)
|| (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))))
+ if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
continue;
if (! eliminate_p)
&& ! 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))))
+ if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
continue;
if (! eliminate_p)
{
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))))
+ if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
continue;
if (! eliminate_p)
{
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))))
+ if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
continue;
if (! eliminate_p)
&& 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))))
+ if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
continue;
if (! eliminate_p)
else
{
register int i, j;
- register char *fmt = GET_RTX_FORMAT (GET_CODE (x));
+ register const char *fmt = GET_RTX_FORMAT (GET_CODE (x));
for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
int i;
unsigned HOST_WIDE_INT n_iterations;
-#if 0
int increment_direction, compare_direction;
/* If the loop condition is <= or >=, the number of iteration
int add_iteration = 0;
enum machine_mode loop_var_mode = word_mode;
-#endif
int loop_num = uid_loop_num [INSN_UID (loop_start)];
/* It's impossible to instrument a competely unrolled loop. */
- if (loop_info->unroll_number == -1)
+ if (loop_info->unroll_number == loop_info->n_iterations)
return;
/* Make sure that the count register is not in use. */
/* Make sure that the loop does not contain a function call
(the count register might be altered by the called function). */
- if (loop_has_call)
+ if (loop_info->has_call)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
/* Make sure that the loop does not jump via a table.
(the count register might be used to perform the branch on table). */
- if (loop_has_tablejump)
+ if (loop_info->has_tablejump)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
NULL_RTX, 0, OPTAB_LIB_WIDEN);
if (increment_value_abs != 1)
- {
- /* ??? This will generate an expensive divide instruction for
- most targets. The original authors apparently expected this
- to be a shift, since they test for power-of-2 divisors above,
- but just naively generating a divide instruction will not give
- a shift. It happens to work for the PowerPC target because
- the rs6000.md file has a divide pattern that emits shifts.
- It will probably not work for any other target. */
- iterations_num_reg = expand_binop (loop_var_mode, sdiv_optab,
- temp_reg,
- GEN_INT (increment_value_abs),
- NULL_RTX, 0, OPTAB_LIB_WIDEN);
- }
+ iterations_num_reg = expand_binop (loop_var_mode, asr_optab,
+ temp_reg,
+ GEN_INT (exact_log2 (increment_value_abs)),
+ NULL_RTX, 0, OPTAB_LIB_WIDEN);
else
iterations_num_reg = temp_reg;
}
static void
load_mems_and_recount_loop_regs_set (scan_start, end, loop_top, start,
- reg_single_usage, insn_count)
+ insn_count)
rtx scan_start;
rtx end;
rtx loop_top;
rtx start;
- varray_type reg_single_usage;
int *insn_count;
{
int nregs = max_reg_num ();
VARRAY_GROW (set_in_loop, nregs);
VARRAY_GROW (n_times_set, nregs);
VARRAY_GROW (may_not_optimize, nregs);
- if (reg_single_usage)
- VARRAY_GROW (reg_single_usage, nregs);
+ VARRAY_GROW (reg_single_usage, nregs);
}
/* Clear the arrays */
bzero ((char *) &set_in_loop->data, nregs * sizeof (int));
bzero ((char *) &may_not_optimize->data, nregs * sizeof (char));
- if (reg_single_usage)
- bzero ((char *) ®_single_usage->data, nregs * sizeof (rtx));
+ bzero ((char *) ®_single_usage->data, nregs * sizeof (rtx));
count_loop_regs_set (loop_top ? loop_top : start, end,
may_not_optimize, reg_single_usage,
int i;
rtx p;
rtx label = NULL_RTX;
- rtx end_label;
+ rtx end_label = NULL_RTX;
if (loop_mems_idx > 0)
{
/* Load the memory immediately before START, which is
the NOTE_LOOP_BEG. */
- set = gen_rtx_SET (GET_MODE (reg), reg, mem);
+ set = gen_move_insn (reg, mem);
emit_insn_before (set, start);
if (written)
/* Store the memory immediately after END, which is
the NOTE_LOOP_END. */
- set = gen_rtx_SET (GET_MODE (reg), copy_rtx (mem), reg);
+ set = gen_move_insn (copy_rtx (mem), reg);
emit_insn_after (set, label);
}
projects / platform / upstream / gcc.git / blobdiff