llvm dev - Nov 2010 - [LLVMdev] Landing my new development on the trunk ...

On 10/29/10 1:26 PM, Eli Friedman wrote:
> Sure, but you know which induction variables you created; you can just
> zap the unused ones at the end of the pass, no?
This is feasible.  We would have to collect more information during OSR 
proper pass and add logic to cleanup at the end.
>> FWIW I noticed that other optimizations (as seen in StandardPasses.h)
are
>> followed by -instcombine for cleanup. I thought requiring or suggesting
>> running
>> -instcombine after -osr would be SOP.
>
> Strength reduction is sort of a special case; it runs extremely late
> because it interferes with other optimizations.
>
>> FWIW2 our intent in creating OSR was not to replace LSR, just provide
an
>> alternative strength reduction optimization.
>
> Sure, but if it can't be used as an alternative to LSR, how would it be
used?
The PACE project intends to use LLVM to perform lower level 
optimizations in its compiler.  OSR would be another optimization that 
it would have in its bag of tricks.  Remember that OSR finds reductions 
that LSR does not.

For code generation, the PACE compiler can use the LLVM C Backend (plus 
the native compiler) or the LLVM native backend (if available) or just 
the native compiler.  Thus, when the PACE compiler uses LLVM, LSR may 
not be run.

I suspect that there may be other LLVM C Backend users who could use OSR 
as well, right?
> -Eli
Brian

On Oct 29, 2010, at 12:20 PM, Brian West wrote:
> On 10/29/10 1:26 PM, Eli Friedman wrote:
>> Sure, but you know which induction variables you created; you can just
>> zap the unused ones at the end of the pass, no?
> This is feasible.  We would have to collect more information during OSR 
> proper pass and add logic to cleanup at the end.
> 
>>> FWIW I noticed that other optimizations (as seen in
StandardPasses.h) are
>>> followed by -instcombine for cleanup. I thought requiring or
suggesting
>>> running
>>> -instcombine after -osr would be SOP.
>> 
>> Strength reduction is sort of a special case; it runs extremely late
>> because it interferes with other optimizations.
>> 
>>> FWIW2 our intent in creating OSR was not to replace LSR, just
provide an
>>> alternative strength reduction optimization.
>> 
>> Sure, but if it can't be used as an alternative to LSR, how would
it be used?
> 
> The PACE project intends to use LLVM to perform lower level 
> optimizations in its compiler.  OSR would be another optimization that 
> it would have in its bag of tricks.  Remember that OSR finds reductions 
> that LSR does not.
LSR's primary goal is to reduce integer register pressure, with
strength reduction being just one of its available tools.  Also, it aggressively
uses the target addressing modes (which is awkward in LLVM IR, since the
addressing modes aren't explicit, but that's another story).  Without
a Target, it currently assumes it can use register+register addressing,
which is probably pretty bad when used with the C backend.  We
can probably fix this, if you're interested.

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.
> For code generation, the PACE compiler can use the LLVM C Backend (plus 
> the native compiler) or the LLVM native backend (if available) or just 
> the native compiler.  Thus, when the PACE compiler uses LLVM, LSR may 
> not be run.
LSR can be run from opt, though as I mentioned above the current
target-independent addressing mode assumptions may need to be tuned.
> I suspect that there may be other LLVM C Backend users who could use OSR 
> as well, right?
Not many people use the C backend.

Dan

Dan Gohman <gohman at apple.com> writes:
>> I suspect that there may be other LLVM C Backend users who could use
OSR
>> as well, right?
>
> Not many people use the C backend.
Au contraire (just had to jump in).  :)  Bugpoint uses cbe so there are
at least some people like me that use it to debug compiler problems.
I use it when there is no "good" llc to compare to, which
unfortunately
happens more often than not here.

                           -Dave

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