graph.cpp 13 KB

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