MLIR  16.0.0git
Functions | Variables
OneShotAnalysis.cpp File Reference
#include "mlir/Dialect/Bufferization/Transforms/OneShotAnalysis.h"
#include <random>
#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/TensorCopyInsertion.h"
#include "mlir/Dialect/Func/IR/FuncOps.h"
#include "mlir/Dialect/MemRef/IR/MemRef.h"
#include "mlir/IR/AsmState.h"
#include "mlir/IR/Dominance.h"
#include "mlir/IR/Operation.h"
#include "mlir/IR/TypeUtilities.h"
#include "mlir/Interfaces/ControlFlowInterfaces.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/SetVector.h"
+ Include dependency graph for OneShotAnalysis.cpp:

Go to the source code of this file.

Functions

static bool isaTensor (Type t)
 
static void setInPlaceOpOperand (OpOperand &opOperand, bool inPlace)
 Mark whether OpOperand will be bufferized inplace. More...
 
static bool isInplaceMemoryWrite (OpOperand &opOperand, const BufferizationAliasInfo &aliasInfo, const AnalysisState &state)
 Return true if opOperand has been decided to bufferize in-place. More...
 
static bool happensBefore (Operation *a, Operation *b, const DominanceInfo &domInfo)
 Return true if a happens before b, i.e., a or one of its ancestors properly dominates b and b is not inside a. More...
 
static Optional< Region * > getCommonEnclosingRepetitiveRegion (ArrayRef< Value > values)
 For each given value, find the closest enclosing repetitive region. More...
 
static bool isMemoryWrite (Value value, const AnalysisState &state)
 Return true if the given tensor value is a memory write. More...
 
static void annotateConflict (OpOperand *uRead, OpOperand *uConflictingWrite, Value lastWrite)
 Annotate IR with details about the detected RaW conflict. More...
 
static bool hasReadAfterWriteInterference (const DenseSet< OpOperand *> &usesRead, const DenseSet< OpOperand *> &usesWrite, const DominanceInfo &domInfo, AnalysisState &state, const BufferizationAliasInfo &aliasInfo)
 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. More...
 
static void getAliasingInplaceWrites (DenseSet< OpOperand *> &res, Value root, const BufferizationAliasInfo &aliasInfo, const AnalysisState &state)
 
static void getAliasingReads (DenseSet< OpOperand *> &res, Value root, const BufferizationAliasInfo &aliasInfo, const AnalysisState &state)
 
static bool wouldCreateReadAfterWriteInterference (OpOperand &operand, const DominanceInfo &domInfo, AnalysisState &state, const BufferizationAliasInfo &aliasInfo, bool checkConsistencyOnly=false)
 Return true if bufferizing operand inplace would create a conflict. More...
 
static bool hasPrecedingAliasingNonWritableTensor (Value value, OpOperand *currentOpOperand, const BufferizationAliasInfo &aliasInfo, const OneShotAnalysisState &state)
 Check the reverse SSA use-def chain (following aliasing OpOperands) for non-writable tensor values. More...
 
static bool wouldCreateWriteToNonWritableBuffer (OpOperand &operand, const BufferizationAliasInfo &aliasInfo, OneShotAnalysisState &state, bool checkConsistencyOnly=false)
 Return true if bufferizing operand inplace would create a write to a non-writable buffer. More...
 
static LogicalResult bufferizableInPlaceAnalysisImpl (OpOperand &operand, BufferizationAliasInfo &aliasInfo, OneShotAnalysisState &state, const DominanceInfo &domInfo)
 Determine if operand can be bufferized in-place. More...
 
static LogicalResult inPlaceAnalysis (SmallVector< Operation *> &ops, BufferizationAliasInfo &aliasInfo, OneShotAnalysisState &state, const DominanceInfo &domInfo, unsigned analysisFuzzerSeed=0)
 Analyze the ops to determine which OpOperands are inplaceable. More...
 
static bool hasTensorSemantics (Operation *op)
 Return true if the given op has a tensor result or a tensor operand. More...
 
static LogicalResult inPlaceAnalysis (Operation *op, BufferizationAliasInfo &aliasInfo, OneShotAnalysisState &state, const DominanceInfo &domInfo, unsigned analysisFuzzerSeed=0)
 Analyze all ops that are contained in op. More...
 
