dataflow.cpp 47 KB

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