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 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() 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. 264 template <typename LeafTy> 265 class 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 271 public: 272 using ScalarTy = typename UnivariateLinearPolyBase<LeafTy>::ScalarTy; 273 enum Dims : unsigned { FixedDim = 0, ScalableDim = 1 }; 274 275 protected: 276 LinearPolySize(ScalarTy MinVal, Dims D) 277 : UnivariateLinearPolyBase<LeafTy>(MinVal, D) {} 278 279 LinearPolySize(const UnivariateLinearPolyBase<LeafTy> &V) 280 : UnivariateLinearPolyBase<LeafTy>(V) {} 281 282 public: 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 380 class ElementCount; 381 template <> struct LinearPolyBaseTypeTraits<ElementCount> { 382 using ScalarTy = unsigned; 383 static constexpr unsigned Dimensions = 2; 384 }; 385 386 class ElementCount : public LinearPolySize<ElementCount> { 387 public: 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 405 class TypeSize; 406 template <> 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. 417 class TypeSize : public LinearPolySize<TypeSize> { 418 public: 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 489 inline 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`. 496 template <typename LeafTy> 497 inline raw_ostream &operator<<(raw_ostream &OS, 498 const LinearPolySize<LeafTy> &PS) { 499 PS.print(OS); 500 return OS; 501 } 502 503 template <typename T> struct DenseMapInfo; 504 template <> 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