#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 "vecprim.h"
#include "except.h"
#if 0
#define REG_DEAD_DEBUGGING
#endif
#define DF_SPARSE_THRESHOLD 32
static bitmap seen_in_block = NULL;
static bitmap seen_in_insn = NULL;
static void df_ri_dump (struct dataflow *, FILE *);
struct df_link *
df_chain_create (struct dataflow *dflow, struct df_ref *src, struct df_ref *dst)
{
struct df_link *head = DF_REF_CHAIN (src);
struct df_link *link = pool_alloc (dflow->block_pool);;
DF_REF_CHAIN (src) = link;
link->next = head;
link->ref = dst;
return link;
}
void
df_chain_unlink (struct dataflow *dflow, struct df_ref *ref, struct df_link *link)
{
struct df_link *chain = DF_REF_CHAIN (ref);
if (link)
{
if (chain == link)
DF_REF_CHAIN (ref) = link->next;
else
{
struct df_link *prev = chain;
while (chain)
{
if (chain == link)
{
prev->next = chain->next;
break;
}
prev = chain;
chain = chain->next;
}
}
pool_free (dflow->block_pool, link);
}
else
{
while (chain)
{
struct df_link *next = chain->next;
df_chain_unlink (dflow, chain->ref, chain);
chain = next;
}
}
}
void
df_chain_copy (struct dataflow *dflow,
struct df_ref *to_ref,
struct df_link *from_ref)
{
while (from_ref)
{
df_chain_create (dflow, to_ref, from_ref->ref);
from_ref = from_ref->next;
}
}
bitmap
df_get_live_in (struct df *df, basic_block bb)
{
gcc_assert (df->problems_by_index[DF_LR]);
if (df->problems_by_index[DF_UREC])
return DF_RA_LIVE_IN (df, bb);
else if (df->problems_by_index[DF_UR])
return DF_LIVE_IN (df, bb);
else
return DF_UPWARD_LIVE_IN (df, bb);
}
bitmap
df_get_live_out (struct df *df, basic_block bb)
{
gcc_assert (df->problems_by_index[DF_LR]);
if (df->problems_by_index[DF_UREC])
return DF_RA_LIVE_OUT (df, bb);
else if (df->problems_by_index[DF_UR])
return DF_LIVE_OUT (df, bb);
else
return DF_UPWARD_LIVE_OUT (df, bb);
}
void
df_grow_bb_info (struct dataflow *dflow)
{
unsigned int new_size = last_basic_block + 1;
if (dflow->block_info_size < new_size)
{
new_size += new_size / 4;
dflow->block_info = xrealloc (dflow->block_info,
new_size *sizeof (void*));
memset (dflow->block_info + dflow->block_info_size, 0,
(new_size - dflow->block_info_size) *sizeof (void *));
dflow->block_info_size = new_size;
}
}
void
df_chain_dump (struct df_link *link, FILE *file)
{
fprintf (file, "{ ");
for (; link; link = link->next)
{
fprintf (file, "%c%d(bb %d insn %d) ",
DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
DF_REF_ID (link->ref),
DF_REF_BBNO (link->ref),
DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
}
fprintf (file, "}");
}
void
df_print_bb_index (basic_block bb, FILE *file)
{
edge e;
edge_iterator ei;
fprintf (file, "( ");
FOR_EACH_EDGE (e, ei, bb->preds)
{
basic_block pred = e->src;
fprintf (file, "%d ", pred->index);
}
fprintf (file, ")->[%d]->( ", bb->index);
FOR_EACH_EDGE (e, ei, bb->succs)
{
basic_block succ = e->dest;
fprintf (file, "%d ", succ->index);
}
fprintf (file, ")\n");
}
static inline bitmap
df_ref_bitmap (bitmap *maps, unsigned int regno, int start, int count)
{
bitmap ids = maps[regno];
if (!ids)
{
unsigned int i;
unsigned int end = start + count;;
ids = BITMAP_ALLOC (NULL);
maps[regno] = ids;
for (i = start; i < end; i++)
bitmap_set_bit (ids, i);
}
return ids;
}
static void
df_set_seen (void)
{
seen_in_block = BITMAP_ALLOC (NULL);
seen_in_insn = BITMAP_ALLOC (NULL);
}
static void
df_unset_seen (void)
{
BITMAP_FREE (seen_in_block);
BITMAP_FREE (seen_in_insn);
}
struct df_ru_problem_data
{
bitmap *use_sites;
unsigned int use_sites_size;
bitmap sparse_invalidated_by_call;
bitmap dense_invalidated_by_call;
};
struct df_ru_bb_info *
df_ru_get_bb_info (struct dataflow *dflow, unsigned int index)
{
return (struct df_ru_bb_info *) dflow->block_info[index];
}
static void
df_ru_set_bb_info (struct dataflow *dflow, unsigned int index,
struct df_ru_bb_info *bb_info)
{
dflow->block_info[index] = bb_info;
}
static void
df_ru_free_bb_info (struct dataflow *dflow,
basic_block bb ATTRIBUTE_UNUSED,
void *vbb_info)
{
struct df_ru_bb_info *bb_info = (struct df_ru_bb_info *) vbb_info;
if (bb_info)
{
BITMAP_FREE (bb_info->kill);
BITMAP_FREE (bb_info->sparse_kill);
BITMAP_FREE (bb_info->gen);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
pool_free (dflow->block_pool, bb_info);
}
}
static void
df_ru_alloc (struct dataflow *dflow,
bitmap blocks_to_rescan ATTRIBUTE_UNUSED,
bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
unsigned int reg_size = max_reg_num ();
if (!dflow->block_pool)
dflow->block_pool = create_alloc_pool ("df_ru_block pool",
sizeof (struct df_ru_bb_info), 50);
if (dflow->problem_data)
{
unsigned int i;
struct df_ru_problem_data *problem_data
= (struct df_ru_problem_data *) dflow->problem_data;
for (i = 0; i < problem_data->use_sites_size; i++)
{
bitmap bm = problem_data->use_sites[i];
if (bm)
{
BITMAP_FREE (bm);
problem_data->use_sites[i] = NULL;
}
}
if (problem_data->use_sites_size < reg_size)
{
problem_data->use_sites
= xrealloc (problem_data->use_sites, reg_size * sizeof (bitmap));
memset (problem_data->use_sites + problem_data->use_sites_size, 0,
(reg_size - problem_data->use_sites_size) * sizeof (bitmap));
problem_data->use_sites_size = reg_size;
}
bitmap_clear (problem_data->sparse_invalidated_by_call);
bitmap_clear (problem_data->dense_invalidated_by_call);
}
else
{
struct df_ru_problem_data *problem_data = XNEW (struct df_ru_problem_data);
dflow->problem_data = problem_data;
problem_data->use_sites = XCNEWVEC (bitmap, reg_size);
problem_data->use_sites_size = reg_size;
problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL);
problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL);
}
df_grow_bb_info (dflow);
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
if (bb_info)
{
bitmap_clear (bb_info->kill);
bitmap_clear (bb_info->sparse_kill);
bitmap_clear (bb_info->gen);
}
else
{
bb_info = (struct df_ru_bb_info *) pool_alloc (dflow->block_pool);
df_ru_set_bb_info (dflow, bb_index, bb_info);
bb_info->kill = BITMAP_ALLOC (NULL);
bb_info->sparse_kill = BITMAP_ALLOC (NULL);
bb_info->gen = BITMAP_ALLOC (NULL);
bb_info->in = BITMAP_ALLOC (NULL);
bb_info->out = BITMAP_ALLOC (NULL);
}
}
}
static void
df_ru_bb_local_compute_process_def (struct dataflow *dflow,
struct df_ru_bb_info *bb_info,
struct df_ref *def,
enum df_ref_flags top_flag)
{
struct df *df = dflow->df;
while (def)
{
if ((top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
&& (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)))
{
unsigned int regno = DF_REF_REGNO (def);
unsigned int begin = DF_REG_USE_GET (df, regno)->begin;
unsigned int n_uses = DF_REG_USE_GET (df, regno)->n_refs;
if (!bitmap_bit_p (seen_in_block, regno))
{
if (!bitmap_bit_p (seen_in_insn, regno))
{
if (n_uses > DF_SPARSE_THRESHOLD)
bitmap_set_bit (bb_info->sparse_kill, regno);
else
{
struct df_ru_problem_data * problem_data
= (struct df_ru_problem_data *)dflow->problem_data;
bitmap uses
= df_ref_bitmap (problem_data->use_sites, regno,
begin, n_uses);
bitmap_ior_into (bb_info->kill, uses);
}
}
bitmap_set_bit (seen_in_insn, regno);
}
}
def = def->next_ref;
}
}
static void
df_ru_bb_local_compute_process_use (struct df_ru_bb_info *bb_info,
struct df_ref *use,
enum df_ref_flags top_flag)
{
while (use)
{
if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
{
unsigned int regno = DF_REF_REGNO (use);
if (!bitmap_bit_p (seen_in_block, regno))
bitmap_set_bit (bb_info->gen, DF_REF_ID (use));
}
use = use->next_ref;
}
}
static void
df_ru_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
{
struct df *df = dflow->df;
basic_block bb = BASIC_BLOCK (bb_index);
struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
rtx insn;
bitmap_clear (seen_in_block);
bitmap_clear (seen_in_insn);
#ifdef EH_USES
df_ru_bb_local_compute_process_use (bb_info,
df_get_artificial_uses (df, bb_index),
DF_REF_AT_TOP);
#endif
df_ru_bb_local_compute_process_def (dflow, bb_info,
df_get_artificial_defs (df, bb_index),
DF_REF_AT_TOP);
FOR_BB_INSNS (bb, insn)
{
unsigned int uid = INSN_UID (insn);
if (!INSN_P (insn))
continue;
df_ru_bb_local_compute_process_use (bb_info,
DF_INSN_UID_USES (df, uid), 0);
df_ru_bb_local_compute_process_def (dflow, bb_info,
DF_INSN_UID_DEFS (df, uid), 0);
bitmap_ior_into (seen_in_block, seen_in_insn);
bitmap_clear (seen_in_insn);
}
df_ru_bb_local_compute_process_use (bb_info,
df_get_artificial_uses (df, bb_index), 0);
df_ru_bb_local_compute_process_def (dflow, bb_info,
df_get_artificial_defs (df, bb_index), 0);
}
static void
df_ru_local_compute (struct dataflow *dflow,
bitmap all_blocks,
bitmap rescan_blocks ATTRIBUTE_UNUSED)
{
struct df *df = dflow->df;
unsigned int bb_index;
bitmap_iterator bi;
unsigned int regno;
struct df_ru_problem_data *problem_data
= (struct df_ru_problem_data *) dflow->problem_data;
bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
df_set_seen ();
if (!df->use_info.refs_organized)
df_reorganize_refs (&df->use_info);
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
df_ru_bb_local_compute (dflow, bb_index);
}
EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
{
struct df_reg_info *reg_info = DF_REG_USE_GET (df, regno);
if (reg_info->n_refs > DF_SPARSE_THRESHOLD)
bitmap_set_bit (sparse_invalidated, regno);
else
{
bitmap defs = df_ref_bitmap (problem_data->use_sites, regno,
reg_info->begin, reg_info->n_refs);
bitmap_ior_into (dense_invalidated, defs);
}
}
df_unset_seen ();
}
static void
df_ru_init_solution (struct dataflow *dflow, bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
bitmap_copy (bb_info->in, bb_info->gen);
bitmap_clear (bb_info->out);
}
}
static void
df_ru_confluence_n (struct dataflow *dflow, edge e)
{
bitmap op1 = df_ru_get_bb_info (dflow, e->src->index)->out;
bitmap op2 = df_ru_get_bb_info (dflow, e->dest->index)->in;
if (e->flags & EDGE_EH)
{
struct df_ru_problem_data *problem_data
= (struct df_ru_problem_data *) dflow->problem_data;
bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
struct df *df = dflow->df;
bitmap_iterator bi;
unsigned int regno;
bitmap tmp = BITMAP_ALLOC (NULL);
bitmap_copy (tmp, op2);
bitmap_and_compl_into (tmp, dense_invalidated);
EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
{
bitmap_clear_range (tmp,
DF_REG_USE_GET (df, regno)->begin,
DF_REG_USE_GET (df, regno)->n_refs);
}
bitmap_ior_into (op1, tmp);
BITMAP_FREE (tmp);
}
else
bitmap_ior_into (op1, op2);
}
static bool
df_ru_transfer_function (struct dataflow *dflow, int bb_index)
{
struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
unsigned int regno;
bitmap_iterator bi;
bitmap in = bb_info->in;
bitmap out = bb_info->out;
bitmap gen = bb_info->gen;
bitmap kill = bb_info->kill;
bitmap sparse_kill = bb_info->sparse_kill;
if (bitmap_empty_p (sparse_kill))
return bitmap_ior_and_compl (in, gen, out, kill);
else
{
struct df *df = dflow->df;
bool changed = false;
bitmap tmp = BITMAP_ALLOC (NULL);
bitmap_copy (tmp, out);
EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
{
bitmap_clear_range (tmp,
DF_REG_USE_GET (df, regno)->begin,
DF_REG_USE_GET (df, regno)->n_refs);
}
bitmap_and_compl_into (tmp, kill);
bitmap_ior_into (tmp, gen);
changed = !bitmap_equal_p (tmp, in);
if (changed)
{
BITMAP_FREE (in);
bb_info->in = tmp;
}
else
BITMAP_FREE (tmp);
return changed;
}
}
static void
df_ru_free (struct dataflow *dflow)
{
unsigned int i;
struct df_ru_problem_data *problem_data
= (struct df_ru_problem_data *) dflow->problem_data;
if (problem_data)
{
for (i = 0; i < dflow->block_info_size; i++)
{
struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, i);
if (bb_info)
{
BITMAP_FREE (bb_info->kill);
BITMAP_FREE (bb_info->sparse_kill);
BITMAP_FREE (bb_info->gen);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
}
}
free_alloc_pool (dflow->block_pool);
for (i = 0; i < problem_data->use_sites_size; i++)
{
bitmap bm = problem_data->use_sites[i];
if (bm)
BITMAP_FREE (bm);
}
free (problem_data->use_sites);
BITMAP_FREE (problem_data->sparse_invalidated_by_call);
BITMAP_FREE (problem_data->dense_invalidated_by_call);
dflow->block_info_size = 0;
free (dflow->block_info);
free (dflow->problem_data);
}
free (dflow);
}
static void
df_ru_dump (struct dataflow *dflow, FILE *file)
{
basic_block bb;
struct df *df = dflow->df;
struct df_ru_problem_data *problem_data
= (struct df_ru_problem_data *) dflow->problem_data;
unsigned int m = max_reg_num ();
unsigned int regno;
if (!dflow->block_info)
return;
fprintf (file, "Reaching uses:\n");
fprintf (file, " sparse invalidated \t");
dump_bitmap (file, problem_data->sparse_invalidated_by_call);
fprintf (file, " dense invalidated \t");
dump_bitmap (file, problem_data->dense_invalidated_by_call);
for (regno = 0; regno < m; regno++)
if (DF_REG_USE_GET (df, regno)->n_refs)
fprintf (file, "%d[%d,%d] ", regno,
DF_REG_USE_GET (df, regno)->begin,
DF_REG_USE_GET (df, regno)->n_refs);
fprintf (file, "\n");
FOR_ALL_BB (bb)
{
struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb->index);
df_print_bb_index (bb, file);
if (!bb_info->in)
continue;
fprintf (file, " in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
dump_bitmap (file, bb_info->in);
fprintf (file, " gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
dump_bitmap (file, bb_info->gen);
fprintf (file, " kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
dump_bitmap (file, bb_info->kill);
fprintf (file, " out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
dump_bitmap (file, bb_info->out);
}
}
static struct df_problem problem_RU =
{
DF_RU,
DF_BACKWARD,
df_ru_alloc,
NULL,
df_ru_free_bb_info,
df_ru_local_compute,
df_ru_init_solution,
df_iterative_dataflow,
NULL,
df_ru_confluence_n,
df_ru_transfer_function,
NULL,
df_ru_free,
df_ru_dump,
NULL,
0
};
struct dataflow *
df_ru_add_problem (struct df *df, int flags)
{
return df_add_problem (df, &problem_RU, flags);
}
struct df_rd_problem_data
{
bitmap *def_sites;
unsigned int def_sites_size;
bitmap sparse_invalidated_by_call;
bitmap dense_invalidated_by_call;
};
struct df_rd_bb_info *
df_rd_get_bb_info (struct dataflow *dflow, unsigned int index)
{
return (struct df_rd_bb_info *) dflow->block_info[index];
}
static void
df_rd_set_bb_info (struct dataflow *dflow, unsigned int index,
struct df_rd_bb_info *bb_info)
{
dflow->block_info[index] = bb_info;
}
static void
df_rd_free_bb_info (struct dataflow *dflow,
basic_block bb ATTRIBUTE_UNUSED,
void *vbb_info)
{
struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
if (bb_info)
{
BITMAP_FREE (bb_info->kill);
BITMAP_FREE (bb_info->sparse_kill);
BITMAP_FREE (bb_info->gen);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
pool_free (dflow->block_pool, bb_info);
}
}
static void
df_rd_alloc (struct dataflow *dflow,
bitmap blocks_to_rescan ATTRIBUTE_UNUSED,
bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
unsigned int reg_size = max_reg_num ();
if (!dflow->block_pool)
dflow->block_pool = create_alloc_pool ("df_rd_block pool",
sizeof (struct df_rd_bb_info), 50);
if (dflow->problem_data)
{
unsigned int i;
struct df_rd_problem_data *problem_data
= (struct df_rd_problem_data *) dflow->problem_data;
for (i = 0; i < problem_data->def_sites_size; i++)
{
bitmap bm = problem_data->def_sites[i];
if (bm)
{
BITMAP_FREE (bm);
problem_data->def_sites[i] = NULL;
}
}
if (problem_data->def_sites_size < reg_size)
{
problem_data->def_sites
= xrealloc (problem_data->def_sites, reg_size *sizeof (bitmap));
memset (problem_data->def_sites + problem_data->def_sites_size, 0,
(reg_size - problem_data->def_sites_size) *sizeof (bitmap));
problem_data->def_sites_size = reg_size;
}
bitmap_clear (problem_data->sparse_invalidated_by_call);
bitmap_clear (problem_data->dense_invalidated_by_call);
}
else
{
struct df_rd_problem_data *problem_data = XNEW (struct df_rd_problem_data);
dflow->problem_data = problem_data;
problem_data->def_sites = XCNEWVEC (bitmap, reg_size);
problem_data->def_sites_size = reg_size;
problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL);
problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL);
}
df_grow_bb_info (dflow);
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
if (bb_info)
{
bitmap_clear (bb_info->kill);
bitmap_clear (bb_info->sparse_kill);
bitmap_clear (bb_info->gen);
}
else
{
bb_info = (struct df_rd_bb_info *) pool_alloc (dflow->block_pool);
df_rd_set_bb_info (dflow, bb_index, bb_info);
bb_info->kill = BITMAP_ALLOC (NULL);
bb_info->sparse_kill = BITMAP_ALLOC (NULL);
bb_info->gen = BITMAP_ALLOC (NULL);
bb_info->in = BITMAP_ALLOC (NULL);
bb_info->out = BITMAP_ALLOC (NULL);
}
}
}
static void
df_rd_bb_local_compute_process_def (struct dataflow *dflow,
struct df_rd_bb_info *bb_info,
struct df_ref *def,
enum df_ref_flags top_flag)
{
struct df *df = dflow->df;
while (def)
{
if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
{
unsigned int regno = DF_REF_REGNO (def);
unsigned int begin = DF_REG_DEF_GET (df, regno)->begin;
unsigned int n_defs = DF_REG_DEF_GET (df, regno)->n_refs;
if (!bitmap_bit_p (seen_in_block, regno))
{
if ((!bitmap_bit_p (seen_in_insn, regno))
&& (!((DF_REF_FLAGS (def) & DF_REF_PARTIAL)
|| (DF_REF_FLAGS (def) & DF_REF_MAY_CLOBBER))))
{
if (n_defs > DF_SPARSE_THRESHOLD)
{
bitmap_set_bit (bb_info->sparse_kill, regno);
bitmap_clear_range(bb_info->gen, begin, n_defs);
}
else
{
struct df_rd_problem_data * problem_data
= (struct df_rd_problem_data *)dflow->problem_data;
bitmap defs = df_ref_bitmap (problem_data->def_sites,
regno, begin, n_defs);
bitmap_ior_into (bb_info->kill, defs);
bitmap_and_compl_into (bb_info->gen, defs);
}
}
bitmap_set_bit (seen_in_insn, regno);
if (!(DF_REF_FLAGS (def)
& (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
}
}
def = def->next_ref;
}
}
static void
df_rd_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
{
struct df *df = dflow->df;
basic_block bb = BASIC_BLOCK (bb_index);
struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
rtx insn;
bitmap_clear (seen_in_block);
bitmap_clear (seen_in_insn);
df_rd_bb_local_compute_process_def (dflow, bb_info,
df_get_artificial_defs (df, bb_index), 0);
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
if (!INSN_P (insn))
continue;
df_rd_bb_local_compute_process_def (dflow, bb_info,
DF_INSN_UID_DEFS (df, uid), 0);
bitmap_ior_into (seen_in_block, seen_in_insn);
bitmap_clear (seen_in_insn);
}
df_rd_bb_local_compute_process_def (dflow, bb_info,
df_get_artificial_defs (df, bb_index),
DF_REF_AT_TOP);
}
static void
df_rd_local_compute (struct dataflow *dflow,
bitmap all_blocks,
bitmap rescan_blocks ATTRIBUTE_UNUSED)
{
struct df *df = dflow->df;
unsigned int bb_index;
bitmap_iterator bi;
unsigned int regno;
struct df_rd_problem_data *problem_data
= (struct df_rd_problem_data *) dflow->problem_data;
bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
df_set_seen ();
if (!df->def_info.refs_organized)
df_reorganize_refs (&df->def_info);
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
df_rd_bb_local_compute (dflow, bb_index);
}
EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
{
struct df_reg_info *reg_info = DF_REG_DEF_GET (df, regno);
if (reg_info->n_refs > DF_SPARSE_THRESHOLD)
{
bitmap_set_bit (sparse_invalidated, regno);
}
else
{
bitmap defs = df_ref_bitmap (problem_data->def_sites, regno,
reg_info->begin, reg_info->n_refs);
bitmap_ior_into (dense_invalidated, defs);
}
}
df_unset_seen ();
}
static void
df_rd_init_solution (struct dataflow *dflow, bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
bitmap_copy (bb_info->out, bb_info->gen);
bitmap_clear (bb_info->in);
}
}
static void
df_rd_confluence_n (struct dataflow *dflow, edge e)
{
bitmap op1 = df_rd_get_bb_info (dflow, e->dest->index)->in;
bitmap op2 = df_rd_get_bb_info (dflow, e->src->index)->out;
if (e->flags & EDGE_EH)
{
struct df_rd_problem_data *problem_data
= (struct df_rd_problem_data *) dflow->problem_data;
bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
struct df *df = dflow->df;
bitmap_iterator bi;
unsigned int regno;
bitmap tmp = BITMAP_ALLOC (NULL);
bitmap_copy (tmp, op2);
bitmap_and_compl_into (tmp, dense_invalidated);
EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
{
bitmap_clear_range (tmp,
DF_REG_DEF_GET (df, regno)->begin,
DF_REG_DEF_GET (df, regno)->n_refs);
}
bitmap_ior_into (op1, tmp);
BITMAP_FREE (tmp);
}
else
bitmap_ior_into (op1, op2);
}
static bool
df_rd_transfer_function (struct dataflow *dflow, int bb_index)
{
struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
unsigned int regno;
bitmap_iterator bi;
bitmap in = bb_info->in;
bitmap out = bb_info->out;
bitmap gen = bb_info->gen;
bitmap kill = bb_info->kill;
bitmap sparse_kill = bb_info->sparse_kill;
if (bitmap_empty_p (sparse_kill))
return bitmap_ior_and_compl (out, gen, in, kill);
else
{
struct df *df = dflow->df;
bool changed = false;
bitmap tmp = BITMAP_ALLOC (NULL);
bitmap_copy (tmp, in);
EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
{
bitmap_clear_range (tmp,
DF_REG_DEF_GET (df, regno)->begin,
DF_REG_DEF_GET (df, regno)->n_refs);
}
bitmap_and_compl_into (tmp, kill);
bitmap_ior_into (tmp, gen);
changed = !bitmap_equal_p (tmp, out);
if (changed)
{
BITMAP_FREE (out);
bb_info->out = tmp;
}
else
BITMAP_FREE (tmp);
return changed;
}
}
static void
df_rd_free (struct dataflow *dflow)
{
unsigned int i;
struct df_rd_problem_data *problem_data
= (struct df_rd_problem_data *) dflow->problem_data;
if (problem_data)
{
for (i = 0; i < dflow->block_info_size; i++)
{
struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, i);
if (bb_info)
{
BITMAP_FREE (bb_info->kill);
BITMAP_FREE (bb_info->sparse_kill);
BITMAP_FREE (bb_info->gen);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
}
}
free_alloc_pool (dflow->block_pool);
for (i = 0; i < problem_data->def_sites_size; i++)
{
bitmap bm = problem_data->def_sites[i];
if (bm)
BITMAP_FREE (bm);
}
free (problem_data->def_sites);
BITMAP_FREE (problem_data->sparse_invalidated_by_call);
BITMAP_FREE (problem_data->dense_invalidated_by_call);
dflow->block_info_size = 0;
free (dflow->block_info);
free (dflow->problem_data);
}
free (dflow);
}
static void
df_rd_dump (struct dataflow *dflow, FILE *file)
{
struct df *df = dflow->df;
basic_block bb;
struct df_rd_problem_data *problem_data
= (struct df_rd_problem_data *) dflow->problem_data;
unsigned int m = max_reg_num ();
unsigned int regno;
if (!dflow->block_info)
return;
fprintf (file, "Reaching defs:\n\n");
fprintf (file, " sparse invalidated \t");
dump_bitmap (file, problem_data->sparse_invalidated_by_call);
fprintf (file, " dense invalidated \t");
dump_bitmap (file, problem_data->dense_invalidated_by_call);
for (regno = 0; regno < m; regno++)
if (DF_REG_DEF_GET (df, regno)->n_refs)
fprintf (file, "%d[%d,%d] ", regno,
DF_REG_DEF_GET (df, regno)->begin,
DF_REG_DEF_GET (df, regno)->n_refs);
fprintf (file, "\n");
FOR_ALL_BB (bb)
{
struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb->index);
df_print_bb_index (bb, file);
if (!bb_info->in)
continue;
fprintf (file, " in \t(%d)\n", (int) bitmap_count_bits (bb_info->in));
dump_bitmap (file, bb_info->in);
fprintf (file, " gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
dump_bitmap (file, bb_info->gen);
fprintf (file, " kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
dump_bitmap (file, bb_info->kill);
fprintf (file, " out \t(%d)\n", (int) bitmap_count_bits (bb_info->out));
dump_bitmap (file, bb_info->out);
}
}
static struct df_problem problem_RD =
{
DF_RD,
DF_FORWARD,
df_rd_alloc,
NULL,
df_rd_free_bb_info,
df_rd_local_compute,
df_rd_init_solution,
df_iterative_dataflow,
NULL,
df_rd_confluence_n,
df_rd_transfer_function,
NULL,
df_rd_free,
df_rd_dump,
NULL,
0
};
struct dataflow *
df_rd_add_problem (struct df *df, int flags)
{
return df_add_problem (df, &problem_RD, flags);
}
struct df_lr_bb_info *
df_lr_get_bb_info (struct dataflow *dflow, unsigned int index)
{
return (struct df_lr_bb_info *) dflow->block_info[index];
}
static void
df_lr_set_bb_info (struct dataflow *dflow, unsigned int index,
struct df_lr_bb_info *bb_info)
{
dflow->block_info[index] = bb_info;
}
static void
df_lr_free_bb_info (struct dataflow *dflow,
basic_block bb ATTRIBUTE_UNUSED,
void *vbb_info)
{
struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
if (bb_info)
{
BITMAP_FREE (bb_info->use);
BITMAP_FREE (bb_info->def);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
pool_free (dflow->block_pool, bb_info);
}
}
static void
df_lr_alloc (struct dataflow *dflow, bitmap blocks_to_rescan,
bitmap all_blocks ATTRIBUTE_UNUSED)
{
unsigned int bb_index;
bitmap_iterator bi;
if (!dflow->block_pool)
dflow->block_pool = create_alloc_pool ("df_lr_block pool",
sizeof (struct df_lr_bb_info), 50);
df_grow_bb_info (dflow);
EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
{
struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
if (bb_info)
{
bitmap_clear (bb_info->def);
bitmap_clear (bb_info->use);
}
else
{
bb_info = (struct df_lr_bb_info *) pool_alloc (dflow->block_pool);
df_lr_set_bb_info (dflow, bb_index, bb_info);
bb_info->use = BITMAP_ALLOC (NULL);
bb_info->def = BITMAP_ALLOC (NULL);
bb_info->in = BITMAP_ALLOC (NULL);
bb_info->out = BITMAP_ALLOC (NULL);
}
}
}
static void
df_lr_bb_local_compute (struct dataflow *dflow,
struct df *df, unsigned int bb_index)
{
basic_block bb = BASIC_BLOCK (bb_index);
struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
rtx insn;
struct df_ref *def;
struct df_ref *use;
for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
if (((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
&& (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)))
{
unsigned int dregno = DF_REF_REGNO (def);
bitmap_set_bit (bb_info->def, dregno);
bitmap_clear_bit (bb_info->use, dregno);
}
for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref)
if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
if (!INSN_P (insn))
continue;
if (CALL_P (insn))
{
for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref)
{
unsigned int dregno = DF_REF_REGNO (def);
if (dregno >= FIRST_PSEUDO_REGISTER
|| !(SIBLING_CALL_P (insn)
&& bitmap_bit_p (df->exit_block_uses, dregno)
&& !refers_to_regno_p (dregno, dregno+1,
current_function_return_rtx,
(rtx *)0)))
{
if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))
{
bitmap_set_bit (bb_info->def, dregno);
bitmap_clear_bit (bb_info->use, dregno);
}
}
}
}
else
{
for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref)
{
unsigned int dregno = DF_REF_REGNO (def);
if (DF_INSN_CONTAINS_ASM (df, insn)
&& dregno < FIRST_PSEUDO_REGISTER)
{
unsigned int i;
unsigned int end = dregno
+ hard_regno_nregs[dregno][GET_MODE (DF_REF_REG (def))] - 1;
for (i = dregno; i <= end; ++i)
regs_asm_clobbered[i] = 1;
}
if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))
{
bitmap_set_bit (bb_info->def, dregno);
bitmap_clear_bit (bb_info->use, dregno);
}
}
}
for (use = DF_INSN_UID_USES (df, uid); use; use = use->next_ref)
bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
}
for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP)
&& (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL)))
{
unsigned int dregno = DF_REF_REGNO (def);
bitmap_set_bit (bb_info->def, dregno);
bitmap_clear_bit (bb_info->use, dregno);
}
#ifdef EH_USES
for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref)
if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
#endif
}
static void
df_lr_local_compute (struct dataflow *dflow,
bitmap all_blocks,
bitmap rescan_blocks)
{
struct df *df = dflow->df;
unsigned int bb_index;
bitmap_iterator bi;
if (bitmap_equal_p (all_blocks, rescan_blocks))
memset (regs_asm_clobbered, 0, sizeof (regs_asm_clobbered));
bitmap_clear (df->hardware_regs_used);
bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
if (!reload_completed)
{
bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
if (fixed_regs[ARG_POINTER_REGNUM])
bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
#endif
if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
&& fixed_regs[PIC_OFFSET_TABLE_REGNUM])
bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
}
if (bitmap_bit_p (rescan_blocks, EXIT_BLOCK))
{
struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, EXIT_BLOCK);
bitmap_copy (bb_info->use, df->exit_block_uses);
}
EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi)
{
if (bb_index == EXIT_BLOCK)
continue;
df_lr_bb_local_compute (dflow, df, bb_index);
}
}
static void
df_lr_init (struct dataflow *dflow, bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
bitmap_copy (bb_info->in, bb_info->use);
bitmap_clear (bb_info->out);
}
}
static void
df_lr_confluence_0 (struct dataflow *dflow, basic_block bb)
{
struct df *df = dflow->df;
bitmap op1 = df_lr_get_bb_info (dflow, bb->index)->out;
if (bb != EXIT_BLOCK_PTR)
bitmap_copy (op1, df->hardware_regs_used);
}
static void
df_lr_confluence_n (struct dataflow *dflow, edge e)
{
bitmap op1 = df_lr_get_bb_info (dflow, e->src->index)->out;
bitmap op2 = df_lr_get_bb_info (dflow, e->dest->index)->in;
if (e->flags & EDGE_EH)
bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
else
bitmap_ior_into (op1, op2);
bitmap_ior_into (op1, dflow->df->hardware_regs_used);
}
static bool
df_lr_transfer_function (struct dataflow *dflow, int bb_index)
{
struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
bitmap in = bb_info->in;
bitmap out = bb_info->out;
bitmap use = bb_info->use;
bitmap def = bb_info->def;
return bitmap_ior_and_compl (in, use, out, def);
}
static void
df_lr_free (struct dataflow *dflow)
{
if (dflow->block_info)
{
unsigned int i;
for (i = 0; i < dflow->block_info_size; i++)
{
struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, i);
if (bb_info)
{
BITMAP_FREE (bb_info->use);
BITMAP_FREE (bb_info->def);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
}
}
free_alloc_pool (dflow->block_pool);
dflow->block_info_size = 0;
free (dflow->block_info);
}
free (dflow->problem_data);
free (dflow);
}
static void
df_lr_dump (struct dataflow *dflow, FILE *file)
{
basic_block bb;
if (!dflow->block_info)
return;
fprintf (file, "Live Registers:\n");
FOR_ALL_BB (bb)
{
struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb->index);
df_print_bb_index (bb, file);
if (!bb_info->in)
continue;
fprintf (file, " in \t");
dump_bitmap (file, bb_info->in);
fprintf (file, " use \t");
dump_bitmap (file, bb_info->use);
fprintf (file, " def \t");
dump_bitmap (file, bb_info->def);
fprintf (file, " out \t");
dump_bitmap (file, bb_info->out);
}
}
static struct df_problem problem_LR =
{
DF_LR,
DF_BACKWARD,
df_lr_alloc,
NULL,
df_lr_free_bb_info,
df_lr_local_compute,
df_lr_init,
df_iterative_dataflow,
df_lr_confluence_0,
df_lr_confluence_n,
df_lr_transfer_function,
NULL,
df_lr_free,
df_lr_dump,
NULL,
0
};
struct dataflow *
df_lr_add_problem (struct df *df, int flags)
{
return df_add_problem (df, &problem_LR, flags);
}
struct df_ur_bb_info *
df_ur_get_bb_info (struct dataflow *dflow, unsigned int index)
{
return (struct df_ur_bb_info *) dflow->block_info[index];
}
static void
df_ur_set_bb_info (struct dataflow *dflow, unsigned int index,
struct df_ur_bb_info *bb_info)
{
dflow->block_info[index] = bb_info;
}
static void
df_ur_free_bb_info (struct dataflow *dflow,
basic_block bb ATTRIBUTE_UNUSED,
void *vbb_info)
{
struct df_ur_bb_info *bb_info = (struct df_ur_bb_info *) vbb_info;
if (bb_info)
{
BITMAP_FREE (bb_info->gen);
BITMAP_FREE (bb_info->kill);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
pool_free (dflow->block_pool, bb_info);
}
}
static void
df_ur_alloc (struct dataflow *dflow, bitmap blocks_to_rescan,
bitmap all_blocks ATTRIBUTE_UNUSED)
{
unsigned int bb_index;
bitmap_iterator bi;
if (!dflow->block_pool)
dflow->block_pool = create_alloc_pool ("df_ur_block pool",
sizeof (struct df_ur_bb_info), 100);
df_grow_bb_info (dflow);
EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
{
struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
if (bb_info)
{
bitmap_clear (bb_info->kill);
bitmap_clear (bb_info->gen);
}
else
{
bb_info = (struct df_ur_bb_info *) pool_alloc (dflow->block_pool);
df_ur_set_bb_info (dflow, bb_index, bb_info);
bb_info->kill = BITMAP_ALLOC (NULL);
bb_info->gen = BITMAP_ALLOC (NULL);
bb_info->in = BITMAP_ALLOC (NULL);
bb_info->out = BITMAP_ALLOC (NULL);
}
}
}
static void
df_ur_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
{
struct df *df = dflow->df;
basic_block bb = BASIC_BLOCK (bb_index);
struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
rtx insn;
struct df_ref *def;
bitmap_clear (seen_in_block);
bitmap_clear (seen_in_insn);
for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
{
unsigned int regno = DF_REF_REGNO (def);
if (!bitmap_bit_p (seen_in_block, regno))
{
bitmap_set_bit (seen_in_block, regno);
bitmap_set_bit (bb_info->gen, regno);
}
}
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
if (!INSN_P (insn))
continue;
for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref)
{
unsigned int regno = DF_REF_REGNO (def);
if (!bitmap_bit_p (seen_in_block, regno))
{
bitmap_set_bit (seen_in_insn, regno);
if (DF_REF_FLAGS (def)
& (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
{
if ((DF_REF_FLAGS (def) & DF_REF_MUST_CLOBBER)
&& (!DF_REF_FLAGS (def) & DF_REF_PARTIAL))
bitmap_set_bit (bb_info->kill, regno);
}
else
bitmap_set_bit (bb_info->gen, regno);
}
}
bitmap_ior_into (seen_in_block, seen_in_insn);
bitmap_clear (seen_in_insn);
}
for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
{
unsigned int regno = DF_REF_REGNO (def);
if (!bitmap_bit_p (seen_in_block, regno))
{
bitmap_set_bit (seen_in_block, regno);
bitmap_set_bit (bb_info->gen, regno);
}
}
}
static void
df_ur_local_compute (struct dataflow *dflow,
bitmap all_blocks ATTRIBUTE_UNUSED,
bitmap rescan_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
df_set_seen ();
EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi)
{
df_ur_bb_local_compute (dflow, bb_index);
}
df_unset_seen ();
}
static void
df_ur_init (struct dataflow *dflow, bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
bitmap_copy (bb_info->out, bb_info->gen);
bitmap_clear (bb_info->in);
}
}
static void
df_ur_local_finalize (struct dataflow *dflow, bitmap all_blocks)
{
struct df *df = dflow->df;
struct dataflow *lr_dflow = df->problems_by_index[DF_LR];
bitmap tmp = BITMAP_ALLOC (NULL);
bitmap_iterator bi;
unsigned int bb_index;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (lr_dflow, bb_index);
bitmap_and_into (bb_info->in, bb_lr_info->in);
bitmap_and_into (bb_info->out, bb_lr_info->out);
#if 1
bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in,
bb_info->kill);
bitmap_and_into (bb_info->out, tmp);
#endif
}
BITMAP_FREE (tmp);
}
static void
df_ur_confluence_n (struct dataflow *dflow, edge e)
{
bitmap op1 = df_ur_get_bb_info (dflow, e->dest->index)->in;
bitmap op2 = df_ur_get_bb_info (dflow, e->src->index)->out;
if (e->flags & EDGE_FAKE)
return;
bitmap_ior_into (op1, op2);
}
static bool
df_ur_transfer_function (struct dataflow *dflow, int bb_index)
{
struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
bitmap in = bb_info->in;
bitmap out = bb_info->out;
bitmap gen = bb_info->gen;
bitmap kill = bb_info->kill;
return bitmap_ior_and_compl (out, gen, in, kill);
}
static void
df_ur_free (struct dataflow *dflow)
{
if (dflow->block_info)
{
unsigned int i;
for (i = 0; i < dflow->block_info_size; i++)
{
struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, i);
if (bb_info)
{
BITMAP_FREE (bb_info->gen);
BITMAP_FREE (bb_info->kill);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
}
}
free_alloc_pool (dflow->block_pool);
dflow->block_info_size = 0;
free (dflow->block_info);
}
free (dflow);
}
static void
df_ur_dump (struct dataflow *dflow, FILE *file)
{
basic_block bb;
if (!dflow->block_info)
return;
fprintf (file, "Undefined regs:\n");
FOR_ALL_BB (bb)
{
struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb->index);
df_print_bb_index (bb, file);
if (!bb_info->in)
continue;
fprintf (file, " in \t");
dump_bitmap (file, bb_info->in);
fprintf (file, " gen \t");
dump_bitmap (file, bb_info->gen);
fprintf (file, " kill\t");
dump_bitmap (file, bb_info->kill);
fprintf (file, " out \t");
dump_bitmap (file, bb_info->out);
}
}
static struct df_problem problem_UR =
{
DF_UR,
DF_FORWARD,
df_ur_alloc,
NULL,
df_ur_free_bb_info,
df_ur_local_compute,
df_ur_init,
df_iterative_dataflow,
NULL,
df_ur_confluence_n,
df_ur_transfer_function,
df_ur_local_finalize,
df_ur_free,
df_ur_dump,
df_lr_add_problem,
0
};
struct dataflow *
df_ur_add_problem (struct df *df, int flags)
{
return df_add_problem (df, &problem_UR, flags);
}
struct df_urec_problem_data
{
bool earlyclobbers_found;
#ifdef STACK_REGS
bitmap stack_regs;
#endif
};
struct df_urec_bb_info *
df_urec_get_bb_info (struct dataflow *dflow, unsigned int index)
{
return (struct df_urec_bb_info *) dflow->block_info[index];
}
static void
df_urec_set_bb_info (struct dataflow *dflow, unsigned int index,
struct df_urec_bb_info *bb_info)
{
dflow->block_info[index] = bb_info;
}
static void
df_urec_free_bb_info (struct dataflow *dflow,
basic_block bb ATTRIBUTE_UNUSED,
void *vbb_info)
{
struct df_urec_bb_info *bb_info = (struct df_urec_bb_info *) vbb_info;
if (bb_info)
{
BITMAP_FREE (bb_info->gen);
BITMAP_FREE (bb_info->kill);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
BITMAP_FREE (bb_info->earlyclobber);
pool_free (dflow->block_pool, bb_info);
}
}
static void
df_urec_alloc (struct dataflow *dflow, bitmap blocks_to_rescan,
bitmap all_blocks ATTRIBUTE_UNUSED)
{
unsigned int bb_index;
bitmap_iterator bi;
struct df_urec_problem_data *problem_data
= (struct df_urec_problem_data *) dflow->problem_data;
if (!dflow->block_pool)
dflow->block_pool = create_alloc_pool ("df_urec_block pool",
sizeof (struct df_urec_bb_info), 50);
if (!dflow->problem_data)
{
problem_data = XNEW (struct df_urec_problem_data);
dflow->problem_data = problem_data;
}
problem_data->earlyclobbers_found = false;
df_grow_bb_info (dflow);
EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
{
struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
if (bb_info)
{
bitmap_clear (bb_info->kill);
bitmap_clear (bb_info->gen);
bitmap_clear (bb_info->earlyclobber);
}
else
{
bb_info = (struct df_urec_bb_info *) pool_alloc (dflow->block_pool);
df_urec_set_bb_info (dflow, bb_index, bb_info);
bb_info->kill = BITMAP_ALLOC (NULL);
bb_info->gen = BITMAP_ALLOC (NULL);
bb_info->in = BITMAP_ALLOC (NULL);
bb_info->out = BITMAP_ALLOC (NULL);
bb_info->earlyclobber = BITMAP_ALLOC (NULL);
}
}
}
static void
df_urec_mark_reg_change (rtx reg, rtx setter, void *data)
{
int regno;
int endregno;
int i;
struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
if (GET_CODE (reg) == SUBREG)
reg = SUBREG_REG (reg);
if (!REG_P (reg))
return;
endregno = regno = REGNO (reg);
if (regno < FIRST_PSEUDO_REGISTER)
{
endregno +=hard_regno_nregs[regno][GET_MODE (reg)];
for (i = regno; i < endregno; i++)
{
bitmap_set_bit (bb_info->kill, i);
if (GET_CODE (setter) != CLOBBER)
bitmap_set_bit (bb_info->gen, i);
else
bitmap_clear_bit (bb_info->gen, i);
}
}
else
{
bitmap_set_bit (bb_info->kill, regno);
if (GET_CODE (setter) != CLOBBER)
bitmap_set_bit (bb_info->gen, regno);
else
bitmap_clear_bit (bb_info->gen, regno);
}
}
static VEC(int,heap) *earlyclobber_regclass;
static bool
df_urec_check_earlyclobber (rtx insn)
{
int opno;
bool found = false;
extract_insn (insn);
VEC_truncate (int, earlyclobber_regclass, 0);
for (opno = 0; opno < recog_data.n_operands; opno++)
{
char c;
bool amp_p;
int i;
enum reg_class class;
const char *p = recog_data.constraints[opno];
class = NO_REGS;
amp_p = false;
for (;;)
{
c = *p;
switch (c)
{
case '=': case '+': case '?':
case '#': case '!':
case '*': case '%':
case 'm': case '<': case '>': case 'V': case 'o':
case 'E': case 'F': case 'G': case 'H':
case 's': case 'i': case 'n':
case 'I': case 'J': case 'K': case 'L':
case 'M': case 'N': case 'O': case 'P':
case 'X':
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
break;
case '&':
amp_p = true;
break;
case '\0':
case ',':
if (amp_p && class != NO_REGS)
{
int rc;
found = true;
for (i = 0;
VEC_iterate (int, earlyclobber_regclass, i, rc);
i++)
{
if (rc == (int) class)
goto found_rc;
}
VEC_quick_push (int, earlyclobber_regclass, (int) class);
found_rc:
;
}
amp_p = false;
class = NO_REGS;
break;
case 'r':
class = GENERAL_REGS;
break;
default:
class = REG_CLASS_FROM_CONSTRAINT (c, p);
break;
}
if (c == '\0')
break;
p += CONSTRAINT_LEN (c, p);
}
}
return found;
}
static int
df_urec_mark_reg_use_for_earlyclobber (rtx *x, void *data)
{
enum reg_class pref_class, alt_class;
int i, regno;
struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
if (REG_P (*x) && REGNO (*x) >= FIRST_PSEUDO_REGISTER)
{
int rc;
regno = REGNO (*x);
if (bitmap_bit_p (bb_info->kill, regno)
|| bitmap_bit_p (bb_info->gen, regno))
return 0;
pref_class = reg_preferred_class (regno);
alt_class = reg_alternate_class (regno);
for (i = 0; VEC_iterate (int, earlyclobber_regclass, i, rc); i++)
{
if (reg_classes_intersect_p (rc, pref_class)
|| (rc != NO_REGS
&& reg_classes_intersect_p (rc, alt_class)))
{
bitmap_set_bit (bb_info->earlyclobber, regno);
break;
}
}
}
return 0;
}
static void
df_urec_mark_reg_use_for_earlyclobber_1 (rtx *x, void *data)
{
for_each_rtx (x, df_urec_mark_reg_use_for_earlyclobber, data);
}
static void
df_urec_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
{
struct df *df = dflow->df;
basic_block bb = BASIC_BLOCK (bb_index);
struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
rtx insn;
struct df_ref *def;
for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
{
unsigned int regno = DF_REF_REGNO (def);
bitmap_set_bit (bb_info->gen, regno);
}
FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
{
note_stores (PATTERN (insn), df_urec_mark_reg_change, bb_info);
if (df_urec_check_earlyclobber (insn))
{
struct df_urec_problem_data *problem_data
= (struct df_urec_problem_data *) dflow->problem_data;
problem_data->earlyclobbers_found = true;
note_uses (&PATTERN (insn),
df_urec_mark_reg_use_for_earlyclobber_1, bb_info);
}
}
}
for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
{
unsigned int regno = DF_REF_REGNO (def);
bitmap_set_bit (bb_info->gen, regno);
}
}
static void
df_urec_local_compute (struct dataflow *dflow,
bitmap all_blocks ATTRIBUTE_UNUSED,
bitmap rescan_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
#ifdef STACK_REGS
int i;
HARD_REG_SET zero, stack_hard_regs, used;
struct df_urec_problem_data *problem_data
= (struct df_urec_problem_data *) dflow->problem_data;
CLEAR_HARD_REG_SET (zero);
CLEAR_HARD_REG_SET (stack_hard_regs);
for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
SET_HARD_REG_BIT (stack_hard_regs, i);
problem_data->stack_regs = BITMAP_ALLOC (NULL);
for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
{
COPY_HARD_REG_SET (used, reg_class_contents[reg_preferred_class (i)]);
IOR_HARD_REG_SET (used, reg_class_contents[reg_alternate_class (i)]);
AND_HARD_REG_SET (used, stack_hard_regs);
GO_IF_HARD_REG_EQUAL (used, zero, skip);
bitmap_set_bit (problem_data->stack_regs, i);
skip:
;
}
#endif
earlyclobber_regclass = VEC_alloc (int, heap, N_REG_CLASSES);
EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi)
{
df_urec_bb_local_compute (dflow, bb_index);
}
VEC_free (int, heap, earlyclobber_regclass);
}
static void
df_urec_init (struct dataflow *dflow, bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
bitmap_copy (bb_info->out, bb_info->gen);
bitmap_clear (bb_info->in);
}
}
static void
df_urec_local_finalize (struct dataflow *dflow, bitmap all_blocks)
{
struct df *df = dflow->df;
struct dataflow *lr_dflow = df->problems_by_index[DF_LR];
bitmap tmp = BITMAP_ALLOC (NULL);
bitmap_iterator bi;
unsigned int bb_index;
struct df_urec_problem_data *problem_data
= (struct df_urec_problem_data *) dflow->problem_data;
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (lr_dflow, bb_index);
if (bb_index != ENTRY_BLOCK && bb_index != EXIT_BLOCK)
{
if (problem_data->earlyclobbers_found)
bitmap_ior_into (bb_info->in, bb_info->earlyclobber);
#ifdef STACK_REGS
bitmap_ior_into (bb_info->in, problem_data->stack_regs);
bitmap_ior_into (bb_info->out, problem_data->stack_regs);
#endif
}
bitmap_and_into (bb_info->in, bb_lr_info->in);
bitmap_and_into (bb_info->out, bb_lr_info->out);
#if 1
bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in,
bb_info->kill);
bitmap_and_into (bb_info->out, tmp);
#endif
}
#ifdef STACK_REGS
BITMAP_FREE (problem_data->stack_regs);
#endif
BITMAP_FREE (tmp);
}
static void
df_urec_confluence_n (struct dataflow *dflow, edge e)
{
bitmap op1 = df_urec_get_bb_info (dflow, e->dest->index)->in;
bitmap op2 = df_urec_get_bb_info (dflow, e->src->index)->out;
if (e->flags & EDGE_FAKE)
return;
bitmap_ior_into (op1, op2);
}
static bool
df_urec_transfer_function (struct dataflow *dflow, int bb_index)
{
struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
bitmap in = bb_info->in;
bitmap out = bb_info->out;
bitmap gen = bb_info->gen;
bitmap kill = bb_info->kill;
return bitmap_ior_and_compl (out, gen, in, kill);
}
static void
df_urec_free (struct dataflow *dflow)
{
if (dflow->block_info)
{
unsigned int i;
for (i = 0; i < dflow->block_info_size; i++)
{
struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, i);
if (bb_info)
{
BITMAP_FREE (bb_info->gen);
BITMAP_FREE (bb_info->kill);
BITMAP_FREE (bb_info->in);
BITMAP_FREE (bb_info->out);
BITMAP_FREE (bb_info->earlyclobber);
}
}
free_alloc_pool (dflow->block_pool);
dflow->block_info_size = 0;
free (dflow->block_info);
free (dflow->problem_data);
}
free (dflow);
}
static void
df_urec_dump (struct dataflow *dflow, FILE *file)
{
basic_block bb;
if (!dflow->block_info)
return;
fprintf (file, "Undefined regs:\n");
FOR_ALL_BB (bb)
{
struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb->index);
df_print_bb_index (bb, file);
if (!bb_info->in)
continue;
fprintf (file, " in \t");
dump_bitmap (file, bb_info->in);
fprintf (file, " gen \t");
dump_bitmap (file, bb_info->gen);
fprintf (file, " kill\t");
dump_bitmap (file, bb_info->kill);
fprintf (file, " ec\t");
dump_bitmap (file, bb_info->earlyclobber);
fprintf (file, " out \t");
dump_bitmap (file, bb_info->out);
}
}
static struct df_problem problem_UREC =
{
DF_UREC,
DF_FORWARD,
df_urec_alloc,
NULL,
df_urec_free_bb_info,
df_urec_local_compute,
df_urec_init,
df_iterative_dataflow,
NULL,
df_urec_confluence_n,
df_urec_transfer_function,
df_urec_local_finalize,
df_urec_free,
df_urec_dump,
df_lr_add_problem,
0
};
struct dataflow *
df_urec_add_problem (struct df *df, int flags)
{
return df_add_problem (df, &problem_UREC, flags);
}
static void
df_chain_alloc (struct dataflow *dflow,
bitmap blocks_to_rescan ATTRIBUTE_UNUSED,
bitmap all_blocks ATTRIBUTE_UNUSED)
{
struct df *df = dflow->df;
unsigned int i;
if (dflow->block_pool)
free_alloc_pool (dflow->block_pool);
dflow->block_pool = create_alloc_pool ("df_chain_chain_block pool",
sizeof (struct df_link), 100);
if (dflow->flags & DF_DU_CHAIN)
{
if (!df->def_info.refs_organized)
df_reorganize_refs (&df->def_info);
for (i = 0; i < DF_DEFS_SIZE (df); i++)
{
struct df_ref *ref = df->def_info.refs[i];
DF_REF_CHAIN (ref) = NULL;
}
}
if (dflow->flags & DF_UD_CHAIN)
{
if (!df->use_info.refs_organized)
df_reorganize_refs (&df->use_info);
for (i = 0; i < DF_USES_SIZE (df); i++)
{
struct df_ref *ref = df->use_info.refs[i];
DF_REF_CHAIN (ref) = NULL;
}
}
}
static void
df_chain_insn_reset (struct dataflow *dflow, rtx insn)
{
struct df *df = dflow->df;
unsigned int uid = INSN_UID (insn);
struct df_insn_info *insn_info = NULL;
struct df_ref *ref;
if (uid < df->insns_size)
insn_info = DF_INSN_UID_GET (df, uid);
if (insn_info)
{
if (dflow->flags & DF_DU_CHAIN)
{
ref = insn_info->defs;
while (ref)
{
ref->chain = NULL;
ref = ref->next_ref;
}
}
if (dflow->flags & DF_UD_CHAIN)
{
ref = insn_info->uses;
while (ref)
{
ref->chain = NULL;
ref = ref->next_ref;
}
}
}
}
static void
df_chain_bb_reset (struct dataflow *dflow, unsigned int bb_index)
{
struct df *df = dflow->df;
rtx insn;
basic_block bb = BASIC_BLOCK (bb_index);
if (!bb)
return;
FOR_BB_INSNS (bb, insn)
{
if (INSN_P (insn))
{
df_chain_insn_reset (dflow, insn);
}
}
if (dflow->flags & DF_DU_CHAIN)
{
struct df_ref *def;
def = df_get_artificial_defs (df, bb_index);
while (def)
{
def->chain = NULL;
def = def->next_ref;
}
}
if (dflow->flags & DF_UD_CHAIN)
{
struct df_ref *use;
use = df_get_artificial_uses (df, bb_index);
while (use)
{
use->chain = NULL;
use = use->next_ref;
}
}
}
static void
df_chain_reset (struct dataflow *dflow, bitmap blocks_to_clear)
{
bitmap_iterator bi;
unsigned int bb_index;
EXECUTE_IF_SET_IN_BITMAP (blocks_to_clear, 0, bb_index, bi)
{
df_chain_bb_reset (dflow, bb_index);
}
free_alloc_pool (dflow->block_pool);
dflow->block_pool = NULL;
}
static void
df_chain_create_bb_process_use (struct dataflow *dflow,
bitmap local_rd,
struct df_ref *use,
enum df_ref_flags top_flag)
{
struct df *df = dflow->df;
bitmap_iterator bi;
unsigned int def_index;
while (use)
{
unsigned int uregno = DF_REF_REGNO (use);
int count = DF_REG_DEF_GET (df, uregno)->n_refs;
if (count)
{
if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
{
unsigned int first_index = DF_REG_DEF_GET (df, uregno)->begin;
unsigned int last_index = first_index + count - 1;
EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
{
struct df_ref *def;
if (def_index > last_index)
break;
def = DF_DEFS_GET (df, def_index);
if (dflow->flags & DF_DU_CHAIN)
df_chain_create (dflow, def, use);
if (dflow->flags & DF_UD_CHAIN)
df_chain_create (dflow, use, def);
}
}
}
use = use->next_ref;
}
}
static void
df_chain_create_bb (struct dataflow *dflow,
struct dataflow *rd_dflow,
unsigned int bb_index)
{
basic_block bb = BASIC_BLOCK (bb_index);
struct df_rd_bb_info *bb_info = df_rd_get_bb_info (rd_dflow, bb_index);
rtx insn;
bitmap cpy = BITMAP_ALLOC (NULL);
struct df *df = dflow->df;
struct df_ref *def;
bitmap_copy (cpy, bb_info->in);
#ifdef EH_USES
df_chain_create_bb_process_use (dflow, cpy,
df_get_artificial_uses (df, bb->index),
DF_REF_AT_TOP);
#endif
for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
{
unsigned int dregno = DF_REF_REGNO (def);
if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))
bitmap_clear_range (cpy,
DF_REG_DEF_GET (df, dregno)->begin,
DF_REG_DEF_GET (df, dregno)->n_refs);
bitmap_set_bit (cpy, DF_REF_ID (def));
}
FOR_BB_INSNS (bb, insn)
{
struct df_ref *def;
unsigned int uid = INSN_UID (insn);
if (!INSN_P (insn))
continue;
df_chain_create_bb_process_use (dflow, cpy,
DF_INSN_UID_USES (df, uid), 0);
for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref)
{
unsigned int dregno = DF_REF_REGNO (def);
if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))
bitmap_clear_range (cpy,
DF_REG_DEF_GET (df, dregno)->begin,
DF_REG_DEF_GET (df, dregno)->n_refs);
if (!(DF_REF_FLAGS (def)
& (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
bitmap_set_bit (cpy, DF_REF_ID (def));
}
}
df_chain_create_bb_process_use (dflow, cpy,
df_get_artificial_uses (df, bb->index), 0);
}
static void
df_chain_finalize (struct dataflow *dflow, bitmap all_blocks)
{
unsigned int bb_index;
bitmap_iterator bi;
struct df *df = dflow->df;
struct dataflow *rd_dflow = df->problems_by_index [DF_RD];
EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
{
df_chain_create_bb (dflow, rd_dflow, bb_index);
}
}
static void
df_chain_free (struct dataflow *dflow)
{
free_alloc_pool (dflow->block_pool);
free (dflow);
}
static void
df_chains_dump (struct dataflow *dflow, FILE *file)
{
struct df *df = dflow->df;
unsigned int j;
if (dflow->flags & DF_DU_CHAIN)
{
fprintf (file, "Def-use chains:\n");
for (j = 0; j < df->def_info.bitmap_size; j++)
{
struct df_ref *def = DF_DEFS_GET (df, j);
if (def)
{
fprintf (file, "d%d bb %d luid %d insn %d reg %d ",
j, DF_REF_BBNO (def),
DF_REF_INSN (def) ?
DF_INSN_LUID (df, DF_REF_INSN (def)):
-1,
DF_REF_INSN (def) ? DF_REF_INSN_UID (def) : -1,
DF_REF_REGNO (def));
if (def->flags & DF_REF_READ_WRITE)
fprintf (file, "read/write ");
df_chain_dump (DF_REF_CHAIN (def), file);
fprintf (file, "\n");
}
}
}
if (dflow->flags & DF_UD_CHAIN)
{
fprintf (file, "Use-def chains:\n");
for (j = 0; j < df->use_info.bitmap_size; j++)
{
struct df_ref *use = DF_USES_GET (df, j);
if (use)
{
fprintf (file, "u%d bb %d luid %d insn %d reg %d ",
j, DF_REF_BBNO (use),
DF_REF_INSN (use) ?
DF_INSN_LUID (df, DF_REF_INSN (use))
: -1,
DF_REF_INSN (DF_USES_GET (df, j)) ?
DF_REF_INSN_UID (DF_USES_GET (df,j))
: -1,
DF_REF_REGNO (use));
if (use->flags & DF_REF_READ_WRITE)
fprintf (file, "read/write ");
if (use->flags & DF_REF_STRIPPED)
fprintf (file, "stripped ");
if (use->flags & DF_REF_IN_NOTE)
fprintf (file, "note ");
df_chain_dump (DF_REF_CHAIN (use), file);
fprintf (file, "\n");
}
}
}
}
static struct df_problem problem_CHAIN =
{
DF_CHAIN,
DF_NONE,
df_chain_alloc,
df_chain_reset,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
df_chain_finalize,
df_chain_free,
df_chains_dump,
df_rd_add_problem,
0
};
struct dataflow *
df_chain_add_problem (struct df *df, int flags)
{
return df_add_problem (df, &problem_CHAIN, flags);
}
#ifdef REG_DEAD_DEBUGGING
static void
print_note (char *prefix, rtx insn, rtx note)
{
fprintf (stderr, "%s %d ", prefix, INSN_UID (insn));
print_rtl (stderr, note);
fprintf (stderr, "\n");
}
#endif
static void
df_ri_alloc (struct dataflow *dflow,
bitmap blocks_to_rescan ATTRIBUTE_UNUSED,
bitmap all_blocks ATTRIBUTE_UNUSED)
{
int i;
struct df *df = dflow->df;
if (dflow->flags & DF_RI_LIFE)
{
max_regno = max_reg_num ();
allocate_reg_info (max_regno, FALSE, FALSE);
for (i = 0; i < max_regno; i++)
{
REG_N_SETS (i) = DF_REG_DEF_COUNT (df, i);
REG_N_REFS (i) = DF_REG_USE_COUNT (df, i) + REG_N_SETS (i);
REG_N_DEATHS (i) = 0;
REG_N_CALLS_CROSSED (i) = 0;
REG_N_THROWING_CALLS_CROSSED (i) = 0;
REG_LIVE_LENGTH (i) = 0;
REG_FREQ (i) = 0;
REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
}
}
}
static inline bool
df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
{
#ifdef STACK_REGS
return (regstack_completed
&& IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG));
#else
return false;
#endif
}
static void
df_kill_notes (rtx insn, int flags)
{
rtx *pprev = ®_NOTES (insn);
rtx link = *pprev;
while (link)
{
switch (REG_NOTE_KIND (link))
{
case REG_DEAD:
if (flags & DF_RI_LIFE)
if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
REG_N_DEATHS (REGNO (XEXP (link, 0)))++;
case REG_UNUSED:
if (!df_ignore_stack_reg (REGNO (XEXP (link, 0))))
{
rtx next = XEXP (link, 1);
#ifdef REG_DEAD_DEBUGGING
print_note ("deleting: ", insn, link);
#endif
free_EXPR_LIST_node (link);
*pprev = link = next;
}
break;
default:
pprev = &XEXP (link, 1);
link = *pprev;
break;
}
}
}
static void
df_set_unused_notes_for_mw (rtx insn, struct df_mw_hardreg *mws,
bitmap live, bitmap do_not_gen,
bitmap artificial_uses, int flags)
{
bool all_dead = true;
struct df_link *regs = mws->regs;
unsigned int regno = DF_REF_REGNO (regs->ref);
#ifdef REG_DEAD_DEBUGGING
fprintf (stderr, "mw unused looking at %d\n", DF_REF_REGNO (regs->ref));
df_ref_debug (regs->ref, stderr);
#endif
while (regs)
{
unsigned int regno = DF_REF_REGNO (regs->ref);
if ((bitmap_bit_p (live, regno))
|| bitmap_bit_p (artificial_uses, regno))
{
all_dead = false;
break;
}
regs = regs->next;
}
if (all_dead)
{
struct df_link *regs = mws->regs;
rtx note = alloc_EXPR_LIST (REG_UNUSED, *DF_REF_LOC (regs->ref),
REG_NOTES (insn));
REG_NOTES (insn) = note;
#ifdef REG_DEAD_DEBUGGING
print_note ("adding 1: ", insn, note);
#endif
bitmap_set_bit (do_not_gen, regno);
if (flags & DF_RI_LIFE)
{
REG_N_DEATHS (regno) ++;
REG_LIVE_LENGTH (regno)++;
}
}
else
{
struct df_link *regs = mws->regs;
while (regs)
{
struct df_ref *ref = regs->ref;
regno = DF_REF_REGNO (ref);
if ((!bitmap_bit_p (live, regno))
&& (!bitmap_bit_p (artificial_uses, regno)))
{
rtx note = alloc_EXPR_LIST (REG_UNUSED, regno_reg_rtx[regno],
REG_NOTES (insn));
REG_NOTES (insn) = note;
#ifdef REG_DEAD_DEBUGGING
print_note ("adding 2: ", insn, note);
#endif
}
bitmap_set_bit (do_not_gen, regno);
regs = regs->next;
}
}
}
static void
df_set_dead_notes_for_mw (rtx insn, struct df_mw_hardreg *mws,
bitmap live, bitmap do_not_gen,
bitmap artificial_uses, int flags)
{
bool all_dead = true;
struct df_link *regs = mws->regs;
unsigned int regno = DF_REF_REGNO (regs->ref);
#ifdef REG_DEAD_DEBUGGING
fprintf (stderr, "mw looking at %d\n", DF_REF_REGNO (regs->ref));
df_ref_debug (regs->ref, stderr);
#endif
while (regs)
{
unsigned int regno = DF_REF_REGNO (regs->ref);
if ((bitmap_bit_p (live, regno))
|| bitmap_bit_p (artificial_uses, regno))
{
all_dead = false;
break;
}
regs = regs->next;
}
if (all_dead)
{
if (!bitmap_bit_p (do_not_gen, regno))
{
struct df_link *regs = mws->regs;
rtx note = alloc_EXPR_LIST (REG_DEAD, *DF_REF_LOC (regs->ref),
REG_NOTES (insn));
REG_NOTES (insn) = note;
#ifdef REG_DEAD_DEBUGGING
print_note ("adding 1: ", insn, note);
#endif
if (flags & DF_RI_LIFE)
{
struct df_link *regs = mws->regs;
while (regs)
{
struct df_ref *ref = regs->ref;
regno = DF_REF_REGNO (ref);
REG_N_DEATHS (regno)++;
regs = regs->next;
}
}
}
}
else
{
struct df_link *regs = mws->regs;
while (regs)
{
struct df_ref *ref = regs->ref;
regno = DF_REF_REGNO (ref);
if ((!bitmap_bit_p (live, regno))
&& (!bitmap_bit_p (artificial_uses, regno))
&& (!bitmap_bit_p (do_not_gen, regno)))
{
rtx note = alloc_EXPR_LIST (REG_DEAD, regno_reg_rtx[regno],
REG_NOTES (insn));
REG_NOTES (insn) = note;
if (flags & DF_RI_LIFE)
REG_N_DEATHS (regno)++;
#ifdef REG_DEAD_DEBUGGING
print_note ("adding 2: ", insn, note);
#endif
}
regs = regs->next;
}
}
}
static void
df_create_unused_note (basic_block bb, rtx insn, struct df_ref *def,
bitmap live, bitmap do_not_gen, bitmap artificial_uses,
bitmap local_live, bitmap local_processed,
int flags, int luid)
{
unsigned int dregno = DF_REF_REGNO (def);
#ifdef REG_DEAD_DEBUGGING
fprintf (stderr, " regular looking at def ");
df_ref_debug (def, stderr);
#endif
if (bitmap_bit_p (live, dregno))
{
if (flags & DF_RI_LIFE)
{
if (bitmap_bit_p (local_processed, dregno))
{
if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))
bitmap_clear_bit (local_live, dregno);
}
else
{
bitmap_set_bit (local_processed, dregno);
REG_LIVE_LENGTH (dregno) += luid;
}
}
}
else if ((!(DF_REF_FLAGS (def) & DF_REF_MW_HARDREG))
&& (!bitmap_bit_p (artificial_uses, dregno))
&& (!df_ignore_stack_reg (dregno)))
{
rtx reg = GET_CODE (*DF_REF_LOC (def)) == SUBREG ?
SUBREG_REG (*DF_REF_LOC (def)) : *DF_REF_LOC (def);
rtx note = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
REG_NOTES (insn) = note;
#ifdef REG_DEAD_DEBUGGING
print_note ("adding 3: ", insn, note);
#endif
if (flags & DF_RI_LIFE)
{
REG_N_DEATHS (dregno) ++;
REG_LIVE_LENGTH (dregno)++;
}
}
if ((flags & DF_RI_LIFE) && (dregno >= FIRST_PSEUDO_REGISTER))
{
REG_FREQ (dregno) += REG_FREQ_FROM_BB (bb);
if (REG_BASIC_BLOCK (dregno) == REG_BLOCK_UNKNOWN)
REG_BASIC_BLOCK (dregno) = bb->index;
else if (REG_BASIC_BLOCK (dregno) != bb->index)
REG_BASIC_BLOCK (dregno) = REG_BLOCK_GLOBAL;
}
if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER + DF_REF_MAY_CLOBBER)))
bitmap_set_bit (do_not_gen, dregno);
if (!(DF_REF_FLAGS (def) & DF_REF_PARTIAL))
bitmap_clear_bit (live, dregno);
}
static void
df_ri_bb_compute (struct dataflow *dflow, unsigned int bb_index,
bitmap live, bitmap do_not_gen, bitmap artificial_uses,
bitmap local_live, bitmap local_processed, bitmap setjumps_crossed)
{
struct df *df = dflow->df;
basic_block bb = BASIC_BLOCK (bb_index);
rtx insn;
struct df_ref *def;
struct df_ref *use;
int luid = 0;
bitmap_copy (live, df_get_live_out (df, bb));
bitmap_clear (artificial_uses);
if (dflow->flags & DF_RI_LIFE)
{
bitmap_iterator bi;
unsigned int regno;
EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
REG_BASIC_BLOCK (regno) = REG_BLOCK_GLOBAL;
}
for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
bitmap_clear_bit (live, DF_REF_REGNO (def));
for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref)
if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
{
unsigned int regno = DF_REF_REGNO (use);
bitmap_set_bit (live, regno);
bitmap_set_bit (artificial_uses, regno);
}
FOR_BB_INSNS_REVERSE (bb, insn)
{
unsigned int uid = INSN_UID (insn);
unsigned int regno;
bitmap_iterator bi;
struct df_mw_hardreg *mws;
if (!INSN_P (insn))
continue;
if (dflow->flags & DF_RI_LIFE)
{
bitmap_iterator bi;
unsigned int regno;
EXECUTE_IF_SET_IN_BITMAP (local_live, 0, regno, bi)
{
REG_LIVE_LENGTH (regno)++;
}
luid++;
}
bitmap_clear (do_not_gen);
df_kill_notes (insn, dflow->flags);
if (CALL_P (insn))
{
if (dflow->flags & DF_RI_LIFE)
{
bool can_throw = can_throw_internal (insn);
bool set_jump = (find_reg_note (insn, REG_SETJMP, NULL) != NULL);
EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
{
REG_N_CALLS_CROSSED (regno)++;
if (can_throw)
REG_N_THROWING_CALLS_CROSSED (regno)++;
if (set_jump && regno >= FIRST_PSEUDO_REGISTER)
bitmap_set_bit (setjumps_crossed, regno);
}
}
for (mws = DF_INSN_UID_MWS (df, uid); mws; mws = mws->next)
{
if ((mws->type == DF_REF_REG_DEF)
&& !df_ignore_stack_reg (REGNO (mws->mw_reg)))
df_set_unused_notes_for_mw (insn, mws, live, do_not_gen,
artificial_uses, dflow->flags);
}
for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref)
if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
df_create_unused_note (bb, insn, def, live, do_not_gen,
artificial_uses, local_live,
local_processed, dflow->flags, luid);
}
else
{
for (mws = DF_INSN_UID_MWS (df, uid); mws; mws = mws->next)
{
if (mws->type == DF_REF_REG_DEF)
df_set_unused_notes_for_mw (insn, mws, live, do_not_gen,
artificial_uses, dflow->flags);
}
for (def = DF_INSN_UID_DEFS (df, uid); def; def = def->next_ref)
df_create_unused_note (bb, insn, def, live, do_not_gen,
artificial_uses, local_live,
local_processed, dflow->flags, luid);
}
for (mws = DF_INSN_UID_MWS (df, uid); mws; mws = mws->next)
{
if ((mws->type != DF_REF_REG_DEF)
&& !df_ignore_stack_reg (REGNO (mws->mw_reg)))
df_set_dead_notes_for_mw (insn, mws, live, do_not_gen,
artificial_uses, dflow->flags);
}
for (use = DF_INSN_UID_USES (df, uid); use; use = use->next_ref)
{
unsigned int uregno = DF_REF_REGNO (use);
if ((dflow->flags & DF_RI_LIFE) && (uregno >= FIRST_PSEUDO_REGISTER))
{
REG_FREQ (uregno) += REG_FREQ_FROM_BB (bb);
if (REG_BASIC_BLOCK (uregno) == REG_BLOCK_UNKNOWN)
REG_BASIC_BLOCK (uregno) = bb->index;
else if (REG_BASIC_BLOCK (uregno) != bb->index)
REG_BASIC_BLOCK (uregno) = REG_BLOCK_GLOBAL;
}
#ifdef REG_DEAD_DEBUGGING
fprintf (stderr, " regular looking at use ");
df_ref_debug (use, stderr);
#endif
if (!bitmap_bit_p (live, uregno))
{
if ( (!(DF_REF_FLAGS (use) & DF_REF_MW_HARDREG))
&& (!bitmap_bit_p (do_not_gen, uregno))
&& (!bitmap_bit_p (artificial_uses, uregno))
&& (!(DF_REF_FLAGS (use) & DF_REF_READ_WRITE))
&& (!df_ignore_stack_reg (uregno)))
{
rtx reg = GET_CODE (*DF_REF_LOC (use)) == SUBREG ?
SUBREG_REG (*DF_REF_LOC (use)) : *DF_REF_LOC (use);
rtx note = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn));
REG_NOTES (insn) = note;
if (dflow->flags & DF_RI_LIFE)
REG_N_DEATHS (uregno)++;
#ifdef REG_DEAD_DEBUGGING
print_note ("adding 4: ", insn, note);
#endif
}
bitmap_set_bit (live, uregno);
if (dflow->flags & DF_RI_LIFE)
{
REG_LIVE_LENGTH (uregno) ++;
bitmap_set_bit (local_live, uregno);
bitmap_set_bit (local_processed, uregno);
}
}
}
}
if (dflow->flags & DF_RI_LIFE)
{
bitmap_iterator bi;
unsigned int regno;
bitmap_and_compl_into (live, local_processed);
EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
{
REG_LIVE_LENGTH (regno) += luid;
}
bitmap_clear (local_processed);
bitmap_clear (local_live);
}
}
static void
df_ri_compute (struct dataflow *dflow, bitmap all_blocks ATTRIBUTE_UNUSED,
bitmap blocks_to_scan)
{
unsigned int bb_index;
bitmap_iterator bi;
bitmap live = BITMAP_ALLOC (NULL);
bitmap do_not_gen = BITMAP_ALLOC (NULL);
bitmap artificial_uses = BITMAP_ALLOC (NULL);
bitmap local_live = NULL;
bitmap local_processed = NULL;
bitmap setjumps_crossed = NULL;
if (dflow->flags & DF_RI_LIFE)
{
local_live = BITMAP_ALLOC (NULL);
local_processed = BITMAP_ALLOC (NULL);
setjumps_crossed = BITMAP_ALLOC (NULL);
}
#ifdef REG_DEAD_DEBUGGING
df_lr_dump (dflow->df->problems_by_index [DF_LR], stderr);
print_rtl_with_bb (stderr, get_insns());
#endif
EXECUTE_IF_SET_IN_BITMAP (blocks_to_scan, 0, bb_index, bi)
{
df_ri_bb_compute (dflow, bb_index, live, do_not_gen, artificial_uses,
local_live, local_processed, setjumps_crossed);
}
BITMAP_FREE (live);
BITMAP_FREE (do_not_gen);
BITMAP_FREE (artificial_uses);
if (dflow->flags & DF_RI_LIFE)
{
bitmap_iterator bi;
unsigned int regno;
EXECUTE_IF_SET_IN_BITMAP (setjumps_crossed, 0, regno, bi)
{
REG_BASIC_BLOCK (regno) = REG_BLOCK_UNKNOWN;
REG_LIVE_LENGTH (regno) = -1;
}
BITMAP_FREE (local_live);
BITMAP_FREE (local_processed);
BITMAP_FREE (setjumps_crossed);
}
}
static void
df_ri_free (struct dataflow *dflow)
{
free (dflow->problem_data);
free (dflow);
}
static void
df_ri_dump (struct dataflow *dflow, FILE *file)
{
print_rtl_with_bb (file, get_insns ());
if (dflow->flags & DF_RI_LIFE)
{
fprintf (file, "Register info:\n");
dump_flow_info (file, -1);
}
}
static struct df_problem problem_RI =
{
DF_RI,
DF_NONE,
df_ri_alloc,
NULL,
NULL,
df_ri_compute,
NULL,
NULL,
NULL,
NULL,
NULL,
NULL,
df_ri_free,
df_ri_dump,
df_lr_add_problem,
0
};
struct dataflow *
df_ri_add_problem (struct df *df, int flags)
{
return df_add_problem (df, &problem_RI, flags);
}