MLIR  15.0.0git
Enumerations | Functions
Sparsification.cpp File Reference
#include "CodegenUtils.h"
#include "mlir/Dialect/Affine/IR/AffineOps.h"
#include "mlir/Dialect/Arithmetic/IR/Arithmetic.h"
#include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.h"
#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
#include "mlir/Dialect/Func/IR/FuncOps.h"
#include "mlir/Dialect/LLVMIR/LLVMDialect.h"
#include "mlir/Dialect/Linalg/IR/Linalg.h"
#include "mlir/Dialect/Linalg/Utils/Utils.h"
#include "mlir/Dialect/MemRef/IR/MemRef.h"
#include "mlir/Dialect/SCF/SCF.h"
#include "mlir/Dialect/SCF/Transforms.h"
#include "mlir/Dialect/SparseTensor/IR/SparseTensor.h"
#include "mlir/Dialect/SparseTensor/Transforms/Passes.h"
#include "mlir/Dialect/SparseTensor/Utils/Merger.h"
#include "mlir/Dialect/Vector/IR/VectorOps.h"
#include "mlir/IR/Matchers.h"
#include "mlir/IR/TensorEncoding.h"
#include "llvm/ADT/SmallBitVector.h"
+ Include dependency graph for Sparsification.cpp:

Go to the source code of this file.

Enumerations

enum  SortMask
 
enum  Reduction
 

Functions

static unsigned perm (const SparseTensorEncodingAttr &enc, unsigned d)
 Helper method to apply dimension ordering permutation. More...
 
static Dim toDim (const SparseTensorEncodingAttr &enc, unsigned d)
 Helper method to translate dim level type to internal representation. More...
 
static bool findAffine (Merger &merger, unsigned tensor, AffineExpr a, Dim dim, bool isDense)
 Helper method to inspect affine expressions. More...
 
static bool findSparseAnnotations (Merger &merger, linalg::GenericOp op)
 Helper method to inspect sparse encodings in the tensor types. More...
 
static bool topSortDFS (unsigned i, std::vector< unsigned > &visit, std::vector< unsigned > &topSort, std::vector< std::vector< bool >> &adjM)
 A DFS helper to compute a topological sort. More...
 
static void addAffineOrderings (std::vector< std::vector< bool >> &adjM, AffineExpr a, AffineExpr b, unsigned fidx)
 Helper method to add all constraints from the indices in one affine expression before all indices in the other affine expression. More...
 
static bool computeIterationGraph (Merger &merger, linalg::GenericOp op, std::vector< unsigned > &topSort, unsigned mask)
 Computes a topologically sorted iteration graph for the linalg operation. More...
 
static bool isInPlace (Value val)
 Returns true if tensor has an in-place annotation. More...
 
static bool isMaterializing (Value val)
 Returns true if tensor materializes uninitialized into the computation. More...
 
static bool isAdmissableTensorExp (Merger &merger, linalg::GenericOp op, std::vector< unsigned > &topSort, unsigned exp, OpOperand **sparseOut, unsigned &outerParNest)
 Returns true when the tensor expression is admissable for codegen. More...
 
static vector::CombiningKind getCombiningKind (Reduction kind)
 Maps reduction kind to vector::CombiningKind. More...
 
static Reduction getReduction (Kind kind)
 Maps operation to reduction. More...
 
static Value genVectorReducInit (CodeGen &codegen, OpBuilder &builder, Location loc, VectorType vtp)
 Generates an initial value for a vector reduction, following the scheme given in Chapter 5 of "The Software Vectorization Handbook", where the initial scalar value is correctly embedded in the vector reduction value, and a straightforward horizontal reduction will complete the operation. More...
 
static Value genVectorReducEnd (CodeGen &codegen, OpBuilder &builder, Location loc, VectorType vtp)
 Generates final value for a vector reduction. More...
 
static void updateReduc (Merger &merger, CodeGen &codegen, Value reduc)
 Updates scalarized reduction value. More...
 
static Value genOutputBuffer (CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, MemRefType denseTp, ArrayRef< Value > args)
 Generates buffer for the output tensor. More...
 
static void genBuffers (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op)
 Local bufferization of all dense and sparse data structures. More...
 
static VectorType vectorType (CodeGen &codegen, Type etp)
 Constructs vector type. More...
 
static VectorType vectorType (CodeGen &codegen, Value ptr)
 Constructs vector type from pointer. More...
 
