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

   1 /**
   2  * @file   dfs.c
   3  * @date   20.04.2007
   4  * @author Sebastian Hack
   5  *
   6  * Simple depth first search on CFGs.
   7  *
   8  * Copyright (C) 2007 Universitaet Karlsruhe
   9  * Released under the GPL
  10  */
  11
  12 #include "assert.h"
  13 #include "irtools.h"
  14 #include "irprintf.h"
  15 #include "set.h"
  16 #include "dfs_t.h"
  17
  18 static int cmp_edge(const void *a, const void *b, size_t sz)
  19 {
  20         const dfs_edge_t *p = a;
  21         const dfs_edge_t *q = b;
  22
  23         return !(p->src == q->src && p->tgt == q->tgt);
  24 }
  25
  26 static int cmp_node(const void *a, const void *b, size_t sz)
  27 {
  28         const dfs_node_t *p = a;
  29         const dfs_node_t *q = b;
  30         return p->node != q->node;
  31 }
  32
  33 #define get_node(dfs, node) _dfs_get_node(dfs, node)
  34
  35 static dfs_edge_t *get_edge(const dfs_t *self, void *src, void *tgt)
  36 {
  37         unsigned hash = HASH_COMBINE(HASH_PTR(src), HASH_PTR(tgt));
  38         dfs_edge_t templ;
  39
  40         templ.src = src;
  41         templ.tgt = tgt;
  42         templ.kind = -1;
  43
  44         return set_insert(self->edges, &templ, sizeof(templ), hash);
  45 }
  46
  47 static void dfs_perform(dfs_t *dfs, void *n, void *anc)
  48 {
  49         dfs_node_t *node = get_node(dfs, n);
  50         void **succs, **iter;
  51
  52         assert(node->visited == 0);
  53
  54         node->visited     = 1;
  55         node->node        = n;
  56         node->ancestor    = anc;
  57         node->pre_num     = dfs->pre_num++;
  58         node->max_pre_num = node->pre_num;
  59
  60         dfs->graph_impl->grow_succs(dfs->graph, n, &dfs->obst);
  61         obstack_ptr_grow(&dfs->obst, NULL);
  62         succs = obstack_finish(&dfs->obst);
  63
  64         for (iter = succs; *iter; ++iter) {
  65                 void *p = *iter;
  66
  67                 /* get the node */
  68                 dfs_node_t *child = get_node(dfs, p);
  69
  70                 /* create the edge object */
  71                 dfs_edge_t *edge = get_edge(dfs, n, p);
  72                 edge->s = node;
  73                 edge->t = child;
  74
  75                 if (!child->visited)
  76                         dfs_perform(dfs, p, node);
  77
  78                 /* get the maximum pre num of the subtree. needed for ancestor determination. */
  79                 node->max_pre_num = MAX(node->max_pre_num, child->max_pre_num);
  80         }
  81
  82         node->post_num = dfs->post_num++;
  83         obstack_free(&dfs->obst, succs);
  84 }
  85
  86 static void classify_edges(dfs_t *dfs)
  87 {
  88         dfs_edge_t *edge;
  89
  90         foreach_set (dfs->edges, edge) {
  91                 dfs_node_t *src = edge->s;
  92                 dfs_node_t *tgt = edge->t;
  93
  94                 if (tgt->ancestor == src)
  95                         edge->kind = DFS_EDGE_ANC;
  96                 else if (_dfs_int_is_ancestor(src, tgt))
  97                         edge->kind = DFS_EDGE_FWD;
  98                 else if (_dfs_int_is_ancestor(tgt, src))
  99                         edge->kind = DFS_EDGE_BACK;
 100                 else
 101                         edge->kind = DFS_EDGE_CROSS;
 102         }
 103 }
 104
 105 dfs_edge_kind_t dfs_get_edge_kind(const dfs_t *dfs, void *a, void *b)
 106 {
 107         if (!dfs->edges_classified) {
 108                 dfs_t *urg = (dfs_t *) dfs;
 109                 classify_edges(urg);
 110                 urg->edges_classified = 1;
 111         }
 112         return get_edge(dfs, a, b)->kind;
 113 }
 114
 115 dfs_t *dfs_new(const absgraph_t *graph_impl, void *graph_self)
 116 {
 117         dfs_t *res = xmalloc(sizeof(res[0]));
 118         dfs_node_t *node;
 119
 120         res->graph_impl = graph_impl;
 121         res->graph      = graph_self;
 122         res->nodes      = new_set(cmp_node, 64);
 123         res->edges      = new_set(cmp_edge, 128);
 124
 125         res->pre_num  = 0;
 126         res->post_num = 0;
 127         res->edges_classified = 0;
 128
 129         obstack_init(&res->obst);
 130
 131         dfs_perform(res, graph_impl->get_root(graph_self), NULL);
 132         classify_edges(res);
 133
 134         res->pre_order = xmalloc(res->pre_num * sizeof(res->pre_order));
 135         res->post_order = xmalloc(res->pre_num * sizeof(res->post_order));
 136         foreach_set (res->nodes, node) {
 137                 res->pre_order[node->pre_num] = node;
 138                 res->post_order[node->post_num] = node;
 139         }
 140
 141         return res;
 142 }
 143
 144 void dfs_free(dfs_t *dfs)
 145 {
 146         del_set(dfs->nodes);
 147         del_set(dfs->edges);
 148         xfree(dfs->pre_order);
 149         xfree(dfs->post_order);
 150         xfree(dfs);
 151 }
 152
 153 void dfs_dump(const dfs_t *dfs, FILE *file)
 154 {
 155         dfs_node_t *node;
 156         dfs_edge_t *edge;
 157
 158         ir_fprintf(file, "digraph G {\n");
 159         foreach_set (dfs->nodes, node) {
 160                 ir_fprintf(file, "\tn%d [shape=box,label=\"%+F\\l%d/%d %d\"];\n",
 161                                 node->pre_num, node->node, node->pre_num, node->post_num, node->max_pre_num);
 162
 163         }
 164
 165         foreach_set (dfs->edges, edge) {
 166                 dfs_node_t *src = edge->s;
 167                 dfs_node_t *tgt = edge->t;
 168                 const char *s, *color;
 169
 170 #define XXX(e)          case DFS_EDGE_ ## e: s = #e; break
 171                 switch (edge->kind) {
 172                         XXX(BACK);
 173                         XXX(FWD);
 174                         XXX(CROSS);
 175                         XXX(ANC);
 176                         default:
 177                         s = "?";
 178                 }
 179 #undef XXX
 180
 181 #define XXX(e)  case DFS_EDGE_ ## e
 182                 switch (edge->kind) {
 183                         XXX(ANC):   color = "black"; break;
 184                         XXX(FWD):   color = "blue"; break;
 185                         XXX(CROSS): color = "red"; break;
 186                         XXX(BACK):  color = "darkviolet"; break;
 187                         default: color = "?";
 188                 }
 189 #undef XXX
 190
 191                 ir_fprintf(file, "\tn%d -> n%d [label=\"%s\",color=\"%s\"];\n", src->pre_num, tgt->pre_num, s, color);
 192         }
 193
 194         ir_fprintf(file, "}\n");
 195 }