graph.cpp 14 KB

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