-/**
- * @file beifg_clique.c
- * @date 18.11.2005
- * @author Sebastian Hack
+/*
+ * Copyright (C) 1995-2007 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.
*
- * Copyright (C) 2005 Universitaet Karlsruhe
- * Released under the GPL
+ * Licensees holding valid libFirm Professional Edition licenses may use
+ * this file in accordance with the libFirm Commercial License.
+ * Agreement provided with the Software.
+ *
+ * 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"
#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"
+#include "benodesets.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 {
struct list_head list;
- ir_node *irn;
+ ir_node *irn;
} cli_element_t;
typedef struct _cli_iter_t {
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_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 */
if (&element->list != &head->list)
{
if (element->irn == irn)
- { /* node is in clique */
+ {
+ /* node is in clique */
it->curr_cli_head = head;
- it->curr_cli_element = (void *) head; /* needed because the next element is searched with list.next of it->curr_cli_element */
+ /* needed because the next element is searched with list.next of it->curr_cli_element */
+ it->curr_cli_element = (void *) head;
break;
}
}
return head;
}
-static cli_element_t *get_next_element(const ir_node *irn, cli_iter_t *it) /* ... of the current clique, returns NULL if there were no more elements ..*/
+/* ... 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;
+ 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 */
{
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;
+ nodeset *live = new_nodeset(ifg->env->cls->n_regs);
+ border_t *b;
assert(is_Block(bl) && "There is no block to work on.");
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));
+ bitset_t *bitset_visneighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
int is_dominated_by_max = 0;
int dominates_min = 0;
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 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)
{
cli_iter_t *it = iter;
+ (void) self;
bitset_free(it->visited_neighbours);
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)
{
cli_iter_t *it = iter;
+ (void) self;
bitset_free(it->visited_nodes);