#include "mlir/Dialect/Linalg/Passes.h"
#include "mlir/Dialect/Affine/IR/AffineOps.h"
#include "mlir/Dialect/Arith/Utils/Utils.h"
#include "mlir/Dialect/Linalg/IR/Linalg.h"
#include "mlir/Dialect/Linalg/Transforms/Transforms.h"
#include "mlir/Dialect/SparseTensor/IR/SparseTensor.h"
#include "mlir/IR/AffineExpr.h"
#include "mlir/IR/AffineMap.h"
#include "mlir/IR/Matchers.h"
#include "mlir/IR/PatternMatch.h"
#include "mlir/Support/LLVM.h"
#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
#include <optional>
#include <utility>
#include "mlir/Dialect/Linalg/Passes.h.inc"

Namespaces
	mlir
	Include the generated interface declarations.

Macros
#define	GEN_PASS_DEF_LINALGELEMENTWISEOPFUSIONPASS

Functions
static AffineMap	getIndexingMapOfProducerOperandsInCoordinatesOfFusedOp (OpOperand *producerOpOperand, AffineMap producerResultIndexMap, AffineMap fusedConsumerArgIndexMap)
	Append to `fusedOpIndexingMapAttrs` the indexing maps for the operands of the `producer` to use in the fused operation given the indexing map of the result of the producer in the consumer. More...

static void	generateFusedElementwiseOpRegion (RewriterBase &rewriter, GenericOp fusedOp, AffineMap consumerToProducerLoopsMap, OpOperand *fusedOperand, unsigned nloops, llvm::SmallDenseSet< int > &preservedProducerResults)
	Generate the region of the fused tensor operation. More...

static bool	isFusableWithReshapeByDimExpansion (LinalgOp linalgOp, OpOperand *fusableOpOperand)
	Conditions for folding a structured linalg operation with a reshape op by expanding the iteration space dimensionality for tensor operations. More...

static LogicalResult	isLinalgOpExpandable (LinalgOp linalgOp, const ExpansionInfo &expansionInfo, PatternRewriter &rewriter)
	Epanding the body of a linalg operation requires adaptations of the accessed loop indices. More...

static AffineMap	getIndexingMapInExpandedOp (OpBuilder &builder, AffineMap indexingMap, const ExpansionInfo &expansionInfo)
	Return the indexing map to use in the expanded op for a given the `indexingMap` of the original operation. More...

static RankedTensorType	getExpandedType (RankedTensorType originalType, AffineMap indexingMap, const ExpansionInfo &expansionInfo)
	Return the type of the operand/result to use in the expanded op given the type in the original op. More...

static SmallVector< ReassociationIndices >	getReassociationForExpansion (AffineMap indexingMap, const ExpansionInfo &expansionInfo)
	Returns the reassociation maps to use in the `tensor.expand_shape` operation to convert the operands of the original operation to operands of the expanded operation. More...

static void	updateExpandedGenericOpRegion (PatternRewriter &rewriter, Location loc, Region &fusedRegion, const ExpansionInfo &expansionInfo)
	Update the body of an expanded linalg operation having index semantics. More...

static std::optional< SmallVector< Value > >	fuseWithReshapeByExpansion (LinalgOp linalgOp, Operation reshapeOp, OpOperand fusableOpOperand, PatternRewriter &rewriter)
	Implements the fusion of a tensor.collapse_shape or a tensor.expand_shape op and a generic op as explained in `isFusableWithReshapeByExpansion`. More...

static ReassociationIndices	getDomainReassociation (AffineMap indexingMap, ReassociationIndicesRef rangeReassociation)
	For a given list of indices in the range of the `indexingMap` that are folded, return the indices of the corresponding domain. More...

static SmallVector< ReassociationIndices >	getCollapsableIterationSpaceDims (GenericOp genericOp, OpOperand *fusableOperand, ArrayRef< ReassociationIndices > reassociation)

static SmallVector< utils::IteratorType >	getCollapsedOpIteratorTypes (ArrayRef< utils::IteratorType > iteratorTypes, const CollapsingInfo &collapsingInfo)
	Get the iterator types for the collapsed operation given the original iterator types and collapsed dimensions. More...

static AffineMap	getCollapsedOpIndexingMap (AffineMap indexingMap, const CollapsingInfo &collapsingInfo)
	Compute the indexing map in the collapsed op that corresponds to the given `indexingMap` of the original operation. More...

