icode.h 12 KB

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