<html><head></head><body><div style="color:#000; background-color:#fff; font-family:HelveticaNeue-Light, Helvetica Neue Light, Helvetica Neue, Helvetica, Arial, Lucida Grande, sans-serif;font-size:13px"><div id="yui_3_16_0_ym19_1_1470325874990_360570" dir="ltr">When we talk about stale information, what does it mean exactly? This goes back to the point about how what guarantees are made about the analysis information, and when it is invalidated. If some information is wrong for the current IR (during a transform), but still fully correct with regards to the IR that was given to the analysis before the transform, this is information that some transforms actually need. The other case is if the analysis info directly points to the IR that is being modified, and some information is wrong for both the old and current IR, which could cause the transform to fail. What should the policy be for analyses, and how would someone writing a transform know when information becomes stale and how?</div><div id="yui_3_16_0_ym19_1_1470325874990_360570" dir="ltr"><br></div><div id="yui_3_16_0_ym19_1_1470325874990_360570" dir="ltr">- Jan </div> <div class="qtdSeparateBR"><br><br></div><div class="yahoo_quoted" style="display: block;"> <div style="font-family: HelveticaNeue-Light, Helvetica Neue Light, Helvetica Neue, Helvetica, Arial, Lucida Grande, sans-serif; font-size: 13px;"> <div style="font-family: HelveticaNeue, Helvetica Neue, Helvetica, Arial, Lucida Grande, sans-serif; font-size: 16px;"> <div dir="ltr"><font size="2" face="Arial"> On Monday, August 8, 2016 1:42 PM, Sean Silva via llvm-dev <llvm-dev@lists.llvm.org> wrote:<br></font></div> <br><br> <div class="y_msg_container"><div id="yiv5022725477"><div dir="ltr"><br><div class="yiv5022725477gmail_extra"><br><div class="yiv5022725477gmail_quote">On Sun, Aug 7, 2016 at 4:55 PM, Philip Reames <span dir="ltr"><<a rel="nofollow" ymailto="mailto:listmail@philipreames.com" target="_blank" href="mailto:listmail@philipreames.com">listmail@philipreames.com</a>></span> wrote:<br><blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div>
<div>Skimming the thread, this post is the
clearest path forward I've seen. Minor comments inline, but I
generally like this framing. <br><span>
<br>
On 07/14/2016 08:04 PM, Chandler Carruth via llvm-dev wrote:<br>
</span></div><span>
<blockquote type="cite">
<div dir="ltr">We need better terminology to talk about this. I
propose:
<div><br>
</div>
<div>analysis-dependencies: analysis A uses result of analysis B
when *running* an analysis and not used by the result</div>
<div>query-dependencies: result of analysis A uses result of
analysis B when evaluating a query</div>
<div>data-structure-depnedencies: result of analysis A uses data
structures from the result of analysis B inside its own data
structures</div>
<div><br>
</div>
<div>I think these are much more precise than "hard" or "soft"
and expose more facets.</div>
<div><br>
</div>
<div>For analysis-depnedencies, I continue to think they work
correctly. If a transformation claims it preserves an
analysis, it must actually know this to be true. I don't see
any actual problems here in practice today, and this isn't
actually something changed in the new PM.</div>
<div><br>
</div>
<div>For data-structure-dependencies, the investigation done by
Sean seems to clearly show these to be rare, and I think
having their invalidate methods be overridden to test that
*all* of the data structures they depend on are preserved is
the correct approach.</div>
</div>
</blockquote></span>
This may end up being too error prone. That seems to be Sean's
concern down thread. I am also worried about that, but assuming the
number of such occurrences are low, it seems reasonable to start
with this approach and revisit if needed. <br></div></blockquote><div><br></div><div>Chandler's suggestion here doesn't actually avoid the issue.</div><div><br></div><div>A simple proof that this approach cannot work is that the issue at hand is one of insufficient invalidation. The `invalidate` callback can only prevent invalidation, so Chandler's suggestion of overriding it can only prevent invalidation -- it cannot trigger additional invalidation and therefore cannot solve a problem of insufficient invalidation.</div><div><br></div><div>-- Sean Silva</div><div> </div><blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;"><div><span>
<blockquote type="cite">
<div dir="ltr">
<div><br>
</div>
<div>The primary issue seems to be with query-dependencies.
These in turn break down into two categories:</div>
<div><br>
</div>
<div>1) query-dependencies on "immutable" analysis results.
These are results that we *never* expect to be invalidated and
we just want easy access to. TargetLibraryInfo is the classic
example here.</div>
<div><br>
</div>
<div>2) query-dependencies on normal analysis results.
DominatorTree and and AAResults are the primary examples here.</div>
<div><br>
</div>
<div>I would like to have a simple way to handle #1 by ensuring
invalidation doesn't occur. I think this already works, but
I'm interested if there is actually an issue here.</div>
<div><br>
</div>
<div>We *could* handle #2 much like data-structure-dependencies,
but I hear Hal and others that this would become burdensome.
However, my preference would be to instead handle #2 by making
result APIs accept direct handles to the analysis results they
rely on.</div>
<div><br>
</div>
<div>The reason for preferring this approach is because I think
it makes the relationship between these things much more clear
to users of the analyses.</div>
</div>
</blockquote></span>
+1 to this. Having the query dependencies explicit at the call site
would generally make the code much easier to understand and thus
much more likely to be correct. I recently ran across an issue in
LVI under the old pass manager that looks highly suspicious, but
because the code is quite complex (putting it mildly), I wasn't sure
whether it was correct or not. Having the additional analyzes
passed in explicitly through the query would make many of these
cases substantially easier to audit.
<blockquote type="cite"><div><div>
<div dir="ltr">
<div><br>
</div>
<div>I think the most annoying of these to handle are
aggregation-style analyses results like AAResults. There, I
think it might make more sense to handle them along the lines
of data-structure-dependencies. I don't think we have so many
of those that this would be a significant burden IMO.</div>
</div>
<br>
<div class="yiv5022725477gmail_quote">
<div dir="ltr">On Thu, Jul 14, 2016 at 7:48 PM Sean Silva <<a rel="nofollow" ymailto="mailto:chisophugis@gmail.com" target="_blank" href="mailto:chisophugis@gmail.com">chisophugis@gmail.com</a>>
wrote:<br>
</div>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div dir="ltr">
<div class="yiv5022725477gmail_extra">
<div class="yiv5022725477gmail_quote">On Thu, Jul 14, 2016 at 7:21 PM,
Hal Finkel <span dir="ltr"><<a rel="nofollow" ymailto="mailto:hfinkel@anl.gov" target="_blank" href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>></span>
wrote:<br>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div>
<div style="font-family:arial, helvetica, sans-serif;font-size:10pt;color:rgb(0,0,0);">Hi
Sean,<br>
<br>
Thanks for writing all of this up. I'll go back to
my previous position: we need a general dependency
graph built as the analysis cache is used. It
should have the following properties:<br>
<br>
1. When we call getResult or getCachedResult on
an analysis manager, we record a dependency of the
current pass on the returned result.<br>
2. This dependency needs to be stored such that
it can be used to invalidate the current result
when the returned result is invalidates and so
that the dependency can be deleted when the
current result is invalidated.<br>
<br>
As I understand the problem, this is a
fully-general solution. I see no reason not to
have a fully-general solution.<br>
</div>
</div>
</blockquote>
<div><br>
</div>
</div>
</div>
</div>
<div dir="ltr">
<div class="yiv5022725477gmail_extra">
<div class="yiv5022725477gmail_quote">
<div>Yeah, the mechanics of maintaining this fully
general mapping are straightforward in the abstract
(once we have a single analysis manager for all
IRUnitT's). Essentially, the analysis manager
maintains a stack of (<span style="font-size:12.8px;">Analysis,
IRUnit)</span> that it is currently computing and
pushes/pops the stack as it (re-)enters/exits
get{,Cached}Result. If the stack is not empty (suppose
top of stack is `(AnalysisFoo, IRUnitBar)`), then when
we go to push `(AnalysisBaz, IRUnitQux)` we record a
dependency that the result cached on key
`(AnalysisBaz, IRUnitQux)` must be invalidated if the
result cached on key `(AnalysisFoo, IRUnitBar)` is
invalidated.</div>
<div><br>
</div>
<div><span style="font-size:12.8px;">The difficult part
is what guarantees we provide about things being
stale or not and how we invalidate when IRUnit's are
deleted or created.</span></div>
<div><span style="font-size:12.8px;">For example, suppose
a function pass DCE's a call which causes an SCC Foo
of 3 functions to no longer be an SCC. When/how do
analyses cached on Foo get invalidated? And is it
valid to query them? One of the expected use cases
(I'm told) for CGSCC passes is to propagate
function-attribute like things, so these are being
potentially queried by that same function pass.</span></div>
</div>
</div>
</div>
<div dir="ltr">
<div class="yiv5022725477gmail_extra">
<div class="yiv5022725477gmail_quote">
<div><br>
</div>
<div>-- Sean Silva</div>
</div>
</div>
</div>
<div dir="ltr">
<div class="yiv5022725477gmail_extra">
<div class="yiv5022725477gmail_quote">
<div> </div>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div>
<div style="font-family:arial, helvetica, sans-serif;font-size:10pt;color:rgb(0,0,0);"><br>
Thanks again,<br>
Hal<br>
<br>
<hr>
<blockquote style="border-left-width:2px;border-left-style:solid;border-left-color:rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica, Arial, sans-serif;font-size:12pt;"><span><b>From:
</b>"Sean Silva" <<a rel="nofollow" ymailto="mailto:chisophugis@gmail.com" target="_blank" href="mailto:chisophugis@gmail.com">chisophugis@gmail.com</a>><br>
<b>To: </b>"Chandler Carruth" <<a rel="nofollow" ymailto="mailto:chandlerc@gmail.com" target="_blank" href="mailto:chandlerc@gmail.com">chandlerc@gmail.com</a>><br>
<b>Cc: </b>"Xinliang David Li" <<a rel="nofollow" ymailto="mailto:davidxl@google.com" target="_blank" href="mailto:davidxl@google.com">davidxl@google.com</a>>,
"llvm-dev" <<a rel="nofollow" ymailto="mailto:llvm-dev@lists.llvm.org" target="_blank" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>>,
"Davide Italiano" <<a rel="nofollow" ymailto="mailto:dccitaliano@gmail.com" target="_blank" href="mailto:dccitaliano@gmail.com">dccitaliano@gmail.com</a>>,
"Tim Amini Golling" <<a rel="nofollow" ymailto="mailto:mehdi.amini@apple.com" target="_blank" href="mailto:mehdi.amini@apple.com">mehdi.amini@apple.com</a>>,
"Hal Finkel" <<a rel="nofollow" ymailto="mailto:hfinkel@anl.gov" target="_blank" href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>>,
"Sanjoy Das" <<a rel="nofollow" ymailto="mailto:sanjoy@playingwithpointers.com" target="_blank" href="mailto:sanjoy@playingwithpointers.com">sanjoy@playingwithpointers.co m</a>>,
"Pete Cooper" <<a rel="nofollow" ymailto="mailto:peter_cooper@apple.com" target="_blank" href="mailto:peter_cooper@apple.com">peter_cooper@apple.com</a>><br>
</span><b>Sent: </b>Thursday, July 14, 2016
4:11:58 AM<span><br>
<b>Subject: </b>Re: [PM] I think that the new
PM needs to learn about inter-analysis
dependencies...<br>
<br>
</span>
<div dir="ltr"><br>
<div class="yiv5022725477gmail_extra"><br>
<div>
<div>
<div class="yiv5022725477gmail_quote">On Thu, Jul 14,
2016 at 12:51 AM, Sean Silva <span dir="ltr"><<a rel="nofollow" ymailto="mailto:chisophugis@gmail.com" target="_blank" href="mailto:chisophugis@gmail.com">chisophugis@gmail.com</a>></span>
wrote:<br>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div dir="ltr"><br>
<div class="yiv5022725477gmail_extra"><br>
<div class="yiv5022725477gmail_quote">
<div>
<div>On Wed, Jul 13, 2016 at
1:48 AM, Sean Silva <span dir="ltr"><<a rel="nofollow" ymailto="mailto:chisophugis@gmail.com" target="_blank" href="mailto:chisophugis@gmail.com">chisophugis@gmail.com</a>></span>
wrote:<br>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div dir="ltr"><br>
<div class="yiv5022725477gmail_extra"><br>
<div class="yiv5022725477gmail_quote">
<div>
<div>On Wed, Jul
13, 2016 at
12:34 AM,
Chandler
Carruth <span dir="ltr"><<a rel="nofollow" ymailto="mailto:chandlerc@gmail.com" target="_blank" href="mailto:chandlerc@gmail.com">chandlerc@gmail.com</a>></span>
wrote:<br>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div dir="ltr">
<div class="yiv5022725477gmail_quote">
<div>
<div>
<div dir="ltr">On
Wed, Jul 13,
2016 at 12:25
AM Sean Silva
<<a rel="nofollow" ymailto="mailto:chisophugis@gmail.com" target="_blank" href="mailto:chisophugis@gmail.com">chisophugis@gmail.com</a>>
wrote:<br>
</div>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div dir="ltr">
<div class="yiv5022725477gmail_extra">
<div class="yiv5022725477gmail_quote">On
Tue, Jul 12,
2016 at 11:39
PM, Chandler
Carruth <span dir="ltr"><<a rel="nofollow" ymailto="mailto:chandlerc@gmail.com" target="_blank" href="mailto:chandlerc@gmail.com">chandlerc@gmail.com</a>></span>
wrote:<br>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div dir="ltr">
<div class="yiv5022725477gmail_quote"><span>
<div dir="ltr">On
Tue, Jul 12,
2016 at 11:34
PM Sean Silva
<<a rel="nofollow" ymailto="mailto:chisophugis@gmail.com" target="_blank" href="mailto:chisophugis@gmail.com">chisophugis@gmail.com</a>>
wrote:<br>
</div>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div dir="ltr">
<div class="yiv5022725477gmail_extra">
<div class="yiv5022725477gmail_quote">On
Tue, Jul 12,
2016 at 11:32
PM, Xinliang
David Li <span dir="ltr"><<a rel="nofollow" ymailto="mailto:davidxl@google.com" target="_blank" href="mailto:davidxl@google.com">davidxl@google.com</a>></span>
wrote:<br>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div dir="ltr"><br>
<div class="yiv5022725477gmail_extra"><br>
<div class="yiv5022725477gmail_quote"><span>On
Tue, Jul 12,
2016 at 10:57
PM, Chandler
Carruth <span dir="ltr"><<a rel="nofollow" ymailto="mailto:chandlerc@gmail.com" target="_blank" href="mailto:chandlerc@gmail.com">chandlerc@gmail.com</a>></span>
wrote:<br>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div dir="ltr">
<div class="yiv5022725477gmail_quote">
<div>Yea, this
is a nasty
problem.</div>
<div><br>
</div>
<div>One
important
thing to
understand is
that this is
specific to
analyses which
hold
references to
other
analyses.
While this
isn't unheard
of, it isn't
as common as
it could be.
Still,
definitely
something we
need to
address.</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</span>
<div>We can
call this type
of
dependencies
(holding
references)
hard-dependency.
The soft
dependency
refers to the
case where
analysis 'A'
depends on 'B'
during
computation,
but does not
need 'B' once
it is
computed.</div>
<div><br>
</div>
<div>There are
actually quite
a few examples
of
hard-dependency
case. For
instance
LoopAccessInfo,
LazyValueInfo
etc which hold
references to
other
analyses.</div>
<div><br>
</div>
<div>Problem
involving
hard-dependency
is actually
easier to
detect, as it
is usually a
compile time
problem.
Issues
involving soft
dependencies
are more
subtle and can
lead to wrong
code gen.</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</div>
</div>
</div>
<div dir="ltr">
<div class="yiv5022725477gmail_extra">
<div class="yiv5022725477gmail_quote">
<div>Did you
mean to say
that
soft-dependency
problems are
easier to
detect? At
least my
intuition is
that
soft-dependency
is easier
because there
is no risk of
dangling
pointers to
other
analyses.<br>
</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</span>
<div>The issue
is that the
fact that
there is *any*
dependency
isn't clear.</div>
<div><br>
</div>
<div>However,
I think the
only real
problem here
are these
"hard
dependencies"
(I don't
really like
that term
though). For
others, only
an analysis
that is
*explicitly*
preserved
survives. So
I'm not
worried about
the fact that
people have to
remember this.</div>
<div><br>
</div>
<div>The
question is
how often
there are
cross-data-structure
references.
David mentions
a few
examples, and
I'm sure there
are more, but
it isn't clear
to me yet
whether this
is pervasive
or occasional.</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</div>
</div>
</div>
<div dir="ltr">
<div class="yiv5022725477gmail_extra">
<div class="yiv5022725477gmail_quote">
<div>
<div><br>
I just did a
quick
run-through of
PassRegistry.def and this is what I found:</div>
<div><br>
</div>
<div>Module
analyses: 0/5
hold pointers
to other
analyses</div>
<div>CallGraph:
No pointers to
other
analyses.</div>
<div>LazyCallGraph:
No pointers to
other
analyses.</div>
<div>ProfileSummaryAnalysis:
No pointers to
other
analyses.</div>
<div>TargetLibraryAnalysis:
No pointers to
other
analyses.<br>
</div>
<div>VerifierAnalysis:
No pointers to
other
analyses.</div>
<div><br>
</div>
<div>Module
alias
analyses: 1/1
keeps pointer
to other
analysis.</div>
<div>GlobalsAA:
Result keeps
pointer to TLI
(this is a
function
analysis).</div>
<div><br>
</div>
<div>Function
analyses: 9/17
keep pointers
to other
analysis</div>
<div>AAManager:
Its Result
holds TLI
pointer and
pointers to
individual AA
result
objects.</div>
<div>AssumptionAnalysis:
No pointers to
other
analyses.<br>
</div>
<div>BlockFrequencyAnalysis:
Its Result
holds pointers
to LoopInfo
and BPI.<br>
</div>
<div>BranchProbabilityAnalysis:
Stores no
pointers to
other
analyses.
(uses LoopInfo
to
"recalculate"
though)<br>
</div>
<div>DominatorTreeAnalysis:
Stores no
pointers to
other
analyses.<br>
</div>
<div>PostDominatorTreeAnalysis:
Stores no
pointers to
other
analyses.</div>
<div>DemandedBitsAnalysis:
Stores
pointers
to AssumptionCache
and DominatorTree<br>
</div>
<div>DominanceFrontierAnalysis:
Stores no
pointers to
other
analyses.
(uses DominatorTreeAnalysis
for
"recalculate"
though).<br>
</div>
<div>LoopInfo:
Uses DominatorTreeAnalysis for "recalculate" but stores no pointers.<br>
</div>
<div>LazyValueAnalysis:
Stores
pointers
to AssumptionCache,
TargetLibraryInfo, DominatorTree.<br>
</div>
<div>DependenceAnalysis:
Stores
pointers to
AliasAnalysis,
ScalarEvolution, LoopInfo</div>
<div>MemoryDependenceAnalysis:
Stores
pointers to
AliasAnalysis,
AssumptionCache, TargetLibraryInfo, DominatorTree<br>
</div>
<div>MemorySSAAnalysis:
Stores
pointers to
AliasAnalysis,
DominatorTree<br>
</div>
<div>RegionInfoAnalysis:
Stores
pointers to
DomTree,
PostDomTree,
DomFrontier<br>
</div>
<div>ScalarEvolutionAnalysis:
Stores
pointers to
TargetLibraryInfo,
AssumptionCache, DominatorTree, LoopInfo</div>
<div>TargetLibraryAnalysis:
Has no
dependencies<br>
</div>
<div>TargetIRAnalysis:
Has no
dependencies.<br>
</div>
<div><br>
</div>
<div>Function
alias
analyses: 3/5
keep pointers
to other
analyses</div>
<div>BasicAA:
Keeps pointers
to
TargetLibraryInfo,
AssumptionCache, DominatorTree, LoopInfo</div>
<div>CFLAA:
Keeps pointer
to
TargetLibraryInfo</div>
<div>SCEVAA:
Keeps pointer
to
ScalarEvolution</div>
<div>ScopedNoAliasAA:
No
dependencies<br>
</div>
<div>TypeBasedAA:
No
dependencies<br>
</div>
<div><br>
</div>
<div><br>
</div>
<div>Total:
13/28 analyses
(~50%) hold
pointers to
other
analyses.</div>
<div>Of the
15/28 analyses
that don't
hold pointers,
12/15 simply
have no
dependencies.
Only 3/15
(BPI, LoopInfo,
DominanceFrontier) have dependencies that are used just for a
"recalculate"
step that
retains no
pointers.</div>
<div>So I
think it is
fair to say
that analyses
which hold
pointers to
other analyses
is not an
exceptional
case. In fact,
analyses that
use other
analyses just
for a
"recalculate"
step seems to
be the
exceptional
case (only
3/28 or about
10%)</div>
</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</div>
</div>
<div>Interesting!</div>
<div><br>
</div>
<div>Most of
these look
like they hold
a pointer to
the root
analysis as
opposed to
detailed
objects
*inside* the
analysis?</div>
<div><br>
</div>
<div>It might
make sense to
try to handle
this very
specific
pattern in a
special way of
overriding the
invalidate
routines is
too error
prone.... <span style="line-height:1.5;">We could try to make this work "automatically"
but I'm
worried this
would be
challenging to
get right.
Open to
suggestions of
course.</span></div>
<div><br>
</div>
<div>Any other
ideas about
what would
make sense to
handle this?</div>
<div><br>
</div>
<div>Does it
make sense to
override the
invalidate
routines now
and iterate
from there? I
feel like
you've done a
lot of the
research
necessary for
this
already...</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</div>
</div>
<div>I'll keep
pushing forward
tomorrow with
building
test-suite
successfully
using the new PM
for the LTO
pipeline (I was
doing some
unrelated LLD
stuff for most
of today). It
will be
interesting to
see how many
`invalidate`
overrides will
be needed to
avoid these
issues for just
the LTO pipeline
on test-suite.</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</div>
</div>
<div>I spent the better part
of today working on this and
will continue tomorrow; this
problem seems nastier than I
thought. For some reason the
LTO pipeline (or something
about LTO) seems to hit on
these issues much more (I'm
talking like 40k lines of
ASan error reports from
building test-suite with the
LTO pipeline in the new PM;
per-TU steps still using the
old PM). Some notes:</div>
<div><br>
</div>
<div>- BasicAA's dependence on
domtree and loopinfo in the
new PM seems to account for
quite a few of the problems.</div>
<div>- BasicAA and other stuff
are marked (by overriding
`invalidate` to return
false) to never be
invalidated because they are
"stateless". However they
still hold pointers and so
they do need to be
invalidated.</div>
<div>- CallGraph uses
AssertingVH (PR28400) and so
I needed a workaround
similar to r274656 in
various passes.</div>
<div>- <span style="font-size:12.8px;">D21921
is holding up -- I haven't
hit any issues with the
core logic of that patch.</span></div>
<div>- AAResults holds handles
to various AA result
objects. This means it
pretty much always needs to
be invalidated unless you
are sure that none of the
AA's will get invalidated.</div>
<div><br>
</div>
<div><br>
</div>
<div>The existing `invalidate`
method doesn't have the
right semantics for even an
error-prone solution :( We
are going to need to make
some significant changes to
even get basic sanity I
think. Perhaps each analysis
can expose a "preserve"
static function. E.g.
instead of
`PA.preserve<Foo>();`
you have to do
`Foo::setPreserved(PA);`.</div>
<div>I'm actually not quite
sure that that will even
work. Once I have test-suite
fully building successfully
with the LTO pipeline in the
new PM I'll be able to give
a more confident answer
(esp. w.r.t. the manager for
different IRUnitT's).</div>
<div>But at this point I'm not
confident running *any* pass
pipeline in the new PM
without at least
assertions+ASan.<br>
</div>
<div><br>
</div>
<div>We may want to have a
proper design discussion
around this problem though.</div>
<div><br>
</div>
<div>Also I'd like to have
test-suite working (by hook
or by crook) with LTO in the
new PM so we can get some
numbers on the resident set
impact of all this caching;
if it is really problematic
then we may need to start
talking front-and-center
about different invalidation
policies for keeping this in
check instead of leaving it
as something that we will be
able to patch later.<br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div>The more I think about
it, the more I'm convinced
that the real "hard" problem
that the new PM is exposing
us to is having the ability
for any pass to ask for any
analysis on any IRUnitT (and
any specific IRUnit of that
IRUnitT) and have the result
stored somewhere and then
invalidated. This means that
"getAnalysisUsage" is not
just a list of passes, but
much more complicated and is
essentially a set of
arbitrary pairs "(analysis,
IRUnit)" (and the associated
potential tangle of
dependencies between the
state cached on these
tuples). With the old PM,
you essentially are looking
at a problem of scheduling
the lifetime of analyses of
the same IRUnit intermingled
with transformation passes
on that same IRUnit, so you
only have the "analysis"
part of the tuple above,
making things much simpler
(and handling dependencies
is much simpler too).</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>To clarify, it seems like the
current new PM is essentially trying
to solve the problem of
maintaining/updating a mapping:</div>
<div>(Analysis, IRUnit) ->
AnalysisResult</div>
<div>where the AnalysisResult's can
have an arbitrary dependency on an
arbitrary set of other
AnalysisResult's currently
maintained in this mapping. In order
to invalidate any AnalysisResult you
need to invalidate all
AnalysisResult's that transitively
depend on it. Therefore the
right-hand side of this mapping
needs to be something like
`(AnalysisResult, SetOfDependents)`.</div>
<div>So the mapping is really
`(Analysis, IRUnit)
-> (AnalysisResult,
SetOfDependents)`</div>
<div>Also, this mapping can be updated
at any point during the execution of
a transformation pass (and various
other places) and must stay correct
as the IR is changed (more on this
below).</div>
<div>For example, you might have
something like:</div>
<div>(DominatorTreeAnalysis, function
@foo) -> (DominatorTree for @foo,
[(DemandedBitsAnalysis, function
@foo)])</div>
<div>(AssumptionAnalysis, function
@foo) -> (AssumptionCache for
@foo, [(DemandedBitsAnalysis,
function @foo)])</div>
<div>(DemandedBitsAnalysis, function
@foo) -> (DemandedBits for @foo,
[])</div>
<div>(AssumptionAnalysis, function
@bar) -> (AssumptionCache for
@bar, [(SomeModuleAnalysis, module
TheModule)])</div>
<div>(AssumptionAnalysis, function
@baz) -> (AssumptionCache for
@baz, [(SomeModuleAnalysis, module
TheModule)])</div>
<div>(SomeModuleAnalysis, module
TheModule) ->
(SomeModuleAnalysisResult for
TheModule, [(SomeFunctionAnalysis,
function @baz)])</div>
<div>(SomeFunctionAnalysis, function
@baz) ->
(SomeFunctionAnalysisResult for
@baz, [])</div>
<div><br>
</div>
<div>So for example, when a
transformation pass invalidates
`(AssumptionAnalysis, function
@bar)`, we need to walk
`(SomeModuleAnalysis, module
TheModule)` and
`(SomeFunctionAnalysis, function
@baz)` to invalidate them.</div>
<div><br>
</div>
<div><br>
</div>
<div>Compare this with the old PM
(although like I said we have
outgrown this model). Essentially
you take the previous mapping, and
require IRUnit to be a constant at
any given point in time. Hence the
mapping is essentially<br>
Analysis -> AnalysisResult</div>
<div>Since this is 1:1 there is no
real distinction between the
Analysis and the AnalysisResult (and
as part of transitioning to the new
PM this has had to be untangled).</div>
<div>This also makes the dependencies
simpler since you just have a set of
"what analyses have been run at this
point". You just need to run the
analyses individually and make sure
they are in the right order. Also,
getAnalysis just takes the Analysis
to get the AnalysisResult which
makes it simpler -- you just query
which analyses are live.</div>
<div><br>
</div>
<div><br>
</div>
<div>Also, the mapping `(Analysis,
IRUnit) -> (AnalysisResult,
SetOfDependents)` that the new PM is
essentially trying to keep is even
more complicated because for e.g.
Loop and CGSCC passes the IRUnit
itself is an object created by an
analysis and subject to invalidation
of that analysis as the IR changes
underneath it.</div>
<div><br>
</div>
<div>And then there is the question of
at what points must this mapping be
valid (i.e. no stale analysis
results, no dangling pointers, etc.)
and when the transitive invalidation
walking happens. Evidently while a
transformation pass is running,
things might temporarily be stale;
what are the "checkpoints" where the
mapping is guaranteed to be valid?
At the start of each transformation
pass? At least Chandler's D21464
does not stick to this because the
IRUnit's (SCC's) are only updated at
the end of running potentially many
function transformation passes. I.e.
all but the first function
transformation pass might observe
stale IRUnit's (SCC's).</div>
<div><br>
</div>
<div>One other thing to note is that
soft-dependencies (using David's
terminology) don't require this kind
of dependency tracking. An analysis
result can be cached even though its
soft-dependencies are not cached.
And invalidation of
soft-dependencies does not require
invalidating the soft-dependents.
Actually, this makes it the
terminology "soft" and "hard' quite
natural; "hard" requires an edge to
track the dependency for
invalidation purposes, "soft" does
not.</div>
<div><br>
</div>
<div>This is all quite general.
Perhaps too much. We clearly need to
go beyond the old PM's model, but we
may not need to go to the fully
general case. Is there a good
middle-ground that meets our needs?
What restrictions would we be
willing to live with in order to
make it easier? The first one on my
list is to not have the IRUnit's
themselves depend on analyses. Like
Chandler mentioned on D21921 this
has the effect of e.g. preventing
caching across the intervening
module pass in a case like
`module(cgscc(require<foo-cgsc c-analysis>),some-module-pass- that-makes-no-changes,cgscc(so me-cgscc-pass-that-uses-foo-cg scc-analysis))`
but that seems like a restriction we
can live with.</div>
<div><br>
</div>
<div><br>
</div>
<div>Again, sorry for the braindump.</div>
<div><br>
</div>
<div><br>
</div>
<div>-- Sean Silva</div>
<div> </div>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div dir="ltr">
<div class="yiv5022725477gmail_extra">
<div class="yiv5022725477gmail_quote">
<div> We've obviously outgrown
this model with examples
like LAA,
AssumptionCacheTracker, etc.
that hack around this in the
old PM. We may want to have
a fresh re-examination of
what problems we are exactly
trying to solve.</div>
<div><br>
</div>
<div>For me, my main concern
now is what changes need to
be made in order to feel
confident running a pipeline
in the new PM
without assertions+ASan.</div>
<div><br>
</div>
<div><br>
</div>
<div>Sorry for the long post,
just brain-dumping before
heading home.</div>
<div><br>
</div>
<div>-- Sean Silva</div>
<div><br>
</div>
<div><br>
</div>
<div> </div>
<blockquote class="yiv5022725477gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex;">
<div dir="ltr">
<div class="yiv5022725477gmail_extra">
<div class="yiv5022725477gmail_quote"><span><font color="#888888">
<div><br>
</div>
<div>-- Sean Silva</div>
</font></span></div>
<br>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</div>
</div>
</div>
</blockquote>
<br>
<br>
<span><br>
-- <br>
<div><span></span>Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<span></span><br>
</div>
</span></div>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
<br>
<fieldset></fieldset>
<br>
</div></div><span><pre>______________________________ _________________
LLVM Developers mailing list
<a rel="nofollow" ymailto="mailto:llvm-dev@lists.llvm.org" target="_blank" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a rel="nofollow" target="_blank" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/ mailman/listinfo/llvm-dev</a>
</pre>
</span></blockquote>
<div><br>
</div>
</div>
</blockquote></div><br></div></div></div><br>_______________________________________________<br>LLVM Developers mailing list<br><a ymailto="mailto:llvm-dev@lists.llvm.org" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br><br><br></div> </div> </div> </div></div></body></html>