[LLVMdev] "Graphite" for llvm

[ether]

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>