dataflow.cpp 49 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099
  1. /*****************************************************************************
  2. * Project: dcc
  3. * File: dataflow.c
  4. * Purpose: Data flow analysis module.
  5. * (C) Cristina Cifuentes
  6. ****************************************************************************/
  7. #include "dcc.h"
  8. #include <string.h>
  9. #include <stdio.h>
  10. /* Returns the index of the local variable or parameter at offset off, if it
  11. * is in the stack frame provided. */
  12. Int STKFRAME::getLocVar(Int off)
  13. { Int i;
  14. for (i = 0; i < sym.size(); i++)
  15. if (sym[i].off == off)
  16. break;
  17. return (i);
  18. }
  19. /* Returns a string with the source operand of Icode */
  20. static COND_EXPR *srcIdent (ICODE * Icode, Function * pProc, Int i, ICODE * duIcode, operDu du)
  21. {
  22. COND_EXPR *n;
  23. if (Icode->ic.ll.flg & I) /* immediate operand */
  24. {
  25. if (Icode->ic.ll.flg & B)
  26. n = COND_EXPR::idKte (Icode->ic.ll.immed.op, 1);
  27. else
  28. n = COND_EXPR::idKte (Icode->ic.ll.immed.op, 2);
  29. }
  30. else
  31. n = COND_EXPR::id (Icode, SRC, pProc, i, duIcode, du);
  32. return (n);
  33. }
  34. /* Returns the destination operand */
  35. static COND_EXPR *dstIdent (ICODE * pIcode, Function * pProc, Int i, ICODE * duIcode,
  36. operDu du)
  37. { COND_EXPR *n;
  38. n = COND_EXPR::id (pIcode, DST, pProc, i, duIcode, du);
  39. /** Is it needed? (pIcode->ic.ll.flg) & NO_SRC_B **/
  40. return (n);
  41. }
  42. /* Eliminates all condition codes and generates new hlIcode instructions */
  43. void Function::elimCondCodes ()
  44. {
  45. Int i,
  46. useAt, /* Index to instruction that used flag */
  47. defAt; /* Index to instruction that defined flag */
  48. byte use; /* Used flags bit vector */
  49. byte def; /* Defined flags bit vector */
  50. boolT notSup; /* Use/def combination not supported */
  51. COND_EXPR *rhs; /* Source operand */
  52. COND_EXPR *lhs; /* Destination operand */
  53. COND_EXPR *exp; /* Boolean expression */
  54. BB * pBB; /* Pointer to BBs in dfs last ordering */
  55. ICODE *prev; /* For extended basic blocks - previous icode inst */
  56. for (i = 0; i < numBBs; i++)
  57. {
  58. pBB = dfsLast[i];
  59. if (pBB->flg & INVALID_BB) continue; /* Do not process invalid BBs */
  60. for (useAt = pBB->start + pBB->length; useAt != pBB->start; useAt--)
  61. if ((Icode.GetIcode(useAt-1)->type == LOW_LEVEL) &&
  62. (Icode.GetIcode(useAt-1)->invalid == FALSE) &&
  63. (use = Icode.GetIcode(useAt-1)->ic.ll.flagDU.u))
  64. {
  65. /* Find definition within the same basic block */
  66. for (defAt = useAt-1; defAt != pBB->start; defAt--)
  67. {
  68. def = Icode.GetIcode(defAt-1)->ic.ll.flagDU.d;
  69. if ((use & def) == use)
  70. {
  71. notSup = FALSE;
  72. if ((Icode.GetLlOpcode(useAt-1) >= iJB) &&
  73. (Icode.GetLlOpcode(useAt-1) <= iJNS))
  74. {
  75. switch (Icode.GetLlOpcode(defAt-1))
  76. {
  77. case iCMP:
  78. rhs = srcIdent (Icode.GetIcode(defAt-1),
  79. this, defAt-1,
  80. Icode.GetIcode(useAt-1), eUSE);
  81. lhs = dstIdent (Icode.GetIcode(defAt-1),
  82. this, defAt-1,
  83. Icode.GetIcode(useAt-1), eUSE);
  84. break;
  85. case iOR:
  86. lhs = Icode.GetIcode(defAt-1)->ic.hl.oper.asgn.lhs->clone();
  87. Icode[useAt-1].copyDU(Icode[defAt-1], eUSE, eDEF);
  88. if (Icode.GetLlFlag(defAt-1) & B)
  89. rhs = COND_EXPR::idKte (0, 1);
  90. else
  91. rhs = COND_EXPR::idKte (0, 2);
  92. break;
  93. case iTEST:
  94. rhs = srcIdent (Icode.GetIcode(defAt-1),
  95. this, defAt-1,
  96. Icode.GetIcode(useAt-1), eUSE);
  97. lhs = dstIdent (Icode.GetIcode(defAt-1),
  98. this, defAt-1,
  99. Icode.GetIcode(useAt-1), eUSE);
  100. lhs = COND_EXPR::boolOp (lhs, rhs, AND);
  101. if (Icode.GetLlFlag(defAt-1) & B)
  102. rhs = COND_EXPR::idKte (0, 1);
  103. else
  104. rhs = COND_EXPR::idKte (0, 2);
  105. break;
  106. default:
  107. notSup = TRUE;
  108. reportError (JX_NOT_DEF, Icode.GetLlOpcode(defAt-1));
  109. flg |= PROC_ASM; /* generate asm */
  110. }
  111. if (! notSup)
  112. {
  113. exp = COND_EXPR::boolOp (lhs, rhs,
  114. condOpJCond[Icode.GetLlOpcode(useAt-1)-iJB]);
  115. Icode.GetIcode(useAt-1)->setJCond(exp);
  116. }
  117. }
  118. else if (Icode.GetLlOpcode(useAt-1) == iJCXZ)
  119. {
  120. lhs = COND_EXPR::idReg (rCX, 0, &localId);
  121. Icode.GetIcode(useAt-1)->setRegDU (rCX, eUSE);
  122. rhs = COND_EXPR::idKte (0, 2);
  123. exp = COND_EXPR::boolOp (lhs, rhs, EQUAL);
  124. Icode.GetIcode(useAt-1)->setJCond(exp);
  125. }
  126. else
  127. {
  128. reportError (NOT_DEF_USE,
  129. Icode.GetLlOpcode(defAt-1),
  130. Icode.GetLlOpcode(useAt-1));
  131. flg |= PROC_ASM; /* generate asm */
  132. }
  133. break;
  134. }
  135. }
  136. /* Check for extended basic block */
  137. if ((pBB->length == 1) &&
  138. (Icode.GetLlOpcode(useAt-1) >= iJB) &&
  139. (Icode.GetLlOpcode(useAt-1) <= iJNS))
  140. {
  141. prev = Icode.GetIcode(pBB->inEdges[0]->start +
  142. pBB->inEdges[0]->length - 1);
  143. if (prev->ic.hl.opcode == HLI_JCOND)
  144. {
  145. exp = prev->ic.hl.oper.exp->clone();
  146. exp->changeBoolOp (condOpJCond[Icode.GetLlOpcode(useAt-1)-iJB]);
  147. Icode[useAt-1].copyDU(*prev, eUSE, eUSE);
  148. Icode[useAt-1].setJCond(exp);
  149. }
  150. }
  151. /* Error - definition not found for use of a cond code */
  152. else if (defAt == pBB->start)
  153. fatalError (DEF_NOT_FOUND,
  154. Icode.GetLlOpcode(useAt-1));
  155. }
  156. }
  157. }
  158. /* Generates the LiveUse() and Def() sets for each basic block in the graph.
  159. * Note: these sets are constant and could have been constructed during
  160. * the construction of the graph, but since the code hasn't been
  161. * analyzed yet for idioms, the procedure preamble misleads the
  162. * analysis (eg: push si, would include si in LiveUse; although it
  163. * is not really meant to be a register that is used before defined). */
  164. void Function::genLiveKtes ()
  165. { Int i, j;
  166. BB * pbb;
  167. ICODE * picode;
  168. dword liveUse, def;
  169. for (i = 0; i < numBBs; i++)
  170. {
  171. liveUse = def = 0;
  172. pbb = dfsLast[i];
  173. if (pbb->flg & INVALID_BB)
  174. continue; /* skip invalid BBs */
  175. for (j = pbb->start; j < (pbb->start + pbb->length); j++)
  176. {
  177. picode = Icode.GetIcode(j);
  178. if ((picode->type == HIGH_LEVEL) && (picode->invalid == FALSE))
  179. {
  180. liveUse |= (picode->du.use & ~def);
  181. def |= picode->du.def;
  182. }
  183. }
  184. pbb->liveUse = liveUse;
  185. pbb->def = def;
  186. }
  187. }
  188. /* Generates the liveIn() and liveOut() sets for each basic block via an
  189. * iterative approach.
  190. * Propagates register usage information to the procedure call. */
  191. void Function::liveRegAnalysis (dword in_liveOut)
  192. {
  193. Int i, j;
  194. BB * pbb=0; /* pointer to current basic block */
  195. Function * pcallee; /* invoked subroutine */
  196. ICODE *ticode, /* icode that invokes a subroutine */
  197. *picode; /* icode of function return */
  198. dword prevLiveOut, /* previous live out */
  199. prevLiveIn; /* previous live in */
  200. boolT change; /* is there change in the live sets?*/
  201. /* liveOut for this procedure */
  202. liveOut = in_liveOut;
  203. change = TRUE;
  204. while (change)
  205. {
  206. /* Process nodes in reverse postorder order */
  207. change = FALSE;
  208. for (i = numBBs; i > 0; i--)
  209. {
  210. pbb = dfsLast[i-1];
  211. if (pbb->flg & INVALID_BB) /* Do not process invalid BBs */
  212. continue;
  213. /* Get current liveIn() and liveOut() sets */
  214. prevLiveIn = pbb->liveIn;
  215. prevLiveOut = pbb->liveOut;
  216. /* liveOut(b) = U LiveIn(s); where s is successor(b)
  217. * liveOut(b) = {liveOut}; when b is a HLI_RET node */
  218. if (pbb->numOutEdges == 0) /* HLI_RET node */
  219. {
  220. pbb->liveOut = in_liveOut;
  221. /* Get return expression of function */
  222. if (flg & PROC_IS_FUNC)
  223. {
  224. picode = Icode.GetIcode(pbb->start + pbb->length - 1);
  225. if (picode->ic.hl.opcode == HLI_RET)
  226. {
  227. picode->ic.hl.oper.exp = COND_EXPR::idID (&retVal,
  228. &localId, pbb->start + pbb->length - 1);
  229. picode->du.use = in_liveOut;
  230. }
  231. }
  232. }
  233. else /* Check successors */
  234. {
  235. for (j = 0; j < pbb->numOutEdges; j++)
  236. pbb->liveOut |= pbb->edges[j].BBptr->liveIn;
  237. /* propagate to invoked procedure */
  238. if (pbb->nodeType == CALL_NODE)
  239. {
  240. ticode = Icode.GetIcode(pbb->start + pbb->length - 1);
  241. pcallee = ticode->ic.hl.oper.call.proc;
  242. /* user/runtime routine */
  243. if (! (pcallee->flg & PROC_ISLIB))
  244. {
  245. if (pcallee->liveAnal == FALSE) /* hasn't been processed */
  246. pcallee->dataFlow (pbb->liveOut);
  247. pbb->liveOut = pcallee->liveIn;
  248. }
  249. else /* library routine */
  250. {
  251. if ((pcallee->flg & PROC_IS_FUNC) && /* returns a value */
  252. (pcallee->liveOut & pbb->edges[0].BBptr->liveIn))
  253. pbb->liveOut = pcallee->liveOut;
  254. else
  255. pbb->liveOut = 0;
  256. }
  257. if ((! (pcallee->flg & PROC_ISLIB)) || (pbb->liveOut != 0))
  258. {
  259. switch (pcallee->retVal.type) {
  260. case TYPE_LONG_SIGN: case TYPE_LONG_UNSIGN:
  261. ticode->du1.numRegsDef = 2;
  262. break;
  263. case TYPE_WORD_SIGN: case TYPE_WORD_UNSIGN:
  264. case TYPE_BYTE_SIGN: case TYPE_BYTE_UNSIGN:
  265. ticode->du1.numRegsDef = 1;
  266. break;
  267. } /*eos*/
  268. /* Propagate def/use results to calling icode */
  269. ticode->du.use = pcallee->liveIn;
  270. ticode->du.def = pcallee->liveOut;
  271. }
  272. }
  273. }
  274. /* liveIn(b) = liveUse(b) U (liveOut(b) - def(b) */
  275. pbb->liveIn = pbb->liveUse | (pbb->liveOut & ~pbb->def);
  276. /* Check if live sets have been modified */
  277. if ((prevLiveIn != pbb->liveIn) || (prevLiveOut != pbb->liveOut))
  278. change = TRUE;
  279. }
  280. }
  281. /* Propagate liveIn(b) to procedure header */
  282. if (pbb->liveIn != 0) /* uses registers */
  283. liveIn = pbb->liveIn;
  284. /* Remove any references to register variables */
  285. if (flg & SI_REGVAR)
  286. {
  287. liveIn &= maskDuReg[rSI];
  288. pbb->liveIn &= maskDuReg[rSI];
  289. }
  290. if (flg & DI_REGVAR)
  291. {
  292. liveIn &= maskDuReg[rDI];
  293. pbb->liveIn &= maskDuReg[rDI];
  294. }
  295. }
  296. /* Generates the du chain of each instruction in a basic block */
  297. void Function::genDU1 ()
  298. {
  299. byte regi; /* Register that was defined */
  300. Int i, j, k, p, n, lastInst, defRegIdx, useIdx;
  301. ICODE * picode, *ticode;/* Current and target bb */
  302. BB * pbb, *tbb; /* Current and target basic block */
  303. boolT res;
  304. COND_EXPR *exp, *lhs;
  305. /* Traverse tree in dfsLast order */
  306. for (i = 0; i < numBBs; i++)
  307. {
  308. pbb = dfsLast[i];
  309. if (pbb->flg & INVALID_BB) continue;
  310. /* Process each register definition of a HIGH_LEVEL icode instruction.
  311. * Note that register variables should not be considered registers.
  312. */
  313. lastInst = pbb->start + pbb->length;
  314. for (j = pbb->start; j < lastInst; j++)
  315. {
  316. picode = Icode.GetIcode(j);
  317. if (picode->type == HIGH_LEVEL)
  318. {
  319. regi = 0;
  320. defRegIdx = 0;
  321. for (k = 0; k < INDEXBASE; k++)
  322. {
  323. if ((picode->du.def & power2(k)) != 0)
  324. {
  325. regi = (byte)(k + 1); /* defined register */
  326. picode->du1.regi[defRegIdx] = regi;
  327. /* Check remaining instructions of the BB for all uses
  328. * of register regi, before any definitions of the
  329. * register */
  330. if ((regi == rDI) && (flg & DI_REGVAR))
  331. continue;
  332. if ((regi == rSI) && (flg & SI_REGVAR))
  333. continue;
  334. if ((j + 1) < lastInst) /* several instructions */
  335. {
  336. useIdx = 0;
  337. for (n = j+1; n < lastInst; n++)
  338. {
  339. /* Only check uses of HIGH_LEVEL icodes */
  340. ticode = Icode.GetIcode(n);
  341. if (ticode->type == HIGH_LEVEL)
  342. {
  343. /* if used, get icode index */
  344. if (ticode->du.use & duReg[regi])
  345. picode->du1.idx[defRegIdx][useIdx++] = n;
  346. /* if defined, stop finding uses for this reg */
  347. if (ticode->du.def & duReg[regi])
  348. break;
  349. }
  350. }
  351. /* Check if last definition of this register */
  352. if ((! (ticode->du.def & duReg[regi])) &&
  353. (pbb->liveOut & duReg[regi]))
  354. picode->du.lastDefRegi |= duReg[regi];
  355. }
  356. else /* only 1 instruction in this basic block */
  357. {
  358. /* Check if last definition of this register */
  359. if (pbb->liveOut & duReg[regi])
  360. picode->du.lastDefRegi |= duReg[regi];
  361. }
  362. /* Find target icode for HLI_CALL icodes to procedures
  363. * that are functions. The target icode is in the
  364. * next basic block (unoptimized code) or somewhere else
  365. * on optimized code. */
  366. if ((picode->ic.hl.opcode == HLI_CALL) &&
  367. (picode->ic.hl.oper.call.proc->flg & PROC_IS_FUNC))
  368. {
  369. tbb = pbb->edges[0].BBptr;
  370. useIdx = 0;
  371. for (n = tbb->start; n < tbb->start + tbb->length; n++)
  372. {
  373. ticode = Icode.GetIcode(n);
  374. if (ticode->type == HIGH_LEVEL)
  375. {
  376. /* if used, get icode index */
  377. if (ticode->du.use & duReg[regi])
  378. picode->du1.idx[defRegIdx][useIdx++] = n;
  379. /* if defined, stop finding uses for this reg */
  380. if (ticode->du.def & duReg[regi])
  381. break;
  382. }
  383. }
  384. /* if not used in this basic block, check if the
  385. * register is live out, if so, make it the last
  386. * definition of this register */
  387. if ((picode->du1.idx[defRegIdx][useIdx] == 0) &&
  388. (tbb->liveOut & duReg[regi]))
  389. picode->du.lastDefRegi |= duReg[regi];
  390. }
  391. /* If not used within this bb or in successors of this
  392. * bb (ie. not in liveOut), then register is useless,
  393. * thus remove it. Also check that this is not a return
  394. * from a library function (routines such as printf
  395. * return an integer, which is normally not taken into
  396. * account by the programmer). */
  397. if ((picode->invalid == FALSE) &&
  398. (picode->du1.idx[defRegIdx][0] == 0) &&
  399. (! (picode->du.lastDefRegi & duReg[regi])) &&
  400. // (! ((picode->ic.hl.opcode != HLI_CALL) &&
  401. (! ((picode->ic.hl.opcode == HLI_CALL) &&
  402. (picode->ic.hl.oper.call.proc->flg & PROC_ISLIB))))
  403. {
  404. if (! (pbb->liveOut & duReg[regi])) /* not liveOut */
  405. {
  406. res = picode->removeDefRegi (regi, defRegIdx+1,&localId);
  407. /* Backpatch any uses of this instruction, within
  408. * the same BB, if the instruction was invalidated */
  409. if (res == TRUE)
  410. for (p = j; p > pbb->start; p--)
  411. {
  412. ticode = Icode.GetIcode(p-1);
  413. for (n = 0; n < MAX_USES; n++)
  414. {
  415. if (ticode->du1.idx[0][n] == j)
  416. {
  417. if (n < MAX_USES - 1)
  418. {
  419. memmove (&ticode->du1.idx[0][n],
  420. &ticode->du1.idx[0][n+1],
  421. (size_t)((MAX_USES - n - 1) * sizeof(Int)));
  422. n--;
  423. }
  424. ticode->du1.idx[0][MAX_USES - 1] = 0;
  425. }
  426. }
  427. }
  428. }
  429. else /* liveOut */
  430. picode->du.lastDefRegi |= duReg[regi];
  431. }
  432. defRegIdx++;
  433. /* Check if all defined registers have been processed */
  434. if ((defRegIdx >= picode->du1.numRegsDef) ||
  435. (defRegIdx == MAX_REGS_DEF))
  436. break;
  437. }
  438. }
  439. }
  440. }
  441. }
  442. }
  443. /* Substitutes the rhs (or lhs if rhs not possible) of ticode for the rhs
  444. * of picode. */
  445. static void forwardSubs (COND_EXPR *lhs, COND_EXPR *rhs, ICODE * picode,
  446. ICODE * ticode, LOCAL_ID *locsym, Int *numHlIcodes)
  447. {
  448. boolT res;
  449. if (rhs == NULL) /* In case expression popped is NULL */
  450. return;
  451. /* Insert on rhs of ticode, if possible */
  452. res = insertSubTreeReg (rhs, &ticode->ic.hl.oper.asgn.rhs,
  453. locsym->id_arr[lhs->expr.ident.idNode.regiIdx].id.regi,
  454. locsym);
  455. if (res)
  456. {
  457. picode->invalidate();
  458. (*numHlIcodes)--;
  459. }
  460. else
  461. {
  462. /* Try to insert it on lhs of ticode*/
  463. res = insertSubTreeReg (rhs, &ticode->ic.hl.oper.asgn.lhs,
  464. locsym->id_arr[lhs->expr.ident.idNode.regiIdx].id.regi,
  465. locsym);
  466. if (res)
  467. {
  468. picode->invalidate();
  469. (*numHlIcodes)--;
  470. }
  471. }
  472. }
  473. /* Substitutes the rhs (or lhs if rhs not possible) of ticode for the
  474. * expression exp given */
  475. static void forwardSubsLong (Int longIdx, COND_EXPR *exp, ICODE * picode,
  476. ICODE * ticode, Int *numHlIcodes)
  477. { boolT res;
  478. if (exp == NULL) /* In case expression popped is NULL */
  479. return;
  480. /* Insert on rhs of ticode, if possible */
  481. res = insertSubTreeLongReg (exp, &ticode->ic.hl.oper.asgn.rhs, longIdx);
  482. if (res)
  483. {
  484. picode->invalidate();
  485. (*numHlIcodes)--;
  486. }
  487. else
  488. {
  489. /* Try to insert it on lhs of ticode*/
  490. res = insertSubTreeLongReg (exp, &ticode->ic.hl.oper.asgn.lhs, longIdx);
  491. if (res)
  492. {
  493. picode->invalidate();
  494. (*numHlIcodes)--;
  495. }
  496. }
  497. }
  498. /* Returns whether the elements of the expression rhs are all x-clear from
  499. * instruction f up to instruction t. */
  500. static boolT xClear (COND_EXPR *rhs, Int f, Int t, Int lastBBinst, Function * pproc)
  501. { Int i;
  502. boolT res;
  503. byte regi;
  504. ICODE * picode;
  505. if (rhs == NULL)
  506. return false;
  507. switch (rhs->type) {
  508. case IDENTIFIER:
  509. if (rhs->expr.ident.idType == REGISTER)
  510. {
  511. picode = pproc->Icode.GetFirstIcode();
  512. regi= pproc->localId.id_arr[rhs->expr.ident.idNode.regiIdx].id.regi;
  513. for (i = (f + 1); (i < lastBBinst) && (i < t); i++)
  514. if ((picode[i].type == HIGH_LEVEL) &&
  515. (picode[i].invalid == FALSE))
  516. {
  517. if (picode[i].du.def & duReg[regi])
  518. return false;
  519. }
  520. if (i < lastBBinst)
  521. return true;
  522. else
  523. return false;
  524. }
  525. else
  526. return true;
  527. /* else if (rhs->expr.ident.idType == LONG_VAR)
  528. {
  529. missing all other identifiers ****
  530. } */
  531. case BOOLEAN_OP:
  532. res = xClear (rhs->expr.boolExpr.rhs, f, t, lastBBinst, pproc);
  533. if (res == FALSE)
  534. return false;
  535. return (xClear (rhs->expr.boolExpr.lhs, f, t, lastBBinst, pproc));
  536. case NEGATION:
  537. case ADDRESSOF:
  538. case DEREFERENCE:
  539. return (xClear (rhs->expr.unaryExp, f, t, lastBBinst, pproc));
  540. } /* eos */
  541. return FALSE;
  542. }
  543. /* Checks the type of the formal argument as against to the actual argument,
  544. * whenever possible, and then places the actual argument on the procedure's
  545. * argument list. */
  546. static void processCArg (Function * pp, Function * pProc, ICODE * picode, Int numArgs, Int *k)
  547. {
  548. COND_EXPR *exp;
  549. boolT res;
  550. /* if (numArgs == 0)
  551. return; */
  552. exp = popExpStk();
  553. if (pp->flg & PROC_ISLIB) /* library function */
  554. {
  555. if (pp->args.numArgs > 0)
  556. if (pp->flg & PROC_VARARG)
  557. {
  558. if (numArgs < pp->args.sym.size())
  559. adjustActArgType (exp, pp->args.sym[numArgs].type, pProc);
  560. }
  561. else
  562. adjustActArgType (exp, pp->args.sym[numArgs].type, pProc);
  563. res = newStkArg (picode, exp, picode->ic.ll.opcode, pProc);
  564. }
  565. else /* user function */
  566. {
  567. if (pp->args.numArgs > 0)
  568. pp->args.adjustForArgType (numArgs, expType (exp, pProc));
  569. res = newStkArg (picode, exp, picode->ic.ll.opcode, pProc);
  570. }
  571. /* Do not update the size of k if the expression was a segment register
  572. * in a near call */
  573. if (res == FALSE)
  574. *k += hlTypeSize (exp, pProc);
  575. }
  576. /* Eliminates extraneous intermediate icode instructions when finding
  577. * expressions. Generates new hlIcodes in the form of expression trees.
  578. * For HLI_CALL hlIcodes, places the arguments in the argument list. */
  579. void Function::findExps()
  580. {
  581. Int i, j, k, lastInst, numHlIcodes;
  582. ICODE * picode, /* Current icode */
  583. * ticode; /* Target icode */
  584. BB * pbb; /* Current and next basic block */
  585. boolT res;
  586. COND_EXPR *exp, /* expression pointer - for HLI_POP and HLI_CALL */
  587. *lhs; /* exp ptr for return value of a HLI_CALL */
  588. STKFRAME * args; /* pointer to arguments - for HLI_CALL */
  589. byte regi, regi2; /* register(s) to be forward substituted */
  590. ID *retVal; /* function return value */
  591. /* Initialize expression stack */
  592. initExpStk();
  593. /* Traverse tree in dfsLast order */
  594. for (i = 0; i < numBBs; i++)
  595. {
  596. /* Process one BB */
  597. pbb = dfsLast[i];
  598. if (pbb->flg & INVALID_BB) continue;
  599. lastInst = pbb->start + pbb->length;
  600. numHlIcodes = 0;
  601. for (j = pbb->start; j < lastInst; j++)
  602. {
  603. picode = Icode.GetIcode(j);
  604. if ((picode->type == HIGH_LEVEL) && (picode->invalid == FALSE))
  605. {
  606. numHlIcodes++;
  607. if (picode->du1.numRegsDef == 1) /* byte/word regs */
  608. {
  609. /* Check for only one use of this register. If this is
  610. * the last definition of the register in this BB, check
  611. * that it is not liveOut from this basic block */
  612. if ((picode->du1.idx[0][0] != 0) &&
  613. (picode->du1.idx[0][1] == 0))
  614. {
  615. /* Check that this register is not liveOut, if it
  616. * is the last definition of the register */
  617. regi = picode->du1.regi[0];
  618. /* Check if we can forward substitute this register */
  619. switch (picode->ic.hl.opcode) {
  620. case HLI_ASSIGN:
  621. /* Replace rhs of current icode into target
  622. * icode expression */
  623. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  624. if ((picode->du.lastDefRegi & duReg[regi]) &&
  625. ((ticode->ic.hl.opcode != HLI_CALL) &&
  626. (ticode->ic.hl.opcode != HLI_RET)))
  627. continue;
  628. if (xClear (picode->ic.hl.oper.asgn.rhs, j,
  629. picode->du1.idx[0][0], lastInst, this))
  630. {
  631. switch (ticode->ic.hl.opcode) {
  632. case HLI_ASSIGN:
  633. forwardSubs (picode->ic.hl.oper.asgn.lhs,
  634. picode->ic.hl.oper.asgn.rhs,
  635. picode, ticode, &localId,
  636. &numHlIcodes);
  637. break;
  638. case HLI_JCOND: case HLI_PUSH: case HLI_RET:
  639. res = insertSubTreeReg (
  640. picode->ic.hl.oper.asgn.rhs,
  641. &ticode->ic.hl.oper.exp,
  642. localId.id_arr[picode->ic.hl.oper.asgn.lhs->expr.ident.idNode.regiIdx].id.regi,
  643. &localId);
  644. if (res)
  645. {
  646. picode->invalidate();
  647. numHlIcodes--;
  648. }
  649. break;
  650. case HLI_CALL: /* register arguments */
  651. newRegArg (picode, ticode);
  652. picode->invalidate();
  653. numHlIcodes--;
  654. break;
  655. } /* eos */
  656. }
  657. break;
  658. case HLI_POP:
  659. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  660. if ((picode->du.lastDefRegi & duReg[regi]) &&
  661. ((ticode->ic.hl.opcode != HLI_CALL) &&
  662. (ticode->ic.hl.opcode != HLI_RET)))
  663. continue;
  664. exp = popExpStk(); /* pop last exp pushed */
  665. switch (ticode->ic.hl.opcode) {
  666. case HLI_ASSIGN:
  667. forwardSubs (picode->ic.hl.oper.exp, exp,
  668. picode, ticode, &localId,
  669. &numHlIcodes);
  670. break;
  671. case HLI_JCOND: case HLI_PUSH: case HLI_RET:
  672. res = insertSubTreeReg (exp,
  673. &ticode->ic.hl.oper.exp,
  674. localId.id_arr[picode->ic.hl.oper.exp->expr.ident.idNode.regiIdx].id.regi,
  675. &localId);
  676. if (res)
  677. {
  678. picode->invalidate();
  679. numHlIcodes--;
  680. }
  681. break;
  682. /****case HLI_CALL: /* register arguments
  683. newRegArg (pProc, picode, ticode);
  684. picode->invalidate();
  685. numHlIcodes--;
  686. break; */
  687. } /* eos */
  688. break;
  689. case HLI_CALL:
  690. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  691. switch (ticode->ic.hl.opcode) {
  692. case HLI_ASSIGN:
  693. exp = COND_EXPR::idFunc (
  694. picode->ic.hl.oper.call.proc,
  695. picode->ic.hl.oper.call.args);
  696. res = insertSubTreeReg (exp,
  697. &ticode->ic.hl.oper.asgn.rhs,
  698. picode->ic.hl.oper.call.proc->retVal.id.regi,
  699. &localId);
  700. if (! res)
  701. insertSubTreeReg (exp,
  702. &ticode->ic.hl.oper.asgn.lhs,
  703. picode->ic.hl.oper.call.proc->retVal.id.regi,
  704. &localId);
  705. /*** HERE missing: 2 regs ****/
  706. picode->invalidate();
  707. numHlIcodes--;
  708. break;
  709. case HLI_PUSH: case HLI_RET:
  710. exp = COND_EXPR::idFunc (
  711. picode->ic.hl.oper.call.proc,
  712. picode->ic.hl.oper.call.args);
  713. ticode->ic.hl.oper.exp = exp;
  714. picode->invalidate();
  715. numHlIcodes--;
  716. break;
  717. case HLI_JCOND:
  718. exp = COND_EXPR::idFunc (
  719. picode->ic.hl.oper.call.proc,
  720. picode->ic.hl.oper.call.args);
  721. retVal = &picode->ic.hl.oper.call.proc->retVal,
  722. res = insertSubTreeReg (exp,
  723. &ticode->ic.hl.oper.exp,
  724. retVal->id.regi, &localId);
  725. if (res) /* was substituted */
  726. {
  727. picode->invalidate();
  728. numHlIcodes--;
  729. }
  730. else /* cannot substitute function */
  731. {
  732. lhs = COND_EXPR::idID(retVal,&localId,j);
  733. picode->setAsgn(lhs, exp);
  734. }
  735. break;
  736. } /* eos */
  737. break;
  738. } /* eos */
  739. }
  740. }
  741. else if (picode->du1.numRegsDef == 2) /* long regs */
  742. {
  743. /* Check for only one use of these registers */
  744. if ((picode->du1.idx[0][0] != 0) &&
  745. (picode->du1.idx[0][1] == 0) &&
  746. (picode->du1.idx[1][0] != 0) &&
  747. (picode->du1.idx[1][1] == 0))
  748. {
  749. switch (picode->ic.hl.opcode) {
  750. case HLI_ASSIGN:
  751. /* Replace rhs of current icode into target
  752. * icode expression */
  753. if (picode->du1.idx[0][0] == picode->du1.idx[1][0])
  754. {
  755. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  756. if ((picode->du.lastDefRegi & duReg[regi]) &&
  757. ((ticode->ic.hl.opcode != HLI_CALL) &&
  758. (ticode->ic.hl.opcode != HLI_RET)))
  759. continue;
  760. switch (ticode->ic.hl.opcode) {
  761. case HLI_ASSIGN:
  762. forwardSubsLong (picode->ic.hl.oper.asgn.lhs->expr.ident.idNode.longIdx,
  763. picode->ic.hl.oper.asgn.rhs, picode,
  764. ticode, &numHlIcodes);
  765. break;
  766. case HLI_JCOND: case HLI_PUSH: case HLI_RET:
  767. res = insertSubTreeLongReg (
  768. picode->ic.hl.oper.asgn.rhs,
  769. &ticode->ic.hl.oper.exp,
  770. picode->ic.hl.oper.asgn.lhs->expr.ident.idNode.longIdx);
  771. if (res)
  772. {
  773. picode->invalidate();
  774. numHlIcodes--;
  775. }
  776. break;
  777. case HLI_CALL: /* register arguments */
  778. newRegArg ( picode, ticode);
  779. picode->invalidate();
  780. numHlIcodes--;
  781. break;
  782. } /* eos */
  783. }
  784. break;
  785. case HLI_POP:
  786. if (picode->du1.idx[0][0] == picode->du1.idx[1][0])
  787. {
  788. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  789. if ((picode->du.lastDefRegi & duReg[regi]) &&
  790. ((ticode->ic.hl.opcode != HLI_CALL) &&
  791. (ticode->ic.hl.opcode != HLI_RET)))
  792. continue;
  793. exp = popExpStk(); /* pop last exp pushed */
  794. switch (ticode->ic.hl.opcode) {
  795. case HLI_ASSIGN:
  796. forwardSubsLong (picode->ic.hl.oper.exp->expr.ident.idNode.longIdx,
  797. exp, picode, ticode, &numHlIcodes);
  798. break;
  799. case HLI_JCOND: case HLI_PUSH:
  800. res = insertSubTreeLongReg (exp,
  801. &ticode->ic.hl.oper.exp,
  802. picode->ic.hl.oper.asgn.lhs->expr.ident.idNode.longIdx);
  803. if (res)
  804. {
  805. picode->invalidate();
  806. numHlIcodes--;
  807. }
  808. break;
  809. case HLI_CALL: /*** missing ***/
  810. break;
  811. } /* eos */
  812. }
  813. break;
  814. case HLI_CALL: /* check for function return */
  815. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  816. switch (ticode->ic.hl.opcode)
  817. {
  818. case HLI_ASSIGN:
  819. exp = COND_EXPR::idFunc (
  820. picode->ic.hl.oper.call.proc,
  821. picode->ic.hl.oper.call.args);
  822. ticode->ic.hl.oper.asgn.lhs =
  823. COND_EXPR::idLong(&localId, DST, ticode,
  824. HIGH_FIRST, j, eDEF, 1);
  825. ticode->ic.hl.oper.asgn.rhs = exp;
  826. picode->invalidate();
  827. numHlIcodes--;
  828. break;
  829. case HLI_PUSH: case HLI_RET:
  830. exp = COND_EXPR::idFunc (
  831. picode->ic.hl.oper.call.proc,
  832. picode->ic.hl.oper.call.args);
  833. ticode->ic.hl.oper.exp = exp;
  834. picode->invalidate();
  835. numHlIcodes--;
  836. break;
  837. case HLI_JCOND:
  838. exp = COND_EXPR::idFunc (
  839. picode->ic.hl.oper.call.proc,
  840. picode->ic.hl.oper.call.args);
  841. retVal = &picode->ic.hl.oper.call.proc->retVal;
  842. res = insertSubTreeLongReg (exp,
  843. &ticode->ic.hl.oper.exp,
  844. localId.newLongReg
  845. (
  846. retVal->type, retVal->id.longId.h,
  847. retVal->id.longId.l, j));
  848. if (res) /* was substituted */
  849. {
  850. picode->invalidate();
  851. numHlIcodes--;
  852. }
  853. else /* cannot substitute function */
  854. {
  855. lhs = COND_EXPR::idID(retVal,&localId,j);
  856. picode->setAsgn(lhs, exp);
  857. }
  858. break;
  859. } /* eos */
  860. } /* eos */
  861. }
  862. }
  863. /* HLI_PUSH doesn't define any registers, only uses registers.
  864. * Push the associated expression to the register on the local
  865. * expression stack */
  866. else if (picode->ic.hl.opcode == HLI_PUSH)
  867. {
  868. pushExpStk (picode->ic.hl.oper.exp);
  869. picode->invalidate();
  870. numHlIcodes--;
  871. }
  872. /* For HLI_CALL instructions that use arguments from the stack,
  873. * pop them from the expression stack and place them on the
  874. * procedure's argument list */
  875. if ((picode->ic.hl.opcode == HLI_CALL) &&
  876. ! (picode->ic.hl.oper.call.proc->flg & REG_ARGS))
  877. { Function * pp;
  878. Int cb, numArgs;
  879. boolT res;
  880. pp = picode->ic.hl.oper.call.proc;
  881. if (pp->flg & CALL_PASCAL)
  882. {
  883. cb = pp->cbParam; /* fixed # arguments */
  884. for (k = 0, numArgs = 0; k < cb; numArgs++)
  885. {
  886. exp = popExpStk();
  887. if (pp->flg & PROC_ISLIB) /* library function */
  888. {
  889. if (pp->args.numArgs > 0)
  890. adjustActArgType(exp, pp->args.sym[numArgs].type, this);
  891. res = newStkArg (picode, exp, picode->ic.ll.opcode, this);
  892. }
  893. else /* user function */
  894. {
  895. if (pp->args.numArgs >0)
  896. pp->args.adjustForArgType (numArgs,expType (exp, this));
  897. res = newStkArg (picode, exp,picode->ic.ll.opcode, this);
  898. }
  899. if (res == FALSE)
  900. k += hlTypeSize (exp, this);
  901. }
  902. }
  903. else /* CALL_C */
  904. {
  905. cb = picode->ic.hl.oper.call.args->cb;
  906. numArgs = 0;
  907. if (cb)
  908. for (k = 0; k < cb; numArgs++)
  909. processCArg (pp, this, picode, numArgs, &k);
  910. else if ((cb == 0) && (picode->ic.ll.flg & REST_STK))
  911. while (! emptyExpStk())
  912. {
  913. processCArg (pp, this, picode, numArgs, &k);
  914. numArgs++;
  915. }
  916. }
  917. }
  918. /* If we could not substitute the result of a function,
  919. * assign it to the corresponding registers */
  920. if ((picode->ic.hl.opcode == HLI_CALL) &&
  921. ((picode->ic.hl.oper.call.proc->flg & PROC_ISLIB) !=
  922. PROC_ISLIB) && (picode->du1.idx[0][0] == 0) &&
  923. (picode->du1.numRegsDef > 0))
  924. {
  925. exp = COND_EXPR::idFunc (picode->ic.hl.oper.call.proc,
  926. picode->ic.hl.oper.call.args);
  927. lhs = COND_EXPR::idID (&picode->ic.hl.oper.call.proc->retVal,
  928. &localId, j);
  929. picode->setAsgn(lhs, exp);
  930. }
  931. }
  932. }
  933. /* Store number of high-level icodes in current basic block */
  934. pbb->numHlIcodes = numHlIcodes;
  935. }
  936. }
  937. /* Invokes procedures related with data flow analysis. Works on a procedure
  938. * at a time basis.
  939. * Note: indirect recursion in liveRegAnalysis is possible. */
  940. void Function::dataFlow(dword liveOut)
  941. {
  942. boolT isAx, isBx, isCx, isDx;
  943. Int idx;
  944. /* Remove references to register variables */
  945. if (flg & SI_REGVAR)
  946. liveOut &= maskDuReg[rSI];
  947. if (flg & DI_REGVAR)
  948. liveOut &= maskDuReg[rDI];
  949. /* Function - return value register(s) */
  950. if (liveOut != 0)
  951. {
  952. flg |= PROC_IS_FUNC;
  953. isAx = (boolT)(liveOut & power2(rAX - rAX));
  954. isBx = (boolT)(liveOut & power2(rBX - rAX));
  955. isCx = (boolT)(liveOut & power2(rCX - rAX));
  956. isDx = (boolT)(liveOut & power2(rDX - rAX));
  957. if (isAx && isDx) /* long or pointer */
  958. {
  959. retVal.type = TYPE_LONG_SIGN;
  960. retVal.loc = REG_FRAME;
  961. retVal.id.longId.h = rDX;
  962. retVal.id.longId.l = rAX;
  963. idx = localId.newLongReg(TYPE_LONG_SIGN, rDX, rAX, 0);
  964. localId.propLongId (rAX, rDX, "\0");
  965. }
  966. else if (isAx || isBx || isCx || isDx) /* word */
  967. {
  968. retVal.type = TYPE_WORD_SIGN;
  969. retVal.loc = REG_FRAME;
  970. if (isAx)
  971. retVal.id.regi = rAX;
  972. else if (isBx)
  973. retVal.id.regi = rBX;
  974. else if (isCx)
  975. retVal.id.regi = rCX;
  976. else
  977. retVal.id.regi = rDX;
  978. idx = localId.newByteWordReg(TYPE_WORD_SIGN,retVal.id.regi);
  979. }
  980. }
  981. /* Data flow analysis */
  982. liveAnal = TRUE;
  983. elimCondCodes();
  984. genLiveKtes();
  985. liveRegAnalysis (liveOut); /* calls dataFlow() recursively */
  986. if (! (flg & PROC_ASM)) /* can generate C for pProc */
  987. {
  988. genDU1 (); /* generate def/use level 1 chain */
  989. findExps (); /* forward substitution algorithm */
  990. }
  991. }