AliasAnalysis refactoring for the new pass manager

Greetings all,

I’m working on refactoring the alias analysis layers to remove the usage of analysis groups and make the logic sharable between old and new pass managers, and I have a couple of questions below.

As background, the overall plan that I’ve discussed with Hal and a few others previously is as follows:

  • Create an AliasAnalysisManager which is provided by a normal analysis pass.
  • Use type erasure to register classes which conform to the core AliasAnalysis concept with the AliasAnalysisManager.
  • The concept will consist solely of the virtual methods currently on AliasAnalysis – all the helpers and such will just be directly provided by the manager layer.

This will make the AA infrastructure look much like the TTI infrastructure, but much simpler as the AA interface boundary is actually a reasonable and small concept.

As part of this, there won’t be any inheritance relationship between alias analyses, and so the nested enums currently in the AliasAnalysis base class aren’t a great way of describing the return types of these interfaces. I’d like to lift them out to be proper top-level enums that describe various aliasing and mod-ref information. In some ways, I think this is cleaner, especially for mod-ref information which might reasonably be used in interfaces that aren’t precisely that of AA. Any concerns so far?

Ok, provided you’re happy with this, I’d like to ask what names and naming conventions people like. Here is a straw-man:

enum class AliasKind {
NoAlias = 0,
MayAlias,
PartialAlias,
MustAlias
};

I find the “Alias” suffix redundant, but “No”, “Maybe”, “Partial”, and “Must” also seem awkward. Is there a better enum name than “AliasKind”? These aren’t just results, so I don’t like the current name.

Whatever convention we use, we should use a similar one for the ModRef stuff. ModRefBehavior there already seems to have good names if it were switched to an enum class outside of AA. ModRefResult I would probably make ModRefKind, but maybe ModRefInfo? We call the methods getModRefInfo…

Please suggest patterns that you like!

Hi Chandler,

I wasn't part of the discussion, but as part of other refactorings,
I'd like to make sure we're all following the same design goals.

So far, it seems that we're on the same page, but I have some comments inline.

- Create an AliasAnalysisManager which is provided by a normal analysis
pass.
- Use type erasure to register classes which conform to the core
AliasAnalysis concept with the AliasAnalysisManager.
- The concept will consist solely of the virtual methods currently on
AliasAnalysis -- all the helpers and such will just be directly provided by
the manager layer.

I believe this is the design we're going for other such manager
classes, right? Sounds good to me.

As part of this, there won't be any inheritance relationship between alias
analyses, and so the nested enums currently in the AliasAnalysis base class
aren't a great way of describing the return types of these interfaces. I'd
like to lift them out to be proper top-level enums that describe various
aliasing and mod-ref information.

I'm all for it. I think we need to keep the interface public and
simple, and the implementation private and as complicated as it has to
be. Also, this doesn't mean we're exposing more information, just that
we're exposing the right things.

I find the "Alias" suffix redundant, but "No", "Maybe", "Partial", and
"Must" also seem awkward.

I kind of like it, even if it's redundant. Though, I wouldn't use
"MaybeAlias", but "MayAlias", but that's as much as I'd change.

Is there a better enum name than "AliasKind"?

Well, we're using this pattern everywhere, I think we should just stick to it.

Having said that, I'm not in favour of bike shedding, so I'm fine with
whatever people are more comfortable with.

cheers,
--renato

Greetings all,

I'm working on refactoring the alias analysis layers to remove the usage
of analysis groups and make the logic sharable between old and new pass
managers, and I have a couple of questions below.

As background, the overall plan that I've discussed with Hal and a few
others previously is as follows:
- Create an AliasAnalysisManager which is provided by a normal analysis
pass.
- Use type erasure to register classes which conform to the core
AliasAnalysis concept with the AliasAnalysisManager.
- The concept will consist solely of the virtual methods currently on
AliasAnalysis -- all the helpers and such will just be directly provided by
the manager layer.

This will make the AA infrastructure look much like the TTI
infrastructure, but much simpler as the AA interface boundary is actually a
reasonable and small concept.

As part of this, there won't be any inheritance relationship between alias
analyses, and so the nested enums currently in the AliasAnalysis base class
aren't a great way of describing the return types of these interfaces. I'd
like to lift them out to be proper top-level enums that describe various
aliasing and mod-ref information. In some ways, I think this is cleaner,
especially for mod-ref information which might reasonably be used in
interfaces that aren't precisely that of AA. Any concerns so far?

