4.3BSD - /usr/src/usr.bin/struct/2.dom.c

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

Defined functions

Defined variables