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
34 #include "irgraph_t.h"
41 #include "bechordal_t.h"
44 typedef struct _adj_head_t adj_head_t;
46 typedef struct _ifg_list_t {
47 const be_ifg_impl_t *impl;
48 const be_chordal_env_t *env;
50 adj_head_t **adj_heads;
53 typedef struct _adj_element_t adj_element_t;
55 struct _adj_element_t {
56 adj_element_t *next_adj_element;
61 ir_node *irn; /* the node you search neighbours for */
62 adj_element_t *first_adj_element;
66 typedef struct _nodes_iter_t {
67 const ifg_list_t *ifg;
68 unsigned int curr_node_idx;
71 typedef struct _adj_iter_t {
72 const ifg_list_t *ifg;
73 adj_element_t *curr_adj_element;
76 /* PRIVATE FUNCTIONS */
78 /* add node to the array of all nodes in this ifg implementation, if the node isn't already in the ifg */
79 static void create_node(ifg_list_t *ifg, ir_node *irn)
81 adj_head_t *adj_head = NULL;
83 adj_head = ifg->adj_heads[irn->node_idx];
86 adj_head = obstack_alloc(&ifg->obst, sizeof(*adj_head));
88 adj_head->first_adj_element = NULL;
90 ifg->adj_heads[irn->node_idx] = adj_head;
94 static adj_element_t *create_adj_element(ifg_list_t *ifg, ir_node *irn)
96 adj_element_t *element = NULL;
98 element = obstack_alloc(&ifg->obst, sizeof(*element));
99 element->next_adj_element = NULL;
100 element->neighbour = irn;
105 /* write the information about the edge between a and b */
106 static void add_edge(ifg_list_t *ifg, ir_node *node_a, ir_node *node_b)
108 adj_head_t *adj_head = NULL;
109 adj_element_t *curr_element = NULL;
110 adj_element_t *new_element = NULL;
112 adj_head = ifg->adj_heads[node_a->node_idx]; /* find the neighbours list of a */
114 assert (adj_head && "There is no entry for node a");
115 curr_element = adj_head->first_adj_element;
119 while (curr_element->neighbour != node_b && curr_element->next_adj_element)
121 curr_element = curr_element->next_adj_element;
124 if (curr_element->neighbour != node_b && curr_element->next_adj_element == NULL)
127 new_element = create_adj_element(ifg, node_b); /* if b isn't in list, add b */
128 curr_element->next_adj_element = new_element;
134 new_element = create_adj_element(ifg, node_b); /* a has no neighbours, add b as the first one*/
135 adj_head->first_adj_element = new_element;
138 /* do the same vice versa */
139 adj_head = ifg->adj_heads[node_b->node_idx];
141 assert (adj_head && "There is no entry for node a");
142 curr_element = adj_head->first_adj_element;
146 while (curr_element->neighbour != node_a && curr_element->next_adj_element)
148 curr_element = curr_element->next_adj_element;
151 if (curr_element->neighbour != node_a && curr_element->next_adj_element == NULL)
154 new_element = create_adj_element(ifg, node_a);
155 curr_element->next_adj_element = new_element;
161 new_element = create_adj_element(ifg, node_a);
162 adj_head->first_adj_element = new_element;
166 /* find all adjacent nodes in the irg */
167 static void find_neighbour_walker(ir_node *bl, void *data)
169 ifg_list_t *ifg = data;
170 struct list_head *head = get_block_border_head(ifg->env, bl);
172 ir_node *live_irn = NULL;
175 ir_nodeset_init(&live);
177 assert(is_Block(bl) && "There is no block to work on");
179 foreach_border_head(head, b) /* follow the borders of each block */
183 create_node(ifg, b->irn); /* add the node to the array of all nodes of this ifg implementation */
184 ir_nodeset_insert(&live, b->irn);
185 if (b->is_real) /* this is a new node */
187 ir_nodeset_iterator_t iter;
189 foreach_ir_nodeset(&live, live_irn, iter)
191 if (b->irn != live_irn) /* add a as a neighbour to b and vice versa */
192 add_edge(ifg, b->irn, live_irn);
196 else /* b->irn is now dead */
198 ir_nodeset_remove(&live, b->irn);
202 ir_nodeset_destroy(&live);
205 static ir_node *get_first_node(const ifg_list_t *ifg, nodes_iter_t *it)
208 adj_head_t *adj_head = NULL;
212 it->curr_node_idx = 0;
214 while (adj_head == NULL)
217 adj_head = ifg->adj_heads[curr_idx];
220 if (adj_head == NULL) /* there are no nodes in this ifg */
225 it->curr_node_idx = curr_idx;
231 static ir_node *get_next_node(nodes_iter_t *it)
233 const ifg_list_t *ifg = it->ifg;
235 adj_head_t *adj_head = NULL;
236 unsigned int curr_idx = it->curr_node_idx;
238 while (adj_head == NULL && curr_idx < it->ifg->env->irg->last_node_idx - 1)
241 adj_head = ifg->adj_heads[curr_idx];
244 if (adj_head == NULL) /* there are no more nodes in this ifg */
249 it->curr_node_idx = curr_idx;
255 static ir_node *get_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *curr_irn)
258 adj_head_t *adj_head = NULL;
260 adj_head = ifg->adj_heads[curr_irn->node_idx];
261 assert(adj_head && "There is no entry for this node");
263 it->curr_adj_element = NULL;
266 if (adj_head->first_adj_element) /* return first neighbour */
268 res = adj_head->first_adj_element->neighbour;
269 it->curr_adj_element = adj_head->first_adj_element;
271 else /* node has no neighbours */
277 static ir_node *get_next_neighbour(adj_iter_t *it)
280 adj_element_t *element = it->curr_adj_element;
282 if (element->next_adj_element) /* return next neighbour */
284 res = element->next_adj_element->neighbour;
285 it->curr_adj_element = element->next_adj_element;
287 else /* was last neighbour */
293 /* PUBLIC FUNCTIONS */
295 static void ifg_list_free(void *self)
297 ifg_list_t *ifg = self;
298 obstack_free(&ifg->obst, NULL);
299 free(ifg->adj_heads);
303 static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b)
305 const ifg_list_t *ifg = self;
307 adj_head_t *adj_head = NULL;
308 adj_element_t *curr_element = NULL;
310 /* first try: find b in the neigbours of a */
311 adj_head = ifg->adj_heads[a->node_idx];
313 assert(adj_head && "There is no entry for the node a");
314 curr_element = adj_head->first_adj_element;
318 while (curr_element->neighbour != b && curr_element->next_adj_element)
320 curr_element = curr_element->next_adj_element;
322 if (curr_element->neighbour == b)
327 else /* node a has no neighbours */
330 /* second try, this should not be necessary... only to check the solution */
331 adj_head = ifg->adj_heads[b->node_idx];
333 assert(adj_head && "There is no entry for the node b");
334 curr_element = adj_head->first_adj_element;
338 while (curr_element->neighbour != a && curr_element->next_adj_element)
340 curr_element = curr_element->next_adj_element;
342 if (curr_element->neighbour == a)
344 assert ("Found the neighbour only in the second try.");
350 else /* node b has no neighbours */
356 static ir_node *ifg_list_nodes_begin(const void *self, void *iter)
358 nodes_iter_t *it = iter;
359 return get_first_node(self, it);
362 static ir_node *ifg_list_nodes_next(const void *self, void *iter)
365 return get_next_node(iter);
368 static void ifg_list_nodes_break(const void *self, void *iter)
370 nodes_iter_t *it = iter;
372 it->curr_node_idx = 0;
376 static ir_node *ifg_list_neighbours_begin(const void *self, void *iter,const ir_node *irn)
378 adj_iter_t *it = iter;
379 return get_first_neighbour(self, it, irn);
382 static ir_node *ifg_list_neighbours_next(const void *self, void *iter)
385 return get_next_neighbour(iter);
388 static void ifg_list_neighbours_break(const void *self, void *iter)
390 adj_iter_t *it= iter;
392 it->curr_adj_element = NULL;
396 static int ifg_list_degree(const void *self, const ir_node *irn)
398 const ifg_list_t *ifg = self;
399 adj_head_t *adj_head = NULL;
401 adj_head = ifg->adj_heads[irn->node_idx];
403 assert (adj_head && "There is no entry for this node");
405 return adj_head->degree;
408 static const be_ifg_impl_t ifg_list_impl = {
409 sizeof(nodes_iter_t),
414 ifg_list_neighbours_begin,
415 ifg_list_neighbours_next,
416 ifg_list_neighbours_break,
417 ifg_list_nodes_begin,
419 ifg_list_nodes_break,
426 be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
428 ifg_list_t *ifg = XMALLOC(ifg_list_t);
429 adj_head_t **adj_heads_array = XMALLOCNZ(adj_head_t*, env->irg->last_node_idx);
431 ifg->impl = &ifg_list_impl;
434 ifg->adj_heads = adj_heads_array;
436 obstack_init(&ifg->obst);
437 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
438 obstack_finish(&ifg->obst);
440 return (be_ifg_t *) ifg;