<div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;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><div><br></div><div><br></div><div>A few years ago, I implemented OSR (with some slight modifications) in GCC, though it was never committed to mainline (it's on a branch somewhere)</div>
<div>It was significantly faster than ivopts (which does what you guys are using LSR for), and found more cases than ivopts did, I just never integrated the same target dependent stuff so it never made it into the mainline.</div>
<div><br>Note that as written in the paper, OSR is pretty target independent because of the order of processing.  It expects to do it's processing on each SCC as it completes the SCC, so it doesn't gather all the possible things it could do before doing them, and then decide what is best.</div>
<div><br></div><div>It is also possible for a "do everything" OSR to completely blow up register pressure if there are a number of conditional iv updates + operations based on them in the loop, since it will have to generate a new variable for each of these cases that will end up live over the entire loop.</div>
<div><br></div><div><br></div><div>So i think you may see good things if you took the OSR code and used it as a basis for LSR.</div><div><br></div><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">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><br></div></div>