#include "config.h"
#include "system.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"
static void compute_antinout PROTO ((int, int_list_ptr *, sbitmap *,
sbitmap *, sbitmap *, sbitmap *));
static void compute_earlyinout PROTO ((int, int, int_list_ptr *, sbitmap *,
sbitmap *, sbitmap *, sbitmap *));
static void compute_delayinout PROTO ((int, int, int_list_ptr *, sbitmap *,
sbitmap *, sbitmap *,
sbitmap *, sbitmap *));
static void compute_latein PROTO ((int, int, int_list_ptr *, sbitmap *,
sbitmap *, sbitmap *));
static void compute_isoinout PROTO ((int, int_list_ptr *, sbitmap *,
sbitmap *, sbitmap *, sbitmap *));
static void compute_optimal PROTO ((int, sbitmap *,
sbitmap *, sbitmap *));
static void compute_redundant PROTO ((int, int, sbitmap *,
sbitmap *, sbitmap *, sbitmap *));
static void compute_avinout PROTO ((int, int_list_ptr *, sbitmap *,
sbitmap *, sbitmap *, sbitmap *));
static void compute_fartherinout PROTO ((int, int, int_list_ptr *,
sbitmap *, sbitmap *,
sbitmap *, sbitmap *));
static void compute_earlierinout PROTO ((int, int, int_list_ptr *, sbitmap *,
sbitmap *, sbitmap *,
sbitmap *, sbitmap *));
static void compute_firstout PROTO ((int, int, int_list_ptr *, sbitmap *,
sbitmap *, sbitmap *));
static void compute_rev_isoinout PROTO ((int, int_list_ptr *, sbitmap *,
sbitmap *, sbitmap *, sbitmap *));
void
pre_lcm (n_blocks, n_exprs, s_preds, s_succs, transp,
antloc, redundant, optimal)
int n_blocks;
int n_exprs;
int_list_ptr *s_preds;
int_list_ptr *s_succs;
sbitmap *transp;
sbitmap *antloc;
sbitmap *redundant;
sbitmap *optimal;
{
sbitmap *antin, *antout, *earlyin, *earlyout, *delayin, *delayout;
sbitmap *latein, *isoin, *isoout;
antin = sbitmap_vector_alloc (n_blocks, n_exprs);
antout = sbitmap_vector_alloc (n_blocks, n_exprs);
compute_antinout (n_blocks, s_succs, antloc,
transp, antin, antout);
free (antout);
antout = NULL;
earlyin = sbitmap_vector_alloc (n_blocks, n_exprs);
earlyout = sbitmap_vector_alloc (n_blocks, n_exprs);
compute_earlyinout (n_blocks, n_exprs, s_preds, transp, antin,
earlyin, earlyout);
free (earlyout);
earlyout = NULL;
delayin = sbitmap_vector_alloc (n_blocks, n_exprs);
delayout = sbitmap_vector_alloc (n_blocks, n_exprs);
compute_delayinout (n_blocks, n_exprs, s_preds, antloc,
antin, earlyin, delayin, delayout);
free (delayout);
delayout = NULL;
free (antin);
antin = NULL;
free (earlyin);
earlyin = NULL;
latein = sbitmap_vector_alloc (n_blocks, n_exprs);
compute_latein (n_blocks, n_exprs, s_succs, antloc, delayin, latein);
free (delayin);
delayin = NULL;
isoin = sbitmap_vector_alloc (n_blocks, n_exprs);
isoout = sbitmap_vector_alloc (n_blocks, n_exprs);
compute_isoinout (n_blocks, s_succs, antloc, latein, isoin, isoout);
free (isoin);
isoin = NULL;
compute_optimal (n_blocks, latein, isoout, optimal);
compute_redundant (n_blocks, n_exprs, antloc, latein, isoout, redundant);
free (latein);
latein = NULL;
free (isoout);
isoout = NULL;
}
void
pre_rev_lcm (n_blocks, n_exprs, s_preds, s_succs, transp,
avloc, redundant, optimal)
int n_blocks;
int n_exprs;
int_list_ptr *s_preds;
int_list_ptr *s_succs;
sbitmap *transp;
sbitmap *avloc;
sbitmap *redundant;
sbitmap *optimal;
{
sbitmap *avin, *avout, *fartherin, *fartherout, *earlierin, *earlierout;
sbitmap *firstout, *rev_isoin, *rev_isoout;
avin = sbitmap_vector_alloc (n_blocks, n_exprs);
avout = sbitmap_vector_alloc (n_blocks, n_exprs);
compute_avinout (n_blocks, s_preds, avloc, transp, avin, avout);
free (avin);
avin = NULL;
fartherin = sbitmap_vector_alloc (n_blocks, n_exprs);
fartherout = sbitmap_vector_alloc (n_blocks, n_exprs);
compute_fartherinout (n_blocks, n_exprs, s_succs, transp,
avout, fartherin, fartherout);
free (fartherin);
fartherin = NULL;
earlierin = sbitmap_vector_alloc (n_blocks, n_exprs);
earlierout = sbitmap_vector_alloc (n_blocks, n_exprs);
compute_earlierinout (n_blocks, n_exprs, s_succs, avloc,
avout, fartherout, earlierin, earlierout);
free (earlierin);
earlierin = NULL;
free (avout);
avout = NULL;
free (fartherout);
fartherout = NULL;
firstout = sbitmap_vector_alloc (n_blocks, n_exprs);
compute_firstout (n_blocks, n_exprs, s_preds, avloc, earlierout, firstout);
free (earlierout);
earlierout = NULL;
rev_isoin = sbitmap_vector_alloc (n_blocks, n_exprs);
rev_isoout = sbitmap_vector_alloc (n_blocks, n_exprs);
compute_rev_isoinout (n_blocks, s_preds, avloc, firstout,
rev_isoin, rev_isoout);
free (rev_isoout);
rev_isoout = NULL;
compute_optimal (n_blocks, firstout, rev_isoin, optimal);
compute_redundant (n_blocks, n_exprs, avloc, firstout, rev_isoin, redundant);
free (firstout);
firstout = NULL;
free (rev_isoin);
rev_isoin = NULL;
}
static void
compute_antinout (n_blocks, s_succs, antloc, transp, antin, antout)
int n_blocks;
int_list_ptr *s_succs;
sbitmap *antloc;
sbitmap *transp;
sbitmap *antin;
sbitmap *antout;
{
int bb, changed, passes;
sbitmap old_changed, new_changed;
sbitmap_zero (antout[n_blocks - 1]);
sbitmap_vector_ones (antin, n_blocks);
old_changed = sbitmap_alloc (n_blocks);
new_changed = sbitmap_alloc (n_blocks);
sbitmap_ones (old_changed);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
sbitmap_zero (new_changed);
for (bb = n_blocks - 1; bb >= 0; bb--)
{
int_list_ptr ps;
for (ps = s_succs[bb] ; ps; ps = ps->next)
{
if (INT_LIST_VAL (ps) == EXIT_BLOCK
|| INT_LIST_VAL (ps) == ENTRY_BLOCK)
break;
if (TEST_BIT (old_changed, INT_LIST_VAL (ps))
|| TEST_BIT (new_changed, INT_LIST_VAL (ps)))
break;
}
if (!ps)
continue;
if (bb != n_blocks - 1)
sbitmap_intersect_of_successors (antout[bb], antin,
bb, s_succs);
if (sbitmap_a_or_b_and_c (antin[bb], antloc[bb],
transp[bb], antout[bb]))
{
changed = 1;
SET_BIT (new_changed, bb);
}
}
sbitmap_copy (old_changed, new_changed);
passes++;
}
free (old_changed);
free (new_changed);
}
static void
compute_earlyinout (n_blocks, n_exprs, s_preds, transp, antin,
earlyin, earlyout)
int n_blocks;
int n_exprs;
int_list_ptr *s_preds;
sbitmap *transp;
sbitmap *antin;
sbitmap *earlyin;
sbitmap *earlyout;
{
int bb, changed, passes;
sbitmap temp_bitmap;
sbitmap old_changed, new_changed;
temp_bitmap = sbitmap_alloc (n_exprs);
sbitmap_vector_zero (earlyout, n_blocks);
sbitmap_ones (earlyin[0]);
old_changed = sbitmap_alloc (n_blocks);
new_changed = sbitmap_alloc (n_blocks);
sbitmap_ones (old_changed);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
sbitmap_zero (new_changed);
for (bb = 0; bb < n_blocks; bb++)
{
int_list_ptr ps;
for (ps = s_preds[bb] ; ps; ps = ps->next)
{
if (INT_LIST_VAL (ps) == EXIT_BLOCK
|| INT_LIST_VAL (ps) == ENTRY_BLOCK)
break;
if (TEST_BIT (old_changed, INT_LIST_VAL (ps))
|| TEST_BIT (new_changed, INT_LIST_VAL (ps)))
break;
}
if (!ps)
continue;
if (bb != 0)
sbitmap_union_of_predecessors (earlyin[bb], earlyout,
bb, s_preds);
sbitmap_not (temp_bitmap, transp[bb]);
if (sbitmap_union_of_diff (earlyout[bb], temp_bitmap,
earlyin[bb], antin[bb]))
{
changed = 1;
SET_BIT (new_changed, bb);
}
}
sbitmap_copy (old_changed, new_changed);
passes++;
}
free (old_changed);
free (new_changed);
free (temp_bitmap);
}
static void
compute_delayinout (n_blocks, n_exprs, s_preds, antloc,
antin, earlyin, delayin, delayout)
int n_blocks;
int n_exprs;
int_list_ptr *s_preds;
sbitmap *antloc;
sbitmap *antin;
sbitmap *earlyin;
sbitmap *delayin;
sbitmap *delayout;
{
int bb, changed, passes;
sbitmap *anti_and_early;
sbitmap temp_bitmap;
temp_bitmap = sbitmap_alloc (n_exprs);
anti_and_early = sbitmap_vector_alloc (n_blocks, n_exprs);
for (bb = 0; bb < n_blocks; bb++)
sbitmap_a_and_b (anti_and_early[bb], antin[bb], earlyin[bb]);
sbitmap_vector_zero (delayout, n_blocks);
sbitmap_copy (delayin[0], anti_and_early[0]);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
for (bb = 0; bb < n_blocks; bb++)
{
if (bb != 0)
{
sbitmap_intersect_of_predecessors (temp_bitmap, delayout,
bb, s_preds);
changed |= sbitmap_a_or_b (delayin[bb],
anti_and_early[bb],
temp_bitmap);
}
sbitmap_not (temp_bitmap, antloc[bb]);
changed |= sbitmap_a_and_b (delayout[bb],
temp_bitmap,
delayin[bb]);
}
passes++;
}
free (anti_and_early);
free (temp_bitmap);
}
static void
compute_latein (n_blocks, n_exprs, s_succs, antloc, delayin, latein)
int n_blocks;
int n_exprs;
int_list_ptr *s_succs;
sbitmap *antloc;
sbitmap *delayin;
sbitmap *latein;
{
int bb;
sbitmap temp_bitmap;
temp_bitmap = sbitmap_alloc (n_exprs);
for (bb = 0; bb < n_blocks; bb++)
{
if (bb == n_blocks - 1)
{
sbitmap_intersect_of_successors (temp_bitmap, delayin,
bb, s_succs);
sbitmap_not (temp_bitmap, temp_bitmap);
}
else
sbitmap_ones (temp_bitmap);
sbitmap_a_and_b_or_c (latein[bb], delayin[bb],
antloc[bb], temp_bitmap);
}
free (temp_bitmap);
}
static void
compute_isoinout (n_blocks, s_succs, antloc, latein, isoin, isoout)
int n_blocks;
int_list_ptr *s_succs;
sbitmap *antloc;
sbitmap *latein;
sbitmap *isoin;
sbitmap *isoout;
{
int bb, changed, passes;
sbitmap_vector_zero (isoin, n_blocks);
sbitmap_zero (isoout[n_blocks - 1]);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
for (bb = n_blocks - 1; bb >= 0; bb--)
{
if (bb != n_blocks - 1)
sbitmap_intersect_of_successors (isoout[bb], isoin,
bb, s_succs);
changed |= sbitmap_union_of_diff (isoin[bb], latein[bb],
isoout[bb], antloc[bb]);
}
passes++;
}
}
static void
compute_optimal (n_blocks, latein, isoout, optimal)
int n_blocks;
sbitmap *latein;
sbitmap *isoout;
sbitmap *optimal;
{
int bb;
for (bb = 0; bb < n_blocks; bb++)
sbitmap_difference (optimal[bb], latein[bb], isoout[bb]);
}
static void
compute_redundant (n_blocks, n_exprs, antloc, latein, isoout, redundant)
int n_blocks;
int n_exprs;
sbitmap *antloc;
sbitmap *latein;
sbitmap *isoout;
sbitmap *redundant;
{
int bb;
sbitmap temp_bitmap;
temp_bitmap = sbitmap_alloc (n_exprs);
for (bb = 0; bb < n_blocks; bb++)
{
sbitmap_a_or_b (temp_bitmap, latein[bb], isoout[bb]);
sbitmap_difference (redundant[bb], antloc[bb], temp_bitmap);
}
free (temp_bitmap);
}
static void
compute_avinout (n_blocks, s_preds, avloc, transp, avin, avout)
int n_blocks;
int_list_ptr *s_preds;
sbitmap *avloc;
sbitmap *transp;
sbitmap *avin;
sbitmap *avout;
{
int bb, changed, passes;
sbitmap_zero (avin[0]);
sbitmap_vector_ones (avout, n_blocks);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
for (bb = 0; bb < n_blocks; bb++)
{
if (bb != 0)
sbitmap_intersect_of_predecessors (avin[bb], avout,
bb, s_preds);
changed |= sbitmap_a_or_b_and_c (avout[bb], avloc[bb],
transp[bb], avin[bb]);
}
passes++;
}
}
static void
compute_fartherinout (n_blocks, n_exprs, s_succs,
transp, avout, fartherin, fartherout)
int n_blocks;
int n_exprs;
int_list_ptr *s_succs;
sbitmap *transp;
sbitmap *avout;
sbitmap *fartherin;
sbitmap *fartherout;
{
int bb, changed, passes;
sbitmap temp_bitmap;
temp_bitmap = sbitmap_alloc (n_exprs);
sbitmap_vector_zero (fartherin, n_blocks);
sbitmap_ones (fartherout[n_blocks - 1]);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
for (bb = n_blocks - 1; bb >= 0; bb--)
{
if (bb != n_blocks - 1)
sbitmap_union_of_successors (fartherout[bb], fartherin,
bb, s_succs);
sbitmap_not (temp_bitmap, transp[bb]);
changed |= sbitmap_union_of_diff (fartherin[bb], temp_bitmap,
fartherout[bb], avout[bb]);
}
passes++;
}
free (temp_bitmap);
}
static void
compute_earlierinout (n_blocks, n_exprs, s_succs, avloc,
avout, fartherout, earlierin, earlierout)
int n_blocks;
int n_exprs;
int_list_ptr *s_succs;
sbitmap *avloc;
sbitmap *avout;
sbitmap *fartherout;
sbitmap *earlierin;
sbitmap *earlierout;
{
int bb, changed, passes;
sbitmap *av_and_farther;
sbitmap temp_bitmap;
temp_bitmap = sbitmap_alloc (n_exprs);
av_and_farther = sbitmap_vector_alloc (n_blocks, n_exprs);
for (bb = 0; bb < n_blocks; bb++)
sbitmap_a_and_b (av_and_farther[bb], avout[bb], fartherout[bb]);
sbitmap_vector_zero (earlierin, n_blocks);
sbitmap_copy (earlierout[n_blocks - 1], av_and_farther[n_blocks - 1]);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
for (bb = n_blocks - 1; bb >= 0; bb--)
{
if (bb != n_blocks - 1)
{
sbitmap_intersect_of_successors (temp_bitmap, earlierin,
bb, s_succs);
changed |= sbitmap_a_or_b (earlierout[bb],
av_and_farther[bb],
temp_bitmap);
}
sbitmap_not (temp_bitmap, avloc[bb]);
changed |= sbitmap_a_and_b (earlierin[bb],
temp_bitmap,
earlierout[bb]);
}
passes++;
}
free (av_and_farther);
free (temp_bitmap);
}
static void
compute_firstout (n_blocks, n_exprs, s_preds, avloc, earlierout, firstout)
int n_blocks;
int n_exprs;
int_list_ptr *s_preds;
sbitmap *avloc;
sbitmap *earlierout;
sbitmap *firstout;
{
int bb;
sbitmap temp_bitmap;
temp_bitmap = sbitmap_alloc (n_exprs);
for (bb = 0; bb < n_blocks; bb++)
{
if (bb != 0)
{
sbitmap_intersect_of_predecessors (temp_bitmap, earlierout,
bb, s_preds);
sbitmap_not (temp_bitmap, temp_bitmap);
}
else
{
sbitmap_ones (temp_bitmap);
}
sbitmap_a_and_b_or_c (firstout[bb], earlierout[bb],
avloc[bb], temp_bitmap);
}
free (temp_bitmap);
}
static void
compute_rev_isoinout (n_blocks, s_preds, avloc, firstout,
rev_isoin, rev_isoout)
int n_blocks;
int_list_ptr *s_preds;
sbitmap *avloc;
sbitmap *firstout;
sbitmap *rev_isoin;
sbitmap *rev_isoout;
{
int bb, changed, passes;
sbitmap_vector_zero (rev_isoout, n_blocks);
sbitmap_zero (rev_isoin[0]);
passes = 0;
changed = 1;
while (changed)
{
changed = 0;
for (bb = 0; bb < n_blocks; bb++)
{
if (bb != 0)
sbitmap_intersect_of_predecessors (rev_isoin[bb], rev_isoout,
bb, s_preds);
changed |= sbitmap_union_of_diff (rev_isoout[bb], firstout[bb],
rev_isoin[bb], avloc[bb]);
}
passes++;
}
}