Return to 2.dom.c CVS log

Up to [CSRG BSD Unix] / 43BSDTahoe / usr.bin / struct

Annotation of 43BSDTahoe/usr.bin/struct/2.dom.c, revision 1.1.1.1

1.1       root        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:        }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.