16 #ifndef MLIR_DIALECT_AFFINE_ANALYSIS_UTILS_H
17 #define MLIR_DIALECT_AFFINE_ANALYSIS_UTILS_H
163 return const_cast<Node *
>(
173 return const_cast<Node *
>(
190 bool hasEdge(
unsigned srcId,
unsigned dstId,
Value value =
nullptr)
const;
193 void addEdge(
unsigned srcId,
unsigned dstId,
Value value);
219 unsigned dstId)
const;
245 const std::function<
void(Edge)> &callback);
250 const std::function<
void(Edge)> &callback);
255 const std::function<
void(Edge)> &callback);
257 void print(raw_ostream &os)
const;
292 llvm::SmallDenseSet<Value, 8> *sequentialLoops);
375 std::optional<bool> isSliceMaximalFastCheck()
const;
421 const FlatAffineValueConstraints &dependenceConstraints,
unsigned loopDepth,
422 bool isBackwardSlice, ComputationSliceState *sliceState);
426 const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap);
433 const ComputationSliceState &slice,
434 llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap);
447 SliceComputationResult
449 unsigned loopDepth,
unsigned numCommonLoops,
450 bool isBackwardSlice, ComputationSliceState *sliceUnion);
464 unsigned dstLoopDepth,
465 ComputationSliceState *sliceState);
524 bool addMemRefDimBounds =
true,
525 bool dropLocalVars =
true,
bool dropOuterIVs =
true);
588 template <
typename LoadOrStoreOpPo
inter>
598 int memorySpace = -1);
618 FailureOr<AffineValueMap>
MemRefDependenceGraph::Node Node
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Block represents an ordered list of Operations.
OpListType::iterator iterator
An integer set representing a conjunction of one or more affine equalities and inequalities.
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
Operation is the basic unit of execution within MLIR.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
FlatAffineValueConstraints is an extension of FlatLinearValueConstraints with helper functions for Af...
IntegerSet simplifyIntegerSet(IntegerSet set)
Simplify the integer set by simplifying the underlying affine expressions by flattening and some simp...
void getEnclosingAffineOps(Operation &op, SmallVectorImpl< Operation * > *ops)
Populates 'ops' with affine operations enclosing op ordered from outermost to innermost while stoppin...
SliceComputationResult computeSliceUnion(ArrayRef< Operation * > opsA, ArrayRef< Operation * > opsB, unsigned loopDepth, unsigned numCommonLoops, bool isBackwardSlice, ComputationSliceState *sliceUnion)
Computes in 'sliceUnion' the union of all slice bounds computed at 'loopDepth' between all dependent ...
bool isLoopParallelAndContainsReduction(AffineForOp forOp)
Returns whether a loop is a parallel loop and contains a reduction loop.
unsigned getNumCommonSurroundingLoops(Operation &a, Operation &b)
Returns the number of surrounding loops common to both A and B.
void getAffineIVs(Operation &op, SmallVectorImpl< Value > &ivs)
Populates 'ivs' with IVs of the surrounding affine.for and affine.parallel ops ordered from the outer...
void getSequentialLoops(AffineForOp forOp, llvm::SmallDenseSet< Value, 8 > *sequentialLoops)
Returns in 'sequentialLoops' all sequential loops in loop nest rooted at 'forOp'.
void getAffineForIVs(Operation &op, SmallVectorImpl< AffineForOp > *loops)
Populates 'loops' with IVs of the affine.for ops surrounding 'op' ordered from the outermost 'affine....
std::optional< int64_t > getMemoryFootprintBytes(AffineForOp forOp, int memorySpace=-1)
Gets the memory footprint of all data touched in the specified memory space in bytes; if the memory s...
unsigned getInnermostCommonLoopDepth(ArrayRef< Operation * > ops, SmallVectorImpl< AffineForOp > *surroundingLoops=nullptr)
Returns the innermost common loop depth for the set of operations in 'ops'.
void getComputationSliceState(Operation *depSourceOp, Operation *depSinkOp, const FlatAffineValueConstraints &dependenceConstraints, unsigned loopDepth, bool isBackwardSlice, ComputationSliceState *sliceState)
Computes the computation slice loop bounds for one loop nest as affine maps of the other loop nest's ...
std::optional< uint64_t > getIntOrFloatMemRefSizeInBytes(MemRefType memRefType)
Returns the size of a memref with element type int or float in bytes if it's statically shaped,...
unsigned getNestingDepth(Operation *op)
Returns the nesting depth of this operation, i.e., the number of loops surrounding this operation.
uint64_t getSliceIterationCount(const llvm::SmallDenseMap< Operation *, uint64_t, 8 > &sliceTripCountMap)
Return the number of iterations for the slicetripCountMap provided.
LogicalResult boundCheckLoadOrStoreOp(LoadOrStoreOpPointer loadOrStoreOp, bool emitError=true)
Checks a load or store op for an out of bound access; returns failure if the access is out of bounds ...
mlir::Block * findInnermostCommonBlockInScope(mlir::Operation *a, mlir::Operation *b)
Find the innermost common Block of a and b in the affine scope that a and b are part of.
bool buildSliceTripCountMap(const ComputationSliceState &slice, llvm::SmallDenseMap< Operation *, uint64_t, 8 > *tripCountMap)
Builds a map 'tripCountMap' from AffineForOp to constant trip count for loop nest surrounding represe...
AffineForOp insertBackwardComputationSlice(Operation *srcOpInst, Operation *dstOpInst, unsigned dstLoopDepth, ComputationSliceState *sliceState)
Creates a clone of the computation contained in the loop nest surrounding 'srcOpInst',...
FailureOr< AffineValueMap > simplifyConstrainedMinMaxOp(Operation *op, FlatAffineValueConstraints constraints)
Try to simplify the given affine.min or affine.max op to an affine map with a single result and opera...
std::optional< int64_t > getMemRefIntOrFloatEltSizeInBytes(MemRefType memRefType)
Returns the memref's element type's size in bytes where the elemental type is an int or float or a ve...
Include the generated interface declarations.
InFlightDiagnostic emitError(Location loc)
Utility method to emit an error message using this location.
ComputationSliceState aggregates loop IVs, loop bound AffineMaps and their associated operands for a ...
std::optional< bool > isSliceValid() const
Checks the validity of the slice computed.
SmallVector< Value, 4 > ivs
LogicalResult getAsConstraints(FlatAffineValueConstraints *cst) const
bool isEmpty() const
Returns true if the computation slice is empty.
LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst) const
Adds to 'cst' constraints which represent the original loop bounds on 'ivs' in 'this'.
std::vector< SmallVector< Value, 4 > > ubOperands
SmallVector< AffineMap, 4 > ubs
std::optional< bool > isMaximal() const
Returns true if the computation slice encloses all the iterations of the sliced loop nest.
SmallVector< AffineMap, 4 > lbs
Block::iterator insertPoint
std::vector< SmallVector< Value, 4 > > lbOperands
SmallVector< Operation *, 4 > memrefFrees
SmallVector< AffineForOp, 4 > forOps
SmallVector< Operation *, 4 > loadOpInsts
SmallVector< Operation *, 4 > memrefStores
void collect(Operation *opToWalk)
SmallVector< Operation *, 4 > memrefLoads
SmallVector< Operation *, 4 > storeOpInsts
void getStoreOpsForMemref(Value memref, SmallVectorImpl< Operation * > *storeOps) const
SmallVector< Operation *, 4 > loads
SmallVector< Operation *, 4 > stores
void getLoadAndStoreMemrefSet(DenseSet< Value > *loadAndStoreMemrefSet) const
Node(unsigned id, Operation *op)
unsigned hasFree(Value memref) const
SmallVector< Operation *, 4 > memrefLoads
SmallVector< Operation *, 4 > memrefStores
DenseSet< Value > privateMemrefs
unsigned getLoadOpCount(Value memref) const
unsigned getStoreOpCount(Value memref) const
unsigned hasStore(Value memref) const
Returns true if there exists an operation with a write memory effect to memref in this node.
void getLoadOpsForMemref(Value memref, SmallVectorImpl< Operation * > *loadOps) const
SmallVector< Operation *, 4 > memrefFrees
DenseMap< unsigned, SmallVector< Edge, 2 > > outEdges
Block & block
The block for which this graph is created to perform fusion.
unsigned addNode(Operation *op)
bool writesToLiveInOrEscapingMemrefs(unsigned id) const
Node * getForOpNode(AffineForOp forOp)
void removeEdge(unsigned srcId, unsigned dstId, Value value)
void addEdge(unsigned srcId, unsigned dstId, Value value)
MemRefDependenceGraph(Block &block)
DenseMap< unsigned, Node > nodes
void gatherDefiningNodes(unsigned id, DenseSet< unsigned > &definingNodes) const
Return all nodes which define SSA values used in node 'id'.
bool hasDependencePath(unsigned srcId, unsigned dstId) const
void clearNodeLoadAndStores(unsigned id)
const Node * getForOpNode(AffineForOp forOp) const
Operation * getFusedLoopNestInsertionPoint(unsigned srcId, unsigned dstId) const
void updateEdges(unsigned srcId, unsigned dstId, const DenseSet< Value > &privateMemRefs, bool removeSrcId)
bool hasNode(unsigned id) const
DenseMap< unsigned, SmallVector< Edge, 2 > > inEdges
void forEachMemRefInputEdge(unsigned id, const std::function< void(Edge)> &callback)
unsigned getOutEdgeCount(unsigned id, Value memref=nullptr) const
const Node * getNode(unsigned id) const
void removeNode(unsigned id)
void forEachMemRefOutputEdge(unsigned id, const std::function< void(Edge)> &callback)
void forEachMemRefEdge(ArrayRef< Edge > edges, const std::function< void(Edge)> &callback)
void addToNode(unsigned id, ArrayRef< Operation * > loads, ArrayRef< Operation * > stores, ArrayRef< Operation * > memrefLoads, ArrayRef< Operation * > memrefStores, ArrayRef< Operation * > memrefFrees)
Node * getNode(unsigned id)
unsigned getIncomingMemRefAccesses(unsigned id, Value memref) const
bool hasEdge(unsigned srcId, unsigned dstId, Value value=nullptr) const
void print(raw_ostream &os) const
DenseMap< Value, unsigned > memrefEdgeCount
A region of a memref's data space; this is typically constructed by analyzing load/store op's on this...
std::optional< int64_t > getConstantBoundingSizeAndShape(SmallVectorImpl< int64_t > *shape=nullptr, SmallVectorImpl< AffineMap > *lbs=nullptr) const
Returns a constant upper bound on the number of elements in this region if bounded by a known constan...
FlatAffineValueConstraints * getConstraints()
unsigned getRank() const
Returns the rank of the memref that this region corresponds to.
FlatAffineValueConstraints cst
Region (data space) of the memref accessed.
LogicalResult compute(Operation *op, unsigned loopDepth, const ComputationSliceState *sliceState=nullptr, bool addMemRefDimBounds=true, bool dropLocalVars=true, bool dropOuterIVs=true)
Computes the memory region accessed by this memref with the region represented as constraints symboli...
void getLowerAndUpperBound(unsigned pos, AffineMap &lbMap, AffineMap &ubMap) const
Gets the lower and upper bound map for the dimensional variable at pos.
std::optional< int64_t > getRegionSize()
Returns the size of this MemRefRegion in bytes.
LogicalResult unionBoundingBox(const MemRefRegion &other)
const FlatAffineValueConstraints * getConstraints() const
Value memref
Memref that this region corresponds to.
MemRefRegion(Location loc)
Location loc
If there is more than one load/store op associated with the region, the location information would co...
Enumerates different result statuses of slice computation by computeSliceUnion
SliceComputationResult(ResultEnum v)
enum mlir::affine::SliceComputationResult::ResultEnum value