retdec
call_info_obtainer.h
Go to the documentation of this file.
1 
8 #ifndef RETDEC_LLVMIR2HLL_OBTAINER_CALL_INFO_OBTAINER_H
9 #define RETDEC_LLVMIR2HLL_OBTAINER_CALL_INFO_OBTAINER_H
10 
11 #include <stack>
12 #include <string>
13 
18 
19 namespace retdec {
20 namespace llvmir2hll {
21 
22 class CFG;
23 class CFGBuilder;
24 class CallExpr;
25 class Function;
26 class Module;
27 class ValueAnalysis;
28 
35  friend class CallInfoObtainer;
36 
37 public:
38  // It needs to be public so it can be called in ShPtr's destructor.
39  virtual ~CallInfo() = default;
40 
41  ShPtr<CallExpr> getCall() const;
42 
47  virtual bool isNeverRead(ShPtr<Variable> var) const = 0;
48 
53  virtual bool mayBeRead(ShPtr<Variable> var) const = 0;
54 
62  virtual bool isAlwaysRead(ShPtr<Variable> var) const = 0;
63 
68  virtual bool isNeverModified(ShPtr<Variable> var) const = 0;
69 
74  virtual bool mayBeModified(ShPtr<Variable> var) const = 0;
75 
84  virtual bool isAlwaysModified(ShPtr<Variable> var) const = 0;
85 
94  virtual bool valueIsNeverChanged(ShPtr<Variable> var) const = 0;
95 
104  virtual bool isAlwaysModifiedBeforeRead(ShPtr<Variable> var) const = 0;
105 
106 protected:
107  explicit CallInfo(ShPtr<CallExpr> call);
108 
109 protected:
112 };
113 
120  friend class CallInfoObtainer;
121 
122 public:
123  // It needs to be public so it can be called in ShPtr's destructor.
124  virtual ~FuncInfo() = default;
125 
126  ShPtr<Function> getFunc() const;
127 
132  virtual bool isNeverRead(ShPtr<Variable> var) const = 0;
133 
138  virtual bool mayBeRead(ShPtr<Variable> var) const = 0;
139 
147  virtual bool isAlwaysRead(ShPtr<Variable> var) const = 0;
148 
153  virtual bool isNeverModified(ShPtr<Variable> var) const = 0;
154 
159  virtual bool mayBeModified(ShPtr<Variable> var) const = 0;
160 
169  virtual bool isAlwaysModified(ShPtr<Variable> var) const = 0;
170 
179  virtual bool valueIsNeverChanged(ShPtr<Variable> var) const = 0;
180 
190  virtual bool isAlwaysModifiedBeforeRead(ShPtr<Variable> var) const = 0;
191 
192 protected:
193  explicit FuncInfo(ShPtr<Function> func);
194 
195 protected:
198 };
199 
217 class CallInfoObtainer: public SharableFromThis<CallInfoObtainer>,
219 public:
220  virtual ~CallInfoObtainer() = default;
221 
222  ShPtr<CG> getCG() const;
224 
225  virtual void init(ShPtr<CG> cg, ShPtr<ValueAnalysis> va);
226  virtual bool isInitialized() const;
227 
231  virtual std::string getId() const = 0;
232 
242  ShPtr<Function> caller) = 0;
243 
252 
253 protected:
255  using FuncVectorSet = std::vector<FuncSet>;
256 
292  public:
293  void debugPrint() const;
294 
295  public:
298 
301  };
302 
304  using FuncCFGMap = std::map<ShPtr<Function>, ShPtr<CFG>>;
305 
306 protected:
308 
310 
311 protected:
314 
317 
320 
323 
326 
327 private:
342  public:
343  // We use a vector of function sets because:
344  //
345  // 1. Tarjan's algorithm outputs SCCs in a topological order
346  // that we want to maintain. That is trivial to do if we
347  // add them to the vector in that order.
348  //
349  // 2. It also only creates each SCC once so we don't have to
350  // worry about duplicates.
351  //
352  // 3. Using sets of sets causes non-determinism because it is
353  // comparing sets of pointers against sets of pointers.
354  //
355  // 4. Each insertion of an function set (SCC) into the SCC set
356  // requires Log N comparisons each possibly taking O(N) time due
357  // to how operator < is defined on std::set (lexicographic
358  // compare).
360 
361  private:
363  using CalledFuncStack = std::stack<ShPtr<CG::CalledFuncs>>;
364 
368  struct CalledFuncInfo {
369  CalledFuncInfo(): onStack(false), index(-1), lowlink(0) {}
370 
371  bool onStack;
372  int index;
373  int lowlink;
374  };
375 
377  using CalledFuncInfoMap = std::map<ShPtr<CG::CalledFuncs>, CalledFuncInfo>;
378 
379  private:
381  void visit(ShPtr<CG::CalledFuncs> calledFunc,
382  CalledFuncInfo &calledFuncInfo);
384 
385  private:
388 
390  int index;
391 
394 
397 
400 
403  };
404 
410  scc(scc), represent(represent) {}
411 
414  };
415 
416 private:
419  const FuncSet &computedFuncs) const;
421  const FuncSet &computedFuncs, const FuncSet &remainingFuncs) const;
422 };
423 
424 } // namespace llvmir2hll
425 } // namespace retdec
426 
427 #endif
A representation of a call graph (CG).
Represents an order in which FuncInfos should be computed.
Definition: call_info_obtainer.h:291
FuncVectorSet sccs
SCCs in the call graph.
Definition: call_info_obtainer.h:300
FuncVector order
An order in which FuncInfos should be computed.
Definition: call_info_obtainer.h:297
void debugPrint() const
Emits the order to standard error.
Definition: call_info_obtainer.cpp:280
A computation of strongly connected components (SCCs) from a call graph.
Definition: call_info_obtainer.h:341
ShPtr< CG > cg
Call graph of the current module.
Definition: call_info_obtainer.h:387
CalledFuncStack stack
The 'stack' variable from the SCC algorithm.
Definition: call_info_obtainer.h:399
FuncVectorSet sccs
The set of computed SCCs.
Definition: call_info_obtainer.h:393
CalledFuncInfoMap calledFuncInfoMap
Information about every CalledFunc.
Definition: call_info_obtainer.h:402
FuncSet currentSCC
The currently computed SCC.
Definition: call_info_obtainer.h:396
std::map< ShPtr< CG::CalledFuncs >, CalledFuncInfo > CalledFuncInfoMap
Mapping of a CalledFunc into its information.
Definition: call_info_obtainer.h:377
FuncVectorSet findSCCs()
Finds and returns all strongly connected components (SCCs) in the given call graph.
Definition: call_info_obtainer.cpp:342
int index
The 'index' variable from the SCC algorithm.
Definition: call_info_obtainer.h:390
static FuncVectorSet computeSCCs(ShPtr< CG > cg)
Computes and returns all strongly connected components (SCCs) in the given call graph.
Definition: call_info_obtainer.cpp:327
std::stack< ShPtr< CG::CalledFuncs > > CalledFuncStack
Stack of CalledFuncs.
Definition: call_info_obtainer.h:363
void visit(ShPtr< CG::CalledFuncs > calledFunc, CalledFuncInfo &calledFuncInfo)
Visits the given node in the call graph.
Definition: call_info_obtainer.cpp:371
SCCComputer(ShPtr< CG > cg)
Constructs a computer.
Definition: call_info_obtainer.cpp:309
A base class of all obtainers of information about functions and function calls.
Definition: call_info_obtainer.h:218
ShPtr< Module > module
The current module.
Definition: call_info_obtainer.h:313
FuncVectorSet computeSCCs()
Computes all SCCs in the current call graph and returns them.
Definition: call_info_obtainer.cpp:271
FuncCFGMap funcCFGMap
Mapping of a function into its CFG.
Definition: call_info_obtainer.h:322
bool callsJustComputedFuncs(ShPtr< Function > func, const FuncSet &computedFuncs) const
Returns true if func calls just functions from computedFuncs, false otherwise.
Definition: call_info_obtainer.cpp:198
ShPtr< FuncInfoCompOrder > getFuncInfoCompOrder(ShPtr< CG > cg)
Computes an order in which FuncInfos should be computed.
Definition: call_info_obtainer.cpp:130
virtual ShPtr< FuncInfo > getFuncInfo(ShPtr< Function > func)=0
Computes and returns information about the given function.
CallInfoObtainer()
Constructs a new obtainer.
Definition: call_info_obtainer.cpp:59
SCCWithRepresent findNextSCC(const FuncVectorSet &sccs, const FuncSet &computedFuncs, const FuncSet &remainingFuncs) const
Finds a next SCC and its represent and returns them.
Definition: call_info_obtainer.cpp:223
virtual ShPtr< CallInfo > getCallInfo(ShPtr< CallExpr > call, ShPtr< Function > caller)=0
Computes and returns information about the given function call which occurs in caller.
ShPtr< ValueAnalysis > va
Analysis of values.
Definition: call_info_obtainer.h:319
ShPtr< CG > getCG() const
Returns the call graph with which the obtainer has been initialized.
Definition: call_info_obtainer.cpp:69
ShPtr< CFGBuilder > cfgBuilder
The used builder of CFGs.
Definition: call_info_obtainer.h:325
virtual std::string getId() const =0
Returns the ID of the obtainer.
virtual bool isInitialized() const
Returns true if the obtainer has been initialized, false otherwise.
Definition: call_info_obtainer.cpp:121
ShPtr< CG > cg
Call graph of the current module.
Definition: call_info_obtainer.h:316
ShPtr< CFG > getCFGForFunc(ShPtr< Function > func) const
Returns the CFG for func after the obtainer has been initialized.
Definition: call_info_obtainer.cpp:79
std::map< ShPtr< Function >, ShPtr< CFG > > FuncCFGMap
Mapping of a function into its CFG.
Definition: call_info_obtainer.h:304
std::vector< FuncSet > FuncVectorSet
Vector of sets of functions.
Definition: call_info_obtainer.h:255
virtual void init(ShPtr< CG > cg, ShPtr< ValueAnalysis > va)
Initializes the obtainer.
Definition: call_info_obtainer.cpp:101
Base class for all classes storing information about a function call.
Definition: call_info_obtainer.h:34
ShPtr< CallExpr > call
Function call for which this piece of information is computed.
Definition: call_info_obtainer.h:111
virtual bool mayBeModified(ShPtr< Variable > var) const =0
Returns true if the value of var may be changed in the call, false otherwise.
ShPtr< CallExpr > getCall() const
Returns the function call for which the piece of information has been computed.
Definition: call_info_obtainer.cpp:38
CallInfo(ShPtr< CallExpr > call)
Constructs a new piece of information about the given function call.
Definition: call_info_obtainer.cpp:31
virtual bool isAlwaysRead(ShPtr< Variable > var) const =0
Returns true if var is always read in the call, false otherwise.
virtual bool valueIsNeverChanged(ShPtr< Variable > var) const =0
Returns true if the value of var is never changed in the call, false otherwise.
virtual bool isNeverModified(ShPtr< Variable > var) const =0
Returns true if there is no assign into var in the call, false otherwise.
virtual bool isNeverRead(ShPtr< Variable > var) const =0
Returns true if var is never read in the call, false otherwise.
virtual bool isAlwaysModified(ShPtr< Variable > var) const =0
Returns true if the value of var is always changed in the call, false otherwise.
virtual bool isAlwaysModifiedBeforeRead(ShPtr< Variable > var) const =0
Returns true if the given variable is modified prior to being read in the call, false otherwise.
virtual bool mayBeRead(ShPtr< Variable > var) const =0
Returns true if var may be read in the call, false otherwise.
virtual ~CallInfo()=default
Base class for all classes storing information about a function.
Definition: call_info_obtainer.h:119
virtual bool valueIsNeverChanged(ShPtr< Variable > var) const =0
Returns true if the value of var is never changed in the call, false otherwise.
virtual bool mayBeRead(ShPtr< Variable > var) const =0
Returns true if var may be read in the function, false otherwise.
ShPtr< Function > func
Function for which this piece of information is computed.
Definition: call_info_obtainer.h:197
virtual bool isAlwaysModifiedBeforeRead(ShPtr< Variable > var) const =0
Returns true if the given variable is modified prior to being read in the function,...
ShPtr< Function > getFunc() const
Returns the function for which the piece of information has been computed.
Definition: call_info_obtainer.cpp:52
virtual bool isNeverRead(ShPtr< Variable > var) const =0
Returns true if var is never read in the function, false otherwise.
virtual bool isAlwaysRead(ShPtr< Variable > var) const =0
Returns true if var is always read in the function, false otherwise.
virtual ~FuncInfo()=default
virtual bool isAlwaysModified(ShPtr< Variable > var) const =0
Returns true if the value of var is always changed in the function, false otherwise.
virtual bool isNeverModified(ShPtr< Variable > var) const =0
Returns true if there is no assign into var in the function, false otherwise.
FuncInfo(ShPtr< Function > func)
Constructs a new piece of information about the given function.
Definition: call_info_obtainer.cpp:45
virtual bool mayBeModified(ShPtr< Variable > var) const =0
Returns true if the value of var may be changed in the function, false otherwise.
Enables shared_from_this() in the inheriting class.
Definition: smart_ptr.h:44
A mixin to make classes non-copyable.
Definition: non_copyable.h:27
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::vector< ShPtr< Function > > FuncVector
Vector of functions.
Definition: types.h:105
std::set< ShPtr< Function > > FuncSet
Set of functions.
Definition: types.h:78
Definition: archive_wrapper.h:19
A mixin to make classes non-copyable.
Declarations, aliases, macros, etc. for the use of smart pointers.
Information about a CalledFunc from the SCC algorithm.
Definition: call_info_obtainer.h:368
An SCC with a represent.
Definition: call_info_obtainer.h:408
FuncSet scc
Definition: call_info_obtainer.h:412
SCCWithRepresent(FuncSet scc, ShPtr< Function > represent)
Definition: call_info_obtainer.h:409
ShPtr< Function > represent
Definition: call_info_obtainer.h:413
Aliases for several useful types.