ast.h 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321
  1. /*
  2. * File: ast.h
  3. * Purpose: definition of the abstract syntax tree ADT.
  4. * Date: September 1993
  5. * (C) Cristina Cifuentes
  6. */
  7. #pragma once
  8. #include "Enums.h"
  9. #include "msvc_fixes.h"
  10. #include <boost/range/iterator_range.hpp>
  11. #include <stdint.h>
  12. #include <cstring>
  13. #include <list>
  14. static const int operandSize=20;
  15. /* The following definitions and types define the Conditional Expression
  16. * attributed syntax tree, as defined by the following EBNF:
  17. CondExp ::= CondTerm AND CondTerm | CondTerm
  18. CondTerm ::= (CondFactor op CondFactor)
  19. CondFactor ::= Identifier | ! CondFactor
  20. Identifier ::= globalVar | register | localVar | parameter | constant
  21. op ::= <= | < | = | != | > | >=
  22. */
  23. /* High-level BOOLEAN conditions for iJB..iJNS icodes */
  24. static const condOp condOpJCond[12] = {LESS, LESS_EQUAL, GREATER_EQUAL, GREATER,
  25. EQUAL, NOT_EQUAL, LESS, GREATER_EQUAL,
  26. LESS_EQUAL, GREATER, GREATER_EQUAL, LESS};
  27. struct AstIdent;
  28. struct Function;
  29. struct STKFRAME;
  30. struct LOCAL_ID;
  31. struct ICODE;
  32. struct LLInst;
  33. struct LLOperand;
  34. struct ID;
  35. typedef std::list<ICODE>::iterator iICODE;
  36. typedef boost::iterator_range<iICODE> rICODE;
  37. #include "IdentType.h"
  38. /* Expression data type */
  39. struct Expr
  40. {
  41. public:
  42. condNodeType m_type; /* Conditional Expression Node Type */
  43. public:
  44. static bool insertSubTreeLongReg(Expr *exp, Expr *&tree, int longIdx);
  45. static bool insertSubTreeReg(Expr *&tree, Expr *_expr, eReg regi, const LOCAL_ID *locsym);
  46. static bool insertSubTreeReg(AstIdent *&tree, Expr *_expr, eReg regi, const LOCAL_ID *locsym);
  47. public:
  48. virtual Expr *clone() const=0; //!< Makes a deep copy of the given expression
  49. Expr(condNodeType t=UNKNOWN_OP) : m_type(t)
  50. {
  51. }
  52. /** Recursively deallocates the abstract syntax tree rooted at *exp */
  53. virtual ~Expr() {}
  54. public:
  55. virtual std::string walkCondExpr (Function * pProc, int* numLoc) const=0;
  56. virtual Expr *inverse() const=0; // return new COND_EXPR that is invarse of this
  57. virtual bool xClear(rICODE range_to_check, iICODE lastBBinst, const LOCAL_ID &locId)=0;
  58. virtual Expr *insertSubTreeReg(Expr *_expr, eReg regi, const LOCAL_ID *locsym)=0;
  59. virtual Expr *insertSubTreeLongReg(Expr *_expr, int longIdx)=0;
  60. virtual hlType expType(Function *pproc) const=0;
  61. virtual int hlTypeSize(Function *pproc) const=0;
  62. virtual Expr * performLongRemoval(eReg regi, LOCAL_ID *locId) { return this; }
  63. };
  64. struct UnaryOperator : public Expr
  65. {
  66. UnaryOperator(condNodeType t=UNKNOWN_OP) : Expr(t),unaryExp(nullptr) {}
  67. Expr *unaryExp;
  68. virtual Expr *inverse() const
  69. {
  70. if (m_type == NEGATION) //TODO: memleak here
  71. {
  72. return unaryExp->clone();
  73. }
  74. return this->clone();
  75. }
  76. virtual Expr *clone() const
  77. {
  78. UnaryOperator *newExp = new UnaryOperator(*this);
  79. newExp->unaryExp = unaryExp->clone();
  80. return newExp;
  81. }
  82. virtual bool xClear(rICODE range_to_check, iICODE lastBBinst, const LOCAL_ID &locs);
  83. static UnaryOperator *Create(condNodeType t, Expr *sub_expr)
  84. {
  85. UnaryOperator *newExp = new UnaryOperator();
  86. newExp->m_type = t;
  87. newExp->unaryExp = sub_expr;
  88. return (newExp);
  89. }
  90. ~UnaryOperator()
  91. {
  92. delete unaryExp;
  93. unaryExp=nullptr;
  94. }
  95. public:
  96. int hlTypeSize(Function *pproc) const;
  97. virtual std::string walkCondExpr(Function *pProc, int *numLoc) const;
  98. virtual Expr *insertSubTreeReg(Expr *_expr, eReg regi, const LOCAL_ID *locsym);
  99. virtual hlType expType(Function *pproc) const;
  100. virtual Expr *insertSubTreeLongReg(Expr *_expr, int longIdx);
  101. };
  102. struct BinaryOperator : public Expr
  103. {
  104. condOp m_op;
  105. Expr *m_lhs;
  106. Expr *m_rhs;
  107. BinaryOperator(condOp o) : Expr(BOOLEAN_OP)
  108. {
  109. m_op = o;
  110. m_lhs=m_rhs=nullptr;
  111. }
  112. BinaryOperator(condOp o,Expr *l,Expr *r) : Expr(BOOLEAN_OP)
  113. {
  114. m_op = o;
  115. m_lhs=l;
  116. m_rhs=r;
  117. }
  118. ~BinaryOperator()
  119. {
  120. assert(m_lhs!=m_rhs or m_lhs==nullptr);
  121. delete m_lhs;
  122. delete m_rhs;
  123. m_lhs=m_rhs=nullptr;
  124. }
  125. static BinaryOperator *Create(condOp o,Expr *l,Expr *r)
  126. {
  127. BinaryOperator *res = new BinaryOperator(o);
  128. res->m_lhs = l;
  129. res->m_rhs = r;
  130. return res;
  131. }
  132. static BinaryOperator *LogicAnd(Expr *l,Expr *r)
  133. {
  134. return Create(DBL_AND,l,r);
  135. }
  136. static BinaryOperator *createSHL(Expr *l,Expr *r)
  137. {
  138. return Create(SHL,l,r);
  139. }
  140. static BinaryOperator *And(Expr *l,Expr *r)
  141. {
  142. return Create(AND,l,r);
  143. }
  144. static BinaryOperator *Or(Expr *l,Expr *r)
  145. {
  146. return Create(OR,l,r);
  147. }
  148. static BinaryOperator *LogicOr(Expr *l,Expr *r)
  149. {
  150. return Create(DBL_OR,l,r);
  151. }
  152. static BinaryOperator *CreateAdd(Expr *l,Expr *r) {
  153. return Create(ADD,l,r);
  154. }
  155. void changeBoolOp(condOp newOp);
  156. virtual Expr *inverse() const;
  157. virtual Expr *clone() const;
  158. virtual bool xClear(rICODE range_to_check, iICODE lastBBinst, const LOCAL_ID &locs);
  159. virtual Expr *insertSubTreeReg(Expr *_expr, eReg regi, const LOCAL_ID *locsym);
  160. virtual Expr *insertSubTreeLongReg(Expr *_expr, int longIdx);
  161. const Expr *lhs() const
  162. {
  163. return const_cast<const Expr *>(const_cast<BinaryOperator *>(this)->lhs());
  164. }
  165. const Expr *rhs() const
  166. {
  167. return const_cast<const Expr *>(const_cast<BinaryOperator *>(this)->rhs());
  168. }
  169. Expr *lhs()
  170. {
  171. assert(m_type==BOOLEAN_OP);
  172. return m_lhs;
  173. }
  174. Expr *rhs()
  175. {
  176. assert(m_type==BOOLEAN_OP);
  177. return m_rhs;
  178. }
  179. condOp op() const { return m_op;}
  180. /* Changes the boolean conditional operator at the root of this expression */
  181. void op(condOp o) { m_op=o;}
  182. std::string walkCondExpr (Function * pProc, int* numLoc) const;
  183. public:
  184. hlType expType(Function *pproc) const;
  185. int hlTypeSize(Function *pproc) const;
  186. };
  187. struct AstIdent : public UnaryOperator
  188. {
  189. AstIdent() : UnaryOperator(IDENTIFIER)
  190. {
  191. }
  192. IDENTTYPE ident; /* for IDENTIFIER */
  193. static AstIdent * Loc(int off, LOCAL_ID *localId);
  194. static AstIdent * LongIdx(int idx);
  195. static AstIdent * String(uint32_t idx);
  196. static AstIdent * Other(eReg seg, eReg regi, int16_t off);
  197. static AstIdent * Param(int off, const STKFRAME *argSymtab);
  198. static AstIdent * Long(LOCAL_ID *localId, opLoc sd, iICODE pIcode, hlFirst f, iICODE ix, operDu du, LLInst &atOffset);
  199. static AstIdent * idID(const ID *retVal, LOCAL_ID *locsym, iICODE ix_);
  200. static Expr * id(const LLInst &ll_insn, opLoc sd, Function *pProc, iICODE ix_, ICODE &duIcode, operDu du);
  201. virtual Expr *clone() const
  202. {
  203. return new AstIdent(*this);
  204. }
  205. virtual int hlTypeSize(Function *pproc) const;
  206. virtual hlType expType(Function *pproc) const;
  207. virtual Expr * performLongRemoval(eReg regi, LOCAL_ID *locId);
  208. virtual std::string walkCondExpr(Function *pProc, int *numLoc) const;
  209. virtual Expr *insertSubTreeReg(Expr *_expr, eReg regi, const LOCAL_ID *locsym);
  210. virtual Expr *insertSubTreeLongReg(Expr *_expr, int longIdx);
  211. virtual bool xClear(rICODE range_to_check, iICODE lastBBinst, const LOCAL_ID &locId);
  212. protected:
  213. eReg otherLongRegi (eReg regi, int idx, LOCAL_ID *locTbl);
  214. };
  215. struct GlobalVariable : public AstIdent
  216. {
  217. bool valid;
  218. int globIdx;
  219. virtual Expr *clone() const
  220. {
  221. return new GlobalVariable(*this);
  222. }
  223. GlobalVariable(int16_t segValue, int16_t off);
  224. std::string walkCondExpr(Function *pProc, int *numLoc) const;
  225. int hlTypeSize(Function *pproc) const;
  226. hlType expType(Function *pproc) const;
  227. };
  228. struct GlobalVariableIdx : public AstIdent
  229. {
  230. bool valid;
  231. int idxGlbIdx; /* idx into localId, GLOB_VAR_IDX */
  232. virtual Expr *clone() const
  233. {
  234. return new GlobalVariableIdx(*this);
  235. }
  236. GlobalVariableIdx(int16_t segValue, int16_t off, uint8_t regi, const LOCAL_ID *locSym);
  237. std::string walkCondExpr(Function *pProc, int *numLoc) const;
  238. int hlTypeSize(Function *pproc) const;
  239. hlType expType(Function *pproc) const;
  240. };
  241. struct Constant : public AstIdent
  242. {
  243. struct _kte
  244. { /* for CONSTANT only */
  245. uint32_t kte; /* value of the constant */
  246. uint8_t size; /* #bytes size constant */
  247. } kte;
  248. Constant(uint32_t _kte, uint8_t size)
  249. {
  250. ident.idType = CONSTANT;
  251. kte.kte = _kte;
  252. kte.size = size;
  253. }
  254. virtual Expr *clone() const
  255. {
  256. return new Constant(*this);
  257. }
  258. std::string walkCondExpr(Function *pProc, int *numLoc) const;
  259. int hlTypeSize(Function *pproc) const;
  260. hlType expType(Function *pproc) const;
  261. };
  262. struct FuncNode : public AstIdent
  263. {
  264. struct _call { /* for FUNCTION only */
  265. Function *proc;
  266. STKFRAME *args;
  267. } call;
  268. FuncNode(Function *pproc, STKFRAME *args)
  269. {
  270. call.proc = pproc;
  271. call.args = args;
  272. }
  273. virtual Expr *clone() const
  274. {
  275. return new FuncNode(*this);
  276. }
  277. std::string walkCondExpr(Function *pProc, int *numLoc) const;
  278. int hlTypeSize(Function *pproc) const;
  279. hlType expType(Function *pproc) const;
  280. };
  281. struct RegisterNode : public AstIdent
  282. {
  283. const LOCAL_ID *m_syms;
  284. regType regiType; /* for REGISTER only */
  285. int regiIdx; /* index into localId, REGISTER */
  286. virtual Expr *insertSubTreeReg(Expr *_expr, eReg regi, const LOCAL_ID *locsym);
  287. RegisterNode(int idx, regType reg_type,const LOCAL_ID *syms)
  288. {
  289. m_syms= syms;
  290. ident.type(REGISTER);
  291. regiType = reg_type;
  292. regiIdx = idx;
  293. }
  294. RegisterNode(const LLOperand &, LOCAL_ID *locsym);
  295. //RegisterNode(eReg regi, uint32_t icodeFlg, LOCAL_ID *locsym);
  296. virtual Expr *clone() const
  297. {
  298. return new RegisterNode(*this);
  299. }
  300. std::string walkCondExpr(Function *pProc, int *numLoc) const;
  301. int hlTypeSize(Function *) const;
  302. hlType expType(Function *pproc) const;
  303. bool xClear(rICODE range_to_check, iICODE lastBBinst, const LOCAL_ID &locId);
  304. };