X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeifg_pointer.c;h=a51735c5dc852c1f1e2dd73858652289a1c0decf;hb=3f807bf48426a29da4129ff29c44a4b4690c45f6;hp=f40bcf0703bb730ecdc93ac8af79047ce9b6e812;hpb=51b9ece7394f09ec1577b764446938976ad6b867;p=libfirm

diff --git a/ir/be/beifg_pointer.c b/ir/be/beifg_pointer.c
index f40bcf070..a51735c5d 100644
--- a/ir/be/beifg_pointer.c
+++ b/ir/be/beifg_pointer.c
@@ -1,13 +1,29 @@
-/**
- * @file   beifg_pointer.c
- * @date   20.03.2006
- * @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.
  */
 
-#if 0
+/**
+ * @file
+ * @brief       Pointer based implementation of chordal interference graphs.
+ * @author      Sebastian Hack
+ * @date        18.11.2005
+ * @version     $Id$
+ */
 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #endif
@@ -16,370 +32,566 @@
 
 #include "belive_t.h"
 #include "list.h"
+#include "irphase_t.h"
 
 #include "irnode_t.h"
 #include "irgraph_t.h"
 #include "irgwalk.h"
+#include "irbitset.h"
 
 #include "be_t.h"
 #include "bera.h"
 #include "beifg_t.h"
 #include "bechordal_t.h"
 
-typedef struct _cli_head_t {
-  struct list_head list;
-	struct _cli_head_t *next_cli_head;
-	ir_node *min;
-	ir_node *max;
-} cli_head_t;
+typedef struct _ptr_element_t ptr_element_t;
+
+typedef union element_content {
+	ir_node       *irn;
+	ptr_element_t *element;
+} element_content;
+
+struct _ptr_element_t {
+	int kind; /* kind = 8888 ..> both are ir_nodes, = 3101 ..> first is another element, second an ir_node */
+	element_content content_first; /* could be a ptr_element or ir_node */
+	element_content content_second; /* could be a ptr_element or ir_node */
+};
+
+typedef struct _ptr_head_t {
+	struct list_head list;
+	ptr_element_t    *element;
+} ptr_head_t;
 
 typedef struct _ifg_pointer_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;
+	ir_phase               ph;
+	struct obstack         obst;
+	ptr_head_t             *curr_ptr_head;
+	ptr_element_t          *curr_element;
 } ifg_pointer_t;
 
-typedef struct _cli_element_t {
-	ir_node *irn;
-	struct list_head list;
-} cli_element_t;
-
-typedef struct _cli_iter_t {
-	ifg_pointer_t *ifg;
-	cli_head_t *curr_cli_head;
-	cli_element_t *curr_cli_element;
-	unsigned long curr_irg_visited;
-	const ir_node *curr_irn;
-} cli_iter_t;
+typedef struct _ptr_iter_t {
+	const ifg_pointer_t *ifg;
+	const ir_node       *irn;
+	ptr_head_t          *curr_ptr_head;
+	ptr_head_t          *first_head;
+	ptr_element_t       *curr_element_t;
+	ir_node             *curr_irn;
+	int                 get_first;
+	int                 sub_call;
+	bitset_t            *visited_neighbours;
+} ptr_iter_t;
 
 /* PRIVATE FUNCTIONS */
