contrib/llvm/include/llvm/Transforms/Utils/Evaluator.h

   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/CallSite.h"
  22 #include "llvm/IR/GlobalVariable.h"
  23 #include "llvm/IR/Value.h"
  24 #include "llvm/Support/Casting.h"
  25 #include <cassert>
  26 #include <deque>
  27 #include <memory>
  28
  29 namespace llvm {
  30
  31 class DataLayout;
  32 class Function;
  33 class TargetLibraryInfo;
  34
  35 /// This class evaluates LLVM IR, producing the Constant representing each SSA
  36 /// instruction.  Changes to global variables are stored in a mapping that can
  37 /// be iterated over after the evaluation is complete.  Once an evaluation call
  38 /// fails, the evaluation object should not be reused.
  39 class Evaluator {
  40 public:
  41   Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
  42       : DL(DL), TLI(TLI) {
  43     ValueStack.emplace_back();
  44   }
  45
  46   ~Evaluator() {
  47     for (auto &Tmp : AllocaTmps)
  48       // If there are still users of the alloca, the program is doing something
  49       // silly, e.g. storing the address of the alloca somewhere and using it
  50       // later.  Since this is undefined, we'll just make it be null.
  51       if (!Tmp->use_empty())
  52         Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
  53   }
  54
  55   /// Evaluate a call to function F, returning true if successful, false if we
  56   /// can't evaluate it.  ActualArgs contains the formal arguments for the
  57   /// function.
  58   bool EvaluateFunction(Function *F, Constant *&RetVal,
  59                         const SmallVectorImpl<Constant*> &ActualArgs);
  60
  61   /// Evaluate all instructions in block BB, returning true if successful, false
  62   /// if we can't evaluate it.  NewBB returns the next BB that control flows
  63   /// into, or null upon return.
  64   bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB);
  65
  66   Constant *getVal(Value *V) {
  67     if (Constant *CV = dyn_cast<Constant>(V)) return CV;
  68     Constant *R = ValueStack.back().lookup(V);
  69     assert(R && "Reference to an uncomputed value!");
  70     return R;
  71   }
  72
  73   void setVal(Value *V, Constant *C) {
  74     ValueStack.back()[V] = C;
  75   }
  76
  77   /// Given call site return callee and list of its formal arguments
  78   Function *getCalleeWithFormalArgs(CallSite &CS,
  79                                     SmallVector<Constant *, 8> &Formals);
  80
  81   /// Given call site and callee returns list of callee formal argument
  82   /// values converting them when necessary
  83   bool getFormalParams(CallSite &CS, Function *F,
  84                        SmallVector<Constant *, 8> &Formals);
  85
  86   /// Casts call result to a type of bitcast call expression
  87   Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV);
  88
  89   const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
  90     return MutatedMemory;
  91   }
  92
  93   const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const {
  94     return Invariants;
  95   }
  96
  97 private:
  98   Constant *ComputeLoadResult(Constant *P);
  99
 100   /// As we compute SSA register values, we store their contents here. The back
 101   /// of the deque contains the current function and the stack contains the
 102   /// values in the calling frames.
 103   std::deque<DenseMap<Value*, Constant*>> ValueStack;
 104
 105   /// This is used to detect recursion.  In pathological situations we could hit
 106   /// exponential behavior, but at least there is nothing unbounded.
 107   SmallVector<Function*, 4> CallStack;
 108
 109   /// For each store we execute, we update this map.  Loads check this to get
 110   /// the most up-to-date value.  If evaluation is successful, this state is
 111   /// committed to the process.
 112   DenseMap<Constant*, Constant*> MutatedMemory;
 113
 114   /// To 'execute' an alloca, we create a temporary global variable to represent
 115   /// its body.  This vector is needed so we can delete the temporary globals
 116   /// when we are done.
 117   SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
 118
 119   /// These global variables have been marked invariant by the static
 120   /// constructor.
 121   SmallPtrSet<GlobalVariable*, 8> Invariants;
 122
 123   /// These are constants we have checked and know to be simple enough to live
 124   /// in a static initializer of a global.
 125   SmallPtrSet<Constant*, 8> SimpleConstants;
 126
 127   const DataLayout &DL;
 128   const TargetLibraryInfo *TLI;
 129 };
 130
 131 } // end namespace llvm
 132
 133 #endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H