/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Analysis/AssumptionCache.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===- AssumptionCache.cpp - Cache finding @llvm.assume calls -------------===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // This file contains a pass that keeps track of @llvm.assume intrinsics in |
11 | | // the functions of a module. |
12 | | // |
13 | | //===----------------------------------------------------------------------===// |
14 | | |
15 | | #include "llvm/Analysis/AssumptionCache.h" |
16 | | #include "llvm/ADT/STLExtras.h" |
17 | | #include "llvm/ADT/SmallPtrSet.h" |
18 | | #include "llvm/ADT/SmallVector.h" |
19 | | #include "llvm/IR/BasicBlock.h" |
20 | | #include "llvm/IR/Function.h" |
21 | | #include "llvm/IR/InstrTypes.h" |
22 | | #include "llvm/IR/Instruction.h" |
23 | | #include "llvm/IR/Instructions.h" |
24 | | #include "llvm/IR/Intrinsics.h" |
25 | | #include "llvm/IR/PassManager.h" |
26 | | #include "llvm/IR/PatternMatch.h" |
27 | | #include "llvm/Pass.h" |
28 | | #include "llvm/Support/Casting.h" |
29 | | #include "llvm/Support/CommandLine.h" |
30 | | #include "llvm/Support/ErrorHandling.h" |
31 | | #include "llvm/Support/raw_ostream.h" |
32 | | #include <algorithm> |
33 | | #include <cassert> |
34 | | #include <utility> |
35 | | |
36 | | using namespace llvm; |
37 | | using namespace llvm::PatternMatch; |
38 | | |
39 | | static cl::opt<bool> |
40 | | VerifyAssumptionCache("verify-assumption-cache", cl::Hidden, |
41 | | cl::desc("Enable verification of assumption cache"), |
42 | | cl::init(false)); |
43 | | |
44 | | SmallVector<WeakTrackingVH, 1> & |
45 | 7.85k | AssumptionCache::getOrInsertAffectedValues(Value *V) { |
46 | 7.85k | // Try using find_as first to avoid creating extra value handles just for the |
47 | 7.85k | // purpose of doing the lookup. |
48 | 7.85k | auto AVI = AffectedValues.find_as(V); |
49 | 7.85k | if (AVI != AffectedValues.end()) |
50 | 3.97k | return AVI->second; |
51 | 3.87k | |
52 | 3.87k | auto AVIP = AffectedValues.insert( |
53 | 3.87k | {AffectedValueCallbackVH(V, this), SmallVector<WeakTrackingVH, 1>()}); |
54 | 3.87k | return AVIP.first->second; |
55 | 3.87k | } |
56 | | |
57 | 3.85k | void AssumptionCache::updateAffectedValues(CallInst *CI) { |
58 | 3.85k | // Note: This code must be kept in-sync with the code in |
59 | 3.85k | // computeKnownBitsFromAssume in ValueTracking. |
60 | 3.85k | |
61 | 3.85k | SmallVector<Value *, 16> Affected; |
62 | 11.5k | auto AddAffected = [&Affected](Value *V) { |
63 | 11.5k | if (isa<Argument>(V)11.5k ) { |
64 | 174 | Affected.push_back(V); |
65 | 11.5k | } else if (auto *11.4k I11.4k = dyn_cast<Instruction>(V)) { |
66 | 7.56k | Affected.push_back(I); |
67 | 7.56k | |
68 | 7.56k | // Peek through unary operators to find the source of the condition. |
69 | 7.56k | Value *Op; |
70 | 7.56k | if (match(I, m_BitCast(m_Value(Op))) || |
71 | 7.56k | match(I, m_PtrToInt(m_Value(Op))) || |
72 | 7.56k | match(I, m_Not(m_Value(Op)))7.47k ) { |
73 | 105 | if (isa<Instruction>(Op) || 105 isa<Argument>(Op)70 ) |
74 | 103 | Affected.push_back(Op); |
75 | 105 | } |
76 | 11.4k | } |
77 | 11.5k | }; |
78 | 3.85k | |
79 | 3.85k | Value *Cond = CI->getArgOperand(0), *A, *B; |
80 | 3.85k | AddAffected(Cond); |
81 | 3.85k | |
82 | 3.85k | CmpInst::Predicate Pred; |
83 | 3.85k | if (match(Cond, m_ICmp(Pred, m_Value(A), m_Value(B)))3.85k ) { |
84 | 3.72k | AddAffected(A); |
85 | 3.72k | AddAffected(B); |
86 | 3.72k | |
87 | 3.72k | if (Pred == ICmpInst::ICMP_EQ3.72k ) { |
88 | 476 | // For equality comparisons, we handle the case of bit inversion. |
89 | 952 | auto AddAffectedFromEq = [&AddAffected](Value *V) { |
90 | 952 | Value *A; |
91 | 952 | if (match(V, m_Not(m_Value(A)))952 ) { |
92 | 2 | AddAffected(A); |
93 | 2 | V = A; |
94 | 2 | } |
95 | 952 | |
96 | 952 | Value *B; |
97 | 952 | ConstantInt *C; |
98 | 952 | // (A & B) or (A | B) or (A ^ B). |
99 | 952 | if (match(V, m_BitwiseLogic(m_Value(A), m_Value(B)))952 ) { |
100 | 134 | AddAffected(A); |
101 | 134 | AddAffected(B); |
102 | 134 | // (A << C) or (A >>_s C) or (A >>_u C) where C is some constant. |
103 | 952 | } else if (818 match(V, m_Shift(m_Value(A), m_ConstantInt(C)))818 ) { |
104 | 3 | AddAffected(A); |
105 | 3 | } |
106 | 952 | }; |
107 | 476 | |
108 | 476 | AddAffectedFromEq(A); |
109 | 476 | AddAffectedFromEq(B); |
110 | 476 | } |
111 | 3.72k | } |
112 | 3.85k | |
113 | 7.84k | for (auto &AV : Affected) { |
114 | 7.84k | auto &AVV = getOrInsertAffectedValues(AV); |
115 | 7.84k | if (std::find(AVV.begin(), AVV.end(), CI) == AVV.end()) |
116 | 7.08k | AVV.push_back(CI); |
117 | 7.84k | } |
118 | 3.85k | } |
119 | | |
120 | 84 | void AssumptionCache::AffectedValueCallbackVH::deleted() { |
121 | 84 | auto AVI = AC->AffectedValues.find(getValPtr()); |
122 | 84 | if (AVI != AC->AffectedValues.end()) |
123 | 84 | AC->AffectedValues.erase(AVI); |
124 | 84 | // 'this' now dangles! |
125 | 84 | } |
126 | | |
127 | 15 | void AssumptionCache::copyAffectedValuesInCache(Value *OV, Value *NV) { |
128 | 15 | auto &NAVV = getOrInsertAffectedValues(NV); |
129 | 15 | auto AVI = AffectedValues.find(OV); |
130 | 15 | if (AVI == AffectedValues.end()) |
131 | 0 | return; |
132 | 15 | |
133 | 15 | for (auto &A : AVI->second) |
134 | 15 | if (15 std::find(NAVV.begin(), NAVV.end(), A) == NAVV.end()15 ) |
135 | 15 | NAVV.push_back(A); |
136 | 15 | } |
137 | | |
138 | 29 | void AssumptionCache::AffectedValueCallbackVH::allUsesReplacedWith(Value *NV) { |
139 | 29 | if (!isa<Instruction>(NV) && 29 !isa<Argument>(NV)14 ) |
140 | 14 | return; |
141 | 15 | |
142 | 15 | // Any assumptions that affected this value now affect the new value. |
143 | 15 | |
144 | 15 | AC->copyAffectedValuesInCache(getValPtr(), NV); |
145 | 15 | // 'this' now might dangle! If the AffectedValues map was resized to add an |
146 | 15 | // entry for NV then this object might have been destroyed in favor of some |
147 | 15 | // copy in the grown map. |
148 | 15 | } |
149 | | |
150 | 1.10M | void AssumptionCache::scanFunction() { |
151 | 1.10M | assert(!Scanned && "Tried to scan the function twice!"); |
152 | 1.10M | assert(AssumeHandles.empty() && "Already have assumes when scanning!"); |
153 | 1.10M | |
154 | 1.10M | // Go through all instructions in all blocks, add all calls to @llvm.assume |
155 | 1.10M | // to this cache. |
156 | 1.10M | for (BasicBlock &B : F) |
157 | 9.56M | for (Instruction &II : B) |
158 | 54.9M | if (54.9M match(&II, m_Intrinsic<Intrinsic::assume>())54.9M ) |
159 | 3.39k | AssumeHandles.push_back(&II); |
160 | 1.10M | |
161 | 1.10M | // Mark the scan as complete. |
162 | 1.10M | Scanned = true; |
163 | 1.10M | |
164 | 1.10M | // Update affected values. |
165 | 1.10M | for (auto &A : AssumeHandles) |
166 | 3.39k | updateAffectedValues(cast<CallInst>(A)); |
167 | 1.10M | } |
168 | | |
169 | 7.10k | void AssumptionCache::registerAssumption(CallInst *CI) { |
170 | 7.10k | assert(match(CI, m_Intrinsic<Intrinsic::assume>()) && |
171 | 7.10k | "Registered call does not call @llvm.assume"); |
172 | 7.10k | |
173 | 7.10k | // If we haven't scanned the function yet, just drop this assumption. It will |
174 | 7.10k | // be found when we scan later. |
175 | 7.10k | if (!Scanned) |
176 | 7.03k | return; |
177 | 77 | |
178 | 77 | AssumeHandles.push_back(CI); |
179 | 77 | |
180 | | #ifndef NDEBUG |
181 | | assert(CI->getParent() && |
182 | | "Cannot register @llvm.assume call not in a basic block"); |
183 | | assert(&F == CI->getParent()->getParent() && |
184 | | "Cannot register @llvm.assume call not in this function"); |
185 | | |
186 | | // We expect the number of assumptions to be small, so in an asserts build |
187 | | // check that we don't accumulate duplicates and that all assumptions point |
188 | | // to the same function. |
189 | | SmallPtrSet<Value *, 16> AssumptionSet; |
190 | | for (auto &VH : AssumeHandles) { |
191 | | if (!VH) |
192 | | continue; |
193 | | |
194 | | assert(&F == cast<Instruction>(VH)->getParent()->getParent() && |
195 | | "Cached assumption not inside this function!"); |
196 | | assert(match(cast<CallInst>(VH), m_Intrinsic<Intrinsic::assume>()) && |
197 | | "Cached something other than a call to @llvm.assume!"); |
198 | | assert(AssumptionSet.insert(VH).second && |
199 | | "Cache contains multiple copies of a call!"); |
200 | | } |
201 | | #endif |
202 | | |
203 | 7.10k | updateAffectedValues(CI); |
204 | 7.10k | } |
205 | | |
206 | | AnalysisKey AssumptionAnalysis::Key; |
207 | | |
208 | | PreservedAnalyses AssumptionPrinterPass::run(Function &F, |
209 | 1 | FunctionAnalysisManager &AM) { |
210 | 1 | AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F); |
211 | 1 | |
212 | 1 | OS << "Cached assumptions for function: " << F.getName() << "\n"; |
213 | 1 | for (auto &VH : AC.assumptions()) |
214 | 3 | if (3 VH3 ) |
215 | 3 | OS << " " << *cast<CallInst>(VH)->getArgOperand(0) << "\n"; |
216 | 1 | |
217 | 1 | return PreservedAnalyses::all(); |
218 | 1 | } |
219 | | |
220 | 383k | void AssumptionCacheTracker::FunctionCallbackVH::deleted() { |
221 | 383k | auto I = ACT->AssumptionCaches.find_as(cast<Function>(getValPtr())); |
222 | 383k | if (I != ACT->AssumptionCaches.end()) |
223 | 383k | ACT->AssumptionCaches.erase(I); |
224 | 383k | // 'this' now dangles! |
225 | 383k | } |
226 | | |
227 | 43.9M | AssumptionCache &AssumptionCacheTracker::getAssumptionCache(Function &F) { |
228 | 43.9M | // We probe the function map twice to try and avoid creating a value handle |
229 | 43.9M | // around the function in common cases. This makes insertion a bit slower, |
230 | 43.9M | // but if we have to insert we're going to scan the whole function so that |
231 | 43.9M | // shouldn't matter. |
232 | 43.9M | auto I = AssumptionCaches.find_as(&F); |
233 | 43.9M | if (I != AssumptionCaches.end()) |
234 | 41.8M | return *I->second; |
235 | 2.15M | |
236 | 2.15M | // Ok, build a new cache by scanning the function, insert it and the value |
237 | 2.15M | // handle into our map, and return the newly populated cache. |
238 | 2.15M | auto IP = AssumptionCaches.insert(std::make_pair( |
239 | 2.15M | FunctionCallbackVH(&F, this), llvm::make_unique<AssumptionCache>(F))); |
240 | 2.15M | assert(IP.second && "Scanning function already in the map?"); |
241 | 2.15M | return *IP.first->second; |
242 | 2.15M | } |
243 | | |
244 | 157k | void AssumptionCacheTracker::verifyAnalysis() const { |
245 | 157k | // FIXME: In the long term the verifier should not be controllable with a |
246 | 157k | // flag. We should either fix all passes to correctly update the assumption |
247 | 157k | // cache and enable the verifier unconditionally or somehow arrange for the |
248 | 157k | // assumption list to be updated automatically by passes. |
249 | 157k | if (!VerifyAssumptionCache) |
250 | 157k | return; |
251 | 1 | |
252 | 1 | SmallPtrSet<const CallInst *, 4> AssumptionSet; |
253 | 1 | for (const auto &I : AssumptionCaches) { |
254 | 1 | for (auto &VH : I.second->assumptions()) |
255 | 2 | if (2 VH2 ) |
256 | 2 | AssumptionSet.insert(cast<CallInst>(VH)); |
257 | 1 | |
258 | 1 | for (const BasicBlock &B : cast<Function>(*I.first)) |
259 | 6 | for (const Instruction &II : B) |
260 | 22 | if (22 match(&II, m_Intrinsic<Intrinsic::assume>()) && |
261 | 2 | !AssumptionSet.count(cast<CallInst>(&II))) |
262 | 0 | report_fatal_error("Assumption in scanned function not in cache"); |
263 | 1 | } |
264 | 157k | } |
265 | | |
266 | 78.2k | AssumptionCacheTracker::AssumptionCacheTracker() : ImmutablePass(ID) { |
267 | 78.2k | initializeAssumptionCacheTrackerPass(*PassRegistry::getPassRegistry()); |
268 | 78.2k | } |
269 | | |
270 | 78.1k | AssumptionCacheTracker::~AssumptionCacheTracker() = default; |
271 | | |
272 | | char AssumptionCacheTracker::ID = 0; |
273 | | |
274 | | INITIALIZE_PASS(AssumptionCacheTracker, "assumption-cache-tracker", |
275 | | "Assumption Cache Tracker", false, true) |