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/Support/Casting.h"
22 #include <cassert>
23 #include <deque>
24 #include <memory>
25 
26 namespace llvm {
27 
28 class CallBase;
29 class DataLayout;
30 class Function;
31 class TargetLibraryInfo;
32 
33 /// This class evaluates LLVM IR, producing the Constant representing each SSA
34 /// instruction.  Changes to global variables are stored in a mapping that can
35 /// be iterated over after the evaluation is complete.  Once an evaluation call
36 /// fails, the evaluation object should not be reused.
37 class Evaluator {
38   struct MutableAggregate;
39 
40   /// The evaluator represents values either as a Constant*, or as a
41   /// MutableAggregate, which allows changing individual aggregate elements
42   /// without creating a new interned Constant.
43   class MutableValue {
44     PointerUnion<Constant *, MutableAggregate *> Val;
45     void clear();
46     bool makeMutable();
47 
48   public:
49     MutableValue(Constant *C) { Val = C; }
50     MutableValue(const MutableValue &) = delete;
51     MutableValue(MutableValue &&Other) {
52       Val = Other.Val;
53       Other.Val = nullptr;
54     }
55     ~MutableValue() { clear(); }
56 
57     Type *getType() const {
58       if (auto *C = Val.dyn_cast<Constant *>())
59         return C->getType();
60       return Val.get<MutableAggregate *>()->Ty;
61     }
62 
63     Constant *toConstant() const {
64       if (auto *C = Val.dyn_cast<Constant *>())
65         return C;
66       return Val.get<MutableAggregate *>()->toConstant();
67     }
68 
69     Constant *read(Type *Ty, APInt Offset, const DataLayout &DL) const;
70     bool write(Constant *V, APInt Offset, const DataLayout &DL);
71   };
72 
73   struct MutableAggregate {
74     Type *Ty;
75     SmallVector<MutableValue> Elements;
76 
77     MutableAggregate(Type *Ty) : Ty(Ty) {}
78     Constant *toConstant() const;
79   };
80 
81 public:
82   Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
83       : DL(DL), TLI(TLI) {
84     ValueStack.emplace_back();
85   }
86 
87   ~Evaluator() {
88     for (auto &Tmp : AllocaTmps)
89       // If there are still users of the alloca, the program is doing something
90       // silly, e.g. storing the address of the alloca somewhere and using it
91       // later.  Since this is undefined, we'll just make it be null.
92       if (!Tmp->use_empty())
93         Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
94   }
95 
96   /// Evaluate a call to function F, returning true if successful, false if we
97   /// can't evaluate it.  ActualArgs contains the formal arguments for the
98   /// function.
99   bool EvaluateFunction(Function *F, Constant *&RetVal,
100                         const SmallVectorImpl<Constant*> &ActualArgs);
101 
102   DenseMap<GlobalVariable *, Constant *> getMutatedInitializers() const {
103     DenseMap<GlobalVariable *, Constant *> Result;
104     for (auto &Pair : MutatedMemory)
105       Result[Pair.first] = Pair.second.toConstant();
106     return Result;
107   }
108 
109   const SmallPtrSetImpl<GlobalVariable *> &getInvariants() const {
110     return Invariants;
111   }
112 
113 private:
114   bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
115                      bool &StrippedPointerCastsForAliasAnalysis);
116 
117   Constant *getVal(Value *V) {
118     if (Constant *CV = dyn_cast<Constant>(V)) return CV;
119     Constant *R = ValueStack.back().lookup(V);
120     assert(R && "Reference to an uncomputed value!");
121     return R;
122   }
123 
124   void setVal(Value *V, Constant *C) {
125     ValueStack.back()[V] = C;
126   }
127 
128   /// Casts call result to a type of bitcast call expression
129   Constant *castCallResultIfNeeded(Type *ReturnType, Constant *RV);
130 
131   /// Given call site return callee and list of its formal arguments
132   Function *getCalleeWithFormalArgs(CallBase &CB,
133                                     SmallVectorImpl<Constant *> &Formals);
134 
135   /// Given call site and callee returns list of callee formal argument
136   /// values converting them when necessary
137   bool getFormalParams(CallBase &CB, Function *F,
138                        SmallVectorImpl<Constant *> &Formals);
139 
140   Constant *ComputeLoadResult(Constant *P, Type *Ty);
141   Constant *ComputeLoadResult(GlobalVariable *GV, Type *Ty,
142                               const APInt &Offset);
143 
144   /// As we compute SSA register values, we store their contents here. The back
145   /// of the deque contains the current function and the stack contains the
146   /// values in the calling frames.
147   std::deque<DenseMap<Value*, Constant*>> ValueStack;
148 
149   /// This is used to detect recursion.  In pathological situations we could hit
150   /// exponential behavior, but at least there is nothing unbounded.
151   SmallVector<Function*, 4> CallStack;
152 
153   /// For each store we execute, we update this map.  Loads check this to get
154   /// the most up-to-date value.  If evaluation is successful, this state is
155   /// committed to the process.
156   DenseMap<GlobalVariable *, MutableValue> MutatedMemory;
157 
158   /// To 'execute' an alloca, we create a temporary global variable to represent
159   /// its body.  This vector is needed so we can delete the temporary globals
160   /// when we are done.
161   SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
162 
163   /// These global variables have been marked invariant by the static
164   /// constructor.
165   SmallPtrSet<GlobalVariable*, 8> Invariants;
166 
167   /// These are constants we have checked and know to be simple enough to live
168   /// in a static initializer of a global.
169   SmallPtrSet<Constant*, 8> SimpleConstants;
170 
171   const DataLayout &DL;
172   const TargetLibraryInfo *TLI;
173 };
174 
175 } // end namespace llvm
176 
177 #endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H
178