2 * @file beifg_pointer.c
4 * @author Sebastian Hack
6 * Copyright (C) 2005 Universitaet Karlsruhe
7 * Released under the GPL
18 #include "irphase_t.h"
21 #include "irgraph_t.h"
28 #include "bechordal_t.h"
30 typedef struct _ptr_element_t ptr_element_t;
32 typedef union element_content {
34 ptr_element_t *element;
37 struct _ptr_element_t {
38 int kind; /* kind = 8888 ..> both are ir_nodes, = 3101 ..> first is another element, second an ir_node */
39 element_content content_first; /* could be a ptr_element or ir_node */
40 element_content content_second; /* could be a ptr_element or ir_node */
43 typedef struct _ptr_head_t {
44 struct list_head list;
45 ptr_element_t *element;
48 typedef struct _ifg_pointer_t {
49 const be_ifg_impl_t *impl;
50 const be_chordal_env_t *env;
53 ptr_head_t *curr_ptr_head;
54 ptr_element_t *curr_element;
58 typedef struct _ptr_iter_t {
59 const ifg_pointer_t *ifg;
61 ptr_head_t *curr_ptr_head;
62 ptr_head_t *first_head;
63 ptr_element_t *curr_element_t;
67 bitset_t *visited_neighbours;
70 /* PRIVATE FUNCTIONS */
72 static void *ptr_irn_data_init(ir_phase *ph, ir_node *irn, void *data)
74 ptr_head_t *head = phase_alloc(ph, sizeof(*head));
75 INIT_LIST_HEAD(&head->list);
79 static ptr_element_t *ptr_get_new_element(ifg_pointer_t *ifg)
81 ptr_element_t *new_element = obstack_alloc(&ifg->obst, sizeof(ptr_element_t));
82 memset(new_element, 0, sizeof(*new_element));
86 static ptr_head_t *ptr_get_new_head(ifg_pointer_t *ifg)
88 ptr_head_t *new_element = obstack_alloc(&ifg->obst, sizeof(*new_element));
89 INIT_LIST_HEAD(&new_element->list);
93 static void write_pointers(bitset_t *live, ifg_pointer_t *ifg)
98 bitset_foreach_irn(ifg->env->irg, live, elm, live_irn)
100 ptr_head_t *head = phase_get_or_set_irn_data(&ifg->ph, live_irn);
101 ptr_head_t *element = ptr_get_new_head(ifg);
105 // Matze: huh, what is this?!? node numbers aren't in any way deterministic AFAIK
106 if (live_irn->node_nr == 1883 || live_irn->node_nr == 1858)
110 element->element = ifg->curr_element; /* write current highest sub-clique for each node */
111 list_add(&element->list, &head->list);
113 /* the following code is to find all nodes, it should be replaced by a "keywalker" of irphase */
114 irn = pmap_get(ifg->node_map, live_irn);
116 pmap_insert(ifg->node_map, live_irn, live_irn);
120 static ptr_element_t *get_last_sub_clique(ifg_pointer_t *ifg, bitset_t *live, bitset_t *my_live, ir_node *irn)
122 ptr_element_t *element = ifg->curr_element;
123 ptr_element_t *res = NULL;
125 /* search the last sub-clique before the sub-clique that contains the node irn */
126 if (element && element->kind == 8888
127 && (element->content_first.irn == irn
128 || element->content_second.irn == irn)) /* contains the node we search and there is no other sub-clique before */
130 if (bitset_is_set(live, get_irn_idx(element->content_first.irn)) && element->content_first.irn != irn) /* irn is still alive and not the node we search a sub-clique for */
132 bitset_set(my_live, get_irn_idx(element->content_first.irn));
135 if (bitset_is_set(live, get_irn_idx(element->content_second.irn))&& element->content_second.irn != irn) /* irn is still alive and not the node we search a sub-clique for */
137 bitset_set(my_live, get_irn_idx(element->content_second.irn));
143 if (element && element->kind == 8889)
144 { /* this was a "single-node-clique" */
148 if (element && (element->kind == 3101)
149 && (element->content_second.irn == irn)) /* sub-clique contains node, return previous sub-clique */
151 res = element->content_first.element;
155 if (element && element->kind == 3101) /* look at previous sub-cliques if the contain the node you are searching for*/
157 if (bitset_is_set(live, get_irn_idx(element->content_second.irn))) /* irn is still alive */
159 bitset_set(my_live, get_irn_idx(element->content_second.irn));
161 ifg->curr_element = element->content_first.element;
162 res = get_last_sub_clique(ifg, live, my_live, irn);
173 static void find_neighbour_walker(ir_node *bl, void *data)
175 ifg_pointer_t *ifg = data;
176 struct list_head *head = get_block_border_head(ifg->env, bl);
178 bitset_t *live = bitset_malloc(get_irg_last_idx(ifg->env->irg));
182 element_content last_irn;
183 element_content last_element;
185 ir_node *first = NULL;
189 last_element.element = NULL;
191 assert(is_Block(bl) && "There is no block to work on.");
193 foreach_border_head(head, b) /* follow the borders of the block */
195 ir_node *irn = b->irn;
196 ptr_element_t *element = NULL;
200 if (irn->node_nr == 1883 || irn->node_nr == 1858)
204 if (b->is_def) /* b is a new node */
206 bitset_set(live, get_irn_idx(irn));
207 if (last_element.element)
209 element = ptr_get_new_element(ifg);
210 element->content_first.element = last_element.element;
211 element->content_second.irn = b->irn;
212 element->kind = 3101; /* first is an element, second an ir_node */
214 last_element.element = element;
215 ifg->curr_element = element;
219 if (last_irn.irn) /* create new sub-clique */
221 element = ptr_get_new_element(ifg);
222 element->content_first.irn = last_irn.irn;
223 element->content_second.irn = b->irn;
224 element->kind = 8888; /* both are ir_nodes */
228 if (irn->node_nr == 1883 || irn->node_nr == 1858 || irn->node_nr == 1936)
233 last_element.element = element;
234 ifg->curr_element = element;
239 last_irn.irn = b->irn; /* needed to create first sub-clique */
240 last_element.element = NULL;
248 if (was_def == 1) /* if there is a USE after a DEF... */
250 if (!last_element.element)
251 { /* there was only one element in the clique */
252 element = ptr_get_new_element(ifg);
253 element->kind = 8889; /* first is a node, second is NULL, because this is a "single-node-clique" */
254 element->content_first.irn = last_irn.irn;
257 ifg->curr_element = NULL;
261 write_pointers(live, ifg); /* ...write a pointer to the highest sub-clique for each living node. */
265 my_live = bitset_malloc(get_irg_last_idx(ifg->env->irg));
266 last_element.element = get_last_sub_clique(ifg, live, my_live, irn);
268 /* check and add still living nodes */
269 //bitset_remv_irn(my_live, irn);
270 if (bitset_popcnt(my_live) > 1)
272 if (last_element.element)
274 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
276 ptr_element_t *my_element = ptr_get_new_element(ifg);
277 my_element->content_first.element = last_element.element;
278 my_element->content_second.irn = my_irn;
279 my_element->kind = 3101; /* first is an element, second an ir_node */
281 last_element.element = my_element;
282 ifg->curr_element = my_element;
287 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
289 ptr_element_t *my_element = NULL;
290 if (!first && !was_first)
297 if (first && was_first)
299 my_element = ptr_get_new_element(ifg);
300 my_element->content_first.irn = first;
301 my_element->content_second.irn = my_irn;
302 my_element->kind = 8888; /* both are ir_nodes */
303 last_element.element = my_element;
304 ifg->curr_element = my_element;
308 if (my_irn->node_nr == 1883 || my_irn->node_nr == 1858 || my_irn->node_nr == 1936)
317 my_element = ptr_get_new_element(ifg);
318 my_element->content_first.element = last_element.element;
319 my_element->content_second.irn = my_irn;
320 my_element->kind = 3101; /* first is an element, second an ir_node */
321 last_element.element = my_element;
322 ifg->curr_element = my_element;
331 if (bitset_popcnt(my_live) == 1) /* there is only one node left */
333 if (last_element.element)
335 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
337 ptr_element_t *my_element = ptr_get_new_element(ifg);
338 my_element->content_first.element = last_element.element;
339 my_element->content_second.irn = my_irn;
340 my_element->kind = 3101; /* first is an element, second an ir_node */
342 last_element.element = my_element;
343 ifg->curr_element = my_element;
348 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn);
350 ptr_element_t *my_element = ptr_get_new_element(ifg);
351 my_element->content_first.irn = my_irn;
352 my_element->content_second.irn = NULL;
353 my_element->kind = 8889;
354 last_element.element = my_element;
355 ifg->curr_element = my_element;
360 bitset_free(my_live);
361 bitset_remv_irn(live, irn);
367 static ir_node *get_first_irn(const ifg_pointer_t *ifg, ptr_iter_t *it)
369 /* this should be replaced using a keywalker of the irphase &ifg.ph */
374 entry = pmap_first(ifg->node_map);
385 static ir_node *get_next_irn(ptr_iter_t *it)
387 /* this should be replaced using a keywalker of the irphase &ifg.ph */
392 entry = pmap_next(it->ifg->node_map);
397 it->curr_irn = entry->value;
402 static ir_node *get_next_neighbour(ptr_iter_t *it)
406 ptr_element_t *element;
408 element = it->curr_element_t;
414 if (it->irn->node_nr == 1883 || it->irn->node_nr == 1858)
418 if (it->curr_ptr_head->list.next != &it->first_head->list)
420 head = list_entry(it->curr_ptr_head->list.next, ptr_head_t, list);
421 it->curr_ptr_head = head;
422 element = head->element;
425 return NULL; /* there are no more neighbours */
428 if (element && element->kind == 8889) /* node has no neighbours */
430 res = element->content_first.irn;
431 it->curr_element_t = NULL;
435 if (element && element->kind == 8888) /* node has only one more neighbour */
439 if (element->content_first.irn != it->irn)
441 res = element->content_first.irn;
443 it->curr_element_t = NULL;
448 it->curr_element_t = NULL;
450 res = get_next_neighbour(it);
456 if (element->content_second.irn != it->irn)
458 res = element->content_second.irn;
460 it->curr_element_t = element;
465 it->curr_element_t = element;
467 res = get_next_neighbour(it);
474 if (element && element->kind == 3101)
476 it->curr_element_t = element->content_first.element;
477 res = element->content_second.irn;
480 { /* element is only an ir_node */// TODO
481 it->curr_element_t = NULL;
487 if (res && !it->sub_call)
489 if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
491 res = get_next_neighbour(it);
495 bitset_set(it->visited_neighbours, get_irn_idx(res));
502 static ir_node *get_first_neighbour(const ifg_pointer_t *ifg, ptr_iter_t *it, const ir_node *irn)
506 ptr_element_t *element;
507 bitset_t *bitsetvisited_neighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
514 it->visited_neighbours = bitsetvisited_neighbours;
516 head = phase_get_irn_data(&ifg->ph, irn);
521 it->first_head = head;
522 head = list_entry(it->first_head->list.next, ptr_head_t, list); /* because first element is NULL */
523 it->curr_ptr_head = head;
524 element = head->element;
527 if (element && element->kind == 8889) /* node has no neighbours */
529 res = element->content_first.irn;
530 it->curr_element_t = NULL;
534 if (element && element->kind == 8888) /* node has only one neighbour */
538 if (element->content_first.irn != it->irn)
540 res = element->content_first.irn;
542 it->curr_element_t = NULL;
547 it->curr_element_t = NULL;
549 res = get_next_neighbour(it);
555 if (element->content_second.irn != it->irn)
557 res = element->content_second.irn;
558 it->curr_element_t = element;
564 it->curr_element_t = element;
566 res = get_next_neighbour(it);
572 if (element && element->kind == 3101)
574 it->curr_element_t = element->content_first.element;
575 res = element->content_second.irn;
578 { /* element is only an ir_node */
579 it->curr_element_t = NULL;
584 if (res && !it->sub_call)
586 if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
588 res = get_next_neighbour(it);
592 bitset_set(it->visited_neighbours, get_irn_idx(res));
601 /* PUBLIC FUNCTIONS */
603 static void ifg_pointer_free(void *self)
605 ifg_pointer_t *ifg = self;
606 obstack_free(&ifg->obst, NULL);
607 phase_free(&ifg->ph);
612 static int ifg_pointer_connected(const void *self, const ir_node *a, const ir_node *b)
614 const ifg_pointer_t *ifg = self;
619 irn = get_first_neighbour(ifg, &it, a);
628 irn = get_next_neighbour(&it);
634 static ir_node *ifg_pointer_neighbours_begin(const void *self, void *iter, const ir_node *irn)
636 return get_first_neighbour(self, iter, irn);
639 static ir_node *ifg_pointer_neighbours_next(const void *self, void *iter)
641 return get_next_neighbour(iter);
644 static void ifg_pointer_neighbours_break(const void *self, void *iter)
646 ptr_iter_t *it = iter;
648 bitset_free(it->visited_neighbours);
653 static ir_node *ifg_pointer_nodes_begin(const void *self, void *iter)
655 return get_first_irn(self, iter);
658 static ir_node *ifg_pointer_nodes_next(const void *self, void *iter)
660 return get_next_irn(iter);
663 static void ifg_pointer_nodes_break(const void *self, void *iter)
668 static int ifg_pointer_degree(const void *self, const ir_node *irn)
673 irn = get_first_neighbour(self, &it, irn);
678 irn = get_next_neighbour(&it);
684 static const be_ifg_impl_t ifg_pointer_impl = {
689 ifg_pointer_connected,
690 ifg_pointer_neighbours_begin,
691 ifg_pointer_neighbours_next,
692 ifg_pointer_neighbours_break,
693 ifg_pointer_nodes_begin,
694 ifg_pointer_nodes_next,
695 ifg_pointer_nodes_break,
702 be_ifg_t *be_ifg_pointer_new(const be_chordal_env_t *env)
704 ifg_pointer_t *ifg = xmalloc(sizeof(*ifg));
705 ifg->impl = &ifg_pointer_impl;
708 ifg->node_map = pmap_create(); /* to find all nodes, should be replaced by a "keywalker" of irphase */
710 phase_init(&ifg->ph, "ptr_map", env->irg, PHASE_DEFAULT_GROWTH, ptr_irn_data_init);
711 obstack_init(&ifg->obst);
713 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
715 obstack_finish(&ifg->obst);
716 return (be_ifg_t *) ifg;