#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "toplev.h"
#include "rtl.h"
#include "tree.h"
#include "tm_p.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
#include "real.h"
#include "insn-config.h"
#include "recog.h"
#include "basic-block.h"
#include "output.h"
#include "function.h"
#include "expr.h"
#include "except.h"
#include "ggc.h"
#include "params.h"
#include "cselib.h"
#include "intl.h"
#include "obstack.h"
#include "timevar.h"
static FILE *gcse_file;
static int run_jump_opt_after_gcse;
static FILE *debug_stderr;
static struct obstack gcse_obstack;
struct reg_use {rtx reg_rtx; };
struct expr
{
rtx expr;
int bitmap_index;
struct expr *next_same_hash;
struct occr *antic_occr;
struct occr *avail_occr;
rtx reaching_reg;
};
struct occr
{
struct occr *next;
rtx insn;
char deleted_p;
char copied_p;
};
struct hash_table
{
struct expr **table;
unsigned int size;
unsigned int n_elems;
int set_p;
};
static struct hash_table expr_hash_table;
static struct hash_table set_hash_table;
static int *uid_cuid;
static int max_uid;
#ifdef ENABLE_CHECKING
#define INSN_CUID(INSN) \
(gcc_assert (INSN_UID (INSN) <= max_uid), uid_cuid[INSN_UID (INSN)])
#else
#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
#endif
static int max_cuid;
static rtx *cuid_insn;
#define CUID_INSN(CUID) (cuid_insn[CUID])
static unsigned int max_gcse_regno;
typedef struct reg_set
{
struct reg_set *next;
int bb_index;
} reg_set;
static reg_set **reg_set_table;
static int reg_set_table_size;
#define REG_SET_TABLE_SLOP 100
struct ls_expr
{
struct expr * expr;
rtx pattern;
rtx pattern_regs;
rtx loads;
rtx stores;
struct ls_expr * next;
int invalid;
int index;
unsigned int hash_index;
rtx reaching_reg;
};
static rtx *implicit_sets;
static struct ls_expr * pre_ldst_mems = NULL;
static regset reg_set_bitmap;
static sbitmap *reg_set_in_block;
static rtx * modify_mem_list;
static bitmap modify_mem_list_set;
static rtx * canon_modify_mem_list;
static bitmap blocks_with_calls;
static int bytes_used;
static int gcse_subst_count;
static int gcse_create_count;
static int local_const_prop_count;
static int local_copy_prop_count;
static int global_const_prop_count;
static int global_copy_prop_count;
static sbitmap *ae_kill, *ae_gen;
static void compute_can_copy (void);
static void *gmalloc (size_t) ATTRIBUTE_MALLOC;
static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC;
static void *grealloc (void *, size_t);
static void *gcse_alloc (unsigned long);
static void alloc_gcse_mem (rtx);
static void free_gcse_mem (void);
static void alloc_reg_set_mem (int);
static void free_reg_set_mem (void);
static void record_one_set (int, rtx);
static void record_set_info (rtx, rtx, void *);
static void compute_sets (rtx);
static void hash_scan_insn (rtx, struct hash_table *, int);
static void hash_scan_set (rtx, rtx, struct hash_table *);
static void hash_scan_clobber (rtx, rtx, struct hash_table *);
static void hash_scan_call (rtx, rtx, struct hash_table *);
static int want_to_gcse_p (rtx);
static bool can_assign_to_reg_p (rtx);
static bool gcse_constant_p (rtx);
static int oprs_unchanged_p (rtx, rtx, int);
static int oprs_anticipatable_p (rtx, rtx);
static int oprs_available_p (rtx, rtx);
static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int,
struct hash_table *);
static void insert_set_in_table (rtx, rtx, struct hash_table *);
static unsigned int hash_expr (rtx, enum machine_mode, int *, int);
static unsigned int hash_set (int, int);
static int expr_equiv_p (rtx, rtx);
static void record_last_reg_set_info (rtx, int);
static void record_last_mem_set_info (rtx);
static void record_last_set_info (rtx, rtx, void *);
static void compute_hash_table (struct hash_table *);
static void alloc_hash_table (int, struct hash_table *, int);
static void free_hash_table (struct hash_table *);
static void compute_hash_table_work (struct hash_table *);
static void dump_hash_table (FILE *, const char *, struct hash_table *);
static struct expr *lookup_set (unsigned int, struct hash_table *);
static struct expr *next_set (unsigned int, struct expr *);
static void reset_opr_set_tables (void);
static int oprs_not_set_p (rtx, rtx);
static void mark_call (rtx);
static void mark_set (rtx, rtx);
static void mark_clobber (rtx, rtx);
static void mark_oprs_set (rtx);
static void alloc_cprop_mem (int, int);
static void free_cprop_mem (void);
static void compute_transp (rtx, int, sbitmap *, int);
static void compute_transpout (void);
static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *,
struct hash_table *);
static void compute_cprop_data (void);
static void find_used_regs (rtx *, void *);
static int try_replace_reg (rtx, rtx, rtx);
static struct expr *find_avail_set (int, rtx);
static int cprop_jump (basic_block, rtx, rtx, rtx, rtx);
static void mems_conflict_for_gcse_p (rtx, rtx, void *);
static int load_killed_in_block_p (basic_block, int, rtx, int);
static void canon_list_insert (rtx, rtx, void *);
static int cprop_insn (rtx, int);
static int cprop (int);
static void find_implicit_sets (void);
static int one_cprop_pass (int, int, int);
static bool constprop_register (rtx, rtx, rtx, int);
static struct expr *find_bypass_set (int, int);
static bool reg_killed_on_edge (rtx, edge);
static int bypass_block (basic_block, rtx, rtx);
static int bypass_conditional_jumps (void);
static void alloc_pre_mem (int, int);
static void free_pre_mem (void);
static void compute_pre_data (void);
static int pre_expr_reaches_here_p (basic_block, struct expr *,
basic_block);
static void insert_insn_end_bb (struct expr *, basic_block, int);
static void pre_insert_copy_insn (struct expr *, rtx);
static void pre_insert_copies (void);
static int pre_delete (void);
static int pre_gcse (void);
static int one_pre_gcse_pass (int);
static void add_label_notes (rtx, rtx);
static void alloc_code_hoist_mem (int, int);
static void free_code_hoist_mem (void);
static void compute_code_hoist_vbeinout (void);
static void compute_code_hoist_data (void);
static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *);
static void hoist_code (void);
static int one_code_hoisting_pass (void);
static rtx process_insert_insn (struct expr *);
static int pre_edge_insert (struct edge_list *, struct expr **);
static int pre_expr_reaches_here_p_work (basic_block, struct expr *,
basic_block, char *);
static struct ls_expr * ldst_entry (rtx);
static void free_ldst_entry (struct ls_expr *);
static void free_ldst_mems (void);
static void print_ldst_list (FILE *);
static struct ls_expr * find_rtx_in_ldst (rtx);
static int enumerate_ldsts (void);
static inline struct ls_expr * first_ls_expr (void);
static inline struct ls_expr * next_ls_expr (struct ls_expr *);
static int simple_mem (rtx);
static void invalidate_any_buried_refs (rtx);
static void compute_ld_motion_mems (void);
static void trim_ld_motion_mems (void);
static void update_ld_motion_stores (struct expr *);
static void reg_set_info (rtx, rtx, void *);
static void reg_clear_last_set (rtx, rtx, void *);
static bool store_ops_ok (rtx, int *);
static rtx extract_mentioned_regs (rtx);
static rtx extract_mentioned_regs_helper (rtx, rtx);
static void find_moveable_store (rtx, int *, int *);
static int compute_store_table (void);
static bool load_kills_store (rtx, rtx, int);
static bool find_loads (rtx, rtx, int);
static bool store_killed_in_insn (rtx, rtx, rtx, int);
static bool store_killed_after (rtx, rtx, rtx, basic_block, int *, rtx *);
static bool store_killed_before (rtx, rtx, rtx, basic_block, int *);
static void build_store_vectors (void);
static void insert_insn_start_bb (rtx, basic_block);
static int insert_store (struct ls_expr *, edge);
static void remove_reachable_equiv_notes (basic_block, struct ls_expr *);
static void replace_store_insn (rtx, rtx, basic_block, struct ls_expr *);
static void delete_store (struct ls_expr *, basic_block);
static void free_store_memory (void);
static void store_motion (void);
static void free_insn_expr_list_list (rtx *);
static void clear_modify_mem_tables (void);
static void free_modify_mem_tables (void);
static rtx gcse_emit_move_after (rtx, rtx, rtx);
static void local_cprop_find_used_regs (rtx *, void *);
static bool do_local_cprop (rtx, rtx, int, rtx*);
static bool adjust_libcall_notes (rtx, rtx, rtx, rtx*);
static void local_cprop_pass (int);
static bool is_too_expensive (const char *);
int
gcse_main (rtx f, FILE *file)
{
int changed, pass;
int initial_bytes_used;
int max_pass_bytes;
char *gcse_obstack_bottom;
if (current_function_calls_setjmp)
return 0;
run_jump_opt_after_gcse = 0;
debug_stderr = stderr;
gcse_file = file;
max_gcse_regno = max_reg_num ();
if (file)
dump_flow_info (file);
if (n_basic_blocks <= 1 || is_too_expensive (_("GCSE disabled")))
return 0;
gcc_obstack_init (&gcse_obstack);
bytes_used = 0;
init_alias_analysis ();
alloc_reg_set_mem (max_gcse_regno);
compute_sets (f);
pass = 0;
initial_bytes_used = bytes_used;
max_pass_bytes = 0;
gcse_obstack_bottom = gcse_alloc (1);
changed = 1;
while (changed && pass < MAX_GCSE_PASSES)
{
changed = 0;
if (file)
fprintf (file, "GCSE pass %d\n\n", pass + 1);
bytes_used = initial_bytes_used;
max_gcse_regno = max_reg_num ();
alloc_gcse_mem (f);
timevar_push (TV_CPROP1);
changed = one_cprop_pass (pass + 1, 0, 0);
timevar_pop (TV_CPROP1);
free_gcse_mem ();
max_gcse_regno = max_reg_num ();
alloc_gcse_mem (f);
free_reg_set_mem ();
alloc_reg_set_mem (max_reg_num ());
compute_sets (f);
if (optimize_size)
;
else
{
timevar_push (TV_PRE);
changed |= one_pre_gcse_pass (pass + 1);
if (changed)
{
free_modify_mem_tables ();
modify_mem_list = gcalloc (last_basic_block, sizeof (rtx));
canon_modify_mem_list = gcalloc (last_basic_block, sizeof (rtx));
}
free_reg_set_mem ();
alloc_reg_set_mem (max_reg_num ());
compute_sets (f);
run_jump_opt_after_gcse = 1;
timevar_pop (TV_PRE);
}
if (max_pass_bytes < bytes_used)
max_pass_bytes = bytes_used;
free_gcse_mem ();
if (optimize_size)
{
timevar_push (TV_HOIST);
max_gcse_regno = max_reg_num ();
alloc_gcse_mem (f);
changed |= one_code_hoisting_pass ();
free_gcse_mem ();
if (max_pass_bytes < bytes_used)
max_pass_bytes = bytes_used;
timevar_pop (TV_HOIST);
}
if (file)
{
fprintf (file, "\n");
fflush (file);
}
obstack_free (&gcse_obstack, gcse_obstack_bottom);
pass++;
}
max_gcse_regno = max_reg_num ();
alloc_gcse_mem (f);
timevar_push (TV_CPROP2);
one_cprop_pass (pass + 1, 1, 0);
timevar_pop (TV_CPROP2);
free_gcse_mem ();
if (file)
{
fprintf (file, "GCSE of %s: %d basic blocks, ",
current_function_name (), n_basic_blocks);
fprintf (file, "%d pass%s, %d bytes\n\n",
pass, pass > 1 ? "es" : "", max_pass_bytes);
}
obstack_free (&gcse_obstack, NULL);
free_reg_set_mem ();
end_alias_analysis ();
allocate_reg_info (max_reg_num (), FALSE, FALSE);
if (!optimize_size && flag_gcse_sm)
{
timevar_push (TV_LSM);
store_motion ();
timevar_pop (TV_LSM);
}
return run_jump_opt_after_gcse;
}
static char can_copy[(int) NUM_MACHINE_MODES];
static void
compute_can_copy (void)
{
int i;
#ifndef AVOID_CCMODE_COPIES
rtx reg, insn;
#endif
memset (can_copy, 0, NUM_MACHINE_MODES);
start_sequence ();
for (i = 0; i < NUM_MACHINE_MODES; i++)
if (GET_MODE_CLASS (i) == MODE_CC)
{
#ifdef AVOID_CCMODE_COPIES
can_copy[i] = 0;
#else
reg = gen_rtx_REG ((enum machine_mode) i, LAST_VIRTUAL_REGISTER + 1);
insn = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
if (recog (PATTERN (insn), insn, NULL) >= 0)
can_copy[i] = 1;
#endif
}
else
can_copy[i] = 1;
end_sequence ();
}
bool
can_copy_p (enum machine_mode mode)
{
static bool can_copy_init_p = false;
if (! can_copy_init_p)
{
compute_can_copy ();
can_copy_init_p = true;
}
return can_copy[mode] != 0;
}
static void *
gmalloc (size_t size)
{
bytes_used += size;
return xmalloc (size);
}
static void *
gcalloc (size_t nelem, size_t elsize)
{
bytes_used += nelem * elsize;
return xcalloc (nelem, elsize);
}
static void *
grealloc (void *ptr, size_t size)
{
return xrealloc (ptr, size);
}
static void *
gcse_alloc (unsigned long size)
{
bytes_used += size;
return obstack_alloc (&gcse_obstack, size);
}
static void
alloc_gcse_mem (rtx f)
{
int i;
rtx insn;
max_uid = get_max_uid ();
uid_cuid = gcalloc (max_uid + 1, sizeof (int));
for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
uid_cuid[INSN_UID (insn)] = i++;
else
uid_cuid[INSN_UID (insn)] = i;
}
max_cuid = i;
cuid_insn = gcalloc (max_cuid + 1, sizeof (rtx));
for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
if (INSN_P (insn))
CUID_INSN (i++) = insn;
reg_set_bitmap = BITMAP_ALLOC (NULL);
reg_set_in_block = sbitmap_vector_alloc (last_basic_block, max_gcse_regno);
modify_mem_list = gcalloc (last_basic_block, sizeof (rtx));
canon_modify_mem_list = gcalloc (last_basic_block, sizeof (rtx));
modify_mem_list_set = BITMAP_ALLOC (NULL);
blocks_with_calls = BITMAP_ALLOC (NULL);
}
static void
free_gcse_mem (void)
{
free (uid_cuid);
free (cuid_insn);
BITMAP_FREE (reg_set_bitmap);
sbitmap_vector_free (reg_set_in_block);
free_modify_mem_tables ();
BITMAP_FREE (modify_mem_list_set);
BITMAP_FREE (blocks_with_calls);
}
static void
compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc,
struct hash_table *table)
{
unsigned int i;
if (transp)
{
if (table->set_p)
sbitmap_vector_zero (transp, last_basic_block);
else
sbitmap_vector_ones (transp, last_basic_block);
}
if (comp)
sbitmap_vector_zero (comp, last_basic_block);
if (antloc)
sbitmap_vector_zero (antloc, last_basic_block);
for (i = 0; i < table->size; i++)
{
struct expr *expr;
for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
{
int indx = expr->bitmap_index;
struct occr *occr;
if (transp)
compute_transp (expr->expr, indx, transp, table->set_p);
if (antloc)
for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
{
SET_BIT (antloc[BLOCK_NUM (occr->insn)], indx);
occr->deleted_p = 0;
}
if (comp)
for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
{
SET_BIT (comp[BLOCK_NUM (occr->insn)], indx);
occr->copied_p = 0;
}
expr->reaching_reg = 0;
}
}
}
static struct obstack reg_set_obstack;
static void
alloc_reg_set_mem (int n_regs)
{
reg_set_table_size = n_regs + REG_SET_TABLE_SLOP;
reg_set_table = gcalloc (reg_set_table_size, sizeof (struct reg_set *));
gcc_obstack_init (®_set_obstack);
}
static void
free_reg_set_mem (void)
{
free (reg_set_table);
obstack_free (®_set_obstack, NULL);
}
static void
record_one_set (int regno, rtx insn)
{
struct reg_set *new_reg_info;
if (regno >= reg_set_table_size)
{
int new_size = regno + REG_SET_TABLE_SLOP;
reg_set_table = grealloc (reg_set_table,
new_size * sizeof (struct reg_set *));
memset (reg_set_table + reg_set_table_size, 0,
(new_size - reg_set_table_size) * sizeof (struct reg_set *));
reg_set_table_size = new_size;
}
new_reg_info = obstack_alloc (®_set_obstack, sizeof (struct reg_set));
bytes_used += sizeof (struct reg_set);
new_reg_info->bb_index = BLOCK_NUM (insn);
new_reg_info->next = reg_set_table[regno];
reg_set_table[regno] = new_reg_info;
}
static void
record_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data)
{
rtx record_set_insn = (rtx) data;
if (REG_P (dest) && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
record_one_set (REGNO (dest), record_set_insn);
}
static void
compute_sets (rtx f)
{
rtx insn;
for (insn = f; insn != 0; insn = NEXT_INSN (insn))
if (INSN_P (insn))
note_stores (PATTERN (insn), record_set_info, insn);
}
struct reg_avail_info
{
basic_block last_bb;
int first_set;
int last_set;
};
static struct reg_avail_info *reg_avail_info;
static basic_block current_bb;
static int
want_to_gcse_p (rtx x)
{
switch (GET_CODE (x))
{
case REG:
case SUBREG:
case CONST_INT:
case CONST_DOUBLE:
case CONST_VECTOR:
case CALL:
return 0;
default:
return can_assign_to_reg_p (x);
}
}
static GTY(()) rtx test_insn;
static bool
can_assign_to_reg_p (rtx x)
{
int num_clobbers = 0;
int icode;
if (general_operand (x, GET_MODE (x)))
return 1;
else if (GET_MODE (x) == VOIDmode)
return 0;
if (test_insn == 0)
{
test_insn
= make_insn_raw (gen_rtx_SET (VOIDmode,
gen_rtx_REG (word_mode,
FIRST_PSEUDO_REGISTER * 2),
const0_rtx));
NEXT_INSN (test_insn) = PREV_INSN (test_insn) = 0;
}
PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x));
SET_SRC (PATTERN (test_insn)) = x;
return ((icode = recog (PATTERN (test_insn), test_insn, &num_clobbers)) >= 0
&& (num_clobbers == 0 || ! added_clobbers_hard_reg_p (icode)));
}
static int
oprs_unchanged_p (rtx x, rtx insn, int avail_p)
{
int i, j;
enum rtx_code code;
const char *fmt;
if (x == 0)
return 1;
code = GET_CODE (x);
switch (code)
{
case REG:
{
struct reg_avail_info *info = ®_avail_info[REGNO (x)];
if (info->last_bb != current_bb)
return 1;
if (avail_p)
return info->last_set < INSN_CUID (insn);
else
return info->first_set >= INSN_CUID (insn);
}
case MEM:
if (load_killed_in_block_p (current_bb, INSN_CUID (insn),
x, avail_p))
return 0;
else
return oprs_unchanged_p (XEXP (x, 0), insn, avail_p);
case PRE_DEC:
case PRE_INC:
case POST_DEC:
case POST_INC:
case PRE_MODIFY:
case POST_MODIFY:
return 0;
case PC:
case CC0:
case CONST:
case CONST_INT:
case CONST_DOUBLE:
case CONST_VECTOR:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
case ADDR_DIFF_VEC:
return 1;
default:
break;
}
for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
{
if (fmt[i] == 'e')
{
if (i == 0)
return oprs_unchanged_p (XEXP (x, i), insn, avail_p);
else if (! oprs_unchanged_p (XEXP (x, i), insn, avail_p))
return 0;
}
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p))
return 0;
}
return 1;
}
static int gcse_mems_conflict_p;
static rtx gcse_mem_operand;
static void
mems_conflict_for_gcse_p (rtx dest, rtx setter ATTRIBUTE_UNUSED,
void *data ATTRIBUTE_UNUSED)
{
while (GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT
|| GET_CODE (dest) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
if (! MEM_P (dest))
return;
if (expr_equiv_p (dest, gcse_mem_operand) && pre_ldst_mems != NULL)
{
if (!find_rtx_in_ldst (dest))
gcse_mems_conflict_p = 1;
return;
}
if (true_dependence (dest, GET_MODE (dest), gcse_mem_operand,
rtx_addr_varies_p))
gcse_mems_conflict_p = 1;
}
static int
load_killed_in_block_p (basic_block bb, int uid_limit, rtx x, int avail_p)
{
rtx list_entry = modify_mem_list[bb->index];
while (list_entry)
{
rtx setter;
if ((avail_p
&& INSN_CUID (XEXP (list_entry, 0)) < uid_limit)
|| (! avail_p
&& INSN_CUID (XEXP (list_entry, 0)) > uid_limit))
{
list_entry = XEXP (list_entry, 1);
continue;
}
setter = XEXP (list_entry, 0);
if (CALL_P (setter))
return 1;
gcse_mem_operand = x;
gcse_mems_conflict_p = 0;
note_stores (PATTERN (setter), mems_conflict_for_gcse_p, NULL);
if (gcse_mems_conflict_p)
return 1;
list_entry = XEXP (list_entry, 1);
}
return 0;
}
static int
oprs_anticipatable_p (rtx x, rtx insn)
{
return oprs_unchanged_p (x, insn, 0);
}
static int
oprs_available_p (rtx x, rtx insn)
{
return oprs_unchanged_p (x, insn, 1);
}
static unsigned int
hash_expr (rtx x, enum machine_mode mode, int *do_not_record_p,
int hash_table_size)
{
unsigned int hash;
*do_not_record_p = 0;
hash = hash_rtx (x, mode, do_not_record_p,
NULL, false);
return hash % hash_table_size;
}
static unsigned int
hash_set (int regno, int hash_table_size)
{
unsigned int hash;
hash = regno;
return hash % hash_table_size;
}
static int
expr_equiv_p (rtx x, rtx y)
{
return exp_equiv_p (x, y, 0, true);
}
static void
insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p,
int avail_p, struct hash_table *table)
{
int found, do_not_record_p;
unsigned int hash;
struct expr *cur_expr, *last_expr = NULL;
struct occr *antic_occr, *avail_occr;
hash = hash_expr (x, mode, &do_not_record_p, table->size);
if (do_not_record_p)
return;
cur_expr = table->table[hash];
found = 0;
while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
{
last_expr = cur_expr;
cur_expr = cur_expr->next_same_hash;
}
if (! found)
{
cur_expr = gcse_alloc (sizeof (struct expr));
bytes_used += sizeof (struct expr);
if (table->table[hash] == NULL)
table->table[hash] = cur_expr;
else
last_expr->next_same_hash = cur_expr;
cur_expr->expr = x;
cur_expr->bitmap_index = table->n_elems++;
cur_expr->next_same_hash = NULL;
cur_expr->antic_occr = NULL;
cur_expr->avail_occr = NULL;
}
if (antic_p)
{
antic_occr = cur_expr->antic_occr;
if (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn))
antic_occr = NULL;
if (antic_occr)
;
else
{
antic_occr = gcse_alloc (sizeof (struct occr));
bytes_used += sizeof (struct occr);
antic_occr->insn = insn;
antic_occr->next = cur_expr->antic_occr;
antic_occr->deleted_p = 0;
cur_expr->antic_occr = antic_occr;
}
}
if (avail_p)
{
avail_occr = cur_expr->avail_occr;
if (avail_occr && BLOCK_NUM (avail_occr->insn) == BLOCK_NUM (insn))
{
avail_occr->insn = insn;
}
else
{
avail_occr = gcse_alloc (sizeof (struct occr));
bytes_used += sizeof (struct occr);
avail_occr->insn = insn;
avail_occr->next = cur_expr->avail_occr;
avail_occr->deleted_p = 0;
cur_expr->avail_occr = avail_occr;
}
}
}
static void
insert_set_in_table (rtx x, rtx insn, struct hash_table *table)
{
int found;
unsigned int hash;
struct expr *cur_expr, *last_expr = NULL;
struct occr *cur_occr;
gcc_assert (GET_CODE (x) == SET && REG_P (SET_DEST (x)));
hash = hash_set (REGNO (SET_DEST (x)), table->size);
cur_expr = table->table[hash];
found = 0;
while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
{
last_expr = cur_expr;
cur_expr = cur_expr->next_same_hash;
}
if (! found)
{
cur_expr = gcse_alloc (sizeof (struct expr));
bytes_used += sizeof (struct expr);
if (table->table[hash] == NULL)
table->table[hash] = cur_expr;
else
last_expr->next_same_hash = cur_expr;
cur_expr->expr = copy_rtx (x);
cur_expr->bitmap_index = table->n_elems++;
cur_expr->next_same_hash = NULL;
cur_expr->antic_occr = NULL;
cur_expr->avail_occr = NULL;
}
cur_occr = cur_expr->avail_occr;
if (cur_occr && BLOCK_NUM (cur_occr->insn) == BLOCK_NUM (insn))
{
cur_occr->insn = insn;
}
else
{
cur_occr = gcse_alloc (sizeof (struct occr));
bytes_used += sizeof (struct occr);
cur_occr->insn = insn;
cur_occr->next = cur_expr->avail_occr;
cur_occr->deleted_p = 0;
cur_expr->avail_occr = cur_occr;
}
}
static bool
gcse_constant_p (rtx x)
{
if (GET_CODE (x) == COMPARE
&& GET_CODE (XEXP (x, 0)) == CONST_INT
&& GET_CODE (XEXP (x, 1)) == CONST_INT)
return true;
if (GET_CODE(x) == COMPARE
&& REG_P (XEXP (x, 0)) && REG_P (XEXP (x, 1))
&& REGNO (XEXP (x, 0)) == REGNO (XEXP (x, 1))
&& ! FLOAT_MODE_P (GET_MODE (XEXP (x, 0)))
&& ! FLOAT_MODE_P (GET_MODE (XEXP (x, 1))))
return true;
return CONSTANT_P (x);
}
static void
hash_scan_set (rtx pat, rtx insn, struct hash_table *table)
{
rtx src = SET_SRC (pat);
rtx dest = SET_DEST (pat);
rtx note;
if (GET_CODE (src) == CALL)
hash_scan_call (src, insn, table);
else if (REG_P (dest))
{
unsigned int regno = REGNO (dest);
rtx tmp;
if (table->set_p && (note = find_reg_equal_equiv_note (insn)) != 0
&& gcse_constant_p (XEXP (note, 0)))
src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest, src);
if (! table->set_p
&& regno >= FIRST_PSEUDO_REGISTER
&& can_copy_p (GET_MODE (dest))
&& !find_reg_note (insn, REG_EH_REGION, NULL_RTX)
&& want_to_gcse_p (src)
&& ! set_noop_p (pat)
&& ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0
|| ! MEM_P (XEXP (note, 0))))
{
int antic_p = oprs_anticipatable_p (src, insn) && single_set (insn);
int avail_p = (oprs_available_p (src, insn)
&& ! JUMP_P (insn));
insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p, table);
}
else if (table->set_p
&& regno >= FIRST_PSEUDO_REGISTER
&& ((REG_P (src)
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
&& can_copy_p (GET_MODE (dest))
&& REGNO (src) != regno)
|| gcse_constant_p (src))
&& (insn == BB_END (BLOCK_FOR_INSN (insn))
|| ((tmp = next_nonnote_insn (insn)) != NULL_RTX
&& oprs_available_p (pat, tmp))))
insert_set_in_table (pat, insn, table);
}
else if (flag_gcse_las && REG_P (src) && MEM_P (dest))
{
unsigned int regno = REGNO (src);
if (! table->set_p
&& regno >= FIRST_PSEUDO_REGISTER
&& can_copy_p (GET_MODE (src))
&& ! find_reg_note (insn, REG_EH_REGION, NULL_RTX)
&& want_to_gcse_p (dest)
&& ! set_noop_p (pat)
&& ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0
|| ! MEM_P (XEXP (note, 0))))
{
int antic_p = 0;
int avail_p = oprs_available_p (dest, insn)
&& ! JUMP_P (insn);
insert_expr_in_table (dest, GET_MODE (dest), insn,
antic_p, avail_p, table);
}
}
}
static void
hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
struct hash_table *table ATTRIBUTE_UNUSED)
{
}
static void
hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
struct hash_table *table ATTRIBUTE_UNUSED)
{
}
static void
hash_scan_insn (rtx insn, struct hash_table *table, int in_libcall_block)
{
rtx pat = PATTERN (insn);
int i;
if (in_libcall_block)
return;
if (GET_CODE (pat) == SET)
hash_scan_set (pat, insn, table);
else if (GET_CODE (pat) == PARALLEL)
for (i = 0; i < XVECLEN (pat, 0); i++)
{
rtx x = XVECEXP (pat, 0, i);
if (GET_CODE (x) == SET)
hash_scan_set (x, insn, table);
else if (GET_CODE (x) == CLOBBER)
hash_scan_clobber (x, insn, table);
else if (GET_CODE (x) == CALL)
hash_scan_call (x, insn, table);
}
else if (GET_CODE (pat) == CLOBBER)
hash_scan_clobber (pat, insn, table);
else if (GET_CODE (pat) == CALL)
hash_scan_call (pat, insn, table);
}
static void
dump_hash_table (FILE *file, const char *name, struct hash_table *table)
{
int i;
struct expr **flat_table;
unsigned int *hash_val;
struct expr *expr;
flat_table = xcalloc (table->n_elems, sizeof (struct expr *));
hash_val = xmalloc (table->n_elems * sizeof (unsigned int));
for (i = 0; i < (int) table->size; i++)
for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
{
flat_table[expr->bitmap_index] = expr;
hash_val[expr->bitmap_index] = i;
}
fprintf (file, "%s hash table (%d buckets, %d entries)\n",
name, table->size, table->n_elems);
for (i = 0; i < (int) table->n_elems; i++)
if (flat_table[i] != 0)
{
expr = flat_table[i];
fprintf (file, "Index %d (hash value %d)\n ",
expr->bitmap_index, hash_val[i]);
print_rtl (file, expr->expr);
fprintf (file, "\n");
}
fprintf (file, "\n");
free (flat_table);
free (hash_val);
}
static void
record_last_reg_set_info (rtx insn, int regno)
{
struct reg_avail_info *info = ®_avail_info[regno];
int cuid = INSN_CUID (insn);
info->last_set = cuid;
if (info->last_bb != current_bb)
{
info->last_bb = current_bb;
info->first_set = cuid;
SET_BIT (reg_set_in_block[current_bb->index], regno);
}
}
static void
canon_list_insert (rtx dest ATTRIBUTE_UNUSED, rtx unused1 ATTRIBUTE_UNUSED,
void * v_insn)
{
rtx dest_addr, insn;
int bb;
while (GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT
|| GET_CODE (dest) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
if (! MEM_P (dest))
return;
dest_addr = get_addr (XEXP (dest, 0));
dest_addr = canon_rtx (dest_addr);
insn = (rtx) v_insn;
bb = BLOCK_NUM (insn);
canon_modify_mem_list[bb] =
alloc_EXPR_LIST (VOIDmode, dest_addr, canon_modify_mem_list[bb]);
canon_modify_mem_list[bb] =
alloc_EXPR_LIST (VOIDmode, dest, canon_modify_mem_list[bb]);
}
static void
record_last_mem_set_info (rtx insn)
{
int bb = BLOCK_NUM (insn);
modify_mem_list[bb] = alloc_INSN_LIST (insn, modify_mem_list[bb]);
bitmap_set_bit (modify_mem_list_set, bb);
if (CALL_P (insn))
{
canon_modify_mem_list[bb] =
alloc_INSN_LIST (insn, canon_modify_mem_list[bb]);
bitmap_set_bit (blocks_with_calls, bb);
}
else
note_stores (PATTERN (insn), canon_list_insert, (void*) insn);
}
static void
record_last_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED, void *data)
{
rtx last_set_insn = (rtx) data;
if (GET_CODE (dest) == SUBREG)
dest = SUBREG_REG (dest);
if (REG_P (dest))
record_last_reg_set_info (last_set_insn, REGNO (dest));
else if (MEM_P (dest)
&& ! push_operand (dest, GET_MODE (dest)))
record_last_mem_set_info (last_set_insn);
}
static void
compute_hash_table_work (struct hash_table *table)
{
unsigned int i;
sbitmap_vector_zero (reg_set_in_block, last_basic_block);
clear_modify_mem_tables ();
reg_avail_info = gmalloc (max_gcse_regno * sizeof (struct reg_avail_info));
for (i = 0; i < max_gcse_regno; ++i)
reg_avail_info[i].last_bb = NULL;
FOR_EACH_BB (current_bb)
{
rtx insn;
unsigned int regno;
int in_libcall_block;
for (insn = BB_HEAD (current_bb);
insn && insn != NEXT_INSN (BB_END (current_bb));
insn = NEXT_INSN (insn))
{
if (! INSN_P (insn))
continue;
if (CALL_P (insn))
{
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
record_last_reg_set_info (insn, regno);
mark_call (insn);
}
note_stores (PATTERN (insn), record_last_set_info, insn);
}
if (table->set_p
&& implicit_sets[current_bb->index] != NULL_RTX)
hash_scan_set (implicit_sets[current_bb->index],
BB_HEAD (current_bb), table);
for (insn = BB_HEAD (current_bb), in_libcall_block = 0;
insn && insn != NEXT_INSN (BB_END (current_bb));
insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
in_libcall_block = 1;
else if (table->set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
in_libcall_block = 0;
hash_scan_insn (insn, table, in_libcall_block);
if (!table->set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
in_libcall_block = 0;
}
}
free (reg_avail_info);
reg_avail_info = NULL;
}
static void
alloc_hash_table (int n_insns, struct hash_table *table, int set_p)
{
int n;
table->size = n_insns / 4;
if (table->size < 11)
table->size = 11;
table->size |= 1;
n = table->size * sizeof (struct expr *);
table->table = gmalloc (n);
table->set_p = set_p;
}
static void
free_hash_table (struct hash_table *table)
{
free (table->table);
}
static void
compute_hash_table (struct hash_table *table)
{
table->n_elems = 0;
memset (table->table, 0, table->size * sizeof (struct expr *));
compute_hash_table_work (table);
}
static struct expr *
lookup_set (unsigned int regno, struct hash_table *table)
{
unsigned int hash = hash_set (regno, table->size);
struct expr *expr;
expr = table->table[hash];
while (expr && REGNO (SET_DEST (expr->expr)) != regno)
expr = expr->next_same_hash;
return expr;
}
static struct expr *
next_set (unsigned int regno, struct expr *expr)
{
do
expr = expr->next_same_hash;
while (expr && REGNO (SET_DEST (expr->expr)) != regno);
return expr;
}
static void
free_insn_expr_list_list (rtx *listp)
{
rtx list, next;
for (list = *listp; list ; list = next)
{
next = XEXP (list, 1);
if (GET_CODE (list) == EXPR_LIST)
free_EXPR_LIST_node (list);
else
free_INSN_LIST_node (list);
}
*listp = NULL;
}
static void
clear_modify_mem_tables (void)
{
unsigned i;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi)
{
free_INSN_LIST_list (modify_mem_list + i);
free_insn_expr_list_list (canon_modify_mem_list + i);
}
bitmap_clear (modify_mem_list_set);
bitmap_clear (blocks_with_calls);
}
static void
free_modify_mem_tables (void)
{
clear_modify_mem_tables ();
free (modify_mem_list);
free (canon_modify_mem_list);
modify_mem_list = 0;
canon_modify_mem_list = 0;
}
static void
reset_opr_set_tables (void)
{
CLEAR_REG_SET (reg_set_bitmap);
clear_modify_mem_tables ();
}
static int
oprs_not_set_p (rtx x, rtx insn)
{
int i, j;
enum rtx_code code;
const char *fmt;
if (x == 0)
return 1;
code = GET_CODE (x);
switch (code)
{
case PC:
case CC0:
case CONST:
case CONST_INT:
case CONST_DOUBLE:
case CONST_VECTOR:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
case ADDR_DIFF_VEC:
return 1;
case MEM:
if (load_killed_in_block_p (BLOCK_FOR_INSN (insn),
INSN_CUID (insn), x, 0))
return 0;
else
return oprs_not_set_p (XEXP (x, 0), insn);
case REG:
return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
default:
break;
}
for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
{
if (fmt[i] == 'e')
{
if (i == 0)
return oprs_not_set_p (XEXP (x, i), insn);
if (! oprs_not_set_p (XEXP (x, i), insn))
return 0;
}
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
if (! oprs_not_set_p (XVECEXP (x, i, j), insn))
return 0;
}
return 1;
}
static void
mark_call (rtx insn)
{
if (! CONST_OR_PURE_CALL_P (insn))
record_last_mem_set_info (insn);
}
static void
mark_set (rtx pat, rtx insn)
{
rtx dest = SET_DEST (pat);
while (GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT
|| GET_CODE (dest) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
if (REG_P (dest))
SET_REGNO_REG_SET (reg_set_bitmap, REGNO (dest));
else if (MEM_P (dest))
record_last_mem_set_info (insn);
if (GET_CODE (SET_SRC (pat)) == CALL)
mark_call (insn);
}
static void
mark_clobber (rtx pat, rtx insn)
{
rtx clob = XEXP (pat, 0);
while (GET_CODE (clob) == SUBREG || GET_CODE (clob) == STRICT_LOW_PART)
clob = XEXP (clob, 0);
if (REG_P (clob))
SET_REGNO_REG_SET (reg_set_bitmap, REGNO (clob));
else
record_last_mem_set_info (insn);
}
static void
mark_oprs_set (rtx insn)
{
rtx pat = PATTERN (insn);
int i;
if (GET_CODE (pat) == SET)
mark_set (pat, insn);
else if (GET_CODE (pat) == PARALLEL)
for (i = 0; i < XVECLEN (pat, 0); i++)
{
rtx x = XVECEXP (pat, 0, i);
if (GET_CODE (x) == SET)
mark_set (x, insn);
else if (GET_CODE (x) == CLOBBER)
mark_clobber (x, insn);
else if (GET_CODE (x) == CALL)
mark_call (insn);
}
else if (GET_CODE (pat) == CLOBBER)
mark_clobber (pat, insn);
else if (GET_CODE (pat) == CALL)
mark_call (insn);
}
static sbitmap *cprop_pavloc;
static sbitmap *cprop_absaltered;
static sbitmap *cprop_avin;
static sbitmap *cprop_avout;
static void
alloc_cprop_mem (int n_blocks, int n_sets)
{
cprop_pavloc = sbitmap_vector_alloc (n_blocks, n_sets);
cprop_absaltered = sbitmap_vector_alloc (n_blocks, n_sets);
cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
}
static void
free_cprop_mem (void)
{
sbitmap_vector_free (cprop_pavloc);
sbitmap_vector_free (cprop_absaltered);
sbitmap_vector_free (cprop_avin);
sbitmap_vector_free (cprop_avout);
}
static void
compute_transp (rtx x, int indx, sbitmap *bmap, int set_p)
{
int i, j;
basic_block bb;
enum rtx_code code;
reg_set *r;
const char *fmt;
repeat:
if (x == 0)
return;
code = GET_CODE (x);
switch (code)
{
case REG:
if (set_p)
{
if (REGNO (x) < FIRST_PSEUDO_REGISTER)
{
FOR_EACH_BB (bb)
if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x)))
SET_BIT (bmap[bb->index], indx);
}
else
{
for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
SET_BIT (bmap[r->bb_index], indx);
}
}
else
{
if (REGNO (x) < FIRST_PSEUDO_REGISTER)
{
FOR_EACH_BB (bb)
if (TEST_BIT (reg_set_in_block[bb->index], REGNO (x)))
RESET_BIT (bmap[bb->index], indx);
}
else
{
for (r = reg_set_table[REGNO (x)]; r != NULL; r = r->next)
RESET_BIT (bmap[r->bb_index], indx);
}
}
return;
case MEM:
{
bitmap_iterator bi;
unsigned bb_index;
EXECUTE_IF_SET_IN_BITMAP (blocks_with_calls, 0, bb_index, bi)
{
if (set_p)
SET_BIT (bmap[bb_index], indx);
else
RESET_BIT (bmap[bb_index], indx);
}
EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set, blocks_with_calls,
0, bb_index, bi)
{
rtx list_entry = canon_modify_mem_list[bb_index];
while (list_entry)
{
rtx dest, dest_addr;
dest = XEXP (list_entry, 0);
list_entry = XEXP (list_entry, 1);
dest_addr = XEXP (list_entry, 0);
if (canon_true_dependence (dest, GET_MODE (dest), dest_addr,
x, rtx_addr_varies_p))
{
if (set_p)
SET_BIT (bmap[bb_index], indx);
else
RESET_BIT (bmap[bb_index], indx);
break;
}
list_entry = XEXP (list_entry, 1);
}
}
}
x = XEXP (x, 0);
goto repeat;
case PC:
case CC0:
case CONST:
case CONST_INT:
case CONST_DOUBLE:
case CONST_VECTOR:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
case ADDR_DIFF_VEC:
return;
default:
break;
}
for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
{
if (fmt[i] == 'e')
{
if (i == 0)
{
x = XEXP (x, i);
goto repeat;
}
compute_transp (XEXP (x, i), indx, bmap, set_p);
}
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
compute_transp (XVECEXP (x, i, j), indx, bmap, set_p);
}
}
static void
compute_cprop_data (void)
{
compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, &set_hash_table);
compute_available (cprop_pavloc, cprop_absaltered,
cprop_avout, cprop_avin);
}
#define MAX_USES 8
static struct reg_use reg_use_table[MAX_USES];
static int reg_use_count;
static void
find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED)
{
int i, j;
enum rtx_code code;
const char *fmt;
rtx x = *xptr;
repeat:
if (x == 0)
return;
code = GET_CODE (x);
if (REG_P (x))
{
if (reg_use_count == MAX_USES)
return;
reg_use_table[reg_use_count].reg_rtx = x;
reg_use_count++;
}
for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
{
if (fmt[i] == 'e')
{
if (i == 0)
{
x = XEXP (x, 0);
goto repeat;
}
find_used_regs (&XEXP (x, i), data);
}
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
find_used_regs (&XVECEXP (x, i, j), data);
}
}
static int
try_replace_reg (rtx from, rtx to, rtx insn)
{
rtx note = find_reg_equal_equiv_note (insn);
rtx src = 0;
int success = 0;
rtx set = single_set (insn);
validate_replace_src_group (from, to, insn);
if (num_changes_pending () && apply_change_group ())
success = 1;
if (success && set && CONSTANT_P (to))
{
src = simplify_rtx (SET_SRC (set));
if (src)
validate_change (insn, &SET_SRC (set), src, 0);
}
if (note != 0)
XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), from, to);
if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
{
src = simplify_replace_rtx (SET_SRC (set), from, to);
if (!rtx_equal_p (src, SET_SRC (set))
&& validate_change (insn, &SET_SRC (set), src, 0))
success = 1;
if (!success && note == 0 && set != 0
&& GET_CODE (SET_DEST (set)) != ZERO_EXTRACT)
note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
}
if (note && REG_P (XEXP (note, 0)))
remove_note (insn, note);
return success;
}
static struct expr *
find_avail_set (int regno, rtx insn)
{
struct expr *set1 = 0;
while (1)
{
rtx src;
struct expr *set = lookup_set (regno, &set_hash_table);
while (set)
{
if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index))
break;
set = next_set (regno, set);
}
if (set == 0)
break;
gcc_assert (GET_CODE (set->expr) == SET);
src = SET_SRC (set->expr);
if (gcse_constant_p (src) || oprs_not_set_p (src, insn))
set1 = set;
if (! REG_P (src))
break;
regno = REGNO (src);
}
return set1;
}
static int
cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src)
{
rtx new, set_src, note_src;
rtx set = pc_set (jump);
rtx note = find_reg_equal_equiv_note (jump);
if (note)
{
note_src = XEXP (note, 0);
if (GET_CODE (note_src) == EXPR_LIST)
note_src = NULL_RTX;
}
else note_src = NULL_RTX;
set_src = note_src ? note_src : SET_SRC (set);
if (setcc != NULL_RTX
&& !modified_between_p (from, setcc, jump)
&& !modified_between_p (src, setcc, jump))
{
rtx setcc_src;
rtx setcc_set = single_set (setcc);
rtx setcc_note = find_reg_equal_equiv_note (setcc);
setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST)
? XEXP (setcc_note, 0) : SET_SRC (setcc_set);
set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set),
setcc_src);
}
else
setcc = NULL_RTX;
new = simplify_replace_rtx (set_src, from, src);
if (rtx_equal_p (new, SET_SRC (set)))
return 0;
if (new == pc_rtx)
delete_insn (jump);
else
{
if (setcc && modified_in_p (new, setcc))
return 0;
if (! validate_change (jump, &SET_SRC (set), new, 0))
{
if (!rtx_equal_p (new, note_src))
set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new));
return 0;
}
if (note_src)
remove_note (jump, note);
if (GET_CODE (SET_SRC (set)) == LABEL_REF)
emit_barrier_after (jump);
}
#ifdef HAVE_cc0
if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
delete_insn (setcc);
#endif
run_jump_opt_after_gcse = 1;
global_const_prop_count++;
if (gcse_file != NULL)
{
fprintf (gcse_file,
"GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with constant ",
REGNO (from), INSN_UID (jump));
print_rtl (gcse_file, src);
fprintf (gcse_file, "\n");
}
purge_dead_edges (bb);
return 1;
}
static bool
constprop_register (rtx insn, rtx from, rtx to, int alter_jumps)
{
rtx sset;
if (alter_jumps
&& (sset = single_set (insn)) != NULL
&& NEXT_INSN (insn)
&& any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
{
rtx dest = SET_DEST (sset);
if ((REG_P (dest) || CC0_P (dest))
&& cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to))
return 1;
}
if (NONJUMP_INSN_P (insn)
&& try_replace_reg (from, to, insn))
return 1;
else if (alter_jumps && any_condjump_p (insn) && onlyjump_p (insn))
return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
return 0;
}
static int
cprop_insn (rtx insn, int alter_jumps)
{
struct reg_use *reg_used;
int changed = 0;
rtx note;
if (!INSN_P (insn))
return 0;
reg_use_count = 0;
note_uses (&PATTERN (insn), find_used_regs, NULL);
note = find_reg_equal_equiv_note (insn);
if (note)
find_used_regs (&XEXP (note, 0), NULL);
for (reg_used = ®_use_table[0]; reg_use_count > 0;
reg_used++, reg_use_count--)
{
unsigned int regno = REGNO (reg_used->reg_rtx);
rtx pat, src;
struct expr *set;
if (regno >= max_gcse_regno)
continue;
if (! oprs_not_set_p (reg_used->reg_rtx, insn))
continue;
set = find_avail_set (regno, insn);
if (! set)
continue;
pat = set->expr;
gcc_assert (GET_CODE (pat) == SET);
src = SET_SRC (pat);
if (gcse_constant_p (src))
{
if (constprop_register (insn, reg_used->reg_rtx, src, alter_jumps))
{
changed = 1;
global_const_prop_count++;
if (gcse_file != NULL)
{
fprintf (gcse_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
fprintf (gcse_file, "insn %d with constant ", INSN_UID (insn));
print_rtl (gcse_file, src);
fprintf (gcse_file, "\n");
}
if (INSN_DELETED_P (insn))
return 1;
}
if ( GET_CODE (insn) == INSN
&& GET_CODE (PATTERN (insn)) == SET
&& ( GET_CODE (XEXP (PATTERN (insn), 1)) == DIV
|| GET_CODE (XEXP (PATTERN (insn), 1)) == UDIV)
&& GET_MODE (XEXP (PATTERN (insn), 1)) == SImode
&& GET_CODE (XEXP (XEXP (PATTERN (insn), 1), 1)) == CONST_INT )
{
rtx seq, result, target;
target = XEXP (PATTERN (insn), 0);
start_sequence ();
result = expand_divmod (0, TRUNC_DIV_EXPR, SImode,
XEXP (XEXP (PATTERN (insn), 1), 0),
XEXP (XEXP (PATTERN (insn), 1), 1),
target,
GET_CODE (XEXP (PATTERN (insn), 1))==DIV ? 0 : 1);
if ( result != target )
emit_move_insn (target, result);
seq = get_insns ();
end_sequence ();
emit_insn_after (seq, insn);
PUT_CODE (insn, NOTE);
NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
NOTE_SOURCE_FILE (insn) = 0;
update_bb_for_insn (BLOCK_FOR_INSN (insn));
changed = 1;
break;
}
else if ( GET_CODE (insn) == INSN
&& GET_CODE (PATTERN (insn)) == SET
&& (note = find_reg_equal_equiv_note (insn))
&& (GET_CODE (XEXP (note, 0)) == DIV
|| GET_CODE (XEXP (note, 0)) == UDIV)
&& GET_MODE (XEXP (note, 0)) == SImode
&& GET_CODE (XEXP (XEXP (note, 0), 1)) == CONST_INT )
{
rtx seq, result, target;
target = XEXP (PATTERN (insn), 0);
start_sequence ();
result = expand_divmod (0, TRUNC_DIV_EXPR, SImode,
XEXP (XEXP (note, 0), 0),
XEXP (XEXP (note, 0), 1),
target,
GET_CODE (XEXP (note, 0))==DIV ? 0 : 1);
if ( result != target )
emit_move_insn (target, result);
seq = get_insns ();
end_sequence ();
emit_insn_after (seq, insn);
PUT_CODE (insn, NOTE);
NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
NOTE_SOURCE_FILE (insn) = 0;
update_bb_for_insn (BLOCK_FOR_INSN (insn));
changed = 1;
break;
}
}
else if (REG_P (src)
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
&& REGNO (src) != regno)
{
if (try_replace_reg (reg_used->reg_rtx, src, insn))
{
changed = 1;
global_copy_prop_count++;
if (gcse_file != NULL)
{
fprintf (gcse_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
regno, INSN_UID (insn));
fprintf (gcse_file, " with reg %d\n", REGNO (src));
}
}
}
}
return changed;
}
static void
local_cprop_find_used_regs (rtx *xptr, void *data)
{
rtx x = *xptr;
if (x == 0)
return;
switch (GET_CODE (x))
{
case ZERO_EXTRACT:
case SIGN_EXTRACT:
case STRICT_LOW_PART:
return;
case PRE_DEC:
case PRE_INC:
case POST_DEC:
case POST_INC:
case PRE_MODIFY:
case POST_MODIFY:
return;
case SUBREG:
if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) > BITS_PER_WORD)
return;
break;
default:
break;
}
find_used_regs (xptr, data);
}
static bool
do_local_cprop (rtx x, rtx insn, int alter_jumps, rtx *libcall_sp)
{
rtx newreg = NULL, newcnst = NULL;
if (REG_P (x)
&& (REGNO (x) >= FIRST_PSEUDO_REGISTER
|| (GET_CODE (PATTERN (insn)) != USE
&& asm_noperands (PATTERN (insn)) < 0)))
{
cselib_val *val = cselib_lookup (x, GET_MODE (x), 0);
struct elt_loc_list *l;
if (!val)
return false;
for (l = val->locs; l; l = l->next)
{
rtx this_rtx = l->loc;
rtx note;
if (l->in_libcall && ! CONSTANT_P (this_rtx))
continue;
if (gcse_constant_p (this_rtx))
newcnst = this_rtx;
if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
&& (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
|| ! MEM_P (XEXP (note, 0))))
newreg = this_rtx;
}
if (newcnst && constprop_register (insn, x, newcnst, alter_jumps))
{
bool adjusted;
adjusted = adjust_libcall_notes (x, newcnst, insn, libcall_sp);
gcc_assert (adjusted);
if (gcse_file != NULL)
{
fprintf (gcse_file, "LOCAL CONST-PROP: Replacing reg %d in ",
REGNO (x));
fprintf (gcse_file, "insn %d with constant ",
INSN_UID (insn));
print_rtl (gcse_file, newcnst);
fprintf (gcse_file, "\n");
}
local_const_prop_count++;
return true;
}
else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
{
adjust_libcall_notes (x, newreg, insn, libcall_sp);
if (gcse_file != NULL)
{
fprintf (gcse_file,
"LOCAL COPY-PROP: Replacing reg %d in insn %d",
REGNO (x), INSN_UID (insn));
fprintf (gcse_file, " with reg %d\n", REGNO (newreg));
}
local_copy_prop_count++;
return true;
}
}
return false;
}
static bool
adjust_libcall_notes (rtx oldreg, rtx newval, rtx insn, rtx *libcall_sp)
{
rtx end;
while ((end = *libcall_sp++))
{
rtx note = find_reg_equal_equiv_note (end);
if (! note)
continue;
if (REG_P (newval))
{
if (reg_set_between_p (newval, PREV_INSN (insn), end))
{
do
{
note = find_reg_equal_equiv_note (end);
if (! note)
continue;
if (reg_mentioned_p (newval, XEXP (note, 0)))
return false;
}
while ((end = *libcall_sp++));
return true;
}
}
XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), oldreg, newval);
insn = end;
}
return true;
}
#define MAX_NESTED_LIBCALLS 9
static void
local_cprop_pass (int alter_jumps)
{
rtx insn;
struct reg_use *reg_used;
rtx libcall_stack[MAX_NESTED_LIBCALLS + 1], *libcall_sp;
bool changed = false;
cselib_init (false);
libcall_sp = &libcall_stack[MAX_NESTED_LIBCALLS];
*libcall_sp = 0;
for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
{
rtx note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
if (note)
{
gcc_assert (libcall_sp != libcall_stack);
*--libcall_sp = XEXP (note, 0);
}
note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
if (note)
libcall_sp++;
note = find_reg_equal_equiv_note (insn);
do
{
reg_use_count = 0;
note_uses (&PATTERN (insn), local_cprop_find_used_regs, NULL);
if (note)
local_cprop_find_used_regs (&XEXP (note, 0), NULL);
for (reg_used = ®_use_table[0]; reg_use_count > 0;
reg_used++, reg_use_count--)
if (do_local_cprop (reg_used->reg_rtx, insn, alter_jumps,
libcall_sp))
{
changed = true;
break;
}
if (INSN_DELETED_P (insn))
break;
}
while (reg_use_count);
}
cselib_process_insn (insn);
}
cselib_finish ();
if (changed && alter_jumps)
{
delete_unreachable_blocks ();
free_reg_set_mem ();
alloc_reg_set_mem (max_reg_num ());
compute_sets (get_insns ());
}
}
static int
cprop (int alter_jumps)
{
int changed;
basic_block bb;
rtx insn;
if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
{
if (gcse_file != NULL)
fprintf (gcse_file, "\n");
return 0;
}
changed = 0;
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
{
reset_opr_set_tables ();
for (insn = BB_HEAD (bb);
insn != NULL && insn != NEXT_INSN (BB_END (bb));
insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
changed |= cprop_insn (insn, alter_jumps);
if (! NOTE_P (insn))
mark_oprs_set (insn);
}
}
if (gcse_file != NULL)
fprintf (gcse_file, "\n");
return changed;
}
rtx
fis_get_condition (rtx jump)
{
return get_condition (jump, NULL, false, true);
}
static bool
implicit_set_cond_p (rtx cond)
{
enum machine_mode mode = GET_MODE (XEXP (cond, 0));
rtx cst = XEXP (cond, 1);
if (HONOR_SIGNED_ZEROS (mode))
{
if (GET_CODE (cst) == CONST_DOUBLE)
{
REAL_VALUE_TYPE d;
REAL_VALUE_FROM_CONST_DOUBLE (d, cst);
if (REAL_VALUES_EQUAL (d, dconst0))
return 0;
}
else
return 0;
}
return gcse_constant_p (cst);
}
static void
find_implicit_sets (void)
{
basic_block bb, dest;
unsigned int count;
rtx cond, new;
count = 0;
FOR_EACH_BB (bb)
if (EDGE_COUNT (bb->succs) > 1)
{
cond = fis_get_condition (BB_END (bb));
if (cond
&& (GET_CODE (cond) == EQ || GET_CODE (cond) == NE)
&& REG_P (XEXP (cond, 0))
&& REGNO (XEXP (cond, 0)) >= FIRST_PSEUDO_REGISTER
&& implicit_set_cond_p (cond))
{
dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest
: FALLTHRU_EDGE (bb)->dest;
if (dest && EDGE_COUNT (dest->preds) == 1
&& dest != EXIT_BLOCK_PTR)
{
new = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
XEXP (cond, 1));
implicit_sets[dest->index] = new;
if (gcse_file)
{
fprintf(gcse_file, "Implicit set of reg %d in ",
REGNO (XEXP (cond, 0)));
fprintf(gcse_file, "basic block %d\n", dest->index);
}
count++;
}
}
}
if (gcse_file)
fprintf (gcse_file, "Found %d implicit sets\n", count);
}
static int
one_cprop_pass (int pass, int cprop_jumps, int bypass_jumps)
{
int changed = 0;
global_const_prop_count = local_const_prop_count = 0;
global_copy_prop_count = local_copy_prop_count = 0;
local_cprop_pass (cprop_jumps);
implicit_sets = xcalloc (last_basic_block, sizeof (rtx));
find_implicit_sets ();
alloc_hash_table (max_cuid, &set_hash_table, 1);
compute_hash_table (&set_hash_table);
free (implicit_sets);
implicit_sets = NULL;
if (gcse_file)
dump_hash_table (gcse_file, "SET", &set_hash_table);
if (set_hash_table.n_elems > 0)
{
alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
compute_cprop_data ();
changed = cprop (cprop_jumps);
if (bypass_jumps)
changed |= bypass_conditional_jumps ();
free_cprop_mem ();
}
free_hash_table (&set_hash_table);
if (gcse_file)
{
fprintf (gcse_file, "CPROP of %s, pass %d: %d bytes needed, ",
current_function_name (), pass, bytes_used);
fprintf (gcse_file, "%d local const props, %d local copy props\n\n",
local_const_prop_count, local_copy_prop_count);
fprintf (gcse_file, "%d global const props, %d global copy props\n\n",
global_const_prop_count, global_copy_prop_count);
}
if (changed && cprop_jumps)
delete_unreachable_blocks ();
return changed;
}
static int bypass_last_basic_block;
static struct expr *
find_bypass_set (int regno, int bb)
{
struct expr *result = 0;
for (;;)
{
rtx src;
struct expr *set = lookup_set (regno, &set_hash_table);
while (set)
{
if (TEST_BIT (cprop_avout[bb], set->bitmap_index))
break;
set = next_set (regno, set);
}
if (set == 0)
break;
gcc_assert (GET_CODE (set->expr) == SET);
src = SET_SRC (set->expr);
if (gcse_constant_p (src))
result = set;
if (! REG_P (src))
break;
regno = REGNO (src);
}
return result;
}
static bool
reg_killed_on_edge (rtx reg, edge e)
{
rtx insn;
for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
if (INSN_P (insn) && reg_set_p (reg, insn))
return true;
return false;
}
static int
bypass_block (basic_block bb, rtx setcc, rtx jump)
{
rtx insn, note;
edge e, edest;
int i, change;
int may_be_loop_header;
unsigned removed_p;
edge_iterator ei;
insn = (setcc != NULL) ? setcc : jump;
reg_use_count = 0;
note_uses (&PATTERN (insn), find_used_regs, NULL);
note = find_reg_equal_equiv_note (insn);
if (note)
find_used_regs (&XEXP (note, 0), NULL);
may_be_loop_header = false;
FOR_EACH_EDGE (e, ei, bb->preds)
if (e->flags & EDGE_DFS_BACK)
{
may_be_loop_header = true;
break;
}
change = 0;
for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
{
removed_p = 0;
if (e->flags & EDGE_COMPLEX)
{
ei_next (&ei);
continue;
}
if (e->src->index >= bypass_last_basic_block)
{
ei_next (&ei);
continue;
}
if (may_be_loop_header
&& !(e->flags & EDGE_DFS_BACK))
{
ei_next (&ei);
continue;
}
for (i = 0; i < reg_use_count; i++)
{
struct reg_use *reg_used = ®_use_table[i];
unsigned int regno = REGNO (reg_used->reg_rtx);
basic_block dest, old_dest;
struct expr *set;
rtx src, new;
if (regno >= max_gcse_regno)
continue;
set = find_bypass_set (regno, e->src->index);
if (! set)
continue;
if (e->insns.r && reg_killed_on_edge (reg_used->reg_rtx, e))
continue;
src = SET_SRC (pc_set (jump));
if (setcc != NULL)
src = simplify_replace_rtx (src,
SET_DEST (PATTERN (setcc)),
SET_SRC (PATTERN (setcc)));
new = simplify_replace_rtx (src, reg_used->reg_rtx,
SET_SRC (set->expr));
if (new == pc_rtx)
{
edest = FALLTHRU_EDGE (bb);
dest = edest->insns.r ? NULL : edest->dest;
}
else if (GET_CODE (new) == LABEL_REF)
{
edge_iterator ei2;
dest = BLOCK_FOR_INSN (XEXP (new, 0));
FOR_EACH_EDGE (edest, ei2, bb->succs)
if (edest->dest == dest && edest->insns.r)
{
dest = NULL;
break;
}
}
else
dest = NULL;
if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc))))
{
edge e2;
edge_iterator ei2;
FOR_EACH_EDGE (e2, ei2, e->src->succs)
if (e2->dest == dest)
{
dest = NULL;
break;
}
}
old_dest = e->dest;
if (dest != NULL
&& dest != old_dest
&& dest != EXIT_BLOCK_PTR)
{
redirect_edge_and_branch_force (e, dest);
if (setcc)
{
rtx pat = PATTERN (setcc);
if (!CC0_P (SET_DEST (pat)))
insert_insn_on_edge (copy_insn (pat), e);
}
if (gcse_file != NULL)
{
fprintf (gcse_file, "JUMP-BYPASS: Proved reg %d "
"in jump_insn %d equals constant ",
regno, INSN_UID (jump));
print_rtl (gcse_file, SET_SRC (set->expr));
fprintf (gcse_file, "\nBypass edge from %d->%d to %d\n",
e->src->index, old_dest->index, dest->index);
}
change = 1;
removed_p = 1;
break;
}
}
if (!removed_p)
ei_next (&ei);
}
return change;
}
static int
bypass_conditional_jumps (void)
{
basic_block bb;
int changed;
rtx setcc;
rtx insn;
rtx dest;
if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
return 0;
bypass_last_basic_block = last_basic_block;
mark_dfs_back_edges ();
changed = 0;
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb,
EXIT_BLOCK_PTR, next_bb)
{
if (EDGE_COUNT (bb->preds) > 1)
{
setcc = NULL_RTX;
for (insn = BB_HEAD (bb);
insn != NULL && insn != NEXT_INSN (BB_END (bb));
insn = NEXT_INSN (insn))
if (NONJUMP_INSN_P (insn))
{
if (setcc)
break;
if (GET_CODE (PATTERN (insn)) != SET)
break;
dest = SET_DEST (PATTERN (insn));
if (REG_P (dest) || CC0_P (dest))
setcc = insn;
else
break;
}
else if (JUMP_P (insn))
{
if ((any_condjump_p (insn) || computed_jump_p (insn))
&& onlyjump_p (insn))
changed |= bypass_block (bb, setcc, insn);
break;
}
else if (INSN_P (insn))
break;
}
}
if (changed)
commit_edge_insertions();
return changed;
}
static sbitmap *transp;
static sbitmap *transpout;
static sbitmap *comp;
static sbitmap *antloc;
static sbitmap *pre_optimal;
static sbitmap *pre_redundant;
static sbitmap *pre_insert_map;
static sbitmap *pre_delete_map;
static struct edge_list *edge_list;
static sbitmap pre_redundant_insns;
static void
alloc_pre_mem (int n_blocks, int n_exprs)
{
transp = sbitmap_vector_alloc (n_blocks, n_exprs);
comp = sbitmap_vector_alloc (n_blocks, n_exprs);
antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
pre_optimal = NULL;
pre_redundant = NULL;
pre_insert_map = NULL;
pre_delete_map = NULL;
ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs);
}
static void
free_pre_mem (void)
{
sbitmap_vector_free (transp);
sbitmap_vector_free (comp);
if (pre_optimal)
sbitmap_vector_free (pre_optimal);
if (pre_redundant)
sbitmap_vector_free (pre_redundant);
if (pre_insert_map)
sbitmap_vector_free (pre_insert_map);
if (pre_delete_map)
sbitmap_vector_free (pre_delete_map);
transp = comp = NULL;
pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL;
}
static void
compute_pre_data (void)
{
sbitmap trapping_expr;
basic_block bb;
unsigned int ui;
compute_local_properties (transp, comp, antloc, &expr_hash_table);
sbitmap_vector_zero (ae_kill, last_basic_block);
trapping_expr = sbitmap_alloc (expr_hash_table.n_elems);
sbitmap_zero (trapping_expr);
for (ui = 0; ui < expr_hash_table.size; ui++)
{
struct expr *e;
for (e = expr_hash_table.table[ui]; e != NULL; e = e->next_same_hash)
if (may_trap_p (e->expr))
SET_BIT (trapping_expr, e->bitmap_index);
}
FOR_EACH_BB (bb)
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->preds)
if (e->flags & EDGE_ABNORMAL)
{
sbitmap_difference (antloc[bb->index], antloc[bb->index], trapping_expr);
sbitmap_difference (transp[bb->index], transp[bb->index], trapping_expr);
break;
}
sbitmap_a_or_b (ae_kill[bb->index], transp[bb->index], comp[bb->index]);
sbitmap_not (ae_kill[bb->index], ae_kill[bb->index]);
}
edge_list = pre_edge_lcm (gcse_file, expr_hash_table.n_elems, transp, comp, antloc,
ae_kill, &pre_insert_map, &pre_delete_map);
sbitmap_vector_free (antloc);
antloc = NULL;
sbitmap_vector_free (ae_kill);
ae_kill = NULL;
sbitmap_free (trapping_expr);
}
static int
pre_expr_reaches_here_p_work (basic_block occr_bb, struct expr *expr, basic_block bb, char *visited)
{
edge pred;
edge_iterator ei;
FOR_EACH_EDGE (pred, ei, bb->preds)
{
basic_block pred_bb = pred->src;
if (pred->src == ENTRY_BLOCK_PTR
|| visited[pred_bb->index])
;
else if (TEST_BIT (comp[pred_bb->index], expr->bitmap_index))
{
if (occr_bb == pred_bb)
return 1;
visited[pred_bb->index] = 1;
}
else if (! TEST_BIT (transp[pred_bb->index], expr->bitmap_index))
visited[pred_bb->index] = 1;
else
{
visited[pred_bb->index] = 1;
if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited))
return 1;
}
}
return 0;
}
static int
pre_expr_reaches_here_p (basic_block occr_bb, struct expr *expr, basic_block bb)
{
int rval;
char *visited = xcalloc (last_basic_block, 1);
rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited);
free (visited);
return rval;
}
static rtx
process_insert_insn (struct expr *expr)
{
rtx reg = expr->reaching_reg;
rtx exp = copy_rtx (expr->expr);
rtx pat;
start_sequence ();
if (general_operand (exp, GET_MODE (reg)))
emit_move_insn (reg, exp);
else
{
rtx insn = emit_insn (gen_rtx_SET (VOIDmode, reg, exp));
if (insn_invalid_p (insn))
gcc_unreachable ();
}
pat = get_insns ();
end_sequence ();
return pat;
}
static void
insert_insn_end_bb (struct expr *expr, basic_block bb, int pre)
{
rtx insn = BB_END (bb);
rtx new_insn;
rtx reg = expr->reaching_reg;
int regno = REGNO (reg);
rtx pat, pat_end;
pat = process_insert_insn (expr);
gcc_assert (pat && INSN_P (pat));
pat_end = pat;
while (NEXT_INSN (pat_end) != NULL_RTX)
pat_end = NEXT_INSN (pat_end);
if (JUMP_P (insn)
|| (NONJUMP_INSN_P (insn)
&& (EDGE_COUNT (bb->succs) > 1
|| EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL)))
{
#ifdef HAVE_cc0
rtx note;
#endif
gcc_assert (!NONJUMP_INSN_P (insn) || !pre
|| TEST_BIT (antloc[bb->index], expr->bitmap_index)
|| TEST_BIT (transp[bb->index], expr->bitmap_index));
if (GET_CODE (PATTERN (insn)) == ADDR_VEC
|| GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
insn = prev_real_insn (insn);
#ifdef HAVE_cc0
note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
if (note)
insn = XEXP (note, 0);
else
{
rtx maybe_cc0_setter = prev_nonnote_insn (insn);
if (maybe_cc0_setter
&& INSN_P (maybe_cc0_setter)
&& sets_cc0_p (PATTERN (maybe_cc0_setter)))
insn = maybe_cc0_setter;
}
#endif
new_insn = emit_insn_before_noloc (pat, insn);
}
else if (CALL_P (insn)
&& (EDGE_COUNT (bb->succs) > 1 || EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL))
{
gcc_assert (!pre
|| TEST_BIT (antloc[bb->index], expr->bitmap_index)
|| TEST_BIT (transp[bb->index], expr->bitmap_index));
insn = find_first_parameter_load (insn, BB_HEAD (bb));
while (LABEL_P (insn)
|| NOTE_INSN_BASIC_BLOCK_P (insn))
insn = NEXT_INSN (insn);
new_insn = emit_insn_before_noloc (pat, insn);
}
else
new_insn = emit_insn_after_noloc (pat, insn);
while (1)
{
if (INSN_P (pat))
{
add_label_notes (PATTERN (pat), new_insn);
note_stores (PATTERN (pat), record_set_info, pat);
}
if (pat == pat_end)
break;
pat = NEXT_INSN (pat);
}
gcse_create_count++;
if (gcse_file)
{
fprintf (gcse_file, "PRE/HOIST: end of bb %d, insn %d, ",
bb->index, INSN_UID (new_insn));
fprintf (gcse_file, "copying expression %d to reg %d\n",
expr->bitmap_index, regno);
}
}
static int
pre_edge_insert (struct edge_list *edge_list, struct expr **index_map)
{
int e, i, j, num_edges, set_size, did_insert = 0;
sbitmap *inserted;
set_size = pre_insert_map[0]->size;
num_edges = NUM_EDGES (edge_list);
inserted = sbitmap_vector_alloc (num_edges, expr_hash_table.n_elems);
sbitmap_vector_zero (inserted, num_edges);
for (e = 0; e < num_edges; e++)
{
int indx;
basic_block bb = INDEX_EDGE_PRED_BB (edge_list, e);
for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
{
SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i];
for (j = indx; insert && j < (int) expr_hash_table.n_elems; j++, insert >>= 1)
if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX)
{
struct expr *expr = index_map[j];
struct occr *occr;
for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
{
if (! occr->deleted_p)
continue;
if (!TEST_BIT (inserted[e], j))
{
rtx insn;
edge eg = INDEX_EDGE (edge_list, e);
if (eg->flags & EDGE_ABNORMAL)
insert_insn_end_bb (index_map[j], bb, 0);
else
{
insn = process_insert_insn (index_map[j]);
insert_insn_on_edge (insn, eg);
}
if (gcse_file)
{
fprintf (gcse_file, "PRE/HOIST: edge (%d,%d), ",
bb->index,
INDEX_EDGE_SUCC_BB (edge_list, e)->index);
fprintf (gcse_file, "copy expression %d\n",
expr->bitmap_index);
}
update_ld_motion_stores (expr);
SET_BIT (inserted[e], j);
did_insert = 1;
gcse_create_count++;
}
}
}
}
}
sbitmap_vector_free (inserted);
return did_insert;
}
static void
pre_insert_copy_insn (struct expr *expr, rtx insn)
{
rtx reg = expr->reaching_reg;
int regno = REGNO (reg);
int indx = expr->bitmap_index;
rtx pat = PATTERN (insn);
rtx set, new_insn;
rtx old_reg;
int i;
switch (GET_CODE (pat))
{
case SET:
set = pat;
break;
case PARALLEL:
set = NULL_RTX;
for (i = 0; i < XVECLEN (pat, 0); i++)
{
rtx x = XVECEXP (pat, 0, i);
if (GET_CODE (x) == SET
&& expr_equiv_p (SET_SRC (x), expr->expr))
{
set = x;
break;
}
}
break;
default:
gcc_unreachable ();
}
if (REG_P (SET_DEST (set)))
{
old_reg = SET_DEST (set);
if (validate_change (insn, &SET_DEST (set), reg, 0))
{
new_insn = gen_move_insn (old_reg, reg);
new_insn = emit_insn_after (new_insn, insn);
record_one_set (regno, insn);
}
else
{
new_insn = gen_move_insn (reg, old_reg);
new_insn = emit_insn_after (new_insn, insn);
record_one_set (regno, new_insn);
}
}
else
{
old_reg = SET_SRC (set);
new_insn = gen_move_insn (reg, old_reg);
if (validate_change (insn, &SET_SRC (set), reg, 0))
new_insn = emit_insn_before (new_insn, insn);
else
new_insn = emit_insn_after (new_insn, insn);
record_one_set (regno, new_insn);
}
gcse_create_count++;
if (gcse_file)
fprintf (gcse_file,
"PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
BLOCK_NUM (insn), INSN_UID (new_insn), indx,
INSN_UID (insn), regno);
}
static void
pre_insert_copies (void)
{
unsigned int i, added_copy;
struct expr *expr;
struct occr *occr;
struct occr *avail;
for (i = 0; i < expr_hash_table.size; i++)
for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
{
if (expr->reaching_reg == NULL)
continue;
added_copy = 0;
for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
{
if (! occr->deleted_p)
continue;
for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
{
rtx insn = avail->insn;
if (avail->copied_p)
continue;
if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn)))
continue;
if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn),
expr,
BLOCK_FOR_INSN (occr->insn)))
continue;
added_copy = 1;
pre_insert_copy_insn (expr, insn);
avail->copied_p = 1;
}
}
if (added_copy)
update_ld_motion_stores (expr);
}
}
static rtx
gcse_emit_move_after (rtx src, rtx dest, rtx insn)
{
rtx new;
rtx set = single_set (insn), set2;
rtx note;
rtx eqv;
new = emit_insn_after (gen_move_insn (dest, src), insn);
set2 = single_set (new);
if (!set2 || !rtx_equal_p (SET_DEST (set2), dest))
return new;
if ((note = find_reg_equal_equiv_note (insn)))
eqv = XEXP (note, 0);
else
eqv = SET_SRC (set);
set_unique_reg_note (new, REG_EQUAL, copy_insn_1 (eqv));
return new;
}
static int
pre_delete (void)
{
unsigned int i;
int changed;
struct expr *expr;
struct occr *occr;
changed = 0;
for (i = 0; i < expr_hash_table.size; i++)
for (expr = expr_hash_table.table[i];
expr != NULL;
expr = expr->next_same_hash)
{
int indx = expr->bitmap_index;
for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
{
rtx insn = occr->insn;
rtx set;
basic_block bb = BLOCK_FOR_INSN (insn);
if (TEST_BIT (pre_delete_map[bb->index], indx)
&& (set = single_set (insn)) != 0)
{
if (expr->reaching_reg == NULL)
expr->reaching_reg
= gen_reg_rtx (GET_MODE (SET_DEST (set)));
gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
delete_insn (insn);
occr->deleted_p = 1;
SET_BIT (pre_redundant_insns, INSN_CUID (insn));
changed = 1;
gcse_subst_count++;
if (gcse_file)
{
fprintf (gcse_file,
"PRE: redundant insn %d (expression %d) in ",
INSN_UID (insn), indx);
fprintf (gcse_file, "bb %d, reaching reg is %d\n",
bb->index, REGNO (expr->reaching_reg));
}
}
}
}
return changed;
}
static int
pre_gcse (void)
{
unsigned int i;
int did_insert, changed;
struct expr **index_map;
struct expr *expr;
index_map = xcalloc (expr_hash_table.n_elems, sizeof (struct expr *));
for (i = 0; i < expr_hash_table.size; i++)
for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
index_map[expr->bitmap_index] = expr;
pre_redundant_insns = sbitmap_alloc (max_cuid);
sbitmap_zero (pre_redundant_insns);
changed = pre_delete ();
did_insert = pre_edge_insert (edge_list, index_map);
pre_insert_copies ();
if (did_insert)
{
commit_edge_insertions ();
changed = 1;
}
free (index_map);
sbitmap_free (pre_redundant_insns);
return changed;
}
static int
one_pre_gcse_pass (int pass)
{
int changed = 0;
gcse_subst_count = 0;
gcse_create_count = 0;
alloc_hash_table (max_cuid, &expr_hash_table, 0);
add_noreturn_fake_exit_edges ();
if (flag_gcse_lm)
compute_ld_motion_mems ();
compute_hash_table (&expr_hash_table);
trim_ld_motion_mems ();
if (gcse_file)
dump_hash_table (gcse_file, "Expression", &expr_hash_table);
if (expr_hash_table.n_elems > 0)
{
alloc_pre_mem (last_basic_block, expr_hash_table.n_elems);
compute_pre_data ();
changed |= pre_gcse ();
free_edge_list (edge_list);
free_pre_mem ();
}
free_ldst_mems ();
remove_fake_exit_edges ();
free_hash_table (&expr_hash_table);
if (gcse_file)
{
fprintf (gcse_file, "\nPRE GCSE of %s, pass %d: %d bytes needed, ",
current_function_name (), pass, bytes_used);
fprintf (gcse_file, "%d substs, %d insns created\n",
gcse_subst_count, gcse_create_count);
}
return changed;
}
static void
add_label_notes (rtx x, rtx insn)
{
enum rtx_code code = GET_CODE (x);
int i, j;
const char *fmt;
if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
{
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))++;
return;
}
for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
{
if (fmt[i] == 'e')
add_label_notes (XEXP (x, i), insn);
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
add_label_notes (XVECEXP (x, i, j), insn);
}
}
static void
compute_transpout (void)
{
basic_block bb;
unsigned int i;
struct expr *expr;
sbitmap_vector_ones (transpout, last_basic_block);
FOR_EACH_BB (bb)
{
if (! CALL_P (BB_END (bb)))
continue;
for (i = 0; i < expr_hash_table.size; i++)
for (expr = expr_hash_table.table[i]; expr ; expr = expr->next_same_hash)
if (MEM_P (expr->expr))
{
if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF
&& CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0)))
continue;
RESET_BIT (transpout[bb->index], expr->bitmap_index);
}
}
}
static sbitmap *hoist_vbein;
static sbitmap *hoist_vbeout;
static sbitmap *hoist_exprs;
static void
alloc_code_hoist_mem (int n_blocks, int n_exprs)
{
antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
transp = sbitmap_vector_alloc (n_blocks, n_exprs);
comp = sbitmap_vector_alloc (n_blocks, n_exprs);
hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs);
hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs);
transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
}
static void
free_code_hoist_mem (void)
{
sbitmap_vector_free (antloc);
sbitmap_vector_free (transp);
sbitmap_vector_free (comp);
sbitmap_vector_free (hoist_vbein);
sbitmap_vector_free (hoist_vbeout);
sbitmap_vector_free (hoist_exprs);
sbitmap_vector_free (transpout);
free_dominance_info (CDI_DOMINATORS);
}
static void
compute_code_hoist_vbeinout (void)
{
int changed, passes;
basic_block bb;
sbitmap_vector_zero (hoist_vbeout, last_basic_block);
sbitmap_vector_zero (hoist_vbein, last_basic_block);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
FOR_EACH_BB_REVERSE (bb)
{
changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index], antloc[bb->index],
hoist_vbeout[bb->index], transp[bb->index]);
if (bb->next_bb != EXIT_BLOCK_PTR)
sbitmap_intersection_of_succs (hoist_vbeout[bb->index], hoist_vbein, bb->index);
}
passes++;
}
if (gcse_file)
fprintf (gcse_file, "hoisting vbeinout computation: %d passes\n", passes);
}
static void
compute_code_hoist_data (void)
{
compute_local_properties (transp, comp, antloc, &expr_hash_table);
compute_transpout ();
compute_code_hoist_vbeinout ();
calculate_dominance_info (CDI_DOMINATORS);
if (gcse_file)
fprintf (gcse_file, "\n");
}
static int
hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb, char *visited)
{
edge pred;
edge_iterator ei;
int visited_allocated_locally = 0;
if (visited == NULL)
{
visited_allocated_locally = 1;
visited = xcalloc (last_basic_block, 1);
}
FOR_EACH_EDGE (pred, ei, bb->preds)
{
basic_block pred_bb = pred->src;
if (pred->src == ENTRY_BLOCK_PTR)
break;
else if (pred_bb == expr_bb)
continue;
else if (visited[pred_bb->index])
continue;
else if (TEST_BIT (comp[pred_bb->index], expr_index))
break;
else if (! TEST_BIT (transp[pred_bb->index], expr_index))
break;
else
{
visited[pred_bb->index] = 1;
if (! hoist_expr_reaches_here_p (expr_bb, expr_index,
pred_bb, visited))
break;
}
}
if (visited_allocated_locally)
free (visited);
return (pred == NULL);
}
static void
hoist_code (void)
{
basic_block bb, dominated;
basic_block *domby;
unsigned int domby_len;
unsigned int i,j;
struct expr **index_map;
struct expr *expr;
sbitmap_vector_zero (hoist_exprs, last_basic_block);
index_map = xcalloc (expr_hash_table.n_elems, sizeof (struct expr *));
for (i = 0; i < expr_hash_table.size; i++)
for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
index_map[expr->bitmap_index] = expr;
FOR_EACH_BB (bb)
{
int found = 0;
int insn_inserted_p;
domby_len = get_dominated_by (CDI_DOMINATORS, bb, &domby);
for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++)
{
int hoistable = 0;
if (TEST_BIT (hoist_vbeout[bb->index], i)
&& TEST_BIT (transpout[bb->index], i))
{
for (j = 0; j < domby_len; j++)
{
dominated = domby[j];
if (bb == dominated)
continue;
if (!TEST_BIT (antloc[dominated->index], i))
continue;
if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
hoistable++;
}
if (hoistable > 1)
{
SET_BIT (hoist_exprs[bb->index], i);
found = 1;
}
}
}
if (! found)
{
free (domby);
continue;
}
for (i = 0; i < hoist_exprs[bb->index]->n_bits; i++)
{
insn_inserted_p = 0;
if (TEST_BIT (hoist_vbeout[bb->index], i))
{
for (j = 0; j < domby_len; j++)
{
dominated = domby[j];
if (bb == dominated)
continue;
if (!TEST_BIT (antloc[dominated->index], i))
continue;
if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
{
struct expr *expr = index_map[i];
struct occr *occr = expr->antic_occr;
rtx insn;
rtx set;
while (BLOCK_FOR_INSN (occr->insn) != dominated && occr)
occr = occr->next;
gcc_assert (occr);
insn = occr->insn;
set = single_set (insn);
gcc_assert (set);
if (expr->reaching_reg == NULL)
expr->reaching_reg
= gen_reg_rtx (GET_MODE (SET_DEST (set)));
gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
delete_insn (insn);
occr->deleted_p = 1;
if (!insn_inserted_p)
{
insert_insn_end_bb (index_map[i], bb, 0);
insn_inserted_p = 1;
}
}
}
}
}
free (domby);
}
free (index_map);
}
static int
one_code_hoisting_pass (void)
{
int changed = 0;
alloc_hash_table (max_cuid, &expr_hash_table, 0);
compute_hash_table (&expr_hash_table);
if (gcse_file)
dump_hash_table (gcse_file, "Code Hosting Expressions", &expr_hash_table);
if (expr_hash_table.n_elems > 0)
{
alloc_code_hoist_mem (last_basic_block, expr_hash_table.n_elems);
compute_code_hoist_data ();
hoist_code ();
free_code_hoist_mem ();
}
free_hash_table (&expr_hash_table);
return changed;
}
static struct ls_expr *
ldst_entry (rtx x)
{
int do_not_record_p = 0;
struct ls_expr * ptr;
unsigned int hash;
hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
NULL, false);
for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
if (ptr->hash_index == hash && expr_equiv_p (ptr->pattern, x))
return ptr;
ptr = xmalloc (sizeof (struct ls_expr));
ptr->next = pre_ldst_mems;
ptr->expr = NULL;
ptr->pattern = x;
ptr->pattern_regs = NULL_RTX;
ptr->loads = NULL_RTX;
ptr->stores = NULL_RTX;
ptr->reaching_reg = NULL_RTX;
ptr->invalid = 0;
ptr->index = 0;
ptr->hash_index = hash;
pre_ldst_mems = ptr;
return ptr;
}
static void
free_ldst_entry (struct ls_expr * ptr)
{
free_INSN_LIST_list (& ptr->loads);
free_INSN_LIST_list (& ptr->stores);
free (ptr);
}
static void
free_ldst_mems (void)
{
while (pre_ldst_mems)
{
struct ls_expr * tmp = pre_ldst_mems;
pre_ldst_mems = pre_ldst_mems->next;
free_ldst_entry (tmp);
}
pre_ldst_mems = NULL;
}
static void
print_ldst_list (FILE * file)
{
struct ls_expr * ptr;
fprintf (file, "LDST list: \n");
for (ptr = first_ls_expr(); ptr != NULL; ptr = next_ls_expr (ptr))
{
fprintf (file, " Pattern (%3d): ", ptr->index);
print_rtl (file, ptr->pattern);
fprintf (file, "\n Loads : ");
if (ptr->loads)
print_rtl (file, ptr->loads);
else
fprintf (file, "(nil)");
fprintf (file, "\n Stores : ");
if (ptr->stores)
print_rtl (file, ptr->stores);
else
fprintf (file, "(nil)");
fprintf (file, "\n\n");
}
fprintf (file, "\n");
}
static struct ls_expr *
find_rtx_in_ldst (rtx x)
{
struct ls_expr * ptr;
for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
if (expr_equiv_p (ptr->pattern, x) && ! ptr->invalid)
return ptr;
return NULL;
}
static int
enumerate_ldsts (void)
{
struct ls_expr * ptr;
int n = 0;
for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
ptr->index = n++;
return n;
}
static inline struct ls_expr *
first_ls_expr (void)
{
return pre_ldst_mems;
}
static inline struct ls_expr *
next_ls_expr (struct ls_expr * ptr)
{
return ptr->next;
}
static int
simple_mem (rtx x)
{
if (! MEM_P (x))
return 0;
if (MEM_VOLATILE_P (x))
return 0;
if (GET_MODE (x) == BLKmode)
return 0;
if (flag_non_call_exceptions && may_trap_p (x))
return 0;
if (side_effects_p (x))
return 0;
if (reg_mentioned_p (stack_pointer_rtx, x))
return 0;
if (flag_float_store && FLOAT_MODE_P (GET_MODE (x)))
return 0;
return 1;
}
static void
invalidate_any_buried_refs (rtx x)
{
const char * fmt;
int i, j;
struct ls_expr * ptr;
if (MEM_P (x) && simple_mem (x))
{
ptr = ldst_entry (x);
ptr->invalid = 1;
}
fmt = GET_RTX_FORMAT (GET_CODE (x));
for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
invalidate_any_buried_refs (XEXP (x, i));
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
invalidate_any_buried_refs (XVECEXP (x, i, j));
}
}
static void
compute_ld_motion_mems (void)
{
struct ls_expr * ptr;
basic_block bb;
rtx insn;
pre_ldst_mems = NULL;
FOR_EACH_BB (bb)
{
for (insn = BB_HEAD (bb);
insn && insn != NEXT_INSN (BB_END (bb));
insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
{
if (GET_CODE (PATTERN (insn)) == SET)
{
rtx src = SET_SRC (PATTERN (insn));
rtx dest = SET_DEST (PATTERN (insn));
if (MEM_P (src) && simple_mem (src))
{
ptr = ldst_entry (src);
if (REG_P (dest))
ptr->loads = alloc_INSN_LIST (insn, ptr->loads);
else
ptr->invalid = 1;
}
else
{
invalidate_any_buried_refs (src);
}
if (MEM_P (dest) && simple_mem (dest))
{
ptr = ldst_entry (dest);
if (! MEM_P (src)
&& GET_CODE (src) != ASM_OPERANDS
&& can_assign_to_reg_p (src))
ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
else
ptr->invalid = 1;
}
}
else
invalidate_any_buried_refs (PATTERN (insn));
}
}
}
}
static void
trim_ld_motion_mems (void)
{
struct ls_expr * * last = & pre_ldst_mems;
struct ls_expr * ptr = pre_ldst_mems;
while (ptr != NULL)
{
struct expr * expr;
if (! ptr->invalid)
{
unsigned int hash = ptr->hash_index % expr_hash_table.size;
for (expr = expr_hash_table.table[hash];
expr != NULL;
expr = expr->next_same_hash)
if (expr_equiv_p (expr->expr, ptr->pattern))
break;
}
else
expr = (struct expr *) 0;
if (expr)
{
ptr->expr = expr;
last = & ptr->next;
ptr = ptr->next;
}
else
{
*last = ptr->next;
free_ldst_entry (ptr);
ptr = * last;
}
}
if (gcse_file && pre_ldst_mems != NULL)
print_ldst_list (gcse_file);
}
static void
update_ld_motion_stores (struct expr * expr)
{
struct ls_expr * mem_ptr;
if ((mem_ptr = find_rtx_in_ldst (expr->expr)))
{
rtx list = mem_ptr->stores;
for ( ; list != NULL_RTX; list = XEXP (list, 1))
{
rtx insn = XEXP (list, 0);
rtx pat = PATTERN (insn);
rtx src = SET_SRC (pat);
rtx reg = expr->reaching_reg;
rtx copy, new;
if (expr->reaching_reg == src)
continue;
if (gcse_file)
{
fprintf (gcse_file, "PRE: store updated with reaching reg ");
print_rtl (gcse_file, expr->reaching_reg);
fprintf (gcse_file, ":\n ");
print_inline_rtx (gcse_file, insn, 8);
fprintf (gcse_file, "\n");
}
copy = gen_move_insn ( reg, copy_rtx (SET_SRC (pat)));
new = emit_insn_before (copy, insn);
record_one_set (REGNO (reg), new);
SET_SRC (pat) = reg;
INSN_CODE (insn) = -1;
gcse_create_count++;
}
}
}
#define ANTIC_STORE_LIST(x) ((x)->loads)
#define AVAIL_STORE_LIST(x) ((x)->stores)
#define LAST_AVAIL_CHECK_FAILURE(x) ((x)->reaching_reg)
static int * regvec;
static rtx compute_store_table_current_insn;
static sbitmap * st_antloc;
static int num_stores;
static void
reg_set_info (rtx dest, rtx setter ATTRIBUTE_UNUSED,
void *data)
{
sbitmap bb_reg = data;
if (GET_CODE (dest) == SUBREG)
dest = SUBREG_REG (dest);
if (REG_P (dest))
{
regvec[REGNO (dest)] = INSN_UID (compute_store_table_current_insn);
if (bb_reg)
SET_BIT (bb_reg, REGNO (dest));
}
}
static void
reg_clear_last_set (rtx dest, rtx setter ATTRIBUTE_UNUSED,
void *data)
{
int *dead_vec = data;
if (GET_CODE (dest) == SUBREG)
dest = SUBREG_REG (dest);
if (REG_P (dest) &&
dead_vec[REGNO (dest)] == INSN_UID (compute_store_table_current_insn))
dead_vec[REGNO (dest)] = 0;
}
static bool
store_ops_ok (rtx x, int *regs_set)
{
rtx reg;
for (; x; x = XEXP (x, 1))
{
reg = XEXP (x, 0);
if (regs_set[REGNO(reg)])
return false;
}
return true;
}
static rtx
extract_mentioned_regs (rtx x)
{
return extract_mentioned_regs_helper (x, NULL_RTX);
}
static rtx
extract_mentioned_regs_helper (rtx x, rtx accum)
{
int i;
enum rtx_code code;
const char * fmt;
repeat:
if (x == 0)
return accum;
code = GET_CODE (x);
switch (code)
{
case REG:
return alloc_EXPR_LIST (0, x, accum);
case MEM:
x = XEXP (x, 0);
goto repeat;
case PRE_DEC:
case PRE_INC:
case POST_DEC:
case POST_INC:
gcc_unreachable ();
case PC:
case CC0:
case CONST:
case CONST_INT:
case CONST_DOUBLE:
case CONST_VECTOR:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
case ADDR_DIFF_VEC:
return accum;
default:
break;
}
i = GET_RTX_LENGTH (code) - 1;
fmt = GET_RTX_FORMAT (code);
for (; i >= 0; i--)
{
if (fmt[i] == 'e')
{
rtx tem = XEXP (x, i);
if (i == 0)
{
x = tem;
goto repeat;
}
accum = extract_mentioned_regs_helper (tem, accum);
}
else if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
accum = extract_mentioned_regs_helper (XVECEXP (x, i, j), accum);
}
}
return accum;
}
static void
find_moveable_store (rtx insn, int *regs_set_before, int *regs_set_after)
{
struct ls_expr * ptr;
rtx dest, set, tmp;
int check_anticipatable, check_available;
basic_block bb = BLOCK_FOR_INSN (insn);
set = single_set (insn);
if (!set)
return;
dest = SET_DEST (set);
if (! MEM_P (dest) || MEM_VOLATILE_P (dest)
|| GET_MODE (dest) == BLKmode)
return;
if (side_effects_p (dest))
return;
if (flag_non_call_exceptions && may_trap_p (dest))
return;
if (find_reg_note (insn, REG_EH_REGION, NULL_RTX))
return;
ptr = ldst_entry (dest);
if (!ptr->pattern_regs)
ptr->pattern_regs = extract_mentioned_regs (dest);
check_anticipatable = 0;
if (!ANTIC_STORE_LIST (ptr))
check_anticipatable = 1;
else
{
tmp = XEXP (ANTIC_STORE_LIST (ptr), 0);
if (tmp != NULL_RTX
&& BLOCK_FOR_INSN (tmp) != bb)
check_anticipatable = 1;
}
if (check_anticipatable)
{
if (store_killed_before (dest, ptr->pattern_regs, insn, bb, regs_set_before))
tmp = NULL_RTX;
else
tmp = insn;
ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (tmp,
ANTIC_STORE_LIST (ptr));
}
check_available = 0;
if (!AVAIL_STORE_LIST (ptr))
check_available = 1;
else
{
tmp = XEXP (AVAIL_STORE_LIST (ptr), 0);
if (BLOCK_FOR_INSN (tmp) != bb)
check_available = 1;
}
if (check_available)
{
if (LAST_AVAIL_CHECK_FAILURE (ptr))
{
for (tmp = BB_END (bb);
tmp != insn && tmp != LAST_AVAIL_CHECK_FAILURE (ptr);
tmp = PREV_INSN (tmp))
continue;
if (tmp == insn)
check_available = 0;
}
else
check_available = store_killed_after (dest, ptr->pattern_regs, insn,
bb, regs_set_after,
&LAST_AVAIL_CHECK_FAILURE (ptr));
}
if (!check_available)
AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn, AVAIL_STORE_LIST (ptr));
}
static int
compute_store_table (void)
{
int ret;
basic_block bb;
unsigned regno;
rtx insn, pat, tmp;
int *last_set_in, *already_set;
struct ls_expr * ptr, **prev_next_ptr_ptr;
max_gcse_regno = max_reg_num ();
reg_set_in_block = sbitmap_vector_alloc (last_basic_block,
max_gcse_regno);
sbitmap_vector_zero (reg_set_in_block, last_basic_block);
pre_ldst_mems = 0;
last_set_in = xcalloc (max_gcse_regno, sizeof (int));
already_set = xmalloc (sizeof (int) * max_gcse_regno);
FOR_EACH_BB (bb)
{
regvec = last_set_in;
for (insn = BB_HEAD (bb);
insn != NEXT_INSN (BB_END (bb));
insn = NEXT_INSN (insn))
{
if (! INSN_P (insn))
continue;
if (CALL_P (insn))
{
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
{
last_set_in[regno] = INSN_UID (insn);
SET_BIT (reg_set_in_block[bb->index], regno);
}
}
pat = PATTERN (insn);
compute_store_table_current_insn = insn;
note_stores (pat, reg_set_info, reg_set_in_block[bb->index]);
}
memset (already_set, 0, sizeof (int) * max_gcse_regno);
regvec = already_set;
for (insn = BB_HEAD (bb);
insn != NEXT_INSN (BB_END (bb));
insn = NEXT_INSN (insn))
{
if (! INSN_P (insn))
continue;
if (CALL_P (insn))
{
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
already_set[regno] = 1;
}
pat = PATTERN (insn);
note_stores (pat, reg_set_info, NULL);
find_moveable_store (insn, already_set, last_set_in);
compute_store_table_current_insn = insn;
note_stores (pat, reg_clear_last_set, last_set_in);
if (CALL_P (insn))
{
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)
&& last_set_in[regno] == INSN_UID (insn))
last_set_in[regno] = 0;
}
}
#ifdef ENABLE_CHECKING
for (regno = 0; regno < max_gcse_regno; regno++)
gcc_assert (!last_set_in[regno]);
#endif
for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
{
LAST_AVAIL_CHECK_FAILURE(ptr) = NULL_RTX;
if (ANTIC_STORE_LIST (ptr)
&& (tmp = XEXP (ANTIC_STORE_LIST (ptr), 0)) == NULL_RTX)
ANTIC_STORE_LIST (ptr) = XEXP (ANTIC_STORE_LIST (ptr), 1);
}
}
for (ptr = pre_ldst_mems, prev_next_ptr_ptr = &pre_ldst_mems;
ptr != NULL;
ptr = *prev_next_ptr_ptr)
{
if (!AVAIL_STORE_LIST (ptr))
{
*prev_next_ptr_ptr = ptr->next;
free_ldst_entry (ptr);
}
else
prev_next_ptr_ptr = &ptr->next;
}
ret = enumerate_ldsts ();
if (gcse_file)
{
fprintf (gcse_file, "ST_avail and ST_antic (shown under loads..)\n");
print_ldst_list (gcse_file);
}
free (last_set_in);
free (already_set);
return ret;
}
static bool
load_kills_store (rtx x, rtx store_pattern, int after)
{
if (after)
return anti_dependence (x, store_pattern);
else
return true_dependence (store_pattern, GET_MODE (store_pattern), x,
rtx_addr_varies_p);
}
static bool
find_loads (rtx x, rtx store_pattern, int after)
{
const char * fmt;
int i, j;
int ret = false;
if (!x)
return false;
if (GET_CODE (x) == SET)
x = SET_SRC (x);
if (MEM_P (x))
{
if (load_kills_store (x, store_pattern, after))
return true;
}
fmt = GET_RTX_FORMAT (GET_CODE (x));
for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0 && !ret; i--)
{
if (fmt[i] == 'e')
ret |= find_loads (XEXP (x, i), store_pattern, after);
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
ret |= find_loads (XVECEXP (x, i, j), store_pattern, after);
}
return ret;
}
static bool
store_killed_in_insn (rtx x, rtx x_regs, rtx insn, int after)
{
rtx reg, base, note;
if (!INSN_P (insn))
return false;
if (CALL_P (insn))
{
if (! CONST_OR_PURE_CALL_P (insn) || pure_call_p (insn))
return true;
for (reg = x_regs; reg; reg = XEXP (reg, 1))
{
base = find_base_term (XEXP (reg, 0));
if (!base
|| (GET_CODE (base) == ADDRESS
&& GET_MODE (base) == Pmode
&& XEXP (base, 0) == stack_pointer_rtx))
return true;
}
return false;
}
if (GET_CODE (PATTERN (insn)) == SET)
{
rtx pat = PATTERN (insn);
rtx dest = SET_DEST (pat);
if (GET_CODE (dest) == ZERO_EXTRACT)
dest = XEXP (dest, 0);
if (MEM_P (dest)
&& !expr_equiv_p (dest, x))
{
if (after)
{
if (output_dependence (dest, x))
return true;
}
else
{
if (output_dependence (x, dest))
return true;
}
}
if (find_loads (SET_SRC (pat), x, after))
return true;
}
else if (find_loads (PATTERN (insn), x, after))
return true;
note = find_reg_equal_equiv_note (insn);
if (! note)
return false;
note = XEXP (note, 0);
if (expr_equiv_p (note, x))
return false;
return find_loads (note, x, after);
}
static bool
store_killed_after (rtx x, rtx x_regs, rtx insn, basic_block bb,
int *regs_set_after, rtx *fail_insn)
{
rtx last = BB_END (bb), act;
if (!store_ops_ok (x_regs, regs_set_after))
{
if (fail_insn)
*fail_insn = NULL_RTX;
return true;
}
for (act = last; act != PREV_INSN (insn); act = PREV_INSN (act))
if (store_killed_in_insn (x, x_regs, act, false))
{
if (fail_insn)
*fail_insn = act;
return true;
}
return false;
}
static bool
store_killed_before (rtx x, rtx x_regs, rtx insn, basic_block bb,
int *regs_set_before)
{
rtx first = BB_HEAD (bb);
if (!store_ops_ok (x_regs, regs_set_before))
return true;
for ( ; insn != PREV_INSN (first); insn = PREV_INSN (insn))
if (store_killed_in_insn (x, x_regs, insn, true))
return true;
return false;
}
static void
build_store_vectors (void)
{
basic_block bb;
int *regs_set_in_block;
rtx insn, st;
struct ls_expr * ptr;
unsigned regno;
ae_gen = sbitmap_vector_alloc (last_basic_block, num_stores);
sbitmap_vector_zero (ae_gen, last_basic_block);
st_antloc = sbitmap_vector_alloc (last_basic_block, num_stores);
sbitmap_vector_zero (st_antloc, last_basic_block);
for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
{
for (st = AVAIL_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
{
insn = XEXP (st, 0);
bb = BLOCK_FOR_INSN (insn);
if (TEST_BIT (ae_gen[bb->index], ptr->index))
{
rtx r = gen_reg_rtx (GET_MODE (ptr->pattern));
if (gcse_file)
fprintf (gcse_file, "Removing redundant store:\n");
replace_store_insn (r, XEXP (st, 0), bb, ptr);
continue;
}
SET_BIT (ae_gen[bb->index], ptr->index);
}
for (st = ANTIC_STORE_LIST (ptr); st != NULL; st = XEXP (st, 1))
{
insn = XEXP (st, 0);
bb = BLOCK_FOR_INSN (insn);
SET_BIT (st_antloc[bb->index], ptr->index);
}
}
ae_kill = sbitmap_vector_alloc (last_basic_block, num_stores);
sbitmap_vector_zero (ae_kill, last_basic_block);
transp = sbitmap_vector_alloc (last_basic_block, num_stores);
sbitmap_vector_zero (transp, last_basic_block);
regs_set_in_block = xmalloc (sizeof (int) * max_gcse_regno);
FOR_EACH_BB (bb)
{
for (regno = 0; regno < max_gcse_regno; regno++)
regs_set_in_block[regno] = TEST_BIT (reg_set_in_block[bb->index], regno);
for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
{
if (store_killed_after (ptr->pattern, ptr->pattern_regs, BB_HEAD (bb),
bb, regs_set_in_block, NULL))
{
if (!TEST_BIT (st_antloc[bb->index], ptr->index)
|| !TEST_BIT (ae_gen[bb->index], ptr->index))
SET_BIT (ae_kill[bb->index], ptr->index);
}
else
SET_BIT (transp[bb->index], ptr->index);
}
}
free (regs_set_in_block);
if (gcse_file)
{
dump_sbitmap_vector (gcse_file, "st_antloc", "", st_antloc, last_basic_block);
dump_sbitmap_vector (gcse_file, "st_kill", "", ae_kill, last_basic_block);
dump_sbitmap_vector (gcse_file, "Transpt", "", transp, last_basic_block);
dump_sbitmap_vector (gcse_file, "st_avloc", "", ae_gen, last_basic_block);
}
}
static void
insert_insn_start_bb (rtx insn, basic_block bb)
{
rtx prev = PREV_INSN (BB_HEAD (bb));
rtx before = BB_HEAD (bb);
while (before != 0)
{
if (! LABEL_P (before)
&& (! NOTE_P (before)
|| NOTE_LINE_NUMBER (before) != NOTE_INSN_BASIC_BLOCK))
break;
prev = before;
if (prev == BB_END (bb))
break;
before = NEXT_INSN (before);
}
insn = emit_insn_after_noloc (insn, prev);
if (gcse_file)
{
fprintf (gcse_file, "STORE_MOTION insert store at start of BB %d:\n",
bb->index);
print_inline_rtx (gcse_file, insn, 6);
fprintf (gcse_file, "\n");
}
}
static int
insert_store (struct ls_expr * expr, edge e)
{
rtx reg, insn;
basic_block bb;
edge tmp;
edge_iterator ei;
if (expr->reaching_reg == NULL_RTX)
return 0;
if (e->flags & EDGE_FAKE)
return 0;
reg = expr->reaching_reg;
insn = gen_move_insn (copy_rtx (expr->pattern), reg);
bb = e->dest;
FOR_EACH_EDGE (tmp, ei, e->dest->preds)
if (!(tmp->flags & EDGE_FAKE))
{
int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
gcc_assert (index != EDGE_INDEX_NO_EDGE);
if (! TEST_BIT (pre_insert_map[index], expr->index))
break;
}
if (!tmp && bb != EXIT_BLOCK_PTR)
{
FOR_EACH_EDGE (tmp, ei, e->dest->preds)
{
int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
RESET_BIT (pre_insert_map[index], expr->index);
}
insert_insn_start_bb (insn, bb);
return 0;
}
gcc_assert (!(e->flags & EDGE_ABNORMAL));
insert_insn_on_edge (insn, e);
if (gcse_file)
{
fprintf (gcse_file, "STORE_MOTION insert insn on edge (%d, %d):\n",
e->src->index, e->dest->index);
print_inline_rtx (gcse_file, insn, 6);
fprintf (gcse_file, "\n");
}
return 1;
}
static void
remove_reachable_equiv_notes (basic_block bb, struct ls_expr *smexpr)
{
edge_iterator *stack, ei;
int sp;
edge act;
sbitmap visited = sbitmap_alloc (last_basic_block);
rtx last, insn, note;
rtx mem = smexpr->pattern;
stack = xmalloc (sizeof (edge_iterator) * n_basic_blocks);
sp = 0;
ei = ei_start (bb->succs);
sbitmap_zero (visited);
act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
while (1)
{
if (!act)
{
if (!sp)
{
free (stack);
sbitmap_free (visited);
return;
}
act = ei_edge (stack[--sp]);
}
bb = act->dest;
if (bb == EXIT_BLOCK_PTR
|| TEST_BIT (visited, bb->index))
{
if (!ei_end_p (ei))
ei_next (&ei);
act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
continue;
}
SET_BIT (visited, bb->index);
if (TEST_BIT (st_antloc[bb->index], smexpr->index))
{
for (last = ANTIC_STORE_LIST (smexpr);
BLOCK_FOR_INSN (XEXP (last, 0)) != bb;
last = XEXP (last, 1))
continue;
last = XEXP (last, 0);
}
else
last = NEXT_INSN (BB_END (bb));
for (insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
note = find_reg_equal_equiv_note (insn);
if (!note || !expr_equiv_p (XEXP (note, 0), mem))
continue;
if (gcse_file)
fprintf (gcse_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
INSN_UID (insn));
remove_note (insn, note);
}
if (!ei_end_p (ei))
ei_next (&ei);
act = (! ei_end_p (ei)) ? ei_edge (ei) : NULL;
if (EDGE_COUNT (bb->succs) > 0)
{
if (act)
stack[sp++] = ei;
ei = ei_start (bb->succs);
act = (EDGE_COUNT (ei_container (ei)) > 0 ? EDGE_I (ei_container (ei), 0) : NULL);
}
}
}
static void
replace_store_insn (rtx reg, rtx del, basic_block bb, struct ls_expr *smexpr)
{
rtx insn, mem, note, set, ptr, pair;
mem = smexpr->pattern;
insn = gen_move_insn (reg, SET_SRC (single_set (del)));
insn = emit_insn_after (insn, del);
if (gcse_file)
{
fprintf (gcse_file,
"STORE_MOTION delete insn in BB %d:\n ", bb->index);
print_inline_rtx (gcse_file, del, 6);
fprintf (gcse_file, "\nSTORE MOTION replaced with insn:\n ");
print_inline_rtx (gcse_file, insn, 6);
fprintf (gcse_file, "\n");
}
for (ptr = ANTIC_STORE_LIST (smexpr); ptr; ptr = XEXP (ptr, 1))
if (XEXP (ptr, 0) == del)
{
XEXP (ptr, 0) = insn;
break;
}
REG_NOTES (insn) = REG_NOTES (del);
note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
if (note)
{
pair = XEXP (note, 0);
note = find_reg_note (pair, REG_LIBCALL, NULL_RTX);
XEXP (note, 0) = insn;
}
note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
if (note)
{
pair = XEXP (note, 0);
note = find_reg_note (pair, REG_RETVAL, NULL_RTX);
XEXP (note, 0) = insn;
}
delete_insn (del);
for (; insn != NEXT_INSN (BB_END (bb)); insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
set = single_set (insn);
if (!set)
continue;
if (expr_equiv_p (SET_DEST (set), mem))
return;
note = find_reg_equal_equiv_note (insn);
if (!note || !expr_equiv_p (XEXP (note, 0), mem))
continue;
if (gcse_file)
fprintf (gcse_file, "STORE_MOTION drop REG_EQUAL note at insn %d:\n",
INSN_UID (insn));
remove_note (insn, note);
}
remove_reachable_equiv_notes (bb, smexpr);
}
static void
delete_store (struct ls_expr * expr, basic_block bb)
{
rtx reg, i, del;
if (expr->reaching_reg == NULL_RTX)
expr->reaching_reg = gen_reg_rtx (GET_MODE (expr->pattern));
reg = expr->reaching_reg;
for (i = AVAIL_STORE_LIST (expr); i; i = XEXP (i, 1))
{
del = XEXP (i, 0);
if (BLOCK_FOR_INSN (del) == bb)
{
replace_store_insn (reg, del, bb, expr);
break;
}
}
}
static void
free_store_memory (void)
{
free_ldst_mems ();
if (ae_gen)
sbitmap_vector_free (ae_gen);
if (ae_kill)
sbitmap_vector_free (ae_kill);
if (transp)
sbitmap_vector_free (transp);
if (st_antloc)
sbitmap_vector_free (st_antloc);
if (pre_insert_map)
sbitmap_vector_free (pre_insert_map);
if (pre_delete_map)
sbitmap_vector_free (pre_delete_map);
if (reg_set_in_block)
sbitmap_vector_free (reg_set_in_block);
ae_gen = ae_kill = transp = st_antloc = NULL;
pre_insert_map = pre_delete_map = reg_set_in_block = NULL;
}
static void
store_motion (void)
{
basic_block bb;
int x;
struct ls_expr * ptr;
int update_flow = 0;
if (gcse_file)
{
fprintf (gcse_file, "before store motion\n");
print_rtl (gcse_file, get_insns ());
}
init_alias_analysis ();
num_stores = compute_store_table ();
if (num_stores == 0)
{
sbitmap_vector_free (reg_set_in_block);
end_alias_analysis ();
return;
}
build_store_vectors ();
add_noreturn_fake_exit_edges ();
connect_infinite_loops_to_exit ();
edge_list = pre_edge_rev_lcm (gcse_file, num_stores, transp, ae_gen,
st_antloc, ae_kill, &pre_insert_map,
&pre_delete_map);
for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
{
for (x = NUM_EDGES (edge_list) - 1; x >= 0; x--)
if (TEST_BIT (pre_insert_map[x], ptr->index)
&& (INDEX_EDGE (edge_list, x)->flags & EDGE_ABNORMAL))
break;
if (x >= 0)
{
if (gcse_file != NULL)
fprintf (gcse_file,
"Can't replace store %d: abnormal edge from %d to %d\n",
ptr->index, INDEX_EDGE (edge_list, x)->src->index,
INDEX_EDGE (edge_list, x)->dest->index);
continue;
}
FOR_EACH_BB (bb)
if (TEST_BIT (pre_delete_map[bb->index], ptr->index))
delete_store (ptr, bb);
for (x = 0; x < NUM_EDGES (edge_list); x++)
if (TEST_BIT (pre_insert_map[x], ptr->index))
update_flow |= insert_store (ptr, INDEX_EDGE (edge_list, x));
}
if (update_flow)
commit_edge_insertions ();
free_store_memory ();
free_edge_list (edge_list);
remove_fake_exit_edges ();
end_alias_analysis ();
}
int
bypass_jumps (FILE *file)
{
int changed;
if (current_function_calls_setjmp)
return 0;
debug_stderr = stderr;
gcse_file = file;
max_gcse_regno = max_reg_num ();
if (file)
dump_flow_info (file);
if (n_basic_blocks <= 1 || is_too_expensive (_ ("jump bypassing disabled")))
return 0;
gcc_obstack_init (&gcse_obstack);
bytes_used = 0;
init_alias_analysis ();
alloc_reg_set_mem (max_gcse_regno);
compute_sets (get_insns ());
max_gcse_regno = max_reg_num ();
alloc_gcse_mem (get_insns ());
changed = one_cprop_pass (MAX_GCSE_PASSES + 2, 1, 1);
free_gcse_mem ();
if (file)
{
fprintf (file, "BYPASS of %s: %d basic blocks, ",
current_function_name (), n_basic_blocks);
fprintf (file, "%d bytes\n\n", bytes_used);
}
obstack_free (&gcse_obstack, NULL);
free_reg_set_mem ();
end_alias_analysis ();
allocate_reg_info (max_reg_num (), FALSE, FALSE);
return changed;
}
static bool
is_too_expensive (const char *pass)
{
if (n_edges > 20000 + n_basic_blocks * 4)
{
if (warn_disabled_optimization)
warning ("%s: %d basic blocks and %d edges/basic block",
pass, n_basic_blocks, n_edges / n_basic_blocks);
return true;
}
if ((n_basic_blocks
* SBITMAP_SET_SIZE (max_reg_num ())
* sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
{
if (warn_disabled_optimization)
warning ("%s: %d basic blocks and %d registers",
pass, n_basic_blocks, max_reg_num ());
return true;
}
return false;
}
#include "gt-gcse.h"