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

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.