home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / dosdisas.zip / dccsrcoo.zip / graph.cpp < prev    next >
C/C++ Source or Header  |  1997-04-09  |  12KB  |  431 lines
  1. /*****************************************************************************
  2.  *$Log:    graph.c,v $
  3.  * Revision 2.11  94/02/23  18:46:06  cifuente
  4.  * newBB has extra parameter (PPROC).  It also marks all icodes that belong
  5.  * to the basic block with the pointer to the current BB (inBB field).
  6.  * 
  7.  * Revision 2.10  94/02/22  15:16:31  cifuente
  8.  * Fixed minor bug.
  9.  * 
  10.  * Revision 2.9  93/12/22  15:54:16  cifuente
  11.  * picode->invalid field set when NO_CODE flag is set.
  12.  * 
  13.  * Revision 2.8  93/12/14  14:05:53  cifuente
  14.  * ic.ll.immed.proc has new level of indirection.
  15.  * 
  16.  * Revision 2.7  93/11/16  12:56:54  cifuente
  17.  * Bug in removal of redundant JMPs.  JX was not considering fall-through
  18.  * case that could be JMP.
  19.  * 
  20.  * Revision 2.6  93/10/20  14:37:44  cifuente
  21.  * New level of indirection for icode array (Icode.icode[])
  22.  * 
  23.  * Revision 2.5  93/09/29  10:44:26  cifuente
  24.  * LOW_LEVEL and HIGH_LEVEL icode definitions.  Increases llIcode indirection
  25.  * by 2 levels.
  26.  * 
  27.  * Revision 2.3  93/08/23  12:15:31  cifuente
  28.  * Interactive mode with curses
  29.  * 
  30.  * Revision 2.1  93/03/30  14:51:34  cifuente
  31.  * Compiled with gcc.
  32.  * 
  33.  *             REVCOMP project CFG related functions
  34.  ****************************************************************************/
  35.  
  36. #include "dcc.h"
  37. #include <string.h>
  38. #if __BORLAND__
  39. #include <alloc.h>
  40. #else
  41. #include <malloc.h>        /* For free() */
  42. #endif
  43.  
  44. static PBB  rmJMP(PPROC pProc, Int marker, PBB pBB);
  45. static void mergeFallThrough(PPROC pProc, PBB pBB);
  46. static void dfsNumbering(PBB pBB, PBB *dfsLast, Int *first, Int *last);
  47.  
  48. /*****************************************************************************
  49.  * createCFG - Create the basic control flow graph
  50.  ****************************************************************************/
  51. PBB createCFG(PPROC pProc)
  52. {
  53.     /* Splits Icode associated with the procedure into Basic Blocks.
  54.      * The links between BBs represent the control flow graph of the 
  55.      * procedure.
  56.      * A Basic Block is defined to end on one of the following instructions:
  57.      * 1) Conditional and unconditional jumps
  58.      * 2) CALL(F)
  59.      * 3) RET(F)
  60.      * 4) On the instruction before a join (a flagged TARGET)
  61.      * 5) Repeated string instructions 
  62.      * 6) End of procedure
  63.     */   
  64.     Int        i;
  65.     Int        ip, start;
  66.     BB        cfg;
  67.     PBB        psBB;
  68.     PBB        pBB    = &cfg;
  69.     PICODE    pIcode = pProc->Icode.GetFirstIcode();
  70.  
  71.     cfg.next = NULL;
  72.     stats.numBBbef = stats.numBBaft = 0;
  73.     for (ip = start = 0; pProc->Icode.IsValid(pIcode); ip++, pIcode++) 
  74.     {
  75.         /* Stick a NOWHERE_NODE on the end if we terminate
  76.          * with anything other than a ret, jump or terminate */
  77.         if (ip + 1 == pProc->Icode.GetNumIcodes() && 
  78.             ! (pIcode->ic.ll.flg & TERMINATES) &&
  79.             pIcode->ic.ll.opcode != iJMP && pIcode->ic.ll.opcode != iJMPF &&
  80.             pIcode->ic.ll.opcode != iRET && pIcode->ic.ll.opcode != iRETF)
  81.             newBB(pBB, start, ip, NOWHERE_NODE, 0, pProc);
  82.  
  83.         /* Only process icodes that have valid instructions */
  84.         else if ((pIcode->ic.ll.flg & NO_CODE) != NO_CODE) 
  85.         {
  86.             switch (pIcode->ic.ll.opcode) {
  87.             case iJB:  case iJBE:  case iJAE:  case iJA:
  88.             case iJL:  case iJLE:  case iJGE:  case iJG:
  89.             case iJE:  case iJNE:  case iJS:   case iJNS:
  90.             case iJO:  case iJNO:  case iJP:   case iJNP:
  91.             case iJCXZ:
  92.                 pBB = newBB(pBB, start, ip, TWO_BRANCH, 2, pProc);
  93.             CondJumps:
  94.                 start = ip + 1;
  95.                 pBB->edges[0].ip = (dword)start;
  96.                 /* This is for jumps off into nowhere */
  97.                 if (pIcode->ic.ll.flg & NO_LABEL)
  98.                     pBB->numOutEdges--;
  99.                 else
  100.                     pBB->edges[1].ip = pIcode->ic.ll.immed.op;
  101.                 break;
  102.  
  103.             case iLOOP: case iLOOPE: case iLOOPNE:
  104.                 pBB = newBB(pBB, start, ip, LOOP_NODE, 2, pProc);
  105.                 goto CondJumps;
  106.  
  107.             case iJMPF: case iJMP:
  108.                 if (pIcode->ic.ll.flg & SWITCH)
  109.                 {
  110.                     pBB = newBB(pBB, start, ip, MULTI_BRANCH,
  111.                                pIcode->ic.ll.caseTbl.numEntries, pProc);
  112.                     for (i = 0; i < pIcode->ic.ll.caseTbl.numEntries; i++)
  113.                         pBB->edges[i].ip = pIcode->ic.ll.caseTbl.entries[i];
  114.                     pProc->hasCase = TRUE;
  115.                 }
  116.                 else if ((pIcode->ic.ll.flg & (I | NO_LABEL)) == I) {
  117.                     pBB = newBB(pBB, start, ip, ONE_BRANCH, 1, pProc);
  118.                     pBB->edges[0].ip = pIcode->ic.ll.immed.op;
  119.                 }
  120.                 else    
  121.                     newBB(pBB, start, ip, NOWHERE_NODE, 0, pProc);
  122.                 start = ip + 1;
  123.                 break;
  124.  
  125.             case iCALLF: case iCALL:
  126.                 { PPROC p = pIcode->ic.ll.immed.proc.proc;
  127.                   if (p)
  128.                       i = ((p->flg) & TERMINATES) ? 0 : 1;
  129.                   else
  130.                       i = 1;
  131.                   pBB = newBB(pBB, start, ip, CALL_NODE, i, pProc);
  132.                   start = ip + 1;
  133.                   if (i)
  134.                      pBB->edges[0].ip = (dword)start;
  135.                 }
  136.                 break;
  137.  
  138.             case iRET:  case iRETF:
  139.                 newBB(pBB, start, ip, RETURN_NODE, 0, pProc);
  140.                 start = ip + 1;
  141.                 break;
  142.  
  143.             default:
  144.                 /* Check for exit to DOS */
  145.                 if (pIcode->ic.ll.flg & TERMINATES) 
  146.                 {
  147.                     pBB = newBB(pBB, start, ip, TERMINATE_NODE, 0, pProc);
  148.                     start = ip + 1;
  149.                 }
  150.                 /* Check for a fall through */
  151.                 else if (pProc->Icode.GetFirstIcode()[ip + 1].ic.ll.flg & (TARGET | CASE))
  152.                 {
  153.                     pBB = newBB(pBB, start, ip, FALL_NODE, 1, pProc);
  154.                     start = ip + 1;
  155.                     pBB->edges[0].ip = (dword)start;
  156.                 }
  157.                 break;
  158.             }
  159.         }
  160.     }
  161.  
  162.     /* Convert list of BBs into a graph */
  163.     for (pBB = cfg.next; pBB; pBB = pBB->next)
  164.     {
  165.         for (i = 0; i < pBB->numOutEdges; i++)
  166.         {
  167.             ip = pBB->edges[i].ip;
  168.             if (ip >= SYNTHESIZED_MIN)
  169.                 fatalError (INVALID_SYNTHETIC_BB);
  170.             else
  171.             {
  172.                 for (psBB = cfg.next; psBB; psBB = psBB->next)
  173.                     if (psBB->start == ip)
  174.                     {
  175.                         pBB->edges[i].BBptr = psBB;
  176.                         psBB->numInEdges++;
  177.                         break;
  178.                     }
  179.                 if (! psBB)
  180.                     fatalError(NO_BB, ip, pProc->name);
  181.             }
  182.         }
  183.     }
  184.     return cfg.next;
  185. }
  186.  
  187.  
  188. /*****************************************************************************
  189.  * newBB - Allocate new BB and link to end of list
  190.  *****************************************************************************/
  191. PBB newBB (PBB pBB, Int start, Int ip, byte nodeType, Int numOutEdges, 
  192.            PPROC pproc)
  193. {
  194.   PBB pnewBB;
  195.  
  196.     pnewBB = allocStruc(BB);
  197.     memset (pnewBB, 0, sizeof(BB));
  198.     pnewBB->nodeType = nodeType;    /* Initialise */
  199.     pnewBB->start = start;
  200.     pnewBB->length = ip - start + 1;
  201.     pnewBB->numOutEdges = (byte)numOutEdges;
  202.     pnewBB->immedDom = NO_DOM;
  203.     pnewBB->loopHead = pnewBB->caseHead = pnewBB->caseTail =
  204.         pnewBB->latchNode= pnewBB->loopFollow = NO_NODE;
  205.  
  206.     if (numOutEdges)
  207.         pnewBB->edges = (TYPEADR_TYPE*)allocMem(numOutEdges * sizeof(TYPEADR_TYPE));
  208.  
  209.     /* Mark the basic block to which the icodes belong to, but only for
  210.      * real code basic blocks (ie. not interval bbs) */
  211.     if (start >= 0)
  212.         pproc->Icode.SetInBB(start, ip, pnewBB);
  213.  
  214.     while (pBB->next)        /* Link */
  215.         pBB = pBB->next;
  216.     pBB->next = pnewBB;
  217.  
  218.     if (start != -1) {        /* Only for code BB's */
  219.         stats.numBBbef++;
  220.     }
  221.     return pnewBB;
  222. }
  223.  
  224.  
  225. /*****************************************************************************
  226.  * freeCFG - Deallocates a cfg
  227.  ****************************************************************************/
  228. void freeCFG(PBB cfg)
  229. {
  230.     PBB    pBB;
  231.  
  232.     for (pBB = cfg; pBB; pBB = cfg) {
  233.         if (pBB->inEdges)
  234.             free(pBB->inEdges);
  235.         if (pBB->edges)
  236.             free(pBB->edges);
  237.         cfg = pBB->next;
  238.         free(pBB);
  239.     }
  240. }
  241.  
  242.  
  243. /*****************************************************************************
  244.  * compressCFG - Remove redundancies and add in-edge information
  245.  ****************************************************************************/
  246. void compressCFG(PPROC pProc)
  247. { PBB    pBB, pNxt;
  248.   Int    ip, first=0, last, i;
  249.  
  250.     /* First pass over BB list removes redundant jumps of the form
  251.      * (Un)Conditional -> Unconditional jump  */
  252.     for (pBB = pProc->cfg; pBB; pBB = pBB->next)
  253.         if (pBB->numInEdges != 0 && (pBB->nodeType == ONE_BRANCH ||
  254.             pBB->nodeType == TWO_BRANCH))
  255.             for (i = 0; i < pBB->numOutEdges; i++) 
  256.     {
  257.             ip   = pBB->start + pBB->length - 1;
  258.             pNxt = rmJMP(pProc, ip, pBB->edges[i].BBptr);
  259.  
  260.             if (pBB->numOutEdges)   /* Might have been clobbered */
  261.             {
  262.                 pBB->edges[i].BBptr = pNxt;
  263.                 pProc->Icode.SetImmediateOp(ip, (dword)pNxt->start);
  264.             }
  265.     }
  266.  
  267.     /* Next is a depth-first traversal merging any FALL_NODE or
  268.      * ONE_BRANCH that fall through to a node with that as their only
  269.      * in-edge. */
  270.     mergeFallThrough(pProc, pProc->cfg);
  271.  
  272.     /* Remove redundant BBs created by the above compressions
  273.      * and allocate in-edge arrays as required. */
  274.     stats.numBBaft = stats.numBBbef;
  275.  
  276.     for (pBB = pProc->cfg; pBB; pBB = pNxt)
  277.     {
  278.         pNxt = pBB->next;
  279.         if (pBB->numInEdges == 0) 
  280.         {
  281.             if (pBB == pProc->cfg)    /* Init it misses out on */
  282.                 pBB->index = UN_INIT;
  283.             else
  284.             {
  285.                 if (pBB->numOutEdges)
  286.                     free(pBB->edges);
  287.                 free(pBB);
  288.                 stats.numBBaft--;
  289.             }
  290.         }
  291.         else 
  292.         {
  293.             pBB->inEdgeCount = pBB->numInEdges;
  294.             pBB->inEdges = (PBB*)allocMem(pBB->numInEdges * sizeof(PBB));
  295.         }
  296.     }
  297.  
  298.     /* Allocate storage for dfsLast[] array */
  299.     pProc->numBBs = stats.numBBaft;
  300.     pProc->dfsLast = (PBB*)allocMem(pProc->numBBs * sizeof(PBB)); 
  301.  
  302.     /* Now do a dfs numbering traversal and fill in the inEdges[] array */
  303.     last = pProc->numBBs - 1;
  304.     dfsNumbering(pProc->cfg, pProc->dfsLast, &first, &last);
  305. }
  306.  
  307.  
  308. /****************************************************************************
  309.  * rmJMP - If BB addressed is just a JMP it is replaced with its target
  310.  ***************************************************************************/
  311. static PBB rmJMP(PPROC pProc, Int marker, PBB pBB)
  312. {
  313.     marker += DFS_JMP;
  314.  
  315.     while (pBB->nodeType == ONE_BRANCH && pBB->length == 1) {
  316.         if (pBB->traversed != marker) {
  317.             pBB->traversed = marker;
  318.             if (--pBB->numInEdges)
  319.                 pBB->edges[0].BBptr->numInEdges++;
  320.             else
  321.             {
  322.                 pProc->Icode.SetLlFlag(pBB->start, NO_CODE);
  323.                 pProc->Icode.SetLlInvalid(pBB->start, TRUE);
  324.             }
  325.  
  326.             pBB = pBB->edges[0].BBptr;
  327.         }
  328.         else {            /* We are going around in circles */
  329.             pBB->nodeType = NOWHERE_NODE;
  330.             pProc->Icode.GetIcode(pBB->start)->ic.ll.immed.op = (dword)pBB->start;
  331.             pProc->Icode.SetImmediateOp(pBB->start, (dword)pBB->start);
  332.             do {
  333.                 pBB = pBB->edges[0].BBptr;
  334.                 if (! --pBB->numInEdges)
  335.                 {
  336.                     pProc->Icode.SetLlFlag(pBB->start, NO_CODE);
  337.                     pProc->Icode.SetLlInvalid(pBB->start, TRUE);
  338.                 }
  339.             } while (pBB->nodeType != NOWHERE_NODE);
  340.  
  341.             free(pBB->edges);
  342.             pBB->numOutEdges = 0;
  343.             pBB->edges       = NULL;
  344.         }
  345.     }
  346.     return pBB;
  347. }
  348.  
  349.  
  350. /*****************************************************************************
  351.  * mergeFallThrough
  352.  ****************************************************************************/
  353. static void mergeFallThrough(PPROC pProc, PBB pBB)
  354. {
  355.     PBB    pChild;
  356.     Int    i, ip;
  357.  
  358.     if (pBB) {
  359.         while (pBB->nodeType == FALL_NODE || pBB->nodeType == ONE_BRANCH) 
  360.         {
  361.             pChild = pBB->edges[0].BBptr;
  362.             /* Jump to next instruction can always be removed */
  363.             if (pBB->nodeType == ONE_BRANCH) 
  364.             {
  365.                 ip = pBB->start + pBB->length;
  366.                 for (i = ip; i < pChild->start
  367.                     && (pProc->Icode.GetLlFlag(i) & NO_CODE); i++);
  368.                 if (i != pChild->start)
  369.                     break;
  370.                 pProc->Icode.SetLlFlag(ip - 1, NO_CODE);
  371.                 pProc->Icode.SetLlInvalid(ip - 1, TRUE);
  372.                 pBB->nodeType = FALL_NODE;
  373.                 pBB->length--;
  374.  
  375.             }
  376.             /* If there's no other edges into child can merge */
  377.             if (pChild->numInEdges != 1)
  378.                 break;
  379.  
  380.             pBB->nodeType = pChild->nodeType;
  381.             pBB->length = pChild->start + pChild->length - pBB->start;
  382.             pProc->Icode.ClearLlFlag(pChild->start, TARGET);
  383.             pBB->numOutEdges = pChild->numOutEdges;
  384.             free(pBB->edges);
  385.             pBB->edges = pChild->edges;
  386.  
  387.             pChild->numOutEdges = pChild->numInEdges = 0;
  388.             pChild->edges = NULL;
  389.         }
  390.         pBB->traversed = DFS_MERGE;
  391.  
  392.         /* Process all out edges recursively */
  393.         for (i = 0; i < pBB->numOutEdges; i++)
  394.             if (pBB->edges[i].BBptr->traversed != DFS_MERGE)
  395.                 mergeFallThrough(pProc, pBB->edges[i].BBptr);
  396.     }
  397. }
  398.  
  399.  
  400. /*****************************************************************************
  401.  * dfsNumbering - Numbers nodes during first and last visits and determine 
  402.  * in-edges
  403.  ****************************************************************************/
  404. static void dfsNumbering(PBB pBB, PBB *dfsLast, Int *first, Int *last)
  405. {
  406.     PBB        pChild;
  407.     byte    i;
  408.  
  409.     if (pBB) 
  410.     {
  411.         pBB->traversed = DFS_NUM;
  412.         pBB->dfsFirstNum = (*first)++;
  413.  
  414.         /* index is being used as an index to inEdges[]. */
  415.         for (i = 0; i < pBB->numOutEdges; i++) 
  416.         {
  417.             pChild = pBB->edges[i].BBptr;
  418.             pChild->inEdges[pChild->index++] = pBB;
  419.  
  420.             /* Is this the last visit? */
  421.             if (pChild->index == pChild->numInEdges)
  422.                 pChild->index = UN_INIT;
  423.  
  424.             if (pChild->traversed != DFS_NUM)
  425.                 dfsNumbering(pChild, dfsLast, first, last);
  426.         }
  427.         pBB->dfsLastNum = *last;
  428.         dfsLast[(*last)--] = pBB;
  429.     }
  430. }
  431.