4 * @author Sebastian Hack
6 * Simple depth first search on CFGs.
8 * Copyright (C) 2007 Universitaet Karlsruhe
9 * Released under the GPL
18 static int cmp_edge(const void *a, const void *b, size_t sz)
20 const dfs_edge_t *p = a;
21 const dfs_edge_t *q = b;
23 return !(p->src == q->src && p->tgt == q->tgt);
26 static int cmp_node(const void *a, const void *b, size_t sz)
28 const dfs_node_t *p = a;
29 const dfs_node_t *q = b;
30 return p->node != q->node;
33 #define get_node(dfs, node) _dfs_get_node(dfs, node)
35 static dfs_edge_t *get_edge(const dfs_t *self, void *src, void *tgt)
37 unsigned hash = HASH_COMBINE(HASH_PTR(src), HASH_PTR(tgt));
44 return set_insert(self->edges, &templ, sizeof(templ), hash);
47 static void dfs_perform(dfs_t *dfs, void *n, void *anc)
49 dfs_node_t *node = get_node(dfs, n);
52 assert(node->visited == 0);
57 node->pre_num = dfs->pre_num++;
58 node->max_pre_num = node->pre_num;
60 dfs->graph_impl->grow_succs(dfs->graph, n, &dfs->obst);
61 obstack_ptr_grow(&dfs->obst, NULL);
62 succs = obstack_finish(&dfs->obst);
64 for (iter = succs; *iter; ++iter) {
68 dfs_node_t *child = get_node(dfs, p);
70 /* create the edge object */
71 dfs_edge_t *edge = get_edge(dfs, n, p);
76 dfs_perform(dfs, p, node);
78 /* get the maximum pre num of the subtree. needed for ancestor determination. */
79 node->max_pre_num = MAX(node->max_pre_num, child->max_pre_num);
82 node->post_num = dfs->post_num++;
83 obstack_free(&dfs->obst, succs);
86 static void classify_edges(dfs_t *dfs)
90 foreach_set (dfs->edges, edge) {
91 dfs_node_t *src = edge->s;
92 dfs_node_t *tgt = edge->t;
94 if (tgt->ancestor == src)
95 edge->kind = DFS_EDGE_ANC;
96 else if (_dfs_int_is_ancestor(src, tgt))
97 edge->kind = DFS_EDGE_FWD;
98 else if (_dfs_int_is_ancestor(tgt, src))
99 edge->kind = DFS_EDGE_BACK;
101 edge->kind = DFS_EDGE_CROSS;
105 dfs_edge_kind_t dfs_get_edge_kind(const dfs_t *dfs, void *a, void *b)
107 if (!dfs->edges_classified) {
108 dfs_t *urg = (dfs_t *) dfs;
110 urg->edges_classified = 1;
112 return get_edge(dfs, a, b)->kind;
115 dfs_t *dfs_new(const absgraph_t *graph_impl, void *graph_self)
117 dfs_t *res = xmalloc(sizeof(res[0]));
120 res->graph_impl = graph_impl;
121 res->graph = graph_self;
122 res->nodes = new_set(cmp_node, 64);
123 res->edges = new_set(cmp_edge, 128);
127 res->edges_classified = 0;
129 obstack_init(&res->obst);
131 dfs_perform(res, graph_impl->get_root(graph_self), NULL);
134 res->pre_order = xmalloc(res->pre_num * sizeof(res->pre_order));
135 res->post_order = xmalloc(res->pre_num * sizeof(res->post_order));
136 foreach_set (res->nodes, node) {
137 res->pre_order[node->pre_num] = node;
138 res->post_order[node->post_num] = node;
144 void dfs_free(dfs_t *dfs)
148 xfree(dfs->pre_order);
149 xfree(dfs->post_order);
153 void dfs_dump(const dfs_t *dfs, FILE *file)
158 ir_fprintf(file, "digraph G {\n");
159 foreach_set (dfs->nodes, node) {
160 ir_fprintf(file, "\tn%d [shape=box,label=\"%+F\\l%d/%d %d\"];\n",
161 node->pre_num, node->node, node->pre_num, node->post_num, node->max_pre_num);
165 foreach_set (dfs->edges, edge) {
166 dfs_node_t *src = edge->s;
167 dfs_node_t *tgt = edge->t;
168 const char *s, *color;
170 #define XXX(e) case DFS_EDGE_ ## e: s = #e; break
171 switch (edge->kind) {
181 #define XXX(e) case DFS_EDGE_ ## e
182 switch (edge->kind) {
183 XXX(ANC): color = "black"; break;
184 XXX(FWD): color = "blue"; break;
185 XXX(CROSS): color = "red"; break;
186 XXX(BACK): color = "darkviolet"; break;
187 default: color = "?";
191 ir_fprintf(file, "\tn%d -> n%d [label=\"%s\",color=\"%s\"];\n", src->pre_num, tgt->pre_num, s, color);
194 ir_fprintf(file, "}\n");