Vikram S. Adve wrote:>> The only way to make preselection or lowermultidimrefs work is to >> duplication all of the knowledge of how the instruction selector will >> select the code (e.g. the advice about allowing constant indices to >> be grouped together). > > > This is why you need a separate, low-level optimization framework - > the kind you were describing. > > --Vikram > http://www.cs.uiuc.edu/~vadve > http://llvm.cs.uiuc.edu/Sounds reasonable to me. It seems to me it would be best if LSR was part of the low-level optimization framework, otherwise it would be forced to duplicate too much work on its own. Also, some of what LSR needs to decide is architecture dependent. For example, it may not want to strength reduce a multiplication which multiplies by a small power of two, as this is handled by addressing modes on some architectures. There is still probably a need for a mid-level LSR that handles the explicit multiplications, divisions, etc...
On Feb 22, 2005, at 10:16 AM, Jeff Cohen wrote:> Vikram S. Adve wrote: > >>> The only way to make preselection or lowermultidimrefs work is to >>> duplication all of the knowledge of how the instruction selector >>> will select the code (e.g. the advice about allowing constant >>> indices to be grouped together). >> >> >> This is why you need a separate, low-level optimization framework - >> the kind you were describing. >> >> --Vikram >> http://www.cs.uiuc.edu/~vadve >> http://llvm.cs.uiuc.edu/ > > Sounds reasonable to me. It seems to me it would be best if LSR was > part of the low-level optimization framework, otherwise it would be > forced to duplicate too much work on its own. > > Also, some of what LSR needs to decide is architecture dependent. For > example, it may not want to strength reduce a multiplication which > multiplies by a small power of two, as this is handled by addressing > modes on some architectures.I agree. I would say that the only part of this problem (array indexing) that is nearly always important is decomposing multidimensional array refs into individual index operations so that LICM in pariticular can hoist each component to the appropriate loop level. Everything else, including GCSE and strength reduction, is somewhat sensitive to target parameters like register set size and addressing modes. --Vikram> > There is still probably a need for a mid-level LSR that handles the > explicit multiplications, divisions, etc... > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://mail.cs.uiuc.edu/mailman/listinfo/llvmdev
On Tue, 22 Feb 2005, Jeff Cohen wrote:> Sounds reasonable to me. It seems to me it would be best if LSR was part of > the low-level optimization framework, otherwise it would be forced to > duplicate too much work on its own. > > There is still probably a need for a mid-level LSR that handles the explicit > multiplications, divisions, etc...You're right: strength reduction is the #1 gray area between the LLVM level and the code generator level. Doing it in the backend has several nice advantages (e.g. handling explicit multiplies and gep instructions is same analysis, you have a better understanding of register pressure, etc), but doing it at the llvm level also has advantages (higher level information is available, the xform is faster and cheaper to do, etc). Currently we also have the infrastructure available to do the transformation on the LLVM level, but don't really have it available in the code generator.> Also, some of what LSR needs to decide is architecture dependent. For > example, it may not want to strength reduce a multiplication which multiplies > by a small power of two, as this is handled by addressing modes on some > architectures.You're right. However, we can choose to expose information about target parameters through the Target* interfaces that llvm->llvm passes can use as well, so at least this aspect is not a killer issue. -Chris -- http://nondot.org/sabre/ http://llvm.cs.uiuc.edu/
Chris Lattner wrote:> On Tue, 22 Feb 2005, Jeff Cohen wrote: > >> Also, some of what LSR needs to decide is architecture dependent. >> For example, it may not want to strength reduce a multiplication >> which multiplies by a small power of two, as this is handled by >> addressing modes on some architectures. > > > You're right. However, we can choose to expose information about > target parameters through the Target* interfaces that llvm->llvm > passes can use as well, so at least this aspect is not a killer issue. > > -ChrisThe only problem I have with this is that bytecode ought to be platform independent. If I compile on an X86 with complex addressing modes, then take the bytecode and translate it to machine code on some RISC, that's not fair to the RISC. Or vice versa. But then this might already be a problem with other optimizations so it might not really introduce anything new (does it?). Or delay all optimization until machine code generation time.