dataflow.cpp 44 KB

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