dataflow.cpp 43 KB

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