2 * Copyright (C) 1995-2007 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
37 #include "irgraph_t.h"
45 #include "bechordal_t.h"
46 #include "benodesets.h"
48 typedef struct _cli_head_t {
49 struct list_head list;
50 struct _cli_head_t *next_cli_head;
55 typedef struct _ifg_clique_t {
56 const be_ifg_impl_t *impl;
57 const be_chordal_env_t *env;
60 cli_head_t *curr_cli_head;
63 typedef struct _cli_element_t {
64 struct list_head list;
68 typedef struct _cli_iter_t {
69 const ifg_clique_t *ifg;
70 cli_head_t *curr_cli_head;
71 cli_element_t *curr_cli_element;
72 const ir_node *curr_irn;
73 bitset_t *visited_neighbours;
74 bitset_t *visited_nodes;
77 /* PRIVATE FUNCTIONS */
78 static cli_head_t *get_new_cli_head(ifg_clique_t *ifg)
81 cli_head_t *new_cli_head;
83 if (ifg->cli_root == NULL)
85 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
86 INIT_LIST_HEAD(&new_cli_head->list);
87 ifg->cli_root = new_cli_head;
91 cli_head = ifg->cli_root;
92 while(!(cli_head->next_cli_head == NULL))
94 cli_head = cli_head->next_cli_head;
96 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
97 INIT_LIST_HEAD(&new_cli_head->list);
98 cli_head->next_cli_head = new_cli_head;
101 new_cli_head->min = NULL;
102 new_cli_head->max = NULL;
103 new_cli_head->next_cli_head = NULL;
104 ifg->curr_cli_head = new_cli_head;
109 static cli_element_t *get_new_cli_element(ifg_clique_t *ifg)
111 cli_element_t *cli_element;
113 cli_element = obstack_alloc(&ifg->obst, sizeof(*cli_element));
114 INIT_LIST_HEAD(&cli_element->list);
119 static void write_clique(nodeset *live_set, ifg_clique_t *ifg)
124 ir_node *max_node = NULL;
125 ir_node *min_node = NULL;
126 cli_element_t *new_element = NULL;
127 cli_element_t *element = NULL;
128 cli_head_t *cli_head = get_new_cli_head(ifg);
131 foreach_nodeset(live_set, live_irn)
133 /* test if node is max or min dominator*/
134 test_node = live_irn;
135 if (max_node == NULL)
137 max_node = test_node;
138 min_node = test_node;
142 test_int = value_dominates(test_node, max_node);
145 max_node = test_node;
147 test_int = value_dominates(min_node, test_node);
150 min_node = test_node;
154 list_for_each_entry(cli_element_t, element, &cli_head->list, list){
155 if(element->irn == live_irn){
162 new_element = get_new_cli_element(ifg);
163 new_element->irn = live_irn;
164 list_add(&new_element->list, &cli_head->list) ;
168 cli_head->min = min_node;
169 cli_head->max = max_node;
172 static cli_head_t *get_next_cli_head(const ir_node *irn, cli_iter_t *it) /* ...containing the node *irn */
175 cli_element_t *element;
177 int is_dominated_by_max;
180 if (it->curr_cli_head == NULL || it->curr_cli_head->next_cli_head == NULL) /* way back of recursion or this is the last clique */
182 it->curr_cli_head = NULL;
186 head = it->curr_cli_head->next_cli_head;
188 is_dominated_by_max = value_dominates(head->max, irn);
189 //dominates_min = value_dominates(irn, head->min);
191 if ((is_dominated_by_max) || (irn == head->max)) /* node could be in clique */
193 /* check if node is in clique */
194 list_for_each_entry(cli_element_t, element, &head->list, list)
196 if (&element->list != &head->list)
198 if (element->irn == irn)
200 /* node is in clique */
201 it->curr_cli_head = head;
202 /* needed because the next element is searched with list.next of it->curr_cli_element */
203 it->curr_cli_element = (void *) head;
209 if (it->curr_cli_head != head) /*node was not in clique */
211 it->curr_cli_head = head;
212 head = get_next_cli_head(irn, it);
217 it->curr_cli_head = head;
218 head = get_next_cli_head(irn, it);
223 /* ... of the current clique, returns NULL if there were no more elements ..*/
224 static cli_element_t *get_next_element(const ir_node *irn, cli_iter_t *it)
226 cli_element_t *element = it->curr_cli_element;
227 cli_head_t *head = it->curr_cli_head;
229 if (!head || it->curr_cli_element == NULL) /* way back of recursion or there are no more heads */
231 it->curr_cli_element = NULL;
236 element = list_entry(element->list.next, cli_element_t, list);
238 if (&element->list == &head->list) /* Clique has no more elements */
240 head = get_next_cli_head(irn, it);
241 element = get_next_element(irn, it);
244 if (element && element->irn == irn) /* the node you are searching neighbors for */
246 it->curr_cli_element = element;
247 element = get_next_element(irn, it);
250 it->curr_cli_element = element;
256 static void find_nodes(const ifg_clique_t *ifg, cli_iter_t *it)
258 cli_element_t *element;
259 cli_head_t *cli_head = ifg->cli_root;
261 bitset_t *bitset_visnodes = bitset_malloc(get_irg_last_idx(ifg->env->irg));
263 it->visited_nodes = bitset_visnodes;
264 it->curr_cli_head = cli_head;
266 assert(cli_head && "There is no root entry to work on!");
268 if (cli_head->list.next != &cli_head->list) /* if cli_head contains an element */
270 element = list_entry(cli_head->list.next, cli_element_t, list);
271 it->curr_cli_element = element;
277 static ir_node *get_next_node(cli_iter_t *it)
279 cli_head_t *cli_head = NULL;
280 cli_element_t *element = it->curr_cli_element;
287 if (!(&it->curr_cli_head->list == element->list.next))
290 element = list_entry(element->list.next, cli_element_t, list);
291 it->curr_cli_element = element;
293 else /* reached end of clique */
295 cli_head = it->curr_cli_head;
296 if (!(cli_head->next_cli_head == NULL))
299 cli_head = cli_head->next_cli_head;
300 it->curr_cli_head = cli_head;
301 element = list_entry(cli_head->list.next, cli_element_t, list);
302 it->curr_cli_element = element;
306 it->curr_cli_head = NULL;
307 it->curr_cli_element = NULL;
313 if (bitset_is_set(it->visited_nodes, get_irn_idx(irn)))
315 irn = get_next_node(it);
319 bitset_set(it->visited_nodes, get_irn_idx(irn));
326 static void find_neighbour_walker(ir_node *bl, void *data)
328 ifg_clique_t *ifg = data;
329 struct list_head *head = get_block_border_head(ifg->env, bl);
331 nodeset *live = new_nodeset(ifg->env->cls->n_regs);
334 assert(is_Block(bl) && "There is no block to work on.");
336 foreach_border_head(head, b) /* follow the borders of the block */
338 ir_node *irn = b->irn;
340 if (b->is_def) /* b is a new node */
342 nodeset_insert(live, irn);
350 if (was_def == 1) /* if there is a USE after a DEF... */
352 write_clique(live, ifg); /* ...add the clique. */
355 nodeset_remove(live, irn);
361 static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const ir_node *irn)
363 cli_head_t *cli_head = ifg->cli_root;
364 cli_element_t *element;
365 bitset_t *bitset_visneighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
367 int is_dominated_by_max = 0;
368 int dominates_min = 0;
369 int is_in_clique = 0;
371 it->curr_cli_head = cli_head;
373 it->visited_neighbours = bitset_visneighbours;
375 assert(cli_head && "There is no root entry for a cli_head.");
377 is_dominated_by_max = value_dominates(cli_head->max, irn);
378 dominates_min = value_dominates(irn, cli_head->min);
380 if ((is_dominated_by_max) || (irn == cli_head->max)) /* node could be in clique */
382 /* check if node is in clique */
383 list_for_each_entry(cli_element_t, element, &cli_head->list, list)
385 if (element->irn == irn) /* node is in clique */
387 it->curr_cli_element = (void *) cli_head; /* needed because the next element is searched with list.next of it->curr_cli_element */
389 element = get_next_element(irn, it);
396 cli_head = get_next_cli_head(irn, it);
397 element = get_next_element(irn, it);
400 it->curr_cli_element = element;
406 static ir_node *get_next_neighbour(cli_iter_t *it)
409 const ir_node *irn = it->curr_irn;
411 if (it->curr_cli_element != NULL)
412 res = it->curr_cli_element->irn;
416 it->curr_cli_element = get_next_element(irn, it);
420 if (bitset_contains_irn(it->visited_neighbours, res))
422 res = get_next_neighbour(it);
426 bitset_set(it->visited_neighbours, get_irn_idx(res));
434 /* PUBLIC FUNCTIONS */
436 static void ifg_clique_free(void *self)
438 ifg_clique_t *ifg = self;
439 obstack_free(&ifg->obst, NULL);
444 static int ifg_clique_connected(const void *self, const ir_node *a, const ir_node *b)
446 const ifg_clique_t *ifg = self;
451 find_first_neighbour(ifg, &it, a);
453 irn = get_next_neighbour(&it);
461 irn = get_next_neighbour(&it);
467 static ir_node *ifg_clique_neighbours_begin(const void *self, void *iter, const ir_node *irn)
469 find_first_neighbour(self, iter, irn);
470 return get_next_neighbour(iter);
473 static ir_node *ifg_clique_neighbours_next(const void *self, void *iter)
475 return get_next_neighbour(iter);
478 static void ifg_clique_neighbours_break(const void *self, void *iter)
480 cli_iter_t *it = iter;
482 bitset_free(it->visited_neighbours);
487 static ir_node *ifg_clique_nodes_begin(const void *self, void *iter)
489 find_nodes(self, iter);
490 return get_next_node(iter);
493 static ir_node *ifg_clique_nodes_next(const void *self, void *iter)
495 return get_next_node(iter);
498 static void ifg_clique_nodes_break(const void *self, void *iter)
500 cli_iter_t *it = iter;
502 bitset_free(it->visited_nodes);
507 static int ifg_clique_degree(const void *self, const ir_node *irn)
512 find_first_neighbour(self, &it, irn);
514 irn = get_next_neighbour(&it);
518 irn = get_next_neighbour(&it);
524 static const be_ifg_impl_t ifg_clique_impl = {
529 ifg_clique_connected,
530 ifg_clique_neighbours_begin,
531 ifg_clique_neighbours_next,
532 ifg_clique_neighbours_break,
533 ifg_clique_nodes_begin,
534 ifg_clique_nodes_next,
535 ifg_clique_nodes_break,
542 be_ifg_t *be_ifg_clique_new(const be_chordal_env_t *env)
544 ifg_clique_t *ifg = xmalloc(sizeof(*ifg));
546 ifg->impl = &ifg_clique_impl;
549 ifg->cli_root = NULL;
550 obstack_init(&ifg->obst);
552 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
554 obstack_finish(&ifg->obst);
555 return (be_ifg_t *) ifg;