LoopFusion.cpp File Reference

#include "mlir/Dialect/Affine/Passes.h"
#include "mlir/Dialect/Affine/Analysis/AffineStructures.h"
#include "mlir/Dialect/Affine/Analysis/LoopAnalysis.h"
#include "mlir/Dialect/Affine/Analysis/Utils.h"
#include "mlir/Dialect/Affine/IR/AffineOps.h"
#include "mlir/Dialect/Affine/LoopFusionUtils.h"
#include "mlir/Dialect/Affine/LoopUtils.h"
#include "mlir/Dialect/Affine/Utils.h"
#include "mlir/Dialect/MemRef/IR/MemRef.h"
#include "mlir/IR/AffineExpr.h"
#include "mlir/IR/AffineMap.h"
#include "mlir/IR/Builders.h"
#include "mlir/Transforms/Passes.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <iomanip>
#include <optional>
#include <sstream>
#include "mlir/Dialect/Affine/Passes.h.inc"

Go to the source code of this file.

Namespaces
	mlir
	Include the generated interface declarations.
	mlir::affine

Macros
#define	GEN_PASS_DEF_AFFINELOOPFUSION
#define	DEBUG_TYPE   "affine-loop-fusion"

Functions
static bool	canRemoveSrcNodeAfterFusion (unsigned srcId, unsigned dstId, const ComputationSliceState &fusionSlice, Operation *fusedLoopInsPoint, const DenseSet< Value > &escapingMemRefs, MemRefDependenceGraph *mdg)
	Returns true if node 'srcId' can be removed after fusing it with node 'dstId'. More...
static void	getProducerCandidates (unsigned dstId, MemRefDependenceGraph *mdg, SmallVectorImpl< unsigned > &srcIdCandidates)
	Returns in 'srcIdCandidates' the producer fusion candidates for consumer 'dstId'. More...
static void	gatherProducerConsumerMemrefs (unsigned srcId, unsigned dstId, MemRefDependenceGraph *mdg, DenseSet< Value > &producerConsumerMemrefs)
	Returns in 'producerConsumerMemrefs' the memrefs involved in a producer-consumer dependence between 'srcId' and 'dstId'. More...
static bool	isEscapingMemref (Value memref, Block *block)
	A memref escapes in the context of the fusion pass if either: More...
static void	gatherEscapingMemrefs (unsigned id, MemRefDependenceGraph *mdg, DenseSet< Value > &escapingMemRefs)
	Returns in 'escapingMemRefs' the memrefs from affine store ops in node 'id' that escape the block or are accessed in a non-affine way. More...
static void	sinkSequentialLoops (MemRefDependenceGraph::Node *node)
static Value	createPrivateMemRef (AffineForOp forOp, Operation *srcStoreOpInst, unsigned dstLoopDepth, std::optional< unsigned > fastMemorySpace, uint64_t localBufSizeThreshold)
static bool	hasNonAffineUsersOnPath (Operation *start, Operation *end, Value memref)
	Returns true if there are any non-affine uses of memref in any of the operations between start and end (both exclusive). More...
static bool	hasNonAffineUsersOnPath (Operation *src, Operation *end)
	Check whether a memref value used in any operation of 'src' has a non-affine operation that is between src and end (exclusive of src and end) where src and end are expected to be in the same Block. More...
static bool	isFusionProfitable (Operation *srcOpInst, Operation *srcStoreOpInst, AffineForOp dstForOp, ArrayRef< ComputationSliceState > depthSliceUnions, unsigned maxLegalFusionDepth, unsigned *dstLoopDepth, double computeToleranceThreshold)

Macro Definition Documentation

DEBUG_TYPE

#define DEBUG_TYPE   "affine-loop-fusion"

Definition at line 44 of file LoopFusion.cpp.

GEN_PASS_DEF_AFFINELOOPFUSION

#define GEN_PASS_DEF_AFFINELOOPFUSION

Definition at line 39 of file LoopFusion.cpp.

Function Documentation

canRemoveSrcNodeAfterFusion()

static bool canRemoveSrcNodeAfterFusion ( unsigned  srcId, unsigned  dstId, const ComputationSliceState &  fusionSlice, Operation *  fusedLoopInsPoint, const DenseSet< Value > &  escapingMemRefs, MemRefDependenceGraph *  mdg  )

static

Returns true if node 'srcId' can be removed after fusing it with node 'dstId'.

The node can be removed if any of the following conditions are met:

1. 'srcId' has no output dependences after fusion and no escaping memrefs.
2. 'srcId' has no output dependences after fusion, has escaping memrefs and the fusion slice is maximal.
3. 'srcId' has output dependences after fusion, the fusion slice is maximal and the fusion insertion point dominates all the dependences.

Definition at line 78 of file LoopFusion.cpp.

References mlir::Operation::getBlock(), mlir::affine::MemRefDependenceGraph::getNode(), mlir::Operation::isBeforeInBlock(), mlir::affine::ComputationSliceState::isMaximal(), mlir::affine::MemRefDependenceGraph::Node::op, and mlir::affine::MemRefDependenceGraph::outEdges.

createPrivateMemRef()

static Value createPrivateMemRef ( AffineForOp  forOp, Operation *  srcStoreOpInst, unsigned  dstLoopDepth, std::optional< unsigned >  fastMemorySpace, uint64_t  localBufSizeThreshold  )

static

Definition at line 245 of file LoopFusion.cpp.

