2 * @file beifg_pointer.c
4 * @author Sebastian Hack
6 * Copyright (C) 2005 Universitaet Karlsruhe
7 * Released under the GPL
19 #include "irphase_t.h"
22 #include "irgraph_t.h"
29 #include "bechordal_t.h"
31 typedef struct _ptr_element_t ptr_element_t;
33 typedef union element_content {
35 ptr_element_t *element;
38 struct _ptr_element_t {
39 int kind; /* kind = 8888 ..> both are ir_nodes, = 3101 ..> first is another element, second an ir_node */
40 element_content content_first; /* could be a ptr_element or ir_node */
41 element_content content_second; /* could be a ptr_element or ir_node */
44 typedef struct _ptr_head_t {
45 struct list_head list;
46 ptr_element_t *element;
49 typedef struct _ifg_pointer_t {
50 const be_ifg_impl_t *impl;
51 const be_chordal_env_t *env;
54 ptr_head_t *curr_ptr_head;
55 ptr_element_t *curr_element;
59 typedef struct _ptr_iter_t {
60 const ifg_pointer_t *ifg;
62 ptr_head_t *curr_ptr_head;
63 ptr_head_t *first_head;
64 ptr_element_t *curr_element_t;
68 bitset_t *visited_neighbours;
71 /* PRIVATE FUNCTIONS */
73 static void *ptr_irn_data_init(phase_t *ph, ir_node *irn, void *data)
75 ptr_head_t *head = phase_alloc(ph, sizeof(*head));
76 INIT_LIST_HEAD(&head->list);
80 static ptr_element_t *ptr_get_new_element(ifg_pointer_t *ifg)
82 ptr_element_t *new_element = obstack_alloc(&ifg->obst, sizeof(ptr_element_t));
83 memset(new_element, 0, sizeof(*new_element));
87 static ptr_head_t *ptr_get_new_head(ifg_pointer_t *ifg)
89 ptr_head_t *new_element = obstack_alloc(&ifg->obst, sizeof(*new_element));
90 INIT_LIST_HEAD(&new_element->list);
94 static void write_pointers(bitset_t *live, ifg_pointer_t *ifg)
99 bitset_foreach_irn(ifg->env->irg, live, elm, live_irn)
101 ptr_head_t *head = phase_get_or_set_irn_data(&ifg->ph, live_irn);
102 ptr_head_t *element = ptr_get_new_head(ifg);
106 // Matze: huh, what is this?!? node numbers aren't in any way deterministic AFAIK
107 if (live_irn->node_nr == 1883 || live_irn->node_nr == 1858)
111 element->element = ifg->curr_element; /* write current highest sub-clique for each node */
112 list_add(&element->list, &head->list);
114 /* the following code is to find all nodes, it should be replaced by a "keywalker" of irphase */
115 irn = pmap_get(ifg->node_map, live_irn);
117 pmap_insert(ifg->node_map, live_irn, live_irn);
121 static ptr_element_t *get_last_sub_clique(ifg_pointer_t *ifg, bitset_t *live, bitset_t *my_live, ir_node *irn)
123 ptr_element_t *element = ifg->curr_element;
124 ptr_element_t *res = NULL;
126 /* search the last sub-clique before the sub-clique that contains the node irn */
127 if (element && element->kind == 8888
128 && (element->content_first.irn == irn
129 || element->content_second.irn == irn)) /* contains the node we search and there is no other sub-clique before */
131 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 */
133 bitset_set(my_live, get_irn_idx(element->content_first.irn));
136 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 */
138 bitset_set(my_live, get_irn_idx(element->content_second.irn));
144 if (element && element->kind == 8889)
145 { /* this was a "single-node-clique" */
149 if (element && (element->kind == 3101)
150 && (element->content_second.irn == irn)) /* sub-clique contains node, return previous sub-clique */
152 res = element->content_first.element;
156 if (element && element->kind == 3101) /* look at previous sub-cliques if the contain the node you are searching for*/
158 if (bitset_is_set(live, get_irn_idx(element->content_second.irn))) /* irn is still alive */
160 bitset_set(my_live, get_irn_idx(element->content_second.irn));
162 ifg->curr_element = element->content_first.element;
163 res = get_last_sub_clique(ifg, live, my_live, irn);
174 static void find_neighbour_walker(ir_node *bl, void *data)
176 ifg_pointer_t *ifg = data;
177 struct list_head *head = get_block_border_head(ifg->env, bl);
179 bitset_t *live = bitset_malloc(get_irg_last_idx(ifg->env->irg));
183 element_content last_irn;
184 element_content last_element;
186 ir_node *first = NULL;
190 last_element.element = NULL;
192 assert(is_Block(bl) && "There is no block to work on.");
194 foreach_border_head(head, b) /* follow the borders of the block */
196 ir_node *irn = b->irn;
197 ptr_element_t *element = NULL;
201 if (irn->node_nr == 1883 || irn->node_nr == 1858)
205 if (b->is_def) /* b is a new node */
207 bitset_set(live, get_irn_idx(irn));
208 if (last_element.element)
210 element = ptr_get_new_element(ifg);
211 element->content_first.element = last_element.element;
212 element->content_second.irn = b->irn;
213 element->kind = 3101; /* first is an element, second an ir_node */
215 last_element.element = element;
216 ifg->curr_element = element;
220 if (last_irn.irn) /* create new sub-clique */
222 element = ptr_get_new_element(ifg);
223 element->content_first.irn = last_irn.irn;
224 element->content_second.irn = b->irn;
225 element->kind = 8888; /* both are ir_nodes */
229 if (irn->node_nr == 1883 || irn->node_nr == 1858 || irn->node_nr == 1936)
234 last_element.element = element;
235 ifg->curr_element = element;
240 last_irn.irn = b->irn; /* needed to create first sub-clique */
241 last_element.element = NULL;
249 if (was_def == 1) /* if there is a USE after a DEF... */
251 if (!last_element.element)
252 { /* there was only one element in the clique */
253 element = ptr_get_new_element(ifg);
254 element->kind = 8889; /* first is a node, second is NULL, because this is a "single-node-clique" */
255 element->content_first.irn = last_irn.irn;
258 ifg->curr_element = NULL;
262 write_pointers(live, ifg); /* ...write a pointer to the highest sub-clique for each living node. */
266 my_live = bitset_malloc(get_irg_last_idx(ifg->env->irg));
267 last_element.element = get_last_sub_clique(ifg, live, my_live, irn);
269 /* check and add still living nodes */
270 //bitset_remv_irn(my_live, irn);
271 if (bitset_popcnt(my_live) > 1)
273 if (last_element.element)
275 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
277 ptr_element_t *my_element = ptr_get_new_element(ifg);
278 my_element->content_first.element = last_element.element;
279 my_element->content_second.irn = my_irn;
280 my_element->kind = 3101; /* first is an element, second an ir_node */
282 last_element.element = my_element;
283 ifg->curr_element = my_element;
288 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
290 ptr_element_t *my_element = NULL;
291 if (!first && !was_first)
298 if (first && was_first)
300 my_element = ptr_get_new_element(ifg);
301 my_element->content_first.irn = first;
302 my_element->content_second.irn = my_irn;
303 my_element->kind = 8888; /* both are ir_nodes */
304 last_element.element = my_element;
305 ifg->curr_element = my_element;
309 if (my_irn->node_nr == 1883 || my_irn->node_nr == 1858 || my_irn->node_nr == 1936)
318 my_element = ptr_get_new_element(ifg);
319 my_element->content_first.element = last_element.element;
320 my_element->content_second.irn = my_irn;
321 my_element->kind = 3101; /* first is an element, second an ir_node */
322 last_element.element = my_element;
323 ifg->curr_element = my_element;
332 if (bitset_popcnt(my_live) == 1) /* there is only one node left */
334 if (last_element.element)
336 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
338 ptr_element_t *my_element = ptr_get_new_element(ifg);
339 my_element->content_first.element = last_element.element;
340 my_element->content_second.irn = my_irn;
341 my_element->kind = 3101; /* first is an element, second an ir_node */
343 last_element.element = my_element;
344 ifg->curr_element = my_element;
349 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn);
351 ptr_element_t *my_element = ptr_get_new_element(ifg);
352 my_element->content_first.irn = my_irn;
353 my_element->content_second.irn = NULL;
354 my_element->kind = 8889;
355 last_element.element = my_element;
356 ifg->curr_element = my_element;
361 bitset_free(my_live);
362 bitset_remv_irn(live, irn);
368 static ir_node *get_first_irn(const ifg_pointer_t *ifg, ptr_iter_t *it)
370 /* this should be replaced using a keywalker of the irphase &ifg.ph */
375 entry = pmap_first(ifg->node_map);
386 static ir_node *get_next_irn(ptr_iter_t *it)
388 /* this should be replaced using a keywalker of the irphase &ifg.ph */
393 entry = pmap_next(it->ifg->node_map);
398 it->curr_irn = entry->value;
403 static ir_node *get_next_neighbour(ptr_iter_t *it)
407 ptr_element_t *element;
409 element = it->curr_element_t;
415 if (it->irn->node_nr == 1883 || it->irn->node_nr == 1858)
419 if (it->curr_ptr_head->list.next != &it->first_head->list)
421 head = list_entry(it->curr_ptr_head->list.next, ptr_head_t, list);
422 it->curr_ptr_head = head;
423 element = head->element;
426 return NULL; /* there are no more neighbours */
429 if (element && element->kind == 8889) /* node has no neighbours */
431 res = element->content_first.irn;
432 it->curr_element_t = NULL;
436 if (element && element->kind == 8888) /* node has only one more neighbour */
440 if (element->content_first.irn != it->irn)
442 res = element->content_first.irn;
444 it->curr_element_t = NULL;
449 it->curr_element_t = NULL;
451 res = get_next_neighbour(it);
457 if (element->content_second.irn != it->irn)
459 res = element->content_second.irn;
461 it->curr_element_t = element;
466 it->curr_element_t = element;
468 res = get_next_neighbour(it);
475 if (element && element->kind == 3101)
477 it->curr_element_t = element->content_first.element;
478 res = element->content_second.irn;
481 { /* element is only an ir_node */// TODO
482 it->curr_element_t = NULL;
488 if (res && !it->sub_call)
490 if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
492 res = get_next_neighbour(it);
496 bitset_set(it->visited_neighbours, get_irn_idx(res));
503 static ir_node *get_first_neighbour(const ifg_pointer_t *ifg, ptr_iter_t *it, const ir_node *irn)
507 ptr_element_t *element;
508 bitset_t *bitsetvisited_neighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
515 it->visited_neighbours = bitsetvisited_neighbours;
517 head = phase_get_irn_data(&ifg->ph, irn);
522 it->first_head = head;
523 head = list_entry(it->first_head->list.next, ptr_head_t, list); /* because first element is NULL */
524 it->curr_ptr_head = head;
525 element = head->element;
528 if (element && element->kind == 8889) /* node has no neighbours */
530 res = element->content_first.irn;
531 it->curr_element_t = NULL;
535 if (element && element->kind == 8888) /* node has only one neighbour */
539 if (element->content_first.irn != it->irn)
541 res = element->content_first.irn;
543 it->curr_element_t = NULL;
548 it->curr_element_t = NULL;
550 res = get_next_neighbour(it);
556 if (element->content_second.irn != it->irn)
558 res = element->content_second.irn;
559 it->curr_element_t = element;
565 it->curr_element_t = element;
567 res = get_next_neighbour(it);
573 if (element && element->kind == 3101)
575 it->curr_element_t = element->content_first.element;
576 res = element->content_second.irn;
579 { /* element is only an ir_node */
580 it->curr_element_t = NULL;
585 if (res && !it->sub_call)
587 if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
589 res = get_next_neighbour(it);
593 bitset_set(it->visited_neighbours, get_irn_idx(res));
602 /* PUBLIC FUNCTIONS */
604 static void ifg_pointer_free(void *self)
606 ifg_pointer_t *ifg = self;
607 obstack_free(&ifg->obst, NULL);
608 phase_free(&ifg->ph);
613 static int ifg_pointer_connected(const void *self, const ir_node *a, const ir_node *b)
615 const ifg_pointer_t *ifg = self;
620 irn = get_first_neighbour(ifg, &it, a);
629 irn = get_next_neighbour(&it);
635 static ir_node *ifg_pointer_neighbours_begin(const void *self, void *iter, const ir_node *irn)
637 return get_first_neighbour(self, iter, irn);
640 static ir_node *ifg_pointer_neighbours_next(const void *self, void *iter)
642 return get_next_neighbour(iter);
645 static void ifg_pointer_neighbours_break(const void *self, void *iter)
647 ptr_iter_t *it = iter;
649 bitset_free(it->visited_neighbours);
654 static ir_node *ifg_pointer_nodes_begin(const void *self, void *iter)
656 return get_first_irn(self, iter);
659 static ir_node *ifg_pointer_nodes_next(const void *self, void *iter)
661 return get_next_irn(iter);
664 static void ifg_pointer_nodes_break(const void *self, void *iter)
669 static int ifg_pointer_degree(const void *self, const ir_node *irn)
674 irn = get_first_neighbour(self, &it, irn);
679 irn = get_next_neighbour(&it);
685 static const be_ifg_impl_t ifg_pointer_impl = {
690 ifg_pointer_connected,
691 ifg_pointer_neighbours_begin,
692 ifg_pointer_neighbours_next,
693 ifg_pointer_neighbours_break,
694 ifg_pointer_nodes_begin,
695 ifg_pointer_nodes_next,
696 ifg_pointer_nodes_break,
703 be_ifg_t *be_ifg_pointer_new(const be_chordal_env_t *env)
705 ifg_pointer_t *ifg = xmalloc(sizeof(*ifg));
706 ifg->impl = &ifg_pointer_impl;
709 ifg->node_map = pmap_create(); /* to find all nodes, should be replaced by a "keywalker" of irphase */
711 phase_init(&ifg->ph, "ptr_map", env->irg, PHASE_DEFAULT_GROWTH, ptr_irn_data_init);
712 obstack_init(&ifg->obst);
714 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
716 obstack_finish(&ifg->obst);
717 return (be_ifg_t *) ifg;