<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jun 21, 2017 at 6:00 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
  
    
  
  <div bgcolor="#FFFFFF" text="#000000"><div><div class="h5">
    <p><br>
    </p>
    <div class="m_-4487549714715789291moz-cite-prefix">On 06/13/2017 01:29 PM, Daniel Berlin
      via llvm-dev wrote:<br>
    </div>
    <blockquote type="cite">
      
      <div dir="ltr"><br>
        <div class="gmail_extra"><br>
          <div class="gmail_quote">On Mon, Jun 12, 2017 at 11:24 PM,
            Tobias Grosser via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span>
            wrote:<br>
            <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi  Jakub,<br>
              <br>
              thanks for the update. I was already eagerly waiting to
              hear what your<br>
              internship on dominance brings. I think the numbers are
              already very<br>
              encouraging and I believe moving incrementally over to the
              new algorithm<br>
              is exactly the right approach.<br>
              <br>
              I have a couple of questions:<br>
              <br>
              1) Daniel and Chandler have for a long time been talking
              about computing<br>
              dominance and post-dominance in one shot to reduce the
              cost of<br>
              post-dominance and make it (freely) available everywhere. 
              Is this<br>
              covered by your current (or planned) work?<br>
            </blockquote>
            <div><br>
            </div>
            <div>I think chandler more than me. If me, assume I was
              wrong :P</div>
            <div><br>
            </div>
            <div>I believe you can prove it is not possible to  do this
              without doing all the work of the separate passes. The
              main cost is the DFS walk, and you can't do an undirected
              DFS that will work here.</div>
            <div>I believe related things have even been proven to show
              the brokenness of various algorithms.<br>
            </div>
            <div><br>
            </div>
            <div>See <a href="https://hal.inria.fr/hal-00761505" target="_blank">https://hal.inria.fr/hal-<wbr>00761505</a>
              section 4.1</div>
            <div><br>
            </div>
            <div>Given the difficulties and subtleties here, I would
              consider any such approach that tried to share work
              between the passes as "fraught with peril"<br>
            </div>
          </div>
        </div>
      </div>
    </blockquote>
    <br></div></div>
    Is there a difference here between sharing work and sharing updates?
</div></blockquote><div><br></div><div>Yes.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div bgcolor="#FFFFFF" text="#000000">    The difficult part of using postdominance seems to be not the
    one-time cost of computing it, but the fact that we don't preserve
    it anywhere. Thus, using it would require re-computing it a lot.
    Even if we can't share the work of constructing a dominance and
    post-dominance tree, could we have an update API that could be used
    to keep both trees consistent?<br>
    <br></div></blockquote><div><br></div><div>This is precisely what Jakub's set of patches solves.</div><div>The API for updating either dominance or post-dominance will be identical.</div><div>It just needs to be informed of new edges and removed edges in the CFG.</div><div><br></div><div>It's possible,at least in the new PM, to easily have a DominatorTreeUpdater utility that uses getAnalysisIfAvailable on both dominator and postdominator analysis, and calls through to the update API for each one.</div><div><br></div></div></div></div>