#include "mlir/Dialect/Affine/Utils.h"
#include "mlir/Dialect/Affine/Analysis/Utils.h"
#include "mlir/Dialect/Affine/IR/AffineOps.h"
#include "mlir/Dialect/Affine/IR/AffineValueMap.h"
#include "mlir/Dialect/Affine/LoopUtils.h"
#include "mlir/Dialect/Arith/Utils/Utils.h"
#include "mlir/Dialect/Func/IR/FuncOps.h"
#include "mlir/Dialect/MemRef/IR/MemRef.h"
#include "mlir/Dialect/Utils/IndexingUtils.h"
#include "mlir/IR/AffineExprVisitor.h"
#include "mlir/IR/Dominance.h"
#include "mlir/IR/IRMapping.h"
#include "mlir/IR/ImplicitLocOpBuilder.h"
#include "mlir/IR/IntegerSet.h"
#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
#include "llvm/Support/LogicalResult.h"
#include <optional>

Macros
#define	DEBUG_TYPE "affine-utils"

Enumerations
enum	TileExprPattern { TileFloorDiv , TileMod , TileNone }
	Enum to set patterns of affine expr in tiled-layout map. More...

Functions
static void	promoteIfBlock (AffineIfOp ifOp, bool elseBlock)
	Promotes the `then` or the `else` block of `ifOp` (depending on whether `elseBlock` is false or true) into `ifOp`'s containing block, and discards the rest of the op. More...

static Operation *	getOutermostInvariantForOp (AffineIfOp ifOp)
	Returns the outermost affine.for/parallel op that the `ifOp` is invariant on. More...

static AffineIfOp	hoistAffineIfOp (AffineIfOp ifOp, Operation *hoistOverOp)
	A helper for the mechanics of mlir::hoistAffineIfOp. More...

static bool	mustReachAtInnermost (const MemRefAccess &srcAccess, const MemRefAccess &destAccess)
	Returns true if the memory operation of `destAccess` depends on `srcAccess` inside of the innermost common surrounding affine loop between the two accesses. More...

static bool	mayHaveEffect (Operation srcMemOp, Operation destMemOp, unsigned minSurroundingLoops)
	Returns true if `srcMemOp` may have an effect on `destMemOp` within the scope of the outermost `minSurroundingLoops` loops that surround them. More...

static void	forwardStoreToLoad (AffineReadOpInterface loadOp, SmallVectorImpl< Operation * > &loadOpsToErase, SmallPtrSetImpl< Value > &memrefsToErase, DominanceInfo &domInfo, llvm::function_ref< bool(Value, Value)> mayAlias)
	Attempt to eliminate loadOp by replacing it with a value stored into memory which the load is guaranteed to retrieve. More...

template bool	mlir::affine::hasNoInterveningEffect< mlir::MemoryEffects::Read, affine::AffineReadOpInterface > (mlir::Operation *, affine::AffineReadOpInterface, llvm::function_ref< bool(Value, Value)>)

static void	findUnusedStore (AffineWriteOpInterface writeA, SmallVectorImpl< Operation * > &opsToErase, PostDominanceInfo &postDominanceInfo, llvm::function_ref< bool(Value, Value)> mayAlias)

static void	loadCSE (AffineReadOpInterface loadA, SmallVectorImpl< Operation * > &loadOpsToErase, DominanceInfo &domInfo, llvm::function_ref< bool(Value, Value)> mayAlias)

LogicalResult	transformMemRefLoadWithReducedRank (Operation *op, Value oldMemRef, Value newMemRef, unsigned memRefOperandPos, ArrayRef< Value > extraIndices, ArrayRef< Value > extraOperands, ArrayRef< Value > symbolOperands, AffineMap indexRemap)

static LogicalResult	getTileSizePos (AffineMap map, SmallVectorImpl< std::tuple< AffineExpr, unsigned, unsigned >> &tileSizePos)
	Check if `map` is a tiled layout. More...

static bool	isNormalizedMemRefDynamicDim (unsigned dim, AffineMap layoutMap, SmallVectorImpl< unsigned > &inMemrefTypeDynDims)
	Check if `dim` dimension of memrefType with `layoutMap` becomes dynamic after normalization. More...

static AffineExpr	createDimSizeExprForTiledLayout (AffineExpr oldMapOutput, TileExprPattern pat)
	Create affine expr to calculate dimension size for a tiled-layout map. More...

static void	createNewDynamicSizes (MemRefType oldMemRefType, MemRefType newMemRefType, AffineMap map, memref::AllocOp *allocOp, OpBuilder b, SmallVectorImpl< Value > &newDynamicSizes)
	Create new maps to calculate each dimension size of `newMemRefType`, and create `newDynamicSizes` from them by using AffineApplyOp. More...

