[LLVMdev] "Graphite" for llvm

[Tobias Grosser]

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.