nsz Git - libfirm/blob - ir/ana/dfs.c

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file    dfs.c
  22  * @author  Sebastian Hack
  23  * @date    20.04.2007
  24  * @version $Id$
  25  * @summary
  26  *
  27  * Simple depth first search on CFGs.
  28  */
  29 #ifdef HAVE_CONFIG_H
  30 #include <config.h>
  31 #endif
  32
  33 #include <assert.h>
  34 #include "irtools.h"
  35 #include "irprintf.h"
  36 #include "set.h"
  37 #include "dfs_t.h"
  38
  39 static int cmp_edge(const void *a, const void *b, size_t sz)
  40 {
  41         const dfs_edge_t *p = a;
  42         const dfs_edge_t *q = b;
  43         (void) sz;
  44
  45         return !(p->src == q->src && p->tgt == q->tgt);
  46 }
  47
  48 static int cmp_node(const void *a, const void *b, size_t sz)
  49 {
  50         const dfs_node_t *p = a;
  51         const dfs_node_t *q = b;
  52         (void) sz;
  53
  54         return p->node != q->node;
  55 }
  56
  57 #define get_node(dfs, node) _dfs_get_node(dfs, node)
  58
  59 static dfs_edge_t *get_edge(const dfs_t *self, void *src, void *tgt)
  60 {
  61         unsigned hash = HASH_COMBINE(HASH_PTR(src), HASH_PTR(tgt));
  62         dfs_edge_t templ;
  63
  64         templ.src = src;
  65         templ.tgt = tgt;
  66         templ.kind = -1;
  67
  68         return set_insert(self->edges, &templ, sizeof(templ), hash);
  69 }
  70
  71 static void dfs_perform(dfs_t *dfs, void *n, void *anc)
  72 {
  73         dfs_node_t *node = get_node(dfs, n);
  74         void **succs, **iter;
  75
  76         assert(node->visited == 0);
  77
  78         node->visited     = 1;
  79         node->node        = n;
  80         node->ancestor    = anc;
  81         node->pre_num     = dfs->pre_num++;
  82         node->max_pre_num = node->pre_num;
  83
  84         dfs->graph_impl->grow_succs(dfs->graph, n, &dfs->obst);
  85         obstack_ptr_grow(&dfs->obst, NULL);
  86         succs = obstack_finish(&dfs->obst);
  87
  88         for (iter = succs; *iter; ++iter) {
  89                 void *p = *iter;
  90
  91                 /* get the node */
  92                 dfs_node_t *child = get_node(dfs, p);
  93
  94                 /* create the edge object */
  95                 dfs_edge_t *edge = get_edge(dfs, n, p);
  96                 edge->s = node;
  97                 edge->t = child;
  98
  99                 if (!child->visited)
 100                         dfs_perform(dfs, p, node);
 101
 102                 /* get the maximum pre num of the subtree. needed for ancestor determination. */
 103                 node->max_pre_num = MAX(node->max_pre_num, child->max_pre_num);
 104         }
 105
 106         node->post_num = dfs->post_num++;
 107         obstack_free(&dfs->obst, succs);
 108 }
 109
 110 static void classify_edges(dfs_t *dfs)
 111 {
 112         dfs_edge_t *edge;
 113
 114         foreach_set (dfs->edges, edge) {
 115                 dfs_node_t *src = edge->s;
 116                 dfs_node_t *tgt = edge->t;
 117
 118                 if (tgt->ancestor == src)
 119                         edge->kind = DFS_EDGE_ANC;
 120                 else if (_dfs_int_is_ancestor(tgt, src))
 121                         edge->kind = DFS_EDGE_BACK;
 122                 else if (_dfs_int_is_ancestor(src, tgt))
 123                         edge->kind = DFS_EDGE_FWD;
 124                 else
 125                         edge->kind = DFS_EDGE_CROSS;
 126         }
 127 }
 128
 129 dfs_edge_kind_t dfs_get_edge_kind(const dfs_t *dfs, void *a, void *b)
 130 {
 131         if (!dfs->edges_classified) {
 132                 dfs_t *urg = (dfs_t *) dfs;
 133                 classify_edges(urg);
 134                 urg->edges_classified = 1;
 135         }
 136         return get_edge(dfs, a, b)->kind;
 137 }
 138
 139 dfs_t *dfs_new(const absgraph_t *graph_impl, void *graph_self)
 140 {
 141         dfs_t *res = xmalloc(sizeof(res[0]));
 142         dfs_node_t *node;
 143
 144         res->graph_impl = graph_impl;
 145         res->graph      = graph_self;
 146         res->nodes      = new_set(cmp_node, 64);
 147         res->edges      = new_set(cmp_edge, 128);
 148
 149         res->pre_num  = 0;
 150         res->post_num = 0;
 151         res->edges_classified = 0;
 152
 153         obstack_init(&res->obst);
 154
 155         dfs_perform(res, graph_impl->get_root(graph_self), NULL);
 156         classify_edges(res);
 157
 158         res->pre_order = xmalloc(res->pre_num * sizeof(res->pre_order));
 159         res->post_order = xmalloc(res->pre_num * sizeof(res->post_order));
 160         foreach_set (res->nodes, node) {
 161                 res->pre_order[node->pre_num] = node;
 162                 res->post_order[node->post_num] = node;
 163         }
 164
 165         return res;
 166 }
 167
 168 void dfs_free(dfs_t *dfs)
 169 {
 170         del_set(dfs->nodes);
 171         del_set(dfs->edges);
 172         xfree(dfs->pre_order);
 173         xfree(dfs->post_order);
 174         xfree(dfs);
 175 }
 176
 177 void dfs_dump(const dfs_t *dfs, FILE *file)
 178 {
 179         dfs_node_t *node;
 180         dfs_edge_t *edge;
 181
 182         ir_fprintf(file, "digraph G {\n");
 183         foreach_set (dfs->nodes, node) {
 184                 ir_fprintf(file, "\tn%d [shape=box,label=\"%+F\\l%d/%d %d\"];\n",
 185                                 node->pre_num, node->node, node->pre_num, node->post_num, node->max_pre_num);
 186
 187         }
 188
 189         foreach_set (dfs->edges, edge) {
 190                 dfs_node_t *src = edge->s;
 191                 dfs_node_t *tgt = edge->t;
 192                 const char *s, *color;
 193
 194 #define XXX(e)          case DFS_EDGE_ ## e: s = #e; break
 195                 switch (edge->kind) {
 196                         XXX(BACK);
 197                         XXX(FWD);
 198                         XXX(CROSS);
 199                         XXX(ANC);
 200                         default:
 201                         s = "?";
 202                 }
 203 #undef XXX
 204
 205 #define XXX(e)  case DFS_EDGE_ ## e
 206                 switch (edge->kind) {
 207                         XXX(ANC):   color = "black"; break;
 208                         XXX(FWD):   color = "blue"; break;
 209                         XXX(CROSS): color = "red"; break;
 210                         XXX(BACK):  color = "darkviolet"; break;
 211                         default: color = "?";
 212                 }
 213 #undef XXX
 214
 215                 ir_fprintf(file, "\tn%d -> n%d [label=\"%s\",color=\"%s\"];\n", src->pre_num, tgt->pre_num, s, color);
 216         }
 217
 218         ir_fprintf(file, "}\n");
 219 }