-static cli_head_t *get_new_cli_head(void *data)
-{
-	cli_iter_t *it = data;
-	cli_head_t *cli_head;
-	cli_head_t *new_cli_head;
 
-	if (it->ifg->cli_root == NULL)
-	{
-	new_cli_head = obstack_alloc(&it->ifg->obst, sizeof(*new_cli_head));
-	INIT_LIST_HEAD(&new_cli_head->list);
-
-	new_cli_head->next_cli_head = NULL;
-	it->ifg->cli_root = new_cli_head;
-	it->curr_cli_head = new_cli_head;
-	}
-	else
-	{
-		cli_head = it->ifg->cli_root;
-		while(!(cli_head->next_cli_head == NULL))
-		{
-			cli_head = cli_head->next_cli_head;
-		}
-		new_cli_head = obstack_alloc(&it->ifg->obst, sizeof(*new_cli_head));
-		INIT_LIST_HEAD(&new_cli_head->list);
-		cli_head->next_cli_head = new_cli_head;
-		it->curr_cli_head = new_cli_head;
-	}
-
-	cli_head->min = NULL;
-	cli_head->max = NULL;
-
-	return new_cli_head;
+static void *ptr_irn_data_init(ir_phase *ph, const ir_node *irn, void *data)
+{
+	ptr_head_t *head = phase_alloc(ph, sizeof(*head));
+	(void) irn;
+	(void) data;
+	INIT_LIST_HEAD(&head->list);
+	return head;
 }
 
-static cli_head_t *get_first_cli_head(void *data)
+static ptr_element_t *ptr_get_new_element(ifg_pointer_t *ifg)
 {
-	cli_iter_t *it = data;
-
-	return it->ifg->cli_root;
+	ptr_element_t *new_element = obstack_alloc(&ifg->obst, sizeof(ptr_element_t));
+	memset(new_element, 0, sizeof(*new_element));
+	return new_element;
 }
 
-static void write_clique(pset *live_set, void *data)
+static ptr_head_t *ptr_get_new_head(ifg_pointer_t *ifg)
 {
-	ir_node *live_irn;
-	ir_node *test_node;
-	int test_int = 0;
-	ir_node *max_node;
-	ir_node *min_node;
-	cli_iter_t *it = data;
-	pset *live = live_set;
-	cli_element_t *element;
-	int is_element = 0;
-
-	cli_head_t *cli_head = get_new_cli_head(it);
-
-	for(live_irn = pset_first(live); live_irn; live_irn = pset_next(live))
-	{
-		/* test if node is max or min dominator*/
-		test_node = live_irn;
-		if (max_node == NULL)
-		{
-			max_node = test_node;
-			min_node = test_node;
-		}
-		else
-		{
-			test_int = value_dominates(test_node, max_node);
-			if (test_int == 1)
-			{
-				max_node = test_node;
-			}
-			test_int = value_dominates(min_node, test_node);
-			if (test_int == 1)
-			{
-				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;
-			}
-		}
-		if (!is_element){
-			element->irn = live_irn;
-			list_add(&element->list, &cli_head->list) ;
-		}
-	}
-	cli_head->min = min_node;
-	cli_head->max = max_node;
+	ptr_head_t *new_element = obstack_alloc(&ifg->obst, sizeof(*new_element));
+	INIT_LIST_HEAD(&new_element->list);
+	return new_element;
 }
 
-static void find_nodes(const void *self, void *iter)
+static void write_pointers(bitset_t *live, ifg_pointer_t *ifg)
 {
-	const ifg_clique_t *ifg	 = self;
-	cli_iter_t *it = iter;
-	cli_element_t *element = NULL;
-	cli_head_t *cli_head = get_first_cli_head(it);
-
-	assert((cli_head == NULL) && "There is no node to work on!");
+	ir_node      *live_irn;
+	bitset_pos_t  elm;
 
-	it->curr_cli_head = cli_head;
-	it->curr_cli_element = element;
+	bitset_foreach_irn(ifg->env->irg, live, elm, live_irn) {
+		ptr_head_t *head    = phase_get_or_set_irn_data(&ifg->ph, live_irn);
+		ptr_head_t *element = ptr_get_new_head(ifg);
 
-	element = list_entry(cli_head->list.next, cli_element_t, list);
-
-	inc_irg_visited(get_irn_irg(element->irn));
-	it->curr_irg_visited = get_irg_visited(get_irn_irg(element->irn));
-
-	return;
+		element->element = ifg->curr_element; /* write current highest sub-clique for each node */
+		list_add(&element->list, &head->list);
+	}
 }
 
-static ir_node *get_next_node(void *iter)
+static ptr_element_t *get_last_sub_clique(ifg_pointer_t *ifg, bitset_t *live, bitset_t *my_live, ir_node *irn)
 {
-	cli_iter_t *it = iter;
-	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;
+	ptr_element_t *element = ifg->curr_element;
+	ptr_element_t *res = NULL;
 
-	if (!(element == it->curr_cli_element))
+	/* search the last sub-clique before the sub-clique that contains the node irn */
+	if (element && element->kind == 8888
+		&& (element->content_first.irn == irn
+		|| element->content_second.irn == irn)) /* contains the node we search and there is no other sub-clique before */
 	{
-		irn = element->irn;
-		element = list_entry(cli_head->list.next, cli_element_t, list);
-		it->curr_cli_element = element;
+		if (bitset_is_set(live, get_irn_idx(element->content_first.irn)) && element->content_first.irn != irn) /* irn is still alive and not the node we search a sub-clique for */
+		{
+			bitset_set(my_live, get_irn_idx(element->content_first.irn));
+		}
+
+		if (bitset_is_set(live, get_irn_idx(element->content_second.irn))&& element->content_second.irn != irn) /* irn is still alive and not the node we search a sub-clique for */
+		{
+			bitset_set(my_live, get_irn_idx(element->content_second.irn));
+		}
+		res = NULL;
 	}
 	else
 	{
-		cli_head = it->curr_cli_head;
-		if (!(cli_head->next_cli_head == NULL))
+		if (element && element->kind == 8889)
+		{ /* this was a "single-node-clique" */
+			res = NULL;
+		}
+
+		if (element && (element->kind == 3101)
+			&& (element->content_second.irn == irn)) /* sub-clique contains node, return previous sub-clique */
 		{
-			irn = element->irn;
-			cli_head = cli_head->next_cli_head;
-			it->curr_cli_head = cli_head;
-			element = list_entry(cli_head->list.next, cli_element_t, list);
-			it->curr_cli_element = element;
+			res = element->content_first.element;
 		}
 		else
 		{
-			return NULL;
+			if (element && element->kind == 3101) /* look at previous sub-cliques if the contain the node you are searching for*/
+			{
+				if (bitset_is_set(live, get_irn_idx(element->content_second.irn))) /* irn is still alive */
+				{
+					bitset_set(my_live, get_irn_idx(element->content_second.irn));
+				}
+				ifg->curr_element = element->content_first.element;
+				res = get_last_sub_clique(ifg, live, my_live, irn);
+			}
+			else
+			{
+				res = NULL;
+			}
 		}
 	}
-
-	if (irn_visited == it->curr_irg_visited)
-	{
-		irn = get_next_node(it);
-	}
-
-	set_irn_visited(irn, it->curr_irg_visited);
-	return irn;
+	return res;
 }
 
 static void find_neighbour_walker(ir_node *bl, void *data)
 {
-	cli_iter_t *it          = data;
-	struct list_head *head  = get_block_border_head(it->ifg->env, bl);
-	border_t *b;
-	int was_def = 0;
-
-	pset *live = put_live_in(bl, pset_new_ptr_default());
+	ifg_pointer_t    *ifg      = data;
+	struct list_head *head     = get_block_border_head(ifg->env, bl);
+	int              was_def   = 0;
+	int              was_first = 0;
+	ir_node          *first    = NULL;
+	bitset_t         *live     = bitset_malloc(get_irg_last_idx(ifg->env->irg));
+	bitset_t         *my_live;
+	bitset_pos_t     my_elm;
+	border_t         *b;
+	ir_node          *my_irn;
+	element_content  last_irn;
+	element_content  last_element;
+
+	last_irn.irn         = NULL;
+	last_element.element = NULL;
 
 	assert(is_Block(bl) && "There is no block to work on.");
 
-	list_for_each_entry_reverse(border_t, b, head, list)
+	foreach_border_head(head, b) /* follow the borders of the block */
 	{
-		ir_node *irn = b->irn;
+		ir_node       *irn     = b->irn;
+		ptr_element_t *element = NULL;
 
-		if (!(pset_find_ptr(live, irn)) && (b->is_def))
+		if (b->is_def) /* b is a new node */
 		{
-			pset_insert_ptr(live, irn);
+			bitset_set(live, get_irn_idx(irn));
+			if (last_element.element)
+			{
+				element = ptr_get_new_element(ifg);
+				element->content_first.element = last_element.element;
+				element->content_second.irn = b->irn;
+				element->kind = 3101; /* first is an element, second an ir_node */
+
+				last_element.element = element;
+				ifg->curr_element = element;
+			}
+			else
+			{
+				if (last_irn.irn)	/* create new sub-clique */
+				{
+					element = ptr_get_new_element(ifg);
+					element->content_first.irn = last_irn.irn;
+					element->content_second.irn = b->irn;
+					element->kind = 8888; /* both are ir_nodes */
+
+					last_element.element = element;
+					ifg->curr_element    = element;
+					last_irn.irn         = NULL;
+				}
+				else
+				{
+					last_irn.irn = b->irn;	/* needed to create first sub-clique */
+					last_element.element = NULL;
+				}
+			}
+
 			was_def = 1;
 		}
-
-		else if (!(b->is_def) && (was_def == 1))
+		else
 		{
-			if (was_def == 1)
+			if (was_def == 1) /* if there is a USE after a DEF... */
 			{
-				write_clique(live, it);
+				if (!last_element.element)
+				{ /* there was only one element in the clique */
+					element = ptr_get_new_element(ifg);
+					element->kind = 8889; /* first is a node, second is NULL, because this is a "single-node-clique" */
+					element->content_first.irn = last_irn.irn;
+					last_irn.irn = NULL;
+					element = NULL;
+					ifg->curr_element = NULL;
+				}
+
+
+				write_pointers(live, ifg); /* ...write a pointer to the highest sub-clique for each living node. */
 				was_def = 0;
 			}
-			pset_remove_ptr(live, irn);
+
+			my_live = bitset_malloc(get_irg_last_idx(ifg->env->irg));
+			last_element.element = get_last_sub_clique(ifg, live, my_live, irn);
+
+			/* check and add still living nodes */
+			if (bitset_popcnt(my_live) > 1)
+			{
+				if (last_element.element)
+				{
+					bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
+					{
+						ptr_element_t *my_element = ptr_get_new_element(ifg);
+						my_element->content_first.element = last_element.element;
+						my_element->content_second.irn = my_irn;
+						my_element->kind = 3101; /* first is an element, second an ir_node */
+
+						last_element.element = my_element;
+						ifg->curr_element = my_element;
+					}
+				}
+				else
+				{
+					bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
+					{
+						ptr_element_t *my_element = NULL;
+						if (!first && !was_first)
+						{
+							first = my_irn;
+							was_first = 1;
+						}
+						else
+						{
+							if (first && was_first)
+							{
+								my_element = ptr_get_new_element(ifg);
+								my_element->content_first.irn = first;
+								my_element->content_second.irn = my_irn;
+								my_element->kind = 8888; /* both are ir_nodes */
+								last_element.element = my_element;
+								ifg->curr_element = my_element;
+								first = NULL;
+							}
+							else
+							{
+								my_element = ptr_get_new_element(ifg);
+								my_element->content_first.element = last_element.element;
+								my_element->content_second.irn = my_irn;
+								my_element->kind = 3101; /* first is an element, second an ir_node */
+								last_element.element = my_element;
+								ifg->curr_element = my_element;
+							}
+						}
+					}
+					was_first = 0;
+				}
+			}
+			else
+			{
+				if (bitset_popcnt(my_live) == 1) /* there is only one node left */
+				{
+					if (last_element.element)
+					{
+						bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
+						{
+							ptr_element_t *my_element = ptr_get_new_element(ifg);
+							my_element->content_first.element = last_element.element;
+							my_element->content_second.irn = my_irn;
+							my_element->kind = 3101; /* first is an element, second an ir_node */
+
+							last_element.element = my_element;
+							ifg->curr_element = my_element;
+						}
+					}
+					else
+					{
+						bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn);
+						{
+							ptr_element_t *my_element = ptr_get_new_element(ifg);
+							my_element->content_first.irn = my_irn;
+							my_element->content_second.irn = NULL;
+							my_element->kind = 8889;
+							last_element.element =  my_element;
+							ifg->curr_element = my_element;
+						}
+					}
+				}
+			}
+			bitset_free(my_live);
+			bitset_remv_irn(live, irn);
 		}
 	}
-	del_pset(live);
+	bitset_free(live);
 }
 