static SmallVector< ReassociationIndices >	getOperandReassociation (AffineMap indexingMap, const CollapsingInfo &collapsingInfo)
	Return the `reassociation` indices to use to collapse the operand when the iteration space of a generic op is collapsed. More...

static Value	getCollapsedOpOperand (Location loc, LinalgOp op, OpOperand *opOperand, const CollapsingInfo &collapsingInfo, OpBuilder &builder)
	Get the new value to use for a given `OpOperand` in the collapsed operation. More...

void	generateCollapsedIndexingRegion (Location loc, Block *block, const CollapsingInfo &collapsingInfo, ValueRange loopRange, RewriterBase &rewriter)
	Modify the `linalg.index` operations in the original generic op, to its value in the collapsed operation. More...

void	collapseOperandsAndResults (LinalgOp op, const CollapsingInfo &collapsingInfo, RewriterBase &rewriter, SmallVectorImpl< Value > &inputOperands, SmallVectorImpl< Value > &outputOperands, SmallVectorImpl< Type > &resultTypes)

template<typename OpTy >
OpTy	cloneToCollapsedOp (RewriterBase &rewriter, OpTy origOp, const CollapsingInfo &collapsingInfo)
	Clone a `LinalgOp` to a collapsed version of same name. More...

template<>
LinalgOp	cloneToCollapsedOp< LinalgOp > (RewriterBase &rewriter, LinalgOp origOp, const CollapsingInfo &collapsingInfo)
	Collapse any `LinalgOp` that does not require any specialization such as indexing_maps, iterator_types, etc. More...

template<>
GenericOp	cloneToCollapsedOp< GenericOp > (RewriterBase &rewriter, GenericOp origOp, const CollapsingInfo &collapsingInfo)
	Collapse a `GenericOp` More...

LinalgOp	createCollapsedOp (LinalgOp op, const CollapsingInfo &collapsingInfo, RewriterBase &rewriter)

Macro Definition Documentation

◆ GEN_PASS_DEF_LINALGELEMENTWISEOPFUSIONPASS

#define GEN_PASS_DEF_LINALGELEMENTWISEOPFUSIONPASS

Definition at line 30 of file ElementwiseOpFusion.cpp.

Function Documentation

◆ cloneToCollapsedOp()

template<typename OpTy >

OpTy cloneToCollapsedOp	(	RewriterBase &	rewriter,
		OpTy	origOp,
		const CollapsingInfo &	collapsingInfo
	)

Clone a LinalgOp to a collapsed version of same name.

Definition at line 1486 of file ElementwiseOpFusion.cpp.

◆ cloneToCollapsedOp< GenericOp >()

template<>

GenericOp cloneToCollapsedOp< GenericOp >	(	RewriterBase &	rewriter,
		GenericOp	origOp,
		const CollapsingInfo &	collapsingInfo
	)

Collapse a GenericOp

Definition at line 1508 of file ElementwiseOpFusion.cpp.

References collapseOperandsAndResults(), mlir::OpBuilder::create(), mlir::Block::front(), mlir::Block::getArguments(), getCollapsedOpIteratorTypes(), and mlir::RewriterBase::mergeBlocks().

◆ cloneToCollapsedOp< LinalgOp >()

template<>

LinalgOp cloneToCollapsedOp< LinalgOp >	(	RewriterBase &	rewriter,
		LinalgOp	origOp,
		const CollapsingInfo &	collapsingInfo
	)

Collapse any LinalgOp that does not require any specialization such as indexing_maps, iterator_types, etc.

Definition at line 1494 of file ElementwiseOpFusion.cpp.

References mlir::clone(), and collapseOperandsAndResults().

◆ collapseOperandsAndResults()

void collapseOperandsAndResults	(	LinalgOp	op,
		const CollapsingInfo &	collapsingInfo,
		RewriterBase &	rewriter,
		SmallVectorImpl< Value > &	inputOperands,
		SmallVectorImpl< Value > &	outputOperands,
		SmallVectorImpl< Type > &	resultTypes
	)

Definition at line 1457 of file ElementwiseOpFusion.cpp.

Referenced by cloneToCollapsedOp< GenericOp >(), and cloneToCollapsedOp< LinalgOp >().

◆ createCollapsedOp()

LinalgOp createCollapsedOp	(	LinalgOp	op,
		const CollapsingInfo &	collapsingInfo,
		RewriterBase &	rewriter
	)

Definition at line 1533 of file ElementwiseOpFusion.cpp.

◆ fuseWithReshapeByExpansion()

