include/llvm/Transforms/Utils/Evaluator.h

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