2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @author Sebastian Hack
12 * Simple depth first search on CFGs.
18 #define DISABLE_STATEV
28 static int cmp_edge(const void *a, const void *b, size_t sz)
30 const dfs_edge_t *p = (const dfs_edge_t*) a;
31 const dfs_edge_t *q = (const dfs_edge_t*) b;
34 return !(p->src == q->src && p->tgt == q->tgt);
37 static int cmp_node(const void *a, const void *b, size_t sz)
39 const dfs_node_t *p = (const dfs_node_t*) a;
40 const dfs_node_t *q = (const dfs_node_t*) b;
43 return p->node != q->node;
46 #define get_node(dfs, node) _dfs_get_node(dfs, node)
48 static dfs_edge_t *get_edge(const dfs_t *self, const void *src, const void *tgt)
50 unsigned hash = hash_combine(hash_ptr(src), hash_ptr(tgt));
55 templ.kind = (dfs_edge_kind_t) -1;
57 return set_insert(dfs_edge_t, self->edges, &templ, sizeof(templ), hash);
60 static void dfs_perform(dfs_t *dfs, void *n, void *anc, int level)
62 dfs_node_t *node = get_node(dfs, n);
65 assert(node->visited == 0);
70 node->pre_num = dfs->pre_num++;
71 node->max_pre_num = node->pre_num;
74 dfs->graph_impl->grow_succs(dfs->graph, n, &dfs->obst);
75 obstack_ptr_grow(&dfs->obst, NULL);
76 succs = (void**) obstack_finish(&dfs->obst);
78 for (iter = succs; *iter; ++iter) {
82 dfs_node_t *child = get_node(dfs, p);
84 /* create the edge object */
85 dfs_edge_t *edge = get_edge(dfs, n, p);
90 dfs_perform(dfs, p, node, level + 1);
92 /* get the maximum pre num of the subtree. needed for ancestor determination. */
93 node->max_pre_num = MAX(node->max_pre_num, child->max_pre_num);
96 node->post_num = dfs->post_num++;
97 obstack_free(&dfs->obst, succs);
100 static void classify_edges(dfs_t *dfs)
102 stat_ev_cnt_decl(anc);
103 stat_ev_cnt_decl(back);
104 stat_ev_cnt_decl(fwd);
105 stat_ev_cnt_decl(cross);
107 foreach_set (dfs->edges, dfs_edge_t, edge) {
108 dfs_node_t *src = edge->s;
109 dfs_node_t *tgt = edge->t;
111 if (tgt->ancestor == src) {
112 stat_ev_cnt_inc(anc);
113 edge->kind = DFS_EDGE_ANC;
115 else if (_dfs_int_is_ancestor(tgt, src)) {
116 stat_ev_cnt_inc(back);
117 edge->kind = DFS_EDGE_BACK;
119 else if (_dfs_int_is_ancestor(src, tgt)) {
120 stat_ev_cnt_inc(fwd);
121 edge->kind = DFS_EDGE_FWD;
124 stat_ev_cnt_inc(cross);
125 edge->kind = DFS_EDGE_CROSS;
129 stat_ev_cnt_done(anc, "dfs_edge_anc");
130 stat_ev_cnt_done(back, "dfs_edge_back");
131 stat_ev_cnt_done(fwd, "dfs_edge_fwd");
132 stat_ev_cnt_done(cross, "dfs_edge_cross");
135 dfs_edge_kind_t dfs_get_edge_kind(const dfs_t *dfs, const void *a, const void *b)
137 if (!dfs->edges_classified) {
138 dfs_t *urg = (dfs_t *) dfs;
140 urg->edges_classified = 1;
142 return get_edge(dfs, a, b)->kind;
145 dfs_t *dfs_new(const absgraph_t *graph_impl, void *graph_self)
147 dfs_t *res = XMALLOC(dfs_t);
149 res->graph_impl = graph_impl;
150 res->graph = graph_self;
151 res->nodes = new_set(cmp_node, 64);
152 res->edges = new_set(cmp_edge, 128);
156 res->edges_classified = 0;
158 obstack_init(&res->obst);
160 dfs_perform(res, graph_impl->get_root(graph_self), NULL, 0);
162 /* make sure the end node (which might not be accessible) has a number */
163 dfs_node_t *const node = get_node(res, graph_impl->get_end(graph_self));
164 if (!node->visited) {
166 node->node = graph_impl->get_end(graph_self);
167 node->ancestor = NULL;
168 node->pre_num = res->pre_num++;
169 node->post_num = res->post_num++;
170 node->max_pre_num = node->pre_num;
176 assert(res->pre_num == res->post_num);
177 res->pre_order = XMALLOCN(dfs_node_t*, res->pre_num);
178 res->post_order = XMALLOCN(dfs_node_t*, res->post_num);
179 foreach_set (res->nodes, dfs_node_t, node) {
180 assert(node->pre_num < res->pre_num);
181 assert(node->post_num < res->post_num);
183 res->pre_order[node->pre_num] = node;
184 res->post_order[node->post_num] = node;
187 stat_ev_dbl("dfs_n_blocks", res->pre_num);
192 void dfs_free(dfs_t *dfs)
194 obstack_free(&dfs->obst, NULL);
197 xfree(dfs->pre_order);
198 xfree(dfs->post_order);
202 static void dfs_dump_edge(const dfs_edge_t *edge, FILE *file)
204 dfs_node_t *src = edge->s;
205 dfs_node_t *tgt = edge->t;
206 const char *s, *style;
209 #define XXX(e) case DFS_EDGE_ ## e: s = #e; break
210 switch (edge->kind) {
218 weight = edge->kind == DFS_EDGE_BACK ? 1 : 1000;
219 style = edge->kind == DFS_EDGE_BACK ? "dashed" : "solid";
221 ir_fprintf(file, "\tn%d -> n%d [label=\"%s\",style=\"%s\",weight=\"%d\"];\n", src->pre_num, tgt->pre_num, s, style, weight);
224 static int node_level_cmp(const void *a, const void *b)
226 const dfs_node_t *p = *(const dfs_node_t **) a;
227 const dfs_node_t *q = *(const dfs_node_t **) b;
229 if (p->level == q->level)
230 return p->pre_num - q->pre_num;
231 return p->level - q->level;
234 void dfs_dump(const dfs_t *dfs, FILE *file)
236 dfs_node_t **nodes = XMALLOCN(dfs_node_t*, dfs->pre_num);
239 ir_fprintf(file, "digraph G {\nranksep=0.5\n");
240 foreach_set (dfs->nodes, dfs_node_t, node) {
244 qsort(nodes, n, sizeof(nodes[0]), node_level_cmp);
248 int level = nodes[i]->level;
250 ir_fprintf(file, "\t{ rank = same; ");
251 for (; i < n && nodes[i]->level == level; ++i)
252 ir_fprintf(file, "n%d;", nodes[i]->pre_num);
253 ir_fprintf(file, "}\n");
258 for (i = 0; i < n; ++i) {
259 dfs_node_t *const node = nodes[i];
260 ir_fprintf(file, "\tn%d [label=\"%d\"]\n", node->pre_num, get_Block_dom_tree_pre_num((ir_node*) node->node));
263 foreach_set (dfs->edges, dfs_edge_t, edge)
264 dfs_dump_edge(edge, file);
266 ir_fprintf(file, "}\n");