dataflow.cpp 49 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098
  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. ICODE & prev(pBB->back());
  142. if (prev.ic.hl.opcode == HLI_JCOND)
  143. {
  144. exp = prev.ic.hl.oper.exp->clone();
  145. exp->changeBoolOp (condOpJCond[Icode.GetLlOpcode(useAt-1)-iJB]);
  146. Icode[useAt-1].copyDU(prev, eUSE, eUSE);
  147. Icode[useAt-1].setJCond(exp);
  148. }
  149. }
  150. /* Error - definition not found for use of a cond code */
  151. else if (defAt == pBB->start)
  152. {
  153. reportError(DEF_NOT_FOUND,Icode.GetLlOpcode(useAt-1));
  154. //fatalError (DEF_NOT_FOUND, Icode.GetLlOpcode(useAt-1));
  155. }
  156. }
  157. }
  158. }
  159. /* Generates the LiveUse() and Def() sets for each basic block in the graph.
  160. * Note: these sets are constant and could have been constructed during
  161. * the construction of the graph, but since the code hasn't been
  162. * analyzed yet for idioms, the procedure preamble misleads the
  163. * analysis (eg: push si, would include si in LiveUse; although it
  164. * is not really meant to be a register that is used before defined). */
  165. void Function::genLiveKtes ()
  166. {
  167. Int i;
  168. BB * pbb;
  169. dword liveUse, def;
  170. for (i = 0; i < numBBs; i++)
  171. {
  172. liveUse = def = 0;
  173. pbb = dfsLast[i];
  174. if (pbb->flg & INVALID_BB)
  175. continue; /* skip invalid BBs */
  176. for (auto j = pbb->begin2(); j != pbb->end2(); j++)
  177. {
  178. if ((j->type == HIGH_LEVEL) && (j->invalid == FALSE))
  179. {
  180. liveUse |= (j->du.use & ~def);
  181. def |= j->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->edges.empty()) /* 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. assert(pbb->back().loc_ip == pbb->start+pbb->length-1);
  228. picode->ic.hl.oper.exp = COND_EXPR::idID (&retVal, &localId, pbb->back().loc_ip);
  229. picode->du.use = in_liveOut;
  230. }
  231. }
  232. }
  233. else /* Check successors */
  234. {
  235. for (j = 0; j < pbb->edges.size(); 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.front();
  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, picode->du1.idx[0][0], lastInst, this))
  629. {
  630. switch (ticode->ic.hl.opcode) {
  631. case HLI_ASSIGN:
  632. forwardSubs (picode->ic.hl.oper.asgn.lhs,
  633. picode->ic.hl.oper.asgn.rhs,
  634. picode, ticode, &localId,
  635. &numHlIcodes);
  636. break;
  637. case HLI_JCOND: case HLI_PUSH: case HLI_RET:
  638. res = insertSubTreeReg (
  639. picode->ic.hl.oper.asgn.rhs,
  640. &ticode->ic.hl.oper.exp,
  641. localId.id_arr[picode->ic.hl.oper.asgn.lhs->expr.ident.idNode.regiIdx].id.regi,
  642. &localId);
  643. if (res)
  644. {
  645. picode->invalidate();
  646. numHlIcodes--;
  647. }
  648. break;
  649. case HLI_CALL: /* register arguments */
  650. newRegArg (picode, ticode);
  651. picode->invalidate();
  652. numHlIcodes--;
  653. break;
  654. } /* eos */
  655. }
  656. break;
  657. case HLI_POP:
  658. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  659. if ((picode->du.lastDefRegi & duReg[regi]) &&
  660. ((ticode->ic.hl.opcode != HLI_CALL) &&
  661. (ticode->ic.hl.opcode != HLI_RET)))
  662. continue;
  663. exp = popExpStk(); /* pop last exp pushed */
  664. switch (ticode->ic.hl.opcode) {
  665. case HLI_ASSIGN:
  666. forwardSubs (picode->ic.hl.oper.exp, exp,
  667. picode, ticode, &localId,
  668. &numHlIcodes);
  669. break;
  670. case HLI_JCOND: case HLI_PUSH: case HLI_RET:
  671. res = insertSubTreeReg (exp,
  672. &ticode->ic.hl.oper.exp,
  673. localId.id_arr[picode->ic.hl.oper.exp->expr.ident.idNode.regiIdx].id.regi,
  674. &localId);
  675. if (res)
  676. {
  677. picode->invalidate();
  678. numHlIcodes--;
  679. }
  680. break;
  681. /****case HLI_CALL: /* register arguments
  682. newRegArg (pProc, picode, ticode);
  683. picode->invalidate();
  684. numHlIcodes--;
  685. break; */
  686. } /* eos */
  687. break;
  688. case HLI_CALL:
  689. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  690. switch (ticode->ic.hl.opcode) {
  691. case HLI_ASSIGN:
  692. exp = COND_EXPR::idFunc (
  693. picode->ic.hl.oper.call.proc,
  694. picode->ic.hl.oper.call.args);
  695. res = insertSubTreeReg (exp,
  696. &ticode->ic.hl.oper.asgn.rhs,
  697. picode->ic.hl.oper.call.proc->retVal.id.regi,
  698. &localId);
  699. if (! res)
  700. insertSubTreeReg (exp,
  701. &ticode->ic.hl.oper.asgn.lhs,
  702. picode->ic.hl.oper.call.proc->retVal.id.regi,
  703. &localId);
  704. /*** HERE missing: 2 regs ****/
  705. picode->invalidate();
  706. numHlIcodes--;
  707. break;
  708. case HLI_PUSH: case HLI_RET:
  709. exp = COND_EXPR::idFunc (
  710. picode->ic.hl.oper.call.proc,
  711. picode->ic.hl.oper.call.args);
  712. ticode->ic.hl.oper.exp = exp;
  713. picode->invalidate();
  714. numHlIcodes--;
  715. break;
  716. case HLI_JCOND:
  717. exp = COND_EXPR::idFunc (
  718. picode->ic.hl.oper.call.proc,
  719. picode->ic.hl.oper.call.args);
  720. retVal = &picode->ic.hl.oper.call.proc->retVal,
  721. res = insertSubTreeReg (exp,
  722. &ticode->ic.hl.oper.exp,
  723. retVal->id.regi, &localId);
  724. if (res) /* was substituted */
  725. {
  726. picode->invalidate();
  727. numHlIcodes--;
  728. }
  729. else /* cannot substitute function */
  730. {
  731. lhs = COND_EXPR::idID(retVal,&localId,j);
  732. picode->setAsgn(lhs, exp);
  733. }
  734. break;
  735. } /* eos */
  736. break;
  737. } /* eos */
  738. }
  739. }
  740. else if (picode->du1.numRegsDef == 2) /* long regs */
  741. {
  742. /* Check for only one use of these registers */
  743. if ((picode->du1.idx[0][0] != 0) &&
  744. (picode->du1.idx[0][1] == 0) &&
  745. (picode->du1.idx[1][0] != 0) &&
  746. (picode->du1.idx[1][1] == 0))
  747. {
  748. switch (picode->ic.hl.opcode) {
  749. case HLI_ASSIGN:
  750. /* Replace rhs of current icode into target
  751. * icode expression */
  752. if (picode->du1.idx[0][0] == picode->du1.idx[1][0])
  753. {
  754. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  755. if ((picode->du.lastDefRegi & duReg[regi]) &&
  756. ((ticode->ic.hl.opcode != HLI_CALL) &&
  757. (ticode->ic.hl.opcode != HLI_RET)))
  758. continue;
  759. switch (ticode->ic.hl.opcode) {
  760. case HLI_ASSIGN:
  761. forwardSubsLong (picode->ic.hl.oper.asgn.lhs->expr.ident.idNode.longIdx,
  762. picode->ic.hl.oper.asgn.rhs, picode,
  763. ticode, &numHlIcodes);
  764. break;
  765. case HLI_JCOND: case HLI_PUSH: case HLI_RET:
  766. res = insertSubTreeLongReg (
  767. picode->ic.hl.oper.asgn.rhs,
  768. &ticode->ic.hl.oper.exp,
  769. picode->ic.hl.oper.asgn.lhs->expr.ident.idNode.longIdx);
  770. if (res)
  771. {
  772. picode->invalidate();
  773. numHlIcodes--;
  774. }
  775. break;
  776. case HLI_CALL: /* register arguments */
  777. newRegArg ( picode, ticode);
  778. picode->invalidate();
  779. numHlIcodes--;
  780. break;
  781. } /* eos */
  782. }
  783. break;
  784. case HLI_POP:
  785. if (picode->du1.idx[0][0] == picode->du1.idx[1][0])
  786. {
  787. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  788. if ((picode->du.lastDefRegi & duReg[regi]) &&
  789. ((ticode->ic.hl.opcode != HLI_CALL) &&
  790. (ticode->ic.hl.opcode != HLI_RET)))
  791. continue;
  792. exp = popExpStk(); /* pop last exp pushed */
  793. switch (ticode->ic.hl.opcode) {
  794. case HLI_ASSIGN:
  795. forwardSubsLong (picode->ic.hl.oper.exp->expr.ident.idNode.longIdx,
  796. exp, picode, ticode, &numHlIcodes);
  797. break;
  798. case HLI_JCOND: case HLI_PUSH:
  799. res = insertSubTreeLongReg (exp,
  800. &ticode->ic.hl.oper.exp,
  801. picode->ic.hl.oper.asgn.lhs->expr.ident.idNode.longIdx);
  802. if (res)
  803. {
  804. picode->invalidate();
  805. numHlIcodes--;
  806. }
  807. break;
  808. case HLI_CALL: /*** missing ***/
  809. break;
  810. } /* eos */
  811. }
  812. break;
  813. case HLI_CALL: /* check for function return */
  814. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  815. switch (ticode->ic.hl.opcode)
  816. {
  817. case HLI_ASSIGN:
  818. exp = COND_EXPR::idFunc (
  819. picode->ic.hl.oper.call.proc,
  820. picode->ic.hl.oper.call.args);
  821. ticode->ic.hl.oper.asgn.lhs =
  822. COND_EXPR::idLong(&localId, DST, ticode,
  823. HIGH_FIRST, j, eDEF, 1);
  824. ticode->ic.hl.oper.asgn.rhs = exp;
  825. picode->invalidate();
  826. numHlIcodes--;
  827. break;
  828. case HLI_PUSH: case HLI_RET:
  829. exp = COND_EXPR::idFunc (
  830. picode->ic.hl.oper.call.proc,
  831. picode->ic.hl.oper.call.args);
  832. ticode->ic.hl.oper.exp = exp;
  833. picode->invalidate();
  834. numHlIcodes--;
  835. break;
  836. case HLI_JCOND:
  837. exp = COND_EXPR::idFunc (
  838. picode->ic.hl.oper.call.proc,
  839. picode->ic.hl.oper.call.args);
  840. retVal = &picode->ic.hl.oper.call.proc->retVal;
  841. res = insertSubTreeLongReg (exp,
  842. &ticode->ic.hl.oper.exp,
  843. localId.newLongReg
  844. (
  845. retVal->type, retVal->id.longId.h,
  846. retVal->id.longId.l, j));
  847. if (res) /* was substituted */
  848. {
  849. picode->invalidate();
  850. numHlIcodes--;
  851. }
  852. else /* cannot substitute function */
  853. {
  854. lhs = COND_EXPR::idID(retVal,&localId,j);
  855. picode->setAsgn(lhs, exp);
  856. }
  857. break;
  858. } /* eos */
  859. } /* eos */
  860. }
  861. }
  862. /* HLI_PUSH doesn't define any registers, only uses registers.
  863. * Push the associated expression to the register on the local
  864. * expression stack */
  865. else if (picode->ic.hl.opcode == HLI_PUSH)
  866. {
  867. pushExpStk (picode->ic.hl.oper.exp);
  868. picode->invalidate();
  869. numHlIcodes--;
  870. }
  871. /* For HLI_CALL instructions that use arguments from the stack,
  872. * pop them from the expression stack and place them on the
  873. * procedure's argument list */
  874. if ((picode->ic.hl.opcode == HLI_CALL) &&
  875. ! (picode->ic.hl.oper.call.proc->flg & REG_ARGS))
  876. { Function * pp;
  877. Int cb, numArgs;
  878. boolT res;
  879. pp = picode->ic.hl.oper.call.proc;
  880. if (pp->flg & CALL_PASCAL)
  881. {
  882. cb = pp->cbParam; /* fixed # arguments */
  883. for (k = 0, numArgs = 0; k < cb; numArgs++)
  884. {
  885. exp = popExpStk();
  886. if (pp->flg & PROC_ISLIB) /* library function */
  887. {
  888. if (pp->args.numArgs > 0)
  889. adjustActArgType(exp, pp->args.sym[numArgs].type, this);
  890. res = newStkArg (picode, exp, picode->ic.ll.opcode, this);
  891. }
  892. else /* user function */
  893. {
  894. if (pp->args.numArgs >0)
  895. pp->args.adjustForArgType (numArgs,expType (exp, this));
  896. res = newStkArg (picode, exp,picode->ic.ll.opcode, this);
  897. }
  898. if (res == FALSE)
  899. k += hlTypeSize (exp, this);
  900. }
  901. }
  902. else /* CALL_C */
  903. {
  904. cb = picode->ic.hl.oper.call.args->cb;
  905. numArgs = 0;
  906. if (cb)
  907. for (k = 0; k < cb; numArgs++)
  908. processCArg (pp, this, picode, numArgs, &k);
  909. else if ((cb == 0) && (picode->ic.ll.flg & REST_STK))
  910. while (! emptyExpStk())
  911. {
  912. processCArg (pp, this, picode, numArgs, &k);
  913. numArgs++;
  914. }
  915. }
  916. }
  917. /* If we could not substitute the result of a function,
  918. * assign it to the corresponding registers */
  919. if ((picode->ic.hl.opcode == HLI_CALL) &&
  920. ((picode->ic.hl.oper.call.proc->flg & PROC_ISLIB) !=
  921. PROC_ISLIB) && (picode->du1.idx[0][0] == 0) &&
  922. (picode->du1.numRegsDef > 0))
  923. {
  924. exp = COND_EXPR::idFunc (picode->ic.hl.oper.call.proc,
  925. picode->ic.hl.oper.call.args);
  926. lhs = COND_EXPR::idID (&picode->ic.hl.oper.call.proc->retVal,
  927. &localId, j);
  928. picode->setAsgn(lhs, exp);
  929. }
  930. }
  931. }
  932. /* Store number of high-level icodes in current basic block */
  933. pbb->numHlIcodes = numHlIcodes;
  934. }
  935. }
  936. /* Invokes procedures related with data flow analysis. Works on a procedure
  937. * at a time basis.
  938. * Note: indirect recursion in liveRegAnalysis is possible. */
  939. void Function::dataFlow(dword liveOut)
  940. {
  941. boolT isAx, isBx, isCx, isDx;
  942. Int idx;
  943. /* Remove references to register variables */
  944. if (flg & SI_REGVAR)
  945. liveOut &= maskDuReg[rSI];
  946. if (flg & DI_REGVAR)
  947. liveOut &= maskDuReg[rDI];
  948. /* Function - return value register(s) */
  949. if (liveOut != 0)
  950. {
  951. flg |= PROC_IS_FUNC;
  952. isAx = (boolT)(liveOut & power2(rAX - rAX));
  953. isBx = (boolT)(liveOut & power2(rBX - rAX));
  954. isCx = (boolT)(liveOut & power2(rCX - rAX));
  955. isDx = (boolT)(liveOut & power2(rDX - rAX));
  956. if (isAx && isDx) /* long or pointer */
  957. {
  958. retVal.type = TYPE_LONG_SIGN;
  959. retVal.loc = REG_FRAME;
  960. retVal.id.longId.h = rDX;
  961. retVal.id.longId.l = rAX;
  962. idx = localId.newLongReg(TYPE_LONG_SIGN, rDX, rAX, 0);
  963. localId.propLongId (rAX, rDX, "\0");
  964. }
  965. else if (isAx || isBx || isCx || isDx) /* word */
  966. {
  967. retVal.type = TYPE_WORD_SIGN;
  968. retVal.loc = REG_FRAME;
  969. if (isAx)
  970. retVal.id.regi = rAX;
  971. else if (isBx)
  972. retVal.id.regi = rBX;
  973. else if (isCx)
  974. retVal.id.regi = rCX;
  975. else
  976. retVal.id.regi = rDX;
  977. idx = localId.newByteWordReg(TYPE_WORD_SIGN,retVal.id.regi);
  978. }
  979. }
  980. /* Data flow analysis */
  981. liveAnal = TRUE;
  982. elimCondCodes();
  983. genLiveKtes();
  984. liveRegAnalysis (liveOut); /* calls dataFlow() recursively */
  985. if (! (flg & PROC_ASM)) /* can generate C for pProc */
  986. {
  987. genDU1 (); /* generate def/use level 1 chain */
  988. findExps (); /* forward substitution algorithm */
  989. }
  990. }