#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 "output.h"
#include "alloc-pool.h"
#include "flags.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "sbitmap.h"
#include "bitmap.h"
#include "timevar.h"
#include "df.h"
#include "tree-pass.h"
static struct df *ddf = NULL;
struct df *shared_df = NULL;
static void *df_get_bb_info (struct dataflow *, unsigned int);
static void df_set_bb_info (struct dataflow *, unsigned int, void *);
struct df *
df_init (int flags)
{
struct df *df = XCNEW (struct df);
df_hard_reg_init ();
df_scan_add_problem (df, flags);
ddf = df;
return df;
}
struct dataflow *
df_add_problem (struct df *df, struct df_problem *problem, int flags)
{
struct dataflow *dflow;
if (problem->dependent_problem_fun)
(problem->dependent_problem_fun) (df, 0);
dflow = df->problems_by_index[problem->id];
if (dflow)
return dflow;
dflow = XCNEW (struct dataflow);
dflow->flags = flags;
dflow->df = df;
dflow->problem = problem;
df->problems_in_order[df->num_problems_defined++] = dflow;
df->problems_by_index[dflow->problem->id] = dflow;
return dflow;
}
int
df_set_flags (struct dataflow *dflow, int mask)
{
int old_flags = dflow->flags;
gcc_assert (!(mask & (~dflow->problem->changeable_flags)));
dflow->flags |= mask;
return old_flags;
}
int
df_clear_flags (struct dataflow *dflow, int mask)
{
int old_flags = dflow->flags;
gcc_assert (!(mask & (~dflow->problem->changeable_flags)));
dflow->flags &= !mask;
return old_flags;
}
void
df_set_blocks (struct df *df, bitmap blocks)
{
if (blocks)
{
if (df->blocks_to_analyze)
{
int p;
bitmap diff = BITMAP_ALLOC (NULL);
bitmap_and_compl (diff, df->blocks_to_analyze, blocks);
for (p = df->num_problems_defined - 1; p >= 0 ;p--)
{
struct dataflow *dflow = df->problems_in_order[p];
if (dflow->problem->reset_fun)
dflow->problem->reset_fun (dflow, df->blocks_to_analyze);
else if (dflow->problem->free_bb_fun)
{
bitmap_iterator bi;
unsigned int bb_index;
EXECUTE_IF_SET_IN_BITMAP (diff, 0, bb_index, bi)
{
basic_block bb = BASIC_BLOCK (bb_index);
if (bb)
{
dflow->problem->free_bb_fun
(dflow, bb, df_get_bb_info (dflow, bb_index));
df_set_bb_info (dflow, bb_index, NULL);
}
}
}
}
BITMAP_FREE (diff);
}
else
{
struct dataflow *scan_dflow = df->problems_by_index [DF_SCAN];
if (scan_dflow->problem_data)
{
bitmap blocks_to_reset = NULL;
int p;
for (p = df->num_problems_defined - 1; p >= 0 ;p--)
{
struct dataflow *dflow = df->problems_in_order[p];
if (dflow->problem->reset_fun)
{
if (!blocks_to_reset)
{
basic_block bb;
blocks_to_reset = BITMAP_ALLOC (NULL);
FOR_ALL_BB(bb)
{
bitmap_set_bit (blocks_to_reset, bb->index);
}
}
dflow->problem->reset_fun (dflow, blocks_to_reset);
}
}
if (blocks_to_reset)
BITMAP_FREE (blocks_to_reset);
}
df->blocks_to_analyze = BITMAP_ALLOC (NULL);
}
bitmap_copy (df->blocks_to_analyze, blocks);
}
else
{
if (df->blocks_to_analyze)
{
BITMAP_FREE (df->blocks_to_analyze);
df->blocks_to_analyze = NULL;
}
}
}
void
df_delete_basic_block (struct df *df, int bb_index)
{
basic_block bb = BASIC_BLOCK (bb_index);
int i;
for (i = 0; i < df->num_problems_defined; i++)
{
struct dataflow *dflow = df->problems_in_order[i];
if (dflow->problem->free_bb_fun)
dflow->problem->free_bb_fun
(dflow, bb, df_get_bb_info (dflow, bb_index));
}
}
void
df_finish1 (struct df *df)
{
int i;
for (i = 0; i < df->num_problems_defined; i++)
df->problems_in_order[i]->problem->free_fun (df->problems_in_order[i]);
free (df);
}
static void
df_hybrid_search_forward (basic_block bb,
struct dataflow *dataflow,
bool single_pass)
{
int result_changed;
int i = bb->index;
edge e;
edge_iterator ei;
SET_BIT (dataflow->visited, bb->index);
gcc_assert (TEST_BIT (dataflow->pending, bb->index));
RESET_BIT (dataflow->pending, i);
if (EDGE_COUNT (bb->preds) > 0)
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (!TEST_BIT (dataflow->considered, e->src->index))
continue;
dataflow->problem->con_fun_n (dataflow, e);
}
else if (dataflow->problem->con_fun_0)
dataflow->problem->con_fun_0 (dataflow, bb);
result_changed = dataflow->problem->trans_fun (dataflow, i);
if (!result_changed || single_pass)
return;
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e->dest->index == i)
continue;
if (!TEST_BIT (dataflow->considered, e->dest->index))
continue;
SET_BIT (dataflow->pending, e->dest->index);
}
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (e->dest->index == i)
continue;
if (!TEST_BIT (dataflow->considered, e->dest->index))
continue;
if (!TEST_BIT (dataflow->visited, e->dest->index))
df_hybrid_search_forward (e->dest, dataflow, single_pass);
}
}
static void
df_hybrid_search_backward (basic_block bb,
struct dataflow *dataflow,
bool single_pass)
{
int result_changed;
int i = bb->index;
edge e;
edge_iterator ei;
SET_BIT (dataflow->visited, bb->index);
gcc_assert (TEST_BIT (dataflow->pending, bb->index));
RESET_BIT (dataflow->pending, i);
if (EDGE_COUNT (bb->succs) > 0)
FOR_EACH_EDGE (e, ei, bb->succs)
{
if (!TEST_BIT (dataflow->considered, e->dest->index))
continue;
dataflow->problem->con_fun_n (dataflow, e);
}
else if (dataflow->problem->con_fun_0)
dataflow->problem->con_fun_0 (dataflow, bb);
result_changed = dataflow->problem->trans_fun (dataflow, i);
if (!result_changed || single_pass)
return;
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (e->src->index == i)
continue;
if (!TEST_BIT (dataflow->considered, e->src->index))
continue;
SET_BIT (dataflow->pending, e->src->index);
}
FOR_EACH_EDGE (e, ei, bb->preds)
{
if (e->src->index == i)
continue;
if (!TEST_BIT (dataflow->considered, e->src->index))
continue;
if (!TEST_BIT (dataflow->visited, e->src->index))
df_hybrid_search_backward (e->src, dataflow, single_pass);
}
}
void
df_iterative_dataflow (struct dataflow *dataflow,
bitmap blocks_to_consider, bitmap blocks_to_init,
int *blocks_in_postorder, int n_blocks,
bool single_pass)
{
unsigned int idx;
int i;
sbitmap visited = sbitmap_alloc (last_basic_block);
sbitmap pending = sbitmap_alloc (last_basic_block);
sbitmap considered = sbitmap_alloc (last_basic_block);
bitmap_iterator bi;
dataflow->visited = visited;
dataflow->pending = pending;
dataflow->considered = considered;
sbitmap_zero (visited);
sbitmap_zero (pending);
sbitmap_zero (considered);
gcc_assert (dataflow->problem->dir);
EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi)
{
SET_BIT (considered, idx);
}
for (i = 0; i < n_blocks; i++)
{
idx = blocks_in_postorder[i];
SET_BIT (pending, idx);
};
dataflow->problem->init_fun (dataflow, blocks_to_init);
while (1)
{
if (dataflow->problem->dir == DF_FORWARD)
{
for (i = n_blocks - 1 ; i >= 0 ; i--)
{
idx = blocks_in_postorder[i];
if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass);
}
}
else
{
for (i = 0; i < n_blocks; i++)
{
idx = blocks_in_postorder[i];
if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass);
}
}
if (sbitmap_first_set_bit (pending) == -1)
break;
sbitmap_zero (visited);
}
sbitmap_free (pending);
sbitmap_free (visited);
sbitmap_free (considered);
}
static unsigned
df_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_problem (struct dataflow *dflow,
bitmap blocks_to_consider,
bitmap blocks_to_init,
bitmap blocks_to_scan,
int *postorder, int n_blocks, bool single_pass)
{
if (dflow->problem->alloc_fun)
dflow->problem->alloc_fun (dflow, blocks_to_scan, blocks_to_init);
if (dflow->problem->local_compute_fun)
dflow->problem->local_compute_fun (dflow, blocks_to_consider, blocks_to_scan);
if (dflow->problem->dataflow_fun)
dflow->problem->dataflow_fun (dflow, blocks_to_consider, blocks_to_init,
postorder, n_blocks, single_pass);
if (dflow->problem->finalize_fun)
dflow->problem->finalize_fun (dflow, blocks_to_consider);
}
void
df_analyze (struct df *df)
{
int *postorder = XNEWVEC (int, last_basic_block);
bitmap current_all_blocks = BITMAP_ALLOC (NULL);
int n_blocks;
int i;
bool everything;
n_blocks = post_order_compute (postorder, true);
if (n_blocks != n_basic_blocks)
delete_unreachable_blocks ();
for (i = 0; i < n_blocks; i++)
bitmap_set_bit (current_all_blocks, postorder[i]);
if (!df->blocks_to_scan)
df_rescan_blocks (df, NULL);
bitmap_and_into (df->blocks_to_scan, current_all_blocks);
if (df->blocks_to_analyze)
{
everything = false;
bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze);
BITMAP_FREE (current_all_blocks);
}
else
{
everything = true;
df->blocks_to_analyze = current_all_blocks;
current_all_blocks = NULL;
}
for (i = 1; i < df->num_problems_defined; i++)
df_analyze_problem (df->problems_in_order[i],
df->blocks_to_analyze, df->blocks_to_analyze,
df->blocks_to_scan,
postorder, n_blocks, false);
if (everything)
{
BITMAP_FREE (df->blocks_to_analyze);
df->blocks_to_analyze = NULL;
}
BITMAP_FREE (df->blocks_to_scan);
df->blocks_to_scan = NULL;
free (postorder);
}
static void *
df_get_bb_info (struct dataflow *dflow, unsigned int index)
{
return (struct df_scan_bb_info *) dflow->block_info[index];
}
static void
df_set_bb_info (struct dataflow *dflow, unsigned int index,
void *bb_info)
{
dflow->block_info[index] = bb_info;
}
void
df_compact_blocks (struct df *df)
{
int i, p;
basic_block bb;
void **problem_temps;
int size = last_basic_block *sizeof (void *);
problem_temps = xmalloc (size);
for (p = 0; p < df->num_problems_defined; p++)
{
struct dataflow *dflow = df->problems_in_order[p];
if (dflow->problem->free_bb_fun)
{
df_grow_bb_info (dflow);
memcpy (problem_temps, dflow->block_info, size);
i = NUM_FIXED_BLOCKS;
FOR_EACH_BB (bb)
{
df_set_bb_info (dflow, i, problem_temps[bb->index]);
problem_temps[bb->index] = NULL;
i++;
}
memset (dflow->block_info + i, 0,
(last_basic_block - i) *sizeof (void *));
for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
{
basic_block bb = BASIC_BLOCK (i);
if (problem_temps[i] && bb)
dflow->problem->free_bb_fun
(dflow, bb, problem_temps[i]);
}
}
}
free (problem_temps);
i = NUM_FIXED_BLOCKS;
FOR_EACH_BB (bb)
{
SET_BASIC_BLOCK (i, bb);
bb->index = i;
i++;
}
gcc_assert (i == n_basic_blocks);
for (; i < last_basic_block; i++)
SET_BASIC_BLOCK (i, NULL);
}
void
df_bb_replace (struct df *df, int old_index, basic_block new_block)
{
int p;
for (p = 0; p < df->num_problems_defined; p++)
{
struct dataflow *dflow = df->problems_in_order[p];
if (dflow->block_info)
{
void *temp;
df_grow_bb_info (dflow);
temp = df_get_bb_info (dflow, old_index);
df_set_bb_info (dflow, old_index,
df_get_bb_info (dflow, new_block->index));
df_set_bb_info (dflow, new_block->index, temp);
}
}
SET_BASIC_BLOCK (old_index, new_block);
new_block->index = old_index;
}
struct df_ref *
df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno)
{
rtx insn;
struct df_ref *use;
unsigned int uid;
FOR_BB_INSNS_REVERSE (bb, insn)
{
if (!INSN_P (insn))
continue;
uid = INSN_UID (insn);
for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
if (DF_REF_REGNO (use) == regno)
return use;
}
return NULL;
}
struct df_ref *
df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno)
{
rtx insn;
struct df_ref *def;
unsigned int uid;
FOR_BB_INSNS (bb, insn)
{
if (!INSN_P (insn))
continue;
uid = INSN_UID (insn);
for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
if (DF_REF_REGNO (def) == regno)
return def;
}
return NULL;
}
struct df_ref *
df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno)
{
rtx insn;
struct df_ref *def;
unsigned int uid;
FOR_BB_INSNS_REVERSE (bb, insn)
{
if (!INSN_P (insn))
continue;
uid = INSN_UID (insn);
for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
if (DF_REF_REGNO (def) == regno)
return def;
}
return NULL;
}
bool
df_insn_regno_def_p (struct df *df, rtx insn, unsigned int regno)
{
unsigned int uid;
struct df_ref *def;
uid = INSN_UID (insn);
for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
if (DF_REF_REGNO (def) == regno)
return true;
return false;
}
struct df_ref *
df_find_def (struct df *df, rtx insn, rtx reg)
{
unsigned int uid;
struct df_ref *def;
if (GET_CODE (reg) == SUBREG)
reg = SUBREG_REG (reg);
gcc_assert (REG_P (reg));
uid = INSN_UID (insn);
for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
return def;
return NULL;
}
bool
df_reg_defined (struct df *df, rtx insn, rtx reg)
{
return df_find_def (df, insn, reg) != NULL;
}
struct df_ref *
df_find_use (struct df *df, rtx insn, rtx reg)
{
unsigned int uid;
struct df_ref *use;
if (GET_CODE (reg) == SUBREG)
reg = SUBREG_REG (reg);
gcc_assert (REG_P (reg));
uid = INSN_UID (insn);
for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
return use;
return NULL;
}
bool
df_reg_used (struct df *df, rtx insn, rtx reg)
{
return df_find_use (df, insn, reg) != NULL;
}
void
df_dump (struct df *df, FILE *file)
{
int i;
if (!df || !file)
return;
fprintf (file, "\n\n%s\n", current_function_name ());
fprintf (file, "\nDataflow summary:\n");
fprintf (file, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n",
df->def_info.bitmap_size, df->use_info.bitmap_size);
for (i = 0; i < df->num_problems_defined; i++)
df->problems_in_order[i]->problem->dump_fun (df->problems_in_order[i], file);
fprintf (file, "\n");
}
void
df_refs_chain_dump (struct df_ref *ref, bool follow_chain, FILE *file)
{
fprintf (file, "{ ");
while (ref)
{
fprintf (file, "%c%d(%d) ",
DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
DF_REF_ID (ref),
DF_REF_REGNO (ref));
if (follow_chain)
df_chain_dump (DF_REF_CHAIN (ref), file);
ref = ref->next_ref;
}
fprintf (file, "}");
}
void
df_regs_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_ref *ref, FILE *file)
{
fprintf (file, "{ ");
while (ref)
{
fprintf (file, "%c%d(%d) ",
DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
DF_REF_ID (ref),
DF_REF_REGNO (ref));
ref = ref->next_reg;
}
fprintf (file, "}");
}
static void
df_mws_dump (struct df_mw_hardreg *mws, FILE *file)
{
while (mws)
{
struct df_link *regs = mws->regs;
fprintf (file, "%c%d(",
(mws->type == DF_REF_REG_DEF) ? 'd' : 'u',
DF_REF_REGNO (regs->ref));
while (regs)
{
fprintf (file, "%d ", DF_REF_REGNO (regs->ref));
regs = regs->next;
}
fprintf (file, ") ");
mws = mws->next;
}
}
static void
df_insn_uid_debug (struct df *df, unsigned int uid,
bool follow_chain, FILE *file)
{
int bbi;
if (DF_INSN_UID_DEFS (df, uid))
bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
else if (DF_INSN_UID_USES(df, uid))
bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
else
bbi = -1;
fprintf (file, "insn %d bb %d luid %d",
uid, bbi, DF_INSN_UID_LUID (df, uid));
if (DF_INSN_UID_DEFS (df, uid))
{
fprintf (file, " defs ");
df_refs_chain_dump (DF_INSN_UID_DEFS (df, uid), follow_chain, file);
}
if (DF_INSN_UID_USES (df, uid))
{
fprintf (file, " uses ");
df_refs_chain_dump (DF_INSN_UID_USES (df, uid), follow_chain, file);
}
if (DF_INSN_UID_MWS (df, uid))
{
fprintf (file, " mws ");
df_mws_dump (DF_INSN_UID_MWS (df, uid), file);
}
fprintf (file, "\n");
}
void
df_insn_debug (struct df *df, rtx insn, bool follow_chain, FILE *file)
{
df_insn_uid_debug (df, INSN_UID (insn), follow_chain, file);
}
void
df_insn_debug_regno (struct df *df, rtx insn, FILE *file)
{
unsigned int uid;
int bbi;
uid = INSN_UID (insn);
if (DF_INSN_UID_DEFS (df, uid))
bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
else if (DF_INSN_UID_USES(df, uid))
bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
else
bbi = -1;
fprintf (file, "insn %d bb %d luid %d defs ",
uid, bbi, DF_INSN_LUID (df, insn));
df_regs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), file);
fprintf (file, " uses ");
df_regs_chain_dump (df, DF_INSN_UID_USES (df, uid), file);
fprintf (file, "\n");
}
void
df_regno_debug (struct df *df, unsigned int regno, FILE *file)
{
fprintf (file, "reg %d defs ", regno);
df_regs_chain_dump (df, DF_REG_DEF_GET (df, regno)->reg_chain, file);
fprintf (file, " uses ");
df_regs_chain_dump (df, DF_REG_USE_GET (df, regno)->reg_chain, file);
fprintf (file, "\n");
}
void
df_ref_debug (struct df_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 insn %d flag %x chain ",
DF_REF_REGNO (ref),
DF_REF_BBNO (ref),
DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1,
DF_REF_FLAGS (ref));
df_chain_dump (DF_REF_CHAIN (ref), file);
fprintf (file, "\n");
}
void
debug_df_insn (rtx insn)
{
df_insn_debug (ddf, insn, true, 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 df_ref *ref)
{
df_ref_debug (ref, stderr);
}
void
debug_df_defno (unsigned int defno)
{
df_ref_debug (DF_DEFS_GET (ddf, defno), stderr);
}
void
debug_df_useno (unsigned int defno)
{
df_ref_debug (DF_USES_GET (ddf, defno), stderr);
}
void
debug_df_chain (struct df_link *link)
{
df_chain_dump (link, stderr);
fputc ('\n', stderr);
}