Switch from matrix to relation data structure

[openscop.git] / doc / clan.texi

\input texinfo
@c %
@c %  /**-----------------------------------------------------------------**
@c %   **                           OpenScop Library                      **
@c %   **-----------------------------------------------------------------**
@c %   **                            openscop.texi                        **
@c %   **-----------------------------------------------------------------**
@c %   **                 First version: september 10th 2006              **
@c %   **-----------------------------------------------------------------**/
@c %
@c % release 0.0: May 4th 2008
@c %

@c % /*************************************************************************
@c %  *                              PART I: HEADER                           *
@c %  *************************************************************************/
@c %**start of header
@setfilename openscop.info
@settitle OpenScop - File Format and Data Structures for Polyhedral Compilation Tools

@set EDITION 1.0
@set SPEC_VERSION 1.0
@set LIB_VERSION 1.0
@set UPDATED November 13th 2010
@c @set UPDATED Coming soon
@setchapternewpage odd

@c % This is to ask for A4 instead of Letter size document.
@iftex
     @afourpaper
@end iftex

@c %**end of header

@c % /************************************************************************
@c %  *                PART II: SUMMARY DESCRIPTION AND COPYRIGHT            *
@c %  ************************************************************************/

@copying
This document describes OpenScop, a specification of a file format and a set
of data structures for polyhedral compilation tools to be able to talk
together. It also describes the OpenScop Library version @value{LIB_VERSION}, 
a Free Software that provides an example of OpenScop implementation.

It would be quite kind to refer the following paper in any publication that
results from the use of the OpenScop library (the reason to cite this paper is,
amongst many other interesting thing, that it defines what is a @emph{SCoP},
or @emph{static control part}):

@example
@@InProceedings@{Bas03,
@ @ author =@ @ @ @ @{C\'edric Bastoul and Albert Cohen and Sylvain Girbal and
@ @ @ @ @ @ @ @ @ @ @ @ @ @ @ Saurabh Sharma and Olivier Temam@},
@ @ title =@ @ @ @ @ @{Putting Polyhedral Loop Transformations to Work@},
@ @ booktitle =@ @{LCPC'16 International Workshop on Languages and
@ @ @ @ @ @ @ @ @ @ @ @ @ @ @ Compilers for Parallel Computers, LNCS 2958@},
@ @ pages =@ @ @ @ @ @{209--225@},
@ @ month =@ @ @ @ @ @{october@},
@ @ year =@ @ @ @ @ @ 2003,
@ @ address =@ @ @ @{College Station, Texas@}
@}
@end example

Copyright @copyright{} 2010 C@'edric Bastoul.

@c quotation
Permission is granted to copy, distribute and/or modify this document under
the terms of the GNU Free Documentation License, Version 1.2
published by the Free Software Foundation. To receive a copy of the
GNU Free Documentation License, write to the Free Software Foundation, Inc.,
59 Temple Place, Suite 330, Boston, MA  02111-1307 USA.
@c end quotation
@end copying

@c % /*************************************************************************
@c %  *                 PART III: TITLEPAGE, CONTENTS, COPYRIGHT              *
@c %  *************************************************************************/
@titlepage
@title OpenScop
@subtitle File Format and Data Structures for Data Exchange in Polyhedral Compilation Tools
@subtitle Edition @value{EDITION}, for OpenScop Specification @value{SPEC_VERSION} and OpenScop Library @value{LIB_VERSION}
@subtitle @value{UPDATED}
@author C@'edric Bastoul

@c The following two commands start the copyright page.
@page
@vskip 0pt plus 1filll
@insertcopying
@end titlepage

@c Output the table of contents at the beginning.
@contents

@c % /*************************************************************************
@c %  *                     PART IV: TOP NODE AND MASTER MENU                 *
@c %  *************************************************************************/
@ifnottex
@node Top
@top OpenSCop

@insertcopying
@end ifnottex

@menu
* Introduction::
* Polyhedral Representation::
* OpenScop File Format Specification::
* Clan Library::
* Installing::
* Documentation::
* References::
@end menu



@c % /*************************************************************************
@c %  *                       PART V: BODY OF THE DOCUMENT                    *
@c %  *************************************************************************/

@c %  ****************************** INTRODUCTION ******************************
@node Introduction
@chapter Introduction
OpenScop is an open specification that defines a file format and a set of
data structures to represent a @emph{static control part} (SCoP for short),
i.e., a program part that can be represented in the @emph{polyhedral model}.
The goal of OpenScop is to provide a common interface to the different
polyhedral compilation tools in order to simplify their interaction. 

Designing a single format for tools that have different purposes
(e.g., as different as code generation and data dependence analysis) may
sound strange at first. However we could observe that most available
polyhedral compilation tool during the last decade were manipulating
more or less the same kind of data (polyhedra, affine functions...) and
were actually sharing a part of their input (e.g., iteration domains and
context concepts are nearly everywhere). We could also observe that
those tools may rely on different internal representations, mostly based on
one of the major polyhedral libraries (e.g., Polylib, PPL or isl), and
this representation may change over time (e.g., when switching to a
more convenient polyhedral library).
The OpenScop aim is to provide a stable, unified format that offers a
durable guarantee that a tool can use an output or provide an input to
another tool without breaking a tool chain because of slight internal
changes. The other promise of OpenScop is the ablility to assemble or
replace the basic blocs of a polyhedral compilation framework at no, or
at least low engineering cost.

The policy that drives OpenScop can be summarized by these three main rules:
@itemize @bullet
@item  Embbed the @emph{minimum} information to build a complete polyhedral
       compilation framework in the core part (to avoid as much as possible
       empty or useless fields for each tool).
@item  Provide a @emph{very stable} core part (including powerful enough
       objects to support state-of-the-art techniques, to avoid 
       spending time to maintain an OpenScop input or output),
@item  Provide a @emph{very flexible} extension part (so OpenScop can also
       be used to test wild new ideas).
@end itemize

The success of OpenScop in meeting its goals totally depend on its
acceptance by the tool developpers (that have to support it in their tools).
To help them, we provide an example implementation: the OpenScop Library.
This library (and in particular its API) is not part of the OpenScop
specification (which includes only the file format and the set of data
structures). It is licensed under the 3-clause BSD license so developpers may
feel free to use it in their code (either by linking it or copy-pasting its
code). This document also describes this library in details.
The current version of the OpenScop Library is still under evaluation,
and there is no guarantee that the upward compatibility will be respected,
even if we do think so. A lot of reports are
necessary to freeze the library API. Thus you are very welcome and
encouraged to send reports on bugs, wishes, critics, comments, suggestions
or (please !) successful experiences to cedric.bastoul@@u-psud.fr.

This document is organized as follows. First, we provide some
background on the polyhedral model and how it is used to represent and to
manipulate programs (@pxref{Polyhedral Representation}). Next,
we describe the OpenScop specification, from the file format
(@pxref{OpenScop File Format Specification}) to the data structures and
details of the OpenScop Library API
(@pxref{OpenScop Data Structure Specification}).
Finally we will detail how to install the OpenScop Library
(@pxref{Installing}).


@c %  ******************* POLYHEDRAL REPRESENTATION OF PROGRAMS ****************
@node Polyhedral Representation
@chapter Polyhedral Representation of Programs
If you are reading at OpenScop's documentation, you probably don't need any
explanation about the Polyhedral Model. It is unlikely someone will read this
paper by chance. However some vicious advisor may ask their poor
engineers/interns/students
to work for the very first time on this exciting topic. Most papers on
polyhedral compilation are hard to read. Despite my efforts,
mine are no exception according to some reviewers... Hence I give there a new
try to provide a comprehensive explanation of the polyhedral model without the
size and style limits of a classical research paper.

Be aware that to be able to understand the polyhedral model, there are few
prerequisites. You should not read the following while you still ignore
what is:
@itemize @bullet
@item  a @code{for} loop construction in C programs (@code{do} loops in FORTRAN are OK too !),
@item  an @emph{affine expression},
@item  a @emph{vector},
@item  a @emph{matrix},
@item  a @emph{matrix-vector multiply}.
@end itemize
If you do not know those concepts, please do some search and come back
afterwards. And if you are courageous enough, send me a few lines that
describe them so I can insert that here !

@menu
* Motivation::
* Thinking in Polyhedra::
@end menu


@node Motivation
@section Motivation: Program Transformations

A direct translation of high level programs written, e.g., in C, to assembly
then to object code is likely to produce (very) inefficient applications.
Architectures are
quite complex, including several levels of cache memory, many cores, deep
pipelines, various number of functionnal units, of registers etc.
The list of such
"architectural features" is growing with each new generation of processors.
To achieve the best performance, the object program must do a smart use
of these features.
Programmers use high level languages for productivity and portability:
typically they do not have to take care of the target architecture but
to ensure they do write programs that produce the right output. Hence,
the problem of mapping the program to the target architecture in the most
efficient way is left to the compiler.

The compiler may see a high level program as a specification
@emph{of an output}. The program is a list of operations to be executed to
produce the output. As long as the output is guaranteed to be as the
programmer specified in his code, the compiler is free to modify
the program.
For instance, let us imagine we are working on an architecture with only
three registers and we consider the following statements written by
a programmer:

@example
@group
x = a + b;
y = c + d;
z = a * b;
@end group
@end example

It is easy to see that we can reorder the three statements in any way without
modifying the semantics (no statement reads or writes a variable that another
statement writes). Because of the lack of registers, the solutions such that
the first and the third statements are one after the other are better
because @code{a} and @code{b} will be put in the processor registers by
one statement and can be reused directly by the other one
without reading to memory (this is called a @emph{data locality
improving} transformation). Hence a better statement order is, e.g.:

@example
@group
x = a + b;
z = a * b; // a and b are still in processor registers
y = c + d;
@end group
@end example

We could also notice that it is possible to run the three statements in
parallel and explicit this in the way the compiler and/or the architecture is
able to understand. Here we use OpenMP to describe parallelism
(this is called a @emph{parallelizing} transformation):

@example
@group
#pragma omp parallel sections
@{
   #pragma omp section
   @{
     x = a + b;
   @}
   #pragma omp section
   @{
     y = c + d;
   @}
   #pragma omp section
   @{
     z = a * b;
   @}
@}
@end group
@end example

However, the right way to optimize this program is probably a mix of these
two techniques, especially if the target architecture have some limitations
to run too many operations in parallel:

@example
@group
#pragma omp parallel sections
@{
   #pragma omp section
   @{
     x = a + b;
     z = a * b;
   @}
   #pragma omp section
   @{
     y = c + d;
   @}
@}
@end group
@end example

Such transformations are quite trivial. The reason is the statements are
executed only once. The real sport begins when we have to deal with loops
as we will see momentarily. However, polyhedral compilation framework users
have to be conscious that we @emph{need} to transform programs to achieve
the best performance and that the best transformation  that have to be
discovered (with often many, many efforts) and performed may be
quite complex. Hence the need of powerful model and tools.


@node Thinking in Polyhedra
@section Thinking in Polyhedra


Since the very first compilers, the internal representation of programs
is the @emph{Abstract Syntax Tree}, or AST. In such representation,
each statement appears only once even if it is executed many times (e.g.,
when it is enclosed inside a loop).

@noindent @strong{This is a limitation for program analysis.}
For instance if a statement @emph{depends} on another statement (i.e., they
access the same memory location and at least one of these accesses is a
write), we will consider both statements as unique entities while the
dependence relation may involve only few statement executions.

@noindent @strong{This is a limitation for program transformations.}
Loop transformations operate on statement executions. For instance,
because they consider all statement executions at the same time, present day
production compilers are not able to achieve loop fusion (that tries to
merge the loop bodies of two loops) if the loop bounds
of the two loops do not match (hahaha).

@noindent @strong{This is a limitation for program manipulation flexibility.}
Trees are very rigid data structures that are not easy to manipulate.
Program transformation may require very complex transformations that will
imply deep modifications of the control flow. Hence, for complex program
restructuration, the need for a more precise, more flexible representation.

The Polyhedral Model is a convenient alternative representation which
combines analysis power, expressiveness and high flexibility. The drawback
is it breaks the classical structure of programs that every programmer
is familiar with. It requires some (real) efforts
to be smoothly manipulated, but it definitely worth it. It is based on three
main concepts, @emph{iteration domain},  @emph{scattering function} and
@emph{access function} that are described in depth in the
following sections.

A program part that can be represented using the Polyhedral Model is called
a @strong{Static Control Part} or @strong{SCoP} for short.

@menu
* Iteration Domain::
* Scattering Function::
* Access Function::
@end menu

@node Iteration Domain
@subsection Iteration Domain

The key aspect of the polyhedral model is to consider @emph{statement
instances}. A statement instance is @emph{one} execution of a statement.
A statement
outside a loop has only one instance while those inside loops may have many.
Let us consider the following code with two statements @code{S1}
and @code{S2}:

@example
@group
pi = 3.14;               // S1
for (i = 0; i < 5; i++)
  A[i] = pi;             // S2
@end group
@end example

The list of statement instances is the following (we just have to fully
unroll the loop):

@example
@group
pi = 3.14;
A[0] = pi;
A[1] = pi;
A[2] = pi;
A[3] = pi;
A[4] = pi;
@end group
@end example

Each instance of a statement which is enclosed inside a loop may be referred
thanks to its outer loop counters (or @emph{iterators}). In the Polyhedral
Model we consider statements as functions of the outer loop counters that may
produce statement instances:
instead of simply "@code{S2}", we use preferably the notation @code{S2(i)}.
For instance we  denote the statement instance @code{A[3] = pi;} of the
previous example as @code{S2(3)}. This means @emph{instance of
statement @code{S2} for} @code{i = 3}.
If a statement @code{S3} is enclosed inside two loops of iterators @code{i}
(outermost loop) and @code{j} (innermost loop), we would denote it
@code{S3(i,j)}, and so on with more enclosing loops.

The ordered list
of iterators (ordered from the outermost iterator to the innermost iterator)
is called the @strong{iteration vector}. For instance the iteration vector for
@code{S3} is @code{(i,j)}, for @code{S2} it is @code{(i)}, and for @code{S1}
it is empty since it has no enclosing loop: @code{()}. A more precise reading
at the notation @code{S2(3)} would show that it denotes the instance of
statement @code{S2} for the iteration vector @code{(2)}.

Obviously, dealing with statement instances does not mean we have to unroll all
loops. First because there would be probably too many instances to deal with,
and second because we probably just don't know how many instances there are.
For instance in the following loop it is not possible to know (at compile time)
how many times the statement @code{S3} will be executed:

@example
@group
for (i = 2; i <= N; i++)
  for (j = 2; j <= N; j++)
    A[i] = pi;             // S3
@end group
@end example

@noindent Such a loop is said to be @emph{parametric}: it depends on
(at least) a value called a @emph{parameter} which is not modified
during the execution of the whole loop, but is unknown at compile time.
Here the only parameter is @code{N}.

A compact way to represent all the instances of a given statement
is to consider the set of all possible values of its iteration vector.
This set is called the @strong{iteration domain}. It can be conveniently
described thanks to all the constraints on the various iterators the statement
depends on. For instance, let us consider
the statement @code{S3} of the previous program. The iteration domain is the set
of iteration vectors @code{(i,j)}. Because of the parameter, we are not able to
achieve a precise list of all possible values, it would look like this:

@example
@group
(2,2)  (2,3)  (2,4)  ...  (2,N)
(3,2)  (3,3)  (3,4)  ...  (3,N)
...    ...    ...    ...  ...
(N,2)  (N,3)  (N,4)  ...  (N,N)
@end group
@end example

@noindent A better way is to say it is the set
of iteration vectors @code{(i,j)} such that @code{i} is an integer greater or
equal than 2 and lower or equal than @code{N}, and @code{j} is an integer
greater or equal than 2 and lower or equal than @code{N}. This may be written
in the following mathematical form:

@tex
$$D _{S3} =  \{(i,j) \in Z^2 \; | \; 2 \leq i \leq N \land 2 \leq j \leq N \}$$
@end tex

@ifnottex
@example
@group
D_S3 =  @{(i,j) in Z^2 | 2 <= i <= N && 2 <= j <= N @}
@end group
@end example
@end ifnottex

@noindent It is easy to see that this iteration domain is a part of the
2-dimensional space
@tex
$Z^2$.
@end tex
@ifnottex
@example
@group
Z^2.
@end group
@end example
@end ifnottex
We often use in our research papers a graphical representation that gives a
better view of this subspace:

@image{images/basic1,4cm}

@noindent Here the iteration domain is specified thanks to a set of
constraints. When those constraints are affine and
depend only on the outer loop counters and some parameters, the set of
constraints defines a @emph{polyhedron} (more precisely this is a
@emph{Z-polyhedron}, but we use @emph{polyhedron} for short).
Hence the Polyhedral Model.

To facilitate the manipulation of the affine constraints, we use a matrix
representation. To write it, we use the @emph{homogeneous} iteration vector:
it is simply the iteration vector with some additional dimensions to
represent the parameters and the constant.
For instance for the statement @code{S3}, the
iteration vector in homogeneous coordinates is @code{(i,j,N,1)}
(we will now call it @emph{iteration vector} directly for short).
Then we write all the constraints as affine inequalities of the form
@tex
$p(i) \geq 0$.
@end tex
@ifnottex
@code{p(i) >= 0}.
@end ifnottex
For instance for the statement @code{S3} the set of constraints is:

@tex
$$
\hbox{$ \cases{  i         - 2  &$\geq 0$\cr
                -i     + N      &$\geq 0$\cr
                     j     - 2  &$\geq 0$\cr
                    -j + N      &$\geq 0$}$}
$$
@end tex

@ifnottex
@example
@group
    i - 2 >= 0
   -i + N >= 0
    j - 2 >= 0
   -j + N >= 0
@end group
@end example
@end ifnottex

@noindent Lastly, we translate the constraint system to the form
@strong{domain matrix}@code{ * }@emph{iteration vector}@code{ >= 0}
(please someone show me how to do this in TeX -not LaTeX- for the
texinfo manual !):
@example
@group
[  1  0  0 -2 ]   [ i ]    [ 0 ]
[ -1  0  1  0 ]   [ j ]    [ 0 ]
[  0  1  0 -2 ] * [ N ] >= [ 0 ]
[  0 -1  1  0 ]   [ 1 ]    [ 0 ]
@end group
@end example

@noindent The domain matrix (along with the iteration vector which
is most of the time an implicit information) will
be used in all our tools to provide the informations on the iteration
domain of a given statement.

@node Scattering Function
@subsection Scattering Function

There is no ordering information inside the iteration domain: it only describes
the set of statement instances but @strong{not} the order in which they have
to be executed relatively to each other. In the past the lexicographic order
of the iteration domain was considered, this is no more true
(especially when using CLooG). If we don't give any ordering information, this
means that the statement instances may be executed in any order
(this is useful, e.g., to specify parallelism), but some statement instances
may depend on some others and it may be critical to enforce a given order (or
non-order). Hence we need another information.

We call @emph{scattering} any kind of ordering information in the Polyhedral
Model. There exists many kind of ordering indeed, as @emph{allocation},
@emph{scheduling}, @emph{chunking} etc. Nevertheless they are all expressed
in the same way, using @emph{logical stamps} that can have various semantics.

