<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Aug 7, 2016 at 4:55 PM, Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span> wrote:<br><blockquote class="gmail_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 bgcolor="#FFFFFF" text="#000000">
    <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="gmail_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 bgcolor="#FFFFFF" text="#000000"><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="gmail_quote">
        <div dir="ltr">On Thu, Jul 14, 2016 at 7:48 PM Sean Silva <<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>>
          wrote:<br>
        </div>
        <blockquote class="gmail_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="gmail_extra">
              <div class="gmail_quote">On Thu, Jul 14, 2016 at 7:21 PM,
                Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span>
                wrote:<br>
                <blockquote class="gmail_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="gmail_extra">
              <div class="gmail_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="gmail_extra">
              <div class="gmail_quote">
                <div><br>
                </div>
                <div>-- Sean Silva</div>
              </div>
            </div>
          </div>
          <div dir="ltr">
            <div class="gmail_extra">
              <div class="gmail_quote">
                <div> </div>
                <blockquote class="gmail_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 href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>><br>
                          <b>To: </b>"Chandler Carruth" <<a href="mailto:chandlerc@gmail.com" target="_blank">chandlerc@gmail.com</a>><br>
                          <b>Cc: </b>"Xinliang David Li" <<a href="mailto:davidxl@google.com" target="_blank">davidxl@google.com</a>>,
                          "llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>,
                          "Davide Italiano" <<a href="mailto:dccitaliano@gmail.com" target="_blank">dccitaliano@gmail.com</a>>,
                          "Tim Amini Golling" <<a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a>>,
                          "Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>>,
                          "Sanjoy Das" <<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.co<wbr>m</a>>,
                          "Pete Cooper" <<a href="mailto:peter_cooper@apple.com" target="_blank">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="gmail_extra"><br>
                            <div>
                              <div>
                                <div class="gmail_quote">On Thu, Jul 14,
                                  2016 at 12:51 AM, Sean Silva <span dir="ltr"><<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>></span>
                                  wrote:<br>
                                  <blockquote class="gmail_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="gmail_extra"><br>
                                        <div class="gmail_quote">
                                          <div>
                                            <div>On Wed, Jul 13, 2016 at
                                              1:48 AM, Sean Silva <span dir="ltr"><<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>></span>
                                              wrote:<br>
                                              <blockquote class="gmail_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="gmail_extra"><br>
                                                    <div class="gmail_quote">
                                                      <div>
                                                        <div>On Wed, Jul
                                                          13, 2016 at
                                                          12:34 AM,
                                                          Chandler
                                                          Carruth <span dir="ltr"><<a href="mailto:chandlerc@gmail.com" target="_blank">chandlerc@gmail.com</a>></span>
                                                          wrote:<br>
                                                          <blockquote class="gmail_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="gmail_quote">
                                                          <div>
                                                          <div>
                                                          <div dir="ltr">On
                                                          Wed, Jul 13,
                                                          2016 at 12:25
                                                          AM Sean Silva
                                                          <<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>>
                                                          wrote:<br>
                                                          </div>
                                                          <blockquote class="gmail_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="gmail_extra">
                                                          <div class="gmail_quote">On
                                                          Tue, Jul 12,
                                                          2016 at 11:39
                                                          PM, Chandler
                                                          Carruth <span dir="ltr"><<a href="mailto:chandlerc@gmail.com" target="_blank">chandlerc@gmail.com</a>></span>
                                                          wrote:<br>
                                                          <blockquote class="gmail_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="gmail_quote"><span>
                                                          <div dir="ltr">On
                                                          Tue, Jul 12,
                                                          2016 at 11:34
                                                          PM Sean Silva
                                                          <<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>>
                                                          wrote:<br>
                                                          </div>
                                                          <blockquote class="gmail_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="gmail_extra">
                                                          <div class="gmail_quote">On
                                                          Tue, Jul 12,
                                                          2016 at 11:32
                                                          PM, Xinliang
                                                          David Li <span dir="ltr"><<a href="mailto:davidxl@google.com" target="_blank">davidxl@google.com</a>></span>
                                                          wrote:<br>
                                                          <blockquote class="gmail_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="gmail_extra"><br>
                                                          <div class="gmail_quote"><span>On
                                                          Tue, Jul 12,
                                                          2016 at 10:57
                                                          PM, Chandler
                                                          Carruth <span dir="ltr"><<a href="mailto:chandlerc@gmail.com" target="_blank">chandlerc@gmail.com</a>></span>
                                                          wrote:<br>
                                                          <blockquote class="gmail_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="gmail_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="gmail_extra">
                                                          <div class="gmail_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="gmail_extra">
                                                          <div class="gmail_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<wbr>c-analysis>),some-module-pass-<wbr>that-makes-no-changes,cgscc(so<wbr>me-cgscc-pass-that-uses-foo-cg<wbr>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="gmail_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="gmail_extra">
                                        <div class="gmail_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="gmail_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="gmail_extra">
                                                <div class="gmail_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 name="x"></span>Hal Finkel<br>
                          Assistant Computational Scientist<br>
                          Leadership Computing Facility<br>
                          Argonne National Laboratory<span name="x"></span><br>
                        </div>
                      </span></div>
                  </div>
                </blockquote>
              </div>
            </div>
          </div>
        </blockquote>
      </div>
      <br>
      <fieldset></fieldset>
      <br>
      </div></div><span><pre>______________________________<wbr>_________________
LLVM Developers mailing list
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a>
</pre>
    </span></blockquote>
    <p><br>
    </p>
  </div>

</blockquote></div><br></div></div>