icode.h 18 KB

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