blob: cf2f845dee0a2d932a74e28e37aea05d35e38c25 [file] [log] [blame]
Daniel Jasperf5123fe2016-12-19 08:32:13 +00001//===- AssumptionCache.cpp - Cache finding @llvm.assume calls -------------===//
2//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// 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
Daniel Jasperf5123fe2016-12-19 08:32:13 +00006//
7//===----------------------------------------------------------------------===//
8//
9// This file contains a pass that keeps track of @llvm.assume intrinsics in
10// the functions of a module.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Analysis/AssumptionCache.h"
Eugene Zelenko75075ef2017-09-01 21:37:29 +000015#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallPtrSet.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/IR/BasicBlock.h"
Daniel Jasperf5123fe2016-12-19 08:32:13 +000019#include "llvm/IR/Function.h"
Eugene Zelenko75075ef2017-09-01 21:37:29 +000020#include "llvm/IR/InstrTypes.h"
21#include "llvm/IR/Instruction.h"
Daniel Jasperf5123fe2016-12-19 08:32:13 +000022#include "llvm/IR/Instructions.h"
Eugene Zelenko75075ef2017-09-01 21:37:29 +000023#include "llvm/IR/Intrinsics.h"
Daniel Jasperf5123fe2016-12-19 08:32:13 +000024#include "llvm/IR/PassManager.h"
25#include "llvm/IR/PatternMatch.h"
Eugene Zelenko75075ef2017-09-01 21:37:29 +000026#include "llvm/Pass.h"
27#include "llvm/Support/Casting.h"
28#include "llvm/Support/CommandLine.h"
29#include "llvm/Support/ErrorHandling.h"
30#include "llvm/Support/raw_ostream.h"
31#include <algorithm>
32#include <cassert>
33#include <utility>
34
Daniel Jasperf5123fe2016-12-19 08:32:13 +000035using namespace llvm;
36using namespace llvm::PatternMatch;
37
Peter Collingbourne9421c2d2017-02-15 21:10:09 +000038static cl::opt<bool>
39 VerifyAssumptionCache("verify-assumption-cache", cl::Hidden,
40 cl::desc("Enable verification of assumption cache"),
41 cl::init(false));
42
Sanjoy Dase6bca0e2017-05-01 17:07:49 +000043SmallVector<WeakTrackingVH, 1> &
44AssumptionCache::getOrInsertAffectedValues(Value *V) {
Hal Finkel8a9a7832017-01-11 13:24:24 +000045 // Try using find_as first to avoid creating extra value handles just for the
46 // purpose of doing the lookup.
47 auto AVI = AffectedValues.find_as(V);
48 if (AVI != AffectedValues.end())
49 return AVI->second;
50
Sanjoy Dase6bca0e2017-05-01 17:07:49 +000051 auto AVIP = AffectedValues.insert(
52 {AffectedValueCallbackVH(V, this), SmallVector<WeakTrackingVH, 1>()});
Hal Finkel8a9a7832017-01-11 13:24:24 +000053 return AVIP.first->second;
54}
55
Sergey Dmitriev807960e2019-02-08 06:55:18 +000056static void findAffectedValues(CallInst *CI,
57 SmallVectorImpl<Value *> &Affected) {
Hal Finkel8a9a7832017-01-11 13:24:24 +000058 // Note: This code must be kept in-sync with the code in
59 // computeKnownBitsFromAssume in ValueTracking.
60
Hal Finkel8a9a7832017-01-11 13:24:24 +000061 auto AddAffected = [&Affected](Value *V) {
62 if (isa<Argument>(V)) {
63 Affected.push_back(V);
64 } else if (auto *I = dyn_cast<Instruction>(V)) {
65 Affected.push_back(I);
66
Sanjay Patel96669962017-01-17 18:15:49 +000067 // Peek through unary operators to find the source of the condition.
68 Value *Op;
69 if (match(I, m_BitCast(m_Value(Op))) ||
70 match(I, m_PtrToInt(m_Value(Op))) ||
71 match(I, m_Not(m_Value(Op)))) {
Hal Finkel8a9a7832017-01-11 13:24:24 +000072 if (isa<Instruction>(Op) || isa<Argument>(Op))
73 Affected.push_back(Op);
74 }
75 }
76 };
77
78 Value *Cond = CI->getArgOperand(0), *A, *B;
79 AddAffected(Cond);
80
81 CmpInst::Predicate Pred;
82 if (match(Cond, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
83 AddAffected(A);
84 AddAffected(B);
85
86 if (Pred == ICmpInst::ICMP_EQ) {
87 // For equality comparisons, we handle the case of bit inversion.
88 auto AddAffectedFromEq = [&AddAffected](Value *V) {
89 Value *A;
90 if (match(V, m_Not(m_Value(A)))) {
91 AddAffected(A);
92 V = A;
93 }
94
95 Value *B;
96 ConstantInt *C;
97 // (A & B) or (A | B) or (A ^ B).
Craig Topper8bec6a42017-06-24 06:27:14 +000098 if (match(V, m_BitwiseLogic(m_Value(A), m_Value(B)))) {
Hal Finkel8a9a7832017-01-11 13:24:24 +000099 AddAffected(A);
100 AddAffected(B);
101 // (A << C) or (A >>_s C) or (A >>_u C) where C is some constant.
Craig Topper8bec6a42017-06-24 06:27:14 +0000102 } else if (match(V, m_Shift(m_Value(A), m_ConstantInt(C)))) {
Hal Finkel8a9a7832017-01-11 13:24:24 +0000103 AddAffected(A);
104 }
105 };
106
107 AddAffectedFromEq(A);
108 AddAffectedFromEq(B);
109 }
110 }
Sergey Dmitriev807960e2019-02-08 06:55:18 +0000111}
112
113void AssumptionCache::updateAffectedValues(CallInst *CI) {
114 SmallVector<Value *, 16> Affected;
115 findAffectedValues(CI, Affected);
Hal Finkel8a9a7832017-01-11 13:24:24 +0000116
117 for (auto &AV : Affected) {
Hal Finkelc29d5f12017-01-16 15:22:01 +0000118 auto &AVV = getOrInsertAffectedValues(AV);
Hal Finkel8a9a7832017-01-11 13:24:24 +0000119 if (std::find(AVV.begin(), AVV.end(), CI) == AVV.end())
120 AVV.push_back(CI);
121 }
122}
123
Sergey Dmitriev807960e2019-02-08 06:55:18 +0000124void AssumptionCache::unregisterAssumption(CallInst *CI) {
125 SmallVector<Value *, 16> Affected;
126 findAffectedValues(CI, Affected);
127
128 for (auto &AV : Affected) {
129 auto AVI = AffectedValues.find_as(AV);
130 if (AVI != AffectedValues.end())
131 AffectedValues.erase(AVI);
132 }
133 remove_if(AssumeHandles, [CI](WeakTrackingVH &VH) { return CI == VH; });
134}
135
Hal Finkel8a9a7832017-01-11 13:24:24 +0000136void AssumptionCache::AffectedValueCallbackVH::deleted() {
137 auto AVI = AC->AffectedValues.find(getValPtr());
138 if (AVI != AC->AffectedValues.end())
139 AC->AffectedValues.erase(AVI);
140 // 'this' now dangles!
141}
142
Hal Finkelc29d5f12017-01-16 15:22:01 +0000143void AssumptionCache::copyAffectedValuesInCache(Value *OV, Value *NV) {
144 auto &NAVV = getOrInsertAffectedValues(NV);
145 auto AVI = AffectedValues.find(OV);
146 if (AVI == AffectedValues.end())
147 return;
148
149 for (auto &A : AVI->second)
150 if (std::find(NAVV.begin(), NAVV.end(), A) == NAVV.end())
151 NAVV.push_back(A);
152}
153
Hal Finkel8a9a7832017-01-11 13:24:24 +0000154void AssumptionCache::AffectedValueCallbackVH::allUsesReplacedWith(Value *NV) {
155 if (!isa<Instruction>(NV) && !isa<Argument>(NV))
156 return;
157
158 // Any assumptions that affected this value now affect the new value.
159
Hal Finkelc29d5f12017-01-16 15:22:01 +0000160 AC->copyAffectedValuesInCache(getValPtr(), NV);
161 // 'this' now might dangle! If the AffectedValues map was resized to add an
162 // entry for NV then this object might have been destroyed in favor of some
163 // copy in the grown map.
Hal Finkel8a9a7832017-01-11 13:24:24 +0000164}
165
Daniel Jasperf5123fe2016-12-19 08:32:13 +0000166void AssumptionCache::scanFunction() {
167 assert(!Scanned && "Tried to scan the function twice!");
168 assert(AssumeHandles.empty() && "Already have assumes when scanning!");
169
170 // Go through all instructions in all blocks, add all calls to @llvm.assume
171 // to this cache.
172 for (BasicBlock &B : F)
173 for (Instruction &II : B)
174 if (match(&II, m_Intrinsic<Intrinsic::assume>()))
175 AssumeHandles.push_back(&II);
176
177 // Mark the scan as complete.
178 Scanned = true;
Hal Finkel8a9a7832017-01-11 13:24:24 +0000179
180 // Update affected values.
181 for (auto &A : AssumeHandles)
182 updateAffectedValues(cast<CallInst>(A));
Daniel Jasperf5123fe2016-12-19 08:32:13 +0000183}
184
185void AssumptionCache::registerAssumption(CallInst *CI) {
186 assert(match(CI, m_Intrinsic<Intrinsic::assume>()) &&
187 "Registered call does not call @llvm.assume");
188
189 // If we haven't scanned the function yet, just drop this assumption. It will
190 // be found when we scan later.
191 if (!Scanned)
192 return;
193
194 AssumeHandles.push_back(CI);
195
196#ifndef NDEBUG
197 assert(CI->getParent() &&
198 "Cannot register @llvm.assume call not in a basic block");
199 assert(&F == CI->getParent()->getParent() &&
200 "Cannot register @llvm.assume call not in this function");
201
202 // We expect the number of assumptions to be small, so in an asserts build
203 // check that we don't accumulate duplicates and that all assumptions point
204 // to the same function.
205 SmallPtrSet<Value *, 16> AssumptionSet;
206 for (auto &VH : AssumeHandles) {
207 if (!VH)
208 continue;
209
210 assert(&F == cast<Instruction>(VH)->getParent()->getParent() &&
211 "Cached assumption not inside this function!");
212 assert(match(cast<CallInst>(VH), m_Intrinsic<Intrinsic::assume>()) &&
213 "Cached something other than a call to @llvm.assume!");
214 assert(AssumptionSet.insert(VH).second &&
215 "Cache contains multiple copies of a call!");
216 }
217#endif
Hal Finkel8a9a7832017-01-11 13:24:24 +0000218
219 updateAffectedValues(CI);
Daniel Jasperf5123fe2016-12-19 08:32:13 +0000220}
221
222AnalysisKey AssumptionAnalysis::Key;
223
224PreservedAnalyses AssumptionPrinterPass::run(Function &F,
225 FunctionAnalysisManager &AM) {
226 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
227
228 OS << "Cached assumptions for function: " << F.getName() << "\n";
229 for (auto &VH : AC.assumptions())
230 if (VH)
231 OS << " " << *cast<CallInst>(VH)->getArgOperand(0) << "\n";
232
233 return PreservedAnalyses::all();
234}
235
236void AssumptionCacheTracker::FunctionCallbackVH::deleted() {
237 auto I = ACT->AssumptionCaches.find_as(cast<Function>(getValPtr()));
238 if (I != ACT->AssumptionCaches.end())
239 ACT->AssumptionCaches.erase(I);
240 // 'this' now dangles!
241}
242
243AssumptionCache &AssumptionCacheTracker::getAssumptionCache(Function &F) {
244 // We probe the function map twice to try and avoid creating a value handle
245 // around the function in common cases. This makes insertion a bit slower,
246 // but if we have to insert we're going to scan the whole function so that
247 // shouldn't matter.
248 auto I = AssumptionCaches.find_as(&F);
249 if (I != AssumptionCaches.end())
250 return *I->second;
251
252 // Ok, build a new cache by scanning the function, insert it and the value
253 // handle into our map, and return the newly populated cache.
254 auto IP = AssumptionCaches.insert(std::make_pair(
255 FunctionCallbackVH(&F, this), llvm::make_unique<AssumptionCache>(F)));
256 assert(IP.second && "Scanning function already in the map?");
257 return *IP.first->second;
258}
259
Sergey Dmitriev807960e2019-02-08 06:55:18 +0000260AssumptionCache *AssumptionCacheTracker::lookupAssumptionCache(Function &F) {
261 auto I = AssumptionCaches.find_as(&F);
262 if (I != AssumptionCaches.end())
263 return I->second.get();
264 return nullptr;
265}
266
Daniel Jasperf5123fe2016-12-19 08:32:13 +0000267void AssumptionCacheTracker::verifyAnalysis() const {
Peter Collingbourne9421c2d2017-02-15 21:10:09 +0000268 // FIXME: In the long term the verifier should not be controllable with a
269 // flag. We should either fix all passes to correctly update the assumption
270 // cache and enable the verifier unconditionally or somehow arrange for the
271 // assumption list to be updated automatically by passes.
272 if (!VerifyAssumptionCache)
273 return;
274
Daniel Jasperf5123fe2016-12-19 08:32:13 +0000275 SmallPtrSet<const CallInst *, 4> AssumptionSet;
276 for (const auto &I : AssumptionCaches) {
277 for (auto &VH : I.second->assumptions())
278 if (VH)
279 AssumptionSet.insert(cast<CallInst>(VH));
280
281 for (const BasicBlock &B : cast<Function>(*I.first))
282 for (const Instruction &II : B)
Peter Collingbourne9421c2d2017-02-15 21:10:09 +0000283 if (match(&II, m_Intrinsic<Intrinsic::assume>()) &&
284 !AssumptionSet.count(cast<CallInst>(&II)))
285 report_fatal_error("Assumption in scanned function not in cache");
Daniel Jasperf5123fe2016-12-19 08:32:13 +0000286 }
Daniel Jasperf5123fe2016-12-19 08:32:13 +0000287}
288
289AssumptionCacheTracker::AssumptionCacheTracker() : ImmutablePass(ID) {
290 initializeAssumptionCacheTrackerPass(*PassRegistry::getPassRegistry());
291}
292
Eugene Zelenko75075ef2017-09-01 21:37:29 +0000293AssumptionCacheTracker::~AssumptionCacheTracker() = default;
294
295char AssumptionCacheTracker::ID = 0;
Daniel Jasperf5123fe2016-12-19 08:32:13 +0000296
297INITIALIZE_PASS(AssumptionCacheTracker, "assumption-cache-tracker",
298 "Assumption Cache Tracker", false, true)