icode.h 15 KB

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