#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 "obstack.h"
#define obstack_chunk_alloc gmalloc
#define obstack_chunk_free free
#define FOLLOW_BACK_EDGES 1
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;
};
static unsigned int expr_hash_table_size;
static struct expr **expr_hash_table;
static unsigned int set_hash_table_size;
static struct expr **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;
static int n_exprs;
static int n_sets;
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
{
int 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, int, int));
static void hash_scan_set PARAMS ((rtx, rtx, int));
static void hash_scan_clobber PARAMS ((rtx, rtx));
static void hash_scan_call PARAMS ((rtx, rtx));
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));
static void insert_set_in_table PARAMS ((rtx, rtx));
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 ((int));
static void alloc_set_hash_table PARAMS ((int));
static void free_set_hash_table PARAMS ((void));
static void compute_set_hash_table PARAMS ((void));
static void alloc_expr_hash_table PARAMS ((unsigned int));
static void free_expr_hash_table PARAMS ((void));
static void compute_expr_hash_table PARAMS ((void));
static void dump_hash_table PARAMS ((FILE *, const char *, struct expr **,
int, int));
static struct expr *lookup_expr PARAMS ((rtx));
static struct expr *lookup_set PARAMS ((unsigned int, rtx));
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 *,
int));
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));
#ifdef HAVE_cc0
static int cprop_cc0_jump PARAMS ((basic_block, rtx, struct reg_use *, rtx));
#endif
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 ((basic_block, rtx, int));
static int cprop PARAMS ((int));
static int one_cprop_pass PARAMS ((int, int));
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 ((void));
static int expr_killed_p PARAMS ((rtx, basic_block));
static void compute_ae_kill PARAMS ((sbitmap *, sbitmap *));
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 void 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 clear_modify_mem_tables PARAMS ((void));
static void free_modify_mem_tables PARAMS ((void));
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);
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 (n_basic_blocks * sizeof (rtx));
canon_modify_mem_list
= (rtx *) gmalloc (n_basic_blocks * sizeof (rtx));
memset ((char *) modify_mem_list, 0, n_basic_blocks * sizeof (rtx));
memset ((char *) canon_modify_mem_list, 0, n_basic_blocks * 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;
{
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 (n_basic_blocks,
max_gcse_regno);
modify_mem_list = (rtx *) gmalloc (n_basic_blocks * sizeof (rtx));
canon_modify_mem_list = (rtx *) gmalloc (n_basic_blocks * sizeof (rtx));
memset ((char *) modify_mem_list, 0, n_basic_blocks * sizeof (rtx));
memset ((char *) canon_modify_mem_list, 0, n_basic_blocks * 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, setp)
sbitmap *transp;
sbitmap *comp;
sbitmap *antloc;
int setp;
{
unsigned int i, hash_table_size;
struct expr **hash_table;
if (transp)
{
if (setp)
sbitmap_vector_zero (transp, n_basic_blocks);
else
sbitmap_vector_ones (transp, n_basic_blocks);
}
if (comp)
sbitmap_vector_zero (comp, n_basic_blocks);
if (antloc)
sbitmap_vector_zero (antloc, n_basic_blocks);
hash_table_size = setp ? set_hash_table_size : expr_hash_table_size;
hash_table = setp ? set_hash_table : expr_hash_table;
for (i = 0; i < hash_table_size; i++)
{
struct expr *expr;
for (expr = hash_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, setp);
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);
}
#define NEVER_SET -1
struct reg_avail_info
{
int last_bb;
int first_set;
int last_set;
};
static struct reg_avail_info *reg_avail_info;
static int current_bb;
static int
want_to_gcse_p (x)
rtx x;
{
static rtx test_insn = 0;
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;
ggc_add_rtx_root (&test_insn, 1);
}
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 (BASIC_BLOCK (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 (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;
hash += MEM_ALIAS_SET (x);
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)
rtx x;
enum machine_mode mode;
rtx insn;
int antic_p, avail_p;
{
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, expr_hash_table_size);
if (do_not_record_p)
return;
cur_expr = expr_hash_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 (expr_hash_table[hash] == NULL)
expr_hash_table[hash] = cur_expr;
else
last_expr->next_same_hash = cur_expr;
cur_expr->expr = x;
cur_expr->bitmap_index = n_exprs++;
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)
rtx x;
rtx insn;
{
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)), set_hash_table_size);
cur_expr = set_hash_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 (set_hash_table[hash] == NULL)
set_hash_table[hash] = cur_expr;
else
last_expr->next_same_hash = cur_expr;
cur_expr->expr = copy_rtx (x);
cur_expr->bitmap_index = n_sets++;
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, set_p)
rtx pat, insn;
int set_p;
{
rtx src = SET_SRC (pat);
rtx dest = SET_DEST (pat);
rtx note;
if (GET_CODE (src) == CALL)
hash_scan_call (src, insn);
else if (GET_CODE (dest) == REG)
{
unsigned int regno = REGNO (dest);
rtx tmp;
if (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 (! set_p
&& regno >= FIRST_PSEUDO_REGISTER
&& can_copy_p [GET_MODE (dest)]
&& !can_throw_internal (insn)
&& want_to_gcse_p (src)
&& ! set_noop_p (pat)
&& ((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);
}
else if (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);
}
}
static void
hash_scan_clobber (x, insn)
rtx x ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
{
}
static void
hash_scan_call (x, insn)
rtx x ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
{
}
static void
hash_scan_insn (insn, set_p, in_libcall_block)
rtx insn;
int set_p;
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, set_p);
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, set_p);
else if (GET_CODE (x) == CLOBBER)
hash_scan_clobber (x, insn);
else if (GET_CODE (x) == CALL)
hash_scan_call (x, insn);
}
else if (GET_CODE (pat) == CLOBBER)
hash_scan_clobber (pat, insn);
else if (GET_CODE (pat) == CALL)
hash_scan_call (pat, insn);
}
static void
dump_hash_table (file, name, table, table_size, total_size)
FILE *file;
const char *name;
struct expr **table;
int table_size, total_size;
{
int i;
struct expr **flat_table;
unsigned int *hash_val;
struct expr *expr;
flat_table
= (struct expr **) xcalloc (total_size, sizeof (struct expr *));
hash_val = (unsigned int *) xmalloc (total_size * sizeof (unsigned int));
for (i = 0; i < table_size; i++)
for (expr = 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, total_size);
for (i = 0; i < total_size; 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], 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;
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;
canon_modify_mem_list[BLOCK_NUM (insn)] =
alloc_INSN_LIST (dest_addr, canon_modify_mem_list[BLOCK_NUM (insn)]);
canon_modify_mem_list[BLOCK_NUM (insn)] =
alloc_INSN_LIST (dest, canon_modify_mem_list[BLOCK_NUM (insn)]);
bitmap_set_bit (canon_modify_mem_list_set, BLOCK_NUM (insn));
}
static void
record_last_mem_set_info (insn)
rtx insn;
{
modify_mem_list[BLOCK_NUM (insn)] =
alloc_INSN_LIST (insn, modify_mem_list[BLOCK_NUM (insn)]);
bitmap_set_bit (modify_mem_list_set, BLOCK_NUM (insn));
if (GET_CODE (insn) == CALL_INSN)
{
canon_modify_mem_list[BLOCK_NUM (insn)] =
alloc_INSN_LIST (insn, canon_modify_mem_list[BLOCK_NUM (insn)]);
bitmap_set_bit (canon_modify_mem_list_set, BLOCK_NUM (insn));
}
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 (set_p)
int set_p;
{
unsigned int i;
sbitmap_vector_zero (reg_set_in_block, n_basic_blocks);
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 = NEVER_SET;
for (current_bb = 0; current_bb < n_basic_blocks; current_bb++)
{
rtx insn;
unsigned int regno;
int in_libcall_block;
for (insn = BLOCK_HEAD (current_bb);
insn && insn != NEXT_INSN (BLOCK_END (current_bb));
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 = BLOCK_HEAD (current_bb), in_libcall_block = 0;
insn && insn != NEXT_INSN (BLOCK_END (current_bb));
insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
in_libcall_block = 1;
else if (set_p && find_reg_note (insn, REG_RETVAL, NULL_RTX))
in_libcall_block = 0;
hash_scan_insn (insn, set_p, in_libcall_block);
if (!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_set_hash_table (n_insns)
int n_insns;
{
int n;
set_hash_table_size = n_insns / 4;
if (set_hash_table_size < 11)
set_hash_table_size = 11;
set_hash_table_size |= 1;
n = set_hash_table_size * sizeof (struct expr *);
set_hash_table = (struct expr **) gmalloc (n);
}
static void
free_set_hash_table ()
{
free (set_hash_table);
}
static void
compute_set_hash_table ()
{
n_sets = 0;
memset ((char *) set_hash_table, 0,
set_hash_table_size * sizeof (struct expr *));
compute_hash_table (1);
}
static void
alloc_expr_hash_table (n_insns)
unsigned int n_insns;
{
int n;
expr_hash_table_size = n_insns / 2;
if (expr_hash_table_size < 11)
expr_hash_table_size = 11;
expr_hash_table_size |= 1;
n = expr_hash_table_size * sizeof (struct expr *);
expr_hash_table = (struct expr **) gmalloc (n);
}
static void
free_expr_hash_table ()
{
free (expr_hash_table);
}
static void
compute_expr_hash_table ()
{
n_exprs = 0;
memset ((char *) expr_hash_table, 0,
expr_hash_table_size * sizeof (struct expr *));
compute_hash_table (0);
}
static struct expr *
lookup_expr (pat)
rtx pat;
{
int do_not_record_p;
unsigned int hash = hash_expr (pat, GET_MODE (pat), &do_not_record_p,
expr_hash_table_size);
struct expr *expr;
if (do_not_record_p)
return NULL;
expr = expr_hash_table[hash];
while (expr && ! expr_equiv_p (expr->expr, pat))
expr = expr->next_same_hash;
return expr;
}
static struct expr *
lookup_set (regno, pat)
unsigned int regno;
rtx pat;
{
unsigned int hash = hash_set (regno, set_hash_table_size);
struct expr *expr;
expr = set_hash_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
clear_modify_mem_tables ()
{
int i;
EXECUTE_IF_SET_IN_BITMAP
(canon_modify_mem_list_set, 0, i,
free_INSN_LIST_list (modify_mem_list + i));
bitmap_clear (canon_modify_mem_list_set);
EXECUTE_IF_SET_IN_BITMAP
(canon_modify_mem_list_set, 0, i,
free_INSN_LIST_list (canon_modify_mem_list + i));
bitmap_clear (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_basic_blocks);
rd_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
sbitmap_vector_zero (rd_gen, n_basic_blocks);
reaching_defs = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
sbitmap_vector_zero (reaching_defs, n_basic_blocks);
rd_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
sbitmap_vector_zero (rd_out, n_basic_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 bb, cuid;
unsigned int regno;
int i;
for (bb = 0; bb < n_basic_blocks; bb++)
for (cuid = 0; cuid < max_cuid; cuid++)
if (TEST_BIT (rd_gen[bb], 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, BASIC_BLOCK (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)),
BASIC_BLOCK (bb));
}
}
else if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == REG)
handle_rd_kill_set (insn, REGNO (SET_DEST (pat)), BASIC_BLOCK (bb));
}
}
static void
compute_rd ()
{
int bb, changed, passes;
for (bb = 0; bb < n_basic_blocks; bb++)
sbitmap_copy (rd_out[bb] , rd_gen[bb] );
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
for (bb = 0; bb < n_basic_blocks; bb++)
{
sbitmap_union_of_preds (reaching_defs[bb], rd_out, bb);
changed |= sbitmap_union_of_diff (rd_out[bb], rd_gen[bb],
reaching_defs[bb], rd_kill[bb]);
}
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_basic_blocks);
ae_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
sbitmap_vector_zero (ae_gen, n_basic_blocks);
ae_in = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
sbitmap_vector_zero (ae_in, n_basic_blocks);
ae_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
sbitmap_vector_zero (ae_out, n_basic_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 ()
{
unsigned int i;
struct expr *expr;
struct occr *occr;
for (i = 0; i < expr_hash_table_size; i++)
for (expr = expr_hash_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)
sbitmap *ae_gen, *ae_kill;
{
int bb;
unsigned int i;
struct expr *expr;
for (bb = 0; bb < n_basic_blocks; bb++)
for (i = 0; i < expr_hash_table_size; i++)
for (expr = expr_hash_table[i]; expr; expr = expr->next_same_hash)
{
if (TEST_BIT (ae_gen[bb], expr->bitmap_index))
continue;
if (expr_killed_p (expr->expr, BASIC_BLOCK (bb)))
SET_BIT (ae_kill[bb], 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 (n_basic_blocks, 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 bb, changed;
rtx insn;
changed = 0;
for (bb = 1; bb < n_basic_blocks; bb++)
{
reset_opr_set_tables ();
for (insn = BLOCK_HEAD (bb);
insn != NULL && insn != NEXT_INSN (BLOCK_END (bb));
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)) != NULL)
&& TEST_BIT (ae_in[bb], 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_expr_hash_table (max_cuid);
alloc_rd_mem (n_basic_blocks, max_cuid);
compute_expr_hash_table ();
if (gcse_file)
dump_hash_table (gcse_file, "Expression", expr_hash_table,
expr_hash_table_size, n_exprs);
if (n_exprs > 0)
{
compute_kill_rd ();
compute_rd ();
alloc_avail_expr_mem (n_basic_blocks, n_exprs);
compute_ae_gen ();
compute_ae_kill (ae_gen, ae_kill);
compute_available (ae_gen, ae_kill, ae_out, ae_in);
changed = classic_gcse ();
free_avail_expr_mem ();
}
free_rd_mem ();
free_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 bb, i, j;
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 (bb = 0; bb < n_basic_blocks; bb++)
if (TEST_BIT (reg_set_in_block[bb], REGNO (x)))
SET_BIT (bmap[bb], 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 (bb = 0; bb < n_basic_blocks; bb++)
if (TEST_BIT (reg_set_in_block[bb], REGNO (x)))
RESET_BIT (bmap[bb], 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 (bb = 0; bb < n_basic_blocks; bb++)
{
rtx list_entry = canon_modify_mem_list[bb];
while (list_entry)
{
rtx dest, dest_addr;
if (GET_CODE (XEXP (list_entry, 0)) == CALL_INSN)
{
if (set_p)
SET_BIT (bmap[bb], indx);
else
RESET_BIT (bmap[bb], 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], indx);
else
RESET_BIT (bmap[bb], 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, 1);
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);
success = validate_replace_src (from, to, insn);
if (!success && set != 0)
{
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)
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);
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, insn, from, src)
rtx insn;
rtx from;
rtx src;
basic_block bb;
{
rtx set = PATTERN (insn);
rtx new = simplify_replace_rtx (SET_SRC (set), from, src);
if (rtx_equal_p (new, SET_SRC (set)))
return 0;
if (new == pc_rtx)
delete_insn (insn);
else
{
if (! validate_change (insn, &SET_SRC (set), new, 0))
return 0;
if (GET_CODE (SET_SRC (set)) == LABEL_REF)
emit_barrier_after (insn);
}
run_jump_opt_after_gcse = 1;
const_prop_count++;
if (gcse_file != NULL)
{
fprintf (gcse_file,
"CONST-PROP: Replacing reg %d in insn %d with constant ",
REGNO (from), INSN_UID (insn));
print_rtl (gcse_file, src);
fprintf (gcse_file, "\n");
}
purge_dead_edges (bb);
return 1;
}
#ifdef HAVE_cc0
static int
cprop_cc0_jump (bb, insn, reg_used, src)
basic_block bb;
rtx insn;
struct reg_use *reg_used;
rtx src;
{
rtx jump = NEXT_INSN (insn);
rtx new_src = simplify_replace_rtx (SET_SRC (PATTERN (insn)),
reg_used->reg_rtx, src);
if (! cprop_jump (bb, jump, cc0_rtx, new_src))
return 0;
delete_insn (insn);
return 1;
}
#endif
static int
cprop_insn (bb, insn, alter_jumps)
basic_block bb;
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 (GET_CODE (insn) == INSN
&& try_replace_reg (reg_used->reg_rtx, src, insn))
{
changed = 1;
const_prop_count++;
if (gcse_file != NULL)
{
fprintf (gcse_file, "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");
}
}
else if (alter_jumps
&& GET_CODE (insn) == JUMP_INSN
&& condjump_p (insn)
&& ! simplejump_p (insn))
changed |= cprop_jump (bb, insn, reg_used->reg_rtx, src);
#ifdef HAVE_cc0
else if (alter_jumps
&& GET_CODE (PATTERN (insn)) == SET
&& SET_DEST (PATTERN (insn)) == cc0_rtx
&& GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
&& condjump_p (NEXT_INSN (insn))
&& ! simplejump_p (NEXT_INSN (insn))
&& cprop_cc0_jump (bb, insn, reg_used, src))
{
changed = 1;
break;
}
#endif
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 = gen_sequence ();
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 (bb);
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 = gen_sequence ();
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 (bb);
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, "COPY-PROP: Replacing reg %d in insn %d",
regno, INSN_UID (insn));
fprintf (gcse_file, " with reg %d\n", REGNO (src));
}
}
}
}
return changed;
}
static int
cprop (alter_jumps)
int alter_jumps;
{
int bb, changed;
rtx insn;
changed = 0;
for (bb = 1; bb < n_basic_blocks; bb++)
{
reset_opr_set_tables ();
for (insn = BLOCK_HEAD (bb);
insn != NULL && insn != NEXT_INSN (BLOCK_END (bb));
insn = NEXT_INSN (insn))
if (INSN_P (insn))
{
changed |= cprop_insn (BASIC_BLOCK (bb), 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;
alloc_set_hash_table (max_cuid);
compute_set_hash_table ();
if (gcse_file)
dump_hash_table (gcse_file, "SET", set_hash_table, set_hash_table_size,
n_sets);
if (n_sets > 0)
{
alloc_cprop_mem (n_basic_blocks, n_sets);
compute_cprop_data ();
changed = cprop (alter_jumps);
free_cprop_mem ();
}
free_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);
}
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;
int i;
unsigned int ui;
compute_local_properties (transp, comp, antloc, 0);
sbitmap_vector_zero (ae_kill, n_basic_blocks);
trapping_expr = sbitmap_alloc (n_exprs);
sbitmap_zero (trapping_expr);
for (ui = 0; ui < expr_hash_table_size; ui++)
{
struct expr *e;
for (e = expr_hash_table[ui]; e != NULL; e = e->next_same_hash)
if (may_trap_p (e->expr))
SET_BIT (trapping_expr, e->bitmap_index);
}
for (i = 0; i < n_basic_blocks; i++)
{
edge e;
for (e = BASIC_BLOCK (i)->pred; e ; e = e->pred_next)
if (e->flags & EDGE_ABNORMAL)
{
sbitmap_difference (antloc[i], antloc[i], trapping_expr);
sbitmap_difference (transp[i], transp[i], trapping_expr);
break;
}
sbitmap_a_or_b (ae_kill[i], transp[i], comp[i]);
sbitmap_not (ae_kill[i], ae_kill[i]);
}
edge_list = pre_edge_lcm (gcse_file, n_exprs, 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 (n_basic_blocks, 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 = gen_sequence ();
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;
int i;
pat = process_insert_insn (expr);
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);
if (GET_CODE (pat) == SEQUENCE)
{
for (i = 0; i < XVECLEN (pat, 0); i++)
{
rtx insn = XVECEXP (pat, 0, i);
if (INSN_P (insn))
add_label_notes (PATTERN (insn), new_insn);
note_stores (PATTERN (insn), record_set_info, insn);
}
}
else
{
add_label_notes (pat, new_insn);
record_one_set (regno, new_insn);
}
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, n_exprs);
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 < n_exprs; 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[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 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[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)));
if (validate_change (insn, &SET_SRC (set),
expr->reaching_reg, 0))
{
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 (n_exprs, sizeof (struct expr *));
for (i = 0; i < expr_hash_table_size; i++)
for (expr = expr_hash_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_expr_hash_table (max_cuid);
add_noreturn_fake_exit_edges ();
if (flag_gcse_lm)
compute_ld_motion_mems ();
compute_expr_hash_table ();
trim_ld_motion_mems ();
if (gcse_file)
dump_hash_table (gcse_file, "Expression", expr_hash_table,
expr_hash_table_size, n_exprs);
if (n_exprs > 0)
{
alloc_pre_mem (n_basic_blocks, n_exprs);
compute_pre_data ();
changed |= pre_gcse ();
free_edge_list (edge_list);
free_pre_mem ();
}
free_ldst_mems ();
remove_fake_edges ();
free_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 ()
{
int bb;
unsigned int i;
struct expr *expr;
sbitmap_vector_ones (transpout, n_basic_blocks);
for (bb = 0; bb < n_basic_blocks; ++bb)
{
if (GET_CODE (BLOCK_END (bb)) != CALL_INSN)
continue;
for (i = 0; i < expr_hash_table_size; i++)
for (expr = expr_hash_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], 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], regno);
SET_BIT (npi->nonnull_killed[npi->current_block], regno);
}
static void
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;
{
int bb;
int current_block;
sbitmap *nonnull_local = npi->nonnull_local;
sbitmap *nonnull_killed = npi->nonnull_killed;
sbitmap_vector_zero (nonnull_local, n_basic_blocks);
sbitmap_vector_zero (nonnull_killed, n_basic_blocks);
for (current_block = 0; current_block < n_basic_blocks; current_block++)
{
rtx insn, stop_insn;
npi->current_block = current_block;
stop_insn = NEXT_INSN (BLOCK_END (current_block));
for (insn = BLOCK_HEAD (current_block);
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],
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],
REGNO (reg) - npi->min_reg);
}
}
compute_available (nonnull_local, nonnull_killed,
nonnull_avout, nonnull_avin);
for (bb = 0; bb < n_basic_blocks; bb++)
{
rtx last_insn = BLOCK_END (bb);
rtx condition, earliest;
int compare_and_branch;
if (block_reg[bb] < npi->min_reg
|| block_reg[bb] >= npi->max_reg)
continue;
condition = get_condition (last_insn, &earliest);
if (! condition)
continue;
if (!TEST_BIT (nonnull_avout[bb], block_reg[bb] - 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_before (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);
}
delete_insn (last_insn);
#if 0
if (compare_and_branch == 2)
delete_insn (earliest);
#endif
purge_dead_edges (BASIC_BLOCK (bb));
block_reg[bb] = 0;
}
}
void
delete_null_pointer_checks (f)
rtx f ATTRIBUTE_UNUSED;
{
sbitmap *nonnull_avin, *nonnull_avout;
unsigned int *block_reg;
int bb;
int reg;
int regs_per_pass;
int max_reg;
struct null_pointer_info npi;
if (n_basic_blocks <= 1)
return;
if (n_basic_blocks > 1000 && n_edges / n_basic_blocks >= 20)
return;
max_reg = max_reg_num ();
regs_per_pass = get_bitmap_width (4, n_basic_blocks, max_reg);
npi.nonnull_local = sbitmap_vector_alloc (n_basic_blocks, regs_per_pass);
npi.nonnull_killed = sbitmap_vector_alloc (n_basic_blocks, regs_per_pass);
nonnull_avin = sbitmap_vector_alloc (n_basic_blocks, regs_per_pass);
nonnull_avout = sbitmap_vector_alloc (n_basic_blocks, regs_per_pass);
block_reg = (unsigned int *) xcalloc (n_basic_blocks, sizeof (int));
for (bb = 0; bb < n_basic_blocks; bb++)
{
rtx last_insn = BLOCK_END (bb);
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] = 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);
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);
}
static sbitmap *hoist_vbein;
static sbitmap *hoist_vbeout;
static sbitmap *hoist_exprs;
static sbitmap *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);
dominators = sbitmap_vector_alloc (n_blocks, n_blocks);
}
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);
sbitmap_vector_free (dominators);
}
static void
compute_code_hoist_vbeinout ()
{
int bb, changed, passes;
sbitmap_vector_zero (hoist_vbeout, n_basic_blocks);
sbitmap_vector_zero (hoist_vbein, n_basic_blocks);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
for (bb = n_basic_blocks - 1; bb >= 0; bb--)
{
changed |= sbitmap_a_or_b_and_c (hoist_vbein[bb], antloc[bb],
hoist_vbeout[bb], transp[bb]);
if (bb != n_basic_blocks - 1)
sbitmap_intersection_of_succs (hoist_vbeout[bb], hoist_vbein, bb);
}
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, 0);
compute_transpout ();
compute_code_hoist_vbeinout ();
calculate_dominance_info (NULL, dominators, 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 (n_basic_blocks, 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 (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 ()
{
int bb, dominated;
unsigned int i;
struct expr **index_map;
struct expr *expr;
sbitmap_vector_zero (hoist_exprs, n_basic_blocks);
index_map = (struct expr **) xcalloc (n_exprs, sizeof (struct expr *));
for (i = 0; i < expr_hash_table_size; i++)
for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
index_map[expr->bitmap_index] = expr;
for (bb = 0; bb < n_basic_blocks; bb++)
{
int found = 0;
int insn_inserted_p;
for (i = 0; i < hoist_vbeout[bb]->n_bits; i++)
{
int hoistable = 0;
if (TEST_BIT (hoist_vbeout[bb], i) && TEST_BIT (transpout[bb], i))
{
for (dominated = 0; dominated < n_basic_blocks; dominated++)
{
if (bb == dominated
|| ! TEST_BIT (dominators[dominated], bb))
continue;
if (!TEST_BIT (antloc[dominated], i))
continue;
if (hoist_expr_reaches_here_p (BASIC_BLOCK (bb), i,
BASIC_BLOCK (dominated), NULL))
hoistable++;
}
if (hoistable > 1)
{
SET_BIT (hoist_exprs[bb], i);
found = 1;
}
}
}
if (! found)
continue;
for (i = 0; i < hoist_exprs[bb]->n_bits; i++)
{
insn_inserted_p = 0;
if (TEST_BIT (hoist_vbeout[bb], i))
{
for (dominated = 0; dominated < n_basic_blocks; dominated++)
{
if (bb == dominated
|| ! TEST_BIT (dominators[dominated], bb))
continue;
if (!TEST_BIT (antloc[dominated], i))
continue;
if (hoist_expr_reaches_here_p (BASIC_BLOCK (bb), i,
BASIC_BLOCK (dominated), NULL))
{
struct expr *expr = index_map[i];
struct occr *occr = expr->antic_occr;
rtx insn;
rtx set;
while (BLOCK_NUM (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)));
if (validate_change (insn, &SET_SRC (set),
expr->reaching_reg, 0))
{
occr->deleted_p = 1;
if (!insn_inserted_p)
{
insert_insn_end_bb (index_map[i],
BASIC_BLOCK (bb), 0);
insn_inserted_p = 1;
}
}
}
}
}
}
}
free (index_map);
}
static int
one_code_hoisting_pass ()
{
int changed = 0;
alloc_expr_hash_table (max_cuid);
compute_expr_hash_table ();
if (gcse_file)
dump_hash_table (gcse_file, "Code Hosting Expressions", expr_hash_table,
expr_hash_table_size, n_exprs);
if (n_exprs > 0)
{
alloc_code_hoist_mem (n_basic_blocks, n_exprs);
compute_code_hoist_data ();
hoist_code ();
free_code_hoist_mem ();
}
free_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;
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;
int bb;
rtx insn;
pre_ldst_mems = NULL;
for (bb = 0; bb < n_basic_blocks; bb++)
{
for (insn = BLOCK_HEAD (bb);
insn && insn != NEXT_INSN (BLOCK_END (bb));
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[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 bb, ret;
unsigned regno;
rtx insn, pat;
max_gcse_regno = max_reg_num ();
reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks,
max_gcse_regno);
sbitmap_vector_zero (reg_set_in_block, n_basic_blocks);
pre_ldst_mems = 0;
for (bb = 0; bb < n_basic_blocks; bb++)
{
regvec = & (reg_set_in_block[bb]);
for (insn = BLOCK_END (bb);
insn && insn != PREV_INSN (BLOCK_HEAD (bb));
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], 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;
int b;
rtx insn, st;
struct ls_expr * ptr;
ae_gen = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, num_stores);
sbitmap_vector_zero (ae_gen, n_basic_blocks);
st_antloc = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, num_stores);
sbitmap_vector_zero (st_antloc, n_basic_blocks);
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 (n_basic_blocks, num_stores);
sbitmap_vector_zero (ae_kill, n_basic_blocks);
transp = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks, num_stores);
sbitmap_vector_zero (transp, n_basic_blocks);
for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
for (b = 0; b < n_basic_blocks; b++)
{
if (store_killed_after (ptr->pattern, BLOCK_HEAD (b), BASIC_BLOCK (b)))
{
SET_BIT (ae_kill[b], ptr->index);
}
else
SET_BIT (transp[b], 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, n_basic_blocks);
dump_sbitmap_vector (gcse_file, "st_kill", "", ae_kill, n_basic_blocks);
dump_sbitmap_vector (gcse_file, "Transpt", "", transp, n_basic_blocks);
dump_sbitmap_vector (gcse_file, "st_avloc", "", ae_gen, n_basic_blocks);
}
}
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 ()
{
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 (x = 0; x < n_basic_blocks; x++)
if (TEST_BIT (pre_delete_map[x], ptr->index))
delete_store (ptr, BASIC_BLOCK (x));
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 ();
}