Return to 2.dom.c CVS log

Up to [CSRG BSD Unix] / 3BSD / cmd / struct

Annotation of 3BSD/cmd/struct/2.dom.c, revision 1.1

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

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