1//===- TypeSize.h - Wrapper around type sizes -------------------*- 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 provides a struct that can be used to query the size of IR types
10// which may be scalable vectors. It provides convenience operators so that
11// it can be used in much the same way as a single scalar value.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_SUPPORT_TYPESIZE_H
16#define LLVM_SUPPORT_TYPESIZE_H
17
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/Support/MathExtras.h"
20#include "llvm/Support/WithColor.h"
21
22#include <algorithm>
23#include <array>
24#include <cassert>
25#include <cstdint>
26#include <type_traits>
27
28namespace llvm {
29
30/// Reports a diagnostic message to indicate an invalid size request has been
31/// done on a scalable vector. This function may not return.
32void reportInvalidSizeRequest(const char *Msg);
33
34template <typename LeafTy> struct LinearPolyBaseTypeTraits {};
35
36//===----------------------------------------------------------------------===//
37// LinearPolyBase - a base class for linear polynomials with multiple
38// dimensions. This can e.g. be used to describe offsets that are have both a
39// fixed and scalable component.
40//===----------------------------------------------------------------------===//
41
42/// LinearPolyBase describes a linear polynomial:
43/// c0 * scale0 + c1 * scale1 + ... + cK * scaleK
44/// where the scale is implicit, so only the coefficients are encoded.
45template <typename LeafTy>
46class LinearPolyBase {
47public:
48 using ScalarTy = typename LinearPolyBaseTypeTraits<LeafTy>::ScalarTy;
49 static constexpr auto Dimensions = LinearPolyBaseTypeTraits<LeafTy>::Dimensions;
50 static_assert(Dimensions != std::numeric_limits<unsigned>::max(),
51 "Dimensions out of range");
52
53private:
54 std::array<ScalarTy, Dimensions> Coefficients;
55
56protected:
57 LinearPolyBase(ArrayRef<ScalarTy> Values) {
58 std::copy(Values.begin(), Values.end(), Coefficients.begin());
59 }
60
61public:
62 friend LeafTy &operator+=(LeafTy &LHS, const LeafTy &RHS) {
63 for (unsigned I=0; I<Dimensions; ++I)
64 LHS.Coefficients[I] += RHS.Coefficients[I];
65 return LHS;
66 }
67
68 friend LeafTy &operator-=(LeafTy &LHS, const LeafTy &RHS) {
69 for (unsigned I=0; I<Dimensions; ++I)
70 LHS.Coefficients[I] -= RHS.Coefficients[I];
71 return LHS;
72 }
73
74 friend LeafTy &operator*=(LeafTy &LHS, ScalarTy RHS) {
75 for (auto &C : LHS.Coefficients)
76 C *= RHS;
77 return LHS;
78 }
79
80 friend LeafTy operator+(const LeafTy &LHS, const LeafTy &RHS) {
81 LeafTy Copy = LHS;
82 return Copy += RHS;
83 }
84
85 friend LeafTy operator-(const LeafTy &LHS, const LeafTy &RHS) {
86 LeafTy Copy = LHS;
87 return Copy -= RHS;
88 }
89
90 friend LeafTy operator*(const LeafTy &LHS, ScalarTy RHS) {
91 LeafTy Copy = LHS;
92 return Copy *= RHS;
93 }
94
95 template <typename U = ScalarTy>
96 friend typename std::enable_if_t<std::is_signed<U>::value, LeafTy>
97 operator-(const LeafTy &LHS) {
98 LeafTy Copy = LHS;
99 return Copy *= -1;
100 }
101
102 bool operator==(const LinearPolyBase &RHS) const {
103 return std::equal(Coefficients.begin(), Coefficients.end(),
104 RHS.Coefficients.begin());
105 }
106
107 bool operator!=(const LinearPolyBase &RHS) const {
108 return !(*this == RHS);
109 }
110
111 bool isZero() const {
112 return all_of(Coefficients, [](const ScalarTy &C) { return C == 0; });
113 }
114 bool isNonZero() const { return !isZero(); }
115 explicit operator bool() const { return isNonZero(); }
116
117 ScalarTy getValue(unsigned Dim) const { return Coefficients[Dim]; }
118};
119
120//===----------------------------------------------------------------------===//
121// StackOffset - Represent an offset with named fixed and scalable components.
122//===----------------------------------------------------------------------===//
123
124class StackOffset;
125template <> struct LinearPolyBaseTypeTraits<StackOffset> {
126 using ScalarTy = int64_t;
127 static constexpr unsigned Dimensions = 2;
128};
129
130/// StackOffset is a class to represent an offset with 2 dimensions,
131/// named fixed and scalable, respectively. This class allows a value for both
132/// dimensions to depict e.g. "8 bytes and 16 scalable bytes", which is needed
133/// to represent stack offsets.
134class StackOffset : public LinearPolyBase<StackOffset> {
135protected:
136 StackOffset(ScalarTy Fixed, ScalarTy Scalable)
137 : LinearPolyBase<StackOffset>({Fixed, Scalable}) {}
138
139public:
140 StackOffset() : StackOffset({0, 0}) {}
141 StackOffset(const LinearPolyBase<StackOffset> &Other)
142 : LinearPolyBase<StackOffset>(Other) {}
143 static StackOffset getFixed(ScalarTy Fixed) { return {Fixed, 0}; }
144 static StackOffset getScalable(ScalarTy Scalable) { return {0, Scalable}; }
145 static StackOffset get(ScalarTy Fixed, ScalarTy Scalable) {
146 return {Fixed, Scalable};
147 }
148
149 ScalarTy getFixed() const { return this->getValue(0); }
150 ScalarTy getScalable() const { return this->getValue(1); }
151};
152
153//===----------------------------------------------------------------------===//
154// UnivariateLinearPolyBase - a base class for linear polynomials with multiple
155// dimensions, but where only one dimension can be set at any time.
156// This can e.g. be used to describe sizes that are either fixed or scalable.
157//===----------------------------------------------------------------------===//
158
159/// UnivariateLinearPolyBase is a base class for ElementCount and TypeSize.
160/// Like LinearPolyBase it tries to represent a linear polynomial
161/// where only one dimension can be set at any time, e.g.
162/// 0 * scale0 + 0 * scale1 + ... + cJ * scaleJ + ... + 0 * scaleK
163/// The dimension that is set is the univariate dimension.
164template <typename LeafTy>
165class UnivariateLinearPolyBase {
166public:
167 using ScalarTy = typename LinearPolyBaseTypeTraits<LeafTy>::ScalarTy;
168 static constexpr auto Dimensions = LinearPolyBaseTypeTraits<LeafTy>::Dimensions;
169 static_assert(Dimensions != std::numeric_limits<unsigned>::max(),
170 "Dimensions out of range");
171
172protected:
173 ScalarTy Value; // The value at the univeriate dimension.
174 unsigned UnivariateDim; // The univeriate dimension.
175
176 UnivariateLinearPolyBase(ScalarTy Val, unsigned UnivariateDim)
177 : Value(Val), UnivariateDim(UnivariateDim) {
178 assert(UnivariateDim < Dimensions && "Dimension out of range");
179 }
180
181 friend LeafTy &operator+=(LeafTy &LHS, const LeafTy &RHS) {
182 assert(LHS.UnivariateDim == RHS.UnivariateDim && "Invalid dimensions");
183 LHS.Value += RHS.Value;
184 return LHS;
185 }
186
187 friend LeafTy &operator-=(LeafTy &LHS, const LeafTy &RHS) {
188 assert(LHS.UnivariateDim == RHS.UnivariateDim && "Invalid dimensions");
189 LHS.Value -= RHS.Value;
190 return LHS;
191 }
192
193 friend LeafTy &operator*=(LeafTy &LHS, ScalarTy RHS) {
194 LHS.Value *= RHS;
195 return LHS;
196 }
197
198 friend LeafTy operator+(const LeafTy &LHS, const LeafTy &RHS) {
199 LeafTy Copy = LHS;
200 return Copy += RHS;
201 }
202
203 friend LeafTy operator-(const LeafTy &LHS, const LeafTy &RHS) {
204 LeafTy Copy = LHS;
205 return Copy -= RHS;
206 }
207
208 friend LeafTy operator*(const LeafTy &LHS, ScalarTy RHS) {
209 LeafTy Copy = LHS;
210 return Copy *= RHS;
211 }
212
213 template <typename U = ScalarTy>
214 friend typename std::enable_if<std::is_signed<U>::value, LeafTy>::type
215 operator-(const LeafTy &LHS) {
216 LeafTy Copy = LHS;
217 return Copy *= -1;
218 }
219
220public:
221 bool operator==(const UnivariateLinearPolyBase &RHS) const {
222 return Value == RHS.Value && UnivariateDim == RHS.UnivariateDim;
223 }
224
225 bool operator!=(const UnivariateLinearPolyBase &RHS) const {
226 return !(*this == RHS);
227 }
228
229 bool isZero() const { return !Value; }
230 bool isNonZero() const { return !isZero(); }
231 explicit operator bool() const { return isNonZero(); }
232 ScalarTy getValue() const { return Value; }
233 ScalarTy getValue(unsigned Dim) const {
234 return Dim == UnivariateDim ? Value : 0;
235 }
236
237 /// Add \p RHS to the value at the univariate dimension.
238 LeafTy getWithIncrement(ScalarTy RHS) const {
239 return static_cast<LeafTy>(
240 UnivariateLinearPolyBase(Value + RHS, UnivariateDim));
241 }
242
243 /// Subtract \p RHS from the value at the univariate dimension.
244 LeafTy getWithDecrement(ScalarTy RHS) const {
245 return static_cast<LeafTy>(
246 UnivariateLinearPolyBase(Value - RHS, UnivariateDim));
247 }
248};
249
250
251//===----------------------------------------------------------------------===//
252// LinearPolySize - base class for fixed- or scalable sizes.
253// ^ ^
254// | |
255// | +----- ElementCount - Leaf class to represent an element count
256// | (vscale x unsigned)
257// |
258// +-------- TypeSize - Leaf class to represent a type size
259// (vscale x uint64_t)
260//===----------------------------------------------------------------------===//
261
262/// LinearPolySize is a base class to represent sizes. It is either
263/// fixed-sized or it is scalable-sized, but it cannot be both.
264template <typename LeafTy>
265class LinearPolySize : public UnivariateLinearPolyBase<LeafTy> {
266 // Make the parent class a friend, so that it can access the protected
267 // conversion/copy-constructor for UnivariatePolyBase<LeafTy> ->
268 // LinearPolySize<LeafTy>.
269 friend class UnivariateLinearPolyBase<LeafTy>;
270
271public:
272 using ScalarTy = typename UnivariateLinearPolyBase<LeafTy>::ScalarTy;
273 enum Dims : unsigned { FixedDim = 0, ScalableDim = 1 };
274
275protected:
276 LinearPolySize(ScalarTy MinVal, Dims D)
277 : UnivariateLinearPolyBase<LeafTy>(MinVal, D) {}
278
279 LinearPolySize(const UnivariateLinearPolyBase<LeafTy> &V)
280 : UnivariateLinearPolyBase<LeafTy>(V) {}
281
282public:
283
284 static LeafTy getFixed(ScalarTy MinVal) {
285 return static_cast<LeafTy>(LinearPolySize(MinVal, FixedDim));
286 }
287 static LeafTy getScalable(ScalarTy MinVal) {
288 return static_cast<LeafTy>(LinearPolySize(MinVal, ScalableDim));
289 }
290 static LeafTy get(ScalarTy MinVal, bool Scalable) {
291 return static_cast<LeafTy>(
292 LinearPolySize(MinVal, Scalable ? ScalableDim : FixedDim));
293 }
294 static LeafTy getNull() { return get(0, false); }
295
296 /// Returns the minimum value this size can represent.
297 ScalarTy getKnownMinValue() const { return this->getValue(); }
298 /// Returns whether the size is scaled by a runtime quantity (vscale).
299 bool isScalable() const { return this->UnivariateDim == ScalableDim; }
300 /// A return value of true indicates we know at compile time that the number
301 /// of elements (vscale * Min) is definitely even. However, returning false
302 /// does not guarantee that the total number of elements is odd.
303 bool isKnownEven() const { return (getKnownMinValue() & 0x1) == 0; }
304 /// This function tells the caller whether the element count is known at
305 /// compile time to be a multiple of the scalar value RHS.
306 bool isKnownMultipleOf(ScalarTy RHS) const {
307 return getKnownMinValue() % RHS == 0;
308 }
309
310 // Return the minimum value with the assumption that the count is exact.
311 // Use in places where a scalable count doesn't make sense (e.g. non-vector
312 // types, or vectors in backends which don't support scalable vectors).
313 ScalarTy getFixedValue() const {
314 assert(!isScalable() &&
315 "Request for a fixed element count on a scalable object");
316 return getKnownMinValue();
317 }
318
319 // For some cases, size ordering between scalable and fixed size types cannot
320 // be determined at compile time, so such comparisons aren't allowed.
321 //
322 // e.g. <vscale x 2 x i16> could be bigger than <4 x i32> with a runtime
323 // vscale >= 5, equal sized with a vscale of 4, and smaller with
324 // a vscale <= 3.
325 //
326 // All the functions below make use of the fact vscale is always >= 1, which
327 // means that <vscale x 4 x i32> is guaranteed to be >= <4 x i32>, etc.
328
329 static bool isKnownLT(const LinearPolySize &LHS, const LinearPolySize &RHS) {
330 if (!LHS.isScalable() || RHS.isScalable())
331 return LHS.getKnownMinValue() < RHS.getKnownMinValue();
332 return false;
333 }
334
335 static bool isKnownGT(const LinearPolySize &LHS, const LinearPolySize &RHS) {
336 if (LHS.isScalable() || !RHS.isScalable())
337 return LHS.getKnownMinValue() > RHS.getKnownMinValue();
338 return false;
339 }
340
341 static bool isKnownLE(const LinearPolySize &LHS, const LinearPolySize &RHS) {
342 if (!LHS.isScalable() || RHS.isScalable())
343 return LHS.getKnownMinValue() <= RHS.getKnownMinValue();
344 return false;
345 }
346
347 static bool isKnownGE(const LinearPolySize &LHS, const LinearPolySize &RHS) {
348 if (LHS.isScalable() || !RHS.isScalable())
349 return LHS.getKnownMinValue() >= RHS.getKnownMinValue();
350 return false;
351 }
352
353 /// We do not provide the '/' operator here because division for polynomial
354 /// types does not work in the same way as for normal integer types. We can
355 /// only divide the minimum value (or coefficient) by RHS, which is not the
356 /// same as
357 /// (Min * Vscale) / RHS
358 /// The caller is recommended to use this function in combination with
359 /// isKnownMultipleOf(RHS), which lets the caller know if it's possible to
360 /// perform a lossless divide by RHS.
361 LeafTy divideCoefficientBy(ScalarTy RHS) const {
362 return static_cast<LeafTy>(
363 LinearPolySize::get(getKnownMinValue() / RHS, isScalable()));
364 }
365
366 LeafTy coefficientNextPowerOf2() const {
367 return static_cast<LeafTy>(LinearPolySize::get(
368 static_cast<ScalarTy>(llvm::NextPowerOf2(getKnownMinValue())),
369 isScalable()));
370 }
371
372 /// Printing function.
373 void print(raw_ostream &OS) const {
374 if (isScalable())
375 OS << "vscale x ";
376 OS << getKnownMinValue();
377 }
378};
379
380class ElementCount;
381template <> struct LinearPolyBaseTypeTraits<ElementCount> {
382 using ScalarTy = unsigned;
383 static constexpr unsigned Dimensions = 2;
384};
385
386class ElementCount : public LinearPolySize<ElementCount> {
387public:
388 ElementCount() : LinearPolySize(LinearPolySize::getNull()) {}
389
390 ElementCount(const LinearPolySize<ElementCount> &V) : LinearPolySize(V) {}
391
392 /// Counting predicates.
393 ///
394 ///@{ Number of elements..
395 /// Exactly one element.
396 bool isScalar() const { return !isScalable() && getKnownMinValue() == 1; }
397 /// One or more elements.
398 bool isVector() const {
399 return (isScalable() && getKnownMinValue() != 0) || getKnownMinValue() > 1;
400 }
401 ///@}
402};
403
404// This class is used to represent the size of types. If the type is of fixed
405class TypeSize;
406template <> struct LinearPolyBaseTypeTraits<TypeSize> {
407 using ScalarTy = uint64_t;
408 static constexpr unsigned Dimensions = 2;
409};
410
411// TODO: Most functionality in this class will gradually be phased out
412// so it will resemble LinearPolySize as much as possible.
413//
414// TypeSize is used to represent the size of types. If the type is of fixed
415// size, it will represent the exact size. If the type is a scalable vector,
416// it will represent the known minimum size.
417class TypeSize : public LinearPolySize<TypeSize> {
418public:
419 TypeSize(const LinearPolySize<TypeSize> &V) : LinearPolySize(V) {}
420 TypeSize(ScalarTy MinVal, bool IsScalable)
421 : LinearPolySize(LinearPolySize::get(MinVal, IsScalable)) {}
422
423 static TypeSize Fixed(ScalarTy MinVal) { return TypeSize(MinVal, false); }
424 static TypeSize Scalable(ScalarTy MinVal) { return TypeSize(MinVal, true); }
425
426 ScalarTy getFixedSize() const { return getFixedValue(); }
427 ScalarTy getKnownMinSize() const { return getKnownMinValue(); }
428
429 // All code for this class below this point is needed because of the
430 // temporary implicit conversion to uint64_t. The operator overloads are
431 // needed because otherwise the conversion of the parent class
432 // UnivariateLinearPolyBase -> TypeSize is ambiguous.
433 // TODO: Remove the implicit conversion.
434
435 // Casts to a uint64_t if this is a fixed-width size.
436 //
437 // This interface is deprecated and will be removed in a future version
438 // of LLVM in favour of upgrading uses that rely on this implicit conversion
439 // to uint64_t. Calls to functions that return a TypeSize should use the
440 // proper interfaces to TypeSize.
441 // In practice this is mostly calls to MVT/EVT::getSizeInBits().
442 //
443 // To determine how to upgrade the code:
444 //
445 // if (<algorithm works for both scalable and fixed-width vectors>)
446 // use getKnownMinValue()
447 // else if (<algorithm works only for fixed-width vectors>) {
448 // if <algorithm can be adapted for both scalable and fixed-width vectors>
449 // update the algorithm and use getKnownMinValue()
450 // else
451 // bail out early for scalable vectors and use getFixedValue()
452 // }
453 operator ScalarTy() const;
454
455 // Additional operators needed to avoid ambiguous parses
456 // because of the implicit conversion hack.
457 friend TypeSize operator*(const TypeSize &LHS, const int RHS) {
458 return LHS * (ScalarTy)RHS;
459 }
460 friend TypeSize operator*(const TypeSize &LHS, const unsigned RHS) {
461 return LHS * (ScalarTy)RHS;
462 }
463 friend TypeSize operator*(const TypeSize &LHS, const int64_t RHS) {
464 return LHS * (ScalarTy)RHS;
465 }
466 friend TypeSize operator*(const int LHS, const TypeSize &RHS) {
467 return RHS * LHS;
468 }
469 friend TypeSize operator*(const unsigned LHS, const TypeSize &RHS) {
470 return RHS * LHS;
471 }
472 friend TypeSize operator*(const int64_t LHS, const TypeSize &RHS) {
473 return RHS * LHS;
474 }
475 friend TypeSize operator*(const uint64_t LHS, const TypeSize &RHS) {
476 return RHS * LHS;
477 }
478};
479
480//===----------------------------------------------------------------------===//
481// Utilities
482//===----------------------------------------------------------------------===//
483
484/// Returns a TypeSize with a known minimum size that is the next integer
485/// (mod 2**64) that is greater than or equal to \p Value and is a multiple
486/// of \p Align. \p Align must be non-zero.
487///
488/// Similar to the alignTo functions in MathExtras.h
489inline TypeSize alignTo(TypeSize Size, uint64_t Align) {
490 assert(Align != 0u && "Align must be non-zero");
491 return {(Size.getKnownMinValue() + Align - 1) / Align * Align,
492 Size.isScalable()};
493}
494
495/// Stream operator function for `LinearPolySize`.
496template <typename LeafTy>
497inline raw_ostream &operator<<(raw_ostream &OS,
498 const LinearPolySize<LeafTy> &PS) {
499 PS.print(OS);
500 return OS;
501}
502
503template <typename T> struct DenseMapInfo;
504template <> struct DenseMapInfo<ElementCount> {
505 static inline ElementCount getEmptyKey() {
506 return ElementCount::getScalable(~0U);
507 }
508 static inline ElementCount getTombstoneKey() {
509 return ElementCount::getFixed(~0U - 1);
510 }
511 static unsigned getHashValue(const ElementCount &EltCnt) {
512 unsigned HashVal = EltCnt.getKnownMinValue() * 37U;
513 if (EltCnt.isScalable())
514 return (HashVal - 1U);
515
516 return HashVal;
517 }
518
519 static bool isEqual(const ElementCount &LHS, const ElementCount &RHS) {
520 return LHS == RHS;
521 }
522};
523
524} // end namespace llvm
525
526#endif // LLVM_SUPPORT_TYPESIZE_H
527