CLooG is a PolyLib plugin providing a software and a library generating
loops for scanning Z-polyhedra.
That is, it finds the code or pseudo-code with which each integral point of one
or more parameterized polyhedra, or union of parameterized polyhedra
is reached. While the user has full control on generated code quality, CLooG is
designed to avoid control overhead and to produce a very effective code. The
heart of the loop generation process is the Quilleré et al.'s algorithm
[4] extended and improved by the works exposed in
[2]. This technique generates loop levels by projecting
the polyhedra onto the corresponding dimension. Then by splitting the projection
into disjoint polyhedra and sorting the resulting polyhedra in order to
respect the lexicographic order. Lastly, it recursively generates loop
nests that scan each polyhedron.
Polyhedral domains to scan
Scanning code optimized in size
Scanning code optimized in guards
for (i=1;i<=8;i++) {
for (j=i-1;j<=7;j++) {
S1 ;
}
if ((i<=6)&&(i>=2)) {
for (j=0;j<=4;j++) {
S2 ;
}
}
}
for (j=0;j<=7;j++) {
S1(i=1) ;
}
for (i=2;i<=5;i++) {
for (j=0;j<=i-2;j++) {
S2 ;
}
for (j=i-1;j<=4;j++) {
S1 ;
S2 ;
}
for (j=5;j<=7;j++) {
S1 ;
}
}
for (j=0;j<=4;j++) {
S2(i=6) ;
}
for (j=5;j<=7;j++) {
S1(i=6) ;
}
for (i=7;i<=8;i++) {
for (j=i-1;j<=7;j++) {
S1 ;
}
}
This generator is a part of the Chunky project, a research tool for data
locality improvement. It is designed to be also the back-end of automatic
parallelizers like PAF. Then it is very 'compilable code oriented' and
provides program transformation facilities.
The current version is still under evaluation, and there is no guarantee that
the upward compatibility will be respected. A lot of reports are needed to
freeze the library API and the input file shape. So you are very welcome and
encouraged to send me reports
on bugs, wishes, critics, comments, suggestions or successful experiences.
Requirements
To successfully install CLooG, you need firstly to install PolyLib version 5.0
or above. You only need to build the 32 or 64 bits version. Polylib can be
downloaded freely at
http://icps.u-strasbg.fr/PolyLib/
or http://www.irisa.fr/polylib/.
Once downloaded and unpacked, you can compile it by typing the following
commands:
./configure
make
And as root: make install
CLooG makes intensive calls to polyhedral operations, and PolyLib functions do
the job. Polylib is a free library written in C for the manipulation of
polyhedra. The library is operating on objects like vectors, matrices, lattices,
polyhedra, Z-polyhedra, unions of polyhedra and a lot of other intermediary
structures. It provides functions for all the important operations on these
structures [5].
0.12.1 -> 0.12.2 : New option -cpp for pseudo-compilable code (nice idea
from Armin Größlinger from the LooPo Team, see the manual), automatic
translation of data structures to LoopGen or Omega
CodeGen input files. Stride support improvements.
Some minor fixing.
0.12 -> 0.12.1 : Choice by configure of the 32 or 64 bits version (64
is the default choice if PolyLib64 is present, 32
otherwise), many thanks to Sven Verdoolaege !
Optimizations with pattern matching: up to a factor 2
with CLooG benchmarks. Some minor fixing.
The user's guide [2] shortly presents Quilleré et al.'s
algorithm [4] and some useful background to understand how
the code generator works. It shows in detail
how to write the input file for the CLooG software and how to set its options
thanks to a lot of examples. It presents the CLooG library, its data
structures and its various functions. It explains how to compile, install and
uninstall it. Lastly, it discusses ongoing works.
A copy of this document is provided in the doc/ subdirectory in the standard
distribution. It would be fair to refer this technical report
[3] or better, the paper about extending and improving the
Quilleré et al.'s algorithm [2] in any publication
resulting from the use of this software or its library.
The PolyLib mailing-list:
Announcements on CLooG are sent to the PolyLib mailing-list. To join the list,
send an email to sympa@u-strasbg.fr
containing the following message:
SUB PolyLib firstname lastname organization.
You will then be asked to confirm your subscription by replying to the returned
message. A forum group of the
Polylib
community was set up too. You may
subscribe
to the group in order to be able to have full contact with the Polylib world.
The CLooG-Benchs are a set of real-life code generation problems from
various programs. These problems want to be representative of the high level
code generation work in the polyhedral model. We choose to enumerate the
code re-generation specifications of all the static control parts of several
well known benchmarks (the extraction work has been done by
WRAP-IT).
The problems can be as simple as few statements without
any loop, and as hard as more than a thousand statements having several
surrounding loops. The goal of this problem library is to help to make accurate
code generation tool evaluations.
Code generation for scanning Z-polyhedron is a well known problem.
It was first solved by Ancourt and Irigoin for the simple
case of Z-polyhedra with unit lattice [1]. They used the
Fourier-Motzkin elimination technique to compute loop bounds. Some code
generators descended from this technique:
For complex situation, the best solution is the Quilleré et al. one
[4].
This technique generates each loop level by separating the polyhedra until
they are disjoint on the current dimension, then recursively generating
loop nests that scan each of them. Code generators using this
technique are:
[1]
C. Ancourt and F. Irigoin. Scanning polyhedra with do loops. In 3rd ACM
SIGPLAN Symposium on Principles and Practice of Parallel Programming,
pages 39-50, june 1991.
[bibtex]
[2]
C. Bastoul.
Efficient code generation for automatic parallelization and optimization.
ISPDC'03 IEEE International Symposium on Parallel and Distributed Computing,
pages 23-30, Ljubljana, october 2003.
[pdf]
[bibtex]
[3]
C. Bastoul. Generating loops for scanning polyhedra.
Technical Report 2002/23, PRiSM, Versailles University, 2002.
[postscript]
[bibtex]
[Home]
[Getting CLooG]
[Documentation]
[CLooG-Benchs]
[Code Generation Links]
[References]