static Value genVectorMask (CodeGen &codegen, OpBuilder &builder, Value iv, Value lo, Value hi, Value step)
 Constructs vector iteration mask. More...
 
static Value genVectorLoad (CodeGen &codegen, OpBuilder &builder, Value ptr, ArrayRef< Value > args)
 Generates a vectorized load lhs = a[ind[lo:hi]] or lhs = a[lo:hi]. More...
 
static void genVectorStore (CodeGen &codegen, OpBuilder &builder, Value rhs, Value ptr, ArrayRef< Value > args)
 Generates a vectorized store a[ind[lo:hi]] = rhs or a[lo:hi] = rhs. More...
 
static Value genVectorInvariantValue (CodeGen &codegen, OpBuilder &builder, Value val)
 Generates a vectorized invariant. More...
 
static Value genAffine (CodeGen &codegen, OpBuilder &builder, AffineExpr a, Location loc)
 Generates an affine expression. More...
 
static Value genIndex (CodeGen &codegen, linalg::GenericOp op, OpOperand *t)
 Generates index for load/store on sparse tensor. More...
 
static Value genSubscript (CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, OpOperand *t, SmallVector< Value, 4 > &args)
 Generates subscript for load/store on a dense or sparse tensor. More...
 
static Value genInsertionLoad (CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, OpOperand *t)
 Generates insertion code to implement dynamic tensor load. More...
 
static void genInsertionStore (CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, OpOperand *t, Value rhs)
 Generates insertion code to implement dynamic tensor store. More...
 
static Value genTensorLoad (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, unsigned exp)
 Generates a load on a dense or sparse tensor. More...
 
static void genTensorStore (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, unsigned exp, Value rhs)
 Generates a store on a dense or sparse tensor. More...
 
static Value genLoad (CodeGen &codegen, OpBuilder &builder, Location loc, Value ptr, Value s)
 Generates a pointer/index load from the sparse storage scheme. More...
 
static Value genInvariantValue (Merger &merger, CodeGen &codegen, OpBuilder &builder, unsigned exp)
 Generates an invariant value. More...
 
static Value genAddress (CodeGen &codegen, OpBuilder &builder, Location loc, Value size, Value p, Value i)
 Generates an address computation "sz * p + i". More...
 
static Value genIndexValue (Merger &merger, CodeGen &codegen, OpBuilder &builder, unsigned exp, unsigned ldx)
 Generates an index value. More...
 
static Value genExp (Merger &merger, CodeGen &codegen, RewriterBase &rewriter, linalg::GenericOp op, unsigned exp, unsigned ldx)
 Recursively generates tensor expression. More...
 
static bool isInvariantAffine (const CodeGen &codegen, AffineExpr a, unsigned ldx, bool &atLevel)
 Determines if affine expression is invariant. More...
 
static void genInvariants (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, unsigned exp, unsigned ldx, bool atStart, Kind last=Kind::kTensor)
 Hoists loop invariant tensor loads for which indices have been exhausted. More...
 
static void genExpansion (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, unsigned at, bool atStart)
 Generates an expanded access pattern in innermost dimension. More...
 
static bool genInit (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, std::vector< unsigned > &topSort, unsigned at, BitVector &inits)
 Generates initialization code for the subsequent loop sequence at current index level. More...
 
static bool isVectorFor (CodeGen &codegen, bool isInner, bool isReduction, bool isSparse)
 Returns vectorization strategy. More...
 
static bool isParallelFor (CodeGen &codegen, bool isOuter, bool isReduction, bool isSparse, bool isVector)
 Returns parallelization strategy. More...
 
static bool denseUnitStrides (Merger &merger, linalg::GenericOp op, unsigned idx)
 Checks unit stride for dense tensors. More...
 
static OperationgenFor (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, bool isOuter, bool isInner, unsigned idx, BitVector &indices)
 Generates a for-loop on a single index. More...
 
static OperationgenWhile (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, unsigned idx, bool needsUniv, BitVector &indices)
 Emit a while-loop for co-iteration over multiple indices. More...
 
static OperationgenLoop (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, std::vector< unsigned > &topSort, unsigned at, bool needsUniv, BitVector &indices)
 Generates a for-loop or a while-loop, depending on whether it implements singleton iteration or co-iteration over the given conjunction. More...
 
