<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/07/2015 05:33 PM, Chandler
      Carruth wrote:<br>
    </div>
    <blockquote
cite="mid:CAGCO0Kj=brN28yWvH-5yQCQ9-Wa0i1rFX_2eu9S2H8Rbeu6PUg@mail.gmail.com"
      type="cite">
      <div dir="ltr">
        <div class="gmail_extra"><br>
          <div class="gmail_quote">On Wed, Jan 7, 2015 at 5:19 PM,
            Philip Reames <span dir="ltr"><<a moz-do-not-send="true"
                href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</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">I've been playing
                with approaches to getting better optimization of loops
                which contain infrequently executed slow paths.  I've
                gotten as far as throwing together a proof of concept
                implementation of a profile guided optimization to
                separate a single loop with multiple latches into a loop
                nest, but I want to get feedback from interested parties
                before investing much more effort.  <br>
                <br>
                The primary case I'm concerned about looks something
                like this C example:<br>
                while( some_condition )<br>
                  //do lots of work here<br>
                  if (!some_rare_condition) { <-- This is loop
                variant<br>
                    helper();<br>
                  }<br>
                }<br>
                <br>
                The key point here is that the 'do lots of work' section
                contains things we could lift out of the loop, but our
                knowledge of memory gets completely destoryed by the
                'helper' call which doesn't get inlined.  This ends up
                crippling LICM in particular, and GVN to a lessor
                degree.  <br>
                <br>
                The approach I've been playing with would create this
                loop structure:<br>
                goto inner<br>
                while (true) {<br>
                  outer:<br>
                  helper();<br>
                  inner:<br>
                  while( some_condition )<br>
                    //do lots of work here<br>
                    if (!some_rare_condition) { <-- This is loop
                variant<br>
                      goto outer;<br>
                    }<br>
                  }<br>
                }<br>
                <br>
                (Excuse the psuedo-C.  Hopefully the idea is clear.)<br>
              </div>
            </blockquote>
            <div><br>
            </div>
            <div>Yep.</div>
            <div><br>
            </div>
            <div>I've not thought about this a lot, but I have two
              initial questions that maybe you can answer:</div>
            <div><br>
            </div>
            <div>How does this compare with classical approaches of loop
              peeling, partitioning, fission, or whatever you might call
              it? Is there any literature behind this approach or some
              literature it should be compared with? (I genuinely don't
              know this area that well, so I'm of little help here...)</div>
          </div>
        </div>
      </div>
    </blockquote>
    I'm not aware of any literature that covers the specific transform
    I'm suggesting here.  This is probably a lack of awareness on my
    part, not a lack of literature though.  While I have some basic
    background in the area, I can't claim to have made an extensive
    study of loop optimization techniques.  *Particularly* profile
    guided ones.  <br>
    <br>
    w.r.t. the tradoffs in practice, I'm going to answer this in a
    separate response just to keep this one short.  I've been playing
    with both approaches and there appears to be appeal in both.  I'm
    currently leaning towards a mixture of both approaches.  <br>
    <br>
    <blockquote
cite="mid:CAGCO0Kj=brN28yWvH-5yQCQ9-Wa0i1rFX_2eu9S2H8Rbeu6PUg@mail.gmail.com"
      type="cite">
      <div dir="ltr">
        <div class="gmail_extra">
          <div class="gmail_quote">
            <div> </div>
            <div><br>
            </div>
            <div>Some of your points I have quick feedback on:</div>
            <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>
                    <p>Points for discussion:</p>
                    <ul>
                      <li>Is using profile information for this purpose
                        even a reasonable thing to do?</li>
                    </ul>
                  </div>
                </div>
              </div>
            </blockquote>
            <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">
                <div>
                  <div>
                    <ul>
                      <li>I chose to implement this without relying on
                        the existing block frequency analysis. My
                        reasoning was that a) this is a rarely taken
                        case and adding an expensive analysis dependency
                        probably wasn't worthwhile and b) that block
                        frequency analysis was more expensive/precise
                        than I really needed. Is this reasonable?</li>
                    </ul>
                  </div>
                </div>
              </div>
            </blockquote>
            <div>I think we should always use the analyses. Either
              BlockFrequency or BranchProbability. I think probably both
              in the common joint usage (frequency of the loop header
              combined with probability of the cold region).</div>
          </div>
        </div>
      </div>
    </blockquote>
    Let me ask a basic question: what do BlockFrequency and
    BranchProbability compute and roughly what mental cost model should
    I have?  Once I have a BlockFrequency, what does it mean?  Some of
    this is documented in BlockFrequencyImpl.h, but the high level bits
    are mostly missing.  Particularly for BranchProbability.  <br>
    <br>
    I chose to write a custom analysis in large part because I didn't
    understand the existing analysis and my (possibly completely wrong)
    perception is that they're overly precise/expensive for what I
    need.  I wanted to focus on the writing the transform since that's
    the point I actually wanted to discuss.  :)<br>
    <br>
    <blockquote