static void equivalenceAnalysis (SmallVector< Operation *> &ops, BufferizationAliasInfo &aliasInfo, AnalysisState &state)
 Analyze equivalence of tied OpResult/OpOperand pairs of the given ops. More...
 
static void equivalenceAnalysis (Operation *op, BufferizationAliasInfo &aliasInfo, AnalysisState &state)
 Analyze equivalence of tied OpResult/OpOperand pairs of all ops contained in op. More...
 
static LogicalResult checkAliasInfoConsistency (Operation *op, const DominanceInfo &domInfo, AnalysisState &state, const BufferizationAliasInfo &aliasInfo)
 Assert that the current bufferization decisions are consistent. More...
 
static void annotateOpsWithBufferizationMarkers (Operation *op, const BufferizationAliasInfo &aliasInfo, AnalysisState &state)
 Annotate the IR with the result of the analysis. For testing/debugging only. More...
 
static LogicalResult assertDestinationPassingStyle (Operation *op, AnalysisState &state, BufferizationAliasInfo &aliasInfo, SmallVector< Operation *> &newOps)
 Assert that IR is in destination-passing style. More...
 

Variables

constexpr StringLiteral kInPlaceResultsAttrName = "__inplace_operands_attr__"
 Attribute marker to specify op results that can be bufferized inPlace. More...
 

Function Documentation

◆ annotateConflict()

static void annotateConflict ( OpOperand uRead,
OpOperand uConflictingWrite,
Value  lastWrite 
)
static

◆ annotateOpsWithBufferizationMarkers()

static void annotateOpsWithBufferizationMarkers ( Operation op,
const BufferizationAliasInfo aliasInfo,
AnalysisState state 
)
static

Annotate the IR with the result of the analysis. For testing/debugging only.

Definition at line 860 of file OneShotAnalysis.cpp.

References mlir::Operation::getOpOperands(), mlir::bufferization::BufferizationAliasInfo::isInPlace(), setInPlaceOpOperand(), and mlir::Operation::walk().

Referenced by mlir::bufferization::analyzeOp().

◆ assertDestinationPassingStyle()

static LogicalResult assertDestinationPassingStyle ( Operation op,
AnalysisState state,
BufferizationAliasInfo aliasInfo,
SmallVector< Operation *> &  newOps 
)
static

Assert that IR is in destination-passing style.

I.e., every value that is returned or yielded from a block is:

  • aliasing a bbArg of that block or a parent block, or
  • aliasing an OpResult of a op in a parent block.

Example:

%0 = "some_op" : tensor<?xf32>
%1 = scf.if %c -> (tensor<?xf32>) {
scf.yield %0 : tensor<?xf32>
} else {
%t = linalg.alloc_tensor : tensor<?xf32>
scf.yield %t : tensor<?xf32>
}

In the above example, the first scf.yield op satifies destination-passing style because the yielded value %0 is defined in the parent block. The second scf.yield op does not satisfy destination-passing style because the yielded value t is defined in the same block as the scf.yield op.

Definition at line 895 of file OneShotAnalysis.cpp.

References mlir::WalkResult::advance(), mlir::bufferization::BufferizationAliasInfo::applyOnEquivalenceClass(), mlir::Value::dyn_cast(), mlir::Operation::emitError(), mlir::Value::getDefiningOp(), mlir::Operation::getOpOperands(), mlir::Operation::getParentOp(), mlir::Value::getType(), happensBefore(), mlir::Type::isa(), mlir::isRegionReturnLike(), mlir::success(), and mlir::Operation::walk().

Referenced by mlir::bufferization::analyzeOp().

◆ bufferizableInPlaceAnalysisImpl()

static LogicalResult bufferizableInPlaceAnalysisImpl ( OpOperand operand,
BufferizationAliasInfo aliasInfo,
OneShotAnalysisState state,
const DominanceInfo domInfo 
)
static

◆ checkAliasInfoConsistency()

static LogicalResult checkAliasInfoConsistency ( Operation op,
const DominanceInfo domInfo,
AnalysisState state,
const BufferizationAliasInfo aliasInfo 
)
static

◆ equivalenceAnalysis() [1/2]

static void equivalenceAnalysis ( SmallVector< Operation *> &  ops,
BufferizationAliasInfo aliasInfo,
AnalysisState state 
)
static

Analyze equivalence of tied OpResult/OpOperand pairs of the given ops.

Definition at line 797 of file OneShotAnalysis.cpp.