Ok, provided you're happy with this, I'd like to ask what names and naming
conventions people like. Here is a straw-man:

enum class AliasKind {
  NoAlias = 0,
  MayAlias,
  PartialAlias,
  MustAlias
};

I find the "Alias" suffix redundant, but "No", "Maybe", "Partial", and
"Must" also seem awkward. Is there a better enum name than "AliasKind"?
These aren't *just* results, so I don't like the current name.

AliasRelationship? None, May/PossiblyAliased/Unknown, Aliased,
PartiallyAliased?

(tense could use some tweaking and I suppose this still has the suffix
problem in all except the "None" case... )

Greetings all,

I'm working on refactoring the alias analysis layers to remove the usage of analysis groups and make the logic sharable between old and new pass managers, and I have a couple of questions below.

As background, the overall plan that I've discussed with Hal and a few others previously is as follows:
- Create an AliasAnalysisManager which is provided by a normal analysis pass.
- Use type erasure to register classes which conform to the core AliasAnalysis concept with the AliasAnalysisManager.
- The concept will consist solely of the virtual methods currently on AliasAnalysis -- all the helpers and such will just be directly provided by the manager layer.

This will make the AA infrastructure look much like the TTI infrastructure, but much simpler as the AA interface boundary is actually a reasonable and small concept.

As part of this, there won't be any inheritance relationship between alias analyses, and so the nested enums currently in the AliasAnalysis base class aren't a great way of describing the return types of these interfaces. I'd like to lift them out to be proper top-level enums that describe various aliasing and mod-ref information. In some ways, I think this is cleaner, especially for mod-ref information which might reasonably be used in interfaces that aren't precisely that of AA. Any concerns so far?

Ok, provided you're happy with this, I'd like to ask what names and naming conventions people like. Here is a straw-man:

enum class AliasKind {
  NoAlias = 0,
  MayAlias,
  PartialAlias,
  MustAlias
};

I find the "Alias" suffix redundant, but "No", "Maybe", "Partial", and "Must" also seem awkward. Is there a better enum name than "AliasKind"? These aren't *just* results, so I don't like the current name.

AliasRelationship? None, May/PossiblyAliased/Unknown, Aliased, PartiallyAliased?

(tense could use some tweaking and I suppose this still has the suffix problem in all except the "None" case... )

I like this colour:

    enum class AliasKind /* or AliasCategory? */ {
      Null,
      Unknown,
      Partial,
      Complete
    };

I would mildly prefer that the current (or similar) element names are kept. A lot of the literature talks about may alias and must alias relationships, so I’d prefer to stick with consistent and known terminology. I’m specificly worried about the readabity of code in places like MemoryDependenceAnalysis and GVN for newcomers to the community. AliasKind::Must is less clear to me than AlaisKind::MustAlias. The second is admittedly more verbose, but that’s not always a bad thing.

So, the only non-bikeshed-color argument I have (which is also referenced by Philip, but i couldn’t reply to both) suggests we really want NoAlias,
MayAlias, and MustAlias, because these are terms of art in the literature (confirmed by DannyB who is a reasonable expert in alias analysis literature). I’m inclined to keep these names as a consequence. The natural extension is PartialAlias.

That leaves the question of the enumeration name. I think “AliasResult” is my new found favorite. Danny gave me a reason: these are really results of a particular query, not just abstract kinds of aliasing… And its shorter than AliasRelationship. =]

Thoughts?

I like this colour:

    enum class AliasKind /* or AliasCategory? */ {
      Null,
      Unknown,
      Partial,
      Complete
    };

