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 Interface for interference graphs.
23 * @author Sebastian Hack
32 #include "lc_opts_enum.h"
42 #include "irphase_t.h"
46 #include "becopystat.h"
47 #include "becopyopt.h"
50 #include "beintlive_t.h"
52 void be_ifg_free(be_ifg_t *self)
57 int be_ifg_connected(const be_ifg_t *ifg, const ir_node *a, const ir_node *b)
59 be_lv_t *lv = be_get_irg_liveness(ifg->env->irg);
60 return be_values_interfere(lv, a, b);
63 static void nodes_walker(ir_node *bl, void *data)
65 nodes_iter_t *it = data;
66 struct list_head *head = get_block_border_head(it->env, bl);
69 foreach_border_head(head, b) {
70 if (b->is_def && b->is_real) {
71 obstack_ptr_grow(&it->obst, b->irn);
77 static void find_nodes(const be_ifg_t *ifg, nodes_iter_t *iter)
79 obstack_init(&iter->obst);
84 irg_block_walk_graph(ifg->env->irg, nodes_walker, NULL, iter);
85 obstack_ptr_grow(&iter->obst, NULL);
86 iter->nodes = obstack_finish(&iter->obst);
89 static inline void node_break(nodes_iter_t *it, int force)
91 if ((it->curr >= it->n || force) && it->nodes) {
92 obstack_free(&it->obst, NULL);
97 static ir_node *get_next_node(nodes_iter_t *it)
101 if (it->curr < it->n)
102 res = it->nodes[it->curr++];
109 ir_node *be_ifg_nodes_begin(const be_ifg_t *ifg, nodes_iter_t *iter)
111 find_nodes(ifg, iter);
112 return get_next_node(iter);
115 ir_node *be_ifg_nodes_next(nodes_iter_t *iter)
117 return get_next_node(iter);
120 void be_ifg_nodes_break(nodes_iter_t *iter)
125 static void find_neighbour_walker(ir_node *block, void *data)
127 neighbours_iter_t *it = data;
128 struct list_head *head = get_block_border_head(it->env, block);
129 be_lv_t *lv = be_get_irg_liveness(it->env->irg);
134 if (!be_is_live_in(lv, block, it->irn) && block != get_nodes_block(it->irn))
137 foreach_border_head(head, b) {
138 ir_node *irn = b->irn;
140 if (irn == it->irn) {
144 break; /* if we reached the end of the node's lifetime we can safely break */
146 else if (b->is_def) {
147 /* if any other node than the one in question starts living, add it to the set */
148 ir_nodeset_insert(&it->neighbours, irn);
150 else if (!has_started) {
151 /* we only delete, if the live range in question has not yet started */
152 ir_nodeset_remove(&it->neighbours, irn);
158 static void find_neighbours(const be_ifg_t *ifg, neighbours_iter_t *it, const ir_node *irn)
163 ir_nodeset_init(&it->neighbours);
165 dom_tree_walk(get_nodes_block(irn), find_neighbour_walker, NULL, it);
167 ir_nodeset_iterator_init(&it->iter, &it->neighbours);
170 static inline void neighbours_break(neighbours_iter_t *it, int force)
173 assert(it->valid == 1);
174 ir_nodeset_destroy(&it->neighbours);
178 static ir_node *get_next_neighbour(neighbours_iter_t *it)
180 ir_node *res = ir_nodeset_iterator_next(&it->iter);
183 ir_nodeset_destroy(&it->neighbours);
188 ir_node *be_ifg_neighbours_begin(const be_ifg_t *ifg, neighbours_iter_t *iter,
191 find_neighbours(ifg, iter, irn);
192 return ir_nodeset_iterator_next(&iter->iter);
195 ir_node *be_ifg_neighbours_next(neighbours_iter_t *iter)
197 return get_next_neighbour(iter);
200 void be_ifg_neighbours_break(neighbours_iter_t *iter)
202 neighbours_break(iter, 1);
205 static inline void free_clique_iter(cliques_iter_t *it)
208 obstack_free(&it->ob, NULL);
209 del_pset(it->living);
212 static void get_blocks_dom_order(ir_node *blk, void *env)
214 cliques_iter_t *it = env;
215 obstack_ptr_grow(&it->ob, blk);
219 * NOTE: Be careful when changing this function!
220 * First understand the control flow of consecutive calls.
222 static inline int get_next_clique(cliques_iter_t *it)
225 /* continue in the block we left the last time */
226 for (; it->blk < it->n_blocks; it->blk++) {
227 int output_on_shrink = 0;
228 struct list_head *head = get_block_border_head(it->cenv, it->blocks[it->blk]);
230 /* on entry to a new block set the first border ... */
232 it->bor = head->prev;
234 /* ... otherwise continue with the border we left the last time */
235 for (; it->bor != head; it->bor = it->bor->prev) {
236 border_t *b = list_entry(it->bor, border_t, list);
238 /* if its a definition irn starts living */
240 pset_insert_ptr(it->living, b->irn);
242 output_on_shrink = 1;
245 /* if its the last usage the irn dies */
247 /* before shrinking the set, return the current maximal clique */
248 if (output_on_shrink) {
252 /* fill the output buffer */
253 for (irn = pset_first(it->living); irn != NULL;
254 irn = pset_next(it->living)) {
255 it->buf[count++] = irn;
258 assert(count > 0 && "We have a 'last usage', so there must be sth. in it->living");
263 pset_remove_ptr(it->living, b->irn);
268 assert(0 == pset_count(it->living) && "Something has survived! (At the end of the block it->living must be empty)");
271 if (it->n_blocks != -1)
272 free_clique_iter(it);
277 int be_ifg_cliques_begin(const be_ifg_t *ifg, cliques_iter_t *it,
280 ir_node *start_bl = get_irg_start_block(ifg->env->irg);
282 obstack_init(&it->ob);
283 dom_tree_walk(start_bl, get_blocks_dom_order, NULL, it);
287 it->n_blocks = obstack_object_size(&it->ob) / sizeof(void *);
288 it->blocks = obstack_finish(&it->ob);
291 it->living = pset_new_ptr(2 * arch_register_class_n_regs(it->cenv->cls));
293 return get_next_clique(it);
296 int be_ifg_cliques_next(cliques_iter_t *iter)
298 return get_next_clique(iter);
301 void be_ifg_cliques_break(cliques_iter_t *iter)
303 free_clique_iter(iter);
306 int be_ifg_degree(const be_ifg_t *ifg, const ir_node *irn)
308 neighbours_iter_t it;
310 find_neighbours(ifg, &it, irn);
311 degree = ir_nodeset_size(&it.neighbours);
312 neighbours_break(&it, 1);
316 be_ifg_t *be_create_ifg(const be_chordal_env_t *env)
318 be_ifg_t *ifg = XMALLOC(be_ifg_t);
324 void be_ifg_dump_dot(be_ifg_t *ifg, ir_graph *irg, FILE *file, const be_ifg_dump_dot_cb_t *cb, void *self)
326 nodes_iter_t nodes_it;
327 neighbours_iter_t neigh_it;
328 bitset_t *nodes = bitset_malloc(get_irg_last_idx(irg));
332 fprintf(file, "graph G {\n\tgraph [");
334 cb->graph_attr(file, self);
335 fprintf(file, "];\n");
338 cb->at_begin(file, self);
340 be_ifg_foreach_node(ifg, &nodes_it, n) {
341 if (cb->is_dump_node && cb->is_dump_node(self, n)) {
342 int idx = get_irn_idx(n);
343 bitset_set(nodes, idx);
344 fprintf(file, "\tnode [");
346 cb->node_attr(file, self, n);
347 fprintf(file, "]; n%d;\n", idx);
351 /* Check, if all neighbours are indeed connected to the node. */
352 be_ifg_foreach_node(ifg, &nodes_it, n) {
353 be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) {
354 int n_idx = get_irn_idx(n);
355 int m_idx = get_irn_idx(m);
357 if (n_idx < m_idx && bitset_is_set(nodes, n_idx) && bitset_is_set(nodes, m_idx)) {
358 fprintf(file, "\tn%d -- n%d [", n_idx, m_idx);
360 cb->edge_attr(file, self, n, m);
361 fprintf(file, "];\n");
367 cb->at_end(file, self);
369 fprintf(file, "}\n");
373 static void int_comp_rec(be_ifg_t *ifg, ir_node *n, bitset_t *seen)
375 neighbours_iter_t neigh_it;
378 be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) {
379 if (bitset_contains_irn(seen, m))
382 if (arch_get_register_req_out(m)->type & arch_register_req_type_ignore)
385 bitset_add_irn(seen, m);
386 int_comp_rec(ifg, m, seen);
391 static int int_component_stat(ir_graph *irg, be_ifg_t *ifg)
394 nodes_iter_t nodes_it;
395 bitset_t *seen = bitset_irg_malloc(irg);
399 be_ifg_foreach_node(ifg, &nodes_it, n) {
400 if (bitset_contains_irn(seen, n))
403 if (arch_get_register_req_out(n)->type & arch_register_req_type_ignore)
407 bitset_add_irn(seen, n);
408 int_comp_rec(ifg, n, seen);
415 void be_ifg_stat(ir_graph *irg, be_ifg_t *ifg, be_ifg_stat_t *stat)
417 nodes_iter_t nodes_it;
418 neighbours_iter_t neigh_it;
419 bitset_t *nodes = bitset_irg_malloc(irg);
422 memset(stat, 0, sizeof(stat[0]));
424 be_ifg_foreach_node(ifg, &nodes_it, n) {
426 be_ifg_foreach_neighbour(ifg, &neigh_it, n, m) {
427 bitset_add_irn(nodes, n);
428 stat->n_edges += !bitset_contains_irn(nodes, m);
432 stat->n_comps = int_component_stat(irg, ifg);