home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / dosdisas.zip / dccsrcoo.zip / reducible.cpp < prev    next >
C/C++ Source or Header  |  1997-04-09  |  13KB  |  439 lines
  1. /********************************************************************
  2.  *$Log:    reducible.c,v $
  3.  * Revision 2.7  94/02/23  18:06:44  cifuente
  4.  * newBB has an extra argument of type PPROC (doesn't apply to intervals).
  5.  * 
  6.  * Revision 2.6  93/10/01  09:00:27  cifuente
  7.  * boolT type - for compilation under unix SVR4.2
  8.  * 
  9.  * Revision 2.5  93/09/20  11:50:21  cifuente
  10.  * Changed tabs to spaces
  11.  * 
  12.  * Revision 2.4  93/08/23  12:22:00  cifuente
  13.  * Casts for DOS
  14.  * 
  15.  * Revision 1.1  93/08/23  12:16:18  cifuente
  16.  * Initial revision
  17.  * 
  18.  * Revision 2.1  93/03/30  14:53:41  cifuente
  19.  * Compiled with gcc.
  20.  * 
  21.  *  Checks for reducibility of a graph by intervals, and
  22.  *  constructs an equivalent reducible graph if one is not found.
  23.  ********************************************************************/
  24.  
  25. #include "dcc.h"
  26. #include <stdio.h>
  27. #ifdef __BORLAND__
  28. #include <alloc.h>
  29. #else
  30. #include <malloc.h>        /* For free() */
  31. #endif
  32. #include <string.h>
  33.  
  34. static Int      numInt;     /* Number of intervals      */
  35.  
  36.  
  37. #define nonEmpty(q)     (q != NULL)
  38. /* Returns whether the queue q is empty or not */
  39.  
  40. #define trivialGraph(G)     (G->numOutEdges == 0)
  41. /* Returns whether the graph is a trivial graph or not */
  42.  
  43.  
  44. static BB *firstOfQueue (queue **Q)
  45. /* Returns the first element in the queue Q, and removes this element
  46.  * from the list.  Q is not an empty queue.                 */
  47. { queue *elim;
  48.   BB *first;
  49.  
  50.     elim  = *Q;         /* Pointer to first node */
  51.     first = (*Q)->node;     /* First element */
  52.     *Q    = (*Q)->next;     /* Pointer to next node */
  53.     free (elim);            /* Free storage */
  54.     return (first);
  55. }
  56.  
  57.  
  58. queue *appendQueue (queue **Q, BB *node)
  59. /* Appends pointer to node at the end of the queue Q if node is not present
  60.  * in this queue.  Returns the queue node just appended.        */
  61. { queue *pq, *l;
  62.  
  63.     pq = allocStruc(queue);
  64.     pq->node = node;
  65.     pq->next = NULL;
  66.  
  67.     if (Q)
  68.         if (*Q)
  69.         {
  70.            for (l = *Q; l->next && l->node != node; l = l->next)
  71.               ;
  72.            if (l->node != node)
  73.               l->next = pq;
  74.         }
  75.         else        /* (*Q) == NULL */
  76.            *Q = pq;
  77.     return (pq);
  78. }
  79.  
  80.  
  81. static BB *firstOfInt (interval *pI)
  82. /* Returns the next unprocessed node of the interval list (pointed to by
  83.  * pI->currNode).  Removes this element logically from the list, by updating
  84.  * the currNode pointer to the next unprocessed element.  */
  85. { queue *pq;
  86.  
  87.     pq = pI->currNode;
  88.     if (pq == NULL)
  89.        return (NULL);
  90.     pI->currNode = pq->next;
  91.     return (pq->node);
  92. }
  93.  
  94.  
  95. static queue *appendNodeInt (queue *pqH, BB *node, interval *pI)
  96. /* Appends node node to the end of the interval list I, updates currNode
  97.  * if necessary, and removes the node from the header list H if it is 
  98.  * there.  The interval header information is placed in the field 
  99.  * node->inInterval.
  100.  * Note: nodes are added to the interval list in interval order (which
  101.  * topsorts the dominance relation).                    */
  102. { queue *pq,        /* Pointer to current node of the list      */
  103.          *prev;     /* Pointer to previous node in the list     */
  104.  
  105.     /* Append node if it is not already in the interval list */
  106.     pq = appendQueue (&pI->nodes, node);
  107.  
  108.     /* Update currNode if necessary */
  109.     if (pI->currNode == NULL)
  110.        pI->currNode = pq;
  111.  
  112.     /* Check header list for occurrence of node, if found, remove it 
  113.      * and decrement number of out-edges from this interval.    */
  114.     if (node->beenOnH && pqH)
  115.     {
  116.        prev = pqH;
  117.        for (pq = prev; pq && pq->node != node; pq = pq->next)
  118.           prev = pq;
  119.        if (pq == prev)
  120.        {
  121.           pqH = pqH->next;
  122.           pI->numOutEdges -= (byte)pq->node->numInEdges - 1;
  123.        }
  124.        else if (pq)
  125.        {
  126.           prev->next = pq->next;
  127.           pI->numOutEdges -= (byte)pq->node->numInEdges - 1;
  128.        }
  129.     }
  130.  
  131.     /* Update interval header information for this basic block */
  132.     node->inInterval = pI;
  133.  
  134.     return (pqH);
  135. }
  136.  
  137.  
  138. static void findIntervals (derSeq *derivedGi)
  139. /* Finds the intervals of graph derivedGi->Gi and places them in the list 
  140.  * of intervals derivedGi->Ii.
  141.  * Algorithm by M.S.Hecht.                      */
  142. {  interval *pI,        /* Interval being processed         */ 
  143.         *J;         /* ^ last interval in derivedGi->Ii */
  144.    BB *h,           /* Node being processed         */
  145.       *header,          /* Current interval's header node   */
  146.       *succ;            /* Successor basic block        */
  147.    Int i;           /* Counter              */
  148.    queue *H;            /* Queue of possible header nodes   */
  149.    boolT first = TRUE;       /* First pass through the loop      */
  150.  
  151.     H = appendQueue (NULL, derivedGi->Gi);  /* H = {first node of G} */
  152.     derivedGi->Gi->beenOnH = TRUE;
  153.     derivedGi->Gi->reachingInt = allocStruc(BB);    /* ^ empty BB */
  154.     memset (derivedGi->Gi->reachingInt, 0, sizeof(BB));
  155.  
  156.     /* Process header nodes list H */
  157.     while (nonEmpty (H))
  158.     {
  159.        header = firstOfQueue (&H);
  160.        pI = allocStruc(interval);
  161.        memset (pI, 0, sizeof(interval));
  162.        pI->numInt = (byte)numInt++;
  163.        if (first)               /* ^ to first interval  */
  164.           derivedGi->Ii = J = pI;
  165.        H = appendNodeInt (H, header, pI);   /* pI(header) = {header} */
  166.  
  167.        /* Process all nodes in the current interval list */
  168.        while ((h = firstOfInt (pI)) != NULL)
  169.        { 
  170.          /* Check all immediate successors of h */
  171.          for (i = 0; i < h->numOutEdges; i++)
  172.          {
  173.                succ = h->edges[i].BBptr;
  174.                succ->inEdgeCount--;
  175.  
  176.                if (succ->reachingInt == NULL)   /* first visit */
  177.                {
  178.               succ->reachingInt = header;
  179.               if (succ->inEdgeCount == 0) 
  180.                      H = appendNodeInt (H, succ, pI);
  181.               else if (! succ->beenOnH) /* out edge */
  182.               {
  183.                  appendQueue (&H, succ);
  184.                  succ->beenOnH = TRUE;
  185.                  pI->numOutEdges++;
  186.               }
  187.                }
  188.                else     /* node has been visited before */
  189.               if (succ->inEdgeCount == 0)
  190.               {
  191.                  if (succ->reachingInt == header || 
  192.                  succ->inInterval == pI) /* same interval */
  193.                  {
  194.                     if (succ != header)
  195.                                 H = appendNodeInt (H, succ, pI);
  196.                  }
  197.                  else            /* out edge */
  198.                 pI->numOutEdges++;
  199.               }
  200.               else if (succ != header && succ->beenOnH)
  201.                    pI->numOutEdges++;
  202.             }
  203.        }
  204.  
  205.        /* Link interval I to list of intervals */
  206.        if (! first)
  207.        {
  208.           J->next = pI;
  209.           J = pI;
  210.        }
  211.        else     /* first interval */
  212.           first = FALSE;
  213.     }
  214. }
  215.  
  216.  
  217. static void displayIntervals (interval *pI)
  218. /* Displays the intervals of the graph Gi.              */
  219. { queue *nodePtr;
  220.  
  221.     while (pI)
  222.     {
  223.        nodePtr = pI->nodes;
  224.        printf ("  Interval #: %ld\t#OutEdges: %ld\n", 
  225.            pI->numInt, pI->numOutEdges);
  226.  
  227.        while (nodePtr)
  228.        {
  229.           if (nodePtr->node->correspInt == NULL)    /* real BBs */
  230.              printf ("    Node: %ld\n", nodePtr->node->start);
  231.           else              /* BBs represent intervals */
  232.          printf ("   Node (corresp int): %d\n",
  233.              nodePtr->node->correspInt->numInt);
  234.           nodePtr = nodePtr->next;
  235.        }
  236.        pI = pI->next;
  237.     }
  238. }
  239.  
  240.  
  241. static derSeq *newDerivedSeq()
  242. /* Allocates space for a new derSeq node. */
  243. { derSeq *pder;
  244.  
  245.     pder = allocStruc(derSeq);
  246.     memset (pder, 0, sizeof(derSeq));
  247.     return (pder);
  248. }
  249.  
  250.  
  251. static void freeQueue (queue **q)
  252. /* Frees the storage allocated for the queue q*/
  253. { queue *queuePtr;
  254.  
  255.     for (queuePtr = *q; queuePtr; queuePtr = *q)
  256.     {
  257.        *q = (*q)->next;
  258.        free (queuePtr);
  259.     }
  260. }
  261.  
  262.  
  263. static void freeInterval (interval **pI)
  264. /* Frees the storage allocated for the interval pI */
  265. { interval *Iptr;
  266.  
  267.     while (*pI)
  268.     {
  269.        freeQueue (&((*pI)->nodes));
  270.        Iptr = *pI;
  271.        *pI = (*pI)->next;
  272.        free (Iptr);
  273.     }
  274. }
  275.  
  276.  
  277. void freeDerivedSeq(derSeq *derivedG)
  278. /* Frees the storage allocated by the derived sequence structure, except 
  279.  * for the original graph cfg (derivedG->Gi).               */
  280. { derSeq *derivedGi;
  281.  
  282.     while (derivedG)
  283.     {
  284.        freeInterval (&(derivedG->Ii));
  285.        if (derivedG->Gi->nodeType == INTERVAL_NODE)
  286.         freeCFG (derivedG->Gi);
  287.        derivedGi = derivedG;
  288.        derivedG  = derivedG->next;
  289.        free (derivedGi);
  290.     }
  291. }
  292.  
  293.  
  294. static boolT nextOrderGraph (derSeq *derivedGi)
  295. /* Finds the next order graph of derivedGi->Gi according to its intervals 
  296.  * (derivedGi->Ii), and places it in derivedGi->next->Gi.       */
  297. { interval *Ii;     /* Interval being processed         */
  298.   BB *BBnode,       /* New basic block of intervals         */
  299.      *curr,     /* BB being checked for out edges       */
  300.      *succ,     /* Successor node               */
  301.      derInt;
  302.   queue *listIi;    /* List of intervals                */
  303.   Int i,        /* Index to outEdges array          */
  304.       j;        /* Index to successors              */
  305.   boolT   sameGraph; /* Boolean, isomorphic graphs           */
  306.  
  307.     /* Process Gi's intervals */
  308.     derivedGi->next = newDerivedSeq();
  309.     Ii = derivedGi->Ii;
  310.     sameGraph = TRUE;
  311.     derInt.next = NULL;
  312.     BBnode = &derInt;
  313.  
  314.     while (Ii) {
  315.        i = 0;
  316.        BBnode = newBB (BBnode, -1, -1, INTERVAL_NODE, Ii->numOutEdges, NULL);
  317.        BBnode->correspInt = Ii;
  318.        listIi = Ii->nodes;
  319.  
  320.        /* Check for more than 1 interval */
  321.        if (sameGraph && listIi->next)
  322.           sameGraph = FALSE;
  323.  
  324.        /* Find out edges */
  325.        if (BBnode->numOutEdges > 0)
  326.           while (listIi) {
  327.          curr = listIi->node;
  328.          for (j = 0; j < curr->numOutEdges; j++) {
  329.              succ = curr->edges[j].BBptr;
  330.              if (succ->inInterval != curr->inInterval)
  331.                 BBnode->edges[i++].intPtr = succ->inInterval;
  332.          }
  333.              listIi = listIi->next;
  334.           }
  335.  
  336.        /* Next interval */
  337.        Ii = Ii->next;
  338.     }
  339.  
  340.     /* Convert list of pointers to intervals into a real graph.
  341.      * Determines the number of in edges to each new BB, and places it
  342.      * in numInEdges and inEdgeCount for later interval processing. */
  343.     curr = derivedGi->next->Gi = derInt.next;
  344.     while (curr) {
  345.        for (i = 0; i < curr->numOutEdges; i++) {
  346.            BBnode = derivedGi->next->Gi;    /* BB of an interval */
  347.            while (BBnode && curr->edges[i].intPtr != BBnode->correspInt)
  348.           BBnode = BBnode->next;
  349.            if (BBnode) {
  350.           curr->edges[i].BBptr = BBnode;
  351.           BBnode->numInEdges++;
  352.           BBnode->inEdgeCount++;
  353.            }
  354.            else
  355.           fatalError (INVALID_INT_BB);
  356.        }
  357.        curr = curr->next;
  358.     }
  359.     return (boolT)(! sameGraph);
  360. }
  361.  
  362.  
  363.  
  364. static byte findDerivedSeq (derSeq *derivedGi)
  365. /* Finds the derived sequence of the graph derivedG->Gi (ie. cfg).
  366.  * Constructs the n-th order graph and places all the intermediate graphs
  367.  * in the derivedG list sequence.                   */
  368. {  BB *Gi;      /* Current derived sequence graph       */
  369.  
  370.     Gi = derivedGi->Gi;
  371.     while (! trivialGraph (Gi))
  372.     {
  373.          /* Find the intervals of Gi and place them in derivedGi->Ii */
  374.          findIntervals (derivedGi);
  375.  
  376.          /* Create Gi+1 and check if it is equivalent to Gi */
  377.          if (! nextOrderGraph (derivedGi))
  378.             break; 
  379.  
  380.          derivedGi = derivedGi->next;
  381.          Gi = derivedGi->Gi;
  382.          stats.nOrder++;
  383.     }
  384.  
  385.     if (! trivialGraph (Gi))
  386.     {
  387.         freeDerivedSeq(derivedGi->next);    /* remove Gi+1 */
  388.         derivedGi->next = NULL;
  389.         return FALSE;
  390.     }
  391.     findIntervals (derivedGi);
  392.     return TRUE;
  393. }
  394.  
  395.  
  396. static void nodeSplitting (BB *G)
  397. /* Converts the irreducible graph G into an equivalent reducible one, by
  398.  * means of node splitting.  */
  399. {
  400.  
  401. }
  402.  
  403.  
  404.  
  405. void displayDerivedSeq(derSeq *derGi)
  406. /* Displays the derived sequence and intervals of the graph G */
  407. {
  408.     Int n = 1;      /* Derived sequence number */
  409.     printf ("\nDerived Sequence Intervals\n");
  410.     while (derGi)
  411.     {
  412.        printf ("\nIntervals for G%lX\n", n++);
  413.        displayIntervals (derGi->Ii);
  414.        derGi = derGi->next;
  415.     }
  416. }
  417.  
  418.  
  419. void checkReducibility (PPROC pProc, derSeq **derivedG)
  420. /* Checks whether the control flow graph, cfg, is reducible or not.
  421.  * If it is not reducible, it is converted into an equivalent reducible
  422.  * graph by node splitting.  The derived sequence of graphs built from cfg
  423.  * are returned in the pointer *derivedG.
  424.  */
  425. { byte    reducible;            /* Reducible graph flag     */
  426.  
  427.     numInt = 1;         /* reinitialize no. of intervals*/
  428.     stats.nOrder = 1;       /* nOrder(cfg) = 1      */
  429.     *derivedG = newDerivedSeq();
  430.     (*derivedG)->Gi = pProc->cfg;
  431.     reducible = findDerivedSeq(*derivedG);
  432.  
  433.     if (! reducible) {
  434.        pProc->flg |= GRAPH_IRRED;
  435.        nodeSplitting (pProc->cfg);
  436.     }
  437. }
  438.  
  439.