X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeifg_list.c;h=5482104c26cb43a9e54e36a95aadfdc9b1526958;hb=5124cba7e9aa4ef891804bb6124812c1eafd7705;hp=e9b970d62f3a84e1269403aedd851c1b4f650ffa;hpb=51b9ece7394f09ec1577b764446938976ad6b867;p=libfirm diff --git a/ir/be/beifg_list.c b/ir/be/beifg_list.c index e9b970d62..5482104c2 100644 --- a/ir/be/beifg_list.c +++ b/ir/be/beifg_list.c @@ -1,343 +1,412 @@ -/** - * @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 -#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, @@ -356,14 +425,16 @@ 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(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;