statement-wise -f/-l options for loop separation
[cloog.git] / doc / cloog.texi
blobbcdc01546c034213034011c5270011ffdececb87
1 \input texinfo
2 @c %
3 @c %  /**-----------------------------------------------------------------**
4 @c %   **                              CLooG                              **
5 @c %   **-----------------------------------------------------------------**
6 @c %   **                            cloog.texi                           **
7 @c %   **-----------------------------------------------------------------**
8 @c %   **                   First version: july 6th 2002                  **
9 @c %   **-----------------------------------------------------------------**/
10 @c %
11 @c % release 1.0: September 17th 2002
12 @c % release 1.1: December   5th 2002
13 @c % release 1.2: April     22th 2003
14 @c % release 2.0: November  21th 2005 (and now in texinfo instead of LaTeX)
15 @c % release 2.1: October   15th 2007
16 @c %
17 @c %/**************************************************************************
18 @c % *               CLooG : the Chunky Loop Generator (experimental)         *
19 @c % **************************************************************************/
20 @c %/* CAUTION: the English used is probably the worst you ever read, please
21 @c % *          feel free to correct and improve it !
22 @c % */
24 @c %\textit{"I found the ultimate transformation functions, optimization for
25 @c %static control programs is now a closed problem, I have \textnormal{just}
26 @c %to generate the target code !"} 
30 @c % /*************************************************************************
31 @c %  *                              PART I: HEADER                           *
32 @c %  *************************************************************************/
33 @c %**start of header
34 @setfilename cloog.info
35 @settitle CLooG - a loop generator for scanning polyhedra
37 @set EDITION 2.1
38 @include gitversion.texi
39 @set UPDATED October 15th 2007
40 @setchapternewpage odd
42 @c %**end of header
44 @c % /*************************************************************************
45 @c %  *                 PART II: SUMMARY DESCRIPTION AND COPYRIGHT            *
46 @c %  *************************************************************************/
48 @copying
49 This manual is for CLooG version @value{VERSION}, a software
50 which generates loops for scanning Z-polyhedra. That is, CLooG produces a
51 code visiting each integral point of a union of parametrized
52 polyhedra. CLooG is designed to avoid control overhead and to produce a very
53 efficient code.
55 It would be quite kind to refer the following paper in any publication that
56 results from the use of the CLooG software or its library:
58 @example
59 @@InProceedings@{Bas04,
60 @ @ author =@ @ @ @ @{C. Bastoul@},
61 @ @ title =@ @ @ @ @ @{Code Generation in the Polyhedral Model
62 @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ Is Easier Than You Think@},
63 @ @ booktitle = @{PACT'13 IEEE International Conference on
64 @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ Parallel Architecture and Compilation Techniques@},
65 @ @ year =@ @ @ @ @ @ 2004,
66 @ @ pages =@ @ @ @ @ @{7--16@},
67 @ @ month =@ @ @ @ @ @{september@},
68 @ @ address =@ @ @ @{Juan-les-Pins@}
70 @end example
72 Copyright @copyright{} 2002-2005 C@'edric Bastoul.
74 @c quotation
75 Permission is granted to copy, distribute and/or modify this document under
76 the terms of the GNU Free Documentation License, Version 1.2 
77 published by the Free Software Foundation. To receive a copy of the
78 GNU Free Documentation License, write to the Free Software Foundation, Inc.,
79 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA.
80 @c end quotation
81 @end copying
83 @c % /*************************************************************************
84 @c %  *                 PART III: TITLEPAGE, CONTENTS, COPYRIGHT              *
85 @c %  *************************************************************************/
86 @titlepage
87 @title CLooG
88 @subtitle A Loop Generator For Scanning Polyhedra
89 @subtitle Edition @value{EDITION}, for CLooG @value{VERSION}
90 @subtitle @value{UPDATED}
91 @author C@'edric Bastoul
92      
93 @c The following two commands start the copyright page.
94 @page
95 @noindent (September 2001)
96 @table @code
97 @item C@'edric Bastoul
98 SCHEDULES GENERATE !!! I just need to apply them now, where can I find
99 a good code generator ?!
100      
101 @item Paul Feautrier
102 Hmmm. I fear that if you want something powerful enough, you'll have to
103 write it yourself !
104 @end table
106 @vskip 0pt plus 1filll
107 @insertcopying
108 @end titlepage
109      
110 @c Output the table of contents at the beginning.
111 @contents
113 @c % /*************************************************************************
114 @c %  *                     PART IV: TOP NODE AND MASTER MENU                 *
115 @c %  *************************************************************************/
116 @ifnottex
117 @node Top
118 @top CLooG
119      
120 @insertcopying
121 @end ifnottex
123 @menu
124 * Introduction::
125 * CLooG Software::
126 * CLooG Library::
127 @c * Hacking::
128 * Installing::
129 * Documentation::
130 * References::
131 @end menu
135 @c % /*************************************************************************
136 @c %  *                       PART V: BODY OF THE DOCUMENT                    *
137 @c %  *************************************************************************/
139 @c %  ****************************** INTRODUCTION ******************************
140 @node Introduction
141 @chapter Introduction
142 CLooG is a free software and library generating loops for scanning Z-polyhedra.
143 That is, it finds a code (e.g. in C, FORTRAN...) that reaches each integral
144 point of one or more parameterized polyhedra. CLooG has been originally
145 written to solve the code generation problem for optimizing compilers based on
146 the polytope model. Nevertheless it is used now in various area, e.g., to build
147 control automata for high-level synthesis or to find the best polynomial
148 approximation of a function. CLooG may help in any situation where scanning
149 polyhedra matters. It uses the best state-of-the-art code generation
150 algorithm known as the Quiller@'e et al. algorithm (@pxref{Qui00})
151 with our own improvements and extensions (@pxref{Bas04}).
152 The user has full control on generated code quality.
153 On one hand, generated code size has to be tuned for sake of
154 readability or instruction cache use. On the other hand, we must ensure that
155 a bad control management does not hamper performance of the generated code,
156 for instance by producing redundant guards or complex loop bounds.
157 CLooG is specially designed to avoid control overhead and to produce a very
158 efficient code.
160 CLooG stands for @emph{Chunky Loop Generator}: it is a part of the Chunky
161 project, a research tool for data locality improvement (@pxref{Bas03a}).
162 It is designed
163 also to be the back-end of automatic parallelizers like LooPo (@pxref{Gri04}).
164 Thus it is very
165 compilable code oriented and provides powerful program transformation
166 facilities. Mainly, it allows the user to specify very general schedules where, 
167 e.g., unimodularity or invertibility of the transformation doesn't matter.
169 The current version is still under
170 evaluation, and there is no guarantee that the upward compatibility
171 will be respected (but the previous API has been stable for two years,
172 we hope this one will be as successful -and we believe it-).
173 A lot of reports are necessary to freeze the library
174 API and the input file shape. Most API changes from 0.12.x to 0.14.x
175 have been requested by the users themselves.
176 Thus you are very welcome and encouraged
177 to post reports on bugs, wishes, critics, comments, suggestions or
178 successful experiences in the forum of @code{http://www.CLooG.org}
179 or to send them to cedric.bastoul@@inria.fr directly.
181 @menu
182 * Basics::
183 * Scattering::
184 @end menu
186 @node Basics
187 @section Basically, what's the point ?
188 If you want to use CLooG, this is because you want to scan or to find
189 something inside the integral points of a set of polyhedra. There are many
190 reasons for that. Maybe you need the generated code itself because it
191 actually implements a very smart program transformation you found.
192 Maybe you want to use the generated code
193 because you know that the solution of your problem belongs to the integral
194 points of those damned polyhedra and you don't know which one. Maybe you just
195 want to know if a polyhedron has integral points depending on some parameters,
196 which is the lexicographic minimum, maximum, the third on the basis of the
197 left etc. Probably you have your own reasons to use CLooG.
199 Let us illustrate a basic use of CLooG. Suppose we have a set of affine
200 constraints that describes a part of a whatever-dimensional space,
201 called a @strong{domain}, and we
202 want to scan it. Let us consider for instance the following set of constraints
203 where @samp{i}
204 and @samp{j} are the unknown (the two dimensions of the space) and
205 @samp{m} and @samp{n} are the parameters (some symbolic constants):
206 @example
207 @group
208 2<=i<=n
209 2<=j<=m
210 j<=n+2-i
211 @end group
212 @end example
213 Let us also consider that we have a partial knowledge of the parameter values,
214 called the @strong{context}, expressed as affine constraints as well,
215 for instance:
216 @example
217 @group
218 m>=2
219 n>=2
220 @end group
221 @end example
222 Note that using parameters is optional, if you are not comfortable with
223 parameter manipulation, just replace them with any scalar value that fits
224 @code{m>=2} and @code{n>=2}.
225 A graphical representation of this part of the 2-dimensional space, where
226 the integral points are represented using heavy dots would be for instance:
228 @image{images/basic,6cm}
230 The affine constraints of both the domain and the context are what we will
231 provide to CLooG as input (in a particular shape that will be described later).
232 The output of CLooG is a pseudo-code to scan the integral points of the
233 input domain according to the context:
234 @example
235 @group
236 for (i=2;i<=n;i++) @{
237   for (j=2;j<=min(m,-i+n+2);j++) @{    
238     S1(i,j) ;
239   @}
241 @end group
242 @end example
243 If you felt such a basic example is yet interesting, there is a good chance
244 that CLooG is appropriate for you. CLooG can do much more: scanning several
245 polyhedra or unions of polyhedra at the same time, applying general affine
246 transformations to the polyhedra, generate compilable code etc. Welcome
247 to the CLooG's user's guide !
249 @node Scattering
250 @section Defining a Scanning Order: Scattering Functions
251 In CLooG, domains only define the set of integral points to scan and their
252 coordinates. In particular, CLooG is free to choose the scanning order for
253 generating the most efficient code. This means, for optimizing/parallelizing
254 compiler people, that CLooG doesn't make any speculation on dependences on and
255 between statements (by the way, it's not its job !).
256 For instance, if an user give to
257 CLooG only two domains @code{S1:1<=i<=n}, @code{S2:1<=i<=n} and the context
258 @code{n>=1}, the following pseudo-codes are considered to be equivalent:
260 @example
261 @group
262 /* A convenient target pseudo-code. */
263 for (i=1;i<=N;i++) @{
264  S1(i) ;
266 for (i=1;i<=N;i++) @{
267  S2(i) ;
269 @end group
270 @end example
272 @example
273 @group
274 /* Another convenient target pseudo-code. */
275 for (i=1;i<=N;i++) @{
276  S1(i) ;
277  S2(i) ;
279 @end group
280 @end example
282 The default behaviour
283 of CLooG is to generate the second one, since it is optimized in control. 
284 It is right if there are no data dependences
285 between @code{S1} and @code{S2}, but wrong otherwise. 
287 Thus it is often useful to force scanning to respect a given order. This can be
288 done in CLooG by using @strong{scattering functions}. Scattering is a
289 shortcut for scheduling, allocation, chunking functions and the like we can
290 find in the restructuring compilation literature. There are a lot of reasons
291 to scatter the integral points of the domains (i.e. the statement instances
292 of a program, for compilation people), parallelization or optimization are good
293 examples. For instance, if the user wants for any reason to set some
294 precedence constraints between the statements of our example above
295 in order to force the generation of the
296 first code, he can do it easily by setting (for example) the following
297 scheduling functions:
299 @tex
300 $$\theta _{S1}(i) =  (1)$$
301 $$\theta _{S2}(j) =  (2)$$
302 @end tex
304 @ifnottex
305 @example
306 @group
307 T_S1(i) = (1)
308 T_S2(j) = (2)
309 @end group
310 @end example
311 @end ifnottex
313 This scattering means that each integral point of the domain @code{S1}
314 is scanned at logical date @code{1} while each integral point of the domain
315 @code{S2} is scanned at logical date @code{2}. As a result, the whole
316 domain @code{S1} is scanned before domain @code{S2} and the first code in our
317 example is generated.
319 The user can set every kind of affine scanning order thanks to the
320 scattering functions. Each domain has its own scattering function and
321 each scattering function may be multi-dimensional. A multi-dimensional logical
322 date may be seen as classical date (year,month,day,hour,minute,etc.) where
323 the first dimensions are the most significant. Each scattering dimension
324 may depend linearly on the original dimensions (e.g., @code{i}), the
325 parameters (e.g., @code{n}) ans scalars (e.g., @code{2}).
327 A very useful example of multi-dimensional scattering functions is, for
328 compilation people, the scheduling of the original program.
329 The basic data to use for code generation are statement iteration domains.
330 As we saw, these data are not sufficient to rebuild the original
331 program (what is the ordering between instances of different statements ?).
332 The missing data can be put in the scattering functions as the original
333 scheduling. The method to compute it is quite simple (@pxref{Fea92}). The idea is to
334 build an abstract syntax tree of the program and to read the scheduling for
335 each statement. For instance, let us consider the following implementation of
336 a Cholesky factorization:
338 @example
339 @group
340 /* A Cholesky factorization kernel. */
341 for (i=1;i<=N;i++) @{
342   for (j=1;j<=i-1;j++) @{
343     a[i][i] -= a[i][j] ;           /* S1 */
344   @}
345   a[i][i] = sqrt(a[i][i]) ;        /* S2 */
346   for (j=i+1;j<=N;j++) @{
347     for (k=1;k<=i-1;k++) @{
348       a[j][i] -= a[j][k]*a[i][k] ; /* S3 */
349     @}
350     a[j][i] /= a[i][i] ;           /* S4 */
351     @}
352   @}
354 @end group
355 @end example
357 The corresponding abstract syntax tree is given in the following figure.
358 It directly gives the scattering functions (schedules) for all the
359 statements of the program.
361 @image{images/tree,6cm}
363 @tex
365 \hbox{$ \cases{ \theta _{S1}(i,j)^T    &$=  (0,i,0,j,0)^T$\cr
366                 \theta _{S2}(i)        &$=  (0,i,1)^T$\cr
367                 \theta _{S3}(i,j,k)^T  &$=  (0,i,2,j,0,k,0)^T$\cr
368                 \theta _{S4}(i,j)^T    &$=  (0,i,2,j,1)^T$}$}
370 @end tex
372 @ifnottex
373 @example
374 @group
375 T_S1(i,j)^T   = (0,i,0,j,0)^T
376 T_S2(i)       = (0,i,1)^T
377 T_S3(i,j,k)^T = (0,i,2,j,0,k,0)^T
378 T_S4(i,j)^T   = (0,i,2,j,1)^T
379 @end group
380 @end example
381 @end ifnottex
383 These schedules depend on the iterators and give for each instance of each
384 statement a unique execution date. Using such scattering functions allow
385 CLooG to re-generate the input code. 
391 @c %  ***********************Using the CLooG Software **************************
392 @node CLooG Software
393 @chapter Using the CLooG Software
396 @menu
397 * A First Example::
398 * Writing The Input File::
399 * Calling CLooG::
400 * CLooG Options::
401 * Full Example::
402 @end menu
404 @c %/*************************************************************************
405 @c % *                              A FIRST EXAMPLE                          *
406 @c % *************************************************************************/
407 @node A First Example
408 @section A First Example
409 CLooG takes as input a file that must be written accordingly to a grammar
410 described in depth in a further section (@pxref{Writing The Input File}). 
411 Moreover it supports many options to tune the target code presentation or
412 quality as discussed in a dedicated section (@pxref{Calling CLooG}).
413 However, a basic use
414 of CLooG is not very complex and we present in this section how to generate the
415 code corresponding to a basic example discussed earlier (@pxref{Basics}).
417 The problem is to find the code that scans a 2-dimensional polyhedron
418 where @samp{i} and @samp{j} are the unknown (the two dimensions of the space)
419 and @samp{m} and @samp{n} are the parameters (the symbolic constants),
420 defined by the following set of constraints:
421 @example
422 @group
423 2<=i<=n
424 2<=j<=m
425 j<=n+2-i
426 @end group
427 @end example
428 @noindent We also consider a partial knowledge of the parameter values,
429 expressed thanks to the following affine constraints:
430 @example
431 @group
432 m>=2
433 n>=2
434 @end group
435 @end example
437 An input file that corresponds to this problem, and asks for a generated
438 code in C, may be the following. Note that we do not describe here precisely
439 the structure and the components of this file (@pxref{Writing The Input File}
440  for such information, if you feel it necessary):
442 @example
443 # ---------------------- CONTEXT ----------------------
444 c # language is C
446 # Context (constraints on two parameters)
447 2 4                   # 2 lines and 4 columns
448 # eq/in m  n  1         eq/in: 1 for inequality >=0, 0 for equality =0
449     1   1  0 -2       # 1*m + 0*n -2*1 >= 0, i.e. m>=2
450     1   0  1 -2       # 0*m + 1*n -2*1 >= 0, i.e. n>=2
452 1 # We want to set manually the parameter names
453 m n                   # parameter names
455 # --------------------- STATEMENTS --------------------
456 1 # Number of statements
458 1 # First statement: one domain
459 # First domain
460 5 6                   # 5 lines and 6 columns
461 # eq/in i  j  m  n  1 
462     1   1  0  0  0 -2 # i >= 2
463     1  -1  0  0  1  0 # i <= n
464     1   0  1  0  0 -2 # j >= 2
465     1   0 -1  1  0  0 # j <= m
466     1  -1 -1  0  1  2 # n+2-i>=j
467 0  0  0               # for future options
469 1 # We want to set manually the iterator names
470 i j                   # iterator names
472 # --------------------- SCATTERING --------------------
473 0 # No scattering functions
474 @end example
476 This file may be called @samp{basic.cloog}
477 (this example is provided in the CLooG distribution as
478 @code{test/manual_basic.cloog}) and we can ask CLooG to process it
479 and to generate the code by a simple calling to CLooG with this file as input:
480 @samp{cloog basic.cloog}. By default, CLooG will print the generated code in
481 the standard output:
483 @example
484 @group
485 /* Generated by CLooG v@value{VERSION} in 0.00s. */
486 for (i=2;i<=n;i++) @{
487   for (j=2;j<=min(m,-i+n+2);j++) @{    
488     S1(i,j) ;
489   @}
491 @end group
492 @end example
494 @c %/*************************************************************************
495 @c % *                                Input file                             *
496 @c % *************************************************************************/
497 @node Writing The Input File
498 @section Writing The Input File
499 The input text file contains a problem description, i.e. the context,
500 the domains and the scattering functions.
501 Because CLooG is very 'compilable code generation oriented', we can associate
502 some additional informations to each domain. We call this association a
503 @emph{statement}. The set of all informations is 
504 called a @emph{program}. The input file respects the grammar below
505 (terminals are preceded by "_"):
507 @example
508 File             ::= Program
509 Program          ::= Context Statements Scattering
510 Context          ::= Language      Domain_union   Naming
511 Statements       ::= Nb_statements Statement_list Naming
512 Scatterings      ::= Nb_functions  Scattering_list Naming
513 Naming           ::= Option Name_list
514 Name_list        ::= _String   Name_list      | (void)
515 Statement_list   ::= Statement Statement_list | (void)
516 Domain_list      ::= _Domain   Domain_list    | (void)
517 Scattering_list  ::= Domain_union Scattering_list | (void)
518 Statement        ::= Iteration_domain 0 0 0
519 Iteration_domain ::= Domain_union
520 Domain_union     ::= Nb_domains Domain_list
521 Option           ::= 0 | 1
522 Language         ::= c | f
523 Nb_statements    ::= _Integer
524 Nb_domains       ::= _Integer
525 Nb_functions     ::= _Integer
526 @end example
528 Note: if there is only one domain in a @samp{Domain_union},
529 i.e., if @samp{Nb_domains} is 1, then this 1 may be omitted.
531 @itemize @bullet
532 @item  @samp{Context} represents the informations that are
533        shared by all the statements. It consists on
534        the language used (which can be @samp{c} for C or @samp{f} for FORTRAN 90)
535        and the global constraints on parameters.
536        These constraints are essential
537        since they give to CLooG the number of parameters. If there is no
538        parameter or no constraints on parameters, just give a constraint
539        always satisfied like @math{1 \geq 0}. @samp{Naming} sets the parameter
540        names.
541        If the naming option @samp{Option} is 1, parameter names will be read
542        on the next line. There must be exactly as many names as parameters.
543        If the naming option @samp{Option} is 0, parameter names are
544        automatically generated. The name of the first parameter will
545        be @samp{M}, and the name of the @math{(n+1)^{th}} parameter directly
546        follows the name of the @math{n^{th}} parameter in ASCII code.
547        It is the user responsibility to ensure that parameter names,
548        iterators and scattering dimension names are different. 
549 @item  @samp{Statements} represents the informations on the statements.
550        @samp{Nb_statements} is the number of statements in the program, 
551        i.e. the number of @samp{Statement} items in the @samp{Statement_list}.
552        @samp{Statement} represents the informations on a given statement.
553        To each statement is associated a domain
554        (the statement iteration domain: @samp{Iteration_domain}) and three
555        zeroes that represents future options.
556        @samp{Naming} sets the iterator names. If the naming option
557        @samp{Option} is 1, the iterator names
558        will be read on the next line. There must be exactly as many names as
559        nesting level in the deepest iteration domain. If the naming option
560        @samp{Option} is 0, iterator names are automatically generated.
561        The iterator name of the outermost loop will be @samp{i}, and the
562        iterator name of the loop at level @math{n+1} directly follows the 
563        iterator name of the loop at level @math{n} in ASCII code. 
564 @item  @samp{Scatterings} represents the informations on scattering functions.
565        @samp{Nb_functions} is the number of functions (it must be
566        equal to the number of statements or 0 if there is no scattering
567        function). The functions themselves are represented through
568        @samp{Scattering_list}.
569        @samp{Naming} sets the scattering dimension names. If the naming option
570        @samp{Option} is 1, the scattering dimension names will be read on the
571        next line.
572        There must be exactly as many names as scattering dimensions. If the
573        naming option @samp{Option} is 0, scattering dimension names are automatically
574        generated. The name of the @math{n^{th}} scattering dimension
575        will be @samp{cn}.
576 @end itemize
578 @menu
579 * Domain Representation::
580 * Scattering Representation::
581 @end menu
583 @node Domain Representation
584 @subsection Domain Representation
585 As shown by the grammar, the input file describes the various informations
586 thanks to characters, integers and domains. Each domain is defined by a set of
587 constraints in the PolyLib format (@pxref{Wil93}). They have the
588 following syntax:
589 @enumerate
590 @item some optional comment lines beginning with @samp{#},
591 @item the row and column numbers, possibly followed by comments,
592 @item the constraint rows, each row corresponds to a constraint the
593       domain have to satisfy. Each row must be on a single line and is possibly
594       followed by comments. The constraint is an equality @math{p(x) = 0} if the
595       first element is 0, an inequality  @math{p(x) \geq 0} if the first element
596       is 1. The next elements are the unknown coefficients, followed by
597       the parameter coefficients. The last element is the constant factor.
598 @end enumerate
599 For instance, assuming that @samp{i}, @samp{j} and @samp{k} are iterators and
600 @samp{m} and @samp{n} are parameters, the domain defined by the following
601 constraints :
603 @tex
605 \hbox{$ \cases{ -i     + m &$\geq 0$\cr
606                     -j + n &$\geq 0$\cr
607                  i + j - k &$\geq 0$}$}
609 @end tex
611 @ifnottex
612 @example
613 @group
614    -i + m >= 0
615    -j + n >= 0
616 i + j - k >= 0
617 @end group
618 @end example
619 @end ifnottex
621 @noindent can be written in the input file as follows :
623 @example
624 @group
625 # This is the domain
626 3 7                      # 3 lines and 7 columns
627 # eq/in i  j  k  m  n  1 
628     1  -1  0  0  1  0  0 #    -i + m >= 0
629     1   0 -1  0  0  1  0 #    -j + n >= 0
630     1   1  1 -1  0  0  0 # i + j - k >= 0
631 @end group
632 @end example
634 Each iteration domain @samp{Iteration_domain} of a given statement
635 is a union of polyhedra
636 @samp{Domain_union}. A union is defined by its number of elements
637 @samp{Nb_domains} and the elements themselves @samp{Domain_list}.
638 For instance, let us consider the following pseudo-code:
640 @example
641 @group
642 for (i=1;i<=n;i++) @{
643   if ((i >= m) || (i <= 2*m))
644     S1 ;
645   for (j=i+1;j<=m;j++)
646     S2 ;
647 @} 
648 @end group
649 @end example
651 @noindent The iteration domain of @samp{S1} can be divided into two
652 polyhedra and written in the input file as follows:
654 @example
655 @group
656 2 # Number of polyhedra in the union
657 # First domain
658 3 5                # 3 lines and 5 columns
659 # eq/in i  m  n  1 
660     1   1  0  0 -1 #  i >= 1
661     1  -1  0  1  0 #  i <= n
662     1   1 -1  0  0 #  i >= m
663 # Second domain
664 3 5                # 3 lines and 5 columns
665 # eq/in i  m  n  1 
666     1   1  0  0 -1 #  i >= 1
667     1  -1  0  1  0 #  i <= n
668     1  -1  2  0  0 #  i <= 2*m
669 @end group
670 @end example
672 @node Scattering Representation
673 @subsection Scattering Function Representation
674 Scattering functions are depicted in the input file thanks a representation
675 very close to the domain one.
676 An integer gives the number of functions @samp{Nb_functions} and each function
677 is represented by a domain. Each line of the domain corresponds to an equality
678 defining a dimension of the function. Note that at present
679 (CLooG @value{VERSION})
680 @strong{all functions must have the same scattering dimension number}. If a
681 user wants to set scattering functions with different dimensionality, he has
682 to complete the smaller one with zeroes to reach the maximum dimensionality.
683 For instance, let us consider the following code and
684 scheduling functions:
686 @example
687 @group
688 for (i=1;i<=n;i++) @{
689   if ((i >= m) || (i <= 2*m))
690     S1 ;
691   for (j=i+1;j<=m;j++)
692     S2 ;
693 @} 
694 @end group
695 @end example
697 @tex
699 \hbox{$ \cases{ \theta _{S1}(i)      &$=  (i,0)^T$\cr
700                 \theta _{S2}(i,j)^T  &$=  (n,i+j)^T$}$}
702 @end tex
704 @ifnottex
705 @example
706 @group
707 T_S1(i)     = (i,0)^T
708 T_S2(i,j)^T = (n,i+j)^T
709 @end group
710 @end example
711 @end ifnottex
714 @noindent This scheduling can be written in the input file as follows:
716 @example
717 @group
718 2 # Number of scattering functions
719 # First function
720 2 7                          # 2 lines and 7 columns
721 # eq/in c1 c2  i  m  n  1 
722     0    1  0 -1  0  0  0    #  c1 = i
723     0    0  1  0  0  0  0    #  c2 = 0
724 # Second function
725 2 8                          # 2 lines and 8 columns
726 # eq/in c1 c2  i  j  m  n  1 
727     0    1  0  0  0  0 -1  0 #  c1 = n
728     0    0  1 -1 -1  0  0  0 #  c2 = i+j
729 @end group
730 @end example
731 The complete input file for the user who wants to generate the code for this
732 example with the preceding scheduling would be
733 (this file is provided in the CLooG distribution
734 as @code{test/manual_scattering.cloog}:
736 @example
737 # ---------------------- CONTEXT ----------------------
738 c # language is C
740 # Context (no constraints on two parameters)
741 1 4                   # 1 lines and 4 columns
742 # eq/in m  n  1
743     1   0  0  0       # 0 >= 0, always true
745 1 # We want to set manually the parameter names
746 m n                   # parameter names
748 # --------------------- STATEMENTS --------------------
749 2 # Number of statements
751 2 # First statement: two domains
752 # First domain
753 3 5                   # 3 lines and 5 columns
754 # eq/in i  m  n  1
755     1   1  0  0 -1    # i >= 1
756     1  -1  0  1  0    # i <= n
757     1   1 -1  0  0    # i >= m
758 # Second domain
759 3 5                   # 3 lines and 5 columns
760 # eq/in i  m  n  1 
761     1   1  0  0 -1    # i >= 1
762     1  -1  0  1  0    # i <= n
763     1  -1  2  0  0    # i <= 2*m
764 0  0  0               # for future options
766 1 # Second statement: one domain
767 4 6                   # 4 lines and 6 columns
768 # eq/in i  j  m  n  1 
769     1   1  0  0  0 -1 # i >= 1
770     1  -1  0  0  1  0 # i <= n
771     1  -1  1  0  0 -1 # j >= i+1
772     1   0 -1  1  0  0 # j <= m
773 0  0  0               # for future options
775 1 # We want to set manually the iterator names
776 i j                   # iterator names
778 # --------------------- SCATTERING --------------------
779 2 # Scattering functions
780 # First function
781 2 7                   # 2 lines and 7 columns
782 # eq/in p1 p2  i  m  n  1 
783     0    1  0 -1  0  0  0    # p1 = i
784     0    0  1  0  0  0  0    # p2 = 0
785 # Second function
786 2 8                   # 2 lines and 8 columns
787 # eq/in p1 p2  i  j  m  n  1 
788     0    1  0  0  0  0 -1  0 # p1 = n
789     0    0  1 -1 -1  0  0  0 # p2 = i+j
791 1 # We want to set manually the scattering dimension names
792 p1 p2                 # scattering dimension names
793 @end example
796 @c %/*************************************************************************
797 @c % *                             Calling CLooG                             *
798 @c % *************************************************************************/
799 @node Calling CLooG
800 @section Calling CLooG
801 CLooG is called by the following command:
802 @example
803        cloog [ options | file ]
804 @end example
805 The default behavior of CLooG is to read the input informations from a file and
806 to print the generated code or pseudo-code on the standard output.
807 CLooG's behavior and the output code shape is under the user control thanks
808 to many options which are detailed a further section (@pxref{CLooG Options}).
809 @code{file} is the input file. @code{stdin} is a special value: when used,
810 input is standard input. For instance, we can call CLooG to treat the
811 input file @code{basic.cloog} with default options by typing:
812 @code{cloog basic.cloog} or @code{more basic.cloog | cloog stdin}.
814 @c %/*************************************************************************
815 @c % *                             CLooG Options                             *
816 @c % *************************************************************************/
817 @node CLooG Options
818 @section CLooG Options
820 @menu
821 * Last Depth to Optimize Control::
822 * First Depth to Optimize Control::
823 * Statement-wise First and Last Depths to Optimize Control
824 * Simplify Convex Hull::
825 * Once Time Loop Elimination::
826 * Equality Spreading::
827 * First Level for Spreading::
828 * Statement Block::
829 * Loop Strides::
830 * Unrolling::
831 * Compilable Code::
832 * Output::
833 * OpenScop::
834 * Help::
835 * Version ::
836 * Quiet ::
837 @end menu
839 @node Last Depth to Optimize Control
840 @subsection Last Depth to Optimize Control @code{-l <depth>}
842 @code{-l <depth>}: this option sets the last loop depth to be optimized in
843 control. The higher this depth, the less control overhead.
844 For instance, with some input file, a user can generate
845 different pseudo-codes with different @code{depth} values as shown below.
846 @example
847 @group
848 /* Generated using a given input file and @strong{option -l 1} */
849 for (i=0;i<=M;i++) @{
850   S1 ;
851   for (j=0;j<=N;j++) @{
852     S2 ;
853   @}
854   for (j=0;j<=N;j++) @{
855     S3 ;
856   @}
857   S4 ;
859 @end group
860 @end example
861 @example
862 @group
863 /* Generated using the same input file but @strong{option -l 2} */
864 for (i=0;i<=M;i++) @{
865   S1 ;
866   for (j=0;j<=N;j++) @{
867     S2 ;
868     S3 ;
869   @}
870   S4 ;
872 @end group
873 @end example
874      In this example we can see that this option can change the operation
875      execution order between statements. Let us remind that CLooG does not
876      make any speculation on dependences between statements
877      (@pxref{Scattering}). Thus if nothing (i.e. scattering functions)
878      forbids this, CLooG considers the above codes to be equivalent.
879      If there is no scattering functions, the minimum value for @code{depth}
880      is 1 (in the case of 0, the user doesn't really need a loop generator !),
881      and the number of scattering dimensions otherwise (CLooG will warn the
882      user if he doesn't respect such constraint).
883      The maximum value for depth is -1 (infinity).
884      Default value is infinity.
886 @node First Depth to Optimize Control
887 @subsection First Depth to Optimize Control @code{-f <depth>}
889      @code{-f <depth>}: this option sets the first loop depth to be optimized
890      in control. The lower this depth, the less control overhead (and the longer
891      the generated code). For instance, with some input file, a user
892      can generate different pseudo-codes with different @code{depth} values
893      as shown below.
894      The minimum value for @code{depth} is 1, and the
895      maximum value is -1 (infinity).
896      Default value is 1.
897 @example
898 @group
899 /* Generated using a given input file and @strong{option -f 3} */
900 for (i=1;i<=N;i++) @{
901   for (j=1;j<=M;j++) @{
902     S1 ;
903     if (j >= 10) @{
904       S2 ;
905     @}
906   @}
908 @end group
909 @end example
910 @example
911 @group
912 /* Generated using the same input file but @strong{option -f 2} */
913 for (i=1;i<=N;i++) @{
914   for (j=1;j<=9;j++) @{
915     S1 ;
916   @}
917   for (j=10;j<=M;j++) @{
918     S1 ;
919     S2 ;
920   @}
922 @end group
923 @end example
925 @node Statement-wise First and Last Depths to Optimize Control
926 @subsection Statement-wise First and Last Depths to Optimize Control @code{options->fs, options->ls}
928 option->f/l (command-line arguments: -f and -l) provide first and last levels to optimize
929 control overhead at a global level (across the entire program / all statements)
930 by separating / splitting loops. option->fs/ls allow the equivalent of setting
931 -f/-l options on a statement-wise basis. Integer arrays options->fs, options->ls should
932 be allocated by the user with options->fs_ls_size set to the number of elements (always equal
933 to the number of statements).  For any
934 given loop, the first and last depths of all statements under it are looked at
935 to determine if the loop should be separated (max across all fs' and ls' is
936 taken). A user has to set fs meaningfully, i.e., for eg., if two statements i &
937 j have a fused loop and fs[i], fs[j] specify separation for that level for stmt
938 i but not for stmt j, the input is ambiguous and we will in this case not
939 separate (since a max is taken). options->fs/ls override f/l; if fs/ls are not
940 set or are set inconsistently (max across ls[i] < max across fs[i]), f/l take
941 over.
943 fs/ls can only be set via the library interface for now.
945 @node Simple Convex Hull
946 @subsection  Simple Convex Hull @code{-sh <boolean>}
948      @code{-sh <boolean>}: this option enables (@code{boolean=1})
949      or forbids (@code{boolean=0}) the use of an overapproximation
950      of the convex hull that may be easier to compute
951      (especially in the isl backend) and that may result in
952      simpler bounds.
953      This option works only for generated code without
954      code duplication (it means, you have to tune @code{-f} and
955      @code{-l} options first to generate only a loop nest with internal
956      guards). For instance, with the input file @code{test/union.cloog}, a user
957      can generate different pseudo-codes  as shown below.
958      Default value is 0.
959 @example
960 @group
961 /* Generated using test/union.cloog and @strong{option -f -1 -l 2 -override} */
962 for (i=0;i<=11;i++) @{
963   for (j=max(0,5*i-50);j<=min(15,5*i+10);j++) @{
964     if ((i <= 10) && (j <= 10)) @{
965       S1 ;
966     @}
967     if ((i >= 1) && (j >= 5)) @{
968       S2 ;
969     @}
970   @}
972 @end group
973 @end example
974 @example
975 @group
976 /* Generated using the same input file but @strong{option -sh 1 -f -1 -l 2 -override} */
977 for (i=0;i<=11;i++) @{
978   for (j=0;j<=15;j++) @{
979     if ((i <= 10) && (j <= 10)) @{
980       S1 ;
981     @}
982     if ((i >= 1) && (j >= 5)) @{
983       S2 ;
984     @}
985   @}
987 @end group
988 @end example
990 @node Once Time Loop Elimination
991 @subsection Once Time Loop Elimination @code{-otl <boolean>}
993      @code{-otl <boolean>}: this option allows (@code{boolean=1}) or
994      forbids (@code{boolean=0}) the simplification of loops running
995      once. Default value is 1.
996 @example
997 @group
998 /* Generated using a given input file and @strong{option -otl 0} */
999 for (j=i+1;j<=i+1;j++) @{
1000   S1 ;
1002 @end group
1003 @end example
1004 @example
1005 @group
1006 /* Generated using the same input file but @strong{option -otl 1} */
1007 j = i+1 ;
1008 S1 ;
1009 @end group
1010 @end example
1013 @node Equality Spreading 
1014 @subsection Equality Spreading @code{-esp <boolean>}
1016      @code{-esp <boolean>}: this option allows (@code{boolean=1}) or
1017      forbids (@code{boolean=0}) values spreading when there
1018      are equalities. Default value is 1.
1019 @example
1020 @group
1021 /* Generated using a given input file and @strong{option -esp 0} */
1022 i = M+2 ;
1023 j = N ;
1024 for (k=i;k<=j+M;k++) @{
1025   S1 ;
1027 @end group
1028 @end example
1029 @example
1030 @group
1031 /* Generated using the same input file but @strong{option -esp 1} */
1032 for (k=M+2;k<=N+M;k++) @{
1033   S1(i = M+2, j = N) ;
1035 @end group
1036 @end example
1039 @node First Level for Spreading 
1040 @subsection First Level for Spreading @code{-fsp <level>}
1042      @code{-fsp <level>}: it can be useful to set a
1043      first level to begin equality spreading. Particularly when using
1044      scattering functions, the user may want to see the scattering dimension
1045      values instead of spreading or hiding them. If user has set a
1046      spreading, @code{level} is
1047      the first level to start it. Default value is 1.
1048 @example
1049 @group
1050 /* Generated using a given input file and @strong{option -fsp 1} */
1051 for (j=0;j<=N+M;j++) @{
1052   S1(i = N) ;
1054 for (j=0;j<=N+M;j++) @{
1055   S1(i = M) ;
1057 @end group
1058 @end example
1059 @example
1060 @group
1061 /* Generated using the same input file but @strong{option -fsp 2} */
1062 c1 = N ;
1063 for (j=0;j<=c1+M;j++) @{
1064   S1(i = c1) ;
1066 c1 = M ;
1067 for (j=0;j<=N+c1;j++) @{
1068   S1(i = c1) ;
1070 @end group
1071 @end example
1074 @node Statement Block  
1075 @subsection Statement Block @code{-block <boolean>}
1077      @code{-block <boolean>}: this option allows (@code{boolean=1}) to
1078      create a statement block for each new iterator, even if there is only
1079      an equality. This can be useful in order to parse the generated
1080      pseudo-code. When @code{boolean} is set to 0 or when the generation
1081      language is FORTRAN, this feature is disabled. Default value is 0.
1082 @example
1083 @group
1084 /* Generated using a given input file and @strong{option -block 0} */
1085 i = M+2 ;
1086 j = N ;
1087 S1 ;
1088 @end group
1089 @end example
1090 @example
1091 @group
1092 /* Generated using the same input file but @strong{option -block 1} */
1093 @{ i = M+2 ;
1094   @{ j = N ;
1095     S1 ;
1096   @}
1098 @end group
1099 @end example
1102 @node Loop Strides 
1103 @subsection Loop Strides @code{-strides <boolean>}
1105      @code{-strides <boolean>}: this options allows (@code{boolean=1}) to
1106      handle non-unit strides for loop increments. This can remove a lot of
1107      guards and make the generated code more efficient. Default value is 0.
1108 @example
1109 @group
1110 /* Generated using a given input file and @strong{option -strides 0} */
1111 for (i=1;i<=n;i++) @{
1112   if (i%2 == 0) @{
1113     S1(j = i/2) ;
1114   @}
1115   if (i%4 == 0) @{
1116     S2(j = i/4) ;
1117   @}
1119 @end group
1120 @end example
1121 @example
1122 @group
1123 /* Generated using the same input file but @strong{option -strides 1} */
1124 for (i=2;i<=n;i+=2) @{
1125   S1(j = i/2) ;
1126   if (i%4 == 0) @{
1127     S2(j = i/4) ;
1128   @}
1130 @end group
1131 @end example
1134 @node Unrolling
1135 @subsection First Depth to Unroll @code{-first-unroll <depth>}
1137     @code{-first-unroll <depth>}: this option sets the first loop depth
1138     to unroll.  Note that a loop is only unrolled when it is supported
1139     by the backend.  In case of the isl backend, a loop is unrolled
1140     if it has a lower bound that can only be incremented
1141     a fixed (non-parametric) amount of times.
1144 @node Compilable Code
1145 @subsection Compilable Code @code{-compilable <value>}
1147      @code{-compilable <value>}: this options allows (@code{value} is not 0)
1148      to generate a compilable code where all parameters have the integral value
1149      @code{value}. This option creates a macro for each statement. Since
1150      CLooG do not know anything about the statement sources, it fills the
1151      macros with a basic increment that computes the total number of
1152      scanned integral points. The user may change easily the macros according
1153      to his own needs. This option is possible only if the generated code is
1154      in C. Default value is 0.
1155 @example
1156 @group
1157 /* Generated using a given input file and @strong{option -compilable 0} */
1158 for (i=0;i<=n;i++) @{
1159   for (j=0;j<=n;j++) @{
1160     S1 ;
1161     S2 ;
1162   @}
1163   S3 ;
1165 @end group
1166 @end example
1167 @example
1168 /* Generated using the same input file but @strong{option -compilable 10} */
1169 /* DON'T FORGET TO USE -lm OPTION TO COMPILE. */
1171 /* Useful headers. */
1172 #include <stdio.h>
1173 #include <stdlib.h>
1174 #include <math.h>
1176 /* Parameter value. */
1177 #define PARVAL 10
1179 /* Statement macros (please set). */
1180 #define S1(i,j) @{total++;@}
1181 #define S2(i,j) @{total++;@}
1182 #define S3(i)   @{total++;@}
1184 int main() @{
1185   /* Original iterators. */
1186   int i, j ;
1187   /* Parameters. */
1188   int n=PARVAL, total=0 ;
1190   for (i=0;i<=n;i++) @{
1191     for (j=0;j<=n;j++) @{
1192       S1(i,j) ;
1193       S2(i,j) ;
1194     @}
1195     S3(i) ;
1196   @}
1198   printf("Number of integral points: %d.\n",total) ;
1199   return 0 ;
1201 @end example
1203 @node Callable Code
1204 @subsection Callable Code @code{-callable <boolean>}
1206      @code{-callable <boolean>}: if @code{boolean=1}, then a @code{test}
1207      function will be generated that has the parameters as arguments.
1208      Similarly to the @code{-compilable} option,
1209      a macro for each statement is generated.  The generated definitions of
1210      these macros are as used during the correctness testing, but they
1211      can easily be changed by the user to suit her own needs.
1212      This option is only available if the target language is C.
1213      The default value is 0.
1215 @example
1216 /* Generated from double.cloog with @strong{option -callable 0} */
1217 for (i=0;i<=M;i++) @{
1218   S1 ;
1219   for (j=0;j<=N;j++) @{
1220     S2 ;
1221     S3 ;
1222   @}
1223   S4 ;
1225 @end example
1226 @example
1227 /* Generated from double.cloog with @strong{option -callable 1} */
1228 extern void hash(int);
1230 /* Useful macros. */
1231 #define floord(n,d) (((n)<0) ? ((n)-(d)+1)/(d) : (n)/(d))
1232 #define ceild(n,d)  (((n)<0) ? (n)/(d) : ((n)+(d)+1)/(d))
1233 #define max(x,y)    ((x) > (y) ? (x) : (y))
1234 #define min(x,y)    ((x) < (y) ? (x) : (y))
1236 #define S1(i) @{ hash(1); hash(i); @}
1237 #define S2(i,j) @{ hash(2); hash(i); hash(j); @}
1238 #define S3(i,j) @{ hash(3); hash(i); hash(j); @}
1239 #define S4(i) @{ hash(4); hash(i); @}
1241 void test(int M, int N)
1243   /* Original iterators. */
1244   int i, j;
1245   for (i=0;i<=M;i++) @{
1246     S1(i) ;
1247     for (j=0;j<=N;j++) @{
1248       S2(i,j) ;
1249       S3(i,j) ;
1250     @}
1251     S4(i) ;
1252   @}
1254 @end example
1256 @node Output
1257 @subsection Output @code{-o <output>}
1259      @code{-o <output>}: this option sets the output file. @code{stdout} is a
1260      special value: when used, output is standard output.
1261      Default value is @code{stdout}.
1263 @node OpenScop
1264 @subsection OpenScop @code{-openscop}
1266      @code{-openscop}: this option states that the input file complies to
1267      the OpenScop specification instead of the native file format
1268      (@pxref{Bas11}). This option is available only if the OpenScop
1269      support has been enabled at compile time (@pxref{Optional Features}).
1270      The following OpenScop extensions are supported by CLooG
1271      (for the details about those extensions, @pxref{Bas11}):
1272      @itemize @bullet
1273      @item @emph{scatnames} to set the scattering dimension names.
1274      @item @emph{coordinates} to inject the generated code at the
1275            place of a given SCoP in a given file. The use of
1276            this extension is disabled when the options
1277            @emph{-compilable} or @emph{-callable} are set.
1278      @end itemize
1280 @node Help
1281 @subsection Help @code{--help} or @code{-h}
1283      @code{--help} or @code{-h}: this option ask CLooG to print a short help.
1285 @node Version
1286 @subsection Version @code{--version} or @code{-v}
1288      @code{--version} or @code{-v}: this option ask CLooG to print some version
1289      informations.
1291 @node Quiet
1292 @subsection Quiet @code{--quiet} or @code{-q}
1294      @code{--quiet} or @code{-q}: this option tells CLooG not to print
1295      any informational messages.
1298 @c %/*************************************************************************
1299 @c % *                           A Full Example                              *
1300 @c % *************************************************************************/
1301 @node Full Example
1302 @section A Full Example
1304 Let us consider the allocation problem of a Gaussian elimination, i.e. we want
1305 to distribute the various statement instances of the compute kernel onto
1306 different processors. The original code is the following:
1307 @example
1308 @group
1309 for (i=1;j<=N-1;i++) @{
1310   for (j=i+1;j<=N;j++) @{
1311     c[i][j] = a[j][i]/a[i][i] ;    /* S1 */
1312     for (k=i+1;k<=N;k++) @{
1313       a[j][k] -= c[i][j]*a[i][k] ; /* S2 */
1314     @}
1315   @}
1317 @end group
1318 @end example
1320 @noindent The best affine allocation functions can be found by any good automatic
1321 parallelizer like LooPo (@pxref{Gri04}):
1323 @tex
1325 \hbox{$ \cases{ \theta _{S1}(i,j)^T    &$=  (i)$\cr
1326                 \theta _{S2}(i,j,k)^T  &$=  (k)$}$}
1328 @end tex
1330 @ifnottex
1331 @example
1332 @group
1333 T_S1(i,j)^T   = (i)
1334 T_S2(i,j,k)^T = (k)
1335 @end group
1336 @end example
1337 @end ifnottex
1339 @noindent To ensure that on each processor, the set of statement instances is
1340 executed according to the original ordering, we add as minor scattering
1341 dimensions the original scheduling (@pxref{Scattering}):
1343 @tex
1345 \hbox{$ \cases{ \theta _{S1}(i,j)^T    &$=  (i,0,i,0,j,0)^T$\cr
1346                 \theta _{S2}(i,j,k)^T  &$=  (k,0,i,0,j,1,k,0)^T$}$}
1348 @end tex
1350 @ifnottex
1351 @example
1352 @group
1353 T_S1(i,j)^T   = (i,0,i,0,j,0)^T
1354 T_S2(i,j,k)^T = (k,0,i,0,j,1,k,0)^T
1355 @end group
1356 @end example
1357 @end ifnottex
1359 @noindent To ensure that the scattering functions have the same dimensionality, we
1360 complete the first function with zeroes
1361 (this is a CLooG @value{VERSION} and previous versions requirement,
1362 it should be removed in a future version, don't worry it's absolutely legal !):
1364 @tex
1366 \hbox{$ \cases{ \theta _{S1}(i,j)^T    &$=  (i,0,i,0,j,0,0,0)^T$\cr
1367                 \theta _{S2}(i,j,k)^T  &$=  (k,0,i,0,j,1,k,0)^T$}$}
1369 @end tex
1371 @ifnottex
1372 @example
1373 @group
1374 T_S1(i,j)^T   = (i,0,i,0,j,0,0,0)^T
1375 T_S2(i,j,k)^T = (k,0,i,0,j,1,k,0)^T
1376 @end group
1377 @end example
1378 @end ifnottex
1380 @noindent The input file corresponding to this code generation problem
1381 could be (this file is provided in the CLooG distribution
1382 as @code{test/manual_gauss.cloog}:
1384 @example
1385 # ---------------------- CONTEXT ----------------------
1386 c # language is C
1388 # Context (no constraints on one parameter)
1389 1 3                     # 1 line and 3 columns    
1390 # eq/in n  1
1391     1   0  0            # 0 >= 0, always true
1393 1 # We want to set manually the parameter name
1394 n                       # parameter name
1396 # --------------------- STATEMENTS --------------------
1397 2 # Number of statements
1399 1 # First statement: one domain
1400 4 5                     # 4 lines and 3 columns
1401 # eq/in i  j  n  1
1402     1   1  0  0 -1      # i >= 1
1403     1  -1  0  1 -1      # i <= n-1
1404     1  -1  1  0 -1      # j >= i+1
1405     1   0 -1  1  0      # j <= n
1406 0  0  0                 # for future options
1409 # Second statement: one domain
1410 6 6                     # 6 lines and 3 columns
1411 # eq/in i  j  k  n  1
1412     1   1  0  0  0 -1   # i >= 1
1413     1  -1  0  0  1 -1   # i <= n-1
1414     1  -1  1  0  0 -1   # j >= i+1
1415     1   0 -1  0  1  0   # j <= n
1416     1  -1  0  1  0 -1   # k >= i+1
1417     1   0  0 -1  1  0   # k <= n
1418 0  0  0                 # for future options
1420 0 # We let CLooG set the iterator names
1422 # --------------------- SCATTERING --------------------
1423 2 # Scattering functions
1424 # First function
1425 8 13                    # 3 lines and 3 columns
1426 # eq/in p1 p2 p3 p4 p5 p6 p7 p8  i  j  n  1
1427     0    1  0  0  0  0  0  0  0 -1  0  0  0     # p1 = i
1428     0    0  1  0  0  0  0  0  0  0  0  0  0     # p2 = 0
1429     0    0  0  1  0  0  0  0  0 -1  0  0  0     # p3 = i
1430     0    0  0  0  1  0  0  0  0  0  0  0  0     # p4 = 0
1431     0    0  0  0  0  1  0  0  0  0 -1  0  0     # p5 = j
1432     0    0  0  0  0  0  1  0  0  0  0  0  0     # p6 = 0
1433     0    0  0  0  0  0  0  1  0  0  0  0  0     # p7 = 0
1434     0    0  0  0  0  0  0  0  1  0  0  0  0     # p8 = 0
1435 # Second function
1436 8 14                    # 3 lines and 3 columns
1437 # eq/in p1 p2 p3 p4 p5 p6 p7 p8  i  j  k  n  1
1438     0    1  0  0  0  0  0  0  0  0  0 -1  0  0  # p1 = k
1439     0    0  1  0  0  0  0  0  0  0  0  0  0  0  # p2 = 0
1440     0    0  0  1  0  0  0  0  0 -1  0  0  0  0  # p3 = i
1441     0    0  0  0  1  0  0  0  0  0  0  0  0  0  # p4 = 0
1442     0    0  0  0  0  1  0  0  0  0 -1  0  0  0  # p5 = j
1443     0    0  0  0  0  0  1  0  0  0  0  0  0 -1  # p6 = 1
1444     0    0  0  0  0  0  0  1  0  0  0 -1  0  0  # p7 = k
1445     0    0  0  0  0  0  0  0  1  0  0  0  0  0  # p8 = 0
1447 1 # We want to set manually the scattering dimension names
1448 p1 p2 p3 p4 p5 p6 p7 p8 # scattering dimension names
1449 @end example
1451 Calling CLooG, with for instance the command line
1452 @code{cloog -fsp 2 gauss.cloog} for a better view
1453 of the allocation (the processor number is given by @code{p1}),
1454 will result on the following target code that actually implements
1455 the transformation. A minor processing on the dimension @code{p1}
1456 to implement, e.g., MPI calls, which is not shown here may
1457 result in dramatic speedups !
1459 @example
1460 if (n >= 2) @{
1461   p1 = 1 ;
1462   for (p5=2;p5<=n;p5++) @{
1463     S1(i = 1,j = p5) ;
1464   @}
1466 for (p1=2;p1<=n-1;p1++) @{
1467   for (p3=1;p3<=p1-1;p3++) @{
1468     for (p5=p3+1;p5<=n;p5++) @{
1469       S2(i = p3,j = p5,k = p1) ;
1470     @}
1471   @}
1472   for (p5=p1+1;p5<=n;p5++) @{
1473     S1(i = p1,j = p5) ;
1474   @}
1476 if (n >= 2) @{
1477   p1 = n ;
1478   for (p3=1;p3<=n-1;p3++) @{
1479     for (p5=p3+1;p5<=n;p5++) @{
1480       S2(i = p3,j = p5,k = n) ;
1481     @}
1482   @}
1484 @end example
1487 @c %/*************************************************************************
1488 @c % *                           A Full Example                              *
1489 @c % *************************************************************************/
1490 @node CLooG Library
1491 @chapter Using the CLooG Library
1492 The CLooG Library was implemented to allow the user to call CLooG
1493 directly from his programs, without file accesses or system calls. The
1494 user only needs to link his programs with C libraries. The CLooG
1495 library mainly provides one function (@code{cloog_clast_create_from_input})
1496 which takes as input the problem
1497 description with some options, and returns the data structure corresponding
1498 to the generated code (a @code{struct clast_stmt} structure)
1499 which is more or less an abstract syntax tree.
1500 The user can work with this data structure and/or use
1501 our pretty printing function to write the final code in either C or FORTRAN.
1502 Some other functions are provided for convenience reasons.
1503 These functions as well as the data structures are described in this section.
1505 @menu
1506 * CLooG Data Structures::
1507 * CLooG Output::
1508 * Retrieving version information::
1509 * Example of Library Utilization::
1510 @end menu
1513 @node CLooG Data Structures
1514 @section CLooG Data Structures Description
1515 In this section, we describe the data structures used by the loop
1516 generator to represent and to process a code generation problem.
1518 @menu
1519 * CloogState::
1520 * CloogMatrix::
1521 * CloogDomain::
1522 * CloogScattering::
1523 * CloogUnionDomain::
1524 * CloogStatement::
1525 * CloogOptions::
1526 * CloogInput::
1527 @end menu
1530 @node CloogState
1531 @subsection CloogState
1532 @example
1533 @group
1534 CloogState *cloog_state_malloc(void);
1535 void cloog_state_free(CloogState *state);
1536 @end group
1537 @end example
1539 @noindent The @code{CloogState} structure is (implicitly) needed to perform
1540 any CLooG operation.  It should be created using @code{cloog_state_malloc}
1541 before any other CLooG objects are created and destroyed using
1542 @code{cloog_state_free} after all objects have been freed.
1543 It is allowed to use more than one @code{CloogState} structure at
1544 the same time, but an object created within the state of a one
1545 @code{CloogState} structure is not allowed to interact with an object
1546 created within the state of an other @code{CloogState} structure.
1548 @menu
1549 * CloogState/isl::
1550 @end menu
1552 @node CloogState/isl
1553 @subsubsection isl
1555 @example
1556 #include <cloog/isl/cloog.h>
1557 CloogState *cloog_isl_state_malloc(isl_ctx *ctx);
1558 @end example
1560 @noindent
1561 When using the isl backend, CLooG will internally create many isl objects.
1562 If the user creates any CLooG objects from isl objects (e.g.,
1563 through @code{cloog_domain_from_isl_set} below), then the user needs
1564 to make sure that these isl objects live in the same @code{isl_ctx}
1565 as those created by CLooG internally.  The best way to ensure this
1566 property is to pass the @code{isl_ctx} created by the user to CLooG
1567 by calling @code{cloog_isl_state_malloc} to create a @code{CloogState}.
1568 Note that this makes the created @code{CloogState} a user of the
1569 given @code{isl_ctx}, meaning that the @code{CloogState} needs to
1570 be freed before the @code{isl_ctx} is freed.
1573 @node CloogMatrix
1574 @subsection CloogMatrix
1576 @noindent The @code{CloogMatrix} structure is equivalent to the PolyLib
1577 @code{Matrix} data structure (@pxref{Wil93}). This structure is devoted to
1578 represent a set of constraints.
1580 @example
1581 @group
1582 struct cloogmatrix
1583 @{ unsigned NbRows ;    /* Number of rows. */
1584   unsigned NbColumns ; /* Number of columns. */
1585   cloog_int_t **p;     /* Array of pointers to the matrix rows. */
1586   cloog_int_t *p_Init; /* Matrix rows contiguously in memory. */
1588 typedef struct cloogmatrix CloogMatrix;
1590 CloogMatrix *cloog_matrix_alloc(unsigned NbRows, unsigned NbColumns);
1591 void cloog_matrix_print(FILE *foo, CloogMatrix *m);
1592 void cloog_matrix_free(CloogMatrix *matrix);
1593 @end group
1594 @end example
1596 @noindent The whole matrix is stored in memory row after row at the
1597 @code{p_Init} address. @code{p} is an array of pointers where
1598 @code{p[i]} points to the first element of the @math{i^{th}} row.
1599 @code{NbRows} and @code{NbColumns} are respectively the number of
1600 rows and columns of the matrix. 
1601 Each row corresponds to a constraint. The first element of each row is an
1602 equality/inequality tag. The
1603 constraint is an equality @math{p(x) = 0} if the first element is 0, but it is
1604 an inequality @math{p(x) \geq 0} if the first element is 1.
1605 The next elements are the coefficients of the unknowns,
1606 followed by the coefficients of the parameters, and finally the constant term.
1607 For instance, the following three constraints:
1609 @tex
1611 \hbox{$ \cases{ -i + m       &$= 0$\cr
1612                 -j + n       &$\geq 0$\cr
1613                  j + i - k   &$\geq 0$}$}
1615 @end tex
1617 @ifnottex
1618 @example
1619 @group
1620     -i + m  = 0
1621     -j + n >= 0
1622  i + j - k >= 0
1623 @end group
1624 @end example
1625 @end ifnottex
1627 @noindent would be represented by the following rows:
1629 @example
1630 @group
1631 # eq/in  i   j   k   m   n   cst
1632     0    0  -1   0   1   0    0 
1633     1   -1   0   0   0   1    0 
1634     1    1   1  -1   0   0    0 
1635 @end group
1636 @end example
1638 @noindent To be able to provide different precision version (CLooG
1639 supports 32 bits, 64 bits and arbitrary precision through the GMP library),
1640 the @code{cloog_int_t} type depends on the configuration options (it may be
1641 @code{long int} for 32 bits version, @code{long long int} for 64 bits version,
1642 and @code{mpz_t} for multiple precision version).
1644 @node CloogDomain
1645 @subsection CloogDomain
1646 @example
1647 @group
1648 CloogDomain *cloog_domain_union_read(CloogState *state,
1649                                      FILE *input, int nb_parameters);
1650 CloogDomain *cloog_domain_from_cloog_matrix(CloogState *state,
1651                                     CloogMatrix *matrix, int nb_par);
1652 void cloog_domain_free(CloogDomain *domain);
1653 @end group
1654 @end example
1656 @noindent @code{CloogDomain} is an opaque type representing a polyhedral
1657 domain (a union of polyhedra).
1658 A @code{CloogDomain} can be read
1659 from a file using @code{cloog_domain_union_read} or
1660 converted from a @code{CloogMatrix}.
1661 The input format for @code{cloog_domain_union_read}
1662 is that of @ref{Domain Representation}.
1663 The function @code{cloog_domain_from_cloog_matrix} takes a @code{CloogState}, a
1664 @code{CloogMatrix} and @code{int} as input and returns a pointer to a
1665 @code{CloogDomain}. @code{matrix} describes the domain and @code{nb_par} is the
1666 number of parameters in this domain. The input data structures are neither
1667 modified nor freed.
1668 The @code{CloogDomain} can be freed using @code{cloog_domain_free}.
1669 There are also some backend dependent functions for creating
1670 @code{CloogDomain}s.
1672 @menu
1673 * CloogDomain/PolyLib::
1674 * CloogDomain/isl::
1675 @end menu
1677 @node CloogDomain/PolyLib
1678 @subsubsection PolyLib
1680 @example
1681 #include <cloog/polylib/cloog.h>
1682 CloogDomain *cloog_domain_from_polylib_polyhedron(CloogState *state,
1683                                         Polyhedron *, int nb_par);
1684 @end example
1685 @noindent
1686 The function @code{cloog_domain_from_polylib_polyhedron} takes a PolyLib
1687 @code{Polyhedron} as input and returns a pointer to a @code{CloogDomain}.
1688 The @code{nb_par} parameter indicates the number of parameters
1689 in the domain.  The input data structure if neither modified nor freed.
1691 @node CloogDomain/isl
1692 @subsubsection isl
1694 @example
1695 #include <cloog/isl/cloog.h>
1696 CloogDomain *cloog_domain_from_isl_set(__isl_take isl_set *set);
1697 __isl_give isl_set *isl_set_from_cloog_domain(CloogDomain *domain);
1698 @end example
1699 @noindent
1700 The function @code{cloog_domain_from_isl_set} takes an
1701 @code{isl_set} as input and returns a pointer to a @code{CloogDomain}.
1702 The function consumes a reference to the given @code{isl_set}.
1703 Similarly, @code{isl_set_from_cloog_domain} consumes a reference
1704 to a @code{CloogDomain} and returns an @code{isl_set}.
1707 @node CloogScattering
1708 @subsection CloogScattering
1709 @example
1710 @group
1711 CloogScattering *cloog_domain_read_scattering(CloogDomain *domain,
1712                                               FILE *foo);
1713 CloogScattering *cloog_scattering_from_cloog_matrix(CloogState *state,
1714                          CloogMatrix *matrix, int nb_scat, int nb_par);
1715 void cloog_scattering_free(CloogScattering *);
1716 @end group
1717 @end example
1719 @noindent
1720 The @code{CloogScattering} type represents a scattering function.
1721 A @code{CloogScattering} for a given @code{CloogDomain} can be read
1722 from a file using @code{cloog_scattering_read} or converted
1723 from a @code{CloogMatrix} using @code{cloog_scattering_from_cloog_matrix}.
1724 The function @code{cloog_scattering_from_cloog_matrix} takes a
1725 @code{CloogState}, a @code{CloogMatrix} and two @code{int}s as input and
1726 returns a
1727 pointer to a @code{CloogScattering}.
1728 @code{matrix} describes the scattering, while @code{nb_scat} and
1729 @code{nb_par} are the number of scattering dimensions and
1730 the number of parameters, respectively. The input data structures are
1731 neither modified nor freed.
1732 A @code{CloogScattering} can be freed using @code{cloog_scattering_free}.
1733 There are also some backend dependent functions for creating
1734 @code{CloogScattering}s.
1736 @menu
1737 * CloogScattering/PolyLib::
1738 * CloogScattering/isl::
1739 @end menu
1741 @node CloogScattering/PolyLib
1742 @subsubsection PolyLib
1744 @example
1745 #include <cloog/polylib/cloog.h>
1746 CloogScattering *cloog_scattering_from_polylib_polyhedron(
1747         CloogState *state, Polyhedron *polyhedron, int nb_par);
1748 @end example
1749 @noindent
1750 The function @code{cloog_scattering_from_polylib_polyhedron} takes a PolyLib
1751 @code{Polyhedron} as input and returns a pointer to a @code{CloogScattering}.
1752 The @code{nb_par} parameter indicates the number of parameters
1753 in the domain.  The input data structure if neither modified nor freed.
1755 @node CloogScattering/isl
1756 @subsubsection isl
1758 @example
1759 #include <cloog/isl/cloog.h>
1760 CloogScattering *cloog_scattering_from_isl_map(__isl_take isl_map *map);
1761 @end example
1762 @noindent
1763 The function @code{cloog_scattering_from_isl_map} takes an
1764 @code{isl_map} as input and returns a pointer to a @code{CloogScattering}.
1765 The output dimensions of the @code{isl_map} correspond to the
1766 scattering dimensions, while the input dimensions correspond to the
1767 domain dimensions.
1768 The function consumes a reference to the given @code{isl_map}.
1771 @node CloogUnionDomain
1772 @subsection CloogUnionDomain
1773 @example
1774 @group
1775 enum cloog_dim_type @{ CLOOG_PARAM, CLOOG_ITER, CLOOG_SCAT @};
1777 CloogUnionDomain *cloog_union_domain_alloc(int nb_par);
1778 CloogUnionDomain *cloog_union_domain_add_domain(CloogUnionDomain *ud,
1779         const char *name, CloogDomain *domain,
1780         CloogScattering *scattering, void *usr);
1781 CloogUnionDomain *cloog_union_domain_set_name(CloogUnionDomain *ud,
1782         enum cloog_dim_type type, int index, const char *name);
1783 void cloog_union_domain_free(CloogUnionDomain *ud);
1784 @end group
1785 @end example
1787 @noindent A @code{CloogUnionDomain} structure represents a union
1788 of scattered named domains.  A @code{CloogUnionDomain} is
1789 initialized by a call to @code{cloog_union_domain_alloc},
1790 after which domains can be added using @code{cloog_union_domain_add_domain}.
1792 @code{cloog_union_domain_alloc} takes the number of parameters as input.
1793 @code{cloog_union_domain_add_domain} takes a previously created
1794 @code{CloogUnionDomain} as input along with an optional name,
1795 a domain, an optional scattering function and a user pointer.
1796 The name may be @code{NULL} and is duplicated if it is not.
1797 If no name is specified, then the statements will be named according
1798 to the order in which they were added.
1799 @code{domain} and @code{scattering} are taken over
1800 by the @code{CloogUnionDomain}.  @code{scattering} may be @code{NULL},
1801 but it must be consistently @code{NULL} or not over all calls
1802 to @code{cloog_union_domain_add_domain}.
1803 @code{cloog_union_domain_set_name} can be used to set the names
1804 of parameters, iterators and scattering dimensions.
1805 The names of iterators and scattering dimensions can only be set
1806 after all domains have been added.
1808 There is also a backend dependent function for creating
1809 @code{CloogUnionDomain}s.
1811 @menu
1812 * CloogUnionDomain/isl::
1813 @end menu
1815 @node CloogUnionDomain/isl
1816 @subsubsection isl
1818 @example
1819 #include <cloog/isl/cloog.h>
1820 CloogUnionDomain *cloog_union_domain_from_isl_union_map(
1821         __isl_take isl_union_map *umap);
1822 CloogUnionDomain *cloog_union_domain_from_isl_set(
1823         __isl_take isl_set *set);
1824 @end example
1825 @noindent
1826 The function @code{cloog_union_domain_from_isl_union_map} takes a
1827 @code{isl_union_map} as input and returns a pointer
1828 to a @code{CloogUnionDomain}.
1829 The input is a mapping from different
1830 spaces (different tuple names and possibly different dimensions)
1831 to a common space.  The iteration domains are set to the domains
1832 in each space.  The statement names are set to the names of the
1833 spaces.  The parameter names of the result are set to those of
1834 the input, but the iterator and scattering dimension names are
1835 left unspecified.
1836 The function consumes a reference to the given @code{isl_union_map}.  The
1837 function @code{cloog_union_domain_from_isl_set} is similar, but takes an
1838 unscattered domain as input. It is not defined for an union_set, because the
1839 order of iterations from two different isl_sets is undefined, if no scattering
1840 is provided.
1843 @node CloogStatement
1844 @subsection CloogStatement
1845 @example
1846 @group
1847 struct cloogstatement
1848 @{ int number ;                  /* The statement unique number. */
1849   char *name;                   /* Name of the statement. */
1850   void * usr ;                  /* Pointer for user's convenience. */
1851   struct cloogstatement * next ;/* Next element of the linked list. */
1852 @} ;
1853 typedef struct cloogstatement CloogStatement ;
1855 CloogStatement *cloog_statement_malloc(CloogState *state);
1856 void cloog_statement_print(FILE *, CloogStatement *);
1857 void cloog_statement_free(CloogStatement *);
1858 @end group
1859 @end example
1861 @noindent The @code{CloogStatement} structure represents a @code{NULL}
1862 terminated linked
1863 list of statements. In CLooG, a statement is only defined by its unique
1864 number (@code{number}). The user can use the pointer @code{usr} for his
1865 own convenience to link his own statement representation to the
1866 corresponding @code{CloogStatement} structure. The whole management of the
1867 @code{usr} pointer is under the responsibility of the user, in particular,
1868 CLooG never tries to print, to allocate or to free a memory block pointed
1869 by @code{usr}. 
1873 @node CloogOptions
1874 @subsection CloogOptions
1875 @example
1876 @group
1877 struct cloogoptions
1878 @{ int l;                     /* -l option.                                */
1879   int f;                     /* -f option.                                 */
1880   int *ls;                   /* Statement-wise l option                    */
1881   int *fs;                   /* Statement-wise f option                    */
1882   int fs_ls_size;            /* Size of the fs and ls arrays (same size)   */
1883   int strides;               /* -strides option.                           */
1884   int sh;                    /* -sh option.                                */
1885   int first_unroll;          /* -first-unroll option.                      */
1886   int esp;                   /* -esp option.                               */
1887   int fsp;                   /* -fsp option.                               */
1888   int otl;                   /* -otl option.                               */
1889   int block;                 /* -block option.                             */
1890   int compilable;            /* -compilable option.                        */
1891   int language;              /* CLOOG_LANGUAGE_C or CLOOG_LANGUAGE_FORTRAN */
1892   int save_domains;          /* Save unsimplified copy of domain.          */
1893 @} ;
1894 typedef struct cloogoptions CloogOptions ;
1896 CloogOptions *cloog_options_malloc(CloogState *state);
1897 void cloog_options_print(FILE *foo, CloogOptions *options);
1898 void cloog_options_free(CloogOptions *options);
1899 @end group
1900 @end example
1902 @noindent The @code{CloogOptions} structure contains all the possible options to
1903 rule CLooG's behaviour (@pxref{Calling CLooG}).
1904 As a reminder, the default values are:
1905 @itemize @bullet
1906 @item @math{l = -1} (optimize control until the innermost loops),
1907 @item @math{f = 1} (optimize control from the outermost loops),
1908 @item @math{ls/fs = NULL} and @math{fs\_ls\_size = 0} (statement-wise l/f are not set),
1909 @item @math{strides = 0} (use only unit strides),
1910 @item @math{sh = 0} (do not compute simple convex hulls),
1911 @item @math{first\_unroll = -1} (do not perform unrolling),
1912 @item @math{esp = 1} (spread complex equalities),
1913 @item @math{fsp = 1} (start to spread from the first iterators),
1914 @item @math{otl = 1} (simplify loops running only once).
1915 @item @math{block = 0} (do not make statement blocks when not necessary).
1916 @item @math{compilable = 0} (do not generate a compilable code).
1917 @end itemize 
1919 The @code{save_domains} option is only useful for users of the CLooG
1920 library.  This option defaults to 0, but when it is set, the @code{domain}
1921 field of each @code{clast_user_stmt} will be set to the set of values for the
1922 scattering dimensions for which this instance of the user statement is executed.
1923 The @code{domain} field of each @code{clast_for} contains the set of values for
1924 the scattering dimensions for which an instance of a user statement is executed
1925 inside the @code{clast_for}. It is only available if the @code{clast_for}
1926 enumerates a scattering dimension.
1928 @node CloogInput
1929 @subsection CloogInput
1930 @example
1931 @group
1932 CloogInput *cloog_input_read(FILE *file, CloogOptions *options);
1933 CloogInput *cloog_input_alloc(CloogDomain *context,
1934                                 CloogUnionDomain *ud);
1935 void cloog_input_free(CloogInput *input);
1937 void cloog_input_dump_cloog(FILE *, CloogInput *, CloogOptions *);
1938 @end group
1939 @end example
1941 @noindent A @code{CloogInput} structure represents the input to CLooG.
1942 It is essentially a @code{CloogUnionDomain} along with a context
1943 @code{CloogDomain}.  A @code{CloogInput} can be created from
1944 a @code{CloogDomain} and a @code{CloogUnionDomains} using
1945 @code{cloog_input_alloc}, or it can be read from a CLooG input
1946 file using @code{cloog_input_read}.  The latter also modifies
1947 the @code{language} field of the @code{CloogOptions} structure.
1948 The constructed @code{CloogInput} can be used as input
1949 to a @code{cloog_clast_create_from_input} call.
1951 A @code{CloogInput} data structure and a @code{CloogOptions} contain
1952 the same information as a .cloog file. This function dumps the .cloog
1953 description of the given data structures into a file.
1955 @node Dump CLooG Input File Function
1956 @subsection Dump CLooG Input File Function
1957 @example
1958 @end example
1960 @node CLooG Output
1961 @section CLooG Output
1963 @noindent
1964 Given a description of the input,
1965 an AST corresponding to the @code{CloogInput} can be constructed
1966 using @code{cloog_clast_create_from_input} and destroyed using
1967 @code{free_clast_stmt}.
1968 @example
1969 struct clast_stmt *cloog_clast_create_from_input(CloogInput *input,
1970                                       CloogOptions *options);
1971 void free_clast_stmt(struct clast_stmt *s);
1972 @end example
1973 @noindent
1974 @code{clast_stmt} represents a linked list of ``statements''.
1975 @example
1976 struct clast_stmt @{
1977     const struct clast_stmt_op    *op;
1978     struct clast_stmt   *next;
1980 @end example
1981 @noindent
1982 The entries in the list are not of type @code{clast_stmt} itself,
1983 but of some larger type.  The following statement types are defined
1984 by CLooG.
1986 @example
1987 struct clast_root @{
1988     struct clast_stmt   stmt;
1989     CloogNames *        names;
1991 struct clast_root *new_clast_root(CloogNames *names);
1993 struct clast_assignment @{
1994     struct clast_stmt   stmt;
1995     const char *        LHS;
1996     struct clast_expr * RHS;
1998 struct clast_assignment *new_clast_assignment(const char *lhs,
1999                                               struct clast_expr *rhs);
2001 struct clast_block @{
2002     struct clast_stmt   stmt;
2003     struct clast_stmt * body;
2005 struct clast_block *new_clast_block(void);
2007 struct clast_user_stmt @{
2008     struct clast_stmt   stmt;
2009     CloogDomain *       domain;
2010     CloogStatement *    statement;
2011     struct clast_stmt * substitutions;
2013 struct clast_user_stmt *new_clast_user_stmt(CloogDomain *domain,
2014     CloogStatement *stmt, struct clast_stmt *subs);
2016 struct clast_for @{
2017     struct clast_stmt   stmt;
2018     CloogDomain *       domain;
2019     const char *        iterator;
2020     struct clast_expr * LB;
2021     struct clast_expr * UB;
2022     cloog_int_t         stride;
2023     struct clast_stmt * body;
2025 struct clast_for *new_clast_for(CloogDomain *domain, const char *it,
2026                                 struct clast_expr *LB, struct clast_expr *UB,
2027                                 cloog_int_t stride);
2029 struct clast_guard @{
2030     struct clast_stmt   stmt;
2031     struct clast_stmt * then;
2032     int                 n;
2033     struct clast_equation       eq[1];
2035 struct clast_guard *new_clast_guard(int n);
2036 @end example
2037 @noindent
2038 The @code{clast_stmt} returned by @code{cloog_clast_create}
2039 is a @code{clast_root}.
2040 It contains a placeholder for all the variable names that appear
2041 in the AST and a (list of) nested statement(s).
2043 @noindent
2044 A @code{clast_assignment} assigns the value given by
2045 the @code{clast_expr} @code{RHS} to a variable named @code{LHS}.
2047 @noindent
2048 A @code{clast_block} groups a list of statements into one statement.
2049 These statements are only generated if the @code{block} option is set,
2050 @pxref{Statement Block} and @ref{CloogOptions}.
2052 @noindent
2053 A @code{clast_user_stmt} represents a call to a statement specified
2054 by the user, @pxref{CloogStatement}.
2055 @code{substitutions} is a list of @code{clast_assignment} statements
2056 assigning an expression in terms of the scattering dimensions to
2057 each of the original iterators in the original order.
2058 The @code{LHS}s of these assignments are left blank (@code{NULL}).
2059 The @code{domain} is set to @code{NULL} if the @code{save_domains} option
2060 is not set.  Otherwise, it is set to the set
2061 of values for the scattering dimensions
2062 for which this instance of the user statement is executed.
2063 Note that unless the @code{noscalars} option has been set, the
2064 constant scattering dimensions may have been removed from this set.
2066 @noindent
2067 A @code{clast_for} represents a for loop, iterating @code{body} for each
2068 value of @code{iterator} between @code{LB} and @code{UB} in steps
2069 of size @code{stride}.
2070 The @code{domain} is set to @code{NULL} if the @code{save_domains} option is not
2071 set.  Otherwise, it is set to the set of values for the scattering dimensions
2072 for which a user statement is executed inside this @code{clast_for}.  Note that
2073 unless the @code{noscalars} option has been set, the constant scattering
2074 dimensions may have been removed from this set.
2076 @noindent
2077 A @code{clast_guard} represents the guarded execution of the @code{then}
2078 (list of) statement(s) by a conjunction of @code{n} (in)equalities.
2079 Each (in)equality is represented by a @code{clast_equation}.
2080 @example
2081 struct clast_equation @{
2082     struct clast_expr * LHS;
2083     struct clast_expr * RHS;
2084     int                 sign;
2086 @end example
2087 @noindent
2088 The condition expressed by a @code{clast_equation} is
2089 @code{LHS <= RHS}, @code{LHS == RHS} or @code{LHS >= RHS}
2090 depending on whether @code{sign} is less than zero, equal
2091 to zero, or greater than zero.
2093 The dynamic type of a @code{clast_stmt} can be determined
2094 using the macro @code{CLAST_STMT_IS_A(stmt,type)},
2095 where @code{stmt} is a pointer to a @code{clast_stmt}
2096 and @code{type} is one of @code{stmt_root}, @code{stmt_ass},
2097 @code{stmt_user}, @code{stmt_block}, @code{stmt_for} or
2098 @code{stmt_guard}.
2099 Users are allowed to define their own statement types by
2100 assigning the @code{op} field of the statements a pointer
2101 to a @code{clast_stmt_op} structure.
2102 @example
2103 struct clast_stmt_op @{
2104     void (*free)(struct clast_stmt *);
2106 @end example
2107 @noindent
2108 The @code{free} field of this structure should point
2109 to a function that frees the user defined statement.
2111 @noindent
2112 A @code{clast_expr} can be an identifier, a term,
2113 a binary expression or a reduction.
2114 @example
2115 enum clast_expr_type @{
2116     clast_expr_name,
2117     clast_expr_term,
2118     clast_expr_bin,
2119     clast_expr_red
2121 struct clast_expr @{
2122     enum clast_expr_type type;
2124 void free_clast_expr(struct clast_expr *e);
2125 @end example
2127 @noindent
2128 Identifiers are of subtype @code{clast_name}.
2129 @example
2130 struct clast_name @{
2131     struct clast_expr   expr;
2132     const char *        name;
2134 struct clast_name *new_clast_name(const char *name);
2135 void free_clast_name(struct clast_name *t);
2136 @end example
2137 @noindent
2138 The character string pointed to by @code{name} is
2139 assumed to be part of the @code{CloogNames} structure
2140 in the root of the clast as is therefore not copied.
2142 @noindent
2143 Terms are of type @code{clast_term}.
2144 @example
2145 struct clast_term @{
2146     struct clast_expr   expr;
2147     cloog_int_t         val;
2148     struct clast_expr  *var;
2150 struct clast_term *new_clast_term(cloog_int_t c, struct clast_expr *v);
2151 void free_clast_term(struct clast_term *t);
2152 @end example
2153 @noindent
2154 If @code{var} is set to @code{NULL}, then the term represents
2155 the integer value @code{val}.  Otherwise, it represents
2156 the term @code{val * var}.
2157 @code{new_clast_term} simply copies the @code{v} pointer
2158 without copying the underlying @code{clast_expr}.
2159 @code{free_clast_term}, on the other hand, recursively frees
2160 @code{var}.
2162 @noindent
2163 Binary expressions are of type @code{clast_bin_type} and
2164 represent either the floor of a division (fdiv),
2165 the ceil of a division (cdiv), an exact division or
2166 the remainder of an fdiv.
2167 @example
2168 enum clast_bin_type @{ clast_bin_fdiv, clast_bin_cdiv, 
2169                       clast_bin_div, clast_bin_mod @};
2170 struct clast_binary @{
2171     struct clast_expr   expr;
2172     enum clast_bin_type type;
2173     struct clast_expr*  LHS;
2174     cloog_int_t         RHS;
2176 struct clast_binary *new_clast_binary(enum clast_bin_type t, 
2177                           struct clast_expr *lhs, cloog_int_t rhs);
2178 void free_clast_binary(struct clast_binary *b);
2179 @end example
2181 @noindent
2182 Reductions are of type @code{clast_reduction} and
2183 can represent either the sum, the minimum or the maximum
2184 of its elements.
2185 @example
2186 enum clast_red_type @{ clast_red_sum, clast_red_min, clast_red_max @};
2187 struct clast_reduction @{
2188     struct clast_expr   expr;
2189     enum clast_red_type type;
2190     int                 n;
2191     struct clast_expr*  elts[1];
2193 struct clast_reduction *new_clast_reduction(enum clast_red_type t,
2194                                             int n);
2195 void free_clast_reduction(struct clast_reduction *r);
2196 @end example
2198 @node Retrieving version information
2199 @section Retrieving version information
2200 CLooG provides static and dynamic version checks to assist on
2201 including a compatible version of the library.
2202 A static version check at compile time can be achieved by
2203 querying the version constants defined in @code{version.h}:
2205 @itemize @bullet
2206 @item @code{CLOOG_VERSION_MAJOR}
2207 @item @code{CLOOG_VERSION_MINOR}
2208 @item @code{CLOOG_VERSION_REVISION}
2209 @end itemize
2211 This way it is possible to ensure the included headers are of the
2212 correct version. It is still possible that the installed CLooG
2213 library version differs from the installed headers.
2214 In order to avoid this, a dynamic version check is provided with
2215 the functions:
2217 @example
2218 @group
2219 int cloog_version_major(void);
2220 int cloog_version_minor(void);
2221 int cloog_version_revision(void);
2222 @end group
2223 @end example
2225 By using both the static and the dynamic version check, it is possible
2226 to match CLooG's header version with the library's version.
2228 @node Example of Library Utilization
2229 @section Example of Library Utilization
2230 @menu
2231 * Basic Library Utilization::
2232 * Scanning isl Sets::
2233 @end menu
2235 @node Basic Library Utilization
2236 @subsection Basic Library Utilization
2237 Here is a basic example showing how it is possible to use the CLooG library,
2238 assuming that a standard installation has been done.
2239 The following C program reads a CLooG input file on the standard input,
2240 then prints the solution on the standard output.
2241 Options are preselected to the default values of the CLooG software.
2242 This example is provided in the @code{example} directory of the
2243 CLooG distribution.
2244 @example
2245 /* example.c */
2246 # include <stdio.h>
2247 # include <cloog/cloog.h>
2249 int main() @{
2250   CloogState *state;
2251   CloogInput *input;
2252   CloogOptions *options ;
2253   struct clast_stmt *root;
2254   
2255   /* Setting options and reading program informations. */
2256   state = cloog_state_malloc();
2257   options = cloog_options_malloc(state);
2258   input = cloog_input_read(stdin, options);
2260   /* Generating and printing the code. */
2261   root = cloog_clast_create_from_input(input, options);
2262   clast_pprint(stdout, root, 0, options);
2264   cloog_clast_free(root);
2265   cloog_options_free(options) ;
2266   cloog_state_free(state);
2267   return 0;
2269 @end example
2271 @noindent The compilation (with default isl/GMP version installed)
2272 command could be:
2273 @example
2274 gcc -DCLOOG_INT_GMP example.c -lcloog-isl -o example
2275 @end example
2276 @noindent A calling command with the input file test.cloog could be:
2277 @example
2278 more test.cloog | ./example
2279 @end example
2281 @node Scanning isl Sets
2282 @subsection Scanning isl Sets
2283 Here is an isl-level example to prepare a convenient input, to generate the
2284 Clast of the scanning code for this input, to pretty-print the code and to
2285 de-allocate memory in a clean way. This example is provided in the
2286 @code{example} directory of the CLooG distribution.
2288 @example
2289 /* example-isl.c */
2290 #include <cloog/cloog.h>
2291 #include <cloog/isl/cloog.h>
2293 /* Input problem */
2294 int nb_parameters = 1;
2295 char *parameter_name[]  = @{"N"@};
2296 char *iterator_name[]   = @{"i", "j"@};
2297 char *scattering_name[] = @{"t0", "t1", "t2"@};
2298 char *str_context       = "[N] -> @{ : N > 0@}";
2299 char *str_domain1       = "[N] -> @{[i, j] : 0 <= i < N and 0 <= j < N@}";
2300 char *str_domain2       = "[N] -> @{[i, j] : 0 <= i < N and 0 <= j < N@}";
2301 char *str_scattering1   = "[N] -> @{[i, j] -> [0, i + j, j]@}";
2302 char *str_scattering2   = "[N] -> @{[i, j] -> [1, i,    -j]@}";
2304 int main() @{
2305   isl_ctx *ctx;
2306   isl_set *set_context, *set1, *set2;
2307   isl_map *map1, *map2;
2308   CloogDomain *context, *domain1, *domain2;
2309   CloogScattering *scattering1, *scattering2;
2310   CloogUnionDomain *domains;
2311   CloogInput *input;
2312   CloogState *state;
2313   CloogOptions *options;
2314   struct clast_stmt *root;
2316   /* Build isl structures for context, sets and mapping */
2317   ctx = isl_ctx_alloc();
2318   set_context = isl_set_read_from_str(ctx, str_context);
2319   set1 = isl_set_read_from_str(ctx, str_domain1);
2320   set2 = isl_set_read_from_str(ctx, str_domain2);
2321   map1 = isl_map_read_from_str(ctx, str_scattering1);
2322   map2 = isl_map_read_from_str(ctx, str_scattering2);
2324   /* Translate them to CLooG context, domains and scattering */
2325   context = cloog_domain_from_isl_set(set_context);
2326   domain1 = cloog_domain_from_isl_set(set1);
2327   domain2 = cloog_domain_from_isl_set(set2);
2328   scattering1 = cloog_scattering_from_isl_map(map1);
2329   scattering2 = cloog_scattering_from_isl_map(map2);
2331   /* Prepare the list of domains to scan */
2332   domains = cloog_union_domain_alloc(nb_parameters);
2333   cloog_union_domain_add_domain(domains,"S1",domain1,scattering1,NULL);
2334   cloog_union_domain_add_domain(domains,"S2",domain2,scattering2,NULL);
2335   cloog_union_domain_set_name(domains,CLOOG_PARAM,0,parameter_name[0]);
2336   cloog_union_domain_set_name(domains,CLOOG_ITER, 0,iterator_name[0]);
2337   cloog_union_domain_set_name(domains,CLOOG_ITER, 1,iterator_name[1]);
2338   cloog_union_domain_set_name(domains,CLOOG_SCAT, 0,scattering_name[0]);
2339   cloog_union_domain_set_name(domains,CLOOG_SCAT, 1,scattering_name[1]);
2340   cloog_union_domain_set_name(domains,CLOOG_SCAT, 2,scattering_name[2]);
2342   /* Build the input, generate a scanning code AST and print the code */
2343   input = cloog_input_alloc(context, domains);
2344   state = cloog_isl_state_malloc(ctx);
2345   options = cloog_options_malloc(state);
2346   root = cloog_clast_create_from_input(input, options);
2347   clast_pprint(stdout, root, 0, options);
2349   /* Recycle allocated memory */
2350   cloog_clast_free(root);
2351   cloog_options_free(options);
2352   cloog_state_free(state);
2353   isl_ctx_free(ctx);
2355 @end example
2357 @noindent The compilation (with default isl/GMP version installed)
2358 command could be:
2359 @example
2360 gcc -DCLOOG_INT_GMP example-isl.c -lcloog-isl -o example-isl
2361 @end example
2362 @noindent A calling command could be:
2363 @example
2364 ./example-isl
2365 @end example
2368 @c %  ******************************** HACKING *********************************
2369 @c @node Hacking
2370 @c @chapter Hacking CLooG
2372 @c @menu
2373 @c * Program organization::
2374 @c * Special Options::
2375 @c * CLooG Coding Standards::
2376 @c @end menu
2378 @c @node Program organization
2379 @c @section Program organization
2381 @c @node Special Options
2382 @c @section Special Options
2384 @c @node CLooG Coding Standards
2385 @c @section CLooG Coding Standards
2388 @c %  ****************************** INSTALLING ********************************
2389 @node Installing
2390 @chapter Installing CLooG
2392 @menu
2393 * License::
2394 * Requirements::
2395 * Basic Installation::
2396 * Optional Features::
2397 * Uninstallation::
2398 @end menu
2400 @node License
2401 @section License
2402 First of all, it would be very kind to refer the following paper in any
2403 publication that result from the use of the CLooG software or its library,
2404 @pxref{Bas04} (a bibtex entry is provided behind the title page of this
2405 manual, along with copyright notice, and in the CLooG home
2406 @code{http://www.CLooG.org}.
2408 This library is free software; you can redistribute it and/or
2409 modify it under the terms of the GNU Lesser General Public
2410 License as published by the Free Software Foundation; either
2411 version 2.1 of the License, or (at your option) any later version.
2412 This library is distributed in the hope that it will be useful,
2413 but WITHOUT ANY WARRANTY; without even the implied warranty of
2414 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
2415 Lesser General Public License for more details.
2416 @code{http://www.gnu.org/licenses/lgpl-2.1.html}
2418 Note, though, that if you link CLooG against a GPL library such
2419 as the PolyLib backend, then the combination becomes GPL too.
2420 In particular, a CLooG library based on the PolyLib backend
2421 is GPL version 2 only.
2422 Since the isl backend is LGPL, linking against it does not affect
2423 the license of CLooG.
2426 @node Requirements
2427 @section Requirements
2429 CLooG can be used with one of two possible backends,
2430 one using isl and one using PolyLib.
2431 The isl library is included in the CLooG distribution,
2432 while the PolyLib library needs to be obtained separately.
2433 On the other hand, isl requires GMP, while PolyLib can be
2434 compiled with or without the use of GMP.
2435 The user therefore needs to install at least one of
2436 PolyLib or GMP.
2438 @menu
2439 * PolyLib::
2440 * GMP Library::
2441 @end menu
2444 @node PolyLib
2445 @subsection PolyLib (optional)
2446 To successfully install CLooG with the PolyLib backend,
2447 the user first needs to install PolyLib
2448 version 5.22.1 or above (default 64 bits version is satisfying
2449 as well as 32 bits or GMP multiple precision version).
2450 Polylib can be downloaded freely
2451 at @code{http://icps.u-strasbg.fr/PolyLib/} or
2452 @code{http://www.irisa.fr/polylib/}. Once downloaded and unpacked
2453 (e.g. using the @samp{tar -zxvf polylib-5.22.3.tar.gz} command),
2454 the user can compile
2455 it by typing the following commands on the PolyLib's root directory:
2457 @itemize @bullet
2458 @item @code{./configure}
2459 @item @code{make}
2460 @item And as root: @code{make install}
2461 @end itemize
2463 Alternatively, the latest development version can be obtained from the
2464 git repository:
2465 @itemize @bullet
2466 @item @code{git clone git://repo.or.cz/polylib.git}
2467 @item @code{cd polylib}
2468 @item @code{./autogen.sh}
2469 @item @code{./configure}
2470 @item @code{make}
2471 @item And as root: @code{make install}
2472 @end itemize
2474 The PolyLib default installation is @code{/usr/local}. This directory may
2475 not be inside your library path. To fix the problem, the user should set
2476 @example
2477 export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib
2478 @end example
2479 @noindent if your shell is, e.g., bash or
2480 @example
2481 setenv LD_LIBRARY_PATH $LD_LIBRARY_PATH:/usr/local/lib
2482 @end example
2483 @noindent if your shell is, e.g., tcsh. Add the line to your .bashrc or .tcshrc (or
2484 whatever convenient file) to make this change permanent. Another solution
2485 is to ask PolyLib to install in the standard path by using the prefix
2486 option of the configure script:
2487 @samp{./configure --prefix=/usr}.
2489 CLooG makes intensive calls to polyhedral operations, and PolyLib
2490 functions do the job. Polylib is a free library written in C for the
2491 manipulation of polyhedra. The library is operating on objects like
2492 vectors, matrices, lattices, polyhedra, Z-polyhedra, unions of
2493 polyhedra and a lot of other intermediary structures. It provides
2494 functions for all the important operations on these structures. 
2496 @node GMP Library
2497 @subsection GMP Library (optional)
2499 To be able to deal with insanely large coefficient, the user will need to
2500 install the GNU Multiple Precision Library (GMP for short) version 4.1.4
2501 or above. It can be freely downloaded from @code{http://www.swox.com/gmp}.
2502 Note that the isl backend currently requires GMP.
2503 The user can compile GMP by typing the following commands on the GMP root
2504 directory:
2506 @itemize @bullet
2507 @item @code{./configure}
2508 @item @code{make}
2509 @item And as root: @code{make install}
2510 @end itemize
2512 The GMP default installation is @code{/usr/local}, the same method to
2513 fix a library path problem applies as with PolyLib (@pxref{PolyLib}).
2515 If you want to use the PolyLib backend, then
2516 PolyLib has to be built using the GMP library by specifying the option
2517 @samp{--with-libgmp=PATH_TO_GMP} to the PolyLib configure script
2518 (where @code{PATH_TO_GMP} is @code{/usr/local} if you did not change the GMP
2519 installation directory). Then you have to set the convenient CLooG configure
2520 script options to build the GMP version (@pxref{Optional Features}).
2523 @node Basic Installation
2524 @section CLooG Basic Installation
2526 Once downloaded and unpacked
2527 (e.g. using the @samp{tar -zxvf cloog-@value{VERSION}.tar.gz} command),
2528 you can compile CLooG by typing the following commands on the CLooG's root
2529 directory:
2531 @itemize @bullet
2532 @item @code{./configure}
2533 @item @code{make}
2534 @item And as root: @code{make install}
2535 @end itemize
2537 Alternatively, the latest development version can be obtained from the
2538 git repository:
2539 @itemize @bullet
2540 @item @code{git clone git://repo.or.cz/cloog.git}
2541 @item @code{cd cloog}
2542 @item @code{./get_submodules.sh}
2543 @item @code{./autogen.sh}
2544 @item @code{./configure}
2545 @item @code{make}
2546 @item And as root: @code{make install}
2547 @end itemize
2549 Depending on which backend you want to use and where they
2550 are located, you may need to pass some
2551 options to the configure script, @pxref{Optional Features}.
2553 The program binaries and object files can be removed from the
2554 source code directory by typing @code{make clean}. To also remove the
2555 files that the @code{configure} script created (so you can compile the
2556 package for a different kind of computer) type @code{make distclean}.
2558 Both the CLooG software and library have been successfully compiled
2559 on the following systems:
2560 @itemize @bullet
2561 @item PC's under Linux, with the @code{gcc} compiler,
2562 @item PC's under Windows (Cygwin), with the @code{gcc} compiler,
2563 @item Sparc and UltraSparc Stations, with the @code{gcc} compiler.
2564 @end itemize
2566 @node Optional Features 
2567 @section Optional Features  
2568 The @code{configure} shell script attempts to guess correct values for
2569 various system-dependent variables and user options used during compilation.
2570 It uses those values to create the @code{Makefile}. Various user options
2571 are provided by the CLooG's configure script. They are summarized in the
2572 following list and may be printed by typing @code{./configure --help} in the
2573 CLooG top-level directory.
2575 @itemize @bullet
2576 @item By default, the installation directory is @code{/usr/local}:
2577 @code{make install} will install the package's files in
2578 @code{/usr/local/bin}, @code{/usr/local/lib} and @code{/usr/local/include}.
2579 The user can specify an installation prefix other than @code{/usr/local} by
2580 giving @code{configure} the option @code{--prefix=PATH}.
2582 @item By default, the isl backend will use the version of isl
2583 that is @code{bundled} together with CLooG.
2584 Using the @code{--with-isl} option of @code{configure}
2585 the user can specify that @code{no} isl,
2586 a previously installed (@code{system}) isl or a @code{build} isl
2587 should be used.
2588 In the latter case, the user should also specify the build location
2589 using @code{--with-isl-builddir=PATH}.
2590 In case of an installed isl,
2591 the installation location can be specified using the
2592 @code{--with-isl-prefix=PATH} and
2593 @code{--with-isl-exec-prefix=PATH} options of @code{configure}.
2595 @item By default, the PolyLib backend will use an installed
2596 (@code{system}) PolyLib, if any.
2597 The installation location can be specified using the
2598 @code{--with-polylib-prefix=PATH} and
2599 @code{--with-polylib-exec-prefix=PATH} options of @code{configure}.
2600 Using the @code{--with-polylib} option of @code{configure}
2601 the user can specify that @code{no} PolyLib or a @code{build} PolyLib
2602 should be used.
2603 In the latter case, the user should also specify the build location
2604 using @code{--with-polylib-builddir=PATH}.
2606 @item By default, the PolyLib backend of CLooG is built
2607 in 64bits version if such version of the
2608 PolyLib is found by @code{configure}. If the only existing version of the
2609 PolyLib is the 32bits or if the user give to @code{configure} the option
2610 @code{--with-bits=32}, the 32bits version of CLooG will be compiled. In the
2611 same way, the option @code{--with-bits=gmp} have to be used to build
2612 the multiple precision version.
2614 @item By default, @code{configure} will look for the GMP library
2615 (necessary to build the multiple precision version) in standard
2616 locations. If necessary, the user can specify the GMP path by giving
2617 @code{configure} the option @code{--with-gmp-prefix=PATH} and/or
2618 @code{--with-gmp-exec-prefix=PATH}.
2620 @item By default, the OpenScop Library (osl) support is not enabled.
2621 @c @code{configure} will use the bundled OpenScop Library (osl).
2622 Using the @code{--with-osl} option of @code{configure}
2623 the user can specify that @code{no} osl,
2624 a previously installed (@code{system}) osl, a @code{bundled} osl, or a
2625 @code{build} osl should be used.
2626 In the latter case, the user should also specify the build location
2627 using @code{--with-osl-builddir=PATH}.
2628 In case of an installed osl,
2629 the installation location can be specified using the
2630 @code{--with-osl-prefix=PATH} and
2631 @code{--with-osl-exec-prefix=PATH} options of @code{configure}.
2632 @end itemize
2634 @node Uninstallation 
2635 @section Uninstallation  
2636 The user can easily remove the CLooG software and library from his system
2637 by typing (as root if necessary) from the CLooG top-level directory
2638 @code{make uninstall}.
2640 @c %  **************************** DOCUMENTATION ******************************
2641 @node Documentation
2642 @chapter Documentation
2643 The CLooG distribution provides several documentation sources. First, the
2644 source code itself is as documented as possible. The code comments use a
2645 Doxygen-compatible presentation (something similar to what JavaDoc does for
2646 JAVA). The user may install Doxygen
2647 (see @code{http://www.stack.nl/~dimitri/doxygen}) to automatically
2648 generate a technical documentation by typing @code{make doc} or
2649 @code{doxygen ./autoconf/Doxyfile} at the CLooG top-level directory after
2650 running the configure script (@pxref{Installing}). Doxygen will generate
2651 documentation sources (in HTML, LaTeX and man) in the @code{doc/source}
2652 directory of the CLooG distribution.
2654 The Texinfo sources of the present document are also provided in the @code{doc}
2655 directory. You can build it in either DVI format (by typing
2656 @code{texi2dvi cloog.texi}) or PDF format
2657 (by typing @code{texi2pdf cloog.texi}) or HTML format
2658 (by typing @code{makeinfo --html cloog.texi}, using @code{--no-split}
2659 option to generate a single HTML file) or info format
2660 (by typing @code{makeinfo cloog.texi}).
2662 @c %  ****************************** REFERENCES ********************************
2663 @node References
2664 @chapter References
2666 @itemize
2667 @item
2668 @anchor{Bas03a}[Bas03a] C. Bastoul, P. Feautrier. Improving data locality
2669 by chunking. CC'12 International Conference on Compiler Construction,
2670 LNCS 2622, pages 320-335, Warsaw, april 2003. 
2672 @item
2673 @anchor{Bas03b}[Bas03b] C. Bastoul. Efficient code generation for automatic
2674 parallelization and optimization. ISPDC'03 IEEE International Symposium on
2675 Parallel and Distributed Computing, pages 23-30, Ljubljana, october 2003. 
2677 @item
2678 @anchor{Bas04}[Bas04] C. Bastoul. Code Generation in the Polyhedral Model
2679 Is Easier Than You Think. PACT'13 IEEE International Conference on Parallel
2680 Architecture and Compilation Techniques, pages 7-16, Juan-les-Pins,
2681 september 2004.
2683 @item
2684 @anchor{Bas11}[Bas11] C. Bastoul. A Specification and a Library for Data 
2685 Exchange in Polyhedral Compilation Tools. Technical Report,
2686 Paris-Sud University, France, September 2011.
2688 @item
2689 @anchor{Fea92}[Fea92] P. Feautrier Some efficient solutions to the affine
2690 scheduling problem, part II: multidimensional time.
2691 International Journal of Parallel Programming, 21(6):389--420, December 1992.
2693 @item
2694 @anchor{Gri04}[Gri04] M. Griebl. Automatic parallelization of loop programs
2695 for distributed memory architectures. Habilitation Thesis. Facult@"at f@"ur
2696 Mathematik und Informatik, Universit@"at Passau, 2004.
2697 @emph{http://www.infosun.fmi.uni-passau.de/cl/loopo/}
2699 @item
2700 @anchor{Qui00}[Qui00] F. Quiller@'e, S. Rajopadhye, and D. Wilde.
2701 Generation of efficient nested loops from polyhedra.
2702 International Journal of Parallel Programming, 28(5):469-498,
2703 october 2000.
2705 @item
2706 @anchor{Wil93}[Wil93] Doran K. Wilde.
2707 A library for doing polyhedral operations.
2708 Technical Report 785, IRISA, Rennes, France, 1993.
2710 @end itemize
2715 @c % /*************************************************************************
2716 @c %  *                       PART VI: END OF THE DOCUMENT                    *
2717 @c %  *************************************************************************/
2718 @c @unnumbered Index
2719      
2720 @c @printindex cp
2721      
2722 @bye