-/**
- * @file beifg_clique.c
- * @date 18.11.2005
- * @author Sebastian Hack
+/*
+ * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
+ *
+ * This file is part of libFirm.
+ *
+ * This file may be distributed and/or modified under the terms of the
+ * GNU General Public License version 2 as published by the Free Software
+ * Foundation and appearing in the file LICENSE.GPL included in the
+ * packaging of this file.
+ *
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
*
- * Copyright (C) 2005 Universitaet Karlsruhe
- * Released under the GPL
+ * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+ * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE.
+ */
+
+/**
+ * @file
+ * @brief Clique calculation for chordal ifg.
+ * @author Sebastian Hack
+ * @date 18.11.2005
+ * @version $Id$
*/
-#ifdef HAVE_CONFIG_H
#include "config.h"
-#endif
#include <stdlib.h>
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irgwalk.h"
+#include "irbitset.h"
+#include "bearch_t.h"
#include "be_t.h"
-#include "bera.h"
+#include "beintlive_t.h"
#include "beifg_t.h"
#include "bechordal_t.h"
typedef struct _cli_head_t {
- struct list_head list;
+ struct list_head list;
struct _cli_head_t *next_cli_head;
- ir_node *min;
- ir_node *max;
+ ir_node *min;
+ ir_node *max;
} cli_head_t;
typedef struct _ifg_clique_t {
- const be_ifg_impl_t *impl;
+ const be_ifg_impl_t *impl;
const be_chordal_env_t *env;
- cli_head_t *cli_root;
- struct obstack obst;
- cli_head_t *curr_cli_head;
+ cli_head_t *cli_root;
+ struct obstack obst;
+ cli_head_t *curr_cli_head;
} ifg_clique_t;
typedef struct _cli_element_t {
- ir_node *irn;
struct list_head list;
+ ir_node *irn;
} cli_element_t;
typedef struct _cli_iter_t {
- ifg_clique_t *ifg;
- cli_head_t *curr_cli_head;
- cli_element_t *curr_cli_element;
- unsigned long curr_irg_visited;
- const ir_node *curr_irn;
+ 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 */
return cli_element;
}
-static void write_clique(nodeset *live_set, ifg_clique_t *ifg)
+static void write_clique(ir_nodeset_t *live_set, ifg_clique_t *ifg)
{
ir_node *live_irn;
ir_node *test_node;
cli_element_t *element = NULL;
cli_head_t *cli_head = get_new_cli_head(ifg);
int is_element = 0;
+ ir_nodeset_iterator_t iter;
- foreach_nodeset(live_set, live_irn)
+ foreach_ir_nodeset(live_set, live_irn, iter)
{
/* test if node is max or min dominator*/
test_node = live_irn;
{
min_node = test_node;
}
+ }
- list_for_each_entry(cli_element_t, element, &cli_head->list, list){
- if(element->irn == live_irn){
- is_element = 1;
- break;
- }
+ list_for_each_entry(cli_element_t, element, &cli_head->list, list){
+ if(element->irn == live_irn){
+ is_element = 1;
+ break;
}
+ }
- if (!is_element){
- new_element = get_new_cli_element(ifg);
- new_element->irn = live_irn;
- list_add(&new_element->list, &cli_head->list) ;
- }
+ if (!is_element){
+ new_element = get_new_cli_element(ifg);
+ new_element->irn = live_irn;
+ list_add(&new_element->list, &cli_head->list) ;
}
}
cli_head->max = max_node;
}
+static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...containing the node *irn */
+{
+ cli_head_t *head;
+ cli_element_t *element;
+
+ int is_dominated_by_max;
+ //int dominates_min;
+
+ if (it->curr_cli_head == NULL || it->curr_cli_head->next_cli_head == NULL) /* way back of recursion or this is the last clique */
+ {
+ it->curr_cli_head = NULL;
+ return NULL;
+ }
+
+ head = it->curr_cli_head->next_cli_head;
+
+ is_dominated_by_max = value_dominates(head->max, irn);
+ //dominates_min = value_dominates(irn, head->min);
+
+ if ((is_dominated_by_max) || (irn == head->max)) /* node could be in clique */
+ {
+ /* check if node is in clique */
+ list_for_each_entry(cli_element_t, element, &head->list, list)
+ {
+ if (&element->list != &head->list)
+ {
+ if (element->irn == irn)
+ {
+ /* node is in clique */
+ it->curr_cli_head = head;
+ /* needed because the next element is searched with list.next of it->curr_cli_element */
+ it->curr_cli_element = (void *) head;
+ break;
+ }
+ }
+ }
+
+ if (it->curr_cli_head != head) /*node was not in clique */
+ {
+ it->curr_cli_head = head;
+ head = get_next_cli_head(irn, it);
+ }
+ }
+ else
+ {
+ it->curr_cli_head = head;
+ head = get_next_cli_head(irn, it);
+ }
+ return head;
+}
+
+/* ... of the current clique, returns NULL if there were no more elements ..*/
+static cli_element_t *get_next_element(const ir_node *irn, cli_iter_t *it)
+{
+ cli_element_t *element = it->curr_cli_element;
+ cli_head_t *head = it->curr_cli_head;
+
+ if (!head || it->curr_cli_element == NULL) /* way back of recursion or there are no more heads */
+ {
+ it->curr_cli_element = NULL;
+ return NULL;
+ }
+ else
+ {
+ element = list_entry(element->list.next, cli_element_t, list);
+
+ if (&element->list == &head->list) /* Clique has no more elements */
+ {
+ head = get_next_cli_head(irn, it);
+ element = get_next_element(irn, it);
+ }
+
+ if (element && element->irn == irn) /* the node you are searching neighbors for */
+ {
+ it->curr_cli_element = element;
+ element = get_next_element(irn, it);
+ }
+
+ it->curr_cli_element = element;
+
+ return element;
+ }
+}
+
static void find_nodes(const ifg_clique_t *ifg, cli_iter_t *it)
{
cli_element_t *element;
cli_head_t *cli_head = ifg->cli_root;
- assert((cli_head == NULL) && "There is no node 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);
it->curr_cli_element = element;
-
- inc_irg_visited(get_irn_irg(element->irn));
- it->curr_irg_visited = get_irg_visited(get_irn_irg(element->irn));
}
-
- return;
}
static ir_node *get_next_node(cli_iter_t *it)
{
cli_head_t *cli_head = NULL;
cli_element_t *element = it->curr_cli_element;
- unsigned long irn_visited = get_irn_visited(element->irn);
ir_node *irn;
- if (!(element == it->curr_cli_element))
+ if (element == NULL)
+ return NULL;
+
+ if (!(&it->curr_cli_head->list == element->list.next))
{
irn = element->irn;
- element = list_entry(cli_head->list.next, cli_element_t, list);
+ element = list_entry(element->list.next, cli_element_t, list);
it->curr_cli_element = element;
}
- else
+ else /* reached end of clique */
{
cli_head = it->curr_cli_head;
if (!(cli_head->next_cli_head == NULL))
}
else
{
- return NULL;
+ it->curr_cli_head = NULL;
+ it->curr_cli_element = NULL;
+ irn = element->irn;
}
}
-
- if (irn_visited == it->curr_irg_visited)
+ if (!(irn == NULL))
{
- irn = get_next_node(it);
+ if (bitset_is_set(it->visited_nodes, get_irn_idx(irn)))
+ {
+ irn = get_next_node(it);
+ }
+ if (!(irn == NULL))
+ {
+ bitset_set(it->visited_nodes, get_irn_idx(irn));
+ }
}
- set_irn_visited(irn, it->curr_irg_visited);
return irn;
}
static void find_neighbour_walker(ir_node *bl, void *data)
{
- ifg_clique_t *ifg = data;
- struct list_head *head = get_block_border_head(ifg->env, bl);
- border_t *b;
- int was_def = 0;
- nodeset *live = new_nodeset(ifg->env->cls->n_regs);
+ ifg_clique_t *ifg = data;
+ struct list_head *head = get_block_border_head(ifg->env, bl);
+ int was_def = 0;
+ ir_nodeset_t live;
+ border_t *b;
+
+ ir_nodeset_init(&live);
assert(is_Block(bl) && "There is no block to work on.");
if (b->is_def) /* b is a new node */
{
- nodeset_insert(live, irn);
+ ir_nodeset_insert(&live, irn);
if(b->is_real)
{
was_def = 1;
}
else
{
- if (!(b->is_def))
+ if (was_def == 1) /* if there is a USE after a DEF... */
{
- if (was_def == 1) /* if there is a USE after a DEF... */
- {
- write_clique(live, ifg); /* ...add the clique. */
- was_def = 0;
- }
- nodeset_remove(live, irn);
+ write_clique(&live, ifg); /* ...add the clique. */
+ was_def = 0;
}
+ ir_nodeset_remove(&live, irn);
}
}
- del_nodeset(live);
+ ir_nodeset_destroy(&live);
}
static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const ir_node *irn)
{
- cli_head_t *cli_head = ifg->cli_root;
+ 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;
+ int is_in_clique = 0;
- assert(!cli_head && "There is no root entry for a cli_head.");
+ it->curr_cli_head = cli_head;
+ it->ifg = ifg;
+ it->visited_neighbours = bitset_visneighbours;
- while(!(cli_head->next_cli_head == NULL))
- {
- is_dominated_by_max = value_dominates(cli_head->max, irn);
- dominates_min = value_dominates(irn, cli_head->min);
+ assert(cli_head && "There is no root entry for a cli_head.");
- if ((is_dominated_by_max && dominates_min) /* node is in clique */
- || (irn == cli_head->max)
- || (irn == cli_head->min))
- {
- element = list_entry(cli_head->list.next, cli_element_t, list);
+ is_dominated_by_max = value_dominates(cli_head->max, irn);
+ dominates_min = value_dominates(irn, cli_head->min);
- it->curr_cli_element = element;
- it->curr_cli_head = cli_head;
- break;
- }
- else
+ if ((is_dominated_by_max) || (irn == cli_head->max)) /* node could be in clique */
+ {
+ /* check if node is in clique */
+ list_for_each_entry(cli_element_t, element, &cli_head->list, list)
{
- cli_head = cli_head->next_cli_head;
+ 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_irn = irn;
+ if(!is_in_clique)
+ {
+ cli_head = get_next_cli_head(irn, it);
+ element = get_next_element(irn, it);
+ }
- inc_irg_visited(get_irn_irg(irn));
- it->curr_irg_visited = get_irg_visited(get_irn_irg(irn));
- return;
+ it->curr_cli_element = element;
+ it->curr_irn = irn;
}
static ir_node *get_next_neighbour(cli_iter_t *it)
{
ir_node *res = NULL;
- cli_element_t *element = NULL;
- cli_head_t *cli_head = NULL;
- int is_dominated_by_max;
- int dominates_min;
const ir_node *irn = it->curr_irn;
- unsigned long irn_visited = 0;
- res = it->curr_cli_element->irn;
-
- /* get next element */
+ if (it->curr_cli_element != NULL)
+ res = it->curr_cli_element->irn;
+ else
+ return NULL;
- element = list_entry(it->curr_cli_element->list.next, cli_element_t, list);
- irn_visited = get_irn_visited(element->irn);
+ it->curr_cli_element = get_next_element(irn, it);
- if ((cli_head_t *)element == it->curr_cli_head) /* end of clique, search next one */
+ if (res)
{
- cli_head = cli_head->next_cli_head;
- while(!(cli_head->next_cli_head == NULL))
+ if (bitset_contains_irn(it->visited_neighbours, res))
{
- is_dominated_by_max = value_dominates(cli_head->max, irn);
- dominates_min = value_dominates(irn, cli_head->min);
-
- if ((is_dominated_by_max && dominates_min) /* node is in clique */
- || (irn == cli_head->max)
- || (irn == cli_head->min))
- {
- element = list_entry(cli_head->list.next, cli_element_t, list);
-
- it->curr_cli_element = element;
- it->curr_cli_head = cli_head;
- break;
- }
- else
- {
- cli_head = cli_head->next_cli_head;
- }
+ res = get_next_neighbour(it);
+ }
+ else
+ {
+ bitset_set(it->visited_neighbours, get_irn_idx(res));
}
- }
- else /* get next element of this clique */
- {
- it->curr_cli_element = element;
- }
-
- if (irn_visited == it->curr_irg_visited)
- {
- irn = get_next_neighbour(it);
}
- set_irn_visited(res, it->curr_irg_visited);
-
return res;
}
static int ifg_clique_connected(const void *self, const ir_node *a, const ir_node *b)
{
- cli_iter_t *it = NULL;
+ const ifg_clique_t *ifg = self;
+ cli_iter_t it;
int connected = -1;
ir_node *irn = NULL;
- find_first_neighbour(self, it, a);
+ find_first_neighbour(ifg, &it, a);
connected = 0;
- irn = get_next_neighbour(it);
+ irn = get_next_neighbour(&it);
while (irn != NULL)
{
if (irn == b)
{
connected = 1;
+ break;
}
- irn = get_next_neighbour(it);
+ irn = get_next_neighbour(&it);
}
return connected;
static ir_node *ifg_clique_neighbours_next(const void *self, void *iter)
{
+ (void) self;
return get_next_neighbour(iter);
}
static void ifg_clique_neighbours_break(const void *self, void *iter)
{
- return;
+ cli_iter_t *it = iter;
+ (void) self;
+
+ bitset_free(it->visited_neighbours);
}
static ir_node *ifg_clique_nodes_begin(const void *self, void *iter)
static ir_node *ifg_clique_nodes_next(const void *self, void *iter)
{
+ (void) self;
return get_next_node(iter);
}
static void ifg_clique_nodes_break(const void *self, void *iter)
{
- return;
+ cli_iter_t *it = iter;
+ (void) self;
+
+ bitset_free(it->visited_nodes);
}
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));
+ ifg_clique_t *ifg = XMALLOC(ifg_clique_t);
+
ifg->impl = &ifg_clique_impl;
ifg->env = env;
projects / libfirm / blobdiff