References mlir::bufferization::Equivalent, and mlir::bufferization::BufferizationAliasInfo::unionEquivalenceClasses().

Referenced by mlir::bufferization::analyzeOp(), and equivalenceAnalysis().

◆ equivalenceAnalysis() [2/2]

static void equivalenceAnalysis ( Operation op,
BufferizationAliasInfo aliasInfo,
AnalysisState state 
)
static

Analyze equivalence of tied OpResult/OpOperand pairs of all ops contained in op.

Definition at line 814 of file OneShotAnalysis.cpp.

References equivalenceAnalysis(), mlir::Operation::getResultTypes(), isaTensor(), mlir::PostOrder, and mlir::Operation::walk().

◆ getAliasingInplaceWrites()

static void getAliasingInplaceWrites ( DenseSet< OpOperand *> &  res,
Value  root,
const BufferizationAliasInfo aliasInfo,
const AnalysisState state 
)
static

◆ getAliasingReads()

static void getAliasingReads ( DenseSet< OpOperand *> &  res,
Value  root,
const BufferizationAliasInfo aliasInfo,
const AnalysisState state 
)
static

Definition at line 593 of file OneShotAnalysis.cpp.

Referenced by wouldCreateReadAfterWriteInterference().

◆ getCommonEnclosingRepetitiveRegion()

static Optional<Region *> getCommonEnclosingRepetitiveRegion ( ArrayRef< Value values)
static

For each given value, find the closest enclosing repetitive region.

If this is the same region for each value, return it. Otherwise return None. Note: If there is no enclosing repetitive region, return nullptr.

Definition at line 358 of file OneShotAnalysis.cpp.

References mlir::getEnclosingRepetitiveRegion(), mlir::bufferization::None, and value.

Referenced by hasReadAfterWriteInterference().

◆ happensBefore()

static bool happensBefore ( Operation a,
Operation b,
const DominanceInfo domInfo 
)
static

Return true if a happens before b, i.e., a or one of its ancestors properly dominates b and b is not inside a.

Definition at line 341 of file OneShotAnalysis.cpp.

References mlir::Operation::getParentOp(), mlir::Operation::isProperAncestor(), and mlir::DominanceInfo::properlyDominates().

Referenced by assertDestinationPassingStyle(), and hasReadAfterWriteInterference().

◆ hasPrecedingAliasingNonWritableTensor()

static bool hasPrecedingAliasingNonWritableTensor ( Value  value,
OpOperand currentOpOperand,
const BufferizationAliasInfo aliasInfo,
const OneShotAnalysisState state 
)
static

Check the reverse SSA use-def chain (following aliasing OpOperands) for non-writable tensor values.

Stop searching when an out-of-place bufferized OpOperand was found (or when the OpOperand was not bufferized yet). currentOpOperand is assumed to be in-place, even if that decision was not materialized in aliasInfo yet.

Definition at line 658 of file OneShotAnalysis.cpp.

References mlir::Value::dyn_cast(), mlir::bufferization::AnalysisState::getAliasingOpOperand(), mlir::bufferization::BufferizationAliasInfo::isInPlace(), and mlir::bufferization::OneShotAnalysisState::isWritable().

Referenced by wouldCreateWriteToNonWritableBuffer().

◆ hasReadAfterWriteInterference()

static bool hasReadAfterWriteInterference ( const DenseSet< OpOperand *> &  usesRead,
const DenseSet< OpOperand *> &  usesWrite,
const DominanceInfo domInfo,
AnalysisState state,
const BufferizationAliasInfo aliasInfo 
)
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 write W1. But because of bufferization decisions, R actually reads another write W2.

Definition at line 421 of file OneShotAnalysis.cpp.

References annotateConflict(), mlir::bufferization::BufferizationOptions::dynCastBufferizableOp(), getCommonEnclosingRepetitiveRegion(), mlir::getEnclosingRepetitiveRegion(), happensBefore(), mlir::insideMutuallyExclusiveRegions(), isMemoryWrite(), and mlir::bufferization::BufferizationOptions::printConflicts.

Referenced by wouldCreateReadAfterWriteInterference().

◆ hasTensorSemantics()

static bool hasTensorSemantics ( Operation op)
static

Return true if the given op has a tensor result or a tensor operand.

Definition at line 772 of file OneShotAnalysis.cpp.

References mlir::Operation::getOperandTypes(), mlir::Operation::getResultTypes(), and isaTensor().

Referenced by inPlaceAnalysis().

