dataflow.cpp 45 KB

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