3 @c % /**-----------------------------------------------------------------**
5 @c % **-----------------------------------------------------------------**
7 @c % **-----------------------------------------------------------------**
8 @c % ** First version: july 6th 2002 **
9 @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
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 !
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 % *************************************************************************/
34 @setfilename cloog.info
35 @settitle CLooG - a loop generator for scanning polyhedra
38 @include gitversion.texi
39 @set UPDATED October 15th 2007
40 @setchapternewpage odd
44 @c % /*************************************************************************
45 @c % * PART II: SUMMARY DESCRIPTION AND COPYRIGHT *
46 @c % *************************************************************************/
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
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:
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@}
72 Copyright @copyright{} 2002-2005 C@'edric Bastoul.
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.
83 @c % /*************************************************************************
84 @c % * PART III: TITLEPAGE, CONTENTS, COPYRIGHT *
85 @c % *************************************************************************/
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
93 @c The following two commands start the copyright page.
95 @noindent (September 2001)
97 @item C@'edric Bastoul
98 SCHEDULES GENERATE !!! I just need to apply them now, where can I find
99 a good code generator ?!
102 Hmmm. I fear that if you want something powerful enough, you'll have to
106 @vskip 0pt plus 1filll
110 @c Output the table of contents at the beginning.
113 @c % /*************************************************************************
114 @c % * PART IV: TOP NODE AND MASTER MENU *
115 @c % *************************************************************************/
135 @c % /*************************************************************************
136 @c % * PART V: BODY OF THE DOCUMENT *
137 @c % *************************************************************************/
139 @c % ****************************** 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
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}).
163 also to be the back-end of automatic parallelizers like LooPo (@pxref{Gri04}).
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.
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
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):
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,
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:
236 for (i=2;i<=n;i++) @{
237 for (j=2;j<=min(m,-i+n+2);j++) @{
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 !
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:
262 /* A convenient target pseudo-code. */
263 for (i=1;i<=N;i++) @{
266 for (i=1;i<=N;i++) @{
274 /* Another convenient target pseudo-code. */
275 for (i=1;i<=N;i++) @{
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:
300 $$\theta _{S1}(i) = (1)$$
301 $$\theta _{S2}(j) = (2)$$
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:
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 */
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 */
350 a[j][i] /= a[i][i] ; /* S4 */
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}
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$}$}
375 T_S1(i,j)^T = (0,i,0,j,0)^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
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 **************************
393 @chapter Using the CLooG Software
398 * Writing The Input File::
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}).
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:
428 @noindent We also consider a partial knowledge of the parameter values,
429 expressed thanks to the following affine constraints:
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):
443 # ---------------------- CONTEXT ----------------------
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
460 5 6 # 5 lines and 6 columns
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
472 # --------------------- SCATTERING --------------------
473 0 # No scattering functions
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
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++) @{
494 @c %/*************************************************************************
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 "_"):
509 Program ::= Context Statements Scattering
510 Context ::= Language Domain Naming
511 Statements ::= Nb_statements Statement_list Naming
512 Scattering ::= Nb_functions Domain_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 Statement ::= Iteration_domain 0 0 0
518 Iteration_domain ::= Domain_union
519 Domain_union ::= Nb_domains Domain_list
522 Nb_statements ::= _Integer
523 Nb_domains ::= _Integer
524 Nb_functions ::= _Integer
528 @item @samp{Context} represents the informations that are
529 shared by all the statements. It consists on
530 the language used (which can be @samp{c} for C or @samp{f} for FORTRAN 90)
531 and the global constraints on parameters.
532 These constraints are essential
533 since they give to CLooG the number of parameters. If there is no
534 parameter or no constraints on parameters, just give a constraint
535 always satisfied like @math{1 \geq 0}. @samp{Naming} sets the parameter
537 If the naming option @samp{Option} is 1, parameter names will be read
538 on the next line. There must be exactly as many names as parameters.
539 If the naming option @samp{Option} is 0, parameter names are
540 automatically generated. The name of the first parameter will
541 be @samp{M}, and the name of the @math{(n+1)^{th}} parameter directly
542 follows the name of the @math{n^{th}} parameter in ASCII code.
543 It is the user responsibility to ensure that parameter names,
544 iterators and scattering dimension names are different.
545 @item @samp{Statements} represents the informations on the statements.
546 @samp{Nb_statements} is the number of statements in the program,
547 i.e. the number of @samp{Statement} items in the @samp{Statement_list}.
548 @samp{Statement} represents the informations on a given statement.
549 To each statement is associated a domain
550 (the statement iteration domain: @samp{Iteration_domain}) and three
551 zeroes that represents future options.
552 @samp{Naming} sets the iterator names. If the naming option
553 @samp{Option} is 1, the iterator names
554 will be read on the next line. There must be exactly as many names as
555 nesting level in the deepest iteration domain. If the naming option
556 @samp{Option} is 0, iterator names are automatically generated.
557 The iterator name of the outermost loop will be @samp{i}, and the
558 iterator name of the loop at level @math{n+1} directly follows the
559 iterator name of the loop at level @math{n} in ASCII code.
560 @item @samp{Scattering} represents the informations on scattering functions.
561 @samp{Nb_functions} is the number of functions (it must be
562 equal to the number of statements or 0 if there is no scattering
563 function). The function themselves are represented through
565 @samp{Naming} sets the scattering dimension names. If the naming option
566 @samp{Option} is 1, the scattering dimension names will be read on the
568 There must be exactly as many names as scattering dimensions. If the
569 naming option @samp{Option} is 0, scattering dimension names are automatically
570 generated. The name of the @math{n^{th}} scattering dimension
575 * Domain Representation::
576 * Scattering Representation::
579 @node Domain Representation
580 @subsection Domain Representation
581 As shown by the grammar, the input file describes the various informations
582 thanks to characters, integers and domains. Each domain is defined by a set of
583 constraints in the PolyLib format (@pxref{Wil93}). They have the
586 @item some optional comment lines beginning with @samp{#},
587 @item the row and column numbers, possibly followed by comments,
588 @item the constraint rows, each row corresponds to a constraint the
589 domain have to satisfy. Each row must be on a single line and is possibly
590 followed by comments. The constraint is an equality @math{p(x) = 0} if the
591 first element is 0, an inequality @math{p(x) \geq 0} if the first element
592 is 1. The next elements are the unknown coefficients, followed by
593 the parameter coefficients. The last element is the constant factor.
595 For instance, assuming that @samp{i}, @samp{j} and @samp{k} are iterators and
596 @samp{m} and @samp{n} are parameters, the domain defined by the following
601 \hbox{$ \cases{ -i + m &$\geq 0$\cr
603 i + j - k &$\geq 0$}$}
617 @noindent can be written in the input file as follows :
622 3 7 # 3 lines and 7 columns
624 1 -1 0 0 1 0 0 # -i + m >= 0
625 1 0 -1 0 0 1 0 # -j + n >= 0
626 1 1 1 -1 0 0 0 # i + j - k >= 0
630 Each iteration domain @samp{Iteration_domain} of a given statement
631 is a union of polyhedra
632 @samp{Domain_union}. A union is defined by its number of elements
633 @samp{Nb_domains} and the elements themselves @samp{Domain_list}.
634 For instance, let us consider the following pseudo-code:
638 for (i=1;i<=n;i++) @{
639 if ((i >= m) || (i <= 2*m))
647 @noindent The iteration domain of @samp{S1} can be divided into two
648 polyhedra and written in the input file as follows:
652 2 # Number of polyhedra in the union
654 3 5 # 3 lines and 5 columns
660 3 5 # 3 lines and 5 columns
664 1 -1 2 0 0 # i <= 2*m
668 @node Scattering Representation
669 @subsection Scattering Function Representation
670 Scattering functions are depicted in the input file thanks a representation
671 very close to the domain one.
672 An integer gives the number of functions @samp{Nb_functions} and each function
673 is represented by a domain. Each line of the domain corresponds to an equality
674 defining a dimension of the function. Note that at present
675 (CLooG @value{VERSION})
676 @strong{all functions must have the same scattering dimension number}. If a
677 user wants to set scattering functions with different dimensionality, he has
678 to complete the smaller one with zeroes to reach the maximum dimensionality.
679 For instance, let us consider the following code and
680 scheduling functions:
684 for (i=1;i<=n;i++) @{
685 if ((i >= m) || (i <= 2*m))
695 \hbox{$ \cases{ \theta _{S1}(i) &$= (i,0)^T$\cr
696 \theta _{S2}(i,j)^T &$= (n,i+j)^T$}$}
704 T_S2(i,j)^T = (n,i+j)^T
710 @noindent This scheduling can be written in the input file as follows:
714 2 # Number of scattering functions
716 2 7 # 2 lines and 7 columns
717 # eq/in c1 c2 i m n 1
718 0 1 0 -1 0 0 0 # c1 = i
719 0 0 1 0 0 0 0 # c2 = 0
721 2 8 # 2 lines and 8 columns
722 # eq/in c1 c2 i j m n 1
723 0 1 0 0 0 0 -1 0 # c1 = n
724 0 0 1 -1 -1 0 0 0 # c2 = i+j
727 The complete input file for the user who wants to generate the code for this
728 example with the preceding scheduling would be
729 (this file is provided in the CLooG distribution
730 as @code{test/manual_scattering.cloog}:
733 # ---------------------- CONTEXT ----------------------
736 # Context (no constraints on two parameters)
737 1 4 # 1 lines and 4 columns
739 1 0 0 0 # 0 >= 0, always true
741 1 # We want to set manually the parameter names
742 m n # parameter names
744 # --------------------- STATEMENTS --------------------
745 2 # Number of statements
747 2 # First statement: two domains
749 3 5 # 3 lines and 5 columns
755 3 5 # 3 lines and 5 columns
759 1 -1 2 0 0 # i <= 2*m
760 0 0 0 # for future options
762 1 # Second statement: one domain
763 4 6 # 4 lines and 6 columns
765 1 1 0 0 0 -1 # i >= 1
766 1 -1 0 0 1 0 # i <= n
767 1 -1 1 0 0 -1 # j >= i+1
768 1 0 -1 1 0 0 # j <= m
769 0 0 0 # for future options
771 1 # We want to set manually the iterator names
774 # --------------------- SCATTERING --------------------
775 2 # Scattering functions
777 2 7 # 2 lines and 7 columns
778 # eq/in p1 p2 i m n 1
779 0 1 0 -1 0 0 0 # p1 = i
780 0 0 1 0 0 0 0 # p2 = 0
782 2 8 # 2 lines and 8 columns
783 # eq/in p1 p2 i j m n 1
784 0 1 0 0 0 0 -1 0 # p1 = n
785 0 0 1 -1 -1 0 0 0 # p2 = i+j
787 1 # We want to set manually the scattering dimension names
788 p1 p2 # scattering dimension names
792 @c %/*************************************************************************
793 @c % * Calling CLooG *
794 @c % *************************************************************************/
796 @section Calling CLooG
797 CLooG is called by the following command:
799 cloog [ options | file ]
801 The default behavior of CLooG is to read the input informations from a file and
802 to print the generated code or pseudo-code on the standard output.
803 CLooG's behavior and the output code shape is under the user control thanks
804 to many options which are detailed a further section (@pxref{CLooG Options}).
805 @code{file} is the input file. @code{stdin} is a special value: when used,
806 input is standard input. For instance, we can call CLooG to treat the
807 input file @code{basic.cloog} with default options by typing:
808 @code{cloog basic.cloog} or @code{more basic.cloog | cloog stdin}.
810 @c %/*************************************************************************
811 @c % * CLooG Options *
812 @c % *************************************************************************/
814 @section CLooG Options
817 * Last Depth to Optimize Control::
818 * First Depth to Optimize Control::
819 * Simplify Convex Hull::
820 * Once Time Loop Elimination::
821 * Equality Spreading::
822 * First Level for Spreading::
832 @node Last Depth to Optimize Control
833 @subsection Last Depth to Optimize Control @code{-l <depth>}
835 @code{-l <depth>}: this option sets the last loop depth to be optimized in
836 control. The higher this depth, the less control overhead.
837 For instance, with some input file, a user can generate
838 different pseudo-codes with different @code{depth} values as shown below.
841 /* Generated using a given input file and @strong{option -l 1} */
842 for (i=0;i<=M;i++) @{
844 for (j=0;j<=N;j++) @{
847 for (j=0;j<=N;j++) @{
856 /* Generated using the same input file but @strong{option -l 2} */
857 for (i=0;i<=M;i++) @{
859 for (j=0;j<=N;j++) @{
867 In this example we can see that this option can change the operation
868 execution order between statements. Let us remind that CLooG does not
869 make any speculation on dependences between statements
870 (@pxref{Scattering}). Thus if nothing (i.e. scattering functions)
871 forbids this, CLooG considers the above codes to be equivalent.
872 If there is no scattering functions, the minimum value for @code{depth}
873 is 1 (in the case of 0, the user doesn't really need a loop generator !),
874 and the number of scattering dimensions otherwise (CLooG will warn the
875 user if he doesn't respect such constraint).
876 The maximum value for depth is -1 (infinity).
877 Default value is infinity.
879 @node First Depth to Optimize Control
880 @subsection First Depth to Optimize Control @code{-f <depth>}
882 @code{-f <depth>}: this option sets the first loop depth to be optimized
883 in control. The lower this depth, the less control overhead (and the longer
884 the generated code). For instance, with some input file, a user
885 can generate different pseudo-codes with different @code{depth} values
887 The minimum value for @code{depth} is 1, and the
888 maximum value is -1 (infinity).
892 /* Generated using a given input file and @strong{option -f 3} */
893 for (i=1;i<=N;i++) @{
894 for (j=1;j<=M;j++) @{
905 /* Generated using the same input file but @strong{option -f 2} */
906 for (i=1;i<=N;i++) @{
907 for (j=1;j<=9;j++) @{
910 for (j=10;j<=M;j++) @{
918 @node Simplify Convex Hull
919 @subsection Simplify Convex Hull @code{-sh <boolean>}
921 @code{-sh <boolean>}: this option enables (@code{boolean=1})
922 or forbids (@code{boolean=0}) a simplification step
923 that may simplify some constraints.
924 This option works only for generated code without
925 code duplication (it means, you have to tune @code{-f} and
926 @code{-l} options first to generate only a loop nest with internal
927 guards). For instance, with the input file @code{test/union.cloog}, a user
928 can generate different pseudo-codes as shown below.
932 /* Generated using test/union.cloog and @strong{option -f -1 -l 2 -override} */
933 for (i=0;i<=11;i++) @{
934 for (j=max(0,5*i-50);j<=min(15,5*i+10);j++) @{
935 if ((i <= 10) && (j <= 10)) @{
938 if ((i >= 1) && (j >= 5)) @{
947 /* Generated using the same input file but @strong{option -sh 1 -f -1 -l 2 -override} */
948 for (i=0;i<=11;i++) @{
949 for (j=0;j<=15;j++) @{
950 if ((i <= 10) && (j <= 10)) @{
953 if ((i >= 1) && (j >= 5)) @{
961 @node Once Time Loop Elimination
962 @subsection Once Time Loop Elimination @code{-otl <boolean>}
964 @code{-otl <boolean>}: this option allows (@code{boolean=1}) or
965 forbids (@code{boolean=0}) the simplification of loops running
966 once. Default value is 1.
969 /* Generated using a given input file and @strong{option -otl 0} */
970 for (j=i+1;j<=i+1;j++) @{
977 /* Generated using the same input file but @strong{option -otl 1} */
984 @node Equality Spreading
985 @subsection Equality Spreading @code{-esp <boolean>}
987 @code{-esp <boolean>}: this option allows (@code{boolean=1}) or
988 forbids (@code{boolean=0}) values spreading when there
989 are equalities. Default value is 1.
992 /* Generated using a given input file and @strong{option -esp 0} */
995 for (k=i;k<=j+M;k++) @{
1002 /* Generated using the same input file but @strong{option -esp 1} */
1003 for (k=M+2;k<=N+M;k++) @{
1004 S1(i = M+2, j = N) ;
1010 @node First Level for Spreading
1011 @subsection First Level for Spreading @code{-fsp <level>}
1013 @code{-fsp <level>}: it can be useful to set a
1014 first level to begin equality spreading. Particularly when using
1015 scattering functions, the user may want to see the scattering dimension
1016 values instead of spreading or hiding them. If user has set a
1017 spreading, @code{level} is
1018 the first level to start it. Default value is 1.
1021 /* Generated using a given input file and @strong{option -fsp 1} */
1022 for (j=0;j<=N+M;j++) @{
1025 for (j=0;j<=N+M;j++) @{
1032 /* Generated using the same input file but @strong{option -fsp 2} */
1034 for (j=0;j<=c1+M;j++) @{
1038 for (j=0;j<=N+c1;j++) @{
1045 @node Statement Block
1046 @subsection Statement Block @code{-block <boolean>}
1048 @code{-block <boolean>}: this option allows (@code{boolean=1}) to
1049 create a statement block for each new iterator, even if there is only
1050 an equality. This can be useful in order to parse the generated
1051 pseudo-code. When @code{boolean} is set to 0 or when the generation
1052 language is FORTRAN, this feature is disabled. Default value is 0.
1055 /* Generated using a given input file and @strong{option -block 0} */
1063 /* Generated using the same input file but @strong{option -block 1} */
1074 @subsection Loop Strides @code{-strides <boolean>}
1076 @code{-strides <boolean>}: this options allows (@code{boolean=1}) to
1077 handle non-unit strides for loop increments. This can remove a lot of
1078 guards and make the generated code more efficient. Default value is 0.
1081 /* Generated using a given input file and @strong{option -strides 0} */
1082 for (i=1;i<=n;i++) @{
1094 /* Generated using the same input file but @strong{option -strides 1} */
1095 for (i=2;i<=n;i+=2) @{
1104 @node Compilable Code
1105 @subsection Compilable Code @code{-compilable <value>}
1107 @code{-compilable <value>}: this options allows (@code{value} is not 0)
1108 to generate a compilable code where all parameters have the integral value
1109 @code{value}. This option creates a macro for each statement. Since
1110 CLooG do not know anything about the statement sources, it fills the
1111 macros with a basic increment that computes the total number of
1112 scanned integral points. The user may change easily the macros according
1113 to his own needs. This option is possible only if the generated code is
1114 in C. Default value is 0.
1117 /* Generated using a given input file and @strong{option -compilable 0} */
1118 for (i=0;i<=n;i++) @{
1119 for (j=0;j<=n;j++) @{
1128 /* Generated using the same input file but @strong{option -compilable 10} */
1129 /* DON'T FORGET TO USE -lm OPTION TO COMPILE. */
1131 /* Useful headers. */
1136 /* Parameter value. */
1139 /* Statement macros (please set). */
1140 #define S1(i,j) @{total++;@}
1141 #define S2(i,j) @{total++;@}
1142 #define S3(i) @{total++;@}
1145 /* Original iterators. */
1148 int n=PARVAL, total=0 ;
1150 for (i=0;i<=n;i++) @{
1151 for (j=0;j<=n;j++) @{
1158 printf("Number of integral points: %d.\n",total) ;
1164 @subsection Callable Code @code{-callable <boolean>}
1166 @code{-callable <boolean>}: if @code{boolean=1}, then a @code{test}
1167 function will be generated that has the parameters as arguments.
1168 Similarly to the @code{-compilable} option,
1169 a macro for each statement is generated. The generated definitions of
1170 these macros are as used during the correctness testing, but they
1171 can easily be changed by the user to suit her own needs.
1172 This option is only available if the target language is C.
1173 The default value is 0.
1176 /* Generated from double.cloog with @strong{option -callable 0} */
1177 for (i=0;i<=M;i++) @{
1179 for (j=0;j<=N;j++) @{
1187 /* Generated from double.cloog with @strong{option -callable 1} */
1188 extern void hash(int);
1190 /* Useful macros. */
1191 #define floord(n,d) (((n)<0) ? ((n)-(d)+1)/(d) : (n)/(d))
1192 #define ceild(n,d) (((n)<0) ? (n)/(d) : ((n)+(d)+1)/(d))
1193 #define max(x,y) ((x) > (y) ? (x) : (y))
1194 #define min(x,y) ((x) < (y) ? (x) : (y))
1196 #define S1(i) @{ hash(1); hash(i); @}
1197 #define S2(i,j) @{ hash(2); hash(i); hash(j); @}
1198 #define S3(i,j) @{ hash(3); hash(i); hash(j); @}
1199 #define S4(i) @{ hash(4); hash(i); @}
1201 void test(int M, int N)
1203 /* Original iterators. */
1205 for (i=0;i<=M;i++) @{
1207 for (j=0;j<=N;j++) @{
1217 @subsection Output @code{-o <output>}
1219 @code{-o <output>}: this option sets the output file. @code{stdout} is a
1220 special value: when used, output is standard output.
1221 Default value is @code{stdout}.
1224 @subsection Help @code{--help} or @code{-h}
1226 @code{--help} or @code{-h}: this option ask CLooG to print a short help.
1229 @subsection Version @code{--version} or @code{-v}
1231 @code{--version} or @code{-v}: this option ask CLooG to print some version
1235 @subsection Quiet @code{--quiet} or @code{-q}
1237 @code{--quiet} or @code{-q}: this option tells CLooG not to print
1238 any informational messages.
1241 @c %/*************************************************************************
1242 @c % * A Full Example *
1243 @c % *************************************************************************/
1245 @section A Full Example
1247 Let us consider the allocation problem of a Gaussian elimination, i.e. we want
1248 to distribute the various statement instances of the compute kernel onto
1249 different processors. The original code is the following:
1252 for (i=1;j<=N-1;i++) @{
1253 for (j=i+1;j<=N;j++) @{
1254 c[i][j] = a[j][i]/a[i][i] ; /* S1 */
1255 for (k=i+1;k<=N;k++) @{
1256 a[j][k] -= c[i][j]*a[i][k] ; /* S2 */
1263 @noindent The best affine allocation functions can be found by any good automatic
1264 parallelizer like LooPo (@pxref{Gri04}):
1268 \hbox{$ \cases{ \theta _{S1}(i,j)^T &$= (i)$\cr
1269 \theta _{S2}(i,j,k)^T &$= (k)$}$}
1282 @noindent To ensure that on each processor, the set of statement instances is
1283 executed according to the original ordering, we add as minor scattering
1284 dimensions the original scheduling (@pxref{Scattering}):
1288 \hbox{$ \cases{ \theta _{S1}(i,j)^T &$= (i,0,i,0,j,0)^T$\cr
1289 \theta _{S2}(i,j,k)^T &$= (k,0,i,0,j,1,k,0)^T$}$}
1296 T_S1(i,j)^T = (i,0,i,0,j,0)^T
1297 T_S2(i,j,k)^T = (k,0,i,0,j,1,k,0)^T
1302 @noindent To ensure that the scattering functions have the same dimensionality, we
1303 complete the first function with zeroes
1304 (this is a CLooG @value{VERSION} and previous versions requirement,
1305 it should be removed in a future version, don't worry it's absolutely legal !):
1309 \hbox{$ \cases{ \theta _{S1}(i,j)^T &$= (i,0,i,0,j,0,0,0)^T$\cr
1310 \theta _{S2}(i,j,k)^T &$= (k,0,i,0,j,1,k,0)^T$}$}
1317 T_S1(i,j)^T = (i,0,i,0,j,0,0,0)^T
1318 T_S2(i,j,k)^T = (k,0,i,0,j,1,k,0)^T
1323 @noindent The input file corresponding to this code generation problem
1324 could be (this file is provided in the CLooG distribution
1325 as @code{test/manual_gauss.cloog}:
1328 # ---------------------- CONTEXT ----------------------
1331 # Context (no constraints on one parameter)
1332 1 3 # 1 line and 3 columns
1334 1 0 0 # 0 >= 0, always true
1336 1 # We want to set manually the parameter name
1339 # --------------------- STATEMENTS --------------------
1340 2 # Number of statements
1342 1 # First statement: one domain
1343 4 5 # 4 lines and 3 columns
1346 1 -1 0 1 -1 # i <= n-1
1347 1 -1 1 0 -1 # j >= i+1
1349 0 0 0 # for future options
1352 # Second statement: one domain
1353 6 6 # 6 lines and 3 columns
1355 1 1 0 0 0 -1 # i >= 1
1356 1 -1 0 0 1 -1 # i <= n-1
1357 1 -1 1 0 0 -1 # j >= i+1
1358 1 0 -1 0 1 0 # j <= n
1359 1 -1 0 1 0 -1 # k >= i+1
1360 1 0 0 -1 1 0 # k <= n
1361 0 0 0 # for future options
1363 0 # We let CLooG set the iterator names
1365 # --------------------- SCATTERING --------------------
1366 2 # Scattering functions
1368 8 13 # 3 lines and 3 columns
1369 # eq/in p1 p2 p3 p4 p5 p6 p7 p8 i j n 1
1370 0 1 0 0 0 0 0 0 0 -1 0 0 0 # p1 = i
1371 0 0 1 0 0 0 0 0 0 0 0 0 0 # p2 = 0
1372 0 0 0 1 0 0 0 0 0 -1 0 0 0 # p3 = i
1373 0 0 0 0 1 0 0 0 0 0 0 0 0 # p4 = 0
1374 0 0 0 0 0 1 0 0 0 0 -1 0 0 # p5 = j
1375 0 0 0 0 0 0 1 0 0 0 0 0 0 # p6 = 0
1376 0 0 0 0 0 0 0 1 0 0 0 0 0 # p7 = 0
1377 0 0 0 0 0 0 0 0 1 0 0 0 0 # p8 = 0
1379 8 14 # 3 lines and 3 columns
1380 # eq/in p1 p2 p3 p4 p5 p6 p7 p8 i j k n 1
1381 0 1 0 0 0 0 0 0 0 0 0 -1 0 0 # p1 = k
1382 0 0 1 0 0 0 0 0 0 0 0 0 0 0 # p2 = 0
1383 0 0 0 1 0 0 0 0 0 -1 0 0 0 0 # p3 = i
1384 0 0 0 0 1 0 0 0 0 0 0 0 0 0 # p4 = 0
1385 0 0 0 0 0 1 0 0 0 0 -1 0 0 0 # p5 = j
1386 0 0 0 0 0 0 1 0 0 0 0 0 0 -1 # p6 = 1
1387 0 0 0 0 0 0 0 1 0 0 0 -1 0 0 # p7 = k
1388 0 0 0 0 0 0 0 0 1 0 0 0 0 0 # p8 = 0
1390 1 # We want to set manually the scattering dimension names
1391 p1 p2 p3 p4 p5 p6 p7 p8 # scattering dimension names
1394 Calling CLooG, with for instance the command line
1395 @code{cloog -fsp 2 gauss.cloog} for a better view
1396 of the allocation (the processor number is given by @code{p1}),
1397 will result on the following target code that actually implements
1398 the transformation. A minor processing on the dimension @code{p1}
1399 to implement, e.g., MPI calls, which is not shown here may
1400 result in dramatic speedups !
1405 for (p5=2;p5<=n;p5++) @{
1409 for (p1=2;p1<=n-1;p1++) @{
1410 for (p3=1;p3<=p1-1;p3++) @{
1411 for (p5=p3+1;p5<=n;p5++) @{
1412 S2(i = p3,j = p5,k = p1) ;
1415 for (p5=p1+1;p5<=n;p5++) @{
1421 for (p3=1;p3<=n-1;p3++) @{
1422 for (p5=p3+1;p5<=n;p5++) @{
1423 S2(i = p3,j = p5,k = n) ;
1430 @c %/*************************************************************************
1431 @c % * A Full Example *
1432 @c % *************************************************************************/
1434 @chapter Using the CLooG Library
1435 The CLooG Library was implemented to allow the user to call CLooG
1436 directly from his programs, without file accesses or system calls. The
1437 user only needs to link his programs with C libraries. The CLooG
1438 library mainly provides one function (@code{cloog_program_generate})
1439 which takes as input the problem
1440 description with some options, and returns the data structure corresponding
1441 to the generated code (a @code{CloogProgram} structure) which is more or less
1442 an abstract syntax tree.
1443 The user can work with this data structure and/or use
1444 our pretty printing function to write the final code in either C or FORTRAN.
1445 Some other functions are provided for convenience reasons.
1446 These functions as well as the data structures are described in this section.
1449 * CLooG Data Structures::
1452 * Example of Library Utilization::
1456 @node CLooG Data Structures
1457 @section CLooG Data Structures Description
1458 In this section, we describe the data structures used by the loop
1459 generator to represent and to process a code generation problem.
1466 * CloogScatteringList::
1478 @subsection CloogState
1481 CloogState *cloog_state_malloc(void);
1482 void cloog_state_free(CloogState *state);
1486 @noindent The @code{CloogState} structure is (implicitly) needed to perform
1487 any CLooG operation. It should be created using @code{cloog_state_malloc}
1488 before any other CLooG objects are created and destroyed using
1489 @code{cloog_state_free} after all objects have been freed.
1490 It is allowed to use more than one @code{CloogState} structure at
1491 the same time, but an object created within the state of a one
1492 @code{CloogState} structure is not allowed to interact with an object
1493 created within the state of an other @code{CloogState} structure.
1497 @subsection CloogMatrix
1499 @noindent The @code{CloogMatrix} structure is equivalent to the PolyLib
1500 @code{Matrix} data structure (@pxref{Wil93}). This structure is devoted to
1501 represent a set of constraints.
1506 @{ unsigned NbRows ; /* Number of rows. */
1507 unsigned NbColumns ; /* Number of columns. */
1508 cloog_int_t **p; /* Array of pointers to the matrix rows. */
1509 cloog_int_t *p_Init; /* Matrix rows contiguously in memory. */
1511 typedef struct cloogmatrix CloogMatrix;
1515 @noindent The whole matrix is stored in memory row after row at the
1516 @code{p_Init} address. @code{p} is an array of pointers where
1517 @code{p[i]} points to the first element of the @math{i^{th}} row.
1518 @code{NbRows} and @code{NbColumns} are respectively the number of
1519 rows and columns of the matrix.
1520 Each row corresponds to a constraint. The first element of each row is an
1521 equality/inequality tag. The
1522 constraint is an equality @math{p(x) = 0} if the first element is 0, but it is
1523 an inequality @math{p(x) \geq 0} if the first element is 1.
1524 The next elements are the coefficients of the unknowns,
1525 followed by the coefficients of the parameters, and finally the constant term.
1526 For instance, the following three constraints:
1530 \hbox{$ \cases{ -i + m &$= 0$\cr
1532 j + i - k &$\geq 0$}$}
1546 @noindent would be represented by the following rows:
1550 # eq/in i j k m n cst
1557 @noindent To be able to provide different precision version (CLooG
1558 supports 32 bits, 64 bits and arbitrary precision through the GMP library),
1559 the @code{cloog_int_t} type depends on the configuration options (it may be
1560 @code{long int} for 32 bits version, @code{long long int} for 64 bits version,
1561 and @code{mpz_t} for multiple precision version).
1564 @subsection CloogDomain
1567 CloogDomain *cloog_domain_union_read(CloogState *state,
1568 FILE *input, int nb_parameters);
1569 CloogDomain *cloog_domain_from_cloog_matrix(CloogState *state,
1570 CloogMatrix *matrix, int nb_par);
1571 void cloog_domain_free(CloogDomain *domain);
1575 @noindent @code{CloogDomain} is an opaque type representing a polyhedral
1576 domain (a union of polyhedra).
1577 A @code{CloogDomain} can be read
1578 from a file using @code{cloog_domain_union_read} or
1579 converted from a @code{CloogMatrix}.
1580 The input format for @code{cloog_domain_union_read}
1581 is that of @ref{Domain Representation}.
1582 The function @code{cloog_domain_from_cloog_matrix} takes a @code{CloogState}, a
1583 @code{CloogMatrix} and @code{int} as input and returns a pointer to a
1584 @code{CloogDomain}. @code{matrix} describes the domain and @code{nb_par} is the
1585 number of parameters in this domain. The input data structures are neiter
1587 The @code{CloogDomain} can be freed using @code{cloog_domain_free}.
1588 There are also some backend dependent functions for creating
1589 @code{CloogDomain}s.
1592 * CloogDomain/PolyLib::
1596 @node CloogDomain/PolyLib
1597 @subsubsection PolyLib
1600 #include <cloog/polylib/cloog.h>
1601 CloogDomain *cloog_domain_from_polylib_polyhedron(CloogState *state,
1602 Polyhedron *, int nb_par);
1605 The function @code{cloog_domain_from_polylib_polyhedron} takes a PolyLib
1606 @code{Polyhedron} as input and returns a pointer to a @code{CloogDomain}.
1607 The @code{nb_par} parameter indicates the number of parameters
1608 in the domain. The input data structure if neither modified nor freed.
1610 @node CloogDomain/isl
1614 #include <cloog/isl/cloog.h>
1615 CloogDomain *cloog_domain_from_isl_set(struct isl_set *set);
1618 The function @code{cloog_domain_from_isl_set} takes a
1619 @code{struct isl_set} as input and returns a pointer to a @code{CloogDomain}.
1620 The function consumes a reference to the given @code{struct isl_set}.
1623 @node CloogScattering
1624 @subsection CloogScattering
1627 CloogScattering *cloog_domain_read_scattering(CloogDomain *domain,
1629 CloogScattering *cloog_scattering_from_cloog_matrix(CloogState *state,
1630 CloogMatrix *matrix, int nb_scat, int nb_par);
1631 void cloog_scattering_free(CloogScattering *);
1636 The @code{CloogScattering} type represents a scattering function.
1637 A @code{CloogScattering} for a given @code{CloogDomain} can be read
1638 from a file using @code{cloog_scattering_read} or converted
1639 from a @code{CloogMatrix} using @code{cloog_scattering_from_cloog_matrix}.
1640 The function @code{cloog_scattering_from_cloog_matrix} takes a
1641 @code{CloogState}, a @code{CloogMatrix} and two @code{int}s as input and
1643 pointer to a @code{CloogScattering}.
1644 @code{matrix} describes the scattering, while @code{nb_scat} and
1645 @code{nb_par} are the number of scattering dimensions and
1646 the number of parameters, respectively. The input data structures are
1647 neiter modified nor freed.
1648 A @code{CloogScattering} can be freed using @code{cloog_scattering_free}.
1649 There are also some backend dependent functions for creating
1650 @code{CloogScattering}s.
1653 * CloogScattering/PolyLib::
1654 * CloogScattering/isl::
1657 @node CloogScattering/PolyLib
1658 @subsubsection PolyLib
1661 #include <cloog/polylib/cloog.h>
1662 CloogScattering *cloog_scattering_from_polylib_polyhedron(
1663 CloogState *state, Polyhedron *polyhedron, int nb_par);
1666 The function @code{cloog_scattering_from_polylib_polyhedron} takes a PolyLib
1667 @code{Polyhedron} as input and returns a pointer to a @code{CloogScattering}.
1668 The @code{nb_par} parameter indicates the number of parameters
1669 in the domain. The input data structure if neither modified nor freed.
1671 @node CloogScattering/isl
1675 #include <cloog/isl/cloog.h>
1676 CloogScattering *cloog_scattering_from_isl_map(struct isl_map *map);
1679 The function @code{cloog_scattering_from_isl_map} takes a
1680 @code{struct isl_map} as input and returns a pointer to a @code{CloogScattering}.
1681 The input dimensions of the @code{struct isl_map} correspond to the
1682 scattering dimensions, while the output dimensions correspond to the
1684 The function consumes a reference to the given @code{struct isl_map}.
1687 @node CloogScatteringList
1688 @subsection CloogScatteringList
1691 struct cloogscatteringlist @{
1692 CloogScattering *scatt;
1693 struct cloogscatteringlist *next;
1695 typedef struct cloogscatteringlist CloogScatteringList;
1699 @noindent The CloogScatteringList structure represents
1700 a @code{NULL} terminated linked list of scattering functions.
1703 @node CloogStatement
1704 @subsection CloogStatement
1707 struct cloogstatement
1708 @{ int number ; /* The statement unique number. */
1709 void * usr ; /* Pointer for user's convenience. */
1710 struct cloogstatement * next ;/* Next element of the linked list. */
1712 typedef struct cloogstatement CloogStatement ;
1716 @noindent The @code{CloogStatement} structure represents a @code{NULL}
1718 list of statements. In CLooG, a statement is only defined by its unique
1719 number (@code{number}). The user can use the pointer @code{usr} for his
1720 own convenience to link his own statement representation to the
1721 corresponding @code{CloogStatement} structure. The whole management of the
1722 @code{usr} pointer is under the responsibility of the user, in particular,
1723 CLooG never tries to print, to allocate or to free a memory block pointed
1728 @subsection CloogBlock
1732 @{ CloogStatement * statement ; /* Statement list of the block. */
1733 CloogMatrix * scattering ; /* Scattering function of the block. */
1734 int depth ; /* Original block depth.*/
1735 void * usr; /* Pointer for user's convenience. */
1737 typedef struct cloogblock CloogBlock ;
1741 @noindent The @code{CloogBlock} structure represents a statement block.
1742 In a statement block, every statements have the same iteration
1743 domain and the same scattering function (actually, the scattering
1744 functions may differ only by a scalar
1745 coefficient if it just precises the ordering of the statements within
1746 the block). @code{statement} is the statement list where the
1747 statement order matters, @code{scattering} is one of
1748 the statement scattering functions and
1749 @code{depth} is the number of dimensions of the
1750 iteration domain (only the unknown, not the tag/parameters/scalar).
1751 @code{usr} is a pointer for library user's convenience. Note this pointer
1752 is never allocated, freed or printed by CLooG.
1754 @node CloogBlockList
1755 @subsection CloogBlockList
1758 struct cloogdblocklist
1759 @{ CloogBlock * block ;
1760 struct cloogblocklist * next ;
1762 typedef struct cloogblocklist CloogBlockList ;
1766 @noindent The CloogBlockList structure represents a @code{NULL} terminated linked list
1771 @subsection CloogLoop
1775 @{ CloogDomain * domain; /* Iteration domain. */
1776 Value stride ; /* Loop stride. */
1777 CloogBlock * block ; /* Included statement block.*/
1778 void * usr; /* Pointer for user's convenience. */
1779 struct cloogloop * inner ; /* Loop at the next level. */
1780 struct cloogloop * next ; /* Next loop at the same level. */
1782 typedef struct cloogloop CloogLoop ;
1786 @noindent The @code{CloogLoop} structure represents a loop.
1788 loop has an iteration domain (@code{domain}). The iterator's stride for loop
1789 increment is @code{stride}. The loop can include a statement block
1790 in the field @code{block}. If there is no included statement block,
1791 @code{block} is set to @code{NULL}. @code{usr} is a pointer for library
1792 user's convenience. Note that this pointer is never allocated, freed or
1793 printed by CLooG. @code{inner} is a pointer to the inner
1794 loop, and @code{next} a pointer to the next loop in the textual order. If
1795 there are no inner loop or no next loop, the corresponding pointer is set
1800 @subsection CloogNames
1804 @{ int nb_scattering ; /* Scattering dimension number. */
1805 int nb_iterators ; /* Iterator number. */
1806 int nb_parameters ; /* Parameter number. */
1807 char ** scattering ; /* The scattering dimension names. */
1808 char ** iterators ; /* The iterator names. */
1809 char ** parameters ; /* The parameter names. */
1811 typedef struct cloognames CloogNames ;
1815 @noindent The @code{CloogNames} structure represents the scattering dimension,
1816 the iterator and the parameter names in the final program.
1817 @code{nb_scattering}
1818 (respectively @code{nb_iterators} and @code{nb_parameters})
1819 is the number of scattering dimensions number
1820 (respectively the iterator and parameter number)
1821 and of elements in the corresponding array of strings
1823 (respectively @code{iterators} and @code{parameters}).
1824 The @math{i^{th}} scattering dimension name will be associated with the
1825 to the dimension @math{i} of the scattering function.
1826 The @math{i^{th}} iterator name will be associated with the
1827 dimension @math{i} of the iteration domain.
1828 The @math{i^{th}} parameter name will be associated with the
1829 dimension @math{i} of the context polyhedron.
1830 The user has to ensure that there are
1831 enough scattering dimension, iterator and parameter names.
1835 @subsection CloogProgram
1839 @{ char language ; /* The language of the program. */
1840 int nb_scattdims ; /* Scattering dimension number. */
1841 CloogNames * names ; /* Iterators and parameters names. */
1842 CloogDomain * context ; /* The context of the program. */
1843 CloogLoop * loop ; /* The loops of the program. */
1844 CloogBlockList * blocklist ; /* The statement block list. */
1845 void * usr; /* For library user's convenience. */
1847 typedef struct cloogprogram CloogProgram ;
1851 @noindent The @code{CloogProgram} structure represents a static control program kernel.
1852 @code{language} precises the language (@code{c} for C or @code{f} for FORTRAN).
1853 @code{nb_scattdims} gives the number of scattering dimensions.
1854 @code{context} is a pointer to the constraints on the program parameters,
1856 @code{NULL} pointer even if there are no constraints on parameters. In such a
1857 case, set a polyhedron with as many dimensions as there are parameters, with
1858 an @emph{always true} constraint like @math{1 \geq 0} (this is necessary
1859 since the number of parameters is deduced from the dimension number of
1860 the context constraints). @code{loop} is a pointer
1861 to the first loop of the program. @code{names} is a pointer to the various
1862 element names (scattering dimension, iterators, parameters)
1863 of the final program. @code{names} can be the @code{NULL}
1864 pointer if the user do not want to use our pretty printing function.
1865 @code{blocklist} is the linked list of all the statement block structures.
1866 @code{usr} is a pointer for library user's convenience. Note that this pointer
1867 is never allocated, freed or printed by CLooG.
1868 As an example, let us consider the following loop nest:
1871 for (i=0; i<=n; i++) @{
1872 for (j=0; j<=n; j++) @{
1876 for (j=n+1; j<=2*n; j++) @{
1882 @noindent The next figure gives a possible representation in memory for this
1883 program thanks to the CLooG data structures (it has been actually printed
1884 by the @code{cloog_program_print} function). In this figure,
1885 @samp{+-- CloogLoop} denotes an @samp{inner} loop, while a @samp{CloogLoop}
1886 on the same column pointed by an arrow denotes a @samp{next} loop:
1893 | Scattering dimension number: 0
1897 | | Scattering dimension number: 0
1899 | | +-- No scattering string
1901 | | Iterator number -----------: 2
1903 | | +-- Iterator strings ------: i j
1905 | | Parameter number ----------: 1
1907 | | +-- Parameter strings -----: n
1922 | | +-- Null CloogBlock
1926 | | | +-- CloogDomain
1927 | | | | [ 1 0 1 0 0 ]
1928 | | | | [ 1 0 -1 1 0 ]
1929 | | | | [ 1 0 0 0 1 ]
1933 | | | +-- Null CloogBlock
1937 | | | | +-- CloogDomain
1938 | | | | | [ 1 0 0 0 1 ]
1942 | | | | +-- CloogBlock
1944 | | | | | +-- CloogStatement 1
1947 | | | | | | CloogStatement 2
1949 | | | | | +-- Null scattering function
1957 | | | +-- CloogDomain
1958 | | | | [ 1 0 -1 2 0 ]
1959 | | | | [ 1 0 1 -1 -1 ]
1960 | | | | [ 1 0 0 0 1 ]
1964 | | | +-- Null CloogBlock
1968 | | | | +-- CloogDomain
1969 | | | | | [ 1 0 0 0 1 ]
1973 | | | | +-- CloogBlock
1975 | | | | | +-- CloogStatement 3
1977 | | | | | +-- Null scattering function
1989 @subsection CloogOptions
1993 @{ int l ; /* -l option. */
1994 int f ; /* -f option. */
1995 int strides ; /* -strides option. */
1996 int sh ; /* -sh option. */
1997 int esp ; /* -esp option. */
1998 int fsp ; /* -fsp option. */
1999 int otl ; /* -otl option. */
2000 int block ; /* -block option. */
2001 int cpp ; /* -cpp option. */
2002 int compilable ; /* -compilable option. */
2004 typedef struct cloogoptions CloogOptions ;
2008 @noindent The @code{CloogOptions} structure contains all the possible options to
2009 rule CLooG's behaviour (@pxref{Calling CLooG}).
2010 As a reminder, the default values are:
2012 @item @math{l = -1} (optimize control until the innermost loops),
2013 @item @math{f = 1} (optimize control from the outermost loops),
2014 @item @math{strides = 0} (use only unit strides),
2015 @item @math{sh = 0} (do not simplify convex hulls),
2016 @item @math{esp = 1} (do not spread complex equalities),
2017 @item @math{fsp = 1} (start to spread from the first iterators),
2018 @item @math{otl = 1} (simplify loops running only once).
2019 @item @math{block = 0} (do not make statement blocks when not necessary).
2020 @item @math{cpp = 0} (do not generate a compilable part of code using preprocessor).
2021 @item @math{compilable = 0} (do not generate a compilable code).
2025 @node CLooG Functions
2026 @section CLooG Functions Description
2029 * cloog_program_generate::
2030 * cloog_program_scatter::
2031 * cloog_program_pprint::
2032 * cloog_program_read::
2033 * Allocation and Initialization Functions::
2034 * Memory Deallocation Functions::
2035 * Printing Functions::
2039 @node cloog_program_generate
2040 @subsection cloog_program_generate
2043 CloogProgram * cloog_program_generate
2044 ( CloogProgram * program, /* Input program. */
2045 CloogOptions * options /* Options. */
2050 @noindent The @code{cloog_program_generate} function generates
2051 the data structure of the source code that scans the input
2052 polyhedra pointed by @code{program}
2053 according to the options pointed by @code{options}.
2054 The process is made directly on the input structure pointed by
2055 @code{program}, thus the original structure is no longer available
2056 after a call to this function. It returns a pointer to a
2057 @code{CloogProgram} structure containing the
2058 solution in CLooG structures.
2060 The input @code{CloogProgram} structure must have only one loop level
2061 (no inner loops): there is one loop per statement block. For a given block,
2062 the corresponding loop carries the iteration domain, the statement block,
2063 and a loop stride initialized to 1. For instance, the input @code{CloogProgram} structure
2064 that have been sent to @code{cloog_program_generate} to achieve the final
2065 structure and code shown as example in the @code{CloogProgram} structure
2066 description (@pxref{CloogProgram}) was the following one:
2073 | Scattering dimension number: 0
2077 | | Scattering dimension number: 0
2079 | | +-- No scattering string
2081 | | Iterator number -----------: 2
2083 | | +-- Iterator strings ------: i j
2085 | | Parameter number ----------: 1
2087 | | +-- Parameter strings -----: n
2096 | | | [ 1 -1 0 1 0 ]
2098 | | | [ 1 0 -1 1 0 ]
2104 | | | +-- CloogStatement 1
2107 | | | | CloogStatement 2
2109 | | | +-- Null scattering function
2118 | | | [ 1 -1 0 1 0 ]
2119 | | | [ 1 0 1 -1 -1 ]
2120 | | | [ 1 0 -1 2 0 ]
2126 | | | +-- CloogStatement 3
2128 | | | +-- Null scattering function
2137 @node cloog_program_pprint
2138 @subsection cloog_program_pprint
2141 void cloog_program_pprint
2142 ( FILE * file, /* Output file. */
2143 CloogProgram * program, /* Program to print. */
2144 CloogOptions * options /* Options. */
2149 @noindent The function @code{cloog_program_pprint} is a pretty printer for
2150 @code{CloogProgram} structures when it is a solution provided by
2151 the @code{cloog_program_generate} function. It prints the code or pseudo-code in the
2152 file pointed by @code{file} (possibly @code{stdout}) with regards to the
2153 options pointed by @code{options}.
2156 @node cloog_program_scatter
2157 @subsection cloog_program_scatter
2160 void cloog_program_scatter(
2161 CloogProgram *program, /* Input program. */
2162 CloogScatteringList *scatt, /* Additional scattering functions. */
2163 CloogOptions *options /* Options. */
2168 @noindent The function @code{cloog_program_scatter} applies scattering
2169 functions to the @code{CloogProgram} structure pointed by @code{program}.
2170 Original domains of @code{program} are freed. Scattering functions
2171 are inside the @code{CloogScatteringList} structure pointed by @code{scattering}.
2172 There must be as many scattering functions in the @code{CloogScatteringList}
2173 structure as loops (i.e. iteration domains) in the @code{CloogProgram}
2174 structure. The first scattering function of the list will be applied to the
2175 iteration domain of the first loop in the program, and so on.
2176 @code{names} gives the scattering dimension names as an array of strings. If
2177 @code{names} is @code{NULL}, names are automatically generated: the name of
2178 the @math{n^{th}} scattering dimension will be @code{cn}.
2181 @node cloog_program_read
2182 @subsection cloog_program_read
2184 CloogProgram * cloog_program_read(FILE *) ;
2186 @noindent The @code{cloog_program_read} function
2187 reads the program data from a CLooG input file
2188 (@pxref{Writing The Input File}). It takes
2189 as input a pointer to the file it has to read (possibly @code{stdin}), and
2190 return a pointer to the read @code{CloogProgram} structure.
2193 @node Allocation and Initialization Functions
2194 @subsection Allocation and Initialization Functions
2196 CloogStructure * cloog_structure_malloc() ;
2198 @noindent Each CLooG data structure has an allocation and initialization
2199 function as shown above, where @code{Structure} and @code{structure} have to
2200 be replaced by the name of the convenient structure (without @samp{Cloog} prefix) for
2201 instance @code{CloogLoop * cloog_loop_malloc() ;}. These functions return
2202 pointers to an allocated structure with fields set to convenient default
2203 values. @strong{Using those functions is mandatory} to support internal
2204 management fields and to avoid upward compatibility problems if
2205 new fields appear. An exception is @code{cloog_matrix_malloc} since the
2206 @code{CloogMatrix} comes directly from the PolyLib. It takes two parameters:
2207 the number of rows and columns of the matrix we want to allocate:
2209 CloogMatrix * cloog_matrix_malloc(unsigned nbrows, unsigned nbcolumns);
2213 @node Memory Deallocation Functions
2214 @subsection Memory Deallocation Functions
2216 void cloog_structure_free(CloogStructure *) ;
2218 @noindent Each CLooG data structure has a deallocation function as shown above,
2219 where @code{Structure} and @code{structure} have to
2220 be replaced by the name of the convenient structure (without @samp{Cloog} prefix) for
2221 instance @code{void cloog_loop_free(CloogLoop *) ;}. These functions
2222 free the allocated memory for the structure provided as input. They free
2223 memory recursively, i.e. they also free the allocated memory for the internal
2225 @strong{Using those functions is mandatory} to avoid memory leaks on internal
2226 management fields and to avoid upward compatibility problems if
2230 @node Printing Functions
2231 @subsection Printing Functions
2233 void cloog_structure_print(FILE *, CloogStructure *) ;
2235 @noindent Each CLooG data structure has a printing function as shown above,
2236 where @code{Structure} and @code{structure} have to
2237 be replaced by the name of the convenient structure (without @samp{Cloog} prefix) for
2238 instance @code{void cloog_loop_print(FILE *, CloogLoop *) ;}. These functions
2239 print the pointed structure (and its fields recursively) to the file provided
2240 as input (possibly @code{stdout}).
2244 @section CLooG Output
2247 Given a @code{CloogProgram} for scanning the input polyhedra,
2248 computed using @code{cloog_program_generate}
2249 (@pxref{cloog_program_generate}),
2250 an AST corresponding to the @code{CloogProgram} can be constructed
2251 using @code{cloog_clast_create} and destroyed using
2252 @code{free_clast_stmt}.
2254 struct clast_stmt *cloog_clast_create(CloogProgram *program,
2255 CloogOptions *options);
2256 void free_clast_stmt(struct clast_stmt *s);
2259 @code{clast_stmt} represents a linked list of ``statements''.
2261 struct clast_stmt @{
2262 const struct clast_stmt_op *op;
2263 struct clast_stmt *next;
2267 The entries in the list are not of type @code{clast_stmt} itself,
2268 but of some larger type. The following statement types are defined
2272 struct clast_root @{
2273 struct clast_stmt stmt;
2276 struct clast_root *new_clast_root(CloogNames *names);
2278 struct clast_assignment @{
2279 struct clast_stmt stmt;
2281 struct clast_expr * RHS;
2283 struct clast_assignment *new_clast_assignment(const char *lhs,
2284 struct clast_expr *rhs);
2286 struct clast_block @{
2287 struct clast_stmt stmt;
2288 struct clast_stmt * body;
2290 struct clast_block *new_clast_block(void);
2292 struct clast_user_stmt @{
2293 struct clast_stmt stmt;
2294 CloogStatement * statement;
2295 struct clast_stmt * substitutions;
2297 struct clast_user_stmt *new_clast_user_stmt(CloogStatement *stmt,
2298 struct clast_stmt *subs);
2301 struct clast_stmt stmt;
2302 const char * iterator;
2303 struct clast_expr * LB;
2304 struct clast_expr * UB;
2306 struct clast_stmt * body;
2308 struct clast_for *new_clast_for(const char *it, struct clast_expr *LB,
2309 struct clast_expr *UB, cloog_int_t stride);
2311 struct clast_guard @{
2312 struct clast_stmt stmt;
2313 struct clast_stmt * then;
2315 struct clast_equation eq[1];
2317 struct clast_guard *new_clast_guard(int n);
2320 The @code{clast_stmt} returned by @code{cloog_clast_create}
2321 is a @code{clast_root}.
2322 It contains a placeholder for all the variable names that appear
2323 in the AST and a (list of) nested statement(s).
2326 A @code{clast_assignment} assigns the value given by
2327 the @code{clast_expr} @code{RHS} to a variable named @code{LHS}.
2330 A @code{clast_block} groups a list of statements into one statement.
2331 These statements are only generated if the @code{block} option is set,
2332 @pxref{Statement Block} and @ref{CloogOptions}.
2335 A @code{clast_user_stmt} represents a call to a statement specified
2336 by the user, @pxref{CloogStatement}.
2337 @code{substitutions} is a list of @code{clast_assignment} statements
2338 assigning an expression in terms of the scattering dimensions to
2339 each of the original iterators in the original order.
2340 The @code{LHS}s of these assignments are left blank (@code{NULL}).
2343 A @code{clast_for} represents a for loop, iterating @code{body} for each
2344 value of @code{iterator} between @code{LB} and @code{UB} in steps
2345 of size @code{stride}.
2348 A @code{clast_guard} represents the guarded execution of the @code{then}
2349 (list of) statement(s) by a conjunction of @code{n} (in)equalities.
2350 Each (in)equality is represented by a @code{clast_equation}.
2352 struct clast_equation @{
2353 struct clast_expr * LHS;
2354 struct clast_expr * RHS;
2359 The condition expressed by a @code{clast_equation} is
2360 @code{LHS <= RHS}, @code{LHS == RHS} or @code{LHS >= RHS}
2361 depending on whether @code{sign} is less than zero, equal
2362 to zero, or greater than zero.
2364 The dynamic type of a @code{clast_stmt} can be determined
2365 using the macro @code{CLAST_STMT_IS_A(stmt,type)},
2366 where @code{stmt} is a pointer to a @code{clast_stmt}
2367 and @code{type} is one of @code{stmt_root}, @code{stmt_ass},
2368 @code{stmt_user}, @code{stmt_block}, @code{stmt_for} or
2370 Users are allowed to define their own statement types by
2371 assigning the @code{op} field of the statements a pointer
2372 to a @code{clast_stmt_op} structure.
2374 struct clast_stmt_op @{
2375 void (*free)(struct clast_stmt *);
2379 The @code{free} field of this structure should point
2380 to a function that frees the user defined statement.
2383 A @code{clast_expr} can be an identifier, a term,
2384 a binary expression or a reduction.
2386 enum clast_expr_type @{
2392 struct clast_expr @{
2393 enum clast_expr_type type;
2395 void free_clast_expr(struct clast_expr *e);
2399 Identifiers are of subtype @code{clast_name}.
2401 struct clast_name @{
2402 struct clast_expr expr;
2405 struct clast_name *new_clast_name(const char *name);
2406 void free_clast_name(struct clast_name *t);
2409 The character string pointed to by @code{name} is
2410 assumed to be part of the @code{CloogNames} structure
2411 in the root of the clast as is therefore not copied.
2414 Terms are of type @code{clast_term}.
2416 struct clast_term @{
2417 struct clast_expr expr;
2419 struct clast_expr *var;
2421 struct clast_term *new_clast_term(cloog_int_t c, struct clast_expr *v);
2422 void free_clast_term(struct clast_term *t);
2425 If @code{var} is set to @code{NULL}, then the term represents
2426 the integer value @code{val}. Otherwise, it represents
2427 the term @code{val * var}.
2428 @code{new_clast_term} simply copies the @code{v} pointer
2429 without copying the underlying @code{clast_expr}.
2430 @code{free_clast_term}, on the other hand, recursively frees
2434 Binary expressions are of type @code{clast_bin_type} and
2435 represent either the floor of a division (fdiv),
2436 the ceil of a division (cdiv), an exact division or
2437 the remainder of an fdiv.
2439 enum clast_bin_type @{ clast_bin_fdiv, clast_bin_cdiv,
2440 clast_bin_div, clast_bin_mod @};
2441 struct clast_binary @{
2442 struct clast_expr expr;
2443 enum clast_bin_type type;
2444 struct clast_expr* LHS;
2447 struct clast_binary *new_clast_binary(enum clast_bin_type t,
2448 struct clast_expr *lhs, cloog_int_t rhs);
2449 void free_clast_binary(struct clast_binary *b);
2453 Reductions are of type @code{clast_reduction} and
2454 can represent either the sum, the minimum or the maximum
2457 enum clast_red_type @{ clast_red_sum, clast_red_min, clast_red_max @};
2458 struct clast_reduction @{
2459 struct clast_expr expr;
2460 enum clast_red_type type;
2462 struct clast_expr* elts[1];
2464 struct clast_reduction *new_clast_reduction(enum clast_red_type t,
2466 void free_clast_reduction(struct clast_reduction *r);
2470 @node Example of Library Utilization
2471 @section Example of Library Utilization
2472 Here is a basic example showing how it is possible to use the CLooG library,
2473 assuming that a standard installation has been done.
2474 The following C program reads a CLooG input file on the standard input,
2475 then prints the solution on the standard output.
2476 Options are preselected to the default values of the CLooG software.
2477 This example is provided in the @code{example} directory of the
2482 # include <cloog/cloog.h>
2487 CloogProgram *program;
2488 CloogOptions * options ;
2490 /* Setting options and reading program informations. */
2491 state = cloog_state_malloc();
2492 options = cloog_options_malloc(state);
2493 program = cloog_program_read(stdin,options) ;
2495 /* Generating and printing the code. */
2496 program = cloog_program_generate(program,options) ;
2497 cloog_program_pprint(stdout,program,options) ;
2499 cloog_options_free(options) ;
2500 cloog_program_free(program) ;
2501 cloog_state_free(state);
2506 @noindent The compilation command could be:
2508 gcc example.c -lcloog -o example
2510 @noindent A calling command with the input file test.cloog could be:
2512 more test.cloog | ./example
2516 @c % ******************************** HACKING *********************************
2518 @c @chapter Hacking CLooG
2521 @c * Program organization::
2522 @c * Special Options::
2523 @c * CLooG Coding Standards::
2526 @c @node Program organization
2527 @c @section Program organization
2529 @c @node Special Options
2530 @c @section Special Options
2532 @c @node CLooG Coding Standards
2533 @c @section CLooG Coding Standards
2536 @c % ****************************** INSTALLING ********************************
2538 @chapter Installing CLooG
2543 * Basic Installation::
2544 * Optional Features::
2550 First of all, it would be very kind to refer the following paper in any
2551 publication that result from the use of the CLooG software or its library,
2552 @pxref{Bas04} (a bibtex entry is provided behind the title page of this
2553 manual, along with copyright notice, and in the CLooG home
2554 @code{http://www.CLooG.org}.
2556 This library is free software; you can redistribute it and/or
2557 modify it under the terms of the GNU Lesser General Public
2558 License as published by the Free Software Foundation; either
2559 version 2.1 of the License, or (at your option) any later version.
2560 This library is distributed in the hope that it will be useful,
2561 but WITHOUT ANY WARRANTY; without even the implied warranty of
2562 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
2563 Lesser General Public License for more details.
2564 @code{http://www.gnu.org/licenses/lgpl-2.1.html}
2566 Note, though, that if you link CLooG against a GPL library such
2567 as the PolyLib backend, then the combination becomes GPL too.
2568 In particular, a CLooG library based on the PolyLib backend
2569 is GPL version 2 only.
2570 Since the isl backend is LGPL, linking against it does not affect
2571 the license of CLooG.
2575 @section Requirements
2577 CLooG can be used with one of two possible backends,
2578 one using isl and one using PolyLib.
2579 The isl library is included in the CLooG distribution,
2580 while the PolyLib library needs to be obtained separately.
2581 On the other hand, isl requires GMP, while PolyLib can be
2582 compiled with or without the use of GMP.
2583 The user therefore needs to install at least one of
2593 @subsection PolyLib (optional)
2594 To successfully install CLooG with the PolyLib backend,
2595 the user first needs to install PolyLib
2596 version 5.22.1 or above (default 64 bits version is satisfying
2597 as well as 32 bits or GMP multiple precision version).
2598 Polylib can be downloaded freely
2599 at @code{http://icps.u-strasbg.fr/PolyLib/} or
2600 @code{http://www.irisa.fr/polylib/}. Once downloaded and unpacked
2601 (e.g. using the @samp{tar -zxvf polylib-5.22.3.tar.gz} command),
2602 the user can compile
2603 it by typing the following commands on the PolyLib's root directory:
2606 @item @code{./configure}
2608 @item And as root: @code{make install}
2611 Alternatively, the latest development version can be obtained from the
2614 @item @code{git clone git://repo.or.cz/polylib.git}
2615 @item @code{cd polylib}
2616 @item @code{./autogen.sh}
2617 @item @code{./configure}
2619 @item And as root: @code{make install}
2622 The PolyLib default installation is @code{/usr/local}. This directory may
2623 not be inside your library path. To fix the problem, the user should set
2625 export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib
2627 @noindent if your shell is, e.g., bash or
2629 setenv LD_LIBRARY_PATH $LD_LIBRARY_PATH:/usr/local/lib
2631 @noindent if your shell is, e.g., tcsh. Add the line to your .bashrc or .tcshrc (or
2632 whatever convenient file) to make this change permanent. Another solution
2633 is to ask PolyLib to install in the standard path by using the prefix
2634 option of the configure script:
2635 @samp{./configure --prefix=/usr}.
2637 CLooG makes intensive calls to polyhedral operations, and PolyLib
2638 functions do the job. Polylib is a free library written in C for the
2639 manipulation of polyhedra. The library is operating on objects like
2640 vectors, matrices, lattices, polyhedra, Z-polyhedra, unions of
2641 polyhedra and a lot of other intermediary structures. It provides
2642 functions for all the important operations on these structures.
2645 @subsection GMP Library (optional)
2647 To be able to deal with insanely large coefficient, the user will need to
2648 install the GNU Multiple Precision Library (GMP for short) version 4.1.4
2649 or above. It can be freely downloaded from @code{http://www.swox.com/gmp}.
2650 Note that the isl backend currently requires GMP.
2651 The user can compile GMP by typing the following commands on the GMP root
2655 @item @code{./configure}
2657 @item And as root: @code{make install}
2660 The GMP default installation is @code{/usr/local}, the same method to
2661 fix a library path problem applies as with PolyLib (@pxref{PolyLib}).
2663 If you want to use the PolyLib backend, then
2664 PolyLib has to be built using the GMP library by specifying the option
2665 @samp{--with-libgmp=PATH_TO_GMP} to the PolyLib configure script
2666 (where @code{PATH_TO_GMP} is @code{/usr/local} if you did not change the GMP
2667 installation directory). Then you have to set the convenient CLooG configure
2668 script options to build the GMP version (@pxref{Optional Features}).
2671 @node Basic Installation
2672 @section CLooG Basic Installation
2674 Once downloaded and unpacked
2675 (e.g. using the @samp{tar -zxvf cloog-@value{VERSION}.tar.gz} command),
2676 you can compile CLooG by typing the following commands on the CLooG's root
2680 @item @code{./configure}
2682 @item And as root: @code{make install}
2685 Alternatively, the latest development version can be obtained from the
2688 @item @code{git clone git://repo.or.cz/cloog.git}
2689 @item @code{cd cloog}
2690 @item @code{./get_submodules.sh}
2691 @item @code{./autogen.sh}
2692 @item @code{./configure}
2694 @item And as root: @code{make install}
2697 Depending on which backend you want to use and where they
2698 are located, you may need to pass some
2699 options to the configure script, @pxref{Optional Features}.
2701 The program binaries and object files can be removed from the
2702 source code directory by typing @code{make clean}. To also remove the
2703 files that the @code{configure} script created (so you can compile the
2704 package for a different kind of computer) type @code{make distclean}.
2706 Both the CLooG software and library have been successfully compiled
2707 on the following systems:
2709 @item PC's under Linux, with the @code{gcc} compiler,
2710 @item PC's under Windows (Cygwin), with the @code{gcc} compiler,
2711 @item Sparc and UltraSparc Stations, with the @code{gcc} compiler.
2714 @node Optional Features
2715 @section Optional Features
2716 The @code{configure} shell script attempts to guess correct values for
2717 various system-dependent variables and user options used during compilation.
2718 It uses those values to create the @code{Makefile}. Various user options
2719 are provided by the CLooG's configure script. They are summarized in the
2720 following list and may be printed by typing @code{./configure --help} in the
2721 CLooG top-level directory.
2724 @item By default, the installation directory is @code{/usr/local}:
2725 @code{make install} will install the package's files in
2726 @code{/usr/local/bin}, @code{/usr/local/lib} and @code{/usr/local/include}.
2727 The user can specify an installation prefix other than @code{/usr/local} by
2728 giving @code{configure} the option @code{--prefix=PATH}.
2730 @item By default, the isl backend will use the version of isl
2731 that is @code{bundled} together with CLooG.
2732 Using the @code{--with-isl} option of @code{configure}
2733 the user can specify that @code{no} isl,
2734 a previously installed (@code{system}) isl or a @code{build} isl
2736 In the latter case, the user should also specify the build location
2737 using @code{--with-isl-builddir=PATH}.
2738 In case of an installed isl,
2739 the installation location can be specified using the
2740 @code{--with-isl-prefix=PATH} and
2741 @code{--with-isl-exec-prefix=PATH} options of @code{configure}.
2743 @item By default, the PolyLib backend will use an installed
2744 (@code{system}) PolyLib, if any.
2745 The installation location can be specified using the
2746 @code{--with-polylib-prefix=PATH} and
2747 @code{--with-polylib-exec-prefix=PATH} options of @code{configure}.
2748 Using the @code{--with-polylib} option of @code{configure}
2749 the user can specify that @code{no} PolyLib or a @code{build} PolyLib
2751 In the latter case, the user should also specify the build location
2752 using @code{--with-polylib-builddir=PATH}.
2754 @item By default, the PolyLib backend of CLooG is built
2755 in 64bits version if such version of the
2756 PolyLib is found by @code{configure}. If the only existing version of the
2757 PolyLib is the 32bits or if the user give to @code{configure} the option
2758 @code{--with-bits=32}, the 32bits version of CLooG will be compiled. In the
2759 same way, the option @code{--with-bits=gmp} have to be used to build
2760 the multiple precision version.
2762 @item By default, @code{configure} will look for the GMP library
2763 (necessary to build the multiple precision version) in standard
2764 locations. If necessary, the user can specify the GMP path by giving
2765 @code{configure} the option @code{--with-gmp-prefix=PATH} and/or
2766 @code{--with-gmp-exec-prefix=PATH}.
2769 @node Uninstallation
2770 @section Uninstallation
2771 The user can easily remove the CLooG software and library from his system
2772 by typing (as root if necessary) from the CLooG top-level directory
2773 @code{make uninstall}.
2775 @c % **************************** DOCUMENTATION ******************************
2777 @chapter Documentation
2778 The CLooG distribution provides several documentation sources. First, the
2779 source code itself is as documented as possible. The code comments use a
2780 Doxygen-compatible presentation (something similar to what JavaDoc does for
2781 JAVA). The user may install Doxygen
2782 (see @code{http://www.stack.nl/~dimitri/doxygen}) to automatically
2783 generate a technical documentation by typing @code{make doc} or
2784 @code{doxygen ./autoconf/Doxyfile} at the CLooG top-level directory after
2785 running the configure script (@pxref{Installing}). Doxygen will generate
2786 documentation sources (in HTML, LaTeX and man) in the @code{doc/source}
2787 directory of the CLooG distribution.
2789 The Texinfo sources of the present document are also provided in the @code{doc}
2790 directory. You can build it in either DVI format (by typing
2791 @code{texi2dvi cloog.texi}) or PDF format
2792 (by typing @code{texi2pdf cloog.texi}) or HTML format
2793 (by typing @code{makeinfo --html cloog.texi}, using @code{--no-split}
2794 option to generate a single HTML file) or info format
2795 (by typing @code{makeinfo cloog.texi}).
2797 @c % ****************************** REFERENCES ********************************
2803 @anchor{Bas03a}[Bas03a] C. Bastoul, P. Feautrier. Improving data locality
2804 by chunking. CC'12 International Conference on Compiler Construction,
2805 LNCS 2622, pages 320-335, Warsaw, april 2003.
2808 @anchor{Bas03b}[Bas03b] C. Bastoul. Efficient code generation for automatic
2809 parallelization and optimization. ISPDC'03 IEEE International Symposium on
2810 Parallel and Distributed Computing, pages 23-30, Ljubljana, october 2003.
2813 @anchor{Bas04}[Bas04] C. Bastoul. Code Generation in the Polyhedral Model
2814 Is Easier Than You Think. PACT'13 IEEE International Conference on Parallel
2815 Architecture and Compilation Techniques, pages 7-16, Juan-les-Pins,
2819 @anchor{Fea92}[Fea92] P. Feautrier Some efficient solutions to the affine
2820 scheduling problem, part II: multidimensional time.
2821 International Journal of Parallel Programming, 21(6):389--420, December 1992.
2824 @anchor{Gri04}[Gri04] M. Griebl. Automatic parallelization of loop programs
2825 for distributed memory architectures. Habilitation Thesis. Facult@"at f@"ur
2826 Mathematik und Informatik, Universit@"at Passau, 2004.
2827 @emph{http://www.infosun.fmi.uni-passau.de/cl/loopo/}
2830 @anchor{Qui00}[Qui00] F. Quiller@'e, S. Rajopadhye, and D. Wilde.
2831 Generation of efficient nested loops from polyhedra.
2832 International Journal of Parallel Programming, 28(5):469-498,
2836 @anchor{Wil93}[Wil93] Doran K. Wilde.
2837 A library for doing polyhedral operations.
2838 Technical Report 785, IRISA, Rennes, France, 1993.
2845 @c % /*************************************************************************
2846 @c % * PART VI: END OF THE DOCUMENT *
2847 @c % *************************************************************************/
2848 @c @unnumbered Index