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