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/GlobalVariable.h" |
21 | #include "llvm/Support/Casting.h" |
22 | #include <cassert> |
23 | #include <deque> |
24 | #include <memory> |
25 | |
26 | namespace llvm { |
27 | |
28 | class CallBase; |
29 | class DataLayout; |
30 | class Function; |
31 | class TargetLibraryInfo; |
32 | |
33 | /// This class evaluates LLVM IR, producing the Constant representing each SSA |
34 | /// instruction. Changes to global variables are stored in a mapping that can |
35 | /// be iterated over after the evaluation is complete. Once an evaluation call |
36 | /// fails, the evaluation object should not be reused. |
37 | class Evaluator { |
38 | struct MutableAggregate; |
39 | |
40 | /// The evaluator represents values either as a Constant*, or as a |
41 | /// MutableAggregate, which allows changing individual aggregate elements |
42 | /// without creating a new interned Constant. |
43 | class MutableValue { |
44 | PointerUnion<Constant *, MutableAggregate *> Val; |
45 | void clear(); |
46 | bool makeMutable(); |
47 | |
48 | public: |
49 | MutableValue(Constant *C) { Val = C; } |
50 | MutableValue(const MutableValue &) = delete; |
51 | MutableValue(MutableValue &&Other) { |
52 | Val = Other.Val; |
53 | Other.Val = nullptr; |
54 | } |
55 | ~MutableValue() { clear(); } |
56 | |
57 | Type *getType() const { |
58 | if (auto *C = dyn_cast_if_present<Constant *>(Val)) |
59 | return C->getType(); |
60 | return cast<MutableAggregate *>(Val)->Ty; |
61 | } |
62 | |
63 | Constant *toConstant() const { |
64 | if (auto *C = dyn_cast_if_present<Constant *>(Val)) |
65 | return C; |
66 | return cast<MutableAggregate *>(Val)->toConstant(); |
67 | } |
68 | |
69 | Constant *read(Type *Ty, APInt Offset, const DataLayout &DL) const; |
70 | bool write(Constant *V, APInt Offset, const DataLayout &DL); |
71 | }; |
72 | |
73 | struct MutableAggregate { |
74 | Type *Ty; |
75 | SmallVector<MutableValue> Elements; |
76 | |
77 | MutableAggregate(Type *Ty) : Ty(Ty) {} |
78 | Constant *toConstant() const; |
79 | }; |
80 | |
81 | public: |
82 | Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI) |
83 | : DL(DL), TLI(TLI) { |
84 | ValueStack.emplace_back(); |
85 | } |
86 | |
87 | ~Evaluator() { |
88 | for (auto &Tmp : AllocaTmps) |
89 | // If there are still users of the alloca, the program is doing something |
90 | // silly, e.g. storing the address of the alloca somewhere and using it |
91 | // later. Since this is undefined, we'll just make it be null. |
92 | if (!Tmp->use_empty()) |
93 | Tmp->replaceAllUsesWith(V: Constant::getNullValue(Ty: Tmp->getType())); |
94 | } |
95 | |
96 | /// Evaluate a call to function F, returning true if successful, false if we |
97 | /// can't evaluate it. ActualArgs contains the formal arguments for the |
98 | /// function. |
99 | bool EvaluateFunction(Function *F, Constant *&RetVal, |
100 | const SmallVectorImpl<Constant*> &ActualArgs); |
101 | |
102 | DenseMap<GlobalVariable *, Constant *> getMutatedInitializers() const { |
103 | DenseMap<GlobalVariable *, Constant *> Result; |
104 | for (const auto &Pair : MutatedMemory) |
105 | Result[Pair.first] = Pair.second.toConstant(); |
106 | return Result; |
107 | } |
108 | |
109 | const SmallPtrSetImpl<GlobalVariable *> &getInvariants() const { |
110 | return Invariants; |
111 | } |
112 | |
113 | private: |
114 | bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB, |
115 | bool &StrippedPointerCastsForAliasAnalysis); |
116 | |
117 | Constant *getVal(Value *V) { |
118 | if (Constant *CV = dyn_cast<Constant>(Val: V)) return CV; |
119 | Constant *R = ValueStack.back().lookup(Val: V); |
120 | assert(R && "Reference to an uncomputed value!" ); |
121 | return R; |
122 | } |
123 | |
124 | void setVal(Value *V, Constant *C) { |
125 | ValueStack.back()[V] = C; |
126 | } |
127 | |
128 | /// Casts call result to a type of bitcast call expression |
129 | Constant *castCallResultIfNeeded(Type *ReturnType, Constant *RV); |
130 | |
131 | /// Given call site return callee and list of its formal arguments |
132 | Function *getCalleeWithFormalArgs(CallBase &CB, |
133 | SmallVectorImpl<Constant *> &Formals); |
134 | |
135 | /// Given call site and callee returns list of callee formal argument |
136 | /// values converting them when necessary |
137 | bool getFormalParams(CallBase &CB, Function *F, |
138 | SmallVectorImpl<Constant *> &Formals); |
139 | |
140 | Constant *ComputeLoadResult(Constant *P, Type *Ty); |
141 | Constant *ComputeLoadResult(GlobalVariable *GV, Type *Ty, |
142 | const APInt &Offset); |
143 | |
144 | /// As we compute SSA register values, we store their contents here. The back |
145 | /// of the deque contains the current function and the stack contains the |
146 | /// values in the calling frames. |
147 | std::deque<DenseMap<Value*, Constant*>> ValueStack; |
148 | |
149 | /// This is used to detect recursion. In pathological situations we could hit |
150 | /// exponential behavior, but at least there is nothing unbounded. |
151 | SmallVector<Function*, 4> CallStack; |
152 | |
153 | /// For each store we execute, we update this map. Loads check this to get |
154 | /// the most up-to-date value. If evaluation is successful, this state is |
155 | /// committed to the process. |
156 | DenseMap<GlobalVariable *, MutableValue> MutatedMemory; |
157 | |
158 | /// To 'execute' an alloca, we create a temporary global variable to represent |
159 | /// its body. This vector is needed so we can delete the temporary globals |
160 | /// when we are done. |
161 | SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps; |
162 | |
163 | /// These global variables have been marked invariant by the static |
164 | /// constructor. |
165 | SmallPtrSet<GlobalVariable*, 8> Invariants; |
166 | |
167 | /// These are constants we have checked and know to be simple enough to live |
168 | /// in a static initializer of a global. |
169 | SmallPtrSet<Constant*, 8> SimpleConstants; |
170 | |
171 | const DataLayout &DL; |
172 | const TargetLibraryInfo *TLI; |
173 | }; |
174 | |
175 | } // end namespace llvm |
176 | |
177 | #endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H |
178 | |