static void genLocals (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, std::vector< unsigned > &topSort, unsigned at, bool needsUniv, BitVector &locals)
 Generates the local variables for this loop, consisting of the sparse indices, restored universal dense index, and dense positions. More...
 
static void genWhileInduction (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, unsigned idx, bool needsUniv, BitVector &induction, scf::WhileOp whileOp)
 Generates the induction structure for a while-loop. More...
 
static void genForInduction (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, Operation *loop)
 Generates the induction structure for a for-loop. More...
 
static scf::IfOp genIf (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, unsigned idx, BitVector &conditions)
 Generates a single if-statement within a while-loop. More...
 
static void endIf (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, scf::IfOp ifOp, Operation *loop, Value redInput, Value cntInput)
 Generates end of true branch of if-statement within a while-loop. More...
 
static bool startLoopSeq (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, std::vector< unsigned > &topSort, unsigned exp, unsigned at, unsigned idx, unsigned ldx, unsigned lts)
 Starts a loop sequence at given level. More...
 
static OperationstartLoop (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, std::vector< unsigned > &topSort, unsigned at, unsigned li, bool needsUniv)
 Starts a single loop in current sequence. More...
 
static bool endLoop (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, Operation *loop, unsigned idx, unsigned li, bool needsUniv)
 Ends a single loop in current sequence. Returns new values for needsUniv. More...
 
static void endLoopSeq (Merger &merger, CodeGen &codegen, OpBuilder &builder, linalg::GenericOp op, unsigned exp, unsigned at, unsigned idx, unsigned ldx)
 Ends a loop sequence at given level. More...
 
static void genStmt (Merger &merger, CodeGen &codegen, RewriterBase &rewriter, linalg::GenericOp op, std::vector< unsigned > &topSort, unsigned exp, unsigned at)
 Recursively generates code while computing iteration lattices in order to manage the complexity of implementing co-iteration over unions and intersections of sparse iterations spaces. More...
 
static void genResult (Merger &merger, CodeGen &codegen, RewriterBase &rewriter, linalg::GenericOp op)
 Converts the result computed by the sparse kernel into the required form. More...
 

Enumeration Type Documentation

◆ Reduction

enum Reduction

Definition at line 47 of file Sparsification.cpp.

◆ SortMask

enum SortMask

Definition at line 44 of file Sparsification.cpp.

Function Documentation

◆ addAffineOrderings()

static void addAffineOrderings ( std::vector< std::vector< bool >> &  adjM,
AffineExpr  a,
AffineExpr  b,
unsigned  fidx 
)
static

Helper method to add all constraints from the indices in one affine expression before all indices in the other affine expression.

For example i0+i1 < i2+i3+1 yields i0<i2, i0<i3, i1<i2, and i1<i3.

Definition at line 204 of file Sparsification.cpp.

References mlir::Add, mlir::AffineExpr::cast(), mlir::DimId, mlir::AffineExpr::getKind(), and mlir::Mul.

Referenced by computeIterationGraph().

◆ computeIterationGraph()

static bool computeIterationGraph ( Merger merger,
linalg::GenericOp  op,
std::vector< unsigned > &  topSort,
unsigned  mask 
)
static

Computes a topologically sorted iteration graph for the linalg operation.

Ensures all tensors are visited in natural index order. This is essential for sparse storage formats since these only support access along fixed dimensions. Even for dense storage formats, however, the natural index order yields innermost unit-stride access with better spatial locality.

Definition at line 232 of file Sparsification.cpp.

References addAffineOrderings(), mlir::sparse_tensor::getSparseTensorEncoding(), mlir::sparse_tensor::Merger::isDim(), mlir::sparse_tensor::kSparse, mlir::sparse_tensor::kUndef, perm(), topSortDFS(), and visit().

◆ denseUnitStrides()

static bool denseUnitStrides ( Merger merger,
linalg::GenericOp  op,
unsigned  idx 
)
static

Checks unit stride for dense tensors.

The iteration graph may have ignored dense access patterns in order to avoid cycles (sparse access patterns are always placed innermost), but that means dense access has become strided. This prevents effective vectorization.

Definition at line 1133 of file Sparsification.cpp.

References mlir::DimId, mlir::AffineExpr::getKind(), mlir::sparse_tensor::getSparseTensorEncoding(), and mlir::AffineExpr::isFunctionOfDim().

Referenced by genFor().

◆ endIf()

static void endIf ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
scf::IfOp  ifOp,
Operation loop,
Value  redInput,
Value  cntInput 
)
static

