[RFC][mlir] ViewLikeOpInterface method for detecting partial views. #164020
Conversation
I am trying to simplify the implementation of Flang's AliasAnalysis by using ViewLikeOpInterface for some FIR dialect operations. Currently, Flang's AliasAnalysis implementation explicitly recognizes specific set of operations, which is inconvenient. ViewLikeOpInterface may also be used in other parts of Flang. In this patch, I only add ViewLikeOpInterface support to few FIR operations to demonstrate the intent. Flang's alias analysis LIT tests are failing with this change, and I would like to get some advices on how to proceed. As soon as I add, ViewLikeOpInterface interface support for FIR operations, the LocalAliasAnalysis kicks in, and starts reporting `MustAlias` for some cases where Flang currently reports MayAlias. I believe both analyses are incorrect here: they should actually report `PartialAlias` for those cases. This is what the new method `isSameStart` should be used for. I would like to fix both LocalAliasAnalysis and Flang's alias analysis to return `PartialAlias` in those cases, but I am not sure if querying `isSameStart` is enough - see the TBD comment in ViewLikeInterface.td. If my understanding of `PartialAlias` is correct, then we can have a partial alias even when the starting addresses of the source and the resulting view are the same - though, I might be wrong.
vzakhari
requested review from
Renaud-K,
River707,
jeanPerier,
joker-eph and
razvanlupusoru
llvmbot
added
mlir
flang
|
@llvm/pr-subscribers-mlir-memref @llvm/pr-subscribers-mlir Author: Slava Zakharin (vzakhari) ChangesI am trying to simplify the implementation of Flang's AliasAnalysis In this patch, I only add ViewLikeOpInterface support to few As soon as I add, ViewLikeOpInterface interface support for FIR This is what the new method I would like to fix both LocalAliasAnalysis and Flang's alias analysis If my understanding of Full diff: https://github.com/llvm/llvm-project/pull/164020.diff 5 Files Affected:
diff --git a/flang/include/flang/Optimizer/Dialect/FIROps.h b/flang/include/flang/Optimizer/Dialect/FIROps.h
index 62ef8b4b502f2..4651f2bb8038e 100644
--- a/flang/include/flang/Optimizer/Dialect/FIROps.h
+++ b/flang/include/flang/Optimizer/Dialect/FIROps.h
@@ -20,6 +20,7 @@
#include "mlir/Dialect/LLVMIR/LLVMAttrs.h"
#include "mlir/Interfaces/LoopLikeInterface.h"
#include "mlir/Interfaces/SideEffectInterfaces.h"
+#include "mlir/Interfaces/ViewLikeInterface.h"
namespace fir {
diff --git a/flang/include/flang/Optimizer/Dialect/FIROps.td b/flang/include/flang/Optimizer/Dialect/FIROps.td
index fc6eedc6ed4c6..5ce7390fca0d8 100644
--- a/flang/include/flang/Optimizer/Dialect/FIROps.td
+++ b/flang/include/flang/Optimizer/Dialect/FIROps.td
@@ -17,6 +17,7 @@
include "mlir/Dialect/Arith/IR/ArithBase.td"
include "mlir/Dialect/Arith/IR/ArithOpsInterfaces.td"
include "mlir/Dialect/LLVMIR/LLVMAttrDefs.td"
+include "mlir/Interfaces/ViewLikeInterface.td"
include "flang/Optimizer/Dialect/CUF/Attributes/CUFAttr.td"
include "flang/Optimizer/Dialect/FIRDialect.td"
include "flang/Optimizer/Dialect/FIRTypes.td"
@@ -1730,8 +1731,9 @@ def fir_ArrayMergeStoreOp : fir_Op<"array_merge_store",
// Record and array type operations
//===----------------------------------------------------------------------===//
-def fir_ArrayCoorOp : fir_Op<"array_coor",
- [NoMemoryEffect, AttrSizedOperandSegments]> {
+def fir_ArrayCoorOp
+ : fir_Op<"array_coor", [NoMemoryEffect, AttrSizedOperandSegments,
+ ViewLikeOpInterface]> {
let summary = "Find the coordinate of an element of an array";
@@ -1774,9 +1776,13 @@ def fir_ArrayCoorOp : fir_Op<"array_coor",
let hasVerifier = 1;
let hasCanonicalizer = 1;
+ let extraClassDeclaration = [{
+ mlir::Value getViewSource() { return getMemref(); }
+ }];
}
-def fir_CoordinateOp : fir_Op<"coordinate_of", [NoMemoryEffect]> {
+def fir_CoordinateOp
+ : fir_Op<"coordinate_of", [NoMemoryEffect, ViewLikeOpInterface]> {
let summary = "Finds the coordinate (location) of a value in memory";
@@ -1828,6 +1834,7 @@ def fir_CoordinateOp : fir_Op<"coordinate_of", [NoMemoryEffect]> {
let extraClassDeclaration = [{
constexpr static int32_t kDynamicIndex = std::numeric_limits<int32_t>::min();
CoordinateIndicesAdaptor getIndices();
+ mlir::Value getViewSource() { return getRef(); }
}];
}
@@ -2792,7 +2799,8 @@ def fir_VolatileCastOp : fir_SimpleOneResultOp<"volatile_cast", [Pure]> {
let hasFolder = 1;
}
-def fir_ConvertOp : fir_SimpleOneResultOp<"convert", [NoMemoryEffect]> {
+def fir_ConvertOp
+ : fir_SimpleOneResultOp<"convert", [NoMemoryEffect, ViewLikeOpInterface]> {
let summary = "encapsulates all Fortran entity type conversions";
let description = [{
@@ -2830,6 +2838,8 @@ def fir_ConvertOp : fir_SimpleOneResultOp<"convert", [NoMemoryEffect]> {
static bool isPointerCompatible(mlir::Type ty);
static bool canBeConverted(mlir::Type inType, mlir::Type outType);
static bool areVectorsCompatible(mlir::Type inTy, mlir::Type outTy);
+ mlir::Value getViewSource() { return getValue(); }
+ bool isSameStart() { return true; }
}];
let hasCanonicalizer = 1;
}
diff --git a/flang/lib/Optimizer/Analysis/AliasAnalysis.cpp b/flang/lib/Optimizer/Analysis/AliasAnalysis.cpp
index 73ddd1ff80126..f3470ecaa0ffc 100644
--- a/flang/lib/Optimizer/Analysis/AliasAnalysis.cpp
+++ b/flang/lib/Optimizer/Analysis/AliasAnalysis.cpp
@@ -559,10 +559,19 @@ AliasAnalysis::Source AliasAnalysis::getSource(mlir::Value v,
type = SourceKind::Allocate;
breakFromLoop = true;
})
- .Case<fir::ConvertOp>([&](auto op) {
- // Skip ConvertOp's and track further through the operand.
- v = op->getOperand(0);
+ .Case<mlir::ViewLikeOpInterface>([&](auto op) {
+ if (isPointerReference(ty))
+ attributes.set(Attribute::Pointer);
+ v = op.getViewSource();
defOp = v.getDefiningOp();
+ // If the source is a box, and the result is not a box,
+ // then this is one of the box "unpacking" operations,
+ // so we should set followingData.
+ if (mlir::isa<fir::BaseBoxType>(v.getType()) &&
+ !mlir::isa<fir::BaseBoxType>(ty))
+ followingData = true;
+ if (!op.isSameStart())
+ approximateSource = true;
})
.Case<fir::PackArrayOp>([&](auto op) {
// The packed array is not distinguishable from the original
@@ -578,15 +587,6 @@ AliasAnalysis::Source AliasAnalysis::getSource(mlir::Value v,
if (mlir::isa<fir::BaseBoxType>(v.getType()))
followBoxData = true;
})
- .Case<fir::ArrayCoorOp, fir::CoordinateOp>([&](auto op) {
- if (isPointerReference(ty))
- attributes.set(Attribute::Pointer);
- v = op->getOperand(0);
- defOp = v.getDefiningOp();
- if (mlir::isa<fir::BaseBoxType>(v.getType()))
- followBoxData = true;
- approximateSource = true;
- })
.Case<fir::EmboxOp, fir::ReboxOp>([&](auto op) {
if (followBoxData) {
v = op->getOperand(0);
diff --git a/mlir/include/mlir/Interfaces/ViewLikeInterface.td b/mlir/include/mlir/Interfaces/ViewLikeInterface.td
index 131c1a0d92b24..5903623572b6e 100644
--- a/mlir/include/mlir/Interfaces/ViewLikeInterface.td
+++ b/mlir/include/mlir/Interfaces/ViewLikeInterface.td
@@ -23,21 +23,34 @@ def ViewLikeOpInterface : OpInterface<"ViewLikeOpInterface"> {
}];
let cppNamespace = "::mlir";
- let methods = [
- InterfaceMethod<
- "Returns the source buffer from which the view is created.",
- "::mlir::Value", "getViewSource">,
- InterfaceMethod<
- /*desc=*/[{ Returns the buffer which the view created. }],
- /*retTy=*/"::mlir::Value",
- /*methodName=*/"getViewDest",
- /*args=*/(ins),
- /*methodBody=*/"",
- /*defaultImplementation=*/[{
+ let methods =
+ [InterfaceMethod<
+ "Returns the source buffer from which the view is created.",
+ "::mlir::Value", "getViewSource">,
+ InterfaceMethod<
+ /*desc=*/[{ Returns the buffer which the view created. }],
+ /*retTy=*/"::mlir::Value",
+ /*methodName=*/"getViewDest",
+ /*args=*/(ins),
+ /*methodBody=*/"",
+ /*defaultImplementation=*/[{
return $_op->getResult(0);
- }]
- >
- ];
+ }]>,
+ InterfaceMethod<
+ // TBD: should it be generalized into isPartialView that will
+ // return true in any of these cases?
+ // 1. Resulting view is a slice view of the source.
+ // 2. Resulting view's start does not match the source's start.
+ // 3. Resulting view's end does not match the source's end.
+ /*desc=*/
+ [{ Returns true iff the source buffer and the resulting view start at the same "address". }],
+ /*retTy=*/"bool",
+ /*methodName=*/"isSameStart",
+ /*args=*/(ins),
+ /*methodBody=*/"",
+ /*defaultImplementation=*/[{
+ return false;
+ }]>];
}
def OffsetSizeAndStrideOpInterface : OpInterface<"OffsetSizeAndStrideOpInterface"> {
diff --git a/mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp b/mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp
index a84d10d5d609d..b0ec97bd9f264 100644
--- a/mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp
+++ b/mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp
@@ -129,6 +129,10 @@ static void collectUnderlyingAddressValues(OpResult result, unsigned maxDepth,
// If this is a view, unwrap to the source.
if (ViewLikeOpInterface view = dyn_cast<ViewLikeOpInterface>(op)) {
if (result == view.getViewDest()) {
+ // TODO: if view.isSameStart() returns false here,
+ // we have to make sure that further analysis may return
+ // PartialAlias for all underlying addresses we are going
+ // to collect from this point up the def-use.
return collectUnderlyingAddressValues(view.getViewSource(), maxDepth,
visited, output);
}
|
|
@llvm/pr-subscribers-flang-fir-hlfir Author: Slava Zakharin (vzakhari) ChangesI am trying to simplify the implementation of Flang's AliasAnalysis In this patch, I only add ViewLikeOpInterface support to few As soon as I add, ViewLikeOpInterface interface support for FIR This is what the new method I would like to fix both LocalAliasAnalysis and Flang's alias analysis If my understanding of Full diff: https://github.com/llvm/llvm-project/pull/164020.diff 5 Files Affected:
diff --git a/flang/include/flang/Optimizer/Dialect/FIROps.h b/flang/include/flang/Optimizer/Dialect/FIROps.h
index 62ef8b4b502f2..4651f2bb8038e 100644
--- a/flang/include/flang/Optimizer/Dialect/FIROps.h
+++ b/flang/include/flang/Optimizer/Dialect/FIROps.h
@@ -20,6 +20,7 @@
#include "mlir/Dialect/LLVMIR/LLVMAttrs.h"
#include "mlir/Interfaces/LoopLikeInterface.h"
#include "mlir/Interfaces/SideEffectInterfaces.h"
+#include "mlir/Interfaces/ViewLikeInterface.h"
namespace fir {
diff --git a/flang/include/flang/Optimizer/Dialect/FIROps.td b/flang/include/flang/Optimizer/Dialect/FIROps.td
index fc6eedc6ed4c6..5ce7390fca0d8 100644
--- a/flang/include/flang/Optimizer/Dialect/FIROps.td
+++ b/flang/include/flang/Optimizer/Dialect/FIROps.td
@@ -17,6 +17,7 @@
include "mlir/Dialect/Arith/IR/ArithBase.td"
include "mlir/Dialect/Arith/IR/ArithOpsInterfaces.td"
include "mlir/Dialect/LLVMIR/LLVMAttrDefs.td"
+include "mlir/Interfaces/ViewLikeInterface.td"
include "flang/Optimizer/Dialect/CUF/Attributes/CUFAttr.td"
include "flang/Optimizer/Dialect/FIRDialect.td"
include "flang/Optimizer/Dialect/FIRTypes.td"
@@ -1730,8 +1731,9 @@ def fir_ArrayMergeStoreOp : fir_Op<"array_merge_store",
// Record and array type operations
//===----------------------------------------------------------------------===//
-def fir_ArrayCoorOp : fir_Op<"array_coor",
- [NoMemoryEffect, AttrSizedOperandSegments]> {
+def fir_ArrayCoorOp
+ : fir_Op<"array_coor", [NoMemoryEffect, AttrSizedOperandSegments,
+ ViewLikeOpInterface]> {
let summary = "Find the coordinate of an element of an array";
@@ -1774,9 +1776,13 @@ def fir_ArrayCoorOp : fir_Op<"array_coor",
let hasVerifier = 1;
let hasCanonicalizer = 1;
+ let extraClassDeclaration = [{
+ mlir::Value getViewSource() { return getMemref(); }
+ }];
}
-def fir_CoordinateOp : fir_Op<"coordinate_of", [NoMemoryEffect]> {
+def fir_CoordinateOp
+ : fir_Op<"coordinate_of", [NoMemoryEffect, ViewLikeOpInterface]> {
let summary = "Finds the coordinate (location) of a value in memory";
@@ -1828,6 +1834,7 @@ def fir_CoordinateOp : fir_Op<"coordinate_of", [NoMemoryEffect]> {
let extraClassDeclaration = [{
constexpr static int32_t kDynamicIndex = std::numeric_limits<int32_t>::min();
CoordinateIndicesAdaptor getIndices();
+ mlir::Value getViewSource() { return getRef(); }
}];
}
@@ -2792,7 +2799,8 @@ def fir_VolatileCastOp : fir_SimpleOneResultOp<"volatile_cast", [Pure]> {
let hasFolder = 1;
}
-def fir_ConvertOp : fir_SimpleOneResultOp<"convert", [NoMemoryEffect]> {
+def fir_ConvertOp
+ : fir_SimpleOneResultOp<"convert", [NoMemoryEffect, ViewLikeOpInterface]> {
let summary = "encapsulates all Fortran entity type conversions";
let description = [{
@@ -2830,6 +2838,8 @@ def fir_ConvertOp : fir_SimpleOneResultOp<"convert", [NoMemoryEffect]> {
static bool isPointerCompatible(mlir::Type ty);
static bool canBeConverted(mlir::Type inType, mlir::Type outType);
static bool areVectorsCompatible(mlir::Type inTy, mlir::Type outTy);
+ mlir::Value getViewSource() { return getValue(); }
+ bool isSameStart() { return true; }
}];
let hasCanonicalizer = 1;
}
diff --git a/flang/lib/Optimizer/Analysis/AliasAnalysis.cpp b/flang/lib/Optimizer/Analysis/AliasAnalysis.cpp
index 73ddd1ff80126..f3470ecaa0ffc 100644
--- a/flang/lib/Optimizer/Analysis/AliasAnalysis.cpp
+++ b/flang/lib/Optimizer/Analysis/AliasAnalysis.cpp
@@ -559,10 +559,19 @@ AliasAnalysis::Source AliasAnalysis::getSource(mlir::Value v,
type = SourceKind::Allocate;
breakFromLoop = true;
})
- .Case<fir::ConvertOp>([&](auto op) {
- // Skip ConvertOp's and track further through the operand.
- v = op->getOperand(0);
+ .Case<mlir::ViewLikeOpInterface>([&](auto op) {
+ if (isPointerReference(ty))
+ attributes.set(Attribute::Pointer);
+ v = op.getViewSource();
defOp = v.getDefiningOp();
+ // If the source is a box, and the result is not a box,
+ // then this is one of the box "unpacking" operations,
+ // so we should set followingData.
+ if (mlir::isa<fir::BaseBoxType>(v.getType()) &&
+ !mlir::isa<fir::BaseBoxType>(ty))
+ followingData = true;
+ if (!op.isSameStart())
+ approximateSource = true;
})
.Case<fir::PackArrayOp>([&](auto op) {
// The packed array is not distinguishable from the original
@@ -578,15 +587,6 @@ AliasAnalysis::Source AliasAnalysis::getSource(mlir::Value v,
if (mlir::isa<fir::BaseBoxType>(v.getType()))
followBoxData = true;
})
- .Case<fir::ArrayCoorOp, fir::CoordinateOp>([&](auto op) {
- if (isPointerReference(ty))
- attributes.set(Attribute::Pointer);
- v = op->getOperand(0);
- defOp = v.getDefiningOp();
- if (mlir::isa<fir::BaseBoxType>(v.getType()))
- followBoxData = true;
- approximateSource = true;
- })
.Case<fir::EmboxOp, fir::ReboxOp>([&](auto op) {
if (followBoxData) {
v = op->getOperand(0);
diff --git a/mlir/include/mlir/Interfaces/ViewLikeInterface.td b/mlir/include/mlir/Interfaces/ViewLikeInterface.td
index 131c1a0d92b24..5903623572b6e 100644
--- a/mlir/include/mlir/Interfaces/ViewLikeInterface.td
+++ b/mlir/include/mlir/Interfaces/ViewLikeInterface.td
@@ -23,21 +23,34 @@ def ViewLikeOpInterface : OpInterface<"ViewLikeOpInterface"> {
}];
let cppNamespace = "::mlir";
- let methods = [
- InterfaceMethod<
- "Returns the source buffer from which the view is created.",
- "::mlir::Value", "getViewSource">,
- InterfaceMethod<
- /*desc=*/[{ Returns the buffer which the view created. }],
- /*retTy=*/"::mlir::Value",
- /*methodName=*/"getViewDest",
- /*args=*/(ins),
- /*methodBody=*/"",
- /*defaultImplementation=*/[{
+ let methods =
+ [InterfaceMethod<
+ "Returns the source buffer from which the view is created.",
+ "::mlir::Value", "getViewSource">,
+ InterfaceMethod<
+ /*desc=*/[{ Returns the buffer which the view created. }],
+ /*retTy=*/"::mlir::Value",
+ /*methodName=*/"getViewDest",
+ /*args=*/(ins),
+ /*methodBody=*/"",
+ /*defaultImplementation=*/[{
return $_op->getResult(0);
- }]
- >
- ];
+ }]>,
+ InterfaceMethod<
+ // TBD: should it be generalized into isPartialView that will
+ // return true in any of these cases?
+ // 1. Resulting view is a slice view of the source.
+ // 2. Resulting view's start does not match the source's start.
+ // 3. Resulting view's end does not match the source's end.
+ /*desc=*/
+ [{ Returns true iff the source buffer and the resulting view start at the same "address". }],
+ /*retTy=*/"bool",
+ /*methodName=*/"isSameStart",
+ /*args=*/(ins),
+ /*methodBody=*/"",
+ /*defaultImplementation=*/[{
+ return false;
+ }]>];
}
def OffsetSizeAndStrideOpInterface : OpInterface<"OffsetSizeAndStrideOpInterface"> {
diff --git a/mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp b/mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp
index a84d10d5d609d..b0ec97bd9f264 100644
--- a/mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp
+++ b/mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp
@@ -129,6 +129,10 @@ static void collectUnderlyingAddressValues(OpResult result, unsigned maxDepth,
// If this is a view, unwrap to the source.
if (ViewLikeOpInterface view = dyn_cast<ViewLikeOpInterface>(op)) {
if (result == view.getViewDest()) {
+ // TODO: if view.isSameStart() returns false here,
+ // we have to make sure that further analysis may return
+ // PartialAlias for all underlying addresses we are going
+ // to collect from this point up the def-use.
return collectUnderlyingAddressValues(view.getViewSource(), maxDepth,
visited, output);
}
|
There was a problem hiding this comment.
It makes sense to me to add the ViewLikeOpInterface to these FIR operations, thanks Slava.
If my understanding of PartialAlias is correct, then we can have a partial alias even when the starting addresses of the source and the resulting view are the same - though, I might be wrong.
That is also my reading of LLVM/MLIR documentation, although I have little experience with how it is used in practice.
|
Hi Slava! Thank you for your proposal! I agree with your points:
Core issue: ViewLikeOpInterface is overloaded Looking at the MemRef dialect, Category 1: Complete alias (same entity, different type):
Category 2: Partial overlap (subset of entity):
Thus, when Proposed solution: I suggest introducing a
This would make Operations like What do you think? |
|
Thank you for the comments, Jean and Razvan. Regarding I thought a bit more about this, and I think that for aliasing analysis we should only care about the beginning of the input and result buffers. For example, if the initial view is Maybe, it is worth having the following two methods in the
|
Interesting - I double-checked against LLVM and its documentation for However, I would like to point out that even LLVM's implementations for alias analysis are not strict about this. For example, a quick search revealed at least one spot where the same base address returns To me, it makes more sense to return Regarding your suggestion to capture all of this in Thank you for your proposal, Slava! |
Thanks for the example! I am not sure if the code actually implies "the same base address returns PartialAlias". I believe in this code, |
in more cases. There are still cases where LocalAliasAnalysis incorrectly returns MustAlias (see mlir/test/Analysis/test-alias-analysis.mlir). Also see a NOTE in flang/test/Analysis/AliasAnalysis/ptr-component.fir, where combining LocalAliasAnalysis result (PartialAlias) and FIR AliasAnalysis result (NoAlias) results in PartialAlias, which is more conservative than the previous NoAlias result. It is unclear how to address this case, given the merging rules for multiple alias analyses' results.
|
Here is what I have in the latest commit: I tried not to change the current LocalAliasAnalysis implementation too much. There are still cases where it incorrectly reports MustAlias instead of PartialAlias. Moreover, the order of visiting affects whether MustAlias or PartialAlias is returned. @River707 do you have any comments? |
4 participants
I am trying to simplify the implementation of Flang's AliasAnalysis
by using ViewLikeOpInterface for some FIR dialect operations.
Currently, Flang's AliasAnalysis implementation explicitly recognizes
specific set of operations, which is inconvenient.
ViewLikeOpInterface may also be used in other parts of Flang.
In this patch, I only add ViewLikeOpInterface support to few
FIR operations to demonstrate the intent. Flang's alias analysis
LIT tests are failing with this change, and I would like to get
some advices on how to proceed.
As soon as I add, ViewLikeOpInterface interface support for FIR
operations, the LocalAliasAnalysis kicks in, and starts reporting
MustAliasfor some cases where Flang currently reports MayAlias.I believe both analyses are incorrect here: they should actually
report
PartialAliasfor those cases.This is what the new method
isSameStartshould be used for.I would like to fix both LocalAliasAnalysis and Flang's alias analysis
to return
PartialAliasin those cases, but I am not sure ifquerying
isSameStartis enough - see the TBD comment inViewLikeInterface.td.
If my understanding of
PartialAliasis correct, then we can havea partial alias even when the starting addresses of the source
and the resulting view are the same - though, I might be wrong.