X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeifg_clique.c;h=affe7cc8d434490d483866f244198a841ce3b1d8;hb=1feecdf96eadc9bfd6e94b245eb38e0009a80c02;hp=745c2d4fd4734cc949c132039a976f9820f3fd1f;hpb=8fca8d6370f5895f2131863a9462a34302ca587c;p=libfirm diff --git a/ir/be/beifg_clique.c b/ir/be/beifg_clique.c index 745c2d4fd..affe7cc8d 100644 --- a/ir/be/beifg_clique.c +++ b/ir/be/beifg_clique.c @@ -1,14 +1,30 @@ -/** - * @file beifg_clique.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 Clique calculation for chordal ifg. + * @author Sebastian Hack + * @date 18.11.2005 + * @version $Id$ */ -#ifdef HAVE_CONFIG_H #include "config.h" -#endif #include @@ -20,38 +36,40 @@ #include "irgwalk.h" #include "irbitset.h" +#include "bearch.h" #include "be_t.h" -#include "bera.h" +#include "beintlive_t.h" #include "beifg_t.h" +#include "beifg_impl.h" #include "bechordal_t.h" typedef struct _cli_head_t { - struct list_head list; + struct list_head list; struct _cli_head_t *next_cli_head; - ir_node *min; - ir_node *max; + ir_node *min; + ir_node *max; } cli_head_t; typedef struct _ifg_clique_t { - const be_ifg_impl_t *impl; + const be_ifg_impl_t *impl; const be_chordal_env_t *env; - cli_head_t *cli_root; - struct obstack obst; - cli_head_t *curr_cli_head; + cli_head_t *cli_root; + struct obstack obst; + cli_head_t *curr_cli_head; } ifg_clique_t; typedef struct _cli_element_t { struct list_head list; - ir_node *irn; + ir_node *irn; } cli_element_t; typedef struct _cli_iter_t { - ifg_clique_t *ifg; - cli_head_t *curr_cli_head; - cli_element_t *curr_cli_element; - const ir_node *curr_irn; - bitset_t *visited_neighbours; - bitset_t *visited_nodes; + const ifg_clique_t *ifg; + cli_head_t *curr_cli_head; + cli_element_t *curr_cli_element; + const ir_node *curr_irn; + bitset_t *visited_neighbours; + bitset_t *visited_nodes; } cli_iter_t; /* PRIVATE FUNCTIONS */ @@ -62,18 +80,18 @@ static cli_head_t *get_new_cli_head(ifg_clique_t *ifg) if (ifg->cli_root == NULL) { - new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head)); + new_cli_head = OALLOC(&ifg->obst, cli_head_t); INIT_LIST_HEAD(&new_cli_head->list); ifg->cli_root = new_cli_head; } else { cli_head = ifg->cli_root; - while(!(cli_head->next_cli_head == NULL)) + while (!(cli_head->next_cli_head == NULL)) { cli_head = cli_head->next_cli_head; } - new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head)); + new_cli_head = OALLOC(&ifg->obst, cli_head_t); INIT_LIST_HEAD(&new_cli_head->list); cli_head->next_cli_head = new_cli_head; } @@ -90,13 +108,13 @@ static cli_element_t *get_new_cli_element(ifg_clique_t *ifg) { cli_element_t *cli_element; - cli_element = obstack_alloc(&ifg->obst, sizeof(*cli_element)); + cli_element = OALLOC(&ifg->obst, cli_element_t); INIT_LIST_HEAD(&cli_element->list); return cli_element; } -static void write_clique(nodeset *live_set, ifg_clique_t *ifg) +static void write_clique(ir_nodeset_t *live_set, ifg_clique_t *ifg) { ir_node *live_irn; ir_node *test_node; @@ -107,8 +125,9 @@ static void write_clique(nodeset *live_set, ifg_clique_t *ifg) cli_element_t *element = NULL; cli_head_t *cli_head = get_new_cli_head(ifg); int is_element = 0; + ir_nodeset_iterator_t iter; - foreach_nodeset(live_set, live_irn) + foreach_ir_nodeset(live_set, live_irn, iter) { /* test if node is max or min dominator*/ test_node = live_irn; @@ -132,7 +151,7 @@ static void write_clique(nodeset *live_set, ifg_clique_t *ifg) } list_for_each_entry(cli_element_t, element, &cli_head->list, list){ - if(element->irn == live_irn){ + if (element->irn == live_irn){ is_element = 1; break; } @@ -155,7 +174,6 @@ static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...c cli_element_t *element; int is_dominated_by_max; - //int dominates_min; if (it->curr_cli_head == NULL || it->curr_cli_head->next_cli_head == NULL) /* way back of recursion or this is the last clique */ { @@ -166,7 +184,6 @@ static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...c head = it->curr_cli_head->next_cli_head; is_dominated_by_max = value_dominates(head->max, irn); - //dominates_min = value_dominates(irn, head->min); if ((is_dominated_by_max) || (irn == head->max)) /* node could be in clique */ { @@ -176,9 +193,11 @@ static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...c if (&element->list != &head->list) { if (element->irn == irn) - { /* node is in clique */ + { + /* node is in clique */ it->curr_cli_head = head; - it->curr_cli_element = (void *) head; /* needed because the next element is searched with list.next of it->curr_cli_element */ + /* needed because the next element is searched with list.next of it->curr_cli_element */ + it->curr_cli_element = (void *) head; break; } } @@ -198,10 +217,11 @@ static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...c return head; } -static cli_element_t *get_next_element(const ir_node *irn, cli_iter_t *it) /* ... of the current clique, returns NULL if there were no more elements ..*/ +/* ... of the current clique, returns NULL if there were no more elements ..*/ +static cli_element_t *get_next_element(const ir_node *irn, cli_iter_t *it) { cli_element_t *element = it->curr_cli_element; - cli_head_t *head = it->curr_cli_head; + cli_head_t *head = it->curr_cli_head; if (!head || it->curr_cli_element == NULL) /* way back of recursion or there are no more heads */ { @@ -247,8 +267,6 @@ static void find_nodes(const ifg_clique_t *ifg, cli_iter_t *it) element = list_entry(cli_head->list.next, cli_element_t, list); it->curr_cli_element = element; } - - return; } static ir_node *get_next_node(cli_iter_t *it) @@ -302,11 +320,13 @@ static ir_node *get_next_node(cli_iter_t *it) static void find_neighbour_walker(ir_node *bl, void *data) { - ifg_clique_t *ifg = data; - struct list_head *head = get_block_border_head(ifg->env, bl); - border_t *b; - int was_def = 0; - nodeset *live = new_nodeset(ifg->env->cls->n_regs); + ifg_clique_t *ifg = data; + struct list_head *head = get_block_border_head(ifg->env, bl); + int was_def = 0; + ir_nodeset_t live; + border_t *b; + + ir_nodeset_init(&live); assert(is_Block(bl) && "There is no block to work on."); @@ -316,8 +336,8 @@ static void find_neighbour_walker(ir_node *bl, void *data) if (b->is_def) /* b is a new node */ { - nodeset_insert(live, irn); - if(b->is_real) + ir_nodeset_insert(&live, irn); + if (b->is_real) { was_def = 1; } @@ -326,23 +346,22 @@ static void find_neighbour_walker(ir_node *bl, void *data) { if (was_def == 1) /* if there is a USE after a DEF... */ { - write_clique(live, ifg); /* ...add the clique. */ + write_clique(&live, ifg); /* ...add the clique. */ was_def = 0; } - nodeset_remove(live, irn); + ir_nodeset_remove(&live, irn); } } - del_nodeset(live); + ir_nodeset_destroy(&live); } static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const ir_node *irn) { - cli_head_t *cli_head = ifg->cli_root; + cli_head_t *cli_head = ifg->cli_root; cli_element_t *element; - bitset_t *bitset_visneighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg)); + bitset_t *bitset_visneighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg)); int is_dominated_by_max = 0; - int dominates_min = 0; int is_in_clique = 0; it->curr_cli_head = cli_head; @@ -352,7 +371,6 @@ static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const assert(cli_head && "There is no root entry for a cli_head."); is_dominated_by_max = value_dominates(cli_head->max, irn); - dominates_min = value_dominates(irn, cli_head->min); if ((is_dominated_by_max) || (irn == cli_head->max)) /* node could be in clique */ { @@ -368,7 +386,7 @@ static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const } } } - if(!is_in_clique) + if (!is_in_clique) { cli_head = get_next_cli_head(irn, it); element = get_next_element(irn, it); @@ -376,14 +394,11 @@ static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const it->curr_cli_element = element; it->curr_irn = irn; - - return; } static ir_node *get_next_neighbour(cli_iter_t *it) { ir_node *res = NULL; - cli_head_t *cli_head = it->curr_cli_head; const ir_node *irn = it->curr_irn; if (it->curr_cli_element != NULL) @@ -419,8 +434,9 @@ static void ifg_clique_free(void *self) free(self); } -static int ifg_clique_connected(const ifg_clique_t *ifg, const ir_node *a, const ir_node *b) +static int ifg_clique_connected(const void *self, const ir_node *a, const ir_node *b) { + const ifg_clique_t *ifg = self; cli_iter_t it; int connected = -1; ir_node *irn = NULL; @@ -449,16 +465,16 @@ static ir_node *ifg_clique_neighbours_begin(const void *self, void *iter, const static ir_node *ifg_clique_neighbours_next(const void *self, void *iter) { + (void) self; return get_next_neighbour(iter); } static void ifg_clique_neighbours_break(const void *self, void *iter) { cli_iter_t *it = iter; + (void) self; bitset_free(it->visited_neighbours); - - return; } static ir_node *ifg_clique_nodes_begin(const void *self, void *iter) @@ -469,16 +485,16 @@ static ir_node *ifg_clique_nodes_begin(const void *self, void *iter) static ir_node *ifg_clique_nodes_next(const void *self, void *iter) { + (void) self; return get_next_node(iter); } static void ifg_clique_nodes_break(const void *self, void *iter) { cli_iter_t *it = iter; + (void) self; bitset_free(it->visited_nodes); - - return; } static int ifg_clique_degree(const void *self, const ir_node *irn) @@ -518,7 +534,7 @@ static const be_ifg_impl_t ifg_clique_impl = { be_ifg_t *be_ifg_clique_new(const be_chordal_env_t *env) { - ifg_clique_t *ifg = xmalloc(sizeof(*ifg)); + ifg_clique_t *ifg = XMALLOC(ifg_clique_t); ifg->impl = &ifg_clique_impl; ifg->env = env;