LLVM  14.0.0git
AssumptionCache.cpp
Go to the documentation of this file.
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 
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/InitializePasses.h"
28 #include "llvm/Pass.h"
29 #include "llvm/Support/Casting.h"
33 #include <algorithm>
34 #include <cassert>
35 #include <utility>
36 
37 using namespace llvm;
38 using namespace llvm::PatternMatch;
39 
40 static cl::opt<bool>
41  VerifyAssumptionCache("verify-assumption-cache", cl::Hidden,
42  cl::desc("Enable verification of assumption cache"),
43  cl::init(false));
44 
46 AssumptionCache::getOrInsertAffectedValues(Value *V) {
47  // Try using find_as first to avoid creating extra value handles just for the
48  // purpose of doing the lookup.
49  auto AVI = AffectedValues.find_as(V);
50  if (AVI != AffectedValues.end())
51  return AVI->second;
52 
53  auto AVIP = AffectedValues.insert(
54  {AffectedValueCallbackVH(V, this), SmallVector<ResultElem, 1>()});
55  return AVIP.first->second;
56 }
57 
58 static void
61  // Note: This code must be kept in-sync with the code in
62  // computeKnownBitsFromAssume in ValueTracking.
63 
64  auto AddAffected = [&Affected](Value *V, unsigned Idx =
66  if (isa<Argument>(V)) {
67  Affected.push_back({V, Idx});
68  } else if (auto *I = dyn_cast<Instruction>(V)) {
69  Affected.push_back({I, Idx});
70 
71  // Peek through unary operators to find the source of the condition.
72  Value *Op;
73  if (match(I, m_BitCast(m_Value(Op))) ||
75  if (isa<Instruction>(Op) || isa<Argument>(Op))
76  Affected.push_back({Op, Idx});
77  }
78  }
79  };
80 
81  for (unsigned Idx = 0; Idx != CI->getNumOperandBundles(); Idx++) {
82  if (CI->getOperandBundleAt(Idx).Inputs.size() > ABA_WasOn &&
83  CI->getOperandBundleAt(Idx).getTagName() != IgnoreBundleTag)
84  AddAffected(CI->getOperandBundleAt(Idx).Inputs[ABA_WasOn], Idx);
85  }
86 
87  Value *Cond = CI->getArgOperand(0), *A, *B;
88  AddAffected(Cond);
89 
90  CmpInst::Predicate Pred;
91  if (match(Cond, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
92  AddAffected(A);
93  AddAffected(B);
94 
95  if (Pred == ICmpInst::ICMP_EQ) {
96  // For equality comparisons, we handle the case of bit inversion.
97  auto AddAffectedFromEq = [&AddAffected](Value *V) {
98  Value *A;
99  if (match(V, m_Not(m_Value(A)))) {
100  AddAffected(A);
101  V = A;
102  }
103 
104  Value *B;
105  // (A & B) or (A | B) or (A ^ B).
106  if (match(V, m_BitwiseLogic(m_Value(A), m_Value(B)))) {
107  AddAffected(A);
108  AddAffected(B);
109  // (A << C) or (A >>_s C) or (A >>_u C) where C is some constant.
110  } else if (match(V, m_Shift(m_Value(A), m_ConstantInt()))) {
111  AddAffected(A);
112  }
113  };
114 
115  AddAffectedFromEq(A);
116  AddAffectedFromEq(B);
117  }
118 
119  Value *X;
120  // Handle (A + C1) u< C2, which is the canonical form of A > C3 && A < C4,
121  // and recognized by LVI at least.
122  if (Pred == ICmpInst::ICMP_ULT &&
123  match(A, m_Add(m_Value(X), m_ConstantInt())) &&
124  match(B, m_ConstantInt()))
125  AddAffected(X);
126  }
127 }
128 
131  findAffectedValues(CI, Affected);
132 
133  for (auto &AV : Affected) {
134  auto &AVV = getOrInsertAffectedValues(AV.Assume);
135  if (std::find_if(AVV.begin(), AVV.end(), [&](ResultElem &Elem) {
136  return Elem.Assume == CI && Elem.Index == AV.Index;
137  }) == AVV.end())
138  AVV.push_back({CI, AV.Index});
139  }
140 }
141 
144  findAffectedValues(CI, Affected);
145 
146  for (auto &AV : Affected) {
147  auto AVI = AffectedValues.find_as(AV.Assume);
148  if (AVI == AffectedValues.end())
149  continue;
150  bool Found = false;
151  bool HasNonnull = false;
152  for (ResultElem &Elem : AVI->second) {
153  if (Elem.Assume == CI) {
154  Found = true;
155  Elem.Assume = nullptr;
156  }
157  HasNonnull |= !!Elem.Assume;
158  if (HasNonnull && Found)
159  break;
160  }
161  assert(Found && "already unregistered or incorrect cache state");
162  if (!HasNonnull)
163  AffectedValues.erase(AVI);
164  }
165 
166  erase_value(AssumeHandles, CI);
167 }
168 
169 void AssumptionCache::AffectedValueCallbackVH::deleted() {
170  AC->AffectedValues.erase(getValPtr());
171  // 'this' now dangles!
172 }
173 
174 void AssumptionCache::transferAffectedValuesInCache(Value *OV, Value *NV) {
175  auto &NAVV = getOrInsertAffectedValues(NV);
176  auto AVI = AffectedValues.find(OV);
177  if (AVI == AffectedValues.end())
178  return;
179 
180  for (auto &A : AVI->second)
181  if (!llvm::is_contained(NAVV, A))
182  NAVV.push_back(A);
183  AffectedValues.erase(OV);
184 }
185 
186 void AssumptionCache::AffectedValueCallbackVH::allUsesReplacedWith(Value *NV) {
187  if (!isa<Instruction>(NV) && !isa<Argument>(NV))
188  return;
189 
190  // Any assumptions that affected this value now affect the new value.
191 
192  AC->transferAffectedValuesInCache(getValPtr(), NV);
193  // 'this' now might dangle! If the AffectedValues map was resized to add an
194  // entry for NV then this object might have been destroyed in favor of some
195  // copy in the grown map.
196 }
197 
198 void AssumptionCache::scanFunction() {
199  assert(!Scanned && "Tried to scan the function twice!");
200  assert(AssumeHandles.empty() && "Already have assumes when scanning!");
201 
202  // Go through all instructions in all blocks, add all calls to @llvm.assume
203  // to this cache.
204  for (BasicBlock &B : F)
205  for (Instruction &I : B)
206  if (isa<AssumeInst>(&I))
207  AssumeHandles.push_back({&I, ExprResultIdx});
208 
209  // Mark the scan as complete.
210  Scanned = true;
211 
212  // Update affected values.
213  for (auto &A : AssumeHandles)
214  updateAffectedValues(cast<AssumeInst>(A));
215 }
216 
218  // If we haven't scanned the function yet, just drop this assumption. It will
219  // be found when we scan later.
220  if (!Scanned)
221  return;
222 
223  AssumeHandles.push_back({CI, ExprResultIdx});
224 
225 #ifndef NDEBUG
226  assert(CI->getParent() &&
227  "Cannot register @llvm.assume call not in a basic block");
228  assert(&F == CI->getParent()->getParent() &&
229  "Cannot register @llvm.assume call not in this function");
230 
231  // We expect the number of assumptions to be small, so in an asserts build
232  // check that we don't accumulate duplicates and that all assumptions point
233  // to the same function.
234  SmallPtrSet<Value *, 16> AssumptionSet;
235  for (auto &VH : AssumeHandles) {
236  if (!VH)
237  continue;
238 
239  assert(&F == cast<Instruction>(VH)->getParent()->getParent() &&
240  "Cached assumption not inside this function!");
241  assert(match(cast<CallInst>(VH), m_Intrinsic<Intrinsic::assume>()) &&
242  "Cached something other than a call to @llvm.assume!");
243  assert(AssumptionSet.insert(VH).second &&
244  "Cache contains multiple copies of a call!");
245  }
246 #endif
247 
249 }
250 
251 AnalysisKey AssumptionAnalysis::Key;
252 
256 
257  OS << "Cached assumptions for function: " << F.getName() << "\n";
258  for (auto &VH : AC.assumptions())
259  if (VH)
260  OS << " " << *cast<CallInst>(VH)->getArgOperand(0) << "\n";
261 
262  return PreservedAnalyses::all();
263 }
264 
265 void AssumptionCacheTracker::FunctionCallbackVH::deleted() {
266  auto I = ACT->AssumptionCaches.find_as(cast<Function>(getValPtr()));
267  if (I != ACT->AssumptionCaches.end())
268  ACT->AssumptionCaches.erase(I);
269  // 'this' now dangles!
270 }
271 
273  // We probe the function map twice to try and avoid creating a value handle
274  // around the function in common cases. This makes insertion a bit slower,
275  // but if we have to insert we're going to scan the whole function so that
276  // shouldn't matter.
277  auto I = AssumptionCaches.find_as(&F);
278  if (I != AssumptionCaches.end())
279  return *I->second;
280 
281  // Ok, build a new cache by scanning the function, insert it and the value
282  // handle into our map, and return the newly populated cache.
283  auto IP = AssumptionCaches.insert(std::make_pair(
284  FunctionCallbackVH(&F, this), std::make_unique<AssumptionCache>(F)));
285  assert(IP.second && "Scanning function already in the map?");
286  return *IP.first->second;
287 }
288 
290  auto I = AssumptionCaches.find_as(&F);
291  if (I != AssumptionCaches.end())
292  return I->second.get();
293  return nullptr;
294 }
295 
297  // FIXME: In the long term the verifier should not be controllable with a
298  // flag. We should either fix all passes to correctly update the assumption
299  // cache and enable the verifier unconditionally or somehow arrange for the
300  // assumption list to be updated automatically by passes.
302  return;
303 
304  SmallPtrSet<const CallInst *, 4> AssumptionSet;
305  for (const auto &I : AssumptionCaches) {
306  for (auto &VH : I.second->assumptions())
307  if (VH)
308  AssumptionSet.insert(cast<CallInst>(VH));
309 
310  for (const BasicBlock &B : cast<Function>(*I.first))
311  for (const Instruction &II : B)
312  if (match(&II, m_Intrinsic<Intrinsic::assume>()) &&
313  !AssumptionSet.count(cast<CallInst>(&II)))
314  report_fatal_error("Assumption in scanned function not in cache");
315  }
316 }
317 
320 }
321 
323 
325 
326 INITIALIZE_PASS(AssumptionCacheTracker, "assumption-cache-tracker",
327  "Assumption Cache Tracker", false, true)
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
AssumptionCache.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::CmpInst::ICMP_EQ
@ ICMP_EQ
equal
Definition: InstrTypes.h:741
llvm::AssumptionCache::registerAssumption
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
Definition: AssumptionCache.cpp:217
llvm::CmpInst::Predicate
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:720
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
llvm::ImmutablePass
ImmutablePass class - This class is used to provide information that does not need to be run.
Definition: Pass.h:269
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:779
llvm::Function
Definition: Function.h:61
Pass.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::PatternMatch::m_Add
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:1008
ErrorHandling.h
llvm::IgnoreBundleTag
constexpr StringRef IgnoreBundleTag
Tag in operand bundle indicating that this bundle should be ignored.
Definition: AssumeBundleQueries.h:136
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
llvm::AssumeInst
This represents the llvm.assume intrinsic.
Definition: IntrinsicInst.h:1319
llvm::AssumptionPrinterPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: AssumptionCache.cpp:253
VerifyAssumptionCache
static cl::opt< bool > VerifyAssumptionCache("verify-assumption-cache", cl::Hidden, cl::desc("Enable verification of assumption cache"), cl::init(false))
llvm::AssumptionCacheTracker::ID
static char ID
Definition: AssumptionCache.h:249
llvm::SmallPtrSet< Value *, 16 >
llvm::ore::NV
DiagnosticInfoOptimizationBase::Argument NV
Definition: OptimizationRemarkEmitter.h:136
STLExtras.h
llvm::PatternMatch::m_Not
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
Definition: PatternMatch.h:2280
llvm::PatternMatch::m_BitCast
CastClass_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
Definition: PatternMatch.h:1603
llvm::AssumptionCache::ResultElem
Definition: AssumptionCache.h:47
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
Instruction.h
CommandLine.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
llvm::ABA_WasOn
@ ABA_WasOn
Definition: AssumeBundleQueries.h:31
Intrinsics.h
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
InstrTypes.h
INITIALIZE_PASS
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:37
AssumeBundleQueries.h
llvm::initializeAssumptionCacheTrackerPass
void initializeAssumptionCacheTrackerPass(PassRegistry &)
IP
Definition: NVPTXLowerArgs.cpp:166
llvm::AssumptionCacheTracker::lookupAssumptionCache
AssumptionCache * lookupAssumptionCache(Function &F)
Return the cached assumptions for a function if it has already been scanned.
Definition: AssumptionCache.cpp:289
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::PatternMatch::m_ConstantInt
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:145
llvm::Instruction
Definition: Instruction.h:45
llvm::AssumptionCacheTracker::AssumptionCacheTracker
AssumptionCacheTracker()
Definition: AssumptionCache.cpp:318
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:140
SmallPtrSet.h
PatternMatch.h
llvm::PatternMatch::m_Shift
BinOpPred_match< LHS, RHS, is_shift_op > m_Shift(const LHS &L, const RHS &R)
Matches shift operations.
Definition: PatternMatch.h:1306
llvm::erase_value
void erase_value(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:1740
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::AssumptionCache::ResultElem::Assume
WeakVH Assume
Definition: AssumptionCache.h:48
BasicBlock.h
llvm::cl::opt< bool >
llvm::DenseMapBase::find_as
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
Definition: DenseMap.h:175
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1616
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::PatternMatch::m_Value
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
llvm::AssumptionCacheTracker
An immutable pass that tracks lazily created AssumptionCache objects.
Definition: AssumptionCache.h:200
Cond
SmallVector< MachineOperand, 4 > Cond
Definition: BasicBlockSections.cpp:179
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::CmpInst::ICMP_ULT
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:745
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:776
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1578
llvm::PatternMatch::m_BitwiseLogic
BinOpPred_match< LHS, RHS, is_bitwiselogic_op > m_BitwiseLogic(const LHS &L, const RHS &R)
Matches bitwise logic operations.
Definition: PatternMatch.h:1328
llvm::AssumptionCache::ExprResultIdx
@ ExprResultIdx
Definition: AssumptionCache.h:45
llvm::AssumptionCacheTracker::getAssumptionCache
AssumptionCache & getAssumptionCache(Function &F)
Get the cached assumptions for a function.
Definition: AssumptionCache.cpp:272
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
Casting.h
Function.h
PassManager.h
llvm::PatternMatch::m_PtrToInt
CastClass_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
Definition: PatternMatch.h:1609
Instructions.h
SmallVector.h
llvm::PatternMatch::m_ICmp
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:1404
llvm::AssumptionCache::assumptions
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
Definition: AssumptionCache.h:146
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
llvm::PatternMatch
Definition: PatternMatch.h:47
llvm::AssumptionCache::unregisterAssumption
void unregisterAssumption(AssumeInst *CI)
Remove an @llvm.assume intrinsic from this function's cache if it has been added to the cache earlier...
Definition: AssumptionCache.cpp:142
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::AssumptionCacheTracker::verifyAnalysis
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
Definition: AssumptionCache.cpp:296
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1161
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
findAffectedValues
static void findAffectedValues(CallBase *CI, SmallVectorImpl< AssumptionCache::ResultElem > &Affected)
Definition: AssumptionCache.cpp:59
llvm::cl::desc
Definition: CommandLine.h:414
llvm::AssumptionCache::updateAffectedValues
void updateAffectedValues(AssumeInst *CI)
Update the cache of values being affected by this assumption (i.e.
Definition: AssumptionCache.cpp:129
raw_ostream.h
llvm::AssumptionCacheTracker::~AssumptionCacheTracker
~AssumptionCacheTracker() override
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:773