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
| //===- 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/CallSite.h"
#include "llvm/IR/GlobalVariable.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 {
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);
/// Evaluate all instructions in block BB, returning true if successful, false
/// if we can't evaluate it. NewBB returns the next BB that control flows
/// into, or null upon return.
bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB);
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;
}
/// Given call site return callee and list of its formal arguments
Function *getCalleeWithFormalArgs(CallSite &CS,
SmallVector<Constant *, 8> &Formals);
/// Given call site and callee returns list of callee formal argument
/// values converting them when necessary
bool getFormalParams(CallSite &CS, Function *F,
SmallVector<Constant *, 8> &Formals);
/// Casts call result to a type of bitcast call expression
Constant *castCallResultIfNeeded(Value *CallExpr, Constant *RV);
const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
return MutatedMemory;
}
const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const {
return Invariants;
}
private:
Constant *ComputeLoadResult(Constant *P);
/// 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<Constant*, Constant*> 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
|