/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Transforms/Utils/Evaluator.h
Line | Count | Source |
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 | 1.10k | : DL(DL), TLI(TLI) { |
42 | 1.10k | ValueStack.emplace_back(); |
43 | 1.10k | } |
44 | | |
45 | 1.10k | ~Evaluator() { |
46 | 1.10k | for (auto &Tmp : AllocaTmps) |
47 | 1.72k | // If there are still users of the alloca, the program is doing something |
48 | 1.72k | // silly, e.g. storing the address of the alloca somewhere and using it |
49 | 1.72k | // later. Since this is undefined, we'll just make it be null. |
50 | 1.72k | if (!Tmp->use_empty()) |
51 | 694 | Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType())); |
52 | 1.10k | } |
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 | | |
65 | 32.3k | Constant *getVal(Value *V) { |
66 | 32.3k | if (Constant *CV = dyn_cast<Constant>(V)) return CV18.5k ; |
67 | 13.8k | Constant *R = ValueStack.back().lookup(V); |
68 | 13.8k | assert(R && "Reference to an uncomputed value!"); |
69 | 13.8k | return R; |
70 | 13.8k | } |
71 | | |
72 | 11.5k | void setVal(Value *V, Constant *C) { |
73 | 11.5k | ValueStack.back()[V] = C; |
74 | 11.5k | } |
75 | | |
76 | | /// Given call site return callee and list of its formal arguments |
77 | | Function *getCalleeWithFormalArgs(CallSite &CS, |
78 | | SmallVector<Constant *, 8> &Formals); |
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, |
83 | | SmallVector<Constant *, 8> &Formals); |
84 | | |
85 | | /// Casts call result to a type of bitcast call expression |
86 | | Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV); |
87 | | |
88 | 92 | const DenseMap<Constant*, Constant*> &getMutatedMemory() const { |
89 | 92 | return MutatedMemory; |
90 | 92 | } |
91 | | |
92 | 92 | const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const { |
93 | 92 | return Invariants; |
94 | 92 | } |
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. |
116 | | SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps; |
117 | | |
118 | | /// These global variables have been marked invariant by the static |
119 | | /// constructor. |
120 | | SmallPtrSet<GlobalVariable*, 8> Invariants; |
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 |