Line data    Source code

       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         216 :   Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
      42         216 :       : DL(DL), TLI(TLI) {
      43         216 :     ValueStack.emplace_back();
      44         216 :   }
      45             : 
      46         648 :   ~Evaluator() {
      47         250 :     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          34 :       if (!Tmp->use_empty())
      52          22 :         Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
      53         216 :   }
      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        2522 :   Constant *getVal(Value *V) {
      67             :     if (Constant *CV = dyn_cast<Constant>(V)) return CV;
      68         778 :     Constant *R = ValueStack.back().lookup(V);
      69             :     assert(R && "Reference to an uncomputed value!");
      70         778 :     return R;
      71             :   }
      72             : 
      73         744 :   void setVal(Value *V, Constant *C) {
      74         744 :     ValueStack.back()[V] = C;
      75         744 :   }
      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