home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / dosdisas.zip / dccsrcoo.zip / control.cpp < prev    next >
C/C++ Source or Header  |  1997-04-09  |  22KB  |  755 lines
  1. /*********************************************************************
  2.  *$Log:    control.c,v $
  3.  * Revision 2.8  94/03/14  08:46:56  cifuente
  4.  * #ifdef MSDOS to include alloc.h
  5.  * 
  6.  * Revision 2.7  94/03/11  16:20:45  cifuente
  7.  * Fixed bug in compound conditions.
  8.  * 
  9.  * Revision 2.6  94/02/22  15:13:51  cifuente
  10.  * Modified if..then..else structuring algorithm (now it works).
  11.  * Doesn't flag nodes that require a label (this is left for the
  12.  * code generator to decide).
  13.  * 
  14.  * Revision 2.5  93/10/01  08:58:13  cifuente
  15.  * boolT type - for compilation under unix SVR4.2
  16.  * 
  17.  * Revision 2.4  93/09/20  11:49:31  cifuente
  18.  * Changed tabs to spaces
  19.  * 
  20.  * Revision 2.3  93/08/23  12:14:51  cifuente
  21.  * Interactive mode with curses
  22.  *
  23.  * Revision 2.1  93/03/30  14:50:03  cifuente
  24.  * Compiled with gcc.
  25.  *
  26.  * Revision 1.1  92/10/09  14:18:26  lederman
  27.  * Initial revision
  28.  *
  29.   Description   : Performs control flow analysis on the CFG
  30.  ********************************************************************/
  31.  
  32. #include "dcc.h"
  33. #include <stdio.h>
  34. #include <string.h>
  35. #if __BORLAND__
  36. #include <alloc.h>
  37. #else
  38. #include <malloc.h>
  39. #endif
  40.  
  41. typedef struct list {
  42.     Int         nodeIdx;    /* dfsLast index to the node */
  43.     struct list *next;
  44. } nodeList;
  45.  
  46.  
  47. #define ancestor(a,b)    ((a->dfsLastNum < b->dfsLastNum) && (a->dfsFirstNum < b->dfsFirstNum))
  48. /* there is a path on the DFST from a to b if the a was first visited in a 
  49.  * dfs, and a was later visited than b when doing the last visit of each 
  50.  * node. */
  51.  
  52.  
  53. static boolT isBackEdge (PBB p,PBB s)
  54. /* Checks if the edge (p,s) is a back edge.  If node s was visited first 
  55.  * during the dfs traversal (ie. s has a smaller dfsFirst number) or s == p,
  56.  * then it is a backedge. 
  57.  * Also incrementes the number of backedges entries to the header node. */
  58. {
  59.     if (p->dfsFirstNum >= s->dfsFirstNum)
  60.     {
  61.         s->numBackEdges++;
  62.         return (TRUE);
  63.     }
  64.     return (FALSE);
  65. }
  66.  
  67.  
  68. static Int commonDom (Int currImmDom, Int predImmDom, PPROC pProc)
  69. /* Finds the common dominator of the current immediate dominator
  70.  * currImmDom and its predecessor's immediate dominator predImmDom  */ 
  71. {
  72.     if (currImmDom == NO_DOM)
  73.        return (predImmDom);
  74.     if (predImmDom == NO_DOM)   /* predecessor is the root */
  75.        return (currImmDom);
  76.  
  77.     while ((currImmDom != NO_DOM) && (predImmDom != NO_DOM) &&
  78.            (currImmDom != predImmDom))
  79.     {
  80.        if (currImmDom < predImmDom)
  81.           predImmDom = pProc->dfsLast[predImmDom]->immedDom;
  82.        else
  83.           currImmDom = pProc->dfsLast[currImmDom]->immedDom;
  84.     }
  85.     return (currImmDom);
  86. }
  87.  
  88.  
  89. static void findImmedDom (PPROC pProc)
  90. /* Finds the immediate dominator of each node in the graph pProc->cfg. 
  91.  * Adapted version of the dominators algorithm by Hecht and Ullman; finds
  92.  * immediate dominators only.  
  93.  * Note: graph should be reducible */
  94. { PBB currNode;
  95.   Int currIdx, j, predIdx;
  96.  
  97.     for (currIdx = 0; currIdx < pProc->numBBs; currIdx++) 
  98.     {
  99.         currNode = pProc->dfsLast[currIdx]; 
  100.         if (currNode->flg & INVALID_BB)        /* Do not process invalid BBs */
  101.             continue;
  102.  
  103.         for (j = 0; j < currNode->numInEdges; j++)
  104.         {
  105.             predIdx = currNode->inEdges[j]->dfsLastNum;
  106.             if (predIdx < currIdx)
  107.                 currNode->immedDom = commonDom (currNode->immedDom, 
  108.                                                 predIdx, pProc);
  109.         }
  110.     }
  111. }
  112.  
  113.  
  114. static void insertList (nodeList **l, Int n)
  115. /* Inserts the node n to the list l. */
  116. {
  117.     nodeList *newNode;
  118.  
  119.     newNode = allocStruc(nodeList);
  120.     memset(newNode, 0, sizeof(nodeList));
  121.     newNode->nodeIdx = n;
  122.     newNode->next = *l;
  123.     *l = newNode;
  124. }
  125.  
  126.  
  127. static boolT inList (nodeList *l, Int n)
  128. /* Returns whether or not the node n (dfsLast numbering of a basic block) 
  129.  * is on the list l. */
  130. {
  131.     while (l)
  132.       if (l->nodeIdx == n)
  133.          return (TRUE);
  134.       else
  135.          l = l->next;
  136.     return (FALSE);
  137. }
  138.  
  139.  
  140. static void freeList (nodeList **l)
  141. /* Frees space allocated by the list l.  */
  142. { nodeList *next;
  143.  
  144.     if (*l)
  145.     {
  146.        next = (*l)->next;
  147.        free (*l);
  148.        *l = next;
  149.     }
  150.     *l = NULL;
  151. }
  152.  
  153.  
  154. static boolT inInt(PBB n, queue *q) 
  155. /* Returns whether the node n belongs to the queue list q. */ 
  156. { 
  157.     while (q)
  158.       if (q->node == n)
  159.          return (TRUE);
  160.       else
  161.          q = q->next;
  162.     return (FALSE);
  163. }
  164.  
  165.  
  166. static void findEndlessFollow (PPROC pProc, nodeList *loopNodes, PBB head)
  167. /* Finds the follow of the endless loop headed at node head (if any).
  168.  * The follow node is the closest node to the loop. */
  169. { nodeList *p;
  170.   Int j, succ;
  171.  
  172.     head->loopFollow = MAX;
  173.     p = loopNodes;
  174.     while (p != NULL)
  175.     {
  176.         for (j = 0; j < pProc->dfsLast[p->nodeIdx]->numOutEdges; j++)
  177.         {
  178.             succ = pProc->dfsLast[p->nodeIdx]->edges[j].BBptr->dfsLastNum; 
  179.             if ((! inList(loopNodes, succ)) && (succ < head->loopFollow))
  180.                 head->loopFollow = succ;
  181.         }
  182.         p = p->next;
  183.     }
  184. }
  185.  
  186.  
  187. static void findNodesInLoop(PBB latchNode,PBB head,PPROC pProc,queue *intNodes) 
  188. /* Flags nodes that belong to the loop determined by (latchNode, head) and 
  189.  * determines the type of loop.                     */
  190. { Int i, headDfsNum, intNodeType, j;
  191.   nodeList *loopNodes = NULL, p;
  192.   Int immedDom,             /* dfsLast index to immediate dominator */
  193.       thenDfs, elseDfs;        /* dsfLast index for THEN and ELSE nodes */
  194.   PBB pbb;
  195.  
  196.     /* Flag nodes in loop headed by head (except header node) */
  197.     headDfsNum = head->dfsLastNum;
  198.     head->loopHead = headDfsNum;
  199.     insertList (&loopNodes, headDfsNum);
  200.     for (i = headDfsNum + 1; i < latchNode->dfsLastNum; i++)
  201.     {
  202.         if (pProc->dfsLast[i]->flg & INVALID_BB)    /* skip invalid BBs */
  203.             continue;
  204.  
  205.         immedDom = pProc->dfsLast[i]->immedDom;
  206.         if (inList (loopNodes, immedDom) && inInt(pProc->dfsLast[i], intNodes))
  207.         {
  208.                insertList (&loopNodes, i);
  209.                if (pProc->dfsLast[i]->loopHead == NO_NODE)/*not in other loop*/
  210.                     pProc->dfsLast[i]->loopHead = headDfsNum;
  211.         }
  212.     }
  213.     latchNode->loopHead = headDfsNum;
  214.     if (latchNode != head)
  215.         insertList (&loopNodes, latchNode->dfsLastNum);
  216.  
  217.     /* Determine type of loop and follow node */
  218.     intNodeType = head->nodeType;
  219.     if (latchNode->nodeType == TWO_BRANCH)
  220.        if ((intNodeType == TWO_BRANCH) || (latchNode == head))
  221.           if ((latchNode == head) ||
  222.               (inList (loopNodes, head->edges[THEN].BBptr->dfsLastNum) &&
  223.                   inList (loopNodes, head->edges[ELSE].BBptr->dfsLastNum)))
  224.           {
  225.             head->loopType = REPEAT_TYPE;
  226.             if (latchNode->edges[0].BBptr == head)
  227.                head->loopFollow = latchNode->edges[ELSE].BBptr->dfsLastNum;
  228.             else
  229.                head->loopFollow = latchNode->edges[THEN].BBptr->dfsLastNum;
  230.             pProc->Icode.SetLlFlag(latchNode->start + latchNode->length - 1,
  231.                 JX_LOOP);
  232.           }
  233.           else
  234.           {
  235.              head->loopType = WHILE_TYPE;
  236.             if (inList (loopNodes, head->edges[THEN].BBptr->dfsLastNum))
  237.                 head->loopFollow = head->edges[ELSE].BBptr->dfsLastNum; 
  238.             else
  239.                 head->loopFollow = head->edges[THEN].BBptr->dfsLastNum; 
  240.             pProc->Icode.SetLlFlag(head->start + head->length - 1, JX_LOOP);
  241.           }
  242.        else /* head = anything besides 2-way, latch = 2-way */ 
  243.        {
  244.             head->loopType = REPEAT_TYPE;
  245.             if (latchNode->edges[THEN].BBptr == head)
  246.                 head->loopFollow = latchNode->edges[ELSE].BBptr->dfsLastNum;
  247.             else
  248.                 head->loopFollow = latchNode->edges[THEN].BBptr->dfsLastNum;
  249.             pProc->Icode.SetLlFlag(latchNode->start + latchNode->length - 1,
  250.                 JX_LOOP);
  251.        }
  252.     else    /* latch = 1-way */
  253.         if (latchNode->nodeType == LOOP_NODE)
  254.         {
  255.             head->loopType = REPEAT_TYPE; 
  256.             head->loopFollow = latchNode->edges[0].BBptr->dfsLastNum;
  257.         }
  258.         else if (intNodeType == TWO_BRANCH)
  259.         {
  260.             head->loopType = WHILE_TYPE;
  261.             pbb = latchNode; 
  262.             thenDfs = head->edges[THEN].BBptr->dfsLastNum;
  263.             elseDfs = head->edges[ELSE].BBptr->dfsLastNum;
  264.             while (1)
  265.             {
  266.                 if (pbb->dfsLastNum == thenDfs)
  267.                 {
  268.                     head->loopFollow = elseDfs;
  269.                     break;
  270.                 }
  271.                 else if (pbb->dfsLastNum == elseDfs)
  272.                 {
  273.                     head->loopFollow = thenDfs;
  274.                     break;
  275.                 }
  276.  
  277.                 /* Check if couldn't find it, then it is a strangely formed
  278.                  * loop, so it is safer to consider it an endless loop */
  279.                 if (pbb->dfsLastNum <= head->dfsLastNum)
  280.                 {
  281.                     head->loopType = ENDLESS_TYPE;
  282.                     findEndlessFollow (pProc, loopNodes, head);
  283.                     break;
  284.                 }
  285.                 pbb = pProc->dfsLast[pbb->immedDom];    
  286.             }
  287.             if (pbb->dfsLastNum > head->dfsLastNum)
  288.                 pProc->dfsLast[head->loopFollow]->loopHead = NO_NODE;    /*****/
  289.             pProc->Icode.SetLlFlag(head->start + head->length - 1, JX_LOOP);
  290.         }
  291.         else
  292.         {
  293.             head->loopType = ENDLESS_TYPE;
  294.             findEndlessFollow (pProc, loopNodes, head);
  295.         }
  296.  
  297.     freeList(&loopNodes);
  298. }
  299.  
  300.  
  301. static void findNodesInInt (queue **intNodes, Int level, interval *Ii)
  302. /* Recursive procedure to find nodes that belong to the interval (ie. nodes 
  303.  * from G1).                                */
  304. { queue *l;
  305.  
  306.     if (level == 1)
  307.        for (l = Ii->nodes; l; l = l->next)
  308.           appendQueue (intNodes, l->node);
  309.     else
  310.        for (l = Ii->nodes; l; l= l->next)
  311.           findNodesInInt (intNodes, level - 1, l->node->correspInt);
  312. }
  313.  
  314.  
  315. static void structLoops(PPROC pProc, derSeq *derivedG)
  316. /* Algorithm for structuring loops */
  317. { interval *Ii;
  318.   PBB intHead,          /* interval header node             */
  319.       pred,             /* predecessor node                 */ 
  320.       latchNode;        /* latching node (in case of loops) */
  321.   Int i,                /* counter                          */ 
  322.       level = 0;        /* derived sequence level           */
  323.   interval *initInt;    /* initial interval                 */
  324.   queue *intNodes;      /* list of interval nodes           */
  325.  
  326.     /* Structure loops */
  327.     while (derivedG)    /* for all derived sequences Gi */
  328.     {
  329.        level++;
  330.        Ii = derivedG->Ii;
  331.        while (Ii)       /* for all intervals Ii of Gi */
  332.        {
  333.           latchNode = NULL;
  334.           intNodes  = NULL;
  335.  
  336.           /* Find interval head (original BB node in G1) and create
  337.            * list of nodes of interval Ii.              */
  338.           initInt = Ii;
  339.           for (i = 1; i < level; i++)
  340.               initInt = initInt->nodes->node->correspInt;
  341.           intHead = initInt->nodes->node;
  342.  
  343.           /* Find nodes that belong to the interval (nodes from G1) */
  344.           findNodesInInt (&intNodes, level, Ii);
  345.  
  346.           /* Find greatest enclosing back edge (if any) */
  347.           for (i = 0; i < intHead->numInEdges; i++)
  348.           {
  349.               pred = intHead->inEdges[i]; 
  350.               if (inInt(pred, intNodes) && isBackEdge(pred, intHead))
  351.                  if (! latchNode)
  352.                     latchNode = pred;
  353.                  else
  354.                  {
  355.                     if (pred->dfsLastNum > latchNode->dfsLastNum)
  356.                            latchNode = pred;
  357.                  }
  358.           }
  359.  
  360.           /* Find nodes in the loop and the type of loop */
  361.           if (latchNode)
  362.           { 
  363.              /* Check latching node is at the same nesting level of case
  364.                * statements (if any) and that the node doesn't belong to
  365.                * another loop.                   */
  366.              if ((latchNode->caseHead == intHead->caseHead) &&
  367.                  (latchNode->loopHead == NO_NODE)) 
  368.              {
  369.                 intHead->latchNode = latchNode->dfsLastNum;
  370.                 findNodesInLoop(latchNode, intHead, pProc, intNodes);
  371.                 latchNode->flg |= IS_LATCH_NODE;
  372.              }
  373.           }
  374.  
  375.           /* Next interval */
  376.           Ii = Ii->next;
  377.        }
  378.  
  379.        /* Next derived sequence */
  380.        derivedG = derivedG->next;
  381.     }
  382. }
  383.  
  384.  
  385. static boolT successor (Int s, Int h, PPROC pProc)
  386. /* Returns whether the BB indexed by s is a successor of the BB indexed by
  387.  * h.  Note that h is a case node.                  */
  388. { Int i;
  389.   PBB header;
  390.  
  391.     header = pProc->dfsLast[h];
  392.     for (i = 0; i < header->numOutEdges; i++)
  393.       if (header->edges[i].BBptr->dfsLastNum == s)
  394.          return (TRUE);
  395.     return (FALSE);
  396. }
  397.  
  398.  
  399. static void tagNodesInCase (PBB pBB, nodeList **l, Int head, Int tail)
  400. /* Recursive procedure to tag nodes that belong to the case described by
  401.  * the list l, head and tail (dfsLast index to first and exit node of the 
  402.  * case).                               */
  403. { Int current,      /* index to current node */
  404.       i;
  405.  
  406.     pBB->traversed = DFS_CASE;
  407.     current = pBB->dfsLastNum;
  408.     if ((current != tail) && (pBB->nodeType != MULTI_BRANCH) && 
  409.         (inList (*l, pBB->immedDom)))
  410.     {
  411.        insertList (l, current);
  412.        pBB->caseHead = head;
  413.        for (i = 0; i < pBB->numOutEdges; i++)
  414.           if (pBB->edges[i].BBptr->traversed != DFS_CASE)
  415.              tagNodesInCase (pBB->edges[i].BBptr, l, head, tail);
  416.     }
  417. }
  418.  
  419.  
  420. static void structCases(PPROC pProc)
  421. /* Structures case statements.  This procedure is invoked only when pProc
  422.  * has a case node.                         */
  423. { Int i, j;
  424.   PBB caseHeader;               /* case header node         */
  425.   Int exitNode = NO_NODE;       /* case exit node           */
  426.   nodeList *caseNodes = NULL;   /* temporary: list of nodes in case */
  427.  
  428.     /* Linear scan of the nodes in reverse dfsLast order, searching for
  429.      * case nodes                           */
  430.     for (i = pProc->numBBs - 1; i >= 0; i--)
  431.         if (pProc->dfsLast[i]->nodeType == MULTI_BRANCH)
  432.         {
  433.             caseHeader = pProc->dfsLast[i];
  434.  
  435.             /* Find descendant node which has as immediate predecessor 
  436.              * the current header node, and is not a successor.    */
  437.             for (j = i + 2; j < pProc->numBBs; j++)
  438.             {
  439.                 if ((!successor(j, i, pProc)) && 
  440.                                         (pProc->dfsLast[j]->immedDom == i))
  441.                     if (exitNode == NO_NODE)
  442.                           exitNode = j;
  443.                     else if (pProc->dfsLast[exitNode]->numInEdges <
  444.                              pProc->dfsLast[j]->numInEdges) 
  445.                           exitNode = j;
  446.              }
  447.             pProc->dfsLast[i]->caseTail = exitNode;
  448.          
  449.             /* Tag nodes that belong to the case by recording the
  450.              * header field with caseHeader.           */
  451.             insertList (&caseNodes, i); 
  452.             pProc->dfsLast[i]->caseHead = i;
  453.             for (j = 0; j < caseHeader->numOutEdges; j++)
  454.                 tagNodesInCase (caseHeader->edges[j].BBptr, &caseNodes, i,
  455.                                 exitNode);
  456.             if (exitNode != NO_NODE)
  457.                 pProc->dfsLast[exitNode]->caseHead = i;
  458.         }
  459. }
  460.  
  461.  
  462. static void flagNodes (nodeList **l, Int f, PPROC pProc)
  463. /* Flags all nodes in the list l as having follow node f, and deletes all
  464.  * nodes from the list.                         */
  465. {  nodeList *p;
  466.  
  467.     p = *l;
  468.     while (p)
  469.     {
  470.        pProc->dfsLast[p->nodeIdx]->ifFollow = f;
  471.        p = p->next;
  472.        free (*l);
  473.        *l = p;
  474.     }
  475.     *l = NULL;
  476. }
  477.  
  478.  
  479. static void structIfs (PPROC pProc)
  480. /* Structures if statements */
  481. {  Int curr,                    /* Index for linear scan of nodes       */
  482.        desc,                    /* Index for descendant                 */
  483.        followInEdges,            /* Largest # in-edges so far             */
  484.        follow;                  /* Possible follow node                 */
  485.    nodeList *domDesc = NULL,    /* List of nodes dominated by curr      */
  486.         *unresolved = NULL,     /* List of unresolved if nodes          */
  487.         *l;                     /* Temporary list                       */
  488.    PBB currNode,                /* Pointer to current node              */
  489.         pbb;
  490.  
  491.     /* Linear scan of nodes in reverse dfsLast order */
  492.     for (curr = pProc->numBBs - 1; curr >= 0; curr--)
  493.     {
  494.         currNode = pProc->dfsLast[curr];
  495.         if (currNode->flg & INVALID_BB)        /* Do not process invalid BBs */
  496.             continue;
  497.  
  498.         if ((currNode->nodeType == TWO_BRANCH) &&
  499.             (! (pProc->Icode.GetLlFlag(currNode->start + currNode->length - 1)
  500.                 & JX_LOOP)))
  501.         {
  502.             followInEdges = 0;
  503.             follow = 0;
  504.  
  505.             /* Find all nodes that have this node as immediate dominator */
  506.             for (desc = curr+1; desc < pProc->numBBs; desc++)
  507.             {
  508.                 if (pProc->dfsLast[desc]->immedDom == curr)  {
  509.                     insertList (&domDesc, desc);
  510.                     pbb = pProc->dfsLast[desc];
  511.                     if ((pbb->numInEdges - pbb->numBackEdges) >= followInEdges)
  512.                     {
  513.                         follow = desc;
  514.                         followInEdges = pbb->numInEdges - pbb->numBackEdges;
  515.                     }
  516.                 }
  517.             }
  518.  
  519.             /* Determine follow according to number of descendants
  520.              * immediately dominated by this node  */
  521.             if ((follow != 0) && (followInEdges > 1))
  522.             {
  523.                 currNode->ifFollow = follow;
  524.                 if (unresolved)
  525.                     flagNodes (&unresolved, follow, pProc);
  526.             }
  527.             else
  528.                 insertList (&unresolved, curr);
  529.         }
  530.         freeList (&domDesc);
  531.     }
  532. }
  533.  
  534.  
  535. void compoundCond (PPROC pproc)
  536. /* Checks for compound conditions of basic blocks that have only 1 high 
  537.  * level instruction.  Whenever these blocks are found, they are merged
  538.  * into one block with the appropriate condition */
  539. { Int i, j, k, numOutEdges;
  540.   PBB pbb, t, e, obb, pred;
  541.   PICODE picode, ticode;
  542.   COND_EXPR *exp;
  543.  TYPEADR_TYPE *edges;
  544.   boolT change;
  545.  
  546.   change = TRUE;
  547.   while (change)
  548.   {
  549.     change = FALSE;
  550.  
  551.     /* Traverse nodes in postorder, this way, the header node of a
  552.      * compound condition is analysed first */
  553.     for (i = 0; i < pproc->numBBs; i++)
  554.     {
  555.         pbb = pproc->dfsLast[i];
  556.         if (pbb->flg & INVALID_BB)
  557.             continue;
  558.  
  559.         if (pbb->nodeType == TWO_BRANCH)
  560.         {
  561.             t = pbb->edges[THEN].BBptr;
  562.             e = pbb->edges[ELSE].BBptr;
  563.  
  564.             /* Check (X || Y) case */
  565.             if ((t->nodeType == TWO_BRANCH) && (t->numHlIcodes == 1) && 
  566.                 (t->numInEdges == 1) && (t->edges[ELSE].BBptr == e)) 
  567.             {
  568.                 obb = t->edges[THEN].BBptr;
  569.  
  570.                 /* Construct compound DBL_OR expression */
  571.                 picode = pproc->Icode.GetIcode(pbb->start + pbb->length -1);
  572.                 ticode = pproc->Icode.GetIcode(t->start + t->length -1);
  573.                 exp = boolCondExp (picode->ic.hl.oper.exp,
  574.                                    ticode->ic.hl.oper.exp, DBL_OR);
  575.                 picode->ic.hl.oper.exp = exp;
  576.  
  577.                 /* Replace in-edge to obb from t to pbb */
  578.                 for (j = 0; j < obb->numInEdges; j++)
  579.                     if (obb->inEdges[j] == t)
  580.                     {
  581.                         obb->inEdges[j] = pbb;
  582.                         break;
  583.                     }
  584.  
  585.                 /* New THEN out-edge of pbb */
  586.                 pbb->edges[THEN].BBptr = obb;
  587.  
  588.                 /* Remove in-edge t to e */
  589.                 for (j = 0; j < (e->numInEdges-1); j++)
  590.                     if (e->inEdges[j] == t)
  591.                     {
  592.                         memmove (&e->inEdges[j], &e->inEdges[j+1], 
  593.                                  (size_t)((e->numInEdges - j - 1) * sizeof(PBB)));
  594.                         break;
  595.                     }
  596.                 e->numInEdges--;    /* looses 1 arc */
  597.                 t->flg |= INVALID_BB;
  598.  
  599.                 if (pbb->flg & IS_LATCH_NODE)
  600.                     pproc->dfsLast[t->dfsLastNum] = pbb;
  601.                 else 
  602.                     i--;        /* to repeat this analysis */
  603.  
  604.                 change = TRUE;
  605.             }
  606.  
  607.             /* Check (!X && Y) case */
  608.             else if ((t->nodeType == TWO_BRANCH) && (t->numHlIcodes == 1) && 
  609.                 (t->numInEdges == 1) && (t->edges[THEN].BBptr == e)) 
  610.             {
  611.                 obb = t->edges[ELSE].BBptr;
  612.  
  613.                 /* Construct compound DBL_AND expression */
  614.                 picode = pproc->Icode.GetIcode(pbb->start + pbb->length -1);
  615.                 ticode = pproc->Icode.GetIcode(t->start + t->length -1);
  616.                 inverseCondOp (&picode->ic.hl.oper.exp);
  617.                 exp = boolCondExp (picode->ic.hl.oper.exp,
  618.                                    ticode->ic.hl.oper.exp, DBL_AND);
  619.                 picode->ic.hl.oper.exp = exp;
  620.  
  621.                 /* Replace in-edge to obb from t to pbb */
  622.                 for (j = 0; j < obb->numInEdges; j++)
  623.                     if (obb->inEdges[j] == t)
  624.                     {
  625.                         obb->inEdges[j] = pbb;
  626.                         break;
  627.                     }
  628.  
  629.                 /* New THEN and ELSE out-edges of pbb */
  630.                 pbb->edges[THEN].BBptr = e;
  631.                 pbb->edges[ELSE].BBptr = obb;
  632.                 
  633.                 /* Remove in-edge t to e */
  634.                 for (j = 0; j < (e->numInEdges-1); j++)
  635.                     if (e->inEdges[j] == t)
  636.                     {
  637.                         memmove (&e->inEdges[j], &e->inEdges[j+1], 
  638.                                  (size_t)((e->numInEdges - j - 1) * sizeof(PBB)));
  639.                         break;
  640.                     }
  641.                 e->numInEdges--;    /* looses 1 arc */
  642.                 t->flg |= INVALID_BB;
  643.  
  644.                 if (pbb->flg & IS_LATCH_NODE)
  645.                     pproc->dfsLast[t->dfsLastNum] = pbb;
  646.                 else 
  647.                     i--;        /* to repeat this analysis */
  648.  
  649.                 change = TRUE;
  650.             }
  651.  
  652.             /* Check (X && Y) case */
  653.             else if ((e->nodeType == TWO_BRANCH) && (e->numHlIcodes == 1) && 
  654.                      (e->numInEdges == 1) && (e->edges[THEN].BBptr == t)) 
  655.             {
  656.                 obb = e->edges[ELSE].BBptr;
  657.  
  658.                 /* Construct compound DBL_AND expression */
  659.                 picode = pproc->Icode.GetIcode(pbb->start + pbb->length -1);
  660.                 ticode = pproc->Icode.GetIcode(t->start + t->length -1);
  661.                 exp = boolCondExp (picode->ic.hl.oper.exp,
  662.                                    ticode->ic.hl.oper.exp, DBL_AND);
  663.                 picode->ic.hl.oper.exp = exp;
  664.                 
  665.                 /* Replace in-edge to obb from e to pbb */
  666.                 for (j = 0; j < obb->numInEdges; j++)
  667.                     if (obb->inEdges[j] == e)
  668.                     {
  669.                         obb->inEdges[j] = pbb;
  670.                         break;
  671.                     }
  672.  
  673.                 /* New ELSE out-edge of pbb */
  674.                 pbb->edges[ELSE].BBptr = obb;
  675.  
  676.                 /* Remove in-edge e to t */
  677.                 for (j = 0; j < (t->numInEdges-1); j++)
  678.                     if (t->inEdges[j] == e)
  679.                     {
  680.                         memmove (&t->inEdges[j], &t->inEdges[j+1], 
  681.                                  (size_t)((t->numInEdges - j - 1) * sizeof(PBB)));
  682.                         break;
  683.                     }
  684.                 t->numInEdges--;    /* looses 1 arc */
  685.                 e->flg |= INVALID_BB;
  686.  
  687.                 if (pbb->flg & IS_LATCH_NODE)
  688.                     pproc->dfsLast[e->dfsLastNum] = pbb;
  689.                 else 
  690.                     i--;        /* to repeat this analysis */
  691.  
  692.                 change = TRUE;
  693.             }
  694.  
  695.             /* Check (!X || Y) case */
  696.             else if ((e->nodeType == TWO_BRANCH) && (e->numHlIcodes == 1) && 
  697.                      (e->numInEdges == 1) && (e->edges[ELSE].BBptr == t)) 
  698.             {
  699.                 obb = e->edges[THEN].BBptr;
  700.  
  701.                 /* Construct compound DBL_OR expression */
  702.                 picode = pproc->Icode.GetIcode(pbb->start + pbb->length -1);
  703.                 ticode = pproc->Icode.GetIcode(t->start + t->length -1);
  704.                 inverseCondOp (&picode->ic.hl.oper.exp);
  705.                 exp = boolCondExp (picode->ic.hl.oper.exp,
  706.                                    ticode->ic.hl.oper.exp, DBL_OR);
  707.                 picode->ic.hl.oper.exp = exp;
  708.                 
  709.                 /* Replace in-edge to obb from e to pbb */
  710.                 for (j = 0; j < obb->numInEdges; j++)
  711.                     if (obb->inEdges[j] == e)
  712.                     {
  713.                         obb->inEdges[j] = pbb;
  714.                         break;
  715.                     }
  716.  
  717.                 /* New THEN and ELSE out-edges of pbb */
  718.                 pbb->edges[THEN].BBptr = obb;
  719.                 pbb->edges[ELSE].BBptr = t;
  720.  
  721.                 /* Remove in-edge e to t */
  722.                 for (j = 0; j < (t->numInEdges-1); j++)
  723.                     if (t->inEdges[j] == e)
  724.                     {
  725.                         memmove (&t->inEdges[j], &t->inEdges[j+1], 
  726.                                  (size_t)((t->numInEdges - j - 1) * sizeof(PBB)));
  727.                         break;
  728.                     }
  729.                 t->numInEdges--;    /* looses 1 arc */
  730.                 e->flg |= INVALID_BB;
  731.  
  732.                 if (pbb->flg & IS_LATCH_NODE)
  733.                     pproc->dfsLast[e->dfsLastNum] = pbb;
  734.                 else 
  735.                     i--;        /* to repeat this analysis */
  736.  
  737.                 change = TRUE;
  738.             }
  739.         }
  740.     }
  741.   }
  742. }
  743.  
  744.  
  745. void structure(PPROC pProc, derSeq *derivedG)
  746. /* Structuring algorithm to find the structures of the graph pProc->cfg */
  747. {
  748.     /* Find immediate dominators of the graph */
  749.     findImmedDom(pProc);
  750.     if (pProc->hasCase)
  751.        structCases(pProc); 
  752.     structLoops(pProc, derivedG); 
  753.     structIfs(pProc); 
  754. }
  755.