Page MenuHomePhabricator

[mlir] Split BufferAliasAnalysis into 2 classes
ClosedPublic

Authored by tpopp on Apr 20 2021, 3:52 AM.

Details

Summary

The previous behavior is unmodified as BufferDependencyAnalysis. The new
BufferAliasAnalysis differs by finding all aliases of a buffer rather
than only subviews of the current value.

For example, given a sequence of subviews that create values
A -> B -> C -> d:
BufferDependencyAnalysis::resolve(B) => {B, C, D}
BufferAliasAnalysis::resolve(B) => {A, B, C, D}

The old behavior is needed by BufferDeallocation. The new behavior is
needed by transformations that are not looking for aliases relative to
the original AllocOp.

Diff Detail

Event Timeline

tpopp created this revision.Apr 20 2021, 3:52 AM
tpopp requested review of this revision.Apr 20 2021, 3:52 AM
tpopp updated this revision to Diff 339114.Apr 20 2021, 11:54 PM

Update cmake file and remove friendliness between Analyses

tpopp added a comment.Apr 23 2021, 4:57 AM

Friendly ping.

I am not convinced that DependencyAnalysis is the better name here. For dependencies, I think of read-after-write, etc.. This only computes the flow of buffers through control flow.

mlir/lib/Analysis/BufferDependencyAnalysis.cpp
22 ↗(On Diff #339114)

nit: dependency here, as well?

mlir/lib/Transforms/BufferOptimizations.cpp
329

Why is this needed?

I have to admit that I am not convinced by the general notion of a "dependency". In my opinion, BufferDependencyAnalysis::resolve(B) => {B, C, D}, does not give any guarantees about whether C and D actually depend on B in the sense of true "data dependencies". Instead, C and D can also be block arguments that are pure aliases without any read/write dependencies. Also, BufferAliasAnalysis::resolve(B) => {A, B, C, D} feels to me like A can be an alias of B, which is not actually the case, right? B has two aliases, namely C and D on the one hand. On the other hand, A has three aliases, namely B, C and D. Returning A as an alias of B could cause confusion in the future. What do you think about this?

mlir/lib/Transforms/BufferOptimizations.cpp
329

Is there a specific use case where the current implementation is failing?

dfki-mako added inline comments.Apr 29 2021, 5:07 AM
mlir/lib/Analysis/BufferAliasAnalysis.cpp
53

nit: Comment does not match the implementation.

tpopp marked 3 inline comments as done.Apr 30 2021, 1:19 AM

I am not convinced that DependencyAnalysis is the better name here. For dependencies, I think of read-after-write, etc.. This only computes the flow of buffers through control flow.

I agree. I can't think of a good name though for "Alias analysis but only for aliases not provably earlier in control flow"

Possible names:
BufferSubviewAliasAnalysis
BufferForwardAliasAnalysis
BufferFlowAnalysis
BufferReferenceAnalysis

I have to admit that I am not convinced by the general notion of a "dependency". In my opinion, BufferDependencyAnalysis::resolve(B) => {B, C, D}, does not give any guarantees about whether C and D actually depend on B in the sense of true "data dependencies". Instead, C and D can also be block arguments that are pure aliases without any read/write dependencies. Also, BufferAliasAnalysis::resolve(B) => {A, B, C, D} feels to me like A can be an alias of B, which is not actually the case, right? B has two aliases, namely C and D on the one hand. On the other hand, A has three aliases, namely B, C and D. Returning A as an alias of B could cause confusion in the future. What do you think about this?

Disclaimer:I'm not an expert on this topic, but the following was what I expected BufferAliasing to refer to and is what Wikipedia implies also. I don't think the current BufferAliasAnalysis (BufferDependencyAnalysis in this patch) should exist, if my view on aliases does turn out to be the common definition, but it was just hard or impossible to remove in the current Dealloc pass implementation.

Aliasing is a symmetric property(https://en.wikipedia.org/wiki/Alias_analysis). This AliasAnalysis is fundamentally broken when it thinks that B aliasing A does not have to imply A aliasing B. We should not think of this in terms of "B aliases A" but in terms of "A and B are potential aliases of the same memory location" or "A and B are not guaranteed to be disjoint memory locations".

mlir/lib/Transforms/BufferOptimizations.cpp
329

There was some memory issue at one point, but it's no longer happening as i am using the same structure as previously, so I'll remove this.

329

I was trying to update BufferAliasAnalysis before without BufferDependencyAnalysis and there was some memory issue if I remember correctly(maybe I had some other bug). It's no longer needed though, so I'll revert it.

tpopp marked an inline comment as done.Apr 30 2021, 1:22 AM

I agree though that "Dependency" is a bad name. I'm just struggling to find a name to encode this concept of BufferViewFlowAnalysis.

I am not convinced that DependencyAnalysis is the better name here. For dependencies, I think of read-after-write, etc.. This only computes the flow of buffers through control flow.

I agree. I can't think of a good name though for "Alias analysis but only for aliases not provably earlier in control flow"

Possible names:
BufferSubviewAliasAnalysis
BufferForwardAliasAnalysis
BufferFlowAnalysis
BufferReferenceAnalysis

I have to admit that I am not convinced by the general notion of a "dependency". In my opinion, BufferDependencyAnalysis::resolve(B) => {B, C, D}, does not give any guarantees about whether C and D actually depend on B in the sense of true "data dependencies". Instead, C and D can also be block arguments that are pure aliases without any read/write dependencies. Also, BufferAliasAnalysis::resolve(B) => {A, B, C, D} feels to me like A can be an alias of B, which is not actually the case, right? B has two aliases, namely C and D on the one hand. On the other hand, A has three aliases, namely B, C and D. Returning A as an alias of B could cause confusion in the future. What do you think about this?

Disclaimer:I'm not an expert on this topic, but the following was what I expected BufferAliasing to refer to and is what Wikipedia implies also. I don't think the current BufferAliasAnalysis (BufferDependencyAnalysis in this patch) should exist, if my view on aliases does turn out to be the common definition, but it was just hard or impossible to remove in the current Dealloc pass implementation.

This alias analysis should indeed not exist. It is broken in several different ways, and only works now because well.. luck mostly (i.e. it is hard coded for very specific types of input). This analysis should really be phased out in favor of the stuff in AliasAnalysis.h, but that is currently missing a few things (namely noalias tags for function arguments, which is one thing that the analysis in this file hard codes).

Aliasing is a symmetric property(https://en.wikipedia.org/wiki/Alias_analysis). This AliasAnalysis is fundamentally broken when it thinks that B aliasing A does not have to imply A aliasing B. We should not think of this in terms of "B aliases A" but in terms of "A and B are potential aliases of the same memory location" or "A and B are not guaranteed to be disjoint memory locations".

This is correct.

I have to admit that my comment regarding all aliases of A was a bit misleading :-( At the time of writing, I accidentally had the "flow"-property (required by the BufferDeallocation phase) in mind. My comment was meant to address potentially "inconsistent" results of two "alias analyses" (of course, aliasing is a symmetric property!) :-)

Regarding the name: I really like BufferViewFlowAnalysis, as it expresses the property of data flow between different Value nodes.

This alias analysis should indeed not exist. It is broken in several different ways, and only works now because well.. luck mostly

This also sounds a bit misleading. At the time of implementing, we had to introduce a specialized and domain-specific version that collects all aliases depending on the "flow" of a given value. This analysis was never intended to serve as a universal global program analysis. However, I agree that it might be beneficial to replace this analysis implementation by the ones available right now.

tpopp added a comment.May 6 2021, 6:48 AM

I have to admit that my comment regarding all aliases of A was a bit misleading :-( At the time of writing, I accidentally had the "flow"-property (required by the BufferDeallocation phase) in mind. My comment was meant to address potentially "inconsistent" results of two "alias analyses" (of course, aliasing is a symmetric property!) :-)

Regarding the name: I really like BufferViewFlowAnalysis, as it expresses the property of data flow between different Value nodes.

This alias analysis should indeed not exist. It is broken in several different ways, and only works now because well.. luck mostly

This also sounds a bit misleading. At the time of implementing, we had to introduce a specialized and domain-specific version that collects all aliases depending on the "flow" of a given value. This analysis was never intended to serve as a universal global program analysis. However, I agree that it might be beneficial to replace this analysis implementation by the ones available right now.

I've worked around this issue in my own code now, so what do you think about me just doing this rename? Then there will be no confusion between this pass and the new AliasAnalysis (and their definitions of aliasing). I think that confusion is good to avoid, and since I have a different solution for my own use case, I can avoid creating more confusion by creating another Analysis at this time.

herhut added a comment.May 7 2021, 2:13 AM

I've worked around this issue in my own code now, so what do you think about me just doing this rename? Then there will be no confusion between this pass and the new AliasAnalysis (and their definitions of aliasing). I think that confusion is good to avoid, and since I have a different solution for my own use case, I can avoid creating more confusion by creating another Analysis at this time.

+1 to renaming it to avoid confusion in the future.

I've worked around this issue in my own code now, so what do you think about me just doing this rename? Then there will be no confusion between this pass and the new AliasAnalysis (and their definitions of aliasing). I think that confusion is good to avoid, and since I have a different solution for my own use case, I can avoid creating more confusion by creating another Analysis at this time.

+1 to renaming it to avoid confusion in the future.

+1 to renaming :)

tpopp updated this revision to Diff 343669.May 7 2021, 7:10 AM

Change this patch to just a rename and expanded documentation.

This revision was not accepted when it landed; it landed in state Needs Review.May 7 2021, 7:13 AM
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.

Awesome work, thanks a lot :-)