graph.cpp 13 KB

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