dataflow.cpp 47 KB

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