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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @author  Sebastian Hack
   9  * @date    20.04.2007
  10  * @brief
  11  *
  12  * Simple depth first search on CFGs.
  13  */
  14 #include <config.h>
  15
  16 #include <stdlib.h>
  17
  18 #define DISABLE_STATEV
  19
  20 #include <assert.h>
  21 #include "irprintf.h"
  22 #include "irdom_t.h"
  23 #include "set.h"
  24 #include "statev_t.h"
  25 #include "dfs_t.h"
  26 #include "util.h"
  27
  28 static int cmp_edge(const void *a, const void *b, size_t sz)
  29 {
  30         const dfs_edge_t *p = (const dfs_edge_t*) a;
  31         const dfs_edge_t *q = (const dfs_edge_t*) b;
  32         (void) sz;
  33
  34         return !(p->src == q->src && p->tgt == q->tgt);
  35 }
  36
  37 static int cmp_node(const void *a, const void *b, size_t sz)
  38 {
  39         const dfs_node_t *p = (const dfs_node_t*) a;
  40         const dfs_node_t *q = (const dfs_node_t*) b;
  41         (void) sz;
  42
  43         return p->node != q->node;
  44 }
  45
  46 #define get_node(dfs, node) _dfs_get_node(dfs, node)
  47
  48 static dfs_edge_t *get_edge(const dfs_t *self, const void *src, const void *tgt)
  49 {
  50         unsigned hash = hash_combine(hash_ptr(src), hash_ptr(tgt));
  51         dfs_edge_t templ;
  52
  53         templ.src = src;
  54         templ.tgt = tgt;
  55         templ.kind = (dfs_edge_kind_t) -1;
  56
  57         return set_insert(dfs_edge_t, self->edges, &templ, sizeof(templ), hash);
  58 }
  59
  60 static void dfs_perform(dfs_t *dfs, void *n, void *anc, int level)
  61 {
  62         dfs_node_t *node = get_node(dfs, n);
  63         void **succs, **iter;
  64
  65         assert(node->visited == 0);
  66
  67         node->visited     = 1;
  68         node->node        = n;
  69         node->ancestor    = anc;
  70         node->pre_num     = dfs->pre_num++;
  71         node->max_pre_num = node->pre_num;
  72         node->level       = level;
  73
  74         dfs->graph_impl->grow_succs(dfs->graph, n, &dfs->obst);
  75         obstack_ptr_grow(&dfs->obst, NULL);
  76         succs = (void**) obstack_finish(&dfs->obst);
  77
  78         for (iter = succs; *iter; ++iter) {
  79                 void *p = *iter;
  80
  81                 /* get the node */
  82                 dfs_node_t *child = get_node(dfs, p);
  83
  84                 /* create the edge object */
  85                 dfs_edge_t *edge = get_edge(dfs, n, p);
  86                 edge->s = node;
  87                 edge->t = child;
  88
  89                 if (!child->visited)
  90                         dfs_perform(dfs, p, node, level + 1);
  91
  92                 /* get the maximum pre num of the subtree. needed for ancestor determination. */
  93                 node->max_pre_num = MAX(node->max_pre_num, child->max_pre_num);
  94         }
  95
  96         node->post_num = dfs->post_num++;
  97         obstack_free(&dfs->obst, succs);
  98 }
  99
 100 static void classify_edges(dfs_t *dfs)
 101 {
 102         stat_ev_cnt_decl(anc);
 103         stat_ev_cnt_decl(back);
 104         stat_ev_cnt_decl(fwd);
 105         stat_ev_cnt_decl(cross);
 106
 107         foreach_set (dfs->edges, dfs_edge_t, edge) {
 108                 dfs_node_t *src = edge->s;
 109                 dfs_node_t *tgt = edge->t;
 110
 111                 if (tgt->ancestor == src) {
 112                         stat_ev_cnt_inc(anc);
 113                         edge->kind = DFS_EDGE_ANC;
 114                 }
 115                 else if (_dfs_int_is_ancestor(tgt, src)) {
 116                         stat_ev_cnt_inc(back);
 117                         edge->kind = DFS_EDGE_BACK;
 118                 }
 119                 else if (_dfs_int_is_ancestor(src, tgt)) {
 120                         stat_ev_cnt_inc(fwd);
 121                         edge->kind = DFS_EDGE_FWD;
 122                 }
 123                 else {
 124                         stat_ev_cnt_inc(cross);
 125                         edge->kind = DFS_EDGE_CROSS;
 126                 }
 127         }
 128
 129         stat_ev_cnt_done(anc,   "dfs_edge_anc");
 130         stat_ev_cnt_done(back,  "dfs_edge_back");
 131         stat_ev_cnt_done(fwd,   "dfs_edge_fwd");
 132         stat_ev_cnt_done(cross, "dfs_edge_cross");
 133 }
 134
 135 dfs_edge_kind_t dfs_get_edge_kind(const dfs_t *dfs, const void *a, const void *b)
 136 {
 137         if (!dfs->edges_classified) {
 138                 dfs_t *urg = (dfs_t *) dfs;
 139                 classify_edges(urg);
 140                 urg->edges_classified = 1;
 141         }
 142         return get_edge(dfs, a, b)->kind;
 143 }
 144
 145 dfs_t *dfs_new(const absgraph_t *graph_impl, void *graph_self)
 146 {
 147         dfs_t *res = XMALLOC(dfs_t);
 148
 149         res->graph_impl = graph_impl;
 150         res->graph      = graph_self;
 151         res->nodes      = new_set(cmp_node, 64);
 152         res->edges      = new_set(cmp_edge, 128);
 153
 154         res->pre_num  = 0;
 155         res->post_num = 0;
 156         res->edges_classified = 0;
 157
 158         obstack_init(&res->obst);
 159
 160         dfs_perform(res, graph_impl->get_root(graph_self), NULL, 0);
 161
 162         /* make sure the end node (which might not be accessible) has a number */
 163         dfs_node_t *const node = get_node(res, graph_impl->get_end(graph_self));
 164         if (!node->visited) {
 165                 node->visited     = 1;
 166                 node->node        = graph_impl->get_end(graph_self);
 167                 node->ancestor    = NULL;
 168                 node->pre_num     = res->pre_num++;
 169                 node->post_num    = res->post_num++;
 170                 node->max_pre_num = node->pre_num;
 171                 node->level       = 0;
 172         }
 173
 174         classify_edges(res);
 175
 176         assert(res->pre_num == res->post_num);
 177         res->pre_order  = XMALLOCN(dfs_node_t*, res->pre_num);
 178         res->post_order = XMALLOCN(dfs_node_t*, res->post_num);
 179         foreach_set (res->nodes, dfs_node_t, node) {
 180                 assert(node->pre_num < res->pre_num);
 181                 assert(node->post_num < res->post_num);
 182
 183                 res->pre_order[node->pre_num] = node;
 184                 res->post_order[node->post_num] = node;
 185         }
 186
 187         stat_ev_dbl("dfs_n_blocks", res->pre_num);
 188
 189         return res;
 190 }
 191
 192 void dfs_free(dfs_t *dfs)
 193 {
 194         obstack_free(&dfs->obst, NULL);
 195         del_set(dfs->nodes);
 196         del_set(dfs->edges);
 197         xfree(dfs->pre_order);
 198         xfree(dfs->post_order);
 199         xfree(dfs);
 200 }
 201
 202 static void dfs_dump_edge(const dfs_edge_t *edge, FILE *file)
 203 {
 204         dfs_node_t *src = edge->s;
 205         dfs_node_t *tgt = edge->t;
 206         const char *s, *style;
 207         int weight;
 208
 209 #define XXX(e)   case DFS_EDGE_ ## e: s = #e; break
 210         switch (edge->kind) {
 211                 XXX(FWD);
 212                 XXX(CROSS);
 213                 default:
 214                 s = "";
 215         }
 216 #undef XXX
 217
 218         weight = edge->kind == DFS_EDGE_BACK ? 1 : 1000;
 219         style  = edge->kind == DFS_EDGE_BACK ? "dashed" : "solid";
 220
 221         ir_fprintf(file, "\tn%d -> n%d [label=\"%s\",style=\"%s\",weight=\"%d\"];\n", src->pre_num, tgt->pre_num, s, style, weight);
 222 }
 223
 224 static int node_level_cmp(const void *a, const void *b)
 225 {
 226         const dfs_node_t *p = *(const dfs_node_t **) a;
 227         const dfs_node_t *q = *(const dfs_node_t **) b;
 228
 229         if (p->level == q->level)
 230                 return p->pre_num - q->pre_num;
 231         return p->level - q->level;
 232 }
 233
 234 void dfs_dump(const dfs_t *dfs, FILE *file)
 235 {
 236         dfs_node_t **nodes = XMALLOCN(dfs_node_t*, dfs->pre_num);
 237         int i, n = 0;
 238
 239         ir_fprintf(file, "digraph G {\nranksep=0.5\n");
 240         foreach_set (dfs->nodes, dfs_node_t, node) {
 241                 nodes[n++] = node;
 242         }
 243
 244         qsort(nodes, n, sizeof(nodes[0]), node_level_cmp);
 245
 246         i = 0;
 247         while (i < n) {
 248                 int level = nodes[i]->level;
 249
 250                 ir_fprintf(file, "\t{ rank = same; ");
 251                 for (; i < n && nodes[i]->level == level; ++i)
 252                         ir_fprintf(file, "n%d;", nodes[i]->pre_num);
 253                 ir_fprintf(file, "}\n");
 254
 255
 256         }
 257
 258         for (i = 0; i < n; ++i) {
 259                 dfs_node_t *const node = nodes[i];
 260                 ir_fprintf(file, "\tn%d [label=\"%d\"]\n", node->pre_num, get_Block_dom_tree_pre_num((ir_node*) node->node));
 261         }
 262
 263         foreach_set (dfs->edges, dfs_edge_t, edge)
 264                 dfs_dump_edge(edge, file);
 265
 266         ir_fprintf(file, "}\n");
 267         xfree(nodes);
 268 }