BasicBlock.cpp 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439
  1. #include "BasicBlock.h"
  2. #include "msvc_fixes.h"
  3. #include "Procedure.h"
  4. #include "dcc.h"
  5. #include "msvc_fixes.h"
  6. #include <QtCore/QTextStream>
  7. #include <cassert>
  8. #include <string>
  9. #include <boost/range/rbegin.hpp>
  10. #include <boost/range/rend.hpp>
  11. #include <boost/range/adaptors.hpp>
  12. using namespace std;
  13. using namespace boost;
  14. BB *BB::Create(void */*ctx*/, const string &/*s*/, Function *parent, BB */*insertBefore*/)
  15. {
  16. BB *pnewBB = new BB;
  17. pnewBB->Parent = parent;
  18. return pnewBB;
  19. }
  20. /**
  21. * @arg start - basic block starts here, might be parent->Icode.end()
  22. * @arg fin - last of basic block's instructions
  23. */
  24. BB *BB::Create(const rCODE &r,eBBKind _nodeType, Function *parent)
  25. {
  26. BB* pnewBB;
  27. pnewBB = new BB;
  28. pnewBB->nodeType = _nodeType; /* Initialise */
  29. pnewBB->immedDom = NO_DOM;
  30. pnewBB->loopHead = pnewBB->caseHead = pnewBB->caseTail =
  31. pnewBB->latchNode= pnewBB->loopFollow = NO_NODE;
  32. pnewBB->instructions = r;
  33. /* Mark the basic block to which the icodes belong to, but only for
  34. * real code basic blocks (ie. not interval bbs) */
  35. if(parent)
  36. {
  37. int addr = pnewBB->begin()->loc_ip;
  38. //setInBB should automatically handle if our range is empty
  39. parent->Icode.SetInBB(pnewBB->instructions, pnewBB);
  40. assert(parent->m_ip_to_bb.find(addr)==parent->m_ip_to_bb.end());
  41. parent->m_ip_to_bb[addr] = pnewBB;
  42. parent->m_actual_cfg.push_back(pnewBB);
  43. pnewBB->Parent = parent;
  44. if ( r.begin() != parent->Icode.end() ) /* Only for code BB's */
  45. stats.numBBbef++;
  46. }
  47. return pnewBB;
  48. }
  49. BB *BB::CreateIntervalBB(Function *parent)
  50. {
  51. iICODE endOfParent = parent->Icode.end();
  52. return Create(make_iterator_range(endOfParent,endOfParent),INTERVAL_NODE,nullptr);
  53. }
  54. static const char *const s_nodeType[] = {"branch", "if", "case", "fall", "return", "call",
  55. "loop", "repeat", "interval", "cycleHead",
  56. "caseHead", "terminate",
  57. "nowhere" };
  58. static const char *const s_loopType[] = {"noLoop", "while", "repeat", "loop", "for"};
  59. void BB::display()
  60. {
  61. printf("\nnode type = %s, ", s_nodeType[nodeType]);
  62. printf("start = %d, length = %zd, #out edges = %zd\n", begin()->loc_ip, size(), edges.size());
  63. for (size_t i = 0; i < edges.size(); i++)
  64. {
  65. if(edges[i].BBptr==nullptr)
  66. printf(" outEdge[%2zd] = Unlinked out edge to %d\n",i, edges[i].ip);
  67. else
  68. printf(" outEdge[%2zd] = %d\n",i, edges[i].BBptr->begin()->loc_ip);
  69. }
  70. }
  71. /*****************************************************************************
  72. * displayDfs - Displays the CFG using a depth first traversal
  73. ****************************************************************************/
  74. void BB::displayDfs()
  75. {
  76. int i;
  77. assert(this);
  78. traversed = DFS_DISP;
  79. printf("node type = %s, ", s_nodeType[nodeType]);
  80. printf("start = %d, length = %zd, #in-edges = %zd, #out-edges = %zd\n",
  81. begin()->loc_ip, size(), inEdges.size(), edges.size());
  82. printf("dfsFirst = %d, dfsLast = %d, immed dom = %d\n",
  83. dfsFirstNum, dfsLastNum,
  84. immedDom == MAX ? -1 : immedDom);
  85. printf("loopType = %s, loopHead = %d, latchNode = %d, follow = %d\n",
  86. s_loopType[(int)loopType],
  87. loopHead == MAX ? -1 : loopHead,
  88. latchNode == MAX ? -1 : latchNode,
  89. loopFollow == MAX ? -1 : loopFollow);
  90. printf ("ifFollow = %d, caseHead = %d, caseTail = %d\n",
  91. ifFollow == MAX ? -1 : ifFollow,
  92. caseHead == MAX ? -1 : caseHead,
  93. caseTail == MAX ? -1 : caseTail);
  94. if (nodeType == INTERVAL_NODE)
  95. printf("corresponding interval = %d\n", correspInt->numInt);
  96. else
  97. {
  98. int edge_idx=0;
  99. for(BB *node : inEdges)
  100. {
  101. printf (" inEdge[%d] = %d\n", edge_idx, node->begin()->loc_ip);
  102. edge_idx++;
  103. }
  104. }
  105. /* Display out edges information */
  106. i=0;
  107. for(TYPEADR_TYPE &edg : edges)
  108. {
  109. if (nodeType == INTERVAL_NODE)
  110. printf(" outEdge[%d] = %d\n", i, edg.BBptr->correspInt->numInt);
  111. else
  112. printf(" outEdge[%d] = %d\n", i, edg.BBptr->begin()->loc_ip);
  113. ++i;
  114. }
  115. printf("----\n");
  116. /* Recursive call on successors of current node */
  117. for(TYPEADR_TYPE &pb : edges)
  118. {
  119. if (pb.BBptr->traversed != DFS_DISP)
  120. pb.BBptr->displayDfs();
  121. }
  122. }
  123. /** Recursive procedure that writes the code for the given procedure, pointed
  124. to by pBB.
  125. \param indLevel indentation level - used for formatting.
  126. \param numLoc: last # assigned to local variables
  127. */
  128. ICODE* BB::writeLoopHeader(int &indLevel, Function* pProc, int *numLoc, BB *&latch, bool &repCond)
  129. {
  130. if(loopType == eNodeHeaderType::NO_TYPE)
  131. return nullptr;
  132. latch = pProc->m_dfsLast[this->latchNode];
  133. QString ostr_contents;
  134. QTextStream ostr(&ostr_contents);
  135. ICODE* picode;
  136. switch (loopType)
  137. {
  138. case eNodeHeaderType::WHILE_TYPE:
  139. picode = &this->back();
  140. /* Check for error in while condition */
  141. if (picode->hl()->opcode != HLI_JCOND)
  142. reportError (WHILE_FAIL);
  143. /* Check if condition is more than 1 HL instruction */
  144. if (numHlIcodes > 1)
  145. {
  146. /* Write the code for this basic block */
  147. writeBB(ostr,indLevel, pProc, numLoc);
  148. repCond = true;
  149. }
  150. /* Condition needs to be inverted if the loop body is along
  151. * the THEN path of the header node */
  152. if (edges[ELSE].BBptr->dfsLastNum == loopFollow)
  153. {
  154. picode->hlU()->replaceExpr(picode->hl()->expr()->inverse());
  155. }
  156. {
  157. QString e=picode->hl()->expr()->walkCondExpr (pProc, numLoc);
  158. ostr << "\n"<<indentStr(indLevel)<<"while ("<<e<<") {\n";
  159. }
  160. picode->invalidate();
  161. break;
  162. case eNodeHeaderType::REPEAT_TYPE:
  163. ostr << "\n"<<indentStr(indLevel)<<"do {\n";
  164. picode = &latch->back();
  165. picode->invalidate();
  166. break;
  167. case eNodeHeaderType::ENDLESS_TYPE:
  168. ostr << "\n"<<indentStr(indLevel)<<"for (;;) {\n";
  169. picode = &latch->back();
  170. break;
  171. }
  172. ostr.flush();
  173. cCode.appendCode(ostr_contents);
  174. stats.numHLIcode += 1;
  175. indLevel++;
  176. return picode;
  177. }
  178. bool BB::isEndOfPath(int latch_node_idx) const
  179. {
  180. return nodeType == RETURN_NODE or nodeType == TERMINATE_NODE or
  181. nodeType == NOWHERE_NODE or dfsLastNum == latch_node_idx;
  182. }
  183. void BB::writeCode (int indLevel, Function * pProc , int *numLoc,int _latchNode, int _ifFollow)
  184. {
  185. int follow; /* ifFollow */
  186. BB * succ, *latch; /* Successor and latching node */
  187. ICODE * picode; /* Pointer to HLI_JCOND instruction */
  188. QString l; /* Pointer to HLI_JCOND expression */
  189. bool emptyThen, /* THEN clause is empty */
  190. repCond; /* Repeat condition for while() */
  191. /* Check if this basic block should be analysed */
  192. if ((_ifFollow != UN_INIT) and (this == pProc->m_dfsLast[_ifFollow]))
  193. return;
  194. if (wasTraversedAtLevel(DFS_ALPHA))
  195. return;
  196. traversed = DFS_ALPHA;
  197. /* Check for start of loop */
  198. repCond = false;
  199. latch = nullptr;
  200. picode=writeLoopHeader(indLevel, pProc, numLoc, latch, repCond);
  201. /* Write the code for this basic block */
  202. if (repCond == false)
  203. {
  204. QString ostr_contents;
  205. QTextStream ostr(&ostr_contents);
  206. writeBB(ostr,indLevel, pProc, numLoc);
  207. ostr.flush();
  208. cCode.appendCode(ostr_contents);
  209. }
  210. /* Check for end of path */
  211. if (isEndOfPath(_latchNode))
  212. return;
  213. /* Check type of loop/node and process code */
  214. if ( loopType!=eNodeHeaderType::NO_TYPE ) /* there is a loop */
  215. {
  216. assert(latch);
  217. if (this != latch) /* loop is over several bbs */
  218. {
  219. if (loopType == eNodeHeaderType::WHILE_TYPE)
  220. {
  221. succ = edges[THEN].BBptr;
  222. if (succ->dfsLastNum == loopFollow)
  223. succ = edges[ELSE].BBptr;
  224. }
  225. else
  226. succ = edges[0].BBptr;
  227. if (succ->traversed != DFS_ALPHA)
  228. succ->writeCode (indLevel, pProc, numLoc, latch->dfsLastNum,_ifFollow);
  229. else /* has been traversed so we need a goto */
  230. succ->front().ll()->emitGotoLabel (indLevel);
  231. }
  232. /* Loop epilogue: generate the loop trailer */
  233. indLevel--;
  234. if (loopType == eNodeHeaderType::WHILE_TYPE)
  235. {
  236. QString ostr_contents;
  237. QTextStream ostr(&ostr_contents);
  238. /* Check if there is need to repeat other statements involved
  239. * in while condition, then, emit the loop trailer */
  240. if (repCond)
  241. {
  242. writeBB(ostr,indLevel+1, pProc, numLoc);
  243. }
  244. ostr <<indentStr(indLevel)<< "} /* end of while */\n";
  245. ostr.flush();
  246. cCode.appendCode(ostr_contents);
  247. }
  248. else if (loopType == eNodeHeaderType::ENDLESS_TYPE)
  249. cCode.appendCode( "%s} /* end of loop */\n",indentStr(indLevel));
  250. else if (loopType == eNodeHeaderType::REPEAT_TYPE)
  251. {
  252. QString e = "//*failed*//";
  253. if (picode->hl()->opcode != HLI_JCOND)
  254. {
  255. reportError (REPEAT_FAIL);
  256. }
  257. else
  258. {
  259. e=picode->hl()->expr()->walkCondExpr (pProc, numLoc);
  260. }
  261. cCode.appendCode( "%s} while (%s);\n", indentStr(indLevel),qPrintable(e));
  262. }
  263. /* Recurse on the loop follow */
  264. if (loopFollow != MAX)
  265. {
  266. succ = pProc->m_dfsLast[loopFollow];
  267. if (succ->traversed != DFS_ALPHA)
  268. succ->writeCode (indLevel, pProc, numLoc, _latchNode, _ifFollow);
  269. else /* has been traversed so we need a goto */
  270. succ->front().ll()->emitGotoLabel (indLevel);
  271. }
  272. }
  273. else /* no loop, process nodeType of the graph */
  274. {
  275. if (nodeType == TWO_BRANCH) /* if-then[-else] */
  276. {
  277. stats.numHLIcode++;
  278. indLevel++;
  279. emptyThen = false;
  280. if (ifFollow != MAX) /* there is a follow */
  281. {
  282. /* process the THEN part */
  283. follow = ifFollow;
  284. succ = edges[THEN].BBptr;
  285. if (succ->traversed != DFS_ALPHA) /* not visited */
  286. {
  287. if (succ->dfsLastNum != follow) /* THEN part */
  288. {
  289. l = writeJcond ( *back().hl(), pProc, numLoc);
  290. cCode.appendCode( "\n%s%s", indentStr(indLevel-1), qPrintable(l));
  291. succ->writeCode (indLevel, pProc, numLoc, _latchNode,follow);
  292. }
  293. else /* empty THEN part => negate ELSE part */
  294. {
  295. l = writeJcondInv ( *back().hl(), pProc, numLoc);
  296. cCode.appendCode( "\n%s%s", indentStr(indLevel-1), qPrintable(l));
  297. edges[ELSE].BBptr->writeCode (indLevel, pProc, numLoc, _latchNode, follow);
  298. emptyThen = true;
  299. }
  300. }
  301. else /* already visited => emit label */
  302. succ->front().ll()->emitGotoLabel(indLevel);
  303. /* process the ELSE part */
  304. succ = edges[ELSE].BBptr;
  305. if (succ->traversed != DFS_ALPHA) /* not visited */
  306. {
  307. if (succ->dfsLastNum != follow) /* ELSE part */
  308. {
  309. cCode.appendCode( "%s}\n%selse {\n",
  310. indentStr(indLevel-1), indentStr(indLevel - 1));
  311. succ->writeCode (indLevel, pProc, numLoc, _latchNode, follow);
  312. }
  313. /* else (empty ELSE part) */
  314. }
  315. else if (not emptyThen) /* already visited => emit label */
  316. {
  317. cCode.appendCode( "%s}\n%selse {\n",
  318. indentStr(indLevel-1), indentStr(indLevel - 1));
  319. succ->front().ll()->emitGotoLabel (indLevel);
  320. }
  321. cCode.appendCode( "%s}\n", indentStr(--indLevel));
  322. /* Continue with the follow */
  323. succ = pProc->m_dfsLast[follow];
  324. if (succ->traversed != DFS_ALPHA)
  325. succ->writeCode (indLevel, pProc, numLoc, _latchNode,_ifFollow);
  326. }
  327. else /* no follow => if..then..else */
  328. {
  329. l = writeJcond ( *back().hl(), pProc, numLoc);
  330. cCode.appendCode( "%s%s", indentStr(indLevel-1), qPrintable(l));
  331. edges[THEN].BBptr->writeCode (indLevel, pProc, numLoc, _latchNode, _ifFollow);
  332. cCode.appendCode( "%s}\n%selse {\n", indentStr(indLevel-1), indentStr(indLevel - 1));
  333. edges[ELSE].BBptr->writeCode (indLevel, pProc, numLoc, _latchNode, _ifFollow);
  334. cCode.appendCode( "%s}\n", indentStr(--indLevel));
  335. }
  336. }
  337. else /* fall, call, 1w */
  338. {
  339. succ = edges[0].BBptr; /* fall-through edge */
  340. assert(succ->size()>0);
  341. if (succ->traversed != DFS_ALPHA)
  342. {
  343. succ->writeCode (indLevel, pProc,numLoc, _latchNode,_ifFollow);
  344. }
  345. }
  346. }
  347. }
  348. /* Writes the code for the current basic block.
  349. * Args: pBB: pointer to the current basic block.
  350. * Icode: pointer to the array of icodes for current procedure.
  351. * lev: indentation level - used for formatting. */
  352. void BB::writeBB(QTextStream &ostr,int lev, Function * pProc, int *numLoc)
  353. {
  354. /* Save the index into the code table in case there is a later goto
  355. * into this instruction (first instruction of the BB) */
  356. front().ll()->codeIdx = cCode.code.nextIdx();
  357. /* Generate code for each hlicode that is not a HLI_JCOND */
  358. for(ICODE &pHli : instructions)
  359. {
  360. if ((pHli.type == HIGH_LEVEL_ICODE) and ( pHli.valid() )) //TODO: use filtering range here.
  361. {
  362. QString line = pHli.hl()->write1HlIcode(pProc, numLoc);
  363. if (not line.isEmpty())
  364. {
  365. ostr<<indentStr(lev)<<line;
  366. stats.numHLIcode++;
  367. }
  368. if (option.verbose)
  369. pHli.writeDU();
  370. }
  371. }
  372. }
  373. iICODE BB::begin()
  374. {
  375. return instructions.begin();
  376. }
  377. iICODE BB::end() const
  378. {
  379. return instructions.end();
  380. }
  381. ICODE &BB::back()
  382. {
  383. return instructions.back();
  384. }
  385. size_t BB::size()
  386. {
  387. return distance(instructions.begin(),instructions.end());
  388. }
  389. ICODE &BB::front()
  390. {
  391. return instructions.front();
  392. }
  393. riICODE BB::rbegin()
  394. {
  395. return riICODE( instructions.end() );
  396. }
  397. riICODE BB::rend()
  398. {
  399. return riICODE( instructions.begin() );
  400. }