<br><br><div class="gmail_quote">On Mon, Nov 15, 2010 at 10:38 AM, Brian West <span dir="ltr"><<a href="mailto:bnwest@rice.edu">bnwest@rice.edu</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"><div class="im">
    On 11/13/10 11:05 PM, Daniel Berlin wrote:
    </div><blockquote type="cite">
      <div class="gmail_quote"><div class="im">
        <blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204, 204, 204);padding-left:1ex">A big downside of the current LSR
          algorithm is it's slow.  I had initially<br>
          hoped that some of the heuristics would protect it better, but
          the problem is<br>
          more complex than I had expected.  I haven't done any
          measurements,<br>
          but it's likely that OSR is faster, which may interest some
          people regardless<br>
          of how the output compares.<br>
        </blockquote>
        <br>
        </div><div class="im"><div>There is one thing both the original paper, the original
          MSCP implementation did (too bad the links to this point to <a href="http://ftp.cs.rice.edu" target="_blank">ftp.cs.rice.edu</a>,
          which no longer works, the web files were a great
          implementation resource) , and my GCC implementation did,
          which is LFTR (Linear Function Test Replacement). LFTR after
          OSR can help reduce register pressure since it enables
          eliminating the IV's that no longer serve any useful purpose.
           I don't see any implementation in this code.</div>
        <div><br>
        </div>
        <div>--Dan</div>
      </div></div>
    </blockquote>
    Dan,<br>
    <br>
    LFTR (Linear Function Test Replacement) was mentioned in the
    original paper.  I considered including LFTR with OSR, but decided
    to get OSR to trunk first and then add LFTR (-lftr) as a separate
    pass later.  </div></blockquote><div><br></div><div>I'm not sure why you'd add it as a separate pass, it is about 80-150 lines of code, and adding it as as a separate pass requires you to do things like induction variable detection + etc all over again.</div>
<div><br></div><div>See <a href="http://gcc.gnu.org/ml/gcc-patches/2007-01/msg01035.html">http://gcc.gnu.org/ml/gcc-patches/2007-01/msg01035.html</a>, record_edge, apply_lftr_edge, follow_lftr_edge and perform_lftr</div><div>
<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div bgcolor="#ffffff" text="#000000">The LLVM development documentation suggests that new
    work be committed piecemeal over time.<br>
    <br></div></blockquote><div>Sure, but that doesn't mean you should commit something that is going </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">
    LLVM does have an optimization pass, -instcombine, which will delete
    unused induction variables. </div></blockquote><div><br></div><div>LFTR does not delete unused IV's directly, it does reductions to transform the IV into something else.</div><div>instcombine could only do this if it knew the sequence of reductions we applied to strength reduce the IV in the first place, or if it computed equivalence of ivs itself.</div>
<div>Both of these are not cheap operations.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div bgcolor="#ffffff" text="#000000">I recommend that -instcombine be run
    after OSR. </div></blockquote><div><br></div><div>In general, there is a careful balance between leaving the IR in a state that requires expensive cleanup, and doing some of that cleanup yourself where it's cheap and easy.</div>
<div>If you were to simply fall on the extreme of running cleanup passes after every optimization, your compiler would be much slower.</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"> It is my understanding that LFTR would attempt to remove
    induction variables whose only use is to participate in an
    end-loop-of-loop test condition.</div></blockquote><div><br></div><div>Well, no, any IV whose only use is a comparison and a linear function of an existing IV.  This is mostly end of loop test conditions, but you'd be surprised where else this pops up.</div>
<div><br></div><div>Logging or progress tracking, for example, where you do things like</div><div><br></div><div>if (i % 100 == 0) {</div><div>   printf(".");</div><div>}<br><br></div><div>etc</div><div><br></div>
<div>Anyway, it looks like the consensus so far is that you need to produce some compile time and benchmark numbers showing OSR is worth it as it's own pass as opposed to replacing/augmenting the LSR implementation that exists now with it.</div>
<div><br></div><div>--Dan </div></div>