/*
- * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
- *
* This file is part of libFirm.
- *
- * This file may be distributed and/or modified under the terms of the
- * GNU General Public License version 2 as published by the Free Software
- * Foundation and appearing in the file LICENSE.GPL included in the
- * packaging of this file.
- *
- * Licensees holding valid libFirm Professional Edition licenses may use
- * this file in accordance with the libFirm Commercial License.
- * Agreement provided with the Software.
- *
- * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
- * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE.
+ * Copyright (C) 2012 University of Karlsruhe.
*/
/**
- * @file dfs.c
+ * @file
* @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 "irdom_t.h"
#include "set.h"
-#include "statev.h"
+#include "statev_t.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);
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;
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)
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;
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;
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;
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));
+ 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);
classify_edges(res);
assert(res->pre_num == res->post_num);
- res->pre_order = xmalloc(res->pre_num * sizeof(res->pre_order));
- res->post_order = xmalloc(res->post_num * sizeof(res->post_order));
- foreach_set (res->nodes, node) {
+ 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);
void dfs_free(dfs_t *dfs)
{
+ obstack_free(&dfs->obst, NULL);
del_set(dfs->nodes);
del_set(dfs->edges);
xfree(dfs->pre_order);
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);
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;
}
}
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
+ 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));
}
- foreach_set (dfs->edges, edge)
+ foreach_set (dfs->edges, dfs_edge_t, edge)
dfs_dump_edge(edge, file);
ir_fprintf(file, "}\n");
projects / libfirm / blobdiff