1//===- AssumptionCache.cpp - Cache finding @llvm.assume calls -------------===// 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 7//===----------------------------------------------------------------------===// 9// This file contains a pass that keeps track of @llvm.assume intrinsics in 10// the functions of a module. 12//===----------------------------------------------------------------------===// 42cl::desc(
"Enable verification of assumption cache"),
46AssumptionCache::getOrInsertAffectedValues(
Value *V) {
47// Try using find_as first to avoid creating extra value handles just for the 48// purpose of doing the lookup. 49auto AVI = AffectedValues.
find_as(V);
50if (AVI != AffectedValues.
end())
53return AffectedValues[AffectedValueCallbackVH(V,
this)];
59// Note: This code must be kept in-sync with the code in 60// computeKnownBitsFromAssume in ValueTracking. 62auto InsertAffected = [&Affected](
Value *V) {
66auto AddAffectedVal = [&Affected](
Value *V,
unsignedIdx) {
67if (isa<Argument>(V) || isa<GlobalValue>(V) || isa<Instruction>(V)) {
76"separate_storage must have two args");
92 AddAffectedVal(
const_cast<Value *
>(
Ptr->stripInBoundsOffsets()),
101for (
auto &AV : Affected) {
102auto &AVV = getOrInsertAffectedValues(AV.Assume);
106 AVV.push_back({CI, AV.Index});
114for (
auto &AV : Affected) {
115auto AVI = AffectedValues.
find_as(AV.Assume);
116if (AVI == AffectedValues.
end())
119bool HasNonnull =
false;
125 HasNonnull |= !!Elem.
Assume;
126if (HasNonnull && Found)
129assert(Found &&
"already unregistered or incorrect cache state");
131 AffectedValues.
erase(AVI);
137void AssumptionCache::AffectedValueCallbackVH::deleted() {
138 AC->AffectedValues.erase(getValPtr());
139// 'this' now dangles! 142void AssumptionCache::transferAffectedValuesInCache(
Value *OV,
Value *NV) {
143auto &NAVV = getOrInsertAffectedValues(NV);
144auto AVI = AffectedValues.
find(OV);
145if (AVI == AffectedValues.
end())
148for (
auto &
A : AVI->second)
151 AffectedValues.
erase(OV);
154void AssumptionCache::AffectedValueCallbackVH::allUsesReplacedWith(
Value *NV) {
155if (!isa<Instruction>(NV) && !isa<Argument>(NV))
158// Any assumptions that affected this value now affect the new value. 160 AC->transferAffectedValuesInCache(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. 166void AssumptionCache::scanFunction() {
167assert(!Scanned &&
"Tried to scan the function twice!");
168assert(AssumeHandles.empty() &&
"Already have assumes when scanning!");
170// Go through all instructions in all blocks, add all calls to @llvm.assume 174if (isa<AssumeInst>(&
I))
177// Mark the scan as complete. 180// Update affected values. 181for (
auto &
A : AssumeHandles)
186// If we haven't scanned the function yet, just drop this assumption. It will 187// be found when we scan later. 195"Cannot register @llvm.assume call not in a basic block");
197"Cannot register @llvm.assume call not in this function");
199// We expect the number of assumptions to be small, so in an asserts build 200// check that we don't accumulate duplicates and that all assumptions point 201// to the same function. 203for (
auto &VH : AssumeHandles) {
208"Cached assumption not inside this function!");
209assert(
match(cast<CallInst>(VH), m_Intrinsic<Intrinsic::assume>()) &&
210"Cached something other than a call to @llvm.assume!");
212"Cache contains multiple copies of a call!");
231 OS <<
"Cached assumptions for function: " <<
F.getName() <<
"\n";
234 OS <<
" " << *cast<CallInst>(VH)->getArgOperand(0) <<
"\n";
239void AssumptionCacheTracker::FunctionCallbackVH::deleted() {
240autoI = ACT->AssumptionCaches.find_as(cast<Function>(getValPtr()));
241if (
I != ACT->AssumptionCaches.end())
242 ACT->AssumptionCaches.erase(
I);
243// 'this' now dangles! 247// We probe the function map twice to try and avoid creating a value handle 248// around the function in common cases. This makes insertion a bit slower, 249// but if we have to insert we're going to scan the whole function so that 252if (
I != AssumptionCaches.
end())
255auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
256auto *
TTI = TTIWP ? &TTIWP->getTTI(
F) :
nullptr;
258// Ok, build a new cache by scanning the function, insert it and the value 259// handle into our map, and return the newly populated cache. 260auto IP = AssumptionCaches.
insert(std::make_pair(
261 FunctionCallbackVH(&
F,
this), std::make_unique<AssumptionCache>(
F,
TTI)));
262assert(IP.second &&
"Scanning function already in the map?");
263return *IP.first->second;
268if (
I != AssumptionCaches.
end())
269returnI->second.get();
274// FIXME: In the long term the verifier should not be controllable with a 275// flag. We should either fix all passes to correctly update the assumption 276// cache and enable the verifier unconditionally or somehow arrange for the 277// assumption list to be updated automatically by passes. 282for (
constauto &
I : AssumptionCaches) {
283for (
auto &VH :
I.second->assumptions())
285 AssumptionSet.
insert(cast<CallInst>(VH));
289if (
match(&
II, m_Intrinsic<Intrinsic::assume>()) &&
290 !AssumptionSet.
count(cast<CallInst>(&
II)))
304"Assumption Cache Tracker",
false,
true)
static void findAffectedValues(CallBase *CI, TargetTransformInfo *TTI, SmallVectorImpl< AssumptionCache::ResultElem > &Affected)
static cl::opt< bool > VerifyAssumptionCache("verify-assumption-cache", cl::Hidden, cl::desc("Enable verification of assumption cache"), cl::init(false))
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This header defines various interfaces for pass management in LLVM.
uint64_t IntrinsicInst * II
FunctionAnalysisManager FAM
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This pass exposes codegen information to IR-level passes.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
This represents the llvm.assume intrinsic.
A function analysis which provides an AssumptionCache.
AssumptionCache run(Function &F, FunctionAnalysisManager &)
An immutable pass that tracks lazily created AssumptionCache objects.
~AssumptionCacheTracker() override
AssumptionCache * lookupAssumptionCache(Function &F)
Return the cached assumptions for a function if it has already been scanned.
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
AssumptionCache & getAssumptionCache(Function &F)
Get the cached assumptions for a function.
A cache of @llvm.assume calls within a function.
void registerAssumption(AssumeInst *CI)
Add an @llvm.assume intrinsic to this function's cache.
void updateAffectedValues(AssumeInst *CI)
Update the cache of values being affected by this assumption (i.e.
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
void unregisterAssumption(AssumeInst *CI)
Remove an @llvm.assume intrinsic from this function's cache if it has been added to the cache earlier...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM Basic Block Representation.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
OperandBundleUse getOperandBundleAt(unsigned Index) const
Return the operand bundle at a specific index.
unsigned getNumOperandBundles() const
Return the number of operand bundles associated with this User.
Value * getArgOperand(unsigned i) const
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
iterator find_as(const LookupKeyT &Val)
Alternate version of find() which allows a different, and possibly less expensive,...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
ImmutablePass class - This class is used to provide information that does not need to be run.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Analysis pass providing the TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
std::pair< const Value *, unsigned > getPredicatedAddrSpace(const Value *V) const
LLVM Value Representation.
const ParentTy * getParent() const
bool match(Val *V, const Pattern &P)
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
constexpr StringRef IgnoreBundleTag
Tag in operand bundle indicating that this bundle should be ignored.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
void initializeAssumptionCacheTrackerPass(PassRegistry &)
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
void findValuesAffectedByCondition(Value *Cond, bool IsAssume, function_ref< void(Value *)> InsertAffected)
Call InsertAffected on all Values whose known bits / value may be affected by the condition Cond.
A special type used by analysis passes to provide an address that identifies that particular analysis...
unsigned Index
contains either ExprResultIdx or the index of the operand bundle containing the knowledge.
A lightweight accessor for an operand bundle meant to be passed around by value.
StringRef getTagName() const
Return the tag of this operand bundle as a string.