static FailureOr< OpFoldResult >	composedAffineMultiply (OpBuilder &b, Location loc, OpFoldResult lhs, OpFoldResult rhs)
	Create an affine map that computes `lhs` * `rhs`, composing in any other affine maps. More...

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "affine-utils"

Definition at line 33 of file Utils.cpp.

Enumeration Type Documentation

◆ TileExprPattern

enum TileExprPattern

Enum to set patterns of affine expr in tiled-layout map.

TileFloorDiv: <dim expr> div <tile size> TileMod: <dim expr> mod <tile size> TileNone: None of the above Example: #tiled_2d_128x256 = affine_map<(d0, d1) -> (d0 div 128, d1 div 256, d0 mod 128, d1 mod 256)> "d0 div 128" and "d1 div 256" ==> TileFloorDiv "d0 mod 128" and "d1 mod 256" ==> TileMod

Enumerator
TileFloorDiv
TileMod
TileNone

Definition at line 1556 of file Utils.cpp.

Function Documentation

◆ composedAffineMultiply()

static FailureOr<OpFoldResult> composedAffineMultiply	(	OpBuilder &	b,
		Location	loc,
		OpFoldResult	lhs,
		OpFoldResult	rhs
	)

static

Create an affine map that computes lhs * rhs, composing in any other affine maps.

Definition at line 1936 of file Utils.cpp.

References mlir::bindSymbols(), mlir::Builder::getContext(), and mlir::affine::makeComposedFoldedAffineApply().

Referenced by mlir::affine::delinearizeIndex().

◆ createDimSizeExprForTiledLayout()

static AffineExpr createDimSizeExprForTiledLayout	(	AffineExpr	oldMapOutput,
		TileExprPattern	pat
	)

static

Create affine expr to calculate dimension size for a tiled-layout map.

Definition at line 1682 of file Utils.cpp.

References mlir::CeilDiv, mlir::getAffineBinaryOpExpr(), mlir::AffineBinaryOpExpr::getLHS(), mlir::AffineBinaryOpExpr::getRHS(), TileFloorDiv, and TileMod.

Referenced by createNewDynamicSizes().

◆ createNewDynamicSizes()

static void createNewDynamicSizes	(	MemRefType	oldMemRefType,
		MemRefType	newMemRefType,
		AffineMap	map,
		memref::AllocOp *	allocOp,
		OpBuilder	b,
		SmallVectorImpl< Value > &	newDynamicSizes
	)

static

Create new maps to calculate each dimension size of newMemRefType, and create newDynamicSizes from them by using AffineApplyOp.

Steps for normalizing dynamic memrefs for a tiled layout map Example: #map0 = affine_map<(d0, d1) -> (d0, d1 floordiv 32, d1 mod 32)> %0 = dim arg0, c1 :memref<4x?xf32> %1 = alloc(%0) : memref<4x?xf32, #map0>

(Before this function)

Check if map(#map0) is a tiled layout using getTileSizePos(). Only single layout map is supported.
Create normalized memrefType using isNormalizedMemRefDynamicDim(). It is memref<4x?x?xf32> in the above example.

(In this function)

Create new maps to calculate each dimension of the normalized memrefType using createDimSizeExprForTiledLayout(). In the tiled layout, the dimension size can be calculated by replacing "floordiv <tile size>" with "ceildiv <tile size>" and "mod <tile size>" with "<tile size>".

New map in the above example #map0 = affine_map<(d0, d1) -> (d0)> #map1 = affine_map<(d0, d1) -> (d1 ceildiv 32)> #map2 = affine_map<(d0, d1) -> (32)>

Create AffineApplyOp to apply the new maps. The output of AffineApplyOp is used in dynamicSizes of new AllocOp. %0 = dim arg0, c1 : memref<4x?xf32> c4 = arith.constant 4 : index %1 = affine.apply #map1(c4, %0) %2 = affine.apply #map2(c4, %0)

Definition at line 1737 of file Utils.cpp.

References mlir::OpBuilder::create(), createDimSizeExprForTiledLayout(), mlir::AffineMap::get(), mlir::Builder::getIndexType(), mlir::Builder::getIntegerAttr(), mlir::AffineMap::getNumInputs(), mlir::AffineMap::getNumSymbols(), mlir::AffineMap::getResults(), getTileSizePos(), TileFloorDiv, TileMod, and TileNone.

Referenced by mlir::affine::normalizeMemRef().

◆ findUnusedStore()

static void findUnusedStore	(	AffineWriteOpInterface	writeA,
		SmallVectorImpl< Operation * > &	opsToErase,
		PostDominanceInfo &	postDominanceInfo,
		llvm::function_ref< bool(Value, Value)>	mayAlias
	)

static

Definition at line 907 of file Utils.cpp.

References mlir::Operation::getUsers(), mayAlias(), and mlir::PostDominanceInfo::postDominates().

Referenced by mlir::affine::affineScalarReplace().

◆ forwardStoreToLoad()

static void forwardStoreToLoad	(	AffineReadOpInterface	loadOp,
		SmallVectorImpl< Operation * > &	loadOpsToErase,
		SmallPtrSetImpl< Value > &	memrefsToErase,
		DominanceInfo &	domInfo,
		llvm::function_ref< bool(Value, Value)>	mayAlias
	)

static

Attempt to eliminate loadOp by replacing it with a value stored into memory which the load is guaranteed to retrieve.

This check involves three components: 1) The store and load must be on the same location 2) The store must dominate (and therefore must always occur prior to) the load 3) No other operations will overwrite the memory loaded between the given load and store. If such a value exists, the replaced loadOp will be added to loadOpsToErase and its memref will be added to memrefsToErase.

