1//===- AssumptionCache.cpp - Cache finding @llvm.assume calls -------------===//
2//
3// 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
6//
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"
15#include "AnalysisOptions.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallPtrSet.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/StringExtras.h"
20#include "llvm/Analysis/AssumeBundleQueries.h"
21#include "llvm/Analysis/TargetTransformInfo.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/IR/BasicBlock.h"
24#include "llvm/IR/BundleAttributes.h"
25#include "llvm/IR/Function.h"
26#include "llvm/IR/InstrTypes.h"
27#include "llvm/IR/Instruction.h"
28#include "llvm/IR/Instructions.h"
29#include "llvm/IR/PassManager.h"
30#include "llvm/IR/PatternMatch.h"
31#include "llvm/InitializePasses.h"
32#include "llvm/Pass.h"
33#include "llvm/Support/Casting.h"
34#include "llvm/Support/ErrorHandling.h"
35#include "llvm/Support/raw_ostream.h"
36#include <cassert>
37
38using namespace llvm;
39using namespace llvm::PatternMatch;
40
41AssumptionCache::AssumptionCache(Function &F, TargetTransformInfo *TTI)
42 : Opts(getAnalysisOptions(F)), F(F), TTI(TTI) {}
43
44SmallVector<AssumptionCache::ResultElem, 1> &
45AssumptionCache::getOrInsertAffectedValues(Value *V) {
46 // Try using find_as first to avoid creating extra value handles just for the
47 // purpose of doing the lookup.
48 auto AVI = AffectedValues.find_as(Val: V);
49 if (AVI != AffectedValues.end())
50 return AVI->second;
51
52 return AffectedValues[AffectedValueCallbackVH(V, this)];
53}
54
55void AssumptionCache::findValuesAffectedByOperandBundle(
56 OperandBundleUse Bundle, function_ref<void(Value *)> InsertAffected) {
57 auto AddAffectedVal = [&](Value *V) {
58 if (isa<Argument, GlobalValue, Instruction>(Val: V))
59 InsertAffected(V);
60 };
61
62 auto Attr = getBundleAttrFromOBU(OBU: Bundle);
63 if (Attr == BundleAttr::SeparateStorage) {
64 assert(Bundle.Inputs.size() == 2 && "separate_storage must have two args");
65 AddAffectedVal(getUnderlyingObject(V: Bundle.Inputs[0]));
66 AddAffectedVal(getUnderlyingObject(V: Bundle.Inputs[1]));
67 } else if (Bundle.Inputs.size() > ABA_WasOn && Attr != BundleAttr::Ignore)
68 AddAffectedVal(Bundle.Inputs[ABA_WasOn]);
69}
70
71static void
72findAffectedValues(CallBase *CI, TargetTransformInfo *TTI,
73 SmallVectorImpl<AssumptionCache::ResultElem> &Affected) {
74 // Note: This code must be kept in-sync with the code in
75 // computeKnownBitsFromAssume in ValueTracking.
76
77 auto InsertAffected = [&Affected](Value *V) {
78 Affected.push_back(Elt: {.Assume: V, .Index: AssumptionCache::ExprResultIdx});
79 };
80
81 auto AddAffectedVal = [&Affected](Value *V, unsigned Idx) {
82 if (isa<Argument>(Val: V) || isa<GlobalValue>(Val: V) || isa<Instruction>(Val: V)) {
83 Affected.push_back(Elt: {.Assume: V, .Index: Idx});
84 }
85 };
86
87 for (unsigned Idx = 0; Idx != CI->getNumOperandBundles(); Idx++)
88 AssumptionCache::findValuesAffectedByOperandBundle(
89 Bundle: CI->getOperandBundleAt(Index: Idx),
90 InsertAffected: [&](Value *V) { Affected.push_back(Elt: {.Assume: V, .Index: Idx}); });
91
92 Value *Cond = CI->getArgOperand(i: 0);
93 findValuesAffectedByCondition(Cond, /*IsAssume=*/true, InsertAffected);
94
95 if (TTI) {
96 const Value *Ptr;
97 unsigned AS;
98 std::tie(args&: Ptr, args&: AS) = TTI->getPredicatedAddrSpace(V: Cond);
99 if (Ptr)
100 AddAffectedVal(const_cast<Value *>(Ptr->stripInBoundsOffsets()),
101 AssumptionCache::ExprResultIdx);
102 }
103}
104
105void AssumptionCache::updateAffectedValues(AssumeInst *CI) {
106 SmallVector<AssumptionCache::ResultElem, 16> Affected;
107 findAffectedValues(CI, TTI, Affected);
108
109 for (auto &AV : Affected) {
110 auto &AVV = getOrInsertAffectedValues(V: AV.Assume);
111
112 // Callers walk every entry cached for a value, including the ones left
113 // behind by erased assumptions, so cache no more of them than an analysis
114 // should walk.
115 if (AVV.size() >= Opts.max_assumes_per_value)
116 continue;
117
118 if (llvm::none_of(Range&: AVV, P: [&](ResultElem &Elem) {
119 return Elem.Assume == CI && Elem.Index == AV.Index;
120 }))
121 AVV.push_back(Elt: {.Assume: CI, .Index: AV.Index});
122 }
123}
124
125void AssumptionCache::removeAffectedValues(AssumeInst *CI) {
126 SmallVector<AssumptionCache::ResultElem, 16> Affected;
127 findAffectedValues(CI, TTI, Affected);
128
129 for (auto &AV : Affected) {
130 auto AVI = AffectedValues.find_as(Val: AV.Assume);
131 if (AVI == AffectedValues.end())
132 continue;
133 bool Found = false;
134 bool HasNonnull = false;
135 for (ResultElem &Elem : AVI->second) {
136 if (Elem.Assume == CI) {
137 Found = true;
138 Elem.Assume = nullptr;
139 }
140
141 // We need to iterate through this loop to determine the value of
142 // HasNonnull, to avoid prematurely calling AffectedValues.erase(AVI).
143 HasNonnull |= !!Elem.Assume;
144 if (HasNonnull && Found)
145 break;
146 }
147
148 if (!Found) {
149 // It may well be the case that we fail to find an affected value in the
150 // cache. In particular, if an assume call is updated via `Use::set()`, we
151 // won't be notified that the affected value has changed and the cache
152 // will silently go stale.
153 } else if (!HasNonnull)
154 AffectedValues.erase(I: AVI);
155 }
156}
157
158void AssumptionCache::unregisterAssumption(AssumeInst *CI) {
159 removeAffectedValues(CI);
160 llvm::erase(C&: AssumeHandles, V: CI);
161}
162
163void AssumptionCache::replaceAssumption(WeakVH &Handle, AssumeInst *New) {
164 removeAffectedValues(CI: cast<AssumeInst>(Val&: Handle));
165 Handle = New;
166 updateAffectedValues(CI: New);
167}
168
169void AssumptionCache::AffectedValueCallbackVH::deleted() {
170 AC->AffectedValues.erase(Val: getValPtr());
171 // 'this' now dangles!
172}
173
174void AssumptionCache::transferAffectedValuesInCache(Value *OV, Value *NV) {
175 auto &NAVV = getOrInsertAffectedValues(V: NV);
176 auto AVI = AffectedValues.find(Val: OV);
177 if (AVI == AffectedValues.end())
178 return;
179
180 for (auto &A : AVI->second) {
181 if (NAVV.size() >= Opts.max_assumes_per_value)
182 break;
183 if (!llvm::is_contained(Range&: NAVV, Element: A))
184 NAVV.push_back(Elt: A);
185 }
186 AffectedValues.erase(Val: OV);
187}
188
189void AssumptionCache::AffectedValueCallbackVH::allUsesReplacedWith(Value *NV) {
190 if (!isa<Instruction>(Val: NV) && !isa<Argument>(Val: NV))
191 return;
192
193 // Any assumptions that affected this value now affect the new value.
194
195 AC->transferAffectedValuesInCache(OV: getValPtr(), NV);
196 // 'this' now might dangle! If the AffectedValues map was resized to add an
197 // entry for NV then this object might have been destroyed in favor of some
198 // copy in the grown map.
199}
200
201void AssumptionCache::scanFunction() {
202 assert(!Scanned && "Tried to scan the function twice!");
203 assert(AssumeHandles.empty() && "Already have assumes when scanning!");
204
205 // Go through all instructions in all blocks, add all calls to @llvm.assume
206 // to this cache.
207 for (BasicBlock &B : F)
208 for (Instruction &I : B)
209 if (isa<AssumeInst>(Val: &I))
210 AssumeHandles.push_back(Elt: &I);
211
212 // Mark the scan as complete.
213 Scanned = true;
214
215 // Update affected values.
216 for (auto &A : AssumeHandles)
217 updateAffectedValues(CI: cast<AssumeInst>(Val&: A));
218}
219
220/// Check the assumptions cached for \p F, collecting them in \p Cached. Returns
221/// a description of the first invariant violated, or nullptr if there is none.
222static const char *
223findCacheViolation(const Function &F, ArrayRef<WeakVH> Assumptions,
224 SmallPtrSetImpl<const CallInst *> &Cached) {
225 for (const WeakVH &VH : Assumptions) {
226 if (!VH)
227 continue;
228
229 const auto *CI = cast<CallInst>(Val: VH);
230 if (CI->getFunction() != &F)
231 return "Cached assumption not inside this function";
232 if (!match(V: CI, P: m_Intrinsic<Intrinsic::assume>()))
233 return "Cached something other than a call to @llvm.assume";
234 if (!Cached.insert(Ptr: CI).second)
235 return "Cache contains multiple copies of a call";
236 }
237
238 return nullptr;
239}
240
241void AssumptionCache::registerAssumption(AssumeInst *CI) {
242 // If we haven't scanned the function yet, just drop this assumption. It will
243 // be found when we scan later.
244 if (!Scanned)
245 return;
246
247 AssumeHandles.push_back(Elt: CI);
248
249#ifndef NDEBUG
250 assert(CI->getParent() &&
251 "Cannot register @llvm.assume call not in a basic block");
252 assert(&F == CI->getParent()->getParent() &&
253 "Cannot register @llvm.assume call not in this function");
254
255 // We expect the number of assumptions to be small, so in an asserts build
256 // check that we don't accumulate duplicates and that all assumptions point
257 // to the same function. Scanning the whole cache on every registration is
258 // quadratic, so stop once it outgrows that expectation unless expensive
259 // checks are enabled. Larger caches are checked by
260 // AssumptionCacheTracker::verifyAnalysis() instead.
261#ifdef EXPENSIVE_CHECKS
262 constexpr unsigned MaxAssumesToVerify = std::numeric_limits<unsigned>::max();
263#else
264 constexpr unsigned MaxAssumesToVerify = 64;
265#endif
266 if (AssumeHandles.size() <= MaxAssumesToVerify) {
267 SmallPtrSet<const CallInst *, 16> Cached;
268 if (const char *Violation = findCacheViolation(F, AssumeHandles, Cached))
269 llvm_unreachable(Violation);
270 }
271#endif
272
273 updateAffectedValues(CI);
274}
275
276AssumptionCache AssumptionAnalysis::run(Function &F,
277 FunctionAnalysisManager &FAM) {
278 auto &TTI = FAM.getResult<TargetIRAnalysis>(IR&: F);
279 return AssumptionCache(F, &TTI);
280}
281
282AnalysisKey AssumptionAnalysis::Key;
283
284PreservedAnalyses AssumptionPrinterPass::run(Function &F,
285 FunctionAnalysisManager &AM) {
286 AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
287
288 OS << "Cached assumptions for function: " << F.getName() << "\n";
289 for (auto &VH : AC.assumptions()) {
290 if (!VH)
291 continue;
292
293 auto *Assume = cast<CallInst>(Val&: VH);
294 if (!Assume->hasOperandBundles()) {
295 OS << " " << *Assume->getArgOperand(i: 0) << "\n";
296 continue;
297 }
298
299 assert(match(Assume->getArgOperand(0), m_One()) &&
300 "assume must have trivial cond");
301 OS << " [ ";
302 ListSeparator LS;
303 for (const OperandBundleUse &BU : Assume->operand_bundles()) {
304 OS << LS << '"' << BU.getTagName() << "\"(";
305 interleaveComma(c: BU.Inputs, os&: OS,
306 each_fn: [&](const Use &Input) { Input->printAsOperand(O&: OS); });
307 OS << ')';
308 }
309 OS << " ]\n";
310 }
311
312 return PreservedAnalyses::all();
313}
314
315void AssumptionCacheTracker::FunctionCallbackVH::deleted() {
316 auto I = ACT->AssumptionCaches.find_as(Val: cast<Function>(Val: getValPtr()));
317 if (I != ACT->AssumptionCaches.end())
318 ACT->AssumptionCaches.erase(I);
319 // 'this' now dangles!
320}
321
322AssumptionCache &AssumptionCacheTracker::getAssumptionCache(Function &F) {
323 // We probe the function map twice to try and avoid creating a value handle
324 // around the function in common cases. This makes insertion a bit slower,
325 // but if we have to insert we're going to scan the whole function so that
326 // shouldn't matter.
327 auto I = AssumptionCaches.find_as(Val: &F);
328 if (I != AssumptionCaches.end())
329 return *I->second;
330
331 auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
332 auto *TTI = TTIWP ? &TTIWP->getTTI(F) : nullptr;
333
334 // Ok, build a new cache by scanning the function, insert it and the value
335 // handle into our map, and return the newly populated cache.
336 auto IP = AssumptionCaches.insert(KV: std::make_pair(
337 x: FunctionCallbackVH(&F, this), y: std::make_unique<AssumptionCache>(args&: F, args&: TTI)));
338 assert(IP.second && "Scanning function already in the map?");
339 return *IP.first->second;
340}
341
342void AssumptionCacheTracker::verifyAnalysis() const {
343 // FIXME: In the long term the verifier should not be controllable with a
344 // flag. We should either fix all passes to correctly update the assumption
345 // cache and enable the verifier unconditionally or somehow arrange for the
346 // assumption list to be updated automatically by passes.
347 for (const auto &I : AssumptionCaches) {
348 const Function &F = cast<Function>(Val&: *I.first);
349 if (!getAnalysisOptions(F).verify_assumption_cache)
350 continue;
351
352 SmallPtrSet<const CallInst *, 4> Cached;
353 if (const char *Violation =
354 findCacheViolation(F, Assumptions: I.second->assumptions(), Cached))
355 report_fatal_error(reason: Violation);
356
357 for (const BasicBlock &B : F)
358 for (const Instruction &II : B)
359 if (match(V: &II, P: m_Intrinsic<Intrinsic::assume>()) &&
360 !Cached.count(Ptr: cast<CallInst>(Val: &II)))
361 report_fatal_error(reason: "Assumption in scanned function not in cache");
362 }
363}
364
365AssumptionCacheTracker::AssumptionCacheTracker() : ImmutablePass(ID) {}
366
367AssumptionCacheTracker::~AssumptionCacheTracker() = default;
368
369char AssumptionCacheTracker::ID = 0;
370
371INITIALIZE_PASS(AssumptionCacheTracker, "assumption-cache-tracker",
372 "Assumption Cache Tracker", false, true)
373