2.9BSD - /usr/src/cmd/struct/2.tree.c

   1: #include <stdio.h>
   2: #
   3: /* use inarc, dom, and head to build tree representing structure of program.
   4: 	Each node v has CHILDNUM(v) children denoted by
   5: 	LCHILD(v,0), LCHILD(v,1),...
   6: 	RSIB((v) is right sibling of v or UNDEFINED;
   7: 	RSIB(v) represents code following v at the same level of nesting,
   8: 	while LCHILD(v,i) represents code nested within v
   9: */
  10: #include "def.h"
  11: #include "2.def.h"
  12: 
  13: gettree(inarc,dom,head)     /* build tree */
  14: struct list **inarc;
  15: VERT *dom, *head;
  16:     {
  17:     VERT v,u,from;
  18:     int i;
  19:     for ( v = 0; v < nodenum; ++v)
  20:         {
  21:         RSIB(v) = UNDEFINED;
  22:         for (i = 0; i < CHILDNUM(v); ++i)
  23:             LCHILD(v,i) = UNDEFINED;
  24:         }
  25:     for (i = accessnum-1; i > 0; --i)
  26:         {
  27:         v = after[i];
  28:         from = oneelt(inarc[v]);    /* the unique elt of inarc[v] or UNDEFINED */
  29:         if (DEFINED(from))
  30:             if (NTYPE(from) == IFVX && (head[v] == head[from] || asoc(v,exitsize) != -1) )
  31:                 /* place in clause of IFVX if in smallest loop containing it
  32: 				or if size of code for v is <= exitsize */
  33:                 if (ARC(from,THEN) == v)
  34:                     {
  35:                     LCHILD(from,THEN) = v;
  36:                     continue;
  37:                     }
  38:                 else
  39:                     {
  40:                     ASSERT(ARC(from,ELSE) == v,gettree);
  41:                     LCHILD(from,ELSE) = v;
  42:                     continue;
  43:                     }
  44:             else if (NTYPE(v) == ITERVX || NTYPE(from) == ITERVX )
  45:                 /* LOOPVX -> ITERVX ->vert always in same loop*/
  46:                 {
  47:                 LCHILD(from,0) = v;
  48:                 continue;
  49:                 }
  50:             else if (NTYPE(from) == SWCHVX)
  51:                 {
  52:                 ASSERT(0 < ARCNUM(v),gettree);
  53:                 if (ARC(from,0) == v)
  54:                     LCHILD(from,0) = v;
  55:                 else
  56:                     {
  57:                     int j;
  58:                     for (j = 1; j < ARCNUM(from); ++j)
  59:                         if (ARC(from,j) == v)
  60:                             {insib(ARC(from,j-1),v);
  61:                             break;
  62:                             }
  63:                     }
  64:                 continue;
  65:                 }
  66:             else if (NTYPE(from) == ICASVX && (head[v] == head[from] || asoc(v,exitsize) != -1))
  67:                 {
  68:                 LCHILD(from,0) = v;
  69:                 continue;
  70:                 }
  71:             else if (NTYPE(from) == DUMVX && ARC(from,0) == v)
  72:                 {
  73:                 LCHILD(from,0) = v;
  74:                 continue;
  75:                 }
  76:         if (loomem(v,head[dom[v]],head))
  77:                 /* v is in smallest loop containing dom[v] */
  78:             insib(dom[v],v);
  79:         else
  80:             {
  81:                 /* make v follow LOOPVX heading largest loop
  82: 					containing DOM[v] but not v */
  83:             ASSERT(DEFINED(head[dom[v]]),gettree);
  84:             for (u = head[dom[v]]; head[u] != head[v]; u = head[u])
  85:                 ASSERT(DEFINED(head[u]),gettree);
  86:             ASSERT(NTYPE(u) == ITERVX,gettree);
  87:             insib(FATH(u),v);
  88:             }
  89:         }
  90:     }
  91: 
  92: 
  93: 
  94: 
  95: insib(w,v)      /* make RSIB(w) = v, and make RSIB(rightmost sib of v) = old RSIB(w) */
  96: VERT w,v;
  97:     {
  98:     VERT u, temp;
  99:     temp = RSIB(w);
 100:     RSIB(w) = v;
 101:     for (u = v; DEFINED(RSIB(u)); u = RSIB(u))
 102:         ;
 103:     RSIB(u) = temp;
 104:     }
 105: 
 106: 
 107: asoc(v,n)       /* return # of nodes associated with v if <= n, -1 otherwise */
 108: VERT v;
 109: int n;
 110:     {
 111:     int count,i,temp;
 112:     VERT w;
 113:     count = (NTYPE(v) == STLNVX) ? CODELINES(v) : 1;
 114:     for (i = 0; i < CHILDNUM(v); ++i)
 115:         {
 116:         w = LCHILD(v,i);
 117:         if (!DEFINED(w)) continue;
 118:         temp = asoc(w,n-count);
 119:         if (temp == -1) return(-1);
 120:         count += temp;
 121:         if (count > n) return(-1);
 122:         }
 123:     if (DEFINED(RSIB(v)))
 124:         {
 125:         temp = asoc(RSIB(v),n-count);
 126:         if (temp == -1) return(-1);
 127:         count += temp;
 128:         }
 129:     if (count > n) return(-1);
 130:     else return(count);
 131:     }

Defined functions