graph.cpp 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399
  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. iICODE pIcode = Icode.begin();
  37. stats.numBBbef = stats.numBBaft = 0;
  38. for (ip = start = 0; pIcode!=Icode.end(); 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.size() &&
  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. {
  47. pBB=BB::Create(start, ip, NOWHERE_NODE, 0, this);
  48. }
  49. /* Only process icodes that have valid instructions */
  50. else if ((pIcode->ic.ll.flg & NO_CODE) != NO_CODE)
  51. {
  52. switch (pIcode->ic.ll.opcode) {
  53. case iJB: case iJBE: case iJAE: case iJA:
  54. case iJL: case iJLE: case iJGE: case iJG:
  55. case iJE: case iJNE: case iJS: case iJNS:
  56. case iJO: case iJNO: case iJP: case iJNP:
  57. case iJCXZ:
  58. pBB = BB::Create(start, ip, TWO_BRANCH, 2, this);
  59. CondJumps:
  60. start = ip + 1;
  61. pBB->edges[0].ip = (uint32_t)start;
  62. /* This is for jumps off into nowhere */
  63. if (pIcode->ic.ll.flg & NO_LABEL)
  64. {
  65. pBB->edges.pop_back();
  66. }
  67. else
  68. pBB->edges[1].ip = pIcode->ic.ll.src.op();
  69. break;
  70. case iLOOP: case iLOOPE: case iLOOPNE:
  71. pBB = BB::Create(start, ip, LOOP_NODE, 2, this);
  72. goto CondJumps;
  73. case iJMPF: case iJMP:
  74. if (pIcode->ic.ll.flg & SWITCH)
  75. {
  76. pBB = BB::Create(start, ip, MULTI_BRANCH, pIcode->ic.ll.caseTbl.numEntries, this);
  77. for (i = 0; i < pIcode->ic.ll.caseTbl.numEntries; i++)
  78. pBB->edges[i].ip = pIcode->ic.ll.caseTbl.entries[i];
  79. hasCase = TRUE;
  80. }
  81. else if ((pIcode->ic.ll.flg & (I | NO_LABEL)) == I)
  82. {
  83. pBB = BB::Create(start, ip, ONE_BRANCH, 1, this);
  84. pBB->edges[0].ip = pIcode->ic.ll.src.op();
  85. }
  86. else
  87. BB::Create(start, ip, NOWHERE_NODE, 0, this);
  88. start = ip + 1;
  89. break;
  90. case iCALLF: case iCALL:
  91. {
  92. Function * p = pIcode->ic.ll.src.proc.proc;
  93. if (p)
  94. i = ((p->flg) & TERMINATES) ? 0 : 1;
  95. else
  96. i = 1;
  97. pBB = BB::Create(start, ip, CALL_NODE, i, this);
  98. start = ip + 1;
  99. if (i)
  100. pBB->edges[0].ip = (uint32_t)start;
  101. }
  102. break;
  103. case iRET: case iRETF:
  104. BB::Create(start, ip, RETURN_NODE, 0, this);
  105. start = ip + 1;
  106. break;
  107. default:
  108. /* Check for exit to DOS */
  109. iICODE next1=++iICODE(pIcode);
  110. if (pIcode->ic.ll.flg & TERMINATES)
  111. {
  112. pBB = BB::Create(start, ip, TERMINATE_NODE, 0, this);
  113. start = ip + 1;
  114. }
  115. /* Check for a fall through */
  116. else if (next1 != Icode.end())
  117. {
  118. assert(next1->loc_ip==ip+1);
  119. if (next1->ic.ll.flg & (TARGET | CASE))
  120. {
  121. pBB = BB::Create(start, ip, FALL_NODE, 1, this);
  122. start = ip + 1;
  123. pBB->edges[0].ip = (uint32_t)start;
  124. }
  125. }
  126. break;
  127. }
  128. }
  129. }
  130. auto iter=heldBBs.begin();
  131. /* Convert list of BBs into a graph */
  132. for (; iter!=heldBBs.end(); ++iter)
  133. {
  134. pBB = *iter;
  135. for (i = 0; i < pBB->edges.size(); i++)
  136. {
  137. ip = pBB->edges[i].ip;
  138. if (ip >= SYNTHESIZED_MIN)
  139. {
  140. fatalError (INVALID_SYNTHETIC_BB);
  141. return ;
  142. }
  143. auto iter2=std::find_if(heldBBs.begin(),heldBBs.end(),
  144. [ip](BB *psBB)->bool {return psBB->begin()==ip;});
  145. if(iter2==heldBBs.end())
  146. fatalError(NO_BB, ip, name.c_str());
  147. psBB = *iter2;
  148. pBB->edges[i].BBptr = psBB;
  149. psBB->inEdges.push_back(0);
  150. }
  151. }
  152. }
  153. void Function::markImpure()
  154. {
  155. SYM * psym;
  156. for(ICODE &icod : Icode)
  157. {
  158. if ( not icod.isLlFlag(SYM_USE | SYM_DEF))
  159. continue;
  160. psym = &symtab[icod.ic.ll.caseTbl.numEntries];
  161. for (int c = (int)psym->label; c < (int)psym->label+psym->size; c++)
  162. {
  163. if (BITMAP(c, BM_CODE))
  164. {
  165. icod.SetLlFlag(IMPURE);
  166. flg |= IMPURE;
  167. break;
  168. }
  169. }
  170. }
  171. }
  172. /*****************************************************************************
  173. * newBB - Allocate new BB and link to end of list
  174. *****************************************************************************/
  175. /*****************************************************************************
  176. * freeCFG - Deallocates a cfg
  177. ****************************************************************************/
  178. void Function::freeCFG()
  179. {
  180. for(BB *p : heldBBs)
  181. delete p;
  182. }
  183. /*****************************************************************************
  184. * compressCFG - Remove redundancies and add in-edge information
  185. ****************************************************************************/
  186. void Function::compressCFG()
  187. {
  188. BB * pBB, *pNxt;
  189. int ip, first=0, last, i;
  190. /* First pass over BB list removes redundant jumps of the form
  191. * (Un)Conditional -> Unconditional jump */
  192. auto iter=m_cfg.begin();
  193. for (;iter!=m_cfg.end(); ++iter)
  194. {
  195. pBB = *iter;
  196. if(pBB->inEdges.empty() || (pBB->nodeType != ONE_BRANCH && pBB->nodeType != TWO_BRANCH))
  197. continue;
  198. for (i = 0; i < pBB->edges.size(); i++)
  199. {
  200. ip = pBB->rbegin();
  201. pNxt = pBB->edges[i].BBptr->rmJMP(ip, pBB->edges[i].BBptr);
  202. if (not pBB->edges.empty()) /* Might have been clobbered */
  203. {
  204. pBB->edges[i].BBptr = pNxt;
  205. assert(pBB->back().loc_ip==ip);
  206. pBB->back().SetImmediateOp((uint32_t)pNxt->begin());
  207. //Icode[ip].SetImmediateOp((uint32_t)pNxt->begin());
  208. }
  209. }
  210. }
  211. /* Next is a depth-first traversal merging any FALL_NODE or
  212. * ONE_BRANCH that fall through to a node with that as their only
  213. * in-edge. */
  214. m_cfg.front()->mergeFallThrough(Icode);
  215. /* Remove redundant BBs created by the above compressions
  216. * and allocate in-edge arrays as required. */
  217. stats.numBBaft = stats.numBBbef;
  218. for(auto iter=m_cfg.begin(); iter!=m_cfg.end(); ++iter)
  219. {
  220. pBB = *iter;
  221. if (pBB->inEdges.empty())
  222. {
  223. if (iter == m_cfg.begin()) /* Init it misses out on */
  224. pBB->index = UN_INIT;
  225. else
  226. {
  227. delete pBB;
  228. stats.numBBaft--;
  229. }
  230. }
  231. else
  232. {
  233. pBB->inEdgeCount = pBB->inEdges.size();
  234. }
  235. }
  236. /* Allocate storage for dfsLast[] array */
  237. numBBs = stats.numBBaft;
  238. m_dfsLast.resize(numBBs,0); // = (BB **)allocMem(numBBs * sizeof(BB *))
  239. /* Now do a dfs numbering traversal and fill in the inEdges[] array */
  240. last = numBBs - 1;
  241. m_cfg.front()->dfsNumbering(m_dfsLast, &first, &last);
  242. }
  243. /****************************************************************************
  244. * rmJMP - If BB addressed is just a JMP it is replaced with its target
  245. ***************************************************************************/
  246. BB *BB::rmJMP(int marker, BB * pBB)
  247. {
  248. marker += DFS_JMP;
  249. while (pBB->nodeType == ONE_BRANCH && pBB->size() == 1)
  250. {
  251. if (pBB->traversed != marker)
  252. {
  253. pBB->traversed = marker;
  254. pBB->inEdges.pop_back();
  255. if (not pBB->inEdges.empty())
  256. {
  257. pBB->edges[0].BBptr->inEdges.push_back(0);
  258. }
  259. else
  260. {
  261. pBB->front().SetLlFlag(NO_CODE);
  262. pBB->front().invalidate(); //pProc->Icode.SetLlInvalid(pBB->begin(), TRUE);
  263. }
  264. pBB = pBB->edges[0].BBptr;
  265. }
  266. else
  267. {
  268. /* We are going around in circles */
  269. pBB->nodeType = NOWHERE_NODE;
  270. pBB->front().ic.ll.src.SetImmediateOp(pBB->front().loc_ip);
  271. //pBB->front().ic.ll.src.immed.op = pBB->front().loc_ip;
  272. do {
  273. pBB = pBB->edges[0].BBptr;
  274. pBB->inEdges.pop_back(); // was --numInedges
  275. if (! pBB->inEdges.empty())
  276. {
  277. pBB->front().SetLlFlag(NO_CODE);
  278. pBB->front().invalidate();
  279. // pProc->Icode.SetLlFlag(pBB->start, NO_CODE);
  280. // pProc->Icode.SetLlInvalid(pBB->start, TRUE);
  281. }
  282. } while (pBB->nodeType != NOWHERE_NODE);
  283. pBB->edges.clear();
  284. }
  285. }
  286. return pBB;
  287. }
  288. /*****************************************************************************
  289. * mergeFallThrough
  290. ****************************************************************************/
  291. void BB::mergeFallThrough( CIcodeRec &Icode)
  292. {
  293. BB * pChild;
  294. int i;
  295. if (!this)
  296. {
  297. printf("mergeFallThrough on empty BB!\n");
  298. }
  299. while (nodeType == FALL_NODE || nodeType == ONE_BRANCH)
  300. {
  301. pChild = edges[0].BBptr;
  302. /* Jump to next instruction can always be removed */
  303. if (nodeType == ONE_BRANCH)
  304. {
  305. assert(Parent==pChild->Parent);
  306. if(back().loc_ip>pChild->front().loc_ip) // back edege
  307. break;
  308. auto iter=std::find_if(this->end2(),pChild->begin2(),[](ICODE &c)
  309. {return not c.isLlFlag(NO_CODE);});
  310. if (iter != pChild->begin2())
  311. break;
  312. back().SetLlFlag(NO_CODE);
  313. back().invalidate();
  314. nodeType = FALL_NODE;
  315. length--;
  316. }
  317. /* If there's no other edges into child can merge */
  318. if (pChild->inEdges.size() != 1)
  319. break;
  320. nodeType = pChild->nodeType;
  321. length = (pChild->start - start) + pChild->length ;
  322. pChild->front().ClrLlFlag(TARGET);
  323. edges.swap(pChild->edges);
  324. pChild->inEdges.clear();
  325. pChild->edges.clear();
  326. }
  327. traversed = DFS_MERGE;
  328. /* Process all out edges recursively */
  329. for (i = 0; i < edges.size(); i++)
  330. if (edges[i].BBptr->traversed != DFS_MERGE)
  331. edges[i].BBptr->mergeFallThrough(Icode);
  332. }
  333. /*****************************************************************************
  334. * dfsNumbering - Numbers nodes during first and last visits and determine
  335. * in-edges
  336. ****************************************************************************/
  337. void BB::dfsNumbering(std::vector<BB *> &dfsLast, int *first, int *last)
  338. {
  339. BB * pChild;
  340. traversed = DFS_NUM;
  341. dfsFirstNum = (*first)++;
  342. /* index is being used as an index to inEdges[]. */
  343. // for (i = 0; i < edges.size(); i++)
  344. for (auto edge : edges)
  345. {
  346. pChild = edge.BBptr;
  347. pChild->inEdges[pChild->index++] = this;
  348. /* Is this the last visit? */
  349. if (pChild->index == pChild->inEdges.size())
  350. pChild->index = UN_INIT;
  351. if (pChild->traversed != DFS_NUM)
  352. pChild->dfsNumbering(dfsLast, first, last);
  353. }
  354. dfsLastNum = *last;
  355. dfsLast[(*last)--] = this;
  356. }