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 40 StackOffset(int64_t Fixed, int64_t Scalable) 41 : Fixed(Fixed), Scalable(Scalable) {} 42 43 public: 44 StackOffset() = default; 45 static StackOffset getFixed(int64_t Fixed) { return {Fixed, 0}; } 46 static StackOffset getScalable(int64_t Scalable) { return {0, 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. 52 int64_t getFixed() const { return Fixed; } 53 54 /// Returns the scalable component of the stack. 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; 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_v<U>, 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 151 constexpr bool isZero() const { return Quantity == 0; } 152 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. 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. 163 constexpr ScalarTy getKnownMinValue() const { return Quantity; } 164 165 /// Returns whether the quantity is scaled by a runtime quantity (vscale). 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. 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. 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). 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 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 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 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 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. 234 constexpr LeafTy divideCoefficientBy(ScalarTy RHS) const { 235 return LeafTy::get(getKnownMinValue() / RHS, isScalable()); 236 } 237 238 constexpr LeafTy multiplyCoefficientBy(ScalarTy RHS) const { 239 return LeafTy::get(getKnownMinValue() * RHS, isScalable()); 240 } 241 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 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 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. 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> { 281 constexpr ElementCount(ScalarTy MinVal, bool Scalable) 282 : FixedOrScalableQuantity(MinVal, Scalable) {} 283 284 constexpr ElementCount( 285 const FixedOrScalableQuantity<ElementCount, unsigned> &V) 286 : FixedOrScalableQuantity(V) {} 287 288 public: 289 constexpr ElementCount() : FixedOrScalableQuantity() {} 290 291 static constexpr ElementCount getFixed(ScalarTy MinVal) { 292 return ElementCount(MinVal, false); 293 } 294 static constexpr ElementCount getScalable(ScalarTy MinVal) { 295 return ElementCount(MinVal, true); 296 } 297 static constexpr ElementCount get(ScalarTy MinVal, bool Scalable) { 298 return ElementCount(MinVal, Scalable); 299 } 300 301 /// Exactly one element. 302 constexpr bool isScalar() const { 303 return !isScalable() && getKnownMinValue() == 1; 304 } 305 /// One or more elements. 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> { 315 TypeSize(const FixedOrScalableQuantity<TypeSize, uint64_t> &V) 316 : FixedOrScalableQuantity(V) {} 317 318 public: 319 constexpr TypeSize(ScalarTy Quantity, bool Scalable) 320 : FixedOrScalableQuantity(Quantity, Scalable) {} 321 322 static constexpr TypeSize getFixed(ScalarTy ExactSize) { 323 return TypeSize(ExactSize, false); 324 } 325 static constexpr TypeSize getScalable(ScalarTy MinimumSize) { 326 return TypeSize(MinimumSize, true); 327 } 328 static constexpr TypeSize get(ScalarTy Quantity, bool Scalable) { 329 return TypeSize(Quantity, Scalable); 330 } 331 static constexpr TypeSize Fixed(ScalarTy ExactSize) { 332 return TypeSize(ExactSize, false); 333 } 334 static constexpr TypeSize Scalable(ScalarTy MinimumSize) { 335 return TypeSize(MinimumSize, true); 336 } 337 338 LLVM_DEPRECATED("Use getFixedValue() instead", "getFixedValue") 339 constexpr ScalarTy getFixedSize() const { return getFixedValue(); } 340 341 LLVM_DEPRECATED("Use getKnownMinValue() instead", "getKnownMinValue") 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 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