4 * @author Sebastian Hack
6 * Copyright (C) 2005 Universitaet Karlsruhe
7 * Released under the GPL
19 #include "irgraph_t.h"
21 #include "benodesets.h"
26 #include "bechordal_t.h"
28 #define MAX(x, y) ((x) > (y) ? (x) : (y))
30 typedef struct _ifg_list_t {
31 const be_ifg_impl_t *impl;
32 const be_chordal_env_t *env;
37 typedef struct _list_element_t {
38 struct list_head list;
42 typedef struct _adj_head_t {
43 struct list_head list;
44 struct list_head *next_adj_head;
49 typedef struct _adj_iter_t {
52 adj_head_t *curr_adj_head;
53 list_element_t *curr_list_element;
57 /* PRIVATE FUNCTIONS */
59 static adj_head_t *get_or_set_adj_head(ifg_list_t *ifg, ir_node *irn)
63 adj_head = pmap_get(ifg->list_map, irn);
65 adj_head = obstack_alloc(&ifg->obst, sizeof(*adj_head));
68 INIT_LIST_HEAD(&adj_head->list);
69 pmap_insert(ifg->list_map, irn, adj_head);
75 static list_element_t *get_new_list_element(ifg_list_t *ifg, ir_node *irn)
77 list_element_t *element;
79 element = obstack_alloc(&ifg->obst, sizeof(*element));
81 INIT_LIST_HEAD(&element->list);
86 static void add_edge(ifg_list_t *ifg, ir_node *a, ir_node *b) /* add node B as a neighbour to A and vice versa */
89 list_element_t *new_element;
90 list_element_t *element;
93 adj_head = get_or_set_adj_head(ifg, a);
94 list_for_each_entry(list_element_t, element, &adj_head->list, list){
95 if(element->irn == b){
100 if (!is_element){ /* if B is not yet a neighbour of A add the node to A's neighbours */
101 new_element = get_new_list_element(ifg, b);
103 list_add(&new_element->list, &adj_head->list) ;
106 adj_head = get_or_set_adj_head(ifg, b);
108 list_for_each_entry(list_element_t, element, &adj_head->list, list){
109 if(element->irn == a){
113 if (!is_element){ /* if A is not yet a neighbour of B add the node to B's neighbours */
114 new_element = get_new_list_element(ifg, a);
116 list_add(&new_element->list, &adj_head->list);
120 static void find_nodes(const ifg_list_t *ifg, adj_iter_t *it)
123 entry = pmap_first(ifg->list_map); /* find the first node */
125 it->ifg->list_map = ifg->list_map;
127 it->curr_adj_head = entry->value;
132 static ir_node *get_next_node(adj_iter_t *it)
134 adj_head_t *adj_head;
139 if (it->curr_adj_head == NULL)
143 adj_head = it->curr_adj_head;
144 irn = adj_head->irn; /* return the last found node */
147 it->entry = pmap_next(it->ifg->list_map); /*find the next node */
148 if (it->entry != NULL)
149 it->curr_adj_head = it->entry->value;
151 it->curr_adj_head = NULL;
156 static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in one given block */
158 ifg_list_t *ifg = data;
159 struct list_head *head = get_block_border_head(ifg->env, bl);
161 int delete_nodeset = 0;
162 nodeset *live = new_nodeset(ifg->env->cls->n_regs);
164 adj_head_t *adj_head;
166 assert(is_Block(bl) && "There is no block to work on.");
168 foreach_border_head(head, b) /* follow the borders of the block */
170 //if(get_irn_node_nr(b->irn) == 2049)
173 adj_head = get_or_set_adj_head(ifg, b->irn);
174 nodeset_insert(live, b->irn);
175 // if (b->is_real) /* b is a new node */ {
176 foreach_nodeset(live, live_irn) {
177 if (b->irn != live_irn) /* add b as a neighbour to each previous found adjacent node */
178 add_edge(ifg, b->irn, live_irn);
184 if (nodeset_find(live,b->irn)) /* b is used, deleting... */
185 nodeset_remove(live, b->irn);
193 static void find_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *irn)
195 ir_node *node = (void *) irn;
196 list_element_t *element;
197 adj_head_t *adj_head = pmap_get(ifg->list_map, node);
199 assert(adj_head && "There is no entry for this node.");
201 if (adj_head->list.next == &adj_head->list)
203 /* element has no neighbours */
205 it->curr_adj_head = adj_head;
206 it->curr_list_element = NULL;
210 element = list_entry(adj_head->list.next, list_element_t, list); /* get the first neighbour of the given node irn */
212 it->curr_list_element = element;
213 it->curr_adj_head = adj_head;
214 it->irn = element->irn;
219 static ir_node *get_next_neighbour(adj_iter_t *it)
222 list_element_t *element;
223 adj_head_t *adj_head = it->curr_adj_head;
225 if(it->irn != NULL) /* return the previous found neighbour */
229 if(it->curr_list_element != NULL)
231 res = it->curr_list_element->irn; /* was last element */
232 it ->curr_list_element = NULL;
239 element = list_entry(it->curr_list_element->list.next, list_element_t, list); /* find the next neighbour */
240 if (element->list.next == &it->curr_list_element->list) /* single element (only one neighbour) */
243 it->curr_list_element = NULL;
247 if(element->list.next == &adj_head->list) /* reaching end of list */
250 it->irn = element->irn;
252 it->curr_list_element = element;
258 /* PUBLIC FUNCTIONS */
259 static void ifg_list_free(void *self)
261 ifg_list_t *ifg = self;
262 obstack_free(&ifg->obst, NULL);
263 pmap_destroy(ifg->list_map);
267 static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b)
269 const ifg_list_t *ifg = self;
270 ir_node *node_a = (void *) a;
271 ir_node *node_b = (void *) b;
272 adj_head_t *adj_head;
273 list_element_t *element;
276 adj_head = pmap_get(ifg->list_map, node_a);
277 assert(adj_head && "There is no entry for the first node.");
279 //if (adj_head == NULL) /* node is not in this ifg */
282 list_for_each_entry(list_element_t, element, &adj_head->list, list)
283 if(element->irn == b)
286 adj_head = pmap_get(ifg->list_map, node_b);
287 assert(adj_head && "There is no entry for the second node");
289 //if (adj_head == NULL) /* node is not in this ifg */
292 list_for_each_entry(list_element_t, element, &adj_head->list, list)
293 if(element->irn == a)
299 static ir_node *ifg_list_neighbours_begin(const void *self, adj_iter_t *it, const ir_node *irn)
301 find_first_neighbour(self, it, irn);
302 return get_next_neighbour(it);
305 static ir_node *ifg_list_neighbours_next(const void *self, adj_iter_t *it)
307 return get_next_neighbour(it);
310 static void ifg_list_neighbours_break(const void *self, adj_iter_t *it)
314 static ir_node *ifg_list_nodes_begin(const void *self, adj_iter_t *it)
316 find_nodes(self, it);
317 return get_next_node(it);
320 static ir_node *ifg_list_nodes_next(const void *self, adj_iter_t *it)
322 return get_next_node(it);
325 static void ifg_list_nodes_break(const void *self, adj_iter_t *it)
329 static int ifg_list_degree(const void *self, const ir_node *irn)
331 const ifg_list_t *ifg = self;
332 adj_head_t *adj_head;
334 adj_head = pmap_get(ifg->list_map, (void *) irn);
335 assert(adj_head && "There is no entry for this node.");
337 return adj_head->degree;
340 static const be_ifg_impl_t ifg_list_impl = {
346 ifg_list_neighbours_begin,
347 ifg_list_neighbours_next,
348 ifg_list_neighbours_break,
349 ifg_list_nodes_begin,
351 ifg_list_nodes_break,
358 be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
360 ifg_list_t *ifg = xmalloc(sizeof(*ifg));
361 ifg->impl = &ifg_list_impl;
362 ifg->list_map = pmap_create();
365 obstack_init(&ifg->obst);
366 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
368 obstack_finish(&ifg->obst);
370 return (be_ifg_t *) ifg;