BasicBlock.cpp 14 KB

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