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 28 namespace 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. 32 void reportInvalidSizeRequest(const char *Msg); 33 34 template <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. 45 template <typename LeafTy> 46 class LinearPolyBase { 47 public: 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 53 private: 54 std::array<ScalarTy, Dimensions> Coefficients; 55 56 protected: 57 LinearPolyBase(ArrayRef<ScalarTy> Values) { 58 std::copy(Values.begin(), Values.end(), Coefficients.begin()); 59 } 60 61 public: 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 124 class StackOffset; 125 template <> 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. 134 class StackOffset : public LinearPolyBase<StackOffset> { 135 protected: 136 StackOffset(ScalarTy Fixed, ScalarTy Scalable) 137 : LinearPolyBase<StackOffset>({Fixed, Scalable}) {} 138 139 public: 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. 164 template <typename LeafTy> 165 class UnivariateLinearPolyBase { 166 public: 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 172 protected: 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 220 public: 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. 263 template <typename LeafTy> 264 class 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 270 public: 271 using ScalarTy = typename UnivariateLinearPolyBase<LeafTy>::ScalarTy; 272 enum Dims : unsigned { FixedDim = 0, ScalableDim = 1 }; 273 274 protected: 275 LinearPolySize(ScalarTy MinVal, Dims D) 276 : UnivariateLinearPolyBase<LeafTy>(MinVal, D) {} 277 278 LinearPolySize(const UnivariateLinearPolyBase<LeafTy> &V) 279 : UnivariateLinearPolyBase<LeafTy>(V) {} 280 281 public: 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 398 class ElementCount; 399 template <> struct LinearPolyBaseTypeTraits<ElementCount> { 400 using ScalarTy = unsigned; 401 static constexpr unsigned Dimensions = 2; 402 }; 403 404 class ElementCount : public LinearPolySize<ElementCount> { 405 public: 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 423 class TypeSize; 424 template <> 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. 435 class TypeSize : public LinearPolySize<TypeSize> { 436 public: 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 507 inline 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`. 514 template <typename LeafTy> 515 inline raw_ostream &operator<<(raw_ostream &OS, 516 const LinearPolySize<LeafTy> &PS) { 517 PS.print(OS); 518 return OS; 519 } 520 521 template <> 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