#include "config.h"
#include "system.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 "obstack.h"
static FILE *gcse_file;
static int run_jump_opt_after_gcse;
static FILE *debug_stderr;
static struct obstack gcse_obstack;
static char can_copy_p[(int) NUM_MACHINE_MODES];
static int can_copy_init_p;
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) (INSN_UID (INSN) > max_uid ? (abort (), 0) : 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;
rtx insn;
} 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 loads;
rtx stores;
struct ls_expr * next;
int invalid;
int index;
int hash_index;
rtx reaching_reg;
};
static struct ls_expr * pre_ldst_mems = NULL;
static regset reg_set_bitmap;
static sbitmap *reg_set_in_block;
static rtx * modify_mem_list;
bitmap modify_mem_list_set;
static rtx * canon_modify_mem_list;
bitmap canon_modify_mem_list_set;
static int bytes_used;
static int gcse_subst_count;
static int gcse_create_count;
static int const_prop_count;
static int copy_prop_count;
static sbitmap *rd_kill, *rd_gen, *reaching_defs, *rd_out;
static sbitmap *ae_kill, *ae_gen, *ae_in, *ae_out;
struct null_pointer_info
{
basic_block current_block;
unsigned int min_reg;
unsigned int max_reg;
sbitmap *nonnull_local;
sbitmap *nonnull_killed;
};
static void compute_can_copy PARAMS ((void));
static char *gmalloc PARAMS ((unsigned int));
static char *grealloc PARAMS ((char *, unsigned int));
static char *gcse_alloc PARAMS ((unsigned long));
static void alloc_gcse_mem PARAMS ((rtx));
static void free_gcse_mem PARAMS ((void));
static void alloc_reg_set_mem PARAMS ((int));
static void free_reg_set_mem PARAMS ((void));
static int get_bitmap_width PARAMS ((int, int, int));
static void record_one_set PARAMS ((int, rtx));
static void record_set_info PARAMS ((rtx, rtx, void *));
static void compute_sets PARAMS ((rtx));
static void hash_scan_insn PARAMS ((rtx, struct hash_table *, int));
static void hash_scan_set PARAMS ((rtx, rtx, struct hash_table *));
static void hash_scan_clobber PARAMS ((rtx, rtx, struct hash_table *));
static void hash_scan_call PARAMS ((rtx, rtx, struct hash_table *));
static int want_to_gcse_p PARAMS ((rtx));
static int oprs_unchanged_p PARAMS ((rtx, rtx, int));
static int oprs_anticipatable_p PARAMS ((rtx, rtx));
static int oprs_available_p PARAMS ((rtx, rtx));
static void insert_expr_in_table PARAMS ((rtx, enum machine_mode, rtx,
int, int, struct hash_table *));
static void insert_set_in_table PARAMS ((rtx, rtx, struct hash_table *));
static unsigned int hash_expr PARAMS ((rtx, enum machine_mode, int *, int));
static unsigned int hash_expr_1 PARAMS ((rtx, enum machine_mode, int *));
static unsigned int hash_string_1 PARAMS ((const char *));
static unsigned int hash_set PARAMS ((int, int));
static int expr_equiv_p PARAMS ((rtx, rtx));
static void record_last_reg_set_info PARAMS ((rtx, int));
static void record_last_mem_set_info PARAMS ((rtx));
static void record_last_set_info PARAMS ((rtx, rtx, void *));
static void compute_hash_table PARAMS ((struct hash_table *));
static void alloc_hash_table PARAMS ((int, struct hash_table *, int));
static void free_hash_table PARAMS ((struct hash_table *));
static void compute_hash_table_work PARAMS ((struct hash_table *));
static void dump_hash_table PARAMS ((FILE *, const char *,
struct hash_table *));
static struct expr *lookup_expr PARAMS ((rtx, struct hash_table *));
static struct expr *lookup_set PARAMS ((unsigned int, rtx, struct hash_table *));
static struct expr *next_set PARAMS ((unsigned int, struct expr *));
static void reset_opr_set_tables PARAMS ((void));
static int oprs_not_set_p PARAMS ((rtx, rtx));
static void mark_call PARAMS ((rtx));
static void mark_set PARAMS ((rtx, rtx));
static void mark_clobber PARAMS ((rtx, rtx));
static void mark_oprs_set PARAMS ((rtx));
static void alloc_cprop_mem PARAMS ((int, int));
static void free_cprop_mem PARAMS ((void));
static void compute_transp PARAMS ((rtx, int, sbitmap *, int));
static void compute_transpout PARAMS ((void));
static void compute_local_properties PARAMS ((sbitmap *, sbitmap *, sbitmap *,
struct hash_table *));
static void compute_cprop_data PARAMS ((void));
static void find_used_regs PARAMS ((rtx *, void *));
static int try_replace_reg PARAMS ((rtx, rtx, rtx));
static struct expr *find_avail_set PARAMS ((int, rtx));
static int cprop_jump PARAMS ((basic_block, rtx, rtx, rtx, rtx));
static void mems_conflict_for_gcse_p PARAMS ((rtx, rtx, void *));
static int load_killed_in_block_p PARAMS ((basic_block, int, rtx, int));
static void canon_list_insert PARAMS ((rtx, rtx, void *));
static int cprop_insn PARAMS ((rtx, int));
static int cprop PARAMS ((int));
static int one_cprop_pass PARAMS ((int, int));
static bool constprop_register PARAMS ((rtx, rtx, rtx, int));
static struct expr *find_bypass_set PARAMS ((int, int));
static int bypass_block PARAMS ((basic_block, rtx, rtx));
static int bypass_conditional_jumps PARAMS ((void));
static void alloc_pre_mem PARAMS ((int, int));
static void free_pre_mem PARAMS ((void));
static void compute_pre_data PARAMS ((void));
static int pre_expr_reaches_here_p PARAMS ((basic_block, struct expr *,
basic_block));
static void insert_insn_end_bb PARAMS ((struct expr *, basic_block, int));
static void pre_insert_copy_insn PARAMS ((struct expr *, rtx));
static void pre_insert_copies PARAMS ((void));
static int pre_delete PARAMS ((void));
static int pre_gcse PARAMS ((void));
static int one_pre_gcse_pass PARAMS ((int));
static void add_label_notes PARAMS ((rtx, rtx));
static void alloc_code_hoist_mem PARAMS ((int, int));
static void free_code_hoist_mem PARAMS ((void));
static void compute_code_hoist_vbeinout PARAMS ((void));
static void compute_code_hoist_data PARAMS ((void));
static int hoist_expr_reaches_here_p PARAMS ((basic_block, int, basic_block,
char *));
static void hoist_code PARAMS ((void));
static int one_code_hoisting_pass PARAMS ((void));
static void alloc_rd_mem PARAMS ((int, int));
static void free_rd_mem PARAMS ((void));
static void handle_rd_kill_set PARAMS ((rtx, int, basic_block));
static void compute_kill_rd PARAMS ((void));
static void compute_rd PARAMS ((void));
static void alloc_avail_expr_mem PARAMS ((int, int));
static void free_avail_expr_mem PARAMS ((void));
static void compute_ae_gen PARAMS ((struct hash_table *));
static int expr_killed_p PARAMS ((rtx, basic_block));
static void compute_ae_kill PARAMS ((sbitmap *, sbitmap *, struct hash_table *));
static int expr_reaches_here_p PARAMS ((struct occr *, struct expr *,
basic_block, int));
static rtx computing_insn PARAMS ((struct expr *, rtx));
static int def_reaches_here_p PARAMS ((rtx, rtx));
static int can_disregard_other_sets PARAMS ((struct reg_set **, rtx, int));
static int handle_avail_expr PARAMS ((rtx, struct expr *));
static int classic_gcse PARAMS ((void));
static int one_classic_gcse_pass PARAMS ((int));
static void invalidate_nonnull_info PARAMS ((rtx, rtx, void *));
static int delete_null_pointer_checks_1 PARAMS ((unsigned int *,
sbitmap *, sbitmap *,
struct null_pointer_info *));
static rtx process_insert_insn PARAMS ((struct expr *));
static int pre_edge_insert PARAMS ((struct edge_list *, struct expr **));
static int expr_reaches_here_p_work PARAMS ((struct occr *, struct expr *,
basic_block, int, char *));
static int pre_expr_reaches_here_p_work PARAMS ((basic_block, struct expr *,
basic_block, char *));
static struct ls_expr * ldst_entry PARAMS ((rtx));
static void free_ldst_entry PARAMS ((struct ls_expr *));
static void free_ldst_mems PARAMS ((void));
static void print_ldst_list PARAMS ((FILE *));
static struct ls_expr * find_rtx_in_ldst PARAMS ((rtx));
static int enumerate_ldsts PARAMS ((void));
static inline struct ls_expr * first_ls_expr PARAMS ((void));
static inline struct ls_expr * next_ls_expr PARAMS ((struct ls_expr *));
static int simple_mem PARAMS ((rtx));
static void invalidate_any_buried_refs PARAMS ((rtx));
static void compute_ld_motion_mems PARAMS ((void));
static void trim_ld_motion_mems PARAMS ((void));
static void update_ld_motion_stores PARAMS ((struct expr *));
static void reg_set_info PARAMS ((rtx, rtx, void *));
static int store_ops_ok PARAMS ((rtx, basic_block));
static void find_moveable_store PARAMS ((rtx));
static int compute_store_table PARAMS ((void));
static int load_kills_store PARAMS ((rtx, rtx));
static int find_loads PARAMS ((rtx, rtx));
static int store_killed_in_insn PARAMS ((rtx, rtx));
static int store_killed_after PARAMS ((rtx, rtx, basic_block));
static int store_killed_before PARAMS ((rtx, rtx, basic_block));
static void build_store_vectors PARAMS ((void));
static void insert_insn_start_bb PARAMS ((rtx, basic_block));
static int insert_store PARAMS ((struct ls_expr *, edge));
static void replace_store_insn PARAMS ((rtx, rtx, basic_block));
static void delete_store PARAMS ((struct ls_expr *,
basic_block));
static void free_store_memory PARAMS ((void));
static void store_motion PARAMS ((void));
static void free_insn_expr_list_list PARAMS ((rtx *));
static void clear_modify_mem_tables PARAMS ((void));
static void free_modify_mem_tables PARAMS ((void));
static rtx gcse_emit_move_after PARAMS ((rtx, rtx, rtx));
static void local_cprop_find_used_regs PARAMS ((rtx *, void *));
static bool do_local_cprop PARAMS ((rtx, rtx, int, rtx*));
static bool adjust_libcall_notes PARAMS ((rtx, rtx, rtx, rtx*));
static void local_cprop_pass PARAMS ((int));
int
gcse_main (f, file)
rtx f;
FILE *file;
{
int changed, pass;
int initial_bytes_used;
int max_pass_bytes;
char *gcse_obstack_bottom;
int orig_bb_count;
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);
orig_bb_count = n_basic_blocks;
if (n_basic_blocks <= 1)
return 0;
if (n_basic_blocks > 1000 && n_edges / n_basic_blocks >= 20)
{
if (warn_disabled_optimization)
warning ("GCSE disabled: %d > 1000 basic blocks and %d >= 20 edges/basic block",
n_basic_blocks, n_edges / n_basic_blocks);
return 0;
}
if ((n_basic_blocks
* SBITMAP_SET_SIZE (max_gcse_regno)
* sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
{
if (warn_disabled_optimization)
warning ("GCSE disabled: %d basic blocks and %d registers",
n_basic_blocks, max_gcse_regno);
return 0;
}
if (! can_copy_init_p)
{
compute_can_copy ();
can_copy_init_p = 1;
}
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);
changed = one_cprop_pass (pass + 1, 0);
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)
changed |= one_classic_gcse_pass (pass + 1);
else
{
changed |= one_pre_gcse_pass (pass + 1);
if (changed)
{
free_modify_mem_tables ();
modify_mem_list
= (rtx *) gmalloc (last_basic_block * sizeof (rtx));
canon_modify_mem_list
= (rtx *) gmalloc (last_basic_block * sizeof (rtx));
memset ((char *) modify_mem_list, 0, last_basic_block * sizeof (rtx));
memset ((char *) canon_modify_mem_list, 0, last_basic_block * sizeof (rtx));
orig_bb_count = n_basic_blocks;
}
free_reg_set_mem ();
alloc_reg_set_mem (max_reg_num ());
compute_sets (f);
run_jump_opt_after_gcse = 1;
}
if (max_pass_bytes < bytes_used)
max_pass_bytes = bytes_used;
free_gcse_mem ();
if (optimize_size)
{
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;
}
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);
one_cprop_pass (pass + 1, 1);
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 (0 && !optimize_size && flag_gcse_sm)
store_motion ();
return run_jump_opt_after_gcse;
}
static void
compute_can_copy ()
{
int i;
#ifndef AVOID_CCMODE_COPIES
rtx reg, insn;
#endif
memset (can_copy_p, 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_p[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_p[i] = 1;
#endif
}
else
can_copy_p[i] = 1;
end_sequence ();
}
static char *
gmalloc (size)
unsigned int size;
{
bytes_used += size;
return xmalloc (size);
}
static char *
grealloc (ptr, size)
char *ptr;
unsigned int size;
{
return xrealloc (ptr, size);
}
static char *
gcse_alloc (size)
unsigned long size;
{
bytes_used += size;
return (char *) obstack_alloc (&gcse_obstack, size);
}
static void
alloc_gcse_mem (f)
rtx f;
{
int i, n;
rtx insn;
max_uid = get_max_uid ();
n = (max_uid + 1) * sizeof (int);
uid_cuid = (int *) gmalloc (n);
memset ((char *) uid_cuid, 0, n);
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;
n = (max_cuid + 1) * sizeof (rtx);
cuid_insn = (rtx *) gmalloc (n);
memset ((char *) cuid_insn, 0, n);
for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
if (INSN_P (insn))
CUID_INSN (i++) = insn;
reg_set_bitmap = BITMAP_XMALLOC ();
reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (last_basic_block,
max_gcse_regno);
modify_mem_list = (rtx *) gmalloc (last_basic_block * sizeof (rtx));
canon_modify_mem_list = (rtx *) gmalloc (last_basic_block * sizeof (rtx));
memset ((char *) modify_mem_list, 0, last_basic_block * sizeof (rtx));
memset ((char *) canon_modify_mem_list, 0, last_basic_block * sizeof (rtx));
modify_mem_list_set = BITMAP_XMALLOC ();
canon_modify_mem_list_set = BITMAP_XMALLOC ();
}
static void
free_gcse_mem ()
{
free (uid_cuid);
free (cuid_insn);
BITMAP_XFREE (reg_set_bitmap);
sbitmap_vector_free (reg_set_in_block);
free_modify_mem_tables ();
BITMAP_XFREE (modify_mem_list_set);
BITMAP_XFREE (canon_modify_mem_list_set);
}
static int
get_bitmap_width (n, x, y)
int n;
int x;
int y;
{
size_t max_bitmap_memory = 10 * 1024 * 1024;
size_t column_size = n * x * sizeof (SBITMAP_ELT_TYPE);
if (column_size * SBITMAP_SET_SIZE (y) <= max_bitmap_memory)
return y;
return SBITMAP_ELT_BITS * ((max_bitmap_memory + column_size - 1)
/ column_size);
}
static void
compute_local_properties (transp, comp, antloc, table)
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 (n_regs)
int n_regs;
{
unsigned int n;
reg_set_table_size = n_regs + REG_SET_TABLE_SLOP;
n = reg_set_table_size * sizeof (struct reg_set *);
reg_set_table = (struct reg_set **) gmalloc (n);
memset ((char *) reg_set_table, 0, n);
gcc_obstack_init (®_set_obstack);
}
static void
free_reg_set_mem ()
{
free (reg_set_table);
obstack_free (®_set_obstack, NULL);
}
static void
record_one_set (regno, insn)
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
= (struct reg_set **) grealloc ((char *) reg_set_table,
new_size * sizeof (struct reg_set *));
memset ((char *) (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 = (struct reg_set *) obstack_alloc (®_set_obstack,
sizeof (struct reg_set));
bytes_used += sizeof (struct reg_set);
new_reg_info->insn = insn;
new_reg_info->next = reg_set_table[regno];
reg_set_table[regno] = new_reg_info;
}
static void
record_set_info (dest, setter, data)
rtx dest, setter ATTRIBUTE_UNUSED;
void *data;
{
rtx record_set_insn = (rtx) data;
if (GET_CODE (dest) == REG && REGNO (dest) >= FIRST_PSEUDO_REGISTER)
record_one_set (REGNO (dest), record_set_insn);
}
static void
compute_sets (f)
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 GTY(()) rtx test_insn;
static int
want_to_gcse_p (x)
rtx x;
{
int num_clobbers = 0;
int icode;
switch (GET_CODE (x))
{
case REG:
case SUBREG:
case CONST_INT:
case CONST_DOUBLE:
case CONST_VECTOR:
case CALL:
return 0;
default:
break;
}
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 (x, insn, avail_p)
rtx x, 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 (dest, setter, data)
rtx dest, setter ATTRIBUTE_UNUSED;
void *data ATTRIBUTE_UNUSED;
{
while (GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT
|| GET_CODE (dest) == SIGN_EXTRACT
|| GET_CODE (dest) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
if (GET_CODE (dest) != MEM)
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 (bb, uid_limit, x, avail_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 (GET_CODE (setter) == CALL_INSN)
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 (x, insn)
rtx x, insn;
{
return oprs_unchanged_p (x, insn, 0);
}
static int
oprs_available_p (x, insn)
rtx x, insn;
{
return oprs_unchanged_p (x, insn, 1);
}
static unsigned int
hash_expr (x, mode, do_not_record_p, hash_table_size)
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_expr_1 (x, mode, do_not_record_p);
return hash % hash_table_size;
}
static inline unsigned
hash_string_1 (ps)
const char *ps;
{
unsigned hash = 0;
const unsigned char *p = (const unsigned char *) ps;
if (p)
while (*p)
hash += *p++;
return hash;
}
static unsigned int
hash_expr_1 (x, mode, do_not_record_p)
rtx x;
enum machine_mode mode;
int *do_not_record_p;
{
int i, j;
unsigned hash = 0;
enum rtx_code code;
const char *fmt;
if (x == 0)
return hash;
repeat:
code = GET_CODE (x);
switch (code)
{
case REG:
hash += ((unsigned int) REG << 7) + REGNO (x);
return hash;
case CONST_INT:
hash += (((unsigned int) CONST_INT << 7) + (unsigned int) mode
+ (unsigned int) INTVAL (x));
return hash;
case CONST_DOUBLE:
hash += (unsigned int) code + (unsigned int) GET_MODE (x);
if (GET_MODE (x) != VOIDmode)
for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
hash += (unsigned int) XWINT (x, i);
else
hash += ((unsigned int) CONST_DOUBLE_LOW (x)
+ (unsigned int) CONST_DOUBLE_HIGH (x));
return hash;
case CONST_VECTOR:
{
int units;
rtx elt;
units = CONST_VECTOR_NUNITS (x);
for (i = 0; i < units; ++i)
{
elt = CONST_VECTOR_ELT (x, i);
hash += hash_expr_1 (elt, GET_MODE (elt), do_not_record_p);
}
return hash;
}
case LABEL_REF:
hash += (((unsigned int) LABEL_REF << 7)
+ CODE_LABEL_NUMBER (XEXP (x, 0)));
return hash;
case SYMBOL_REF:
{
unsigned int h = 0;
const unsigned char *p = (const unsigned char *) XSTR (x, 0);
while (*p)
h += (h << 7) + *p++;
hash += ((unsigned int) SYMBOL_REF << 7) + h;
return hash;
}
case MEM:
if (MEM_VOLATILE_P (x))
{
*do_not_record_p = 1;
return 0;
}
hash += (unsigned int) MEM;
x = XEXP (x, 0);
goto repeat;
case PRE_DEC:
case PRE_INC:
case POST_DEC:
case POST_INC:
case PC:
case CC0:
case CALL:
case UNSPEC_VOLATILE:
*do_not_record_p = 1;
return 0;
case ASM_OPERANDS:
if (MEM_VOLATILE_P (x))
{
*do_not_record_p = 1;
return 0;
}
else
{
hash += (unsigned) code + (unsigned) GET_MODE (x)
+ hash_string_1 (ASM_OPERANDS_TEMPLATE (x))
+ hash_string_1 (ASM_OPERANDS_OUTPUT_CONSTRAINT (x))
+ (unsigned) ASM_OPERANDS_OUTPUT_IDX (x);
if (ASM_OPERANDS_INPUT_LENGTH (x))
{
for (i = 1; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
{
hash += (hash_expr_1 (ASM_OPERANDS_INPUT (x, i),
GET_MODE (ASM_OPERANDS_INPUT (x, i)),
do_not_record_p)
+ hash_string_1 (ASM_OPERANDS_INPUT_CONSTRAINT
(x, i)));
}
hash += hash_string_1 (ASM_OPERANDS_INPUT_CONSTRAINT (x, 0));
x = ASM_OPERANDS_INPUT (x, 0);
mode = GET_MODE (x);
goto repeat;
}
return hash;
}
default:
break;
}
hash += (unsigned) code + (unsigned) GET_MODE (x);
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;
}
hash += hash_expr_1 (XEXP (x, i), 0, do_not_record_p);
if (*do_not_record_p)
return 0;
}
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
{
hash += hash_expr_1 (XVECEXP (x, i, j), 0, do_not_record_p);
if (*do_not_record_p)
return 0;
}
else if (fmt[i] == 's')
hash += hash_string_1 (XSTR (x, i));
else if (fmt[i] == 'i')
hash += (unsigned int) XINT (x, i);
else
abort ();
}
return hash;
}
static unsigned int
hash_set (regno, hash_table_size)
int regno;
int hash_table_size;
{
unsigned int hash;
hash = regno;
return hash % hash_table_size;
}
static int
expr_equiv_p (x, y)
rtx x, y;
{
int i, j;
enum rtx_code code;
const char *fmt;
if (x == y)
return 1;
if (x == 0 || y == 0)
return x == y;
code = GET_CODE (x);
if (code != GET_CODE (y))
return 0;
if (GET_MODE (x) != GET_MODE (y))
return 0;
switch (code)
{
case PC:
case CC0:
return x == y;
case CONST_INT:
return INTVAL (x) == INTVAL (y);
case LABEL_REF:
return XEXP (x, 0) == XEXP (y, 0);
case SYMBOL_REF:
return XSTR (x, 0) == XSTR (y, 0);
case REG:
return REGNO (x) == REGNO (y);
case MEM:
if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
return 0;
break;
case PLUS:
case MULT:
case AND:
case IOR:
case XOR:
case NE:
case EQ:
return ((expr_equiv_p (XEXP (x, 0), XEXP (y, 0))
&& expr_equiv_p (XEXP (x, 1), XEXP (y, 1)))
|| (expr_equiv_p (XEXP (x, 0), XEXP (y, 1))
&& expr_equiv_p (XEXP (x, 1), XEXP (y, 0))));
case ASM_OPERANDS:
if (MEM_VOLATILE_P (x) || MEM_VOLATILE_P (y))
return 0;
if (GET_MODE (x) != GET_MODE (y)
|| strcmp (ASM_OPERANDS_TEMPLATE (x), ASM_OPERANDS_TEMPLATE (y))
|| strcmp (ASM_OPERANDS_OUTPUT_CONSTRAINT (x),
ASM_OPERANDS_OUTPUT_CONSTRAINT (y))
|| ASM_OPERANDS_OUTPUT_IDX (x) != ASM_OPERANDS_OUTPUT_IDX (y)
|| ASM_OPERANDS_INPUT_LENGTH (x) != ASM_OPERANDS_INPUT_LENGTH (y))
return 0;
if (ASM_OPERANDS_INPUT_LENGTH (x))
{
for (i = ASM_OPERANDS_INPUT_LENGTH (x) - 1; i >= 0; i--)
if (! expr_equiv_p (ASM_OPERANDS_INPUT (x, i),
ASM_OPERANDS_INPUT (y, i))
|| strcmp (ASM_OPERANDS_INPUT_CONSTRAINT (x, i),
ASM_OPERANDS_INPUT_CONSTRAINT (y, i)))
return 0;
}
return 1;
default:
break;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
switch (fmt[i])
{
case 'e':
if (! expr_equiv_p (XEXP (x, i), XEXP (y, i)))
return 0;
break;
case 'E':
if (XVECLEN (x, i) != XVECLEN (y, i))
return 0;
for (j = 0; j < XVECLEN (x, i); j++)
if (! expr_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
return 0;
break;
case 's':
if (strcmp (XSTR (x, i), XSTR (y, i)))
return 0;
break;
case 'i':
if (XINT (x, i) != XINT (y, i))
return 0;
break;
case 'w':
if (XWINT (x, i) != XWINT (y, i))
return 0;
break;
case '0':
break;
default:
abort ();
}
}
return 1;
}
static void
insert_expr_in_table (x, mode, insn, antic_p, avail_p, table)
rtx x;
enum machine_mode mode;
rtx insn;
int antic_p, 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;
struct occr *last_occr = NULL;
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 = (struct 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;
while (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn))
{
last_occr = antic_occr;
antic_occr = antic_occr->next;
}
if (antic_occr)
;
else
{
antic_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
bytes_used += sizeof (struct occr);
if (cur_expr->antic_occr == NULL)
cur_expr->antic_occr = antic_occr;
else
last_occr->next = antic_occr;
antic_occr->insn = insn;
antic_occr->next = NULL;
}
}
if (avail_p)
{
avail_occr = cur_expr->avail_occr;
while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn))
{
last_occr = avail_occr;
avail_occr = avail_occr->next;
}
if (avail_occr)
avail_occr->insn = insn;
else
{
avail_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
bytes_used += sizeof (struct occr);
if (cur_expr->avail_occr == NULL)
cur_expr->avail_occr = avail_occr;
else
last_occr->next = avail_occr;
avail_occr->insn = insn;
avail_occr->next = NULL;
}
}
}
static void
insert_set_in_table (x, insn, 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, *last_occr = NULL;
if (GET_CODE (x) != SET
|| GET_CODE (SET_DEST (x)) != REG)
abort ();
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 = (struct 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;
while (cur_occr && BLOCK_NUM (cur_occr->insn) != BLOCK_NUM (insn))
{
last_occr = cur_occr;
cur_occr = cur_occr->next;
}
if (cur_occr)
cur_occr->insn = insn;
else
{
cur_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
bytes_used += sizeof (struct occr);
if (cur_expr->avail_occr == NULL)
cur_expr->avail_occr = cur_occr;
else
last_occr->next = cur_occr;
cur_occr->insn = insn;
cur_occr->next = NULL;
}
}
static void
hash_scan_set (pat, insn, table)
rtx pat, 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 (GET_CODE (dest) == REG)
{
unsigned int regno = REGNO (dest);
rtx tmp;
if (table->set_p && (note = find_reg_equal_equiv_note (insn)) != 0
&& 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)
&& !(flag_float_store && FLOAT_MODE_P (GET_MODE (dest)))
&& ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0
|| GET_CODE (XEXP (note, 0)) != MEM))
{
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
&& ((GET_CODE (src) == REG
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
&& can_copy_p [GET_MODE (dest)]
&& REGNO (src) != regno)
|| CONSTANT_P (src))
&& (insn == BLOCK_END (BLOCK_NUM (insn))
|| ((tmp = next_nonnote_insn (insn)) != NULL_RTX
&& oprs_available_p (pat, tmp))))
insert_set_in_table (pat, insn, table);
}
}
static void
hash_scan_clobber (x, insn, table)
rtx x ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
struct hash_table *table ATTRIBUTE_UNUSED;
{
}
static void
hash_scan_call (x, insn, table)
rtx x ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
struct hash_table *table ATTRIBUTE_UNUSED;
{
}
static void
hash_scan_insn (insn, table, in_libcall_block)
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, name, 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
= (struct expr **) xcalloc (table->n_elems, sizeof (struct expr *));
hash_val = (unsigned int *) 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 (insn, regno)
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 (dest, unused1, v_insn)
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) == SIGN_EXTRACT
|| GET_CODE (dest) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
if (GET_CODE (dest) != MEM)
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]);
bitmap_set_bit (canon_modify_mem_list_set, bb);
}
static void
record_last_mem_set_info (insn)
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 (GET_CODE (insn) == CALL_INSN)
{
canon_modify_mem_list[bb] =
alloc_INSN_LIST (insn, canon_modify_mem_list[bb]);
bitmap_set_bit (canon_modify_mem_list_set, bb);
}
else
note_stores (PATTERN (insn), canon_list_insert, (void*) insn);
}
static void
record_last_set_info (dest, setter, data)
rtx dest, setter ATTRIBUTE_UNUSED;
void *data;
{
rtx last_set_insn = (rtx) data;
if (GET_CODE (dest) == SUBREG)
dest = SUBREG_REG (dest);
if (GET_CODE (dest) == REG)
record_last_reg_set_info (last_set_insn, REGNO (dest));
else if (GET_CODE (dest) == MEM
&& ! push_operand (dest, GET_MODE (dest)))
record_last_mem_set_info (last_set_insn);
}
static void
compute_hash_table_work (table)
struct hash_table *table;
{
unsigned int i;
sbitmap_vector_zero (reg_set_in_block, last_basic_block);
clear_modify_mem_tables ();
reg_avail_info = (struct 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 = current_bb->head;
insn && insn != NEXT_INSN (current_bb->end);
insn = NEXT_INSN (insn))
{
if (! INSN_P (insn))
continue;
if (GET_CODE (insn) == CALL_INSN)
{
bool clobbers_all = false;
#ifdef NON_SAVING_SETJMP
if (NON_SAVING_SETJMP
&& find_reg_note (insn, REG_SETJMP, NULL_RTX))
clobbers_all = true;
#endif
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
if (clobbers_all
|| 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);
}
for (insn = current_bb->head, in_libcall_block = 0;
insn && insn != NEXT_INSN (current_bb->end);
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 (n_insns, table, set_p)
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 = (struct expr **) gmalloc (n);
table->set_p = set_p;
}
static void
free_hash_table (table)
struct hash_table *table;
{
free (table->table);
}
static void
compute_hash_table (table)
struct hash_table *table;
{
table->n_elems = 0;
memset ((char *) table->table, 0,
table->size * sizeof (struct expr *));
compute_hash_table_work (table);
}
static struct expr *
lookup_expr (pat, table)
rtx pat;
struct hash_table *table;
{
int do_not_record_p;
unsigned int hash = hash_expr (pat, GET_MODE (pat), &do_not_record_p,
table->size);
struct expr *expr;
if (do_not_record_p)
return NULL;
expr = table->table[hash];
while (expr && ! expr_equiv_p (expr->expr, pat))
expr = expr->next_same_hash;
return expr;
}
static struct expr *
lookup_set (regno, pat, table)
unsigned int regno;
rtx pat;
struct hash_table *table;
{
unsigned int hash = hash_set (regno, table->size);
struct expr *expr;
expr = table->table[hash];
if (pat)
{
while (expr && ! expr_equiv_p (expr->expr, pat))
expr = expr->next_same_hash;
}
else
{
while (expr && REGNO (SET_DEST (expr->expr)) != regno)
expr = expr->next_same_hash;
}
return expr;
}
static struct expr *
next_set (regno, expr)
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 (listp)
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 ()
{
int i;
EXECUTE_IF_SET_IN_BITMAP
(modify_mem_list_set, 0, i, free_INSN_LIST_list (modify_mem_list + i));
bitmap_clear (modify_mem_list_set);
EXECUTE_IF_SET_IN_BITMAP
(canon_modify_mem_list_set, 0, i,
free_insn_expr_list_list (canon_modify_mem_list + i));
bitmap_clear (canon_modify_mem_list_set);
}
static void
free_modify_mem_tables ()
{
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 ()
{
CLEAR_REG_SET (reg_set_bitmap);
clear_modify_mem_tables ();
}
static int
oprs_not_set_p (x, insn)
rtx x, 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 (insn)
rtx insn;
{
if (! CONST_OR_PURE_CALL_P (insn))
record_last_mem_set_info (insn);
}
static void
mark_set (pat, insn)
rtx pat, insn;
{
rtx dest = SET_DEST (pat);
while (GET_CODE (dest) == SUBREG
|| GET_CODE (dest) == ZERO_EXTRACT
|| GET_CODE (dest) == SIGN_EXTRACT
|| GET_CODE (dest) == STRICT_LOW_PART)
dest = XEXP (dest, 0);
if (GET_CODE (dest) == REG)
SET_REGNO_REG_SET (reg_set_bitmap, REGNO (dest));
else if (GET_CODE (dest) == MEM)
record_last_mem_set_info (insn);
if (GET_CODE (SET_SRC (pat)) == CALL)
mark_call (insn);
}
static void
mark_clobber (pat, insn)
rtx pat, insn;
{
rtx clob = XEXP (pat, 0);
while (GET_CODE (clob) == SUBREG || GET_CODE (clob) == STRICT_LOW_PART)
clob = XEXP (clob, 0);
if (GET_CODE (clob) == REG)
SET_REGNO_REG_SET (reg_set_bitmap, REGNO (clob));
else
record_last_mem_set_info (insn);
}
static void
mark_oprs_set (insn)
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 void
alloc_rd_mem (n_blocks, n_insns)
int n_blocks, n_insns;
{
rd_kill = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
sbitmap_vector_zero (rd_kill, n_blocks);
rd_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
sbitmap_vector_zero (rd_gen, n_blocks);
reaching_defs = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
sbitmap_vector_zero (reaching_defs, n_blocks);
rd_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
sbitmap_vector_zero (rd_out, n_blocks);
}
static void
free_rd_mem ()
{
sbitmap_vector_free (rd_kill);
sbitmap_vector_free (rd_gen);
sbitmap_vector_free (reaching_defs);
sbitmap_vector_free (rd_out);
}
static void
handle_rd_kill_set (insn, regno, bb)
rtx insn;
int regno;
basic_block bb;
{
struct reg_set *this_reg;
for (this_reg = reg_set_table[regno]; this_reg; this_reg = this_reg ->next)
if (BLOCK_NUM (this_reg->insn) != BLOCK_NUM (insn))
SET_BIT (rd_kill[bb->index], INSN_CUID (this_reg->insn));
}
static void
compute_kill_rd ()
{
int cuid;
unsigned int regno;
int i;
basic_block bb;
FOR_EACH_BB (bb)
for (cuid = 0; cuid < max_cuid; cuid++)
if (TEST_BIT (rd_gen[bb->index], cuid))
{
rtx insn = CUID_INSN (cuid);
rtx pat = PATTERN (insn);
if (GET_CODE (insn) == CALL_INSN)
{
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
handle_rd_kill_set (insn, regno, bb);
}
if (GET_CODE (pat) == PARALLEL)
{
for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
{
enum rtx_code code = GET_CODE (XVECEXP (pat, 0, i));
if ((code == SET || code == CLOBBER)
&& GET_CODE (XEXP (XVECEXP (pat, 0, i), 0)) == REG)
handle_rd_kill_set (insn,
REGNO (XEXP (XVECEXP (pat, 0, i), 0)),
bb);
}
}
else if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == REG)
handle_rd_kill_set (insn, REGNO (SET_DEST (pat)), bb);
}
}
static void
compute_rd ()
{
int changed, passes;
basic_block bb;
FOR_EACH_BB (bb)
sbitmap_copy (rd_out[bb->index] , rd_gen[bb->index] );
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
FOR_EACH_BB (bb)
{
sbitmap_union_of_preds (reaching_defs[bb->index], rd_out, bb->index);
changed |= sbitmap_union_of_diff_cg (rd_out[bb->index], rd_gen[bb->index],
reaching_defs[bb->index], rd_kill[bb->index]);
}
passes++;
}
if (gcse_file)
fprintf (gcse_file, "reaching def computation: %d passes\n", passes);
}
static void
alloc_avail_expr_mem (n_blocks, n_exprs)
int n_blocks, n_exprs;
{
ae_kill = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
sbitmap_vector_zero (ae_kill, n_blocks);
ae_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
sbitmap_vector_zero (ae_gen, n_blocks);
ae_in = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
sbitmap_vector_zero (ae_in, n_blocks);
ae_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
sbitmap_vector_zero (ae_out, n_blocks);
}
static void
free_avail_expr_mem ()
{
sbitmap_vector_free (ae_kill);
sbitmap_vector_free (ae_gen);
sbitmap_vector_free (ae_in);
sbitmap_vector_free (ae_out);
}
static void
compute_ae_gen (expr_hash_table)
struct hash_table *expr_hash_table;
{
unsigned int i;
struct expr *expr;
struct occr *occr;
for (i = 0; i < expr_hash_table->size; i++)
for (expr = expr_hash_table->table[i]; expr != 0; expr = expr->next_same_hash)
for (occr = expr->avail_occr; occr != 0; occr = occr->next)
SET_BIT (ae_gen[BLOCK_NUM (occr->insn)], expr->bitmap_index);
}
static int
expr_killed_p (x, bb)
rtx x;
basic_block bb;
{
int i, j;
enum rtx_code code;
const char *fmt;
if (x == 0)
return 1;
code = GET_CODE (x);
switch (code)
{
case REG:
return TEST_BIT (reg_set_in_block[bb->index], REGNO (x));
case MEM:
if (load_killed_in_block_p (bb, get_max_uid () + 1, x, 0))
return 1;
else
return expr_killed_p (XEXP (x, 0), bb);
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 0;
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 expr_killed_p (XEXP (x, i), bb);
else if (expr_killed_p (XEXP (x, i), bb))
return 1;
}
else if (fmt[i] == 'E')
for (j = 0; j < XVECLEN (x, i); j++)
if (expr_killed_p (XVECEXP (x, i, j), bb))
return 1;
}
return 0;
}
static void
compute_ae_kill (ae_gen, ae_kill, expr_hash_table)
sbitmap *ae_gen, *ae_kill;
struct hash_table *expr_hash_table;
{
basic_block bb;
unsigned int i;
struct expr *expr;
FOR_EACH_BB (bb)
for (i = 0; i < expr_hash_table->size; i++)
for (expr = expr_hash_table->table[i]; expr; expr = expr->next_same_hash)
{
if (TEST_BIT (ae_gen[bb->index], expr->bitmap_index))
continue;
if (expr_killed_p (expr->expr, bb))
SET_BIT (ae_kill[bb->index], expr->bitmap_index);
}
}
static int
expr_reaches_here_p_work (occr, expr, bb, check_self_loop, visited)
struct occr *occr;
struct expr *expr;
basic_block bb;
int check_self_loop;
char *visited;
{
edge pred;
for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
{
basic_block pred_bb = pred->src;
if (visited[pred_bb->index])
;
else if (pred_bb == bb)
{
if (check_self_loop
&& TEST_BIT (ae_gen[pred_bb->index], expr->bitmap_index)
&& BLOCK_NUM (occr->insn) == pred_bb->index)
return 1;
visited[pred_bb->index] = 1;
}
else if (TEST_BIT (ae_kill[pred_bb->index], expr->bitmap_index))
visited[pred_bb->index] = 1;
else if (TEST_BIT (ae_gen[pred_bb->index], expr->bitmap_index))
{
if (BLOCK_NUM (occr->insn) == pred_bb->index)
return 1;
visited[pred_bb->index] = 1;
}
else
{
visited[pred_bb->index] = 1;
if (expr_reaches_here_p_work (occr, expr, pred_bb, check_self_loop,
visited))
return 1;
}
}
return 0;
}
static int
expr_reaches_here_p (occr, expr, bb, check_self_loop)
struct occr *occr;
struct expr *expr;
basic_block bb;
int check_self_loop;
{
int rval;
char *visited = (char *) xcalloc (last_basic_block, 1);
rval = expr_reaches_here_p_work (occr, expr, bb, check_self_loop, visited);
free (visited);
return rval;
}
static rtx
computing_insn (expr, insn)
struct expr *expr;
rtx insn;
{
basic_block bb = BLOCK_FOR_INSN (insn);
if (expr->avail_occr->next == NULL)
{
if (BLOCK_FOR_INSN (expr->avail_occr->insn) == bb)
return NULL;
return expr->avail_occr->insn;
}
else
{
struct occr *occr;
rtx insn_computes_expr = NULL;
int can_reach = 0;
for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
{
if (BLOCK_FOR_INSN (occr->insn) == bb)
{
if (INSN_CUID (insn) < INSN_CUID (occr->insn)
&& expr_reaches_here_p (occr, expr, bb, 1))
{
can_reach++;
if (can_reach > 1)
return NULL;
insn_computes_expr = occr->insn;
}
}
else if (expr_reaches_here_p (occr, expr, bb, 0))
{
can_reach++;
if (can_reach > 1)
return NULL;
insn_computes_expr = occr->insn;
}
}
if (insn_computes_expr == NULL)
abort ();
return insn_computes_expr;
}
}
static int
def_reaches_here_p (insn, def_insn)
rtx insn, def_insn;
{
rtx reg;
if (TEST_BIT (reaching_defs[BLOCK_NUM (insn)], INSN_CUID (def_insn)))
return 1;
if (BLOCK_NUM (insn) == BLOCK_NUM (def_insn))
{
if (INSN_CUID (def_insn) < INSN_CUID (insn))
{
if (GET_CODE (PATTERN (def_insn)) == PARALLEL)
return 1;
else if (GET_CODE (PATTERN (def_insn)) == CLOBBER)
reg = XEXP (PATTERN (def_insn), 0);
else if (GET_CODE (PATTERN (def_insn)) == SET)
reg = SET_DEST (PATTERN (def_insn));
else
abort ();
return ! reg_set_between_p (reg, NEXT_INSN (def_insn), insn);
}
else
return 0;
}
return 0;
}
static int
can_disregard_other_sets (addr_this_reg, insn, for_combine)
struct reg_set **addr_this_reg;
rtx insn;
int for_combine;
{
int number_of_reaching_defs = 0;
struct reg_set *this_reg;
for (this_reg = *addr_this_reg; this_reg != 0; this_reg = this_reg->next)
if (def_reaches_here_p (insn, this_reg->insn))
{
number_of_reaching_defs++;
if (GET_CODE (PATTERN (this_reg->insn)) == PARALLEL)
return 0;
if (!for_combine
&& (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER
|| ! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
SET_SRC (PATTERN (insn)))))
return 0;
if (number_of_reaching_defs > 1)
{
if (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER)
return 0;
else if (! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
SET_SRC (PATTERN (insn))))
return 0;
}
*addr_this_reg = this_reg;
}
return number_of_reaching_defs;
}
static int
handle_avail_expr (insn, expr)
rtx insn;
struct expr *expr;
{
rtx pat, insn_computes_expr, expr_set;
rtx to;
struct reg_set *this_reg;
int found_setting, use_src;
int changed = 0;
insn_computes_expr = computing_insn (expr, insn);
if (insn_computes_expr == NULL)
return 0;
expr_set = single_set (insn_computes_expr);
if (!expr_set)
abort ();
found_setting = 0;
use_src = 0;
if (GET_CODE (SET_SRC (expr_set)) == REG)
{
unsigned int regnum_for_replacing
= REGNO (SET_SRC (expr_set));
if (regnum_for_replacing >= max_gcse_regno
|| (((this_reg = reg_set_table[regnum_for_replacing]),
this_reg->next == NULL)
|| can_disregard_other_sets (&this_reg, insn, 0)))
{
use_src = 1;
found_setting = 1;
}
}
if (!found_setting)
{
unsigned int regnum_for_replacing
= REGNO (SET_DEST (expr_set));
if (regnum_for_replacing >= max_gcse_regno)
abort ();
this_reg = reg_set_table[regnum_for_replacing];
if (this_reg->next == NULL
|| can_disregard_other_sets (&this_reg, insn, 0))
found_setting = 1;
}
if (found_setting)
{
pat = PATTERN (insn);
if (use_src)
to = SET_SRC (expr_set);
else
to = SET_DEST (expr_set);
changed = validate_change (insn, &SET_SRC (pat), to, 0);
if (changed)
{
gcse_subst_count++;
if (gcse_file != NULL)
{
fprintf (gcse_file, "GCSE: Replacing the source in insn %d with",
INSN_UID (insn));
fprintf (gcse_file, " reg %d %s insn %d\n",
REGNO (to), use_src ? "from" : "set in",
INSN_UID (insn_computes_expr));
}
}
}
else if (1 )
{
rtx new_insn;
to = gen_reg_rtx (GET_MODE (SET_DEST (expr_set)));
new_insn
= emit_insn_after (gen_rtx_SET (VOIDmode, to,
SET_DEST (expr_set)),
insn_computes_expr);
record_one_set (REGNO (to), new_insn);
gcse_create_count++;
if (gcse_file != NULL)
{
fprintf (gcse_file, "GCSE: Creating insn %d to copy value of reg %d",
INSN_UID (NEXT_INSN (insn_computes_expr)),
REGNO (SET_SRC (PATTERN (NEXT_INSN (insn_computes_expr)))));
fprintf (gcse_file, ", computed in insn %d,\n",
INSN_UID (insn_computes_expr));
fprintf (gcse_file, " into newly allocated reg %d\n",
REGNO (to));
}
pat = PATTERN (insn);
changed = validate_change (insn, &SET_SRC (pat),
SET_DEST (PATTERN
(NEXT_INSN (insn_computes_expr))),
0);
if (changed)
{
gcse_subst_count++;
if (gcse_file != NULL)
{
fprintf (gcse_file,
"GCSE: Replacing the source in insn %d with reg %d ",
INSN_UID (insn),
REGNO (SET_DEST (PATTERN (NEXT_INSN
(insn_computes_expr)))));
fprintf (gcse_file, "set in insn %d\n",
INSN_UID (insn_computes_expr));
}
}
}
return changed;
}
static int
classic_gcse ()
{
int changed;
rtx insn;
basic_block bb;
if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
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;
insn != NULL && insn != NEXT_INSN (bb->end);
insn = NEXT_INSN (insn))
{
if (GET_CODE (insn) == INSN
&& GET_CODE (PATTERN (insn)) == SET
&& GET_CODE (SET_DEST (PATTERN (insn))) == REG
&& REGNO (SET_DEST (PATTERN (insn))) >= FIRST_PSEUDO_REGISTER)
{
rtx pat = PATTERN (insn);
rtx src = SET_SRC (pat);
struct expr *expr;
if (want_to_gcse_p (src)
&& ((expr = lookup_expr (src, &expr_hash_table)) != NULL)
&& TEST_BIT (ae_in[bb->index], expr->bitmap_index)
&& oprs_not_set_p (src, insn))
changed |= handle_avail_expr (insn, expr);
}
if (INSN_P (insn))
mark_oprs_set (insn);
}
}
return changed;
}
static int
one_classic_gcse_pass (pass)
int pass;
{
int changed = 0;
gcse_subst_count = 0;
gcse_create_count = 0;
alloc_hash_table (max_cuid, &expr_hash_table, 0);
alloc_rd_mem (last_basic_block, max_cuid);
compute_hash_table (&expr_hash_table);
if (gcse_file)
dump_hash_table (gcse_file, "Expression", &expr_hash_table);
if (expr_hash_table.n_elems > 0)
{
compute_kill_rd ();
compute_rd ();
alloc_avail_expr_mem (last_basic_block, expr_hash_table.n_elems);
compute_ae_gen (&expr_hash_table);
compute_ae_kill (ae_gen, ae_kill, &expr_hash_table);
compute_available (ae_gen, ae_kill, ae_out, ae_in);
changed = classic_gcse ();
free_avail_expr_mem ();
}
free_rd_mem ();
free_hash_table (&expr_hash_table);
if (gcse_file)
{
fprintf (gcse_file, "\n");
fprintf (gcse_file, "GCSE of %s, pass %d: %d bytes needed, %d substs,",
current_function_name, pass, bytes_used, gcse_subst_count);
fprintf (gcse_file, "%d insns created\n", gcse_create_count);
}
return changed;
}
static sbitmap *cprop_pavloc;
static sbitmap *cprop_absaltered;
static sbitmap *cprop_avin;
static sbitmap *cprop_avout;
static void
alloc_cprop_mem (n_blocks, n_sets)
int n_blocks, 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 ()
{
sbitmap_vector_free (cprop_pavloc);
sbitmap_vector_free (cprop_absaltered);
sbitmap_vector_free (cprop_avin);
sbitmap_vector_free (cprop_avout);
}
static void
compute_transp (x, indx, bmap, set_p)
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[BLOCK_NUM (r->insn)], 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[BLOCK_NUM (r->insn)], indx);
}
}
return;
case MEM:
FOR_EACH_BB (bb)
{
rtx list_entry = canon_modify_mem_list[bb->index];
while (list_entry)
{
rtx dest, dest_addr;
if (GET_CODE (XEXP (list_entry, 0)) == CALL_INSN)
{
if (set_p)
SET_BIT (bmap[bb->index], indx);
else
RESET_BIT (bmap[bb->index], indx);
break;
}
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 ()
{
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 (xptr, data)
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 (from, to, insn)
rtx from, to, insn;
{
rtx note = find_reg_equal_equiv_note (insn);
rtx src = 0;
int success = 0;
rtx set = single_set (insn);
#ifdef MAGIC_INDIRECT_CALL_REG
if ( GET_CODE (from) == REG && REGNO (from) < FIRST_PSEUDO_REGISTER
&& GET_CODE (to) == REG && REGNO (to) >= FIRST_PSEUDO_REGISTER)
return 0;
#endif
validate_replace_src_group (from, to, insn);
if (num_changes_pending () && apply_change_group ())
success = 1;
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 (XEXP (set, 0)) != ZERO_EXTRACT
&& GET_CODE (XEXP (set, 0)) != SIGN_EXTRACT)
note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
}
else if (note != 0)
XEXP (note, 0) = simplify_replace_rtx (XEXP (note, 0), from, to);
if (note && REG_P (XEXP (note, 0)))
remove_note (insn, note);
return success;
}
static struct expr *
find_avail_set (regno, insn)
int regno;
rtx insn;
{
struct expr *set1 = 0;
while (1)
{
rtx src;
struct expr *set = lookup_set (regno, NULL_RTX, &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;
if (GET_CODE (set->expr) != SET)
abort ();
src = SET_SRC (set->expr);
if (CONSTANT_P (src) || oprs_not_set_p (src, insn))
set1 = set;
if (GET_CODE (src) != REG)
break;
regno = REGNO (src);
}
return set1;
}
static int
cprop_jump (bb, setcc, jump, from, src)
basic_block bb;
rtx setcc;
rtx jump;
rtx from;
rtx src;
{
rtx new, new_set;
rtx set = pc_set (jump);
if (setcc != NULL
&& !modified_between_p (from, setcc, jump)
&& !modified_between_p (src, setcc, jump))
{
rtx setcc_set = single_set (setcc);
new_set = simplify_replace_rtx (SET_SRC (set),
SET_DEST (setcc_set),
SET_SRC (setcc_set));
}
else
new_set = set;
new = simplify_replace_rtx (new_set, from, src);
if (rtx_equal_p (new, new_set) || 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))
return 0;
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;
const_prop_count++;
if (gcse_file != NULL)
{
fprintf (gcse_file,
"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 (insn, from, to, alter_jumps)
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 (GET_CODE (insn) == 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 (insn, alter_jumps)
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;
if (GET_CODE (pat) != SET)
abort ();
src = SET_SRC (pat);
if (CONSTANT_P (src))
{
if (constprop_register (insn, reg_used->reg_rtx, src, alter_jumps))
{
changed = 1;
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 ( 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 (GET_CODE (src) == REG
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
&& REGNO (src) != regno)
{
if (try_replace_reg (reg_used->reg_rtx, src, insn))
{
changed = 1;
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 (xptr, data)
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 (x, insn, alter_jumps, libcall_sp)
rtx x;
rtx insn;
int alter_jumps;
rtx *libcall_sp;
{
rtx newreg = NULL, newcnst = NULL;
if (GET_CODE (x) == REG
&& (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)
continue;
if (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))
|| GET_CODE (XEXP (note, 0)) != MEM))
newreg = this_rtx;
}
if (newcnst && constprop_register (insn, x, newcnst, alter_jumps))
{
if (!adjust_libcall_notes (x, newcnst, insn, libcall_sp))
abort ();
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");
}
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));
}
copy_prop_count++;
return true;
}
}
return false;
}
static bool
adjust_libcall_notes (oldreg, newval, insn, libcall_sp)
rtx oldreg, newval, insn, *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) = replace_rtx (XEXP (note, 0), oldreg, newval);
insn = end;
}
return true;
}
#define MAX_NESTED_LIBCALLS 9
static void
local_cprop_pass (alter_jumps)
int alter_jumps;
{
rtx insn;
struct reg_use *reg_used;
rtx libcall_stack[MAX_NESTED_LIBCALLS + 1], *libcall_sp;
bool changed = false;
cselib_init ();
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)
{
if (libcall_sp == libcall_stack)
abort ();
*--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;
}
}
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 (alter_jumps)
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;
insn != NULL && insn != NEXT_INSN (bb->end);
insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
changed |= cprop_insn (insn, alter_jumps);
if (GET_CODE (insn) != NOTE)
mark_oprs_set (insn);
}
}
if (gcse_file != NULL)
fprintf (gcse_file, "\n");
return changed;
}
static int
one_cprop_pass (pass, alter_jumps)
int pass;
int alter_jumps;
{
int changed = 0;
const_prop_count = 0;
copy_prop_count = 0;
local_cprop_pass (alter_jumps);
alloc_hash_table (max_cuid, &set_hash_table, 1);
compute_hash_table (&set_hash_table);
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 (alter_jumps);
if (alter_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 const props, %d copy props\n\n",
const_prop_count, copy_prop_count);
}
if (changed && alter_jumps)
delete_unreachable_blocks ();
return changed;
}
static struct expr *
find_bypass_set (regno, bb)
int regno;
int bb;
{
struct expr *result = 0;
for (;;)
{
rtx src;
struct expr *set = lookup_set (regno, NULL_RTX, &set_hash_table);
while (set)
{
if (TEST_BIT (cprop_avout[bb], set->bitmap_index))
break;
set = next_set (regno, set);
}
if (set == 0)
break;
if (GET_CODE (set->expr) != SET)
abort ();
src = SET_SRC (set->expr);
if (CONSTANT_P (src))
result = set;
if (GET_CODE (src) != REG)
break;
regno = REGNO (src);
}
return result;
}
static int
bypass_block (bb, setcc, jump)
basic_block bb;
rtx setcc, jump;
{
rtx insn, note;
edge e, enext;
int i, change;
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);
change = 0;
for (e = bb->pred; e; e = enext)
{
enext = e->pred_next;
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;
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)
dest = FALLTHRU_EDGE (bb)->dest;
else if (GET_CODE (new) == LABEL_REF)
dest = BRANCH_EDGE (bb)->dest;
else
dest = NULL;
old_dest = e->dest;
if (dest != NULL && dest != old_dest
&& redirect_edge_and_branch (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;
break;
}
}
}
return change;
}
static int
bypass_conditional_jumps ()
{
basic_block bb;
int changed;
rtx setcc;
rtx insn;
rtx dest;
if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
return 0;
changed = 0;
FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb,
EXIT_BLOCK_PTR, next_bb)
{
if (bb->pred && bb->pred->pred_next)
{
setcc = NULL_RTX;
for (insn = bb->head;
insn != NULL && insn != NEXT_INSN (bb->end);
insn = NEXT_INSN (insn))
if (GET_CODE (insn) == 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 (GET_CODE (insn) == JUMP_INSN)
{
if (any_condjump_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 (n_blocks, n_exprs)
int n_blocks, 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_in = NULL;
ae_out = NULL;
ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs);
}
static void
free_pre_mem ()
{
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);
if (ae_in)
sbitmap_vector_free (ae_in);
if (ae_out)
sbitmap_vector_free (ae_out);
transp = comp = NULL;
pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL;
ae_in = ae_out = NULL;
}
static void
compute_pre_data ()
{
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;
for (e = bb->pred; e ; e = e->pred_next)
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 (occr_bb, expr, bb, visited)
basic_block occr_bb;
struct expr *expr;
basic_block bb;
char *visited;
{
edge pred;
for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
{
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 (occr_bb, expr, bb)
basic_block occr_bb;
struct expr *expr;
basic_block bb;
{
int rval;
char *visited = (char *) 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 (expr)
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 if (insn_invalid_p (emit_insn (gen_rtx_SET (VOIDmode, reg, exp))))
abort ();
pat = get_insns ();
end_sequence ();
return pat;
}
static void
insert_insn_end_bb (expr, bb, pre)
struct expr *expr;
basic_block bb;
int pre;
{
rtx insn = bb->end;
rtx new_insn;
rtx reg = expr->reaching_reg;
int regno = REGNO (reg);
rtx pat, pat_end;
pat = process_insert_insn (expr);
if (pat == NULL_RTX || ! INSN_P (pat))
abort ();
pat_end = pat;
while (NEXT_INSN (pat_end) != NULL_RTX)
pat_end = NEXT_INSN (pat_end);
if (GET_CODE (insn) == JUMP_INSN
|| (GET_CODE (insn) == INSN
&& (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL))))
{
#ifdef HAVE_cc0
rtx note;
#endif
if (GET_CODE (insn) == INSN && pre
&& !TEST_BIT (antloc[bb->index], expr->bitmap_index)
&& !TEST_BIT (transp[bb->index], expr->bitmap_index))
abort ();
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 (pat, insn);
}
else if (GET_CODE (insn) == CALL_INSN
&& (bb->succ->succ_next || (bb->succ->flags & EDGE_ABNORMAL)))
{
if (pre
&& !TEST_BIT (antloc[bb->index], expr->bitmap_index)
&& !TEST_BIT (transp[bb->index], expr->bitmap_index))
abort ();
insn = find_first_parameter_load (insn, bb->head);
while (GET_CODE (insn) == CODE_LABEL
|| NOTE_INSN_BASIC_BLOCK_P (insn))
insn = NEXT_INSN (insn);
new_insn = emit_insn_before (pat, insn);
}
else
new_insn = emit_insn_after (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 (edge_list, index_map)
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) == 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 (expr, insn)
struct expr *expr;
rtx insn;
{
rtx reg = expr->reaching_reg;
int regno = REGNO (reg);
int indx = expr->bitmap_index;
rtx set = single_set (insn);
rtx new_insn;
if (!set)
abort ();
new_insn = emit_insn_after (gen_move_insn (reg, SET_DEST (set)), 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);
update_ld_motion_stores (expr);
}
static void
pre_insert_copies ()
{
unsigned int i;
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;
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;
pre_insert_copy_insn (expr, insn);
avail->copied_p = 1;
}
}
}
}
static rtx
gcse_emit_move_after (src, dest, insn)
rtx src, dest, 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 ()
{
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);
if (! set)
abort ();
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 ()
{
unsigned int i;
int did_insert, changed;
struct expr **index_map;
struct expr *expr;
index_map = (struct expr **) 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 (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_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 (x, insn)
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 ()
{
basic_block bb;
unsigned int i;
struct expr *expr;
sbitmap_vector_ones (transpout, last_basic_block);
FOR_EACH_BB (bb)
{
if (GET_CODE (bb->end) != CALL_INSN)
continue;
for (i = 0; i < expr_hash_table.size; i++)
for (expr = expr_hash_table.table[i]; expr ; expr = expr->next_same_hash)
if (GET_CODE (expr->expr) == MEM)
{
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 void
invalidate_nonnull_info (x, setter, data)
rtx x;
rtx setter ATTRIBUTE_UNUSED;
void *data;
{
unsigned int regno;
struct null_pointer_info *npi = (struct null_pointer_info *) data;
while (GET_CODE (x) == SUBREG)
x = SUBREG_REG (x);
if (GET_CODE (x) != REG
|| REGNO (x) < npi->min_reg
|| REGNO (x) >= npi->max_reg)
return;
regno = REGNO (x) - npi->min_reg;
RESET_BIT (npi->nonnull_local[npi->current_block->index], regno);
SET_BIT (npi->nonnull_killed[npi->current_block->index], regno);
}
static int
delete_null_pointer_checks_1 (block_reg, nonnull_avin,
nonnull_avout, npi)
unsigned int *block_reg;
sbitmap *nonnull_avin;
sbitmap *nonnull_avout;
struct null_pointer_info *npi;
{
basic_block bb, current_block;
sbitmap *nonnull_local = npi->nonnull_local;
sbitmap *nonnull_killed = npi->nonnull_killed;
int something_changed = 0;
sbitmap_vector_zero (nonnull_local, last_basic_block);
sbitmap_vector_zero (nonnull_killed, last_basic_block);
FOR_EACH_BB (current_block)
{
rtx insn, stop_insn;
npi->current_block = current_block;
stop_insn = NEXT_INSN (current_block->end);
for (insn = current_block->head;
insn != stop_insn;
insn = NEXT_INSN (insn))
{
rtx set;
rtx reg;
if (! INSN_P (insn))
continue;
set = single_set (insn);
if (!set)
{
note_stores (PATTERN (insn), invalidate_nonnull_info, npi);
continue;
}
if (GET_CODE (SET_SRC (set)) == MEM
&& GET_CODE ((reg = XEXP (SET_SRC (set), 0))) == REG
&& REGNO (reg) >= npi->min_reg
&& REGNO (reg) < npi->max_reg)
SET_BIT (nonnull_local[current_block->index],
REGNO (reg) - npi->min_reg);
note_stores (PATTERN (insn), invalidate_nonnull_info, npi);
if (GET_CODE (SET_DEST (set)) == MEM
&& GET_CODE ((reg = XEXP (SET_DEST (set), 0))) == REG
&& REGNO (reg) >= npi->min_reg
&& REGNO (reg) < npi->max_reg)
SET_BIT (nonnull_local[current_block->index],
REGNO (reg) - npi->min_reg);
}
}
compute_available (nonnull_local, nonnull_killed,
nonnull_avout, nonnull_avin);
FOR_EACH_BB (bb)
{
rtx last_insn = bb->end;
rtx condition, earliest;
int compare_and_branch;
if (block_reg[bb->index] < npi->min_reg
|| block_reg[bb->index] >= npi->max_reg)
continue;
condition = get_condition (last_insn, &earliest);
if (! condition)
continue;
if (!TEST_BIT (nonnull_avout[bb->index], block_reg[bb->index] - npi->min_reg))
continue;
if (earliest == last_insn)
compare_and_branch = 1;
else if (earliest == prev_nonnote_insn (last_insn))
compare_and_branch = 2;
else
continue;
if (GET_CODE (condition) == NE)
{
rtx new_jump;
new_jump = emit_jump_insn_after (gen_jump (JUMP_LABEL (last_insn)),
last_insn);
JUMP_LABEL (new_jump) = JUMP_LABEL (last_insn);
LABEL_NUSES (JUMP_LABEL (new_jump))++;
emit_barrier_after (new_jump);
}
something_changed = 1;
delete_insn (last_insn);
#if 0
if (compare_and_branch == 2)
delete_insn (earliest);
#endif
purge_dead_edges (bb);
block_reg[bb->index] = 0;
}
return something_changed;
}
int
delete_null_pointer_checks (f)
rtx f ATTRIBUTE_UNUSED;
{
sbitmap *nonnull_avin, *nonnull_avout;
unsigned int *block_reg;
basic_block bb;
int reg;
int regs_per_pass;
int max_reg;
struct null_pointer_info npi;
int something_changed = 0;
if (n_basic_blocks <= 1)
return 0;
if (n_basic_blocks > 1000 && n_edges / n_basic_blocks >= 20)
return 0;
max_reg = max_reg_num ();
regs_per_pass = get_bitmap_width (4, last_basic_block, max_reg);
npi.nonnull_local = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
npi.nonnull_killed = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
nonnull_avin = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
nonnull_avout = sbitmap_vector_alloc (last_basic_block, regs_per_pass);
block_reg = (unsigned int *) xcalloc (last_basic_block, sizeof (int));
FOR_EACH_BB (bb)
{
rtx last_insn = bb->end;
rtx condition, earliest, reg;
if (GET_CODE (last_insn) != JUMP_INSN
|| !any_condjump_p (last_insn)
|| !onlyjump_p (last_insn))
continue;
condition = get_condition (last_insn, &earliest);
if (!condition
|| (GET_CODE (condition) != NE && GET_CODE (condition) != EQ)
|| GET_CODE (XEXP (condition, 1)) != CONST_INT
|| (XEXP (condition, 1)
!= CONST0_RTX (GET_MODE (XEXP (condition, 0)))))
continue;
reg = XEXP (condition, 0);
if (GET_CODE (reg) != REG)
continue;
block_reg[bb->index] = REGNO (reg);
}
for (reg = FIRST_PSEUDO_REGISTER; reg < max_reg; reg += regs_per_pass)
{
npi.min_reg = reg;
npi.max_reg = MIN (reg + regs_per_pass, max_reg);
something_changed |= delete_null_pointer_checks_1 (block_reg,
nonnull_avin,
nonnull_avout,
&npi);
}
free (block_reg);
sbitmap_vector_free (npi.nonnull_local);
sbitmap_vector_free (npi.nonnull_killed);
sbitmap_vector_free (nonnull_avin);
sbitmap_vector_free (nonnull_avout);
return something_changed;
}
static sbitmap *hoist_vbein;
static sbitmap *hoist_vbeout;
static sbitmap *hoist_exprs;
dominance_info dominators;
static void
alloc_code_hoist_mem (n_blocks, n_exprs)
int n_blocks, 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 ()
{
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 (dominators);
}
static void
compute_code_hoist_vbeinout ()
{
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 ()
{
compute_local_properties (transp, comp, antloc, &expr_hash_table);
compute_transpout ();
compute_code_hoist_vbeinout ();
dominators = calculate_dominance_info (CDI_DOMINATORS);
if (gcse_file)
fprintf (gcse_file, "\n");
}
static int
hoist_expr_reaches_here_p (expr_bb, expr_index, bb, visited)
basic_block expr_bb;
int expr_index;
basic_block bb;
char *visited;
{
edge pred;
int visited_allocated_locally = 0;
if (visited == NULL)
{
visited_allocated_locally = 1;
visited = xcalloc (last_basic_block, 1);
}
for (pred = bb->pred; pred != NULL; pred = pred->pred_next)
{
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 ()
{
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 = (struct expr **) 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 (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;
if (!occr)
abort ();
insn = occr->insn;
set = single_set (insn);
if (! set)
abort ();
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 ()
{
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 (x)
rtx x;
{
struct ls_expr * ptr;
for (ptr = first_ls_expr(); ptr != NULL; ptr = next_ls_expr (ptr))
if (expr_equiv_p (ptr->pattern, x))
break;
if (!ptr)
{
ptr = (struct ls_expr *) xmalloc (sizeof (struct ls_expr));
ptr->next = pre_ldst_mems;
ptr->expr = NULL;
ptr->pattern = x;
ptr->loads = NULL_RTX;
ptr->stores = NULL_RTX;
ptr->reaching_reg = NULL_RTX;
ptr->invalid = 0;
ptr->index = 0;
ptr->hash_index = 0;
pre_ldst_mems = ptr;
}
return ptr;
}
static void
free_ldst_entry (ptr)
struct ls_expr * ptr;
{
free_INSN_LIST_list (& ptr->loads);
free_INSN_LIST_list (& ptr->stores);
free (ptr);
}
static void
free_ldst_mems ()
{
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 * 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 (x)
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 ()
{
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 ()
{
return pre_ldst_mems;
}
static inline struct ls_expr *
next_ls_expr (ptr)
struct ls_expr * ptr;
{
return ptr->next;
}
static int
simple_mem (x)
rtx x;
{
if (GET_CODE (x) != MEM)
return 0;
if (MEM_VOLATILE_P (x))
return 0;
if (GET_MODE (x) == BLKmode)
return 0;
if (!rtx_varies_p (XEXP (x, 0), 0))
return 1;
if (flag_float_store && FLOAT_MODE_P (GET_MODE (x)))
return 0;
return 0;
}
static void
invalidate_any_buried_refs (x)
rtx x;
{
const char * fmt;
int i, j;
struct ls_expr * ptr;
if (GET_CODE (x) == MEM && 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 ()
{
struct ls_expr * ptr;
basic_block bb;
rtx insn;
pre_ldst_mems = NULL;
FOR_EACH_BB (bb)
{
for (insn = bb->head;
insn && insn != NEXT_INSN (bb->end);
insn = NEXT_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
if (GET_CODE (PATTERN (insn)) == SET)
{
rtx src = SET_SRC (PATTERN (insn));
rtx dest = SET_DEST (PATTERN (insn));
if (GET_CODE (src) == MEM && simple_mem (src))
{
ptr = ldst_entry (src);
if (GET_CODE (dest) == REG)
ptr->loads = alloc_INSN_LIST (insn, ptr->loads);
else
ptr->invalid = 1;
}
else
{
invalidate_any_buried_refs (src);
}
if (GET_CODE (dest) == MEM && simple_mem (dest))
{
ptr = ldst_entry (dest);
if (GET_CODE (src) != MEM
&& GET_CODE (src) != ASM_OPERANDS)
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 ()
{
struct ls_expr * last = NULL;
struct ls_expr * ptr = first_ls_expr ();
while (ptr != NULL)
{
int del = ptr->invalid;
struct expr * expr = NULL;
if (!del)
{
unsigned int i;
del = 1;
for (i = 0; i < expr_hash_table.size && del; i++)
{
for (expr = expr_hash_table.table[i];
expr != NULL;
expr = expr->next_same_hash)
if (expr_equiv_p (expr->expr, ptr->pattern))
{
del = 0;
break;
}
}
}
if (del)
{
if (last != NULL)
{
last->next = ptr->next;
free_ldst_entry (ptr);
ptr = last->next;
}
else
{
pre_ldst_mems = pre_ldst_mems->next;
free_ldst_entry (ptr);
ptr = pre_ldst_mems;
}
}
else
{
last = ptr;
ptr->expr = expr;
ptr = ptr->next;
}
}
if (gcse_file && pre_ldst_mems != NULL)
print_ldst_list (gcse_file);
}
static void
update_ld_motion_stores (expr)
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, 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++;
}
}
}
static sbitmap * regvec;
static sbitmap * st_antloc;
static int num_stores;
static void
reg_set_info (dest, setter, data)
rtx dest, setter ATTRIBUTE_UNUSED;
void * data ATTRIBUTE_UNUSED;
{
if (GET_CODE (dest) == SUBREG)
dest = SUBREG_REG (dest);
if (GET_CODE (dest) == REG)
SET_BIT (*regvec, REGNO (dest));
}
static int
store_ops_ok (x, bb)
rtx x;
basic_block bb;
{
int i;
enum rtx_code code;
const char * fmt;
repeat:
if (x == 0)
return 1;
code = GET_CODE (x);
switch (code)
{
case REG:
return TEST_BIT (reg_set_in_block[bb->index], REGNO (x));
case MEM:
x = XEXP (x, 0);
goto repeat;
case PRE_DEC:
case PRE_INC:
case POST_DEC:
case POST_INC:
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;
}
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;
}
if (! store_ops_ok (tem, bb))
return 0;
}
else if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
{
if (! store_ops_ok (XVECEXP (x, i, j), bb))
return 0;
}
}
}
return 1;
}
static void
find_moveable_store (insn)
rtx insn;
{
struct ls_expr * ptr;
rtx dest = PATTERN (insn);
if (GET_CODE (dest) != SET
|| GET_CODE (SET_SRC (dest)) == ASM_OPERANDS)
return;
dest = SET_DEST (dest);
if (GET_CODE (dest) != MEM || MEM_VOLATILE_P (dest)
|| GET_MODE (dest) == BLKmode)
return;
if (GET_CODE (XEXP (dest, 0)) != SYMBOL_REF)
return;
if (rtx_varies_p (XEXP (dest, 0), 0))
return;
ptr = ldst_entry (dest);
ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
}
static int
compute_store_table ()
{
int ret;
basic_block bb;
unsigned regno;
rtx insn, pat;
max_gcse_regno = max_reg_num ();
reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (last_basic_block,
max_gcse_regno);
sbitmap_vector_zero (reg_set_in_block, last_basic_block);
pre_ldst_mems = 0;
FOR_EACH_BB (bb)
{
regvec = & (reg_set_in_block[bb->index]);
for (insn = bb->end;
insn && insn != PREV_INSN (bb->end);
insn = PREV_INSN (insn))
{
if (! INSN_P (insn))
continue;
if (GET_CODE (insn) == CALL_INSN)
{
bool clobbers_all = false;
#ifdef NON_SAVING_SETJMP
if (NON_SAVING_SETJMP
&& find_reg_note (insn, REG_SETJMP, NULL_RTX))
clobbers_all = true;
#endif
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
if (clobbers_all
|| TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
SET_BIT (reg_set_in_block[bb->index], regno);
}
pat = PATTERN (insn);
note_stores (pat, reg_set_info, NULL);
if (GET_CODE (pat) == SET)
find_moveable_store (insn);
}
}
ret = enumerate_ldsts ();
if (gcse_file)
{
fprintf (gcse_file, "Store Motion Expressions.\n");
print_ldst_list (gcse_file);
}
return ret;
}
static int
load_kills_store (x, store_pattern)
rtx x, store_pattern;
{
if (true_dependence (x, GET_MODE (x), store_pattern, rtx_addr_varies_p))
return 1;
return 0;
}
static int
find_loads (x, store_pattern)
rtx x, store_pattern;
{
const char * fmt;
int i, j;
int ret = 0;
if (!x)
return 0;
if (GET_CODE (x) == SET)
x = SET_SRC (x);
if (GET_CODE (x) == MEM)
{
if (load_kills_store (x, store_pattern))
return 1;
}
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);
else if (fmt[i] == 'E')
for (j = XVECLEN (x, i) - 1; j >= 0; j--)
ret |= find_loads (XVECEXP (x, i, j), store_pattern);
}
return ret;
}
static int
store_killed_in_insn (x, insn)
rtx x, insn;
{
if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
return 0;
if (GET_CODE (insn) == CALL_INSN)
{
return ! CONST_OR_PURE_CALL_P (insn) || pure_call_p (insn);
}
if (GET_CODE (PATTERN (insn)) == SET)
{
rtx pat = PATTERN (insn);
if (GET_CODE (SET_DEST (pat)) == MEM && !expr_equiv_p (SET_DEST (pat), x))
if (find_loads (SET_DEST (pat), x))
return 1;
return find_loads (SET_SRC (pat), x);
}
else
return find_loads (PATTERN (insn), x);
}
static int
store_killed_after (x, insn, bb)
rtx x, insn;
basic_block bb;
{
rtx last = bb->end;
if (insn == last)
return 0;
if (!store_ops_ok (XEXP (x, 0), bb))
return 1;
for ( ; insn && insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
if (store_killed_in_insn (x, insn))
return 1;
return 0;
}
static int
store_killed_before (x, insn, bb)
rtx x, insn;
basic_block bb;
{
rtx first = bb->head;
if (insn == first)
return store_killed_in_insn (x, insn);
if (!store_ops_ok (XEXP (x, 0), bb))
return 1;
for ( ; insn && insn != PREV_INSN (first); insn = PREV_INSN (insn))
if (store_killed_in_insn (x, insn))
return 1;
return 0;
}
#define ANTIC_STORE_LIST(x) ((x)->loads)
#define AVAIL_STORE_LIST(x) ((x)->stores)
static void
build_store_vectors ()
{
basic_block bb, b;
rtx insn, st;
struct ls_expr * ptr;
ae_gen = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
sbitmap_vector_zero (ae_gen, last_basic_block);
st_antloc = (sbitmap *) 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))
{
rtx store_list = ptr->stores;
ptr->stores = NULL_RTX;
for (st = store_list; st != NULL; st = XEXP (st, 1))
{
insn = XEXP (st, 0);
bb = BLOCK_FOR_INSN (insn);
if (!store_killed_after (ptr->pattern, insn, bb))
{
if (TEST_BIT (ae_gen[bb->index], ptr->index))
{
rtx st;
for (st = AVAIL_STORE_LIST (ptr); st ; st = XEXP (st, 1))
if (BLOCK_FOR_INSN (XEXP (st, 0)) == bb)
break;
if (st)
{
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);
XEXP (st, 0) = insn;
continue;
}
}
SET_BIT (ae_gen[bb->index], ptr->index);
AVAIL_STORE_LIST (ptr) = alloc_INSN_LIST (insn,
AVAIL_STORE_LIST (ptr));
}
if (!store_killed_before (ptr->pattern, insn, bb))
{
SET_BIT (st_antloc[BLOCK_NUM (insn)], ptr->index);
ANTIC_STORE_LIST (ptr) = alloc_INSN_LIST (insn,
ANTIC_STORE_LIST (ptr));
}
}
free_INSN_LIST_list (&store_list);
}
ae_kill = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
sbitmap_vector_zero (ae_kill, last_basic_block);
transp = (sbitmap *) sbitmap_vector_alloc (last_basic_block, num_stores);
sbitmap_vector_zero (transp, last_basic_block);
for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
FOR_EACH_BB (b)
{
if (store_killed_after (ptr->pattern, b->head, b))
{
SET_BIT (ae_kill[b->index], ptr->index);
}
else
SET_BIT (transp[b->index], ptr->index);
}
if (gcse_file)
{
fprintf (gcse_file, "ST_avail and ST_antic (shown under loads..)\n");
print_ldst_list (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 (insn, bb)
rtx insn;
basic_block bb;
{
rtx prev = PREV_INSN (bb->head);
rtx before = bb->head;
while (before != 0)
{
if (GET_CODE (before) != CODE_LABEL
&& (GET_CODE (before) != NOTE
|| NOTE_LINE_NUMBER (before) != NOTE_INSN_BASIC_BLOCK))
break;
prev = before;
if (prev == bb->end)
break;
before = NEXT_INSN (before);
}
insn = emit_insn_after (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 (expr, e)
struct ls_expr * expr;
edge e;
{
rtx reg, insn;
basic_block bb;
edge tmp;
if (expr->reaching_reg == NULL_RTX)
return 0;
reg = expr->reaching_reg;
insn = gen_move_insn (expr->pattern, reg);
bb = e->dest;
for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next)
{
int index = EDGE_INDEX (edge_list, tmp->src, tmp->dest);
if (index == EDGE_INDEX_NO_EDGE)
abort ();
if (! TEST_BIT (pre_insert_map[index], expr->index))
break;
}
if (!tmp && bb != EXIT_BLOCK_PTR)
{
for (tmp = e->dest->pred; tmp ; tmp = tmp->pred_next)
{
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;
}
if ((e->flags & EDGE_ABNORMAL) == EDGE_ABNORMAL)
{
insert_insn_start_bb (insn, bb);
return 0;
}
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
replace_store_insn (reg, del, bb)
rtx reg, del;
basic_block bb;
{
rtx insn;
insn = gen_move_insn (reg, SET_SRC (PATTERN (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");
}
delete_insn (del);
}
static void
delete_store (expr, bb)
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);
break;
}
}
}
static void
free_store_memory ()
{
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 ()
{
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;
}
add_noreturn_fake_exit_edges ();
build_store_vectors ();
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_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_edges ();
end_alias_analysis ();
}
#include "gt-gcse.h"