#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.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 "cselib.h"
#include "except.h"
#include "toplev.h"
#include "predict.h"
#include "insn-flags.h"
#include "optabs.h"
#include "cfgloop.h"
#include "ggc.h"
#define LOOP_INFO(LOOP) ((struct loop_info *) (LOOP)->aux)
#define LOOP_MOVABLES(LOOP) (&LOOP_INFO (LOOP)->movables)
#define LOOP_REGS(LOOP) (&LOOP_INFO (LOOP)->regs)
#define LOOP_IVS(LOOP) (&LOOP_INFO (LOOP)->ivs)
#define INSN_LUID(INSN) \
(INSN_UID (INSN) < max_uid_for_loop ? uid_luid[INSN_UID (INSN)] \
: (abort (), -1))
#define REGNO_FIRST_LUID(REGNO) \
(REGNO_FIRST_UID (REGNO) < max_uid_for_loop \
? uid_luid[REGNO_FIRST_UID (REGNO)] \
: 0)
#define REGNO_LAST_LUID(REGNO) \
(REGNO_LAST_UID (REGNO) < max_uid_for_loop \
? uid_luid[REGNO_LAST_UID (REGNO)] \
: INT_MAX)
enum g_types
{
DEST_ADDR,
DEST_REG
};
struct induction
{
rtx insn;
rtx new_reg;
rtx src_reg;
enum g_types giv_type;
rtx dest_reg;
rtx *location;
enum machine_mode mode;
rtx mem;
rtx mult_val;
rtx add_val;
int benefit;
rtx final_value;
unsigned combined_with;
unsigned replaceable : 1;
unsigned not_replaceable : 1;
unsigned ignore : 1;
unsigned always_computable : 1;
unsigned always_executed : 1;
unsigned maybe_multiple : 1;
unsigned cant_derive : 1;
unsigned maybe_dead : 1;
unsigned auto_inc_opt : 1;
unsigned shared : 1;
unsigned no_const_addval : 1;
int lifetime;
rtx derive_adjustment;
rtx ext_dependent;
struct induction *next_iv;
struct induction *same;
struct induction *same_insn;
rtx last_use;
};
struct iv_class
{
unsigned int regno;
int biv_count;
struct induction *biv;
int giv_count;
struct induction *giv;
int total_benefit;
rtx initial_value;
rtx initial_test;
rtx final_value;
struct iv_class *next;
rtx init_insn;
rtx init_set;
unsigned incremented : 1;
unsigned eliminable : 1;
unsigned nonneg : 1;
unsigned reversed : 1;
unsigned all_reduced : 1;
};
enum iv_mode
{
UNKNOWN_INDUCT,
BASIC_INDUCT,
NOT_BASIC_INDUCT,
GENERAL_INDUCT
};
struct iv
{
enum iv_mode type;
union
{
struct iv_class *class;
struct induction *info;
} iv;
};
#define REG_IV_TYPE(ivs, n) ivs->regs[n].type
#define REG_IV_INFO(ivs, n) ivs->regs[n].iv.info
#define REG_IV_CLASS(ivs, n) ivs->regs[n].iv.class
struct loop_ivs
{
struct iv *regs;
unsigned int n_regs;
struct iv_class *list;
};
typedef struct loop_mem_info
{
rtx mem;
rtx reg;
int optimizable;
} loop_mem_info;
struct loop_reg
{
int set_in_loop;
int n_times_set;
rtx single_usage;
char may_not_optimize;
char moved_once;
};
struct loop_regs
{
int num;
int size;
struct loop_reg *array;
int multiple_uses;
};
struct loop_movables
{
struct movable *head;
struct movable *last;
};
struct loop_info
{
int has_call;
int has_libcall;
int has_nonconst_call;
int has_prefetch;
int has_volatile;
int has_tablejump;
int has_multiple_exit_targets;
int has_indirect_jump;
rtx initial_value;
rtx comparison_value;
rtx final_value;
rtx initial_equiv_value;
rtx final_equiv_value;
rtx iteration_var;
rtx increment;
enum rtx_code comparison_code;
unsigned HOST_WIDE_INT n_iterations;
int used_count_register;
struct iv_class *iv;
rtx store_mems;
loop_mem_info *mems;
int mems_idx;
int mems_allocated;
int unknown_address_altered;
int unknown_constant_address_altered;
int num_mem_sets;
rtx first_loop_store_insn;
struct loop_movables movables;
struct loop_regs regs;
struct loop_ivs ivs;
int pre_header_has_call;
};
#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)
static int *uid_luid;
static struct loop **uid_loop;
static int max_uid_for_loop;
static int max_loop_num;
static 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 is_equiv : 1;
unsigned int insert_temp : 1;
struct movable *match;
struct movable *forces;
struct movable *next;
};
static FILE *loop_dump_stream;
static void invalidate_loops_containing_label (rtx);
static void find_and_verify_loops (rtx, struct loops *);
static void mark_loop_jump (rtx, struct loop *);
static void prescan_loop (struct loop *);
static int reg_in_basic_block_p (rtx, rtx);
static int consec_sets_invariant_p (const struct loop *, rtx, int, rtx);
static int labels_in_range_p (rtx, int);
static void count_one_set (struct loop_regs *, rtx, rtx, rtx *);
static void note_addr_stored (rtx, rtx, void *);
static void note_set_pseudo_multiple_uses (rtx, rtx, void *);
static int loop_reg_used_before_p (const struct loop *, rtx, rtx);
static rtx find_regs_nested (rtx, rtx);
static void scan_loop (struct loop*, int);
#if 0
static void replace_call_address (rtx, rtx, rtx);
#endif
static rtx skip_consec_insns (rtx, int);
static int libcall_benefit (rtx);
static rtx libcall_other_reg (rtx, rtx);
static void record_excess_regs (rtx, rtx, rtx *);
static void ignore_some_movables (struct loop_movables *);
static void force_movables (struct loop_movables *);
static void combine_movables (struct loop_movables *, struct loop_regs *);
static int num_unmoved_movables (const struct loop *);
static int regs_match_p (rtx, rtx, struct loop_movables *);
static int rtx_equal_for_loop_p (rtx, rtx, struct loop_movables *,
struct loop_regs *);
static void add_label_notes (rtx, rtx);
static void move_movables (struct loop *loop, struct loop_movables *, int,
int);
static void loop_movables_add (struct loop_movables *, struct movable *);
static void loop_movables_free (struct loop_movables *);
static int count_nonfixed_reads (const struct loop *, rtx);
static void loop_bivs_find (struct loop *);
static void loop_bivs_init_find (struct loop *);
static void loop_bivs_check (struct loop *);
static void loop_givs_find (struct loop *);
static void loop_givs_check (struct loop *);
static int loop_biv_eliminable_p (struct loop *, struct iv_class *, int, int);
static int loop_giv_reduce_benefit (struct loop *, struct iv_class *,
struct induction *, rtx);
static void loop_givs_dead_check (struct loop *, struct iv_class *);
static void loop_givs_reduce (struct loop *, struct iv_class *);
static void loop_givs_rescan (struct loop *, struct iv_class *, rtx *);
static void loop_ivs_free (struct loop *);
static void strength_reduce (struct loop *, int);
static void find_single_use_in_loop (struct loop_regs *, rtx, rtx);
static int valid_initial_value_p (rtx, rtx, int, rtx);
static void find_mem_givs (const struct loop *, rtx, rtx, int, int);
static void record_biv (struct loop *, struct induction *, rtx, rtx, rtx,
rtx, rtx *, int, int);
static void check_final_value (const struct loop *, struct induction *);
static void loop_ivs_dump (const struct loop *, FILE *, int);
static void loop_iv_class_dump (const struct iv_class *, FILE *, int);
static void loop_biv_dump (const struct induction *, FILE *, int);
static void loop_giv_dump (const struct induction *, FILE *, int);
static void record_giv (const struct loop *, struct induction *, rtx, rtx,
rtx, rtx, rtx, rtx, int, enum g_types, int, int,
rtx *);
static void update_giv_derive (const struct loop *, rtx);
static HOST_WIDE_INT get_monotonic_increment (struct iv_class *);
static bool biased_biv_fits_mode_p (const struct loop *, struct iv_class *,
HOST_WIDE_INT, enum machine_mode,
unsigned HOST_WIDE_INT);
static bool biv_fits_mode_p (const struct loop *, struct iv_class *,
HOST_WIDE_INT, enum machine_mode, bool);
static bool extension_within_bounds_p (const struct loop *, struct iv_class *,
HOST_WIDE_INT, rtx);
static void check_ext_dependent_givs (const struct loop *, struct iv_class *);
static int basic_induction_var (const struct loop *, rtx, enum machine_mode,
rtx, rtx, rtx *, rtx *, rtx **);
static rtx simplify_giv_expr (const struct loop *, rtx, rtx *, int *);
static int general_induction_var (const struct loop *loop, rtx, rtx *, rtx *,
rtx *, rtx *, int, int *, enum machine_mode);
static int consec_sets_giv (const struct loop *, int, rtx, rtx, rtx, rtx *,
rtx *, rtx *, rtx *);
static int check_dbra_loop (struct loop *, int);
static rtx express_from_1 (rtx, rtx, rtx);
static rtx combine_givs_p (struct induction *, struct induction *);
static int cmp_combine_givs_stats (const void *, const void *);
static void combine_givs (struct loop_regs *, struct iv_class *);
static int product_cheap_p (rtx, rtx);
static int maybe_eliminate_biv (const struct loop *, struct iv_class *, int,
int, int);
static int maybe_eliminate_biv_1 (const struct loop *, rtx, rtx,
struct iv_class *, int, basic_block, rtx);
static int last_use_this_basic_block (rtx, rtx);
static void record_initial (rtx, rtx, void *);
static void update_reg_last_use (rtx, rtx);
static rtx next_insn_in_loop (const struct loop *, rtx);
static void loop_regs_scan (const struct loop *, int);
static int count_insns_in_loop (const struct loop *);
static int find_mem_in_note_1 (rtx *, void *);
static rtx find_mem_in_note (rtx);
static void load_mems (const struct loop *);
static int insert_loop_mem (rtx *, void *);
static int replace_loop_mem (rtx *, void *);
static void replace_loop_mems (rtx, rtx, rtx, int);
static int replace_loop_reg (rtx *, void *);
static void replace_loop_regs (rtx insn, rtx, rtx);
static void note_reg_stored (rtx, rtx, void *);
static void try_copy_prop (const struct loop *, rtx, unsigned int);
static void try_swap_copy_prop (const struct loop *, rtx, unsigned int);
static rtx check_insn_for_givs (struct loop *, rtx, int, int);
static rtx check_insn_for_bivs (struct loop *, rtx, int, int);
static rtx gen_add_mult (rtx, rtx, rtx, rtx);
static void loop_regs_update (const struct loop *, rtx);
static int iv_add_mult_cost (rtx, rtx, rtx, rtx);
static int loop_invariant_p (const struct loop *, rtx);
static rtx loop_insn_hoist (const struct loop *, rtx);
static void loop_iv_add_mult_emit_before (const struct loop *, rtx, rtx, rtx,
rtx, basic_block, rtx);
static rtx loop_insn_emit_before (const struct loop *, basic_block,
rtx, rtx);
static int loop_insn_first_p (rtx, rtx);
static rtx get_condition_for_loop (const struct loop *, rtx);
static void loop_iv_add_mult_sink (const struct loop *, rtx, rtx, rtx, rtx);
static void loop_iv_add_mult_hoist (const struct loop *, rtx, rtx, rtx, rtx);
static rtx extend_value_for_giv (struct induction *, rtx);
static rtx loop_insn_sink (const struct loop *, rtx);
static rtx loop_insn_emit_after (const struct loop *, basic_block, rtx, rtx);
static rtx loop_call_insn_emit_before (const struct loop *, basic_block,
rtx, rtx);
static rtx loop_call_insn_hoist (const struct loop *, rtx);
static rtx loop_insn_sink_or_swim (const struct loop *, rtx);
static void loop_dump_aux (const struct loop *, FILE *, int);
static void loop_delete_insns (rtx, rtx);
static HOST_WIDE_INT remove_constant_addition (rtx *);
static rtx gen_load_of_final_value (rtx, rtx);
void debug_ivs (const struct loop *);
void debug_iv_class (const struct iv_class *);
void debug_biv (const struct induction *);
void debug_giv (const struct induction *);
void debug_loop (const struct loop *);
void debug_loops (const struct loops *);
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 (rtx);
static int compute_luids (rtx, rtx, int);
static int biv_elimination_giv_has_0_offset (struct induction *,
struct induction *, rtx);
static int copy_cost;
static int reg_address_cost;
void
init_loop (void)
{
rtx reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
reg_address_cost = address_cost (reg, SImode);
copy_cost = COSTS_N_INSNS (1);
}
static int
compute_luids (rtx start, rtx 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 (!NOTE_P (insn)
|| NOTE_LINE_NUMBER (insn) <= 0)
uid_luid[INSN_UID (insn)] = ++i;
else
uid_luid[INSN_UID (insn)] = i;
}
return i + 1;
}
void
loop_optimize (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 (NOTE_P (insn)
&& 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 = xcalloc (max_uid_for_loop, sizeof (int));
uid_loop = xcalloc (max_uid_for_loop, sizeof (struct loop *));
loops->array = 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 < (int) loops->num; i++)
loops->array[i].aux = loops_info + i;
reg_scan (f, max_reg_before_loop);
init_alias_analysis ();
if (get_max_uid () > max_uid_for_loop)
abort ();
max_uid_for_loop = get_max_uid ();
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);
ggc_collect ();
}
}
end_alias_analysis ();
for (i = 0; i < (int) loops->num; i++)
free (loops_info[i].mems);
free (uid_luid);
free (uid_loop);
free (loops_info);
free (loops->array);
}
static rtx
next_insn_in_loop (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 rtx
find_regs_nested (rtx deps, rtx x)
{
enum rtx_code code = GET_CODE (x);
if (code == REG)
deps = gen_rtx_EXPR_LIST (VOIDmode, x, deps);
else
{
const char *fmt = GET_RTX_FORMAT (code);
int i, j;
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
deps = find_regs_nested (deps, XEXP (x, i));
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
deps = find_regs_nested (deps, XVECEXP (x, i, j));
}
}
return deps;
}
static void
scan_loop (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;
int insn_count;
int tem;
rtx temp, update_start, update_end;
rtx set, set1;
struct loop_movables *movables = LOOP_MOVABLES (loop);
int threshold;
int in_libcall;
loop->top = 0;
movables->head = 0;
movables->last = 0;
for (p = NEXT_INSN (loop_start);
p != loop_end
&& !LABEL_P (p) && ! INSN_P (p)
&& (!NOTE_P (p)
|| (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 (JUMP_P (p)
&& any_uncondjump_p (p)
&& JUMP_LABEL (p) != 0
&& INSN_IN_RANGE_P (JUMP_LABEL (p), loop_start, loop_end))
{
rtx end_test = prev_real_insn (loop_end);
loop->top = next_label (loop->scan_start);
loop->scan_start = JUMP_LABEL (p);
if ((any_condjump_p (end_test) || any_uncondjump_p (end_test))
&& JUMP_LABEL (end_test) != loop->top)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"\nLoop from %d to %d is too complex.\n\n",
INSN_UID (loop_start), INSN_UID (loop_end));
return;
}
}
if (INSN_UID (loop->scan_start) >= max_uid_for_loop
|| !LABEL_P (loop->scan_start))
{
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);
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 (NONJUMP_INSN_P (p))
{
if (GET_CODE (PATTERN (p)) == ASM_INPUT)
break;
temp = find_reg_note (p, REG_LIBCALL, NULL_RTX);
if (temp)
in_libcall++;
if (! in_libcall
&& (set = single_set (p))
&& REG_P (SET_DEST (set))
#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);
else if (GET_CODE (x) == CLOBBER
&& MEM_P (XEXP (x, 0)))
dependencies = find_regs_nested (dependencies,
XEXP (XEXP (x, 0), 0));
}
}
if (
! reg_in_basic_block_p (p, SET_DEST (set))
&& (maybe_never
|| loop_reg_used_before_p (loop, set, p)))
insert_temp = 1;
if (GET_MODE_CLASS (GET_MODE (SET_DEST (set))) == MODE_CC
&& CONSTANT_P (src))
;
else if (REGNO (SET_DEST (set)) >= max_reg_before_loop)
;
else if (insert_temp
&& (optimize_size
|| ! can_copy_p (GET_MODE (SET_SRC (set)))
|| REG_P (SET_SRC (set))
|| (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
|| (! (REG_P (SET_SRC (set))
&& (REGNO (SET_SRC (set))
< FIRST_PSEUDO_REGISTER))))
&& regno >= 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 = 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
&& NONJUMP_INSN_P (NEXT_INSN (p))
&& (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 = 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 (CALL_P (p) && ! CONST_OR_PURE_CALL_P (p))
call_passed = 1;
else if ((LABEL_P (p) || JUMP_P (p))
&& ! (JUMP_P (p) && JUMP_LABEL (p) == loop->top
&& NEXT_INSN (NEXT_INSN (p)) == loop_end
&& any_uncondjump_p (p)))
maybe_never = 1;
}
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)
&& !LABEL_P (PREV_INSN (update_start));
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)
&& !LABEL_P (PREV_INSN (update_start));
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 && LABEL_P (update_end))
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 && LABEL_P (update_end)
&& --LABEL_NUSES (update_end) == 0)
delete_related_insns (update_end);
}
loop_movables_free (movables);
free (regs->array);
regs->array = 0;
regs->num = 0;
}
static void
record_excess_regs (rtx in_this, rtx 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;
}
}
}
static rtx
libcall_other_reg (rtx insn, rtx equiv)
{
rtx note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
rtx p = XEXP (note, 0);
rtx output = 0;
while (p != insn)
{
if (INSN_P (p))
record_excess_regs (PATTERN (p), equiv, &output);
p = NEXT_INSN (p);
}
return output;
}
static int
reg_in_basic_block_p (rtx insn, rtx 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 (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 (CALL_P (insn))
benefit += 10;
else if (NONJUMP_INSN_P (insn)
&& GET_CODE (PATTERN (insn)) != USE
&& GET_CODE (PATTERN (insn)) != CLOBBER)
benefit++;
}
return benefit;
}
static rtx
skip_consec_insns (rtx insn, int count)
{
for (; count > 0; count--)
{
rtx temp;
if (!NOTE_P (insn)
&& (temp = find_reg_note (insn, REG_LIBCALL, NULL_RTX)))
insn = XEXP (temp, 0);
do
insn = NEXT_INSN (insn);
while (NOTE_P (insn));
}
return insn;
}
static void
ignore_some_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 (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)
{
struct movable *m2;
m->forces = m1;
for (m2 = m1; m2; m2 = m2->forces)
{
m2->lifetime += m->lifetime;
m2->savings += m->savings;
}
}
}
}
static void
combine_movables (struct loop_movables *movables, struct loop_regs *regs)
{
struct movable *m;
char *matched_regs = 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
&& ((REG_P (m1->set_src)
&& 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 (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 (rtx x, rtx 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 (rtx x, rtx 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 (REG_P (x) && 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 (REG_P (y) && 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 (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 (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 = xcalloc (nregs, sizeof (rtx));
char *already_moved = 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]
|| (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 (!NOTE_P (p)
&& (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
abort ();
if (!NOTE_P (p)
&& (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 && NOTE_P (p))
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 (!NOTE_P (p)
&& (temp = find_reg_note (p, REG_LIBCALL, NULL_RTX)))
p = XEXP (temp, 0);
if (!NOTE_P (p)
&& (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 (NOTE_P (temp))
continue;
body = PATTERN (temp);
for (next = NEXT_INSN (temp); next != p;
next = NEXT_INSN (next))
if (! (NONJUMP_INSN_P (next)
&& GET_CODE (PATTERN (next)) == USE)
&& !NOTE_P (next))
break;
if (CALL_P (next)
&& GET_CODE (body) == SET
&& REG_P (SET_DEST (body))
&& (n = find_reg_note (temp, REG_EQUAL,
NULL_RTX)))
{
fn_reg = SET_SRC (body);
if (!REG_P (fn_reg))
fn_reg = SET_DEST (body);
fn_address = XEXP (n, 0);
fn_address_insn = temp;
}
if (CALL_P (temp)
&& 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 (CALL_P (temp))
{
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 (CALL_P (p))
{
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->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);
}
else if (m->insert_temp)
{
rtx *reg_map2 = 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 && NOTE_P (p))
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_LUID (regno) > INSN_LUID (loop_start))
REGNO_FIRST_UID (regno) = INSN_UID (loop_start);
if (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 (INSN_P (p))
{
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 (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 (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 (rtx x, rtx reg, rtx 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 (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 (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;
for (insn = start; insn && !LABEL_P (insn);
insn = PREV_INSN (insn))
{
if (CALL_P (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))
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 (JUMP_P (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);
MEM_READONLY_P (mem) = 1;
loop_info->store_mems
= gen_rtx_EXPR_LIST (VOIDmode, mem, loop_info->store_mems);
}
}
static void
invalidate_loops_containing_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 (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 (NOTE_P (insn))
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_END:
if (! current_loop)
abort ();
current_loop->end = insn;
current_loop = current_loop->outer;
break;
default:
break;
}
if (CALL_P (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 (NONJUMP_INSN_P (insn) || CALL_P (insn))
{
rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX);
if (note)
invalidate_loops_containing_label (XEXP (note, 0));
}
if (!JUMP_P (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);
!LABEL_P (p)
&& ! (NOTE_P (p)
&& NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG)
&& !JUMP_P (p);
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 (JUMP_P (p) && JUMP_LABEL (p)
&& uid_loop[INSN_UID (JUMP_LABEL (p))] != this_loop)
outer_loop = this_loop;
if (! outer_loop
&& JUMP_P (p)
&& 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 && !LABEL_P (tmp); tmp = NEXT_INSN (tmp))
if (BARRIER_P (tmp))
last_insn_to_move = tmp;
for (loc = target; loc; loc = PREV_INSN (loc))
if (BARRIER_P (loc)
&& ((loc2 = next_nonnote_insn (loc)) == 0
|| !LABEL_P (loc2)
|| (loc2 = next_nonnote_insn (loc2)) == 0
|| !JUMP_P (loc2)
|| (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 (BARRIER_P (loc)
&& ((loc2 = next_nonnote_insn (loc)) == 0
|| !LABEL_P (loc2)
|| (loc2 = next_nonnote_insn (loc2)) == 0
|| !JUMP_P (loc2)
|| (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 (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 (rtx insn, int end)
{
while (insn && INSN_LUID (insn) <= end)
{
if (LABEL_P (insn))
return 1;
insn = NEXT_INSN (insn);
}
return 0;
}
static void
note_addr_stored (rtx x, rtx y ATTRIBUTE_UNUSED,
void *data ATTRIBUTE_UNUSED)
{
struct loop_info *loop_info = data;
if (x == 0 || !MEM_P (x))
return;
loop_info->num_mem_sets++;
if (GET_MODE (x) == BLKmode)
{
if (MEM_READONLY_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 (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 (!REG_P (x) || 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;
}
static int
loop_invariant_p (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:
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 (const struct loop *loop, rtx reg, int n_sets,
rtx 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))
&& REG_P (SET_DEST (set))
&& 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);
}
static void
find_single_use_in_loop (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 (!REG_P (SET_DEST (x)))
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 (struct loop_regs *regs, rtx insn, rtx x, rtx *last_set)
{
if (GET_CODE (x) == CLOBBER && REG_P (XEXP (x, 0)))
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) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
if (REG_P (dest))
{
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[regno] == 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 (const struct loop *loop, rtx set, rtx 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 (rtx, rtx, void *);
static void emit_prefetch_instructions (struct loop *);
static int rtx_equal_for_prefetch_p (rtx, rtx);
static void
check_store (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
{
struct check_store_data *d = (struct check_store_data *) data;
if ((MEM_P (x)) && rtx_equal_p (d->mem_address, XEXP (x, 0)))
d->mem_write = 1;
}
static int
rtx_equal_for_prefetch_p (rtx x, rtx 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;
if (COMMUTATIVE_ARITH_P (x))
{
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 (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 (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 || PREFETCH_BLOCK == 0)
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: " HOST_WIDE_INT_PRINT_DEC
"; stride: " HOST_WIDE_INT_PRINT_DEC "; address: ",
info[i].index, info[i].stride);
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;
static int
back_branch_in_range_p (const struct loop *loop, rtx insn)
{
rtx p, q, target_insn;
rtx loop_start = loop->start;
rtx loop_end = loop->end;
rtx orig_loop_end = loop->end;
loop_end = prev_nonnote_insn (loop_end);
if (BARRIER_P (loop_end))
loop_end = PREV_INSN (loop_end);
while (INSN_DELETED_P (insn))
insn = NEXT_INSN (insn);
if (insn == loop_end || insn == orig_loop_end)
return 0;
for (p = NEXT_INSN (insn); p != loop_end; p = NEXT_INSN (p))
{
if (JUMP_P (p))
{
target_insn = JUMP_LABEL (p);
for (q = loop_start; q != insn; q = NEXT_INSN (q))
if (q == target_insn)
return 1;
}
}
return 0;
}
typedef rtx (*loop_insn_callback) (struct loop *, rtx, int, int);
static void
for_each_insn_in_loop (struct loop *loop, loop_insn_callback fncall)
{
int not_every_iteration = 0;
int maybe_multiple = 0;
int past_loop_latch = 0;
bool exit_test_is_entry = false;
rtx p;
if (prev_nonnote_insn (loop->scan_start) != prev_nonnote_insn (loop->start))
{
exit_test_is_entry = true;
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 (LABEL_P (p))
{
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 (JUMP_P (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 (JUMP_P (p)
&& (exit_test_is_entry
|| !(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;
}
if (JUMP_P (p)
&& JUMP_LABEL (p) == NEXT_INSN (loop->start))
past_loop_latch = 1;
if (not_every_iteration
&& !past_loop_latch
&& LABEL_P (p)
&& no_labels_between_p (p, loop->end))
not_every_iteration = 0;
}
}
static void
loop_bivs_find (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 (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 && !LABEL_P (p); p = PREV_INSN (p))
{
rtx test;
note_insn = p;
if (CALL_P (p))
call_seen = 1;
if (INSN_P (p))
note_stores (PATTERN (p), record_initial, ivs);
if (JUMP_P (p)
&& JUMP_LABEL (p) != 0
&& next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop->end)
&& (test = get_condition_for_loop (loop, p)) != 0
&& REG_P (XEXP (test, 0))
&& 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 (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 (struct loop* loop)
{
for_each_insn_in_loop (loop, check_insn_for_givs);
}
static void
loop_givs_check (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 rtx
fold_rtx_mult_add (rtx mult1, rtx mult2, rtx add1, enum machine_mode mode)
{
rtx temp, mult_res;
rtx result;
if ((GET_MODE (mult1) != mode && GET_MODE (mult1) != VOIDmode)
|| (GET_MODE (mult2) != mode && GET_MODE (mult2) != VOIDmode)
|| (GET_MODE (add1) != mode && GET_MODE (add1) != VOIDmode))
abort ();
if (GET_CODE (mult1) == CONST_INT)
{
temp = mult2;
mult2 = mult1;
mult1 = temp;
}
mult_res = simplify_binary_operation (MULT, mode, mult1, mult2);
if (! mult_res)
mult_res = gen_rtx_MULT (mode, mult1, mult2);
if (GET_CODE (add1) == CONST_INT)
{
temp = add1;
add1 = mult_res;
mult_res = temp;
}
result = simplify_binary_operation (PLUS, mode, add1, mult_res);
if (! result)
result = gen_rtx_PLUS (mode, add1, mult_res);
return result;
}
static rtx
biv_total_increment (const struct iv_class *bl)
{
struct induction *v;
rtx result;
result = const0_rtx;
for (v = bl->biv; v; v = v->next_iv)
{
if (v->always_computable && v->mult_val == const1_rtx
&& ! v->maybe_multiple
&& SCALAR_INT_MODE_P (v->mode))
{
if (v->same)
continue;
result = fold_rtx_mult_add (result, const1_rtx, v->add_val, v->mode);
}
else
return 0;
}
return result;
}
static int
reg_dead_after_loop (const struct loop *loop, rtx reg)
{
rtx insn, label;
int jump_count = 0;
int label_count = 0;
for (label = loop->exit_labels; label; label = LABEL_NEXTREF (label))
label_count++;
if (label_count != loop->exit_count)
return 0;
label = gen_rtx_LABEL_REF (VOIDmode, loop->end);
LABEL_NEXTREF (label) = loop->exit_labels;
for (; label; label = LABEL_NEXTREF (label))
{
insn = NEXT_INSN (XEXP (label, 0));
while (insn)
{
if (INSN_P (insn))
{
rtx set, note;
if (reg_referenced_p (reg, PATTERN (insn)))
return 0;
note = find_reg_equal_equiv_note (insn);
if (note && reg_overlap_mentioned_p (reg, XEXP (note, 0)))
return 0;
set = single_set (insn);
if (set && rtx_equal_p (SET_DEST (set), reg))
break;
if (JUMP_P (insn))
{
if (GET_CODE (PATTERN (insn)) == RETURN)
break;
else if (!any_uncondjump_p (insn)
|| jump_count++ > 20)
return 0;
else
insn = JUMP_LABEL (insn);
}
}
insn = NEXT_INSN (insn);
}
}
return 1;
}
static rtx
final_biv_value (const struct loop *loop, struct iv_class *bl)
{
unsigned HOST_WIDE_INT n_iterations = LOOP_INFO (loop)->n_iterations;
rtx increment, tem;
if (GET_MODE_CLASS (bl->biv->mode) != MODE_INT)
return 0;
if (bl->reversed)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Final biv value for %d, reversed biv.\n", bl->regno);
return const0_rtx;
}
if (n_iterations != 0
&& ! loop->exit_count
&& loop_invariant_p (loop, bl->initial_value))
{
increment = biv_total_increment (bl);
if (increment && loop_invariant_p (loop, increment))
{
tem = gen_reg_rtx (bl->biv->mode);
record_base_value (REGNO (tem), bl->biv->add_val, 0);
loop_iv_add_mult_sink (loop, increment, GEN_INT (n_iterations),
bl->initial_value, tem);
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Final biv value for %d, calculated.\n", bl->regno);
return tem;
}
}
if (reg_dead_after_loop (loop, bl->biv->src_reg))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Final biv value for %d, biv dead after loop exit.\n",
bl->regno);
return const0_rtx;
}
return 0;
}
static int
loop_biv_eliminable_p (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 (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
&& !loop->top)
{
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 (tv->same)
continue;
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 (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 (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 (REG_P (v->new_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 (REG_P (v->new_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 (REG_P (v->new_reg)
&& REG_P (v->add_val)
&& 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 (REG_P (v->new_reg) && v->giv_type == DEST_ADDR)
mark_reg_pointer (v->new_reg, 0);
if (v->giv_type == DEST_ADDR)
{
if (!validate_change (v->insn, v->location, v->new_reg, 0))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"unable to reduce iv to register in insn %d\n",
INSN_UID (v->insn));
bl->all_reduced = 0;
v->ignore = 1;
continue;
}
}
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 (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 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 (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 rtx
loop_find_equiv_value (const struct loop *loop, rtx reg)
{
rtx loop_start = loop->start;
rtx insn, set;
rtx ret;
ret = reg;
for (insn = PREV_INSN (loop_start); insn; insn = PREV_INSN (insn))
{
if (LABEL_P (insn))
break;
else if (INSN_P (insn) && reg_set_p (reg, insn))
{
if ((set = single_set (insn))
&& (SET_DEST (set) == reg))
{
rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST
&& CONSTANT_P (XEXP (note, 0)))
ret = XEXP (note, 0);
else
ret = SET_SRC (set);
if (modified_between_p (ret, insn, loop_start))
ret = reg;
}
break;
}
}
return ret;
}
static rtx
find_common_reg_term (rtx op0, rtx op1)
{
if ((REG_P (op0) || GET_CODE (op0) == PLUS)
&& (REG_P (op1) || GET_CODE (op1) == PLUS))
{
rtx op00;
rtx op01;
rtx op10;
rtx op11;
if (GET_CODE (op0) == PLUS)
op01 = XEXP (op0, 1), op00 = XEXP (op0, 0);
else
op01 = const0_rtx, op00 = op0;
if (GET_CODE (op1) == PLUS)
op11 = XEXP (op1, 1), op10 = XEXP (op1, 0);
else
op11 = const0_rtx, op10 = op1;
if (REG_P (op00) && (op00 == op10 || op00 == op11))
return op00;
else if (REG_P (op01) && (op01 == op10 || op01 == op11))
return op01;
}
return NULL_RTX;
}
static unsigned HOST_WIDE_INT
loop_iterations (struct loop *loop)
{
struct loop_info *loop_info = LOOP_INFO (loop);
struct loop_ivs *ivs = LOOP_IVS (loop);
rtx comparison, comparison_value;
rtx iteration_var, initial_value, increment, final_value;
enum rtx_code comparison_code;
HOST_WIDE_INT inc;
unsigned HOST_WIDE_INT abs_inc;
unsigned HOST_WIDE_INT abs_diff;
int off_by_one;
int increment_dir;
int unsigned_p, compare_dir, final_larger;
rtx last_loop_insn;
struct iv_class *bl;
loop_info->n_iterations = 0;
loop_info->initial_value = 0;
loop_info->initial_equiv_value = 0;
loop_info->comparison_value = 0;
loop_info->final_value = 0;
loop_info->final_equiv_value = 0;
loop_info->increment = 0;
loop_info->iteration_var = 0;
loop_info->iv = 0;
last_loop_insn = PREV_INSN (loop->end);
if (!JUMP_P (last_loop_insn))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: No final conditional branch found.\n");
return 0;
}
if (LABEL_NUSES (JUMP_LABEL (last_loop_insn)) > 1)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: Loop has multiple back edges.\n");
return 0;
}
comparison = get_condition_for_loop (loop, last_loop_insn);
if (comparison == 0)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: No final comparison found.\n");
return 0;
}
comparison_code = GET_CODE (comparison);
iteration_var = XEXP (comparison, 0);
comparison_value = XEXP (comparison, 1);
if (!REG_P (iteration_var))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: Comparison not against register.\n");
return 0;
}
if ((unsigned) REGNO (iteration_var) >= ivs->n_regs
&& ! REG_USERVAR_P (iteration_var))
abort ();
initial_value = 0;
increment = 0;
if ((unsigned) REGNO (iteration_var) >= ivs->n_regs)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: No reg_iv_type entry for iteration var.\n");
return 0;
}
else if ((GET_MODE_BITSIZE (GET_MODE (iteration_var))
> HOST_BITS_PER_WIDE_INT))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: Iteration var rejected because mode too large.\n");
return 0;
}
else if (GET_MODE_CLASS (GET_MODE (iteration_var)) != MODE_INT)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: Iteration var not an integer.\n");
return 0;
}
if (REG_IV_TYPE (ivs, REGNO (iteration_var)) != BASIC_INDUCT
&& REG_IV_TYPE (ivs, REGNO (iteration_var)) != GENERAL_INDUCT
&& REG_P (comparison_value)
&& REGNO (comparison_value) < ivs->n_regs)
{
rtx temp = comparison_value;
comparison_code = swap_condition (comparison_code);
comparison_value = iteration_var;
iteration_var = temp;
}
if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
{
if (REGNO (iteration_var) >= ivs->n_regs)
abort ();
bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
initial_value = bl->initial_value;
if (!bl->biv->always_executed || bl->biv->maybe_multiple)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: Basic induction var not set once in each iteration.\n");
return 0;
}
increment = biv_total_increment (bl);
}
else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
{
HOST_WIDE_INT offset = 0;
struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
rtx biv_initial_value;
if (REGNO (v->src_reg) >= ivs->n_regs)
abort ();
if (!v->always_executed || v->maybe_multiple)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: General induction var not set once in each iteration.\n");
return 0;
}
bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
increment = biv_total_increment (bl);
if (increment)
{
struct induction *biv_inc;
increment = fold_rtx_mult_add (v->mult_val,
extend_value_for_giv (v, increment),
const0_rtx, v->mode);
for (biv_inc = bl->biv; biv_inc; biv_inc = biv_inc->next_iv)
{
if (loop_insn_first_p (v->insn, biv_inc->insn))
{
if (REG_P (biv_inc->add_val))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: Basic induction var add_val is REG %d.\n",
REGNO (biv_inc->add_val));
return 0;
}
if (biv_inc->same)
continue;
offset -= INTVAL (biv_inc->add_val);
}
}
}
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: Giv iterator, initial value bias %ld.\n",
(long) offset);
biv_initial_value = extend_value_for_giv (v, bl->initial_value);
initial_value
= fold_rtx_mult_add (v->mult_val,
plus_constant (biv_initial_value, offset),
v->add_val, v->mode);
}
else
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: Not basic or general induction var.\n");
return 0;
}
if (initial_value == 0)
return 0;
unsigned_p = 0;
off_by_one = 0;
switch (comparison_code)
{
case LEU:
unsigned_p = 1;
case LE:
compare_dir = 1;
off_by_one = 1;
break;
case GEU:
unsigned_p = 1;
case GE:
compare_dir = -1;
off_by_one = -1;
break;
case EQ:
compare_dir = 0;
break;
case LTU:
unsigned_p = 1;
case LT:
compare_dir = 1;
break;
case GTU:
unsigned_p = 1;
case GT:
compare_dir = -1;
break;
case NE:
compare_dir = 0;
break;
default:
abort ();
}
final_value = comparison_value;
if (REG_P (comparison_value)
&& loop_invariant_p (loop, comparison_value))
{
final_value = loop_find_equiv_value (loop, comparison_value);
if (! loop_invariant_p (loop, final_value))
final_value = comparison_value;
}
if (off_by_one)
final_value = plus_constant (final_value, off_by_one);
loop_info->initial_value = initial_value;
loop_info->comparison_value = comparison_value;
loop_info->final_value = plus_constant (comparison_value, off_by_one);
loop_info->increment = increment;
loop_info->iteration_var = iteration_var;
loop_info->comparison_code = comparison_code;
loop_info->iv = bl;
if (REG_P (initial_value))
{
rtx reg1;
rtx reg2;
rtx const2;
reg1 = initial_value;
if (GET_CODE (final_value) == PLUS)
reg2 = XEXP (final_value, 0), const2 = XEXP (final_value, 1);
else
reg2 = final_value, const2 = const0_rtx;
if (REG_P (reg2) && reg2 != reg1)
{
rtx temp;
temp = loop_find_equiv_value (loop, reg1);
if (find_common_reg_term (temp, reg2))
initial_value = temp;
else if (loop_invariant_p (loop, reg2))
{
temp = loop_find_equiv_value (loop, reg2);
if (temp == loop_info->iteration_var)
temp = initial_value;
if (temp == reg1)
final_value = (const2 == const0_rtx)
? reg1 : gen_rtx_PLUS (GET_MODE (reg1), reg1, const2);
}
}
}
loop_info->initial_equiv_value = initial_value;
loop_info->final_equiv_value = final_value;
if (comparison_code == EQ)
loop_info->final_equiv_value = loop_info->final_value = 0;
if (increment == 0)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Loop iterations: Increment value can't be calculated.\n");
return 0;
}
if (GET_CODE (increment) != CONST_INT)
{
if (REG_P (increment) || GET_CODE (increment) == SUBREG)
increment = loop_find_equiv_value (loop, increment);
if (GET_CODE (increment) != CONST_INT)
{
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
"Loop iterations: Increment value not constant ");
print_simple_rtl (loop_dump_stream, increment);
fprintf (loop_dump_stream, ".\n");
}
return 0;
}
loop_info->increment = increment;
}
if (GET_CODE (initial_value) != CONST_INT)
{
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
"Loop iterations: Initial value not constant ");
print_simple_rtl (loop_dump_stream, initial_value);
fprintf (loop_dump_stream, ".\n");
}
return 0;
}
else if (GET_CODE (final_value) != CONST_INT)
{
if (loop_dump_stream)
{
fprintf (loop_dump_stream,
"Loop iterations: Final value not constant ");
print_simple_rtl (loop_dump_stream, final_value);
fprintf (loop_dump_stream, ".\n");
}
return 0;
}
else if (comparison_code == EQ)
{
rtx inc_once;
if (loop_dump_stream)
fprintf (loop_dump_stream, "Loop iterations: EQ comparison loop.\n");
inc_once = gen_int_mode (INTVAL (initial_value) + INTVAL (increment),
GET_MODE (iteration_var));
if (inc_once == final_value)
{
if (increment == const0_rtx)
return 0;
loop_info->n_iterations = 2;
}
else
loop_info->n_iterations = 1;
if (GET_CODE (loop_info->initial_value) == CONST_INT)
loop_info->final_value
= gen_int_mode ((INTVAL (loop_info->initial_value)
+ loop_info->n_iterations * INTVAL (increment)),
GET_MODE (iteration_var));
else
loop_info->final_value
= plus_constant (loop_info->initial_value,
loop_info->n_iterations * INTVAL (increment));
loop_info->final_equiv_value
= gen_int_mode ((INTVAL (initial_value)
+ loop_info->n_iterations * INTVAL (increment)),
GET_MODE (iteration_var));
return loop_info->n_iterations;
}
if (unsigned_p)
final_larger
= ((unsigned HOST_WIDE_INT) INTVAL (final_value)
> (unsigned HOST_WIDE_INT) INTVAL (initial_value))
- ((unsigned HOST_WIDE_INT) INTVAL (final_value)
< (unsigned HOST_WIDE_INT) INTVAL (initial_value));
else
final_larger = (INTVAL (final_value) > INTVAL (initial_value))
- (INTVAL (final_value) < INTVAL (initial_value));
if (INTVAL (increment) > 0)
increment_dir = 1;
else if (INTVAL (increment) == 0)
increment_dir = 0;
else
increment_dir = -1;
if (final_larger == increment_dir && final_larger != 0
&& (final_larger == compare_dir || compare_dir == 0))
;
else
{
if (loop_dump_stream)
fprintf (loop_dump_stream, "Loop iterations: Not normal loop.\n");
return 0;
}
inc = INTVAL (increment);
if (inc > 0)
{
abs_diff = INTVAL (final_value) - INTVAL (initial_value);
abs_inc = inc;
}
else if (inc < 0)
{
abs_diff = INTVAL (initial_value) - INTVAL (final_value);
abs_inc = -inc;
}
else
abort ();
abs_diff &= ((unsigned HOST_WIDE_INT) 1
<< (GET_MODE_BITSIZE (GET_MODE (iteration_var)) - 1)
<< 1) - 1;
if (compare_dir == 0 && (abs_diff % abs_inc) != 0)
return 0;
loop_info->n_iterations = abs_diff / abs_inc + ((abs_diff % abs_inc) != 0);
return loop_info->n_iterations;
}
static void
strength_reduce (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;
rtx test_reg = gen_rtx_REG (word_mode, LAST_VIRTUAL_REGISTER + 1);
int insn_count = count_insns_in_loop (loop);
addr_placeholder = gen_reg_rtx (Pmode);
ivs->n_regs = max_reg_before_loop;
ivs->regs = xcalloc (ivs->n_regs, sizeof (struct iv));
loop_bivs_find (loop);
if (! ivs->list)
{
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 = 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 (loop, bl);
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 (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 (INSN_P (p))
{
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_dump_stream)
fprintf (loop_dump_stream, "\n");
loop_ivs_free (loop);
if (reg_map)
free (reg_map);
}
static rtx
check_insn_for_bivs (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 (NONJUMP_INSN_P (p)
&& (set = single_set (p))
&& REG_P (SET_DEST (set)))
{
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 = 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 (struct loop *loop, rtx p, int not_every_iteration,
int maybe_multiple)
{
struct loop_regs *regs = LOOP_REGS (loop);
rtx set;
if (NONJUMP_INSN_P (p)
&& (set = single_set (p))
&& REG_P (SET_DEST (set))
&& ! 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 = 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);
}
}
if (NONJUMP_INSN_P (p))
find_mem_givs (loop, PATTERN (p), p, not_every_iteration,
maybe_multiple);
if (INSN_P (p) || LABEL_P (p))
update_giv_derive (loop, p);
return p;
}
static int
valid_initial_value_p (rtx x, rtx insn, int call_seen, rtx loop_start)
{
if (CONSTANT_P (x))
return 1;
if (!REG_P (x)
|| 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 (const struct loop *loop, rtx x, rtx insn,
int not_every_iteration, int 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 = 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 (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;
v->same = 0;
bl = REG_IV_CLASS (ivs, REGNO (dest_reg));
if (bl == 0)
{
bl = 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;
}
else
{
struct induction *induction;
for (induction = bl->biv; induction; induction = induction->next_iv)
if (location == induction->location)
{
v->same = induction;
break;
}
}
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 (const struct loop *loop, struct induction *v, rtx insn,
rtx src_reg, rtx dest_reg, rtx mult_val, rtx add_val,
rtx ext_val, int benefit, enum g_types type,
int not_every_iteration, int 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->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 rtx
final_giv_value (const struct loop *loop, struct induction *v)
{
struct loop_ivs *ivs = LOOP_IVS (loop);
struct iv_class *bl;
rtx insn;
rtx increment, tem;
rtx seq;
rtx loop_end = loop->end;
unsigned HOST_WIDE_INT n_iterations = LOOP_INFO (loop)->n_iterations;
bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
if (bl->reversed)
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Final giv value for %d, depends on reversed biv\n",
REGNO (v->dest_reg));
return const0_rtx;
}
if (n_iterations != 0
&& ! loop->exit_count
&& v->always_executed)
{
increment = biv_total_increment (bl);
if (increment && loop_invariant_p (loop, increment)
&& loop_invariant_p (loop, bl->initial_value))
{
tem = gen_reg_rtx (v->mode);
record_base_value (REGNO (tem), bl->biv->add_val, 0);
loop_iv_add_mult_sink (loop, extend_value_for_giv (v, increment),
GEN_INT (n_iterations),
extend_value_for_giv (v, bl->initial_value),
tem);
for (insn = NEXT_INSN (v->insn); insn != loop_end;
insn = NEXT_INSN (insn))
{
struct induction *biv;
for (biv = bl->biv; biv; biv = biv->next_iv)
if (biv->insn == insn)
{
start_sequence ();
tem = expand_simple_binop (GET_MODE (tem), MINUS, tem,
biv->add_val, NULL_RTX, 0,
OPTAB_LIB_WIDEN);
seq = get_insns ();
end_sequence ();
loop_insn_sink (loop, seq);
}
}
loop_iv_add_mult_sink (loop, tem, v->mult_val, v->add_val, tem);
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Final giv value for %d, calc from biv's value.\n",
REGNO (v->dest_reg));
return tem;
}
}
if (v->replaceable)
abort ();
if (reg_dead_after_loop (loop, v->dest_reg))
{
if (loop_dump_stream)
fprintf (loop_dump_stream,
"Final giv value for %d, giv dead after loop exit.\n",
REGNO (v->dest_reg));
return const0_rtx;
}
return 0;
}
static void
check_final_value (const struct loop *loop, struct induction *v)
{
rtx final_value = 0;
#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 (INSN_P (p))
{
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 (JUMP_P (p) && 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 (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 (LABEL_P (p) || JUMP_P (p)
|| biv->insn == p)
{
if (biv->same)
continue;
for (giv = bl->giv; giv; giv = giv->next_iv)
{
if (giv->cant_derive)
continue;
if (LABEL_P (p) && ! 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 ((LABEL_P (p) && ! biv->always_computable)
|| (JUMP_P (p) && biv->maybe_multiple))
giv->cant_derive = 1;
}
}
}
static int
basic_induction_var (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, last, inc;
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;
last = get_last_insn ();
inc = convert_modes (GET_MODE (dest_reg), GET_MODE (x), arg, 0);
if (get_last_insn () != last)
{
delete_insns_since (last);
return 0;
}
*inc_val = inc;
*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 && NOTE_P (insn)
&& 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) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT
|| 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)
{
last = get_last_insn ();
inc = convert_modes (GET_MODE (dest_reg), mode, x, 0);
if (get_last_insn () != last)
{
delete_insns_since (last);
return 0;
}
*inc_val = inc;
*mult_val = const0_rtx;
return 1;
}
else
return 0;
case SIGN_EXTEND:
if (flag_wrapv)
return 0;
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 && NOTE_P (insn)
&& 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 (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 (enum machine_mode, rtx, rtx);
static rtx sge_plus_constant (rtx, rtx);
static rtx
simplify_giv_expr (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 (REG_P (arg0))
arg0 = gen_rtx_MULT (mode, arg0, const1_rtx);
if (REG_P (arg1))
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 && REG_P (arg0))
{
*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 (rtx x, rtx 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 (enum machine_mode mode, rtx x, rtx 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 (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 = 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))
&& REG_P (SET_DEST (set))
&& 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 (rtx a, rtx b, rtx 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;
}
static rtx
express_from (struct induction *g1, struct induction *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
|| (g1->mult_val == constm1_rtx
&& INTVAL (g2->mult_val)
== (HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))
|| 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 (struct induction *g1, struct induction *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))
return ret;
return NULL_RTX;
}
static HOST_WIDE_INT
get_monotonic_increment (struct iv_class *bl)
{
struct induction *v;
rtx incr;
incr = biv_total_increment (bl);
if (incr == 0 || GET_CODE (incr) != CONST_INT)
return 0;
for (v = bl->biv; v != 0; v = v->next_iv)
{
if (GET_CODE (v->add_val) != CONST_INT)
return 0;
if (INTVAL (v->add_val) < 0 && INTVAL (incr) >= 0)
return 0;
if (INTVAL (v->add_val) > 0 && INTVAL (incr) <= 0)
return 0;
}
return INTVAL (incr);
}
static bool
biased_biv_fits_mode_p (const struct loop *loop, struct iv_class *bl,
HOST_WIDE_INT incr, enum machine_mode mode,
unsigned HOST_WIDE_INT bias)
{
unsigned HOST_WIDE_INT initial, maximum, span, delta;
if (HOST_BITS_PER_WIDE_INT < GET_MODE_BITSIZE (mode))
return false;
if (LOOP_INFO (loop)->n_iterations == 0)
return false;
if (bl->initial_value == 0 || GET_CODE (bl->initial_value) != CONST_INT)
return false;
initial = bias + INTVAL (bl->initial_value);
maximum = GET_MODE_MASK (mode);
if (initial > maximum)
return false;
if (incr < 0)
{
delta = -incr;
span = initial;
}
else
{
delta = incr;
if (maximum + 1 == initial)
span = LOOP_INFO (loop)->n_iterations * delta;
else
span = maximum + 1 - initial;
}
return (span / LOOP_INFO (loop)->n_iterations >= delta);
}
static bool
biv_fits_mode_p (const struct loop *loop, struct iv_class *bl,
HOST_WIDE_INT incr, enum machine_mode mode, bool unsignedp)
{
struct loop_info *loop_info;
unsigned HOST_WIDE_INT bias;
if (GET_MODE_SIZE (mode) > GET_MODE_SIZE (GET_MODE (bl->biv->src_reg)))
mode = GET_MODE (bl->biv->src_reg);
loop_info = LOOP_INFO (loop);
bias = (unsignedp ? 0 : (GET_MODE_MASK (mode) >> 1) + 1);
if (biased_biv_fits_mode_p (loop, bl, incr, mode, bias))
return true;
if (mode == GET_MODE (bl->biv->src_reg)
&& bl->biv->src_reg == loop_info->iteration_var
&& loop_info->comparison_value
&& loop_invariant_p (loop, loop_info->comparison_value))
{
if (incr == 1)
{
if (loop_info->comparison_code == LT)
return true;
if (loop_info->comparison_code == LTU && unsignedp)
return true;
}
if (incr == -1)
{
if (loop_info->comparison_code == GT)
return true;
if (loop_info->comparison_code == GTU && unsignedp)
return true;
}
}
return false;
}
static bool
extension_within_bounds_p (const struct loop *loop, struct iv_class *bl,
HOST_WIDE_INT incr, rtx x)
{
enum machine_mode mode;
bool signedp, unsignedp;
switch (GET_CODE (x))
{
case SIGN_EXTEND:
case ZERO_EXTEND:
mode = GET_MODE (XEXP (x, 0));
signedp = (GET_CODE (x) == SIGN_EXTEND);
unsignedp = (GET_CODE (x) == ZERO_EXTEND);
break;
case TRUNCATE:
mode = GET_MODE (x);
signedp = unsignedp = true;
break;
default:
abort ();
}
return ((!signedp || biv_fits_mode_p (loop, bl, incr, mode, false))
&& (!unsignedp || biv_fits_mode_p (loop, bl, incr, mode, true)));
}
static void
check_ext_dependent_givs (const struct loop *loop, struct iv_class *bl)
{
struct induction *v;
HOST_WIDE_INT incr;
incr = get_monotonic_increment (bl);
for (v = bl->giv; v; v = v->next_iv)
if (v->ext_dependent)
{
if (incr != 0
&& extension_within_bounds_p (loop, bl, incr, v->ext_dependent))
{
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)
fprintf (loop_dump_stream,
"Failed ext dependent giv at %d\n",
INSN_UID (v->insn));
v->ignore = 1;
bl->all_reduced = 0;
}
}
}
static rtx
extend_value_for_giv (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 (const void *xp, const void *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 (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 = 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 = xcalloc (giv_count, sizeof (*stats));
can_combine = 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 (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 (const struct loop *loop ATTRIBUTE_UNUSED, rtx seq)
{
rtx insn;
insn = seq;
while (insn != NULL_RTX)
{
rtx set = single_set (insn);
if (set && REG_P (SET_DEST (set)))
record_base_value (REGNO (SET_DEST (set)), SET_SRC (set), 0);
insn = NEXT_INSN (insn);
}
}
static void
loop_iv_add_mult_emit_before (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);
}
static void
loop_iv_add_mult_sink (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);
}
static void
loop_iv_add_mult_hoist (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 (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 (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 (tmp == NULL_RTX)
;
else if (INSN_P (tmp))
{
n_insns = 0;
while (tmp != NULL_RTX)
{
rtx next = NEXT_INSN (tmp);
if (++n_insns > 3
|| !NONJUMP_INSN_P (tmp)
|| (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 (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;
enum machine_mode mode;
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, false, true);
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))
&& JUMP_P (jump1))
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)
for (bl = ivs->list; bl; bl = bl->next)
if (bl->biv_count == 1
&& ! bl->biv->maybe_multiple
&& bl->biv->dest_reg == XEXP (comparison, 1)
&& ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn,
first_compare))
{
comparison = gen_rtx_fmt_ee (swap_condition (GET_CODE (comparison)),
VOIDmode,
XEXP (comparison, 1),
XEXP (comparison, 0));
break;
}
if (! bl)
return 0;
if (((GET_CODE (comparison) == GT && XEXP (comparison, 1) == constm1_rtx)
|| (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 (LABEL_P (p))
break;
if (!JUMP_P (p))
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
|| GET_CODE (before_comparison) == LTU)
&& 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 && REG_P (SET_DEST (set))
&& REGNO (SET_DEST (set)) == bl->regno)
;
else if (!reg_mentioned_p (bivreg, PATTERN (p)))
;
else if (p == prev_nonnote_insn (prev_nonnote_insn (loop_end))
|| p == prev_nonnote_insn (loop_end))
{
note_stores (PATTERN (p), note_set_pseudo_multiple_uses,
regs);
if (regs->multiple_uses)
{
no_use_except_counting = 0;
break;
}
}
else
{
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;
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)
|| GET_CODE (comparison) == LTU))
{
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;
bool keep_first_compare;
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
&& 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
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;
mode = GET_MODE (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_mode (comparison_val - add_adjust, mode);
loop_insn_hoist (loop, gen_move_insn (reg, start_value));
}
else if (GET_CODE (initial_value) == CONST_INT)
{
rtx offset = GEN_INT (-INTVAL (initial_value) - add_adjust);
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)
{
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))++;
keep_first_compare = (compare_and_branch == 2
#ifdef HAVE_CC0
&& sets_cc0_p (first_compare) <= 0
#endif
);
if (keep_first_compare
|| (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));
if (keep_first_compare)
loop_insn_sink (loop, PATTERN (first_compare));
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,
mode, 0,
XEXP (jump_label, 0));
tem = get_insns ();
end_sequence ();
emit_jump_insn_before (tem, loop_end);
for (tem = PREV_INSN (loop_end);
tem && !JUMP_P (tem);
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
|| !REG_P (SET_DEST (set))
|| (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 (const struct loop *loop, struct iv_class *bl,
int eliminate_p, int threshold, int 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 (INSN_P (p))
{
note = find_reg_note (p, REG_LIBCALL, NULL_RTX);
if (note)
{
rtx last = XEXP (note, 0);
rtx set = single_set (last);
if (set && REG_P (SET_DEST (set)))
{
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;
}
static int
loop_insn_first_p (rtx insn, rtx 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
&& !NOTE_P (p))
return INSN_LUID (p) <= INSN_LUID (q);
if (INSN_UID (p) >= max_uid_for_loop
|| NOTE_P (p))
p = NEXT_INSN (p);
if (INSN_UID (q) >= max_uid_for_loop)
q = NEXT_INSN (q);
}
}
static int
biv_elimination_giv_has_0_offset (struct induction *biv,
struct induction *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 (const struct loop *loop, rtx x, rtx 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
|| (REG_P (v->add_val)
&& 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
|| (REG_P (v->add_val)
&& 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 (REG_P (arg) || MEM_P (arg))
{
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 (!REG_P (arg)
|| 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 (rtx reg, rtx insn)
{
rtx n;
for (n = insn;
n && !LABEL_P (n) && !JUMP_P (n);
n = NEXT_INSN (n))
{
if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (n))
return 1;
}
return 0;
}
static void
record_initial (rtx dest, rtx set, void *data ATTRIBUTE_UNUSED)
{
struct loop_ivs *ivs = (struct loop_ivs *) data;
struct iv_class *bl;
if (!REG_P (dest)
|| 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 (rtx x, rtx insn)
{
if (REG_P (x) && 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);
}
}
}
static rtx
get_condition_for_loop (const struct loop *loop, rtx x)
{
rtx comparison = get_condition (x, (rtx*) 0, false, true);
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 (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 (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 (MEM_VOLATILE_P (m) && !MEM_VOLATILE_P (loop_info->mems[i].mem))
loop_info->mems[i].mem = m;
if (GET_MODE (m) != GET_MODE (loop_info->mems[i].mem))
loop_info->mems[i].optimizable = 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 = 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].optimizable = (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 (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 = 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 = 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 (LABEL_P (insn) || JUMP_P (insn))
memset (last_set, 0, regs->num * sizeof (rtx));
if (CALL_P (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
&& REG_P (reg = XEXP (op, 0))
&& 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 (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 (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 && !LABEL_P (end_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 (LABEL_P (p))
maybe_never = 1;
else if (JUMP_P (p)
&& ! (JUMP_P (p)
&& 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) && !LABEL_P (p);
p = PREV_INSN (p))
;
prev_ebb_head = p;
cselib_init (true);
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].optimizable = 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].optimizable = 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].optimizable = 0;
if (loop_info->mems[i].optimizable && 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].optimizable = 0;
break;
}
}
}
if (maybe_never && may_trap_p (mem))
loop_info->mems[i].optimizable = 0;
if (!loop_info->mems[i].optimizable)
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
&& REG_P (SET_DEST (set))
&& 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
&& REG_P (SET_SRC (set))
&& 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 (CALL_P (p)
&& reg_mentioned_p (loop_info->mems[i].mem,
CALL_INSN_FUNCTION_USAGE (p)))
{
cancel_changes (0);
loop_info->mems[i].optimizable = 0;
break;
}
else
replace_loop_mems (p, loop_info->mems[i].mem,
loop_info->mems[i].reg, written);
}
if (LABEL_P (p)
|| JUMP_P (p))
maybe_never = 1;
}
if (! loop_info->mems[i].optimizable)
;
else if (! apply_change_group ())
loop_info->mems[i].optimizable = 0;
else
{
cselib_val *e = cselib_lookup (mem, VOIDmode, 0);
rtx set;
rtx best = mem;
unsigned j;
struct elt_loc_list *const_equiv = 0;
reg_set_iterator rsi;
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 (REG_P (equiv->loc)
&& 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, rsi)
{
try_copy_prop (loop, reg, j);
}
CLEAR_REG_SET (&load_copies);
EXECUTE_IF_SET_IN_REG_SET
(&store_copies, FIRST_PSEUDO_REGISTER, j, rsi)
{
try_swap_copy_prop (loop, reg, j);
}
CLEAR_REG_SET (&store_copies);
}
}
if (label != NULL_RTX && end_label != NULL_RTX)
for (p = loop->start; p != loop->end; p = NEXT_INSN (p))
if (JUMP_P (p) && JUMP_LABEL (p) == end_label)
redirect_jump (p, label, false);
cselib_finish ();
}
struct note_reg_stored_arg
{
int set_seen;
rtx reg;
};
static void
note_reg_stored (rtx x, rtx 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 (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 (LABEL_P (insn) && init_insn)
break;
if (! INSN_P (insn))
continue;
set = single_set (insn);
if (set
&& REG_P (SET_DEST (set))
&& 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 (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 (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))
&& REG_P (SET_DEST (set))
&& REGNO (SET_DEST (set)) == new_regno
&& REG_P (SET_SRC (set))
&& 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))
&& REG_P (SET_DEST (prev_set))
&& 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
find_mem_in_note_1 (rtx *x, void *data)
{
if (*x != NULL_RTX && MEM_P (*x))
{
rtx *res = (rtx *) data;
*res = *x;
return 1;
}
return 0;
}
static rtx
find_mem_in_note (rtx note)
{
if (note && for_each_rtx (¬e, find_mem_in_note_1, ¬e))
return note;
return NULL_RTX;
}
static int
replace_loop_mem (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 (rtx insn, rtx mem, rtx reg, int written)
{
loop_replace_args args;
args.insn = insn;
args.match = mem;
args.replacement = reg;
for_each_rtx (&insn, replace_loop_mem, &args);
if (written)
{
rtx note, sub;
rtx *link;
for (link = ®_NOTES (insn); (note = *link); link = &XEXP (note, 1))
{
if (REG_NOTE_KIND (note) == REG_EQUAL
&& (sub = find_mem_in_note (note))
&& true_dependence (mem, VOIDmode, sub, rtx_varies_p))
{
validate_change (NULL_RTX, link, XEXP (note, 1), 1);
break;
}
}
}
}
static int
replace_loop_reg (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 (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 rtx
loop_insn_emit_after (const struct loop *loop ATTRIBUTE_UNUSED,
basic_block where_bb ATTRIBUTE_UNUSED, rtx where_insn,
rtx pattern)
{
return emit_insn_after (pattern, where_insn);
}
static rtx
loop_insn_emit_before (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 (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);
}
static rtx
loop_insn_hoist (const struct loop *loop, rtx pattern)
{
return loop_insn_emit_before (loop, 0, loop->start, pattern);
}
static rtx
loop_call_insn_hoist (const struct loop *loop, rtx pattern)
{
return loop_call_insn_emit_before (loop, 0, loop->start, pattern);
}
static rtx
loop_insn_sink (const struct loop *loop, rtx pattern)
{
return loop_insn_emit_before (loop, 0, loop->sink, pattern);
}
static rtx
gen_load_of_final_value (rtx reg, rtx 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 (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 (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 (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 (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 (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 (const struct loop *loop)
{
loop_ivs_dump (loop, stderr, 1);
}
void
debug_iv_class (const struct iv_class *bl)
{
loop_iv_class_dump (bl, stderr, 1);
}
void
debug_biv (const struct induction *v)
{
loop_biv_dump (v, stderr, 1);
}
void
debug_giv (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) ? (NOTE_P (INSN) \
? 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 (const struct loop *loop, FILE *file,
int verbose ATTRIBUTE_UNUSED)
{
rtx label;
if (! loop || ! file || !BB_HEAD (loop->first))
return;
if (! PREV_INSN (BB_HEAD (loop->first))
|| !NOTE_P (PREV_INSN (BB_HEAD (loop->first)))
|| NOTE_LINE_NUMBER (PREV_INSN (BB_HEAD (loop->first)))
!= NOTE_INSN_LOOP_BEG)
fprintf (file, ";; No NOTE_INSN_LOOP_BEG at %d\n",
INSN_UID (PREV_INSN (BB_HEAD (loop->first))));
if (! NEXT_INSN (BB_END (loop->last))
|| !NOTE_P (NEXT_INSN (BB_END (loop->last)))
|| NOTE_LINE_NUMBER (NEXT_INSN (BB_END (loop->last)))
!= NOTE_INSN_LOOP_END)
fprintf (file, ";; No NOTE_INSN_LOOP_END at %d\n",
INSN_UID (NEXT_INSN (BB_END (loop->last))));
if (loop->start)
{
fprintf (file,
";; start %d (%d), end %d (%d)\n",
LOOP_BLOCK_NUM (loop->start),
LOOP_INSN_UID (loop->start),
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);
}
}
void
debug_loop (const struct loop *loop)
{
flow_loop_dump (loop, stderr, loop_dump_aux, 1);
}
void
debug_loops (const struct loops *loops)
{
flow_loops_dump (loops, stderr, loop_dump_aux, 1);
}