retdec
simple_types.h
Go to the documentation of this file.
1 
7 #ifndef RETDEC_BIN2LLVMIR_OPTIMIZATIONS_SIMPLE_TYPES_SIMPLE_TYPES_H
8 #define RETDEC_BIN2LLVMIR_OPTIMIZATIONS_SIMPLE_TYPES_SIMPLE_TYPES_H
9 
10 #include <functional>
11 #include <list>
12 #include <map>
13 #include <set>
14 #include <unordered_map>
15 #include <unordered_set>
16 
17 #include <llvm/IR/Function.h>
18 #include <llvm/IR/Module.h>
19 #include <llvm/Pass.h>
20 
23 
24 namespace retdec {
25 namespace bin2llvmir {
26 
27 class ValueEntry;
28 class TypeEntry;
29 class EquationEntry;
30 class EqSet;
31 class EqSetContainer;
32 
37 enum class eSourcePriority
38 {
39  PRIORITY_NONE = 0,
42 };
43 
48 {
49  public:
50  ValueEntry(llvm::Value* v = nullptr, eSourcePriority p = eSourcePriority::PRIORITY_NONE);
51  llvm::Type* getTypeForPropagation() const;
52  bool operator==(const ValueEntry& o) const;
53  bool operator<(const ValueEntry& o) const;
54  std::size_t hash() const;
55  friend std::ostream& operator<<(std::ostream& out, const ValueEntry& ve);
56 
57  public:
58  llvm::Value* value = nullptr;
60 };
62 {
63  std::size_t operator() (const ValueEntry& v) const { return v.hash(); }
64 };
65 
69 class TypeEntry
70 {
71  public:
72  TypeEntry(llvm::Type* t = nullptr, eSourcePriority p = eSourcePriority::PRIORITY_NONE);
73  bool operator==(const TypeEntry& o) const;
74  bool operator<(const TypeEntry& o) const;
75  std::size_t hash() const;
76  friend std::ostream& operator<<(std::ostream& out, const TypeEntry& te);
77 
78  public:
79  llvm::Type* type = nullptr;
81 };
83 {
84  std::size_t operator() (const TypeEntry& t) const { return t.hash(); }
85 };
86 
91 {
92  public:
95 
96  bool operator==(const EquationEntry& o) const;
97  bool operator<(const EquationEntry& o) const;
98  std::size_t hash() const;
99  friend std::ostream& operator<<(std::ostream& out, const EquationEntry& ee);
100 
101  bool isOtherIsPtrToThis();
102  bool isThisIsPtrToOther();
103 
104  public:
106 
107  private:
108  enum class eqType
109  {
112  };
113 
114  private:
115  EquationEntry(EqSet* o, eqType t);
116 
117  private:
119 };
121 {
122  std::size_t operator() (const EquationEntry& e) const { return e.hash(); }
123 };
124 
125 using ValueEntrySet = std::unordered_set<ValueEntry, ValueEntryHash>;
126 using TypeEntrySet = std::unordered_set<TypeEntry, TypeEntryHash>;
127 using EquationEntrySet = std::unordered_set<EquationEntry, EquationEntryHash>;
128 
132 class EqSet
133 {
134  public:
135  EqSet(std::size_t id);
136  void insert(Config* config, llvm::Value* v, eSourcePriority p = eSourcePriority::PRIORITY_NONE);
137  void insert(llvm::Type* t, eSourcePriority p = eSourcePriority::PRIORITY_NONE);
138  void propagate(llvm::Module* module);
139  void apply(
140  llvm::Module* module,
141  Config* config,
142  FileImage* objf,
143  std::unordered_set<llvm::Instruction*>& instToErase);
144 
145  friend std::ostream& operator<<(std::ostream& out, const EqSet& eq);
146 
147  private:
148  llvm::Type* getHigherPriorityType(
149  llvm::Module* module,
150  llvm::Type* t1,
151  llvm::Type* t2);
152  llvm::Type* getHigherPriorityTypePrivate(
153  llvm::Module* module,
154  llvm::Type* t1,
155  llvm::Type* t2,
156  std::unordered_set<llvm::Type*>& seen);
157 
158  public:
160  const std::size_t id;
161 
171 };
172 
177 {
178  public:
180  void propagate(llvm::Module* module);
181  void apply(
182  llvm::Module* module,
183  Config* config,
184  FileImage* objf,
185  std::unordered_set<llvm::Instruction*>& valsToErase);
186 
187  friend std::ostream& operator<<(std::ostream& out, const EqSetContainer& eqs);
188 
189  public:
190  std::list<EqSet> eqSets;
191 };
192 
193 using ValueMap = std::unordered_map<llvm::Value*, EqSet*>;
194 using ValuePair = std::pair<llvm::Value*, llvm::Value*>;
195 using ValuePairList = std::list<ValuePair>;
196 
200 class SimpleTypesAnalysis : public llvm::ModulePass
201 {
202  public:
203  static char ID;
205 
206  virtual bool runOnModule(llvm::Module& m) override;
207  virtual void getAnalysisUsage(llvm::AnalysisUsage& AU) const override;
208 
209  private:
210  void buildEqSets(llvm::Module& M);
211  void buildEquations();
212  void processRoot(llvm::Value* root);
213  void processValue(std::queue<llvm::Value*>& toProcess, EqSet& eqSet);
214  void processUse(llvm::Value* c, llvm::Value* x, std::queue<llvm::Value*>& toProcess, EqSet& eqSet);
216  void setGlobalConstants();
217 
218  private:
222 
224  llvm::Module* module = nullptr;
225  const llvm::GlobalVariable* _specialGlobal = nullptr;
226  Config* config = nullptr;
227  FileImage* objf = nullptr;
228 
229  std::unordered_set<llvm::Instruction*> instToErase;
230 };
231 
232 } // namespace bin2llvmir
233 } // namespace retdec
234 
235 #endif
Debugging utilities.
Definition: config.h:24
Definition: simple_types.h:177
friend std::ostream & operator<<(std::ostream &out, const EqSetContainer &eqs)
Definition: simple_types.cpp:750
EqSet & createEmptySet()
Definition: simple_types.cpp:724
std::list< EqSet > eqSets
Definition: simple_types.h:190
void apply(llvm::Module *module, Config *config, FileImage *objf, std::unordered_set< llvm::Instruction * > &valsToErase)
Definition: simple_types.cpp:738
void propagate(llvm::Module *module)
Definition: simple_types.cpp:730
Definition: simple_types.h:133
TypeEntrySet typeSet
This allows to add certain types to set without having a value for them.
Definition: simple_types.h:167
EqSet(std::size_t id)
Definition: simple_types.cpp:767
void apply(llvm::Module *module, Config *config, FileImage *objf, std::unordered_set< llvm::Instruction * > &instToErase)
Definition: simple_types.cpp:1220
ValueEntrySet valSet
Values in the set.
Definition: simple_types.h:165
friend std::ostream & operator<<(std::ostream &out, const EqSet &eq)
Definition: simple_types.cpp:1272
llvm::Type * getHigherPriorityType(llvm::Module *module, llvm::Type *t1, llvm::Type *t2)
Definition: simple_types.cpp:843
void propagate(llvm::Module *module)
Definition: simple_types.cpp:1152
const std::size_t id
Each instance gets its own unique ID for debug print purposes.
Definition: simple_types.h:160
llvm::Type * getHigherPriorityTypePrivate(llvm::Module *module, llvm::Type *t1, llvm::Type *t2, std::unordered_set< llvm::Type * > &seen)
Definition: simple_types.cpp:860
EquationEntrySet equationSet
Definition: simple_types.h:170
void insert(Config *config, llvm::Value *v, eSourcePriority p=eSourcePriority::PRIORITY_NONE)
Definition: simple_types.cpp:773
TypeEntry masterType
Type of an entire equivalence set.
Definition: simple_types.h:163
Definition: simple_types.h:91
bool operator==(const EquationEntry &o) const
Definition: simple_types.cpp:1430
eqType type
Definition: simple_types.h:118
EquationEntry(EqSet *o, eqType t)
Definition: simple_types.cpp:1413
std::size_t hash() const
Definition: simple_types.cpp:1440
static EquationEntry otherIsPtrToThis(EqSet *o)
Definition: simple_types.cpp:1420
eqType
Definition: simple_types.h:109
bool operator<(const EquationEntry &o) const
Definition: simple_types.cpp:1435
bool isOtherIsPtrToThis()
Definition: simple_types.cpp:1446
static EquationEntry thisIsPtrToOther(EqSet *o)
Definition: simple_types.cpp:1425
friend std::ostream & operator<<(std::ostream &out, const EquationEntry &ee)
Definition: simple_types.cpp:1456
EqSet * other
Definition: simple_types.h:105
bool isThisIsPtrToOther()
Definition: simple_types.cpp:1451
Definition: fileimage.h:27
Definition: reaching_definitions.h:121
Definition: simple_types.h:201
void buildEquations()
Definition: simple_types.cpp:685
virtual bool runOnModule(llvm::Module &m) override
Definition: simple_types.cpp:70
ReachingDefinitionsAnalysis RDA
Definition: simple_types.h:223
Config * config
Definition: simple_types.h:226
std::unordered_set< llvm::Instruction * > instToErase
Definition: simple_types.h:229
void processValue(std::queue< llvm::Value * > &toProcess, EqSet &eqSet)
Definition: simple_types.cpp:360
void processUse(llvm::Value *c, llvm::Value *x, std::queue< llvm::Value * > &toProcess, EqSet &eqSet)
Definition: simple_types.cpp:384
virtual void getAnalysisUsage(llvm::AnalysisUsage &AU) const override
Definition: simple_types.cpp:65
void setGlobalConstants()
Definition: simple_types.cpp:226
llvm::Module * module
Definition: simple_types.h:224
void processRoot(llvm::Value *root)
Definition: simple_types.cpp:332
void buildEqSets(llvm::Module &M)
Definition: simple_types.cpp:291
ValuePairList val2PtrVal
Definition: simple_types.h:221
SimpleTypesAnalysis()
Definition: simple_types.cpp:59
FileImage * objf
Definition: simple_types.h:227
const llvm::GlobalVariable * _specialGlobal
Definition: simple_types.h:225
EqSetContainer eqSets
Definition: simple_types.h:220
void eraseObsoleteInstructions()
Definition: simple_types.cpp:710
ValueMap processedObjs
Definition: simple_types.h:219
static char ID
Definition: simple_types.h:203
Definition: simple_types.h:70
eSourcePriority priority
Definition: simple_types.h:80
bool operator==(const TypeEntry &o) const
Definition: simple_types.cpp:1384
friend std::ostream & operator<<(std::ostream &out, const TypeEntry &te)
Definition: simple_types.cpp:1400
std::size_t hash() const
Definition: simple_types.cpp:1394
TypeEntry(llvm::Type *t=nullptr, eSourcePriority p=eSourcePriority::PRIORITY_NONE)
Definition: simple_types.cpp:1377
bool operator<(const TypeEntry &o) const
Definition: simple_types.cpp:1389
llvm::Type * type
Definition: simple_types.h:79
Definition: simple_types.h:48
std::size_t hash() const
Definition: simple_types.cpp:1355
llvm::Type * getTypeForPropagation() const
Definition: simple_types.cpp:1316
bool operator==(const ValueEntry &o) const
Definition: simple_types.cpp:1345
ValueEntry(llvm::Value *v=nullptr, eSourcePriority p=eSourcePriority::PRIORITY_NONE)
Definition: simple_types.cpp:1301
llvm::Value * value
Definition: simple_types.h:58
bool operator<(const ValueEntry &o) const
Definition: simple_types.cpp:1350
eSourcePriority priority
Definition: simple_types.h:59
friend std::ostream & operator<<(std::ostream &out, const ValueEntry &ve)
Definition: simple_types.cpp:1361
File image provider for bin2llvmirl.
ShPtr< Module > module
The current module.
Definition: hll_writer.cpp:100
The frontend-end part of the decompiler.
std::pair< llvm::Value *, llvm::Value * > ValuePair
Definition: simple_types.h:194
std::unordered_set< EquationEntry, EquationEntryHash > EquationEntrySet
Definition: simple_types.h:127
std::unordered_set< ValueEntry, ValueEntryHash > ValueEntrySet
Definition: simple_types.h:125
eSourcePriority
Definition: simple_types.h:38
std::list< ValuePair > ValuePairList
Definition: simple_types.h:195
std::unordered_set< TypeEntry, TypeEntryHash > TypeEntrySet
Definition: simple_types.h:126
std::unordered_map< llvm::Value *, EqSet * > ValueMap
Definition: simple_types.h:193
Definition: archive_wrapper.h:19
Definition: simple_types.h:121
std::size_t operator()(const EquationEntry &e) const
Definition: simple_types.h:122
Definition: simple_types.h:83
std::size_t operator()(const TypeEntry &t) const
Definition: simple_types.h:84
Definition: simple_types.h:62
std::size_t operator()(const ValueEntry &v) const
Definition: simple_types.h:63