Generates end of true branch of if-statement within a while-loop.

Definition at line 1490 of file Sparsification.cpp.

References mlir::OpBuilder::create(), mlir::OpBuilder::setInsertionPointToStart(), and updateReduc().

◆ endLoop()

static bool endLoop ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
Operation loop,
unsigned  idx,
unsigned  li,
bool  needsUniv 
)
static

Ends a single loop in current sequence. Returns new values for needsUniv.

Definition at line 1556 of file Sparsification.cpp.

References mlir::sparse_tensor::LatPoint::bits, genForInduction(), genWhileInduction(), and mlir::sparse_tensor::Merger::lat().

◆ endLoopSeq()

static void endLoopSeq ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
unsigned  exp,
unsigned  at,
unsigned  idx,
unsigned  ldx 
)
static

Ends a loop sequence at given level.

Definition at line 1572 of file Sparsification.cpp.

References genExpansion(), genInvariants(), genVectorReducEnd(), and updateReduc().

◆ findAffine()

static bool findAffine ( Merger merger,
unsigned  tensor,
AffineExpr  a,
Dim  dim,
bool  isDense 
)
static

Helper method to inspect affine expressions.

Rejects cases where the same index is used more than once. Also rejects affine expressions that are not a direct index for annotated tensors.

Definition at line 135 of file Sparsification.cpp.

References mlir::Add, mlir::AffineExpr::cast(), mlir::Constant, mlir::DimId, mlir::AffineExpr::getKind(), mlir::sparse_tensor::Merger::isDim(), mlir::sparse_tensor::kUndef, mlir::Mul, and mlir::sparse_tensor::Merger::setDim().

Referenced by findSparseAnnotations().

◆ findSparseAnnotations()

static bool findSparseAnnotations ( Merger merger,
linalg::GenericOp  op 
)
static

Helper method to inspect sparse encodings in the tensor types.

Fills the per-dimension sparsity information for all tensors. Returns true if the sparse annotations and affine subscript expressions of all tensors are admissable. Returns false if no annotations are found or inadmissable constructs occur.

Definition at line 165 of file Sparsification.cpp.

References findAffine(), mlir::sparse_tensor::getSparseTensorEncoding(), perm(), and toDim().

◆ genAddress()

static Value genAddress ( CodeGen &  codegen,
OpBuilder builder,
Location  loc,
Value  size,
Value  p,
Value  i 
)
static

Generates an address computation "sz * p + i".

Definition at line 872 of file Sparsification.cpp.

References mlir::OpBuilder::create(), mlir::Type::dyn_cast(), genVectorInvariantValue(), and mlir::Value::getType().

Referenced by genLocals().

◆ genAffine()

static Value genAffine ( CodeGen &  codegen,
OpBuilder builder,
AffineExpr  a,
Location  loc 
)
static

◆ genBuffers()

static void genBuffers ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op 
)
static

◆ genExp()

static Value genExp ( Merger merger,
CodeGen &  codegen,
RewriterBase rewriter,
linalg::GenericOp  op,
unsigned  exp,
unsigned  ldx 
)
static

◆ genExpansion()

static void genExpansion ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
unsigned  at,
bool  atStart 
)
static

Generates an expanded access pattern in innermost dimension.

Definition at line 1010 of file Sparsification.cpp.

Referenced by endLoopSeq(), and startLoopSeq().

◆ genFor()

static Operation* genFor ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
bool  isOuter,
bool  isInner,
unsigned  idx,
BitVector &  indices 
)
static

◆ genForInduction()

static void genForInduction ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
Operation loop 
)
static

Generates the induction structure for a for-loop.

Definition at line 1437 of file Sparsification.cpp.

References mlir::OpBuilder::create(), mlir::Operation::getResult(), mlir::OpBuilder::setInsertionPointAfter(), and updateReduc().

Referenced by endLoop().

◆ genIf()

static scf::IfOp genIf ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
unsigned  idx,
BitVector &  conditions 
)
static

◆ genIndex()

static Value genIndex ( CodeGen &  codegen,
linalg::GenericOp  op,
OpOperand t 
)
static

◆ genIndexValue()

static Value genIndexValue ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
unsigned  exp,
unsigned  ldx 
)
static

◆ genInit()

static bool genInit ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
std::vector< unsigned > &  topSort,
unsigned  at,
BitVector &  inits 
)
static

