1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
#pragma once
#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif
//===- AssumeBundleQueries.h - utilities to query assume bundles *- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file contain tools to query into assume bundles. assume bundles can be
// built using utilities from Transform/Utils/AssumeBundleBuilder.h
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ANALYSIS_ASSUMEBUNDLEQUERIES_H
#define LLVM_ANALYSIS_ASSUMEBUNDLEQUERIES_H
#include "llvm/IR/Attributes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/ADT/DenseMap.h"
namespace llvm {
class AssumptionCache;
class DominatorTree;
/// Index of elements in the operand bundle.
/// If the element exist it is guaranteed to be what is specified in this enum
/// but it may not exist.
enum AssumeBundleArg {
ABA_WasOn = 0,
ABA_Argument = 1,
};
/// Query the operand bundle of an llvm.assume to find a single attribute of
/// the specified kind applied on a specified Value.
///
/// This has a non-constant complexity. It should only be used when a single
/// attribute is going to be queried.
///
/// Return true iff the queried attribute was found.
/// If ArgVal is set. the argument will be stored to ArgVal.
bool hasAttributeInAssume(AssumeInst &Assume, Value *IsOn, StringRef AttrName,
uint64_t *ArgVal = nullptr);
inline bool hasAttributeInAssume(AssumeInst &Assume, Value *IsOn,
Attribute::AttrKind Kind,
uint64_t *ArgVal = nullptr) {
return hasAttributeInAssume(Assume, IsOn,
Attribute::getNameFromAttrKind(Kind), ArgVal);
}
template<> struct DenseMapInfo<Attribute::AttrKind> {
static Attribute::AttrKind getEmptyKey() {
return Attribute::EmptyKey;
}
static Attribute::AttrKind getTombstoneKey() {
return Attribute::TombstoneKey;
}
static unsigned getHashValue(Attribute::AttrKind AK) {
return hash_combine(AK);
}
static bool isEqual(Attribute::AttrKind LHS, Attribute::AttrKind RHS) {
return LHS == RHS;
}
};
/// The map Key contains the Value on for which the attribute is valid and
/// the Attribute that is valid for that value.
/// If the Attribute is not on any value, the Value is nullptr.
using RetainedKnowledgeKey = std::pair<Value *, Attribute::AttrKind>;
struct MinMax {
uint64_t Min;
uint64_t Max;
};
/// A mapping from intrinsics (=`llvm.assume` calls) to a value range
/// (=knowledge) that is encoded in them. How the value range is interpreted
/// depends on the RetainedKnowledgeKey that was used to get this out of the
/// RetainedKnowledgeMap.
using Assume2KnowledgeMap = DenseMap<AssumeInst *, MinMax>;
using RetainedKnowledgeMap =
DenseMap<RetainedKnowledgeKey, Assume2KnowledgeMap>;
/// Insert into the map all the informations contained in the operand bundles of
/// the llvm.assume. This should be used instead of hasAttributeInAssume when
/// many queries are going to be made on the same llvm.assume.
/// String attributes are not inserted in the map.
/// If the IR changes the map will be outdated.
void fillMapFromAssume(AssumeInst &Assume, RetainedKnowledgeMap &Result);
/// Represent one information held inside an operand bundle of an llvm.assume.
/// AttrKind is the property that holds.
/// WasOn if not null is that Value for which AttrKind holds.
/// ArgValue is optionally an argument of the attribute.
/// For example if we know that %P has an alignment of at least four:
/// - AttrKind will be Attribute::Alignment.
/// - WasOn will be %P.
/// - ArgValue will be 4.
struct RetainedKnowledge {
Attribute::AttrKind AttrKind = Attribute::None;
uint64_t ArgValue = 0;
Value *WasOn = nullptr;
bool operator==(RetainedKnowledge Other) const {
return AttrKind == Other.AttrKind && WasOn == Other.WasOn &&
ArgValue == Other.ArgValue;
}
bool operator!=(RetainedKnowledge Other) const { return !(*this == Other); }
/// This is only intended for use in std::min/std::max between attribute that
/// only differ in ArgValue.
bool operator<(RetainedKnowledge Other) const {
assert(((AttrKind == Other.AttrKind && WasOn == Other.WasOn) ||
AttrKind == Attribute::None || Other.AttrKind == Attribute::None) &&
"This is only intend for use in min/max to select the best for "
"RetainedKnowledge that is otherwise equal");
return ArgValue < Other.ArgValue;
}
operator bool() const { return AttrKind != Attribute::None; }
static RetainedKnowledge none() { return RetainedKnowledge{}; }
};
/// Retreive the information help by Assume on the operand at index Idx.
/// Assume should be an llvm.assume and Idx should be in the operand bundle.
RetainedKnowledge getKnowledgeFromOperandInAssume(AssumeInst &Assume,
unsigned Idx);
/// Retreive the information help by the Use U of an llvm.assume. the use should
/// be in the operand bundle.
inline RetainedKnowledge getKnowledgeFromUseInAssume(const Use *U) {
return getKnowledgeFromOperandInAssume(*cast<AssumeInst>(U->getUser()),
U->getOperandNo());
}
/// Tag in operand bundle indicating that this bundle should be ignored.
constexpr StringRef IgnoreBundleTag = "ignore";
/// Return true iff the operand bundles of the provided llvm.assume doesn't
/// contain any valuable information. This is true when:
/// - The operand bundle is empty
/// - The operand bundle only contains information about dropped values or
/// constant folded values.
///
/// the argument to the call of llvm.assume may still be useful even if the
/// function returned true.
bool isAssumeWithEmptyBundle(AssumeInst &Assume);
/// Return a valid Knowledge associated to the Use U if its Attribute kind is
/// in AttrKinds.
RetainedKnowledge getKnowledgeFromUse(const Use *U,
ArrayRef<Attribute::AttrKind> AttrKinds);
/// Return a valid Knowledge associated to the Value V if its Attribute kind is
/// in AttrKinds and it matches the Filter.
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 the knowledge is suitable to be used in the context of
/// CtxI.
RetainedKnowledge getKnowledgeValidInContext(
const Value *V, ArrayRef<Attribute::AttrKind> AttrKinds,
const Instruction *CtxI, const DominatorTree *DT = nullptr,
AssumptionCache *AC = nullptr);
/// This extracts the Knowledge from an element of an operand bundle.
/// This is mostly for use in the assume builder.
RetainedKnowledge getKnowledgeFromBundle(AssumeInst &Assume,
const CallBase::BundleOpInfo &BOI);
} // namespace llvm
#endif
#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif
|
