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
23 * @author Sebastian Hack
25 * Copyright (C) 2005 Universitaet Karlsruhe
26 * Released under the GPL
35 #include "benodesets.h"
39 #include "irgraph_t.h"
45 #include "bechordal_t.h"
48 typedef struct _adj_head_t adj_head_t;
50 typedef struct _ifg_list_t {
51 const be_ifg_impl_t *impl;
52 const be_chordal_env_t *env;
54 adj_head_t **adj_heads;
57 typedef struct _adj_element_t adj_element_t;
59 struct _adj_element_t {
60 adj_element_t *next_adj_element;
65 ir_node *irn; /* the node you search neighbours for */
66 adj_element_t *first_adj_element;
70 typedef struct _nodes_iter_t {
71 const ifg_list_t *ifg;
72 unsigned int curr_node_idx;
75 typedef struct _adj_iter_t {
76 const ifg_list_t *ifg;
77 adj_element_t *curr_adj_element;
80 /* PRIVATE FUNCTIONS */
82 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 */
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 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 */
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 static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in the irg */
170 ifg_list_t *ifg = data;
171 struct list_head *head = get_block_border_head(ifg->env, bl);
173 nodeset *live = new_nodeset(ifg->env->cls->n_regs);
174 ir_node *live_irn = NULL;
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 nodeset_insert(live, b->irn);
185 if (b->is_real) /* this is a new node */
187 foreach_nodeset(live, live_irn)
189 if (b->irn != live_irn) /* add a as a neighbour to b and vice versa */
190 add_edge(ifg, b->irn, live_irn);
194 else /* b->irn is now dead */
196 if (nodeset_find(live, b->irn))
197 nodeset_remove(live, b->irn);
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)
364 return get_next_node(iter);
367 static void ifg_list_nodes_break(const void *self, void *iter)
369 nodes_iter_t *it = iter;
370 it->curr_node_idx = 0;
374 static ir_node *ifg_list_neighbours_begin(const void *self, void *iter,const ir_node *irn)
376 adj_iter_t *it = iter;
377 return get_first_neighbour(self, it, irn);
380 static ir_node *ifg_list_neighbours_next(const void *self, void *iter)
382 return get_next_neighbour(iter);
385 static void ifg_list_neighbours_break(const void *self, void *iter)
387 adj_iter_t *it= iter;
388 it->curr_adj_element = NULL;
392 static int ifg_list_degree(const void *self, const ir_node *irn)
394 const ifg_list_t *ifg = self;
395 adj_head_t *adj_head = NULL;
397 adj_head = ifg->adj_heads[irn->node_idx];
399 assert (adj_head && "There is no entry for this node");
401 return adj_head->degree;
404 static const be_ifg_impl_t ifg_list_impl = {
405 sizeof(nodes_iter_t),
410 ifg_list_neighbours_begin,
411 ifg_list_neighbours_next,
412 ifg_list_neighbours_break,
413 ifg_list_nodes_begin,
415 ifg_list_nodes_break,
422 be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
424 ifg_list_t *ifg = xmalloc(sizeof(*ifg));
425 adj_head_t **adj_heads_array = xmalloc(env->irg->last_node_idx * sizeof(adj_heads_array[0]));
427 ifg->impl = &ifg_list_impl;
430 memset(adj_heads_array, 0, env->irg->last_node_idx * sizeof(adj_heads_array[0]));
431 ifg->adj_heads = adj_heads_array;
433 obstack_init(&ifg->obst);
434 dom_tree_walk_irg(env->irg, find_neighbour_walker, NULL, ifg);
435 obstack_finish(&ifg->obst);
437 return (be_ifg_t *) ifg;