-static ifg_clique_t *build_neighbours(const be_chordal_env_t *env)
+static ir_node *get_first_irn(const ifg_pointer_t *ifg, ptr_iter_t *it)
 {
-	ifg_clique_t *ifg = NULL;
-	cli_iter_t *it = NULL;
+	ir_node *irn = phase_get_first_node(&ifg->ph);
 
-	it->ifg       			= ifg;
-	it->curr_cli_head 		= NULL;
-	it->curr_cli_element 	= NULL;
-	it->curr_irg_visited 	= get_irg_visited(env->irg);
+	if (! irn)
+		return NULL;
 
-	obstack_init(&it->ifg->obst);
-	dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, it);
+	it->curr_irn = irn;
 
-	return ifg;
+	return irn;
 }
 
-static void find_first_neighbour(const void *self, void *iter, const ir_node *irn)
+static ir_node *get_next_irn(ptr_iter_t *it)
 {
-	const ifg_clique_t *ifg = self;
-	cli_iter_t *it = iter;
+	ir_node *irn = phase_get_next_node(&it->ifg->ph, it->curr_irn);
 
-	cli_head_t *cli_head = ifg->cli_root;
-	cli_element_t *element;
+	if (! irn)
+		return NULL;
 
-	int is_dominated_by_max = 0;
-	int dominates_min = 0;
+	it->curr_irn = irn;
 
-	assert(!cli_head && "There is no root entry for a cli_head.");
+	return irn;
+}
+
+static ir_node *get_next_neighbour(ptr_iter_t *it)
+{
+	ir_node       *res;
+	ptr_head_t    *head;
+	ptr_element_t *element;
 
-	while(!(cli_head->next_cli_head == NULL))
+	element = it->curr_element_t;
+
+	if (element == NULL)
 	{
-		is_dominated_by_max = value_dominates(cli_head->max, irn);
-		dominates_min = value_dominates(irn, cli_head->min);
+		if (it->curr_ptr_head->list.next != &it->first_head->list)
+		{
+			head = list_entry(it->curr_ptr_head->list.next, ptr_head_t, list);
+			it->curr_ptr_head = head;
+			element = head->element;
+		}
+		else
+			return NULL; /* there are no more neighbours */
+	}
 
-		if ((is_dominated_by_max && dominates_min) /* node is in clique */
-				|| (irn == cli_head->max)
-				|| (irn == cli_head->min))
+	if (element && element->kind == 8889) /* node has no neighbours */
+	{
+		res = element->content_first.irn;
+		it->curr_element_t = NULL;
+	}
+	else
+	{
+		if (element && element->kind == 8888) /* node has only one more neighbour */
+		{
+			if (it->get_first)
+			{
+				if (element->content_first.irn != it->irn)
+				{
+					res = element->content_first.irn;
+					it->get_first = 0;
+					it->curr_element_t = NULL;
+				}
+				else
+				{
+					it->get_first = 0;
+					it->curr_element_t = NULL;
+					it->sub_call++;
+					res = get_next_neighbour(it);
+					it->sub_call--;
+				}
+			}
+			else
+			{
+				if (element->content_second.irn != it->irn)
+				{
+					res = element->content_second.irn;
+					it->get_first = 1;
+					it->curr_element_t = element;
+				}
+				else
+				{
+					it->get_first = 1;
+					it->curr_element_t = element;
+					it->sub_call++;
+					res = get_next_neighbour(it);
+					it->sub_call--;
+				}
+			}
+		}
+		else
 		{
-			element = list_entry(cli_head->list.next, cli_element_t, list);
+			if (element && element->kind == 3101)
+			{
+				it->curr_element_t = element->content_first.element;
+				res = element->content_second.irn;
+			}
+			else
+			{ /* element is only an ir_node */// TODO
+				it->curr_element_t = NULL;
+				return NULL;
+			}
+		}
+	}
 
-			it->curr_cli_element = element;
-			it->curr_cli_head = cli_head;
-			break;
+	if (res && !it->sub_call)
+	{
+		if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
+		{
+			res = get_next_neighbour(it);
 		}
 		else
 		{
-			cli_head = cli_head->next_cli_head;
+			bitset_set(it->visited_neighbours, get_irn_idx(res));
 		}
 	}
-	it->curr_irn = irn;
 
-	inc_irg_visited(get_irn_irg(irn));
-	it->curr_irg_visited = get_irg_visited(get_irn_irg(irn));
-	return;
+	return res;
 }
 
