4 * @author Sebastian Hack
6 * Copyright (C) 2005 Universitaet Karlsruhe
7 * Released under the GPL
16 #include "benodesets.h"
20 #include "irgraph_t.h"
26 #include "bechordal_t.h"
29 typedef struct _adj_head_t adj_head_t;
31 typedef struct _ifg_list_t {
32 const be_ifg_impl_t *impl;
33 const be_chordal_env_t *env;
35 adj_head_t **adj_heads;
38 typedef struct _adj_element_t adj_element_t;
40 struct _adj_element_t {
41 adj_element_t *next_adj_element;
46 ir_node *irn; /* the node you search neighbours for */
47 adj_element_t *first_adj_element;
51 typedef struct _nodes_iter_t {
52 const ifg_list_t *ifg;
53 unsigned int curr_node_idx;
56 typedef struct _adj_iter_t {
57 const ifg_list_t *ifg;
58 adj_element_t *curr_adj_element;
61 /* PRIVATE FUNCTIONS */
63 static void create_node (ifg_list_t *ifg, ir_node *irn) /* add node to the array of all nodes in this ifg implementation, if the node isn't already in the ifg */
65 adj_head_t *adj_head = NULL;
67 adj_head = ifg->adj_heads[irn->node_idx];
70 adj_head = obstack_alloc(&ifg->obst, sizeof(*adj_head));
72 adj_head->first_adj_element = NULL;
74 ifg->adj_heads[irn->node_idx] = adj_head;
78 static adj_element_t *create_adj_element(ifg_list_t *ifg, ir_node *irn)
80 adj_element_t *element = NULL;
82 element = obstack_alloc(&ifg->obst, sizeof(*element));
83 element->next_adj_element = NULL;
84 element->neighbour = irn;
89 static void add_edge(ifg_list_t *ifg, ir_node *node_a, ir_node *node_b) /* write the information about the edge between a and b */
91 adj_head_t *adj_head = NULL;
92 adj_element_t *curr_element = NULL;
93 adj_element_t *new_element = NULL;
95 adj_head = ifg->adj_heads[node_a->node_idx]; /* find the neighbours list of a */
97 assert (adj_head && "There is no entry for node a");
98 curr_element = adj_head->first_adj_element;
102 while (curr_element->neighbour != node_b && curr_element->next_adj_element)
104 curr_element = curr_element->next_adj_element;
107 if (curr_element->neighbour != node_b && curr_element->next_adj_element == NULL)
110 new_element = create_adj_element(ifg, node_b); /* if b isn't in list, add b */
111 curr_element->next_adj_element = new_element;
117 new_element = create_adj_element(ifg, node_b); /* a has no neighbours, add b as the first one*/
118 adj_head->first_adj_element = new_element;
121 /* do the same vice versa */
122 adj_head = ifg->adj_heads[node_b->node_idx];
124 assert (adj_head && "There is no entry for node a");
125 curr_element = adj_head->first_adj_element;
129 while (curr_element->neighbour != node_a && curr_element->next_adj_element)
131 curr_element = curr_element->next_adj_element;
134 if (curr_element->neighbour != node_a && curr_element->next_adj_element == NULL)
137 new_element = create_adj_element(ifg, node_a);
138 curr_element->next_adj_element = new_element;
144 new_element = create_adj_element(ifg, node_a);
145 adj_head->first_adj_element = new_element;
149 static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in the irg */
151 ifg_list_t *ifg = data;
152 struct list_head *head = get_block_border_head(ifg->env, bl);
154 nodeset *live = new_nodeset(ifg->env->cls->n_regs);
155 ir_node *live_irn = NULL;
158 assert (is_Block(bl) && "There is no block to work on");
160 foreach_border_head(head, b) /* follow the borders of each block */
164 create_node(ifg, b->irn); /* add the node to the array of all nodes of this ifg implementation */
165 nodeset_insert(live, b->irn);
166 if (b->is_real) /* this is a new node */
168 foreach_nodeset(live, live_irn)
170 if (b->irn != live_irn) /* add a as a neighbour to b and vice versa */
171 add_edge(ifg, b->irn, live_irn);
175 else /* b->irn is now dead */
177 if (nodeset_find(live, b->irn))
178 nodeset_remove(live, b->irn);
186 static ir_node *get_first_node(const ifg_list_t *ifg, nodes_iter_t *it)
189 adj_head_t *adj_head= NULL;
193 it->curr_node_idx = 0;
195 while (adj_head == NULL)
198 adj_head = ifg->adj_heads[curr_idx];
201 if (adj_head == NULL) /* there are no nodes in this ifg */
206 it->curr_node_idx = curr_idx;
212 static ir_node *get_next_node(nodes_iter_t *it)
214 const ifg_list_t *ifg = it->ifg;
216 adj_head_t *adj_head= NULL;
217 unsigned int curr_idx = it->curr_node_idx;
219 while (adj_head == NULL && curr_idx < it->ifg->env->irg->last_node_idx - 1)
222 adj_head = ifg->adj_heads[curr_idx];
225 if (adj_head == NULL) /* there are no more nodes in this ifg */
230 it->curr_node_idx = curr_idx;
236 static ir_node *get_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *curr_irn)
239 adj_head_t *adj_head = NULL;
241 adj_head = ifg->adj_heads[curr_irn->node_idx];
242 assert (adj_head && "There is no entry for this node");
244 it->curr_adj_element = NULL;
247 if (adj_head->first_adj_element) /* return first neighbour */
249 res = adj_head->first_adj_element->neighbour;
250 it->curr_adj_element = adj_head->first_adj_element;
252 else /* node has no neighbours */
258 static ir_node *get_next_neighbour(adj_iter_t *it)
261 adj_element_t *element = it->curr_adj_element;
263 if (element->next_adj_element) /* return next neighbour */
265 res = element->next_adj_element->neighbour;
266 it->curr_adj_element = element->next_adj_element;
268 else /* was last neighbour */
274 /* PUBLIC FUNCTIONS */
276 static void ifg_list_free(void *self)
278 ifg_list_t *ifg = self;
279 obstack_free(&ifg->obst, NULL);
280 free(ifg->adj_heads);
284 static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b)
286 const ifg_list_t *ifg = self;
288 adj_head_t *adj_head = NULL;
289 adj_element_t *curr_element = NULL;
291 /* first try: find b in the neigbours of a */
292 adj_head = ifg->adj_heads[a->node_idx];
294 assert(adj_head && "There is no entry for the node a");
295 curr_element = adj_head->first_adj_element;
299 while (curr_element->neighbour != b && curr_element->next_adj_element)
301 curr_element = curr_element->next_adj_element;
303 if (curr_element->neighbour == b)
308 else /* node a has no neighbours */
311 /* second try, this should not be necessary... only to check the solution */
312 adj_head = ifg->adj_heads[b->node_idx];
314 assert(adj_head && "There is no entry for the node b");
315 curr_element = adj_head->first_adj_element;
319 while (curr_element->neighbour != a && curr_element->next_adj_element)
321 curr_element = curr_element->next_adj_element;
323 if (curr_element->neighbour == a)
325 assert ("Found the neighbour only in the second try.");
331 else /* node b has no neighbours */
337 static ir_node *ifg_list_nodes_begin(const void *self, void *iter)
339 nodes_iter_t *it = iter;
340 return get_first_node(self, it);
343 static ir_node *ifg_list_nodes_next(const void *self, void *iter)
345 return get_next_node(iter);
348 static void ifg_list_nodes_break(const void *self, void *iter)
350 nodes_iter_t *it = iter;
351 it->curr_node_idx = 0;
355 static ir_node *ifg_list_neighbours_begin(const void *self, void *iter,const ir_node *irn)
357 adj_iter_t *it = iter;
358 return get_first_neighbour(self, it, irn);
361 static ir_node *ifg_list_neighbours_next(const void *self, void *iter)
363 return get_next_neighbour(iter);
366 static void ifg_list_neighbours_break(const void *self, void *iter)
368 adj_iter_t *it= iter;
369 it->curr_adj_element = NULL;
373 static int ifg_list_degree(const void *self, const ir_node *irn)
375 const ifg_list_t *ifg = self;
376 adj_head_t *adj_head = NULL;
378 adj_head = ifg->adj_heads[irn->node_idx];
380 assert (adj_head && "There is no entry for this node");
382 return adj_head->degree;
385 static const be_ifg_impl_t ifg_list_impl = {
386 sizeof(nodes_iter_t),
391 ifg_list_neighbours_begin,
392 ifg_list_neighbours_next,
393 ifg_list_neighbours_break,
394 ifg_list_nodes_begin,
396 ifg_list_nodes_break,
403 be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
405 ifg_list_t *ifg = xmalloc(sizeof(*ifg));
406 adj_head_t **adj_heads_array = xmalloc(env->irg->last_node_idx * sizeof(adj_heads_array[0]));
408 ifg->impl = &ifg_list_impl;
411 memset(adj_heads_array, 0, env->irg->last_node_idx * sizeof(adj_heads_array[0]));
412 ifg->adj_heads = adj_heads_array;
414 obstack_init(&ifg->obst);
415 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
416 obstack_finish(&ifg->obst);
418 return (be_ifg_t *) ifg;