X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fdfs.c;h=b10895a769214f736f1c98fdd9205209541f6849;hb=b402f0c11a621b8cb99d685afa5eb2f8c94a6fed;hp=880706e6733b2333ad67148ace0b219a6c96f6ec;hpb=1b57293234c2f0c753f48c94e0ca0f127b15a27b;p=libfirm

diff --git a/ir/ana/dfs.c b/ir/ana/dfs.c
index 880706e67..b10895a76 100644
--- a/ir/ana/dfs.c
+++ b/ir/ana/dfs.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
+ * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
  *
  * This file is part of libFirm.
  *
@@ -21,21 +21,28 @@
  * @file    dfs.c
  * @author  Sebastian Hack
  * @date    20.04.2007
- * @version $Id$
- * @summary
+ * @brief
  *
  * Simple depth first search on CFGs.
  */
+#include <config.h>
+
+#include <stdlib.h>
+
+#define DISABLE_STATEV
+
 #include <assert.h>
-#include "irtools.h"
 #include "irprintf.h"
+#include "irdom_t.h"
 #include "set.h"
+#include "statev.h"
 #include "dfs_t.h"
+#include "util.h"
 
 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;
+	const dfs_edge_t *p = (const dfs_edge_t*) a;
+	const dfs_edge_t *q = (const dfs_edge_t*) b;
 	(void) sz;
 
 	return !(p->src == q->src && p->tgt == q->tgt);
@@ -43,8 +50,8 @@ static int cmp_edge(const void *a, const void *b, size_t sz)
 
 static int cmp_node(const void *a, const void *b, size_t sz)
 {
-	const dfs_node_t *p = a;
-	const dfs_node_t *q = b;
+	const dfs_node_t *p = (const dfs_node_t*) a;
+	const dfs_node_t *q = (const dfs_node_t*) b;
 	(void) sz;
 
 	return p->node != q->node;
@@ -52,19 +59,19 @@ static int cmp_node(const void *a, const void *b, size_t sz)
 
 #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));
+	unsigned hash = hash_combine(hash_ptr(src), hash_ptr(tgt));
 	dfs_edge_t templ;
 
 	templ.src = src;
 	templ.tgt = tgt;
-	templ.kind = -1;
+	templ.kind = (dfs_edge_kind_t) -1;
 
-	return set_insert(self->edges, &templ, sizeof(templ), hash);
+	return (dfs_edge_t*) 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;
@@ -76,10 +83,11 @@ static void dfs_perform(dfs_t *dfs, void *n, void *anc)
 	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);
-	succs = obstack_finish(&dfs->obst);
+	succs = (void**) obstack_finish(&dfs->obst);
 
 	for (iter = succs; *iter; ++iter) {
 		void *p = *iter;
@@ -93,7 +101,7 @@ static void dfs_perform(dfs_t *dfs, void *n, void *anc)
 		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);
@@ -106,23 +114,40 @@ static void dfs_perform(dfs_t *dfs, void *n, void *anc)
 static void classify_edges(dfs_t *dfs)
 {
 	dfs_edge_t *edge;
+	stat_ev_cnt_decl(anc);
+	stat_ev_cnt_decl(back);
+	stat_ev_cnt_decl(fwd);
+	stat_ev_cnt_decl(cross);
 
-	foreach_set (dfs->edges, edge) {
+	foreach_set (dfs->edges, dfs_edge_t, 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(tgt, src))
+		}
+		else if (_dfs_int_is_ancestor(tgt, src)) {
+			stat_ev_cnt_inc(back);
 			edge->kind = DFS_EDGE_BACK;
-		else if (_dfs_int_is_ancestor(src, tgt))
+		}
+		else if (_dfs_int_is_ancestor(src, tgt)) {
+			stat_ev_cnt_inc(fwd);
 			edge->kind = DFS_EDGE_FWD;
-		else
+		}
+		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;
@@ -134,7 +159,7 @@ dfs_edge_kind_t dfs_get_edge_kind(const dfs_t *dfs, void *a, void *b)
 
 dfs_t *dfs_new(const absgraph_t *graph_impl, void *graph_self)
 {
-	dfs_t *res = xmalloc(sizeof(res[0]));
+	dfs_t *res = XMALLOC(dfs_t);
 	dfs_node_t *node;
 
 	res->graph_impl = graph_impl;
@@ -148,21 +173,41 @@ dfs_t *dfs_new(const absgraph_t *graph_impl, void *graph_self)
 
 	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);
+
+	/* make sure the end node (which might not be accessible) has a number */
+	node = get_node(res, graph_impl->get_end(graph_self));
+	if (!node->visited) {
+		node->visited     = 1;
+		node->node        = graph_impl->get_end(graph_self);
+		node->ancestor    = NULL;
+		node->pre_num     = res->pre_num++;
+		node->post_num    = res->post_num++;
+		node->max_pre_num = node->pre_num;
+		node->level       = 0;
+	}
+
 	classify_edges(res);
 
-	res->pre_order = xmalloc(res->pre_num * sizeof(res->pre_order));
-	res->post_order = xmalloc(res->pre_num * sizeof(res->post_order));
-	foreach_set (res->nodes, node) {
+	assert(res->pre_num == res->post_num);
+	res->pre_order  = XMALLOCN(dfs_node_t*, res->pre_num);
+	res->post_order = XMALLOCN(dfs_node_t*, res->post_num);
+	foreach_set (res->nodes, dfs_node_t, node) {
+		assert(node->pre_num < res->pre_num);
+		assert(node->post_num < res->post_num);
+
 		res->pre_order[node->pre_num] = node;
 		res->post_order[node->post_num] = node;
 	}
 
+	stat_ev_dbl("dfs_n_blocks", res->pre_num);
+
 	return res;
 }
 
 void dfs_free(dfs_t *dfs)
 {
+	obstack_free(&dfs->obst, NULL);
 	del_set(dfs->nodes);
 	del_set(dfs->edges);
 	xfree(dfs->pre_order);
@@ -170,46 +215,77 @@ void dfs_free(dfs_t *dfs)
 	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 = XMALLOCN(dfs_node_t*, dfs->pre_num);
 	dfs_node_t *node;
 	dfs_edge_t *edge;
+	int i, n = 0;
 
-	ir_fprintf(file, "digraph G {\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);
-
+	ir_fprintf(file, "digraph G {\nranksep=0.5\n");
+	foreach_set (dfs->nodes, dfs_node_t, node) {
+		nodes[n++] = node;
 	}
 
-	foreach_set (dfs->edges, edge) {
-		dfs_node_t *src = edge->s;
-		dfs_node_t *tgt = edge->t;
-		const char *s, *color;
-
-#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
+	qsort(nodes, n, sizeof(nodes[0]), node_level_cmp);
 
-#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
+	i = 0;
+	while (i < n) {
+		int level = nodes[i]->level;
+
+		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) {
+		node = nodes[i];
+		ir_fprintf(file, "\tn%d [label=\"%d\"]\n", node->pre_num, get_Block_dom_tree_pre_num((ir_node*) 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, dfs_edge_t, edge)
+		dfs_dump_edge(edge, file);
+
 	ir_fprintf(file, "}\n");
+	xfree(nodes);
 }