dataflow.cpp 46 KB

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