llvm dev - Jul 2016 - [PM] I think that the new PM needs to learn about inter-analysis dependencies...

On Wed, Jul 13, 2016 at 1:40 AM Sean Silva <chisophugis at gmail.com>
wrote:
> On Wed, Jul 13, 2016 at 12:39 AM, Hal Finkel <hfinkel at anl.gov>
wrote:
>
>> Interesting. I'm not sure this is the right metric, however. There
are
>> lots of analyses that hold pointers to other analyses but don't
need to.
>> The analysis handle itself can be reacquired lazily if we care to do
so.
>>
>
> Are you thinking of instead holding a pointer to the analysis manager?
>
I'm really concerned with using this approach as the common case. It
triggers the run of the analyses at very strange points (mid-query of some
other analysis) and forces us to pay the analysis manager lookup overhead
on every query. For many analyses, this overhead is larger than the actual
query.

There may be cases where this is the only sane way to manage things, but
this should be the exception rather than the rule IMO.

>
>
>> What's truly problematic is holding pointers into another
analysis's data
>> structures. To be concrete, holding a pointer to ScalarEvolution is not
a
>> fundamental problem because we could make the analysis reacquire the
>> pointer at the start of every query. Holding SCEV* is the problem.
>>
>
> Looks like SCEV* at least is held only by LoopAccessInfo. (Looks like LAA
> holds Loop* too)
>
Note that Loop (and SCC) are somewhat special as they are IRUnitTs and
might as a consequence be more reasonable to hold on to and expect
definitive invalidation to occur. But I say "might". I think this will
be
case-by-case depending on how they're being used.

