graph.cpp 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379
  1. /*****************************************************************************
  2. * dcc project CFG related functions
  3. * (C) Cristina Cifuentes
  4. ****************************************************************************/
  5. #include "dcc.h"
  6. #include <string.h>
  7. #if __BORLAND__
  8. #include <alloc.h>
  9. #else
  10. #include <malloc.h> /* For free() */
  11. #endif
  12. #include "graph.h"
  13. static BB * rmJMP(Function * pProc, Int marker, BB * pBB);
  14. static void mergeFallThrough(Function * pProc, BB * pBB);
  15. static void dfsNumbering(BB * pBB, std::vector<BB*> &dfsLast, Int *first, Int *last);
  16. /*****************************************************************************
  17. * createCFG - Create the basic control flow graph
  18. ****************************************************************************/
  19. void Function::createCFG()
  20. {
  21. /* Splits Icode associated with the procedure into Basic Blocks.
  22. * The links between BBs represent the control flow graph of the
  23. * procedure.
  24. * A Basic Block is defined to end on one of the following instructions:
  25. * 1) Conditional and unconditional jumps
  26. * 2) CALL(F)
  27. * 3) RET(F)
  28. * 4) On the instruction before a join (a flagged TARGET)
  29. * 5) Repeated string instructions
  30. * 6) End of procedure
  31. */
  32. Int i;
  33. Int ip, start;
  34. BB * psBB;
  35. BB * pBB;
  36. ICODE * pIcode = Icode.GetFirstIcode();
  37. stats.numBBbef = stats.numBBaft = 0;
  38. for (ip = start = 0; Icode.IsValid(pIcode); ip++, pIcode++)
  39. {
  40. /* Stick a NOWHERE_NODE on the end if we terminate
  41. * with anything other than a ret, jump or terminate */
  42. if (ip + 1 == Icode.GetNumIcodes() &&
  43. ! (pIcode->ic.ll.flg & TERMINATES) &&
  44. pIcode->ic.ll.opcode != iJMP && pIcode->ic.ll.opcode != iJMPF &&
  45. pIcode->ic.ll.opcode != iRET && pIcode->ic.ll.opcode != iRETF)
  46. pBB=BB::Create(start, ip, NOWHERE_NODE, 0, this);
  47. /* Only process icodes that have valid instructions */
  48. else if ((pIcode->ic.ll.flg & NO_CODE) != NO_CODE)
  49. {
  50. switch (pIcode->ic.ll.opcode) {
  51. case iJB: case iJBE: case iJAE: case iJA:
  52. case iJL: case iJLE: case iJGE: case iJG:
  53. case iJE: case iJNE: case iJS: case iJNS:
  54. case iJO: case iJNO: case iJP: case iJNP:
  55. case iJCXZ:
  56. pBB = BB::Create(start, ip, TWO_BRANCH, 2, this);
  57. CondJumps:
  58. start = ip + 1;
  59. pBB->edges[0].ip = (dword)start;
  60. /* This is for jumps off into nowhere */
  61. if (pIcode->ic.ll.flg & NO_LABEL)
  62. pBB->numOutEdges--;
  63. else
  64. pBB->edges[1].ip = pIcode->ic.ll.immed.op;
  65. break;
  66. case iLOOP: case iLOOPE: case iLOOPNE:
  67. pBB = BB::Create(start, ip, LOOP_NODE, 2, this);
  68. goto CondJumps;
  69. case iJMPF: case iJMP:
  70. if (pIcode->ic.ll.flg & SWITCH)
  71. {
  72. pBB = BB::Create(start, ip, MULTI_BRANCH,
  73. pIcode->ic.ll.caseTbl.numEntries, this);
  74. for (i = 0; i < pIcode->ic.ll.caseTbl.numEntries; i++)
  75. pBB->edges[i].ip = pIcode->ic.ll.caseTbl.entries[i];
  76. hasCase = TRUE;
  77. }
  78. else if ((pIcode->ic.ll.flg & (I | NO_LABEL)) == I) {
  79. pBB = BB::Create(start, ip, ONE_BRANCH, 1, this);
  80. pBB->edges[0].ip = pIcode->ic.ll.immed.op;
  81. }
  82. else
  83. BB::Create(start, ip, NOWHERE_NODE, 0, this);
  84. start = ip + 1;
  85. break;
  86. case iCALLF: case iCALL:
  87. {
  88. Function * p = pIcode->ic.ll.immed.proc.proc;
  89. if (p)
  90. i = ((p->flg) & TERMINATES) ? 0 : 1;
  91. else
  92. i = 1;
  93. pBB = BB::Create(start, ip, CALL_NODE, i, this);
  94. start = ip + 1;
  95. if (i)
  96. pBB->edges[0].ip = (dword)start;
  97. }
  98. break;
  99. case iRET: case iRETF:
  100. BB::Create(start, ip, RETURN_NODE, 0, this);
  101. start = ip + 1;
  102. break;
  103. default:
  104. /* Check for exit to DOS */
  105. if (pIcode->ic.ll.flg & TERMINATES)
  106. {
  107. pBB = BB::Create(start, ip, TERMINATE_NODE, 0, this);
  108. start = ip + 1;
  109. }
  110. /* Check for a fall through */
  111. else if (Icode.GetFirstIcode()[ip + 1].ic.ll.flg & (TARGET | CASE))
  112. {
  113. pBB = BB::Create(start, ip, FALL_NODE, 1, this);
  114. start = ip + 1;
  115. pBB->edges[0].ip = (dword)start;
  116. }
  117. break;
  118. }
  119. }
  120. }
  121. std::vector<BB *>::iterator iter=heldBBs.begin();
  122. /* Convert list of BBs into a graph */
  123. for (; iter!=heldBBs.end(); ++iter)
  124. {
  125. pBB = *iter;
  126. for (i = 0; i < pBB->numOutEdges; i++)
  127. {
  128. ip = pBB->edges[i].ip;
  129. if (ip >= SYNTHESIZED_MIN)
  130. fatalError (INVALID_SYNTHETIC_BB);
  131. else
  132. {
  133. auto iter2=std::find_if(heldBBs.begin(),heldBBs.end(),
  134. [ip](BB *psBB)->bool {return psBB->start==ip;});
  135. if(iter2==heldBBs.end())
  136. fatalError(NO_BB, ip, name);
  137. psBB = *iter2;
  138. pBB->edges[i].BBptr = psBB;
  139. psBB->numInEdges++;
  140. }
  141. }
  142. }
  143. }
  144. void Function::markImpure()
  145. {
  146. SYM * psym;
  147. for (int i = 0; i < Icode.GetNumIcodes(); i++)
  148. {
  149. if (Icode.GetLlFlag(i) & (SYM_USE | SYM_DEF))
  150. {
  151. psym = &symtab.sym[Icode.GetIcode(i)->ic.ll.caseTbl.numEntries];
  152. for (int c = (Int)psym->label; c < (Int)psym->label+psym->size; c++)
  153. {
  154. if (BITMAP(c, BM_CODE))
  155. {
  156. Icode.SetLlFlag(i, IMPURE);
  157. flg |= IMPURE;
  158. break;
  159. }
  160. }
  161. }
  162. }
  163. }
  164. /*****************************************************************************
  165. * newBB - Allocate new BB and link to end of list
  166. *****************************************************************************/
  167. /*****************************************************************************
  168. * freeCFG - Deallocates a cfg
  169. ****************************************************************************/
  170. void Function::freeCFG()
  171. {
  172. std::for_each(heldBBs.begin(),heldBBs.end(),[](BB *p)->void {delete p;});
  173. }
  174. /*****************************************************************************
  175. * compressCFG - Remove redundancies and add in-edge information
  176. ****************************************************************************/
  177. void Function::compressCFG()
  178. {
  179. BB * pBB, *pNxt;
  180. Int ip, first=0, last, i;
  181. /* First pass over BB list removes redundant jumps of the form
  182. * (Un)Conditional -> Unconditional jump */
  183. std::vector<BB*>::iterator iter=cfg.begin();
  184. for (;iter!=cfg.end(); ++iter)
  185. {
  186. pBB = *iter;
  187. pBB->inEdges.resize(pBB->numInEdges,0);
  188. if (pBB->numInEdges != 0 && (pBB->nodeType == ONE_BRANCH || pBB->nodeType == TWO_BRANCH))
  189. for (i = 0; i < pBB->numOutEdges; i++)
  190. {
  191. ip = pBB->start + pBB->length - 1;
  192. pNxt = rmJMP(this, ip, pBB->edges[i].BBptr);
  193. if (pBB->numOutEdges) /* Might have been clobbered */
  194. {
  195. pBB->edges[i].BBptr = pNxt;
  196. Icode.SetImmediateOp(ip, (dword)pNxt->start);
  197. }
  198. }
  199. }
  200. /* Next is a depth-first traversal merging any FALL_NODE or
  201. * ONE_BRANCH that fall through to a node with that as their only
  202. * in-edge. */
  203. this->cfg.front()->mergeFallThrough(Icode);
  204. /* Remove redundant BBs created by the above compressions
  205. * and allocate in-edge arrays as required. */
  206. stats.numBBaft = stats.numBBbef;
  207. for(auto iter=cfg.begin(); iter!=cfg.end(); ++iter)
  208. {
  209. pBB = *iter;
  210. if (pBB->numInEdges == 0)
  211. {
  212. if (iter == cfg.begin()) /* Init it misses out on */
  213. pBB->index = UN_INIT;
  214. else
  215. {
  216. if (pBB->numOutEdges)
  217. pBB->edges.clear();
  218. delete pBB;
  219. stats.numBBaft--;
  220. }
  221. }
  222. else
  223. {
  224. pBB->inEdgeCount = pBB->numInEdges;
  225. }
  226. }
  227. /* Allocate storage for dfsLast[] array */
  228. numBBs = stats.numBBaft;
  229. dfsLast.resize(numBBs,0); // = (BB **)allocMem(numBBs * sizeof(BB *))
  230. /* Now do a dfs numbering traversal and fill in the inEdges[] array */
  231. last = numBBs - 1;
  232. cfg.front()->dfsNumbering(dfsLast, &first, &last);
  233. }
  234. /****************************************************************************
  235. * rmJMP - If BB addressed is just a JMP it is replaced with its target
  236. ***************************************************************************/
  237. static BB * rmJMP(Function * pProc, Int marker, BB * pBB)
  238. {
  239. marker += DFS_JMP;
  240. while (pBB->nodeType == ONE_BRANCH && pBB->length == 1) {
  241. if (pBB->traversed != marker) {
  242. pBB->traversed = marker;
  243. if (--pBB->numInEdges)
  244. pBB->edges[0].BBptr->numInEdges++;
  245. else
  246. {
  247. pProc->Icode.SetLlFlag(pBB->start, NO_CODE);
  248. pProc->Icode.SetLlInvalid(pBB->start, TRUE);
  249. }
  250. pBB = pBB->edges[0].BBptr;
  251. }
  252. else { /* We are going around in circles */
  253. pBB->nodeType = NOWHERE_NODE;
  254. pProc->Icode.GetIcode(pBB->start)->ic.ll.immed.op = (dword)pBB->start;
  255. pProc->Icode.SetImmediateOp(pBB->start, (dword)pBB->start);
  256. do {
  257. pBB = pBB->edges[0].BBptr;
  258. if (! --pBB->numInEdges)
  259. {
  260. pProc->Icode.SetLlFlag(pBB->start, NO_CODE);
  261. pProc->Icode.SetLlInvalid(pBB->start, TRUE);
  262. }
  263. } while (pBB->nodeType != NOWHERE_NODE);
  264. pBB->edges.clear();
  265. pBB->numOutEdges = 0;
  266. }
  267. }
  268. return pBB;
  269. }
  270. /*****************************************************************************
  271. * mergeFallThrough
  272. ****************************************************************************/
  273. void BB::mergeFallThrough( CIcodeRec &Icode)
  274. {
  275. BB * pChild;
  276. Int i, _ip;
  277. if (!this)
  278. {
  279. printf("mergeFallThrough on empty BB!\n");
  280. }
  281. while (nodeType == FALL_NODE || nodeType == ONE_BRANCH)
  282. {
  283. pChild = edges[0].BBptr;
  284. /* Jump to next instruction can always be removed */
  285. if (nodeType == ONE_BRANCH)
  286. {
  287. _ip = start + length;
  288. for (i = _ip; i < pChild->start && (Icode.GetLlFlag(i) & NO_CODE); i++);
  289. if (i != pChild->start)
  290. break;
  291. Icode.SetLlFlag(_ip - 1, NO_CODE);
  292. Icode.SetLlInvalid(_ip - 1, TRUE);
  293. nodeType = FALL_NODE;
  294. length--;
  295. }
  296. /* If there's no other edges into child can merge */
  297. if (pChild->numInEdges != 1)
  298. break;
  299. nodeType = pChild->nodeType;
  300. length = pChild->start + pChild->length - start;
  301. Icode.ClearLlFlag(pChild->start, TARGET);
  302. numOutEdges = pChild->numOutEdges;
  303. edges.swap(pChild->edges);
  304. pChild->numOutEdges = pChild->numInEdges = 0;
  305. pChild->edges.clear();
  306. }
  307. traversed = DFS_MERGE;
  308. /* Process all out edges recursively */
  309. for (i = 0; i < numOutEdges; i++)
  310. if (edges[i].BBptr->traversed != DFS_MERGE)
  311. edges[i].BBptr->mergeFallThrough(Icode);
  312. }
  313. /*****************************************************************************
  314. * dfsNumbering - Numbers nodes during first and last visits and determine
  315. * in-edges
  316. ****************************************************************************/
  317. void BB::dfsNumbering(std::vector<BB *> &dfsLast, Int *first, Int *last)
  318. {
  319. BB * pChild;
  320. byte i;
  321. traversed = DFS_NUM;
  322. dfsFirstNum = (*first)++;
  323. /* index is being used as an index to inEdges[]. */
  324. for (i = 0; i < numOutEdges; i++)
  325. {
  326. pChild = edges[i].BBptr;
  327. pChild->inEdges[pChild->index++] = this;
  328. /* Is this the last visit? */
  329. if (pChild->index == pChild->numInEdges)
  330. pChild->index = UN_INIT;
  331. if (pChild->traversed != DFS_NUM)
  332. pChild->dfsNumbering(dfsLast, first, last);
  333. }
  334. dfsLastNum = *last;
  335. dfsLast[(*last)--] = this;
  336. }