X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeifg_list.c;h=50ca476e0324d163aaac7a5beba2c1602ca80613;hb=cbfbedae75798a9830fb0ef090189345ede85dc8;hp=3ff05922ec417b693173868aa770fdc8fdbdae69;hpb=6bad23167725caf75b971f8fe605f255153b709a;p=libfirm

diff --git a/ir/be/beifg_list.c b/ir/be/beifg_list.c
index 3ff05922e..50ca476e0 100644
--- a/ir/be/beifg_list.c
+++ b/ir/be/beifg_list.c
@@ -6,339 +6,384 @@
  * Copyright (C) 2005 Universitaet Karlsruhe
  * Released under the GPL
  */
+
 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #endif
 
 #include <stdlib.h>
 
-#include "belive_t.h"
+#include "benodesets.h"
 #include "list.h"
 
 #include "irnode_t.h"
 #include "irgraph_t.h"
 #include "irgwalk.h"
-#include "benodesets.h"
 
 #include "be_t.h"
 #include "bera.h"
 #include "beifg_t.h"
 #include "bechordal_t.h"
 
-#define MAX(x, y) ((x) > (y) ? (x) : (y))
+
+typedef struct _adj_head_t adj_head_t;
 
 typedef struct _ifg_list_t {
 	const be_ifg_impl_t *impl;
 	const be_chordal_env_t *env;
 	struct obstack obst;
-	pmap *list_map;
+	adj_head_t **adj_heads;
 } ifg_list_t;
 
-typedef struct _list_element_t {
-	struct list_head list;
-	ir_node *irn;
-} list_element_t;
+typedef struct _adj_element_t adj_element_t;
+
+struct _adj_element_t {
+	adj_element_t *next_adj_element;
+	ir_node *neighbour;
+};
 
-typedef struct _adj_head_t {
-	struct list_head list;
-	struct list_head *next_adj_head;
-	ir_node *irn;
+struct _adj_head_t {
+	ir_node *irn; /* the node you search neighbours for */
+	adj_element_t *first_adj_element;
 	int degree;
-} adj_head_t;
+};
+
+typedef struct _nodes_iter_t {
+	const ifg_list_t *ifg;
+	unsigned int curr_node_idx;
+} nodes_iter_t;
 
 typedef struct _adj_iter_t {
-	ifg_list_t *ifg;
-	ir_node *irn;
-	adj_head_t *curr_adj_head;
-	list_element_t *curr_list_element;
-	pmap_entry *entry;
+	const ifg_list_t *ifg;
+	adj_element_t *curr_adj_element;
 } adj_iter_t;
 
 /* PRIVATE FUNCTIONS */
 
