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