proplong.cpp 21 KB

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