2 * @file beifg_pointer.c
4 * @author Sebastian Hack
6 * Copyright (C) 2005 Universitaet Karlsruhe
7 * Released under the GPL
21 #include "irgraph_t.h"
27 #include "bechordal_t.h"
29 typedef struct _cli_head_t {
30 struct list_head list;
31 struct _cli_head_t *next_cli_head;
36 typedef struct _ifg_pointer_t {
37 const be_ifg_impl_t *impl;
38 const be_chordal_env_t *env;
43 typedef struct _cli_element_t {
45 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 unsigned long curr_irg_visited;
53 const ir_node *curr_irn;
56 /* PRIVATE FUNCTIONS */
57 static cli_head_t *get_new_cli_head(void *data)
59 cli_iter_t *it = data;
61 cli_head_t *new_cli_head;
63 if (it->ifg->cli_root == NULL)
65 new_cli_head = obstack_alloc(&it->ifg->obst, sizeof(*new_cli_head));
66 INIT_LIST_HEAD(&new_cli_head->list);
68 new_cli_head->next_cli_head = NULL;
69 it->ifg->cli_root = new_cli_head;
70 it->curr_cli_head = new_cli_head;
74 cli_head = it->ifg->cli_root;
75 while(!(cli_head->next_cli_head == NULL))
77 cli_head = cli_head->next_cli_head;
79 new_cli_head = obstack_alloc(&it->ifg->obst, sizeof(*new_cli_head));
80 INIT_LIST_HEAD(&new_cli_head->list);
81 cli_head->next_cli_head = new_cli_head;
82 it->curr_cli_head = new_cli_head;
91 static cli_head_t *get_first_cli_head(void *data)
93 cli_iter_t *it = data;
95 return it->ifg->cli_root;
98 static void write_clique(pset *live_set, void *data)
105 cli_iter_t *it = data;
106 pset *live = live_set;
107 cli_element_t *element;
110 cli_head_t *cli_head = get_new_cli_head(it);
112 for(live_irn = pset_first(live); live_irn; live_irn = pset_next(live))
114 /* test if node is max or min dominator*/
115 test_node = live_irn;
116 if (max_node == NULL)
118 max_node = test_node;
119 min_node = test_node;
123 test_int = value_dominates(test_node, max_node);
126 max_node = test_node;
128 test_int = value_dominates(min_node, test_node);
131 min_node = test_node;
135 list_for_each_entry(cli_element_t, element, &cli_head->list, list){
136 if(element->irn == live_irn){
142 element->irn = live_irn;
143 list_add(&element->list, &cli_head->list) ;
146 cli_head->min = min_node;
147 cli_head->max = max_node;
150 static void find_nodes(const void *self, void *iter)
152 const ifg_clique_t *ifg = self;
153 cli_iter_t *it = iter;
154 cli_element_t *element = NULL;
155 cli_head_t *cli_head = get_first_cli_head(it);
157 assert((cli_head == NULL) && "There is no node to work on!");
159 it->curr_cli_head = cli_head;
160 it->curr_cli_element = element;
162 element = list_entry(cli_head->list.next, cli_element_t, list);
164 inc_irg_visited(get_irn_irg(element->irn));
165 it->curr_irg_visited = get_irg_visited(get_irn_irg(element->irn));
170 static ir_node *get_next_node(void *iter)
172 cli_iter_t *it = iter;
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 cli_iter_t *it = data;
214 struct list_head *head = get_block_border_head(it->ifg->env, bl);
218 pset *live = put_live_in(bl, pset_new_ptr_default());
220 assert(is_Block(bl) && "There is no block to work on.");
222 list_for_each_entry_reverse(border_t, b, head, list)
224 ir_node *irn = b->irn;
226 if (!(pset_find_ptr(live, irn)) && (b->is_def))
228 pset_insert_ptr(live, irn);
232 else if (!(b->is_def) && (was_def == 1))
236 write_clique(live, it);
239 pset_remove_ptr(live, irn);
245 static ifg_clique_t *build_neighbours(const be_chordal_env_t *env)
247 ifg_clique_t *ifg = NULL;
248 cli_iter_t *it = NULL;
251 it->curr_cli_head = NULL;
252 it->curr_cli_element = NULL;
253 it->curr_irg_visited = get_irg_visited(env->irg);
255 obstack_init(&it->ifg->obst);
256 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, it);
261 static void find_first_neighbour(const void *self, void *iter, const ir_node *irn)
263 const ifg_clique_t *ifg = self;
264 cli_iter_t *it = iter;
266 cli_head_t *cli_head = ifg->cli_root;
267 cli_element_t *element;
269 int is_dominated_by_max = 0;
270 int dominates_min = 0;
272 assert(!cli_head && "There is no root entry for a cli_head.");
274 while(!(cli_head->next_cli_head == NULL))
276 is_dominated_by_max = value_dominates(cli_head->max, irn);
277 dominates_min = value_dominates(irn, cli_head->min);
279 if ((is_dominated_by_max && dominates_min) /* node is in clique */
280 || (irn == cli_head->max)
281 || (irn == cli_head->min))
283 element = list_entry(cli_head->list.next, cli_element_t, list);
285 it->curr_cli_element = element;
286 it->curr_cli_head = cli_head;
291 cli_head = cli_head->next_cli_head;
296 inc_irg_visited(get_irn_irg(irn));
297 it->curr_irg_visited = get_irg_visited(get_irn_irg(irn));
301 static ir_node *get_next_neighbour(cli_iter_t *it)
304 cli_element_t *element = NULL;
305 cli_head_t *cli_head = NULL;
306 int is_dominated_by_max;
308 const ir_node *irn = it->curr_irn;
309 unsigned long irn_visited = 0;
311 res = it->curr_cli_element->irn;
313 /* get next element */
315 element = list_entry(it->curr_cli_element->list.next, cli_element_t, list);
316 irn_visited = get_irn_visited(element->irn);
318 if ((cli_head_t *)element == it->curr_cli_head) /* end of clique, search next one */
320 cli_head = cli_head->next_cli_head;
321 while(!(cli_head->next_cli_head == NULL))
323 is_dominated_by_max = value_dominates(cli_head->max, irn);
324 dominates_min = value_dominates(irn, cli_head->min);
326 if ((is_dominated_by_max && dominates_min) /* node is in clique */
327 || (irn == cli_head->max)
328 || (irn == cli_head->min))
330 element = list_entry(cli_head->list.next, cli_element_t, list);
332 it->curr_cli_element = element;
333 it->curr_cli_head = cli_head;
338 cli_head = cli_head->next_cli_head;
342 else /* get next element of this clique */
344 it->curr_cli_element = element;
347 if (irn_visited == it->curr_irg_visited)
349 irn = get_next_neighbour(it);
352 set_irn_visited(res, it->curr_irg_visited);
358 /* PUBLIC FUNCTIONS */
360 static void ifg_pointer_free(void *self)
362 ifg_clique_t *ifg = self;
367 static int ifg_pointer_connected(const void *self, const ir_node *a, const ir_node *b)
369 cli_iter_t *it = NULL;
373 find_first_neighbour(self, it, a);
375 irn = get_next_neighbour(it);
382 irn = get_next_neighbour(it);
388 static ir_node *ifg_pointer_neighbours_begin(const void *self, void *iter, const ir_node *irn)
390 find_first_neighbour(self, iter, irn);
391 return get_next_neighbour(iter);
394 static ir_node *ifg_pointer_neighbours_next(const void *self, void *iter)
396 return get_next_neighbour(iter);
399 static void ifg_pointer_neighbours_break(const void *self, void *iter)
404 static ir_node *ifg_pointer_nodes_begin(const void *self, void *iter)
406 find_nodes(self, iter);
407 return get_next_node(iter);
410 static ir_node *ifg_pointer_nodes_next(const void *self, void *iter)
412 return get_next_node(iter);
415 static void ifg_pointer_nodes_break(const void *self, void *iter)
420 static int ifg_pointer_degree(const void *self, const ir_node *irn)
423 cli_iter_t *it = NULL;
425 find_first_neighbour(self, it, irn);
427 irn = get_next_neighbour(it);
431 irn = get_next_neighbour(it);
437 static const be_ifg_impl_t ifg_pointer_impl = {
442 ifg_pointer_connected,
443 ifg_pointer_neighbours_begin,
444 ifg_pointer_neighbours_next,
445 ifg_pointer_neighbours_break,
446 ifg_pointer_nodes_begin,
447 ifg_pointer_nodes_next,
448 ifg_pointer_nodes_break,
455 be_ifg_t *be_ifg_pointer_new(const be_chordal_env_t *env)
457 ifg_pointer_t *ifg = malloc(sizeof(*ifg));
458 ifg->impl = &ifg_pointer_impl;
460 ifg->cli_root = NULL;
463 ifg = build_neighbours(env);
465 return (be_ifg_t *) ifg;