<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 8, 2015 at 2:37 PM, Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
  
    
  
  <div bgcolor="#FFFFFF" text="#000000"><span class="">
    <br>
    <div>On 01/07/2015 05:33 PM, Chandler
      Carruth wrote:<br>
    </div>
    <blockquote 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 href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span>
            wrote:<br>
            <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style: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></span>
    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.  </div></blockquote><div><br></div><div><a href="http://webdocs.cs.ualberta.ca/~amaral/papers/BartonCC05.pdf">http://webdocs.cs.ualberta.ca/~amaral/papers/BartonCC05.pdf</a></div><div><br></div><div>This is essentially index set splitting with the goal of it being an enabling optimization for LICM.</div></div><br></div><div class="gmail_extra">(At least, as i've seen it implemented in other compilers)<br><br></div></div>