X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fana%2Fdfs.c;h=091800bc4349d435d3116a378be5be3d3cce62d1;hb=2bf74f898dd67f0004d7d5d1e9c41f4aa3a28bde;hp=a85064aeb0618b4f8363a86c0e738c52048a259d;hpb=edc739b393d7982e78a573d854113f47293c96b1;p=libfirm diff --git a/ir/ana/dfs.c b/ir/ana/dfs.c index a85064aeb..091800bc4 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,36 +21,28 @@ * @file dfs.c * @author Sebastian Hack * @date 20.04.2007 - * @version $Id$ - * @summary + * @brief * * Simple depth first search on CFGs. */ -#ifdef HAVE_CONFIG_H #include -#endif #include +#define DISABLE_STATEV + #include -#include "irtools.h" #include "irprintf.h" -#include "irdom.h" +#include "irdom_t.h" #include "set.h" -#include "statev.h" +#include "statev_t.h" #include "dfs_t.h" - -static const char *edge_names[] = { - "anc", - "fwd", - "cross", - "back" -}; +#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); @@ -58,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; @@ -69,14 +61,14 @@ static int cmp_node(const void *a, const void *b, size_t sz) 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 set_insert(dfs_edge_t, self->edges, &templ, sizeof(templ), hash); } static void dfs_perform(dfs_t *dfs, void *n, void *anc, int level) @@ -95,7 +87,7 @@ static void dfs_perform(dfs_t *dfs, void *n, void *anc, int 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; @@ -125,9 +117,8 @@ static void classify_edges(dfs_t *dfs) stat_ev_cnt_decl(back); stat_ev_cnt_decl(fwd); stat_ev_cnt_decl(cross); - dfs_edge_t *edge; - 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; @@ -167,8 +158,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_node_t *node; + dfs_t *res = XMALLOC(dfs_t); res->graph_impl = graph_impl; res->graph = graph_self; @@ -182,11 +172,28 @@ 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 */ + dfs_node_t *const 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; } @@ -198,6 +205,7 @@ dfs_t *dfs_new(const absgraph_t *graph_impl, void *graph_self) void dfs_free(dfs_t *dfs) { + obstack_free(&dfs->obst, NULL); del_set(dfs->nodes); del_set(dfs->edges); xfree(dfs->pre_order); @@ -212,7 +220,7 @@ static void dfs_dump_edge(const dfs_edge_t *edge, FILE *file) const char *s, *style; int weight; -#define XXX(e) case DFS_EDGE_ ## e: s = #e; break +#define XXX(e) case DFS_EDGE_ ## e: s = #e; break switch (edge->kind) { XXX(FWD); XXX(CROSS); @@ -239,13 +247,11 @@ 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 *node; - dfs_edge_t *edge; + dfs_node_t **nodes = XMALLOCN(dfs_node_t*, dfs->pre_num); int i, n = 0; ir_fprintf(file, "digraph G {\nranksep=0.5\n"); - foreach_set (dfs->nodes, node) { + foreach_set (dfs->nodes, dfs_node_t, node) { nodes[n++] = node; } @@ -264,8 +270,8 @@ void dfs_dump(const dfs_t *dfs, FILE *file) } 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)); + dfs_node_t *const 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), @@ -273,7 +279,7 @@ void dfs_dump(const dfs_t *dfs, FILE *file) #endif } - foreach_set (dfs->edges, edge) + foreach_set (dfs->edges, dfs_edge_t, edge) dfs_dump_edge(edge, file); ir_fprintf(file, "}\n");