<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
On 11/13/10 11:05 PM, Daniel Berlin wrote:
<blockquote
cite="mid:AANLkTi=C=QYMg23vpVMM_qv0bkcOCfMnKPDXkPsqwGb=@mail.gmail.com"
type="cite">
<div class="gmail_quote">
<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>There is one thing both the original paper, the original
MSCP implementation did (too bad the links to this point to <a
moz-do-not-send="true" 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>
</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. The LLVM development documentation suggests that new
work be committed piecemeal over time.<br>
<br>
LLVM does have an optimization pass, -instcombine, which will delete
unused induction variables. I recommend that -instcombine be run
after OSR. 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.<br>
<br>
thanks for your comments,<br>
Brian West<br>
<br>
</body>
</html>