graph.cpp 15 KB

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