icode.h 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608
  1. /*****************************************************************************
  2. * I-code related definitions
  3. * (C) Cristina Cifuentes
  4. ****************************************************************************/
  5. #pragma once
  6. #include <memory>
  7. #include <vector>
  8. #include <list>
  9. #include <bitset>
  10. #include <set>
  11. #include <algorithm>
  12. #include <initializer_list>
  13. #include <llvm/ADT/ilist.h>
  14. #include <llvm/ADT/ilist_node.h>
  15. #include <llvm/MC/MCInst.h>
  16. #include <llvm/Instruction.h>
  17. #include <boost/range/iterator_range.hpp>
  18. #include "libdis.h"
  19. #include "Enums.h"
  20. #include "state.h" // State depends on INDEXBASE, but later need STATE
  21. //enum condId;
  22. struct LOCAL_ID;
  23. struct BB;
  24. struct Function;
  25. struct STKFRAME;
  26. class CIcodeRec;
  27. struct ICODE;
  28. struct bundle;
  29. typedef std::list<ICODE>::iterator iICODE;
  30. typedef std::list<ICODE>::reverse_iterator riICODE;
  31. typedef boost::iterator_range<iICODE> rCODE;
  32. struct LivenessSet
  33. {
  34. std::set<eReg> registers;
  35. public:
  36. LivenessSet(const std::initializer_list<eReg> &init) : registers(init) {}
  37. LivenessSet() {}
  38. LivenessSet(const LivenessSet &other) : registers(other.registers)
  39. {
  40. }
  41. void reset()
  42. {
  43. registers.clear();
  44. }
  45. // LivenessSet(LivenessSet &&other) : LivenessSet()
  46. // {
  47. // swap(*this,other);
  48. // }
  49. LivenessSet &operator=(LivenessSet other)
  50. {
  51. swap(*this,other);
  52. return *this;
  53. }
  54. friend void swap(LivenessSet& first, LivenessSet& second) // nothrow
  55. {
  56. // enable ADL (not necessary in our case, but good practice)
  57. using std::swap;
  58. // by swapping the members of two classes,
  59. // the two classes are effectively swapped
  60. swap(first.registers, second.registers);
  61. }
  62. LivenessSet &operator|=(const LivenessSet &other)
  63. {
  64. registers.insert(other.registers.begin(),other.registers.end());
  65. return *this;
  66. }
  67. LivenessSet &operator&=(const LivenessSet &other)
  68. {
  69. std::set<eReg> res;
  70. std::set_intersection(registers.begin(),registers.end(),
  71. other.registers.begin(),other.registers.end(),
  72. std::inserter(res, res.end()));
  73. registers = res;
  74. return *this;
  75. }
  76. LivenessSet &operator-=(const LivenessSet &other)
  77. {
  78. std::set<eReg> res;
  79. std::set_difference(registers.begin(),registers.end(),
  80. other.registers.begin(),other.registers.end(),
  81. std::inserter(res, res.end()));
  82. registers = res;
  83. return *this;
  84. }
  85. LivenessSet operator-(const LivenessSet &other) const
  86. {
  87. return LivenessSet(*this) -= other;
  88. }
  89. LivenessSet operator+(const LivenessSet &other) const
  90. {
  91. return LivenessSet(*this) |= other;
  92. }
  93. LivenessSet operator &(const LivenessSet &other) const
  94. {
  95. return LivenessSet(*this) &= other;
  96. }
  97. bool any() const
  98. {
  99. return not registers.empty();
  100. }
  101. bool operator==(const LivenessSet &other) const
  102. {
  103. return registers==other.registers;
  104. }
  105. bool operator!=(const LivenessSet &other) const { return not(*this==other);}
  106. LivenessSet &setReg(int r);
  107. LivenessSet &addReg(int r);
  108. bool testReg(int r) const
  109. {
  110. return registers.find(eReg(r))!=registers.end();
  111. }
  112. bool testRegAndSubregs(int r) const;
  113. LivenessSet &clrReg(int r);
  114. private:
  115. void postProcessCompositeRegs();
  116. };
  117. /* uint8_t and uint16_t registers */
  118. /* Def/use of flags - low 4 bits represent flags */
  119. struct DU
  120. {
  121. uint8_t d;
  122. uint8_t u;
  123. };
  124. /* Definition-use chain for level 1 (within a basic block) */
  125. #define MAX_REGS_DEF 4 /* 2 regs def'd for long-reg vars */
  126. struct Expr;
  127. struct AstIdent;
  128. struct UnaryOperator;
  129. struct HlTypeSupport
  130. {
  131. //hlIcode opcode; /* hlIcode opcode */
  132. virtual bool removeRegFromLong(eReg regi, LOCAL_ID *locId)=0;
  133. virtual std::string writeOut(Function *pProc, int *numLoc) const=0;
  134. protected:
  135. Expr * performLongRemoval (eReg regi, LOCAL_ID *locId, Expr *tree);
  136. };
  137. struct CallType : public HlTypeSupport
  138. {
  139. //for HLI_CALL
  140. Function * proc;
  141. STKFRAME * args; // actual arguments
  142. void allocStkArgs (int num);
  143. bool newStkArg(Expr *exp, llIcode opcode, Function *pproc);
  144. void placeStkArg(Expr *exp, int pos);
  145. virtual Expr * toAst();
  146. public:
  147. bool removeRegFromLong(eReg /*regi*/, LOCAL_ID */*locId*/)
  148. {
  149. printf("CallType : removeRegFromLong not supproted");
  150. return false;
  151. }
  152. std::string writeOut(Function *pProc, int *numLoc) const;
  153. };
  154. struct AssignType : public HlTypeSupport
  155. {
  156. /* for HLI_ASSIGN */
  157. protected:
  158. public:
  159. Expr *m_lhs;
  160. Expr *rhs;
  161. AssignType() {}
  162. Expr *lhs() const {return m_lhs;}
  163. void lhs(Expr *l);
  164. bool removeRegFromLong(eReg regi, LOCAL_ID *locId);
  165. std::string writeOut(Function *pProc, int *numLoc) const;
  166. };
  167. struct ExpType : public HlTypeSupport
  168. {
  169. /* for HLI_JCOND, HLI_RET, HLI_PUSH, HLI_POP*/
  170. Expr *v;
  171. ExpType() : v(0) {}
  172. bool removeRegFromLong(eReg regi, LOCAL_ID *locId)
  173. {
  174. v=performLongRemoval(regi,locId,v);
  175. return true;
  176. }
  177. std::string writeOut(Function *pProc, int *numLoc) const;
  178. };
  179. struct HLTYPE
  180. {
  181. protected:
  182. public:
  183. ExpType exp; /* for HLI_JCOND, HLI_RET, HLI_PUSH, HLI_POP*/
  184. hlIcode opcode; /* hlIcode opcode */
  185. AssignType asgn;
  186. CallType call;
  187. HlTypeSupport *get();
  188. const HlTypeSupport *get() const
  189. {
  190. return const_cast<const HlTypeSupport *>(const_cast<HLTYPE*>(this)->get());
  191. }
  192. void expr(Expr *e)
  193. {
  194. assert(e);
  195. exp.v=e;
  196. }
  197. Expr *getMyExpr()
  198. {
  199. if(opcode==HLI_CALL)
  200. return call.toAst();
  201. return expr();
  202. }
  203. void replaceExpr(Expr *e);
  204. Expr * expr() { return exp.v;}
  205. const Expr * expr() const { return exp.v;}
  206. void set(hlIcode i,Expr *e)
  207. {
  208. if(i!=HLI_RET)
  209. assert(e);
  210. assert(exp.v==0);
  211. opcode=i;
  212. exp.v=e;
  213. }
  214. void set(Expr *l,Expr *r);
  215. void setCall(Function *proc);
  216. HLTYPE(hlIcode op=HLI_INVALID) : opcode(op)
  217. {}
  218. // HLTYPE() // help valgrind find uninitialized HLTYPES
  219. // {}
  220. HLTYPE & operator=(const HLTYPE &l)
  221. {
  222. exp = l.exp;
  223. opcode = l.opcode;
  224. asgn = l.asgn;
  225. call = l.call;
  226. return *this;
  227. }
  228. public:
  229. std::string write1HlIcode(Function *pProc, int *numLoc) const;
  230. void setAsgn(Expr *lhs, Expr *rhs);
  231. } ;
  232. /* LOW_LEVEL icode operand record */
  233. struct LLOperand
  234. {
  235. eReg seg; /* CS, DS, ES, SS */
  236. eReg segOver; /* CS, DS, ES, SS if segment override */
  237. int16_t segValue; /* Value of segment seg during analysis */
  238. eReg regi; /* 0 < regs < INDEXBASE <= index modes */
  239. int16_t off; /* memory address offset */
  240. uint32_t opz; /* idx of immed src op */
  241. //union {/* Source operand if (flg & I) */
  242. struct { /* Call & # actual arg bytes */
  243. Function *proc; /* pointer to target proc (for CALL(F))*/
  244. int cb; /* # actual arg bytes */
  245. } proc;
  246. LLOperand() : seg(rUNDEF),segOver(rUNDEF),segValue(0),regi(rUNDEF),off(0),opz(0)
  247. {
  248. proc.proc=0;
  249. proc.cb=0;
  250. }
  251. bool operator==(const LLOperand &with) const
  252. {
  253. return (seg==with.seg) &&
  254. (segOver==with.segOver) &&
  255. (segValue==with.segValue) &&
  256. (regi == with.regi) &&
  257. (off == with.off) &&
  258. (opz==with.opz) &&
  259. (proc.proc==with.proc.proc);
  260. }
  261. int64_t getImm2() const {return opz;}
  262. void SetImmediateOp(uint32_t dw)
  263. {
  264. opz=dw;
  265. }
  266. eReg getReg2() const {return regi;}
  267. bool isReg() const;
  268. static LLOperand CreateImm2(int64_t Val)
  269. {
  270. LLOperand Op;
  271. //Op.Kind = kImmediate;
  272. //Op.ImmVal = Val;
  273. Op.opz = Val;
  274. return Op;
  275. }
  276. static LLOperand CreateReg2(unsigned Val)
  277. {
  278. LLOperand Op;
  279. Op.regi = (eReg)Val;
  280. return Op;
  281. }
  282. bool isSet()
  283. {
  284. return not (*this == LLOperand());
  285. }
  286. void addProcInformation(int param_count,uint32_t call_conv);
  287. };
  288. struct LLInst : public llvm::MCInst //: public llvm::ilist_node<LLInst>
  289. {
  290. protected:
  291. uint32_t flg; /* icode flags */
  292. LLOperand m_src; /* source operand */
  293. public:
  294. int codeIdx; /* Index into cCode.code */
  295. uint8_t numBytes; /* Number of bytes this instr */
  296. uint32_t label; /* offset in image (20-bit adr) */
  297. LLOperand m_dst; /* destination operand */
  298. DU flagDU; /* def/use of flags */
  299. int caseEntry;
  300. std::vector<uint32_t> caseTbl2;
  301. int hllLabNum; /* label # for hll codegen */
  302. bool conditionalJump()
  303. {
  304. return (getOpcode() >= iJB) && (getOpcode() < iJCXZ);
  305. }
  306. bool testFlags(uint32_t x) const { return (flg & x)!=0;}
  307. void setFlags(uint32_t flag) {flg |= flag;}
  308. void clrFlags(uint32_t flag)
  309. {
  310. if(getOpcode()==iMOD)
  311. {
  312. assert(false);
  313. }
  314. flg &= ~flag;
  315. }
  316. uint32_t getFlag() const {return flg;}
  317. uint32_t GetLlLabel() const { return label;}
  318. void SetImmediateOp(uint32_t dw) {m_src.SetImmediateOp(dw);}
  319. bool match(llIcode op)
  320. {
  321. return (getOpcode()==op);
  322. }
  323. bool matchWithRegDst(llIcode op)
  324. {
  325. return (getOpcode()==op) and m_dst.isReg();
  326. }
  327. bool match(llIcode op,eReg dest)
  328. {
  329. return (getOpcode()==op)&&m_dst.regi==dest;
  330. }
  331. bool match(llIcode op,eReg dest,uint32_t flgs)
  332. {
  333. return (getOpcode()==op) and (m_dst.regi==dest) and testFlags(flgs);
  334. }
  335. bool match(llIcode op,eReg dest,eReg src_reg)
  336. {
  337. return (getOpcode()==op)&&(m_dst.regi==dest)&&(m_src.regi==src_reg);
  338. }
  339. bool match(eReg dest,eReg src_reg)
  340. {
  341. return (m_dst.regi==dest)&&(m_src.regi==src_reg);
  342. }
  343. bool match(eReg dest)
  344. {
  345. return (m_dst.regi==dest);
  346. }
  347. bool match(llIcode op,uint32_t flgs)
  348. {
  349. return (getOpcode()==op) and testFlags(flgs);
  350. }
  351. void set(llIcode op,uint32_t flags)
  352. {
  353. setOpcode(op);
  354. flg =flags;
  355. }
  356. void set(llIcode op,uint32_t flags,eReg dst_reg)
  357. {
  358. setOpcode(op);
  359. m_dst = LLOperand::CreateReg2(dst_reg);
  360. flg =flags;
  361. }
  362. void set(llIcode op,uint32_t flags,eReg dst_reg,const LLOperand &src_op)
  363. {
  364. setOpcode(op);
  365. m_dst = LLOperand::CreateReg2(dst_reg);
  366. m_src = src_op;
  367. flg =flags;
  368. }
  369. void emitGotoLabel(int indLevel);
  370. void findJumpTargets(CIcodeRec &_pc);
  371. void writeIntComment(std::ostringstream &s);
  372. void dis1Line(int loc_ip, int pass);
  373. std::ostringstream &strSrc(std::ostringstream &os,bool skip_comma=false);
  374. void flops(std::ostringstream &out);
  375. bool isJmpInst();
  376. HLTYPE createCall();
  377. LLInst(ICODE *container) : flg(0),codeIdx(0),numBytes(0),m_link(container)
  378. {
  379. setOpcode(0);
  380. }
  381. const LLOperand &src() const {return m_src;}
  382. LLOperand &src() {return m_src;}
  383. void replaceSrc(const LLOperand &with)
  384. {
  385. m_src = with;
  386. }
  387. void replaceSrc(eReg r)
  388. {
  389. m_src = LLOperand::CreateReg2(r);
  390. }
  391. void replaceSrc(int64_t r)
  392. {
  393. m_src = LLOperand::CreateImm2(r);
  394. }
  395. void replaceDst(const LLOperand &with)
  396. {
  397. m_dst = with;
  398. }
  399. // void replaceDst(eReg r)
  400. // {
  401. // dst = LLOperand::CreateReg2(r);
  402. // }
  403. ICODE *m_link;
  404. condId idType(opLoc sd) const;
  405. const LLOperand * get(opLoc sd) const { return (sd == SRC) ? &src() : &m_dst; }
  406. LLOperand * get(opLoc sd) { return (sd == SRC) ? &src() : &m_dst; }
  407. };
  408. /* Icode definition: LOW_LEVEL and HIGH_LEVEL */
  409. struct ICODE
  410. {
  411. // use llvm names at least
  412. typedef BB MachineBasicBlock;
  413. protected:
  414. LLInst m_ll;
  415. HLTYPE m_hl;
  416. MachineBasicBlock * Parent; /* BB to which this icode belongs */
  417. bool invalid; /* Has no HIGH_LEVEL equivalent */
  418. public:
  419. x86_insn_t insn;
  420. template<int FLAG>
  421. struct FlagFilter
  422. {
  423. bool operator()(ICODE *ic) {return ic->ll()->testFlags(FLAG);}
  424. bool operator()(ICODE &ic) {return ic.ll()->testFlags(FLAG);}
  425. };
  426. template<int TYPE>
  427. struct TypeFilter
  428. {
  429. bool operator()(ICODE *ic) {return ic->type==HIGH_LEVEL;}
  430. bool operator()(ICODE &ic) {return ic.type==HIGH_LEVEL;}
  431. };
  432. template<int TYPE>
  433. struct TypeAndValidFilter
  434. {
  435. bool operator()(ICODE *ic) {return (ic->type==HIGH_LEVEL)&&(ic->valid());}
  436. bool operator()(ICODE &ic) {return (ic.type==HIGH_LEVEL)&&ic.valid();}
  437. };
  438. static TypeFilter<HIGH_LEVEL> select_high_level;
  439. static TypeAndValidFilter<HIGH_LEVEL> select_valid_high_level;
  440. /* Def/Use of registers and stack variables */
  441. struct DU_ICODE
  442. {
  443. DU_ICODE()
  444. {
  445. def.reset();
  446. use.reset();
  447. lastDefRegi.reset();
  448. }
  449. LivenessSet def; // For Registers: position in bitset is reg index
  450. LivenessSet use; // For Registers: position in uint32_t is reg index
  451. LivenessSet lastDefRegi;// Bit set if last def of this register in BB
  452. void addDefinedAndUsed(eReg r)
  453. {
  454. def.addReg(r);
  455. use.addReg(r);
  456. }
  457. };
  458. struct DU1
  459. {
  460. protected:
  461. int numRegsDef; /* # registers defined by this inst */
  462. public:
  463. struct Use
  464. {
  465. int Reg; // used register
  466. std::vector<std::list<ICODE>::iterator> uses; // use locations [MAX_USES]
  467. void removeUser(std::list<ICODE>::iterator us)
  468. {
  469. // ic is no no longer an user
  470. auto iter=std::find(uses.begin(),uses.end(),us);
  471. if(iter==uses.end())
  472. return;
  473. uses.erase(iter);
  474. assert("Same user more then once!" && uses.end()==std::find(uses.begin(),uses.end(),us));
  475. }
  476. };
  477. uint8_t regi[MAX_REGS_DEF+1]; /* registers defined by this inst */
  478. Use idx[MAX_REGS_DEF+1];
  479. //int idx[MAX_REGS_DEF][MAX_USES]; /* inst that uses this def */
  480. bool used(int regIdx)
  481. {
  482. return not idx[regIdx].uses.empty();
  483. }
  484. int numUses(int regIdx)
  485. {
  486. return idx[regIdx].uses.size();
  487. }
  488. void recordUse(int regIdx,std::list<ICODE>::iterator location)
  489. {
  490. idx[regIdx].uses.push_back(location);
  491. }
  492. void remove(int regIdx,int use_idx)
  493. {
  494. idx[regIdx].uses.erase(idx[regIdx].uses.begin()+use_idx);
  495. }
  496. void remove(int regIdx,std::list<ICODE>::iterator ic)
  497. {
  498. Use &u(idx[regIdx]);
  499. u.removeUser(ic);
  500. }
  501. int getNumRegsDef() const {return numRegsDef;}
  502. void clearAllDefs() {numRegsDef=0;}
  503. DU1 &addDef(eReg r) {numRegsDef++; return *this;}
  504. DU1 &setDef(eReg r) {numRegsDef=1; return *this;}
  505. void removeDef(eReg r) {numRegsDef--;}
  506. DU1() : numRegsDef(0)
  507. {
  508. }
  509. };
  510. icodeType type; /* Icode type */
  511. DU_ICODE du; /* Def/use regs/vars */
  512. DU1 du1; /* du chain 1 */
  513. int loc_ip; // used by CICodeRec to number ICODEs
  514. LLInst * ll() { return &m_ll;}
  515. const LLInst * ll() const { return &m_ll;}
  516. HLTYPE * hlU() {
  517. // assert(type==HIGH_LEVEL);
  518. // assert(m_hl.opcode!=HLI_INVALID);
  519. return &m_hl;
  520. }
  521. const HLTYPE * hl() const {
  522. // assert(type==HIGH_LEVEL);
  523. // assert(m_hl.opcode!=HLI_INVALID);
  524. return &m_hl;
  525. }
  526. void hl(const HLTYPE &v) { m_hl=v;}
  527. void setRegDU(eReg regi, operDu du_in);
  528. void invalidate();
  529. void newCallHl();
  530. void writeDU();
  531. condId idType(opLoc sd);
  532. // HLL setting functions
  533. // set this icode to be an assign
  534. void setAsgn(Expr *lhs, Expr *rhs)
  535. {
  536. type=HIGH_LEVEL;
  537. hlU()->setAsgn(lhs,rhs);
  538. }
  539. void setUnary(hlIcode op, Expr *_exp);
  540. void setJCond(Expr *cexp);
  541. void emitGotoLabel(int indLevel);
  542. void copyDU(const ICODE &duIcode, operDu _du, operDu duDu);
  543. bool valid() {return not invalid;}
  544. void setParent(MachineBasicBlock *P) { Parent = P; }
  545. public:
  546. bool removeDefRegi(eReg regi, int thisDefIdx, LOCAL_ID *locId);
  547. void checkHlCall();
  548. bool newStkArg(Expr *exp, llIcode opcode, Function *pproc)
  549. {
  550. return hlU()->call.newStkArg(exp,opcode,pproc);
  551. }
  552. ICODE() : m_ll(this),Parent(0),invalid(false),type(NOT_SCANNED),loc_ip(0)
  553. {
  554. }
  555. public:
  556. const MachineBasicBlock* getParent() const { return Parent; }
  557. MachineBasicBlock* getParent() { return Parent; }
  558. //unsigned getNumOperands() const { return (unsigned)Operands.size(); }
  559. };
  560. /** Map n low level instructions to m high level instructions
  561. */
  562. struct MappingLLtoML
  563. {
  564. typedef llvm::iplist<llvm::Instruction> InstListType;
  565. typedef boost::iterator_range<iICODE> rSourceRange;
  566. typedef boost::iterator_range<InstListType::iterator> rTargetRange;
  567. rSourceRange m_low_level;
  568. rTargetRange m_middle_level;
  569. };
  570. // This is the icode array object.
  571. class CIcodeRec : public std::list<ICODE>
  572. {
  573. public:
  574. CIcodeRec(); // Constructor
  575. ICODE * addIcode(ICODE *pIcode);
  576. void SetInBB(rCODE &rang, BB* pnewBB);
  577. bool labelSrch(uint32_t target, uint32_t &pIndex);
  578. iterator labelSrch(uint32_t target);
  579. ICODE * GetIcode(size_t ip);
  580. bool alreadyDecoded(uint32_t target);
  581. };