2 * Copyright (C) 1995-2008 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 Pointer based implementation of chordal interference graphs.
23 * @author Sebastian Hack
33 #include "irphase_t.h"
36 #include "irgraph_t.h"
43 #include "bechordal_t.h"
45 typedef struct _ptr_element_t ptr_element_t;
47 typedef union element_content {
49 ptr_element_t *element;
52 struct _ptr_element_t {
53 int kind; /* kind = 8888 ..> both are ir_nodes, = 3101 ..> first is another element, second an ir_node */
54 element_content content_first; /* could be a ptr_element or ir_node */
55 element_content content_second; /* could be a ptr_element or ir_node */
58 typedef struct _ptr_head_t {
59 struct list_head list;
60 ptr_element_t *element;
63 typedef struct _ifg_pointer_t {
64 const be_ifg_impl_t *impl;
65 const be_chordal_env_t *env;
68 ptr_head_t *curr_ptr_head;
69 ptr_element_t *curr_element;
72 typedef struct _ptr_iter_t {
73 const ifg_pointer_t *ifg;
75 ptr_head_t *curr_ptr_head;
76 ptr_head_t *first_head;
77 ptr_element_t *curr_element_t;
81 bitset_t *visited_neighbours;
84 /* PRIVATE FUNCTIONS */
86 static void *ptr_irn_data_init(ir_phase *ph, const ir_node *irn, void *data)
88 ptr_head_t *head = phase_alloc(ph, sizeof(*head));
91 INIT_LIST_HEAD(&head->list);
95 static ptr_element_t *ptr_get_new_element(ifg_pointer_t *ifg)
97 ptr_element_t *new_element = OALLOCZ(&ifg->obst, ptr_element_t);
101 static ptr_head_t *ptr_get_new_head(ifg_pointer_t *ifg)
103 ptr_head_t *new_element = OALLOC(&ifg->obst, ptr_head_t);
104 INIT_LIST_HEAD(&new_element->list);
108 static void write_pointers(bitset_t *live, ifg_pointer_t *ifg)
113 bitset_foreach_irn(ifg->env->irg, live, elm, live_irn) {
114 ptr_head_t *head = phase_get_or_set_irn_data(&ifg->ph, live_irn);
115 ptr_head_t *element = ptr_get_new_head(ifg);
117 element->element = ifg->curr_element; /* write current highest sub-clique for each node */
118 list_add(&element->list, &head->list);
122 static ptr_element_t *get_last_sub_clique(ifg_pointer_t *ifg, bitset_t *live, bitset_t *my_live, ir_node *irn)
124 ptr_element_t *element = ifg->curr_element;
125 ptr_element_t *res = NULL;
127 /* search the last sub-clique before the sub-clique that contains the node irn */
128 if (element && element->kind == 8888
129 && (element->content_first.irn == irn
130 || element->content_second.irn == irn)) /* contains the node we search and there is no other sub-clique before */
132 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 */
134 bitset_set(my_live, get_irn_idx(element->content_first.irn));
137 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 */
139 bitset_set(my_live, get_irn_idx(element->content_second.irn));
145 if (element && element->kind == 8889)
146 { /* this was a "single-node-clique" */
150 if (element && (element->kind == 3101)
151 && (element->content_second.irn == irn)) /* sub-clique contains node, return previous sub-clique */
153 res = element->content_first.element;
157 if (element && element->kind == 3101) /* look at previous sub-cliques if the contain the node you are searching for*/
159 if (bitset_is_set(live, get_irn_idx(element->content_second.irn))) /* irn is still alive */
161 bitset_set(my_live, get_irn_idx(element->content_second.irn));
163 ifg->curr_element = element->content_first.element;
164 res = get_last_sub_clique(ifg, live, my_live, irn);
175 static void find_neighbour_walker(ir_node *bl, void *data)
177 ifg_pointer_t *ifg = data;
178 struct list_head *head = get_block_border_head(ifg->env, bl);
181 ir_node *first = NULL;
182 bitset_t *live = bitset_malloc(get_irg_last_idx(ifg->env->irg));
187 element_content last_irn;
188 element_content last_element;
191 last_element.element = NULL;
193 assert(is_Block(bl) && "There is no block to work on.");
195 foreach_border_head(head, b) /* follow the borders of the block */
197 ir_node *irn = b->irn;
198 ptr_element_t *element = NULL;
200 if (b->is_def) /* b is a new node */
202 bitset_set(live, get_irn_idx(irn));
203 if (last_element.element)
205 element = ptr_get_new_element(ifg);
206 element->content_first.element = last_element.element;
207 element->content_second.irn = b->irn;
208 element->kind = 3101; /* first is an element, second an ir_node */
210 last_element.element = element;
211 ifg->curr_element = element;
215 if (last_irn.irn) /* create new sub-clique */
217 element = ptr_get_new_element(ifg);
218 element->content_first.irn = last_irn.irn;
219 element->content_second.irn = b->irn;
220 element->kind = 8888; /* both are ir_nodes */
222 last_element.element = element;
223 ifg->curr_element = element;
228 last_irn.irn = b->irn; /* needed to create first sub-clique */
229 last_element.element = NULL;
237 if (was_def == 1) /* if there is a USE after a DEF... */
239 if (!last_element.element)
240 { /* there was only one element in the clique */
241 element = ptr_get_new_element(ifg);
242 element->kind = 8889; /* first is a node, second is NULL, because this is a "single-node-clique" */
243 element->content_first.irn = last_irn.irn;
246 ifg->curr_element = NULL;
250 write_pointers(live, ifg); /* ...write a pointer to the highest sub-clique for each living node. */
254 my_live = bitset_malloc(get_irg_last_idx(ifg->env->irg));
255 last_element.element = get_last_sub_clique(ifg, live, my_live, irn);
257 /* check and add still living nodes */
258 if (bitset_popcnt(my_live) > 1)
260 if (last_element.element)
262 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
264 ptr_element_t *my_element = ptr_get_new_element(ifg);
265 my_element->content_first.element = last_element.element;
266 my_element->content_second.irn = my_irn;
267 my_element->kind = 3101; /* first is an element, second an ir_node */
269 last_element.element = my_element;
270 ifg->curr_element = my_element;
275 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
277 ptr_element_t *my_element = NULL;
278 if (!first && !was_first)
285 if (first && was_first)
287 my_element = ptr_get_new_element(ifg);
288 my_element->content_first.irn = first;
289 my_element->content_second.irn = my_irn;
290 my_element->kind = 8888; /* both are ir_nodes */
291 last_element.element = my_element;
292 ifg->curr_element = my_element;
297 my_element = ptr_get_new_element(ifg);
298 my_element->content_first.element = last_element.element;
299 my_element->content_second.irn = my_irn;
300 my_element->kind = 3101; /* first is an element, second an ir_node */
301 last_element.element = my_element;
302 ifg->curr_element = my_element;
311 if (bitset_popcnt(my_live) == 1) /* there is only one node left */
313 if (last_element.element)
315 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
317 ptr_element_t *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 */
322 last_element.element = my_element;
323 ifg->curr_element = my_element;
328 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn);
330 ptr_element_t *my_element = ptr_get_new_element(ifg);
331 my_element->content_first.irn = my_irn;
332 my_element->content_second.irn = NULL;
333 my_element->kind = 8889;
334 last_element.element = my_element;
335 ifg->curr_element = my_element;
340 bitset_free(my_live);
341 bitset_remv_irn(live, irn);
347 static ir_node *get_first_irn(const ifg_pointer_t *ifg, ptr_iter_t *it)
349 ir_node *irn = phase_get_first_node(&ifg->ph);
359 static ir_node *get_next_irn(ptr_iter_t *it)
361 ir_node *irn = phase_get_next_node(&it->ifg->ph, it->curr_irn);
371 static ir_node *get_next_neighbour(ptr_iter_t *it)
375 ptr_element_t *element;
377 element = it->curr_element_t;
381 if (it->curr_ptr_head->list.next != &it->first_head->list)
383 head = list_entry(it->curr_ptr_head->list.next, ptr_head_t, list);
384 it->curr_ptr_head = head;
385 element = head->element;
388 return NULL; /* there are no more neighbours */
391 if (element && element->kind == 8889) /* node has no neighbours */
393 res = element->content_first.irn;
394 it->curr_element_t = NULL;
398 if (element && element->kind == 8888) /* node has only one more neighbour */
402 if (element->content_first.irn != it->irn)
404 res = element->content_first.irn;
406 it->curr_element_t = NULL;
411 it->curr_element_t = NULL;
413 res = get_next_neighbour(it);
419 if (element->content_second.irn != it->irn)
421 res = element->content_second.irn;
423 it->curr_element_t = element;
428 it->curr_element_t = element;
430 res = get_next_neighbour(it);
437 if (element && element->kind == 3101)
439 it->curr_element_t = element->content_first.element;
440 res = element->content_second.irn;
443 { /* element is only an ir_node */// TODO
444 it->curr_element_t = NULL;
450 if (res && !it->sub_call)
452 if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
454 res = get_next_neighbour(it);
458 bitset_set(it->visited_neighbours, get_irn_idx(res));
465 static ir_node *get_first_neighbour(const ifg_pointer_t *ifg, ptr_iter_t *it, const ir_node *irn)
469 ptr_element_t *element;
470 bitset_t *bitsetvisited_neighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
477 it->visited_neighbours = bitsetvisited_neighbours;
479 head = phase_get_irn_data(&ifg->ph, irn);
484 it->first_head = head;
485 head = list_entry(it->first_head->list.next, ptr_head_t, list); /* because first element is NULL */
486 it->curr_ptr_head = head;
487 element = head->element;
490 if (element && element->kind == 8889) /* node has no neighbours */
492 res = element->content_first.irn;
493 it->curr_element_t = NULL;
497 if (element && element->kind == 8888) /* node has only one neighbour */
501 if (element->content_first.irn != it->irn)
503 res = element->content_first.irn;
505 it->curr_element_t = NULL;
510 it->curr_element_t = NULL;
512 res = get_next_neighbour(it);
518 if (element->content_second.irn != it->irn)
520 res = element->content_second.irn;
521 it->curr_element_t = element;
527 it->curr_element_t = element;
529 res = get_next_neighbour(it);
535 if (element && element->kind == 3101)
537 it->curr_element_t = element->content_first.element;
538 res = element->content_second.irn;
541 { /* element is only an ir_node */
542 it->curr_element_t = NULL;
547 if (res && !it->sub_call)
549 if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
551 res = get_next_neighbour(it);
555 bitset_set(it->visited_neighbours, get_irn_idx(res));
564 /* PUBLIC FUNCTIONS */
566 static void ifg_pointer_free(void *self)
568 ifg_pointer_t *ifg = self;
569 obstack_free(&ifg->obst, NULL);
570 phase_free(&ifg->ph);
575 static int ifg_pointer_connected(const void *self, const ir_node *a, const ir_node *b)
577 const ifg_pointer_t *ifg = self;
582 irn = get_first_neighbour(ifg, &it, a);
591 irn = get_next_neighbour(&it);
597 static ir_node *ifg_pointer_neighbours_begin(const void *self, void *iter, const ir_node *irn)
599 return get_first_neighbour(self, iter, irn);
602 static ir_node *ifg_pointer_neighbours_next(const void *self, void *iter)
605 return get_next_neighbour(iter);
608 static void ifg_pointer_neighbours_break(const void *self, void *iter)
610 ptr_iter_t *it = iter;
613 bitset_free(it->visited_neighbours);
616 static ir_node *ifg_pointer_nodes_begin(const void *self, void *iter)
618 return get_first_irn(self, iter);
621 static ir_node *ifg_pointer_nodes_next(const void *self, void *iter)
624 return get_next_irn(iter);
627 static void ifg_pointer_nodes_break(const void *self, void *iter)
634 static int ifg_pointer_degree(const void *self, const ir_node *irn)
639 irn = get_first_neighbour(self, &it, irn);
644 irn = get_next_neighbour(&it);
650 static const be_ifg_impl_t ifg_pointer_impl = {
655 ifg_pointer_connected,
656 ifg_pointer_neighbours_begin,
657 ifg_pointer_neighbours_next,
658 ifg_pointer_neighbours_break,
659 ifg_pointer_nodes_begin,
660 ifg_pointer_nodes_next,
661 ifg_pointer_nodes_break,
668 be_ifg_t *be_ifg_pointer_new(const be_chordal_env_t *env)
670 ifg_pointer_t *ifg = XMALLOC(ifg_pointer_t);
671 ifg->impl = &ifg_pointer_impl;
674 phase_init(&ifg->ph, "ptr_map", env->irg, PHASE_DEFAULT_GROWTH, ptr_irn_data_init, NULL);
675 obstack_init(&ifg->obst);
677 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
679 obstack_finish(&ifg->obst);
680 return (be_ifg_t *) ifg;