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 <stdlib.h>
  34
  35 #include <assert.h>
  36 #include "irtools.h"
  37 #include "irprintf.h"
  38 #include "irdom.h"
  39 #include "set.h"
  40 #include "statev.h"
  41 #include "dfs_t.h"
  42
  43 static const char *edge_names[] = {
  44         "anc",
  45         "fwd",
  46         "cross",
  47         "back"
  48 };
  49
  50 static int cmp_edge(const void *a, const void *b, size_t sz)
  51 {
  52         const dfs_edge_t *p = a;
  53         const dfs_edge_t *q = b;
  54         (void) sz;
  55
  56         return !(p->src == q->src && p->tgt == q->tgt);
  57 }
  58
  59 static int cmp_node(const void *a, const void *b, size_t sz)
  60 {
  61         const dfs_node_t *p = a;
  62         const dfs_node_t *q = b;
  63         (void) sz;
  64
  65         return p->node != q->node;
  66 }
  67
  68 #define get_node(dfs, node) _dfs_get_node(dfs, node)
  69
  70 static dfs_edge_t *get_edge(const dfs_t *self, const void *src, const void *tgt)
  71 {
  72         unsigned hash = HASH_COMBINE(HASH_PTR(src), HASH_PTR(tgt));
  73         dfs_edge_t templ;
  74
  75         templ.src = src;
  76         templ.tgt = tgt;
  77         templ.kind = -1;
  78
  79         return set_insert(self->edges, &templ, sizeof(templ), hash);
  80 }
  81
  82 static void dfs_perform(dfs_t *dfs, void *n, void *anc, int level)
  83 {
  84         dfs_node_t *node = get_node(dfs, n);
  85         void **succs, **iter;
  86
  87         assert(node->visited == 0);
  88
  89         node->visited     = 1;
  90         node->node        = n;
  91         node->ancestor    = anc;
  92         node->pre_num     = dfs->pre_num++;
  93         node->max_pre_num = node->pre_num;
  94         node->level       = level;
  95
  96         dfs->graph_impl->grow_succs(dfs->graph, n, &dfs->obst);
  97         obstack_ptr_grow(&dfs->obst, NULL);
  98         succs = obstack_finish(&dfs->obst);
  99
 100         for (iter = succs; *iter; ++iter) {
 101                 void *p = *iter;
 102
 103                 /* get the node */
 104                 dfs_node_t *child = get_node(dfs, p);
 105
 106                 /* create the edge object */
 107                 dfs_edge_t *edge = get_edge(dfs, n, p);
 108                 edge->s = node;
 109                 edge->t = child;
 110
 111                 if (!child->visited)
 112                         dfs_perform(dfs, p, node, level + 1);
 113
 114                 /* get the maximum pre num of the subtree. needed for ancestor determination. */
 115                 node->max_pre_num = MAX(node->max_pre_num, child->max_pre_num);
 116         }
 117
 118         node->post_num = dfs->post_num++;
 119         obstack_free(&dfs->obst, succs);
 120 }
 121
 122 static void classify_edges(dfs_t *dfs)
 123 {
 124         stat_ev_cnt_decl(anc);
 125         stat_ev_cnt_decl(back);
 126         stat_ev_cnt_decl(fwd);
 127         stat_ev_cnt_decl(cross);
 128         dfs_edge_t *edge;
 129
 130         foreach_set (dfs->edges, edge) {
 131                 dfs_node_t *src = edge->s;
 132                 dfs_node_t *tgt = edge->t;
 133
 134                 if (tgt->ancestor == src) {
 135                         stat_ev_cnt_inc(anc);
 136                         edge->kind = DFS_EDGE_ANC;
 137                 }
 138                 else if (_dfs_int_is_ancestor(tgt, src)) {
 139                         stat_ev_cnt_inc(back);
 140                         edge->kind = DFS_EDGE_BACK;
 141                 }
 142                 else if (_dfs_int_is_ancestor(src, tgt)) {
 143                         stat_ev_cnt_inc(fwd);
 144                         edge->kind = DFS_EDGE_FWD;
 145                 }
 146                 else {
 147                         stat_ev_cnt_inc(cross);
 148                         edge->kind = DFS_EDGE_CROSS;
 149                 }
 150         }
 151
 152         stat_ev_cnt_done(anc,   "dfs_edge_anc");
 153         stat_ev_cnt_done(back,  "dfs_edge_back");
 154         stat_ev_cnt_done(fwd,   "dfs_edge_fwd");
 155         stat_ev_cnt_done(cross, "dfs_edge_cross");
 156 }
 157
 158 dfs_edge_kind_t dfs_get_edge_kind(const dfs_t *dfs, const void *a, const void *b)
 159 {
 160         if (!dfs->edges_classified) {
 161                 dfs_t *urg = (dfs_t *) dfs;
 162                 classify_edges(urg);
 163                 urg->edges_classified = 1;
 164         }
 165         return get_edge(dfs, a, b)->kind;
 166 }
 167
 168 dfs_t *dfs_new(const absgraph_t *graph_impl, void *graph_self)
 169 {
 170         dfs_t *res = xmalloc(sizeof(res[0]));
 171         dfs_node_t *node;
 172
 173         res->graph_impl = graph_impl;
 174         res->graph      = graph_self;
 175         res->nodes      = new_set(cmp_node, 64);
 176         res->edges      = new_set(cmp_edge, 128);
 177
 178         res->pre_num  = 0;
 179         res->post_num = 0;
 180         res->edges_classified = 0;
 181
 182         obstack_init(&res->obst);
 183
 184         dfs_perform(res, graph_impl->get_root(graph_self), NULL, 0);
 185         classify_edges(res);
 186
 187         res->pre_order = xmalloc(res->pre_num * sizeof(res->pre_order));
 188         res->post_order = xmalloc(res->pre_num * sizeof(res->post_order));
 189         foreach_set (res->nodes, node) {
 190                 res->pre_order[node->pre_num] = node;
 191                 res->post_order[node->post_num] = node;
 192         }
 193
 194         stat_ev_dbl("dfs_n_blocks", res->pre_num);
 195
 196         return res;
 197 }
 198
 199 void dfs_free(dfs_t *dfs)
 200 {
 201         del_set(dfs->nodes);
 202         del_set(dfs->edges);
 203         xfree(dfs->pre_order);
 204         xfree(dfs->post_order);
 205         xfree(dfs);
 206 }
 207
 208 static void dfs_dump_edge(const dfs_edge_t *edge, FILE *file)
 209 {
 210         dfs_node_t *src = edge->s;
 211         dfs_node_t *tgt = edge->t;
 212         const char *s, *style;
 213         int weight;
 214
 215 #define XXX(e)          case DFS_EDGE_ ## e: s = #e; break
 216         switch (edge->kind) {
 217                 XXX(FWD);
 218                 XXX(CROSS);
 219                 default:
 220                 s = "";
 221         }
 222 #undef XXX
 223
 224         weight = edge->kind == DFS_EDGE_BACK ? 1 : 1000;
 225         style  = edge->kind == DFS_EDGE_BACK ? "dashed" : "solid";
 226
 227         ir_fprintf(file, "\tn%d -> n%d [label=\"%s\",style=\"%s\",weight=\"%d\"];\n", src->pre_num, tgt->pre_num, s, style, weight);
 228 }
 229
 230 static int node_level_cmp(const void *a, const void *b)
 231 {
 232         const dfs_node_t *p = *(const dfs_node_t **) a;
 233         const dfs_node_t *q = *(const dfs_node_t **) b;
 234
 235         if (p->level == q->level)
 236                 return p->pre_num - q->pre_num;
 237         return p->level - q->level;
 238 }
 239
 240 void dfs_dump(const dfs_t *dfs, FILE *file)
 241 {
 242         dfs_node_t **nodes = xmalloc(dfs->pre_num * sizeof(nodes[0]));
 243         dfs_node_t *node;
 244         dfs_edge_t *edge;
 245         int i, n = 0;
 246
 247         ir_fprintf(file, "digraph G {\nranksep=0.5\n");
 248         foreach_set (dfs->nodes, node) {
 249                 nodes[n++] = node;
 250         }
 251
 252         qsort(nodes, n, sizeof(nodes[0]), node_level_cmp);
 253
 254         i = 0;
 255         while (i < n) {
 256                 int level = nodes[i]->level;
 257
 258                 ir_fprintf(file, "\t{ rank = same; ");
 259                 for (; i < n && nodes[i]->level == level; ++i)
 260                         ir_fprintf(file, "n%d;", nodes[i]->pre_num);
 261                 ir_fprintf(file, "}\n");
 262
 263
 264         }
 265
 266         for (i = 0; i < n; ++i) {
 267                 dfs_node_t *node = nodes[i];
 268                 ir_fprintf(file, "\tn%d [label=\"%d\"]\n", node->pre_num, get_Block_dom_tree_pre_num(node->node));
 269 #if 0
 270                 ir_fprintf(file, "\tn%d [shape=box,label=\"%+F\\l%d %d/%d %d\"];\n",
 271                                 node->pre_num, node->node, get_Block_dom_tree_pre_num(node->node),
 272                                 node->pre_num, node->post_num, node->max_pre_num);
 273 #endif
 274         }
 275
 276         foreach_set (dfs->edges, edge)
 277                 dfs_dump_edge(edge, file);
 278
 279         ir_fprintf(file, "}\n");
 280         xfree(nodes);
 281 }