dataflow.cpp 47 KB

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