BasicBlock.cpp 14 KB

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