Hi ether, On 12/26/09 13:06, ether zhhb wrote:> hi, > > dose anyone going/planning to add something like > Graphite(http://gcc.gnu.org/wiki/Graphite) in gcc to llvm(or that > should be implement at the level of clang?)?I already looked into implementing something like Graphite for LLVM. However just recently, so I have not released any code yet. As soon as some code is available I will post patches. Anybody who wants to work on the polyhedral model in LLVM, is invited to the Graphite mailing list, so we can share ideas. Here some information about graphite like optimizations in LLVM. A short introduction to the current state of GCC/Graphite: ----------------------------------------------------------------------- Graphite is a project in GCC that uses a mathematical representation, the polytop model, to represent and transform loops and other control flow structures. Using an abstract representation it is possible to reason about transformations in a more general way and to use highly optimized linear programming libraries to figure out the optimal loop structures. These transformations can be used to do constant propagation through arrays, remove dead loop iterations, optimize loops for cache locality, optimize arrays, apply advanced automatic parallelization, or to drive vectorization. The current state of Graphite and the polyhedral model in general is at the moment in between research and production. Over the last 20 years there has been a lot of research in the area of the polyhedral model, however it was never used in real world compilers (I know of) until Sebastian Pop started to implement the required analysis and Graphite itself. Graphite has shown that it is possible to convert a low level imperative language into the polyhedral model and generate working code back from it with reasonable afford. Now several people from INRIA, IBM, AMD, the University of Passau and China are working on making the optimizations that have been found during the 20 years of research available to GCC. The latest news about Graphite, will be presented on the GROW workshop 2010 in Pisa by Konrad Trifunovic. [Advertisement end] ;-) ----------------------------------------------------------------------- A general plan to implement polyhedral transformations in LLVM: 1. The identity transformation (LLVM->polyedral->LLVM) ===================================================== Create the polyhedral representation of the LLVM IR, do nothing with it, and generate LLVM IR from the polyhedral representation. (Enough to attach external optimizers) 1.1 Detect regions 1.2 Translate LLVM IR to polyhedral model ----------------------------------------- The first step will be to analyze the LLVM intermediate language and extract control flow regions that can be analyzed using the polyhedral model. This is mainly based on the scalar evolution analysis and should be more or less like the detection in Graphite. One point I do not yet fully understand is how to get array access functions from the LLVM-IR. (Probably based on getElementPtr) Another question is which polyhedral library can be used inside LLVM. One option would be ISL from Sven Verdoolaege (LGPL) another the PPL from Roberto Bagnara (GPLv3). 1.3 Generate LLVM IR from polyhedral mode ----------------------------------------- For code generation the CLooG/isl library can be used. It is LGPL licensed. Sven will also work on an CLooG using the PPL, so this could also be an option. 2. Optimize on the polyhedral representation =========================================== 2.1 Use external optimizers --------------------------- The polyhedral loop description is simple and not compiler depended. Therefore external tools like LooPo (automatic parallelization), Pluto (optimization in general) or even Graphite might be used to optimize code. This could give a first impression what to expect from the polyhedral model in LLVM. There are also affords to establish an interchangeable polyhedral format (scoplib - Louis-Noel Pouchet) and to generate a polyhedral compilation package. These will allow to share/exchange optimizations between different compilers and research tools. Furthermore an external interface will enable researchers to use LLVM for their work on polyhedral optimizations. This might be useful as there is no polyhedral compiler for any dynamic language yet. Also recent work on optimizing for GPUs has started in the polyhedral community, so the LLVM OpenCL implementation might be interesting too. 2.2 Implement optimizations in LLVM ----------------------------------- Useful optimizations could be imported into / rewritten in LLVM. For optimizations that transfrom the LLVM-IR like vectorization or automatic parallelization at least some part of the optimizations has to be in LLVM anyway. This is just a rough overview. If anybody is interested in working on any of these topics, as mentioned above, I would be glad to help. Enjoy your holidays Tobi P.S.: I do not see any reason implement this in Clang, the LLVM IR is the right place to do this.
hi Tobi , that sounds greate :D On 2009-12-27 5:43, Tobias Grosser wrote:> I already looked into implementing something like Graphite for LLVM. > However just recently, so I have not released any code yet. As soon as > some code is available I will post patches.whats its status? do you need any help?> A general plan to implement polyhedral transformations in LLVM: > > 1. The identity transformation (LLVM->polyedral->LLVM) > =====================================================> > Create the polyhedral representation of the LLVM IR, do nothing with > it, and generate LLVM IR from the polyhedral representation. (Enough > to attach external optimizers) > > 1.1 Detect regions > 1.2 Translate LLVM IR to polyhedral model > ----------------------------------------- > > The first step will be to analyze the LLVM intermediate language and > extract control flow regions that can be analyzed using the polyhedral > model. This is mainly based on the scalar evolution analysis and > should be more or less like the detection in Graphite. > One point I do not yet fully understand is how to get array access > functions from the LLVM-IR. (Probably based on getElementPtr)as i know, getElementPtr combine the base pointer and the offset to generate the pointer to the given element, likeļ¼ &(b[i]) ==> %8 = getelementptr i32* %b, i32 %i.03 ;1-dimension and &(c[i][j]) ==> %4 = getelementptr [4 x i32]* %c, i32 %i.0.reg2mem.0.ph.ph, i32 %j.0.reg2mem.0.ph ;2-dimension so maybe you could check the non-pointer operand of the getelementptr instructrion.> Another question is which polyhedral library can be used inside LLVM. > One option would be ISL from Sven Verdoolaege (LGPL) another the PPL > from Roberto Bagnara (GPLv3). > > 1.3 Generate LLVM IR from polyhedral mode > ----------------------------------------- > > For code generation the CLooG/isl library can be used. It is LGPL > licensed. Sven will also work on an CLooG using the PPL, so this could > also be an option. > > 2. Optimize on the polyhedral representation > ===========================================> > 2.1 Use external optimizers > --------------------------- > > The polyhedral loop description is simple and not compiler depended. > Therefore external tools like LooPo (automatic parallelization), > Pluto (optimization in general)i had contacted the author a week ago, and if we use it, we need a IR generator in llvm side to extract SCoP, and the corresponding parser in Pluto side that read, then a backend for cloog and the corresponding in parser llvm that read those stuff back to llvm. :)> or even Graphitehows the statue of PCP? could us just use the PCP language with annotation?> might be used to optimize code. This could give a first impression > what to expect from the polyhedral model in LLVM. > > There are also affords to establish an interchangeable polyhedral > format (scoplib - Louis-Noel Pouchet) and to generate a polyhedral > compilation package. These will allow to share/exchange optimizations > between different compilers and research tools. > > Furthermore an external interface will enable researchers to use LLVM > for their work on polyhedral optimizations. This might be useful as > there is no polyhedral compiler for any dynamic language yet. Also > recent work on optimizing for GPUs has started in the polyhedral > community, so the LLVM OpenCL implementation might be interesting too.if that targeting some entertainment application instead of scientific computing, implement the polyhedral framework beyond the llvm "support" and "system" library, to allow those thing run as native windows application is a good idea, i think.> > 2.2 Implement optimizations in LLVM > ----------------------------------- > > Useful optimizations could be imported into / rewritten in LLVM. For > optimizations that transfrom the LLVM-IR like vectorization or > automatic parallelization at least some part of the optimizations has > to be in LLVM anyway.the information that compute in polyhedral framework such like iteration domain and affine schedule may all llvm to do some interesting optimization like generate stream processing code from normal c code (and to optimize pointer access boundary check?)> > Enjoy your holidays >the same to you guys :) best regards --ether
ether wrote:>> The polyhedral loop description is simple and not compiler depended. >> Therefore external tools like LooPo (automatic parallelization), Pluto >> (optimization in general) > i had contacted the author a week ago, and if we use it, we need a IR > generator in llvm side to extract SCoP, and the corresponding parser in > Pluto side that read, then a backend for cloog and the corresponding in > parser llvm that read those stuff back to llvm. :) >> or even Graphite > hows the statue of PCP? could us just use the PCP language with annotation?Hi all, PCP is only partially implemented: conversion out of PCP to Graphite is not implemented, but the existing code would definitely help anybody working in interfacing other tools with PCP. The main people to contact are "Sjodin, Jan" <Jan.Sjodin at amd.com> Sebastian Pop <sebpop at gmail.com> Work on PCP has stalled because Jan has left for another group. In the hort term, Tobias is right that the best way to interface tools is to use the scoplib format and library from Louis-Noel Pouchet (PoCC). In any case, work on either PCP or scoplib will be beneficial. The community of polyhedral compilation experts is small, and its openly available output is already diminished by two proprietary development projects at IBM and Reservoir Labs. I strongly wish that any effort within LLVM will be wise enough to join forces with Graphite :-) Albert
hi Tobi, i just added the Poly library(http://wiki.llvm.org/Polyhedral_optimization_framework) to llvm build system, which only contain a toy pass "Poly". i think we could add the polyhedral optimization stuff in to this library. it was test under cmake+visual studio 2009, and i also add the library build rule to MAKEFILEs, but not sure if it work under linux/cygwin/mac, sorry. hope this help best regards --ether On 2009-12-27 5:43, Tobias Grosser wrote:> Hi ether, > > On 12/26/09 13:06, ether zhhb wrote: >> hi, >> >> dose anyone going/planning to add something like >> Graphite(http://gcc.gnu.org/wiki/Graphite) in gcc to llvm(or that >> should be implement at the level of clang?)? > > I already looked into implementing something like Graphite for LLVM. > However just recently, so I have not released any code yet. As soon as > some code is available I will post patches. > > Anybody who wants to work on the polyhedral model in LLVM, is invited > to the Graphite mailing list, so we can share ideas. > > Here some information about graphite like optimizations in LLVM. > > A short introduction to the current state of GCC/Graphite: > ----------------------------------------------------------------------- > Graphite is a project in GCC that uses a mathematical representation, > the polytop model, to represent and transform loops and other control > flow structures. Using an abstract representation it is possible to > reason about transformations in a more general way and to use highly > optimized linear programming libraries to figure out the optimal loop > structures. These transformations can be used to do constant > propagation through arrays, remove dead loop iterations, optimize > loops for cache locality, optimize arrays, apply advanced automatic > parallelization, or to drive vectorization. > > The current state of Graphite and the polyhedral model in general is > at the moment in between research and production. Over the last 20 > years there has been a lot of research in the area of the polyhedral > model, however it was never used in real world compilers (I know of) > until Sebastian Pop started to implement the required analysis and > Graphite itself. Graphite has shown that it is possible to convert a > low level imperative language into the polyhedral model and generate > working code back from it with reasonable afford. Now several people > from INRIA, IBM, AMD, the University of Passau and China are working > on making the optimizations that have been found during the 20 years > of research available to GCC. The latest news about Graphite, will be > presented on the GROW workshop 2010 in Pisa by Konrad Trifunovic. > > [Advertisement end] ;-) > ----------------------------------------------------------------------- > > > A general plan to implement polyhedral transformations in LLVM: > > 1. The identity transformation (LLVM->polyedral->LLVM) > =====================================================> > Create the polyhedral representation of the LLVM IR, do nothing with > it, and generate LLVM IR from the polyhedral representation. (Enough > to attach external optimizers) > > 1.1 Detect regions > 1.2 Translate LLVM IR to polyhedral model > ----------------------------------------- > > The first step will be to analyze the LLVM intermediate language and > extract control flow regions that can be analyzed using the polyhedral > model. This is mainly based on the scalar evolution analysis and > should be more or less like the detection in Graphite. > One point I do not yet fully understand is how to get array access > functions from the LLVM-IR. (Probably based on getElementPtr) > > Another question is which polyhedral library can be used inside LLVM. > One option would be ISL from Sven Verdoolaege (LGPL) another the PPL > from Roberto Bagnara (GPLv3). > > 1.3 Generate LLVM IR from polyhedral mode > ----------------------------------------- > > For code generation the CLooG/isl library can be used. It is LGPL > licensed. Sven will also work on an CLooG using the PPL, so this could > also be an option. > > 2. Optimize on the polyhedral representation > ===========================================> > 2.1 Use external optimizers > --------------------------- > > The polyhedral loop description is simple and not compiler depended. > Therefore external tools like LooPo (automatic parallelization), Pluto > (optimization in general) or even Graphite might be used to optimize > code. This could give a first impression what to expect from the > polyhedral model in LLVM. > > There are also affords to establish an interchangeable polyhedral > format (scoplib - Louis-Noel Pouchet) and to generate a polyhedral > compilation package. These will allow to share/exchange optimizations > between different compilers and research tools. > > Furthermore an external interface will enable researchers to use LLVM > for their work on polyhedral optimizations. This might be useful as > there is no polyhedral compiler for any dynamic language yet. Also > recent work on optimizing for GPUs has started in the polyhedral > community, so the LLVM OpenCL implementation might be interesting too. > > 2.2 Implement optimizations in LLVM > ----------------------------------- > > Useful optimizations could be imported into / rewritten in LLVM. For > optimizations that transfrom the LLVM-IR like vectorization or > automatic parallelization at least some part of the optimizations has > to be in LLVM anyway. > > This is just a rough overview. If anybody is interested in working on > any of these topics, as mentioned above, I would be glad to help. > > Enjoy your holidays > > Tobi > > P.S.: I do not see any reason implement this in Clang, the LLVM IR is > the right place to do this. > > > >-------------- next part -------------- An embedded and charset-unspecified text was scrubbed... Name: polylib.patch URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100105/b0705a20/attachment.ksh>