dataflow.cpp 44 KB

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