llvm dev - Dec 2009 - [LLVMdev] "Graphite" for llvm

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

Tobias Grosser wrote:
> 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.
By the way, Konrad Trifunovic is interested (for his own research) to 
improve on the current read/write capabilities of Graphite to process 
the full scoplib format instead. Dealing with iteration domain and 
schedule/scattering is easy, but to process array subscripts will 
require more work. We will keep you informed of the progresses on the 
Graphite mailing list, but collaboration outside the Graphities is welcome.

Albert

On Dec 28, 2009, at 4:24 PM, Tobias Grosser wrote:
> 
> 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.
If you want to know how the address is calculated as a function of
each enclosing loop, ScalarEvolution should be quite usable for
multiple dimensions. This is represented with an add-recurrence
with another add-recurrence as its "start" operand. For example:

  for (i=0; i<m; ++i)    // X
    for (j=0; j<n; ++j)  // Y
      A[i][j];

The store address has this expression:

  {{A,+,sizeof(double)*n}<X>,+,sizeof(double)}<Y>

This says that the value starts at A, steps by sizeof(double)*n
(address units) with the iteration of loop X, and steps by
sizeof(double) with the iteration of loop Y.

However, if you want to recognize this as a high-level array
reference on A with subscripts "i" and then "j", there are
some
missing pieces.

On a related note, analyzing getelementptr yourself directly is
doable, but there are several major complications. Using a helper
library such as ScalarEvolution can protect you from many
low-level artifacts (though not all).

Dan

Dear colleagues,

Happy New Year!

Just wanted to mention that since cTuning community is interested in 
performance/code size/power tuning using empirical feedback-directed techniques
using different compilers including GCC and LLVM, so just wanted to mention that
we would be interested to add support to fine-grain optimizations from GRAPHITE
to Interactive Compilation Interface at some point at the beginning
of this year to be able to use cTuning optimization framework directly 
and share optimization cases with the community. 

Will keep in touch,
Grigori

> -----Original Message-----
> From: gcc-graphite at googlegroups.com [mailto:gcc-graphite at
googlegroups.com] On Behalf Of Albert
> Cohen
> Sent: Tuesday, December 29, 2009 1:12 PM
> To: Tobias Grosser
> Cc: ether; LLVM Developers Mailing List; GCC GRAPHITE; loopo at
infosun.fim.uni-passau.de
> Subject: Re: [LLVMdev] "Graphite" for llvm
> 
> Tobias Grosser wrote:
> > 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.
> 
> By the way, Konrad Trifunovic is interested (for his own research) to
> improve on the current read/write capabilities of Graphite to process
> the full scoplib format instead. Dealing with iteration domain and
> schedule/scattering is easy, but to process array subscripts will
> require more work. We will keep you informed of the progresses on the
> Graphite mailing list, but collaboration outside the Graphities is welcome.
> 
> Albert