1Dear Dr. Bastoul, 2 3At the university of Ghent, we are starting to look 4at automatic optimization of loops to optimize the implementation 5in an FPGA. With the advent of your Cloog tool, we think 6it becomes possible to use the polyhedral model 7for the kind of optimizations we are thinking about, instead of using 8optimizations based on transforming abstract syntax trees. 9 10As a first test, we started with the representation of a 11wavelet decoder loop kernel in Cloog format. We do this 12by starting from a Fortran77-description, parse it 13using our FPT compiler and PolyAst-library, and then 14generate the Cloog data structures. Then we use 15the function cloog_program_dump_cloog to obtain an 16ASCII-file representing the code in Cloog-format. 17 18However, when trying to read in the generated file, 19we found that the generated file was incorrect, and 20I think the cause is in two small bugs in the 21function cloog_program_dump_cloog. After I've 22corrected them, the generated file seems correct 23(i.e. cloog can correctly read the generated file). 24 25I've attached the adapted program.c source file. 26I only changed the function cloog_program_dump_cloog, 27and now it looks as follows: 28 29void cloog_program_dump_cloog(FILE * foo, CloogProgram * program) 30{ int i, j ; 31 Matrix * matrix ; 32 Polyhedron * polyhedron ; 33 CloogLoop * loop ; 34 35 fprintf(foo, 36 "# CLooG -> CLooG\n" 37 "# This is an automatic dump of an input file from a CloogProgram data\n" 38 "# structure. It can be correct ONLY if dumped before loop generation.\n") ; 39 40 /* Language. */ 41 if (program->language == 'c') 42 fprintf(foo,"# Langage: C\n") ; 43 else 44 fprintf(foo,"# Langage: FORTRAN\n") ; 45 fprintf(foo,"%c\n\n",program->language) ; 46 47 /* Context. */ 48 fprintf(foo,"# Context (%d parameter(s)):\n",program->context->Dimension) ; 49 matrix = cloog_domain_domain2matrix(program->context) ; 50 cloog_domain_matrix_print(foo,matrix); 51 cloog_domain_matrix_free(matrix); 52 fprintf(foo,"1 # Parameter name(s)\n") ; 53 for (i=0;i<program->names->nb_parameters;i++) 54 fprintf(foo,"%s ",program->names->parameters[i]) ; 55 56 /* Statement number. */ 57 i = 0 ; 58 loop = program->loop ; 59 while (loop != NULL) 60 { i++ ; 61 loop = loop->next ; 62 } 63 fprintf(foo,"\n\n# Statement number:\n%d\n\n",i) ; 64 65 /* Iteration domains. */ 66 i = 1 ; 67 loop = program->loop ; 68 while (loop != NULL) 69 { /* Name of the domain. */ 70 fprintf(foo,"# Iteration domain of statement %d.\n",i) ; 71 72 /* Number of polyhedron inside the union of disjoint polyhedra. */ 73 j = 0 ; 74 polyhedron = /* KB 15.05.2005 remove program->, since otherwise 75 the number of polytopes describing the iteration 76 space of the first loop will be printed, instead 77 of the number of polytopes for the current loop. program->*/loop->domain ; 78 while (polyhedron != NULL) 79 { j++ ; 80 polyhedron = polyhedron->next ; 81 } 82 fprintf(foo,"%d\n",j) ; 83 84 /* The polyhedra themselves. */ 85 polyhedron = loop->domain ; 86 while (polyhedron != NULL) 87 { matrix = cloog_domain_domain2matrix(polyhedron) ; 88 cloog_domain_matrix_print(foo,matrix); 89 cloog_domain_matrix_free(matrix); 90 polyhedron = polyhedron->next ; 91 } 92 /* KB 15.05.2005 : options should be printed once per statement, not once 93 per polytope */ 94 fprintf(foo,"0 0 0 # For future options.\n\n") ; 95 i++ ; 96 loop = loop->next ; 97 } 98 fprintf(foo,"\n1 # Iterator name(s)\n") ; 99 for (i=0;i<program->names->nb_iterators;i++) 100 fprintf(foo,"%s ",program->names->iterators[i]) ; 101 fprintf(foo,"\n\n") ; 102 103 /* Scattering functions (none since included inside domains). */ 104 fprintf(foo,"# No scattering functions.\n0\n\n") ; 105} 106 107 108The two changes are indicated by comments starting with the letters 'KB'. 109 110I'm sending you these changes, so that they can be incorporated in the 111next version of cloog, if you find them to be correct. 112 113with kinds regards, 114 115Kristof Beyls 116 117P.S.: I'm currently studying your work about loop chunking, since I'll 118need some kind of generalized loop tiling transformation that extends over 119multiple loop nests, to get an efficient implementation of the wavelet 120code in an FPGA. 121 122 123-- -------------------------------------------------------------------- Parallel Information Systems Tel: +32(9)2649528 Universiteit Gent Fax: +32(9)2643594 St.-Pietersnieuwstraat 41 E-mail: Kristof.Beyls@elis.ugent.be B-9000 Gent, Belgium http://www.elis.ugent.be/~kbeyls -------------------------------------------------------------------- 124 125 126 127 128 /**-------------------------------------------------------------------** 129 ** CLooG ** 130 **-------------------------------------------------------------------** 131 ** program.c ** 132 **-------------------------------------------------------------------** 133 ** First version: october 25th 2001 ** 134 **-------------------------------------------------------------------**/ 135 136 137/****************************************************************************** 138 * CLooG : the Chunky Loop Generator (experimental) * 139 ****************************************************************************** 140 * * 141 * Copyright (C) 2001 Cedric Bastoul * 142 * * 143 * This is free software; you can redistribute it and/or modify it under the * 144 * terms of the GNU General Public License as published by the Free Software * 145 * Foundation; either version 2 of the License, or (at your option) any later * 146 * version. * 147 * * 148 * This software is distributed in the hope that it will be useful, but * 149 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY * 150 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * 151 * for more details. * 152 * * 153 * You should have received a copy of the GNU General Public License along * 154 * with software; if not, write to the Free Software Foundation, Inc., * 155 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * 156 * * 157 * CLooG, the Chunky Loop Generator * 158 * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr * 159 * * 160 ******************************************************************************/ 161/* CAUTION: the english used for comments is probably the worst you ever read, 162 * please feel free to correct and improve it ! 163 */ 164 165 166# include <sys/types.h> 167# include <sys/time.h> 168# include <sys/resource.h> 169# include <stdlib.h> 170# include <stdio.h> 171# include <string.h> 172# include <ctype.h> 173# include "../include/cloog/cloog.h" 174 175 176/****************************************************************************** 177 * Structure display function * 178 ******************************************************************************/ 179 180/* cloog_program_print function: 181 * This function prints the content of a CloogProgram structure (program) into a 182 * file (foo, possibly stdout). 183 */ 184void cloog_program_print(FILE * foo, CloogProgram * program) 185{ fprintf(foo,"Program:\n") ; 186 fprintf(foo,"Language %c.\n",program->language) ; 187 fprintf(foo,"Scattering dimension number = %d.\n",program->scattdims) ; 188 189 cloog_names_print(foo,program->names) ; 190 191 fprintf(foo,"Under the context:\n") ; 192 cloog_domain_print(foo,program->context) ; 193 fprintf(foo,"\n") ; 194 cloog_loop_print(foo,program->loop) ; 195} 196 197 198/* cloog_program_dump_cloog function: 199 * This function dumps a CloogProgram structure supposed to be completely 200 * filled in a CLooG input file (foo possibly stdout) such as CLooG can 201 * rebuild almost exactly the data structure from the input file (the number 202 * of scattering functions is lost since they are included inside the 203 * iteration domains, this can only lead to a less beautiful pretty printing). 204 * 27 june 2003: first version. 205 */ 206void cloog_program_dump_cloog(FILE * foo, CloogProgram * program) 207{ int i, j ; 208 Matrix * matrix ; 209 Polyhedron * polyhedron ; 210 CloogLoop * loop ; 211 212 fprintf(foo, 213 "# CLooG -> CLooG\n" 214 "# This is an automatic dump of an input file from a CloogProgram data\n" 215 "# structure. It can be correct ONLY if dumped before loop generation.\n") ; 216 217 /* Language. */ 218 if (program->language == 'c') 219 fprintf(foo,"# Langage: C\n") ; 220 else 221 fprintf(foo,"# Langage: FORTRAN\n") ; 222 fprintf(foo,"%c\n\n",program->language) ; 223 224 /* Context. */ 225 fprintf(foo,"# Context (%d parameter(s)):\n",program->context->Dimension) ; 226 matrix = cloog_domain_domain2matrix(program->context) ; 227 cloog_domain_matrix_print(foo,matrix); 228 cloog_domain_matrix_free(matrix); 229 fprintf(foo,"1 # Parameter name(s)\n") ; 230 for (i=0;i<program->names->nb_parameters;i++) 231 fprintf(foo,"%s ",program->names->parameters[i]) ; 232 233 /* Statement number. */ 234 i = 0 ; 235 loop = program->loop ; 236 while (loop != NULL) 237 { i++ ; 238 loop = loop->next ; 239 } 240 fprintf(foo,"\n\n# Statement number:\n%d\n\n",i) ; 241 242 /* Iteration domains. */ 243 i = 1 ; 244 loop = program->loop ; 245 while (loop != NULL) 246 { /* Name of the domain. */ 247 fprintf(foo,"# Iteration domain of statement %d.\n",i) ; 248 249 /* Number of polyhedron inside the union of disjoint polyhedra. */ 250 j = 0 ; 251 polyhedron = /* KB 15.05.2005 remove program->, since otherwise 252 the number of polytopes describing the iteration 253 space of the first loop will be printed, instead 254 of the number of polytopes for the current loop. program->*/loop->domain ; 255 while (polyhedron != NULL) 256 { j++ ; 257 polyhedron = polyhedron->next ; 258 } 259 fprintf(foo,"%d\n",j) ; 260 261 /* The polyhedra themselves. */ 262 polyhedron = loop->domain ; 263 while (polyhedron != NULL) 264 { matrix = cloog_domain_domain2matrix(polyhedron) ; 265 cloog_domain_matrix_print(foo,matrix); 266 cloog_domain_matrix_free(matrix); 267 polyhedron = polyhedron->next ; 268 } 269 /* KB 15.05.2005 : options should be printed once per statement, not once 270 per polytope */ 271 fprintf(foo,"0 0 0 # For future options.\n\n") ; 272 i++ ; 273 loop = loop->next ; 274 } 275 fprintf(foo,"\n1 # Iterator name(s)\n") ; 276 for (i=0;i<program->names->nb_iterators;i++) 277 fprintf(foo,"%s ",program->names->iterators[i]) ; 278 fprintf(foo,"\n\n") ; 279 280 /* Scattering functions (none since included inside domains). */ 281 fprintf(foo,"# No scattering functions.\n0\n\n") ; 282} 283 284 285/* cloog_program_dump_loopgen function: 286 * This function dumps a CloogProgram structure supposed to be completely 287 * filled in a LoopGen input file (foo possibly stdout) such as LoopGen can 288 * generate the code for this problem. If the user of CLooG had the bad idea 289 * to put the scattering functions directly inside the iteration domains, the 290 * time dimension of LoopGen is supposed to be 1. 291 * 27 june 2003: first version (should work but do not...). 292 */ 293void cloog_program_dump_loopgen(FILE * foo, CloogProgram * program) 294{ int i, j, time ; 295 Matrix * matrix ; 296 Polyhedron * polyhedron ; 297 CloogLoop * loop ; 298 299 /* Statement number and time dimensions. */ 300 i = 0 ; 301 loop = program->loop ; 302 while (loop != NULL) 303 { i++ ; 304 loop = loop->next ; 305 } 306 if (program->scattdims) 307 time = program->scattdims ; 308 else 309 time = 1 ; 310 fprintf(foo,"%d %d 1\n\n",i,time) ; 311 312 fprintf(foo, 313 "# CLooG -> LoopGen\n" 314 "# This is an automatic dump of an input file from a CloogProgram data\n" 315 "# structure. It can be correct ONLY if dumped before loop generation.\n\n") ; 316 317 /* Context. */ 318 fprintf(foo,"# Context (%d parameter(s)):\n1\n",program->context->Dimension) ; 319 matrix = cloog_domain_domain2matrix(program->context) ; 320 cloog_domain_matrix_print(foo,matrix); 321 cloog_domain_matrix_free(matrix); 322 fprintf(foo,"\n") ; 323 324 /* Iteration domains. */ 325 i = 1 ; 326 loop = program->loop ; 327 while (loop != NULL) 328 { /* Number of polyhedron inside the union of disjoint polyhedra. */ 329 j = 0 ; 330 polyhedron = program->loop->domain ; 331 while (polyhedron != NULL) 332 { j++ ; 333 polyhedron = polyhedron->next ; 334 } 335 fprintf(foo,"%d\n",j) ; 336 337 /* Name of the domain. */ 338 fprintf(foo,"# Iteration domain of statement %d.\n",i) ; 339 340 /* The polyhedra themselves. */ 341 polyhedron = loop->domain ; 342 while (polyhedron != NULL) 343 { matrix = cloog_domain_domain2matrix(polyhedron) ; 344 cloog_domain_matrix_print(foo,matrix); 345 cloog_domain_matrix_free(matrix); 346 polyhedron = polyhedron->next ; 347 } 348 fprintf(foo,"\n") ; 349 i++ ; 350 loop = loop->next ; 351 } 352} 353 354 355/* cloog_program_dump_omega function: 356 * This function dumps a CloogProgram structure supposed to be completely 357 * filled in a OMEGA Calculator file (foo possibly stdout) such as OC can 358 * generate the code for this problem. If the user of CLooG had the bad idea 359 * to put the scattering functions directly inside the iteration domains, they 360 * will be added in the corresponding iteration domain for OMEGA with some 361 * equalities, so he need to pray (because OMEGA and equalities are really 362 * not friends)... 363 * December 7th 2003: first version. 364 */ 365void cloog_program_dump_omega(FILE * foo, CloogProgram * program) 366{ int i, j, k, first, nb_iterators, nb_parameters, max_depth=0, 367 statement_number ; 368 Polyhedron * polyhedron ; 369 CloogLoop * loop ; 370 Value sign ; 371 372 fprintf(foo, 373 "# CLooG -> OMEGA\n" 374 "# This is an automatic dump of an input file from a CloogProgram data\n" 375 "# structure. It can be correct ONLY if dumped before loop generation.\n\n") ; 376 377 nb_parameters = program->context->Dimension ; 378 379 /* Context. */ 380 fprintf(foo,"# Context (%d parameter(s)).\n",nb_parameters) ; 381 if (nb_parameters >= 1) 382 { fprintf(foo,"Symbolic %s",program->names->parameters[0]) ; 383 for (i=1;i<nb_parameters;i++) 384 fprintf(foo,", %s",program->names->parameters[i]) ; 385 fprintf(foo," ;\n\n") ; 386 } 387 388 /* Statements. */ 389 fprintf(foo,"# Iteration domains:\n") ; 390 statement_number = 1 ; 391 loop = program->loop ; 392 while (loop != NULL) 393 { nb_iterators = loop->domain->Dimension - nb_parameters ; 394 if (nb_iterators > max_depth) 395 max_depth = nb_iterators ; 396 397 /* Name of the statement. */ 398 fprintf(foo,"IS%d0:={",statement_number) ; 399 400 /* Dimensions. */ 401 fprintf(foo,"[") ; 402 if (nb_iterators-program->scattdims >= 1) 403 { fprintf(foo,"%s",program->names->iterators[program->scattdims]) ; 404 for (j=program->scattdims+1;j<nb_iterators;j++) 405 fprintf(foo,",%s",program->names->iterators[j]) ; 406 } 407 fprintf(foo,"]: ") ; 408 409 /* Number of polyhedron inside the union of disjoint polyhedra 410 * (must be 1 for OMEGA, we just check it). 411 */ 412 j = 0 ; 413 polyhedron = program->loop->domain ; 414 while (polyhedron != NULL) 415 { j++ ; 416 polyhedron = polyhedron->next ; 417 } 418 if (j > 1) 419 { fprintf(stderr,"[CLooG]ERROR: the problem cannot be dumped for OMEGA.\n"); 420 exit(0) ; 421 } 422 423 /* The polyhedra themselves. */ 424 polyhedron = loop->domain ; 425 for (j=program->scattdims;j<polyhedron->NbConstraints;j++) 426 { first = 1 ; 427 428 if (j > program->scattdims) 429 fprintf(foo," && ") ; 430 431 /* The coefficients of the iterators and the parameters. */ 432 for (k=1;k<=polyhedron->Dimension;k++) 433 if (polyhedron->Constraint[j][k] != 0) 434 { if (!first) 435 { if (polyhedron->Constraint[j][k] > 0) 436 fprintf(foo,"+") ; 437 } 438 else 439 first = 0 ; 440 441 if ((polyhedron->Constraint[j][k] != 1) && 442 (polyhedron->Constraint[j][k] != -1)) 443 fprintf(foo,VALUE_FMT,polyhedron->Constraint[j][k]) ; 444 else 445 if (polyhedron->Constraint[j][k] == -1) 446 fprintf(foo,"-") ; 447 448 if (k<=nb_iterators) 449 fprintf(foo,"%s",program->names->iterators[k-1]) ; 450 else 451 fprintf(foo,"%s",program->names->parameters[k-1-nb_iterators]) ; 452 } 453 454 /* The constant (k has the good value after the loop). */ 455 if (polyhedron->Constraint[j][k] != 0) 456 { if (!first) 457 { if (polyhedron->Constraint[j][k] > 0) 458 fprintf(foo,"+") ; 459 } 460 fprintf(foo,VALUE_FMT,polyhedron->Constraint[j][k]) ; 461 } 462 463 /* The (in)equality to 0. */ 464 if (polyhedron->Constraint[j][0] == 0) 465 fprintf(foo,"=0") ; 466 else 467 fprintf(foo,">=0") ; 468 } 469 fprintf(foo,"} ;\n") ; 470 471 if ((loop = loop->next) != NULL) 472 statement_number ++ ; 473 } 474 475 /* Scattering functions (scheduling for OMEGA). */ 476 loop = program->loop ; 477 if (program->scattdims > 0) 478 { statement_number = 1 ; 479 loop = program->loop ; 480 fprintf(foo,"\n# Schedules:\n") ; 481 482 while (loop != NULL) 483 { nb_iterators = loop->domain->Dimension - nb_parameters ; 484 if (nb_iterators > max_depth) 485 max_depth = nb_iterators ; 486 487 /* Name of the statement. */ 488 fprintf(foo,"T%d0:={",statement_number) ; 489 490 /* Dimensions. */ 491 fprintf(foo,"[") ; 492 if (nb_iterators-program->scattdims >= 1) 493 { fprintf(foo,"%s",program->names->iterators[program->scattdims]) ; 494 for (j=program->scattdims+1;j<nb_iterators;j++) 495 fprintf(foo,",%s",program->names->iterators[j]) ; 496 } 497 fprintf(foo,"] -> [") ; 498 499 /* The functions themselves. */ 500 polyhedron = loop->domain ; 501 for (j=0;j<program->scattdims;j++) 502 { first = 1 ; 503 504 if (j > 0) 505 fprintf(foo,",") ; 506 507 /* We assume that the coefficient of the scattering iterator is 1. */ 508 if ((polyhedron->Constraint[j][j+1] != 1) && 509 (polyhedron->Constraint[j][j+1] != -1)) 510 { fprintf(stderr,"[CLooG]ERROR: scattering dimension coefficients must " 511 "be 1 or -1to dump for OMEGA.") ; 512 exit(0) ; 513 } 514 515 /* Depending on the sign of the scattering coefficient, the 516 * coefficient for the scheduling expression. 517 */ 518 if (polyhedron->Constraint[j][j+1] == 1) 519 sign = -1 ; 520 else 521 sign = 1 ; 522 523 /* The coefficients of the iterators and the parameters. */ 524 for (k=program->scattdims+1;k<=polyhedron->Dimension;k++) 525 if (polyhedron->Constraint[j][k] != 0) 526 { if (!first) 527 { if (sign*polyhedron->Constraint[j][k] > 0) 528 fprintf(foo,"+") ; 529 } 530 else 531 first = 0 ; 532 533 if ((polyhedron->Constraint[j][k] != 1) && 534 (polyhedron->Constraint[j][k] != -1)) 535 fprintf(foo,VALUE_FMT,sign*polyhedron->Constraint[j][k]) ; 536 else 537 if (sign*polyhedron->Constraint[j][k] == -1) 538 fprintf(foo,"-") ; 539 540 if (k<=nb_iterators) 541 fprintf(foo,"%s",program->names->iterators[k-1]) ; 542 else 543 fprintf(foo,"%s",program->names->parameters[k-1-nb_iterators]) ; 544 } 545 546 /* The constant (k has the good value after the loop). */ 547 if (polyhedron->Constraint[j][k] != 0) 548 { if (!first) 549 { if (sign*polyhedron->Constraint[j][k] > 0) 550 fprintf(foo,"+") ; 551 } 552 fprintf(foo,VALUE_FMT,sign*polyhedron->Constraint[j][k]) ; 553 } 554 else 555 { if (first) 556 fprintf(foo,"0") ; 557 } 558 } 559 560 /* The scheduling expressions 'a la CLooG' end with the original 561 * dimensions... 562 */ 563 if (nb_iterators >= 1) 564 { for (j=program->scattdims;j<nb_iterators;j++) 565 fprintf(foo,",%s",program->names->iterators[j]) ; 566 } 567 568 /* ...and possibly zeros in order for the scheduling functions to have 569 * the same dimension number. 570 */ 571 for (j=nb_iterators;j<max_depth;j++) 572 fprintf(foo,",0") ; 573 574 fprintf(foo,"]} ;\n") ; 575 576 if ((loop = loop->next) != NULL) 577 statement_number ++ ; 578 } 579 } 580 581 /* The codegen call. */ 582 fprintf(foo,"\n# CodeGen call:\n") ; 583 fprintf(foo,"codegen %d ",max_depth) ; 584 if (statement_number > 0) 585 { if (program->scattdims != 0) 586 fprintf(foo,"T10:") ; 587 fprintf(foo,"IS10") ; 588 for (i=1;i<statement_number;i++) 589 { fprintf(foo,", ") ; 590 if (program->scattdims != 0) 591 fprintf(foo,"T%d0:",i+1) ; 592 fprintf(foo,"IS%d0",i+1) ; 593 } 594 } 595 fprintf(foo," ;\n") ; 596} 597 598 599/* cloog_program_pprint function: 600 * This function prints the content of a CloogProgram structure (program) into a 601 * file (foo, possibly stdout), in a C-like language. 602 */ 603void cloog_program_pprint(foo, program, options) 604FILE * foo ; 605CloogProgram * program ; 606CloogOptions * options ; 607{ CloogInfos * infos ; 608 609 infos = (CloogInfos *)malloc(sizeof(CloogInfos)) ; 610 infos->nb_iterators = program->names->nb_iterators ; 611 infos->nb_parameters = program->names->nb_parameters ; 612 infos->iterators = program->names->iterators ; 613 infos->parameters = program->names->parameters ; 614 infos->scattdims = program->scattdims ; 615 infos->options = options ; 616 /* Allocation for the array of strides, there is a +1 since the statement can 617 * be included inside an external loop without iteration domain. 618 */ 619 infos->stride =(Value *)malloc((infos->nb_iterators+1)*sizeof(Value)) ; 620 621 if (program->language == 'f') 622 infos->language = LANGUAGE_FORTRAN ; 623 else 624 infos->language = LANGUAGE_C ; 625 626 if (program->language == 'f') 627 fprintf(foo,"! Generated from %s by CLooG v%s %s bits in %.2fs.\n", 628 options->name,CLOOG_RELEASE,CLOOG_VERSION,options->time) ; 629 else 630 fprintf(foo,"/* Generated from %s by CLooG v%s %s bits in %.2fs. */\n", 631 options->name,CLOOG_RELEASE,CLOOG_VERSION,options->time) ; 632 633 pprint(foo,program->loop,NULL,1,0,infos) ; 634 635 free(infos->stride) ; 636 free(infos) ; 637} 638 639 640/****************************************************************************** 641 * Memory deallocation function * 642 ******************************************************************************/ 643 644 645/* cloog_program_free function: 646 * This function frees the allocated memory for a CloogProgram structure. 647 */ 648void cloog_program_free(CloogProgram * program) 649{ cloog_names_free(program->names) ; 650 cloog_loop_free(program->loop) ; 651 cloog_domain_free(program->context) ; 652 free(program) ; 653} 654 655 656/****************************************************************************** 657 * Reading function * 658 ******************************************************************************/ 659 660 661/* cloog_program_read function: 662 * This function read the informations to put in a CloogProgram structure from 663 * a file (foo, possibly stdin). It returns a pointer to a CloogProgram 664 * structure containing the read informations. 665 * October 25th 2001: first version. 666 * September 9th 2002: - the big reading function is now splitted in several 667 * functions (one per read data structure). 668 * - adaptation to the new file format with naming. 669 */ 670CloogProgram * cloog_program_read(FILE * foo) 671{ int i, nb_statements, nb_parameters, nb_iterators ; 672 char s[MAX_STRING], language, ** scat_names, prefix[2]={'c','\0'} ; 673 CloogLoop * current, * next ; 674 CloogNames * names ; 675 CloogDomainList * scattering ; 676 CloogProgram * p ; 677 678 /* Memory allocation for the CloogProgram structure. */ 679 p = (CloogProgram *)malloc(sizeof(CloogProgram)) ; 680 if (p == NULL) 681 { fprintf(stderr, "[CLooG]ERROR: memory overflow.\n") ; 682 exit(1) ; 683 } 684 685 /* Memory allocation for the CloogNames structure. */ 686 names = (CloogNames *)malloc(sizeof(CloogNames)) ; 687 if (names == NULL) 688 { fprintf(stderr, "[CLooG]ERROR: memory overflow.\n") ; 689 exit(1) ; 690 } 691 692 /* First of all, we read the language to use. */ 693 while (fgets(s,MAX_STRING,foo) == 0) ; 694 while ((*s=='#'||*s=='\n') || (sscanf(s," %c",&language)<1)) 695 fgets(s,MAX_STRING,foo) ; 696 p->language = language ; 697 698 /* We then read the context data. */ 699 p->context = cloog_domain_read(foo) ; 700 nb_parameters = p->context->Dimension ; 701 702 /* Reading of the parameter names. */ 703 names->nb_parameters = nb_parameters ; 704 names->parameters = cloog_names_read(foo,nb_parameters,NULL,FIRST_PARAMETER) ; 705 706 /* We read the statement number. */ 707 while (fgets(s,MAX_STRING,foo) == 0) ; 708 while ((*s=='#'||*s=='\n') || (sscanf(s," %d",&nb_statements)<1)) 709 fgets(s,MAX_STRING,foo) ; 710 711 /*printf("%d ",nb_statements) ;*/ 712 713 /* Domains reading for each statement. */ 714 if (nb_statements > 0) 715 { /* Reading of the first domain. */ 716 p->loop = cloog_loop_read(foo,1,nb_parameters) ; 717 if (p->loop->domain != NULL) 718 nb_iterators = p->loop->domain->Dimension - nb_parameters ; 719 else 720 nb_iterators = 0 ; 721 722 /* And the same for each next domain. */ 723 current = p->loop ; 724 for (i=2;i<=nb_statements;i++) 725 { next = cloog_loop_read(foo,i,nb_parameters) ; 726 if (next->domain != NULL) 727 if (next->domain->Dimension - nb_parameters > nb_iterators) 728 nb_iterators = next->domain->Dimension - nb_parameters ; 729 730 current->next = next ; 731 current = current->next ; 732 } 733 734 /* Reading of the iterator names. */ 735 names->nb_iterators = nb_iterators ; 736 names->iterators = cloog_names_read(foo,nb_iterators,NULL,FIRST_ITERATOR) ; 737 p->names = names ; 738 739 /* Reading and puting the scattering data in program structure. */ 740 scattering = cloog_domain_list_read(foo) ; 741 742 if (scattering != NULL) 743 { if (cloog_domain_list_quick_same(scattering)) 744 { fprintf(stderr, "[CLooG]WARNING: some scattering functions are " 745 "similar.\n") ; 746 } 747 748 p->scattdims = scattering->domain->Dimension - p->loop->domain->Dimension; 749 scat_names = cloog_names_read(foo,p->scattdims,prefix,'1') ; 750 cloog_program_scatter(p,scattering,scat_names) ; 751 cloog_domain_list_free(scattering) ; 752 /* Now we can free scat_names since cloog_program_scatter copied it. */ 753 for (i=0;i<p->scattdims;i++) 754 free(scat_names[i]) ; 755 free(scat_names) ; 756 } 757 else 758 p->scattdims = 0 ; 759 } 760 else 761 { p->loop = NULL ; 762 p->names = NULL ; 763 } 764 765 return(p) ; 766} 767 768 769/****************************************************************************** 770 * Processing functions * 771 ******************************************************************************/ 772 773 774/* cloog_program_statement_count function: 775 * This function returns the number of statements in the whole program. This has 776 * nothing to do here, and I don't remember why and when I wrote it, anyway... 777 */ 778int cloog_program_statement_count(CloogLoop * start) 779{ int count=0 ; 780 CloogLoop * loop ; 781 CloogStatement * statement ; 782 783 loop = start ; 784 785 while (loop != NULL) 786 { if (loop->inner != NULL) 787 count += cloog_program_statement_count(loop->inner) ; 788 789 statement = loop->statement ; 790 791 while (statement != NULL) 792 { count ++ ; 793 statement = statement->next ; 794 } 795 loop = loop->next ; 796 } 797 798 return count ; 799} 800 801 802/* cloog_program_generate function: 803 * This function calls the Quillere algorithm for loop scanning. (see the 804 * Quillere paper) and calls the loop simplification function. 805 * - depth is the loop depth we want to optimize (guard free as possible), 806 * the first loop depth is 1 and anegative value is the infinity depth. 807 * - sep_level is the level number where we want to start loop separation. 808 * October 26th 2001: first version. 809 */ 810CloogProgram * cloog_program_generate(program, options) 811CloogProgram * program ; 812CloogOptions * options ; 813{ float time ; 814 struct rusage start, end ; 815 CloogLoop * loop, * simplified ; 816 817 if ((program->scattdims > options->l) && (options->l > 0)) 818 fprintf(stderr, "[CLooG]WARNING: -l depth is less than scattering dimension " 819 "number (the generated code may be illegal).\n") ; 820 821 if (program->loop == NULL) 822 return program ; 823 else 824 { loop = program->loop ; 825 getrusage(RUSAGE_SELF, &start) ; 826 827 /* Here we go ! */ 828 loop = cloog_loop_generate(loop,program->context,1, 829 program->context->Dimension,options) ; 830 831 getrusage(RUSAGE_SELF, &end) ; 832 /* We calculate the time spent in code generation. */ 833 time = (end.ru_utime.tv_usec - start.ru_utime.tv_usec)/(float)(MEGA) ; 834 time += (float)(end.ru_utime.tv_sec - start.ru_utime.tv_sec) ; 835 options->time = time ; 836 837 if (loop == NULL) 838 { program->loop = NULL ; 839 return program ; 840 } 841 else 842 { /*cloog_loop_print(stdout,loop) ;*/ 843 simplified = cloog_loop_simplify(loop,program->context,1, 844 program->context->Dimension); 845 program->loop = simplified ; 846 /*program->loop = loop ;*/ 847 return program ; 848 } 849 } 850} 851 852 853/* cloog_program_scatter function: 854 * This function adds the scattering (scheduling) informations in a program. 855 * If names is NULL, this function create names itself such that the i^th 856 * name is ci. 857 * November 6th 2001: first version. 858 */ 859void cloog_program_scatter(program, scattering, names) 860CloogProgram * program ; 861CloogDomainList * scattering ; 862char ** names ; 863{ int i, scattering_dim, scattering_dim2, new_dim, not_enough_constraints=0 ; 864 char ** iterators ; 865 CloogLoop * loop ; 866 867 if ((program != NULL) && (scattering != NULL)) 868 { loop = program->loop ; 869 870 /* We compute the scattering dimension and check it is >=0. */ 871 scattering_dim = scattering->domain->Dimension - loop->domain->Dimension ; 872 if (scattering_dim <= 0) 873 { fprintf(stderr, "[CLooG]ERROR: scattering has not enough dimensions.\n") ; 874 exit(1) ; 875 } 876 if (scattering_dim >= scattering->domain->NbConstraints) 877 not_enough_constraints ++ ; 878 879 /* We add scattering names in program->iterators. */ 880 new_dim = program->names->nb_iterators + scattering_dim ; 881 iterators = (char **)malloc(new_dim*sizeof(char *)) ; 882 if (iterators == NULL) 883 { fprintf(stderr, "[CLooG]ERROR: memory overflow.\n") ; 884 exit(1) ; 885 } 886 for (i=0;i<scattering_dim;i++) 887 { iterators[i] = (char *)malloc(MAX_NAME*sizeof(char)) ; 888 if (iterators[i] == NULL) 889 { fprintf(stderr, "[CLooG]ERROR: memory overflow.\n") ; 890 exit(1) ; 891 } 892 if (names != NULL) 893 strcpy(iterators[i],names[i]) ; 894 else 895 sprintf(iterators[i],"c%d",i+1) ; 896 } 897 for (i=scattering_dim;i<new_dim;i++) 898 iterators[i] = program->names->iterators[i-scattering_dim] ; 899 free(program->names->iterators) ; 900 program->names->iterators = iterators ; 901 902 /* We update nb_iterators. */ 903 program->names->nb_iterators = new_dim ; 904 905 /* Finally we scatter all loops. */ 906 cloog_loop_scatter(loop,scattering->domain) ; 907 loop = loop->next ; 908 scattering = scattering->next ; 909 910 while ((loop != NULL) && (scattering != NULL)) 911 { scattering_dim2 = scattering->domain->Dimension - loop->domain->Dimension; 912 if (scattering_dim2 != scattering_dim) 913 { fprintf(stderr, "[CLooG]ERROR: " 914 "scattering dimensions are not the same.\n") ; 915 exit(1) ; 916 } 917 if (scattering_dim2 >= scattering->domain->NbConstraints) 918 not_enough_constraints ++ ; 919 920 cloog_loop_scatter(loop,scattering->domain) ; 921 loop = loop->next ; 922 scattering = scattering->next ; 923 } 924 if ((loop != NULL) || (scattering != NULL)) 925 fprintf(stderr, "[CLooG]WARNING: " 926 "there is not a scattering for each statement.\n"); 927 928 if (not_enough_constraints) 929 fprintf(stderr, "[CLooG]WARNING: not enough constraints for " 930 "%d scattering function(s).\n",not_enough_constraints) ; 931 } 932} 933 934