#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "tm_p.h"
#include "insn-config.h"
#include "recog.h"
#include "function.h"
#include "regs.h"
#include "alloc-pool.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "sbitmap.h"
#include "bitmap.h"
#include "df.h"
#define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
do \
{ \
unsigned int node_; \
bitmap_iterator bi; \
EXECUTE_IF_SET_IN_BITMAP (BITMAP, MIN, node_, bi) \
{ \
(BB) = BASIC_BLOCK (node_); \
CODE; \
} \
} \
while (0)
static alloc_pool df_ref_pool;
static alloc_pool df_link_pool;
static struct df *ddf;
static void df_reg_table_realloc (struct df *, int);
static void df_insn_table_realloc (struct df *, unsigned int);
static void df_bb_table_realloc (struct df *, unsigned int);
static void df_bitmaps_alloc (struct df *, bitmap, int);
static void df_bitmaps_free (struct df *, int);
static void df_free (struct df *);
static void df_alloc (struct df *, int);
static rtx df_reg_use_gen (unsigned int);
static inline struct df_link *df_link_create (struct ref *, struct df_link *);
static struct df_link *df_ref_unlink (struct df_link **, struct ref *);
static void df_def_unlink (struct df *, struct ref *);
static void df_use_unlink (struct df *, struct ref *);
static void df_insn_refs_unlink (struct df *, basic_block, rtx);
#if 0
static void df_bb_refs_unlink (struct df *, basic_block);
static void df_refs_unlink (struct df *, bitmap);
#endif
static struct ref *df_ref_create (struct df *, rtx, rtx *, rtx,
enum df_ref_type, enum df_ref_flags);
static void df_ref_record_1 (struct df *, rtx, rtx *, rtx, enum df_ref_type,
enum df_ref_flags);
static void df_ref_record (struct df *, rtx, rtx *, rtx, enum df_ref_type,
enum df_ref_flags);
static void df_def_record_1 (struct df *, rtx, basic_block, rtx);
static void df_defs_record (struct df *, rtx, basic_block, rtx);
static void df_uses_record (struct df *, rtx *, enum df_ref_type,
basic_block, rtx, enum df_ref_flags);
static void df_insn_refs_record (struct df *, basic_block, rtx);
static void df_bb_refs_record (struct df *, basic_block);
static void df_refs_record (struct df *, bitmap);
static void df_bb_reg_def_chain_create (struct df *, basic_block);
static void df_reg_def_chain_create (struct df *, bitmap, bool);
static void df_bb_reg_use_chain_create (struct df *, basic_block);
static void df_reg_use_chain_create (struct df *, bitmap, bool);
static void df_bb_du_chain_create (struct df *, basic_block, bitmap);
static void df_du_chain_create (struct df *, bitmap);
static void df_bb_ud_chain_create (struct df *, basic_block);
static void df_ud_chain_create (struct df *, bitmap);
static void df_bb_rd_local_compute (struct df *, basic_block, bitmap);
static void df_rd_local_compute (struct df *, bitmap);
static void df_bb_ru_local_compute (struct df *, basic_block);
static void df_ru_local_compute (struct df *, bitmap);
static void df_bb_lr_local_compute (struct df *, basic_block);
static void df_lr_local_compute (struct df *, bitmap);
static void df_bb_reg_info_compute (struct df *, basic_block, bitmap);
static void df_reg_info_compute (struct df *, bitmap);
static int df_bb_luids_set (struct df *df, basic_block);
static int df_luids_set (struct df *df, bitmap);
static int df_modified_p (struct df *, bitmap);
static int df_refs_queue (struct df *);
static int df_refs_process (struct df *);
static int df_bb_refs_update (struct df *, basic_block);
static int df_refs_update (struct df *, bitmap);
static void df_analyze_1 (struct df *, bitmap, int, int);
static void df_insns_modify (struct df *, basic_block, rtx, rtx);
static int df_rtx_mem_replace (rtx *, void *);
static int df_rtx_reg_replace (rtx *, void *);
void df_refs_reg_replace (struct df *, bitmap, struct df_link *, rtx, rtx);
static int df_def_dominates_all_uses_p (struct df *, struct ref *def);
static int df_def_dominates_uses_p (struct df *, struct ref *def, bitmap);
static struct ref *df_bb_insn_regno_last_use_find (struct df *, basic_block,
rtx, unsigned int);
static struct ref *df_bb_insn_regno_first_def_find (struct df *, basic_block,
rtx, unsigned int);
static void df_chain_dump (struct df_link *, FILE *file);
static void df_chain_dump_regno (struct df_link *, FILE *file);
static void df_regno_debug (struct df *, unsigned int, FILE *);
static void df_ref_debug (struct df *, struct ref *, FILE *);
static void df_rd_transfer_function (int, int *, void *, void *, void *,
void *, void *);
static void df_ru_transfer_function (int, int *, void *, void *, void *,
void *, void *);
static void df_lr_transfer_function (int, int *, void *, void *, void *,
void *, void *);
static void hybrid_search (basic_block, struct dataflow *,
sbitmap, sbitmap, sbitmap);
static void
df_insn_table_realloc (struct df *df, unsigned int size)
{
size++;
if (size <= df->insn_size)
return;
size += df->insn_size / 4;
df->insns = xrealloc (df->insns, size * sizeof (struct insn_info));
memset (df->insns + df->insn_size, 0,
(size - df->insn_size) * sizeof (struct insn_info));
df->insn_size = size;
if (! df->insns_modified)
{
df->insns_modified = BITMAP_ALLOC (NULL);
bitmap_zero (df->insns_modified);
}
}
static void
df_bb_table_realloc (struct df *df, unsigned int size)
{
size++;
if (size <= df->n_bbs)
return;
size += df->n_bbs / 4;
df->bbs = xrealloc (df->bbs, size * sizeof (struct bb_info));
memset (df->bbs + df->n_bbs, 0, (size - df->n_bbs) * sizeof (struct bb_info));
df->n_bbs = size;
}
static void
df_reg_table_realloc (struct df *df, int size)
{
if (! size)
size = df->reg_size / 4;
size += df->reg_size;
if (size < max_reg_num ())
size = max_reg_num ();
df->regs = xrealloc (df->regs, size * sizeof (struct reg_info));
df->reg_def_last = xrealloc (df->reg_def_last,
size * sizeof (struct ref *));
memset (df->regs + df->reg_size, 0,
(size - df->reg_size) * sizeof (struct reg_info));
df->reg_size = size;
}
static void
df_bitmaps_alloc (struct df *df, bitmap blocks, int flags)
{
basic_block bb;
df->n_defs = df->def_id;
df->n_uses = df->use_id;
if (!blocks)
blocks = df->all_blocks;
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
if (flags & DF_RD)
{
if (!bb_info->rd_in)
{
bb_info->rd_kill = BITMAP_ALLOC (NULL);
bb_info->rd_gen = BITMAP_ALLOC (NULL);
bb_info->rd_in = BITMAP_ALLOC (NULL);
bb_info->rd_out = BITMAP_ALLOC (NULL);
}
else
{
bitmap_clear (bb_info->rd_kill);
bitmap_clear (bb_info->rd_gen);
bitmap_clear (bb_info->rd_in);
bitmap_clear (bb_info->rd_out);
}
}
if (flags & DF_RU)
{
if (!bb_info->ru_in)
{
bb_info->ru_kill = BITMAP_ALLOC (NULL);
bb_info->ru_gen = BITMAP_ALLOC (NULL);
bb_info->ru_in = BITMAP_ALLOC (NULL);
bb_info->ru_out = BITMAP_ALLOC (NULL);
}
else
{
bitmap_clear (bb_info->ru_kill);
bitmap_clear (bb_info->ru_gen);
bitmap_clear (bb_info->ru_in);
bitmap_clear (bb_info->ru_out);
}
}
if (flags & DF_LR)
{
if (!bb_info->lr_in)
{
bb_info->lr_def = BITMAP_ALLOC (NULL);
bb_info->lr_use = BITMAP_ALLOC (NULL);
bb_info->lr_in = BITMAP_ALLOC (NULL);
bb_info->lr_out = BITMAP_ALLOC (NULL);
}
else
{
bitmap_clear (bb_info->lr_def);
bitmap_clear (bb_info->lr_use);
bitmap_clear (bb_info->lr_in);
bitmap_clear (bb_info->lr_out);
}
}
});
}
static void
df_bitmaps_free (struct df *df, int flags)
{
basic_block bb;
FOR_EACH_BB (bb)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
if (!bb_info)
continue;
if ((flags & DF_RD) && bb_info->rd_in)
{
BITMAP_FREE (bb_info->rd_kill);
bb_info->rd_kill = NULL;
BITMAP_FREE (bb_info->rd_gen);
bb_info->rd_gen = NULL;
BITMAP_FREE (bb_info->rd_in);
bb_info->rd_in = NULL;
BITMAP_FREE (bb_info->rd_out);
bb_info->rd_out = NULL;
}
if ((flags & DF_RU) && bb_info->ru_in)
{
BITMAP_FREE (bb_info->ru_kill);
bb_info->ru_kill = NULL;
BITMAP_FREE (bb_info->ru_gen);
bb_info->ru_gen = NULL;
BITMAP_FREE (bb_info->ru_in);
bb_info->ru_in = NULL;
BITMAP_FREE (bb_info->ru_out);
bb_info->ru_out = NULL;
}
if ((flags & DF_LR) && bb_info->lr_in)
{
BITMAP_FREE (bb_info->lr_def);
bb_info->lr_def = NULL;
BITMAP_FREE (bb_info->lr_use);
bb_info->lr_use = NULL;
BITMAP_FREE (bb_info->lr_in);
bb_info->lr_in = NULL;
BITMAP_FREE (bb_info->lr_out);
bb_info->lr_out = NULL;
}
}
df->flags &= ~(flags & (DF_RD | DF_RU | DF_LR));
}
static void
df_alloc (struct df *df, int n_regs)
{
int n_insns;
basic_block bb;
df_link_pool = create_alloc_pool ("df_link pool", sizeof (struct df_link),
100);
df_ref_pool = create_alloc_pool ("df_ref pool", sizeof (struct ref), 100);
n_insns = get_max_uid () + 1;
df->def_id = 0;
df->n_defs = 0;
df->def_size = n_insns;
df->defs = xmalloc (df->def_size * sizeof (*df->defs));
df->use_id = 0;
df->n_uses = 0;
df->use_size = n_insns * 2;
df->uses = xmalloc (df->use_size * sizeof (*df->uses));
df->n_regs = n_regs;
df->n_bbs = last_basic_block;
df_insn_table_realloc (df, n_insns);
df_reg_table_realloc (df, df->n_regs);
df->bbs_modified = BITMAP_ALLOC (NULL);
bitmap_zero (df->bbs_modified);
df->flags = 0;
df->bbs = xcalloc (last_basic_block, sizeof (struct bb_info));
df->all_blocks = BITMAP_ALLOC (NULL);
FOR_EACH_BB (bb)
bitmap_set_bit (df->all_blocks, bb->index);
}
static void
df_free (struct df *df)
{
df_bitmaps_free (df, DF_ALL);
if (df->bbs)
free (df->bbs);
df->bbs = 0;
if (df->insns)
free (df->insns);
df->insns = 0;
df->insn_size = 0;
if (df->defs)
free (df->defs);
df->defs = 0;
df->def_size = 0;
df->def_id = 0;
if (df->uses)
free (df->uses);
df->uses = 0;
df->use_size = 0;
df->use_id = 0;
if (df->regs)
free (df->regs);
df->regs = 0;
df->reg_size = 0;
BITMAP_FREE (df->bbs_modified);
df->bbs_modified = 0;
BITMAP_FREE (df->insns_modified);
df->insns_modified = 0;
BITMAP_FREE (df->all_blocks);
df->all_blocks = 0;
free_alloc_pool (df_ref_pool);
free_alloc_pool (df_link_pool);
}
static rtx df_reg_use_gen (unsigned int regno)
{
rtx reg;
rtx use;
reg = regno_reg_rtx[regno];
use = gen_rtx_USE (GET_MODE (reg), reg);
return use;
}
static inline struct df_link *
df_link_create (struct ref *ref, struct df_link *next)
{
struct df_link *link;
link = pool_alloc (df_link_pool);
link->next = next;
link->ref = ref;
return link;
}
static void
free_reg_ref_chain (struct df_link **chain)
{
struct df_link *act, *next;
for (act = *chain; act; act = next)
{
next = act->next;
pool_free (df_link_pool, act);
}
*chain = NULL;
}
static struct df_link *
df_ref_unlink (struct df_link **phead, struct ref *ref)
{
struct df_link *link = *phead;
if (link)
{
if (! link->next)
{
gcc_assert (link->ref == ref);
*phead = NULL;
}
else
{
if (link->ref == ref)
*phead = link->next;
else
{
for (; link->next; link = link->next)
{
if (link->next->ref == ref)
{
link->next = link->next->next;
return link->next;
}
}
}
}
}
return link;
}
int
df_ref_remove (struct df *df, struct ref *ref)
{
if (DF_REF_REG_DEF_P (ref))
{
df_def_unlink (df, ref);
df_ref_unlink (&df->insns[DF_REF_INSN_UID (ref)].defs, ref);
}
else
{
df_use_unlink (df, ref);
df_ref_unlink (&df->insns[DF_REF_INSN_UID (ref)].uses, ref);
}
return 1;
}
static void
df_def_unlink (struct df *df ATTRIBUTE_UNUSED, struct ref *def)
{
struct df_link *du_link;
unsigned int dregno = DF_REF_REGNO (def);
for (du_link = DF_REF_CHAIN (def); du_link; du_link = du_link->next)
{
struct ref *use = du_link->ref;
df_ref_unlink (&DF_REF_CHAIN (use), def);
}
DF_REF_CHAIN (def) = 0;
df_ref_unlink (&df->regs[dregno].defs, def);
df->defs[DF_REF_ID (def)] = 0;
}
static void
df_use_unlink (struct df *df ATTRIBUTE_UNUSED, struct ref *use)
{
struct df_link *ud_link;
unsigned int uregno = DF_REF_REGNO (use);
for (ud_link = DF_REF_CHAIN (use); ud_link; ud_link = ud_link->next)
{
struct ref *def = ud_link->ref;
df_ref_unlink (&DF_REF_CHAIN (def), use);
}
DF_REF_CHAIN (use) = 0;
df_ref_unlink (&df->regs[uregno].uses, use);
df->uses[DF_REF_ID (use)] = 0;
}
static struct ref *
df_ref_create (struct df *df, rtx reg, rtx *loc, rtx insn,
enum df_ref_type ref_type, enum df_ref_flags ref_flags)
{
struct ref *this_ref;
this_ref = pool_alloc (df_ref_pool);
DF_REF_REG (this_ref) = reg;
DF_REF_LOC (this_ref) = loc;
DF_REF_INSN (this_ref) = insn;
DF_REF_CHAIN (this_ref) = 0;
DF_REF_TYPE (this_ref) = ref_type;
DF_REF_FLAGS (this_ref) = ref_flags;
DF_REF_DATA (this_ref) = NULL;
if (ref_type == DF_REF_REG_DEF)
{
if (df->def_id >= df->def_size)
{
df->def_size += (df->def_size / 4);
df->defs = xrealloc (df->defs,
df->def_size * sizeof (*df->defs));
}
DF_REF_ID (this_ref) = df->def_id;
df->defs[df->def_id++] = this_ref;
}
else
{
if (df->use_id >= df->use_size)
{
df->use_size += (df->use_size / 4);
df->uses = xrealloc (df->uses,
df->use_size * sizeof (*df->uses));
}
DF_REF_ID (this_ref) = df->use_id;
df->uses[df->use_id++] = this_ref;
}
return this_ref;
}
static void
df_ref_record_1 (struct df *df, rtx reg, rtx *loc, rtx insn,
enum df_ref_type ref_type, enum df_ref_flags ref_flags)
{
df_ref_create (df, reg, loc, insn, ref_type, ref_flags);
}
static void
df_ref_record (struct df *df, rtx reg, rtx *loc, rtx insn,
enum df_ref_type ref_type, enum df_ref_flags ref_flags)
{
unsigned int regno;
gcc_assert (REG_P (reg) || GET_CODE (reg) == SUBREG);
if (GET_CODE (reg) == SUBREG
&& (GET_MODE_SIZE (GET_MODE (reg)) < GET_MODE_SIZE (word_mode)
|| GET_MODE_SIZE (GET_MODE (reg))
>= GET_MODE_SIZE (GET_MODE (SUBREG_REG (reg)))))
{
loc = &SUBREG_REG (reg);
reg = *loc;
ref_flags |= DF_REF_STRIPPED;
}
regno = REGNO (GET_CODE (reg) == SUBREG ? SUBREG_REG (reg) : reg);
if (regno < FIRST_PSEUDO_REGISTER)
{
int i;
int endregno;
if (! (df->flags & DF_HARD_REGS))
return;
endregno = hard_regno_nregs[regno][GET_MODE (reg)];
if (GET_CODE (reg) == SUBREG)
regno += subreg_regno_offset (regno, GET_MODE (SUBREG_REG (reg)),
SUBREG_BYTE (reg), GET_MODE (reg));
endregno += regno;
for (i = regno; i < endregno; i++)
df_ref_record_1 (df, regno_reg_rtx[i],
loc, insn, ref_type, ref_flags);
}
else
{
df_ref_record_1 (df, reg, loc, insn, ref_type, ref_flags);
}
}
bool
read_modify_subreg_p (rtx x)
{
unsigned int isize, osize;
if (GET_CODE (x) != SUBREG)
return false;
isize = GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)));
osize = GET_MODE_SIZE (GET_MODE (x));
return (isize > osize && isize > UNITS_PER_WORD);
}
static void
df_def_record_1 (struct df *df, rtx x, basic_block bb, rtx insn)
{
rtx *loc;
rtx dst;
enum df_ref_flags flags = 0;
if (GET_CODE (x) == EXPR_LIST || GET_CODE (x) == CLOBBER)
loc = &XEXP (x, 0);
else
loc = &SET_DEST (x);
dst = *loc;
if (GET_CODE (dst) == PARALLEL)
{
int i;
for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
{
rtx temp = XVECEXP (dst, 0, i);
if (GET_CODE (temp) == EXPR_LIST || GET_CODE (temp) == CLOBBER
|| GET_CODE (temp) == SET)
df_def_record_1 (df, temp, bb, insn);
}
return;
}
while (GET_CODE (dst) == STRICT_LOW_PART
|| GET_CODE (dst) == ZERO_EXTRACT
|| read_modify_subreg_p (dst))
{
if (GET_CODE (dst) == STRICT_LOW_PART)
{
loc = &XEXP (dst, 0);
dst = *loc;
}
loc = &XEXP (dst, 0);
dst = *loc;
flags |= DF_REF_READ_WRITE;
}
if (REG_P (dst)
|| (GET_CODE (dst) == SUBREG && REG_P (SUBREG_REG (dst))))
df_ref_record (df, dst, loc, insn, DF_REF_REG_DEF, flags);
}
static void
df_defs_record (struct df *df, rtx x, basic_block bb, rtx insn)
{
RTX_CODE code = GET_CODE (x);
if (code == SET || code == CLOBBER)
{
df_def_record_1 (df, x, bb, insn);
}
else if (code == PARALLEL)
{
int i;
for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
{
code = GET_CODE (XVECEXP (x, 0, i));
if (code == SET || code == CLOBBER)
df_def_record_1 (df, XVECEXP (x, 0, i), bb, insn);
}
}
}
static void
df_uses_record (struct df *df, rtx *loc, enum df_ref_type ref_type,
basic_block bb, rtx insn, enum df_ref_flags flags)
{
RTX_CODE code;
rtx x;
retry:
x = *loc;
if (!x)
return;
code = GET_CODE (x);
switch (code)
{
case LABEL_REF:
case SYMBOL_REF:
case CONST_INT:
case CONST:
case CONST_DOUBLE:
case CONST_VECTOR:
case PC:
case CC0:
case ADDR_VEC:
case ADDR_DIFF_VEC:
return;
case CLOBBER:
if (MEM_P (XEXP (x, 0)))
df_uses_record (df, &XEXP (XEXP (x, 0), 0),
DF_REF_REG_MEM_STORE, bb, insn, flags);
return;
case MEM:
df_uses_record (df, &XEXP (x, 0), DF_REF_REG_MEM_LOAD, bb, insn, 0);
return;
case SUBREG:
if (!REG_P (SUBREG_REG (x)))
{
loc = &SUBREG_REG (x);
df_uses_record (df, loc, ref_type, bb, insn, flags);
return;
}
case REG:
df_ref_record (df, x, loc, insn, ref_type, flags);
return;
case SET:
{
rtx dst = SET_DEST (x);
df_uses_record (df, &SET_SRC (x), DF_REF_REG_USE, bb, insn, 0);
switch (GET_CODE (dst))
{
case SUBREG:
if (read_modify_subreg_p (dst))
{
df_uses_record (df, &SUBREG_REG (dst), DF_REF_REG_USE, bb,
insn, DF_REF_READ_WRITE);
break;
}
case REG:
case PARALLEL:
case PC:
case CC0:
break;
case MEM:
df_uses_record (df, &XEXP (dst, 0),
DF_REF_REG_MEM_STORE,
bb, insn, 0);
break;
case STRICT_LOW_PART:
dst = XEXP (dst, 0);
gcc_assert (GET_CODE (dst) == SUBREG);
df_uses_record (df, &SUBREG_REG (dst), DF_REF_REG_USE, bb,
insn, DF_REF_READ_WRITE);
break;
case ZERO_EXTRACT:
case SIGN_EXTRACT:
df_uses_record (df, &XEXP (dst, 0), DF_REF_REG_USE, bb, insn,
DF_REF_READ_WRITE);
df_uses_record (df, &XEXP (dst, 1), DF_REF_REG_USE, bb, insn, 0);
df_uses_record (df, &XEXP (dst, 2), DF_REF_REG_USE, bb, insn, 0);
dst = XEXP (dst, 0);
break;
default:
gcc_unreachable ();
}
return;
}
case RETURN:
break;
case ASM_OPERANDS:
case UNSPEC_VOLATILE:
case TRAP_IF:
case ASM_INPUT:
{
if (code == ASM_OPERANDS)
{
int j;
for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
df_uses_record (df, &ASM_OPERANDS_INPUT (x, j),
DF_REF_REG_USE, bb, insn, 0);
return;
}
break;
}
case PRE_DEC:
case POST_DEC:
case PRE_INC:
case POST_INC:
case PRE_MODIFY:
case POST_MODIFY:
df_ref_record (df, XEXP (x, 0), &XEXP (x, 0), insn, DF_REF_REG_DEF, DF_REF_READ_WRITE);
default:
break;
}
{
const char *fmt = GET_RTX_FORMAT (code);
int i;
for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
{
if (fmt[i] == 'e')
{
if (i == 0)
{
loc = &XEXP (x, 0);
goto retry;
}
df_uses_record (df, &XEXP (x, i), ref_type, bb, insn, flags);
}
else if (fmt[i] == 'E')
{
int j;
for (j = 0; j < XVECLEN (x, i); j++)
df_uses_record (df, &XVECEXP (x, i, j), ref_type,
bb, insn, flags);
}
}
}
}
static void
df_insn_refs_record (struct df *df, basic_block bb, rtx insn)
{
int i;
if (INSN_P (insn))
{
rtx note;
df_defs_record (df, PATTERN (insn), bb, insn);
if (df->flags & DF_EQUIV_NOTES)
for (note = REG_NOTES (insn); note;
note = XEXP (note, 1))
{
switch (REG_NOTE_KIND (note))
{
case REG_EQUIV:
case REG_EQUAL:
df_uses_record (df, &XEXP (note, 0), DF_REF_REG_USE,
bb, insn, 0);
default:
break;
}
}
if (CALL_P (insn))
{
rtx note;
rtx x;
for (note = CALL_INSN_FUNCTION_USAGE (insn); note;
note = XEXP (note, 1))
{
if (GET_CODE (XEXP (note, 0)) == USE)
df_uses_record (df, &XEXP (XEXP (note, 0), 0), DF_REF_REG_USE,
bb, insn, 0);
}
x = df_reg_use_gen (STACK_POINTER_REGNUM);
df_uses_record (df, &XEXP (x, 0), DF_REF_REG_USE, bb, insn, 0);
if (df->flags & DF_HARD_REGS)
{
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (global_regs[i])
{
x = df_reg_use_gen (i);
df_uses_record (df, &XEXP (x, 0),
DF_REF_REG_USE, bb, insn, 0);
}
}
}
df_uses_record (df, &PATTERN (insn),
DF_REF_REG_USE, bb, insn, 0);
if (CALL_P (insn))
{
rtx note;
for (note = CALL_INSN_FUNCTION_USAGE (insn);
note;
note = XEXP (note, 1))
if (GET_CODE (XEXP (note, 0)) == CLOBBER)
df_defs_record (df, XEXP (note, 0), bb, insn);
}
}
}
static void
df_bb_refs_record (struct df *df, basic_block bb)
{
rtx insn;
FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
{
df_insn_refs_record (df, bb, insn);
}
}
}
static void
df_refs_record (struct df *df, bitmap blocks)
{
basic_block bb;
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_refs_record (df, bb);
});
}
static void
df_bb_reg_def_chain_create (struct df *df, basic_block bb)
{
rtx insn;
FOR_BB_INSNS_REVERSE (bb, insn)
{
struct df_link *link;
unsigned int uid = INSN_UID (insn);
if (! INSN_P (insn))
continue;
for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
unsigned int dregno = DF_REF_REGNO (def);
if (DF_REF_ID (def) < df->def_id_save)
continue;
df->regs[dregno].defs = df_link_create (def, df->regs[dregno].defs);
}
}
}
static void
df_reg_def_chain_create (struct df *df, bitmap blocks, bool redo)
{
basic_block bb;
#ifdef ENABLE_CHECKING
unsigned regno;
#endif
unsigned old_def_id_save = df->def_id_save;
if (redo)
{
#ifdef ENABLE_CHECKING
for (regno = 0; regno < df->n_regs; regno++)
gcc_assert (!df->regs[regno].defs);
#endif
df->def_id_save = 0;
}
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_reg_def_chain_create (df, bb);
});
df->def_id_save = old_def_id_save;
}
static void
df_reg_def_chain_clean (struct df *df)
{
unsigned regno;
for (regno = 0; regno < df->n_regs; regno++)
free_reg_ref_chain (&df->regs[regno].defs);
}
static void
df_bb_reg_use_chain_create (struct df *df, basic_block bb)
{
rtx insn;
FOR_BB_INSNS (bb, insn)
{
struct df_link *link;
unsigned int uid = INSN_UID (insn);
if (! INSN_P (insn))
continue;
for (link = df->insns[uid].uses; link; link = link->next)
{
struct ref *use = link->ref;
unsigned int uregno = DF_REF_REGNO (use);
if (DF_REF_ID (use) < df->use_id_save)
continue;
df->regs[uregno].uses
= df_link_create (use, df->regs[uregno].uses);
}
}
}
static void
df_reg_use_chain_create (struct df *df, bitmap blocks, bool redo)
{
basic_block bb;
#ifdef ENABLE_CHECKING
unsigned regno;
#endif
unsigned old_use_id_save = df->use_id_save;
if (redo)
{
#ifdef ENABLE_CHECKING
for (regno = 0; regno < df->n_regs; regno++)
gcc_assert (!df->regs[regno].uses);
#endif
df->use_id_save = 0;
}
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_reg_use_chain_create (df, bb);
});
df->use_id_save = old_use_id_save;
}
static void
df_reg_use_chain_clean (struct df *df)
{
unsigned regno;
for (regno = 0; regno < df->n_regs; regno++)
free_reg_ref_chain (&df->regs[regno].uses);
}
static void
df_bb_du_chain_create (struct df *df, basic_block bb, bitmap ru)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
bitmap_copy (ru, bb_info->ru_out);
FOR_BB_INSNS_REVERSE (bb, insn)
{
struct df_link *def_link;
struct df_link *use_link;
unsigned int uid = INSN_UID (insn);
if (! INSN_P (insn))
continue;
for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
{
struct ref *def = def_link->ref;
unsigned int dregno = DF_REF_REGNO (def);
DF_REF_CHAIN (def) = 0;
for (use_link = df->regs[dregno].uses; use_link;
use_link = use_link->next)
{
struct ref *use = use_link->ref;
if (bitmap_bit_p (ru, DF_REF_ID (use)))
{
DF_REF_CHAIN (def)
= df_link_create (use, DF_REF_CHAIN (def));
bitmap_clear_bit (ru, DF_REF_ID (use));
}
}
}
for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
{
struct ref *use = use_link->ref;
bitmap_set_bit (ru, DF_REF_ID (use));
}
}
}
static void
df_du_chain_create (struct df *df, bitmap blocks)
{
bitmap ru;
basic_block bb;
ru = BITMAP_ALLOC (NULL);
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_du_chain_create (df, bb, ru);
});
BITMAP_FREE (ru);
}
static void
df_bb_ud_chain_create (struct df *df, basic_block bb)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
struct ref **reg_def_last = df->reg_def_last;
rtx insn;
memset (reg_def_last, 0, df->n_regs * sizeof (struct ref *));
FOR_BB_INSNS (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_link *use_link;
struct df_link *def_link;
if (! INSN_P (insn))
continue;
for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
{
struct ref *use = use_link->ref;
unsigned int regno = DF_REF_REGNO (use);
DF_REF_CHAIN (use) = 0;
if (reg_def_last[regno])
{
DF_REF_CHAIN (use)
= df_link_create (reg_def_last[regno], 0);
}
else
{
for (def_link = df->regs[regno].defs; def_link;
def_link = def_link->next)
{
struct ref *def = def_link->ref;
if (bitmap_bit_p (bb_info->rd_in, DF_REF_ID (def)))
{
DF_REF_CHAIN (use)
= df_link_create (def, DF_REF_CHAIN (use));
}
}
}
}
for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
{
struct ref *def = def_link->ref;
int dregno = DF_REF_REGNO (def);
reg_def_last[dregno] = def;
}
}
}
static void
df_ud_chain_create (struct df *df, bitmap blocks)
{
basic_block bb;
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_ud_chain_create (df, bb);
});
}
static void
df_rd_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, void *in,
void *out, void *gen, void *kill,
void *data ATTRIBUTE_UNUSED)
{
*changed = bitmap_ior_and_compl (out, gen, in, kill);
}
static void
df_ru_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, void *in,
void *out, void *gen, void *kill,
void *data ATTRIBUTE_UNUSED)
{
*changed = bitmap_ior_and_compl (in, gen, out, kill);
}
static void
df_lr_transfer_function (int bb ATTRIBUTE_UNUSED, int *changed, void *in,
void *out, void *use, void *def,
void *data ATTRIBUTE_UNUSED)
{
*changed = bitmap_ior_and_compl (in, use, out, def);
}
static void
df_bb_rd_local_compute (struct df *df, basic_block bb, bitmap call_killed_defs)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
bitmap seen = BITMAP_ALLOC (NULL);
bool call_seen = false;
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_link *def_link;
if (! INSN_P (insn))
continue;
for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
{
struct ref *def = def_link->ref;
unsigned int regno = DF_REF_REGNO (def);
struct df_link *def2_link;
if (bitmap_bit_p (seen, regno)
|| (call_seen
&& regno < FIRST_PSEUDO_REGISTER
&& TEST_HARD_REG_BIT (regs_invalidated_by_call, regno)))
continue;
for (def2_link = df->regs[regno].defs; def2_link;
def2_link = def2_link->next)
{
struct ref *def2 = def2_link->ref;
bitmap_set_bit (bb_info->rd_kill, DF_REF_ID (def2));
}
bitmap_set_bit (bb_info->rd_gen, DF_REF_ID (def));
bitmap_set_bit (seen, regno);
}
if (CALL_P (insn) && (df->flags & DF_HARD_REGS))
{
bitmap_ior_into (bb_info->rd_kill, call_killed_defs);
call_seen = 1;
}
}
BITMAP_FREE (seen);
}
static void
df_rd_local_compute (struct df *df, bitmap blocks)
{
basic_block bb;
bitmap killed_by_call = NULL;
unsigned regno;
struct df_link *def_link;
if (df->flags & DF_HARD_REGS)
{
killed_by_call = BITMAP_ALLOC (NULL);
for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
{
if (!TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
continue;
for (def_link = df->regs[regno].defs;
def_link;
def_link = def_link->next)
bitmap_set_bit (killed_by_call, DF_REF_ID (def_link->ref));
}
}
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_rd_local_compute (df, bb, killed_by_call);
});
if (df->flags & DF_HARD_REGS)
BITMAP_FREE (killed_by_call);
}
static void
df_bb_ru_local_compute (struct df *df, basic_block bb)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_link *def_link;
struct df_link *use_link;
if (! INSN_P (insn))
continue;
for (def_link = df->insns[uid].defs; def_link; def_link = def_link->next)
{
struct ref *def = def_link->ref;
unsigned int dregno = DF_REF_REGNO (def);
for (use_link = df->regs[dregno].uses; use_link;
use_link = use_link->next)
{
struct ref *use = use_link->ref;
bitmap_set_bit (bb_info->ru_kill, DF_REF_ID (use));
bitmap_clear_bit (bb_info->ru_gen, DF_REF_ID (use));
}
}
for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
{
struct ref *use = use_link->ref;
bitmap_set_bit (bb_info->ru_gen, DF_REF_ID (use));
}
}
}
static void
df_ru_local_compute (struct df *df, bitmap blocks)
{
basic_block bb;
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_ru_local_compute (df, bb);
});
}
static void
df_bb_lr_local_compute (struct df *df, basic_block bb)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
struct df_link *link;
if (! INSN_P (insn))
continue;
for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
unsigned int dregno = DF_REF_REGNO (def);
bitmap_set_bit (bb_info->lr_def, dregno);
bitmap_clear_bit (bb_info->lr_use, dregno);
}
for (link = df->insns[uid].uses; link; link = link->next)
{
struct ref *use = link->ref;
bitmap_set_bit (bb_info->lr_use, DF_REF_REGNO (use));
}
}
}
static void
df_lr_local_compute (struct df *df, bitmap blocks)
{
basic_block bb;
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_lr_local_compute (df, bb);
});
}
static void
df_bb_reg_info_compute (struct df *df, basic_block bb, bitmap live)
{
struct reg_info *reg_info = df->regs;
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
bitmap_copy (live, bb_info->lr_out);
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
unsigned int regno;
struct df_link *link;
bitmap_iterator bi;
if (! INSN_P (insn))
continue;
for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
unsigned int dregno = DF_REF_REGNO (def);
bitmap_clear_bit (live, dregno);
reg_info[dregno].n_defs++;
}
for (link = df->insns[uid].uses; link; link = link->next)
{
struct ref *use = link->ref;
unsigned int uregno = DF_REF_REGNO (use);
bitmap_set_bit (live, uregno);
reg_info[uregno].n_uses++;
}
EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
{
reg_info[regno].lifetime++;
}
}
}
static void
df_reg_info_compute (struct df *df, bitmap blocks)
{
basic_block bb;
bitmap live;
live = BITMAP_ALLOC (NULL);
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_reg_info_compute (df, bb, live);
});
BITMAP_FREE (live);
}
static int
df_bb_luids_set (struct df *df, basic_block bb)
{
rtx insn;
int luid = 0;
FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
DF_INSN_LUID (df, insn) = luid++;
DF_INSN_LUID (df, insn) = luid;
}
return luid;
}
static int
df_luids_set (struct df *df, bitmap blocks)
{
basic_block bb;
int total = 0;
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
total += df_bb_luids_set (df, bb);
});
return total;
}
static void
df_analyze_1 (struct df *df, bitmap blocks, int flags, int update)
{
int aflags;
int dflags;
int i;
basic_block bb;
struct dataflow dflow;
dflags = 0;
aflags = flags;
if (flags & DF_UD_CHAIN)
aflags |= DF_RD | DF_RD_CHAIN;
if (flags & DF_DU_CHAIN)
aflags |= DF_RU;
if (flags & DF_RU)
aflags |= DF_RU_CHAIN;
if (flags & DF_REG_INFO)
aflags |= DF_LR;
if (! blocks)
blocks = df->all_blocks;
df->flags = flags;
if (update)
{
df_refs_update (df, NULL);
#if 0
df_refs_unlink (df, blocks);
#endif
}
else
{
df_refs_queue (df);
df_refs_record (df, blocks);
df_refs_process (df);
}
df_bitmaps_alloc (df, NULL, aflags);
df_luids_set (df, blocks);
if (aflags & DF_RD_CHAIN)
{
df_reg_def_chain_create (df, blocks, false);
}
if (aflags & DF_RU_CHAIN)
{
df_reg_use_chain_create (df, blocks, false);
}
df->dfs_order = xmalloc (sizeof (int) * n_basic_blocks);
df->rc_order = xmalloc (sizeof (int) * n_basic_blocks);
df->rts_order = xmalloc (sizeof (int) * n_basic_blocks);
df->inverse_dfs_map = xmalloc (sizeof (int) * last_basic_block);
df->inverse_rc_map = xmalloc (sizeof (int) * last_basic_block);
df->inverse_rts_map = xmalloc (sizeof (int) * last_basic_block);
flow_depth_first_order_compute (df->dfs_order, df->rc_order);
flow_reverse_top_sort_order_compute (df->rts_order);
for (i = 0; i < n_basic_blocks; i++)
{
df->inverse_dfs_map[df->dfs_order[i]] = i;
df->inverse_rc_map[df->rc_order[i]] = i;
df->inverse_rts_map[df->rts_order[i]] = i;
}
if (aflags & DF_RD)
{
dflow.in = xmalloc (sizeof (bitmap) * last_basic_block);
dflow.out = xmalloc (sizeof (bitmap) * last_basic_block);
dflow.gen = xmalloc (sizeof (bitmap) * last_basic_block);
dflow.kill = xmalloc (sizeof (bitmap) * last_basic_block);
df_rd_local_compute (df, df->flags & DF_RD ? blocks : df->all_blocks);
FOR_EACH_BB (bb)
{
dflow.in[bb->index] = DF_BB_INFO (df, bb)->rd_in;
dflow.out[bb->index] = DF_BB_INFO (df, bb)->rd_out;
dflow.gen[bb->index] = DF_BB_INFO (df, bb)->rd_gen;
dflow.kill[bb->index] = DF_BB_INFO (df, bb)->rd_kill;
}
dflow.repr = SR_BITMAP;
dflow.dir = DF_FORWARD;
dflow.conf_op = DF_UNION;
dflow.transfun = df_rd_transfer_function;
dflow.n_blocks = n_basic_blocks;
dflow.order = df->rc_order;
dflow.data = NULL;
iterative_dataflow (&dflow);
free (dflow.in);
free (dflow.out);
free (dflow.gen);
free (dflow.kill);
}
if (aflags & DF_UD_CHAIN)
{
df_ud_chain_create (df, df->all_blocks);
if (! (flags & DF_RD))
dflags |= DF_RD;
}
if (aflags & DF_RU)
{
dflow.in = xmalloc (sizeof (bitmap) * last_basic_block);
dflow.out = xmalloc (sizeof (bitmap) * last_basic_block);
dflow.gen = xmalloc (sizeof (bitmap) * last_basic_block);
dflow.kill = xmalloc (sizeof (bitmap) * last_basic_block);
df_ru_local_compute (df, df->flags & DF_RU ? blocks : df->all_blocks);
FOR_EACH_BB (bb)
{
dflow.in[bb->index] = DF_BB_INFO (df, bb)->ru_in;
dflow.out[bb->index] = DF_BB_INFO (df, bb)->ru_out;
dflow.gen[bb->index] = DF_BB_INFO (df, bb)->ru_gen;
dflow.kill[bb->index] = DF_BB_INFO (df, bb)->ru_kill;
}
dflow.repr = SR_BITMAP;
dflow.dir = DF_BACKWARD;
dflow.conf_op = DF_UNION;
dflow.transfun = df_ru_transfer_function;
dflow.n_blocks = n_basic_blocks;
dflow.order = df->rts_order;
dflow.data = NULL;
iterative_dataflow (&dflow);
free (dflow.in);
free (dflow.out);
free (dflow.gen);
free (dflow.kill);
}
if (aflags & DF_DU_CHAIN)
{
df_du_chain_create (df, df->all_blocks);
if (! (flags & DF_RU))
dflags |= DF_RU;
}
if (dflags)
df_bitmaps_free (df, dflags);
if (aflags & DF_LR)
{
dflow.in = xmalloc (sizeof (bitmap) * last_basic_block);
dflow.out = xmalloc (sizeof (bitmap) * last_basic_block);
dflow.gen = xmalloc (sizeof (bitmap) * last_basic_block);
dflow.kill = xmalloc (sizeof (bitmap) * last_basic_block);
df_lr_local_compute (df, df->flags & DF_LR ? blocks : df->all_blocks);
FOR_EACH_BB (bb)
{
dflow.in[bb->index] = DF_BB_INFO (df, bb)->lr_in;
dflow.out[bb->index] = DF_BB_INFO (df, bb)->lr_out;
dflow.gen[bb->index] = DF_BB_INFO (df, bb)->lr_use;
dflow.kill[bb->index] = DF_BB_INFO (df, bb)->lr_def;
}
dflow.repr = SR_BITMAP;
dflow.dir = DF_BACKWARD;
dflow.conf_op = DF_UNION;
dflow.transfun = df_lr_transfer_function;
dflow.n_blocks = n_basic_blocks;
dflow.order = df->rts_order;
dflow.data = NULL;
iterative_dataflow (&dflow);
free (dflow.in);
free (dflow.out);
free (dflow.gen);
free (dflow.kill);
}
if (aflags & DF_REG_INFO)
{
df_reg_info_compute (df, df->all_blocks);
}
free (df->dfs_order);
free (df->rc_order);
free (df->rts_order);
free (df->inverse_rc_map);
free (df->inverse_dfs_map);
free (df->inverse_rts_map);
}
struct df *
df_init (void)
{
struct df *df;
df = xcalloc (1, sizeof (struct df));
ddf = df;
return df;
}
static int
df_refs_queue (struct df *df)
{
df->def_id_save = df->def_id;
df->use_id_save = df->use_id;
return 0;
}
static int
df_refs_process (struct df *df)
{
unsigned int i;
for (i = df->def_id_save; i != df->def_id; i++)
{
struct ref *def = df->defs[i];
unsigned int uid = DF_REF_INSN_UID (def);
df->insns[uid].defs
= df_link_create (def, df->insns[uid].defs);
}
for (i = df->use_id_save; i != df->use_id; i++)
{
struct ref *use = df->uses[i];
unsigned int uid = DF_REF_INSN_UID (use);
df->insns[uid].uses
= df_link_create (use, df->insns[uid].uses);
}
return 0;
}
static int
df_bb_refs_update (struct df *df, basic_block bb)
{
rtx insn;
int count = 0;
FOR_BB_INSNS (bb, insn)
{
unsigned int uid;
uid = INSN_UID (insn);
if (bitmap_bit_p (df->insns_modified, uid))
{
df_insn_refs_unlink (df, bb, insn);
df_insn_refs_record (df, bb, insn);
count++;
}
}
return count;
}
static int
df_refs_update (struct df *df, bitmap blocks)
{
basic_block bb;
unsigned count = 0, bbno;
df->n_regs = max_reg_num ();
if (df->n_regs >= df->reg_size)
df_reg_table_realloc (df, 0);
df_refs_queue (df);
if (!blocks)
{
FOR_EACH_BB_IN_BITMAP (df->bbs_modified, 0, bb,
{
count += df_bb_refs_update (df, bb);
});
}
else
{
bitmap_iterator bi;
EXECUTE_IF_AND_IN_BITMAP (df->bbs_modified, blocks, 0, bbno, bi)
{
count += df_bb_refs_update (df, BASIC_BLOCK (bbno));
}
}
df_refs_process (df);
return count;
}
static int
df_modified_p (struct df *df, bitmap blocks)
{
int update = 0;
basic_block bb;
if (!df->n_bbs)
return 0;
FOR_EACH_BB (bb)
if (bitmap_bit_p (df->bbs_modified, bb->index)
&& (! blocks || (blocks == (bitmap) -1) || bitmap_bit_p (blocks, bb->index)))
{
update = 1;
break;
}
return update;
}
int
df_analyze (struct df *df, bitmap blocks, int flags)
{
int update;
gcc_assert (!df->n_bbs || df->n_bbs == (unsigned int) last_basic_block);
update = df_modified_p (df, blocks);
if (update || (flags != df->flags))
{
if (! blocks)
{
if (df->n_bbs)
{
df_free (df);
}
df_alloc (df, max_reg_num ());
df_analyze_1 (df, 0, flags, 0);
update = 1;
}
else
{
if (blocks == (bitmap) -1)
blocks = df->bbs_modified;
gcc_assert (df->n_bbs);
df_analyze_1 (df, blocks, flags, 1);
bitmap_zero (df->bbs_modified);
bitmap_zero (df->insns_modified);
}
}
return update;
}
static unsigned
prune_to_subcfg (int list[], unsigned len, bitmap blocks)
{
unsigned act, last;
for (act = 0, last = 0; act < len; act++)
if (bitmap_bit_p (blocks, list[act]))
list[last++] = list[act];
return last;
}
void
df_analyze_subcfg (struct df *df, bitmap blocks, int flags)
{
rtx insn;
basic_block bb;
struct dataflow dflow;
unsigned n_blocks;
if (flags & DF_UD_CHAIN)
flags |= DF_RD | DF_RD_CHAIN;
if (flags & DF_DU_CHAIN)
flags |= DF_RU;
if (flags & DF_RU)
flags |= DF_RU_CHAIN;
if (flags & DF_REG_INFO)
flags |= DF_LR;
if (!df->n_bbs)
{
df_alloc (df, max_reg_num ());
FOR_EACH_BB (bb)
{
FOR_BB_INSNS (bb, insn)
{
df_insn_modify (df, bb, insn);
}
}
}
df->flags = flags;
df_reg_def_chain_clean (df);
df_reg_use_chain_clean (df);
df_refs_update (df, blocks);
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
if (bitmap_bit_p (df->bbs_modified, bb->index))
{
FOR_BB_INSNS (bb, insn)
{
bitmap_clear_bit (df->insns_modified, INSN_UID (insn));
}
bitmap_clear_bit (df->bbs_modified, bb->index);
}
});
df_bitmaps_alloc (df, blocks, flags);
df_luids_set (df, blocks);
if (flags & DF_RD_CHAIN)
{
df_reg_def_chain_create (df, blocks, true);
}
if (flags & DF_RU_CHAIN)
{
df_reg_use_chain_create (df, blocks, true);
}
df->dfs_order = xmalloc (sizeof (int) * n_basic_blocks);
df->rc_order = xmalloc (sizeof (int) * n_basic_blocks);
df->rts_order = xmalloc (sizeof (int) * n_basic_blocks);
flow_depth_first_order_compute (df->dfs_order, df->rc_order);
flow_reverse_top_sort_order_compute (df->rts_order);
n_blocks = prune_to_subcfg (df->dfs_order, n_basic_blocks, blocks);
prune_to_subcfg (df->rc_order, n_basic_blocks, blocks);
prune_to_subcfg (df->rts_order, n_basic_blocks, blocks);
dflow.in = xmalloc (sizeof (bitmap) * last_basic_block);
dflow.out = xmalloc (sizeof (bitmap) * last_basic_block);
dflow.gen = xmalloc (sizeof (bitmap) * last_basic_block);
dflow.kill = xmalloc (sizeof (bitmap) * last_basic_block);
if (flags & DF_RD)
{
df_rd_local_compute (df, blocks);
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
dflow.in[bb->index] = DF_BB_INFO (df, bb)->rd_in;
dflow.out[bb->index] = DF_BB_INFO (df, bb)->rd_out;
dflow.gen[bb->index] = DF_BB_INFO (df, bb)->rd_gen;
dflow.kill[bb->index] = DF_BB_INFO (df, bb)->rd_kill;
});
dflow.repr = SR_BITMAP;
dflow.dir = DF_FORWARD;
dflow.conf_op = DF_UNION;
dflow.transfun = df_rd_transfer_function;
dflow.n_blocks = n_blocks;
dflow.order = df->rc_order;
dflow.data = NULL;
iterative_dataflow (&dflow);
}
if (flags & DF_UD_CHAIN)
{
df_ud_chain_create (df, blocks);
}
if (flags & DF_RU)
{
df_ru_local_compute (df, blocks);
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
dflow.in[bb->index] = DF_BB_INFO (df, bb)->ru_in;
dflow.out[bb->index] = DF_BB_INFO (df, bb)->ru_out;
dflow.gen[bb->index] = DF_BB_INFO (df, bb)->ru_gen;
dflow.kill[bb->index] = DF_BB_INFO (df, bb)->ru_kill;
});
dflow.repr = SR_BITMAP;
dflow.dir = DF_BACKWARD;
dflow.conf_op = DF_UNION;
dflow.transfun = df_ru_transfer_function;
dflow.n_blocks = n_blocks;
dflow.order = df->rts_order;
dflow.data = NULL;
iterative_dataflow (&dflow);
}
if (flags & DF_DU_CHAIN)
{
df_du_chain_create (df, blocks);
}
if (flags & DF_LR)
{
df_lr_local_compute (df, blocks);
FOR_EACH_BB (bb)
{
dflow.in[bb->index] = DF_BB_INFO (df, bb)->lr_in;
dflow.out[bb->index] = DF_BB_INFO (df, bb)->lr_out;
dflow.gen[bb->index] = DF_BB_INFO (df, bb)->lr_use;
dflow.kill[bb->index] = DF_BB_INFO (df, bb)->lr_def;
}
dflow.repr = SR_BITMAP;
dflow.dir = DF_BACKWARD;
dflow.conf_op = DF_UNION;
dflow.transfun = df_lr_transfer_function;
dflow.n_blocks = n_blocks;
dflow.order = df->rts_order;
dflow.data = NULL;
iterative_dataflow (&dflow);
}
if (flags & DF_REG_INFO)
{
df_reg_info_compute (df, blocks);
}
free (dflow.in);
free (dflow.out);
free (dflow.gen);
free (dflow.kill);
free (df->dfs_order);
free (df->rc_order);
free (df->rts_order);
}
void
df_finish (struct df *df)
{
df_free (df);
free (df);
}
static void
df_insn_refs_unlink (struct df *df, basic_block bb ATTRIBUTE_UNUSED, rtx insn)
{
struct df_link *link;
unsigned int uid;
uid = INSN_UID (insn);
for (link = df->insns[uid].defs; link; link = link->next)
df_def_unlink (df, link->ref);
for (link = df->insns[uid].uses; link; link = link->next)
df_use_unlink (df, link->ref);
df->insns[uid].defs = 0;
df->insns[uid].uses = 0;
}
#if 0
static void
df_bb_refs_unlink (struct df *df, basic_block bb)
{
rtx insn;
for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
{
df_insn_refs_unlink (df, bb, insn);
}
if (insn == BB_END (bb))
break;
}
}
static void
df_refs_unlink (struct df *df, bitmap blocks)
{
basic_block bb;
if (blocks)
{
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_refs_unlink (df, bb);
});
}
else
{
FOR_EACH_BB (bb)
df_bb_refs_unlink (df, bb);
}
}
#endif
rtx
df_insn_delete (struct df *df, basic_block bb ATTRIBUTE_UNUSED, rtx insn)
{
gcc_assert (insn != BB_HEAD (bb));
delete_insn (insn);
df_insn_modify (df, bb, insn);
return NEXT_INSN (insn);
}
static void
df_bb_modify (struct df *df, basic_block bb)
{
if ((unsigned) bb->index >= df->n_bbs)
df_bb_table_realloc (df, df->n_bbs);
bitmap_set_bit (df->bbs_modified, bb->index);
}
void
df_insn_modify (struct df *df, basic_block bb, rtx insn)
{
unsigned int uid;
uid = INSN_UID (insn);
if (uid >= df->insn_size)
df_insn_table_realloc (df, uid);
df_bb_modify (df, bb);
bitmap_set_bit (df->insns_modified, uid);
}
typedef struct replace_args
{
rtx match;
rtx replacement;
rtx insn;
int modified;
} replace_args;
static int
df_rtx_mem_replace (rtx *px, void *data)
{
replace_args *args = (replace_args *) data;
rtx mem = *px;
if (mem == NULL_RTX)
return 0;
switch (GET_CODE (mem))
{
case MEM:
break;
case CONST_DOUBLE:
return -1;
default:
return 0;
}
if (!rtx_equal_p (args->match, mem))
return 0;
validate_change (args->insn, px, args->replacement, 1);
args->modified++;
return 0;
}
int
df_insn_mem_replace (struct df *df, basic_block bb, rtx insn, rtx mem, rtx reg)
{
replace_args args;
args.insn = insn;
args.match = mem;
args.replacement = reg;
args.modified = 0;
for_each_rtx (&insn, df_rtx_mem_replace, &args);
if (args.modified)
df_insn_modify (df, bb, insn);
return args.modified;
}
static int
df_rtx_reg_replace (rtx *px, void *data)
{
rtx x = *px;
replace_args *args = (replace_args *) data;
if (x == NULL_RTX)
return 0;
if (x == args->match)
{
validate_change (args->insn, px, args->replacement, 1);
args->modified++;
}
return 0;
}
void
df_refs_reg_replace (struct df *df, bitmap blocks, struct df_link *chain, rtx oldreg, rtx newreg)
{
struct df_link *link;
replace_args args;
if (! blocks)
blocks = df->all_blocks;
args.match = oldreg;
args.replacement = newreg;
args.modified = 0;
for (link = chain; link; link = link->next)
{
struct ref *ref = link->ref;
rtx insn = DF_REF_INSN (ref);
if (! INSN_P (insn))
continue;
gcc_assert (bitmap_bit_p (blocks, DF_REF_BBNO (ref)));
df_ref_reg_replace (df, ref, oldreg, newreg);
if ((! link->next || DF_REF_INSN (ref)
!= DF_REF_INSN (link->next->ref))
&& REG_NOTES (insn))
{
args.insn = insn;
for_each_rtx (®_NOTES (insn), df_rtx_reg_replace, &args);
}
}
}
int
df_reg_replace (struct df *df, bitmap blocks, rtx oldreg, rtx newreg)
{
unsigned int oldregno = REGNO (oldreg);
df_refs_reg_replace (df, blocks, df->regs[oldregno].defs, oldreg, newreg);
df_refs_reg_replace (df, blocks, df->regs[oldregno].uses, oldreg, newreg);
return 1;
}
int
df_ref_reg_replace (struct df *df, struct ref *ref, rtx oldreg, rtx newreg)
{
if (! INSN_P (DF_REF_INSN (ref)))
return 0;
gcc_assert (!oldreg || oldreg == DF_REF_REG (ref));
if (! validate_change (DF_REF_INSN (ref), DF_REF_LOC (ref), newreg, 1))
return 0;
df_insn_modify (df, DF_REF_BB (ref), DF_REF_INSN (ref));
return 1;
}
struct ref*
df_bb_def_use_swap (struct df *df, basic_block bb, rtx def_insn, rtx use_insn, unsigned int regno)
{
struct ref *def;
struct ref *use;
int def_uid;
int use_uid;
struct df_link *link;
def = df_bb_insn_regno_first_def_find (df, bb, def_insn, regno);
if (! def)
return 0;
use = df_bb_insn_regno_last_use_find (df, bb, use_insn, regno);
if (! use)
return 0;
use_uid = INSN_UID (use_insn);
df_use_unlink (df, use);
df_ref_unlink (&df->insns[use_uid].uses, use);
def_uid = INSN_UID (def_insn);
link = df_ref_unlink (&df->insns[def_uid].defs, def);
link->ref = def;
link->next = df->insns[use_uid].defs;
df->insns[use_uid].defs = link;
#if 0
link = df_ref_unlink (&df->regs[regno].defs, def);
link->ref = def;
link->next = df->regs[regno].defs;
df->insns[regno].defs = link;
#endif
DF_REF_INSN (def) = use_insn;
return def;
}
static void
df_insns_modify (struct df *df, basic_block bb, rtx first_insn, rtx last_insn)
{
rtx insn;
for (insn = first_insn; ; insn = NEXT_INSN (insn))
{
unsigned int uid;
gcc_assert ((!CALL_P (insn) || CONST_OR_PURE_CALL_P (insn))
&& !LABEL_P (insn));
uid = INSN_UID (insn);
if (uid >= df->insn_size)
df_insn_table_realloc (df, uid);
df_insn_modify (df, bb, insn);
if (insn == last_insn)
break;
}
}
rtx
df_pattern_emit_before (struct df *df, rtx pattern, basic_block bb, rtx insn)
{
rtx ret_insn;
rtx prev_insn = PREV_INSN (insn);
gcc_assert (insn != BB_HEAD (bb));
ret_insn = emit_insn_before (pattern, insn);
if (ret_insn == insn)
return ret_insn;
df_insns_modify (df, bb, NEXT_INSN (prev_insn), ret_insn);
return ret_insn;
}
rtx
df_pattern_emit_after (struct df *df, rtx pattern, basic_block bb, rtx insn)
{
rtx ret_insn;
ret_insn = emit_insn_after (pattern, insn);
if (ret_insn == insn)
return ret_insn;
df_insns_modify (df, bb, NEXT_INSN (insn), ret_insn);
return ret_insn;
}
rtx
df_jump_pattern_emit_after (struct df *df, rtx pattern, basic_block bb, rtx insn)
{
rtx ret_insn;
ret_insn = emit_jump_insn_after (pattern, insn);
if (ret_insn == insn)
return ret_insn;
df_insns_modify (df, bb, NEXT_INSN (insn), ret_insn);
return ret_insn;
}
rtx
df_insn_move_before (struct df *df, basic_block bb, rtx insn, basic_block before_bb, rtx before_insn)
{
struct df_link *link;
unsigned int uid;
if (! bb)
return df_pattern_emit_before (df, insn, before_bb, before_insn);
uid = INSN_UID (insn);
for (link = df->insns[uid].defs; link; link = link->next)
DF_REF_BB (link->ref) = before_bb;
for (link = df->insns[uid].uses; link; link = link->next)
DF_REF_BB (link->ref) = before_bb;
return emit_insn_before (insn, before_insn);
}
int
df_insn_regno_def_p (struct df *df, basic_block bb ATTRIBUTE_UNUSED,
rtx insn, unsigned int regno)
{
unsigned int uid;
struct df_link *link;
uid = INSN_UID (insn);
for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
if (DF_REF_REGNO (def) == regno)
return 1;
}
return 0;
}
struct ref *
df_find_def (struct df *df, rtx insn, rtx reg)
{
struct df_link *defs;
for (defs = DF_INSN_DEFS (df, insn); defs; defs = defs->next)
if (rtx_equal_p (DF_REF_REG (defs->ref), reg))
return defs->ref;
return NULL;
}
int
df_reg_used (struct df *df, rtx insn, rtx reg)
{
struct df_link *uses;
for (uses = DF_INSN_USES (df, insn); uses; uses = uses->next)
if (rtx_equal_p (DF_REF_REG (uses->ref), reg))
return 1;
return 0;
}
static int
df_def_dominates_all_uses_p (struct df *df ATTRIBUTE_UNUSED, struct ref *def)
{
struct df_link *du_link;
for (du_link = DF_REF_CHAIN (def); du_link; du_link = du_link->next)
{
struct ref *use = du_link->ref;
struct df_link *ud_link;
for (ud_link = DF_REF_CHAIN (use); ud_link; ud_link = ud_link->next)
if (ud_link->ref != def)
return 0;
}
return 1;
}
int
df_insn_dominates_all_uses_p (struct df *df, basic_block bb ATTRIBUTE_UNUSED,
rtx insn)
{
unsigned int uid;
struct df_link *link;
uid = INSN_UID (insn);
for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
if (! df_def_dominates_all_uses_p (df, def))
return 0;
}
return 1;
}
static int
df_def_dominates_uses_p (struct df *df ATTRIBUTE_UNUSED, struct ref *def,
bitmap blocks)
{
struct df_link *du_link;
for (du_link = DF_REF_CHAIN (def); du_link; du_link = du_link->next)
{
struct ref *use = du_link->ref;
struct df_link *ud_link;
if (bitmap_bit_p (blocks, DF_REF_BBNO (use)))
{
for (ud_link = DF_REF_CHAIN (use); ud_link; ud_link = ud_link->next)
if (ud_link->ref != def)
return 0;
}
}
return 1;
}
int
df_insn_dominates_uses_p (struct df *df, basic_block bb ATTRIBUTE_UNUSED,
rtx insn, bitmap blocks)
{
unsigned int uid;
struct df_link *link;
uid = INSN_UID (insn);
for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
if (bitmap_bit_p (blocks, DF_REF_BBNO (def))
&& ! df_def_dominates_uses_p (df, def, blocks))
return 0;
}
return 1;
}
basic_block
df_regno_bb (struct df *df, unsigned int regno)
{
struct df_link *defs = df->regs[regno].defs;
struct df_link *uses = df->regs[regno].uses;
struct ref *def = defs ? defs->ref : 0;
struct ref *use = uses ? uses->ref : 0;
basic_block bb_def = def ? DF_REF_BB (def) : 0;
basic_block bb_use = use ? DF_REF_BB (use) : 0;
return bb_def == bb_use ? bb_def : 0;
}
int
df_reg_global_p (struct df *df, rtx reg)
{
return df_regno_bb (df, REGNO (reg)) != 0;
}
int
df_reg_lifetime (struct df *df, rtx reg)
{
return df->regs[REGNO (reg)].lifetime;
}
int
df_bb_reg_live_start_p (struct df *df, basic_block bb, rtx reg)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
gcc_assert (bb_info->lr_in);
return bitmap_bit_p (bb_info->lr_in, REGNO (reg));
}
int
df_bb_reg_live_end_p (struct df *df, basic_block bb, rtx reg)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
gcc_assert (bb_info->lr_in);
return bitmap_bit_p (bb_info->lr_out, REGNO (reg));
}
int
df_bb_regs_lives_compare (struct df *df, basic_block bb, rtx reg1, rtx reg2)
{
unsigned int regno1 = REGNO (reg1);
unsigned int regno2 = REGNO (reg2);
struct ref *def1;
struct ref *use1;
struct ref *def2;
struct ref *use2;
gcc_assert (df_regno_bb (df, regno1) == bb
&& df_regno_bb (df, regno2) == bb);
def2 = df_bb_regno_first_def_find (df, bb, regno2);
use1 = df_bb_regno_last_use_find (df, bb, regno1);
if (DF_INSN_LUID (df, DF_REF_INSN (def2))
> DF_INSN_LUID (df, DF_REF_INSN (use1)))
return -1;
def1 = df_bb_regno_first_def_find (df, bb, regno1);
use2 = df_bb_regno_last_use_find (df, bb, regno2);
if (DF_INSN_LUID (df, DF_REF_INSN (def1))
> DF_INSN_LUID (df, DF_REF_INSN (use2)))
return 1;
return 0;
}
struct ref *
df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno)
{
struct df_link *link;
for (link = df->regs[regno].uses; link; link = link->next)
{
struct ref *use = link->ref;
if (DF_REF_BB (use) == bb)
return use;
}
return 0;
}
struct ref *
df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno)
{
struct df_link *link;
for (link = df->regs[regno].defs; link; link = link->next)
{
struct ref *def = link->ref;
if (DF_REF_BB (def) == bb)
return def;
}
return 0;
}
struct ref *
df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno)
{
struct df_link *link;
struct ref *last_def = NULL;
int in_bb = 0;
for (link = df->regs[regno].defs; link; link = link->next)
{
struct ref *def = link->ref;
if (DF_REF_BB (def) == bb)
in_bb = 1;
else if (in_bb)
return last_def;
last_def = def;
}
return last_def;
}
static struct ref *
df_bb_insn_regno_last_use_find (struct df *df,
basic_block bb ATTRIBUTE_UNUSED, rtx insn,
unsigned int regno)
{
unsigned int uid;
struct df_link *link;
uid = INSN_UID (insn);
for (link = df->insns[uid].uses; link; link = link->next)
{
struct ref *use = link->ref;
if (DF_REF_REGNO (use) == regno)
return use;
}
return 0;
}
static struct ref *
df_bb_insn_regno_first_def_find (struct df *df,
basic_block bb ATTRIBUTE_UNUSED, rtx insn,
unsigned int regno)
{
unsigned int uid;
struct df_link *link;
uid = INSN_UID (insn);
for (link = df->insns[uid].defs; link; link = link->next)
{
struct ref *def = link->ref;
if (DF_REF_REGNO (def) == regno)
return def;
}
return 0;
}
rtx
df_bb_single_def_use_insn_find (struct df *df, basic_block bb, rtx insn, rtx reg)
{
struct ref *def;
struct ref *use;
struct df_link *du_link;
def = df_bb_insn_regno_first_def_find (df, bb, insn, REGNO (reg));
gcc_assert (def);
du_link = DF_REF_CHAIN (def);
if (! du_link)
return NULL_RTX;
use = du_link->ref;
if (! use)
return NULL_RTX;
if (du_link->next)
return NULL_RTX;
return DF_REF_INSN (use);
}
static void
df_chain_dump (struct df_link *link, FILE *file)
{
fprintf (file, "{ ");
for (; link; link = link->next)
{
fprintf (file, "%c%d ",
DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
DF_REF_ID (link->ref));
}
fprintf (file, "}");
}
static void
df_chain_dump_regno (struct df_link *link, FILE *file)
{
fprintf (file, "{ ");
for (; link; link = link->next)
{
fprintf (file, "%c%d(%d) ",
DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
DF_REF_ID (link->ref),
DF_REF_REGNO (link->ref));
}
fprintf (file, "}");
}
void
df_dump (struct df *df, int flags, FILE *file)
{
unsigned int j;
basic_block bb;
if (! df || ! file)
return;
fprintf (file, "\nDataflow summary:\n");
fprintf (file, "n_regs = %d, n_defs = %d, n_uses = %d, n_bbs = %d\n",
df->n_regs, df->n_defs, df->n_uses, df->n_bbs);
if (flags & DF_RD)
{
basic_block bb;
fprintf (file, "Reaching defs:\n");
FOR_EACH_BB (bb)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
if (! bb_info->rd_in)
continue;
fprintf (file, "bb %d in \t", bb->index);
dump_bitmap (file, bb_info->rd_in);
fprintf (file, "bb %d gen \t", bb->index);
dump_bitmap (file, bb_info->rd_gen);
fprintf (file, "bb %d kill\t", bb->index);
dump_bitmap (file, bb_info->rd_kill);
fprintf (file, "bb %d out \t", bb->index);
dump_bitmap (file, bb_info->rd_out);
}
}
if (flags & DF_UD_CHAIN)
{
fprintf (file, "Use-def chains:\n");
for (j = 0; j < df->n_defs; j++)
{
if (df->defs[j])
{
fprintf (file, "d%d bb %d luid %d insn %d reg %d ",
j, DF_REF_BBNO (df->defs[j]),
DF_INSN_LUID (df, DF_REF_INSN (df->defs[j])),
DF_REF_INSN_UID (df->defs[j]),
DF_REF_REGNO (df->defs[j]));
if (df->defs[j]->flags & DF_REF_READ_WRITE)
fprintf (file, "read/write ");
df_chain_dump (DF_REF_CHAIN (df->defs[j]), file);
fprintf (file, "\n");
}
}
}
if (flags & DF_RU)
{
fprintf (file, "Reaching uses:\n");
FOR_EACH_BB (bb)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
if (! bb_info->ru_in)
continue;
fprintf (file, "bb %d in \t", bb->index);
dump_bitmap (file, bb_info->ru_in);
fprintf (file, "bb %d gen \t", bb->index);
dump_bitmap (file, bb_info->ru_gen);
fprintf (file, "bb %d kill\t", bb->index);
dump_bitmap (file, bb_info->ru_kill);
fprintf (file, "bb %d out \t", bb->index);
dump_bitmap (file, bb_info->ru_out);
}
}
if (flags & DF_DU_CHAIN)
{
fprintf (file, "Def-use chains:\n");
for (j = 0; j < df->n_uses; j++)
{
if (df->uses[j])
{
fprintf (file, "u%d bb %d luid %d insn %d reg %d ",
j, DF_REF_BBNO (df->uses[j]),
DF_INSN_LUID (df, DF_REF_INSN (df->uses[j])),
DF_REF_INSN_UID (df->uses[j]),
DF_REF_REGNO (df->uses[j]));
if (df->uses[j]->flags & DF_REF_READ_WRITE)
fprintf (file, "read/write ");
df_chain_dump (DF_REF_CHAIN (df->uses[j]), file);
fprintf (file, "\n");
}
}
}
if (flags & DF_LR)
{
fprintf (file, "Live regs:\n");
FOR_EACH_BB (bb)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
if (! bb_info->lr_in)
continue;
fprintf (file, "bb %d in \t", bb->index);
dump_bitmap (file, bb_info->lr_in);
fprintf (file, "bb %d use \t", bb->index);
dump_bitmap (file, bb_info->lr_use);
fprintf (file, "bb %d def \t", bb->index);
dump_bitmap (file, bb_info->lr_def);
fprintf (file, "bb %d out \t", bb->index);
dump_bitmap (file, bb_info->lr_out);
}
}
if (flags & (DF_REG_INFO | DF_RD_CHAIN | DF_RU_CHAIN))
{
struct reg_info *reg_info = df->regs;
fprintf (file, "Register info:\n");
for (j = 0; j < df->n_regs; j++)
{
if (((flags & DF_REG_INFO)
&& (reg_info[j].n_uses || reg_info[j].n_defs))
|| ((flags & DF_RD_CHAIN) && reg_info[j].defs)
|| ((flags & DF_RU_CHAIN) && reg_info[j].uses))
{
fprintf (file, "reg %d", j);
if ((flags & DF_RD_CHAIN) && (flags & DF_RU_CHAIN))
{
basic_block bb = df_regno_bb (df, j);
if (bb)
fprintf (file, " bb %d", bb->index);
else
fprintf (file, " bb ?");
}
if (flags & DF_REG_INFO)
{
fprintf (file, " life %d", reg_info[j].lifetime);
}
if ((flags & DF_REG_INFO) || (flags & DF_RD_CHAIN))
{
fprintf (file, " defs ");
if (flags & DF_REG_INFO)
fprintf (file, "%d ", reg_info[j].n_defs);
if (flags & DF_RD_CHAIN)
df_chain_dump (reg_info[j].defs, file);
}
if ((flags & DF_REG_INFO) || (flags & DF_RU_CHAIN))
{
fprintf (file, " uses ");
if (flags & DF_REG_INFO)
fprintf (file, "%d ", reg_info[j].n_uses);
if (flags & DF_RU_CHAIN)
df_chain_dump (reg_info[j].uses, file);
}
fprintf (file, "\n");
}
}
}
fprintf (file, "\n");
}
void
df_insn_debug (struct df *df, rtx insn, FILE *file)
{
unsigned int uid;
int bbi;
uid = INSN_UID (insn);
if (uid >= df->insn_size)
return;
if (df->insns[uid].defs)
bbi = DF_REF_BBNO (df->insns[uid].defs->ref);
else if (df->insns[uid].uses)
bbi = DF_REF_BBNO (df->insns[uid].uses->ref);
else
bbi = -1;
fprintf (file, "insn %d bb %d luid %d defs ",
uid, bbi, DF_INSN_LUID (df, insn));
df_chain_dump (df->insns[uid].defs, file);
fprintf (file, " uses ");
df_chain_dump (df->insns[uid].uses, file);
fprintf (file, "\n");
}
void
df_insn_debug_regno (struct df *df, rtx insn, FILE *file)
{
unsigned int uid;
int bbi;
uid = INSN_UID (insn);
if (uid >= df->insn_size)
return;
if (df->insns[uid].defs)
bbi = DF_REF_BBNO (df->insns[uid].defs->ref);
else if (df->insns[uid].uses)
bbi = DF_REF_BBNO (df->insns[uid].uses->ref);
else
bbi = -1;
fprintf (file, "insn %d bb %d luid %d defs ",
uid, bbi, DF_INSN_LUID (df, insn));
df_chain_dump_regno (df->insns[uid].defs, file);
fprintf (file, " uses ");
df_chain_dump_regno (df->insns[uid].uses, file);
fprintf (file, "\n");
}
static void
df_regno_debug (struct df *df, unsigned int regno, FILE *file)
{
if (regno >= df->reg_size)
return;
fprintf (file, "reg %d life %d defs ",
regno, df->regs[regno].lifetime);
df_chain_dump (df->regs[regno].defs, file);
fprintf (file, " uses ");
df_chain_dump (df->regs[regno].uses, file);
fprintf (file, "\n");
}
static void
df_ref_debug (struct df *df, struct ref *ref, FILE *file)
{
fprintf (file, "%c%d ",
DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
DF_REF_ID (ref));
fprintf (file, "reg %d bb %d luid %d insn %d chain ",
DF_REF_REGNO (ref),
DF_REF_BBNO (ref),
DF_INSN_LUID (df, DF_REF_INSN (ref)),
INSN_UID (DF_REF_INSN (ref)));
df_chain_dump (DF_REF_CHAIN (ref), file);
fprintf (file, "\n");
}
void
debug_df_insn (rtx insn)
{
df_insn_debug (ddf, insn, stderr);
debug_rtx (insn);
}
void
debug_df_reg (rtx reg)
{
df_regno_debug (ddf, REGNO (reg), stderr);
}
void
debug_df_regno (unsigned int regno)
{
df_regno_debug (ddf, regno, stderr);
}
void
debug_df_ref (struct ref *ref)
{
df_ref_debug (ddf, ref, stderr);
}
void
debug_df_defno (unsigned int defno)
{
df_ref_debug (ddf, ddf->defs[defno], stderr);
}
void
debug_df_useno (unsigned int defno)
{
df_ref_debug (ddf, ddf->uses[defno], stderr);
}
void
debug_df_chain (struct df_link *link)
{
df_chain_dump (link, stderr);
fputc ('\n', stderr);
}
static void
dataflow_set_a_op_b (enum set_representation repr,
enum df_confluence_op op,
void *op1, void *op2)
{
switch (repr)
{
case SR_SBITMAP:
switch (op)
{
case DF_UNION:
sbitmap_a_or_b (op1, op1, op2);
break;
case DF_INTERSECTION:
sbitmap_a_and_b (op1, op1, op2);
break;
default:
gcc_unreachable ();
}
break;
case SR_BITMAP:
switch (op)
{
case DF_UNION:
bitmap_ior_into (op1, op2);
break;
case DF_INTERSECTION:
bitmap_and_into (op1, op2);
break;
default:
gcc_unreachable ();
}
break;
default:
gcc_unreachable ();
}
}
static void
dataflow_set_copy (enum set_representation repr, void *dest, void *src)
{
switch (repr)
{
case SR_SBITMAP:
sbitmap_copy (dest, src);
break;
case SR_BITMAP:
bitmap_copy (dest, src);
break;
default:
gcc_unreachable ();
}
}
static void
hybrid_search (basic_block bb, struct dataflow *dataflow,
sbitmap visited, sbitmap pending, sbitmap considered)
{
int changed;
int i = bb->index;
edge e;
edge_iterator ei;
SET_BIT (visited, bb->index);
gcc_assert (TEST_BIT (pending, bb->index));
RESET_BIT (pending, i);
#define HS(E_ANTI, E_ANTI_BB, E_ANTI_START_BB, IN_SET, \
E, E_BB, E_START_BB, OUT_SET) \
do \
{ \
\
bitmap_zero (IN_SET[i]); \
FOR_EACH_EDGE (e, ei, bb->E_ANTI) \
{ \
if (e->E_ANTI_BB == E_ANTI_START_BB) \
continue; \
if (!TEST_BIT (considered, e->E_ANTI_BB->index)) \
continue; \
\
dataflow_set_a_op_b (dataflow->repr, dataflow->conf_op, \
IN_SET[i], \
OUT_SET[e->E_ANTI_BB->index]); \
} \
\
(*dataflow->transfun)(i, &changed, \
dataflow->in[i], dataflow->out[i], \
dataflow->gen[i], dataflow->kill[i], \
dataflow->data); \
\
if (!changed) \
break; \
\
FOR_EACH_EDGE (e, ei, bb->E) \
{ \
if (e->E_BB == E_START_BB || e->E_BB->index == i) \
continue; \
\
if (!TEST_BIT (considered, e->E_BB->index)) \
continue; \
\
SET_BIT (pending, e->E_BB->index); \
} \
\
FOR_EACH_EDGE (e, ei, bb->E) \
{ \
if (e->E_BB == E_START_BB || e->E_BB->index == i) \
continue; \
\
if (!TEST_BIT (considered, e->E_BB->index)) \
continue; \
\
if (!TEST_BIT (visited, e->E_BB->index)) \
hybrid_search (e->E_BB, dataflow, visited, pending, considered); \
} \
} while (0)
if (dataflow->dir == DF_FORWARD)
HS (preds, src, ENTRY_BLOCK_PTR, dataflow->in,
succs, dest, EXIT_BLOCK_PTR, dataflow->out);
else
HS (succs, dest, EXIT_BLOCK_PTR, dataflow->out,
preds, src, ENTRY_BLOCK_PTR, dataflow->in);
}
void
iterative_dataflow (struct dataflow *dataflow)
{
unsigned i, idx;
sbitmap visited, pending, considered;
pending = sbitmap_alloc (last_basic_block);
visited = sbitmap_alloc (last_basic_block);
considered = sbitmap_alloc (last_basic_block);
sbitmap_zero (pending);
sbitmap_zero (visited);
sbitmap_zero (considered);
for (i = 0; i < dataflow->n_blocks; i++)
{
idx = dataflow->order[i];
SET_BIT (pending, idx);
SET_BIT (considered, idx);
if (dataflow->dir == DF_FORWARD)
dataflow_set_copy (dataflow->repr,
dataflow->out[idx], dataflow->gen[idx]);
else
dataflow_set_copy (dataflow->repr,
dataflow->in[idx], dataflow->gen[idx]);
};
while (1)
{
for (i = 0; i < dataflow->n_blocks; i++)
{
idx = dataflow->order[i];
if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
hybrid_search (BASIC_BLOCK (idx), dataflow,
visited, pending, considered);
}
if (sbitmap_first_set_bit (pending) == -1)
break;
sbitmap_zero (visited);
}
sbitmap_free (pending);
sbitmap_free (visited);
sbitmap_free (considered);
}