dataflow.cpp 47 KB

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