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_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
523 Nb_statements ::= _Integer
524 Nb_domains ::= _Integer
525 Nb_functions ::= _Integer
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.
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
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
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
579 * Domain Representation::
580 * Scattering Representation::
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
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.
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
605 \hbox{$ \cases{ -i + m &$\geq 0$\cr
607 i + j - k &$\geq 0$}$}
621 @noindent can be written in the input file as follows :
626 3 7 # 3 lines and 7 columns
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
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:
642 for (i=1;i<=n;i++) @{
643 if ((i >= m) || (i <= 2*m))
651 @noindent The iteration domain of @samp{S1} can be divided into two
652 polyhedra and written in the input file as follows:
656 2 # Number of polyhedra in the union
658 3 5 # 3 lines and 5 columns
664 3 5 # 3 lines and 5 columns
668 1 -1 2 0 0 # i <= 2*m
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:
688 for (i=1;i<=n;i++) @{
689 if ((i >= m) || (i <= 2*m))
699 \hbox{$ \cases{ \theta _{S1}(i) &$= (i,0)^T$\cr
700 \theta _{S2}(i,j)^T &$= (n,i+j)^T$}$}
708 T_S2(i,j)^T = (n,i+j)^T
714 @noindent This scheduling can be written in the input file as follows:
718 2 # Number of scattering functions
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
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
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}:
737 # ---------------------- CONTEXT ----------------------
740 # Context (no constraints on two parameters)
741 1 4 # 1 lines and 4 columns
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
753 3 5 # 3 lines and 5 columns
759 3 5 # 3 lines and 5 columns
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
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
778 # --------------------- SCATTERING --------------------
779 2 # Scattering functions
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
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
796 @c %/*************************************************************************
797 @c % * Calling CLooG *
798 @c % *************************************************************************/
800 @section Calling CLooG
801 CLooG is called by the following command:
803 cloog [ options | file ]
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 % *************************************************************************/
818 @section CLooG Options
821 * Last Depth to Optimize Control::
822 * First Depth to Optimize Control::
823 * Simplify Convex Hull::
824 * Once Time Loop Elimination::
825 * Equality Spreading::
826 * First Level for Spreading::
838 @node Last Depth to Optimize Control
839 @subsection Last Depth to Optimize Control @code{-l <depth>}
841 @code{-l <depth>}: this option sets the last loop depth to be optimized in
842 control. The higher this depth, the less control overhead.
843 For instance, with some input file, a user can generate
844 different pseudo-codes with different @code{depth} values as shown below.
847 /* Generated using a given input file and @strong{option -l 1} */
848 for (i=0;i<=M;i++) @{
850 for (j=0;j<=N;j++) @{
853 for (j=0;j<=N;j++) @{
862 /* Generated using the same input file but @strong{option -l 2} */
863 for (i=0;i<=M;i++) @{
865 for (j=0;j<=N;j++) @{
873 In this example we can see that this option can change the operation
874 execution order between statements. Let us remind that CLooG does not
875 make any speculation on dependences between statements
876 (@pxref{Scattering}). Thus if nothing (i.e. scattering functions)
877 forbids this, CLooG considers the above codes to be equivalent.
878 If there is no scattering functions, the minimum value for @code{depth}
879 is 1 (in the case of 0, the user doesn't really need a loop generator !),
880 and the number of scattering dimensions otherwise (CLooG will warn the
881 user if he doesn't respect such constraint).
882 The maximum value for depth is -1 (infinity).
883 Default value is infinity.
885 @node First Depth to Optimize Control
886 @subsection First Depth to Optimize Control @code{-f <depth>}
888 @code{-f <depth>}: this option sets the first loop depth to be optimized
889 in control. The lower this depth, the less control overhead (and the longer
890 the generated code). For instance, with some input file, a user
891 can generate different pseudo-codes with different @code{depth} values
893 The minimum value for @code{depth} is 1, and the
894 maximum value is -1 (infinity).
898 /* Generated using a given input file and @strong{option -f 3} */
899 for (i=1;i<=N;i++) @{
900 for (j=1;j<=M;j++) @{
911 /* Generated using the same input file but @strong{option -f 2} */
912 for (i=1;i<=N;i++) @{
913 for (j=1;j<=9;j++) @{
916 for (j=10;j<=M;j++) @{
924 @node Simple Convex Hull
925 @subsection Simple Convex Hull @code{-sh <boolean>}
927 @code{-sh <boolean>}: this option enables (@code{boolean=1})
928 or forbids (@code{boolean=0}) the use of an overapproximation
929 of the convex hull that may be easier to compute
930 (especially in the isl backend) and that may result in
932 This option works only for generated code without
933 code duplication (it means, you have to tune @code{-f} and
934 @code{-l} options first to generate only a loop nest with internal
935 guards). For instance, with the input file @code{test/union.cloog}, a user
936 can generate different pseudo-codes as shown below.
940 /* Generated using test/union.cloog and @strong{option -f -1 -l 2 -override} */
941 for (i=0;i<=11;i++) @{
942 for (j=max(0,5*i-50);j<=min(15,5*i+10);j++) @{
943 if ((i <= 10) && (j <= 10)) @{
946 if ((i >= 1) && (j >= 5)) @{
955 /* Generated using the same input file but @strong{option -sh 1 -f -1 -l 2 -override} */
956 for (i=0;i<=11;i++) @{
957 for (j=0;j<=15;j++) @{
958 if ((i <= 10) && (j <= 10)) @{
961 if ((i >= 1) && (j >= 5)) @{
969 @node Once Time Loop Elimination
970 @subsection Once Time Loop Elimination @code{-otl <boolean>}
972 @code{-otl <boolean>}: this option allows (@code{boolean=1}) or
973 forbids (@code{boolean=0}) the simplification of loops running
974 once. Default value is 1.
977 /* Generated using a given input file and @strong{option -otl 0} */
978 for (j=i+1;j<=i+1;j++) @{
985 /* Generated using the same input file but @strong{option -otl 1} */
992 @node Equality Spreading
993 @subsection Equality Spreading @code{-esp <boolean>}
995 @code{-esp <boolean>}: this option allows (@code{boolean=1}) or
996 forbids (@code{boolean=0}) values spreading when there
997 are equalities. Default value is 1.
1000 /* Generated using a given input file and @strong{option -esp 0} */
1003 for (k=i;k<=j+M;k++) @{
1010 /* Generated using the same input file but @strong{option -esp 1} */
1011 for (k=M+2;k<=N+M;k++) @{
1012 S1(i = M+2, j = N) ;
1018 @node First Level for Spreading
1019 @subsection First Level for Spreading @code{-fsp <level>}
1021 @code{-fsp <level>}: it can be useful to set a
1022 first level to begin equality spreading. Particularly when using
1023 scattering functions, the user may want to see the scattering dimension
1024 values instead of spreading or hiding them. If user has set a
1025 spreading, @code{level} is
1026 the first level to start it. Default value is 1.
1029 /* Generated using a given input file and @strong{option -fsp 1} */
1030 for (j=0;j<=N+M;j++) @{
1033 for (j=0;j<=N+M;j++) @{
1040 /* Generated using the same input file but @strong{option -fsp 2} */
1042 for (j=0;j<=c1+M;j++) @{
1046 for (j=0;j<=N+c1;j++) @{
1053 @node Statement Block
1054 @subsection Statement Block @code{-block <boolean>}
1056 @code{-block <boolean>}: this option allows (@code{boolean=1}) to
1057 create a statement block for each new iterator, even if there is only
1058 an equality. This can be useful in order to parse the generated
1059 pseudo-code. When @code{boolean} is set to 0 or when the generation
1060 language is FORTRAN, this feature is disabled. Default value is 0.
1063 /* Generated using a given input file and @strong{option -block 0} */
1071 /* Generated using the same input file but @strong{option -block 1} */
1082 @subsection Loop Strides @code{-strides <boolean>}
1084 @code{-strides <boolean>}: this options allows (@code{boolean=1}) to
1085 handle non-unit strides for loop increments. This can remove a lot of
1086 guards and make the generated code more efficient. Default value is 0.
1089 /* Generated using a given input file and @strong{option -strides 0} */
1090 for (i=1;i<=n;i++) @{
1102 /* Generated using the same input file but @strong{option -strides 1} */
1103 for (i=2;i<=n;i+=2) @{
1114 @subsection First Depth to Unroll @code{-first-unroll <depth>}
1116 @code{-first-unroll <depth>}: this option sets the first loop depth
1117 to unroll. Note that a loop is only unrolled when it is supported
1118 by the backend. In case of the isl backend, a loop is unrolled
1119 if it has a lower bound that can only be incremented
1120 a fixed (non-parametric) amount of times.
1123 @node Compilable Code
1124 @subsection Compilable Code @code{-compilable <value>}
1126 @code{-compilable <value>}: this options allows (@code{value} is not 0)
1127 to generate a compilable code where all parameters have the integral value
1128 @code{value}. This option creates a macro for each statement. Since
1129 CLooG do not know anything about the statement sources, it fills the
1130 macros with a basic increment that computes the total number of
1131 scanned integral points. The user may change easily the macros according
1132 to his own needs. This option is possible only if the generated code is
1133 in C. Default value is 0.
1136 /* Generated using a given input file and @strong{option -compilable 0} */
1137 for (i=0;i<=n;i++) @{
1138 for (j=0;j<=n;j++) @{
1147 /* Generated using the same input file but @strong{option -compilable 10} */
1148 /* DON'T FORGET TO USE -lm OPTION TO COMPILE. */
1150 /* Useful headers. */
1155 /* Parameter value. */
1158 /* Statement macros (please set). */
1159 #define S1(i,j) @{total++;@}
1160 #define S2(i,j) @{total++;@}
1161 #define S3(i) @{total++;@}
1164 /* Original iterators. */
1167 int n=PARVAL, total=0 ;
1169 for (i=0;i<=n;i++) @{
1170 for (j=0;j<=n;j++) @{
1177 printf("Number of integral points: %d.\n",total) ;
1183 @subsection Callable Code @code{-callable <boolean>}
1185 @code{-callable <boolean>}: if @code{boolean=1}, then a @code{test}
1186 function will be generated that has the parameters as arguments.
1187 Similarly to the @code{-compilable} option,
1188 a macro for each statement is generated. The generated definitions of
1189 these macros are as used during the correctness testing, but they
1190 can easily be changed by the user to suit her own needs.
1191 This option is only available if the target language is C.
1192 The default value is 0.
1195 /* Generated from double.cloog with @strong{option -callable 0} */
1196 for (i=0;i<=M;i++) @{
1198 for (j=0;j<=N;j++) @{
1206 /* Generated from double.cloog with @strong{option -callable 1} */
1207 extern void hash(int);
1209 /* Useful macros. */
1210 #define floord(n,d) (((n)<0) ? ((n)-(d)+1)/(d) : (n)/(d))
1211 #define ceild(n,d) (((n)<0) ? (n)/(d) : ((n)+(d)+1)/(d))
1212 #define max(x,y) ((x) > (y) ? (x) : (y))
1213 #define min(x,y) ((x) < (y) ? (x) : (y))
1215 #define S1(i) @{ hash(1); hash(i); @}
1216 #define S2(i,j) @{ hash(2); hash(i); hash(j); @}
1217 #define S3(i,j) @{ hash(3); hash(i); hash(j); @}
1218 #define S4(i) @{ hash(4); hash(i); @}
1220 void test(int M, int N)
1222 /* Original iterators. */
1224 for (i=0;i<=M;i++) @{
1226 for (j=0;j<=N;j++) @{
1236 @subsection Output @code{-o <output>}
1238 @code{-o <output>}: this option sets the output file. @code{stdout} is a
1239 special value: when used, output is standard output.
1240 Default value is @code{stdout}.
1243 @subsection OpenScop @code{-openscop}
1245 @code{-openscop}: this option states that the input file complies to
1246 the OpenScop specification instead of the native file format
1247 (@pxref{Bas11}). This option is available only if the OpenScop
1248 support has been enabled at compile time (@pxref{Optional Features}).
1249 The following OpenScop extensions are supported by CLooG
1250 (for the details about those extensions, @pxref{Bas11}):
1252 @item @emph{scatnames} to set the scattering dimension names.
1253 @item @emph{coordinates} to inject the generated code at the
1254 place of a given SCoP in a given file. The use of
1255 this extension is disabled when the options
1256 @emph{-compilable} or @emph{-callable} are set.
1260 @subsection Help @code{--help} or @code{-h}
1262 @code{--help} or @code{-h}: this option ask CLooG to print a short help.
1265 @subsection Version @code{--version} or @code{-v}
1267 @code{--version} or @code{-v}: this option ask CLooG to print some version
1271 @subsection Quiet @code{--quiet} or @code{-q}
1273 @code{--quiet} or @code{-q}: this option tells CLooG not to print
1274 any informational messages.
1277 @c %/*************************************************************************
1278 @c % * A Full Example *
1279 @c % *************************************************************************/
1281 @section A Full Example
1283 Let us consider the allocation problem of a Gaussian elimination, i.e. we want
1284 to distribute the various statement instances of the compute kernel onto
1285 different processors. The original code is the following:
1288 for (i=1;j<=N-1;i++) @{
1289 for (j=i+1;j<=N;j++) @{
1290 c[i][j] = a[j][i]/a[i][i] ; /* S1 */
1291 for (k=i+1;k<=N;k++) @{
1292 a[j][k] -= c[i][j]*a[i][k] ; /* S2 */
1299 @noindent The best affine allocation functions can be found by any good automatic
1300 parallelizer like LooPo (@pxref{Gri04}):
1304 \hbox{$ \cases{ \theta _{S1}(i,j)^T &$= (i)$\cr
1305 \theta _{S2}(i,j,k)^T &$= (k)$}$}
1318 @noindent To ensure that on each processor, the set of statement instances is
1319 executed according to the original ordering, we add as minor scattering
1320 dimensions the original scheduling (@pxref{Scattering}):
1324 \hbox{$ \cases{ \theta _{S1}(i,j)^T &$= (i,0,i,0,j,0)^T$\cr
1325 \theta _{S2}(i,j,k)^T &$= (k,0,i,0,j,1,k,0)^T$}$}
1332 T_S1(i,j)^T = (i,0,i,0,j,0)^T
1333 T_S2(i,j,k)^T = (k,0,i,0,j,1,k,0)^T
1338 @noindent To ensure that the scattering functions have the same dimensionality, we
1339 complete the first function with zeroes
1340 (this is a CLooG @value{VERSION} and previous versions requirement,
1341 it should be removed in a future version, don't worry it's absolutely legal !):
1345 \hbox{$ \cases{ \theta _{S1}(i,j)^T &$= (i,0,i,0,j,0,0,0)^T$\cr
1346 \theta _{S2}(i,j,k)^T &$= (k,0,i,0,j,1,k,0)^T$}$}
1353 T_S1(i,j)^T = (i,0,i,0,j,0,0,0)^T
1354 T_S2(i,j,k)^T = (k,0,i,0,j,1,k,0)^T
1359 @noindent The input file corresponding to this code generation problem
1360 could be (this file is provided in the CLooG distribution
1361 as @code{test/manual_gauss.cloog}:
1364 # ---------------------- CONTEXT ----------------------
1367 # Context (no constraints on one parameter)
1368 1 3 # 1 line and 3 columns
1370 1 0 0 # 0 >= 0, always true
1372 1 # We want to set manually the parameter name
1375 # --------------------- STATEMENTS --------------------
1376 2 # Number of statements
1378 1 # First statement: one domain
1379 4 5 # 4 lines and 3 columns
1382 1 -1 0 1 -1 # i <= n-1
1383 1 -1 1 0 -1 # j >= i+1
1385 0 0 0 # for future options
1388 # Second statement: one domain
1389 6 6 # 6 lines and 3 columns
1391 1 1 0 0 0 -1 # i >= 1
1392 1 -1 0 0 1 -1 # i <= n-1
1393 1 -1 1 0 0 -1 # j >= i+1
1394 1 0 -1 0 1 0 # j <= n
1395 1 -1 0 1 0 -1 # k >= i+1
1396 1 0 0 -1 1 0 # k <= n
1397 0 0 0 # for future options
1399 0 # We let CLooG set the iterator names
1401 # --------------------- SCATTERING --------------------
1402 2 # Scattering functions
1404 8 13 # 3 lines and 3 columns
1405 # eq/in p1 p2 p3 p4 p5 p6 p7 p8 i j n 1
1406 0 1 0 0 0 0 0 0 0 -1 0 0 0 # p1 = i
1407 0 0 1 0 0 0 0 0 0 0 0 0 0 # p2 = 0
1408 0 0 0 1 0 0 0 0 0 -1 0 0 0 # p3 = i
1409 0 0 0 0 1 0 0 0 0 0 0 0 0 # p4 = 0
1410 0 0 0 0 0 1 0 0 0 0 -1 0 0 # p5 = j
1411 0 0 0 0 0 0 1 0 0 0 0 0 0 # p6 = 0
1412 0 0 0 0 0 0 0 1 0 0 0 0 0 # p7 = 0
1413 0 0 0 0 0 0 0 0 1 0 0 0 0 # p8 = 0
1415 8 14 # 3 lines and 3 columns
1416 # eq/in p1 p2 p3 p4 p5 p6 p7 p8 i j k n 1
1417 0 1 0 0 0 0 0 0 0 0 0 -1 0 0 # p1 = k
1418 0 0 1 0 0 0 0 0 0 0 0 0 0 0 # p2 = 0
1419 0 0 0 1 0 0 0 0 0 -1 0 0 0 0 # p3 = i
1420 0 0 0 0 1 0 0 0 0 0 0 0 0 0 # p4 = 0
1421 0 0 0 0 0 1 0 0 0 0 -1 0 0 0 # p5 = j
1422 0 0 0 0 0 0 1 0 0 0 0 0 0 -1 # p6 = 1
1423 0 0 0 0 0 0 0 1 0 0 0 -1 0 0 # p7 = k
1424 0 0 0 0 0 0 0 0 1 0 0 0 0 0 # p8 = 0
1426 1 # We want to set manually the scattering dimension names
1427 p1 p2 p3 p4 p5 p6 p7 p8 # scattering dimension names
1430 Calling CLooG, with for instance the command line
1431 @code{cloog -fsp 2 gauss.cloog} for a better view
1432 of the allocation (the processor number is given by @code{p1}),
1433 will result on the following target code that actually implements
1434 the transformation. A minor processing on the dimension @code{p1}
1435 to implement, e.g., MPI calls, which is not shown here may
1436 result in dramatic speedups !
1441 for (p5=2;p5<=n;p5++) @{
1445 for (p1=2;p1<=n-1;p1++) @{
1446 for (p3=1;p3<=p1-1;p3++) @{
1447 for (p5=p3+1;p5<=n;p5++) @{
1448 S2(i = p3,j = p5,k = p1) ;
1451 for (p5=p1+1;p5<=n;p5++) @{
1457 for (p3=1;p3<=n-1;p3++) @{
1458 for (p5=p3+1;p5<=n;p5++) @{
1459 S2(i = p3,j = p5,k = n) ;
1466 @c %/*************************************************************************
1467 @c % * A Full Example *
1468 @c % *************************************************************************/
1470 @chapter Using the CLooG Library
1471 The CLooG Library was implemented to allow the user to call CLooG
1472 directly from his programs, without file accesses or system calls. The
1473 user only needs to link his programs with C libraries. The CLooG
1474 library mainly provides one function (@code{cloog_clast_create_from_input})
1475 which takes as input the problem
1476 description with some options, and returns the data structure corresponding
1477 to the generated code (a @code{struct clast_stmt} structure)
1478 which is more or less an abstract syntax tree.
1479 The user can work with this data structure and/or use
1480 our pretty printing function to write the final code in either C or FORTRAN.
1481 Some other functions are provided for convenience reasons.
1482 These functions as well as the data structures are described in this section.
1485 * CLooG Data Structures::
1487 * Retrieving version information::
1488 * Example of Library Utilization::
1492 @node CLooG Data Structures
1493 @section CLooG Data Structures Description
1494 In this section, we describe the data structures used by the loop
1495 generator to represent and to process a code generation problem.
1502 * CloogUnionDomain::
1510 @subsection CloogState
1513 CloogState *cloog_state_malloc(void);
1514 void cloog_state_free(CloogState *state);
1518 @noindent The @code{CloogState} structure is (implicitly) needed to perform
1519 any CLooG operation. It should be created using @code{cloog_state_malloc}
1520 before any other CLooG objects are created and destroyed using
1521 @code{cloog_state_free} after all objects have been freed.
1522 It is allowed to use more than one @code{CloogState} structure at
1523 the same time, but an object created within the state of a one
1524 @code{CloogState} structure is not allowed to interact with an object
1525 created within the state of an other @code{CloogState} structure.
1531 @node CloogState/isl
1535 #include <cloog/isl/cloog.h>
1536 CloogState *cloog_isl_state_malloc(isl_ctx *ctx);
1540 When using the isl backend, CLooG will internally create many isl objects.
1541 If the user creates any CLooG objects from isl objects (e.g.,
1542 through @code{cloog_domain_from_isl_set} below), then the user needs
1543 to make sure that these isl objects live in the same @code{isl_ctx}
1544 as those created by CLooG internally. The best way to ensure this
1545 property is to pass the @code{isl_ctx} created by the user to CLooG
1546 by calling @code{cloog_isl_state_malloc} to create a @code{CloogState}.
1547 Note that this makes the created @code{CloogState} a user of the
1548 given @code{isl_ctx}, meaning that the @code{CloogState} needs to
1549 be freed before the @code{isl_ctx} is freed.
1553 @subsection CloogMatrix
1555 @noindent The @code{CloogMatrix} structure is equivalent to the PolyLib
1556 @code{Matrix} data structure (@pxref{Wil93}). This structure is devoted to
1557 represent a set of constraints.
1562 @{ unsigned NbRows ; /* Number of rows. */
1563 unsigned NbColumns ; /* Number of columns. */
1564 cloog_int_t **p; /* Array of pointers to the matrix rows. */
1565 cloog_int_t *p_Init; /* Matrix rows contiguously in memory. */
1567 typedef struct cloogmatrix CloogMatrix;
1569 CloogMatrix *cloog_matrix_alloc(unsigned NbRows, unsigned NbColumns);
1570 void cloog_matrix_print(FILE *foo, CloogMatrix *m);
1571 void cloog_matrix_free(CloogMatrix *matrix);
1575 @noindent The whole matrix is stored in memory row after row at the
1576 @code{p_Init} address. @code{p} is an array of pointers where
1577 @code{p[i]} points to the first element of the @math{i^{th}} row.
1578 @code{NbRows} and @code{NbColumns} are respectively the number of
1579 rows and columns of the matrix.
1580 Each row corresponds to a constraint. The first element of each row is an
1581 equality/inequality tag. The
1582 constraint is an equality @math{p(x) = 0} if the first element is 0, but it is
1583 an inequality @math{p(x) \geq 0} if the first element is 1.
1584 The next elements are the coefficients of the unknowns,
1585 followed by the coefficients of the parameters, and finally the constant term.
1586 For instance, the following three constraints:
1590 \hbox{$ \cases{ -i + m &$= 0$\cr
1592 j + i - k &$\geq 0$}$}
1606 @noindent would be represented by the following rows:
1610 # eq/in i j k m n cst
1617 @noindent To be able to provide different precision version (CLooG
1618 supports 32 bits, 64 bits and arbitrary precision through the GMP library),
1619 the @code{cloog_int_t} type depends on the configuration options (it may be
1620 @code{long int} for 32 bits version, @code{long long int} for 64 bits version,
1621 and @code{mpz_t} for multiple precision version).
1624 @subsection CloogDomain
1627 CloogDomain *cloog_domain_union_read(CloogState *state,
1628 FILE *input, int nb_parameters);
1629 CloogDomain *cloog_domain_from_cloog_matrix(CloogState *state,
1630 CloogMatrix *matrix, int nb_par);
1631 void cloog_domain_free(CloogDomain *domain);
1635 @noindent @code{CloogDomain} is an opaque type representing a polyhedral
1636 domain (a union of polyhedra).
1637 A @code{CloogDomain} can be read
1638 from a file using @code{cloog_domain_union_read} or
1639 converted from a @code{CloogMatrix}.
1640 The input format for @code{cloog_domain_union_read}
1641 is that of @ref{Domain Representation}.
1642 The function @code{cloog_domain_from_cloog_matrix} takes a @code{CloogState}, a
1643 @code{CloogMatrix} and @code{int} as input and returns a pointer to a
1644 @code{CloogDomain}. @code{matrix} describes the domain and @code{nb_par} is the
1645 number of parameters in this domain. The input data structures are neither
1647 The @code{CloogDomain} can be freed using @code{cloog_domain_free}.
1648 There are also some backend dependent functions for creating
1649 @code{CloogDomain}s.
1652 * CloogDomain/PolyLib::
1656 @node CloogDomain/PolyLib
1657 @subsubsection PolyLib
1660 #include <cloog/polylib/cloog.h>
1661 CloogDomain *cloog_domain_from_polylib_polyhedron(CloogState *state,
1662 Polyhedron *, int nb_par);
1665 The function @code{cloog_domain_from_polylib_polyhedron} takes a PolyLib
1666 @code{Polyhedron} as input and returns a pointer to a @code{CloogDomain}.
1667 The @code{nb_par} parameter indicates the number of parameters
1668 in the domain. The input data structure if neither modified nor freed.
1670 @node CloogDomain/isl
1674 #include <cloog/isl/cloog.h>
1675 CloogDomain *cloog_domain_from_isl_set(__isl_take isl_set *set);
1676 __isl_give isl_set *isl_set_from_cloog_domain(CloogDomain *domain);
1679 The function @code{cloog_domain_from_isl_set} takes an
1680 @code{isl_set} as input and returns a pointer to a @code{CloogDomain}.
1681 The function consumes a reference to the given @code{isl_set}.
1682 Similarly, @code{isl_set_from_cloog_domain} consumes a reference
1683 to a @code{CloogDomain} and returns an @code{isl_set}.
1686 @node CloogScattering
1687 @subsection CloogScattering
1690 CloogScattering *cloog_domain_read_scattering(CloogDomain *domain,
1692 CloogScattering *cloog_scattering_from_cloog_matrix(CloogState *state,
1693 CloogMatrix *matrix, int nb_scat, int nb_par);
1694 void cloog_scattering_free(CloogScattering *);
1699 The @code{CloogScattering} type represents a scattering function.
1700 A @code{CloogScattering} for a given @code{CloogDomain} can be read
1701 from a file using @code{cloog_scattering_read} or converted
1702 from a @code{CloogMatrix} using @code{cloog_scattering_from_cloog_matrix}.
1703 The function @code{cloog_scattering_from_cloog_matrix} takes a
1704 @code{CloogState}, a @code{CloogMatrix} and two @code{int}s as input and
1706 pointer to a @code{CloogScattering}.
1707 @code{matrix} describes the scattering, while @code{nb_scat} and
1708 @code{nb_par} are the number of scattering dimensions and
1709 the number of parameters, respectively. The input data structures are
1710 neither modified nor freed.
1711 A @code{CloogScattering} can be freed using @code{cloog_scattering_free}.
1712 There are also some backend dependent functions for creating
1713 @code{CloogScattering}s.
1716 * CloogScattering/PolyLib::
1717 * CloogScattering/isl::
1720 @node CloogScattering/PolyLib
1721 @subsubsection PolyLib
1724 #include <cloog/polylib/cloog.h>
1725 CloogScattering *cloog_scattering_from_polylib_polyhedron(
1726 CloogState *state, Polyhedron *polyhedron, int nb_par);
1729 The function @code{cloog_scattering_from_polylib_polyhedron} takes a PolyLib
1730 @code{Polyhedron} as input and returns a pointer to a @code{CloogScattering}.
1731 The @code{nb_par} parameter indicates the number of parameters
1732 in the domain. The input data structure if neither modified nor freed.
1734 @node CloogScattering/isl
1738 #include <cloog/isl/cloog.h>
1739 CloogScattering *cloog_scattering_from_isl_map(__isl_take isl_map *map);
1742 The function @code{cloog_scattering_from_isl_map} takes an
1743 @code{isl_map} as input and returns a pointer to a @code{CloogScattering}.
1744 The output dimensions of the @code{isl_map} correspond to the
1745 scattering dimensions, while the input dimensions correspond to the
1747 The function consumes a reference to the given @code{isl_map}.
1750 @node CloogUnionDomain
1751 @subsection CloogUnionDomain
1754 enum cloog_dim_type @{ CLOOG_PARAM, CLOOG_ITER, CLOOG_SCAT @};
1756 CloogUnionDomain *cloog_union_domain_alloc(int nb_par);
1757 CloogUnionDomain *cloog_union_domain_add_domain(CloogUnionDomain *ud,
1758 const char *name, CloogDomain *domain,
1759 CloogScattering *scattering, void *usr);
1760 CloogUnionDomain *cloog_union_domain_set_name(CloogUnionDomain *ud,
1761 enum cloog_dim_type type, int index, const char *name);
1762 void cloog_union_domain_free(CloogUnionDomain *ud);
1766 @noindent A @code{CloogUnionDomain} structure represents a union
1767 of scattered named domains. A @code{CloogUnionDomain} is
1768 initialized by a call to @code{cloog_union_domain_alloc},
1769 after which domains can be added using @code{cloog_union_domain_add_domain}.
1771 @code{cloog_union_domain_alloc} takes the number of parameters as input.
1772 @code{cloog_union_domain_add_domain} takes a previously created
1773 @code{CloogUnionDomain} as input along with an optional name,
1774 a domain, an optional scattering function and a user pointer.
1775 The name may be @code{NULL} and is duplicated if it is not.
1776 If no name is specified, then the statements will be named according
1777 to the order in which they were added.
1778 @code{domain} and @code{scattering} are taken over
1779 by the @code{CloogUnionDomain}. @code{scattering} may be @code{NULL},
1780 but it must be consistently @code{NULL} or not over all calls
1781 to @code{cloog_union_domain_add_domain}.
1782 @code{cloog_union_domain_set_name} can be used to set the names
1783 of parameters, iterators and scattering dimensions.
1784 The names of iterators and scattering dimensions can only be set
1785 after all domains have been added.
1787 There is also a backend dependent function for creating
1788 @code{CloogUnionDomain}s.
1791 * CloogUnionDomain/isl::
1794 @node CloogUnionDomain/isl
1798 #include <cloog/isl/cloog.h>
1799 CloogUnionDomain *cloog_union_domain_from_isl_union_map(
1800 __isl_take isl_union_map *umap);
1801 CloogUnionDomain *cloog_union_domain_from_isl_set(
1802 __isl_take isl_set *set);
1805 The function @code{cloog_union_domain_from_isl_union_map} takes a
1806 @code{isl_union_map} as input and returns a pointer
1807 to a @code{CloogUnionDomain}.
1808 The input is a mapping from different
1809 spaces (different tuple names and possibly different dimensions)
1810 to a common space. The iteration domains are set to the domains
1811 in each space. The statement names are set to the names of the
1812 spaces. The parameter names of the result are set to those of
1813 the input, but the iterator and scattering dimension names are
1815 The function consumes a reference to the given @code{isl_union_map}. The
1816 function @code{cloog_union_domain_from_isl_set} is similar, but takes an
1817 unscattered domain as input. It is not defined for an union_set, because the
1818 order of iterations from two different isl_sets is undefined, if no scattering
1822 @node CloogStatement
1823 @subsection CloogStatement
1826 struct cloogstatement
1827 @{ int number ; /* The statement unique number. */
1828 char *name; /* Name of the statement. */
1829 void * usr ; /* Pointer for user's convenience. */
1830 struct cloogstatement * next ;/* Next element of the linked list. */
1832 typedef struct cloogstatement CloogStatement ;
1834 CloogStatement *cloog_statement_malloc(CloogState *state);
1835 void cloog_statement_print(FILE *, CloogStatement *);
1836 void cloog_statement_free(CloogStatement *);
1840 @noindent The @code{CloogStatement} structure represents a @code{NULL}
1842 list of statements. In CLooG, a statement is only defined by its unique
1843 number (@code{number}). The user can use the pointer @code{usr} for his
1844 own convenience to link his own statement representation to the
1845 corresponding @code{CloogStatement} structure. The whole management of the
1846 @code{usr} pointer is under the responsibility of the user, in particular,
1847 CLooG never tries to print, to allocate or to free a memory block pointed
1853 @subsection CloogOptions
1857 @{ int l; /* -l option. */
1858 int f; /* -f option. */
1859 int strides; /* -strides option. */
1860 int sh; /* -sh option. */
1861 int first_unroll; /* -first-unroll option. */
1862 int esp; /* -esp option. */
1863 int fsp; /* -fsp option. */
1864 int otl; /* -otl option. */
1865 int block; /* -block option. */
1866 int compilable; /* -compilable option. */
1867 int language; /* CLOOG_LANGUAGE_C or CLOOG_LANGUAGE_FORTRAN */
1868 int save_domains; /* Save unsimplified copy of domain. */
1870 typedef struct cloogoptions CloogOptions ;
1872 CloogOptions *cloog_options_malloc(CloogState *state);
1873 void cloog_options_print(FILE *foo, CloogOptions *options);
1874 void cloog_options_free(CloogOptions *options);
1878 @noindent The @code{CloogOptions} structure contains all the possible options to
1879 rule CLooG's behaviour (@pxref{Calling CLooG}).
1880 As a reminder, the default values are:
1882 @item @math{l = -1} (optimize control until the innermost loops),
1883 @item @math{f = 1} (optimize control from the outermost loops),
1884 @item @math{strides = 0} (use only unit strides),
1885 @item @math{sh = 0} (do not compute simple convex hulls),
1886 @item @math{first\_unroll = -1} (do not perform unrolling),
1887 @item @math{esp = 1} (spread complex equalities),
1888 @item @math{fsp = 1} (start to spread from the first iterators),
1889 @item @math{otl = 1} (simplify loops running only once).
1890 @item @math{block = 0} (do not make statement blocks when not necessary).
1891 @item @math{compilable = 0} (do not generate a compilable code).
1894 The @code{save_domains} option is only useful for users of the CLooG
1895 library. This option defaults to 0, but when it is set, the @code{domain}
1896 field of each @code{clast_user_stmt} will be set to the set of values for the
1897 scattering dimensions for which this instance of the user statement is executed.
1898 The @code{domain} field of each @code{clast_for} contains the set of values for
1899 the scattering dimensions for which an instance of a user statement is executed
1900 inside the @code{clast_for}. It is only available if the @code{clast_for}
1901 enumerates a scattering dimension.
1904 @subsection CloogInput
1907 CloogInput *cloog_input_read(FILE *file, CloogOptions *options);
1908 CloogInput *cloog_input_alloc(CloogDomain *context,
1909 CloogUnionDomain *ud);
1910 void cloog_input_free(CloogInput *input);
1912 void cloog_input_dump_cloog(FILE *, CloogInput *, CloogOptions *);
1916 @noindent A @code{CloogInput} structure represents the input to CLooG.
1917 It is essentially a @code{CloogUnionDomain} along with a context
1918 @code{CloogDomain}. A @code{CloogInput} can be created from
1919 a @code{CloogDomain} and a @code{CloogUnionDomains} using
1920 @code{cloog_input_alloc}, or it can be read from a CLooG input
1921 file using @code{cloog_input_read}. The latter also modifies
1922 the @code{language} field of the @code{CloogOptions} structure.
1923 The constructed @code{CloogInput} can be used as input
1924 to a @code{cloog_clast_create_from_input} call.
1926 A @code{CloogInput} data structure and a @code{CloogOptions} contain
1927 the same information as a .cloog file. This function dumps the .cloog
1928 description of the given data structures into a file.
1930 @node Dump CLooG Input File Function
1931 @subsection Dump CLooG Input File Function
1936 @section CLooG Output
1939 Given a description of the input,
1940 an AST corresponding to the @code{CloogInput} can be constructed
1941 using @code{cloog_clast_create_from_input} and destroyed using
1942 @code{free_clast_stmt}.
1944 struct clast_stmt *cloog_clast_create_from_input(CloogInput *input,
1945 CloogOptions *options);
1946 void free_clast_stmt(struct clast_stmt *s);
1949 @code{clast_stmt} represents a linked list of ``statements''.
1951 struct clast_stmt @{
1952 const struct clast_stmt_op *op;
1953 struct clast_stmt *next;
1957 The entries in the list are not of type @code{clast_stmt} itself,
1958 but of some larger type. The following statement types are defined
1962 struct clast_root @{
1963 struct clast_stmt stmt;
1966 struct clast_root *new_clast_root(CloogNames *names);
1968 struct clast_assignment @{
1969 struct clast_stmt stmt;
1971 struct clast_expr * RHS;
1973 struct clast_assignment *new_clast_assignment(const char *lhs,
1974 struct clast_expr *rhs);
1976 struct clast_block @{
1977 struct clast_stmt stmt;
1978 struct clast_stmt * body;
1980 struct clast_block *new_clast_block(void);
1982 struct clast_user_stmt @{
1983 struct clast_stmt stmt;
1984 CloogDomain * domain;
1985 CloogStatement * statement;
1986 struct clast_stmt * substitutions;
1988 struct clast_user_stmt *new_clast_user_stmt(CloogDomain *domain,
1989 CloogStatement *stmt, struct clast_stmt *subs);
1992 struct clast_stmt stmt;
1993 CloogDomain * domain;
1994 const char * iterator;
1995 struct clast_expr * LB;
1996 struct clast_expr * UB;
1998 struct clast_stmt * body;
2000 struct clast_for *new_clast_for(CloogDomain *domain, const char *it,
2001 struct clast_expr *LB, struct clast_expr *UB,
2002 cloog_int_t stride);
2004 struct clast_guard @{
2005 struct clast_stmt stmt;
2006 struct clast_stmt * then;
2008 struct clast_equation eq[1];
2010 struct clast_guard *new_clast_guard(int n);
2013 The @code{clast_stmt} returned by @code{cloog_clast_create}
2014 is a @code{clast_root}.
2015 It contains a placeholder for all the variable names that appear
2016 in the AST and a (list of) nested statement(s).
2019 A @code{clast_assignment} assigns the value given by
2020 the @code{clast_expr} @code{RHS} to a variable named @code{LHS}.
2023 A @code{clast_block} groups a list of statements into one statement.
2024 These statements are only generated if the @code{block} option is set,
2025 @pxref{Statement Block} and @ref{CloogOptions}.
2028 A @code{clast_user_stmt} represents a call to a statement specified
2029 by the user, @pxref{CloogStatement}.
2030 @code{substitutions} is a list of @code{clast_assignment} statements
2031 assigning an expression in terms of the scattering dimensions to
2032 each of the original iterators in the original order.
2033 The @code{LHS}s of these assignments are left blank (@code{NULL}).
2034 The @code{domain} is set to @code{NULL} if the @code{save_domains} option
2035 is not set. Otherwise, it is set to the set
2036 of values for the scattering dimensions
2037 for which this instance of the user statement is executed.
2038 Note that unless the @code{noscalars} option has been set, the
2039 constant scattering dimensions may have been removed from this set.
2042 A @code{clast_for} represents a for loop, iterating @code{body} for each
2043 value of @code{iterator} between @code{LB} and @code{UB} in steps
2044 of size @code{stride}.
2045 The @code{domain} is set to @code{NULL} if the @code{save_domains} option is not
2046 set. Otherwise, it is set to the set of values for the scattering dimensions
2047 for which a user statement is executed inside this @code{clast_for}. Note that
2048 unless the @code{noscalars} option has been set, the constant scattering
2049 dimensions may have been removed from this set.
2052 A @code{clast_guard} represents the guarded execution of the @code{then}
2053 (list of) statement(s) by a conjunction of @code{n} (in)equalities.
2054 Each (in)equality is represented by a @code{clast_equation}.
2056 struct clast_equation @{
2057 struct clast_expr * LHS;
2058 struct clast_expr * RHS;
2063 The condition expressed by a @code{clast_equation} is
2064 @code{LHS <= RHS}, @code{LHS == RHS} or @code{LHS >= RHS}
2065 depending on whether @code{sign} is less than zero, equal
2066 to zero, or greater than zero.
2068 The dynamic type of a @code{clast_stmt} can be determined
2069 using the macro @code{CLAST_STMT_IS_A(stmt,type)},
2070 where @code{stmt} is a pointer to a @code{clast_stmt}
2071 and @code{type} is one of @code{stmt_root}, @code{stmt_ass},
2072 @code{stmt_user}, @code{stmt_block}, @code{stmt_for} or
2074 Users are allowed to define their own statement types by
2075 assigning the @code{op} field of the statements a pointer
2076 to a @code{clast_stmt_op} structure.
2078 struct clast_stmt_op @{
2079 void (*free)(struct clast_stmt *);
2083 The @code{free} field of this structure should point
2084 to a function that frees the user defined statement.
2087 A @code{clast_expr} can be an identifier, a term,
2088 a binary expression or a reduction.
2090 enum clast_expr_type @{
2096 struct clast_expr @{
2097 enum clast_expr_type type;
2099 void free_clast_expr(struct clast_expr *e);
2103 Identifiers are of subtype @code{clast_name}.
2105 struct clast_name @{
2106 struct clast_expr expr;
2109 struct clast_name *new_clast_name(const char *name);
2110 void free_clast_name(struct clast_name *t);
2113 The character string pointed to by @code{name} is
2114 assumed to be part of the @code{CloogNames} structure
2115 in the root of the clast as is therefore not copied.
2118 Terms are of type @code{clast_term}.
2120 struct clast_term @{
2121 struct clast_expr expr;
2123 struct clast_expr *var;
2125 struct clast_term *new_clast_term(cloog_int_t c, struct clast_expr *v);
2126 void free_clast_term(struct clast_term *t);
2129 If @code{var} is set to @code{NULL}, then the term represents
2130 the integer value @code{val}. Otherwise, it represents
2131 the term @code{val * var}.
2132 @code{new_clast_term} simply copies the @code{v} pointer
2133 without copying the underlying @code{clast_expr}.
2134 @code{free_clast_term}, on the other hand, recursively frees
2138 Binary expressions are of type @code{clast_bin_type} and
2139 represent either the floor of a division (fdiv),
2140 the ceil of a division (cdiv), an exact division or
2141 the remainder of an fdiv.
2143 enum clast_bin_type @{ clast_bin_fdiv, clast_bin_cdiv,
2144 clast_bin_div, clast_bin_mod @};
2145 struct clast_binary @{
2146 struct clast_expr expr;
2147 enum clast_bin_type type;
2148 struct clast_expr* LHS;
2151 struct clast_binary *new_clast_binary(enum clast_bin_type t,
2152 struct clast_expr *lhs, cloog_int_t rhs);
2153 void free_clast_binary(struct clast_binary *b);
2157 Reductions are of type @code{clast_reduction} and
2158 can represent either the sum, the minimum or the maximum
2161 enum clast_red_type @{ clast_red_sum, clast_red_min, clast_red_max @};
2162 struct clast_reduction @{
2163 struct clast_expr expr;
2164 enum clast_red_type type;
2166 struct clast_expr* elts[1];
2168 struct clast_reduction *new_clast_reduction(enum clast_red_type t,
2170 void free_clast_reduction(struct clast_reduction *r);
2173 @node Retrieving version information
2174 @section Retrieving version information
2175 CLooG provides static and dynamic version checks to assist on
2176 including a compatible version of the library.
2177 A static version check at compile time can be achieved by
2178 querying the version constants defined in @code{version.h}:
2181 @item @code{CLOOG_VERSION_MAJOR}
2182 @item @code{CLOOG_VERSION_MINOR}
2183 @item @code{CLOOG_VERSION_REVISION}
2186 This way it is possible to ensure the included headers are of the
2187 correct version. It is still possible that the installed CLooG
2188 library version differs from the installed headers.
2189 In order to avoid this, a dynamic version check is provided with
2194 int cloog_version_major(void);
2195 int cloog_version_minor(void);
2196 int cloog_version_revision(void);
2200 By using both the static and the dynamic version check, it is possible
2201 to match CLooG's header version with the library's version.
2203 @node Example of Library Utilization
2204 @section Example of Library Utilization
2206 * Basic Library Utilization::
2207 * Scanning isl Sets::
2210 @node Basic Library Utilization
2211 @subsection Basic Library Utilization
2212 Here is a basic example showing how it is possible to use the CLooG library,
2213 assuming that a standard installation has been done.
2214 The following C program reads a CLooG input file on the standard input,
2215 then prints the solution on the standard output.
2216 Options are preselected to the default values of the CLooG software.
2217 This example is provided in the @code{example} directory of the
2222 # include <cloog/cloog.h>
2227 CloogOptions *options ;
2228 struct clast_stmt *root;
2230 /* Setting options and reading program informations. */
2231 state = cloog_state_malloc();
2232 options = cloog_options_malloc(state);
2233 input = cloog_input_read(stdin, options);
2235 /* Generating and printing the code. */
2236 root = cloog_clast_create_from_input(input, options);
2237 clast_pprint(stdout, root, 0, options);
2239 cloog_clast_free(root);
2240 cloog_options_free(options) ;
2241 cloog_state_free(state);
2246 @noindent The compilation (with default isl/GMP version installed)
2249 gcc -DCLOOG_INT_GMP example.c -lcloog-isl -o example
2251 @noindent A calling command with the input file test.cloog could be:
2253 more test.cloog | ./example
2256 @node Scanning isl Sets
2257 @subsection Scanning isl Sets
2258 Here is an isl-level example to prepare a convenient input, to generate the
2259 Clast of the scanning code for this input, to pretty-print the code and to
2260 de-allocate memory in a clean way. This example is provided in the
2261 @code{example} directory of the CLooG distribution.
2265 #include <cloog/cloog.h>
2266 #include <cloog/isl/cloog.h>
2269 int nb_parameters = 1;
2270 char *parameter_name[] = @{"N"@};
2271 char *iterator_name[] = @{"i", "j"@};
2272 char *scattering_name[] = @{"t0", "t1", "t2"@};
2273 char *str_context = "[N] -> @{ : N > 0@}";
2274 char *str_domain1 = "[N] -> @{[i, j] : 0 <= i < N and 0 <= j < N@}";
2275 char *str_domain2 = "[N] -> @{[i, j] : 0 <= i < N and 0 <= j < N@}";
2276 char *str_scattering1 = "[N] -> @{[i, j] -> [0, i + j, j]@}";
2277 char *str_scattering2 = "[N] -> @{[i, j] -> [1, i, -j]@}";
2281 isl_set *set_context, *set1, *set2;
2282 isl_map *map1, *map2;
2283 CloogDomain *context, *domain1, *domain2;
2284 CloogScattering *scattering1, *scattering2;
2285 CloogUnionDomain *domains;
2288 CloogOptions *options;
2289 struct clast_stmt *root;
2291 /* Build isl structures for context, sets and mapping */
2292 ctx = isl_ctx_alloc();
2293 set_context = isl_set_read_from_str(ctx, str_context);
2294 set1 = isl_set_read_from_str(ctx, str_domain1);
2295 set2 = isl_set_read_from_str(ctx, str_domain2);
2296 map1 = isl_map_read_from_str(ctx, str_scattering1);
2297 map2 = isl_map_read_from_str(ctx, str_scattering2);
2299 /* Translate them to CLooG context, domains and scattering */
2300 context = cloog_domain_from_isl_set(set_context);
2301 domain1 = cloog_domain_from_isl_set(set1);
2302 domain2 = cloog_domain_from_isl_set(set2);
2303 scattering1 = cloog_scattering_from_isl_map(map1);
2304 scattering2 = cloog_scattering_from_isl_map(map2);
2306 /* Prepare the list of domains to scan */
2307 domains = cloog_union_domain_alloc(nb_parameters);
2308 cloog_union_domain_add_domain(domains,"S1",domain1,scattering1,NULL);
2309 cloog_union_domain_add_domain(domains,"S2",domain2,scattering2,NULL);
2310 cloog_union_domain_set_name(domains,CLOOG_PARAM,0,parameter_name[0]);
2311 cloog_union_domain_set_name(domains,CLOOG_ITER, 0,iterator_name[0]);
2312 cloog_union_domain_set_name(domains,CLOOG_ITER, 1,iterator_name[1]);
2313 cloog_union_domain_set_name(domains,CLOOG_SCAT, 0,scattering_name[0]);
2314 cloog_union_domain_set_name(domains,CLOOG_SCAT, 1,scattering_name[1]);
2315 cloog_union_domain_set_name(domains,CLOOG_SCAT, 2,scattering_name[2]);
2317 /* Build the input, generate a scanning code AST and print the code */
2318 input = cloog_input_alloc(context, domains);
2319 state = cloog_isl_state_malloc(ctx);
2320 options = cloog_options_malloc(state);
2321 root = cloog_clast_create_from_input(input, options);
2322 clast_pprint(stdout, root, 0, options);
2324 /* Recycle allocated memory */
2325 cloog_clast_free(root);
2326 cloog_options_free(options);
2327 cloog_state_free(state);
2332 @noindent The compilation (with default isl/GMP version installed)
2335 gcc -DCLOOG_INT_GMP example-isl.c -lcloog-isl -o example-isl
2337 @noindent A calling command could be:
2343 @c % ******************************** HACKING *********************************
2345 @c @chapter Hacking CLooG
2348 @c * Program organization::
2349 @c * Special Options::
2350 @c * CLooG Coding Standards::
2353 @c @node Program organization
2354 @c @section Program organization
2356 @c @node Special Options
2357 @c @section Special Options
2359 @c @node CLooG Coding Standards
2360 @c @section CLooG Coding Standards
2363 @c % ****************************** INSTALLING ********************************
2365 @chapter Installing CLooG
2370 * Basic Installation::
2371 * Optional Features::
2377 First of all, it would be very kind to refer the following paper in any
2378 publication that result from the use of the CLooG software or its library,
2379 @pxref{Bas04} (a bibtex entry is provided behind the title page of this
2380 manual, along with copyright notice, and in the CLooG home
2381 @code{http://www.CLooG.org}.
2383 This library is free software; you can redistribute it and/or
2384 modify it under the terms of the GNU Lesser General Public
2385 License as published by the Free Software Foundation; either
2386 version 2.1 of the License, or (at your option) any later version.
2387 This library is distributed in the hope that it will be useful,
2388 but WITHOUT ANY WARRANTY; without even the implied warranty of
2389 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
2390 Lesser General Public License for more details.
2391 @code{http://www.gnu.org/licenses/lgpl-2.1.html}
2393 Note, though, that if you link CLooG against a GPL library such
2394 as the PolyLib backend, then the combination becomes GPL too.
2395 In particular, a CLooG library based on the PolyLib backend
2396 is GPL version 2 only.
2397 Since the isl backend is LGPL, linking against it does not affect
2398 the license of CLooG.
2402 @section Requirements
2404 CLooG can be used with one of two possible backends,
2405 one using isl and one using PolyLib.
2406 The isl library is included in the CLooG distribution,
2407 while the PolyLib library needs to be obtained separately.
2408 On the other hand, isl requires GMP, while PolyLib can be
2409 compiled with or without the use of GMP.
2410 The user therefore needs to install at least one of
2420 @subsection PolyLib (optional)
2421 To successfully install CLooG with the PolyLib backend,
2422 the user first needs to install PolyLib
2423 version 5.22.1 or above (default 64 bits version is satisfying
2424 as well as 32 bits or GMP multiple precision version).
2425 Polylib can be downloaded freely
2426 at @code{http://icps.u-strasbg.fr/PolyLib/} or
2427 @code{http://www.irisa.fr/polylib/}. Once downloaded and unpacked
2428 (e.g. using the @samp{tar -zxvf polylib-5.22.3.tar.gz} command),
2429 the user can compile
2430 it by typing the following commands on the PolyLib's root directory:
2433 @item @code{./configure}
2435 @item And as root: @code{make install}
2438 Alternatively, the latest development version can be obtained from the
2441 @item @code{git clone git://repo.or.cz/polylib.git}
2442 @item @code{cd polylib}
2443 @item @code{./autogen.sh}
2444 @item @code{./configure}
2446 @item And as root: @code{make install}
2449 The PolyLib default installation is @code{/usr/local}. This directory may
2450 not be inside your library path. To fix the problem, the user should set
2452 export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib
2454 @noindent if your shell is, e.g., bash or
2456 setenv LD_LIBRARY_PATH $LD_LIBRARY_PATH:/usr/local/lib
2458 @noindent if your shell is, e.g., tcsh. Add the line to your .bashrc or .tcshrc (or
2459 whatever convenient file) to make this change permanent. Another solution
2460 is to ask PolyLib to install in the standard path by using the prefix
2461 option of the configure script:
2462 @samp{./configure --prefix=/usr}.
2464 CLooG makes intensive calls to polyhedral operations, and PolyLib
2465 functions do the job. Polylib is a free library written in C for the
2466 manipulation of polyhedra. The library is operating on objects like
2467 vectors, matrices, lattices, polyhedra, Z-polyhedra, unions of
2468 polyhedra and a lot of other intermediary structures. It provides
2469 functions for all the important operations on these structures.
2472 @subsection GMP Library (optional)
2474 To be able to deal with insanely large coefficient, the user will need to
2475 install the GNU Multiple Precision Library (GMP for short) version 4.1.4
2476 or above. It can be freely downloaded from @code{http://www.swox.com/gmp}.
2477 Note that the isl backend currently requires GMP.
2478 The user can compile GMP by typing the following commands on the GMP root
2482 @item @code{./configure}
2484 @item And as root: @code{make install}
2487 The GMP default installation is @code{/usr/local}, the same method to
2488 fix a library path problem applies as with PolyLib (@pxref{PolyLib}).
2490 If you want to use the PolyLib backend, then
2491 PolyLib has to be built using the GMP library by specifying the option
2492 @samp{--with-libgmp=PATH_TO_GMP} to the PolyLib configure script
2493 (where @code{PATH_TO_GMP} is @code{/usr/local} if you did not change the GMP
2494 installation directory). Then you have to set the convenient CLooG configure
2495 script options to build the GMP version (@pxref{Optional Features}).
2498 @node Basic Installation
2499 @section CLooG Basic Installation
2501 Once downloaded and unpacked
2502 (e.g. using the @samp{tar -zxvf cloog-@value{VERSION}.tar.gz} command),
2503 you can compile CLooG by typing the following commands on the CLooG's root
2507 @item @code{./configure}
2509 @item And as root: @code{make install}
2512 Alternatively, the latest development version can be obtained from the
2515 @item @code{git clone git://repo.or.cz/cloog.git}
2516 @item @code{cd cloog}
2517 @item @code{./get_submodules.sh}
2518 @item @code{./autogen.sh}
2519 @item @code{./configure}
2521 @item And as root: @code{make install}
2524 Depending on which backend you want to use and where they
2525 are located, you may need to pass some
2526 options to the configure script, @pxref{Optional Features}.
2528 The program binaries and object files can be removed from the
2529 source code directory by typing @code{make clean}. To also remove the
2530 files that the @code{configure} script created (so you can compile the
2531 package for a different kind of computer) type @code{make distclean}.
2533 Both the CLooG software and library have been successfully compiled
2534 on the following systems:
2536 @item PC's under Linux, with the @code{gcc} compiler,
2537 @item PC's under Windows (Cygwin), with the @code{gcc} compiler,
2538 @item Sparc and UltraSparc Stations, with the @code{gcc} compiler.
2541 @node Optional Features
2542 @section Optional Features
2543 The @code{configure} shell script attempts to guess correct values for
2544 various system-dependent variables and user options used during compilation.
2545 It uses those values to create the @code{Makefile}. Various user options
2546 are provided by the CLooG's configure script. They are summarized in the
2547 following list and may be printed by typing @code{./configure --help} in the
2548 CLooG top-level directory.
2551 @item By default, the installation directory is @code{/usr/local}:
2552 @code{make install} will install the package's files in
2553 @code{/usr/local/bin}, @code{/usr/local/lib} and @code{/usr/local/include}.
2554 The user can specify an installation prefix other than @code{/usr/local} by
2555 giving @code{configure} the option @code{--prefix=PATH}.
2557 @item By default, the isl backend will use the version of isl
2558 that is @code{bundled} together with CLooG.
2559 Using the @code{--with-isl} option of @code{configure}
2560 the user can specify that @code{no} isl,
2561 a previously installed (@code{system}) isl or a @code{build} isl
2563 In the latter case, the user should also specify the build location
2564 using @code{--with-isl-builddir=PATH}.
2565 In case of an installed isl,
2566 the installation location can be specified using the
2567 @code{--with-isl-prefix=PATH} and
2568 @code{--with-isl-exec-prefix=PATH} options of @code{configure}.
2570 @item By default, the PolyLib backend will use an installed
2571 (@code{system}) PolyLib, if any.
2572 The installation location can be specified using the
2573 @code{--with-polylib-prefix=PATH} and
2574 @code{--with-polylib-exec-prefix=PATH} options of @code{configure}.
2575 Using the @code{--with-polylib} option of @code{configure}
2576 the user can specify that @code{no} PolyLib or a @code{build} PolyLib
2578 In the latter case, the user should also specify the build location
2579 using @code{--with-polylib-builddir=PATH}.
2581 @item By default, the PolyLib backend of CLooG is built
2582 in 64bits version if such version of the
2583 PolyLib is found by @code{configure}. If the only existing version of the
2584 PolyLib is the 32bits or if the user give to @code{configure} the option
2585 @code{--with-bits=32}, the 32bits version of CLooG will be compiled. In the
2586 same way, the option @code{--with-bits=gmp} have to be used to build
2587 the multiple precision version.
2589 @item By default, @code{configure} will look for the GMP library
2590 (necessary to build the multiple precision version) in standard
2591 locations. If necessary, the user can specify the GMP path by giving
2592 @code{configure} the option @code{--with-gmp-prefix=PATH} and/or
2593 @code{--with-gmp-exec-prefix=PATH}.
2595 @item By default, the OpenScop Library (osl) support is not enabled.
2596 @c @code{configure} will use the bundled OpenScop Library (osl).
2597 Using the @code{--with-osl} option of @code{configure}
2598 the user can specify that @code{no} osl,
2599 a previously installed (@code{system}) osl, a @code{bundled} osl, or a
2600 @code{build} osl should be used.
2601 In the latter case, the user should also specify the build location
2602 using @code{--with-osl-builddir=PATH}.
2603 In case of an installed osl,
2604 the installation location can be specified using the
2605 @code{--with-osl-prefix=PATH} and
2606 @code{--with-osl-exec-prefix=PATH} options of @code{configure}.
2609 @node Uninstallation
2610 @section Uninstallation
2611 The user can easily remove the CLooG software and library from his system
2612 by typing (as root if necessary) from the CLooG top-level directory
2613 @code{make uninstall}.
2615 @c % **************************** DOCUMENTATION ******************************
2617 @chapter Documentation
2618 The CLooG distribution provides several documentation sources. First, the
2619 source code itself is as documented as possible. The code comments use a
2620 Doxygen-compatible presentation (something similar to what JavaDoc does for
2621 JAVA). The user may install Doxygen
2622 (see @code{http://www.stack.nl/~dimitri/doxygen}) to automatically
2623 generate a technical documentation by typing @code{make doc} or
2624 @code{doxygen ./autoconf/Doxyfile} at the CLooG top-level directory after
2625 running the configure script (@pxref{Installing}). Doxygen will generate
2626 documentation sources (in HTML, LaTeX and man) in the @code{doc/source}
2627 directory of the CLooG distribution.
2629 The Texinfo sources of the present document are also provided in the @code{doc}
2630 directory. You can build it in either DVI format (by typing
2631 @code{texi2dvi cloog.texi}) or PDF format
2632 (by typing @code{texi2pdf cloog.texi}) or HTML format
2633 (by typing @code{makeinfo --html cloog.texi}, using @code{--no-split}
2634 option to generate a single HTML file) or info format
2635 (by typing @code{makeinfo cloog.texi}).
2637 @c % ****************************** REFERENCES ********************************
2643 @anchor{Bas03a}[Bas03a] C. Bastoul, P. Feautrier. Improving data locality
2644 by chunking. CC'12 International Conference on Compiler Construction,
2645 LNCS 2622, pages 320-335, Warsaw, april 2003.
2648 @anchor{Bas03b}[Bas03b] C. Bastoul. Efficient code generation for automatic
2649 parallelization and optimization. ISPDC'03 IEEE International Symposium on
2650 Parallel and Distributed Computing, pages 23-30, Ljubljana, october 2003.
2653 @anchor{Bas04}[Bas04] C. Bastoul. Code Generation in the Polyhedral Model
2654 Is Easier Than You Think. PACT'13 IEEE International Conference on Parallel
2655 Architecture and Compilation Techniques, pages 7-16, Juan-les-Pins,
2659 @anchor{Bas11}[Bas11] C. Bastoul. A Specification and a Library for Data
2660 Exchange in Polyhedral Compilation Tools. Technical Report,
2661 Paris-Sud University, France, September 2011.
2664 @anchor{Fea92}[Fea92] P. Feautrier Some efficient solutions to the affine
2665 scheduling problem, part II: multidimensional time.
2666 International Journal of Parallel Programming, 21(6):389--420, December 1992.
2669 @anchor{Gri04}[Gri04] M. Griebl. Automatic parallelization of loop programs
2670 for distributed memory architectures. Habilitation Thesis. Facult@"at f@"ur
2671 Mathematik und Informatik, Universit@"at Passau, 2004.
2672 @emph{http://www.infosun.fmi.uni-passau.de/cl/loopo/}
2675 @anchor{Qui00}[Qui00] F. Quiller@'e, S. Rajopadhye, and D. Wilde.
2676 Generation of efficient nested loops from polyhedra.
2677 International Journal of Parallel Programming, 28(5):469-498,
2681 @anchor{Wil93}[Wil93] Doran K. Wilde.
2682 A library for doing polyhedral operations.
2683 Technical Report 785, IRISA, Rennes, France, 1993.
2690 @c % /*************************************************************************
2691 @c % * PART VI: END OF THE DOCUMENT *
2692 @c % *************************************************************************/
2693 @c @unnumbered Index