-static adj_head_t *get_or_set_adj_head(ifg_list_t *ifg, ir_node *irn)
+static void create_node (ifg_list_t *ifg, ir_node *irn) /* add node to the array of all nodes in this ifg implementation, if the node isn't already in the ifg */
 {
-	adj_head_t *adj_head;
+	adj_head_t *adj_head = NULL;
 
-	adj_head = pmap_get(ifg->list_map, irn);
-	if(!adj_head){
+	adj_head = ifg->adj_heads[irn->node_idx];
+	if (!adj_head)
+	{
 		adj_head = obstack_alloc(&ifg->obst, sizeof(*adj_head));
 		adj_head->irn = irn;
+		adj_head->first_adj_element = NULL;
 		adj_head->degree = 0;
-		INIT_LIST_HEAD(&adj_head->list);
-		pmap_insert(ifg->list_map, irn, adj_head);
+		ifg->adj_heads[irn->node_idx] = adj_head;
 	}
-
-	return adj_head;
 }
 
-static list_element_t *get_new_list_element(ifg_list_t *ifg, ir_node *irn)
+static adj_element_t *create_adj_element(ifg_list_t *ifg, ir_node *irn)
 {
-	list_element_t *element;
+	adj_element_t *element = NULL;
 
 	element = obstack_alloc(&ifg->obst, sizeof(*element));
-	element->irn = irn;
-	INIT_LIST_HEAD(&element->list);
+	element->next_adj_element = NULL;
+	element->neighbour = irn;
 
 	return element;
 }
 
-static void add_edge(ifg_list_t *ifg, ir_node *a, ir_node *b) /* add node B as a neighbour to A and vice versa */
+static void add_edge(ifg_list_t *ifg, ir_node *node_a, ir_node *node_b) /* write the information about the edge between a and b */
 {
-	adj_head_t *adj_head;
-	list_element_t *new_element;
-	list_element_t *element;
-	int is_element = 0;
-
-	adj_head = get_or_set_adj_head(ifg, a);
-	list_for_each_entry(list_element_t, element, &adj_head->list, list){
-		if(element->irn == b){
-			is_element = 1;
-			break;
+	adj_head_t *adj_head = NULL;
+	adj_element_t *curr_element = NULL;
+	adj_element_t *new_element = NULL;
+
+	adj_head = ifg->adj_heads[node_a->node_idx]; /* find the neighbours list of a */
+
+	assert (adj_head && "There is no entry for node a");
+	curr_element = adj_head->first_adj_element;
+
+	if (curr_element)
+	{
+		while (curr_element->neighbour != node_b && curr_element->next_adj_element)
+		{
+			curr_element = curr_element->next_adj_element;
 		}
-	}
-	if (!is_element){ /* if B is not yet a neighbour of A add the node to A's neighbours */
-		new_element = get_new_list_element(ifg, b);
-		adj_head->degree++;
-		list_add(&new_element->list, &adj_head->list) ;
-	}
 
-	adj_head = get_or_set_adj_head(ifg, b);
-	is_element = 0;
-	list_for_each_entry(list_element_t, element, &adj_head->list, list){
-		if(element->irn == a){
-			is_element = 1;
+		if (curr_element->neighbour != node_b && curr_element->next_adj_element == NULL)
+		{
+			adj_head->degree++;
+			new_element = create_adj_element(ifg, node_b); /* if b isn't in list, add b */
+			curr_element->next_adj_element = new_element;
 		}
 	}
-	if (!is_element){ /* if A is not yet a neighbour of B add the node to B's neighbours */
-		new_element = get_new_list_element(ifg, a);
+	else
+	{
 		adj_head->degree++;
-		list_add(&new_element->list, &adj_head->list);
+		new_element = create_adj_element(ifg, node_b); /* a has no neighbours, add b as the first one*/
+		adj_head->first_adj_element = new_element;
 	}
-}
-
-static void find_nodes(const ifg_list_t *ifg, adj_iter_t *it)
-{
-	pmap_entry *entry;
-	entry = pmap_first(ifg->list_map); /* find the first node */
-	it->ifg = ifg;
-	it->ifg->list_map = ifg->list_map;
-	it->entry = entry;
-	it->curr_adj_head = entry->value;
 
-	return;
-}
+	/* do the same vice versa */
+	adj_head = ifg->adj_heads[node_b->node_idx];
 
-static ir_node *get_next_node(adj_iter_t *it)
-{
-	adj_head_t *adj_head;
+	assert (adj_head && "There is no entry for node a");
+	curr_element = adj_head->first_adj_element;
 
-	pmap_entry *entry;
-	ir_node *irn;
+	if (curr_element)
+	{
+		while (curr_element->neighbour != node_a && curr_element->next_adj_element)
+		{
+			curr_element = curr_element->next_adj_element;
+		}
 
-	if (it->curr_adj_head == NULL)
-		return NULL;
+		if (curr_element->neighbour != node_a && curr_element->next_adj_element == NULL)
+		{
+			adj_head->degree++;
+			new_element = create_adj_element(ifg, node_a);
+			curr_element->next_adj_element = new_element;
+		}
+	}
 	else
 	{
-		adj_head = it->curr_adj_head;
-		irn = adj_head->irn; /* return the last found node */
-		entry = it->entry;
-		it->irn = irn;
-		it->entry = pmap_next(it->ifg->list_map); /*find the next node */
-		if (it->entry != NULL)
-			it->curr_adj_head = it->entry->value;
-		else
-			it->curr_adj_head = NULL;
+		adj_head->degree++;
+		new_element = create_adj_element(ifg, node_a);
+		adj_head->first_adj_element = new_element;
 	}
-  return irn;
 }
 
-static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in one given block */
+static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in the irg */
 {
 	ifg_list_t *ifg = data;
 	struct list_head *head  = get_block_border_head(ifg->env, bl);
-	border_t *b;
-	int delete_nodeset = 0;
+
 	nodeset *live = new_nodeset(ifg->env->cls->n_regs);
-	ir_node *live_irn;
-	adj_head_t *adj_head;
+	ir_node *live_irn = NULL;
+	border_t *b = NULL;
 
-	assert(is_Block(bl) && "There is no block to work on.");
+	assert (is_Block(bl) && "There is no block to work on");
 
-	foreach_border_head(head, b) /* follow the borders of the block */
+	foreach_border_head(head, b) /* follow the borders of each block */
 	{
-		//if(get_irn_node_nr(b->irn) == 2049)
-		//	printf("Hallo");
-		if (b->is_def) {
-			adj_head = get_or_set_adj_head(ifg, b->irn);
+		if (b->is_def)
+		{
+			create_node(ifg, b->irn); /* add the node to the array of all nodes of this ifg implementation */
 			nodeset_insert(live, b->irn);
-//			if (b->is_real) /* b is a new node */ {
-				foreach_nodeset(live, live_irn) {
-					if (b->irn != live_irn) /* add b as a neighbour to each previous found adjacent node */
+			if (b->is_real) /* this is a new node */
+			{
+				foreach_nodeset(live, live_irn)
+				{
+					if (b->irn != live_irn) /* add a as a neighbour to b and vice versa */
 						add_edge(ifg, b->irn, live_irn);
-//				}
+				}
 			}
 		}
-
-		else {
-			if (nodeset_find(live,b->irn)) /* b is used, deleting... */
+		else /* b->irn is now dead */
+		{
+			if (nodeset_find(live, b->irn))
 				nodeset_remove(live, b->irn);
 		}
 	}
-	if (delete_nodeset)
+
+	if (live)
 		del_nodeset(live);
 }
 
-
-static void find_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *irn)
+static ir_node *get_first_node(const ifg_list_t *ifg, nodes_iter_t *it)
 {
-	ir_node *node = (void *) irn;
-	list_element_t *element;
-	adj_head_t *adj_head = pmap_get(ifg->list_map, node);
+	ir_node *res = NULL;
+	adj_head_t *adj_head= NULL;
+	int curr_idx = -1;
 
-	assert(adj_head && "There is no entry for this node.");
+	it->ifg = ifg;
+	it->curr_node_idx = 0;
 
-	if (adj_head->list.next == &adj_head->list)
+	while (adj_head == NULL)
 	{
-		/* element has no neighbours */
-		it->irn = NULL;
-		it->curr_adj_head = adj_head;
-		it->curr_list_element = NULL;
-		return;
+		curr_idx++;
+		adj_head = ifg->adj_heads[curr_idx];
 	}
 
-	element = list_entry(adj_head->list.next, list_element_t, list); /* get the first neighbour of the given node irn */
-
-	it->curr_list_element = element;
-	it->curr_adj_head = adj_head;
-	it->irn = element->irn;
+	if (adj_head == NULL) /* there are no nodes in this ifg */
+		return NULL;
+	else
+	{
+		res = adj_head->irn;
+		it->curr_node_idx = curr_idx;
+	}
 
-	return;
+	return res;
 }
 
-static ir_node *get_next_neighbour(adj_iter_t *it)
+static ir_node *get_next_node(nodes_iter_t *it)
 {
-	ir_node *res;
-	list_element_t *element;
-	adj_head_t *adj_head = it->curr_adj_head;
+	const ifg_list_t *ifg = it->ifg;
+	ir_node *res = NULL;
+	adj_head_t *adj_head= NULL;
+	unsigned int curr_idx = it->curr_node_idx;
 
-	if(it->irn != NULL) /* return the previous found neighbour */
-		res = it->irn;
-	else
+	while (adj_head == NULL && curr_idx < it->ifg->env->irg->last_node_idx - 1)
 	{
-		if(it->curr_list_element != NULL)
-		{
-			res = it->curr_list_element->irn; /* was last element */
-			it ->curr_list_element = NULL;
-			return res;
-		}
-		else
-			return NULL;
+		curr_idx++;
+		adj_head = ifg->adj_heads[curr_idx];
 	}
 
-	element = list_entry(it->curr_list_element->list.next, list_element_t, list); /* find the next neighbour */
-	if (element->list.next == &it->curr_list_element->list) /* single element (only one neighbour) */
+	if (adj_head == NULL) /* there are no more nodes in this ifg */
+		return NULL;
+	else
 	{
-		it->irn = NULL;
-		it->curr_list_element = NULL;
-		return res;
+		res = adj_head->irn;
+		it->curr_node_idx = curr_idx;
 	}
 
-	if(element->list.next == &adj_head->list) /* reaching end of list */
-		it->irn = NULL;
-	else
-		it->irn = element->irn;
+	return res;
+}
+
+static ir_node *get_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *curr_irn)
+{
+	ir_node *res = NULL;
+	adj_head_t *adj_head = NULL;
+
+	adj_head = ifg->adj_heads[curr_irn->node_idx];
+	assert (adj_head && "There is no entry for this node");
+
+	it->curr_adj_element = NULL;
+	it->ifg = ifg;
 
-	it->curr_list_element = element;
+	if (adj_head->first_adj_element) /* return first neighbour */
+	{
+		res = adj_head->first_adj_element->neighbour;
+		it->curr_adj_element = adj_head->first_adj_element;
+	}
+	else /* node has no neighbours */
+		return NULL;
 
 	return res;
 }
 
+static ir_node *get_next_neighbour(adj_iter_t *it)
+{
+	ir_node *res = NULL;
+	adj_element_t *element = it->curr_adj_element;
+
+	if (element->next_adj_element) /* return next neighbour */
+	{
+		res = element->next_adj_element->neighbour;
+		it->curr_adj_element = element->next_adj_element;
+	}
+	else /* was last neighbour */
+		return NULL;
+
+	return res;
+}
 
 /* PUBLIC FUNCTIONS */
+
 static void ifg_list_free(void *self)
 {
 	ifg_list_t *ifg = self;
 	obstack_free(&ifg->obst, NULL);
-	pmap_destroy(ifg->list_map);
-	free(self);
+	free(ifg->adj_heads);
+	free(ifg);
 }
 
 static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b)
 {
 	const ifg_list_t *ifg = self;
-	ir_node *node_a = (void *) a;
-	ir_node *node_b = (void *) b;
-	adj_head_t *adj_head;
-	list_element_t *element;
-	int is_element = 0;
+	int res = -1;
+	adj_head_t *adj_head = NULL;
+	adj_element_t *curr_element = NULL;
 
-	adj_head = pmap_get(ifg->list_map, node_a);
-	assert(adj_head && "There is no entry for the first node.");
+	/* first try: find b in the neigbours of a */
+	adj_head = ifg->adj_heads[a->node_idx];
 
-	//if (adj_head == NULL) /* node is not in this ifg */
-	//	return 1;
+	assert(adj_head && "There is no entry for the node a");
+	curr_element = adj_head->first_adj_element;
 
-	list_for_each_entry(list_element_t, element, &adj_head->list, list)
-		if(element->irn == b)
-			is_element = 1;
+	if(curr_element)
+	{
+		while (curr_element->neighbour != b && curr_element->next_adj_element)
+		{
+			curr_element = curr_element->next_adj_element;
+		}
+		if (curr_element->neighbour == b)
+			return 1;
+		else
+			res = 0;
+	}
+	else /* node a has no neighbours */
+		res = 0;
 
-	adj_head = pmap_get(ifg->list_map, node_b);
-	assert(adj_head && "There is no entry for the second node");
+	/* second try, this should not be necessary... only to check the solution */
+	adj_head = ifg->adj_heads[b->node_idx];
 
-	//if (adj_head == NULL) /* node is not in this ifg */
-	//	return 1;
+	assert(adj_head && "There is no entry for the node b");
+	curr_element = adj_head->first_adj_element;
 
-	list_for_each_entry(list_element_t, element, &adj_head->list, list)
-		if(element->irn == a)
-			is_element = 1;
+	if(curr_element)
+	{
+		while (curr_element->neighbour != a && curr_element->next_adj_element)
+		{
+			curr_element = curr_element->next_adj_element;
+		}
+		if (curr_element->neighbour == a)
+		{
+			assert ("Found the neighbour only in the second try.");
+			return 1;
+		}
+		else
+			res = 0;
+	}
+	else /* node b has no neighbours */
+		res = 0;
 
-	return is_element;
+	return res;
 }
 
-static ir_node *ifg_list_neighbours_begin(const void *self, adj_iter_t *it, const ir_node *irn)
+static ir_node *ifg_list_nodes_begin(const void *self, void *iter)
 {
-	find_first_neighbour(self, it, irn);
-	return get_next_neighbour(it);
+	nodes_iter_t *it = iter;
+	return get_first_node(self, it);
 }
 
-static ir_node *ifg_list_neighbours_next(const void *self, adj_iter_t *it)
+static ir_node *ifg_list_nodes_next(const void *self, void *iter)
 {
-	return get_next_neighbour(it);
+	return get_next_node(iter);
 }
 
-static void ifg_list_neighbours_break(const void *self, adj_iter_t *it)
+static void ifg_list_nodes_break(const void *self, void *iter)
 {
+	nodes_iter_t *it = iter;
+	it->curr_node_idx = 0;
+	it->ifg = NULL;
 }
 
-static ir_node *ifg_list_nodes_begin(const void *self, adj_iter_t *it)
+static ir_node *ifg_list_neighbours_begin(const void *self, void *iter,const ir_node *irn)
 {
-	find_nodes(self, it);
-	return get_next_node(it);
+	adj_iter_t *it = iter;
+	return get_first_neighbour(self, it, irn);
 }
 
-static ir_node *ifg_list_nodes_next(const void *self, adj_iter_t *it)
+static ir_node *ifg_list_neighbours_next(const void *self, void *iter)
 {
-	return get_next_node(it);
+	return get_next_neighbour(iter);
 }
 
-static void ifg_list_nodes_break(const void *self, adj_iter_t *it)
+static void ifg_list_neighbours_break(const void *self, void *iter)
 {
+	adj_iter_t *it= iter;
+	it->curr_adj_element = NULL;
+	it->ifg = NULL;
 }
 
 static int ifg_list_degree(const void *self, const ir_node *irn)
 {
 	const ifg_list_t *ifg = self;
-	adj_head_t *adj_head;
+	adj_head_t *adj_head = NULL;
 
-	adj_head = pmap_get(ifg->list_map, (void *) irn);
-	assert(adj_head && "There is no entry for this node.");
+	adj_head = ifg->adj_heads[irn->node_idx];
+
+	assert (adj_head && "There is no entry for this node");
 
 	return adj_head->degree;
 }
 
 static const be_ifg_impl_t ifg_list_impl = {
-	sizeof(adj_iter_t),
+	sizeof(nodes_iter_t),
 	sizeof(adj_iter_t),
 	0,
 	ifg_list_free,
@@ -357,14 +402,17 @@ static const be_ifg_impl_t ifg_list_impl = {
 
 be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
 {
-	ifg_list_t *ifg 	= xmalloc(sizeof(*ifg));
-	ifg->impl     		= &ifg_list_impl;
-	ifg->list_map 		= pmap_create();
-	ifg->env			= env;
+	ifg_list_t *ifg = xmalloc(sizeof(*ifg));
+	adj_head_t **adj_heads_array = xmalloc(env->irg->last_node_idx * sizeof(adj_heads_array[0]));
+
+	ifg->impl = &ifg_list_impl;
+	ifg->env  = env;
+
+	memset(adj_heads_array, 0, env->irg->last_node_idx * sizeof(adj_heads_array[0]));
+	ifg->adj_heads = adj_heads_array;
 
 	obstack_init(&ifg->obst);
 	dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
-
 	obstack_finish(&ifg->obst);
 
 	return (be_ifg_t *) ifg;