4 * @author Sebastian Hack
6 * Copyright (C) 2005 Universitaet Karlsruhe
7 * Released under the GPL
19 #include "irgraph_t.h"
26 #include "bechordal_t.h"
28 typedef struct _cli_head_t {
29 struct list_head list;
30 struct _cli_head_t *next_cli_head;
35 typedef struct _ifg_clique_t {
36 const be_ifg_impl_t *impl;
37 const be_chordal_env_t *env;
40 cli_head_t *curr_cli_head;
43 typedef struct _cli_element_t {
44 struct list_head list;
48 typedef struct _cli_iter_t {
50 cli_head_t *curr_cli_head;
51 cli_element_t *curr_cli_element;
52 const ir_node *curr_irn;
53 bitset_t *visited_neighbours;
54 bitset_t *visited_nodes;
57 /* PRIVATE FUNCTIONS */
58 static cli_head_t *get_new_cli_head(ifg_clique_t *ifg)
61 cli_head_t *new_cli_head;
63 if (ifg->cli_root == NULL)
65 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
66 INIT_LIST_HEAD(&new_cli_head->list);
67 ifg->cli_root = new_cli_head;
71 cli_head = ifg->cli_root;
72 while(!(cli_head->next_cli_head == NULL))
74 cli_head = cli_head->next_cli_head;
76 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
77 INIT_LIST_HEAD(&new_cli_head->list);
78 cli_head->next_cli_head = new_cli_head;
81 new_cli_head->min = NULL;
82 new_cli_head->max = NULL;
83 new_cli_head->next_cli_head = NULL;
84 ifg->curr_cli_head = new_cli_head;
89 static cli_element_t *get_new_cli_element(ifg_clique_t *ifg)
91 cli_element_t *cli_element;
93 cli_element = obstack_alloc(&ifg->obst, sizeof(*cli_element));
94 INIT_LIST_HEAD(&cli_element->list);
99 static void write_clique(nodeset *live_set, ifg_clique_t *ifg)
104 ir_node *max_node = NULL;
105 ir_node *min_node = NULL;
106 cli_element_t *new_element = NULL;
107 cli_element_t *element = NULL;
108 cli_head_t *cli_head = get_new_cli_head(ifg);
111 foreach_nodeset(live_set, live_irn)
113 /* test if node is max or min dominator*/
114 test_node = live_irn;
115 if (max_node == NULL)
117 max_node = test_node;
118 min_node = test_node;
122 test_int = value_dominates(test_node, max_node);
125 max_node = test_node;
127 test_int = value_dominates(min_node, test_node);
130 min_node = test_node;
134 list_for_each_entry(cli_element_t, element, &cli_head->list, list){
135 if(element->irn == live_irn){
142 new_element = get_new_cli_element(ifg);
143 new_element->irn = live_irn;
144 list_add(&new_element->list, &cli_head->list) ;
148 cli_head->min = min_node;
149 cli_head->max = max_node;
152 static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...containing the node *irn */
155 cli_element_t *element;
157 int is_dominated_by_max;
160 if (it->curr_cli_head == NULL || it->curr_cli_head->next_cli_head == NULL) /* way back of recursion or this is the last clique */
162 it->curr_cli_head = NULL;
166 head = it->curr_cli_head->next_cli_head;
168 is_dominated_by_max = value_dominates(head->max, irn);
169 //dominates_min = value_dominates(irn, head->min);
171 if ((is_dominated_by_max) || (irn == head->max)) /* node could be in clique */
173 /* check if node is in clique */
174 list_for_each_entry(cli_element_t, element, &head->list, list)
176 if (&element->list != &head->list)
178 if (element->irn == irn)
179 { /* node is in clique */
180 it->curr_cli_head = head;
181 it->curr_cli_element = (void *) head; /* needed because the next element is searched with list.next of it->curr_cli_element */
187 if (it->curr_cli_head != head) /*node was not in clique */
189 it->curr_cli_head = head;
190 head = get_next_cli_head(irn, it);
195 it->curr_cli_head = head;
196 head = get_next_cli_head(irn, it);
201 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 ..*/
203 cli_element_t *element = it->curr_cli_element;
204 cli_head_t *head = it->curr_cli_head;
206 if (!head || it->curr_cli_element == NULL) /* way back of recursion or there are no more heads */
208 it->curr_cli_element = NULL;
213 element = list_entry(element->list.next, cli_element_t, list);
215 if (&element->list == &head->list) /* Clique has no more elements */
217 head = get_next_cli_head(irn, it);
218 element = get_next_element(irn, it);
221 if (element && element->irn == irn) /* the node you are searching neighbors for */
223 it->curr_cli_element = element;
224 element = get_next_element(irn, it);
227 it->curr_cli_element = element;
233 static void find_nodes(const ifg_clique_t *ifg, cli_iter_t *it)
235 cli_element_t *element;
236 cli_head_t *cli_head = ifg->cli_root;
238 bitset_t *bitset_visnodes = bitset_malloc(get_irg_last_idx(ifg->env->irg));
240 it->visited_nodes = bitset_visnodes;
241 it->curr_cli_head = cli_head;
243 assert(cli_head && "There is no root entry to work on!");
245 if (cli_head->list.next != &cli_head->list) /* if cli_head contains an element */
247 element = list_entry(cli_head->list.next, cli_element_t, list);
248 it->curr_cli_element = element;
254 static ir_node *get_next_node(cli_iter_t *it)
256 cli_head_t *cli_head = NULL;
257 cli_element_t *element = it->curr_cli_element;
264 if (!(&it->curr_cli_head->list == element->list.next))
267 element = list_entry(element->list.next, cli_element_t, list);
268 it->curr_cli_element = element;
270 else /* reached end of clique */
272 cli_head = it->curr_cli_head;
273 if (!(cli_head->next_cli_head == NULL))
276 cli_head = cli_head->next_cli_head;
277 it->curr_cli_head = cli_head;
278 element = list_entry(cli_head->list.next, cli_element_t, list);
279 it->curr_cli_element = element;
283 it->curr_cli_head = NULL;
284 it->curr_cli_element = NULL;
290 if (bitset_is_set(it->visited_nodes, get_irn_idx(irn)))
292 irn = get_next_node(it);
296 bitset_set(it->visited_nodes, get_irn_idx(irn));
303 static void find_neighbour_walker(ir_node *bl, void *data)
305 ifg_clique_t *ifg = data;
306 struct list_head *head = get_block_border_head(ifg->env, bl);
309 nodeset *live = new_nodeset(ifg->env->cls->n_regs);
311 assert(is_Block(bl) && "There is no block to work on.");
313 foreach_border_head(head, b) /* follow the borders of the block */
315 ir_node *irn = b->irn;
317 if (b->is_def) /* b is a new node */
319 nodeset_insert(live, irn);
327 if (was_def == 1) /* if there is a USE after a DEF... */
329 write_clique(live, ifg); /* ...add the clique. */
332 nodeset_remove(live, irn);
338 static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const ir_node *irn)
340 cli_head_t *cli_head = ifg->cli_root;
341 cli_element_t *element;
342 bitset_t *bitset_visneighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
344 int is_dominated_by_max = 0;
345 int dominates_min = 0;
346 int is_in_clique = 0;
348 it->curr_cli_head = cli_head;
350 it->visited_neighbours = bitset_visneighbours;
352 assert(cli_head && "There is no root entry for a cli_head.");
354 is_dominated_by_max = value_dominates(cli_head->max, irn);
355 dominates_min = value_dominates(irn, cli_head->min);
357 if ((is_dominated_by_max) || (irn == cli_head->max)) /* node could be in clique */
359 /* check if node is in clique */
360 list_for_each_entry(cli_element_t, element, &cli_head->list, list)
362 if (element->irn == irn) /* node is in clique */
364 it->curr_cli_element = (void *) cli_head; /* needed because the next element is searched with list.next of it->curr_cli_element */
366 element = get_next_element(irn, it);
373 cli_head = get_next_cli_head(irn, it);
374 element = get_next_element(irn, it);
377 it->curr_cli_element = element;
383 static ir_node *get_next_neighbour(cli_iter_t *it)
386 cli_head_t *cli_head = it->curr_cli_head;
387 const ir_node *irn = it->curr_irn;
389 if (it->curr_cli_element != NULL)
390 res = it->curr_cli_element->irn;
394 it->curr_cli_element = get_next_element(irn, it);
398 if (bitset_contains_irn(it->visited_neighbours, res))
400 res = get_next_neighbour(it);
404 bitset_set(it->visited_neighbours, get_irn_idx(res));
412 /* PUBLIC FUNCTIONS */
414 static void ifg_clique_free(void *self)
416 ifg_clique_t *ifg = self;
417 obstack_free(&ifg->obst, NULL);
422 static int ifg_clique_connected(const ifg_clique_t *ifg, const ir_node *a, const ir_node *b)
428 find_first_neighbour(ifg, &it, a);
430 irn = get_next_neighbour(&it);
438 irn = get_next_neighbour(&it);
444 static ir_node *ifg_clique_neighbours_begin(const void *self, void *iter, const ir_node *irn)
446 find_first_neighbour(self, iter, irn);
447 return get_next_neighbour(iter);
450 static ir_node *ifg_clique_neighbours_next(const void *self, void *iter)
452 return get_next_neighbour(iter);
455 static void ifg_clique_neighbours_break(const void *self, void *iter)
457 cli_iter_t *it = iter;
459 bitset_free(it->visited_neighbours);
464 static ir_node *ifg_clique_nodes_begin(const void *self, void *iter)
466 find_nodes(self, iter);
467 return get_next_node(iter);
470 static ir_node *ifg_clique_nodes_next(const void *self, void *iter)
472 return get_next_node(iter);
475 static void ifg_clique_nodes_break(const void *self, void *iter)
477 cli_iter_t *it = iter;
479 bitset_free(it->visited_nodes);
484 static int ifg_clique_degree(const void *self, const ir_node *irn)
489 find_first_neighbour(self, &it, irn);
491 irn = get_next_neighbour(&it);
495 irn = get_next_neighbour(&it);
501 static const be_ifg_impl_t ifg_clique_impl = {
506 ifg_clique_connected,
507 ifg_clique_neighbours_begin,
508 ifg_clique_neighbours_next,
509 ifg_clique_neighbours_break,
510 ifg_clique_nodes_begin,
511 ifg_clique_nodes_next,
512 ifg_clique_nodes_break,
519 be_ifg_t *be_ifg_clique_new(const be_chordal_env_t *env)
521 ifg_clique_t *ifg = xmalloc(sizeof(*ifg));
523 ifg->impl = &ifg_clique_impl;
526 ifg->cli_root = NULL;
527 obstack_init(&ifg->obst);
529 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
531 obstack_finish(&ifg->obst);
532 return (be_ifg_t *) ifg;