Return to 2.dom.c CVS log

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

Annotation of 43BSD/usr.bin/struct/2.dom.c, revision 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.