Prevent iterator redefinition
[cloog.git] / source / program.c
blob9606de28c7b62d8fb4432b8d6cf466225a215c66
2 /**-------------------------------------------------------------------**
3 ** CLooG **
4 **-------------------------------------------------------------------**
5 ** program.c **
6 **-------------------------------------------------------------------**
7 ** First version: october 25th 2001 **
8 **-------------------------------------------------------------------**/
11 /******************************************************************************
12 * CLooG : the Chunky Loop Generator (experimental) *
13 ******************************************************************************
14 * *
15 * Copyright (C) 2001-2005 Cedric Bastoul *
16 * *
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. *
21 * *
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. *
26 * *
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 *
31 * *
32 * CLooG, the Chunky Loop Generator *
33 * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr *
34 * *
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>
43 #include <stdarg.h>
44 # include <stdlib.h>
45 # include <stdio.h>
46 # include <string.h>
47 # include <ctype.h>
48 # include <unistd.h>
49 # include "../include/cloog/cloog.h"
50 #ifdef CLOOG_RUSAGE
51 # include <sys/resource.h>
52 #endif
54 #define ALLOC(type) (type*)malloc(sizeof(type))
56 #ifdef OSL_SUPPORT
57 #include <osl/scop.h>
58 #include <osl/extensions/coordinates.h>
59 #include <osl/extensions/loop.h>
60 #endif
62 /******************************************************************************
63 * Structure display function *
64 ******************************************************************************/
67 /**
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)
75 FILE * file ;
76 CloogProgram * program ;
77 int level ;
78 { int i, j ;
80 /* Go to the right level. */
81 for (i=0; i<level; i++)
82 fprintf(file,"|\t") ;
84 fprintf(file,"+-- CloogProgram\n") ;
86 /* A blank line. */
87 for (i=0; i<=level+1; i++)
88 fprintf(file,"|\t") ;
89 fprintf(file,"\n") ;
91 /* Print the language. */
92 for (i=0; i<=level; i++)
93 fprintf(file,"|\t") ;
94 fprintf(file, "Language: %c\n",program->language) ;
96 /* A blank line. */
97 for (i=0; i<=level+1; i++)
98 fprintf(file,"|\t") ;
99 fprintf(file,"\n") ;
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) ;
106 /* A blank line. */
107 for (i=0; i<=level+1; i++)
108 fprintf(file,"|\t") ;
109 fprintf(file,"\n") ;
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]) ;
118 fprintf(file,"\n") ;
120 else
121 fprintf(file,"No scalar scattering dimensions\n") ;
123 /* A blank line. */
124 for (i=0; i<=level+1; i++)
125 fprintf(file,"|\t") ;
126 fprintf(file,"\n") ;
128 /* Print the parameter and the iterator names. */
129 cloog_names_print_structure(file,program->names,level+1) ;
131 /* A blank line. */
132 for (i=0; i<=level+1; i++)
133 fprintf(file,"|\t") ;
134 fprintf(file,"\n") ;
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. */
143 for (j=0; j<2; j++)
144 { for (i=0; i<=level; i++)
145 fprintf(file,"|\t") ;
147 fprintf(file,"\n") ;
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)
169 int i;
170 CloogLoop * loop ;
171 CloogScatteringList *tmp_scatt;
173 fprintf(foo,
174 "# CLooG -> CLooG\n"
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") ;
182 /* Language. */
183 if (program->language == 'c')
184 fprintf(foo,"# Language: C\n") ;
185 else
186 fprintf(foo,"# Language: FORTRAN\n") ;
187 fprintf(foo,"%c\n\n",program->language) ;
189 /* Context. */
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. */
197 i = 0 ;
198 loop = program->loop ;
199 while (loop != NULL)
200 { i++ ;
201 loop = loop->next ;
203 fprintf(foo,"\n\n# Statement number:\n%d\n\n",i) ;
205 /* Iteration domains. */
206 i = 1 ;
207 loop = program->loop ;
208 while (loop != NULL)
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") ;
215 i++ ;
216 loop = loop->next ;
218 fprintf(foo,"\n1 # Iterator name(s)\n") ;
220 /* Scattering already applied? In this case print the scattering names as
221 * additional iterator names. */
222 if (!scattering)
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. */
230 if (!scattering) {
231 fprintf(foo, "# No scattering functions.\n0\n\n");
232 return;
235 /* Scattering relations. */
236 fprintf(foo, "# --------------------- SCATTERING --------------------\n");
238 i = 0;
239 for (tmp_scatt = scattering; tmp_scatt; tmp_scatt = tmp_scatt->next)
240 i++;
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, ...)
270 va_list args;
272 va_start(args, fmt);
273 if (options->language == CLOOG_LANGUAGE_FORTRAN) {
274 fprintf(file, "! ");
275 vfprintf(file, fmt, args);
276 fprintf(file, "\n");
277 } else {
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") ;
287 fprintf(file,
288 "#define floord(n,d) (((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))\n");
289 fprintf(file,
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)
299 int i;
301 for (i = 0; i < indentation; i++)
302 fprintf(file, " ");
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,
310 int indentation)
312 int i, j, found;
313 int nb_scatnames = 0;
314 CloogNames *names = program->names;
316 // Copy pointer only to those scatering names that do not duplicate
317 // iterator names.
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) {
321 found = 0;
322 if (strcmp(names->scattering[i], names->iterators[j]) == 0) {
323 found = 1;
326 if (!found) {
327 // Save a pointer (intentional!) to the names in the new array.
328 scatnames[nb_scatnames++] = names->scattering[i];
332 if (nb_scatnames) {
333 for (i = 0; i < indentation; i++)
334 fprintf(file, " ");
335 fprintf(file, "/* Scattering iterators. */\n");
336 print_declarations(file, nb_scatnames, scatnames, indentation);
340 static void print_iterator_declarations(FILE *file, CloogProgram *program,
341 CloogOptions *options)
343 CloogNames *names = program->names;
345 print_scattering_declarations(file, program, 2);
346 if (names->nb_iterators) {
347 fprintf(file, " /* Original iterators. */\n");
348 print_declarations(file, names->nb_iterators, names->iterators, 2);
352 static void print_callable_preamble(FILE *file, CloogProgram *program,
353 CloogOptions *options)
355 int j;
356 CloogBlockList *blocklist;
357 CloogBlock *block;
358 CloogStatement *statement;
360 fprintf(file, "extern void hash(int);\n\n");
362 print_macros(file);
364 for (blocklist = program->blocklist; blocklist; blocklist = blocklist->next) {
365 block = blocklist->block;
366 for (statement = block->statement; statement; statement = statement->next) {
367 fprintf(file, "#define S%d(", statement->number);
368 if (block->depth > 0) {
369 fprintf(file, "%s", program->names->iterators[0]);
370 for(j = 1; j < block->depth; j++)
371 fprintf(file, ",%s", program->names->iterators[j]);
373 fprintf(file,") { hash(%d);", statement->number);
374 for(j = 0; j < block->depth; j++)
375 fprintf(file, " hash(%s);", program->names->iterators[j]);
376 fprintf(file, " }\n");
379 fprintf(file, "\nvoid test(");
380 if (program->names->nb_parameters > 0) {
381 fprintf(file, "int %s", program->names->parameters[0]);
382 for(j = 1; j < program->names->nb_parameters; j++)
383 fprintf(file, ", int %s", program->names->parameters[j]);
385 fprintf(file, ")\n{\n");
386 print_iterator_declarations(file, program, options);
389 static void print_callable_postamble(FILE *file, CloogProgram *program)
391 fprintf(file, "}\n");
394 #ifdef OSL_SUPPORT
395 static int get_osl_loop_flags (osl_scop_p scop) {
396 int flags = 0;
397 osl_loop_p ll = osl_generic_lookup(scop->extension, OSL_URI_LOOP);
398 while (ll) {
399 flags |= ll->directive;
400 ll = ll->next;
403 return flags;
406 static void print_iterator_declarations_osl(FILE *file, CloogProgram *program,
407 int indent, CloogOptions *options)
409 osl_coordinates_p co = NULL;
410 int i;
411 int loopflags = 0;
412 char* vecvar[2] = {"lbv", "ubv"};
413 char* parvar[2] = {"lbp", "ubp"};
415 osl_scop_p scop = options->scop;
416 CloogNames *names = program->names;
418 print_scattering_declarations(file, program, indent);
420 co = osl_generic_lookup(scop->extension, OSL_URI_COORDINATES);
421 if (co==NULL //if coordinates exist then iterators already declared in file
422 && names->nb_iterators) {
423 for (i = 0; i < indent; i++)
424 fprintf(file, " ");
425 fprintf(file, "/* Original iterators. */\n");
426 print_declarations(file, names->nb_iterators, names->iterators, indent);
429 loopflags = get_osl_loop_flags(scop);
430 if(loopflags & CLAST_PARALLEL_OMP)
431 print_declarations(file, 2, parvar, indent);
432 if(loopflags & CLAST_PARALLEL_VEC)
433 print_declarations(file, 2, vecvar, indent);
435 fprintf(file, "\n");
439 * add tags clast loops according to information in scop's osl_loop extension
441 static int annotate_loops(osl_scop_p program, struct clast_stmt *root){
443 int j, nclastloops, nclaststmts;
444 struct clast_for **clastloops = NULL;
445 int *claststmts = NULL;
446 int ret = 0;
448 if (program == NULL) {
449 return ret;
452 osl_loop_p ll = osl_generic_lookup(program->extension, OSL_URI_LOOP);
453 while (ll) {
454 //for each loop
455 osl_loop_p loop = ll;
456 ClastFilter filter = { loop->iter, loop->stmt_ids,
457 loop->nb_stmts, subset};
459 clast_filter(root, filter, &clastloops, &nclastloops,
460 &claststmts, &nclaststmts);
462 /* There should be at least one */
463 if (nclastloops==0) { //FROM PLUTO
464 /* Sometimes loops may disappear (1) tile size larger than trip count
465 * 2) it's a scalar dimension but can't be determined from the
466 * trans matrix */
467 printf("Warning: parallel poly loop not found in AST\n");
468 ll = ll->next;
469 continue;
471 for (j=0; j<nclastloops; j++) {
473 if (loop->directive & CLAST_PARALLEL_VEC) {
474 clastloops[j]->parallel |= CLAST_PARALLEL_VEC;
475 ret |= CLAST_PARALLEL_VEC;
478 if (loop->directive & CLAST_PARALLEL_OMP) {
479 clastloops[j]->parallel |= CLAST_PARALLEL_OMP;
480 ret |= CLAST_PARALLEL_OMP;
481 clastloops[j]->private_vars = strdup(loop->private_vars);
485 if (clastloops) { free(clastloops); clastloops=NULL;}
486 if (claststmts) { free(claststmts); claststmts=NULL;}
488 ll = ll->next;
491 return ret;
493 #endif
496 * cloog_program_osl_pprint function:
497 * this function pretty-prints the C or FORTRAN code generated from an
498 * OpenScop specification by overwriting SCoP in a given code, if the
499 * options -compilable or -callable are not set. The SCoP coordinates are
500 * provided through the OpenScop "Coordinates" extension. It returns 1 if
501 * it succeeds to find an OpenScop coordinates information
502 * to pretty-print the generated code, 0 otherwise.
503 * \param[in] file The output stream (possibly stdout).
504 * \param[in] program The generated pseudo-AST to pretty-print.
505 * \param[in] options CLooG options (contains the OpenSCop specification).
506 * \return 1 on success to pretty-print at the place of a SCoP, 0 otherwise.
508 int cloog_program_osl_pprint(FILE * file, CloogProgram * program,
509 CloogOptions * options) {
510 #ifdef OSL_SUPPORT
511 int lines = 0;
512 int columns = 0;
513 int read = 1;
514 int indentation = 0;
515 char c;
516 osl_scop_p scop = options->scop;
517 osl_coordinates_p coordinates;
518 struct clast_stmt *root;
519 FILE* original = NULL;
521 if (scop && !options->compilable && !options->callable) {
522 #ifdef CLOOG_RUSAGE
523 print_comment(file, options, "Generated from %s by %s in %.2fs.",
524 options->name, cloog_version(), options->time);
525 #else
526 print_comment(file, options, "Generated from %s by %s.",
527 options->name, cloog_version());
528 #endif
529 coordinates = osl_generic_lookup(scop->extension, OSL_URI_COORDINATES);
530 if (coordinates) {
531 original = fopen(coordinates->name, "r");
532 indentation = coordinates->indent;
533 if (!original) {
534 cloog_msg(options, CLOOG_WARNING,
535 "unable to open the file specified in the SCoP "
536 "coordinates\n");
537 coordinates = NULL;
541 /* Print the macros the generated code may need. */
542 print_macros(file);
544 /* Print what was before the SCoP in the original file (if any). */
545 if (coordinates) {
546 while (((lines < coordinates->line_start - 1) ||
547 (columns < coordinates->column_start - 1)) && (read != EOF)) {
548 read = fscanf(original, "%c", &c);
549 columns++;
550 if (read != EOF) {
551 if (c == '\n') {
552 lines++;
553 columns = 0;
555 fprintf(file, "%c", c);
559 /* Carriage return to preserve indentation if necessary. */
560 if (coordinates->column_start > 0)
561 fprintf(file, "\n");
564 /* Generate the clast from the pseudo-AST then pretty-print it. */
565 root = cloog_clast_create(program, options);
566 annotate_loops(options->scop, root);
567 print_iterator_declarations_osl(file, program, indentation, options);
568 clast_pprint(file, root, indentation, options);
569 cloog_clast_free(root);
571 /* Print what was after the SCoP in the original file (if any). */
572 if (coordinates) {
573 while (read != EOF) {
574 read = fscanf(original, "%c", &c);
575 columns++;
576 if (read != EOF) {
577 if (((lines == coordinates->line_end - 1) &&
578 (columns > coordinates->column_end)) ||
579 (lines > coordinates->line_end - 1))
580 fprintf(file, "%c", c);
581 if (c == '\n') {
582 lines++;
583 columns = 0;
588 fclose(original);
591 return 1;
593 #endif
594 return 0;
598 * cloog_program_pprint function:
599 * This function prints the content of a CloogProgram structure (program) into a
600 * file (file, possibly stdout), in a C-like language.
601 * - June 22nd 2005: Adaptation for GMP.
603 void cloog_program_pprint(file, program, options)
604 FILE * file ;
605 CloogProgram * program ;
606 CloogOptions * options ;
608 int i, j, indentation = 0;
609 CloogStatement * statement ;
610 CloogBlockList * blocklist ;
611 CloogBlock * block ;
612 struct clast_stmt *root;
614 if (cloog_program_osl_pprint(file, program, options))
615 return;
617 if (program->language == 'f')
618 options->language = CLOOG_LANGUAGE_FORTRAN ;
619 else
620 options->language = CLOOG_LANGUAGE_C ;
622 #ifdef CLOOG_RUSAGE
623 print_comment(file, options, "Generated from %s by %s in %.2fs.",
624 options->name, cloog_version(), options->time);
625 #else
626 print_comment(file, options, "Generated from %s by %s.",
627 options->name, cloog_version());
628 #endif
629 #ifdef CLOOG_MEMORY
630 print_comment(file, options, "CLooG asked for %d KBytes.", options->memory);
631 cloog_msg(CLOOG_INFO, "%.2fs and %dKB used for code generation.\n",
632 options->time,options->memory);
633 #endif
635 /* If the option "compilable" is set, we provide the whole stuff to generate
636 * a compilable code. This code just do nothing, but now the user can edit
637 * the source and set the statement macros and parameters values.
639 if (options->compilable && (program->language == 'c'))
640 { /* The headers. */
641 fprintf(file,"/* DON'T FORGET TO USE -lm OPTION TO COMPILE. */\n\n") ;
642 fprintf(file,"/* Useful headers. */\n") ;
643 fprintf(file,"#include <stdio.h>\n") ;
644 fprintf(file,"#include <stdlib.h>\n") ;
645 fprintf(file,"#include <math.h>\n\n") ;
647 /* The value of parameters. */
648 fprintf(file,"/* Parameter value. */\n") ;
649 for (i = 1; i <= program->names->nb_parameters; i++)
650 fprintf(file, "#define PARVAL%d %d\n", i, options->compilable);
652 /* The macros. */
653 print_macros(file);
655 /* The statement macros. */
656 fprintf(file,"/* Statement macros (please set). */\n") ;
657 blocklist = program->blocklist ;
658 while (blocklist != NULL)
659 { block = blocklist->block ;
660 statement = block->statement ;
661 while (statement != NULL)
662 { fprintf(file,"#define S%d(",statement->number) ;
663 if (block->depth > 0)
664 { fprintf(file,"%s",program->names->iterators[0]) ;
665 for(j=1;j<block->depth;j++)
666 fprintf(file,",%s",program->names->iterators[j]) ;
668 fprintf(file,") {total++;") ;
669 if (block->depth > 0) {
670 fprintf(file, " printf(\"S%d %%d", statement->number);
671 for(j=1;j<block->depth;j++)
672 fprintf(file, " %%d");
674 fprintf(file,"\\n\",%s",program->names->iterators[0]) ;
675 for(j=1;j<block->depth;j++)
676 fprintf(file,",%s",program->names->iterators[j]) ;
677 fprintf(file,");") ;
679 fprintf(file,"}\n") ;
681 statement = statement->next ;
683 blocklist = blocklist->next ;
686 /* The iterator and parameter declaration. */
687 fprintf(file,"\nint main() {\n") ;
688 print_iterator_declarations(file, program, options);
689 if (program->names->nb_parameters > 0)
690 { fprintf(file," /* Parameters. */\n") ;
691 fprintf(file, " int %s=PARVAL1",program->names->parameters[0]);
692 for(i=2;i<=program->names->nb_parameters;i++)
693 fprintf(file, ", %s=PARVAL%d", program->names->parameters[i-1], i);
695 fprintf(file,";\n");
697 fprintf(file," int total=0;\n");
698 fprintf(file,"\n") ;
700 /* And we adapt the identation. */
701 indentation += 2 ;
702 } else if (options->callable && program->language == 'c') {
703 print_callable_preamble(file, program, options);
704 indentation += 2;
707 root = cloog_clast_create(program, options);
708 clast_pprint(file, root, indentation, options);
709 cloog_clast_free(root);
711 /* The end of the compilable code in case of 'compilable' option. */
712 if (options->compilable && (program->language == 'c'))
714 fprintf(file, "\n printf(\"Number of integral points: %%d.\\n\",total);");
715 fprintf(file, "\n return 0;\n}\n");
716 } else if (options->callable && program->language == 'c')
717 print_callable_postamble(file, program);
721 /******************************************************************************
722 * Memory deallocation function *
723 ******************************************************************************/
727 * cloog_program_free function:
728 * This function frees the allocated memory for a CloogProgram structure.
730 void cloog_program_free(CloogProgram * program)
731 { cloog_names_free(program->names) ;
732 cloog_loop_free(program->loop) ;
733 cloog_domain_free(program->context) ;
734 cloog_block_list_free(program->blocklist) ;
735 if (program->scaldims != NULL)
736 free(program->scaldims) ;
738 free(program) ;
742 /******************************************************************************
743 * Reading function *
744 ******************************************************************************/
747 static void cloog_program_construct_block_list(CloogProgram *p)
749 CloogLoop *loop;
750 CloogBlockList **next = &p->blocklist;
752 for (loop = p->loop; loop; loop = loop->next) {
753 *next = cloog_block_list_alloc(loop->block);
754 next = &(*next)->next;
760 * Construct a CloogProgram structure from a given context and
761 * union domain representing the iteration domains and scattering functions.
763 CloogProgram *cloog_program_alloc(CloogDomain *context, CloogUnionDomain *ud,
764 CloogOptions *options)
766 int i;
767 char prefix[] = "c";
768 CloogScatteringList * scatteringl;
769 CloogNames *n;
770 CloogProgram * p ;
772 /* Memory allocation for the CloogProgram structure. */
773 p = cloog_program_malloc() ;
775 if (options->language == CLOOG_LANGUAGE_FORTRAN)
776 p->language = 'f';
777 else
778 p->language = 'c';
780 p->names = n = cloog_names_alloc();
782 /* We then read the context data. */
783 p->context = context;
784 n->nb_parameters = ud->n_name[CLOOG_PARAM];
786 /* First part of the CloogNames structure: the parameter names. */
787 if (ud->name[CLOOG_PARAM]) {
788 n->parameters = ud->name[CLOOG_PARAM];
789 ud->name[CLOOG_PARAM] = NULL;
790 } else
791 n->parameters = cloog_names_generate_items(n->nb_parameters, NULL,
792 FIRST_PARAMETER);
794 n->nb_iterators = ud->n_name[CLOOG_ITER];
795 if (ud->name[CLOOG_ITER]) {
796 n->iterators = ud->name[CLOOG_ITER];
797 ud->name[CLOOG_ITER] = NULL;
798 } else
799 n->iterators = cloog_names_generate_items(n->nb_iterators, NULL,
800 FIRST_ITERATOR);
802 if (ud->domain) {
803 CloogNamedDomainList *l;
804 CloogLoop **next = &p->loop;
805 CloogScatteringList **next_scat = &scatteringl;
807 scatteringl = NULL;
808 for (i = 0, l = ud->domain; l; ++i, l = l->next) {
809 *next = cloog_loop_from_domain(options->state, l->domain, i);
810 l->domain = NULL;
811 (*next)->block->statement->name = l->name;
812 (*next)->block->statement->usr = l->usr;
813 l->name = NULL;
815 if (l->scattering) {
816 *next_scat = ALLOC(CloogScatteringList);
817 (*next_scat)->scatt = l->scattering;
818 l->scattering = NULL;
819 (*next_scat)->next = NULL;
821 next_scat = &(*next_scat)->next;
824 next = &(*next)->next;
827 if (scatteringl != NULL) {
828 p->nb_scattdims = cloog_scattering_dimension(scatteringl->scatt,
829 p->loop->domain);
830 n->nb_scattering = p->nb_scattdims;
831 if (ud->name[CLOOG_SCAT]) {
832 n->scattering = ud->name[CLOOG_SCAT];
833 ud->name[CLOOG_SCAT] = NULL;
834 } else
835 n->scattering = cloog_names_generate_items(n->nb_scattering, prefix, -1);
837 /* The boolean array for scalar dimensions is created and set to 0. */
838 p->scaldims = (int *)malloc(p->nb_scattdims*(sizeof(int))) ;
839 if (p->scaldims == NULL)
840 cloog_die("memory overflow.\n");
841 for (i=0;i<p->nb_scattdims;i++)
842 p->scaldims[i] = 0 ;
844 /* We try to find blocks in the input problem to reduce complexity. */
845 if (!options->noblocks)
846 cloog_program_block(p, scatteringl, options);
847 if (!options->noscalars)
848 cloog_program_extract_scalars(p, scatteringl, options);
850 cloog_program_scatter(p, scatteringl, options);
851 cloog_scattering_list_free(scatteringl);
853 if (!options->noblocks)
854 p->loop = cloog_loop_block(p->loop, p->scaldims, p->nb_scattdims);
856 else
857 { p->nb_scattdims = 0 ;
858 p->scaldims = NULL ;
861 cloog_names_scalarize(p->names,p->nb_scattdims,p->scaldims) ;
863 cloog_program_construct_block_list(p);
865 else
866 { p->loop = NULL ;
867 p->blocklist = NULL ;
868 p->scaldims = NULL ;
871 cloog_union_domain_free(ud);
873 return(p) ;
878 * cloog_program_read function:
879 * This function read the informations to put in a CloogProgram structure from
880 * a file (file, possibly stdin). It returns a pointer to a CloogProgram
881 * structure containing the read informations.
882 * - October 25th 2001: first version.
883 * - September 9th 2002: - the big reading function is now split in several
884 * functions (one per read data structure).
885 * - adaptation to the new file format with naming.
887 CloogProgram *cloog_program_read(FILE *file, CloogOptions *options)
889 CloogInput *input;
890 CloogProgram *p;
892 input = cloog_input_read(file, options);
893 p = cloog_program_alloc(input->context, input->ud, options);
894 free(input);
896 return p;
900 /******************************************************************************
901 * Processing functions *
902 ******************************************************************************/
906 * cloog_program_malloc function:
907 * This function allocates the memory space for a CloogProgram structure and
908 * sets its fields with default values. Then it returns a pointer to the
909 * allocated space.
910 * - November 21th 2005: first version.
912 CloogProgram * cloog_program_malloc()
913 { CloogProgram * program ;
915 /* Memory allocation for the CloogProgram structure. */
916 program = (CloogProgram *)malloc(sizeof(CloogProgram)) ;
917 if (program == NULL)
918 cloog_die("memory overflow.\n");
920 /* We set the various fields with default values. */
921 program->language = 'c' ;
922 program->nb_scattdims = 0 ;
923 program->context = NULL ;
924 program->loop = NULL ;
925 program->names = NULL ;
926 program->blocklist = NULL ;
927 program->scaldims = NULL ;
928 program->usr = NULL;
930 return program ;
935 * cloog_program_generate function:
936 * This function calls the Quillere algorithm for loop scanning. (see the
937 * Quillere paper) and calls the loop simplification function.
938 * - depth is the loop depth we want to optimize (guard free as possible),
939 * the first loop depth is 1 and anegative value is the infinity depth.
940 * - sep_level is the level number where we want to start loop separation.
942 * - October 26th 2001: first version.
943 * - April 19th 2005: some basic fixes and memory usage feature.
944 * - April 29th 2005: (bug fix, bug found by DaeGon Kim) see case 2 below.
946 CloogProgram * cloog_program_generate(program, options)
947 CloogProgram * program ;
948 CloogOptions * options ;
950 #ifdef CLOOG_RUSAGE
951 float time;
952 struct rusage start, end ;
953 #endif
954 CloogLoop * loop ;
955 #ifdef CLOOG_MEMORY
956 char status_path[MAX_STRING_VAL] ;
957 FILE * status ;
959 /* We initialize the memory need to 0. */
960 options->memory = 0 ;
961 #endif
963 if (options->override)
965 cloog_msg(options, CLOOG_WARNING,
966 "you are using -override option, be aware that the "
967 "generated\n code may be incorrect.\n") ;
969 else
970 { /* Playing with options may be dangerous, here are two possible issues :
971 * 1. Using -l option less than scattering dimension number may lead to
972 * an illegal target code (since the scattering is not respected), if
973 * it is the case, we set -l depth to the first acceptable value.
975 if ((program->nb_scattdims > options->l) && (options->l >= 0))
977 cloog_msg(options, CLOOG_WARNING,
978 "-l depth is less than the scattering dimension number "
979 "(the \n generated code may be incorrect), it has been "
980 "automaticaly set\n to this value (use option -override "
981 "to override).\n") ;
982 options->l = program->nb_scattdims ;
985 /* 2. Using -f option greater than one while -l depth is greater than the
986 * scattering dimension number may lead to iteration duplication (try
987 * test/daegon_lu_osp.cloog with '-f 3' to test) because of the step 4b
988 * of the cloog_loop_generate function, if it is the case, we set -l to
989 * the first acceptable value.
991 if (((options->f > 1) || (options->f < 0)) &&
992 ((options->l > program->nb_scattdims) || (options->l < 0)))
994 cloog_msg(options, CLOOG_WARNING,
995 "-f depth is more than one, -l depth has been "
996 "automaticaly set\n to the scattering dimension number "
997 "(target code may have\n duplicated iterations), -l depth "
998 "has been automaticaly set to\n this value (use option "
999 "-override to override).\n") ;
1000 options->l = program->nb_scattdims ;
1004 #ifdef CLOOG_RUSAGE
1005 getrusage(RUSAGE_SELF, &start) ;
1006 #endif
1007 if (program->loop != NULL)
1008 { loop = program->loop ;
1010 /* Here we go ! */
1011 loop = cloog_loop_generate(loop, program->context, 0, 0,
1012 program->scaldims,
1013 program->nb_scattdims,
1014 options);
1016 #ifdef CLOOG_MEMORY
1017 /* We read into the status file of the process how many memory it uses. */
1018 sprintf(status_path,"/proc/%d/status",getpid()) ;
1019 status = fopen(status_path, "r") ;
1020 while (fscanf(status,"%s",status_path) && strcmp(status_path,"VmData:")!=0);
1021 fscanf(status,"%d",&(options->memory)) ;
1022 fclose(status) ;
1023 #endif
1025 if ((!options->nosimplify) && (program->loop != NULL))
1026 loop = cloog_loop_simplify(loop, program->context, 0,
1027 program->nb_scattdims, options);
1029 program->loop = loop ;
1032 #ifdef CLOOG_RUSAGE
1033 getrusage(RUSAGE_SELF, &end) ;
1034 /* We calculate the time spent in code generation. */
1035 time = (end.ru_utime.tv_usec - start.ru_utime.tv_usec)/(float)(MEGA) ;
1036 time += (float)(end.ru_utime.tv_sec - start.ru_utime.tv_sec) ;
1037 options->time = time ;
1038 #endif
1040 return program ;
1045 * cloog_program_block function:
1046 * this function gives a last chance to the lazy user to consider statement
1047 * blocks instead of some statement lists where the whole list may be
1048 * considered as a single statement from a code generation point of view.
1049 * For instance two statements with the same iteration domain and the same
1050 * scattering functions may be considered as a block. This function is lazy
1051 * and can only find very simple forms of trivial blocks (see
1052 * cloog_domain_lazy_block function for more details). The useless loops and
1053 * scattering functions are removed and freed while the statement list of
1054 * according blocks are filled.
1055 * - program is the whole program structure (befaore applying scattering),
1056 * - scattering is the list of scattering functions.
1058 * - April 30th 2005: first attempt.
1059 * - June 10-11th 2005: first working version.
1061 void cloog_program_block(CloogProgram *program,
1062 CloogScatteringList *scattering, CloogOptions *options)
1063 { int blocked_reference=0, blocked=0, nb_blocked=0 ;
1064 CloogLoop * reference, * start, * loop ;
1065 CloogScatteringList * scatt_reference, * scatt_loop, * scatt_start;
1067 if ((program->loop == NULL) || (program->loop->next == NULL))
1068 return ;
1070 /* The process will use three variables for the linked list :
1071 * - 'start' is the starting point of a new block,
1072 * - 'reference' is the node of the block used for the block checking,
1073 * - 'loop' is the candidate to be inserted inside the block.
1074 * At the beginning of the process, the linked lists are as follow:
1075 * O------>O------>O------>O------>NULL
1076 * | |
1077 * start loop
1078 * reference
1081 reference = program->loop ;
1082 start = program->loop ;
1083 loop = reference->next ;
1084 scatt_reference = scattering ;
1085 scatt_start = scattering ;
1086 scatt_loop = scattering->next ;
1088 while (loop != NULL)
1089 { if (cloog_domain_lazy_equal(reference->domain,loop->domain) &&
1090 cloog_scattering_lazy_block(scatt_reference->scatt, scatt_loop->scatt,
1091 scattering,program->nb_scattdims))
1092 { /* If we find a block we update the links:
1093 * +---------------+
1094 * | v
1095 * O O------>O------>O------>NULL
1096 * | |
1097 * start loop
1098 * reference
1100 blocked = 1 ;
1101 nb_blocked ++ ;
1102 cloog_block_merge(start->block,loop->block); /* merge frees loop->block */
1103 loop->block = NULL ;
1104 start->next = loop->next ;
1105 scatt_start->next = scatt_loop->next ;
1107 else
1108 { /* If we didn't find a block, the next start of a block is updated:
1109 * O------>O------>O------>O------>NULL
1110 * | |
1111 * reference start
1112 * loop
1114 blocked= 0 ;
1115 start = loop ;
1116 scatt_start = scatt_loop ;
1119 /* If the reference node has been included into a block, we can free it. */
1120 if (blocked_reference)
1121 { reference->next = NULL ;
1122 cloog_loop_free(reference) ;
1123 cloog_scattering_free(scatt_reference->scatt);
1124 free(scatt_reference) ;
1127 /* The reference and the loop are now updated for the next try, the
1128 * starting position depends on the previous step.
1129 * O ? O------>O------>O------>NULL
1130 * | |
1131 * reference loop
1133 reference = loop ;
1134 loop = loop->next ;
1135 scatt_reference = scatt_loop ;
1136 scatt_loop = scatt_loop->next ;
1138 /* We mark the new reference as being blocked or not, if will be freed
1139 * during the next while loop execution.
1141 if (blocked)
1142 blocked_reference = 1 ;
1143 else
1144 blocked_reference = 0 ;
1147 /* We free the last blocked reference if any (since in the while loop it was
1148 * freed during the next loop execution, it was not possible to free the
1149 * last one inside).
1151 if (blocked_reference)
1152 { reference->next = NULL ;
1153 cloog_loop_free(reference) ;
1154 cloog_scattering_free(scatt_reference->scatt);
1155 free(scatt_reference) ;
1158 if (nb_blocked != 0)
1159 cloog_msg(options, CLOOG_INFO, "%d domains have been blocked.\n", nb_blocked);
1164 * cloog_program_extract_scalars function:
1165 * this functions finds and removes the dimensions of the scattering functions
1166 * when they are scalar (i.e. of the shape "dim + scalar = 0") for all
1167 * scattering functions. The reason is that the processing of such dimensions
1168 * is trivial and do not need neither a row and a column in the matrix
1169 * representation of the domain (this will save memory) neither the full
1170 * Quillere processing (this will save time). The scalar dimensions data are
1171 * dispatched in the CloogProgram structure (the boolean vector scaldims will
1172 * say which original dimensions are scalar or not) and to the CloogBlock
1173 * structures (each one has a scaldims vector that contains the scalar values).
1174 * - June 14th 2005: first developments.
1175 * - June 30th 2005: first version.
1177 void cloog_program_extract_scalars(CloogProgram *program,
1178 CloogScatteringList *scattering, CloogOptions *options)
1179 { int i, j, scalar, current, nb_scaldims=0 ;
1180 CloogScatteringList *start;
1181 CloogScattering *old;
1182 CloogLoop *loop;
1183 CloogBlock * block ;
1185 start = scattering ;
1187 for (i=0;i<program->nb_scattdims;i++)
1188 { scalar = 1 ;
1189 scattering = start ;
1190 while (scattering != NULL)
1191 { if (!cloog_scattering_lazy_isscalar(scattering->scatt, i, NULL))
1192 { scalar = 0 ;
1193 break ;
1195 scattering = scattering->next ;
1198 if (scalar)
1199 { nb_scaldims ++ ;
1200 program->scaldims[i] = 1 ;
1204 /* If there are no scalar dimensions, we can continue directly. */
1205 if (!nb_scaldims)
1206 return ;
1208 /* Otherwise, in each block, we have to put the number of scalar dimensions,
1209 * and to allocate the memory for the scalar values.
1211 for (loop = program->loop; loop; loop = loop->next) {
1212 block = loop->block;
1213 block->nb_scaldims = nb_scaldims ;
1214 block->scaldims = (cloog_int_t *)malloc(nb_scaldims*sizeof(cloog_int_t));
1215 for (i=0;i<nb_scaldims;i++)
1216 cloog_int_init(block->scaldims[i]);
1219 /* Then we have to fill these scalar values, so we can erase those dimensions
1220 * from the scattering functions. It's easier to begin with the last one,
1221 * since there would be an offset otherwise (if we remove the i^th dimension,
1222 * then the next one is not the (i+1)^th but still the i^th...).
1224 current = nb_scaldims - 1 ;
1225 for (i=program->nb_scattdims-1;i>=0;i--)
1226 if (program->scaldims[i])
1228 scattering = start ;
1229 for (loop = program->loop; loop; loop = loop->next) {
1230 block = loop->block;
1231 if (!cloog_scattering_lazy_isscalar(scattering->scatt, i,
1232 &block->scaldims[current])) {
1233 /* We should have found a scalar value: if not, there is an error. */
1234 cloog_die("dimension %d is not scalar as expected.\n", i);
1236 scattering = scattering->next ;
1239 scattering = start ;
1240 while (scattering != NULL) {
1241 old = scattering->scatt;
1242 scattering->scatt = cloog_scattering_erase_dimension(old, i);
1243 cloog_scattering_free(old);
1244 scattering = scattering->next ;
1246 current-- ;
1249 /* We postprocess the scaldims array in such a way that each entry is how
1250 * many scalar dimensions follows + 1 (the current one). This will make
1251 * some other processing easier (e.g. knowledge of some offsets).
1253 for (i=0;i<program->nb_scattdims-1;i++)
1254 { if (program->scaldims[i])
1255 { j = i + 1 ;
1256 while ((j < program->nb_scattdims) && program->scaldims[j])
1257 { program->scaldims[i] ++ ;
1258 j ++ ;
1263 if (nb_scaldims != 0)
1264 cloog_msg(options, CLOOG_INFO, "%d dimensions (over %d) are scalar.\n",
1265 nb_scaldims,program->nb_scattdims) ;
1270 * cloog_program_scatter function:
1271 * This function adds the scattering (scheduling) informations in a program.
1272 * If names is NULL, this function create names itself such that the i^th
1273 * name is ci.
1274 * - November 6th 2001: first version.
1276 void cloog_program_scatter(CloogProgram *program,
1277 CloogScatteringList *scattering, CloogOptions *options)
1278 { int scattering_dim, scattering_dim2, not_enough_constraints=0 ;
1279 CloogLoop * loop ;
1281 if ((program != NULL) && (scattering != NULL))
1282 { loop = program->loop ;
1284 /* We compute the scattering dimension and check it is >=0. */
1285 scattering_dim = cloog_scattering_dimension(scattering->scatt, loop->domain);
1286 if (scattering_dim < 0)
1287 cloog_die("scattering has not enough dimensions.\n");
1288 if (!cloog_scattering_fully_specified(scattering->scatt, loop->domain))
1289 not_enough_constraints ++ ;
1291 /* The scattering dimension may have been modified by scalar extraction. */
1292 scattering_dim = cloog_scattering_dimension(scattering->scatt, loop->domain);
1294 /* Finally we scatter all loops. */
1295 cloog_loop_scatter(loop, scattering->scatt);
1296 loop = loop->next ;
1297 scattering = scattering->next ;
1299 while ((loop != NULL) && (scattering != NULL))
1300 { scattering_dim2 = cloog_scattering_dimension(scattering->scatt,
1301 loop->domain);
1302 if (scattering_dim2 != scattering_dim)
1303 cloog_die("scattering dimensions are not the same.\n") ;
1304 if (!cloog_scattering_fully_specified(scattering->scatt, loop->domain))
1305 not_enough_constraints ++ ;
1307 cloog_loop_scatter(loop, scattering->scatt);
1308 loop = loop->next ;
1309 scattering = scattering->next ;
1311 if ((loop != NULL) || (scattering != NULL))
1312 cloog_msg(options, CLOOG_WARNING,
1313 "there is not a scattering for each statement.\n");
1315 if (not_enough_constraints)
1316 cloog_msg(options, CLOOG_WARNING, "not enough constraints for "
1317 "%d scattering function(s).\n",not_enough_constraints) ;