Definition at line 830 of file Utils.cpp.

References mlir::DominanceInfo::dominates(), mlir::Value::getType(), mayAlias(), mustReachAtInnermost(), and mlir::Value::replaceAllUsesWith().

Referenced by mlir::affine::affineScalarReplace().

◆ getOutermostInvariantForOp()

static Operation* getOutermostInvariantForOp ( AffineIfOp ifOp )

static

Returns the outermost affine.for/parallel op that the ifOp is invariant on.

The ifOp could be hoisted and placed right before such an operation. This method assumes that the ifOp has been canonicalized (to be correct and effective).

Definition at line 260 of file Utils.cpp.

References mlir::Operation::getOperands().

Referenced by mlir::affine::hoistAffineIfOp().

◆ getTileSizePos()

static LogicalResult getTileSizePos	(	AffineMap	map,
		SmallVectorImpl< std::tuple< AffineExpr, unsigned, unsigned >> &	tileSizePos
	)

static

Check if map is a tiled layout.

In the tiled layout, specific k dimensions being floordiv'ed by respective tile sizes appeare in a mod with the same tile sizes, and no other expression involves those k dimensions. This function stores a vector of tuples (tileSizePos) including AffineExpr for tile size, positions of corresponding floordiv and mod. If it is not a tiled layout, an empty vector is returned.

Definition at line 1564 of file Utils.cpp.

References mlir::FloorDiv, mlir::AffineBinaryOpExpr::getLHS(), mlir::AffineMap::getResults(), mlir::AffineBinaryOpExpr::getRHS(), and mlir::Mod.

Referenced by createNewDynamicSizes(), mlir::affine::normalizeMemRef(), and mlir::affine::normalizeMemRefType().

◆ hoistAffineIfOp()

static AffineIfOp hoistAffineIfOp	(	AffineIfOp	ifOp,
		Operation *	hoistOverOp
	)

static

A helper for the mechanics of mlir::hoistAffineIfOp.

Hoists ifOp just over hoistOverOp. Returns the new hoisted op if any hoisting happened, otherwise the same ifOp.

Definition at line 286 of file Utils.cpp.

References mlir::WalkResult::advance(), mlir::IRMapping::clear(), mlir::OpBuilder::clone(), mlir::OpBuilder::create(), mlir::Operation::getBlock(), mlir::Builder::getBoolAttr(), mlir::Block::getOperations(), mlir::Builder::getStringAttr(), mlir::WalkResult::interrupt(), promoteIfBlock(), and mlir::OpBuilder::setInsertionPointAfter().

◆ isNormalizedMemRefDynamicDim()

static bool isNormalizedMemRefDynamicDim	(	unsigned	dim,
		AffineMap	layoutMap,
		SmallVectorImpl< unsigned > &	inMemrefTypeDynDims
	)

static

Check if dim dimension of memrefType with layoutMap becomes dynamic after normalization.

Dimensions that include dynamic dimensions in the map output will become dynamic dimensions. Return true if dim is dynamic dimension.

Example: #map0 = affine_map<(d0, d1) -> (d0, d1 floordiv 32, d1 mod 32)>

If d1 is dynamic dimension, 2nd and 3rd dimension of map output are dynamic. memref<4x?xf32, #map0> ==> memref<4x?x?xf32>

Definition at line 1663 of file Utils.cpp.

References mlir::WalkResult::advance(), mlir::getAffineDimExpr(), mlir::AffineMap::getContext(), mlir::AffineMap::getResults(), mlir::WalkResult::interrupt(), and mlir::AffineExpr::walk().

