#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "et-forest.h"
#include "alloc-pool.h"
#undef DEBUG_ET
#ifdef DEBUG_ET
#include "basic-block.h"
#endif
struct et_occ
{
struct et_node *of;
struct et_occ *parent;
struct et_occ *prev;
struct et_occ *next;
int depth;
int min;
struct et_occ *min_occ;
};
static alloc_pool et_nodes;
static alloc_pool et_occurrences;
static inline void
set_depth (struct et_occ *occ, int d)
{
if (!occ)
return;
occ->min += d - occ->depth;
occ->depth = d;
}
static inline void
set_depth_add (struct et_occ *occ, int d)
{
if (!occ)
return;
occ->min += d;
occ->depth += d;
}
static inline void
set_prev (struct et_occ *occ, struct et_occ *t)
{
#ifdef DEBUG_ET
gcc_assert (occ != t);
#endif
occ->prev = t;
if (t)
t->parent = occ;
}
static inline void
set_next (struct et_occ *occ, struct et_occ *t)
{
#ifdef DEBUG_ET
gcc_assert (occ != t);
#endif
occ->next = t;
if (t)
t->parent = occ;
}
static inline void
et_recomp_min (struct et_occ *occ)
{
struct et_occ *mson = occ->prev;
if (!mson
|| (occ->next
&& mson->min > occ->next->min))
mson = occ->next;
if (mson && mson->min < 0)
{
occ->min = mson->min + occ->depth;
occ->min_occ = mson->min_occ;
}
else
{
occ->min = occ->depth;
occ->min_occ = occ;
}
}
#ifdef DEBUG_ET
static void
et_check_occ_sanity (struct et_occ *occ)
{
if (!occ)
return;
gcc_assert (occ->parent != occ);
gcc_assert (occ->prev != occ);
gcc_assert (occ->next != occ);
gcc_assert (!occ->next || occ->next != occ->prev);
if (occ->next)
{
gcc_assert (occ->next != occ->parent);
gcc_assert (occ->next->parent == occ);
}
if (occ->prev)
{
gcc_assert (occ->prev != occ->parent);
gcc_assert (occ->prev->parent == occ);
}
gcc_assert (!occ->parent
|| occ->parent->prev == occ
|| occ->parent->next == occ);
}
static void
et_check_sanity (struct et_occ *occ)
{
et_check_occ_sanity (occ);
if (occ->prev)
et_check_sanity (occ->prev);
if (occ->next)
et_check_sanity (occ->next);
}
static void
et_check_tree_sanity (struct et_occ *occ)
{
while (occ->parent)
occ = occ->parent;
et_check_sanity (occ);
}
#define MAX_NODES 100000
static int len;
static void *datas[MAX_NODES];
static int depths[MAX_NODES];
static int
record_path_before_1 (struct et_occ *occ, int depth)
{
int mn, m;
depth += occ->depth;
mn = depth;
if (occ->prev)
{
m = record_path_before_1 (occ->prev, depth);
if (m < mn)
mn = m;
}
fprintf (stderr, "%d (%d); ", ((basic_block) occ->of->data)->index, depth);
gcc_assert (len < MAX_NODES);
depths[len] = depth;
datas[len] = occ->of;
len++;
if (occ->next)
{
m = record_path_before_1 (occ->next, depth);
if (m < mn)
mn = m;
}
gcc_assert (mn == occ->min + depth - occ->depth);
return mn;
}
static void
record_path_before (struct et_occ *occ)
{
while (occ->parent)
occ = occ->parent;
len = 0;
record_path_before_1 (occ, 0);
fprintf (stderr, "\n");
}
static int
check_path_after_1 (struct et_occ *occ, int depth)
{
int mn, m;
depth += occ->depth;
mn = depth;
if (occ->next)
{
m = check_path_after_1 (occ->next, depth);
if (m < mn)
mn = m;
}
len--;
gcc_assert (depths[len] == depth && datas[len] == occ->of);
if (occ->prev)
{
m = check_path_after_1 (occ->prev, depth);
if (m < mn)
mn = m;
}
gcc_assert (mn == occ->min + depth - occ->depth);
return mn;
}
static void
check_path_after (struct et_occ *occ)
{
while (occ->parent)
occ = occ->parent;
check_path_after_1 (occ, 0);
gcc_assert (!len);
}
#endif
static void
et_splay (struct et_occ *occ)
{
struct et_occ *f, *gf, *ggf;
int occ_depth, f_depth, gf_depth;
#ifdef DEBUG_ET
record_path_before (occ);
et_check_tree_sanity (occ);
#endif
while (occ->parent)
{
occ_depth = occ->depth;
f = occ->parent;
f_depth = f->depth;
gf = f->parent;
if (!gf)
{
set_depth_add (occ, f_depth);
occ->min_occ = f->min_occ;
occ->min = f->min;
if (f->prev == occ)
{
set_prev (f, occ->next);
set_next (occ, f);
set_depth_add (f->prev, occ_depth);
}
else
{
set_next (f, occ->prev);
set_prev (occ, f);
set_depth_add (f->next, occ_depth);
}
set_depth (f, -occ_depth);
occ->parent = NULL;
et_recomp_min (f);
#ifdef DEBUG_ET
et_check_tree_sanity (occ);
check_path_after (occ);
#endif
return;
}
gf_depth = gf->depth;
set_depth_add (occ, f_depth + gf_depth);
occ->min_occ = gf->min_occ;
occ->min = gf->min;
ggf = gf->parent;
if (gf->prev == f)
{
if (f->prev == occ)
{
set_prev (gf, f->next);
set_prev (f, occ->next);
set_next (occ, f);
set_next (f, gf);
set_depth (f, -occ_depth);
set_depth_add (f->prev, occ_depth);
set_depth (gf, -f_depth);
set_depth_add (gf->prev, f_depth);
}
else
{
set_prev (gf, occ->next);
set_next (f, occ->prev);
set_prev (occ, f);
set_next (occ, gf);
set_depth (f, -occ_depth);
set_depth_add (f->next, occ_depth);
set_depth (gf, -occ_depth - f_depth);
set_depth_add (gf->prev, occ_depth + f_depth);
}
}
else
{
if (f->prev == occ)
{
set_next (gf, occ->prev);
set_prev (f, occ->next);
set_prev (occ, gf);
set_next (occ, f);
set_depth (f, -occ_depth);
set_depth_add (f->prev, occ_depth);
set_depth (gf, -occ_depth - f_depth);
set_depth_add (gf->next, occ_depth + f_depth);
}
else
{
set_next (gf, f->prev);
set_next (f, occ->prev);
set_prev (occ, f);
set_prev (f, gf);
set_depth (f, -occ_depth);
set_depth_add (f->next, occ_depth);
set_depth (gf, -f_depth);
set_depth_add (gf->next, f_depth);
}
}
occ->parent = ggf;
if (ggf)
{
if (ggf->prev == gf)
ggf->prev = occ;
else
ggf->next = occ;
}
et_recomp_min (gf);
et_recomp_min (f);
#ifdef DEBUG_ET
et_check_tree_sanity (occ);
#endif
}
#ifdef DEBUG_ET
et_check_sanity (occ);
check_path_after (occ);
#endif
}
static struct et_occ *
et_new_occ (struct et_node *node)
{
struct et_occ *nw;
if (!et_occurrences)
et_occurrences = create_alloc_pool ("et_occ pool", sizeof (struct et_occ), 300);
nw = pool_alloc (et_occurrences);
nw->of = node;
nw->parent = NULL;
nw->prev = NULL;
nw->next = NULL;
nw->depth = 0;
nw->min_occ = nw;
nw->min = 0;
return nw;
}
struct et_node *
et_new_tree (void *data)
{
struct et_node *nw;
if (!et_nodes)
et_nodes = create_alloc_pool ("et_node pool", sizeof (struct et_node), 300);
nw = pool_alloc (et_nodes);
nw->data = data;
nw->father = NULL;
nw->left = NULL;
nw->right = NULL;
nw->son = NULL;
nw->rightmost_occ = et_new_occ (nw);
nw->parent_occ = NULL;
return nw;
}
void
et_free_tree (struct et_node *t)
{
while (t->son)
et_split (t->son);
if (t->father)
et_split (t);
pool_free (et_occurrences, t->rightmost_occ);
pool_free (et_nodes, t);
}
void
et_free_tree_force (struct et_node *t)
{
pool_free (et_occurrences, t->rightmost_occ);
if (t->parent_occ)
pool_free (et_occurrences, t->parent_occ);
pool_free (et_nodes, t);
}
void
et_free_pools (void)
{
free_alloc_pool_if_empty (&et_occurrences);
free_alloc_pool_if_empty (&et_nodes);
}
void
et_set_father (struct et_node *t, struct et_node *father)
{
struct et_node *left, *right;
struct et_occ *rmost, *left_part, *new_f_occ, *p;
new_f_occ = et_new_occ (father);
rmost = father->rightmost_occ;
et_splay (rmost);
left_part = rmost->prev;
p = t->rightmost_occ;
et_splay (p);
set_prev (new_f_occ, left_part);
set_next (new_f_occ, p);
p->depth++;
p->min++;
et_recomp_min (new_f_occ);
set_prev (rmost, new_f_occ);
if (new_f_occ->min + rmost->depth < rmost->min)
{
rmost->min = new_f_occ->min + rmost->depth;
rmost->min_occ = new_f_occ->min_occ;
}
t->parent_occ = new_f_occ;
t->father = father;
right = father->son;
if (right)
left = right->left;
else
left = right = t;
left->right = t;
right->left = t;
t->left = left;
t->right = right;
father->son = t;
#ifdef DEBUG_ET
et_check_tree_sanity (rmost);
record_path_before (rmost);
#endif
}
void
et_split (struct et_node *t)
{
struct et_node *father = t->father;
struct et_occ *r, *l, *rmost, *p_occ;
rmost = t->rightmost_occ;
et_splay (rmost);
for (r = rmost->next; r->prev; r = r->prev)
continue;
et_splay (r);
r->prev->parent = NULL;
p_occ = t->parent_occ;
et_splay (p_occ);
t->parent_occ = NULL;
l = p_occ->prev;
p_occ->next->parent = NULL;
set_prev (r, l);
et_recomp_min (r);
et_splay (rmost);
rmost->depth = 0;
rmost->min = 0;
pool_free (et_occurrences, p_occ);
if (father->son == t)
father->son = t->right;
if (father->son == t)
father->son = NULL;
else
{
t->left->right = t->right;
t->right->left = t->left;
}
t->left = t->right = NULL;
t->father = NULL;
#ifdef DEBUG_ET
et_check_tree_sanity (rmost);
record_path_before (rmost);
et_check_tree_sanity (r);
record_path_before (r);
#endif
}
struct et_node *
et_nca (struct et_node *n1, struct et_node *n2)
{
struct et_occ *o1 = n1->rightmost_occ, *o2 = n2->rightmost_occ, *om;
struct et_occ *l, *r, *ret;
int mn;
if (n1 == n2)
return n1;
et_splay (o1);
l = o1->prev;
r = o1->next;
if (l)
l->parent = NULL;
if (r)
r->parent = NULL;
et_splay (o2);
if (l == o2 || (l && l->parent != NULL))
{
ret = o2->next;
set_prev (o1, o2);
if (r)
r->parent = o1;
}
else
{
ret = o2->prev;
set_next (o1, o2);
if (l)
l->parent = o1;
}
if (0 < o2->depth)
{
om = o1;
mn = o1->depth;
}
else
{
om = o2;
mn = o2->depth + o1->depth;
}
#ifdef DEBUG_ET
et_check_tree_sanity (o2);
#endif
if (ret && ret->min + o1->depth + o2->depth < mn)
return ret->min_occ->of;
else
return om->of;
}
bool
et_below (struct et_node *down, struct et_node *up)
{
struct et_occ *u = up->rightmost_occ, *d = down->rightmost_occ;
struct et_occ *l, *r;
if (up == down)
return true;
et_splay (u);
l = u->prev;
r = u->next;
if (!l)
return false;
l->parent = NULL;
if (r)
r->parent = NULL;
et_splay (d);
if (l == d || l->parent != NULL)
{
if (r)
r->parent = u;
set_prev (u, d);
#ifdef DEBUG_ET
et_check_tree_sanity (u);
#endif
}
else
{
l->parent = u;
if (r && r->parent != NULL)
set_next (u, d);
else
set_next (u, r);
#ifdef DEBUG_ET
et_check_tree_sanity (u);
#endif
return false;
}
if (0 >= d->depth)
return false;
return !d->next || d->next->min + d->depth >= 0;
}