BasicBlock.cpp 15 KB

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