#include "config.h"
#include "system.h"
#include "rtl.h"
#include "tm_p.h"
#include "function.h"
#include "expr.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "insn-config.h"
#include "regs.h"
#include "recog.h"
#include "flags.h"
#include "real.h"
#include "loop.h"
#include "cselib.h"
#include "except.h"
#include "toplev.h"
#include "predict.h"
#include "insn-flags.h"
#include "optabs.h"
#ifndef SIMULTANEOUS_PREFETCHES
#define SIMULTANEOUS_PREFETCHES 3
#endif
#ifndef PREFETCH_BLOCK
#define PREFETCH_BLOCK 32
#endif
#ifndef HAVE_prefetch
#define HAVE_prefetch 0
#define CODE_FOR_prefetch 0
#define gen_prefetch(a,b,c) (abort(), NULL_RTX)
#endif
#define MAX_PREFETCHES 100
#define PREFETCH_BLOCKS_BEFORE_LOOP_MAX 6
#define PREFETCH_BLOCKS_BEFORE_LOOP_MIN 2
#ifndef PREFETCH_ONLY_DENSE_MEM
#define PREFETCH_ONLY_DENSE_MEM 1
#endif
#ifndef PREFETCH_DENSE_MEM
#define PREFETCH_DENSE_MEM 220
#endif
#ifndef PREFETCH_NO_LOW_LOOPCNT
#define PREFETCH_NO_LOW_LOOPCNT 1
#endif
#ifndef PREFETCH_LOW_LOOPCNT
#define PREFETCH_LOW_LOOPCNT 32
#endif
#ifndef PREFETCH_NO_CALL
#define PREFETCH_NO_CALL 1
#endif
#ifndef PREFETCH_NO_EXTREME_STRIDE
#define PREFETCH_NO_EXTREME_STRIDE 1
#endif
#ifndef PREFETCH_EXTREME_STRIDE
#define PREFETCH_EXTREME_STRIDE 4096
#endif
#ifndef PREFETCH_EXTREME_DIFFERENCE
#define PREFETCH_EXTREME_DIFFERENCE 4096
#endif
#ifndef PREFETCH_BEFORE_LOOP
#define PREFETCH_BEFORE_LOOP 1
#endif
#ifndef PREFETCH_NO_REVERSE_ORDER
#define PREFETCH_NO_REVERSE_ORDER 1
#endif
#ifndef PREFETCH_CONDITIONAL
#define PREFETCH_CONDITIONAL 1
#endif
#define LOOP_REG_LIFETIME(LOOP, REGNO) \
(((REGNO_LAST_UID (REGNO) > max_uid_for_loop) \
? (INSN_LUID ((LOOP)->end)) \
: (REGNO_LAST_LUID (REGNO))) \
- ((REGNO_FIRST_UID (REGNO) > max_uid_for_loop) \
? (INSN_LUID ((LOOP)->start)) \
: (REGNO_FIRST_LUID (REGNO))))
#define LOOP_REG_GLOBAL_P(LOOP, REGNO) \
((REGNO_LAST_UID (REGNO) > max_uid_for_loop) ? 0 : \
(((REGNO_FIRST_UID (REGNO) > max_uid_for_loop) ? 0 : \
((((REGNO_LAST_LUID (REGNO) > INSN_LUID ((LOOP)->end) \
|| REGNO_FIRST_LUID (REGNO) < INSN_LUID ((LOOP)->start))))))))
#define LOOP_REGNO_NREGS(REGNO, SET_DEST) \
((REGNO) < FIRST_PSEUDO_REGISTER \
? (int) HARD_REGNO_NREGS ((REGNO), GET_MODE (SET_DEST)) : 1)
int *uid_luid;
struct loop **uid_loop;
int max_uid_for_loop;
static int max_luid;
static int max_loop_num;
unsigned int max_reg_before_loop;
static int loop_max_reg;
struct movable
{
rtx insn;
rtx set_src;
rtx set_dest;
rtx dependencies;
int consec;
unsigned int regno;
short lifetime;
short savings;
ENUM_BITFIELD(machine_mode) savemode : 8;
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 insert_temp : 1;
unsigned int is_equiv : 1;
struct movable *match;
struct movable *forces;
struct movable *next;
};
FILE *loop_dump_stream;
static void invalidate_loops_containing_label PARAMS ((rtx));
static void find_and_verify_loops PARAMS ((rtx, struct loops *));
static void mark_loop_jump PARAMS ((rtx, struct loop *));
static void prescan_loop PARAMS ((struct loop *));
static int reg_in_basic_block_p PARAMS ((rtx, rtx));
static int consec_sets_invariant_p PARAMS ((const struct loop *,
rtx, int, rtx));
static int labels_in_range_p PARAMS ((rtx, int));
static void count_one_set PARAMS ((struct loop_regs *, rtx, rtx, rtx *));
static void note_addr_stored PARAMS ((rtx, rtx, void *));
static void note_set_pseudo_multiple_uses PARAMS ((rtx, rtx, void *));
static int loop_reg_used_before_p PARAMS ((const struct loop *, rtx, rtx));
static void scan_loop PARAMS ((struct loop*, int));
#if 0
static void replace_call_address PARAMS ((rtx, rtx, rtx));
#endif
static rtx skip_consec_insns PARAMS ((rtx, int));
static int libcall_benefit PARAMS ((rtx));
static void ignore_some_movables PARAMS ((struct loop_movables *));
static void force_movables PARAMS ((struct loop_movables *));
static void combine_movables PARAMS ((struct loop_movables *,
struct loop_regs *));
static int num_unmoved_movables PARAMS ((const struct loop *));
static int regs_match_p PARAMS ((rtx, rtx, struct loop_movables *));
static int rtx_equal_for_loop_p PARAMS ((rtx, rtx, struct loop_movables *,
struct loop_regs *));
static void add_label_notes PARAMS ((rtx, rtx));
static void move_movables PARAMS ((struct loop *loop, struct loop_movables *,
int, int));
static void loop_movables_add PARAMS((struct loop_movables *,
struct movable *));
static void loop_movables_free PARAMS((struct loop_movables *));
static int count_nonfixed_reads PARAMS ((const struct loop *, rtx));
static void loop_bivs_find PARAMS((struct loop *));
static void loop_bivs_init_find PARAMS((struct loop *));
static void loop_bivs_check PARAMS((struct loop *));
static void loop_givs_find PARAMS((struct loop *));
static void loop_givs_check PARAMS((struct loop *));
static int loop_biv_eliminable_p PARAMS((struct loop *, struct iv_class *,
int, int));
static int loop_giv_reduce_benefit PARAMS((struct loop *, struct iv_class *,
struct induction *, rtx));
static void loop_givs_dead_check PARAMS((struct loop *, struct iv_class *));
static void loop_givs_reduce PARAMS((struct loop *, struct iv_class *));
static void loop_givs_rescan PARAMS((struct loop *, struct iv_class *,
rtx *));
static void loop_ivs_free PARAMS((struct loop *));
static void strength_reduce PARAMS ((struct loop *, int));
static void find_single_use_in_loop PARAMS ((struct loop_regs *, rtx, rtx));
static int valid_initial_value_p PARAMS ((rtx, rtx, int, rtx));
static void find_mem_givs PARAMS ((const struct loop *, rtx, rtx, int, int));
static void record_biv PARAMS ((struct loop *, struct induction *,
rtx, rtx, rtx, rtx, rtx *,
int, int));
static void check_final_value PARAMS ((const struct loop *,
struct induction *));
static void loop_ivs_dump PARAMS((const struct loop *, FILE *, int));
static void loop_iv_class_dump PARAMS((const struct iv_class *, FILE *, int));
static void loop_biv_dump PARAMS((const struct induction *, FILE *, int));
static void loop_giv_dump PARAMS((const struct induction *, FILE *, int));
static void record_giv PARAMS ((const struct loop *, struct induction *,
rtx, rtx, rtx, rtx, rtx, rtx, int,
enum g_types, int, int, rtx *));
static void update_giv_derive PARAMS ((const struct loop *, rtx));
static void check_ext_dependent_givs PARAMS ((struct iv_class *,
struct loop_info *));
static int basic_induction_var PARAMS ((const struct loop *, rtx,
enum machine_mode, rtx, rtx,
rtx *, rtx *, rtx **));
static rtx simplify_giv_expr PARAMS ((const struct loop *, rtx, rtx *, int *));
static int general_induction_var PARAMS ((const struct loop *loop, rtx, rtx *,
rtx *, rtx *, rtx *, int, int *,
enum machine_mode));
static int consec_sets_giv PARAMS ((const struct loop *, int, rtx,
rtx, rtx, rtx *, rtx *, rtx *, rtx *));
static int check_dbra_loop PARAMS ((struct loop *, int));
static rtx express_from_1 PARAMS ((rtx, rtx, rtx));
static rtx combine_givs_p PARAMS ((struct induction *, struct induction *));
static int cmp_combine_givs_stats PARAMS ((const PTR, const PTR));
static void combine_givs PARAMS ((struct loop_regs *, struct iv_class *));
static int product_cheap_p PARAMS ((rtx, rtx));
static int maybe_eliminate_biv PARAMS ((const struct loop *, struct iv_class *,
int, int, int));
static int maybe_eliminate_biv_1 PARAMS ((const struct loop *, rtx, rtx,
struct iv_class *, int,
basic_block, rtx));
static int last_use_this_basic_block PARAMS ((rtx, rtx));
static void record_initial PARAMS ((rtx, rtx, void *));
static void update_reg_last_use PARAMS ((rtx, rtx));
static rtx next_insn_in_loop PARAMS ((const struct loop *, rtx));
static void loop_regs_scan PARAMS ((const struct loop *, int));
static int count_insns_in_loop PARAMS ((const struct loop *));
static void load_mems PARAMS ((const struct loop *));
static int insert_loop_mem PARAMS ((rtx *, void *));
static int replace_loop_mem PARAMS ((rtx *, void *));
static void replace_loop_mems PARAMS ((rtx, rtx, rtx));
static int replace_loop_reg PARAMS ((rtx *, void *));
static void replace_loop_regs PARAMS ((rtx insn, rtx, rtx));
static void note_reg_stored PARAMS ((rtx, rtx, void *));
static void try_copy_prop PARAMS ((const struct loop *, rtx, unsigned int));
static void try_swap_copy_prop PARAMS ((const struct loop *, rtx,
unsigned int));
static int replace_label PARAMS ((rtx *, void *));
static rtx check_insn_for_givs PARAMS((struct loop *, rtx, int, int));
static rtx check_insn_for_bivs PARAMS((struct loop *, rtx, int, int));
static rtx gen_add_mult PARAMS ((rtx, rtx, rtx, rtx));
static void loop_regs_update PARAMS ((const struct loop *, rtx));
static int iv_add_mult_cost PARAMS ((rtx, rtx, rtx, rtx));
static rtx loop_insn_emit_after PARAMS((const struct loop *, basic_block,
rtx, rtx));
static rtx loop_call_insn_emit_before PARAMS((const struct loop *,
basic_block, rtx, rtx));
static rtx loop_call_insn_hoist PARAMS((const struct loop *, rtx));
static rtx loop_insn_sink_or_swim PARAMS((const struct loop *, rtx));
static void loop_dump_aux PARAMS ((const struct loop *, FILE *, int));
static void loop_delete_insns PARAMS ((rtx, rtx));
static HOST_WIDE_INT remove_constant_addition PARAMS ((rtx *));
static rtx gen_load_of_final_value PARAMS ((rtx, rtx));
void debug_ivs PARAMS ((const struct loop *));
void debug_iv_class PARAMS ((const struct iv_class *));
void debug_biv PARAMS ((const struct induction *));
void debug_giv PARAMS ((const struct induction *));
void debug_loop PARAMS ((const struct loop *));
void debug_loops PARAMS ((const struct loops *));
typedef struct rtx_pair
{
rtx r1;
rtx r2;
} rtx_pair;
typedef struct loop_replace_args
{
rtx match;
rtx replacement;
rtx insn;
} loop_replace_args;
#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))
static int indirect_jump_in_function;
static int indirect_jump_in_function_p PARAMS ((rtx));
static int compute_luids PARAMS ((rtx, rtx, int));
static int biv_elimination_giv_has_0_offset PARAMS ((struct induction *,
struct induction *,
rtx));
static int copy_cost;
static int reg_address_cost;
void
init_loop ()
{
rtx reg = gen_rtx_REG (ABI_WORD_MODE, LAST_VIRTUAL_REGISTER + 1);
reg_address_cost = address_cost (reg, SImode);
copy_cost = COSTS_N_INSNS (1);
}
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, flags)
rtx f;
FILE *dumpfile;
int flags;
{
rtx insn;
int i;
struct loops loops_data;
struct loops *loops = &loops_data;
struct loop_info *loops_info;
loop_dump_stream = dumpfile;
init_recog_no_volatile ();
max_reg_before_loop = max_reg_num ();
loop_max_reg = 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;
loops->num = max_loop_num;
max_uid_for_loop = get_max_uid () + 1 + max_loop_num * 32;
uid_luid = (int *) xcalloc (max_uid_for_loop, sizeof (int));
uid_loop = (struct loop **) xcalloc (max_uid_for_loop,
sizeof (struct loop *));
loops->array = (struct loop *)
xcalloc (loops->num, sizeof (struct loop));
find_and_verify_loops (f, loops);
loops_info = xcalloc (loops->num, sizeof (struct loop_info));
for (i = 0; i < loops->num; i++)
loops->array[i].aux = loops_info + i;
reg_scan (f, max_reg_before_loop, 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];
indirect_jump_in_function = indirect_jump_in_function_p (f);
for (i = max_loop_num - 1; i >= 0; i--)
{
struct loop *loop = &loops->array[i];
if (! loop->invalid && loop->end)
scan_loop (loop, flags);
}
end_alias_analysis ();
free (uid_luid);
free (uid_loop);
free (loops_info);
free (loops->array);
}
static rtx
next_insn_in_loop (loop, insn)
const struct loop *loop;
rtx insn;
{
insn = NEXT_INSN (insn);
if (insn == loop->end)
{
if (loop->top)
insn = loop->top;
else
insn = NULL_RTX;
}
if (insn == loop->scan_start)
insn = NULL_RTX;
return insn;
}
static void
scan_loop (loop, flags)
struct loop *loop;
int flags;
{
struct loop_info *loop_info = LOOP_INFO (loop);
struct loop_regs *regs = LOOP_REGS (loop);
int i;
rtx loop_start = loop->start;
rtx loop_end = loop->end;
rtx p;
int maybe_never = 0;
int call_passed = 0;
rtx loop_entry_jump = 0;
int insn_count;
int tem;
rtx temp, update_start, update_end;
rtx set, set1;
struct loop_movables *movables = LOOP_MOVABLES (loop);
int threshold;
int loop_depth = 0;
int in_libcall;
loop->top = 0;
movables->head = 0;
movables->last = 0;
for (p = NEXT_INSN (loop_start);
p != loop_end
&& GET_CODE (p) != CODE_LABEL && ! INSN_P (p)
&& (GET_CODE (p) != NOTE
|| (NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_BEG
&& NOTE_LINE_NUMBER (p) != NOTE_INSN_LOOP_END));
p = NEXT_INSN (p))
;
loop->scan_start = p;
if (NEXT_INSN (loop->end) != 0)
loop->sink = NEXT_INSN (loop->end);
else
loop->sink = emit_note_after (NOTE_INSN_DELETED, loop->end);
prescan_loop (loop);
threshold = (loop_info->has_call ? 1 : 2) * (1 + n_non_fixed_regs);
if (GET_CODE (p) == JUMP_INSN)
{
loop_entry_jump = p;
if (any_uncondjump_p (p)
&& JUMP_LABEL (p) != 0
&& INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, loop_end))
{
loop->top = next_label (loop->scan_start);
loop->scan_start = JUMP_LABEL (p);
}
}
if (INSN_UID (loop->scan_start) >= max_uid_for_loop
|| GET_CODE (loop->scan_start) != CODE_LABEL)
{
if (loop_dump_stream)
fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
INSN_UID (loop_start), INSN_UID (loop_end));
return;
}
loop_regs_scan (loop, loop_info->mems_idx + 16);
insn_count = count_insns_in_loop (loop);
if (loop_dump_stream)
{
fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n",
INSN_UID (loop_start), INSN_UID (loop_end), insn_count);
if (loop->cont)
fprintf (loop_dump_stream, "Continue at insn %d.\n",
INSN_UID (loop->cont));
}
for (in_libcall = 0, p = next_insn_in_loop (loop, loop->scan_start);
p != NULL_RTX;
p = next_insn_in_loop (loop, p))
{
if (in_libcall && INSN_P (p) && find_reg_note (p, REG_RETVAL, NULL_RTX))
in_libcall--;
if (GET_CODE (p) == INSN)
{
temp = find_reg_note (p, REG_LIBCALL, NULL_RTX);
if (temp)
in_libcall++;
if (! in_libcall
&& (set = single_set (p))
&& GET_CODE (SET_DEST (set)) == REG
#ifdef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
&& SET_DEST (set) != pic_offset_table_rtx
#endif
&& ! regs->array[REGNO (SET_DEST (set))].may_not_optimize)
{
int tem1 = 0;
int tem2 = 0;
int move_insn = 0;
int insert_temp = 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 (GET_CODE (PATTERN (p)) == PARALLEL)
{
for (i = 0; i < XVECLEN (PATTERN (p), 0); i++)
{
rtx x = XVECEXP (PATTERN (p), 0, i);
if (GET_CODE (x) == USE)
dependencies
= gen_rtx_EXPR_LIST (VOIDmode, XEXP (x, 0),
dependencies);
}
}
if (
! reg_in_basic_block_p (p, SET_DEST (set))
&& (maybe_never
|| loop_reg_used_before_p (loop, set, p)))
insert_temp = 1;
if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
;
else if (insert_temp
&& (optimize_size || GET_CODE (SET_SRC (set)) == REG
|| (CONSTANT_P (SET_SRC (set))
&& LEGITIMATE_CONSTANT_P (SET_SRC (set)))))
;
else if ((tem = loop_invariant_p (loop, src))
&& (dependencies == 0
|| (tem2
= loop_invariant_p (loop, dependencies)) != 0)
&& (regs->array[REGNO (SET_DEST (set))].set_in_loop == 1
|| (tem1
= consec_sets_invariant_p
(loop, SET_DEST (set),
regs->array[REGNO (SET_DEST (set))].set_in_loop,
p)))
&& ! ((maybe_never || call_passed)
&& may_trap_p (src)))
{
struct movable *m;
int regno = REGNO (SET_DEST (set));
if (loop_info->has_call
&& regs->array[regno].single_usage != 0
&& regs->array[regno].single_usage != const0_rtx
&& REGNO_FIRST_UID (regno) == INSN_UID (p)
&& (REGNO_LAST_UID (regno)
== INSN_UID (regs->array[regno].single_usage))
&& regs->array[regno].set_in_loop == 1
&& GET_CODE (SET_SRC (set)) != ASM_OPERANDS
&& ! side_effects_p (SET_SRC (set))
&& ! find_reg_note (p, REG_RETVAL, NULL_RTX)
&& (! SMALL_REGISTER_CLASSES
|| (! (GET_CODE (SET_SRC (set)) == REG
&& (REGNO (SET_SRC (set))
< FIRST_PSEUDO_REGISTER))))
&& ! modified_between_p (SET_SRC (set), p,
regs->array[regno].single_usage)
&& no_labels_between_p (p,
regs->array[regno].single_usage)
&& validate_replace_rtx (SET_DEST (set), SET_SRC (set),
regs->array[regno].single_usage))
{
REG_NOTES (regs->array[regno].single_usage)
= (replace_rtx
(REG_NOTES (regs->array[regno].single_usage),
SET_DEST (set), copy_rtx (SET_SRC (set))));
delete_insn (p);
for (i = 0; i < LOOP_REGNO_NREGS (regno, SET_DEST (set));
i++)
regs->array[regno+i].set_in_loop = 0;
continue;
}
m = (struct movable *) xmalloc (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
= regs->array[REGNO (SET_DEST (set))].set_in_loop - 1;
m->done = 0;
m->forces = 0;
m->partial = 0;
m->move_insn = move_insn;
m->move_insn_first = 0;
m->insert_temp = insert_temp;
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 = LOOP_REG_GLOBAL_P (loop, regno);
m->match = 0;
m->lifetime = LOOP_REG_LIFETIME (loop, regno);
m->savings = regs->array[regno].n_times_set;
if (find_reg_note (p, REG_RETVAL, NULL_RTX))
m->savings += libcall_benefit (p);
for (i = 0; i < LOOP_REGNO_NREGS (regno, SET_DEST (set)); i++)
regs->array[regno+i].set_in_loop = move_insn ? -2 : -1;
loop_movables_add (movables, 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)))
{
int regno = REGNO (SET_DEST (set));
if (regs->array[regno].set_in_loop == 2)
{
struct movable *m;
m = (struct movable *) xmalloc (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->insert_temp = insert_temp;
m->partial = 1;
m->global = (INSN_UID (p) >= max_uid_for_loop
|| LOOP_REG_GLOBAL_P (loop, regno)
|| (labels_in_range_p
(p, REGNO_FIRST_LUID (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 = LOOP_REG_LIFETIME (loop, regno);
m->savings = 1;
for (i = 0;
i < LOOP_REGNO_NREGS (regno, SET_DEST (set));
i++)
regs->array[regno+i].set_in_loop = -1;
loop_movables_add (movables, m);
}
}
}
}
else if (GET_CODE (p) == CALL_INSN && ! CONST_OR_PURE_CALL_P (p))
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)) == loop_end
&& any_uncondjump_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, regs);
if (!optimize_size
|| (reg_class_size[GENERAL_REGS] > 18 && !loop_info->has_call))
{
move_movables (loop, movables, threshold, insn_count);
if (max_reg_num () > regs->num)
{
loop_regs_scan (loop, 0);
for (update_start = loop_start;
PREV_INSN (update_start)
&& GET_CODE (PREV_INSN (update_start)) != CODE_LABEL;
update_start = PREV_INSN (update_start))
;
update_end = NEXT_INSN (loop_end);
reg_scan_update (update_start, update_end, loop_max_reg);
loop_max_reg = max_reg_num ();
}
}
for (i = 0; i < regs->num; i++)
if (regs->array[i].set_in_loop < 0)
regs->array[i].set_in_loop = regs->array[i].n_times_set;
load_mems (loop);
if (max_reg_num () > regs->num)
loop_regs_scan (loop, 0);
for (update_start = loop_start;
PREV_INSN (update_start)
&& GET_CODE (PREV_INSN (update_start)) != CODE_LABEL;
update_start = PREV_INSN (update_start))
;
update_end = NEXT_INSN (loop_end);
reg_scan_update (update_start, update_end, loop_max_reg);
loop_max_reg = max_reg_num ();
if (flag_strength_reduce)
{
if (update_end && GET_CODE (update_end) == CODE_LABEL)
LABEL_NUSES (update_end)++;
strength_reduce (loop, flags);
reg_scan_update (update_start, update_end, loop_max_reg);
loop_max_reg = max_reg_num ();
if (update_end && GET_CODE (update_end) == CODE_LABEL
&& --LABEL_NUSES (update_end) == 0)
delete_related_insns (update_end);
}
loop_movables_free (movables);
free (regs->array);
regs->array = 0;
regs->num = 0;
}
void
record_excess_regs (in_this, not_in_this, output)
rtx in_this, not_in_this;
rtx *output;
{
enum rtx_code code;
const 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;
}
}
return 1;
}
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 loop_movables *movables;
{
struct movable *m, *m1;
for (m = movables->head; 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->head; m1 != m; m1 = m1->next)
if (m1->insn == insn)
m1->done = 1;
}
}
}
static void
force_movables (movables)
struct loop_movables *movables;
{
struct movable *m, *m1;
for (m1 = movables->head; 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, regs)
struct loop_movables *movables;
struct loop_regs *regs;
{
struct movable *m;
char *matched_regs = (char *) xmalloc (regs->num);
enum machine_mode mode;
for (m = movables->head; m; m = m->next)
if (m->match == 0 && regs->array[m->regno].n_times_set == 1
&& m->regno >= FIRST_PSEUDO_REGISTER
&& !m->insert_temp
&& !m->partial)
{
struct movable *m1;
int regno = m->regno;
memset (matched_regs, 0, regs->num);
matched_regs[regno] = 1;
for (m1 = m->next; m1; m1 = m1->next)
if (m != m1 && m1->match == 0
&& !m1->insert_temp
&& regs->array[m1->regno].n_times_set == 1
&& m1->regno >= FIRST_PSEUDO_REGISTER
&& !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)))))
&& m1->regno >= FIRST_PSEUDO_REGISTER
&& ((GET_CODE (m1->set_src) == REG
&& matched_regs[REGNO (m1->set_src)])
|| rtx_equal_for_loop_p (m->set_src, m1->set_src,
movables, regs))))
&& ((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))
{
struct movable *m0 = 0;
for (m = movables->head; m; m = m->next)
if (m->partial && ! m->global
&& mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn)))))
{
struct movable *m1;
int first = REGNO_FIRST_LUID (m->regno);
int last = REGNO_LAST_LUID (m->regno);
if (m0 == 0)
{
m0 = m;
continue;
}
if (GET_MODE (m->set_dest) != GET_MODE (m0->set_dest))
continue;
for (m1 = movables->head; m1 != m; m1 = m1->next)
if (m1 == m0 || (m1->partial && m1->match == m0))
if (! (REGNO_FIRST_LUID (m1->regno) > last
|| REGNO_LAST_LUID (m1->regno) < first))
goto overlap;
m0->lifetime += m->lifetime;
m0->savings += m->savings;
m->done = 1;
m->match = m0;
overlap:
;
}
}
free (matched_regs);
}
static int
num_unmoved_movables (loop)
const struct loop *loop;
{
int num = 0;
struct movable *m;
for (m = LOOP_MOVABLES (loop)->head; m; m = m->next)
if (!m->done)
++num;
return num;
}
static int
regs_match_p (x, y, movables)
rtx x, y;
struct loop_movables *movables;
{
unsigned int xn = REGNO (x);
unsigned int yn = REGNO (y);
struct movable *mx, *my;
for (mx = movables->head; mx; mx = mx->next)
if (mx->regno == xn)
break;
for (my = movables->head; 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, regs)
rtx x, y;
struct loop_movables *movables;
struct loop_regs *regs;
{
int i;
int j;
struct movable *m;
enum rtx_code code;
const char *fmt;
if (x == y)
return 1;
if (x == 0 || y == 0)
return 0;
code = GET_CODE (x);
if (GET_CODE (x) == REG && regs->array[REGNO (x)].set_in_loop == -2
&& CONSTANT_P (y))
{
for (m = movables->head; 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 && regs->array[REGNO (y)].set_in_loop == -2
&& CONSTANT_P (x))
{
for (m = movables->head; 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, regs) == 0)
return 0;
break;
case 'e':
if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables, regs)
== 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;
const 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_INSN_LIST (REG_LABEL, XEXP (x, 0),
REG_NOTES (insn));
if (LABEL_P (XEXP (x, 0)))
LABEL_NUSES (XEXP (x, 0))++;
}
}
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 (loop, movables, threshold, insn_count)
struct loop *loop;
struct loop_movables *movables;
int threshold;
int insn_count;
{
struct loop_regs *regs = LOOP_REGS (loop);
int nregs = regs->num;
rtx new_start = 0;
struct movable *m;
rtx p;
rtx loop_start = loop->start;
rtx loop_end = loop->end;
rtx *reg_map = (rtx *) xcalloc (nregs, sizeof (rtx));
char *already_moved = (char *) xcalloc (nregs, sizeof (char));
for (m = movables->head; 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));
}
if (!m->done
&& (! m->cond
|| (1 == loop_invariant_p (loop, m->set_src)
&& (m->dependencies == 0
|| 1 == loop_invariant_p (loop, m->dependencies))
&& (m->consec == 0
|| 1 == consec_sets_invariant_p (loop, m->set_dest,
m->consec + 1,
m->insn))))
&& (! m->forces || m->forces->done))
{
int regno;
rtx p;
int savings = m->savings;
p = m->insn;
regno = m->regno;
if (loop_dump_stream)
fprintf (loop_dump_stream, "savings %d ", savings);
if (regs->array[regno].moved_once && loop_dump_stream)
fprintf (loop_dump_stream, "halved since already moved ");
if (already_moved[regno]
|| flag_move_all_movables
|| (threshold * savings * m->lifetime) >=
(regs->array[regno].moved_once ? insn_count * 2 : insn_count)
|| (m->forces && m->forces->done
&& regs->array[m->forces->regno].n_times_set == 1))
{
int count;
struct movable *m1;
rtx first = NULL_RTX;
rtx newreg = NULL_RTX;
if (m->insert_temp)
newreg = gen_reg_rtx (GET_MODE (m->set_dest));
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 = loop_insn_hoist (loop, newpat);
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, seq;
for (count = m->consec; count >= 0; count--)
{
if (GET_CODE (p) != NOTE
&& (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
abort ();
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);
if (m->insert_temp)
{
start_sequence ();
emit_move_insn (m->set_dest, newreg);
seq = get_insns ();
end_sequence ();
emit_insn_before (seq, p);
}
}
start_sequence ();
emit_move_insn (m->insert_temp ? newreg : m->set_dest,
m->set_src);
seq = get_insns ();
end_sequence ();
add_label_notes (m->set_src, seq);
i1 = loop_insn_hoist (loop, seq);
if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
set_unique_reg_note (i1,
m->is_equiv ? REG_EQUIV : REG_EQUAL,
m->set_src);
if (loop_dump_stream)
fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1));
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))
loop_insn_emit_after (loop, 0, fn_address_insn,
gen_move_insn
(fn_reg, fn_address));
if (GET_CODE (temp) == CALL_INSN)
{
i1 = loop_call_insn_hoist (loop, body);
if (CALL_INSN_FUNCTION_USAGE (temp))
CALL_INSN_FUNCTION_USAGE (i1)
= copy_rtx (CALL_INSN_FUNCTION_USAGE (temp));
}
else
i1 = loop_insn_hoist (loop, body);
if (first == 0)
first = i1;
if (temp == fn_address_insn)
fn_address_insn = i1;
REG_NOTES (i1) = REG_NOTES (temp);
REG_NOTES (temp) = NULL;
delete_insn (temp);
}
if (new_start == 0)
new_start = first;
}
if (m->savemode != VOIDmode)
{
rtx reg = m->set_dest;
rtx sequence;
rtx tem;
start_sequence ();
tem = expand_simple_binop
(GET_MODE (reg), AND, 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 = get_insns ();
end_sequence ();
i1 = loop_insn_hoist (loop, sequence);
}
else if (GET_CODE (p) == CALL_INSN)
{
i1 = loop_call_insn_hoist (loop, PATTERN (p));
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)
{
rtx seq;
start_sequence ();
emit_move_insn (m->set_dest, m->set_src);
seq = get_insns ();
end_sequence ();
add_label_notes (m->set_src, seq);
i1 = loop_insn_hoist (loop, seq);
if (! find_reg_note (i1, REG_EQUAL, NULL_RTX))
set_unique_reg_note (i1, m->is_equiv ? REG_EQUIV
: REG_EQUAL, m->set_src);
}
else if (m->insert_temp)
{
rtx *reg_map2 = (rtx *) xcalloc (REGNO (newreg),
sizeof(rtx));
reg_map2 [m->regno] = newreg;
i1 = loop_insn_hoist (loop, copy_rtx (PATTERN (p)));
replace_regs (i1, reg_map2, REGNO (newreg), 1);
free (reg_map2);
}
else
i1 = loop_insn_hoist (loop, PATTERN (p));
if (REG_NOTES (i1) == 0)
{
REG_NOTES (i1) = REG_NOTES (p);
REG_NOTES (p) = NULL;
if ((temp = find_reg_note (i1, REG_EQUAL, NULL_RTX))
&& ! loop_invariant_p (loop, 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);
if (m->insert_temp)
{
rtx seq;
start_sequence ();
emit_move_insn (m->set_dest, newreg);
seq = get_insns ();
end_sequence ();
emit_insn_before (seq, p);
}
}
threshold -= 3;
}
m->done = 1;
if (!m->insert_temp)
{
already_moved[regno] = 1;
regs->array[regno].moved_once = 1;
if (! m->partial)
{
int i;
for (i = 0; i < LOOP_REGNO_NREGS (regno, m->set_dest); i++)
regs->array[regno+i].set_in_loop = 0;
}
if (REGNO_FIRST_UID (regno) > max_uid_for_loop
|| REGNO_FIRST_LUID (regno) > INSN_LUID (loop_start))
REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
if (REGNO_LAST_UID (regno) > max_uid_for_loop
|| REGNO_LAST_LUID (regno) < INSN_LUID (loop_end))
REGNO_LAST_UID (regno) = INSN_UID (loop_end);
}
if (! m->partial)
for (m1 = movables->head; 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)))
delete_insn_chain (XEXP (temp, 0), m1->insn);
else
delete_insn (m1->insn);
already_moved[m1->regno] = 1;
if (! m->partial)
{
int i;
for (i = 0;
i < LOOP_REGNO_NREGS (regno, m1->set_dest);
i++)
regs->array[m1->regno+i].set_in_loop = 0;
}
}
}
else if (loop_dump_stream)
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 != loop_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;
}
free (reg_map);
free (already_moved);
}
static void
loop_movables_add (movables, m)
struct loop_movables *movables;
struct movable *m;
{
if (movables->head == 0)
movables->head = m;
else
movables->last->next = m;
movables->last = m;
}
static void
loop_movables_free (movables)
struct loop_movables *movables;
{
struct movable *m;
struct movable *m_next;
for (m = movables->head; m; m = m_next)
{
m_next = m->next;
free (m);
}
}
#if 0
static void
replace_call_address (x, reg, addr)
rtx x, reg, addr;
{
enum rtx_code code;
int i;
const 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);
else if (fmt[i] == 'E')
{
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 (loop, x)
const struct loop *loop;
rtx x;
{
enum rtx_code code;
int i;
const 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 ((loop_invariant_p (loop, XEXP (x, 0)) != 1)
+ count_nonfixed_reads (loop, 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 (loop, XEXP (x, i));
if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
value += count_nonfixed_reads (loop, XVECEXP (x, i, j));
}
}
return value;
}
static void
prescan_loop (loop)
struct loop *loop;
{
int level = 1;
rtx insn;
struct loop_info *loop_info = LOOP_INFO (loop);
rtx start = loop->start;
rtx end = loop->end;
rtx exit_target = next_nonnote_insn (end);
loop_info->has_indirect_jump = indirect_jump_in_function;
loop_info->pre_header_has_call = 0;
loop_info->has_call = 0;
loop_info->has_nonconst_call = 0;
loop_info->has_prefetch = 0;
loop_info->has_volatile = 0;
loop_info->has_tablejump = 0;
loop_info->has_multiple_exit_targets = 0;
loop->level = 1;
loop_info->unknown_address_altered = 0;
loop_info->unknown_constant_address_altered = 0;
loop_info->store_mems = NULL_RTX;
loop_info->first_loop_store_insn = NULL_RTX;
loop_info->mems_idx = 0;
loop_info->num_mem_sets = 0;
loop_info->preconditioned = NOTE_PRECONDITIONED (end);
for (insn = start; insn && GET_CODE (insn) != CODE_LABEL;
insn = PREV_INSN (insn))
{
if (GET_CODE (insn) == CALL_INSN)
{
loop_info->pre_header_has_call = 1;
break;
}
}
for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
insn = NEXT_INSN (insn))
{
switch (GET_CODE (insn))
{
case NOTE:
if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
{
++level;
loop->level++;
}
else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
--level;
break;
case CALL_INSN:
if (! CONST_OR_PURE_CALL_P (insn))
{
loop_info->unknown_address_altered = 1;
loop_info->has_nonconst_call = 1;
}
else if (pure_call_p (insn) || SIBLING_CALL_P (insn))
loop_info->has_nonconst_call = 1;
loop_info->has_call = 1;
if (can_throw_internal (insn))
loop_info->has_multiple_exit_targets = 1;
break;
case JUMP_INSN:
if (! loop_info->has_multiple_exit_targets)
{
rtx set = pc_set (insn);
if (set)
{
rtx src = SET_SRC (set);
rtx label1, label2;
if (GET_CODE (src) == IF_THEN_ELSE)
{
label1 = XEXP (src, 1);
label2 = XEXP (src, 2);
}
else
{
label1 = src;
label2 = NULL_RTX;
}
do
{
if (label1 && label1 != pc_rtx)
{
if (GET_CODE (label1) != LABEL_REF)
{
loop_info->has_multiple_exit_targets = 1;
break;
}
else if (XEXP (label1, 0) != exit_target
&& LABEL_OUTSIDE_LOOP_P (label1))
{
loop_info->has_multiple_exit_targets = 1;
break;
}
}
label1 = label2;
label2 = NULL_RTX;
}
while (label1);
}
else
{
loop_info->has_multiple_exit_targets = 1;
}
}
case INSN:
if (volatile_refs_p (PATTERN (insn)))
loop_info->has_volatile = 1;
if (GET_CODE (insn) == JUMP_INSN
&& (GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_VEC))
loop_info->has_tablejump = 1;
note_stores (PATTERN (insn), note_addr_stored, loop_info);
if (! loop_info->first_loop_store_insn && loop_info->store_mems)
loop_info->first_loop_store_insn = insn;
if (flag_non_call_exceptions && can_throw_internal (insn))
loop_info->has_multiple_exit_targets = 1;
break;
default:
break;
}
}
if (
! loop_info->has_nonconst_call
&& ! current_function_calls_alloca
&& ! loop_info->has_multiple_exit_targets)
for (insn = NEXT_INSN (start); insn != NEXT_INSN (end);
insn = NEXT_INSN (insn))
for_each_rtx (&insn, insert_loop_mem, loop_info);
if (loop_info->unknown_address_altered)
{
rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
loop_info->store_mems
= gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
}
if (loop_info->unknown_constant_address_altered)
{
rtx mem = gen_rtx_MEM (BLKmode, const0_rtx);
RTX_UNCHANGING_P (mem) = 1;
loop_info->store_mems
= gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
}
}
static void
invalidate_loops_containing_label (label)
rtx label;
{
struct loop *loop;
for (loop = uid_loop[INSN_UID (label)]; loop; loop = loop->outer)
loop->invalid = 1;
}
static void
find_and_verify_loops (f, loops)
rtx f;
struct loops *loops;
{
rtx insn;
rtx label;
int num_loops;
struct loop *current_loop;
struct loop *next_loop;
struct loop *loop;
num_loops = loops->num;
compute_luids (f, NULL_RTX, 0);
uid_loop[0] = NULL;
num_loops = 0;
current_loop = NULL;
for (insn = f; insn; insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) == NOTE)
switch (NOTE_LINE_NUMBER (insn))
{
case NOTE_INSN_LOOP_BEG:
next_loop = loops->array + num_loops;
next_loop->num = num_loops;
num_loops++;
next_loop->start = insn;
next_loop->outer = current_loop;
current_loop = next_loop;
break;
case NOTE_INSN_LOOP_CONT:
current_loop->cont = insn;
break;
case NOTE_INSN_LOOP_VTOP:
current_loop->vtop = insn;
break;
case NOTE_INSN_LOOP_END:
if (! current_loop)
abort ();
current_loop->end = insn;
current_loop = current_loop->outer;
break;
default:
break;
}
if (GET_CODE (insn) == CALL_INSN
&& find_reg_note (insn, REG_SETJMP, NULL))
{
for (loop = current_loop; loop; loop = loop->outer)
{
loop->invalid = 1;
if (loop_dump_stream)
fprintf (loop_dump_stream,
"\nLoop at %d ignored due to setjmp.\n",
INSN_UID (loop->start));
}
}
uid_loop[INSN_UID (insn)] = current_loop;
}
for (label = forced_labels; label; label = XEXP (label, 1))
invalidate_loops_containing_label (XEXP (label, 0));
for_each_eh_label (invalidate_loops_containing_label);
for (insn = f; insn; insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
struct loop *this_loop = uid_loop[INSN_UID (insn)];
if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
{
rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
if (note)
invalidate_loops_containing_label (XEXP (note, 0));
}
if (GET_CODE (insn) != JUMP_INSN)
continue;
mark_loop_jump (PATTERN (insn), this_loop);
if (this_loop
&& (GET_CODE (PATTERN (insn)) == RETURN
|| (any_uncondjump_p (insn)
&& onlyjump_p (insn)
&& (uid_loop[INSN_UID (JUMP_LABEL (insn))]
!= this_loop)))
&& get_max_uid () < max_uid_for_loop)
{
rtx p;
rtx our_next = next_real_insn (insn);
rtx last_insn_to_move = NEXT_INSN (insn);
struct loop *dest_loop;
struct loop *outer_loop = NULL;
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[INSN_UID (JUMP_LABEL (insn))];
if (dest_loop)
{
for (outer_loop = dest_loop; outer_loop;
outer_loop = outer_loop->outer)
if (outer_loop == this_loop)
break;
}
}
if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p)
&& uid_loop[INSN_UID (JUMP_LABEL (p))] != this_loop)
outer_loop = this_loop;
if (! outer_loop
&& GET_CODE (p) == JUMP_INSN
&& JUMP_LABEL (p) != 0
&& INSN_UID (JUMP_LABEL (p)) != 0
&& any_condjump_p (p) && onlyjump_p (p)
&& next_real_insn (JUMP_LABEL (p)) == our_next
&& insns_safe_to_move_p (p, NEXT_INSN (insn),
&last_insn_to_move))
{
rtx target
= JUMP_LABEL (insn) ? JUMP_LABEL (insn) : get_last_insn ();
struct loop *target_loop = uid_loop[INSN_UID (target)];
rtx loc, loc2;
rtx tmp;
for (tmp = last_insn_to_move;
tmp && GET_CODE (tmp) != CODE_LABEL; tmp = NEXT_INSN (tmp))
if (GET_CODE (tmp) == BARRIER)
last_insn_to_move = tmp;
for (loc = target; loc; loc = PREV_INSN (loc))
if (GET_CODE (loc) == BARRIER
&& ((loc2 = next_nonnote_insn (loc)) == 0
|| GET_CODE (loc2) != CODE_LABEL
|| (loc2 = next_nonnote_insn (loc2)) == 0
|| GET_CODE (loc2) != JUMP_INSN
|| (GET_CODE (PATTERN (loc2)) != ADDR_VEC
&& GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
&& uid_loop[INSN_UID (loc)] == target_loop)
break;
if (loc == 0)
for (loc = target; loc; loc = NEXT_INSN (loc))
if (GET_CODE (loc) == BARRIER
&& ((loc2 = next_nonnote_insn (loc)) == 0
|| GET_CODE (loc2) != CODE_LABEL
|| (loc2 = next_nonnote_insn (loc2)) == 0
|| GET_CODE (loc2) != JUMP_INSN
|| (GET_CODE (PATTERN (loc2)) != ADDR_VEC
&& GET_CODE (PATTERN (loc2)) != ADDR_DIFF_VEC))
&& uid_loop[INSN_UID (loc)] == target_loop)
break;
if (loc)
{
rtx cond_label = JUMP_LABEL (p);
rtx new_label = get_label_after (p);
LABEL_NUSES (cond_label)++;
if (invert_jump (p, new_label, 1))
{
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);
}
if (squeeze_notes (&new_label, &last_insn_to_move))
abort ();
reorder_insns (new_label, last_insn_to_move, loc);
for (q = new_label;
q != NEXT_INSN (last_insn_to_move);
q = NEXT_INSN (q))
uid_loop[INSN_UID (q)] = target_loop;
if (JUMP_LABEL (insn))
{
for (q = 0, r = this_loop->exit_labels;
r;
q = r, r = LABEL_NEXTREF (r))
if (XEXP (r, 0) == JUMP_LABEL (insn))
{
LABEL_OUTSIDE_LOOP_P (r) = 0;
if (q)
LABEL_NEXTREF (q) = LABEL_NEXTREF (r);
else
this_loop->exit_labels = LABEL_NEXTREF (r);
break;
}
for (loop = this_loop; loop && loop != target_loop;
loop = loop->outer)
loop->exit_count--;
if (! r)
abort ();
}
mark_loop_jump (PATTERN (p), this_loop);
if (JUMP_LABEL (insn) != 0
&& (next_real_insn (JUMP_LABEL (insn))
== next_real_insn (insn)))
delete_related_insns (insn);
}
insn = NEXT_INSN (cond_label);
if (--LABEL_NUSES (cond_label) == 0)
delete_related_insns (cond_label);
insn = PREV_INSN (insn);
}
}
}
}
}
static void
mark_loop_jump (x, loop)
rtx x;
struct loop *loop;
{
struct loop *dest_loop;
struct loop *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);
return;
case PLUS:
case MINUS:
case MULT:
mark_loop_jump (XEXP (x, 0), loop);
mark_loop_jump (XEXP (x, 1), loop);
return;
case LO_SUM:
mark_loop_jump (XEXP (x, 1), loop);
return;
case SIGN_EXTEND:
case ZERO_EXTEND:
mark_loop_jump (XEXP (x, 0), loop);
return;
case LABEL_REF:
dest_loop = uid_loop[INSN_UID (XEXP (x, 0))];
if (dest_loop)
{
for (outer_loop = dest_loop; outer_loop;
outer_loop = outer_loop->outer)
if (outer_loop == loop)
break;
}
else
outer_loop = NULL;
if (loop && ! outer_loop)
{
LABEL_OUTSIDE_LOOP_P (x) = 1;
LABEL_NEXTREF (x) = loop->exit_labels;
loop->exit_labels = x;
for (outer_loop = loop;
outer_loop && outer_loop != dest_loop;
outer_loop = outer_loop->outer)
outer_loop->exit_count++;
}
if (! dest_loop)
return;
for (; dest_loop; dest_loop = dest_loop->outer)
{
for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
if (dest_loop == outer_loop)
return;
if (loop_dump_stream && ! dest_loop->invalid)
fprintf (loop_dump_stream,
"\nLoop at %d ignored due to multiple entry points.\n",
INSN_UID (dest_loop->start));
dest_loop->invalid = 1;
}
return;
case SET:
if (SET_DEST (x) == pc_rtx)
mark_loop_jump (SET_SRC (x), loop);
return;
case IF_THEN_ELSE:
mark_loop_jump (XEXP (x, 1), loop);
mark_loop_jump (XEXP (x, 2), loop);
return;
case PARALLEL:
case ADDR_VEC:
for (i = 0; i < XVECLEN (x, 0); i++)
mark_loop_jump (XVECEXP (x, 0, i), loop);
return;
case ADDR_DIFF_VEC:
for (i = 0; i < XVECLEN (x, 1); i++)
mark_loop_jump (XVECEXP (x, 1, i), loop);
return;
default:
if (loop)
{
for (outer_loop = loop; outer_loop; outer_loop = outer_loop->outer)
{
if (loop_dump_stream && ! outer_loop->invalid)
fprintf (loop_dump_stream,
"\nLoop at %d ignored due to unknown exit jump.\n",
INSN_UID (outer_loop->start));
outer_loop->invalid = 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, data)
rtx x;
rtx y ATTRIBUTE_UNUSED;
void *data ATTRIBUTE_UNUSED;
{
struct loop_info *loop_info = data;
if (x == 0 || GET_CODE (x) != MEM)
return;
loop_info->num_mem_sets++;
if (GET_MODE (x) == BLKmode)
{
if (RTX_UNCHANGING_P (x))
loop_info->unknown_constant_address_altered = 1;
else
loop_info->unknown_address_altered = 1;
return;
}
loop_info->store_mems = gen_rtx_EXPR_LIST (VOIDmode, x,
loop_info->store_mems);
}
static void
note_set_pseudo_multiple_uses (x, y, data)
rtx x;
rtx y ATTRIBUTE_UNUSED;
void *data;
{
struct loop_regs *regs = (struct loop_regs *) data;
if (x == 0)
return;
while (GET_CODE (x) == STRICT_LOW_PART
|| GET_CODE (x) == SIGN_EXTRACT
|| GET_CODE (x) == ZERO_EXTRACT
|| GET_CODE (x) == SUBREG)
x = XEXP (x, 0);
if (GET_CODE (x) != REG || REGNO (x) < FIRST_PSEUDO_REGISTER)
return;
if (REGNO (x) >= max_reg_before_loop
|| ! regs->array[REGNO (x)].single_usage
|| regs->array[REGNO (x)].single_usage == const0_rtx)
regs->multiple_uses = 1;
}
int
loop_invariant_p (loop, x)
const struct loop *loop;
rtx x;
{
struct loop_info *loop_info = LOOP_INFO (loop);
struct loop_regs *regs = LOOP_REGS (loop);
int i;
enum rtx_code code;
const 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 || x == pic_offset_table_rtx)
&& ! current_function_has_nonlocal_goto)
return 1;
if (LOOP_INFO (loop)->has_call
&& REGNO (x) < FIRST_PSEUDO_REGISTER && call_used_regs[REGNO (x)])
return 0;
if (REGNO (x) >= (unsigned) regs->num)
return 0;
if (regs->array[REGNO (x)].set_in_loop < 0)
return 2;
return regs->array[REGNO (x)].set_in_loop == 0;
case MEM:
if (MEM_VOLATILE_P (x))
return 0;
mem_list_entry = loop_info->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 = loop_invariant_p (loop, XEXP (x, i));
if (tem == 0)
return 0;
if (tem == 2)
conditional = 1;
}
else if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
{
int tem = loop_invariant_p (loop, XVECEXP (x, i, j));
if (tem == 0)
return 0;
if (tem == 2)
conditional = 1;
}
}
}
return 1 + conditional;
}
static int
consec_sets_invariant_p (loop, reg, n_sets, insn)
const struct loop *loop;
int n_sets;
rtx reg, insn;
{
struct loop_regs *regs = LOOP_REGS (loop);
rtx p = insn;
unsigned int regno = REGNO (reg);
rtx temp;
int count = n_sets - 1;
int old = regs->array[regno].set_in_loop;
int value = 0;
int this;
if (n_sets == 127)
return 0;
regs->array[regno].set_in_loop = 0;
while (count > 0)
{
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 = loop_invariant_p (loop, 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)
&& loop_invariant_p (loop, XEXP (temp, 0))));
if (this != 0)
value |= this;
}
}
if (this != 0)
count--;
else if (code != NOTE)
{
regs->array[regno].set_in_loop = old;
return 0;
}
}
regs->array[regno].set_in_loop = old;
return 1 + (value & 2);
}
#if 0
static int
all_sets_invariant_p (reg, insn, table)
rtx reg, insn;
short *table;
{
rtx p = insn;
int regno = REGNO (reg);
while (1)
{
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 (! loop_invariant_p (loop, SET_SRC (PATTERN (p)), table))
return 0;
}
}
}
#endif
static void
find_single_use_in_loop (regs, insn, x)
struct loop_regs *regs;
rtx insn;
rtx x;
{
enum rtx_code code = GET_CODE (x);
const char *fmt = GET_RTX_FORMAT (code);
int i, j;
if (code == REG)
regs->array[REGNO (x)].single_usage
= (regs->array[REGNO (x)].single_usage != 0
&& regs->array[REGNO (x)].single_usage != insn)
? const0_rtx : insn;
else if (code == SET)
{
if (GET_CODE (SET_DEST (x)) != REG)
find_single_use_in_loop (regs, insn, SET_DEST (x));
find_single_use_in_loop (regs, insn, SET_SRC (x));
}
else
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e' && XEXP (x, i) != 0)
find_single_use_in_loop (regs, insn, XEXP (x, i));
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
find_single_use_in_loop (regs, insn, XVECEXP (x, i, j));
}
}
static void
count_one_set (regs, insn, x, last_set)
struct loop_regs *regs;
rtx insn, x;
rtx *last_set;
{
if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
regs->array[REGNO (XEXP (x, 0))].may_not_optimize = 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)
{
int i;
int regno = REGNO (dest);
for (i = 0; i < LOOP_REGNO_NREGS (regno, dest); i++)
{
if (regs->array[regno].set_in_loop > 0
&& last_set == 0)
regs->array[regno+i].may_not_optimize = 1;
if (last_set[regno] != 0
&& reg_used_between_p (dest, last_set[regno], insn))
regs->array[regno+i].may_not_optimize = 1;
if (regs->array[regno+i].set_in_loop < 127)
++regs->array[regno+i].set_in_loop;
last_set[regno+i] = insn;
}
}
}
}
static int
loop_reg_used_before_p (loop, set, insn)
const struct loop *loop;
rtx set, insn;
{
rtx reg = SET_DEST (set);
rtx p;
for (p = loop->scan_start; p != insn; p = NEXT_INSN (p))
{
if (INSN_P (p) && reg_overlap_mentioned_p (reg, PATTERN (p)))
return 1;
if (p == loop->end)
p = loop->start;
}
return 0;
}
struct prefetch_info
{
struct iv_class *class;
struct induction *giv;
rtx base_address;
HOST_WIDE_INT index;
HOST_WIDE_INT stride;
unsigned int bytes_accessed;
unsigned int total_bytes;
int prefetch_in_loop;
int prefetch_before_loop;
unsigned int write : 1;
};
struct check_store_data
{
rtx mem_address;
int mem_write;
};
static void check_store PARAMS ((rtx, rtx, void *));
static void emit_prefetch_instructions PARAMS ((struct loop *));
static int rtx_equal_for_prefetch_p PARAMS ((rtx, rtx));
static void
check_store (x, pat, data)
rtx x, pat ATTRIBUTE_UNUSED;
void *data;
{
struct check_store_data *d = (struct check_store_data *) data;
if ((GET_CODE (x) == MEM) && rtx_equal_p (d->mem_address, XEXP (x, 0)))
d->mem_write = 1;
}
static int
rtx_equal_for_prefetch_p (x, y)
rtx x, y;
{
int i;
int j;
enum rtx_code code = GET_CODE (x);
const char *fmt;
if (x == y)
return 1;
if (code != GET_CODE (y))
return 0;
code = GET_CODE (x);
if (GET_RTX_CLASS (code) == 'c')
{
return ((rtx_equal_for_prefetch_p (XEXP (x, 0), XEXP (y, 0))
&& rtx_equal_for_prefetch_p (XEXP (x, 1), XEXP (y, 1)))
|| (rtx_equal_for_prefetch_p (XEXP (x, 0), XEXP (y, 1))
&& rtx_equal_for_prefetch_p (XEXP (x, 1), XEXP (y, 0))));
}
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_prefetch_p (XVECEXP (x, i, j),
XVECEXP (y, i, j)) == 0)
return 0;
break;
case 'e':
if (rtx_equal_for_prefetch_p (XEXP (x, i), XEXP (y, i)) == 0)
return 0;
break;
case 's':
if (strcmp (XSTR (x, i), XSTR (y, i)))
return 0;
break;
case 'u':
break;
case '0':
break;
default:
abort ();
}
}
return 1;
}
static HOST_WIDE_INT
remove_constant_addition (x)
rtx *x;
{
HOST_WIDE_INT addval = 0;
rtx exp = *x;
if (GET_CODE (exp) == CONST)
{
if (GET_CODE (XEXP (exp, 0)) == PLUS
&& GET_CODE (XEXP (XEXP (exp, 0), 0)) == SYMBOL_REF
&& GET_CODE (XEXP (XEXP (exp, 0), 1)) == CONST_INT)
{
*x = XEXP (XEXP (exp, 0), 0);
return INTVAL (XEXP (XEXP (exp, 0), 1));
}
return 0;
}
if (GET_CODE (exp) == CONST_INT)
{
addval = INTVAL (exp);
*x = const0_rtx;
}
else if (GET_CODE (exp) == PLUS)
{
addval += remove_constant_addition (&XEXP (exp, 0));
addval += remove_constant_addition (&XEXP (exp, 1));
if (XEXP (exp, 0) == const0_rtx)
*x = XEXP (exp, 1);
else if (XEXP (exp, 1) == const0_rtx)
*x = XEXP (exp, 0);
}
return addval;
}
static void
emit_prefetch_instructions (loop)
struct loop *loop;
{
int num_prefetches = 0;
int num_real_prefetches = 0;
int num_real_write_prefetches = 0;
int num_prefetches_before = 0;
int num_write_prefetches_before = 0;
int ahead = 0;
int i;
struct iv_class *bl;
struct induction *iv;
struct prefetch_info info[MAX_PREFETCHES];
struct loop_ivs *ivs = LOOP_IVS (loop);
if (!HAVE_prefetch)
return;
if (PREFETCH_NO_CALL && LOOP_INFO (loop)->has_call)
{
if (loop_dump_stream)
fprintf (loop_dump_stream, "Prefetch: ignoring loop: has call.\n");
return;
}
if (PREFETCH_NO_LOW_LOOPCNT
&& LOOP_INFO (loop)->n_iterations
&& LOOP_INFO (loop)->n_iterations <= PREFETCH_LOW_LOOPCNT)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Prefetch: ignoring loop: not enough iterations.\n");
return;
}
for (bl = ivs->list; bl; bl = bl->next)
{
struct induction *biv = bl->biv, *biv1;
int basestride = 0;
biv1 = biv;
while (biv1)
{
if (GET_CODE (biv->add_val) != CONST_INT)
{
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
"Prefetch: ignoring biv %d: non-constant addition at insn %d:",
REGNO (biv->src_reg), INSN_UID (biv->insn));
print_rtl (loop_dump_stream, biv->add_val);
fprintf (loop_dump_stream, "\n");
}
break;
}
if (biv->maybe_multiple)
{
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
"Prefetch: ignoring biv %d: maybe_multiple at insn %i:",
REGNO (biv->src_reg), INSN_UID (biv->insn));
print_rtl (loop_dump_stream, biv->add_val);
fprintf (loop_dump_stream, "\n");
}
break;
}
basestride += INTVAL (biv1->add_val);
biv1 = biv1->next_iv;
}
if (biv1 || !basestride)
continue;
for (iv = bl->giv; iv; iv = iv->next_iv)
{
rtx address;
rtx temp;
HOST_WIDE_INT index = 0;
int add = 1;
HOST_WIDE_INT stride = 0;
int stride_sign = 1;
struct check_store_data d;
const char *ignore_reason = NULL;
int size = GET_MODE_SIZE (GET_MODE (iv));
if (iv->giv_type != DEST_ADDR)
ignore_reason = "giv is not a destination address";
else if (GET_CODE (iv->mult_val) != CONST_INT)
ignore_reason = "stride is not constant";
else
{
stride = INTVAL (iv->mult_val) * basestride;
if (stride < 0)
{
stride = -stride;
stride_sign = -1;
}
if (PREFETCH_NO_REVERSE_ORDER && stride_sign < 0)
ignore_reason = "reversed order stride";
else if (PREFETCH_NO_EXTREME_STRIDE
&& stride > PREFETCH_EXTREME_STRIDE)
ignore_reason = "extreme stride";
else if (!loop_invariant_p (loop, iv->add_val))
ignore_reason = "giv has varying add value";
else if (iv->maybe_multiple)
ignore_reason = "giv is in nested loop";
}
if (ignore_reason != NULL)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Prefetch: ignoring giv at %d: %s.\n",
INSN_UID (iv->insn), ignore_reason);
continue;
}
address = copy_rtx (iv->add_val);
temp = copy_rtx (bl->initial_value);
address = simplify_gen_binary (PLUS, Pmode, temp, address);
index = remove_constant_addition (&address);
d.mem_write = 0;
d.mem_address = *iv->location;
if (PREFETCH_CONDITIONAL || iv->always_executed)
note_stores (PATTERN (iv->insn), check_store, &d);
else
{
if (loop_dump_stream)
fprintf (loop_dump_stream, "Prefetch: Ignoring giv at %d: %s\n",
INSN_UID (iv->insn), "in conditional code.");
continue;
}
for (i = 0; i < num_prefetches; i++)
if (rtx_equal_for_prefetch_p (address, info[i].base_address)
&& stride == info[i].stride)
{
if (index >= info[i].index
&& index - info[i].index < PREFETCH_EXTREME_DIFFERENCE)
{
info[i].write |= d.mem_write;
info[i].bytes_accessed += size;
info[i].index = index;
info[i].giv = iv;
info[i].class = bl;
info[num_prefetches].base_address = address;
add = 0;
break;
}
if (index < info[i].index
&& info[i].index - index < PREFETCH_EXTREME_DIFFERENCE)
{
info[i].write |= d.mem_write;
info[i].bytes_accessed += size;
add = 0;
break;
}
}
if (add)
{
info[num_prefetches].giv = iv;
info[num_prefetches].class = bl;
info[num_prefetches].index = index;
info[num_prefetches].stride = stride;
info[num_prefetches].base_address = address;
info[num_prefetches].write = d.mem_write;
info[num_prefetches].bytes_accessed = size;
num_prefetches++;
if (num_prefetches >= MAX_PREFETCHES)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Maximal number of prefetches exceeded.\n");
return;
}
}
}
}
for (i = 0; i < num_prefetches; i++)
{
int density;
if (LOOP_INFO (loop)->n_iterations
&& ((unsigned HOST_WIDE_INT) (0xffffffff / info[i].stride)
>= LOOP_INFO (loop)->n_iterations))
info[i].total_bytes = info[i].stride * LOOP_INFO (loop)->n_iterations;
else
info[i].total_bytes = 0xffffffff;
density = info[i].bytes_accessed * 100 / info[i].stride;
if (PREFETCH_ONLY_DENSE_MEM)
if (density * 256 > PREFETCH_DENSE_MEM * 100
&& (info[i].total_bytes / PREFETCH_BLOCK
>= PREFETCH_BLOCKS_BEFORE_LOOP_MIN))
{
info[i].prefetch_before_loop = 1;
info[i].prefetch_in_loop
= (info[i].total_bytes / PREFETCH_BLOCK
> PREFETCH_BLOCKS_BEFORE_LOOP_MAX);
}
else
{
info[i].prefetch_in_loop = 0, info[i].prefetch_before_loop = 0;
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Prefetch: ignoring giv at %d: %d%% density is too low.\n",
INSN_UID (info[i].giv->insn), density);
}
else
info[i].prefetch_in_loop = 1, info[i].prefetch_before_loop = 1;
if (info[i].prefetch_in_loop != 0)
{
info[i].prefetch_in_loop = ((info[i].stride + PREFETCH_BLOCK - 1)
/ PREFETCH_BLOCK);
num_real_prefetches += info[i].prefetch_in_loop;
if (info[i].write)
num_real_write_prefetches += info[i].prefetch_in_loop;
}
}
if (num_real_prefetches != 0)
{
if ((ahead = SIMULTANEOUS_PREFETCHES / num_real_prefetches) == 0)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Prefetch: ignoring prefetches within loop: ahead is zero; %d < %d\n",
SIMULTANEOUS_PREFETCHES, num_real_prefetches);
num_real_prefetches = 0, num_real_write_prefetches = 0;
}
}
if (ahead == 0)
ahead = PREFETCH_BLOCKS_BEFORE_LOOP_MAX;
for (i = 0; i < num_prefetches; i++)
{
if (num_real_prefetches == 0)
info[i].prefetch_in_loop = 0;
if (info[i].prefetch_before_loop != 0)
{
int n = info[i].total_bytes / PREFETCH_BLOCK;
if (n > ahead)
n = ahead;
info[i].prefetch_before_loop = n;
num_prefetches_before += n;
if (info[i].write)
num_write_prefetches_before += n;
}
if (loop_dump_stream)
{
if (info[i].prefetch_in_loop == 0
&& info[i].prefetch_before_loop == 0)
continue;
fprintf (loop_dump_stream, "Prefetch insn: %d",
INSN_UID (info[i].giv->insn));
fprintf (loop_dump_stream,
"; in loop: %d; before: %d; %s\n",
info[i].prefetch_in_loop,
info[i].prefetch_before_loop,
info[i].write ? "read/write" : "read only");
fprintf (loop_dump_stream,
" density: %d%%; bytes_accessed: %u; total_bytes: %u\n",
(int) (info[i].bytes_accessed * 100 / info[i].stride),
info[i].bytes_accessed, info[i].total_bytes);
fprintf (loop_dump_stream, " index: ");
fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, info[i].index);
fprintf (loop_dump_stream, "; stride: ");
fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC, info[i].stride);
fprintf (loop_dump_stream, "; address: ");
print_rtl (loop_dump_stream, info[i].base_address);
fprintf (loop_dump_stream, "\n");
}
}
if (num_real_prefetches + num_prefetches_before > 0)
{
LOOP_INFO (loop)->has_prefetch = 1;
if (loop_dump_stream)
{
fprintf (loop_dump_stream, "Real prefetches needed within loop: %d (write: %d)\n",
num_real_prefetches, num_real_write_prefetches);
fprintf (loop_dump_stream, "Real prefetches needed before loop: %d (write: %d)\n",
num_prefetches_before, num_write_prefetches_before);
}
}
for (i = 0; i < num_prefetches; i++)
{
int y;
for (y = 0; y < info[i].prefetch_in_loop; y++)
{
rtx loc = copy_rtx (*info[i].giv->location);
rtx insn;
int bytes_ahead = PREFETCH_BLOCK * (ahead + y);
rtx before_insn = info[i].giv->insn;
rtx prev_insn = PREV_INSN (info[i].giv->insn);
rtx seq;
if (offsettable_address_p (0, VOIDmode, loc))
loc = plus_constant (loc, bytes_ahead);
else
{
rtx reg = gen_reg_rtx (Pmode);
loop_iv_add_mult_emit_before (loop, loc, const1_rtx,
GEN_INT (bytes_ahead), reg,
0, before_insn);
loc = reg;
}
start_sequence ();
if (! (*insn_data[(int)CODE_FOR_prefetch].operand[0].predicate)
(loc, insn_data[(int)CODE_FOR_prefetch].operand[0].mode))
loc = force_reg (Pmode, loc);
emit_insn (gen_prefetch (loc, GEN_INT (info[i].write),
GEN_INT (3)));
seq = get_insns ();
end_sequence ();
emit_insn_before (seq, before_insn);
insn = NEXT_INSN (prev_insn);
while (insn != before_insn)
{
insn = check_insn_for_givs (loop, insn,
info[i].giv->always_executed,
info[i].giv->maybe_multiple);
insn = NEXT_INSN (insn);
}
}
if (PREFETCH_BEFORE_LOOP)
{
for (y = 0; y < info[i].prefetch_before_loop; y++)
{
rtx reg = gen_reg_rtx (Pmode);
rtx loop_start = loop->start;
rtx init_val = info[i].class->initial_value;
rtx add_val = simplify_gen_binary (PLUS, Pmode,
info[i].giv->add_val,
GEN_INT (y * PREFETCH_BLOCK));
if (GET_MODE (init_val) != Pmode && !CONSTANT_P (init_val))
{
rtx seq;
start_sequence ();
init_val = convert_to_mode (Pmode, init_val, 0);
seq = get_insns ();
end_sequence ();
loop_insn_emit_before (loop, 0, loop_start, seq);
}
loop_iv_add_mult_emit_before (loop, init_val,
info[i].giv->mult_val,
add_val, reg, 0, loop_start);
emit_insn_before (gen_prefetch (reg, GEN_INT (info[i].write),
GEN_INT (3)),
loop_start);
}
}
}
return;
}
static rtx note_insn;
static rtx addr_placeholder;
void
for_each_insn_in_loop (loop, fncall)
struct loop *loop;
loop_insn_callback fncall;
{
int not_every_iteration = 0;
int maybe_multiple = 0;
int past_loop_latch = 0;
int loop_depth = 0;
rtx p;
if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
maybe_multiple = back_branch_in_range_p (loop, loop->scan_start);
for (p = next_insn_in_loop (loop, loop->scan_start);
p != NULL_RTX;
p = next_insn_in_loop (loop, p))
{
p = fncall (loop, p, not_every_iteration, maybe_multiple);
if (GET_CODE (p) == CODE_LABEL)
{
rtx insn = p;
maybe_multiple = 0;
while (1)
{
insn = NEXT_INSN (insn);
if (insn == loop->scan_start)
break;
if (insn == loop->end)
{
if (loop->top != 0)
insn = loop->top;
else
break;
if (insn == loop->scan_start)
break;
}
if (GET_CODE (insn) == JUMP_INSN
&& GET_CODE (PATTERN (insn)) != RETURN
&& (!any_condjump_p (insn)
|| (JUMP_LABEL (insn) != 0
&& JUMP_LABEL (insn) != loop->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
&& any_uncondjump_p (p))
|| (NEXT_INSN (p) == loop->end && any_condjump_p (p)))))
{
rtx label = 0;
for (label = loop->exit_labels; 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;
}
}
static void
loop_bivs_find (loop)
struct loop *loop;
{
struct loop_regs *regs = LOOP_REGS (loop);
struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl, **backbl;
ivs->list = 0;
for_each_insn_in_loop (loop, check_insn_for_bivs);
for (backbl = &ivs->list, bl = *backbl; bl; bl = bl->next)
{
if (REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
|| regs->array[bl->regno].n_times_set != bl->biv_count
|| ! bl->incremented)
{
if (loop_dump_stream)
fprintf (loop_dump_stream, "Biv %d: discarded, %s\n",
bl->regno,
(REG_IV_TYPE (ivs, bl->regno) != BASIC_INDUCT
? "not induction variable"
: (! bl->incremented ? "never incremented"
: "count error")));
REG_IV_TYPE (ivs, bl->regno) = NOT_BASIC_INDUCT;
*backbl = bl->next;
}
else
{
backbl = &bl->next;
if (loop_dump_stream)
fprintf (loop_dump_stream, "Biv %d: verified\n", bl->regno);
}
}
}
static void
loop_bivs_init_find (loop)
struct loop *loop;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
int call_seen;
rtx p;
call_seen = 0;
for (p = loop->start; p && GET_CODE (p) != CODE_LABEL; p = PREV_INSN (p))
{
rtx test;
note_insn = p;
if (GET_CODE (p) == CALL_INSN)
call_seen = 1;
if (INSN_P (p))
note_stores (PATTERN (p), record_initial, ivs);
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 (loop, p)) != 0
&& GET_CODE (XEXP (test, 0)) == REG
&& REGNO (XEXP (test, 0)) < max_reg_before_loop
&& (bl = REG_IV_CLASS (ivs, 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;
}
}
}
static void
loop_bivs_check (loop)
struct loop *loop;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
struct iv_class **backbl;
for (backbl = &ivs->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,
LOOP_INFO (loop)->pre_header_has_call,
loop->start))
{
bl->initial_value = src;
if (loop_dump_stream)
{
print_simple_rtl (loop_dump_stream, src);
fputc ('\n', loop_dump_stream);
}
}
else if (loop_dump_stream)
fprintf (loop_dump_stream, "is complex\n");
}
}
static void
loop_givs_find (loop)
struct loop* loop;
{
for_each_insn_in_loop (loop, check_insn_for_givs);
}
static void
loop_givs_check (loop)
struct loop *loop;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
for (bl = ivs->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 (loop, v);
}
}
static int
loop_biv_eliminable_p (loop, bl, threshold, insn_count)
struct loop *loop;
struct iv_class *bl;
int threshold;
int insn_count;
{
#ifdef HAVE_decrement_and_branch_until_zero
if (bl->nonneg)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Cannot eliminate nonneg biv %d.\n", bl->regno);
return 0;
}
#endif
if ((REGNO_LAST_LUID (bl->regno) < INSN_LUID (loop->end)
&& bl->init_insn
&& INSN_UID (bl->init_insn) < max_uid_for_loop
&& REGNO_FIRST_LUID (bl->regno) >= INSN_LUID (bl->init_insn)
&& ! reg_mentioned_p (bl->biv->dest_reg, SET_SRC (bl->init_set)))
|| (bl->final_value = final_biv_value (loop, bl)))
return maybe_eliminate_biv (loop, bl, 0, threshold, insn_count);
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
"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));
}
return 0;
}
static void
loop_givs_reduce (loop, bl)
struct loop *loop;
struct iv_class *bl;
{
struct induction *v;
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);
#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 (loop->scan_start)
|| (INSN_LUID (bl->biv->insn)
> INSN_LUID (loop->scan_start))))
|| (INSN_LUID (v->insn) < INSN_LUID (loop->scan_start)
&& (INSN_LUID (loop->scan_start)
< INSN_LUID (bl->biv->insn))))
auto_inc_opt = -1;
else
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
&& INSN_P (prev)
&& 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 = NEXT_INSN (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)
loop_iv_add_mult_emit_before (loop, tv->add_val, v->mult_val,
v->new_reg, v->new_reg,
0, insert_before);
else
loop_iv_add_mult_emit_before (loop, tv->add_val, v->mult_val,
v->add_val, v->new_reg,
0, insert_before);
}
loop_iv_add_mult_hoist (loop,
extend_value_for_giv (v, bl->initial_value),
v->mult_val, v->add_val, v->new_reg);
}
}
}
static void
loop_givs_dead_check (loop, bl)
struct loop *loop ATTRIBUTE_UNUSED;
struct iv_class *bl;
{
struct induction *v;
for (v = bl->giv; v; v = v->next_iv)
{
if (v->ignore
|| (v->same && v->same->ignore))
continue;
if (v->giv_type == DEST_REG
&& REGNO_FIRST_UID (REGNO (v->dest_reg)) == INSN_UID (v->insn))
{
struct induction *v1;
for (v1 = bl->giv; v1; v1 = v1->next_iv)
if (REGNO_LAST_UID (REGNO (v->dest_reg)) == INSN_UID (v1->insn))
v->maybe_dead = 1;
}
}
}
static void
loop_givs_rescan (loop, bl, reg_map)
struct loop *loop;
struct iv_class *bl;
rtx *reg_map;
{
struct induction *v;
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 (GET_CODE (v->new_reg) == REG
&& v->giv_type == DEST_REG
&& REG_POINTER (v->dest_reg))
mark_reg_pointer (v->new_reg,
REGNO_POINTER_ALIGN (REGNO (v->dest_reg)));
else if (GET_CODE (v->new_reg) == REG
&& REG_POINTER (v->src_reg))
{
unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->src_reg));
if (align == 0
|| GET_CODE (v->add_val) != CONST_INT
|| INTVAL (v->add_val) % (align / BITS_PER_UNIT) != 0)
align = 0;
mark_reg_pointer (v->new_reg, align);
}
else if (GET_CODE (v->new_reg) == REG
&& GET_CODE (v->add_val) == REG
&& REG_POINTER (v->add_val))
{
unsigned int align = REGNO_POINTER_ALIGN (REGNO (v->add_val));
if (align == 0 || GET_CODE (v->mult_val) != CONST_INT
|| INTVAL (v->mult_val) % (align / BITS_PER_UNIT) != 0)
align = 0;
mark_reg_pointer (v->new_reg, align);
}
else if (GET_CODE (v->new_reg) == REG && v->giv_type == DEST_ADDR)
mark_reg_pointer (v->new_reg, 0);
if (v->giv_type == DEST_ADDR)
validate_change (v->insn, v->location, v->new_reg, 0);
else if (v->replaceable)
{
reg_map[REGNO (v->dest_reg)] = v->new_reg;
}
else
{
rtx original_insn = v->insn;
rtx note;
v->insn = loop_insn_emit_after (loop, 0, original_insn,
gen_move_insn (v->dest_reg,
v->new_reg));
note = find_reg_note (original_insn, REG_EQUAL, NULL_RTX);
if (note)
remove_note (original_insn, note);
}
if (bl->reversed && ! v->replaceable)
loop_iv_add_mult_sink (loop,
extend_value_for_giv (v, bl->initial_value),
v->mult_val, v->add_val, v->dest_reg);
else if (v->final_value)
loop_insn_sink_or_swim (loop,
gen_load_of_final_value (v->dest_reg,
v->final_value));
if (loop_dump_stream)
{
fprintf (loop_dump_stream, "giv at %d reduced to ",
INSN_UID (v->insn));
print_simple_rtl (loop_dump_stream, v->new_reg);
fprintf (loop_dump_stream, "\n");
}
}
}
static int
loop_giv_reduce_benefit (loop, bl, v, test_reg)
struct loop *loop ATTRIBUTE_UNUSED;
struct iv_class *bl;
struct induction *v;
rtx test_reg;
{
int add_cost;
int benefit;
benefit = v->benefit;
PUT_MODE (test_reg, v->mode);
add_cost = iv_add_mult_cost (bl->biv->add_val, v->mult_val,
test_reg, test_reg);
if (! v->replaceable && ! bl->eliminable
&& REG_USERVAR_P (v->dest_reg))
benefit -= copy_cost;
benefit -= add_cost * bl->biv_count;
#ifdef TARGET_POWERPC
if ( v->replaceable && bl->eliminable )
{
int orig_add_cost = iv_add_mult_cost (bl->biv->add_val,
bl->biv->mult_val, test_reg, test_reg);
benefit += orig_add_cost * bl->biv_count;
}
#endif
#ifdef AUTO_INC_DEC
if (v->giv_type == DEST_ADDR
&& benefit >= 0
&& GET_CODE (v->mult_val) == CONST_INT)
{
int size = GET_MODE_SIZE (GET_MODE (v->mem));
if (HAVE_POST_INCREMENT
&& INTVAL (v->mult_val) == size)
benefit += add_cost * bl->biv_count;
else if (HAVE_PRE_INCREMENT
&& INTVAL (v->mult_val) == size)
benefit += add_cost * bl->biv_count;
else if (HAVE_POST_DECREMENT
&& -INTVAL (v->mult_val) == size)
benefit += add_cost * bl->biv_count;
else if (HAVE_PRE_DECREMENT
&& -INTVAL (v->mult_val) == size)
benefit += add_cost * bl->biv_count;
}
#endif
return benefit;
}
static void
loop_ivs_free (loop)
struct loop *loop;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *iv = ivs->list;
free (ivs->regs);
while (iv)
{
struct iv_class *next = iv->next;
struct induction *induction;
struct induction *next_induction;
for (induction = iv->biv; induction; induction = next_induction)
{
next_induction = induction->next_iv;
free (induction);
}
for (induction = iv->giv; induction; induction = next_induction)
{
next_induction = induction->next_iv;
free (induction);
}
free (iv);
iv = next;
}
}
static void
strength_reduce (loop, flags)
struct loop *loop;
int flags;
{
struct loop_info *loop_info = LOOP_INFO (loop);
struct loop_regs *regs = LOOP_REGS (loop);
struct loop_ivs *ivs = LOOP_IVS (loop);
rtx p;
struct iv_class *bl;
int threshold = (loop_info->has_call ? 1 : 2) * (3 + n_non_fixed_regs);
rtx *reg_map = NULL;
int reg_map_size;
int unrolled_insn_copies = 0;
rtx test_reg = gen_rtx_REG (ABI_WORD_MODE, LAST_VIRTUAL_REGISTER + 1);
int insn_count = count_insns_in_loop (loop);
addr_placeholder = gen_reg_rtx (Pmode);
ivs->n_regs = max_reg_before_loop;
ivs->regs = (struct iv *) xcalloc (ivs->n_regs, sizeof (struct iv));
loop_bivs_find (loop);
if (! ivs->list)
{
if (flags & LOOP_UNROLL)
unroll_loop (loop, insn_count, 0);
loop_ivs_free (loop);
return;
}
loop_bivs_init_find (loop);
loop_bivs_check (loop);
loop_givs_find (loop);
loop_iterations (loop);
#ifdef HAVE_prefetch
if (flags & LOOP_PREFETCH)
emit_prefetch_instructions (loop);
#endif
loop_givs_check (loop);
check_dbra_loop (loop, insn_count);
reg_map_size = ivs->n_regs;
reg_map = (rtx *) xcalloc (reg_map_size, sizeof (rtx));
for (bl = ivs->list; bl; bl = bl->next)
{
struct induction *v;
int benefit;
bl->eliminable = loop_biv_eliminable_p (loop, bl, threshold, insn_count);
bl->all_reduced = 1;
check_ext_dependent_givs (bl, loop_info);
combine_givs (regs, bl);
for (v = bl->giv; v; v = v->next_iv)
{
struct induction *tv;
if (v->ignore || v->same)
continue;
benefit = loop_giv_reduce_benefit (loop, bl, v, test_reg);
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;
bl->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;
bl->all_reduced = 0;
break;
}
}
}
loop_givs_dead_check (loop, bl);
loop_givs_reduce (loop, bl);
loop_givs_rescan (loop, bl, reg_map);
for (v = bl->giv; v; v = v->next_iv)
if (! v->maybe_dead && v->same)
v->same->maybe_dead = 0;
if (bl->all_reduced == 1 && bl->eliminable
&& maybe_eliminate_biv (loop, bl, 1, threshold, insn_count))
{
if (bl->final_value && ! bl->reversed)
loop_insn_sink (loop, gen_load_of_final_value (bl->biv->dest_reg,
bl->final_value));
if (loop_dump_stream)
fprintf (loop_dump_stream, "Reg %d: biv eliminated\n",
bl->regno);
}
else if (bl->final_value && ! bl->reversed)
loop_insn_sink (loop, gen_load_of_final_value (bl->biv->dest_reg,
bl->final_value));
}
for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
|| GET_CODE (p) == CALL_INSN)
{
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 (loop_info->n_iterations > 0)
{
unrolled_insn_copies = insn_count - 2;
#ifdef HAVE_cc0
unrolled_insn_copies -= 1;
#endif
unrolled_insn_copies *= loop_info->n_iterations;
unrolled_insn_copies -= 1;
if (unrolled_insn_copies < 0)
unrolled_insn_copies = 0;
}
if ((flags & LOOP_UNROLL)
|| ((flags & LOOP_AUTO_UNROLL)
&& loop_info->n_iterations > 0
&& unrolled_insn_copies <= insn_count))
unroll_loop (loop, insn_count, 1);
#ifdef HAVE_doloop_end
if (HAVE_doloop_end && (flags & LOOP_BCT) && flag_branch_on_count_reg)
doloop_optimize (loop);
#endif
if (flags & LOOP_BCT)
{
unsigned HOST_WIDE_INT n
= loop_info->n_iterations / loop_info->unroll_number;
if (n > 1)
predict_insn (prev_nonnote_insn (loop->end), PRED_LOOP_ITERATIONS,
REG_BR_PROB_BASE - REG_BR_PROB_BASE / n);
}
if (loop_dump_stream)
fprintf (loop_dump_stream, "\n");
loop_ivs_free (loop);
if (reg_map)
free (reg_map);
}
static rtx
check_insn_for_bivs (loop, p, not_every_iteration, maybe_multiple)
struct loop *loop;
rtx p;
int not_every_iteration;
int maybe_multiple;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
rtx set;
rtx dest_reg;
rtx inc_val;
rtx mult_val;
rtx *location;
if (GET_CODE (p) == INSN
&& (set = single_set (p))
&& GET_CODE (SET_DEST (set)) == REG)
{
dest_reg = SET_DEST (set);
if (REGNO (dest_reg) < max_reg_before_loop
&& REGNO (dest_reg) >= FIRST_PSEUDO_REGISTER
&& REG_IV_TYPE (ivs, REGNO (dest_reg)) != NOT_BASIC_INDUCT)
{
if (basic_induction_var (loop, SET_SRC (set),
GET_MODE (SET_SRC (set)),
dest_reg, p, &inc_val, &mult_val,
&location))
{
struct induction *v
= (struct induction *) xmalloc (sizeof (struct induction));
record_biv (loop, v, p, dest_reg, inc_val, mult_val, location,
not_every_iteration, maybe_multiple);
REG_IV_TYPE (ivs, REGNO (dest_reg)) = BASIC_INDUCT;
}
else if (REGNO (dest_reg) < ivs->n_regs)
REG_IV_TYPE (ivs, REGNO (dest_reg)) = NOT_BASIC_INDUCT;
}
}
return p;
}
static rtx
check_insn_for_givs (loop, p, not_every_iteration, maybe_multiple)
struct loop *loop;
rtx p;
int not_every_iteration;
int maybe_multiple;
{
struct loop_regs *regs = LOOP_REGS (loop);
rtx set;
if (GET_CODE (p) == INSN
&& (set = single_set (p))
&& GET_CODE (SET_DEST (set)) == REG
&& ! regs->array[REGNO (SET_DEST (set))].may_not_optimize)
{
rtx src_reg;
rtx dest_reg;
rtx add_val;
rtx mult_val;
rtx ext_val;
int benefit;
rtx regnote = 0;
rtx last_consec_insn;
dest_reg = SET_DEST (set);
if (REGNO (dest_reg) < FIRST_PSEUDO_REGISTER)
return p;
if (
(general_induction_var (loop, SET_SRC (set), &src_reg, &add_val,
&mult_val, &ext_val, 0, &benefit, VOIDmode)
|| ((regnote = find_reg_note (p, REG_EQUAL, NULL_RTX))
&& general_induction_var (loop, XEXP (regnote, 0), &src_reg,
&add_val, &mult_val, &ext_val, 0,
&benefit, VOIDmode)))
&& REGNO (dest_reg) < max_reg_before_loop
&& dest_reg != src_reg
&& (regs->array[REGNO (dest_reg)].n_times_set == 1
|| (benefit = consec_sets_giv (loop, benefit, p,
src_reg, dest_reg,
&add_val, &mult_val, &ext_val,
&last_consec_insn))))
{
struct induction *v
= (struct induction *) xmalloc (sizeof (struct induction));
if (find_reg_note (p, REG_RETVAL, NULL_RTX))
benefit += libcall_benefit (p);
if (regs->array[REGNO (dest_reg)].n_times_set != 1)
p = last_consec_insn;
record_giv (loop, v, p, src_reg, dest_reg, mult_val, add_val,
ext_val, benefit, DEST_REG, not_every_iteration,
maybe_multiple, (rtx*) 0);
}
}
#ifndef DONT_REDUCE_ADDR
if (GET_CODE (p) == INSN)
find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
maybe_multiple);
#endif
if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
|| GET_CODE (p) == CODE_LABEL)
update_giv_derive (loop, p);
return p;
}
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 (loop, x, insn, not_every_iteration, maybe_multiple)
const struct loop *loop;
rtx x;
rtx insn;
int not_every_iteration, maybe_multiple;
{
int i, j;
enum rtx_code code;
const 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;
rtx ext_val;
int benefit;
if (general_induction_var (loop, XEXP (x, 0), &src_reg, &add_val,
&mult_val, &ext_val, 1, &benefit,
GET_MODE (x)))
{
struct induction *v
= (struct induction *) xmalloc (sizeof (struct induction));
record_giv (loop, v, insn, src_reg, addr_placeholder, mult_val,
add_val, ext_val, benefit, DEST_ADDR,
not_every_iteration, maybe_multiple, &XEXP (x, 0));
v->mem = 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 (loop, XEXP (x, i), insn, not_every_iteration,
maybe_multiple);
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
find_mem_givs (loop, XVECEXP (x, i, j), insn, not_every_iteration,
maybe_multiple);
}
static void
record_biv (loop, v, insn, dest_reg, inc_val, mult_val, location,
not_every_iteration, maybe_multiple)
struct loop *loop;
struct induction *v;
rtx insn;
rtx dest_reg;
rtx inc_val;
rtx mult_val;
rtx *location;
int not_every_iteration;
int maybe_multiple;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
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->ext_dependent = NULL_RTX;
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_IV_CLASS (ivs, REGNO (dest_reg));
if (bl == 0)
{
bl = (struct iv_class *) xmalloc (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->final_value = 0;
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 = ivs->list;
ivs->list = bl;
REG_IV_CLASS (ivs, 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)
loop_biv_dump (v, loop_dump_stream, 0);
}
static void
record_giv (loop, v, insn, src_reg, dest_reg, mult_val, add_val, ext_val,
benefit, type, not_every_iteration, maybe_multiple, location)
const struct loop *loop;
struct induction *v;
rtx insn;
rtx src_reg;
rtx dest_reg;
rtx mult_val, add_val, ext_val;
int benefit;
enum g_types type;
int not_every_iteration, maybe_multiple;
rtx *location;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct induction *b;
struct iv_class *bl;
rtx set = single_set (insn);
rtx temp;
temp = simplify_rtx (add_val);
if (temp
&& ! (GET_CODE (add_val) == MULT
&& GET_CODE (temp) == ASHIFT))
add_val = temp;
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->ext_dependent = ext_val;
v->benefit = benefit;
v->location = location;
v->cant_derive = 0;
v->combined_with = 0;
v->maybe_multiple = maybe_multiple;
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;
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 = LOOP_REG_LIFETIME (loop, REGNO (dest_reg));
if (v->lifetime == 0)
v->ignore = 1;
REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
}
bl = REG_IV_CLASS (ivs, 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;
v->not_replaceable = 0;
}
else
{
if (REGNO_FIRST_UID (REGNO (dest_reg)) == INSN_UID (insn)
&& REGNO_LAST_LUID (REGNO (dest_reg))
< INSN_LUID (loop->end)
&& (! not_every_iteration
|| last_use_this_basic_block (dest_reg, insn)))
{
v->replaceable = 1;
v->not_replaceable = 0;
for (b = bl->biv; b; b = b->next_iv)
{
if (INSN_UID (b->insn) >= max_uid_for_loop
|| ((INSN_LUID (b->insn)
>= REGNO_FIRST_LUID (REGNO (dest_reg)))
&& (INSN_LUID (b->insn)
<= REGNO_LAST_LUID (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 (loop, b->insn))
{
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 (CONSTANT_P (add_val))
v->no_const_addval = 0;
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 (CONSTANT_P (XEXP (tem, 1)))
v->no_const_addval = 0;
}
}
if (loop_dump_stream)
loop_giv_dump (v, loop_dump_stream, 0);
}
static void
check_final_value (loop, v)
const struct loop *loop;
struct induction *v;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
rtx final_value = 0;
bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
#if 0
v->replaceable = 0;
#endif
if ((final_value = final_giv_value (loop, v))
&& (v->always_executed
|| last_use_this_basic_block (v->dest_reg, v->insn)))
{
int biv_increment_seen = 0, before_giv_insn = 0;
rtx p = v->insn;
rtx last_giv_use;
v->replaceable = 1;
v->not_replaceable = 0;
last_giv_use = v->insn;
while (1)
{
p = NEXT_INSN (p);
if (p == loop->end)
{
before_giv_insn = 1;
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
&& reg_set_p (v->src_reg, PATTERN (p)))
biv_increment_seen = 1;
if (reg_mentioned_p (v->dest_reg, PATTERN (p)))
{
if (biv_increment_seen || before_giv_insn)
{
v->replaceable = 0;
v->not_replaceable = 1;
break;
}
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 (loop, p)
const struct loop *loop;
rtx p;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
struct induction *biv, *giv;
rtx tem;
int dummy;
for (bl = ivs->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)
{
rtx ext_val_dummy;
tem = 0;
if (biv->mult_val == const1_rtx)
tem = simplify_giv_expr (loop,
gen_rtx_MULT (giv->mode,
biv->add_val,
giv->mult_val),
&ext_val_dummy, &dummy);
if (tem && giv->derive_adjustment)
tem = simplify_giv_expr
(loop,
gen_rtx_PLUS (giv->mode, tem, giv->derive_adjustment),
&ext_val_dummy, &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 (loop, x, mode, dest_reg, p, inc_val, mult_val, location)
const struct loop *loop;
rtx x;
enum machine_mode mode;
rtx dest_reg;
rtx p;
rtx *inc_val;
rtx *mult_val;
rtx **location;
{
enum rtx_code code;
rtx *argp, arg;
rtx insn, set = 0;
code = GET_CODE (x);
*location = NULL;
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 (loop_invariant_p (loop, 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:
return basic_induction_var (loop, SUBREG_REG (x),
GET_MODE (SUBREG_REG (x)),
dest_reg, p, inc_val, mult_val, location);
case REG:
if (rtx_equal_p (dest_reg, x))
return 0;
insn = p;
while (1)
{
rtx dest;
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;
dest = SET_DEST (set);
if (dest == x
|| (GET_CODE (dest) == SUBREG
&& (GET_MODE_SIZE (GET_MODE (dest)) <= UNITS_PER_WORD)
&& (GET_MODE_CLASS (GET_MODE (dest)) == MODE_INT)
&& SUBREG_REG (dest) == x))
return basic_induction_var (loop, 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);
while (GET_CODE (dest) == SIGN_EXTRACT
|| GET_CODE (dest) == ZERO_EXTRACT
|| GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
if (dest == x)
break;
}
case MEM:
if (loop_invariant_p (loop, x) != 1)
return 0;
case CONST_INT:
case SYMBOL_REF:
case CONST:
if (loop->level == 1
&& GET_MODE_CLASS (mode) == GET_MODE_CLASS (GET_MODE (dest_reg))
&& GET_MODE_CLASS (mode) != 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 (loop, 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 (! rtx_equal_p (dest_reg, XEXP (x, 0))
&& set && SET_DEST (set) == XEXP (x, 0)
&& GET_CODE (XEXP (x, 1)) == CONST_INT
&& INTVAL (XEXP (x, 1)) >= 0
&& GET_CODE (SET_SRC (set)) == ASHIFT
&& XEXP (x, 1) == XEXP (SET_SRC (set), 1))
return basic_induction_var (loop, 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 (loop, x, src_reg, add_val, mult_val, ext_val,
is_addr, pbenefit, addr_mode)
const struct loop *loop;
rtx x;
rtx *src_reg;
rtx *add_val;
rtx *mult_val;
rtx *ext_val;
int is_addr;
int *pbenefit;
enum machine_mode addr_mode;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
rtx orig_x = x;
if (loop_invariant_p (loop, x) == 1)
return 0;
*pbenefit = 0;
*ext_val = NULL_RTX;
x = simplify_giv_expr (loop, x, ext_val, pbenefit);
if (x == 0)
return 0;
switch (GET_CODE (x))
{
case USE:
case CONST_INT:
*src_reg = ivs->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)
*pbenefit += address_cost (orig_x, addr_mode) - reg_address_cost;
else
*pbenefit += rtx_cost (orig_x, SET);
return 1;
}
static rtx sge_plus PARAMS ((enum machine_mode, rtx, rtx));
static rtx sge_plus_constant PARAMS ((rtx, rtx));
static rtx
simplify_giv_expr (loop, x, ext_val, benefit)
const struct loop *loop;
rtx x;
rtx *ext_val;
int *benefit;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct loop_regs *regs = LOOP_REGS (loop);
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 (loop, XEXP (x, 0), ext_val, benefit);
arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, 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 (loop,
gen_rtx_PLUS (mode,
XEXP (arg0, 0),
gen_rtx_PLUS (mode,
XEXP (arg0, 1),
arg1)),
ext_val, 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 (loop,
gen_rtx_PLUS (mode,
gen_rtx_PLUS (mode, arg0,
XEXP (arg1, 0)),
XEXP (arg1, 1)),
ext_val, 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 (loop,
gen_rtx_MULT (mode,
XEXP (arg0, 0),
gen_rtx_PLUS (mode,
XEXP (arg0, 1),
XEXP (arg1, 1))),
ext_val, benefit);
case MINUS:
return simplify_giv_expr (loop,
gen_rtx_PLUS (mode,
XEXP (x, 0),
gen_rtx_MULT (mode,
XEXP (x, 1),
constm1_rtx)),
ext_val, benefit);
case MULT:
arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
arg1 = simplify_giv_expr (loop, XEXP (x, 1), ext_val, 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) == MULT)
{
return simplify_giv_expr (loop,
gen_rtx_MULT (mode,
XEXP (arg0, 0),
gen_rtx_MULT (mode,
XEXP (arg0,
1),
arg1)),
ext_val, benefit);
}
else if (GET_CODE (arg0) == PLUS)
{
return simplify_giv_expr (loop,
gen_rtx_PLUS (mode,
gen_rtx_MULT (mode,
XEXP (arg0,
0),
arg1),
gen_rtx_MULT (mode,
XEXP (arg0,
1),
arg1)),
ext_val, benefit);
}
return gen_rtx_USE (mode, gen_rtx_MULT (mode, arg0, arg1));
case MULT:
return simplify_giv_expr (loop,
gen_rtx_MULT (mode,
XEXP (arg0, 0),
gen_rtx_MULT (mode,
XEXP (arg0, 1),
arg1)),
ext_val, benefit);
case PLUS:
return simplify_giv_expr (loop,
gen_rtx_PLUS (mode,
gen_rtx_MULT (mode,
XEXP (arg0, 0),
arg1),
gen_rtx_MULT (mode,
XEXP (arg0, 1),
arg1)),
ext_val, benefit);
default:
abort ();
}
case ASHIFT:
if (GET_CODE (XEXP (x, 1)) != CONST_INT)
return 0;
return
simplify_giv_expr (loop,
gen_rtx_MULT (mode,
XEXP (x, 0),
GEN_INT ((HOST_WIDE_INT) 1
<< INTVAL (XEXP (x, 1)))),
ext_val, benefit);
case NEG:
return simplify_giv_expr (loop,
gen_rtx_MULT (mode, XEXP (x, 0), constm1_rtx),
ext_val, benefit);
case NOT:
return simplify_giv_expr (loop,
gen_rtx_MINUS (mode,
gen_rtx_NEG (mode, XEXP (x, 0)),
const1_rtx),
ext_val, benefit);
case USE:
return x;
case SIGN_EXTEND:
case ZERO_EXTEND:
case TRUNCATE:
if (*ext_val == NULL_RTX)
{
arg0 = simplify_giv_expr (loop, XEXP (x, 0), ext_val, benefit);
if (arg0 && *ext_val == NULL_RTX && GET_CODE (arg0) == REG)
{
*ext_val = gen_rtx_fmt_e (GET_CODE (x), mode, arg0);
return arg0;
}
}
goto do_default;
case REG:
if (REGNO (x) >= max_reg_before_loop)
return 0;
switch (REG_IV_TYPE (ivs, REGNO (x)))
{
case BASIC_INDUCT:
return x;
case GENERAL_INDUCT:
{
struct induction *v = REG_IV_INFO (ivs, REGNO (x));
{
rtx single_use = regs->array[REGNO (x)].single_usage;
if (single_use && single_use != const0_rtx)
*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);
arg0 = simplify_giv_expr (loop, tem, ext_val, benefit);
if (*ext_val)
{
if (!v->ext_dependent)
return arg0;
}
else
{
*ext_val = v->ext_dependent;
return arg0;
}
return 0;
}
default:
do_default:
if (loop_invariant_p (loop, x) == 1)
{
struct movable *m;
struct loop_movables *movables = LOOP_MOVABLES (loop);
for (m = movables->head; m; m = m->next)
if (rtx_equal_p (x, m->set_dest))
{
if (m->match)
return simplify_giv_expr (loop, m->match->set_dest,
ext_val, 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 (loop, tem, ext_val,
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 (loop, XEXP (tem, 0),
ext_val, benefit);
if (tem)
return tem;
}
}
break;
}
}
break;
}
default:
if (GET_CODE (x) == USE)
x = XEXP (x, 0);
if (loop_invariant_p (loop, 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 (loop, first_benefit, p, src_reg, dest_reg,
add_val, mult_val, ext_val, last_consec_insn)
const struct loop *loop;
int first_benefit;
rtx p;
rtx src_reg;
rtx dest_reg;
rtx *add_val;
rtx *mult_val;
rtx *ext_val;
rtx *last_consec_insn;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct loop_regs *regs = LOOP_REGS (loop);
int count;
enum rtx_code code;
int benefit;
rtx temp;
rtx set;
struct induction *v;
if (REG_IV_TYPE (ivs, REGNO (dest_reg)) != UNKNOWN_INDUCT)
return 0;
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;
v->ext_dependent = NULL_RTX;
REG_IV_TYPE (ivs, REGNO (dest_reg)) = GENERAL_INDUCT;
REG_IV_INFO (ivs, REGNO (dest_reg)) = v;
count = regs->array[REGNO (dest_reg)].n_times_set - 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 (loop, SET_SRC (set), &src_reg,
add_val, mult_val, ext_val, 0,
&benefit, VOIDmode)
|| ((temp = find_reg_note (p, REG_EQUAL, NULL_RTX))
&& general_induction_var (loop, XEXP (temp, 0), &src_reg,
add_val, mult_val, ext_val, 0,
&benefit, VOIDmode)))
&& 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 (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
return 0;
}
}
REG_IV_TYPE (ivs, REGNO (dest_reg)) = UNKNOWN_INDUCT;
*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 (CONSTANT_P (a))
{
enum machine_mode mode_a = GET_MODE (a);
enum machine_mode mode_b = GET_MODE (b);
enum machine_mode mode = mode_b == VOIDmode ? mode_a : mode_b;
return simplify_gen_binary (MINUS, mode, b, a);
}
else if (GET_CODE (b) == PLUS)
{
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)
{
if (INTVAL (mult) > 1)
{
rtx g1_add_val = g1->add_val;
if (GET_CODE (g1_add_val) == MULT
&& GET_CODE (XEXP (g1_add_val, 1)) == CONST_INT)
{
HOST_WIDE_INT m;
m = INTVAL (mult) * INTVAL (XEXP (g1_add_val, 1));
g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val),
XEXP (g1_add_val, 0), GEN_INT (m));
}
else
{
g1_add_val = gen_rtx_MULT (GET_MODE (g1_add_val), g1_add_val,
mult);
}
add = express_from_1 (g1_add_val, g2->add_val, const1_rtx);
}
}
if (add == NULL_RTX)
return NULL_RTX;
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 comb, ret;
if (GET_MODE_SIZE (g1->mode) < GET_MODE_SIZE (g2->mode))
return NULL_RTX;
ret = comb = express_from (g1, g2);
if (comb == NULL_RTX)
return NULL_RTX;
if (g1->mode != g2->mode)
ret = gen_lowpart (g2->mode, comb);
if (comb == g1->dest_reg
&& (g1->giv_type == DEST_REG || g2->giv_type == DEST_ADDR))
{
return ret;
}
if (ret != NULL_RTX
&& g2->giv_type == DEST_ADDR
&& memory_address_p (GET_MODE (g2->mem), ret)
#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 ret;
}
return NULL_RTX;
}
static void
check_ext_dependent_givs (bl, loop_info)
struct iv_class *bl;
struct loop_info *loop_info;
{
int ze_ok = 0, se_ok = 0, info_ok = 0;
enum machine_mode biv_mode = GET_MODE (bl->biv->src_reg);
HOST_WIDE_INT start_val;
unsigned HOST_WIDE_INT u_end_val = 0;
unsigned HOST_WIDE_INT u_start_val = 0;
rtx incr = pc_rtx;
struct induction *v;
if (loop_info->n_iterations > 0
&& bl->initial_value
&& GET_CODE (bl->initial_value) == CONST_INT
&& (incr = biv_total_increment (bl))
&& GET_CODE (incr) == CONST_INT
&& HOST_BITS_PER_WIDE_INT >= GET_MODE_BITSIZE (biv_mode))
{
unsigned HOST_WIDE_INT abs_incr, total_incr;
HOST_WIDE_INT s_end_val;
int neg_incr;
info_ok = 1;
start_val = INTVAL (bl->initial_value);
u_start_val = start_val;
neg_incr = 0, abs_incr = INTVAL (incr);
if (INTVAL (incr) < 0)
neg_incr = 1, abs_incr = -abs_incr;
total_incr = abs_incr * loop_info->n_iterations;
if (total_incr / loop_info->n_iterations == abs_incr)
{
unsigned HOST_WIDE_INT u_max;
HOST_WIDE_INT s_max;
u_end_val = start_val + (neg_incr ? -total_incr : total_incr);
s_end_val = u_end_val;
u_max = GET_MODE_MASK (biv_mode);
s_max = u_max >> 1;
if (start_val >= 0
&& (neg_incr
? u_end_val < u_start_val
: u_end_val > u_start_val)
&& (neg_incr
? 1
: u_end_val <= u_max))
{
ze_ok = 1;
}
if (start_val >= -s_max - 1
&& (neg_incr
? s_end_val < start_val
: s_end_val > start_val)
&& (neg_incr
? s_end_val >= -s_max - 1
: s_end_val <= s_max))
{
se_ok = 1;
}
}
}
for (v = bl->giv; v; v = v->next_iv)
if (v->ext_dependent)
{
enum rtx_code code = GET_CODE (v->ext_dependent);
int ok = 0;
switch (code)
{
case SIGN_EXTEND:
ok = se_ok;
break;
case ZERO_EXTEND:
ok = ze_ok;
break;
case TRUNCATE:
if (se_ok && ze_ok)
{
enum machine_mode outer_mode = GET_MODE (v->ext_dependent);
unsigned HOST_WIDE_INT max = GET_MODE_MASK (outer_mode) >> 1;
if (u_start_val <= max && u_end_val <= max)
ok = 1;
}
break;
default:
abort ();
}
if (ok)
{
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
"Verified ext dependent giv at %d of reg %d\n",
INSN_UID (v->insn), bl->regno);
}
}
else
{
if (loop_dump_stream)
{
const char *why;
if (info_ok)
why = "biv iteration values overflowed";
else
{
if (incr == pc_rtx)
incr = biv_total_increment (bl);
if (incr == const1_rtx)
why = "biv iteration info incomplete; incr by 1";
else
why = "biv iteration info incomplete";
}
fprintf (loop_dump_stream,
"Failed ext dependent giv at %d, %s\n",
INSN_UID (v->insn), why);
}
v->ignore = 1;
bl->all_reduced = 0;
}
}
}
rtx
extend_value_for_giv (v, value)
struct induction *v;
rtx value;
{
rtx ext_dep = v->ext_dependent;
if (! ext_dep)
return value;
if (CONSTANT_P (value) && GET_MODE (value) == VOIDmode)
return value;
return gen_rtx_fmt_e (GET_CODE (ext_dep), GET_MODE (ext_dep), value);
}
struct combine_givs_stats
{
int giv_number;
int total_benefit;
};
static int
cmp_combine_givs_stats (xp, yp)
const PTR xp;
const PTR yp;
{
const struct combine_givs_stats * const x =
(const struct combine_givs_stats *) xp;
const struct combine_givs_stats * const y =
(const struct combine_givs_stats *) yp;
int d;
d = y->total_benefit - x->total_benefit;
if (!d)
d = x->giv_number - y->giv_number;
return d;
}
static void
combine_givs (regs, bl)
struct loop_regs *regs;
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 *) xcalloc (giv_count, sizeof (*stats));
can_combine = (rtx *) xcalloc (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 = regs->array[REGNO (g1->dest_reg)].single_usage)
&& 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;
if (g2->giv_type == DEST_ADDR)
g2->benefit = (g2->benefit + reg_address_cost
- address_cost (g2->new_reg,
GET_MODE (g2->mem)));
g1->combined_with++;
g1->lifetime += g2->lifetime;
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; new benefit %d + %d, lifetime %d\n",
INSN_UID (g2->insn), INSN_UID (g1->insn),
g1->benefit, g1_add_benefit, g1->lifetime);
}
}
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;
}
}
free (stats);
free (can_combine);
}
static rtx
gen_add_mult (b, m, a, reg)
rtx b;
rtx m;
rtx a;
rtx reg;
{
rtx seq;
rtx result;
start_sequence ();
result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
if (reg != result)
emit_move_insn (reg, result);
seq = get_insns ();
end_sequence ();
return seq;
}
static void
loop_regs_update (loop, seq)
const struct loop *loop ATTRIBUTE_UNUSED;
rtx seq;
{
rtx insn;
if (seq == NULL_RTX)
return;
if (INSN_P (seq))
{
insn = seq;
while (insn != NULL_RTX)
{
rtx set = single_set (insn);
if (set && GET_CODE (SET_DEST (set)) == REG)
record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
insn = NEXT_INSN (insn);
}
}
else if (GET_CODE (seq) == SET
&& GET_CODE (SET_DEST (seq)) == REG)
record_base_value (REGNO (SET_DEST (seq)), SET_SRC (seq), 0);
}
void
loop_iv_add_mult_emit_before (loop, b, m, a, reg, before_bb, before_insn)
const struct loop *loop;
rtx b;
rtx m;
rtx a;
rtx reg;
basic_block before_bb;
rtx before_insn;
{
rtx seq;
if (! before_insn)
{
loop_iv_add_mult_hoist (loop, b, m, a, reg);
return;
}
seq = gen_add_mult (copy_rtx (b), copy_rtx (m), copy_rtx (a), reg);
update_reg_last_use (a, before_insn);
update_reg_last_use (b, before_insn);
update_reg_last_use (m, before_insn);
loop_regs_update (loop, seq);
loop_insn_emit_before (loop, before_bb, before_insn, seq);
}
void
loop_iv_add_mult_sink (loop, b, m, a, reg)
const struct loop *loop;
rtx b;
rtx m;
rtx a;
rtx reg;
{
rtx seq;
seq = gen_add_mult (copy_rtx (b), copy_rtx (m), copy_rtx (a), reg);
update_reg_last_use (a, loop->sink);
update_reg_last_use (b, loop->sink);
update_reg_last_use (m, loop->sink);
loop_regs_update (loop, seq);
loop_insn_sink (loop, seq);
}
void
loop_iv_add_mult_hoist (loop, b, m, a, reg)
const struct loop *loop;
rtx b;
rtx m;
rtx a;
rtx reg;
{
rtx seq;
seq = gen_add_mult (copy_rtx (b), copy_rtx (m), copy_rtx (a), reg);
loop_regs_update (loop, seq);
loop_insn_hoist (loop, seq);
}
static int
iv_add_mult_cost (b, m, a, reg)
rtx b;
rtx m;
rtx a;
rtx reg;
{
int cost = 0;
rtx last, result;
start_sequence ();
result = expand_mult_add (b, reg, m, a, GET_MODE (reg), 1);
if (reg != result)
emit_move_insn (reg, result);
last = get_last_insn ();
while (last)
{
rtx t = single_set (last);
if (t)
cost += rtx_cost (SET_SRC (t), SET);
last = PREV_INSN (last);
}
end_sequence ();
return cost;
}
static int
product_cheap_p (a, b)
rtx a;
rtx b;
{
rtx tmp;
int win, n_insns;
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;
start_sequence ();
expand_mult (GET_MODE (a), a, b, NULL_RTX, 1);
tmp = get_insns ();
end_sequence ();
win = 1;
if (INSN_P (tmp))
{
n_insns = 0;
while (tmp != NULL_RTX)
{
rtx next = NEXT_INSN (tmp);
if (++n_insns > 3
|| GET_CODE (tmp) != INSN
|| (GET_CODE (PATTERN (tmp)) == SET
&& GET_CODE (SET_SRC (PATTERN (tmp))) == MULT)
|| (GET_CODE (PATTERN (tmp)) == PARALLEL
&& GET_CODE (XVECEXP (PATTERN (tmp), 0, 0)) == SET
&& GET_CODE (SET_SRC (XVECEXP (PATTERN (tmp), 0, 0))) == MULT))
{
win = 0;
break;
}
tmp = next;
}
}
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;
return win;
}
static int
check_dbra_loop (loop, insn_count)
struct loop *loop;
int insn_count;
{
struct loop_info *loop_info = LOOP_INFO (loop);
struct loop_regs *regs = LOOP_REGS (loop);
struct loop_ivs *ivs = LOOP_IVS (loop);
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;
rtx loop_start = loop->start;
rtx loop_end = loop->end;
jump = PREV_INSN (loop_end);
comparison = get_condition_for_loop (loop, jump);
if (comparison == 0)
return 0;
if (!onlyjump_p (jump))
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;
{
rtx jump1;
if ((jump1 = prev_nonnote_insn (first_compare)) != loop->cont)
if (GET_CODE (jump1) == JUMP_INSN)
return 0;
}
for (bl = ivs->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)
{
if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
REG_NOTES (jump)
= gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
REG_NOTES (jump));
bl->nonneg = 1;
return 1;
}
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 (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)
{
if (! find_reg_note (jump, REG_NONNEG, NULL_RTX))
REG_NOTES (jump)
= gen_rtx_EXPR_LIST (REG_NONNEG, bl->biv->dest_reg,
REG_NOTES (jump));
bl->nonneg = 1;
return 1;
}
}
}
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->exit_count
&& !loop_info->has_multiple_exit_targets)
{
rtx bivreg = regno_reg_rtx[bl->regno];
struct iv_class *blt;
no_use_except_counting = 1;
for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
if (INSN_P (p))
{
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_stores (PATTERN (p), note_set_pseudo_multiple_uses,
regs);
if (regs->multiple_uses)
{
no_use_except_counting = 0;
break;
}
}
else if (reg_mentioned_p (bivreg, PATTERN (p)))
{
no_use_except_counting = 0;
break;
}
}
for (blt = ivs->list; blt; blt = blt->next)
if (blt->init_set
&& reg_mentioned_p (bivreg, SET_SRC (blt->init_set)))
{
no_use_except_counting = 0;
break;
}
}
if (no_use_except_counting)
;
else if (loop_info->num_mem_sets <= 1)
{
for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
if (INSN_P (p))
num_nonfixed_reads += count_nonfixed_reads (loop, PATTERN (p));
if (loop_info->num_mem_sets == 1)
{
struct induction *v;
reversible_mem_store = 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,
PATTERN (loop_info->first_loop_store_insn))
&& loop_insn_first_p (loop_info->first_loop_store_insn,
v->insn))
reversible_mem_store = 0;
}
}
}
else
return 0;
if ((num_nonfixed_reads <= 1
&& ! loop_info->has_nonconst_call
&& ! loop_info->has_prefetch
&& ! loop_info->has_volatile
&& reversible_mem_store
&& (bl->giv_count + bl->biv_count + loop_info->num_mem_sets
+ num_unmoved_movables (loop) + compare_and_branch == insn_count)
&& (bl == ivs->list && bl->next == 0))
|| (no_use_except_counting && ! loop_info->has_prefetch))
{
rtx tem;
int regno;
int reg_is_global;
regno = REGNO (SET_DEST (PATTERN (first_compare)));
reg_is_global = LOOP_REG_GLOBAL_P (loop, regno);
if (reg_is_global)
return 0;
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 = 0;
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 (! loop_invariant_p (loop, comparison_value))
return 0;
if (GET_CODE (comparison_value) == CONST_INT)
comparison_val = INTVAL (comparison_value);
initial_value = bl->initial_value;
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->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->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 = condjump_label (PREV_INSN (loop_end));
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);
loop_insn_hoist (loop, gen_move_insn (reg, start_value));
}
else if (GET_CODE (initial_value) == CONST_INT)
{
enum machine_mode mode = GET_MODE (reg);
rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
rtx add_insn = gen_add3_insn (reg, comparison_value, offset);
if (add_insn == 0)
return 0;
start_value
= gen_rtx_PLUS (mode, comparison_value, offset);
loop_insn_hoist (loop, add_insn);
if (GET_CODE (comparison) == LE)
final_value = gen_rtx_PLUS (mode, comparison_value,
GEN_INT (add_val));
}
else if (! add_adjust)
{
enum machine_mode mode = GET_MODE (reg);
rtx sub_insn = gen_sub3_insn (reg, comparison_value,
initial_value);
if (sub_insn == 0)
return 0;
start_value
= gen_rtx_MINUS (mode, comparison_value, initial_value);
loop_insn_hoist (loop, sub_insn);
}
else
return 0;
start_sequence ();
expand_inc (reg, new_add_val);
tem = get_insns ();
end_sequence ();
p = loop_insn_emit_before (loop, 0, bl->biv->insn, tem);
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))
loop_insn_sink (loop, gen_load_of_final_value (reg, final_value));
delete_related_insns (PREV_INSN (loop_end));
if (compare_and_branch == 2)
delete_related_insns (first_compare);
start_sequence ();
emit_cmp_and_jump_insns (reg, const0_rtx, cmp_code, NULL_RTX,
GET_MODE (reg), 0,
XEXP (jump_label, 0));
tem = get_insns ();
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, reg,
REG_NOTES (tem));
}
bl->nonneg = 1;
}
for (p = loop_start; p != loop_end; p = NEXT_INSN (p))
if (INSN_P (p))
{
rtx *pnote;
rtx set = single_set (p);
if (! set
|| GET_CODE (SET_DEST (set)) != REG
|| (size_t) REGNO (SET_DEST (set)) >= ivs->n_regs
|| REG_IV_TYPE (ivs, REGNO (SET_DEST (set))) != GENERAL_INDUCT
|| REG_IV_INFO (ivs, REGNO (SET_DEST (set)))->src_reg != bl->biv->src_reg)
for (pnote = ®_NOTES (p); *pnote;)
{
if (REG_NOTE_KIND (*pnote) == REG_EQUAL
&& reg_mentioned_p (regno_reg_rtx[bl->regno],
XEXP (*pnote, 0)))
*pnote = XEXP (*pnote, 1);
else
pnote = &XEXP (*pnote, 1);
}
}
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 (loop, bl, eliminate_p, threshold, insn_count)
const struct loop *loop;
struct iv_class *bl;
int eliminate_p;
int threshold, insn_count;
{
struct loop_ivs *ivs = LOOP_IVS (loop);
rtx reg = bl->biv->dest_reg;
rtx p;
for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
{
enum rtx_code code = GET_CODE (p);
basic_block where_bb = 0;
rtx where_insn = threshold >= insn_count ? 0 : p;
rtx note;
if (GET_RTX_CLASS (code) == 'i')
{
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)
{
unsigned int regno = REGNO (SET_DEST (set));
if (regno < ivs->n_regs
&& REG_IV_TYPE (ivs, regno) == GENERAL_INDUCT
&& REG_IV_INFO (ivs, 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 (loop, PATTERN (p), p, bl,
eliminate_p, where_bb, where_insn))
{
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 (eliminate_p
&& (note = find_reg_note (p, REG_EQUAL, NULL_RTX)) != NULL_RTX
&& reg_mentioned_p (reg, XEXP (note, 0)))
remove_note (p, note);
}
if (p == loop->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;
return 1;
}
static int
maybe_eliminate_biv_1 (loop, x, insn, bl, eliminate_p, where_bb, where_insn)
const struct loop *loop;
rtx x, insn;
struct iv_class *bl;
int eliminate_p;
basic_block where_bb;
rtx where_insn;
{
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;
const 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 (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx
&& v->add_val == const0_rtx
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode
&& 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 (GET_CODE (v->mult_val) == CONST_INT
&& v->mult_val != const0_rtx
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode
&& (GET_CODE (v->add_val) == SYMBOL_REF
|| GET_CODE (v->add_val) == LABEL_REF
|| GET_CODE (v->add_val) == CONST
|| (GET_CODE (v->add_val) == REG
&& REG_POINTER (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));
loop_insn_emit_before (loop, 0, where_insn,
gen_move_insn (tem,
copy_rtx (v->add_val)));
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 (GET_CODE (v->mult_val) == CONST_INT
&& INTVAL (v->mult_val) > 0
&& (GET_CODE (v->add_val) == SYMBOL_REF
|| GET_CODE (v->add_val) == LABEL_REF
|| GET_CODE (v->add_val) == CONST
|| (GET_CODE (v->add_val) == REG
&& REG_POINTER (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 (GET_CODE (arg) == CONST_INT)
{
rtx add_val;
if (GET_CODE (v->add_val) == CONST_INT)
add_val = v->add_val;
else
add_val = const0_rtx;
if (const_mult_add_overflow_p (arg, v->mult_val,
add_val, mode, 1))
continue;
}
if (! eliminate_p)
return 1;
validate_change (insn, &XEXP (x, 1 - arg_operand), v->new_reg, 1);
if (GET_CODE (arg) == CONST_INT
&& GET_CODE (v->add_val) == CONST_INT)
{
tem = expand_mult_add (arg, NULL_RTX, v->mult_val,
v->add_val, mode, 1);
}
else
{
tem = gen_reg_rtx (mode);
loop_iv_add_mult_emit_before (loop, arg,
v->mult_val, v->add_val,
tem, where_bb, where_insn);
}
validate_change (insn, &XEXP (x, arg_operand), tem, 1);
if (apply_change_group ())
return 1;
}
for (v = bl->giv; v; v = v->next_iv)
if (GET_CODE (v->mult_val) == CONST_INT
&& INTVAL (v->mult_val) > 0
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode
&& 0)
{
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);
loop_iv_add_mult_emit_before (loop, arg,
v->mult_val, v->add_val,
tem, where_bb, where_insn);
validate_change (insn, &XEXP (x, arg_operand), tem, 1);
if (apply_change_group ())
return 1;
}
}
else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM)
{
if (loop_invariant_p (loop, arg) == 1)
{
for (v = bl->giv; v; v = v->next_iv)
if (GET_CODE (v->mult_val) == CONST_INT && INTVAL (v->mult_val) > 0
&& ! v->ignore && ! v->maybe_dead && v->always_computable
&& v->mode == mode
&& 0)
{
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);
loop_iv_add_mult_emit_before (loop, arg,
v->mult_val, v->add_val,
tem, where_bb, where_insn);
validate_change (insn, &XEXP (x, arg_operand), tem, 1);
if (apply_change_group ())
return 1;
}
}
#if 0
if (GET_CODE (arg) != REG
|| REG_IV_TYPE (ivs, 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_IV_CLASS (ivs, REGNO (arg))->giv; tv;
tv = tv->next_iv)
if (! tv->ignore && ! tv->maybe_dead
&& rtx_equal_p (tv->mult_val, v->mult_val)
&& 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 (loop, XEXP (x, i), insn, bl,
eliminate_p, where_bb, where_insn))
return 0;
break;
case 'E':
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
if (! maybe_eliminate_biv_1 (loop, XVECEXP (x, i, j), insn, bl,
eliminate_p, where_bb, where_insn))
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, data)
rtx dest;
rtx set;
void *data ATTRIBUTE_UNUSED;
{
struct loop_ivs *ivs = (struct loop_ivs *) data;
struct iv_class *bl;
if (GET_CODE (dest) != REG
|| REGNO (dest) >= ivs->n_regs
|| REG_IV_TYPE (ivs, REGNO (dest)) != BASIC_INDUCT)
return;
bl = REG_IV_CLASS (ivs, 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
&& REGNO_LAST_LUID (REGNO (x)) < INSN_LUID (insn))
{
REGNO_LAST_UID (REGNO (x)) = INSN_UID (insn);
}
else
{
int i, j;
const char *fmt = GET_RTX_FORMAT (GET_CODE (x));
for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
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
canonicalize_condition (insn, cond, reverse, earliest, want_reg)
rtx insn;
rtx cond;
int reverse;
rtx *earliest;
rtx want_reg;
{
enum rtx_code code;
rtx prev = insn;
rtx set;
rtx tem;
rtx op0, op1;
int reverse_code = 0;
enum machine_mode mode;
code = GET_CODE (cond);
mode = GET_MODE (cond);
op0 = XEXP (cond, 0);
op1 = XEXP (cond, 1);
if (reverse)
code = reversed_comparison_code (cond, insn);
if (code == UNKNOWN)
return 0;
if (earliest)
*earliest = insn;
while (GET_RTX_CLASS (code) == '<'
&& op1 == CONST0_RTX (GET_MODE (op0))
&& op0 != want_reg)
{
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, NULL_RTX))
break;
set = set_of (op0, prev);
if (set
&& (GET_CODE (set) != SET
|| !rtx_equal_p (SET_DEST (set), op0)))
break;
if (set)
{
enum machine_mode inner_mode = GET_MODE (SET_DEST (set));
#ifdef FLOAT_STORE_FLAG_VALUE
REAL_VALUE_TYPE fsfv;
#endif
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
&& (fsfv = FLOAT_STORE_FLAG_VALUE (inner_mode),
REAL_VALUE_NEGATIVE (fsfv)))
#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
&& (fsfv = FLOAT_STORE_FLAG_VALUE (inner_mode),
REAL_VALUE_NEGATIVE (fsfv)))
#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))
{
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 = reversed_comparison_code (x, prev);
if (code == UNKNOWN)
return 0;
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_mode (const_val + 1, GET_MODE (op0));
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_mode (const_val - 1, GET_MODE (op0));
break;
case LEU:
if (uconst_val < max_val)
code = LTU, op1 = gen_int_mode (uconst_val + 1, GET_MODE (op0));
break;
case GEU:
if (uconst_val != 0)
code = GTU, op1 = gen_int_mode (uconst_val - 1, GET_MODE (op0));
break;
default:
break;
}
}
#ifdef HAVE_cc0
if (op0 == cc0_rtx)
return 0;
#endif
return gen_rtx_fmt_ee (code, VOIDmode, op0, op1);
}
rtx
get_condition (jump, earliest)
rtx jump;
rtx *earliest;
{
rtx cond;
int reverse;
rtx set;
if (GET_CODE (jump) != JUMP_INSN
|| ! any_condjump_p (jump))
return 0;
set = pc_set (jump);
cond = XEXP (SET_SRC (set), 0);
reverse
= GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
&& XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump);
return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
}
rtx
get_condition_for_loop (loop, x)
const struct loop *loop;
rtx x;
{
rtx comparison = get_condition (x, (rtx*) 0);
if (comparison == 0
|| ! loop_invariant_p (loop, XEXP (comparison, 0))
|| loop_invariant_p (loop, XEXP (comparison, 1)))
return comparison;
return gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)), VOIDmode,
XEXP (comparison, 1), XEXP (comparison, 0));
}
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;
{
struct loop_info *loop_info = data;
int i;
rtx m = *mem;
if (m == NULL_RTX)
return 0;
switch (GET_CODE (m))
{
case MEM:
break;
case CLOBBER:
return -1;
case CONST_DOUBLE:
return -1;
case EXPR_LIST:
return -1;
default:
return 0;
}
for (i = 0; i < loop_info->mems_idx; ++i)
if (rtx_equal_p (m, loop_info->mems[i].mem))
{
if (GET_MODE (m) != GET_MODE (loop_info->mems[i].mem))
loop_info->mems[i].optimize = 0;
return 0;
}
if (loop_info->mems_idx == loop_info->mems_allocated)
{
if (loop_info->mems_allocated != 0)
loop_info->mems_allocated *= 2;
else
loop_info->mems_allocated = 32;
loop_info->mems = (loop_mem_info *)
xrealloc (loop_info->mems,
loop_info->mems_allocated * sizeof (loop_mem_info));
}
loop_info->mems[loop_info->mems_idx].mem = m;
loop_info->mems[loop_info->mems_idx].optimize = (GET_MODE (m) != BLKmode);
loop_info->mems[loop_info->mems_idx].reg = NULL_RTX;
++loop_info->mems_idx;
return 0;
}
static void
loop_regs_scan (loop, extra_size)
const struct loop *loop;
int extra_size;
{
struct loop_regs *regs = LOOP_REGS (loop);
int old_nregs;
rtx *last_set;
rtx insn;
int i;
old_nregs = regs->num;
regs->num = max_reg_num ();
if (regs->num >= regs->size)
{
regs->size = regs->num + extra_size;
regs->array = (struct loop_reg *)
xrealloc (regs->array, regs->size * sizeof (*regs->array));
memset (regs->array + old_nregs, 0,
(regs->size - old_nregs) * sizeof (*regs->array));
}
for (i = 0; i < old_nregs; i++)
{
regs->array[i].set_in_loop = 0;
regs->array[i].may_not_optimize = 0;
regs->array[i].single_usage = NULL_RTX;
}
last_set = (rtx *) xcalloc (regs->num, sizeof (rtx));
for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
{
find_single_use_in_loop (regs, insn, PATTERN (insn));
if (REG_NOTES (insn))
find_single_use_in_loop (regs, insn, REG_NOTES (insn));
if (GET_CODE (PATTERN (insn)) == SET
|| GET_CODE (PATTERN (insn)) == CLOBBER)
count_one_set (regs, insn, PATTERN (insn), last_set);
else if (GET_CODE (PATTERN (insn)) == PARALLEL)
{
int i;
for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
count_one_set (regs, insn, XVECEXP (PATTERN (insn), 0, i),
last_set);
}
}
if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
memset (last_set, 0, regs->num * sizeof (rtx));
if (GET_CODE (insn) == CALL_INSN)
{
rtx link;
for (link = CALL_INSN_FUNCTION_USAGE (insn);
link;
link = XEXP (link, 1))
{
rtx op, reg;
if (GET_CODE (op = XEXP (link, 0)) == USE
&& GET_CODE (reg = XEXP (op, 0)) == REG
&& rtx_varies_p (reg, 1))
regs->array[REGNO (reg)].may_not_optimize = 1;
}
}
}
if (LOOP_INFO (loop)->has_call)
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)
&& rtx_varies_p (regno_reg_rtx[i], 1))
{
regs->array[i].may_not_optimize = 1;
regs->array[i].set_in_loop = 1;
}
#ifdef AVOID_CCMODE_COPIES
for (i = regs->num - 1; i >= FIRST_PSEUDO_REGISTER; i--)
if (GET_MODE_CLASS (GET_MODE (regno_reg_rtx[i])) == MODE_CC)
regs->array[i].may_not_optimize = 1;
#endif
for (i = old_nregs; i < regs->num; i++)
regs->array[i].n_times_set = regs->array[i].set_in_loop;
free (last_set);
}
static int
count_insns_in_loop (loop)
const struct loop *loop;
{
int count = 0;
rtx insn;
for (insn = loop->top ? loop->top : loop->start; insn != loop->end;
insn = NEXT_INSN (insn))
if (INSN_P (insn))
++count;
return count;
}
static void
load_mems (loop)
const struct loop *loop;
{
struct loop_info *loop_info = LOOP_INFO (loop);
struct loop_regs *regs = LOOP_REGS (loop);
int maybe_never = 0;
int i;
rtx p, prev_ebb_head;
rtx label = NULL_RTX;
rtx end_label;
int next_maybe_never = 0;
unsigned int last_max_reg = max_reg_num ();
if (loop_info->mems_idx == 0)
return;
end_label = next_nonnote_insn (loop->end);
if (end_label && GET_CODE (end_label) != CODE_LABEL)
end_label = NULL_RTX;
for (p = next_insn_in_loop (loop, loop->scan_start);
p != NULL_RTX;
p = next_insn_in_loop (loop, p))
{
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)) == loop->end
&& any_uncondjump_p (p)))
{
if (
!JUMP_LABEL (p)
|| (JUMP_LABEL (p) != end_label
&& (INSN_UID (JUMP_LABEL (p)) >= max_uid_for_loop
|| INSN_LUID (JUMP_LABEL (p)) < INSN_LUID (loop->start)
|| INSN_LUID (JUMP_LABEL (p)) > INSN_LUID (loop->end))))
return;
if (!any_condjump_p (p))
maybe_never = 1;
else
next_maybe_never = 1;
}
else if (next_maybe_never)
maybe_never = 1;
}
for (p = loop->start;
PREV_INSN (p) && GET_CODE (p) != CODE_LABEL;
p = PREV_INSN (p))
;
prev_ebb_head = p;
cselib_init ();
for (; p != loop->start; p = NEXT_INSN (p))
cselib_process_insn (p);
for (i = 0; i < loop_info->mems_idx; ++i)
{
regset_head load_copies;
regset_head store_copies;
int written = 0;
rtx reg;
rtx mem = loop_info->mems[i].mem;
rtx mem_list_entry;
if (MEM_VOLATILE_P (mem)
|| loop_invariant_p (loop, XEXP (mem, 0)) != 1)
loop_info->mems[i].optimize = 0;
mem_list_entry = loop_info->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_info->mems[i].optimize = 0;
break;
}
mem_list_entry = XEXP (mem_list_entry, 1);
}
if (flag_float_store && written
&& GET_MODE_CLASS (GET_MODE (mem)) == MODE_FLOAT)
loop_info->mems[i].optimize = 0;
if (loop_info->mems[i].optimize && written)
{
int j;
for (j = 0; j < loop_info->mems_idx; ++j)
{
if (j == i)
continue;
else if (true_dependence (mem,
VOIDmode,
loop_info->mems[j].mem,
rtx_varies_p))
{
loop_info->mems[i].optimize = 0;
break;
}
}
}
if (maybe_never && may_trap_p (mem))
loop_info->mems[i].optimize = 0;
if (!loop_info->mems[i].optimize)
continue;
INIT_REG_SET (&load_copies);
INIT_REG_SET (&store_copies);
reg = gen_reg_rtx (GET_MODE (mem));
REG_USERVAR_P (reg) = 1;
loop_info->mems[i].reg = reg;
maybe_never = 0;
for (p = next_insn_in_loop (loop, loop->scan_start);
p != NULL_RTX;
p = next_insn_in_loop (loop, p))
{
if (INSN_P (p))
{
rtx set;
set = single_set (p);
if (set
&& ! maybe_never
&& GET_CODE (SET_DEST (set)) == REG
&& REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
&& REGNO (SET_DEST (set)) < last_max_reg
&& regs->array[REGNO (SET_DEST (set))].n_times_set == 1
&& rtx_equal_p (SET_SRC (set), mem))
SET_REGNO_REG_SET (&load_copies, REGNO (SET_DEST (set)));
if (set
&& ! maybe_never
&& GET_CODE (SET_SRC (set)) == REG
&& REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER
&& REGNO (SET_SRC (set)) < last_max_reg
&& regs->array[REGNO (SET_SRC (set))].n_times_set == 1
&& rtx_equal_p (SET_DEST (set), mem))
SET_REGNO_REG_SET (&store_copies, REGNO (SET_SRC (set)));
if (GET_CODE (p) == CALL_INSN
&& reg_mentioned_p (loop_info->mems[i].mem,
CALL_INSN_FUNCTION_USAGE (p)))
{
cancel_changes (0);
loop_info->mems[i].optimize = 0;
break;
}
else
replace_loop_mems (p, loop_info->mems[i].mem,
loop_info->mems[i].reg);
}
if (GET_CODE (p) == CODE_LABEL
|| GET_CODE (p) == JUMP_INSN)
maybe_never = 1;
}
if (! loop_info->mems[i].optimize)
;
else if (! apply_change_group ())
loop_info->mems[i].optimize = 0;
else
{
cselib_val *e = cselib_lookup (mem, VOIDmode, 0);
rtx set;
rtx best = mem;
int j;
struct elt_loc_list *const_equiv = 0;
if (e)
{
struct elt_loc_list *equiv;
struct elt_loc_list *best_equiv = 0;
for (equiv = e->locs; equiv; equiv = equiv->next)
{
if (CONSTANT_P (equiv->loc))
const_equiv = equiv;
else if (GET_CODE (equiv->loc) == REG
&& REGNO (equiv->loc) >= FIRST_PSEUDO_REGISTER)
best_equiv = equiv;
}
if (! best_equiv)
best_equiv = const_equiv;
else if (const_equiv
&& (rtx_cost (const_equiv->loc, SET)
<= rtx_cost (best_equiv->loc, SET)))
{
best_equiv = const_equiv;
const_equiv = 0;
}
if (best_equiv)
best = copy_rtx (best_equiv->loc);
}
set = gen_move_insn (reg, best);
set = loop_insn_hoist (loop, set);
if (REG_P (best))
{
for (p = prev_ebb_head; p != loop->start; p = NEXT_INSN (p))
if (REGNO_LAST_UID (REGNO (best)) == INSN_UID (p))
{
REGNO_LAST_UID (REGNO (best)) = INSN_UID (set);
break;
}
}
if (const_equiv)
set_unique_reg_note (set, REG_EQUAL, copy_rtx (const_equiv->loc));
if (written)
{
if (label == NULL_RTX)
{
label = gen_label_rtx ();
emit_label_after (label, loop->end);
}
set = gen_move_insn (copy_rtx (mem), reg);
loop_insn_emit_after (loop, 0, label, set);
}
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);
}
EXECUTE_IF_SET_IN_REG_SET
(&load_copies, FIRST_PSEUDO_REGISTER, j,
{
try_copy_prop (loop, reg, j);
});
CLEAR_REG_SET (&load_copies);
EXECUTE_IF_SET_IN_REG_SET
(&store_copies, FIRST_PSEUDO_REGISTER, j,
{
try_swap_copy_prop (loop, reg, j);
});
CLEAR_REG_SET (&store_copies);
}
}
if (label != NULL_RTX && end_label != NULL_RTX)
{
rtx_pair rr;
rr.r1 = end_label;
rr.r2 = label;
for (p = loop->start; p != loop->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;
}
}
cselib_finish ();
}
struct note_reg_stored_arg
{
int set_seen;
rtx reg;
};
static void
note_reg_stored (x, setter, arg)
rtx x, setter ATTRIBUTE_UNUSED;
void *arg;
{
struct note_reg_stored_arg *t = (struct note_reg_stored_arg *) arg;
if (t->reg == x)
t->set_seen = 1;
}
static void
try_copy_prop (loop, replacement, regno)
const struct loop *loop;
rtx replacement;
unsigned int regno;
{
rtx reg_rtx = regno_reg_rtx[regno];
rtx init_insn = 0;
rtx insn;
int replaced_last = 0;
int store_is_first = 0;
for (insn = next_insn_in_loop (loop, loop->scan_start);
insn != NULL_RTX;
insn = next_insn_in_loop (loop, insn))
{
rtx set;
if (GET_CODE (insn) == CODE_LABEL && init_insn)
break;
if (! INSN_P (insn))
continue;
set = single_set (insn);
if (set
&& GET_CODE (SET_DEST (set)) == REG
&& REGNO (SET_DEST (set)) == regno)
{
if (init_insn)
abort ();
init_insn = insn;
if (REGNO_FIRST_UID (regno) == INSN_UID (insn))
store_is_first = 1;
}
if (init_insn && insn != init_insn)
{
struct note_reg_stored_arg arg;
replace_loop_regs (insn, reg_rtx, replacement);
if (REGNO_LAST_UID (regno) == INSN_UID (insn))
replaced_last = 1;
arg.reg = replacement;
arg.set_seen = 0;
note_stores (PATTERN (insn), note_reg_stored, &arg);
if (arg.set_seen)
{
rtx note = find_reg_note (insn, REG_EQUAL, NULL);
if (note && reg_mentioned_p (replacement, XEXP (note, 0)))
remove_note (insn, note);
break;
}
}
}
if (! init_insn)
abort ();
if (apply_change_group ())
{
if (loop_dump_stream)
fprintf (loop_dump_stream, " Replaced reg %d", regno);
if (store_is_first && replaced_last)
{
rtx first;
rtx retval_note;
first = init_insn;
retval_note = find_reg_note (init_insn, REG_RETVAL, NULL_RTX);
if (retval_note)
first = XEXP (retval_note, 0);
loop_delete_insns (first, init_insn);
}
if (loop_dump_stream)
fprintf (loop_dump_stream, ".\n");
}
}
static void
loop_delete_insns (first, last)
rtx first;
rtx last;
{
while (1)
{
if (loop_dump_stream)
fprintf (loop_dump_stream, ", deleting init_insn (%d)",
INSN_UID (first));
delete_insn (first);
if (first == last)
break;
first = NEXT_INSN (first);
}
}
static void
try_swap_copy_prop (loop, replacement, regno)
const struct loop *loop;
rtx replacement;
unsigned int regno;
{
rtx insn;
rtx set = NULL_RTX;
unsigned int new_regno;
new_regno = REGNO (replacement);
for (insn = next_insn_in_loop (loop, loop->scan_start);
insn != NULL_RTX;
insn = next_insn_in_loop (loop, insn))
{
if (INSN_P (insn)
&& (set = single_set (insn))
&& GET_CODE (SET_DEST (set)) == REG
&& REGNO (SET_DEST (set)) == new_regno
&& GET_CODE (SET_SRC (set)) == REG
&& REGNO (SET_SRC (set)) == regno)
break;
}
if (insn != NULL_RTX)
{
rtx prev_insn;
rtx prev_set;
prev_insn = PREV_INSN (insn);
if (INSN_P (insn)
&& (prev_set = single_set (prev_insn))
&& GET_CODE (SET_DEST (prev_set)) == REG
&& REGNO (SET_DEST (prev_set)) == regno)
{
validate_change (prev_insn, &SET_DEST (prev_set),
replacement, 1);
validate_change (insn, &SET_DEST (set),
SET_SRC (set), 1);
validate_change (insn, &SET_SRC (set),
replacement, 1);
if (apply_change_group ())
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
" Swapped set of reg %d at %d with reg %d at %d.\n",
regno, INSN_UID (insn),
new_regno, INSN_UID (prev_insn));
if (REGNO_FIRST_UID (regno) == INSN_UID (prev_insn))
REGNO_FIRST_UID (regno) = INSN_UID (insn);
try_copy_prop (loop, replacement, regno);
}
}
}
}
static int
replace_loop_mem (mem, data)
rtx *mem;
void *data;
{
loop_replace_args *args = (loop_replace_args *) data;
rtx m = *mem;
if (m == NULL_RTX)
return 0;
switch (GET_CODE (m))
{
case MEM:
break;
case CONST_DOUBLE:
return -1;
default:
return 0;
}
if (!rtx_equal_p (args->match, m))
return 0;
validate_change (args->insn, mem, args->replacement, 1);
return 0;
}
static void
replace_loop_mems (insn, mem, reg)
rtx insn;
rtx mem;
rtx reg;
{
loop_replace_args args;
args.insn = insn;
args.match = mem;
args.replacement = reg;
for_each_rtx (&insn, replace_loop_mem, &args);
}
static int
replace_loop_reg (px, data)
rtx *px;
void *data;
{
rtx x = *px;
loop_replace_args *args = (loop_replace_args *) data;
if (x == NULL_RTX)
return 0;
if (x == args->match)
validate_change (args->insn, px, args->replacement, 1);
return 0;
}
static void
replace_loop_regs (insn, reg, replacement)
rtx insn;
rtx reg;
rtx replacement;
{
loop_replace_args args;
args.insn = insn;
args.match = reg;
args.replacement = replacement;
for_each_rtx (&insn, replace_loop_reg, &args);
}
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;
}
static rtx
loop_insn_emit_after (loop, where_bb, where_insn, pattern)
const struct loop *loop ATTRIBUTE_UNUSED;
basic_block where_bb ATTRIBUTE_UNUSED;
rtx where_insn;
rtx pattern;
{
return emit_insn_after (pattern, where_insn);
}
rtx
loop_insn_emit_before (loop, where_bb, where_insn, pattern)
const struct loop *loop;
basic_block where_bb ATTRIBUTE_UNUSED;
rtx where_insn;
rtx pattern;
{
if (! where_insn)
return loop_insn_hoist (loop, pattern);
return emit_insn_before (pattern, where_insn);
}
static rtx
loop_call_insn_emit_before (loop, where_bb, where_insn, pattern)
const struct loop *loop ATTRIBUTE_UNUSED;
basic_block where_bb ATTRIBUTE_UNUSED;
rtx where_insn;
rtx pattern;
{
return emit_call_insn_before (pattern, where_insn);
}
rtx
loop_insn_hoist (loop, pattern)
const struct loop *loop;
rtx pattern;
{
return loop_insn_emit_before (loop, 0, loop->start, pattern);
}
static rtx
loop_call_insn_hoist (loop, pattern)
const struct loop *loop;
rtx pattern;
{
return loop_call_insn_emit_before (loop, 0, loop->start, pattern);
}
rtx
loop_insn_sink (loop, pattern)
const struct loop *loop;
rtx pattern;
{
return loop_insn_emit_before (loop, 0, loop->sink, pattern);
}
static rtx
gen_load_of_final_value (reg, final_value)
rtx reg, final_value;
{
rtx seq;
start_sequence ();
final_value = force_operand (final_value, reg);
if (final_value != reg)
emit_move_insn (reg, final_value);
seq = get_insns ();
end_sequence ();
return seq;
}
static rtx
loop_insn_sink_or_swim (loop, pattern)
const struct loop *loop;
rtx pattern;
{
if (loop->exit_count)
return loop_insn_hoist (loop, pattern);
else
return loop_insn_sink (loop, pattern);
}
static void
loop_ivs_dump (loop, file, verbose)
const struct loop *loop;
FILE *file;
int verbose;
{
struct iv_class *bl;
int iv_num = 0;
if (! loop || ! file)
return;
for (bl = LOOP_IVS (loop)->list; bl; bl = bl->next)
iv_num++;
fprintf (file, "Loop %d: %d IV classes\n", loop->num, iv_num);
for (bl = LOOP_IVS (loop)->list; bl; bl = bl->next)
{
loop_iv_class_dump (bl, file, verbose);
fputc ('\n', file);
}
}
static void
loop_iv_class_dump (bl, file, verbose)
const struct iv_class *bl;
FILE *file;
int verbose ATTRIBUTE_UNUSED;
{
struct induction *v;
rtx incr;
int i;
if (! bl || ! file)
return;
fprintf (file, "IV class for reg %d, benefit %d\n",
bl->regno, bl->total_benefit);
fprintf (file, " Init insn %d", INSN_UID (bl->init_insn));
if (bl->initial_value)
{
fprintf (file, ", init val: ");
print_simple_rtl (file, bl->initial_value);
}
if (bl->initial_test)
{
fprintf (file, ", init test: ");
print_simple_rtl (file, bl->initial_test);
}
fputc ('\n', file);
if (bl->final_value)
{
fprintf (file, " Final val: ");
print_simple_rtl (file, bl->final_value);
fputc ('\n', file);
}
if ((incr = biv_total_increment (bl)))
{
fprintf (file, " Total increment: ");
print_simple_rtl (file, incr);
fputc ('\n', file);
}
for (i = 0, v = bl->biv; v; v = v->next_iv, i++)
{
fprintf (file, " Inc%d: insn %d, incr: ", i, INSN_UID (v->insn));
print_simple_rtl (file, v->add_val);
fputc ('\n', file);
}
for (i = 0, v = bl->giv; v; v = v->next_iv, i++)
{
fprintf (file, " Giv%d: insn %d, benefit %d, ",
i, INSN_UID (v->insn), v->benefit);
if (v->giv_type == DEST_ADDR)
print_simple_rtl (file, v->mem);
else
print_simple_rtl (file, single_set (v->insn));
fputc ('\n', file);
}
}
static void
loop_biv_dump (v, file, verbose)
const struct induction *v;
FILE *file;
int verbose;
{
if (! v || ! file)
return;
fprintf (file,
"Biv %d: insn %d",
REGNO (v->dest_reg), INSN_UID (v->insn));
fprintf (file, " const ");
print_simple_rtl (file, v->add_val);
if (verbose && v->final_value)
{
fputc ('\n', file);
fprintf (file, " final ");
print_simple_rtl (file, v->final_value);
}
fputc ('\n', file);
}
static void
loop_giv_dump (v, file, verbose)
const struct induction *v;
FILE *file;
int verbose;
{
if (! v || ! file)
return;
if (v->giv_type == DEST_REG)
fprintf (file, "Giv %d: insn %d",
REGNO (v->dest_reg), INSN_UID (v->insn));
else
fprintf (file, "Dest address: insn %d",
INSN_UID (v->insn));
fprintf (file, " src reg %d benefit %d",
REGNO (v->src_reg), v->benefit);
fprintf (file, " lifetime %d",
v->lifetime);
if (v->replaceable)
fprintf (file, " replaceable");
if (v->no_const_addval)
fprintf (file, " ncav");
if (v->ext_dependent)
{
switch (GET_CODE (v->ext_dependent))
{
case SIGN_EXTEND:
fprintf (file, " ext se");
break;
case ZERO_EXTEND:
fprintf (file, " ext ze");
break;
case TRUNCATE:
fprintf (file, " ext tr");
break;
default:
abort ();
}
}
fputc ('\n', file);
fprintf (file, " mult ");
print_simple_rtl (file, v->mult_val);
fputc ('\n', file);
fprintf (file, " add ");
print_simple_rtl (file, v->add_val);
if (verbose && v->final_value)
{
fputc ('\n', file);
fprintf (file, " final ");
print_simple_rtl (file, v->final_value);
}
fputc ('\n', file);
}
void
debug_ivs (loop)
const struct loop *loop;
{
loop_ivs_dump (loop, stderr, 1);
}
void
debug_iv_class (bl)
const struct iv_class *bl;
{
loop_iv_class_dump (bl, stderr, 1);
}
void
debug_biv (v)
const struct induction *v;
{
loop_biv_dump (v, stderr, 1);
}
void
debug_giv (v)
const struct induction *v;
{
loop_giv_dump (v, stderr, 1);
}
#define LOOP_BLOCK_NUM_1(INSN) \
((INSN) ? (BLOCK_FOR_INSN (INSN) ? BLOCK_NUM (INSN) : - 1) : -1)
#define LOOP_BLOCK_NUM(INSN) \
((INSN) ? (GET_CODE (INSN) == NOTE \
? LOOP_BLOCK_NUM_1 (next_nonnote_insn (INSN)) \
: LOOP_BLOCK_NUM_1 (INSN)) \
: -1)
#define LOOP_INSN_UID(INSN) ((INSN) ? INSN_UID (INSN) : -1)
static void
loop_dump_aux (loop, file, verbose)
const struct loop *loop;
FILE *file;
int verbose ATTRIBUTE_UNUSED;
{
rtx label;
if (! loop || ! file)
return;
if (! PREV_INSN (loop->first->head)
|| GET_CODE (PREV_INSN (loop->first->head)) != NOTE
|| NOTE_LINE_NUMBER (PREV_INSN (loop->first->head))
!= NOTE_INSN_LOOP_BEG)
fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
INSN_UID (PREV_INSN (loop->first->head)));
if (! NEXT_INSN (loop->last->end)
|| GET_CODE (NEXT_INSN (loop->last->end)) != NOTE
|| NOTE_LINE_NUMBER (NEXT_INSN (loop->last->end))
!= NOTE_INSN_LOOP_END)
fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
INSN_UID (NEXT_INSN (loop->last->end)));
if (loop->start)
{
fprintf (file,
";; start %d (%d), cont dom %d (%d), cont %d (%d), vtop %d (%d), end %d (%d)\n",
LOOP_BLOCK_NUM (loop->start),
LOOP_INSN_UID (loop->start),
LOOP_BLOCK_NUM (loop->cont),
LOOP_INSN_UID (loop->cont),
LOOP_BLOCK_NUM (loop->cont),
LOOP_INSN_UID (loop->cont),
LOOP_BLOCK_NUM (loop->vtop),
LOOP_INSN_UID (loop->vtop),
LOOP_BLOCK_NUM (loop->end),
LOOP_INSN_UID (loop->end));
fprintf (file, ";; top %d (%d), scan start %d (%d)\n",
LOOP_BLOCK_NUM (loop->top),
LOOP_INSN_UID (loop->top),
LOOP_BLOCK_NUM (loop->scan_start),
LOOP_INSN_UID (loop->scan_start));
fprintf (file, ";; exit_count %d", loop->exit_count);
if (loop->exit_count)
{
fputs (", labels:", file);
for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
{
fprintf (file, " %d ",
LOOP_INSN_UID (XEXP (label, 0)));
}
}
fputs ("\n", file);
if (LOOP_BLOCK_NUM (loop->cont) != loop->latch->index)
fprintf (file, ";; NOTE_INSN_LOOP_CONT not in loop latch\n");
}
}
void
debug_loop (loop)
const struct loop *loop;
{
flow_loop_dump (loop, stderr, loop_dump_aux, 1);
}
void
debug_loops (loops)
const struct loops *loops;
{
flow_loops_dump (loops, stderr, loop_dump_aux, 1);
}