MLIR  18.0.0git
Enums.h
Go to the documentation of this file.
1 //===- Enums.h - Enums for the SparseTensor dialect -------------*- 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 // Typedefs and enums shared between MLIR code for manipulating the
10 // IR, and the lightweight runtime support library for sparse tensor
11 // manipulations. That is, all the enums are used to define the API
12 // of the runtime library and hence are also needed when generating
13 // calls into the runtime library. Moveover, the `LevelType` enum
14 // is also used as the internal IR encoding of dimension level types,
15 // to avoid code duplication (e.g., for the predicates).
16 //
17 // This file also defines x-macros <https://en.wikipedia.org/wiki/X_Macro>
18 // so that we can generate variations of the public functions for each
19 // supported primary- and/or overhead-type.
20 //
21 // Because this file defines a library which is a dependency of the
22 // runtime library itself, this file must not depend on any MLIR internals
23 // (e.g., operators, attributes, ArrayRefs, etc) lest the runtime library
24 // inherit those dependencies.
25 //
26 //===----------------------------------------------------------------------===//
27 
28 #ifndef MLIR_DIALECT_SPARSETENSOR_IR_ENUMS_H
29 #define MLIR_DIALECT_SPARSETENSOR_IR_ENUMS_H
30 
31 // NOTE: Client code will need to include "mlir/ExecutionEngine/Float16bits.h"
32 // if they want to use the `MLIR_SPARSETENSOR_FOREVERY_V` macro.
33 
34 #include <cassert>
35 #include <cinttypes>
36 #include <complex>
37 #include <optional>
38 
39 namespace mlir {
40 namespace sparse_tensor {
41 
42 /// This type is used in the public API at all places where MLIR expects
43 /// values with the built-in type "index". For now, we simply assume that
44 /// type is 64-bit, but targets with different "index" bitwidths should
45 /// link with an alternatively built runtime support library.
46 using index_type = uint64_t;
47 
48 /// Encoding of overhead types (both position overhead and coordinate
49 /// overhead), for "overloading" @newSparseTensor.
50 enum class OverheadType : uint32_t {
51  kIndex = 0,
52  kU64 = 1,
53  kU32 = 2,
54  kU16 = 3,
55  kU8 = 4
56 };
57 
58 // This x-macro calls its argument on every overhead type which has
59 // fixed-width. It excludes `index_type` because that type is often
60 // handled specially (e.g., by translating it into the architecture-dependent
61 // equivalent fixed-width overhead type).
62 #define MLIR_SPARSETENSOR_FOREVERY_FIXED_O(DO) \
63  DO(64, uint64_t) \
64  DO(32, uint32_t) \
65  DO(16, uint16_t) \
66  DO(8, uint8_t)
67 
68 // This x-macro calls its argument on every overhead type, including
69 // `index_type`.
70 #define MLIR_SPARSETENSOR_FOREVERY_O(DO) \
71  MLIR_SPARSETENSOR_FOREVERY_FIXED_O(DO) \
72  DO(0, index_type)
73 
74 // These are not just shorthands but indicate the particular
75 // implementation used (e.g., as opposed to C99's `complex double`,
76 // or MLIR's `ComplexType`).
77 using complex64 = std::complex<double>;
78 using complex32 = std::complex<float>;
79 
80 /// Encoding of the elemental type, for "overloading" @newSparseTensor.
81 enum class PrimaryType : uint32_t {
82  kF64 = 1,
83  kF32 = 2,
84  kF16 = 3,
85  kBF16 = 4,
86  kI64 = 5,
87  kI32 = 6,
88  kI16 = 7,
89  kI8 = 8,
90  kC64 = 9,
91  kC32 = 10
92 };
93 
94 // This x-macro includes all `V` types.
95 #define MLIR_SPARSETENSOR_FOREVERY_V(DO) \
96  DO(F64, double) \
97  DO(F32, float) \
98  DO(F16, f16) \
99  DO(BF16, bf16) \
100  DO(I64, int64_t) \
101  DO(I32, int32_t) \
102  DO(I16, int16_t) \
103  DO(I8, int8_t) \
104  DO(C64, complex64) \
105  DO(C32, complex32)
106 
107 // This x-macro includes all `V` types and supports variadic arguments.
108 #define MLIR_SPARSETENSOR_FOREVERY_V_VAR(DO, ...) \
109  DO(F64, double, __VA_ARGS__) \
110  DO(F32, float, __VA_ARGS__) \
111  DO(F16, f16, __VA_ARGS__) \
112  DO(BF16, bf16, __VA_ARGS__) \
113  DO(I64, int64_t, __VA_ARGS__) \
114  DO(I32, int32_t, __VA_ARGS__) \
115  DO(I16, int16_t, __VA_ARGS__) \
116  DO(I8, int8_t, __VA_ARGS__) \
117  DO(C64, complex64, __VA_ARGS__) \
118  DO(C32, complex32, __VA_ARGS__)
119 
120 // This x-macro calls its argument on every pair of overhead and `V` types.
121 #define MLIR_SPARSETENSOR_FOREVERY_V_O(DO) \
122  MLIR_SPARSETENSOR_FOREVERY_V_VAR(DO, 64, uint64_t) \
123  MLIR_SPARSETENSOR_FOREVERY_V_VAR(DO, 32, uint32_t) \
124  MLIR_SPARSETENSOR_FOREVERY_V_VAR(DO, 16, uint16_t) \
125  MLIR_SPARSETENSOR_FOREVERY_V_VAR(DO, 8, uint8_t) \
126  MLIR_SPARSETENSOR_FOREVERY_V_VAR(DO, 0, index_type)
127 
128 constexpr bool isFloatingPrimaryType(PrimaryType valTy) {
129  return PrimaryType::kF64 <= valTy && valTy <= PrimaryType::kBF16;
130 }
131 
132 constexpr bool isIntegralPrimaryType(PrimaryType valTy) {
133  return PrimaryType::kI64 <= valTy && valTy <= PrimaryType::kI8;
134 }
135 
136 constexpr bool isRealPrimaryType(PrimaryType valTy) {
137  return PrimaryType::kF64 <= valTy && valTy <= PrimaryType::kI8;
138 }
139 
140 constexpr bool isComplexPrimaryType(PrimaryType valTy) {
141  return PrimaryType::kC64 <= valTy && valTy <= PrimaryType::kC32;
142 }
143 
144 /// The actions performed by @newSparseTensor.
145 enum class Action : uint32_t {
146  kEmpty = 0,
147  kEmptyForward = 1,
148  kFromCOO = 2,
149  kFromReader = 4,
150  kToCOO = 5,
151  kPack = 7,
152  kSortCOOInPlace = 8,
153 };
154 
155 /// This enum defines all the sparse representations supportable by
156 /// the SparseTensor dialect. We use a lightweight encoding to encode
157 /// both the "format" per se (dense, compressed, singleton, loose_compressed,
158 /// two-out-of-four) as well as the "properties" (ordered, unique). The
159 /// encoding is chosen for performance of the runtime library, and thus may
160 /// change in future versions; consequently, client code should use the
161 /// predicate functions defined below, rather than relying on knowledge
162 /// about the particular binary encoding.
163 ///
164 /// The `Undef` "format" is a special value used internally for cases
165 /// where we need to store an undefined or indeterminate `LevelType`.
166 /// It should not be used externally, since it does not indicate an
167 /// actual/representable format.
168 enum class LevelType : uint8_t {
169  Undef = 0, // 0b00000_00
170  Dense = 4, // 0b00001_00
171  Compressed = 8, // 0b00010_00
172  CompressedNu = 9, // 0b00010_01
173  CompressedNo = 10, // 0b00010_10
174  CompressedNuNo = 11, // 0b00010_11
175  Singleton = 16, // 0b00100_00
176  SingletonNu = 17, // 0b00100_01
177  SingletonNo = 18, // 0b00100_10
178  SingletonNuNo = 19, // 0b00100_11
179  LooseCompressed = 32, // 0b01000_00
180  LooseCompressedNu = 33, // 0b01000_01
181  LooseCompressedNo = 34, // 0b01000_10
182  LooseCompressedNuNo = 35, // 0b01000_11
183  TwoOutOfFour = 64, // 0b10000_00
184 };
185 
186 /// This enum defines all supported storage format without the level properties.
187 enum class LevelFormat : uint8_t {
188  Dense = 4, // 0b00001_00
189  Compressed = 8, // 0b00010_00
190  Singleton = 16, // 0b00100_00
191  LooseCompressed = 32, // 0b01000_00
192  TwoOutOfFour = 64, // 0b10000_00
193 };
194 
195 /// This enum defines all the nondefault properties for storage formats.
196 enum class LevelPropertyNondefault : uint8_t {
197  Nonunique = 1, // 0b00000_01
198  Nonordered = 2, // 0b00000_10
199 };
200 
201 /// Returns string representation of the given dimension level type.
202 constexpr const char *toMLIRString(LevelType lt) {
203  switch (lt) {
204  case LevelType::Undef:
205  return "undef";
206  case LevelType::Dense:
207  return "dense";
209  return "compressed";
211  return "compressed(nonunique)";
213  return "compressed(nonordered)";
215  return "compressed(nonunique, nonordered)";
217  return "singleton";
219  return "singleton(nonunique)";
221  return "singleton(nonordered)";
223  return "singleton(nonunique, nonordered)";
225  return "loose_compressed";
227  return "loose_compressed(nonunique)";
229  return "loose_compressed(nonordered)";
231  return "loose_compressed(nonunique, nonordered)";
233  return "block2_4";
234  }
235  return "";
236 }
237 
238 /// Check that the `LevelType` contains a valid (possibly undefined) value.
239 constexpr bool isValidLT(LevelType lt) {
240  const uint8_t formatBits = static_cast<uint8_t>(lt) >> 2;
241  const uint8_t propertyBits = static_cast<uint8_t>(lt) & 3;
242  // If undefined or dense, then must be unique and ordered.
243  // Otherwise, the format must be one of the known ones.
244  return (formatBits <= 1 || formatBits == 16)
245  ? (propertyBits == 0)
246  : (formatBits == 2 || formatBits == 4 || formatBits == 8);
247 }
248 
249 /// Check if the `LevelType` is the special undefined value.
250 constexpr bool isUndefLT(LevelType lt) { return lt == LevelType::Undef; }
251 
252 /// Check if the `LevelType` is dense (regardless of properties).
253 constexpr bool isDenseLT(LevelType lt) {
254  return (static_cast<uint8_t>(lt) & ~3) ==
255  static_cast<uint8_t>(LevelType::Dense);
256 }
257 
258 /// Check if the `LevelType` is compressed (regardless of properties).
259 constexpr bool isCompressedLT(LevelType lt) {
260  return (static_cast<uint8_t>(lt) & ~3) ==
261  static_cast<uint8_t>(LevelType::Compressed);
262 }
263 
264 /// Check if the `LevelType` is singleton (regardless of properties).
265 constexpr bool isSingletonLT(LevelType lt) {
266  return (static_cast<uint8_t>(lt) & ~3) ==
267  static_cast<uint8_t>(LevelType::Singleton);
268 }
269 
270 /// Check if the `LevelType` is loose compressed (regardless of properties).
271 constexpr bool isLooseCompressedLT(LevelType lt) {
272  return (static_cast<uint8_t>(lt) & ~3) ==
273  static_cast<uint8_t>(LevelType::LooseCompressed);
274 }
275 
276 /// Check if the `LevelType` is 2OutOf4 (regardless of properties).
277 constexpr bool is2OutOf4LT(LevelType lt) {
278  return (static_cast<uint8_t>(lt) & ~3) ==
279  static_cast<uint8_t>(LevelType::TwoOutOfFour);
280 }
281 
282 /// Check if the `LevelType` needs positions array.
283 constexpr bool isWithPosLT(LevelType lt) {
284  return isCompressedLT(lt) || isLooseCompressedLT(lt);
285 }
286 
287 /// Check if the `LevelType` needs coordinates array.
288 constexpr bool isWithCrdLT(LevelType lt) {
289  return isCompressedLT(lt) || isSingletonLT(lt) || isLooseCompressedLT(lt) ||
290  is2OutOf4LT(lt);
291 }
292 
293 /// Check if the `LevelType` is ordered (regardless of storage format).
294 constexpr bool isOrderedLT(LevelType lt) {
295  return !(static_cast<uint8_t>(lt) & 2);
296 }
297 
298 /// Check if the `LevelType` is unique (regardless of storage format).
299 constexpr bool isUniqueLT(LevelType lt) {
300  return !(static_cast<uint8_t>(lt) & 1);
301 }
302 
303 /// Convert a LevelType to its corresponding LevelFormat.
304 /// Returns std::nullopt when input lt is Undef.
305 constexpr std::optional<LevelFormat> getLevelFormat(LevelType lt) {
306  if (lt == LevelType::Undef)
307  return std::nullopt;
308  return static_cast<LevelFormat>(static_cast<uint8_t>(lt) & ~3);
309 }
310 
311 /// Convert a LevelFormat to its corresponding LevelType with the given
312 /// properties. Returns std::nullopt when the properties are not applicable
313 /// for the input level format.
314 constexpr std::optional<LevelType> buildLevelType(LevelFormat lf, bool ordered,
315  bool unique) {
316  auto lt = static_cast<LevelType>(static_cast<uint8_t>(lf) |
317  (ordered ? 0 : 2) | (unique ? 0 : 1));
318  return isValidLT(lt) ? std::optional(lt) : std::nullopt;
319 }
320 
321 //
322 // Ensure the above methods work as indended.
323 //
324 
325 static_assert(
326  (getLevelFormat(LevelType::Undef) == std::nullopt &&
345  "getLevelFormat conversion is broken");
346 
347 static_assert(
348  (buildLevelType(LevelFormat::Dense, false, true) == std::nullopt &&
349  buildLevelType(LevelFormat::Dense, true, false) == std::nullopt &&
350  buildLevelType(LevelFormat::Dense, false, false) == std::nullopt &&
352  *buildLevelType(LevelFormat::Compressed, true, true) ==
354  *buildLevelType(LevelFormat::Compressed, true, false) ==
356  *buildLevelType(LevelFormat::Compressed, false, true) ==
358  *buildLevelType(LevelFormat::Compressed, false, false) ==
360  *buildLevelType(LevelFormat::Singleton, true, true) ==
362  *buildLevelType(LevelFormat::Singleton, true, false) ==
364  *buildLevelType(LevelFormat::Singleton, false, true) ==
366  *buildLevelType(LevelFormat::Singleton, false, false) ==
376  buildLevelType(LevelFormat::TwoOutOfFour, false, true) == std::nullopt &&
377  buildLevelType(LevelFormat::TwoOutOfFour, true, false) == std::nullopt &&
378  buildLevelType(LevelFormat::TwoOutOfFour, false, false) == std::nullopt &&
381  "buildLevelType conversion is broken");
382 
383 static_assert(
395  "isValidLT definition is broken");
396 
397 static_assert((isDenseLT(LevelType::Dense) &&
411  "isDenseLT definition is broken");
412 
413 static_assert((!isCompressedLT(LevelType::Dense) &&
427  "isCompressedLT definition is broken");
428 
429 static_assert((!isSingletonLT(LevelType::Dense) &&
443  "isSingletonLT definition is broken");
444 
445 static_assert((!isLooseCompressedLT(LevelType::Dense) &&
459  "isLooseCompressedLT definition is broken");
460 
461 static_assert((!is2OutOf4LT(LevelType::Dense) &&
475  "is2OutOf4LT definition is broken");
476 
477 static_assert((isOrderedLT(LevelType::Dense) &&
491  "isOrderedLT definition is broken");
492 
493 static_assert((isUniqueLT(LevelType::Dense) &&
507  "isUniqueLT definition is broken");
508 
509 /// Bit manipulations for affine encoding.
510 ///
511 /// Note that because the indices in the mappings refer to dimensions
512 /// and levels (and *not* the sizes of these dimensions and levels), the
513 /// 64-bit encoding gives ample room for a compact encoding of affine
514 /// operations in the higher bits. Pure permutations still allow for
515 /// 60-bit indices. But non-permutations reserve 20-bits for the
516 /// potential three components (index i, constant, index ii).
517 ///
518 /// The compact encoding is as follows:
519 ///
520 /// 0xffffffffffffffff
521 /// |0000 | 60-bit idx| e.g. i
522 /// |0001 floor| 20-bit const|20-bit idx| e.g. i floor c
523 /// |0010 mod | 20-bit const|20-bit idx| e.g. i mod c
524 /// |0011 mul |20-bit idx|20-bit const|20-bit idx| e.g. i + c * ii
525 ///
526 /// This encoding provides sufficient generality for currently supported
527 /// sparse tensor types. To generalize this more, we will need to provide
528 /// a broader encoding scheme for affine functions. Also, the library
529 /// encoding may be replaced with pure "direct-IR" code in the future.
530 ///
531 constexpr uint64_t encodeDim(uint64_t i, uint64_t cf, uint64_t cm) {
532  if (cf != 0) {
533  assert(cf <= 0xfffff && cm == 0 && i <= 0xfffff);
534  return (0x01ULL << 60) | (cf << 20) | i;
535  }
536  if (cm != 0) {
537  assert(cm <= 0xfffff && i <= 0xfffff);
538  return (0x02ULL << 60) | (cm << 20) | i;
539  }
540  assert(i <= 0x0fffffffffffffffu);
541  return i;
542 }
543 constexpr uint64_t encodeLvl(uint64_t i, uint64_t c, uint64_t ii) {
544  if (c != 0) {
545  assert(c <= 0xfffff && ii <= 0xfffff && i <= 0xfffff);
546  return (0x03ULL << 60) | (c << 20) | (ii << 40) | i;
547  }
548  assert(i <= 0x0fffffffffffffffu);
549  return i;
550 }
551 constexpr bool isEncodedFloor(uint64_t v) { return (v >> 60) == 0x01; }
552 constexpr bool isEncodedMod(uint64_t v) { return (v >> 60) == 0x02; }
553 constexpr bool isEncodedMul(uint64_t v) { return (v >> 60) == 0x03; }
554 constexpr uint64_t decodeIndex(uint64_t v) { return v & 0xfffffu; }
555 constexpr uint64_t decodeConst(uint64_t v) { return (v >> 20) & 0xfffffu; }
556 constexpr uint64_t decodeMulc(uint64_t v) { return (v >> 20) & 0xfffffu; }
557 constexpr uint64_t decodeMuli(uint64_t v) { return (v >> 40) & 0xfffffu; }
558 
559 } // namespace sparse_tensor
560 } // namespace mlir
561 
562 #endif // MLIR_DIALECT_SPARSETENSOR_IR_ENUMS_H
std::complex< double > complex64
Definition: Enums.h:77
constexpr const char * toMLIRString(LevelType lt)
Returns string representation of the given dimension level type.
Definition: Enums.h:202
LevelPropertyNondefault
This enum defines all the nondefault properties for storage formats.
Definition: Enums.h:196
LevelFormat
This enum defines all supported storage format without the level properties.
Definition: Enums.h:187
constexpr uint64_t decodeMuli(uint64_t v)
Definition: Enums.h:557
constexpr bool isWithPosLT(LevelType lt)
Check if the LevelType needs positions array.
Definition: Enums.h:283
OverheadType
Encoding of overhead types (both position overhead and coordinate overhead), for "overloading" @newSp...
Definition: Enums.h:50
constexpr bool isLooseCompressedLT(LevelType lt)
Check if the LevelType is loose compressed (regardless of properties).
Definition: Enums.h:271
Action
The actions performed by @newSparseTensor.
Definition: Enums.h:145
constexpr bool isEncodedMul(uint64_t v)
Definition: Enums.h:553
constexpr bool isUniqueLT(LevelType lt)
Check if the LevelType is unique (regardless of storage format).
Definition: Enums.h:299
constexpr bool isIntegralPrimaryType(PrimaryType valTy)
Definition: Enums.h:132
constexpr bool isEncodedMod(uint64_t v)
Definition: Enums.h:552
constexpr uint64_t decodeConst(uint64_t v)
Definition: Enums.h:555
constexpr bool isUndefLT(LevelType lt)
Check if the LevelType is the special undefined value.
Definition: Enums.h:250
PrimaryType
Encoding of the elemental type, for "overloading" @newSparseTensor.
Definition: Enums.h:81
std::complex< float > complex32
Definition: Enums.h:78
constexpr bool isWithCrdLT(LevelType lt)
Check if the LevelType needs coordinates array.
Definition: Enums.h:288
constexpr uint64_t decodeIndex(uint64_t v)
Definition: Enums.h:554
constexpr bool is2OutOf4LT(LevelType lt)
Check if the LevelType is 2OutOf4 (regardless of properties).
Definition: Enums.h:277
constexpr bool isDenseLT(LevelType lt)
Check if the LevelType is dense (regardless of properties).
Definition: Enums.h:253
constexpr std::optional< LevelFormat > getLevelFormat(LevelType lt)
Convert a LevelType to its corresponding LevelFormat.
Definition: Enums.h:305
constexpr bool isSingletonLT(LevelType lt)
Check if the LevelType is singleton (regardless of properties).
Definition: Enums.h:265
constexpr bool isRealPrimaryType(PrimaryType valTy)
Definition: Enums.h:136
constexpr bool isOrderedLT(LevelType lt)
Check if the LevelType is ordered (regardless of storage format).
Definition: Enums.h:294
LevelType
This enum defines all the sparse representations supportable by the SparseTensor dialect.
Definition: Enums.h:168
uint64_t index_type
This type is used in the public API at all places where MLIR expects values with the built-in type "i...
Definition: Enums.h:46
constexpr bool isCompressedLT(LevelType lt)
Check if the LevelType is compressed (regardless of properties).
Definition: Enums.h:259
constexpr bool isComplexPrimaryType(PrimaryType valTy)
Definition: Enums.h:140
constexpr uint64_t encodeLvl(uint64_t i, uint64_t c, uint64_t ii)
Definition: Enums.h:543
constexpr uint64_t decodeMulc(uint64_t v)
Definition: Enums.h:556
constexpr bool isValidLT(LevelType lt)
Check that the LevelType contains a valid (possibly undefined) value.
Definition: Enums.h:239
constexpr uint64_t encodeDim(uint64_t i, uint64_t cf, uint64_t cm)
Bit manipulations for affine encoding.
Definition: Enums.h:531
constexpr std::optional< LevelType > buildLevelType(LevelFormat lf, bool ordered, bool unique)
Convert a LevelFormat to its corresponding LevelType with the given properties.
Definition: Enums.h:314
constexpr bool isFloatingPrimaryType(PrimaryType valTy)
Definition: Enums.h:128
constexpr bool isEncodedFloor(uint64_t v)
Definition: Enums.h:551
Include the generated interface declarations.