-/**
- * @file beifg_list.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 List based implementation of chordal interference graphs.
+ * @author Sebastian Hack
+ * @date 18.11.2005
+ * @version $Id$
*/
-#ifdef HAVE_CONFIG_H
#include "config.h"
-#endif
#include <stdlib.h>
-#include "belive_t.h"
#include "list.h"
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irgwalk.h"
-#include "benodesets.h"
+#include "bearch_t.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_ifg_impl_t *impl;
const be_chordal_env_t *env;
- struct obstack obst;
- pmap *list_map;
+ struct obstack obst;
+ 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;
+};
+
+struct _adj_head_t {
+ ir_node *irn; /* the node you search neighbours for */
+ adj_element_t *first_adj_element;
+ int degree;
+};
-typedef struct _adj_head_t {
- struct list_head list;
- struct list_head *next_adj_head;
- ir_node *irn;
- 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)
+/* add node to the array of all nodes in this ifg implementation, if the node isn't already in the ifg */
+static void create_node(ifg_list_t *ifg, ir_node *irn)
{
- 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;
- INIT_LIST_HEAD(&adj_head->list);
- pmap_insert(ifg->list_map, irn, adj_head);
+ adj_head->first_adj_element = NULL;
+ adj_head->degree = 0;
+ 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 */
+/* write the information about the edge between a and b */
+static void add_edge(ifg_list_t *ifg, ir_node *node_a, ir_node *node_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;
+ /* do the same vice versa */
+ adj_head = ifg->adj_heads[node_b->node_idx];
- return;
-}
+ assert (adj_head && "There is no entry for node a");
+ curr_element = adj_head->first_adj_element;
-static ir_node *get_next_node(adj_iter_t *it)
-{
- adj_head_t *adj_head;
-
- 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 */
+/* find all adjacent nodes in the irg */
+static void find_neighbour_walker(ir_node *bl, void *data)
{
- 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;
+ ifg_list_t *ifg = data;
+ struct list_head *head = get_block_border_head(ifg->env, bl);
+ ir_nodeset_t live;
+ ir_node *live_irn = NULL;
+ border_t *b = NULL;
+
+ ir_nodeset_init(&live);
- 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);
- 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_def)
+ {
+ create_node(ifg, b->irn); /* add the node to the array of all nodes of this ifg implementation */
+ ir_nodeset_insert(&live, b->irn);
+ if (b->is_real) /* this is a new node */
+ {
+ ir_nodeset_iterator_t iter;
+
+ foreach_ir_nodeset(&live, live_irn, iter)
+ {
+ 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... */
- nodeset_remove(live, b->irn);
+ else /* b->irn is now dead */
+ {
+ ir_nodeset_remove(&live, b->irn);
}
}
- if (delete_nodeset)
- del_nodeset(live);
-}
+ ir_nodeset_destroy(&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;
+}
- it->curr_list_element = element;
+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;
+
+ 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;
+ const ifg_list_t *ifg = self;
+ 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);
+ (void) self;
+ 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;
+ (void) self;
+ 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);
+ (void) self;
+ 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;
+ (void) self;
+ 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 = ifg->adj_heads[irn->node_idx];
- adj_head = pmap_get(ifg->list_map, (void *) irn);
- assert(!adj_head && "There is no entry for this node.");
+ 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,
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(ifg_list_t);
+ adj_head_t **adj_heads_array = XMALLOCNZ(adj_head_t*, env->irg->last_node_idx);
+
+ ifg->impl = &ifg_list_impl;
+ ifg->env = env;
+
+ 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;
projects / libfirm / blobdiff