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