X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeifg_clique.c;h=c8864f84e274e3995e5a87eae0d5ec28d4c08bf2;hb=22b354ac921664032c93e5f0176fa668c95dfc60;hp=7c583451af3b2ded132e55e715e418202f1765f1;hpb=287b05140d6a6e7c74c779035cb760b4a7f5aa39;p=libfirm

diff --git a/ir/be/beifg_clique.c b/ir/be/beifg_clique.c
index 7c583451a..c8864f84e 100644
--- a/ir/be/beifg_clique.c
+++ b/ir/be/beifg_clique.c
@@ -1,14 +1,30 @@
-/**
- * @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.
  *
- * 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"
-#endif
 
 #include <stdlib.h>
 
@@ -18,39 +34,41 @@
 #include "irnode_t.h"
 #include "irgraph_t.h"
 #include "irgwalk.h"
+#include "irbitset.h"
 
+#include "bearch.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;
-	bitset_t *visited_nodes;
-	bitset_t *visited_neighbours;
+	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 {
-	ifg_clique_t *ifg;
-	cli_head_t *curr_cli_head;
-	cli_element_t *curr_cli_element;
-	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 */
@@ -61,7 +79,7 @@ static cli_head_t *get_new_cli_head(ifg_clique_t *ifg)
 
 	if (ifg->cli_root == NULL)
 	{
-		new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
+		new_cli_head = OALLOC(&ifg->obst, cli_head_t);
 		INIT_LIST_HEAD(&new_cli_head->list);
 		ifg->cli_root = new_cli_head;
 	}
@@ -72,7 +90,7 @@ static cli_head_t *get_new_cli_head(ifg_clique_t *ifg)
 		{
 			cli_head = cli_head->next_cli_head;
 		}
-		new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
+		new_cli_head = OALLOC(&ifg->obst, cli_head_t);
 		INIT_LIST_HEAD(&new_cli_head->list);
 		cli_head->next_cli_head = new_cli_head;
 	}
@@ -89,13 +107,13 @@ static cli_element_t *get_new_cli_element(ifg_clique_t *ifg)
 {
 	cli_element_t *cli_element;
 
-	cli_element = obstack_alloc(&ifg->obst, sizeof(*cli_element));
+	cli_element = OALLOC(&ifg->obst, cli_element_t);
 	INIT_LIST_HEAD(&cli_element->list);
 
 	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;
@@ -106,8 +124,9 @@ static void write_clique(nodeset *live_set, ifg_clique_t *ifg)
 	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;
@@ -167,9 +186,6 @@ static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...c
 	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 */
@@ -178,9 +194,11 @@ static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...c
 			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;
 				}
 			}
@@ -200,10 +218,11 @@ static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...c
 	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 */
 	{
@@ -220,7 +239,7 @@ static cli_element_t *get_next_element(const ir_node *irn, cli_iter_t *it) /* ..
 			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);
@@ -237,19 +256,18 @@ 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;
 
-	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);
 		it->curr_cli_element = element;
 	}
-
-	return;
 }
 
 static ir_node *get_next_node(cli_iter_t *it)
@@ -288,13 +306,13 @@ static ir_node *get_next_node(cli_iter_t *it)
 	}
 	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));
 		}
 	}
 
@@ -303,24 +321,23 @@ static ir_node *get_next_node(cli_iter_t *it)
 
 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.");
 
 	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 */
 		{
-			nodeset_insert(live, irn);
+			ir_nodeset_insert(&live, irn);
 			if(b->is_real)
 			{
 				was_def = 1;
@@ -330,19 +347,20 @@ static void find_neighbour_walker(ir_node *bl, void *data)
 		{
 			if (was_def == 1) /* if there is a USE after a DEF... */
 			{
-				write_clique(live, ifg); /* ...add the clique. */
+				write_clique(&live, ifg); /* ...add the clique. */
 				was_def = 0;
 			}
-			nodeset_remove(live, irn);
+			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;
@@ -350,7 +368,7 @@ static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const
 
 	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.");
 
@@ -362,15 +380,12 @@ static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const
 		/* 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;
 			}
 		}
 	}
@@ -382,15 +397,11 @@ static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const
 
 	it->curr_cli_element = element;
 	it->curr_irn = irn;
-
-	return;
 }
 
 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)
@@ -398,30 +409,17 @@ static ir_node *get_next_neighbour(cli_iter_t *it)
 	else
 		return NULL;
 
-	element = get_next_element(irn, it);
-
-	if (element == NULL) /* no more elements in this clique */
-	{
-		it->curr_cli_element = NULL;
-	}
-	else
-	{
-		it->curr_cli_element = element;
-	}
+	it->curr_cli_element = get_next_element(irn, it);
 
-	if (!(res == NULL))
+	if (res)
 	{
-		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));
 		}
 	}
 
@@ -439,8 +437,9 @@ static void ifg_clique_free(void *self)
 	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;
@@ -469,12 +468,16 @@ static ir_node *ifg_clique_neighbours_begin(const void *self, void *iter, const
 
 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)
@@ -485,26 +488,30 @@ 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;
@@ -530,11 +537,8 @@ static const be_ifg_impl_t ifg_clique_impl = {
 
 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_clique_t *ifg	= XMALLOC(ifg_clique_t);
+
 	ifg->impl     		= &ifg_clique_impl;
 	ifg->env			= env;