-
Notifications
You must be signed in to change notification settings - Fork 11.1k
/
AliasAnalysis.h
284 lines (232 loc) · 11 KB
/
AliasAnalysis.h
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
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
//===- AliasAnalysis.h - Alias Analysis in MLIR -----------------*- 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 header file defines utilities and analyses for performing alias queries
// and related memory queries in MLIR.
//
//===----------------------------------------------------------------------===//
#ifndef MLIR_ANALYSIS_ALIASANALYSIS_H_
#define MLIR_ANALYSIS_ALIASANALYSIS_H_
#include "mlir/IR/Operation.h"
namespace mlir {
//===----------------------------------------------------------------------===//
// AliasResult
//===----------------------------------------------------------------------===//
/// The possible results of an alias query.
class AliasResult {
public:
enum Kind {
/// The two locations do not alias at all.
///
/// This value is arranged to convert to false, while all other values
/// convert to true. This allows a boolean context to convert the result to
/// a binary flag indicating whether there is the possibility of aliasing.
NoAlias = 0,
/// The two locations may or may not alias. This is the least precise
/// result.
MayAlias,
/// The two locations alias, but only due to a partial overlap.
PartialAlias,
/// The two locations precisely alias each other.
MustAlias,
};
AliasResult(Kind kind) : kind(kind) {}
bool operator==(const AliasResult &other) const { return kind == other.kind; }
bool operator!=(const AliasResult &other) const { return !(*this == other); }
/// Allow conversion to bool to signal if there is an aliasing or not.
explicit operator bool() const { return kind != NoAlias; }
/// Merge this alias result with `other` and return a new result that
/// represents the conservative merge of both results. If the results
/// represent a known alias, the stronger alias is chosen (i.e.
/// Partial+Must=Must). If the two results are conflicting, MayAlias is
/// returned.
AliasResult merge(AliasResult other) const;
/// Returns if this result indicates no possibility of aliasing.
bool isNo() const { return kind == NoAlias; }
/// Returns if this result is a may alias.
bool isMay() const { return kind == MayAlias; }
/// Returns if this result is a must alias.
bool isMust() const { return kind == MustAlias; }
/// Returns if this result is a partial alias.
bool isPartial() const { return kind == PartialAlias; }
/// Print this alias result to the provided output stream.
void print(raw_ostream &os) const;
private:
/// The internal kind of the result.
Kind kind;
};
inline raw_ostream &operator<<(raw_ostream &os, const AliasResult &result) {
result.print(os);
return os;
}
//===----------------------------------------------------------------------===//
// ModRefResult
//===----------------------------------------------------------------------===//
/// The possible results of whether a memory access modifies or references
/// a memory location. The possible results are: no access at all, a
/// modification, a reference, or both a modification and a reference.
class [[nodiscard]] ModRefResult {
/// Note: This is a simplified version of the ModRefResult in
/// `llvm/Analysis/AliasAnalysis.h`, and namely removes the `Must` concept. If
/// this becomes useful/necessary we should add it here.
enum class Kind {
/// The access neither references nor modifies the value stored in memory.
NoModRef = 0,
/// The access may reference the value stored in memory.
Ref = 1,
/// The access may modify the value stored in memory.
Mod = 2,
/// The access may reference and may modify the value stored in memory.
ModRef = Ref | Mod,
};
public:
bool operator==(const ModRefResult &rhs) const { return kind == rhs.kind; }
bool operator!=(const ModRefResult &rhs) const { return !(*this == rhs); }
/// Return a new result that indicates that the memory access neither
/// references nor modifies the value stored in memory.
static ModRefResult getNoModRef() { return Kind::NoModRef; }
/// Return a new result that indicates that the memory access may reference
/// the value stored in memory.
static ModRefResult getRef() { return Kind::Ref; }
/// Return a new result that indicates that the memory access may modify the
/// value stored in memory.
static ModRefResult getMod() { return Kind::Mod; }
/// Return a new result that indicates that the memory access may reference
/// and may modify the value stored in memory.
static ModRefResult getModAndRef() { return Kind::ModRef; }
/// Returns if this result does not modify or reference memory.
[[nodiscard]] bool isNoModRef() const { return kind == Kind::NoModRef; }
/// Returns if this result modifies memory.
[[nodiscard]] bool isMod() const {
return static_cast<int>(kind) & static_cast<int>(Kind::Mod);
}
/// Returns if this result references memory.
[[nodiscard]] bool isRef() const {
return static_cast<int>(kind) & static_cast<int>(Kind::Ref);
}
/// Returns if this result modifies *or* references memory.
[[nodiscard]] bool isModOrRef() const { return kind != Kind::NoModRef; }
/// Returns if this result modifies *and* references memory.
[[nodiscard]] bool isModAndRef() const { return kind == Kind::ModRef; }
/// Merge this ModRef result with `other` and return the result.
ModRefResult merge(const ModRefResult &other) {
return ModRefResult(static_cast<Kind>(static_cast<int>(kind) |
static_cast<int>(other.kind)));
}
/// Intersect this ModRef result with `other` and return the result.
ModRefResult intersect(const ModRefResult &other) {
return ModRefResult(static_cast<Kind>(static_cast<int>(kind) &
static_cast<int>(other.kind)));
}
/// Print this ModRef result to the provided output stream.
void print(raw_ostream &os) const;
private:
ModRefResult(Kind kind) : kind(kind) {}
/// The internal kind of the result.
Kind kind;
};
inline raw_ostream &operator<<(raw_ostream &os, const ModRefResult &result) {
result.print(os);
return os;
}
//===----------------------------------------------------------------------===//
// AliasAnalysisTraits
//===----------------------------------------------------------------------===//
namespace detail {
/// This class contains various internal trait classes used by the main
/// AliasAnalysis class below.
struct AliasAnalysisTraits {
/// This class represents the `Concept` of an alias analysis implementation.
/// It is the abstract base class used by the AliasAnalysis class for
/// querying into derived analysis implementations.
class Concept {
public:
virtual ~Concept() = default;
/// Given two values, return their aliasing behavior.
virtual AliasResult alias(Value lhs, Value rhs) = 0;
/// Return the modify-reference behavior of `op` on `location`.
virtual ModRefResult getModRef(Operation *op, Value location) = 0;
};
/// This class represents the `Model` of an alias analysis implementation
/// `ImplT`. A model is instantiated for each alias analysis implementation
/// to implement the `Concept` without the need for the derived
/// implementation to inherit from the `Concept` class.
template <typename ImplT>
class Model final : public Concept {
public:
explicit Model(ImplT &&impl) : impl(std::forward<ImplT>(impl)) {}
~Model() override = default;
/// Given two values, return their aliasing behavior.
AliasResult alias(Value lhs, Value rhs) final {
return impl.alias(lhs, rhs);
}
/// Return the modify-reference behavior of `op` on `location`.
ModRefResult getModRef(Operation *op, Value location) final {
return impl.getModRef(op, location);
}
private:
ImplT impl;
};
};
} // namespace detail
//===----------------------------------------------------------------------===//
// AliasAnalysis
//===----------------------------------------------------------------------===//
/// This class represents the main alias analysis interface in MLIR. It
/// functions as an aggregate of various different alias analysis
/// implementations. This aggregation allows for utilizing the strengths of
/// different alias analysis implementations that either target or have access
/// to different aliasing information. This is especially important for MLIR
/// given the scope of different types of memory models and aliasing behaviors.
/// For users of this analysis that want to perform aliasing queries, see the
/// `Alias Queries` section below for the available methods. For users of this
/// analysis that want to add a new alias analysis implementation to the
/// aggregate, see the `Alias Implementations` section below.
class AliasAnalysis {
using Concept = detail::AliasAnalysisTraits::Concept;
template <typename ImplT>
using Model = detail::AliasAnalysisTraits::Model<ImplT>;
public:
AliasAnalysis(Operation *op);
//===--------------------------------------------------------------------===//
// Alias Implementations
//===--------------------------------------------------------------------===//
/// Add a new alias analysis implementation `AnalysisT` to this analysis
/// aggregate. This allows for users to access this implementation when
/// performing alias queries. Implementations added here must provide the
/// following:
/// * AnalysisT(AnalysisT &&)
/// * AliasResult alias(Value lhs, Value rhs)
/// - This method returns an `AliasResult` that corresponds to the
/// aliasing behavior between `lhs` and `rhs`. The conservative "I don't
/// know" result of this method should be MayAlias.
/// * ModRefResult getModRef(Operation *op, Value location)
/// - This method returns a `ModRefResult` that corresponds to the
/// modify-reference behavior of `op` on the given `location`. The
/// conservative "I don't know" result of this method should be ModRef.
template <typename AnalysisT>
void addAnalysisImplementation(AnalysisT &&analysis) {
aliasImpls.push_back(
std::make_unique<Model<AnalysisT>>(std::forward<AnalysisT>(analysis)));
}
//===--------------------------------------------------------------------===//
// Alias Queries
//===--------------------------------------------------------------------===//
/// Given two values, return their aliasing behavior.
AliasResult alias(Value lhs, Value rhs);
//===--------------------------------------------------------------------===//
// ModRef Queries
//===--------------------------------------------------------------------===//
/// Return the modify-reference behavior of `op` on `location`.
ModRefResult getModRef(Operation *op, Value location);
private:
/// A set of internal alias analysis implementations.
SmallVector<std::unique_ptr<Concept>, 4> aliasImpls;
};
} // namespace mlir
#endif // MLIR_ANALYSIS_ALIASANALYSIS_H_