icode.h 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492
  1. /*****************************************************************************
  2. * I-code related definitions
  3. * (C) Cristina Cifuentes
  4. ****************************************************************************/
  5. #pragma once
  6. #include <vector>
  7. #include <list>
  8. #include <bitset>
  9. #include <llvm/MC/MCInst.h>
  10. #include <llvm/MC/MCAsmInfo.h>
  11. #include "Enums.h"
  12. //enum condId;
  13. struct LOCAL_ID;
  14. /* LOW_LEVEL icode flags */
  15. enum eLLFlags
  16. {
  17. B =0x0000001, /* uint8_t operands (value implicitly used) */
  18. I =0x0000002, /* Immed. source */
  19. NOT_HLL =0x0000004, /* Not HLL inst. */
  20. FLOAT_OP =0x0000008, /* ESC or WAIT */
  21. SEG_IMMED =0x0000010, /* Number is relocated segment value */
  22. IMPURE =0x0000020, /* Instruction modifies code */
  23. WORD_OFF =0x0000040, /* Inst has uint16_t offset ie.could be address */
  24. TERMINATES =0x0000080, /* Instruction terminates program */
  25. CASE =0x0000100, /* Label as case part of switch */
  26. SWITCH =0x0000200, /* Treat indirect JMP as switch stmt */
  27. TARGET =0x0000400, /* Jump target */
  28. SYNTHETIC =0x0000800, /* Synthetic jump instruction */
  29. NO_LABEL =0x0001000, /* Immed. jump cannot be linked to a label */
  30. NO_CODE =0x0002000, /* Hole in Icode array */
  31. SYM_USE =0x0004000, /* Instruction uses a symbol */
  32. SYM_DEF =0x0008000, /* Instruction defines a symbol */
  33. NO_SRC =0x0010000, /* Opcode takes no source */
  34. NO_OPS =0x0020000, /* Opcode takes no operands */
  35. IM_OPS =0x0040000, /* Opcode takes implicit operands */
  36. SRC_B =0x0080000, /* Source operand is uint8_t (dest is uint16_t) */
  37. #define NO_SRC_B 0xF7FFFF /* Masks off SRC_B */
  38. HLL_LABEL =0x0100000, /* Icode has a high level language label */
  39. IM_DST =0x0200000, /* Implicit DST for opcode (SIGNEX) */
  40. IM_SRC =0x0400000, /* Implicit SRC for opcode (dx:ax) */
  41. IM_TMP_DST =0x0800000, /* Implicit rTMP DST for opcode (DIV/IDIV) */
  42. JMP_ICODE =0x1000000, /* Jmp dest immed.op converted to icode index */
  43. JX_LOOP =0x2000000, /* Cond jump is part of loop conditional exp */
  44. REST_STK =0x4000000 /* Stack needs to be restored after CALL */
  45. };
  46. /* Parser flags */
  47. #define TO_REG 0x000100 /* rm is source */
  48. #define S_EXT 0x000200 /* sign extend */
  49. #define OP386 0x000400 /* 386 op-code */
  50. #define NSP 0x000800 /* NOT_HLL if SP is src or dst */
  51. #define ICODEMASK 0xFF00FF /* Masks off parser flags */
  52. /* LOW_LEVEL icode, DU flag bits */
  53. enum eDuFlags
  54. {
  55. Cf=1,
  56. Sf=2,
  57. Zf=4,
  58. Df=8
  59. };
  60. /* uint8_t and uint16_t registers */
  61. static const char *const byteReg[9] = {"al", "cl", "dl", "bl",
  62. "ah", "ch", "dh", "bh", "tmp" };
  63. static const char *const wordReg[21] = {"ax", "cx", "dx", "bx", "sp", "bp",
  64. "si", "di", "es", "cs", "ss", "ds",
  65. "", "", "", "", "", "", "", "", "tmp"};
  66. #include "state.h" // State depends on INDEXBASE, but later need STATE
  67. /* Types of icodes */
  68. enum icodeType
  69. {
  70. NOT_SCANNED = 0, /* not even scanned yet */
  71. LOW_LEVEL, /* low-level icode */
  72. HIGH_LEVEL /* high-level icode */
  73. };
  74. /* LOW_LEVEL icode opcodes */
  75. enum llIcode
  76. {
  77. iCBW, /* 0 */
  78. iAAA,
  79. iAAD,
  80. iAAM,
  81. iAAS,
  82. iADC,
  83. iADD,
  84. iAND,
  85. iBOUND,
  86. iCALL,
  87. iCALLF, /* 10 */
  88. iCLC,
  89. iCLD,
  90. iCLI,
  91. iCMC,
  92. iCMP,
  93. iCMPS,
  94. iREPNE_CMPS,
  95. iREPE_CMPS,
  96. iDAA,
  97. iDAS, /* 20 */
  98. iDEC,
  99. iDIV,
  100. iENTER,
  101. iESC,
  102. iHLT,
  103. iIDIV,
  104. iIMUL,
  105. iIN,
  106. iINC,
  107. iINS, /* 30 */
  108. iREP_INS,
  109. iINT,
  110. iIRET,
  111. iJB,
  112. iJBE,
  113. iJAE,
  114. iJA,
  115. iJE,
  116. iJNE,
  117. iJL, /* 40 */
  118. iJGE,
  119. iJLE,
  120. iJG,
  121. iJS,
  122. iJNS,
  123. iJO,
  124. iJNO,
  125. iJP,
  126. iJNP,
  127. iJCXZ, /* 50 */
  128. iJMP,
  129. iJMPF,
  130. iLAHF,
  131. iLDS,
  132. iLEA,
  133. iLEAVE,
  134. iLES,
  135. iLOCK,
  136. iLODS,
  137. iREP_LODS, /* 60 */
  138. iLOOP,
  139. iLOOPE,
  140. iLOOPNE,
  141. iMOV, /* 64 */
  142. iMOVS,
  143. iREP_MOVS,
  144. iMUL, /* 67 */
  145. iNEG,
  146. iNOT,
  147. iOR, /* 70 */
  148. iOUT,
  149. iOUTS,
  150. iREP_OUTS,
  151. iPOP,
  152. iPOPA,
  153. iPOPF,
  154. iPUSH,
  155. iPUSHA,
  156. iPUSHF,
  157. iRCL, /* 80 */
  158. iRCR,
  159. iROL,
  160. iROR,
  161. iRET, /* 84 */
  162. iRETF,
  163. iSAHF,
  164. iSAR,
  165. iSHL,
  166. iSHR,
  167. iSBB, /* 90 */
  168. iSCAS,
  169. iREPNE_SCAS,
  170. iREPE_SCAS,
  171. iSIGNEX,
  172. iSTC,
  173. iSTD,
  174. iSTI,
  175. iSTOS,
  176. iREP_STOS,
  177. iSUB, /* 100 */
  178. iTEST,
  179. iWAIT,
  180. iXCHG,
  181. iXLAT,
  182. iXOR,
  183. iINTO,
  184. iNOP,
  185. iREPNE,
  186. iREPE,
  187. iMOD /* 110 */
  188. };
  189. struct BB;
  190. struct Function;
  191. struct STKFRAME;
  192. /* Def/use of flags - low 4 bits represent flags */
  193. struct DU
  194. {
  195. uint8_t d;
  196. uint8_t u;
  197. };
  198. /* Definition-use chain for level 1 (within a basic block) */
  199. #define MAX_REGS_DEF 2 /* 2 regs def'd for long-reg vars */
  200. #define MAX_USES 5
  201. struct COND_EXPR;
  202. struct HlTypeSupport
  203. {
  204. //hlIcode opcode; /* hlIcode opcode */
  205. virtual bool removeRegFromLong(uint8_t regi, LOCAL_ID *locId)=0;
  206. virtual std::string writeOut(Function *pProc, int *numLoc)=0;
  207. protected:
  208. void performLongRemoval (uint8_t regi, LOCAL_ID *locId, COND_EXPR *tree);
  209. };
  210. struct CallType : public HlTypeSupport
  211. {
  212. //for HLI_CALL
  213. Function * proc;
  214. STKFRAME * args; // actual arguments
  215. void allocStkArgs (int num);
  216. bool newStkArg(COND_EXPR *exp, llIcode opcode, Function *pproc);
  217. void placeStkArg(COND_EXPR *exp, int pos);
  218. public:
  219. bool removeRegFromLong(uint8_t regi, LOCAL_ID *locId)
  220. {
  221. printf("CallType : removeRegFromLong not supproted");
  222. return false;
  223. }
  224. std::string writeOut(Function *pProc, int *numLoc);
  225. };
  226. struct AssignType : public HlTypeSupport
  227. {
  228. /* for HLI_ASSIGN */
  229. COND_EXPR *lhs;
  230. COND_EXPR *rhs;
  231. bool removeRegFromLong(uint8_t regi, LOCAL_ID *locId)
  232. {
  233. performLongRemoval(regi,locId,lhs);
  234. return true;
  235. }
  236. std::string writeOut(Function *pProc, int *numLoc);
  237. };
  238. struct ExpType : public HlTypeSupport
  239. {
  240. /* for HLI_JCOND, HLI_RET, HLI_PUSH, HLI_POP*/
  241. COND_EXPR *v;
  242. bool removeRegFromLong(uint8_t regi, LOCAL_ID *locId)
  243. {
  244. performLongRemoval(regi,locId,v);
  245. return true;
  246. }
  247. std::string writeOut(Function *pProc, int *numLoc);
  248. };
  249. struct HLTYPE
  250. {
  251. hlIcode opcode; /* hlIcode opcode */
  252. ExpType exp; /* for HLI_JCOND, HLI_RET, HLI_PUSH, HLI_POP*/
  253. AssignType asgn;
  254. CallType call;
  255. HlTypeSupport *get()
  256. {
  257. switch(opcode)
  258. {
  259. case HLI_ASSIGN: return &asgn;
  260. case HLI_RET:
  261. case HLI_POP:
  262. case HLI_PUSH: return &exp;
  263. case HLI_CALL: return &call;
  264. default:
  265. return 0;
  266. }
  267. }
  268. void expr(COND_EXPR *e)
  269. {
  270. assert(e);
  271. exp.v=e;
  272. }
  273. COND_EXPR * expr() { return exp.v;}
  274. void set(hlIcode i,COND_EXPR *e)
  275. {
  276. if(i!=HLI_RET)
  277. assert(e);
  278. assert(exp.v==0);
  279. opcode=i;
  280. exp.v=e;
  281. }
  282. void set(COND_EXPR *l,COND_EXPR *r)
  283. {
  284. assert(l);
  285. assert(r);
  286. opcode = HLI_ASSIGN;
  287. assert((asgn.lhs==0) and (asgn.rhs==0)); //prevent memory leaks
  288. asgn.lhs=l;
  289. asgn.rhs=r;
  290. }
  291. public:
  292. std::string write1HlIcode(Function *pProc, int *numLoc);
  293. } ;
  294. /* LOW_LEVEL icode operand record */
  295. struct LLOperand //: public llvm::MCOperand
  296. {
  297. uint8_t seg; /* CS, DS, ES, SS */
  298. int16_t segValue; /* Value of segment seg during analysis */
  299. uint8_t segOver; /* CS, DS, ES, SS if segment override */
  300. uint8_t regi; /* 0 < regs < INDEXBASE <= index modes */
  301. int16_t off; /* memory address offset */
  302. uint32_t opz; /* idx of immed src op */
  303. //union {/* Source operand if (flg & I) */
  304. struct { /* Call & # actual arg bytes */
  305. Function *proc; /* pointer to target proc (for CALL(F))*/
  306. int cb; /* # actual arg bytes */
  307. } proc;
  308. uint32_t op() const {return opz;}
  309. void SetImmediateOp(uint32_t dw) {opz=dw;}
  310. };
  311. struct LLInst : public llvm::MCInst
  312. {
  313. llIcode opcode; /* llIcode instruction */
  314. uint8_t numBytes; /* Number of bytes this instr */
  315. uint32_t flg; /* icode flags */
  316. uint32_t label; /* offset in image (20-bit adr) */
  317. LLOperand dst; /* destination operand */
  318. LLOperand src; /* source operand */
  319. DU flagDU; /* def/use of flags */
  320. struct { /* Case table if op==JMP && !I */
  321. int numEntries; /* # entries in case table */
  322. uint32_t *entries; /* array of offsets */
  323. } caseTbl;
  324. int hllLabNum; /* label # for hll codegen */
  325. bool conditionalJump()
  326. {
  327. return (opcode >= iJB) && (opcode < iJCXZ);
  328. }
  329. bool anyFlagSet(uint32_t x) const { return (flg & x)!=0;}
  330. bool match(llIcode op)
  331. {
  332. return (opcode==op);
  333. }
  334. bool match(llIcode op,eReg dest)
  335. {
  336. return (opcode==op)&&dst.regi==dest;
  337. }
  338. bool match(llIcode op,eReg dest,eReg src_reg)
  339. {
  340. return (opcode==op)&&(dst.regi==dest)&&(src.regi==src_reg);
  341. }
  342. bool match(eReg dest,eReg src_reg)
  343. {
  344. return (dst.regi==dest)&&(src.regi==src_reg);
  345. }
  346. bool match(eReg dest)
  347. {
  348. return (dst.regi==dest);
  349. }
  350. void set(llIcode op,uint32_t flags)
  351. {
  352. opcode = op;
  353. flg =flags;
  354. }
  355. };
  356. /* Icode definition: LOW_LEVEL and HIGH_LEVEL */
  357. struct ICODE
  358. {
  359. /* Def/Use of registers and stack variables */
  360. struct DU_ICODE
  361. {
  362. std::bitset<32> def; // For Registers: position in bitset is reg index
  363. std::bitset<32> use; // For Registers: position in uint32_t is reg index
  364. std::bitset<32> lastDefRegi;// Bit set if last def of this register in BB
  365. };
  366. struct DU1
  367. {
  368. struct DefUse
  369. {
  370. int Reg; // used register
  371. int DefLoc;
  372. std::vector<std::list<ICODE>::iterator > useLoc; // use locations [MAX_USES]
  373. };
  374. struct Use
  375. {
  376. int Reg; // used register
  377. std::vector<std::list<ICODE>::iterator> uses; // use locations [MAX_USES]
  378. void removeUser(std::list<ICODE>::iterator us)
  379. {
  380. // ic is no no longer an user
  381. auto iter=std::find(uses.begin(),uses.end(),us);
  382. if(iter==uses.end())
  383. return;
  384. uses.erase(iter);
  385. assert("Same user more then once!" && uses.end()==std::find(uses.begin(),uses.end(),us));
  386. }
  387. };
  388. int numRegsDef; /* # registers defined by this inst */
  389. uint8_t regi[MAX_REGS_DEF]; /* registers defined by this inst */
  390. Use idx[MAX_REGS_DEF];
  391. //int idx[MAX_REGS_DEF][MAX_USES]; /* inst that uses this def */
  392. bool used(int regIdx)
  393. {
  394. return not idx[regIdx].uses.empty();
  395. }
  396. int numUses(int regIdx)
  397. {
  398. return idx[regIdx].uses.size();
  399. }
  400. void recordUse(int regIdx,std::list<ICODE>::iterator location)
  401. {
  402. idx[regIdx].uses.push_back(location);
  403. }
  404. void remove(int regIdx,int use_idx)
  405. {
  406. idx[regIdx].uses.erase(idx[regIdx].uses.begin()+use_idx);
  407. }
  408. void remove(int regIdx,std::list<ICODE>::iterator ic)
  409. {
  410. Use &u(idx[regIdx]);
  411. u.removeUser(ic);
  412. }
  413. };
  414. icodeType type; /* Icode type */
  415. bool invalid; /* Has no HIGH_LEVEL equivalent */
  416. BB *inBB; /* BB to which this icode belongs */
  417. DU_ICODE du; /* Def/use regs/vars */
  418. DU1 du1; /* du chain 1 */
  419. int codeIdx; /* Index into cCode.code */
  420. struct IC { /* Different types of icodes */
  421. LLInst ll;
  422. HLTYPE hl; /* For HIGH_LEVEL icodes */
  423. };
  424. IC ic;/* intermediate code */
  425. int loc_ip; // used by CICodeRec to number ICODEs
  426. void ClrLlFlag(uint32_t flag) {ic.ll.flg &= ~flag;}
  427. void SetLlFlag(uint32_t flag) {ic.ll.flg |= flag;}
  428. uint32_t GetLlFlag() {return ic.ll.flg;}
  429. bool isLlFlag(uint32_t flg) {return (ic.ll.flg&flg)!=0;}
  430. llIcode GetLlOpcode() const { return ic.ll.opcode; }
  431. uint32_t GetLlLabel() const { return ic.ll.label;}
  432. void SetImmediateOp(uint32_t dw) {ic.ll.src.SetImmediateOp(dw);}
  433. void writeIntComment(std::ostringstream &s);
  434. void setRegDU(uint8_t regi, operDu du_in);
  435. void invalidate();
  436. void newCallHl();
  437. void writeDU(int idx);
  438. condId idType(opLoc sd);
  439. // HLL setting functions
  440. void setAsgn(COND_EXPR *lhs, COND_EXPR *rhs); // set this icode to be an assign
  441. void setUnary(hlIcode op, COND_EXPR *exp);
  442. void setJCond(COND_EXPR *cexp);
  443. void emitGotoLabel(int indLevel);
  444. void copyDU(const ICODE &duIcode, operDu _du, operDu duDu);
  445. bool valid() {return not invalid;}
  446. public:
  447. bool removeDefRegi(uint8_t regi, int thisDefIdx, LOCAL_ID *locId);
  448. void checkHlCall();
  449. bool newStkArg(COND_EXPR *exp, llIcode opcode, Function *pproc)
  450. {
  451. return ic.hl.call.newStkArg(exp,opcode,pproc);
  452. }
  453. };
  454. // This is the icode array object.
  455. class CIcodeRec : public std::list<ICODE>
  456. {
  457. public:
  458. CIcodeRec(); // Constructor
  459. ICODE * addIcode(ICODE *pIcode);
  460. void SetInBB(int start, int end, BB* pnewBB);
  461. bool labelSrch(uint32_t target, uint32_t &pIndex);
  462. iterator labelSrch(uint32_t target);
  463. ICODE * GetIcode(int ip);
  464. };
  465. typedef CIcodeRec::iterator iICODE;
  466. typedef CIcodeRec::reverse_iterator riICODE;