#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "regs.h"
#include "hard-reg-set.h"
#include "flags.h"
#include "real.h"
#include "insn-config.h"
#include "recog.h"
#include "basic-block.h"
#include "output.h"
#include "tm_p.h"
#include "function.h"
#include "insn-attr.h"
static void compute_antinout_edge (sbitmap *, sbitmap *, sbitmap *, sbitmap *);
static void compute_earliest (struct edge_list *, int, sbitmap *, sbitmap *,
sbitmap *, sbitmap *, sbitmap *);
static void compute_laterin (struct edge_list *, sbitmap *, sbitmap *,
sbitmap *, sbitmap *);
static void compute_insert_delete (struct edge_list *edge_list, sbitmap *,
sbitmap *, sbitmap *, sbitmap *, sbitmap *);
static void compute_farthest (struct edge_list *, int, sbitmap *, sbitmap *,
sbitmap*, sbitmap *, sbitmap *);
static void compute_nearerout (struct edge_list *, sbitmap *, sbitmap *,
sbitmap *, sbitmap *);
static void compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *,
sbitmap *, sbitmap *, sbitmap *,
sbitmap *);
static void
compute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin,
sbitmap *antout)
{
basic_block bb;
edge e;
basic_block *worklist, *qin, *qout, *qend;
unsigned int qlen;
edge_iterator ei;
qin = qout = worklist = XNEWVEC (basic_block, n_basic_blocks);
sbitmap_vector_ones (antin, last_basic_block);
FOR_EACH_BB_REVERSE (bb)
{
*qin++ = bb;
bb->aux = bb;
}
qin = worklist;
qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
e->src->aux = EXIT_BLOCK_PTR;
while (qlen)
{
bb = *qout++;
qlen--;
if (qout >= qend)
qout = worklist;
if (bb->aux == EXIT_BLOCK_PTR)
sbitmap_zero (antout[bb->index]);
else
{
bb->aux = NULL;
sbitmap_intersection_of_succs (antout[bb->index], antin, bb->index);
}
if (sbitmap_a_or_b_and_c_cg (antin[bb->index], antloc[bb->index],
transp[bb->index], antout[bb->index]))
FOR_EACH_EDGE (e, ei, bb->preds)
if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
{
*qin++ = e->src;
e->src->aux = e;
qlen++;
if (qin >= qend)
qin = worklist;
}
}
clear_aux_for_edges ();
clear_aux_for_blocks ();
free (worklist);
}
static void
compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin,
sbitmap *antout, sbitmap *avout, sbitmap *kill,
sbitmap *earliest)
{
sbitmap difference, temp_bitmap;
int x, num_edges;
basic_block pred, succ;
num_edges = NUM_EDGES (edge_list);
difference = sbitmap_alloc (n_exprs);
temp_bitmap = sbitmap_alloc (n_exprs);
for (x = 0; x < num_edges; x++)
{
pred = INDEX_EDGE_PRED_BB (edge_list, x);
succ = INDEX_EDGE_SUCC_BB (edge_list, x);
if (pred == ENTRY_BLOCK_PTR)
sbitmap_copy (earliest[x], antin[succ->index]);
else
{
if (succ == EXIT_BLOCK_PTR)
sbitmap_zero (earliest[x]);
else
{
sbitmap_difference (difference, antin[succ->index],
avout[pred->index]);
sbitmap_not (temp_bitmap, antout[pred->index]);
sbitmap_a_and_b_or_c (earliest[x], difference,
kill[pred->index], temp_bitmap);
}
}
}
sbitmap_free (temp_bitmap);
sbitmap_free (difference);
}
static void
compute_laterin (struct edge_list *edge_list, sbitmap *earliest,
sbitmap *antloc, sbitmap *later, sbitmap *laterin)
{
int num_edges, i;
edge e;
basic_block *worklist, *qin, *qout, *qend, bb;
unsigned int qlen;
edge_iterator ei;
num_edges = NUM_EDGES (edge_list);
qin = qout = worklist
= XNEWVEC (basic_block, n_basic_blocks);
for (i = 0; i < num_edges; i++)
INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
sbitmap_vector_ones (later, num_edges);
FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
sbitmap_copy (later[(size_t) e->aux], earliest[(size_t) e->aux]);
FOR_EACH_BB (bb)
{
*qin++ = bb;
bb->aux = bb;
}
qin = worklist;
qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
while (qlen)
{
bb = *qout++;
bb->aux = NULL;
qlen--;
if (qout >= qend)
qout = worklist;
sbitmap_ones (laterin[bb->index]);
FOR_EACH_EDGE (e, ei, bb->preds)
sbitmap_a_and_b (laterin[bb->index], laterin[bb->index],
later[(size_t)e->aux]);
FOR_EACH_EDGE (e, ei, bb->succs)
if (sbitmap_union_of_diff_cg (later[(size_t) e->aux],
earliest[(size_t) e->aux],
laterin[e->src->index],
antloc[e->src->index])
&& e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0)
{
*qin++ = e->dest;
e->dest->aux = e;
qlen++;
if (qin >= qend)
qin = worklist;
}
}
sbitmap_ones (laterin[last_basic_block]);
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
sbitmap_a_and_b (laterin[last_basic_block],
laterin[last_basic_block],
later[(size_t) e->aux]);
clear_aux_for_edges ();
free (worklist);
}
static void
compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc,
sbitmap *later, sbitmap *laterin, sbitmap *insert,
sbitmap *delete)
{
int x;
basic_block bb;
FOR_EACH_BB (bb)
sbitmap_difference (delete[bb->index], antloc[bb->index],
laterin[bb->index]);
for (x = 0; x < NUM_EDGES (edge_list); x++)
{
basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
if (b == EXIT_BLOCK_PTR)
sbitmap_difference (insert[x], later[x], laterin[last_basic_block]);
else
sbitmap_difference (insert[x], later[x], laterin[b->index]);
}
}
struct edge_list *
pre_edge_lcm (int n_exprs, sbitmap *transp,
sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
sbitmap **insert, sbitmap **delete)
{
sbitmap *antin, *antout, *earliest;
sbitmap *avin, *avout;
sbitmap *later, *laterin;
struct edge_list *edge_list;
int num_edges;
edge_list = create_edge_list ();
num_edges = NUM_EDGES (edge_list);
#ifdef LCM_DEBUG_INFO
if (dump_file)
{
fprintf (dump_file, "Edge List:\n");
verify_edge_list (dump_file, edge_list);
print_edge_list (dump_file, edge_list);
dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block);
dump_sbitmap_vector (dump_file, "antloc", "", antloc, last_basic_block);
dump_sbitmap_vector (dump_file, "avloc", "", avloc, last_basic_block);
dump_sbitmap_vector (dump_file, "kill", "", kill, last_basic_block);
}
#endif
avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
compute_available (avloc, kill, avout, avin);
sbitmap_vector_free (avin);
antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
compute_antinout_edge (antloc, transp, antin, antout);
#ifdef LCM_DEBUG_INFO
if (dump_file)
{
dump_sbitmap_vector (dump_file, "antin", "", antin, last_basic_block);
dump_sbitmap_vector (dump_file, "antout", "", antout, last_basic_block);
}
#endif
earliest = sbitmap_vector_alloc (num_edges, n_exprs);
compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
#ifdef LCM_DEBUG_INFO
if (dump_file)
dump_sbitmap_vector (dump_file, "earliest", "", earliest, num_edges);
#endif
sbitmap_vector_free (antout);
sbitmap_vector_free (antin);
sbitmap_vector_free (avout);
later = sbitmap_vector_alloc (num_edges, n_exprs);
laterin = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
compute_laterin (edge_list, earliest, antloc, later, laterin);
#ifdef LCM_DEBUG_INFO
if (dump_file)
{
dump_sbitmap_vector (dump_file, "laterin", "", laterin, last_basic_block + 1);
dump_sbitmap_vector (dump_file, "later", "", later, num_edges);
}
#endif
sbitmap_vector_free (earliest);
*insert = sbitmap_vector_alloc (num_edges, n_exprs);
*delete = sbitmap_vector_alloc (last_basic_block, n_exprs);
compute_insert_delete (edge_list, antloc, later, laterin, *insert, *delete);
sbitmap_vector_free (laterin);
sbitmap_vector_free (later);
#ifdef LCM_DEBUG_INFO
if (dump_file)
{
dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
dump_sbitmap_vector (dump_file, "pre_delete_map", "", *delete,
last_basic_block);
}
#endif
return edge_list;
}
void
compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
sbitmap *avin)
{
edge e;
basic_block *worklist, *qin, *qout, *qend, bb;
unsigned int qlen;
edge_iterator ei;
qin = qout = worklist =
XNEWVEC (basic_block, n_basic_blocks - NUM_FIXED_BLOCKS);
sbitmap_vector_ones (avout, last_basic_block);
FOR_EACH_BB (bb)
{
*qin++ = bb;
bb->aux = bb;
}
qin = worklist;
qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
e->dest->aux = ENTRY_BLOCK_PTR;
while (qlen)
{
bb = *qout++;
qlen--;
if (qout >= qend)
qout = worklist;
if (bb->aux == ENTRY_BLOCK_PTR)
sbitmap_zero (avin[bb->index]);
else
{
bb->aux = NULL;
sbitmap_intersection_of_preds (avin[bb->index], avout, bb->index);
}
if (sbitmap_union_of_diff_cg (avout[bb->index], avloc[bb->index],
avin[bb->index], kill[bb->index]))
FOR_EACH_EDGE (e, ei, bb->succs)
if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
{
*qin++ = e->dest;
e->dest->aux = e;
qlen++;
if (qin >= qend)
qin = worklist;
}
}
clear_aux_for_edges ();
clear_aux_for_blocks ();
free (worklist);
}
static void
compute_farthest (struct edge_list *edge_list, int n_exprs,
sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin,
sbitmap *kill, sbitmap *farthest)
{
sbitmap difference, temp_bitmap;
int x, num_edges;
basic_block pred, succ;
num_edges = NUM_EDGES (edge_list);
difference = sbitmap_alloc (n_exprs);
temp_bitmap = sbitmap_alloc (n_exprs);
for (x = 0; x < num_edges; x++)
{
pred = INDEX_EDGE_PRED_BB (edge_list, x);
succ = INDEX_EDGE_SUCC_BB (edge_list, x);
if (succ == EXIT_BLOCK_PTR)
sbitmap_copy (farthest[x], st_avout[pred->index]);
else
{
if (pred == ENTRY_BLOCK_PTR)
sbitmap_zero (farthest[x]);
else
{
sbitmap_difference (difference, st_avout[pred->index],
st_antin[succ->index]);
sbitmap_not (temp_bitmap, st_avin[succ->index]);
sbitmap_a_and_b_or_c (farthest[x], difference,
kill[succ->index], temp_bitmap);
}
}
}
sbitmap_free (temp_bitmap);
sbitmap_free (difference);
}
static void
compute_nearerout (struct edge_list *edge_list, sbitmap *farthest,
sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout)
{
int num_edges, i;
edge e;
basic_block *worklist, *tos, bb;
edge_iterator ei;
num_edges = NUM_EDGES (edge_list);
tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1);
for (i = 0; i < num_edges; i++)
INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
sbitmap_vector_ones (nearer, num_edges);
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
sbitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]);
FOR_EACH_BB (bb)
{
*tos++ = bb;
bb->aux = bb;
}
while (tos != worklist)
{
bb = *--tos;
bb->aux = NULL;
sbitmap_ones (nearerout[bb->index]);
FOR_EACH_EDGE (e, ei, bb->succs)
sbitmap_a_and_b (nearerout[bb->index], nearerout[bb->index],
nearer[(size_t) e->aux]);
FOR_EACH_EDGE (e, ei, bb->preds)
if (sbitmap_union_of_diff_cg (nearer[(size_t) e->aux],
farthest[(size_t) e->aux],
nearerout[e->dest->index],
st_avloc[e->dest->index])
&& e->src != ENTRY_BLOCK_PTR && e->src->aux == 0)
{
*tos++ = e->src;
e->src->aux = e;
}
}
sbitmap_ones (nearerout[last_basic_block]);
FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
sbitmap_a_and_b (nearerout[last_basic_block],
nearerout[last_basic_block],
nearer[(size_t) e->aux]);
clear_aux_for_edges ();
free (tos);
}
static void
compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc,
sbitmap *nearer, sbitmap *nearerout,
sbitmap *insert, sbitmap *delete)
{
int x;
basic_block bb;
FOR_EACH_BB (bb)
sbitmap_difference (delete[bb->index], st_avloc[bb->index],
nearerout[bb->index]);
for (x = 0; x < NUM_EDGES (edge_list); x++)
{
basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
if (b == ENTRY_BLOCK_PTR)
sbitmap_difference (insert[x], nearer[x], nearerout[last_basic_block]);
else
sbitmap_difference (insert[x], nearer[x], nearerout[b->index]);
}
}
struct edge_list *
pre_edge_rev_lcm (int n_exprs, sbitmap *transp,
sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill,
sbitmap **insert, sbitmap **delete)
{
sbitmap *st_antin, *st_antout;
sbitmap *st_avout, *st_avin, *farthest;
sbitmap *nearer, *nearerout;
struct edge_list *edge_list;
int num_edges;
edge_list = create_edge_list ();
num_edges = NUM_EDGES (edge_list);
st_antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
st_antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
sbitmap_vector_zero (st_antin, last_basic_block);
sbitmap_vector_zero (st_antout, last_basic_block);
compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
st_avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
st_avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
compute_available (st_avloc, kill, st_avout, st_avin);
#ifdef LCM_DEBUG_INFO
if (dump_file)
{
fprintf (dump_file, "Edge List:\n");
verify_edge_list (dump_file, edge_list);
print_edge_list (dump_file, edge_list);
dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block);
dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
dump_sbitmap_vector (dump_file, "st_antin", "", st_antin, last_basic_block);
dump_sbitmap_vector (dump_file, "st_antout", "", st_antout, last_basic_block);
dump_sbitmap_vector (dump_file, "st_kill", "", kill, last_basic_block);
}
#endif
#ifdef LCM_DEBUG_INFO
if (dump_file)
{
dump_sbitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block);
dump_sbitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block);
}
#endif
farthest = sbitmap_vector_alloc (num_edges, n_exprs);
compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
kill, farthest);
#ifdef LCM_DEBUG_INFO
if (dump_file)
dump_sbitmap_vector (dump_file, "farthest", "", farthest, num_edges);
#endif
sbitmap_vector_free (st_antin);
sbitmap_vector_free (st_antout);
sbitmap_vector_free (st_avin);
sbitmap_vector_free (st_avout);
nearer = sbitmap_vector_alloc (num_edges, n_exprs);
nearerout = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
#ifdef LCM_DEBUG_INFO
if (dump_file)
{
dump_sbitmap_vector (dump_file, "nearerout", "", nearerout,
last_basic_block + 1);
dump_sbitmap_vector (dump_file, "nearer", "", nearer, num_edges);
}
#endif
sbitmap_vector_free (farthest);
*insert = sbitmap_vector_alloc (num_edges, n_exprs);
*delete = sbitmap_vector_alloc (last_basic_block, n_exprs);
compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
*insert, *delete);
sbitmap_vector_free (nearerout);
sbitmap_vector_free (nearer);
#ifdef LCM_DEBUG_INFO
if (dump_file)
{
dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
dump_sbitmap_vector (dump_file, "pre_delete_map", "", *delete,
last_basic_block);
}
#endif
return edge_list;
}