#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/IntegerSet.h"
#include "mlir/Transforms/GreedyPatternRewriteDriver.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.
static Operation *	getOutermostInvariantForOp (AffineIfOp ifOp)
	Returns the outermost affine.for/parallel op that the ifOp is invariant on.
static AffineIfOp	hoistAffineIfOp (AffineIfOp ifOp, Operation *hoistOverOp)
	A helper for the mechanics of mlir::hoistAffineIfOp.
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.
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.
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.
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)
static bool	isDereferencingOp (Operation *op)
static LogicalResult	getTileSizePos (AffineMap map, SmallVectorImpl< std::tuple< AffineExpr, unsigned, unsigned > > &tileSizePos)
	Check if map is a tiled layout.
static bool	isNormalizedMemRefDynamicDim (unsigned dim, AffineMap layoutMap, SmallVectorImpl< unsigned > &inMemrefTypeDynDims)
	Check if dim dimension of memrefType with layoutMap becomes dynamic after normalization.
static AffineExpr	createDimSizeExprForTiledLayout (AffineExpr oldMapOutput, TileExprPattern pat)
	Create affine expr to calculate dimension size for a tiled-layout map.
template<typename AllocLikeOp>
static void	createNewDynamicSizes (MemRefType oldMemRefType, MemRefType newMemRefType, AffineMap map, AllocLikeOp allocOp, OpBuilder b, SmallVectorImpl< Value > &newDynamicSizes)
	Create new maps to calculate each dimension size of newMemRefType, and create newDynamicSizes from them by using AffineApplyOp.
template LogicalResult	mlir::affine::normalizeMemRef< memref::AllocaOp > (memref::AllocaOp op)
template LogicalResult	mlir::affine::normalizeMemRef< memref::AllocOp > (memref::AllocOp op)
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.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "affine-utils"

Definition at line 31 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 1484 of file Utils.cpp.

Function Documentation

◆ composedAffineMultiply()

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 1954 of file Utils.cpp.

References b, mlir::bindSymbols(), lhs, mlir::affine::makeComposedFoldedAffineApply(), and rhs.

◆ createDimSizeExprForTiledLayout()

AffineExpr createDimSizeExprForTiledLayout	(	AffineExpr	oldMapOutput,
		TileExprPattern	pat )

static

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

Definition at line 1610 of file Utils.cpp.

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

Referenced by createNewDynamicSizes().

◆ createNewDynamicSizes()

template<typename AllocLikeOp>

void createNewDynamicSizes	(	MemRefType	oldMemRefType,
		MemRefType	newMemRefType,
		AffineMap	map,
		AllocLikeOp	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 1666 of file Utils.cpp.

References b, createDimSizeExprForTiledLayout(), mlir::AffineMap::get(), mlir::AffineMap::getNumInputs(), mlir::AffineMap::getNumSymbols(), mlir::AffineMap::getResults(), getTileSizePos(), TileFloorDiv, TileMod, and TileNone.

◆ findUnusedStore()

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

static

Definition at line 912 of file Utils.cpp.

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

◆ forwardStoreToLoad()

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 835 of file Utils.cpp.

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

◆ getOutermostInvariantForOp()

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 262 of file Utils.cpp.

References mlir::Operation::getOperands(), mlir::Operation::getParentOp(), and mlir::Operation::hasTrait().

◆ getTileSizePos()

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 1492 of file Utils.cpp.

References mlir::FloorDiv, mlir::AffineExpr::getKind(), mlir::AffineBinaryOpExpr::getLHS(), mlir::AffineMap::getResults(), mlir::AffineBinaryOpExpr::getRHS(), mlir::Mod, success(), and mlir::AffineExpr::walk().

Referenced by createNewDynamicSizes().

◆ hoistAffineIfOp()

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 289 of file Utils.cpp.

References mlir::WalkResult::advance(), b, mlir::IRMapping::clear(), mlir::Operation::getBlock(), mlir::Block::getOperations(), mlir::WalkResult::interrupt(), promoteIfBlock(), and mlir::Operation::walk().

◆ isDereferencingOp()

bool isDereferencingOp ( Operation * op )

static

Definition at line 1104 of file Utils.cpp.

◆ isNormalizedMemRefDynamicDim()

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 1591 of file Utils.cpp.

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

◆ loadCSE()

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

static

Definition at line 959 of file Utils.cpp.

References mlir::DominanceInfo::dominates(), mlir::affine::hasNoInterveningEffect(), and mayAlias().

◆ mayHaveEffect()

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 654 of file Utils.cpp.

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

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)>	)

References mlir::affine::hasNoInterveningEffect().

◆ mlir::affine::normalizeMemRef< memref::AllocaOp >()

template LogicalResult mlir::affine::normalizeMemRef< memref::AllocaOp > ( memref::AllocaOp op )

◆ mlir::affine::normalizeMemRef< memref::AllocOp >()

template LogicalResult mlir::affine::normalizeMemRef< memref::AllocOp > ( memref::AllocOp op )

◆ mustReachAtInnermost()

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 636 of file Utils.cpp.

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

Referenced by forwardStoreToLoad().

◆ promoteIfBlock()

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 246 of file Utils.cpp.

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

Referenced by hoistAffineIfOp().

Macros

Enumerations

Functions

Macro Definition Documentation

◆ DEBUG_TYPE

Enumeration Type Documentation

◆ TileExprPattern

Function Documentation

◆ composedAffineMultiply()

◆ createDimSizeExprForTiledLayout()

◆ createNewDynamicSizes()

◆ findUnusedStore()

◆ forwardStoreToLoad()

◆ getOutermostInvariantForOp()

◆ getTileSizePos()

◆ hoistAffineIfOp()

◆ isDereferencingOp()

◆ isNormalizedMemRefDynamicDim()

◆ loadCSE()

◆ mayHaveEffect()

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

◆ mlir::affine::normalizeMemRef< memref::AllocaOp >()

◆ mlir::affine::normalizeMemRef< memref::AllocOp >()

◆ mustReachAtInnermost()

◆ promoteIfBlock()