values may die at every use

[libfirm] / ir / be / beifg_list.c

diff --git a/ir/be/beifg_list.c b/ir/be/beifg_list.c
index e9b970d..f7c608b 100644 (file)
--- a/ir/be/beifg_list.c
+++ b/ir/be/beifg_list.c
@@ -27,11 +27,13 @@
 
 #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 {
@@ -39,33 +41,34 @@ typedef struct _list_element_t {
        ir_node *irn;
 } list_element_t;
 
-typedef struct _adj_head_t {
+struct _adj_head_t {
        struct list_head list;
        struct list_head *next_adj_head;
        ir_node *irn;
        int degree;
-} adj_head_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;
+       int curr_node_idx;
 } adj_iter_t;
 
 /* PRIVATE FUNCTIONS */
 
 static adj_head_t *get_or_set_adj_head(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);
+       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->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;
@@ -118,12 +121,19 @@ static void add_edge(ifg_list_t *ifg, ir_node *a, ir_node *b) /* add node B as a
 
 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 */
+       adj_head_t *adj_head = NULL;
+       int i = -1;
+
+       while(adj_head == NULL) /* find first adj_head */
+       {
+               i++;
+               adj_head = ifg->adj_heads[i];
+       }
+
        it->ifg = ifg;
-       it->ifg->list_map = ifg->list_map;
-       it->entry = entry;
-       it->curr_adj_head = entry->value;
+       it->ifg->adj_heads = ifg->adj_heads;
+       it->curr_adj_head = adj_head;
+       it->curr_node_idx = i;
 
        return;
 }
@@ -131,9 +141,8 @@ static void find_nodes(const ifg_list_t *ifg, adj_iter_t *it)
 static ir_node *get_next_node(adj_iter_t *it)
 {
        adj_head_t *adj_head;
-
-       pmap_entry *entry;
        ir_node *irn;
+       unsigned int node_idx = it->curr_node_idx;
 
        if (it->curr_adj_head == NULL)
                return NULL;
@@ -141,13 +150,24 @@ static ir_node *get_next_node(adj_iter_t *it)
        {
                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
+
+               adj_head = NULL;
+               while (adj_head == NULL && node_idx < it->ifg->env->irg->last_node_idx - 1)
+               {
+                       node_idx++;
+                       adj_head = it->ifg->adj_heads[node_idx];
+               }
+
+               it->curr_node_idx = node_idx;
+               it->curr_adj_head = adj_head;
+
+               if (!adj_head) /* was last node */
+               {
                        it->curr_adj_head = NULL;
+                       it->curr_node_idx = -1;
+               }
        }
   return irn;
 }
@@ -191,9 +211,8 @@ static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent
 
 static void find_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *irn)
 {
-       ir_node *node = (void *) irn;
        list_element_t *element;
-       adj_head_t *adj_head = pmap_get(ifg->list_map, node);
+       adj_head_t *adj_head = ifg->adj_heads[irn->node_idx];
 
        assert(adj_head && "There is no entry for this node.");
 
@@ -259,7 +278,7 @@ static void ifg_list_free(void *self)
 {
        ifg_list_t *ifg = self;
        obstack_free(&ifg->obst, NULL);
-       pmap_destroy(ifg->list_map);
+       free(ifg->adj_heads);
        free(self);
 }
 
@@ -272,7 +291,7 @@ static int ifg_list_connected(const void *self, const ir_node *a, const ir_node
        list_element_t *element;
        int is_element = 0;
 
-       adj_head = pmap_get(ifg->list_map, node_a);
+       adj_head = ifg->adj_heads[node_a->node_idx];
        assert(adj_head && "There is no entry for the first node.");
 
        //if (adj_head == NULL) /* node is not in this ifg */
@@ -282,7 +301,7 @@ static int ifg_list_connected(const void *self, const ir_node *a, const ir_node
                if(element->irn == b)
                        is_element = 1;
 
-       adj_head = pmap_get(ifg->list_map, node_b);
+       adj_head = ifg->adj_heads[node_b->node_idx];
        assert(adj_head && "There is no entry for the second node");
 
        //if (adj_head == NULL) /* node is not in this ifg */
@@ -330,8 +349,8 @@ 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 = 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;
 }
@@ -356,10 +375,13 @@ 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);