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;
42 typedef struct _cli_element_t {
44 struct list_head list;
47 typedef struct _cli_iter_t {
49 cli_head_t *curr_cli_head;
50 cli_element_t *curr_cli_element;
51 unsigned long curr_irg_visited;
52 const ir_node *curr_irn;
55 /* PRIVATE FUNCTIONS */
56 static cli_head_t *get_new_cli_head(ifg_clique_t *ifg)
59 cli_head_t *new_cli_head;
61 if (ifg->cli_root == NULL)
63 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
64 INIT_LIST_HEAD(&new_cli_head->list);
65 ifg->cli_root = new_cli_head;
69 cli_head = ifg->cli_root;
70 while(!(cli_head->next_cli_head == NULL))
72 cli_head = cli_head->next_cli_head;
74 new_cli_head = obstack_alloc(&ifg->obst, sizeof(*new_cli_head));
75 INIT_LIST_HEAD(&new_cli_head->list);
76 cli_head->next_cli_head = new_cli_head;
79 new_cli_head->min = NULL;
80 new_cli_head->max = NULL;
81 new_cli_head->next_cli_head = NULL;
82 ifg->curr_cli_head = new_cli_head;
87 static cli_element_t *get_new_cli_element(ifg_clique_t *ifg)
89 cli_element_t *cli_element;
91 cli_element = obstack_alloc(&ifg->obst, sizeof(*cli_element));
92 INIT_LIST_HEAD(&cli_element->list);
97 static void write_clique(nodeset *live_set, ifg_clique_t *ifg)
102 ir_node *max_node = NULL;
103 ir_node *min_node = NULL;
104 cli_element_t *new_element = NULL;
105 cli_element_t *element = NULL;
106 cli_head_t *cli_head = get_new_cli_head(ifg);
109 foreach_nodeset(live_set, live_irn)
111 /* test if node is max or min dominator*/
112 test_node = live_irn;
113 if (max_node == NULL)
115 max_node = test_node;
116 min_node = test_node;
120 test_int = value_dominates(test_node, max_node);
123 max_node = test_node;
125 test_int = value_dominates(min_node, test_node);
128 min_node = test_node;
131 list_for_each_entry(cli_element_t, element, &cli_head->list, list){
132 if(element->irn == live_irn){
139 new_element = get_new_cli_element(ifg);
140 new_element->irn = live_irn;
141 list_add(&new_element->list, &cli_head->list) ;
146 cli_head->min = min_node;
147 cli_head->max = max_node;
150 static void find_nodes(const ifg_clique_t *ifg, cli_iter_t *it)
152 cli_element_t *element;
153 cli_head_t *cli_head = ifg->cli_root;
155 assert((cli_head == NULL) && "There is no node to work on!");
157 it->curr_cli_head = cli_head;
159 if (cli_head->list.next != &cli_head->list) /* if cli_head contains an element */
161 element = list_entry(cli_head->list.next, cli_element_t, list);
162 it->curr_cli_element = element;
164 inc_irg_visited(get_irn_irg(element->irn));
165 it->curr_irg_visited = get_irg_visited(get_irn_irg(element->irn));
171 static ir_node *get_next_node(cli_iter_t *it)
173 cli_head_t *cli_head = NULL;
174 cli_element_t *element = it->curr_cli_element;
175 unsigned long irn_visited = get_irn_visited(element->irn);
179 if (!(element == it->curr_cli_element))
182 element = list_entry(cli_head->list.next, cli_element_t, list);
183 it->curr_cli_element = element;
187 cli_head = it->curr_cli_head;
188 if (!(cli_head->next_cli_head == NULL))
191 cli_head = cli_head->next_cli_head;
192 it->curr_cli_head = cli_head;
193 element = list_entry(cli_head->list.next, cli_element_t, list);
194 it->curr_cli_element = element;
202 if (irn_visited == it->curr_irg_visited)
204 irn = get_next_node(it);
207 set_irn_visited(irn, it->curr_irg_visited);
211 static void find_neighbour_walker(ir_node *bl, void *data)
213 ifg_clique_t *ifg = data;
214 struct list_head *head = get_block_border_head(ifg->env, bl);
217 nodeset *live = new_nodeset(ifg->env->cls->n_regs);
219 assert(is_Block(bl) && "There is no block to work on.");
221 foreach_border_head(head, b) /* follow the borders of the block */
223 ir_node *irn = b->irn;
225 if (b->is_def) /* b is a new node */
227 nodeset_insert(live, irn);
237 if (was_def == 1) /* if there is a USE after a DEF... */
239 write_clique(live, ifg); /* ...add the clique. */
242 nodeset_remove(live, irn);
249 static void find_first_neighbour(const ifg_clique_t *ifg, cli_iter_t *it, const ir_node *irn)
251 cli_head_t *cli_head = ifg->cli_root;
252 cli_element_t *element;
254 int is_dominated_by_max = 0;
255 int dominates_min = 0;
257 assert(!cli_head && "There is no root entry for a cli_head.");
259 while(!(cli_head->next_cli_head == NULL))
261 is_dominated_by_max = value_dominates(cli_head->max, irn);
262 dominates_min = value_dominates(irn, cli_head->min);
264 if ((is_dominated_by_max && dominates_min) /* node is in clique */
265 || (irn == cli_head->max)
266 || (irn == cli_head->min))
268 element = list_entry(cli_head->list.next, cli_element_t, list);
270 it->curr_cli_element = element;
271 it->curr_cli_head = cli_head;
276 cli_head = cli_head->next_cli_head;
281 inc_irg_visited(get_irn_irg(irn));
282 it->curr_irg_visited = get_irg_visited(get_irn_irg(irn));
286 static ir_node *get_next_neighbour(cli_iter_t *it)
289 cli_element_t *element = NULL;
290 cli_head_t *cli_head = NULL;
291 int is_dominated_by_max;
293 const ir_node *irn = it->curr_irn;
294 unsigned long irn_visited = 0;
296 res = it->curr_cli_element->irn;
298 /* get next element */
300 element = list_entry(it->curr_cli_element->list.next, cli_element_t, list);
301 irn_visited = get_irn_visited(element->irn);
303 if ((cli_head_t *)element == it->curr_cli_head) /* end of clique, search next one */
305 cli_head = cli_head->next_cli_head;
306 while(!(cli_head->next_cli_head == NULL))
308 is_dominated_by_max = value_dominates(cli_head->max, irn);
309 dominates_min = value_dominates(irn, cli_head->min);
311 if ((is_dominated_by_max && dominates_min) /* node is in clique */
312 || (irn == cli_head->max)
313 || (irn == cli_head->min))
315 element = list_entry(cli_head->list.next, cli_element_t, list);
317 it->curr_cli_element = element;
318 it->curr_cli_head = cli_head;
323 cli_head = cli_head->next_cli_head;
327 else /* get next element of this clique */
329 it->curr_cli_element = element;
332 if (irn_visited == it->curr_irg_visited)
334 irn = get_next_neighbour(it);
337 set_irn_visited(res, it->curr_irg_visited);
343 /* PUBLIC FUNCTIONS */
345 static void ifg_clique_free(void *self)
347 ifg_clique_t *ifg = self;
348 obstack_free(&ifg->obst, NULL);
353 static int ifg_clique_connected(const void *self, const ir_node *a, const ir_node *b)
355 cli_iter_t *it = NULL;
359 find_first_neighbour(self, it, a);
361 irn = get_next_neighbour(it);
368 irn = get_next_neighbour(it);
374 static ir_node *ifg_clique_neighbours_begin(const void *self, void *iter, const ir_node *irn)
376 find_first_neighbour(self, iter, irn);
377 return get_next_neighbour(iter);
380 static ir_node *ifg_clique_neighbours_next(const void *self, void *iter)
382 return get_next_neighbour(iter);
385 static void ifg_clique_neighbours_break(const void *self, void *iter)
390 static ir_node *ifg_clique_nodes_begin(const void *self, void *iter)
392 find_nodes(self, iter);
393 return get_next_node(iter);
396 static ir_node *ifg_clique_nodes_next(const void *self, void *iter)
398 return get_next_node(iter);
401 static void ifg_clique_nodes_break(const void *self, void *iter)
406 static int ifg_clique_degree(const void *self, const ir_node *irn)
409 cli_iter_t *it = NULL;
411 find_first_neighbour(self, it, irn);
413 irn = get_next_neighbour(it);
417 irn = get_next_neighbour(it);
423 static const be_ifg_impl_t ifg_clique_impl = {
428 ifg_clique_connected,
429 ifg_clique_neighbours_begin,
430 ifg_clique_neighbours_next,
431 ifg_clique_neighbours_break,
432 ifg_clique_nodes_begin,
433 ifg_clique_nodes_next,
434 ifg_clique_nodes_break,
441 be_ifg_t *be_ifg_clique_new(const be_chordal_env_t *env)
443 ifg_clique_t *ifg = xmalloc(sizeof(*ifg));
444 ifg->impl = &ifg_clique_impl;
447 ifg->cli_root = NULL;
448 obstack_init(&ifg->obst);
450 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
452 obstack_finish(&ifg->obst);
453 return (be_ifg_t *) ifg;