Generates initialization code for the subsequent loop sequence at current index level.

Returns true if the loop sequence needs to maintain the universal index.

Definition at line 1047 of file Sparsification.cpp.

References mlir::sparse_tensor::constantIndex(), mlir::OpBuilder::create(), genLoad(), mlir::sparse_tensor::Merger::index(), mlir::sparse_tensor::Merger::isDim(), mlir::sparse_tensor::kSparse, and mlir::sparse_tensor::Merger::tensor().

Referenced by startLoopSeq().

◆ genInsertionLoad()

static Value genInsertionLoad ( CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
OpOperand t 
)
static

◆ genInsertionStore()

static void genInsertionStore ( CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
OpOperand t,
Value  rhs 
)
static

Generates insertion code to implement dynamic tensor store.

Definition at line 721 of file Sparsification.cpp.

◆ genInvariants()

static void genInvariants ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
unsigned  exp,
unsigned  ldx,
bool  atStart,
Kind  last = Kind::kTensor 
)
static

◆ genInvariantValue()

static Value genInvariantValue ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
unsigned  exp 
)
static

Generates an invariant value.

Definition at line 863 of file Sparsification.cpp.

References mlir::sparse_tensor::Merger::exp(), genVectorInvariantValue(), and mlir::sparse_tensor::TensorExp::val.

Referenced by genExp().

◆ genLoad()

static Value genLoad ( CodeGen &  codegen,
OpBuilder builder,
Location  loc,
Value  ptr,
Value  s 
)
static

Generates a pointer/index load from the sparse storage scheme.

Narrower data types need to be zero extended before casting the value into the index type used for looping and indexing.

Definition at line 819 of file Sparsification.cpp.

References mlir::Type::cast(), mlir::OpBuilder::create(), genVectorLoad(), getElementType(), mlir::Builder::getI32Type(), mlir::Builder::getI64Type(), mlir::Builder::getIndexType(), mlir::Type::getIntOrFloatBitWidth(), mlir::Value::getType(), mlir::Type::isa(), and vectorType().

Referenced by genInit(), and genLocals().

◆ genLocals()

static void genLocals ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
std::vector< unsigned > &  topSort,
unsigned  at,
bool  needsUniv,
BitVector &  locals 
)
static

Generates the local variables for this loop, consisting of the sparse indices, restored universal dense index, and dense positions.

Definition at line 1308 of file Sparsification.cpp.

References mlir::sparse_tensor::constantIndex(), mlir::OpBuilder::create(), genAddress(), genLoad(), mlir::sparse_tensor::Merger::index(), mlir::sparse_tensor::Merger::isDim(), mlir::sparse_tensor::Merger::isOutTensor(), mlir::sparse_tensor::kSparse, min(), and mlir::sparse_tensor::Merger::tensor().

Referenced by startLoop().

◆ genLoop()

static Operation* genLoop ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
std::vector< unsigned > &  topSort,
unsigned  at,
bool  needsUniv,
BitVector &  indices 
)
static

Generates a for-loop or a while-loop, depending on whether it implements singleton iteration or co-iteration over the given conjunction.

Definition at line 1294 of file Sparsification.cpp.

References genFor(), and genWhile().

Referenced by startLoop().

◆ genOutputBuffer()

static Value genOutputBuffer ( CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
MemRefType  denseTp,
ArrayRef< Value args 
)
static

Generates buffer for the output tensor.

Note that all sparse kernels assume that when all elements are written to (viz. x(i) = y(i) * z(i)), the output buffer is already initialized to all zeroes and only nonzeroes values are computed and written out. For updates (viz. x(i) += y(i) * z(i)), only nonzeroes values are used for the updates and no assumption on the original contents of the output buffer is necessary..

Definition at line 453 of file Sparsification.cpp.

References mlir::sparse_tensor::constantZero(), mlir::OpBuilder::create(), isInPlace(), and isMaterializing().

Referenced by genBuffers().

◆ genResult()

static void genResult ( Merger merger,
CodeGen &  codegen,
RewriterBase rewriter,
linalg::GenericOp  op 
)
static

Converts the result computed by the sparse kernel into the required form.

Definition at line 1650 of file Sparsification.cpp.

◆ genStmt()

static void genStmt ( Merger merger,
CodeGen &  codegen,
RewriterBase rewriter,
linalg::GenericOp  op,
std::vector< unsigned > &  topSort,
unsigned  exp,
unsigned  at 
)
static

