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/GlobalVariable.h"
21 #include "llvm/IR/Instructions.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   /// Casts call result to a type of bitcast call expression
77   Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV);
78 
79   const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
80     return MutatedMemory;
81   }
82 
83   const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const {
84     return Invariants;
85   }
86 
87 private:
88   /// Given call site return callee and list of its formal arguments
89   Function *getCalleeWithFormalArgs(CallBase &CB,
90                                     SmallVectorImpl<Constant *> &Formals);
91 
92   /// Given call site and callee returns list of callee formal argument
93   /// values converting them when necessary
94   bool getFormalParams(CallBase &CB, Function *F,
95                        SmallVectorImpl<Constant *> &Formals);
96 
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
133