◆ inPlaceAnalysis() [1/2]

static LogicalResult inPlaceAnalysis ( SmallVector< Operation *> &  ops,
BufferizationAliasInfo aliasInfo,
OneShotAnalysisState state,
const DominanceInfo domInfo,
unsigned  analysisFuzzerSeed = 0 
)
static

Analyze the ops to determine which OpOperands are inplaceable.

Walk ops in reverse and bufferize ops greedily. This is a good starter heuristic.

Even if an op does not read or write, it may still create an alias when bufferized in-place. An example of such ops is tensor.extract_slice.

Rationale for bufferizing %1 = tensor.extract_slice %0[...] inplace:

When bufferized out of place, an ExtractSliceOp lowers to alloc + copy. This cannot change the flow of information for either the source or the result buffers.

When bufferized inplace, an ExtractSliceOp does not by itself create any read or write from memory. Instead, it has the effect of merging the alias sets of the source and the result buffers.

An analysis is required to ensure inplace bufferization would not result in RaW dependence violations.

Definition at line 746 of file OneShotAnalysis.cpp.

References bufferizableInPlaceAnalysisImpl(), mlir::bufferization::BufferizationOptions::dynCastBufferizableOp(), mlir::failed(), mlir::failure(), mlir::bufferization::AnalysisState::getOptions(), and mlir::success().

Referenced by mlir::bufferization::analyzeOp(), and inPlaceAnalysis().

◆ inPlaceAnalysis() [2/2]

static LogicalResult inPlaceAnalysis ( Operation op,
BufferizationAliasInfo aliasInfo,
OneShotAnalysisState state,
const DominanceInfo domInfo,
unsigned  analysisFuzzerSeed = 0 
)
static

Analyze all ops that are contained in op.

Definition at line 779 of file OneShotAnalysis.cpp.

References hasTensorSemantics(), inPlaceAnalysis(), and mlir::Operation::walk().

◆ isaTensor()

static bool isaTensor ( Type  t)
static

Definition at line 63 of file OneShotAnalysis.cpp.

References mlir::Type::isa().

Referenced by equivalenceAnalysis(), and hasTensorSemantics().

◆ isInplaceMemoryWrite()

static bool isInplaceMemoryWrite ( OpOperand opOperand,
const BufferizationAliasInfo aliasInfo,
const AnalysisState state 
)
static

Return true if opOperand has been decided to bufferize in-place.

Definition at line 329 of file OneShotAnalysis.cpp.

References mlir::bufferization::BufferizationAliasInfo::isInPlace().

◆ isMemoryWrite()

static bool isMemoryWrite ( Value  value,
const AnalysisState state 
)
static

Return true if the given tensor value is a memory write.

Most values are tensor writes, but ops that define a tensor SSA value without specifying its contents (e.g., alloc_tensor) are not.

Definition at line 371 of file OneShotAnalysis.cpp.

References mlir::Value::dyn_cast().

Referenced by hasReadAfterWriteInterference(), and mlir::bufferization::populateDynamicDimSizes().

◆ setInPlaceOpOperand()

static void setInPlaceOpOperand ( OpOperand opOperand,
bool  inPlace 
)
static

◆ wouldCreateReadAfterWriteInterference()

static bool wouldCreateReadAfterWriteInterference ( OpOperand operand,
const DominanceInfo domInfo,
AnalysisState state,
const BufferizationAliasInfo aliasInfo,
bool  checkConsistencyOnly = false 
)
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 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 633 of file OneShotAnalysis.cpp.

References mlir::IROperand< DerivedT, IRValueT >::get(), getAliasingInplaceWrites(), getAliasingReads(), and hasReadAfterWriteInterference().

Referenced by bufferizableInPlaceAnalysisImpl(), and checkAliasInfoConsistency().

◆ wouldCreateWriteToNonWritableBuffer()

static bool wouldCreateWriteToNonWritableBuffer ( OpOperand operand,
const BufferizationAliasInfo aliasInfo,
OneShotAnalysisState state,
bool  checkConsistencyOnly = false 
)
static

Variable Documentation

◆ kInPlaceResultsAttrName

constexpr StringLiteral kInPlaceResultsAttrName = "__inplace_operands_attr__"

Attribute marker to specify op results that can be bufferized inPlace.

Definition at line 74 of file OneShotAnalysis.cpp.

Referenced by setInPlaceOpOperand().