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?> -EliBrian
Apparently Analagous Threads
- [LLVMdev] Landing my new development on the trunk ...
- [LLVMdev] Landing my new development on the trunk ...
- [LLVMdev] Landing my new development on the trunk ...
- [LLVMdev] Landing my new development on the trunk ...
- [LLVMdev] Landing my new development on the trunk ...