ast.h 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320
  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 QString 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 QString 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. private:
  102. QString wrapUnary(Function *pProc, int *numLoc, QChar op) const;
  103. };
  104. struct BinaryOperator : public Expr
  105. {
  106. condOp m_op;
  107. Expr *m_lhs;
  108. Expr *m_rhs;
  109. BinaryOperator(condOp o) : Expr(BOOLEAN_OP)
  110. {
  111. m_op = o;
  112. m_lhs=m_rhs=nullptr;
  113. }
  114. BinaryOperator(condOp o,Expr *l,Expr *r) : Expr(BOOLEAN_OP)
  115. {
  116. m_op = o;
  117. m_lhs=l;
  118. m_rhs=r;
  119. }
  120. ~BinaryOperator()
  121. {
  122. assert(m_lhs!=m_rhs or m_lhs==nullptr);
  123. delete m_lhs;
  124. delete m_rhs;
  125. m_lhs=m_rhs=nullptr;
  126. }
  127. static BinaryOperator *Create(condOp o,Expr *l,Expr *r)
  128. {
  129. BinaryOperator *res = new BinaryOperator(o);
  130. res->m_lhs = l;
  131. res->m_rhs = r;
  132. return res;
  133. }
  134. static BinaryOperator *LogicAnd(Expr *l,Expr *r)
  135. {
  136. return Create(DBL_AND,l,r);
  137. }
  138. static BinaryOperator *createSHL(Expr *l,Expr *r)
  139. {
  140. return Create(SHL,l,r);
  141. }
  142. static BinaryOperator *And(Expr *l,Expr *r)
  143. {
  144. return Create(AND,l,r);
  145. }
  146. static BinaryOperator *Or(Expr *l,Expr *r)
  147. {
  148. return Create(OR,l,r);
  149. }
  150. static BinaryOperator *LogicOr(Expr *l,Expr *r)
  151. {
  152. return Create(DBL_OR,l,r);
  153. }
  154. static BinaryOperator *CreateAdd(Expr *l,Expr *r) {
  155. return Create(ADD,l,r);
  156. }
  157. void changeBoolOp(condOp newOp);
  158. virtual Expr *inverse() const;
  159. virtual Expr *clone() const;
  160. virtual bool xClear(rICODE range_to_check, iICODE lastBBinst, const LOCAL_ID &locs);
  161. virtual Expr *insertSubTreeReg(Expr *_expr, eReg regi, const LOCAL_ID *locsym);
  162. virtual Expr *insertSubTreeLongReg(Expr *_expr, int longIdx);
  163. const Expr *lhs() const
  164. {
  165. return const_cast<const Expr *>(const_cast<BinaryOperator *>(this)->lhs());
  166. }
  167. const Expr *rhs() const
  168. {
  169. return const_cast<const Expr *>(const_cast<BinaryOperator *>(this)->rhs());
  170. }
  171. Expr *lhs()
  172. {
  173. assert(m_type==BOOLEAN_OP);
  174. return m_lhs;
  175. }
  176. Expr *rhs()
  177. {
  178. assert(m_type==BOOLEAN_OP);
  179. return m_rhs;
  180. }
  181. condOp op() const { return m_op;}
  182. /* Changes the boolean conditional operator at the root of this expression */
  183. void op(condOp o) { m_op=o;}
  184. QString walkCondExpr(Function * pProc, int* numLoc) const;
  185. public:
  186. hlType expType(Function *pproc) const;
  187. int hlTypeSize(Function *pproc) const;
  188. };
  189. struct AstIdent : public UnaryOperator
  190. {
  191. AstIdent() : UnaryOperator(IDENTIFIER)
  192. {
  193. }
  194. IDENTTYPE ident; /* for IDENTIFIER */
  195. static AstIdent * Loc(int off, LOCAL_ID *localId);
  196. static AstIdent * LongIdx(int idx);
  197. static AstIdent * String(uint32_t idx);
  198. static AstIdent * Other(eReg seg, eReg regi, int16_t off);
  199. static AstIdent * Param(int off, const STKFRAME *argSymtab);
  200. static AstIdent * Long(LOCAL_ID *localId, opLoc sd, iICODE pIcode, hlFirst f, iICODE ix, operDu du, LLInst &atOffset);
  201. static AstIdent * idID(const ID *retVal, LOCAL_ID *locsym, iICODE ix_);
  202. static Expr * id(const LLInst &ll_insn, opLoc sd, Function *pProc, iICODE ix_, ICODE &duIcode, operDu du);
  203. virtual Expr *clone() const
  204. {
  205. return new AstIdent(*this);
  206. }
  207. virtual int hlTypeSize(Function *pproc) const;
  208. virtual hlType expType(Function *pproc) const;
  209. virtual Expr * performLongRemoval(eReg regi, LOCAL_ID *locId);
  210. virtual QString walkCondExpr(Function *pProc, int *numLoc) const;
  211. virtual Expr *insertSubTreeReg(Expr *_expr, eReg regi, const LOCAL_ID *locsym);
  212. virtual Expr *insertSubTreeLongReg(Expr *_expr, int longIdx);
  213. virtual bool xClear(rICODE range_to_check, iICODE lastBBinst, const LOCAL_ID &locId);
  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. QString 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. QString 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. QString walkCondExpr(Function *pProc, int *numLoc) const;
  259. int hlTypeSize(Function *pproc) const;
  260. hlType expType(Function *pproc) const { return TYPE_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. QString 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. QString 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. };