LLVM 20.0.0git
Legality.h
Go to the documentation of this file.
1//===- Legality.h -----------------------------------------------*- 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// Legality checks for the Sandbox Vectorizer.
10//
11
12#ifndef LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_LEGALITY_H
13#define LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_LEGALITY_H
14
15#include "llvm/ADT/ArrayRef.h"
17#include "llvm/IR/DataLayout.h"
21
22namespace llvm::sandboxir {
23
24class LegalityAnalysis;
25class Value;
26class InstrMaps;
27
29public:
31
32private:
33 IndicesVecT Indices;
34
35public:
36 ShuffleMask(SmallVectorImpl<int> &&Indices) : Indices(std::move(Indices)) {}
37 ShuffleMask(std::initializer_list<int> Indices) : Indices(Indices) {}
38 explicit ShuffleMask(ArrayRef<int> Indices) : Indices(Indices) {}
39 operator ArrayRef<int>() const { return Indices; }
40 /// Creates and returns an identity shuffle mask of size \p Sz.
41 /// For example if Sz == 4 the returned mask is {0, 1, 2, 3}.
42 static ShuffleMask getIdentity(unsigned Sz) {
43 IndicesVecT Indices;
44 Indices.reserve(Sz);
45 for (auto Idx : seq<int>(0, (int)Sz))
46 Indices.push_back(Idx);
47 return ShuffleMask(std::move(Indices));
48 }
49 /// \Returns true if the mask is a perfect identity mask with consecutive
50 /// indices, i.e., performs no lane shuffling, like 0,1,2,3...
51 bool isIdentity() const {
52 for (auto [Idx, Elm] : enumerate(Indices)) {
53 if ((int)Idx != Elm)
54 return false;
55 }
56 return true;
57 }
58 bool operator==(const ShuffleMask &Other) const {
59 return Indices == Other.Indices;
60 }
61 bool operator!=(const ShuffleMask &Other) const { return !(*this == Other); }
62 size_t size() const { return Indices.size(); }
63 int operator[](int Idx) const { return Indices[Idx]; }
65 const_iterator begin() const { return Indices.begin(); }
66 const_iterator end() const { return Indices.end(); }
67#ifndef NDEBUG
69 Mask.print(OS);
70 return OS;
71 }
72 void print(raw_ostream &OS) const {
73 interleave(Indices, OS, [&OS](auto Elm) { OS << Elm; }, ",");
74 }
75 LLVM_DUMP_METHOD void dump() const;
76#endif
77};
78
79enum class LegalityResultID {
80 Pack, ///> Collect scalar values.
81 Widen, ///> Vectorize by combining scalars to a vector.
82 DiamondReuse, ///> Don't generate new code, reuse existing vector.
83 DiamondReuseWithShuffle, ///> Reuse the existing vector but add a shuffle.
84};
85
86/// The reason for vectorizing or not vectorizing.
87enum class ResultReason {
97};
98
99#ifndef NDEBUG
100struct ToStr {
102 switch (ID) {
104 return "Pack";
106 return "Widen";
108 return "DiamondReuse";
110 return "DiamondReuseWithShuffle";
111 }
112 llvm_unreachable("Unknown LegalityResultID enum");
113 }
114
115 static const char *getVecReason(ResultReason Reason) {
116 switch (Reason) {
118 return "NotInstructions";
120 return "DiffOpcodes";
122 return "DiffTypes";
124 return "DiffMathFlags";
126 return "DiffWrapFlags";
128 return "NotConsecutive";
130 return "CantSchedule";
132 return "Unimplemented";
134 return "Infeasible";
135 }
136 llvm_unreachable("Unknown ResultReason enum");
137 }
138};
139#endif // NDEBUG
140
141/// The legality outcome is represented by a class rather than an enum class
142/// because in some cases the legality checks are expensive and look for a
143/// particular instruction that can be passed along to the vectorizer to avoid
144/// repeating the same expensive computation.
146protected:
148 /// Only Legality can create LegalityResults.
150 friend class LegalityAnalysis;
151
152 /// We shouldn't need copies.
155
156public:
157 virtual ~LegalityResult() {}
159#ifndef NDEBUG
160 virtual void print(raw_ostream &OS) const {
162 }
163 LLVM_DUMP_METHOD void dump() const;
165 LR.print(OS);
166 return OS;
167 }
168#endif // NDEBUG
169};
170
171/// Base class for results with reason.
173 [[maybe_unused]] ResultReason Reason;
175 : LegalityResult(ID), Reason(Reason) {}
176 friend class Pack; // For constructor.
177
178public:
179 ResultReason getReason() const { return Reason; }
180#ifndef NDEBUG
181 void print(raw_ostream &OS) const override {
183 OS << " Reason: " << ToStr::getVecReason(Reason);
184 }
185#endif
186};
187
188class Widen final : public LegalityResult {
189 friend class LegalityAnalysis;
191
192public:
193 static bool classof(const LegalityResult *From) {
194 return From->getSubclassID() == LegalityResultID::Widen;
195 }
196};
197
198class DiamondReuse final : public LegalityResult {
199 friend class LegalityAnalysis;
200 Value *Vec;
201 DiamondReuse(Value *Vec)
203
204public:
205 static bool classof(const LegalityResult *From) {
206 return From->getSubclassID() == LegalityResultID::DiamondReuse;
207 }
208 Value *getVector() const { return Vec; }
209};
210
212 friend class LegalityAnalysis;
213 Value *Vec;
214 ShuffleMask Mask;
215 DiamondReuseWithShuffle(Value *Vec, const ShuffleMask &Mask)
217 Mask(Mask) {}
218
219public:
220 static bool classof(const LegalityResult *From) {
221 return From->getSubclassID() == LegalityResultID::DiamondReuseWithShuffle;
222 }
223 Value *getVector() const { return Vec; }
224 const ShuffleMask &getMask() const { return Mask; }
225};
226
227class Pack final : public LegalityResultWithReason {
228 Pack(ResultReason Reason)
230 friend class LegalityAnalysis; // For constructor.
231
232public:
233 static bool classof(const LegalityResult *From) {
234 return From->getSubclassID() == LegalityResultID::Pack;
235 }
236};
237
238/// Describes how to collect the values needed by each lane.
240public:
241 /// Describes how to get a value element. If the value is a vector then it
242 /// also provides the index to extract it from.
244 Value *V;
245 /// The index in `V` that the value can be extracted from.
246 /// This is nullopt if we need to use `V` as a whole.
247 std::optional<int> ExtractIdx;
248
249 public:
250 ExtractElementDescr(Value *V, int ExtractIdx)
251 : V(V), ExtractIdx(ExtractIdx) {}
252 ExtractElementDescr(Value *V) : V(V), ExtractIdx(std::nullopt) {}
253 Value *getValue() const { return V; }
254 bool needsExtract() const { return ExtractIdx.has_value(); }
255 int getExtractIdx() const { return *ExtractIdx; }
256 };
257
260
261public:
263 : Descrs(std::move(Descrs)) {}
264 /// If all elements come from a single vector input, then return that vector
265 /// and also the shuffle mask required to get them in order.
266 std::optional<std::pair<Value *, ShuffleMask>> getSingleInput() const {
267 const auto &Descr0 = *Descrs.begin();
268 Value *V0 = Descr0.getValue();
269 if (!Descr0.needsExtract())
270 return std::nullopt;
271 ShuffleMask::IndicesVecT MaskIndices;
272 MaskIndices.push_back(Descr0.getExtractIdx());
273 for (const auto &Descr : drop_begin(Descrs)) {
274 if (!Descr.needsExtract())
275 return std::nullopt;
276 if (Descr.getValue() != V0)
277 return std::nullopt;
278 MaskIndices.push_back(Descr.getExtractIdx());
279 }
280 return std::make_pair(V0, ShuffleMask(std::move(MaskIndices)));
281 }
282 bool hasVectorInputs() const {
283 return any_of(Descrs, [](const auto &D) { return D.needsExtract(); });
284 }
286 return Descrs;
287 }
288};
289
290/// Performs the legality analysis and returns a LegalityResult object.
292 Scheduler Sched;
293 /// Owns the legality result objects created by createLegalityResult().
295 /// Checks opcodes, types and other IR-specifics and returns a ResultReason
296 /// object if not vectorizable, or nullptr otherwise.
297 std::optional<ResultReason>
298 notVectorizableBasedOnOpcodesAndTypes(ArrayRef<Value *> Bndl);
299
300 ScalarEvolution &SE;
301 const DataLayout &DL;
302 InstrMaps &IMaps;
303
304 /// Finds how we can collect the values in \p Bndl from the vectorized or
305 /// non-vectorized code. It returns a map of the value we should extract from
306 /// and the corresponding shuffle mask we need to use.
307 CollectDescr getHowToCollectValues(ArrayRef<Value *> Bndl) const;
308
309public:
311 Context &Ctx, InstrMaps &IMaps)
312 : Sched(AA, Ctx), SE(SE), DL(DL), IMaps(IMaps) {}
313 /// A LegalityResult factory.
314 template <typename ResultT, typename... ArgsT>
315 ResultT &createLegalityResult(ArgsT... Args) {
316 ResultPool.push_back(std::unique_ptr<ResultT>(new ResultT(Args...)));
317 return cast<ResultT>(*ResultPool.back());
318 }
319 /// Checks if it's legal to vectorize the instructions in \p Bndl.
320 /// \Returns a LegalityResult object owned by LegalityAnalysis.
321 /// \p SkipScheduling skips the scheduler check and is only meant for testing.
322 // TODO: Try to remove the SkipScheduling argument by refactoring the tests.
324 bool SkipScheduling = false);
325 void clear();
326};
327
328} // namespace llvm::sandboxir
329
330#endif // LLVM_TRANSFORMS_VECTORIZE_SANDBOXVECTORIZER_LEGALITY_H
static SDValue Widen(SelectionDAG *CurDAG, SDValue N)
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
BlockVerifier::State From
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:622
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
raw_pwrite_stream & OS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
The main scalar evolution driver.
size_t size() const
Definition: SmallVector.h:78
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:573
void reserve(size_type N)
Definition: SmallVector.h:663
void push_back(const T &Elt)
Definition: SmallVector.h:413
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
Describes how to get a value element.
Definition: Legality.h:243
ExtractElementDescr(Value *V, int ExtractIdx)
Definition: Legality.h:250
Describes how to collect the values needed by each lane.
Definition: Legality.h:239
const SmallVector< ExtractElementDescr, 4 > & getDescrs() const
Definition: Legality.h:285
std::optional< std::pair< Value *, ShuffleMask > > getSingleInput() const
If all elements come from a single vector input, then return that vector and also the shuffle mask re...
Definition: Legality.h:266
bool hasVectorInputs() const
Definition: Legality.h:282
CollectDescr(SmallVectorImpl< ExtractElementDescr > &&Descrs)
Definition: Legality.h:262
const ShuffleMask & getMask() const
Definition: Legality.h:224
static bool classof(const LegalityResult *From)
Definition: Legality.h:220
Value * getVector() const
Definition: Legality.h:208
static bool classof(const LegalityResult *From)
Definition: Legality.h:205
Maps the original instructions to the vectorized instrs and the reverse.
Definition: InstrMaps.h:27
Performs the legality analysis and returns a LegalityResult object.
Definition: Legality.h:291
ResultT & createLegalityResult(ArgsT... Args)
A LegalityResult factory.
Definition: Legality.h:315
const LegalityResult & canVectorize(ArrayRef< Value * > Bndl, bool SkipScheduling=false)
Checks if it's legal to vectorize the instructions in Bndl.
Definition: Legality.cpp:209
LegalityAnalysis(AAResults &AA, ScalarEvolution &SE, const DataLayout &DL, Context &Ctx, InstrMaps &IMaps)
Definition: Legality.h:310
Base class for results with reason.
Definition: Legality.h:172
void print(raw_ostream &OS) const override
Definition: Legality.h:181
The legality outcome is represented by a class rather than an enum class because in some cases the le...
Definition: Legality.h:145
LegalityResult & operator=(const LegalityResult &)=delete
friend raw_ostream & operator<<(raw_ostream &OS, const LegalityResult &LR)
Definition: Legality.h:164
LLVM_DUMP_METHOD void dump() const
Definition: Legality.cpp:28
LegalityResultID getSubclassID() const
Definition: Legality.h:158
virtual void print(raw_ostream &OS) const
Definition: Legality.h:160
LegalityResult(LegalityResultID ID)
Only Legality can create LegalityResults.
Definition: Legality.h:149
LegalityResult(const LegalityResult &)=delete
We shouldn't need copies.
static bool classof(const LegalityResult *From)
Definition: Legality.h:233
The list scheduler.
Definition: Scheduler.h:111
ShuffleMask(std::initializer_list< int > Indices)
Definition: Legality.h:37
void print(raw_ostream &OS) const
Definition: Legality.h:72
bool isIdentity() const
\Returns true if the mask is a perfect identity mask with consecutive indices, i.e....
Definition: Legality.h:51
const_iterator end() const
Definition: Legality.h:66
ShuffleMask(SmallVectorImpl< int > &&Indices)
Definition: Legality.h:36
static ShuffleMask getIdentity(unsigned Sz)
Creates and returns an identity shuffle mask of size Sz.
Definition: Legality.h:42
LLVM_DUMP_METHOD void dump() const
Definition: Legality.cpp:23
bool operator==(const ShuffleMask &Other) const
Definition: Legality.h:58
bool operator!=(const ShuffleMask &Other) const
Definition: Legality.h:61
int operator[](int Idx) const
Definition: Legality.h:63
friend raw_ostream & operator<<(raw_ostream &OS, const ShuffleMask &Mask)
Definition: Legality.h:68
ShuffleMask(ArrayRef< int > Indices)
Definition: Legality.h:38
const_iterator begin() const
Definition: Legality.h:65
A SandboxIR Value has users. This is the base class.
Definition: Value.h:63
static bool classof(const LegalityResult *From)
Definition: Legality.h:193
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ DiamondReuse
‍Vectorize by combining scalars to a vector.
@ DiamondReuseWithShuffle
‍Don't generate new code, reuse existing vector.
@ Widen
‍Collect scalar values.
ResultReason
The reason for vectorizing or not vectorizing.
Definition: Legality.h:87
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:329
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
Definition: STLExtras.h:2448
void interleave(ForwardIterator begin, ForwardIterator end, UnaryFunctor each_fn, NullaryFunctor between_fn)
An STL-style algorithm similar to std::for_each that applies a second functor between every pair of e...
Definition: STLExtras.h:2169
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1746
@ Other
Any other memory.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1873
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
static const char * getVecReason(ResultReason Reason)
Definition: Legality.h:115
static const char * getLegalityResultID(LegalityResultID ID)
Definition: Legality.h:101