4 * @author Sebastian Hack
6 * Copyright (C) 2005 Universitaet Karlsruhe
7 * Released under the GPL
19 #include "irgraph_t.h"
25 #include "bechordal_t.h"
27 typedef struct _cli_head_t {
28 struct list_head list;
29 struct _cli_head_t *next_cli_head;
34 typedef struct _ifg_clique_t {
35 const be_ifg_impl_t *impl;
36 const be_chordal_env_t *env;
39 cli_head_t *curr_cli_head;
40 bitset_t *visited_nodes;
41 bitset_t *visited_neighbours;
44 typedef struct _cli_element_t {
45 struct list_head list;
49 typedef struct _cli_iter_t {
51 cli_head_t *curr_cli_head;
52 cli_element_t *curr_cli_element;
53 const ir_node *curr_irn;
56 /* PRIVATE FUNCTIONS */
57 static cli_head_t *get_new_cli_head(ifg_clique_t *ifg)
60 cli_head_t *new_cli_head;
62 if (ifg->cli_root == NULL)
64 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
65 INIT_LIST_HEAD(&new_cli_head->list);
66 ifg->cli_root = new_cli_head;
70 cli_head = ifg->cli_root;
71 while(!(cli_head->next_cli_head == NULL))
73 cli_head = cli_head->next_cli_head;
75 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
76 INIT_LIST_HEAD(&new_cli_head->list);
77 cli_head->next_cli_head = new_cli_head;
80 new_cli_head->min = NULL;
81 new_cli_head->max = NULL;
82 new_cli_head->next_cli_head = NULL;
83 ifg->curr_cli_head = new_cli_head;
88 static cli_element_t *get_new_cli_element(ifg_clique_t *ifg)
90 cli_element_t *cli_element;
92 cli_element = obstack_alloc(&ifg->obst, sizeof(*cli_element));
93 INIT_LIST_HEAD(&cli_element->list);
98 static void write_clique(nodeset *live_set, ifg_clique_t *ifg)
103 ir_node *max_node = NULL;
104 ir_node *min_node = NULL;
105 cli_element_t *new_element = NULL;
106 cli_element_t *element = NULL;
107 cli_head_t *cli_head = get_new_cli_head(ifg);
110 foreach_nodeset(live_set, live_irn)
112 /* test if node is max or min dominator*/
113 test_node = live_irn;
114 if (max_node == NULL)
116 max_node = test_node;
117 min_node = test_node;
121 test_int = value_dominates(test_node, max_node);
124 max_node = test_node;
126 test_int = value_dominates(min_node, test_node);
129 min_node = test_node;
133 list_for_each_entry(cli_element_t, element, &cli_head->list, list){
134 if(element->irn == live_irn){
141 new_element = get_new_cli_element(ifg);
142 new_element->irn = live_irn;
143 list_add(&new_element->list, &cli_head->list) ;
147 cli_head->min = min_node;
148 cli_head->max = max_node;
151 static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...containing the node *irn */
154 cli_element_t *element;
156 int is_dominated_by_max;
159 if (it->curr_cli_head == NULL || it->curr_cli_head->next_cli_head == NULL) /* way back of recursion or this is the last clique */
161 it->curr_cli_head = NULL;
165 head = it->curr_cli_head->next_cli_head;
167 is_dominated_by_max = value_dominates(head->max, irn);
168 //dominates_min = value_dominates(irn, head->min);
170 if(head->min->node_nr == 2000)
173 if ((is_dominated_by_max) || (irn == head->max)) /* node could be in clique */
175 /* check if node is in clique */
176 list_for_each_entry(cli_element_t, element, &head->list, list)
178 if (&element->list != &head->list)
180 if (element->irn == irn)
181 { /* node is in clique */
182 it->curr_cli_head = head;
183 it->curr_cli_element = (void *) head; /* needed because the next element is searched with list.next of it->curr_cli_element */
189 if (it->curr_cli_head != head) /*node was not in clique */
191 it->curr_cli_head = head;
192 head = get_next_cli_head(irn, it);
197 it->curr_cli_head = head;
198 head = get_next_cli_head(irn, it);
203 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 ..*/
205 cli_element_t *element = it->curr_cli_element;
206 cli_head_t *head = it->curr_cli_head;
208 if (!head || it->curr_cli_element == NULL) /* way back of recursion or there are no more heads */
210 it->curr_cli_element = NULL;
215 element = list_entry(element->list.next, cli_element_t, list);
217 if (&element->list == &head->list) /* Clique has no more elements */
219 head = get_next_cli_head(irn, it);
220 element = get_next_element(irn, it);
223 if (element != NULL && element->irn == irn) /* the node you are searching neighbors for */
225 it->curr_cli_element = element;
226 element = get_next_element(irn, it);
229 it->curr_cli_element = element;
235 static void find_nodes(const ifg_clique_t *ifg, cli_iter_t *it)
237 cli_element_t *element;
238 cli_head_t *cli_head = ifg->cli_root;
240 bitset_clear_all(ifg->visited_nodes);
242 assert(cli_head && "There is no root entry to work on!");
244 it->curr_cli_head = cli_head;
246 if (cli_head->list.next != &cli_head->list) /* if cli_head contains an element */
248 element = list_entry(cli_head->list.next, cli_element_t, list);
249 it->curr_cli_element = element;
255 static ir_node *get_next_node(cli_iter_t *it)
257 cli_head_t *cli_head = NULL;
258 cli_element_t *element = it->curr_cli_element;
265 if (!(&it->curr_cli_head->list == element->list.next))
268 element = list_entry(element->list.next, cli_element_t, list);
269 it->curr_cli_element = element;
271 else /* reached end of clique */
273 cli_head = it->curr_cli_head;
274 if (!(cli_head->next_cli_head == NULL))
277 cli_head = cli_head->next_cli_head;
278 it->curr_cli_head = cli_head;
279 element = list_entry(cli_head->list.next, cli_element_t, list);
280 it->curr_cli_element = element;
284 it->curr_cli_head = NULL;
285 it->curr_cli_element = NULL;
291 if (bitset_is_set(it->ifg->visited_nodes, get_irn_idx(irn)))
293 irn = get_next_node(it);
297 bitset_set(it->ifg->visited_nodes, get_irn_idx(irn));
304 static void find_neighbour_walker(ir_node *bl, void *data)
306 ifg_clique_t *ifg = data;
307 struct list_head *head = get_block_border_head(ifg->env, bl);
310 nodeset *live = new_nodeset(ifg->env->cls->n_regs);
312 assert(is_Block(bl) && "There is no block to work on.");
314 foreach_border_head(head, b) /* follow the borders of the block */
316 ir_node *irn = b->irn;
318 // if (b->irn->node_nr == 1869)
321 if (b->is_def) /* b is a new node */
323 nodeset_insert(live, irn);
331 if (was_def == 1) /* if there is a USE after a DEF... */
333 write_clique(live, ifg); /* ...add the clique. */
336 nodeset_remove(live, irn);
342 static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const ir_node *irn)
344 cli_head_t *cli_head = ifg->cli_root;
345 cli_element_t *element;
347 int is_dominated_by_max = 0;
348 int dominates_min = 0;
349 int is_in_clique = 0;
351 it->curr_cli_head = cli_head;
353 bitset_clear_all(it->ifg->visited_neighbours);
355 assert(cli_head && "There is no root entry for a cli_head.");
357 is_dominated_by_max = value_dominates(cli_head->max, irn);
358 dominates_min = value_dominates(irn, cli_head->min);
360 if ((is_dominated_by_max) || (irn == cli_head->max)) /* node could be in clique */
362 /* check if node is in clique */
363 list_for_each_entry(cli_element_t, element, &cli_head->list, list)
365 if (&element->list != &cli_head->list)
367 if (element->irn == irn)
368 { /* node is in clique */
369 it->curr_cli_element = (void *) cli_head; /* needed because the next element is searched with list.next of it->curr_cli_element */
371 element = get_next_element(irn, it);
379 cli_head = get_next_cli_head(irn, it);
380 element = get_next_element(irn, it);
383 it->curr_cli_element = element;
389 static ir_node *get_next_neighbour(cli_iter_t *it)
392 cli_element_t *element;
393 cli_head_t *cli_head = it->curr_cli_head;
394 const ir_node *irn = it->curr_irn;
396 if (it->curr_cli_element != NULL)
397 res = it->curr_cli_element->irn;
401 element = get_next_element(irn, it);
403 if (element == NULL) /* no more elements in this clique */
405 it->curr_cli_element = NULL;
409 it->curr_cli_element = element;
414 if (bitset_is_set(it->ifg->visited_neighbours, get_irn_idx(res)))
416 res = get_next_neighbour(it);
417 // if (res == NULL) /* there are no more neighbours to return */
424 bitset_set(it->ifg->visited_neighbours, get_irn_idx(res));
432 /* PUBLIC FUNCTIONS */
434 static void ifg_clique_free(void *self)
436 ifg_clique_t *ifg = self;
437 obstack_free(&ifg->obst, NULL);
442 static int ifg_clique_connected(const ifg_clique_t *ifg, const ir_node *a, const ir_node *b)
448 find_first_neighbour(ifg, &it, a);
450 irn = get_next_neighbour(&it);
458 irn = get_next_neighbour(&it);
464 static ir_node *ifg_clique_neighbours_begin(const void *self, void *iter, const ir_node *irn)
466 find_first_neighbour(self, iter, irn);
467 return get_next_neighbour(iter);
470 static ir_node *ifg_clique_neighbours_next(const void *self, void *iter)
472 return get_next_neighbour(iter);
475 static void ifg_clique_neighbours_break(const void *self, void *iter)
480 static ir_node *ifg_clique_nodes_begin(const void *self, void *iter)
482 find_nodes(self, iter);
483 return get_next_node(iter);
486 static ir_node *ifg_clique_nodes_next(const void *self, void *iter)
488 return get_next_node(iter);
491 static void ifg_clique_nodes_break(const void *self, void *iter)
496 static int ifg_clique_degree(const void *self, const ir_node *irn)
499 cli_iter_t *it = NULL;
501 find_first_neighbour(self, it, irn);
503 irn = get_next_neighbour(it);
507 irn = get_next_neighbour(it);
513 static const be_ifg_impl_t ifg_clique_impl = {
518 ifg_clique_connected,
519 ifg_clique_neighbours_begin,
520 ifg_clique_neighbours_next,
521 ifg_clique_neighbours_break,
522 ifg_clique_nodes_begin,
523 ifg_clique_nodes_next,
524 ifg_clique_nodes_break,
531 be_ifg_t *be_ifg_clique_new(const be_chordal_env_t *env)
533 ifg_clique_t *ifg = xmalloc(sizeof(*ifg));
534 bitset_t *bitset_visnodes = bitset_malloc(get_irg_last_idx(env->irg));
535 bitset_t *bitset_visneighbours = bitset_malloc(get_irg_last_idx(env->irg));
536 ifg->visited_nodes = bitset_visnodes;
537 ifg->visited_neighbours = bitset_visneighbours;
538 ifg->impl = &ifg_clique_impl;
541 ifg->cli_root = NULL;
542 obstack_init(&ifg->obst);
544 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
546 obstack_finish(&ifg->obst);
547 return (be_ifg_t *) ifg;