Google Git
Sign in
gnu / gcc / 737cee66f221eb8de21f0e41affc4b13cb7c0feb / . / gcc / loop.c
blob: 1c67f1c51597a5d1ce19d9c5eb12964323214a50 [file] [log] [blame]
/* Perform various loop optimizations, including strength reduction.
Copyright (C) 1987, 88, 89, 91-6, 1997 Free Software Foundation, Inc.
This file is part of GNU CC.
GNU CC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
GNU CC is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING. If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA. */
/* 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
general induction variables. Strength reduction is applied to the general
induction variables, and induction variable elimination is applied to
the basic induction variables.
It also finds cases where
a register is set within the loop by zero-extending a narrower value
and changes these to zero the entire register once before the loop
and merely copy the low part within the loop.
Most of the complexity is in heuristics to decide when it is worth
while to do these things. */
#include <stdio.h>
#include "config.h"
#include "rtl.h"
#include "obstack.h"
#include "expr.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 "except.h"
/* Vector mapping INSN_UIDs to luids.
The luids are like uids but increase monotonically always.
We use them to see whether a jump comes from outside a given loop. */
int *uid_luid;
/* Indexed by INSN_UID, contains the ordinal giving the (innermost) loop
number the insn is contained in. */
int *uid_loop_num;
/* 1 + largest uid of any insn. */
int max_uid_for_loop;
/* 1 + luid of last insn. */
static int max_luid;
/* Number of loops detected in current function. Used as index to the
next few tables. */
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;
/* For each loop, gives the containing loop number, -1 if none. */
int *loop_outer_loop;
/* 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;
/* Holds the number of loop iterations. It is zero if the number could not be
calculated. Must be unsigned since the number of iterations can
be as high as 2^wordsize-1. For loops with a wider iterator, this number
will will be zero if the number of loop iterations is too large for an
unsigned integer to hold. */
unsigned HOST_WIDE_INT loop_n_iterations;
/* Nonzero if there is a subroutine call in the current loop.
(unknown_address_altered is also nonzero in this case.) */
static int loop_has_call;
/* Nonzero if there is a volatile memory reference in the current
loop. */
static int loop_has_volatile;
/* Added loop_continue which is the NOTE_INSN_LOOP_CONT of the
current loop. A continue statement will generate a branch to
NEXT_INSN (loop_continue). */
static rtx loop_continue;
/* Indexed by register number, contains the number of times the reg
is set during the loop being scanned.
During code motion, a negative value indicates a reg that has been
made a candidate; in particular -2 means that it is an candidate that
we know is equal to a constant and -1 means that it is an candidate
not known equal to a constant.
After code motion, regs moved have 0 (which is accurate now)
while the failed candidates have the original number of times set.
Therefore, at all times, == 0 indicates an invariant register;
< 0 a conditionally invariant one. */
static int *n_times_set;
/* Original value of n_times_set; same except that this value
is not set negative for a reg whose sets have been made candidates
and not set to 0 for a reg that is moved. */
static int *n_times_used;
/* Index by register number, 1 indicates that the register
cannot be moved or strength reduced. */
static char *may_not_optimize;
/* Nonzero means reg N has already been moved out of one loop.
This reduces the desire to move it out of another. */
static char *moved_once;
/* Array of MEMs that are stored in this loop. If there are too many to fit
here, we just turn on unknown_address_altered. */
#define NUM_STORES 20
static rtx loop_store_mems[NUM_STORES];
/* Index of first available slot in above array. */
static int loop_store_mems_idx;
/* Nonzero if we don't know what MEMs were changed in the current loop.
This happens if the loop contains a call (in which case `loop_has_call'
will also be set) or if we store into more than NUM_STORES MEMs. */
static int unknown_address_altered;
/* Count of movable (i.e. invariant) instructions discovered in the loop. */
static int num_movables;
/* Count of memory write instructions discovered in the loop. */
static int num_mem_sets;
/* Number of loops contained within the current one, including itself. */
static int loops_enclosed;
/* Bound on pseudo register number before loop optimization.
A pseudo has valid regscan info if its number is < max_reg_before_loop. */
int max_reg_before_loop;
/* 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.
If we used the same obstack that it did, we would be deallocating
that array. */
static struct obstack temp_obstack;
/* This is where the pointer to the obstack being used for RTL is stored. */
extern struct obstack *rtl_obstack;
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
extern char *oballoc ();
/* During the analysis of a loop, a chain of `struct movable's
is made to record all the movable insns found.
Then the entire chain can be scanned to decide which to move. */
struct movable
{
rtx insn; /* A movable insn */
rtx set_src; /* The expression this reg is set from. */
rtx set_dest; /* The destination of this SET. */
rtx dependencies; /* When INSN is libcall, this is an EXPR_LIST
of any registers used within the LIBCALL. */
int consec; /* Number of consecutive following insns
that must be moved with this one. */
int regno; /* The register it sets */
short lifetime; /* lifetime of that register;
may be adjusted when matching movables
that load the same value are found. */
short savings; /* Number of insns we can move for this reg,
including other movables that force this
or match this one. */
unsigned int cond : 1; /* 1 if only conditionally movable */
unsigned int force : 1; /* 1 means MUST move this insn */
unsigned int global : 1; /* 1 means reg is live outside this loop */
/* If PARTIAL is 1, GLOBAL means something different:
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. */
unsigned int move_insn : 1; /* 1 means that we call emit_move_insn to
load SRC, rather than copying INSN. */
unsigned int is_equiv : 1; /* 1 means a REG_EQUIV is present on INSN. */
enum machine_mode savemode; /* Nonzero means it is a mode for a low part
that we should avoid changing when clearing
the rest of the reg. */
struct movable *match; /* First entry for same value */
struct movable *forces; /* An insn that must be moved if this is */
struct movable *next;
};
FILE *loop_dump_stream;
/* Forward declarations. */
static void find_and_verify_loops ();
static void mark_loop_jump ();
static void prescan_loop ();
static int reg_in_basic_block_p ();
static int consec_sets_invariant_p ();
static rtx libcall_other_reg ();
static int labels_in_range_p ();
static void count_loop_regs_set ();
static void note_addr_stored ();
static int loop_reg_used_before_p ();
static void scan_loop ();
static void replace_call_address ();
static rtx skip_consec_insns ();
static int libcall_benefit ();
static void ignore_some_movables ();
static void force_movables ();
static void combine_movables ();
static int rtx_equal_for_loop_p ();
static void move_movables ();
static void strength_reduce ();
static int valid_initial_value_p ();
static void find_mem_givs ();
static void record_biv ();
static void check_final_value ();
static void record_giv ();
static void update_giv_derive ();
static int basic_induction_var ();
static rtx simplify_giv_expr ();
static int general_induction_var ();
static int consec_sets_giv ();
static int check_dbra_loop ();
static rtx express_from ();
static int combine_givs_p ();
static void combine_givs ();
static int product_cheap_p ();
static int maybe_eliminate_biv ();
static int maybe_eliminate_biv_1 ();
static int last_use_this_basic_block ();
static void record_initial ();
static void update_reg_last_use ();
/* Relative gain of eliminating various kinds of operations. */
int add_cost;
#if 0
int shift_cost;
int mult_cost;
#endif
/* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to
copy the value of the strength reduced giv to its original register. */
int copy_cost;
void
init_loop ()
{
char *free_point = (char *) oballoc (1);
rtx reg = gen_rtx (REG, word_mode, LAST_VIRTUAL_REGISTER + 1);
add_cost = rtx_cost (gen_rtx (PLUS, word_mode, reg, reg), SET);
/* We multiply by 2 to reconcile the difference in scale between
these two ways of computing costs. Otherwise the cost of a copy
will be far less than the cost of an add. */
copy_cost = 2 * 2;
/* Free the objects we just allocated. */
obfree (free_point);
/* Initialize the obstack used for rtl in product_cheap_p. */
gcc_obstack_init (&temp_obstack);
}
/* Entry point of this file. Perform loop optimization
on the current function. F is the first insn of the function
and DUMPFILE is a stream for output of a trace of actions taken
(or 0 if none should be output). */
void
loop_optimize (f, dumpfile)
/* f is the first instruction of a chain of insns for one function */
rtx f;
FILE *dumpfile;
{
register rtx insn;
register int i;
rtx last_insn;
loop_dump_stream = dumpfile;
init_recog_no_volatile ();
init_alias_analysis ();
max_reg_before_loop = max_reg_num ();
moved_once = (char *) alloca (max_reg_before_loop);
bzero (moved_once, max_reg_before_loop);
regs_may_share = 0;
/* Count the number of loops. */
max_loop_num = 0;
for (insn = f; insn; insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) == NOTE
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
max_loop_num++;
}
/* Don't waste time if no loops. */
if (max_loop_num == 0)
return;
/* 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_outer_loop = (int *) alloca (max_loop_num * sizeof (int));
loop_invalid = (char *) alloca (max_loop_num * sizeof (char));
loop_number_exit_labels = (rtx *) alloca (max_loop_num * sizeof (rtx));
loop_number_exit_count = (int *) alloca (max_loop_num * sizeof (int));
/* Find and process each loop.
First, find them, and record them in order of their beginnings. */
find_and_verify_loops (f);
/* 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);
/* See if we went too far. */
if (get_max_uid () > max_uid_for_loop)
abort ();
/* Compute the mapping from uids to luids.
LUIDs are numbers assigned to insns, like uids,
except that luids increase monotonically through the code.
Don't assign luids to line-number NOTEs, so that the distance in luids
between two insns is not affected by -g. */
for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
{
last_insn = insn;
if (GET_CODE (insn) != NOTE
|| NOTE_LINE_NUMBER (insn) <= 0)
uid_luid[INSN_UID (insn)] = ++i;
else
/* Give a line number note the same luid as preceding insn. */
uid_luid[INSN_UID (insn)] = i;
}
max_luid = i + 1;
/* Don't leave gaps in uid_luid for insns that have been
deleted. It is possible that the first or last insn
using some register has been deleted by cross-jumping.
Make sure that uid_luid for that former insn's uid
points to the general area where that insn used to be. */
for (i = 0; i < max_uid_for_loop; i++)
{
uid_luid[0] = uid_luid[i];
if (uid_luid[0] != 0)
break;
}
for (i = 0; i < max_uid_for_loop; i++)
if (uid_luid[i] == 0)
uid_luid[i] = uid_luid[i - 1];
/* Create a mapping from loops to BLOCK tree nodes. */
if (flag_unroll_loops && write_symbols != NO_DEBUG)
find_loop_tree_blocks ();
/* 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],
max_reg_num ());
/* 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 (flag_unroll_loops && write_symbols != NO_DEBUG)
unroll_block_trees ();
}
/* 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. */
/* ??? Could also move memory writes out of loops if the destination address
is invariant, the source is invariant, the memory write is not volatile,
and if we can prove that no read inside the loop can read this address
before the write occurs. If there is a read of this address after the
write, then we can also mark the memory read as invariant. */
static void
scan_loop (loop_start, end, nregs)
rtx loop_start, end;
int nregs;
{
register int i;
register 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;
/* The SET from an insn, if it is the only SET in the insn. */
rtx set, set1;
/* Chain describing insns movable in current loop. */
struct movable *movables = 0;
/* Last element in `movables' -- so we can add elements at the end. */
struct movable *last_movable = 0;
/* 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. */
int threshold;
/* If we have calls, contains the insn in which a register was used
if it was used exactly once; contains const0_rtx if it was used more
than once. */
rtx *reg_single_usage = 0;
/* Nonzero if we are scanning instructions in a sub-loop. */
int loop_depth = 0;
n_times_set = (int *) alloca (nregs * sizeof (int));
n_times_used = (int *) alloca (nregs * sizeof (int));
may_not_optimize = (char *) alloca (nregs);
/* Determine whether this loop starts with a jump down to a test at
the end. This will occur for a small number of loops with a test
that is too complex to duplicate in front of the loop.
We search for the first insn or label in the loop, skipping NOTEs.
However, we must be careful not to skip past a NOTE_INSN_LOOP_BEG
(because we might have a loop executed only once that contains a
loop which starts with a jump to its exit test) or a NOTE_INSN_LOOP_END
(in case we have a degenerate loop).
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
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'
&& (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;
/* Set up variables describing this loop. */
prescan_loop (loop_start, end);
threshold = (loop_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
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)
&& JUMP_LABEL (p) != 0
/* Check to see whether the jump actually
jumps out of the loop (meaning it's no loop).
This case can happen for things like
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_UID (JUMP_LABEL (p)) < max_uid_for_loop
&& INSN_LUID (JUMP_LABEL (p)) >= INSN_LUID (loop_start)
&& INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (end))
{
loop_top = next_label (scan_start);
scan_start = JUMP_LABEL (p);
}
}
/* If 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.)
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 (loop_dump_stream)
fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
INSN_UID (loop_start), INSN_UID (end));
return;
}
/* Count number of times each reg is set during this loop.
Set may_not_optimize[I] if it is not safe to move out
the setting of register I. If this loop has calls, set
reg_single_usage[I]. */
bzero ((char *) n_times_set, nregs * sizeof (int));
bzero (may_not_optimize, nregs);
if (loop_has_call)
{
reg_single_usage = (rtx *) alloca (nregs * sizeof (rtx));
bzero ((char *) reg_single_usage, nregs * sizeof (rtx));
}
count_loop_regs_set (loop_top ? loop_top : loop_start, end,
may_not_optimize, reg_single_usage, &insn_count, nregs);
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
may_not_optimize[i] = 1, n_times_set[i] = 1;
bcopy ((char *) n_times_set, (char *) n_times_used, 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_continue)
fprintf (loop_dump_stream, "Continue at insn %d.\n",
INSN_UID (loop_continue));
}
/* Scan through the loop finding insns that are safe to move.
Set n_times_set negative for the reg being set, so that
this reg will be considered invariant for subsequent insns.
We consider whether subsequent insns use the reg
in deciding whether it is worth actually moving.
MAYBE_NEVER is nonzero if we have passed a conditional jump insn
and therefore it is possible that the insns we are scanning
would never be executed. At such times, we must make sure
that it is safe to execute the insn once instead of zero times.
When MAYBE_NEVER is 0, all insns will be executed at least once
so that is not a problem. */
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;
}
if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
&& 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))
in_libcall = 0;
if (GET_CODE (p) == INSN
&& (set = single_set (p))
&& GET_CODE (SET_DEST (set)) == REG
&& ! may_not_optimize[REGNO (SET_DEST (set))])
{
int tem1 = 0;
int tem2 = 0;
int move_insn = 0;
rtx src = SET_SRC (set);
rtx dependencies = 0;
/* Figure out what to use as a source of this insn. If a REG_EQUIV
note is given or if a REG_EQUAL note with a constant operand is
specified, use it as the source and mark that we should move
this insn by calling emit_move_insn rather that duplicating the
insn.
Otherwise, only use the REG_EQUAL contents if a REG_RETVAL note
is present. */
temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
if (temp)
src = XEXP (temp, 0), move_insn = 1;
else
{
temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
if (temp && CONSTANT_P (XEXP (temp, 0)))
src = XEXP (temp, 0), move_insn = 1;
if (temp && find_reg_note (p, REG_RETVAL, NULL_RTX))
{
src = XEXP (temp, 0);
/* A libcall block can use regs that don't appear in
the equivalent expression. To move the libcall,
we must move those regs too. */
dependencies = libcall_other_reg (p, src);
}
}
/* Don't try to optimize a register that was made
by loop-optimization for an inner loop.
We don't know its life-span, so we can't compute the benefit. */
if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
;
/* In order to move a register, we need to have one of three cases:
(1) it is used only in the same basic block as the set
(2) it is not a user variable and it is not used in the
exit test (this can cause the variable to be used
before it is set just like a user-variable).
(3) the set is guaranteed to be executed once the loop starts,
and the reg is not used until after that. */
else if (! ((! maybe_never
&& ! loop_reg_used_before_p (set, p, loop_start,
scan_start, end))
|| (! REG_USERVAR_P (SET_DEST (set))
&& ! REG_LOOP_TEST_P (SET_DEST (set)))
|| reg_in_basic_block_p (p, SET_DEST (set))))
;
else if ((tem = invariant_p (src))
&& (dependencies == 0
|| (tem2 = invariant_p (dependencies)) != 0)
&& (n_times_set[REGNO (SET_DEST (set))] == 1
|| (tem1
= consec_sets_invariant_p (SET_DEST (set),
n_times_set[REGNO (SET_DEST (set))],
p)))
/* If the insn can cause a trap (such as divide by zero),
can't move it unless it's guaranteed to be executed
once loop is entered. Even a function call might
prevent the trap insn from being reached
(since it might exit!) */
&& ! ((maybe_never || call_passed)
&& may_trap_p (src)))
{
register struct movable *m;
register int regno = REGNO (SET_DEST (set));
/* A potential lossage is where we have a case where two insns
can be combined as long as they are both in the loop, but
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.
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.
Don't do this if P has a REG_RETVAL note or if we have
SMALL_REGISTER_CLASSES and SET_SRC is a hard register. */
if (reg_single_usage && reg_single_usage[regno] != 0
&& reg_single_usage[regno] != const0_rtx
&& REGNO_FIRST_UID (regno) == INSN_UID (p)
&& (REGNO_LAST_UID (regno)
== INSN_UID (reg_single_usage[regno]))
&& n_times_set[REGNO (SET_DEST (set))] == 1
&& ! side_effects_p (SET_SRC (set))
&& ! find_reg_note (p, REG_RETVAL, NULL_RTX)
#ifdef SMALL_REGISTER_CLASSES
&& ! (SMALL_REGISTER_CLASSES
&& GET_CODE (SET_SRC (set)) == REG
&& REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)
#endif
/* This test is not redundant; SET_SRC (set) might be
a call-clobbered register and the life of REGNO
might span a call. */
&& ! modified_between_p (SET_SRC (set), p,
reg_single_usage[regno])
&& no_labels_between_p (p, reg_single_usage[regno])
&& validate_replace_rtx (SET_DEST (set), SET_SRC (set),
reg_single_usage[regno]))
{
/* Replace any usage in a REG_EQUAL note. Must copy the
new source, so that we don't get rtx sharing between the
SET_SOURCE and REG_NOTES of insn p. */
REG_NOTES (reg_single_usage[regno])
= replace_rtx (REG_NOTES (reg_single_usage[regno]),
SET_DEST (set), copy_rtx (SET_SRC (set)));
PUT_CODE (p, NOTE);
NOTE_LINE_NUMBER (p) = NOTE_INSN_DELETED;
NOTE_SOURCE_FILE (p) = 0;
n_times_set[regno] = 0;
continue;
}
m = (struct movable *) alloca (sizeof (struct movable));
m->next = 0;
m->insn = p;
m->set_src = src;
m->dependencies = dependencies;
m->set_dest = SET_DEST (set);
m->force = 0;
m->consec = n_times_set[REGNO (SET_DEST (set))] - 1;
m->done = 0;
m->forces = 0;
m->partial = 0;
m->move_insn = move_insn;
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). */
m->cond = ((tem | tem1 | tem2) > 1);
m->global = (uid_luid[REGNO_LAST_UID (regno)] > INSN_LUID (end)
|| uid_luid[REGNO_FIRST_UID (regno)] < INSN_LUID (loop_start));
m->match = 0;
m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
- uid_luid[REGNO_FIRST_UID (regno)]);
m->savings = n_times_used[regno];
if (find_reg_note (p, REG_RETVAL, NULL_RTX))
m->savings += libcall_benefit (p);
n_times_set[regno] = move_insn ? -2 : -1;
/* Add M to the end of the chain MOVABLES. */
if (movables == 0)
movables = m;
else
last_movable->next = m;
last_movable = m;
if (m->consec > 0)
{
/* Skip this insn, not checking REG_LIBCALL notes. */
p = next_nonnote_insn (p);
/* Skip the consecutive insns, if there are any. */
p = skip_consec_insns (p, m->consec);
/* Back up to the last insn of the consecutive group. */
p = prev_nonnote_insn (p);
/* We must now reset m->move_insn, m->is_equiv, and possibly
m->set_src to correspond to the effects of all the
insns. */
temp = find_reg_note (p, REG_EQUIV, NULL_RTX);
if (temp)
m->set_src = XEXP (temp, 0), m->move_insn = 1;
else
{
temp = find_reg_note (p, REG_EQUAL, NULL_RTX);
if (temp && CONSTANT_P (XEXP (temp, 0)))
m->set_src = XEXP (temp, 0), m->move_insn = 1;
else
m->move_insn = 0;
}
m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
}
}
/* If this register is always set within a STRICT_LOW_PART
or set to zero, then its high bytes are constant.
So clear them outside the loop and within the loop
just load the low bytes.
We must check that the machine has an instruction to do so.
Also, if the value loaded into the register
depends on the same register, this cannot be done. */
else if (SET_SRC (set) == const0_rtx
&& GET_CODE (NEXT_INSN (p)) == INSN
&& (set1 = single_set (NEXT_INSN (p)))
&& GET_CODE (set1) == SET
&& (GET_CODE (SET_DEST (set1)) == STRICT_LOW_PART)
&& (GET_CODE (XEXP (SET_DEST (set1), 0)) == SUBREG)
&& (SUBREG_REG (XEXP (SET_DEST (set1), 0))
== SET_DEST (set))
&& !reg_mentioned_p (SET_DEST (set), SET_SRC (set1)))
{
register int regno = REGNO (SET_DEST (set));
if (n_times_set[regno] == 2)
{
register struct movable *m;
m = (struct movable *) alloca (sizeof (struct movable));
m->next = 0;
m->insn = p;
m->set_dest = SET_DEST (set);
m->dependencies = 0;
m->force = 0;
m->consec = 0;
m->done = 0;
m->forces = 0;
m->move_insn = 0;
m->partial = 1;
/* If the insn may not be executed on some cycles,
we can't clear the whole reg; clear just high part.
Not even if the reg is used only within this loop.
Consider this:
while (1)
while (s != t) {
if (foo ()) x = *s;
use (x);
}
Clearing x before the inner loop could clobber a value
being saved from the last time around the outer loop.
However, if the reg is not used outside this loop
and all uses of the register are in the same
basic block as the store, there is no problem.
If this insn was made by loop, we don't know its
INSN_LUID and hence must make a conservative
assumption. */
m->global = (INSN_UID (p) >= max_uid_for_loop
|| (uid_luid[REGNO_LAST_UID (regno)]
> INSN_LUID (end))
|| (uid_luid[REGNO_FIRST_UID (regno)]
< INSN_LUID (p))
|| (labels_in_range_p
(p, uid_luid[REGNO_FIRST_UID (regno)])));
if (maybe_never && m->global)
m->savemode = GET_MODE (SET_SRC (set1));
else
m->savemode = VOIDmode;
m->regno = regno;
m->cond = 0;
m->match = 0;
m->lifetime = (uid_luid[REGNO_LAST_UID (regno)]
- uid_luid[REGNO_FIRST_UID (regno)]);
m->savings = 1;
n_times_set[regno] = -1;
/* Add M to the end of the chain MOVABLES. */
if (movables == 0)
movables = m;
else
last_movable->next = m;
last_movable = m;
}
}
}
/* Past a call insn, we get to insns which might not be executed
because the call might exit. This matters for insns that trap.
Call insns inside a REG_LIBCALL/REG_RETVAL block always return,
so they don't count. */
else if (GET_CODE (p) == CALL_INSN && ! in_libcall)
call_passed = 1;
/* Past a label or a jump, we get to insns for which we
can't count on whether or how many times they will be
executed during each iteration. Therefore, we can
only move out sets of trivial variables
(those not used after the loop). */
/* Similar code appears twice in strength_reduce. */
else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
/* If we enter the loop in the middle, and scan around to the
beginning, don't set maybe_never for that. This must be an
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)))
maybe_never = 1;
else if (GET_CODE (p) == NOTE)
{
/* At the virtual top of a converted loop, insns are again known to
be executed: logically, the loop begins here even though the exit
code has been duplicated. */
if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_VTOP && loop_depth == 0)
maybe_never = call_passed = 0;
else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
loop_depth++;
else if (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)
loop_depth--;
}
}
/* If one movable subsumes another, ignore that other. */
ignore_some_movables (movables);
/* For each movable insn, see if the reg that it loads
leads when it dies right into another conditionally movable insn.
If so, record that the second insn "forces" the first one,
since the second can be moved only if the first is. */
force_movables (movables);
/* See if there are multiple movable insns that load the same value.
If there are, make all but the first point at the first one
through the `match' field, and add the priorities of them
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 n_times_set for each reg that is moved. */
move_movables (movables, threshold,
insn_count, loop_start, end, nregs);
/* Now candidates that still are negative are those not moved.
Change n_times_set to indicate that those are not actually invariant. */
for (i = 0; i < nregs; i++)
if (n_times_set[i] < 0)
n_times_set[i] = n_times_used[i];
if (flag_strength_reduce)
strength_reduce (scan_start, end, loop_top,
insn_count, loop_start, end);
}
/* Add elements to *OUTPUT to record all the pseudo-regs
mentioned in IN_THIS but not mentioned in NOT_IN_THIS. */
void
record_excess_regs (in_this, not_in_this, output)
rtx in_this, not_in_this;
rtx *output;
{
enum rtx_code code;
char *fmt;
int i;
code = GET_CODE (in_this);
switch (code)
{
case PC:
case CC0:
case CONST_INT:
case CONST_DOUBLE:
case CONST:
case SYMBOL_REF:
case LABEL_REF:
return;
case REG:
if (REGNO (in_this) >= FIRST_PSEUDO_REGISTER
&& ! reg_mentioned_p (in_this, not_in_this))
*output = gen_rtx (EXPR_LIST, VOIDmode, in_this, *output);
return;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
int j;
switch (fmt[i])
{
case 'E':
for (j = 0; j < XVECLEN (in_this, i); j++)
record_excess_regs (XVECEXP (in_this, i, j), not_in_this, output);
break;
case 'e':
record_excess_regs (XEXP (in_this, i), not_in_this, output);
break;
}
}
}
/* Check what regs are referred to in the libcall block ending with INSN,
aside from those mentioned in the equivalent value.
If there are none, return 0.
If there are one or more, return an EXPR_LIST containing all of them. */
static rtx
libcall_other_reg (insn, equiv)
rtx insn, equiv;
{
rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
rtx p = XEXP (note, 0);
rtx output = 0;
/* First, find all the regs used in the libcall block
that are not mentioned as inputs to the result. */
while (p != insn)
{
if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
|| GET_CODE (p) == CALL_INSN)
record_excess_regs (PATTERN (p), equiv, &output);
p = NEXT_INSN (p);
}
return output;
}
/* Return 1 if all uses of REG
are between INSN and the end of the basic block. */
static int
reg_in_basic_block_p (insn, reg)
rtx insn, reg;
{
int regno = REGNO (reg);
rtx p;
if (REGNO_FIRST_UID (regno) != INSN_UID (insn))
return 0;
/* Search this basic block for the already recorded last use of the reg. */
for (p = insn; p; p = NEXT_INSN (p))
{
switch (GET_CODE (p))
{
case NOTE:
break;
case INSN:
case CALL_INSN:
/* Ordinary insn: if this is the last use, we win. */
if (REGNO_LAST_UID (regno) == INSN_UID (p))
return 1;
break;
case JUMP_INSN:
/* Jump insn: if this is the last use, we win. */
if (REGNO_LAST_UID (regno) == INSN_UID (p))
return 1;
/* Otherwise, it's the end of the basic block, so we lose. */
return 0;
case CODE_LABEL:
case BARRIER:
/* It's the end of the basic block, so we lose. */
return 0;
}
}
/* The "last use" doesn't follow the "first use"?? */
abort ();
}
/* Compute the benefit of eliminating the insns in the block whose
last insn is LAST. This may be a group of insns used to compute a
value directly or can contain a library call. */
static int
libcall_benefit (last)
rtx last;
{
rtx insn;
int benefit = 0;
for (insn = XEXP (find_reg_note (last, REG_RETVAL, NULL_RTX), 0);
insn != last; insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) == CALL_INSN)
benefit += 10; /* Assume at least this many insns in a library
routine. */
else if (GET_CODE (insn) == INSN
&& GET_CODE (PATTERN (insn)) != USE
&& GET_CODE (PATTERN (insn)) != CLOBBER)
benefit++;
}
return benefit;
}
/* Skip COUNT insns from INSN, counting library calls as 1 insn. */
static rtx
skip_consec_insns (insn, count)
rtx insn;
int count;
{
for (; count > 0; count--)
{
rtx temp;
/* If first insn of libcall sequence, skip to end. */
/* 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);
while (GET_CODE (insn) == NOTE);
}
return insn;
}
/* Ignore any movable whose insn falls within a libcall
which is part of another movable.
We make use of the fact that the movable for the libcall value
was made later and so appears later on the chain. */
static void
ignore_some_movables (movables)
struct movable *movables;
{
register struct movable *m, *m1;
for (m = movables; m; m = m->next)
{
/* Is this a movable for the value of a libcall? */
rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
if (note)
{
rtx insn;
/* Check for earlier movables inside that range,
and mark them invalid. We cannot use LUIDs here because
insns created by loop.c for prior loops don't have LUIDs.
Rather than reject all such insns from movables, we just
explicitly check each insn in the libcall (since invariant
libcalls aren't that common). */
for (insn = XEXP (note, 0); insn != m->insn; insn = NEXT_INSN (insn))
for (m1 = movables; m1 != m; m1 = m1->next)
if (m1->insn == insn)
m1->done = 1;
}
}
}
/* For each movable insn, see if the reg that it loads
leads when it dies right into another conditionally movable insn.
If so, record that the second insn "forces" the first one,
since the second can be moved only if the first is. */
static void
force_movables (movables)
struct movable *movables;
{
register struct movable *m, *m1;
for (m1 = movables; m1; m1 = m1->next)
/* Omit this if moving just the (SET (REG) 0) of a zero-extend. */
if (!m1->partial && !m1->done)
{
int regno = m1->regno;
for (m = m1->next; m; m = m->next)
/* ??? Could this be a bug? What if CSE caused the
register of M1 to be used after this insn?
Since CSE does not update regno_last_uid,
this insn M->insn might not be where it dies.
But very likely this doesn't matter; what matters is
that M's reg is computed from M1's reg. */
if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
&& !m->done)
break;
if (m != 0 && m->set_src == m1->set_dest
/* If m->consec, m->set_src isn't valid. */
&& m->consec == 0)
m = 0;
/* Increase the priority of the moving the first insn
since it permits the second to be moved as well. */
if (m != 0)
{
m->forces = m1;
m1->lifetime += m->lifetime;
m1->savings += m1->savings;
}
}
}
/* Find invariant expressions that are equal and can be combined into
one register. */
static void
combine_movables (movables, nregs)
struct movable *movables;
int nregs;
{
register struct movable *m;
char *matched_regs = (char *) alloca (nregs);
enum machine_mode mode;
/* Regs that are set more than once are not allowed to match
or be matched. I'm no longer sure why not. */
/* Perhaps testing m->consec_sets would be more appropriate here? */
for (m = movables; m; m = m->next)
if (m->match == 0 && n_times_used[m->regno] == 1 && !m->partial)
{
register struct movable *m1;
int regno = m->regno;
bzero (matched_regs, nregs);
matched_regs[regno] = 1;
for (m1 = movables; m1; m1 = m1->next)
if (m != m1 && m1->match == 0 && n_times_used[m1->regno] == 1
/* A reg used outside the loop mustn't be eliminated. */
&& !m1->global
/* A reg used for zero-extending mustn't be eliminated. */
&& !m1->partial
&& (matched_regs[m1->regno]
||
(
/* Can combine regs with different modes loaded from the
same constant only if the modes are the same or
if both are integer modes with M wider or the same
width as M1. The check for integer is redundant, but
safe, since the only case of differing destination
modes with equal sources is when both sources are
VOIDmode, i.e., CONST_INT. */
(GET_MODE (m->set_dest) == GET_MODE (m1->set_dest)
|| (GET_MODE_CLASS (GET_MODE (m->set_dest)) == MODE_INT
&& GET_MODE_CLASS (GET_MODE (m1->set_dest)) == MODE_INT
&& (GET_MODE_BITSIZE (GET_MODE (m->set_dest))
>= GET_MODE_BITSIZE (GET_MODE (m1->set_dest)))))
/* See if the source of M1 says it matches M. */
&& ((GET_CODE (m1->set_src) == REG
&& matched_regs[REGNO (m1->set_src)])
|| rtx_equal_for_loop_p (m->set_src, m1->set_src,
movables))))
&& ((m->dependencies == m1->dependencies)
|| rtx_equal_p (m->dependencies, m1->dependencies)))
{
m->lifetime += m1->lifetime;
m->savings += m1->savings;
m1->done = 1;
m1->match = m;
matched_regs[m1->regno] = 1;
}
}
/* Now combine the regs used for zero-extension.
This can be done for those not marked `global'
provided their lives don't overlap. */
for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
mode = GET_MODE_WIDER_MODE (mode))
{
register struct movable *m0 = 0;
/* Combine all the registers for extension from mode MODE.
Don't combine any that are used outside this loop. */
for (m = movables; m; m = m->next)
if (m->partial && ! m->global
&& mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
{
register struct movable *m1;
int first = uid_luid[REGNO_FIRST_UID (m->regno)];
int last = uid_luid[REGNO_LAST_UID (m->regno)];
if (m0 == 0)
{
/* First one: don't check for overlap, just record it. */
m0 = m;
continue;
}
/* Make sure they extend to the same mode.
(Almost always true.) */
if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
continue;
/* We already have one: check for overlap with those
already combined together. */
for (m1 = movables; m1 != m; m1 = m1->next)
if (m1 == m0 || (m1->partial && m1->match == m0))
if (! (uid_luid[REGNO_FIRST_UID (m1->regno)] > last
|| uid_luid[REGNO_LAST_UID (m1->regno)] < first))
goto overlap;
/* No overlap: we can combine this with the others. */
m0->lifetime += m->lifetime;
m0->savings += m->savings;
m->done = 1;
m->match = m0;
overlap: ;
}
}
}
/* Return 1 if regs X and Y will become the same if moved. */
static int
regs_match_p (x, y, movables)
rtx x, y;
struct movable *movables;
{
int xn = REGNO (x);
int yn = REGNO (y);
struct movable *mx, *my;
for (mx = movables; mx; mx = mx->next)
if (mx->regno == xn)
break;
for (my = movables; my; my = my->next)
if (my->regno == yn)
break;
return (mx && my
&& ((mx->match == my->match && mx->match != 0)
|| mx->match == my
|| mx == my->match));
}
/* Return 1 if X and Y are identical-looking rtx's.
This is the Lisp function EQUAL for rtx arguments.
If two registers are matching movables or a movable register and an
equivalent constant, consider them equal. */
static int
rtx_equal_for_loop_p (x, y, movables)
rtx x, y;
struct movable *movables;
{
register int i;
register int j;
register struct movable *m;
register enum rtx_code code;
register char *fmt;
if (x == y)
return 1;
if (x == 0 || y == 0)
return 0;
code = GET_CODE (x);
/* If we have a register and a constant, they may sometimes be
equal. */
if (GET_CODE (x) == REG && n_times_set[REGNO (x)] == -2
&& CONSTANT_P (y))
for (m = movables; m; m = m->next)
if (m->move_insn && m->regno == REGNO (x)
&& rtx_equal_p (m->set_src, y))
return 1;
else if (GET_CODE (y) == REG && n_times_set[REGNO (y)] == -2
&& CONSTANT_P (x))
for (m = movables; m; m = m->next)
if (m->move_insn && m->regno == REGNO (y)
&& rtx_equal_p (m->set_src, x))
return 1;
/* Otherwise, rtx's of different codes cannot be equal. */
if (code != GET_CODE (y))
return 0;
/* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
(REG:SI x) and (REG:HI x) are NOT equivalent. */
if (GET_MODE (x) != GET_MODE (y))
return 0;
/* These three types of rtx's can be compared nonrecursively. */
if (code == REG)
return (REGNO (x) == REGNO (y) || regs_match_p (x, y, movables));
if (code == LABEL_REF)
return XEXP (x, 0) == XEXP (y, 0);
if (code == SYMBOL_REF)
return XSTR (x, 0) == XSTR (y, 0);
/* Compare the elements. If any pair of corresponding elements
fail to match, return 0 for the whole things. */
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
switch (fmt[i])
{
case 'w':
if (XWINT (x, i) != XWINT (y, i))
return 0;
break;
case 'i':
if (XINT (x, i) != XINT (y, i))
return 0;
break;
case 'E':
/* Two vectors must have the same length. */
if (XVECLEN (x, i) != XVECLEN (y, i))
return 0;
/* And the corresponding elements must match. */
for (j = 0; j < XVECLEN (x, i); j++)
if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j), movables) == 0)
return 0;
break;
case 'e':
if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables) == 0)
return 0;
break;
case 's':
if (strcmp (XSTR (x, i), XSTR (y, i)))
return 0;
break;
case 'u':
/* These are just backpointers, so they don't matter. */
break;
case '0':
break;
/* It is believed that rtx's at this level will never
contain anything but integers and other rtx's,
except for within LABEL_REFs and SYMBOL_REFs. */
default:
abort ();
}
}
return 1;
}
/* If X contains any LABEL_REF's, add REG_LABEL notes for them to all
insns in INSNS which use thet reference. */
static void
add_label_notes (x, insns)
rtx x;
rtx insns;
{
enum rtx_code code = GET_CODE (x);
int i, j;
char *fmt;
rtx insn;
if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
{
rtx next = next_real_insn (XEXP (x, 0));
/* Don't record labels that refer to dispatch tables.
This is not necessary, since the tablejump references the same label.
And if we did record them, flow.c would make worse code. */
if (next == 0
|| ! (GET_CODE (next) == JUMP_INSN
&& (GET_CODE (PATTERN (next)) == ADDR_VEC
|| GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC)))
{
for (insn = insns; insn; insn = NEXT_INSN (insn))
if (reg_mentioned_p (XEXP (x, 0), insn))
REG_NOTES (insn) = gen_rtx (EXPR_LIST, REG_LABEL, XEXP (x, 0),
REG_NOTES (insn));
}
return;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
add_label_notes (XEXP (x, i), insns);
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
add_label_notes (XVECEXP (x, i, j), insns);
}
}
/* Scan MOVABLES, and move the insns that deserve to be moved.
If two matching movables are combined, replace one reg with the
other throughout. */
static void
move_movables (movables, threshold, insn_count, loop_start, end, nregs)
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;
/* 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));
num_movables = 0;
for (m = movables; m; m = m->next)
{
/* Describe this movable insn. */
if (loop_dump_stream)
{
fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
INSN_UID (m->insn), m->regno, m->lifetime);
if (m->consec > 0)
fprintf (loop_dump_stream, "consec %d, ", m->consec);
if (m->cond)
fprintf (loop_dump_stream, "cond ");
if (m->force)
fprintf (loop_dump_stream, "force ");
if (m->global)
fprintf (loop_dump_stream, "global ");
if (m->done)
fprintf (loop_dump_stream, "done ");
if (m->move_insn)
fprintf (loop_dump_stream, "move-insn ");
if (m->match)
fprintf (loop_dump_stream, "matches %d ",
INSN_UID (m->match->insn));
if (m->forces)
fprintf (loop_dump_stream, "forces %d ",
INSN_UID (m->forces->insn));
}
/* Count movables. Value used in heuristics in strength_reduce. */
num_movables++;
/* Ignore the insn if it's already done (it matched something else).
Otherwise, see if it is now safe to move. */
if (!m->done
&& (! m->cond
|| (1 == invariant_p (m->set_src)
&& (m->dependencies == 0
|| 1 == invariant_p (m->dependencies))
&& (m->consec == 0
|| 1 == consec_sets_invariant_p (m->set_dest,
m->consec + 1,
m->insn))))
&& (! m->forces || m->forces->done))
{
register int regno;
register rtx p;
int savings = m->savings;
/* We have an insn that is safe to move.
Compute its desirability. */
p = m->insn;
regno = m->regno;
if (loop_dump_stream)
fprintf (loop_dump_stream, "savings %d ", savings);
if (moved_once[regno])
{
insn_count *= 2;
if (loop_dump_stream)
fprintf (loop_dump_stream, "halved since already moved ");
}
/* An insn MUST be moved if we already moved something else
which is safe only if this one is moved too: that is,
if already_moved[REGNO] is nonzero. */
/* An insn is desirable to move if the new lifetime of the
register is no more than THRESHOLD times the old lifetime.
If it's not desirable, it means the loop is so big
that moving won't speed things up much,
and it is liable to make register usage worse. */
/* It is also desirable to move if it can be moved at no
extra cost because something else was already moved. */
if (already_moved[regno]
|| (threshold * savings * m->lifetime) >= insn_count
|| (m->forces && m->forces->done
&& n_times_used[m->forces->regno] == 1))
{
int count;
register struct movable *m1;
rtx first;
/* Now move the insns that set the reg. */
if (m->partial && m->match)
{
rtx newpat, i1;
rtx r1, r2;
/* Find the end of this chain of matching regs.
Thus, we load each reg in the chain from that one reg.
And that reg is loaded with 0 directly,
since it has ->match == 0. */
for (m1 = m; m1->match; m1 = m1->match);
newpat = gen_move_insn (SET_DEST (PATTERN (m->insn)),
SET_DEST (PATTERN (m1->insn)));
i1 = emit_insn_before (newpat, loop_start);
/* Mark the moved, invariant reg as being allowed to
share a hard reg with the other matching invariant. */
REG_NOTES (i1) = REG_NOTES (m->insn);
r1 = SET_DEST (PATTERN (m->insn));
r2 = SET_DEST (PATTERN (m1->insn));
regs_may_share = gen_rtx (EXPR_LIST, VOIDmode, r1,
gen_rtx (EXPR_LIST, VOIDmode, r2,
regs_may_share));
delete_insn (m->insn);
if (new_start == 0)
new_start = i1;
if (loop_dump_stream)
fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
}
/* If we are to re-generate the item being moved with a
new move insn, first delete what we have and then emit
the move insn before the loop. */
else if (m->move_insn)
{
rtx i1, temp;
for (count = m->consec; count >= 0; count--)
{
/* If this is the first insn of a library call sequence,
skip to the end. */
if (GET_CODE (p) != NOTE
&& (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
p = XEXP (temp, 0);
/* If this is the last insn of a libcall sequence, then
delete every insn in the sequence except the last.
The last insn is handled in the normal manner. */
if (GET_CODE (p) != NOTE
&& (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
{
temp = XEXP (temp, 0);
while (temp != p)
temp = delete_insn (temp);
}
p = delete_insn (p);
while (p && GET_CODE (p) == NOTE)
p = NEXT_INSN (p);
}
start_sequence ();
emit_move_insn (m->set_dest, m->set_src);
temp = get_insns ();
end_sequence ();
add_label_notes (m->set_src, temp);
i1 = emit_insns_before (temp, loop_start);
if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
REG_NOTES (i1)
= gen_rtx (EXPR_LIST,
m->is_equiv ? REG_EQUIV : REG_EQUAL,
m->set_src, REG_NOTES (i1));
if (loop_dump_stream)
fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
/* The more regs we move, the less we like moving them. */
threshold -= 3;
}
else
{
for (count = m->consec; count >= 0; count--)
{
rtx i1, temp;
/* If first insn of libcall sequence, skip to end. */
/* Do this at start of loop, since p is guaranteed to
be an insn here. */
if (GET_CODE (p) != NOTE
&& (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
p = XEXP (temp, 0);
/* If last insn of libcall sequence, move all
insns except the last before the loop. The last
insn is handled in the normal manner. */
if (GET_CODE (p) != NOTE
&& (temp = find_reg_note (p, REG_RETVAL, NULL_RTX)))
{
rtx fn_address = 0;
rtx fn_reg = 0;
rtx fn_address_insn = 0;
first = 0;
for (temp = XEXP (temp, 0); temp != p;
temp = NEXT_INSN (temp))
{
rtx body;
rtx n;
rtx next;
if (GET_CODE (temp) == NOTE)
continue;
body = PATTERN (temp);
/* Find the next insn after TEMP,
not counting USE or NOTE insns. */
for (next = NEXT_INSN (temp); next != p;
next = NEXT_INSN (next))
if (! (GET_CODE (next) == INSN
&& 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.
Extract the function address from the insn
that loads it into a register.
If this insn was cse'd, we get incorrect code.
So emit a new move insn that copies the
function address into the register that the
call insn will use. flow.c will delete any
redundant stores that we have created. */
if (GET_CODE (next) == CALL_INSN
&& GET_CODE (body) == SET
&& GET_CODE (SET_DEST (body)) == REG
&& (n = find_reg_note (temp, REG_EQUAL,
NULL_RTX)))
{
fn_reg = SET_SRC (body);
if (GET_CODE (fn_reg) != REG)
fn_reg = SET_DEST (body);
fn_address = XEXP (n, 0);
fn_address_insn = temp;
}
/* We have the call insn.
If it uses the register we suspect it might,
load it with the correct address directly. */
if (GET_CODE (temp) == CALL_INSN
&& fn_address != 0
&& reg_referenced_p (fn_reg, body))
emit_insn_after (gen_move_insn (fn_reg,
fn_address),
fn_address_insn);
if (GET_CODE (temp) == CALL_INSN)
{
i1 = emit_call_insn_before (body, loop_start);
/* Because the USAGE information potentially
contains objects other than hard registers
we need to copy it. */
if (CALL_INSN_FUNCTION_USAGE (temp))
CALL_INSN_FUNCTION_USAGE (i1)
= copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
}
else
i1 = emit_insn_before (body, loop_start);
if (first == 0)
first = i1;
if (temp == fn_address_insn)
fn_address_insn = i1;
REG_NOTES (i1) = REG_NOTES (temp);
delete_insn (temp);
}
}
if (m->savemode != VOIDmode)
{
/* P sets REG to zero; but we should clear only
the bits that are not covered by the mode
m->savemode. */
rtx reg = m->set_dest;
rtx sequence;
rtx tem;
start_sequence ();
tem = expand_binop
(GET_MODE (reg), and_optab, reg,
GEN_INT ((((HOST_WIDE_INT) 1
<< GET_MODE_BITSIZE (m->savemode)))
- 1),
reg, 1, OPTAB_LIB_WIDEN);
if (tem == 0)
abort ();
if (tem != reg)
emit_move_insn (reg, tem);
sequence = gen_sequence ();
end_sequence ();
i1 = emit_insn_before (sequence, loop_start);
}
else if (GET_CODE (p) == CALL_INSN)
{
i1 = emit_call_insn_before (PATTERN (p), loop_start);
/* Because the USAGE information potentially
contains objects other than hard registers
we need to copy it. */
if (CALL_INSN_FUNCTION_USAGE (p))
CALL_INSN_FUNCTION_USAGE (i1)
= copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
}
else
i1 = emit_insn_before (PATTERN (p), loop_start);
REG_NOTES (i1) = REG_NOTES (p);
/* If there is a REG_EQUAL note present whose value is
not loop invariant, then delete it, since it may
cause problems with later optimization passes.
It is possible for cse to create such notes
like this as a result of record_jump_cond. */
if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
&& ! invariant_p (XEXP (temp, 0)))
remove_note (i1, temp);
if (new_start == 0)
new_start = i1;
if (loop_dump_stream)
fprintf (loop_dump_stream, " moved to %d",
INSN_UID (i1));
#if 0
/* This isn't needed because REG_NOTES is copied
below and is wrong since P might be a PARALLEL. */
if (REG_NOTES (i1) == 0
&& ! m->partial /* But not if it's a zero-extend clr. */
&& ! m->global /* and not if used outside the loop
(since it might get set outside). */
&& CONSTANT_P (SET_SRC (PATTERN (p))))
REG_NOTES (i1)
= gen_rtx (EXPR_LIST, REG_EQUAL,
SET_SRC (PATTERN (p)), REG_NOTES (i1));
#endif
/* If library call, now fix the REG_NOTES that contain
insn pointers, namely REG_LIBCALL on FIRST
and REG_RETVAL on I1. */
if (temp = find_reg_note (i1, REG_RETVAL, NULL_RTX))
{
XEXP (temp, 0) = first;
temp = find_reg_note (first, REG_LIBCALL, NULL_RTX);
XEXP (temp, 0) = i1;
}
delete_insn (p);
do p = NEXT_INSN (p);
while (p && GET_CODE (p) == NOTE);
}
/* The more regs we move, the less we like moving them. */
threshold -= 3;
}
/* Any other movable that loads the same register
MUST be moved. */
already_moved[regno] = 1;
/* This reg has been moved out of one loop. */
moved_once[regno] = 1;
/* The reg set here is now invariant. */
if (! m->partial)
n_times_set[regno] = 0;
m->done = 1;
/* Change the length-of-life info for the register
to say it lives at least the full length of this loop.
This will help guide optimizations in outer loops. */
if (uid_luid[REGNO_FIRST_UID (regno)] > INSN_LUID (loop_start))
/* This is the old insn before all the moved insns.
We can't use the moved insn because it is out of range
in uid_luid. Only the old insns have luids. */
REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
if (uid_luid[REGNO_LAST_UID (regno)] < INSN_LUID (end))
REGNO_LAST_UID (regno) = INSN_UID (end);
/* Combine with this moved insn any other matching movables. */
if (! m->partial)
for (m1 = movables; m1; m1 = m1->next)
if (m1->match == m)
{
rtx temp;
/* Schedule the reg loaded by M1
for replacement so that shares the reg of M.
If the modes differ (only possible in restricted
circumstances, make a SUBREG. */
if (GET_MODE (m->set_dest) == GET_MODE (m1->set_dest))
reg_map[m1->regno] = m->set_dest;
else
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;
/* if library call, delete all insn except last, which
is deleted below */
if (temp = find_reg_note (m1->insn, REG_RETVAL,
NULL_RTX))
{
for (temp = XEXP (temp, 0); temp != m1->insn;
temp = NEXT_INSN (temp))
delete_insn (temp);
}
delete_insn (m1->insn);
/* Any other movable that loads the same register
MUST be moved. */
already_moved[m1->regno] = 1;
/* The reg merged here is now invariant,
if the reg it matches is invariant. */
if (! m->partial)
n_times_set[m1->regno] = 0;
}
}
else if (loop_dump_stream)
fprintf (loop_dump_stream, "not desirable");
}
else if (loop_dump_stream && !m->match)
fprintf (loop_dump_stream, "not safe");
if (loop_dump_stream)
fprintf (loop_dump_stream, "\n");
}
if (new_start == 0)
new_start = loop_start;
/* 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))
if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
|| GET_CODE (p) == CALL_INSN)
{
replace_regs (PATTERN (p), reg_map, nregs, 0);
replace_regs (REG_NOTES (p), reg_map, nregs, 0);
INSN_CODE (p) = -1;
}
}
#if 0
/* Scan X and replace the address of any MEM in it with ADDR.
REG is the address that MEM should have before the replacement. */
static void
replace_call_address (x, reg, addr)
rtx x, reg, addr;
{
register enum rtx_code code;
register int i;
register char *fmt;
if (x == 0)
return;
code = GET_CODE (x);
switch (code)
{
case PC:
case CC0:
case CONST_INT:
case CONST_DOUBLE:
case CONST:
case SYMBOL_REF:
case LABEL_REF:
case REG:
return;
case SET:
/* Short cut for very common case. */
replace_call_address (XEXP (x, 1), reg, addr);
return;
case CALL:
/* Short cut for very common case. */
replace_call_address (XEXP (x, 0), reg, addr);
return;
case MEM:
/* If this MEM uses a reg other than the one we expected,
something is wrong. */
if (XEXP (x, 0) != reg)
abort ();
XEXP (x, 0) = addr;
return;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
replace_call_address (XEXP (x, i), reg, addr);
if (fmt[i] == 'E')
{
register int j;
for (j = 0; j < XVECLEN (x, i); j++)
replace_call_address (XVECEXP (x, i, j), reg, addr);
}
}
}
#endif
/* Return the number of memory refs to addresses that vary
in the rtx X. */
static int
count_nonfixed_reads (x)
rtx x;
{
register enum rtx_code code;
register int i;
register char *fmt;
int value;
if (x == 0)
return 0;
code = GET_CODE (x);
switch (code)
{
case PC:
case CC0:
case CONST_INT:
case CONST_DOUBLE:
case CONST:
case SYMBOL_REF:
case LABEL_REF:
case REG:
return 0;
case MEM:
return ((invariant_p (XEXP (x, 0)) != 1)
+ count_nonfixed_reads (XEXP (x, 0)));
}
value = 0;
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
value += count_nonfixed_reads (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));
}
}
return value;
}
#if 0
/* P is an instruction that sets a register to the result of a ZERO_EXTEND.
Replace it with an instruction to load just the low bytes
if the machine supports such an instruction,
and insert above LOOP_START an instruction to clear the register. */
static void
constant_high_bytes (p, loop_start)
rtx p, loop_start;
{
register rtx new;
register int insn_code_number;
/* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */
new = gen_rtx (SET, VOIDmode,
gen_rtx (STRICT_LOW_PART, VOIDmode,
gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)),
SET_DEST (PATTERN (p)),
0)),
XEXP (SET_SRC (PATTERN (p)), 0));
insn_code_number = recog (new, p);
if (insn_code_number)
{
register int i;
/* Clear destination register before the loop. */
emit_insn_before (gen_rtx (SET, VOIDmode,
SET_DEST (PATTERN (p)),
const0_rtx),
loop_start);
/* Inside the loop, just load the low part. */
PATTERN (p) = new;
}
}
#endif
/* Scan a loop setting the variables `unknown_address_altered',
`num_mem_sets', `loop_continue', loops_enclosed', `loop_has_call',
and `loop_has_volatile'.
Also, fill in the array `loop_store_mems'. */
static void
prescan_loop (start, end)
rtx start, end;
{
register int level = 1;
register rtx insn;
unknown_address_altered = 0;
loop_has_call = 0;
loop_has_volatile = 0;
loop_store_mems_idx = 0;
num_mem_sets = 0;
loops_enclosed = 1;
loop_continue = 0;
for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) == NOTE)
{
if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
{
++level;
/* Count number of loops contained in this one. */
loops_enclosed++;
}
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
{
--level;
if (level == 0)
{
end = insn;
break;
}
}
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT)
{
if (level == 1)
loop_continue = insn;
}
}
else if (GET_CODE (insn) == CALL_INSN)
{
unknown_address_altered = 1;
loop_has_call = 1;
}
else
{
if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
{
if (volatile_refs_p (PATTERN (insn)))
loop_has_volatile = 1;
note_stores (PATTERN (insn), note_addr_stored);
}
}
}
}
/* Scan the function looking for loops. Record the start and end of each loop.
Also mark as invalid loops any loops that contain a setjmp or are branched
to from outside the loop. */
static void
find_and_verify_loops (f)
rtx f;
{
rtx insn, label;
int current_loop = -1;
int next_loop = -1;
int loop;
/* 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;
/* Find boundaries of loops, mark which loops are contained within
loops, and invalidate loops that have setjmp. */
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_outer_loop[next_loop] = current_loop;
loop_invalid[next_loop] = 0;
loop_number_exit_labels[next_loop] = 0;
loop_number_exit_count[next_loop] = 0;
current_loop = next_loop;
break;
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])
{
loop_invalid[loop] = 1;
if (loop_dump_stream)
fprintf (loop_dump_stream,
"\nLoop at %d ignored due to setjmp.\n",
INSN_UID (loop_number_loop_starts[loop]));
}
break;
case NOTE_INSN_LOOP_END:
if (current_loop == -1)
abort ();
loop_number_loop_ends[current_loop] = insn;
current_loop = loop_outer_loop[current_loop];
break;
}
/* 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;
}
/* Any loop containing a label used in an initializer must be invalidated,
because it can be jumped into from anywhere. */
for (label = forced_labels; label; label = XEXP (label, 1))
{
int loop_num;
for (loop_num = uid_loop_num[INSN_UID (XEXP (label, 0))];
loop_num != -1;
loop_num = loop_outer_loop[loop_num])
loop_invalid[loop_num] = 1;
}
/* Any loop containing a label used for an exception handler must be
invalidated, because it can be jumped into from anywhere. */
for (label = exception_handler_labels; label; label = XEXP (label, 1))
{
int loop_num;
for (loop_num = uid_loop_num[INSN_UID (XEXP (label, 0))];
loop_num != -1;
loop_num = loop_outer_loop[loop_num])
loop_invalid[loop_num] = 1;
}
/* Now scan all insn's in the function. If any JUMP_INSN branches into a
loop that it is not contained within, that loop is marked invalid.
If any INSN or CALL_INSN uses a label's address, then the loop containing
that label is marked invalid, because it could be jumped into from
anywhere.
Also look for blocks of code ending in an unconditional branch that
exits the loop. If such a block is surrounded by a conditional
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')
{
int this_loop_num = uid_loop_num[INSN_UID (insn)];
if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
{
rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
if (note)
{
int loop_num;
for (loop_num = uid_loop_num[INSN_UID (XEXP (note, 0))];
loop_num != -1;
loop_num = loop_outer_loop[loop_num])
loop_invalid[loop_num] = 1;
}
}
if (GET_CODE (insn) != JUMP_INSN)
continue;
mark_loop_jump (PATTERN (insn), this_loop_num);
/* See if this is an unconditional branch outside the loop. */
if (this_loop_num != -1
&& (GET_CODE (PATTERN (insn)) == RETURN
|| (simplejump_p (insn)
&& (uid_loop_num[INSN_UID (JUMP_LABEL (insn))]
!= this_loop_num)))
&& get_max_uid () < max_uid_for_loop)
{
rtx p;
rtx our_next = next_real_insn (insn);
int dest_loop;
int outer_loop = -1;
/* Go backwards until we reach the start of the loop, a label,
or a JUMP_INSN. */
for (p = PREV_INSN (insn);
GET_CODE (p) != CODE_LABEL
&& ! (GET_CODE (p) == NOTE
&& NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
&& GET_CODE (p) != JUMP_INSN;
p = PREV_INSN (p))
;
/* Check for the case where we have a jump to an inner nested
loop, and do not perform the optimization in that case. */
if (JUMP_LABEL (insn))
{
dest_loop = uid_loop_num[INSN_UID (JUMP_LABEL (insn))];
if (dest_loop != -1)
{
for (outer_loop = dest_loop; outer_loop != -1;
outer_loop = loop_outer_loop[outer_loop])
if (outer_loop == this_loop_num)
break;
}
}
/* Make sure that the target of P is within the current loop. */
if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
&& uid_loop_num[INSN_UID (JUMP_LABEL (p))] != this_loop_num)
outer_loop = this_loop_num;
/* If we stopped on a JUMP_INSN to the next insn after INSN,
we have a block of code to try to move.
We look backward and then forward from the target of INSN
to find a BARRIER at the same loop depth as the target.
If we find such a BARRIER, we make a new label for the start
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
&& 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)
&& next_real_insn (JUMP_LABEL (p)) == our_next)
{
rtx target
= JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
int target_loop_num = uid_loop_num[INSN_UID (target)];
rtx loc;
for (loc = target; loc; loc = PREV_INSN (loc))
if (GET_CODE (loc) == BARRIER
&& uid_loop_num[INSN_UID (loc)] == target_loop_num)
break;
if (loc == 0)
for (loc = target; loc; loc = NEXT_INSN (loc))
if (GET_CODE (loc) == BARRIER
&& uid_loop_num[INSN_UID (loc)] == target_loop_num)
break;
if (loc)
{
rtx cond_label = JUMP_LABEL (p);
rtx new_label = get_label_after (p);
/* Ensure our label doesn't go away. */
LABEL_NUSES (cond_label)++;
/* Verify that uid_loop_num is large enough and that
we can invert P. */
if (invert_jump (p, new_label))
{
rtx q, r;
/* Include the BARRIER after INSN and copy the
block after LOC. */
new_label = squeeze_notes (new_label, NEXT_INSN (insn));
reorder_insns (new_label, NEXT_INSN (insn), loc);
/* All those insns are now in TARGET_LOOP_NUM. */
for (q = new_label; q != NEXT_INSN (NEXT_INSN (insn));
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);
}
/* Continue the loop after where the conditional
branch used to jump, since the only branch insn
in the block (if it still remains) is an inter-loop
branch and hence needs no processing. */
insn = NEXT_INSN (cond_label);
if (--LABEL_NUSES (cond_label) == 0)
delete_insn (cond_label);
/* This loop will be continued with NEXT_INSN (insn). */
insn = PREV_INSN (insn);
}
}
}
}
}
/* If any label in X jumps to a loop different from LOOP_NUM and any of the
loops it is contained in, mark the target loop invalid.
For speed, we assume that X is part of a pattern of a JUMP_INSN. */
static void
mark_loop_jump (x, loop_num)
rtx x;
int loop_num;
{
int dest_loop;
int outer_loop;
int i;
switch (GET_CODE (x))
{
case PC:
case USE:
case CLOBBER:
case REG:
case MEM:
case CONST_INT:
case CONST_DOUBLE:
case RETURN:
return;
case CONST:
/* There could be a label reference in here. */
mark_loop_jump (XEXP (x, 0), loop_num);
return;
case PLUS:
case MINUS:
case MULT:
mark_loop_jump (XEXP (x, 0), loop_num);
mark_loop_jump (XEXP (x, 1), loop_num);
return;
case SIGN_EXTEND:
case ZERO_EXTEND:
mark_loop_jump (XEXP (x, 0), loop_num);
return;
case LABEL_REF:
dest_loop = uid_loop_num[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
mark this LABEL_REF so we know that this branch should predict
false. */
/* A check to make sure the label is not in an inner nested loop,
since this does not count as a loop exit. */
if (dest_loop != -1)
{
for (outer_loop = dest_loop; outer_loop != -1;
outer_loop = loop_outer_loop[outer_loop])
if (outer_loop == loop_num)
break;
}
else
outer_loop = -1;
if (loop_num != -1 && outer_loop == -1)
{
LABEL_OUTSIDE_LOOP_P (x) = 1;
LABEL_NEXTREF (x) = loop_number_exit_labels[loop_num];
loop_number_exit_labels[loop_num] = x;
for (outer_loop = loop_num;
outer_loop != -1 && outer_loop != dest_loop;
outer_loop = loop_outer_loop[outer_loop])
loop_number_exit_count[outer_loop]++;
}
/* If this is inside a loop, but not in the current loop or one enclosed
by it, it invalidates at least one loop. */
if (dest_loop == -1)
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])
{
/* 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])
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])
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;
}
return;
case SET:
/* If this is not setting pc, ignore. */
if (SET_DEST (x) == pc_rtx)
mark_loop_jump (SET_SRC (x), loop_num);
return;
case IF_THEN_ELSE:
mark_loop_jump (XEXP (x, 1), loop_num);
mark_loop_jump (XEXP (x, 2), loop_num);
return;
case PARALLEL:
case ADDR_VEC:
for (i = 0; i < XVECLEN (x, 0); i++)
mark_loop_jump (XVECEXP (x, 0, i), loop_num);
return;
case ADDR_DIFF_VEC:
for (i = 0; i < XVECLEN (x, 1); i++)
mark_loop_jump (XVECEXP (x, 1, i), loop_num);
return;
default:
/* Treat anything else (such as a symbol_ref)
as a branch out of this loop, but not into any loop. */
if (loop_num != -1)
{
loop_number_exit_labels[loop_num] = x;
for (outer_loop = loop_num; outer_loop != -1;
outer_loop = loop_outer_loop[outer_loop])
loop_number_exit_count[outer_loop]++;
}
return;
}
}
/* Return nonzero if there is a label in the range from
insn INSN to and including the insn whose luid is END
INSN must have an assigned luid (i.e., it must not have
been previously created by loop.c). */
static int
labels_in_range_p (insn, end)
rtx insn;
int end;
{
while (insn && INSN_LUID (insn) <= end)
{
if (GET_CODE (insn) == CODE_LABEL)
return 1;
insn = NEXT_INSN (insn);
}
return 0;
}
/* Record that a memory reference X is being set. */
static void
note_addr_stored (x)
rtx x;
{
register int i;
if (x == 0 || GET_CODE (x) != MEM)
return;
/* Count number of memory writes.
This affects heuristics in strength_reduce. */
num_mem_sets++;
/* BLKmode MEM means all memory is clobbered. */
if (GET_MODE (x) == BLKmode)
unknown_address_altered = 1;
if (unknown_address_altered)
return;
for (i = 0; i < loop_store_mems_idx; i++)
if (rtx_equal_p (XEXP (loop_store_mems[i], 0), XEXP (x, 0))
&& MEM_IN_STRUCT_P (x) == MEM_IN_STRUCT_P (loop_store_mems[i]))
{
/* We are storing at the same address as previously noted. Save the
wider reference. */
if (GET_MODE_SIZE (GET_MODE (x))
> GET_MODE_SIZE (GET_MODE (loop_store_mems[i])))
loop_store_mems[i] = x;
break;
}
if (i == NUM_STORES)
unknown_address_altered = 1;
else if (i == loop_store_mems_idx)
loop_store_mems[loop_store_mems_idx++] = x;
}
/* Return nonzero if the rtx X is invariant over the current loop.
The value is 2 if we refer to something only conditionally invariant.
If `unknown_address_altered' is nonzero, no memory ref is invariant.
Otherwise, a memory ref is invariant if it does not conflict with
anything stored in `loop_store_mems'. */
int
invariant_p (x)
register rtx x;
{
register int i;
register enum rtx_code code;
register char *fmt;
int conditional = 0;
if (x == 0)
return 1;
code = GET_CODE (x);
switch (code)
{
case CONST_INT:
case CONST_DOUBLE:
case SYMBOL_REF:
case CONST:
return 1;
case LABEL_REF:
/* A LABEL_REF is normally invariant, however, if we are unrolling
loops, and this label is inside the loop, then it isn't invariant.
This is because each unrolled copy of the loop body will have
a copy of this label. If this was invariant, then an insn loading
the address of this label into a register might get moved outside
the loop, and then each loop body would end up using the same label.
We don't know the loop bounds here though, so just fail for all
labels. */
if (flag_unroll_loops)
return 0;
else
return 1;
case PC:
case CC0:
case UNSPEC_VOLATILE:
return 0;
case REG:
/* We used to check RTX_UNCHANGING_P (x) here, but that is invalid
since the reg might be set by initialization within the loop. */
if ((x == frame_pointer_rtx || x == hard_frame_pointer_rtx
|| x == arg_pointer_rtx)
&& ! current_function_has_nonlocal_goto)
return 1;
if (loop_has_call
&& REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
return 0;
if (n_times_set[REGNO (x)] < 0)
return 2;
return n_times_set[REGNO (x)] == 0;
case MEM:
/* Volatile memory references must be rejected. Do this before
checking for read-only items, so that volatile read-only items
will be rejected also. */
if (MEM_VOLATILE_P (x))
return 0;
/* Read-only items (such as constants in a constant pool) are
invariant if their address is. */
if (RTX_UNCHANGING_P (x))
break;
/* If we filled the table (or had a subroutine call), any location
in memory could have been clobbered. */
if (unknown_address_altered)
return 0;
/* See if there is any dependence between a store and this load. */
for (i = loop_store_mems_idx - 1; i >= 0; i--)
if (true_dependence (loop_store_mems[i], x))
return 0;
/* It's not invalidated by a store in memory
but we must still verify the address is invariant. */
break;
case ASM_OPERANDS:
/* Don't mess with insns declared volatile. */
if (MEM_VOLATILE_P (x))
return 0;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
{
int tem = invariant_p (XEXP (x, i));
if (tem == 0)
return 0;
if (tem == 2)
conditional = 1;
}
else if (fmt[i] == 'E')
{
register int j;
for (j = 0; j < XVECLEN (x, i); j++)
{
int tem = invariant_p (XVECEXP (x, i, j));
if (tem == 0)
return 0;
if (tem == 2)
conditional = 1;
}
}
}
return 1 + conditional;
}
/* Return nonzero if all the insns in the loop that set REG
are INSN and the immediately following insns,
and if each of those insns sets REG in an invariant way
(not counting uses of REG in them).
The value is 2 if some of these insns are only conditionally invariant.
We assume that INSN itself is the first set of REG
and that its source is invariant. */
static int
consec_sets_invariant_p (reg, n_sets, insn)
int n_sets;
rtx reg, insn;
{
register rtx p = insn;
register int regno = REGNO (reg);
rtx temp;
/* Number of sets we have to insist on finding after INSN. */
int count = n_sets - 1;
int old = n_times_set[regno];
int value = 0;
int this;
/* If N_SETS hit the limit, we can't rely on its value. */
if (n_sets == 127)
return 0;
n_times_set[regno] = 0;
while (count > 0)
{
register enum rtx_code code;
rtx set;
p = NEXT_INSN (p);
code = GET_CODE (p);
/* If library call, skip to end of of it. */
if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
p = XEXP (temp, 0);
this = 0;
if (code == INSN
&& (set = single_set (p))
&& GET_CODE (SET_DEST (set)) == REG
&& REGNO (SET_DEST (set)) == regno)
{
this = invariant_p (SET_SRC (set));
if (this != 0)
value |= this;
else if (temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
{
/* If this is a libcall, then any invariant REG_EQUAL note is OK.
If this is an ordinary insn, then only CONSTANT_P REG_EQUAL
notes are OK. */
this = (CONSTANT_P (XEXP (temp, 0))
|| (find_reg_note (p, REG_RETVAL, NULL_RTX)
&& invariant_p (XEXP (temp, 0))));
if (this != 0)
value |= this;
}
}
if (this != 0)
count--;
else if (code != NOTE)
{
n_times_set[regno] = old;
return 0;
}
}
n_times_set[regno] = old;
/* If invariant_p ever returned 2, we return 2. */
return 1 + (value & 2);
}
#if 0
/* I don't think this condition is sufficient to allow INSN
to be moved, so we no longer test it. */
/* Return 1 if all insns in the basic block of INSN and following INSN
that set REG are invariant according to TABLE. */
static int
all_sets_invariant_p (reg, insn, table)
rtx reg, insn;
short *table;
{
register rtx p = insn;
register int regno = REGNO (reg);
while (1)
{
register enum rtx_code code;
p = NEXT_INSN (p);
code = GET_CODE (p);
if (code == CODE_LABEL || code == JUMP_INSN)
return 1;
if (code == INSN && GET_CODE (PATTERN (p)) == SET
&& GET_CODE (SET_DEST (PATTERN (p))) == REG
&& REGNO (SET_DEST (PATTERN (p))) == regno)
{
if (!invariant_p (SET_SRC (PATTERN (p)), table))
return 0;
}
}
}
#endif /* 0 */
/* Look at all uses (not sets) of registers in X. For each, if it is
the single use, set USAGE[REGNO] to INSN; if there was a previous use in
a different insn, set USAGE[REGNO] to const0_rtx. */
static void
find_single_use_in_loop (insn, x, usage)
rtx insn;
rtx x;
rtx *usage;
{
enum rtx_code code = GET_CODE (x);
char *fmt = GET_RTX_FORMAT (code);
int i, j;
if (code == REG)
usage[REGNO (x)]
= (usage[REGNO (x)] != 0 && usage[REGNO (x)] != insn)
? const0_rtx : insn;
else if (code == SET)
{
/* 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
for it. */
if (GET_CODE (SET_DEST (x)) != REG)
find_single_use_in_loop (insn, SET_DEST (x), usage);
find_single_use_in_loop (insn, SET_SRC (x), usage);
}
else
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e' && XEXP (x, i) != 0)
find_single_use_in_loop (insn, XEXP (x, i), usage);
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
find_single_use_in_loop (insn, XVECEXP (x, i, j), usage);
}
}
/* Increment N_TIMES_SET at the index of each register
that is modified by an insn between FROM and TO.
If the value of an element of N_TIMES_SET becomes 127 or more,
stop incrementing it, to avoid overflow.
Store in SINGLE_USAGE[I] the single insn in which register I is
used, if it is only used once. Otherwise, it is set to 0 (for no
uses) or const0_rtx for more than one use. This parameter may be zero,
in which case this processing is not done.
Store in *COUNT_PTR the number of actual instruction
in the loop. We use this to decide what is worth moving out. */
/* last_set[n] is nonzero iff reg n has been set in the current basic block.
In that case, it is the insn that last set reg n. */
static void
count_loop_regs_set (from, to, may_not_move, single_usage, count_ptr, nregs)
register rtx from, to;
char *may_not_move;
rtx *single_usage;
int *count_ptr;
int nregs;
{
register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx));
register rtx insn;
register int count = 0;
register rtx dest;
bzero ((char *) last_set, nregs * sizeof (rtx));
for (insn = from; insn != to; insn = NEXT_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
++count;
/* If requested, record registers that have exactly one use. */
if (single_usage)
{
find_single_use_in_loop (insn, PATTERN (insn), single_usage);
/* Include uses in REG_EQUAL notes. */
if (REG_NOTES (insn))
find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
}
if (GET_CODE (PATTERN (insn)) == CLOBBER
&& GET_CODE (XEXP (PATTERN (insn), 0)) == REG)
/* Don't move a reg that has an explicit clobber.
We might do so sometimes, but it's not worth the pain. */
may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1;
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
{
dest = SET_DEST (PATTERN (insn));
while (GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT
|| GET_CODE (dest) == SIGN_EXTRACT
|| GET_CODE (dest) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
if (GET_CODE (dest) == REG)
{
register int regno = REGNO (dest);
/* If this is the first setting of this reg
in current basic block, and it was set before,
it must be set in two basic blocks, so it cannot
be moved out of the loop. */
if (n_times_set[regno] > 0 && last_set[regno] == 0)
may_not_move[regno] = 1;
/* If this is not first setting in current basic block,
see if reg was used in between previous one and this.
If so, neither one can be moved. */
if (last_set[regno] != 0
&& reg_used_between_p (dest, last_set[regno], insn))
may_not_move[regno] = 1;
if (n_times_set[regno] < 127)
++n_times_set[regno];
last_set[regno] = insn;
}
}
else if (GET_CODE (PATTERN (insn)) == PARALLEL)
{
register int i;
for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
{
register rtx x = XVECEXP (PATTERN (insn), 0, i);
if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
/* Don't move a reg that has an explicit clobber.
It's not worth the pain to try to do it correctly. */
may_not_move[REGNO (XEXP (x, 0))] = 1;
if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
{
dest = SET_DEST (x);
while (GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT
|| GET_CODE (dest) == SIGN_EXTRACT
|| GET_CODE (dest) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
if (GET_CODE (dest) == REG)
{
register int regno = REGNO (dest);
if (n_times_set[regno] > 0 && last_set[regno] == 0)
may_not_move[regno] = 1;
if (last_set[regno] != 0
&& reg_used_between_p (dest, last_set[regno], insn))
may_not_move[regno] = 1;
if (n_times_set[regno] < 127)
++n_times_set[regno];
last_set[regno] = insn;
}
}
}
}
}
if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
bzero ((char *) last_set, nregs * sizeof (rtx));
}
*count_ptr = count;