/* Perform various loop optimizations, including strength reduction.
Copyright (C) 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997,
- 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+ 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
-This file is part of GNU CC.
+This file is part of GCC.
-GNU CC is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
-any later version.
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
-GNU CC is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
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, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+along with GCC; see the file COPYING. If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA. */
/* This is the loop optimization pass of the compiler.
It finds invariant computations within loops and moves them
#include "hard-reg-set.h"
#include "basic-block.h"
#include "insn-config.h"
-#include "insn-flags.h"
#include "regs.h"
#include "recog.h"
#include "flags.h"
#include "cselib.h"
#include "except.h"
#include "toplev.h"
+#include "predict.h"
+#include "insn-flags.h"
+#include "optabs.h"
+
+/* Not really meaningful values, but at least something. */
+#ifndef SIMULTANEOUS_PREFETCHES
+#define SIMULTANEOUS_PREFETCHES 3
+#endif
+#ifndef PREFETCH_BLOCK
+#define PREFETCH_BLOCK 32
+#endif
+#ifndef HAVE_prefetch
+#define HAVE_prefetch 0
+#define CODE_FOR_prefetch 0
+#define gen_prefetch(a,b,c) (abort(), NULL_RTX)
+#endif
+
+/* Give up the prefetch optimizations once we exceed a given threshhold.
+ It is unlikely that we would be able to optimize something in a loop
+ with so many detected prefetches. */
+#define MAX_PREFETCHES 100
+/* The number of prefetch blocks that are beneficial to fetch at once before
+ a loop with a known (and low) iteration count. */
+#define PREFETCH_BLOCKS_BEFORE_LOOP_MAX 6
+/* For very tiny loops it is not worthwhile to prefetch even before the loop,
+ since it is likely that the data are already in the cache. */
+#define PREFETCH_BLOCKS_BEFORE_LOOP_MIN 2
+/* The minimal number of prefetch blocks that a loop must consume to make
+ the emitting of prefetch instruction in the body of loop worthwhile. */
+#define PREFETCH_BLOCKS_IN_LOOP_MIN 6
+
+/* Parameterize some prefetch heuristics so they can be turned on and off
+ easily for performance testing on new architecures. These can be
+ defined in target-dependent files. */
+
+/* Prefetch is worthwhile only when loads/stores are dense. */
+#ifndef PREFETCH_ONLY_DENSE_MEM
+#define PREFETCH_ONLY_DENSE_MEM 1
+#endif
+
+/* Define what we mean by "dense" loads and stores; This value divided by 256
+ is the minimum percentage of memory references that worth prefetching. */
+#ifndef PREFETCH_DENSE_MEM
+#define PREFETCH_DENSE_MEM 220
+#endif
+
+/* Do not prefetch for a loop whose iteration count is known to be low. */
+#ifndef PREFETCH_NO_LOW_LOOPCNT
+#define PREFETCH_NO_LOW_LOOPCNT 1
+#endif
+
+/* Define what we mean by a "low" iteration count. */
+#ifndef PREFETCH_LOW_LOOPCNT
+#define PREFETCH_LOW_LOOPCNT 32
+#endif
+
+/* Do not prefetch for a loop that contains a function call; such a loop is
+ probably not an internal loop. */
+#ifndef PREFETCH_NO_CALL
+#define PREFETCH_NO_CALL 1
+#endif
+
+/* Do not prefetch accesses with an extreme stride. */
+#ifndef PREFETCH_NO_EXTREME_STRIDE
+#define PREFETCH_NO_EXTREME_STRIDE 1
+#endif
+
+/* Define what we mean by an "extreme" stride. */
+#ifndef PREFETCH_EXTREME_STRIDE
+#define PREFETCH_EXTREME_STRIDE 4096
+#endif
+
+/* Do not handle reversed order prefetches (negative stride). */
+#ifndef PREFETCH_NO_REVERSE_ORDER
+#define PREFETCH_NO_REVERSE_ORDER 1
+#endif
+
+/* Prefetch even if the GIV is not always executed. */
+#ifndef PREFETCH_NOT_ALWAYS
+#define PREFETCH_NOT_ALWAYS 0
+#endif
+
+/* If the loop requires more prefetches than the target can process in
+ parallel then don't prefetch anything in that loop. */
+#ifndef PREFETCH_LIMIT_TO_SIMULTANEOUS
+#define PREFETCH_LIMIT_TO_SIMULTANEOUS 1
+#endif
#define LOOP_REG_LIFETIME(LOOP, REGNO) \
((REGNO_LAST_LUID (REGNO) - REGNO_FIRST_LUID (REGNO)))
((REGNO_LAST_LUID (REGNO) > INSN_LUID ((LOOP)->end) \
|| REGNO_FIRST_LUID (REGNO) < INSN_LUID ((LOOP)->start)))
+#define LOOP_REGNO_NREGS(REGNO, SET_DEST) \
+((REGNO) < FIRST_PSEUDO_REGISTER \
+ ? HARD_REGNO_NREGS ((REGNO), GET_MODE (SET_DEST)) : 1)
+
/* Vector mapping INSN_UIDs to luids.
The luids are like uids but increase monotonically always.
/* Forward declarations. */
+static void invalidate_loops_containing_label PARAMS ((rtx));
static void find_and_verify_loops PARAMS ((rtx, struct loops *));
static void mark_loop_jump PARAMS ((rtx, struct loop *));
static void prescan_loop PARAMS ((struct loop *));
rtx, int, rtx));
static int labels_in_range_p PARAMS ((rtx, int));
static void count_one_set PARAMS ((struct loop_regs *, rtx, rtx, rtx *));
-
-static void count_loop_regs_set PARAMS ((const struct loop *, int *));
static void note_addr_stored PARAMS ((rtx, rtx, void *));
static void note_set_pseudo_multiple_uses PARAMS ((rtx, rtx, void *));
static int loop_reg_used_before_p PARAMS ((const struct loop *, rtx, rtx));
static void force_movables PARAMS ((struct loop_movables *));
static void combine_movables PARAMS ((struct loop_movables *,
struct loop_regs *));
+static int num_unmoved_movables PARAMS ((const struct loop *));
static int regs_match_p PARAMS ((rtx, rtx, struct loop_movables *));
static int rtx_equal_for_loop_p PARAMS ((rtx, rtx, struct loop_movables *,
struct loop_regs *));
static void loop_givs_dead_check PARAMS((struct loop *, struct iv_class *));
static void loop_givs_reduce PARAMS((struct loop *, struct iv_class *));
static void loop_givs_rescan PARAMS((struct loop *, struct iv_class *,
- rtx *, rtx));
+ rtx *));
static void loop_ivs_free PARAMS((struct loop *));
-static void strength_reduce PARAMS ((struct loop *, int, int));
+static void strength_reduce PARAMS ((struct loop *, int));
static void find_single_use_in_loop PARAMS ((struct loop_regs *, rtx, rtx));
static int valid_initial_value_p PARAMS ((rtx, rtx, int, rtx));
static void find_mem_givs PARAMS ((const struct loop *, rtx, rtx, int, int));
int, int));
static void check_final_value PARAMS ((const struct loop *,
struct induction *));
+static void loop_ivs_dump PARAMS((const struct loop *, FILE *, int));
+static void loop_iv_class_dump PARAMS((const struct iv_class *, FILE *, int));
+static void loop_biv_dump PARAMS((const struct induction *, FILE *, int));
+static void loop_giv_dump PARAMS((const struct induction *, FILE *, int));
static void record_giv PARAMS ((const struct loop *, struct induction *,
rtx, rtx, rtx, rtx, rtx, rtx, int,
enum g_types, int, int, rtx *));
static void update_giv_derive PARAMS ((const struct loop *, rtx));
-static void check_ext_dependant_givs PARAMS ((struct iv_class *,
+static void check_ext_dependent_givs PARAMS ((struct iv_class *,
struct loop_info *));
static int basic_induction_var PARAMS ((const struct loop *, rtx,
enum machine_mode, rtx, rtx,
static int maybe_eliminate_biv PARAMS ((const struct loop *, struct iv_class *,
int, int, int));
static int maybe_eliminate_biv_1 PARAMS ((const struct loop *, rtx, rtx,
- struct iv_class *, int, rtx));
+ struct iv_class *, int,
+ basic_block, rtx));
static int last_use_this_basic_block PARAMS ((rtx, rtx));
static void record_initial PARAMS ((rtx, rtx, void *));
static void update_reg_last_use PARAMS ((rtx, rtx));
static rtx next_insn_in_loop PARAMS ((const struct loop *, rtx));
-static void load_mems_and_recount_loop_regs_set PARAMS ((const struct loop*,
- int *));
+static void loop_regs_scan PARAMS ((const struct loop *, int));
+static int count_insns_in_loop PARAMS ((const struct loop *));
static void load_mems PARAMS ((const struct loop *));
static int insert_loop_mem PARAMS ((rtx *, void *));
static int replace_loop_mem PARAMS ((rtx *, void *));
static int replace_label PARAMS ((rtx *, void *));
static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
+static rtx gen_add_mult PARAMS ((rtx, rtx, rtx, rtx));
+static void loop_regs_update PARAMS ((const struct loop *, rtx));
static int iv_add_mult_cost PARAMS ((rtx, rtx, rtx, rtx));
+static rtx loop_insn_emit_after PARAMS((const struct loop *, basic_block,
+ rtx, rtx));
+static rtx loop_call_insn_emit_before PARAMS((const struct loop *,
+ basic_block, rtx, rtx));
+static rtx loop_call_insn_hoist PARAMS((const struct loop *, rtx));
+static rtx loop_insn_sink_or_swim PARAMS((const struct loop *, rtx));
+
static void loop_dump_aux PARAMS ((const struct loop *, FILE *, int));
+static void loop_delete_insns PARAMS ((rtx, rtx));
+static HOST_WIDE_INT remove_constant_addition PARAMS ((rtx *));
+static rtx gen_load_of_final_value PARAMS ((rtx, rtx));
+void debug_ivs PARAMS ((const struct loop *));
+void debug_iv_class PARAMS ((const struct iv_class *));
+void debug_biv PARAMS ((const struct induction *));
+void debug_giv PARAMS ((const struct induction *));
void debug_loop PARAMS ((const struct loop *));
void debug_loops PARAMS ((const struct loops *));
} loop_replace_args;
/* Nonzero iff INSN is between START and END, inclusive. */
-#define INSN_IN_RANGE_P(INSN, START, END) \
- (INSN_UID (INSN) < max_uid_for_loop \
+#define INSN_IN_RANGE_P(INSN, START, END) \
+ (INSN_UID (INSN) < max_uid_for_loop \
&& INSN_LUID (INSN) >= INSN_LUID (START) \
&& INSN_LUID (INSN) <= INSN_LUID (END))
FILE *dumpfile;
int flags;
{
- register rtx insn;
- register int i;
+ rtx insn;
+ int i;
struct loops loops_data;
struct loops *loops = &loops_data;
struct loop_info *loops_info;
{
struct loop_info *loop_info = LOOP_INFO (loop);
struct loop_regs *regs = LOOP_REGS (loop);
- register int i;
+ int i;
rtx loop_start = loop->start;
rtx loop_end = loop->end;
rtx p;
movables->head = 0;
movables->last = 0;
- movables->num = 0;
/* 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
loop->scan_start = p;
+ /* If loop end is the end of the current function, then emit a
+ NOTE_INSN_DELETED after loop_end and set loop->sink to the dummy
+ note insn. This is the position we use when sinking insns out of
+ the loop. */
+ if (NEXT_INSN (loop->end) != 0)
+ loop->sink = NEXT_INSN (loop->end);
+ else
+ loop->sink = emit_note_after (NOTE_INSN_DELETED, loop->end);
+
/* Set up variables describing this loop. */
prescan_loop (loop);
threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
return;
}
- /* Count number of times each reg is set during this loop. Set
- regs->array[I].may_not_optimize if it is not safe to move out the
- setting of register I. Set regs->array[I].single_usage. */
-
- regs->num = max_reg_num ();
-
- /* Allocate extra space for REGs that might be created by
- load_mems. We allocate a little extra slop as well, in the hopes
- that even after the moving of movables creates some new registers
- we won't have to reallocate these arrays. However, we do grow
- the arrays, if necessary, in load_mems_recount_loop_regs_set. */
- regs->size = regs->num + loop_info->mems_idx + 16;
- regs->array = (struct loop_reg *)
- xmalloc (regs->size * sizeof (*regs->array));
-
- for (i = 0; i < regs->num; i++)
- {
- regs->array[i].set_in_loop = 0;
- regs->array[i].may_not_optimize = 0;
- regs->array[i].single_usage = NULL_RTX;
- }
-
- count_loop_regs_set (loop, &insn_count);
-
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- {
- regs->array[i].may_not_optimize = 1;
- regs->array[i].set_in_loop = 1;
- }
-
-#ifdef AVOID_CCMODE_COPIES
- /* Don't try to move insns which set CC registers if we should not
- create CCmode register copies. */
- for (i = regs->num - 1; i >= FIRST_PSEUDO_REGISTER; i--)
- if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
- regs->array[i].may_not_optimize = 1;
-#endif
-
- for (i = 0; i < regs->num; i++)
- regs->array[i].n_times_set = regs->array[i].set_in_loop;
+ /* Allocate extra space for REGs that might be created by load_mems.
+ We allocate a little extra slop as well, in the hopes that we
+ won't have to reallocate the regs array. */
+ loop_regs_scan (loop, loop_info->mems_idx + 16);
+ insn_count = count_insns_in_loop (loop);
if (loop_dump_stream)
{
if (GET_CODE (p) == INSN
&& (set = single_set (p))
&& GET_CODE (SET_DEST (set)) == REG
+#ifdef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
+ && SET_DEST (set) != pic_offset_table_rtx
+#endif
&& ! regs->array[REGNO (SET_DEST (set))].may_not_optimize)
{
int tem1 = 0;
}
}
+ /* For parallels, add any possible uses to the depencies, as we can't move
+ the insn without resolving them first. */
+ if (GET_CODE (PATTERN (p)) == PARALLEL)
+ {
+ for (i = 0; i < XVECLEN (PATTERN (p), 0); i++)
+ {
+ rtx x = XVECEXP (PATTERN (p), 0, i);
+ if (GET_CODE (x) == USE)
+ dependencies = gen_rtx_EXPR_LIST (VOIDmode, XEXP (x, 0), dependencies);
+ }
+ }
+
/* Don't try to optimize a register that was made
by loop-optimization for an inner loop.
We don't know its life-span, so we can't compute the benefit. */
something after this point in the loop might
depend on its value before the set). */
! reg_in_basic_block_p (p, SET_DEST (set))
- /* And the set is not guaranteed to be executed one
+ /* And the set is not guaranteed to be executed once
the loop starts, or the value before the set is
needed before the set occurs...
&& ! ((maybe_never || call_passed)
&& may_trap_p (src)))
{
- register struct movable *m;
- register int regno = REGNO (SET_DEST (set));
+ struct movable *m;
+ int regno = REGNO (SET_DEST (set));
/* A potential lossage is where we have a case where two insns
can be combined as long as they are both in the loop, but
&& (REGNO_LAST_UID (regno)
== INSN_UID (regs->array[regno].single_usage))
&& regs->array[regno].set_in_loop == 1
+ && GET_CODE (SET_SRC (set)) != ASM_OPERANDS
&& ! side_effects_p (SET_SRC (set))
&& ! find_reg_note (p, REG_RETVAL, NULL_RTX)
&& (! SMALL_REGISTER_CLASSES
= replace_rtx (REG_NOTES (regs->array[regno].single_usage),
SET_DEST (set), copy_rtx (SET_SRC (set)));
- PUT_CODE (p, NOTE);
- NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
- NOTE_SOURCE_FILE (p) = 0;
- regs->array[regno].set_in_loop = 0;
+ delete_insn (p);
+ for (i = 0; i < LOOP_REGNO_NREGS (regno, SET_DEST (set)); i++)
+ regs->array[regno+i].set_in_loop = 0;
continue;
}
m->savings = regs->array[regno].n_times_set;
if (find_reg_note (p, REG_RETVAL, NULL_RTX))
m->savings += libcall_benefit (p);
- regs->array[regno].set_in_loop = move_insn ? -2 : -1;
+ for (i = 0; i < LOOP_REGNO_NREGS (regno, SET_DEST (set)); i++)
+ regs->array[regno+i].set_in_loop = move_insn ? -2 : -1;
/* Add M to the end of the chain MOVABLES. */
loop_movables_add (movables, m);
== SET_DEST (set))
&& !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
{
- register int regno = REGNO (SET_DEST (set));
+ int regno = REGNO (SET_DEST (set));
if (regs->array[regno].set_in_loop == 2)
{
- register struct movable *m;
+ struct movable *m;
m = (struct movable *) xmalloc (sizeof (struct movable));
m->next = 0;
m->insn = p;
m->match = 0;
m->lifetime = LOOP_REG_LIFETIME (loop, regno);
m->savings = 1;
- regs->array[regno].set_in_loop = -1;
+ for (i = 0; i < LOOP_REGNO_NREGS (regno, SET_DEST (set)); i++)
+ regs->array[regno+i].set_in_loop = -1;
/* Add M to the end of the chain MOVABLES. */
loop_movables_add (movables, m);
}
/* Past a call insn, we get to insns which might not be executed
because the call might exit. This matters for insns that trap.
Constant and pure call insns always return, so they don't count. */
- else if (GET_CODE (p) == CALL_INSN && ! CONST_CALL_P (p))
+ else if (GET_CODE (p) == CALL_INSN && ! CONST_OR_PURE_CALL_P (p))
call_passed = 1;
/* 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
beginning, don't set maybe_never for that. This must be an
unconditional jump, otherwise the code at the top of the
loop might never be executed. Unconditional jumps are
- followed a by barrier then loop end. */
+ followed by a barrier then the loop_end. */
&& ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop->top
&& NEXT_INSN (NEXT_INSN (p)) == loop_end
&& any_uncondjump_p (p)))
optimizing for code size. */
if (! optimize_size)
- move_movables (loop, movables, threshold, insn_count);
+ {
+ move_movables (loop, movables, threshold, insn_count);
+
+ /* Recalculate regs->array if move_movables has created new
+ registers. */
+ if (max_reg_num () > regs->num)
+ {
+ loop_regs_scan (loop, 0);
+ for (update_start = loop_start;
+ PREV_INSN (update_start)
+ && GET_CODE (PREV_INSN (update_start)) != CODE_LABEL;
+ update_start = PREV_INSN (update_start))
+ ;
+ update_end = NEXT_INSN (loop_end);
+
+ reg_scan_update (update_start, update_end, loop_max_reg);
+ loop_max_reg = max_reg_num ();
+ }
+ }
/* Now candidates that still are negative are those not moved.
Change regs->array[I].set_in_loop to indicate that those are not actually
/* Now that we've moved some things out of the loop, we might be able to
hoist even more memory references. */
- load_mems_and_recount_loop_regs_set (loop, &insn_count);
+ load_mems (loop);
+
+ /* Recalculate regs->array if load_mems has created new registers. */
+ if (max_reg_num () > regs->num)
+ loop_regs_scan (loop, 0);
for (update_start = loop_start;
PREV_INSN (update_start)
/* Ensure our label doesn't go away. */
LABEL_NUSES (update_end)++;
- strength_reduce (loop, insn_count, flags);
+ strength_reduce (loop, flags);
reg_scan_update (update_start, update_end, loop_max_reg);
loop_max_reg = max_reg_num ();
if (update_end && GET_CODE (update_end) == CODE_LABEL
&& --LABEL_NUSES (update_end) == 0)
- delete_insn (update_end);
+ delete_related_insns (update_end);
}
ignore_some_movables (movables)
struct loop_movables *movables;
{
- register struct movable *m, *m1;
+ struct movable *m, *m1;
for (m = movables->head; m; m = m->next)
{
force_movables (movables)
struct loop_movables *movables;
{
- register struct movable *m, *m1;
+ struct movable *m, *m1;
+
for (m1 = movables->head; m1; m1 = m1->next)
/* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
if (!m1->partial && !m1->done)
struct loop_movables *movables;
struct loop_regs *regs;
{
- register struct movable *m;
+ struct movable *m;
char *matched_regs = (char *) xmalloc (regs->num);
enum machine_mode mode;
/* Regs that are set more than once are not allowed to match
or be matched. I'm no longer sure why not. */
+ /* Only pseudo registers are allowed to match or be matched,
+ since move_movables does not validate the change. */
/* Perhaps testing m->consec_sets would be more appropriate here? */
for (m = movables->head; m; m = m->next)
if (m->match == 0 && regs->array[m->regno].n_times_set == 1
+ && m->regno >= FIRST_PSEUDO_REGISTER
&& !m->partial)
{
- register struct movable *m1;
+ struct movable *m1;
int regno = m->regno;
memset (matched_regs, 0, regs->num);
/* We want later insns to match the first one. Don't make the first
one match any later ones. So start this loop at m->next. */
for (m1 = m->next; m1; m1 = m1->next)
- if (m != m1 && m1->match == 0
+ if (m != m1 && m1->match == 0
&& regs->array[m1->regno].n_times_set == 1
+ && m1->regno >= FIRST_PSEUDO_REGISTER
/* A reg used outside the loop mustn't be eliminated. */
&& !m1->global
/* A reg used for zero-extending mustn't be eliminated. */
for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
mode = GET_MODE_WIDER_MODE (mode))
{
- register struct movable *m0 = 0;
+ struct movable *m0 = 0;
/* Combine all the registers for extension from mode MODE.
Don't combine any that are used outside this loop. */
if (m->partial && ! m->global
&& mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
{
- register struct movable *m1;
+ struct movable *m1;
+
int first = REGNO_FIRST_LUID (m->regno);
int last = REGNO_LAST_LUID (m->regno);
/* Clean up. */
free (matched_regs);
}
+
+/* Returns the number of movable instructions in LOOP that were not
+ moved outside the loop. */
+
+static int
+num_unmoved_movables (loop)
+ const struct loop *loop;
+{
+ int num = 0;
+ struct movable *m;
+
+ for (m = LOOP_MOVABLES (loop)->head; m; m = m->next)
+ if (!m->done)
+ ++num;
+
+ return num;
+}
+
\f
/* Return 1 if regs X and Y will become the same if moved. */
struct loop_movables *movables;
struct loop_regs *regs;
{
- register int i;
- register int j;
- register struct movable *m;
- register enum rtx_code code;
- register const char *fmt;
+ int i;
+ int j;
+ struct movable *m;
+ enum rtx_code code;
+ 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 the reference. LABEL_NUSES for CODE_LABEL
- references is incremented once for each added note. */
+ references is incremented once for each added note. */
static void
add_label_notes (x, insns)
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) = gen_rtx_INSN_LIST (REG_LABEL, XEXP (x, 0),
REG_NOTES (insn));
if (LABEL_P (XEXP (x, 0)))
LABEL_NUSES (XEXP (x, 0))++;
struct loop_regs *regs = LOOP_REGS (loop);
int nregs = regs->num;
rtx new_start = 0;
- register struct movable *m;
- register rtx p;
+ struct movable *m;
+ rtx p;
rtx loop_start = loop->start;
rtx loop_end = loop->end;
/* Map of pseudo-register replacements to handle combining
rtx *reg_map = (rtx *) xcalloc (nregs, sizeof (rtx));
char *already_moved = (char *) xcalloc (nregs, sizeof (char));
- movables->num = 0;
-
for (m = movables->head; m; m = m->next)
{
/* Describe this movable insn. */
INSN_UID (m->forces->insn));
}
- /* Count movables. Value used in heuristics in strength_reduce. */
- movables->num++;
-
/* Ignore the insn if it's already done (it matched something else).
Otherwise, see if it is now safe to move. */
m->insn))))
&& (! m->forces || m->forces->done))
{
- register int regno;
- register rtx p;
+ int regno;
+ rtx p;
int savings = m->savings;
/* We have an insn that is safe to move.
&& regs->array[m->forces->regno].n_times_set == 1))
{
int count;
- register struct movable *m1;
+ struct movable *m1;
rtx first = NULL_RTX;
/* Now move the insns that set the reg. */
for (m1 = m; m1->match; m1 = m1->match);
newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
SET_DEST (PATTERN (m1->insn)));
- i1 = emit_insn_before (newpat, loop_start);
+ i1 = loop_insn_hoist (loop, newpat);
/* Mark the moved, invariant reg as being allowed to
share a hard reg with the other matching invariant. */
the move insn before the loop. */
else if (m->move_insn)
{
- rtx i1, temp;
+ rtx i1, temp, seq;
for (count = m->consec; count >= 0; count--)
{
start_sequence ();
emit_move_insn (m->set_dest, m->set_src);
temp = get_insns ();
+ seq = gen_sequence ();
end_sequence ();
add_label_notes (m->set_src, temp);
- i1 = emit_insns_before (temp, loop_start);
+ i1 = loop_insn_hoist (loop, seq);
if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
- REG_NOTES (i1)
- = gen_rtx_EXPR_LIST (m->is_equiv ? REG_EQUIV : REG_EQUAL,
- m->set_src, REG_NOTES (i1));
+ set_unique_reg_note (i1,
+ m->is_equiv ? REG_EQUIV : REG_EQUAL,
+ m->set_src);
if (loop_dump_stream)
fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
if (GET_CODE (temp) == CALL_INSN
&& fn_address != 0
&& reg_referenced_p (fn_reg, body))
- emit_insn_after (gen_move_insn (fn_reg,
- fn_address),
- fn_address_insn);
+ loop_insn_emit_after (loop, 0, fn_address_insn,
+ gen_move_insn
+ (fn_reg, fn_address));
if (GET_CODE (temp) == CALL_INSN)
{
- i1 = emit_call_insn_before (body, loop_start);
+ i1 = loop_call_insn_hoist (loop, body);
/* Because the USAGE information potentially
contains objects other than hard registers
we need to copy it. */
= copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
}
else
- i1 = emit_insn_before (body, loop_start);
+ i1 = loop_insn_hoist (loop, body);
if (first == 0)
first = i1;
if (temp == fn_address_insn)
fn_address_insn = i1;
REG_NOTES (i1) = REG_NOTES (temp);
+ REG_NOTES (temp) = NULL;
delete_insn (temp);
}
if (new_start == 0)
rtx tem;
start_sequence ();
- tem = expand_binop
- (GET_MODE (reg), and_optab, reg,
+ tem = expand_simple_binop
+ (GET_MODE (reg), AND, reg,
GEN_INT ((((HOST_WIDE_INT) 1
<< GET_MODE_BITSIZE (m->savemode)))
- 1),
emit_move_insn (reg, tem);
sequence = gen_sequence ();
end_sequence ();
- i1 = emit_insn_before (sequence, loop_start);
+ i1 = loop_insn_hoist (loop, sequence);
}
else if (GET_CODE (p) == CALL_INSN)
{
- i1 = emit_call_insn_before (PATTERN (p), loop_start);
+ i1 = loop_call_insn_hoist (loop, PATTERN (p));
/* Because the USAGE information potentially
contains objects other than hard registers
we need to copy it. */
}
else if (count == m->consec && m->move_insn_first)
{
+ rtx seq;
/* The SET_SRC might not be invariant, so we must
use the REG_EQUAL note. */
start_sequence ();
emit_move_insn (m->set_dest, m->set_src);
temp = get_insns ();
+ seq = gen_sequence ();
end_sequence ();
add_label_notes (m->set_src, temp);
- i1 = emit_insns_before (temp, loop_start);
+ i1 = loop_insn_hoist (loop, seq);
if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
- REG_NOTES (i1)
- = gen_rtx_EXPR_LIST ((m->is_equiv ? REG_EQUIV
- : REG_EQUAL),
- m->set_src, REG_NOTES (i1));
+ set_unique_reg_note (i1, m->is_equiv ? REG_EQUIV
+ : REG_EQUAL, m->set_src);
}
else
- i1 = emit_insn_before (PATTERN (p), loop_start);
+ i1 = loop_insn_hoist (loop, PATTERN (p));
if (REG_NOTES (i1) == 0)
{
REG_NOTES (i1) = REG_NOTES (p);
+ REG_NOTES (p) = NULL;
/* If there is a REG_EQUAL note present whose value
is not loop invariant, then delete it, since it
/* The reg set here is now invariant. */
if (! m->partial)
- regs->array[regno].set_in_loop = 0;
+ {
+ int i;
+ for (i = 0; i < LOOP_REGNO_NREGS (regno, m->set_dest); i++)
+ regs->array[regno+i].set_in_loop = 0;
+ }
m->done = 1;
and prevent further processing of it. */
m1->done = 1;
- /* if library call, delete all insn except last, which
- is deleted below */
+ /* if library call, delete all insns. */
if ((temp = find_reg_note (m1->insn, REG_RETVAL,
NULL_RTX)))
- {
- for (temp = XEXP (temp, 0); temp != m1->insn;
- temp = NEXT_INSN (temp))
- delete_insn (temp);
- }
- delete_insn (m1->insn);
+ delete_insn_chain (XEXP (temp, 0), m1->insn);
+ else
+ delete_insn (m1->insn);
/* Any other movable that loads the same register
MUST be moved. */
/* The reg merged here is now invariant,
if the reg it matches is invariant. */
if (! m->partial)
- regs->array[m1->regno].set_in_loop = 0;
+ {
+ int i;
+ for (i = 0;
+ i < LOOP_REGNO_NREGS (regno, m1->set_dest);
+ i++)
+ regs->array[m1->regno+i].set_in_loop = 0;
+ }
}
}
else if (loop_dump_stream)
m_next = m->next;
free (m);
}
-}
+}
\f
#if 0
/* Scan X and replace the address of any MEM in it with ADDR.
replace_call_address (x, reg, addr)
rtx x, reg, addr;
{
- register enum rtx_code code;
- register int i;
- register const char *fmt;
+ enum rtx_code code;
+ int i;
+ const char *fmt;
if (x == 0)
return;
replace_call_address (XEXP (x, i), reg, addr);
else if (fmt[i] == 'E')
{
- register int j;
+ int j;
for (j = 0; j < XVECLEN (x, i); j++)
replace_call_address (XVECEXP (x, i, j), reg, addr);
}
const struct loop *loop;
rtx x;
{
- register enum rtx_code code;
- register int i;
- register const char *fmt;
+ enum rtx_code code;
+ int i;
+ const char *fmt;
int value;
if (x == 0)
value += count_nonfixed_reads (loop, XEXP (x, i));
if (fmt[i] == 'E')
{
- register int j;
+ int j;
for (j = 0; j < XVECLEN (x, i); j++)
value += count_nonfixed_reads (loop, XVECEXP (x, i, j));
}
prescan_loop (loop)
struct loop *loop;
{
- register int level = 1;
+ int level = 1;
rtx insn;
struct loop_info *loop_info = LOOP_INFO (loop);
rtx start = loop->start;
loop_info->num_mem_sets = 0;
- for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
+ for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
insn = PREV_INSN (insn))
{
if (GET_CODE (insn) == CALL_INSN)
for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
insn = NEXT_INSN (insn))
{
- if (GET_CODE (insn) == NOTE)
+ switch (GET_CODE (insn))
{
+ case NOTE:
if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
{
++level;
loop->level++;
}
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
- {
- --level;
- }
- }
- else if (GET_CODE (insn) == CALL_INSN)
- {
- if (! CONST_CALL_P (insn))
+ --level;
+ break;
+
+ case CALL_INSN:
+ if (! CONST_OR_PURE_CALL_P (insn))
{
loop_info->unknown_address_altered = 1;
loop_info->has_nonconst_call = 1;
}
+ else if (pure_call_p (insn))
+ loop_info->has_nonconst_call = 1;
loop_info->has_call = 1;
- }
- else if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
- {
- rtx label1 = NULL_RTX;
- rtx label2 = NULL_RTX;
+ if (can_throw_internal (insn))
+ loop_info->has_multiple_exit_targets = 1;
+ break;
+
+ case JUMP_INSN:
+ if (! loop_info->has_multiple_exit_targets)
+ {
+ rtx set = pc_set (insn);
+
+ if (set)
+ {
+ rtx src = SET_SRC (set);
+ rtx label1, label2;
+
+ if (GET_CODE (src) == IF_THEN_ELSE)
+ {
+ label1 = XEXP (src, 1);
+ label2 = XEXP (src, 2);
+ }
+ else
+ {
+ label1 = src;
+ label2 = NULL_RTX;
+ }
+
+ do
+ {
+ if (label1 && label1 != pc_rtx)
+ {
+ if (GET_CODE (label1) != LABEL_REF)
+ {
+ /* Something tricky. */
+ 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_info->has_multiple_exit_targets = 1;
+ break;
+ }
+ }
+
+ label1 = label2;
+ label2 = NULL_RTX;
+ }
+ while (label1);
+ }
+ else
+ {
+ /* A return, or something tricky. */
+ loop_info->has_multiple_exit_targets = 1;
+ }
+ }
+ /* FALLTHRU */
+ case INSN:
if (volatile_refs_p (PATTERN (insn)))
loop_info->has_volatile = 1;
if (! loop_info->first_loop_store_insn && loop_info->store_mems)
loop_info->first_loop_store_insn = insn;
- 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 (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
- {
- label1 = XEXP (SET_SRC (PATTERN (insn)), 1);
- label2 = XEXP (SET_SRC (PATTERN (insn)), 2);
- }
- else
- {
- label1 = SET_SRC (PATTERN (insn));
- }
-
- do
- {
- if (label1 && label1 != pc_rtx)
- {
- if (GET_CODE (label1) != LABEL_REF)
- {
- /* Something tricky. */
- 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_info->has_multiple_exit_targets = 1;
- break;
- }
- }
+ if (flag_non_call_exceptions && can_throw_internal (insn))
+ loop_info->has_multiple_exit_targets = 1;
+ break;
- label1 = label2;
- label2 = NULL_RTX;
- }
- while (label1);
- }
+ default:
+ break;
}
- else if (GET_CODE (insn) == RETURN)
- loop_info->has_multiple_exit_targets = 1;
}
/* Now, rescan the loop, setting up the LOOP_MEMS array. */
}
}
\f
+/* Invalidate all loops containing LABEL. */
+
+static void
+invalidate_loops_containing_label (label)
+ rtx label;
+{
+ struct loop *loop;
+ for (loop = uid_loop[INSN_UID (label)]; loop; loop = loop->outer)
+ loop->invalid = 1;
+}
+
/* Scan the function looking for loops. Record the start and end of each loop.
Also mark as invalid loops any loops that contain a setjmp or are branched
to from outside the loop. */
current_loop = next_loop;
break;
- case NOTE_INSN_SETJMP:
- /* In this case, we must invalidate our current loop and any
- enclosing loop. */
- for (loop = current_loop; loop; loop = loop->outer)
- {
- loop->invalid = 1;
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "\nLoop at %d ignored due to setjmp.\n",
- INSN_UID (loop->start));
- }
- break;
-
case NOTE_INSN_LOOP_CONT:
current_loop->cont = insn;
break;
break;
}
+ if (GET_CODE (insn) == CALL_INSN
+ && find_reg_note (insn, REG_SETJMP, NULL))
+ {
+ /* In this case, we must invalidate our current loop and any
+ enclosing loop. */
+ for (loop = current_loop; loop; loop = loop->outer)
+ {
+ loop->invalid = 1;
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "\nLoop at %d ignored due to setjmp.\n",
+ INSN_UID (loop->start));
+ }
+ }
+
/* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
enclosing loop, but this doesn't matter. */
uid_loop[INSN_UID (insn)] = current_loop;
/* 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))
- {
- for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
- loop; loop = loop->outer)
- loop->invalid = 1;
- }
+ invalidate_loops_containing_label (XEXP (label, 0));
/* 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))
- {
- for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
- loop; loop = loop->outer)
- loop->invalid = 1;
- }
+ for_each_eh_label (invalidate_loops_containing_label);
/* 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.
{
rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
if (note)
- {
- for (loop = uid_loop[INSN_UID (XEXP (note, 0))];
- loop; loop = loop->outer)
- loop->invalid = 1;
- }
+ invalidate_loops_containing_label (XEXP (note, 0));
}
if (GET_CODE (insn) != JUMP_INSN)
= JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
struct loop *target_loop = uid_loop[INSN_UID (target)];
rtx loc, loc2;
+ rtx tmp;
+
+ /* Search for possible garbage past the conditional jumps
+ and look for the last barrier. */
+ for (tmp = last_insn_to_move;
+ tmp && GET_CODE (tmp) != CODE_LABEL; tmp = NEXT_INSN (tmp))
+ if (GET_CODE (tmp) == BARRIER)
+ last_insn_to_move = tmp;
for (loc = target; loc; loc = PREV_INSN (loc))
if (GET_CODE (loc) == BARRIER
/* If no suitable BARRIER was found, create a suitable
one before TARGET. Since TARGET is a fall through
path, we'll need to insert an jump around our block
- and a add a BARRIER before TARGET.
+ and add a BARRIER before TARGET.
This creates an extra unconditional jump outside
the loop. However, the benefits of removing rarely
/* Include the BARRIER after INSN and copy the
block after LOC. */
- new_label = squeeze_notes (new_label,
- last_insn_to_move);
+ if (squeeze_notes (&new_label, &last_insn_to_move))
+ abort ();
reorder_insns (new_label, last_insn_to_move, loc);
/* All those insns are now in TARGET_LOOP. */
if (JUMP_LABEL (insn) != 0
&& (next_real_insn (JUMP_LABEL (insn))
== next_real_insn (insn)))
- delete_insn (insn);
+ delete_related_insns (insn);
}
/* Continue the loop after where the conditional
insn = NEXT_INSN (cond_label);
if (--LABEL_NUSES (cond_label) == 0)
- delete_insn (cond_label);
+ delete_related_insns (cond_label);
/* This loop will be continued with NEXT_INSN (insn). */
insn = PREV_INSN (insn);
int
loop_invariant_p (loop, x)
const struct loop *loop;
- register rtx x;
+ rtx x;
{
struct loop_info *loop_info = LOOP_INFO (loop);
struct loop_regs *regs = LOOP_REGS (loop);
- register int i;
- register enum rtx_code code;
- register const char *fmt;
+ int i;
+ enum rtx_code code;
+ const char *fmt;
int conditional = 0;
rtx mem_list_entry;
since the reg might be set by initialization within the loop. */
if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
- || x == arg_pointer_rtx)
+ || x == arg_pointer_rtx || x == pic_offset_table_rtx)
&& ! current_function_has_nonlocal_goto)
return 1;
}
else if (fmt[i] == 'E')
{
- register int j;
+ int j;
for (j = 0; j < XVECLEN (x, i); j++)
{
int tem = loop_invariant_p (loop, XVECEXP (x, i, j));
while (count > 0)
{
- register enum rtx_code code;
+ enum rtx_code code;
rtx set;
p = NEXT_INSN (p);
rtx reg, insn;
short *table;
{
- register rtx p = insn;
- register int regno = REGNO (reg);
+ rtx p = insn;
+ int regno = REGNO (reg);
while (1)
{
- register enum rtx_code code;
+ enum rtx_code code;
p = NEXT_INSN (p);
code = GET_CODE (p);
if (code == CODE_LABEL || code == JUMP_INSN)
dest = XEXP (dest, 0);
if (GET_CODE (dest) == REG)
{
- register int regno = REGNO (dest);
- /* If this is the first setting of this reg
- in current basic block, and it was set before,
- it must be set in two basic blocks, so it cannot
- be moved out of the loop. */
- if (regs->array[regno].set_in_loop > 0
- && last_set == 0)
- regs->array[regno].may_not_optimize = 1;
- /* If this is not first setting in current basic block,
- see if reg was used in between previous one and this.
- If so, neither one can be moved. */
- if (last_set[regno] != 0
- && reg_used_between_p (dest, last_set[regno], insn))
- regs->array[regno].may_not_optimize = 1;
- if (regs->array[regno].set_in_loop < 127)
- ++regs->array[regno].set_in_loop;
- last_set[regno] = insn;
- }
- }
-}
-
-/* Increment REGS->array[I].SET_IN_LOOP at the index I of each
- register that is modified by an insn between FROM and TO. If the
- value of an element of REGS->array[I].SET_IN_LOOP becomes 127 or
- more, stop incrementing it, to avoid overflow.
-
- Store in REGS->array[I].SINGLE_USAGE[I] the single insn in which
- register I is used, if it is only used once. Otherwise, it is set
- to 0 (for no uses) or const0_rtx for more than one use. This
- parameter may be zero, in which case this processing is not done.
-
- Store in *COUNT_PTR the number of actual instruction
- in the loop. We use this to decide what is worth moving out. */
-
-/* last_set[n] is nonzero iff reg n has been set in the current basic block.
- In that case, it is the insn that last set reg n. */
-
-static void
-count_loop_regs_set (loop, count_ptr)
- const struct loop *loop;
- int *count_ptr;
-{
- struct loop_regs *regs = LOOP_REGS (loop);
- register rtx *last_set = (rtx *) xcalloc (regs->num, sizeof (rtx));
- register rtx insn;
- register int count = 0;
-
- for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
- insn = NEXT_INSN (insn))
- {
- if (INSN_P (insn))
- {
- ++count;
-
- /* Record registers that have exactly one use. */
- find_single_use_in_loop (regs, insn, PATTERN (insn));
-
- /* Include uses in REG_EQUAL notes. */
- if (REG_NOTES (insn))
- find_single_use_in_loop (regs, insn, REG_NOTES (insn));
-
- if (GET_CODE (PATTERN (insn)) == SET
- || GET_CODE (PATTERN (insn)) == CLOBBER)
- count_one_set (regs, insn, PATTERN (insn), last_set);
- else if (GET_CODE (PATTERN (insn)) == PARALLEL)
+ int i;
+ int regno = REGNO (dest);
+ for (i = 0; i < LOOP_REGNO_NREGS (regno, dest); i++)
{
- register int i;
- for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
- count_one_set (regs, insn, XVECEXP (PATTERN (insn), 0, i),
- last_set);
+ /* If this is the first setting of this reg
+ in current basic block, and it was set before,
+ it must be set in two basic blocks, so it cannot
+ be moved out of the loop. */
+ if (regs->array[regno].set_in_loop > 0
+ && last_set == 0)
+ regs->array[regno+i].may_not_optimize = 1;
+ /* If this is not first setting in current basic block,
+ see if reg was used in between previous one and this.
+ If so, neither one can be moved. */
+ if (last_set[regno] != 0
+ && reg_used_between_p (dest, last_set[regno], insn))
+ regs->array[regno+i].may_not_optimize = 1;
+ if (regs->array[regno+i].set_in_loop < 127)
+ ++regs->array[regno+i].set_in_loop;
+ last_set[regno+i] = insn;
}
}
-
- if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
- memset ((char *) last_set, 0, regs->num * sizeof (rtx));
}
- *count_ptr = count;
-
- /* Clean up. */
- free (last_set);
}
\f
/* Given a loop that is bounded by LOOP->START and LOOP->END and that
return 0;
}
\f
-/* A "basic induction variable" or biv is a pseudo reg that is set
+
+/* Information we collect about arrays that we might want to prefetch. */
+struct prefetch_info
+{
+ struct iv_class *class; /* Class this prefetch is based on. */
+ struct induction *giv; /* GIV this prefetch is based on. */
+ rtx base_address; /* Start prefetching from this address plus
+ index. */
+ HOST_WIDE_INT index;
+ HOST_WIDE_INT stride; /* Prefetch stride in bytes in each
+ iteration. */
+ unsigned int bytes_accesed; /* Sum of sizes of all acceses to this
+ prefetch area in one iteration. */
+ unsigned int total_bytes; /* Total bytes loop will access in this block.
+ This is set only for loops with known
+ iteration counts and is 0xffffffff
+ otherwise. */
+ unsigned int write : 1; /* 1 for read/write prefetches. */
+ unsigned int prefetch_in_loop : 1;
+ /* 1 for those chosen for prefetching. */
+ unsigned int prefetch_before_loop : 1;
+ /* 1 for those chosen for prefetching. */
+};
+
+/* Data used by check_store function. */
+struct check_store_data
+{
+ rtx mem_address;
+ int mem_write;
+};
+
+static void check_store PARAMS ((rtx, rtx, void *));
+static void emit_prefetch_instructions PARAMS ((struct loop *));
+static int rtx_equal_for_prefetch_p PARAMS ((rtx, rtx));
+
+/* Set mem_write when mem_address is found. Used as callback to
+ note_stores. */
+static void
+check_store (x, pat, data)
+ rtx x, pat ATTRIBUTE_UNUSED;
+ void *data;
+{
+ struct check_store_data *d = (struct check_store_data *) data;
+
+ if ((GET_CODE (x) == MEM) && rtx_equal_p (d->mem_address, XEXP (x, 0)))
+ d->mem_write = 1;
+}
+\f
+/* Like rtx_equal_p, but attempts to swap commutative operands. This is
+ important to get some addresses combined. Later more sophisticated
+ transformations can be added when necesary.
+
+ ??? Same trick with swapping operand is done at several other places.
+ It can be nice to develop some common way to handle this. */
+
+static int
+rtx_equal_for_prefetch_p (x, y)
+ rtx x, y;
+{
+ int i;
+ int j;
+ enum rtx_code code = GET_CODE (x);
+ const char *fmt;
+
+ if (x == y)
+ return 1;
+ if (code != GET_CODE (y))
+ return 0;
+
+ code = GET_CODE (x);
+
+ if (GET_RTX_CLASS (code) == 'c')
+ {
+ return ((rtx_equal_for_prefetch_p (XEXP (x, 0), XEXP (y, 0))
+ && rtx_equal_for_prefetch_p (XEXP (x, 1), XEXP (y, 1)))
+ || (rtx_equal_for_prefetch_p (XEXP (x, 0), XEXP (y, 1))
+ && rtx_equal_for_prefetch_p (XEXP (x, 1), XEXP (y, 0))));
+ }
+ /* Compare the elements. If any pair of corresponding elements fails to
+ match, return 0 for the whole thing. */
+
+ fmt = GET_RTX_FORMAT (code);
+ for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+ {
+ switch (fmt[i])
+ {
+ case 'w':
+ if (XWINT (x, i) != XWINT (y, i))
+ return 0;
+ break;
+
+ case 'i':
+ if (XINT (x, i) != XINT (y, i))
+ return 0;
+ break;
+
+ case 'E':
+ /* Two vectors must have the same length. */
+ if (XVECLEN (x, i) != XVECLEN (y, i))
+ return 0;
+
+ /* And the corresponding elements must match. */
+ for (j = 0; j < XVECLEN (x, i); j++)
+ if (rtx_equal_for_prefetch_p (XVECEXP (x, i, j),
+ XVECEXP (y, i, j)) == 0)
+ return 0;
+ break;
+
+ case 'e':
+ if (rtx_equal_for_prefetch_p (XEXP (x, i), XEXP (y, i)) == 0)
+ return 0;
+ break;
+
+ case 's':
+ if (strcmp (XSTR (x, i), XSTR (y, i)))
+ return 0;
+ break;
+
+ case 'u':
+ /* These are just backpointers, so they don't matter. */
+ break;
+
+ case '0':
+ break;
+
+ /* It is believed that rtx's at this level will never
+ contain anything but integers and other rtx's,
+ except for within LABEL_REFs and SYMBOL_REFs. */
+ default:
+ abort ();
+ }
+ }
+ return 1;
+}
+\f
+/* Remove constant addition value from the expression X (when present)
+ and return it. */
+
+static HOST_WIDE_INT
+remove_constant_addition (x)
+ rtx *x;
+{
+ HOST_WIDE_INT addval = 0;
+ rtx exp = *x;
+
+ /* Avoid clobbering a shared CONST expression. */
+ if (GET_CODE (exp) == CONST)
+ {
+ if (GET_CODE (XEXP (exp, 0)) == PLUS
+ && GET_CODE (XEXP (XEXP (exp, 0), 0)) == SYMBOL_REF
+ && GET_CODE (XEXP (XEXP (exp, 0), 1)) == CONST_INT)
+ {
+ *x = XEXP (XEXP (exp, 0), 0);
+ return INTVAL (XEXP (XEXP (exp, 0), 1));
+ }
+ return 0;
+ }
+
+ if (GET_CODE (exp) == CONST_INT)
+ {
+ addval = INTVAL (exp);
+ *x = const0_rtx;
+ }
+
+ /* For plus expression recurse on ourself. */
+ else if (GET_CODE (exp) == PLUS)
+ {
+ addval += remove_constant_addition (&XEXP (exp, 0));
+ addval += remove_constant_addition (&XEXP (exp, 1));
+
+ /* In case our parameter was constant, remove extra zero from the
+ expression. */
+ if (XEXP (exp, 0) == const0_rtx)
+ *x = XEXP (exp, 1);
+ else if (XEXP (exp, 1) == const0_rtx)
+ *x = XEXP (exp, 0);
+ }
+
+ return addval;
+}
+
+/* Attempt to identify accesses to arrays that are most likely to cause cache
+ misses, and emit prefetch instructions a few prefetch blocks forward.
+
+ To detect the arrays we use the GIV information that was collected by the
+ strength reduction pass.
+
+ The prefetch instructions are generated after the GIV information is done
+ and before the strength reduction process. The new GIVs are injected into
+ the strength reduction tables, so the prefetch addresses are optimized as
+ well.
+
+ GIVs are split into base address, stride, and constant addition values.
+ GIVs with the same address, stride and close addition values are combined
+ into a single prefetch. Also writes to GIVs are detected, so that prefetch
+ for write instructions can be used for the block we write to, on machines
+ that support write prefetches.
+
+ Several heuristics are used to determine when to prefetch. They are
+ controlled by defined symbols that can be overridden for each target. */
+
+static void
+emit_prefetch_instructions (loop)
+ struct loop *loop;
+{
+ int num_prefetches = 0;
+ int num_real_prefetches = 0;
+ int num_real_write_prefetches = 0;
+ int ahead;
+ int i;
+ struct iv_class *bl;
+ struct induction *iv;
+ struct prefetch_info info[MAX_PREFETCHES];
+ struct loop_ivs *ivs = LOOP_IVS (loop);
+
+ if (!HAVE_prefetch)
+ return;
+
+ /* Consider only loops w/o calls. When a call is done, the loop is probably
+ slow enough to read the memory. */
+ if (PREFETCH_NO_CALL && LOOP_INFO (loop)->has_call)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream, "Prefetch: ignoring loop - has call.\n");
+
+ return;
+ }
+
+ if (PREFETCH_NO_LOW_LOOPCNT
+ && LOOP_INFO (loop)->n_iterations
+ && LOOP_INFO (loop)->n_iterations <= PREFETCH_LOW_LOOPCNT)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Prefetch: ignoring loop - not enought iterations.\n");
+ return;
+ }
+
+ /* Search all induction variables and pick those interesting for the prefetch
+ machinery. */
+ for (bl = ivs->list; bl; bl = bl->next)
+ {
+ struct induction *biv = bl->biv, *biv1;
+ int basestride = 0;
+
+ biv1 = biv;
+
+ /* Expect all BIVs to be executed in each iteration. This makes our
+ analysis more conservative. */
+ while (biv1)
+ {
+ /* Discard non-constant additions that we can't handle well yet, and
+ BIVs that are executed multiple times; such BIVs ought to be
+ handled in the nested loop. We accept not_every_iteration BIVs,
+ since these only result in larger strides and make our
+ heuristics more conservative.
+ ??? What does the last sentence mean? */
+ if (GET_CODE (biv->add_val) != CONST_INT)
+ {
+ if (loop_dump_stream)
+ {
+ fprintf (loop_dump_stream,
+ "Prefetch: biv %i ignored: non-constant addition at insn %i:",
+ REGNO (biv->src_reg), INSN_UID (biv->insn));
+ print_rtl (loop_dump_stream, biv->add_val);
+ fprintf (loop_dump_stream, "\n");
+ }
+ break;
+ }
+
+ if (biv->maybe_multiple)
+ {
+ if (loop_dump_stream)
+ {
+ fprintf (loop_dump_stream,
+ "Prefetch: biv %i ignored: maybe_multiple at insn %i:",
+ REGNO (biv->src_reg), INSN_UID (biv->insn));
+ print_rtl (loop_dump_stream, biv->add_val);
+ fprintf (loop_dump_stream, "\n");
+ }
+ break;
+ }
+
+ basestride += INTVAL (biv1->add_val);
+ biv1 = biv1->next_iv;
+ }
+
+ if (biv1 || !basestride)
+ continue;
+
+ for (iv = bl->giv; iv; iv = iv->next_iv)
+ {
+ rtx address;
+ rtx temp;
+ HOST_WIDE_INT index = 0;
+ int add = 1;
+ HOST_WIDE_INT stride;
+ struct check_store_data d;
+ int size = GET_MODE_SIZE (GET_MODE (iv));
+
+ /* There are several reasons why an induction variable is not
+ interesting to us. */
+ if (iv->giv_type != DEST_ADDR
+ /* We are interested only in constant stride memory references
+ in order to be able to compute density easily. */
+ || GET_CODE (iv->mult_val) != CONST_INT
+ /* Don't handle reversed order prefetches, since they are usually
+ ineffective. Later we may be able to reverse such BIVs. */
+ || (PREFETCH_NO_REVERSE_ORDER
+ && (stride = INTVAL (iv->mult_val) * basestride) < 0)
+ /* Prefetching of accesses with such an extreme stride is probably
+ not worthwhile, either. */
+ || (PREFETCH_NO_EXTREME_STRIDE
+ && stride > PREFETCH_EXTREME_STRIDE)
+ /* Ignore GIVs with varying add values; we can't predict the
+ value for the next iteration. */
+ || !loop_invariant_p (loop, iv->add_val)
+ /* Ignore GIVs in the nested loops; they ought to have been
+ handled already. */
+ || iv->maybe_multiple)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream, "Prefetch: Ignoring giv at %i\n",
+ INSN_UID (iv->insn));
+ continue;
+ }
+
+ /* Determine the pointer to the basic array we are examining. It is
+ the sum of the BIV's initial value and the GIV's add_val. */
+ index = 0;
+
+ address = copy_rtx (iv->add_val);
+ temp = copy_rtx (bl->initial_value);
+
+ address = simplify_gen_binary (PLUS, Pmode, temp, address);
+ index = remove_constant_addition (&address);
+
+ index += size;
+ d.mem_write = 0;
+ d.mem_address = *iv->location;
+
+ /* When the GIV is not always executed, we might be better off by
+ not dirtying the cache pages. */
+ if (PREFETCH_NOT_ALWAYS || iv->always_executed)
+ note_stores (PATTERN (iv->insn), check_store, &d);
+
+ /* Attempt to find another prefetch to the same array and see if we
+ can merge this one. */
+ for (i = 0; i < num_prefetches; i++)
+ if (rtx_equal_for_prefetch_p (address, info[i].base_address)
+ && stride == info[i].stride)
+ {
+ /* In case both access same array (same location
+ just with small difference in constant indexes), merge
+ the prefetches. Just do the later and the earlier will
+ get prefetched from previous iteration.
+ 4096 is artificial threshold. It should not be too small,
+ but also not bigger than small portion of memory usually
+ traversed by single loop. */
+ if (index >= info[i].index && index - info[i].index < 4096)
+ {
+ info[i].write |= d.mem_write;
+ info[i].bytes_accesed += size;
+ info[i].index = index;
+ info[i].giv = iv;
+ info[i].class = bl;
+ info[num_prefetches].base_address = address;
+ add = 0;
+ break;
+ }
+
+ if (index < info[i].index && info[i].index - index < 4096)
+ {
+ info[i].write |= d.mem_write;
+ info[i].bytes_accesed += size;
+ add = 0;
+ break;
+ }
+ }
+
+ /* Merging failed. */
+ if (add)
+ {
+ info[num_prefetches].giv = iv;
+ info[num_prefetches].class = bl;
+ info[num_prefetches].index = index;
+ info[num_prefetches].stride = stride;
+ info[num_prefetches].base_address = address;
+ info[num_prefetches].write = d.mem_write;
+ info[num_prefetches].bytes_accesed = size;
+ num_prefetches++;
+ if (num_prefetches >= MAX_PREFETCHES)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ "Maximal number of prefetches exceeded.\n");
+ return;
+ }
+ }
+ }
+ }
+
+ for (i = 0; i < num_prefetches; i++)
+ {
+ /* Attempt to calculate the number of bytes fetched by the loop.
+ Avoid overflow. */
+ if (LOOP_INFO (loop)->n_iterations
+ && ((unsigned HOST_WIDE_INT) (0xffffffff / info[i].stride)
+ >= LOOP_INFO (loop)->n_iterations))
+ info[i].total_bytes = info[i].stride * LOOP_INFO (loop)->n_iterations;
+ else
+ info[i].total_bytes = 0xffffffff;
+
+ /* Prefetch is worthwhile only when the loads/stores are dense. */
+ if (PREFETCH_ONLY_DENSE_MEM
+ && info[i].bytes_accesed * 256 / info[i].stride > PREFETCH_DENSE_MEM
+ && (info[i].total_bytes / PREFETCH_BLOCK
+ >= PREFETCH_BLOCKS_BEFORE_LOOP_MIN))
+ {
+ info[i].prefetch_before_loop = 1;
+ info[i].prefetch_in_loop
+ = (info[i].total_bytes / PREFETCH_BLOCK
+ > PREFETCH_BLOCKS_BEFORE_LOOP_MAX);
+ }
+ else
+ info[i].prefetch_in_loop = 0, info[i].prefetch_before_loop = 0;
+
+ if (info[i].prefetch_in_loop)
+ {
+ num_real_prefetches += ((info[i].stride + PREFETCH_BLOCK - 1)
+ / PREFETCH_BLOCK);
+ if (info[i].write)
+ num_real_write_prefetches
+ += (info[i].stride + PREFETCH_BLOCK - 1) / PREFETCH_BLOCK;
+ }
+ }
+
+ if (loop_dump_stream)
+ {
+ for (i = 0; i < num_prefetches; i++)
+ {
+ fprintf (loop_dump_stream, "Prefetch insn %i address: ",
+ INSN_UID (info[i].giv->insn));
+ print_rtl (loop_dump_stream, info[i].base_address);
+ fprintf (loop_dump_stream, " Index: ");
+ fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, info[i].index);
+ fprintf (loop_dump_stream, " stride: ");
+ fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, info[i].stride);
+ fprintf (loop_dump_stream,
+ " density: %i%% total_bytes: %u%sin loop: %s before: %s\n",
+ (int) (info[i].bytes_accesed * 100 / info[i].stride),
+ info[i].total_bytes,
+ info[i].write ? " read/write " : " read only ",
+ info[i].prefetch_in_loop ? "yes" : "no",
+ info[i].prefetch_before_loop ? "yes" : "no");
+ }
+
+ fprintf (loop_dump_stream, "Real prefetches needed: %i (write: %i)\n",
+ num_real_prefetches, num_real_write_prefetches);
+ }
+
+ if (!num_real_prefetches)
+ return;
+
+ ahead = SIMULTANEOUS_PREFETCHES / num_real_prefetches;
+
+ if (!ahead)
+ return;
+
+ for (i = 0; i < num_prefetches; i++)
+ {
+ if (info[i].prefetch_in_loop)
+ {
+ int y;
+
+ for (y = 0; y < ((info[i].stride + PREFETCH_BLOCK - 1)
+ / PREFETCH_BLOCK); y++)
+ {
+ rtx loc = copy_rtx (*info[i].giv->location);
+ rtx insn;
+ int bytes_ahead = PREFETCH_BLOCK * (ahead + y);
+ rtx before_insn = info[i].giv->insn;
+ rtx prev_insn = PREV_INSN (info[i].giv->insn);
+
+ /* We can save some effort by offsetting the address on
+ architectures with offsettable memory references. */
+ if (offsettable_address_p (0, VOIDmode, loc))
+ loc = plus_constant (loc, bytes_ahead);
+ else
+ {
+ rtx reg = gen_reg_rtx (Pmode);
+ loop_iv_add_mult_emit_before (loop, loc, const1_rtx,
+ GEN_INT (bytes_ahead), reg,
+ 0, before_insn);
+ loc = reg;
+ }
+
+ /* Make sure the address operand is valid for prefetch. */
+ if (! (*insn_data[(int)CODE_FOR_prefetch].operand[0].predicate)
+ (loc,
+ insn_data[(int)CODE_FOR_prefetch].operand[0].mode))
+ loc = force_reg (Pmode, loc);
+ emit_insn_before (gen_prefetch (loc, GEN_INT (info[i].write),
+ GEN_INT (3)),
+ before_insn);
+
+ /* Check all insns emitted and record the new GIV
+ information. */
+ insn = NEXT_INSN (prev_insn);
+ while (insn != before_insn)
+ {
+ insn = check_insn_for_givs (loop, insn,
+ info[i].giv->always_executed,
+ info[i].giv->maybe_multiple);
+ insn = NEXT_INSN (insn);
+ }
+ }
+ }
+
+ if (info[i].prefetch_before_loop)
+ {
+ int y;
+
+ /* Emit INSNs before the loop to fetch the first cache lines. */
+ for (y = 0;
+ (!info[i].prefetch_in_loop || y < ahead)
+ && y * PREFETCH_BLOCK < (int) info[i].total_bytes; y ++)
+ {
+ rtx reg = gen_reg_rtx (Pmode);
+ rtx loop_start = loop->start;
+ rtx add_val = simplify_gen_binary (PLUS, Pmode,
+ info[i].giv->add_val,
+ GEN_INT (y * PREFETCH_BLOCK));
+
+ loop_iv_add_mult_emit_before (loop, info[i].class->initial_value,
+ info[i].giv->mult_val,
+ add_val, reg, 0, loop_start);
+ emit_insn_before (gen_prefetch (reg, GEN_INT (info[i].write),
+ GEN_INT (3)),
+ loop_start);
+ }
+ }
+ }
+
+ return;
+}
+\f
+/* A "basic induction variable" or biv is a pseudo reg that is set
(within this loop) only by incrementing or decrementing it. */
/* A "general induction variable" or giv is a pseudo reg whose
value is a linear function of a biv. */
ivs->list = 0;
for_each_insn_in_loop (loop, check_insn_for_bivs);
-
+
/* Scan ivs->list to remove all regs that proved not to be bivs.
Make a sanity check against regs->n_times_set. */
for (backbl = &ivs->list, bl = *backbl; bl; bl = bl->next)
|| ! bl->incremented)
{
if (loop_dump_stream)
- fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
+ fprintf (loop_dump_stream, "Biv %d: discarded, %s\n",
bl->regno,
(REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
? "not induction variable"
backbl = &bl->next;
if (loop_dump_stream)
- fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
+ fprintf (loop_dump_stream, "Biv %d: verified\n", bl->regno);
}
}
}
if (loop_dump_stream)
fprintf (loop_dump_stream,
- "Biv %d initialized at insn %d: initial value ",
+ "Biv %d: initialized at insn %d: initial value ",
bl->regno, INSN_UID (bl->init_insn));
if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
|| GET_MODE (src) == VOIDmode)
- && valid_initial_value_p (src, bl->init_insn,
- LOOP_INFO (loop)->pre_header_has_call,
+ && valid_initial_value_p (src, bl->init_insn,
+ LOOP_INFO (loop)->pre_header_has_call,
loop->start))
{
bl->initial_value = src;
if (loop_dump_stream)
{
- if (GET_CODE (src) == CONST_INT)
- {
- fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
- INTVAL (src));
- fputc ('\n', loop_dump_stream);
- }
- else
- {
- print_rtl (loop_dump_stream, src);
- fprintf (loop_dump_stream, "\n");
- }
+ print_simple_rtl (loop_dump_stream, src);
+ fputc ('\n', loop_dump_stream);
}
}
/* If we can't make it a giv,
/* For each giv for which we still don't know whether or not it is
replaceable, check to see if it is replaceable because its final value
- can be calculated. */
+ can be calculated. */
static void
loop_givs_check (loop)
loop->start since these won't be affected by the value of the biv
elsewhere in the function, so long as init_insn doesn't use the
biv itself. */
-
+
if ((REGNO_LAST_LUID (bl->regno) < INSN_LUID (loop->end)
&& bl->init_insn
&& INSN_UID (bl->init_insn) < max_uid_for_loop
&& ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
|| (bl->final_value = final_biv_value (loop, bl)))
return maybe_eliminate_biv (loop, bl, 0, threshold, insn_count);
-
+
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
if (! v->ignore && v->same == 0)
{
int auto_inc_opt = 0;
-
+
/* 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);
-
+
#ifdef AUTO_INC_DEC
/* If the target has auto-increment addressing modes, and
this is an address giv, then try to put the increment
/* 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
if (v->combined_with)
{
struct induction *other_giv = 0;
-
+
for (tv = bl->giv; tv; tv = tv->next_iv)
if (tv->same == v)
{
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 = 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, insert_before);
+ loop_iv_add_mult_emit_before (loop, tv->add_val, v->mult_val,
+ v->new_reg, v->new_reg,
+ 0, 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, insert_before);
+ loop_iv_add_mult_emit_before (loop, tv->add_val, v->mult_val,
+ v->add_val, v->new_reg,
+ 0, insert_before);
}
-
+
/* Add code at loop start to initialize giv's reduced reg. */
-
- emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
- v->mult_val, v->add_val, v->new_reg,
- loop->start);
+
+ loop_iv_add_mult_hoist (loop,
+ extend_value_for_giv (v, bl->initial_value),
+ v->mult_val, v->add_val, v->new_reg);
}
}
}
if (v->ignore
|| (v->same && v->same->ignore))
continue;
-
+
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;
static void
-loop_givs_rescan (loop, bl, reg_map, end_insert_before)
+loop_givs_rescan (loop, bl, reg_map)
struct loop *loop;
struct iv_class *bl;
rtx *reg_map;
- rtx end_insert_before;
{
struct induction *v;
{
if (v->same && v->same->ignore)
v->ignore = 1;
-
+
if (v->ignore)
continue;
-
+
/* Update expression if this was combined, in case other giv was
replaced. */
if (v->same)
v->new_reg = replace_rtx (v->new_reg,
v->same->dest_reg, v->same->new_reg);
-
+
/* See if this register is known to be a pointer to something. If
so, see if we can find the alignment. First see if there is a
destination register that is a pointer. If so, this shares the
&& REG_POINTER (v->src_reg))
{
unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->src_reg));
-
+
if (align == 0
|| GET_CODE (v->add_val) != CONST_INT
|| INTVAL (v->add_val) % (align / BITS_PER_UNIT) != 0)
align = 0;
-
+
mark_reg_pointer (v->new_reg, align);
}
else if (GET_CODE (v->new_reg) == REG
&& REG_POINTER (v->add_val))
{
unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->add_val));
-
+
if (align == 0 || GET_CODE (v->mult_val) != CONST_INT
|| INTVAL (v->mult_val) % (align / BITS_PER_UNIT) != 0)
align = 0;
-
+
mark_reg_pointer (v->new_reg, align);
}
else if (GET_CODE (v->new_reg) == REG && v->giv_type == DEST_ADDR)
mark_reg_pointer (v->new_reg, 0);
-
+
if (v->giv_type == DEST_ADDR)
/* Store reduced reg as the address in the memref where we found
this giv. */
{
/* Not replaceable; emit an insn to set the original giv reg from
the reduced giv, same as above. */
- emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
- v->insn);
+ loop_insn_emit_after (loop, 0, v->insn,
+ gen_move_insn (v->dest_reg, v->new_reg));
}
-
+
/* When a loop is reversed, givs which depend on the reversed
biv, and which are live outside the loop, must be set to their
correct final value. This insn is only needed if the giv is
not replaceable. The correct final value is the same as the
value that the giv starts the reversed loop with. */
if (bl->reversed && ! v->replaceable)
- emit_iv_add_mult (extend_value_for_giv (v, bl->initial_value),
- v->mult_val, v->add_val, v->dest_reg,
- end_insert_before);
+ loop_iv_add_mult_sink (loop,
+ extend_value_for_giv (v, bl->initial_value),
+ v->mult_val, v->add_val, v->dest_reg);
else if (v->final_value)
- {
- rtx insert_before;
-
- /* If the loop has multiple exits, emit the insn before the
- 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->exit_count)
- insert_before = loop->start;
- else
- insert_before = end_insert_before;
- emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
- insert_before);
- }
-
+ loop_insn_sink_or_swim (loop,
+ gen_load_of_final_value (v->dest_reg,
+ v->final_value));
+
if (loop_dump_stream)
{
fprintf (loop_dump_stream, "giv at %d reduced to ",
INSN_UID (v->insn));
- print_rtl (loop_dump_stream, v->new_reg);
+ print_simple_rtl (loop_dump_stream, v->new_reg);
fprintf (loop_dump_stream, "\n");
}
}
PUT_MODE (test_reg, v->mode);
add_cost = iv_add_mult_cost (bl->biv->add_val, v->mult_val,
test_reg, test_reg);
-
+
/* Reduce benefit if not replaceable, since we will insert a
move-insn to replace the insn that calculates this giv. Don't do
this unless the giv is a user variable, since it will often be
if (! v->replaceable && ! bl->eliminable
&& REG_USERVAR_P (v->dest_reg))
benefit -= copy_cost;
-
+
/* Decrease the benefit to count the add-insns that we will insert
to increment the reduced reg for the giv. ??? This can
overestimate the run-time cost of the additional insns, e.g. if
&& benefit > 0
&& GET_CODE (v->mult_val) == CONST_INT)
{
+ int size = GET_MODE_SIZE (GET_MODE (v->mem));
+
if (HAVE_POST_INCREMENT
- && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
+ && INTVAL (v->mult_val) == size)
benefit += add_cost * bl->biv_count;
else if (HAVE_PRE_INCREMENT
- && INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
+ && INTVAL (v->mult_val) == size)
benefit += add_cost * bl->biv_count;
else if (HAVE_POST_DECREMENT
- && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
+ && -INTVAL (v->mult_val) == size)
benefit += add_cost * bl->biv_count;
else if (HAVE_PRE_DECREMENT
- && -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
+ && -INTVAL (v->mult_val) == size)
benefit += add_cost * bl->biv_count;
}
#endif
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *iv = ivs->list;
-
+
free (ivs->regs);
while (iv)
struct iv_class *next = iv->next;
struct induction *induction;
struct induction *next_induction;
-
+
for (induction = iv->biv; induction; induction = next_induction)
{
next_induction = induction->next_iv;
next_induction = induction->next_iv;
free (induction);
}
-
+
free (iv);
iv = next;
}
must check regnos to make sure they are in bounds. */
static void
-strength_reduce (loop, insn_count, flags)
+strength_reduce (loop, flags)
struct loop *loop;
- int insn_count;
int flags;
{
struct loop_info *loop_info = LOOP_INFO (loop);
/* Map of pseudo-register replacements. */
rtx *reg_map = NULL;
int reg_map_size;
- rtx end_insert_before;
int unrolled_insn_copies = 0;
rtx test_reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
+ int insn_count = count_insns_in_loop (loop);
addr_placeholder = gen_reg_rtx (Pmode);
- /* 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).
-
- 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);
-
ivs->n_regs = max_reg_before_loop;
ivs->regs = (struct iv *) xcalloc (ivs->n_regs, sizeof (struct iv));
/* Can still unroll the loop anyways, but indicate that there is no
strength reduction info available. */
if (flags & LOOP_UNROLL)
- unroll_loop (loop, insn_count, end_insert_before, 0);
+ unroll_loop (loop, insn_count, 0);
loop_ivs_free (loop);
return;
fail if the iteration variable is a giv. */
loop_iterations (loop);
+#ifdef HAVE_prefetch
+ if (flags & LOOP_PREFETCH)
+ emit_prefetch_instructions (loop);
+#endif
+
/* Now for each giv for which we still don't know whether or not it is
replaceable, check to see if it is replaceable because its final value
can be calculated. This must be done after loop_iterations is called,
{
struct induction *v;
int benefit;
-
+
/* Test whether it will be possible to eliminate this biv
provided all givs are reduced. */
bl->eliminable = loop_biv_eliminable_p (loop, bl, threshold, insn_count);
+ /* This will be true at the end, if all givs which depend on this
+ biv have been strength reduced.
+ We can't (currently) eliminate the biv unless this is so. */
+ bl->all_reduced = 1;
+
/* Check each extension dependent giv in this class to see if its
root biv is safe from wrapping in the interior mode. */
- check_ext_dependant_givs (bl, loop_info);
+ check_ext_dependent_givs (bl, loop_info);
/* Combine all giv's for this iv_class. */
combine_givs (regs, bl);
- /* This will be true at the end, if all givs which depend on this
- biv have been strength reduced.
- We can't (currently) eliminate the biv unless this is so. */
- bl->all_reduced = 1;
-
for (v = bl->giv; v; v = v->next_iv)
{
struct induction *tv;
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". */
- loop_givs_rescan (loop, bl, reg_map, end_insert_before);
+ loop_givs_rescan (loop, bl, reg_map);
/* All the givs based on the biv bl have been reduced if they
merit it. */
value, so we don't need another one. We can't calculate the
proper final value for such a biv here anyways. */
if (bl->final_value && ! bl->reversed)
- {
- rtx insert_before;
-
- /* If the loop has multiple exits, emit the insn before the
- 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->exit_count)
- insert_before = loop->start;
- else
- insert_before = end_insert_before;
-
- emit_insn_before (gen_move_insn (bl->biv->dest_reg,
- bl->final_value),
- end_insert_before);
- }
+ loop_insn_sink_or_swim (loop,
+ gen_load_of_final_value (bl->biv->dest_reg,
+ bl->final_value));
if (loop_dump_stream)
fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
bl->regno);
}
+ /* See above note wrt final_value. But since we couldn't eliminate
+ the biv, we must set the value after the loop instead of before. */
+ else if (bl->final_value && ! bl->reversed)
+ loop_insn_sink (loop, gen_load_of_final_value (bl->biv->dest_reg,
+ bl->final_value));
}
/* Go through all the instructions in the loop, making all the
collected. Always unroll loops that would be as small or smaller
unrolled than when rolled. */
if ((flags & LOOP_UNROLL)
- || (loop_info->n_iterations > 0
+ || (!(flags & LOOP_FIRST_PASS)
+ && loop_info->n_iterations > 0
&& unrolled_insn_copies <= insn_count))
- unroll_loop (loop, insn_count, end_insert_before, 1);
+ unroll_loop (loop, insn_count, 1);
#ifdef HAVE_doloop_end
if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg)
doloop_optimize (loop);
#endif /* HAVE_doloop_end */
+ /* In case number of iterations is known, drop branch prediction note
+ in the branch. Do that only in second loop pass, as loop unrolling
+ may change the number of iterations performed. */
+ if (flags & LOOP_BCT)
+ {
+ unsigned HOST_WIDE_INT n
+ = loop_info->n_iterations / loop_info->unroll_number;
+ if (n > 1)
+ predict_insn (PREV_INSN (loop->end), PRED_LOOP_ITERATIONS,
+ REG_BR_PROB_BASE - REG_BR_PROB_BASE / n);
+ }
+
if (loop_dump_stream)
fprintf (loop_dump_stream, "\n");
record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
ext_val, benefit, DEST_REG, not_every_iteration,
- maybe_multiple, NULL_PTR);
+ maybe_multiple, (rtx*) 0);
}
}
rtx insn;
int not_every_iteration, maybe_multiple;
{
- register int i, j;
- register enum rtx_code code;
- register const char *fmt;
+ int i, j;
+ enum rtx_code code;
+ const char *fmt;
if (x == 0)
return;
/* This code used to disable creating GIVs with mult_val == 1 and
add_val == 0. However, this leads to lost optimizations when
it comes time to combine a set of related DEST_ADDR GIVs, since
- this one would not be seen. */
+ this one would not be seen. */
if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
&mult_val, &ext_val, 1, &benefit,
add_val, ext_val, benefit, DEST_ADDR,
not_every_iteration, maybe_multiple, &XEXP (x, 0));
- v->mem_mode = GET_MODE (x);
+ v->mem = x;
}
}
return;
v->dest_reg = dest_reg;
v->mult_val = mult_val;
v->add_val = inc_val;
- v->ext_dependant = NULL_RTX;
+ v->ext_dependent = NULL_RTX;
v->location = location;
v->mode = GET_MODE (dest_reg);
v->always_computable = ! not_every_iteration;
bl->incremented = 1;
if (loop_dump_stream)
- {
- fprintf (loop_dump_stream,
- "Insn %d: possible biv, reg %d,",
- INSN_UID (insn), REGNO (dest_reg));
- if (GET_CODE (inc_val) == CONST_INT)
- {
- fprintf (loop_dump_stream, " const =");
- fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (inc_val));
- fputc ('\n', loop_dump_stream);
- }
- else
- {
- fprintf (loop_dump_stream, " const = ");
- print_rtl (loop_dump_stream, inc_val);
- fprintf (loop_dump_stream, "\n");
- }
- }
+ loop_biv_dump (v, loop_dump_stream, 0);
}
\f
/* Fill in the data about one giv.
rtx set = single_set (insn);
rtx temp;
- /* Attempt to prove constantness of the values. */
+ /* Attempt to prove constantness of the values. Don't let simplity_rtx
+ undo the MULT canonicalization that we performed earlier. */
temp = simplify_rtx (add_val);
- if (temp)
+ if (temp
+ && ! (GET_CODE (add_val) == MULT
+ && GET_CODE (temp) == ASHIFT))
add_val = temp;
v->insn = insn;
v->dest_reg = dest_reg;
v->mult_val = mult_val;
v->add_val = add_val;
- v->ext_dependant = ext_val;
+ v->ext_dependent = ext_val;
v->benefit = benefit;
v->location = location;
v->cant_derive = 0;
{
/* The giv can be replaced outright by the reduced register only if all
of the following conditions are true:
- - the insn that sets the giv is always executed on any iteration
+ - the insn that sets the giv is always executed on any iteration
on which the giv is used at all
(there are two ways to deduce this:
either the insn is executed on every iteration,
or all uses follow that insn in the same basic block),
- - the giv is not used outside the loop
+ - 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 (loop_dump_stream)
- {
- if (type == DEST_REG)
- fprintf (loop_dump_stream, "Insn %d: giv reg %d",
- INSN_UID (insn), REGNO (dest_reg));
- else
- fprintf (loop_dump_stream, "Insn %d: dest address",
- INSN_UID (insn));
-
- fprintf (loop_dump_stream, " src reg %d benefit %d",
- REGNO (src_reg), v->benefit);
- fprintf (loop_dump_stream, " lifetime %d",
- v->lifetime);
-
- if (v->replaceable)
- fprintf (loop_dump_stream, " replaceable");
-
- if (v->no_const_addval)
- fprintf (loop_dump_stream, " ncav");
-
- if (v->ext_dependant)
- {
- switch (GET_CODE (v->ext_dependant))
- {
- case SIGN_EXTEND:
- fprintf (loop_dump_stream, " ext se");
- break;
- case ZERO_EXTEND:
- fprintf (loop_dump_stream, " ext ze");
- break;
- case TRUNCATE:
- fprintf (loop_dump_stream, " ext tr");
- break;
- default:
- abort ();
- }
- }
-
- if (GET_CODE (mult_val) == CONST_INT)
- {
- fprintf (loop_dump_stream, " mult ");
- fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (mult_val));
- }
- else
- {
- fprintf (loop_dump_stream, " mult ");
- print_rtl (loop_dump_stream, mult_val);
- }
-
- if (GET_CODE (add_val) == CONST_INT)
- {
- fprintf (loop_dump_stream, " add ");
- fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (add_val));
- }
- else
- {
- fprintf (loop_dump_stream, " add ");
- print_rtl (loop_dump_stream, add_val);
- }
- }
-
- if (loop_dump_stream)
- fprintf (loop_dump_stream, "\n");
-
+ loop_giv_dump (v, loop_dump_stream, 0);
}
/* All this does is determine whether a giv can be made replaceable because
static int
basic_induction_var (loop, x, mode, dest_reg, p, inc_val, mult_val, location)
const struct loop *loop;
- register rtx x;
+ rtx x;
enum machine_mode mode;
rtx dest_reg;
rtx p;
rtx *mult_val;
rtx **location;
{
- register enum rtx_code code;
+ enum rtx_code code;
rtx *argp, arg;
rtx insn, set = 0;
return 1;
case SUBREG:
- /* If this is a SUBREG for a promoted variable, check the inner
- value. */
- if (SUBREG_PROMOTED_VAR_P (x))
- return basic_induction_var (loop, SUBREG_REG (x),
- GET_MODE (SUBREG_REG (x)),
- dest_reg, p, inc_val, mult_val, location);
- return 0;
+ /* If what's inside the SUBREG is a BIV, then the SUBREG. This will
+ handle addition of promoted variables.
+ ??? The comment at the start of this function is wrong: promoted
+ variable increments don't look like it says they do. */
+ return basic_induction_var (loop, SUBREG_REG (x),
+ GET_MODE (SUBREG_REG (x)),
+ dest_reg, p, inc_val, mult_val, location);
case REG:
/* If this register is assigned in a previous insn, look at its
/* 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
+ Otherwise, a biv of an inner loop may be incorrectly recognized
as a biv of the outer loop,
causing code to be moved INTO the inner loop. */
case MEM:
case CONST:
/* 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. */
+ would be a useful iterator anyways. convert_modes aborts if we try to
+ convert a float mode to non-float or vice versa too. */
if (loop->level == 1
- && GET_MODE_CLASS (mode) != MODE_CC
- && GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
+ && GET_MODE_CLASS (mode) == GET_MODE_CLASS (GET_MODE (dest_reg))
+ && GET_MODE_CLASS (mode) != MODE_CC)
{
/* Possible bug here? Perhaps we don't know the mode of X. */
*inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
\f
/* Given an expression, X, try to form it as a linear function of a biv.
We will canonicalize it to be of the form
- (plus (mult (BIV) (invar_1))
+ (plus (mult (BIV) (invar_1))
(invar_2))
with possible degeneracies.
case CONST_INT:
case USE:
/* Adding two invariants must result in an invariant, so enclose
- addition operation inside a USE and return it. */
+ addition operation inside a USE and return it. */
if (GET_CODE (arg0) == USE)
arg0 = XEXP (arg0, 0);
if (GET_CODE (arg1) == USE)
tem = arg0, arg0 = arg1, arg1 = tem;
if (GET_CODE (arg1) == PLUS)
- return
- simplify_giv_expr (loop,
- gen_rtx_PLUS (mode,
- gen_rtx_PLUS (mode, arg0,
- XEXP (arg1, 0)),
- XEXP (arg1, 1)),
- ext_val, benefit);
+ return
+ simplify_giv_expr (loop,
+ gen_rtx_PLUS (mode,
+ gen_rtx_PLUS (mode, arg0,
+ XEXP (arg1, 0)),
+ XEXP (arg1, 1)),
+ ext_val, benefit);
/* Now must have MULT + MULT. Distribute if same biv, else not giv. */
if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
arg0 = simplify_giv_expr (loop, tem, ext_val, benefit);
if (*ext_val)
{
- if (!v->ext_dependant)
+ if (!v->ext_dependent)
return arg0;
}
else
{
- *ext_val = v->ext_dependant;
+ *ext_val = v->ext_dependent;
return arg0;
}
return 0;
v->benefit = first_benefit;
v->cant_derive = 0;
v->derive_adjustment = 0;
- v->ext_dependant = NULL_RTX;
+ v->ext_dependent = NULL_RTX;
REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
it cannot possibly be a valid address, 0 is returned.
To perform the computation, we note that
- G1 = x * v + a and
+ G1 = x * v + a and
G2 = y * v + b
where `v' is the biv.
}
else if (CONSTANT_P (a))
{
- return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), const0_rtx, a);
+ enum machine_mode mode_a = GET_MODE (a);
+ enum machine_mode mode_b = GET_MODE (b);
+ enum machine_mode mode = mode_b == VOIDmode ? mode_a : mode_b;
+ return simplify_gen_binary (MINUS, mode, b, a);
}
else if (GET_CODE (b) == PLUS)
{
{
rtx comb, ret;
- /* With the introduction of ext dependant givs, we must care for modes.
+ /* With the introduction of ext dependent givs, we must care for modes.
G2 must not use a wider mode than G1. */
if (GET_MODE_SIZE (g1->mode) < GET_MODE_SIZE (g2->mode))
return NULL_RTX;
the expression of G2 in terms of G1 can be used. */
if (ret != NULL_RTX
&& g2->giv_type == DEST_ADDR
- && memory_address_p (g2->mem_mode, ret)
+ && memory_address_p (GET_MODE (g2->mem), ret)
/* ??? Looses, especially with -fforce-addr, where *g2->location
will always be a register, and so anything more complicated
gets discarded. */
return NULL_RTX;
}
\f
-/* Check each extension dependant giv in this class to see if its
+/* Check each extension dependent giv in this class to see if its
root biv is safe from wrapping in the interior mode, which would
make the giv illegal. */
static void
-check_ext_dependant_givs (bl, loop_info)
+check_ext_dependent_givs (bl, loop_info)
struct iv_class *bl;
struct loop_info *loop_info;
{
int ze_ok = 0, se_ok = 0, info_ok = 0;
enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
HOST_WIDE_INT start_val;
- unsigned HOST_WIDE_INT u_end_val, u_start_val;
+ unsigned HOST_WIDE_INT u_end_val = 0;
+ unsigned HOST_WIDE_INT u_start_val = 0;
rtx incr = pc_rtx;
struct induction *v;
/* Invalidate givs that fail the tests. */
for (v = bl->giv; v; v = v->next_iv)
- if (v->ext_dependant)
+ if (v->ext_dependent)
{
- enum rtx_code code = GET_CODE (v->ext_dependant);
+ enum rtx_code code = GET_CODE (v->ext_dependent);
int ok = 0;
switch (code)
derived GIV. */
if (se_ok && ze_ok)
{
- enum machine_mode outer_mode = GET_MODE (v->ext_dependant);
+ enum machine_mode outer_mode = GET_MODE (v->ext_dependent);
unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
/* We know from the above that both endpoints are nonnegative,
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
- "Verified ext dependant giv at %d of reg %d\n",
+ "Verified ext dependent giv at %d of reg %d\n",
INSN_UID (v->insn), bl->regno);
}
}
}
fprintf (loop_dump_stream,
- "Failed ext dependant giv at %d, %s\n",
+ "Failed ext dependent giv at %d, %s\n",
INSN_UID (v->insn), why);
}
v->ignore = 1;
+ bl->all_reduced = 0;
}
}
}
struct induction *v;
rtx value;
{
- rtx ext_dep = v->ext_dependant;
+ rtx ext_dep = v->ext_dependent;
if (! ext_dep)
return value;
- /* Recall that check_ext_dependant_givs verified that the known bounds
+ /* Recall that check_ext_dependent_givs verified that the known bounds
of a biv did not overflow or wrap with respect to the extension for
the giv. Therefore, constants need no additional adjustment. */
if (CONSTANT_P (value) && GET_MODE (value) == VOIDmode)
g2->new_reg = can_combine[i * giv_count + j];
g2->same = g1;
+ /* For destination, we now may replace by mem expression instead
+ of register. This changes the costs considerably, so add the
+ compensation. */
+ if (g2->giv_type == DEST_ADDR)
+ g2->benefit = (g2->benefit + reg_address_cost
+ - address_cost (g2->new_reg,
+ GET_MODE (g2->mem)));
g1->combined_with++;
g1->lifetime += g2->lifetime;
free (can_combine);
}
\f
-/* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
+/* Generate sequence for REG = B * M + A. */
-void
-emit_iv_add_mult (b, m, a, reg, insert_before)
+static rtx
+gen_add_mult (b, m, a, reg)
rtx b; /* initial value of basic induction variable */
rtx m; /* multiplicative constant */
rtx a; /* additive constant */
rtx reg; /* destination register */
- rtx insert_before;
{
rtx seq;
rtx result;
- /* Prevent unexpected sharing of these rtx. */
- a = copy_rtx (a);
- b = copy_rtx (b);
-
- /* 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);
-
start_sequence ();
+ /* Use unsigned arithmetic. */
result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
if (reg != result)
emit_move_insn (reg, result);
seq = gen_sequence ();
end_sequence ();
- emit_insn_before (seq, insert_before);
+ return seq;
+}
+
- /* It is entirely possible that the expansion created lots of new
- registers. Iterate over the sequence we just created and
- record them all. */
+/* Update registers created in insn sequence SEQ. */
+
+static void
+loop_regs_update (loop, seq)
+ const struct loop *loop ATTRIBUTE_UNUSED;
+ rtx seq;
+{
+ /* Update register info for alias analysis. */
if (GET_CODE (seq) == SEQUENCE)
{
record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
}
}
- else if (GET_CODE (seq) == SET
- && GET_CODE (SET_DEST (seq)) == REG)
- record_base_value (REGNO (SET_DEST (seq)), SET_SRC (seq), 0);
+ else
+ {
+ if (GET_CODE (seq) == SET
+ && GET_CODE (SET_DEST (seq)) == REG)
+ record_base_value (REGNO (SET_DEST (seq)), SET_SRC (seq), 0);
+ }
}
-/* Similar to emit_iv_add_mult, but compute cost rather than emitting
- insns. */
+
+/* EMIT code before BEFORE_BB/BEFORE_INSN to set REG = B * M + A. */
+
+void
+loop_iv_add_mult_emit_before (loop, b, m, a, reg, before_bb, before_insn)
+ const struct loop *loop;
+ rtx b; /* initial value of basic induction variable */
+ rtx m; /* multiplicative constant */
+ rtx a; /* additive constant */
+ rtx reg; /* destination register */
+ basic_block before_bb;
+ rtx before_insn;
+{
+ rtx seq;
+
+ if (! before_insn)
+ {
+ loop_iv_add_mult_hoist (loop, b, m, a, reg);
+ return;
+ }
+
+ /* Use copy_rtx to prevent unexpected sharing of these rtx. */
+ seq = gen_add_mult (copy_rtx (b), copy_rtx (m), copy_rtx (a), reg);
+
+ /* Increase the lifetime of any invariants moved further in code. */
+ update_reg_last_use (a, before_insn);
+ update_reg_last_use (b, before_insn);
+ update_reg_last_use (m, before_insn);
+
+ loop_insn_emit_before (loop, before_bb, before_insn, seq);
+
+ /* It is possible that the expansion created lots of new registers.
+ Iterate over the sequence we just created and record them all. */
+ loop_regs_update (loop, seq);
+}
+
+
+/* Emit insns in loop pre-header to set REG = B * M + A. */
+
+void
+loop_iv_add_mult_sink (loop, b, m, a, reg)
+ const struct loop *loop;
+ rtx b; /* initial value of basic induction variable */
+ rtx m; /* multiplicative constant */
+ rtx a; /* additive constant */
+ rtx reg; /* destination register */
+{
+ rtx seq;
+
+ /* Use copy_rtx to prevent unexpected sharing of these rtx. */
+ seq = gen_add_mult (copy_rtx (b), copy_rtx (m), copy_rtx (a), reg);
+
+ /* Increase the lifetime of any invariants moved further in code.
+ ???? Is this really necessary? */
+ update_reg_last_use (a, loop->sink);
+ update_reg_last_use (b, loop->sink);
+ update_reg_last_use (m, loop->sink);
+
+ loop_insn_sink (loop, seq);
+
+ /* It is possible that the expansion created lots of new registers.
+ Iterate over the sequence we just created and record them all. */
+ loop_regs_update (loop, seq);
+}
+
+
+/* Emit insns after loop to set REG = B * M + A. */
+
+void
+loop_iv_add_mult_hoist (loop, b, m, a, reg)
+ const struct loop *loop;
+ rtx b; /* initial value of basic induction variable */
+ rtx m; /* multiplicative constant */
+ rtx a; /* additive constant */
+ rtx reg; /* destination register */
+{
+ rtx seq;
+
+ /* Use copy_rtx to prevent unexpected sharing of these rtx. */
+ seq = gen_add_mult (copy_rtx (b), copy_rtx (m), copy_rtx (a), reg);
+
+ loop_insn_hoist (loop, seq);
+
+ /* It is possible that the expansion created lots of new registers.
+ Iterate over the sequence we just created and record them all. */
+ loop_regs_update (loop, seq);
+}
+
+
+
+/* Similar to gen_add_mult, but compute cost rather than generating
+ sequence. */
+
static int
iv_add_mult_cost (b, m, a, reg)
rtx b; /* initial value of basic induction variable */
rtx last, result;
start_sequence ();
- result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
+ result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
if (reg != result)
emit_move_insn (reg, result);
last = get_last_insn ();
which is reversible. */
int reversible_mem_store = 1;
- if (bl->giv_count == 0 && ! loop->exit_count)
+ if (bl->giv_count == 0
+ && !loop->exit_count
+ && !loop_info->has_multiple_exit_targets)
{
rtx bivreg = regno_reg_rtx[bl->regno];
+ struct iv_class *blt;
/* If there are no givs for this biv, and the only exit is the
fall through at the end of the loop, then
break;
}
}
+
+ /* A biv has uses besides counting if it is used to set
+ another biv. */
+ for (blt = ivs->list; blt; blt = blt->next)
+ if (blt->init_set
+ && reg_mentioned_p (bivreg, SET_SRC (blt->init_set)))
+ {
+ no_use_except_counting = 0;
+ break;
+ }
}
if (no_use_except_counting)
{
struct induction *v;
- reversible_mem_store
- = (! loop_info->unknown_address_altered
- && ! loop_info->unknown_constant_address_altered
- && ! loop_invariant_p (loop,
- XEXP (XEXP (loop_info->store_mems, 0),
- 0)));
+ /* If we could prove that each of the memory locations
+ written to was different, then we could reverse the
+ store -- but we don't presently have any way of
+ knowing that. */
+ reversible_mem_store = 0;
/* If the store depends on a register that is set after the
store, it depends on the initial value, and is thus not
&& ! loop_info->has_volatile
&& reversible_mem_store
&& (bl->giv_count + bl->biv_count + loop_info->num_mem_sets
- + LOOP_MOVABLES (loop)->num + compare_and_branch == insn_count)
+ + num_unmoved_movables (loop) + compare_and_branch == insn_count)
&& (bl == ivs->list && bl->next == 0))
|| no_use_except_counting)
{
/* 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);
+ jump_label = condjump_label (PREV_INSN (loop_end));
new_add_val = GEN_INT (-INTVAL (bl->biv->add_val));
/* Set start_value; if this is not a CONST_INT, we need
&& GET_CODE (comparison_value) == CONST_INT)
{
start_value = GEN_INT (comparison_val - add_adjust);
- emit_insn_before (gen_move_insn (reg, start_value),
- loop_start);
+ loop_insn_hoist (loop, gen_move_insn (reg, start_value));
}
else if (GET_CODE (initial_value) == CONST_INT)
{
- rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
enum machine_mode mode = GET_MODE (reg);
- enum insn_code icode
- = add_optab->handlers[(int) mode].insn_code;
-
- if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
- || ! ((*insn_data[icode].operand[1].predicate)
- (comparison_value, mode))
- || ! ((*insn_data[icode].operand[2].predicate)
- (offset, mode)))
+ rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
+ rtx add_insn = gen_add3_insn (reg, comparison_value, offset);
+
+ if (add_insn == 0)
return 0;
+
start_value
= gen_rtx_PLUS (mode, comparison_value, offset);
- emit_insn_before ((GEN_FCN (icode)
- (reg, comparison_value, offset)),
- loop_start);
+ loop_insn_hoist (loop, add_insn);
if (GET_CODE (comparison) == LE)
final_value = gen_rtx_PLUS (mode, comparison_value,
GEN_INT (add_val));
else if (! add_adjust)
{
enum machine_mode mode = GET_MODE (reg);
- enum insn_code icode
- = sub_optab->handlers[(int) mode].insn_code;
- if (! (*insn_data[icode].operand[0].predicate) (reg, mode)
- || ! ((*insn_data[icode].operand[1].predicate)
- (comparison_value, mode))
- || ! ((*insn_data[icode].operand[2].predicate)
- (initial_value, mode)))
+ rtx sub_insn = gen_sub3_insn (reg, comparison_value,
+ initial_value);
+
+ if (sub_insn == 0)
return 0;
start_value
= gen_rtx_MINUS (mode, comparison_value, initial_value);
- emit_insn_before ((GEN_FCN (icode)
- (reg, comparison_value, initial_value)),
- loop_start);
+ loop_insn_hoist (loop, sub_insn);
}
else
/* We could handle the other cases too, but it'll be
tem = gen_sequence ();
end_sequence ();
- p = emit_insn_before (tem, bl->biv->insn);
+ p = loop_insn_emit_before (loop, 0, bl->biv->insn, tem);
delete_insn (bl->biv->insn);
/* Update biv info to reflect its new status. */
if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare))
|| ! bl->init_insn
|| REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
- emit_insn_after (gen_move_insn (reg, final_value),
- loop_end);
+ loop_insn_sink (loop, gen_load_of_final_value (reg, final_value));
/* Delete compare/branch at end of loop. */
- delete_insn (PREV_INSN (loop_end));
+ delete_related_insns (PREV_INSN (loop_end));
if (compare_and_branch == 2)
- delete_insn (first_compare);
+ delete_related_insns (first_compare);
/* Add new compare/branch insn at end of loop. */
start_sequence ();
emit_cmp_and_jump_insns (reg, const0_rtx, cmp_code, NULL_RTX,
- GET_MODE (reg), 0, 0,
+ GET_MODE (reg), 0,
XEXP (jump_label, 0));
tem = gen_sequence ();
end_sequence ();
{
struct loop_ivs *ivs = LOOP_IVS (loop);
rtx reg = bl->biv->dest_reg;
- rtx loop_start = loop->start;
- rtx loop_end = loop->end;
rtx p;
/* Scan all insns in the loop, stopping if we find one that uses the
biv in a way that we cannot eliminate. */
- for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
+ for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
{
enum rtx_code code = GET_CODE (p);
- rtx where = threshold >= insn_count ? loop_start : p;
+ basic_block where_bb = 0;
+ rtx where_insn = threshold >= insn_count ? 0 : p;
/* If this is a libcall that sets a giv, skip ahead to its end. */
if (GET_RTX_CLASS (code) == 'i')
if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
&& reg_mentioned_p (reg, PATTERN (p))
&& ! maybe_eliminate_biv_1 (loop, PATTERN (p), p, bl,
- eliminate_p, where))
+ eliminate_p, where_bb, where_insn))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
}
}
- if (p == loop_end)
+ if (p == loop->end)
{
if (loop_dump_stream)
fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
If BIV does not appear in X, return 1.
- If ELIMINATE_P is non-zero, actually do the elimination. WHERE indicates
- where extra insns should be added. Depending on how many items have been
- moved out of the loop, it will either be before INSN or at the start of
- the loop. */
+ If ELIMINATE_P is non-zero, actually do the elimination.
+ WHERE_INSN/WHERE_BB indicate where extra insns should be added.
+ Depending on how many items have been moved out of the loop, it
+ will either be before INSN (when WHERE_INSN is non-zero) or at the
+ start of the loop (when WHERE_INSN is zero). */
static int
-maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where)
+maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where_bb, where_insn)
const struct loop *loop;
rtx x, insn;
struct iv_class *bl;
int eliminate_p;
- rtx where;
+ basic_block where_bb;
+ rtx where_insn;
{
enum rtx_code code = GET_CODE (x);
rtx reg = bl->biv->dest_reg;
into a register (it will be a loop invariant.) */
tem = gen_reg_rtx (GET_MODE (v->new_reg));
- emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
- where);
+ loop_insn_emit_before (loop, 0, where_insn,
+ gen_move_insn (tem,
+ copy_rtx (v->add_val)));
/* Substitute the new register for its invariant value in
the compare expression. */
{
/* Otherwise, load it into a register. */
tem = gen_reg_rtx (mode);
- emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
+ loop_iv_add_mult_emit_before (loop, arg,
+ v->mult_val, v->add_val,
+ tem, where_bb, where_insn);
validate_change (insn, &XEXP (x, arg_operand), tem, 1);
}
if (apply_change_group ())
v->new_reg, 1);
/* Compute value to compare against. */
- emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
+ loop_iv_add_mult_emit_before (loop, arg,
+ v->mult_val, v->add_val,
+ tem, where_bb, where_insn);
/* Use it in this insn. */
validate_change (insn, &XEXP (x, arg_operand), tem, 1);
if (apply_change_group ())
v->new_reg, 1);
/* Compute value to compare against. */
- emit_iv_add_mult (arg, v->mult_val, v->add_val,
- tem, where);
+ loop_iv_add_mult_emit_before (loop, arg,
+ v->mult_val, v->add_val,
+ tem, where_bb, where_insn);
validate_change (insn, &XEXP (x, arg_operand), tem, 1);
if (apply_change_group ())
return 1;
if (v->ignore || v->maybe_dead || v->mode != mode)
continue;
- for (tv = REG_IV_CLASS (ivs, REGNO (arg))->giv; tv;
+ for (tv = REG_IV_CLASS (ivs, REGNO (arg))->giv; tv;
tv = tv->next_iv)
if (! tv->ignore && ! tv->maybe_dead
&& rtx_equal_p (tv->mult_val, v->mult_val)
{
case 'e':
if (! maybe_eliminate_biv_1 (loop, XEXP (x, i), insn, bl,
- eliminate_p, where))
+ eliminate_p, where_bb, where_insn))
return 0;
break;
case 'E':
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl,
- eliminate_p, where))
+ eliminate_p, where_bb, where_insn))
return 0;
break;
}
/* If any of the registers in X are "old" and currently have a last use earlier
than INSN, update them to have a last use of INSN. Their actual last use
will be the previous insn but it will not have a valid uid_luid so we can't
- use it. */
+ use it. X must be a source expression only. */
static void
update_reg_last_use (x, insn)
/* Check for the case where INSN does not have a valid luid. In this case,
there is no need to modify the regno_last_uid, as this can only happen
when code is inserted after the loop_end to set a pseudo's final value,
- and hence this insn will never be the last use of x. */
+ and hence this insn will never be the last use of x.
+ ???? This comment is not correct. See for example loop_givs_reduce.
+ This may insert an insn before another new insn. */
if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
&& INSN_UID (insn) < max_uid_for_loop
&& REGNO_LAST_LUID (REGNO (x)) < INSN_LUID (insn))
- REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
+ {
+ REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
+ }
else
{
- register int i, j;
- register const char *fmt = GET_RTX_FORMAT (GET_CODE (x));
+ int i, j;
+ 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')
rtx tem;
rtx op0, op1;
int reverse_code = 0;
- int did_reverse_condition = 0;
enum machine_mode mode;
code = GET_CODE (cond);
op1 = XEXP (cond, 1);
if (reverse)
- {
- code = reverse_condition (code);
- did_reverse_condition ^= 1;
- }
+ code = reversed_comparison_code (cond, insn);
+ if (code == UNKNOWN)
+ return 0;
if (earliest)
*earliest = insn;
if ((prev = prev_nonnote_insn (prev)) == 0
|| GET_CODE (prev) != INSN
- || FIND_REG_INC_NOTE (prev, 0)
- || (set = single_set (prev)) == 0)
+ || FIND_REG_INC_NOTE (prev, NULL_RTX))
+ break;
+
+ set = set_of (op0, prev);
+
+ if (set
+ && (GET_CODE (set) != SET
+ || !rtx_equal_p (SET_DEST (set), op0)))
break;
/* If this is setting OP0, get what it sets it to if it looks
relevant. */
- if (rtx_equal_p (SET_DEST (set), op0))
+ if (set)
{
enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
|| mode == VOIDmode || inner_mode == VOIDmode))
{
- /* We might have reversed a LT to get a GE here. But this wasn't
- actually the comparison of data, so we don't flag that we
- have had to reverse the condition. */
- did_reverse_condition ^= 1;
reverse_code = 1;
x = SET_SRC (set);
}
code = GET_CODE (x);
if (reverse_code)
{
- code = reverse_condition (code);
+ code = reversed_comparison_code (x, prev);
if (code == UNKNOWN)
return 0;
- did_reverse_condition ^= 1;
reverse_code = 0;
}
{
case LE:
if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
- code = LT, op1 = GEN_INT (const_val + 1);
+ code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
break;
/* When cross-compiling, const_val might be sign-extended from
if ((HOST_WIDE_INT) (const_val & max_val)
!= (((HOST_WIDE_INT) 1
<< (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
- code = GT, op1 = GEN_INT (const_val - 1);
+ code = GT, op1 = gen_int_mode (const_val - 1, GET_MODE (op0));
break;
case LEU:
if (uconst_val < max_val)
- code = LTU, op1 = GEN_INT (uconst_val + 1);
+ code = LTU, op1 = gen_int_mode (uconst_val + 1, GET_MODE (op0));
break;
case GEU:
if (uconst_val != 0)
- code = GTU, op1 = GEN_INT (uconst_val - 1);
+ code = GTU, op1 = gen_int_mode (uconst_val - 1, GET_MODE (op0));
break;
default:
}
}
- /* If this was floating-point and we reversed anything other than an
- EQ or NE or (UN)ORDERED, return zero. */
- if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
- && did_reverse_condition
- && code != NE && code != EQ && code != UNORDERED && code != ORDERED
- && ! flag_fast_math
- && GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
- return 0;
-
#ifdef HAVE_cc0
/* Never return CC0; return zero instead. */
if (op0 == cc0_rtx)
const struct loop *loop;
rtx x;
{
- rtx comparison = get_condition (x, NULL_PTR);
+ rtx comparison = get_condition (x, (rtx*) 0);
if (comparison == 0
|| ! loop_invariant_p (loop, XEXP (comparison, 0))
return 0;
}
-/* Like load_mems, but also ensures that REGS->array[I].SET_IN_LOOP,
- REGS->array[I].MAY_NOT_OPTIMIZE, REGS->array[I].SINGLE_USAGE, and
- INSN_COUNT have the correct values after load_mems. */
+
+/* Allocate REGS->ARRAY or reallocate it if it is too small.
+
+ Increment REGS->ARRAY[I].SET_IN_LOOP at the index I of each
+ register that is modified by an insn between FROM and TO. If the
+ value of an element of REGS->array[I].SET_IN_LOOP becomes 127 or
+ more, stop incrementing it, to avoid overflow.
+
+ Store in REGS->ARRAY[I].SINGLE_USAGE the single insn in which
+ register I is used, if it is only used once. Otherwise, it is set
+ to 0 (for no uses) or const0_rtx for more than one use. This
+ parameter may be zero, in which case this processing is not done.
+
+ Set REGS->ARRAY[I].MAY_NOT_OPTIMIZE nonzero if we should not
+ optimize register I. */
static void
-load_mems_and_recount_loop_regs_set (loop, insn_count)
+loop_regs_scan (loop, extra_size)
const struct loop *loop;
- int *insn_count;
+ int extra_size;
{
struct loop_regs *regs = LOOP_REGS (loop);
+ int old_nregs;
+ /* last_set[n] is nonzero iff reg n has been set in the current
+ basic block. In that case, it is the insn that last set reg n. */
+ rtx *last_set;
+ rtx insn;
+ int i;
- load_mems (loop);
+ old_nregs = regs->num;
+ regs->num = max_reg_num ();
- /* Recalculate regs->array since load_mems may have created new
- registers. */
- if (max_reg_num () > regs->num)
+ /* Grow the regs array if not allocated or too small. */
+ if (regs->num >= regs->size)
{
- int i;
- int old_nregs;
+ regs->size = regs->num + extra_size;
- old_nregs = regs->num;
- regs->num = max_reg_num ();
+ regs->array = (struct loop_reg *)
+ xrealloc (regs->array, regs->size * sizeof (*regs->array));
- if (regs->num >= regs->size)
- {
- regs->size = regs->num;
+ /* Zero the new elements. */
+ memset (regs->array + old_nregs, 0,
+ (regs->size - old_nregs) * sizeof (*regs->array));
+ }
- /* Grow the array. */
- regs->array = (struct loop_reg *)
- xrealloc (regs->array, regs->size * sizeof (*regs->array));
- }
+ /* Clear previously scanned fields but do not clear n_times_set. */
+ for (i = 0; i < old_nregs; i++)
+ {
+ regs->array[i].set_in_loop = 0;
+ regs->array[i].may_not_optimize = 0;
+ regs->array[i].single_usage = NULL_RTX;
+ }
- for (i = 0; i < regs->num; i++)
+ last_set = (rtx *) xcalloc (regs->num, sizeof (rtx));
+
+ /* Scan the loop, recording register usage. */
+ for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
+ insn = NEXT_INSN (insn))
+ {
+ if (INSN_P (insn))
{
- regs->array[i].set_in_loop = 0;
- regs->array[i].may_not_optimize = 0;
- regs->array[i].single_usage = NULL_RTX;
- }
+ /* Record registers that have exactly one use. */
+ find_single_use_in_loop (regs, insn, PATTERN (insn));
- count_loop_regs_set (loop, insn_count);
+ /* Include uses in REG_EQUAL notes. */
+ if (REG_NOTES (insn))
+ find_single_use_in_loop (regs, insn, REG_NOTES (insn));
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- {
- regs->array[i].may_not_optimize = 1;
- regs->array[i].set_in_loop = 1;
+ if (GET_CODE (PATTERN (insn)) == SET
+ || GET_CODE (PATTERN (insn)) == CLOBBER)
+ count_one_set (regs, insn, PATTERN (insn), last_set);
+ else if (GET_CODE (PATTERN (insn)) == PARALLEL)
+ {
+ int i;
+ for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
+ count_one_set (regs, insn, XVECEXP (PATTERN (insn), 0, i),
+ last_set);
+ }
}
+ if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
+ memset (last_set, 0, regs->num * sizeof (rtx));
+ }
+
+ /* Invalidate all hard registers clobbered by calls. With one exception:
+ a call-clobbered PIC register is still function-invariant for our
+ purposes, since we can hoist any PIC calculations out of the loop.
+ Thus the call to rtx_varies_p. */
+ if (LOOP_INFO (loop)->has_call)
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)
+ && rtx_varies_p (gen_rtx_REG (Pmode, i), /*for_alias=*/1))
+ {
+ regs->array[i].may_not_optimize = 1;
+ regs->array[i].set_in_loop = 1;
+ }
+
#ifdef AVOID_CCMODE_COPIES
- /* Don't try to move insns which set CC registers if we should not
- create CCmode register copies. */
- for (i = regs->num - 1; i >= FIRST_PSEUDO_REGISTER; i--)
- if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
- regs->array[i].may_not_optimize = 1;
+ /* Don't try to move insns which set CC registers if we should not
+ create CCmode register copies. */
+ for (i = regs->num - 1; i >= FIRST_PSEUDO_REGISTER; i--)
+ if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
+ regs->array[i].may_not_optimize = 1;
#endif
- /* Set regs->array[I].n_times_set for the new registers. */
- for (i = old_nregs; i < regs->num; i++)
- regs->array[i].n_times_set = regs->array[i].set_in_loop;
- }
+ /* Set regs->array[I].n_times_set for the new registers. */
+ for (i = old_nregs; i < regs->num; i++)
+ regs->array[i].n_times_set = regs->array[i].set_in_loop;
+
+ free (last_set);
+}
+
+/* Returns the number of real INSNs in the LOOP. */
+
+static int
+count_insns_in_loop (loop)
+ const struct loop *loop;
+{
+ int count = 0;
+ rtx insn;
+
+ for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
+ insn = NEXT_INSN (insn))
+ if (INSN_P (insn))
+ ++count;
+
+ return count;
}
/* Move MEMs into registers for the duration of the loop. */
struct loop_regs *regs = LOOP_REGS (loop);
int maybe_never = 0;
int i;
- rtx p;
+ rtx p, prev_ebb_head;
rtx label = NULL_RTX;
rtx end_label;
/* Nonzero if the next instruction may never be executed. */
int next_maybe_never = 0;
- int last_max_reg = max_reg_num ();
+ unsigned int last_max_reg = max_reg_num ();
if (loop_info->mems_idx == 0)
return;
never executed. Also check if there is a goto out of the loop other
than right after the end of the loop. */
for (p = next_insn_in_loop (loop, loop->scan_start);
- p != NULL_RTX && ! maybe_never;
+ p != NULL_RTX;
p = next_insn_in_loop (loop, p))
{
if (GET_CODE (p) == CODE_LABEL)
/* If this is a jump outside of the loop but not right
after the end of the loop, we would have to emit new fixup
sequences for each such label. */
- if (JUMP_LABEL (p) != end_label
- && (INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop
- || INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop->start)
- || INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop->end)))
+ if (/* If we can't tell where control might go when this
+ JUMP_INSN is executed, we must be conservative. */
+ !JUMP_LABEL (p)
+ || (JUMP_LABEL (p) != end_label
+ && (INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop
+ || INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop->start)
+ || INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop->end))))
return;
if (!any_condjump_p (p))
PREV_INSN (p) && GET_CODE (p) != CODE_LABEL;
p = PREV_INSN (p))
;
+ prev_ebb_head = p;
cselib_init ();
loop_info->mems[i].reg = reg;
/* Now, replace all references to the MEM with the
- corresponding pesudos. */
+ corresponding pseudos. */
maybe_never = 0;
for (p = next_insn_in_loop (loop, loop->scan_start);
p != NULL_RTX;
&& rtx_equal_p (SET_DEST (set), mem))
SET_REGNO_REG_SET (&store_copies, REGNO (SET_SRC (set)));
- /* Replace the memory reference with the shadow register. */
- replace_loop_mems (p, loop_info->mems[i].mem,
- loop_info->mems[i].reg);
+ /* If this is a call which uses / clobbers this memory
+ location, we must not change the interface here. */
+ if (GET_CODE (p) == CALL_INSN
+ && reg_mentioned_p (loop_info->mems[i].mem,
+ CALL_INSN_FUNCTION_USAGE (p)))
+ {
+ cancel_changes (0);
+ loop_info->mems[i].optimize = 0;
+ break;
+ }
+ else
+ /* Replace the memory reference with the shadow register. */
+ replace_loop_mems (p, loop_info->mems[i].mem,
+ loop_info->mems[i].reg);
}
if (GET_CODE (p) == CODE_LABEL
maybe_never = 1;
}
- if (! apply_change_group ())
+ if (! loop_info->mems[i].optimize)
+ ; /* We found we couldn't do the replacement, so do nothing. */
+ else if (! apply_change_group ())
/* We couldn't replace all occurrences of the MEM. */
loop_info->mems[i].optimize = 0;
else
if (CONSTANT_P (equiv->loc))
const_equiv = equiv;
else if (GET_CODE (equiv->loc) == REG
- /* Extending hard register lifetimes cuases crash
+ /* Extending hard register lifetimes causes crash
on SRC targets. Doing so on non-SRC is
probably also not good idea, since we most
probably have pseudoregister equivalence as
if (best_equiv)
best = copy_rtx (best_equiv->loc);
}
+
set = gen_move_insn (reg, best);
- set = emit_insn_before (set, loop->start);
+ set = loop_insn_hoist (loop, set);
+ if (REG_P (best))
+ {
+ for (p = prev_ebb_head; p != loop->start; p = NEXT_INSN (p))
+ if (REGNO_LAST_UID (REGNO (best)) == INSN_UID (p))
+ {
+ REGNO_LAST_UID (REGNO (best)) = INSN_UID (set);
+ break;
+ }
+ }
+
if (const_equiv)
- REG_NOTES (set) = gen_rtx_EXPR_LIST (REG_EQUAL,
- copy_rtx (const_equiv->loc),
- REG_NOTES (set));
+ set_unique_reg_note (set, REG_EQUAL, copy_rtx (const_equiv->loc));
if (written)
{
/* Store the memory immediately after END, which is
the NOTE_LOOP_END. */
set = gen_move_insn (copy_rtx (mem), reg);
- emit_insn_after (set, label);
+ loop_insn_emit_after (loop, 0, label, set);
}
if (loop_dump_stream)
arg.set_seen = 0;
note_stores (PATTERN (insn), note_reg_stored, &arg);
if (arg.set_seen)
- break;
+ {
+ rtx note = find_reg_note (insn, REG_EQUAL, NULL);
+
+ /* It is possible that we've turned previously valid REG_EQUAL to
+ invalid, as we change the REGNO to REPLACEMENT and unlike REGNO,
+ REPLACEMENT is modified, we get different meaning. */
+ if (note && reg_mentioned_p (replacement, XEXP (note, 0)))
+ remove_note (insn, note);
+ break;
+ }
}
}
if (! init_insn)
fprintf (loop_dump_stream, " Replaced reg %d", regno);
if (store_is_first && replaced_last)
{
- PUT_CODE (init_insn, NOTE);
- NOTE_LINE_NUMBER (init_insn) = NOTE_INSN_DELETED;
- if (loop_dump_stream)
- fprintf (loop_dump_stream, ", deleting init_insn (%d)",
- INSN_UID (init_insn));
+ rtx first;
+ rtx retval_note;
+
+ /* Assume we're just deleting INIT_INSN. */
+ first = init_insn;
+ /* Look for REG_RETVAL note. If we're deleting the end of
+ the libcall sequence, the whole sequence can go. */
+ retval_note = find_reg_note (init_insn, REG_RETVAL, NULL_RTX);
+ /* If we found a REG_RETVAL note, find the first instruction
+ in the sequence. */
+ if (retval_note)
+ first = XEXP (retval_note, 0);
+
+ /* Delete the instructions. */
+ loop_delete_insns (first, init_insn);
}
if (loop_dump_stream)
fprintf (loop_dump_stream, ".\n");
}
}
+/* Replace all the instructions from FIRST up to and including LAST
+ with NOTE_INSN_DELETED notes. */
+
+static void
+loop_delete_insns (first, last)
+ rtx first;
+ rtx last;
+{
+ while (1)
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream, ", deleting init_insn (%d)",
+ INSN_UID (first));
+ delete_insn (first);
+
+ /* If this was the LAST instructions we're supposed to delete,
+ we're done. */
+ if (first == last)
+ break;
+
+ first = NEXT_INSN (first);
+ }
+}
+
/* Try to replace occurrences of pseudo REGNO with REPLACEMENT within
loop LOOP if the order of the sets of these registers can be
swapped. There must be exactly one insn within the loop that sets
unsigned int regno;
{
rtx insn;
- rtx set;
+ rtx set = NULL_RTX;
unsigned int new_regno;
new_regno = REGNO (replacement);
insn = next_insn_in_loop (loop, insn))
{
/* Search for the insn that copies REGNO to NEW_REGNO? */
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
+ if (INSN_P (insn)
&& (set = single_set (insn))
&& GET_CODE (SET_DEST (set)) == REG
&& REGNO (SET_DEST (set)) == new_regno
prev_insn = PREV_INSN (insn);
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
+ if (INSN_P (insn)
&& (prev_set = single_set (prev_insn))
&& GET_CODE (SET_DEST (prev_set)) == REG
&& REGNO (SET_DEST (prev_set)) == regno)
return 0;
}
\f
+/* Emit insn for PATTERN after WHERE_INSN in basic block WHERE_BB
+ (ignored in the interim). */
+
+static rtx
+loop_insn_emit_after (loop, where_bb, where_insn, pattern)
+ const struct loop *loop ATTRIBUTE_UNUSED;
+ basic_block where_bb ATTRIBUTE_UNUSED;
+ rtx where_insn;
+ rtx pattern;
+{
+ return emit_insn_after (pattern, where_insn);
+}
+
+
+/* If WHERE_INSN is non-zero emit insn for PATTERN before WHERE_INSN
+ in basic block WHERE_BB (ignored in the interim) within the loop
+ otherwise hoist PATTERN into the loop pre-header. */
+
+rtx
+loop_insn_emit_before (loop, where_bb, where_insn, pattern)
+ const struct loop *loop;
+ basic_block where_bb ATTRIBUTE_UNUSED;
+ rtx where_insn;
+ rtx pattern;
+{
+ if (! where_insn)
+ return loop_insn_hoist (loop, pattern);
+ return emit_insn_before (pattern, where_insn);
+}
+
+
+/* Emit call insn for PATTERN before WHERE_INSN in basic block
+ WHERE_BB (ignored in the interim) within the loop. */
+
+static rtx
+loop_call_insn_emit_before (loop, where_bb, where_insn, pattern)
+ const struct loop *loop ATTRIBUTE_UNUSED;
+ basic_block where_bb ATTRIBUTE_UNUSED;
+ rtx where_insn;
+ rtx pattern;
+{
+ return emit_call_insn_before (pattern, where_insn);
+}
+
+
+/* Hoist insn for PATTERN into the loop pre-header. */
+
+rtx
+loop_insn_hoist (loop, pattern)
+ const struct loop *loop;
+ rtx pattern;
+{
+ return loop_insn_emit_before (loop, 0, loop->start, pattern);
+}
+
+
+/* Hoist call insn for PATTERN into the loop pre-header. */
+
+static rtx
+loop_call_insn_hoist (loop, pattern)
+ const struct loop *loop;
+ rtx pattern;
+{
+ return loop_call_insn_emit_before (loop, 0, loop->start, pattern);
+}
+
+
+/* Sink insn for PATTERN after the loop end. */
+
+rtx
+loop_insn_sink (loop, pattern)
+ const struct loop *loop;
+ rtx pattern;
+{
+ return loop_insn_emit_before (loop, 0, loop->sink, pattern);
+}
+
+/* bl->final_value can be eighter general_operand or PLUS of general_operand
+ and constant. Emit sequence of intructions to load it into REG */
+static rtx
+gen_load_of_final_value (reg, final_value)
+ rtx reg, final_value;
+{
+ rtx seq;
+ start_sequence ();
+ final_value = force_operand (final_value, reg);
+ if (final_value != reg)
+ emit_move_insn (reg, final_value);
+ seq = gen_sequence ();
+ end_sequence ();
+ return seq;
+}
+
+/* If the loop has multiple exits, emit insn for PATTERN before the
+ loop to ensure that it will always be executed no matter how the
+ loop exits. Otherwise, emit the insn for PATTERN after the loop,
+ since this is slightly more efficient. */
+
+static rtx
+loop_insn_sink_or_swim (loop, pattern)
+ const struct loop *loop;
+ rtx pattern;
+{
+ if (loop->exit_count)
+ return loop_insn_hoist (loop, pattern);
+ else
+ return loop_insn_sink (loop, pattern);
+}
+\f
+static void
+loop_ivs_dump (loop, file, verbose)
+ const struct loop *loop;
+ FILE *file;
+ int verbose;
+{
+ struct iv_class *bl;
+ int iv_num = 0;
+
+ if (! loop || ! file)
+ return;
+
+ for (bl = LOOP_IVS (loop)->list; bl; bl = bl->next)
+ iv_num++;
+
+ fprintf (file, "Loop %d: %d IV classes\n", loop->num, iv_num);
+
+ for (bl = LOOP_IVS (loop)->list; bl; bl = bl->next)
+ {
+ loop_iv_class_dump (bl, file, verbose);
+ fputc ('\n', file);
+ }
+}
+
+
+static void
+loop_iv_class_dump (bl, file, verbose)
+ const struct iv_class *bl;
+ FILE *file;
+ int verbose ATTRIBUTE_UNUSED;
+{
+ struct induction *v;
+ rtx incr;
+ int i;
+
+ if (! bl || ! file)
+ return;
+
+ fprintf (file, "IV class for reg %d, benefit %d\n",
+ bl->regno, bl->total_benefit);
+
+ fprintf (file, " Init insn %d", INSN_UID (bl->init_insn));
+ if (bl->initial_value)
+ {
+ fprintf (file, ", init val: ");
+ print_simple_rtl (file, bl->initial_value);
+ }
+ if (bl->initial_test)
+ {
+ fprintf (file, ", init test: ");
+ print_simple_rtl (file, bl->initial_test);
+ }
+ fputc ('\n', file);
+
+ if (bl->final_value)
+ {
+ fprintf (file, " Final val: ");
+ print_simple_rtl (file, bl->final_value);
+ fputc ('\n', file);
+ }
+
+ if ((incr = biv_total_increment (bl)))
+ {
+ fprintf (file, " Total increment: ");
+ print_simple_rtl (file, incr);
+ fputc ('\n', file);
+ }
+
+ /* List the increments. */
+ for (i = 0, v = bl->biv; v; v = v->next_iv, i++)
+ {
+ fprintf (file, " Inc%d: insn %d, incr: ", i, INSN_UID (v->insn));
+ print_simple_rtl (file, v->add_val);
+ fputc ('\n', file);
+ }
+
+ /* List the givs. */
+ for (i = 0, v = bl->giv; v; v = v->next_iv, i++)
+ {
+ fprintf (file, " Giv%d: insn %d, benefit %d, ",
+ i, INSN_UID (v->insn), v->benefit);
+ if (v->giv_type == DEST_ADDR)
+ print_simple_rtl (file, v->mem);
+ else
+ print_simple_rtl (file, single_set (v->insn));
+ fputc ('\n', file);
+ }
+}
+
+
+static void
+loop_biv_dump (v, file, verbose)
+ const struct induction *v;
+ FILE *file;
+ int verbose;
+{
+ if (! v || ! file)
+ return;
+
+ fprintf (file,
+ "Biv %d: insn %d",
+ REGNO (v->dest_reg), INSN_UID (v->insn));
+ fprintf (file, " const ");
+ print_simple_rtl (file, v->add_val);
+
+ if (verbose && v->final_value)
+ {
+ fputc ('\n', file);
+ fprintf (file, " final ");
+ print_simple_rtl (file, v->final_value);
+ }
+
+ fputc ('\n', file);
+}
+
+
+static void
+loop_giv_dump (v, file, verbose)
+ const struct induction *v;
+ FILE *file;
+ int verbose;
+{
+ if (! v || ! file)
+ return;
+
+ if (v->giv_type == DEST_REG)
+ fprintf (file, "Giv %d: insn %d",
+ REGNO (v->dest_reg), INSN_UID (v->insn));
+ else
+ fprintf (file, "Dest address: insn %d",
+ INSN_UID (v->insn));
+
+ fprintf (file, " src reg %d benefit %d",
+ REGNO (v->src_reg), v->benefit);
+ fprintf (file, " lifetime %d",
+ v->lifetime);
+
+ if (v->replaceable)
+ fprintf (file, " replaceable");
+
+ if (v->no_const_addval)
+ fprintf (file, " ncav");
+
+ if (v->ext_dependent)
+ {
+ switch (GET_CODE (v->ext_dependent))
+ {
+ case SIGN_EXTEND:
+ fprintf (file, " ext se");
+ break;
+ case ZERO_EXTEND:
+ fprintf (file, " ext ze");
+ break;
+ case TRUNCATE:
+ fprintf (file, " ext tr");
+ break;
+ default:
+ abort ();
+ }
+ }
+
+ fputc ('\n', file);
+ fprintf (file, " mult ");
+ print_simple_rtl (file, v->mult_val);
+
+ fputc ('\n', file);
+ fprintf (file, " add ");
+ print_simple_rtl (file, v->add_val);
+
+ if (verbose && v->final_value)
+ {
+ fputc ('\n', file);
+ fprintf (file, " final ");
+ print_simple_rtl (file, v->final_value);
+ }
+
+ fputc ('\n', file);
+}
+
+
+void
+debug_ivs (loop)
+ const struct loop *loop;
+{
+ loop_ivs_dump (loop, stderr, 1);
+}
+
+
+void
+debug_iv_class (bl)
+ const struct iv_class *bl;
+{
+ loop_iv_class_dump (bl, stderr, 1);
+}
+
+
+void
+debug_biv (v)
+ const struct induction *v;
+{
+ loop_biv_dump (v, stderr, 1);
+}
+
+
+void
+debug_giv (v)
+ const struct induction *v;
+{
+ loop_giv_dump (v, stderr, 1);
+}
+
+
#define LOOP_BLOCK_NUM_1(INSN) \
((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
OSDN Git Service
