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:
Evaluator(const DataLayout & DL,const TargetLibraryInfo * TLI)41   Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
42       : DL(DL), TLI(TLI) {
43     ValueStack.emplace_back();
44   }
45 
~Evaluator()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 
getVal(Value * V)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 
setVal(Value * V,Constant * C)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 
getMutatedMemory()89   const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
90     return MutatedMemory;
91   }
92 
getInvariants()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
134