static std::optional<SmallVector<Value> > fuseWithReshapeByExpansion	(	LinalgOp	linalgOp,
		Operation *	reshapeOp,
		OpOperand *	fusableOpOperand,
		PatternRewriter &	rewriter
	)

static

Implements the fusion of a tensor.collapse_shape or a tensor.expand_shape op and a generic op as explained in isFusableWithReshapeByExpansion.

Assumes that those conditions have been satisfied.

Definition at line 757 of file ElementwiseOpFusion.cpp.

References mlir::Region::begin(), mlir::OpBuilder::cloneRegionBefore(), mlir::OpBuilder::create(), mlir::detail::enumerate(), mlir::failed(), getExpandedType(), getReassociationForExpansion(), mlir::ValueRange::getTypes(), isFusableWithReshapeByDimExpansion(), isLinalgOpExpandable(), mlir::RewriterBase::notifyMatchFailure(), mlir::reshapeLikeShapesAreCompatible(), mlir::OpBuilder::setInsertionPoint(), and updateExpandedGenericOpRegion().

◆ generateCollapsedIndexingRegion()

void generateCollapsedIndexingRegion	(	Location	loc,
		Block *	block,
		const CollapsingInfo &	collapsingInfo,
		ValueRange	loopRange,
		RewriterBase &	rewriter
	)

Modify the linalg.index operations in the original generic op, to its value in the collapsed operation.

Definition at line 1419 of file ElementwiseOpFusion.cpp.

References mlir::OpBuilder::create(), mlir::detail::enumerate(), mlir::Block::getOps(), mlir::RewriterBase::replaceOp(), and mlir::OpBuilder::setInsertionPointToStart().

◆ generateFusedElementwiseOpRegion()

static void generateFusedElementwiseOpRegion	(	RewriterBase &	rewriter,
		GenericOp	fusedOp,
		AffineMap	consumerToProducerLoopsMap,
		OpOperand *	fusedOperand,
		unsigned	nloops,
		llvm::SmallDenseSet< int > &	preservedProducerResults
	)

static

Generate the region of the fused tensor operation.

The region of the fused op must be empty.

Definition at line 171 of file ElementwiseOpFusion.cpp.

References mlir::Block::addArgument(), mlir::OpBuilder::create(), mlir::OpBuilder::createBlock(), mlir::detail::enumerate(), mlir::Block::front(), mlir::IROperand< DerivedT, IRValueT >::get(), mlir::Block::getArguments(), mlir::Value::getDefiningOp(), mlir::OpOperand::getOperandNumber(), mlir::Block::getOps(), mlir::detail::IROperandBase::getOwner(), mlir::AffineMap::getSubMap(), mlir::IRMapping::map(), and max().

Referenced by mlir::linalg::fuseElementwiseOps().

◆ getCollapsableIterationSpaceDims()

static SmallVector<ReassociationIndices> getCollapsableIterationSpaceDims	(	GenericOp	genericOp,
		OpOperand *	fusableOperand,
		ArrayRef< ReassociationIndices >	reassociation
	)

static

Definition at line 1129 of file ElementwiseOpFusion.cpp.

References mlir::detail::enumerate(), getDomainReassociation(), mlir::linalg::isParallelIterator(), and mlir::linalg::isReductionIterator().

◆ getCollapsedOpIndexingMap()

static AffineMap getCollapsedOpIndexingMap	(	AffineMap	indexingMap,
		const CollapsingInfo &	collapsingInfo
	)

static

Compute the indexing map in the collapsed op that corresponds to the given indexingMap of the original operation.

Definition at line 1339 of file ElementwiseOpFusion.cpp.

References mlir::AffineMap::get(), mlir::getAffineDimExpr(), mlir::AffineMap::getContext(), mlir::AffineMap::getResults(), and mlir::AffineMap::isProjectedPermutation().

◆ getCollapsedOpIteratorTypes()

static SmallVector<utils::IteratorType> getCollapsedOpIteratorTypes	(	ArrayRef< utils::IteratorType >	iteratorTypes,
		const CollapsingInfo &	collapsingInfo
	)

static

Get the iterator types for the collapsed operation given the original iterator types and collapsed dimensions.

Definition at line 1321 of file ElementwiseOpFusion.cpp.

Referenced by cloneToCollapsedOp< GenericOp >().

◆ getCollapsedOpOperand()

static Value getCollapsedOpOperand	(	Location	loc,
		LinalgOp	op,
		OpOperand *	opOperand,
		const CollapsingInfo &	collapsingInfo,
		OpBuilder &	builder
	)

static

Get the new value to use for a given OpOperand in the collapsed operation.

