/* Perform various loop optimizations, including strength reduction.
- Copyright (C) 1987, 88, 89, 91-98, 1999 Free Software Foundation, Inc.
+ Copyright (C) 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997,
+ 1998, 1999, 2000 Free Software Foundation, Inc.
This file is part of GNU CC.
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
- to the beginning of the loop. Then it identifies basic and
+ to the beginning of the loop. Then it identifies basic and
general induction variables. Strength reduction is applied to the general
induction variables, and induction variable elimination is applied to
the basic induction variables.
#include "config.h"
#include "system.h"
#include "rtl.h"
+#include "tm_p.h"
#include "obstack.h"
#include "function.h"
#include "expr.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
#include "insn-config.h"
#include "insn-flags.h"
#include "regs.h"
-#include "hard-reg-set.h"
#include "recog.h"
#include "flags.h"
#include "real.h"
#include "loop.h"
+#include "cselib.h"
#include "except.h"
#include "toplev.h"
-/* Information about the loop being processed used to compute
- the number of loop iterations for loop unrolling and doloop
- optimization. */
-static struct loop_info this_loop_info;
-
/* Vector mapping INSN_UIDs to luids.
The luids are like uids but increase monotonically always.
We use them to see whether a jump comes from outside a given loop. */
/* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
number the insn is contained in. */
-int *uid_loop_num;
+struct loop **uid_loop;
/* 1 + largest uid of any insn. */
static int max_loop_num;
-/* Indexed by loop number, contains the first and last insn of each loop. */
-
-static rtx *loop_number_loop_starts, *loop_number_loop_ends;
-
-/* Likewise for the continue insn */
-static rtx *loop_number_loop_cont;
-
-/* The first code_label that is reached in every loop iteration.
- 0 when not computed yet, initially const0_rtx if a jump couldn't be
- followed.
- Also set to 0 when there is no such label before the NOTE_INSN_LOOP_CONT
- of this loop, or in verify_dominator, if a jump couldn't be followed. */
-static rtx *loop_number_cont_dominator;
-
-/* For each loop, gives the containing loop number, -1 if none. */
-
-int *loop_outer_loop;
-
-#ifdef HAVE_decrement_and_branch_on_count
-/* Records whether resource in use by inner loop. */
-
-int *loop_used_count_register;
-#endif /* HAVE_decrement_and_branch_on_count */
-
-/* Indexed by loop number, contains a nonzero value if the "loop" isn't
- really a loop (an insn outside the loop branches into it). */
-
-static char *loop_invalid;
-
-/* Indexed by loop number, links together all LABEL_REFs which refer to
- code labels outside the loop. Used by routines that need to know all
- loop exits, such as final_biv_value and final_giv_value.
-
- This does not include loop exits due to return instructions. This is
- because all bivs and givs are pseudos, and hence must be dead after a
- return, so the presense of a return does not affect any of the
- optimizations that use this info. It is simpler to just not include return
- instructions on this list. */
-
-rtx *loop_number_exit_labels;
-
-/* Indexed by loop number, counts the number of LABEL_REFs on
- loop_number_exit_labels for this loop and all loops nested inside it. */
-
-int *loop_number_exit_count;
-
/* Indexed by register number, contains the number of times the reg
is set during the loop being scanned.
During code motion, a negative value indicates a reg that has been
static int unknown_address_altered;
+/* The above doesn't count any readonly memory locations that are stored.
+ This does. */
+
+static int unknown_constant_address_altered;
+
/* Count of movable (i.e. invariant) instructions discovered in the loop. */
static int num_movables;
/* Bound on pseudo register number before loop optimization.
A pseudo has valid regscan info if its number is < max_reg_before_loop. */
-int max_reg_before_loop;
+unsigned int max_reg_before_loop;
+
+/* The value to pass to the next call of reg_scan_update. */
+static int loop_max_reg;
/* This obstack is used in product_cheap_p to allocate its rtl. It
may call gen_reg_rtx which, in turn, may reallocate regno_reg_rtx.
rtx set_dest; /* The destination of this SET. */
rtx dependencies; /* When INSN is libcall, this is an EXPR_LIST
of any registers used within the LIBCALL. */
- int consec; /* Number of consecutive following insns
+ int consec; /* Number of consecutive following insns
that must be moved with this one. */
- int regno; /* The register it sets */
+ unsigned int regno; /* The register it sets */
short lifetime; /* lifetime of that register;
may be adjusted when matching movables
that load the same value are found. */
that the reg is live outside the range from where it is set
to the following label. */
unsigned int done : 1; /* 1 inhibits further processing of this */
-
+
unsigned int partial : 1; /* 1 means this reg is used for zero-extending.
In particular, moving it does not make it
invariant. */
/* Forward declarations. */
-static void verify_dominator PROTO((int));
-static void find_and_verify_loops PROTO((rtx));
-static void mark_loop_jump PROTO((rtx, int));
-static void prescan_loop PROTO((rtx, rtx, struct loop_info *));
-static int reg_in_basic_block_p PROTO((rtx, rtx));
-static int consec_sets_invariant_p PROTO((rtx, int, rtx));
-static int labels_in_range_p PROTO((rtx, int));
-static void count_one_set PROTO((rtx, rtx, varray_type, rtx *));
-
-static void count_loop_regs_set PROTO((rtx, rtx, varray_type, varray_type,
- int *, int));
-static void note_addr_stored PROTO((rtx, rtx));
-static int loop_reg_used_before_p PROTO((rtx, rtx, rtx, rtx, rtx));
-static void scan_loop PROTO((rtx, rtx, rtx, int, int));
+static void verify_dominator PARAMS ((struct loop *));
+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 *));
+static int reg_in_basic_block_p PARAMS ((rtx, rtx));
+static int consec_sets_invariant_p PARAMS ((const struct loop *,
+ rtx, int, rtx));
+static int labels_in_range_p PARAMS ((rtx, int));
+static void count_one_set PARAMS ((rtx, rtx, varray_type, rtx *));
+
+static void count_loop_regs_set PARAMS ((rtx, rtx, varray_type, varray_type,
+ int *, 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 scan_loop PARAMS ((struct loop*, int));
#if 0
-static void replace_call_address PROTO((rtx, rtx, rtx));
+static void replace_call_address PARAMS ((rtx, rtx, rtx));
#endif
-static rtx skip_consec_insns PROTO((rtx, int));
-static int libcall_benefit PROTO((rtx));
-static void ignore_some_movables PROTO((struct movable *));
-static void force_movables PROTO((struct movable *));
-static void combine_movables PROTO((struct movable *, int));
-static int regs_match_p PROTO((rtx, rtx, struct movable *));
-static int rtx_equal_for_loop_p PROTO((rtx, rtx, struct movable *));
-static void add_label_notes PROTO((rtx, rtx));
-static void move_movables PROTO((struct movable *, int, int, rtx, rtx, int));
-static int count_nonfixed_reads PROTO((rtx));
-static void strength_reduce PROTO((rtx, rtx, rtx, int, rtx, rtx,
- struct loop_info *, rtx, int, int));
-static void find_single_use_in_loop PROTO((rtx, rtx, varray_type));
-static int valid_initial_value_p PROTO((rtx, rtx, int, rtx));
-static void find_mem_givs PROTO((rtx, rtx, int, int, rtx, rtx));
-static void record_biv PROTO((struct induction *, rtx, rtx, rtx, rtx, rtx *, int, int));
-static void check_final_value PROTO((struct induction *, rtx, rtx,
- unsigned HOST_WIDE_INT));
-static void record_giv PROTO((struct induction *, rtx, rtx, rtx, rtx, rtx, int, enum g_types, int, int, rtx *, rtx, rtx));
-static void update_giv_derive PROTO((rtx));
-static int basic_induction_var PROTO((rtx, enum machine_mode, rtx, rtx, rtx *, rtx *, rtx **));
-static rtx simplify_giv_expr PROTO((rtx, int *));
-static int general_induction_var PROTO((rtx, rtx *, rtx *, rtx *, int, int *));
-static int consec_sets_giv PROTO((int, rtx, rtx, rtx, rtx *, rtx *, rtx *));
-static int check_dbra_loop PROTO((rtx, int, rtx, struct loop_info *));
-static rtx express_from_1 PROTO((rtx, rtx, rtx));
-static rtx combine_givs_p PROTO((struct induction *, struct induction *));
-static void combine_givs PROTO((struct iv_class *));
+static rtx skip_consec_insns PARAMS ((rtx, int));
+static int libcall_benefit PARAMS ((rtx));
+static void ignore_some_movables PARAMS ((struct movable *));
+static void force_movables PARAMS ((struct movable *));
+static void combine_movables PARAMS ((struct movable *, int));
+static int regs_match_p PARAMS ((rtx, rtx, struct movable *));
+static int rtx_equal_for_loop_p PARAMS ((rtx, rtx, struct movable *));
+static void add_label_notes PARAMS ((rtx, rtx));
+static void move_movables PARAMS ((struct loop *loop, struct movable *,
+ int, int, int));
+static int count_nonfixed_reads PARAMS ((const struct loop *, rtx));
+static void strength_reduce PARAMS ((struct loop *, int, int));
+static void find_single_use_in_loop PARAMS ((rtx, rtx, varray_type));
+static int valid_initial_value_p PARAMS ((rtx, rtx, int, rtx));
+static void find_mem_givs PARAMS ((const struct loop *, rtx, rtx, int, int));
+static void record_biv PARAMS ((struct induction *, rtx, rtx, rtx, rtx, rtx *,
+ int, int));
+static void check_final_value PARAMS ((const struct loop *,
+ struct induction *));
+static void record_giv PARAMS ((const struct loop *, struct induction *,
+ rtx, rtx, rtx, rtx, rtx, int, enum g_types,
+ int, int, rtx *));
+static void update_giv_derive PARAMS ((const struct loop *, rtx));
+static int basic_induction_var PARAMS ((const struct loop *, rtx,
+ enum machine_mode, rtx, rtx,
+ rtx *, rtx *, rtx **));
+static rtx simplify_giv_expr PARAMS ((const struct loop *, rtx, int *));
+static int general_induction_var PARAMS ((const struct loop *loop, rtx, rtx *,
+ rtx *, rtx *, int, int *, enum machine_mode));
+static int consec_sets_giv PARAMS ((const struct loop *, int, rtx,
+ rtx, rtx, rtx *, rtx *, rtx *));
+static int check_dbra_loop PARAMS ((struct loop *, int));
+static rtx express_from_1 PARAMS ((rtx, rtx, rtx));
+static rtx combine_givs_p PARAMS ((struct induction *, struct induction *));
+static void combine_givs PARAMS ((struct iv_class *));
struct recombine_givs_stats;
-static int find_life_end PROTO((rtx, struct recombine_givs_stats *, rtx, rtx));
-static void recombine_givs PROTO((struct iv_class *, rtx, rtx, int));
-static int product_cheap_p PROTO((rtx, rtx));
-static int maybe_eliminate_biv PROTO((struct iv_class *, rtx, rtx, int, int, int));
-static int maybe_eliminate_biv_1 PROTO((rtx, rtx, struct iv_class *, int, rtx));
-static int last_use_this_basic_block PROTO((rtx, rtx));
-static void record_initial PROTO((rtx, rtx));
-static void update_reg_last_use PROTO((rtx, rtx));
-static rtx next_insn_in_loop PROTO((rtx, rtx, rtx, rtx));
-static void load_mems_and_recount_loop_regs_set PROTO((rtx, rtx, rtx,
- rtx, int *));
-static void load_mems PROTO((rtx, rtx, rtx, rtx));
-static int insert_loop_mem PROTO((rtx *, void *));
-static int replace_loop_mem PROTO((rtx *, void *));
-static int replace_label PROTO((rtx *, void *));
+static int find_life_end PARAMS ((rtx, struct recombine_givs_stats *,
+ rtx, rtx));
+static void recombine_givs PARAMS ((const struct loop *, struct iv_class *,
+ int));
+static int product_cheap_p PARAMS ((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));
+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 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_loop_reg PARAMS ((rtx *, void *));
+static void note_reg_stored PARAMS ((rtx, rtx, void *));
+static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
+static void try_swap_copy_prop PARAMS ((const struct loop *, rtx,
+ unsigned int));
+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));
typedef struct rtx_and_int {
rtx r;
&& INSN_LUID (INSN) >= INSN_LUID (START) \
&& INSN_LUID (INSN) <= INSN_LUID (END))
-#ifdef HAVE_decrement_and_branch_on_count
-/* Test whether BCT applicable and safe. */
-static void insert_bct PROTO((rtx, rtx, struct loop_info *));
-
-/* Auxiliary function that inserts the BCT pattern into the loop. */
-static void instrument_loop_bct PROTO((rtx, rtx, rtx));
-#endif /* HAVE_decrement_and_branch_on_count */
-
/* Indirect_jump_in_function is computed once per function. */
-int indirect_jump_in_function = 0;
-static int indirect_jump_in_function_p PROTO((rtx));
+static int indirect_jump_in_function;
+static int indirect_jump_in_function_p PARAMS ((rtx));
-static int compute_luids PROTO((rtx, rtx, int));
+static int compute_luids PARAMS ((rtx, rtx, int));
-static int biv_elimination_giv_has_0_offset PROTO((struct induction *,
+static int biv_elimination_giv_has_0_offset PARAMS ((struct induction *,
struct induction *, rtx));
\f
/* Relative gain of eliminating various kinds of operations. */
/* Cost of using a register, to normalize the benefits of a giv. */
static int reg_address_cost;
-
void
init_loop ()
{
add_cost = rtx_cost (gen_rtx_PLUS (word_mode, reg, reg), SET);
-#ifdef ADDRESS_COST
- reg_address_cost = ADDRESS_COST (reg);
-#else
- reg_address_cost = rtx_cost (reg, MEM);
-#endif
+ reg_address_cost = address_cost (reg, SImode);
/* We multiply by 2 to reconcile the difference in scale between
these two ways of computing costs. Otherwise the cost of a copy
(or 0 if none should be output). */
void
-loop_optimize (f, dumpfile, unroll_p, bct_p)
+loop_optimize (f, dumpfile, flags)
/* f is the first instruction of a chain of insns for one function */
rtx f;
FILE *dumpfile;
- int unroll_p, bct_p;
+ int flags;
{
register rtx insn;
register int i;
+ struct loops loops_data;
+ struct loops *loops = &loops_data;
+ struct loop_info *loops_info;
loop_dump_stream = dumpfile;
init_recog_no_volatile ();
max_reg_before_loop = max_reg_num ();
-
- moved_once = (char *) alloca (max_reg_before_loop);
- bzero (moved_once, max_reg_before_loop);
+ loop_max_reg = max_reg_before_loop;
regs_may_share = 0;
if (max_loop_num == 0)
return;
+ loops->num = max_loop_num;
+
+ moved_once = (char *) xcalloc (max_reg_before_loop, sizeof (char));
+
/* Get size to use for tables indexed by uids.
Leave some space for labels allocated by find_and_verify_loops. */
max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
- uid_luid = (int *) alloca (max_uid_for_loop * sizeof (int));
- uid_loop_num = (int *) alloca (max_uid_for_loop * sizeof (int));
-
- bzero ((char *) uid_luid, max_uid_for_loop * sizeof (int));
- bzero ((char *) uid_loop_num, max_uid_for_loop * sizeof (int));
-
- /* Allocate tables for recording each loop. We set each entry, so they need
- not be zeroed. */
- loop_number_loop_starts = (rtx *) alloca (max_loop_num * sizeof (rtx));
- loop_number_loop_ends = (rtx *) alloca (max_loop_num * sizeof (rtx));
- loop_number_loop_cont = (rtx *) alloca (max_loop_num * sizeof (rtx));
- loop_number_cont_dominator = (rtx *) alloca (max_loop_num * sizeof (rtx));
- loop_outer_loop = (int *) alloca (max_loop_num * sizeof (int));
- loop_invalid = (char *) alloca (max_loop_num * sizeof (char));
- loop_number_exit_labels = (rtx *) alloca (max_loop_num * sizeof (rtx));
- loop_number_exit_count = (int *) alloca (max_loop_num * sizeof (int));
-
-#ifdef HAVE_decrement_and_branch_on_count
- /* Allocate for BCT optimization */
- loop_used_count_register = (int *) alloca (max_loop_num * sizeof (int));
- bzero ((char *) loop_used_count_register, max_loop_num * sizeof (int));
-#endif /* HAVE_decrement_and_branch_on_count */
+ uid_luid = (int *) xcalloc (max_uid_for_loop, sizeof (int));
+ uid_loop = (struct loop **) xcalloc (max_uid_for_loop,
+ sizeof (struct loop *));
+
+ /* Allocate storage for array of loops. */
+ loops->array = (struct loop *)
+ xcalloc (loops->num, sizeof (struct loop));
/* Find and process each loop.
First, find them, and record them in order of their beginnings. */
- find_and_verify_loops (f);
+ find_and_verify_loops (f, loops);
+
+ /* Allocate and initialize auxiliary loop information. */
+ loops_info = xcalloc (loops->num, sizeof (struct loop_info));
+ for (i = 0; i < loops->num; i++)
+ loops->array[i].aux = loops_info + i;
/* Now find all register lifetimes. This must be done after
find_and_verify_loops, because it might reorder the insns in the
function. */
- reg_scan (f, max_reg_num (), 1);
+ reg_scan (f, max_reg_before_loop, 1);
/* This must occur after reg_scan so that registers created by gcse
will have entries in the register tables.
/* Now reset it to the actual size we need. See above. */
max_uid_for_loop = get_max_uid ();
- /* find_and_verify_loops has already called compute_luids, but it might
- have rearranged code afterwards, so we need to recompute the luids now. */
+ /* find_and_verify_loops has already called compute_luids, but it
+ might have rearranged code afterwards, so we need to recompute
+ the luids now. */
max_luid = compute_luids (f, NULL_RTX, 0);
/* Don't leave gaps in uid_luid for insns that have been
if (uid_luid[i] == 0)
uid_luid[i] = uid_luid[i - 1];
- /* Create a mapping from loops to BLOCK tree nodes. */
- if (unroll_p && write_symbols != NO_DEBUG)
- find_loop_tree_blocks ();
-
/* Determine if the function has indirect jump. On some systems
this prevents low overhead loop instructions from being used. */
indirect_jump_in_function = indirect_jump_in_function_p (f);
/* Now scan the loops, last ones first, since this means inner ones are done
before outer ones. */
- for (i = max_loop_num-1; i >= 0; i--)
- if (! loop_invalid[i] && loop_number_loop_ends[i])
- scan_loop (loop_number_loop_starts[i], loop_number_loop_ends[i],
- loop_number_loop_cont[i], unroll_p, bct_p);
+ for (i = max_loop_num - 1; i >= 0; i--)
+ {
+ struct loop *loop = &loops->array[i];
- /* If debugging and unrolling loops, we must replicate the tree nodes
- corresponding to the blocks inside the loop, so that the original one
- to one mapping will remain. */
- if (unroll_p && write_symbols != NO_DEBUG)
- unroll_block_trees ();
+ if (! loop->invalid && loop->end)
+ scan_loop (loop, flags);
+ }
+
+ /* If there were lexical blocks inside the loop, they have been
+ replicated. We will now have more than one NOTE_INSN_BLOCK_BEG
+ and NOTE_INSN_BLOCK_END for each such block. We must duplicate
+ the BLOCKs as well. */
+ if (write_symbols != NO_DEBUG)
+ reorder_blocks ();
end_alias_analysis ();
+
+ /* Clean up. */
+ free (moved_once);
+ free (uid_luid);
+ free (uid_loop);
+ free (loops_info);
+ free (loops->array);
}
\f
/* Returns the next insn, in execution order, after INSN. START and
END are the NOTE_INSN_LOOP_BEG and NOTE_INSN_LOOP_END for the loop,
- respectively. LOOP_TOP, if non-NULL, is the top of the loop in the
+ respectively. LOOP->TOP, if non-NULL, is the top of the loop in the
insn-stream; it is used with loops that are entered near the
bottom. */
static rtx
-next_insn_in_loop (insn, start, end, loop_top)
+next_insn_in_loop (loop, insn)
+ const struct loop *loop;
rtx insn;
- rtx start;
- rtx end;
- rtx loop_top;
{
insn = NEXT_INSN (insn);
- if (insn == end)
+ if (insn == loop->end)
{
- if (loop_top)
+ if (loop->top)
/* Go to the top of the loop, and continue there. */
- insn = loop_top;
+ insn = loop->top;
else
/* We're done. */
insn = NULL_RTX;
}
- if (insn == start)
+ if (insn == loop->scan_start)
/* We're done. */
insn = NULL_RTX;
return insn;
}
-/* Optimize one loop whose start is LOOP_START and end is END.
- LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
- NOTE_INSN_LOOP_END.
- LOOP_CONT is the NOTE_INSN_LOOP_CONT. */
+/* Optimize one loop described by LOOP. */
/* ??? Could also move memory writes out of loops if the destination address
is invariant, the source is invariant, the memory write is not volatile,
write, then we can also mark the memory read as invariant. */
static void
-scan_loop (loop_start, end, loop_cont, unroll_p, bct_p)
- rtx loop_start, end, loop_cont;
- int unroll_p, bct_p;
+scan_loop (loop, flags)
+ struct loop *loop;
+ int flags;
{
register int i;
+ rtx loop_start = loop->start;
+ rtx loop_end = loop->end;
+ /* Additional information about the current loop being processed
+ that is used to compute the number of loop iterations for loop
+ unrolling and doloop optimization. */
+ struct loop_info *loop_info = LOOP_INFO (loop);
rtx p;
/* 1 if we are scanning insns that could be executed zero times. */
int maybe_never = 0;
/* 1 if we are scanning insns that might never be executed
due to a subroutine call which might exit before they are reached. */
int call_passed = 0;
- /* For a rotated loop that is entered near the bottom,
- this is the label at the top. Otherwise it is zero. */
- rtx loop_top = 0;
/* Jump insn that enters the loop, or 0 if control drops in. */
rtx loop_entry_jump = 0;
- /* Place in the loop where control enters. */
- rtx scan_start;
/* Number of insns in the loop. */
int insn_count;
int in_libcall = 0;
int tem;
- rtx temp;
+ rtx temp, update_start, update_end;
/* The SET from an insn, if it is the only SET in the insn. */
rtx set, set1;
/* Chain describing insns movable in current loop. */
/* Nonzero if we are scanning instructions in a sub-loop. */
int loop_depth = 0;
int nregs;
- struct loop_info *loop_info = &this_loop_info;
+
+ loop->top = 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
Note that if we mistakenly think that a loop is entered at the top
when, in fact, it is entered at the exit test, the only effect will be
slightly poorer optimization. Making the opposite error can generate
- incorrect code. Since very few loops now start with a jump to the
+ incorrect code. Since very few loops now start with a jump to the
exit test, the code here to detect that case is very conservative. */
for (p = NEXT_INSN (loop_start);
- p != end
- && GET_CODE (p) != CODE_LABEL && GET_RTX_CLASS (GET_CODE (p)) != 'i'
+ p != loop_end
+ && GET_CODE (p) != CODE_LABEL && ! INSN_P (p)
&& (GET_CODE (p) != NOTE
|| (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
&& NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
p = NEXT_INSN (p))
;
- scan_start = p;
+ loop->scan_start = p;
/* Set up variables describing this loop. */
- prescan_loop (loop_start, end, loop_info);
+ prescan_loop (loop);
threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
/* If loop has a jump before the first label,
the true entry is the target of that jump.
Start scan from there.
- But record in LOOP_TOP the place where the end-test jumps
+ But record in LOOP->TOP the place where the end-test jumps
back to so we can scan that after the end of the loop. */
if (GET_CODE (p) == JUMP_INSN)
{
loop_entry_jump = p;
/* Loop entry must be unconditional jump (and not a RETURN) */
- if (simplejump_p (p)
+ if (any_uncondjump_p (p)
&& JUMP_LABEL (p) != 0
/* Check to see whether the jump actually
jumps out of the loop (meaning it's no loop).
do {..} while (0). If this label was generated previously
by loop, we can't tell anything about it and have to reject
the loop. */
- && INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, end))
+ && INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, loop_end))
{
- loop_top = next_label (scan_start);
- scan_start = JUMP_LABEL (p);
+ loop->top = next_label (loop->scan_start);
+ loop->scan_start = JUMP_LABEL (p);
}
}
- /* If SCAN_START was an insn created by loop, we don't know its luid
+ /* If LOOP->SCAN_START was an insn created by loop, we don't know its luid
as required by loop_reg_used_before_p. So skip such loops. (This
- test may never be true, but it's best to play it safe.)
+ test may never be true, but it's best to play it safe.)
Also, skip loops where we do not start scanning at a label. This
test also rejects loops starting with a JUMP_INSN that failed the
test above. */
- if (INSN_UID (scan_start) >= max_uid_for_loop
- || GET_CODE (scan_start) != CODE_LABEL)
+ if (INSN_UID (loop->scan_start) >= max_uid_for_loop
+ || GET_CODE (loop->scan_start) != CODE_LABEL)
{
if (loop_dump_stream)
fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
- INSN_UID (loop_start), INSN_UID (end));
+ INSN_UID (loop_start), INSN_UID (loop_end));
return;
}
/* Count number of times each reg is set during this loop.
Set VARRAY_CHAR (may_not_optimize, I) if it is not safe to move out
the setting of register I. Set VARRAY_RTX (reg_single_usage, I). */
-
+
/* Allocate extra space for REGS that might be created by
load_mems. We allocate a little extra slop as well, in the hopes
that even after the moving of movables creates some new registers
VARRAY_CHAR_INIT (may_not_optimize, nregs, "may_not_optimize");
VARRAY_RTX_INIT (reg_single_usage, nregs, "reg_single_usage");
- count_loop_regs_set (loop_top ? loop_top : loop_start, end,
+ count_loop_regs_set (loop->top ? loop->top : loop->start, loop->end,
may_not_optimize, reg_single_usage, &insn_count, nregs);
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
VARRAY_CHAR (may_not_optimize, i) = 1;
#endif
- bcopy ((char *) &set_in_loop->data,
+ bcopy ((char *) &set_in_loop->data,
(char *) &n_times_set->data, nregs * sizeof (int));
if (loop_dump_stream)
{
fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
- INSN_UID (loop_start), INSN_UID (end), insn_count);
- if (loop_info->cont)
+ INSN_UID (loop_start), INSN_UID (loop_end), insn_count);
+ if (loop->cont)
fprintf (loop_dump_stream, "Continue at insn %d.\n",
- INSN_UID (loop_info->cont));
+ INSN_UID (loop->cont));
}
/* Scan through the loop finding insns that are safe to move.
When MAYBE_NEVER is 0, all insns will be executed at least once
so that is not a problem. */
- for (p = next_insn_in_loop (scan_start, scan_start, end, loop_top);
+ for (p = next_insn_in_loop (loop, loop->scan_start);
p != NULL_RTX;
- p = next_insn_in_loop (p, scan_start, end, loop_top))
+ p = next_insn_in_loop (loop, p))
{
- if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
- && find_reg_note (p, REG_LIBCALL, NULL_RTX))
+ if (INSN_P (p) && find_reg_note (p, REG_LIBCALL, NULL_RTX))
in_libcall = 1;
- else if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
- && find_reg_note (p, REG_RETVAL, NULL_RTX))
+ else if (INSN_P (p) && find_reg_note (p, REG_RETVAL, NULL_RTX))
in_libcall = 0;
if (GET_CODE (p) == INSN
temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
if (temp)
src = XEXP (temp, 0), move_insn = 1;
- else
+ else
{
temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
if (temp && CONSTANT_P (XEXP (temp, 0)))
! reg_in_basic_block_p (p, SET_DEST (set))
/* And the set is not guaranteed to be executed one
the loop starts, or the value before the set is
- needed before the set occurs...
+ needed before the set occurs...
??? Note we have quadratic behaviour here, mitigated
by the fact that the previous test will often fail for
each time for register usage, we should build tables
of the register usage and use them here instead. */
&& (maybe_never
- || loop_reg_used_before_p (set, p, loop_start,
- scan_start, end)))
- /* It is unsafe to move the set.
+ || loop_reg_used_before_p (loop, set, p)))
+ /* It is unsafe to move the set.
This code used to consider it OK to move a set of a variable
which was not created by the user and not used in an exit test.
That behavior is incorrect and was removed. */
;
- else if ((tem = invariant_p (src))
+ else if ((tem = loop_invariant_p (loop, src))
&& (dependencies == 0
- || (tem2 = invariant_p (dependencies)) != 0)
- && (VARRAY_INT (set_in_loop,
+ || (tem2 = loop_invariant_p (loop, dependencies)) != 0)
+ && (VARRAY_INT (set_in_loop,
REGNO (SET_DEST (set))) == 1
|| (tem1
- = consec_sets_invariant_p
- (SET_DEST (set),
+ = consec_sets_invariant_p
+ (loop, SET_DEST (set),
VARRAY_INT (set_in_loop, REGNO (SET_DEST (set))),
p)))
/* If the insn can cause a trap (such as divide by zero),
can be combined as long as they are both in the loop, but
we move one of them outside the loop. For large loops,
this can lose. The most common case of this is the address
- of a function being called.
+ of a function being called.
Therefore, if this register is marked as being used exactly
once if we are in a loop with calls (a "large loop"), see if
we can replace the usage of this register with the source
- of this SET. If we can, delete this insn.
+ of this SET. If we can, delete this insn.
Don't do this if P has a REG_RETVAL note or if we have
SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
might span a call. */
&& ! modified_between_p (SET_SRC (set), p,
VARRAY_RTX
- (reg_single_usage, regno))
+ (reg_single_usage, regno))
&& no_labels_between_p (p, VARRAY_RTX (reg_single_usage, regno))
&& validate_replace_rtx (SET_DEST (set), SET_SRC (set),
VARRAY_RTX
- (reg_single_usage, regno)))
+ (reg_single_usage, regno)))
{
/* Replace any usage in a REG_EQUAL note. Must copy the
new source, so that we don't get rtx sharing between the
SET_SOURCE and REG_NOTES of insn p. */
REG_NOTES (VARRAY_RTX (reg_single_usage, regno))
= replace_rtx (REG_NOTES (VARRAY_RTX
- (reg_single_usage, regno)),
+ (reg_single_usage, regno)),
SET_DEST (set), copy_rtx (SET_SRC (set)));
-
+
PUT_CODE (p, NOTE);
NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
NOTE_SOURCE_FILE (p) = 0;
m->dependencies = dependencies;
m->set_dest = SET_DEST (set);
m->force = 0;
- m->consec = VARRAY_INT (set_in_loop,
+ m->consec = VARRAY_INT (set_in_loop,
REGNO (SET_DEST (set))) - 1;
m->done = 0;
m->forces = 0;
m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
m->savemode = VOIDmode;
m->regno = regno;
- /* Set M->cond if either invariant_p or consec_sets_invariant_p
- returned 2 (only conditionally invariant). */
+ /* Set M->cond if either loop_invariant_p
+ or consec_sets_invariant_p returned 2
+ (only conditionally invariant). */
m->cond = ((tem | tem1 | tem2) > 1);
- m->global = (uid_luid[REGNO_LAST_UID (regno)] > INSN_LUID (end)
+ m->global = (uid_luid[REGNO_LAST_UID (regno)]
+ > INSN_LUID (loop_end)
|| uid_luid[REGNO_FIRST_UID (regno)] < INSN_LUID (loop_start));
m->match = 0;
m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
assumption. */
m->global = (INSN_UID (p) >= max_uid_for_loop
|| (uid_luid[REGNO_LAST_UID (regno)]
- > INSN_LUID (end))
+ > INSN_LUID (loop_end))
|| (uid_luid[REGNO_FIRST_UID (regno)]
< INSN_LUID (p))
|| (labels_in_range_p
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. */
- && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop_top
- && NEXT_INSN (NEXT_INSN (p)) == end
- && simplejump_p (p)))
+ && ! (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == loop->top
+ && NEXT_INSN (NEXT_INSN (p)) == loop_end
+ && any_uncondjump_p (p)))
maybe_never = 1;
else if (GET_CODE (p) == NOTE)
{
all together as the priority of the first. */
combine_movables (movables, nregs);
-
+
/* Now consider each movable insn to decide whether it is worth moving.
Store 0 in set_in_loop for each reg that is moved.
optimizing for code size. */
if (! optimize_size)
- move_movables (movables, threshold,
- insn_count, loop_start, end, nregs);
+ move_movables (loop, movables, threshold, insn_count, nregs);
/* Now candidates that still are negative are those not moved.
Change set_in_loop to indicate that those are not actually invariant. */
/* 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 (scan_start, end, loop_top,
- loop_start, &insn_count);
+ load_mems_and_recount_loop_regs_set (loop, &insn_count);
+
+ 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 ();
if (flag_strength_reduce)
{
+ if (update_end && GET_CODE (update_end) == CODE_LABEL)
+ /* Ensure our label doesn't go away. */
+ LABEL_NUSES (update_end)++;
+
the_movables = movables;
- strength_reduce (scan_start, end, loop_top,
- insn_count, loop_start, end,
- loop_info, loop_cont, unroll_p, bct_p);
+ strength_reduce (loop, insn_count, 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);
}
VARRAY_FREE (reg_single_usage);
&& ! reg_mentioned_p (in_this, not_in_this))
*output = gen_rtx_EXPR_LIST (VOIDmode, in_this, *output);
return;
-
+
default:
break;
}
/* Return 1 if all uses of REG
are between INSN and the end of the basic block. */
-static int
+static int
reg_in_basic_block_p (insn, reg)
rtx insn, reg;
{
case BARRIER:
/* It's the end of the basic block, so we lose. */
return 0;
-
+
default:
break;
}
}
- /* The "last use" doesn't follow the "first use"?? */
- abort ();
+ /* The "last use" that was recorded can't be found after the first
+ use. This can happen when the last use was deleted while
+ processing an inner loop, this inner loop was then completely
+ unrolled, and the outer loop is always exited after the inner loop,
+ so that everything after the first use becomes a single basic block. */
+ return 1;
}
\f
/* Compute the benefit of eliminating the insns in the block whose
rtx temp;
/* If first insn of libcall sequence, skip to end. */
- /* Do this at start of loop, since INSN is guaranteed to
+ /* Do this at start of loop, since INSN is guaranteed to
be an insn here. */
if (GET_CODE (insn) != NOTE
&& (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
insn = XEXP (temp, 0);
- do insn = NEXT_INSN (insn);
+ do
+ insn = NEXT_INSN (insn);
while (GET_CODE (insn) == NOTE);
}
m1->done = 1;
}
}
-}
+}
/* For each movable insn, see if the reg that it loads
leads when it dies right into another conditionally movable insn.
int nregs;
{
register struct movable *m;
- char *matched_regs = (char *) alloca (nregs);
+ char *matched_regs = (char *) xmalloc (nregs);
enum machine_mode mode;
/* Regs that are set more than once are not allowed to match
/* Perhaps testing m->consec_sets would be more appropriate here? */
for (m = movables; m; m = m->next)
- if (m->match == 0 && VARRAY_INT (n_times_set, m->regno) == 1 && !m->partial)
+ if (m->match == 0 && VARRAY_INT (n_times_set, m->regno) == 1
+ && !m->partial)
{
register struct movable *m1;
int regno = m->regno;
{
/* First one: don't check for overlap, just record it. */
m0 = m;
- continue;
+ continue;
}
/* Make sure they extend to the same mode.
(Almost always true.) */
if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
- continue;
+ continue;
/* We already have one: check for overlap with those
already combined together. */
m->done = 1;
m->match = m0;
- overlap: ;
+ overlap:
+ ;
}
}
+
+ /* Clean up. */
+ free (matched_regs);
}
\f
/* Return 1 if regs X and Y will become the same if moved. */
rtx x, y;
struct movable *movables;
{
- int xn = REGNO (x);
- int yn = REGNO (y);
+ unsigned int xn = REGNO (x);
+ unsigned int yn = REGNO (y);
struct movable *mx, *my;
for (mx = movables; mx; mx = mx->next)
other throughout. */
static void
-move_movables (movables, threshold, insn_count, loop_start, end, nregs)
+move_movables (loop, movables, threshold, insn_count, nregs)
+ struct loop *loop;
struct movable *movables;
int threshold;
int insn_count;
- rtx loop_start;
- rtx end;
int nregs;
{
rtx new_start = 0;
register struct movable *m;
register rtx p;
+ rtx loop_start = loop->start;
+ rtx loop_end = loop->end;
/* Map of pseudo-register replacements to handle combining
when we move several insns that load the same value
into different pseudo-registers. */
- rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx));
- char *already_moved = (char *) alloca (nregs);
-
- bzero (already_moved, nregs);
- bzero ((char *) reg_map, nregs * sizeof (rtx));
+ rtx *reg_map = (rtx *) xcalloc (nregs, sizeof (rtx));
+ char *already_moved = (char *) xcalloc (nregs, sizeof (char));
num_movables = 0;
if (!m->done
&& (! m->cond
- || (1 == invariant_p (m->set_src)
+ || (1 == loop_invariant_p (loop, m->set_src)
&& (m->dependencies == 0
- || 1 == invariant_p (m->dependencies))
+ || 1 == loop_invariant_p (loop, m->dependencies))
&& (m->consec == 0
- || 1 == consec_sets_invariant_p (m->set_dest,
+ || 1 == consec_sets_invariant_p (loop, m->set_dest,
m->consec + 1,
m->insn))))
&& (! m->forces || m->forces->done))
rtx i1, temp;
/* If first insn of libcall sequence, skip to end. */
- /* Do this at start of loop, since p is guaranteed to
+ /* Do this at start of loop, since p is guaranteed to
be an insn here. */
if (GET_CODE (p) != NOTE
&& (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
&& GET_CODE (PATTERN (next)) == USE)
&& GET_CODE (next) != NOTE)
break;
-
+
/* If that is the call, this may be the insn
that loads the function address.
rtx reg = m->set_dest;
rtx sequence;
rtx tem;
-
+
start_sequence ();
tem = expand_binop
(GET_MODE (reg), and_optab, reg,
may cause problems with later optimization passes.
It is possible for cse to create such notes
like this as a result of record_jump_cond. */
-
+
if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
- && ! invariant_p (XEXP (temp, 0)))
+ && ! loop_invariant_p (loop, XEXP (temp, 0)))
remove_note (i1, temp);
}
We can't use the moved insn because it is out of range
in uid_luid. Only the old insns have luids. */
REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
- if (uid_luid[REGNO_LAST_UID (regno)] < INSN_LUID (end))
- REGNO_LAST_UID (regno) = INSN_UID (end);
+ if (uid_luid[REGNO_LAST_UID (regno)] < INSN_LUID (loop_end))
+ REGNO_LAST_UID (regno) = INSN_UID (loop_end);
/* Combine with this moved insn any other matching movables. */
reg_map[m1->regno]
= gen_lowpart_common (GET_MODE (m1->set_dest),
m->set_dest);
-
+
/* Get rid of the matching insn
and prevent further processing of it. */
m1->done = 1;
/* Go through all the instructions in the loop, making
all the register substitutions scheduled in REG_MAP. */
- for (p = new_start; p != end; p = NEXT_INSN (p))
+ for (p = new_start; p != loop_end; p = NEXT_INSN (p))
if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
|| GET_CODE (p) == CALL_INSN)
{
replace_regs (REG_NOTES (p), reg_map, nregs, 0);
INSN_CODE (p) = -1;
}
+
+ /* Clean up. */
+ free (reg_map);
+ free (already_moved);
}
\f
#if 0
abort ();
XEXP (x, 0) = addr;
return;
-
+
default:
break;
}
{
if (fmt[i] == 'e')
replace_call_address (XEXP (x, i), reg, addr);
- if (fmt[i] == 'E')
+ else if (fmt[i] == 'E')
{
register int j;
for (j = 0; j < XVECLEN (x, i); j++)
in the rtx X. */
static int
-count_nonfixed_reads (x)
+count_nonfixed_reads (loop, x)
+ const struct loop *loop;
rtx x;
{
register enum rtx_code code;
return 0;
case MEM:
- return ((invariant_p (XEXP (x, 0)) != 1)
- + count_nonfixed_reads (XEXP (x, 0)));
-
+ return ((loop_invariant_p (loop, XEXP (x, 0)) != 1)
+ + count_nonfixed_reads (loop, XEXP (x, 0)));
+
default:
break;
}
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
- value += count_nonfixed_reads (XEXP (x, i));
+ value += count_nonfixed_reads (loop, XEXP (x, i));
if (fmt[i] == 'E')
{
register int j;
for (j = 0; j < XVECLEN (x, i); j++)
- value += count_nonfixed_reads (XVECEXP (x, i, j));
+ value += count_nonfixed_reads (loop, XVECEXP (x, i, j));
}
}
return value;
}
-
\f
#if 0
/* P is an instruction that sets a register to the result of a ZERO_EXTEND.
#endif
\f
/* Scan a loop setting the elements `cont', `vtop', `loops_enclosed',
- `has_call', `has_volatile', and `has_tablejump' within LOOP_INFO.
- Set the global variables `unknown_address_altered' and
- `num_mem_sets'. Also, fill in the array `loop_mems' and the list
- `loop_store_mems'. */
+ `has_call', `has_volatile', and `has_tablejump' within LOOP.
+ Set the global variables `unknown_address_altered',
+ `unknown_constant_address_altered', and `num_mem_sets'. Also, fill
+ in the array `loop_mems' and the list `loop_store_mems'. */
static void
-prescan_loop (start, end, loop_info)
- rtx start, end;
- struct loop_info *loop_info;
+prescan_loop (loop)
+ struct loop *loop;
{
register int level = 1;
rtx insn;
+ struct loop_info *loop_info = LOOP_INFO (loop);
+ rtx start = loop->start;
+ rtx end = loop->end;
/* The label after END. Jumping here is just like falling off the
end of the loop. We use next_nonnote_insn instead of next_label
as a hedge against the (pathological) case where some actual insn
might end up between the two. */
rtx exit_target = next_nonnote_insn (end);
- loop_info->num = uid_loop_num [INSN_UID (start)];
loop_info->has_indirect_jump = indirect_jump_in_function;
loop_info->has_call = 0;
loop_info->has_volatile = 0;
loop_info->has_tablejump = 0;
- loop_info->loops_enclosed = 1;
loop_info->has_multiple_exit_targets = 0;
- loop_info->cont = 0;
- loop_info->vtop = 0;
+ loop->cont = 0;
+ loop->vtop = 0;
+ loop->level = 1;
unknown_address_altered = 0;
+ unknown_constant_address_altered = 0;
loop_store_mems = NULL_RTX;
first_loop_store_insn = NULL_RTX;
loop_mems_idx = 0;
{
++level;
/* Count number of loops contained in this one. */
- loop_info->loops_enclosed++;
+ loop->level++;
}
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
{
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
{
if (level == 1)
- loop_info->cont = insn;
+ loop->cont = insn;
}
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP)
{
start. Thus, we can assume that the loop condition
was true when the loop was entered. */
if (level == 1)
- loop_info->vtop = insn;
+ loop->vtop = insn;
}
}
else if (GET_CODE (insn) == CALL_INSN)
&& (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_VEC))
loop_info->has_tablejump = 1;
-
- note_stores (PATTERN (insn), note_addr_stored);
+
+ note_stores (PATTERN (insn), note_addr_stored, NULL);
if (! first_loop_store_insn && loop_store_mems)
first_loop_store_insn = insn;
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;
- }
- }
+ 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);
+ label1 = label2;
+ label2 = NULL_RTX;
+ }
+ while (label1);
}
}
else if (GET_CODE (insn) == RETURN)
/* Now, rescan the loop, setting up the LOOP_MEMS array. */
if (/* We can't tell what MEMs are aliased by what. */
- !unknown_address_altered
+ ! unknown_address_altered
/* An exception thrown by a called function might land us
anywhere. */
- && !loop_info->has_call
+ && ! loop_info->has_call
/* We don't want loads for MEMs moved to a location before the
one at which their stack memory becomes allocated. (Note
that this is not a problem for malloc, etc., since those
require actual function calls. */
- && !current_function_calls_alloca
+ && ! current_function_calls_alloca
/* There are ways to leave the loop other than falling off the
end. */
- && !loop_info->has_multiple_exit_targets)
+ && ! loop_info->has_multiple_exit_targets)
for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
insn = NEXT_INSN (insn))
for_each_rtx (&insn, insert_loop_mem, 0);
}
\f
-/* LOOP_NUMBER_CONT_DOMINATOR is now the last label between the loop start
+/* LOOP->CONT_DOMINATOR is now the last label between the loop start
and the continue note that is a the destination of a (cond)jump after
the continue note. If there is any (cond)jump between the loop start
- and what we have so far as LOOP_NUMBER_CONT_DOMINATOR that has a
- target between LOOP_DOMINATOR and the continue note, move
- LOOP_NUMBER_CONT_DOMINATOR forward to that label; if a jump's
- destination cannot be determined, clear LOOP_NUMBER_CONT_DOMINATOR. */
+ and what we have so far as LOOP->CONT_DOMINATOR that has a
+ target between LOOP->DOMINATOR and the continue note, move
+ LOOP->CONT_DOMINATOR forward to that label; if a jump's
+ destination cannot be determined, clear LOOP->CONT_DOMINATOR. */
static void
-verify_dominator (loop_number)
- int loop_number;
+verify_dominator (loop)
+ struct loop *loop;
{
rtx insn;
- if (! loop_number_cont_dominator[loop_number])
+ if (! loop->cont_dominator)
/* This can happen for an empty loop, e.g. in
gcc.c-torture/compile/920410-2.c */
return;
- if (loop_number_cont_dominator[loop_number] == const0_rtx)
+ if (loop->cont_dominator == const0_rtx)
{
- loop_number_cont_dominator[loop_number] = 0;
+ loop->cont_dominator = 0;
return;
}
- for (insn = loop_number_loop_starts[loop_number];
- insn != loop_number_cont_dominator[loop_number];
+ for (insn = loop->start; insn != loop->cont_dominator;
insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) == JUMP_INSN
/* If it is not a jump we can easily understand or for
which we do not have jump target information in the JUMP_LABEL
field (consider ADDR_VEC and ADDR_DIFF_VEC insns), then clear
- LOOP_NUMBER_CONT_DOMINATOR. */
- if ((! condjump_p (insn)
- && ! condjump_in_parallel_p (insn))
+ LOOP->CONT_DOMINATOR. */
+ if (! any_condjump_p (insn)
|| label == NULL_RTX)
{
- loop_number_cont_dominator[loop_number] = NULL_RTX;
+ loop->cont_dominator = NULL_RTX;
return;
}
label_luid = INSN_LUID (label);
- if (label_luid < INSN_LUID (loop_number_loop_cont[loop_number])
+ if (label_luid < INSN_LUID (loop->cont)
&& (label_luid
- > INSN_LUID (loop_number_cont_dominator[loop_number])))
- loop_number_cont_dominator[loop_number] = label;
+ > INSN_LUID (loop->cont)))
+ loop->cont_dominator = label;
}
}
}
to from outside the loop. */
static void
-find_and_verify_loops (f)
+find_and_verify_loops (f, loops)
rtx f;
+ struct loops *loops;
{
- rtx insn, label;
- int current_loop = -1;
- int next_loop = -1;
- int loop;
+ rtx insn;
+ rtx label;
+ int num_loops;
+ struct loop *current_loop;
+ struct loop *next_loop;
+ struct loop *loop;
+
+ num_loops = loops->num;
compute_luids (f, NULL_RTX, 0);
/* If there are jumps to undefined labels,
treat them as jumps out of any/all loops.
This also avoids writing past end of tables when there are no loops. */
- uid_loop_num[0] = -1;
+ uid_loop[0] = NULL;
/* Find boundaries of loops, mark which loops are contained within
loops, and invalidate loops that have setjmp. */
+ num_loops = 0;
+ current_loop = NULL;
for (insn = f; insn; insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) == NOTE)
switch (NOTE_LINE_NUMBER (insn))
{
case NOTE_INSN_LOOP_BEG:
- loop_number_loop_starts[++next_loop] = insn;
- loop_number_loop_ends[next_loop] = 0;
- loop_number_loop_cont[next_loop] = 0;
- loop_number_cont_dominator[next_loop] = 0;
- loop_outer_loop[next_loop] = current_loop;
- loop_invalid[next_loop] = 0;
- loop_number_exit_labels[next_loop] = 0;
- loop_number_exit_count[next_loop] = 0;
+ next_loop = loops->array + num_loops;
+ next_loop->num = num_loops;
+ num_loops++;
+ next_loop->start = insn;
+ next_loop->outer = current_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 != -1; loop = loop_outer_loop[loop])
+ for (loop = current_loop; loop; loop = loop->outer)
{
- loop_invalid[loop] = 1;
+ loop->invalid = 1;
if (loop_dump_stream)
fprintf (loop_dump_stream,
"\nLoop at %d ignored due to setjmp.\n",
- INSN_UID (loop_number_loop_starts[loop]));
+ INSN_UID (loop->start));
}
break;
case NOTE_INSN_LOOP_CONT:
- loop_number_loop_cont[current_loop] = insn;
+ current_loop->cont = insn;
break;
case NOTE_INSN_LOOP_END:
- if (current_loop == -1)
+ if (! current_loop)
abort ();
- loop_number_loop_ends[current_loop] = insn;
+ current_loop->end = insn;
verify_dominator (current_loop);
- current_loop = loop_outer_loop[current_loop];
+ current_loop = current_loop->outer;
break;
default:
break;
}
/* If for any loop, this is a jump insn between the NOTE_INSN_LOOP_CONT
- and NOTE_INSN_LOOP_END notes, update loop_number_loop_dominator. */
+ and NOTE_INSN_LOOP_END notes, update loop->dominator. */
else if (GET_CODE (insn) == JUMP_INSN
&& GET_CODE (PATTERN (insn)) != RETURN
- && current_loop >= 0)
+ && current_loop)
{
- int this_loop_num;
rtx label = JUMP_LABEL (insn);
- if (! condjump_p (insn) && ! condjump_in_parallel_p (insn))
+ if (! any_condjump_p (insn))
label = NULL_RTX;
- this_loop_num = current_loop;
+ loop = current_loop;
do
{
/* First see if we care about this loop. */
- if (loop_number_loop_cont[this_loop_num]
- && loop_number_cont_dominator[this_loop_num] != const0_rtx)
+ if (loop->cont && loop->cont_dominator != const0_rtx)
{
/* If the jump destination is not known, invalidate
- loop_number_const_dominator. */
+ loop->const_dominator. */
if (! label)
- loop_number_cont_dominator[this_loop_num] = const0_rtx;
+ loop->cont_dominator = const0_rtx;
else
/* Check if the destination is between loop start and
cont. */
if ((INSN_LUID (label)
- < INSN_LUID (loop_number_loop_cont[this_loop_num]))
+ < INSN_LUID (loop->cont))
&& (INSN_LUID (label)
- > INSN_LUID (loop_number_loop_starts[this_loop_num]))
+ > INSN_LUID (loop->start))
/* And if there is no later destination already
recorded. */
- && (! loop_number_cont_dominator[this_loop_num]
+ && (! loop->cont_dominator
|| (INSN_LUID (label)
- > INSN_LUID (loop_number_cont_dominator
- [this_loop_num]))))
- loop_number_cont_dominator[this_loop_num] = label;
+ > INSN_LUID (loop->cont_dominator))))
+ loop->cont_dominator = label;
}
- this_loop_num = loop_outer_loop[this_loop_num];
+ loop = loop->outer;
}
- while (this_loop_num >= 0);
+ while (loop);
}
/* Note that this will mark the NOTE_INSN_LOOP_END note as being in the
enclosing loop, but this doesn't matter. */
- uid_loop_num[INSN_UID (insn)] = current_loop;
+ uid_loop[INSN_UID (insn)] = current_loop;
}
/* Any loop containing a label used in an initializer must be invalidated,
for (label = forced_labels; label; label = XEXP (label, 1))
{
- int loop_num;
-
- for (loop_num = uid_loop_num[INSN_UID (XEXP (label, 0))];
- loop_num != -1;
- loop_num = loop_outer_loop[loop_num])
- loop_invalid[loop_num] = 1;
+ for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
+ loop; loop = loop->outer)
+ loop->invalid = 1;
}
/* Any loop containing a label used for an exception handler must be
for (label = exception_handler_labels; label; label = XEXP (label, 1))
{
- int loop_num;
-
- for (loop_num = uid_loop_num[INSN_UID (XEXP (label, 0))];
- loop_num != -1;
- loop_num = loop_outer_loop[loop_num])
- loop_invalid[loop_num] = 1;
+ for (loop = uid_loop[INSN_UID (XEXP (label, 0))];
+ loop; loop = loop->outer)
+ loop->invalid = 1;
}
/* Now scan all insn's in the function. If any JUMP_INSN branches into a
anywhere.
Also look for blocks of code ending in an unconditional branch that
- exits the loop. If such a block is surrounded by a conditional
+ exits the loop. If such a block is surrounded by a conditional
branch around the block, move the block elsewhere (see below) and
invert the jump to point to the code block. This may eliminate a
label in our loop and will simplify processing by both us and a
possible second cse pass. */
for (insn = f; insn; insn = NEXT_INSN (insn))
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ if (INSN_P (insn))
{
- int this_loop_num = uid_loop_num[INSN_UID (insn)];
+ struct loop *this_loop = uid_loop[INSN_UID (insn)];
if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
{
rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
if (note)
{
- int loop_num;
-
- for (loop_num = uid_loop_num[INSN_UID (XEXP (note, 0))];
- loop_num != -1;
- loop_num = loop_outer_loop[loop_num])
- loop_invalid[loop_num] = 1;
+ for (loop = uid_loop[INSN_UID (XEXP (note, 0))];
+ loop; loop = loop->outer)
+ loop->invalid = 1;
}
}
if (GET_CODE (insn) != JUMP_INSN)
continue;
- mark_loop_jump (PATTERN (insn), this_loop_num);
+ mark_loop_jump (PATTERN (insn), this_loop);
/* See if this is an unconditional branch outside the loop. */
- if (this_loop_num != -1
+ if (this_loop
&& (GET_CODE (PATTERN (insn)) == RETURN
- || (simplejump_p (insn)
- && (uid_loop_num[INSN_UID (JUMP_LABEL (insn))]
- != this_loop_num)))
+ || (any_uncondjump_p (insn)
+ && onlyjump_p (insn)
+ && (uid_loop[INSN_UID (JUMP_LABEL (insn))]
+ != this_loop)))
&& get_max_uid () < max_uid_for_loop)
{
rtx p;
rtx our_next = next_real_insn (insn);
rtx last_insn_to_move = NEXT_INSN (insn);
- int dest_loop;
- int outer_loop = -1;
+ struct loop *dest_loop;
+ struct loop *outer_loop = NULL;
/* Go backwards until we reach the start of the loop, a label,
or a JUMP_INSN. */
if (JUMP_LABEL (insn))
{
- dest_loop = uid_loop_num[INSN_UID (JUMP_LABEL (insn))];
- if (dest_loop != -1)
+ dest_loop = uid_loop[INSN_UID (JUMP_LABEL (insn))];
+ if (dest_loop)
{
- for (outer_loop = dest_loop; outer_loop != -1;
- outer_loop = loop_outer_loop[outer_loop])
- if (outer_loop == this_loop_num)
+ for (outer_loop = dest_loop; outer_loop;
+ outer_loop = outer_loop->outer)
+ if (outer_loop == this_loop)
break;
}
}
/* Make sure that the target of P is within the current loop. */
if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
- && uid_loop_num[INSN_UID (JUMP_LABEL (p))] != this_loop_num)
- outer_loop = this_loop_num;
+ && uid_loop[INSN_UID (JUMP_LABEL (p))] != this_loop)
+ outer_loop = this_loop;
/* If we stopped on a JUMP_INSN to the next insn after INSN,
we have a block of code to try to move.
of the block, invert the jump in P and point it to that label,
and move the block of code to the spot we found. */
- if (outer_loop == -1
+ if (! outer_loop
&& GET_CODE (p) == JUMP_INSN
&& JUMP_LABEL (p) != 0
/* Just ignore jumps to labels that were never emitted.
These always indicate compilation errors. */
&& INSN_UID (JUMP_LABEL (p)) != 0
- && condjump_p (p)
- && ! simplejump_p (p)
+ && any_condjump_p (p) && onlyjump_p (p)
&& next_real_insn (JUMP_LABEL (p)) == our_next
/* If it's not safe to move the sequence, then we
mustn't try. */
- && insns_safe_to_move_p (p, NEXT_INSN (insn),
+ && insns_safe_to_move_p (p, NEXT_INSN (insn),
&last_insn_to_move))
{
rtx target
= JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
- int target_loop_num = uid_loop_num[INSN_UID (target)];
- rtx loc;
+ struct loop *target_loop = uid_loop[INSN_UID (target)];
+ rtx loc, loc2;
for (loc = target; loc; loc = PREV_INSN (loc))
if (GET_CODE (loc) == BARRIER
- && uid_loop_num[INSN_UID (loc)] == target_loop_num)
+ /* Don't move things inside a tablejump. */
+ && ((loc2 = next_nonnote_insn (loc)) == 0
+ || GET_CODE (loc2) != CODE_LABEL
+ || (loc2 = next_nonnote_insn (loc2)) == 0
+ || GET_CODE (loc2) != JUMP_INSN
+ || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
+ && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
+ && uid_loop[INSN_UID (loc)] == target_loop)
break;
if (loc == 0)
for (loc = target; loc; loc = NEXT_INSN (loc))
if (GET_CODE (loc) == BARRIER
- && uid_loop_num[INSN_UID (loc)] == target_loop_num)
+ /* Don't move things inside a tablejump. */
+ && ((loc2 = next_nonnote_insn (loc)) == 0
+ || GET_CODE (loc2) != CODE_LABEL
+ || (loc2 = next_nonnote_insn (loc2)) == 0
+ || GET_CODE (loc2) != JUMP_INSN
+ || (GET_CODE (PATTERN (loc2)) != ADDR_VEC
+ && GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
+ && uid_loop[INSN_UID (loc)] == target_loop)
break;
if (loc)
/* Ensure our label doesn't go away. */
LABEL_NUSES (cond_label)++;
- /* Verify that uid_loop_num is large enough and that
+ /* Verify that uid_loop is large enough and that
we can invert P. */
- if (invert_jump (p, new_label))
- {
- rtx q, r;
-
- /* 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.
-
- This creates an extra unconditional jump outside
- the loop. However, the benefits of removing rarely
- executed instructions from inside the loop usually
- outweighs the cost of the extra unconditional jump
- outside the loop. */
- if (loc == 0)
- {
- rtx temp;
-
- temp = gen_jump (JUMP_LABEL (insn));
- temp = emit_jump_insn_before (temp, target);
- JUMP_LABEL (temp) = JUMP_LABEL (insn);
- LABEL_NUSES (JUMP_LABEL (insn))++;
- loc = emit_barrier_before (target);
- }
-
- /* Include the BARRIER after INSN and copy the
- block after LOC. */
- new_label = squeeze_notes (new_label,
- last_insn_to_move);
- reorder_insns (new_label, last_insn_to_move, loc);
-
- /* All those insns are now in TARGET_LOOP_NUM. */
- for (q = new_label;
- q != NEXT_INSN (last_insn_to_move);
- q = NEXT_INSN (q))
- uid_loop_num[INSN_UID (q)] = target_loop_num;
-
- /* The label jumped to by INSN is no longer a loop exit.
- Unless INSN does not have a label (e.g., it is a
- RETURN insn), search loop_number_exit_labels to find
- its label_ref, and remove it. Also turn off
- LABEL_OUTSIDE_LOOP_P bit. */
- if (JUMP_LABEL (insn))
- {
- int loop_num;
-
- for (q = 0,
- r = loop_number_exit_labels[this_loop_num];
- r; q = r, r = LABEL_NEXTREF (r))
- if (XEXP (r, 0) == JUMP_LABEL (insn))
- {
- LABEL_OUTSIDE_LOOP_P (r) = 0;
- if (q)
- LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
- else
- loop_number_exit_labels[this_loop_num]
- = LABEL_NEXTREF (r);
- break;
- }
-
- for (loop_num = this_loop_num;
- loop_num != -1 && loop_num != target_loop_num;
- loop_num = loop_outer_loop[loop_num])
- loop_number_exit_count[loop_num]--;
-
- /* If we didn't find it, then something is wrong. */
- if (! r)
- abort ();
- }
-
- /* P is now a jump outside the loop, so it must be put
- in loop_number_exit_labels, and marked as such.
- The easiest way to do this is to just call
- mark_loop_jump again for P. */
- mark_loop_jump (PATTERN (p), this_loop_num);
-
- /* If INSN now jumps to the insn after it,
- delete INSN. */
- if (JUMP_LABEL (insn) != 0
- && (next_real_insn (JUMP_LABEL (insn))
- == next_real_insn (insn)))
- delete_insn (insn);
- }
+ if (invert_jump (p, new_label, 1))
+ {
+ rtx q, r;
+
+ /* 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.
+
+ This creates an extra unconditional jump outside
+ the loop. However, the benefits of removing rarely
+ executed instructions from inside the loop usually
+ outweighs the cost of the extra unconditional jump
+ outside the loop. */
+ if (loc == 0)
+ {
+ rtx temp;
+
+ temp = gen_jump (JUMP_LABEL (insn));
+ temp = emit_jump_insn_before (temp, target);
+ JUMP_LABEL (temp) = JUMP_LABEL (insn);
+ LABEL_NUSES (JUMP_LABEL (insn))++;
+ loc = emit_barrier_before (target);
+ }
+
+ /* Include the BARRIER after INSN and copy the
+ block after LOC. */
+ new_label = squeeze_notes (new_label,
+ last_insn_to_move);
+ reorder_insns (new_label, last_insn_to_move, loc);
+
+ /* All those insns are now in TARGET_LOOP. */
+ for (q = new_label;
+ q != NEXT_INSN (last_insn_to_move);
+ q = NEXT_INSN (q))
+ uid_loop[INSN_UID (q)] = target_loop;
+
+ /* The label jumped to by INSN is no longer a loop
+ exit. Unless INSN does not have a label (e.g.,
+ it is a RETURN insn), search loop->exit_labels
+ to find its label_ref, and remove it. Also turn
+ off LABEL_OUTSIDE_LOOP_P bit. */
+ if (JUMP_LABEL (insn))
+ {
+ for (q = 0,
+ r = this_loop->exit_labels;
+ r; q = r, r = LABEL_NEXTREF (r))
+ if (XEXP (r, 0) == JUMP_LABEL (insn))
+ {
+ LABEL_OUTSIDE_LOOP_P (r) = 0;
+ if (q)
+ LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
+ else
+ this_loop->exit_labels = LABEL_NEXTREF (r);
+ break;
+ }
+
+ for (loop = this_loop; loop && loop != target_loop;
+ loop = loop->outer)
+ loop->exit_count--;
+
+ /* If we didn't find it, then something is
+ wrong. */
+ if (! r)
+ abort ();
+ }
+
+ /* P is now a jump outside the loop, so it must be put
+ in loop->exit_labels, and marked as such.
+ The easiest way to do this is to just call
+ mark_loop_jump again for P. */
+ mark_loop_jump (PATTERN (p), this_loop);
+
+ /* If INSN now jumps to the insn after it,
+ delete INSN. */
+ if (JUMP_LABEL (insn) != 0
+ && (next_real_insn (JUMP_LABEL (insn))
+ == next_real_insn (insn)))
+ delete_insn (insn);
+ }
/* Continue the loop after where the conditional
branch used to jump, since the only branch insn
For speed, we assume that X is part of a pattern of a JUMP_INSN. */
static void
-mark_loop_jump (x, loop_num)
+mark_loop_jump (x, loop)
rtx x;
- int loop_num;
+ struct loop *loop;
{
- int dest_loop;
- int outer_loop;
+ struct loop *dest_loop;
+ struct loop *outer_loop;
int i;
switch (GET_CODE (x))
case CONST:
/* There could be a label reference in here. */
- mark_loop_jump (XEXP (x, 0), loop_num);
+ mark_loop_jump (XEXP (x, 0), loop);
return;
case PLUS:
case MINUS:
case MULT:
- mark_loop_jump (XEXP (x, 0), loop_num);
- mark_loop_jump (XEXP (x, 1), loop_num);
+ mark_loop_jump (XEXP (x, 0), loop);
+ mark_loop_jump (XEXP (x, 1), loop);
return;
case LO_SUM:
/* This may refer to a LABEL_REF or SYMBOL_REF. */
- mark_loop_jump (XEXP (x, 1), loop_num);
+ mark_loop_jump (XEXP (x, 1), loop);
return;
case SIGN_EXTEND:
case ZERO_EXTEND:
- mark_loop_jump (XEXP (x, 0), loop_num);
+ mark_loop_jump (XEXP (x, 0), loop);
return;
case LABEL_REF:
- dest_loop = uid_loop_num[INSN_UID (XEXP (x, 0))];
+ dest_loop = uid_loop[INSN_UID (XEXP (x, 0))];
/* Link together all labels that branch outside the loop. This
is used by final_[bg]iv_value and the loop unrolling code. Also
/* A check to make sure the label is not in an inner nested loop,
since this does not count as a loop exit. */
- if (dest_loop != -1)
+ if (dest_loop)
{
- for (outer_loop = dest_loop; outer_loop != -1;
- outer_loop = loop_outer_loop[outer_loop])
- if (outer_loop == loop_num)
+ for (outer_loop = dest_loop; outer_loop;
+ outer_loop = outer_loop->outer)
+ if (outer_loop == loop)
break;
}
else
- outer_loop = -1;
+ outer_loop = NULL;
- if (loop_num != -1 && outer_loop == -1)
+ if (loop && ! outer_loop)
{
LABEL_OUTSIDE_LOOP_P (x) = 1;
- LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
- loop_number_exit_labels[loop_num] = x;
+ LABEL_NEXTREF (x) = loop->exit_labels;
+ loop->exit_labels = x;
- for (outer_loop = loop_num;
- outer_loop != -1 && outer_loop != dest_loop;
- outer_loop = loop_outer_loop[outer_loop])
- loop_number_exit_count[outer_loop]++;
+ for (outer_loop = loop;
+ outer_loop && outer_loop != dest_loop;
+ outer_loop = outer_loop->outer)
+ outer_loop->exit_count++;
}
/* If this is inside a loop, but not in the current loop or one enclosed
by it, it invalidates at least one loop. */
- if (dest_loop == -1)
+ if (! dest_loop)
return;
/* We must invalidate every nested loop containing the target of this
label, except those that also contain the jump insn. */
- for (; dest_loop != -1; dest_loop = loop_outer_loop[dest_loop])
+ for (; dest_loop; dest_loop = dest_loop->outer)
{
/* Stop when we reach a loop that also contains the jump insn. */
- for (outer_loop = loop_num; outer_loop != -1;
- outer_loop = loop_outer_loop[outer_loop])
+ for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
if (dest_loop == outer_loop)
return;
/* If we get here, we know we need to invalidate a loop. */
- if (loop_dump_stream && ! loop_invalid[dest_loop])
+ if (loop_dump_stream && ! dest_loop->invalid)
fprintf (loop_dump_stream,
"\nLoop at %d ignored due to multiple entry points.\n",
- INSN_UID (loop_number_loop_starts[dest_loop]));
-
- loop_invalid[dest_loop] = 1;
+ INSN_UID (dest_loop->start));
+
+ dest_loop->invalid = 1;
}
return;
case SET:
/* If this is not setting pc, ignore. */
if (SET_DEST (x) == pc_rtx)
- mark_loop_jump (SET_SRC (x), loop_num);
+ mark_loop_jump (SET_SRC (x), loop);
return;
case IF_THEN_ELSE:
- mark_loop_jump (XEXP (x, 1), loop_num);
- mark_loop_jump (XEXP (x, 2), loop_num);
+ mark_loop_jump (XEXP (x, 1), loop);
+ mark_loop_jump (XEXP (x, 2), loop);
return;
case PARALLEL:
case ADDR_VEC:
for (i = 0; i < XVECLEN (x, 0); i++)
- mark_loop_jump (XVECEXP (x, 0, i), loop_num);
+ mark_loop_jump (XVECEXP (x, 0, i), loop);
return;
case ADDR_DIFF_VEC:
for (i = 0; i < XVECLEN (x, 1); i++)
- mark_loop_jump (XVECEXP (x, 1, i), loop_num);
+ mark_loop_jump (XVECEXP (x, 1, i), loop);
return;
default:
jump out of the loop. However, we have no way to link the destination
of this jump onto the list of exit labels. To be safe we mark this
loop and any containing loops as invalid. */
- if (loop_num != -1)
+ if (loop)
{
- for (outer_loop = loop_num; outer_loop != -1;
- outer_loop = loop_outer_loop[outer_loop])
+ for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
{
- if (loop_dump_stream && ! loop_invalid[outer_loop])
+ if (loop_dump_stream && ! outer_loop->invalid)
fprintf (loop_dump_stream,
"\nLoop at %d ignored due to unknown exit jump.\n",
- INSN_UID (loop_number_loop_starts[outer_loop]));
- loop_invalid[outer_loop] = 1;
+ INSN_UID (outer_loop->start));
+ outer_loop->invalid = 1;
}
}
return;
/* Record that a memory reference X is being set. */
static void
-note_addr_stored (x, y)
+note_addr_stored (x, y, data)
rtx x;
rtx y ATTRIBUTE_UNUSED;
+ void *data ATTRIBUTE_UNUSED;
{
if (x == 0 || GET_CODE (x) != MEM)
return;
num_mem_sets++;
/* BLKmode MEM means all memory is clobbered. */
- if (GET_MODE (x) == BLKmode)
- unknown_address_altered = 1;
+ if (GET_MODE (x) == BLKmode)
+ {
+ if (RTX_UNCHANGING_P (x))
+ unknown_constant_address_altered = 1;
+ else
+ unknown_address_altered = 1;
- if (unknown_address_altered)
- return;
+ return;
+ }
loop_store_mems = gen_rtx_EXPR_LIST (VOIDmode, x, loop_store_mems);
}
+
+/* X is a value modified by an INSN that references a biv inside a loop
+ exit test (ie, X is somehow related to the value of the biv). If X
+ is a pseudo that is used more than once, then the biv is (effectively)
+ used more than once. DATA is really an `int *', and is set if the
+ biv is used more than once. */
+
+static void
+note_set_pseudo_multiple_uses (x, y, data)
+ rtx x;
+ rtx y ATTRIBUTE_UNUSED;
+ void *data;
+{
+ if (x == 0)
+ return;
+
+ while (GET_CODE (x) == STRICT_LOW_PART
+ || GET_CODE (x) == SIGN_EXTRACT
+ || GET_CODE (x) == ZERO_EXTRACT
+ || GET_CODE (x) == SUBREG)
+ x = XEXP (x, 0);
+
+ if (GET_CODE (x) != REG || REGNO (x) < FIRST_PSEUDO_REGISTER)
+ return;
+
+ /* If we do not have usage information, or if we know the register
+ is used more than once, note that fact for check_dbra_loop. */
+ if (REGNO (x) >= max_reg_before_loop
+ || ! VARRAY_RTX (reg_single_usage, REGNO (x))
+ || VARRAY_RTX (reg_single_usage, REGNO (x)) == const0_rtx)
+ *((int *) data) = 1;
+}
\f
/* Return nonzero if the rtx X is invariant over the current loop.
anything stored in `loop_store_mems'. */
int
-invariant_p (x)
+loop_invariant_p (loop, x)
+ const struct loop *loop;
register rtx x;
{
register int i;
&& ! current_function_has_nonlocal_goto)
return 1;
- if (this_loop_info.has_call
+ if (LOOP_INFO (loop)->has_call
&& REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
return 0;
if (MEM_VOLATILE_P (x))
return 0;
- /* Read-only items (such as constants in a constant pool) are
- invariant if their address is. */
- if (RTX_UNCHANGING_P (x))
- break;
-
- /* If we had a subroutine call, any location in memory could have been
- clobbered. */
- if (unknown_address_altered)
+ /* If we had a subroutine call, any location in memory could
+ have been clobbered. We used to test here for volatile and
+ readonly, but true_dependence knows how to do that better
+ than we do. */
+ if (RTX_UNCHANGING_P (x)
+ ? unknown_constant_address_altered : unknown_address_altered)
return 0;
/* See if there is any dependence between a store and this load. */
if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
x, rtx_varies_p))
return 0;
+
mem_list_entry = XEXP (mem_list_entry, 1);
}
if (MEM_VOLATILE_P (x))
return 0;
break;
-
+
default:
break;
}
{
if (fmt[i] == 'e')
{
- int tem = invariant_p (XEXP (x, i));
+ int tem = loop_invariant_p (loop, XEXP (x, i));
if (tem == 0)
return 0;
if (tem == 2)
register int j;
for (j = 0; j < XVECLEN (x, i); j++)
{
- int tem = invariant_p (XVECEXP (x, i, j));
+ int tem = loop_invariant_p (loop, XVECEXP (x, i, j));
if (tem == 0)
return 0;
if (tem == 2)
return 1 + conditional;
}
-
\f
/* Return nonzero if all the insns in the loop that set REG
are INSN and the immediately following insns,
and that its source is invariant. */
static int
-consec_sets_invariant_p (reg, n_sets, insn)
+consec_sets_invariant_p (loop, reg, n_sets, insn)
+ const struct loop *loop;
int n_sets;
rtx reg, insn;
{
- register rtx p = insn;
- register int regno = REGNO (reg);
+ rtx p = insn;
+ unsigned int regno = REGNO (reg);
rtx temp;
/* Number of sets we have to insist on finding after INSN. */
int count = n_sets - 1;
&& GET_CODE (SET_DEST (set)) == REG
&& REGNO (SET_DEST (set)) == regno)
{
- this = invariant_p (SET_SRC (set));
+ this = loop_invariant_p (loop, SET_SRC (set));
if (this != 0)
value |= this;
else if ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX)))
notes are OK. */
this = (CONSTANT_P (XEXP (temp, 0))
|| (find_reg_note (p, REG_RETVAL, NULL_RTX)
- && invariant_p (XEXP (temp, 0))));
+ && loop_invariant_p (loop, XEXP (temp, 0))));
if (this != 0)
value |= this;
}
}
VARRAY_INT (set_in_loop, regno) = old;
- /* If invariant_p ever returned 2, we return 2. */
+ /* If loop_invariant_p ever returned 2, we return 2. */
return 1 + (value & 2);
}
&& GET_CODE (SET_DEST (PATTERN (p))) == REG
&& REGNO (SET_DEST (PATTERN (p))) == regno)
{
- if (!invariant_p (SET_SRC (PATTERN (p)), table))
+ if (! loop_invariant_p (loop, SET_SRC (PATTERN (p)), table))
return 0;
}
}
if (code == REG)
VARRAY_RTX (usage, REGNO (x))
- = (VARRAY_RTX (usage, REGNO (x)) != 0
+ = (VARRAY_RTX (usage, REGNO (x)) != 0
&& VARRAY_RTX (usage, REGNO (x)) != insn)
? const0_rtx : insn;
{
/* Don't count SET_DEST if it is a REG; otherwise count things
in SET_DEST because if a register is partially modified, it won't
- show up as a potential movable so we don't care how USAGE is set
+ show up as a potential movable so we don't care how USAGE is set
for it. */
if (GET_CODE (SET_DEST (x)) != REG)
find_single_use_in_loop (insn, SET_DEST (x), usage);
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 (VARRAY_INT (set_in_loop, regno) > 0
+ if (VARRAY_INT (set_in_loop, regno) > 0
&& last_set[regno] == 0)
VARRAY_CHAR (may_not_move, regno) = 1;
/* If this is not first setting in current basic block,
int *count_ptr;
int nregs;
{
- register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx));
+ register rtx *last_set = (rtx *) xcalloc (nregs, sizeof (rtx));
register rtx insn;
register int count = 0;
- bzero ((char *) last_set, nregs * sizeof (rtx));
for (insn = from; insn != to; insn = NEXT_INSN (insn))
{
- if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
+ if (INSN_P (insn))
{
++count;
bzero ((char *) last_set, nregs * 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 is entered at SCAN_START,
- return 1 if the register set in SET contained in insn INSN is used by
- any insn that precedes INSN in cyclic order starting
- from the loop entry point.
+/* Given a loop that is bounded by LOOP->START and LOOP->END and that
+ is entered at LOOP->SCAN_START, return 1 if the register set in SET
+ contained in insn INSN is used by any insn that precedes INSN in
+ cyclic order starting from the loop entry point.
We don't want to use INSN_LUID here because if we restrict INSN to those
that have a valid INSN_LUID, it means we cannot move an invariant out
from an inner loop past two loops. */
static int
-loop_reg_used_before_p (set, insn, loop_start, scan_start, loop_end)
- rtx set, insn, loop_start, scan_start, loop_end;
+loop_reg_used_before_p (loop, set, insn)
+ const struct loop *loop;
+ rtx set, insn;
{
rtx reg = SET_DEST (set);
rtx p;
/* Scan forward checking for register usage. If we hit INSN, we
- are done. Otherwise, if we hit LOOP_END, wrap around to LOOP_START. */
- for (p = scan_start; p != insn; p = NEXT_INSN (p))
+ are done. Otherwise, if we hit LOOP->END, wrap around to LOOP->START. */
+ for (p = loop->scan_start; p != insn; p = NEXT_INSN (p))
{
- if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
- && reg_overlap_mentioned_p (reg, PATTERN (p)))
+ if (INSN_P (p) && reg_overlap_mentioned_p (reg, PATTERN (p)))
return 1;
- if (p == loop_end)
- p = loop_start;
+ if (p == loop->end)
+ p = loop->start;
}
return 0;
/* Givs made from biv increments are always splittable for loop unrolling.
Since there is no regscan info for them, we have to keep track of them
separately. */
-int first_increment_giv, last_increment_giv;
+unsigned int first_increment_giv, last_increment_giv;
/* Communication with routines called via `note_stores'. */
was rerun in loop_optimize whenever a register was added or moved.
Also, some of the optimizations could be a little less conservative. */
\f
-/* Perform strength reduction and induction variable elimination.
+/* Scan the loop body and call FNCALL for each insn. In the addition to the
+ LOOP and INSN parameters pass MAYBE_MULTIPLE and NOT_EVERY_ITERATION to the
+ callback.
- Pseudo registers created during this function will be beyond the last
- valid index in several tables including n_times_set and regno_last_uid.
- This does not cause a problem here, because the added registers cannot be
- givs outside of their loop, and hence will never be reconsidered.
- But scan_loop must check regnos to make sure they are in bounds.
-
- SCAN_START is the first instruction in the loop, as the loop would
- actually be executed. END is the NOTE_INSN_LOOP_END. LOOP_TOP is
- the first instruction in the loop, as it is layed out in the
- instruction stream. LOOP_START is the NOTE_INSN_LOOP_BEG.
- LOOP_CONT is the NOTE_INSN_LOOP_CONT. */
+ NOT_EVERY_ITERATION if current insn is not executed at least once for every
+ loop iteration except for the last one.
-static void
-strength_reduce (scan_start, end, loop_top, insn_count,
- loop_start, loop_end, loop_info, loop_cont, unroll_p, bct_p)
- rtx scan_start;
- rtx end;
- rtx loop_top;
- int insn_count;
- rtx loop_start;
- rtx loop_end;
- struct loop_info *loop_info;
- rtx loop_cont;
- int unroll_p, bct_p ATTRIBUTE_UNUSED;
+ MAYBE_MULTIPLE is 1 if current insn may be executed more than once for every
+ loop iteration.
+ */
+void
+for_each_insn_in_loop (loop, fncall)
+ struct loop *loop;
+ loop_insn_callback fncall;
{
- rtx p;
- rtx set;
- rtx inc_val;
- rtx mult_val;
- rtx dest_reg;
- rtx *location;
/* This is 1 if current insn is not executed at least once for every loop
iteration. */
int not_every_iteration = 0;
- /* This is 1 if current insn may be executed more than once for every
- loop iteration. */
int maybe_multiple = 0;
- /* This is 1 if we have past a branch back to the top of the loop
- (aka a loop latch). */
int past_loop_latch = 0;
- /* Temporary list pointers for traversing loop_iv_list. */
- struct iv_class *bl, **backbl;
- /* Ratio of extra register life span we can justify
- for saving an instruction. More if loop doesn't call subroutines
- since in that case saving an insn makes more difference
- and more registers are available. */
- /* ??? could set this to last value of threshold in move_movables */
- int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
- /* Map of pseudo-register replacements. */
- rtx *reg_map;
- int reg_map_size;
- int call_seen;
- rtx test;
- rtx end_insert_before;
int loop_depth = 0;
- int n_extra_increment;
- int unrolled_insn_copies;
+ rtx p;
- /* If scan_start points to the loop exit test, we have to be wary of
+ /* If loop_scan_start points to the loop exit test, we have to be wary of
subversive use of gotos inside expression statements. */
- if (prev_nonnote_insn (scan_start) != prev_nonnote_insn (loop_start))
- maybe_multiple = back_branch_in_range_p (scan_start, loop_start, loop_end);
-
- VARRAY_INT_INIT (reg_iv_type, max_reg_before_loop, "reg_iv_type");
- VARRAY_GENERIC_PTR_INIT (reg_iv_info, max_reg_before_loop, "reg_iv_info");
- reg_biv_class = (struct iv_class **)
- alloca (max_reg_before_loop * sizeof (struct iv_class *));
- bzero ((char *) reg_biv_class, (max_reg_before_loop
- * sizeof (struct iv_class *)));
-
- loop_iv_list = 0;
- 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);
+ if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
+ maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
/* Scan through loop to find all possible bivs. */
- for (p = next_insn_in_loop (scan_start, scan_start, end, loop_top);
+ for (p = next_insn_in_loop (loop, loop->scan_start);
p != NULL_RTX;
- p = next_insn_in_loop (p, scan_start, end, loop_top))
+ p = next_insn_in_loop (loop, p))
{
- if (GET_CODE (p) == INSN
- && (set = single_set (p))
- && GET_CODE (SET_DEST (set)) == REG)
- {
- dest_reg = SET_DEST (set);
- if (REGNO (dest_reg) < max_reg_before_loop
- && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
- && REG_IV_TYPE (REGNO (dest_reg)) != NOT_BASIC_INDUCT)
- {
- if (basic_induction_var (SET_SRC (set), GET_MODE (SET_SRC (set)),
- dest_reg, p, &inc_val, &mult_val,
- &location))
- {
- /* It is a possible basic induction variable.
- Create and initialize an induction structure for it. */
-
- struct induction *v
- = (struct induction *) alloca (sizeof (struct induction));
-
- record_biv (v, p, dest_reg, inc_val, mult_val, location,
- not_every_iteration, maybe_multiple);
- REG_IV_TYPE (REGNO (dest_reg)) = BASIC_INDUCT;
- }
- else if (REGNO (dest_reg) < max_reg_before_loop)
- REG_IV_TYPE (REGNO (dest_reg)) = NOT_BASIC_INDUCT;
- }
- }
+ p = fncall (loop, p, not_every_iteration, maybe_multiple);
/* Past CODE_LABEL, we get to insns that may be executed multiple
- times. The only way we can be sure that they can't is if every
- jump insn between here and the end of the loop either
- returns, exits the loop, is a jump to a location that is still
- behind the label, or is a jump to the loop start. */
+ times. The only way we can be sure that they can't is if every
+ jump insn between here and the end of the loop either
+ returns, exits the loop, is a jump to a location that is still
+ behind the label, or is a jump to the loop start. */
if (GET_CODE (p) == CODE_LABEL)
{
while (1)
{
insn = NEXT_INSN (insn);
- if (insn == scan_start)
+ if (insn == loop->scan_start)
break;
- if (insn == end)
+ if (insn == loop->end)
{
- if (loop_top != 0)
- insn = loop_top;
+ if (loop->top != 0)
+ insn = loop->top;
else
break;
- if (insn == scan_start)
+ if (insn == loop->scan_start)
break;
}
if (GET_CODE (insn) == JUMP_INSN
&& GET_CODE (PATTERN (insn)) != RETURN
- && (! condjump_p (insn)
+ && (!any_condjump_p (insn)
|| (JUMP_LABEL (insn) != 0
- && JUMP_LABEL (insn) != scan_start
- && ! loop_insn_first_p (p, JUMP_LABEL (insn)))))
+ && JUMP_LABEL (insn) != loop->scan_start
+ && !loop_insn_first_p (p, JUMP_LABEL (insn)))))
{
maybe_multiple = 1;
break;
}
/* Past a jump, we get to insns for which we can't count
- on whether they will be executed during each iteration. */
+ on whether they will be executed during each iteration. */
/* This code appears twice in strength_reduce. There is also similar
- code in scan_loop. */
+ code in scan_loop. */
if (GET_CODE (p) == JUMP_INSN
- /* If we enter the loop in the middle, and scan around to the
- beginning, don't set not_every_iteration for that.
- This can be any kind of jump, since we want to know if insns
- will be executed if the loop is executed. */
- && ! (JUMP_LABEL (p) == loop_top
- && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
- || (NEXT_INSN (p) == loop_end && condjump_p (p)))))
+ /* If we enter the loop in the middle, and scan around to the
+ beginning, don't set not_every_iteration for that.
+ This can be any kind of jump, since we want to know if insns
+ will be executed if the loop is executed. */
+ && !(JUMP_LABEL (p) == loop->top
+ && ((NEXT_INSN (NEXT_INSN (p)) == loop->end
+ && any_uncondjump_p (p))
+ || (NEXT_INSN (p) == loop->end && any_condjump_p (p)))))
{
rtx label = 0;
/* If this is a jump outside the loop, then it also doesn't
matter. Check to see if the target of this branch is on the
- loop_number_exits_labels list. */
-
- for (label = loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]];
- label;
- label = LABEL_NEXTREF (label))
+ loop->exits_labels list. */
+
+ for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
if (XEXP (label, 0) == JUMP_LABEL (p))
break;
- if (! label)
+ if (!label)
not_every_iteration = 1;
}
}
/* Note if we pass a loop latch. If we do, then we can not clear
- NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
- a loop since a jump before the last CODE_LABEL may have started
- a new loop iteration.
-
- Note that LOOP_TOP is only set for rotated loops and we need
- this check for all loops, so compare against the CODE_LABEL
- which immediately follows LOOP_START. */
- if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == NEXT_INSN (loop_start))
+ NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
+ a loop since a jump before the last CODE_LABEL may have started
+ a new loop iteration.
+
+ Note that LOOP_TOP is only set for rotated loops and we need
+ this check for all loops, so compare against the CODE_LABEL
+ which immediately follows LOOP_START. */
+ if (GET_CODE (p) == JUMP_INSN
+ && JUMP_LABEL (p) == NEXT_INSN (loop->start))
past_loop_latch = 1;
/* Unlike in the code motion pass where MAYBE_NEVER indicates that
- an insn may never be executed, NOT_EVERY_ITERATION indicates whether
- or not an insn is known to be executed each iteration of the
- loop, whether or not any iterations are known to occur.
+ an insn may never be executed, NOT_EVERY_ITERATION indicates whether
+ or not an insn is known to be executed each iteration of the
+ loop, whether or not any iterations are known to occur.
- Therefore, if we have just passed a label and have no more labels
- between here and the test insn of the loop, and we have not passed
- a jump to the top of the loop, then we know these insns will be
- executed each iteration. */
+ Therefore, if we have just passed a label and have no more labels
+ between here and the test insn of the loop, and we have not passed
+ a jump to the top of the loop, then we know these insns will be
+ executed each iteration. */
- if (not_every_iteration
- && ! past_loop_latch
+ if (not_every_iteration
+ && !past_loop_latch
&& GET_CODE (p) == CODE_LABEL
- && no_labels_between_p (p, loop_end)
- && loop_insn_first_p (p, loop_cont))
+ && no_labels_between_p (p, loop->end)
+ && loop_insn_first_p (p, loop->cont))
not_every_iteration = 0;
}
+}
+\f
+/* Perform strength reduction and induction variable elimination.
+
+ Pseudo registers created during this function will be beyond the last
+ valid index in several tables including n_times_set and regno_last_uid.
+ This does not cause a problem here, because the added registers cannot be
+ givs outside of their loop, and hence will never be reconsidered.
+ But scan_loop must check regnos to make sure they are in bounds. */
+
+static void
+strength_reduce (loop, insn_count, flags)
+ struct loop *loop;
+ int insn_count;
+ int flags;
+{
+ rtx p;
+ /* Temporary list pointers for traversing loop_iv_list. */
+ struct iv_class *bl, **backbl;
+ struct loop_info *loop_info = LOOP_INFO (loop);
+ /* Ratio of extra register life span we can justify
+ for saving an instruction. More if loop doesn't call subroutines
+ since in that case saving an insn makes more difference
+ and more registers are available. */
+ /* ??? could set this to last value of threshold in move_movables */
+ int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
+ /* Map of pseudo-register replacements. */
+ rtx *reg_map = NULL;
+ int reg_map_size;
+ int call_seen;
+ rtx test;
+ rtx end_insert_before;
+ int n_extra_increment;
+ int unrolled_insn_copies = 0;
+ rtx loop_start = loop->start;
+ rtx loop_end = loop->end;
+ rtx loop_scan_start = loop->scan_start;
+
+ VARRAY_INT_INIT (reg_iv_type, max_reg_before_loop, "reg_iv_type");
+ VARRAY_GENERIC_PTR_INIT (reg_iv_info, max_reg_before_loop, "reg_iv_info");
+ reg_biv_class = (struct iv_class **)
+ xcalloc (max_reg_before_loop, sizeof (struct iv_class *));
+
+ loop_iv_list = 0;
+ 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);
+
+ for_each_insn_in_loop (loop, check_insn_for_bivs);
/* Scan loop_iv_list to remove all regs that proved not to be bivs.
Make a sanity check against n_times_set. */
? "not induction variable"
: (! bl->incremented ? "never incremented"
: "count error")));
-
+
REG_IV_TYPE (bl->regno) = NOT_BASIC_INDUCT;
*backbl = bl->next;
}
{
/* Can still unroll the loop anyways, but indicate that there is no
strength reduction info available. */
- if (unroll_p)
- unroll_loop (loop_end, insn_count, loop_start, end_insert_before,
- loop_info, 0);
+ if (flags & LOOP_UNROLL)
+ unroll_loop (loop, insn_count, end_insert_before, 0);
goto egress;
}
if (GET_CODE (p) == CALL_INSN)
call_seen = 1;
- if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
- || GET_CODE (p) == CALL_INSN)
- note_stores (PATTERN (p), record_initial);
+ if (INSN_P (p))
+ note_stores (PATTERN (p), record_initial, NULL);
/* Record any test of a biv that branches around the loop if no store
between it and the start of loop. We only care about tests with
if (GET_CODE (p) == JUMP_INSN
&& JUMP_LABEL (p) != 0
&& next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end)
- && (test = get_condition_for_loop (p)) != 0
+ && (test = get_condition_for_loop (loop, p)) != 0
&& GET_CODE (XEXP (test, 0)) == REG
&& REGNO (XEXP (test, 0)) < max_reg_before_loop
&& (bl = reg_biv_class[REGNO (XEXP (test, 0))]) != 0
&& GET_CODE (src) == PLUS
&& GET_CODE (XEXP (src, 0)) == REG
&& CONSTANT_P (XEXP (src, 1))
- && ((increment = biv_total_increment (bl, loop_start, loop_end))
- != NULL_RTX))
+ && ((increment = biv_total_increment (bl)) != NULL_RTX))
{
- int regno = REGNO (XEXP (src, 0));
+ unsigned int regno = REGNO (XEXP (src, 0));
for (bl2 = loop_iv_list; bl2; bl2 = bl2->next)
if (bl2->regno == regno)
break;
}
-
+
/* Now, can we transform this biv into a giv? */
if (bl2
&& bl2->biv_count == 1
- && rtx_equal_p (increment,
- biv_total_increment (bl2, loop_start, loop_end))
+ && rtx_equal_p (increment, biv_total_increment (bl2))
/* init_insn is only set to insns that are before loop_start
without any intervening labels. */
&& ! reg_set_between_p (bl2->biv->src_reg,
&SET_SRC (single_set (bl->biv->insn)),
copy_rtx (src), 0))
{
- int loop_num = uid_loop_num[INSN_UID (loop_start)];
- rtx dominator = loop_number_cont_dominator[loop_num];
+ rtx dominator = loop->cont_dominator;
rtx giv = bl->biv->src_reg;
rtx giv_insn = bl->biv->insn;
rtx after_giv = NEXT_INSN (giv_insn);
fprintf (loop_dump_stream, "is giv of biv %d\n", bl2->regno);
/* Let this giv be discovered by the generic code. */
REG_IV_TYPE (bl->regno) = UNKNOWN_INDUCT;
- reg_biv_class[bl->regno] = NULL_PTR;
+ reg_biv_class[bl->regno] = (struct iv_class *) NULL_PTR;
/* We can get better optimization if we can move the giv setting
before the first giv use. */
if (dominator
- && ! loop_insn_first_p (dominator, scan_start)
+ && ! loop_insn_first_p (dominator, loop_scan_start)
&& ! reg_set_between_p (bl2->biv->src_reg, loop_start,
dominator)
&& ! reg_used_between_p (giv, loop_start, dominator)
rtx p;
rtx next;
- for (next = NEXT_INSN (dominator); ; next = NEXT_INSN (next))
+ for (next = NEXT_INSN (dominator);; next = NEXT_INSN (next))
{
- if ((GET_RTX_CLASS (GET_CODE (next)) == 'i'
- && (reg_mentioned_p (giv, PATTERN (next))
- || reg_set_p (bl2->biv->src_reg, next)))
- || GET_CODE (next) == JUMP_INSN)
+ if (GET_CODE (next) == JUMP_INSN
+ || (INSN_P (next)
+ && insn_dependent_p (giv_insn, next)))
break;
#ifdef HAVE_cc0
- if (GET_RTX_CLASS (GET_CODE (next)) != 'i'
- || ! sets_cc0_p (PATTERN (next)))
+ if (! INSN_P (next) || ! sets_cc0_p (PATTERN (next)))
#endif
dominator = next;
}
/* Avoid problems with luids by actually moving the insn
and adjusting all luids in the range. */
reorder_insns (giv_insn, giv_insn, dominator);
- for (p = dominator; INSN_UID (p) >= max_uid_for_loop; )
+ for (p = dominator; INSN_UID (p) >= max_uid_for_loop;)
p = PREV_INSN (p);
compute_luids (giv_insn, after_giv, INSN_LUID (p));
/* If the only purpose of the init insn is to initialize
INSN_LUID (p));
}
/* Remove this biv from the chain. */
- if (bl->next)
- {
- /* We move the following giv from *bl->next into *bl.
- We have to update reg_biv_class for that moved biv
- to point to its new address. */
- *bl = *bl->next;
- reg_biv_class[bl->regno] = bl;
- }
- else
- {
- *backbl = 0;
- break;
- }
+ *backbl = bl->next;
}
/* If we can't make it a giv,
n_extra_increment += bl->biv_count - 1;
/* If the loop contains volatile memory references do not allow any
- replacements to take place, since this could loose the volatile markers. */
+ replacements to take place, since this could loose the volatile
+ markers. */
if (n_extra_increment && ! loop_info->has_volatile)
{
- int nregs = first_increment_giv + n_extra_increment;
+ unsigned int nregs = first_increment_giv + n_extra_increment;
/* Reallocate reg_iv_type and reg_iv_info. */
VARRAY_GROW (reg_iv_type, nregs);
struct induction **vp, *v, *next;
int biv_dead_after_loop = 0;
- /* The biv increments lists are in reverse order. Fix this first. */
+ /* The biv increments lists are in reverse order. Fix this
+ first. */
for (v = bl->biv, bl->biv = 0; v; v = next)
{
next = v->next_iv;
HOST_WIDE_INT offset;
rtx set, add_val, old_reg, dest_reg, last_use_insn, note;
int old_regno, new_regno;
+ rtx next_loc_insn;
if (! v->always_executed
|| v->maybe_multiple
add_val = plus_constant (next->add_val, offset);
old_reg = v->dest_reg;
dest_reg = gen_reg_rtx (v->mode);
-
+
/* Unlike reg_iv_type / reg_iv_info, the other three arrays
have been allocated with some slop space, so we may not
actually need to reallocate them. If we do, the following
VARRAY_GROW (may_not_optimize, nregs);
VARRAY_GROW (reg_single_usage, nregs);
}
-
- if (! validate_change (next->insn, next->location, add_val, 0))
+
+ /* Some bivs are incremented with a multi-insn sequence.
+ The first insn contains the add. */
+ next_loc_insn = next->insn;
+ while (! loc_mentioned_in_p (next->location,
+ PATTERN (next_loc_insn)))
+ next_loc_insn = PREV_INSN (next_loc_insn);
+
+ if (next_loc_insn == v->insn)
+ abort ();
+
+ if (! validate_change (next_loc_insn, next->location, add_val, 0))
{
vp = &v->next_iv;
continue;
/* Set last_use_insn so that we can check against it. */
for (last_use_insn = v->insn, p = NEXT_INSN (v->insn);
- p != next->insn;
- p = next_insn_in_loop (p, scan_start, end, loop_top))
+ p != next_loc_insn;
+ p = next_insn_in_loop (loop, p))
{
- if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
+ if (!INSN_P (p))
continue;
if (reg_mentioned_p (old_reg, PATTERN (p)))
{
|| ! validate_change (v->insn, &SET_DEST (set), dest_reg, 0))
{
/* Change the increment at NEXT back to what it was. */
- if (! validate_change (next->insn, next->location,
+ if (! validate_change (next_loc_insn, next->location,
next->add_val, 0))
abort ();
vp = &v->next_iv;
v->always_executed = 1;
v->replaceable = 1;
v->no_const_addval = 0;
-
+
old_regno = REGNO (old_reg);
new_regno = REGNO (dest_reg);
VARRAY_INT (set_in_loop, old_regno)--;
VARRAY_INT (n_times_set, old_regno)--;
VARRAY_INT (n_times_set, new_regno) = 1;
VARRAY_CHAR (may_not_optimize, new_regno) = 0;
-
+
REG_IV_TYPE (new_regno) = GENERAL_INDUCT;
REG_IV_INFO (new_regno) = v;
bl->giv_count++;
v->benefit = rtx_cost (SET_SRC (set), SET);
bl->total_benefit += v->benefit;
-
+
/* Now replace the biv with DEST_REG in all insns between
the replaced increment and the next increment, and
remember the last insn that needed a replacement. */
for (last_use_insn = v->insn, p = NEXT_INSN (v->insn);
- p != next->insn;
- p = next_insn_in_loop (p, scan_start, end, loop_top))
+ p != next_loc_insn;
+ p = next_insn_in_loop (loop, p))
{
rtx note;
-
- if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
+
+ if (! INSN_P (p))
continue;
if (reg_mentioned_p (old_reg, PATTERN (p)))
{
= replace_rtx (XEXP (note, 0), old_reg, dest_reg);
}
}
-
+
v->last_use = last_use_insn;
- v->lifetime = INSN_LUID (v->insn) - INSN_LUID (last_use_insn);
+ v->lifetime = INSN_LUID (last_use_insn) - INSN_LUID (v->insn);
/* If the lifetime is zero, it means that this register is really
a dead store. So mark this as a giv that can be ignored.
This will not prevent the biv from being eliminated. */
/* Search the loop for general induction variables. */
- /* A register is a giv if: it is only set once, it is a function of a
- biv and a constant (or invariant), and it is not a biv. */
-
- not_every_iteration = 0;
- loop_depth = 0;
- maybe_multiple = 0;
- p = scan_start;
- while (1)
- {
- p = NEXT_INSN (p);
- /* At end of a straight-in loop, we are done.
- At end of a loop entered at the bottom, scan the top. */
- if (p == scan_start)
- break;
- if (p == end)
- {
- if (loop_top != 0)
- p = loop_top;
- else
- break;
- if (p == scan_start)
- break;
- }
-
- /* Look for a general induction variable in a register. */
- if (GET_CODE (p) == INSN
- && (set = single_set (p))
- && GET_CODE (SET_DEST (set)) == REG
- && ! VARRAY_CHAR (may_not_optimize, REGNO (SET_DEST (set))))
- {
- rtx src_reg;
- rtx add_val;
- rtx mult_val;
- int benefit;
- rtx regnote = 0;
- rtx last_consec_insn;
-
- dest_reg = SET_DEST (set);
- if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
- continue;
-
- if (/* SET_SRC is a giv. */
- (general_induction_var (SET_SRC (set), &src_reg, &add_val,
- &mult_val, 0, &benefit)
- /* Equivalent expression is a giv. */
- || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
- && general_induction_var (XEXP (regnote, 0), &src_reg,
- &add_val, &mult_val, 0,
- &benefit)))
- /* Don't try to handle any regs made by loop optimization.
- We have nothing on them in regno_first_uid, etc. */
- && REGNO (dest_reg) < max_reg_before_loop
- /* Don't recognize a BASIC_INDUCT_VAR here. */
- && dest_reg != src_reg
- /* This must be the only place where the register is set. */
- && (VARRAY_INT (n_times_set, REGNO (dest_reg)) == 1
- /* or all sets must be consecutive and make a giv. */
- || (benefit = consec_sets_giv (benefit, p,
- src_reg, dest_reg,
- &add_val, &mult_val,
- &last_consec_insn))))
- {
- struct induction *v
- = (struct induction *) alloca (sizeof (struct induction));
-
- /* If this is a library call, increase benefit. */
- if (find_reg_note (p, REG_RETVAL, NULL_RTX))
- benefit += libcall_benefit (p);
-
- /* Skip the consecutive insns, if there are any. */
- if (VARRAY_INT (n_times_set, REGNO (dest_reg)) != 1)
- p = last_consec_insn;
-
- record_giv (v, p, src_reg, dest_reg, mult_val, add_val, benefit,
- DEST_REG, not_every_iteration, maybe_multiple,
- NULL_PTR, loop_start, loop_end);
-
- }
- }
-
-#ifndef DONT_REDUCE_ADDR
- /* Look for givs which are memory addresses. */
- /* This resulted in worse code on a VAX 8600. I wonder if it
- still does. */
- if (GET_CODE (p) == INSN)
- find_mem_givs (PATTERN (p), p, not_every_iteration, maybe_multiple,
- loop_start, loop_end);
-#endif
-
- /* Update the status of whether giv can derive other givs. This can
- change when we pass a label or an insn that updates a biv. */
- if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
- || GET_CODE (p) == CODE_LABEL)
- update_giv_derive (p);
-
- /* Past CODE_LABEL, we get to insns that may be executed multiple
- times. The only way we can be sure that they can't is if every
- every jump insn between here and the end of the loop either
- returns, exits the loop, is a forward jump, or is a jump
- to the loop start. */
-
- if (GET_CODE (p) == CODE_LABEL)
- {
- rtx insn = p;
-
- maybe_multiple = 0;
-
- while (1)
- {
- insn = NEXT_INSN (insn);
- if (insn == scan_start)
- break;
- if (insn == end)
- {
- if (loop_top != 0)
- insn = loop_top;
- else
- break;
- if (insn == scan_start)
- break;
- }
-
- if (GET_CODE (insn) == JUMP_INSN
- && GET_CODE (PATTERN (insn)) != RETURN
- && (! condjump_p (insn)
- || (JUMP_LABEL (insn) != 0
- && JUMP_LABEL (insn) != scan_start
- && (INSN_UID (JUMP_LABEL (insn)) >= max_uid_for_loop
- || INSN_UID (insn) >= max_uid_for_loop
- || (INSN_LUID (JUMP_LABEL (insn))
- < INSN_LUID (insn))))))
- {
- maybe_multiple = 1;
- break;
- }
- }
- }
-
- /* Past a jump, we get to insns for which we can't count
- on whether they will be executed during each iteration. */
- /* This code appears twice in strength_reduce. There is also similar
- code in scan_loop. */
- if (GET_CODE (p) == JUMP_INSN
- /* If we enter the loop in the middle, and scan around to the
- beginning, don't set not_every_iteration for that.
- This can be any kind of jump, since we want to know if insns
- will be executed if the loop is executed. */
- && ! (JUMP_LABEL (p) == loop_top
- && ((NEXT_INSN (NEXT_INSN (p)) == loop_end && simplejump_p (p))
- || (NEXT_INSN (p) == loop_end && condjump_p (p)))))
- {
- rtx label = 0;
-
- /* If this is a jump outside the loop, then it also doesn't
- matter. Check to see if the target of this branch is on the
- loop_number_exits_labels list. */
-
- for (label = loop_number_exit_labels[uid_loop_num[INSN_UID (loop_start)]];
- label;
- label = LABEL_NEXTREF (label))
- if (XEXP (label, 0) == JUMP_LABEL (p))
- break;
-
- if (! label)
- not_every_iteration = 1;
- }
-
- else if (GET_CODE (p) == NOTE)
- {
- /* At the virtual top of a converted loop, insns are again known to
- be executed each iteration: logically, the loop begins here
- even though the exit code has been duplicated.
-
- Insns are also again known to be executed each iteration at
- the LOOP_CONT note. */
- if ((NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP
- || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_CONT)
- && loop_depth == 0)
- not_every_iteration = 0;
- else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
- loop_depth++;
- else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
- loop_depth--;
- }
-
- /* Unlike in the code motion pass where MAYBE_NEVER indicates that
- an insn may never be executed, NOT_EVERY_ITERATION indicates whether
- or not an insn is known to be executed each iteration of the
- loop, whether or not any iterations are known to occur.
-
- Therefore, if we have just passed a label and have no more labels
- between here and the test insn of the loop, we know these insns
- will be executed each iteration. */
-
- if (not_every_iteration && GET_CODE (p) == CODE_LABEL
- && no_labels_between_p (p, loop_end)
- && loop_insn_first_p (p, loop_cont))
- not_every_iteration = 0;
- }
+ for_each_insn_in_loop (loop, check_insn_for_givs);
/* Try to calculate and save the number of loop iterations. This is
set to zero if the actual number can not be calculated. This must
be called after all giv's have been identified, since otherwise it may
fail if the iteration variable is a giv. */
- loop_iterations (loop_start, loop_end, loop_info);
+ loop_iterations (loop);
/* 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
for (v = bl->giv; v; v = v->next_iv)
if (! v->replaceable && ! v->not_replaceable)
- check_final_value (v, loop_start, loop_end, loop_info->n_iterations);
+ check_final_value (loop, v);
}
/* Try to prove that the loop counter variable (if any) is always
nonnegative; if so, record that fact with a REG_NONNEG note
so that "decrement and branch until zero" insn can be used. */
- check_dbra_loop (loop_end, insn_count, loop_start, loop_info);
+ check_dbra_loop (loop, insn_count);
/* Create reg_map to hold substitutions for replaceable giv regs.
Some givs might have been made from biv increments, so look at
reg_iv_type for a suitable size. */
reg_map_size = reg_iv_type->num_elements;
- reg_map = (rtx *) alloca (reg_map_size * sizeof (rtx));
- bzero ((char *) reg_map, reg_map_size * sizeof (rtx));
+ reg_map = (rtx *) xcalloc (reg_map_size, sizeof (rtx));
/* Examine each iv class for feasibility of strength reduction/induction
variable elimination. */
&& ! bl->nonneg
#endif
&& ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
- || ((final_value = final_biv_value (bl, loop_start, loop_end,
- loop_info->n_iterations))
+ || ((final_value = final_biv_value (loop, bl))
#ifdef HAVE_decrement_and_branch_until_zero
&& ! bl->nonneg
#endif
))
- bl->eliminable = maybe_eliminate_biv (bl, loop_start, end, 0,
- threshold, insn_count);
+ bl->eliminable = maybe_eliminate_biv (loop, bl, 0, threshold,
+ insn_count);
else
{
if (loop_dump_stream)
VARRAY_GROW (reg_iv_type, nregs);
VARRAY_GROW (reg_iv_info, nregs);
}
- recombine_givs (bl, loop_start, loop_end, unroll_p);
+ recombine_givs (loop, bl, flags & LOOP_UNROLL);
/* Reduce each giv that we decided to reduce. */
/* Check for case where increment is before the address
giv. Do this test in "loop order". */
else if ((INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn)
- && (INSN_LUID (v->insn) < INSN_LUID (scan_start)
+ && (INSN_LUID (v->insn) < INSN_LUID (loop_scan_start)
|| (INSN_LUID (bl->biv->insn)
- > INSN_LUID (scan_start))))
- || (INSN_LUID (v->insn) < INSN_LUID (scan_start)
- && (INSN_LUID (scan_start)
+ > INSN_LUID (loop_scan_start))))
+ || (INSN_LUID (v->insn) < INSN_LUID (loop_scan_start)
+ && (INSN_LUID (loop_scan_start)
< INSN_LUID (bl->biv->insn))))
auto_inc_opt = -1;
else
if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
|| (auto_inc_opt == -1
&& (prev = prev_nonnote_insn (v->insn)) != 0
- && GET_RTX_CLASS (GET_CODE (prev)) == 'i'
+ && INSN_P (prev)
&& sets_cc0_p (PATTERN (prev))))
auto_inc_opt = 0;
}
/* Rescan all givs. If a giv is the same as a giv not reduced, mark it
as not reduced.
-
+
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 to ensure that it will always be executed no matter
how the loop exits. Otherwise, emit the insn after the loop,
since this is slightly more efficient. */
- if (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
+ if (loop->exit_count)
insert_before = loop_start;
else
insert_before = end_insert_before;
We have to be careful that we didn't initially think we could eliminate
this biv because of a giv that we now think may be dead and shouldn't
- be used as a biv replacement.
+ be used as a biv replacement.
Also, there is the possibility that we may have a giv that looks
like it can be used to eliminate a biv, but the resulting insn
- isn't valid. This can happen, for example, on the 88k, where a
+ isn't valid. This can happen, for example, on the 88k, where a
JUMP_INSN can compare a register only with zero. Attempts to
replace it with a compare with a constant will fail.
doing so in the rare cases where it can occur. */
if (all_reduced == 1 && bl->eliminable
- && maybe_eliminate_biv (bl, loop_start, end, 1,
- threshold, insn_count))
-
+ && maybe_eliminate_biv (loop, bl, 1, threshold, insn_count))
{
/* ?? If we created a new test to bypass the loop entirely,
or otherwise drop straight in, based on this test, then
loop to ensure that it will always be executed no matter
how the loop exits. Otherwise, emit the insn after the
loop, since this is slightly more efficient. */
- if (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
+ if (loop->exit_count)
insert_before = loop_start;
else
insert_before = end_insert_before;
/* Go through all the instructions in the loop, making all the
register substitutions scheduled in REG_MAP. */
- for (p = loop_start; p != end; p = NEXT_INSN (p))
+ for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
- || GET_CODE (p) == CALL_INSN)
+ || GET_CODE (p) == CALL_INSN)
{
replace_regs (PATTERN (p), reg_map, reg_map_size, 0);
replace_regs (REG_NOTES (p), reg_map, reg_map_size, 0);
if (unrolled_insn_copies < 0)
unrolled_insn_copies = 0;
}
-
+
/* Unroll loops from within strength reduction so that we can use the
induction variable information that strength_reduce has already
collected. Always unroll loops that would be as small or smaller
unrolled than when rolled. */
- if (unroll_p
+ if ((flags & LOOP_UNROLL)
|| (loop_info->n_iterations > 0
&& unrolled_insn_copies <= insn_count))
- unroll_loop (loop_end, insn_count, loop_start, end_insert_before,
- loop_info, 1);
+ unroll_loop (loop, insn_count, end_insert_before, 1);
-#ifdef HAVE_decrement_and_branch_on_count
- /* Instrument the loop with BCT insn. */
- if (HAVE_decrement_and_branch_on_count && bct_p
- && flag_branch_on_count_reg)
- insert_bct (loop_start, loop_end, loop_info);
-#endif /* HAVE_decrement_and_branch_on_count */
+#ifdef HAVE_doloop_end
+ if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg)
+ doloop_optimize (loop);
+#endif /* HAVE_doloop_end */
if (loop_dump_stream)
fprintf (loop_dump_stream, "\n");
egress:
VARRAY_FREE (reg_iv_type);
VARRAY_FREE (reg_iv_info);
+ free (reg_biv_class);
+ if (reg_map)
+ free (reg_map);
+}
+\f
+/*Record all basic induction variables calculated in the insn. */
+static rtx
+check_insn_for_bivs (loop, p, not_every_iteration, maybe_multiple)
+ struct loop *loop;
+ rtx p;
+ int not_every_iteration;
+ int maybe_multiple;
+{
+ rtx set;
+ rtx dest_reg;
+ rtx inc_val;
+ rtx mult_val;
+ rtx *location;
+
+ if (GET_CODE (p) == INSN
+ && (set = single_set (p))
+ && GET_CODE (SET_DEST (set)) == REG)
+ {
+ dest_reg = SET_DEST (set);
+ if (REGNO (dest_reg) < max_reg_before_loop
+ && REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
+ && REG_IV_TYPE (REGNO (dest_reg)) != NOT_BASIC_INDUCT)
+ {
+ if (basic_induction_var (loop, SET_SRC (set),
+ GET_MODE (SET_SRC (set)),
+ dest_reg, p, &inc_val, &mult_val,
+ &location))
+ {
+ /* It is a possible basic induction variable.
+ Create and initialize an induction structure for it. */
+
+ struct induction *v
+ = (struct induction *) oballoc (sizeof (struct induction));
+
+ record_biv (v, p, dest_reg, inc_val, mult_val, location,
+ not_every_iteration, maybe_multiple);
+ REG_IV_TYPE (REGNO (dest_reg)) = BASIC_INDUCT;
+ }
+ else if (REGNO (dest_reg) < max_reg_before_loop)
+ REG_IV_TYPE (REGNO (dest_reg)) = NOT_BASIC_INDUCT;
+ }
+ }
+ return p;
+}
+\f
+/* Record all givs calculated in the insn.
+ A register is a giv if: it is only set once, it is a function of a
+ biv and a constant (or invariant), and it is not a biv. */
+static rtx
+check_insn_for_givs (loop, p, not_every_iteration, maybe_multiple)
+ struct loop *loop;
+ rtx p;
+ int not_every_iteration;
+ int maybe_multiple;
+{
+ rtx set;
+ /* Look for a general induction variable in a register. */
+ if (GET_CODE (p) == INSN
+ && (set = single_set (p))
+ && GET_CODE (SET_DEST (set)) == REG
+ && ! VARRAY_CHAR (may_not_optimize, REGNO (SET_DEST (set))))
+ {
+ rtx src_reg;
+ rtx dest_reg;
+ rtx add_val;
+ rtx mult_val;
+ int benefit;
+ rtx regnote = 0;
+ rtx last_consec_insn;
+
+ dest_reg = SET_DEST (set);
+ if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
+ return p;
+
+ if (/* SET_SRC is a giv. */
+ (general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
+ &mult_val, 0, &benefit, VOIDmode)
+ /* Equivalent expression is a giv. */
+ || ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
+ && general_induction_var (loop, XEXP (regnote, 0), &src_reg,
+ &add_val, &mult_val, 0,
+ &benefit, VOIDmode)))
+ /* Don't try to handle any regs made by loop optimization.
+ We have nothing on them in regno_first_uid, etc. */
+ && REGNO (dest_reg) < max_reg_before_loop
+ /* Don't recognize a BASIC_INDUCT_VAR here. */
+ && dest_reg != src_reg
+ /* This must be the only place where the register is set. */
+ && (VARRAY_INT (n_times_set, REGNO (dest_reg)) == 1
+ /* or all sets must be consecutive and make a giv. */
+ || (benefit = consec_sets_giv (loop, benefit, p,
+ src_reg, dest_reg,
+ &add_val, &mult_val,
+ &last_consec_insn))))
+ {
+ struct induction *v
+ = (struct induction *) oballoc (sizeof (struct induction));
+
+ /* If this is a library call, increase benefit. */
+ if (find_reg_note (p, REG_RETVAL, NULL_RTX))
+ benefit += libcall_benefit (p);
+
+ /* Skip the consecutive insns, if there are any. */
+ if (VARRAY_INT (n_times_set, REGNO (dest_reg)) != 1)
+ p = last_consec_insn;
+
+ record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
+ benefit, DEST_REG, not_every_iteration,
+ maybe_multiple, NULL_PTR);
+
+ }
+ }
+
+#ifndef DONT_REDUCE_ADDR
+ /* Look for givs which are memory addresses. */
+ /* This resulted in worse code on a VAX 8600. I wonder if it
+ still does. */
+ if (GET_CODE (p) == INSN)
+ find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
+ maybe_multiple);
+#endif
+
+ /* Update the status of whether giv can derive other givs. This can
+ change when we pass a label or an insn that updates a biv. */
+ if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
+ || GET_CODE (p) == CODE_LABEL)
+ update_giv_derive (loop, p);
+ return p;
}
\f
/* Return 1 if X is a valid source for an initial value (or as value being
more thanonce in each loop iteration. */
static void
-find_mem_givs (x, insn, not_every_iteration, maybe_multiple, loop_start,
- loop_end)
+find_mem_givs (loop, x, insn, not_every_iteration, maybe_multiple)
+ const struct loop *loop;
rtx x;
rtx insn;
int not_every_iteration, maybe_multiple;
- rtx loop_start, loop_end;
{
register int i, j;
register enum rtx_code code;
int benefit;
/* This code used to disable creating GIVs with mult_val == 1 and
- add_val == 0. However, this leads to lost optimizations when
+ 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. */
- if (general_induction_var (XEXP (x, 0), &src_reg, &add_val,
- &mult_val, 1, &benefit))
+ if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
+ &mult_val, 1, &benefit, GET_MODE (x)))
{
/* Found one; record it. */
struct induction *v
= (struct induction *) oballoc (sizeof (struct induction));
- record_giv (v, insn, src_reg, addr_placeholder, mult_val,
+ record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
add_val, benefit, DEST_ADDR, not_every_iteration,
- maybe_multiple, &XEXP (x, 0), loop_start, loop_end);
+ maybe_multiple, &XEXP (x, 0));
v->mem_mode = GET_MODE (x);
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
if (fmt[i] == 'e')
- find_mem_givs (XEXP (x, i), insn, not_every_iteration, maybe_multiple,
- loop_start, loop_end);
+ find_mem_givs (loop, XEXP (x, i), insn, not_every_iteration,
+ maybe_multiple);
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
- find_mem_givs (XVECEXP (x, i, j), insn, not_every_iteration,
- maybe_multiple, loop_start, loop_end);
+ find_mem_givs (loop, XVECEXP (x, i, j), insn, not_every_iteration,
+ maybe_multiple);
}
\f
/* Fill in the data about one biv update.
LOCATION points to the place where this giv's value appears in INSN. */
static void
-record_giv (v, insn, src_reg, dest_reg, mult_val, add_val, benefit,
- type, not_every_iteration, maybe_multiple, location, loop_start,
- loop_end)
+record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, benefit,
+ type, not_every_iteration, maybe_multiple, location)
+ const struct loop *loop;
struct induction *v;
rtx insn;
rtx src_reg;
enum g_types type;
int not_every_iteration, maybe_multiple;
rtx *location;
- rtx loop_start, loop_end;
{
struct induction *b;
struct iv_class *bl;
rtx set = single_set (insn);
+ rtx temp;
+
+ /* Attempt to prove constantness of the values. */
+ temp = simplify_rtx (add_val);
+ if (temp)
+ add_val = temp;
v->insn = insn;
v->src_reg = src_reg;
if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
/* Previous line always fails if INSN was moved by loop opt. */
- && uid_luid[REGNO_LAST_UID (REGNO (dest_reg))] < INSN_LUID (loop_end)
+ && uid_luid[REGNO_LAST_UID (REGNO (dest_reg))]
+ < INSN_LUID (loop->end)
&& (! not_every_iteration
|| last_use_this_basic_block (dest_reg, insn)))
- {
+ {
/* Now check that there are no assignments to the biv within the
giv's lifetime. This requires two separate checks. */
/* Check each biv update, and fail if any are between the first
and last use of the giv.
-
+
If this loop contains an inner loop that was unrolled, then
the insn modifying the biv may have been emitted by the loop
unrolling code, and hence does not have a valid luid. Just
v->replaceable = 0;
v->not_replaceable = 1;
break;
- }
+ }
}
/* If there are any backwards branches that go from after the
biv update to before it, then this giv is not replaceable. */
if (v->replaceable)
for (b = bl->biv; b; b = b->next_iv)
- if (back_branch_in_range_p (b->insn, loop_start, loop_end))
+ if (back_branch_in_range_p (loop, b->insn))
{
v->replaceable = 0;
v->not_replaceable = 1;
v->no_const_addval = 1;
if (tem == const0_rtx)
;
- else if (GET_CODE (tem) == CONST_INT)
+ else if (CONSTANT_P (add_val))
v->no_const_addval = 0;
- else if (GET_CODE (tem) == PLUS)
+ if (GET_CODE (tem) == PLUS)
{
- while (1)
+ while (1)
{
if (GET_CODE (XEXP (tem, 0)) == PLUS)
tem = XEXP (tem, 0);
else
break;
}
- if (GET_CODE (XEXP (tem, 1)) == CONST_INT)
- v->no_const_addval = 0;
+ if (CONSTANT_P (XEXP (tem, 1)))
+ v->no_const_addval = 0;
}
}
}
-
/* All this does is determine whether a giv can be made replaceable because
its final value can be calculated. This code can not be part of record_giv
above, because final_giv_value requires that the number of loop iterations
have been identified. */
static void
-check_final_value (v, loop_start, loop_end, n_iterations)
+check_final_value (loop, v)
+ const struct loop *loop;
struct induction *v;
- rtx loop_start, loop_end;
- unsigned HOST_WIDE_INT n_iterations;
{
struct iv_class *bl;
rtx final_value = 0;
v->replaceable = 0;
#endif
- if ((final_value = final_giv_value (v, loop_start, loop_end, n_iterations))
+ if ((final_value = final_giv_value (loop, v))
&& (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
{
int biv_increment_seen = 0;
while (1)
{
p = NEXT_INSN (p);
- if (p == loop_end)
- p = NEXT_INSN (loop_start);
+ if (p == loop->end)
+ p = NEXT_INSN (loop->start);
if (p == v->insn)
break;
last_giv_use = p;
}
}
-
+
/* Now that the lifetime of the giv is known, check for branches
from within the lifetime to outside the lifetime if it is still
replaceable. */
while (1)
{
p = NEXT_INSN (p);
- if (p == loop_end)
- p = NEXT_INSN (loop_start);
+ if (p == loop->end)
+ p = NEXT_INSN (loop->start);
if (p == last_giv_use)
break;
if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
&& LABEL_NAME (JUMP_LABEL (p))
&& ((loop_insn_first_p (JUMP_LABEL (p), v->insn)
- && loop_insn_first_p (loop_start, JUMP_LABEL (p)))
+ && loop_insn_first_p (loop->start, JUMP_LABEL (p)))
|| (loop_insn_first_p (last_giv_use, JUMP_LABEL (p))
- && loop_insn_first_p (JUMP_LABEL (p), loop_end))))
+ && loop_insn_first_p (JUMP_LABEL (p), loop->end))))
{
v->replaceable = 0;
v->not_replaceable = 1;
The cases we look at are when a label or an update to a biv is passed. */
static void
-update_giv_derive (p)
+update_giv_derive (loop, p)
+ const struct loop *loop;
rtx p;
{
struct iv_class *bl;
tem = 0;
if (biv->mult_val == const1_rtx)
- tem = simplify_giv_expr (gen_rtx_MULT (giv->mode,
+ tem = simplify_giv_expr (loop,
+ gen_rtx_MULT (giv->mode,
biv->add_val,
giv->mult_val),
&dummy);
if (tem && giv->derive_adjustment)
tem = simplify_giv_expr
- (gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
+ (loop,
+ gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
&dummy);
if (tem)
Note that treating the entire pseudo as a BIV will result in making
simple increments to any GIVs based on it. However, if the variable
overflows in its declared mode but not its promoted mode, the result will
- be incorrect. This is acceptable if the variable is signed, since
+ be incorrect. This is acceptable if the variable is signed, since
overflows in such cases are undefined, but not if it is unsigned, since
those overflows are defined. So we only check for SIGN_EXTEND and
not ZERO_EXTEND.
If we cannot find a biv, we return 0. */
static int
-basic_induction_var (x, mode, dest_reg, p, inc_val, mult_val, location)
+basic_induction_var (loop, x, mode, dest_reg, p, inc_val, mult_val, location)
+ const struct loop *loop;
register rtx x;
enum machine_mode mode;
- rtx p;
rtx dest_reg;
+ rtx p;
rtx *inc_val;
rtx *mult_val;
rtx **location;
argp = &XEXP (x, 0);
}
else
- return 0;
+ return 0;
arg = *argp;
- if (invariant_p (arg) != 1)
+ if (loop_invariant_p (loop, arg) != 1)
return 0;
*inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
/* If this is a SUBREG for a promoted variable, check the inner
value. */
if (SUBREG_PROMOTED_VAR_P (x))
- return basic_induction_var (SUBREG_REG (x), GET_MODE (SUBREG_REG (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 this register is assigned in a previous insn, look at its
source, but don't go outside the loop or past a label. */
+ /* If this sets a register to itself, we would repeat any previous
+ biv increment if we applied this strategy blindly. */
+ if (rtx_equal_p (dest_reg, x))
+ return 0;
+
insn = p;
while (1)
{
- do {
- insn = PREV_INSN (insn);
- } while (insn && GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
+ do
+ {
+ insn = PREV_INSN (insn);
+ }
+ while (insn && GET_CODE (insn) == NOTE
+ && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
- if (!insn)
+ if (!insn)
break;
set = single_set (insn);
if (set == 0)
|| (GET_CODE (SET_DEST (set)) == SUBREG
&& (GET_MODE_SIZE (GET_MODE (SET_DEST (set)))
<= UNITS_PER_WORD)
+ && (GET_MODE_CLASS (GET_MODE (SET_DEST (set)))
+ == MODE_INT)
&& SUBREG_REG (SET_DEST (set)) == x))
- && basic_induction_var (SET_SRC (set),
+ && basic_induction_var (loop, SET_SRC (set),
(GET_MODE (SET_SRC (set)) == VOIDmode
? GET_MODE (x)
: GET_MODE (SET_SRC (set))),
as a biv of the outer loop,
causing code to be moved INTO the inner loop. */
case MEM:
- if (invariant_p (x) != 1)
+ if (loop_invariant_p (loop, x) != 1)
return 0;
case CONST_INT:
case SYMBOL_REF:
/* convert_modes aborts if we try to convert to or from CCmode, so just
exclude that case. It is very unlikely that a condition code value
would be a useful iterator anyways. */
- if (this_loop_info.loops_enclosed == 1
+ if (loop->level == 1
&& GET_MODE_CLASS (mode) != MODE_CC
&& GET_MODE_CLASS (GET_MODE (dest_reg)) != 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);
- *mult_val = const0_rtx;
- return 1;
- }
+ *mult_val = const0_rtx;
+ return 1;
+ }
else
- return 0;
+ return 0;
case SIGN_EXTEND:
- return basic_induction_var (XEXP (x, 0), GET_MODE (XEXP (x, 0)),
+ return basic_induction_var (loop, XEXP (x, 0), GET_MODE (XEXP (x, 0)),
dest_reg, p, inc_val, mult_val, location);
case ASHIFTRT:
if (insn)
set = single_set (insn);
- if (set && SET_DEST (set) == XEXP (x, 0)
+ if (! rtx_equal_p (dest_reg, XEXP (x, 0))
+ && set && SET_DEST (set) == XEXP (x, 0)
&& GET_CODE (XEXP (x, 1)) == CONST_INT
&& INTVAL (XEXP (x, 1)) >= 0
&& GET_CODE (SET_SRC (set)) == ASHIFT
&& XEXP (x, 1) == XEXP (SET_SRC (set), 1))
- return basic_induction_var (XEXP (SET_SRC (set), 0),
+ return basic_induction_var (loop, XEXP (SET_SRC (set), 0),
GET_MODE (XEXP (x, 0)),
dest_reg, insn, inc_val, mult_val,
location);
such that the value of X is biv * mult + add; */
static int
-general_induction_var (x, src_reg, add_val, mult_val, is_addr, pbenefit)
+general_induction_var (loop, x, src_reg, add_val, mult_val, is_addr,
+ pbenefit, addr_mode)
+ const struct loop *loop;
rtx x;
rtx *src_reg;
rtx *add_val;
rtx *mult_val;
int is_addr;
int *pbenefit;
+ enum machine_mode addr_mode;
{
rtx orig_x = x;
char *storage;
/* If this is an invariant, forget it, it isn't a giv. */
- if (invariant_p (x) == 1)
+ if (loop_invariant_p (loop, x) == 1)
return 0;
/* See if the expression could be a giv and get its form.
Mark our place on the obstack in case we don't find a giv. */
storage = (char *) oballoc (0);
*pbenefit = 0;
- x = simplify_giv_expr (x, pbenefit);
+ x = simplify_giv_expr (loop, x, pbenefit);
if (x == 0)
{
obfree (storage);
*mult_val = XEXP (*mult_val, 0);
if (is_addr)
- {
-#ifdef ADDRESS_COST
- *pbenefit += ADDRESS_COST (orig_x) - reg_address_cost;
-#else
- *pbenefit += rtx_cost (orig_x, MEM) - reg_address_cost;
-#endif
- }
+ *pbenefit += address_cost (orig_x, addr_mode) - reg_address_cost;
else
*pbenefit += rtx_cost (orig_x, SET);
/* Always return true if this is a giv so it will be detected as such,
- even if the benefit is zero or negative. This allows elimination
- of bivs that might otherwise not be eliminated. */
- return 1;
+ even if the benefit is zero or negative. This allows elimination
+ of bivs that might otherwise not be eliminated. */
+ return 1;
}
\f
/* Given an expression, X, try to form it as a linear function of a biv.
returns 0.
For a non-zero return, the result will have a code of CONST_INT, USE,
- REG (for a BIV), PLUS, or MULT. No other codes will occur.
+ REG (for a BIV), PLUS, or MULT. No other codes will occur.
*BENEFIT will be incremented by the benefit of any sub-giv encountered. */
-static rtx sge_plus PROTO ((enum machine_mode, rtx, rtx));
-static rtx sge_plus_constant PROTO ((rtx, rtx));
+static rtx sge_plus PARAMS ((enum machine_mode, rtx, rtx));
+static rtx sge_plus_constant PARAMS ((rtx, rtx));
+static int cmp_combine_givs_stats PARAMS ((const PTR, const PTR));
+static int cmp_recombine_givs_stats PARAMS ((const PTR, const PTR));
static rtx
-simplify_giv_expr (x, benefit)
+simplify_giv_expr (loop, x, benefit)
+ const struct loop *loop;
rtx x;
int *benefit;
{
switch (GET_CODE (x))
{
case PLUS:
- arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
- arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
+ arg0 = simplify_giv_expr (loop, XEXP (x, 0), benefit);
+ arg1 = simplify_giv_expr (loop, XEXP (x, 1), benefit);
if (arg0 == 0 || arg1 == 0)
return NULL_RTX;
case PLUS:
/* (a + invar_1) + invar_2. Associate. */
return
- simplify_giv_expr (gen_rtx_PLUS (mode,
+ simplify_giv_expr (loop,
+ gen_rtx_PLUS (mode,
XEXP (arg0, 0),
gen_rtx_PLUS (mode,
XEXP (arg0, 1),
if (GET_CODE (arg1) == PLUS)
return
- simplify_giv_expr (gen_rtx_PLUS (mode,
+ simplify_giv_expr (loop,
+ gen_rtx_PLUS (mode,
gen_rtx_PLUS (mode, arg0,
XEXP (arg1, 0)),
XEXP (arg1, 1)),
if (!rtx_equal_p (arg0, arg1))
return NULL_RTX;
- return simplify_giv_expr (gen_rtx_MULT (mode,
+ return simplify_giv_expr (loop,
+ gen_rtx_MULT (mode,
XEXP (arg0, 0),
gen_rtx_PLUS (mode,
XEXP (arg0, 1),
case MINUS:
/* Handle "a - b" as "a + b * (-1)". */
- return simplify_giv_expr (gen_rtx_PLUS (mode,
+ return simplify_giv_expr (loop,
+ gen_rtx_PLUS (mode,
XEXP (x, 0),
gen_rtx_MULT (mode,
XEXP (x, 1),
benefit);
case MULT:
- arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
- arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
+ arg0 = simplify_giv_expr (loop, XEXP (x, 0), benefit);
+ arg1 = simplify_giv_expr (loop, XEXP (x, 1), benefit);
if (arg0 == 0 || arg1 == 0)
return NULL_RTX;
return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
case USE:
- /* invar * invar. It is a giv, but very few of these will
- actually pay off, so limit to simple registers. */
+ /* invar * invar is a giv, but attempt to simplify it somehow. */
if (GET_CODE (arg1) != CONST_INT)
return NULL_RTX;
arg0 = XEXP (arg0, 0);
- if (GET_CODE (arg0) == REG)
- tem = gen_rtx_MULT (mode, arg0, arg1);
- else if (GET_CODE (arg0) == MULT
- && GET_CODE (XEXP (arg0, 0)) == REG
- && GET_CODE (XEXP (arg0, 1)) == CONST_INT)
+ if (GET_CODE (arg0) == MULT)
{
- tem = gen_rtx_MULT (mode, XEXP (arg0, 0),
- GEN_INT (INTVAL (XEXP (arg0, 1))
- * INTVAL (arg1)));
+ /* (invar_0 * invar_1) * invar_2. Associate. */
+ return simplify_giv_expr (loop,
+ gen_rtx_MULT (mode,
+ XEXP (arg0, 0),
+ gen_rtx_MULT (mode,
+ XEXP (arg0,
+ 1),
+ arg1)),
+ benefit);
}
- else
- return NULL_RTX;
- return gen_rtx_USE (mode, tem);
+ /* Porpagate the MULT expressions to the intermost nodes. */
+ else if (GET_CODE (arg0) == PLUS)
+ {
+ /* (invar_0 + invar_1) * invar_2. Distribute. */
+ return simplify_giv_expr (loop,
+ gen_rtx_PLUS (mode,
+ gen_rtx_MULT (mode,
+ XEXP (arg0,
+ 0),
+ arg1),
+ gen_rtx_MULT (mode,
+ XEXP (arg0,
+ 1),
+ arg1)),
+ benefit);
+ }
+ return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
case MULT:
/* (a * invar_1) * invar_2. Associate. */
- return simplify_giv_expr (gen_rtx_MULT (mode,
+ return simplify_giv_expr (loop,
+ gen_rtx_MULT (mode,
XEXP (arg0, 0),
gen_rtx_MULT (mode,
XEXP (arg0, 1),
case PLUS:
/* (a + invar_1) * invar_2. Distribute. */
- return simplify_giv_expr (gen_rtx_PLUS (mode,
+ return simplify_giv_expr (loop,
+ gen_rtx_PLUS (mode,
gen_rtx_MULT (mode,
XEXP (arg0, 0),
arg1),
return 0;
return
- simplify_giv_expr (gen_rtx_MULT (mode,
+ simplify_giv_expr (loop,
+ gen_rtx_MULT (mode,
XEXP (x, 0),
GEN_INT ((HOST_WIDE_INT) 1
<< INTVAL (XEXP (x, 1)))),
case NEG:
/* "-a" is "a * (-1)" */
- return simplify_giv_expr (gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
+ return simplify_giv_expr (loop,
+ gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
benefit);
case NOT:
/* "~a" is "-a - 1". Silly, but easy. */
- return simplify_giv_expr (gen_rtx_MINUS (mode,
+ return simplify_giv_expr (loop,
+ gen_rtx_MINUS (mode,
gen_rtx_NEG (mode, XEXP (x, 0)),
const1_rtx),
benefit);
if (v->derive_adjustment)
tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
- return simplify_giv_expr (tem, benefit);
+ return simplify_giv_expr (loop, tem, benefit);
}
default:
/* If it isn't an induction variable, and it is invariant, we
may be able to simplify things further by looking through
the bits we just moved outside the loop. */
- if (invariant_p (x) == 1)
+ if (loop_invariant_p (loop, x) == 1)
{
struct movable *m;
- for (m = the_movables; m ; m = m->next)
+ for (m = the_movables; m; m = m->next)
if (rtx_equal_p (x, m->set_dest))
{
/* Ok, we found a match. Substitute and simplify. */
- /* If we match another movable, we must use that, as
+ /* If we match another movable, we must use that, as
this one is going away. */
if (m->match)
- return simplify_giv_expr (m->match->set_dest, benefit);
+ return simplify_giv_expr (loop, m->match->set_dest,
+ benefit);
/* If consec is non-zero, this is a member of a group of
instructions that were moved together. We handle this
}
else
{
- tem = single_set (m->insn);
- if (tem)
+ tem = single_set (m->insn);
+ if (tem)
tem = SET_SRC (tem);
}
|| GET_CODE (tem) == CONST_INT
|| GET_CODE (tem) == SYMBOL_REF)
{
- tem = simplify_giv_expr (tem, benefit);
+ tem = simplify_giv_expr (loop, tem, benefit);
if (tem)
return tem;
}
&& GET_CODE (XEXP (XEXP (tem, 0), 0)) == SYMBOL_REF
&& GET_CODE (XEXP (XEXP (tem, 0), 1)) == CONST_INT)
{
- tem = simplify_giv_expr (XEXP (tem, 0), benefit);
+ tem = simplify_giv_expr (loop, XEXP (tem, 0),
+ benefit);
if (tem)
return tem;
}
if (GET_CODE (x) == USE)
x = XEXP (x, 0);
- if (invariant_p (x) == 1)
+ if (loop_invariant_p (loop, x) == 1)
{
if (GET_CODE (x) == CONST_INT)
return x;
*MULT_VAL and *ADD_VAL. */
static int
-consec_sets_giv (first_benefit, p, src_reg, dest_reg,
+consec_sets_giv (loop, first_benefit, p, src_reg, dest_reg,
add_val, mult_val, last_consec_insn)
+ const struct loop *loop;
int first_benefit;
rtx p;
rtx src_reg;
rtx set;
/* Indicate that this is a giv so that we can update the value produced in
- each insn of the multi-insn sequence.
+ each insn of the multi-insn sequence.
This induction structure will be used only by the call to
general_induction_var below, so we can allocate it on our stack.
&& (set = single_set (p))
&& GET_CODE (SET_DEST (set)) == REG
&& SET_DEST (set) == dest_reg
- && (general_induction_var (SET_SRC (set), &src_reg,
- add_val, mult_val, 0, &benefit)
+ && (general_induction_var (loop, SET_SRC (set), &src_reg,
+ add_val, mult_val, 0, &benefit, VOIDmode)
/* Giv created by equivalent expression. */
|| ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
- && general_induction_var (XEXP (temp, 0), &src_reg,
- add_val, mult_val, 0, &benefit)))
+ && general_induction_var (loop, XEXP (temp, 0), &src_reg,
+ add_val, mult_val, 0, &benefit,
+ VOIDmode)))
&& src_reg == v->src_reg)
{
if (find_reg_note (p, REG_RETVAL, NULL_RTX))
\f
/* Return an rtx, if any, that expresses giv G2 as a function of the register
represented by G1. If no such expression can be found, or it is clear that
- it cannot possibly be a valid address, 0 is returned.
+ it cannot possibly be a valid address, 0 is returned.
To perform the computation, we note that
G1 = x * v + a and
ra = XEXP (a, 0), oa = XEXP (a, 1);
if (GET_CODE (ra) == PLUS)
- tmp = ra, ra = oa, oa = tmp;
+ tmp = ra, ra = oa, oa = tmp;
rb = XEXP (b, 0), ob = XEXP (b, 1);
if (GET_CODE (rb) == PLUS)
- tmp = rb, rb = ob, ob = tmp;
+ tmp = rb, rb = ob, ob = tmp;
if (rtx_equal_p (ra, rb))
/* We matched: remove one reg completely. */
a = ra, b = ob;
else
{
- /* Indicates an extra register in B. Strip one level from B and
+ /* Indicates an extra register in B. Strip one level from B and
recurse, hoping B was the higher order expression. */
ob = express_from_1 (a, ob, mult);
if (ob == NULL_RTX)
{
return plus_constant (b, -INTVAL (a) * INTVAL (mult));
}
+ else if (CONSTANT_P (a))
+ {
+ return simplify_gen_binary (MINUS, GET_MODE (b) != VOIDmode ? GET_MODE (b) : GET_MODE (a), const0_rtx, a);
+ }
else if (GET_CODE (b) == PLUS)
{
if (rtx_equal_p (a, XEXP (b, 0)))
&& GET_CODE (g2->mult_val) == CONST_INT)
{
if (g1->mult_val == const0_rtx
- || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
- return NULL_RTX;
+ || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
+ return NULL_RTX;
mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
}
else if (rtx_equal_p (g1->mult_val, g2->mult_val))
mult = gen_rtx_PLUS (g2->mode, mult, XEXP (add, 0));
add = tem;
}
-
+
return gen_rtx_PLUS (g2->mode, mult, add);
}
-
}
\f
/* Return an rtx, if any, that expresses giv G2 as a function of the register
};
static int
-cmp_combine_givs_stats (x, y)
- struct combine_givs_stats *x, *y;
+cmp_combine_givs_stats (xp, yp)
+ const PTR xp;
+ const PTR yp;
{
+ const struct combine_givs_stats * const x =
+ (const struct combine_givs_stats *) xp;
+ const struct combine_givs_stats * const y =
+ (const struct combine_givs_stats *) yp;
int d;
d = y->total_benefit - x->total_benefit;
/* Stabilize the sort. */
if (!g1->ignore)
giv_array[i++] = g1;
- stats = (struct combine_givs_stats *) alloca (giv_count * sizeof (*stats));
- bzero ((char *) stats, giv_count * sizeof (*stats));
-
- can_combine = (rtx *) alloca (giv_count * giv_count * sizeof(rtx));
- bzero ((char *) can_combine, giv_count * giv_count * sizeof(rtx));
+ stats = (struct combine_givs_stats *) xcalloc (giv_count, sizeof (*stats));
+ can_combine = (rtx *) xcalloc (giv_count, giv_count * sizeof (rtx));
for (i = 0; i < giv_count; i++)
{
/* If a DEST_REG GIV is used only once, do not allow it to combine
with anything, for in doing so we will gain nothing that cannot
be had by simply letting the GIV with which we would have combined
- to be reduced on its own. The losage shows up in particular with
+ to be reduced on its own. The losage shows up in particular with
DEST_ADDR targets on hosts with reg+reg addressing, though it can
be seen elsewhere as well. */
if (g1->giv_type == DEST_REG
if (g1 != g2
&& (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
{
- can_combine[i*giv_count + j] = this_combine;
+ can_combine[i * giv_count + j] = this_combine;
this_benefit += g2->benefit + extra_benefit;
}
}
/* Iterate, combining until we can't. */
restart:
- qsort (stats, giv_count, sizeof(*stats), cmp_combine_givs_stats);
+ qsort (stats, giv_count, sizeof (*stats), cmp_combine_givs_stats);
if (loop_dump_stream)
{
{
g1 = giv_array[stats[k].giv_number];
if (!g1->combined_with && !g1->same)
- fprintf (loop_dump_stream, " {%d, %d}",
+ fprintf (loop_dump_stream, " {%d, %d}",
INSN_UID (giv_array[stats[k].giv_number]->insn),
stats[k].total_benefit);
}
for (j = 0; j < giv_count; j++)
{
g2 = giv_array[j];
- if (g1 != g2 && can_combine[i*giv_count + j]
+ if (g1 != g2 && can_combine[i * giv_count + j]
/* If it has already been combined, skip. */
&& ! g2->same && ! g2->combined_with)
{
int l;
- g2->new_reg = can_combine[i*giv_count + j];
+ g2->new_reg = can_combine[i * giv_count + j];
g2->same = g1;
g1->combined_with++;
g1->lifetime += g2->lifetime;
longer be necessary. */
if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
g1_add_benefit -= copy_cost;
-
+
/* To help optimize the next set of combinations, remove
this giv from the benefits of other potential mates. */
for (l = 0; l < giv_count; ++l)
{
int m = stats[l].giv_number;
- if (can_combine[m*giv_count + j])
+ if (can_combine[m * giv_count + j])
stats[l].total_benefit -= g2->benefit + extra_benefit;
}
for (j = 0; j < giv_count; ++j)
{
int m = stats[j].giv_number;
- if (can_combine[m*giv_count + i])
+ if (can_combine[m * giv_count + i])
stats[j].total_benefit -= g1->benefit + extra_benefit;
}
g1->benefit += g1_add_benefit;
/* We've finished with this giv, and everything it touched.
- Restart the combination so that proper weights for the
+ Restart the combination so that proper weights for the
rest of the givs are properly taken into account. */
/* ??? Ideally we would compact the arrays at this point, so
as to not cover old ground. But sanely compacting
goto restart;
}
}
+
+ /* Clean up. */
+ free (stats);
+ free (can_combine);
}
\f
struct recombine_givs_stats
when scanning the array starting at the end, thus the arguments are
used in reverse. */
static int
-cmp_recombine_givs_stats (x, y)
- struct recombine_givs_stats *x, *y;
+cmp_recombine_givs_stats (xp, yp)
+ const PTR xp;
+ const PTR yp;
{
+ const struct recombine_givs_stats * const x =
+ (const struct recombine_givs_stats *) xp;
+ const struct recombine_givs_stats * const y =
+ (const struct recombine_givs_stats *) yp;
int d;
d = y->start_luid - x->start_luid;
/* Stabilize the sort. */
retval += find_life_end (XEXP (x, i), stats, insn, biv);
else if (fmt[i] == 'E')
- for (j = XVECLEN (x, i) - 1; j >= 0; j--)
+ for (j = XVECLEN (x, i) - 1; j >= 0; j--)
retval += find_life_end (XVECEXP (x, i, j), stats, insn, biv);
}
return retval;
This tends to shorten giv lifetimes, and helps the next step:
try to derive givs from other givs. */
static void
-recombine_givs (bl, loop_start, loop_end, unroll_p)
+recombine_givs (loop, bl, unroll_p)
+ const struct loop *loop;
struct iv_class *bl;
- rtx loop_start, loop_end;
int unroll_p;
{
struct induction *v, **giv_array, *last_giv;
giv_count++;
}
giv_array
- = (struct induction **) alloca (giv_count * sizeof (struct induction *));
- stats = (struct recombine_givs_stats *) alloca (giv_count * sizeof *stats);
+ = (struct induction **) xmalloc (giv_count * sizeof (struct induction *));
+ stats = (struct recombine_givs_stats *) xmalloc (giv_count * sizeof *stats);
/* Initialize stats and set up the ix field for each giv in stats to name
the corresponding index into stats. */
i++;
}
- qsort (stats, giv_count, sizeof(*stats), cmp_recombine_givs_stats);
+ qsort (stats, giv_count, sizeof (*stats), cmp_recombine_givs_stats);
/* Set up the ix field for each giv in stats to name
the corresponding index into stats, and
/* Loop unrolling of an inner loop can even create new DEST_REG
givs. */
rtx p;
- for (p = v->insn; INSN_UID (p) >= max_uid_for_loop; )
+ for (p = v->insn; INSN_UID (p) >= max_uid_for_loop;)
p = PREV_INSN (p);
stats[i].start_luid = stats[i].end_luid = INSN_LUID (p);
if (p != v->insn)
{
p = prev_nonnote_insn (p);
if (reg_set_p (v->dest_reg, p))
- count--;
+ count--;
}
stats[i].start_luid = INSN_LUID (p);
else
{
stats[i].end_luid = uid_luid[REGNO_LAST_UID (regno)];
- if (stats[i].end_luid > INSN_LUID (loop_end))
+ if (stats[i].end_luid > INSN_LUID (loop->end))
{
stats[i].end_luid = -1;
ends_need_computing++;
if (ends_need_computing)
{
rtx biv = bl->biv->src_reg;
- rtx p = loop_end;
+ rtx p = loop->end;
do
{
- if (p == loop_start)
- p = loop_end;
+ if (p == loop->start)
+ p = loop->end;
p = PREV_INSN (p);
- if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
+ if (! INSN_P (p))
continue;
ends_need_computing -= find_life_end (PATTERN (p), stats, p, biv);
}
}
}
- qsort (stats, giv_count, sizeof(*stats), cmp_recombine_givs_stats);
+ qsort (stats, giv_count, sizeof (*stats), cmp_recombine_givs_stats);
/* Try to derive DEST_REG givs from previous DEST_REG givs with the
same mult_val and non-overlapping lifetime. This reduces register
LAST_GIV. */
for (i = giv_count - 1; i >= 0; i = rescan)
{
- int life_start, life_end;
+ int life_start = 0, life_end = 0;
for (last_giv = 0, rescan = -1; i >= 0; i--)
{
derived giv would defeat the purpose of reducing register
pressure.
??? We could arrange to move the insn. */
- && ((unsigned) stats[i].end_luid - INSN_LUID (loop_start)
- > (unsigned) stats[i].start_luid - INSN_LUID (loop_start))
+ && ((unsigned) stats[i].end_luid - INSN_LUID (loop->start)
+ > (unsigned) stats[i].start_luid - INSN_LUID (loop->start))
&& rtx_equal_p (last_giv->mult_val, v->mult_val)
/* ??? Could handle libcalls, but would need more logic. */
&& ! find_reg_note (v->insn, REG_RETVAL, NULL_RTX)
rescan = i;
}
}
+
+ /* Clean up. */
+ free (giv_array);
+ free (stats);
}
\f
/* EMIT code before INSERT_BEFORE to set REG = B * M + A. */
emit_insn_before (seq, insert_before);
- /* It is entirely possible that the expansion created lots of new
- registers. Iterate over the sequence we just created and
+ /* It is entirely possible that the expansion created lots of new
+ registers. Iterate over the sequence we just created and
record them all. */
if (GET_CODE (seq) == SEQUENCE)
final_[bg]iv_value. */
static int
-check_dbra_loop (loop_end, insn_count, loop_start, loop_info)
- rtx loop_end;
+check_dbra_loop (loop, insn_count)
+ struct loop *loop;
int insn_count;
- rtx loop_start;
- struct loop_info *loop_info;
{
struct iv_class *bl;
rtx reg;
rtx jump;
rtx first_compare;
int compare_and_branch;
+ rtx loop_start = loop->start;
+ rtx loop_end = loop->end;
+ struct loop_info *loop_info = LOOP_INFO (loop);
/* If last insn is a conditional branch, and the insn before tests a
register value, try to optimize it. Otherwise, we can't do anything. */
jump = PREV_INSN (loop_end);
- comparison = get_condition_for_loop (jump);
+ comparison = get_condition_for_loop (loop, jump);
if (comparison == 0)
return 0;
+ if (!onlyjump_p (jump))
+ return 0;
/* Try to compute whether the compare/branch at the loop end is one or
two instructions. */
else
return 0;
+ {
+ /* If more than one condition is present to control the loop, then
+ do not proceed, as this function does not know how to rewrite
+ loop tests with more than one condition.
+
+ Look backwards from the first insn in the last comparison
+ sequence and see if we've got another comparison sequence. */
+
+ rtx jump1;
+ if ((jump1 = prev_nonnote_insn (first_compare)) != loop->cont)
+ if (GET_CODE (jump1) == JUMP_INSN)
+ return 0;
+ }
+
/* Check all of the bivs to see if the compare uses one of them.
Skip biv's set more than once because we can't guarantee that
it will be zero on the last iteration. Also skip if the biv is
for (bl = loop_iv_list; bl; bl = bl->next)
{
if (bl->biv_count == 1
+ && ! bl->biv->maybe_multiple
&& bl->biv->dest_reg == XEXP (comparison, 0)
&& ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
first_compare))
% (-INTVAL (bl->biv->add_val))) == 0)
{
/* register always nonnegative, add REG_NOTE to branch */
- REG_NOTES (PREV_INSN (loop_end))
- = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX,
- REG_NOTES (PREV_INSN (loop_end)));
+ if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
+ REG_NOTES (jump)
+ = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
+ REG_NOTES (jump));
bl->nonneg = 1;
return 1;
if (GET_CODE (p) != JUMP_INSN)
continue;
- before_comparison = get_condition_for_loop (p);
+ before_comparison = get_condition_for_loop (loop, p);
if (before_comparison
&& XEXP (before_comparison, 0) == bl->biv->dest_reg
&& GET_CODE (before_comparison) == LT
&& ! reg_set_between_p (bl->biv->dest_reg, p, loop_start)
&& INTVAL (bl->biv->add_val) == -1)
{
- REG_NOTES (PREV_INSN (loop_end))
- = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX,
- REG_NOTES (PREV_INSN (loop_end)));
+ if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
+ REG_NOTES (jump)
+ = gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
+ REG_NOTES (jump));
bl->nonneg = 1;
return 1;
which is reversible. */
int reversible_mem_store = 1;
- if (bl->giv_count == 0
- && ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
+ if (bl->giv_count == 0 && ! loop->exit_count)
{
rtx bivreg = regno_reg_rtx[bl->regno];
see if perhaps there are no uses except to count. */
no_use_except_counting = 1;
for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
- if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
+ if (INSN_P (p))
{
rtx set = single_set (p);
&& REGNO (SET_DEST (set)) == bl->regno)
/* An insn that sets the biv is okay. */
;
- else if (p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
- || p == prev_nonnote_insn (loop_end))
- /* Don't bother about the end test. */
- ;
+ else if ((p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
+ || p == prev_nonnote_insn (loop_end))
+ && reg_mentioned_p (bivreg, PATTERN (p)))
+ {
+ /* If either of these insns uses the biv and sets a pseudo
+ that has more than one usage, then the biv has uses
+ other than counting since it's used to derive a value
+ that is used more than one time. */
+ int note_set_pseudo_multiple_uses_retval = 0;
+ note_stores (PATTERN (p), note_set_pseudo_multiple_uses,
+ ¬e_set_pseudo_multiple_uses_retval);
+ if (note_set_pseudo_multiple_uses_retval)
+ {
+ no_use_except_counting = 0;
+ break;
+ }
+ }
else if (reg_mentioned_p (bivreg, PATTERN (p)))
{
no_use_except_counting = 0;
}
if (no_use_except_counting)
- ; /* no need to worry about MEMs. */
+ /* No need to worry about MEMs. */
+ ;
else if (num_mem_sets <= 1)
{
for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
- if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
- num_nonfixed_reads += count_nonfixed_reads (PATTERN (p));
+ if (INSN_P (p))
+ num_nonfixed_reads += count_nonfixed_reads (loop, PATTERN (p));
/* If the loop has a single store, and the destination address is
invariant, then we can't reverse the loop, because this address
reversible_mem_store
= (! unknown_address_altered
- && ! invariant_p (XEXP (XEXP (loop_store_mems, 0), 0)));
+ && ! unknown_constant_address_altered
+ && ! loop_invariant_p (loop,
+ XEXP (XEXP (loop_store_mems, 0),
+ 0)));
/* If the store depends on a register that is set after the
store, it depends on the initial value, and is thus not
{
if (v->giv_type == DEST_REG
&& reg_mentioned_p (v->dest_reg,
- XEXP (loop_store_mems, 0))
+ PATTERN (first_loop_store_insn))
&& loop_insn_first_p (first_loop_store_insn, v->insn))
reversible_mem_store = 0;
}
/* Now check other conditions:
The increment must be a constant, as must the initial value,
- and the comparison code must be LT.
+ and the comparison code must be LT.
This test can probably be improved since +/- 1 in the constant
can be obtained by changing LT to LE and vice versa; this is
|| (GET_CODE (comparison) == LE
&& no_use_except_counting)))
{
- HOST_WIDE_INT add_val, add_adjust, comparison_val;
+ HOST_WIDE_INT add_val, add_adjust, comparison_val = 0;
rtx initial_value, comparison_value;
int nonneg = 0;
enum rtx_code cmp_code;
if (comparison_const_width > HOST_BITS_PER_WIDE_INT)
comparison_const_width = HOST_BITS_PER_WIDE_INT;
comparison_sign_mask
- = (unsigned HOST_WIDE_INT)1 << (comparison_const_width - 1);
+ = (unsigned HOST_WIDE_INT) 1 << (comparison_const_width - 1);
/* If the comparison value is not a loop invariant, then we
can not reverse this loop.
??? If the insns which initialize the comparison value as
a whole compute an invariant result, then we could move
them out of the loop and proceed with loop reversal. */
- if (!invariant_p (comparison_value))
+ if (! loop_invariant_p (loop, comparison_value))
return 0;
if (GET_CODE (comparison_value) == CONST_INT)
comparison_val = INTVAL (comparison_value);
initial_value = bl->initial_value;
-
- /* Normalize the initial value if it is an integer and
+
+ /* Normalize the initial value if it is an integer and
has no other use except as a counter. This will allow
a few more loops to be reversed. */
if (no_use_except_counting
calculate a giv or has a non-counting use. */
#if ! defined (HAVE_decrement_and_branch_until_zero) \
&& defined (HAVE_decrement_and_branch_on_count)
- && (! (add_val == 1 && loop_info->vtop
+ && (! (add_val == 1 && loop->vtop
&& (bl->biv_count == 0
|| no_use_except_counting)))
#endif
nonneg = 1;
cmp_code = GE;
}
- else if (add_val == 1 && loop_info->vtop
+ else if (add_val == 1 && loop->vtop
&& (bl->biv_count == 0
|| no_use_except_counting))
{
create a sequence to hold all the insns from expand_inc. */
start_sequence ();
expand_inc (reg, new_add_val);
- tem = gen_sequence ();
- end_sequence ();
+ tem = gen_sequence ();
+ end_sequence ();
p = emit_insn_before (tem, bl->biv->insn);
delete_insn (bl->biv->insn);
-
+
/* Update biv info to reflect its new status. */
bl->biv->insn = p;
bl->initial_value = start_value;
/* 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, 0,
XEXP (jump_label, 0));
tem = gen_sequence ();
end_sequence ();
/* Increment of LABEL_NUSES done above. */
/* Register is now always nonnegative,
so add REG_NONNEG note to the branch. */
- REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX,
+ REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, reg,
REG_NOTES (tem));
}
bl->nonneg = 1;
remove all REG_EQUAL notes based on the reversed biv
here. */
for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
- if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
+ if (INSN_P (p))
{
rtx *pnote;
rtx set = single_set (p);
\f
/* Verify whether the biv BL appears to be eliminable,
based on the insns in the loop that refer to it.
- LOOP_START is the first insn of the loop, and END is the end insn.
If ELIMINATE_P is non-zero, actually do the elimination.
start of the loop. */
static int
-maybe_eliminate_biv (bl, loop_start, end, eliminate_p, threshold, insn_count)
+maybe_eliminate_biv (loop, bl, eliminate_p, threshold, insn_count)
+ const struct loop *loop;
struct iv_class *bl;
- rtx loop_start;
- rtx end;
int eliminate_p;
int threshold, insn_count;
{
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 != 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;
if (set && GET_CODE (SET_DEST (set)) == REG)
{
- int regno = REGNO (SET_DEST (set));
+ unsigned int regno = REGNO (SET_DEST (set));
if (regno < max_reg_before_loop
&& REG_IV_TYPE (regno) == GENERAL_INDUCT
}
if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
&& reg_mentioned_p (reg, PATTERN (p))
- && ! maybe_eliminate_biv_1 (PATTERN (p), p, bl, eliminate_p, where))
+ && ! maybe_eliminate_biv_1 (loop, PATTERN (p), p, bl,
+ eliminate_p, where))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
}
}
- if (p == end)
+ if (p == loop_end)
{
if (loop_dump_stream)
fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
{
rtx p, q;
- for (p = insn, q = reference; ;)
+ for (p = insn, q = reference;;)
{
/* Start with test for not first so that INSN == REFERENCE yields not
first. */
the loop. */
static int
-maybe_eliminate_biv_1 (x, insn, bl, eliminate_p, where)
+maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where)
+ const struct loop *loop;
rtx x, insn;
struct iv_class *bl;
int eliminate_p;
overflows. */
for (v = bl->giv; v; v = v->next_iv)
- if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
+ if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
&& v->add_val == const0_rtx
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode
overflow problem. */
for (v = bl->giv; v; v = v->next_iv)
- if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
+ if (GET_CODE (v->mult_val) == CONST_INT
+ && v->mult_val != const0_rtx
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode
&& (GET_CODE (v->add_val) == SYMBOL_REF
where);
/* Substitute the new register for its invariant value in
- the compare expression. */
+ the compare expression. */
XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
return 1;
negative mult_val, but it seems complex to do it in general. */
for (v = bl->giv; v; v = v->next_iv)
- if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
+ if (GET_CODE (v->mult_val) == CONST_INT
+ && INTVAL (v->mult_val) > 0
&& (GET_CODE (v->add_val) == SYMBOL_REF
|| GET_CODE (v->add_val) == LABEL_REF
|| GET_CODE (v->add_val) == CONST
return 1;
/* Replace biv with the giv's reduced reg. */
- XEXP (x, 1-arg_operand) = v->new_reg;
+ validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
/* If all constants are actually constant integers and
the derived constant can be directly placed in the COMPARE,
do so. */
if (GET_CODE (arg) == CONST_INT
&& GET_CODE (v->mult_val) == CONST_INT
- && GET_CODE (v->add_val) == CONST_INT
- && validate_change (insn, &XEXP (x, arg_operand),
- GEN_INT (INTVAL (arg)
- * INTVAL (v->mult_val)
- + INTVAL (v->add_val)), 0))
- return 1;
-
- /* Otherwise, load it into a register. */
- tem = gen_reg_rtx (mode);
- emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
- if (validate_change (insn, &XEXP (x, arg_operand), tem, 0))
+ && GET_CODE (v->add_val) == CONST_INT)
+ {
+ validate_change (insn, &XEXP (x, arg_operand),
+ GEN_INT (INTVAL (arg)
+ * INTVAL (v->mult_val)
+ + INTVAL (v->add_val)), 1);
+ }
+ else
+ {
+ /* Otherwise, load it into a register. */
+ tem = gen_reg_rtx (mode);
+ emit_iv_add_mult (arg, v->mult_val, v->add_val, tem, where);
+ validate_change (insn, &XEXP (x, arg_operand), tem, 1);
+ }
+ if (apply_change_group ())
return 1;
-
- /* If that failed, put back the change we made above. */
- XEXP (x, 1-arg_operand) = reg;
}
-
+
/* Look for giv with positive constant mult_val and nonconst add_val.
- Insert insns to calculate new compare value.
+ Insert insns to calculate new compare value.
??? Turn this off due to possible overflow. */
for (v = bl->giv; v; v = v->next_iv)
- if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
+ if (GET_CODE (v->mult_val) == CONST_INT
+ && INTVAL (v->mult_val) > 0
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode
&& 0)
}
else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
{
- if (invariant_p (arg) == 1)
+ if (loop_invariant_p (loop, arg) == 1)
{
/* Look for giv with constant positive mult_val and nonconst
- add_val. Insert insns to compute new compare value.
+ add_val. Insert insns to compute new compare value.
??? Turn this off due to possible overflow. */
for (v = bl->giv; v; v = v->next_iv)
- if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
+ if (GET_CODE (v->mult_val) == CONST_INT && INTVAL (v->mult_val) > 0
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode
&& 0)
return 1;
/* Replace biv with its giv's reduced reg. */
- XEXP (x, 1-arg_operand) = v->new_reg;
+ XEXP (x, 1 - arg_operand) = v->new_reg;
/* Replace other operand with the other giv's
reduced reg. */
XEXP (x, arg_operand) = tv->new_reg;
switch (fmt[i])
{
case 'e':
- if (! maybe_eliminate_biv_1 (XEXP (x, i), insn, bl,
+ if (! maybe_eliminate_biv_1 (loop, XEXP (x, i), insn, bl,
eliminate_p, where))
return 0;
break;
case 'E':
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
- if (! maybe_eliminate_biv_1 (XVECEXP (x, i, j), insn, bl,
+ if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl,
eliminate_p, where))
return 0;
break;
}
return 1;
-}
+}
\f
/* Return nonzero if the last use of REG
is in an insn following INSN in the same basic block. */
just record the location of the set and process it later. */
static void
-record_initial (dest, set)
+record_initial (dest, set, data)
rtx dest;
rtx set;
+ void *data ATTRIBUTE_UNUSED;
{
struct iv_class *bl;
}
}
\f
-/* Given a jump insn JUMP, return the condition that will cause it to branch
- to its JUMP_LABEL. If the condition cannot be understood, or is an
- inequality floating-point comparison which needs to be reversed, 0 will
- be returned.
+/* Given an insn INSN and condition COND, return the condition in a
+ canonical form to simplify testing by callers. Specifically:
+
+ (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
+ (2) Both operands will be machine operands; (cc0) will have been replaced.
+ (3) If an operand is a constant, it will be the second operand.
+ (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
+ for GE, GEU, and LEU.
+
+ If the condition cannot be understood, or is an inequality floating-point
+ comparison which needs to be reversed, 0 will be returned.
+
+ If REVERSE is non-zero, then reverse the condition prior to canonizing it.
If EARLIEST is non-zero, it is a pointer to a place where the earliest
insn used in locating the condition was found. If a replacement test
of the condition is desired, it should be placed in front of that
insn and we will be sure that the inputs are still valid.
- The condition will be returned in a canonical form to simplify testing by
- callers. Specifically:
-
- (1) The code will always be a comparison operation (EQ, NE, GT, etc.).
- (2) Both operands will be machine operands; (cc0) will have been replaced.
- (3) If an operand is a constant, it will be the second operand.
- (4) (LE x const) will be replaced with (LT x <const+1>) and similarly
- for GE, GEU, and LEU. */
+ If WANT_REG is non-zero, we wish the condition to be relative to that
+ register, if possible. Therefore, do not canonicalize the condition
+ further. */
rtx
-get_condition (jump, earliest)
- rtx jump;
+canonicalize_condition (insn, cond, reverse, earliest, want_reg)
+ rtx insn;
+ rtx cond;
+ int reverse;
rtx *earliest;
+ rtx want_reg;
{
enum rtx_code code;
- rtx prev = jump;
+ rtx prev = insn;
rtx set;
rtx tem;
rtx op0, op1;
int did_reverse_condition = 0;
enum machine_mode mode;
- /* If this is not a standard conditional jump, we can't parse it. */
- if (GET_CODE (jump) != JUMP_INSN
- || ! condjump_p (jump) || simplejump_p (jump))
- return 0;
+ code = GET_CODE (cond);
+ mode = GET_MODE (cond);
+ op0 = XEXP (cond, 0);
+ op1 = XEXP (cond, 1);
- code = GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 0));
- mode = GET_MODE (XEXP (SET_SRC (PATTERN (jump)), 0));
- op0 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 0);
- op1 = XEXP (XEXP (SET_SRC (PATTERN (jump)), 0), 1);
+ if (reverse)
+ {
+ code = reverse_condition (code);
+ did_reverse_condition ^= 1;
+ }
if (earliest)
- *earliest = jump;
-
- /* If this branches to JUMP_LABEL when the condition is false, reverse
- the condition. */
- if (GET_CODE (XEXP (SET_SRC (PATTERN (jump)), 2)) == LABEL_REF
- && XEXP (XEXP (SET_SRC (PATTERN (jump)), 2), 0) == JUMP_LABEL (jump))
- code = reverse_condition (code), did_reverse_condition ^= 1;
+ *earliest = insn;
/* If we are comparing a register with zero, see if the register is set
in the previous insn to a COMPARE or a comparison operation. Perform
the same tests as a function of STORE_FLAG_VALUE as find_comparison_args
in cse.c */
- while (GET_RTX_CLASS (code) == '<' && op1 == CONST0_RTX (GET_MODE (op0)))
+ while (GET_RTX_CLASS (code) == '<'
+ && op1 == CONST0_RTX (GET_MODE (op0))
+ && op0 != want_reg)
{
/* Set non-zero when we find something of interest. */
rtx x = 0;
relevant. */
if (rtx_equal_p (SET_DEST (set), op0))
{
- enum machine_mode inner_mode = GET_MODE (SET_SRC (set));
+ enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
/* ??? We may not combine comparisons done in a CCmode with
comparisons not done in a CCmode. This is to aid targets
#ifdef FLOAT_STORE_FLAG_VALUE
|| (code == LT
&& GET_MODE_CLASS (inner_mode) == MODE_FLOAT
- && FLOAT_STORE_FLAG_VALUE < 0)
+ && (REAL_VALUE_NEGATIVE
+ (FLOAT_STORE_FLAG_VALUE (inner_mode))))
#endif
))
&& GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))
#ifdef FLOAT_STORE_FLAG_VALUE
|| (code == GE
&& GET_MODE_CLASS (inner_mode) == MODE_FLOAT
- && FLOAT_STORE_FLAG_VALUE < 0)
+ && (REAL_VALUE_NEGATIVE
+ (FLOAT_STORE_FLAG_VALUE (inner_mode))))
#endif
))
&& GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'
- && (((GET_MODE_CLASS (mode) == MODE_CC)
+ && (((GET_MODE_CLASS (mode) == MODE_CC)
== (GET_MODE_CLASS (inner_mode) == MODE_CC))
|| mode == VOIDmode || inner_mode == VOIDmode))
if (reverse_code)
{
code = reverse_condition (code);
+ 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 (const_val + 1);
break;
/* When cross-compiling, const_val might be sign-extended from
}
/* If this was floating-point and we reversed anything other than an
- EQ or NE, return zero. */
+ EQ or NE or (UN)ORDERED, return zero. */
if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
- && did_reverse_condition && code != NE && code != EQ
+ && did_reverse_condition
+ && code != NE && code != EQ && code != UNORDERED && code != ORDERED
&& ! flag_fast_math
&& GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
return 0;
return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
}
-/* Similar to above routine, except that we also put an invariant last
- unless both operands are invariants. */
-
-rtx
-get_condition_for_loop (x)
- rtx x;
-{
- rtx comparison = get_condition (x, NULL_PTR);
-
- if (comparison == 0
- || ! invariant_p (XEXP (comparison, 0))
- || invariant_p (XEXP (comparison, 1)))
- return comparison;
-
- return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
- XEXP (comparison, 1), XEXP (comparison, 0));
-}
+/* Given a jump insn JUMP, return the condition that will cause it to branch
+ to its JUMP_LABEL. If the condition cannot be understood, or is an
+ inequality floating-point comparison which needs to be reversed, 0 will
+ be returned.
-#ifdef HAVE_decrement_and_branch_on_count
-/* Instrument loop for insertion of bct instruction. We distinguish between
- loops with compile-time bounds and those with run-time bounds.
- Information from loop_iterations() is used to compute compile-time bounds.
- Run-time bounds should use loop preconditioning, but currently ignored.
- */
+ If EARLIEST is non-zero, it is a pointer to a place where the earliest
+ insn used in locating the condition was found. If a replacement test
+ of the condition is desired, it should be placed in front of that
+ insn and we will be sure that the inputs are still valid. */
-static void
-insert_bct (loop_start, loop_end, loop_info)
- rtx loop_start, loop_end;
- struct loop_info *loop_info;
+rtx
+get_condition (jump, earliest)
+ rtx jump;
+ rtx *earliest;
{
- int i;
- unsigned HOST_WIDE_INT n_iterations;
-
- int increment_direction, compare_direction;
-
- /* If the loop condition is <= or >=, the number of iteration
- is 1 more than the range of the bounds of the loop. */
- int add_iteration = 0;
-
- enum machine_mode loop_var_mode = word_mode;
-
- int loop_num = uid_loop_num [INSN_UID (loop_start)];
-
- /* It's impossible to instrument a competely unrolled loop. */
- if (loop_info->unroll_number == loop_info->n_iterations)
- return;
-
- /* Make sure that the count register is not in use. */
- if (loop_used_count_register [loop_num])
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "insert_bct %d: BCT instrumentation failed: count register already in use\n",
- loop_num);
- return;
- }
-
- /* Make sure that the function has no indirect jumps. */
- if (indirect_jump_in_function)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "insert_bct %d: BCT instrumentation failed: indirect jump in function\n",
- loop_num);
- return;
- }
-
- /* Make sure that the last loop insn is a conditional jump. */
- if (GET_CODE (PREV_INSN (loop_end)) != JUMP_INSN
- || ! condjump_p (PREV_INSN (loop_end))
- || simplejump_p (PREV_INSN (loop_end)))
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "insert_bct %d: BCT instrumentation failed: invalid jump at loop end\n",
- loop_num);
- return;
- }
-
- /* Make sure that the loop does not contain a function call
- (the count register might be altered by the called function). */
- if (loop_info->has_call)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "insert_bct %d: BCT instrumentation failed: function call in loop\n",
- loop_num);
- return;
- }
-
- /* Make sure that the loop does not jump via a table.
- (the count register might be used to perform the branch on table). */
- if (loop_info->has_tablejump)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "insert_bct %d: BCT instrumentation failed: computed branch in the loop\n",
- loop_num);
- return;
- }
-
- /* Account for loop unrolling in instrumented iteration count. */
- if (loop_info->unroll_number > 1)
- n_iterations = loop_info->n_iterations / loop_info->unroll_number;
- else
- n_iterations = loop_info->n_iterations;
-
- if (n_iterations != 0 && n_iterations < 3)
- {
- /* Allow an enclosing outer loop to benefit if possible. */
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "insert_bct %d: Too few iterations to benefit from BCT optimization\n",
- loop_num);
- return;
- }
-
- /* Try to instrument the loop. */
-
- /* Handle the simpler case, where the bounds are known at compile time. */
- if (n_iterations > 0)
- {
- /* Mark all enclosing loops that they cannot use count register. */
- for (i = loop_num; i != -1; i = loop_outer_loop[i])
- loop_used_count_register[i] = 1;
- instrument_loop_bct (loop_start, loop_end, GEN_INT (n_iterations));
- return;
- }
-
- /* Handle the more complex case, that the bounds are NOT known
- at compile time. In this case we generate run_time calculation
- of the number of iterations. */
-
- if (loop_info->iteration_var == 0)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "insert_bct %d: BCT Runtime Instrumentation failed: no loop iteration variable found\n",
- loop_num);
- return;
- }
-
- if (GET_MODE_CLASS (GET_MODE (loop_info->iteration_var)) != MODE_INT
- || GET_MODE_SIZE (GET_MODE (loop_info->iteration_var)) != UNITS_PER_WORD)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "insert_bct %d: BCT Runtime Instrumentation failed: loop variable not integer\n",
- loop_num);
- return;
- }
-
- /* With runtime bounds, if the compare is of the form '!=' we give up */
- if (loop_info->comparison_code == NE)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "insert_bct %d: BCT Runtime Instrumentation failed: runtime bounds with != comparison\n",
- loop_num);
- return;
- }
-/* Use common loop preconditioning code instead. */
-#if 0
- else
- {
- /* We rely on the existence of run-time guard to ensure that the
- loop executes at least once. */
- rtx sequence;
- rtx iterations_num_reg;
-
- unsigned HOST_WIDE_INT increment_value_abs
- = INTVAL (increment) * increment_direction;
+ rtx cond;
+ int reverse;
+ rtx set;
- /* make sure that the increment is a power of two, otherwise (an
- expensive) divide is needed. */
- if (exact_log2 (increment_value_abs) == -1)
- {
- if (loop_dump_stream)
- fprintf (loop_dump_stream,
- "insert_bct: not instrumenting BCT because the increment is not power of 2\n");
- return;
- }
+ /* If this is not a standard conditional jump, we can't parse it. */
+ if (GET_CODE (jump) != JUMP_INSN
+ || ! any_condjump_p (jump))
+ return 0;
+ set = pc_set (jump);
- /* compute the number of iterations */
- start_sequence ();
- {
- rtx temp_reg;
-
- /* Again, the number of iterations is calculated by:
- ;
- ; compare-val - initial-val + (increment -1) + additional-iteration
- ; num_iterations = -----------------------------------------------------------------
- ; increment
- */
- /* ??? Do we have to call copy_rtx here before passing rtx to
- expand_binop? */
- if (compare_direction > 0)
- {
- /* <, <= :the loop variable is increasing */
- temp_reg = expand_binop (loop_var_mode, sub_optab,
- comparison_value, initial_value,
- NULL_RTX, 0, OPTAB_LIB_WIDEN);
- }
- else
- {
- temp_reg = expand_binop (loop_var_mode, sub_optab,
- initial_value, comparison_value,
- NULL_RTX, 0, OPTAB_LIB_WIDEN);
- }
+ cond = XEXP (SET_SRC (set), 0);
- if (increment_value_abs - 1 + add_iteration != 0)
- temp_reg = expand_binop (loop_var_mode, add_optab, temp_reg,
- GEN_INT (increment_value_abs - 1
- + add_iteration),
- NULL_RTX, 0, OPTAB_LIB_WIDEN);
-
- if (increment_value_abs != 1)
- iterations_num_reg = expand_binop (loop_var_mode, asr_optab,
- temp_reg,
- GEN_INT (exact_log2 (increment_value_abs)),
- NULL_RTX, 0, OPTAB_LIB_WIDEN);
- else
- iterations_num_reg = temp_reg;
- }
- sequence = gen_sequence ();
- end_sequence ();
- emit_insn_before (sequence, loop_start);
- instrument_loop_bct (loop_start, loop_end, iterations_num_reg);
- }
+ /* If this branches to JUMP_LABEL when the condition is false, reverse
+ the condition. */
+ reverse
+ = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
+ && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
- return;
-#endif /* Complex case */
+ return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
}
-/* Instrument loop by inserting a bct in it as follows:
- 1. A new counter register is created.
- 2. In the head of the loop the new variable is initialized to the value
- passed in the loop_num_iterations parameter.
- 3. At the end of the loop, comparison of the register with 0 is generated.
- The created comparison follows the pattern defined for the
- decrement_and_branch_on_count insn, so this insn will be generated.
- 4. The branch on the old variable are deleted. The compare must remain
- because it might be used elsewhere. If the loop-variable or condition
- register are used elsewhere, they will be eliminated by flow. */
+/* Similar to above routine, except that we also put an invariant last
+ unless both operands are invariants. */
-static void
-instrument_loop_bct (loop_start, loop_end, loop_num_iterations)
- rtx loop_start, loop_end;
- rtx loop_num_iterations;
+rtx
+get_condition_for_loop (loop, x)
+ const struct loop *loop;
+ rtx x;
{
- rtx counter_reg;
- rtx start_label;
- rtx sequence;
-
- if (HAVE_decrement_and_branch_on_count)
- {
- if (loop_dump_stream)
- {
- fputs ("instrument_bct: Inserting BCT (", loop_dump_stream);
- if (GET_CODE (loop_num_iterations) == CONST_INT)
- fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
- INTVAL (loop_num_iterations));
- else
- fputs ("runtime", loop_dump_stream);
- fputs (" iterations)", loop_dump_stream);
- }
+ rtx comparison = get_condition (x, NULL_PTR);
- /* Discard original jump to continue loop. Original compare result
- may still be live, so it cannot be discarded explicitly. */
- delete_insn (PREV_INSN (loop_end));
-
- /* Insert the label which will delimit the start of the loop. */
- start_label = gen_label_rtx ();
- emit_label_after (start_label, loop_start);
-
- /* Insert initialization of the count register into the loop header. */
- start_sequence ();
- counter_reg = gen_reg_rtx (word_mode);
- emit_insn (gen_move_insn (counter_reg, loop_num_iterations));
- sequence = gen_sequence ();
- end_sequence ();
- emit_insn_before (sequence, loop_start);
-
- /* Insert new comparison on the count register instead of the
- old one, generating the needed BCT pattern (that will be
- later recognized by assembly generation phase). */
- emit_jump_insn_before (gen_decrement_and_branch_on_count (counter_reg,
- start_label),
- loop_end);
- LABEL_NUSES (start_label)++;
- }
+ if (comparison == 0
+ || ! loop_invariant_p (loop, XEXP (comparison, 0))
+ || loop_invariant_p (loop, XEXP (comparison, 1)))
+ return comparison;
+ return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
+ XEXP (comparison, 1), XEXP (comparison, 0));
}
-#endif /* HAVE_decrement_and_branch_on_count */
/* Scan the function and determine whether it has indirect (computed) jumps.
case MEM:
break;
+ case CLOBBER:
+ /* We're not interested in MEMs that are only clobbered. */
+ return -1;
+
case CONST_DOUBLE:
/* We're not interested in the MEM associated with a
CONST_DOUBLE, so there's no need to traverse into this. */
return -1;
+ case EXPR_LIST:
+ /* We're not interested in any MEMs that only appear in notes. */
+ return -1;
+
default:
/* This is not a MEM. */
return 0;
/* See if we've already seen this MEM. */
for (i = 0; i < loop_mems_idx; ++i)
- if (rtx_equal_p (m, loop_mems[i].mem))
+ if (rtx_equal_p (m, loop_mems[i].mem))
{
if (GET_MODE (m) != GET_MODE (loop_mems[i].mem))
/* The modes of the two memory accesses are different. If
}
/* Resize the array, if necessary. */
- if (loop_mems_idx == loop_mems_allocated)
+ if (loop_mems_idx == loop_mems_allocated)
{
if (loop_mems_allocated != 0)
loop_mems_allocated *= 2;
else
loop_mems_allocated = 32;
- loop_mems = (loop_mem_info*)
+ loop_mems = (loop_mem_info*)
xrealloc (loop_mems,
- loop_mems_allocated * sizeof (loop_mem_info));
+ loop_mems_allocated * sizeof (loop_mem_info));
}
/* Actually insert the MEM. */
values after load_mems. */
static void
-load_mems_and_recount_loop_regs_set (scan_start, end, loop_top, start,
- insn_count)
- rtx scan_start;
- rtx end;
- rtx loop_top;
- rtx start;
+load_mems_and_recount_loop_regs_set (loop, insn_count)
+ const struct loop *loop;
int *insn_count;
{
int nregs = max_reg_num ();
- load_mems (scan_start, end, loop_top, start);
-
+ load_mems (loop);
+
/* Recalculate set_in_loop and friends since load_mems may have
created new registers. */
if (max_reg_num () > nregs)
bzero ((char *) &may_not_optimize->data, nregs * sizeof (char));
bzero ((char *) ®_single_usage->data, nregs * sizeof (rtx));
- count_loop_regs_set (loop_top ? loop_top : start, end,
+ count_loop_regs_set (loop->top ? loop->top : loop->start, loop->end,
may_not_optimize, reg_single_usage,
- insn_count, nregs);
+ insn_count, nregs);
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
{
VARRAY_CHAR (may_not_optimize, i) = 1;
VARRAY_INT (set_in_loop, i) = 1;
}
-
+
#ifdef AVOID_CCMODE_COPIES
/* Don't try to move insns which set CC registers if we should not
create CCmode register copies. */
}
}
-/* Move MEMs into registers for the duration of the loop. SCAN_START
- is the first instruction in the loop (as it is executed). The
- other parameters are as for next_insn_in_loop. */
+/* Move MEMs into registers for the duration of the loop. */
static void
-load_mems (scan_start, end, loop_top, start)
- rtx scan_start;
- rtx end;
- rtx loop_top;
- rtx start;
+load_mems (loop)
+ const struct loop *loop;
{
int maybe_never = 0;
int i;
rtx p;
rtx label = NULL_RTX;
rtx end_label = NULL_RTX;
+ /* Nonzero if the next instruction may never be executed. */
+ int next_maybe_never = 0;
+ int last_max_reg = max_reg_num ();
+
+ if (loop_mems_idx == 0)
+ return;
+
+ /* Find start of the extended basic block that enters the loop. */
+ for (p = loop->start;
+ PREV_INSN (p) && GET_CODE (p) != CODE_LABEL;
+ p = PREV_INSN (p))
+ ;
+
+ cselib_init ();
+
+ /* Build table of mems that get set to constant values before the
+ loop. */
+ for (; p != loop->start; p = NEXT_INSN (p))
+ cselib_process_insn (p);
- if (loop_mems_idx > 0)
+ /* Check to see if it's possible that some instructions in the
+ loop are never executed. */
+ for (p = next_insn_in_loop (loop, loop->scan_start);
+ p != NULL_RTX && ! maybe_never;
+ p = next_insn_in_loop (loop, p))
{
- /* Nonzero if the next instruction may never be executed. */
- int next_maybe_never = 0;
-
- /* Check to see if it's possible that some instructions in the
- loop are never executed. */
- for (p = next_insn_in_loop (scan_start, scan_start, end, loop_top);
- p != NULL_RTX && !maybe_never;
- p = next_insn_in_loop (p, scan_start, end, loop_top))
+ if (GET_CODE (p) == CODE_LABEL)
+ maybe_never = 1;
+ else if (GET_CODE (p) == JUMP_INSN
+ /* If we enter the loop in the middle, and scan
+ around to the beginning, don't set maybe_never
+ for that. This must be an 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. */
+ && ! (GET_CODE (p) == JUMP_INSN
+ && JUMP_LABEL (p) == loop->top
+ && NEXT_INSN (NEXT_INSN (p)) == loop->end
+ && any_uncondjump_p (p)))
{
- if (GET_CODE (p) == CODE_LABEL)
+ if (!any_condjump_p (p))
+ /* Something complicated. */
maybe_never = 1;
- else if (GET_CODE (p) == JUMP_INSN
- /* If we enter the loop in the middle, and scan
- around to the beginning, don't set maybe_never
- for that. This must be an 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. */
- && ! (GET_CODE (p) == JUMP_INSN
- && JUMP_LABEL (p) == loop_top
- && NEXT_INSN (NEXT_INSN (p)) == end
- && simplejump_p (p)))
+ else
+ /* If there are any more instructions in the loop, they
+ might not be reached. */
+ next_maybe_never = 1;
+ }
+ else if (next_maybe_never)
+ maybe_never = 1;
+ }
+
+ /* Actually move the MEMs. */
+ for (i = 0; i < loop_mems_idx; ++i)
+ {
+ regset_head load_copies;
+ regset_head store_copies;
+ int written = 0;
+ rtx reg;
+ rtx mem = loop_mems[i].mem;
+ rtx mem_list_entry;
+
+ if (MEM_VOLATILE_P (mem)
+ || loop_invariant_p (loop, XEXP (mem, 0)) != 1)
+ /* There's no telling whether or not MEM is modified. */
+ loop_mems[i].optimize = 0;
+
+ /* Go through the MEMs written to in the loop to see if this
+ one is aliased by one of them. */
+ mem_list_entry = loop_store_mems;
+ while (mem_list_entry)
+ {
+ if (rtx_equal_p (mem, XEXP (mem_list_entry, 0)))
+ written = 1;
+ else if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
+ mem, rtx_varies_p))
{
- if (!condjump_p (p))
- /* Something complicated. */
- maybe_never = 1;
- else
- /* If there are any more instructions in the loop, they
- might not be reached. */
- next_maybe_never = 1;
- }
- else if (next_maybe_never)
- maybe_never = 1;
+ /* MEM is indeed aliased by this store. */
+ loop_mems[i].optimize = 0;
+ break;
+ }
+ mem_list_entry = XEXP (mem_list_entry, 1);
}
- /* Actually move the MEMs. */
- for (i = 0; i < loop_mems_idx; ++i)
+ if (flag_float_store && written
+ && GET_MODE_CLASS (GET_MODE (mem)) == MODE_FLOAT)
+ loop_mems[i].optimize = 0;
+
+ /* If this MEM is written to, we must be sure that there
+ are no reads from another MEM that aliases this one. */
+ if (loop_mems[i].optimize && written)
{
- int written = 0;
- rtx reg;
- rtx mem = loop_mems[i].mem;
- rtx mem_list_entry;
-
- if (MEM_VOLATILE_P (mem)
- || invariant_p (XEXP (mem, 0)) != 1)
- /* There's no telling whether or not MEM is modified. */
- loop_mems[i].optimize = 0;
-
- /* Go through the MEMs written to in the loop to see if this
- one is aliased by one of them. */
- mem_list_entry = loop_store_mems;
- while (mem_list_entry)
+ int j;
+
+ for (j = 0; j < loop_mems_idx; ++j)
{
- if (rtx_equal_p (mem, XEXP (mem_list_entry, 0)))
- written = 1;
- else if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
- mem, rtx_varies_p))
+ if (j == i)
+ continue;
+ else if (true_dependence (mem,
+ VOIDmode,
+ loop_mems[j].mem,
+ rtx_varies_p))
{
- /* MEM is indeed aliased by this store. */
+ /* It's not safe to hoist loop_mems[i] out of
+ the loop because writes to it might not be
+ seen by reads from loop_mems[j]. */
loop_mems[i].optimize = 0;
break;
}
- mem_list_entry = XEXP (mem_list_entry, 1);
}
-
- /* If this MEM is written to, we must be sure that there
- are no reads from another MEM that aliases this one. */
- if (loop_mems[i].optimize && written)
- {
- int j;
+ }
- for (j = 0; j < loop_mems_idx; ++j)
- {
- if (j == i)
- continue;
- else if (true_dependence (mem,
- VOIDmode,
- loop_mems[j].mem,
- rtx_varies_p))
- {
- /* It's not safe to hoist loop_mems[i] out of
- the loop because writes to it might not be
- seen by reads from loop_mems[j]. */
- loop_mems[i].optimize = 0;
- break;
- }
- }
- }
+ if (maybe_never && may_trap_p (mem))
+ /* We can't access the MEM outside the loop; it might
+ cause a trap that wouldn't have happened otherwise. */
+ loop_mems[i].optimize = 0;
- if (maybe_never && may_trap_p (mem))
- /* We can't access the MEM outside the loop; it might
- cause a trap that wouldn't have happened otherwise. */
- loop_mems[i].optimize = 0;
-
- if (!loop_mems[i].optimize)
- /* We thought we were going to lift this MEM out of the
- loop, but later discovered that we could not. */
- continue;
+ if (!loop_mems[i].optimize)
+ /* We thought we were going to lift this MEM out of the
+ loop, but later discovered that we could not. */
+ continue;
+
+ INIT_REG_SET (&load_copies);
+ INIT_REG_SET (&store_copies);
+
+ /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
+ order to keep scan_loop from moving stores to this MEM
+ out of the loop just because this REG is neither a
+ user-variable nor used in the loop test. */
+ reg = gen_reg_rtx (GET_MODE (mem));
+ REG_USERVAR_P (reg) = 1;
+ loop_mems[i].reg = reg;
+
+ /* Now, replace all references to the MEM with the
+ corresponding pesudos. */
+ maybe_never = 0;
+ for (p = next_insn_in_loop (loop, loop->scan_start);
+ p != NULL_RTX;
+ p = next_insn_in_loop (loop, p))
+ {
+ rtx_and_int ri;
- /* Allocate a pseudo for this MEM. We set REG_USERVAR_P in
- order to keep scan_loop from moving stores to this MEM
- out of the loop just because this REG is neither a
- user-variable nor used in the loop test. */
- reg = gen_reg_rtx (GET_MODE (mem));
- REG_USERVAR_P (reg) = 1;
- loop_mems[i].reg = reg;
-
- /* Now, replace all references to the MEM with the
- corresponding pesudos. */
- for (p = next_insn_in_loop (scan_start, scan_start, end, loop_top);
- p != NULL_RTX;
- p = next_insn_in_loop (p, scan_start, end, loop_top))
+ if (INSN_P (p))
{
- rtx_and_int ri;
+ rtx set;
+
+ set = single_set (p);
+
+ /* See if this copies the mem into a register that isn't
+ modified afterwards. We'll try to do copy propagation
+ a little further on. */
+ if (set
+ /* @@@ This test is _way_ too conservative. */
+ && ! maybe_never
+ && GET_CODE (SET_DEST (set)) == REG
+ && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
+ && REGNO (SET_DEST (set)) < last_max_reg
+ && VARRAY_INT (n_times_set, REGNO (SET_DEST (set))) == 1
+ && rtx_equal_p (SET_SRC (set), mem))
+ SET_REGNO_REG_SET (&load_copies, REGNO (SET_DEST (set)));
+
+ /* See if this copies the mem from a register that isn't
+ modified afterwards. We'll try to remove the
+ redundant copy later on by doing a little register
+ renaming and copy propagation. This will help
+ to untangle things for the BIV detection code. */
+ if (set
+ && ! maybe_never
+ && GET_CODE (SET_SRC (set)) == REG
+ && REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
+ && REGNO (SET_SRC (set)) < last_max_reg
+ && VARRAY_INT (n_times_set, REGNO (SET_SRC (set))) == 1
+ && 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. */
ri.r = p;
ri.i = i;
for_each_rtx (&p, replace_loop_mem, &ri);
}
- if (!apply_change_group ())
- /* We couldn't replace all occurrences of the MEM. */
- loop_mems[i].optimize = 0;
- else
- {
- rtx set;
-
- /* Load the memory immediately before START, which is
- the NOTE_LOOP_BEG. */
- set = gen_move_insn (reg, mem);
- emit_insn_before (set, start);
+ if (GET_CODE (p) == CODE_LABEL
+ || GET_CODE (p) == JUMP_INSN)
+ maybe_never = 1;
+ }
- if (written)
+ if (! apply_change_group ())
+ /* We couldn't replace all occurrences of the MEM. */
+ loop_mems[i].optimize = 0;
+ else
+ {
+ /* Load the memory immediately before LOOP->START, which is
+ the NOTE_LOOP_BEG. */
+ cselib_val *e = cselib_lookup (mem, VOIDmode, 0);
+ rtx set;
+ rtx best = mem;
+ int j;
+ struct elt_loc_list *const_equiv = 0;
+
+ if (e)
+ {
+ struct elt_loc_list *equiv;
+ struct elt_loc_list *best_equiv = 0;
+ for (equiv = e->locs; equiv; equiv = equiv->next)
{
- if (label == NULL_RTX)
- {
- /* We must compute the former
- right-after-the-end label before we insert
- the new one. */
- end_label = next_label (end);
- label = gen_label_rtx ();
- emit_label_after (label, end);
- }
-
- /* 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);
+ if (CONSTANT_P (equiv->loc))
+ const_equiv = equiv;
+ else if (GET_CODE (equiv->loc) == REG
+ /* Extending hard register lifetimes cuases crash
+ on SRC targets. Doing so on non-SRC is
+ probably also not good idea, since we most
+ probably have pseudoregister equivalence as
+ well. */
+ && REGNO (equiv->loc) >= FIRST_PSEUDO_REGISTER)
+ best_equiv = equiv;
+ }
+ /* Use the constant equivalence if that is cheap enough. */
+ if (! best_equiv)
+ best_equiv = const_equiv;
+ else if (const_equiv
+ && (rtx_cost (const_equiv->loc, SET)
+ <= rtx_cost (best_equiv->loc, SET)))
+ {
+ best_equiv = const_equiv;
+ const_equiv = 0;
}
- if (loop_dump_stream)
+ /* If best_equiv is nonzero, we know that MEM is set to a
+ constant or register before the loop. We will use this
+ knowledge to initialize the shadow register with that
+ constant or reg rather than by loading from MEM. */
+ if (best_equiv)
+ best = copy_rtx (best_equiv->loc);
+ }
+ set = gen_move_insn (reg, best);
+ set = emit_insn_before (set, loop->start);
+ if (const_equiv)
+ REG_NOTES (set) = gen_rtx_EXPR_LIST (REG_EQUAL,
+ copy_rtx (const_equiv->loc),
+ REG_NOTES (set));
+
+ if (written)
+ {
+ if (label == NULL_RTX)
{
- fprintf (loop_dump_stream, "Hoisted regno %d %s from ",
- REGNO (reg), (written ? "r/w" : "r/o"));
- print_rtl (loop_dump_stream, mem);
- fputc ('\n', loop_dump_stream);
+ /* We must compute the former
+ right-after-the-end label before we insert
+ the new one. */
+ end_label = next_label (loop->end);
+ label = gen_label_rtx ();
+ emit_label_after (label, loop->end);
}
+
+ /* 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);
}
+
+ if (loop_dump_stream)
+ {
+ fprintf (loop_dump_stream, "Hoisted regno %d %s from ",
+ REGNO (reg), (written ? "r/w" : "r/o"));
+ print_rtl (loop_dump_stream, mem);
+ fputc ('\n', loop_dump_stream);
+ }
+
+ /* Attempt a bit of copy propagation. This helps untangle the
+ data flow, and enables {basic,general}_induction_var to find
+ more bivs/givs. */
+ EXECUTE_IF_SET_IN_REG_SET
+ (&load_copies, FIRST_PSEUDO_REGISTER, j,
+ {
+ try_copy_prop (loop, reg, j);
+ });
+ CLEAR_REG_SET (&load_copies);
+
+ EXECUTE_IF_SET_IN_REG_SET
+ (&store_copies, FIRST_PSEUDO_REGISTER, j,
+ {
+ try_swap_copy_prop (loop, reg, j);
+ });
+ CLEAR_REG_SET (&store_copies);
}
}
{
/* Now, we need to replace all references to the previous exit
label with the new one. */
- rtx_pair rr;
+ rtx_pair rr;
rr.r1 = end_label;
rr.r2 = label;
- for (p = start; p != end; p = NEXT_INSN (p))
+ for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
{
for_each_rtx (&p, replace_label, &rr);
JUMP_LABEL (p) = label;
}
}
+
+ cselib_finish ();
+}
+
+/* For communication between note_reg_stored and its caller. */
+struct note_reg_stored_arg
+{
+ int set_seen;
+ rtx reg;
+};
+
+/* Called via note_stores, record in SET_SEEN whether X, which is written,
+ is equal to ARG. */
+static void
+note_reg_stored (x, setter, arg)
+ rtx x, setter ATTRIBUTE_UNUSED;
+ void *arg;
+{
+ struct note_reg_stored_arg *t = (struct note_reg_stored_arg *) arg;
+ if (t->reg == x)
+ t->set_seen = 1;
+}
+
+/* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
+ There must be exactly one insn that sets this pseudo; it will be
+ deleted if all replacements succeed and we can prove that the register
+ is not used after the loop. */
+
+static void
+try_copy_prop (loop, replacement, regno)
+ const struct loop *loop;
+ rtx replacement;
+ unsigned int regno;
+{
+ /* This is the reg that we are copying from. */
+ rtx reg_rtx = regno_reg_rtx[regno];
+ rtx init_insn = 0;
+ rtx insn;
+ /* These help keep track of whether we replaced all uses of the reg. */
+ int replaced_last = 0;
+ int store_is_first = 0;
+
+ for (insn = next_insn_in_loop (loop, loop->scan_start);
+ insn != NULL_RTX;
+ insn = next_insn_in_loop (loop, insn))
+ {
+ rtx set;
+
+ /* Only substitute within one extended basic block from the initializing
+ insn. */
+ if (GET_CODE (insn) == CODE_LABEL && init_insn)
+ break;
+
+ if (! INSN_P (insn))
+ continue;
+
+ /* Is this the initializing insn? */
+ set = single_set (insn);
+ if (set
+ && GET_CODE (SET_DEST (set)) == REG
+ && REGNO (SET_DEST (set)) == regno)
+ {
+ if (init_insn)
+ abort ();
+
+ init_insn = insn;
+ if (REGNO_FIRST_UID (regno) == INSN_UID (insn))
+ store_is_first = 1;
+ }
+
+ /* Only substitute after seeing the initializing insn. */
+ if (init_insn && insn != init_insn)
+ {
+ struct note_reg_stored_arg arg;
+ rtx array[3];
+ array[0] = reg_rtx;
+ array[1] = replacement;
+ array[2] = insn;
+
+ for_each_rtx (&insn, replace_loop_reg, array);
+ if (REGNO_LAST_UID (regno) == INSN_UID (insn))
+ replaced_last = 1;
+
+ /* Stop replacing when REPLACEMENT is modified. */
+ arg.reg = replacement;
+ arg.set_seen = 0;
+ note_stores (PATTERN (insn), note_reg_stored, &arg);
+ if (arg.set_seen)
+ break;
+ }
+ }
+ if (! init_insn)
+ abort ();
+ if (apply_change_group ())
+ {
+ if (loop_dump_stream)
+ 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));
+ }
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream, ".\n");
+ }
}
+
+/* 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
+ this pseudo followed immediately by a move insn that sets
+ REPLACEMENT with REGNO. */
+static void
+try_swap_copy_prop (loop, replacement, regno)
+ const struct loop *loop;
+ rtx replacement;
+ unsigned int regno;
+{
+ rtx insn;
+ rtx set;
+ unsigned int new_regno;
+
+ new_regno = REGNO (replacement);
+
+ for (insn = next_insn_in_loop (loop, loop->scan_start);
+ insn != NULL_RTX;
+ 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'
+ && (set = single_set (insn))
+ && GET_CODE (SET_DEST (set)) == REG
+ && REGNO (SET_DEST (set)) == new_regno
+ && GET_CODE (SET_SRC (set)) == REG
+ && REGNO (SET_SRC (set)) == regno)
+ break;
+ }
+
+ if (insn != NULL_RTX)
+ {
+ rtx prev_insn;
+ rtx prev_set;
+
+ /* Some DEF-USE info would come in handy here to make this
+ function more general. For now, just check the previous insn
+ which is the most likely candidate for setting REGNO. */
+
+ prev_insn = PREV_INSN (insn);
+
+ if (GET_RTX_CLASS (GET_CODE (insn)) == 'i'
+ && (prev_set = single_set (prev_insn))
+ && GET_CODE (SET_DEST (prev_set)) == REG
+ && REGNO (SET_DEST (prev_set)) == regno)
+ {
+ /* We have:
+ (set (reg regno) (expr))
+ (set (reg new_regno) (reg regno))
+
+ so try converting this to:
+ (set (reg new_regno) (expr))
+ (set (reg regno) (reg new_regno))
+
+ The former construct is often generated when a global
+ variable used for an induction variable is shadowed by a
+ register (NEW_REGNO). The latter construct improves the
+ chances of GIV replacement and BIV elimination. */
+
+ validate_change (prev_insn, &SET_DEST (prev_set),
+ replacement, 1);
+ validate_change (insn, &SET_DEST (set),
+ SET_SRC (set), 1);
+ validate_change (insn, &SET_SRC (set),
+ replacement, 1);
+
+ if (apply_change_group ())
+ {
+ if (loop_dump_stream)
+ fprintf (loop_dump_stream,
+ " Swapped set of reg %d at %d with reg %d at %d.\n",
+ regno, INSN_UID (insn),
+ new_regno, INSN_UID (prev_insn));
+
+ /* Update first use of REGNO. */
+ if (REGNO_FIRST_UID (regno) == INSN_UID (prev_insn))
+ REGNO_FIRST_UID (regno) = INSN_UID (insn);
+
+ /* Now perform copy propagation to hopefully
+ remove all uses of REGNO within the loop. */
+ try_copy_prop (loop, replacement, regno);
+ }
+ }
+ }
+}
+
+
/* Replace MEM with its associated pseudo register. This function is
called from load_mems via for_each_rtx. DATA is actually an
rtx_and_int * describing the instruction currently being scanned
rtx *mem;
void *data;
{
- rtx_and_int *ri;
+ rtx_and_int *ri;
rtx insn;
int i;
rtx m = *mem;
return 0;
}
- ri = (rtx_and_int*) data;
+ ri = (rtx_and_int *) data;
i = ri->i;
if (!rtx_equal_p (loop_mems[i].mem, m))
return 0;
}
+/* Replace one register with another. Called through for_each_rtx; PX points
+ to the rtx being scanned. DATA is actually an array of three rtx's; the
+ first one is the one to be replaced, and the second one the replacement.
+ The third one is the current insn. */
+
+static int
+replace_loop_reg (px, data)
+ rtx *px;
+ void *data;
+{
+ rtx x = *px;
+ rtx *array = (rtx *) data;
+
+ if (x == NULL_RTX)
+ return 0;
+
+ if (x == array[0])
+ validate_change (array[2], px, array[1], 1);
+
+ return 0;
+}
+
/* Replace occurrences of the old exit label for the loop with the new
one. DATA is an rtx_pair containing the old and new labels,
respectively. */
void *data;
{
rtx l = *x;
- rtx old_label = ((rtx_pair*) data)->r1;
- rtx new_label = ((rtx_pair*) data)->r2;
+ rtx old_label = ((rtx_pair *) data)->r1;
+ rtx new_label = ((rtx_pair *) data)->r2;
if (l == NULL_RTX)
return 0;
if (XEXP (l, 0) != old_label)
return 0;
-
+
XEXP (l, 0) = new_label;
++LABEL_NUSES (new_label);
--LABEL_NUSES (old_label);
return 0;
}
-
OSDN Git Service
