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

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