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 |