dataflow.cpp 45 KB

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