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 * @author Sebastian Hack
27 * Simple depth first search on CFGs.
35 #define DISABLE_STATEV
45 static int cmp_edge(const void *a, const void *b, size_t sz)
47 const dfs_edge_t *p = a;
48 const dfs_edge_t *q = b;
51 return !(p->src == q->src && p->tgt == q->tgt);
54 static int cmp_node(const void *a, const void *b, size_t sz)
56 const dfs_node_t *p = a;
57 const dfs_node_t *q = b;
60 return p->node != q->node;
63 #define get_node(dfs, node) _dfs_get_node(dfs, node)
65 static dfs_edge_t *get_edge(const dfs_t *self, const void *src, const void *tgt)
67 unsigned hash = HASH_COMBINE(HASH_PTR(src), HASH_PTR(tgt));
74 return set_insert(self->edges, &templ, sizeof(templ), hash);
77 static void dfs_perform(dfs_t *dfs, void *n, void *anc, int level)
79 dfs_node_t *node = get_node(dfs, n);
82 assert(node->visited == 0);
87 node->pre_num = dfs->pre_num++;
88 node->max_pre_num = node->pre_num;
91 dfs->graph_impl->grow_succs(dfs->graph, n, &dfs->obst);
92 obstack_ptr_grow(&dfs->obst, NULL);
93 succs = obstack_finish(&dfs->obst);
95 for (iter = succs; *iter; ++iter) {
99 dfs_node_t *child = get_node(dfs, p);
101 /* create the edge object */
102 dfs_edge_t *edge = get_edge(dfs, n, p);
107 dfs_perform(dfs, p, node, level + 1);
109 /* get the maximum pre num of the subtree. needed for ancestor determination. */
110 node->max_pre_num = MAX(node->max_pre_num, child->max_pre_num);
113 node->post_num = dfs->post_num++;
114 obstack_free(&dfs->obst, succs);
117 static void classify_edges(dfs_t *dfs)
119 stat_ev_cnt_decl(anc);
120 stat_ev_cnt_decl(back);
121 stat_ev_cnt_decl(fwd);
122 stat_ev_cnt_decl(cross);
125 foreach_set (dfs->edges, edge) {
126 dfs_node_t *src = edge->s;
127 dfs_node_t *tgt = edge->t;
129 if (tgt->ancestor == src) {
130 stat_ev_cnt_inc(anc);
131 edge->kind = DFS_EDGE_ANC;
133 else if (_dfs_int_is_ancestor(tgt, src)) {
134 stat_ev_cnt_inc(back);
135 edge->kind = DFS_EDGE_BACK;
137 else if (_dfs_int_is_ancestor(src, tgt)) {
138 stat_ev_cnt_inc(fwd);
139 edge->kind = DFS_EDGE_FWD;
142 stat_ev_cnt_inc(cross);
143 edge->kind = DFS_EDGE_CROSS;
147 stat_ev_cnt_done(anc, "dfs_edge_anc");
148 stat_ev_cnt_done(back, "dfs_edge_back");
149 stat_ev_cnt_done(fwd, "dfs_edge_fwd");
150 stat_ev_cnt_done(cross, "dfs_edge_cross");
153 dfs_edge_kind_t dfs_get_edge_kind(const dfs_t *dfs, const void *a, const void *b)
155 if (!dfs->edges_classified) {
156 dfs_t *urg = (dfs_t *) dfs;
158 urg->edges_classified = 1;
160 return get_edge(dfs, a, b)->kind;
163 dfs_t *dfs_new(const absgraph_t *graph_impl, void *graph_self)
165 dfs_t *res = xmalloc(sizeof(res[0]));
168 res->graph_impl = graph_impl;
169 res->graph = graph_self;
170 res->nodes = new_set(cmp_node, 64);
171 res->edges = new_set(cmp_edge, 128);
175 res->edges_classified = 0;
177 obstack_init(&res->obst);
179 dfs_perform(res, graph_impl->get_root(graph_self), NULL, 0);
181 /* make sure the end node (which might not be accessible) has a number */
182 node = get_node(res, graph_impl->get_end(graph_self));
183 if (!node->visited) {
185 node->node = graph_impl->get_end(graph_self);
186 node->ancestor = NULL;
187 node->pre_num = res->pre_num++;
188 node->post_num = res->post_num++;
189 node->max_pre_num = node->pre_num;
195 assert(res->pre_num == res->post_num);
196 res->pre_order = xmalloc(res->pre_num * sizeof(res->pre_order));
197 res->post_order = xmalloc(res->post_num * sizeof(res->post_order));
198 foreach_set (res->nodes, node) {
199 assert(node->pre_num < res->pre_num);
200 assert(node->post_num < res->post_num);
202 res->pre_order[node->pre_num] = node;
203 res->post_order[node->post_num] = node;
206 stat_ev_dbl("dfs_n_blocks", res->pre_num);
211 void dfs_free(dfs_t *dfs)
215 xfree(dfs->pre_order);
216 xfree(dfs->post_order);
220 static void dfs_dump_edge(const dfs_edge_t *edge, FILE *file)
222 dfs_node_t *src = edge->s;
223 dfs_node_t *tgt = edge->t;
224 const char *s, *style;
227 #define XXX(e) case DFS_EDGE_ ## e: s = #e; break
228 switch (edge->kind) {
236 weight = edge->kind == DFS_EDGE_BACK ? 1 : 1000;
237 style = edge->kind == DFS_EDGE_BACK ? "dashed" : "solid";
239 ir_fprintf(file, "\tn%d -> n%d [label=\"%s\",style=\"%s\",weight=\"%d\"];\n", src->pre_num, tgt->pre_num, s, style, weight);
242 static int node_level_cmp(const void *a, const void *b)
244 const dfs_node_t *p = *(const dfs_node_t **) a;
245 const dfs_node_t *q = *(const dfs_node_t **) b;
247 if (p->level == q->level)
248 return p->pre_num - q->pre_num;
249 return p->level - q->level;
252 void dfs_dump(const dfs_t *dfs, FILE *file)
254 dfs_node_t **nodes = xmalloc(dfs->pre_num * sizeof(nodes[0]));
259 ir_fprintf(file, "digraph G {\nranksep=0.5\n");
260 foreach_set (dfs->nodes, node) {
264 qsort(nodes, n, sizeof(nodes[0]), node_level_cmp);
268 int level = nodes[i]->level;
270 ir_fprintf(file, "\t{ rank = same; ");
271 for (; i < n && nodes[i]->level == level; ++i)
272 ir_fprintf(file, "n%d;", nodes[i]->pre_num);
273 ir_fprintf(file, "}\n");
278 for (i = 0; i < n; ++i) {
279 dfs_node_t *node = nodes[i];
280 ir_fprintf(file, "\tn%d [label=\"%d\"]\n", node->pre_num, get_Block_dom_tree_pre_num(node->node));
282 ir_fprintf(file, "\tn%d [shape=box,label=\"%+F\\l%d %d/%d %d\"];\n",
283 node->pre_num, node->node, get_Block_dom_tree_pre_num(node->node),
284 node->pre_num, node->post_num, node->max_pre_num);
288 foreach_set (dfs->edges, edge)
289 dfs_dump_edge(edge, file);
291 ir_fprintf(file, "}\n");