* @file dfs.c
* @author Sebastian Hack
* @date 20.04.2007
- * @version $Id: $
+ * @version $Id$
* @summary
*
* Simple depth first search on CFGs.
- *
- * Copyright (C) 2007 Universitaet Karlsruhe
- * Released under the GPL
*/
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <stdlib.h>
+
#include <assert.h>
#include "irtools.h"
#include "irprintf.h"
+#include "irdom.h"
#include "set.h"
+#include "statev.h"
#include "dfs_t.h"
+static const char *edge_names[] = {
+ "anc",
+ "fwd",
+ "cross",
+ "back"
+};
+
static int cmp_edge(const void *a, const void *b, size_t sz)
{
const dfs_edge_t *p = a;
const dfs_edge_t *q = b;
+ (void) sz;
return !(p->src == q->src && p->tgt == q->tgt);
}
{
const dfs_node_t *p = a;
const dfs_node_t *q = b;
+ (void) sz;
+
return p->node != q->node;
}
#define get_node(dfs, node) _dfs_get_node(dfs, node)
-static dfs_edge_t *get_edge(const dfs_t *self, void *src, void *tgt)
+static dfs_edge_t *get_edge(const dfs_t *self, const void *src, const void *tgt)
{
unsigned hash = HASH_COMBINE(HASH_PTR(src), HASH_PTR(tgt));
dfs_edge_t templ;
return set_insert(self->edges, &templ, sizeof(templ), hash);
}
-static void dfs_perform(dfs_t *dfs, void *n, void *anc)
+static void dfs_perform(dfs_t *dfs, void *n, void *anc, int level)
{
dfs_node_t *node = get_node(dfs, n);
void **succs, **iter;
node->ancestor = anc;
node->pre_num = dfs->pre_num++;
node->max_pre_num = node->pre_num;
+ node->level = level;
dfs->graph_impl->grow_succs(dfs->graph, n, &dfs->obst);
obstack_ptr_grow(&dfs->obst, NULL);
edge->t = child;
if (!child->visited)
- dfs_perform(dfs, p, node);
+ dfs_perform(dfs, p, node, level + 1);
/* get the maximum pre num of the subtree. needed for ancestor determination. */
node->max_pre_num = MAX(node->max_pre_num, child->max_pre_num);
static void classify_edges(dfs_t *dfs)
{
+ stat_ev_cnt_decl(anc);
+ stat_ev_cnt_decl(back);
+ stat_ev_cnt_decl(fwd);
+ stat_ev_cnt_decl(cross);
dfs_edge_t *edge;
foreach_set (dfs->edges, edge) {
dfs_node_t *src = edge->s;
dfs_node_t *tgt = edge->t;
- if (tgt->ancestor == src)
+ if (tgt->ancestor == src) {
+ stat_ev_cnt_inc(anc);
edge->kind = DFS_EDGE_ANC;
- else if (_dfs_int_is_ancestor(src, tgt))
- edge->kind = DFS_EDGE_FWD;
- else if (_dfs_int_is_ancestor(tgt, src))
+ }
+ else if (_dfs_int_is_ancestor(tgt, src)) {
+ stat_ev_cnt_inc(back);
edge->kind = DFS_EDGE_BACK;
- else
+ }
+ else if (_dfs_int_is_ancestor(src, tgt)) {
+ stat_ev_cnt_inc(fwd);
+ edge->kind = DFS_EDGE_FWD;
+ }
+ else {
+ stat_ev_cnt_inc(cross);
edge->kind = DFS_EDGE_CROSS;
+ }
}
+
+ stat_ev_cnt_done(anc, "dfs_edge_anc");
+ stat_ev_cnt_done(back, "dfs_edge_back");
+ stat_ev_cnt_done(fwd, "dfs_edge_fwd");
+ stat_ev_cnt_done(cross, "dfs_edge_cross");
}
-dfs_edge_kind_t dfs_get_edge_kind(const dfs_t *dfs, void *a, void *b)
+dfs_edge_kind_t dfs_get_edge_kind(const dfs_t *dfs, const void *a, const void *b)
{
if (!dfs->edges_classified) {
dfs_t *urg = (dfs_t *) dfs;
obstack_init(&res->obst);
- dfs_perform(res, graph_impl->get_root(graph_self), NULL);
+ dfs_perform(res, graph_impl->get_root(graph_self), NULL, 0);
classify_edges(res);
res->pre_order = xmalloc(res->pre_num * sizeof(res->pre_order));
res->post_order[node->post_num] = node;
}
+ stat_ev_dbl("dfs_n_blocks", res->pre_num);
+
return res;
}
xfree(dfs);
}
+static void dfs_dump_edge(const dfs_edge_t *edge, FILE *file)
+{
+ dfs_node_t *src = edge->s;
+ dfs_node_t *tgt = edge->t;
+ const char *s, *style;
+ int weight;
+
+#define XXX(e) case DFS_EDGE_ ## e: s = #e; break
+ switch (edge->kind) {
+ XXX(FWD);
+ XXX(CROSS);
+ default:
+ s = "";
+ }
+#undef XXX
+
+ weight = edge->kind == DFS_EDGE_BACK ? 1 : 1000;
+ style = edge->kind == DFS_EDGE_BACK ? "dashed" : "solid";
+
+ ir_fprintf(file, "\tn%d -> n%d [label=\"%s\",style=\"%s\",weight=\"%d\"];\n", src->pre_num, tgt->pre_num, s, style, weight);
+}
+
+static int node_level_cmp(const void *a, const void *b)
+{
+ const dfs_node_t *p = *(const dfs_node_t **) a;
+ const dfs_node_t *q = *(const dfs_node_t **) b;
+
+ if (p->level == q->level)
+ return p->pre_num - q->pre_num;
+ return p->level - q->level;
+}
+
void dfs_dump(const dfs_t *dfs, FILE *file)
{
+ dfs_node_t **nodes = xmalloc(dfs->pre_num * sizeof(nodes[0]));
dfs_node_t *node;
dfs_edge_t *edge;
+ int i, n = 0;
- ir_fprintf(file, "digraph G {\n");
+ ir_fprintf(file, "digraph G {\nranksep=0.5\n");
foreach_set (dfs->nodes, node) {
- ir_fprintf(file, "\tn%d [shape=box,label=\"%+F\\l%d/%d %d\"];\n",
- node->pre_num, node->node, node->pre_num, node->post_num, node->max_pre_num);
-
+ nodes[n++] = node;
}
- foreach_set (dfs->edges, edge) {
- dfs_node_t *src = edge->s;
- dfs_node_t *tgt = edge->t;
- const char *s, *color;
+ qsort(nodes, n, sizeof(nodes[0]), node_level_cmp);
-#define XXX(e) case DFS_EDGE_ ## e: s = #e; break
- switch (edge->kind) {
- XXX(BACK);
- XXX(FWD);
- XXX(CROSS);
- XXX(ANC);
- default:
- s = "?";
- }
-#undef XXX
+ i = 0;
+ while (i < n) {
+ int level = nodes[i]->level;
-#define XXX(e) case DFS_EDGE_ ## e
- switch (edge->kind) {
- XXX(ANC): color = "black"; break;
- XXX(FWD): color = "blue"; break;
- XXX(CROSS): color = "red"; break;
- XXX(BACK): color = "darkviolet"; break;
- default: color = "?";
- }
-#undef XXX
+ ir_fprintf(file, "\t{ rank = same; ");
+ for (; i < n && nodes[i]->level == level; ++i)
+ ir_fprintf(file, "n%d;", nodes[i]->pre_num);
+ ir_fprintf(file, "}\n");
- ir_fprintf(file, "\tn%d -> n%d [label=\"%s\",color=\"%s\"];\n", src->pre_num, tgt->pre_num, s, color);
+
+ }
+
+ for (i = 0; i < n; ++i) {
+ dfs_node_t *node = nodes[i];
+ ir_fprintf(file, "\tn%d [label=\"%d\"]\n", node->pre_num, get_Block_dom_tree_pre_num(node->node));
+#if 0
+ ir_fprintf(file, "\tn%d [shape=box,label=\"%+F\\l%d %d/%d %d\"];\n",
+ node->pre_num, node->node, get_Block_dom_tree_pre_num(node->node),
+ node->pre_num, node->post_num, node->max_pre_num);
+#endif
}
+ foreach_set (dfs->edges, edge)
+ dfs_dump_edge(edge, file);
+
ir_fprintf(file, "}\n");
+ xfree(nodes);
}
projects / libfirm / blobdiff