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

Eli Friedman <eli.friedman <at> gmail.com> writes:
 > >> > I did not mention in the original email (and should have)
that
OSR needs
 > >> > -instcombine to be run after it for cleanup. Also -licm, 
-reassociate, -gvn
 > >> > and -sccp can be enabling optimizations for OSR.
 > >>
 > >> Hmm... perhaps that could be partially fixed using the
InstSimplify
 > >> infrastructure.
 > >
 > > OSR can produce induction variables that are not used.  
-instcombine finds the
 > > unused induction variables and deletes them (which is super cool 
btw :)).  I am
 > > unsure if InstructionSimplify can fix that.
 >
 > Oh... no, you would need instcombine for that.  However, how hard
 > would it be to just avoid creating unused induction variables?
 > instcombine doesn't normally run after LSR.


Short answer is no.

The OSR adds new induction variables based on existing variables.  That 
way, we
can go from induction variable i to induction variable &a[long(i)] (aka, a +
long(i)).   There may be some intermediate induction variables that 
assist in i
reaching (a + long(i)), like long(i), e.g.

i -> long(i) -> (a + long(i))

after creating (a + long(i)), induction variable long(i) may be unused,
depending on whether long(i) can participate in creating an another 
induction
variable. Thus, it is not known until the algorithm is done, which of the
created induction variables are unused.

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.

FWIW2 our intent in creating OSR was not to replace LSR, just provide an
alternative strength reduction optimization.


 > -Eli


Brian

On Fri, Oct 29, 2010 at 11:18 AM, Brian West <bnwest at rice.edu>
wrote:
> Eli Friedman <eli.friedman <at> gmail.com> writes:
>> >> > I did not mention in the original email (and should have)
that OSR
>> >> > needs
>> >> > -instcombine to be run after it for cleanup. Also -licm,
>> >> > -reassociate, -gvn
>> >> > and -sccp can be enabling optimizations for OSR.
>> >>
>> >> Hmm... perhaps that could be partially fixed using the
InstSimplify
>> >> infrastructure.
>> >
>> > OSR can produce induction variables that are not used.
 -instcombine
>> > finds the
>> > unused induction variables and deletes them (which is super cool
btw
>> > :)).  I am
>> > unsure if InstructionSimplify can fix that.
>>
>> Oh... no, you would need instcombine for that.  However, how hard
>> would it be to just avoid creating unused induction variables?
>> instcombine doesn't normally run after LSR.
>
>
> Short answer is no.
>
> The OSR adds new induction variables based on existing variables.  That
way,
> we
> can go from induction variable i to induction variable &a[long(i)]
(aka, a +
> long(i)).   There may be some intermediate induction variables that assist
> in i
> reaching (a + long(i)), like long(i), e.g.
>
> i -> long(i) -> (a + long(i))
>
> after creating (a + long(i)), induction variable long(i) may be unused,
> depending on whether long(i) can participate in creating an another
> induction
> variable. Thus, it is not known until the algorithm is done, which of the
> created induction variables are unused.
Sure, but you know which induction variables you created; you can just
zap the unused ones at the end of the pass, no?
> 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?

-Eli

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