<html>
  <head>
    <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    <br>
    <div class="moz-cite-prefix">On 01/11/2015 10:35 PM, Daniel Berlin
      wrote:<br>
    </div>
    <blockquote
cite="mid:CAF4BwTXbAC7JiNy6J_DWOeoNiCV-YO+wCvsNUK+wFbyZAjomTA@mail.gmail.com"
      type="cite">
      <div dir="ltr">
        <div class="gmail_extra">
          <div class="gmail_quote">
            <blockquote class="gmail_quote" style="margin:0 0 0
              .8ex;border-left:1px #ccc solid;padding-left:1ex">
              <div dir="ltr">
                <div class="gmail_extra">
                  <div class="gmail_quote">
                    <div><br>
                    </div>
                    <div>Looking at what LLVM does, the failing on the
                      PRE side is that our PRE/GVN models are not strong
                      enough to handle this. I'm not sure at all why we
                      think anything else is necessary.  </div>
                  </div>
                </div>
              </div>
            </blockquote>
            <div><br>
            </div>
            <div>By this i mean we don't actually perform real PRE for
              loads. It's a known deficiency and one that does not
              require any duplicate heuristics to solve.</div>
            <div>Right now we perform some availability based removal
              that happens be willing to do an insertion here or there
              to try to move a load in some cases (it will only do a
              single insertion).  It's not also based on real
              availability, but on finding nearest dependencies of loads
              and squinting at them (which is not even really the same
              as finding where a load stops being available) funny.</div>
            <div><br>
            </div>
            <div>It's also not real PRE, just some code that is willing
              to insert one load to move a load.</div>
          </div>
        </div>
      </div>
    </blockquote>
    Er, I think we have a terminology problem here.  From what I can
    gather, our current implementation *is* an implementation of classic
    PRE.  It's more or less directly organized around the classic
    "available" and "anticipated" concepts from the literature.  The
    *implementation* has some limitations, but the conceptual framework
    is there*.  One of the key invariants in classic PRE is that you do
    not change program behaviour on any path.  As a result, moving (or
    at most duplicating) loads is pretty much all that happens.<br>
    <br>
    * It took me a few hours of squinting at the code to recognize that
    weird backwards walk as being an implementation of "anctipated", but
    it is.  The "available" part comes from MemoryDependenceAnalysis and
    the forward dataflow algorithm based on those inputs.<br>
    <br>
    If you want to start inserting loads on paths which didn't
    previously have them - for example the loop preheader in your
    example in the previous email - this is not classic PRE as I'm
    familiar with it.  It can be very profitable and worthwhile, but is
    not classic PRE.   I'm not sure what this variant is known as in the
    literature.  <br>
    <br>
    (If I'm being overly pedantic here, or just flat out wrong, please
    say so.  I'm still exploring related material and am trying to
    categorize things in my own head.)<br>
    <br>
    I think we actually in reasonable agreement that we do need to move
    beyond 'classic PRE' as I called it above.  If you have specific
    suggestions, positive or negative examples, or other thoughts to
    share, I'd very much value the input.  <br>
    <blockquote
cite="mid:CAF4BwTXbAC7JiNy6J_DWOeoNiCV-YO+wCvsNUK+wFbyZAjomTA@mail.gmail.com"
      type="cite">
      <div dir="ltr">
        <div class="gmail_extra">
          <div class="gmail_quote">
            <div><br>
            </div>
            <div>If you want this case to work, what you need is a real
              Load PRE implementation, not one based on simple memdep
              based load moving.</div>
          </div>
        </div>
      </div>
    </blockquote>
    <blockquote
cite="mid:CAF4BwTXbAC7JiNy6J_DWOeoNiCV-YO+wCvsNUK+wFbyZAjomTA@mail.gmail.com"
      type="cite">
      <div dir="ltr">
        <div class="gmail_extra">
          <div class="gmail_quote">
            <div><br>
            </div>
            <div>Trying to hack this one up with profile guided code
              duplication, etc, to get it to kinda sorta work seems to
              me to be a bad idea.</div>
          </div>
        </div>
      </div>
    </blockquote>
    Not sure I really agree here, but I'm open to pushing as far as we
    can with static heuristics first.  I suspect that's likely to be
    more stable w.r.t. optimization effect and applicable to more
    cases.  <br>
    <blockquote
cite="mid:CAF4BwTXbAC7JiNy6J_DWOeoNiCV-YO+wCvsNUK+wFbyZAjomTA@mail.gmail.com"
      type="cite">
      <div dir="ltr">
        <div class="gmail_extra">
          <div class="gmail_quote">
            <div>  </div>
            <blockquote class="gmail_quote" style="margin:0 0 0
              .8ex;border-left:1px #ccc solid;padding-left:1ex">
              <div dir="ltr">
                <div class="gmail_extra">
                  <div class="gmail_quote">
                    <div>It's certainly not requiring special code
                      duplication heuristics, etc.</div>
                    <div><br>
                    </div>
                    <div>So either you are thinking of a case that is
                      different from the above, or I am seriously
                      confused :)</div>
                  </div>
                </div>
              </div>
            </blockquote>
          </div>
          <br>
        </div>
      </div>
    </blockquote>
    <br>
  </body>
</html>