So, the only non-bikeshed-color argument I have (which is also referenced by Philip, but i couldn't reply to both) suggests we *really* want NoAlias,
MayAlias, and MustAlias, because these are terms of art in the literature (confirmed by DannyB who is a reasonable expert in alias analysis literature). I'm inclined to keep these names as a consequence. The natural extension is PartialAlias.

Sad that "alias" is sometimes a noun and sometimes a verb, but if
it's in the literature, then I guess that's that.

Might be better to have "NoAlias" be the only one that treats "alias"
as a noun though. PartiallyAlias? PartlyAlias? (But since it's
inconsistent anyway, then PartialAlias isn't all bad.)

That leaves the question of the enumeration name. I think "AliasResult" is my new found favorite. Danny gave me a reason: these are really results of a particular query, not just abstract kinds of aliasing... And its shorter than AliasRelationship. =]

Thoughts?

I don't really see how it's better than AliasKind, but I don't see
anything wrong with it either.

Sad that "alias" is sometimes a noun and sometimes a verb, but if
it's in the literature, then I guess that's that.

Yes, you will see both "a may-alias b" and "a is a may-alias of b", etc..

So, after looking at doing this, I’m left with more questions and no good answers. C++ has truly failed me today.

This enum is currently designed (and even documented as being designed) to allow conversion-to-bool to detect whether any alias is possible (that is, only no-alias becomes false). This makes it really easy to write the overwhelming majority of test: if (“do things alias”) { bail… }.

It turns out that it is impossible to do this with C++11 "enum class"es. Despite the fact that they seemed specifically designed to serve these kinds of use cases. They are, IMO, completely useless at this point.

It also turns out that it is nearly impossible to define a normal class and a collection of constants that behave in the way folks generally want a strongly typed enum to behave. It requires class templates, typedefs, constexpr, and like 3x the boilerplate code. Its nuts.[1]

So the options I see are:

  1. Commit the significant body of code necessary to emulate proper enum classes in C++, and document it as a boilerplate pattern. I might be able to shrink it with some clever macro tricks, but it looks pretty doubtful honestly.

  2. Use “enum class AliasResult { NoAlias, … }” and update everywhere to say explicitly “… != AliasResult::NoAlias”.

  3. Use “enum AliasResult { NoAlias = 0, … }” and everything Just Works but we pollute the llvm namespace with “NoAlias” and friends.

  4. Use “enum AliasResult { AR_NoAlias = 0, …}” to get the effect of #2 with some minimal name collision prevention.

Thoughts?

-Chandler

[1] Here is the completely untested sketch of what seems required: https://ghostbin.com/paste/2bso6

So, after looking at *doing* this, I'm left with more questions and no
good answers. C++ has truly failed me today.

This enum is currently designed (and even *documented* as being designed)
to allow conversion-to-bool to detect whether any alias is possible (that
is, only no-alias becomes false). This makes it *really* easy to write the
overwhelming majority of test: if ("do things alias") { bail... }.

It turns out that it is impossible to do this with C++11 "enum class"es.
Despite the fact that they seemed specifically designed to serve these
kinds of use cases. They are, IMO, completely useless at this point.

It also turns out that it is *nearly* impossible to define a normal class
and a collection of constants that behave in the way folks generally want a
strongly typed enum to behave. It requires class templates, typedefs,
constexpr, and like 3x the boilerplate code. Its nuts.[1]

So the options I see are:

1) Commit the significant body of code necessary to emulate proper enum
classes in C++, and document it as a boilerplate pattern. I might be able
to shrink it with some clever macro tricks, but it looks pretty doubtful
honestly.

2) Use "enum class AliasResult { NoAlias, ... }" and update everywhere to
say explicitly "... != AliasResult::NoAlias".

3) Use "enum AliasResult { NoAlias = 0, ... }" and everything Just Works
but we pollute the llvm namespace with "NoAlias" and friends.

4) Use "enum AliasResult { AR_NoAlias = 0, ...}" to get the effect of #2
with some minimal name collision prevention.

Or 4.1) make it explicit " ... != AR_NoAlias"

David

How is this different from 2? You always have to write ‘AliasResult::’ before ‘NoAlias’.

So, after looking at *doing* this, I'm left with more questions and no
good answers. C++ has truly failed me today.

This enum is currently designed (and even *documented* as being designed)
to allow conversion-to-bool to detect whether any alias is possible (that
is, only no-alias becomes false). This makes it *really* easy to write the
overwhelming majority of test: if ("do things alias") { bail... }.

It turns out that it is impossible to do this with C++11 "enum class"es.
Despite the fact that they seemed specifically designed to serve these
kinds of use cases. They are, IMO, completely useless at this point.

It also turns out that it is *nearly* impossible to define a normal class
and a collection of constants that behave in the way folks generally want a
strongly typed enum to behave. It requires class templates, typedefs,
constexpr, and like 3x the boilerplate code. Its nuts.[1]

So the options I see are:

1) Commit the significant body of code necessary to emulate proper enum
classes in C++, and document it as a boilerplate pattern. I might be able
to shrink it with some clever macro tricks, but it looks pretty doubtful
honestly.

2) Use "enum class AliasResult { NoAlias, ... }" and update everywhere to
say explicitly "... != AliasResult::NoAlias".

