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/raw_ostream.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(unsigned Dim) const {
233 return Dim == UnivariateDim ? Value : 0;
234 }
235
236 /// Add \p RHS to the value at the univariate dimension.
237 LeafTy getWithIncrement(ScalarTy RHS) const {
238 return static_cast<LeafTy>(
239 UnivariateLinearPolyBase(Value + RHS, UnivariateDim));
240 }
241
242 /// Subtract \p RHS from the value at the univariate dimension.
243 LeafTy getWithDecrement(ScalarTy RHS) const {
244 return static_cast<LeafTy>(
245 UnivariateLinearPolyBase(Value - RHS, UnivariateDim));
246 }
247};
248
249
250//===----------------------------------------------------------------------===//
251// LinearPolySize - base class for fixed- or scalable sizes.
252// ^ ^
253// | |
254// | +----- ElementCount - Leaf class to represent an element count
255// | (vscale x unsigned)
256// |
257// +-------- TypeSize - Leaf class to represent a type size
258// (vscale x uint64_t)
259//===----------------------------------------------------------------------===//
260
261/// LinearPolySize is a base class to represent sizes. It is either
262/// fixed-sized or it is scalable-sized, but it cannot be both.
263template <typename LeafTy>
264class LinearPolySize : public UnivariateLinearPolyBase<LeafTy> {
265 // Make the parent class a friend, so that it can access the protected
266 // conversion/copy-constructor for UnivariatePolyBase<LeafTy> ->
267 // LinearPolySize<LeafTy>.
268 friend class UnivariateLinearPolyBase<LeafTy>;
269
270public:
271 using ScalarTy = typename UnivariateLinearPolyBase<LeafTy>::ScalarTy;
272 enum Dims : unsigned { FixedDim = 0, ScalableDim = 1 };
273
274protected:
275 LinearPolySize(ScalarTy MinVal, Dims D)
276 : UnivariateLinearPolyBase<LeafTy>(MinVal, D) {}
277
278 LinearPolySize(const UnivariateLinearPolyBase<LeafTy> &V)
279 : UnivariateLinearPolyBase<LeafTy>(V) {}
280
281public:
282
283 static LeafTy getFixed(ScalarTy MinVal) {
284 return static_cast<LeafTy>(LinearPolySize(MinVal, FixedDim));
285 }
286 static LeafTy getScalable(ScalarTy MinVal) {
287 return static_cast<LeafTy>(LinearPolySize(MinVal, ScalableDim));
288 }
289 static LeafTy get(ScalarTy MinVal, bool Scalable) {
290 return static_cast<LeafTy>(
291 LinearPolySize(MinVal, Scalable ? ScalableDim : FixedDim));
292 }
293 static LeafTy getNull() { return get(0, false); }
294
295 /// Returns the minimum value this size can represent.
296 ScalarTy getKnownMinValue() const { return this->Value; }
297 /// Returns whether the size is scaled by a runtime quantity (vscale).
298 bool isScalable() const { return this->UnivariateDim == ScalableDim; }
299 /// A return value of true indicates we know at compile time that the number
300 /// of elements (vscale * Min) is definitely even. However, returning false
301 /// does not guarantee that the total number of elements is odd.
302 bool isKnownEven() const { return (getKnownMinValue() & 0x1) == 0; }
303 /// This function tells the caller whether the element count is known at
304 /// compile time to be a multiple of the scalar value RHS.
305 bool isKnownMultipleOf(ScalarTy RHS) const {
306 return getKnownMinValue() % RHS == 0;
307 }
308
309 // Return the minimum value with the assumption that the count is exact.
310 // Use in places where a scalable count doesn't make sense (e.g. non-vector
311 // types, or vectors in backends which don't support scalable vectors).
312 ScalarTy getFixedValue() const {
313 assert(!isScalable() &&
314 "Request for a fixed element count on a scalable object");
315 return getKnownMinValue();
316 }
317
318 // For some cases, size ordering between scalable and fixed size types cannot
319 // be determined at compile time, so such comparisons aren't allowed.
320 //
321 // e.g. <vscale x 2 x i16> could be bigger than <4 x i32> with a runtime
322 // vscale >= 5, equal sized with a vscale of 4, and smaller with
323 // a vscale <= 3.
324 //
325 // All the functions below make use of the fact vscale is always >= 1, which
326 // means that <vscale x 4 x i32> is guaranteed to be >= <4 x i32>, etc.
327
328 static bool isKnownLT(const LinearPolySize &LHS, const LinearPolySize &RHS) {
329 if (!LHS.isScalable() || RHS.isScalable())
330 return LHS.getKnownMinValue() < RHS.getKnownMinValue();
331 return false;
332 }
333
334 static bool isKnownGT(const LinearPolySize &LHS, const LinearPolySize &RHS) {
335 if (LHS.isScalable() || !RHS.isScalable())
336 return LHS.getKnownMinValue() > RHS.getKnownMinValue();
337 return false;
338 }
339
340 static bool isKnownLE(const LinearPolySize &LHS, const LinearPolySize &RHS) {
341 if (!LHS.isScalable() || RHS.isScalable())
342 return LHS.getKnownMinValue() <= RHS.getKnownMinValue();
343 return false;
344 }
345
346 static bool isKnownGE(const LinearPolySize &LHS, const LinearPolySize &RHS) {
347 if (LHS.isScalable() || !RHS.isScalable())
348 return LHS.getKnownMinValue() >= RHS.getKnownMinValue();
349 return false;
350 }
351
352 /// We do not provide the '/' operator here because division for polynomial
353 /// types does not work in the same way as for normal integer types. We can
354 /// only divide the minimum value (or coefficient) by RHS, which is not the
355 /// same as
356 /// (Min * Vscale) / RHS
357 /// The caller is recommended to use this function in combination with
358 /// isKnownMultipleOf(RHS), which lets the caller know if it's possible to
359 /// perform a lossless divide by RHS.
360 LeafTy divideCoefficientBy(ScalarTy RHS) const {
361 return static_cast<LeafTy>(
362 LinearPolySize::get(getKnownMinValue() / RHS, isScalable()));
363 }
364
365 LeafTy multiplyCoefficientBy(ScalarTy RHS) const {
366 return static_cast<LeafTy>(
367 LinearPolySize::get(getKnownMinValue() * RHS, isScalable()));
368 }
369
370 LeafTy coefficientNextPowerOf2() const {
371 return static_cast<LeafTy>(LinearPolySize::get(
372 static_cast<ScalarTy>(llvm::NextPowerOf2(getKnownMinValue())),
373 isScalable()));
374 }
375
376 /// Returns true if there exists a value X where RHS.multiplyCoefficientBy(X)
377 /// will result in a value whose size matches our own.
378 bool hasKnownScalarFactor(const LinearPolySize &RHS) const {
379 return isScalable() == RHS.isScalable() &&
380 getKnownMinValue() % RHS.getKnownMinValue() == 0;
381 }
382
383 /// Returns a value X where RHS.multiplyCoefficientBy(X) will result in a
384 /// value whose size matches our own.
385 ScalarTy getKnownScalarFactor(const LinearPolySize &RHS) const {
386 assert(hasKnownScalarFactor(RHS) && "Expected RHS to be a known factor!");
387 return getKnownMinValue() / RHS.getKnownMinValue();
388 }
389
390 /// Printing function.
391 void print(raw_ostream &OS) const {
392 if (isScalable())
393 OS << "vscale x ";
394 OS << getKnownMinValue();
395 }
396};
397
398class ElementCount;
399template <> struct LinearPolyBaseTypeTraits<ElementCount> {
400 using ScalarTy = unsigned;
401 static constexpr unsigned Dimensions = 2;
402};
403
404class ElementCount : public LinearPolySize<ElementCount> {
405public:
406 ElementCount() : LinearPolySize(LinearPolySize::getNull()) {}
407
408 ElementCount(const LinearPolySize<ElementCount> &V) : LinearPolySize(V) {}
409
410 /// Counting predicates.
411 ///
412 ///@{ Number of elements..
413 /// Exactly one element.
414 bool isScalar() const { return !isScalable() && getKnownMinValue() == 1; }
415 /// One or more elements.
416 bool isVector() const {
417 return (isScalable() && getKnownMinValue() != 0) || getKnownMinValue() > 1;
418 }
419 ///@}
420};
421
422// This class is used to represent the size of types. If the type is of fixed
423class TypeSize;
424template <> struct LinearPolyBaseTypeTraits<TypeSize> {
425 using ScalarTy = uint64_t;
426 static constexpr unsigned Dimensions = 2;
427};
428
429// TODO: Most functionality in this class will gradually be phased out
430// so it will resemble LinearPolySize as much as possible.
431//
432// TypeSize is used to represent the size of types. If the type is of fixed
433// size, it will represent the exact size. If the type is a scalable vector,
434// it will represent the known minimum size.
435class TypeSize : public LinearPolySize<TypeSize> {
436public:
437 TypeSize(const LinearPolySize<TypeSize> &V) : LinearPolySize(V) {}
438 TypeSize(ScalarTy MinVal, bool IsScalable)
439 : LinearPolySize(LinearPolySize::get(MinVal, IsScalable)) {}
440
441 static TypeSize Fixed(ScalarTy MinVal) { return TypeSize(MinVal, false); }
442 static TypeSize Scalable(ScalarTy MinVal) { return TypeSize(MinVal, true); }
443
444 ScalarTy getFixedSize() const { return getFixedValue(); }
445 ScalarTy getKnownMinSize() const { return getKnownMinValue(); }
446
447 // All code for this class below this point is needed because of the
448 // temporary implicit conversion to uint64_t. The operator overloads are
449 // needed because otherwise the conversion of the parent class
450 // UnivariateLinearPolyBase -> TypeSize is ambiguous.
451 // TODO: Remove the implicit conversion.
452
453 // Casts to a uint64_t if this is a fixed-width size.
454 //
455 // This interface is deprecated and will be removed in a future version
456 // of LLVM in favour of upgrading uses that rely on this implicit conversion
457 // to uint64_t. Calls to functions that return a TypeSize should use the
458 // proper interfaces to TypeSize.
459 // In practice this is mostly calls to MVT/EVT::getSizeInBits().
460 //
461 // To determine how to upgrade the code:
462 //
463 // if (<algorithm works for both scalable and fixed-width vectors>)
464 // use getKnownMinValue()
465 // else if (<algorithm works only for fixed-width vectors>) {
466 // if <algorithm can be adapted for both scalable and fixed-width vectors>
467 // update the algorithm and use getKnownMinValue()
468 // else
469 // bail out early for scalable vectors and use getFixedValue()
470 // }
471 operator ScalarTy() const;
472
473 // Additional operators needed to avoid ambiguous parses
474 // because of the implicit conversion hack.
475 friend TypeSize operator*(const TypeSize &LHS, const int RHS) {
476 return LHS * (ScalarTy)RHS;
477 }
478 friend TypeSize operator*(const TypeSize &LHS, const unsigned RHS) {
479 return LHS * (ScalarTy)RHS;
480 }
481 friend TypeSize operator*(const TypeSize &LHS, const int64_t RHS) {
482 return LHS * (ScalarTy)RHS;
483 }
484 friend TypeSize operator*(const int LHS, const TypeSize &RHS) {
485 return RHS * LHS;
486 }
487 friend TypeSize operator*(const unsigned LHS, const TypeSize &RHS) {
488 return RHS * LHS;
489 }
490 friend TypeSize operator*(const int64_t LHS, const TypeSize &RHS) {
491 return RHS * LHS;
492 }
493 friend TypeSize operator*(const uint64_t LHS, const TypeSize &RHS) {
494 return RHS * LHS;
495 }
496};
497
498//===----------------------------------------------------------------------===//
499// Utilities
500//===----------------------------------------------------------------------===//
501
502/// Returns a TypeSize with a known minimum size that is the next integer
503/// (mod 2**64) that is greater than or equal to \p Value and is a multiple
504/// of \p Align. \p Align must be non-zero.
505///
506/// Similar to the alignTo functions in MathExtras.h
507inline TypeSize alignTo(TypeSize Size, uint64_t Align) {
508 assert(Align != 0u && "Align must be non-zero");
509 return {(Size.getKnownMinValue() + Align - 1) / Align * Align,
510 Size.isScalable()};
511}
512
513/// Stream operator function for `LinearPolySize`.
514template <typename LeafTy>
515inline raw_ostream &operator<<(raw_ostream &OS,
516 const LinearPolySize<LeafTy> &PS) {
517 PS.print(OS);
518 return OS;
519}
520
521template <> struct DenseMapInfo<ElementCount, void> {
522 static inline ElementCount getEmptyKey() {
523 return ElementCount::getScalable(~0U);
524 }
525 static inline ElementCount getTombstoneKey() {
526 return ElementCount::getFixed(~0U - 1);
527 }
528 static unsigned getHashValue(const ElementCount &EltCnt) {
529 unsigned HashVal = EltCnt.getKnownMinValue() * 37U;
530 if (EltCnt.isScalable())
531 return (HashVal - 1U);
532
533 return HashVal;
534 }
535
536 static bool isEqual(const ElementCount &LHS, const ElementCount &RHS) {
537 return LHS == RHS;
538 }
539};
540
541} // end namespace llvm
542
543#endif // LLVM_SUPPORT_TYPESIZE_H
544

source code of llvm/include/llvm/Support/TypeSize.h