udm.cpp 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159
  1. /*****************************************************************************
  2. * dcc project Universal Decompilation Module
  3. * This is supposedly a machine independant and language independant module
  4. * that just plays with abstract cfg's and intervals and such like.
  5. * (C) Cristina Cifuentes
  6. ****************************************************************************/
  7. #include <list>
  8. #include <cassert>
  9. #include <stdio.h>
  10. #include "dcc.h"
  11. static void displayCFG(Function * pProc);
  12. static void displayDfs(BB * pBB);
  13. /****************************************************************************
  14. * udm
  15. ****************************************************************************/
  16. void udm(void)
  17. {
  18. /* Build the control flow graph, find idioms, and convert low-level
  19. * icodes to high-level ones */
  20. for (auto iter = pProcList.rbegin(); iter!=pProcList.rend(); ++iter)
  21. {
  22. if (iter->flg & PROC_ISLIB)
  23. continue; /* Ignore library functions */
  24. /* Create the basic control flow graph */
  25. iter->createCFG();
  26. if (option.VeryVerbose)
  27. iter->displayCFG();
  28. /* Remove redundancies and add in-edge information */
  29. iter->compressCFG();
  30. /* Print 2nd pass assembler listing */
  31. if (option.asm2)
  32. disassem(2, &(*iter));
  33. /* Idiom analysis and propagation of long type */
  34. iter->lowLevelAnalysis();
  35. /* Generate HIGH_LEVEL icodes whenever possible */
  36. iter->highLevelGen();
  37. }
  38. /* Data flow analysis - eliminate condition codes, extraneous registers
  39. * and intermediate instructions. Find expressions by forward
  40. * substitution algorithm */
  41. pProcList.front().dataFlow (0);
  42. derSeq *derivedG=0;
  43. /* Control flow analysis - structuring algorithm */
  44. for (auto iter = pProcList.rbegin(); iter!=pProcList.rend(); ++iter)
  45. {
  46. if (iter->flg & PROC_ISLIB)
  47. continue; /* Ignore library functions */
  48. /* Make cfg reducible and build derived sequences */
  49. derivedG=iter->checkReducibility();
  50. if (option.VeryVerbose)
  51. derivedG->display();
  52. /* Structure the graph */
  53. iter->structure(derivedG);
  54. /* Check for compound conditions */
  55. iter->compoundCond ();
  56. if (option.verbose) {
  57. printf("\nDepth first traversal - Proc %s\n", iter->name);
  58. iter->cfg.front()->displayDfs();
  59. }
  60. /* Free storage occupied by this procedure */
  61. freeDerivedSeq(*derivedG);
  62. }
  63. }
  64. static const char *const s_nodeType[] = {"branch", "if", "case", "fall", "return", "call",
  65. "loop", "repeat", "interval", "cycleHead",
  66. "caseHead", "terminate",
  67. "nowhere" };
  68. static const char *const s_loopType[] = {"noLoop", "while", "repeat", "loop", "for"};
  69. /****************************************************************************
  70. * displayCFG - Displays the Basic Block list
  71. ***************************************************************************/
  72. void Function::displayCFG()
  73. {
  74. Int i;
  75. BB * pBB;
  76. printf("\nBasic Block List - Proc %s", name);
  77. for (auto iter = cfg.begin(); iter!=cfg.end(); ++iter)
  78. {
  79. pBB = *iter;
  80. printf("\nnode type = %s, ", s_nodeType[pBB->nodeType]);
  81. printf("start = %ld, length = %ld, #out edges = %ld\n",
  82. pBB->start, pBB->length, pBB->numOutEdges);
  83. for (i = 0; i < pBB->numOutEdges; i++)
  84. printf(" outEdge[%2d] = %ld\n",i, pBB->edges[i].BBptr->start);
  85. }
  86. }
  87. /*****************************************************************************
  88. * displayDfs - Displays the CFG using a depth first traversal
  89. ****************************************************************************/
  90. void BB::displayDfs()
  91. {
  92. Int i;
  93. assert(this);
  94. traversed = DFS_DISP;
  95. printf("node type = %s, ", s_nodeType[nodeType]);
  96. printf("start = %ld, length = %ld, #in-edges = %ld, #out-edges = %ld\n",
  97. start, length, inEdges.size(), numOutEdges);
  98. printf("dfsFirst = %ld, dfsLast = %ld, immed dom = %ld\n",
  99. dfsFirstNum, dfsLastNum,
  100. immedDom == MAX ? -1 : immedDom);
  101. printf("loopType = %s, loopHead = %ld, latchNode = %ld, follow = %ld\n",
  102. s_loopType[loopType],
  103. loopHead == MAX ? -1 : loopHead,
  104. latchNode == MAX ? -1 : latchNode,
  105. loopFollow == MAX ? -1 : loopFollow);
  106. printf ("ifFollow = %ld, caseHead = %ld, caseTail = %ld\n",
  107. ifFollow == MAX ? -1 : ifFollow,
  108. caseHead == MAX ? -1 : caseHead,
  109. caseTail == MAX ? -1 : caseTail);
  110. if (nodeType == INTERVAL_NODE)
  111. printf("corresponding interval = %ld\n", correspInt->numInt);
  112. else
  113. for (i = 0; i < inEdges.size(); i++)
  114. printf (" inEdge[%ld] = %ld\n", i, inEdges[i]->start);
  115. /* Display out edges information */
  116. for (i = 0; i < numOutEdges; i++)
  117. if (nodeType == INTERVAL_NODE)
  118. printf(" outEdge[%ld] = %ld\n", i,
  119. edges[i].BBptr->correspInt->numInt);
  120. else
  121. printf(" outEdge[%d] = %ld\n", i, edges[i].BBptr->start);
  122. printf("----\n");
  123. /* Recursive call on successors of current node */
  124. for (i = 0; i < numOutEdges; i++)
  125. if (edges[i].BBptr->traversed != DFS_DISP)
  126. edges[i].BBptr->displayDfs();
  127. }