Recursively generates code while computing iteration lattices in order to manage the complexity of implementing co-iteration over unions and intersections of sparse iterations spaces.

Definition at line 1591 of file Sparsification.cpp.

◆ genSubscript()

static Value genSubscript ( CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
OpOperand t,
SmallVector< Value, 4 > &  args 
)
static

◆ genTensorLoad()

static Value genTensorLoad ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
unsigned  exp 
)
static

◆ genTensorStore()

static void genTensorStore ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
unsigned  exp,
Value  rhs 
)
static

Generates a store on a dense or sparse tensor.

Definition at line 784 of file Sparsification.cpp.

◆ genVectorInvariantValue()

static Value genVectorInvariantValue ( CodeGen &  codegen,
OpBuilder builder,
Value  val 
)
static

Generates a vectorized invariant.

Here we rely on subsequent loop optimizations to hoist the invariant broadcast out of the vector loop.

Definition at line 633 of file Sparsification.cpp.

References mlir::OpBuilder::create(), mlir::Value::getLoc(), mlir::Value::getType(), and vectorType().

Referenced by genAddress(), genInvariantValue(), and genTensorLoad().

◆ genVectorLoad()

static Value genVectorLoad ( CodeGen &  codegen,
OpBuilder builder,
Value  ptr,
ArrayRef< Value args 
)
static

Generates a vectorized load lhs = a[ind[lo:hi]] or lhs = a[lo:hi].

Definition at line 599 of file Sparsification.cpp.

References mlir::sparse_tensor::constantIndex(), mlir::sparse_tensor::constantZero(), mlir::OpBuilder::create(), mlir::Value::getLoc(), and vectorType().

Referenced by genLoad(), and genTensorLoad().

◆ genVectorMask()

static Value genVectorMask ( CodeGen &  codegen,
OpBuilder builder,
Value  iv,
Value  lo,
Value  hi,
Value  step 
)
static

◆ genVectorReducEnd()

static Value genVectorReducEnd ( CodeGen &  codegen,
OpBuilder builder,
Location  loc,
VectorType  vtp 
)
static

Generates final value for a vector reduction.

Definition at line 431 of file Sparsification.cpp.

Referenced by endLoopSeq().

◆ genVectorReducInit()

static Value genVectorReducInit ( CodeGen &  codegen,
OpBuilder builder,
Location  loc,
VectorType  vtp 
)
static

Generates an initial value for a vector reduction, following the scheme given in Chapter 5 of "The Software Vectorization Handbook", where the initial scalar value is correctly embedded in the vector reduction value, and a straightforward horizontal reduction will complete the operation.

Definition at line 406 of file Sparsification.cpp.

References mlir::sparse_tensor::constantIndex(), mlir::sparse_tensor::constantOne(), mlir::sparse_tensor::constantZero(), and mlir::OpBuilder::create().

Referenced by genFor().

◆ genVectorStore()

static void genVectorStore ( CodeGen &  codegen,
OpBuilder builder,
Value  rhs,
Value  ptr,
ArrayRef< Value args 
)
static

Generates a vectorized store a[ind[lo:hi]] = rhs or a[lo:hi] = rhs.

Definition at line 616 of file Sparsification.cpp.

◆ genWhile()

static Operation* genWhile ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
unsigned  idx,
bool  needsUniv,
BitVector &  indices 
)
static

◆ genWhileInduction()

static void genWhileInduction ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
unsigned  idx,
bool  needsUniv,
BitVector &  induction,
scf::WhileOp  whileOp 
)
static

◆ getCombiningKind()

static vector::CombiningKind getCombiningKind ( Reduction  kind)
static

Maps reduction kind to vector::CombiningKind.

Definition at line 359 of file Sparsification.cpp.

◆ getReduction()

static Reduction getReduction ( Kind  kind)
static

Maps operation to reduction.

Definition at line 378 of file Sparsification.cpp.

◆ isAdmissableTensorExp()

static bool isAdmissableTensorExp ( Merger merger,
linalg::GenericOp  op,
std::vector< unsigned > &  topSort,
unsigned  exp,
OpOperand **  sparseOut,
unsigned outerParNest 
)
static

Returns true when the tensor expression is admissable for codegen.

