#include "config.h"
#include "system.h"
#include "rtl.h"
#include "tm_p.h"
#include "insn-config.h"
#include "recog.h"
#include "function.h"
#include "regs.h"
#include "obstack.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "sbitmap.h"
#include "bitmap.h"
#include "df.h"
#include "fibheap.h"
#define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
do \
{ \
unsigned int node_; \
EXECUTE_IF_SET_IN_BITMAP (BITMAP, MIN, node_, \
{(BB) = BASIC_BLOCK (node_); CODE;}); \
} \
while (0)
static struct obstack df_ref_obstack;
static struct df *ddf;
static void df_reg_table_realloc PARAMS((struct df *, int));
#if 0
static void df_def_table_realloc PARAMS((struct df *, int));
#endif
static void df_insn_table_realloc PARAMS((struct df *, unsigned int));
static void df_bitmaps_alloc PARAMS((struct df *, int));
static void df_bitmaps_free PARAMS((struct df *, int));
static void df_free PARAMS((struct df *));
static void df_alloc PARAMS((struct df *, int));
static rtx df_reg_clobber_gen PARAMS((unsigned int));
static rtx df_reg_use_gen PARAMS((unsigned int));
static inline struct df_link *df_link_create PARAMS((struct ref *,
struct df_link *));
static struct df_link *df_ref_unlink PARAMS((struct df_link **, struct ref *));
static void df_def_unlink PARAMS((struct df *, struct ref *));
static void df_use_unlink PARAMS((struct df *, struct ref *));
static void df_insn_refs_unlink PARAMS ((struct df *, basic_block, rtx));
#if 0
static void df_bb_refs_unlink PARAMS ((struct df *, basic_block));
static void df_refs_unlink PARAMS ((struct df *, bitmap));
#endif
static struct ref *df_ref_create PARAMS((struct df *,
rtx, rtx *, rtx,
enum df_ref_type, enum df_ref_flags));
static void df_ref_record_1 PARAMS((struct df *, rtx, rtx *,
rtx, enum df_ref_type,
enum df_ref_flags));
static void df_ref_record PARAMS((struct df *, rtx, rtx *,
rtx, enum df_ref_type,
enum df_ref_flags));
static void df_def_record_1 PARAMS((struct df *, rtx, basic_block, rtx));
static void df_defs_record PARAMS((struct df *, rtx, basic_block, rtx));
static void df_uses_record PARAMS((struct df *, rtx *,
enum df_ref_type, basic_block, rtx,
enum df_ref_flags));
static void df_insn_refs_record PARAMS((struct df *, basic_block, rtx));
static void df_bb_refs_record PARAMS((struct df *, basic_block));
static void df_refs_record PARAMS((struct df *, bitmap));
static void df_bb_reg_def_chain_create PARAMS((struct df *, basic_block));
static void df_reg_def_chain_create PARAMS((struct df *, bitmap));
static void df_bb_reg_use_chain_create PARAMS((struct df *, basic_block));
static void df_reg_use_chain_create PARAMS((struct df *, bitmap));
static void df_bb_du_chain_create PARAMS((struct df *, basic_block, bitmap));
static void df_du_chain_create PARAMS((struct df *, bitmap));
static void df_bb_ud_chain_create PARAMS((struct df *, basic_block));
static void df_ud_chain_create PARAMS((struct df *, bitmap));
static void df_bb_rd_local_compute PARAMS((struct df *, basic_block));
static void df_rd_local_compute PARAMS((struct df *, bitmap));
static void df_bb_ru_local_compute PARAMS((struct df *, basic_block));
static void df_ru_local_compute PARAMS((struct df *, bitmap));
static void df_bb_lr_local_compute PARAMS((struct df *, basic_block));
static void df_lr_local_compute PARAMS((struct df *, bitmap));
static void df_bb_reg_info_compute PARAMS((struct df *, basic_block, bitmap));
static void df_reg_info_compute PARAMS((struct df *, bitmap));
static int df_bb_luids_set PARAMS((struct df *df, basic_block));
static int df_luids_set PARAMS((struct df *df, bitmap));
static int df_modified_p PARAMS ((struct df *, bitmap));
static int df_refs_queue PARAMS ((struct df *));
static int df_refs_process PARAMS ((struct df *));
static int df_bb_refs_update PARAMS ((struct df *, basic_block));
static int df_refs_update PARAMS ((struct df *));
static void df_analyse_1 PARAMS((struct df *, bitmap, int, int));
static void df_insns_modify PARAMS((struct df *, basic_block,
rtx, rtx));
static int df_rtx_mem_replace PARAMS ((rtx *, void *));
static int df_rtx_reg_replace PARAMS ((rtx *, void *));
void df_refs_reg_replace PARAMS ((struct df *, bitmap,
struct df_link *, rtx, rtx));
static int df_def_dominates_all_uses_p PARAMS((struct df *, struct ref *def));
static int df_def_dominates_uses_p PARAMS((struct df *,
struct ref *def, bitmap));
static struct ref *df_bb_regno_last_use_find PARAMS((struct df *, basic_block,
unsigned int));
static struct ref *df_bb_regno_first_def_find PARAMS((struct df *, basic_block,
unsigned int));
static struct ref *df_bb_insn_regno_last_use_find PARAMS((struct df *,
basic_block,
rtx, unsigned int));
static struct ref *df_bb_insn_regno_first_def_find PARAMS((struct df *,
basic_block,
rtx, unsigned int));
static void df_chain_dump PARAMS((struct df_link *, FILE *file));
static void df_chain_dump_regno PARAMS((struct df_link *, FILE *file));
static void df_regno_debug PARAMS ((struct df *, unsigned int, FILE *));
static void df_ref_debug PARAMS ((struct df *, struct ref *, FILE *));
static void df_rd_transfer_function PARAMS ((int, int *, bitmap, bitmap,
bitmap, bitmap, void *));
static void df_ru_transfer_function PARAMS ((int, int *, bitmap, bitmap,
bitmap, bitmap, void *));
static void df_lr_transfer_function PARAMS ((int, int *, bitmap, bitmap,
bitmap, bitmap, void *));
static void hybrid_search_bitmap PARAMS ((basic_block, bitmap *, bitmap *,
bitmap *, bitmap *, enum df_flow_dir,
enum df_confluence_op,
transfer_function_bitmap,
sbitmap, sbitmap, void *));
static void hybrid_search_sbitmap PARAMS ((basic_block, sbitmap *, sbitmap *,
sbitmap *, sbitmap *, enum df_flow_dir,
enum df_confluence_op,
transfer_function_sbitmap,
sbitmap, sbitmap, void *));
static inline bool read_modify_subreg_p PARAMS ((rtx));
static void
df_insn_table_realloc (df, size)
struct df *df;
unsigned int size;
{
size++;
if (size <= df->insn_size)
return;
size += df->insn_size / 4;
df->insns = (struct insn_info *)
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_XMALLOC ();
bitmap_zero (df->insns_modified);
}
}
static void
df_reg_table_realloc (df, size)
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 = (struct reg_info *)
xrealloc (df->regs, size * sizeof (struct reg_info));
memset (df->regs + df->reg_size, 0,
(size - df->reg_size) * sizeof (struct reg_info));
df->reg_size = size;
}
#if 0
static void
df_def_table_realloc (df, size)
struct df *df;
int size;
{
int i;
struct ref *refs;
if (! size)
size = df->def_size / 4;
df->def_size += size;
df->defs = xrealloc (df->defs,
df->def_size * sizeof (*df->defs));
refs = xmalloc (size * sizeof (*refs));
for (i = 0; i < size - 1; i++)
refs[i].chain = (struct df_link *) (refs + i + 1);
refs[size - 1].chain = 0;
}
#endif
static void
df_bitmaps_alloc (df, flags)
struct df *df;
int flags;
{
int dflags = 0;
basic_block bb;
if ((flags & DF_LR) && df->n_regs < (unsigned int) max_reg_num ())
dflags |= DF_LR | DF_RU;
if ((flags & DF_RU) && df->n_uses < df->use_id)
dflags |= DF_RU;
if ((flags & DF_RD) && df->n_defs < df->def_id)
dflags |= DF_RD;
if (dflags)
df_bitmaps_free (df, dflags);
df->n_defs = df->def_id;
df->n_uses = df->use_id;
FOR_EACH_BB (bb)
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
if (flags & DF_RD && ! bb_info->rd_in)
{
bb_info->rd_kill = BITMAP_XMALLOC ();
bitmap_zero (bb_info->rd_kill);
bb_info->rd_gen = BITMAP_XMALLOC ();
bitmap_zero (bb_info->rd_gen);
bb_info->rd_in = BITMAP_XMALLOC ();
bb_info->rd_out = BITMAP_XMALLOC ();
bb_info->rd_valid = 0;
}
if (flags & DF_RU && ! bb_info->ru_in)
{
bb_info->ru_kill = BITMAP_XMALLOC ();
bitmap_zero (bb_info->ru_kill);
bb_info->ru_gen = BITMAP_XMALLOC ();
bitmap_zero (bb_info->ru_gen);
bb_info->ru_in = BITMAP_XMALLOC ();
bb_info->ru_out = BITMAP_XMALLOC ();
bb_info->ru_valid = 0;
}
if (flags & DF_LR && ! bb_info->lr_in)
{
bb_info->lr_def = BITMAP_XMALLOC ();
bitmap_zero (bb_info->lr_def);
bb_info->lr_use = BITMAP_XMALLOC ();
bitmap_zero (bb_info->lr_use);
bb_info->lr_in = BITMAP_XMALLOC ();
bb_info->lr_out = BITMAP_XMALLOC ();
bb_info->lr_valid = 0;
}
}
}
static void
df_bitmaps_free (df, flags)
struct df *df ATTRIBUTE_UNUSED;
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_XFREE (bb_info->rd_kill);
bb_info->rd_kill = NULL;
BITMAP_XFREE (bb_info->rd_gen);
bb_info->rd_gen = NULL;
BITMAP_XFREE (bb_info->rd_in);
bb_info->rd_in = NULL;
BITMAP_XFREE (bb_info->rd_out);
bb_info->rd_out = NULL;
}
if ((flags & DF_RU) && bb_info->ru_in)
{
BITMAP_XFREE (bb_info->ru_kill);
bb_info->ru_kill = NULL;
BITMAP_XFREE (bb_info->ru_gen);
bb_info->ru_gen = NULL;
BITMAP_XFREE (bb_info->ru_in);
bb_info->ru_in = NULL;
BITMAP_XFREE (bb_info->ru_out);
bb_info->ru_out = NULL;
}
if ((flags & DF_LR) && bb_info->lr_in)
{
BITMAP_XFREE (bb_info->lr_def);
bb_info->lr_def = NULL;
BITMAP_XFREE (bb_info->lr_use);
bb_info->lr_use = NULL;
BITMAP_XFREE (bb_info->lr_in);
bb_info->lr_in = NULL;
BITMAP_XFREE (bb_info->lr_out);
bb_info->lr_out = NULL;
}
}
df->flags &= ~(flags & (DF_RD | DF_RU | DF_LR));
}
static void
df_alloc (df, n_regs)
struct df *df;
int n_regs;
{
int n_insns;
basic_block bb;
gcc_obstack_init (&df_ref_obstack);
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->reg_def_last = xmalloc (df->n_regs * sizeof (struct ref *));
df_insn_table_realloc (df, n_insns);
df_reg_table_realloc (df, df->n_regs);
df->bbs_modified = BITMAP_XMALLOC ();
bitmap_zero (df->bbs_modified);
df->flags = 0;
df->bbs = xcalloc (last_basic_block, sizeof (struct bb_info));
df->all_blocks = BITMAP_XMALLOC ();
FOR_EACH_BB (bb)
bitmap_set_bit (df->all_blocks, bb->index);
}
static void
df_free (df)
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;
if (df->bbs_modified)
BITMAP_XFREE (df->bbs_modified);
df->bbs_modified = 0;
if (df->insns_modified)
BITMAP_XFREE (df->insns_modified);
df->insns_modified = 0;
BITMAP_XFREE (df->all_blocks);
df->all_blocks = 0;
obstack_free (&df_ref_obstack, NULL);
}
static rtx df_reg_use_gen (regno)
unsigned int regno;
{
rtx reg;
rtx use;
reg = regno_reg_rtx[regno];
use = gen_rtx_USE (GET_MODE (reg), reg);
return use;
}
static rtx df_reg_clobber_gen (regno)
unsigned int regno;
{
rtx reg;
rtx use;
reg = regno_reg_rtx[regno];
use = gen_rtx_CLOBBER (GET_MODE (reg), reg);
return use;
}
static inline struct df_link *
df_link_create (ref, next)
struct ref *ref;
struct df_link *next;
{
struct df_link *link;
link = (struct df_link *) obstack_alloc (&df_ref_obstack,
sizeof (*link));
link->next = next;
link->ref = ref;
return link;
}
static struct df_link *
df_ref_unlink (phead, ref)
struct df_link **phead;
struct ref *ref;
{
struct df_link *link = *phead;
if (link)
{
if (! link->next)
{
if (link->ref != ref)
abort ();
*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 (df, ref)
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 (df, def)
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 (df, use)
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 (df, reg, loc, insn, ref_type, ref_flags)
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;
unsigned int uid;
this_ref = (struct ref *) obstack_alloc (&df_ref_obstack,
sizeof (*this_ref));
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;
uid = INSN_UID (insn);
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 (df, reg, loc, insn, ref_type, ref_flags)
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 (df, reg, loc, insn, ref_type, ref_flags)
struct df *df;
rtx reg;
rtx *loc;
rtx insn;
enum df_ref_type ref_type;
enum df_ref_flags ref_flags;
{
unsigned int regno;
if (GET_CODE (reg) != REG && GET_CODE (reg) != SUBREG)
abort ();
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;
}
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);
}
}
static inline bool
read_modify_subreg_p (x)
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));
if (isize <= osize)
return true;
if (isize <= UNITS_PER_WORD)
return false;
if (osize >= UNITS_PER_WORD)
return false;
return true;
}
static void
df_def_record_1 (df, x, bb, insn)
struct df *df;
rtx x;
basic_block bb;
rtx insn;
{
rtx *loc = &SET_DEST (x);
rtx dst = *loc;
enum df_ref_flags flags = 0;
if (GET_CODE (dst) == PARALLEL && GET_MODE (dst) == BLKmode)
{
int i;
for (i = XVECLEN (dst, 0) - 1; i >= 0; i--)
df_def_record_1 (df, XVECEXP (dst, 0, i), bb, insn);
return;
}
#ifdef CLASS_CANNOT_CHANGE_MODE
if (GET_CODE (dst) == SUBREG
&& CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (SUBREG_REG (dst)),
GET_MODE (dst)))
flags |= DF_REF_MODE_CHANGE;
#endif
while (GET_CODE (dst) == STRICT_LOW_PART
|| GET_CODE (dst) == ZERO_EXTRACT
|| GET_CODE (dst) == SIGN_EXTRACT
|| read_modify_subreg_p (dst))
{
if (GET_CODE (dst) == STRICT_LOW_PART)
{
loc = &XEXP (dst, 0);
dst = *loc;
}
#ifdef CLASS_CANNOT_CHANGE_MODE
if (GET_CODE (dst) == SUBREG
&& CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (SUBREG_REG (dst)),
GET_MODE (dst)))
flags |= DF_REF_MODE_CHANGE;
#endif
loc = &XEXP (dst, 0);
dst = *loc;
flags |= DF_REF_READ_WRITE;
}
if (GET_CODE (dst) == REG
|| (GET_CODE (dst) == SUBREG && GET_CODE (SUBREG_REG (dst)) == REG))
df_ref_record (df, dst, loc, insn, DF_REF_REG_DEF, flags);
}
static void
df_defs_record (df, x, bb, insn)
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 (df, loc, ref_type, bb, insn, flags)
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 (GET_CODE (XEXP (x, 0)) == MEM)
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, flags);
return;
case SUBREG:
if (GET_CODE (SUBREG_REG (x)) != REG)
{
loc = &SUBREG_REG (x);
df_uses_record (df, loc, ref_type, bb, insn, flags);
return;
}
#ifdef CLASS_CANNOT_CHANGE_MODE
if (CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (x),
GET_MODE (SUBREG_REG (x))))
flags |= DF_REF_MODE_CHANGE;
#endif
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))
{
enum df_ref_flags use_flags;
case SUBREG:
if (read_modify_subreg_p (dst))
{
use_flags = DF_REF_READ_WRITE;
#ifdef CLASS_CANNOT_CHANGE_MODE
if (CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (dst),
GET_MODE (SUBREG_REG (dst))))
use_flags |= DF_REF_MODE_CHANGE;
#endif
df_uses_record (df, &SUBREG_REG (dst), DF_REF_REG_USE, bb,
insn, use_flags);
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);
if (GET_CODE (dst) != SUBREG)
abort ();
use_flags = DF_REF_READ_WRITE;
#ifdef CLASS_CANNOT_CHANGE_MODE
if (CLASS_CANNOT_CHANGE_MODE_P (GET_MODE (dst),
GET_MODE (SUBREG_REG (dst))))
use_flags |= DF_REF_MODE_CHANGE;
#endif
df_uses_record (df, &SUBREG_REG (dst), DF_REF_REG_USE, bb,
insn, use_flags);
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:
abort ();
}
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 (df, bb, insn)
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 (GET_CODE (insn) == CALL_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, &SET_DEST (x),
DF_REF_REG_USE, bb, insn, 0);
}
}
}
df_uses_record (df, &PATTERN (insn),
DF_REF_REG_USE, bb, insn, 0);
if (GET_CODE (insn) == CALL_INSN)
{
rtx note;
if (df->flags & DF_HARD_REGS)
{
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)
|| HARD_REGNO_CALL_PART_CLOBBERED (i, reg_raw_mode[i]))
{
rtx reg_clob = df_reg_clobber_gen (i);
df_defs_record (df, reg_clob, bb, insn);
}
}
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 (df, bb)
struct df *df;
basic_block bb;
{
rtx insn;
for (insn = bb->head; ; insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
{
df_insn_refs_record (df, bb, insn);
}
if (insn == bb->end)
break;
}
}
static void
df_refs_record (df, blocks)
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 (df, bb)
struct df *df;
basic_block bb;
{
rtx insn;
for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
insn = PREV_INSN (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 (df, blocks)
struct df *df;
bitmap blocks;
{
basic_block bb;
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_reg_def_chain_create (df, bb);
});
}
static void
df_bb_reg_use_chain_create (df, bb)
struct df *df;
basic_block bb;
{
rtx insn;
for (insn = bb->head; insn && insn != NEXT_INSN (bb->end);
insn = NEXT_INSN (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 (df, blocks)
struct df *df;
bitmap blocks;
{
basic_block bb;
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_reg_use_chain_create (df, bb);
});
}
static void
df_bb_du_chain_create (df, bb, ru)
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 (insn = bb->end; insn && insn != PREV_INSN (bb->head);
insn = PREV_INSN (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 (df, blocks)
struct df *df;
bitmap blocks;
{
bitmap ru;
basic_block bb;
ru = BITMAP_XMALLOC ();
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_du_chain_create (df, bb, ru);
});
BITMAP_XFREE (ru);
}
static void
df_bb_ud_chain_create (df, bb)
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 (insn = bb->head; insn && insn != NEXT_INSN (bb->end);
insn = NEXT_INSN (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 (df, blocks)
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 (bb, changed, in, out, gen, kill, data)
int bb ATTRIBUTE_UNUSED;
int *changed;
bitmap in, out, gen, kill;
void *data ATTRIBUTE_UNUSED;
{
*changed = bitmap_union_of_diff (out, gen, in, kill);
}
static void
df_ru_transfer_function (bb, changed, in, out, gen, kill, data)
int bb ATTRIBUTE_UNUSED;
int *changed;
bitmap in, out, gen, kill;
void *data ATTRIBUTE_UNUSED;
{
*changed = bitmap_union_of_diff (in, gen, out, kill);
}
static void
df_lr_transfer_function (bb, changed, in, out, use, def, data)
int bb ATTRIBUTE_UNUSED;
int *changed;
bitmap in, out, use, def;
void *data ATTRIBUTE_UNUSED;
{
*changed = bitmap_union_of_diff (in, use, out, def);
}
static void
df_bb_rd_local_compute (df, bb)
struct df *df;
basic_block bb;
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
for (insn = bb->head; insn && insn != NEXT_INSN (bb->end);
insn = NEXT_INSN (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;
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_clear_bit (bb_info->rd_gen, DF_REF_ID (def2));
}
bitmap_set_bit (bb_info->rd_gen, DF_REF_ID (def));
}
}
bb_info->rd_valid = 1;
}
static void
df_rd_local_compute (df, blocks)
struct df *df;
bitmap blocks;
{
basic_block bb;
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_rd_local_compute (df, bb);
});
}
static void
df_bb_ru_local_compute (df, bb)
struct df *df;
basic_block bb;
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
insn = PREV_INSN (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));
}
}
bb_info->ru_valid = 1;
}
static void
df_ru_local_compute (df, blocks)
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 (df, bb)
struct df *df;
basic_block bb;
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
insn = PREV_INSN (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));
}
}
bb_info->lr_valid = 1;
}
static void
df_lr_local_compute (df, blocks)
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 (df, bb, live)
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 (insn = bb->end; insn && insn != PREV_INSN (bb->head);
insn = PREV_INSN (insn))
{
unsigned int uid = INSN_UID (insn);
unsigned int regno;
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_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,
{
reg_info[regno].lifetime++;
});
}
}
static void
df_reg_info_compute (df, blocks)
struct df *df;
bitmap blocks;
{
basic_block bb;
bitmap live;
live = BITMAP_XMALLOC ();
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_reg_info_compute (df, bb, live);
});
BITMAP_XFREE (live);
}
static int
df_bb_luids_set (df, bb)
struct df *df;
basic_block bb;
{
rtx insn;
int luid = 0;
for (insn = bb->head; ; insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
DF_INSN_LUID (df, insn) = luid++;
DF_INSN_LUID (df, insn) = luid;
if (insn == bb->end)
break;
}
return luid;
}
static int
df_luids_set (df, blocks)
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_analyse_1 (df, blocks, flags, update)
struct df *df;
bitmap blocks;
int flags;
int update;
{
int aflags;
int dflags;
int i;
basic_block bb;
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);
#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, aflags);
df_luids_set (df, blocks);
if (aflags & DF_RD_CHAIN)
{
df_reg_def_chain_create (df, blocks);
}
if (aflags & DF_RU_CHAIN)
{
df_reg_use_chain_create (df, blocks);
}
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)
{
df_rd_local_compute (df, df->flags & DF_RD ? blocks : df->all_blocks);
{
bitmap *in = xmalloc (sizeof (bitmap) * last_basic_block);
bitmap *out = xmalloc (sizeof (bitmap) * last_basic_block);
bitmap *gen = xmalloc (sizeof (bitmap) * last_basic_block);
bitmap *kill = xmalloc (sizeof (bitmap) * last_basic_block);
FOR_EACH_BB (bb)
{
in[bb->index] = DF_BB_INFO (df, bb)->rd_in;
out[bb->index] = DF_BB_INFO (df, bb)->rd_out;
gen[bb->index] = DF_BB_INFO (df, bb)->rd_gen;
kill[bb->index] = DF_BB_INFO (df, bb)->rd_kill;
}
iterative_dataflow_bitmap (in, out, gen, kill, df->all_blocks,
FORWARD, UNION, df_rd_transfer_function,
df->inverse_rc_map, NULL);
free (in);
free (out);
free (gen);
free (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)
{
df_ru_local_compute (df, df->flags & DF_RU ? blocks : df->all_blocks);
{
bitmap *in = xmalloc (sizeof (bitmap) * last_basic_block);
bitmap *out = xmalloc (sizeof (bitmap) * last_basic_block);
bitmap *gen = xmalloc (sizeof (bitmap) * last_basic_block);
bitmap *kill = xmalloc (sizeof (bitmap) * last_basic_block);
FOR_EACH_BB (bb)
{
in[bb->index] = DF_BB_INFO (df, bb)->ru_in;
out[bb->index] = DF_BB_INFO (df, bb)->ru_out;
gen[bb->index] = DF_BB_INFO (df, bb)->ru_gen;
kill[bb->index] = DF_BB_INFO (df, bb)->ru_kill;
}
iterative_dataflow_bitmap (in, out, gen, kill, df->all_blocks,
BACKWARD, UNION, df_ru_transfer_function,
df->inverse_rts_map, NULL);
free (in);
free (out);
free (gen);
free (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)
{
df_lr_local_compute (df, df->flags & DF_LR ? blocks : df->all_blocks);
{
bitmap *in = xmalloc (sizeof (bitmap) * last_basic_block);
bitmap *out = xmalloc (sizeof (bitmap) * last_basic_block);
bitmap *use = xmalloc (sizeof (bitmap) * last_basic_block);
bitmap *def = xmalloc (sizeof (bitmap) * last_basic_block);
FOR_EACH_BB (bb)
{
in[bb->index] = DF_BB_INFO (df, bb)->lr_in;
out[bb->index] = DF_BB_INFO (df, bb)->lr_out;
use[bb->index] = DF_BB_INFO (df, bb)->lr_use;
def[bb->index] = DF_BB_INFO (df, bb)->lr_def;
}
iterative_dataflow_bitmap (in, out, use, def, df->all_blocks,
BACKWARD, UNION, df_lr_transfer_function,
df->inverse_rts_map, NULL);
free (in);
free (out);
free (use);
free (def);
}
}
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 ()
{
struct df *df;
df = xcalloc (1, sizeof (struct df));
ddf = df;
return df;
}
static int
df_refs_queue (df)
struct df *df;
{
df->def_id_save = df->def_id;
df->use_id_save = df->use_id;
return 0;
}
static int
df_refs_process (df)
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 (df, bb)
struct df *df;
basic_block bb;
{
rtx insn;
int count = 0;
for (insn = bb->head; ; insn = NEXT_INSN (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++;
}
if (insn == bb->end)
break;
}
return count;
}
static int
df_refs_update (df)
struct df *df;
{
basic_block bb;
int count = 0;
if ((unsigned int) max_reg_num () >= df->reg_size)
df_reg_table_realloc (df, 0);
df_refs_queue (df);
FOR_EACH_BB_IN_BITMAP (df->bbs_modified, 0, bb,
{
count += df_bb_refs_update (df, bb);
});
df_refs_process (df);
return count;
}
static int
df_modified_p (df, blocks)
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_analyse (df, blocks, flags)
struct df *df;
bitmap blocks;
int flags;
{
int update;
if (df->n_bbs && df->n_bbs != (unsigned int) last_basic_block)
abort ();
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_analyse_1 (df, 0, flags, 0);
update = 1;
}
else
{
if (blocks == (bitmap) -1)
blocks = df->bbs_modified;
if (! df->n_bbs)
abort ();
df_analyse_1 (df, blocks, flags, 1);
bitmap_zero (df->bbs_modified);
bitmap_zero (df->insns_modified);
}
}
return update;
}
void
df_finish (df)
struct df *df;
{
df_free (df);
free (df);
}
static void
df_insn_refs_unlink (df, bb, insn)
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 (df, bb)
struct df *df;
basic_block bb;
{
rtx insn;
for (insn = bb->head; ; insn = NEXT_INSN (insn))
{
if (INSN_P (insn))
{
df_insn_refs_unlink (df, bb, insn);
}
if (insn == bb->end)
break;
}
}
static void
df_refs_unlink (df, blocks)
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 (df, bb, insn)
struct df *df;
basic_block bb ATTRIBUTE_UNUSED;
rtx insn;
{
if (insn == bb->head)
abort ();
delete_insn (insn);
df_insn_modify (df, bb, insn);
return NEXT_INSN (insn);
}
void
df_insn_modify (df, bb, insn)
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);
bitmap_set_bit (df->bbs_modified, bb->index);
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 (px, data)
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 (df, bb, insn, mem, reg)
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 (px, data)
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 (df, blocks, chain, oldreg, newreg)
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;
if (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);
}
}
else
{
abort ();
}
}
}
int
df_reg_replace (df, blocks, oldreg, newreg)
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 (df, ref, oldreg, newreg)
struct df *df;
struct ref *ref;
rtx oldreg;
rtx newreg;
{
if (! INSN_P (DF_REF_INSN (ref)))
return 0;
if (oldreg && oldreg != DF_REF_REG (ref))
abort ();
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 (df, bb, def_insn, use_insn, regno)
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 (df, bb, first_insn, last_insn)
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;
if ((GET_CODE (insn) == CALL_INSN
&& ! CONST_OR_PURE_CALL_P (insn))
|| GET_CODE (insn) == CODE_LABEL)
abort ();
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 (df, pattern, bb, insn)
struct df *df ATTRIBUTE_UNUSED;
rtx pattern;
basic_block bb;
rtx insn;
{
rtx ret_insn;
rtx prev_insn = PREV_INSN (insn);
if (insn == bb->head)
abort ();
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 (df, pattern, bb, insn)
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 (df, pattern, bb, insn)
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 (df, bb, insn, before_bb, before_insn)
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 (df, bb, insn, regno)
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;
}
static int
df_def_dominates_all_uses_p (df, def)
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 (df, bb, insn)
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 (df, def, blocks)
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 (df, bb, insn, blocks)
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 (df, regno)
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 (df, reg)
struct df *df;
rtx reg;
{
return df_regno_bb (df, REGNO (reg)) != 0;
}
int
df_reg_lifetime (df, reg)
struct df *df;
rtx reg;
{
return df->regs[REGNO (reg)].lifetime;
}
int
df_bb_reg_live_start_p (df, bb, reg)
struct df *df ATTRIBUTE_UNUSED;
basic_block bb;
rtx reg;
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
#ifdef ENABLE_CHECKING
if (! bb_info->lr_in)
abort ();
#endif
return bitmap_bit_p (bb_info->lr_in, REGNO (reg));
}
int
df_bb_reg_live_end_p (df, bb, reg)
struct df *df ATTRIBUTE_UNUSED;
basic_block bb;
rtx reg;
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
#ifdef ENABLE_CHECKING
if (! bb_info->lr_in)
abort ();
#endif
return bitmap_bit_p (bb_info->lr_out, REGNO (reg));
}
int
df_bb_regs_lives_compare (df, bb, reg1, reg2)
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;
if (df_regno_bb (df, regno1) != bb
|| df_regno_bb (df, regno2) != bb)
abort ();
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;
}
static struct ref *
df_bb_regno_last_use_find (df, bb, regno)
struct df * df;
basic_block bb ATTRIBUTE_UNUSED;
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;
}
static struct ref *
df_bb_regno_first_def_find (df, bb, regno)
struct df * df;
basic_block bb ATTRIBUTE_UNUSED;
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;
}
static struct ref *
df_bb_insn_regno_last_use_find (df, bb, insn, regno)
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 (df, bb, insn, regno)
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 (df, bb, insn, reg)
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));
if (! def)
abort ();
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 (link, file)
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 (link, file)
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 (df, flags, file)
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 (df, insn, file)
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 (df, insn, file)
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 (df, regno, file)
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 (df, ref, file)
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 (insn)
rtx insn;
{
df_insn_debug (ddf, insn, stderr);
debug_rtx (insn);
}
void
debug_df_reg (reg)
rtx reg;
{
df_regno_debug (ddf, REGNO (reg), stderr);
}
void
debug_df_regno (regno)
unsigned int regno;
{
df_regno_debug (ddf, regno, stderr);
}
void
debug_df_ref (ref)
struct ref *ref;
{
df_ref_debug (ddf, ref, stderr);
}
void
debug_df_defno (defno)
unsigned int defno;
{
df_ref_debug (ddf, ddf->defs[defno], stderr);
}
void
debug_df_useno (defno)
unsigned int defno;
{
df_ref_debug (ddf, ddf->uses[defno], stderr);
}
void
debug_df_chain (link)
struct df_link *link;
{
df_chain_dump (link, stderr);
fputc ('\n', stderr);
}
static void
hybrid_search_bitmap (block, in, out, gen, kill, dir,
conf_op, transfun, visited, pending,
data)
basic_block block;
bitmap *in, *out, *gen, *kill;
enum df_flow_dir dir;
enum df_confluence_op conf_op;
transfer_function_bitmap transfun;
sbitmap visited;
sbitmap pending;
void *data;
{
int changed;
int i = block->index;
edge e;
basic_block bb = block;
SET_BIT (visited, block->index);
if (TEST_BIT (pending, block->index))
{
if (dir == FORWARD)
{
bitmap_zero (in[i]);
for (e = bb->pred; e != 0; e = e->pred_next)
{
if (e->src == ENTRY_BLOCK_PTR)
continue;
switch (conf_op)
{
case UNION:
bitmap_a_or_b (in[i], in[i], out[e->src->index]);
break;
case INTERSECTION:
bitmap_a_and_b (in[i], in[i], out[e->src->index]);
break;
}
}
}
else
{
bitmap_zero (out[i]);
for (e = bb->succ; e != 0; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
continue;
switch (conf_op)
{
case UNION:
bitmap_a_or_b (out[i], out[i], in[e->dest->index]);
break;
case INTERSECTION:
bitmap_a_and_b (out[i], out[i], in[e->dest->index]);
break;
}
}
}
(*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
RESET_BIT (pending, i);
if (changed)
{
if (dir == FORWARD)
{
for (e = bb->succ; e != 0; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
continue;
SET_BIT (pending, e->dest->index);
}
}
else
{
for (e = bb->pred; e != 0; e = e->pred_next)
{
if (e->src == ENTRY_BLOCK_PTR || e->dest->index == i)
continue;
SET_BIT (pending, e->src->index);
}
}
}
}
if (dir == FORWARD)
{
for (e = bb->succ; e != 0; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
continue;
if (!TEST_BIT (visited, e->dest->index))
hybrid_search_bitmap (e->dest, in, out, gen, kill, dir,
conf_op, transfun, visited, pending,
data);
}
}
else
{
for (e = bb->pred; e != 0; e = e->pred_next)
{
if (e->src == ENTRY_BLOCK_PTR || e->src->index == i)
continue;
if (!TEST_BIT (visited, e->src->index))
hybrid_search_bitmap (e->src, in, out, gen, kill, dir,
conf_op, transfun, visited, pending,
data);
}
}
}
static void
hybrid_search_sbitmap (block, in, out, gen, kill, dir,
conf_op, transfun, visited, pending,
data)
basic_block block;
sbitmap *in, *out, *gen, *kill;
enum df_flow_dir dir;
enum df_confluence_op conf_op;
transfer_function_sbitmap transfun;
sbitmap visited;
sbitmap pending;
void *data;
{
int changed;
int i = block->index;
edge e;
basic_block bb = block;
SET_BIT (visited, block->index);
if (TEST_BIT (pending, block->index))
{
if (dir == FORWARD)
{
sbitmap_zero (in[i]);
for (e = bb->pred; e != 0; e = e->pred_next)
{
if (e->src == ENTRY_BLOCK_PTR)
continue;
switch (conf_op)
{
case UNION:
sbitmap_a_or_b (in[i], in[i], out[e->src->index]);
break;
case INTERSECTION:
sbitmap_a_and_b (in[i], in[i], out[e->src->index]);
break;
}
}
}
else
{
sbitmap_zero (out[i]);
for (e = bb->succ; e != 0; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR)
continue;
switch (conf_op)
{
case UNION:
sbitmap_a_or_b (out[i], out[i], in[e->dest->index]);
break;
case INTERSECTION:
sbitmap_a_and_b (out[i], out[i], in[e->dest->index]);
break;
}
}
}
(*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
RESET_BIT (pending, i);
if (changed)
{
if (dir == FORWARD)
{
for (e = bb->succ; e != 0; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
continue;
SET_BIT (pending, e->dest->index);
}
}
else
{
for (e = bb->pred; e != 0; e = e->pred_next)
{
if (e->src == ENTRY_BLOCK_PTR || e->dest->index == i)
continue;
SET_BIT (pending, e->src->index);
}
}
}
}
if (dir == FORWARD)
{
for (e = bb->succ; e != 0; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR || e->dest->index == i)
continue;
if (!TEST_BIT (visited, e->dest->index))
hybrid_search_sbitmap (e->dest, in, out, gen, kill, dir,
conf_op, transfun, visited, pending,
data);
}
}
else
{
for (e = bb->pred; e != 0; e = e->pred_next)
{
if (e->src == ENTRY_BLOCK_PTR || e->src->index == i)
continue;
if (!TEST_BIT (visited, e->src->index))
hybrid_search_sbitmap (e->src, in, out, gen, kill, dir,
conf_op, transfun, visited, pending,
data);
}
}
}
void
iterative_dataflow_sbitmap (in, out, gen, kill, blocks,
dir, conf_op, transfun, order, data)
sbitmap *in, *out, *gen, *kill;
bitmap blocks;
enum df_flow_dir dir;
enum df_confluence_op conf_op;
transfer_function_sbitmap transfun;
int *order;
void *data;
{
int i;
fibheap_t worklist;
basic_block bb;
sbitmap visited, pending;
pending = sbitmap_alloc (last_basic_block);
visited = sbitmap_alloc (last_basic_block);
sbitmap_zero (pending);
sbitmap_zero (visited);
worklist = fibheap_new ();
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
fibheap_insert (worklist, order[i], (void *) (size_t) i);
SET_BIT (pending, i);
if (dir == FORWARD)
sbitmap_copy (out[i], gen[i]);
else
sbitmap_copy (in[i], gen[i]);
});
while (sbitmap_first_set_bit (pending) != -1)
{
while (!fibheap_empty (worklist))
{
i = (size_t) fibheap_extract_min (worklist);
bb = BASIC_BLOCK (i);
if (!TEST_BIT (visited, bb->index))
hybrid_search_sbitmap (bb, in, out, gen, kill, dir,
conf_op, transfun, visited, pending, data);
}
if (sbitmap_first_set_bit (pending) != -1)
{
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
fibheap_insert (worklist, order[i], (void *) (size_t) i);
});
sbitmap_zero (visited);
}
else
{
break;
}
}
sbitmap_free (pending);
sbitmap_free (visited);
fibheap_delete (worklist);
}
void
iterative_dataflow_bitmap (in, out, gen, kill, blocks,
dir, conf_op, transfun, order, data)
bitmap *in, *out, *gen, *kill;
bitmap blocks;
enum df_flow_dir dir;
enum df_confluence_op conf_op;
transfer_function_bitmap transfun;
int *order;
void *data;
{
int i;
fibheap_t worklist;
basic_block bb;
sbitmap visited, pending;
pending = sbitmap_alloc (last_basic_block);
visited = sbitmap_alloc (last_basic_block);
sbitmap_zero (pending);
sbitmap_zero (visited);
worklist = fibheap_new ();
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
fibheap_insert (worklist, order[i], (void *) (size_t) i);
SET_BIT (pending, i);
if (dir == FORWARD)
bitmap_copy (out[i], gen[i]);
else
bitmap_copy (in[i], gen[i]);
});
while (sbitmap_first_set_bit (pending) != -1)
{
while (!fibheap_empty (worklist))
{
i = (size_t) fibheap_extract_min (worklist);
bb = BASIC_BLOCK (i);
if (!TEST_BIT (visited, bb->index))
hybrid_search_bitmap (bb, in, out, gen, kill, dir,
conf_op, transfun, visited, pending, data);
}
if (sbitmap_first_set_bit (pending) != -1)
{
EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
fibheap_insert (worklist, order[i], (void *) (size_t) i);
});
sbitmap_zero (visited);
}
else
{
break;
}
}
sbitmap_free (pending);
sbitmap_free (visited);
fibheap_delete (worklist);
}