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