X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fdfs.c;h=bc6da0a74e2e19884423249f83a0fb725b393bc3;hb=0f234e2d94155d13c0e4727871125beda0eaa66d;hp=6a8cb1070a2c778fc3fb848901bbdbf1e5f9668d;hpb=ac0462d2c9bacc6c0c59ce6dd3769b0ace5dc975;p=libfirm

diff --git a/ir/ana/dfs.c b/ir/ana/dfs.c
index 6a8cb1070..bc6da0a74 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.
  *
@@ -22,21 +22,22 @@
  * @author  Sebastian Hack
  * @date    20.04.2007
  * @version $Id$
- * @summary
+ * @brief
  *
  * Simple depth first search on CFGs.
  */
-#ifdef HAVE_CONFIG_H
 #include <config.h>
-#endif
 
 #include <stdlib.h>
 
+#define DISABLE_STATEV
+
 #include <assert.h>
 #include "irtools.h"
 #include "irprintf.h"
 #include "irdom.h"
 #include "set.h"
+#include "statev.h"
 #include "dfs_t.h"
 
 static int cmp_edge(const void *a, const void *b, size_t sz)
@@ -114,20 +115,37 @@ static void dfs_perform(dfs_t *dfs, void *n, void *anc, int level)
 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) {
 		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, const void *a, const void *b)
@@ -142,7 +160,7 @@ dfs_edge_kind_t dfs_get_edge_kind(const dfs_t *dfs, const void *a, const 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;
@@ -157,15 +175,34 @@ 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, 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));
+	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, 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;
 }
 
@@ -212,7 +249,7 @@ static int node_level_cmp(const void *a, const void *b)
 
 void dfs_dump(const dfs_t *dfs, FILE *file)
 {
-	dfs_node_t **nodes = xmalloc(dfs->pre_num * sizeof(nodes[0]));
+	dfs_node_t **nodes = XMALLOCN(dfs_node_t*, dfs->pre_num);
 	dfs_node_t *node;
 	dfs_edge_t *edge;
 	int i, n = 0;