source/scop.c

   1
   2     /*+-----------------------------------------------------------------**
   3      **                       OpenScop Library                          **
   4      **-----------------------------------------------------------------**
   5      **                            scop.c                               **
   6      **-----------------------------------------------------------------**
   7      **                   First version: 30/04/2008                     **
   8      **-----------------------------------------------------------------**
   9
  10
  11  *****************************************************************************
  12  * OpenScop: Structures and formats for polyhedral tools to talk together    *
  13  *****************************************************************************
  14  *    ,___,,_,__,,__,,__,,__,,_,__,,_,__,,__,,___,_,__,,_,__,                *
  15  *    /   / /  //  //  //  // /   / /  //  //   / /  // /  /|,_,             *
  16  *   /   / /  //  //  //  // /   / /  //  //   / /  // /  / / /\             *
  17  *  |~~~|~|~~~|~~~|~~~|~~~|~|~~~|~|~~~|~~~|~~~|~|~~~|~|~~~|/_/  \            *
  18  *  | G |C| P | = | L | P |=| = |C| = | = | = |=| = |=| C |\  \ /\           *
  19  *  | R |l| o | = | e | l |=| = |a| = | = | = |=| = |=| L | \# \ /\          *
  20  *  | A |a| l | = | t | u |=| = |n| = | = | = |=| = |=| o | |\# \  \         *
  21  *  | P |n| l | = | s | t |=| = |d| = | = | = | |   |=| o | | \# \  \        *
  22  *  | H | | y |   | e | o | | = |l|   |   | = | |   | | G | |  \  \  \       *
  23  *  | I | |   |   | e |   | |   | |   |   |   | |   | |   | |   \  \  \      *
  24  *  | T | |   |   |   |   | |   | |   |   |   | |   | |   | |    \  \  \     *
  25  *  | E | |   |   |   |   | |   | |   |   |   | |   | |   | |     \  \  \    *
  26  *  | * |*| * | * | * | * |*| * |*| * | * | * |*| * |*| * | /      \* \  \   *
  27  *  | O |p| e | n | S | c |o| p |-| L | i | b |r| a |r| y |/        \  \ /   *
  28  *  '---'-'---'---'---'---'-'---'-'---'---'---'-'---'-'---'          '--'    *
  29  *                                                                           *
  30  * Copyright (C) 2008 University Paris-Sud 11 and INRIA                      *
  31  *                                                                           *
  32  * (3-clause BSD license)                                                    *
  33  * Redistribution and use in source  and binary forms, with or without       *
  34  * modification, are permitted provided that the following conditions        *
  35  * are met:                                                                  *
  36  *                                                                           *
  37  * 1. Redistributions of source code must retain the above copyright notice, *
  38  *    this list of conditions and the following disclaimer.                  *
  39  * 2. Redistributions in binary form must reproduce the above copyright      *
  40  *    notice, this list of conditions and the following disclaimer in the    *
  41  *    documentation and/or other materials provided with the distribution.   *
  42  * 3. The name of the author may not be used to endorse or promote products  *
  43  *    derived from this software without specific prior written permission.  *
  44  *                                                                           *
  45  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR      *
  46  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES *
  47  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.   *
  48  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,          *
  49  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT  *
  50  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, *
  51  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY     *
  52  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT       *
  53  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF  *
  54  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.         *
  55  *                                                                           *
  56  * OpenScop Library, a library to manipulate OpenScop formats and data       *
  57  * structures. Written by:                                                   *
  58  * Cedric Bastoul     <Cedric.Bastoul@u-psud.fr> and                         *
  59  * Louis-Noel Pouchet <Louis-Noel.pouchet@inria.fr>                          *
  60  *                                                                           *
  61  *****************************************************************************/
  62
  63 # include <stdlib.h>
  64 # include <stdio.h>
  65 # include <ctype.h>
  66 # include <string.h>
  67
  68 #include <osl/macros.h>
  69 #include <osl/util.h>
  70 #include <osl/extensions/arrays.h>
  71 #include <osl/extensions/textual.h>
  72 #include <osl/strings.h>
  73 #include <osl/relation.h>
  74 #include <osl/interface.h>
  75 #include <osl/generic.h>
  76 #include <osl/statement.h>
  77 #include <osl/scop.h>
  78
  79
  80 /*+***************************************************************************
  81  *                         Structure display functions                       *
  82  *****************************************************************************/
  83
  84
  85 /**
  86  * osl_scop_idump function:
  87  * this function displays an osl_scop_t structure (*scop) into a
  88  * file (file, possibly stdout) in a way that trends to be understandable. It
  89  * includes an indentation level (level) in order to work with others
  90  * idump functions.
  91  * \param file  The file where the information has to be printed.
  92  * \param scop  The scop structure whose information has to be printed.
  93  * \param level Number of spaces before printing, for each line.
  94  */
  95 void osl_scop_idump(FILE * file, osl_scop_p scop, int level) {
  96   int j, first = 1;
  97
  98   // Go to the right level.
  99   for (j = 0; j < level; j++)
 100     fprintf(file, "|\t");
 101
 102   if (scop != NULL)
 103     fprintf(file, "+-- osl_scop_t\n");
 104   else
 105     fprintf(file, "+-- NULL scop\n");
 106
 107   while (scop != NULL) {
 108     if (!first) {
 109       // Go to the right level.
 110       for (j = 0; j < level; j++)
 111         fprintf(file, "|\t");
 112       fprintf(file, "|   osl_scop_t\n");
 113     }
 114     else
 115       first = 0;
 116
 117     // A blank line.
 118     for (j = 0; j <= level+1; j++)
 119       fprintf(file, "|\t");
 120     fprintf(file, "\n");
 121
 122     // Print the version.
 123     for (j = 0; j < level; j++)
 124       fprintf(file, "|\t");
 125     fprintf(file, "|\tVersion: %d\n", scop->version);
 126
 127     // A blank line.
 128     for (j = 0; j <= level+1; j++)
 129       fprintf(file, "|\t");
 130     fprintf(file, "\n");
 131
 132     // Print the language.
 133     for (j = 0; j < level; j++)
 134       fprintf(file, "|\t");
 135     fprintf(file, "|\tLanguage: %s\n", scop->language);
 136
 137     // A blank line.
 138     for (j = 0; j <= level+1; j++)
 139       fprintf(file, "|\t");
 140     fprintf(file, "\n");
 141
 142     // Print the context of the scop.
 143     osl_relation_idump(file, scop->context, level+1);
 144
 145     // Print the parameters.
 146     osl_generic_idump(file, scop->parameters, level+1);
 147
 148     // Print the statements.
 149     osl_statement_idump(file, scop->statement, level+1);
 150
 151     // Print the registered extension interfaces.
 152     osl_interface_idump(file, scop->registry, level+1);
 153
 154     // Print the extensions.
 155     osl_generic_idump(file, scop->extension, level+1);
 156
 157     scop = scop->next;
 158
 159     // Next line.
 160     if (scop != NULL) {
 161       for (j = 0; j <= level; j++)
 162         fprintf(file, "|\t");
 163       fprintf(file, "V\n");
 164     }
 165   }
 166
 167   // The last line.
 168   for (j = 0; j <= level; j++)
 169     fprintf(file, "|\t");
 170   fprintf(file, "\n");
 171 }
 172
 173
 174 /**
 175  * osl_scop_dump function:
 176  * this function prints the content of an osl_scop_t structure (*scop)
 177  * into a file (file, possibly stdout).
 178  * \param file The file where the information has to be printed.
 179  * \param scop The scop structure whose information has to be printed.
 180  */
 181 void osl_scop_dump(FILE * file, osl_scop_p scop) {
 182   osl_scop_idump(file, scop, 0);
 183 }
 184
 185
 186 /**
 187  * osl_scop_names function:
 188  * this function generates as set of names for all the dimensions
 189  * involved in a given scop.
 190  * \param[in] scop The scop (list) we have to generate names for.
 191  * \return A set of generated names for the input scop dimensions.
 192  */
 193 osl_names_p osl_scop_names(osl_scop_p scop) {
 194   int nb_parameters = OSL_UNDEFINED;
 195   int nb_iterators  = OSL_UNDEFINED;
 196   int nb_scattdims  = OSL_UNDEFINED;
 197   int nb_localdims  = OSL_UNDEFINED;
 198   int array_id      = OSL_UNDEFINED;
 199
 200   osl_scop_get_attributes(scop, &nb_parameters, &nb_iterators,
 201                           &nb_scattdims,  &nb_localdims, &array_id);
 202
 203   return osl_names_generate("P", nb_parameters,
 204                             "i", nb_iterators,
 205                             "c", nb_scattdims,
 206                             "l", nb_localdims,
 207                             "A", array_id);
 208 }
 209
 210
 211 /**
 212  * osl_scop_print function:
 213  * this function prints the content of an osl_scop_t structure (*scop)
 214  * into a file (file, possibly stdout) in the OpenScop textual format.
 215  * \param file The file where the information has to be printed.
 216  * \param scop The scop structure whose information has to be printed.
 217  */
 218 void osl_scop_print(FILE * file, osl_scop_p scop) {
 219   int parameters_backedup = 0;
 220   int arrays_backedup = 0;
 221   osl_strings_p parameters_backup = NULL;
 222   osl_strings_p arrays_backup = NULL;
 223   osl_names_p names;
 224   osl_arrays_p arrays;
 225
 226   if (scop == NULL) {
 227     fprintf(file, "# NULL scop\n");
 228     return;
 229   }
 230   else {
 231     fprintf(file, "# [File generated by the OpenScop Library %s]\n",
 232             OSL_RELEASE);
 233   }
 234
 235   if (osl_scop_integrity_check(scop) == 0)
 236     OSL_warning("OpenScop integrity check failed. Something may go wrong.");
 237
 238   // Generate the names for the various dimensions.
 239   names = osl_scop_names(scop);
 240
 241   while (scop != NULL) {
 242     // If possible, replace parameter names with scop parameter names.
 243     if (osl_generic_has_URI(scop->parameters, OSL_URI_STRINGS)) {
 244       parameters_backedup = 1;
 245       parameters_backup = names->parameters;
 246       names->parameters = scop->parameters->data;
 247     }
 248
 249     // If possible, replace array names with arrays extension names.
 250     arrays = osl_generic_lookup(scop->extension, OSL_URI_ARRAYS);
 251     if (arrays != NULL) {
 252       arrays_backedup = 1;
 253       arrays_backup = names->arrays;
 254       names->arrays = osl_arrays_to_strings(arrays);
 255     }
 256
 257     fprintf(file, "\n<"OSL_URI_SCOP">\n\n");
 258     fprintf(file, "# =============================================== "
 259                   "Global\n");
 260     fprintf(file, "# Language\n");
 261     fprintf(file, "%s\n\n", scop->language);
 262
 263     fprintf(file, "# Context\n");
 264     osl_relation_pprint(file, scop->context, names);
 265     fprintf(file, "\n");
 266
 267     osl_util_print_provided(file,
 268         osl_generic_has_URI(scop->parameters, OSL_URI_STRINGS),
 269         "Parameters are");
 270     osl_generic_print(file, scop->parameters);
 271
 272     fprintf(file, "\n# Number of statements\n");
 273     fprintf(file, "%d\n\n",osl_statement_number(scop->statement));
 274
 275     osl_statement_pprint(file, scop->statement, names);
 276
 277     if (scop->extension) {
 278       fprintf(file, "# =============================================== "
 279                     "Extensions\n");
 280       osl_generic_print(file, scop->extension);
 281     }
 282     fprintf(file, "\n</"OSL_URI_SCOP">\n\n");
 283
 284     // If necessary, switch back parameter names.
 285     if (parameters_backedup) {
 286       parameters_backedup = 0;
 287       names->parameters = parameters_backup;
 288     }
 289
 290     // If necessary, switch back array names.
 291     if (arrays_backedup) {
 292       arrays_backedup = 0;
 293       osl_strings_free(names->arrays);
 294       names->arrays = arrays_backup;
 295     }
 296
 297     scop = scop->next;
 298   }
 299
 300   osl_names_free(names);
 301 }
 302
 303
 304 /**
 305  * osl_scop_print_scoplib function:
 306  * this function prints the content of an osl_scop_t structure (*scop)
 307  * into a file (file, possibly stdout) in the ScopLib textual format.
 308  * \param file The file where the information has to be printed.
 309  * \param scop The scop structure whose information has to be printed.
 310  */
 311 void osl_scop_print_scoplib(FILE * file, osl_scop_p scop) {
 312   int parameters_backedup = 0;
 313   int arrays_backedup = 0;
 314   osl_strings_p parameters_backup = NULL;
 315   osl_strings_p arrays_backup = NULL;
 316   osl_names_p names;
 317   osl_arrays_p arrays;
 318
 319   if (scop == NULL) {
 320     fprintf(file, "# NULL scop\n");
 321     return;
 322   }
 323   else {
 324     fprintf(file, "# [File generated by the OpenScop Library %s]\n"
 325                   "# [SCoPLib format]\n",
 326                   OSL_RELEASE);
 327   }
 328
 329   if (osl_scop_check_compatible_scoplib(scop) == 0) {
 330     OSL_error("SCoP integrity check failed. Something may go wrong.");
 331     exit(1);
 332   }
 333
 334   // Generate the names for the various dimensions.
 335   names = osl_scop_names(scop);
 336
 337   while (scop != NULL) {
 338     // If possible, replace parameter names with scop parameter names.
 339     if (osl_generic_has_URI(scop->parameters, OSL_URI_STRINGS)) {
 340       parameters_backedup = 1;
 341       parameters_backup = names->parameters;
 342       names->parameters = scop->parameters->data;
 343     }
 344
 345     // If possible, replace array names with arrays extension names.
 346     arrays = osl_generic_lookup(scop->extension, OSL_URI_ARRAYS);
 347     if (arrays != NULL) {
 348       arrays_backedup = 1;
 349       arrays_backup = names->arrays;
 350       names->arrays = osl_arrays_to_strings(arrays);
 351     }
 352
 353     fprintf(file, "\nSCoP\n\n");
 354     fprintf(file, "# =============================================== "
 355                   "Global\n");
 356     fprintf(file, "# Language\n");
 357     fprintf(file, "%s\n\n", scop->language);
 358
 359     fprintf(file, "# Context\n");
 360
 361     osl_relation_pprint_scoplib(file, scop->context, names, 0, 0);
 362     fprintf(file, "\n");
 363
 364     osl_util_print_provided(file,
 365         osl_generic_has_URI(scop->parameters, OSL_URI_STRINGS),
 366         "Parameters are");
 367
 368     if (scop->parameters) {
 369       fprintf(file, "# Parameter names\n");
 370       osl_strings_print(file, scop->parameters->data);
 371     }
 372
 373     fprintf(file, "\n# Number of statements\n");
 374     fprintf(file, "%d\n\n",osl_statement_number(scop->statement));
 375
 376     osl_statement_pprint_scoplib(file, scop->statement, names);
 377
 378     if (scop->extension) {
 379       fprintf(file, "# =============================================== "
 380                     "Options\n");
 381       osl_generic_print_options_scoplib(file, scop->extension);
 382     }
 383
 384     // If necessary, switch back parameter names.
 385     if (parameters_backedup) {
 386       parameters_backedup = 0;
 387       names->parameters = parameters_backup;
 388     }
 389
 390     // If necessary, switch back array names.
 391     if (arrays_backedup) {
 392       arrays_backedup = 0;
 393       osl_strings_free(names->arrays);
 394       names->arrays = arrays_backup;
 395     }
 396
 397     scop = scop->next;
 398   }
 399
 400   osl_names_free(names);
 401 }
 402
 403
 404 /*****************************************************************************
 405  *                               Reading function                            *
 406  *****************************************************************************/
 407
 408
 409 /**
 410  * osl_scop_pread function ("precision read"):
 411  * this function reads a list of scop structures from a file (possibly stdin)
 412  * complying to the OpenScop textual format and returns a pointer to this
 413  * scop list. If some relation properties (number of input/output/local
 414  * dimensions and number of parameters) are undefined, it will define them
 415  * according to the available information.
 416  * \param[in] file      The file where the scop has to be read.
 417  * \param[in] registry  The list of known interfaces (others are ignored).
 418  * \param[in] precision The precision of the relation elements.
 419  * \return A pointer to the scop structure that has been read.
 420  */
 421 osl_scop_p osl_scop_pread(FILE * file, osl_interface_p registry,
 422                           int precision) {
 423   osl_scop_p list = NULL, current = NULL, scop;
 424   osl_statement_p stmt = NULL;
 425   osl_statement_p prev = NULL;
 426   osl_strings_p language;
 427   int nb_statements;
 428   char * tmp;
 429   int first = 1;
 430   int i;
 431
 432   if (file == NULL)
 433     return NULL;
 434
 435   while(1) {
 436     //
 437     // I. START TAG
 438     //
 439     tmp = osl_util_read_uptotag(file, NULL, OSL_URI_SCOP);
 440     if (tmp == NULL) {
 441       OSL_debug("no more scop in the file");
 442       break;
 443     }
 444     else {
 445       free(tmp);
 446     }
 447
 448     scop = osl_scop_malloc();
 449     scop->registry = osl_interface_clone(registry);
 450
 451     //
 452     // II. CONTEXT PART
 453     //
 454
 455     // Read the language.
 456     language = osl_strings_read(file);
 457     if (osl_strings_size(language) == 0)
 458       OSL_error("no language (backend) specified");
 459
 460     if (osl_strings_size(language) > 1)
 461       OSL_warning("uninterpreted information (after language)");
 462
 463     if (language != NULL) {
 464       OSL_strdup(scop->language, language->string[0]);
 465       osl_strings_free(language);
 466     }
 467
 468     // Read the context domain.
 469     scop->context = osl_relation_pread(file, precision);
 470
 471     // Read the parameters.
 472     if (osl_util_read_int(file, NULL) > 0)
 473       scop->parameters = osl_generic_read_one(file, scop->registry);
 474
 475     //
 476     // III. STATEMENT PART
 477     //
 478
 479     // Read the number of statements.
 480     nb_statements = osl_util_read_int(file, NULL);
 481
 482     for (i = 0; i < nb_statements; i++) {
 483       // Read each statement.
 484       stmt = osl_statement_pread(file, scop->registry, precision);
 485       if (scop->statement == NULL)
 486         scop->statement = stmt;
 487       else
 488         prev->next = stmt;
 489       prev = stmt;
 490     }
 491
 492     //
 493     // IV. EXTENSION PART (TO THE END TAG)
 494     //
 495
 496     // Read up the end tag (if any), and store extensions.
 497     scop->extension = osl_generic_read(file, scop->registry);
 498
 499     // Add the new scop to the list.
 500     if (first) {
 501       list = scop;
 502       first = 0;
 503     }
 504     else {
 505       current->next = scop;
 506     }
 507     current = scop;
 508   }
 509
 510   if (!osl_scop_integrity_check(list))
 511     OSL_warning("scop integrity check failed");
 512
 513   return list;
 514 }
 515
 516
 517 /**
 518  * osl_scop_read function:
 519  * this function is equivalent to osl_scop_pread() except that
 520  * (1) the precision corresponds to the precision environment variable or
 521  *     to the highest available precision if it is not defined, and
 522  * (2) the list of known interface is set to the default one.
 523  * \see{osl_scop_pread}
 524  */
 525 osl_scop_p osl_scop_read(FILE * foo) {
 526   int precision = osl_util_get_precision();
 527   osl_interface_p registry = osl_interface_get_default_registry();
 528   osl_scop_p scop = osl_scop_pread(foo, registry, precision);
 529
 530   osl_interface_free(registry);
 531   return scop;
 532 }
 533
 534
 535 /*+***************************************************************************
 536  *                   Memory allocation/deallocation functions                *
 537  *****************************************************************************/
 538
 539
 540 /**
 541  * osl_scop_malloc function:
 542  * this function allocates the memory space for a osl_scop_t structure and
 543  * sets its fields with default values. Then it returns a pointer to the
 544  * allocated space.
 545  * \return A pointer to an empty scop with fields set to default values.
 546  */
 547 osl_scop_p osl_scop_malloc() {
 548   osl_scop_p scop;
 549
 550   OSL_malloc(scop, osl_scop_p, sizeof(osl_scop_t));
 551   scop->version        = 1;
 552   scop->language       = NULL;
 553   scop->context        = NULL;
 554   scop->parameters     = NULL;
 555   scop->statement      = NULL;
 556   scop->registry       = NULL;
 557   scop->extension      = NULL;
 558   scop->usr            = NULL;
 559   scop->next           = NULL;
 560
 561   return scop;
 562 }
 563
 564
 565 /**
 566  * osl_scop_free function:
 567  * This function frees the allocated memory for a osl_scop_t structure.
 568  * \param scop The pointer to the scop we want to free.
 569  */
 570 void osl_scop_free(osl_scop_p scop) {
 571   osl_scop_p tmp;
 572
 573   while (scop != NULL) {
 574     if (scop->language != NULL)
 575       free(scop->language);
 576     osl_generic_free(scop->parameters);
 577     osl_relation_free(scop->context);
 578     osl_statement_free(scop->statement);
 579     osl_interface_free(scop->registry);
 580     osl_generic_free(scop->extension);
 581
 582     tmp = scop->next;
 583     free(scop);
 584     scop = tmp;
 585   }
 586 }
 587
 588
 589 /*+***************************************************************************
 590  *                            Processing functions                           *
 591  *****************************************************************************/
 592
 593
 594 /**
 595  * osl_scop_add function:
 596  * this function adds a scop "scop" at the end of the scop list pointed
 597  * by "location".
 598  * \param[in,out] location  Address of the first element of the scop list.
 599  * \param[in]     scop      The scop to add to the list.
 600  */
 601 void osl_scop_add(osl_scop_p * location, osl_scop_p scop) {
 602   while (*location != NULL)
 603     location = &((*location)->next);
 604
 605   *location = scop;
 606 }
 607
 608
 609 /**
 610  * osl_scop_number function:
 611  * this function returns the number of scops in the scop list
 612  * provided as parameter.
 613  * \param[in] scop The first element of the scop list.
 614  * \return The number of scops in the scop list.
 615  */
 616 size_t osl_scop_number(osl_scop_p scop) {
 617   size_t number = 0;
 618
 619   while (scop != NULL) {
 620     number++;
 621     scop = scop->next;
 622   }
 623   return number;
 624 }
 625
 626
 627 /**
 628  * osl_scop_clone function:
 629  * This functions builds and returns a "hard copy" (not a pointer copy)
 630  * of a osl_statement_t data structure provided as parameter.
 631  * Note that the usr field is not touched by this function.
 632  * \param scop The pointer to the scop we want to clone.
 633  * \return A pointer to the full clone of the scop provided as parameter.
 634  */
 635 osl_scop_p osl_scop_clone(osl_scop_p scop) {
 636   osl_scop_p clone = NULL, node, previous = NULL;
 637   int first = 1;
 638
 639   while (scop != NULL) {
 640     node                 = osl_scop_malloc();
 641     node->version        = scop->version;
 642     if (scop->language != NULL)
 643       OSL_strdup(node->language, scop->language);
 644     node->context        = osl_relation_clone(scop->context);
 645     node->parameters     = osl_generic_clone(scop->parameters);
 646     node->statement      = osl_statement_clone(scop->statement);
 647     node->registry       = osl_interface_clone(scop->registry);
 648     node->extension      = osl_generic_clone(scop->extension);
 649
 650     if (first) {
 651       first = 0;
 652       clone = node;
 653       previous = node;
 654     }
 655     else {
 656       previous->next = node;
 657       previous = previous->next;
 658     }
 659
 660     scop = scop->next;
 661   }
 662
 663   return clone;
 664 }
 665
 666 /**
 667  * osl_scop_remove_unions function:
 668  * Replace each statement having unions of relations by a list of statements,
 669  * each of which has exactly one domain relation and one scattering relation.
 670  * \param[in] scop A SCoP with statements featuring unions of relations.
 671  * \returns  An identical SCoP without unions of relations.
 672  */
 673 osl_scop_p osl_scop_remove_unions(osl_scop_p scop) {
 674   osl_statement_p statement, new_statement, scop_statement_ptr;
 675   osl_scop_p new_scop, scop_ptr, result = NULL;
 676
 677   for ( ; scop != NULL; scop = scop->next) {
 678     statement = scop->statement;
 679     scop_statement_ptr = NULL;
 680     new_scop = osl_scop_malloc();
 681
 682     for ( ; statement != NULL; statement = statement->next) {
 683       new_statement = osl_statement_remove_unions(statement);
 684       if (!scop_statement_ptr) {
 685         scop_statement_ptr = new_statement;
 686         new_scop->statement = scop_statement_ptr;
 687       } else {
 688         scop_statement_ptr->next = new_statement;
 689         scop_statement_ptr = scop_statement_ptr->next;
 690       }
 691     }
 692
 693     new_scop->context = osl_relation_clone(scop->context);
 694     new_scop->extension = osl_generic_clone(scop->extension);
 695     if (scop->language != NULL) {
 696       new_scop->language = (char *) malloc(strlen(scop->language) + 1);
 697       new_scop->language = strcpy(new_scop->language, scop->language);
 698     }
 699     new_scop->parameters = osl_generic_clone(scop->parameters);
 700     new_scop->registry = osl_interface_clone(scop->registry);
 701     new_scop->version = scop->version;
 702     if (!result) {
 703       result = new_scop;
 704       scop_ptr = new_scop;
 705     } else {
 706       scop_ptr->next = new_scop;
 707       scop_ptr = scop_ptr->next;
 708     }
 709   }
 710
 711   return result;
 712 }
 713
 714 /**
 715  * osl_scop_equal function:
 716  * this function returns true if the two scops are the same, false
 717  * otherwise (the usr field is not tested).
 718  * \param s1 The first scop.
 719  * \param s2 The second scop.
 720  * \return 1 if s1 and s2 are the same (content-wise), 0 otherwise.
 721  */
 722 int osl_scop_equal(osl_scop_p s1, osl_scop_p s2) {
 723
 724   while ((s1 != NULL) && (s2 != NULL)) {
 725     if (s1 == s2)
 726       return 1;
 727
 728     if (s1->version != s2->version) {
 729       OSL_info("versions are not the same");
 730       return 0;
 731     }
 732
 733     if (strcmp(s1->language, s2->language) != 0) {
 734       OSL_info("languages are not the same");
 735       return 0;
 736     }
 737
 738     if (!osl_relation_equal(s1->context, s2->context)) {
 739       OSL_info("contexts are not the same");
 740       return 0;
 741     }
 742
 743     if (!osl_generic_equal(s1->parameters, s2->parameters)) {
 744       OSL_info("parameters are not the same");
 745       return 0;
 746     }
 747
 748     if (!osl_statement_equal(s1->statement, s2->statement)) {
 749       OSL_info("statements are not the same");
 750       return 0;
 751     }
 752
 753     if (!osl_interface_equal(s1->registry, s2->registry)) {
 754       OSL_info("registries are not the same");
 755       return 0;
 756     }
 757
 758     if (!osl_generic_equal(s1->extension, s2->extension)) {
 759       OSL_info("extensions are not the same");
 760       return 0;
 761     }
 762
 763     s1 = s1->next;
 764     s2 = s2->next;
 765   }
 766
 767   if (((s1 == NULL) && (s2 != NULL)) || ((s1 != NULL) && (s2 == NULL)))
 768     return 0;
 769
 770   return 1;
 771 }
 772
 773
 774 /**
 775  * osl_scop_integrity_check function:
 776  * This function checks that a scop is "well formed". It returns 0 if the
 777  * check failed or 1 if no problem has been detected.
 778  * \param scop  The scop we want to check.
 779  * \return 0 if the integrity check fails, 1 otherwise.
 780  */
 781 int osl_scop_integrity_check(osl_scop_p scop) {
 782   int expected_nb_parameters;
 783
 784
 785   while (scop != NULL) {
 786     // Check the language.
 787     if ((scop->language != NULL) &&
 788         (!strcmp(scop->language, "caml")  || !strcmp(scop->language, "Caml") ||
 789          !strcmp(scop->language, "ocaml") || !strcmp(scop->language, "OCaml")))
 790       fprintf(stderr, "[OpenScop] Alert: What ?! Caml ?! Are you sure ?!?!\n");
 791
 792     // Check the context.
 793     if (!osl_relation_integrity_check(scop->context,
 794                                       OSL_TYPE_CONTEXT,
 795                                       OSL_UNDEFINED,
 796                                       OSL_UNDEFINED,
 797                                       OSL_UNDEFINED))
 798       return 0;
 799
 800     // Get the number of parameters.
 801     if (scop->context != NULL)
 802       expected_nb_parameters = scop->context->nb_parameters;
 803     else
 804       expected_nb_parameters = OSL_UNDEFINED;
 805
 806     // TODO : check the number of parameter strings.
 807
 808     if (!osl_statement_integrity_check(scop->statement,
 809                                        expected_nb_parameters))
 810       return 0;
 811
 812     scop = scop->next;
 813   }
 814
 815   return 1;
 816 }
 817
 818
 819 /**
 820  * osl_scop_check_compatible_scoplib function:
 821  * This function checks that a scop is "well formed". It returns 0 if the
 822  * check failed or 1 if no problem has been detected.
 823  * \param scop  The scop we want to check.
 824  * \return 0 if the integrity check fails, 1 otherwise.
 825  */
 826 int osl_scop_check_compatible_scoplib(osl_scop_p scop) {
 827
 828   if (!osl_scop_integrity_check(scop))
 829     return 0;
 830   if (scop->next != NULL)
 831     return 0;
 832   if (scop == NULL || scop->statement == NULL)
 833     return 1;
 834
 835   osl_relation_p domain;
 836   osl_statement_p statement;
 837   osl_relation_p scattering;
 838   int precision = scop->statement->scattering->precision;
 839   int i, j;
 840
 841   statement = scop->statement;
 842   while (statement != NULL) {
 843     scattering = statement->scattering;
 844
 845     if (scattering->nb_local_dims != 0) {
 846       OSL_error("Local dims in scattering matrix");
 847       return 0;
 848     }
 849
 850     domain = statement->domain;
 851     while (domain != NULL) {
 852       if (domain->nb_local_dims != 0) {
 853         OSL_error("Local dims in domain matrix");
 854         return 0;
 855       }
 856       domain = domain->next;
 857     }
 858
 859     // Check if there is only the -Identity in the output_dims
 860     // and the lines MUST be in the right order
 861     for (i = 0 ; i < scattering->nb_rows ; i++) {
 862       for (j = 0 ; j < scattering->nb_output_dims ; j++) {
 863         if (i == j) { // -1
 864           if (!osl_int_mone(precision, scattering->m[i][j+1])) {
 865             OSL_error("Wrong -Identity");
 866             return 0;
 867           }
 868         } else { // 0
 869           if (!osl_int_zero(precision, scattering->m[i][j+1])) {
 870             OSL_error("Wrong -Identity");
 871             return 0;
 872           }
 873         }
 874       }
 875     }
 876
 877     statement = statement->next;
 878   }
 879
 880   return 1;
 881 }
 882
 883
 884 /**
 885  * osl_scop_get_nb_parameters function:
 886  * this function returns the number of global parameters of a given SCoP.
 887  * \param scop The scop we want to know the number of global parameters.
 888  * \return The number of global parameters in the scop.
 889  */
 890 int osl_scop_get_nb_parameters(osl_scop_p scop) {
 891
 892   if (scop->context == NULL) {
 893     OSL_debug("no context domain, assuming 0 parameters");
 894     return 0;
 895   }
 896   else {
 897     return scop->context->nb_parameters;
 898   }
 899 }
 900
 901
 902 /**
 903  * osl_scop_register_extension function:
 904  * this function registers a list of extension interfaces to a scop, i.e., it
 905  * adds them to the scop registry. In addition, it will extract extensions
 906  * corresponding to those interfaces from the textual form of the extensions
 907  * (if any) and add them to the scop extension list.
 908  * \param scop      The scop for which an extension has to be registered.
 909  * \param interface The extension interface to register within the scop.
 910  */
 911 void osl_scop_register_extension(osl_scop_p scop, osl_interface_p interface) {
 912   osl_generic_p textual, new;
 913   char * extension_string;
 914
 915   if ((interface != NULL) && (scop != NULL)) {
 916     osl_interface_add(&scop->registry, interface);
 917
 918     textual = osl_generic_lookup(scop->extension, interface->URI);
 919     if (textual != NULL) {
 920       extension_string = ((osl_textual_p)textual->data)->textual;
 921       new = osl_generic_sread(&extension_string, interface);
 922       osl_generic_add(&scop->extension, new);
 923     }
 924   }
 925 }
 926
 927
 928 /**
 929  * osl_scop_get_attributes function:
 930  * this function returns, through its parameters, the maximum values of the
 931  * relation attributes (nb_iterators, nb_parameters etc) in the scop.
 932  * HOWEVER, it updates the parameter value iff the attribute is greater than
 933  * the input parameter value. Hence it may be used to get the attributes as
 934  * well as to find the maximum attributes for several scop lists. The array
 935  * identifier 0 is used when there is no array identifier (AND this is OK),
 936  * OSL_UNDEFINED is used to report it is impossible to provide the property
 937  * while it should. This function is not intended for checking, the input
 938  * scop should be correct.
 939  * \param[in]     scop          The scop to extract attributes values.
 940  * \param[in,out] nb_parameters Number of parameter attribute.
 941  * \param[in,out] nb_iterators  Number of iterators attribute.
 942  * \param[in,out] nb_scattdims  Number of scattering dimensions attribute.
 943  * \param[in,out] nb_localdims  Number of local dimensions attribute.
 944  * \param[in,out] array_id      Maximum array identifier attribute.
 945  */
 946 void osl_scop_get_attributes(osl_scop_p scop,
 947                              int * nb_parameters,
 948                              int * nb_iterators,
 949                              int * nb_scattdims,
 950                              int * nb_localdims,
 951                              int * array_id) {
 952   int local_nb_parameters = OSL_UNDEFINED;
 953   int local_nb_iterators  = OSL_UNDEFINED;
 954   int local_nb_scattdims  = OSL_UNDEFINED;
 955   int local_nb_localdims  = OSL_UNDEFINED;
 956   int local_array_id      = OSL_UNDEFINED;
 957
 958   while (scop != NULL) {
 959     osl_relation_get_attributes(scop->context,
 960                                 &local_nb_parameters,
 961                                 &local_nb_iterators,
 962                                 &local_nb_scattdims,
 963                                 &local_nb_localdims,
 964                                 &local_array_id);
 965
 966     osl_statement_get_attributes(scop->statement,
 967                                 &local_nb_parameters,
 968                                 &local_nb_iterators,
 969                                 &local_nb_scattdims,
 970                                 &local_nb_localdims,
 971                                 &local_array_id);
 972     // Update.
 973     *nb_parameters = OSL_max(*nb_parameters, local_nb_parameters);
 974     *nb_iterators  = OSL_max(*nb_iterators,  local_nb_iterators);
 975     *nb_scattdims  = OSL_max(*nb_scattdims,  local_nb_scattdims);
 976     *nb_localdims  = OSL_max(*nb_localdims,  local_nb_localdims);
 977     *array_id      = OSL_max(*array_id,      local_array_id);
 978     scop = scop->next;
 979   }
 980 }
 981
 982
 983 /**
 984  * osl_scop_normalize_scattering function:
 985  * this function modifies a scop such that all scattering relation have
 986  * the same number of output dimensions (additional output dimensions are
 987  * set as being equal to zero).
 988  * \param[in,out] scop The scop to nomalize the scattering functions.
 989  */
 990 void osl_scop_normalize_scattering(osl_scop_p scop) {
 991   int max_scattering_dims = 0;
 992   osl_statement_p statement;
 993   osl_relation_p extended;
 994
 995   if ((scop != NULL) && (scop->statement != NULL)) {
 996     // Get the max number of scattering dimensions.
 997     statement = scop->statement;
 998     while (statement != NULL) {
 999       if (statement->scattering != NULL) {
1000         max_scattering_dims = OSL_max(max_scattering_dims,
1001                                       statement->scattering->nb_output_dims);
1002       }
1003       statement = statement->next;
1004     }
1005
1006     // Normalize.
1007     statement = scop->statement;
1008     while (statement != NULL) {
1009       if (statement->scattering != NULL) {
1010         extended = osl_relation_extend_output(statement->scattering,
1011                                               max_scattering_dims);
1012         osl_relation_free(statement->scattering);
1013         statement->scattering = extended;
1014       }
1015       statement = statement->next;
1016     }
1017   }
1018 }
1019