LLVM  10.0.0svn
Evaluator.h
Go to the documentation of this file.
1 //===- Evaluator.h - LLVM IR evaluator --------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Function evaluator for LLVM IR.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_TRANSFORMS_UTILS_EVALUATOR_H
14 #define LLVM_TRANSFORMS_UTILS_EVALUATOR_H
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/IR/BasicBlock.h"
20 #include "llvm/IR/CallSite.h"
21 #include "llvm/IR/GlobalVariable.h"
22 #include "llvm/IR/Value.h"
23 #include "llvm/Support/Casting.h"
24 #include <cassert>
25 #include <deque>
26 #include <memory>
27 
28 namespace llvm {
29 
30 class DataLayout;
31 class Function;
32 class TargetLibraryInfo;
33 
34 /// This class evaluates LLVM IR, producing the Constant representing each SSA
35 /// instruction. Changes to global variables are stored in a mapping that can
36 /// be iterated over after the evaluation is complete. Once an evaluation call
37 /// fails, the evaluation object should not be reused.
38 class Evaluator {
39 public:
40  Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
41  : DL(DL), TLI(TLI) {
42  ValueStack.emplace_back();
43  }
44 
46  for (auto &Tmp : AllocaTmps)
47  // If there are still users of the alloca, the program is doing something
48  // silly, e.g. storing the address of the alloca somewhere and using it
49  // later. Since this is undefined, we'll just make it be null.
50  if (!Tmp->use_empty())
51  Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
52  }
53 
54  /// Evaluate a call to function F, returning true if successful, false if we
55  /// can't evaluate it. ActualArgs contains the formal arguments for the
56  /// function.
57  bool EvaluateFunction(Function *F, Constant *&RetVal,
58  const SmallVectorImpl<Constant*> &ActualArgs);
59 
60  /// Evaluate all instructions in block BB, returning true if successful, false
61  /// if we can't evaluate it. NewBB returns the next BB that control flows
62  /// into, or null upon return.
63  bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB);
64 
66  if (Constant *CV = dyn_cast<Constant>(V)) return CV;
67  Constant *R = ValueStack.back().lookup(V);
68  assert(R && "Reference to an uncomputed value!");
69  return R;
70  }
71 
72  void setVal(Value *V, Constant *C) {
73  ValueStack.back()[V] = C;
74  }
75 
76  /// Given call site return callee and list of its formal arguments
79 
80  /// Given call site and callee returns list of callee formal argument
81  /// values converting them when necessary
82  bool getFormalParams(CallSite &CS, Function *F,
84 
85  /// Casts call result to a type of bitcast call expression
87 
89  return MutatedMemory;
90  }
91 
93  return Invariants;
94  }
95 
96 private:
97  Constant *ComputeLoadResult(Constant *P);
98 
99  /// As we compute SSA register values, we store their contents here. The back
100  /// of the deque contains the current function and the stack contains the
101  /// values in the calling frames.
102  std::deque<DenseMap<Value*, Constant*>> ValueStack;
103 
104  /// This is used to detect recursion. In pathological situations we could hit
105  /// exponential behavior, but at least there is nothing unbounded.
106  SmallVector<Function*, 4> CallStack;
107 
108  /// For each store we execute, we update this map. Loads check this to get
109  /// the most up-to-date value. If evaluation is successful, this state is
110  /// committed to the process.
111  DenseMap<Constant*, Constant*> MutatedMemory;
112 
113  /// To 'execute' an alloca, we create a temporary global variable to represent
114  /// its body. This vector is needed so we can delete the temporary globals
115  /// when we are done.
117 
118  /// These global variables have been marked invariant by the static
119  /// constructor.
121 
122  /// These are constants we have checked and know to be simple enough to live
123  /// in a static initializer of a global.
124  SmallPtrSet<Constant*, 8> SimpleConstants;
125 
126  const DataLayout &DL;
127  const TargetLibraryInfo *TLI;
128 };
129 
130 } // end namespace llvm
131 
132 #endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H
uint64_t CallInst * C
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB)
Evaluate all instructions in block BB, returning true if successful, false if we can&#39;t evaluate it...
Definition: Evaluator.cpp:328
bool getFormalParams(CallSite &CS, Function *F, SmallVector< Constant *, 8 > &Formals)
Given call site and callee returns list of callee formal argument values converting them when necessa...
Definition: Evaluator.cpp:284
F(f)
bool EvaluateFunction(Function *F, Constant *&RetVal, const SmallVectorImpl< Constant *> &ActualArgs)
Evaluate a call to function F, returning true if successful, false if we can&#39;t evaluate it...
Definition: Evaluator.cpp:672
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:289
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
#define P(N)
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
This is an important base class in LLVM.
Definition: Constant.h:41
void setVal(Value *V, Constant *C)
Definition: Evaluator.h:72
This class evaluates LLVM IR, producing the Constant representing each SSA instruction.
Definition: Evaluator.h:38
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
Constant * getVal(Value *V)
Definition: Evaluator.h:65
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Provides information about what library functions are available for the current target.
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:89
const SmallPtrSetImpl< GlobalVariable * > & getInvariants() const
Definition: Evaluator.h:92
Function * getCalleeWithFormalArgs(CallSite &CS, SmallVector< Constant *, 8 > &Formals)
Given call site return callee and list of its formal arguments.
Definition: Evaluator.cpp:269
Constant * castCallResultIfNeeded(Value *CallExpr, Constant *RV)
Casts call result to a type of bitcast call expression.
Definition: Evaluator.cpp:311
const DenseMap< Constant *, Constant * > & getMutatedMemory() const
Definition: Evaluator.h:88
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:74
Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
Definition: Evaluator.h:40