icode.h 13 KB

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