ast.h 10 KB

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