This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Question about polyhedral model and solver used in GRAPHITE


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]