2.9BSD - /usr/src/cmd/struct/2.dom.c

   1: #include <stdio.h>
   2: #
   3: /*
   4: set dom[v] to immediate dominator of v, based on arcs as stored in inarcs
   5: (i.e. pretending the graph is reducible if it isn't).
   6: Algorithm is from Hecht and Ullman, Analysis of a simple algorithm for global
   7: flow analysis problems, except bit vector operations replaced by search
   8: through DOM to save quadratic blowup in space
   9: */
  10: #include "def.h"
  11: #include "2.def.h"
  12: 
  13: 
  14: getdom(inarc,dom)
  15: struct list **inarc;
  16: VERT *dom;
  17:     {
  18:     VERT v;
  19:     int i;
  20:     struct list *ls;
  21:     for (v = 0; v < nodenum; ++v)
  22:         dom[v] = UNDEFINED;
  23:     for (i = 1; i < accessnum; ++i)
  24:         {
  25:         v = after[i];
  26:         for (ls = inarc[v]; ls; ls = ls->nxtlist)
  27:             {
  28:             ASSERT(ntoaft[ls->elt] < i,getdom);
  29:             dom[v] = comdom(dom[v],ls->elt,dom);
  30:             }
  31: 
  32:         }
  33:     }
  34: 
  35: 
  36: comdom(u,v,dom)         /* find closest common dominator of u,v */
  37: VERT u,v, *dom;
  38:     {
  39:     if (u == UNDEFINED) return(v);
  40:     if (v == UNDEFINED) return(u);
  41:     while(u != v)
  42:         {
  43:         ASSERT(u != UNDEFINED && v != UNDEFINED, comdom);
  44:         if (ntoaft[u] < ntoaft[v])
  45:             v = dom[v];
  46:         else
  47:             u = dom[u];
  48:         }
  49:     return(u);
  50:     }

Defined functions