BasicBlock.cpp 13 KB

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