Chris, Chris Lattner wrote:> I would love to see any progress in this area. It is clearly an > important thing to tackle, and it is blocking other interesting > improvements in the code generator. It would also allow us to > eliminate a significant amount of weirdness that exists to hack around > this (e.g. switch lowering).we've been working on a whole-function instruction selector here at the vienna university of technology in the recent past. our approach considers ssa graphs and is based on a problem transformation to a specialized quadratic assignment problem (pbqp). in contrast to previous work [1], the technique is flexible enough to cope with general DAG patterns such as pre/postincrement or divmod patterns. the instruction selector is a drop-in replacement for the original implementation (llvm 2.1). we've used the ARM backend for evaluation and obtained quite encouraging results: speedups are up to 10% for SPEC/Mibench and up to 57% for simple loop kernels. the compile time increase is about a factor of 2. the paper has been accepted for this year's LCTES conference (june 12-13, tucson, az). i'm afraid i cannot post it on the list but i'm happy to send a preliminary version to anybody who's interested. the implementation is not yet as efficient as it could be (e.g., we maintain an additional datastructure for the ssa graph along with the selection DAG) and i'm afraid there are licensing issues that do not allow me to directly post or contribute the code. however, i'm happy to share further experimental results and discuss the approach in case somebody is interested. - dietmar [1] Erik Eckstein, Oliver König and Bernhard Scholz Code Instruction Selection Based on SSA-Graphs SCOPES 2003 http://springerlink.metapress.com/content/83cj0ebgtm998hj8 -- --------------------------------------------------------------------- Dietmar Ebner CD Laboratory - Compilation Techniques for Embedded Processors Institut fuer Computersprachen E: ebner at complang.tuwien.ac.at Technische Universitaet Wien F: (+431) 58801-18598 Argentinierstrasse 8 / E1851 T: (+431) 58801-58521 1040 Wien, Austria W: www.complang.tuwien.ac.at/cd/ebner
On Mar 25, 2008, at 9:40 AM, Dietmar Ebner wrote:> Chris, > > Chris Lattner wrote: >> I would love to see any progress in this area. It is clearly an >> important thing to tackle, and it is blocking other interesting >> improvements in the code generator. It would also allow us to >> eliminate a significant amount of weirdness that exists to hack >> around >> this (e.g. switch lowering). > we've been working on a whole-function instruction selector here at > the > vienna university of technology in the recent past. our approach > considers ssa graphs and is based on a problem transformation to a > specialized quadratic assignment problem (pbqp). in contrast to > previous > work [1], the technique is flexible enough to cope with general DAG > patterns such as pre/postincrement or divmod patterns. > > the instruction selector is a drop-in replacement for the original > implementation (llvm 2.1). we've used the ARM backend for evaluation > and > obtained quite encouraging results: speedups are up to 10% for > SPEC/Mibench and up to 57% for simple loop kernels. the compile time > increase is about a factor of 2.Very nice!> > > the paper has been accepted for this year's LCTES conference (june > 12-13, tucson, az). i'm afraid i cannot post it on the list but i'm > happy to send a preliminary version to anybody who's interested. > > the implementation is not yet as efficient as it could be (e.g., we > maintain an additional datastructure for the ssa graph along with the > selection DAG) and i'm afraid there are licensing issues that do not > allow me to directly post or contribute the code. however, i'm happy > to > share further experimental results and discuss the approach in case > somebody is interested.That's unfortunate. What kind of licensing issues are there? Evan> > > - > dietmar > > > [1] Erik Eckstein, Oliver König and Bernhard Scholz > Code Instruction Selection Based on SSA-Graphs > SCOPES 2003 > http://springerlink.metapress.com/content/83cj0ebgtm998hj8 > > -- > --------------------------------------------------------------------- > Dietmar Ebner > CD Laboratory - Compilation Techniques for Embedded Processors > Institut fuer Computersprachen E: ebner at complang.tuwien.ac.at > Technische Universitaet Wien F: (+431) 58801-18598 > Argentinierstrasse 8 / E1851 T: (+431) 58801-58521 > 1040 Wien, Austria W: www.complang.tuwien.ac.at/cd/ebner > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Evan Cheng wrote:>> the implementation is not yet as efficient as it could be (e.g., we >> maintain an additional datastructure for the ssa graph along with the >> selection DAG) and i'm afraid there are licensing issues that do not >> allow me to directly post or contribute the code. however, i'm happy >> to >> share further experimental results and discuss the approach in case >> somebody is interested. > > That's unfortunate. What kind of licensing issues are there?i'm working in a christian doppler laboratory. projects are funded partially by industry and the developed code "belongs" to the partner company unless they decide to release it. i would have to talk to them and see what i can do. furthermore, there's a generic solver that has been implemented by bernhard scholz (university of sydney) [1]. it's free for research purposes but would have to be re-licensed for llvm. however, the latter would be no problem if you just want to play with it. note that the implementation is pretty stable but sincerely not ready for prime time. several parts would have to be revised and/or replaced and some design decisions would probably be different for a production quality system vs. a research prototype. - dietmar [1] http://www.it.usyd.edu.au/~scholz/pbqp.html -- --------------------------------------------------------------------- Dietmar Ebner CD Laboratory - Compilation Techniques for Embedded Processors Institut fuer Computersprachen E: ebner at complang.tuwien.ac.at Technische Universitaet Wien F: (+431) 58801-18598 Argentinierstrasse 8 / E1851 T: (+431) 58801-58521 1040 Wien, Austria W: www.complang.tuwien.ac.at/cd/ebner
Evan Cheng wrote:> That's unfortunate. What kind of licensing issues are there?i've talked to our supporting company and they agreed to release the code to interested parties. it's not a copyleft license but the code can be used freely for private and research purposes. be warned that the code is merely a prototype implementation and not ready for inclusion in LLVM. it also requires a cost augmented graph grammar. for our ARM implementation, we could derive a basic set of rules directly from the LLVM tablegen description, but additional handwritten rules (e.g., replacing the c++ written address mode selection) were necessary. the implementation has been ported from another private backend which is still evident in some places. if you're still interested in the code, i could prepare a small package to play with along with some useful instructions. if you think that a PBQP based approach would be useful for LLVM and has a chance for inclusion, i would be willing to bring the code in shape and make changes where necessary. - dietmar -- --------------------------------------------------------------------- Dietmar Ebner CD Laboratory - Compilation Techniques for Embedded Processors Institut fuer Computersprachen E: ebner at complang.tuwien.ac.at Technische Universitaet Wien F: (+431) 58801-18598 Argentinierstrasse 8 / E1851 T: (+431) 58801-58521 1040 Wien, Austria W: www.complang.tuwien.ac.at/cd/ebner