retdec
symbolic_tree.h
Go to the documentation of this file.
1 
11 #ifndef RETDEC_BIN2LLVMIR_ANALYSES_SYMBOLIC_TREE_H
12 #define RETDEC_BIN2LLVMIR_ANALYSES_SYMBOLIC_TREE_H
13 
14 #include <set>
15 #include <unordered_set>
16 #include <vector>
17 
18 #include <llvm/IR/Function.h>
19 #include <llvm/IR/Instruction.h>
20 #include <llvm/IR/Instructions.h>
21 #include <llvm/IR/Module.h>
22 
25 
26 namespace retdec {
27 namespace bin2llvmir {
28 
43 {
44  // Ctors, dtors.
45  //
46  public:
54  llvm::Value* v,
55  unsigned maxNodeLevel = 10
56  );
65  llvm::Value* v,
66  std::map<llvm::Value*, llvm::Value*>* val2val,
67  unsigned maxNodeLevel = 10
68  );
79  llvm::Value* v,
80  unsigned maxNodeLevel = 10
81  );
87  static SymbolicTree Linear(
88  llvm::Value* v,
89  unsigned maxNodeLevel = 10
90  );
91 
92  // Copy/move ctors, operators, etc.
93  //
94  public:
95  SymbolicTree(const SymbolicTree& other) = default;
96  SymbolicTree(SymbolicTree&& other) = default;
98  bool operator==(const SymbolicTree& o) const;
99  bool operator!=(const SymbolicTree& o) const;
100  friend std::ostream& operator<<(
101  std::ostream& out,
102  const SymbolicTree& s);
103  std::string print(unsigned indent = 0) const;
104 
105  // Misc methods.
106  //
107  public:
108  bool isNullary() const;
109  bool isUnary() const;
110  bool isBinary() const;
111  bool isTernary() const;
112  bool isNary(unsigned N) const;
113 
114  unsigned getLevel() const;
115 
116  void simplifyNode();
117  void solveMemoryLoads(FileImage* image);
118 
120 
121  // Tree linearization methods.
122  //
123  public:
124  std::vector<SymbolicTree*> getPreOrder() const;
125  std::vector<SymbolicTree*> getPostOrder() const;
126  std::vector<SymbolicTree*> getLevelOrder() const;
127 
128  // Public data.
129  //
130  public:
131  llvm::Value* value = nullptr;
132  llvm::Value* user = nullptr;
133  std::vector<SymbolicTree> ops;
134 
135  // Global SymbolicTree configuration methods and data.
136  //
137  public:
138  static void clear();
139  static bool isVal2ValMapUsed();
140  static void setAbi(Abi* abi);
141  static void setConfig(Config* config);
142  static void setToDefaultConfiguration();
143  static void setTrackThroughAllocaLoads(bool b);
144  static void setTrackThroughGeneralRegisterLoads(bool b);
145  static void setTrackOnlyFlagRegisters(bool b);
146  static void setSimplifyAtCreation(bool b);
147  static void setNaryLimit(unsigned n);
148 
149  private:
150  static Abi* _abi;
151  static Config* _config;
152  static bool _val2valUsed;
156  static bool _simplifyAtCreation;
157  static unsigned _naryLimit;
158 
159  // Private methods.
160  //
161  private:
162  void expandNode(
164  std::map<llvm::Value*, llvm::Value*>* val2val,
165  unsigned maxNodeLevel,
166  bool linear);
167 
168  void _simplifyNode();
169  void fixLevel(unsigned level = 0);
170 
171  void _getPreOrder(std::vector<SymbolicTree*>& res) const;
172  void _getPostOrder(std::vector<SymbolicTree*>& res) const;
173 
174  // Private ctors, dtors.
175  //
176  public:
181  SymbolicTree(
183  llvm::Value* v,
184  llvm::Value* u,
185  unsigned nodeLevel,
186  unsigned maxNodeLevel,
187  std::map<llvm::Value*, llvm::Value*>* v2v,
188  bool linear);
189 
190  // Private data.
191  //
192  private:
193  unsigned _level = 1;
194 };
195 
196 } // namespace bin2llvmir
197 } // namespace retdec
198 
199 #endif
Definition: abi.h:27
Definition: config.h:24
Definition: fileimage.h:27
Definition: reaching_definitions.h:121
Definition: symbolic_tree.h:43
unsigned _level
Definition: symbolic_tree.h:193
void solveMemoryLoads(FileImage *image)
Definition: symbolic_tree.cpp:501
static Config * _config
Definition: symbolic_tree.h:151
bool isNary(unsigned N) const
Definition: symbolic_tree.cpp:691
bool operator!=(const SymbolicTree &o) const
Definition: symbolic_tree.cpp:136
unsigned getLevel() const
Definition: symbolic_tree.cpp:96
void expandNode(ReachingDefinitionsAnalysis *RDA, std::map< llvm::Value *, llvm::Value * > *val2val, unsigned maxNodeLevel, bool linear)
Definition: symbolic_tree.cpp:141
bool isTernary() const
Definition: symbolic_tree.cpp:686
std::string print(unsigned indent=0) const
Definition: symbolic_tree.cpp:565
std::vector< SymbolicTree * > getPreOrder() const
Definition: symbolic_tree.cpp:598
static void setToDefaultConfiguration()
Definition: symbolic_tree.cpp:718
bool isUnary() const
Definition: symbolic_tree.cpp:676
void _getPreOrder(std::vector< SymbolicTree * > &res) const
Definition: symbolic_tree.cpp:637
static unsigned _naryLimit
Definition: symbolic_tree.h:157
static SymbolicTree PrecomputedRdaWithValueMap(ReachingDefinitionsAnalysis &rda, llvm::Value *v, std::map< llvm::Value *, llvm::Value * > *val2val, unsigned maxNodeLevel=10)
Definition: symbolic_tree.cpp:38
static void setTrackThroughGeneralRegisterLoads(bool b)
Definition: symbolic_tree.cpp:748
static void setAbi(Abi *abi)
Definition: symbolic_tree.cpp:733
friend std::ostream & operator<<(std::ostream &out, const SymbolicTree &s)
Definition: symbolic_tree.cpp:581
bool isNullary() const
Definition: symbolic_tree.cpp:671
std::vector< SymbolicTree * > getLevelOrder() const
Definition: symbolic_tree.cpp:623
static void setConfig(Config *config)
Definition: symbolic_tree.cpp:738
void _getPostOrder(std::vector< SymbolicTree * > &res) const
Definition: symbolic_tree.cpp:646
SymbolicTree & operator=(SymbolicTree &&other)
Definition: symbolic_tree.cpp:101
static void setTrackThroughAllocaLoads(bool b)
Definition: symbolic_tree.cpp:743
void fixLevel(unsigned level=0)
Definition: symbolic_tree.cpp:655
static bool _trackThroughGeneralRegisterLoads
Definition: symbolic_tree.h:154
void simplifyNode()
Definition: symbolic_tree.cpp:341
static bool _val2valUsed
Definition: symbolic_tree.h:152
std::vector< SymbolicTree > ops
Definition: symbolic_tree.h:133
static SymbolicTree PrecomputedRda(ReachingDefinitionsAnalysis &rda, llvm::Value *v, unsigned maxNodeLevel=10)
Definition: symbolic_tree.cpp:30
void _simplifyNode()
Definition: symbolic_tree.cpp:347
static Abi * _abi
Definition: symbolic_tree.h:150
static void setNaryLimit(unsigned n)
Definition: symbolic_tree.cpp:763
bool operator==(const SymbolicTree &o) const
Definition: symbolic_tree.cpp:114
SymbolicTree * getMaxIntValue()
Definition: symbolic_tree.cpp:529
SymbolicTree(SymbolicTree &&other)=default
std::vector< SymbolicTree * > getPostOrder() const
Definition: symbolic_tree.cpp:613
static void clear()
Definition: symbolic_tree.cpp:711
llvm::Value * value
Definition: symbolic_tree.h:131
static bool isVal2ValMapUsed()
Definition: symbolic_tree.cpp:728
SymbolicTree(const SymbolicTree &other)=default
static SymbolicTree Linear(llvm::Value *v, unsigned maxNodeLevel=10)
Definition: symbolic_tree.cpp:55
static void setTrackOnlyFlagRegisters(bool b)
Definition: symbolic_tree.cpp:753
bool isBinary() const
Definition: symbolic_tree.cpp:681
static bool _simplifyAtCreation
Definition: symbolic_tree.h:156
static bool _trackThroughAllocaLoads
Definition: symbolic_tree.h:153
static SymbolicTree OnDemandRda(llvm::Value *v, unsigned maxNodeLevel=10)
Definition: symbolic_tree.cpp:48
llvm::Value * user
Definition: symbolic_tree.h:132
static bool _trackOnlyFlagRegisters
Definition: symbolic_tree.h:155
static void setSimplifyAtCreation(bool b)
Definition: symbolic_tree.cpp:758
File image provider for bin2llvmirl.
The frontend-end part of the decompiler.
Definition: archive_wrapper.h:19
Reaching definitions analysis (RDA) builds UD and DU chains.