dataflow.cpp 48 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 (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. 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->length == 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. for (i = 0; i < numBBs; i++)
  295. {
  296. pbb = dfsLast[i];
  297. if (pbb->flg & INVALID_BB) continue;
  298. /* Process each register definition of a HIGH_LEVEL icode instruction.
  299. * Note that register variables should not be considered registers.
  300. */
  301. lastInst = pbb->end2();
  302. for (picode = pbb->begin2(); picode != lastInst; picode++)
  303. {
  304. if (picode->type == HIGH_LEVEL)
  305. {
  306. regi = 0;
  307. defRegIdx = 0;
  308. for (k = 0; k < INDEXBASE; k++)
  309. {
  310. if ((picode->du.def & power2(k)) != 0)
  311. {
  312. regi = (byte)(k + 1); /* defined register */
  313. picode->du1.regi[defRegIdx] = regi;
  314. /* Check remaining instructions of the BB for all uses
  315. * of register regi, before any definitions of the
  316. * register */
  317. if ((regi == rDI) && (flg & DI_REGVAR))
  318. continue;
  319. if ((regi == rSI) && (flg & SI_REGVAR))
  320. continue;
  321. if ((picode + 1) != lastInst) /* several instructions */
  322. {
  323. useIdx = 0;
  324. for (auto ricode = picode + 1; ricode != lastInst; ricode++)
  325. {
  326. ticode=ricode;
  327. /* Only check uses of HIGH_LEVEL icodes */
  328. if (ricode->type == HIGH_LEVEL)
  329. {
  330. /* if used, get icode index */
  331. if (ricode->du.use & duReg[regi])
  332. picode->du1.idx[defRegIdx][useIdx++] = ricode->loc_ip;
  333. /* if defined, stop finding uses for this reg */
  334. if (ricode->du.def & duReg[regi])
  335. break;
  336. }
  337. }
  338. /* Check if last definition of this register */
  339. if ((! (ticode->du.def & duReg[regi])) && (pbb->liveOut & duReg[regi]))
  340. picode->du.lastDefRegi |= duReg[regi];
  341. }
  342. else /* only 1 instruction in this basic block */
  343. {
  344. /* Check if last definition of this register */
  345. if (pbb->liveOut & duReg[regi])
  346. picode->du.lastDefRegi |= duReg[regi];
  347. }
  348. /* Find target icode for HLI_CALL icodes to procedures
  349. * that are functions. The target icode is in the
  350. * next basic block (unoptimized code) or somewhere else
  351. * on optimized code. */
  352. if ((picode->ic.hl.opcode == HLI_CALL) &&
  353. (picode->ic.hl.oper.call.proc->flg & PROC_IS_FUNC))
  354. {
  355. tbb = pbb->edges[0].BBptr;
  356. useIdx = 0;
  357. for (ticode = tbb->begin2(); ticode != tbb->end2(); ticode++)
  358. {
  359. if (ticode->type == HIGH_LEVEL)
  360. {
  361. /* if used, get icode index */
  362. if (ticode->du.use & duReg[regi])
  363. picode->du1.idx[defRegIdx][useIdx++] = ticode->loc_ip;
  364. /* if defined, stop finding uses for this reg */
  365. if (ticode->du.def & duReg[regi])
  366. break;
  367. }
  368. }
  369. /* if not used in this basic block, check if the
  370. * register is live out, if so, make it the last
  371. * definition of this register */
  372. if ((picode->du1.idx[defRegIdx][useIdx] == 0) &&
  373. (tbb->liveOut & duReg[regi]))
  374. picode->du.lastDefRegi |= duReg[regi];
  375. }
  376. /* If not used within this bb or in successors of this
  377. * bb (ie. not in liveOut), then register is useless,
  378. * thus remove it. Also check that this is not a return
  379. * from a library function (routines such as printf
  380. * return an integer, which is normally not taken into
  381. * account by the programmer). */
  382. if ((picode->invalid == FALSE) &&
  383. (picode->du1.idx[defRegIdx][0] == 0) &&
  384. (! (picode->du.lastDefRegi & duReg[regi])) &&
  385. // (! ((picode->ic.hl.opcode != HLI_CALL) &&
  386. (! ((picode->ic.hl.opcode == HLI_CALL) &&
  387. (picode->ic.hl.oper.call.proc->flg & PROC_ISLIB))))
  388. {
  389. if (! (pbb->liveOut & duReg[regi])) /* not liveOut */
  390. {
  391. res = picode->removeDefRegi (regi, defRegIdx+1,&localId);
  392. /* Backpatch any uses of this instruction, within
  393. * the same BB, if the instruction was invalidated */
  394. if (res == TRUE)
  395. for (auto ticode = riICODE(picode); ticode != pbb->rend2(); ticode++)
  396. {
  397. for (int n = 0; n < MAX_USES; n++)
  398. {
  399. if (ticode->du1.idx[0][n] == picode->loc_ip)
  400. {
  401. if (n < MAX_USES - 1)
  402. {
  403. memmove (&ticode->du1.idx[0][n],
  404. &ticode->du1.idx[0][n+1],
  405. (size_t)((MAX_USES - n - 1) * sizeof(Int)));
  406. n--;
  407. }
  408. ticode->du1.idx[0][MAX_USES - 1] = 0;
  409. }
  410. }
  411. }
  412. }
  413. else /* liveOut */
  414. picode->du.lastDefRegi |= duReg[regi];
  415. }
  416. defRegIdx++;
  417. /* Check if all defined registers have been processed */
  418. if ((defRegIdx >= picode->du1.numRegsDef) ||
  419. (defRegIdx == MAX_REGS_DEF))
  420. break;
  421. }
  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, Int f, Int t, Int lastBBinst, Function * pproc)
  485. { Int i;
  486. boolT res;
  487. byte regi;
  488. ICODE * picode;
  489. if (rhs == NULL)
  490. return false;
  491. switch (rhs->type) {
  492. case IDENTIFIER:
  493. if (rhs->expr.ident.idType == REGISTER)
  494. {
  495. picode = &pproc->Icode.front();
  496. regi= pproc->localId.id_arr[rhs->expr.ident.idNode.regiIdx].id.regi;
  497. for (i = (f + 1); (i < lastBBinst) && (i < t); i++)
  498. if ((picode[i].type == HIGH_LEVEL) &&
  499. (picode[i].invalid == FALSE))
  500. {
  501. if (picode[i].du.def & duReg[regi])
  502. return false;
  503. }
  504. if (i < lastBBinst)
  505. return true;
  506. else
  507. return false;
  508. }
  509. else
  510. return true;
  511. /* else if (rhs->expr.ident.idType == LONG_VAR)
  512. {
  513. missing all other identifiers ****
  514. } */
  515. case BOOLEAN_OP:
  516. res = xClear (rhs->expr.boolExpr.rhs, f, t, lastBBinst, pproc);
  517. if (res == FALSE)
  518. return false;
  519. return (xClear (rhs->expr.boolExpr.lhs, f, t, lastBBinst, pproc));
  520. case NEGATION:
  521. case ADDRESSOF:
  522. case DEREFERENCE:
  523. return (xClear (rhs->expr.unaryExp, f, t, lastBBinst, pproc));
  524. } /* eos */
  525. return FALSE;
  526. }
  527. /* Checks the type of the formal argument as against to the actual argument,
  528. * whenever possible, and then places the actual argument on the procedure's
  529. * argument list. */
  530. static void processCArg (Function * pp, Function * pProc, ICODE * picode, Int numArgs, Int *k)
  531. {
  532. COND_EXPR *exp;
  533. boolT res;
  534. /* if (numArgs == 0)
  535. return; */
  536. exp = popExpStk();
  537. if (pp->flg & PROC_ISLIB) /* library function */
  538. {
  539. if (pp->args.numArgs > 0)
  540. if (pp->flg & PROC_VARARG)
  541. {
  542. if (numArgs < pp->args.sym.size())
  543. adjustActArgType (exp, pp->args.sym[numArgs].type, pProc);
  544. }
  545. else
  546. adjustActArgType (exp, pp->args.sym[numArgs].type, pProc);
  547. res = newStkArg (picode, exp, picode->ic.ll.opcode, pProc);
  548. }
  549. else /* user function */
  550. {
  551. if (pp->args.numArgs > 0)
  552. pp->args.adjustForArgType (numArgs, expType (exp, pProc));
  553. res = newStkArg (picode, exp, picode->ic.ll.opcode, pProc);
  554. }
  555. /* Do not update the size of k if the expression was a segment register
  556. * in a near call */
  557. if (res == FALSE)
  558. *k += hlTypeSize (exp, pProc);
  559. }
  560. /* Eliminates extraneous intermediate icode instructions when finding
  561. * expressions. Generates new hlIcodes in the form of expression trees.
  562. * For HLI_CALL hlIcodes, places the arguments in the argument list. */
  563. void Function::findExps()
  564. {
  565. Int i, j, k, lastInst, numHlIcodes;
  566. ICODE * 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) continue;
  583. lastInst = pbb->start + pbb->length;
  584. numHlIcodes = 0;
  585. for (j = pbb->start; j < lastInst; j++)
  586. {
  587. picode = Icode.GetIcode(j);
  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.GetIcode(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, j, picode->du1.idx[0][0], lastInst, this))
  613. {
  614. switch (ticode->ic.hl.opcode) {
  615. case HLI_ASSIGN:
  616. forwardSubs (picode->ic.hl.oper.asgn.lhs,
  617. picode->ic.hl.oper.asgn.rhs,
  618. picode, ticode, &localId,
  619. &numHlIcodes);
  620. break;
  621. case HLI_JCOND: case HLI_PUSH: case HLI_RET:
  622. res = insertSubTreeReg (
  623. picode->ic.hl.oper.asgn.rhs,
  624. &ticode->ic.hl.oper.exp,
  625. localId.id_arr[picode->ic.hl.oper.asgn.lhs->expr.ident.idNode.regiIdx].id.regi,
  626. &localId);
  627. if (res)
  628. {
  629. picode->invalidate();
  630. numHlIcodes--;
  631. }
  632. break;
  633. case HLI_CALL: /* register arguments */
  634. newRegArg (picode, ticode);
  635. picode->invalidate();
  636. numHlIcodes--;
  637. break;
  638. } /* eos */
  639. }
  640. break;
  641. case HLI_POP:
  642. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  643. if ((picode->du.lastDefRegi & duReg[regi]) &&
  644. ((ticode->ic.hl.opcode != HLI_CALL) &&
  645. (ticode->ic.hl.opcode != HLI_RET)))
  646. continue;
  647. exp = popExpStk(); /* pop last exp pushed */
  648. switch (ticode->ic.hl.opcode) {
  649. case HLI_ASSIGN:
  650. forwardSubs (picode->ic.hl.oper.exp, exp,
  651. picode, ticode, &localId,
  652. &numHlIcodes);
  653. break;
  654. case HLI_JCOND: case HLI_PUSH: case HLI_RET:
  655. res = insertSubTreeReg (exp,
  656. &ticode->ic.hl.oper.exp,
  657. localId.id_arr[picode->ic.hl.oper.exp->expr.ident.idNode.regiIdx].id.regi,
  658. &localId);
  659. if (res)
  660. {
  661. picode->invalidate();
  662. numHlIcodes--;
  663. }
  664. break;
  665. /****case HLI_CALL: /* register arguments
  666. newRegArg (pProc, picode, ticode);
  667. picode->invalidate();
  668. numHlIcodes--;
  669. break; */
  670. } /* eos */
  671. break;
  672. case HLI_CALL:
  673. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  674. switch (ticode->ic.hl.opcode) {
  675. case HLI_ASSIGN:
  676. exp = COND_EXPR::idFunc (
  677. picode->ic.hl.oper.call.proc,
  678. picode->ic.hl.oper.call.args);
  679. res = insertSubTreeReg (exp,
  680. &ticode->ic.hl.oper.asgn.rhs,
  681. picode->ic.hl.oper.call.proc->retVal.id.regi,
  682. &localId);
  683. if (! res)
  684. insertSubTreeReg (exp,
  685. &ticode->ic.hl.oper.asgn.lhs,
  686. picode->ic.hl.oper.call.proc->retVal.id.regi,
  687. &localId);
  688. /*** HERE missing: 2 regs ****/
  689. picode->invalidate();
  690. numHlIcodes--;
  691. break;
  692. case HLI_PUSH: case HLI_RET:
  693. exp = COND_EXPR::idFunc (
  694. picode->ic.hl.oper.call.proc,
  695. picode->ic.hl.oper.call.args);
  696. ticode->ic.hl.oper.exp = exp;
  697. picode->invalidate();
  698. numHlIcodes--;
  699. break;
  700. case HLI_JCOND:
  701. exp = COND_EXPR::idFunc (
  702. picode->ic.hl.oper.call.proc,
  703. picode->ic.hl.oper.call.args);
  704. retVal = &picode->ic.hl.oper.call.proc->retVal,
  705. res = insertSubTreeReg (exp,
  706. &ticode->ic.hl.oper.exp,
  707. retVal->id.regi, &localId);
  708. if (res) /* was substituted */
  709. {
  710. picode->invalidate();
  711. numHlIcodes--;
  712. }
  713. else /* cannot substitute function */
  714. {
  715. lhs = COND_EXPR::idID(retVal,&localId,j);
  716. picode->setAsgn(lhs, exp);
  717. }
  718. break;
  719. } /* eos */
  720. break;
  721. } /* eos */
  722. }
  723. }
  724. else if (picode->du1.numRegsDef == 2) /* long regs */
  725. {
  726. /* Check for only one use of these registers */
  727. if ((picode->du1.idx[0][0] != 0) &&
  728. (picode->du1.idx[0][1] == 0) &&
  729. (picode->du1.idx[1][0] != 0) &&
  730. (picode->du1.idx[1][1] == 0))
  731. {
  732. switch (picode->ic.hl.opcode) {
  733. case HLI_ASSIGN:
  734. /* Replace rhs of current icode into target
  735. * icode expression */
  736. if (picode->du1.idx[0][0] == picode->du1.idx[1][0])
  737. {
  738. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  739. if ((picode->du.lastDefRegi & duReg[regi]) &&
  740. ((ticode->ic.hl.opcode != HLI_CALL) &&
  741. (ticode->ic.hl.opcode != HLI_RET)))
  742. continue;
  743. switch (ticode->ic.hl.opcode) {
  744. case HLI_ASSIGN:
  745. forwardSubsLong (picode->ic.hl.oper.asgn.lhs->expr.ident.idNode.longIdx,
  746. picode->ic.hl.oper.asgn.rhs, picode,
  747. ticode, &numHlIcodes);
  748. break;
  749. case HLI_JCOND: case HLI_PUSH: case HLI_RET:
  750. res = insertSubTreeLongReg (
  751. picode->ic.hl.oper.asgn.rhs,
  752. &ticode->ic.hl.oper.exp,
  753. picode->ic.hl.oper.asgn.lhs->expr.ident.idNode.longIdx);
  754. if (res)
  755. {
  756. picode->invalidate();
  757. numHlIcodes--;
  758. }
  759. break;
  760. case HLI_CALL: /* register arguments */
  761. newRegArg ( picode, ticode);
  762. picode->invalidate();
  763. numHlIcodes--;
  764. break;
  765. } /* eos */
  766. }
  767. break;
  768. case HLI_POP:
  769. if (picode->du1.idx[0][0] == picode->du1.idx[1][0])
  770. {
  771. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  772. if ((picode->du.lastDefRegi & duReg[regi]) &&
  773. ((ticode->ic.hl.opcode != HLI_CALL) &&
  774. (ticode->ic.hl.opcode != HLI_RET)))
  775. continue;
  776. exp = popExpStk(); /* pop last exp pushed */
  777. switch (ticode->ic.hl.opcode) {
  778. case HLI_ASSIGN:
  779. forwardSubsLong (picode->ic.hl.oper.exp->expr.ident.idNode.longIdx,
  780. exp, picode, ticode, &numHlIcodes);
  781. break;
  782. case HLI_JCOND: case HLI_PUSH:
  783. res = insertSubTreeLongReg (exp,
  784. &ticode->ic.hl.oper.exp,
  785. picode->ic.hl.oper.asgn.lhs->expr.ident.idNode.longIdx);
  786. if (res)
  787. {
  788. picode->invalidate();
  789. numHlIcodes--;
  790. }
  791. break;
  792. case HLI_CALL: /*** missing ***/
  793. break;
  794. } /* eos */
  795. }
  796. break;
  797. case HLI_CALL: /* check for function return */
  798. ticode = Icode.GetIcode(picode->du1.idx[0][0]);
  799. switch (ticode->ic.hl.opcode)
  800. {
  801. case HLI_ASSIGN:
  802. exp = COND_EXPR::idFunc (
  803. picode->ic.hl.oper.call.proc,
  804. picode->ic.hl.oper.call.args);
  805. ticode->ic.hl.oper.asgn.lhs =
  806. COND_EXPR::idLong(&localId, DST, ticode,
  807. HIGH_FIRST, j, eDEF, 1);
  808. ticode->ic.hl.oper.asgn.rhs = exp;
  809. picode->invalidate();
  810. numHlIcodes--;
  811. break;
  812. case HLI_PUSH: case HLI_RET:
  813. exp = COND_EXPR::idFunc (
  814. picode->ic.hl.oper.call.proc,
  815. picode->ic.hl.oper.call.args);
  816. ticode->ic.hl.oper.exp = exp;
  817. picode->invalidate();
  818. numHlIcodes--;
  819. break;
  820. case HLI_JCOND:
  821. exp = COND_EXPR::idFunc (
  822. picode->ic.hl.oper.call.proc,
  823. picode->ic.hl.oper.call.args);
  824. retVal = &picode->ic.hl.oper.call.proc->retVal;
  825. res = insertSubTreeLongReg (exp,
  826. &ticode->ic.hl.oper.exp,
  827. localId.newLongReg
  828. (
  829. retVal->type, retVal->id.longId.h,
  830. retVal->id.longId.l, j));
  831. if (res) /* was substituted */
  832. {
  833. picode->invalidate();
  834. numHlIcodes--;
  835. }
  836. else /* cannot substitute function */
  837. {
  838. lhs = COND_EXPR::idID(retVal,&localId,j);
  839. picode->setAsgn(lhs, exp);
  840. }
  841. break;
  842. } /* eos */
  843. } /* eos */
  844. }
  845. }
  846. /* HLI_PUSH doesn't define any registers, only uses registers.
  847. * Push the associated expression to the register on the local
  848. * expression stack */
  849. else if (picode->ic.hl.opcode == HLI_PUSH)
  850. {
  851. pushExpStk (picode->ic.hl.oper.exp);
  852. picode->invalidate();
  853. numHlIcodes--;
  854. }
  855. /* For HLI_CALL instructions that use arguments from the stack,
  856. * pop them from the expression stack and place them on the
  857. * procedure's argument list */
  858. if ((picode->ic.hl.opcode == HLI_CALL) &&
  859. ! (picode->ic.hl.oper.call.proc->flg & REG_ARGS))
  860. { Function * pp;
  861. Int cb, numArgs;
  862. boolT res;
  863. pp = picode->ic.hl.oper.call.proc;
  864. if (pp->flg & CALL_PASCAL)
  865. {
  866. cb = pp->cbParam; /* fixed # arguments */
  867. for (k = 0, numArgs = 0; k < cb; numArgs++)
  868. {
  869. exp = popExpStk();
  870. if (pp->flg & PROC_ISLIB) /* library function */
  871. {
  872. if (pp->args.numArgs > 0)
  873. adjustActArgType(exp, pp->args.sym[numArgs].type, this);
  874. res = newStkArg (picode, exp, picode->ic.ll.opcode, this);
  875. }
  876. else /* user function */
  877. {
  878. if (pp->args.numArgs >0)
  879. pp->args.adjustForArgType (numArgs,expType (exp, this));
  880. res = newStkArg (picode, exp,picode->ic.ll.opcode, this);
  881. }
  882. if (res == FALSE)
  883. k += hlTypeSize (exp, this);
  884. }
  885. }
  886. else /* CALL_C */
  887. {
  888. cb = picode->ic.hl.oper.call.args->cb;
  889. numArgs = 0;
  890. if (cb)
  891. for (k = 0; k < cb; numArgs++)
  892. processCArg (pp, this, picode, numArgs, &k);
  893. else if ((cb == 0) && (picode->ic.ll.flg & REST_STK))
  894. while (! emptyExpStk())
  895. {
  896. processCArg (pp, this, picode, numArgs, &k);
  897. numArgs++;
  898. }
  899. }
  900. }
  901. /* If we could not substitute the result of a function,
  902. * assign it to the corresponding registers */
  903. if ((picode->ic.hl.opcode == HLI_CALL) &&
  904. ((picode->ic.hl.oper.call.proc->flg & PROC_ISLIB) !=
  905. PROC_ISLIB) && (picode->du1.idx[0][0] == 0) &&
  906. (picode->du1.numRegsDef > 0))
  907. {
  908. exp = COND_EXPR::idFunc (picode->ic.hl.oper.call.proc,
  909. picode->ic.hl.oper.call.args);
  910. lhs = COND_EXPR::idID (&picode->ic.hl.oper.call.proc->retVal,
  911. &localId, j);
  912. picode->setAsgn(lhs, exp);
  913. }
  914. }
  915. }
  916. /* Store number of high-level icodes in current basic block */
  917. pbb->numHlIcodes = numHlIcodes;
  918. }
  919. }
  920. /* Invokes procedures related with data flow analysis. Works on a procedure
  921. * at a time basis.
  922. * Note: indirect recursion in liveRegAnalysis is possible. */
  923. void Function::dataFlow(dword liveOut)
  924. {
  925. boolT isAx, isBx, isCx, isDx;
  926. Int idx;
  927. /* Remove references to register variables */
  928. if (flg & SI_REGVAR)
  929. liveOut &= maskDuReg[rSI];
  930. if (flg & DI_REGVAR)
  931. liveOut &= maskDuReg[rDI];
  932. /* Function - return value register(s) */
  933. if (liveOut != 0)
  934. {
  935. flg |= PROC_IS_FUNC;
  936. isAx = (boolT)(liveOut & power2(rAX - rAX));
  937. isBx = (boolT)(liveOut & power2(rBX - rAX));
  938. isCx = (boolT)(liveOut & power2(rCX - rAX));
  939. isDx = (boolT)(liveOut & power2(rDX - rAX));
  940. if (isAx && isDx) /* long or pointer */
  941. {
  942. retVal.type = TYPE_LONG_SIGN;
  943. retVal.loc = REG_FRAME;
  944. retVal.id.longId.h = rDX;
  945. retVal.id.longId.l = rAX;
  946. idx = localId.newLongReg(TYPE_LONG_SIGN, rDX, rAX, 0);
  947. localId.propLongId (rAX, rDX, "\0");
  948. }
  949. else if (isAx || isBx || isCx || isDx) /* word */
  950. {
  951. retVal.type = TYPE_WORD_SIGN;
  952. retVal.loc = REG_FRAME;
  953. if (isAx)
  954. retVal.id.regi = rAX;
  955. else if (isBx)
  956. retVal.id.regi = rBX;
  957. else if (isCx)
  958. retVal.id.regi = rCX;
  959. else
  960. retVal.id.regi = rDX;
  961. idx = localId.newByteWordReg(TYPE_WORD_SIGN,retVal.id.regi);
  962. }
  963. }
  964. /* Data flow analysis */
  965. liveAnal = TRUE;
  966. elimCondCodes();
  967. genLiveKtes();
  968. liveRegAnalysis (liveOut); /* calls dataFlow() recursively */
  969. if (! (flg & PROC_ASM)) /* can generate C for pProc */
  970. {
  971. genDU1 (); /* generate def/use level 1 chain */
  972. findExps (); /* forward substitution algorithm */
  973. }
  974. }