Definition at line 1391 of file ElementwiseOpFusion.cpp.

◆ getDomainReassociation()

static ReassociationIndices getDomainReassociation	(	AffineMap	indexingMap,
		ReassociationIndicesRef	rangeReassociation
	)

static

For a given list of indices in the range of the indexingMap that are folded, return the indices of the corresponding domain.

Return std::nullopt on failure. Ensures that all the elements of the returned reassociation are distinct.

Definition at line 1015 of file ElementwiseOpFusion.cpp.

References mlir::AffineMap::getResults(), and mlir::AffineMap::isProjectedPermutation().

Referenced by getCollapsableIterationSpaceDims().

◆ getExpandedType()

static RankedTensorType getExpandedType	(	RankedTensorType	originalType,
		AffineMap	indexingMap,
		const ExpansionInfo &	expansionInfo
	)

static

Return the type of the operand/result to use in the expanded op given the type in the original op.

Definition at line 676 of file ElementwiseOpFusion.cpp.

References mlir::get(), and mlir::AffineMap::getResults().

Referenced by fuseWithReshapeByExpansion().

◆ getIndexingMapInExpandedOp()

static AffineMap getIndexingMapInExpandedOp	(	OpBuilder &	builder,
		AffineMap	indexingMap,
		const ExpansionInfo &	expansionInfo
	)

static

Return the indexing map to use in the expanded op for a given the indexingMap of the original operation.

Definition at line 658 of file ElementwiseOpFusion.cpp.

References mlir::AffineMap::get(), mlir::Builder::getContext(), mlir::AffineMap::getNumSymbols(), and mlir::AffineMap::getResults().

◆ getIndexingMapOfProducerOperandsInCoordinatesOfFusedOp()

static AffineMap getIndexingMapOfProducerOperandsInCoordinatesOfFusedOp	(	OpOperand *	producerOpOperand,
		AffineMap	producerResultIndexMap,
		AffineMap	fusedConsumerArgIndexMap
	)

static

Append to fusedOpIndexingMapAttrs the indexing maps for the operands of the producer to use in the fused operation given the indexing map of the result of the producer in the consumer.

Definition at line 44 of file ElementwiseOpFusion.cpp.

References mlir::AffineMap::compose(), mlir::detail::IROperandBase::getOwner(), and mlir::inversePermutation().

Referenced by mlir::linalg::areElementwiseOpsFusable(), and mlir::linalg::fuseElementwiseOps().

◆ getOperandReassociation()

static SmallVector<ReassociationIndices> getOperandReassociation	(	AffineMap	indexingMap,
		const CollapsingInfo &	collapsingInfo
	)

static

Return the reassociation indices to use to collapse the operand when the iteration space of a generic op is collapsed.

Definition at line 1364 of file ElementwiseOpFusion.cpp.

References mlir::AffineMap::getNumResults(), and mlir::AffineMap::getResult().

◆ getReassociationForExpansion()

static SmallVector<ReassociationIndices> getReassociationForExpansion	(	AffineMap	indexingMap,
		const ExpansionInfo &	expansionInfo
	)

static

Returns the reassociation maps to use in the tensor.expand_shape operation to convert the operands of the original operation to operands of the expanded operation.

The same method is used to compute the tensor.collapse_shape used to collapse the result of the expanded op to get the value that can replace all uses of the results of the original op.

Definition at line 695 of file ElementwiseOpFusion.cpp.

References mlir::AffineMap::getResults().

Referenced by fuseWithReshapeByExpansion().

◆ isFusableWithReshapeByDimExpansion()

static bool isFusableWithReshapeByDimExpansion	(	LinalgOp	linalgOp,
		OpOperand *	fusableOpOperand
	)

static

Conditions for folding a structured linalg operation with a reshape op by expanding the iteration space dimensionality for tensor operations.

These are preconditions assumed by foldReshapeByDimExpansion which implements the following fusion pattern.

Consider

c = linalg.generic ins(a, b : memref<?x?x?xf32>, memref<?x?xf32>) indexing_maps = [affine_map<(d0, d1, d2) -> (d1, d0, d2)>, affine_map<(d0, d1, d2) -> (d1, d2)>, affine_map<(d0, d1, d2) -> (d0, d2, d1)>] d = tensor.expand_shape c [[0, 1], [2], [3, 4, 5]] : tensor<?x?x?xf32> into tensor<?x?x?x?x?x?xf32>

