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