References mlir::affine::MemRefRegion::compute(), mlir::OpBuilder::create(), mlir::AffineMap::get(), mlir::get(), mlir::Builder::getAffineConstantExpr(), mlir::Builder::getAffineDimExpr(), mlir::affine::MemRefRegion::getConstantBoundingSizeAndShape(), mlir::affine::MemRefRegion::getConstraints(), mlir::Operation::getLoc(), mlir::affine::getMemRefIntOrFloatEltSizeInBytes(), mlir::presburger::IntegerRelation::getNumCols(), mlir::presburger::IntegerRelation::getNumVars(), mlir::Operation::getParentRegion(), mlir::FlatLinearValueConstraints::getValues(), mlir::affine::replaceAllMemRefUsesWith(), and mlir::simplifyAffineExpr().

gatherEscapingMemrefs()

static void gatherEscapingMemrefs ( unsigned  id, MemRefDependenceGraph *  mdg, DenseSet< Value > &  escapingMemRefs  )

static

Returns in 'escapingMemRefs' the memrefs from affine store ops in node 'id' that escape the block or are accessed in a non-affine way.

Definition at line 217 of file LoopFusion.cpp.

References mlir::affine::MemRefDependenceGraph::block, mlir::affine::MemRefDependenceGraph::getNode(), and isEscapingMemref().

gatherProducerConsumerMemrefs()

static void gatherProducerConsumerMemrefs ( unsigned  srcId, unsigned  dstId, MemRefDependenceGraph *  mdg, DenseSet< Value > &  producerConsumerMemrefs  )

static

Returns in 'producerConsumerMemrefs' the memrefs involved in a producer-consumer dependence between 'srcId' and 'dstId'.

Definition at line 171 of file LoopFusion.cpp.

References mlir::affine::gatherProducerConsumerMemrefs(), and mlir::affine::MemRefDependenceGraph::getNode().

getProducerCandidates()

static void getProducerCandidates ( unsigned  dstId, MemRefDependenceGraph *  mdg, SmallVectorImpl< unsigned > &  srcIdCandidates  )

static

Returns in 'srcIdCandidates' the producer fusion candidates for consumer 'dstId'.

Candidates are sorted by node id order. This order corresponds to the program order when the 'mdg' is created. However, program order is not guaranteed and must not be required by the client. Program order won't be held if the 'mdg' is reused from a previous fusion step or if the node creation order changes in the future to support more advance cases.

Definition at line 137 of file LoopFusion.cpp.

References mlir::affine::MemRefDependenceGraph::getNode(), and mlir::affine::MemRefDependenceGraph::inEdges.

hasNonAffineUsersOnPath() [1/2]

static bool hasNonAffineUsersOnPath ( Operation *  src, Operation *  end  )

static

Check whether a memref value used in any operation of 'src' has a non-affine operation that is between src and end (exclusive of src and end) where src and end are expected to be in the same Block.

Any other than affine read/write are treated as non-affine uses of memref.

Definition at line 369 of file LoopFusion.cpp.

References mlir::WalkResult::advance(), mlir::Operation::getBlock(), mlir::Operation::getOperands(), hasNonAffineUsersOnPath(), mlir::Operation::isBeforeInBlock(), and mlir::Operation::walk().

hasNonAffineUsersOnPath() [2/2]

static bool hasNonAffineUsersOnPath ( Operation *  start, Operation *  end, Value  memref  )

static

Returns true if there are any non-affine uses of memref in any of the operations between start and end (both exclusive).

Any other than affine read/write are treated as non-affine uses of memref.

Definition at line 349 of file LoopFusion.cpp.

References mlir::Operation::getBlock(), mlir::Value::getUsers(), and mlir::Operation::isBeforeInBlock().

Referenced by hasNonAffineUsersOnPath().

isEscapingMemref()

static bool isEscapingMemref ( Value  memref, Block *  block  )

static

A memref escapes in the context of the fusion pass if either:

1. it (or its alias) is a block argument, or
2. created by an op not known to guarantee alias freedom,
3. it (or its alias) are used by ops other than affine dereferencing ops (e.g., by call op, memref load/store ops, alias creating ops, unknown ops, terminator ops, etc.); such ops do not deference the memref in an affine way.

Definition at line 187 of file LoopFusion.cpp.

References mlir::Value::getDefiningOp(), and mlir::Value::getUsers().

Referenced by gatherEscapingMemrefs().

isFusionProfitable()

static bool isFusionProfitable ( Operation *  srcOpInst, Operation *  srcStoreOpInst, AffineForOp  dstForOp, ArrayRef< ComputationSliceState >  depthSliceUnions, unsigned  maxLegalFusionDepth, unsigned *  dstLoopDepth, double  computeToleranceThreshold  )

static

Definition at line 430 of file LoopFusion.cpp.

References mlir::affine::MemRefRegion::compute(), mlir::affine::getAffineForIVs(), mlir::affine::getComputeCost(), mlir::affine::getFusionComputeCost(), mlir::Operation::getLoc(), mlir::affine::getLoopNestStats(), mlir::affine::getMemoryFootprintBytes(), mlir::affine::MemRefRegion::getRegionSize(), mlir::affine::ComputationSliceState::isEmpty(), and max().

sinkSequentialLoops()

static void sinkSequentialLoops ( MemRefDependenceGraph::Node *  node )

static

Definition at line 234 of file LoopFusion.cpp.

References mlir::affine::MemRefDependenceGraph::Node::op, and mlir::affine::sinkSequentialLoops().