This is an archive of the discontinued LLVM Phabricator instance.

[mlir] Add initial support for an alias analysis framework in MLIR
ClosedPublic

Authored by rriddle on Nov 30 2020, 12:53 PM.

Details

Summary

This revision adds a new AliasAnalysis class that represents the main alias analysis interface in MLIR. The purpose of this class is not to hold the aliasing logic itself, but to provide an interface into various different alias analysis implementations. As it evolves this should allow for users to plug in specialized alias analysis implementations for their own needs, and have them immediately usable by other analyses and transformations.

This revision also adds an initial simple generic alias, LocalAliasAnalysis, that provides support for performing stateless local alias queries between values. This class is similar in scope to LLVM's BasicAA.

Diff Detail

Event Timeline

rriddle created this revision.Nov 30 2020, 12:53 PM
rriddle requested review of this revision.Nov 30 2020, 12:53 PM

Do we have a Discourse thread for this already?

Thanks, River, this looks useful! I have a couple of comments.

mlir/include/mlir/Analysis/AliasAnalysis.h
38

Does this also guarantee that there exists some non-overlapping portion? Or can this be used as "could not prove precise aliasing, but there is definitely some aliasing"?

132

it should also be move-constructible

mlir/lib/Analysis/AliasAnalysis.cpp
36

Do we expect other analyses to register themselves here, or do we rather expect the user of AliasAnalysis to add what they want?

42

If PartialAlias cases are a subset of MustAlias cases (see above), we may be returning too early here: an insufficiently precise analyses that happens to be first in the list returns PartialAlias but some other analysis further down in the list could return MustAlias.

44

Do we want a check, under NDEBUG that analyses don't contradict each other (e.g. we don't have NoAlias and MustAlias simultaneously)

mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp
1

Nit: //=== -> //===-

27

Nit: mention that the behavior if region is null follows the convention of RegionBranchOpInterface, i.e. the successor is assumed to be the parent op.

36

Nit: this deserves a doc

38

Can we just sink the definition into the lambda? This does not seem used anywhere else.

82

Shouldn't this also rely on RegionBranchOpInterface? There may be terminator that are not exactly return like, but for which we have the same sort of information

183

Nit: could we have a named constexpr for this and put it at the top of the file?

214

Nit: automatically

239–240

Should we then conservatively say constants may alias without further checking the values?

ftynse accepted this revision.Dec 3 2020, 11:08 AM
ftynse added inline comments.
mlir/lib/Analysis/AliasAnalysis.cpp
1

This file may require CMakeLists update

This revision is now accepted and ready to land.Dec 3 2020, 11:08 AM
silvas added a subscriber: silvas.Dec 3 2020, 12:15 PM
silvas added inline comments.
mlir/test/Analysis/test-alias-analysis.mlir
22

drive-by: not obvious to me why a freshly allocated value MayAlias the function argument. Surely even LocalAliasAnalysis can mark this NoAlias, especially since it already does so for the alloca case.

rriddle added inline comments.Dec 3 2020, 12:16 PM
mlir/test/Analysis/test-alias-analysis.mlir
22

This requires doing a proper escape analysis, which is a TODO in the code as an improvement. Will add a note here as well.

Very cool, thanks River!
I have a bunch of use cases for this :)

rriddle updated this revision to Diff 309709.Dec 4 2020, 6:47 PM
rriddle marked 15 inline comments as done.

Resolve comments and rebase

rriddle added inline comments.Dec 4 2020, 6:48 PM
mlir/include/mlir/Analysis/AliasAnalysis.h
38

It does not guarantee that there is a non-overlapping portion, it simply guarantees that there is an overlap of some kind. It's not as strong as Must which is I know for a fact they completely alias, but is stronger than MayAlias which is effectively I don't know. When chaining together alias analysis results it is useful because MayAlias is not a strong result when it comes to merging, it will take whatever the other result is. PartialAlias establishes a precedent that there is some overlapping aliasing there, but it couldn't prove any more than that.

mlir/lib/Analysis/AliasAnalysis.cpp
1

I forget about that more often than I'd like to admit.

36

This is something that needs a bit more fleshing out(and some work in a couple of other areas), but the way that I see it now there are two scenarios that additional analysis implementations would be added:

  • DialectInterface

Allow dialects to provide alias analyses that are specific to their types/related types. Given that we span many different domains, having dialects be able to plug in their own analysis implementations seems useful.

  • External users via the PassPipeline(similar to how LLVM AAManager works)

Kind of along the same lines as above, but it is also useful to allow for external users that are building a pipeline to plugin in their own analyses that they are writing. This is a useful invariant IMO as it provides another mechanism to provide this information that may be toolchain specific, as well as simplifying the ability to test new implementations without changing upstream MLIR.

The API for each of these needs fleshed out, but I've attempted to write this initial skeleton in such a way that it will be easy to build these use cases in the future. For now, we can hardcode the specific default implementations here but in the future I imagine what we have here to simply be a default configuration.

44

The nature of alias analyses is that they may conflict. An easy example is type based alias analysis(TBAA). TBAA puts types into different alias classes, which determines what things that can alias with. For C++, float* and int* would have different classes. If we end up in a situation like:

int foo(int *ptr) {
  *ptr = 8;
  float *fptr = reinterpret_cast<float *>(ptr);
  *fptr = 100;
  return *ptr;
}

fptr and ptr must alias as per the local alias analysis here, but TBAA would say that they don't alias each other. So we can end up with NoAlias and MustAlias. In practice that's technically UB in C++, but for the sake of this analysis we just pick the first resolved result and move on. It gives determinism and allow for us to order the analyses in a way that the most conservative ones get picked up first.

https://godbolt.org/z/jq9xEq

mlir/lib/Analysis/AliasAnalysis/LocalAliasAnalysis.cpp
82

For the situations where we don't have a proper trait, most likely yeah. RegionBranchOpInterface doesn't support that at the moment, and we don't have any use cases yet AFAIK. So I'd leave that to a separate change given that it would be usable by most other users of RegionBranchOpInterface.

239–240

Yeah, switched to may alias for now. We'll need to refine this for things like globals(via SymbolRefAttr) though, so also rephrased the TODO.

chhe added a subscriber: chhe.Dec 21 2020, 11:07 AM
This revision was landed with ongoing or failed builds.Feb 9 2021, 2:26 PM
This revision was automatically updated to reflect the committed changes.