1 //===-- Evaluator.h - LLVM IR evaluator -------------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // Function evaluator for LLVM IR. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_TRANSFORMS_UTILS_EVALUATOR_H 15 #define LLVM_TRANSFORMS_UTILS_EVALUATOR_H 16 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/IR/BasicBlock.h" 21 #include "llvm/IR/Constant.h" 22 #include "llvm/IR/GlobalVariable.h" 23 24 #include <deque> 25 #include <memory> 26 27 namespace llvm { 28 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 public: 39 Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI) 40 : DL(DL), TLI(TLI) { 41 ValueStack.emplace_back(); 42 } 43 44 ~Evaluator() { 45 for (auto &Tmp : AllocaTmps) 46 // If there are still users of the alloca, the program is doing something 47 // silly, e.g. storing the address of the alloca somewhere and using it 48 // later. Since this is undefined, we'll just make it be null. 49 if (!Tmp->use_empty()) 50 Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType())); 51 } 52 53 /// Evaluate a call to function F, returning true if successful, false if we 54 /// can't evaluate it. ActualArgs contains the formal arguments for the 55 /// function. 56 bool EvaluateFunction(Function *F, Constant *&RetVal, 57 const SmallVectorImpl<Constant*> &ActualArgs); 58 59 /// Evaluate all instructions in block BB, returning true if successful, false 60 /// if we can't evaluate it. NewBB returns the next BB that control flows 61 /// into, or null upon return. 62 bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB); 63 64 Constant *getVal(Value *V) { 65 if (Constant *CV = dyn_cast<Constant>(V)) return CV; 66 Constant *R = ValueStack.back().lookup(V); 67 assert(R && "Reference to an uncomputed value!"); 68 return R; 69 } 70 71 void setVal(Value *V, Constant *C) { 72 ValueStack.back()[V] = C; 73 } 74 75 const DenseMap<Constant*, Constant*> &getMutatedMemory() const { 76 return MutatedMemory; 77 } 78 79 const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const { 80 return Invariants; 81 } 82 83 private: 84 Constant *ComputeLoadResult(Constant *P); 85 86 /// As we compute SSA register values, we store their contents here. The back 87 /// of the deque contains the current function and the stack contains the 88 /// values in the calling frames. 89 std::deque<DenseMap<Value*, Constant*>> ValueStack; 90 91 /// This is used to detect recursion. In pathological situations we could hit 92 /// exponential behavior, but at least there is nothing unbounded. 93 SmallVector<Function*, 4> CallStack; 94 95 /// For each store we execute, we update this map. Loads check this to get 96 /// the most up-to-date value. If evaluation is successful, this state is 97 /// committed to the process. 98 DenseMap<Constant*, Constant*> MutatedMemory; 99 100 /// To 'execute' an alloca, we create a temporary global variable to represent 101 /// its body. This vector is needed so we can delete the temporary globals 102 /// when we are done. 103 SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps; 104 105 /// These global variables have been marked invariant by the static 106 /// constructor. 107 SmallPtrSet<GlobalVariable*, 8> Invariants; 108 109 /// These are constants we have checked and know to be simple enough to live 110 /// in a static initializer of a global. 111 SmallPtrSet<Constant*, 8> SimpleConstants; 112 113 const DataLayout &DL; 114 const TargetLibraryInfo *TLI; 115 }; 116 117 } 118 119 #endif 120
