BasicBlock.cpp 14 KB

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