1 | //===- AssumeBundleQueries.h - utilis 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/ADT/DenseMap.h" |
18 | #include "llvm/IR/IntrinsicInst.h" |
19 | |
20 | namespace llvm { |
21 | class AssumptionCache; |
22 | class DominatorTree; |
23 | class Instruction; |
24 | class Value; |
25 | |
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 { |
30 | ABA_WasOn = 0, |
31 | ABA_Argument = 1, |
32 | }; |
33 | |
34 | /// Query the operand bundle of an llvm.assume to find a single attribute of |
35 | /// the specified kind applied on a specified Value. |
36 | /// |
37 | /// This has a non-constant complexity. It should only be used when a single |
38 | /// attribute is going to be queried. |
39 | /// |
40 | /// Return true iff the queried attribute was found. |
41 | /// If ArgVal is set. the argument will be stored to ArgVal. |
42 | bool hasAttributeInAssume(AssumeInst &Assume, Value *IsOn, StringRef AttrName, |
43 | uint64_t *ArgVal = nullptr); |
44 | inline bool hasAttributeInAssume(AssumeInst &Assume, Value *IsOn, |
45 | Attribute::AttrKind Kind, |
46 | uint64_t *ArgVal = nullptr) { |
47 | return hasAttributeInAssume(Assume, IsOn, |
48 | AttrName: Attribute::getNameFromAttrKind(AttrKind: Kind), ArgVal); |
49 | } |
50 | |
51 | template<> struct DenseMapInfo<Attribute::AttrKind> { |
52 | static Attribute::AttrKind getEmptyKey() { |
53 | return Attribute::EmptyKey; |
54 | } |
55 | static Attribute::AttrKind getTombstoneKey() { |
56 | return Attribute::TombstoneKey; |
57 | } |
58 | static unsigned getHashValue(Attribute::AttrKind AK) { |
59 | return hash_combine(args: AK); |
60 | } |
61 | static bool isEqual(Attribute::AttrKind LHS, Attribute::AttrKind RHS) { |
62 | return LHS == RHS; |
63 | } |
64 | }; |
65 | |
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>; |
70 | |
71 | struct MinMax { |
72 | uint64_t Min; |
73 | uint64_t Max; |
74 | }; |
75 | |
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<AssumeInst *, MinMax>; |
81 | |
82 | using RetainedKnowledgeMap = |
83 | DenseMap<RetainedKnowledgeKey, Assume2KnowledgeMap>; |
84 | |
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(AssumeInst &Assume, RetainedKnowledgeMap &Result); |
91 | |
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 | uint64_t ArgValue = 0; |
103 | Value *WasOn = nullptr; |
104 | bool operator==(RetainedKnowledge Other) const { |
105 | return AttrKind == Other.AttrKind && WasOn == Other.WasOn && |
106 | ArgValue == Other.ArgValue; |
107 | } |
108 | bool operator!=(RetainedKnowledge Other) const { return !(*this == Other); } |
109 | /// This is only intended for use in std::min/std::max between attribute that |
110 | /// only differ in ArgValue. |
111 | bool operator<(RetainedKnowledge Other) const { |
112 | assert(((AttrKind == Other.AttrKind && WasOn == Other.WasOn) || |
113 | AttrKind == Attribute::None || Other.AttrKind == Attribute::None) && |
114 | "This is only intend for use in min/max to select the best for " |
115 | "RetainedKnowledge that is otherwise equal" ); |
116 | return ArgValue < Other.ArgValue; |
117 | } |
118 | operator bool() const { return AttrKind != Attribute::None; } |
119 | static RetainedKnowledge none() { return RetainedKnowledge{}; } |
120 | }; |
121 | |
122 | /// Retreive the information help by Assume on the operand at index Idx. |
123 | /// Assume should be an llvm.assume and Idx should be in the operand bundle. |
124 | RetainedKnowledge getKnowledgeFromOperandInAssume(AssumeInst &Assume, |
125 | unsigned Idx); |
126 | |
127 | /// Retreive the information help by the Use U of an llvm.assume. the use should |
128 | /// be in the operand bundle. |
129 | inline RetainedKnowledge getKnowledgeFromUseInAssume(const Use *U) { |
130 | return getKnowledgeFromOperandInAssume(Assume&: *cast<AssumeInst>(Val: U->getUser()), |
131 | Idx: U->getOperandNo()); |
132 | } |
133 | |
134 | /// Tag in operand bundle indicating that this bundle should be ignored. |
135 | constexpr StringRef IgnoreBundleTag = "ignore" ; |
136 | |
137 | /// Return true iff the operand bundles of the provided llvm.assume doesn't |
138 | /// contain any valuable information. This is true when: |
139 | /// - The operand bundle is empty |
140 | /// - The operand bundle only contains information about dropped values or |
141 | /// constant folded values. |
142 | /// |
143 | /// the argument to the call of llvm.assume may still be useful even if the |
144 | /// function returned true. |
145 | bool isAssumeWithEmptyBundle(const AssumeInst &Assume); |
146 | |
147 | /// Return a valid Knowledge associated to the Use U if its Attribute kind is |
148 | /// in AttrKinds. |
149 | RetainedKnowledge getKnowledgeFromUse(const Use *U, |
150 | ArrayRef<Attribute::AttrKind> AttrKinds); |
151 | |
152 | /// Return a valid Knowledge associated to the Value V if its Attribute kind is |
153 | /// in AttrKinds and it matches the Filter. |
154 | RetainedKnowledge getKnowledgeForValue( |
155 | const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds, |
156 | AssumptionCache *AC = nullptr, |
157 | function_ref<bool(RetainedKnowledge, Instruction *, |
158 | const CallBase::BundleOpInfo *)> |
159 | Filter = [](auto...) { return true; }); |
160 | |
161 | /// Return a valid Knowledge associated to the Value V if its Attribute kind is |
162 | /// in AttrKinds and the knowledge is suitable to be used in the context of |
163 | /// CtxI. |
164 | RetainedKnowledge getKnowledgeValidInContext( |
165 | const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds, |
166 | const Instruction *CtxI, const DominatorTree *DT = nullptr, |
167 | AssumptionCache *AC = nullptr); |
168 | |
169 | /// This extracts the Knowledge from an element of an operand bundle. |
170 | /// This is mostly for use in the assume builder. |
171 | RetainedKnowledge getKnowledgeFromBundle(AssumeInst &Assume, |
172 | const CallBase::BundleOpInfo &BOI); |
173 | |
174 | } // namespace llvm |
175 | |
176 | #endif |
177 | |