X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeifg_list.c;h=117815e17283edee7e908a2c425885230949c942;hb=29189ce06a4930207bac3adda67d7d663dbb77f7;hp=617f160f6f8cc607f32d181c77f6e51022a7c795;hpb=d6768d8d4427959eb045aafb1d15bd189beaa5dd;p=libfirm diff --git a/ir/be/beifg_list.c b/ir/be/beifg_list.c index 617f160f6..117815e17 100644 --- a/ir/be/beifg_list.c +++ b/ir/be/beifg_list.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -18,28 +18,23 @@ */ /** - * @file beifg_list.c - * @date 18.11.2005 - * @author Sebastian Hack - * - * Copyright (C) 2005 Universitaet Karlsruhe - * Released under the GPL + * @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 "benodesets.h" #include "list.h" #include "irnode_t.h" #include "irgraph_t.h" #include "irgwalk.h" -#include "bearch_t.h" +#include "bearch.h" #include "be_t.h" #include "bera.h" #include "beifg_t.h" @@ -49,45 +44,46 @@ 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; - adj_head_t **adj_heads; + struct obstack obst; + adj_head_t **adj_heads; } ifg_list_t; typedef struct _adj_element_t adj_element_t; struct _adj_element_t { adj_element_t *next_adj_element; - ir_node *neighbour; + ir_node *neighbour; }; struct _adj_head_t { - ir_node *irn; /* the node you search neighbours for */ + ir_node *irn; /* the node you search neighbours for */ adj_element_t *first_adj_element; - int degree; + int degree; }; typedef struct _nodes_iter_t { const ifg_list_t *ifg; - unsigned int curr_node_idx; + unsigned int curr_node_idx; } nodes_iter_t; typedef struct _adj_iter_t { const ifg_list_t *ifg; - adj_element_t *curr_adj_element; + adj_element_t *curr_adj_element; } adj_iter_t; /* PRIVATE FUNCTIONS */ -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 */ +/* 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 = NULL; adj_head = ifg->adj_heads[irn->node_idx]; if (!adj_head) { - adj_head = obstack_alloc(&ifg->obst, sizeof(*adj_head)); + adj_head = OALLOC(&ifg->obst, adj_head_t); adj_head->irn = irn; adj_head->first_adj_element = NULL; adj_head->degree = 0; @@ -99,18 +95,19 @@ static adj_element_t *create_adj_element(ifg_list_t *ifg, ir_node *irn) { adj_element_t *element = NULL; - element = obstack_alloc(&ifg->obst, sizeof(*element)); + element = OALLOC(&ifg->obst, adj_element_t); element->next_adj_element = NULL; element->neighbour = irn; return element; } -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 */ +/* 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 = NULL; + adj_head_t *adj_head = NULL; adj_element_t *curr_element = NULL; - adj_element_t *new_element = NULL; + adj_element_t *new_element = NULL; adj_head = ifg->adj_heads[node_a->node_idx]; /* find the neighbours list of a */ @@ -166,26 +163,30 @@ static void add_edge(ifg_list_t *ifg, ir_node *node_a, ir_node *node_b) /* write } } -static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in the irg */ +/* 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); + 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; - nodeset *live = new_nodeset(ifg->env->cls->n_regs); - 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 each block */ { 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); + ir_nodeset_insert(&live, b->irn); if (b->is_real) /* this is a new node */ { - foreach_nodeset(live, live_irn) + 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); @@ -194,20 +195,18 @@ static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent } else /* b->irn is now dead */ { - if (nodeset_find(live, b->irn)) - nodeset_remove(live, b->irn); + ir_nodeset_remove(&live, b->irn); } } - if (live) - del_nodeset(live); + ir_nodeset_destroy(&live); } static ir_node *get_first_node(const ifg_list_t *ifg, nodes_iter_t *it) { - ir_node *res = NULL; - adj_head_t *adj_head= NULL; - int curr_idx = -1; + ir_node *res = NULL; + adj_head_t *adj_head = NULL; + int curr_idx = -1; it->ifg = ifg; it->curr_node_idx = 0; @@ -231,10 +230,10 @@ static ir_node *get_first_node(const ifg_list_t *ifg, nodes_iter_t *it) static ir_node *get_next_node(nodes_iter_t *it) { - 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; + 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; while (adj_head == NULL && curr_idx < it->ifg->env->irg->last_node_idx - 1) { @@ -255,11 +254,11 @@ static ir_node *get_next_node(nodes_iter_t *it) static ir_node *get_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *curr_irn) { - ir_node *res = NULL; + 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"); + assert(adj_head && "There is no entry for this node"); it->curr_adj_element = NULL; it->ifg = ifg; @@ -277,7 +276,7 @@ static ir_node *get_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const static ir_node *get_next_neighbour(adj_iter_t *it) { - ir_node *res = NULL; + ir_node *res = NULL; adj_element_t *element = it->curr_adj_element; if (element->next_adj_element) /* return next neighbour */ @@ -303,10 +302,10 @@ static void ifg_list_free(void *self) static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b) { - const ifg_list_t *ifg = self; - int res = -1; - adj_head_t *adj_head = NULL; - adj_element_t *curr_element = NULL; + const ifg_list_t *ifg = self; + int res = -1; + adj_head_t *adj_head = NULL; + adj_element_t *curr_element = NULL; /* first try: find b in the neigbours of a */ adj_head = ifg->adj_heads[a->node_idx]; @@ -314,7 +313,7 @@ static int ifg_list_connected(const void *self, const ir_node *a, const ir_node assert(adj_head && "There is no entry for the node a"); curr_element = adj_head->first_adj_element; - if(curr_element) + if (curr_element) { while (curr_element->neighbour != b && curr_element->next_adj_element) { @@ -334,7 +333,7 @@ static int ifg_list_connected(const void *self, const ir_node *a, const ir_node assert(adj_head && "There is no entry for the node b"); curr_element = adj_head->first_adj_element; - if(curr_element) + if (curr_element) { while (curr_element->neighbour != a && curr_element->next_adj_element) { @@ -362,12 +361,14 @@ static ir_node *ifg_list_nodes_begin(const void *self, void *iter) static ir_node *ifg_list_nodes_next(const void *self, void *iter) { + (void) self; return get_next_node(iter); } 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; } @@ -380,12 +381,14 @@ static ir_node *ifg_list_neighbours_begin(const void *self, void *iter,const ir_ static ir_node *ifg_list_neighbours_next(const void *self, void *iter) { + (void) self; return get_next_neighbour(iter); } 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; } @@ -422,13 +425,12 @@ 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)); - adj_head_t **adj_heads_array = xmalloc(env->irg->last_node_idx * sizeof(adj_heads_array[0])); + 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; - 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);