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 _adj_head_t adj_head_t;
32 typedef struct _ifg_list_t {
33 const be_ifg_impl_t *impl;
34 const be_chordal_env_t *env;
36 adj_head_t **adj_heads;
39 typedef struct _list_element_t {
40 struct list_head list;
45 struct list_head list;
46 struct list_head *next_adj_head;
51 typedef struct _adj_iter_t {
54 adj_head_t *curr_adj_head;
55 list_element_t *curr_list_element;
59 /* PRIVATE FUNCTIONS */
61 static adj_head_t *get_or_set_adj_head(ifg_list_t *ifg, ir_node *irn)
63 adj_head_t *adj_head = NULL;
65 adj_head = ifg->adj_heads[irn->node_idx];
67 adj_head = obstack_alloc(&ifg->obst, sizeof(*adj_head));
70 INIT_LIST_HEAD(&adj_head->list);
71 ifg->adj_heads[irn->node_idx] = adj_head;
77 static list_element_t *get_new_list_element(ifg_list_t *ifg, ir_node *irn)
79 list_element_t *element = NULL;
81 element = obstack_alloc(&ifg->obst, sizeof(*element));
83 INIT_LIST_HEAD(&element->list);
88 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 */
90 adj_head_t *adj_head = NULL;
91 list_element_t *new_element = NULL;
92 list_element_t *element = NULL;
95 adj_head = get_or_set_adj_head(ifg, a);
96 list_for_each_entry(list_element_t, element, &adj_head->list, list){
97 if(element->irn == b){
102 if (!is_element){ /* if B is not yet a neighbour of A add the node to A's neighbours */
103 new_element = get_new_list_element(ifg, b);
105 list_add(&new_element->list, &adj_head->list) ;
108 adj_head = get_or_set_adj_head(ifg, b);
110 list_for_each_entry(list_element_t, element, &adj_head->list, list){
111 if(element->irn == a){
115 if (!is_element){ /* if A is not yet a neighbour of B add the node to B's neighbours */
116 new_element = get_new_list_element(ifg, a);
118 list_add(&new_element->list, &adj_head->list);
122 static void find_nodes(const ifg_list_t *ifg, adj_iter_t *it)
124 adj_head_t *adj_head = NULL;
127 while(adj_head == NULL) /* find first adj_head */
130 adj_head = ifg->adj_heads[i];
134 it->ifg->adj_heads = ifg->adj_heads;
135 it->curr_adj_head = adj_head;
136 it->curr_node_idx = i;
141 static ir_node *get_next_node(adj_iter_t *it)
143 adj_head_t *adj_head = NULL;
145 unsigned int node_idx = it->curr_node_idx;
147 if (it->curr_adj_head == NULL)
151 adj_head = it->curr_adj_head;
152 irn = adj_head->irn; /* return the last found node */
157 while (adj_head == NULL && node_idx < it->ifg->env->irg->last_node_idx - 1)
160 adj_head = it->ifg->adj_heads[node_idx];
163 it->curr_node_idx = node_idx;
164 it->curr_adj_head = adj_head;
166 if (!adj_head) /* was last node */
168 it->curr_adj_head = NULL;
169 it->curr_node_idx = -1;
175 static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in one given block */
177 ifg_list_t *ifg = data;
178 struct list_head *head = get_block_border_head(ifg->env, bl);
180 int delete_nodeset = 0;
181 nodeset *live = new_nodeset(ifg->env->cls->n_regs);
182 ir_node *live_irn = NULL;
183 adj_head_t *adj_head = NULL;
185 assert(is_Block(bl) && "There is no block to work on.");
187 foreach_border_head(head, b) /* follow the borders of the block */
189 //if(get_irn_node_nr(b->irn) == 2049)
192 adj_head = get_or_set_adj_head(ifg, b->irn);
193 nodeset_insert(live, b->irn);
194 // if (b->is_real) /* b is a new node */ {
195 foreach_nodeset(live, live_irn) {
196 if (b->irn != live_irn) /* add b as a neighbour to each previous found adjacent node */
197 add_edge(ifg, b->irn, live_irn);
203 if (nodeset_find(live,b->irn)) /* b is used, deleting... */
204 nodeset_remove(live, b->irn);
212 static void find_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *irn)
214 list_element_t *element = NULL;
215 adj_head_t *adj_head = ifg->adj_heads[irn->node_idx];
217 assert(adj_head && "There is no entry for this node.");
219 if (adj_head->list.next == &adj_head->list)
221 /* element has no neighbours */
223 it->curr_adj_head = adj_head;
224 it->curr_list_element = NULL;
228 element = list_entry(adj_head->list.next, list_element_t, list); /* get the first neighbour of the given node irn */
230 it->curr_list_element = element;
231 it->curr_adj_head = adj_head;
232 it->irn = element->irn;
237 static ir_node *get_next_neighbour(adj_iter_t *it)
240 list_element_t *element = NULL;
241 adj_head_t *adj_head = it->curr_adj_head;
243 if(it->irn != NULL) /* return the previous found neighbour */
247 if(it->curr_list_element != NULL)
249 res = it->curr_list_element->irn; /* was last element */
250 it ->curr_list_element = NULL;
257 element = list_entry(it->curr_list_element->list.next, list_element_t, list); /* find the next neighbour */
258 if (element->list.next == &it->curr_list_element->list) /* single element (only one neighbour) */
261 it->curr_list_element = NULL;
265 if(element->list.next == &adj_head->list) /* reaching end of list */
268 it->irn = element->irn;
270 it->curr_list_element = element;
276 /* PUBLIC FUNCTIONS */
277 static void ifg_list_free(void *self)
279 ifg_list_t *ifg = self;
280 obstack_free(&ifg->obst, NULL);
281 free(ifg->adj_heads);
285 static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b)
287 const ifg_list_t *ifg = self;
288 ir_node *node_a = (void *) a;
289 ir_node *node_b = (void *) b;
290 adj_head_t *adj_head = NULL;
291 list_element_t *element = NULL;
294 adj_head = ifg->adj_heads[node_a->node_idx];
295 assert(adj_head && "There is no entry for the first node.");
297 //if (adj_head == NULL) /* node is not in this ifg */
300 list_for_each_entry(list_element_t, element, &adj_head->list, list)
301 if(element->irn == b)
304 adj_head = ifg->adj_heads[node_b->node_idx];
305 assert(adj_head && "There is no entry for the second node");
307 //if (adj_head == NULL) /* node is not in this ifg */
310 list_for_each_entry(list_element_t, element, &adj_head->list, list)
311 if(element->irn == a)
317 static ir_node *ifg_list_neighbours_begin(const void *self, adj_iter_t *it, const ir_node *irn)
319 find_first_neighbour(self, it, irn);
320 return get_next_neighbour(it);
323 static ir_node *ifg_list_neighbours_next(const void *self, adj_iter_t *it)
325 return get_next_neighbour(it);
328 static void ifg_list_neighbours_break(const void *self, adj_iter_t *it)
332 static ir_node *ifg_list_nodes_begin(const void *self, adj_iter_t *it)
334 find_nodes(self, it);
335 return get_next_node(it);
338 static ir_node *ifg_list_nodes_next(const void *self, adj_iter_t *it)
340 return get_next_node(it);
343 static void ifg_list_nodes_break(const void *self, adj_iter_t *it)
347 static int ifg_list_degree(const void *self, const ir_node *irn)
349 const ifg_list_t *ifg = self;
350 adj_head_t *adj_head = NULL;
352 adj_head = ifg->adj_heads[irn->node_idx];
353 assert(adj_head && "There is no entry for this node.");
355 return adj_head->degree;
358 static const be_ifg_impl_t ifg_list_impl = {
364 ifg_list_neighbours_begin,
365 ifg_list_neighbours_next,
366 ifg_list_neighbours_break,
367 ifg_list_nodes_begin,
369 ifg_list_nodes_break,
376 be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
378 ifg_list_t *ifg = xmalloc(sizeof(*ifg));
379 adj_head_t **adj_heads_array = xmalloc(env->irg->last_node_idx * sizeof(adj_heads_array[0]));
380 ifg->impl = &ifg_list_impl;
383 memset(adj_heads_array, 0, env->irg->last_node_idx * sizeof(adj_heads_array[0]));
384 ifg->adj_heads = adj_heads_array;
386 obstack_init(&ifg->obst);
387 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
389 obstack_finish(&ifg->obst);
391 return (be_ifg_t *) ifg;