#include "config.h"
#include "system.h"
#include "toplev.h"
#include "rtl.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 "expr.h"
#include "obstack.h"
#define obstack_chunk_alloc gmalloc
#define obstack_chunk_free free
#define MAX_PASSES 1
#define FOLLOW_BACK_EDGES 1
static FILE *gcse_file;
static int run_jump_opt_after_gcse;
static int_list_ptr *s_preds;
static int_list_ptr *s_succs;
static int *num_preds;
static int *num_succs;
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 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 int expr_hash_table_size;
static struct expr **expr_hash_table;
static int set_hash_table_size;
static struct expr **set_hash_table;
static int *uid_cuid;
static int max_uid;
#define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
static int max_cuid;
static rtx *cuid_insn;
#define CUID_INSN(CUID) (cuid_insn[CUID])
static 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
static sbitmap reg_set_bitmap;
static sbitmap *reg_set_in_block;
static char *mem_set_in_block;
static int bytes_used;
static int gcse_subst_count;
static int gcse_create_count;
static int const_prop_count;
static int copy_prop_count;
extern char *current_function_name;
extern int current_function_calls_setjmp;
static sbitmap u_bitmap;
static sbitmap *rd_kill, *rd_gen, *reaching_defs, *rd_out;
static sbitmap *ae_kill, *ae_gen, *ae_in, *ae_out;
static void compute_can_copy PROTO ((void));
static char *gmalloc PROTO ((unsigned int));
static char *grealloc PROTO ((char *, unsigned int));
static char *gcse_alloc PROTO ((unsigned long));
static void alloc_gcse_mem PROTO ((rtx));
static void free_gcse_mem PROTO ((void));
static void alloc_reg_set_mem PROTO ((int));
static void free_reg_set_mem PROTO ((void));
static void record_one_set PROTO ((int, rtx));
static void record_set_info PROTO ((rtx, rtx));
static void compute_sets PROTO ((rtx));
static void hash_scan_insn PROTO ((rtx, int, int));
static void hash_scan_set PROTO ((rtx, rtx, int));
static void hash_scan_clobber PROTO ((rtx, rtx));
static void hash_scan_call PROTO ((rtx, rtx));
static int want_to_gcse_p PROTO ((rtx));
static int oprs_unchanged_p PROTO ((rtx, rtx, int));
static int oprs_anticipatable_p PROTO ((rtx, rtx));
static int oprs_available_p PROTO ((rtx, rtx));
static void insert_expr_in_table PROTO ((rtx, enum machine_mode,
rtx, int, int));
static void insert_set_in_table PROTO ((rtx, rtx));
static unsigned int hash_expr PROTO ((rtx, enum machine_mode,
int *, int));
static unsigned int hash_expr_1 PROTO ((rtx, enum machine_mode, int *));
static unsigned int hash_set PROTO ((int, int));
static int expr_equiv_p PROTO ((rtx, rtx));
static void record_last_reg_set_info PROTO ((rtx, int));
static void record_last_mem_set_info PROTO ((rtx));
static void record_last_set_info PROTO ((rtx, rtx));
static void compute_hash_table PROTO ((int));
static void alloc_set_hash_table PROTO ((int));
static void free_set_hash_table PROTO ((void));
static void compute_set_hash_table PROTO ((void));
static void alloc_expr_hash_table PROTO ((int));
static void free_expr_hash_table PROTO ((void));
static void compute_expr_hash_table PROTO ((void));
static void dump_hash_table PROTO ((FILE *, const char *, struct expr **,
int, int));
static struct expr *lookup_expr PROTO ((rtx));
static struct expr *lookup_set PROTO ((int, rtx));
static struct expr *next_set PROTO ((int, struct expr *));
static void reset_opr_set_tables PROTO ((void));
static int oprs_not_set_p PROTO ((rtx, rtx));
static void mark_call PROTO ((rtx));
static void mark_set PROTO ((rtx, rtx));
static void mark_clobber PROTO ((rtx, rtx));
static void mark_oprs_set PROTO ((rtx));
static void alloc_cprop_mem PROTO ((int, int));
static void free_cprop_mem PROTO ((void));
static void compute_transp PROTO ((rtx, int, sbitmap *, int));
static void compute_transpout PROTO ((void));
static void compute_local_properties PROTO ((sbitmap *, sbitmap *,
sbitmap *, int));
static void compute_cprop_avinout PROTO ((void));
static void compute_cprop_data PROTO ((void));
static void find_used_regs PROTO ((rtx));
static int try_replace_reg PROTO ((rtx, rtx, rtx));
static struct expr *find_avail_set PROTO ((int, rtx));
static int cprop_insn PROTO ((rtx, int));
static int cprop PROTO ((int));
static int one_cprop_pass PROTO ((int, int));
static void alloc_pre_mem PROTO ((int, int));
static void free_pre_mem PROTO ((void));
static void compute_pre_data PROTO ((void));
static int pre_expr_reaches_here_p PROTO ((int, struct expr *,
int, int, char *));
static void insert_insn_end_bb PROTO ((struct expr *, int, int));
static void pre_insert PROTO ((struct expr **));
static void pre_insert_copy_insn PROTO ((struct expr *, rtx));
static void pre_insert_copies PROTO ((void));
static int pre_delete PROTO ((void));
static int pre_gcse PROTO ((void));
static int one_pre_gcse_pass PROTO ((int));
static void add_label_notes PROTO ((rtx, rtx));
static void alloc_rd_mem PROTO ((int, int));
static void free_rd_mem PROTO ((void));
static void handle_rd_kill_set PROTO ((rtx, int, int));
static void compute_kill_rd PROTO ((void));
static void compute_rd PROTO ((void));
static void alloc_avail_expr_mem PROTO ((int, int));
static void free_avail_expr_mem PROTO ((void));
static void compute_ae_gen PROTO ((void));
static int expr_killed_p PROTO ((rtx, int));
static void compute_ae_kill PROTO ((void));
static void compute_available PROTO ((void));
static int expr_reaches_here_p PROTO ((struct occr *, struct expr *,
int, int, char *));
static rtx computing_insn PROTO ((struct expr *, rtx));
static int def_reaches_here_p PROTO ((rtx, rtx));
static int can_disregard_other_sets PROTO ((struct reg_set **, rtx, int));
static int handle_avail_expr PROTO ((rtx, struct expr *));
static int classic_gcse PROTO ((void));
static int one_classic_gcse_pass PROTO ((int));
int
gcse_main (f, file)
rtx f;
FILE *file;
{
int changed, pass;
int initial_bytes_used;
int max_pass_bytes;
char *gcse_obstack_bottom;
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 ();
find_basic_blocks (f, max_gcse_regno, file, 1);
if (n_basic_blocks <= 1)
{
free_basic_block_vars (0);
return 0;
}
if (! can_copy_init_p)
{
compute_can_copy ();
can_copy_init_p = 1;
}
gcc_obstack_init (&gcse_obstack);
s_preds = (int_list_ptr *) alloca (n_basic_blocks * sizeof (int_list_ptr));
s_succs = (int_list_ptr *) alloca (n_basic_blocks * sizeof (int_list_ptr));
num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
bytes_used = 4 * n_basic_blocks * sizeof (int_list_ptr);
compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
if (file)
dump_bb_data (file, s_preds, s_succs, 0);
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_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);
if (optimize_size)
changed |= one_classic_gcse_pass (pass + 1);
else
changed |= one_pre_gcse_pass (pass + 1);
if (max_pass_bytes < bytes_used)
max_pass_bytes = bytes_used;
free_gcse_mem ();
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_PTR);
free_reg_set_mem ();
free_bb_mem ();
free_basic_block_vars (0);
return run_jump_opt_after_gcse;
}
static void
compute_can_copy ()
{
int i;
#ifndef AVOID_CCMODE_COPIES
rtx reg,insn;
#endif
char *free_point = (char *) oballoc (1);
bzero (can_copy_p, NUM_MACHINE_MODES);
start_sequence ();
for (i = 0; i < NUM_MACHINE_MODES; i++)
{
switch (GET_MODE_CLASS (i))
{
case 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_PTR) >= 0)
can_copy_p[i] = 1;
#endif
break;
default :
can_copy_p[i] = 1;
break;
}
}
end_sequence ();
obfree (free_point);
}
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);
bzero ((char *) uid_cuid, n);
for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
INSN_CUID (insn) = i++;
else
INSN_CUID (insn) = i;
}
max_cuid = i;
n = (max_cuid + 1) * sizeof (rtx);
cuid_insn = (rtx *) gmalloc (n);
bzero ((char *) cuid_insn, n);
for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
CUID_INSN (i) = insn;
i++;
}
}
reg_set_bitmap = (sbitmap) sbitmap_alloc (max_gcse_regno);
reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks,
max_gcse_regno);
mem_set_in_block = (char *) gmalloc (n_basic_blocks);
}
static void
free_gcse_mem ()
{
free (uid_cuid);
free (cuid_insn);
free (reg_set_bitmap);
free (reg_set_in_block);
free (mem_set_in_block);
}
static void
compute_local_properties (transp, comp, antloc, setp)
sbitmap *transp;
sbitmap *comp;
sbitmap *antloc;
int setp;
{
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)
{
struct occr *occr;
int indx = expr->bitmap_index;
if (transp)
compute_transp (expr->expr, indx, transp, setp);
if (antloc)
{
for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
{
int bb = BLOCK_NUM (occr->insn);
SET_BIT (antloc[bb], indx);
occr->deleted_p = 0;
}
}
if (comp)
{
for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
{
int bb = BLOCK_NUM (occr->insn);
SET_BIT (comp[bb], 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;
{
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);
bzero ((char *) reg_set_table, n);
gcc_obstack_init (®_set_obstack);
}
static void
free_reg_set_mem ()
{
free (reg_set_table);
obstack_free (®_set_obstack, NULL_PTR);
}
static void
record_one_set (regno, insn)
int regno;
rtx insn;
{
struct reg_set *new_reg_info, *reg_info_ptr1, *reg_info_ptr2;
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 *));
bzero ((char *) (reg_set_table + reg_set_table_size),
(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 = NULL;
if (reg_set_table[regno] == NULL)
reg_set_table[regno] = new_reg_info;
else
{
reg_info_ptr1 = reg_info_ptr2 = reg_set_table[regno];
while (reg_info_ptr1 != NULL)
{
reg_info_ptr2 = reg_info_ptr1;
reg_info_ptr1 = reg_info_ptr1->next;
}
reg_info_ptr2->next = new_reg_info;
}
}
static rtx record_set_insn;
static void
record_set_info (dest, setter)
rtx dest, setter ATTRIBUTE_UNUSED;
{
if (GET_CODE (dest) == SUBREG)
dest = SUBREG_REG (dest);
if (GET_CODE (dest) == REG)
{
if (REGNO (dest) >= FIRST_PSEUDO_REGISTER)
record_one_set (REGNO (dest), record_set_insn);
}
}
static void
compute_sets (f)
rtx f;
{
rtx insn = f;
while (insn)
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
record_set_insn = insn;
note_stores (PATTERN (insn), record_set_info);
}
insn = NEXT_INSN (insn);
}
}
#define NEVER_SET -1
static int *reg_first_set;
static int *reg_last_set;
static int mem_first_set;
static int mem_last_set;
static int
want_to_gcse_p (x)
rtx x;
{
enum rtx_code code = GET_CODE (x);
switch (code)
{
case REG:
case SUBREG:
case CONST_INT:
case CONST_DOUBLE:
case CALL:
return 0;
default:
break;
}
return 1;
}
static int
oprs_unchanged_p (x, insn, avail_p)
rtx x, insn;
int avail_p;
{
int i;
enum rtx_code code;
char *fmt;
repeat:
if (x == 0)
return 1;
code = GET_CODE (x);
switch (code)
{
case REG:
if (avail_p)
return (reg_last_set[REGNO (x)] == NEVER_SET
|| reg_last_set[REGNO (x)] < INSN_CUID (insn));
else
return (reg_first_set[REGNO (x)] == NEVER_SET
|| reg_first_set[REGNO (x)] >= INSN_CUID (insn));
case MEM:
if (avail_p)
{
if (mem_last_set != NEVER_SET
&& mem_last_set >= INSN_CUID (insn))
return 0;
}
else
{
if (mem_first_set != NEVER_SET
&& mem_first_set < INSN_CUID (insn))
return 0;
}
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 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 (! oprs_unchanged_p (tem, insn, avail_p))
return 0;
}
else if (fmt[i] == 'E')
{
int j;
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
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 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;
char *fmt;
repeat:
if (x == 0)
return hash;
code = GET_CODE (x);
switch (code)
{
case REG:
{
register int regno = REGNO (x);
hash += ((unsigned) REG << 7) + regno;
return hash;
}
case CONST_INT:
{
unsigned HOST_WIDE_INT tem = INTVAL (x);
hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem;
return hash;
}
case CONST_DOUBLE:
hash += (unsigned) code + (unsigned) GET_MODE (x);
if (GET_MODE (x) != VOIDmode)
for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
{
unsigned tem = XINT (x, i);
hash += tem;
}
else
hash += ((unsigned) CONST_DOUBLE_LOW (x)
+ (unsigned) CONST_DOUBLE_HIGH (x));
return hash;
case LABEL_REF:
hash += ((unsigned) LABEL_REF << 7) + CODE_LABEL_NUMBER (XEXP (x, 0));
return hash;
case SYMBOL_REF:
{
unsigned int h = 0;
unsigned char *p = (unsigned char *) XSTR (x, 0);
while (*p)
h += (h << 7) + *p++;
hash += ((unsigned) SYMBOL_REF << 7) + h;
return hash;
}
case MEM:
if (MEM_VOLATILE_P (x))
{
*do_not_record_p = 1;
return 0;
}
hash += (unsigned) 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;
}
default:
break;
}
i = GET_RTX_LENGTH (code) - 1;
hash += (unsigned) code + (unsigned) GET_MODE (x);
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;
}
hash += hash_expr_1 (tem, 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')
{
register unsigned char *p = (unsigned char *) XSTR (x, i);
if (p)
while (*p)
hash += *p++;
}
else if (fmt[i] == 'i')
{
register unsigned tem = XINT (x, i);
hash += tem;
}
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;
{
register int i, j;
register enum rtx_code code;
register 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))));
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 && ! (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 && ! (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);
if (GET_CODE (src) == CALL)
hash_scan_call (src, insn);
if (GET_CODE (dest) == REG)
{
int regno = REGNO (dest);
rtx tmp;
if (! set_p
&& regno >= FIRST_PSEUDO_REGISTER
&& can_copy_p [GET_MODE (dest)]
&& want_to_gcse_p (src))
{
int antic_p = ! optimize_size && oprs_anticipatable_p (src, insn);
int avail_p = oprs_available_p (src, 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)])
|| GET_CODE (src) == CONST_INT
|| GET_CODE (src) == CONST_DOUBLE)
&& (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);
if (GET_CODE (pat) == SET && ! in_libcall_block)
hash_scan_set (pat, insn, set_p);
else if (GET_CODE (pat) == PARALLEL)
{
int i;
for (i = 0; i < XVECLEN (pat, 0); i++)
{
rtx x = XVECEXP (pat, 0, i);
if (GET_CODE (x) == SET)
{
if (GET_CODE (SET_SRC (x)) == CALL)
hash_scan_call (SET_SRC (x), insn);
}
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 = (struct expr **) alloca (total_size * sizeof (struct expr *));
unsigned int *hash_val = (unsigned int *) alloca (total_size * sizeof (unsigned int));
bzero ((char *) flat_table, total_size * sizeof (struct expr *));
for (i = 0; i < table_size; i++)
{
struct expr *expr;
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++)
{
struct expr *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");
}
static void
record_last_reg_set_info (insn, regno)
rtx insn;
int regno;
{
if (reg_first_set[regno] == NEVER_SET)
reg_first_set[regno] = INSN_CUID (insn);
reg_last_set[regno] = INSN_CUID (insn);
SET_BIT (reg_set_in_block[BLOCK_NUM (insn)], regno);
}
static void
record_last_mem_set_info (insn)
rtx insn;
{
if (mem_first_set == NEVER_SET)
mem_first_set = INSN_CUID (insn);
mem_last_set = INSN_CUID (insn);
mem_set_in_block[BLOCK_NUM (insn)] = 1;
}
static rtx last_set_insn;
static void
record_last_set_info (dest, setter)
rtx dest, setter ATTRIBUTE_UNUSED;
{
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;
{
int bb;
sbitmap_vector_zero (reg_set_in_block, n_basic_blocks);
bzero ((char *) mem_set_in_block, n_basic_blocks);
reg_first_set = (int *) gmalloc (max_gcse_regno * sizeof (int));
reg_last_set = (int *) gmalloc (max_gcse_regno * sizeof (int));
for (bb = 0; bb < n_basic_blocks; bb++)
{
rtx insn;
int regno;
int in_libcall_block;
int i;
for (i = 0; i < max_gcse_regno; i++)
reg_first_set[i] = reg_last_set[i] = NEVER_SET;
mem_first_set = NEVER_SET;
mem_last_set = NEVER_SET;
for (insn = BLOCK_HEAD (bb);
insn && insn != NEXT_INSN (BLOCK_END (bb));
insn = NEXT_INSN (insn))
{
#ifdef NON_SAVING_SETJMP
if (NON_SAVING_SETJMP && GET_CODE (insn) == NOTE
&& NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
{
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
record_last_reg_set_info (insn, regno);
continue;
}
#endif
if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
continue;
if (GET_CODE (insn) == CALL_INSN)
{
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
if ((call_used_regs[regno]
&& regno != STACK_POINTER_REGNUM
#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
&& regno != HARD_FRAME_POINTER_REGNUM
#endif
#if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
&& ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
#endif
#if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED)
&& ! (regno == PIC_OFFSET_TABLE_REGNUM && flag_pic)
#endif
&& regno != FRAME_POINTER_REGNUM)
|| global_regs[regno])
record_last_reg_set_info (insn, regno);
if (! CONST_CALL_P (insn))
record_last_mem_set_info (insn);
}
last_set_insn = insn;
note_stores (PATTERN (insn), record_last_set_info);
}
for (insn = BLOCK_HEAD (bb), in_libcall_block = 0;
insn && insn != NEXT_INSN (BLOCK_END (bb));
insn = NEXT_INSN (insn))
{
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
in_libcall_block = 1;
else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
in_libcall_block = 0;
hash_scan_insn (insn, set_p, in_libcall_block);
}
}
}
free (reg_first_set);
free (reg_last_set);
reg_first_set = reg_last_set = 0;
}
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;
bzero ((char *) set_hash_table, set_hash_table_size * sizeof (struct expr *));
compute_hash_table (1);
}
static void
alloc_expr_hash_table (n_insns)
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;
bzero ((char *) expr_hash_table, 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)
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)
int regno;
struct expr *expr;
{
do
expr = expr->next_same_hash;
while (expr && REGNO (SET_DEST (expr->expr)) != regno);
return expr;
}
static void
reset_opr_set_tables ()
{
sbitmap_zero (reg_set_bitmap);
mem_last_set = 0;
}
static int
oprs_not_set_p (x, insn)
rtx x, insn;
{
int i;
enum rtx_code code;
char *fmt;
repeat:
if (x == 0)
return 1;
code = GET_CODE (x);
switch (code)
{
case PC:
case CC0:
case CONST:
case CONST_INT:
case CONST_DOUBLE:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
case ADDR_DIFF_VEC:
return 1;
case MEM:
if (mem_last_set != 0)
return 0;
x = XEXP (x, 0);
goto repeat;
case REG:
return ! TEST_BIT (reg_set_bitmap, REGNO (x));
default:
break;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
{
int not_set_p;
if (i == 0)
{
x = XEXP (x, 0);
goto repeat;
}
not_set_p = oprs_not_set_p (XEXP (x, i), insn);
if (! not_set_p)
return 0;
}
else if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
{
int not_set_p = oprs_not_set_p (XVECEXP (x, i, j), insn);
if (! not_set_p)
return 0;
}
}
}
return 1;
}
static void
mark_call (insn)
rtx insn;
{
mem_last_set = INSN_CUID (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_BIT (reg_set_bitmap, REGNO (dest));
else if (GET_CODE (dest) == MEM)
mem_last_set = INSN_CUID (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_BIT (reg_set_bitmap, REGNO (clob));
else
mem_last_set = INSN_CUID (insn);
}
static void
mark_oprs_set (insn)
rtx insn;
{
rtx pat = PATTERN (insn);
if (GET_CODE (pat) == SET)
mark_set (pat, insn);
else if (GET_CODE (pat) == PARALLEL)
{
int i;
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 ()
{
free (rd_kill);
free (rd_gen);
free (reaching_defs);
free (rd_out);
}
static void
handle_rd_kill_set (insn, regno, bb)
rtx insn;
int regno, bb;
{
struct reg_set *this_reg = reg_set_table[regno];
while (this_reg)
{
if (BLOCK_NUM (this_reg->insn) != BLOCK_NUM (insn))
SET_BIT (rd_kill[bb], INSN_CUID (this_reg->insn));
this_reg = this_reg->next;
}
}
static void
compute_kill_rd ()
{
int bb,cuid;
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)
{
int regno;
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
{
if ((call_used_regs[regno]
&& regno != STACK_POINTER_REGNUM
#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
&& regno != HARD_FRAME_POINTER_REGNUM
#endif
#if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
&& ! (regno == ARG_POINTER_REGNUM
&& fixed_regs[regno])
#endif
#if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED)
&& ! (regno == PIC_OFFSET_TABLE_REGNUM && flag_pic)
#endif
&& regno != FRAME_POINTER_REGNUM)
|| global_regs[regno])
handle_rd_kill_set (insn, regno, bb);
}
}
if (GET_CODE (pat) == PARALLEL)
{
int i;
for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
{
enum rtx_code code = GET_CODE (XVECEXP (pat, 0, i));
if ((code == SET || code == CLOBBER)
&& GET_CODE (XEXP (XVECEXP (pat, 0, i), 0)) == REG)
handle_rd_kill_set (insn,
REGNO (XEXP (XVECEXP (pat, 0, i), 0)),
bb);
}
}
else if (GET_CODE (pat) == SET)
{
if (GET_CODE (SET_DEST (pat)) == REG)
{
handle_rd_kill_set (insn, REGNO (SET_DEST (pat)), 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_predecessors (reaching_defs[bb], rd_out,
bb, s_preds);
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);
u_bitmap = (sbitmap) sbitmap_alloc (n_exprs);
sbitmap_ones (u_bitmap);
}
static void
free_avail_expr_mem ()
{
free (ae_kill);
free (ae_gen);
free (ae_in);
free (ae_out);
free (u_bitmap);
}
static void
compute_ae_gen ()
{
int i;
for (i = 0; i < expr_hash_table_size; i++)
{
struct expr *expr = expr_hash_table[i];
while (expr != NULL)
{
struct occr *occr = expr->avail_occr;
while (occr != NULL)
{
SET_BIT (ae_gen[BLOCK_NUM (occr->insn)], expr->bitmap_index);
occr = occr->next;
}
expr = expr->next_same_hash;
}
}
}
static int
expr_killed_p (x, bb)
rtx x;
int bb;
{
int i;
enum rtx_code code;
char *fmt;
repeat:
if (x == 0)
return 1;
code = GET_CODE (x);
switch (code)
{
case REG:
return TEST_BIT (reg_set_in_block[bb], REGNO (x));
case MEM:
if (mem_set_in_block[bb])
return 1;
x = XEXP (x, 0);
goto repeat;
case PC:
case CC0:
case CONST:
case CONST_INT:
case CONST_DOUBLE:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
case ADDR_DIFF_VEC:
return 0;
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 (expr_killed_p (tem, bb))
return 1;
}
else if (fmt[i] == 'E')
{
int j;
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 ()
{
int bb,i;
for (bb = 0; bb < n_basic_blocks; bb++)
{
for (i = 0; i < expr_hash_table_size; i++)
{
struct expr *expr = expr_hash_table[i];
for ( ; expr != NULL; expr = expr->next_same_hash)
{
if (TEST_BIT (ae_gen[bb], expr->bitmap_index))
continue;
if (expr_killed_p (expr->expr, bb))
SET_BIT (ae_kill[bb], expr->bitmap_index);
}
}
}
}
static void
compute_available ()
{
int bb, changed, passes;
sbitmap_zero (ae_in[0]);
sbitmap_copy (ae_out[0] , ae_gen[0] );
for (bb = 1; bb < n_basic_blocks; bb++)
sbitmap_difference (ae_out[bb], u_bitmap, ae_kill[bb]);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
for (bb = 1; bb < n_basic_blocks; bb++)
{
sbitmap_intersect_of_predecessors (ae_in[bb], ae_out, bb, s_preds);
changed |= sbitmap_union_of_diff (ae_out[bb], ae_gen[bb],
ae_in[bb], ae_kill[bb]);
}
passes++;
}
if (gcse_file)
fprintf (gcse_file, "avail expr computation: %d passes\n", passes);
}
static int
expr_reaches_here_p (occr, expr, bb, check_self_loop, visited)
struct occr *occr;
struct expr *expr;
int bb;
int check_self_loop;
char *visited;
{
int_list_ptr pred;
if (visited == NULL)
{
visited = (char *) alloca (n_basic_blocks);
bzero (visited, n_basic_blocks);
}
for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
{
int pred_bb = INT_LIST_VAL (pred);
if (visited[pred_bb])
{
;
}
else if (pred_bb == bb)
{
if (check_self_loop
&& TEST_BIT (ae_gen[pred_bb], expr->bitmap_index)
&& BLOCK_NUM (occr->insn) == pred_bb)
return 1;
visited[pred_bb] = 1;
}
else if (TEST_BIT (ae_kill[pred_bb], expr->bitmap_index))
visited[pred_bb] = 1;
else if (TEST_BIT (ae_gen[pred_bb], expr->bitmap_index))
{
if (BLOCK_NUM (occr->insn) == pred_bb)
return 1;
visited[pred_bb] = 1;
}
else
{
visited[pred_bb] = 1;
if (expr_reaches_here_p (occr, expr, pred_bb, check_self_loop, visited))
return 1;
}
}
return 0;
}
static rtx
computing_insn (expr, insn)
struct expr *expr;
rtx insn;
{
int bb = BLOCK_NUM (insn);
if (expr->avail_occr->next == NULL)
{
if (BLOCK_NUM (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_NUM (occr->insn) == bb)
{
if (INSN_CUID (insn) < INSN_CUID (occr->insn))
{
if (expr_reaches_here_p (occr, expr, bb, 1, NULL))
{
can_reach++;
if (can_reach > 1)
return NULL;
insn_computes_expr = occr->insn;
}
}
}
else
{
if (expr_reaches_here_p (occr, expr, bb, 0, NULL))
{
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;
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 = *addr_this_reg;
while (this_reg)
{
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;
if (! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
SET_SRC (PATTERN (insn))))
return 0;
}
*addr_this_reg = this_reg;
}
this_reg = this_reg->next;
}
return number_of_reaching_defs;
}
static int
handle_avail_expr (insn, expr)
rtx insn;
struct expr *expr;
{
rtx pat, insn_computes_expr;
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;
found_setting = 0;
use_src = 0;
if (GET_CODE (SET_SRC (PATTERN (insn_computes_expr))) == REG)
{
int regnum_for_replacing = REGNO (SET_SRC (PATTERN (insn_computes_expr)));
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)
{
int regnum_for_replacing = REGNO (SET_DEST (PATTERN (insn_computes_expr)));
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 (PATTERN (insn_computes_expr));
else
to = SET_DEST (PATTERN (insn_computes_expr));
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 reg %d %s insn %d\n",
INSN_UID (insn), 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 (PATTERN (insn_computes_expr))));
new_insn
= emit_insn_after (gen_rtx_SET (VOIDmode, to,
SET_DEST (PATTERN (insn_computes_expr))),
insn_computes_expr);
set_block_num (new_insn, BLOCK_NUM (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, computed in insn %d,\n",
INSN_UID (NEXT_INSN (insn_computes_expr)),
REGNO (SET_SRC (PATTERN (NEXT_INSN (insn_computes_expr)))),
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 set in insn %d\n",
INSN_UID (insn),
REGNO (SET_DEST (PATTERN (NEXT_INSN (insn_computes_expr)))),
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 (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
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 ();
compute_available ();
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, %d insns created\n",
current_function_name, pass,
bytes_used, gcse_subst_count, 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 ()
{
free (cprop_pavloc);
free (cprop_absaltered);
free (cprop_avin);
free (cprop_avout);
}
static void
compute_transp (x, indx, bmap, set_p)
rtx x;
int indx;
sbitmap *bmap;
int set_p;
{
int bb,i;
enum rtx_code code;
char *fmt;
repeat:
if (x == 0)
return;
code = GET_CODE (x);
switch (code)
{
case REG:
{
reg_set *r;
int regno = REGNO (x);
if (set_p)
{
if (regno < FIRST_PSEUDO_REGISTER)
{
for (bb = 0; bb < n_basic_blocks; bb++)
if (TEST_BIT (reg_set_in_block[bb], regno))
SET_BIT (bmap[bb], indx);
}
else
{
for (r = reg_set_table[regno]; r != NULL; r = r->next)
{
bb = BLOCK_NUM (r->insn);
SET_BIT (bmap[bb], indx);
}
}
}
else
{
if (regno < FIRST_PSEUDO_REGISTER)
{
for (bb = 0; bb < n_basic_blocks; bb++)
if (TEST_BIT (reg_set_in_block[bb], regno))
RESET_BIT (bmap[bb], indx);
}
else
{
for (r = reg_set_table[regno]; r != NULL; r = r->next)
{
bb = BLOCK_NUM (r->insn);
RESET_BIT (bmap[bb], indx);
}
}
}
return;
}
case MEM:
if (set_p)
{
for (bb = 0; bb < n_basic_blocks; bb++)
if (mem_set_in_block[bb])
SET_BIT (bmap[bb], indx);
}
else
{
for (bb = 0; bb < n_basic_blocks; bb++)
if (mem_set_in_block[bb])
RESET_BIT (bmap[bb], indx);
}
x = XEXP (x, 0);
goto repeat;
case PC:
case CC0:
case CONST:
case CONST_INT:
case CONST_DOUBLE:
case SYMBOL_REF:
case LABEL_REF:
case ADDR_VEC:
case ADDR_DIFF_VEC:
return;
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;
}
compute_transp (tem, indx, bmap, set_p);
}
else if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
compute_transp (XVECEXP (x, i, j), indx, bmap, set_p);
}
}
}
static void
compute_cprop_avinout ()
{
int bb, changed, passes;
sbitmap_zero (cprop_avin[0]);
sbitmap_vector_ones (cprop_avout, n_basic_blocks);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
for (bb = 0; bb < n_basic_blocks; bb++)
{
if (bb != 0)
sbitmap_intersect_of_predecessors (cprop_avin[bb],
cprop_avout, bb, s_preds);
changed |= sbitmap_union_of_diff (cprop_avout[bb],
cprop_pavloc[bb],
cprop_avin[bb],
cprop_absaltered[bb]);
}
passes++;
}
if (gcse_file)
fprintf (gcse_file, "cprop avail expr computation: %d passes\n", passes);
}
static void
compute_cprop_data ()
{
compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, 1);
compute_cprop_avinout ();
}
struct reg_use {
rtx reg_rtx;
};
#define MAX_USES 8
static struct reg_use reg_use_table[MAX_USES];
static int reg_use_count;
static void
find_used_regs (x)
rtx x;
{
int i;
enum rtx_code code;
char *fmt;
repeat:
if (x == 0)
return;
code = GET_CODE (x);
switch (code)
{
case REG:
if (reg_use_count == MAX_USES)
return;
reg_use_table[reg_use_count].reg_rtx = x;
reg_use_count++;
return;
case MEM:
x = XEXP (x, 0);
goto repeat;
case PC:
case CC0:
case CONST:
case CONST_INT:
case CONST_DOUBLE:
case SYMBOL_REF:
case LABEL_REF:
case CLOBBER:
case ADDR_VEC:
case ADDR_DIFF_VEC:
case ASM_INPUT:
return;
case SET:
if (GET_CODE (SET_DEST (x)) == MEM)
find_used_regs (SET_DEST (x));
x = SET_SRC (x);
goto repeat;
default:
break;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
{
if (i == 0)
{
x = XEXP (x, 0);
goto repeat;
}
find_used_regs (XEXP (x, i));
}
else if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
find_used_regs (XVECEXP (x, i, j));
}
}
}
static int
try_replace_reg (from, to, insn)
rtx from, to, insn;
{
return validate_replace_src (from, to, insn);
}
static struct expr *
find_avail_set (regno, insn)
int regno;
rtx insn;
{
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);
}
return set;
}
static int
cprop_insn (insn, alter_jumps)
rtx insn;
int alter_jumps;
{
struct reg_use *reg_used;
int changed = 0;
if ((GET_CODE (insn) != INSN
&& GET_CODE (insn) != JUMP_INSN)
|| GET_CODE (PATTERN (insn)) != SET)
return 0;
reg_use_count = 0;
find_used_regs (PATTERN (insn));
reg_used = ®_use_table[0];
for ( ; reg_use_count > 0; reg_used++, reg_use_count--)
{
rtx pat, src;
struct expr *set;
int regno = REGNO (reg_used->reg_rtx);
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 (GET_CODE (src) == CONST_INT || GET_CODE (src) == CONST_DOUBLE)
{
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 insn %d with constant ",
regno, 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))
{
rtx copy = copy_rtx (insn);
rtx set = PATTERN (copy);
rtx temp;
replace_rtx (SET_SRC (set), reg_used->reg_rtx, src);
temp = simplify_ternary_operation (GET_CODE (SET_SRC (set)),
GET_MODE (SET_SRC (set)),
GET_MODE (XEXP (SET_SRC (set), 0)),
XEXP (SET_SRC (set), 0),
XEXP (SET_SRC (set), 1),
XEXP (SET_SRC (set), 2));
if (temp)
SET_SRC (set) = temp;
else
continue;
INSN_CODE (copy) = -1;
if ((SET_DEST (set) == pc_rtx
&& (SET_SRC (set) == pc_rtx
|| GET_CODE (SET_SRC (set)) == LABEL_REF))
|| recog (PATTERN (copy), copy, NULL) >= 0)
{
PATTERN (insn) = set;
INSN_CODE (insn) = -1;
if (SET_SRC (set) == pc_rtx && JUMP_LABEL (insn) != 0)
--LABEL_NUSES (JUMP_LABEL (insn));
if (GET_CODE (SET_SRC (set)) == LABEL_REF)
emit_barrier_after (insn);
run_jump_opt_after_gcse = 1;
changed = 1;
const_prop_count++;
if (gcse_file != NULL)
{
fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ",
regno, INSN_UID (insn));
print_rtl (gcse_file, src);
fprintf (gcse_file, "\n");
}
}
}
}
else if (GET_CODE (src) == REG
&& REGNO (src) >= FIRST_PSEUDO_REGISTER
&& REGNO (src) != regno)
{
if (oprs_not_set_p (src, insn))
{
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 with reg %d\n",
regno, INSN_UID (insn), 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 (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
{
changed |= cprop_insn (insn, alter_jumps);
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, %d const props, %d copy props\n",
current_function_name, pass,
bytes_used, const_prop_count, copy_prop_count);
fprintf (gcse_file, "\n");
}
return changed;
}
static sbitmap *transp;
static sbitmap *transpout;
static sbitmap *comp;
static sbitmap *antloc;
static sbitmap *pre_optimal;
static sbitmap *pre_redundant;
static sbitmap *temp_bitmap;
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);
temp_bitmap = sbitmap_vector_alloc (n_blocks, n_exprs);
pre_optimal = sbitmap_vector_alloc (n_blocks, n_exprs);
pre_redundant = sbitmap_vector_alloc (n_blocks, n_exprs);
transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
}
static void
free_pre_mem ()
{
free (transp);
free (comp);
free (antloc);
free (pre_optimal);
free (pre_redundant);
free (transpout);
}
static void
compute_pre_data ()
{
compute_local_properties (transp, comp, antloc, 0);
compute_transpout ();
pre_lcm (n_basic_blocks, n_exprs, s_preds, s_succs, transp,
antloc, pre_redundant, pre_optimal);
}
static int
pre_expr_reaches_here_p (occr_bb, expr, bb, check_pre_comp, visited)
int occr_bb;
struct expr *expr;
int bb;
int check_pre_comp;
char *visited;
{
int_list_ptr pred;
if (visited == NULL)
{
visited = (char *) alloca (n_basic_blocks);
bzero (visited, n_basic_blocks);
}
for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
{
int pred_bb = INT_LIST_VAL (pred);
if (pred_bb == ENTRY_BLOCK
|| visited[pred_bb])
{
}
else if ((!check_pre_comp && occr_bb == pred_bb)
|| TEST_BIT (comp[pred_bb], expr->bitmap_index))
{
if (occr_bb == pred_bb)
return 1;
visited[pred_bb] = 1;
}
else if (! TEST_BIT (transp[pred_bb], expr->bitmap_index))
visited[pred_bb] = 1;
else
{
visited[pred_bb] = 1;
if (pre_expr_reaches_here_p (occr_bb, expr, pred_bb,
check_pre_comp, visited))
return 1;
}
}
return 0;
}
static void
insert_insn_end_bb (expr, bb, pre)
struct expr *expr;
int bb;
int pre;
{
rtx insn = BLOCK_END (bb);
rtx new_insn;
rtx reg = expr->reaching_reg;
int regno = REGNO (reg);
rtx pat, copied_expr;
rtx first_new_insn;
start_sequence ();
copied_expr = copy_rtx (expr->expr);
emit_move_insn (reg, copied_expr);
first_new_insn = get_insns ();
pat = gen_sequence ();
end_sequence ();
if (GET_CODE (insn) == JUMP_INSN)
{
#ifdef HAVE_cc0
rtx note;
#endif
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
&& GET_RTX_CLASS (GET_CODE (maybe_cc0_setter)) == 'i'
&& sets_cc0_p (PATTERN (maybe_cc0_setter)))
insn = maybe_cc0_setter;
}
#endif
new_insn = emit_insn_before (pat, insn);
if (BLOCK_HEAD (bb) == insn)
BLOCK_HEAD (bb) = new_insn;
}
else if (GET_CODE (insn) == CALL_INSN)
{
HARD_REG_SET parm_regs;
int nparm_regs;
rtx p;
if (pre
&& !TEST_BIT (antloc[bb], expr->bitmap_index)
&& !TEST_BIT (transp[bb], expr->bitmap_index))
abort ();
CLEAR_HARD_REG_SET (parm_regs);
nparm_regs = 0;
for (p = CALL_INSN_FUNCTION_USAGE (insn); p ; p = XEXP (p, 1))
if (GET_CODE (XEXP (p, 0)) == USE
&& GET_CODE (XEXP (XEXP (p, 0), 0)) == REG)
{
int regno = REGNO (XEXP (XEXP (p, 0), 0));
if (regno >= FIRST_PSEUDO_REGISTER)
abort ();
SET_HARD_REG_BIT (parm_regs, regno);
nparm_regs++;
}
while (nparm_regs && BLOCK_HEAD (bb) != insn)
{
insn = PREV_INSN (insn);
p = single_set (insn);
if (p && GET_CODE (SET_DEST (p)) == REG
&& REGNO (SET_DEST (p)) < FIRST_PSEUDO_REGISTER
&& TEST_HARD_REG_BIT (parm_regs, REGNO (SET_DEST (p))))
{
CLEAR_HARD_REG_BIT (parm_regs, REGNO (SET_DEST (p)));
nparm_regs--;
}
}
if (GET_CODE (insn) != CODE_LABEL)
{
new_insn = emit_insn_before (pat, insn);
if (BLOCK_HEAD (bb) == insn)
BLOCK_HEAD (bb) = new_insn;
}
else
{
new_insn = emit_insn_after (pat, insn);
}
}
else
{
new_insn = emit_insn_after (pat, insn);
BLOCK_END (bb) = new_insn;
}
if (GET_CODE (pat) == SEQUENCE)
{
int i;
for (i = 0; i < XVECLEN (pat, 0); i++)
{
rtx insn = XVECEXP (pat, 0, i);
set_block_num (insn, bb);
if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
add_label_notes (PATTERN (insn), new_insn);
record_set_insn = insn;
note_stores (PATTERN (insn), record_set_info);
}
}
else
{
add_label_notes (SET_SRC (pat), new_insn);
set_block_num (new_insn, bb);
record_one_set (regno, new_insn);
}
gcse_create_count++;
if (gcse_file)
{
fprintf (gcse_file, "PRE/HOIST: end of bb %d, insn %d, copying expression %d to reg %d\n",
bb, INSN_UID (new_insn), expr->bitmap_index, regno);
}
}
static void
pre_insert (index_map)
struct expr **index_map;
{
int bb, i, set_size;
sbitmap *inserted;
set_size = pre_optimal[0]->size;
inserted = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
sbitmap_vector_zero (inserted, n_basic_blocks);
for (bb = 0; bb < n_basic_blocks; bb++)
{
int indx;
sbitmap_not (temp_bitmap[bb], pre_redundant[bb]);
sbitmap_a_and_b (temp_bitmap[bb], temp_bitmap[bb], pre_optimal[bb]);
for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
{
SBITMAP_ELT_TYPE insert = temp_bitmap[bb]->elms[i];
int j;
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[bb], j)
&& pre_expr_reaches_here_p (bb, expr,
BLOCK_NUM (occr->insn), 0,
NULL))
{
SET_BIT (inserted[bb], j);
insert_insn_end_bb (index_map[j], bb, 1);
}
}
}
}
}
}
}
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_rtx_SET (VOIDmode, reg, SET_DEST (set)),
insn);
set_block_num (new_insn, BLOCK_NUM (insn));
record_one_set (regno, new_insn);
gcse_create_count++;
if (gcse_file)
{
fprintf (gcse_file, "PRE: bb %d, insn %d, copying expression %d in insn %d to reg %d\n",
BLOCK_NUM (insn), INSN_UID (new_insn), indx, INSN_UID (insn), regno);
}
}
static void
pre_insert_copies ()
{
int i, bb;
for (bb = 0; bb < n_basic_blocks; bb++)
{
sbitmap_a_and_b (temp_bitmap[bb], pre_optimal[bb], pre_redundant[bb]);
}
for (i = 0; i < expr_hash_table_size; i++)
{
struct expr *expr;
for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
{
struct occr *occr;
if (expr->reaching_reg == NULL)
continue;
for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
{
struct occr *avail;
if (! occr->deleted_p)
continue;
for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
{
rtx insn = avail->insn;
int bb = BLOCK_NUM (insn);
if (!TEST_BIT (temp_bitmap[bb], expr->bitmap_index))
continue;
if (avail->copied_p)
continue;
if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn)))
continue;
if (! pre_expr_reaches_here_p (BLOCK_NUM (avail->insn), expr,
BLOCK_NUM (occr->insn),
1, NULL))
continue;
pre_insert_copy_insn (expr, insn);
avail->copied_p = 1;
}
}
}
}
}
static int
pre_delete ()
{
int i, bb, changed;
for (bb = 0; bb < n_basic_blocks; bb++)
{
sbitmap_not (temp_bitmap[bb], pre_optimal[bb]);
sbitmap_a_and_b (temp_bitmap[bb], temp_bitmap[bb], pre_redundant[bb]);
}
changed = 0;
for (i = 0; i < expr_hash_table_size; i++)
{
struct expr *expr;
for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
{
struct occr *occr;
int indx = expr->bitmap_index;
for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
{
rtx insn = occr->insn;
rtx set;
int bb = BLOCK_NUM (insn);
if (TEST_BIT (temp_bitmap[bb], 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 bb %d, reaching reg is %d\n",
INSN_UID (insn), indx, bb, REGNO (expr->reaching_reg));
}
}
}
}
}
return changed;
}
static int
pre_gcse ()
{
int i;
int changed;
struct expr **index_map;
index_map = (struct expr **) alloca (n_exprs * sizeof (struct expr *));
bzero ((char *) index_map, n_exprs * sizeof (struct expr *));
for (i = 0; i < expr_hash_table_size; i++)
{
struct expr *expr;
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 ();
pre_insert (index_map);
pre_insert_copies ();
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);
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)
{
alloc_pre_mem (n_basic_blocks, n_exprs);
compute_pre_data ();
changed |= pre_gcse ();
free_pre_mem ();
}
free_expr_hash_table ();
if (gcse_file)
{
fprintf (gcse_file, "\n");
fprintf (gcse_file, "PRE GCSE of %s, pass %d: %d bytes needed, %d substs, %d insns created\n",
current_function_name, pass,
bytes_used, 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;
char *fmt;
if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
{
REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
REG_NOTES (insn));
return;
}
fmt = GET_RTX_FORMAT (code);
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
add_label_notes (XEXP (x, i), 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;
sbitmap_vector_ones (transpout, n_basic_blocks);
for (bb = 0; bb < n_basic_blocks; ++bb)
{
int i;
if (GET_CODE (BLOCK_END (bb)) != CALL_INSN)
continue;
for (i = 0; i < expr_hash_table_size; i++)
{
struct expr *expr;
for (expr = expr_hash_table[i]; expr ; expr = expr->next_same_hash)
if (GET_CODE (expr->expr) == MEM)
{
rtx addr = XEXP (expr->expr, 0);
if (GET_CODE (addr) == SYMBOL_REF
&& CONSTANT_POOL_ADDRESS_P (addr))
continue;
RESET_BIT (transpout[bb], expr->bitmap_index);
}
}
}
}