BasicBlock.cpp 15 KB

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