dataflow.cpp 47 KB

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