LLVM  13.0.0git
AssumeBundleQueries.cpp
Go to the documentation of this file.
1 //===- AssumeBundleQueries.cpp - tool to query assume bundles ---*- C++ -*-===//
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 #define DEBUG_TYPE "assume-queries"
10 
12 #include "llvm/ADT/Statistic.h"
15 #include "llvm/IR/Function.h"
16 #include "llvm/IR/InstIterator.h"
17 #include "llvm/IR/IntrinsicInst.h"
18 #include "llvm/IR/PatternMatch.h"
20 
21 using namespace llvm;
22 using namespace llvm::PatternMatch;
23 
24 STATISTIC(NumAssumeQueries, "Number of Queries into an assume assume bundles");
25 STATISTIC(
26  NumUsefullAssumeQueries,
27  "Number of Queries into an assume assume bundles that were satisfied");
28 
29 DEBUG_COUNTER(AssumeQueryCounter, "assume-queries-counter",
30  "Controls which assumes gets created");
31 
32 static bool bundleHasArgument(const CallBase::BundleOpInfo &BOI, unsigned Idx) {
33  return BOI.End - BOI.Begin > Idx;
34 }
35 
37  const CallBase::BundleOpInfo &BOI,
38  unsigned Idx) {
39  assert(bundleHasArgument(BOI, Idx) && "index out of range");
40  return (Assume.op_begin() + BOI.Begin + Idx)->get();
41 }
42 
44  StringRef AttrName, uint64_t *ArgVal) {
46  "this attribute doesn't exist");
47  assert((ArgVal == nullptr || Attribute::doesAttrKindHaveArgument(
48  Attribute::getAttrKindFromName(AttrName))) &&
49  "requested value for an attribute that has no argument");
50  if (Assume.bundle_op_infos().empty())
51  return false;
52 
53  for (auto &BOI : Assume.bundle_op_infos()) {
54  if (BOI.Tag->getKey() != AttrName)
55  continue;
56  if (IsOn && (BOI.End - BOI.Begin <= ABA_WasOn ||
57  IsOn != getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn)))
58  continue;
59  if (ArgVal) {
60  assert(BOI.End - BOI.Begin > ABA_Argument);
61  *ArgVal =
62  cast<ConstantInt>(getValueFromBundleOpInfo(Assume, BOI, ABA_Argument))
63  ->getZExtValue();
64  }
65  return true;
66  }
67  return false;
68 }
69 
71  for (auto &Bundles : Assume.bundle_op_infos()) {
72  std::pair<Value *, Attribute::AttrKind> Key{
73  nullptr, Attribute::getAttrKindFromName(Bundles.Tag->getKey())};
74  if (bundleHasArgument(Bundles, ABA_WasOn))
75  Key.first = getValueFromBundleOpInfo(Assume, Bundles, ABA_WasOn);
76 
77  if (Key.first == nullptr && Key.second == Attribute::None)
78  continue;
79  if (!bundleHasArgument(Bundles, ABA_Argument)) {
80  Result[Key][&Assume] = {0, 0};
81  continue;
82  }
83  auto *CI = dyn_cast<ConstantInt>(
84  getValueFromBundleOpInfo(Assume, Bundles, ABA_Argument));
85  if (!CI)
86  continue;
87  unsigned Val = CI->getZExtValue();
88  auto Lookup = Result.find(Key);
89  if (Lookup == Result.end() || !Lookup->second.count(&Assume)) {
90  Result[Key][&Assume] = {Val, Val};
91  continue;
92  }
93  Lookup->second[&Assume].Min = std::min(Val, Lookup->second[&Assume].Min);
94  Lookup->second[&Assume].Max = std::max(Val, Lookup->second[&Assume].Max);
95  }
96 }
97 
100  const CallBase::BundleOpInfo &BOI) {
101  RetainedKnowledge Result;
102  Result.AttrKind = Attribute::getAttrKindFromName(BOI.Tag->getKey());
103  if (bundleHasArgument(BOI, ABA_WasOn))
104  Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn);
105  auto GetArgOr1 = [&](unsigned Idx) -> unsigned {
106  if (auto *ConstInt = dyn_cast<ConstantInt>(
107  getValueFromBundleOpInfo(Assume, BOI, ABA_Argument + Idx)))
108  return ConstInt->getZExtValue();
109  return 1;
110  };
111  if (BOI.End - BOI.Begin > ABA_Argument)
112  Result.ArgValue = GetArgOr1(0);
113  if (Result.AttrKind == Attribute::Alignment)
114  if (BOI.End - BOI.Begin > ABA_Argument + 1)
115  Result.ArgValue = MinAlign(Result.ArgValue, GetArgOr1(1));
116  return Result;
117 }
118 
120  unsigned Idx) {
122  return getKnowledgeFromBundle(Assume, BOI);
123 }
124 
126  return none_of(Assume.bundle_op_infos(),
127  [](const CallBase::BundleOpInfo &BOI) {
128  return BOI.Tag->getKey() != IgnoreBundleTag;
129  });
130 }
131 
132 static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) {
133  auto *Intr = dyn_cast<IntrinsicInst>(U->getUser());
134  if (!match(U->getUser(),
135  m_Intrinsic<Intrinsic::assume>(m_Unless(m_Specific(U->get())))))
136  return nullptr;
137  return &Intr->getBundleOpInfoForOperand(U->getOperandNo());
138 }
139 
142  ArrayRef<Attribute::AttrKind> AttrKinds) {
144  if (!Bundle)
145  return RetainedKnowledge::none();
146  RetainedKnowledge RK =
147  getKnowledgeFromBundle(*cast<AssumeInst>(U->getUser()), *Bundle);
148  if (llvm::is_contained(AttrKinds, RK.AttrKind))
149  return RK;
150  return RetainedKnowledge::none();
151 }
152 
156  AssumptionCache *AC,
158  const CallBase::BundleOpInfo *)>
159  Filter) {
160  NumAssumeQueries++;
161  if (!DebugCounter::shouldExecute(AssumeQueryCounter))
162  return RetainedKnowledge::none();
163  if (AC) {
164  for (AssumptionCache::ResultElem &Elem : AC->assumptionsFor(V)) {
165  auto *II = cast_or_null<AssumeInst>(Elem.Assume);
166  if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
167  continue;
169  *II, II->bundle_op_info_begin()[Elem.Index])) {
170  if (V != RK.WasOn)
171  continue;
172  if (is_contained(AttrKinds, RK.AttrKind) &&
173  Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {
174  NumUsefullAssumeQueries++;
175  return RK;
176  }
177  }
178  }
179  return RetainedKnowledge::none();
180  }
181  for (const auto &U : V->uses()) {
183  if (!Bundle)
184  continue;
185  if (RetainedKnowledge RK =
186  getKnowledgeFromBundle(*cast<AssumeInst>(U.getUser()), *Bundle))
187  if (is_contained(AttrKinds, RK.AttrKind) &&
188  Filter(RK, cast<Instruction>(U.getUser()), Bundle)) {
189  NumUsefullAssumeQueries++;
190  return RK;
191  }
192  }
193  return RetainedKnowledge::none();
194 }
195 
197  const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
198  const Instruction *CtxI, const DominatorTree *DT, AssumptionCache *AC) {
199  return getKnowledgeForValue(V, AttrKinds, AC,
200  [&](auto, Instruction *I, auto) {
201  return isValidAssumeForContext(I, CtxI, DT);
202  });
203 }
AssumptionCache.h
llvm
Definition: AllocatorList.h:23
llvm::none_of
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1496
llvm::ABA_Argument
@ ABA_Argument
Definition: AssumeBundleQueries.h:32
llvm::getKnowledgeFromUse
RetainedKnowledge getKnowledgeFromUse(const Use *U, ArrayRef< Attribute::AttrKind > AttrKinds)
Return a valid Knowledge associated to the Use U if its Attribute kind is in AttrKinds.
Definition: AssumeBundleQueries.cpp:141
IntrinsicInst.h
InstIterator.h
llvm::CallBase::BundleOpInfo::Tag
StringMapEntry< uint32_t > * Tag
The operand bundle tag, interned by LLVMContextImpl::getOrInsertBundleTag.
Definition: InstrTypes.h:2101
llvm::Attribute::getAttrKindFromName
static Attribute::AttrKind getAttrKindFromName(StringRef AttrName)
Definition: Attributes.cpp:216
Statistic.h
getValueFromBundleOpInfo
static Value * getValueFromBundleOpInfo(AssumeInst &Assume, const CallBase::BundleOpInfo &BOI, unsigned Idx)
Definition: AssumeBundleQueries.cpp:36
ValueTracking.h
llvm::isAssumeWithEmptyBundle
bool isAssumeWithEmptyBundle(AssumeInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn't contain any valuable informat...
Definition: AssumeBundleQueries.cpp:125
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
llvm::AssumeInst
This represents the llvm.assume intrinsic.
Definition: IntrinsicInst.h:1272
llvm::CallBase::bundle_op_infos
iterator_range< bundle_op_iterator > bundle_op_infos()
Return the range [bundle_op_info_begin, bundle_op_info_end).
Definition: InstrTypes.h:2207
llvm::AssumptionCache::ExprResultIdx
@ ExprResultIdx
Definition: AssumptionCache.h:45
llvm::AssumptionCache::ResultElem
Definition: AssumptionCache.h:47
llvm::PatternMatch::m_Unless
match_unless< Ty > m_Unless(const Ty &M)
Match if the inner matcher does NOT match.
Definition: PatternMatch.h:174
llvm::MinAlign
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:672
llvm::isValidAssumeForContext
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
Definition: ValueTracking.cpp:520
llvm::PatternMatch::match
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
getBundleFromUse
static CallInst::BundleOpInfo * getBundleFromUse(const Use *U)
Definition: AssumeBundleQueries.cpp:132
llvm::ABA_WasOn
@ ABA_WasOn
Definition: AssumeBundleQueries.h:31
Intr
unsigned Intr
Definition: AMDGPUBaseInfo.cpp:1927
llvm::CallBase::getBundleOpInfoForOperand
BundleOpInfo & getBundleOpInfoForOperand(unsigned OpIdx)
Return the BundleOpInfo for the operand at index OpIdx.
Definition: Instructions.cpp:393
llvm::hasAttributeInAssume
bool hasAttributeInAssume(AssumeInst &Assume, Value *IsOn, StringRef AttrName, uint64_t *ArgVal=nullptr)
Query the operand bundle of an llvm.assume to find a single attribute of the specified kind applied o...
Definition: AssumeBundleQueries.cpp:43
AssumeBundleQueries.h
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:481
llvm::Value::uses
iterator_range< use_iterator > uses()
Definition: Value.h:389
llvm::Instruction
Definition: Instruction.h:45
llvm::CallBase::BundleOpInfo::Begin
uint32_t Begin
The index in the Use& vector where operands for this operand bundle starts.
Definition: InstrTypes.h:2105
llvm::DebugCounter::shouldExecute
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::CallBase::BundleOpInfo
Used to keep track of an operand bundle.
Definition: InstrTypes.h:2098
llvm::getKnowledgeFromBundle
RetainedKnowledge getKnowledgeFromBundle(AssumeInst &Assume, const CallBase::BundleOpInfo &BOI)
This extracts the Knowledge from an element of an operand bundle.
Definition: AssumeBundleQueries.cpp:99
PatternMatch.h
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
llvm::ClrHandlerType::Filter
@ Filter
llvm::RetainedKnowledge::AttrKind
Attribute::AttrKind AttrKind
Definition: AssumeBundleQueries.h:102
llvm::Attribute::None
@ None
No attributes have been set.
Definition: Attributes.h:73
llvm::RetainedKnowledge::none
static RetainedKnowledge none()
Definition: AssumeBundleQueries.h:120
llvm::DenseMap< RetainedKnowledgeKey, Assume2KnowledgeMap >
llvm::fillMapFromAssume
void fillMapFromAssume(AssumeInst &Assume, RetainedKnowledgeMap &Result)
Insert into the map all the informations contained in the operand bundles of the llvm....
Definition: AssumeBundleQueries.cpp:70
I
#define I(x, y, z)
Definition: MD5.cpp:59
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:1547
llvm::Attribute::doesAttrKindHaveArgument
static bool doesAttrKindHaveArgument(Attribute::AttrKind AttrKind)
Return true if and only if the attribute has an Argument.
Definition: Attributes.cpp:239
llvm::StringMapEntry::getKey
StringRef getKey() const
Definition: StringMapEntry.h:102
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::RetainedKnowledge
Represent one information held inside an operand bundle of an llvm.assume.
Definition: AssumeBundleQueries.h:101
llvm::CallBase::BundleOpInfo::End
uint32_t End
The index in the Use& vector where operands for this operand bundle ends.
Definition: InstrTypes.h:2109
llvm::Attribute::isExistingAttribute
static bool isExistingAttribute(StringRef Name)
Return true if the provided string matches the IR name of an attribute.
Definition: Attributes.cpp:248
Function.h
DebugCounter.h
Lookup
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
Definition: X86FloatingPoint.cpp:599
bundleHasArgument
static bool bundleHasArgument(const CallBase::BundleOpInfo &BOI, unsigned Idx)
Definition: AssumeBundleQueries.cpp:32
llvm::PatternMatch::m_Specific
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:802
llvm::User::op_begin
op_iterator op_begin()
Definition: User.h:234
llvm::getKnowledgeValidInContext
RetainedKnowledge getKnowledgeValidInContext(const Value *V, ArrayRef< Attribute::AttrKind > AttrKinds, const Instruction *CtxI, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr)
Return a valid Knowledge associated to the Value V if its Attribute kind is in AttrKinds and the know...
Definition: AssumeBundleQueries.cpp:196
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::PatternMatch
Definition: PatternMatch.h:47
DEBUG_COUNTER
DEBUG_COUNTER(AssumeQueryCounter, "assume-queries-counter", "Controls which assumes gets created")
llvm::getKnowledgeFromOperandInAssume
RetainedKnowledge getKnowledgeFromOperandInAssume(AssumeInst &Assume, unsigned Idx)
Retreive the information help by Assume on the operand at index Idx.
Definition: AssumeBundleQueries.cpp:119
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
llvm::getKnowledgeForValue
RetainedKnowledge getKnowledgeForValue(const Value *V, ArrayRef< Attribute::AttrKind > AttrKinds, AssumptionCache *AC=nullptr, function_ref< bool(RetainedKnowledge, Instruction *, const CallBase::BundleOpInfo *)> Filter=[](auto...) { return true;})
Return a valid Knowledge associated to the Value V if its Attribute kind is in AttrKinds and it match...
Definition: AssumeBundleQueries.cpp:154
llvm::AssumptionCache::assumptionsFor
MutableArrayRef< ResultElem > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
Definition: AssumptionCache.h:153