2 * Copyright (C) 1995-2007 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
35 #include "irphase_t.h"
38 #include "irgraph_t.h"
45 #include "bechordal_t.h"
47 typedef struct _ptr_element_t ptr_element_t;
49 typedef union element_content {
51 ptr_element_t *element;
54 struct _ptr_element_t {
55 int kind; /* kind = 8888 ..> both are ir_nodes, = 3101 ..> first is another element, second an ir_node */
56 element_content content_first; /* could be a ptr_element or ir_node */
57 element_content content_second; /* could be a ptr_element or ir_node */
60 typedef struct _ptr_head_t {
61 struct list_head list;
62 ptr_element_t *element;
65 typedef struct _ifg_pointer_t {
66 const be_ifg_impl_t *impl;
67 const be_chordal_env_t *env;
70 ptr_head_t *curr_ptr_head;
71 ptr_element_t *curr_element;
74 typedef struct _ptr_iter_t {
75 const ifg_pointer_t *ifg;
77 ptr_head_t *curr_ptr_head;
78 ptr_head_t *first_head;
79 ptr_element_t *curr_element_t;
83 bitset_t *visited_neighbours;
86 /* PRIVATE FUNCTIONS */
88 static void *ptr_irn_data_init(ir_phase *ph, ir_node *irn, void *data)
90 ptr_head_t *head = phase_alloc(ph, sizeof(*head));
93 INIT_LIST_HEAD(&head->list);
97 static ptr_element_t *ptr_get_new_element(ifg_pointer_t *ifg)
99 ptr_element_t *new_element = obstack_alloc(&ifg->obst, sizeof(ptr_element_t));
100 memset(new_element, 0, sizeof(*new_element));
104 static ptr_head_t *ptr_get_new_head(ifg_pointer_t *ifg)
106 ptr_head_t *new_element = obstack_alloc(&ifg->obst, sizeof(*new_element));
107 INIT_LIST_HEAD(&new_element->list);
111 static void write_pointers(bitset_t *live, ifg_pointer_t *ifg)
116 bitset_foreach_irn(ifg->env->irg, live, elm, live_irn)
118 ptr_head_t *head = phase_get_or_set_irn_data(&ifg->ph, live_irn);
119 ptr_head_t *element = ptr_get_new_head(ifg);
121 element->element = ifg->curr_element; /* write current highest sub-clique for each node */
122 list_add(&element->list, &head->list);
126 static ptr_element_t *get_last_sub_clique(ifg_pointer_t *ifg, bitset_t *live, bitset_t *my_live, ir_node *irn)
128 ptr_element_t *element = ifg->curr_element;
129 ptr_element_t *res = NULL;
131 /* search the last sub-clique before the sub-clique that contains the node irn */
132 if (element && element->kind == 8888
133 && (element->content_first.irn == irn
134 || element->content_second.irn == irn)) /* contains the node we search and there is no other sub-clique before */
136 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 */
138 bitset_set(my_live, get_irn_idx(element->content_first.irn));
141 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 */
143 bitset_set(my_live, get_irn_idx(element->content_second.irn));
149 if (element && element->kind == 8889)
150 { /* this was a "single-node-clique" */
154 if (element && (element->kind == 3101)
155 && (element->content_second.irn == irn)) /* sub-clique contains node, return previous sub-clique */
157 res = element->content_first.element;
161 if (element && element->kind == 3101) /* look at previous sub-cliques if the contain the node you are searching for*/
163 if (bitset_is_set(live, get_irn_idx(element->content_second.irn))) /* irn is still alive */
165 bitset_set(my_live, get_irn_idx(element->content_second.irn));
167 ifg->curr_element = element->content_first.element;
168 res = get_last_sub_clique(ifg, live, my_live, irn);
179 static void find_neighbour_walker(ir_node *bl, void *data)
181 ifg_pointer_t *ifg = data;
182 struct list_head *head = get_block_border_head(ifg->env, bl);
185 ir_node *first = NULL;
186 bitset_t *live = bitset_malloc(get_irg_last_idx(ifg->env->irg));
191 element_content last_irn;
192 element_content last_element;
195 last_element.element = NULL;
197 assert(is_Block(bl) && "There is no block to work on.");
199 foreach_border_head(head, b) /* follow the borders of the block */
201 ir_node *irn = b->irn;
202 ptr_element_t *element = NULL;
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 */
226 last_element.element = element;
227 ifg->curr_element = element;
232 last_irn.irn = b->irn; /* needed to create first sub-clique */
233 last_element.element = NULL;
241 if (was_def == 1) /* if there is a USE after a DEF... */
243 if (!last_element.element)
244 { /* there was only one element in the clique */
245 element = ptr_get_new_element(ifg);
246 element->kind = 8889; /* first is a node, second is NULL, because this is a "single-node-clique" */
247 element->content_first.irn = last_irn.irn;
250 ifg->curr_element = NULL;
254 write_pointers(live, ifg); /* ...write a pointer to the highest sub-clique for each living node. */
258 my_live = bitset_malloc(get_irg_last_idx(ifg->env->irg));
259 last_element.element = get_last_sub_clique(ifg, live, my_live, irn);
261 /* check and add still living nodes */
262 if (bitset_popcnt(my_live) > 1)
264 if (last_element.element)
266 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
268 ptr_element_t *my_element = ptr_get_new_element(ifg);
269 my_element->content_first.element = last_element.element;
270 my_element->content_second.irn = my_irn;
271 my_element->kind = 3101; /* first is an element, second an ir_node */
273 last_element.element = my_element;
274 ifg->curr_element = my_element;
279 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
281 ptr_element_t *my_element = NULL;
282 if (!first && !was_first)
289 if (first && was_first)
291 my_element = ptr_get_new_element(ifg);
292 my_element->content_first.irn = first;
293 my_element->content_second.irn = my_irn;
294 my_element->kind = 8888; /* both are ir_nodes */
295 last_element.element = my_element;
296 ifg->curr_element = my_element;
301 my_element = ptr_get_new_element(ifg);
302 my_element->content_first.element = last_element.element;
303 my_element->content_second.irn = my_irn;
304 my_element->kind = 3101; /* first is an element, second an ir_node */
305 last_element.element = my_element;
306 ifg->curr_element = my_element;
315 if (bitset_popcnt(my_live) == 1) /* there is only one node left */
317 if (last_element.element)
319 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn)
321 ptr_element_t *my_element = ptr_get_new_element(ifg);
322 my_element->content_first.element = last_element.element;
323 my_element->content_second.irn = my_irn;
324 my_element->kind = 3101; /* first is an element, second an ir_node */
326 last_element.element = my_element;
327 ifg->curr_element = my_element;
332 bitset_foreach_irn(ifg->env->irg, my_live, my_elm, my_irn);
334 ptr_element_t *my_element = ptr_get_new_element(ifg);
335 my_element->content_first.irn = my_irn;
336 my_element->content_second.irn = NULL;
337 my_element->kind = 8889;
338 last_element.element = my_element;
339 ifg->curr_element = my_element;
344 bitset_free(my_live);
345 bitset_remv_irn(live, irn);
351 static ir_node *get_first_irn(const ifg_pointer_t *ifg, ptr_iter_t *it)
353 ir_node *irn = phase_get_first_node(&ifg->ph);
363 static ir_node *get_next_irn(ptr_iter_t *it)
365 ir_node *irn = phase_get_next_node(&it->ifg->ph, it->curr_irn);
375 static ir_node *get_next_neighbour(ptr_iter_t *it)
379 ptr_element_t *element;
381 element = it->curr_element_t;
385 if (it->curr_ptr_head->list.next != &it->first_head->list)
387 head = list_entry(it->curr_ptr_head->list.next, ptr_head_t, list);
388 it->curr_ptr_head = head;
389 element = head->element;
392 return NULL; /* there are no more neighbours */
395 if (element && element->kind == 8889) /* node has no neighbours */
397 res = element->content_first.irn;
398 it->curr_element_t = NULL;
402 if (element && element->kind == 8888) /* node has only one more neighbour */
406 if (element->content_first.irn != it->irn)
408 res = element->content_first.irn;
410 it->curr_element_t = NULL;
415 it->curr_element_t = NULL;
417 res = get_next_neighbour(it);
423 if (element->content_second.irn != it->irn)
425 res = element->content_second.irn;
427 it->curr_element_t = element;
432 it->curr_element_t = element;
434 res = get_next_neighbour(it);
441 if (element && element->kind == 3101)
443 it->curr_element_t = element->content_first.element;
444 res = element->content_second.irn;
447 { /* element is only an ir_node */// TODO
448 it->curr_element_t = NULL;
454 if (res && !it->sub_call)
456 if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
458 res = get_next_neighbour(it);
462 bitset_set(it->visited_neighbours, get_irn_idx(res));
469 static ir_node *get_first_neighbour(const ifg_pointer_t *ifg, ptr_iter_t *it, const ir_node *irn)
473 ptr_element_t *element;
474 bitset_t *bitsetvisited_neighbours = bitset_malloc(get_irg_last_idx(ifg->env->irg));
481 it->visited_neighbours = bitsetvisited_neighbours;
483 head = phase_get_irn_data(&ifg->ph, irn);
488 it->first_head = head;
489 head = list_entry(it->first_head->list.next, ptr_head_t, list); /* because first element is NULL */
490 it->curr_ptr_head = head;
491 element = head->element;
494 if (element && element->kind == 8889) /* node has no neighbours */
496 res = element->content_first.irn;
497 it->curr_element_t = NULL;
501 if (element && element->kind == 8888) /* node has only one neighbour */
505 if (element->content_first.irn != it->irn)
507 res = element->content_first.irn;
509 it->curr_element_t = NULL;
514 it->curr_element_t = NULL;
516 res = get_next_neighbour(it);
522 if (element->content_second.irn != it->irn)
524 res = element->content_second.irn;
525 it->curr_element_t = element;
531 it->curr_element_t = element;
533 res = get_next_neighbour(it);
539 if (element && element->kind == 3101)
541 it->curr_element_t = element->content_first.element;
542 res = element->content_second.irn;
545 { /* element is only an ir_node */
546 it->curr_element_t = NULL;
551 if (res && !it->sub_call)
553 if (bitset_contains_irn(it->visited_neighbours, res) || res == it->irn)
555 res = get_next_neighbour(it);
559 bitset_set(it->visited_neighbours, get_irn_idx(res));
568 /* PUBLIC FUNCTIONS */
570 static void ifg_pointer_free(void *self)
572 ifg_pointer_t *ifg = self;
573 obstack_free(&ifg->obst, NULL);
574 phase_free(&ifg->ph);
579 static int ifg_pointer_connected(const void *self, const ir_node *a, const ir_node *b)
581 const ifg_pointer_t *ifg = self;
586 irn = get_first_neighbour(ifg, &it, a);
595 irn = get_next_neighbour(&it);
601 static ir_node *ifg_pointer_neighbours_begin(const void *self, void *iter, const ir_node *irn)
603 return get_first_neighbour(self, iter, irn);
606 static ir_node *ifg_pointer_neighbours_next(const void *self, void *iter)
608 return get_next_neighbour(iter);
611 static void ifg_pointer_neighbours_break(const void *self, void *iter)
613 ptr_iter_t *it = iter;
615 bitset_free(it->visited_neighbours);
620 static ir_node *ifg_pointer_nodes_begin(const void *self, void *iter)
622 return get_first_irn(self, iter);
625 static ir_node *ifg_pointer_nodes_next(const void *self, void *iter)
627 return get_next_irn(iter);
630 static void ifg_pointer_nodes_break(const void *self, void *iter)
635 static int ifg_pointer_degree(const void *self, const ir_node *irn)
640 irn = get_first_neighbour(self, &it, irn);
645 irn = get_next_neighbour(&it);
651 static const be_ifg_impl_t ifg_pointer_impl = {
656 ifg_pointer_connected,
657 ifg_pointer_neighbours_begin,
658 ifg_pointer_neighbours_next,
659 ifg_pointer_neighbours_break,
660 ifg_pointer_nodes_begin,
661 ifg_pointer_nodes_next,
662 ifg_pointer_nodes_break,
669 be_ifg_t *be_ifg_pointer_new(const be_chordal_env_t *env)
671 ifg_pointer_t *ifg = xmalloc(sizeof(*ifg));
672 ifg->impl = &ifg_pointer_impl;
675 phase_init(&ifg->ph, "ptr_map", env->irg, PHASE_DEFAULT_GROWTH, ptr_irn_data_init, NULL);
676 obstack_init(&ifg->obst);
678 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
680 obstack_finish(&ifg->obst);
681 return (be_ifg_t *) ifg;