From 51b9ece7394f09ec1577b764446938976ad6b867 Mon Sep 17 00:00:00 2001 From: Johannes Spallek Date: Wed, 3 May 2006 14:43:12 +0000 Subject: [PATCH] alternativ methods to create a local reusable ifg --- ir/be/beifg_clique.c | 454 ++++++++++++++++++++++++++++++++++++++++ ir/be/beifg_list.c | 370 +++++++++++++++++++++++++++++++++ ir/be/beifg_pointer.c | 468 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 1292 insertions(+) create mode 100644 ir/be/beifg_clique.c create mode 100644 ir/be/beifg_list.c create mode 100644 ir/be/beifg_pointer.c diff --git a/ir/be/beifg_clique.c b/ir/be/beifg_clique.c new file mode 100644 index 000000000..9558d1321 --- /dev/null +++ b/ir/be/beifg_clique.c @@ -0,0 +1,454 @@ +/** + * @file beifg_clique.c + * @date 18.11.2005 + * @author Sebastian Hack + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ +#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 "be_t.h" +#include "bera.h" +#include "beifg_t.h" +#include "bechordal_t.h" + +typedef struct _cli_head_t { + struct list_head list; + struct _cli_head_t *next_cli_head; + ir_node *min; + ir_node *max; +} cli_head_t; + +typedef struct _ifg_clique_t { + 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; +} ifg_clique_t; + +typedef struct _cli_element_t { + ir_node *irn; + struct list_head list; +} cli_element_t; + +typedef struct _cli_iter_t { + ifg_clique_t *ifg; + cli_head_t *curr_cli_head; + cli_element_t *curr_cli_element; + unsigned long curr_irg_visited; + const ir_node *curr_irn; +} cli_iter_t; + +/* PRIVATE FUNCTIONS */ +static cli_head_t *get_new_cli_head(ifg_clique_t *ifg) +{ + cli_head_t *cli_head; + cli_head_t *new_cli_head; + + if (ifg->cli_root == NULL) + { + new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head)); + 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)) + { + cli_head = cli_head->next_cli_head; + } + new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head)); + INIT_LIST_HEAD(&new_cli_head->list); + cli_head->next_cli_head = new_cli_head; + } + + new_cli_head->min = NULL; + new_cli_head->max = NULL; + new_cli_head->next_cli_head = NULL; + ifg->curr_cli_head = new_cli_head; + + return new_cli_head; +} + +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)); + INIT_LIST_HEAD(&cli_element->list); + + return cli_element; +} + +static void write_clique(nodeset *live_set, ifg_clique_t *ifg) +{ + ir_node *live_irn; + ir_node *test_node; + int test_int = 0; + ir_node *max_node = NULL; + ir_node *min_node = NULL; + cli_element_t *new_element = NULL; + cli_element_t *element = NULL; + cli_head_t *cli_head = get_new_cli_head(ifg); + int is_element = 0; + + foreach_nodeset(live_set, live_irn) + { + /* test if node is max or min dominator*/ + test_node = live_irn; + if (max_node == NULL) + { + max_node = test_node; + min_node = test_node; + } + else + { + test_int = value_dominates(test_node, max_node); + if (test_int == 1) + { + max_node = test_node; + } + test_int = value_dominates(min_node, test_node); + if (test_int == 1) + { + min_node = test_node; + } + + list_for_each_entry(cli_element_t, element, &cli_head->list, list){ + if(element->irn == live_irn){ + is_element = 1; + break; + } + } + + if (!is_element){ + new_element = get_new_cli_element(ifg); + new_element->irn = live_irn; + list_add(&new_element->list, &cli_head->list) ; + } + } + } + + cli_head->min = min_node; + cli_head->max = max_node; +} + +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; + + assert((cli_head == NULL) && "There is no node to work on!"); + + it->curr_cli_head = cli_head; + + 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); + it->curr_cli_element = element; + + inc_irg_visited(get_irn_irg(element->irn)); + it->curr_irg_visited = get_irg_visited(get_irn_irg(element->irn)); + } + + return; +} + +static ir_node *get_next_node(cli_iter_t *it) +{ + cli_head_t *cli_head = NULL; + cli_element_t *element = it->curr_cli_element; + unsigned long irn_visited = get_irn_visited(element->irn); + + ir_node *irn; + + if (!(element == it->curr_cli_element)) + { + irn = element->irn; + element = list_entry(cli_head->list.next, cli_element_t, list); + it->curr_cli_element = element; + } + else + { + cli_head = it->curr_cli_head; + if (!(cli_head->next_cli_head == NULL)) + { + irn = element->irn; + cli_head = cli_head->next_cli_head; + it->curr_cli_head = cli_head; + element = list_entry(cli_head->list.next, cli_element_t, list); + it->curr_cli_element = element; + } + else + { + return NULL; + } + } + + if (irn_visited == it->curr_irg_visited) + { + irn = get_next_node(it); + } + + set_irn_visited(irn, it->curr_irg_visited); + return irn; +} + +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); + + assert(is_Block(bl) && "There is no block to work on."); + + foreach_border_head(head, b) /* follow the borders of the block */ + { + ir_node *irn = b->irn; + + if (b->is_def) /* b is a new node */ + { + nodeset_insert(live, irn); + if(b->is_real) + { + was_def = 1; + } + } + else + { + if (!(b->is_def)) + { + if (was_def == 1) /* if there is a USE after a DEF... */ + { + write_clique(live, ifg); /* ...add the clique. */ + was_def = 0; + } + nodeset_remove(live, irn); + } + } + } + del_nodeset(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_element_t *element; + + int is_dominated_by_max = 0; + int dominates_min = 0; + + assert(!cli_head && "There is no root entry for a cli_head."); + + while(!(cli_head->next_cli_head == NULL)) + { + is_dominated_by_max = value_dominates(cli_head->max, irn); + dominates_min = value_dominates(irn, cli_head->min); + + if ((is_dominated_by_max && dominates_min) /* node is in clique */ + || (irn == cli_head->max) + || (irn == cli_head->min)) + { + element = list_entry(cli_head->list.next, cli_element_t, list); + + it->curr_cli_element = element; + it->curr_cli_head = cli_head; + break; + } + else + { + cli_head = cli_head->next_cli_head; + } + } + it->curr_irn = irn; + + inc_irg_visited(get_irn_irg(irn)); + it->curr_irg_visited = get_irg_visited(get_irn_irg(irn)); + return; +} + +static ir_node *get_next_neighbour(cli_iter_t *it) +{ + ir_node *res = NULL; + cli_element_t *element = NULL; + cli_head_t *cli_head = NULL; + int is_dominated_by_max; + int dominates_min; + const ir_node *irn = it->curr_irn; + unsigned long irn_visited = 0; + + res = it->curr_cli_element->irn; + + /* get next element */ + + element = list_entry(it->curr_cli_element->list.next, cli_element_t, list); + irn_visited = get_irn_visited(element->irn); + + if ((cli_head_t *)element == it->curr_cli_head) /* end of clique, search next one */ + { + cli_head = cli_head->next_cli_head; + while(!(cli_head->next_cli_head == NULL)) + { + is_dominated_by_max = value_dominates(cli_head->max, irn); + dominates_min = value_dominates(irn, cli_head->min); + + if ((is_dominated_by_max && dominates_min) /* node is in clique */ + || (irn == cli_head->max) + || (irn == cli_head->min)) + { + element = list_entry(cli_head->list.next, cli_element_t, list); + + it->curr_cli_element = element; + it->curr_cli_head = cli_head; + break; + } + else + { + cli_head = cli_head->next_cli_head; + } + } + } + else /* get next element of this clique */ + { + it->curr_cli_element = element; + } + + if (irn_visited == it->curr_irg_visited) + { + irn = get_next_neighbour(it); + } + + set_irn_visited(res, it->curr_irg_visited); + + return res; +} + + +/* PUBLIC FUNCTIONS */ + +static void ifg_clique_free(void *self) +{ + ifg_clique_t *ifg = self; + obstack_free(&ifg->obst, NULL); + + free(self); +} + +static int ifg_clique_connected(const void *self, const ir_node *a, const ir_node *b) +{ + cli_iter_t *it = NULL; + int connected = -1; + ir_node *irn = NULL; + + find_first_neighbour(self, it, a); + connected = 0; + irn = get_next_neighbour(it); + while (irn != NULL) + { + if (irn == b) + { + connected = 1; + } + irn = get_next_neighbour(it); + } + + return connected; +} + +static ir_node *ifg_clique_neighbours_begin(const void *self, void *iter, const ir_node *irn) +{ + find_first_neighbour(self, iter, irn); + return get_next_neighbour(iter); +} + +static ir_node *ifg_clique_neighbours_next(const void *self, void *iter) +{ + return get_next_neighbour(iter); +} + +static void ifg_clique_neighbours_break(const void *self, void *iter) +{ + return; +} + +static ir_node *ifg_clique_nodes_begin(const void *self, void *iter) +{ + find_nodes(self, iter); + return get_next_node(iter); +} + +static ir_node *ifg_clique_nodes_next(const void *self, void *iter) +{ + return get_next_node(iter); +} + +static void ifg_clique_nodes_break(const void *self, void *iter) +{ + return; +} + +static int ifg_clique_degree(const void *self, const ir_node *irn) +{ + int degree = -1; + cli_iter_t *it = NULL; + + find_first_neighbour(self, it, irn); + degree = 0; + irn = get_next_neighbour(it); + while (irn != NULL) + { + degree++; + irn = get_next_neighbour(it); + } + + return degree; +} + +static const be_ifg_impl_t ifg_clique_impl = { + sizeof(cli_iter_t), + sizeof(cli_iter_t), + 0, + ifg_clique_free, + ifg_clique_connected, + ifg_clique_neighbours_begin, + ifg_clique_neighbours_next, + ifg_clique_neighbours_break, + ifg_clique_nodes_begin, + ifg_clique_nodes_next, + ifg_clique_nodes_break, + NULL, + NULL, + NULL, + ifg_clique_degree +}; + +be_ifg_t *be_ifg_clique_new(const be_chordal_env_t *env) +{ + ifg_clique_t *ifg = xmalloc(sizeof(*ifg)); + ifg->impl = &ifg_clique_impl; + ifg->env = env; + + ifg->cli_root = NULL; + obstack_init(&ifg->obst); + + dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg); + + obstack_finish(&ifg->obst); + return (be_ifg_t *) ifg; +} diff --git a/ir/be/beifg_list.c b/ir/be/beifg_list.c new file mode 100644 index 000000000..e9b970d62 --- /dev/null +++ b/ir/be/beifg_list.c @@ -0,0 +1,370 @@ +/** + * @file beifg_list.c + * @date 18.11.2005 + * @author Sebastian Hack + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ +#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 "be_t.h" +#include "bera.h" +#include "beifg_t.h" +#include "bechordal_t.h" + +#define MAX(x, y) ((x) > (y) ? (x) : (y)) + +typedef struct _ifg_list_t { + const be_ifg_impl_t *impl; + const be_chordal_env_t *env; + struct obstack obst; + pmap *list_map; +} ifg_list_t; + +typedef struct _list_element_t { + struct list_head list; + ir_node *irn; +} list_element_t; + +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 _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; +} 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 = pmap_get(ifg->list_map, irn); + 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); + } + + return adj_head; +} + +static list_element_t *get_new_list_element(ifg_list_t *ifg, ir_node *irn) +{ + list_element_t *element; + + element = obstack_alloc(&ifg->obst, sizeof(*element)); + element->irn = irn; + INIT_LIST_HEAD(&element->list); + + 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 */ +{ + 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; + } + } + 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 (!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); + adj_head->degree++; + list_add(&new_element->list, &adj_head->list); + } +} + +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; + + return; +} + +static ir_node *get_next_node(adj_iter_t *it) +{ + adj_head_t *adj_head; + + pmap_entry *entry; + ir_node *irn; + + if (it->curr_adj_head == NULL) + return NULL; + 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; + } + return irn; +} + +static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in one given block */ +{ + 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; + + assert(is_Block(bl) && "There is no block to work on."); + + foreach_border_head(head, b) /* follow the borders of the 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 */ + add_edge(ifg, b->irn, live_irn); +// } + } + } + + else { + if (nodeset_find(live,b->irn)) /* b is used, deleting... */ + nodeset_remove(live, b->irn); + } + } + if (delete_nodeset) + del_nodeset(live); +} + + +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); + + assert(adj_head && "There is no entry for this node."); + + if (adj_head->list.next == &adj_head->list) + { + /* element has no neighbours */ + it->irn = NULL; + it->curr_adj_head = adj_head; + it->curr_list_element = NULL; + return; + } + + 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; + + return; +} + +static ir_node *get_next_neighbour(adj_iter_t *it) +{ + ir_node *res; + list_element_t *element; + adj_head_t *adj_head = it->curr_adj_head; + + if(it->irn != NULL) /* return the previous found neighbour */ + res = it->irn; + else + { + 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; + } + + 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) */ + { + it->irn = NULL; + it->curr_list_element = NULL; + return res; + } + + if(element->list.next == &adj_head->list) /* reaching end of list */ + it->irn = NULL; + else + it->irn = element->irn; + + it->curr_list_element = element; + + 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); +} + +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; + + adj_head = pmap_get(ifg->list_map, node_a); + assert(adj_head && "There is no entry for the first node."); + + //if (adj_head == NULL) /* node is not in this ifg */ + // return 1; + + list_for_each_entry(list_element_t, element, &adj_head->list, list) + if(element->irn == b) + is_element = 1; + + adj_head = pmap_get(ifg->list_map, node_b); + assert(adj_head && "There is no entry for the second node"); + + //if (adj_head == NULL) /* node is not in this ifg */ + // return 1; + + list_for_each_entry(list_element_t, element, &adj_head->list, list) + if(element->irn == a) + is_element = 1; + + return is_element; +} + +static ir_node *ifg_list_neighbours_begin(const void *self, adj_iter_t *it, const ir_node *irn) +{ + find_first_neighbour(self, it, irn); + return get_next_neighbour(it); +} + +static ir_node *ifg_list_neighbours_next(const void *self, adj_iter_t *it) +{ + return get_next_neighbour(it); +} + +static void ifg_list_neighbours_break(const void *self, adj_iter_t *it) +{ +} + +static ir_node *ifg_list_nodes_begin(const void *self, adj_iter_t *it) +{ + find_nodes(self, it); + return get_next_node(it); +} + +static ir_node *ifg_list_nodes_next(const void *self, adj_iter_t *it) +{ + return get_next_node(it); +} + +static void ifg_list_nodes_break(const void *self, adj_iter_t *it) +{ +} + +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."); + + return adj_head->degree; +} + +static const be_ifg_impl_t ifg_list_impl = { + sizeof(adj_iter_t), + sizeof(adj_iter_t), + 0, + ifg_list_free, + ifg_list_connected, + ifg_list_neighbours_begin, + ifg_list_neighbours_next, + ifg_list_neighbours_break, + ifg_list_nodes_begin, + ifg_list_nodes_next, + ifg_list_nodes_break, + NULL, + NULL, + NULL, + ifg_list_degree +}; + +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; + + obstack_init(&ifg->obst); + dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg); + + obstack_finish(&ifg->obst); + + return (be_ifg_t *) ifg; +} diff --git a/ir/be/beifg_pointer.c b/ir/be/beifg_pointer.c new file mode 100644 index 000000000..f40bcf070 --- /dev/null +++ b/ir/be/beifg_pointer.c @@ -0,0 +1,468 @@ +/** + * @file beifg_pointer.c + * @date 20.03.2006 + * @author Sebastian Hack + * + * Copyright (C) 2005 Universitaet Karlsruhe + * Released under the GPL + */ + +#if 0 +#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 "be_t.h" +#include "bera.h" +#include "beifg_t.h" +#include "bechordal_t.h" + +typedef struct _cli_head_t { + struct list_head list; + struct _cli_head_t *next_cli_head; + ir_node *min; + ir_node *max; +} cli_head_t; + +typedef struct _ifg_pointer_t { + const be_ifg_impl_t *impl; + const be_chordal_env_t *env; + cli_head_t *cli_root; + struct obstack obst; +} ifg_pointer_t; + +typedef struct _cli_element_t { + ir_node *irn; + struct list_head list; +} cli_element_t; + +typedef struct _cli_iter_t { + ifg_pointer_t *ifg; + cli_head_t *curr_cli_head; + cli_element_t *curr_cli_element; + unsigned long curr_irg_visited; + const ir_node *curr_irn; +} cli_iter_t; + +/* PRIVATE FUNCTIONS */ +static cli_head_t *get_new_cli_head(void *data) +{ + cli_iter_t *it = data; + cli_head_t *cli_head; + cli_head_t *new_cli_head; + + if (it->ifg->cli_root == NULL) + { + new_cli_head = obstack_alloc(&it->ifg->obst, sizeof(*new_cli_head)); + INIT_LIST_HEAD(&new_cli_head->list); + + new_cli_head->next_cli_head = NULL; + it->ifg->cli_root = new_cli_head; + it->curr_cli_head = new_cli_head; + } + else + { + cli_head = it->ifg->cli_root; + while(!(cli_head->next_cli_head == NULL)) + { + cli_head = cli_head->next_cli_head; + } + new_cli_head = obstack_alloc(&it->ifg->obst, sizeof(*new_cli_head)); + INIT_LIST_HEAD(&new_cli_head->list); + cli_head->next_cli_head = new_cli_head; + it->curr_cli_head = new_cli_head; + } + + cli_head->min = NULL; + cli_head->max = NULL; + + return new_cli_head; +} + +static cli_head_t *get_first_cli_head(void *data) +{ + cli_iter_t *it = data; + + return it->ifg->cli_root; +} + +static void write_clique(pset *live_set, void *data) +{ + ir_node *live_irn; + ir_node *test_node; + int test_int = 0; + ir_node *max_node; + ir_node *min_node; + cli_iter_t *it = data; + pset *live = live_set; + cli_element_t *element; + int is_element = 0; + + cli_head_t *cli_head = get_new_cli_head(it); + + for(live_irn = pset_first(live); live_irn; live_irn = pset_next(live)) + { + /* test if node is max or min dominator*/ + test_node = live_irn; + if (max_node == NULL) + { + max_node = test_node; + min_node = test_node; + } + else + { + test_int = value_dominates(test_node, max_node); + if (test_int == 1) + { + max_node = test_node; + } + test_int = value_dominates(min_node, test_node); + if (test_int == 1) + { + min_node = test_node; + } + } + + list_for_each_entry(cli_element_t, element, &cli_head->list, list){ + if(element->irn == live_irn){ + is_element = 1; + break; + } + } + if (!is_element){ + element->irn = live_irn; + list_add(&element->list, &cli_head->list) ; + } + } + cli_head->min = min_node; + cli_head->max = max_node; +} + +static void find_nodes(const void *self, void *iter) +{ + const ifg_clique_t *ifg = self; + cli_iter_t *it = iter; + cli_element_t *element = NULL; + cli_head_t *cli_head = get_first_cli_head(it); + + assert((cli_head == NULL) && "There is no node to work on!"); + + it->curr_cli_head = cli_head; + it->curr_cli_element = element; + + element = list_entry(cli_head->list.next, cli_element_t, list); + + inc_irg_visited(get_irn_irg(element->irn)); + it->curr_irg_visited = get_irg_visited(get_irn_irg(element->irn)); + + return; +} + +static ir_node *get_next_node(void *iter) +{ + cli_iter_t *it = iter; + cli_head_t *cli_head = NULL; + cli_element_t *element = it->curr_cli_element; + unsigned long irn_visited = get_irn_visited(element->irn); + + ir_node *irn; + + if (!(element == it->curr_cli_element)) + { + irn = element->irn; + element = list_entry(cli_head->list.next, cli_element_t, list); + it->curr_cli_element = element; + } + else + { + cli_head = it->curr_cli_head; + if (!(cli_head->next_cli_head == NULL)) + { + irn = element->irn; + cli_head = cli_head->next_cli_head; + it->curr_cli_head = cli_head; + element = list_entry(cli_head->list.next, cli_element_t, list); + it->curr_cli_element = element; + } + else + { + return NULL; + } + } + + if (irn_visited == it->curr_irg_visited) + { + irn = get_next_node(it); + } + + set_irn_visited(irn, it->curr_irg_visited); + return irn; +} + +static void find_neighbour_walker(ir_node *bl, void *data) +{ + cli_iter_t *it = data; + struct list_head *head = get_block_border_head(it->ifg->env, bl); + border_t *b; + int was_def = 0; + + pset *live = put_live_in(bl, pset_new_ptr_default()); + + assert(is_Block(bl) && "There is no block to work on."); + + list_for_each_entry_reverse(border_t, b, head, list) + { + ir_node *irn = b->irn; + + if (!(pset_find_ptr(live, irn)) && (b->is_def)) + { + pset_insert_ptr(live, irn); + was_def = 1; + } + + else if (!(b->is_def) && (was_def == 1)) + { + if (was_def == 1) + { + write_clique(live, it); + was_def = 0; + } + pset_remove_ptr(live, irn); + } + } + del_pset(live); +} + +static ifg_clique_t *build_neighbours(const be_chordal_env_t *env) +{ + ifg_clique_t *ifg = NULL; + cli_iter_t *it = NULL; + + it->ifg = ifg; + it->curr_cli_head = NULL; + it->curr_cli_element = NULL; + it->curr_irg_visited = get_irg_visited(env->irg); + + obstack_init(&it->ifg->obst); + dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, it); + + return ifg; +} + +static void find_first_neighbour(const void *self, void *iter, const ir_node *irn) +{ + const ifg_clique_t *ifg = self; + cli_iter_t *it = iter; + + cli_head_t *cli_head = ifg->cli_root; + cli_element_t *element; + + int is_dominated_by_max = 0; + int dominates_min = 0; + + assert(!cli_head && "There is no root entry for a cli_head."); + + while(!(cli_head->next_cli_head == NULL)) + { + is_dominated_by_max = value_dominates(cli_head->max, irn); + dominates_min = value_dominates(irn, cli_head->min); + + if ((is_dominated_by_max && dominates_min) /* node is in clique */ + || (irn == cli_head->max) + || (irn == cli_head->min)) + { + element = list_entry(cli_head->list.next, cli_element_t, list); + + it->curr_cli_element = element; + it->curr_cli_head = cli_head; + break; + } + else + { + cli_head = cli_head->next_cli_head; + } + } + it->curr_irn = irn; + + inc_irg_visited(get_irn_irg(irn)); + it->curr_irg_visited = get_irg_visited(get_irn_irg(irn)); + return; +} + +static ir_node *get_next_neighbour(cli_iter_t *it) +{ + ir_node *res = NULL; + cli_element_t *element = NULL; + cli_head_t *cli_head = NULL; + int is_dominated_by_max; + int dominates_min; + const ir_node *irn = it->curr_irn; + unsigned long irn_visited = 0; + + res = it->curr_cli_element->irn; + + /* get next element */ + + element = list_entry(it->curr_cli_element->list.next, cli_element_t, list); + irn_visited = get_irn_visited(element->irn); + + if ((cli_head_t *)element == it->curr_cli_head) /* end of clique, search next one */ + { + cli_head = cli_head->next_cli_head; + while(!(cli_head->next_cli_head == NULL)) + { + is_dominated_by_max = value_dominates(cli_head->max, irn); + dominates_min = value_dominates(irn, cli_head->min); + + if ((is_dominated_by_max && dominates_min) /* node is in clique */ + || (irn == cli_head->max) + || (irn == cli_head->min)) + { + element = list_entry(cli_head->list.next, cli_element_t, list); + + it->curr_cli_element = element; + it->curr_cli_head = cli_head; + break; + } + else + { + cli_head = cli_head->next_cli_head; + } + } + } + else /* get next element of this clique */ + { + it->curr_cli_element = element; + } + + if (irn_visited == it->curr_irg_visited) + { + irn = get_next_neighbour(it); + } + + set_irn_visited(res, it->curr_irg_visited); + + return res; +} + + +/* PUBLIC FUNCTIONS */ + +static void ifg_pointer_free(void *self) +{ + ifg_clique_t *ifg = self; + + free(self); +} + +static int ifg_pointer_connected(const void *self, const ir_node *a, const ir_node *b) +{ + cli_iter_t *it = NULL; + int connected = -1; + ir_node *irn = NULL; + + find_first_neighbour(self, it, a); + connected = 0; + irn = get_next_neighbour(it); + while (irn != NULL) + { + if (irn == b) + { + connected = 1; + } + irn = get_next_neighbour(it); + } + + return connected; +} + +static ir_node *ifg_pointer_neighbours_begin(const void *self, void *iter, const ir_node *irn) +{ + find_first_neighbour(self, iter, irn); + return get_next_neighbour(iter); +} + +static ir_node *ifg_pointer_neighbours_next(const void *self, void *iter) +{ + return get_next_neighbour(iter); +} + +static void ifg_pointer_neighbours_break(const void *self, void *iter) +{ + return; +} + +static ir_node *ifg_pointer_nodes_begin(const void *self, void *iter) +{ + find_nodes(self, iter); + return get_next_node(iter); +} + +static ir_node *ifg_pointer_nodes_next(const void *self, void *iter) +{ + return get_next_node(iter); +} + +static void ifg_pointer_nodes_break(const void *self, void *iter) +{ + return; +} + +static int ifg_pointer_degree(const void *self, const ir_node *irn) +{ + int degree = -1; + cli_iter_t *it = NULL; + + find_first_neighbour(self, it, irn); + degree = 0; + irn = get_next_neighbour(it); + while (irn != NULL) + { + degree++; + irn = get_next_neighbour(it); + } + + return degree; +} + +static const be_ifg_impl_t ifg_pointer_impl = { + sizeof(cli_iter_t), + 0, + 0, + ifg_pointer_free, + ifg_pointer_connected, + ifg_pointer_neighbours_begin, + ifg_pointer_neighbours_next, + ifg_pointer_neighbours_break, + ifg_pointer_nodes_begin, + ifg_pointer_nodes_next, + ifg_pointer_nodes_break, + NULL, + NULL, + NULL, + ifg_pointer_degree +}; + +be_ifg_t *be_ifg_pointer_new(const be_chordal_env_t *env) +{ + ifg_pointer_t *ifg = malloc(sizeof(*ifg)); + ifg->impl = &ifg_pointer_impl; + + ifg->cli_root = NULL; + ifg->env = env; + + ifg = build_neighbours(env); + + return (be_ifg_t *) ifg; +} + +#endif -- 2.20.1