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/Compiler.h"
20 #include "llvm/Support/MathExtras.h"
21 #include "llvm/Support/raw_ostream.h"
22 
23 #include <algorithm>
24 #include <array>
25 #include <cassert>
26 #include <cstdint>
27 #include <type_traits>
28 
29 namespace llvm {
30 
31 /// Reports a diagnostic message to indicate an invalid size request has been
32 /// done on a scalable vector. This function may not return.
33 void reportInvalidSizeRequest(const char *Msg);
34 
35 /// StackOffset holds a fixed and a scalable offset in bytes.
36 class StackOffset {
37   int64_t Fixed = 0;
38   int64_t Scalable = 0;
39 
StackOffset(int64_t Fixed,int64_t Scalable)40   StackOffset(int64_t Fixed, int64_t Scalable)
41       : Fixed(Fixed), Scalable(Scalable) {}
42 
43 public:
44   StackOffset() = default;
getFixed(int64_t Fixed)45   static StackOffset getFixed(int64_t Fixed) { return {Fixed, 0}; }
getScalable(int64_t Scalable)46   static StackOffset getScalable(int64_t Scalable) { return {0, Scalable}; }
get(int64_t Fixed,int64_t Scalable)47   static StackOffset get(int64_t Fixed, int64_t Scalable) {
48     return {Fixed, Scalable};
49   }
50 
51   /// Returns the fixed component of the stack.
getFixed()52   int64_t getFixed() const { return Fixed; }
53 
54   /// Returns the scalable component of the stack.
getScalable()55   int64_t getScalable() const { return Scalable; }
56 
57   // Arithmetic operations.
58   StackOffset operator+(const StackOffset &RHS) const {
59     return {Fixed + RHS.Fixed, Scalable + RHS.Scalable};
60   }
61   StackOffset operator-(const StackOffset &RHS) const {
62     return {Fixed - RHS.Fixed, Scalable - RHS.Scalable};
63   }
64   StackOffset &operator+=(const StackOffset &RHS) {
65     Fixed += RHS.Fixed;
66     Scalable += RHS.Scalable;
67     return *this;
68   }
69   StackOffset &operator-=(const StackOffset &RHS) {
70     Fixed -= RHS.Fixed;
71     Scalable -= RHS.Scalable;
72     return *this;
73   }
74   StackOffset operator-() const { return {-Fixed, -Scalable}; }
75 
76   // Equality comparisons.
77   bool operator==(const StackOffset &RHS) const {
78     return Fixed == RHS.Fixed && Scalable == RHS.Scalable;
79   }
80   bool operator!=(const StackOffset &RHS) const {
81     return Fixed != RHS.Fixed || Scalable != RHS.Scalable;
82   }
83 
84   // The bool operator returns true iff any of the components is non zero.
85   explicit operator bool() const { return Fixed != 0 || Scalable != 0; }
86 };
87 
88 namespace details {
89 
90 // Base class for ElementCount and TypeSize below.
91 template <typename LeafTy, typename ValueTy> class FixedOrScalableQuantity {
92 public:
93   using ScalarTy = ValueTy;
94 
95 protected:
96   ScalarTy Quantity = 0;
97   bool Scalable = false;
98 
99   constexpr FixedOrScalableQuantity() = default;
FixedOrScalableQuantity(ScalarTy Quantity,bool Scalable)100   constexpr FixedOrScalableQuantity(ScalarTy Quantity, bool Scalable)
101       : Quantity(Quantity), Scalable(Scalable) {}
102 
103   friend constexpr LeafTy &operator+=(LeafTy &LHS, const LeafTy &RHS) {
104     assert(LHS.Scalable == RHS.Scalable && "Incompatible types");
105     LHS.Quantity += RHS.Quantity;
106     return LHS;
107   }
108 
109   friend constexpr LeafTy &operator-=(LeafTy &LHS, const LeafTy &RHS) {
110     assert(LHS.Scalable == RHS.Scalable && "Incompatible types");
111     LHS.Quantity -= RHS.Quantity;
112     return LHS;
113   }
114 
115   friend constexpr LeafTy &operator*=(LeafTy &LHS, ScalarTy RHS) {
116     LHS.Quantity *= RHS;
117     return LHS;
118   }
119 
120   friend constexpr LeafTy operator+(const LeafTy &LHS, const LeafTy &RHS) {
121     LeafTy Copy = LHS;
122     return Copy += RHS;
123   }
124 
125   friend constexpr LeafTy operator-(const LeafTy &LHS, const LeafTy &RHS) {
126     LeafTy Copy = LHS;
127     return Copy -= RHS;
128   }
129 
130   friend constexpr LeafTy operator*(const LeafTy &LHS, ScalarTy RHS) {
131     LeafTy Copy = LHS;
132     return Copy *= RHS;
133   }
134 
135   template <typename U = ScalarTy>
136   friend constexpr std::enable_if_t<std::is_signed<U>::value, LeafTy>
137   operator-(const LeafTy &LHS) {
138     LeafTy Copy = LHS;
139     return Copy *= -1;
140   }
141 
142 public:
143   constexpr bool operator==(const FixedOrScalableQuantity &RHS) const {
144     return Quantity == RHS.Quantity && Scalable == RHS.Scalable;
145   }
146 
147   constexpr bool operator!=(const FixedOrScalableQuantity &RHS) const {
148     return Quantity != RHS.Quantity || Scalable != RHS.Scalable;
149   }
150 
isZero()151   constexpr bool isZero() const { return Quantity == 0; }
152 
isNonZero()153   constexpr bool isNonZero() const { return Quantity != 0; }
154 
155   explicit operator bool() const { return isNonZero(); }
156 
157   /// Add \p RHS to the underlying quantity.
getWithIncrement(ScalarTy RHS)158   constexpr LeafTy getWithIncrement(ScalarTy RHS) const {
159     return LeafTy::get(Quantity + RHS, Scalable);
160   }
161 
162   /// Returns the minimum value this quantity can represent.
getKnownMinValue()163   constexpr ScalarTy getKnownMinValue() const { return Quantity; }
164 
165   /// Returns whether the quantity is scaled by a runtime quantity (vscale).
isScalable()166   constexpr bool isScalable() const { return Scalable; }
167 
168   /// A return value of true indicates we know at compile time that the number
169   /// of elements (vscale * Min) is definitely even. However, returning false
170   /// does not guarantee that the total number of elements is odd.
isKnownEven()171   constexpr bool isKnownEven() const { return (getKnownMinValue() & 0x1) == 0; }
172 
173   /// This function tells the caller whether the element count is known at
174   /// compile time to be a multiple of the scalar value RHS.
isKnownMultipleOf(ScalarTy RHS)175   constexpr bool isKnownMultipleOf(ScalarTy RHS) const {
176     return getKnownMinValue() % RHS == 0;
177   }
178 
179   // Return the minimum value with the assumption that the count is exact.
180   // Use in places where a scalable count doesn't make sense (e.g. non-vector
181   // types, or vectors in backends which don't support scalable vectors).
getFixedValue()182   constexpr ScalarTy getFixedValue() const {
183     assert(!isScalable() &&
184            "Request for a fixed element count on a scalable object");
185     return getKnownMinValue();
186   }
187 
188   // For some cases, quantity ordering between scalable and fixed quantity types
189   // cannot be determined at compile time, so such comparisons aren't allowed.
190   //
191   // e.g. <vscale x 2 x i16> could be bigger than <4 x i32> with a runtime
192   // vscale >= 5, equal sized with a vscale of 4, and smaller with
193   // a vscale <= 3.
194   //
195   // All the functions below make use of the fact vscale is always >= 1, which
196   // means that <vscale x 4 x i32> is guaranteed to be >= <4 x i32>, etc.
197 
isKnownLT(const FixedOrScalableQuantity & LHS,const FixedOrScalableQuantity & RHS)198   static constexpr bool isKnownLT(const FixedOrScalableQuantity &LHS,
199                                   const FixedOrScalableQuantity &RHS) {
200     if (!LHS.isScalable() || RHS.isScalable())
201       return LHS.getKnownMinValue() < RHS.getKnownMinValue();
202     return false;
203   }
204 
isKnownGT(const FixedOrScalableQuantity & LHS,const FixedOrScalableQuantity & RHS)205   static constexpr bool isKnownGT(const FixedOrScalableQuantity &LHS,
206                                   const FixedOrScalableQuantity &RHS) {
207     if (LHS.isScalable() || !RHS.isScalable())
208       return LHS.getKnownMinValue() > RHS.getKnownMinValue();
209     return false;
210   }
211 
isKnownLE(const FixedOrScalableQuantity & LHS,const FixedOrScalableQuantity & RHS)212   static constexpr bool isKnownLE(const FixedOrScalableQuantity &LHS,
213                                   const FixedOrScalableQuantity &RHS) {
214     if (!LHS.isScalable() || RHS.isScalable())
215       return LHS.getKnownMinValue() <= RHS.getKnownMinValue();
216     return false;
217   }
218 
isKnownGE(const FixedOrScalableQuantity & LHS,const FixedOrScalableQuantity & RHS)219   static constexpr bool isKnownGE(const FixedOrScalableQuantity &LHS,
220                                   const FixedOrScalableQuantity &RHS) {
221     if (LHS.isScalable() || !RHS.isScalable())
222       return LHS.getKnownMinValue() >= RHS.getKnownMinValue();
223     return false;
224   }
225 
226   /// We do not provide the '/' operator here because division for polynomial
227   /// types does not work in the same way as for normal integer types. We can
228   /// only divide the minimum value (or coefficient) by RHS, which is not the
229   /// same as
230   ///   (Min * Vscale) / RHS
231   /// The caller is recommended to use this function in combination with
232   /// isKnownMultipleOf(RHS), which lets the caller know if it's possible to
233   /// perform a lossless divide by RHS.
divideCoefficientBy(ScalarTy RHS)234   constexpr LeafTy divideCoefficientBy(ScalarTy RHS) const {
235     return LeafTy::get(getKnownMinValue() / RHS, isScalable());
236   }
237 
multiplyCoefficientBy(ScalarTy RHS)238   constexpr LeafTy multiplyCoefficientBy(ScalarTy RHS) const {
239     return LeafTy::get(getKnownMinValue() * RHS, isScalable());
240   }
241 
coefficientNextPowerOf2()242   constexpr LeafTy coefficientNextPowerOf2() const {
243     return LeafTy::get(
244         static_cast<ScalarTy>(llvm::NextPowerOf2(getKnownMinValue())),
245         isScalable());
246   }
247 
248   /// Returns true if there exists a value X where RHS.multiplyCoefficientBy(X)
249   /// will result in a value whose quantity matches our own.
250   constexpr bool
hasKnownScalarFactor(const FixedOrScalableQuantity & RHS)251   hasKnownScalarFactor(const FixedOrScalableQuantity &RHS) const {
252     return isScalable() == RHS.isScalable() &&
253            getKnownMinValue() % RHS.getKnownMinValue() == 0;
254   }
255 
256   /// Returns a value X where RHS.multiplyCoefficientBy(X) will result in a
257   /// value whose quantity matches our own.
258   constexpr ScalarTy
getKnownScalarFactor(const FixedOrScalableQuantity & RHS)259   getKnownScalarFactor(const FixedOrScalableQuantity &RHS) const {
260     assert(hasKnownScalarFactor(RHS) && "Expected RHS to be a known factor!");
261     return getKnownMinValue() / RHS.getKnownMinValue();
262   }
263 
264   /// Printing function.
print(raw_ostream & OS)265   void print(raw_ostream &OS) const {
266     if (isScalable())
267       OS << "vscale x ";
268     OS << getKnownMinValue();
269   }
270 };
271 
272 } // namespace details
273 
274 // Stores the number of elements for a type and whether this type is fixed
275 // (N-Elements) or scalable (e.g., SVE).
276 //  - ElementCount::getFixed(1) : A scalar value.
277 //  - ElementCount::getFixed(2) : A vector type holding 2 values.
278 //  - ElementCount::getScalable(4) : A scalable vector type holding 4 values.
279 class ElementCount
280     : public details::FixedOrScalableQuantity<ElementCount, unsigned> {
ElementCount(ScalarTy MinVal,bool Scalable)281   constexpr ElementCount(ScalarTy MinVal, bool Scalable)
282       : FixedOrScalableQuantity(MinVal, Scalable) {}
283 
ElementCount(const FixedOrScalableQuantity<ElementCount,unsigned> & V)284   constexpr ElementCount(
285       const FixedOrScalableQuantity<ElementCount, unsigned> &V)
286       : FixedOrScalableQuantity(V) {}
287 
288 public:
ElementCount()289   constexpr ElementCount() : FixedOrScalableQuantity() {}
290 
getFixed(ScalarTy MinVal)291   static constexpr ElementCount getFixed(ScalarTy MinVal) {
292     return ElementCount(MinVal, false);
293   }
getScalable(ScalarTy MinVal)294   static constexpr ElementCount getScalable(ScalarTy MinVal) {
295     return ElementCount(MinVal, true);
296   }
get(ScalarTy MinVal,bool Scalable)297   static constexpr ElementCount get(ScalarTy MinVal, bool Scalable) {
298     return ElementCount(MinVal, Scalable);
299   }
300 
301   /// Exactly one element.
isScalar()302   constexpr bool isScalar() const {
303     return !isScalable() && getKnownMinValue() == 1;
304   }
305   /// One or more elements.
isVector()306   constexpr bool isVector() const {
307     return (isScalable() && getKnownMinValue() != 0) || getKnownMinValue() > 1;
308   }
309 };
310 
311 // Stores the size of a type. If the type is of fixed size, it will represent
312 // the exact size. If the type is a scalable vector, it will represent the known
313 // minimum size.
314 class TypeSize : public details::FixedOrScalableQuantity<TypeSize, uint64_t> {
TypeSize(const FixedOrScalableQuantity<TypeSize,uint64_t> & V)315   TypeSize(const FixedOrScalableQuantity<TypeSize, uint64_t> &V)
316       : FixedOrScalableQuantity(V) {}
317 
318 public:
TypeSize(ScalarTy Quantity,bool Scalable)319   constexpr TypeSize(ScalarTy Quantity, bool Scalable)
320       : FixedOrScalableQuantity(Quantity, Scalable) {}
321 
getFixed(ScalarTy ExactSize)322   static constexpr TypeSize getFixed(ScalarTy ExactSize) {
323     return TypeSize(ExactSize, false);
324   }
getScalable(ScalarTy MinimunSize)325   static constexpr TypeSize getScalable(ScalarTy MinimunSize) {
326     return TypeSize(MinimunSize, true);
327   }
get(ScalarTy Quantity,bool Scalable)328   static constexpr TypeSize get(ScalarTy Quantity, bool Scalable) {
329     return TypeSize(Quantity, Scalable);
330   }
Fixed(ScalarTy ExactSize)331   static constexpr TypeSize Fixed(ScalarTy ExactSize) {
332     return TypeSize(ExactSize, false);
333   }
Scalable(ScalarTy MinimumSize)334   static constexpr TypeSize Scalable(ScalarTy MinimumSize) {
335     return TypeSize(MinimumSize, true);
336   }
337 
338   LLVM_DEPRECATED("Use getFixedValue() instead", "getFixedValue")
getFixedSize()339   constexpr ScalarTy getFixedSize() const { return getFixedValue(); }
340 
341   LLVM_DEPRECATED("Use getKnownMinValue() instead", "getKnownMinValue")
getKnownMinSize()342   constexpr ScalarTy getKnownMinSize() const { return getKnownMinValue(); }
343 
344   // All code for this class below this point is needed because of the
345   // temporary implicit conversion to uint64_t. The operator overloads are
346   // needed because otherwise the conversion of the parent class
347   // UnivariateLinearPolyBase -> TypeSize is ambiguous.
348   // TODO: Remove the implicit conversion.
349 
350   // Casts to a uint64_t if this is a fixed-width size.
351   //
352   // This interface is deprecated and will be removed in a future version
353   // of LLVM in favour of upgrading uses that rely on this implicit conversion
354   // to uint64_t. Calls to functions that return a TypeSize should use the
355   // proper interfaces to TypeSize.
356   // In practice this is mostly calls to MVT/EVT::getSizeInBits().
357   //
358   // To determine how to upgrade the code:
359   //
360   //   if (<algorithm works for both scalable and fixed-width vectors>)
361   //     use getKnownMinValue()
362   //   else if (<algorithm works only for fixed-width vectors>) {
363   //     if <algorithm can be adapted for both scalable and fixed-width vectors>
364   //       update the algorithm and use getKnownMinValue()
365   //     else
366   //       bail out early for scalable vectors and use getFixedValue()
367   //   }
368   operator ScalarTy() const;
369 
370   // Additional operators needed to avoid ambiguous parses
371   // because of the implicit conversion hack.
372   friend constexpr TypeSize operator*(const TypeSize &LHS, const int RHS) {
373     return LHS * (ScalarTy)RHS;
374   }
375   friend constexpr TypeSize operator*(const TypeSize &LHS, const unsigned RHS) {
376     return LHS * (ScalarTy)RHS;
377   }
378   friend constexpr TypeSize operator*(const TypeSize &LHS, const int64_t RHS) {
379     return LHS * (ScalarTy)RHS;
380   }
381   friend constexpr TypeSize operator*(const int LHS, const TypeSize &RHS) {
382     return RHS * LHS;
383   }
384   friend constexpr TypeSize operator*(const unsigned LHS, const TypeSize &RHS) {
385     return RHS * LHS;
386   }
387   friend constexpr TypeSize operator*(const int64_t LHS, const TypeSize &RHS) {
388     return RHS * LHS;
389   }
390   friend constexpr TypeSize operator*(const uint64_t LHS, const TypeSize &RHS) {
391     return RHS * LHS;
392   }
393 };
394 
395 //===----------------------------------------------------------------------===//
396 // Utilities
397 //===----------------------------------------------------------------------===//
398 
399 /// Returns a TypeSize with a known minimum size that is the next integer
400 /// (mod 2**64) that is greater than or equal to \p Quantity and is a multiple
401 /// of \p Align. \p Align must be non-zero.
402 ///
403 /// Similar to the alignTo functions in MathExtras.h
alignTo(TypeSize Size,uint64_t Align)404 inline constexpr TypeSize alignTo(TypeSize Size, uint64_t Align) {
405   assert(Align != 0u && "Align must be non-zero");
406   return {(Size.getKnownMinValue() + Align - 1) / Align * Align,
407           Size.isScalable()};
408 }
409 
410 /// Stream operator function for `FixedOrScalableQuantity`.
411 template <typename LeafTy, typename ScalarTy>
412 inline raw_ostream &
413 operator<<(raw_ostream &OS,
414            const details::FixedOrScalableQuantity<LeafTy, ScalarTy> &PS) {
415   PS.print(OS);
416   return OS;
417 }
418 
419 template <> struct DenseMapInfo<ElementCount, void> {
420   static inline ElementCount getEmptyKey() {
421     return ElementCount::getScalable(~0U);
422   }
423   static inline ElementCount getTombstoneKey() {
424     return ElementCount::getFixed(~0U - 1);
425   }
426   static unsigned getHashValue(const ElementCount &EltCnt) {
427     unsigned HashVal = EltCnt.getKnownMinValue() * 37U;
428     if (EltCnt.isScalable())
429       return (HashVal - 1U);
430 
431     return HashVal;
432   }
433   static bool isEqual(const ElementCount &LHS, const ElementCount &RHS) {
434     return LHS == RHS;
435   }
436 };
437 
438 } // end namespace llvm
439 
440 #endif // LLVM_SUPPORT_TYPESIZE_H
441