2 /**-------------------------------------------------------------------**
4 **-------------------------------------------------------------------**
6 **-------------------------------------------------------------------**
7 ** First version: october 25th 2001 **
8 **-------------------------------------------------------------------**/
11 /******************************************************************************
12 * CLooG : the Chunky Loop Generator (experimental) *
13 ******************************************************************************
15 * Copyright (C) 2001-2005 Cedric Bastoul *
17 * This library is free software; you can redistribute it and/or *
18 * modify it under the terms of the GNU Lesser General Public *
19 * License as published by the Free Software Foundation; either *
20 * version 2.1 of the License, or (at your option) any later version. *
22 * This library is distributed in the hope that it will be useful, *
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
25 * Lesser General Public License for more details. *
27 * You should have received a copy of the GNU Lesser General Public *
28 * License along with this library; if not, write to the Free Software *
29 * Foundation, Inc., 51 Franklin Street, Fifth Floor, *
30 * Boston, MA 02110-1301 USA *
32 * CLooG, the Chunky Loop Generator *
33 * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr *
35 ******************************************************************************/
36 /* CAUTION: the english used for comments is probably the worst you ever read,
37 * please feel free to correct and improve it !
41 # include <sys/types.h>
42 # include <sys/time.h>
49 # include "../include/cloog/cloog.h"
51 # include <sys/resource.h>
54 #define ALLOC(type) (type*)malloc(sizeof(type))
58 #include <osl/extensions/coordinates.h>
59 #include <osl/extensions/loop.h>
62 /******************************************************************************
63 * Structure display function *
64 ******************************************************************************/
68 * cloog_program_print function:
69 * this function is a human-friendly way to display the CloogProgram data
70 * structure, it shows all the different fields and includes an indentation
71 * level (level) in order to work with others print_structure functions.
72 * - July 1st 2005: first version based on the old cloog_program_print function.
74 void cloog_program_print_structure(file
, program
, level
)
76 CloogProgram
* program
;
80 /* Go to the right level. */
81 for (i
=0; i
<level
; i
++)
84 fprintf(file
,"+-- CloogProgram\n") ;
87 for (i
=0; i
<=level
+1; i
++)
91 /* Print the language. */
92 for (i
=0; i
<=level
; i
++)
94 fprintf(file
, "Language: %c\n",program
->language
) ;
97 for (i
=0; i
<=level
+1; i
++)
101 /* Print the scattering dimension number. */
102 for (i
=0; i
<=level
; i
++)
103 fprintf(file
,"|\t") ;
104 fprintf(file
,"Scattering dimension number: %d\n",program
->nb_scattdims
) ;
107 for (i
=0; i
<=level
+1; i
++)
108 fprintf(file
,"|\t") ;
111 /* Print the scalar scattering dimension informations. */
112 for (i
=0; i
<=level
; i
++)
113 fprintf(file
,"|\t") ;
114 if (program
->scaldims
!= NULL
)
115 { fprintf(file
,"Scalar dimensions:") ;
116 for (i
=0;i
<program
->nb_scattdims
;i
++)
117 fprintf(file
," %d:%d ",i
,program
->scaldims
[i
]) ;
121 fprintf(file
,"No scalar scattering dimensions\n") ;
124 for (i
=0; i
<=level
+1; i
++)
125 fprintf(file
,"|\t") ;
128 /* Print the parameter and the iterator names. */
129 cloog_names_print_structure(file
,program
->names
,level
+1) ;
132 for (i
=0; i
<=level
+1; i
++)
133 fprintf(file
,"|\t") ;
136 /* Print the context. */
137 cloog_domain_print_structure(file
, program
->context
, level
+1, "Context");
139 /* Print the loop. */
140 cloog_loop_print_structure(file
,program
->loop
,level
+1) ;
142 /* One more time something that is here only for a better look. */
144 { for (i
=0; i
<=level
; i
++)
145 fprintf(file
,"|\t") ;
153 * cloog_program_dump_cloog function:
154 * This function dumps a CloogProgram structure supposed to be completely
155 * filled in a CLooG input file (foo possibly stdout) such as CLooG can
156 * rebuild almost exactly the data structure from the input file.
158 * If the scattering is already applied, the scattering parameter is supposed to
159 * be NULL. In this case the number of scattering functions is lost, since they
160 * are included inside the iteration domains. This can only lead to a less
161 * beautiful pretty printing.
163 * In case the scattering is not yet applied it can be passed to this function
164 * and will be included in the CLooG input file dump.
166 void cloog_program_dump_cloog(FILE * foo
, CloogProgram
* program
,
167 CloogScatteringList
*scattering
)
171 CloogScatteringList
*tmp_scatt
;
175 "# This is an automatic dump of a CLooG input file from a CloogProgram data\n"
176 "# structure. WARNING: it is highly dangerous and MAY be correct ONLY if\n"
177 "# - it has been dumped before loop generation.\n"
178 "# - option -noscalars is used (it removes scalar dimensions otherwise)\n"
179 "# - option -l is at least the original scattering dimension number\n"
180 "# ASK THE AUTHOR IF YOU *NEED* SOMETHING MORE ROBUST\n") ;
183 if (program
->language
== 'c')
184 fprintf(foo
,"# Language: C\n") ;
186 fprintf(foo
,"# Language: FORTRAN\n") ;
187 fprintf(foo
,"%c\n\n",program
->language
) ;
190 fprintf(foo
, "# Context (%d parameter(s)):\n", program
->names
->nb_parameters
);
191 cloog_domain_print_constraints(foo
, program
->context
, 0);
192 fprintf(foo
,"1 # Parameter name(s)\n") ;
193 for (i
=0;i
<program
->names
->nb_parameters
;i
++)
194 fprintf(foo
,"%s ",program
->names
->parameters
[i
]) ;
196 /* Statement number. */
198 loop
= program
->loop
;
203 fprintf(foo
,"\n\n# Statement number:\n%d\n\n",i
) ;
205 /* Iteration domains. */
207 loop
= program
->loop
;
209 { /* Name of the domain. */
210 fprintf(foo
,"# Iteration domain of statement %d.\n",i
) ;
212 cloog_domain_print_constraints(foo
, loop
->domain
, 1);
213 fprintf(foo
,"0 0 0 # For future options.\n\n") ;
218 fprintf(foo
,"\n1 # Iterator name(s)\n") ;
220 /* Scattering already applied? In this case print the scattering names as
221 * additional iterator names. */
223 for (i
= 0; i
< program
->names
->nb_scattering
; i
++)
224 fprintf(foo
, "%s ", program
->names
->scattering
[i
]);
225 for (i
=0;i
<program
->names
->nb_iterators
;i
++)
226 fprintf(foo
,"%s ",program
->names
->iterators
[i
]);
227 fprintf(foo
,"\n\n") ;
229 /* Exit, if scattering is already applied. */
231 fprintf(foo
, "# No scattering functions.\n0\n\n");
235 /* Scattering relations. */
236 fprintf(foo
, "# --------------------- SCATTERING --------------------\n");
239 for (tmp_scatt
= scattering
; tmp_scatt
; tmp_scatt
= tmp_scatt
->next
)
242 fprintf(foo
, "%d # Scattering functions", i
);
244 for (tmp_scatt
= scattering
; tmp_scatt
; tmp_scatt
= tmp_scatt
->next
)
245 cloog_scattering_print_constraints(foo
, tmp_scatt
->scatt
);
247 fprintf(foo
, "\n1 # Scattering dimension name(s)\n");
249 for (i
= 0; i
< program
->names
->nb_scattering
; i
++)
250 fprintf(foo
, "%s ", program
->names
->scattering
[i
]);
255 * cloog_program_print function:
256 * This function prints the content of a CloogProgram structure (program) into a
257 * file (file, possibly stdout).
258 * - July 1st 2005: Now this very old function (probably as old as CLooG) is
259 * only a frontend to cloog_program_print_structure, with a
260 * quite better human-readable representation.
262 void cloog_program_print(FILE * file
, CloogProgram
* program
)
263 { cloog_program_print_structure(file
,program
,0) ;
267 static void print_comment(FILE *file
, CloogOptions
*options
,
268 const char *fmt
, ...)
273 if (options
->language
== CLOOG_LANGUAGE_FORTRAN
) {
275 vfprintf(file
, fmt
, args
);
278 fprintf(file
, "/* ");
279 vfprintf(file
, fmt
, args
);
280 fprintf(file
, " */\n");
284 static void print_macros(FILE *file
)
286 fprintf(file
, "/* Useful macros. */\n") ;
288 "#define floord(n,d) (((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))\n");
290 "#define ceild(n,d) (((n)<0) ? -((-(n))/(d)) : ((n)+(d)-1)/(d))\n");
291 fprintf(file
, "#define max(x,y) ((x) > (y) ? (x) : (y))\n") ;
292 fprintf(file
, "#define min(x,y) ((x) < (y) ? (x) : (y))\n\n") ;
293 fprintf(file
, "#ifdef TIME \n#define IF_TIME(foo) foo; \n"
294 "#else\n#define IF_TIME(foo)\n#endif\n\n");
297 static void print_declarations(FILE *file
, int n
, char **names
, int indentation
)
301 for (i
= 0; i
< indentation
; i
++)
303 fprintf(file
, "int %s", names
[0]);
304 for (i
= 1; i
< n
; i
++)
305 fprintf(file
, ", %s", names
[i
]);
306 fprintf(file
, ";\n");
309 static void print_scattering_declarations(FILE *file
, CloogProgram
*program
,
313 int nb_scatnames
= 0;
314 CloogNames
*names
= program
->names
;
316 // Copy pointer only to those scatering names that do not duplicate
318 char **scatnames
= (char **) malloc(sizeof(char *) * names
->nb_scattering
);
319 for (i
= 0; i
< names
->nb_scattering
; ++i
) {
320 for (j
= 0; j
< names
->nb_iterators
; ++j
) {
322 if (strcmp(names
->scattering
[i
], names
->iterators
[j
]) == 0) {
327 // Save a pointer (intentional!) to the names in the new array.
328 scatnames
[nb_scatnames
++] = names
->scattering
[i
];
333 for (i
= 0; i
< indentation
; i
++)
335 fprintf(file
, "/* Scattering iterators. */\n");
336 print_declarations(file
, nb_scatnames
, scatnames
, indentation
);
341 static void print_iterator_declarations(FILE *file
, CloogProgram
*program
,
342 CloogOptions
*options
)
344 CloogNames
*names
= program
->names
;
346 print_scattering_declarations(file
, program
, 2);
347 if (names
->nb_iterators
) {
348 fprintf(file
, " /* Original iterators. */\n");
349 print_declarations(file
, names
->nb_iterators
, names
->iterators
, 2);
353 static void print_callable_preamble(FILE *file
, CloogProgram
*program
,
354 CloogOptions
*options
)
357 CloogBlockList
*blocklist
;
359 CloogStatement
*statement
;
361 fprintf(file
, "extern void hash(int);\n\n");
365 for (blocklist
= program
->blocklist
; blocklist
; blocklist
= blocklist
->next
) {
366 block
= blocklist
->block
;
367 for (statement
= block
->statement
; statement
; statement
= statement
->next
) {
368 fprintf(file
, "#define S%d(", statement
->number
);
369 if (block
->depth
> 0) {
370 fprintf(file
, "%s", program
->names
->iterators
[0]);
371 for(j
= 1; j
< block
->depth
; j
++)
372 fprintf(file
, ",%s", program
->names
->iterators
[j
]);
374 fprintf(file
,") { hash(%d);", statement
->number
);
375 for(j
= 0; j
< block
->depth
; j
++)
376 fprintf(file
, " hash(%s);", program
->names
->iterators
[j
]);
377 fprintf(file
, " }\n");
380 fprintf(file
, "\nvoid test(");
381 if (program
->names
->nb_parameters
> 0) {
382 fprintf(file
, "int %s", program
->names
->parameters
[0]);
383 for(j
= 1; j
< program
->names
->nb_parameters
; j
++)
384 fprintf(file
, ", int %s", program
->names
->parameters
[j
]);
386 fprintf(file
, ")\n{\n");
387 print_iterator_declarations(file
, program
, options
);
390 static void print_callable_postamble(FILE *file
, CloogProgram
*program
)
392 fprintf(file
, "}\n");
396 static int get_osl_loop_flags (osl_scop_p scop
) {
398 osl_loop_p ll
= osl_generic_lookup(scop
->extension
, OSL_URI_LOOP
);
400 flags
|= ll
->directive
;
407 static void print_iterator_declarations_osl(FILE *file
, CloogProgram
*program
,
408 int indent
, CloogOptions
*options
)
410 osl_coordinates_p co
= NULL
;
413 char* vecvar
[2] = {"lbv", "ubv"};
414 char* parvar
[2] = {"lbp", "ubp"};
416 osl_scop_p scop
= options
->scop
;
417 CloogNames
*names
= program
->names
;
419 print_scattering_declarations(file
, program
, indent
);
421 co
= osl_generic_lookup(scop
->extension
, OSL_URI_COORDINATES
);
422 if (co
==NULL
//if coordinates exist then iterators already declared in file
423 && names
->nb_iterators
) {
424 for (i
= 0; i
< indent
; i
++)
426 fprintf(file
, "/* Original iterators. */\n");
427 print_declarations(file
, names
->nb_iterators
, names
->iterators
, indent
);
430 loopflags
= get_osl_loop_flags(scop
);
431 if(loopflags
& CLAST_PARALLEL_OMP
)
432 print_declarations(file
, 2, parvar
, indent
);
433 if(loopflags
& CLAST_PARALLEL_VEC
)
434 print_declarations(file
, 2, vecvar
, indent
);
440 * add tags clast loops according to information in scop's osl_loop extension
442 static int annotate_loops(osl_scop_p program
, struct clast_stmt
*root
){
444 int j
, nclastloops
, nclaststmts
;
445 struct clast_for
**clastloops
= NULL
;
446 int *claststmts
= NULL
;
449 if (program
== NULL
) {
453 osl_loop_p ll
= osl_generic_lookup(program
->extension
, OSL_URI_LOOP
);
456 osl_loop_p loop
= ll
;
457 ClastFilter filter
= { loop
->iter
, loop
->stmt_ids
,
458 loop
->nb_stmts
, subset
};
460 clast_filter(root
, filter
, &clastloops
, &nclastloops
,
461 &claststmts
, &nclaststmts
);
463 /* There should be at least one */
464 if (nclastloops
==0) { //FROM PLUTO
465 /* Sometimes loops may disappear (1) tile size larger than trip count
466 * 2) it's a scalar dimension but can't be determined from the
468 printf("Warning: parallel poly loop not found in AST\n");
472 for (j
=0; j
<nclastloops
; j
++) {
474 if (loop
->directive
& CLAST_PARALLEL_VEC
) {
475 clastloops
[j
]->parallel
|= CLAST_PARALLEL_VEC
;
476 ret
|= CLAST_PARALLEL_VEC
;
479 if (loop
->directive
& CLAST_PARALLEL_OMP
) {
480 clastloops
[j
]->parallel
|= CLAST_PARALLEL_OMP
;
481 ret
|= CLAST_PARALLEL_OMP
;
482 if (loop
->private_vars
) {
483 clastloops
[j
]->private_vars
= strdup(loop
->private_vars
);
488 if (clastloops
) { free(clastloops
); clastloops
=NULL
;}
489 if (claststmts
) { free(claststmts
); claststmts
=NULL
;}
499 * cloog_program_osl_pprint function:
500 * this function pretty-prints the C or FORTRAN code generated from an
501 * OpenScop specification by overwriting SCoP in a given code, if the
502 * options -compilable or -callable are not set. The SCoP coordinates are
503 * provided through the OpenScop "Coordinates" extension. It returns 1 if
504 * it succeeds to find an OpenScop coordinates information
505 * to pretty-print the generated code, 0 otherwise.
506 * \param[in] file The output stream (possibly stdout).
507 * \param[in] program The generated pseudo-AST to pretty-print.
508 * \param[in] options CLooG options (contains the OpenSCop specification).
509 * \return 1 on success to pretty-print at the place of a SCoP, 0 otherwise.
511 int cloog_program_osl_pprint(FILE * file
, CloogProgram
* program
,
512 CloogOptions
* options
) {
519 osl_scop_p scop
= options
->scop
;
520 osl_coordinates_p coordinates
;
521 struct clast_stmt
*root
;
522 FILE* original
= NULL
;
524 if (scop
&& !options
->compilable
&& !options
->callable
) {
526 print_comment(file
, options
, "Generated from %s by %s in %.2fs.",
527 options
->name
, cloog_version(), options
->time
);
529 print_comment(file
, options
, "Generated from %s by %s.",
530 options
->name
, cloog_version());
532 coordinates
= osl_generic_lookup(scop
->extension
, OSL_URI_COORDINATES
);
534 original
= fopen(coordinates
->name
, "r");
535 indentation
= coordinates
->indent
;
537 cloog_msg(options
, CLOOG_WARNING
,
538 "unable to open the file specified in the SCoP "
544 /* Print the macros the generated code may need. */
547 /* Print what was before the SCoP in the original file (if any). */
549 while (((lines
< coordinates
->line_start
- 1) ||
550 (columns
< coordinates
->column_start
- 1)) && (read
!= EOF
)) {
551 read
= fscanf(original
, "%c", &c
);
558 fprintf(file
, "%c", c
);
562 /* Carriage return to preserve indentation if necessary. */
563 if (coordinates
->column_start
> 0)
567 /* Generate the clast from the pseudo-AST then pretty-print it. */
568 root
= cloog_clast_create(program
, options
);
569 annotate_loops(options
->scop
, root
);
570 print_iterator_declarations_osl(file
, program
, indentation
, options
);
571 clast_pprint(file
, root
, indentation
, options
);
572 cloog_clast_free(root
);
574 /* Print what was after the SCoP in the original file (if any). */
576 while (read
!= EOF
) {
577 read
= fscanf(original
, "%c", &c
);
580 if (((lines
== coordinates
->line_end
- 1) &&
581 (columns
> coordinates
->column_end
)) ||
582 (lines
> coordinates
->line_end
- 1))
583 fprintf(file
, "%c", c
);
601 * cloog_program_pprint function:
602 * This function prints the content of a CloogProgram structure (program) into a
603 * file (file, possibly stdout), in a C-like language.
604 * - June 22nd 2005: Adaptation for GMP.
606 void cloog_program_pprint(file
, program
, options
)
608 CloogProgram
* program
;
609 CloogOptions
* options
;
611 int i
, j
, indentation
= 0;
612 CloogStatement
* statement
;
613 CloogBlockList
* blocklist
;
615 struct clast_stmt
*root
;
617 if (cloog_program_osl_pprint(file
, program
, options
))
620 if (program
->language
== 'f')
621 options
->language
= CLOOG_LANGUAGE_FORTRAN
;
623 options
->language
= CLOOG_LANGUAGE_C
;
626 print_comment(file
, options
, "Generated from %s by %s in %.2fs.",
627 options
->name
, cloog_version(), options
->time
);
629 print_comment(file
, options
, "Generated from %s by %s.",
630 options
->name
, cloog_version());
633 print_comment(file
, options
, "CLooG asked for %d KBytes.", options
->memory
);
634 cloog_msg(CLOOG_INFO
, "%.2fs and %dKB used for code generation.\n",
635 options
->time
,options
->memory
);
638 /* If the option "compilable" is set, we provide the whole stuff to generate
639 * a compilable code. This code just do nothing, but now the user can edit
640 * the source and set the statement macros and parameters values.
642 if (options
->compilable
&& (program
->language
== 'c'))
644 fprintf(file
,"/* DON'T FORGET TO USE -lm OPTION TO COMPILE. */\n\n") ;
645 fprintf(file
,"/* Useful headers. */\n") ;
646 fprintf(file
,"#include <stdio.h>\n") ;
647 fprintf(file
,"#include <stdlib.h>\n") ;
648 fprintf(file
,"#include <math.h>\n\n") ;
650 /* The value of parameters. */
651 fprintf(file
,"/* Parameter value. */\n") ;
652 for (i
= 1; i
<= program
->names
->nb_parameters
; i
++)
653 fprintf(file
, "#define PARVAL%d %d\n", i
, options
->compilable
);
658 /* The statement macros. */
659 fprintf(file
,"/* Statement macros (please set). */\n") ;
660 blocklist
= program
->blocklist
;
661 while (blocklist
!= NULL
)
662 { block
= blocklist
->block
;
663 statement
= block
->statement
;
664 while (statement
!= NULL
)
665 { fprintf(file
,"#define S%d(",statement
->number
) ;
666 if (block
->depth
> 0)
667 { fprintf(file
,"%s",program
->names
->iterators
[0]) ;
668 for(j
=1;j
<block
->depth
;j
++)
669 fprintf(file
,",%s",program
->names
->iterators
[j
]) ;
671 fprintf(file
,") {total++;") ;
672 if (block
->depth
> 0) {
673 fprintf(file
, " printf(\"S%d %%d", statement
->number
);
674 for(j
=1;j
<block
->depth
;j
++)
675 fprintf(file
, " %%d");
677 fprintf(file
,"\\n\",%s",program
->names
->iterators
[0]) ;
678 for(j
=1;j
<block
->depth
;j
++)
679 fprintf(file
,",%s",program
->names
->iterators
[j
]) ;
682 fprintf(file
,"}\n") ;
684 statement
= statement
->next
;
686 blocklist
= blocklist
->next
;
689 /* The iterator and parameter declaration. */
690 fprintf(file
,"\nint main() {\n") ;
691 print_iterator_declarations(file
, program
, options
);
692 if (program
->names
->nb_parameters
> 0)
693 { fprintf(file
," /* Parameters. */\n") ;
694 fprintf(file
, " int %s=PARVAL1",program
->names
->parameters
[0]);
695 for(i
=2;i
<=program
->names
->nb_parameters
;i
++)
696 fprintf(file
, ", %s=PARVAL%d", program
->names
->parameters
[i
-1], i
);
700 fprintf(file
," int total=0;\n");
703 /* And we adapt the identation. */
705 } else if (options
->callable
&& program
->language
== 'c') {
706 print_callable_preamble(file
, program
, options
);
710 root
= cloog_clast_create(program
, options
);
711 clast_pprint(file
, root
, indentation
, options
);
712 cloog_clast_free(root
);
714 /* The end of the compilable code in case of 'compilable' option. */
715 if (options
->compilable
&& (program
->language
== 'c'))
717 fprintf(file
, "\n printf(\"Number of integral points: %%d.\\n\",total);");
718 fprintf(file
, "\n return 0;\n}\n");
719 } else if (options
->callable
&& program
->language
== 'c')
720 print_callable_postamble(file
, program
);
724 /******************************************************************************
725 * Memory deallocation function *
726 ******************************************************************************/
730 * cloog_program_free function:
731 * This function frees the allocated memory for a CloogProgram structure.
733 void cloog_program_free(CloogProgram
* program
)
734 { cloog_names_free(program
->names
) ;
735 cloog_loop_free(program
->loop
) ;
736 cloog_domain_free(program
->context
) ;
737 cloog_block_list_free(program
->blocklist
) ;
738 if (program
->scaldims
!= NULL
)
739 free(program
->scaldims
) ;
745 /******************************************************************************
747 ******************************************************************************/
750 static void cloog_program_construct_block_list(CloogProgram
*p
)
753 CloogBlockList
**next
= &p
->blocklist
;
755 for (loop
= p
->loop
; loop
; loop
= loop
->next
) {
756 *next
= cloog_block_list_alloc(loop
->block
);
757 next
= &(*next
)->next
;
763 * Construct a CloogProgram structure from a given context and
764 * union domain representing the iteration domains and scattering functions.
766 CloogProgram
*cloog_program_alloc(CloogDomain
*context
, CloogUnionDomain
*ud
,
767 CloogOptions
*options
)
771 CloogScatteringList
* scatteringl
;
775 /* Memory allocation for the CloogProgram structure. */
776 p
= cloog_program_malloc() ;
778 if (options
->language
== CLOOG_LANGUAGE_FORTRAN
)
783 p
->names
= n
= cloog_names_alloc();
785 /* We then read the context data. */
786 p
->context
= context
;
787 n
->nb_parameters
= ud
->n_name
[CLOOG_PARAM
];
789 /* First part of the CloogNames structure: the parameter names. */
790 if (ud
->name
[CLOOG_PARAM
]) {
791 n
->parameters
= ud
->name
[CLOOG_PARAM
];
792 ud
->name
[CLOOG_PARAM
] = NULL
;
794 n
->parameters
= cloog_names_generate_items(n
->nb_parameters
, NULL
,
797 n
->nb_iterators
= ud
->n_name
[CLOOG_ITER
];
798 if (ud
->name
[CLOOG_ITER
]) {
799 n
->iterators
= ud
->name
[CLOOG_ITER
];
800 ud
->name
[CLOOG_ITER
] = NULL
;
802 n
->iterators
= cloog_names_generate_items(n
->nb_iterators
, NULL
,
806 CloogNamedDomainList
*l
;
807 CloogLoop
**next
= &p
->loop
;
808 CloogScatteringList
**next_scat
= &scatteringl
;
811 for (i
= 0, l
= ud
->domain
; l
; ++i
, l
= l
->next
) {
812 *next
= cloog_loop_from_domain(options
->state
, l
->domain
, i
);
814 (*next
)->block
->statement
->name
= l
->name
;
815 (*next
)->block
->statement
->usr
= l
->usr
;
819 *next_scat
= ALLOC(CloogScatteringList
);
820 (*next_scat
)->scatt
= l
->scattering
;
821 l
->scattering
= NULL
;
822 (*next_scat
)->next
= NULL
;
824 next_scat
= &(*next_scat
)->next
;
827 next
= &(*next
)->next
;
830 if (scatteringl
!= NULL
) {
831 p
->nb_scattdims
= cloog_scattering_dimension(scatteringl
->scatt
,
833 n
->nb_scattering
= p
->nb_scattdims
;
834 if (ud
->name
[CLOOG_SCAT
]) {
835 n
->scattering
= ud
->name
[CLOOG_SCAT
];
836 ud
->name
[CLOOG_SCAT
] = NULL
;
838 n
->scattering
= cloog_names_generate_items(n
->nb_scattering
, prefix
, -1);
840 /* The boolean array for scalar dimensions is created and set to 0. */
841 p
->scaldims
= (int *)malloc(p
->nb_scattdims
*(sizeof(int))) ;
842 if (p
->scaldims
== NULL
)
843 cloog_die("memory overflow.\n");
844 for (i
=0;i
<p
->nb_scattdims
;i
++)
847 /* We try to find blocks in the input problem to reduce complexity. */
848 if (!options
->noblocks
)
849 cloog_program_block(p
, scatteringl
, options
);
850 if (!options
->noscalars
)
851 cloog_program_extract_scalars(p
, scatteringl
, options
);
853 cloog_program_scatter(p
, scatteringl
, options
);
854 cloog_scattering_list_free(scatteringl
);
856 if (!options
->noblocks
)
857 p
->loop
= cloog_loop_block(p
->loop
, p
->scaldims
, p
->nb_scattdims
);
860 { p
->nb_scattdims
= 0 ;
864 cloog_names_scalarize(p
->names
,p
->nb_scattdims
,p
->scaldims
) ;
866 cloog_program_construct_block_list(p
);
870 p
->blocklist
= NULL
;
874 cloog_union_domain_free(ud
);
881 * cloog_program_read function:
882 * This function read the informations to put in a CloogProgram structure from
883 * a file (file, possibly stdin). It returns a pointer to a CloogProgram
884 * structure containing the read informations.
885 * - October 25th 2001: first version.
886 * - September 9th 2002: - the big reading function is now split in several
887 * functions (one per read data structure).
888 * - adaptation to the new file format with naming.
890 CloogProgram
*cloog_program_read(FILE *file
, CloogOptions
*options
)
895 input
= cloog_input_read(file
, options
);
896 p
= cloog_program_alloc(input
->context
, input
->ud
, options
);
903 /******************************************************************************
904 * Processing functions *
905 ******************************************************************************/
909 * cloog_program_malloc function:
910 * This function allocates the memory space for a CloogProgram structure and
911 * sets its fields with default values. Then it returns a pointer to the
913 * - November 21th 2005: first version.
915 CloogProgram
* cloog_program_malloc()
916 { CloogProgram
* program
;
918 /* Memory allocation for the CloogProgram structure. */
919 program
= (CloogProgram
*)malloc(sizeof(CloogProgram
)) ;
921 cloog_die("memory overflow.\n");
923 /* We set the various fields with default values. */
924 program
->language
= 'c' ;
925 program
->nb_scattdims
= 0 ;
926 program
->context
= NULL
;
927 program
->loop
= NULL
;
928 program
->names
= NULL
;
929 program
->blocklist
= NULL
;
930 program
->scaldims
= NULL
;
938 * cloog_program_generate function:
939 * This function calls the Quillere algorithm for loop scanning. (see the
940 * Quillere paper) and calls the loop simplification function.
941 * - depth is the loop depth we want to optimize (guard free as possible),
942 * the first loop depth is 1 and anegative value is the infinity depth.
943 * - sep_level is the level number where we want to start loop separation.
945 * - October 26th 2001: first version.
946 * - April 19th 2005: some basic fixes and memory usage feature.
947 * - April 29th 2005: (bug fix, bug found by DaeGon Kim) see case 2 below.
949 CloogProgram
* cloog_program_generate(program
, options
)
950 CloogProgram
* program
;
951 CloogOptions
* options
;
955 struct rusage start
, end
;
959 char status_path
[MAX_STRING_VAL
] ;
962 /* We initialize the memory need to 0. */
963 options
->memory
= 0 ;
966 if (options
->override
)
968 cloog_msg(options
, CLOOG_WARNING
,
969 "you are using -override option, be aware that the "
970 "generated\n code may be incorrect.\n") ;
973 { /* Playing with options may be dangerous, here are two possible issues :
974 * 1. Using -l option less than scattering dimension number may lead to
975 * an illegal target code (since the scattering is not respected), if
976 * it is the case, we set -l depth to the first acceptable value.
978 if ((program
->nb_scattdims
> options
->l
) && (options
->l
>= 0))
980 cloog_msg(options
, CLOOG_WARNING
,
981 "-l depth is less than the scattering dimension number "
982 "(the \n generated code may be incorrect), it has been "
983 "automaticaly set\n to this value (use option -override "
985 options
->l
= program
->nb_scattdims
;
988 /* 2. Using -f option greater than one while -l depth is greater than the
989 * scattering dimension number may lead to iteration duplication (try
990 * test/daegon_lu_osp.cloog with '-f 3' to test) because of the step 4b
991 * of the cloog_loop_generate function, if it is the case, we set -l to
992 * the first acceptable value.
994 if (((options
->f
> 1) || (options
->f
< 0)) &&
995 ((options
->l
> program
->nb_scattdims
) || (options
->l
< 0)))
997 cloog_msg(options
, CLOOG_WARNING
,
998 "-f depth is more than one, -l depth has been "
999 "automaticaly set\n to the scattering dimension number "
1000 "(target code may have\n duplicated iterations), -l depth "
1001 "has been automaticaly set to\n this value (use option "
1002 "-override to override).\n") ;
1003 options
->l
= program
->nb_scattdims
;
1008 getrusage(RUSAGE_SELF
, &start
) ;
1010 if (program
->loop
!= NULL
)
1011 { loop
= program
->loop
;
1014 loop
= cloog_loop_generate(loop
, program
->context
, 0, 0,
1016 program
->nb_scattdims
,
1020 /* We read into the status file of the process how many memory it uses. */
1021 sprintf(status_path
,"/proc/%d/status",getpid()) ;
1022 status
= fopen(status_path
, "r") ;
1023 while (fscanf(status
,"%s",status_path
) && strcmp(status_path
,"VmData:")!=0);
1024 fscanf(status
,"%d",&(options
->memory
)) ;
1028 if ((!options
->nosimplify
) && (program
->loop
!= NULL
))
1029 loop
= cloog_loop_simplify(loop
, program
->context
, 0,
1030 program
->nb_scattdims
, options
);
1032 program
->loop
= loop
;
1036 getrusage(RUSAGE_SELF
, &end
) ;
1037 /* We calculate the time spent in code generation. */
1038 time
= (end
.ru_utime
.tv_usec
- start
.ru_utime
.tv_usec
)/(float)(MEGA
) ;
1039 time
+= (float)(end
.ru_utime
.tv_sec
- start
.ru_utime
.tv_sec
) ;
1040 options
->time
= time
;
1048 * cloog_program_block function:
1049 * this function gives a last chance to the lazy user to consider statement
1050 * blocks instead of some statement lists where the whole list may be
1051 * considered as a single statement from a code generation point of view.
1052 * For instance two statements with the same iteration domain and the same
1053 * scattering functions may be considered as a block. This function is lazy
1054 * and can only find very simple forms of trivial blocks (see
1055 * cloog_domain_lazy_block function for more details). The useless loops and
1056 * scattering functions are removed and freed while the statement list of
1057 * according blocks are filled.
1058 * - program is the whole program structure (befaore applying scattering),
1059 * - scattering is the list of scattering functions.
1061 * - April 30th 2005: first attempt.
1062 * - June 10-11th 2005: first working version.
1064 void cloog_program_block(CloogProgram
*program
,
1065 CloogScatteringList
*scattering
, CloogOptions
*options
)
1066 { int blocked_reference
=0, blocked
=0, nb_blocked
=0 ;
1067 CloogLoop
* reference
, * start
, * loop
;
1068 CloogScatteringList
* scatt_reference
, * scatt_loop
, * scatt_start
;
1070 if ((program
->loop
== NULL
) || (program
->loop
->next
== NULL
))
1073 /* The process will use three variables for the linked list :
1074 * - 'start' is the starting point of a new block,
1075 * - 'reference' is the node of the block used for the block checking,
1076 * - 'loop' is the candidate to be inserted inside the block.
1077 * At the beginning of the process, the linked lists are as follow:
1078 * O------>O------>O------>O------>NULL
1084 reference
= program
->loop
;
1085 start
= program
->loop
;
1086 loop
= reference
->next
;
1087 scatt_reference
= scattering
;
1088 scatt_start
= scattering
;
1089 scatt_loop
= scattering
->next
;
1091 while (loop
!= NULL
)
1092 { if (cloog_domain_lazy_equal(reference
->domain
,loop
->domain
) &&
1093 cloog_scattering_lazy_block(scatt_reference
->scatt
, scatt_loop
->scatt
,
1094 scattering
,program
->nb_scattdims
))
1095 { /* If we find a block we update the links:
1098 * O O------>O------>O------>NULL
1105 cloog_block_merge(start
->block
,loop
->block
); /* merge frees loop->block */
1106 loop
->block
= NULL
;
1107 start
->next
= loop
->next
;
1108 scatt_start
->next
= scatt_loop
->next
;
1111 { /* If we didn't find a block, the next start of a block is updated:
1112 * O------>O------>O------>O------>NULL
1119 scatt_start
= scatt_loop
;
1122 /* If the reference node has been included into a block, we can free it. */
1123 if (blocked_reference
)
1124 { reference
->next
= NULL
;
1125 cloog_loop_free(reference
) ;
1126 cloog_scattering_free(scatt_reference
->scatt
);
1127 free(scatt_reference
) ;
1130 /* The reference and the loop are now updated for the next try, the
1131 * starting position depends on the previous step.
1132 * O ? O------>O------>O------>NULL
1138 scatt_reference
= scatt_loop
;
1139 scatt_loop
= scatt_loop
->next
;
1141 /* We mark the new reference as being blocked or not, if will be freed
1142 * during the next while loop execution.
1145 blocked_reference
= 1 ;
1147 blocked_reference
= 0 ;
1150 /* We free the last blocked reference if any (since in the while loop it was
1151 * freed during the next loop execution, it was not possible to free the
1154 if (blocked_reference
)
1155 { reference
->next
= NULL
;
1156 cloog_loop_free(reference
) ;
1157 cloog_scattering_free(scatt_reference
->scatt
);
1158 free(scatt_reference
) ;
1161 if (nb_blocked
!= 0)
1162 cloog_msg(options
, CLOOG_INFO
, "%d domains have been blocked.\n", nb_blocked
);
1167 * cloog_program_extract_scalars function:
1168 * this functions finds and removes the dimensions of the scattering functions
1169 * when they are scalar (i.e. of the shape "dim + scalar = 0") for all
1170 * scattering functions. The reason is that the processing of such dimensions
1171 * is trivial and do not need neither a row and a column in the matrix
1172 * representation of the domain (this will save memory) neither the full
1173 * Quillere processing (this will save time). The scalar dimensions data are
1174 * dispatched in the CloogProgram structure (the boolean vector scaldims will
1175 * say which original dimensions are scalar or not) and to the CloogBlock
1176 * structures (each one has a scaldims vector that contains the scalar values).
1177 * - June 14th 2005: first developments.
1178 * - June 30th 2005: first version.
1180 void cloog_program_extract_scalars(CloogProgram
*program
,
1181 CloogScatteringList
*scattering
, CloogOptions
*options
)
1182 { int i
, j
, scalar
, current
, nb_scaldims
=0 ;
1183 CloogScatteringList
*start
;
1184 CloogScattering
*old
;
1186 CloogBlock
* block
;
1188 start
= scattering
;
1190 for (i
=0;i
<program
->nb_scattdims
;i
++)
1192 scattering
= start
;
1193 while (scattering
!= NULL
)
1194 { if (!cloog_scattering_lazy_isscalar(scattering
->scatt
, i
, NULL
))
1198 scattering
= scattering
->next
;
1203 program
->scaldims
[i
] = 1 ;
1207 /* If there are no scalar dimensions, we can continue directly. */
1211 /* Otherwise, in each block, we have to put the number of scalar dimensions,
1212 * and to allocate the memory for the scalar values.
1214 for (loop
= program
->loop
; loop
; loop
= loop
->next
) {
1215 block
= loop
->block
;
1216 block
->nb_scaldims
= nb_scaldims
;
1217 block
->scaldims
= (cloog_int_t
*)malloc(nb_scaldims
*sizeof(cloog_int_t
));
1218 for (i
=0;i
<nb_scaldims
;i
++)
1219 cloog_int_init(block
->scaldims
[i
]);
1222 /* Then we have to fill these scalar values, so we can erase those dimensions
1223 * from the scattering functions. It's easier to begin with the last one,
1224 * since there would be an offset otherwise (if we remove the i^th dimension,
1225 * then the next one is not the (i+1)^th but still the i^th...).
1227 current
= nb_scaldims
- 1 ;
1228 for (i
=program
->nb_scattdims
-1;i
>=0;i
--)
1229 if (program
->scaldims
[i
])
1231 scattering
= start
;
1232 for (loop
= program
->loop
; loop
; loop
= loop
->next
) {
1233 block
= loop
->block
;
1234 if (!cloog_scattering_lazy_isscalar(scattering
->scatt
, i
,
1235 &block
->scaldims
[current
])) {
1236 /* We should have found a scalar value: if not, there is an error. */
1237 cloog_die("dimension %d is not scalar as expected.\n", i
);
1239 scattering
= scattering
->next
;
1242 scattering
= start
;
1243 while (scattering
!= NULL
) {
1244 old
= scattering
->scatt
;
1245 scattering
->scatt
= cloog_scattering_erase_dimension(old
, i
);
1246 cloog_scattering_free(old
);
1247 scattering
= scattering
->next
;
1252 /* We postprocess the scaldims array in such a way that each entry is how
1253 * many scalar dimensions follows + 1 (the current one). This will make
1254 * some other processing easier (e.g. knowledge of some offsets).
1256 for (i
=0;i
<program
->nb_scattdims
-1;i
++)
1257 { if (program
->scaldims
[i
])
1259 while ((j
< program
->nb_scattdims
) && program
->scaldims
[j
])
1260 { program
->scaldims
[i
] ++ ;
1266 if (nb_scaldims
!= 0)
1267 cloog_msg(options
, CLOOG_INFO
, "%d dimensions (over %d) are scalar.\n",
1268 nb_scaldims
,program
->nb_scattdims
) ;
1273 * cloog_program_scatter function:
1274 * This function adds the scattering (scheduling) informations in a program.
1275 * If names is NULL, this function create names itself such that the i^th
1277 * - November 6th 2001: first version.
1279 void cloog_program_scatter(CloogProgram
*program
,
1280 CloogScatteringList
*scattering
, CloogOptions
*options
)
1281 { int scattering_dim
, scattering_dim2
, not_enough_constraints
=0 ;
1284 if ((program
!= NULL
) && (scattering
!= NULL
))
1285 { loop
= program
->loop
;
1287 /* We compute the scattering dimension and check it is >=0. */
1288 scattering_dim
= cloog_scattering_dimension(scattering
->scatt
, loop
->domain
);
1289 if (scattering_dim
< 0)
1290 cloog_die("scattering has not enough dimensions.\n");
1291 if (!cloog_scattering_fully_specified(scattering
->scatt
, loop
->domain
))
1292 not_enough_constraints
++ ;
1294 /* The scattering dimension may have been modified by scalar extraction. */
1295 scattering_dim
= cloog_scattering_dimension(scattering
->scatt
, loop
->domain
);
1297 /* Finally we scatter all loops. */
1298 cloog_loop_scatter(loop
, scattering
->scatt
);
1300 scattering
= scattering
->next
;
1302 while ((loop
!= NULL
) && (scattering
!= NULL
))
1303 { scattering_dim2
= cloog_scattering_dimension(scattering
->scatt
,
1305 if (scattering_dim2
!= scattering_dim
)
1306 cloog_die("scattering dimensions are not the same.\n") ;
1307 if (!cloog_scattering_fully_specified(scattering
->scatt
, loop
->domain
))
1308 not_enough_constraints
++ ;
1310 cloog_loop_scatter(loop
, scattering
->scatt
);
1312 scattering
= scattering
->next
;
1314 if ((loop
!= NULL
) || (scattering
!= NULL
))
1315 cloog_msg(options
, CLOOG_WARNING
,
1316 "there is not a scattering for each statement.\n");
1318 if (not_enough_constraints
)
1319 cloog_msg(options
, CLOOG_WARNING
, "not enough constraints for "
1320 "%d scattering function(s).\n",not_enough_constraints
) ;