BasicBlock.cpp 15 KB

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