#include "config.h"
#include "system.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"
#include "toplev.h"
int *uid_luid;
int *uid_loop_num;
int max_uid_for_loop;
static int max_luid;
static int max_loop_num;
static rtx *loop_number_loop_starts, *loop_number_loop_ends;
static rtx *loop_number_loop_cont;
static rtx *loop_number_cont_dominator;
int *loop_outer_loop;
#ifdef HAVE_decrement_and_branch_on_count
int *loop_used_count_register;
#endif
static char *loop_invalid;
rtx *loop_number_exit_labels;
int *loop_number_exit_count;
static int loop_has_call;
static int loop_has_volatile;
static int loop_has_tablejump;
static rtx loop_continue;
static varray_type set_in_loop;
static varray_type n_times_set;
static varray_type may_not_optimize;
static varray_type reg_single_usage;
static char *moved_once;
static rtx loop_store_mems;
static rtx first_loop_store_insn;
typedef struct loop_mem_info {
rtx mem;
rtx reg;
int optimize;
} loop_mem_info;
static loop_mem_info *loop_mems;
static int loop_mems_idx;
static int loop_mems_allocated;
static int unknown_address_altered;
static int num_movables;
static int num_mem_sets;
static int loops_enclosed;
int max_reg_before_loop;
static struct obstack temp_obstack;
extern struct obstack *rtl_obstack;
#define obstack_chunk_alloc xmalloc
#define obstack_chunk_free free
struct movable
{
rtx insn;
rtx set_src;
rtx set_dest;
rtx dependencies;
int consec;
int regno;
short lifetime;
short savings;
unsigned int cond : 1;
unsigned int force : 1;
unsigned int global : 1;
unsigned int done : 1;
unsigned int partial : 1;
unsigned int move_insn : 1;
unsigned int move_insn_first:1;
unsigned int is_equiv : 1;
enum machine_mode savemode;
struct movable *match;
struct movable *forces;
struct movable *next;
};
static struct movable *the_movables;
FILE *loop_dump_stream;
static int note_set_pseudo_multiple_uses_retval;
static void verify_dominator PROTO((int));
static void find_and_verify_loops PROTO((rtx));
static void mark_loop_jump PROTO((rtx, int));
static void prescan_loop PROTO((rtx, rtx));
static 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 void note_set_pseudo_multiple_uses PROTO((rtx, rtx));
static int loop_reg_used_before_p PROTO((rtx, rtx, rtx, rtx, rtx));
static void scan_loop PROTO((rtx, rtx, rtx, int, int));
#if 0
static void replace_call_address PROTO((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, rtx, int, int));
static void find_single_use_in_loop PROTO((rtx, rtx, varray_type));
static int valid_initial_value_p PROTO((rtx, rtx, int, rtx));
static void find_mem_givs PROTO((rtx, rtx, int, rtx, rtx));
static void record_biv PROTO((struct induction *, rtx, rtx, rtx, rtx, rtx *, int, int));
static void check_final_value PROTO((struct induction *, rtx, rtx,
unsigned HOST_WIDE_INT));
static void record_giv PROTO((struct induction *, rtx, rtx, rtx, rtx, rtx, int, enum g_types, int, rtx *, rtx, rtx));
static void 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 *));
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 *));
typedef struct rtx_and_int {
rtx r;
int i;
} rtx_and_int;
typedef struct rtx_pair {
rtx r1;
rtx r2;
} rtx_pair;
#define INSN_IN_RANGE_P(INSN, START, END) \
(INSN_UID (INSN) < max_uid_for_loop \
&& INSN_LUID (INSN) >= INSN_LUID (START) \
&& INSN_LUID (INSN) <= INSN_LUID (END))
#ifdef HAVE_decrement_and_branch_on_count
static void insert_bct PROTO((rtx, rtx, struct loop_info *));
static void instrument_loop_bct PROTO((rtx, rtx, rtx));
#endif
int indirect_jump_in_function = 0;
static int indirect_jump_in_function_p PROTO((rtx));
static int compute_luids PROTO((rtx, rtx, int));
static int biv_elimination_giv_has_0_offset PROTO((struct induction *,
struct induction *, rtx));
static int add_cost;
#if 0
static int shift_cost;
static int mult_cost;
#endif
static int copy_cost;
static int reg_address_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);
#ifdef ADDRESS_COST
reg_address_cost = ADDRESS_COST (reg);
#else
reg_address_cost = rtx_cost (reg, MEM);
#endif
copy_cost = 2 * 2;
obfree (free_point);
gcc_obstack_init (&temp_obstack);
}
static int
compute_luids (start, end, prev_luid)
rtx start, end;
int prev_luid;
{
int i;
rtx insn;
for (insn = start, i = prev_luid; insn != end; insn = NEXT_INSN (insn))
{
if (INSN_UID (insn) >= max_uid_for_loop)
continue;
if (GET_CODE (insn) != NOTE
|| NOTE_LINE_NUMBER (insn) <= 0)
uid_luid[INSN_UID (insn)] = ++i;
else
uid_luid[INSN_UID (insn)] = i;
}
return i + 1;
}
void
loop_optimize (f, dumpfile, unroll_p, bct_p)
rtx f;
FILE *dumpfile;
int unroll_p, bct_p;
{
register rtx insn;
register int i;
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);
regs_may_share = 0;
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++;
}
if (max_loop_num == 0)
return;
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));
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
loop_used_count_register = (int *) alloca (max_loop_num * sizeof (int));
bzero ((char *) loop_used_count_register, max_loop_num * sizeof (int));
#endif
find_and_verify_loops (f);
reg_scan (f, max_reg_num (), 1);
init_alias_analysis ();
if (get_max_uid () > max_uid_for_loop)
abort ();
max_uid_for_loop = get_max_uid ();
max_luid = compute_luids (f, NULL_RTX, 0);
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];
if (unroll_p && write_symbols != NO_DEBUG)
find_loop_tree_blocks ();
indirect_jump_in_function = indirect_jump_in_function_p (f);
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);
if (unroll_p && write_symbols != NO_DEBUG)
unroll_block_trees ();
end_alias_analysis ();
}
static rtx
next_insn_in_loop (insn, start, end, loop_top)
rtx insn;
rtx start;
rtx end;
rtx loop_top;
{
insn = NEXT_INSN (insn);
if (insn == end)
{
if (loop_top)
insn = loop_top;
else
insn = NULL_RTX;
}
if (insn == start)
insn = NULL_RTX;
return insn;
}
static void
scan_loop (loop_start, end, loop_cont, unroll_p, bct_p)
rtx loop_start, end, loop_cont;
int unroll_p, bct_p;
{
register int i;
rtx p;
int maybe_never = 0;
int call_passed = 0;
rtx loop_top = 0;
rtx loop_entry_jump = 0;
rtx scan_start;
int insn_count;
int in_libcall = 0;
int tem;
rtx temp;
rtx set, set1;
struct movable *movables = 0;
struct movable *last_movable = 0;
int threshold;
int loop_depth = 0;
int nregs;
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;
prescan_loop (loop_start, end);
threshold = (loop_has_call ? 1 : 2) * (1 + n_non_fixed_regs);
if (GET_CODE (p) == JUMP_INSN)
{
loop_entry_jump = p;
if (simplejump_p (p)
&& JUMP_LABEL (p) != 0
&& INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, end))
{
loop_top = next_label (scan_start);
scan_start = JUMP_LABEL (p);
}
}
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;
}
nregs = max_reg_num () + loop_mems_idx + 16;
VARRAY_INT_INIT (set_in_loop, nregs, "set_in_loop");
VARRAY_INT_INIT (n_times_set, nregs, "n_times_set");
VARRAY_CHAR_INIT (may_not_optimize, nregs, "may_not_optimize");
VARRAY_RTX_INIT (reg_single_usage, nregs, "reg_single_usage");
count_loop_regs_set (loop_top ? loop_top : loop_start, end,
may_not_optimize, reg_single_usage, &insn_count, nregs);
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
for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
VARRAY_CHAR (may_not_optimize, i) = 1;
#endif
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_continue)
fprintf (loop_dump_stream, "Continue at insn %d.\n",
INSN_UID (loop_continue));
}
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 (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
&& ! VARRAY_CHAR (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;
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);
dependencies = libcall_other_reg (p, src);
}
}
if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
;
else if (
! reg_in_basic_block_p (p, SET_DEST (set))
&& (maybe_never
|| loop_reg_used_before_p (set, p, loop_start,
scan_start, end)))
;
else if ((tem = invariant_p (src))
&& (dependencies == 0
|| (tem2 = invariant_p (dependencies)) != 0)
&& (VARRAY_INT (set_in_loop,
REGNO (SET_DEST (set))) == 1
|| (tem1
= consec_sets_invariant_p
(SET_DEST (set),
VARRAY_INT (set_in_loop, REGNO (SET_DEST (set))),
p)))
&& ! ((maybe_never || call_passed)
&& may_trap_p (src)))
{
register struct movable *m;
register int regno = REGNO (SET_DEST (set));
if (loop_has_call
&& VARRAY_RTX (reg_single_usage, regno) != 0
&& VARRAY_RTX (reg_single_usage, regno) != const0_rtx
&& REGNO_FIRST_UID (regno) == INSN_UID (p)
&& (REGNO_LAST_UID (regno)
== INSN_UID (VARRAY_RTX (reg_single_usage, regno)))
&& VARRAY_INT (set_in_loop, regno) == 1
&& ! side_effects_p (SET_SRC (set))
&& ! find_reg_note (p, REG_RETVAL, NULL_RTX)
&& (! SMALL_REGISTER_CLASSES
|| (! (GET_CODE (SET_SRC (set)) == REG
&& REGNO (SET_SRC (set)) < FIRST_PSEUDO_REGISTER)))
&& ! modified_between_p (SET_SRC (set), p,
VARRAY_RTX
(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_NOTES (VARRAY_RTX (reg_single_usage, regno))
= replace_rtx (REG_NOTES (VARRAY_RTX
(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;
VARRAY_INT (set_in_loop, 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 = VARRAY_INT (set_in_loop,
REGNO (SET_DEST (set))) - 1;
m->done = 0;
m->forces = 0;
m->partial = 0;
m->move_insn = move_insn;
m->move_insn_first = 0;
m->is_equiv = (find_reg_note (p, REG_EQUIV, NULL_RTX) != 0);
m->savemode = VOIDmode;
m->regno = regno;
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 = VARRAY_INT (n_times_set, regno);
if (find_reg_note (p, REG_RETVAL, NULL_RTX))
m->savings += libcall_benefit (p);
VARRAY_INT (set_in_loop, regno) = move_insn ? -2 : -1;
if (movables == 0)
movables = m;
else
last_movable->next = m;
last_movable = m;
if (m->consec > 0)
{
m->move_insn_first = m->move_insn;
p = next_nonnote_insn (p);
p = skip_consec_insns (p, m->consec);
p = prev_nonnote_insn (p);
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);
}
}
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 (VARRAY_INT (set_in_loop, 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->move_insn_first = 0;
m->partial = 1;
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;
VARRAY_INT (set_in_loop, regno) = -1;
if (movables == 0)
movables = m;
else
last_movable->next = m;
last_movable = m;
}
}
}
else if (GET_CODE (p) == CALL_INSN && ! in_libcall)
call_passed = 1;
else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
&& ! (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)
{
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--;
}
}
ignore_some_movables (movables);
force_movables (movables);
combine_movables (movables, nregs);
if (! optimize_size)
move_movables (movables, threshold,
insn_count, loop_start, end, nregs);
for (i = 0; i < nregs; i++)
if (VARRAY_INT (set_in_loop, i) < 0)
VARRAY_INT (set_in_loop, i) = VARRAY_INT (n_times_set, i);
load_mems_and_recount_loop_regs_set (scan_start, end, loop_top,
loop_start, &insn_count);
if (flag_strength_reduce)
{
the_movables = movables;
strength_reduce (scan_start, end, loop_top,
insn_count, loop_start, end, loop_cont, unroll_p, bct_p);
}
VARRAY_FREE (reg_single_usage);
VARRAY_FREE (set_in_loop);
VARRAY_FREE (n_times_set);
VARRAY_FREE (may_not_optimize);
}
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;
default:
break;
}
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;
}
}
}
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;
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;
}
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;
for (p = insn; p; p = NEXT_INSN (p))
{
switch (GET_CODE (p))
{
case NOTE:
break;
case INSN:
case CALL_INSN:
if (REGNO_LAST_UID (regno) == INSN_UID (p))
return 1;
break;
case JUMP_INSN:
if (REGNO_LAST_UID (regno) == INSN_UID (p))
return 1;
return 0;
case CODE_LABEL:
case BARRIER:
return 0;
default:
break;
}
}
abort ();
}
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;
else if (GET_CODE (insn) == INSN
&& GET_CODE (PATTERN (insn)) != USE
&& GET_CODE (PATTERN (insn)) != CLOBBER)
benefit++;
}
return benefit;
}
static rtx
skip_consec_insns (insn, count)
rtx insn;
int count;
{
for (; count > 0; count--)
{
rtx temp;
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;
}
static void
ignore_some_movables (movables)
struct movable *movables;
{
register struct movable *m, *m1;
for (m = movables; m; m = m->next)
{
rtx note = find_reg_note (m->insn, REG_RETVAL, NULL_RTX);
if (note)
{
rtx insn;
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;
}
}
}
static void
force_movables (movables)
struct movable *movables;
{
register struct movable *m, *m1;
for (m1 = movables; m1; m1 = m1->next)
if (!m1->partial && !m1->done)
{
int regno = m1->regno;
for (m = m1->next; m; m = m->next)
if (INSN_UID (m->insn) == REGNO_LAST_UID (regno)
&& !m->done)
break;
if (m != 0 && m->set_src == m1->set_dest
&& m->consec == 0)
m = 0;
if (m != 0)
{
m->forces = m1;
m1->lifetime += m->lifetime;
m1->savings += m->savings;
}
}
}
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;
for (m = movables; m; m = m->next)
if (m->match == 0 && VARRAY_INT (n_times_set, m->regno) == 1 && !m->partial)
{
register struct movable *m1;
int regno = m->regno;
bzero (matched_regs, nregs);
matched_regs[regno] = 1;
for (m1 = m->next; m1; m1 = m1->next)
if (m != m1 && m1->match == 0 && VARRAY_INT (n_times_set, m1->regno) == 1
&& !m1->global
&& !m1->partial
&& (matched_regs[m1->regno]
||
(
(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)))))
&& ((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;
}
}
for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
mode = GET_MODE_WIDER_MODE (mode))
{
register struct movable *m0 = 0;
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)
{
m0 = m;
continue;
}
if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
continue;
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;
m0->lifetime += m->lifetime;
m0->savings += m->savings;
m->done = 1;
m->match = m0;
overlap: ;
}
}
}
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));
}
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 (GET_CODE (x) == REG && VARRAY_INT (set_in_loop, 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 && VARRAY_INT (set_in_loop, 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;
}
if (code != GET_CODE (y))
return 0;
if (GET_MODE (x) != GET_MODE (y))
return 0;
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);
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':
if (XVECLEN (x, i) != XVECLEN (y, i))
return 0;
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':
break;
case '0':
break;
default:
abort ();
}
}
return 1;
}
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))
{
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));
}
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);
}
}
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;
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)
{
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));
}
num_movables++;
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;
p = m->insn;
regno = m->regno;
if (loop_dump_stream)
fprintf (loop_dump_stream, "savings %d ", savings);
if (moved_once[regno] && loop_dump_stream)
fprintf (loop_dump_stream, "halved since already moved ");
if (already_moved[regno]
|| flag_move_all_movables
|| (threshold * savings * m->lifetime) >=
(moved_once[regno] ? insn_count * 2 : insn_count)
|| (m->forces && m->forces->done
&& VARRAY_INT (n_times_set, m->forces->regno) == 1))
{
int count;
register struct movable *m1;
rtx first;
if (m->partial && m->match)
{
rtx newpat, i1;
rtx r1, r2;
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);
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));
}
else if (m->move_insn)
{
rtx i1, temp;
for (count = m->consec; count >= 0; count--)
{
if (GET_CODE (p) != NOTE
&& (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
p = XEXP (temp, 0);
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);
}
temp = p;
p = delete_insn (p);
while (p && GET_CODE (p) == NOTE)
p = NEXT_INSN (temp) = 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));
threshold -= 3;
}
else
{
for (count = m->consec; count >= 0; count--)
{
rtx i1, temp;
if (GET_CODE (p) != NOTE
&& (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
p = XEXP (temp, 0);
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);
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 (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;
}
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);
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 (new_start == 0)
new_start = first;
}
if (m->savemode != VOIDmode)
{
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);
if (CALL_INSN_FUNCTION_USAGE (p))
CALL_INSN_FUNCTION_USAGE (i1)
= copy_rtx (CALL_INSN_FUNCTION_USAGE (p));
}
else if (count == m->consec && m->move_insn_first)
{
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));
}
else
i1 = emit_insn_before (PATTERN (p), loop_start);
if (REG_NOTES (i1) == 0)
{
REG_NOTES (i1) = REG_NOTES (p);
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 ((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;
}
temp = p;
delete_insn (p);
p = NEXT_INSN (p);
while (p && GET_CODE (p) == NOTE)
p = NEXT_INSN (temp) = NEXT_INSN (p);
}
threshold -= 3;
}
already_moved[regno] = 1;
moved_once[regno] = 1;
if (! m->partial)
VARRAY_INT (set_in_loop, regno) = 0;
m->done = 1;
if (uid_luid[REGNO_FIRST_UID (regno)] > INSN_LUID (loop_start))
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 (! m->partial)
for (m1 = movables; m1; m1 = m1->next)
if (m1->match == m)
{
rtx temp;
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);
m1->done = 1;
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);
already_moved[m1->regno] = 1;
if (! m->partial)
VARRAY_INT (set_in_loop, 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;
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
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:
replace_call_address (XEXP (x, 1), reg, addr);
return;
case CALL:
replace_call_address (XEXP (x, 0), reg, addr);
return;
case MEM:
if (XEXP (x, 0) != reg)
abort ();
XEXP (x, 0) = addr;
return;
default:
break;
}
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
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)));
default:
break;
}
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
static void
constant_high_bytes (p, loop_start)
rtx p, loop_start;
{
register rtx new;
register int insn_code_number;
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;
emit_insn_before (gen_rtx_SET (VOIDmode, SET_DEST (PATTERN (p)),
const0_rtx),
loop_start);
PATTERN (p) = new;
}
}
#endif
static void
prescan_loop (start, end)
rtx start, end;
{
register int level = 1;
rtx insn;
int loop_has_multiple_exit_targets = 0;
rtx exit_target = next_nonnote_insn (end);
if (exit_target == NULL_RTX || GET_CODE (exit_target) != CODE_LABEL)
loop_has_multiple_exit_targets = 1;
unknown_address_altered = 0;
loop_has_call = 0;
loop_has_volatile = 0;
loop_has_tablejump = 0;
loop_store_mems = NULL_RTX;
first_loop_store_insn = NULL_RTX;
loop_mems_idx = 0;
num_mem_sets = 0;
loops_enclosed = 1;
loop_continue = 0;
for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) == NOTE)
{
if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
{
++level;
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)
{
if (! CONST_CALL_P (insn))
unknown_address_altered = 1;
loop_has_call = 1;
}
else if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
{
rtx label1 = NULL_RTX;
rtx label2 = NULL_RTX;
if (volatile_refs_p (PATTERN (insn)))
loop_has_volatile = 1;
if (GET_CODE (insn) == JUMP_INSN
&& (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_VEC))
loop_has_tablejump = 1;
note_stores (PATTERN (insn), note_addr_stored);
if (! first_loop_store_insn && loop_store_mems)
first_loop_store_insn = insn;
if (! loop_has_multiple_exit_targets
&& GET_CODE (insn) == JUMP_INSN
&& GET_CODE (PATTERN (insn)) == SET
&& SET_DEST (PATTERN (insn)) == pc_rtx)
{
if (GET_CODE (SET_SRC (PATTERN (insn))) == IF_THEN_ELSE)
{
label1 = XEXP (SET_SRC (PATTERN (insn)), 1);
label2 = XEXP (SET_SRC (PATTERN (insn)), 2);
}
else
{
label1 = SET_SRC (PATTERN (insn));
}
do {
if (label1 && label1 != pc_rtx)
{
if (GET_CODE (label1) != LABEL_REF)
{
loop_has_multiple_exit_targets = 1;
break;
}
else if (XEXP (label1, 0) != exit_target
&& LABEL_OUTSIDE_LOOP_P (label1))
{
loop_has_multiple_exit_targets = 1;
break;
}
}
label1 = label2;
label2 = NULL_RTX;
} while (label1);
}
}
else if (GET_CODE (insn) == RETURN)
loop_has_multiple_exit_targets = 1;
}
if (
!unknown_address_altered
&& !loop_has_call
&& !current_function_calls_alloca
&& !loop_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);
}
static void
verify_dominator (loop_number)
int loop_number;
{
rtx insn;
if (! loop_number_cont_dominator[loop_number])
return;
if (loop_number_cont_dominator[loop_number] == const0_rtx)
{
loop_number_cont_dominator[loop_number] = 0;
return;
}
for (insn = loop_number_loop_starts[loop_number];
insn != loop_number_cont_dominator[loop_number];
insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) == JUMP_INSN
&& GET_CODE (PATTERN (insn)) != RETURN)
{
rtx label = JUMP_LABEL (insn);
int label_luid;
if ((! condjump_p (insn)
&& ! condjump_in_parallel_p (insn))
|| label == NULL_RTX)
{
loop_number_cont_dominator[loop_number] = NULL_RTX;
return;
}
label_luid = INSN_LUID (label);
if (label_luid < INSN_LUID (loop_number_loop_cont[loop_number])
&& (label_luid
> INSN_LUID (loop_number_cont_dominator[loop_number])))
loop_number_cont_dominator[loop_number] = label;
}
}
}
static void
find_and_verify_loops (f)
rtx f;
{
rtx insn, label;
int current_loop = -1;
int next_loop = -1;
int loop;
compute_luids (f, NULL_RTX, 0);
uid_loop_num[0] = -1;
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;
current_loop = next_loop;
break;
case NOTE_INSN_SETJMP:
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_CONT:
loop_number_loop_cont[current_loop] = insn;
break;
case NOTE_INSN_LOOP_END:
if (current_loop == -1)
abort ();
loop_number_loop_ends[current_loop] = insn;
verify_dominator (current_loop);
current_loop = loop_outer_loop[current_loop];
break;
default:
break;
}
else if (GET_CODE (insn) == JUMP_INSN
&& GET_CODE (PATTERN (insn)) != RETURN
&& current_loop >= 0)
{
int this_loop;
rtx label = JUMP_LABEL (insn);
if (! condjump_p (insn) && ! condjump_in_parallel_p (insn))
label = NULL_RTX;
this_loop = current_loop;
do
{
if (loop_number_loop_cont[this_loop]
&& loop_number_cont_dominator[this_loop] != const0_rtx)
{
if (! label)
loop_number_cont_dominator[this_loop] = const0_rtx;
else
if ((INSN_LUID (label)
< INSN_LUID (loop_number_loop_cont[this_loop]))
&& (INSN_LUID (label)
> INSN_LUID (loop_number_loop_starts[this_loop]))
&& (! loop_number_cont_dominator[this_loop]
|| (INSN_LUID (label)
> INSN_LUID (loop_number_cont_dominator
[this_loop]))))
loop_number_cont_dominator[this_loop] = label;
}
this_loop = loop_outer_loop[this_loop];
}
while (this_loop >= 0);
}
uid_loop_num[INSN_UID (insn)] = current_loop;
}
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 (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 (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);
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;
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))
;
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;
}
}
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 (outer_loop == -1
&& GET_CODE (p) == JUMP_INSN
&& JUMP_LABEL (p) != 0
&& 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);
LABEL_NUSES (cond_label)++;
if (invert_jump (p, new_label))
{
rtx q, r;
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);
}
new_label = squeeze_notes (new_label, NEXT_INSN (insn));
reorder_insns (new_label, NEXT_INSN (insn), loc);
for (q = new_label; q != NEXT_INSN (NEXT_INSN (insn));
q = NEXT_INSN (q))
uid_loop_num[INSN_UID (q)] = target_loop_num;
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 (! r)
abort ();
}
mark_loop_jump (PATTERN (p), this_loop_num);
if (JUMP_LABEL (insn) != 0
&& (next_real_insn (JUMP_LABEL (insn))
== next_real_insn (insn)))
delete_insn (insn);
}
insn = NEXT_INSN (cond_label);
if (--LABEL_NUSES (cond_label) == 0)
delete_insn (cond_label);
insn = PREV_INSN (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:
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 LO_SUM:
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))];
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 (dest_loop == -1)
return;
for (; dest_loop != -1; dest_loop = loop_outer_loop[dest_loop])
{
for (outer_loop = loop_num; outer_loop != -1;
outer_loop = loop_outer_loop[outer_loop])
if (dest_loop == outer_loop)
return;
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 (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:
if (loop_num != -1)
{
for (outer_loop = loop_num; outer_loop != -1;
outer_loop = loop_outer_loop[outer_loop])
{
if (loop_dump_stream && ! loop_invalid[outer_loop])
fprintf (loop_dump_stream,
"\nLoop at %d ignored due to unknown exit jump.\n",
INSN_UID (loop_number_loop_starts[outer_loop]));
loop_invalid[outer_loop] = 1;
}
}
return;
}
}
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;
}
static void
note_addr_stored (x, y)
rtx x;
rtx y ATTRIBUTE_UNUSED;
{
if (x == 0 || GET_CODE (x) != MEM)
return;
num_mem_sets++;
if (GET_MODE (x) == BLKmode)
unknown_address_altered = 1;
if (unknown_address_altered)
return;
loop_store_mems = gen_rtx_EXPR_LIST (VOIDmode, x, loop_store_mems);
}
static void
note_set_pseudo_multiple_uses (x, y)
rtx x;
rtx y ATTRIBUTE_UNUSED;
{
if (x == 0)
return;
while (GET_CODE (x) == STRICT_LOW_PART
|| GET_CODE (x) == SIGN_EXTRACT
|| GET_CODE (x) == ZERO_EXTRACT
|| GET_CODE (x) == SUBREG)
x = XEXP (x, 0);
if (GET_CODE (x) != REG || REGNO (x) < FIRST_PSEUDO_REGISTER)
return;
if (REGNO (x) >= max_reg_before_loop
|| ! VARRAY_RTX (reg_single_usage, REGNO (x))
|| VARRAY_RTX (reg_single_usage, REGNO (x)) == const0_rtx)
note_set_pseudo_multiple_uses_retval = 1;
}
int
invariant_p (x)
register rtx x;
{
register int i;
register enum rtx_code code;
register char *fmt;
int conditional = 0;
rtx mem_list_entry;
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:
if (flag_unroll_loops)
return 0;
else
return 1;
case PC:
case CC0:
case UNSPEC_VOLATILE:
return 0;
case REG:
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 (VARRAY_INT (set_in_loop, REGNO (x)) < 0)
return 2;
return VARRAY_INT (set_in_loop, REGNO (x)) == 0;
case MEM:
if (MEM_VOLATILE_P (x))
return 0;
if (RTX_UNCHANGING_P (x))
break;
if (unknown_address_altered)
return 0;
mem_list_entry = loop_store_mems;
while (mem_list_entry)
{
if (true_dependence (XEXP (mem_list_entry, 0), VOIDmode,
x, rtx_varies_p))
return 0;
mem_list_entry = XEXP (mem_list_entry, 1);
}
break;
case ASM_OPERANDS:
if (MEM_VOLATILE_P (x))
return 0;
break;
default:
break;
}
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;
}
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;
int count = n_sets - 1;
int old = VARRAY_INT (set_in_loop, regno);
int value = 0;
int this;
if (n_sets == 127)
return 0;
VARRAY_INT (set_in_loop, regno) = 0;
while (count > 0)
{
register enum rtx_code code;
rtx set;
p = NEXT_INSN (p);
code = GET_CODE (p);
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)))
{
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)
{
VARRAY_INT (set_in_loop, regno) = old;
return 0;
}
}
VARRAY_INT (set_in_loop, regno) = old;
return 1 + (value & 2);
}
#if 0
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
static void
find_single_use_in_loop (insn, x, usage)
rtx insn;
rtx x;
varray_type usage;
{
enum rtx_code code = GET_CODE (x);
char *fmt = GET_RTX_FORMAT (code);
int i, j;
if (code == REG)
VARRAY_RTX (usage, REGNO (x))
= (VARRAY_RTX (usage, REGNO (x)) != 0
&& VARRAY_RTX (usage, REGNO (x)) != insn)
? const0_rtx : insn;
else if (code == SET)
{
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);
}
}
static void
count_one_set (insn, x, may_not_move, last_set)
rtx insn, x;
varray_type may_not_move;
rtx *last_set;
{
if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
VARRAY_CHAR (may_not_move, REGNO (XEXP (x, 0))) = 1;
if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
{
rtx 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 (VARRAY_INT (set_in_loop, regno) > 0
&& last_set[regno] == 0)
VARRAY_CHAR (may_not_move, regno) = 1;
if (last_set[regno] != 0
&& reg_used_between_p (dest, last_set[regno], insn))
VARRAY_CHAR (may_not_move, regno) = 1;
if (VARRAY_INT (set_in_loop, regno) < 127)
++VARRAY_INT (set_in_loop, regno);
last_set[regno] = insn;
}
}
}
static void
count_loop_regs_set (from, to, may_not_move, single_usage, count_ptr, nregs)
register rtx from, to;
varray_type may_not_move;
varray_type single_usage;
int *count_ptr;
int nregs;
{
register rtx *last_set = (rtx *) alloca (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')
{
++count;
find_single_use_in_loop (insn, PATTERN (insn), single_usage);
if (REG_NOTES (insn))
find_single_use_in_loop (insn, REG_NOTES (insn), single_usage);
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
count_one_set (insn, PATTERN (insn), may_not_move, last_set);
else if (GET_CODE (PATTERN (insn)) == PARALLEL)
{
register int i;
for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
count_one_set (insn, XVECEXP (PATTERN (insn), 0, i),
may_not_move, last_set);
}
}
if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
bzero ((char *) last_set, nregs * sizeof (rtx));
}
*count_ptr = count;
}
static int
loop_reg_used_before_p (set, insn, loop_start, scan_start, loop_end)
rtx set, insn, loop_start, scan_start, loop_end;
{
rtx reg = SET_DEST (set);
rtx p;
for (p = scan_start; p != insn; p = NEXT_INSN (p))
{
if (GET_RTX_CLASS (GET_CODE (p)) == 'i'
&& reg_overlap_mentioned_p (reg, PATTERN (p)))
return 1;
if (p == loop_end)
p = loop_start;
}
return 0;
}
varray_type reg_iv_type;
varray_type reg_iv_info;
struct iv_class **reg_biv_class;
struct iv_class *loop_iv_list;
int first_increment_giv, last_increment_giv;
static rtx note_insn;
static rtx addr_placeholder;
static void
strength_reduce (scan_start, end, loop_top, insn_count,
loop_start, loop_end, loop_cont, unroll_p, bct_p)
rtx scan_start;
rtx end;
rtx loop_top;
int insn_count;
rtx loop_start;
rtx loop_end;
rtx loop_cont;
int unroll_p, bct_p ATTRIBUTE_UNUSED;
{
rtx p;
rtx set;
rtx inc_val;
rtx mult_val;
rtx dest_reg;
rtx *location;
int not_every_iteration = 0;
int maybe_multiple = 0;
int past_loop_latch = 0;
struct iv_class *bl, **backbl;
int threshold = (loop_has_call ? 1 : 2) * (3 + n_non_fixed_regs);
rtx *reg_map;
int reg_map_size;
int call_seen;
rtx test;
rtx end_insert_before;
int loop_depth = 0;
int n_extra_increment;
struct loop_info loop_iteration_info;
struct loop_info *loop_info = &loop_iteration_info;
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);
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 (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 (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))
{
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;
}
}
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
&& ! loop_insn_first_p (p, JUMP_LABEL (insn)))))
{
maybe_multiple = 1;
break;
}
}
}
if (GET_CODE (p) == JUMP_INSN
&& ! (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;
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)
{
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--;
}
if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == NEXT_INSN (loop_start))
past_loop_latch = 1;
if (not_every_iteration
&& ! past_loop_latch
&& GET_CODE (p) == CODE_LABEL
&& no_labels_between_p (p, loop_end)
&& loop_insn_first_p (p, loop_cont))
not_every_iteration = 0;
}
for (backbl = &loop_iv_list, bl = *backbl; bl; bl = bl->next)
{
if (REG_IV_TYPE (bl->regno) != BASIC_INDUCT
|| VARRAY_INT (n_times_set, bl->regno) != bl->biv_count
|| ! bl->incremented)
{
if (loop_dump_stream)
fprintf (loop_dump_stream, "Reg %d: biv discarded, %s\n",
bl->regno,
(REG_IV_TYPE (bl->regno) != BASIC_INDUCT
? "not induction variable"
: (! bl->incremented ? "never incremented"
: "count error")));
REG_IV_TYPE (bl->regno) = NOT_BASIC_INDUCT;
*backbl = bl->next;
}
else
{
backbl = &bl->next;
if (loop_dump_stream)
fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno);
}
}
if (! loop_iv_list)
{
if (unroll_p)
unroll_loop (loop_end, insn_count, loop_start, end_insert_before,
loop_info, 0);
return;
}
call_seen = 0;
for (p = loop_start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
{
note_insn = p;
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 (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
&& GET_CODE (XEXP (test, 0)) == REG
&& REGNO (XEXP (test, 0)) < max_reg_before_loop
&& (bl = reg_biv_class[REGNO (XEXP (test, 0))]) != 0
&& valid_initial_value_p (XEXP (test, 1), p, call_seen, loop_start)
&& bl->init_insn == 0)
{
if (GET_CODE (test) == NE)
{
bl->init_insn = p;
bl->init_set = gen_rtx_SET (VOIDmode,
XEXP (test, 0), XEXP (test, 1));
}
else
bl->initial_test = test;
}
}
for (backbl = &loop_iv_list; (bl = *backbl); backbl = &bl->next)
{
rtx src;
rtx note;
if (! bl->init_insn)
continue;
if (((note = find_reg_note (bl->init_insn, REG_EQUAL, 0)) != NULL
&& CONSTANT_P (XEXP (note, 0)))
|| ((note = find_reg_note (bl->init_insn, REG_EQUIV, 0)) != NULL
&& CONSTANT_P (XEXP (note, 0))))
src = XEXP (note, 0);
else
src = SET_SRC (bl->init_set);
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Biv %d initialized at insn %d: initial value ",
bl->regno, INSN_UID (bl->init_insn));
if ((GET_MODE (src) == GET_MODE (regno_reg_rtx[bl->regno])
|| GET_MODE (src) == VOIDmode)
&& valid_initial_value_p (src, bl->init_insn, call_seen, loop_start))
{
bl->initial_value = src;
if (loop_dump_stream)
{
if (GET_CODE (src) == CONST_INT)
{
fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (src));
fputc ('\n', loop_dump_stream);
}
else
{
print_rtl (loop_dump_stream, src);
fprintf (loop_dump_stream, "\n");
}
}
}
else
{
struct iv_class *bl2 = 0;
rtx increment;
if (bl->biv_count == 1
&& bl->regno < max_reg_before_loop
&& uid_luid[REGNO_LAST_UID (bl->regno)] < INSN_LUID (loop_end)
&& 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))
{
int regno = REGNO (XEXP (src, 0));
for (bl2 = loop_iv_list; bl2; bl2 = bl2->next)
if (bl2->regno == regno)
break;
}
if (bl2
&& bl2->biv_count == 1
&& rtx_equal_p (increment,
biv_total_increment (bl2, loop_start, loop_end))
&& ! reg_set_between_p (bl2->biv->src_reg,
PREV_INSN (bl->init_insn), loop_start)
&& ((loop_insn_first_p (bl2->biv->insn, bl->biv->insn)
&& no_labels_between_p (bl2->biv->insn, bl->biv->insn))
|| (! reg_used_between_p (bl->biv->src_reg, bl->biv->insn,
bl2->biv->insn)
&& no_jumps_between_p (bl->biv->insn, bl2->biv->insn)))
&& validate_change (bl->biv->insn,
&SET_SRC (single_set (bl->biv->insn)),
copy_rtx (src), 0))
{
int loop_num = uid_loop_num[INSN_UID (loop_start)];
rtx dominator = loop_number_cont_dominator[loop_num];
rtx giv = bl->biv->src_reg;
rtx giv_insn = bl->biv->insn;
rtx after_giv = NEXT_INSN (giv_insn);
if (loop_dump_stream)
fprintf (loop_dump_stream, "is giv of biv %d\n", bl2->regno);
REG_IV_TYPE (bl->regno) = UNKNOWN_INDUCT;
if (dominator
&& ! loop_insn_first_p (dominator, scan_start)
&& ! reg_set_between_p (bl2->biv->src_reg, loop_start,
dominator)
&& ! reg_used_between_p (giv, loop_start, dominator)
&& ! reg_used_between_p (giv, giv_insn, loop_end))
{
rtx p;
rtx 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)
break;
#ifdef HAVE_cc0
if (GET_RTX_CLASS (GET_CODE (next)) != 'i'
|| ! sets_cc0_p (PATTERN (next)))
#endif
dominator = next;
}
if (loop_dump_stream)
fprintf (loop_dump_stream, "move after insn %d\n",
INSN_UID (dominator));
reorder_insns (giv_insn, giv_insn, dominator);
for (p = dominator; INSN_UID (p) >= max_uid_for_loop; )
p = PREV_INSN (p);
compute_luids (giv_insn, after_giv, INSN_LUID (p));
if (single_set (bl->init_insn)
&& ! reg_used_between_p (giv, bl->init_insn, loop_start))
delete_insn (bl->init_insn);
}
else if (! loop_insn_first_p (bl2->biv->insn, bl->biv->insn))
{
rtx p = PREV_INSN (giv_insn);
while (INSN_UID (p) >= max_uid_for_loop)
p = PREV_INSN (p);
reorder_insns (giv_insn, giv_insn, bl2->biv->insn);
compute_luids (after_giv, NEXT_INSN (giv_insn),
INSN_LUID (p));
}
if (bl->next)
*bl = *bl->next;
else
{
*backbl = 0;
break;
}
}
else if (loop_dump_stream)
fprintf (loop_dump_stream, "is complex\n");
}
}
first_increment_giv = max_reg_num ();
for (n_extra_increment = 0, bl = loop_iv_list; bl; bl = bl->next)
n_extra_increment += bl->biv_count - 1;
if (0 && n_extra_increment && ! loop_has_volatile)
{
int nregs = first_increment_giv + n_extra_increment;
VARRAY_GROW (reg_iv_type, nregs);
VARRAY_GROW (reg_iv_info, nregs);
for (bl = loop_iv_list; bl; bl = bl->next)
{
struct induction **vp, *v, *next;
int biv_dead_after_loop = 0;
for (v = bl->biv, bl->biv = 0; v; v = next)
{
next = v->next_iv;
v->next_iv = bl->biv;
bl->biv = v;
}
if (uid_luid[REGNO_LAST_UID (bl->regno)] < INSN_LUID (loop_end)
&& bl->init_insn
&& INSN_UID (bl->init_insn) < max_uid_for_loop
&& (uid_luid[REGNO_FIRST_UID (bl->regno)]
>= INSN_LUID (bl->init_insn))
#ifdef HAVE_decrement_and_branch_until_zero
&& ! bl->nonneg
#endif
&& ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
biv_dead_after_loop = 1;
for (vp = &bl->biv, next = *vp; v = next, next = v->next_iv;)
{
HOST_WIDE_INT offset;
rtx set, add_val, old_reg, dest_reg, last_use_insn;
int old_regno, new_regno;
if (! v->always_executed
|| v->maybe_multiple
|| GET_CODE (v->add_val) != CONST_INT
|| ! next->always_executed
|| next->maybe_multiple
|| ! CONSTANT_P (next->add_val)
|| v->mult_val != const1_rtx
|| next->mult_val != const1_rtx
|| ! (biv_dead_after_loop
|| no_jumps_between_p (v->insn, next->insn)))
{
vp = &v->next_iv;
continue;
}
offset = INTVAL (v->add_val);
set = single_set (v->insn);
add_val = plus_constant (next->add_val, offset);
old_reg = v->dest_reg;
dest_reg = gen_reg_rtx (v->mode);
if ((unsigned) max_reg_num () > n_times_set->num_elements)
{
VARRAY_GROW (set_in_loop, nregs);
VARRAY_GROW (n_times_set, nregs);
VARRAY_GROW (may_not_optimize, nregs);
VARRAY_GROW (reg_single_usage, nregs);
}
if (! validate_change (next->insn, next->location, add_val, 0))
{
vp = &v->next_iv;
continue;
}
for (last_use_insn = v->insn, p = NEXT_INSN (v->insn);
p != next->insn;
p = next_insn_in_loop (p, scan_start, end, loop_top))
{
if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
continue;
if (reg_mentioned_p (old_reg, PATTERN (p)))
{
last_use_insn = p;
}
}
if (INSN_UID (v->insn) >= max_uid_for_loop
|| INSN_UID (last_use_insn) >= max_uid_for_loop
|| ! validate_change (v->insn, &SET_DEST (set), dest_reg, 0))
{
if (! validate_change (next->insn, next->location,
next->add_val, 0))
abort ();
vp = &v->next_iv;
continue;
}
next->add_val = add_val;
v->dest_reg = dest_reg;
v->giv_type = DEST_REG;
v->location = &SET_SRC (set);
v->cant_derive = 0;
v->combined_with = 0;
v->maybe_dead = 0;
v->derive_adjustment = 0;
v->same = 0;
v->ignore = 0;
v->new_reg = 0;
v->final_value = 0;
v->same_insn = 0;
v->auto_inc_opt = 0;
v->unrolled = 0;
v->shared = 0;
v->derived_from = 0;
v->always_computable = 1;
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 (set_in_loop, new_regno) = 1;
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;
*vp = next;
bl->biv_count--;
v->next_iv = bl->giv;
bl->giv = v;
bl->giv_count++;
v->benefit = rtx_cost (SET_SRC (set), SET);
bl->total_benefit += v->benefit;
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))
{
rtx note;
if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
continue;
if (reg_mentioned_p (old_reg, PATTERN (p)))
{
last_use_insn = p;
if (! validate_replace_rtx (old_reg, dest_reg, p))
abort ();
}
for (note = REG_NOTES (p); note; note = XEXP (note, 1))
{
if (GET_CODE (note) == EXPR_LIST)
XEXP (note, 0)
= 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);
if (v->lifetime == 0)
v->ignore = 1;
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Increment %d of biv %d converted to giv %d.\n\n",
INSN_UID (v->insn), old_regno, new_regno);
}
}
}
last_increment_giv = max_reg_num () - 1;
not_every_iteration = 0;
loop_depth = 0;
p = scan_start;
while (1)
{
p = NEXT_INSN (p);
if (p == scan_start)
break;
if (p == end)
{
if (loop_top != 0)
p = loop_top;
else
break;
if (p == scan_start)
break;
}
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 (
(general_induction_var (SET_SRC (set), &src_reg, &add_val,
&mult_val, 0, &benefit)
|| ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
&& general_induction_var (XEXP (regnote, 0), &src_reg,
&add_val, &mult_val, 0,
&benefit)))
&& REGNO (dest_reg) < max_reg_before_loop
&& dest_reg != src_reg
&& (VARRAY_INT (n_times_set, REGNO (dest_reg)) == 1
|| (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 (find_reg_note (p, REG_RETVAL, NULL_RTX))
benefit += libcall_benefit (p);
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, NULL_PTR, loop_start,
loop_end);
}
}
#ifndef DONT_REDUCE_ADDR
if (GET_CODE (p) == INSN)
find_mem_givs (PATTERN (p), p, not_every_iteration, loop_start,
loop_end);
#endif
if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
|| GET_CODE (p) == CODE_LABEL)
update_giv_derive (p);
if (GET_CODE (p) == JUMP_INSN
&& ! (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;
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)
{
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--;
}
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;
}
loop_iterations (loop_start, loop_end, loop_info);
for (bl = loop_iv_list; bl; bl = bl->next)
{
struct induction *v;
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_dbra_loop (loop_end, insn_count, loop_start, loop_info);
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));
for (bl = loop_iv_list; bl; bl = bl->next)
{
struct induction *v;
int benefit;
int all_reduced;
rtx final_value = 0;
unsigned nregs;
if ((uid_luid[REGNO_LAST_UID (bl->regno)] < INSN_LUID (loop_end)
&& bl->init_insn
&& INSN_UID (bl->init_insn) < max_uid_for_loop
&& uid_luid[REGNO_FIRST_UID (bl->regno)] >= INSN_LUID (bl->init_insn)
#ifdef HAVE_decrement_and_branch_until_zero
&& ! bl->nonneg
#endif
&& ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
|| ((final_value = final_biv_value (bl, loop_start, loop_end,
loop_info->n_iterations))
#ifdef HAVE_decrement_and_branch_until_zero
&& ! bl->nonneg
#endif
))
bl->eliminable = maybe_eliminate_biv (bl, loop_start, end, 0,
threshold, insn_count);
else
{
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
"Cannot eliminate biv %d.\n",
bl->regno);
fprintf (loop_dump_stream,
"First use: insn %d, last use: insn %d.\n",
REGNO_FIRST_UID (bl->regno),
REGNO_LAST_UID (bl->regno));
}
}
combine_givs (bl);
all_reduced = 1;
for (v = bl->giv; v; v = v->next_iv)
{
struct induction *tv;
if (v->ignore || v->same)
continue;
benefit = v->benefit;
if (! v->replaceable && ! bl->eliminable
&& REG_USERVAR_P (v->dest_reg))
benefit -= copy_cost;
benefit -= add_cost * bl->biv_count;
#ifdef AUTO_INC_DEC
if (v->giv_type == DEST_ADDR
&& GET_CODE (v->mult_val) == CONST_INT)
{
if (HAVE_POST_INCREMENT
&& INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
benefit += add_cost * bl->biv_count;
else if (HAVE_PRE_INCREMENT
&& INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
benefit += add_cost * bl->biv_count;
else if (HAVE_POST_DECREMENT
&& -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
benefit += add_cost * bl->biv_count;
else if (HAVE_PRE_DECREMENT
&& -INTVAL (v->mult_val) == GET_MODE_SIZE (v->mem_mode))
benefit += add_cost * bl->biv_count;
}
#endif
if ( ! flag_reduce_all_givs && v->lifetime * threshold * benefit < insn_count
&& ! bl->reversed )
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"giv of insn %d not worth while, %d vs %d.\n",
INSN_UID (v->insn),
v->lifetime * threshold * benefit, insn_count);
v->ignore = 1;
all_reduced = 0;
}
else
{
for (tv = bl->biv; tv; tv = tv->next_iv)
if (tv->mult_val == const1_rtx
&& ! product_cheap_p (tv->add_val, v->mult_val))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"giv of insn %d: would need a multiply.\n",
INSN_UID (v->insn));
v->ignore = 1;
all_reduced = 0;
break;
}
}
}
for (v = bl->giv; v; v = v->next_iv)
{
if (v->ignore
|| (v->same && v->same->ignore))
continue;
if (v->last_use)
{
struct induction *v1;
for (v1 = bl->giv; v1; v1 = v1->next_iv)
if (v->last_use == v1->insn)
v->maybe_dead = 1;
}
else if (v->giv_type == DEST_REG
&& REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
{
struct induction *v1;
for (v1 = bl->giv; v1; v1 = v1->next_iv)
if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
v->maybe_dead = 1;
}
}
nregs = max_reg_num ();
if (nregs > reg_iv_type->num_elements)
{
if (bl->next)
nregs += nregs / 4;
VARRAY_GROW (reg_iv_type, nregs);
VARRAY_GROW (reg_iv_info, nregs);
}
#if 0
recombine_givs (bl, loop_start, loop_end, unroll_p);
#endif
for (v = bl->giv; v; v = v->next_iv)
{
struct induction *tv;
if (! v->ignore && v->same == 0)
{
int auto_inc_opt = 0;
if (! v->new_reg)
v->new_reg = gen_reg_rtx (v->mode);
if (v->derived_from)
{
struct induction *d = v->derived_from;
if (! d->new_reg)
d->new_reg = gen_reg_rtx (d->mode);
PATTERN (v->insn)
= replace_rtx (PATTERN (v->insn), d->dest_reg, d->new_reg);
PATTERN (v->insn)
= replace_rtx (PATTERN (v->insn), v->dest_reg, v->new_reg);
if (bl->biv_count != 1)
{
for (tv = bl->biv; tv; tv = tv->next_iv)
{
emit_insn_after (copy_rtx (PATTERN (v->insn)),
tv->insn);
}
}
continue;
}
#ifdef AUTO_INC_DEC
if (v->giv_type == DEST_ADDR && bl->biv_count == 1
&& bl->biv->always_executed && ! bl->biv->maybe_multiple
&& ! bl->reversed
&& v->always_executed && ! v->maybe_multiple
&& INSN_UID (v->insn) < max_uid_for_loop)
{
if (v->combined_with)
{
struct induction *other_giv = 0;
for (tv = bl->giv; tv; tv = tv->next_iv)
if (tv->same == v)
{
if (other_giv)
break;
else
other_giv = tv;
}
if (! tv && other_giv
&& REGNO (other_giv->dest_reg) < max_reg_before_loop
&& (REGNO_LAST_UID (REGNO (other_giv->dest_reg))
== INSN_UID (v->insn))
&& INSN_LUID (v->insn) < INSN_LUID (bl->biv->insn))
auto_inc_opt = 1;
}
else if ((INSN_LUID (v->insn) > INSN_LUID (bl->biv->insn)
&& (INSN_LUID (v->insn) < INSN_LUID (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 (bl->biv->insn))))
auto_inc_opt = -1;
else
auto_inc_opt = 1;
#ifdef HAVE_cc0
{
rtx prev;
if ((auto_inc_opt == 1 && sets_cc0_p (PATTERN (v->insn)))
|| (auto_inc_opt == -1
&& (prev = prev_nonnote_insn (v->insn)) != 0
&& GET_RTX_CLASS (GET_CODE (prev)) == 'i'
&& sets_cc0_p (PATTERN (prev))))
auto_inc_opt = 0;
}
#endif
if (auto_inc_opt)
v->auto_inc_opt = 1;
}
#endif
for (tv = bl->biv; tv; tv = tv->next_iv)
{
rtx insert_before;
if (! auto_inc_opt)
insert_before = tv->insn;
else if (auto_inc_opt == 1)
insert_before = NEXT_INSN (v->insn);
else
insert_before = v->insn;
if (tv->mult_val == const1_rtx)
emit_iv_add_mult (tv->add_val, v->mult_val,
v->new_reg, v->new_reg, insert_before);
else
emit_iv_add_mult (tv->add_val, v->mult_val,
v->add_val, v->new_reg, insert_before);
}
emit_iv_add_mult (bl->initial_value, v->mult_val,
v->add_val, v->new_reg, loop_start);
}
}
for (v = bl->giv; v; v = v->next_iv)
{
if (v->same && v->same->ignore)
v->ignore = 1;
if (v->ignore)
continue;
if (v->same)
v->new_reg = replace_rtx (v->new_reg,
v->same->dest_reg, v->same->new_reg);
if (v->giv_type == DEST_ADDR)
validate_change (v->insn, v->location, v->new_reg, 0);
else if (v->replaceable)
{
reg_map[REGNO (v->dest_reg)] = v->new_reg;
#if 0
emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
v->insn);
#endif
}
else
{
emit_insn_after (gen_move_insn (v->dest_reg, v->new_reg),
v->insn);
}
if (bl->reversed && ! v->replaceable)
emit_iv_add_mult (bl->initial_value, v->mult_val,
v->add_val, v->dest_reg, end_insert_before);
else if (v->final_value)
{
rtx insert_before;
if (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
insert_before = loop_start;
else
insert_before = end_insert_before;
emit_insn_before (gen_move_insn (v->dest_reg, v->final_value),
insert_before);
#if 0
delete_insn (v->insn);
#endif
}
if (loop_dump_stream)
{
fprintf (loop_dump_stream, "giv at %d reduced to ",
INSN_UID (v->insn));
print_rtl (loop_dump_stream, v->new_reg);
fprintf (loop_dump_stream, "\n");
}
}
for (v = bl->giv; v; v = v->next_iv)
if (! v->maybe_dead && v->same)
v->same->maybe_dead = 0;
if (all_reduced == 1 && bl->eliminable
&& maybe_eliminate_biv (bl, loop_start, end, 1,
threshold, insn_count))
{
if (final_value != 0 && ! bl->reversed)
{
rtx insert_before;
if (loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
insert_before = loop_start;
else
insert_before = end_insert_before;
emit_insn_before (gen_move_insn (bl->biv->dest_reg, final_value),
end_insert_before);
}
#if 0
for (v = bl->biv; v; v = v->next_iv)
delete_insn (v->insn);
#endif
if (loop_dump_stream)
fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
bl->regno);
}
}
for (p = loop_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, reg_map_size, 0);
replace_regs (REG_NOTES (p), reg_map, reg_map_size, 0);
INSN_CODE (p) = -1;
}
if (unroll_p)
unroll_loop (loop_end, insn_count, loop_start, end_insert_before,
loop_info, 1);
#ifdef HAVE_decrement_and_branch_on_count
if (HAVE_decrement_and_branch_on_count && bct_p
&& flag_branch_on_count_reg)
insert_bct (loop_start, loop_end, loop_info);
#endif
if (loop_dump_stream)
fprintf (loop_dump_stream, "\n");
VARRAY_FREE (reg_iv_type);
VARRAY_FREE (reg_iv_info);
}
static int
valid_initial_value_p (x, insn, call_seen, loop_start)
rtx x;
rtx insn;
int call_seen;
rtx loop_start;
{
if (CONSTANT_P (x))
return 1;
if (GET_CODE (x) != REG
|| REGNO (x) >= max_reg_before_loop)
return 0;
if (REGNO (x) < FIRST_PSEUDO_REGISTER
&& (SMALL_REGISTER_CLASSES
|| (call_used_regs[REGNO (x)] && call_seen)))
return 0;
if (reg_set_between_p (x, insn, loop_start))
return 0;
return 1;
}
static void
find_mem_givs (x, insn, not_every_iteration, loop_start, loop_end)
rtx x;
rtx insn;
int not_every_iteration;
rtx loop_start, loop_end;
{
register int i, j;
register enum rtx_code code;
register char *fmt;
if (x == 0)
return;
code = GET_CODE (x);
switch (code)
{
case REG:
case CONST_INT:
case CONST:
case CONST_DOUBLE:
case SYMBOL_REF:
case LABEL_REF:
case PC:
case CC0:
case ADDR_VEC:
case ADDR_DIFF_VEC:
case USE:
case CLOBBER:
return;
case MEM:
{
rtx src_reg;
rtx add_val;
rtx mult_val;
int benefit;
if (general_induction_var (XEXP (x, 0), &src_reg, &add_val,
&mult_val, 1, &benefit))
{
struct induction *v
= (struct induction *) oballoc (sizeof (struct induction));
record_giv (v, insn, src_reg, addr_placeholder, mult_val,
add_val, benefit, DEST_ADDR, not_every_iteration,
&XEXP (x, 0), loop_start, loop_end);
v->mem_mode = GET_MODE (x);
}
}
return;
default:
break;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
if (fmt[i] == 'e')
find_mem_givs (XEXP (x, i), insn, not_every_iteration, loop_start,
loop_end);
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
find_mem_givs (XVECEXP (x, i, j), insn, not_every_iteration,
loop_start, loop_end);
}
static void
record_biv (v, insn, dest_reg, inc_val, mult_val, location,
not_every_iteration, maybe_multiple)
struct induction *v;
rtx insn;
rtx dest_reg;
rtx inc_val;
rtx mult_val;
rtx *location;
int not_every_iteration;
int maybe_multiple;
{
struct iv_class *bl;
v->insn = insn;
v->src_reg = dest_reg;
v->dest_reg = dest_reg;
v->mult_val = mult_val;
v->add_val = inc_val;
v->location = location;
v->mode = GET_MODE (dest_reg);
v->always_computable = ! not_every_iteration;
v->always_executed = ! not_every_iteration;
v->maybe_multiple = maybe_multiple;
bl = reg_biv_class[REGNO (dest_reg)];
if (bl == 0)
{
bl = (struct iv_class *) oballoc (sizeof (struct iv_class));
bl->regno = REGNO (dest_reg);
bl->biv = 0;
bl->giv = 0;
bl->biv_count = 0;
bl->giv_count = 0;
bl->initial_value = dest_reg;
bl->init_insn = 0;
bl->init_set = 0;
bl->initial_test = 0;
bl->incremented = 0;
bl->eliminable = 0;
bl->nonneg = 0;
bl->reversed = 0;
bl->total_benefit = 0;
bl->next = loop_iv_list;
loop_iv_list = bl;
reg_biv_class[REGNO (dest_reg)] = bl;
}
v->next_iv = bl->biv;
bl->biv = v;
bl->biv_count++;
if (mult_val == const1_rtx)
bl->incremented = 1;
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
"Insn %d: possible biv, reg %d,",
INSN_UID (insn), REGNO (dest_reg));
if (GET_CODE (inc_val) == CONST_INT)
{
fprintf (loop_dump_stream, " const =");
fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (inc_val));
fputc ('\n', loop_dump_stream);
}
else
{
fprintf (loop_dump_stream, " const = ");
print_rtl (loop_dump_stream, inc_val);
fprintf (loop_dump_stream, "\n");
}
}
}
static void
record_giv (v, insn, src_reg, dest_reg, mult_val, add_val, benefit,
type, not_every_iteration, location, loop_start, loop_end)
struct induction *v;
rtx insn;
rtx src_reg;
rtx dest_reg;
rtx mult_val, add_val;
int benefit;
enum g_types type;
int not_every_iteration;
rtx *location;
rtx loop_start, loop_end;
{
struct induction *b;
struct iv_class *bl;
rtx set = single_set (insn);
v->insn = insn;
v->src_reg = src_reg;
v->giv_type = type;
v->dest_reg = dest_reg;
v->mult_val = mult_val;
v->add_val = add_val;
v->benefit = benefit;
v->location = location;
v->cant_derive = 0;
v->combined_with = 0;
v->maybe_multiple = 0;
v->maybe_dead = 0;
v->derive_adjustment = 0;
v->same = 0;
v->ignore = 0;
v->new_reg = 0;
v->final_value = 0;
v->same_insn = 0;
v->auto_inc_opt = 0;
v->unrolled = 0;
v->shared = 0;
v->derived_from = 0;
v->last_use = 0;
if (type == DEST_ADDR)
v->always_computable = 1;
else
v->always_computable = ! not_every_iteration;
v->always_executed = ! not_every_iteration;
if (type == DEST_ADDR)
{
v->mode = GET_MODE (*location);
v->lifetime = 1;
}
else
{
v->mode = GET_MODE (SET_DEST (set));
v->lifetime = (uid_luid[REGNO_LAST_UID (REGNO (dest_reg))]
- uid_luid[REGNO_FIRST_UID (REGNO (dest_reg))]);
if (v->lifetime == 0)
v->ignore = 1;
REG_IV_TYPE (REGNO (dest_reg)) = GENERAL_INDUCT;
REG_IV_INFO (REGNO (dest_reg)) = v;
}
bl = reg_biv_class[REGNO (src_reg)];
if (bl)
{
v->next_iv = bl->giv;
bl->giv = v;
if (type == DEST_REG)
bl->giv_count++;
bl->total_benefit += benefit;
}
else
abort ();
if (type == DEST_ADDR)
v->replaceable = 1;
else
{
if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
&& uid_luid[REGNO_LAST_UID (REGNO (dest_reg))] < INSN_LUID (loop_end)
&& (! not_every_iteration
|| last_use_this_basic_block (dest_reg, insn)))
{
v->replaceable = 1;
for (b = bl->biv; b; b = b->next_iv)
{
if (INSN_UID (b->insn) >= max_uid_for_loop
|| ((uid_luid[INSN_UID (b->insn)]
>= uid_luid[REGNO_FIRST_UID (REGNO (dest_reg))])
&& (uid_luid[INSN_UID (b->insn)]
<= uid_luid[REGNO_LAST_UID (REGNO (dest_reg))])))
{
v->replaceable = 0;
v->not_replaceable = 1;
break;
}
}
if (v->replaceable)
for (b = bl->biv; b; b = b->next_iv)
if (back_branch_in_range_p (b->insn, loop_start, loop_end))
{
v->replaceable = 0;
v->not_replaceable = 1;
break;
}
}
else
{
v->replaceable = 0;
v->not_replaceable = 0;
}
}
{
rtx tem = add_val;
v->no_const_addval = 1;
if (tem == const0_rtx)
;
else if (GET_CODE (tem) == CONST_INT)
v->no_const_addval = 0;
else if (GET_CODE (tem) == PLUS)
{
while (1)
{
if (GET_CODE (XEXP (tem, 0)) == PLUS)
tem = XEXP (tem, 0);
else if (GET_CODE (XEXP (tem, 1)) == PLUS)
tem = XEXP (tem, 1);
else
break;
}
if (GET_CODE (XEXP (tem, 1)) == CONST_INT)
v->no_const_addval = 0;
}
}
if (loop_dump_stream)
{
if (type == DEST_REG)
fprintf (loop_dump_stream, "Insn %d: giv reg %d",
INSN_UID (insn), REGNO (dest_reg));
else
fprintf (loop_dump_stream, "Insn %d: dest address",
INSN_UID (insn));
fprintf (loop_dump_stream, " src reg %d benefit %d",
REGNO (src_reg), v->benefit);
fprintf (loop_dump_stream, " lifetime %d",
v->lifetime);
if (v->replaceable)
fprintf (loop_dump_stream, " replaceable");
if (v->no_const_addval)
fprintf (loop_dump_stream, " ncav");
if (GET_CODE (mult_val) == CONST_INT)
{
fprintf (loop_dump_stream, " mult ");
fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (mult_val));
}
else
{
fprintf (loop_dump_stream, " mult ");
print_rtl (loop_dump_stream, mult_val);
}
if (GET_CODE (add_val) == CONST_INT)
{
fprintf (loop_dump_stream, " add ");
fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, INTVAL (add_val));
}
else
{
fprintf (loop_dump_stream, " add ");
print_rtl (loop_dump_stream, add_val);
}
}
if (loop_dump_stream)
fprintf (loop_dump_stream, "\n");
}
static void
check_final_value (v, loop_start, loop_end, n_iterations)
struct induction *v;
rtx loop_start, loop_end;
unsigned HOST_WIDE_INT n_iterations;
{
struct iv_class *bl;
rtx final_value = 0;
bl = reg_biv_class[REGNO (v->src_reg)];
#if 0
v->replaceable = 0;
#endif
if ((final_value = final_giv_value (v, loop_start, loop_end, n_iterations))
&& (v->always_computable || last_use_this_basic_block (v->dest_reg, v->insn)))
{
int biv_increment_seen = 0;
rtx p = v->insn;
rtx last_giv_use;
v->replaceable = 1;
last_giv_use = v->insn;
while (1)
{
p = NEXT_INSN (p);
if (p == loop_end)
p = NEXT_INSN (loop_start);
if (p == v->insn)
break;
if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
|| GET_CODE (p) == CALL_INSN)
{
if (biv_increment_seen)
{
if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
{
v->replaceable = 0;
v->not_replaceable = 1;
break;
}
}
else if (reg_set_p (v->src_reg, PATTERN (p)))
biv_increment_seen = 1;
else if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
last_giv_use = p;
}
}
if (v->replaceable)
{
p = v->insn;
while (1)
{
p = NEXT_INSN (p);
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 (last_giv_use, JUMP_LABEL (p))
&& loop_insn_first_p (JUMP_LABEL (p), loop_end))))
{
v->replaceable = 0;
v->not_replaceable = 1;
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Found branch outside giv lifetime.\n");
break;
}
}
}
if (v->replaceable)
v->final_value = final_value;
}
if (loop_dump_stream && v->replaceable)
fprintf (loop_dump_stream, "Insn %d: giv reg %d final_value replaceable\n",
INSN_UID (v->insn), REGNO (v->dest_reg));
}
static void
update_giv_derive (p)
rtx p;
{
struct iv_class *bl;
struct induction *biv, *giv;
rtx tem;
int dummy;
for (bl = loop_iv_list; bl; bl = bl->next)
for (biv = bl->biv; biv; biv = biv->next_iv)
if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN
|| biv->insn == p)
{
for (giv = bl->giv; giv; giv = giv->next_iv)
{
if (giv->cant_derive)
continue;
if (GET_CODE (p) == CODE_LABEL && ! giv->always_computable)
giv->cant_derive = 1;
else if (giv->mult_val == const0_rtx || giv->replaceable)
continue;
else if (biv->insn == p)
{
tem = 0;
if (biv->mult_val == const1_rtx)
tem = simplify_giv_expr (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),
&dummy);
if (tem)
giv->derive_adjustment = tem;
else
giv->cant_derive = 1;
}
else if ((GET_CODE (p) == CODE_LABEL && ! biv->always_computable)
|| (GET_CODE (p) == JUMP_INSN && biv->maybe_multiple))
giv->cant_derive = 1;
}
}
}
static int
basic_induction_var (x, mode, dest_reg, p, inc_val, mult_val, location)
register rtx x;
enum machine_mode mode;
rtx p;
rtx dest_reg;
rtx *inc_val;
rtx *mult_val;
rtx **location;
{
register enum rtx_code code;
rtx *argp, arg;
rtx insn, set = 0;
code = GET_CODE (x);
switch (code)
{
case PLUS:
if (rtx_equal_p (XEXP (x, 0), dest_reg)
|| (GET_CODE (XEXP (x, 0)) == SUBREG
&& SUBREG_PROMOTED_VAR_P (XEXP (x, 0))
&& SUBREG_REG (XEXP (x, 0)) == dest_reg))
{
argp = &XEXP (x, 1);
}
else if (rtx_equal_p (XEXP (x, 1), dest_reg)
|| (GET_CODE (XEXP (x, 1)) == SUBREG
&& SUBREG_PROMOTED_VAR_P (XEXP (x, 1))
&& SUBREG_REG (XEXP (x, 1)) == dest_reg))
{
argp = &XEXP (x, 0);
}
else
return 0;
arg = *argp;
if (invariant_p (arg) != 1)
return 0;
*inc_val = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
*mult_val = const1_rtx;
*location = argp;
return 1;
case SUBREG:
if (SUBREG_PROMOTED_VAR_P (x))
return basic_induction_var (SUBREG_REG (x), GET_MODE (SUBREG_REG (x)),
dest_reg, p, inc_val, mult_val, location);
return 0;
case REG:
insn = p;
while (1)
{
do {
insn = PREV_INSN (insn);
} while (insn && GET_CODE (insn) == NOTE
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
if (!insn)
break;
set = single_set (insn);
if (set == 0)
break;
if ((SET_DEST (set) == x
|| (GET_CODE (SET_DEST (set)) == SUBREG
&& (GET_MODE_SIZE (GET_MODE (SET_DEST (set)))
<= UNITS_PER_WORD)
&& SUBREG_REG (SET_DEST (set)) == x))
&& basic_induction_var (SET_SRC (set),
(GET_MODE (SET_SRC (set)) == VOIDmode
? GET_MODE (x)
: GET_MODE (SET_SRC (set))),
dest_reg, insn,
inc_val, mult_val, location))
return 1;
}
case MEM:
if (invariant_p (x) != 1)
return 0;
case CONST_INT:
case SYMBOL_REF:
case CONST:
if (loops_enclosed == 1
#ifdef NEXT_SEMANTICS
&& (GET_MODE_CLASS (mode) == MODE_FLOAT)
== (GET_MODE_CLASS (GET_MODE (dest_reg)) == MODE_FLOAT)
#endif
&& GET_MODE_CLASS (mode) != MODE_CC
&& GET_MODE_CLASS (GET_MODE (dest_reg)) != MODE_CC)
{
*inc_val = convert_modes (GET_MODE (dest_reg), mode, x, 0);
*mult_val = const0_rtx;
return 1;
}
else
return 0;
case SIGN_EXTEND:
return basic_induction_var (XEXP (x, 0), GET_MODE (XEXP (x, 0)),
dest_reg, p, inc_val, mult_val, location);
case ASHIFTRT:
for (insn = PREV_INSN (p);
(insn && GET_CODE (insn) == NOTE
&& NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
insn = PREV_INSN (insn))
;
if (insn)
set = single_set (insn);
if (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),
GET_MODE (XEXP (x, 0)),
dest_reg, insn, inc_val, mult_val,
location);
return 0;
default:
return 0;
}
}
static int
general_induction_var (x, src_reg, add_val, mult_val, is_addr, pbenefit)
rtx x;
rtx *src_reg;
rtx *add_val;
rtx *mult_val;
int is_addr;
int *pbenefit;
{
rtx orig_x = x;
char *storage;
if (invariant_p (x) == 1)
return 0;
storage = (char *) oballoc (0);
*pbenefit = 0;
x = simplify_giv_expr (x, pbenefit);
if (x == 0)
{
obfree (storage);
return 0;
}
switch (GET_CODE (x))
{
case USE:
case CONST_INT:
*src_reg = loop_iv_list->biv->dest_reg;
*mult_val = const0_rtx;
*add_val = x;
break;
case REG:
*src_reg = x;
*mult_val = const1_rtx;
*add_val = const0_rtx;
break;
case PLUS:
if (GET_CODE (XEXP (x, 0)) == MULT)
{
*src_reg = XEXP (XEXP (x, 0), 0);
*mult_val = XEXP (XEXP (x, 0), 1);
}
else
{
*src_reg = XEXP (x, 0);
*mult_val = const1_rtx;
}
*add_val = XEXP (x, 1);
break;
case MULT:
*src_reg = XEXP (x, 0);
*mult_val = XEXP (x, 1);
*add_val = const0_rtx;
break;
default:
abort ();
}
if (GET_CODE (*add_val) == USE)
*add_val = XEXP (*add_val, 0);
if (GET_CODE (*mult_val) == USE)
*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
}
else
*pbenefit += rtx_cost (orig_x, SET);
return 1;
}
static rtx sge_plus PROTO ((enum machine_mode, rtx, rtx));
static rtx sge_plus_constant PROTO ((rtx, rtx));
static rtx
simplify_giv_expr (x, benefit)
rtx x;
int *benefit;
{
enum machine_mode mode = GET_MODE (x);
rtx arg0, arg1;
rtx tem;
if (mode != VOIDmode
&& (GET_MODE_CLASS (mode) != MODE_INT
|| GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT))
return NULL_RTX;
switch (GET_CODE (x))
{
case PLUS:
arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
if (arg0 == 0 || arg1 == 0)
return NULL_RTX;
if ((GET_CODE (arg0) == USE
|| GET_CODE (arg0) == CONST_INT)
&& ! ((GET_CODE (arg0) == USE
&& GET_CODE (arg1) == USE)
|| GET_CODE (arg1) == CONST_INT))
tem = arg0, arg0 = arg1, arg1 = tem;
if (arg1 == const0_rtx)
return arg0;
else if (GET_CODE (arg1) == CONST_INT || GET_CODE (arg1) == USE)
switch (GET_CODE (arg0))
{
case CONST_INT:
case USE:
if (GET_CODE (arg0) == USE)
arg0 = XEXP (arg0, 0);
if (GET_CODE (arg1) == USE)
arg1 = XEXP (arg1, 0);
if (GET_CODE (arg0) == CONST_INT)
tem = arg0, arg0 = arg1, arg1 = tem;
if (GET_CODE (arg1) == CONST_INT)
tem = sge_plus_constant (arg0, arg1);
else
tem = sge_plus (mode, arg0, arg1);
if (GET_CODE (tem) != CONST_INT)
tem = gen_rtx_USE (mode, tem);
return tem;
case REG:
case MULT:
return gen_rtx_PLUS (mode, arg0, arg1);
case PLUS:
return simplify_giv_expr (
gen_rtx_PLUS (mode, XEXP (arg0, 0),
gen_rtx_PLUS (mode, XEXP (arg0, 1), arg1)),
benefit);
default:
abort ();
}
if (GET_CODE (arg0) == REG)
arg0 = gen_rtx_MULT (mode, arg0, const1_rtx);
if (GET_CODE (arg1) == REG)
arg1 = gen_rtx_MULT (mode, arg1, const1_rtx);
if (GET_CODE (arg1) == MULT)
tem = arg0, arg0 = arg1, arg1 = tem;
if (GET_CODE (arg1) == PLUS)
return simplify_giv_expr (gen_rtx_PLUS (mode,
gen_rtx_PLUS (mode, arg0,
XEXP (arg1, 0)),
XEXP (arg1, 1)),
benefit);
if (GET_CODE (arg0) != MULT || GET_CODE (arg1) != MULT)
return NULL_RTX;
if (!rtx_equal_p (arg0, arg1))
return NULL_RTX;
return simplify_giv_expr (gen_rtx_MULT (mode,
XEXP (arg0, 0),
gen_rtx_PLUS (mode,
XEXP (arg0, 1),
XEXP (arg1, 1))),
benefit);
case MINUS:
return simplify_giv_expr (gen_rtx_PLUS (mode,
XEXP (x, 0),
gen_rtx_MULT (mode, XEXP (x, 1),
constm1_rtx)),
benefit);
case MULT:
arg0 = simplify_giv_expr (XEXP (x, 0), benefit);
arg1 = simplify_giv_expr (XEXP (x, 1), benefit);
if (arg0 == 0 || arg1 == 0)
return NULL_RTX;
if ((GET_CODE (arg0) == USE || GET_CODE (arg0) == CONST_INT)
&& GET_CODE (arg1) != CONST_INT)
tem = arg0, arg0 = arg1, arg1 = tem;
if (GET_CODE (arg1) != USE && GET_CODE (arg1) != CONST_INT)
return NULL_RTX;
if (arg1 == const0_rtx)
return const0_rtx;
else if (arg1 == const1_rtx)
return arg0;
switch (GET_CODE (arg0))
{
case REG:
return gen_rtx_MULT (mode, arg0, arg1);
case CONST_INT:
return GEN_INT (INTVAL (arg0) * INTVAL (arg1));
case USE:
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)
{
tem = gen_rtx_MULT (mode, XEXP (arg0, 0),
GEN_INT (INTVAL (XEXP (arg0, 1))
* INTVAL (arg1)));
}
else
return NULL_RTX;
return gen_rtx_USE (mode, tem);
case MULT:
return simplify_giv_expr (gen_rtx_MULT (mode, XEXP (arg0, 0),
gen_rtx_MULT (mode,
XEXP (arg0, 1),
arg1)),
benefit);
case PLUS:
return simplify_giv_expr (gen_rtx_PLUS (mode,
gen_rtx_MULT (mode,
XEXP (arg0, 0),
arg1),
gen_rtx_MULT (mode,
XEXP (arg0, 1),
arg1)),
benefit);
default:
abort ();
}
case ASHIFT:
if (GET_CODE (XEXP (x, 1)) != CONST_INT)
return 0;
return simplify_giv_expr (gen_rtx_MULT (mode,
XEXP (x, 0),
GEN_INT ((HOST_WIDE_INT) 1
<< INTVAL (XEXP (x, 1)))),
benefit);
case NEG:
return simplify_giv_expr (gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
benefit);
case NOT:
return simplify_giv_expr (gen_rtx_MINUS (mode,
gen_rtx_NEG (mode, XEXP (x, 0)),
const1_rtx),
benefit);
case USE:
return x;
case REG:
if (REGNO (x) >= max_reg_before_loop)
return 0;
switch (REG_IV_TYPE (REGNO (x)))
{
case BASIC_INDUCT:
return x;
case GENERAL_INDUCT:
{
struct induction *v = REG_IV_INFO (REGNO (x));
*benefit += v->benefit;
if (v->cant_derive)
return 0;
tem = gen_rtx_PLUS (mode, gen_rtx_MULT (mode, v->src_reg,
v->mult_val),
v->add_val);
if (v->derive_adjustment)
tem = gen_rtx_MINUS (mode, tem, v->derive_adjustment);
return simplify_giv_expr (tem, benefit);
}
default:
if (invariant_p (x) == 1)
{
struct movable *m;
for (m = the_movables; m ; m = m->next)
if (rtx_equal_p (x, m->set_dest))
{
if (m->match)
return simplify_giv_expr (m->match->set_dest, benefit);
if (m->consec != 0)
{
int i = m->consec;
tem = m->insn;
do { tem = NEXT_INSN (tem); } while (--i > 0);
tem = find_reg_note (tem, REG_EQUAL, NULL_RTX);
if (tem)
tem = XEXP (tem, 0);
}
else
{
tem = single_set (m->insn);
if (tem)
tem = SET_SRC (tem);
}
if (tem)
{
if (GET_CODE (tem) == PLUS
|| GET_CODE (tem) == MULT
|| GET_CODE (tem) == ASHIFT
|| GET_CODE (tem) == CONST_INT
|| GET_CODE (tem) == SYMBOL_REF)
{
tem = simplify_giv_expr (tem, benefit);
if (tem)
return tem;
}
else if (GET_CODE (tem) == CONST
&& GET_CODE (XEXP (tem, 0)) == PLUS
&& 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);
if (tem)
return tem;
}
}
break;
}
}
break;
}
default:
if (GET_CODE (x) == USE)
x = XEXP (x, 0);
if (invariant_p (x) == 1)
{
if (GET_CODE (x) == CONST_INT)
return x;
if (GET_CODE (x) == CONST
&& GET_CODE (XEXP (x, 0)) == PLUS
&& GET_CODE (XEXP (XEXP (x, 0), 0)) == SYMBOL_REF
&& GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT)
x = XEXP (x, 0);
return gen_rtx_USE (mode, x);
}
else
return 0;
}
}
static rtx
sge_plus_constant (x, c)
rtx x, c;
{
if (GET_CODE (x) == CONST_INT)
return GEN_INT (INTVAL (x) + INTVAL (c));
else if (GET_CODE (x) != PLUS)
return gen_rtx_PLUS (GET_MODE (x), x, c);
else if (GET_CODE (XEXP (x, 1)) == CONST_INT)
{
return gen_rtx_PLUS (GET_MODE (x), XEXP (x, 0),
GEN_INT (INTVAL (XEXP (x, 1)) + INTVAL (c)));
}
else if (GET_CODE (XEXP (x, 0)) == PLUS
|| GET_CODE (XEXP (x, 1)) != PLUS)
{
return gen_rtx_PLUS (GET_MODE (x),
sge_plus_constant (XEXP (x, 0), c), XEXP (x, 1));
}
else
{
return gen_rtx_PLUS (GET_MODE (x),
sge_plus_constant (XEXP (x, 1), c), XEXP (x, 0));
}
}
static rtx
sge_plus (mode, x, y)
enum machine_mode mode;
rtx x, y;
{
while (GET_CODE (y) == PLUS)
{
rtx a = XEXP (y, 0);
if (GET_CODE (a) == CONST_INT)
x = sge_plus_constant (x, a);
else
x = gen_rtx_PLUS (mode, x, a);
y = XEXP (y, 1);
}
if (GET_CODE (y) == CONST_INT)
x = sge_plus_constant (x, y);
else
x = gen_rtx_PLUS (mode, x, y);
return x;
}
static int
consec_sets_giv (first_benefit, p, src_reg, dest_reg,
add_val, mult_val, last_consec_insn)
int first_benefit;
rtx p;
rtx src_reg;
rtx dest_reg;
rtx *add_val;
rtx *mult_val;
rtx *last_consec_insn;
{
int count;
enum rtx_code code;
int benefit;
rtx temp;
rtx set;
struct induction *v
= (struct induction *) alloca (sizeof (struct induction));
v->src_reg = src_reg;
v->mult_val = *mult_val;
v->add_val = *add_val;
v->benefit = first_benefit;
v->cant_derive = 0;
v->derive_adjustment = 0;
REG_IV_TYPE (REGNO (dest_reg)) = GENERAL_INDUCT;
REG_IV_INFO (REGNO (dest_reg)) = v;
count = VARRAY_INT (n_times_set, REGNO (dest_reg)) - 1;
while (count > 0)
{
p = NEXT_INSN (p);
code = GET_CODE (p);
if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
p = XEXP (temp, 0);
if (code == INSN
&& (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)
|| ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
&& general_induction_var (XEXP (temp, 0), &src_reg,
add_val, mult_val, 0, &benefit)))
&& src_reg == v->src_reg)
{
if (find_reg_note (p, REG_RETVAL, NULL_RTX))
benefit += libcall_benefit (p);
count--;
v->mult_val = *mult_val;
v->add_val = *add_val;
v->benefit = benefit;
}
else if (code != NOTE)
{
if (code == INSN
&& (set = single_set (p))
&& SET_DEST (set) != dest_reg
&& CONSTANT_P (SET_SRC (set)))
continue;
REG_IV_TYPE (REGNO (dest_reg)) = UNKNOWN_INDUCT;
return 0;
}
}
*last_consec_insn = p;
return v->benefit;
}
static rtx
express_from_1 (a, b, mult)
rtx a, b, mult;
{
if (mult == const0_rtx)
return b;
if (mult != const1_rtx && GET_CODE (a) != CONST_INT)
return NULL_RTX;
while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
{
rtx ra, rb, oa, ob, tmp;
ra = XEXP (a, 0), oa = XEXP (a, 1);
if (GET_CODE (ra) == PLUS)
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;
if (rtx_equal_p (ra, rb))
a = oa, b = ob;
else if (GET_CODE (ob) != PLUS && rtx_equal_p (ra, ob))
a = oa, b = rb;
else if (GET_CODE (oa) != PLUS && rtx_equal_p (oa, rb))
a = ra, b = ob;
else
{
ob = express_from_1 (a, ob, mult);
if (ob == NULL_RTX)
return NULL_RTX;
return gen_rtx_PLUS (GET_MODE (b), rb, ob);
}
}
if (GET_CODE (a) == PLUS)
{
rtx ra, oa;
ra = XEXP (a, 0), oa = XEXP (a, 1);
if (rtx_equal_p (oa, b))
oa = ra;
else if (!rtx_equal_p (ra, b))
return NULL_RTX;
if (GET_CODE (oa) != CONST_INT)
return NULL_RTX;
return GEN_INT (-INTVAL (oa) * INTVAL (mult));
}
else if (GET_CODE (a) == CONST_INT)
{
return plus_constant (b, -INTVAL (a) * INTVAL (mult));
}
else if (GET_CODE (b) == PLUS)
{
if (rtx_equal_p (a, XEXP (b, 0)))
return XEXP (b, 1);
else if (rtx_equal_p (a, XEXP (b, 1)))
return XEXP (b, 0);
else
return NULL_RTX;
}
else if (rtx_equal_p (a, b))
return const0_rtx;
return NULL_RTX;
}
rtx
express_from (g1, g2)
struct induction *g1, *g2;
{
rtx mult, add;
if (GET_CODE (g1->mult_val) == CONST_INT
&& 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;
mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
}
else if (rtx_equal_p (g1->mult_val, g2->mult_val))
mult = const1_rtx;
else
{
return NULL_RTX;
}
add = express_from_1 (g1->add_val, g2->add_val, mult);
if (add == NULL_RTX)
return NULL_RTX;
if (mult == const0_rtx)
return add;
else if (mult == const1_rtx)
mult = g1->dest_reg;
else
mult = gen_rtx_MULT (g2->mode, g1->dest_reg, mult);
if (add == const0_rtx)
return mult;
else
{
if (GET_CODE (add) == PLUS
&& CONSTANT_P (XEXP (add, 1)))
{
rtx tem = XEXP (add, 1);
mult = gen_rtx_PLUS (g2->mode, mult, XEXP (add, 0));
add = tem;
}
return gen_rtx_PLUS (g2->mode, mult, add);
}
}
static rtx
combine_givs_p (g1, g2)
struct induction *g1, *g2;
{
rtx tem = express_from (g1, g2);
if (tem == g1->dest_reg
&& (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
{
return g1->dest_reg;
}
if (tem != NULL_RTX
&& g2->giv_type == DEST_ADDR
&& memory_address_p (g2->mem_mode, tem)
#if 0
#ifdef ADDRESS_COST
&& ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
#else
&& rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
#endif
#endif
)
{
return tem;
}
return NULL_RTX;
}
struct combine_givs_stats
{
int giv_number;
int total_benefit;
};
static int
cmp_combine_givs_stats (x, y)
struct combine_givs_stats *x, *y;
{
int d;
d = y->total_benefit - x->total_benefit;
if (!d)
d = x->giv_number - y->giv_number;
return d;
}
static void
combine_givs (bl)
struct iv_class *bl;
{
const int extra_benefit = 3;
struct induction *g1, *g2, **giv_array;
int i, j, k, giv_count;
struct combine_givs_stats *stats;
rtx *can_combine;
giv_count = 0;
for (g1 = bl->giv; g1; g1 = g1->next_iv)
if (!g1->ignore)
giv_count++;
giv_array
= (struct induction **) alloca (giv_count * sizeof (struct induction *));
i = 0;
for (g1 = bl->giv; g1; g1 = g1->next_iv)
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));
for (i = 0; i < giv_count; i++)
{
int this_benefit;
rtx single_use;
g1 = giv_array[i];
stats[i].giv_number = i;
if (g1->giv_type == DEST_REG
&& (single_use = VARRAY_RTX (reg_single_usage, REGNO (g1->dest_reg)))
&& single_use != const0_rtx)
continue;
this_benefit = g1->benefit;
if (g1->no_const_addval)
this_benefit += 1;
for (j = 0; j < giv_count; j++)
{
rtx this_combine;
g2 = giv_array[j];
if (g1 != g2
&& (this_combine = combine_givs_p (g1, g2)) != NULL_RTX)
{
can_combine[i*giv_count + j] = this_combine;
this_benefit += g2->benefit + extra_benefit;
}
}
stats[i].total_benefit = this_benefit;
}
restart:
qsort (stats, giv_count, sizeof(*stats), cmp_combine_givs_stats);
if (loop_dump_stream)
{
fprintf (loop_dump_stream, "Sorted combine statistics:\n");
for (k = 0; k < giv_count; k++)
{
g1 = giv_array[stats[k].giv_number];
if (!g1->combined_with && !g1->same)
fprintf (loop_dump_stream, " {%d, %d}",
INSN_UID (giv_array[stats[k].giv_number]->insn),
stats[k].total_benefit);
}
putc ('\n', loop_dump_stream);
}
for (k = 0; k < giv_count; k++)
{
int g1_add_benefit = 0;
i = stats[k].giv_number;
g1 = giv_array[i];
if (g1->combined_with || g1->same)
continue;
for (j = 0; j < giv_count; j++)
{
g2 = giv_array[j];
if (g1 != g2 && can_combine[i*giv_count + j]
&& ! g2->same && ! g2->combined_with)
{
int l;
g2->new_reg = can_combine[i*giv_count + j];
g2->same = g1;
g1->combined_with++;
g1->lifetime += g2->lifetime;
g1_add_benefit += g2->benefit;
if (! g2->replaceable && REG_USERVAR_P (g2->dest_reg))
g1_add_benefit -= copy_cost;
for (l = 0; l < giv_count; ++l)
{
int m = stats[l].giv_number;
if (can_combine[m*giv_count + j])
stats[l].total_benefit -= g2->benefit + extra_benefit;
}
if (loop_dump_stream)
fprintf (loop_dump_stream,
"giv at %d combined with giv at %d\n",
INSN_UID (g2->insn), INSN_UID (g1->insn));
}
}
if (g1->combined_with)
{
for (j = 0; j < giv_count; ++j)
{
int m = stats[j].giv_number;
if (can_combine[m*giv_count + i])
stats[j].total_benefit -= g1->benefit + extra_benefit;
}
g1->benefit += g1_add_benefit;
goto restart;
}
}
}
struct recombine_givs_stats
{
int giv_number;
int start_luid, end_luid;
};
static int
cmp_recombine_givs_stats (x, y)
struct recombine_givs_stats *x, *y;
{
int d;
d = y->start_luid - x->start_luid;
if (!d)
d = y->giv_number - x->giv_number;
return d;
}
static int
find_life_end (x, stats, insn, biv)
rtx x, insn, biv;
struct recombine_givs_stats *stats;
{
enum rtx_code code;
char *fmt;
int i, j;
int retval;
code = GET_CODE (x);
switch (code)
{
case SET:
{
rtx reg = SET_DEST (x);
if (GET_CODE (reg) == REG)
{
int regno = REGNO (reg);
struct induction *v = REG_IV_INFO (regno);
if (REG_IV_TYPE (regno) == GENERAL_INDUCT
&& ! v->ignore
&& v->src_reg == biv
&& stats[v->ix].end_luid <= 0)
{
if (stats[v->ix].end_luid == 0)
{
stats[v->ix].end_luid = stats[v->ix].start_luid;
return 1 + find_life_end (SET_SRC (x), stats, insn, biv);
}
else if (stats[v->ix].start_luid == INSN_LUID (insn))
stats[v->ix].end_luid = 0;
}
return find_life_end (SET_SRC (x), stats, insn, biv);
}
break;
}
case REG:
{
int regno = REGNO (x);
struct induction *v = REG_IV_INFO (regno);
if (REG_IV_TYPE (regno) == GENERAL_INDUCT
&& ! v->ignore
&& v->src_reg == biv
&& stats[v->ix].end_luid == 0)
{
while (INSN_UID (insn) >= max_uid_for_loop)
insn = NEXT_INSN (insn);
stats[v->ix].end_luid = INSN_LUID (insn);
return 1;
}
return 0;
}
case LABEL_REF:
case CONST_DOUBLE:
case CONST_INT:
case CONST:
return 0;
default:
break;
}
fmt = GET_RTX_FORMAT (code);
retval = 0;
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
retval += find_life_end (XEXP (x, i), stats, insn, biv);
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
retval += find_life_end (XVECEXP (x, i, j), stats, insn, biv);
}
return retval;
}
static void
recombine_givs (bl, loop_start, loop_end, unroll_p)
struct iv_class *bl;
rtx loop_start, loop_end;
int unroll_p;
{
struct induction *v, **giv_array, *last_giv;
struct recombine_givs_stats *stats;
int giv_count;
int i, rescan;
int ends_need_computing;
for (giv_count = 0, v = bl->giv; v; v = v->next_iv)
{
if (! v->ignore)
giv_count++;
}
giv_array
= (struct induction **) alloca (giv_count * sizeof (struct induction *));
stats = (struct recombine_givs_stats *) alloca (giv_count * sizeof *stats);
for (i = 0, v = bl->giv; v; v = v->next_iv)
{
rtx p;
if (v->ignore)
continue;
giv_array[i] = v;
stats[i].giv_number = i;
for (p = v->insn; INSN_UID (p) >= max_uid_for_loop; )
p = PREV_INSN (p);
stats[i].start_luid = INSN_LUID (p);
v->ix = i;
i++;
}
qsort (stats, giv_count, sizeof(*stats), cmp_recombine_givs_stats);
for (last_giv = 0, i = giv_count - 1; i >= 0; i--)
{
v = giv_array[stats[i].giv_number];
if (v->same)
{
struct induction *old_same = v->same;
rtx new_combine;
if (last_giv
&& ((old_same->maybe_dead && ! old_same->combined_with)
|| ! last_giv->maybe_dead
|| last_giv->combined_with)
&& (new_combine = combine_givs_p (last_giv, v)))
{
old_same->combined_with--;
v->new_reg = new_combine;
v->same = last_giv;
last_giv->combined_with++;
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
"giv at %d recombined with giv at %d as ",
INSN_UID (v->insn), INSN_UID (last_giv->insn));
print_rtl (loop_dump_stream, v->new_reg);
putc ('\n', loop_dump_stream);
}
continue;
}
v = v->same;
}
else if (v->giv_type != DEST_REG)
continue;
if (! last_giv
|| (last_giv->maybe_dead && ! last_giv->combined_with)
|| ! v->maybe_dead
|| v->combined_with)
last_giv = v;
}
ends_need_computing = 0;
for (i = 0, v = bl->giv; v; v = v->next_iv)
{
if (v->ignore)
continue;
if (v->giv_type == DEST_ADDR)
{
rtx p;
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)
stats[i].end_luid++;
}
else
{
if (v->last_use)
{
stats[i].start_luid = INSN_LUID (v->insn);
stats[i].end_luid = INSN_LUID (v->last_use);
}
else if (INSN_UID (v->insn) >= max_uid_for_loop)
{
rtx p;
for (p = PREV_INSN (v->insn); INSN_UID (p) >= max_uid_for_loop; )
p = PREV_INSN (p);
stats[i].start_luid = INSN_LUID (p);
stats[i].end_luid = 0;
ends_need_computing++;
}
else
{
int regno = REGNO (v->dest_reg);
int count = VARRAY_INT (n_times_set, regno) - 1;
rtx p = v->insn;
while (count)
{
p = prev_nonnote_insn (p);
if (reg_set_p (v->dest_reg, p))
count--;
}
stats[i].start_luid = INSN_LUID (p);
if (stats[i].start_luid > uid_luid[REGNO_FIRST_UID (regno)])
{
stats[i].end_luid = -1;
ends_need_computing++;
}
else
{
stats[i].end_luid = uid_luid[REGNO_LAST_UID (regno)];
if (stats[i].end_luid > INSN_LUID (loop_end))
{
stats[i].end_luid = -1;
ends_need_computing++;
}
}
}
}
i++;
}
if (ends_need_computing)
{
rtx biv = bl->biv->src_reg;
rtx p = loop_end;
do
{
if (p == loop_start)
p = loop_end;
p = PREV_INSN (p);
if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
continue;
ends_need_computing -= find_life_end (PATTERN (p), stats, p, biv);
}
while (ends_need_computing);
}
for (i = 0, v = bl->giv; v; v = v->next_iv)
{
if (v->ignore)
continue;
if (INSN_UID (v->insn) < max_uid_for_loop)
stats[i].start_luid = INSN_LUID (v->insn);
i++;
}
for (i = 0, v = bl->giv; v; v = v->next_iv)
{
unsigned luid;
int j;
if (v->ignore)
continue;
if (v->same && ! v->same->ignore)
{
j = v->same->ix;
luid = stats[i].start_luid;
if (luid - stats[j].start_luid
> (unsigned) stats[j].end_luid - stats[j].start_luid)
stats[j].end_luid = luid;
}
i++;
}
qsort (stats, giv_count, sizeof(*stats), cmp_recombine_givs_stats);
for (i = giv_count - 1; i >= 0; i = rescan)
{
int life_start, life_end;
for (last_giv = 0, rescan = -1; i >= 0; i--)
{
rtx sum;
v = giv_array[stats[i].giv_number];
if (v->giv_type != DEST_REG || v->derived_from || v->same)
continue;
if (! last_giv)
{
if (! v->maybe_dead || v->combined_with)
{
last_giv = v;
life_start = stats[i].start_luid;
life_end = stats[i].end_luid;
}
continue;
}
if (((unsigned) stats[i].start_luid - life_start
>= (unsigned) life_end - life_start)
&& ((unsigned) stats[i].end_luid - life_start
> (unsigned) life_end - life_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)
&& ! find_reg_note (v->insn, REG_RETVAL, NULL_RTX)
&& (v->always_executed || ! v->combined_with)
&& (sum = express_from (last_giv, v))
&& (rtx_cost (sum, SET)
<= rtx_cost (SET_SRC (single_set (v->insn)), SET))
&& ((GET_CODE (sum) == PLUS
&& GET_CODE (XEXP (sum, 0)) == REG
&& GET_CODE (XEXP (sum, 1)) == CONST_INT)
|| ! unroll_p)
&& validate_change (v->insn, &PATTERN (v->insn),
gen_rtx_SET (VOIDmode, v->dest_reg, sum), 0))
{
v->derived_from = last_giv;
life_end = stats[i].end_luid;
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
"giv at %d derived from %d as ",
INSN_UID (v->insn), INSN_UID (last_giv->insn));
print_rtl (loop_dump_stream, sum);
putc ('\n', loop_dump_stream);
}
}
else if (rescan < 0)
rescan = i;
}
}
}
void
emit_iv_add_mult (b, m, a, reg, insert_before)
rtx b;
rtx m;
rtx a;
rtx reg;
rtx insert_before;
{
rtx seq;
rtx result;
a = copy_rtx (a);
b = copy_rtx (b);
update_reg_last_use (a, insert_before);
update_reg_last_use (b, insert_before);
update_reg_last_use (m, insert_before);
start_sequence ();
result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 0);
if (reg != result)
emit_move_insn (reg, result);
seq = gen_sequence ();
end_sequence ();
emit_insn_before (seq, insert_before);
if (GET_CODE (seq) == SEQUENCE)
{
int i;
for (i = 0; i < XVECLEN (seq, 0); ++i)
{
rtx set = single_set (XVECEXP (seq, 0, i));
if (set && GET_CODE (SET_DEST (set)) == REG)
record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
}
}
else if (GET_CODE (seq) == SET
&& GET_CODE (SET_DEST (seq)) == REG)
record_base_value (REGNO (SET_DEST (seq)), SET_SRC (seq), 0);
}
static int
product_cheap_p (a, b)
rtx a;
rtx b;
{
int i;
rtx tmp;
struct obstack *old_rtl_obstack = rtl_obstack;
char *storage = (char *) obstack_alloc (&temp_obstack, 0);
int win = 1;
if (GET_CODE (a) == CONST_INT)
tmp = a, a = b, b = tmp;
if (GET_CODE (a) == CONST_INT)
return 1;
if (GET_CODE (b) != CONST_INT)
return 0;
rtl_obstack = &temp_obstack;
start_sequence ();
expand_mult (GET_MODE (a), a, b, NULL_RTX, 0);
tmp = gen_sequence ();
end_sequence ();
if (GET_CODE (tmp) == SEQUENCE)
{
if (XVEC (tmp, 0) == 0)
win = 1;
else if (XVECLEN (tmp, 0) > 3)
win = 0;
else
for (i = 0; i < XVECLEN (tmp, 0); i++)
{
rtx insn = XVECEXP (tmp, 0, i);
if (GET_CODE (insn) != INSN
|| (GET_CODE (PATTERN (insn)) == SET
&& GET_CODE (SET_SRC (PATTERN (insn))) == MULT)
|| (GET_CODE (PATTERN (insn)) == PARALLEL
&& GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) == SET
&& GET_CODE (SET_SRC (XVECEXP (PATTERN (insn), 0, 0))) == MULT))
{
win = 0;
break;
}
}
}
else if (GET_CODE (tmp) == SET
&& GET_CODE (SET_SRC (tmp)) == MULT)
win = 0;
else if (GET_CODE (tmp) == PARALLEL
&& GET_CODE (XVECEXP (tmp, 0, 0)) == SET
&& GET_CODE (SET_SRC (XVECEXP (tmp, 0, 0))) == MULT)
win = 0;
obstack_free (&temp_obstack, storage);
rtl_obstack = old_rtl_obstack;
return win;
}
static int
check_dbra_loop (loop_end, insn_count, loop_start, loop_info)
rtx loop_end;
int insn_count;
rtx loop_start;
struct loop_info *loop_info;
{
struct iv_class *bl;
rtx reg;
rtx jump_label;
rtx final_value;
rtx start_value;
rtx new_add_val;
rtx comparison;
rtx before_comparison;
rtx p;
rtx jump;
rtx first_compare;
int compare_and_branch;
jump = PREV_INSN (loop_end);
comparison = get_condition_for_loop (jump);
if (comparison == 0)
return 0;
get_condition (jump, &first_compare);
if (first_compare == jump)
compare_and_branch = 1;
else if (first_compare == prev_nonnote_insn (jump))
compare_and_branch = 2;
else
return 0;
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))
break;
}
if (! bl)
return 0;
if (((GET_CODE (comparison) == GT
&& GET_CODE (XEXP (comparison, 1)) == CONST_INT
&& INTVAL (XEXP (comparison, 1)) == -1)
|| (GET_CODE (comparison) == NE && XEXP (comparison, 1) == const0_rtx))
&& GET_CODE (bl->biv->add_val) == CONST_INT
&& INTVAL (bl->biv->add_val) < 0)
{
if (GET_CODE (bl->initial_value) == CONST_INT
&& INTVAL (bl->initial_value) > 0
&& (INTVAL (bl->initial_value)
% (-INTVAL (bl->biv->add_val))) == 0)
{
REG_NOTES (PREV_INSN (loop_end))
= gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX,
REG_NOTES (PREV_INSN (loop_end)));
bl->nonneg = 1;
return 1;
}
for (p = loop_start; p; p = PREV_INSN (p))
{
if (GET_CODE (p) == CODE_LABEL)
break;
if (GET_CODE (p) != JUMP_INSN)
continue;
before_comparison = get_condition_for_loop (p);
if (before_comparison
&& XEXP (before_comparison, 0) == bl->biv->dest_reg
&& GET_CODE (before_comparison) == LT
&& XEXP (before_comparison, 1) == const0_rtx
&& ! 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)));
bl->nonneg = 1;
return 1;
}
}
}
else if (GET_CODE (bl->biv->add_val) == CONST_INT
&& INTVAL (bl->biv->add_val) > 0)
{
int num_nonfixed_reads = 0;
int no_use_except_counting = 0;
int reversible_mem_store = 1;
if (bl->giv_count == 0
&& ! loop_number_exit_count[uid_loop_num[INSN_UID (loop_start)]])
{
rtx bivreg = regno_reg_rtx[bl->regno];
no_use_except_counting = 1;
for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
{
rtx set = single_set (p);
if (set && GET_CODE (SET_DEST (set)) == REG
&& REGNO (SET_DEST (set)) == bl->regno)
;
else if ((p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
|| p == prev_nonnote_insn (loop_end))
&& reg_mentioned_p (bivreg, PATTERN (p)))
{
note_set_pseudo_multiple_uses_retval = 0;
note_stores (PATTERN (p), note_set_pseudo_multiple_uses);
if (note_set_pseudo_multiple_uses_retval)
{
no_use_except_counting = 0;
break;
}
}
else if (reg_mentioned_p (bivreg, PATTERN (p)))
{
no_use_except_counting = 0;
break;
}
}
}
if (no_use_except_counting)
;
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 (num_mem_sets == 1)
{
struct induction *v;
reversible_mem_store
= (! unknown_address_altered
&& ! invariant_p (XEXP (XEXP (loop_store_mems, 0), 0)));
for (v = bl->giv; reversible_mem_store && v; v = v->next_iv)
{
if (v->giv_type == DEST_REG
&& reg_mentioned_p (v->dest_reg,
XEXP (loop_store_mems, 0))
&& loop_insn_first_p (first_loop_store_insn, v->insn))
reversible_mem_store = 0;
}
}
}
else
return 0;
if ((num_nonfixed_reads <= 1
&& !loop_has_call
&& !loop_has_volatile
&& reversible_mem_store
&& (bl->giv_count + bl->biv_count + num_mem_sets
+ num_movables + compare_and_branch == insn_count)
&& (bl == loop_iv_list && bl->next == 0))
|| no_use_except_counting)
{
rtx tem;
if (loop_dump_stream)
fprintf (loop_dump_stream, "Can reverse loop\n");
if (comparison
&& (GET_CODE (comparison) == LT
|| (GET_CODE (comparison) == LE
&& no_use_except_counting)))
{
HOST_WIDE_INT add_val, add_adjust, comparison_val;
rtx initial_value, comparison_value;
int nonneg = 0;
enum rtx_code cmp_code;
int comparison_const_width;
unsigned HOST_WIDE_INT comparison_sign_mask;
add_val = INTVAL (bl->biv->add_val);
comparison_value = XEXP (comparison, 1);
if (GET_MODE (comparison_value) == VOIDmode)
comparison_const_width
= GET_MODE_BITSIZE (GET_MODE (XEXP (comparison, 0)));
else
comparison_const_width
= GET_MODE_BITSIZE (GET_MODE (comparison_value));
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);
if (!invariant_p (comparison_value))
return 0;
if (GET_CODE (comparison_value) == CONST_INT)
comparison_val = INTVAL (comparison_value);
initial_value = bl->initial_value;
if (no_use_except_counting
&& GET_CODE (comparison_value) == CONST_INT
&& GET_CODE (initial_value) == CONST_INT)
{
comparison_val = comparison_val - INTVAL (bl->initial_value);
comparison_val = comparison_val + add_val - 1;
comparison_val
-= (unsigned HOST_WIDE_INT) comparison_val % add_val;
initial_value = const0_rtx;
}
if (initial_value == const0_rtx
#if ! defined (HAVE_decrement_and_branch_until_zero) && defined (HAVE_decrement_and_branch_on_count)
&& (! (add_val == 1 && loop_info->vtop
&& (bl->biv_count == 0
|| no_use_except_counting)))
#endif
&& GET_CODE (comparison_value) == CONST_INT
&& ! (((comparison_val - add_val) ^ INTVAL (comparison_value))
& comparison_sign_mask))
{
add_adjust = add_val;
nonneg = 1;
cmp_code = GE;
}
else if (add_val == 1 && loop_info->vtop
&& (bl->biv_count == 0
|| no_use_except_counting))
{
add_adjust = 0;
cmp_code = NE;
}
else
return 0;
if (GET_CODE (comparison) == LE)
add_adjust -= add_val;
if (initial_value == const0_rtx
&& GET_CODE (comparison_value) == CONST_INT)
{
if (((unsigned HOST_WIDE_INT) comparison_val % add_val) != 0)
return 0;
}
else
{
if (! no_use_except_counting || add_val != 1)
return 0;
}
final_value = comparison_value;
if (GET_CODE (comparison_value) == CONST_INT
&& GET_CODE (initial_value) == CONST_INT)
{
comparison_value = GEN_INT (comparison_val);
final_value
= GEN_INT (comparison_val + INTVAL (bl->initial_value));
}
bl->initial_value = initial_value;
reg = bl->biv->dest_reg;
jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1);
if (jump_label == pc_rtx)
jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 2);
new_add_val = GEN_INT (- INTVAL (bl->biv->add_val));
if (initial_value == const0_rtx
&& GET_CODE (comparison_value) == CONST_INT)
{
start_value = GEN_INT (comparison_val - add_adjust);
emit_insn_before (gen_move_insn (reg, start_value),
loop_start);
}
else if (GET_CODE (initial_value) == CONST_INT)
{
rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
enum machine_mode mode = GET_MODE (reg);
enum insn_code icode
= add_optab->handlers[(int) mode].insn_code;
if (! (*insn_operand_predicate[icode][0]) (reg, mode)
|| ! ((*insn_operand_predicate[icode][1])
(comparison_value, mode))
|| ! (*insn_operand_predicate[icode][2]) (offset, mode))
return 0;
start_value
= gen_rtx_PLUS (mode, comparison_value, offset);
emit_insn_before ((GEN_FCN (icode)
(reg, comparison_value, offset)),
loop_start);
if (GET_CODE (comparison) == LE)
final_value = gen_rtx_PLUS (mode, comparison_value,
GEN_INT (add_val));
}
else if (! add_adjust)
{
enum machine_mode mode = GET_MODE (reg);
enum insn_code icode
= sub_optab->handlers[(int) mode].insn_code;
if (! (*insn_operand_predicate[icode][0]) (reg, mode)
|| ! ((*insn_operand_predicate[icode][1])
(comparison_value, mode))
|| ! ((*insn_operand_predicate[icode][2])
(initial_value, mode)))
return 0;
start_value
= gen_rtx_MINUS (mode, comparison_value, initial_value);
emit_insn_before ((GEN_FCN (icode)
(reg, comparison_value, initial_value)),
loop_start);
}
else
return 0;
start_sequence ();
expand_inc (reg, new_add_val);
tem = gen_sequence ();
end_sequence ();
p = emit_insn_before (tem, bl->biv->insn);
delete_insn (bl->biv->insn);
bl->biv->insn = p;
bl->initial_value = start_value;
bl->biv->add_val = new_add_val;
loop_info->initial_value = reg;
loop_info->initial_equiv_value = reg;
loop_info->final_value = const0_rtx;
loop_info->final_equiv_value = const0_rtx;
loop_info->comparison_value = const0_rtx;
loop_info->comparison_code = cmp_code;
loop_info->increment = new_add_val;
LABEL_NUSES (XEXP (jump_label, 0)) ++;
if ((REGNO_LAST_UID (bl->regno) != INSN_UID (first_compare))
|| ! bl->init_insn
|| REGNO_FIRST_UID (bl->regno) != INSN_UID (bl->init_insn))
emit_insn_after (gen_move_insn (reg, final_value),
loop_end);
delete_insn (PREV_INSN (loop_end));
if (compare_and_branch == 2)
delete_insn (first_compare);
start_sequence ();
emit_cmp_and_jump_insns (reg, const0_rtx, cmp_code, NULL_RTX,
GET_MODE (reg), 0, 0,
XEXP (jump_label, 0));
tem = gen_sequence ();
end_sequence ();
emit_jump_insn_before (tem, loop_end);
for (tem = PREV_INSN (loop_end);
tem && GET_CODE (tem) != JUMP_INSN;
tem = PREV_INSN (tem))
;
if (tem)
JUMP_LABEL (tem) = XEXP (jump_label, 0);
if (nonneg)
{
if (tem)
{
REG_NOTES (tem) = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX,
REG_NOTES (tem));
}
bl->nonneg = 1;
}
bl->reversed = 1;
if (loop_dump_stream)
{
fprintf (loop_dump_stream, "Reversed loop");
if (bl->nonneg)
fprintf (loop_dump_stream, " and added reg_nonneg\n");
else
fprintf (loop_dump_stream, "\n");
}
return 1;
}
}
}
return 0;
}
static int
maybe_eliminate_biv (bl, loop_start, end, eliminate_p, threshold, insn_count)
struct iv_class *bl;
rtx loop_start;
rtx end;
int eliminate_p;
int threshold, insn_count;
{
rtx reg = bl->biv->dest_reg;
rtx p;
for (p = loop_start; p != end; p = NEXT_INSN (p))
{
enum rtx_code code = GET_CODE (p);
rtx where = threshold >= insn_count ? loop_start : p;
if (GET_RTX_CLASS (code) == 'i')
{
rtx note = find_reg_note (p, REG_LIBCALL, NULL_RTX);
if (note)
{
rtx last = XEXP (note, 0);
rtx set = single_set (last);
if (set && GET_CODE (SET_DEST (set)) == REG)
{
int regno = REGNO (SET_DEST (set));
if (regno < max_reg_before_loop
&& REG_IV_TYPE (regno) == GENERAL_INDUCT
&& REG_IV_INFO (regno)->src_reg == bl->biv->src_reg)
p = last;
}
}
}
if ((code == INSN || code == JUMP_INSN || code == CALL_INSN)
&& reg_mentioned_p (reg, PATTERN (p))
&& ! maybe_eliminate_biv_1 (PATTERN (p), p, bl, eliminate_p, where))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Cannot eliminate biv %d: biv used in insn %d.\n",
bl->regno, INSN_UID (p));
break;
}
}
if (p == end)
{
if (loop_dump_stream)
fprintf (loop_dump_stream, "biv %d %s eliminated.\n",
bl->regno, eliminate_p ? "was" : "can be");
return 1;
}
return 0;
}
int
loop_insn_first_p (insn, reference)
rtx insn, reference;
{
rtx p, q;
for (p = insn, q = reference; ;)
{
if (q == insn || ! p)
return 0;
if (p == reference || ! q)
return 1;
if (INSN_UID (p) < max_uid_for_loop
&& INSN_UID (q) < max_uid_for_loop
&& GET_CODE (p) != NOTE)
return INSN_LUID (p) <= INSN_LUID (q);
if (INSN_UID (p) >= max_uid_for_loop
|| GET_CODE (p) == NOTE)
p = NEXT_INSN (p);
if (INSN_UID (q) >= max_uid_for_loop)
q = NEXT_INSN (q);
}
}
static int
biv_elimination_giv_has_0_offset (biv, giv, insn)
struct induction *biv, *giv;
rtx insn;
{
if (giv->auto_inc_opt
&& ((loop_insn_first_p (giv->insn, insn)
&& loop_insn_first_p (insn, biv->insn))
|| (loop_insn_first_p (biv->insn, insn)
&& loop_insn_first_p (insn, giv->insn))))
return 0;
if (giv->derived_from
&& ! (giv->always_executed
&& loop_insn_first_p (giv->insn, insn)
&& loop_insn_first_p (insn, biv->insn)))
return 0;
if (giv->same
&& giv->same->derived_from
&& ! (giv->same->always_executed
&& loop_insn_first_p (giv->same->insn, insn)
&& loop_insn_first_p (insn, biv->insn)))
return 0;
return 1;
}
static int
maybe_eliminate_biv_1 (x, insn, bl, eliminate_p, where)
rtx x, insn;
struct iv_class *bl;
int eliminate_p;
rtx where;
{
enum rtx_code code = GET_CODE (x);
rtx reg = bl->biv->dest_reg;
enum machine_mode mode = GET_MODE (reg);
struct induction *v;
rtx arg, tem;
#ifdef HAVE_cc0
rtx new;
#endif
int arg_operand;
char *fmt;
int i, j;
switch (code)
{
case REG:
if (x == reg)
return 0;
return 1;
case SET:
if (SET_DEST (x) == reg)
return 1;
for (v = bl->giv; v; v = v->next_iv)
if (v->giv_type == DEST_REG && SET_DEST (x) == v->dest_reg)
return 1;
#ifdef HAVE_cc0
if (SET_DEST (x) == cc0_rtx && SET_SRC (x) == reg)
{
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
&& v->add_val == const0_rtx
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode
&& 0)
{
if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
continue;
if (! eliminate_p)
return 1;
if (INTVAL (v->mult_val) < 0)
new = gen_rtx_COMPARE (GET_MODE (v->new_reg),
const0_rtx, v->new_reg);
else
new = v->new_reg;
if (validate_change (insn, &SET_SRC (x), new, 0))
return 1;
}
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && v->mult_val != const0_rtx
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode
&& (GET_CODE (v->add_val) == SYMBOL_REF
|| GET_CODE (v->add_val) == LABEL_REF
|| GET_CODE (v->add_val) == CONST
|| (GET_CODE (v->add_val) == REG
&& REGNO_POINTER_FLAG (REGNO (v->add_val)))))
{
if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
continue;
if (! eliminate_p)
return 1;
if (INTVAL (v->mult_val) < 0)
new = gen_rtx_COMPARE (VOIDmode, copy_rtx (v->add_val),
v->new_reg);
else
new = gen_rtx_COMPARE (VOIDmode, v->new_reg,
copy_rtx (v->add_val));
update_reg_last_use (v->add_val, insn);
if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
return 1;
tem = gen_reg_rtx (GET_MODE (v->new_reg));
emit_insn_before (gen_move_insn (tem, copy_rtx (v->add_val)),
where);
XEXP (new, (INTVAL (v->mult_val) < 0) ? 0 : 1) = tem;
if (validate_change (insn, &SET_SRC (PATTERN (insn)), new, 0))
return 1;
}
}
#endif
break;
case COMPARE:
case EQ: case NE:
case GT: case GE: case GTU: case GEU:
case LT: case LE: case LTU: case LEU:
if (XEXP (x, 0) == reg)
arg = XEXP (x, 1), arg_operand = 1;
else if (XEXP (x, 1) == reg)
arg = XEXP (x, 0), arg_operand = 0;
else
break;
if (CONSTANT_P (arg))
{
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && 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
|| (GET_CODE (v->add_val) == REG
&& REGNO_POINTER_FLAG (REGNO (v->add_val))))
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode)
{
if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
continue;
if (! eliminate_p)
return 1;
XEXP (x, 1-arg_operand) = v->new_reg;
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;
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))
return 1;
XEXP (x, 1-arg_operand) = reg;
}
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode
&& 0)
{
rtx tem;
if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
continue;
if (! eliminate_p)
return 1;
tem = gen_reg_rtx (mode);
validate_change (insn, &XEXP (x, 1 - arg_operand),
v->new_reg, 1);
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;
}
}
else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
{
if (invariant_p (arg) == 1)
{
for (v = bl->giv; v; v = v->next_iv)
if (CONSTANT_P (v->mult_val) && INTVAL (v->mult_val) > 0
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode
&& 0)
{
rtx tem;
if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
continue;
if (! eliminate_p)
return 1;
tem = gen_reg_rtx (mode);
validate_change (insn, &XEXP (x, 1 - arg_operand),
v->new_reg, 1);
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 0
if (GET_CODE (arg) != REG
|| REG_IV_TYPE (REGNO (arg)) != BASIC_INDUCT)
return 0;
for (v = bl->giv; v; v = v->next_iv)
{
struct induction *tv;
if (v->ignore || v->maybe_dead || v->mode != mode)
continue;
for (tv = reg_biv_class[REGNO (arg)]->giv; tv; tv = tv->next_iv)
if (! tv->ignore && ! tv->maybe_dead
&& rtx_equal_p (tv->mult_val, v->mult_val)
&& rtx_equal_p (tv->add_val, v->add_val)
&& tv->mode == mode)
{
if (! biv_elimination_giv_has_0_offset (bl->biv, v, insn))
continue;
if (! eliminate_p)
return 1;
XEXP (x, 1-arg_operand) = v->new_reg;
XEXP (x, arg_operand) = tv->new_reg;
return 1;
}
}
#endif
}
return 0;
case MEM:
for (v = bl->giv; v; v = v->next_iv)
if (v->giv_type == DEST_ADDR && v->location == &XEXP (x, 0))
return 1;
break;
default:
break;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
switch (fmt[i])
{
case 'e':
if (! maybe_eliminate_biv_1 (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,
eliminate_p, where))
return 0;
break;
}
}
return 1;
}
static int
last_use_this_basic_block (reg, insn)
rtx reg;
rtx insn;
{
rtx n;
for (n = insn;
n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN;
n = NEXT_INSN (n))
{
if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
return 1;
}
return 0;
}
static void
record_initial (dest, set)
rtx dest;
rtx set;
{
struct iv_class *bl;
if (GET_CODE (dest) != REG
|| REGNO (dest) >= max_reg_before_loop
|| REG_IV_TYPE (REGNO (dest)) != BASIC_INDUCT)
return;
bl = reg_biv_class[REGNO (dest)];
if (bl->init_insn == 0)
{
bl->init_insn = note_insn;
bl->init_set = set;
}
}
static void
update_reg_last_use (x, insn)
rtx x;
rtx insn;
{
if (GET_CODE (x) == REG && REGNO (x) < max_reg_before_loop
&& INSN_UID (insn) < max_uid_for_loop
&& uid_luid[REGNO_LAST_UID (REGNO (x))] < uid_luid[INSN_UID (insn)])
REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
else
{
register int i, j;
register char *fmt = GET_RTX_FORMAT (GET_CODE (x));
for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
update_reg_last_use (XEXP (x, i), insn);
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
update_reg_last_use (XVECEXP (x, i, j), insn);
}
}
}
rtx
get_condition (jump, earliest)
rtx jump;
rtx *earliest;
{
enum rtx_code code;
rtx prev = jump;
rtx set;
rtx tem;
rtx op0, op1;
int reverse_code = 0;
int did_reverse_condition = 0;
enum machine_mode mode;
if (GET_CODE (jump) != JUMP_INSN
|| ! condjump_p (jump) || simplejump_p (jump))
return 0;
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 (earliest)
*earliest = jump;
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;
while (GET_RTX_CLASS (code) == '<' && op1 == CONST0_RTX (GET_MODE (op0)))
{
rtx x = 0;
#ifdef HAVE_cc0
if (op0 == cc0_rtx)
{
if ((prev = prev_nonnote_insn (prev)) == 0
|| GET_CODE (prev) != INSN
|| (set = single_set (prev)) == 0
|| SET_DEST (set) != cc0_rtx)
return 0;
op0 = SET_SRC (set);
op1 = CONST0_RTX (GET_MODE (op0));
if (earliest)
*earliest = prev;
}
#endif
if (GET_CODE (op0) == COMPARE)
{
op1 = XEXP (op0, 1);
op0 = XEXP (op0, 0);
continue;
}
else if (GET_CODE (op0) != REG)
break;
if ((prev = prev_nonnote_insn (prev)) == 0
|| GET_CODE (prev) != INSN
|| FIND_REG_INC_NOTE (prev, 0)
|| (set = single_set (prev)) == 0)
break;
if (rtx_equal_p (SET_DEST (set), op0))
{
enum machine_mode inner_mode = GET_MODE (SET_SRC (set));
if ((GET_CODE (SET_SRC (set)) == COMPARE
|| (((code == NE
|| (code == LT
&& GET_MODE_CLASS (inner_mode) == MODE_INT
&& (GET_MODE_BITSIZE (inner_mode)
<= HOST_BITS_PER_WIDE_INT)
&& (STORE_FLAG_VALUE
& ((HOST_WIDE_INT) 1
<< (GET_MODE_BITSIZE (inner_mode) - 1))))
#ifdef FLOAT_STORE_FLAG_VALUE
|| (code == LT
&& GET_MODE_CLASS (inner_mode) == MODE_FLOAT
&& FLOAT_STORE_FLAG_VALUE < 0)
#endif
))
&& GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'))
&& (((GET_MODE_CLASS (mode) == MODE_CC)
== (GET_MODE_CLASS (inner_mode) == MODE_CC))
|| mode == VOIDmode || inner_mode == VOIDmode))
x = SET_SRC (set);
else if (((code == EQ
|| (code == GE
&& (GET_MODE_BITSIZE (inner_mode)
<= HOST_BITS_PER_WIDE_INT)
&& GET_MODE_CLASS (inner_mode) == MODE_INT
&& (STORE_FLAG_VALUE
& ((HOST_WIDE_INT) 1
<< (GET_MODE_BITSIZE (inner_mode) - 1))))
#ifdef FLOAT_STORE_FLAG_VALUE
|| (code == GE
&& GET_MODE_CLASS (inner_mode) == MODE_FLOAT
&& FLOAT_STORE_FLAG_VALUE < 0)
#endif
))
&& GET_RTX_CLASS (GET_CODE (SET_SRC (set))) == '<'
&& (((GET_MODE_CLASS (mode) == MODE_CC)
== (GET_MODE_CLASS (inner_mode) == MODE_CC))
|| mode == VOIDmode || inner_mode == VOIDmode))
{
did_reverse_condition ^= 1;
reverse_code = 1;
x = SET_SRC (set);
}
else
break;
}
else if (reg_set_p (op0, prev))
break;
if (x)
{
if (GET_RTX_CLASS (GET_CODE (x)) == '<')
code = GET_CODE (x);
if (reverse_code)
{
code = reverse_condition (code);
did_reverse_condition ^= 1;
reverse_code = 0;
}
op0 = XEXP (x, 0), op1 = XEXP (x, 1);
if (earliest)
*earliest = prev;
}
}
if (CONSTANT_P (op0))
code = swap_condition (code), tem = op0, op0 = op1, op1 = tem;
if (GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC)
return 0;
if (GET_CODE (op1) == CONST_INT
&& GET_MODE (op0) != VOIDmode
&& GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT)
{
HOST_WIDE_INT const_val = INTVAL (op1);
unsigned HOST_WIDE_INT uconst_val = const_val;
unsigned HOST_WIDE_INT max_val
= (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0));
switch (code)
{
case LE:
if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
code = LT, op1 = GEN_INT (const_val + 1);
break;
case GE:
if ((HOST_WIDE_INT) (const_val & max_val)
!= (((HOST_WIDE_INT) 1
<< (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
code = GT, op1 = GEN_INT (const_val - 1);
break;
case LEU:
if (uconst_val < max_val)
code = LTU, op1 = GEN_INT (uconst_val + 1);
break;
case GEU:
if (uconst_val != 0)
code = GTU, op1 = GEN_INT (uconst_val - 1);
break;
default:
break;
}
}
if (TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
&& did_reverse_condition && code != NE && code != EQ
&& ! flag_fast_math
&& GET_MODE_CLASS (GET_MODE (op0)) == MODE_FLOAT)
return 0;
#ifdef HAVE_cc0
if (op0 == cc0_rtx)
return 0;
#endif
return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
}
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));
}
#ifdef HAVE_decrement_and_branch_on_count
static void
insert_bct (loop_start, loop_end, loop_info)
rtx loop_start, loop_end;
struct loop_info *loop_info;
{
int i;
unsigned HOST_WIDE_INT n_iterations;
int increment_direction, compare_direction;
int add_iteration = 0;
enum machine_mode loop_var_mode = word_mode;
int loop_num = uid_loop_num [INSN_UID (loop_start)];
if (loop_info->unroll_number == -1)
return;
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;
}
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;
}
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;
}
if (loop_has_call)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"insert_bct %d: BCT instrumentation failed: function call in loop\n",
loop_num);
return;
}
if (loop_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;
}
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)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"insert_bct %d: Too few iterations to benefit from BCT optimization\n",
loop_num);
return;
}
if (n_iterations > 0)
{
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;
}
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;
}
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;
}
#if 0
else
{
rtx sequence;
rtx iterations_num_reg;
unsigned HOST_WIDE_INT increment_value_abs
= INTVAL (increment) * increment_direction;
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;
}
start_sequence ();
{
rtx temp_reg;
if (compare_direction > 0)
{
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);
}
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, sdiv_optab,
temp_reg,
GEN_INT (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);
}
return;
#endif
}
static void
instrument_loop_bct (loop_start, loop_end, loop_num_iterations)
rtx loop_start, loop_end;
rtx loop_num_iterations;
{
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);
}
delete_insn (PREV_INSN (loop_end));
start_label = gen_label_rtx ();
emit_label_after (start_label, loop_start);
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);
emit_jump_insn_before (gen_decrement_and_branch_on_count (counter_reg,
start_label),
loop_end);
LABEL_NUSES (start_label)++;
}
}
#endif
static int
indirect_jump_in_function_p (start)
rtx start;
{
rtx insn;
for (insn = start; insn; insn = NEXT_INSN (insn))
if (computed_jump_p (insn))
return 1;
return 0;
}
static int
insert_loop_mem (mem, data)
rtx *mem;
void *data ATTRIBUTE_UNUSED;
{
int i;
rtx m = *mem;
if (m == NULL_RTX)
return 0;
switch (GET_CODE (m))
{
case MEM:
break;
case CONST_DOUBLE:
return -1;
default:
return 0;
}
for (i = 0; i < loop_mems_idx; ++i)
if (rtx_equal_p (m, loop_mems[i].mem))
{
if (GET_MODE (m) != GET_MODE (loop_mems[i].mem))
loop_mems[i].optimize = 0;
return 0;
}
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*)
xrealloc (loop_mems,
loop_mems_allocated * sizeof (loop_mem_info));
}
loop_mems[loop_mems_idx].mem = m;
loop_mems[loop_mems_idx].optimize = (GET_MODE (m) != BLKmode);
loop_mems[loop_mems_idx].reg = NULL_RTX;
++loop_mems_idx;
return 0;
}
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;
int *insn_count;
{
int nregs = max_reg_num ();
load_mems (scan_start, end, loop_top, start);
if (max_reg_num () > nregs)
{
int i;
int old_nregs;
old_nregs = nregs;
nregs = max_reg_num ();
if ((unsigned) nregs > set_in_loop->num_elements)
{
VARRAY_GROW (set_in_loop, nregs);
VARRAY_GROW (n_times_set, nregs);
VARRAY_GROW (may_not_optimize, nregs);
VARRAY_GROW (reg_single_usage, nregs);
}
bzero ((char *) &set_in_loop->data, nregs * sizeof (int));
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,
may_not_optimize, reg_single_usage,
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
for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
VARRAY_CHAR (may_not_optimize, i) = 1;
#endif
bcopy ((char *) (&set_in_loop->data.i[0] + old_nregs),
(char *) (&n_times_set->data.i[0] + old_nregs),
(nregs - old_nregs) * sizeof (int));
}
}
static void
load_mems (scan_start, end, loop_top, start)
rtx scan_start;
rtx end;
rtx loop_top;
rtx start;
{
int maybe_never = 0;
int i;
rtx p;
rtx label = NULL_RTX;
rtx end_label;
if (loop_mems_idx > 0)
{
int next_maybe_never = 0;
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
&& ! (GET_CODE (p) == JUMP_INSN
&& JUMP_LABEL (p) == loop_top
&& NEXT_INSN (NEXT_INSN (p)) == end
&& simplejump_p (p)))
{
if (!condjump_p (p))
maybe_never = 1;
else
next_maybe_never = 1;
}
else if (next_maybe_never)
maybe_never = 1;
}
for (i = 0; i < loop_mems_idx; ++i)
{
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)
loop_mems[i].optimize = 0;
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))
{
loop_mems[i].optimize = 0;
break;
}
mem_list_entry = XEXP (mem_list_entry, 1);
}
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))
{
loop_mems[i].optimize = 0;
break;
}
}
}
if (maybe_never && may_trap_p (mem))
loop_mems[i].optimize = 0;
if (!loop_mems[i].optimize)
continue;
reg = gen_reg_rtx (GET_MODE (mem));
REG_USERVAR_P (reg) = 1;
loop_mems[i].reg = reg;
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))
{
rtx_and_int ri;
ri.r = p;
ri.i = i;
for_each_rtx (&p, replace_loop_mem, &ri);
}
if (!apply_change_group ())
loop_mems[i].optimize = 0;
else
{
rtx set;
set = gen_move_insn (reg, mem);
emit_insn_before (set, start);
if (written)
{
if (label == NULL_RTX)
{
end_label = next_label (end);
label = gen_label_rtx ();
emit_label_after (label, 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);
}
}
}
}
if (label != NULL_RTX)
{
rtx_pair rr;
rr.r1 = end_label;
rr.r2 = label;
for (p = start; p != end; p = NEXT_INSN (p))
{
for_each_rtx (&p, replace_label, &rr);
if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == end_label)
JUMP_LABEL (p) = label;
}
}
}
static int
replace_loop_mem (mem, data)
rtx *mem;
void *data;
{
rtx_and_int *ri;
rtx insn;
int i;
rtx m = *mem;
if (m == NULL_RTX)
return 0;
switch (GET_CODE (m))
{
case MEM:
break;
case CONST_DOUBLE:
return -1;
default:
return 0;
}
ri = (rtx_and_int*) data;
i = ri->i;
if (!rtx_equal_p (loop_mems[i].mem, m))
return 0;
insn = ri->r;
validate_change (insn, mem, loop_mems[i].reg, 1);
return 0;
}
static int
replace_label (x, data)
rtx *x;
void *data;
{
rtx l = *x;
rtx old_label = ((rtx_pair*) data)->r1;
rtx new_label = ((rtx_pair*) data)->r2;
if (l == NULL_RTX)
return 0;
if (GET_CODE (l) != LABEL_REF)
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;
}