Since all sparse input tensors are admissable, we just need to check whether the out tensor in the tensor expression codegen is admissable. Sets sparseOut to the tensor and outerParNest to the outer injective nesting depth when a "truly dynamic" sparse tensor output occurs.

Definition at line 304 of file Sparsification.cpp.

◆ isInPlace()

static bool isInPlace ( Value  val)
static

◆ isInvariantAffine()

static bool isInvariantAffine ( const CodeGen &  codegen,
AffineExpr  a,
unsigned  ldx,
bool &  atLevel 
)
static

Determines if affine expression is invariant.

Definition at line 936 of file Sparsification.cpp.

References mlir::Add, mlir::AffineExpr::cast(), mlir::DimId, mlir::AffineExpr::getKind(), and mlir::Mul.

Referenced by genInvariants().

◆ isMaterializing()

static bool isMaterializing ( Value  val)
static

Returns true if tensor materializes uninitialized into the computation.

Definition at line 294 of file Sparsification.cpp.

References mlir::Value::getDefiningOp().

Referenced by genOutputBuffer().

◆ isParallelFor()

static bool isParallelFor ( CodeGen &  codegen,
bool  isOuter,
bool  isReduction,
bool  isSparse,
bool  isVector 
)
static

Returns parallelization strategy.

Any implicit loop in the Linalg operation that is marked "parallel" is a candidate. Whether it is actually converted to a parallel operation depends on the requested strategy.

Definition at line 1108 of file Sparsification.cpp.

References mlir::kAnyStorageAnyLoop, mlir::kAnyStorageOuterLoop, mlir::kDenseAnyLoop, mlir::kDenseOuterLoop, and mlir::kNone.

Referenced by genFor().

◆ isVectorFor()

static bool isVectorFor ( CodeGen &  codegen,
bool  isInner,
bool  isReduction,
bool  isSparse 
)
static

Returns vectorization strategy.

Any implicit inner loop in the Linalg operation is a candidate. Whether it is actually converted to SIMD code depends on the requested strategy.

Definition at line 1088 of file Sparsification.cpp.

References mlir::kAnyStorageInnerLoop, mlir::kDenseInnerLoop, and mlir::kNone.

Referenced by genFor().

◆ perm()

static unsigned perm ( const SparseTensorEncodingAttr &  enc,
unsigned  d 
)
static

◆ startLoop()

static Operation* startLoop ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
std::vector< unsigned > &  topSort,
unsigned  at,
unsigned  li,
bool  needsUniv 
)
static

◆ startLoopSeq()

static bool startLoopSeq ( Merger merger,
CodeGen &  codegen,
OpBuilder builder,
linalg::GenericOp  op,
std::vector< unsigned > &  topSort,
unsigned  exp,
unsigned  at,
unsigned  idx,
unsigned  ldx,
unsigned  lts 
)
static

◆ toDim()

static Dim toDim ( const SparseTensorEncodingAttr &  enc,
unsigned  d 
)
static

Helper method to translate dim level type to internal representation.

Definition at line 120 of file Sparsification.cpp.

References mlir::sparse_tensor::kSingle, and mlir::sparse_tensor::kSparse.

Referenced by findSparseAnnotations().

◆ topSortDFS()

static bool topSortDFS ( unsigned  i,
std::vector< unsigned > &  visit,
std::vector< unsigned > &  topSort,
std::vector< std::vector< bool >> &  adjM 
)
static

A DFS helper to compute a topological sort.

Note that recursion is bounded by the number of implicit loops, which is always small. Returns false when a cycle is detected.

Definition at line 186 of file Sparsification.cpp.

Referenced by computeIterationGraph().

◆ updateReduc()

static void updateReduc ( Merger merger,
CodeGen &  codegen,
Value  reduc 
)
static

Updates scalarized reduction value.

Definition at line 438 of file Sparsification.cpp.

References mlir::sparse_tensor::Merger::exp(), and mlir::sparse_tensor::TensorExp::val.

Referenced by endIf(), endLoopSeq(), genFor(), genForInduction(), genWhile(), and genWhileInduction().

◆ vectorType() [1/2]

static VectorType vectorType ( CodeGen &  codegen,
Type  etp 
)
static

◆ vectorType() [2/2]

static VectorType vectorType ( CodeGen &  codegen,
Value  ptr 
)
static

Constructs vector type from pointer.

Definition at line 563 of file Sparsification.cpp.

References mlir::Type::cast(), getElementType(), mlir::Value::getType(), and vectorType().