2 * Copyright (C) 1995-2008 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
36 #include "irgraph_t.h"
43 #include "bechordal_t.h"
46 typedef struct _adj_head_t adj_head_t;
48 typedef struct _ifg_list_t {
49 const be_ifg_impl_t *impl;
50 const be_chordal_env_t *env;
52 adj_head_t **adj_heads;
55 typedef struct _adj_element_t adj_element_t;
57 struct _adj_element_t {
58 adj_element_t *next_adj_element;
63 ir_node *irn; /* the node you search neighbours for */
64 adj_element_t *first_adj_element;
68 typedef struct _nodes_iter_t {
69 const ifg_list_t *ifg;
70 unsigned int curr_node_idx;
73 typedef struct _adj_iter_t {
74 const ifg_list_t *ifg;
75 adj_element_t *curr_adj_element;
78 /* PRIVATE FUNCTIONS */
80 /* add node to the array of all nodes in this ifg implementation, if the node isn't already in the ifg */
81 static void create_node(ifg_list_t *ifg, ir_node *irn)
83 adj_head_t *adj_head = NULL;
85 adj_head = ifg->adj_heads[irn->node_idx];
88 adj_head = obstack_alloc(&ifg->obst, sizeof(*adj_head));
90 adj_head->first_adj_element = NULL;
92 ifg->adj_heads[irn->node_idx] = adj_head;
96 static adj_element_t *create_adj_element(ifg_list_t *ifg, ir_node *irn)
98 adj_element_t *element = NULL;
100 element = obstack_alloc(&ifg->obst, sizeof(*element));
101 element->next_adj_element = NULL;
102 element->neighbour = irn;
107 /* write the information about the edge between a and b */
108 static void add_edge(ifg_list_t *ifg, ir_node *node_a, ir_node *node_b)
110 adj_head_t *adj_head = NULL;
111 adj_element_t *curr_element = NULL;
112 adj_element_t *new_element = NULL;
114 adj_head = ifg->adj_heads[node_a->node_idx]; /* find the neighbours list of a */
116 assert (adj_head && "There is no entry for node a");
117 curr_element = adj_head->first_adj_element;
121 while (curr_element->neighbour != node_b && curr_element->next_adj_element)
123 curr_element = curr_element->next_adj_element;
126 if (curr_element->neighbour != node_b && curr_element->next_adj_element == NULL)
129 new_element = create_adj_element(ifg, node_b); /* if b isn't in list, add b */
130 curr_element->next_adj_element = new_element;
136 new_element = create_adj_element(ifg, node_b); /* a has no neighbours, add b as the first one*/
137 adj_head->first_adj_element = new_element;
140 /* do the same vice versa */
141 adj_head = ifg->adj_heads[node_b->node_idx];
143 assert (adj_head && "There is no entry for node a");
144 curr_element = adj_head->first_adj_element;
148 while (curr_element->neighbour != node_a && curr_element->next_adj_element)
150 curr_element = curr_element->next_adj_element;
153 if (curr_element->neighbour != node_a && curr_element->next_adj_element == NULL)
156 new_element = create_adj_element(ifg, node_a);
157 curr_element->next_adj_element = new_element;
163 new_element = create_adj_element(ifg, node_a);
164 adj_head->first_adj_element = new_element;
168 /* find all adjacent nodes in the irg */
169 static void find_neighbour_walker(ir_node *bl, void *data)
171 ifg_list_t *ifg = data;
172 struct list_head *head = get_block_border_head(ifg->env, bl);
174 ir_node *live_irn = NULL;
177 ir_nodeset_init(&live);
179 assert(is_Block(bl) && "There is no block to work on");
181 foreach_border_head(head, b) /* follow the borders of each block */
185 create_node(ifg, b->irn); /* add the node to the array of all nodes of this ifg implementation */
186 ir_nodeset_insert(&live, b->irn);
187 if (b->is_real) /* this is a new node */
189 ir_nodeset_iterator_t iter;
191 foreach_ir_nodeset(&live, live_irn, iter)
193 if (b->irn != live_irn) /* add a as a neighbour to b and vice versa */
194 add_edge(ifg, b->irn, live_irn);
198 else /* b->irn is now dead */
200 ir_nodeset_remove(&live, b->irn);
204 ir_nodeset_destroy(&live);
207 static ir_node *get_first_node(const ifg_list_t *ifg, nodes_iter_t *it)
210 adj_head_t *adj_head = NULL;
214 it->curr_node_idx = 0;
216 while (adj_head == NULL)
219 adj_head = ifg->adj_heads[curr_idx];
222 if (adj_head == NULL) /* there are no nodes in this ifg */
227 it->curr_node_idx = curr_idx;
233 static ir_node *get_next_node(nodes_iter_t *it)
235 const ifg_list_t *ifg = it->ifg;
237 adj_head_t *adj_head = NULL;
238 unsigned int curr_idx = it->curr_node_idx;
240 while (adj_head == NULL && curr_idx < it->ifg->env->irg->last_node_idx - 1)
243 adj_head = ifg->adj_heads[curr_idx];
246 if (adj_head == NULL) /* there are no more nodes in this ifg */
251 it->curr_node_idx = curr_idx;
257 static ir_node *get_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *curr_irn)
260 adj_head_t *adj_head = NULL;
262 adj_head = ifg->adj_heads[curr_irn->node_idx];
263 assert(adj_head && "There is no entry for this node");
265 it->curr_adj_element = NULL;
268 if (adj_head->first_adj_element) /* return first neighbour */
270 res = adj_head->first_adj_element->neighbour;
271 it->curr_adj_element = adj_head->first_adj_element;
273 else /* node has no neighbours */
279 static ir_node *get_next_neighbour(adj_iter_t *it)
282 adj_element_t *element = it->curr_adj_element;
284 if (element->next_adj_element) /* return next neighbour */
286 res = element->next_adj_element->neighbour;
287 it->curr_adj_element = element->next_adj_element;
289 else /* was last neighbour */
295 /* PUBLIC FUNCTIONS */
297 static void ifg_list_free(void *self)
299 ifg_list_t *ifg = self;
300 obstack_free(&ifg->obst, NULL);
301 free(ifg->adj_heads);
305 static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b)
307 const ifg_list_t *ifg = self;
309 adj_head_t *adj_head = NULL;
310 adj_element_t *curr_element = NULL;
312 /* first try: find b in the neigbours of a */
313 adj_head = ifg->adj_heads[a->node_idx];
315 assert(adj_head && "There is no entry for the node a");
316 curr_element = adj_head->first_adj_element;
320 while (curr_element->neighbour != b && curr_element->next_adj_element)
322 curr_element = curr_element->next_adj_element;
324 if (curr_element->neighbour == b)
329 else /* node a has no neighbours */
332 /* second try, this should not be necessary... only to check the solution */
333 adj_head = ifg->adj_heads[b->node_idx];
335 assert(adj_head && "There is no entry for the node b");
336 curr_element = adj_head->first_adj_element;
340 while (curr_element->neighbour != a && curr_element->next_adj_element)
342 curr_element = curr_element->next_adj_element;
344 if (curr_element->neighbour == a)
346 assert ("Found the neighbour only in the second try.");
352 else /* node b has no neighbours */
358 static ir_node *ifg_list_nodes_begin(const void *self, void *iter)
360 nodes_iter_t *it = iter;
361 return get_first_node(self, it);
364 static ir_node *ifg_list_nodes_next(const void *self, void *iter)
367 return get_next_node(iter);
370 static void ifg_list_nodes_break(const void *self, void *iter)
372 nodes_iter_t *it = iter;
374 it->curr_node_idx = 0;
378 static ir_node *ifg_list_neighbours_begin(const void *self, void *iter,const ir_node *irn)
380 adj_iter_t *it = iter;
381 return get_first_neighbour(self, it, irn);
384 static ir_node *ifg_list_neighbours_next(const void *self, void *iter)
387 return get_next_neighbour(iter);
390 static void ifg_list_neighbours_break(const void *self, void *iter)
392 adj_iter_t *it= iter;
394 it->curr_adj_element = NULL;
398 static int ifg_list_degree(const void *self, const ir_node *irn)
400 const ifg_list_t *ifg = self;
401 adj_head_t *adj_head = NULL;
403 adj_head = ifg->adj_heads[irn->node_idx];
405 assert (adj_head && "There is no entry for this node");
407 return adj_head->degree;
410 static const be_ifg_impl_t ifg_list_impl = {
411 sizeof(nodes_iter_t),
416 ifg_list_neighbours_begin,
417 ifg_list_neighbours_next,
418 ifg_list_neighbours_break,
419 ifg_list_nodes_begin,
421 ifg_list_nodes_break,
428 be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
430 ifg_list_t *ifg = xmalloc(sizeof(*ifg));
431 adj_head_t **adj_heads_array = xmalloc(env->irg->last_node_idx * sizeof(adj_heads_array[0]));
433 ifg->impl = &ifg_list_impl;
436 memset(adj_heads_array, 0, env->irg->last_node_idx * sizeof(adj_heads_array[0]));
437 ifg->adj_heads = adj_heads_array;
439 obstack_init(&ifg->obst);
440 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
441 obstack_finish(&ifg->obst);
443 return (be_ifg_t *) ifg;