llvm dev - Jun 2015 - [LLVMdev] 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!
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150613/d7e8f2ce/attachment.html>

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.


On 13 June 2015 at 09:52, Chandler Carruth <chandlerc at gmail.com>
wrote:
> - 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

On Sat, Jun 13, 2015 at 12:52 AM, Chandler Carruth <chandlerc at
gmail.com>
wrote:
> 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... )

>
> 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!
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150613/f413ed5d/attachment.html>

> On 2015-Jun-13, at 09:12, David Blaikie <dblaikie at gmail.com>
wrote:
> 
> 
> 
> On Sat, Jun 13, 2015 at 12:52 AM, Chandler Carruth <chandlerc at
gmail.com> wrote:
> 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
    };

> 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!
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On 06/13/2015 12:52 AM, Chandler Carruth wrote:
> 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.
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.

>
> 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!
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150615/c97c68e4/attachment.html>

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

On 6/13/15 2:52 AM, Chandler Carruth wrote:
> 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!
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-- 
John Criswell
Assistant Professor
Department of Computer Science, University of Rochester
http://www.cs.rochester.edu/u/criswell

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150616/386fbd5f/attachment.html>

On Tue, Jun 16, 2015 at 6:30 AM John Criswell <jtcriswel at gmail.com>
wrote:
>  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.

> 2) 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.

> 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?
>
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150617/d3ea35aa/attachment.html>

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

On Sat, Jun 13, 2015 at 3:00 AM Renato Golin <renato.golin at linaro.org>
wrote:
> 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.
>
>
> On 13 June 2015 at 09:52, Chandler Carruth <chandlerc at gmail.com>
wrote:
> > - 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150617/d549b73a/attachment.html>