1//===- SparseTensorBase.td - Sparse tensor dialect base ----*- tablegen -*-===//
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#ifndef SPARSETENSOR_BASE
10#define SPARSETENSOR_BASE
11
12include "mlir/IR/OpBase.td"
13
14def SparseTensor_Dialect : Dialect {
15  let name = "sparse_tensor";
16  let cppNamespace = "::mlir::sparse_tensor";
17  let description = [{
18    The `SparseTensor` dialect supports all the attributes, types,
19    operations, and passes that are required to make sparse tensor
20    types first class citizens within the MLIR compiler infrastructure.
21    The dialect forms a bridge between high-level operations on sparse
22    tensors types and lower-level operations on the actual sparse storage
23    schemes consisting of pointers, indices, and values. Lower-level
24    support may consist of fully generated code or may be provided by
25    means of a small sparse runtime support library.
26
27    The concept of **treating sparsity as a property, not a tedious
28    implementation detail**, by letting a **sparse compiler** generate
29    sparse code automatically was pioneered for linear algebra by [Bik96]
30    in MT1 (see https://www.aartbik.com/sparse.php) and formalized
31    to tensor algebra by [Kjolstad17,Kjolstad20] in the Sparse Tensor
32    Algebra Compiler (TACO) project (see http://tensor-compiler.org).
33
34    The MLIR implementation closely follows the "sparse iteration theory"
35    that forms the foundation of TACO. A rewriting rule is applied to each
36    tensor expression in the Linalg dialect (MLIR's tensor index notation)
37    where the sparsity of tensors is indicated using the per-dimension level
38    types dense/compressed together with a specification of the order on the
39    dimensions (see [Chou18] for an in-depth discussions and possible
40    extensions to these level types). Subsequently, a topologically sorted
41    iteration graph, reflecting the required order on indices with respect
42    to the dimensions of each tensor, is constructed to ensure that all tensors
43    are visited in natural index order. Next, iteration lattices are
44    constructed for the tensor expression for every index in topological
45    order. Each iteration lattice point consists of a conjunction of tensor
46    indices together with a tensor (sub)expression that needs to be evaluated
47    for that conjunction.  Within the lattice, iteration points are ordered
48    according to the way indices are exhausted. As such these iteration
49    lattices drive actual sparse code generation, which consists of a
50    relatively straightforward one-to-one mapping from iteration lattices
51    to combinations of for-loops, while-loops, and if-statements. Sparse
52    tensor outputs that materialize uninitialized are handled with
53    insertions in pure lexicographical index order if all parallel loops
54    are outermost or using a 1-dimensional access pattern expansion
55    (a.k.a. workspace) where feasible [Gustavson72,Bik96,Kjolstad19].
56
57    * [Bik96] Aart J.C. Bik. Compiler Support for Sparse Matrix Computations.
58    PhD thesis, Leiden University, May 1996.
59    * [Chou18] Stephen Chou, Fredrik Berg Kjolstad, and Saman Amarasinghe.
60    Format Abstraction for Sparse Tensor Algebra Compilers. Proceedings of
61    the ACM on Programming Languages, October 2018.
62    * [Gustavson72] Fred G. Gustavson. Some basic techniques for solving
63    sparse systems of linear equations. In Sparse Matrices and Their
64    Applications, pages 41–52. Plenum Press, New York, 1972.
65    * [Kjolstad17] Fredrik Berg Kjolstad, Shoaib Ashraf Kamil, Stephen Chou, David
66    Lugato, and Saman Amarasinghe. The Tensor Algebra Compiler. Proceedings of
67    the ACM on Programming Languages, October 2017.
68    * [Kjolstad19] Fredrik Berg Kjolstad, Peter Ahrens, Shoaib Ashraf Kamil,
69    and Saman Amarasinghe. Tensor Algebra Compilation with Workspaces,
70    Proceedings of the IEEE/ACM International Symposium on Code Generation
71    and Optimization, 2019.
72    * [Kjolstad20] Fredrik Berg Kjolstad. Sparse Tensor Algebra Compilation.
73    PhD thesis, MIT, February, 2020.
74  }];
75
76  let useDefaultAttributePrinterParser = 1;
77
78  let emitAccessorPrefix = kEmitAccessorPrefix_Prefixed;
79}
80
81#endif // SPARSETENSOR_BASE
82