[LLVMdev] Landing my new development on the trunk ...

[Daniel Berlin]

>
> A big downside of the current LSR algorithm is it's slow.  I had initially
> hoped that some of the heuristics would protect it better, but the problem
> is
> more complex than I had expected.  I haven't done any measurements,
> but it's likely that OSR is faster, which may interest some people
> regardless
> of how the output compares.
>


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)
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.

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.

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.


So i think you may see good things if you took the OSR code and used it as a
basis for LSR.

There is one thing both the original paper, the original MSCP implementation
did (too bad the links to this point to ftp.cs.rice.edu, 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.

--Dan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20101114/09479798/attachment.html>