dataflow.cpp 45 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194
  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. size_t 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. //lhs=rhs=_expr=0;
  107. for (i = 0; i < numBBs; i++)
  108. {
  109. pBB = m_dfsLast[i];
  110. if (pBB->flg & INVALID_BB)
  111. continue; /* Do not process invalid BBs */
  112. // auto v(pBB | boost::adaptors::reversed);
  113. // for (const ICODE &useAt : v)
  114. // {}
  115. for (useAt = pBB->rbegin(); useAt != pBB->rend(); useAt++)
  116. {
  117. llIcode useAtOp = llIcode(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(ICODE &insn : *pbb)
  230. {
  231. if ((insn.type == HIGH_LEVEL) && ( insn.valid() ))
  232. {
  233. liveUse |= (insn.du.use & ~def);
  234. def |= insn.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. for(TYPEADR_TYPE &e : pbb->edges)
  290. {
  291. pbb->liveOut |= e.BBptr->liveIn;
  292. }
  293. /* propagate to invoked procedure */
  294. if (pbb->nodeType == CALL_NODE)
  295. {
  296. ICODE &ticode(pbb->back());
  297. pcallee = ticode.hl()->call.proc;
  298. /* user/runtime routine */
  299. if (! (pcallee->flg & PROC_ISLIB))
  300. {
  301. if (pcallee->liveAnal == false) /* hasn't been processed */
  302. pcallee->dataFlow (pbb->liveOut);
  303. pbb->liveOut = pcallee->liveIn;
  304. }
  305. else /* library routine */
  306. {
  307. if ( (pcallee->flg & PROC_IS_FUNC) && /* returns a value */
  308. (pcallee->liveOut & pbb->edges[0].BBptr->liveIn).any()
  309. )
  310. pbb->liveOut = pcallee->liveOut;
  311. else
  312. pbb->liveOut = 0;
  313. }
  314. if ((! (pcallee->flg & PROC_ISLIB)) || (pbb->liveOut != 0))
  315. {
  316. switch (pcallee->retVal.type) {
  317. case TYPE_LONG_SIGN: case TYPE_LONG_UNSIGN:
  318. ticode.du1.numRegsDef = 2;
  319. break;
  320. case TYPE_WORD_SIGN: case TYPE_WORD_UNSIGN:
  321. case TYPE_BYTE_SIGN: case TYPE_BYTE_UNSIGN:
  322. ticode.du1.numRegsDef = 1;
  323. break;
  324. default:
  325. ticode.du1.numRegsDef = 0;
  326. fprintf(stderr,"Function::liveRegAnalysis : Unknown return type %d, assume 0\n",pcallee->retVal.type);
  327. } /*eos*/
  328. /* Propagate def/use results to calling icode */
  329. ticode.du.use = pcallee->liveIn;
  330. ticode.du.def = pcallee->liveOut;
  331. }
  332. }
  333. }
  334. /* liveIn(b) = liveUse(b) U (liveOut(b) - def(b) */
  335. pbb->liveIn = pbb->liveUse | (pbb->liveOut & ~pbb->def);
  336. /* Check if live sets have been modified */
  337. if ((prevLiveIn != pbb->liveIn) || (prevLiveOut != pbb->liveOut))
  338. change = true;
  339. }
  340. }
  341. /* Propagate liveIn(b) to procedure header */
  342. if (pbb->liveIn != 0) /* uses registers */
  343. liveIn = pbb->liveIn;
  344. /* Remove any references to register variables */
  345. if (flg & SI_REGVAR)
  346. {
  347. liveIn &= maskDuReg[rSI];
  348. pbb->liveIn &= maskDuReg[rSI];
  349. }
  350. if (flg & DI_REGVAR)
  351. {
  352. liveIn &= maskDuReg[rDI];
  353. pbb->liveIn &= maskDuReg[rDI];
  354. }
  355. }
  356. void BB::genDU1()
  357. {
  358. eReg regi; /* Register that was defined */
  359. int k, defRegIdx, useIdx;
  360. iICODE picode, ticode,lastInst;
  361. BB *tbb; /* Target basic block */
  362. bool res;
  363. //COND_EXPR *e
  364. /* Process each register definition of a HIGH_LEVEL icode instruction.
  365. * Note that register variables should not be considered registers.
  366. */
  367. assert(0!=Parent);
  368. lastInst = this->end();
  369. for (picode = this->begin(); picode != lastInst; picode++)
  370. {
  371. if (picode->type != HIGH_LEVEL)
  372. continue;
  373. regi = rUNDEF;
  374. defRegIdx = 0;
  375. // foreach defined register
  376. bitset<32> processed=0;
  377. for (k = 0; k < INDEX_BX_SI; k++)
  378. {
  379. if (not picode->du.def.test(k))
  380. continue;
  381. //printf("Processing reg")
  382. processed |= duReg[k];
  383. regi = (eReg)(k + 1); /* defined register */
  384. picode->du1.regi[defRegIdx] = regi;
  385. /* Check remaining instructions of the BB for all uses
  386. * of register regi, before any definitions of the
  387. * register */
  388. if ((regi == rDI) && (flg & DI_REGVAR))
  389. continue;
  390. if ((regi == rSI) && (flg & SI_REGVAR))
  391. continue;
  392. if (distance(picode,lastInst)>1) /* several instructions */
  393. {
  394. useIdx = 0;
  395. for (auto ricode = ++iICODE(picode); ricode != lastInst; ricode++)
  396. {
  397. ticode=ricode;
  398. if (ricode->type != HIGH_LEVEL) // Only check uses of HIGH_LEVEL icodes
  399. continue;
  400. /* if used, get icode index */
  401. if ((ricode->du.use & duReg[regi]).any())
  402. picode->du1.recordUse(defRegIdx,ricode);
  403. /* if defined, stop finding uses for this reg */
  404. if ((ricode->du.def & duReg[regi]).any())
  405. break;
  406. }
  407. /* Check if last definition of this register */
  408. if ((not (ticode->du.def & duReg[regi]).any()) and (this->liveOut & duReg[regi]).any())
  409. picode->du.lastDefRegi |= duReg[regi];
  410. }
  411. else /* only 1 instruction in this basic block */
  412. {
  413. /* Check if last definition of this register */
  414. if ((this->liveOut & duReg[regi]).any())
  415. picode->du.lastDefRegi |= duReg[regi];
  416. }
  417. /* Find target icode for HLI_CALL icodes to procedures
  418. * that are functions. The target icode is in the
  419. * next basic block (unoptimized code) or somewhere else
  420. * on optimized code. */
  421. if ((picode->hl()->opcode == HLI_CALL) &&
  422. (picode->hl()->call.proc->flg & PROC_IS_FUNC))
  423. {
  424. tbb = this->edges[0].BBptr;
  425. for (ticode = tbb->begin(); ticode != tbb->end(); ticode++)
  426. {
  427. if (ticode->type != HIGH_LEVEL)
  428. continue;
  429. /* if used, get icode index */
  430. if ((ticode->du.use & duReg[regi]).any())
  431. picode->du1.recordUse(defRegIdx,ticode);
  432. /* if defined, stop finding uses for this reg */
  433. if ((ticode->du.def & duReg[regi]).any())
  434. break;
  435. }
  436. /* if not used in this basic block, check if the
  437. * register is live out, if so, make it the last
  438. * definition of this register */
  439. if ( picode->du1.used(defRegIdx) && (tbb->liveOut & duReg[regi]).any())
  440. picode->du.lastDefRegi |= duReg[regi];
  441. }
  442. /* If not used within this bb or in successors of this
  443. * bb (ie. not in liveOut), then register is useless,
  444. * thus remove it. Also check that this is not a return
  445. * from a library function (routines such as printf
  446. * return an integer, which is normally not taken into
  447. * account by the programmer). */
  448. if (picode->valid() and not picode->du1.used(defRegIdx) and
  449. (not (picode->du.lastDefRegi & duReg[regi]).any()) &&
  450. (not ((picode->hl()->opcode == HLI_CALL) &&
  451. (picode->hl()->call.proc->flg & PROC_ISLIB))))
  452. {
  453. if (! (this->liveOut & duReg[regi]).any()) /* not liveOut */
  454. {
  455. res = picode->removeDefRegi (regi, defRegIdx+1,&Parent->localId);
  456. if (res != true)
  457. {
  458. defRegIdx++;
  459. continue;
  460. }
  461. /* Backpatch any uses of this instruction, within
  462. * the same BB, if the instruction was invalidated */
  463. for (auto back_patch_at = riICODE(picode); back_patch_at != rend(); back_patch_at++)
  464. {
  465. back_patch_at->du1.remove(0,picode);
  466. }
  467. }
  468. else /* liveOut */
  469. picode->du.lastDefRegi |= duReg[regi];
  470. }
  471. defRegIdx++;
  472. /* Check if all defined registers have been processed */
  473. if ((defRegIdx >= picode->du1.numRegsDef) || (defRegIdx == MAX_REGS_DEF))
  474. break;
  475. }
  476. }
  477. }
  478. /* Generates the du chain of each instruction in a basic block */
  479. void Function::genDU1 ()
  480. {
  481. /* Traverse tree in dfsLast order */
  482. assert(m_dfsLast.size()==numBBs);
  483. for(BB *pbb : m_dfsLast)
  484. {
  485. if (pbb->flg & INVALID_BB)
  486. continue;
  487. pbb->genDU1();
  488. }
  489. }
  490. /* Substitutes the rhs (or lhs if rhs not possible) of ticode for the rhs
  491. * of picode. */
  492. static void forwardSubs (COND_EXPR *lhs, COND_EXPR *rhs, iICODE picode,
  493. iICODE ticode, LOCAL_ID *locsym, int &numHlIcodes)
  494. {
  495. boolT res;
  496. if (rhs == NULL) /* In case expression popped is NULL */
  497. return;
  498. /* Insert on rhs of ticode, if possible */
  499. res = COND_EXPR::insertSubTreeReg (ticode->hl()->asgn.rhs,rhs,
  500. locsym->id_arr[lhs->expr.ident.idNode.regiIdx].id.regi,
  501. locsym);
  502. if (res)
  503. {
  504. picode->invalidate();
  505. numHlIcodes--;
  506. }
  507. else
  508. {
  509. /* Try to insert it on lhs of ticode*/
  510. res = COND_EXPR::insertSubTreeReg (ticode->hl()->asgn.lhs,rhs,
  511. locsym->id_arr[lhs->expr.ident.idNode.regiIdx].id.regi,
  512. locsym);
  513. if (res)
  514. {
  515. picode->invalidate();
  516. numHlIcodes--;
  517. }
  518. }
  519. }
  520. /* Substitutes the rhs (or lhs if rhs not possible) of ticode for the
  521. * expression exp given */
  522. static void forwardSubsLong (int longIdx, COND_EXPR *_exp, iICODE picode, iICODE ticode, int *numHlIcodes)
  523. {
  524. bool res;
  525. if (_exp == NULL) /* In case expression popped is NULL */
  526. return;
  527. /* Insert on rhs of ticode, if possible */
  528. res = COND_EXPR::insertSubTreeLongReg (_exp, &ticode->hl()->asgn.rhs, longIdx);
  529. if (res)
  530. {
  531. picode->invalidate();
  532. (*numHlIcodes)--;
  533. }
  534. else
  535. {
  536. /* Try to insert it on lhs of ticode*/
  537. res = COND_EXPR::insertSubTreeLongReg (_exp, &ticode->hl()->asgn.lhs, longIdx);
  538. if (res)
  539. {
  540. picode->invalidate();
  541. (*numHlIcodes)--;
  542. }
  543. }
  544. }
  545. /* Returns whether the elements of the expression rhs are all x-clear from
  546. * instruction f up to instruction t. */
  547. bool COND_EXPR::xClear (iICODE f, iICODE t, iICODE lastBBinst, Function * pproc)
  548. {
  549. iICODE i;
  550. boolT res;
  551. uint8_t regi;
  552. switch (type)
  553. {
  554. case IDENTIFIER:
  555. if (expr.ident.idType == REGISTER)
  556. {
  557. regi= pproc->localId.id_arr[expr.ident.idNode.regiIdx].id.regi;
  558. for (i = ++iICODE(f); (i != lastBBinst) && (i!=t); i++)
  559. if ((i->type == HIGH_LEVEL) && ( i->valid() ))
  560. {
  561. if ((i->du.def & duReg[regi]).any())
  562. return false;
  563. }
  564. if (i != lastBBinst)
  565. return true;
  566. return false;
  567. }
  568. else
  569. return true;
  570. /* else if (rhs->expr.ident.idType == LONG_VAR)
  571. {
  572. missing all other identifiers ****
  573. } */
  574. case BOOLEAN_OP:
  575. if(0==rhs())
  576. return false;
  577. res = rhs()->xClear ( f, t, lastBBinst, pproc);
  578. if (res == FALSE)
  579. return false;
  580. if(0==lhs())
  581. return false;
  582. return lhs()->xClear ( f, t, lastBBinst, pproc);
  583. case NEGATION:
  584. case ADDRESSOF:
  585. case DEREFERENCE:
  586. if(0==expr.unaryExp)
  587. return false;
  588. return expr.unaryExp->xClear ( f, t, lastBBinst, pproc);
  589. } /* eos */
  590. return false;
  591. }
  592. bool UnaryOperator::xClear(iICODE f, iICODE t, iICODE lastBBinst, Function *pproc)
  593. {
  594. if(0==unaryExp)
  595. return false;
  596. return unaryExp->xClear ( f, t, lastBBinst, pproc);
  597. }
  598. bool BinaryOperator::xClear(iICODE f, iICODE t, iICODE lastBBinst, Function *pproc)
  599. {
  600. if(0==m_rhs)
  601. return false;
  602. if ( ! m_rhs->xClear (f, t, lastBBinst, pproc) )
  603. return false;
  604. if(0==m_lhs)
  605. return false;
  606. return m_lhs->xClear (f, t, lastBBinst, pproc);
  607. }
  608. /* Checks the type of the formal argument as against to the actual argument,
  609. * whenever possible, and then places the actual argument on the procedure's
  610. * argument list. */
  611. /// @returns the type size of the stored Arg
  612. static int processCArg (Function * pp, Function * pProc, ICODE * picode, int numArgs)
  613. {
  614. COND_EXPR *_exp;
  615. bool res;
  616. /* if (numArgs == 0)
  617. return; */
  618. _exp = g_exp_stk.pop();
  619. if (pp->flg & PROC_ISLIB) /* library function */
  620. {
  621. if (pp->args.numArgs > 0)
  622. if (pp->flg & PROC_VARARG)
  623. {
  624. if (numArgs < pp->args.sym.size())
  625. adjustActArgType (_exp, pp->args.sym[numArgs].type, pProc);
  626. }
  627. else
  628. adjustActArgType (_exp, pp->args.sym[numArgs].type, pProc);
  629. }
  630. else /* user function */
  631. {
  632. if (pp->args.numArgs > 0)
  633. pp->args.adjustForArgType (numArgs, expType (_exp, pProc));
  634. }
  635. res = picode->newStkArg (_exp, (llIcode)picode->ll()->getOpcode(), pProc);
  636. /* Do not update the size of k if the expression was a segment register
  637. * in a near call */
  638. if (res == false)
  639. return hlTypeSize (_exp, pProc);
  640. return 0; // be default we do not know the size of the argument
  641. }
  642. /** Eliminates extraneous intermediate icode instructions when finding
  643. * expressions. Generates new hlIcodes in the form of expression trees.
  644. * For HLI_CALL hlIcodes, places the arguments in the argument list. */
  645. void Function::processTargetIcode(iICODE picode, int &numHlIcodes, iICODE ticode,bool isLong)
  646. {
  647. boolT res;
  648. switch (ticode->hl()->opcode) {
  649. case HLI_ASSIGN:
  650. if(isLong)
  651. {
  652. forwardSubsLong (picode->hl()->asgn.lhs->expr.ident.idNode.longIdx,
  653. picode->hl()->asgn.rhs, picode,ticode,
  654. &numHlIcodes);
  655. }
  656. else
  657. forwardSubs (picode->hl()->asgn.lhs, picode->hl()->asgn.rhs,
  658. picode, ticode, &localId, numHlIcodes);
  659. break;
  660. case HLI_JCOND: case HLI_PUSH: case HLI_RET:
  661. if(isLong)
  662. {
  663. res = COND_EXPR::insertSubTreeLongReg (
  664. picode->hl()->asgn.rhs,
  665. &ticode->hl()->exp.v,
  666. picode->hl()->asgn.lhs->expr.ident.idNode.longIdx);
  667. }
  668. else
  669. {
  670. res = COND_EXPR::insertSubTreeReg (
  671. ticode->hl()->exp.v,
  672. picode->hl()->asgn.rhs,
  673. localId.id_arr[picode->hl()->asgn.lhs->expr.ident.idNode.regiIdx].id.regi,
  674. &localId);
  675. }
  676. if (res)
  677. {
  678. picode->invalidate();
  679. numHlIcodes--;
  680. }
  681. break;
  682. case HLI_CALL: /* register arguments */
  683. newRegArg ( picode, ticode);
  684. picode->invalidate();
  685. numHlIcodes--;
  686. break;
  687. }
  688. }
  689. void Function::processHliCall(COND_EXPR *_exp, iICODE picode)
  690. {
  691. Function * pp;
  692. int cb, numArgs;
  693. boolT res;
  694. int k;
  695. pp = picode->hl()->call.proc;
  696. if (pp->flg & CALL_PASCAL)
  697. {
  698. cb = pp->cbParam; /* fixed # arguments */
  699. k = 0;
  700. numArgs = 0;
  701. while(k<cb)
  702. {
  703. _exp = g_exp_stk.pop();
  704. if (pp->flg & PROC_ISLIB) /* library function */
  705. {
  706. if (pp->args.numArgs > 0)
  707. adjustActArgType(_exp, pp->args.sym[numArgs].type, this);
  708. res = picode->newStkArg (_exp, (llIcode)picode->ll()->getOpcode(), this);
  709. }
  710. else /* user function */
  711. {
  712. if (pp->args.numArgs >0)
  713. pp->args.adjustForArgType (numArgs,expType (_exp, this));
  714. res = picode->newStkArg (_exp,(llIcode)picode->ll()->getOpcode(), this);
  715. }
  716. if (res == FALSE)
  717. k += hlTypeSize (_exp, this);
  718. numArgs++;
  719. }
  720. }
  721. else /* CALL_C */
  722. {
  723. cb = picode->hl()->call.args->cb;
  724. numArgs = 0;
  725. k = 0;
  726. if (cb)
  727. {
  728. while ( k < cb )
  729. {
  730. k+=processCArg (pp, this, &(*picode), numArgs);
  731. numArgs++;
  732. }
  733. }
  734. else if ((cb == 0) && picode->ll()->testFlags(REST_STK))
  735. {
  736. while (! g_exp_stk.empty())
  737. {
  738. k+=processCArg (pp, this, &(*picode), numArgs);
  739. numArgs++;
  740. }
  741. }
  742. }
  743. }
  744. void Function::findExps()
  745. {
  746. int i, numHlIcodes;
  747. iICODE
  748. picode, // Current icode */
  749. ticode; // Target icode */
  750. BB * pbb; // Current and next basic block */
  751. boolT res;
  752. COND_EXPR *_exp, // expression pointer - for HLI_POP and HLI_CALL */
  753. *lhs; // exp ptr for return value of a HLI_CALL */
  754. //STKFRAME * args; // pointer to arguments - for HLI_CALL */
  755. uint8_t regi; // register(s) to be forward substituted */
  756. ID *_retVal; // function return value
  757. /* Initialize expression stack */
  758. g_exp_stk.init();
  759. _exp = 0;
  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. numHlIcodes = 0;
  768. for (picode = pbb->begin(); picode != pbb->end(); picode++)
  769. {
  770. if ((picode->type != HIGH_LEVEL) || ( ! picode->valid() ))
  771. continue;
  772. numHlIcodes++;
  773. if (picode->du1.numRegsDef == 1) /* uint8_t/uint16_t regs */
  774. {
  775. /* Check for only one use of this register. If this is
  776. * the last definition of the register in this BB, check
  777. * that it is not liveOut from this basic block */
  778. if (picode->du1.numUses(0)==1)
  779. {
  780. /* Check that this register is not liveOut, if it
  781. * is the last definition of the register */
  782. regi = picode->du1.regi[0];
  783. /* Check if we can forward substitute this register */
  784. switch (picode->hl()->opcode)
  785. {
  786. case HLI_ASSIGN:
  787. /* Replace rhs of current icode into target
  788. * icode expression */
  789. ticode = picode->du1.idx[0].uses.front();
  790. if ((picode->du.lastDefRegi & duReg[regi]).any() &&
  791. ((ticode->hl()->opcode != HLI_CALL) &&
  792. (ticode->hl()->opcode != HLI_RET)))
  793. continue;
  794. if (picode->hl()->asgn.rhs->xClear (picode,
  795. picode->du1.idx[0].uses[0], pbb->end(), this))
  796. {
  797. processTargetIcode(picode, numHlIcodes, ticode,false);
  798. }
  799. break;
  800. case HLI_POP:
  801. ticode = picode->du1.idx[0].uses.front();
  802. if ((picode->du.lastDefRegi & duReg[regi]).any() &&
  803. ((ticode->hl()->opcode != HLI_CALL) &&
  804. (ticode->hl()->opcode != HLI_RET)))
  805. continue;
  806. _exp = g_exp_stk.pop(); /* pop last exp pushed */
  807. switch (ticode->hl()->opcode) {
  808. case HLI_ASSIGN:
  809. forwardSubs (picode->hl()->expr(), _exp,
  810. picode, ticode, &localId,
  811. numHlIcodes);
  812. break;
  813. case HLI_JCOND: case HLI_PUSH: case HLI_RET:
  814. res = COND_EXPR::insertSubTreeReg (ticode->hl()->exp.v,
  815. _exp,
  816. localId.id_arr[picode->hl()->expr()->expr.ident.idNode.regiIdx].id.regi,
  817. &localId);
  818. if (res)
  819. {
  820. picode->invalidate();
  821. numHlIcodes--;
  822. }
  823. break;
  824. /****case HLI_CALL: /* register arguments
  825. newRegArg (pProc, picode, ticode);
  826. picode->invalidate();
  827. numHlIcodes--;
  828. break; */
  829. } /* eos */
  830. break;
  831. case HLI_CALL:
  832. ticode = picode->du1.idx[0].uses.front();
  833. HLTYPE *ti_hl(ticode->hl());
  834. _retVal = &picode->hl()->call.proc->retVal;
  835. switch (ti_hl->opcode) {
  836. case HLI_ASSIGN:
  837. assert(ti_hl->asgn.rhs);
  838. _exp = COND_EXPR::idFunc ( picode->hl()->call.proc, picode->hl()->call.args);
  839. res = COND_EXPR::insertSubTreeReg (ti_hl->asgn.rhs,_exp, _retVal->id.regi, &localId);
  840. if (! res)
  841. COND_EXPR::insertSubTreeReg (ti_hl->asgn.lhs, _exp,_retVal->id.regi, &localId);
  842. //TODO: HERE missing: 2 regs
  843. picode->invalidate();
  844. numHlIcodes--;
  845. break;
  846. case HLI_PUSH: case HLI_RET:
  847. ti_hl->expr( COND_EXPR::idFunc ( picode->hl()->call.proc, picode->hl()->call.args) );
  848. picode->invalidate();
  849. numHlIcodes--;
  850. break;
  851. case HLI_JCOND:
  852. _exp = COND_EXPR::idFunc ( picode->hl()->call.proc, picode->hl()->call.args);
  853. res = COND_EXPR::insertSubTreeReg (ti_hl->exp.v, _exp, _retVal->id.regi, &localId);
  854. if (res) /* was substituted */
  855. {
  856. picode->invalidate();
  857. numHlIcodes--;
  858. }
  859. else /* cannot substitute function */
  860. {
  861. //picode->loc_ip
  862. lhs = COND_EXPR::idID(_retVal,&localId,picode);
  863. picode->setAsgn(lhs, _exp);
  864. }
  865. break;
  866. } /* eos */
  867. break;
  868. } /* eos */
  869. }
  870. }
  871. else if (picode->du1.numRegsDef == 2) /* long regs */
  872. {
  873. /* Check for only one use of these registers */
  874. if ((picode->du1.numUses(0) == 1) and (picode->du1.numUses(1) == 1))
  875. {
  876. regi = picode->du1.regi[0]; //TODO: verify that regi actually should be assigned this
  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. processHliCall(_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. /* Store number of high-level icodes in current basic block */
  988. pbb->numHlIcodes = numHlIcodes;
  989. }
  990. }
  991. /** Invokes procedures related with data flow analysis. Works on a procedure
  992. * at a time basis.
  993. * Note: indirect recursion in liveRegAnalysis is possible. */
  994. void Function::dataFlow(std::bitset<32> &_liveOut)
  995. {
  996. bool isAx, isBx, isCx, isDx;
  997. int idx;
  998. /* Remove references to register variables */
  999. if (flg & SI_REGVAR)
  1000. _liveOut &= maskDuReg[rSI];
  1001. if (flg & DI_REGVAR)
  1002. _liveOut &= maskDuReg[rDI];
  1003. /* Function - return value register(s) */
  1004. if (_liveOut.any())
  1005. {
  1006. flg |= PROC_IS_FUNC;
  1007. isAx = _liveOut.test(rAX - rAX);
  1008. isBx = _liveOut.test(rBX - rAX);
  1009. isCx = _liveOut.test(rCX - rAX);
  1010. isDx = _liveOut.test(rDX - rAX);
  1011. bool isAL = !isAx && _liveOut.test(rAL - rAX);
  1012. bool isAH = !isAx && _liveOut.test(rAH - rAX);
  1013. bool isBL = !isBx && _liveOut.test(rBL - rAX);
  1014. bool isBH = !isBx && _liveOut.test(rBH - rAX);
  1015. bool isCL = !isCx && _liveOut.test(rCL - rAX);
  1016. bool isCH = !isCx && _liveOut.test(rCH - rAX);
  1017. bool isDL = !isDx && _liveOut.test(rDL - rAX);
  1018. bool isDH = !isDx && _liveOut.test(rDH - rAX);
  1019. if(isAL && isAH)
  1020. {
  1021. isAx = true;
  1022. printf("**************************************************************************** dataFlow Join discovered Ax\n");
  1023. isAH=isAL=false;
  1024. }
  1025. if(isDL && isDH)
  1026. {
  1027. isDx = true;
  1028. printf("**************************************************************************** dataFlow Join discovered Dx\n");
  1029. isDH=isDL=false;
  1030. }
  1031. if(isBL && isBH)
  1032. {
  1033. isBx = true;
  1034. printf("**************************************************************************** dataFlow Join discovered Dx\n");
  1035. isBH=isBL=false;
  1036. }
  1037. if(isCL && isCH)
  1038. {
  1039. isCx = true;
  1040. printf("**************************************************************************** dataFlow Join discovered Dx\n");
  1041. isCH=isCL=false;
  1042. }
  1043. if (isAx && isDx) /* long or pointer */
  1044. {
  1045. retVal.type = TYPE_LONG_SIGN;
  1046. retVal.loc = REG_FRAME;
  1047. retVal.id.longId.h = rDX;
  1048. retVal.id.longId.l = rAX;
  1049. idx = localId.newLongReg(TYPE_LONG_SIGN, rDX, rAX, Icode.begin()/*0*/);
  1050. localId.propLongId (rAX, rDX, "\0");
  1051. }
  1052. else if (isAx || isBx || isCx || isDx) /* uint16_t */
  1053. {
  1054. retVal.type = TYPE_WORD_SIGN;
  1055. retVal.loc = REG_FRAME;
  1056. if (isAx)
  1057. retVal.id.regi = rAX;
  1058. else if (isBx)
  1059. retVal.id.regi = rBX;
  1060. else if (isCx)
  1061. retVal.id.regi = rCX;
  1062. else
  1063. retVal.id.regi = rDX;
  1064. idx = localId.newByteWordReg(TYPE_WORD_SIGN,retVal.id.regi);
  1065. }
  1066. else if(isAL||isBL||isCL||isDL)
  1067. {
  1068. printf("**************************************************************************** AL/DL return \n");
  1069. retVal.type = TYPE_BYTE_SIGN;
  1070. retVal.loc = REG_FRAME;
  1071. if (isAL)
  1072. retVal.id.regi = rAL;
  1073. else if (isBL)
  1074. retVal.id.regi = rBL;
  1075. else if (isCL)
  1076. retVal.id.regi = rCL;
  1077. else
  1078. retVal.id.regi = rDL;
  1079. idx = localId.newByteWordReg(TYPE_BYTE_SIGN,retVal.id.regi);
  1080. }
  1081. }
  1082. /* Data flow analysis */
  1083. liveAnal = true;
  1084. elimCondCodes();
  1085. genLiveKtes();
  1086. liveRegAnalysis (_liveOut); /* calls dataFlow() recursively */
  1087. if (! (flg & PROC_ASM)) /* can generate C for pProc */
  1088. {
  1089. genDU1 (); /* generate def/use level 1 chain */
  1090. findExps (); /* forward substitution algorithm */
  1091. }
  1092. }