1 //===- AssumeBundleQueries.h - utilities to query assume bundles *- C++ -*-===//
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 contain tools to query into assume bundles. assume bundles can be
10 // built using utilities from Transform/Utils/AssumeBundleBuilder.h
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_TRANSFORMS_UTILS_ASSUMEBUNDLEQUERIES_H
15 #define LLVM_TRANSFORMS_UTILS_ASSUMEBUNDLEQUERIES_H
17 #include "llvm/IR/Attributes.h"
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/ADT/DenseMap.h"
23 class AssumptionCache;
26 /// Index of elements in the operand bundle.
27 /// If the element exist it is guaranteed to be what is specified in this enum
28 /// but it may not exist.
29 enum AssumeBundleArg {
34 /// Query the operand bundle of an llvm.assume to find a single attribute of
35 /// the specified kind applied on a specified Value.
37 /// This has a non-constant complexity. It should only be used when a single
38 /// attribute is going to be queried.
40 /// Return true iff the queried attribute was found.
41 /// If ArgVal is set. the argument will be stored to ArgVal.
42 bool hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn, StringRef AttrName,
43 uint64_t *ArgVal = nullptr);
44 inline bool hasAttributeInAssume(CallInst &AssumeCI, Value *IsOn,
45 Attribute::AttrKind Kind,
46 uint64_t *ArgVal = nullptr) {
47 return hasAttributeInAssume(AssumeCI, IsOn,
48 Attribute::getNameFromAttrKind(Kind), ArgVal);
51 template<> struct DenseMapInfo<Attribute::AttrKind> {
52 static Attribute::AttrKind getEmptyKey() {
53 return Attribute::EmptyKey;
55 static Attribute::AttrKind getTombstoneKey() {
56 return Attribute::TombstoneKey;
58 static unsigned getHashValue(Attribute::AttrKind AK) {
59 return hash_combine(AK);
61 static bool isEqual(Attribute::AttrKind LHS, Attribute::AttrKind RHS) {
66 /// The map Key contains the Value on for which the attribute is valid and
67 /// the Attribute that is valid for that value.
68 /// If the Attribute is not on any value, the Value is nullptr.
69 using RetainedKnowledgeKey = std::pair<Value *, Attribute::AttrKind>;
76 /// A mapping from intrinsics (=`llvm.assume` calls) to a value range
77 /// (=knowledge) that is encoded in them. How the value range is interpreted
78 /// depends on the RetainedKnowledgeKey that was used to get this out of the
79 /// RetainedKnowledgeMap.
80 using Assume2KnowledgeMap = DenseMap<IntrinsicInst *, MinMax>;
82 using RetainedKnowledgeMap =
83 DenseMap<RetainedKnowledgeKey, Assume2KnowledgeMap>;
85 /// Insert into the map all the informations contained in the operand bundles of
86 /// the llvm.assume. This should be used instead of hasAttributeInAssume when
87 /// many queries are going to be made on the same llvm.assume.
88 /// String attributes are not inserted in the map.
89 /// If the IR changes the map will be outdated.
90 void fillMapFromAssume(CallInst &AssumeCI, RetainedKnowledgeMap &Result);
92 /// Represent one information held inside an operand bundle of an llvm.assume.
93 /// AttrKind is the property that holds.
94 /// WasOn if not null is that Value for which AttrKind holds.
95 /// ArgValue is optionally an argument of the attribute.
96 /// For example if we know that %P has an alignment of at least four:
97 /// - AttrKind will be Attribute::Alignment.
98 /// - WasOn will be %P.
99 /// - ArgValue will be 4.
100 struct RetainedKnowledge {
101 Attribute::AttrKind AttrKind = Attribute::None;
102 unsigned ArgValue = 0;
103 Value *WasOn = nullptr;
104 bool operator==(RetainedKnowledge Other) const {
105 return AttrKind == Other.AttrKind && WasOn == Other.WasOn &&
106 ArgValue == Other.ArgValue;
108 bool operator!=(RetainedKnowledge Other) const { return !(*this == Other); }
109 operator bool() const { return AttrKind != Attribute::None; }
110 static RetainedKnowledge none() { return RetainedKnowledge{}; }
113 /// Retreive the information help by Assume on the operand at index Idx.
114 /// Assume should be an llvm.assume and Idx should be in the operand bundle.
115 RetainedKnowledge getKnowledgeFromOperandInAssume(CallInst &Assume,
118 /// Retreive the information help by the Use U of an llvm.assume. the use should
119 /// be in the operand bundle.
120 inline RetainedKnowledge getKnowledgeFromUseInAssume(const Use *U) {
121 return getKnowledgeFromOperandInAssume(*cast<CallInst>(U->getUser()),
125 /// Tag in operand bundle indicating that this bundle should be ignored.
126 constexpr StringRef IgnoreBundleTag = "ignore";
128 /// Return true iff the operand bundles of the provided llvm.assume doesn't
129 /// contain any valuable information. This is true when:
130 /// - The operand bundle is empty
131 /// - The operand bundle only contains information about dropped values or
132 /// constant folded values.
134 /// the argument to the call of llvm.assume may still be useful even if the
135 /// function returned true.
136 bool isAssumeWithEmptyBundle(CallInst &Assume);
138 /// Return a valid Knowledge associated to the Use U if its Attribute kind is
140 RetainedKnowledge getKnowledgeFromUse(const Use *U,
141 ArrayRef<Attribute::AttrKind> AttrKinds);
143 /// Return a valid Knowledge associated to the Value V if its Attribute kind is
144 /// in AttrKinds and it matches the Filter.
145 RetainedKnowledge getKnowledgeForValue(
146 const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
147 AssumptionCache *AC = nullptr,
148 function_ref<bool(RetainedKnowledge, Instruction *,
149 const CallBase::BundleOpInfo *)>
150 Filter = [](auto...) { return true; });
152 /// Return a valid Knowledge associated to the Value V if its Attribute kind is
153 /// in AttrKinds and the knowledge is suitable to be used in the context of
155 RetainedKnowledge getKnowledgeValidInContext(
156 const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
157 const Instruction *CtxI, const DominatorTree *DT = nullptr,
158 AssumptionCache *AC = nullptr);
160 /// This extracts the Knowledge from an element of an operand bundle.
161 /// This is mostly for use in the assume builder.
162 RetainedKnowledge getKnowledgeFromBundle(CallInst &Assume,
163 const CallBase::BundleOpInfo &BOI);