BasicBlock.cpp 14 KB

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