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