hi Tobi ,
that sounds greate
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