LLVM  13.0.0git
AssumeBundleQueries.h
Go to the documentation of this file.
1 //===- AssumeBundleQueries.h - utilities 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 // This file contain tools to query into assume bundles. assume bundles can be
10 // built using utilities from Transform/Utils/AssumeBundleBuilder.h
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ANALYSIS_ASSUMEBUNDLEQUERIES_H
15 #define LLVM_ANALYSIS_ASSUMEBUNDLEQUERIES_H
16 
17 #include "llvm/IR/Attributes.h"
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/IR/IntrinsicInst.h"
20 #include "llvm/ADT/DenseMap.h"
21 
22 namespace llvm {
23 class IntrinsicInst;
24 class AssumptionCache;
25 class DominatorTree;
26 
27 /// Index of elements in the operand bundle.
28 /// If the element exist it is guaranteed to be what is specified in this enum
29 /// but it may not exist.
31  ABA_WasOn = 0,
33 };
34 
35 /// Query the operand bundle of an llvm.assume to find a single attribute of
36 /// the specified kind applied on a specified Value.
37 ///
38 /// This has a non-constant complexity. It should only be used when a single
39 /// attribute is going to be queried.
40 ///
41 /// Return true iff the queried attribute was found.
42 /// If ArgVal is set. the argument will be stored to ArgVal.
43 bool hasAttributeInAssume(AssumeInst &Assume, Value *IsOn, StringRef AttrName,
44  uint64_t *ArgVal = nullptr);
45 inline bool hasAttributeInAssume(AssumeInst &Assume, Value *IsOn,
47  uint64_t *ArgVal = nullptr) {
48  return hasAttributeInAssume(Assume, IsOn,
50 }
51 
52 template<> struct DenseMapInfo<Attribute::AttrKind> {
54  return Attribute::EmptyKey;
55  }
58  }
59  static unsigned getHashValue(Attribute::AttrKind AK) {
60  return hash_combine(AK);
61  }
63  return LHS == RHS;
64  }
65 };
66 
67 /// The map Key contains the Value on for which the attribute is valid and
68 /// the Attribute that is valid for that value.
69 /// If the Attribute is not on any value, the Value is nullptr.
70 using RetainedKnowledgeKey = std::pair<Value *, Attribute::AttrKind>;
71 
72 struct MinMax {
73  unsigned Min;
74  unsigned Max;
75 };
76 
77 /// A mapping from intrinsics (=`llvm.assume` calls) to a value range
78 /// (=knowledge) that is encoded in them. How the value range is interpreted
79 /// depends on the RetainedKnowledgeKey that was used to get this out of the
80 /// RetainedKnowledgeMap.
82 
85 
86 /// Insert into the map all the informations contained in the operand bundles of
87 /// the llvm.assume. This should be used instead of hasAttributeInAssume when
88 /// many queries are going to be made on the same llvm.assume.
89 /// String attributes are not inserted in the map.
90 /// If the IR changes the map will be outdated.
92 
93 /// Represent one information held inside an operand bundle of an llvm.assume.
94 /// AttrKind is the property that holds.
95 /// WasOn if not null is that Value for which AttrKind holds.
96 /// ArgValue is optionally an argument of the attribute.
97 /// For example if we know that %P has an alignment of at least four:
98 /// - AttrKind will be Attribute::Alignment.
99 /// - WasOn will be %P.
100 /// - ArgValue will be 4.
103  unsigned ArgValue = 0;
104  Value *WasOn = nullptr;
105  bool operator==(RetainedKnowledge Other) const {
106  return AttrKind == Other.AttrKind && WasOn == Other.WasOn &&
107  ArgValue == Other.ArgValue;
108  }
109  bool operator!=(RetainedKnowledge Other) const { return !(*this == Other); }
110  /// This is only intended for use in std::min/std::max between attribute that
111  /// only differ in ArgValue.
112  bool operator<(RetainedKnowledge Other) const {
113  assert(((AttrKind == Other.AttrKind && WasOn == Other.WasOn) ||
114  AttrKind == Attribute::None || Other.AttrKind == Attribute::None) &&
115  "This is only intend for use in min/max to select the best for "
116  "RetainedKnowledge that is otherwise equal");
117  return ArgValue < Other.ArgValue;
118  }
119  operator bool() const { return AttrKind != Attribute::None; }
120  static RetainedKnowledge none() { return RetainedKnowledge{}; }
121 };
122 
123 /// Retreive the information help by Assume on the operand at index Idx.
124 /// Assume should be an llvm.assume and Idx should be in the operand bundle.
125 RetainedKnowledge getKnowledgeFromOperandInAssume(AssumeInst &Assume,
126  unsigned Idx);
127 
128 /// Retreive the information help by the Use U of an llvm.assume. the use should
129 /// be in the operand bundle.
131  return getKnowledgeFromOperandInAssume(*cast<AssumeInst>(U->getUser()),
132  U->getOperandNo());
133 }
134 
135 /// Tag in operand bundle indicating that this bundle should be ignored.
136 constexpr StringRef IgnoreBundleTag = "ignore";
137 
138 /// Return true iff the operand bundles of the provided llvm.assume doesn't
139 /// contain any valuable information. This is true when:
140 /// - The operand bundle is empty
141 /// - The operand bundle only contains information about dropped values or
142 /// constant folded values.
143 ///
144 /// the argument to the call of llvm.assume may still be useful even if the
145 /// function returned true.
146 bool isAssumeWithEmptyBundle(AssumeInst &Assume);
147 
148 /// Return a valid Knowledge associated to the Use U if its Attribute kind is
149 /// in AttrKinds.
152 
153 /// Return a valid Knowledge associated to the Value V if its Attribute kind is
154 /// in AttrKinds and it matches the Filter.
156  const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
157  AssumptionCache *AC = nullptr,
159  const CallBase::BundleOpInfo *)>
160  Filter = [](auto...) { return true; });
161 
162 /// Return a valid Knowledge associated to the Value V if its Attribute kind is
163 /// in AttrKinds and the knowledge is suitable to be used in the context of
164 /// CtxI.
165 RetainedKnowledge getKnowledgeValidInContext(
166  const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
167  const Instruction *CtxI, const DominatorTree *DT = nullptr,
168  AssumptionCache *AC = nullptr);
169 
170 /// This extracts the Knowledge from an element of an operand bundle.
171 /// This is mostly for use in the assume builder.
172 RetainedKnowledge getKnowledgeFromBundle(AssumeInst &Assume,
173  const CallBase::BundleOpInfo &BOI);
174 
175 } // namespace llvm
176 
177 #endif
llvm::RetainedKnowledge::WasOn
Value * WasOn
Definition: AssumeBundleQueries.h:104
llvm
Definition: AllocatorList.h:23
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
llvm::Attribute
Definition: Attributes.h:52
llvm::Attribute::TombstoneKey
@ TombstoneKey
Use as Tombstone key for DenseMap of AttrKind.
Definition: Attributes.h:79
llvm::IgnoreBundleTag
constexpr StringRef IgnoreBundleTag
Tag in operand bundle indicating that this bundle should be ignored.
Definition: AssumeBundleQueries.h:136
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::Attribute::EmptyKey
@ EmptyKey
Use as Empty key for DenseMap of AttrKind.
Definition: Attributes.h:78
llvm::AssumeInst
This represents the llvm.assume intrinsic.
Definition: IntrinsicInst.h:1278
DenseMap.h
llvm::RetainedKnowledge::operator==
bool operator==(RetainedKnowledge Other) const
Definition: AssumeBundleQueries.h:105
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::AssumeBundleArg
AssumeBundleArg
Index of elements in the operand bundle.
Definition: AssumeBundleQueries.h:30
llvm::ABA_WasOn
@ ABA_WasOn
Definition: AssumeBundleQueries.h:31
llvm::RetainedKnowledge::operator!=
bool operator!=(RetainedKnowledge Other) const
Definition: AssumeBundleQueries.h:109
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
llvm::DenseMapInfo< Attribute::AttrKind >::getEmptyKey
static Attribute::AttrKind getEmptyKey()
Definition: AssumeBundleQueries.h:53
llvm::Instruction
Definition: Instruction.h:45
llvm::RetainedKnowledge::ArgValue
unsigned ArgValue
Definition: AssumeBundleQueries.h:103
llvm::CallBase::BundleOpInfo
Used to keep track of an operand bundle.
Definition: InstrTypes.h:2104
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
llvm::getKnowledgeFromUseInAssume
RetainedKnowledge getKnowledgeFromUseInAssume(const Use *U)
Retreive the information help by the Use U of an llvm.assume.
Definition: AssumeBundleQueries.h:130
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::MinMax::Min
unsigned Min
Definition: AssumeBundleQueries.h:73
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
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::operator<
bool operator<(RetainedKnowledge Other) const
This is only intended for use in std::min/stdmax between attribute that only differ in ArgValue.
Definition: AssumeBundleQueries.h:112
llvm::RetainedKnowledge::none
static RetainedKnowledge none()
Definition: AssumeBundleQueries.h:120
llvm::DenseMap
Definition: DenseMap.h:714
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
llvm::DenseMapInfo< Attribute::AttrKind >::isEqual
static bool isEqual(Attribute::AttrKind LHS, Attribute::AttrKind RHS)
Definition: AssumeBundleQueries.h:62
llvm::Attribute::AttrKind
AttrKind
This enumeration lists the attributes that can be associated with parameters, function results,...
Definition: Attributes.h:71
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DenseMapInfo< Attribute::AttrKind >::getTombstoneKey
static Attribute::AttrKind getTombstoneKey()
Definition: AssumeBundleQueries.h:56
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::MinMax
Definition: AssumeBundleQueries.h:72
llvm::RetainedKnowledge
Represent one information held inside an operand bundle of an llvm.assume.
Definition: AssumeBundleQueries.h:101
Attributes.h
llvm::MinMax::Max
unsigned Max
Definition: AssumeBundleQueries.h:74
llvm::DenseMapInfo< Attribute::AttrKind >::getHashValue
static unsigned getHashValue(Attribute::AttrKind AK)
Definition: AssumeBundleQueries.h:59
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::Attribute::getNameFromAttrKind
static StringRef getNameFromAttrKind(Attribute::AttrKind AttrKind)
Definition: Attributes.cpp:225
Instructions.h
llvm::hash_combine
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
Definition: Hashing.h:604
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::getKnowledgeFromOperandInAssume
RetainedKnowledge getKnowledgeFromOperandInAssume(AssumeInst &Assume, unsigned Idx)
Retreive the information help by Assume on the operand at index Idx.
Definition: AssumeBundleQueries.cpp:119
llvm::RetainedKnowledgeKey
std::pair< Value *, Attribute::AttrKind > RetainedKnowledgeKey
The map Key contains the Value on for which the attribute is valid and the Attribute that is valid fo...
Definition: AssumeBundleQueries.h:70
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1169
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