<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/12/2017 07:58 PM, Sean Silva via
      llvm-dev wrote:<br>
    </div>
    <blockquote
cite="mid:CAHnXoamYg5doTyCTntkRXv_H79RNmnnAc9n=ozQ56rp9VVj4rA@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 5:12 PM,
            Jakub (Kuba) Kuderski 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:0 0 0
              .8ex;border-left:1px #ccc solid;padding-left:1ex">
              <div dir="ltr">
                <div>
                  <div>Hi folks,<br>
                    ...
                    <div> </div>
                    <div>a) Keep the existing DomTree and gradually
                      replace its uses with the new one. It is possible
                      to convert the DBS-based dominators to the old
                      ones.</div>
                    <div>b) Replace the existing DomTree with the new,
                      dynamic dominators. Nuke all of the old update
                      functions and replace their uses with the new
                      incremental API in one commit.</div>
                    <div>c) Replace the existing DomTree with the new
                      one, but keep the old API around and mark it as
                      deprecated. If someone invokes one of the old
                      update functions, mark the the additional
                      information as invalid for dynamic deletions.
                      Follow the pessimistic but correct dynamic
                      deletion path if the additional information is
                      marked as invalidated. Gradually modernize the
                      projects to use the new API instead and then
                      remove the old update functions.</div>
                    <div> </div>
                    <div>Maintaining the old DT and the new one
                      simultaneously seems like a waste of time as the
                      DBS offers better or similar performance to the
                      existing SLT-based implementation.</div>
                    <div>The problem with replacing the old API with the
                      new one is that it’s used in many places (~100)
                      across the project and I believe that doing that
                      all at once would be tricky to get correct.
                      Gradual update seems much easier to ensure
                      correctness and the transitional API (invalid
                      additional data check) is trivial to implement.
                      Because of that, I propose to follow the option
                      (c). </div>
                  </div>
                </div>
              </div>
            </blockquote>
            <div><br>
            </div>
            <div>(c) sounds like the best choice to me too. That would
              also allow fixing dominator verification failures first,
              giving a nice immediate benefit to motivate and kickstart
              the transition.</div>
          </div>
        </div>
      </div>
    </blockquote>
    <br>
    +1<br>
    <br>
     -Hal<br>
    <br>
    <blockquote
cite="mid:CAHnXoamYg5doTyCTntkRXv_H79RNmnnAc9n=ozQ56rp9VVj4rA@mail.gmail.com"
      type="cite">
      <div dir="ltr">
        <div class="gmail_extra">
          <div class="gmail_quote">
            <div><br>
            </div>
            <div>-- Sean Silva</div>
            <div> </div>
            <blockquote class="gmail_quote" style="margin:0 0 0
              .8ex;border-left:1px #ccc solid;padding-left:1ex">
              <div dir="ltr">
                <div>
                  <div><br>
                    <br>
                    <br>
                  </div>
                  <div>[1] Georgiadis et al., An Experimental Study of
                    Dynamic Dominators, <a moz-do-not-send="true"
                      href="https://arxiv.org/pdf/1604.02711.pdf"
                      target="_blank">https://arxiv.org/pdf/1604.<wbr>02711.pdf</a></div>
                  <div>[2] llvm-dominators LLVM fork on Github, <a
                      moz-do-not-send="true"
                      href="https://github.com/kuhar/llvm-dominators"
                      target="_blank">https://github.com/<wbr>kuhar/llvm-dominators</a></div>
                  <div>[3] L. Georgiadis, Linear-Time Algorithms for
                    Dominators and Related Problems, <a
                      moz-do-not-send="true"
                      href="ftp://ftp.cs.princeton.edu/reports/2005/737.pdf"
                      target="_blank">ftp://ftp.cs.princeton.edu/<wbr>reports/2005/737.pdf</a>
                    p. 38</div>
                  <div>[4] Google Doc with the performance numbers, <a
                      moz-do-not-send="true"
href="https://docs.google.com/document/d/1wPYeWykeO51YDPLYQEg4KNTlDIGIdyF65OTfhSMaNHQ/edit?usp=sharing"
                      target="_blank">https://docs.google.com/<wbr>document/d/<wbr>1wPYeWykeO51YDPLYQEg4KNTlDIGId<wbr>yF65OTfhSMaNHQ/edit?usp=<wbr>sharing</a></div>
                </div>
              </div>
              <br>
              ______________________________<wbr>_________________<br>
              LLVM Developers mailing list<br>
              <a moz-do-not-send="true"
                href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
              <a moz-do-not-send="true"
                href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
                rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
              <br>
            </blockquote>
          </div>
          <br>
        </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>