dataflow.cpp 45 KB

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