dataflow.cpp 44 KB

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