3) Use "enum AliasResult { NoAlias = 0, ... }" and everything Just Works
but we pollute the llvm namespace with "NoAlias" and friends.

+1 for 3)

-- Sean Silva

Dear Chandler,

A few questions:

1) Are you removing the analysis groups functionality? If so, will the new way to get similar functionality be to write a Manager pass like AliasAnalysisManager?

2) Will AliasAnalysis passes still chain as they do today?

3) Will your refactoring fix the "problem" (or maybe it's a feature?) of having to manually schedule AliasAnalysis passes because pass invalidation always causes the default AliasAnalysis pass from the group to be scheduled by the PassManager?

We have some old code that, if we resurrect it, will need to be rewritten if Analysis Groups are removed. Removing/Replacing Analysis Groups is fine, but I'd like to know in advance if they disappear.

Regards,

John Criswell

FYI, I’ve implemented the plain ol’ enum approach in http://reviews.llvm.org/D10495 – so far, the alternatives haven’t been compelling to me.

Dear Chandler,

A few questions:

  1. Are you removing the analysis groups functionality? If so, will the new way to get similar functionality be to write a Manager pass like AliasAnalysisManager?

Yes, that is the general plan.

The analysis group infrastructure was used exceedingly rarely, and each of the uses had a subtly different desired interaction between the extension points it managed.

Explicitly writing manager passes allows the domain and use cases to precisely dictate how extensions in that domain interact.

Naturally, if we end up producing repeated patterns here, we should extract common helper functionality so that producing these manager passes isn’t unnecessarily repetitive.

  1. Will AliasAnalysis passes still chain as they do today?

There will definitely be a delegation path.

I’ve not actually implemented it yet, so its a bit premature, but my general plan was to try to clean up and formalize several aspects such as the concept of TBAA only refining MayAlias pointers, leaving MustAlias pointers alone.

  1. Will your refactoring fix the “problem” (or maybe it’s a feature?) of having to manually schedule AliasAnalysis passes because pass invalidation always causes the default AliasAnalysis pass from the group to be scheduled by the PassManager?

Yes and no.

It won’t be a problem because there won’t be any “default” scheduling. The entire manager will get invalidation events and get to handle them as it sees fit.

But it will still be a complication as the manager will have to handle invalidation in some reasonable way for a stateful AA implementation. I’m going to try to wire everything up such that a stateful AA would Just Work, but there may be rough edges until someone really exercises the infrastructure. If I don’t have time to dig into this fully, I’m hopeful that George or whomever next works on CFL-AA will push it forward because CFL in particular should benefit heavily from being able to have some state but to also have controlled invalidation of the state.

We have some old code that, if we resurrect it, will need to be rewritten if Analysis Groups are removed. Removing/Replacing Analysis Groups is fine, but I’d like to know in advance if they disappear.

I would plan for them to disappear, and soon.

The entire concept is extremely poorly founded. Look at the this-pointer-adjustment hacks. =/

Long term, I expect almost all users will look like TargetTransformInfo (but hopefully with a much smaller interface!) and be able to follow its pattern to produce a simple analysis which is constructed with the type-erased implementation desired.

-Chandler

Sorry to not have replied to these high level comments earlier…

Hi Chandler,

I wasn’t part of the discussion, but as part of other refactorings,
I’d like to make sure we’re all following the same design goals.

Pretty sure that all of this is just the same pattern as already discussed many times.

So far, it seems that we’re on the same page, but I have some comments inline.

  • Create an AliasAnalysisManager which is provided by a normal analysis
    pass.
  • Use type erasure to register classes which conform to the core
    AliasAnalysis concept with the AliasAnalysisManager.
  • The concept will consist solely of the virtual methods currently on
    AliasAnalysis – all the helpers and such will just be directly provided by
    the manager layer.

I believe this is the design we’re going for other such manager
classes, right? Sounds good to me.

Yep. Nothing new here. If anything, this’ll be a much better example as the interface isn’t so huge.

As part of this, there won’t be any inheritance relationship between alias
analyses, and so the nested enums currently in the AliasAnalysis base class
aren’t a great way of describing the return types of these interfaces. I’d
like to lift them out to be proper top-level enums that describe various
aliasing and mod-ref information.

I’m all for it. I think we need to keep the interface public and
simple, and the implementation private and as complicated as it has to
be. Also, this doesn’t mean we’re exposing more information, just that
we’re exposing the right things.

Yep.