1 2 /**-------------------------------------------------------------------** 3 ** CLooG ** 4 **-------------------------------------------------------------------** 5 ** program.c ** 6 **-------------------------------------------------------------------** 7 ** First version: october 25th 2001 ** 8 **-------------------------------------------------------------------**/ 9 10 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 ! 38 */ 39 40 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 53 54#define ALLOC(type) (type*)malloc(sizeof(type)) 55 56#ifdef OSL_SUPPORT 57#include <osl/scop.h> 58#include <osl/extensions/coordinates.h> 59#endif 60 61/****************************************************************************** 62 * Structure display function * 63 ******************************************************************************/ 64 65 66/** 67 * cloog_program_print function: 68 * this function is a human-friendly way to display the CloogProgram data 69 * structure, it shows all the different fields and includes an indentation 70 * level (level) in order to work with others print_structure functions. 71 * - July 1st 2005: first version based on the old cloog_program_print function. 72 */ 73void cloog_program_print_structure(file, program, level) 74FILE * file ; 75CloogProgram * program ; 76int level ; 77{ int i, j ; 78 79 /* Go to the right level. */ 80 for (i=0; i<level; i++) 81 fprintf(file,"|\t") ; 82 83 fprintf(file,"+-- CloogProgram\n") ; 84 85 /* A blank line. */ 86 for (i=0; i<=level+1; i++) 87 fprintf(file,"|\t") ; 88 fprintf(file,"\n") ; 89 90 /* Print the language. */ 91 for (i=0; i<=level; i++) 92 fprintf(file,"|\t") ; 93 fprintf(file, "Language: %c\n",program->language) ; 94 95 /* A blank line. */ 96 for (i=0; i<=level+1; i++) 97 fprintf(file,"|\t") ; 98 fprintf(file,"\n") ; 99 100 /* Print the scattering dimension number. */ 101 for (i=0; i<=level; i++) 102 fprintf(file,"|\t") ; 103 fprintf(file,"Scattering dimension number: %d\n",program->nb_scattdims) ; 104 105 /* A blank line. */ 106 for (i=0; i<=level+1; i++) 107 fprintf(file,"|\t") ; 108 fprintf(file,"\n") ; 109 110 /* Print the scalar scattering dimension informations. */ 111 for (i=0; i<=level; i++) 112 fprintf(file,"|\t") ; 113 if (program->scaldims != NULL) 114 { fprintf(file,"Scalar dimensions:") ; 115 for (i=0;i<program->nb_scattdims;i++) 116 fprintf(file," %d:%d ",i,program->scaldims[i]) ; 117 fprintf(file,"\n") ; 118 } 119 else 120 fprintf(file,"No scalar scattering dimensions\n") ; 121 122 /* A blank line. */ 123 for (i=0; i<=level+1; i++) 124 fprintf(file,"|\t") ; 125 fprintf(file,"\n") ; 126 127 /* Print the parameter and the iterator names. */ 128 cloog_names_print_structure(file,program->names,level+1) ; 129 130 /* A blank line. */ 131 for (i=0; i<=level+1; i++) 132 fprintf(file,"|\t") ; 133 fprintf(file,"\n") ; 134 135 /* Print the context. */ 136 cloog_domain_print_structure(file, program->context, level+1, "Context"); 137 138 /* Print the loop. */ 139 cloog_loop_print_structure(file,program->loop,level+1) ; 140 141 /* One more time something that is here only for a better look. */ 142 for (j=0; j<2; j++) 143 { for (i=0; i<=level; i++) 144 fprintf(file,"|\t") ; 145 146 fprintf(file,"\n") ; 147 } 148} 149 150 151/** 152 * cloog_program_dump_cloog function: 153 * This function dumps a CloogProgram structure supposed to be completely 154 * filled in a CLooG input file (foo possibly stdout) such as CLooG can 155 * rebuild almost exactly the data structure from the input file. 156 * 157 * If the scattering is already applied, the scattering parameter is supposed to 158 * be NULL. In this case the number of scattering functions is lost, since they 159 * are included inside the iteration domains. This can only lead to a less 160 * beautiful pretty printing. 161 * 162 * In case the scattering is not yet applied it can be passed to this function 163 * and will be included in the CLooG input file dump. 164 */ 165void cloog_program_dump_cloog(FILE * foo, CloogProgram * program, 166 CloogScatteringList *scattering) 167{ 168 int i; 169 CloogLoop * loop ; 170 CloogScatteringList *tmp_scatt; 171 172 fprintf(foo, 173 "# CLooG -> CLooG\n" 174 "# This is an automatic dump of a CLooG input file from a CloogProgram data\n" 175 "# structure. WARNING: it is highly dangerous and MAY be correct ONLY if\n" 176 "# - it has been dumped before loop generation.\n" 177 "# - option -noscalars is used (it removes scalar dimensions otherwise)\n" 178 "# - option -l is at least the original scattering dimension number\n" 179 "# ASK THE AUTHOR IF YOU *NEED* SOMETHING MORE ROBUST\n") ; 180 181 /* Language. */ 182 if (program->language == 'c') 183 fprintf(foo,"# Language: C\n") ; 184 else 185 fprintf(foo,"# Language: FORTRAN\n") ; 186 fprintf(foo,"%c\n\n",program->language) ; 187 188 /* Context. */ 189 fprintf(foo, "# Context (%d parameter(s)):\n", program->names->nb_parameters); 190 cloog_domain_print_constraints(foo, program->context, 0); 191 fprintf(foo,"1 # Parameter name(s)\n") ; 192 for (i=0;i<program->names->nb_parameters;i++) 193 fprintf(foo,"%s ",program->names->parameters[i]) ; 194 195 /* Statement number. */ 196 i = 0 ; 197 loop = program->loop ; 198 while (loop != NULL) 199 { i++ ; 200 loop = loop->next ; 201 } 202 fprintf(foo,"\n\n# Statement number:\n%d\n\n",i) ; 203 204 /* Iteration domains. */ 205 i = 1 ; 206 loop = program->loop ; 207 while (loop != NULL) 208 { /* Name of the domain. */ 209 fprintf(foo,"# Iteration domain of statement %d.\n",i) ; 210 211 cloog_domain_print_constraints(foo, loop->domain, 1); 212 fprintf(foo,"0 0 0 # For future options.\n\n") ; 213 214 i++ ; 215 loop = loop->next ; 216 } 217 fprintf(foo,"\n1 # Iterator name(s)\n") ; 218 219 /* Scattering already applied? In this case print the scattering names as 220 * additional iterator names. */ 221 if (!scattering) 222 for (i = 0; i < program->names->nb_scattering; i++) 223 fprintf(foo, "%s ", program->names->scattering[i]); 224 for (i=0;i<program->names->nb_iterators;i++) 225 fprintf(foo,"%s ",program->names->iterators[i]); 226 fprintf(foo,"\n\n") ; 227 228 /* Exit, if scattering is already applied. */ 229 if (!scattering) { 230 fprintf(foo, "# No scattering functions.\n0\n\n"); 231 return; 232 } 233 234 /* Scattering relations. */ 235 fprintf(foo, "# --------------------- SCATTERING --------------------\n"); 236 237 i = 0; 238 for (tmp_scatt = scattering; tmp_scatt; tmp_scatt = tmp_scatt->next) 239 i++; 240 241 fprintf(foo, "%d # Scattering functions", i); 242 243 for (tmp_scatt = scattering; tmp_scatt; tmp_scatt = tmp_scatt->next) 244 cloog_scattering_print_constraints(foo, tmp_scatt->scatt); 245 246 fprintf(foo, "\n1 # Scattering dimension name(s)\n"); 247 248 for (i = 0; i < program->names->nb_scattering; i++) 249 fprintf(foo, "%s ", program->names->scattering[i]); 250} 251 252 253/** 254 * cloog_program_print function: 255 * This function prints the content of a CloogProgram structure (program) into a 256 * file (file, possibly stdout). 257 * - July 1st 2005: Now this very old function (probably as old as CLooG) is 258 * only a frontend to cloog_program_print_structure, with a 259 * quite better human-readable representation. 260 */ 261void cloog_program_print(FILE * file, CloogProgram * program) 262{ cloog_program_print_structure(file,program,0) ; 263} 264 265 266static void print_comment(FILE *file, CloogOptions *options, 267 const char *fmt, ...) 268{ 269 va_list args; 270 271 va_start(args, fmt); 272 if (options->language == CLOOG_LANGUAGE_FORTRAN) { 273 fprintf(file, "! "); 274 vfprintf(file, fmt, args); 275 fprintf(file, "\n"); 276 } else { 277 fprintf(file, "/* "); 278 vfprintf(file, fmt, args); 279 fprintf(file, " */\n"); 280 } 281} 282 283static void print_macros(FILE *file) 284{ 285 fprintf(file, "/* Useful macros. */\n") ; 286 fprintf(file, 287 "#define floord(n,d) (((n)<0) ? -((-(n)+(d)-1)/(d)) : (n)/(d))\n"); 288 fprintf(file, 289 "#define ceild(n,d) (((n)<0) ? -((-(n))/(d)) : ((n)+(d)-1)/(d))\n"); 290 fprintf(file, "#define max(x,y) ((x) > (y) ? (x) : (y))\n") ; 291 fprintf(file, "#define min(x,y) ((x) < (y) ? (x) : (y))\n\n") ; 292} 293 294static void print_declarations(FILE *file, int n, char **names) 295{ 296 int i; 297 298 fprintf(file, " int %s", names[0]); 299 for (i = 1; i < n; i++) 300 fprintf(file, ", %s", names[i]); 301 302 fprintf(file, ";\n"); 303} 304 305static void print_iterator_declarations(FILE *file, CloogProgram *program, 306 CloogOptions *options) 307{ 308 CloogNames *names = program->names; 309 310 if (names->nb_scattering) { 311 fprintf(file, " /* Scattering iterators. */\n"); 312 print_declarations(file, names->nb_scattering, names->scattering); 313 } 314 if (names->nb_iterators) { 315 fprintf(file, " /* Original iterators. */\n"); 316 print_declarations(file, names->nb_iterators, names->iterators); 317 } 318} 319 320static void print_callable_preamble(FILE *file, CloogProgram *program, 321 CloogOptions *options) 322{ 323 int j; 324 CloogBlockList *blocklist; 325 CloogBlock *block; 326 CloogStatement *statement; 327 328 fprintf(file, "extern void hash(int);\n\n"); 329 330 print_macros(file); 331 332 for (blocklist = program->blocklist; blocklist; blocklist = blocklist->next) { 333 block = blocklist->block; 334 for (statement = block->statement; statement; statement = statement->next) { 335 fprintf(file, "#define S%d(", statement->number); 336 if (block->depth > 0) { 337 fprintf(file, "%s", program->names->iterators[0]); 338 for(j = 1; j < block->depth; j++) 339 fprintf(file, ",%s", program->names->iterators[j]); 340 } 341 fprintf(file,") { hash(%d);", statement->number); 342 for(j = 0; j < block->depth; j++) 343 fprintf(file, " hash(%s);", program->names->iterators[j]); 344 fprintf(file, " }\n"); 345 } 346 } 347 fprintf(file, "\nvoid test("); 348 if (program->names->nb_parameters > 0) { 349 fprintf(file, "int %s", program->names->parameters[0]); 350 for(j = 1; j < program->names->nb_parameters; j++) 351 fprintf(file, ", int %s", program->names->parameters[j]); 352 } 353 fprintf(file, ")\n{\n"); 354 print_iterator_declarations(file, program, options); 355} 356 357static void print_callable_postamble(FILE *file, CloogProgram *program) 358{ 359 fprintf(file, "}\n"); 360} 361 362/** 363 * cloog_program_osl_pprint function: 364 * this function pretty-prints the C or FORTRAN code generated from an 365 * OpenScop specification by overwriting SCoP in a given code, if the 366 * options -compilable or -callable are not set. The SCoP coordinates are 367 * provided through the OpenScop "Coordinates" extension. It returns 1 if 368 * it succeeds to find an OpenScop coordinates information 369 * to pretty-print the generated code, 0 otherwise. 370 * \param[in] file The output stream (possibly stdout). 371 * \param[in] program The generated pseudo-AST to pretty-print. 372 * \param[in] options CLooG options (contains the OpenSCop specification). 373 * \return 1 on success to pretty-print at the place of a SCoP, 0 otherwise. 374 */ 375int cloog_program_osl_pprint(FILE * file, CloogProgram * program, 376 CloogOptions * options) { 377#ifdef OSL_SUPPORT 378 int lines = 0; 379 int read = 1; 380 char c; 381 osl_scop_p scop = options->scop; 382 osl_coordinates_p coordinates; 383 struct clast_stmt *root; 384 FILE * original; 385 386 if (scop && !options->compilable && !options->callable) { 387 coordinates = osl_generic_lookup(scop->extension, OSL_URI_COORDINATES); 388 if (coordinates) { 389 original = fopen(coordinates->name, "r"); 390 if (!original) { 391 cloog_msg(options, CLOOG_WARNING, 392 "unable to open the file specified in the SCoP " 393 "coordinates\n"); 394 return 0; 395 } 396 397 /* Print the macros the generated code may need. */ 398 print_macros(file); 399 400 /* Print what was before the SCoP in the original file. */ 401 while ((lines < coordinates->start) && (read != EOF)) { 402 read = fscanf(original, "%c", &c); 403 if (read != EOF) { 404 if (c == '\n') 405 lines ++; 406 fprintf(file, "%c", c); 407 } 408 } 409 410 /* Generate the clast from the pseudo-AST then pretty-print it. */ 411 root = cloog_clast_create(program, options); 412 clast_pprint(file, root, coordinates->indent, options); 413 cloog_clast_free(root); 414 415 /* Print what was after the SCoP in the original file. */ 416 while (read != EOF) { 417 read = fscanf(original, "%c", &c); 418 if (read != EOF) { 419 if (lines >= coordinates->end - 1) 420 fprintf(file, "%c", c); 421 if (c == '\n') 422 lines ++; 423 } 424 } 425 426 fclose(original); 427 return 1; 428 } 429 } 430#endif 431 return 0; 432} 433 434/** 435 * cloog_program_pprint function: 436 * This function prints the content of a CloogProgram structure (program) into a 437 * file (file, possibly stdout), in a C-like language. 438 * - June 22nd 2005: Adaptation for GMP. 439 */ 440void cloog_program_pprint(file, program, options) 441FILE * file ; 442CloogProgram * program ; 443CloogOptions * options ; 444{ 445 int i, j, indentation = 0; 446 CloogStatement * statement ; 447 CloogBlockList * blocklist ; 448 CloogBlock * block ; 449 struct clast_stmt *root; 450 451 if (cloog_program_osl_pprint(file, program, options)) 452 return; 453 454 if (program->language == 'f') 455 options->language = CLOOG_LANGUAGE_FORTRAN ; 456 else 457 options->language = CLOOG_LANGUAGE_C ; 458 459#ifdef CLOOG_RUSAGE 460 print_comment(file, options, "Generated from %s by %s in %.2fs.", 461 options->name, cloog_version(), options->time); 462#else 463 print_comment(file, options, "Generated from %s by %s.", 464 options->name, cloog_version()); 465#endif 466#ifdef CLOOG_MEMORY 467 print_comment(file, options, "CLooG asked for %d KBytes.", options->memory); 468 cloog_msg(CLOOG_INFO, "%.2fs and %dKB used for code generation.\n", 469 options->time,options->memory); 470#endif 471 472 /* If the option "compilable" is set, we provide the whole stuff to generate 473 * a compilable code. This code just do nothing, but now the user can edit 474 * the source and set the statement macros and parameters values. 475 */ 476 if (options->compilable && (program->language == 'c')) 477 { /* The headers. */ 478 fprintf(file,"/* DON'T FORGET TO USE -lm OPTION TO COMPILE. */\n\n") ; 479 fprintf(file,"/* Useful headers. */\n") ; 480 fprintf(file,"#include <stdio.h>\n") ; 481 fprintf(file,"#include <stdlib.h>\n") ; 482 fprintf(file,"#include <math.h>\n\n") ; 483 484 /* The value of parameters. */ 485 fprintf(file,"/* Parameter value. */\n") ; 486 for (i = 1; i <= program->names->nb_parameters; i++) 487 fprintf(file, "#define PARVAL%d %d\n", i, options->compilable); 488 489 /* The macros. */ 490 print_macros(file); 491 492 /* The statement macros. */ 493 fprintf(file,"/* Statement macros (please set). */\n") ; 494 blocklist = program->blocklist ; 495 while (blocklist != NULL) 496 { block = blocklist->block ; 497 statement = block->statement ; 498 while (statement != NULL) 499 { fprintf(file,"#define S%d(",statement->number) ; 500 if (block->depth > 0) 501 { fprintf(file,"%s",program->names->iterators[0]) ; 502 for(j=1;j<block->depth;j++) 503 fprintf(file,",%s",program->names->iterators[j]) ; 504 } 505 fprintf(file,") {total++;") ; 506 if (block->depth > 0) { 507 fprintf(file, " printf(\"S%d %%d", statement->number); 508 for(j=1;j<block->depth;j++) 509 fprintf(file, " %%d"); 510 511 fprintf(file,"\\n\",%s",program->names->iterators[0]) ; 512 for(j=1;j<block->depth;j++) 513 fprintf(file,",%s",program->names->iterators[j]) ; 514 fprintf(file,");") ; 515 } 516 fprintf(file,"}\n") ; 517 518 statement = statement->next ; 519 } 520 blocklist = blocklist->next ; 521 } 522 523 /* The iterator and parameter declaration. */ 524 fprintf(file,"\nint main() {\n") ; 525 print_iterator_declarations(file, program, options); 526 if (program->names->nb_parameters > 0) 527 { fprintf(file," /* Parameters. */\n") ; 528 fprintf(file, " int %s=PARVAL1",program->names->parameters[0]); 529 for(i=2;i<=program->names->nb_parameters;i++) 530 fprintf(file, ", %s=PARVAL%d", program->names->parameters[i-1], i); 531 532 fprintf(file,";\n"); 533 } 534 fprintf(file," int total=0;\n"); 535 fprintf(file,"\n") ; 536 537 /* And we adapt the identation. */ 538 indentation += 2 ; 539 } else if (options->callable && program->language == 'c') { 540 print_callable_preamble(file, program, options); 541 indentation += 2; 542 } 543 544 root = cloog_clast_create(program, options); 545 clast_pprint(file, root, indentation, options); 546 cloog_clast_free(root); 547 548 /* The end of the compilable code in case of 'compilable' option. */ 549 if (options->compilable && (program->language == 'c')) 550 { 551 fprintf(file, "\n printf(\"Number of integral points: %%d.\\n\",total);"); 552 fprintf(file, "\n return 0;\n}\n"); 553 } else if (options->callable && program->language == 'c') 554 print_callable_postamble(file, program); 555} 556 557 558/****************************************************************************** 559 * Memory deallocation function * 560 ******************************************************************************/ 561 562 563/** 564 * cloog_program_free function: 565 * This function frees the allocated memory for a CloogProgram structure. 566 */ 567void cloog_program_free(CloogProgram * program) 568{ cloog_names_free(program->names) ; 569 cloog_loop_free(program->loop) ; 570 cloog_domain_free(program->context) ; 571 cloog_block_list_free(program->blocklist) ; 572 if (program->scaldims != NULL) 573 free(program->scaldims) ; 574 575 free(program) ; 576} 577 578 579/****************************************************************************** 580 * Reading function * 581 ******************************************************************************/ 582 583 584static void cloog_program_construct_block_list(CloogProgram *p) 585{ 586 CloogLoop *loop; 587 CloogBlockList **next = &p->blocklist; 588 589 for (loop = p->loop; loop; loop = loop->next) { 590 *next = cloog_block_list_alloc(loop->block); 591 next = &(*next)->next; 592 } 593} 594 595 596/** 597 * Construct a CloogProgram structure from a given context and 598 * union domain representing the iteration domains and scattering functions. 599 */ 600CloogProgram *cloog_program_alloc(CloogDomain *context, CloogUnionDomain *ud, 601 CloogOptions *options) 602{ 603 int i; 604 char prefix[] = "c"; 605 CloogScatteringList * scatteringl; 606 CloogNames *n; 607 CloogProgram * p ; 608 609 /* Memory allocation for the CloogProgram structure. */ 610 p = cloog_program_malloc() ; 611 612 if (options->language == CLOOG_LANGUAGE_FORTRAN) 613 p->language = 'f'; 614 else 615 p->language = 'c'; 616 617 p->names = n = cloog_names_alloc(); 618 619 /* We then read the context data. */ 620 p->context = context; 621 n->nb_parameters = ud->n_name[CLOOG_PARAM]; 622 623 /* First part of the CloogNames structure: the parameter names. */ 624 if (ud->name[CLOOG_PARAM]) { 625 n->parameters = ud->name[CLOOG_PARAM]; 626 ud->name[CLOOG_PARAM] = NULL; 627 } else 628 n->parameters = cloog_names_generate_items(n->nb_parameters, NULL, 629 FIRST_PARAMETER); 630 631 n->nb_iterators = ud->n_name[CLOOG_ITER]; 632 if (ud->name[CLOOG_ITER]) { 633 n->iterators = ud->name[CLOOG_ITER]; 634 ud->name[CLOOG_ITER] = NULL; 635 } else 636 n->iterators = cloog_names_generate_items(n->nb_iterators, NULL, 637 FIRST_ITERATOR); 638 639 if (ud->domain) { 640 CloogNamedDomainList *l; 641 CloogLoop **next = &p->loop; 642 CloogScatteringList **next_scat = &scatteringl; 643 644 scatteringl = NULL; 645 for (i = 0, l = ud->domain; l; ++i, l = l->next) { 646 *next = cloog_loop_from_domain(options->state, l->domain, i); 647 l->domain = NULL; 648 (*next)->block->statement->name = l->name; 649 (*next)->block->statement->usr = l->usr; 650 l->name = NULL; 651 652 if (l->scattering) { 653 *next_scat = ALLOC(CloogScatteringList); 654 (*next_scat)->scatt = l->scattering; 655 l->scattering = NULL; 656 (*next_scat)->next = NULL; 657 658 next_scat = &(*next_scat)->next; 659 } 660 661 next = &(*next)->next; 662 } 663 664 if (scatteringl != NULL) { 665 p->nb_scattdims = cloog_scattering_dimension(scatteringl->scatt, 666 p->loop->domain); 667 n->nb_scattering = p->nb_scattdims; 668 if (ud->name[CLOOG_SCAT]) { 669 n->scattering = ud->name[CLOOG_SCAT]; 670 ud->name[CLOOG_SCAT] = NULL; 671 } else 672 n->scattering = cloog_names_generate_items(n->nb_scattering, prefix, -1); 673 674 /* The boolean array for scalar dimensions is created and set to 0. */ 675 p->scaldims = (int *)malloc(p->nb_scattdims*(sizeof(int))) ; 676 if (p->scaldims == NULL) 677 cloog_die("memory overflow.\n"); 678 for (i=0;i<p->nb_scattdims;i++) 679 p->scaldims[i] = 0 ; 680 681 /* We try to find blocks in the input problem to reduce complexity. */ 682 if (!options->noblocks) 683 cloog_program_block(p, scatteringl, options); 684 if (!options->noscalars) 685 cloog_program_extract_scalars(p, scatteringl, options); 686 687 cloog_program_scatter(p, scatteringl, options); 688 cloog_scattering_list_free(scatteringl); 689 690 if (!options->noblocks) 691 p->loop = cloog_loop_block(p->loop, p->scaldims, p->nb_scattdims); 692 } 693 else 694 { p->nb_scattdims = 0 ; 695 p->scaldims = NULL ; 696 } 697 698 cloog_names_scalarize(p->names,p->nb_scattdims,p->scaldims) ; 699 700 cloog_program_construct_block_list(p); 701 } 702 else 703 { p->loop = NULL ; 704 p->blocklist = NULL ; 705 p->scaldims = NULL ; 706 } 707 708 cloog_union_domain_free(ud); 709 710 return(p) ; 711} 712 713 714/** 715 * cloog_program_read function: 716 * This function read the informations to put in a CloogProgram structure from 717 * a file (file, possibly stdin). It returns a pointer to a CloogProgram 718 * structure containing the read informations. 719 * - October 25th 2001: first version. 720 * - September 9th 2002: - the big reading function is now split in several 721 * functions (one per read data structure). 722 * - adaptation to the new file format with naming. 723 */ 724CloogProgram *cloog_program_read(FILE *file, CloogOptions *options) 725{ 726 CloogInput *input; 727 CloogProgram *p; 728 729 input = cloog_input_read(file, options); 730 p = cloog_program_alloc(input->context, input->ud, options); 731 free(input); 732 733 return p; 734} 735 736 737/****************************************************************************** 738 * Processing functions * 739 ******************************************************************************/ 740 741 742/** 743 * cloog_program_malloc function: 744 * This function allocates the memory space for a CloogProgram structure and 745 * sets its fields with default values. Then it returns a pointer to the 746 * allocated space. 747 * - November 21th 2005: first version. 748 */ 749CloogProgram * cloog_program_malloc() 750{ CloogProgram * program ; 751 752 /* Memory allocation for the CloogProgram structure. */ 753 program = (CloogProgram *)malloc(sizeof(CloogProgram)) ; 754 if (program == NULL) 755 cloog_die("memory overflow.\n"); 756 757 /* We set the various fields with default values. */ 758 program->language = 'c' ; 759 program->nb_scattdims = 0 ; 760 program->context = NULL ; 761 program->loop = NULL ; 762 program->names = NULL ; 763 program->blocklist = NULL ; 764 program->scaldims = NULL ; 765 program->usr = NULL; 766 767 return program ; 768} 769 770 771/** 772 * cloog_program_generate function: 773 * This function calls the Quillere algorithm for loop scanning. (see the 774 * Quillere paper) and calls the loop simplification function. 775 * - depth is the loop depth we want to optimize (guard free as possible), 776 * the first loop depth is 1 and anegative value is the infinity depth. 777 * - sep_level is the level number where we want to start loop separation. 778 ** 779 * - October 26th 2001: first version. 780 * - April 19th 2005: some basic fixes and memory usage feature. 781 * - April 29th 2005: (bug fix, bug found by DaeGon Kim) see case 2 below. 782 */ 783CloogProgram * cloog_program_generate(program, options) 784CloogProgram * program ; 785CloogOptions * options ; 786{ 787#ifdef CLOOG_RUSAGE 788 float time; 789 struct rusage start, end ; 790#endif 791 CloogLoop * loop ; 792#ifdef CLOOG_MEMORY 793 char status_path[MAX_STRING_VAL] ; 794 FILE * status ; 795 796 /* We initialize the memory need to 0. */ 797 options->memory = 0 ; 798#endif 799 800 if (options->override) 801 { 802 cloog_msg(options, CLOOG_WARNING, 803 "you are using -override option, be aware that the " 804 "generated\n code may be incorrect.\n") ; 805 } 806 else 807 { /* Playing with options may be dangerous, here are two possible issues : 808 * 1. Using -l option less than scattering dimension number may lead to 809 * an illegal target code (since the scattering is not respected), if 810 * it is the case, we set -l depth to the first acceptable value. 811 */ 812 if ((program->nb_scattdims > options->l) && (options->l >= 0)) 813 { 814 cloog_msg(options, CLOOG_WARNING, 815 "-l depth is less than the scattering dimension number " 816 "(the \n generated code may be incorrect), it has been " 817 "automaticaly set\n to this value (use option -override " 818 "to override).\n") ; 819 options->l = program->nb_scattdims ; 820 } 821 822 /* 2. Using -f option greater than one while -l depth is greater than the 823 * scattering dimension number may lead to iteration duplication (try 824 * test/daegon_lu_osp.cloog with '-f 3' to test) because of the step 4b 825 * of the cloog_loop_generate function, if it is the case, we set -l to 826 * the first acceptable value. 827 */ 828 if (((options->f > 1) || (options->f < 0)) && 829 ((options->l > program->nb_scattdims) || (options->l < 0))) 830 { 831 cloog_msg(options, CLOOG_WARNING, 832 "-f depth is more than one, -l depth has been " 833 "automaticaly set\n to the scattering dimension number " 834 "(target code may have\n duplicated iterations), -l depth " 835 "has been automaticaly set to\n this value (use option " 836 "-override to override).\n") ; 837 options->l = program->nb_scattdims ; 838 } 839 } 840 841#ifdef CLOOG_RUSAGE 842 getrusage(RUSAGE_SELF, &start) ; 843#endif 844 if (program->loop != NULL) 845 { loop = program->loop ; 846 847 /* Here we go ! */ 848 loop = cloog_loop_generate(loop, program->context, 0, 0, 849 program->scaldims, 850 program->nb_scattdims, 851 options); 852 853#ifdef CLOOG_MEMORY 854 /* We read into the status file of the process how many memory it uses. */ 855 sprintf(status_path,"/proc/%d/status",getpid()) ; 856 status = fopen(status_path, "r") ; 857 while (fscanf(status,"%s",status_path) && strcmp(status_path,"VmData:")!=0); 858 fscanf(status,"%d",&(options->memory)) ; 859 fclose(status) ; 860#endif 861 862 if ((!options->nosimplify) && (program->loop != NULL)) 863 loop = cloog_loop_simplify(loop, program->context, 0, 864 program->nb_scattdims, options); 865 866 program->loop = loop ; 867 } 868 869#ifdef CLOOG_RUSAGE 870 getrusage(RUSAGE_SELF, &end) ; 871 /* We calculate the time spent in code generation. */ 872 time = (end.ru_utime.tv_usec - start.ru_utime.tv_usec)/(float)(MEGA) ; 873 time += (float)(end.ru_utime.tv_sec - start.ru_utime.tv_sec) ; 874 options->time = time ; 875#endif 876 877 return program ; 878} 879 880 881/** 882 * cloog_program_block function: 883 * this function gives a last chance to the lazy user to consider statement 884 * blocks instead of some statement lists where the whole list may be 885 * considered as a single statement from a code generation point of view. 886 * For instance two statements with the same iteration domain and the same 887 * scattering functions may be considered as a block. This function is lazy 888 * and can only find very simple forms of trivial blocks (see 889 * cloog_domain_lazy_block function for more details). The useless loops and 890 * scattering functions are removed and freed while the statement list of 891 * according blocks are filled. 892 * - program is the whole program structure (befaore applying scattering), 893 * - scattering is the list of scattering functions. 894 ** 895 * - April 30th 2005: first attempt. 896 * - June 10-11th 2005: first working version. 897 */ 898void cloog_program_block(CloogProgram *program, 899 CloogScatteringList *scattering, CloogOptions *options) 900{ int blocked_reference=0, blocked=0, nb_blocked=0 ; 901 CloogLoop * reference, * start, * loop ; 902 CloogScatteringList * scatt_reference, * scatt_loop, * scatt_start; 903 904 if ((program->loop == NULL) || (program->loop->next == NULL)) 905 return ; 906 907 /* The process will use three variables for the linked list : 908 * - 'start' is the starting point of a new block, 909 * - 'reference' is the node of the block used for the block checking, 910 * - 'loop' is the candidate to be inserted inside the block. 911 * At the beginning of the process, the linked lists are as follow: 912 * O------>O------>O------>O------>NULL 913 * | | 914 * start loop 915 * reference 916 */ 917 918 reference = program->loop ; 919 start = program->loop ; 920 loop = reference->next ; 921 scatt_reference = scattering ; 922 scatt_start = scattering ; 923 scatt_loop = scattering->next ; 924 925 while (loop != NULL) 926 { if (cloog_domain_lazy_equal(reference->domain,loop->domain) && 927 cloog_scattering_lazy_block(scatt_reference->scatt, scatt_loop->scatt, 928 scattering,program->nb_scattdims)) 929 { /* If we find a block we update the links: 930 * +---------------+ 931 * | v 932 * O O------>O------>O------>NULL 933 * | | 934 * start loop 935 * reference 936 */ 937 blocked = 1 ; 938 nb_blocked ++ ; 939 cloog_block_merge(start->block,loop->block); /* merge frees loop->block */ 940 loop->block = NULL ; 941 start->next = loop->next ; 942 scatt_start->next = scatt_loop->next ; 943 } 944 else 945 { /* If we didn't find a block, the next start of a block is updated: 946 * O------>O------>O------>O------>NULL 947 * | | 948 * reference start 949 * loop 950 */ 951 blocked= 0 ; 952 start = loop ; 953 scatt_start = scatt_loop ; 954 } 955 956 /* If the reference node has been included into a block, we can free it. */ 957 if (blocked_reference) 958 { reference->next = NULL ; 959 cloog_loop_free(reference) ; 960 cloog_scattering_free(scatt_reference->scatt); 961 free(scatt_reference) ; 962 } 963 964 /* The reference and the loop are now updated for the next try, the 965 * starting position depends on the previous step. 966 * O ? O------>O------>O------>NULL 967 * | | 968 * reference loop 969 */ 970 reference = loop ; 971 loop = loop->next ; 972 scatt_reference = scatt_loop ; 973 scatt_loop = scatt_loop->next ; 974 975 /* We mark the new reference as being blocked or not, if will be freed 976 * during the next while loop execution. 977 */ 978 if (blocked) 979 blocked_reference = 1 ; 980 else 981 blocked_reference = 0 ; 982 } 983 984 /* We free the last blocked reference if any (since in the while loop it was 985 * freed during the next loop execution, it was not possible to free the 986 * last one inside). 987 */ 988 if (blocked_reference) 989 { reference->next = NULL ; 990 cloog_loop_free(reference) ; 991 cloog_scattering_free(scatt_reference->scatt); 992 free(scatt_reference) ; 993 } 994 995 if (nb_blocked != 0) 996 cloog_msg(options, CLOOG_INFO, "%d domains have been blocked.\n", nb_blocked); 997} 998 999 1000/** 1001 * cloog_program_extract_scalars function: 1002 * this functions finds and removes the dimensions of the scattering functions 1003 * when they are scalar (i.e. of the shape "dim + scalar = 0") for all 1004 * scattering functions. The reason is that the processing of such dimensions 1005 * is trivial and do not need neither a row and a column in the matrix 1006 * representation of the domain (this will save memory) neither the full 1007 * Quillere processing (this will save time). The scalar dimensions data are 1008 * dispatched in the CloogProgram structure (the boolean vector scaldims will 1009 * say which original dimensions are scalar or not) and to the CloogBlock 1010 * structures (each one has a scaldims vector that contains the scalar values). 1011 * - June 14th 2005: first developments. 1012 * - June 30th 2005: first version. 1013 */ 1014void cloog_program_extract_scalars(CloogProgram *program, 1015 CloogScatteringList *scattering, CloogOptions *options) 1016{ int i, j, scalar, current, nb_scaldims=0 ; 1017 CloogScatteringList *start; 1018 CloogScattering *old; 1019 CloogLoop *loop; 1020 CloogBlock * block ; 1021 1022 start = scattering ; 1023 1024 for (i=0;i<program->nb_scattdims;i++) 1025 { scalar = 1 ; 1026 scattering = start ; 1027 while (scattering != NULL) 1028 { if (!cloog_scattering_lazy_isscalar(scattering->scatt, i, NULL)) 1029 { scalar = 0 ; 1030 break ; 1031 } 1032 scattering = scattering->next ; 1033 } 1034 1035 if (scalar) 1036 { nb_scaldims ++ ; 1037 program->scaldims[i] = 1 ; 1038 } 1039 } 1040 1041 /* If there are no scalar dimensions, we can continue directly. */ 1042 if (!nb_scaldims) 1043 return ; 1044 1045 /* Otherwise, in each block, we have to put the number of scalar dimensions, 1046 * and to allocate the memory for the scalar values. 1047 */ 1048 for (loop = program->loop; loop; loop = loop->next) { 1049 block = loop->block; 1050 block->nb_scaldims = nb_scaldims ; 1051 block->scaldims = (cloog_int_t *)malloc(nb_scaldims*sizeof(cloog_int_t)); 1052 for (i=0;i<nb_scaldims;i++) 1053 cloog_int_init(block->scaldims[i]); 1054 } 1055 1056 /* Then we have to fill these scalar values, so we can erase those dimensions 1057 * from the scattering functions. It's easier to begin with the last one, 1058 * since there would be an offset otherwise (if we remove the i^th dimension, 1059 * then the next one is not the (i+1)^th but still the i^th...). 1060 */ 1061 current = nb_scaldims - 1 ; 1062 for (i=program->nb_scattdims-1;i>=0;i--) 1063 if (program->scaldims[i]) 1064 { 1065 scattering = start ; 1066 for (loop = program->loop; loop; loop = loop->next) { 1067 block = loop->block; 1068 if (!cloog_scattering_lazy_isscalar(scattering->scatt, i, 1069 &block->scaldims[current])) { 1070 /* We should have found a scalar value: if not, there is an error. */ 1071 cloog_die("dimension %d is not scalar as expected.\n", i); 1072 } 1073 scattering = scattering->next ; 1074 } 1075 1076 scattering = start ; 1077 while (scattering != NULL) { 1078 old = scattering->scatt; 1079 scattering->scatt = cloog_scattering_erase_dimension(old, i); 1080 cloog_scattering_free(old); 1081 scattering = scattering->next ; 1082 } 1083 current-- ; 1084 } 1085 1086 /* We postprocess the scaldims array in such a way that each entry is how 1087 * many scalar dimensions follows + 1 (the current one). This will make 1088 * some other processing easier (e.g. knowledge of some offsets). 1089 */ 1090 for (i=0;i<program->nb_scattdims-1;i++) 1091 { if (program->scaldims[i]) 1092 { j = i + 1 ; 1093 while ((j < program->nb_scattdims) && program->scaldims[j]) 1094 { program->scaldims[i] ++ ; 1095 j ++ ; 1096 } 1097 } 1098 } 1099 1100 if (nb_scaldims != 0) 1101 cloog_msg(options, CLOOG_INFO, "%d dimensions (over %d) are scalar.\n", 1102 nb_scaldims,program->nb_scattdims) ; 1103} 1104 1105 1106/** 1107 * cloog_program_scatter function: 1108 * This function adds the scattering (scheduling) informations in a program. 1109 * If names is NULL, this function create names itself such that the i^th 1110 * name is ci. 1111 * - November 6th 2001: first version. 1112 */ 1113void cloog_program_scatter(CloogProgram *program, 1114 CloogScatteringList *scattering, CloogOptions *options) 1115{ int scattering_dim, scattering_dim2, not_enough_constraints=0 ; 1116 CloogLoop * loop ; 1117 1118 if ((program != NULL) && (scattering != NULL)) 1119 { loop = program->loop ; 1120 1121 /* We compute the scattering dimension and check it is >=0. */ 1122 scattering_dim = cloog_scattering_dimension(scattering->scatt, loop->domain); 1123 if (scattering_dim < 0) 1124 cloog_die("scattering has not enough dimensions.\n"); 1125 if (!cloog_scattering_fully_specified(scattering->scatt, loop->domain)) 1126 not_enough_constraints ++ ; 1127 1128 /* The scattering dimension may have been modified by scalar extraction. */ 1129 scattering_dim = cloog_scattering_dimension(scattering->scatt, loop->domain); 1130 1131 /* Finally we scatter all loops. */ 1132 cloog_loop_scatter(loop, scattering->scatt); 1133 loop = loop->next ; 1134 scattering = scattering->next ; 1135 1136 while ((loop != NULL) && (scattering != NULL)) 1137 { scattering_dim2 = cloog_scattering_dimension(scattering->scatt, 1138 loop->domain); 1139 if (scattering_dim2 != scattering_dim) 1140 cloog_die("scattering dimensions are not the same.\n") ; 1141 if (!cloog_scattering_fully_specified(scattering->scatt, loop->domain)) 1142 not_enough_constraints ++ ; 1143 1144 cloog_loop_scatter(loop, scattering->scatt); 1145 loop = loop->next ; 1146 scattering = scattering->next ; 1147 } 1148 if ((loop != NULL) || (scattering != NULL)) 1149 cloog_msg(options, CLOOG_WARNING, 1150 "there is not a scattering for each statement.\n"); 1151 1152 if (not_enough_constraints) 1153 cloog_msg(options, CLOOG_WARNING, "not enough constraints for " 1154 "%d scattering function(s).\n",not_enough_constraints) ; 1155 } 1156} 1157