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
26namespace llvm {
27
28class CallBase;
29class DataLayout;
30class Function;
31class 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.
37class 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 = dyn_cast_if_present<Constant *>(Val))
59 return C->getType();
60 return cast<MutableAggregate *>(Val)->Ty;
61 }
62
63 Constant *toConstant() const {
64 if (auto *C = dyn_cast_if_present<Constant *>(Val))
65 return C;
66 return cast<MutableAggregate *>(Val)->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
81public:
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(V: Constant::getNullValue(Ty: 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 (const 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
113private:
114 bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB,
115 bool &StrippedPointerCastsForAliasAnalysis);
116
117 Constant *getVal(Value *V) {
118 if (Constant *CV = dyn_cast<Constant>(Val: V)) return CV;
119 Constant *R = ValueStack.back().lookup(Val: 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 /// Given call site return callee and list of its formal arguments
129 Function *getCalleeWithFormalArgs(CallBase &CB,
130 SmallVectorImpl<Constant *> &Formals);
131
132 /// Given call site and callee returns list of callee formal argument
133 /// values converting them when necessary
134 bool getFormalParams(CallBase &CB, Function *F,
135 SmallVectorImpl<Constant *> &Formals);
136
137 Constant *ComputeLoadResult(Constant *P, Type *Ty);
138 Constant *ComputeLoadResult(GlobalVariable *GV, Type *Ty,
139 const APInt &Offset);
140
141 /// As we compute SSA register values, we store their contents here. The back
142 /// of the deque contains the current function and the stack contains the
143 /// values in the calling frames.
144 std::deque<DenseMap<Value*, Constant*>> ValueStack;
145
146 /// This is used to detect recursion. In pathological situations we could hit
147 /// exponential behavior, but at least there is nothing unbounded.
148 SmallVector<Function*, 4> CallStack;
149
150 /// For each store we execute, we update this map. Loads check this to get
151 /// the most up-to-date value. If evaluation is successful, this state is
152 /// committed to the process.
153 DenseMap<GlobalVariable *, MutableValue> MutatedMemory;
154
155 /// To 'execute' an alloca, we create a temporary global variable to represent
156 /// its body. This vector is needed so we can delete the temporary globals
157 /// when we are done.
158 SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
159
160 /// These global variables have been marked invariant by the static
161 /// constructor.
162 SmallPtrSet<GlobalVariable*, 8> Invariants;
163
164 /// These are constants we have checked and know to be simple enough to live
165 /// in a static initializer of a global.
166 SmallPtrSet<Constant*, 8> SimpleConstants;
167
168 const DataLayout &DL;
169 const TargetLibraryInfo *TLI;
170};
171
172} // end namespace llvm
173
174#endif // LLVM_TRANSFORMS_UTILS_EVALUATOR_H
175