dataflow.cpp 43 KB

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