icode.h 14 KB

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