icode.h 18 KB

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