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 public: 40 Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI) 41 : DL(DL), TLI(TLI) { 42 ValueStack.emplace_back(); 43 } 44 45 ~Evaluator() { 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 const DenseMap<Constant *, Constant *> &getMutatedMemory() const { 61 return MutatedMemory; 62 } 63 64 const SmallPtrSetImpl<GlobalVariable *> &getInvariants() const { 65 return Invariants; 66 } 67 68 private: 69 bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB, 70 bool &StrippedPointerCastsForAliasAnalysis); 71 72 Constant *getVal(Value *V) { 73 if (Constant *CV = dyn_cast<Constant>(V)) return CV; 74 Constant *R = ValueStack.back().lookup(V); 75 assert(R && "Reference to an uncomputed value!"); 76 return R; 77 } 78 79 void setVal(Value *V, Constant *C) { 80 ValueStack.back()[V] = C; 81 } 82 83 /// Casts call result to a type of bitcast call expression 84 Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV); 85 86 /// Given call site return callee and list of its formal arguments 87 Function *getCalleeWithFormalArgs(CallBase &CB, 88 SmallVectorImpl<Constant *> &Formals); 89 90 /// Given call site and callee returns list of callee formal argument 91 /// values converting them when necessary 92 bool getFormalParams(CallBase &CB, Function *F, 93 SmallVectorImpl<Constant *> &Formals); 94 95 Constant *ComputeLoadResult(Constant *P, Type *Ty); 96 97 /// As we compute SSA register values, we store their contents here. The back 98 /// of the deque contains the current function and the stack contains the 99 /// values in the calling frames. 100 std::deque<DenseMap<Value*, Constant*>> ValueStack; 101 102 /// This is used to detect recursion. In pathological situations we could hit 103 /// exponential behavior, but at least there is nothing unbounded. 104 SmallVector<Function*, 4> CallStack; 105 106 /// For each store we execute, we update this map. Loads check this to get 107 /// the most up-to-date value. If evaluation is successful, this state is 108 /// committed to the process. 109 DenseMap<Constant*, Constant*> MutatedMemory; 110 111 /// To 'execute' an alloca, we create a temporary global variable to represent 112 /// its body. This vector is needed so we can delete the temporary globals 113 /// when we are done. 114 SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps; 115 116 /// These global variables have been marked invariant by the static 117 /// constructor. 118 SmallPtrSet<GlobalVariable*, 8> Invariants; 119 120 /// These are constants we have checked and know to be simple enough to live 121 /// in a static initializer of a global. 122 SmallPtrSet<Constant*, 8> SimpleConstants; 123 124 const DataLayout &DL; 125 const TargetLibraryInfo *TLI; 126 }; 127 128 } // end namespace llvm 129 130 #endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H 131