Question about polyhedral model and solver used in GRAPHITE

[Tobias Grosser]

On 06/17/2010 10:41 AM, Simone Pellegrini wrote:
> Dear all,
> I was reading one of the first technical reports of GRAPHITE and it
> looks like several libraries have been considered for integration into
> GCC for solving the ILP problem and polyhedral model representation. In
> the document the Omega library, PIP, PolyLib and PPL are mentioned.
>
> I am wondering about which library is actually used in the current
> implementation of the GRAPHITE framework and if possible I would like to
> know the motivations behind this choice. I actually need to build
> dependence analysis on top of a source-to-source compiler and I find
> myself in the 'nightmare' of choosing a suitable library for supporting
> the polyhedral model analysis and transformation.

Hi Simone,

currently we use PPL. At the time we wanted to commit Graphite it was 
the only realistic choice.

The alternative was Polylib. However it was GPLv2 only and there was no 
chance to change the license. (I heard that it was changed recently).
So there was not too much choice.

Furthermore, technically polylib is a very old implementation that has a 
plain interface that is not that easy to understand. Polyhedron are e.g. 
represented as two dimensional matrices.
Also its support for integer polyhedron is limited and sometimes wrong.

On the other hand there is PPL. A nicely developed library, that since 
the most recent release also includes a PIP solver. It has a nice 
constraint based interface, good documentation and is GPLv3 licensed. 
Unfortunately integer polyhedron are not that easy to use in PPL.

Recently there showed up a new library called ISL. It is developed by 
Sven Verdoolaege and is state of the art in terms of integer polyhedron. 
It is plain C and also supports a nice constraint based interface. 
Furthermore it has native support for existentially quantified variables.
It already proved useful in CLooG [1] and is also used in Polly [2] 
because of its liberal LGPL license.

You said you are planning to work on Source to Source compilation, and 
you are going to develop a dependency analysis.

In this case I highly recommend you to check if this is not already 
available. There is candl from Cedric Bastoul that does dependency 
analysis and furthermore ISL has an integrated dependency solver.
You just might want to use it directly.

Furthermore I would be interested in the toolchain you are developing 
and if there is any possibility to integrate it with existing tools.
We are working on an open Polyhedral interchange format called 
openscop/scoplib that will allow different polyhedral tools to 
interchange their data.

So you could e.g. write the frontend/backend and could plug in tools 
supporting SCoPlib.

Currently these tools exist that support SCoPlib:

* Graphite: Frontend/Backend in GCC
* Polly: Frontend/Backend in LLVM
* Clan: C Source frontend
* Candl: Dependency analysis
* Pluto: Integrated toolchain for source to source compilation/

Please ask if you need further information or you want to introduce us 
to your project.

Cheers
Tobi

[1] http://www.cloog.org
[2] http://wiki.llvm.org/Polyhedral_optimization_framework