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
20namespace llvm {
21class AssumptionCache;
22class DominatorTree;
23class Instruction;
24class 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.
29enum 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.
42bool hasAttributeInAssume(AssumeInst &Assume, Value *IsOn, StringRef AttrName,
43 uint64_t *ArgVal = nullptr);
44inline 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
51template<> 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.
69using RetainedKnowledgeKey = std::pair<Value *, Attribute::AttrKind>;
70
71struct 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.
80using Assume2KnowledgeMap = DenseMap<AssumeInst *, MinMax>;
81
82using 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.
90void 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.
100struct 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.
124RetainedKnowledge 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.
129inline 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.
135constexpr 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.
145bool isAssumeWithEmptyBundle(const AssumeInst &Assume);
146
147/// Return a valid Knowledge associated to the Use U if its Attribute kind is
148/// in AttrKinds.
149RetainedKnowledge 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.
154RetainedKnowledge 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.
164RetainedKnowledge 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.
171RetainedKnowledge getKnowledgeFromBundle(AssumeInst &Assume,
172 const CallBase::BundleOpInfo &BOI);
173
174} // namespace llvm
175
176#endif
177

source code of llvm/include/llvm/Analysis/AssumeBundleQueries.h