2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Clique calculation for chordal ifg.
23 * @author Sebastian Hack
35 #include "irgraph_t.h"
41 #include "beintlive_t.h"
43 #include "beifg_impl.h"
44 #include "bechordal_t.h"
46 typedef struct _cli_head_t {
47 struct list_head list;
48 struct _cli_head_t *next_cli_head;
53 typedef struct _ifg_clique_t {
54 const be_ifg_impl_t *impl;
55 const be_chordal_env_t *env;
58 cli_head_t *curr_cli_head;
61 typedef struct _cli_element_t {
62 struct list_head list;
66 typedef struct _cli_iter_t {
67 const ifg_clique_t *ifg;
68 cli_head_t *curr_cli_head;
69 cli_element_t *curr_cli_element;
70 const ir_node *curr_irn;
71 bitset_t *visited_neighbours;
72 bitset_t *visited_nodes;
75 /* PRIVATE FUNCTIONS */
76 static cli_head_t *get_new_cli_head(ifg_clique_t *ifg)
79 cli_head_t *new_cli_head;
81 if (ifg->cli_root == NULL)
83 new_cli_head = OALLOC(&ifg->obst, cli_head_t);
84 INIT_LIST_HEAD(&new_cli_head->list);
85 ifg->cli_root = new_cli_head;
89 cli_head = ifg->cli_root;
90 while (!(cli_head->next_cli_head == NULL))
92 cli_head = cli_head->next_cli_head;
94 new_cli_head = OALLOC(&ifg->obst, cli_head_t);
95 INIT_LIST_HEAD(&new_cli_head->list);
96 cli_head->next_cli_head = new_cli_head;
99 new_cli_head->min = NULL;
100 new_cli_head->max = NULL;
101 new_cli_head->next_cli_head = NULL;
102 ifg->curr_cli_head = new_cli_head;
107 static cli_element_t *get_new_cli_element(ifg_clique_t *ifg)
109 cli_element_t *cli_element;
111 cli_element = OALLOC(&ifg->obst, cli_element_t);
112 INIT_LIST_HEAD(&cli_element->list);
117 static void write_clique(ir_nodeset_t *live_set, ifg_clique_t *ifg)
122 ir_node *max_node = NULL;
123 ir_node *min_node = NULL;
124 cli_element_t *new_element = NULL;
125 cli_element_t *element = NULL;
126 cli_head_t *cli_head = get_new_cli_head(ifg);
128 ir_nodeset_iterator_t iter;
130 foreach_ir_nodeset(live_set, live_irn, iter)
132 /* test if node is max or min dominator*/
133 test_node = live_irn;
134 if (max_node == NULL)
136 max_node = test_node;
137 min_node = test_node;
141 test_int = value_dominates(test_node, max_node);
144 max_node = test_node;
146 test_int = value_dominates(min_node, test_node);
149 min_node = test_node;
153 list_for_each_entry(cli_element_t, element, &cli_head->list, list){
154 if (element->irn == live_irn){
161 new_element = get_new_cli_element(ifg);
162 new_element->irn = live_irn;
163 list_add(&new_element->list, &cli_head->list) ;
167 cli_head->min = min_node;
168 cli_head->max = max_node;
171 static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...containing the node *irn */
174 cli_element_t *element;
176 int is_dominated_by_max;
179 if (it->curr_cli_head == NULL || it->curr_cli_head->next_cli_head == NULL) /* way back of recursion or this is the last clique */
181 it->curr_cli_head = NULL;
185 head = it->curr_cli_head->next_cli_head;
187 is_dominated_by_max = value_dominates(head->max, irn);
188 //dominates_min = value_dominates(irn, head->min);
190 if ((is_dominated_by_max) || (irn == head->max)) /* node could be in clique */
192 /* check if node is in clique */
193 list_for_each_entry(cli_element_t, element, &head->list, list)
195 if (&element->list != &head->list)
197 if (element->irn == irn)
199 /* node is in clique */
200 it->curr_cli_head = head;
201 /* needed because the next element is searched with list.next of it->curr_cli_element */
202 it->curr_cli_element = (void *) head;
208 if (it->curr_cli_head != head) /*node was not in clique */
210 it->curr_cli_head = head;
211 head = get_next_cli_head(irn, it);
216 it->curr_cli_head = head;
217 head = get_next_cli_head(irn, it);
222 /* ... of the current clique, returns NULL if there were no more elements ..*/
223 static cli_element_t *get_next_element(const ir_node *irn, cli_iter_t *it)
225 cli_element_t *element = it->curr_cli_element;
226 cli_head_t *head = it->curr_cli_head;
228 if (!head || it->curr_cli_element == NULL) /* way back of recursion or there are no more heads */
230 it->curr_cli_element = NULL;
235 element = list_entry(element->list.next, cli_element_t, list);
237 if (&element->list == &head->list) /* Clique has no more elements */
239 head = get_next_cli_head(irn, it);
240 element = get_next_element(irn, it);
243 if (element && element->irn == irn) /* the node you are searching neighbors for */
245 it->curr_cli_element = element;
246 element = get_next_element(irn, it);
249 it->curr_cli_element = element;
255 static void find_nodes(const ifg_clique_t *ifg, cli_iter_t *it)
257 cli_element_t *element;
258 cli_head_t *cli_head = ifg->cli_root;
260 bitset_t *bitset_visnodes = bitset_malloc(get_irg_last_idx(ifg->env->irg));
262 it->visited_nodes = bitset_visnodes;
263 it->curr_cli_head = cli_head;
265 assert(cli_head && "There is no root entry to work on!");
267 if (cli_head->list.next != &cli_head->list) /* if cli_head contains an element */
269 element = list_entry(cli_head->list.next, cli_element_t, list);
270 it->curr_cli_element = element;
274 static ir_node *get_next_node(cli_iter_t *it)
276 cli_head_t *cli_head = NULL;
277 cli_element_t *element = it->curr_cli_element;
284 if (!(&it->curr_cli_head->list == element->list.next))
287 element = list_entry(element->list.next, cli_element_t, list);
288 it->curr_cli_element = element;
290 else /* reached end of clique */
292 cli_head = it->curr_cli_head;
293 if (!(cli_head->next_cli_head == NULL))
296 cli_head = cli_head->next_cli_head;
297 it->curr_cli_head = cli_head;
298 element = list_entry(cli_head->list.next, cli_element_t, list);
299 it->curr_cli_element = element;
303 it->curr_cli_head = NULL;
304 it->curr_cli_element = NULL;
310 if (bitset_is_set(it->visited_nodes, get_irn_idx(irn)))
312 irn = get_next_node(it);
316 bitset_set(it->visited_nodes, get_irn_idx(irn));
323 static void find_neighbour_walker(ir_node *bl, void *data)
325 ifg_clique_t *ifg = data;
326 struct list_head *head = get_block_border_head(ifg->env, bl);
331 ir_nodeset_init(&live);
333 assert(is_Block(bl) && "There is no block to work on.");
335 foreach_border_head(head, b) /* follow the borders of the block */
337 ir_node *irn = b->irn;
339 if (b->is_def) /* b is a new node */
341 ir_nodeset_insert(&live, irn);
349 if (was_def == 1) /* if there is a USE after a DEF... */
351 write_clique(&live, ifg); /* ...add the clique. */
354 ir_nodeset_remove(&live, irn);
357 ir_nodeset_destroy(&live);
360 static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const ir_node *irn)
362 cli_head_t *cli_head = ifg->cli_root;
363 cli_element_t *element;
364 bitset_t *bitset_visneighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
366 int is_dominated_by_max = 0;
367 int dominates_min = 0;
368 int is_in_clique = 0;
370 it->curr_cli_head = cli_head;
372 it->visited_neighbours = bitset_visneighbours;
374 assert(cli_head && "There is no root entry for a cli_head.");
376 is_dominated_by_max = value_dominates(cli_head->max, irn);
377 dominates_min = value_dominates(irn, cli_head->min);
379 if ((is_dominated_by_max) || (irn == cli_head->max)) /* node could be in clique */
381 /* check if node is in clique */
382 list_for_each_entry(cli_element_t, element, &cli_head->list, list)
384 if (element->irn == irn) /* node is in clique */
386 it->curr_cli_element = (void *) cli_head; /* needed because the next element is searched with list.next of it->curr_cli_element */
388 element = get_next_element(irn, it);
395 cli_head = get_next_cli_head(irn, it);
396 element = get_next_element(irn, it);
399 it->curr_cli_element = element;
403 static ir_node *get_next_neighbour(cli_iter_t *it)
406 const ir_node *irn = it->curr_irn;
408 if (it->curr_cli_element != NULL)
409 res = it->curr_cli_element->irn;
413 it->curr_cli_element = get_next_element(irn, it);
417 if (bitset_contains_irn(it->visited_neighbours, res))
419 res = get_next_neighbour(it);
423 bitset_set(it->visited_neighbours, get_irn_idx(res));
431 /* PUBLIC FUNCTIONS */
433 static void ifg_clique_free(void *self)
435 ifg_clique_t *ifg = self;
436 obstack_free(&ifg->obst, NULL);
441 static int ifg_clique_connected(const void *self, const ir_node *a, const ir_node *b)
443 const ifg_clique_t *ifg = self;
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)
473 return get_next_neighbour(iter);
476 static void ifg_clique_neighbours_break(const void *self, void *iter)
478 cli_iter_t *it = iter;
481 bitset_free(it->visited_neighbours);
484 static ir_node *ifg_clique_nodes_begin(const void *self, void *iter)
486 find_nodes(self, iter);
487 return get_next_node(iter);
490 static ir_node *ifg_clique_nodes_next(const void *self, void *iter)
493 return get_next_node(iter);
496 static void ifg_clique_nodes_break(const void *self, void *iter)
498 cli_iter_t *it = iter;
501 bitset_free(it->visited_nodes);
504 static int ifg_clique_degree(const void *self, const ir_node *irn)
509 find_first_neighbour(self, &it, irn);
511 irn = get_next_neighbour(&it);
515 irn = get_next_neighbour(&it);
521 static const be_ifg_impl_t ifg_clique_impl = {
526 ifg_clique_connected,
527 ifg_clique_neighbours_begin,
528 ifg_clique_neighbours_next,
529 ifg_clique_neighbours_break,
530 ifg_clique_nodes_begin,
531 ifg_clique_nodes_next,
532 ifg_clique_nodes_break,
539 be_ifg_t *be_ifg_clique_new(const be_chordal_env_t *env)
541 ifg_clique_t *ifg = XMALLOC(ifg_clique_t);
543 ifg->impl = &ifg_clique_impl;
546 ifg->cli_root = NULL;
547 obstack_init(&ifg->obst);
549 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
551 obstack_finish(&ifg->obst);
552 return (be_ifg_t *) ifg;