home *** CD-ROM | disk | FTP | other *** search
/ minnie.tuhs.org / unixen.tar / unixen / PDP-11 / Trees / V7 / usr / src / cmd / struct / 2.dom.c < prev    next >
Encoding:
C/C++ Source or Header  |  1979-01-10  |  1.0 KB  |  51 lines
  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.     }
  51.