#include "mlir/Dialect/Bufferization/Transforms/OneShotAnalysis.h"#include <random>#include <tuple>#include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.h"#include "mlir/Dialect/Bufferization/IR/Bufferization.h"#include "mlir/Dialect/Bufferization/Transforms/Bufferize.h"#include "mlir/Dialect/Bufferization/Transforms/Transforms.h"#include "mlir/Dialect/MemRef/IR/MemRef.h"#include "mlir/IR/AsmState.h"#include "mlir/IR/Dominance.h"#include "mlir/IR/Iterators.h"#include "mlir/IR/Operation.h"#include "mlir/IR/TypeUtilities.h"#include "mlir/Interfaces/ControlFlowInterfaces.h"#include "mlir/Interfaces/SubsetOpInterface.h"#include "llvm/ADT/DenseMap.h"#include "llvm/ADT/DenseSet.h"#include "llvm/ADT/STLExtras.h"#include "llvm/ADT/SetVector.h"#include "llvm/ADT/SmallPtrSet.h"#include "llvm/ADT/SmallVector.h"#include "llvm/Support/DebugLog.h"Go to the source code of this file.
Classes | |
| class | mlir::bufferization::OneShotAnalysisState::CFGReachabilityCache |
| Cached CFG reachability to avoid repeated linear BFS traversals from Block->isReachable. More... | |
| class | mlir::bufferization::OneShotAnalysisState::OpDominanceBlockCache |
| canUseOpDominanceDueToBlocks walks enclosing regions and queries CFG reachability, but the answer is a property of blocks: every op in a block has the same parent chain, and a definition contributes only its block as a reachability barrier. More... | |
Macros | |
| #define | DEBUG_TYPE "one-shot-analysis" |
Functions | |
| static bool | isaTensor (Type t) |
| static void | setInPlaceOpOperand (OpOperand &opOperand, bool inPlace) |
| Mark whether OpOperand will be bufferized inplace. | |
| static bool | detectUnstructuredControlFlow (Operation *op) |
| A region with more than one block is unstructured control flow. | |
| static bool | detectParallelRegions (Operation *op, const BufferizationOptions &options) |
| Return "true" if any allowed op has a parallel region. | |
| static bool | isInplaceMemoryWrite (OpOperand &opOperand, const OneShotAnalysisState &state) |
| Return true if opOperand has been decided to bufferize in-place. | |
| static bool | cannotHappenAfter (Operation *a, Operation *b, const DominanceInfo &domInfo, OneShotAnalysisState &state, SmallPtrSet< Block *, 16 > extraBarriers={}) |
| Return true if a cannot happen after b. | |
| static bool | canUseOpDominanceDueToRegions (OpOperand *uRead, OpOperand *uWrite, const SetVector< Value > &definitions, AnalysisState &state) |
| Return true if op dominance can be used to rule out a read-after-write conflicts based on the ordering of ops. | |
| static bool | computeCanUseOpDominanceDueToBlocks (OpOperand *uRead, OpOperand *uWrite, const SetVector< Value > &definitions, OneShotAnalysisState &state) |
| Return true if op dominance can be used to rule out a read-after-write conflicts based on the ordering of ops. | |
| static bool | canUseOpDominanceDueToBlocks (OpOperand *uRead, OpOperand *uWrite, const SetVector< Value > &definitions, OneShotAnalysisState &state) |
| static bool | canUseOpDominance (OpOperand *uRead, OpOperand *uWrite, const SetVector< Value > &definitions, OneShotAnalysisState &state) |
| static void | annotateConflict (OpOperand *uRead, OpOperand *uConflictingWrite, Value definition) |
| Annotate IR with details about the detected RaW conflict. | |
| static bool | hasEquivalentValueInReverseUseDefChain (AnalysisState &state, OpOperand *start, Value other) |
| Return 'true' if a tensor that is equivalent to other can be found in the reverse use-def chain of start. | |
| static bool | matchesInsertDestination (const AnalysisState &state, OpOperand *opOperand, SubsetInsertionOpInterface subsetOp) |
| Return "true" if the given operand's value is originating from a subset that is equivalent to the subset that subsetOp inserts into. | |
| static bool | areNonConflictingSubsets (OpOperand *uRead, OpOperand *uConflictingWrite, const AnalysisState &state) |
| Return "true" if the given "read" and potentially conflicting "write" are not conflicting due to their subset relationship. | |
| static bool | hasReadAfterWriteInterference (const DenseSet< OpOperand * > &usesRead, const DenseSet< OpOperand * > &usesWrite, const DominanceInfo &domInfo, OneShotAnalysisState &state) |
| Given sets of uses and writes, return true if there is a RaW conflict under the assumption that all given reads/writes alias the same buffer and that all given writes bufferize inplace. | |
| static void | getAliasingInplaceWrites (DenseSet< OpOperand * > &res, Value root, const OneShotAnalysisState &state) |
| static void | getAliasingReads (DenseSet< OpOperand * > &res, Value root, const OneShotAnalysisState &state) |
| static bool | wouldCreateReadAfterWriteInterference (OpOperand &operand, const DominanceInfo &domInfo, OneShotAnalysisState &state, bool checkConsistencyOnly=false) |
| Return true if bufferizing operand inplace would create a conflict. | |
| static void | annotateNonWritableTensor (Value value) |
| Annotate IR with details about the detected non-writability conflict. | |
| static bool | wouldCreateWriteToNonWritableBuffer (OpOperand &operand, OneShotAnalysisState &state, bool checkConsistencyOnly=false) |
| Return true if bufferizing operand inplace would create a write to a non-writable buffer. | |
| static LogicalResult | bufferizableInPlaceAnalysisImpl (OpOperand &operand, OneShotAnalysisState &state, const DominanceInfo &domInfo) |
| Determine if operand can be bufferized in-place. | |
| static void | equivalenceAnalysis (SmallVector< Operation * > &ops, OneShotAnalysisState &state) |
| Analyze equivalence of tied OpResult/OpOperand pairs of the given ops. | |
| static void | equivalenceAnalysis (Operation *op, OneShotAnalysisState &state) |
| Analyze equivalence of tied OpResult/OpOperand pairs of all ops contained in op. | |
| static SmallVector< Operation * > | bottomUpFromTerminatorsHeuristic (Operation *op, const OneShotAnalysisState &state) |
| "Bottom-up from terminators" heuristic. | |
| static void | annotateOpsWithBufferizationMarkers (Operation *op, const OneShotAnalysisState &state) |
| Annotate the IR with the result of the analysis. For testing/debugging only. | |
| static void | annotateOpsWithAliasSets (Operation *op, const OneShotAnalysisState &state) |
Variables | |
| constexpr StringLiteral | kInPlaceOperandsAttrName = "__inplace_operands_attr__" |
| Attribute marker to specify op operands that bufferize in-place. | |
| constexpr StringLiteral | kOpResultAliasSetAttrName |
| constexpr StringLiteral | kBbArgAliasSetAttrName = "__bbarg_alias_set_attr__" |
Macro Definition Documentation
◆ DEBUG_TYPE
| #define DEBUG_TYPE "one-shot-analysis" |
Definition at line 70 of file OneShotAnalysis.cpp.
Function Documentation
◆ annotateConflict()
Annotate IR with details about the detected RaW conflict.
Definition at line 648 of file OneShotAnalysis.cpp.
References b, mlir::Operation::getContext(), mlir::OpOperand::getOperandNumber(), mlir::detail::IROperandBase::getOwner(), and mlir::Operation::setDiscardableAttr().
Referenced by hasReadAfterWriteInterference().
◆ annotateNonWritableTensor()
Annotate IR with details about the detected non-writability conflict.
Definition at line 1193 of file OneShotAnalysis.cpp.
References b, and mlir::Value::getContext().
Referenced by wouldCreateWriteToNonWritableBuffer().
◆ annotateOpsWithAliasSets()
|
static |
Definition at line 1583 of file OneShotAnalysis.cpp.
References mlir::bufferization::OneShotAnalysisState::applyOnAliases(), b, mlir::Operation::getContext(), mlir::Operation::getOpResults(), mlir::Operation::getRegions(), kBbArgAliasSetAttrName, kOpResultAliasSetAttrName, mlir::Value::printAsOperand(), mlir::Operation::setDiscardableAttr(), and mlir::Operation::walk().
Referenced by mlir::bufferization::analyzeOp().
◆ annotateOpsWithBufferizationMarkers()
|
static |
Annotate the IR with the result of the analysis. For testing/debugging only.
Definition at line 1573 of file OneShotAnalysis.cpp.
References mlir::Operation::getOpOperands(), mlir::bufferization::OneShotAnalysisState::isInPlace(), setInPlaceOpOperand(), and mlir::Operation::walk().
Referenced by mlir::bufferization::analyzeOp().
◆ areNonConflictingSubsets()
|
static |
Return "true" if the given "read" and potentially conflicting "write" are not conflicting due to their subset relationship.
The comments in this function are expressed in terms of tensor.extract_slice/tensor.insert_slice pairs, but apply to any subset ops that implement the SubsetInsertionOpInterface.
Definition at line 727 of file OneShotAnalysis.cpp.
References mlir::IROperand< DerivedT, IRValueT >::get(), mlir::detail::IROperandBase::getOwner(), and matchesInsertDestination().
Referenced by mlir::bufferization::OneShotAnalysisState::areNonConflictingSubsetsCached().
◆ bottomUpFromTerminatorsHeuristic()
|
static |
"Bottom-up from terminators" heuristic.
Definition at line 1395 of file OneShotAnalysis.cpp.
References mlir::Value::getDefiningOp(), mlir::Value::getType(), mlir::PostOrder, result, and mlir::Operation::walk().
Referenced by mlir::bufferization::OneShotAnalysisState::analyzeOp().
◆ bufferizableInPlaceAnalysisImpl()
|
static |
Determine if operand can be bufferized in-place.
Definition at line 1300 of file OneShotAnalysis.cpp.
References mlir::bufferization::OneShotAnalysisState::bufferizeInPlace(), mlir::bufferization::OneShotAnalysisState::bufferizeOutOfPlace(), mlir::OpOperand::getOperandNumber(), mlir::detail::IROperandBase::getOwner(), success(), wouldCreateReadAfterWriteInterference(), and wouldCreateWriteToNonWritableBuffer().
Referenced by mlir::bufferization::OneShotAnalysisState::analyzeSingleOp().
◆ cannotHappenAfter()
|
static |
Return true if a cannot happen after b.
True if a properly dominates b and b is not inside a, or if they are in the same region with no CFG path from b to a. Dominance is sufficient but not necessary. E.g.:
^bb0: cf.cond_br c, ^bb1, ^bb2 ^bb1: "op_a"(t) cf.br ^bb3 ^bb2: "op_b"(t) cf.br ^bb3 ^bb3:
op_a does not dominate op_b, but there is no CFG path from op_b to op_a, so op_a cannot happen after op_b.
extraBarriers are extra blocks a CFG path from b to a must not cross.
Definition at line 426 of file OneShotAnalysis.cpp.
References b.
Referenced by hasReadAfterWriteInterference().
◆ canUseOpDominance()
|
static |
Definition at line 640 of file OneShotAnalysis.cpp.
References canUseOpDominanceDueToBlocks(), and canUseOpDominanceDueToRegions().
Referenced by hasReadAfterWriteInterference().
◆ canUseOpDominanceDueToBlocks()
|
static |
Definition at line 615 of file OneShotAnalysis.cpp.
References mlir::bufferization::OneShotAnalysisState::canUseOpDominanceDueToBlocksCached(), computeCanUseOpDominanceDueToBlocks(), mlir::Operation::getBlock(), mlir::detail::IROperandBase::getOwner(), and mlir::bufferization::OneShotAnalysisState::mayHaveUnstructuredControlFlow().
Referenced by canUseOpDominance().
◆ canUseOpDominanceDueToRegions()
|
static |
Return true if op dominance can be used to rule out a read-after-write conflicts based on the ordering of ops.
Returns false if op dominance cannot be used to due region-based loops.
Generalized op dominance can often be used to rule out potential conflicts due to "read happens before write". E.g., the following IR is not a RaW conflict because the read happens before the write.
Example 1: %0 = ... : tensor<?xf32> // DEF "reading_op"(%0) : tensor<?xf32> // READ %1 = "writing_op"(%0) : tensor<?xf32> -> tensor<?xf32> // WRITE
This is no longer true inside loops (or repetitive regions). In such cases, there may not be a meaningful cannotHappenAfter relationship because ops could be executed multiple times. E.g.:
Example 2: %0 = ... : tensor<?xf32> // DEF scf.for ... { "reading_op"(%0) : tensor<?xf32> // READ %1 = "writing_op"(%0) : tensor<?xf32> -> tensor<?xf32> // WRITE ... }
In the above example, reading_op happens before writing_op according to op dominance. However, both ops may happen multiple times; in particular, the second execution of reading_op happens after the first execution of writing_op. This is problematic because the tensor %0 they operate on (i.e., the "definition") is defined outside of the loop.
On a high-level, there is a potential RaW in a program if there exists a possible program execution such that there is a sequence of DEF, followed by WRITE, followed by READ. Each additional DEF resets the sequence.
E.g.: No conflict: DEF, WRITE, DEF, READ Potential conflict: DEF, READ, WRITE, READ, WRITE
Example 1 has no conflict: DEF, READ, WRITE Example 2 has a potential conflict: DEF, (READ, WRITE)* Example 3: scf.for ... { %0 = ... : tensor<?xf32> "reading_op"(%0) : tensor<?xf32> %1 = "writing_op"(%0) : tensor<?xf32> -> tensor<?xf32> ... } This has no conflict: (DEF, READ, WRITE)*
Example 4: %0 = ... : tensor<?xf32> scf.for ... { scf.for ... { "reading_op"(%0) } %1 = "writing_op"(%0) } This has a potential conflict: DEF, ((READ)*, WRITE)*
Example 5: %0 = ... : tensor<?xf32> scf.for ... { %1 = "writing_op"(%0) } scf.for ... { "reading_op"(%0) } This has a potential conflict: DEF, WRITE*, READ*
The following rules are used to rule out RaW conflicts via ordering of ops:
- If the closest enclosing repetitive region of DEF is a proper ancestor of a repetitive region that enclosing both READ and WRITE, we cannot rule out RaW conflict due to the ordering of ops.
- Otherwise: There are no loops that interfere with our analysis; for analysis purposes, we can assume that there are no loops/repetitive regions. I.e., we can rule out a RaW conflict if READ cannot happen after WRITE or WRITE cannot happen after DEF. (Checked in hasReadAfterWriteInterference.)
Definition at line 528 of file OneShotAnalysis.cpp.
References mlir::detail::IROperandBase::getOwner(), mlir::Region::getParentOp(), mlir::Operation::isAncestor(), and options.
Referenced by canUseOpDominance().
◆ computeCanUseOpDominanceDueToBlocks()
|
static |
Return true if op dominance can be used to rule out a read-after-write conflicts based on the ordering of ops.
Returns false if op dominance cannot be used to due block-based loops within a region.
Refer to the canUseOpDominanceDueToRegions documentation for details on how op domiance is used during RaW conflict detection.
On a high-level, there is a potential RaW in a program if there exists a possible program execution such that there is a sequence of DEF, followed by WRITE, followed by READ. Each additional DEF resets the sequence.
Op dominance cannot be used if there is a path from block(READ) to block(WRITE) and a path from block(WRITE) to block(READ). block(DEF) should not appear on that path. Walk from the uses up through enclosing regions and stop at the definition region(s): SSA dominance means a cycle that skips DEF cannot live above DEF.
Definition at line 577 of file OneShotAnalysis.cpp.
References mlir::Region::findAncestorOpInRegion(), mlir::Operation::getBlock(), mlir::detail::IROperandBase::getOwner(), mlir::Operation::getParentOp(), mlir::Region::getParentRegion(), mlir::Region::isAncestor(), and mlir::bufferization::OneShotAnalysisState::isReachableCached().
Referenced by canUseOpDominanceDueToBlocks().
◆ detectParallelRegions()
|
static |
Return "true" if any allowed op has a parallel region.
Definition at line 135 of file OneShotAnalysis.cpp.
References mlir::WalkResult::advance(), mlir::WalkResult::interrupt(), options, mlir::WalkResult::skip(), mlir::Operation::walk(), and mlir::WalkResult::wasInterrupted().
◆ detectUnstructuredControlFlow()
A region with more than one block is unstructured control flow.
Single-block regions, including structured loops, are not.
Definition at line 122 of file OneShotAnalysis.cpp.
References mlir::WalkResult::advance(), mlir::Operation::getRegions(), mlir::WalkResult::interrupt(), mlir::Operation::walk(), and mlir::WalkResult::wasInterrupted().
Referenced by mlir::bufferization::OneShotAnalysisState::OneShotAnalysisState().
◆ equivalenceAnalysis() [1/2]
|
static |
Analyze equivalence of tied OpResult/OpOperand pairs of all ops contained in op.
Definition at line 1380 of file OneShotAnalysis.cpp.
References equivalenceAnalysis(), mlir::Operation::getResultTypes(), isaTensor(), mlir::PostOrder, and mlir::Operation::walk().
◆ equivalenceAnalysis() [2/2]
|
static |
Analyze equivalence of tied OpResult/OpOperand pairs of the given ops.
Definition at line 1330 of file OneShotAnalysis.cpp.
References mlir::bufferization::OneShotAnalysisState::areEquivalentBufferizedValues(), mlir::bufferization::OneShotAnalysisState::getOptions(), mlir::bufferization::OneShotAnalysisState::isInPlace(), and mlir::bufferization::OneShotAnalysisState::unionEquivalenceClasses().
Referenced by mlir::bufferization::OneShotAnalysisState::analyzeOp(), and equivalenceAnalysis().
◆ getAliasingInplaceWrites()
|
static |
Definition at line 1099 of file OneShotAnalysis.cpp.
References mlir::bufferization::OneShotAnalysisState::applyOnAliases(), mlir::Value::getUses(), and isInplaceMemoryWrite().
Referenced by wouldCreateReadAfterWriteInterference(), and wouldCreateWriteToNonWritableBuffer().
◆ getAliasingReads()
|
static |
Definition at line 1110 of file OneShotAnalysis.cpp.
References mlir::bufferization::OneShotAnalysisState::applyOnAliases(), and mlir::Value::getUses().
Referenced by wouldCreateReadAfterWriteInterference().
◆ hasEquivalentValueInReverseUseDefChain()
|
static |
Return 'true' if a tensor that is equivalent to other can be found in the reverse use-def chain of start.
Note: If an OpOperand bufferizes out of place along that use-def chain, the two tensors may not materialize as equivalent buffers (but separate allocations).
Note: This function also requires that the two tensors have equivalent indexing. I.e., the tensor types do not change along the use-def chain, apart from static <-> dynamic dim casts.
Definition at line 689 of file OneShotAnalysis.cpp.
Referenced by hasReadAfterWriteInterference().
◆ hasReadAfterWriteInterference()
|
static |
Given sets of uses and writes, return true if there is a RaW conflict under the assumption that all given reads/writes alias the same buffer and that all given writes bufferize inplace.
A conflict is: According to SSA use-def chains, a read R is supposed to read the result of a definition W1. But because of bufferization decisions, R actually reads another definition W2.
Definition at line 857 of file OneShotAnalysis.cpp.
References annotateConflict(), mlir::bufferization::OneShotAnalysisState::areNonConflictingSubsetsCached(), cannotHappenAfter(), canUseOpDominance(), mlir::Region::findAncestorOpInRegion(), mlir::bufferization::OneShotAnalysisState::findDefinitionsCached(), mlir::Operation::getBlock(), mlir::bufferization::OneShotAnalysisState::getOptions(), mlir::Block::getParent(), hasEquivalentValueInReverseUseDefChain(), mlir::bufferization::OneShotAnalysisState::isReachableCached(), mlir::bufferization::OneShotAnalysisState::mayHaveParallelRegions(), and options.
Referenced by wouldCreateReadAfterWriteInterference().
◆ isaTensor()
Definition at line 75 of file OneShotAnalysis.cpp.
Referenced by equivalenceAnalysis(), and mlir::bufferization::func_ext::FuncOpInterface::hasTensorSemantics().
◆ isInplaceMemoryWrite()
|
static |
Return true if opOperand has been decided to bufferize in-place.
Definition at line 305 of file OneShotAnalysis.cpp.
References mlir::bufferization::OneShotAnalysisState::isInPlace().
Referenced by getAliasingInplaceWrites().
◆ matchesInsertDestination()
|
static |
Return "true" if the given operand's value is originating from a subset that is equivalent to the subset that subsetOp inserts into.
Definition at line 704 of file OneShotAnalysis.cpp.
Referenced by areNonConflictingSubsets().
◆ setInPlaceOpOperand()
Mark whether OpOperand will be bufferized inplace.
Definition at line 94 of file OneShotAnalysis.cpp.
References mlir::IROperand< DerivedT, IRValueT >::get(), mlir::Operation::getDiscardableAttr(), mlir::Operation::getNumOperands(), mlir::OpOperand::getOperandNumber(), mlir::Operation::getOpOperands(), mlir::detail::IROperandBase::getOwner(), mlir::Value::getType(), kInPlaceOperandsAttrName, and mlir::Operation::setDiscardableAttr().
Referenced by annotateOpsWithBufferizationMarkers().
◆ wouldCreateReadAfterWriteInterference()
|
static |
Return true if bufferizing operand inplace would create a conflict.
A read R and a write W of the same alias set is a conflict if inplace bufferization of W changes the value read by R to a value different from the one that would be expected by tracing back R's origin through SSA use-def chains. A conflict can only be introduced by a new alias and/or an inplace bufferization decision.
Example: %0 = tensor.extract_slice t[...][...][1, 1] {inplace?} %1 = vector.transfer_write v1, t {inplace} : vector<5xf32>, tensor<?xf32> e = tensor.extract_slice %1 %2 = vector.transfer_write v2, %0 {inplace} : vector<6xf32>, tensor<?xf32> %3 = vector.transfer_read e, cst : tensor<?xf32>, vector<7xf32>
In the above example, the two TransferWriteOps have already been decided to bufferize inplace. Bufferizing the ExtractSliceOp inplace would create a conflict because:
- According to SSA use-def chains, we expect to read the result of %1.
- However, adding an alias {%0, t} would mean that the second TransferWriteOp overwrites the result of the first one. Therefore, the TransferReadOp would no longer be reading the result of %1.
If checkConsistencyOnly is true, this function checks if there is a read-after-write conflict without bufferizing operand inplace. This would indicate a problem with the current inplace bufferization decisions.
Note: If checkConsistencyOnly, this function may be called with a null OpResult. In that case, only the consistency of bufferization decisions involving aliases of the given OpOperand are checked.
Definition at line 1175 of file OneShotAnalysis.cpp.
References mlir::IROperand< DerivedT, IRValueT >::get(), getAliasingInplaceWrites(), getAliasingReads(), and hasReadAfterWriteInterference().
Referenced by bufferizableInPlaceAnalysisImpl(), and mlir::bufferization::checkPreBufferizationAssumptions().
◆ wouldCreateWriteToNonWritableBuffer()
|
static |
Return true if bufferizing operand inplace would create a write to a non-writable buffer.
Definition at line 1212 of file OneShotAnalysis.cpp.
References annotateNonWritableTensor(), mlir::bufferization::OneShotAnalysisState::applyOnAliases(), mlir::IROperand< DerivedT, IRValueT >::get(), getAliasingInplaceWrites(), mlir::bufferization::OneShotAnalysisState::getOptions(), and mlir::bufferization::OneShotAnalysisState::isWritable().
Referenced by bufferizableInPlaceAnalysisImpl(), and mlir::bufferization::checkPreBufferizationAssumptions().
Variable Documentation
◆ kBbArgAliasSetAttrName
|
constexpr |
Definition at line 91 of file OneShotAnalysis.cpp.
Referenced by annotateOpsWithAliasSets().
◆ kInPlaceOperandsAttrName
|
constexpr |
Attribute marker to specify op operands that bufferize in-place.
Definition at line 86 of file OneShotAnalysis.cpp.
Referenced by setInPlaceOpOperand().
◆ kOpResultAliasSetAttrName
|
constexpr |
Definition at line 88 of file OneShotAnalysis.cpp.
Referenced by annotateOpsWithAliasSets().
Generated on for MLIR by
1.14.0