LLVM  12.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) {
45  assert(isa<IntrinsicInst>(AssumeCI) &&
46  "this function is intended to be used on llvm.assume");
47  IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI);
48  assert(Assume.getIntrinsicID() == Intrinsic::assume &&
49  "this function is intended to be used on llvm.assume");
51  "this attribute doesn't exist");
52  assert((ArgVal == nullptr || Attribute::doesAttrKindHaveArgument(
53  Attribute::getAttrKindFromName(AttrName))) &&
54  "requested value for an attribute that has no argument");
55  if (Assume.bundle_op_infos().empty())
56  return false;
57 
58  for (auto &BOI : Assume.bundle_op_infos()) {
59  if (BOI.Tag->getKey() != AttrName)
60  continue;
61  if (IsOn && (BOI.End - BOI.Begin <= ABA_WasOn ||
62  IsOn != getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn)))
63  continue;
64  if (ArgVal) {
65  assert(BOI.End - BOI.Begin > ABA_Argument);
66  *ArgVal =
67  cast<ConstantInt>(getValueFromBundleOpInfo(Assume, BOI, ABA_Argument))
68  ->getZExtValue();
69  }
70  return true;
71  }
72  return false;
73 }
74 
76  IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI);
77  assert(Assume.getIntrinsicID() == Intrinsic::assume &&
78  "this function is intended to be used on llvm.assume");
79  for (auto &Bundles : Assume.bundle_op_infos()) {
80  std::pair<Value *, Attribute::AttrKind> Key{
81  nullptr, Attribute::getAttrKindFromName(Bundles.Tag->getKey())};
82  if (bundleHasArgument(Bundles, ABA_WasOn))
83  Key.first = getValueFromBundleOpInfo(Assume, Bundles, ABA_WasOn);
84 
85  if (Key.first == nullptr && Key.second == Attribute::None)
86  continue;
87  if (!bundleHasArgument(Bundles, ABA_Argument)) {
88  Result[Key][&Assume] = {0, 0};
89  continue;
90  }
91  unsigned Val = cast<ConstantInt>(
92  getValueFromBundleOpInfo(Assume, Bundles, ABA_Argument))
93  ->getZExtValue();
94  auto Lookup = Result.find(Key);
95  if (Lookup == Result.end() || !Lookup->second.count(&Assume)) {
96  Result[Key][&Assume] = {Val, Val};
97  continue;
98  }
99  Lookup->second[&Assume].Min = std::min(Val, Lookup->second[&Assume].Min);
100  Lookup->second[&Assume].Max = std::max(Val, Lookup->second[&Assume].Max);
101  }
102 }
103 
106  const CallBase::BundleOpInfo &BOI) {
107  RetainedKnowledge Result;
109  if (bundleHasArgument(BOI, ABA_WasOn))
110  Result.WasOn = getValueFromBundleOpInfo(Assume, BOI, ABA_WasOn);
111  auto GetArgOr1 = [&](unsigned Idx) -> unsigned {
112  if (auto *ConstInt = dyn_cast<ConstantInt>(
113  getValueFromBundleOpInfo(Assume, BOI, ABA_Argument + Idx)))
114  return ConstInt->getZExtValue();
115  return 1;
116  };
117  if (BOI.End - BOI.Begin > ABA_Argument)
118  Result.ArgValue = GetArgOr1(0);
119  if (Result.AttrKind == Attribute::Alignment)
120  if (BOI.End - BOI.Begin > ABA_Argument + 1)
121  Result.ArgValue = MinAlign(Result.ArgValue, GetArgOr1(1));
122  return Result;
123 }
124 
126  unsigned Idx) {
127  IntrinsicInst &Assume = cast<IntrinsicInst>(AssumeCI);
128  assert(Assume.getIntrinsicID() == Intrinsic::assume &&
129  "this function is intended to be used on llvm.assume");
131  return getKnowledgeFromBundle(AssumeCI, BOI);
132 }
133 
135  IntrinsicInst &Assume = cast<IntrinsicInst>(CI);
136  assert(Assume.getIntrinsicID() == Intrinsic::assume &&
137  "this function is intended to be used on llvm.assume");
138  return none_of(Assume.bundle_op_infos(),
139  [](const CallBase::BundleOpInfo &BOI) {
140  return BOI.Tag->getKey() != IgnoreBundleTag;
141  });
142 }
143 
144 static CallInst::BundleOpInfo *getBundleFromUse(const Use *U) {
145  auto *Intr = dyn_cast<IntrinsicInst>(U->getUser());
146  if (!match(U->getUser(),
147  m_Intrinsic<Intrinsic::assume>(m_Unless(m_Specific(U->get())))))
148  return nullptr;
149  return &Intr->getBundleOpInfoForOperand(U->getOperandNo());
150 }
151 
154  ArrayRef<Attribute::AttrKind> AttrKinds) {
156  if (!Bundle)
157  return RetainedKnowledge::none();
158  RetainedKnowledge RK =
159  getKnowledgeFromBundle(*cast<CallInst>(U->getUser()), *Bundle);
160  for (auto Attr : AttrKinds)
161  if (Attr == RK.AttrKind)
162  return RK;
163  return RetainedKnowledge::none();
164 }
165 
169  AssumptionCache *AC,
171  const CallBase::BundleOpInfo *)>
172  Filter) {
173  NumAssumeQueries++;
174  if (!DebugCounter::shouldExecute(AssumeQueryCounter))
175  return RetainedKnowledge::none();
176  if (AC) {
177  for (AssumptionCache::ResultElem &Elem : AC->assumptionsFor(V)) {
178  IntrinsicInst *II = cast_or_null<IntrinsicInst>(Elem.Assume);
179  if (!II || Elem.Index == AssumptionCache::ExprResultIdx)
180  continue;
182  *II, II->bundle_op_info_begin()[Elem.Index]))
183  if (is_contained(AttrKinds, RK.AttrKind) &&
184  Filter(RK, II, &II->bundle_op_info_begin()[Elem.Index])) {
185  NumUsefullAssumeQueries++;
186  return RK;
187  }
188  }
189  return RetainedKnowledge::none();
190  }
191  for (const auto &U : V->uses()) {
193  if (!Bundle)
194  continue;
195  if (RetainedKnowledge RK =
196  getKnowledgeFromBundle(*cast<CallInst>(U.getUser()), *Bundle))
197  if (is_contained(AttrKinds, RK.AttrKind) &&
198  Filter(RK, cast<Instruction>(U.getUser()), Bundle)) {
199  NumUsefullAssumeQueries++;
200  return RK;
201  }
202  }
203  return RetainedKnowledge::none();
204 }
205 
207  const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
208  const Instruction *CtxI, const DominatorTree *DT, AssumptionCache *AC) {
209  return getKnowledgeForValue(V, AttrKinds, AC,
210  [&](auto, Instruction *I, auto) {
211  return isValidAssumeForContext(I, CtxI, DT);
212  });
213 }
iterator_range< use_iterator > uses()
Definition: Value.h:373
LLVM_NODISCARD std::enable_if_t< !is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition: Casting.h:334
DEBUG_COUNTER(AssumeQueryCounter, "assume-queries-counter", "Controls which assumes gets created")
This class represents lattice values for constants.
Definition: AllocatorList.h:23
match_unless< Ty > m_Unless(const Ty &M)
Match if the inner matcher does NOT match.
Definition: PatternMatch.h:117
static Value * getValueFromBundleOpInfo(CallInst &Assume, const CallBase::BundleOpInfo &BOI, unsigned Idx)
This class represents a function call, abstracting a target machine&#39;s calling convention.
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:176
A cache of @llvm.assume calls within a function.
RetainedKnowledge getKnowledgeFromOperandInAssume(CallInst &Assume, unsigned Idx)
Retreive the information help by Assume on the operand at index Idx.
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, I, at the point in the control-flow identified by the context instruction, CxtI.
STATISTIC(NumFunctions, "Total number of functions")
op_iterator op_begin()
Definition: User.h:234
MutableArrayRef< ResultElem > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
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...
static bool isExistingAttribute(StringRef Name)
Return true if the provided string matches the IR name of an attribute.
Definition: Attributes.cpp:218
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
Used to keep track of an operand bundle.
Definition: InstrTypes.h:1997
static int Lookup(ArrayRef< TableEntry > Table, unsigned Opcode)
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44
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:1505
No attributes have been set.
Definition: Attributes.h:72
unsigned Intr
This file provides an implementation of debug counters.
Key
PAL metadata keys.
constexpr StringRef IgnoreBundleTag
Tag in operand bundle indicating that this bundle should be ignored.
static Attribute::AttrKind getAttrKindFromName(StringRef AttrName)
Definition: Attributes.cpp:187
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
uint32_t Begin
The index in the Use& vector where operands for this operand bundle starts.
Definition: InstrTypes.h:2004
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:144
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:673
Attribute::AttrKind AttrKind
static bool bundleHasArgument(const CallBase::BundleOpInfo &BOI, unsigned Idx)
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...
StringRef getKey() const
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:648
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:305
bool hasAttributeInAssume(CallInst &AssumeCI, 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...
static bool shouldExecute(unsigned CounterName)
Definition: DebugCounter.h:74
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:51
static bool doesAttrKindHaveArgument(Attribute::AttrKind AttrKind)
Return true if and only if the attribute has an Argument.
Definition: Attributes.cpp:210
void fillMapFromAssume(CallInst &AssumeCI, RetainedKnowledgeMap &Result)
Insert into the map all the informations contained in the operand bundles of the llvm.assume.
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
static RetainedKnowledge none()
StringMapEntry< uint32_t > * Tag
The operand bundle tag, interned by LLVMContextImpl::getOrInsertBundleTag.
Definition: InstrTypes.h:2000
BundleOpInfo & getBundleOpInfoForOperand(unsigned OpIdx)
Return the BundleOpInfo for the operand at index OpIdx.
#define I(x, y, z)
Definition: MD5.cpp:59
iterator end()
Definition: DenseMap.h:83
uint32_t End
The index in the Use& vector where operands for this operand bundle ends.
Definition: InstrTypes.h:2008
bool isAssumeWithEmptyBundle(CallInst &Assume)
Return true iff the operand bundles of the provided llvm.assume doesn&#39;t contain any valuable informat...
static CallInst::BundleOpInfo * getBundleFromUse(const Use *U)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:74
RetainedKnowledge getKnowledgeFromBundle(CallInst &Assume, const CallBase::BundleOpInfo &BOI)
This extracts the Knowledge from an element of an operand bundle.
bundle_op_iterator bundle_op_info_begin()
Return the start of the list of BundleOpInfo instances associated with this OperandBundleUser.
Definition: InstrTypes.h:2073
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:57
iterator_range< bundle_op_iterator > bundle_op_infos()
Return the range [bundle_op_info_begin, bundle_op_info_end).
Definition: InstrTypes.h:2106
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.
Represent one information held inside an operand bundle of an llvm.assume.
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:44
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:1549