source/program.c

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