In the case of @strong{scheduling}, the logical stamps are logical dates that
express at which date a statement instance have to be executed. For instance,
let us consider the following three statements:

@example
@group
x = a + b;   // S1
y = c + d;   // S2
z = a * b;   // S3
@end group
@end example

@noindent The scheduling of a statement @code{S} is typically
denoted by
@tex
$\theta_{S}$.
@end tex
@ifnottex
T_S.
@end ifnottex
Let us consider the following logical dates for each statement:

@tex
@example
@group
$\theta_{S1} = 2$
$\theta_{S2} = 3$
$\theta_{S3} = 1$
@end group
@end example
@end tex

@ifnottex
@example
@group
T_S1 = 1
T_S2 = 2
T_S3 = 3
@end group
@end example
@end ifnottex

@noindent It means that statement @code{S3} have to be executed at logical date
@code{1}, statement @code{S1} have to be executed at logical date
@code{2} and statement @code{S2} have to be executed at logical date
@code{3}. The target code have to respect this scheduling (the order of
the logical dates), hence it would look like the following where the
variable @code{t} denotes the time:

@example
@group
t = 1;
z = a * b;   // S3
t = 2;
x = a + b;   // S1
t = 3;
y = c + d;   // S2
@end group
@end example

@noindent When some statements share the same logical date, this means that,
once the program reaches this logical date, the two statements can be executed
in any order, or better, in parallel. For instance let us consider the
following scheduling:

@tex
@example
@group
$\theta_{S1} = 1$
$\theta_{S2} = 2$
$\theta_{S3} = 1$
@end group
@end example
@end tex

@ifnottex
@example
@group
T_S1 = 1
T_S2 = 2
T_S3 = 1
@end group
@end example
@end ifnottex

@noindent Statements @code{S1} and @code{S3} have the same logical date,
hence the target code would be:

@example
@group
t = 1;
#pragma omp parallel sections
@{
   #pragma omp section
   @{
     x = a + b;   // S1
   @}
   #pragma omp section
   @{
     z = a * b;   // S3
   @}
@}
t = 2;
y = c + d;        // S2
@end group
@end example

Logical dates may be multidimensional, as clocks: the first dimension
corresponds to days (most significant), next one is hours (less
significant), the third to minutes and so on. For instance we can consider
the following multidimensional schedules for our example:

@tex
@example
@group
$\theta_{S1} = (1,1)$
$\theta_{S2} = (2,1)$
$\theta_{S3} = (1,2)$
@end group
@end example
@end tex

@ifnottex
@example
@group
T_S1 = (1,1)
T_S2 = (2,1)
T_S3 = (1,2)
@end group
@end example
@end ifnottex

@noindent It is not very hard to decypher the meaning of such scheduling.
Because of the first dimension, statements @code{S1} and @code{S3} will be
executed before statement @code{S2} (@code{S1} and @code{S3} are executed at
day 1, while @code{S2} is executed at day 2). The second dimension is not
really useful there for @code{S2} because it is the only statement executed
at day 2. Nevertheless it allows to order @code{S1} and
@code{S3} relatively to each other since @code{S1} is executed at hour 1 of day
1 while @code{S3} is executed at hour 2 of day 1.
The corresponding target code is the following, with some
additional time variables for a better view of the ordering (@code{t1}
corresponds to the first time dimension, @code{t2} to the second one):

@example
@group
t1 = 1;
t2 = 1;
x = a + b;   // S1
t2 = 2;
z = a * b;   // S3
t1 = 2;
t2 = 1;
y = c + d;   // S2
@end group
@end example

In the case of @strong{allocation} (in the litterature we can find some
papers that call it @emph{placement}), the logical stamps are a processor
number that expresses on which processor a statement instance has to be
executed. Typically, allocations are written in the same way as scheduling
(hence the general term of @emph{scattering}), here we denote it @math{P_S} for a
statement @code{S}. For instance, let us consider the following
allocation:

@tex
@example
@group
$P_{S1} = 1$
$P_{S2} = 2$
$P_{S3} = 1$
@end group
@end example
@end tex

@ifnottex
@example
@group
P_S1 = 1
P_S2 = 2
P_S3 = 1
@end group
@end example
@end ifnottex

@noindent The corresponding target code have to take into account that both
statements @code{S1} and @code{S3} have to be executed on the same processor
(they have the same logical number 1) and that statement @code{S2} have
to be executed on another processor (logical number 2). A possible target code
is the following:

@example
@group
#pragma omp parallel sections
@{
   #pragma omp section
   @{
     // Logical processor 1
     x = a + b;   // S1
     z = a * b;   // S3
   @}
   #pragma omp section
   @{
     // Logical processor 2
     y = c + d;   // S2
   @}
@}
@end group
@end example

@noindent We can note that no order have been specified for the
statements @code{S1} and @code{S3} that are executed on the same processor.
Hence any order is satisfying. For sake of flexibility, it is usual to build
a scattering whose various dimensions do not have the same semantics. A
typical construction is @emph{space/time mapping} where the first @code{n}
dimensions are devoted to allocation, then the last @code{m}
dimensions are devoted to scheduling. Typically, space/time mapping is
written in the same way as scheduling (hence again the general term of
@emph{scattering}), here we denote it for a statement @code{S} as @math{M_S}.
For instance, let us consider the following space/time mapping for our
example where one dimension is devoted for mapping and one dimension is
devoted to scheduling:

@tex
@example
@group
$M_{S1} = (1,2)$
$M_{S2} = (2,1)$
$M_{S3} = (1,1)$
@end group
@end example
@end tex

@ifnottex
@example
@group
M_S1 = (1,2)
M_S2 = (2,1)
M_S3 = (1,1)
@end group
@end example
@end ifnottex

@noindent Here we have the same first dimension as the previous example, thus
the allocation of the statements to processors is the same. The second
dimension precises on a given processor at which logical date a statement
instance has to be executed. Here, the statement @code{S1} is executed at
day 2 on processor 1 while the statement @code{S3} is executed at day 1 onto
the same processor. It follows this space/time mapping corresponds to the
following target code (we added an additional variable to represent the
local logical clocks):

@example
@group
#pragma omp parallel sections
@{
   #pragma omp section
   @{
     // Logical processor 1
     t = 1;
     z = a * b;   // S3
     t = 2;
     x = a + b;   // S1
   @}
   #pragma omp section
   @{
     // Logical processor 2
     t = 1;
     y = c + d;   // S2
   @}
@}
@end group
@end example

For the same reason as discussed for iteration domains
(@pxref{Iteration Domain}), it is not possible to define a scattering for
each statement instance, especially if the statement belongs to a
(possibly parametric) loop. The iteration vector fully defines an
instance of a given statement. Thus, a practical way to provide a scattering
for each instance of a given statement is to use a @emph{function}
that depends on the iteration vector. In this way the function may give
for each iteration vector a different scattering. We call these functions
@strong{scattering functions}. Scattering functions are @emph{affine}
functions of the outer loop counter and the global parameters.
For instance, let us consider the following source code:

@example
@group
for (i = 2; i <= 4; i++)
  for (j = 2; j <= 4; j++)
    P[i+j] += A[i] + B[j]; // S4
@end group
@end example

@noindent The iteration domain of the statement @code{S4} is:


@tex
$$D _{S4} =  \{(i,j) \in Z^2 \; | \; 2 \leq i \leq 4 \land 2 \leq j \leq 4 \}.$$
@end tex
@ifnottex
@example
@group
D_S4=  @{(i,j) in Z^2 | 2 <= i <= 4 && 2 <= j <= 4 @}.
@end group
@end example
@end ifnottex

@noindent If you are still not comfortable with the mathematical notation, it
corresponds to the following graphical representation:

@image{images/basic2,3cm}

@noindent The list of the statement instances of @code{S4} (the integral
points of its iteration domain) corresponds to the following iteration vectors:

@example
@group
iteration vector
     (2,2)
     (2,3)
     (2,4)
     (3,2)
     (3,3)
     (3,4)
     (4,2)
     (4,3)
     (4,4)
@end group
@end example

@noindent Let us suppose we want to schedule the instances of the statement
@code{S4} (the integral points of its iteration domain) using the following
scheduling function:

@tex
@example
@group
$\theta_{S4}(i,j) = (j+2,3*i+j)$
@end group
@end example
@end tex

@ifnottex
@example
@group
T_S4(i,j) = (j+2,3*i+j)
@end group
@end example
@end ifnottex

@noindent We only have to apply the function to each iteration vector to find
the logical date of each instance:

@example
@group
iteration vector       logical date
     (2,2)       -->       (4,8)
     (2,3)       -->       (5,9)
     (2,4)       -->       (6,10)
     (3,2)       -->       (4,11)
     (3,3)       -->       (5,12)
     (3,4)       -->       (6,13)
     (4,2)       -->       (4,14)
     (4,3)       -->       (5,15)
     (4,4)       -->       (6,16)
@end group
@end example