-static ir_node *get_next_neighbour(cli_iter_t *it)
+static ir_node *get_first_neighbour(const ifg_pointer_t *ifg, ptr_iter_t *it, const ir_node *irn)
 {
-	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;
+	ir_node       *res;
+	ptr_head_t    *head;
+	ptr_element_t *element;
+	bitset_t      *bitsetvisited_neighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
 
-	res = it->curr_cli_element->irn;
+	it->ifg       = ifg;
+	it->irn       = irn;
+	it->get_first = 0;
+	it->sub_call  = 0;
 
-	/* get next element */
+	it->visited_neighbours = bitsetvisited_neighbours;
 
-	element = list_entry(it->curr_cli_element->list.next, cli_element_t, list);
-	irn_visited = get_irn_visited(element->irn);
+	head = phase_get_irn_data(&ifg->ph, irn);
+	if (! head)
+		return NULL;
+	else
+	{
+		it->first_head = head;
+		head = list_entry(it->first_head->list.next, ptr_head_t, list); /* because first element is NULL */
+		it->curr_ptr_head = head;
+		element = head->element;
+	}
 
-	if ((cli_head_t *)element == it->curr_cli_head) /* end of clique, search next one */
+	if (element && element->kind == 8889) /* node has no neighbours */
 	{
-		cli_head = cli_head->next_cli_head;
-		while(!(cli_head->next_cli_head == NULL))
+		res = element->content_first.irn;
+		it->curr_element_t = NULL;
+	}
+	else
+	{
+		if (element && element->kind == 8888) /* node has only one neighbour */
 		{
-			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))
+			if (it->get_first)
 			{
-				element = list_entry(cli_head->list.next, cli_element_t, list);
-
-				it->curr_cli_element = element;
-				it->curr_cli_head = cli_head;
-				break;
+				if (element->content_first.irn != it->irn)
+				{
+					res = element->content_first.irn;
+					it->get_first = 0;
+					it->curr_element_t = NULL;
+				}
+				else
+				{
+					it->get_first = 0;
+					it->curr_element_t = NULL;
+					it->sub_call++;
+					res = get_next_neighbour(it);
+					it->sub_call--;
+				}
 			}
 			else
 			{
-				cli_head = cli_head->next_cli_head;
+				if (element->content_second.irn != it->irn)
+				{
+					res = element->content_second.irn;
+					it->curr_element_t = element;
+					it->get_first = 1;
+				}
+				else
+				{
+					it->get_first = 1;
+					it->curr_element_t = element;
+					it->sub_call++;
+					res = get_next_neighbour(it);
+					it->sub_call--;
+				}
 			}
 		}
