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: MutableValue(Constant * C)49 MutableValue(Constant *C) { Val = C; } 50 MutableValue(const MutableValue &) = delete; MutableValue(MutableValue && Other)51 MutableValue(MutableValue &&Other) { 52 Val = Other.Val; 53 Other.Val = nullptr; 54 } ~MutableValue()55 ~MutableValue() { clear(); } 56 getType()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 toConstant()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 MutableAggregateMutableAggregate77 MutableAggregate(Type *Ty) : Ty(Ty) {} 78 Constant *toConstant() const; 79 }; 80 81 public: Evaluator(const DataLayout & DL,const TargetLibraryInfo * TLI)82 Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI) 83 : DL(DL), TLI(TLI) { 84 ValueStack.emplace_back(); 85 } 86 ~Evaluator()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(Constant::getNullValue(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 getMutatedInitializers()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 getInvariants()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 getVal(Value * V)117 Constant *getVal(Value *V) { 118 if (Constant *CV = dyn_cast<Constant>(V)) return CV; 119 Constant *R = ValueStack.back().lookup(V); 120 assert(R && "Reference to an uncomputed value!"); 121 return R; 122 } 123 setVal(Value * V,Constant * C)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