Polyhedral Model users do not have to take care about the generation of a
target code that respects the scattering: the CLooG tool is there to
solve the problem quite easily (@code{http://www.cloog.org}). For the previous
example, the target code would be the following (@code{t1} and @code{t2}
corresponds to the two dimensions of the logical date):

@example
@group
for (t1 = 4; t1 <= 6; t1++) @{
  for (t2 = t1+4; t2 <= t1+10; t2++) @{
    if ((-t1+t2+2)%3 == 0) @{
      i = (-t1+t2+2)/3 ;
      j = t1-2 ;
      P[i+j] += A[i] + B[j]; // S4
    @}
  @}
@}
@end group
@end example



Obviously with such a twisted scheduling, it is hard to see the "meaning"
of the transformation. To name any kind of program transformation as
a magic spell ("tile", "fuse", "skew"...) is an old bad habit that should
be changed in the Polyhedral Model: a scheduling may be an arbitrary complex
sequence of basic-old-good transformations. Nevertheless it is most of the
time quite easy to translate well known transformations to schedules. For
instance, let us consider this new scheduling function:

@tex
@example
@group
$\theta_{S4}(i,j) = (j,i)$
@end group
@end example
@end tex

@ifnottex
@example
@group
T_S4(i,j) = (j,i)
@end group
@end example
@end ifnottex

@noindent Using CLooG, we can generate the target code:

@example
@group
for (t1 = 2; t1 <= 4; t1++) @{
  for (t2 = 2; t2 <= 4; t2++) @{
    i = t2;
    j = t1;
    P[i+j] += A[i] + B[j]; // S4
  @}
@}
@end group
@end example


@noindent It is easy to see (and analyze) that it corresponds to a classical
@emph{loop interchange} transformation.

A very useful example of multi-dimensional scattering functions is
the @strong{scheduling of the original program}.
The method to compute it is quite simple (@pxref{Fea92}). The idea is to
build an abstract syntax tree of the program and to read the scheduling for
each statement. For instance, let us consider the following implementation of
a Cholesky factorization:

@example
@group
/* A Cholesky factorization kernel. */
for (i=1;i<=N;i++) @{
  for (j=1;j<=i-1;j++) @{
    a[i][i] -= a[i][j] ;           /* S1 */
  @}
  a[i][i] = sqrt(a[i][i]) ;        /* S2 */
  for (j=i+1;j<=N;j++) @{
    for (k=1;k<=i-1;k++) @{
      a[j][i] -= a[j][k]*a[i][k] ; /* S3 */
    @}
    a[j][i] /= a[i][i] ;           /* S4 */
    @}
  @}
@}
@end group
@end example

@noindent The corresponding abstract syntax tree is given in the following
figure. It directly gives the scattering functions (schedules) for all the
statements of the program.

@image{images/tree,6cm}

@tex
$$
\hbox{$ \cases{ \theta _{S1}(i,j)    &$=  (0,i,0,j,0)$\cr
                \theta _{S2}(i)      &$=  (0,i,1)$\cr
                \theta _{S3}(i,j,k)  &$=  (0,i,2,j,0,k,0)$\cr
                \theta _{S4}(i,j)    &$=  (0,i,2,j,1)$}$}
$$
@end tex

@ifnottex
@example
@group
T_S1(i,j)   = (0,i,0,j,0)
T_S2(i)     = (0,i,1)
T_S3(i,j,k) = (0,i,2,j,0,k,0)
T_S4(i,j)   = (0,i,2,j,1)
@end group
@end example
@end ifnottex

@noindent These schedules depend on the iterators and give for each instance
of each statement a unique execution date. Using such scattering functions
allows CLooG to re-generate the input code.

@noindent To easily manipulate the scattering function of any
statement @code{S}, we translate it to the matrix form:
@tex
@math{\theta_S}(@emph{iteration vector})
@end tex
@ifnottex
T_S(@emph{iteration vector})
@end ifnottex
@code{ = }@strong{scattering matrix}@code{ * }@emph{iteration vector}.
For instance let us consider again our previous example
@tex
$\theta_{S4}(i,j) = (j+2,3*i+j).$
@end tex
@ifnottex
T_S4(i,j) = (j+2,3*i+j).
@end ifnottex
We write it in the following way (again please someone show me how to do
this in TeX -not LaTeX- for the texinfo manual !):
@example
@group
     [ i ]    [  0  1  2 ]   [ i ]
T_S4([ j ]) = [  3  1  0 ] * [ j ]
     [ 1 ]                   [ 1 ]
@end group
@end example

@noindent The scattering matrix (along with the iteration vector which
is most of the time an implicit information) will
be used in all our tools to provide the informations on the scattering
of a given statement.


@node Access Function
@subsection Access Function

Before applying any transformation, it is essential to deeply analyze both the
original program and the transformation to ensure the transformation does not
imply any modification of the original program semantics. In the Polyhedral
Model, we can reach a @strong{total analysis power}: we are able to achieve
an exact analysis when all the memory accesses are made through arrays
(note that variables are a particular case of arrays since they are simply
arrays with only one memory location) with affine subscripts that depend
on outer loop counters and global parameters (note that @emph{subscripts}
are sometimes called @emph{index} or @emph{accesses} in the litterature).

For instance let us consider the array access @code{A[2*i+j][j][i+N]}. It has
three dimensions, each subscript dimension is an affine form of some outer loop
iterarors (@code{i} and @code{j}) and global parameters (@code{N}) hence
it corresponds to an acceptable array access in the Polyhedral Model.

Each array access can target a different memory cell depending on the
statement instance, i.e., depending on the iteration vector.
Thus we use access functions (or subscript functions or index functions as you
prefer) depending on the iteration vector to describe an array access. In our
example, the access function would be written
@math{F_A(i,j) = (2*i+j,j,i+N)}.

@noindent To easily manipulate the access function of any
array @code{A}, we translate it to the matrix form:
@math{F_A}(@emph{iteration vector})
@code{ = }@strong{access matrix}@code{ * }@emph{iteration vector}.
For instance let us consider again our previous example: we write it in the
following way (again please someone show me how to do this in TeX -not LaTeX-
for the texinfo manual !):
@example
@group
    [ i ]    [  2  1  0  0 ]   [ i ]
F_A([ j ]) = [  0  1  0  0 ] * [ j ]
    [ N ]    [  1  0  1  0 ]   [ N ]
    [ 1 ]                      [ 1 ]
@end group
@end example

@noindent The access matrix (along with the iteration vector which
is most of the time an implicit information) will
be used in all our tools to provide the informations on the access
of a given statement.



@c %  *********************** OpenScop Specification **************************
@node OpenScop File Format Specification
@chapter OpenScop File Format Specification


@menu
* A First Example::
* Writing The Input File::
* Reading The Output File::
* Calling Clan::
* Clan Options::
@end menu

@c %/*************************************************************************
@c % *                              A FIRST EXAMPLE                          *
@c % *************************************************************************/
@node A First Example
@section A First Example
Clan takes as input a source code file than can be written in either C or
C++ or C# or Java (or any other imperative language that is close enough
to C). It is very simple as it only translates a part of a program that can
be represented using the Polyhedral model (@pxref{Polyhedral Representation}) in
a matrix form. Clan does not find itself the program parts that could be
represented using the Polyhedral Model. More complex tools like WRAP-IT for the
ORC compiler (@code{http://www.lri.fr/~girbal/site_wrapit})or the GRAPHITE
branch of GCC (@code{http://gcc.gnu.org/wiki/Graphite}) are devoted to
such a complex, highly technical problem. Using Clan, the user has to specify
thanks to pragmas where begins the SCoP he is interested by, and where it ends.

For instance, let us consider the following source code in C of a matrix-matrix
multiply program that reads two matrices, achieves the multiply then prints
the result. Let us also consider that the user is only interested in the
matrix-matrix multiply kernel:

@example
/* matmul.c 128*128 matrix multiply */
#include <stdio.h>
#define N 128

int main() @{
  int   i,j,k;
  float a[N][N], b[N][N], c[N][N];

  /* We read matrix a then matrix b */
  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
      scanf(" %f",&a[i][j]);
  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
      scanf(" %f",&b[i][j]);

  /* c = a * b */
#pragma scop
  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++) @{
      c[i][j] = 0.0;
      for (k = 0; k < N; k++)
        c[i][j] = c[i][j] + a[i][k]*b[k][j];
    @}
#pragma endscop

  /* We print matrix c */
  for (i = 0; i < N; i++) @{
    for (j = 0; j < N; j++)
      printf("%6.2f ",c[i][j]);
    printf("\n");
  @}

  return 0;
@}
@end example

The tags to ask Clan to consider a given part of the code are provided thanks
to the pragmas @code{#pragma scop} and  @code{#pragma endscop}. It can have
different forms depending on the input language. This is explained in
a further section (@pxref{Writing The Input File}).

This source code file may be called @samp{matmul.c}
(this example is provided in the Clan distribution as
@code{test/matmul.c}) and we can ask Clan to process it
and to generate the polyhedral representation by a simple call to Clan
with this file as input: @samp{clan matmul.c}. By default, Clan will print
the polyhedral representation in the standard output:

@example
# [File generated by Clan 1.0.0 64 bits]

SCoP

# =============================================== Global
# Language
C

# Context
0 3

# Parameter names are provided
1
# Parameter names
N

# Number of statements
2

# =============================================== Statement 1
# ----------------------------------------------  1.1 Domain
# Iteration domain
1
4 5
   1    1    0    0    0    ## i >= 0
   1   -1    0    1   -1    ## -i+N-1 >= 0
   1    0    1    0    0    ## j >= 0
   1    0   -1    1   -1    ## -j+N-1 >= 0

# ----------------------------------------------  1.2 Scattering
# Scattering function is provided
1
# Scattering function
5 5
   0    0    0    0    0    ## 0
   0    1    0    0    0    ## i
   0    0    0    0    0    ## 0
   0    0    1    0    0    ## j
   0    0    0    0    0    ## 0

# ----------------------------------------------  1.3 Access
# Access informations are provided
1
# Read access informations
0 5
# Write access informations
2 5
   1    1    0    0    0    ## c[i][j]
   0    0    1    0    0    ##

# ----------------------------------------------  1.4 Body
# Statement body is provided
1
# Original iterator names
i j
# Statement body
c[i][j]=0.0;


# =============================================== Statement 2
# ----------------------------------------------  2.1 Domain
# Iteration domain
1
6 6
   1    1    0    0    0    0    ## i >= 0
   1   -1    0    0    1   -1    ## -i+N-1 >= 0
   1    0    1    0    0    0    ## j >= 0
   1    0   -1    0    1   -1    ## -j+N-1 >= 0
   1    0    0    1    0    0    ## k >= 0
   1    0    0   -1    1   -1    ## -k+N-1 >= 0

# ----------------------------------------------  2.2 Scattering
# Scattering function is provided
1
# Scattering function
7 6
   0    0    0    0    0    0    ## 0
   0    1    0    0    0    0    ## i
   0    0    0    0    0    0    ## 0
   0    0    1    0    0    0    ## j
   0    0    0    0    0    1    ## 1
   0    0    0    1    0    0    ## k
   0    0    0    0    0    0    ## 0

# ----------------------------------------------  2.3 Access
# Access informations are provided
1
# Read access informations
6 6
   1    1    0    0    0    0    ## c[i][j]
   0    0    1    0    0    0    ##
   2    1    0    0    0    0    ## a[i][k]
   0    0    0    1    0    0    ##
   3    0    0    1    0    0    ## b[k][j]
   0    0    1    0    0    0    ##
# Write access informations
2 6
   1    1    0    0    0    0    ## c[i][j]
   0    0    1    0    0    0    ##

# ----------------------------------------------  2.4 Body
# Statement body is provided
1
# Original iterator names
i j k
# Statement body
c[i][j]=c[i][j]+a[i][k]*b[k][j];


# =============================================== Options
@end example

We will not describe here precisely the structure and the components of this
output, this is described in depth in a further section
(@pxref{Reading The Output File}). This file format, called @code{.scop} has
been designed to be the input file format of most of the polyhedral tools.
If you read the description of the polyhedral representation of programs,
you should already feel familiar with this file format
(@pxref{Polyhedral Representation}).


@c %/*************************************************************************
@c % *                                Input file                             *
@c % *************************************************************************/
@node Writing The Input File
@section Writing The Input File

The input file of Clan is a source code file written in any language based on
C for the @code{for} loop, the @code{if} and for the array accesses.
C, C++, Java and C# are good examples that should work pretty well with Clan.

The input file may contain a static control part (i.e., a part of the
program that can be represented using the Polyhedral Model as described in
the corresponding chapter, @pxref{Polyhedral Representation}) delimitated
@strong{by the user} thanks to pragmas. Clan trusts the user: it will not check
hardly whether the program part is actually a SCoP or not. It will only try to
translate the program part to a polyhedral representation and will fail with
@emph{syntax error} if it reads something wrong.

In C, C++ and C#, the pragma to tag the beginning of the SCoP is:
@example
@group
#pragma scop
@end group
@end example
@noindent and the pragma to tag the end of the SCoP is:
@example
@group
#pragma endscop
@end group
@end example

In Java, the pragma to tag the beginning of the SCoP is:
@example
@group
/*@@ scop */
@end group
@end example
@noindent and the pragma to tag the end of the SCoP is:
@example
@group
/*@@ end scop */
@end group
@end example



@c %/*************************************************************************
@c % *                               Output file                             *
@c % *************************************************************************/
@node Reading The Output File
@section Reading The Output File

The output text file of Clan provides an explicit polyhedral representation of
a static control part. The output file format is called @emph{.scop} format.
It has been designed by various researchers in polyhedral compilation from
various institutions. It builds on previous popular polyhedral file formats
like @emph{.cloog} to provide a unique, extensible file format to every
polyhedral compilation tools (including future versions of CLooG). This file
is composed of two main parts. The first part is devoted to the polyhedral
representation of a SCoP. It contains what is strictly necessary to enter a
complete source-to-source framework in the polyhedral model and to output a
semantically equivalent code for the SCoP, from analysis to code generation.
The second part of the file contains options, i.e. extensions to provide
additional informations to some tools.

The following grammar describes the structure of the first part of the
.scop file format where terminals are preceeded by "_". Each
relevant part will be explained in more details momentarily. Its looks
long but it has been artificially extended to be easily understood and
it can be easily simplified:

@example
File                ::= SCoP
SCoP                ::= "SCoP"   Context Statements
Context             ::= Language Domain  Parameters
Statements          ::= Nb_statements Statement_list
String_list         ::= _String   String_list    | (void)
Statement_list      ::= Statement Statement_list | (void)
Domain_list         ::= Domain    Domain_list    | (void)
Statement           ::= Iteration_domain Scattering Access Body
Iteration_domain    ::= Domain_union
Domain_union        ::= Nb_domains Domain_list
Scattering          ::= "0" | "1" Scattering_function
Access              ::= "0" | "1" Read_function Write_function
Parameters          ::= "0" | "1" Parameter_list
Body                ::= "0" | "1" Iterator_list Body_text
Language            ::= "C" | "C++" | "C#" | "Java" | "Toy"
Parameter_list      ::= String_list
Iterator_list       ::= String_list
Domain              ::= _Matrix
Scattering_function ::= _Matrix
Read_function       ::= _Matrix
Write_function      ::= _Matrix
Nb_statements       ::= _Integer
Nb_domains          ::= _Integer
Body_text           ::= _String
@end example


@itemize @bullet
@item  @samp{Context} represents the informations that are
       shared by all the statements. It consists on
       the language used (which can be @samp{C}, @samp{C++}, @samp{C#}
       or @samp{Java}), the global constraints on parameters and
       optionally the parameter names. The set of constraints on parameters is
       essential since it provides the number of parameters. The @samp{Domain}
       encoding includes the number of unknown (here the number of parameters)
       (@pxref{Domain Representation}). Even if there are no constraints, this
       number has to be correct.
       After the constraints, it is possible to provide the list of parameter
       names (the textual names in the original program). A @samp{0} means
       we don't provide the list of parameter names, and a @samp{1} means
       the list of parameter names is provided afterward. The original
       parameter names
       are necessary for the code generator to be able to generate a code
       that can replace directly the SCoP in the original program by
       copy/paste. In the case of a @samp{0}, parameter names will probably
       be generated by the code generator (this is the case when using CLooG)
       or will be extracted from another input source.
@item  @samp{Statements} represents the informations on the statements.
       @samp{Nb_statements} is the number of statements in the program,
       i.e. the number of @samp{Statement} items in the @samp{Statement_list}.
       @samp{Statement} represents the informations on a given statement.
       To each statement is associated four informations, the first one is
       mandatory while the three others are optional. The statement iteration
       domain @samp{Iteration_domain} is the required information, then one can
       provide optionally a scattering function, the access functions and
       the statement body, in this order. Each optional information is
       preceeded by a boolean that precises whether the optional information is
       provided or not.
       The iteration domain (@pxref{Iteration Domain}) is represented using a
       matrix (@pxref{Domain Representation}). Next, the scattering function
       (@pxref{Scattering Function}) is represented using a matrix as well
       (@pxref{Scattering Representation}). The access functions
       (@pxref{Access Function}) are represented using two matrices, one for read
       accesses and another one for write accesses
       (@pxref{Access Representation}). The statement body is made of two
       parts: first, the list of surrounding loop counters in the original
       program and second, the text string of the statement. This
       representation allows to apply the substitution of the original
       iterators with new iterators in the target program.
@end itemize

The main terminal parts (domains, scattering and access functions) are
detailed in the next subsections. Lastly, we will describe the option part
(@pxref{Option Part}).

@menu
* Domain Representation::
* Scattering Representation::
* Access Representation::
* Option Part::
@end menu

@node Domain Representation
@subsection Domain Representation
As shown by the grammar, the input file describes the various informations
thanks to strings, integers and domains. Each domain is defined by a set of
constraints in the PolyLib format (@pxref{Wil93}). They have the
following syntax:
@enumerate
@item Some optional comment lines beginning with @samp{#}.
@item The row and column numbers, possibly followed by comments.
@item The constraint rows. Each row corresponds to a constraint the
      domain have to satisfy. Each row must be on a single line and is possibly
      followed by comments. The constraint is an equality @math{p(x) = 0} if the
      first element is 0, an inequality  @math{p(x) \geq 0} if the first element
      is 1. The next elements are the unknown coefficients, followed by
      the parameter coefficients. The last element is the constant factor.
@end enumerate
For instance, assuming that @samp{i}, @samp{j} and @samp{k} are the loop
iterators and @samp{m} and @samp{n} are the parameters, the domain defined by
the following constraints :

@tex
$$
\hbox{$ \cases{ -i     + m &$\geq 0$\cr
                    -j + n &$\geq 0$\cr
                 i + j - k &$\geq 0$}$}
$$
@end tex
@ifnottex
@example
@group
   -i + m >= 0
   -j + n >= 0
i + j - k >= 0
@end group
@end example
@end ifnottex

@noindent can be written in the input file as follows :

@example
@group
# This is a domain
3 7                      # 3 lines and 7 columns
# eq/in i  j  k  m  n  1
    1  -1  0  0  1  0  0 #    -i + m >= 0
    1   0 -1  0  0  1  0 #    -j + n >= 0
    1   1  1 -1  0  0  0 # i + j - k >= 0
@end group
@end example

Each iteration domain @samp{Iteration_domain} of a given statement
is a @emph{union} of polyhedra
@samp{Domain_union}. A union is defined by its number of elements
@samp{Nb_domains} and the elements themselves @samp{Domain_list}.
For instance, let us consider the following pseudo-code:

@example
@group
for (i = 1; i <= n; i++) @{
  if ((i >= m) || (i <= 2*m))
    S1;
@}
@end group
@end example

@noindent The iteration domain of @samp{S1} can be divided into two
polyhedra and written in the .scop file as follows:

@example
@group
2 # Number of polyhedra in the union
# First domain
3 5                # 3 lines and 5 columns
# eq/in i  m  n  1
    1   1  0  0 -1 #  i >= 1
    1  -1  0  1  0 #  i <= n
    1   1 -1  0  0 #  i >= m
# Second domain
3 5                # 3 lines and 5 columns
# eq/in i  m  n  1
    1   1  0  0 -1 #  i >= 1
    1  -1  0  1  0 #  i <= n
    1  -1  2  0  0 #  i <= 2*m
@end group
@end example

@node Scattering Representation
@subsection Scattering Representation
Scattering functions are depicted in the input file thanks a representation
very close to the domain one. The difference is each row do not describe a
constraint but a scattering function dimension (@pxref{Scattering Function}).
By convention, the first element of each row (the one that defines whether
the constraint is an equality or an inequality for domains)
@emph{must be set to 0}. The next elements are the unknown coefficients,
followed by the parameter coefficients. The last element is the constant
factor. For instance, assuming that @samp{i}, @samp{j} and @samp{k} are the loop
iterators and @samp{m} and @samp{n} are the parameters, the scattering
function
@tex
$\theta_{S}(i,j,k) = (j+2,3*i+j,k+n+1)$
@end tex
@ifnottex
@example
T_@{S@}(i,j,k) = (j+2,3*i+j,k+n+1)
@end example
@end ifnottex
may be written in a .scop file in the following way:

@example
@group
# A scattering function
3 7                      # 3 dimensions and 7 columns
# 0  i  j  k  m  n  1
  0  0  1  0  0  0  2    # j+2
  0  3  1  0  0  0  0    # 3*i+j
  0  0  0  1  0  1  1    # k+n+1
@end group
@end example

Note that this representation is different from the .cloog format: the useless
and error-prone identity matrix part disappeared.

The scattering function extracted by Clan is the scheduling of the original
program as described in a previous section (@pxref{Scattering Function}). It
allows a code generator (like CLooG) to reconstruct directly the original
program or a dependence analyzer (like Candl) to achieve its data dependence
calculation.

@node Access Representation
@subsection Access Representation

Access functions are depicted in the input file thanks a representation
very close to the domain one. The difference is each row do not describe a
constraint but a access function dimension (@pxref{Access Function}).
Moreover, the matrix representation do not describes only one access function
but a set of access functions. Each array accessed in the SCoP has a unique
strictly positive identification number. The first element of each row (the
one that defines whether the constraint is an equality or an inequality for
domains) corresponds to the array identifier iff the row corresponds to the
first dimension of the access function. If the first element is 0, this means
the row corresponds to the next dimension of the access function, with respect
to the previous row. The next elements are the unknown coefficients,
followed by the parameter coefficients. The last element is the constant
factor. For instance, assuming that @samp{i}, @samp{j} and @samp{k} are the loop
iterators and @samp{m} and @samp{n} are the parameters, the set of array
accesses @code{A[2*i+j][j][i+n]}, @code{B[i+j]} and @code{A[k][j][1]} (the
identifier of @code{A} is 1 and the identifier of @code{B} is 2)
may be written in a .scop file in the following way:

@example
@group
# A set of access functions
7 7                      # 7 rows and 7 columns
# id  i  j  k  m  n  1
   1  2  1  0  0  0  0   # A[2*i+j][j][i+n]
   0  0  1  0  0  0  0   #
   0  1  0  0  0  1  0   #
   2  1  1  0  0  0  0   # B[i+j]
   1  0  0  1  0  0  0   # A[k][j][1]
   0  0  1  0  0  0  0   #
   0  0  0  0  0  0  1   #
@end group
@end example


@node Option Part
@subsection Option Part

The end of the .scop file is made of a succession of options delimited using
XML-like tags. Each tool will take care of known options and will ignore the
others. There is no specification for the option body as it is
tool-dependent. Nevertheless, authors are invited to put the name of
the tool inside the option name to avoid conflicts. A reserved
option name is @samp{Comments} that allows to put some comments in the second
part of the .scop file. For instance, this could be a possible
second part of a .scop file:

@example
@group
<Comments>
    Just a comment example.
<\Comments>

<CLooG foobar>
    This is supposed to provide CLooG some interesting
    additional informations.
<\CLooG foobar>
@end group
@end example

A second reserved name is @samp{arrays}, Clan can optionally print a
table of the arrays referenced in the access functions. For instance, for a program referencing first the array @samp{FOO}, then the array @samp{BAR}:

@example
@group
<arrays>
# Number of referenced arrays
2
# First reference
1 FOO
# Second reference
2 BAR
</arrays>
@end group
@end example



@c %/*************************************************************************
@c % *                              Calling Clan                             *
@c % *************************************************************************/
@node Calling Clan
@section Calling Clan
Clan is called by the following command:
@example
       clan [ options | file ]
@end example
The default behavior of Clan is to read the input source code from a file and
to print the generated .scop file on the standard output.
Clan's behavior and the output file are under the user control thanks
to some options which will be detailed momentarily (@pxref{Clan Options}).
@code{file} is the input file. @code{stdin} is a special value: when used,
input is standard input. For instance, we can call Clan to process the
input file @code{basic.c} with default options by typing:
@code{clan basic.c} or @code{more basic.c | clan stdin}
(usual @code{more basic.c | clan -} works too).


@c %/*************************************************************************
@c % *                              Clan Options                             *
@c % *************************************************************************/
@node Clan Options
@section Clan Options

@menu
* Output::
* Arrays Tag::
* Help::
* Version ::
@end menu

@node Output
@subsection Output @code{-o <output>}

     @code{-o <output>}: this option sets the output file. @code{stdout} is a
     special value: when used, output is standard output.
     Default value is @code{stdout}.

@node Arrays Tag
@subsection Arrays Tag @code{-arraystag}

@code{-arraystag}: this option dumps the table of referenced arrays at
the end of the .scop file, between the @samp{<arrays>} and
@samp{</arrays} tags.

@node Help
@subsection Help @code{--help} or @code{-h}

     @code{--help} or @code{-h}: this option asks Clan to print a short help.

@node Version
@subsection Version @code{--version} or @code{-v}

     @code{--version} or @code{-v}: this option asks Clan to print some
     release and version informations.


@c %/*************************************************************************
@c % *                 OpenScop Data Structure Specification                 *
@c % *************************************************************************/
@node OpenScop Data Structure Specification
@chapter OpenScop Data Structure Specification
The Clan Library was implemented to allow the user to call Clan
directly from his programs, without file accesses or system calls. The
user only needs to link his programs with C libraries. The Clan
library mainly provides one function (@code{clan_scop_extract})
which takes as input the source code file to process with some options,
and returns the data structure corresponding
to the SCoP (a @code{clan_scop_t} structure) which contains the
polyhedral representation of the SCoP.
The user can work with this data structure and/or use
the printing function to output a .scop file.
Some other functions are provided for convenience reasons.
These functions as well as the data structures are described in this section.

@menu
* Clan Data Structures::
* Clan Functions::
* Example of Library Utilization::
@end menu


@node Clan Data Structures
@section Clan Data Structures Description
In this section, we describe the data structures used by the loop
analyzer to represent and to process a SCoP. As this is not a developer's
guide, data structure devoted to internal use as well as internal use
fields are not described here.

@menu
* clan_matrix_t::
* clan_matrix_list_t::
* clan_statement_t::
* clan_scop_t::
* clan_options_t::
@end menu


@node clan_matrix_t
@subsection clan_matrix_t

@noindent The @code{clan_matrix_t} structure is the same as the PolyLib
@code{Matrix} data structure (@pxref{Wil93}) in order to be used
directly by tools using this format with a simple cast.

@example
@group
struct clan_matrix
@{
  unsigned NbRows;     /* The number of rows */
  unsigned NbColumns;  /* The number of columns */
  clan_int_t ** p;     /* An array of pointers to the matrix row */
  clan_int_t * p_Init; /* The matrix rows contiguously in memory */
  int p_Init_size;     /* Initial size of p_Init */
@};
typedef struct clan_matrix   clan_matrix_t;
typedef struct clan_matrix * clan_matrix_p;
@end group
@end example

@noindent The whole matrix is stored in memory row after row at the
@code{p_Init} address. @code{p} is an array of pointers where
@code{p[i]} points to the first element of the @math{i^{th}} row.
@code{NbRows} and @code{NbColumns} are respectively the number of
rows and columns of the matrix.

@noindent To be able to provide different precision versions (Clan
supports 32 bits, 64 bits and arbitrary precision through the GMP library),
the @code{clan_int_t} type depends on the configuration options (it may be
@code{long int} for 32 bits version, @code{long long int} for 64 bits version,
and @code{mpz_t} for multiple precision version).
The @code{p_Init_size} field is needed to free
the memory allocated by @code{mpz_init} in the multiple precision version.
Set this field to the initial size of the @code{p_Init} array
(its size may vary during processing, for instance if you are using PolyLib).


@node clan_matrix_list_t
@subsection clan_matrix_list_t

@example
@group
struct clan_matrix_list
@{
  clan_matrix_p elt;             /* An element of the list. */
  struct clan_matrix_list* next; /* Pointer to the next element. */
@};
typedef struct clan_matrix_list   clan_matrix_list_t;
typedef struct clan_matrix_list * clan_matrix_list_p;
@end group
@end example

@noindent The @code{clan_matrix_list_t} structure is a @code{NULL}-terminated
linked list of @code{clan_matrix_t} data structures. It is used for instance
to represent a union of convex domains (each matrix representing a convex
part of the union). @code{elt} is a matrix element of the list and
@code{next} is the pointer to the next element of the list.


@node clan_statement_t
@subsection clan_statement_t
@example
@group
struct clan_statement
@{
  clan_matrix_list_p domain;    /* Iteration domain */
  clan_matrix_p scattering;     /* Scattering function */
  clan_matrix_p read;           /* Array read access informations */
  clan_matrix_p write;          /* Array write access informations */
  int nb_iterators;             /* Original depth of the statement */
  char ** iterators;            /* Array of iterator names */
  char * body;                  /* Original statement body */
  struct clan_statement * next; /* Next statement in the linked list */
@};
typedef struct clan_statement   clan_statement_t;
typedef struct clan_statement * clan_statement_p;
@end group
@end example

@noindent The @code{clan_statement_t} structure represents a @code{NULL}
terminated linked list of statements. The structure contains all
elements of the polyhedral representation of the statement. It uses a
@code{clan_matrix_list_t} data structure to represent a union for the
iteration domain @code{domain} (it is simply a linked list of
@code{clan_matrix_t} elements), and a @code{clan_matrix_t} data
structure for the rest: the scattering function @code{scattering}, the
set of array read accesses @code{read} and the set of array write
accesses @code{write}.  The particular representation of each element
using the @code{clan_matrix_t} data structure is described with the
output file format (@pxref{Reading The Output File}). If an element is
not present, the according pointer have to be @code{NULL}.  The
@code{nb_iterators} field gives the depth of the statement in the
original program. It may be used with any matrix to compute the number
of parameters (e.g.  @code{nb_parameters = domain->NbColumns -
nb_iterators - 2}) To represent the statement body, we use
@code{iterators}, an array of @code{nb_iterators} strings for the
surrounding loop counters names in the original program, and
@code{body}, the statement body string in the original program.

@node clan_scop_t
@subsection clan_scop_t
@example
@group
struct clan_scop
@{
  clan_matrix_p context;      /* Constraints on the SCoP parameters */
  int nb_parameters;          /* Number of parameters for the SCoP */
  char ** parameters;         /* Array of parameter names */
  int nb_arrays;              /* Number of arrays accessed in the SCoP */
  char ** arrays;             /* Array of array names */
  clan_statement_p statement; /* Statement list of the SCoP */
  char * optiontags;          /* The content (as a 0 terminated
                                 string) of the optional tags. */
  void * usr;                 /* A user-defined field,
                                 not touched by clan. */
@};
typedef struct clan_scop   clan_scop_t;
typedef struct clan_scop * clan_scop_p;
@end group
@end example

@noindent @code{clan_scop_t} stores the useful informations of a static
control part of a program to process it within a polyhedral framework.
It contains the informations about the context (what is common to all
statements in the SCoP) and the list of statements @code{statement}.
The context is made of the constraints on the global parameters
@code{context}. The representation of the context using the
@code{clan_matrix_t} data structure is described with the output file
format (this is a domain, @pxref{Reading The Output File}).  The list of
parameter names is provided as an array of @code{nb_parameters} strings
called @code{parameters} (@code{nb_parameters} is somewhat redundant as
it is supposed to be equal to @code{context->NbColumns - 2}). The list
of array names is provided as an array of @code{nb_arrays} strings
called @code{arrays}. Each accessed array in the SCoP has a unique
identifier (a strictly positive number, @pxref{Access Representation}),
@code{arrays} provides the correspondance between an identifier and the
real name of the accessed array. If an array has the identifier
@samp{id}, then its real name is @samp{arrays[id - 1]}. The
@code{optiontags} field contains the remainder of the SCoP description
file, as a @code{char*} string. Optional tags specified in the
@samp{Options} section are stored there. Finally, the @code{usr} field
is a pointer for library users convenience. This field is not touched by
Clan.

As an example, let us consider again the matrix-matrix multiply program
(@pxref{A First Example}).
The next figure gives a possible representation in memory for this
SCoP thanks to the Clan data structures (it has been actually printed
by the @code{clan_scop_print} function, it is also possible to ask Clan to
output the internal representation using the command line option
@code{-structure}):

@smallexample
+-- clan_scop_t
|       |
|       +-- clan_matrix_t
|       |       0 3
|       |
|       +-- Original parameters strings: N
|       |
|       +-- Accessed array strings: c a b
|       |
|       +-- clan_statement_t (S1)
|       |       |
|       |       +-- clan_matrix_list_t
|       |       |       |       
|       |       |       +-- clan_matrix_t
|       |       |       |       4 5
|       |       |       |       [    1    1    0    0    0 ]
|       |       |       |       [    1   -1    0    1   -1 ]
|       |       |       |       [    1    0    1    0    0 ]
|       |       |       |       [    1    0   -1    1   -1 ]
|       |       |       |       
|       |       |       
|       |       +-- clan_matrix_t
|       |       |       5 5
|       |       |       [    0    0    0    0    0 ]
|       |       |       [    0    1    0    0    0 ]
|       |       |       [    0    0    0    0    0 ]
|       |       |       [    0    0    1    0    0 ]
|       |       |       [    0    0    0    0    0 ]
|       |       |
|       |       +-- NULL matrix
|       |       |
|       |       +-- clan_matrix_t
|       |       |       2 5
|       |       |       [    1    1    0    0    0 ]
|       |       |       [    0    0    1    0    0 ]
|       |       |
|       |       +-- Original iterator strings: i j
|       |       |
|       |       +-- Original body: c[i][j]=0.0;
|       |       |
|       |       V
|       |   clan_statement_t (S2)
|       |       |
|       |       +-- clan_matrix_list_t
|       |       |       |       
|       |       |       +-- clan_matrix_t
|       |       |       |       6 6
|       |       |       |       [    1    1    0    0    0    0 ]
|       |       |       |       [    1   -1    0    0    1   -1 ]
|       |       |       |       [    1    0    1    0    0    0 ]
|       |       |       |       [    1    0   -1    0    1   -1 ]
|       |       |       |       [    1    0    0    1    0    0 ]
|       |       |       |       [    1    0    0   -1    1   -1 ]
|       |       |       |       
|       |       |
|       |       +-- clan_matrix_t
|       |       |       7 6
|       |       |       [    0    0    0    0    0    0 ]
|       |       |       [    0    1    0    0    0    0 ]
|       |       |       [    0    0    0    0    0    0 ]
|       |       |       [    0    0    1    0    0    0 ]
|       |       |       [    0    0    0    0    0    1 ]
|       |       |       [    0    0    0    1    0    0 ]
|       |       |       [    0    0    0    0    0    0 ]
|       |       |
|       |       +-- clan_matrix_t
|       |       |       6 6
|       |       |       [    1    1    0    0    0    0 ]
|       |       |       [    0    0    1    0    0    0 ]
|       |       |       [    2    1    0    0    0    0 ]
|       |       |       [    0    0    0    1    0    0 ]
|       |       |       [    3    0    0    1    0    0 ]
|       |       |       [    0    0    1    0    0    0 ]
|       |       |
|       |       +-- clan_matrix_t
|       |       |       2 6
|       |       |       [    1    1    0    0    0    0 ]
|       |       |       [    0    0    1    0    0    0 ]
|       |       |
|       |       +-- Original iterator strings: i j k
|       |       |
|       |       +-- Original body: c[i][j]=c[i][j]+a[i][k]*b[k][j];
|       |       |
|       |
|
@end smallexample


@node clan_options_t
@subsection clan_options_t
@example
@group
struct clan_options
@{
  char * name ;  /* Name of the input file. */
@};
typedef struct clan_options   clan_options_t;
typedef struct clan_options * clan_options_p;
@end group
@end example

@noindent The @code{clan_options_t} structure contains all the possible
options to rule Clan's behaviour (@pxref{Calling Clan}). For the moment there
are mainly internal options, but it's going to change in the future.


@node Clan Functions
@section Clan Functions Description

@menu
* clan_scop_extract::
* clan_scop_print_dot_scop::
* clan_scop_read::
* clan_scop_tag_content::
* Allocation and Initialization Functions::
* Memory Deallocation Functions::
* Printing Functions::
@end menu


@node clan_scop_extract
@subsection clan_scop_extract
@example
@group
clan_scop_p clan_scop_extract(FILE * input, clan_options_p options);
@end group
@end example

@noindent The @code{clan_scop_extract} function extracts the polyhedral
representation of a SCoP in the file provided thanks to the @code{input}
pointer (the file, possibly @code{stdin}, has to be open for reading),
according to some options
provided thanks to the pointer @code{options} to a @code{clan_options_t}
data structure (@pxref{clan_options_t}). It returns a pointer to the
extracted SCoP, translated into
a @code{clan_scop_t} data structure (@pxref{clan_scop_t}).

@node clan_scop_print_dot_scop
@subsection clan_scop_print_dot_scop
@example
@group
void clan_scop_print_dot_scop
(
  FILE * output,
  clan_scop_p scop,
  clan_options_p options
);
@end group
@end example

@noindent The function @code{clan_scop_print_dot_scop} is a pretty printer for
@code{clan_scop_t} structures. It dumps the @code{scop} informations in
.scop format (@pxref{Reading The Output File}) in the file provided thanks to
the pointer @code{output} (the file, possibly @code{stdout}, has to be open
for writing), according to some options provided thanks to the pointer
@code{options} to a @code{clan_options_t} data structure
(@pxref{clan_options_t}).



@node clan_scop_read
@subsection clan_scop_read
@example
@group
clan_scop_p clan_scop_read
(
  FILE * input,
  clan_options_p options
);
@end group
@end example

@noindent The function @code{clan_scop_read} reads a .scop file from
the standard input, and returns a pointer on a freshly allocated
@code{clan_scop_t} structure containing the SCoP information.


@node clan_scop_tag_content
@subsection clan_scop_tag_content
@example
@group
char* clan_scop_tag_content
(
  clan_scop_p scop,
  char* from,
  char* to
);
@end group
@end example

@noindent The function @code{clan_scop_tag_content} reads the list of
optional tags for the @code{clan_scop_t} (stored in the
@code{optiontags} string), and returns a freshly allocated string of all
characters between the two given strings @code{from} and @code{to}. If
one or the other given strings are not found, or if there was no
optional part specified in the .scop, @code{NULL} is returned.


@node Allocation and Initialization Functions
@subsection Allocation and Initialization Functions
@example
clan_structure_p clan_structure_malloc();
@end example
@noindent Each Clan data structure has an allocation and initialization
function as shown above, where @code{structure} have to
be replaced by the name of the convenient structure (without @samp{clan}
prefix and @samp{_t} suffix) for
instance @code{clan_scop_p clan_scop_malloc();}. These functions return
pointers to an allocated structure with fields set to convenient default
values. @strong{Using those functions is mandatory} to support internal
management fields and to avoid upward compatibility problems if
new fields appear. An exception is @code{clan_matrix_malloc} since the
@code{clan_matrix_t} needs two parameters:
the number of rows and columns of the matrix we want to allocate:
@example
clan_matrix_p clan_matrix_malloc(unsigned nbrows, unsigned nbcolumns);
@end example


@node Memory Deallocation Functions
@subsection Memory Deallocation Functions
@example
void clan_structure_free(clan_structure_p);
@end example
@noindent Each Clan data structure has a deallocation function as shown above,
where @code{structure} have to
be replaced by the name of the convenient structure (without @samp{clan}
prefix and @samp{_t} suffix) for
instance @code{void clan_scop_free(clan_scop_p);}. These functions
free the allocated memory for the structure provided as input. They free
memory recursively, i.e. they also free the allocated memory for the internal
structures.
@strong{Using those functions is mandatory} to avoid memory leaks on internal
management fields and to avoid upward compatibility problems if
new fields appear.


@node Printing Functions
@subsection Printing Functions
@example
void clan_structure_print(FILE *, clan_structure_p) ;
@end example
@noindent Each Clan data structure has a printing function as shown above,
where @code{structure} have to
be replaced by the name of the convenient structure (without @samp{clan}
prefix and @samp{_t} suffix) for
instance @code{void clan_scop_print(FILE *, clan_scop_p);}. These functions
print the pointed structure (and its fields recursively) to the file provided
as input (the file, possibly @code{stdout}, has to be open
for writing).


@node Example of Library Utilization
@section Example of Library Utilization
Here is a basic example showing how it is possible to use the Clan library,
assuming that a standard installation has been done.
The following C program reads a source code input file on the standard input,
then prints the solution on the standard output.
Options are preselected to the default values of the Clan software.
@example
/* example.c */
# include <stdio.h>
# include <clan/clan.h>

int main()
@{
  clan_scop_p scop;
  clan_options_p options;

  /* Default option setting. */
  options = clan_options_malloc() ;

  /* Extraction of the SCoP. */
  scop = clan_scop_extract(stdin, options);

  /* Output of the .scop file. */
  clan_scop_print_dot_scop(stdout, scop, options);

  /* Save the planet. */
  clan_options_free(options);
  clan_scop_free(scop);

  return 0;
@}
@end example

@noindent The compilation command could be:
@example
gcc example.c -lclan -o example
@end example
@noindent A calling command with the input file test.c could be:
@example
more test.c | ./example
@end example



@c %  ****************************** INSTALLING ********************************
@node Installing
@chapter Installing Clan

@menu
* License::
* Requirements::
* Basic Installation::
* Optional Features::
* Uninstallation::
@end menu

@node License
@section License
First of all, it would be very kind to refer the following paper in any
publication that result from the use of the Clan software or its library,
@pxref{Bas03} (a bibtex entry is provided behind the title page of this
manual, along with copyright notice).

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public License
as published by the Free Software Foundation,
either version 3 of the  License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
@code{http://www.gnu.org/copyleft/lgpl.html}


@node Requirements
@section Requirements


Clan is a stand-alone tool and library. For a basic use, it does not need any
additional tool or library. Anyway, to be able to work in conjunction with
other tools that manipulate multiple precision numbers, the GNU GMP library
can be used as an option.


@menu
* GMP Library::
@end menu


@node GMP Library
@subsection GMP Library (optional)

To be able to deal with insanely large coefficient, the user will need to
install the GNU Multiple Precision Library (GMP for short) version 4.2.2
or above. It can be freely downloaded from @code{http://www.swox.com/gmp}.
The user can compile it by typing the following commands on the GMP root
directory:

@itemize @bullet
@item @code{./configure}
@item @code{make}
@item And as root: @code{make install}
@end itemize

The GMP default installation is @code{/usr/local}. This directory may
not be inside your library path. To fix the problem, the user should set
@example
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib
@end example
@noindent if your shell is, e.g., bash or
@example
setenv LD_LIBRARY_PATH $LD_LIBRARY_PATH:/usr/local/lib
@end example
@noindent if your shell is, e.g., tcsh. Add the line to your .bashrc or .tcshrc (or
whatever convenient file) to make this change permanent. Another solution
is to ask GMP to install in the standard path by using the prefix
option of the configure script:
@samp{./configure --prefix=/usr}.

Clan has to be built using the GMP library by specifying the convenient
configure script options to buid the GMP version (@pxref{Optional Features}).


@node Basic Installation
@section Clan Basic Installation

Once downloaded and unpacked
(e.g. using the @samp{tar -zxvf clan-@value{VERSION}.tar.gz} command),
you can compile Clan by typing the following commands on the Clan's root
directory:

@itemize @bullet
@item @code{./configure}
@item @code{make}
@item And as root: @code{make install}
@end itemize

The program binaries and object files can be removed from the
source code directory by typing @code{make clean}. To also remove the
files that the @code{configure} script created (so you can compile the
package for a different kind of computer) type @code{make distclean}.


@node Optional Features
@section Optional Features
The @code{configure} shell script attempts to guess correct values for
various system-dependent variables and user options used during compilation.
It uses those values to create the @code{Makefile}. Various user options
are provided by the Clan's configure script. They are summarized in the
following list and may be printed by typing @code{./configure --help} in the
Clan top-level directory.

@itemize @bullet
@item By default, the installation directory is @code{/usr/local}:
@code{make install} will install the package's files in
@code{/usr/local/bin}, @code{/usr/local/lib} and @code{/usr/local/include}.
The user can specify an installation prefix other than @code{/usr/local} by
giving @code{configure} the option @code{--prefix=PATH}.

@item By default, Clan is built in 64bits version. If the user give to
@code{configure} the option
@code{--enable-int-version}, the 32bits version of Clan will be compiled.
In the same way, the option @code{--enable-mp-version} have to be used to
build the multiple precision version.

@item By default, @code{configure} will look for the GMP library
(necessary to build the multiple precision version) in standard
locations. If necessary, the user can specify the GMP path by giving
@code{configure} the option @code{--with-gmp=PATH}.
@end itemize

@node Uninstallation
@section Uninstallation
The user can easily remove the Clan software and library from his system
by typing (as root if necessary) from the Clan top-level directory
@code{make uninstall}.

@c %  **************************** DOCUMENTATION ******************************
@node Documentation
@chapter Documentation
The Clan distribution provides several documentation sources. First, the
source code itself is as documented as possible. The code comments use a
Doxygen-compatible presentation (something similar to what JavaDoc does for
JAVA). The user may install Doxygen
(see @code{http://www.stack.nl/~dimitri/doxygen}) to automatically
generate a technical documentation by typing @code{make doc} or
@code{doxygen ./autoconf/Doxyfile} at the Clan top-level directory after
running the configure script (@pxref{Installing}). Doxygen will generate
documentation sources (in HTML, LaTeX and man) in the @code{doc/source}
directory of the Clan distribution.

The Texinfo sources of the present document are also provided in the @code{doc}
directory. You can build it in either DVI format (by typing
@code{texi2dvi cloog.texi}) or PDF format
(by typing @code{texi2pdf cloog.texi}) or HTML format
(by typing @code{makeinfo --html cloog.texi}, using @code{--no-split}
option to generate a single HTML file) or info format
(by typing @code{makeinfo cloog.texi}).

@c %  ****************************** REFERENCES ********************************
@node References
@chapter References

@itemize
@item
@anchor{Bas03a}[Bas03a] C. Bastoul, P. Feautrier. Improving data locality
by chunking. CC'12 International Conference on Compiler Construction,
LNCS 2622, pages 320-335, Warsaw, april 2003.

@item
@anchor{Bas03}[Bas03] C. Bastoul and A. Cohen and S. Girbal and
S. Sharma and O. Temam. Putting Polyhedral Loop Transformations to
Work, LCPC'16 International Workshop on Languages and
Compilers for Parallel Computers, LNCS 2958, pages 209--225,
College Station, Texas, october 2003.

@item
@anchor{Fea92}[Fea92] P. Feautrier Some efficient solutions to the affine
scheduling problem, part II: multidimensional time.
International Journal of Parallel Programming, 21(6):389--420, December 1992.

@item
@anchor{Gri04}[Gri04] M. Griebl. Automatic parallelization of loop programs
for distributed memory architectures. Habilitation Thesis. Facult@"at f@"ur
Mathematik und Informatik, Universit@"at Passau, 2004.
@emph{http://www.infosun.fmi.uni-passau.de/cl/loopo/}

@item
@anchor{Wil93}[Wil93] Doran K. Wilde.
A library for doing polyhedral operations.
Technical Report 785, IRISA, Rennes, France, 1993.

@end itemize




@c % /*************************************************************************
@c %  *                       PART VI: END OF THE DOCUMENT                    *
@c %  *************************************************************************/
@c @unnumbered Index

@c @printindex cp

@bye