icode.h 18 KB

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