util/ego/cf/cf_idom.c

   1 /* $Id: cf_idom.c,v 1.4 1994/06/24 10:20:17 ceriel Exp $ */
   2 /*
   3  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   4  * See the copyright notice in the ACK home directory, in the file "Copyright".
   5  */
   6 /*  C O N T R O L   F L O W
   7  *
   8  *  C F _ I D O M . C
   9  */
  10
  11
  12 #include "../share/types.h"
  13 #include "../share/debug.h"
  14 #include "../share/lset.h"
  15 #include "../share/alloc.h"
  16 #include "cf.h"
  17
  18
  19 /* The algorithm for finding dominators in a flowgraph
  20  * that is used here, was developed by Thomas Lengauer
  21  * and Robert E. Tarjan of Stanford University.
  22  * The algorithm is described in their article:
  23  *          A Fast Algorithm for Finding Dominators
  24  *          in a Flowgraph
  25  *  which was published in:
  26  *         ACM Transactions on Programming Languages and Systems,
  27  *         Vol. 1, No. 1, July 1979, Pages 121-141.
  28  */
  29
  30
  31 #define UNREACHABLE(b) (b->B_SEMI == (short) 0)
  32
  33 short   dfs_nr;
  34 bblock_p *vertex;  /* dynamically allocated array */
  35
  36
  37 STATIC dfs(v)
  38         bblock_p v;
  39 {
  40         /* Depth First Search */
  41
  42         Lindex i;
  43         bblock_p w;
  44
  45         v->B_SEMI = ++dfs_nr;
  46         vertex[dfs_nr] = v->B_LABEL = v;
  47         v->B_ANCESTOR = (bblock_p) 0;
  48         for (i = Lfirst(v->b_succ); i != (Lindex) 0; i = Lnext(i,v->b_succ)) {
  49                 w = (bblock_p) Lelem(i);
  50                 if (w->B_SEMI == 0) {
  51                         w->B_PARENT = v;
  52                         dfs(w);
  53                 }
  54         }
  55 }
  56
  57
  58
  59 STATIC compress(v)
  60         bblock_p v;
  61 {
  62         if (v->B_ANCESTOR->B_ANCESTOR != (bblock_p) 0) {
  63                 compress(v->B_ANCESTOR);
  64                 if (v->B_ANCESTOR->B_LABEL->B_SEMI < v->B_LABEL->B_SEMI) {
  65                         v->B_LABEL = v->B_ANCESTOR->B_LABEL;
  66                 }
  67                 v->B_ANCESTOR = v->B_ANCESTOR->B_ANCESTOR;
  68         }
  69 }
  70
  71
  72
  73 STATIC bblock_p eval(v)
  74         bblock_p v;
  75 {
  76         if (v->B_ANCESTOR == (bblock_p) 0) {
  77                 return v;
  78         } else {
  79                 compress(v);
  80                 return v->B_LABEL;
  81         }
  82 }
  83
  84
  85
  86 STATIC linkblocks(v,w)
  87         bblock_p v,w;
  88 {
  89         w->B_ANCESTOR = v;
  90 }
  91
  92
  93
  94 dominators(r,n)
  95         bblock_p r;
  96         short n;
  97 {
  98         /* Compute the immediate dominator of every basic
  99          * block in the control flow graph rooted by r.
 100          */
 101
 102         register short i;
 103         Lindex ind, next;
 104         bblock_p v,w,u;
 105
 106         dfs_nr = 0;
 107         vertex = (bblock_p *) newmap(n);
 108         /* allocate vertex (dynamic array). All remaining
 109          * initializations were done by the routine
 110          * nextblock of get.c.
 111          */
 112         dfs(r);
 113         for (i = dfs_nr; i > 1; i--) {
 114                 w = vertex[i];
 115                 for (ind = Lfirst(w->b_pred); ind != (Lindex) 0;
 116                                                 ind = Lnext(ind,w->b_pred)) {
 117                         v = (bblock_p) Lelem(ind);
 118                         if (UNREACHABLE(v)) continue;
 119                         u = eval(v);
 120                         if (u->B_SEMI < w->B_SEMI) {
 121                                 w->B_SEMI = u->B_SEMI;
 122                         }
 123                 }
 124                 Ladd(w,&(vertex[w->B_SEMI]->B_BUCKET));
 125                 linkblocks(w->B_PARENT,w);
 126                 for (ind = Lfirst(w->B_PARENT->B_BUCKET); ind != (Lindex) 0;
 127                                                            ind = next) {
 128                         next = Lnext(ind,w->B_PARENT->B_BUCKET);
 129                         v = (bblock_p) Lelem(ind);
 130                         Lremove(v,&w->B_PARENT->B_BUCKET);
 131                         u = eval(v);
 132                         v->b_idom = (u->B_SEMI < v->B_SEMI ? u : w->B_PARENT);
 133                 }
 134         }
 135         for (i = 2; i <= dfs_nr; i++) {
 136                 w = vertex[i];
 137                 if (w->b_idom != vertex[w->B_SEMI]) {
 138                         w->b_idom = w->b_idom->b_idom;
 139                 }
 140         }
 141         r->b_idom = (bblock_p) 0;
 142         oldmap(vertex,n);   /* release memory for dynamic array vertex */
 143 }