<html>
  <head>
    <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    <p><br>
    </p>
    <div class="moz-cite-prefix">On 06/13/2017 01:29 PM, Daniel Berlin
      via llvm-dev wrote:<br>
    </div>
    <blockquote
cite="mid:CAF4BwTVeTqN8FG1v0UVtH=4o5j7mPs4eJCAnehPz5HAzMeF4DA@mail.gmail.com"
      type="cite">
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
      <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
                moz-do-not-send="true"
                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 moz-do-not-send="true"
                href="https://hal.inria.fr/hal-00761505">https://hal.inria.fr/hal-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>
    Is there a difference here between sharing work and sharing updates?
    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>
    Thanks again,<br>
    Hal<br>
    <br>
    <blockquote
cite="mid:CAF4BwTVeTqN8FG1v0UVtH=4o5j7mPs4eJCAnehPz5HAzMeF4DA@mail.gmail.com"
      type="cite">
      <div dir="ltr">
        <div class="gmail_extra">
          <div class="gmail_quote">
            <div><br>
            </div>
            <div><br>
            </div>
            <div><br>
            </div>
          </div>
        </div>
      </div>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
    </blockquote>
    <br>
    <pre class="moz-signature" cols="72">-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
  </body>
</html>