The reshape can be folded into the linalgOp if its loop dimensionality is increased to match the result (operand) of the tensor.expand_shape. The indexing_map of the fused tensor in the linalgOp and the reassociation map helps compute the indexing maps of the modified op. For the above example, based on the reassociation map it can be concluded that

The loop used to access the first dimension of the fused tensor is split into two.
The loop used to access the second dimension of the fused tensor is kept as is.
The loop used to access the third dimension of the fused tensor is split into three.

i.e. (e0, e1, e2, e3, e4) is the domain of the indexing map of the modified op, then

d0 -> e0, e1 d1 -> e2, e3, e4 d2 -> e5

substituting this, the structured op can be rewritten as

d = linalg.generic ins(%0, %1 : ) indexing_maps = [affine_map<(e0, e1, e2, e3, e4, e5) -> (e2, e3, e4, e0, e1, e5)>, affine_map<(e0, e1, e2, e3, e4, e5) -> (e2, e3, e4, e5)>, affine_map<(e0, e1, e2, e3, e4, e5) -> (e0, e1, e5, e2, e3, e4)>]

Since operands to the linalg generic are now 5D, reshapes can be introduced to make it consistent

%0 = tensor.expand_shape a [[0, 1, 2], [3, 4], [5]] : tensor<?x?x?xf32> into tensor<?x?x?x?x?x?xf32> %1 = tensor.expand_shape b [[0, 1, 2], [3]] : tensor<?x?x?xf32> into tensor<?x?x?x?xf32>

The added reshapes are again expanding patterns, so they will get fused with its producers if possible.

Definition at line 523 of file ElementwiseOpFusion.cpp.

References mlir::AffineMap::getNumResults(), and mlir::AffineMap::getResults().

Referenced by fuseWithReshapeByExpansion().

◆ isLinalgOpExpandable()

static LogicalResult isLinalgOpExpandable	(	LinalgOp	linalgOp,
		const ExpansionInfo &	expansionInfo,
		PatternRewriter &	rewriter
	)

static

Epanding the body of a linalg operation requires adaptations of the accessed loop indices.

Specifically, access of indices in the original operation need to be replaced with linearizations of indices in the expanded op. That requires the shape of the expanded dimensions to be static (at least all but the most significant). For now check that these are all statically sized. Note that this could be extended to handle dynamic case, but the implementation below uses affine.apply which seems to have issues when the shapes are not static.

Definition at line 636 of file ElementwiseOpFusion.cpp.

References mlir::RewriterBase::notifyMatchFailure(), and mlir::success().

Referenced by fuseWithReshapeByExpansion().

◆ updateExpandedGenericOpRegion()

static void updateExpandedGenericOpRegion	(	PatternRewriter &	rewriter,
		Location	loc,
		Region &	fusedRegion,
		const ExpansionInfo &	expansionInfo
	)

static

Update the body of an expanded linalg operation having index semantics.

The indices of the original operation need to be recovered by linearizing the indices of the correspoding dimensions of the expanded operation. For now it is assumed that the shapes of the expanded operation needed for linearization are static.

Definition at line 715 of file ElementwiseOpFusion.cpp.

References mlir::bindDims(), mlir::OpBuilder::create(), mlir::Region::front(), mlir::Builder::getContext(), mlir::Block::getOps(), mlir::RewriterBase::replaceOp(), and mlir::OpBuilder::setInsertionPointAfter().

Referenced by fuseWithReshapeByExpansion().

Namespaces

Macros

Functions

Macro Definition Documentation

◆ GEN_PASS_DEF_LINALGELEMENTWISEOPFUSIONPASS

Function Documentation

◆ cloneToCollapsedOp()

◆ cloneToCollapsedOp< GenericOp >()

◆ cloneToCollapsedOp< LinalgOp >()

◆ collapseOperandsAndResults()

◆ createCollapsedOp()

◆ fuseWithReshapeByExpansion()

◆ generateCollapsedIndexingRegion()

◆ generateFusedElementwiseOpRegion()

◆ getCollapsableIterationSpaceDims()

◆ getCollapsedOpIndexingMap()

◆ getCollapsedOpIteratorTypes()

◆ getCollapsedOpOperand()

◆ getDomainReassociation()

◆ getExpandedType()

◆ getIndexingMapInExpandedOp()

◆ getIndexingMapOfProducerOperandsInCoordinatesOfFusedOp()

◆ getOperandReassociation()

◆ getReassociationForExpansion()

◆ isFusableWithReshapeByDimExpansion()

◆ isLinalgOpExpandable()

◆ updateExpandedGenericOpRegion()