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 template <typename LeafTy> struct LinearPolyBaseTypeTraits {}; 31 32 //===----------------------------------------------------------------------===// 33 // LinearPolyBase - a base class for linear polynomials with multiple 34 // dimensions. This can e.g. be used to describe offsets that are have both a 35 // fixed and scalable component. 36 //===----------------------------------------------------------------------===// 37 38 /// LinearPolyBase describes a linear polynomial: 39 /// c0 * scale0 + c1 * scale1 + ... + cK * scaleK 40 /// where the scale is implicit, so only the coefficients are encoded. 41 template <typename LeafTy> 42 class LinearPolyBase { 43 public: 44 using ScalarTy = typename LinearPolyBaseTypeTraits<LeafTy>::ScalarTy; 45 static constexpr auto Dimensions = LinearPolyBaseTypeTraits<LeafTy>::Dimensions; 46 static_assert(Dimensions != std::numeric_limits<unsigned>::max(), 47 "Dimensions out of range"); 48 49 private: 50 std::array<ScalarTy, Dimensions> Coefficients; 51 52 protected: LinearPolyBase(ArrayRef<ScalarTy> Values)53 LinearPolyBase(ArrayRef<ScalarTy> Values) { 54 std::copy(Values.begin(), Values.end(), Coefficients.begin()); 55 } 56 57 public: 58 friend LeafTy &operator+=(LeafTy &LHS, const LeafTy &RHS) { 59 for (unsigned I=0; I<Dimensions; ++I) 60 LHS.Coefficients[I] += RHS.Coefficients[I]; 61 return LHS; 62 } 63 64 friend LeafTy &operator-=(LeafTy &LHS, const LeafTy &RHS) { 65 for (unsigned I=0; I<Dimensions; ++I) 66 LHS.Coefficients[I] -= RHS.Coefficients[I]; 67 return LHS; 68 } 69 70 friend LeafTy &operator*=(LeafTy &LHS, ScalarTy RHS) { 71 for (auto &C : LHS.Coefficients) 72 C *= RHS; 73 return LHS; 74 } 75 76 friend LeafTy operator+(const LeafTy &LHS, const LeafTy &RHS) { 77 LeafTy Copy = LHS; 78 return Copy += RHS; 79 } 80 81 friend LeafTy operator-(const LeafTy &LHS, const LeafTy &RHS) { 82 LeafTy Copy = LHS; 83 return Copy -= RHS; 84 } 85 86 friend LeafTy operator*(const LeafTy &LHS, ScalarTy RHS) { 87 LeafTy Copy = LHS; 88 return Copy *= RHS; 89 } 90 91 template <typename U = ScalarTy> 92 friend typename std::enable_if_t<std::is_signed<U>::value, LeafTy> 93 operator-(const LeafTy &LHS) { 94 LeafTy Copy = LHS; 95 return Copy *= -1; 96 } 97 98 bool operator==(const LinearPolyBase &RHS) const { 99 return std::equal(Coefficients.begin(), Coefficients.end(), 100 RHS.Coefficients.begin()); 101 } 102 103 bool operator!=(const LinearPolyBase &RHS) const { 104 return !(*this == RHS); 105 } 106 isZero()107 bool isZero() const { 108 return all_of(Coefficients, [](const ScalarTy &C) { return C == 0; }); 109 } isNonZero()110 bool isNonZero() const { return !isZero(); } 111 explicit operator bool() const { return isNonZero(); } 112 getValue(unsigned Dim)113 ScalarTy getValue(unsigned Dim) const { return Coefficients[Dim]; } 114 }; 115 116 //===----------------------------------------------------------------------===// 117 // StackOffset - Represent an offset with named fixed and scalable components. 118 //===----------------------------------------------------------------------===// 119 120 class StackOffset; 121 template <> struct LinearPolyBaseTypeTraits<StackOffset> { 122 using ScalarTy = int64_t; 123 static constexpr unsigned Dimensions = 2; 124 }; 125 126 /// StackOffset is a class to represent an offset with 2 dimensions, 127 /// named fixed and scalable, respectively. This class allows a value for both 128 /// dimensions to depict e.g. "8 bytes and 16 scalable bytes", which is needed 129 /// to represent stack offsets. 130 class StackOffset : public LinearPolyBase<StackOffset> { 131 protected: 132 StackOffset(ScalarTy Fixed, ScalarTy Scalable) 133 : LinearPolyBase<StackOffset>({Fixed, Scalable}) {} 134 135 public: 136 StackOffset() : StackOffset({0, 0}) {} 137 StackOffset(const LinearPolyBase<StackOffset> &Other) 138 : LinearPolyBase<StackOffset>(Other) {} 139 static StackOffset getFixed(ScalarTy Fixed) { return {Fixed, 0}; } 140 static StackOffset getScalable(ScalarTy Scalable) { return {0, Scalable}; } 141 static StackOffset get(ScalarTy Fixed, ScalarTy Scalable) { 142 return {Fixed, Scalable}; 143 } 144 145 ScalarTy getFixed() const { return this->getValue(0); } 146 ScalarTy getScalable() const { return this->getValue(1); } 147 }; 148 149 //===----------------------------------------------------------------------===// 150 // UnivariateLinearPolyBase - a base class for linear polynomials with multiple 151 // dimensions, but where only one dimension can be set at any time. 152 // This can e.g. be used to describe sizes that are either fixed or scalable. 153 //===----------------------------------------------------------------------===// 154 155 /// UnivariateLinearPolyBase is a base class for ElementCount and TypeSize. 156 /// Like LinearPolyBase it tries to represent a linear polynomial 157 /// where only one dimension can be set at any time, e.g. 158 /// 0 * scale0 + 0 * scale1 + ... + cJ * scaleJ + ... + 0 * scaleK 159 /// The dimension that is set is the univariate dimension. 160 template <typename LeafTy> 161 class UnivariateLinearPolyBase { 162 public: 163 using ScalarTy = typename LinearPolyBaseTypeTraits<LeafTy>::ScalarTy; 164 static constexpr auto Dimensions = LinearPolyBaseTypeTraits<LeafTy>::Dimensions; 165 static_assert(Dimensions != std::numeric_limits<unsigned>::max(), 166 "Dimensions out of range"); 167 168 protected: 169 ScalarTy Value; // The value at the univeriate dimension. 170 unsigned UnivariateDim; // The univeriate dimension. 171 172 UnivariateLinearPolyBase(ScalarTy Val, unsigned UnivariateDim) 173 : Value(Val), UnivariateDim(UnivariateDim) { 174 assert(UnivariateDim < Dimensions && "Dimension out of range"); 175 } 176 177 friend LeafTy &operator+=(LeafTy &LHS, const LeafTy &RHS) { 178 assert(LHS.UnivariateDim == RHS.UnivariateDim && "Invalid dimensions"); 179 LHS.Value += RHS.Value; 180 return LHS; 181 } 182 183 friend LeafTy &operator-=(LeafTy &LHS, const LeafTy &RHS) { 184 assert(LHS.UnivariateDim == RHS.UnivariateDim && "Invalid dimensions"); 185 LHS.Value -= RHS.Value; 186 return LHS; 187 } 188 189 friend LeafTy &operator*=(LeafTy &LHS, ScalarTy RHS) { 190 LHS.Value *= RHS; 191 return LHS; 192 } 193 194 friend LeafTy operator+(const LeafTy &LHS, const LeafTy &RHS) { 195 LeafTy Copy = LHS; 196 return Copy += RHS; 197 } 198 199 friend LeafTy operator-(const LeafTy &LHS, const LeafTy &RHS) { 200 LeafTy Copy = LHS; 201 return Copy -= RHS; 202 } 203 204 friend LeafTy operator*(const LeafTy &LHS, ScalarTy RHS) { 205 LeafTy Copy = LHS; 206 return Copy *= RHS; 207 } 208 209 template <typename U = ScalarTy> 210 friend typename std::enable_if<std::is_signed<U>::value, LeafTy>::type 211 operator-(const LeafTy &LHS) { 212 LeafTy Copy = LHS; 213 return Copy *= -1; 214 } 215 216 public: 217 bool operator==(const UnivariateLinearPolyBase &RHS) const { 218 return Value == RHS.Value && UnivariateDim == RHS.UnivariateDim; 219 } 220 221 bool operator!=(const UnivariateLinearPolyBase &RHS) const { 222 return !(*this == RHS); 223 } 224 225 bool isZero() const { return !Value; } 226 bool isNonZero() const { return !isZero(); } 227 explicit operator bool() const { return isNonZero(); } 228 ScalarTy getValue() const { return Value; } 229 ScalarTy getValue(unsigned Dim) const { 230 return Dim == UnivariateDim ? Value : 0; 231 } 232 233 /// Add \p RHS to the value at the univariate dimension. 234 LeafTy getWithIncrement(ScalarTy RHS) { 235 return static_cast<LeafTy>( 236 UnivariateLinearPolyBase(Value + RHS, UnivariateDim)); 237 } 238 239 /// Subtract \p RHS from the value at the univariate dimension. 240 LeafTy getWithDecrement(ScalarTy RHS) { 241 return static_cast<LeafTy>( 242 UnivariateLinearPolyBase(Value - RHS, UnivariateDim)); 243 } 244 }; 245 246 247 //===----------------------------------------------------------------------===// 248 // LinearPolySize - base class for fixed- or scalable sizes. 249 // ^ ^ 250 // | | 251 // | +----- ElementCount - Leaf class to represent an element count 252 // | (vscale x unsigned) 253 // | 254 // +-------- TypeSize - Leaf class to represent a type size 255 // (vscale x uint64_t) 256 //===----------------------------------------------------------------------===// 257 258 /// LinearPolySize is a base class to represent sizes. It is either 259 /// fixed-sized or it is scalable-sized, but it cannot be both. 260 template <typename LeafTy> 261 class LinearPolySize : public UnivariateLinearPolyBase<LeafTy> { 262 // Make the parent class a friend, so that it can access the protected 263 // conversion/copy-constructor for UnivariatePolyBase<LeafTy> -> 264 // LinearPolySize<LeafTy>. 265 friend class UnivariateLinearPolyBase<LeafTy>; 266 267 public: 268 using ScalarTy = typename UnivariateLinearPolyBase<LeafTy>::ScalarTy; 269 enum Dims : unsigned { FixedDim = 0, ScalableDim = 1 }; 270 271 protected: 272 LinearPolySize(ScalarTy MinVal, Dims D) 273 : UnivariateLinearPolyBase<LeafTy>(MinVal, D) {} 274 275 LinearPolySize(const UnivariateLinearPolyBase<LeafTy> &V) 276 : UnivariateLinearPolyBase<LeafTy>(V) {} 277 278 public: 279 280 static LeafTy getFixed(ScalarTy MinVal) { 281 return static_cast<LeafTy>(LinearPolySize(MinVal, FixedDim)); 282 } 283 static LeafTy getScalable(ScalarTy MinVal) { 284 return static_cast<LeafTy>(LinearPolySize(MinVal, ScalableDim)); 285 } 286 static LeafTy get(ScalarTy MinVal, bool Scalable) { 287 return static_cast<LeafTy>( 288 LinearPolySize(MinVal, Scalable ? ScalableDim : FixedDim)); 289 } 290 static LeafTy getNull() { return get(0, false); } 291 292 /// Returns the minimum value this size can represent. 293 ScalarTy getKnownMinValue() const { return this->getValue(); } 294 /// Returns whether the size is scaled by a runtime quantity (vscale). 295 bool isScalable() const { return this->UnivariateDim == ScalableDim; } 296 /// A return value of true indicates we know at compile time that the number 297 /// of elements (vscale * Min) is definitely even. However, returning false 298 /// does not guarantee that the total number of elements is odd. 299 bool isKnownEven() const { return (getKnownMinValue() & 0x1) == 0; } 300 /// This function tells the caller whether the element count is known at 301 /// compile time to be a multiple of the scalar value RHS. 302 bool isKnownMultipleOf(ScalarTy RHS) const { 303 return getKnownMinValue() % RHS == 0; 304 } 305 306 // Return the minimum value with the assumption that the count is exact. 307 // Use in places where a scalable count doesn't make sense (e.g. non-vector 308 // types, or vectors in backends which don't support scalable vectors). 309 ScalarTy getFixedValue() const { 310 assert(!isScalable() && 311 "Request for a fixed element count on a scalable object"); 312 return getKnownMinValue(); 313 } 314 315 // For some cases, size ordering between scalable and fixed size types cannot 316 // be determined at compile time, so such comparisons aren't allowed. 317 // 318 // e.g. <vscale x 2 x i16> could be bigger than <4 x i32> with a runtime 319 // vscale >= 5, equal sized with a vscale of 4, and smaller with 320 // a vscale <= 3. 321 // 322 // All the functions below make use of the fact vscale is always >= 1, which 323 // means that <vscale x 4 x i32> is guaranteed to be >= <4 x i32>, etc. 324 325 static bool isKnownLT(const LinearPolySize &LHS, const LinearPolySize &RHS) { 326 if (!LHS.isScalable() || RHS.isScalable()) 327 return LHS.getKnownMinValue() < RHS.getKnownMinValue(); 328 return false; 329 } 330 331 static bool isKnownGT(const LinearPolySize &LHS, const LinearPolySize &RHS) { 332 if (LHS.isScalable() || !RHS.isScalable()) 333 return LHS.getKnownMinValue() > RHS.getKnownMinValue(); 334 return false; 335 } 336 337 static bool isKnownLE(const LinearPolySize &LHS, const LinearPolySize &RHS) { 338 if (!LHS.isScalable() || RHS.isScalable()) 339 return LHS.getKnownMinValue() <= RHS.getKnownMinValue(); 340 return false; 341 } 342 343 static bool isKnownGE(const LinearPolySize &LHS, const LinearPolySize &RHS) { 344 if (LHS.isScalable() || !RHS.isScalable()) 345 return LHS.getKnownMinValue() >= RHS.getKnownMinValue(); 346 return false; 347 } 348 349 /// We do not provide the '/' operator here because division for polynomial 350 /// types does not work in the same way as for normal integer types. We can 351 /// only divide the minimum value (or coefficient) by RHS, which is not the 352 /// same as 353 /// (Min * Vscale) / RHS 354 /// The caller is recommended to use this function in combination with 355 /// isKnownMultipleOf(RHS), which lets the caller know if it's possible to 356 /// perform a lossless divide by RHS. 357 LeafTy divideCoefficientBy(ScalarTy RHS) const { 358 return static_cast<LeafTy>( 359 LinearPolySize::get(getKnownMinValue() / RHS, isScalable())); 360 } 361 362 LeafTy coefficientNextPowerOf2() const { 363 return static_cast<LeafTy>(LinearPolySize::get( 364 static_cast<ScalarTy>(llvm::NextPowerOf2(getKnownMinValue())), 365 isScalable())); 366 } 367 368 /// Printing function. 369 void print(raw_ostream &OS) const { 370 if (isScalable()) 371 OS << "vscale x "; 372 OS << getKnownMinValue(); 373 } 374 }; 375 376 class ElementCount; 377 template <> struct LinearPolyBaseTypeTraits<ElementCount> { 378 using ScalarTy = unsigned; 379 static constexpr unsigned Dimensions = 2; 380 }; 381 382 class ElementCount : public LinearPolySize<ElementCount> { 383 public: 384 385 ElementCount(const LinearPolySize<ElementCount> &V) : LinearPolySize(V) {} 386 387 /// Counting predicates. 388 /// 389 ///@{ Number of elements.. 390 /// Exactly one element. 391 bool isScalar() const { return !isScalable() && getKnownMinValue() == 1; } 392 /// One or more elements. 393 bool isVector() const { 394 return (isScalable() && getKnownMinValue() != 0) || getKnownMinValue() > 1; 395 } 396 ///@} 397 }; 398 399 // This class is used to represent the size of types. If the type is of fixed 400 class TypeSize; 401 template <> struct LinearPolyBaseTypeTraits<TypeSize> { 402 using ScalarTy = uint64_t; 403 static constexpr unsigned Dimensions = 2; 404 }; 405 406 // TODO: Most functionality in this class will gradually be phased out 407 // so it will resemble LinearPolySize as much as possible. 408 // 409 // TypeSize is used to represent the size of types. If the type is of fixed 410 // size, it will represent the exact size. If the type is a scalable vector, 411 // it will represent the known minimum size. 412 class TypeSize : public LinearPolySize<TypeSize> { 413 public: 414 TypeSize(const LinearPolySize<TypeSize> &V) : LinearPolySize(V) {} 415 TypeSize(ScalarTy MinVal, bool IsScalable) 416 : LinearPolySize(LinearPolySize::get(MinVal, IsScalable)) {} 417 418 static TypeSize Fixed(ScalarTy MinVal) { return TypeSize(MinVal, false); } 419 static TypeSize Scalable(ScalarTy MinVal) { return TypeSize(MinVal, true); } 420 421 ScalarTy getFixedSize() const { return getFixedValue(); } 422 ScalarTy getKnownMinSize() const { return getKnownMinValue(); } 423 424 // All code for this class below this point is needed because of the 425 // temporary implicit conversion to uint64_t. The operator overloads are 426 // needed because otherwise the conversion of the parent class 427 // UnivariateLinearPolyBase -> TypeSize is ambiguous. 428 // TODO: Remove the implicit conversion. 429 430 // Casts to a uint64_t if this is a fixed-width size. 431 // 432 // This interface is deprecated and will be removed in a future version 433 // of LLVM in favour of upgrading uses that rely on this implicit conversion 434 // to uint64_t. Calls to functions that return a TypeSize should use the 435 // proper interfaces to TypeSize. 436 // In practice this is mostly calls to MVT/EVT::getSizeInBits(). 437 // 438 // To determine how to upgrade the code: 439 // 440 // if (<algorithm works for both scalable and fixed-width vectors>) 441 // use getKnownMinValue() 442 // else if (<algorithm works only for fixed-width vectors>) { 443 // if <algorithm can be adapted for both scalable and fixed-width vectors> 444 // update the algorithm and use getKnownMinValue() 445 // else 446 // bail out early for scalable vectors and use getFixedValue() 447 // } 448 operator ScalarTy() const { 449 #ifdef STRICT_FIXED_SIZE_VECTORS 450 return getFixedValue(); 451 #else 452 if (isScalable()) 453 WithColor::warning() << "Compiler has made implicit assumption that " 454 "TypeSize is not scalable. This may or may not " 455 "lead to broken code.\n"; 456 return getKnownMinValue(); 457 #endif 458 } 459 460 // Additional operators needed to avoid ambiguous parses 461 // because of the implicit conversion hack. 462 friend TypeSize operator*(const TypeSize &LHS, const int RHS) { 463 return LHS * (ScalarTy)RHS; 464 } 465 friend TypeSize operator*(const TypeSize &LHS, const unsigned RHS) { 466 return LHS * (ScalarTy)RHS; 467 } 468 friend TypeSize operator*(const TypeSize &LHS, const int64_t RHS) { 469 return LHS * (ScalarTy)RHS; 470 } 471 friend TypeSize operator*(const int LHS, const TypeSize &RHS) { 472 return RHS * LHS; 473 } 474 friend TypeSize operator*(const unsigned LHS, const TypeSize &RHS) { 475 return RHS * LHS; 476 } 477 friend TypeSize operator*(const int64_t LHS, const TypeSize &RHS) { 478 return RHS * LHS; 479 } 480 friend TypeSize operator*(const uint64_t LHS, const TypeSize &RHS) { 481 return RHS * LHS; 482 } 483 }; 484 485 //===----------------------------------------------------------------------===// 486 // Utilities 487 //===----------------------------------------------------------------------===// 488 489 /// Returns a TypeSize with a known minimum size that is the next integer 490 /// (mod 2**64) that is greater than or equal to \p Value and is a multiple 491 /// of \p Align. \p Align must be non-zero. 492 /// 493 /// Similar to the alignTo functions in MathExtras.h 494 inline TypeSize alignTo(TypeSize Size, uint64_t Align) { 495 assert(Align != 0u && "Align must be non-zero"); 496 return {(Size.getKnownMinValue() + Align - 1) / Align * Align, 497 Size.isScalable()}; 498 } 499 500 /// Stream operator function for `LinearPolySize`. 501 template <typename LeafTy> 502 inline raw_ostream &operator<<(raw_ostream &OS, 503 const LinearPolySize<LeafTy> &PS) { 504 PS.print(OS); 505 return OS; 506 } 507 508 template <typename T> struct DenseMapInfo; 509 template <> struct DenseMapInfo<ElementCount> { 510 static inline ElementCount getEmptyKey() { 511 return ElementCount::getScalable(~0U); 512 } 513 static inline ElementCount getTombstoneKey() { 514 return ElementCount::getFixed(~0U - 1); 515 } 516 static unsigned getHashValue(const ElementCount &EltCnt) { 517 unsigned HashVal = EltCnt.getKnownMinValue() * 37U; 518 if (EltCnt.isScalable()) 519 return (HashVal - 1U); 520 521 return HashVal; 522 } 523 524 static bool isEqual(const ElementCount &LHS, const ElementCount &RHS) { 525 return LHS == RHS; 526 } 527 }; 528 529 } // end namespace llvm 530 531 #endif // LLVM_SUPPORT_TypeSize_H 532