dataflow.cpp 45 KB

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