cite="mid:CAGCO0Kj=brN28yWvH-5yQCQ9-Wa0i1rFX_2eu9S2H8Rbeu6PUg@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 bgcolor="#FFFFFF" text="#000000">
                <div>
                  <div>
                    <ul>
                      <li>If so, is the notion of 'rareness' of a loop
                        block something that's worth extracting out on
                        it's own and reusing? Are there other similar
                        uses anyone can think of?</li>
                      <li>Currently, I'm only supporting a fairly small
                        set of controlling conditions. Are there
                        important cases I'm not considering?</li>
                    </ul>
                  </div>
                </div>
              </div>
            </blockquote>
            <div>To both of these, I think the general combination to
              use is to identify the set of blocks dominated by a block
              which is in the loop body of a hot loop, and is cold
              relative to the other successors of its predecessor(s).
              These form cold "regions" as I think of them without
              requiring the complexity of the region analysis.</div>
          </div>
        </div>
      </div>
    </blockquote>
    I get why you find this a useful mental model, but the transform is
    far harder to express this way in the couple of cases I've looked
    at.  It's much easier to start with a latch, reason about it's
    hotness, and then let the generic loop code construct the cold
    "region".<br>
    <br>
    Then again, if you were to ask for the set of latches which were
    dominated by blocks in the cold-with-hot-predecessors list, that
    might be interesting.  But again, I'd really like to start from the
    latches since that's what controls the legality/profitability of the
    transform.  Hm, we could walk back along the dom tree from the latch
    looking for such a cwhp block... This might be a better way to think
    about the profitability of the transform, even starting from the
    latch.  Is that what you were trying to get at to start with?  Or
    were you looking for something more general?<br>
    <br>
    <blockquote
cite="mid:CAGCO0Kj=brN28yWvH-5yQCQ9-Wa0i1rFX_2eu9S2H8Rbeu6PUg@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 bgcolor="#FFFFFF" text="#000000">
                <div>
                  <div>
                    <ul>
                      <li>Since the rarest latch is often deep in a loop
                        - with other "if (X) continue;" (i.e. latches)
                        before it - this tends to create loops with
                        multiple exiting blocks. Some of the existing
                        passes might not deal with this well, is that a
                        major concern? Suggestions for how to analysis
                        and validate?</li>
                    </ul>
                  </div>
                </div>
              </div>
            </blockquote>
            <div>I'm somewhat concerned about this, but want to think
              more about the fundamental transformation.</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">
                <div>
                  <div>
                    <ul>
                      <li>Currently, I've structured this as pulling off
                        the rarest latch as an outer iteration. I could
                        also pull off the most popular latch as an inner
                        iteration. This might give different tradeoffs;
                        thoughts?</li>
                    </ul>
                    <p>Generally, any thoughts anyone have on the
                      problem or approach are welcome. I'm not
                      particular attached to the particular approach
                      laid out here and if there's a more advantageous
                      approach, all the better.</p>
                  </div>
                </div>
              </div>
            </blockquote>
          </div>
          Thanks for pushing on this! ;] Now I need to go and ponder a
          lot so i can reply more deeply on the actual transform.<br>
        </div>
      </div>
    </blockquote>
    You're welcome.  :)<br>
    <br>
    This might be an area where it's profitable to talk in person, are
    you going to be at the social tonight?<br>
    <br>
    Philip<br>
    <br>
  </body>
</html>