[LLVMdev] "Graphite" for llvm

[ether]

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 Graphite 
hows 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