retdec
value_analysis.h
Go to the documentation of this file.
1 
7 #ifndef RETDEC_LLVMIR2HLL_ANALYSIS_VALUE_ANALYSIS_H
8 #define RETDEC_LLVMIR2HLL_ANALYSIS_VALUE_ANALYSIS_H
9 
10 #include <cstddef>
11 #include <map>
12 
19 
20 namespace retdec {
21 namespace llvmir2hll {
22 
23 class AliasAnalysis;
24 class Value;
25 
33 class ValueData {
34  friend class ValueAnalysis;
35 
36 public:
38  using var_iterator = VarSet::const_iterator;
39 
41  using call_iterator = CallVector::const_iterator;
42 
43 public:
44  ValueData(const ValueData &other) = default;
45 
46  ValueData &operator=(const ValueData &other) = default;
47  bool operator==(const ValueData &other) const;
48  bool operator!=(const ValueData &other) const;
49 
52  const VarSet &getDirReadVars() const;
53  const VarSet &getDirWrittenVars() const;
54  const VarSet &getDirAccessedVars() const;
55  std::size_t getNumOfDirReadVars() const;
56  std::size_t getNumOfDirWrittenVars() const;
57  std::size_t getNumOfDirAccessedVars() const;
58  std::size_t getDirNumOfUses(ShPtr<Variable> var) const;
59  bool isDirRead(ShPtr<Variable> var) const;
60  bool isDirWritten(ShPtr<Variable> var) const;
61  bool isDirAccessed(ShPtr<Variable> var) const;
62 
64  var_iterator dir_read_end() const;
65 
68 
70  var_iterator dir_all_end() const;
72 
75  // may
76  const VarSet &getMayBeReadVars() const;
77  const VarSet &getMayBeWrittenVars() const;
78  const VarSet &getMayBeAccessedVars() const;
79  bool mayBeIndirRead(ShPtr<Variable> var) const;
80  bool mayBeIndirWritten(ShPtr<Variable> var) const;
81  bool mayBeIndirAccessed(ShPtr<Variable> var) const;
82 
85 
88 
91 
92  // must
93  const VarSet &getMustBeReadVars() const;
94  const VarSet &getMustBeWrittenVars() const;
95  const VarSet &getMustBeAccessedVars() const;
96  bool mustBeIndirRead(ShPtr<Variable> var) const;
97  bool mustBeIndirWritten(ShPtr<Variable> var) const;
98  bool mustBeIndirAccessed(ShPtr<Variable> var) const;
99 
102 
105 
109 
112  const CallVector &getCalls() const;
113  bool hasCalls() const;
114  std::size_t getNumOfCalls() const;
115 
116  call_iterator call_begin() const;
117  call_iterator call_end() const;
119 
122  bool hasAddressOps() const;
123  bool hasAddressTaken(ShPtr<Variable> var) const;
125 
128  bool hasDerefs() const;
130 
133  bool hasArrayAccesses() const;
135 
138  bool hasStructAccesses() const;
140 
141 private:
143  using VarCountMap = std::map<ShPtr<Variable>, std::size_t>;
144 
145 private:
146  ValueData();
147 
148  void clear();
149 
150 private:
153 
156 
159 
162 
165 
168 
171 
174 
177 
180 
183 
186 
189 
192 
195 };
196 
212  private retdec::utils::NonCopyable, public ValidState,
213  public Caching<ShPtr<Value>, ShPtr<ValueData>> {
214 
215 public:
217 
220  void clearCache();
221  void removeFromCache(ShPtr<Value> value, bool recursive = true);
223 
227  const VarSet &mayPointTo(ShPtr<Variable> var) const;
229  bool mayBePointed(ShPtr<Variable> var) const;
231 
233  bool enableCaching = false);
234 
235 private:
237  bool enableCaching = false);
238 
240 
244  virtual void visit(ShPtr<Function> func) override;
245  // Statements
246  virtual void visit(ShPtr<AssignStmt> stmt) override;
247  virtual void visit(ShPtr<BreakStmt> stmt) override;
248  virtual void visit(ShPtr<CallStmt> stmt) override;
249  virtual void visit(ShPtr<ContinueStmt> stmt) override;
250  virtual void visit(ShPtr<EmptyStmt> stmt) override;
251  virtual void visit(ShPtr<ForLoopStmt> stmt) override;
252  virtual void visit(ShPtr<UForLoopStmt> stmt) override;
253  virtual void visit(ShPtr<GotoStmt> stmt) override;
254  virtual void visit(ShPtr<IfStmt> stmt) override;
255  virtual void visit(ShPtr<ReturnStmt> stmt) override;
256  virtual void visit(ShPtr<SwitchStmt> stmt) override;
257  virtual void visit(ShPtr<UnreachableStmt> stmt) override;
258  virtual void visit(ShPtr<VarDefStmt> stmt) override;
259  virtual void visit(ShPtr<WhileLoopStmt> stmt) override;
260  // Expressions
261  virtual void visit(ShPtr<AddOpExpr> expr) override;
262  virtual void visit(ShPtr<AddressOpExpr> expr) override;
263  virtual void visit(ShPtr<AndOpExpr> expr) override;
264  virtual void visit(ShPtr<ArrayIndexOpExpr> expr) override;
265  virtual void visit(ShPtr<AssignOpExpr> expr) override;
266  virtual void visit(ShPtr<BitAndOpExpr> expr) override;
267  virtual void visit(ShPtr<BitOrOpExpr> expr) override;
268  virtual void visit(ShPtr<BitShlOpExpr> expr) override;
269  virtual void visit(ShPtr<BitShrOpExpr> expr) override;
270  virtual void visit(ShPtr<BitXorOpExpr> expr) override;
271  virtual void visit(ShPtr<CallExpr> expr) override;
272  virtual void visit(ShPtr<CommaOpExpr> expr) override;
273  virtual void visit(ShPtr<DerefOpExpr> expr) override;
274  virtual void visit(ShPtr<DivOpExpr> expr) override;
275  virtual void visit(ShPtr<EqOpExpr> expr) override;
276  virtual void visit(ShPtr<GtEqOpExpr> expr) override;
277  virtual void visit(ShPtr<GtOpExpr> expr) override;
278  virtual void visit(ShPtr<LtEqOpExpr> expr) override;
279  virtual void visit(ShPtr<LtOpExpr> expr) override;
280  virtual void visit(ShPtr<ModOpExpr> expr) override;
281  virtual void visit(ShPtr<MulOpExpr> expr) override;
282  virtual void visit(ShPtr<NegOpExpr> expr) override;
283  virtual void visit(ShPtr<NeqOpExpr> expr) override;
284  virtual void visit(ShPtr<NotOpExpr> expr) override;
285  virtual void visit(ShPtr<OrOpExpr> expr) override;
286  virtual void visit(ShPtr<StructIndexOpExpr> expr) override;
287  virtual void visit(ShPtr<SubOpExpr> expr) override;
288  virtual void visit(ShPtr<TernaryOpExpr> expr) override;
289  virtual void visit(ShPtr<Variable> var) override;
290  // Casts
291  virtual void visit(ShPtr<BitCastExpr> expr) override;
292  virtual void visit(ShPtr<ExtCastExpr> expr) override;
293  virtual void visit(ShPtr<FPToIntCastExpr> expr) override;
294  virtual void visit(ShPtr<IntToFPCastExpr> expr) override;
295  virtual void visit(ShPtr<IntToPtrCastExpr> expr) override;
296  virtual void visit(ShPtr<PtrToIntCastExpr> expr) override;
297  virtual void visit(ShPtr<TruncCastExpr> expr) override;
298  // Constants
299  virtual void visit(ShPtr<ConstArray> constant) override;
300  virtual void visit(ShPtr<ConstBool> constant) override;
301  virtual void visit(ShPtr<ConstFloat> constant) override;
302  virtual void visit(ShPtr<ConstInt> constant) override;
303  virtual void visit(ShPtr<ConstNullPointer> constant) override;
304  virtual void visit(ShPtr<ConstString> constant) override;
305  virtual void visit(ShPtr<ConstStruct> constant) override;
307 
308 private:
311 
314 
316  bool writing;
317 
320 };
321 
322 } // namespace llvmir2hll
323 } // namespace retdec
324 
325 #endif
A mixin for enabling caching of computed results.
A mixin for enabling caching of computed results.
Definition: caching.h:51
void enableCaching()
Enables caching.
Definition: caching.h:60
A visitor that visits everything in an ordered way.
Definition: ordered_all_visitor.h:44
virtual void visit(ShPtr< GlobalVarDef > varDef) override
Definition: ordered_all_visitor.cpp:95
A mixin providing support for keeping the validity of an object.
Definition: valid_state.h:31
An analysis for obtaining information about a value.
Definition: value_analysis.h:213
bool removingFromCache
Are we removing values from the cache?
Definition: value_analysis.h:319
ShPtr< Variable > pointsTo(ShPtr< Variable > var) const
Returns the variable to which var always points.
Definition: value_analysis.cpp:659
static ShPtr< ValueAnalysis > create(ShPtr< AliasAnalysis > aliasAnalysis, bool enableCaching=false)
Creates a new analysis.
Definition: value_analysis.cpp:687
bool mayBePointed(ShPtr< Variable > var) const
Returns true if a pointer may point to var, false otherwise.
Definition: value_analysis.cpp:670
ValueAnalysis(ShPtr< AliasAnalysis > aliasAnalysis, bool enableCaching=false)
Constructs a new visitor.
Definition: value_analysis.cpp:559
const VarSet & mayPointTo(ShPtr< Variable > var) const
Returns the set of variables to which var may point to.
Definition: value_analysis.cpp:649
ShPtr< ValueData > getValueData(ShPtr< Value > value)
Returns information about the given value.
Definition: value_analysis.cpp:571
virtual void visit(ShPtr< GlobalVarDef > varDef) override
Definition: ordered_all_visitor.cpp:95
ShPtr< AliasAnalysis > aliasAnalysis
The used alias analysis.
Definition: value_analysis.h:310
bool writing
Are we writing into a variable?
Definition: value_analysis.h:316
void computeAndStoreIndirectlyUsedVars(ShPtr< DerefOpExpr > expr)
Computes indirectly used variables in the given dereferencing expression and stores them in appropria...
Definition: value_analysis.cpp:698
void clearCache()
Clears the cache of the already cached results.
Definition: value_analysis.cpp:602
void removeFromCache(ShPtr< Value > value, bool recursive=true)
Removes the selected value from the cache.
Definition: value_analysis.cpp:617
void initAliasAnalysis(ShPtr< Module > module)
Re-initializes the underlying alias analysis.
Definition: value_analysis.cpp:639
ShPtr< ValueData > valueData
Information about the currently computed value.
Definition: value_analysis.h:313
Information about a value.
Definition: value_analysis.h:33
bool mustBeIndirAccessed(ShPtr< Variable > var) const
Returns true if var must be indirectly accessed, false otherwise.
Definition: value_analysis.cpp:406
std::size_t getNumOfCalls() const
Returns the number of calls.
Definition: value_analysis.cpp:475
bool hasAddressTaken(ShPtr< Variable > var) const
Returns true if var has its address taken, false otherwise.
Definition: value_analysis.cpp:506
bool hasDerefs() const
Returns true if there are any dereferences, false otherwise.
Definition: value_analysis.cpp:515
VarSet mustBeReadVars
Set of variables that must be read.
Definition: value_analysis.h:173
var_iterator must_be_accessed_end() const
Returns an iterator past the last variable that must be accessed.
Definition: value_analysis.cpp:454
const VarSet & getMustBeWrittenVars() const
Returns the set of variables into which must be indirectly written.
Definition: value_analysis.cpp:376
VarSet dirReadVars
Set of variables that are directly read.
Definition: value_analysis.h:152
var_iterator may_be_read_begin() const
Returns an iterator to the first variable that may be indirectly read.
Definition: value_analysis.cpp:308
bool isDirRead(ShPtr< Variable > var) const
Returns true if var is directly read, false otherwise.
Definition: value_analysis.cpp:230
var_iterator may_be_read_end() const
Returns an iterator past the last variable that may be indirectly read.
Definition: value_analysis.cpp:319
var_iterator dir_all_end() const
Returns an iterator past the last directly accessed variable.
Definition: value_analysis.cpp:223
bool hasArrayAccesses() const
Returns true if there are any array accesses, false otherwise.
Definition: value_analysis.cpp:522
CallVector calls
List of function calls.
Definition: value_analysis.h:182
bool hasCalls() const
Returns true if there are function calls, false otherwise.
Definition: value_analysis.cpp:468
CallVector::const_iterator call_iterator
Calls iterator.
Definition: value_analysis.h:41
bool hasStructAccesses() const
Returns true if there are any struct accesses, false otherwise.
Definition: value_analysis.cpp:529
var_iterator must_be_read_end() const
Returns an iterator past the last variable that must be indirectly read.
Definition: value_analysis.cpp:422
var_iterator may_be_accessed_begin() const
Returns an iterator to the first variable that may be accessed.
Definition: value_analysis.cpp:352
VarSet mustBeWrittenVars
Set of variables into which something must be written.
Definition: value_analysis.h:176
const VarSet & getDirReadVars() const
Returns the variables that are directly read.
Definition: value_analysis.cpp:129
bool hasAddressOps() const
Returns true if there are any address operators, false otherwise.
Definition: value_analysis.cpp:496
const VarSet & getMustBeAccessedVars() const
Returns the set of variables that must be indirectly accessed.
Definition: value_analysis.cpp:383
var_iterator must_be_written_begin() const
Returns an iterator to the first variable into which must be written.
Definition: value_analysis.cpp:430
const VarSet & getMayBeAccessedVars() const
Returns the set of variables that may be indirectly accessed.
Definition: value_analysis.cpp:274
bool operator==(const ValueData &other) const
Returns true if the current object is equal to other, false otherwise.
Definition: value_analysis.cpp:100
bool operator!=(const ValueData &other) const
Returns true if the current object is not equal to other, false otherwise.
Definition: value_analysis.cpp:122
bool containsStructAccesses
Are there any struct accesses?
Definition: value_analysis.h:194
VarSet::const_iterator var_iterator
Variables iterator.
Definition: value_analysis.h:38
var_iterator dir_all_begin() const
Returns an iterator to the first directly accessed variable.
Definition: value_analysis.cpp:216
ValueData & operator=(const ValueData &other)=default
call_iterator call_begin() const
Returns an iterator to the first call.
Definition: value_analysis.cpp:482
VarSet addressTakenVars
Set of variables whose address is taken.
Definition: value_analysis.h:185
VarSet mayBeReadVars
Set of variables that may be read.
Definition: value_analysis.h:164
const VarSet & getMayBeReadVars() const
Returns the set of variables that may be indirectly read.
Definition: value_analysis.cpp:254
ValueData()
Constructs a new ValueData object.
Definition: value_analysis.cpp:90
VarSet mayBeWrittenVars
Set of variables into which something may be written.
Definition: value_analysis.h:167
var_iterator dir_written_end() const
Returns an iterator past the last directly written variable.
Definition: value_analysis.cpp:209
const VarSet & getDirAccessedVars() const
Returns the set of all directly accessed variables.
Definition: value_analysis.cpp:143
std::size_t getDirNumOfUses(ShPtr< Variable > var) const
Returns the number of direct uses of var.
Definition: value_analysis.cpp:174
std::map< ShPtr< Variable >, std::size_t > VarCountMap
Mapping of a variable into a count.
Definition: value_analysis.h:143
bool isDirWritten(ShPtr< Variable > var) const
Returns true if var is directly written, false otherwise.
Definition: value_analysis.cpp:237
const CallVector & getCalls() const
Returns all function calls.
Definition: value_analysis.cpp:461
bool containsDerefs
Are there any dereferences?
Definition: value_analysis.h:188
bool mustBeIndirRead(ShPtr< Variable > var) const
Returns true if var must be indirectly read, false otherwise.
Definition: value_analysis.cpp:390
ValueData(const ValueData &other)=default
const VarSet & getDirWrittenVars() const
Returns the variables that are directly written into.
Definition: value_analysis.cpp:136
VarCountMap dirNumOfVarUses
Number of uses of a variable in direct accesses.
Definition: value_analysis.h:161
var_iterator dir_written_begin() const
Returns an iterator to the first directly written variable.
Definition: value_analysis.cpp:202
std::size_t getNumOfDirWrittenVars() const
Returns the number of directly written variables.
Definition: value_analysis.cpp:157
bool mayBeIndirAccessed(ShPtr< Variable > var) const
Returns true if var may be indirectly accessed, false otherwise.
Definition: value_analysis.cpp:297
std::size_t getNumOfDirAccessedVars() const
Returns the number of directly accessed variables.
Definition: value_analysis.cpp:164
var_iterator dir_read_end() const
Returns an iterator past the last directly read variable.
Definition: value_analysis.cpp:195
bool mustBeIndirWritten(ShPtr< Variable > var) const
Returns true if var must be indirectly written-into, false otherwise.
Definition: value_analysis.cpp:398
const VarSet & getMayBeWrittenVars() const
Returns the set of variables into which may be indirectly written.
Definition: value_analysis.cpp:264
bool containsArrayAccesses
Are there any array accesses?
Definition: value_analysis.h:191
std::size_t getNumOfDirReadVars() const
Returns the number of directly read variables.
Definition: value_analysis.cpp:150
var_iterator must_be_accessed_begin() const
Returns an iterator to the first variable that must be accessed.
Definition: value_analysis.cpp:446
const VarSet & getMustBeReadVars() const
Returns the set of variables that must be indirectly read.
Definition: value_analysis.cpp:369
var_iterator may_be_written_begin() const
Returns an iterator to the first variable into which may be written.
Definition: value_analysis.cpp:330
VarSet dirAllVars
Set of all directly accessed variables (read or written).
Definition: value_analysis.h:158
var_iterator must_be_written_end() const
Returns an iterator past the last variable into which must be written.
Definition: value_analysis.cpp:438
void clear()
Clears all private containers and variables.
Definition: value_analysis.cpp:536
var_iterator may_be_accessed_end() const
Returns an iterator past the last variable that may be.
Definition: value_analysis.cpp:362
var_iterator dir_read_begin() const
Returns an iterator to the first directly read variable.
Definition: value_analysis.cpp:188
bool mayBeIndirWritten(ShPtr< Variable > var) const
Returns true if var may be indirectly written-into, false otherwise.
Definition: value_analysis.cpp:289
VarSet dirWrittenVars
Set of variables into which something is directly written.
Definition: value_analysis.h:155
VarSet mustBeAccessedVars
Set of variables which must be accessed.
Definition: value_analysis.h:179
call_iterator call_end() const
Returns an iterator past the last call.
Definition: value_analysis.cpp:489
var_iterator may_be_written_end() const
Returns an iterator past the last variable into which may be written.
Definition: value_analysis.cpp:341
var_iterator must_be_read_begin() const
Returns an iterator to the first variable that must be indirectly read.
Definition: value_analysis.cpp:414
VarSet mayBeAccessedVars
Set of variables which may be accessed.
Definition: value_analysis.h:170
bool isDirAccessed(ShPtr< Variable > var) const
Returns true if var is directly accessed, false otherwise.
Definition: value_analysis.cpp:244
bool mayBeIndirRead(ShPtr< Variable > var) const
Returns true if var may be indirectly read, false otherwise.
Definition: value_analysis.cpp:281
A mixin to make classes non-copyable.
Definition: non_copyable.h:27
ShPtr< Module > module
The current module.
Definition: hll_writer.cpp:100
A library providing API for working with back-end IR.
std::shared_ptr< T > ShPtr
An alias for a shared pointer.
Definition: smart_ptr.h:18
std::set< ShPtr< Variable > > VarSet
Set of variables.
Definition: types.h:57
std::vector< ShPtr< CallExpr > > CallVector
Vector of function calls.
Definition: types.h:102
Definition: archive_wrapper.h:19
A mixin to make classes non-copyable.
A visitor that visits everything in an ordered way.
Declarations, aliases, macros, etc. for the use of smart pointers.
Aliases for several useful types.
A mixin providing support for keeping the validity of an object.