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
177
178
179
180
181
182
183
|
//===- llvm/Analysis/AssumptionCache.h - Track @llvm.assume ---*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains a pass that keeps track of @llvm.assume intrinsics in
// the functions of a module (allowing assumptions within any function to be
// found cheaply by other parts of the optimizer).
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_ASSUMPTIONCACHE_H
#define LLVM_ANALYSIS_ASSUMPTIONCACHE_H
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include <memory>
namespace llvm {
// FIXME: Replace this brittle forward declaration with the include of the new
// PassManager.h when doing so doesn't break the PassManagerBuilder.
template <typename IRUnitT> class AnalysisManager;
class PreservedAnalyses;
/// \brief A cache of @llvm.assume calls within a function.
///
/// This cache provides fast lookup of assumptions within a function by caching
/// them and amortizing the cost of scanning for them across all queries. The
/// cache is also conservatively self-updating so that it will never return
/// incorrect results about a function even as the function is being mutated.
/// However, flushing the cache and rebuilding it (or explicitly updating it)
/// may allow it to discover new assumptions.
class AssumptionCache {
/// \brief The function for which this cache is handling assumptions.
///
/// We track this to lazily populate our assumptions.
Function &F;
/// \brief Vector of weak value handles to calls of the @llvm.assume
/// intrinsic.
SmallVector<WeakVH, 4> AssumeHandles;
/// \brief Flag tracking whether we have scanned the function yet.
///
/// We want to be as lazy about this as possible, and so we scan the function
/// at the last moment.
bool Scanned;
/// \brief Scan the function for assumptions and add them to the cache.
void scanFunction();
public:
/// \brief Construct an AssumptionCache from a function by scanning all of
/// its instructions.
AssumptionCache(Function &F) : F(F), Scanned(false) {}
/// \brief Add an @llvm.assume intrinsic to this function's cache.
///
/// The call passed in must be an instruction within this fuction and must
/// not already be in the cache.
void registerAssumption(CallInst *CI);
/// \brief Clear the cache of @llvm.assume intrinsics for a function.
///
/// It will be re-scanned the next time it is requested.
void clear() {
AssumeHandles.clear();
Scanned = false;
}
/// \brief Access the list of assumption handles currently tracked for this
/// fuction.
///
/// Note that these produce weak handles that may be null. The caller must
/// handle that case.
/// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
/// when we can write that to filter out the null values. Then caller code
/// will become simpler.
MutableArrayRef<WeakVH> assumptions() {
if (!Scanned)
scanFunction();
return AssumeHandles;
}
};
/// \brief A function analysis which provides an \c AssumptionCache.
///
/// This analysis is intended for use with the new pass manager and will vend
/// assumption caches for a given function.
class AssumptionAnalysis {
static char PassID;
public:
typedef AssumptionCache Result;
/// \brief Opaque, unique identifier for this analysis pass.
static void *ID() { return (void *)&PassID; }
/// \brief Provide a name for the analysis for debugging and logging.
static StringRef name() { return "AssumptionAnalysis"; }
AssumptionAnalysis() {}
AssumptionAnalysis(const AssumptionAnalysis &Arg) {}
AssumptionAnalysis(AssumptionAnalysis &&Arg) {}
AssumptionAnalysis &operator=(const AssumptionAnalysis &RHS) { return *this; }
AssumptionAnalysis &operator=(AssumptionAnalysis &&RHS) { return *this; }
AssumptionCache run(Function &F) { return AssumptionCache(F); }
};
/// \brief Printer pass for the \c AssumptionAnalysis results.
class AssumptionPrinterPass {
raw_ostream &OS;
public:
explicit AssumptionPrinterPass(raw_ostream &OS) : OS(OS) {}
PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
static StringRef name() { return "AssumptionPrinterPass"; }
};
/// \brief An immutable pass that tracks lazily created \c AssumptionCache
/// objects.
///
/// This is essentially a workaround for the legacy pass manager's weaknesses
/// which associates each assumption cache with Function and clears it if the
/// function is deleted. The nature of the AssumptionCache is that it is not
/// invalidated by any changes to the function body and so this is sufficient
/// to be conservatively correct.
class AssumptionCacheTracker : public ImmutablePass {
/// A callback value handle applied to function objects, which we use to
/// delete our cache of intrinsics for a function when it is deleted.
class FunctionCallbackVH : public CallbackVH {
AssumptionCacheTracker *ACT;
void deleted() override;
public:
typedef DenseMapInfo<Value *> DMI;
FunctionCallbackVH(Value *V, AssumptionCacheTracker *ACT = nullptr)
: CallbackVH(V), ACT(ACT) {}
};
friend FunctionCallbackVH;
typedef DenseMap<FunctionCallbackVH, std::unique_ptr<AssumptionCache>,
FunctionCallbackVH::DMI> FunctionCallsMap;
FunctionCallsMap AssumptionCaches;
public:
/// \brief Get the cached assumptions for a function.
///
/// If no assumptions are cached, this will scan the function. Otherwise, the
/// existing cache will be returned.
AssumptionCache &getAssumptionCache(Function &F);
AssumptionCacheTracker();
~AssumptionCacheTracker() override;
void releaseMemory() override { AssumptionCaches.shrink_and_clear(); }
void verifyAnalysis() const override;
bool doFinalization(Module &) override {
verifyAnalysis();
return false;
}
static char ID; // Pass identification, replacement for typeid
};
} // end namespace llvm
#endif
|
