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 % *************************************************************************/
35 @setfilename cloog.info
36 @settitle CLooG - a loop generator for scanning polyhedra
38 @dircategory Software libraries
40 * cloog: (cloog). A loop generator for scanning polyhedra
44 @include gitversion.texi
45 @set UPDATED October 15th 2007
46 @setchapternewpage odd
50 @c % /*************************************************************************
51 @c % * PART II: SUMMARY DESCRIPTION AND COPYRIGHT *
52 @c % *************************************************************************/
55 This manual is for CLooG version @value{VERSION}, a software
56 which generates loops for scanning Z-polyhedra. That is, CLooG produces a
57 code visiting each integral point of a union of parametrized
58 polyhedra. CLooG is designed to avoid control overhead and to produce a very
61 It would be quite kind to refer the following paper in any publication that
62 results from the use of the CLooG software or its library:
65 @@InProceedings@{Bas04,
66 @ @ author =@ @ @ @ @{C. Bastoul@},
67 @ @ title =@ @ @ @ @ @{Code Generation in the Polyhedral Model
68 @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ Is Easier Than You Think@},
69 @ @ booktitle = @{PACT'13 IEEE International Conference on
70 @ @ @ @ @ @ @ @ @ @ @ @ @ @ @ Parallel Architecture and Compilation Techniques@},
71 @ @ year =@ @ @ @ @ @ 2004,
72 @ @ pages =@ @ @ @ @ @{7--16@},
73 @ @ month =@ @ @ @ @ @{september@},
74 @ @ address =@ @ @ @{Juan-les-Pins@}
78 Copyright @copyright{} 2002-2005 C@'edric Bastoul.
81 Permission is granted to copy, distribute and/or modify this document under
82 the terms of the GNU Free Documentation License, Version 1.2
83 published by the Free Software Foundation. To receive a copy of the
84 GNU Free Documentation License, write to the Free Software Foundation, Inc.,
85 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
89 @c % /*************************************************************************
90 @c % * PART III: TITLEPAGE, CONTENTS, COPYRIGHT *
91 @c % *************************************************************************/
94 @subtitle A Loop Generator For Scanning Polyhedra
95 @subtitle Edition @value{EDITION}, for CLooG @value{VERSION}
96 @subtitle @value{UPDATED}
97 @author C@'edric Bastoul
99 @c The following two commands start the copyright page.
101 @noindent (September 2001)
103 @item C@'edric Bastoul
104 SCHEDULES GENERATE !!! I just need to apply them now, where can I find
105 a good code generator ?!
108 Hmmm. I fear that if you want something powerful enough, you'll have to
112 @vskip 0pt plus 1filll
116 @c Output the table of contents at the beginning.
119 @c % /*************************************************************************
120 @c % * PART IV: TOP NODE AND MASTER MENU *
121 @c % *************************************************************************/
141 @c % /*************************************************************************
142 @c % * PART V: BODY OF THE DOCUMENT *
143 @c % *************************************************************************/
145 @c % ****************************** INTRODUCTION ******************************
147 @chapter Introduction
148 CLooG is a free software and library generating loops for scanning Z-polyhedra.
149 That is, it finds a code (e.g. in C, FORTRAN...) that reaches each integral
150 point of one or more parameterized polyhedra. CLooG has been originally
151 written to solve the code generation problem for optimizing compilers based on
152 the polytope model. Nevertheless it is used now in various area, e.g., to build
153 control automata for high-level synthesis or to find the best polynomial
154 approximation of a function. CLooG may help in any situation where scanning
155 polyhedra matters. It uses the best state-of-the-art code generation
156 algorithm known as the Quiller@'e et al. algorithm (@pxref{Qui00})
157 with our own improvements and extensions (@pxref{Bas04}).
158 The user has full control on generated code quality.
159 On one hand, generated code size has to be tuned for sake of
160 readability or instruction cache use. On the other hand, we must ensure that
161 a bad control management does not hamper performance of the generated code,
162 for instance by producing redundant guards or complex loop bounds.
163 CLooG is specially designed to avoid control overhead and to produce a very
166 CLooG stands for @emph{Chunky Loop Generator}: it is a part of the Chunky
167 project, a research tool for data locality improvement (@pxref{Bas03a}).
169 also to be the back-end of automatic parallelizers like LooPo (@pxref{Gri04}).
171 compilable code oriented and provides powerful program transformation
172 facilities. Mainly, it allows the user to specify very general schedules where,
173 e.g., unimodularity or invertibility of the transformation doesn't matter.
175 The current version is still under
176 evaluation, and there is no guarantee that the upward compatibility
177 will be respected (but the previous API has been stable for two years,
178 we hope this one will be as successful -and we believe it-).
179 A lot of reports are necessary to freeze the library
180 API and the input file shape. Most API changes from 0.12.x to 0.14.x
181 have been requested by the users themselves.
182 Thus you are very welcome and encouraged
183 to post reports on bugs, wishes, critics, comments, suggestions or
184 successful experiences in the forum of @code{http://www.CLooG.org}
185 or to send them to cedric.bastoul@@inria.fr directly.
193 @section Basically, what's the point ?
194 If you want to use CLooG, this is because you want to scan or to find
195 something inside the integral points of a set of polyhedra. There are many
196 reasons for that. Maybe you need the generated code itself because it
197 actually implements a very smart program transformation you found.
198 Maybe you want to use the generated code
199 because you know that the solution of your problem belongs to the integral
200 points of those damned polyhedra and you don't know which one. Maybe you just
201 want to know if a polyhedron has integral points depending on some parameters,
202 which is the lexicographic minimum, maximum, the third on the basis of the
203 left etc. Probably you have your own reasons to use CLooG.
205 Let us illustrate a basic use of CLooG. Suppose we have a set of affine
206 constraints that describes a part of a whatever-dimensional space,
207 called a @strong{domain}, and we
208 want to scan it. Let us consider for instance the following set of constraints
210 and @samp{j} are the unknown (the two dimensions of the space) and
211 @samp{m} and @samp{n} are the parameters (some symbolic constants):
219 Let us also consider that we have a partial knowledge of the parameter values,
220 called the @strong{context}, expressed as affine constraints as well,
228 Note that using parameters is optional, if you are not comfortable with
229 parameter manipulation, just replace them with any scalar value that fits
230 @code{m>=2} and @code{n>=2}.
231 A graphical representation of this part of the 2-dimensional space, where
232 the integral points are represented using heavy dots would be for instance:
234 @image{images/basic,6cm}
236 The affine constraints of both the domain and the context are what we will
237 provide to CLooG as input (in a particular shape that will be described later).
238 The output of CLooG is a pseudo-code to scan the integral points of the
239 input domain according to the context:
242 for (i=2;i<=n;i++) @{
243 for (j=2;j<=min(m,-i+n+2);j++) @{
249 If you felt such a basic example is yet interesting, there is a good chance
250 that CLooG is appropriate for you. CLooG can do much more: scanning several
251 polyhedra or unions of polyhedra at the same time, applying general affine
252 transformations to the polyhedra, generate compilable code etc. Welcome
253 to the CLooG's user's guide !
256 @section Defining a Scanning Order: Scattering Functions
257 In CLooG, domains only define the set of integral points to scan and their
258 coordinates. In particular, CLooG is free to choose the scanning order for
259 generating the most efficient code. This means, for optimizing/parallelizing
260 compiler people, that CLooG doesn't make any speculation on dependences on and
261 between statements (by the way, it's not its job !).
262 For instance, if an user give to
263 CLooG only two domains @code{S1:1<=i<=n}, @code{S2:1<=i<=n} and the context
264 @code{n>=1}, the following pseudo-codes are considered to be equivalent:
268 /* A convenient target pseudo-code. */
269 for (i=1;i<=N;i++) @{
272 for (i=1;i<=N;i++) @{
280 /* Another convenient target pseudo-code. */
281 for (i=1;i<=N;i++) @{
288 The default behaviour
289 of CLooG is to generate the second one, since it is optimized in control.
290 It is right if there are no data dependences
291 between @code{S1} and @code{S2}, but wrong otherwise.
293 Thus it is often useful to force scanning to respect a given order. This can be
294 done in CLooG by using @strong{scattering functions}. Scattering is a
295 shortcut for scheduling, allocation, chunking functions and the like we can
296 find in the restructuring compilation litterature. There are a lot of reasons
297 to scatter the integral points of the domains (i.e. the statement instances
298 of a program, for compilation people), parallelization or optimization are good
299 examples. For instance, if the user wants for any reason to set some
300 precedence constraints between the statements of our example above
301 in order to force the generation of the
302 first code, he can do it easily by setting (for example) the following
303 scheduling functions:
306 $$\theta _{S1}(i) = (1)$$
307 $$\theta _{S2}(j) = (2)$$
319 This scattering means that each integral point of the domain @code{S1}
320 is scanned at logical date @code{1} while each integral point of the domain
321 @code{S2} is scanned at logical date @code{2}. As a result, the whole
322 domain @code{S1} is scanned before domain @code{S2} and the first code in our
323 example is generated.
325 The user can set every kind of affine scanning order thanks to the
326 scattering functions. Each domain has its own scattering function and
327 each scattering function may be multi-dimensional. A multi-dimentional logical
328 date may be seen as classical date (year,month,day,hour,minute,etc.) where
329 the first dimensions are the most significant. Each scattering dimension
330 may depend linearly on the original dimensions (e.g., @code{i}), the
331 parameters (e.g., @code{n}) ans scalars (e.g., @code{2}).
333 A very useful example of multi-dimensional scattering functions is, for
334 compilation people, the scheduling of the original program.
335 The basic data to use for code generation are statement iteration domains.
336 As we saw, these data are not sufficient to rebuild the original
337 program (what is the ordering between instances of different statements ?).
338 The missing data can be put in the scattering functions as the original
339 scheduling. The method to compute it is quite simple (@pxref{Fea92}). The idea is to
340 build an abstract syntax tree of the program and to read the scheduling for
341 each statement. For instance, let us consider the following implementation of
342 a Cholesky factorization:
346 /* A Cholesky factorization kernel. */
347 for (i=1;i<=N;i++) @{
348 for (j=1;j<=i-1;j++) @{
349 a[i][i] -= a[i][j] ; /* S1 */
351 a[i][i] = sqrt(a[i][i]) ; /* S2 */
352 for (j=i+1;j<=N;j++) @{
353 for (k=1;k<=i-1;k++) @{
354 a[j][i] -= a[j][k]*a[i][k] ; /* S3 */
356 a[j][i] /= a[i][i] ; /* S4 */
363 The corresponding abstract syntax tree is given in the following figure.
364 It directly gives the scattering functions (schedules) for all the
365 statements of the program.
367 @image{images/tree,6cm}
371 \hbox{$ \cases{ \theta _{S1}(i,j)^T &$= (0,i,0,j,0)^T$\cr
372 \theta _{S2}(i) &$= (0,i,1)^T$\cr
373 \theta _{S3}(i,j,k)^T &$= (0,i,2,j,0,k,0)^T$\cr
374 \theta _{S4}(i,j)^T &$= (0,i,2,j,1)^T$}$}
381 T_S1(i,j)^T = (0,i,0,j,0)^T
383 T_S3(i,j,k)^T = (0,i,2,j,0,k,0)^T
384 T_S4(i,j)^T = (0,i,2,j,1)^T
389 These schedules depend on the iterators and give for each instance of each
390 statement a unique execution date. Using such scattering functions allow
391 CLooG to re-generate the input code.
397 @c % ***********************Using the CLooG Software **************************
399 @chapter Using the CLooG Software
404 * Writing The Input File::
410 @c %/*************************************************************************
411 @c % * A FIRST EXAMPLE *
412 @c % *************************************************************************/
413 @node A First Example
414 @section A First Example
415 CLooG takes as input a file that must be written accordingly to a grammar
416 described in depth in a further section (@pxref{Writing The Input File}).
417 Moreover it supports many options to tune the target code presentation or
418 quality as discussed in a dedicated section (@pxref{Calling CLooG}).
420 of CLooG is not very complex and we present in this section how to generate the
421 code corresponding to a basic example discussed earlier (@pxref{Basics}).
423 The problem is to find the code that scans a 2-dimensional polyhedron
424 where @samp{i} and @samp{j} are the unknown (the two dimensions of the space)
425 and @samp{m} and @samp{n} are the parameters (the symbolic constants),
426 defined by the following set of constraints:
434 @noindent We also consider a partial knowledge of the parameter values,
435 expressed thanks to the following affine constraints:
443 An input file that corresponds to this problem, and asks for a generated
444 code in C, may be the following. Note that we do not describe here precisely
445 the structure and the components of this file (@pxref{Writing The Input File}
446 for such information, if you feel it necessary):
449 # ---------------------- CONTEXT ----------------------
452 # Context (constraints on two parameters)
453 2 4 # 2 lines and 4 columns
454 # eq/in m n 1 eq/in: 1 for inequality >=0, 0 for equality =0
455 1 1 0 -2 # 1*m + 0*n -2*1 >= 0, i.e. m>=2
456 1 0 1 -2 # 0*m + 1*n -2*1 >= 0, i.e. n>=2
458 1 # We want to set manually the parameter names
459 m n # parameter names
461 # --------------------- STATEMENTS --------------------
462 1 # Number of statements
464 1 # First statement: one domain
466 5 6 # 5 lines and 6 columns
468 1 1 0 0 0 -2 # i >= 2
469 1 -1 0 0 1 0 # i <= n
470 1 0 1 0 0 -2 # j >= 2
471 1 0 -1 1 0 0 # j <= m
472 1 -1 -1 0 1 2 # n+2-i>=j
473 0 0 0 # for future options
475 1 # We want to set manually the iterator names
478 # --------------------- SCATTERING --------------------
479 0 # No scattering functions
482 This file may be called @samp{basic.cloog}
483 (this example is provided in the CLooG distribution as
484 @code{test/manual_basic.cloog}) and we can ask CLooG to process it
485 and to generate the code by a simple calling to CLooG with this file as input:
486 @samp{cloog basic.cloog}. By default, CLooG will print the generated code in
491 /* Generated by CLooG v@value{VERSION} in 0.00s. */
492 for (i=2;i<=n;i++) @{
493 for (j=2;j<=min(m,-i+n+2);j++) @{
500 @c %/*************************************************************************
502 @c % *************************************************************************/
503 @node Writing The Input File
504 @section Writing The Input File
505 The input text file contains a problem description, i.e. the context,
506 the domains and the scattering functions.
507 Because CLooG is very 'compilable code generation oriented', we can associate
508 some additional informations to each domain. We call this association a
509 @emph{statement}. The set of all informations is
510 called a @emph{program}. The input file respects the grammar below
511 (terminals are preceeded by "_"):
515 Program ::= Context Statements Scattering
516 Context ::= Language Domain Naming
517 Statements ::= Nb_statements Statement_list Naming
518 Scattering ::= Nb_functions Domain_list Naming
519 Naming ::= Option Name_list
520 Name_list ::= _String Name_list | (void)
521 Statement_list ::= Statement Statement_list | (void)
522 Domain_list ::= _Domain Domain_list | (void)
523 Statement ::= Iteration_domain 0 0 0
524 Iteration_domain ::= Domain_union
525 Domain_union ::= Nb_domains Domain_list
528 Nb_statements ::= _Integer
529 Nb_domains ::= _Integer
530 Nb_functions ::= _Integer
534 @item @samp{Context} represents the informations that are
535 shared by all the statements. It consists on
536 the language used (which can be @samp{c} for C or @samp{f} for FORTRAN 90)
537 and the global constraints on parameters.
538 These constraints are essential
539 since they give to CLooG the number of parameters. If there is no
540 parameter or no constraints on parameters, just give a constraint
541 always satisfied like @math{1 \geq 0}. @samp{Naming} sets the parameter
543 If the naming option @samp{Option} is 1, parameter names will be read
544 on the next line. There must be exactly as many names as parameters.
545 If the naming option @samp{Option} is 0, parameter names are
546 automatically generated. The name of the first parameter will
547 be @samp{M}, and the name of the @math{(n+1)^{th}} parameter directly
548 follows the name of the @math{n^{th}} parameter in ASCII code.
549 It is the user responsibility to ensure that parameter names,
550 iterators and scattering dimension names are different.
551 @item @samp{Statements} represents the informations on the statements.
552 @samp{Nb_statements} is the number of statements in the program,
553 i.e. the number of @samp{Statement} items in the @samp{Statement_list}.
554 @samp{Statement} represents the informations on a given statement.
555 To each statement is associated a domain
556 (the statement iteration domain: @samp{Iteration_domain}) and three
557 zeroes that represents future options.
558 @samp{Naming} sets the iterator names. If the naming option
559 @samp{Option} is 1, the iterator names
560 will be read on the next line. There must be exactly as many names as
561 nesting level in the deepest iteration domain. If the naming option
562 @samp{Option} is 0, iterator names are automatically generated.
563 The iterator name of the outermost loop will be @samp{i}, and the
564 iterator name of the loop at level @math{n+1} directly follows the
565 iterator name of the loop at level @math{n} in ASCII code.
566 @item @samp{Scattering} represents the informations on scattering functions.
567 @samp{Nb_functions} is the number of functions (it must be
568 equal to the number of statements or 0 if there is no scattering
569 function). The function themselves are represented through
571 @samp{Naming} sets the scattering dimension names. If the naming option
572 @samp{Option} is 1, the scattering dimension names will be read on the
574 There must be exactly as many names as scattering dimensions. If the
575 naming option @samp{Option} is 0, scattering dimension names are automatically
576 generated. The name of the @math{n^{th}} scattering dimention
581 * Domain Representation::
582 * Scattering Representation::
585 @node Domain Representation
586 @subsection Domain Representation
587 As shown by the grammar, the input file describes the various informations
588 thanks to characters, integers and domains. Each domain is defined by a set of
589 constraints in the PolyLib format (@pxref{Wil93}). They have the
592 @item some optional comment lines beginning with @samp{#},
593 @item the row and column numbers, possibly followed by comments,
594 @item the constraint rows, each row corresponds to a constraint the
595 domain have to satisfy. Each row must be on a single line and is possibly
596 followed by comments. The constraint is an equality @math{p(x) = 0} if the
597 first element is 0, an inequality @math{p(x) \geq 0} if the first element
598 is 1. The next elements are the unknown coefficients, followed by
599 the parameter coefficients. The last element is the constant factor.
601 For instance, assuming that @samp{i}, @samp{j} and @samp{k} are iterators and
602 @samp{m} and @samp{n} are parameters, the domain defined by the following
607 \hbox{$ \cases{ -i + m &$\geq 0$\cr
609 i + j - k &$\geq 0$}$}
623 @noindent can be written in the input file as follows :
628 3 7 # 3 lines and 7 columns
630 1 -1 0 0 1 0 0 # -i + m >= 0
631 1 0 -1 0 0 1 0 # -j + n >= 0
632 1 1 1 -1 0 0 0 # i + j - k >= 0
636 Each iteration domain @samp{Iteration_domain} of a given statement
637 is a union of polyhedra
638 @samp{Domain_union}. A union is defined by its number of elements
639 @samp{Nb_domains} and the elements themselves @samp{Domain_list}.
640 For instance, let us consider the following pseudo-code:
644 for (i=1;i<=n;i++) @{
645 if ((i >= m) || (i <= 2*m))
653 @noindent The iteration domain of @samp{S1} can be divided into two
654 polyhedra and written in the input file as follows:
658 2 # Number of polyhedra in the union
660 3 5 # 3 lines and 5 columns
666 3 5 # 3 lines and 5 columns
670 1 -1 2 0 0 # i <= 2*m
674 @node Scattering Representation
675 @subsection Scattering Function Representation
676 Scattering functions are depicted in the input file thanks a representation
677 very close to the domain one.
678 An integer gives the number of functions @samp{Nb_functions} and each function
679 is represented by a domain. Each line of the domain corresponds to an equality
680 defining a dimension of the function. Note that at present
681 (CLooG @value{VERSION})
682 @strong{all functions must have the same scattering dimension number}. If a
683 user wants to set scattering functions with different dimensionality, he has
684 to complete the smaller one with zeroes to reach the maximum dimensionality.
685 For instance, let us consider the following code and
686 scheduling functions:
690 for (i=1;i<=n;i++) @{
691 if ((i >= m) || (i <= 2*m))
701 \hbox{$ \cases{ \theta _{S1}(i) &$= (i,0)^T$\cr
702 \theta _{S2}(i,j)^T &$= (n,i+j)^T$}$}
710 T_S2(i,j)^T = (n,i+j)^T
716 @noindent This scheduling can be written in the input file as follows:
720 2 # Number of scattering functions
722 2 7 # 2 lines and 7 columns
723 # eq/in c1 c2 i m n 1
724 0 1 0 -1 0 0 0 # c1 = i
725 0 0 1 0 0 0 0 # c2 = 0
727 2 8 # 2 lines and 8 columns
728 # eq/in c1 c2 i j m n 1
729 0 1 0 0 0 0 -1 0 # c1 = n
730 0 0 1 -1 -1 0 0 0 # c2 = i+j
733 The complete input file for the user who wants to generate the code for this
734 example with the preceding scheduling would be
735 (this file is provided in the CLooG distribution
736 as @code{test/manual_scattering.cloog}:
739 # ---------------------- CONTEXT ----------------------
742 # Context (no constraints on two parameters)
743 1 4 # 1 lines and 4 columns
745 1 0 0 0 # 0 >= 0, always true
747 1 # We want to set manually the parameter names
748 m n # parameter names
750 # --------------------- STATEMENTS --------------------
751 2 # Number of statements
753 2 # First statement: two domains
755 3 5 # 3 lines and 5 columns
761 3 5 # 3 lines and 5 columns
765 1 -1 2 0 0 # i <= 2*m
766 0 0 0 # for future options
768 1 # Second statement: one domain
769 4 6 # 4 lines and 6 columns
771 1 1 0 0 0 -1 # i >= 1
772 1 -1 0 0 1 0 # i <= n
773 1 -1 1 0 0 -1 # j >= i+1
774 1 0 -1 1 0 0 # j <= m
775 0 0 0 # for future options
777 1 # We want to set manually the iterator names
780 # --------------------- SCATTERING --------------------
781 2 # Scattering functions
783 2 7 # 2 lines and 7 columns
784 # eq/in p1 p2 i m n 1
785 0 1 0 -1 0 0 0 # p1 = i
786 0 0 1 0 0 0 0 # p2 = 0
788 2 8 # 2 lines and 8 columns
789 # eq/in p1 p2 i j m n 1
790 0 1 0 0 0 0 -1 0 # p1 = n
791 0 0 1 -1 -1 0 0 0 # p2 = i+j
793 1 # We want to set manually the scattering dimension names
794 p1 p2 # scattering dimension names
798 @c %/*************************************************************************
799 @c % * Calling CLooG *
800 @c % *************************************************************************/
802 @section Calling CLooG
803 CLooG is called by the following command:
805 cloog [ options | file ]
807 The default behavior of CLooG is to read the input informations from a file and
808 to print the generated code or pseudo-code on the standard output.
809 CLooG's behavior and the output code shape is under the user control thanks
810 to many options which are detailed a further section (@pxref{CLooG Options}).
811 @code{file} is the input file. @code{stdin} is a special value: when used,
812 input is standard input. For instance, we can call CLooG to treat the
813 input file @code{basic.cloog} with default options by typing:
814 @code{cloog basic.cloog} or @code{more basic.cloog | cloog stdin}.
816 @c %/*************************************************************************
817 @c % * CLooG Options *
818 @c % *************************************************************************/
820 @section CLooG Options
823 * Last Depth to Optimize Control::
824 * First Depth to Optimize Control::
825 * Simplify Convex Hull::
826 * Once Time Loop Elimination::
827 * Equality Spreading::
828 * Constant Spreading::
829 * First Level for Spreading::
830 * C PreProcessor Friendly::
839 @node Last Depth to Optimize Control
840 @subsection Last Depth to Optimize Control @code{-l <depth>}
842 @code{-l <depth>}: this option sets the last loop depth to be optimized in
843 control. The higher this depth, the less control overhead.
844 For instance, with some input file, a user can generate
845 different pseudo-codes with different @code{depth} values as shown below.
848 /* Generated using a given input file and @strong{option -l 1} */
849 for (i=0;i<=M;i++) @{
851 for (j=0;j<=N;j++) @{
854 for (j=0;j<=N;j++) @{
863 /* Generated using the same input file but @strong{option -l 2} */
864 for (i=0;i<=M;i++) @{
866 for (j=0;j<=N;j++) @{
874 In this example we can see that this option can change the operation
875 execution order between statements. Let us remind that CLooG does not
876 make any speculation on dependences between statements
877 (@pxref{Scattering}). Thus if nothing (i.e. scattering functions)
878 forbids this, CLooG considers the above codes to be equivalent.
879 If there is no scattering functions, the minimum value for @code{depth}
880 is 1 (in the case of 0, the user doesn't really need a loop generator !),
881 and the number of scattering dimensions otherwise (CLooG will warn the
882 user if he doesn't respect such constraint).
883 The maximum value for depth is -1 (infinity).
884 Default value is infinity.
886 @node First Depth to Optimize Control
887 @subsection First Depth to Optimize Control @code{-f <depth>}
889 @code{-f <depth>}: this option sets the first loop depth to be optimized
890 in control. The lower this depth, the less control overhead (and the longer
891 the generated code). For instance, with some input file, a user
892 can generate different pseudo-codes with different @code{depth} values
894 The minimum value for @code{depth} is 1, and the
895 maximum value is -1 (infinity).
899 /* Generated using a given input file and @strong{option -f 3} */
900 for (i=1;i<=N;i++) @{
901 for (j=1;j<=M;j++) @{
912 /* Generated using the same input file but @strong{option -f 2} */
913 for (i=1;i<=N;i++) @{
914 for (j=1;j<=9;j++) @{
917 for (j=10;j<=M;j++) @{
925 @node Simplify Convex Hull
926 @subsection Simplify Convex Hull @code{-sh <boolean>}
928 @code{-sh <boolean>}: this option enables (@code{boolean=1})
929 or forbids (@code{boolean=0}) a simplification step
930 that may simplify some constraints.
931 This option works only for generated code without
932 code duplication (it means, you have to tune @code{-f} and
933 @code{-l} options first to generate only a loop nest with internal
934 guards). For instance, with the input file @code{test/union.cloog}, a user
935 can generate different pseudo-codes as shown below.
939 /* Generated using test/union.cloog and @strong{option -f -1 -l 2 -override} */
940 for (i=0;i<=11;i++) @{
941 for (j=max(0,5*i-50);j<=min(15,5*i+10);j++) @{
942 if ((i <= 10) && (j <= 10)) @{
945 if ((i >= 1) && (j >= 5)) @{
954 /* Generated using the same input file but @strong{option -sh 1 -f -1 -l 2 -override} */
955 for (i=0;i<=11;i++) @{
956 for (j=0;j<=15;j++) @{
957 if ((i <= 10) && (j <= 10)) @{
960 if ((i >= 1) && (j >= 5)) @{
968 @node Once Time Loop Elimination
969 @subsection Once Time Loop Elimination @code{-otl <boolean>}
971 @code{-otl <boolean>}: this option allows (@code{boolean=1}) or
972 forbids (@code{boolean=0}) the simplification of loops running
973 once. Default value is 1.
976 /* Generated using a given input file and @strong{option -otl 0} */
977 for (j=i+1;j<=i+1;j++) @{
984 /* Generated using the same input file but @strong{option -otl 1} */
991 @node Equality Spreading
992 @subsection Equality Spreading @code{-esp <boolean>}
994 @code{-esp <boolean>}: this option allows (@code{boolean=1}) or
995 forbids (@code{boolean=0}) values spreading when there
996 are equalities. Default value is 0.
999 /* Generated using a given input file and @strong{option -esp 0} */
1002 for (k=i;k<=j+M;k++) @{
1009 /* Generated using the same input file but @strong{option -esp 1} */
1010 for (k=M+2;k<=N+M;k++) @{
1011 S1(i = M+2, j = N) ;
1017 @node Constant Spreading
1018 @subsection Constant Spreading @code{-csp <boolean>}
1020 @code{-csp <boolean>}: this option allows (@code{boolean=1}) or
1021 forbids (@code{boolean=0}) values spreading when
1022 there are @emph{constant} equalities. That is, when the right member
1023 of the equality is a constant term. Default value is 1.
1026 /* Generated using a given input file and @strong{option -csp 0} */
1029 for (k=i;j<=j+M;j++) @{
1036 /* Generated using the same input file but @strong{option -csp 1} */
1038 for (k=i;k<=N+M;k++) @{
1045 @node First Level for Spreading
1046 @subsection First Level for Spreading @code{-fsp <level>}
1048 @code{-fsp <level>}: it can be useful to set a
1049 first level to begin equality spreading. Particularly when using
1050 scattering functions, the user may want to see the scattering dimension
1051 values instead of spreading or hiding them. If user has set a
1052 spreading, @code{level} is
1053 the first level to start it. Default value is 1.
1056 /* Generated using a given input file and @strong{option -fsp 1} */
1057 for (j=0;j<=N+M;j++) @{
1060 for (j=0;j<=N+M;j++) @{
1067 /* Generated using the same input file but @strong{option -fsp 2} */
1069 for (j=0;j<=c1+M;j++) @{
1073 for (j=0;j<=N+c1;j++) @{
1080 @node C PreProcessor Friendly
1081 @subsection C PreProcessor Friendly @code{-cpp <boolean>}
1083 @code{-cpp <boolean>}: this option ask CLooG for printing a less
1084 human-readable but compilable code by using the C preprocessor
1085 (@code{boolean=1}). In this case each statement is written as a
1086 function of the iterators corresponding to its domain dimensions:
1087 @code{Si(value_of_iterator_1,...,value_of_iterator_n)}. It follows
1088 that the user can easily add preprocessor macros to define each
1089 statement and use the generated textual code directly for compilation.
1090 When @code{boolean} is set to 0, the pretty printer has the default
1091 behaviour. Default value is 0.
1094 /* Generated using a given input file and @strong{option -cpp 0} */
1095 for (j=0;j<=N+M;j++) @{
1102 /* Generated using the same input file but @strong{option -cpp 1} */
1103 /* and a preprocessor macro set by the user */
1105 #define S1(i,j) A[(j)]=3*(i)
1107 for (j=0;j<=N+M;j++) @{
1113 @node Statement Block
1114 @subsection Statement Block @code{-block <boolean>}
1116 @code{-block <boolean>}: this option allows (@code{boolean=1}) to
1117 create a statement block for each new iterator, even if there is only
1118 an equality. This can be useful in order to parse the generated
1119 pseudo-code. When @code{boolean} is set to 0 or when the generation
1120 language is FORTRAN, this feature is disabled. Default value is 0.
1123 /* Generated using a given input file and @strong{option -block 0} */
1131 /* Generated using the same input file but @strong{option -block 1} */
1142 @subsection Loop Strides @code{-strides <boolean>}
1144 @code{-strides <boolean>}: this options allows (@code{boolean=1}) to
1145 handle non-unit strides for loop increments. This can remove a lot of
1146 guards and make the generated code more efficient. Default value is 0.
1149 /* Generated using a given input file and @strong{option -strides 0} */
1150 for (i=1;i<=n;i++) @{
1162 /* Generated using the same input file but @strong{option -strides 1} */
1163 for (i=2;i<=n;i+=2) @{
1172 @node Compilable Code
1173 @subsection Compilable Code @code{-compilable <value>}
1175 @code{-compilable <value>}: this options allows (@code{value} is not 0)
1176 to generate a compilable code where all parameters have the integral value
1177 @code{value}. This option creates a macro for each statement. Since
1178 CLooG do not know anything about the statement sources, it fills the
1179 macros with a basic increment that computes the total number of
1180 scanned integral points. The user may change easily the macros according
1181 to his own needs. This option is possible only if the generated code is
1182 in C. Default value is 0.
1185 /* Generated using a given input file and @strong{option -compilable 0} */
1186 for (i=0;i<=n;i++) @{
1187 for (j=0;j<=n;j++) @{
1196 /* Generated using the same input file but @strong{option -compilable 10} */
1197 /* DON'T FORGET TO USE -lm OPTION TO COMPILE. */
1199 /* Useful headers. */
1204 /* Parameter value. */
1207 /* Statement macros (please set). */
1208 #define S1(i,j) @{total++;@}
1209 #define S2(i,j) @{total++;@}
1210 #define S3(i) @{total++;@}
1213 /* Original iterators. */
1216 int n=PARVAL, total=0 ;
1218 for (i=0;i<=n;i++) @{
1219 for (j=0;j<=n;j++) @{
1226 printf("Number of integral points: %d.\n",total) ;
1232 @subsection Output @code{-o <output>}
1234 @code{-o <output>}: this option sets the output file. @code{stdout} is a
1235 special value: when used, output is standard output.
1236 Default value is @code{stdout}.
1239 @subsection Help @code{--help} or @code{-h}
1241 @code{--help} or @code{-h}: this option ask CLooG to print a short help.
1244 @subsection Version @code{--version} or @code{-v}
1246 @code{--version} or @code{-v}: this option ask CLooG to print some version
1250 @c %/*************************************************************************
1251 @c % * A Full Example *
1252 @c % *************************************************************************/
1254 @section A Full Example
1256 Let us consider the allocation problem of a Gaussian elimination, i.e. we want
1257 to distribute the various statement instances of the compute kernel onto
1258 different processors. The original code is the following:
1261 for (i=1;j<=N-1;i++) @{
1262 for (j=i+1;j<=N;j++) @{
1263 c[i][j] = a[j][i]/a[i][i] ; /* S1 */
1264 for (k=i+1;k<=N;k++) @{
1265 a[j][k] -= c[i][j]*a[i][k] ; /* S2 */
1272 @noindent The best affine allocation functions can be found by any good automatic
1273 parallelizer like LooPo (@pxref{Gri04}):
1277 \hbox{$ \cases{ \theta _{S1}(i,j)^T &$= (i)$\cr
1278 \theta _{S2}(i,j,k)^T &$= (k)$}$}
1291 @noindent To ensure that on each processor, the set of statement instances is
1292 executed according to the original ordering, we add as minor scattering
1293 dimensions the original scheduling (@pxref{Scattering}):
1297 \hbox{$ \cases{ \theta _{S1}(i,j)^T &$= (i,0,i,0,j,0)^T$\cr
1298 \theta _{S2}(i,j,k)^T &$= (k,0,i,0,j,1,k,0)^T$}$}
1305 T_S1(i,j)^T = (i,0,i,0,j,0)^T
1306 T_S2(i,j,k)^T = (k,0,i,0,j,1,k,0)^T
1311 @noindent To ensure that the scattering functions have the same dimensionality, we
1312 complete the first function with zeroes
1313 (this is a CLooG @value{VERSION} and previous versions requirement,
1314 it should be removed in a future version, don't worry it's absolutly legal !):
1318 \hbox{$ \cases{ \theta _{S1}(i,j)^T &$= (i,0,i,0,j,0,0,0)^T$\cr
1319 \theta _{S2}(i,j,k)^T &$= (k,0,i,0,j,1,k,0)^T$}$}
1326 T_S1(i,j)^T = (i,0,i,0,j,0,0,0)^T
1327 T_S2(i,j,k)^T = (k,0,i,0,j,1,k,0)^T
1332 @noindent The input file corresponding to this code generation problem
1333 could be (this file is provided in the CLooG distribution
1334 as @code{test/manual_gauss.cloog}:
1337 # ---------------------- CONTEXT ----------------------
1340 # Context (no constraints on one parameter)
1341 1 3 # 1 line and 3 columns
1343 1 0 0 # 0 >= 0, always true
1345 1 # We want to set manually the parameter name
1348 # --------------------- STATEMENTS --------------------
1349 2 # Number of statements
1351 1 # First statement: one domain
1352 4 5 # 4 lines and 3 columns
1355 1 -1 0 1 -1 # i <= n-1
1356 1 -1 1 0 -1 # j >= i+1
1358 0 0 0 # for future options
1361 # Second statement: one domain
1362 6 6 # 6 lines and 3 columns
1364 1 1 0 0 0 -1 # i >= 1
1365 1 -1 0 0 1 -1 # i <= n-1
1366 1 -1 1 0 0 -1 # j >= i+1
1367 1 0 -1 0 1 0 # j <= n
1368 1 -1 0 1 0 -1 # k >= i+1
1369 1 0 0 -1 1 0 # k <= n
1370 0 0 0 # for future options
1372 0 # We let CLooG set the iterator names
1374 # --------------------- SCATTERING --------------------
1375 2 # Scattering functions
1377 8 13 # 3 lines and 3 columns
1378 # eq/in p1 p2 p3 p4 p5 p6 p7 p8 i j n 1
1379 0 1 0 0 0 0 0 0 0 -1 0 0 0 # p1 = i
1380 0 0 1 0 0 0 0 0 0 0 0 0 0 # p2 = 0
1381 0 0 0 1 0 0 0 0 0 -1 0 0 0 # p3 = i
1382 0 0 0 0 1 0 0 0 0 0 0 0 0 # p4 = 0
1383 0 0 0 0 0 1 0 0 0 0 -1 0 0 # p5 = j
1384 0 0 0 0 0 0 1 0 0 0 0 0 0 # p6 = 0
1385 0 0 0 0 0 0 0 1 0 0 0 0 0 # p7 = 0
1386 0 0 0 0 0 0 0 0 1 0 0 0 0 # p8 = 0
1388 8 14 # 3 lines and 3 columns
1389 # eq/in p1 p2 p3 p4 p5 p6 p7 p8 i j k n 1
1390 0 1 0 0 0 0 0 0 0 0 0 -1 0 0 # p1 = k
1391 0 0 1 0 0 0 0 0 0 0 0 0 0 0 # p2 = 0
1392 0 0 0 1 0 0 0 0 0 -1 0 0 0 0 # p3 = i
1393 0 0 0 0 1 0 0 0 0 0 0 0 0 0 # p4 = 0
1394 0 0 0 0 0 1 0 0 0 0 -1 0 0 0 # p5 = j
1395 0 0 0 0 0 0 1 0 0 0 0 0 0 -1 # p6 = 1
1396 0 0 0 0 0 0 0 1 0 0 0 -1 0 0 # p7 = k
1397 0 0 0 0 0 0 0 0 1 0 0 0 0 0 # p8 = 0
1399 1 # We want to set manually the scattering dimension names
1400 p1 p2 p3 p4 p5 p6 p7 p8 # scattering dimension names
1403 Calling CLooG, with for instance the command line
1404 @code{cloog -fsp 2 gauss.cloog} for a better view
1405 of the allocation (the processor number is given by @code{p1}),
1406 will result on the following target code that actually implements
1407 the transformation. A minor processing on the dimension @code{p1}
1408 to implement, e.g., MPI calls, which is not shown here may
1409 result in dramatic speedups !
1414 for (p5=2;p5<=n;p5++) @{
1418 for (p1=2;p1<=n-1;p1++) @{
1419 for (p3=1;p3<=p1-1;p3++) @{
1420 for (p5=p3+1;p5<=n;p5++) @{
1421 S2(i = p3,j = p5,k = p1) ;
1424 for (p5=p1+1;p5<=n;p5++) @{
1430 for (p3=1;p3<=n-1;p3++) @{
1431 for (p5=p3+1;p5<=n;p5++) @{
1432 S2(i = p3,j = p5,k = n) ;
1439 @c %/*************************************************************************
1440 @c % * A Full Example *
1441 @c % *************************************************************************/
1443 @chapter Using the CLooG Library
1444 The CLooG Library was implemented to allow the user to call CLooG
1445 directly from his programs, without file accesses or system calls. The
1446 user only needs to link his programs with C libraries. The CLooG
1447 library mainly provides one function (@code{cloog_program_generate})
1448 which takes as input the problem
1449 description with some options, and returns the data structure corresponding
1450 to the generated code (a @code{CloogProgram} structure) which is more or less
1451 an abstract syntax tree.
1452 The user can work with this data structure and/or use
1453 our pretty printing function to write the final code in either C or FORTRAN.
1454 Some other functions are provided for convenience reasons.
1455 These functions as well as the data structures are described in this section.
1458 * CLooG Data Structures::
1460 * Example of Library Utilization::
1464 @node CLooG Data Structures
1465 @section CLooG Data Structures Description
1466 In this section, we describe the data structures used by the loop
1467 generator to represent and to process a code generation problem.
1484 @subsection CloogMatrix
1487 #define CloogMatrix Matrix
1491 @noindent The @code{CloogMatrix} structure is directly the PolyLib
1492 @code{Matrix} data structure (@pxref{Wil93}). This structure is devoted to
1493 represent a set of constraints. It is
1494 defined in @code{polylib/types.h} as the following:
1499 @{ unsigned NbRows ; /* Number of rows. */
1500 unsigned NbColumns ; /* Number of columns. */
1501 Value ** p ; /* Array of pointers to the matrix rows. */
1502 Value * p_Init ; /* Matrix rows contiguously in memory. */
1503 int p_Init_size ; /* For internal use. */
1505 typedef struct matrix Matrix;
1509 @noindent The whole matrix is stored in memory row after row at the
1510 @code{p_Init} address. @code{p} is an array of pointers where
1511 @code{p[i]} points to the first element of the @math{i^{th}} row.
1512 @code{NbRows} and @code{NbColumns} are respectively the number of
1513 rows and columns of the matrix.
1514 Each row corresponds to a constraint. The first element of each row is an
1515 equality/inequality tag. The
1516 constraint is an equality @math{p(x) = 0} if the first element is 0, but it is
1517 an inequality @math{p(x) \geq 0} if the first element is 1.
1518 The next elements are the unknown coefficients, followed by the parameter
1519 coefficients, then the scalar coefficient.
1520 For instance, the following three constraints:
1524 \hbox{$ \cases{ -i + m &$= 0$\cr
1526 j + i - k &$\geq 0$}$}
1540 @noindent would be represented by the following rows:
1544 # eq/in i j k m n cst
1551 @noindent To be able to provide different precision version (CLooG
1552 supports 32 bits, 64 bits and arbitrary precision through the GMP library),
1553 the @code{Value} type depends on the configuration options (it may be
1554 @code{long int} for 32 bits version, @code{long long int} for 64 bits version,
1555 and @code{mpz_t} for multiple precision version).
1556 The @code{p_Init_size} field is needed by the PolyLib to free
1557 the memory allocated by @code{mpz_init} in the multiple precision release.
1558 Set this field to 0 if you are @emph{not} using multiple precision.
1559 Set this field to the size of the @code{p_Init} array if you
1560 initialized it yourself and if you are using the multiple precision version.
1564 @subsection CloogDomain
1568 @{ Polyhedron * polyhedron ; /* The polyhedral domain. */
1570 typedef struct cloogdomain CloogDomain ;
1574 @noindent The @code{CloogDomain} structure contains a PolyLib
1575 @code{Polyhedron} data structure which represents a polyhedral domain
1576 (a union of polyhedra) in both constraint representation and its dual
1577 ray representation (@pxref{Wil93}).
1578 It is defined in @code{polylib/types.h} as the following:
1583 @{ unsigned Dimension, /* Number of dimensions. */
1584 NbConstraints, /* Number of constraints. */
1585 NbRays, /* Number of rays. */
1586 NbEq, /* Number of vertices (?). */
1587 NbBid ; /* Number of extremal rays (?). */
1588 Value ** Constraint ; /* Pointers to constraints. */
1589 Value ** Ray ; /* Pointers to rays. */
1590 Value * p_Init ; /* Constraints and rays contiguously. */
1591 int p_Init_size ; /* For internal use. */
1592 struct polyhedron * next ; /* Next component of the union. */
1594 typedef struct polyhedron Polyhedron;
1598 @noindent The constraint representation is quite the same as in
1599 the @code{Matrix} data structure (@pxref{CloogMatrix}). The number of
1600 rows is @code{NbConstraints} and the
1601 number of columns in the @code{Polyhedron} structure is
1602 @code{Dimension+2} (the @math{+2} comes from the equality/inequality
1603 tag and the scalar coefficient). As in the @code{Matrix} structure,
1604 The data are stored in memory contiguously at the
1605 @code{p_Init} address and the @code{p_Init_size} field is used for
1606 memory deallocation in the multiple precision case (@pxref{CloogMatrix}).
1607 For a better understanding of the
1608 dual ray representation, the user may refer to the PolyLib documentation.
1611 @node CloogDomainList
1612 @subsection CloogDomainList
1615 struct cloogdomainlist
1616 @{ CloogDomain * domain ;
1617 struct cloogdomainlist * next ;
1619 typedef struct cloogdomainlist CloogDomainList ;
1623 @noindent The CloogDomainList structure represents a @code{NULL} terminated linked list
1627 @node CloogStatement
1628 @subsection CloogStatement
1631 struct cloogstatement
1632 @{ int number ; /* The statement unique number. */
1633 void * usr ; /* Pointer for user's convenience. */
1634 struct cloogstatement * next ;/* Next element of the linked list. */
1636 typedef struct cloogstatement CloogStatement ;
1640 @noindent The @code{CloogStatement} structure represents a @code{NULL}
1642 list of statements. In CLooG, a statement is only defined by its unique
1643 number (@code{number}). The user can use the pointer @code{usr} for his
1644 own convenience to link his own statement representation to the
1645 corresponding @code{CloogStatement} structure. The whole management of the
1646 @code{usr} pointer is under the responsibility of the user, in particular,
1647 CLooG never tries to print, to allocate or to free a memory block pointed
1652 @subsection CloogBlock
1656 @{ CloogStatement * statement ; /* Statement list of the block. */
1657 CloogMatrix * scattering ; /* Scattering function of the block. */
1658 int depth ; /* Original block depth.*/
1659 void * usr; /* Pointer for user's convenience. */
1661 typedef struct cloogblock CloogBlock ;
1665 @noindent The @code{CloogBlock} structure represents a statement block.
1666 In a statement block, every statements have the same iteration
1667 domain and the same scattering function (actually, the scattering
1668 functions may differ only by a scalar
1669 coefficient if it just precises the ordering of the statements within
1670 the block). @code{statement} is the statement list where the
1671 statement order matters, @code{scattering} is one of
1672 the statement scattering functions and
1673 @code{depth} is the number of dimensions of the
1674 iteration domain (only the unknown, not the tag/parameters/scalar).
1675 @code{usr} is a pointer for library user's convenience. Note this pointer
1676 is never allocated, freed or printed by CLooG.
1678 @node CloogBlockList
1679 @subsection CloogBlockList
1682 struct cloogdblocklist
1683 @{ CloogBlock * block ;
1684 struct cloogblocklist * next ;
1686 typedef struct cloogblocklist CloogBlockList ;
1690 @noindent The CloogBlockList structure represents a @code{NULL} terminated linked list
1695 @subsection CloogLoop
1699 @{ CloogDomain * domain; /* Iteration domain. */
1700 Value stride ; /* Loop stride. */
1701 CloogBlock * block ; /* Included statement block.*/
1702 void * usr; /* Pointer for user's convenience. */
1703 struct cloogloop * inner ; /* Loop at the next level. */
1704 struct cloogloop * next ; /* Next loop at the same level. */
1706 typedef struct cloogloop CloogLoop ;
1710 @noindent The @code{CloogLoop} structure represents a loop.
1712 loop has an iteration domain (@code{domain}). The iterator's stride for loop
1713 increment is @code{stride}. The loop can include a statement block
1714 in the field @code{block}. If there is no included statement block,
1715 @code{block} is set to @code{NULL}. @code{usr} is a pointer for library
1716 user's convenience. Note that this pointer is never allocated, freed or
1717 printed by CLooG. @code{inner} is a pointer to the inner
1718 loop, and @code{next} a pointer to the next loop in the textual order. If
1719 there are no inner loop or no next loop, the corresponding pointer is set
1724 @subsection CloogNames
1728 @{ int nb_scattering ; /* Scattering dimension number. */
1729 int nb_iterators ; /* Iterator number. */
1730 int nb_parameters ; /* Parameter number. */
1731 char ** scattering ; /* The scattering dimension names. */
1732 char ** iterators ; /* The iterator names. */
1733 char ** parameters ; /* The parameter names. */
1735 typedef struct cloognames CloogNames ;
1739 @noindent The @code{CloogNames} structure represents the scattering dimension,
1740 the iterator and the parameter names in the final program.
1741 @code{nb_scattering}
1742 (respectively @code{nb_iterators} and @code{nb_parameters})
1743 is the number of scattering dimensions number
1744 (respectively the iterator and parameter number)
1745 and of elements in the corresponding array of strings
1747 (respectively @code{iterators} and @code{parameters}).
1748 The @math{i^{th}} scattering dimension name will be associated with the
1749 to the dimension @math{i} of the scattering function.
1750 The @math{i^{th}} iterator name will be associated with the
1751 dimension @math{i} of the iteration domain.
1752 The @math{i^{th}} parameter name will be associated with the
1753 dimension @math{i} of the context polyhedron.
1754 The user has to ensure that there are
1755 enough scattering dimension, iterator and parameter names.
1759 @subsection CloogProgram
1763 @{ char language ; /* The language of the program. */
1764 int nb_scattdims ; /* Scattering dimension number. */
1765 CloogNames * names ; /* Iterators and parameters names. */
1766 CloogDomain * context ; /* The context of the program. */
1767 CloogLoop * loop ; /* The loops of the program. */
1768 CloogBlockList * blocklist ; /* The statement block list. */
1769 void * usr; /* For library user's convenience. */
1771 typedef struct cloogprogram CloogProgram ;
1775 @noindent The @code{CloogProgram} structure represents a static control program kernel.
1776 @code{language} precises the language (@code{c} for C or @code{f} for FORTRAN).
1777 @code{nb_scattdims} gives the number of scattering dimensions.
1778 @code{context} is a pointer to the constraints on the program parameters,
1780 @code{NULL} pointer even if there are no constraints on parameters. In such a
1781 case, set a polyhedron with as many dimensions as there are parameters, with
1782 an @emph{always true} constraint like @math{1 \geq 0} (this is necessary
1783 since the number of parameters is deduced from the dimension number of
1784 the context constraints). @code{loop} is a pointer
1785 to the first loop of the program. @code{names} is a pointer to the various
1786 element names (scattering dimension, iterators, parameters)
1787 of the final program. @code{names} can be the @code{NULL}
1788 pointer if the user do not want to use our pretty printing function.
1789 @code{blocklist} is the linked list of all the statement block structures.
1790 @code{usr} is a pointer for library user's convenience. Note that this pointer
1791 is never allocated, freed or printed by CLooG.
1792 As an example, let us consider the following loop nest:
1795 for (i=0; i<=n; i++) @{
1796 for (j=0; j<=n; j++) @{
1800 for (j=n+1; j<=2*n; j++) @{
1806 @noindent The next figure gives a possible representation in memory for this
1807 program thanks to the CLooG data structures (it has been actually printed
1808 by the @code{cloog_program_print} function). In this figure,
1809 @samp{+-- CloogLoop} denotes an @samp{inner} loop, while a @samp{CloogLoop}
1810 on the same column pointed by an arrow denotes a @samp{next} loop:
1817 | Scattering dimension number: 0
1821 | | Scattering dimension number: 0
1823 | | +-- No scattering string
1825 | | Iterator number -----------: 2
1827 | | +-- Iterator strings ------: i j
1829 | | Parameter number ----------: 1
1831 | | +-- Parameter strings -----: n
1846 | | +-- Null CloogBlock
1850 | | | +-- CloogDomain
1851 | | | | [ 1 0 1 0 0 ]
1852 | | | | [ 1 0 -1 1 0 ]
1853 | | | | [ 1 0 0 0 1 ]
1857 | | | +-- Null CloogBlock
1861 | | | | +-- CloogDomain
1862 | | | | | [ 1 0 0 0 1 ]
1866 | | | | +-- CloogBlock
1868 | | | | | +-- CloogStatement 1
1871 | | | | | | CloogStatement 2
1873 | | | | | +-- Null scattering function
1881 | | | +-- CloogDomain
1882 | | | | [ 1 0 -1 2 0 ]
1883 | | | | [ 1 0 1 -1 -1 ]
1884 | | | | [ 1 0 0 0 1 ]
1888 | | | +-- Null CloogBlock
1892 | | | | +-- CloogDomain
1893 | | | | | [ 1 0 0 0 1 ]
1897 | | | | +-- CloogBlock
1899 | | | | | +-- CloogStatement 3
1901 | | | | | +-- Null scattering function
1913 @subsection CloogOptions
1917 @{ int l ; /* -l option. */
1918 int f ; /* -f option. */
1919 int strides ; /* -strides option. */
1920 int sh ; /* -sh option. */
1921 int esp ; /* -esp option. */
1922 int csp ; /* -csp option. */
1923 int fsp ; /* -fsp option. */
1924 int otl ; /* -otl option. */
1925 int block ; /* -block option. */
1926 int cpp ; /* -cpp option. */
1927 int compilable ; /* -compilable option. */
1929 typedef struct cloogoptions CloogOptions ;
1933 @noindent The @code{CloogOptions} structure contains all the possible options to
1934 rule CLooG's behaviour (@pxref{Calling CLooG}).
1935 As a reminder, the default values are:
1937 @item @math{l = -1} (optimize control until the innermost loops),
1938 @item @math{f = 1} (optimize control from the outermost loops),
1939 @item @math{strides = 0} (use only unit strides),
1940 @item @math{sh = 0} (do not simplify convex hulls),
1941 @item @math{esp = 0} (do not spread complex equalities),
1942 @item @math{csp = 1} (spread constant values),
1943 @item @math{fsp = 1} (start to spread from the first iterators),
1944 @item @math{otl = 1} (simplify loops running only once).
1945 @item @math{block = 0} (do not make statement blocks when not necessary).
1946 @item @math{cpp = 0} (do not generate a compilable part of code using preprocessor).
1947 @item @math{compilable = 0} (do not generate a compilable code).
1951 @node CLooG Functions
1952 @section CLooG Functions Description
1955 * cloog_program_generate::
1956 * cloog_program_scatter::
1957 * cloog_program_pprint::
1958 * cloog_program_read::
1959 * From Matrices to Domains and Conversely::
1960 * Allocation and Initialization Functions::
1961 * Memory Deallocation Functions::
1962 * Printing Functions::
1966 @node cloog_program_generate
1967 @subsection cloog_program_generate
1970 CloogProgram * cloog_program_generate
1971 ( CloogProgram * program, /* Input program. */
1972 CloogOptions * options /* Options. */
1977 @noindent The @code{cloog_program_generate} function generates
1978 the data structure of the source code that scans the input
1979 polyhedra pointed by @code{program}
1980 according to the options pointed by @code{options}.
1981 The process is made directly on the input structure pointed by
1982 @code{program}, thus the original structure is no longer available
1983 after a call to this function. It returns a pointer to a
1984 @code{CloogProgram} structure containing the
1985 solution in CLooG structures.
1987 The input @code{CloogProgram} structure must have only one loop level
1988 (no inner loops): there is one loop per statement block. For a given block,
1989 the corresponding loop carries the iteration domain, the statement block,
1990 and a loop stride initialized to 1. For instance, the input @code{CloogProgram} structure
1991 that have been sent to @code{cloog_program_generate} to achieve the final
1992 structure and code shown as example in the @code{CloogProgram} structure
1993 description (@pxref{CloogProgram}) was the following one:
2000 | Scattering dimension number: 0
2004 | | Scattering dimension number: 0
2006 | | +-- No scattering string
2008 | | Iterator number -----------: 2
2010 | | +-- Iterator strings ------: i j
2012 | | Parameter number ----------: 1
2014 | | +-- Parameter strings -----: n
2023 | | | [ 1 -1 0 1 0 ]
2025 | | | [ 1 0 -1 1 0 ]
2031 | | | +-- CloogStatement 1
2034 | | | | CloogStatement 2
2036 | | | +-- Null scattering function
2045 | | | [ 1 -1 0 1 0 ]
2046 | | | [ 1 0 1 -1 -1 ]
2047 | | | [ 1 0 -1 2 0 ]
2053 | | | +-- CloogStatement 3
2055 | | | +-- Null scattering function
2064 @node cloog_program_pprint
2065 @subsection cloog_program_pprint
2068 void cloog_program_pprint
2069 ( FILE * file, /* Output file. */
2070 CloogProgram * program, /* Program to print. */
2071 CloogOptions * options /* Options. */
2076 @noindent The function @code{cloog_program_pprint} is a pretty printer for
2077 @code{CloogProgram} structures when it is a solution provided by
2078 the @code{cloog_program_generate} function. It prints the code or pseudo-code in the
2079 file pointed by @code{file} (possibly @code{stdout}) with regards to the
2080 options pointed by @code{options}.
2083 @node cloog_program_scatter
2084 @subsection cloog_program_scatter
2087 void cloog_program_scatter
2088 ( CloogProgram * program, /* Input program. */
2089 CloogDomainList * scattering, /* Additional scattering functions. */
2090 char ** names ; /* Additional dimension names. */
2095 @noindent The function @code{cloog_program_scatter} applies scattering
2096 functions to the @code{CloogProgram} structure pointed by @code{program}.
2097 Original domains of @code{program} are freed. Scattering functions
2098 are inside the @code{CloogDomainList} structure pointed by @code{scattering}.
2099 There must be as many scattering functions in the @code{CloogDomainList}
2100 structure as loops (i.e. iteration domains) in the @code{CloogProgram}
2101 structure. The first scattering function of the list will be applied to the
2102 iteration domain of the first loop in the program, and so on.
2103 @code{names} gives the scattering dimension names as an array of strings. If
2104 @code{names} is @code{NULL}, names are automatically generated: the name of
2105 the @math{n^{th}} scattering dimension will be @code{cn}.
2108 @node cloog_program_read
2109 @subsection cloog_program_read
2111 CloogProgram * cloog_program_read(FILE *) ;
2113 @noindent The @code{cloog_program_read} function
2114 reads the program data from a CLooG input file
2115 (@pxref{Writing The Input File}). It takes
2116 as input a pointer to the file it has to read (possibly @code{stdin}), and
2117 return a pointer to the read @code{CloogProgram} structure.
2120 @node From Matrices to Domains and Conversely
2121 @subsection From Matrices to Domains and Conversely
2123 CloogMatrix * cloog_domain_domain2matrix(CloogDomain *) ;
2124 CloogDomain * cloog_domain_matrix2domain(CloogMatrix *) ;
2126 @noindent Two functions are provided to translate a @code{CloogDomain}
2127 data structure to a @code{CloogMatrix} data structure and conversely.
2128 Each function takes as input a pointer to the data structure to translate
2129 and returns as output a pointer to the translated data structure. The
2130 input data structure if neither modified nor freed. They
2131 may be quite useful for e.g. pretty printing since it is more convenient
2132 in constraint (matrix) representation.
2135 @node Allocation and Initialization Functions
2136 @subsection Allocation and Initialization Functions
2138 CloogStructure * cloog_structure_malloc() ;
2140 @noindent Each CLooG data structure has an allocation and initialization
2141 function as shown above, where @code{Structure} and @code{structure} have to
2142 be replaced by the name of the convenient structure (without @samp{Cloog} prefix) for
2143 instance @code{CloogLoop * cloog_loop_malloc() ;}. These functions return
2144 pointers to an allocated structure with fields set to convenient default
2145 values. @strong{Using those functions is mandatory} to support internal
2146 management fields and to avoid upward compatibility problems if
2147 new fields appear. An exception is @code{cloog_matrix_malloc} since the
2148 @code{CloogMatrix} comes directly from the PolyLib. It takes two parameters:
2149 the number of rows and columns of the matrix we want to allocate:
2151 CloogMatrix * cloog_matrix_malloc(unsigned nbrows, unsigned nbcolumns);
2155 @node Memory Deallocation Functions
2156 @subsection Memory Deallocation Functions
2158 void cloog_structure_free(CloogStructure *) ;
2160 @noindent Each CLooG data structure has a deallocation function as shown above,
2161 where @code{Structure} and @code{structure} have to
2162 be replaced by the name of the convenient structure (without @samp{Cloog} prefix) for
2163 instance @code{void cloog_loop_free(CloogLoop *) ;}. These functions
2164 free the allocated memory for the structure provided as input. They free
2165 memory recursively, i.e. they also free the allocated memory for the internal
2167 @strong{Using those functions is mandatory} to avoid memory leaks on internal
2168 management fields and to avoid upward compatibility problems if
2172 @node Printing Functions
2173 @subsection Printing Functions
2175 void cloog_structure_print(FILE *, CloogStructure *) ;
2177 @noindent Each CLooG data structure has a printing function as shown above,
2178 where @code{Structure} and @code{structure} have to
2179 be replaced by the name of the convenient structure (without @samp{Cloog} prefix) for
2180 instance @code{void cloog_loop_print(FILE *, CloogLoop *) ;}. These functions
2181 print the pointed structure (and its fields recursively) to the file provided
2182 as input (possibly @code{stdout}).
2185 @node Example of Library Utilization
2186 @section Example of Library Utilization
2187 Here is a basic example showing how it is possible to use the CLooG library,
2188 assuming that a standard installation has been done.
2189 The following C program reads a CLooG input file on the standard input,
2190 then prints the solution on the standard output.
2191 Options are preselected to the default values of the CLooG software.
2192 This example is provided in the @code{example} directory of the
2197 # include <cloog/cloog.h>
2200 @{ CloogProgram * program ;
2201 CloogOptions * options ;
2203 /* Setting options and reading program informations. */
2204 options = cloog_options_malloc() ;
2205 program = cloog_program_read(stdin,options) ;
2207 /* Generating and printing the code. */
2208 program = cloog_program_generate(program,options) ;
2209 cloog_program_pprint(stdout,program,options) ;
2211 cloog_options_free(options) ;
2212 cloog_program_free(program) ;
2217 @noindent The compilation command could be:
2219 gcc example.c -lcloog -o example
2221 @noindent A calling command with the input file test.cloog could be:
2223 more test.cloog | ./example
2227 @c % ******************************** HACKING *********************************
2229 @c @chapter Hacking CLooG
2232 @c * Program organization::
2233 @c * Special Options::
2234 @c * CLooG Coding Standards::
2237 @c @node Program organization
2238 @c @section Program organization
2240 @c @node Special Options
2241 @c @section Special Options
2243 @c @node CLooG Coding Standards
2244 @c @section CLooG Coding Standards
2247 @c % ****************************** INSTALLING ********************************
2249 @chapter Installing CLooG
2254 * Basic Installation::
2255 * Optional Features::
2261 First of all, it would be very kind to refer the following paper in any
2262 publication that result from the use of the CLooG software or its library,
2263 @pxref{Bas04} (a bibtex entry is provided behind the title page of this
2264 manual, along with copyright notice, and in the CLooG home
2265 @code{http://www.CLooG.org}.
2267 This program is free software; you can redistribute it and/or
2268 modify it under the terms of the GNU General Public License version 2
2269 as published by the Free Software Foundation.
2270 This program is distributed in the hope that it will be useful,
2271 but WITHOUT ANY WARRANTY; without even the implied warranty of
2272 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
2273 GNU General Public License for more details.
2274 @code{http://www.gnu.org/copyleft/gpl.html}
2278 @section Requirements
2287 @subsection PolyLib (mandatory)
2288 To successfully install CLooG, the user need firstly to install PolyLib
2289 version 5.22.1 or above (default 64 bits version is satisfying
2290 as well as 32 bits or GMP multiple precision version).
2291 Polylib can be downloaded freely
2292 at @code{http://icps.u-strasbg.fr/PolyLib/} or
2293 @code{http://www.irisa.fr/polylib/}. Once downloaded and unpacked
2294 (e.g. using the @samp{tar -zxvf polylib-5.22.1.tar.gz} command),
2295 the user can compile
2296 it by typing the following commands on the PolyLib's root directory:
2299 @item @code{./configure}
2301 @item And as root: @code{make install}
2304 The PolyLib default installation is @code{/usr/local}. This directory may
2305 not be inside your library path. To fix the problem, the user should set
2307 export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/lib
2309 @noindent if your shell is, e.g., bash or
2311 setenv LD_LIBRARY_PATH $LD_LIBRARY_PATH:/usr/local/lib
2313 @noindent if your shell is, e.g., tcsh. Add the line to your .bashrc or .tcshrc (or
2314 whatever convenient file) to make this change permanent. Another solution
2315 is to ask PolyLib to install in the standard path by using the prefix
2316 option of the configure script:
2317 @samp{./configure --prefix=/usr}.
2319 CLooG makes intensive calls to polyhedral operations, and PolyLib
2320 functions do the job. Polylib is a free library written in C for the
2321 manipulation of polyhedra. The library is operating on objects like
2322 vectors, matrices, lattices, polyhedra, Z-polyhedra, unions of
2323 polyhedra and a lot of other intermediary structures. It provides
2324 functions for all the important operations on these structures.
2327 @subsection GMP Library (optional)
2329 To be able to deal with insanely large coefficient, the user will need to
2330 install the GNU Multiple Precision Library (GMP for short) version 4.1.4
2331 or above. It can be freely downloaded from @code{http://www.swox.com/gmp}.
2332 The user can compile it by typing the following commands on the GMP root
2336 @item @code{./configure}
2338 @item And as root: @code{make install}
2341 The GMP default installation is @code{/usr/local}, the same method to
2342 fix a library path problem applies as with PolyLib (@pxref{PolyLib}).
2344 The PolyLib has to be built using the GMP library by specifying the option
2345 @samp{--with-libgmp=PATH_TO_GMP} to the PolyLib configure script
2346 (where @code{PATH_TO_GMP} is @code{/usr/local} if you did not change the GMP
2347 installation directory). Then you have to set the convenient CLooG configure
2348 script options to buid the GMP version (@pxref{Optional Features}).
2351 @node Basic Installation
2352 @section CLooG Basic Installation
2354 Once downloaded and unpacked
2355 (e.g. using the @samp{tar -zxvf cloog-@value{VERSION}.tar.gz} command),
2356 you can compile CLooG by typing the following commands on the CLooG's root
2360 @item @code{./configure}
2362 @item And as root: @code{make install}
2365 Depending on the location of the PolyLib, you may need to set the
2366 option @code{--with-polylib} of the configure script
2367 (e.g. @samp{./configure --with-polylib=/usr/local} with a default PolyLib
2370 The program binaries and object files can be removed from the
2371 source code directory by typing @code{make clean}. To also remove the
2372 files that the @code{configure} script created (so you can compile the
2373 package for a different kind of computer) type @code{make distclean}.
2375 Both the CLooG software and library have been successfully compiled
2376 on the following systems:
2378 @item PC's under Linux, with the @code{gcc} compiler,
2379 @item PC's under Windows (Cygwin), with the @code{gcc} compiler,
2380 @item Sparc and UltraSparc Stations, with the @code{gcc} compiler.
2383 @node Optional Features
2384 @section Optional Features
2385 The @code{configure} shell script attempts to guess correct values for
2386 various system-dependent variables and user options used during compilation.
2387 It uses those values to create the @code{Makefile}. Various user options
2388 are provided by the CLooG's configure script. They are summarized in the
2389 following list and may be printed by typing @code{./configure --help} in the
2390 CLooG top-level directory.
2393 @item By default, the installation directory is @code{/usr/local}:
2394 @code{make install} will install the package's files in
2395 @code{/usr/local/bin}, @code{/usr/local/lib} and @code{/usr/local/include}.
2396 The user can specify an installation prefix other than @code{/usr/local} by
2397 giving @code{configure} the option @code{--prefix=PATH}.
2399 @item By default, @code{configure} will look for the PolyLib in standard
2400 locations. If necessary, the user can specify the PolyLib path by giving
2401 @code{configure} the option @code{--with-polylib=PATH}.
2403 @item By default, both CLooG software and library are compiled and installed.
2404 By giving @code{configure} the option @code{--without-cloog} the user
2405 disable the compilation and installation of the CLooG software.
2406 By giving @code{configure} the option
2407 @code{--without-lib} the user disable the compilation and installation of the
2410 @item By default, CLooG is built in 64bits version if such version of the
2411 PolyLib is found by @code{configure}. If the only existing version of the
2412 PolyLib is the 32bits or if the user give to @code{configure} the option
2413 @code{--with-bits=32}, the 32bits version of CLooG will be compiled. In the
2414 same way, the option @code{--with-bits=gmp} have to be used to build
2415 the multiple precision version.
2417 @item By default, @code{configure} will look for the GMP library
2418 (necessary to build the multiple precision version) in standard
2419 locations. If necessary, the user can specify the GMP path by giving
2420 @code{configure} the option @code{--with-gmp=PATH}.
2423 @node Uninstallation
2424 @section Uninstallation
2425 The user can easily remove the CLooG software and library from his system
2426 by typing (as root if necessary) from the CLooG top-level directory
2427 @code{make uninstall}.
2429 @c % **************************** DOCUMENTATION ******************************
2431 @chapter Documentation
2432 The CLooG distribution provides several documentation sources. First, the
2433 source code itself is as documented as possible. The code comments use a
2434 Doxygen-compatible presentation (something similar to what JavaDoc does for
2435 JAVA). The user may install Doxygen
2436 (see @code{http://www.stack.nl/~dimitri/doxygen}) to automatically
2437 generate a technical documentation by typing @code{make doc} or
2438 @code{doxygen ./autoconf/Doxyfile} at the CLooG top-level directory after
2439 running the configure script (@pxref{Installing}). Doxygen will generate
2440 documentation sources (in HTML, LaTeX and man) in the @code{doc/source}
2441 directory of the CLooG distribution.
2443 The Texinfo sources of the present document are also provided in the @code{doc}
2444 directory. You can build it in either DVI format (by typing
2445 @code{texi2dvi cloog.texi}) or PDF format
2446 (by typing @code{texi2pdf cloog.texi}) or HTML format
2447 (by typing @code{makeinfo --html cloog.texi}, using @code{--no-split}
2448 option to generate a single HTML file) or info format
2449 (by typing @code{makeinfo cloog.texi}).
2451 @c % ****************************** REFERENCES ********************************
2457 @anchor{Bas03a}[Bas03a] C. Bastoul, P. Feautrier. Improving data locality
2458 by chunking. CC'12 International Conference on Compiler Construction,
2459 LNCS 2622, pages 320-335, Warsaw, april 2003.
2462 @anchor{Bas03b}[Bas03b] C. Bastoul. Efficient code generation for automatic
2463 parallelization and optimization. ISPDC'03 IEEE International Symposium on
2464 Parallel and Distributed Computing, pages 23-30, Ljubljana, october 2003.
2467 @anchor{Bas04}[Bas04] C. Bastoul. Code Generation in the Polyhedral Model
2468 Is Easier Than You Think. PACT'13 IEEE International Conference on Parallel
2469 Architecture and Compilation Techniques, pages 7-16, Juan-les-Pins,
2473 @anchor{Fea92}[Fea92] P. Feautrier Some efficient solutions to the affine
2474 scheduling problem, part II: multidimensional time.
2475 International Journal of Parallel Programming, 21(6):389--420, December 1992.
2478 @anchor{Gri04}[Gri04] M. Griebl. Automatic parallelization of loop programs
2479 for distributed memory architectures. Habilitation Thesis. Facult@"at f@"ur
2480 Mathematik und Informatik, Universit@"at Passau, 2004.
2481 @emph{http://www.infosun.fmi.uni-passau.de/cl/loopo/}
2484 @anchor{Qui00}[Qui00] F. Quiller@'e, S. Rajopadhye, and D. Wilde.
2485 Generation of efficient nested loops from polyhedra.
2486 International Journal of Parallel Programming, 28(5):469-498,
2490 @anchor{Wil93}[Wil93] Doran K. Wilde.
2491 A library for doing polyhedral operations.
2492 Technical Report 785, IRISA, Rennes, France, 1993.
2499 @c % /*************************************************************************
2500 @c % * PART VI: END OF THE DOCUMENT *
2501 @c % *************************************************************************/
2502 @c @unnumbered Index