/*
- * 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.
*
*
* 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)
#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;
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, 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;
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;
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;
}
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;