#include "irnode_t.h"
#include "irgraph_t.h"
#include "irgwalk.h"
+#include "irbitset.h"
#include "be_t.h"
#include "bera.h"
cli_head_t *cli_root;
struct obstack obst;
cli_head_t *curr_cli_head;
- bitset_t *visited_nodes;
- bitset_t *visited_neighbours;
} ifg_clique_t;
typedef struct _cli_element_t {
} cli_element_t;
typedef struct _cli_iter_t {
- ifg_clique_t *ifg;
+ const ifg_clique_t *ifg;
cli_head_t *curr_cli_head;
cli_element_t *curr_cli_element;
const ir_node *curr_irn;
+ bitset_t *visited_neighbours;
+ bitset_t *visited_nodes;
} cli_iter_t;
/* PRIVATE FUNCTIONS */
is_dominated_by_max = value_dominates(head->max, irn);
//dominates_min = value_dominates(irn, head->min);
- if(head->min->node_nr == 2000)
- assert("stop");
-
if ((is_dominated_by_max) || (irn == head->max)) /* node could be in clique */
{
/* check if node is in clique */
element = get_next_element(irn, it);
}
- if (element != NULL && element->irn == irn) /* the node you are searching neighbors for */
+ if (element && element->irn == irn) /* the node you are searching neighbors for */
{
it->curr_cli_element = element;
element = get_next_element(irn, it);
cli_element_t *element;
cli_head_t *cli_head = ifg->cli_root;
- bitset_clear_all(ifg->visited_nodes);
-
- assert(cli_head && "There is no root entry to work on!");
+ bitset_t *bitset_visnodes = bitset_malloc(get_irg_last_idx(ifg->env->irg));
+ it->visited_nodes = bitset_visnodes;
it->curr_cli_head = cli_head;
+ assert(cli_head && "There is no root entry to work on!");
+
if (cli_head->list.next != &cli_head->list) /* if cli_head contains an element */
{
element = list_entry(cli_head->list.next, cli_element_t, list);
}
if (!(irn == NULL))
{
- if (bitset_is_set(it->ifg->visited_nodes, get_irn_idx(irn)))
+ if (bitset_is_set(it->visited_nodes, get_irn_idx(irn)))
{
irn = get_next_node(it);
}
if (!(irn == NULL))
{
- bitset_set(it->ifg->visited_nodes, get_irn_idx(irn));
+ bitset_set(it->visited_nodes, get_irn_idx(irn));
}
}
foreach_border_head(head, b) /* follow the borders of the block */
{
ir_node *irn = b->irn;
-//
-// if (b->irn->node_nr == 1869)
-// printf("");
if (b->is_def) /* b is a new node */
{
{
cli_head_t *cli_head = ifg->cli_root;
cli_element_t *element;
+ bitset_t *bitset_visneighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
int is_dominated_by_max = 0;
int dominates_min = 0;
it->curr_cli_head = cli_head;
it->ifg = ifg;
- bitset_clear_all(it->ifg->visited_neighbours);
+ it->visited_neighbours = bitset_visneighbours;
assert(cli_head && "There is no root entry for a cli_head.");
/* check if node is in clique */
list_for_each_entry(cli_element_t, element, &cli_head->list, list)
{
- if (&element->list != &cli_head->list)
+ if (element->irn == irn) /* node is in clique */
{
- if (element->irn == irn)
- { /* node is in clique */
- it->curr_cli_element = (void *) cli_head; /* needed because the next element is searched with list.next of it->curr_cli_element */
- is_in_clique = 1;
- element = get_next_element(irn, it);
- break;
- }
+ it->curr_cli_element = (void *) cli_head; /* needed because the next element is searched with list.next of it->curr_cli_element */
+ is_in_clique = 1;
+ element = get_next_element(irn, it);
+ break;
}
}
}
static ir_node *get_next_neighbour(cli_iter_t *it)
{
ir_node *res = NULL;
- cli_element_t *element;
- cli_head_t *cli_head = it->curr_cli_head;
const ir_node *irn = it->curr_irn;
if (it->curr_cli_element != NULL)
else
return NULL;
- element = get_next_element(irn, it);
+ it->curr_cli_element = get_next_element(irn, it);
- if (element == NULL) /* no more elements in this clique */
+ if (res)
{
- it->curr_cli_element = NULL;
- }
- else
- {
- it->curr_cli_element = element;
- }
-
- if (!(res == NULL))
- {
- if (bitset_is_set(it->ifg->visited_neighbours, get_irn_idx(res)))
+ if (bitset_contains_irn(it->visited_neighbours, res))
{
res = get_next_neighbour(it);
-// if (res == NULL) /* there are no more neighbours to return */
-// {
-// return NULL;
-// }
}
else
{
- bitset_set(it->ifg->visited_neighbours, get_irn_idx(res));
+ bitset_set(it->visited_neighbours, get_irn_idx(res));
}
}
free(self);
}
-static int ifg_clique_connected(const ifg_clique_t *ifg, const ir_node *a, const ir_node *b)
+static int ifg_clique_connected(const void *self, const ir_node *a, const ir_node *b)
{
+ const ifg_clique_t *ifg = self;
cli_iter_t it;
int connected = -1;
ir_node *irn = NULL;
static void ifg_clique_neighbours_break(const void *self, void *iter)
{
+ cli_iter_t *it = iter;
+
+ bitset_free(it->visited_neighbours);
+
return;
}
static void ifg_clique_nodes_break(const void *self, void *iter)
{
+ cli_iter_t *it = iter;
+
+ bitset_free(it->visited_nodes);
+
return;
}
static int ifg_clique_degree(const void *self, const ir_node *irn)
{
int degree = -1;
- cli_iter_t *it = NULL;
+ cli_iter_t it;
- find_first_neighbour(self, it, irn);
+ find_first_neighbour(self, &it, irn);
degree = 0;
- irn = get_next_neighbour(it);
+ irn = get_next_neighbour(&it);
while (irn != NULL)
{
degree++;
- irn = get_next_neighbour(it);
+ irn = get_next_neighbour(&it);
}
return degree;
be_ifg_t *be_ifg_clique_new(const be_chordal_env_t *env)
{
ifg_clique_t *ifg = xmalloc(sizeof(*ifg));
- bitset_t *bitset_visnodes = bitset_malloc(get_irg_last_idx(env->irg));
- bitset_t *bitset_visneighbours = bitset_malloc(get_irg_last_idx(env->irg));
- ifg->visited_nodes = bitset_visnodes;
- ifg->visited_neighbours = bitset_visneighbours;
+
ifg->impl = &ifg_clique_impl;
ifg->env = env;