> New updated rendering at http://reviews.llvm.org/F2161258
> (DependenceAnalysis was missing some edges in my previous rendering and I
> didn't have and I've added LoopAccessAnalysis; I've updated
> http://reviews.llvm.org/P6603). Which other analyses vend data objects
> that others might hold pointers to?
>
SCEV, Loop, SCC, DomTreeNode, and Region leap immediately to mind. and 3 of
those are what would be IRUnitTs (Region being the third, and its weird and
likely won't be in the new PM ever).
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160713/c042b6b6/attachment.html>

On Wed, Jul 13, 2016 at 1:50 AM, Chandler Carruth <chandlerc at gmail.com>
wrote:
> On Wed, Jul 13, 2016 at 1:40 AM Sean Silva <chisophugis at gmail.com>
wrote:
>
>> On Wed, Jul 13, 2016 at 12:39 AM, Hal Finkel <hfinkel at anl.gov>
wrote:
>>
>>> Interesting. I'm not sure this is the right metric, however.
There are
>>> lots of analyses that hold pointers to other analyses but don't
need to.
>>> The analysis handle itself can be reacquired lazily if we care to
do so.
>>>
>>
>> Are you thinking of instead holding a pointer to the analysis manager?
>>
>
> I'm really concerned with using this approach as the common case. It
> triggers the run of the analyses at very strange points (mid-query of some
> other analysis) and forces us to pay the analysis manager lookup overhead
> on every query. For many analyses, this overhead is larger than the actual
> query.
>
Yeah, the overhead is my main concern. (also, this would be very difficult
to coexist with the old PM so at least in the immediate future isn't an
option)

>
> There may be cases where this is the only sane way to manage things, but
> this should be the exception rather than the rule IMO.
>
>
>>
>>
>>> What's truly problematic is holding pointers into another
analysis's
>>> data structures. To be concrete, holding a pointer to
ScalarEvolution is
>>> not a fundamental problem because we could make the analysis
reacquire the
>>> pointer at the start of every query. Holding SCEV* is the problem.
>>>
>>
>> Looks like SCEV* at least is held only by LoopAccessInfo. (Looks like
LAA
>> holds Loop* too)
>>
>
> Note that Loop (and SCC) are somewhat special as they are IRUnitTs and
> might as a consequence be more reasonable to hold on to and expect
> definitive invalidation to occur. But I say "might". I think this
will be
> case-by-case depending on how they're being used.
>
>
>> New updated rendering at http://reviews.llvm.org/F2161258
>> (DependenceAnalysis was missing some edges in my previous rendering and
I
>> didn't have and I've added LoopAccessAnalysis; I've updated
>> http://reviews.llvm.org/P6603). Which other analyses vend data objects
>> that others might hold pointers to?
>>
>
> SCEV, Loop, SCC, DomTreeNode, and Region leap immediately to mind. and 3
> of those are what would be IRUnitTs (Region being the third, and its weird
> and likely won't be in the new PM ever).
>
Looking around a bit:
Looks like DomTreeNode isn't held by anything currently.
Pointers to Loop are only held by LAA as far as I can tell.
CallGraphSCC objects are only used by GlobalsAA but only for a
"recalculate" step.
Region's data structures don't seem to be held by anything.

So it seems like LAA is the main offender in this regard.

-- Sean Silva
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160713/ba543b71/attachment.html>

> On Jul 13, 2016, at 2:02 AM, Sean Silva via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> 
> 
> On Wed, Jul 13, 2016 at 1:50 AM, Chandler Carruth <chandlerc at
gmail.com <mailto:chandlerc at gmail.com>> wrote:
> On Wed, Jul 13, 2016 at 1:40 AM Sean Silva <chisophugis at gmail.com
<mailto:chisophugis at gmail.com>> wrote:
> On Wed, Jul 13, 2016 at 12:39 AM, Hal Finkel <hfinkel at anl.gov
<mailto:hfinkel at anl.gov>> wrote:
> Interesting. I'm not sure this is the right metric, however. There are
lots of analyses that hold pointers to other analyses but don't need to. The
analysis handle itself can be reacquired lazily if we care to do so.
> 
> Are you thinking of instead holding a pointer to the analysis manager?
> 
> I'm really concerned with using this approach as the common case. It
triggers the run of the analyses at very strange points (mid-query of some other
analysis) and forces us to pay the analysis manager lookup overhead on every
query. For many analyses, this overhead is larger than the actual query.
> 
> Yeah, the overhead is my main concern. (also, this would be very difficult
to coexist with the old PM so at least in the immediate future isn't an
option)
>  
> 
> There may be cases where this is the only sane way to manage things, but
this should be the exception rather than the rule IMO.
>  
>  
> What's truly problematic is holding pointers into another
analysis's data structures. To be concrete, holding a pointer to
ScalarEvolution is not a fundamental problem because we could make the analysis
reacquire the pointer at the start of every query. Holding SCEV* is the problem.
> 
> Looks like SCEV* at least is held only by LoopAccessInfo. (Looks like LAA
holds Loop* too)
> 
> Note that Loop (and SCC) are somewhat special as they are IRUnitTs and
might as a consequence be more reasonable to hold on to and expect definitive
invalidation to occur. But I say "might". I think this will be
case-by-case depending on how they're being used.
>  
> New updated rendering at http://reviews.llvm.org/F2161258
<http://reviews.llvm.org/F2161258> (DependenceAnalysis was missing some
edges in my previous rendering and I didn't have and I've added
LoopAccessAnalysis; I've updated http://reviews.llvm.org/P6603
<http://reviews.llvm.org/P6603>). Which other analyses vend data objects
that others might hold pointers to?
> 
> SCEV, Loop, SCC, DomTreeNode, and Region leap immediately to mind. and 3 of
those are what would be IRUnitTs (Region being the third, and its weird and
likely won't be in the new PM ever).
> 
> Looking around a bit:
> Looks like DomTreeNode isn't held by anything currently.
> Pointers to Loop are only held by LAA as far as I can tell.
> CallGraphSCC objects are only used by GlobalsAA but only for a
"recalculate" step.
> Region's data structures don't seem to be held by anything.
> 
> So it seems like LAA is the main offender in this regard.
I think one main reason that analysis passes used to do this was to work around
limitations in the old PM.  Like LAA wasn’t a loop pass so as a function pass it
did lazy computation for loops.  Thus it had to hold on to the input analyses to
compute the per-loop analysis result.  I am hoping that this use case will go
away with the new PM.  There may be a way to refactor LoopAccessInfo to reflect
this, hopefully the old PM won’t stand in the way.

SCEV might pose another problem though.  Caching is per Value there, so that is
probably a genuine use case when we need to keep input analysis alive until the
main pass is alive.

A few more other thoughts on this topic.

Can we perhaps have a special reference type for passes to reference other
passes, something like a CallbackVH for passes and them somehow disallow holding
onto passes via a pointer?

There could also be a way to verify correctness.  We could force-invalidate all
passes that the pass does not declare to depend on, then hopefully bugs will
unconditionally present themselves independent of the pipeline.

Adam
> 
> -- Sean Silva
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160713/82eca97a/attachment.html>