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 List based implementation of chordal interference graphs.
23 * @author Sebastian Hack
33 #include "benodesets.h"
37 #include "irgraph_t.h"
44 #include "bechordal_t.h"
47 typedef struct _adj_head_t adj_head_t;
49 typedef struct _ifg_list_t {
50 const be_ifg_impl_t *impl;
51 const be_chordal_env_t *env;
53 adj_head_t **adj_heads;
56 typedef struct _adj_element_t adj_element_t;
58 struct _adj_element_t {
59 adj_element_t *next_adj_element;
64 ir_node *irn; /* the node you search neighbours for */
65 adj_element_t *first_adj_element;
69 typedef struct _nodes_iter_t {
70 const ifg_list_t *ifg;
71 unsigned int curr_node_idx;
74 typedef struct _adj_iter_t {
75 const ifg_list_t *ifg;
76 adj_element_t *curr_adj_element;
79 /* PRIVATE FUNCTIONS */
81 /* add node to the array of all nodes in this ifg implementation, if the node isn't already in the ifg */
82 static void create_node(ifg_list_t *ifg, ir_node *irn)
84 adj_head_t *adj_head = NULL;
86 adj_head = ifg->adj_heads[irn->node_idx];
89 adj_head = obstack_alloc(&ifg->obst, sizeof(*adj_head));
91 adj_head->first_adj_element = NULL;
93 ifg->adj_heads[irn->node_idx] = adj_head;
97 static adj_element_t *create_adj_element(ifg_list_t *ifg, ir_node *irn)
99 adj_element_t *element = NULL;
101 element = obstack_alloc(&ifg->obst, sizeof(*element));
102 element->next_adj_element = NULL;
103 element->neighbour = irn;
108 /* write the information about the edge between a and b */
109 static void add_edge(ifg_list_t *ifg, ir_node *node_a, ir_node *node_b)
111 adj_head_t *adj_head = NULL;
112 adj_element_t *curr_element = NULL;
113 adj_element_t *new_element = NULL;
115 adj_head = ifg->adj_heads[node_a->node_idx]; /* find the neighbours list of a */
117 assert (adj_head && "There is no entry for node a");
118 curr_element = adj_head->first_adj_element;
122 while (curr_element->neighbour != node_b && curr_element->next_adj_element)
124 curr_element = curr_element->next_adj_element;
127 if (curr_element->neighbour != node_b && curr_element->next_adj_element == NULL)
130 new_element = create_adj_element(ifg, node_b); /* if b isn't in list, add b */
131 curr_element->next_adj_element = new_element;
137 new_element = create_adj_element(ifg, node_b); /* a has no neighbours, add b as the first one*/
138 adj_head->first_adj_element = new_element;
141 /* do the same vice versa */
142 adj_head = ifg->adj_heads[node_b->node_idx];
144 assert (adj_head && "There is no entry for node a");
145 curr_element = adj_head->first_adj_element;
149 while (curr_element->neighbour != node_a && curr_element->next_adj_element)
151 curr_element = curr_element->next_adj_element;
154 if (curr_element->neighbour != node_a && curr_element->next_adj_element == NULL)
157 new_element = create_adj_element(ifg, node_a);
158 curr_element->next_adj_element = new_element;
164 new_element = create_adj_element(ifg, node_a);
165 adj_head->first_adj_element = new_element;
169 /* find all adjacent nodes in the irg */
170 static void find_neighbour_walker(ir_node *bl, void *data)
172 ifg_list_t *ifg = data;
173 struct list_head *head = get_block_border_head(ifg->env, bl);
174 nodeset *live = new_nodeset(ifg->env->cls->n_regs);
175 ir_node *live_irn = NULL;
178 assert(is_Block(bl) && "There is no block to work on");
180 foreach_border_head(head, b) /* follow the borders of each block */
184 create_node(ifg, b->irn); /* add the node to the array of all nodes of this ifg implementation */
185 nodeset_insert(live, b->irn);
186 if (b->is_real) /* this is a new node */
188 foreach_nodeset(live, live_irn)
190 if (b->irn != live_irn) /* add a as a neighbour to b and vice versa */
191 add_edge(ifg, b->irn, live_irn);
195 else /* b->irn is now dead */
197 if (nodeset_find(live, b->irn))
198 nodeset_remove(live, b->irn);
206 static ir_node *get_first_node(const ifg_list_t *ifg, nodes_iter_t *it)
209 adj_head_t *adj_head = NULL;
213 it->curr_node_idx = 0;
215 while (adj_head == NULL)
218 adj_head = ifg->adj_heads[curr_idx];
221 if (adj_head == NULL) /* there are no nodes in this ifg */
226 it->curr_node_idx = curr_idx;
232 static ir_node *get_next_node(nodes_iter_t *it)
234 const ifg_list_t *ifg = it->ifg;
236 adj_head_t *adj_head = NULL;
237 unsigned int curr_idx = it->curr_node_idx;
239 while (adj_head == NULL && curr_idx < it->ifg->env->irg->last_node_idx - 1)
242 adj_head = ifg->adj_heads[curr_idx];
245 if (adj_head == NULL) /* there are no more nodes in this ifg */
250 it->curr_node_idx = curr_idx;
256 static ir_node *get_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *curr_irn)
259 adj_head_t *adj_head = NULL;
261 adj_head = ifg->adj_heads[curr_irn->node_idx];
262 assert(adj_head && "There is no entry for this node");
264 it->curr_adj_element = NULL;
267 if (adj_head->first_adj_element) /* return first neighbour */
269 res = adj_head->first_adj_element->neighbour;
270 it->curr_adj_element = adj_head->first_adj_element;
272 else /* node has no neighbours */
278 static ir_node *get_next_neighbour(adj_iter_t *it)
281 adj_element_t *element = it->curr_adj_element;
283 if (element->next_adj_element) /* return next neighbour */
285 res = element->next_adj_element->neighbour;
286 it->curr_adj_element = element->next_adj_element;
288 else /* was last neighbour */
294 /* PUBLIC FUNCTIONS */
296 static void ifg_list_free(void *self)
298 ifg_list_t *ifg = self;
299 obstack_free(&ifg->obst, NULL);
300 free(ifg->adj_heads);
304 static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b)
306 const ifg_list_t *ifg = self;
308 adj_head_t *adj_head = NULL;
309 adj_element_t *curr_element = NULL;
311 /* first try: find b in the neigbours of a */
312 adj_head = ifg->adj_heads[a->node_idx];
314 assert(adj_head && "There is no entry for the node a");
315 curr_element = adj_head->first_adj_element;
319 while (curr_element->neighbour != b && curr_element->next_adj_element)
321 curr_element = curr_element->next_adj_element;
323 if (curr_element->neighbour == b)
328 else /* node a has no neighbours */
331 /* second try, this should not be necessary... only to check the solution */
332 adj_head = ifg->adj_heads[b->node_idx];
334 assert(adj_head && "There is no entry for the node b");
335 curr_element = adj_head->first_adj_element;
339 while (curr_element->neighbour != a && curr_element->next_adj_element)
341 curr_element = curr_element->next_adj_element;
343 if (curr_element->neighbour == a)
345 assert ("Found the neighbour only in the second try.");
351 else /* node b has no neighbours */
357 static ir_node *ifg_list_nodes_begin(const void *self, void *iter)
359 nodes_iter_t *it = iter;
360 return get_first_node(self, it);
363 static ir_node *ifg_list_nodes_next(const void *self, void *iter)
366 return get_next_node(iter);
369 static void ifg_list_nodes_break(const void *self, void *iter)
371 nodes_iter_t *it = iter;
373 it->curr_node_idx = 0;
377 static ir_node *ifg_list_neighbours_begin(const void *self, void *iter,const ir_node *irn)
379 adj_iter_t *it = iter;
380 return get_first_neighbour(self, it, irn);
383 static ir_node *ifg_list_neighbours_next(const void *self, void *iter)
386 return get_next_neighbour(iter);
389 static void ifg_list_neighbours_break(const void *self, void *iter)
391 adj_iter_t *it= iter;
393 it->curr_adj_element = NULL;
397 static int ifg_list_degree(const void *self, const ir_node *irn)
399 const ifg_list_t *ifg = self;
400 adj_head_t *adj_head = NULL;
402 adj_head = ifg->adj_heads[irn->node_idx];
404 assert (adj_head && "There is no entry for this node");
406 return adj_head->degree;
409 static const be_ifg_impl_t ifg_list_impl = {
410 sizeof(nodes_iter_t),
415 ifg_list_neighbours_begin,
416 ifg_list_neighbours_next,
417 ifg_list_neighbours_break,
418 ifg_list_nodes_begin,
420 ifg_list_nodes_break,
427 be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
429 ifg_list_t *ifg = xmalloc(sizeof(*ifg));
430 adj_head_t **adj_heads_array = xmalloc(env->irg->last_node_idx * sizeof(adj_heads_array[0]));
432 ifg->impl = &ifg_list_impl;
435 memset(adj_heads_array, 0, env->irg->last_node_idx * sizeof(adj_heads_array[0]));
436 ifg->adj_heads = adj_heads_array;
438 obstack_init(&ifg->obst);
439 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
440 obstack_finish(&ifg->obst);
442 return (be_ifg_t *) ifg;