X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeifg_clique.c;h=778d0b1a4599a2c2e26ba4c2fef4a2316877d363;hb=4ed245f5007168dab7850942a7ee6b6b29a19817;hp=7c583451af3b2ded132e55e715e418202f1765f1;hpb=287b05140d6a6e7c74c779035cb760b4a7f5aa39;p=libfirm diff --git a/ir/be/beifg_clique.c b/ir/be/beifg_clique.c index 7c583451a..778d0b1a4 100644 --- a/ir/be/beifg_clique.c +++ b/ir/be/beifg_clique.c @@ -18,6 +18,7 @@ #include "irnode_t.h" #include "irgraph_t.h" #include "irgwalk.h" +#include "irbitset.h" #include "be_t.h" #include "bera.h" @@ -37,8 +38,6 @@ typedef struct _ifg_clique_t { cli_head_t *cli_root; struct obstack obst; cli_head_t *curr_cli_head; - bitset_t *visited_nodes; - bitset_t *visited_neighbours; } ifg_clique_t; typedef struct _cli_element_t { @@ -47,10 +46,12 @@ typedef struct _cli_element_t { } cli_element_t; typedef struct _cli_iter_t { - ifg_clique_t *ifg; + 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 */ @@ -167,9 +168,6 @@ static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...c is_dominated_by_max = value_dominates(head->max, irn); //dominates_min = value_dominates(irn, head->min); - if(head->min->node_nr == 2000) - assert("stop"); - if ((is_dominated_by_max) || (irn == head->max)) /* node could be in clique */ { /* check if node is in clique */ @@ -220,7 +218,7 @@ static cli_element_t *get_next_element(const ir_node *irn, cli_iter_t *it) /* .. element = get_next_element(irn, it); } - if (element != NULL && element->irn == irn) /* the node you are searching neighbors for */ + if (element && element->irn == irn) /* the node you are searching neighbors for */ { it->curr_cli_element = element; element = get_next_element(irn, it); @@ -237,12 +235,13 @@ static void find_nodes(const ifg_clique_t *ifg, cli_iter_t *it) cli_element_t *element; cli_head_t *cli_head = ifg->cli_root; - bitset_clear_all(ifg->visited_nodes); - - assert(cli_head && "There is no root entry to work on!"); + bitset_t *bitset_visnodes = bitset_malloc(get_irg_last_idx(ifg->env->irg)); + it->visited_nodes = bitset_visnodes; it->curr_cli_head = cli_head; + assert(cli_head && "There is no root entry to work on!"); + if (cli_head->list.next != &cli_head->list) /* if cli_head contains an element */ { element = list_entry(cli_head->list.next, cli_element_t, list); @@ -288,13 +287,13 @@ static ir_node *get_next_node(cli_iter_t *it) } if (!(irn == NULL)) { - if (bitset_is_set(it->ifg->visited_nodes, get_irn_idx(irn))) + if (bitset_is_set(it->visited_nodes, get_irn_idx(irn))) { irn = get_next_node(it); } if (!(irn == NULL)) { - bitset_set(it->ifg->visited_nodes, get_irn_idx(irn)); + bitset_set(it->visited_nodes, get_irn_idx(irn)); } } @@ -314,9 +313,6 @@ static void find_neighbour_walker(ir_node *bl, void *data) foreach_border_head(head, b) /* follow the borders of the block */ { ir_node *irn = b->irn; -// -// if (b->irn->node_nr == 1869) -// printf(""); if (b->is_def) /* b is a new node */ { @@ -343,6 +339,7 @@ static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const { 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)); int is_dominated_by_max = 0; int dominates_min = 0; @@ -350,7 +347,7 @@ static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const it->curr_cli_head = cli_head; it->ifg = ifg; - bitset_clear_all(it->ifg->visited_neighbours); + it->visited_neighbours = bitset_visneighbours; assert(cli_head && "There is no root entry for a cli_head."); @@ -362,15 +359,12 @@ static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const /* check if node is in clique */ list_for_each_entry(cli_element_t, element, &cli_head->list, list) { - if (&element->list != &cli_head->list) + if (element->irn == irn) /* node is in clique */ { - if (element->irn == irn) - { /* node is in clique */ - it->curr_cli_element = (void *) cli_head; /* needed because the next element is searched with list.next of it->curr_cli_element */ - is_in_clique = 1; - element = get_next_element(irn, it); - break; - } + it->curr_cli_element = (void *) cli_head; /* needed because the next element is searched with list.next of it->curr_cli_element */ + is_in_clique = 1; + element = get_next_element(irn, it); + break; } } } @@ -389,8 +383,6 @@ static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const static ir_node *get_next_neighbour(cli_iter_t *it) { ir_node *res = NULL; - cli_element_t *element; - cli_head_t *cli_head = it->curr_cli_head; const ir_node *irn = it->curr_irn; if (it->curr_cli_element != NULL) @@ -398,30 +390,17 @@ static ir_node *get_next_neighbour(cli_iter_t *it) else return NULL; - element = get_next_element(irn, it); + it->curr_cli_element = get_next_element(irn, it); - if (element == NULL) /* no more elements in this clique */ + if (res) { - it->curr_cli_element = NULL; - } - else - { - it->curr_cli_element = element; - } - - if (!(res == NULL)) - { - if (bitset_is_set(it->ifg->visited_neighbours, get_irn_idx(res))) + if (bitset_contains_irn(it->visited_neighbours, res)) { res = get_next_neighbour(it); -// if (res == NULL) /* there are no more neighbours to return */ -// { -// return NULL; -// } } else { - bitset_set(it->ifg->visited_neighbours, get_irn_idx(res)); + bitset_set(it->visited_neighbours, get_irn_idx(res)); } } @@ -439,8 +418,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; @@ -474,6 +454,10 @@ static ir_node *ifg_clique_neighbours_next(const void *self, void *iter) static void ifg_clique_neighbours_break(const void *self, void *iter) { + cli_iter_t *it = iter; + + bitset_free(it->visited_neighbours); + return; } @@ -490,21 +474,25 @@ static ir_node *ifg_clique_nodes_next(const void *self, void *iter) static void ifg_clique_nodes_break(const void *self, void *iter) { + cli_iter_t *it = iter; + + bitset_free(it->visited_nodes); + return; } static int ifg_clique_degree(const void *self, const ir_node *irn) { int degree = -1; - cli_iter_t *it = NULL; + cli_iter_t it; - find_first_neighbour(self, it, irn); + find_first_neighbour(self, &it, irn); degree = 0; - irn = get_next_neighbour(it); + irn = get_next_neighbour(&it); while (irn != NULL) { degree++; - irn = get_next_neighbour(it); + irn = get_next_neighbour(&it); } return degree; @@ -531,10 +519,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)); - bitset_t *bitset_visnodes = bitset_malloc(get_irg_last_idx(env->irg)); - bitset_t *bitset_visneighbours = bitset_malloc(get_irg_last_idx(env->irg)); - ifg->visited_nodes = bitset_visnodes; - ifg->visited_neighbours = bitset_visneighbours; + ifg->impl = &ifg_clique_impl; ifg->env = env;