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