Referenced by mlir::affine::normalizeMemRefType().

◆ loadCSE()

static void loadCSE	(	AffineReadOpInterface	loadA,
		SmallVectorImpl< Operation * > &	loadOpsToErase,
		DominanceInfo &	domInfo,
		llvm::function_ref< bool(Value, Value)>	mayAlias
	)

static

Definition at line 954 of file Utils.cpp.

References mlir::DominanceInfo::dominates(), mayAlias(), and mlir::Value::replaceAllUsesWith().

Referenced by mlir::affine::affineScalarReplace().

◆ mayHaveEffect()

static bool mayHaveEffect	(	Operation *	srcMemOp,
		Operation *	destMemOp,
		unsigned	minSurroundingLoops
	)

static

Returns true if srcMemOp may have an effect on destMemOp within the scope of the outermost minSurroundingLoops loops that surround them.

srcMemOp and destMemOp are expected to be affine read/write ops.

Definition at line 649 of file Utils.cpp.

References mlir::affine::checkMemrefAccessDependence(), mlir::affine::getAffineScope(), mlir::affine::getNumCommonSurroundingLoops(), mlir::affine::MemRefAccess::memref, and mlir::affine::noDependence().

Referenced by mlir::affine::hasNoInterveningEffect().

◆ mlir::affine::hasNoInterveningEffect< mlir::MemoryEffects::Read, affine::AffineReadOpInterface >()

template bool mlir::affine::hasNoInterveningEffect< mlir::MemoryEffects::Read, affine::AffineReadOpInterface >	(	mlir::Operation *	,
		affine::AffineReadOpInterface	,
		llvm::function_ref< bool(Value, Value)>
	)

◆ mustReachAtInnermost()

static bool mustReachAtInnermost	(	const MemRefAccess &	srcAccess,
		const MemRefAccess &	destAccess
	)

static

Returns true if the memory operation of destAccess depends on srcAccess inside of the innermost common surrounding affine loop between the two accesses.

Definition at line 632 of file Utils.cpp.

References mlir::affine::checkMemrefAccessDependence(), mlir::affine::getAffineScope(), mlir::affine::getNumCommonSurroundingLoops(), mlir::affine::hasDependence(), and mlir::affine::MemRefAccess::opInst.

Referenced by forwardStoreToLoad().

◆ promoteIfBlock()

static void promoteIfBlock	(	AffineIfOp	ifOp,
		bool	elseBlock
	)

static

Promotes the then or the else block of ifOp (depending on whether elseBlock is false or true) into ifOp's containing block, and discards the rest of the op.

Definition at line 244 of file Utils.cpp.

References mlir::Block::begin(), mlir::Block::end(), and mlir::Block::getOperations().

Referenced by hoistAffineIfOp().

◆ transformMemRefLoadWithReducedRank()

LogicalResult transformMemRefLoadWithReducedRank	(	Operation *	op,
		Value	oldMemRef,
		Value	newMemRef,
		unsigned	memRefOperandPos,
		ArrayRef< Value >	extraIndices,
		ArrayRef< Value >	extraOperands,
		ArrayRef< Value >	symbolOperands,
		AffineMap	indexRemap
	)

Definition at line 1100 of file Utils.cpp.

References mlir::OpBuilder::create(), mlir::AffineMap::get(), mlir::Operation::getLoc(), mlir::Builder::getMultiDimIdentityMap(), mlir::AffineMap::getNumDims(), mlir::AffineMap::getNumSymbols(), mlir::AffineMap::getResults(), mlir::Value::getType(), mlir::affine::isValidDim(), mlir::affine::isValidSymbol(), and mlir::Operation::operand_begin().

Referenced by mlir::affine::replaceAllMemRefUsesWith().

Macros

Enumerations

Functions

Macro Definition Documentation

◆ DEBUG_TYPE

Enumeration Type Documentation

◆ TileExprPattern

Function Documentation

◆ composedAffineMultiply()

◆ createDimSizeExprForTiledLayout()

◆ createNewDynamicSizes()

◆ findUnusedStore()

◆ forwardStoreToLoad()

◆ getOutermostInvariantForOp()

◆ getTileSizePos()

◆ hoistAffineIfOp()

◆ isNormalizedMemRefDynamicDim()

◆ loadCSE()

◆ mayHaveEffect()

◆ mlir::affine::hasNoInterveningEffect< mlir::MemoryEffects::Read, affine::AffineReadOpInterface >()

◆ mustReachAtInnermost()

◆ promoteIfBlock()

◆ transformMemRefLoadWithReducedRank()