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));
67 INIT_LIST_HEAD(&adj_head->list);
68 pmap_insert(ifg->list_map, irn, adj_head);
74 static list_element_t *get_new_list_element(ifg_list_t *ifg, ir_node *irn)
76 list_element_t *element;
78 element = obstack_alloc(&ifg->obst, sizeof(*element));
80 INIT_LIST_HEAD(&element->list);
85 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 */
88 list_element_t *new_element;
89 list_element_t *element;
92 adj_head = get_or_set_adj_head(ifg, a);
93 list_for_each_entry(list_element_t, element, &adj_head->list, list){
94 if(element->irn == b){
99 if (!is_element){ /* if B is not yet a neighbour of A add the node to A's neighbours */
100 new_element = get_new_list_element(ifg, b);
102 list_add(&new_element->list, &adj_head->list) ;
105 adj_head = get_or_set_adj_head(ifg, b);
107 list_for_each_entry(list_element_t, element, &adj_head->list, list){
108 if(element->irn == a){
112 if (!is_element){ /* if A is not yet a neighbour of B add the node to B's neighbours */
113 new_element = get_new_list_element(ifg, a);
115 list_add(&new_element->list, &adj_head->list);
119 static void find_nodes(const ifg_list_t *ifg, adj_iter_t *it)
122 entry = pmap_first(ifg->list_map); /* find the first node */
124 it->ifg->list_map = ifg->list_map;
126 it->curr_adj_head = entry->value;
131 static ir_node *get_next_node(adj_iter_t *it)
133 adj_head_t *adj_head;
138 if (it->curr_adj_head == NULL)
142 adj_head = it->curr_adj_head;
143 irn = adj_head->irn; /* return the last found node */
146 it->entry = pmap_next(it->ifg->list_map); /*find the next node */
147 if (it->entry != NULL)
148 it->curr_adj_head = it->entry->value;
150 it->curr_adj_head = NULL;
155 static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in one given block */
157 ifg_list_t *ifg = data;
158 struct list_head *head = get_block_border_head(ifg->env, bl);
160 int delete_nodeset = 0;
161 nodeset *live = new_nodeset(ifg->env->cls->n_regs);
163 adj_head_t *adj_head;
165 assert(is_Block(bl) && "There is no block to work on.");
167 foreach_border_head(head, b) /* follow the borders of the block */
169 //if(get_irn_node_nr(b->irn) == 2049)
172 adj_head = get_or_set_adj_head(ifg, b->irn);
173 nodeset_insert(live, b->irn);
174 // if (b->is_real) /* b is a new node */ {
175 foreach_nodeset(live, live_irn) {
176 if (b->irn != live_irn) /* add b as a neighbour to each previous found adjacent node */
177 add_edge(ifg, b->irn, live_irn);
183 if (nodeset_find(live,b->irn)) /* b is used, deleting... */
184 nodeset_remove(live, b->irn);
192 static void find_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *irn)
194 ir_node *node = (void *) irn;
195 list_element_t *element;
196 adj_head_t *adj_head = pmap_get(ifg->list_map, node);
198 assert(adj_head && "There is no entry for this node.");
200 if (adj_head->list.next == &adj_head->list)
202 /* element has no neighbours */
204 it->curr_adj_head = adj_head;
205 it->curr_list_element = NULL;
209 element = list_entry(adj_head->list.next, list_element_t, list); /* get the first neighbour of the given node irn */
211 it->curr_list_element = element;
212 it->curr_adj_head = adj_head;
213 it->irn = element->irn;
218 static ir_node *get_next_neighbour(adj_iter_t *it)
221 list_element_t *element;
222 adj_head_t *adj_head = it->curr_adj_head;
224 if(it->irn != NULL) /* return the previous found neighbour */
228 if(it->curr_list_element != NULL)
230 res = it->curr_list_element->irn; /* was last element */
231 it ->curr_list_element = NULL;
238 element = list_entry(it->curr_list_element->list.next, list_element_t, list); /* find the next neighbour */
239 if (element->list.next == &it->curr_list_element->list) /* single element (only one neighbour) */
242 it->curr_list_element = NULL;
246 if(element->list.next == &adj_head->list) /* reaching end of list */
249 it->irn = element->irn;
251 it->curr_list_element = element;
257 /* PUBLIC FUNCTIONS */
258 static void ifg_list_free(void *self)
260 ifg_list_t *ifg = self;
261 obstack_free(&ifg->obst, NULL);
262 pmap_destroy(ifg->list_map);
266 static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b)
268 const ifg_list_t *ifg = self;
269 ir_node *node_a = (void *) a;
270 ir_node *node_b = (void *) b;
271 adj_head_t *adj_head;
272 list_element_t *element;
275 adj_head = pmap_get(ifg->list_map, node_a);
276 assert(adj_head && "There is no entry for the first node.");
278 //if (adj_head == NULL) /* node is not in this ifg */
281 list_for_each_entry(list_element_t, element, &adj_head->list, list)
282 if(element->irn == b)
285 adj_head = pmap_get(ifg->list_map, node_b);
286 assert(adj_head && "There is no entry for the second node");
288 //if (adj_head == NULL) /* node is not in this ifg */
291 list_for_each_entry(list_element_t, element, &adj_head->list, list)
292 if(element->irn == a)
298 static ir_node *ifg_list_neighbours_begin(const void *self, adj_iter_t *it, const ir_node *irn)
300 find_first_neighbour(self, it, irn);
301 return get_next_neighbour(it);
304 static ir_node *ifg_list_neighbours_next(const void *self, adj_iter_t *it)
306 return get_next_neighbour(it);
309 static void ifg_list_neighbours_break(const void *self, adj_iter_t *it)
313 static ir_node *ifg_list_nodes_begin(const void *self, adj_iter_t *it)
315 find_nodes(self, it);
316 return get_next_node(it);
319 static ir_node *ifg_list_nodes_next(const void *self, adj_iter_t *it)
321 return get_next_node(it);
324 static void ifg_list_nodes_break(const void *self, adj_iter_t *it)
328 static int ifg_list_degree(const void *self, const ir_node *irn)
330 const ifg_list_t *ifg = self;
331 adj_head_t *adj_head;
333 adj_head = pmap_get(ifg->list_map, (void *) irn);
334 assert(!adj_head && "There is no entry for this node.");
336 return adj_head->degree;
339 static const be_ifg_impl_t ifg_list_impl = {
345 ifg_list_neighbours_begin,
346 ifg_list_neighbours_next,
347 ifg_list_neighbours_break,
348 ifg_list_nodes_begin,
350 ifg_list_nodes_break,
357 be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
359 ifg_list_t *ifg = xmalloc(sizeof(*ifg));
360 ifg->impl = &ifg_list_impl;
361 ifg->list_map = pmap_create();
364 obstack_init(&ifg->obst);
365 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
367 obstack_finish(&ifg->obst);
369 return (be_ifg_t *) ifg;