proplong.cpp 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530
  1. /**************************************************************************
  2. * File : propLong.c
  3. * Purpose: propagate the value of long variables (local variables and
  4. * registers) along the graph. Structure the graph in this way.
  5. * (C) Cristina Cifuentes
  6. **************************************************************************/
  7. #include <string.h>
  8. #include <memory.h>
  9. #include <cassert>
  10. #include <algorithm>
  11. #include "dcc.h"
  12. static boolT isJCond (llIcode opcode)
  13. /* Returns whether the given icode opcode is within the range of valid
  14. * high-level conditional jump icodes (iJB..iJG) */
  15. {
  16. if ((opcode >= iJB) && (opcode <= iJG))
  17. return true;
  18. return false;
  19. }
  20. /* Returns whether the conditions for a 2-3 long variable are satisfied */
  21. static boolT isLong23 (Int i, BB * pbb, ICODE * icode, Int *off, Int *arc)
  22. {
  23. BB * t, * e, * obb2;
  24. if (pbb->nodeType != TWO_BRANCH)
  25. return false;
  26. t = pbb->edges[THEN].BBptr;
  27. e = pbb->edges[ELSE].BBptr;
  28. /* Check along the THEN path */
  29. if ((t->length == 1) && (t->nodeType == TWO_BRANCH) && (t->inEdges.size() == 1))
  30. {
  31. obb2 = t->edges[THEN].BBptr;
  32. if ((obb2->length == 2) && (obb2->nodeType == TWO_BRANCH) &&
  33. (icode[obb2->start].ic.ll.opcode == iCMP))
  34. {
  35. *off = obb2->start - i;
  36. *arc = THEN;
  37. return true;
  38. }
  39. }
  40. /* Check along the ELSE path */
  41. else if ((e->length == 1) && (e->nodeType == TWO_BRANCH) &&
  42. (e->inEdges.size() == 1))
  43. {
  44. obb2 = e->edges[THEN].BBptr;
  45. if ((obb2->length == 2) && (obb2->nodeType == TWO_BRANCH) &&
  46. (icode[obb2->start].ic.ll.opcode == iCMP))
  47. {
  48. *off = obb2->start - i;
  49. *arc = ELSE;
  50. return true;
  51. }
  52. }
  53. return false;
  54. }
  55. /* Returns whether the conditions for a 2-2 long variable are satisfied */
  56. static boolT isLong22 (ICODE * pIcode, ICODE * pEnd, Int *off)
  57. {
  58. if (((pIcode+2) < pEnd) && ((pIcode+2)->ic.ll.opcode == iCMP) &&
  59. (isJCond ((pIcode+1)->ic.ll.opcode)) &&
  60. (isJCond ((pIcode+3)->ic.ll.opcode)))
  61. {
  62. *off = 2;
  63. return true;
  64. }
  65. return false;
  66. }
  67. /* Creates a long conditional <=, >=, <, or > at (pIcode+1).
  68. * Removes excess nodes from the graph by flagging them, and updates
  69. * the new edges for the remaining nodes. */
  70. static void longJCond23 (COND_EXPR *rhs, COND_EXPR *lhs, ICODE * pIcode,
  71. Int *idx, Function * pProc, Int arc, Int off)
  72. { Int j;
  73. BB * pbb, * obb1, * obb2, * tbb;
  74. if (arc == THEN)
  75. {
  76. /* Find intermediate basic blocks and target block */
  77. pbb = pIcode->inBB;
  78. obb1 = pbb->edges[THEN].BBptr;
  79. obb2 = obb1->edges[THEN].BBptr;
  80. tbb = obb2->edges[THEN].BBptr;
  81. /* Modify out edge of header basic block */
  82. pbb->edges[THEN].BBptr = tbb;
  83. /* Modify in edges of target basic block */
  84. auto newlast=std::remove_if(tbb->inEdges.begin(),tbb->inEdges.end(),
  85. [obb1,obb2](BB *b) -> bool
  86. {
  87. return (b==obb1) || (b==obb2);
  88. }
  89. );
  90. tbb->inEdges.erase(newlast,tbb->inEdges.end());
  91. tbb->inEdges.push_back(pbb); /* looses 2 arcs, gains 1 arc */
  92. /* Modify in edges of the ELSE basic block */
  93. tbb = pbb->edges[ELSE].BBptr;
  94. auto iter=std::find(tbb->inEdges.begin(),tbb->inEdges.end(),obb2);
  95. assert(iter!=tbb->inEdges.end());
  96. tbb->inEdges.erase(iter); /* looses 1 arc */
  97. /* Update icode index */
  98. (*idx) += 5;
  99. }
  100. else /* ELSE arc */
  101. {
  102. /* Find intermediate basic blocks and target block */
  103. pbb = pIcode->inBB;
  104. obb1 = pbb->edges[ELSE].BBptr;
  105. obb2 = obb1->edges[THEN].BBptr;
  106. tbb = obb2->edges[THEN].BBptr;
  107. /* Modify in edges of target basic block */
  108. auto iter=std::find(tbb->inEdges.begin(),tbb->inEdges.end(),obb2);
  109. assert(iter!=tbb->inEdges.end());
  110. tbb->inEdges.erase(iter); /* looses 1 arc */
  111. /* Modify in edges of the ELSE basic block */
  112. tbb = obb2->edges[ELSE].BBptr;
  113. auto newlast=std::remove_if(tbb->inEdges.begin(),tbb->inEdges.end(),
  114. [obb1,obb2](BB *b) -> bool
  115. {
  116. return (b==obb1) || (b==obb2);
  117. }
  118. );
  119. tbb->inEdges.erase(newlast,tbb->inEdges.end());
  120. tbb->inEdges.push_back(pbb); /* looses 2 arcs, gains 1 arc */
  121. /* Modify out edge of header basic block */
  122. pbb->edges[ELSE].BBptr = tbb;
  123. /* Update icode index */
  124. (*idx) += 2;
  125. }
  126. /* Create new HLI_JCOND and condition */
  127. lhs = COND_EXPR::boolOp (lhs, rhs, condOpJCond[(pIcode+off+1)->ic.ll.opcode-iJB]);
  128. (pIcode+1)->setJCond(lhs);
  129. (pIcode+1)->copyDU(*pIcode, eUSE, eUSE);
  130. (pIcode+1)->du.use |= (pIcode+off)->du.use;
  131. /* Update statistics */
  132. obb1->flg |= INVALID_BB;
  133. obb2->flg |= INVALID_BB;
  134. stats.numBBaft -= 2;
  135. pIcode->invalidate();
  136. pProc->Icode.GetIcode(obb1->start)->invalidate();
  137. pProc->Icode.GetIcode(obb2->start)->invalidate();
  138. pProc->Icode.GetIcode(obb2->start+1)->invalidate();
  139. }
  140. /* Creates a long conditional equality or inequality at (pIcode+1).
  141. * Removes excess nodes from the graph by flagging them, and updates
  142. * the new edges for the remaining nodes. */
  143. static void longJCond22 (COND_EXPR *rhs, COND_EXPR *lhs, ICODE * pIcode,
  144. Int *idx)
  145. {
  146. Int j;
  147. BB * pbb, * obb1, * tbb;
  148. /* Form conditional expression */
  149. lhs = COND_EXPR::boolOp (lhs, rhs, condOpJCond[(pIcode+3)->ic.ll.opcode - iJB]);
  150. (pIcode+1)->setJCond(lhs);
  151. (pIcode+1)->copyDU (*pIcode, eUSE, eUSE);
  152. (pIcode+1)->du.use |= (pIcode+2)->du.use;
  153. /* Adjust outEdges[0] to the new target basic block */
  154. pbb = pIcode->inBB;
  155. if ((pbb->start + pbb->length - 1) == (*idx + 1))
  156. {
  157. /* Find intermediate and target basic blocks */
  158. obb1 = pbb->edges[THEN].BBptr;
  159. tbb = obb1->edges[THEN].BBptr;
  160. /* Modify THEN out edge of header basic block */
  161. pbb->edges[THEN].BBptr = tbb;
  162. /* Modify in edges of target basic block */
  163. auto iter=std::find(tbb->inEdges.begin(),tbb->inEdges.end(),obb1);
  164. assert(iter!=tbb->inEdges.end());
  165. tbb->inEdges.erase(iter);
  166. if ((pIcode+3)->ic.ll.opcode != iJE)
  167. tbb->inEdges.push_back(pbb); /* iJNE => replace arc */
  168. /* Modify ELSE out edge of header basic block */
  169. tbb = obb1->edges[ELSE].BBptr;
  170. pbb->edges[ELSE].BBptr = tbb;
  171. iter=std::find(tbb->inEdges.begin(),tbb->inEdges.end(),obb1);
  172. assert(iter!=tbb->inEdges.end());
  173. tbb->inEdges.erase(iter);
  174. if ((pIcode+3)->ic.ll.opcode == iJE) /* replace */
  175. tbb->inEdges.push_back(pbb);
  176. // else
  177. // tbb->numInEdges--; /* iJNE => looses 1 arc */
  178. /* Update statistics */
  179. obb1->flg |= INVALID_BB;
  180. stats.numBBaft--;
  181. }
  182. pIcode->invalidate();
  183. (pIcode+2)->invalidate();
  184. (pIcode+3)->invalidate();
  185. (*idx) += 4;
  186. }
  187. /* Propagates TYPE_LONG_(UN)SIGN icode information to the current pIcode
  188. * Pointer.
  189. * Arguments: i : index into the local identifier table
  190. * pLocId: ptr to the long local identifier
  191. * pProc : ptr to current procedure's record. */
  192. void Function::propLongStk (Int i, ID *pLocId)
  193. {
  194. Int idx, off, arc;
  195. COND_EXPR *lhs, *rhs; /* Pointers to left and right hand expression */
  196. ICODE * pIcode, * pEnd;
  197. /* Check all icodes for offHi:offLo */
  198. pEnd = this->Icode.GetIcode(this->Icode.GetNumIcodes() -1);
  199. for (idx = 0; idx < (this->Icode.GetNumIcodes() - 1); idx++)
  200. {
  201. pIcode = this->Icode.GetIcode(idx);
  202. if ((pIcode->type == HIGH_LEVEL) || (pIcode->invalid == TRUE))
  203. continue;
  204. if (pIcode->ic.ll.opcode == (pIcode+1)->ic.ll.opcode)
  205. {
  206. switch (pIcode->ic.ll.opcode) {
  207. case iMOV:
  208. if (checkLongEq (pLocId->id.longStkId, pIcode, i, idx, this,
  209. &rhs, &lhs, 1) == TRUE)
  210. {
  211. pIcode->setAsgn(lhs, rhs);
  212. (pIcode+1)->invalidate();
  213. idx++;
  214. }
  215. break;
  216. case iAND: case iOR: case iXOR:
  217. if (checkLongEq (pLocId->id.longStkId, pIcode, i, idx, this,
  218. &rhs, &lhs, 1) == TRUE)
  219. {
  220. switch (pIcode->ic.ll.opcode) {
  221. case iAND: rhs = COND_EXPR::boolOp (lhs, rhs, AND);
  222. break;
  223. case iOR: rhs = COND_EXPR::boolOp (lhs, rhs, OR);
  224. break;
  225. case iXOR: rhs = COND_EXPR::boolOp (lhs, rhs, XOR);
  226. break;
  227. }
  228. pIcode->setAsgn(lhs, rhs);
  229. (pIcode+1)->invalidate();
  230. idx++;
  231. }
  232. break;
  233. case iPUSH:
  234. if (checkLongEq (pLocId->id.longStkId, pIcode, i, idx, this,
  235. &rhs, &lhs, 1) == TRUE)
  236. {
  237. pIcode->setUnary( HLI_PUSH, lhs);
  238. (pIcode+1)->invalidate();
  239. idx++;
  240. }
  241. break;
  242. } /*eos*/
  243. }
  244. /* Check long conditional (i.e. 2 CMPs and 3 branches */
  245. else if ((pIcode->ic.ll.opcode == iCMP) && (isLong23 (idx, pIcode->inBB, this->Icode.GetFirstIcode(),&off, &arc)))
  246. {
  247. if (checkLongEq (pLocId->id.longStkId, pIcode, i, idx, this, &rhs, &lhs, off) == TRUE)
  248. longJCond23 (rhs, lhs, pIcode, &idx, this, arc, off);
  249. }
  250. /* Check for long conditional equality or inequality. This requires
  251. * 2 CMPs and 2 branches */
  252. else if ((pIcode->ic.ll.opcode == iCMP) &&
  253. isLong22 (pIcode, pEnd, &off))
  254. {
  255. if (checkLongEq (pLocId->id.longStkId, pIcode, i, idx, this,
  256. &rhs, &lhs, off) == TRUE)
  257. longJCond22 (rhs, lhs, pIcode, &idx);
  258. }
  259. }
  260. }
  261. /* Finds the definition of the long register pointed to by pLocId, and
  262. * transforms that instruction into a HIGH_LEVEL icode instruction.
  263. * Arguments: i : index into the local identifier table
  264. * pLocId: ptr to the long local identifier
  265. * pProc : ptr to current procedure's record. */
  266. void Function::propLongReg (Int i, ID *pLocId)
  267. {
  268. COND_EXPR *lhs, *rhs;
  269. Int idx, j, off, arc;
  270. ICODE * pIcode, * pEnd;
  271. ICODEMEM * pmH,* pmL; /* Pointers to dst LOW_LEVEL icodes */
  272. /* Process all definitions/uses of long registers at an icode position */
  273. pEnd = this->Icode.GetIcode(this->Icode.GetNumIcodes() -1);
  274. for (j = 0; j < pLocId->idx.size(); j++)
  275. {
  276. /* Check backwards for a definition of this long register */
  277. for (idx = pLocId->idx[j] - 1; idx > 0 ; idx--)
  278. {
  279. pIcode = this->Icode.GetIcode(idx-1);
  280. if ((pIcode->type == HIGH_LEVEL) || (pIcode->invalid == TRUE))
  281. continue;
  282. if (pIcode->ic.ll.opcode == (pIcode+1)->ic.ll.opcode)
  283. switch (pIcode->ic.ll.opcode)
  284. {
  285. case iMOV:
  286. pmH = &pIcode->ic.ll.dst;
  287. pmL = &(pIcode+1)->ic.ll.dst;
  288. if ((pLocId->id.longId.h == pmH->regi) && (pLocId->id.longId.l == pmL->regi))
  289. {
  290. lhs = COND_EXPR::idLongIdx (i);
  291. this->localId.id_arr[i].idx.push_back(idx-1);
  292. pIcode->setRegDU( pmL->regi, eDEF);
  293. rhs = COND_EXPR::idLong (&this->localId, SRC, pIcode, HIGH_FIRST, idx, eUSE, 1);
  294. pIcode->setAsgn(lhs, rhs);
  295. (pIcode+1)->invalidate();
  296. idx = 0; /* to exit the loop */
  297. }
  298. break;
  299. case iPOP:
  300. pmH = &(pIcode+1)->ic.ll.dst;
  301. pmL = &pIcode->ic.ll.dst;
  302. if ((pLocId->id.longId.h == pmH->regi) && (pLocId->id.longId.l == pmL->regi))
  303. {
  304. lhs = COND_EXPR::idLongIdx (i);
  305. pIcode->setRegDU( pmH->regi, eDEF);
  306. pIcode->setUnary(HLI_POP, lhs);
  307. (pIcode+1)->invalidate();
  308. idx = 0; /* to exit the loop */
  309. }
  310. break;
  311. /**** others missing ***/
  312. case iAND: case iOR: case iXOR:
  313. pmL = &pIcode->ic.ll.dst;
  314. pmH = &(pIcode+1)->ic.ll.dst;
  315. if ((pLocId->id.longId.h == pmH->regi) && (pLocId->id.longId.l == pmL->regi))
  316. {
  317. lhs = COND_EXPR::idLongIdx (i);
  318. pIcode->setRegDU( pmH->regi, USE_DEF);
  319. rhs = COND_EXPR::idLong (&this->localId, SRC, pIcode, LOW_FIRST, idx, eUSE, 1);
  320. switch (pIcode->ic.ll.opcode) {
  321. case iAND: rhs = COND_EXPR::boolOp (lhs, rhs, AND);
  322. break;
  323. case iOR:
  324. rhs = COND_EXPR::boolOp (lhs, rhs, OR);
  325. break;
  326. case iXOR: rhs = COND_EXPR::boolOp (lhs, rhs, XOR);
  327. break;
  328. } /* eos */
  329. pIcode->setAsgn(lhs, rhs);
  330. (pIcode+1)->invalidate();
  331. idx = 0;
  332. }
  333. break;
  334. } /* eos */
  335. }
  336. /* If no definition backwards, check forward for a use of this long reg */
  337. if (idx <= 0)
  338. for (idx = pLocId->idx[j] + 1; idx < this->Icode.GetNumIcodes() - 1; idx++)
  339. {
  340. pIcode = this->Icode.GetIcode(idx);
  341. if ((pIcode->type == HIGH_LEVEL) || (pIcode->invalid == TRUE))
  342. continue;
  343. if (pIcode->ic.ll.opcode == (pIcode+1)->ic.ll.opcode)
  344. switch (pIcode->ic.ll.opcode) {
  345. case iMOV:
  346. if ((pLocId->id.longId.h == pIcode->ic.ll.src.regi) &&
  347. (pLocId->id.longId.l == (pIcode+1)->ic.ll.src.regi))
  348. {
  349. rhs = COND_EXPR::idLongIdx (i);
  350. pIcode->setRegDU( (pIcode+1)->ic.ll.src.regi, eUSE);
  351. lhs = COND_EXPR::idLong (&this->localId, DST, pIcode,
  352. HIGH_FIRST, idx, eDEF, 1);
  353. pIcode->setAsgn(lhs, rhs);
  354. (pIcode+1)->invalidate();
  355. idx = this->Icode.GetNumIcodes(); /* to exit the loop */
  356. }
  357. break;
  358. case iPUSH:
  359. if ((pLocId->id.longId.h == pIcode->ic.ll.src.regi) &&
  360. (pLocId->id.longId.l == (pIcode+1)->ic.ll.src.regi))
  361. {
  362. rhs = COND_EXPR::idLongIdx (i);
  363. pIcode->setRegDU( (pIcode+1)->ic.ll.src.regi, eUSE);
  364. pIcode->setUnary(HLI_PUSH, lhs);
  365. (pIcode+1)->invalidate();
  366. }
  367. idx = this->Icode.GetNumIcodes(); /* to exit the loop */
  368. break;
  369. /*** others missing ****/
  370. case iAND: case iOR: case iXOR:
  371. pmL = &pIcode->ic.ll.dst;
  372. pmH = &(pIcode+1)->ic.ll.dst;
  373. if ((pLocId->id.longId.h == pmH->regi) &&
  374. (pLocId->id.longId.l == pmL->regi))
  375. {
  376. lhs = COND_EXPR::idLongIdx (i);
  377. pIcode->setRegDU( pmH->regi, USE_DEF);
  378. rhs = COND_EXPR::idLong (&this->localId, SRC, pIcode,
  379. LOW_FIRST, idx, eUSE, 1);
  380. switch (pIcode->ic.ll.opcode) {
  381. case iAND: rhs = COND_EXPR::boolOp (lhs, rhs, AND);
  382. break;
  383. case iOR: rhs = COND_EXPR::boolOp (lhs, rhs, OR);
  384. break;
  385. case iXOR: rhs = COND_EXPR::boolOp (lhs, rhs, XOR);
  386. break;
  387. }
  388. pIcode->setAsgn(lhs, rhs);
  389. (pIcode+1)->invalidate();
  390. idx = 0;
  391. }
  392. break;
  393. } /* eos */
  394. /* Check long conditional (i.e. 2 CMPs and 3 branches */
  395. else if ((pIcode->ic.ll.opcode == iCMP) &&
  396. (isLong23 (idx, pIcode->inBB, this->Icode.GetFirstIcode(),
  397. &off, &arc)))
  398. {
  399. if (checkLongRegEq (pLocId->id.longId, pIcode, i, idx, this,
  400. &rhs, &lhs, off) == TRUE)
  401. longJCond23 (rhs, lhs, pIcode, &idx, this, arc, off);
  402. }
  403. /* Check for long conditional equality or inequality. This requires
  404. * 2 CMPs and 2 branches */
  405. else if ((pIcode->ic.ll.opcode == iCMP) &&
  406. (isLong22 (pIcode, pEnd, &off)))
  407. {
  408. if (checkLongRegEq (pLocId->id.longId, pIcode, i, idx, this,
  409. &rhs, &lhs, off) == TRUE)
  410. longJCond22 (rhs, lhs, pIcode, &idx);
  411. }
  412. /* Check for OR regH, regL
  413. * JX lab
  414. * => HLI_JCOND (regH:regL X 0) lab
  415. * This is better code than HLI_JCOND (HI(regH:regL) | LO(regH:regL)) */
  416. else if ((pIcode->ic.ll.opcode == iOR) && ((pIcode+1) < pEnd) &&
  417. (isJCond ((pIcode+1)->ic.ll.opcode)))
  418. {
  419. if ((pIcode->ic.ll.dst.regi == pLocId->id.longId.h) &&
  420. (pIcode->ic.ll.src.regi == pLocId->id.longId.l))
  421. {
  422. lhs = COND_EXPR::idLongIdx (i);
  423. rhs = COND_EXPR::idKte (0, 4); /* long 0 */
  424. lhs = COND_EXPR::boolOp (lhs, rhs,
  425. condOpJCond[(pIcode+1)->ic.ll.opcode - iJB]);
  426. (pIcode+1)->setJCond(lhs);
  427. (pIcode+1)->copyDU(*pIcode, eUSE, eUSE);
  428. pIcode->invalidate();
  429. }
  430. }
  431. } /* end for */
  432. } /* end for */
  433. }
  434. /* Propagates the long global address across all LOW_LEVEL icodes.
  435. * Transforms some LOW_LEVEL icodes into HIGH_LEVEL */
  436. void Function::propLongGlb (Int i, ID *pLocId)
  437. {
  438. printf("WARN: Function::propLongGlb not implemented");
  439. }
  440. /* Propagated identifier information, thus converting some LOW_LEVEL icodes
  441. * into HIGH_LEVEL icodes. */
  442. void Function::propLong()
  443. {
  444. Int i;
  445. ID *pLocId; /* Pointer to current local identifier */
  446. for (i = 0; i < localId.csym(); i++)
  447. {
  448. pLocId = &localId.id_arr[i];
  449. if ((pLocId->type==TYPE_LONG_SIGN) || (pLocId->type==TYPE_LONG_UNSIGN))
  450. {
  451. switch (pLocId->loc)
  452. {
  453. case STK_FRAME:
  454. propLongStk (i, pLocId);
  455. break;
  456. case REG_FRAME:
  457. propLongReg (i, pLocId);
  458. break;
  459. case GLB_FRAME:
  460. propLongGlb (i, pLocId);
  461. break;
  462. }
  463. }
  464. }
  465. }