-	}
-	else /* get next element of this clique */
-	{
-		it->curr_cli_element = element;
+		else
+			if (element && element->kind == 3101)
+			{
+				it->curr_element_t = element->content_first.element;
+				res = element->content_second.irn;
+			}
+			else
+			{ /* element is only an ir_node */
+				it->curr_element_t = NULL;
+				return NULL;
+			}
 	}
 
-	if (irn_visited == it->curr_irg_visited)
+	if (res && !it->sub_call)
 	{
-		irn = get_next_neighbour(it);
+		if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
+		{
+			res = get_next_neighbour(it);
+		}
+		else
+		{
+			bitset_set(it->visited_neighbours, get_irn_idx(res));
+		}
 	}
 
-	set_irn_visited(res, it->curr_irg_visited);
-
 	return res;
 }
 
 
+
 /* PUBLIC FUNCTIONS */
 
 static void ifg_pointer_free(void *self)
 {
-	ifg_clique_t *ifg = self;
+	ifg_pointer_t *ifg = self;
+	obstack_free(&ifg->obst, NULL);
+	phase_free(&ifg->ph);
 
 	free(self);
 }
 
 static int ifg_pointer_connected(const void *self, const ir_node *a, const ir_node *b)
 {
-	cli_iter_t *it = NULL;
-	int connected = -1;
-	ir_node *irn = NULL;
+	const ifg_pointer_t *ifg = self;
+	int                 connected = -1;
+	ptr_iter_t          it;
+	ir_node             *irn = NULL;
 
-	find_first_neighbour(self, it, a);
+	irn       = get_first_neighbour(ifg, &it, a);
 	connected = 0;
-	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;
@@ -387,56 +599,60 @@ static int ifg_pointer_connected(const void *self, const ir_node *a, const ir_no
 
 static ir_node *ifg_pointer_neighbours_begin(const void *self, void *iter, const ir_node *irn)
 {
-	find_first_neighbour(self, iter, irn);
-	return get_next_neighbour(iter);
+	return get_first_neighbour(self, iter, irn);
 }
 
 static ir_node *ifg_pointer_neighbours_next(const void *self, void *iter)
 {
+	(void) self;
 	return get_next_neighbour(iter);
 }
 
 static void ifg_pointer_neighbours_break(const void *self, void *iter)
 {
-	return;
+	ptr_iter_t *it = iter;
+	(void) self;
+
+	bitset_free(it->visited_neighbours);
 }
 
 static ir_node *ifg_pointer_nodes_begin(const void *self, void *iter)
 {
-	find_nodes(self, iter);
-	return get_next_node(iter);
+	return get_first_irn(self, iter);
 }
 
 static ir_node *ifg_pointer_nodes_next(const void *self, void *iter)
 {
-	return get_next_node(iter);
+	(void) self;
+	return get_next_irn(iter);
 }
 
 static void ifg_pointer_nodes_break(const void *self, void *iter)
 {
+	(void) self;
+	(void) iter;
 	return;
 }
 
 static int ifg_pointer_degree(const void *self, const ir_node *irn)
 {
 	int degree = -1;
-	cli_iter_t *it = NULL;
+	ptr_iter_t it;
 
-	find_first_neighbour(self, it, irn);
+	irn = get_first_neighbour(self, &it, irn);
 	degree = 0;
-	irn = get_next_neighbour(it);
 	while (irn != NULL)
 	{
 		degree++;
-		irn = get_next_neighbour(it);
+		irn = get_next_neighbour(&it);
 	}
 
 	return degree;
 }
 
 static const be_ifg_impl_t ifg_pointer_impl = {
-	sizeof(cli_iter_t),
-	0,
+	sizeof(ptr_iter_t),
+	sizeof(ptr_iter_t),
 	0,
 	ifg_pointer_free,
 	ifg_pointer_connected,
@@ -454,15 +670,15 @@ static const be_ifg_impl_t ifg_pointer_impl = {
 
 be_ifg_t *be_ifg_pointer_new(const be_chordal_env_t *env)
 {
-	ifg_pointer_t *ifg	= malloc(sizeof(*ifg));
+	ifg_pointer_t *ifg	= xmalloc(sizeof(*ifg));
 	ifg->impl     		= &ifg_pointer_impl;
+	ifg->env			= env;
 
-	ifg->cli_root		= NULL;
-	ifg->env		 	= env;
+	phase_init(&ifg->ph, "ptr_map", env->irg, PHASE_DEFAULT_GROWTH, ptr_irn_data_init, NULL);
+	obstack_init(&ifg->obst);
 
-	ifg = build_neighbours(env);
+	dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
 
+	obstack_finish(&ifg->obst);
 	return (be_ifg_t *) ifg;
 }
-
-#endif