[LLVMdev] "Graphite" for llvm

[Tobias Grosser]

On 12/27/09 10:18, ether wrote:
> 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?

Very recently started. That's why I did not talk about this on my own.

However help is always needed. As already said. Getting affine access 
functions from the memory accesses would be a big 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.

Probably. I think for single dimensional arrays it will not be too 
difficult using scalar evolution to get the access functions. I think 
multi dimensional arrays will get complicated.

>> 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. :)

The way to go is the scoplib format (propably extended by quantified 
variables). This format could be extracted from graphite easily and 
could also be created in LLVM.
What we need to get back into LLVM is only the new optimized schedule 
described e.g. as cloog like scattering functions. These can be parsed 
easily. The real code generation could be done internally, so it is not 
necessary to parse the generated from external tools.

>> or even Graphite
> hows the statue of PCP? could us just use the PCP language with annotation?
See Jan's mail.
The first steps we have to take are not yet dependend on PCP, later on 
it might be useful for debugging and better readability of the test cases.

>> 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.
Sure.

>>
>> 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?)
Yes

See you

Tobi