//===- SparseTensorBase.td - Sparse tensor dialect base ----*- tablegen -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef SPARSETENSOR_BASE
#define SPARSETENSOR_BASE

include "mlir/IR/OpBase.td"

def SparseTensor_Dialect : Dialect {
  let name = "sparse_tensor";
  let cppNamespace = "::mlir::sparse_tensor";
  let description = [{
    The `SparseTensor` dialect supports all the attributes, types,
    operations, and passes that are required to make sparse tensor
    types first class citizens within the MLIR compiler infrastructure.
    The dialect forms a bridge between high-level operations on sparse
    tensors types and lower-level operations on the actual sparse storage
    schemes consisting of pointers, indices, and values. Lower-level
    support may consist of fully generated code or may be provided by
    means of a small sparse runtime support library.

    The concept of **treating sparsity as a property, not a tedious
    implementation detail**, by letting a **sparse compiler** generate
    sparse code automatically was pioneered for dense linear algebra by
    [Bik96] in MT1 (see https://www.aartbik.com/sparse.php) and formalized
    to tensor algebra by [Kjolstad17,Kjolstad20] in the Sparse Tensor
    Algebra Compiler (TACO) project (see http://tensor-compiler.org).

    The MLIR implementation closely follows the "sparse iteration theory"
    that forms the foundation of TACO. A rewriting rule is applied to each
    tensor expression in the Linalg dialect (MLIR's tensor index notation)
    where the sparsity of tensors is indicated using the per-dimension level
    types dense/compressed together with a specification of the order on the
    dimensions (see [Chou18] for an in-depth discussions and possible
    extensions to these level types). Subsequently, a topologically sorted
    iteration graph, reflecting the required order on indices with respect
    to the dimensions of each tensor, is constructed to ensure that all tensors
    are visited in natural index order. Next, iteration lattices are
    constructed for the tensor expression for every index in topological
    order. Each iteration lattice point consists of a conjunction of tensor
    indices together with a tensor (sub)expression that needs to be evaluated
    for that conjunction.  Within the lattice, iteration points are ordered
    according to the way indices are exhausted. As such these iteration
    lattices drive actual sparse code generation, which consists of a
    relatively straightforward one-to-one mapping from iteration lattices
    to combinations of for-loops, while-loops, and if-statements.

    * [Bik96] Aart J.C. Bik. Compiler Support for Sparse Matrix Computations.
    PhD thesis, Leiden University, May 1996.
    * [Kjolstad17] Fredrik Berg Kjolstad, Shoaib Ashraf Kamil, Stephen Chou, David
    Lugato, and Saman Amarasinghe. The Tensor Algebra Compiler. Proceedings of
    the ACM on Programming Languages, October 2017.
    * [Kjolstad20] Fredrik Berg Kjolstad. Sparse Tensor Algebra Compilation.
    PhD thesis, MIT, February, 2020.
    * [Chou18] Stephen Chou, Fredrik Berg Kjolstad, and Saman Amarasinghe.
    Format Abstraction for Sparse Tensor Algebra Compilers. Proceedings of
    the ACM on Programming Languages, October 2018.
  }];
}

#endif // SPARSETENSOR_BASE