source/statement.c

   1
   2     /*+-----------------------------------------------------------------**
   3      **                       OpenScop Library                          **
   4      **-----------------------------------------------------------------**
   5      **                          statement.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
  64 # include <stdlib.h>
  65 # include <stdio.h>
  66 # include <string.h>
  67 # include <ctype.h>
  68 # include <openscop/statement.h>
  69
  70
  71 /*+***************************************************************************
  72  *                         Structure display functions                       *
  73  *****************************************************************************/
  74
  75
  76 /**
  77  * openscop_statement_print_structure function:
  78  * Displays a openscop_statement_t structure (*statement) into a file (file,
  79  * possibly stdout) in a way that trends to be understandable without falling
  80  * in a deep depression or, for the lucky ones, getting a headache... It
  81  * includes an indentation level (level) in order to work with others
  82  * print_structure functions.
  83  * \param file      File where informations are printed.
  84  * \param statement The statement whose information have to be printed.
  85  * \param level     Number of spaces before printing, for each line.
  86  */
  87 void
  88 openscop_statement_print_structure(FILE * file, openscop_statement_p statement,
  89                                    int level)
  90 {
  91   int i, j, first = 1, number = 1;
  92
  93   // Go to the right level.
  94   for (j = 0; j < level; j++)
  95     fprintf(file, "|\t");
  96
  97   if (statement != NULL)
  98     fprintf(file, "+-- openscop_statement_t (S%d)\n", number);
  99   else
 100     fprintf(file, "+-- NULL statement\n");
 101
 102   while (statement != NULL)
 103   { if (!first)
 104     {
 105       // Go to the right level.
 106       for (j = 0; j < level; j++)
 107         fprintf(file, "|\t");
 108       fprintf(file, "|   openscop_statement_t (S%d)\n", number);
 109     }
 110     else
 111       first = 0;
 112
 113     // A blank line.
 114     for (j = 0; j <= level+1; j++)
 115       fprintf(file, "|\t");
 116     fprintf(file, "\n");
 117
 118     // Print the domain of the statement.
 119     openscop_relation_print_structure(file, statement->domain, level+1);
 120
 121     // Print the scattering of the statement.
 122     openscop_relation_print_structure(file, statement->scattering, level+1);
 123
 124     // Print the array read access informations of the statement.
 125     openscop_relation_list_print_structure(file, statement->read, level+1);
 126
 127     // Print the array write access informations of the statement.
 128     openscop_relation_list_print_structure(file, statement->write, level+1);
 129
 130     // Print the original iterator names.
 131     for (i = 0; i <= level; i++)
 132       fprintf(file, "|\t");
 133     if (statement->nb_iterators > 0)
 134     {
 135       fprintf(file, "+-- Original iterator strings:");
 136       for (i = 0; i < statement->nb_iterators; i++)
 137         fprintf(file, " %s", statement->iterators[i]);
 138       fprintf(file, "\n");
 139     }
 140     else
 141       fprintf(file, "+-- No original iterator string\n");
 142
 143     // A blank line.
 144     for (i = 0; i <= level+1; i++)
 145       fprintf(file, "|\t");
 146     fprintf(file, "\n");
 147
 148     // Print the original statement body.
 149     for (i = 0; i <= level; i++)
 150       fprintf(file, "|\t");
 151     if (statement->body != NULL)
 152       fprintf(file, "+-- Original body: %s\n", statement->body);
 153     else
 154       fprintf(file, "+-- No original body\n");
 155
 156     // A blank line.
 157     for (i = 0; i <= level+1; i++)
 158       fprintf(file, "|\t");
 159     fprintf(file, "\n");
 160
 161     statement = statement->next;
 162     number++;
 163
 164     // Next line.
 165     if (statement != NULL)
 166     {
 167       for (j = 0; j <= level; j++)
 168         fprintf(file, "|\t");
 169       fprintf(file, "V\n");
 170     }
 171   }
 172
 173   // The last line.
 174   for (j = 0; j <= level; j++)
 175     fprintf(file, "|\t");
 176   fprintf(file, "\n");
 177 }
 178
 179
 180 /**
 181  * openscop_statement_print function:
 182  * This function prints the content of a openscop_statement_t structure
 183  * (*statement) into  a file (file, possibly stdout).
 184  * \param file      File where informations are printed.
 185  * \param statement The statement whose information have to be printed.
 186  */
 187 void
 188 openscop_statement_print(FILE * file, openscop_statement_p statement)
 189 {
 190   openscop_statement_print_structure(file, statement, 0);
 191 }
 192
 193
 194 /**
 195  * openscop_statement_print_openscop function:
 196  * This function prints the content of a openscop_statement_t structure
 197  * (*statement) into a file (file, possibly stdout) in the OpenScop format.
 198  * \param file          File where informations are printed.
 199  * \param statement     The statement whose information have to be printed.
 200  * \param nb_parameters The number of parameters in the SCoP.
 201  * \param parameters    An array containing all parameters names.
 202  * \param nb_arrays     The number of arrays accessed in the SCoP.
 203  * \param arrays        An array containing all accessed array names.
 204  */
 205 void
 206 openscop_statement_print_openscop(FILE * file, openscop_statement_p statement,
 207                                   int nb_parameters, char ** parameters,
 208                                   int nb_arrays, char ** arrays)
 209 {
 210   int i, number = 1;
 211
 212   while (statement != NULL)
 213   {
 214     fprintf(file, "# =============================================== ");
 215     fprintf(file, "Statement %d\n", number);
 216
 217     fprintf(file, "# ---------------------------------------------- ");
 218     fprintf(file, "%2d.1 Domain\n", number);
 219     fprintf(file, "# Iteration domain\n");
 220     openscop_relation_print_openscop(file, statement->domain,
 221                                      OPENSCOP_TYPE_DOMAIN,
 222                                      statement->nb_iterators,
 223                                      statement->iterators,
 224                                      nb_parameters, parameters,
 225                                      nb_arrays, arrays);
 226     fprintf(file, "\n");
 227
 228     fprintf(file, "# ---------------------------------------------- ");
 229     fprintf(file, "%2d.2 Scattering\n", number);
 230     fprintf(file, "# Scattering function is provided\n");
 231     fprintf(file, "1\n");
 232     fprintf(file, "# Scattering function\n");
 233     openscop_relation_print_openscop(file, statement->scattering,
 234                                  OPENSCOP_TYPE_SCATTERING,
 235                                  statement->nb_iterators, statement->iterators,
 236                                  nb_parameters, parameters,
 237                                  nb_arrays, arrays);
 238     fprintf(file, "\n");
 239
 240     fprintf(file, "# ---------------------------------------------- ");
 241     fprintf(file, "%2d.3 Access\n", number);
 242     fprintf(file, "# Access informations are provided\n");
 243     fprintf(file, "1\n");
 244     fprintf(file, "\n# Read access information\n");
 245     openscop_relation_list_print_openscop(file, statement->read,
 246                                  OPENSCOP_TYPE_ACCESS,
 247                                  statement->nb_iterators, statement->iterators,
 248                                  nb_parameters, parameters,
 249                                  nb_arrays, arrays);
 250     fprintf(file, "\n# Write access information\n");
 251     openscop_relation_list_print_openscop(file, statement->write,
 252                                  OPENSCOP_TYPE_ACCESS,
 253                                  statement->nb_iterators, statement->iterators,
 254                                  nb_parameters, parameters,
 255                                  nb_arrays, arrays);
 256     fprintf(file, "\n");
 257
 258     fprintf(file, "# ---------------------------------------------- ");
 259     fprintf(file, "%2d.4 Body\n", number);
 260     fprintf(file, "# Statement body is provided\n");
 261     fprintf(file, "1\n");
 262     if (statement->nb_iterators > 0)
 263     {
 264       fprintf(file, "# Original iterator names\n");
 265       for (i = 0; i < statement->nb_iterators; i++)
 266         fprintf(file, "%s ", statement->iterators[i]);
 267       fprintf(file, "\n");
 268     }
 269     else
 270       fprintf(file, "# No original iterator names\n");
 271     fprintf(file, "# Statement body\n");
 272     fprintf(file, "%s\n", statement->body);
 273     fprintf(file, "\n\n");
 274
 275     statement = statement->next;
 276     number++;
 277   }
 278 }
 279
 280
 281 /*****************************************************************************
 282  *                               Reading function                            *
 283  *****************************************************************************/
 284
 285
 286 /**
 287  * openscop_statement_read function:
 288  * This function reads a openscop_statement_t structure from an input stream
 289  * (possibly stdin).
 290  * \param file  The input stream.
 291  * \return A pointer to the statement structure that has been read.
 292  */
 293 openscop_statement_p
 294 openscop_statement_read(FILE * file)
 295 {
 296   openscop_statement_p stmt = openscop_statement_malloc();
 297   char buff[OPENSCOP_MAX_STRING], * start, * end;
 298   int nb_iterators;
 299
 300   if (file)
 301   {
 302     // Read the domain matrices.
 303     stmt->domain = openscop_relation_read(file);
 304
 305     // Read the scattering, if any.
 306     if (openscop_util_read_int(file, NULL) > 0)
 307       stmt->scattering = openscop_relation_read(file);
 308
 309     // Read the access functions, if any.
 310     if (openscop_util_read_int(file, NULL) > 0)
 311     {
 312       stmt->read = openscop_relation_list_read(file);
 313       stmt->write = openscop_relation_list_read(file);
 314     }
 315
 316     // Read the body information, if any.
 317     if (openscop_util_read_int(file, NULL) > 0)
 318     {
 319       // Read the original iterator names.
 320       stmt->iterators = openscop_util_read_strings(file, -1, &nb_iterators);
 321       stmt->nb_iterators = nb_iterators;
 322
 323       // Read the body:
 324       // - Skip blank/commented lines and spaces.
 325       start = openscop_util_skip_blank_and_comments(file, buff);
 326
 327       // - Remove the comments.
 328       end = start;
 329       while ((*end != '#') && (*end != '\n'))
 330         end++;
 331       *end = '\0';
 332
 333       // - Copy the body.
 334       stmt->body = strdup(start);
 335     }
 336     else
 337     {
 338       stmt->nb_iterators = OPENSCOP_UNDEFINED;
 339       stmt->iterators = NULL;
 340       stmt->body = strdup("[undefined]");
 341     }
 342   }
 343
 344   return stmt;
 345 }
 346
 347
 348 /*+***************************************************************************
 349  *                   Memory allocation/deallocation functions                *
 350  *****************************************************************************/
 351
 352
 353 /**
 354  * openscop_statement_malloc function:
 355  * This function allocates the memory space for a openscop_statement_t
 356  * structure and sets its fields with default values. Then it returns a pointer
 357  * to the allocated space.
 358  * \return A pointer to an empty statement with fields set to default values.
 359  */
 360 openscop_statement_p
 361 openscop_statement_malloc()
 362 {
 363   openscop_statement_p statement;
 364
 365   statement = (openscop_statement_p)malloc(sizeof(openscop_statement_t));
 366   if (statement == NULL)
 367   {
 368     fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 369     exit(1);
 370   }
 371
 372   statement->domain     = NULL;
 373   statement->scattering = NULL;
 374   statement->read       = NULL;
 375   statement->write      = NULL;
 376   statement->nb_iterators = 0;
 377   statement->iterators  = NULL;
 378   statement->body       = NULL;
 379   statement->next       = NULL;
 380
 381   return statement;
 382 }
 383
 384
 385 /**
 386  * openscop_statement_free function:
 387  * This function frees the allocated memory for a openscop_statement_t
 388  * structure.
 389  * \param statement The pointer to the statement we want to free.
 390  */
 391 void
 392 openscop_statement_free(openscop_statement_p statement)
 393 {
 394   int i;
 395   openscop_statement_p next;
 396
 397   while (statement != NULL)
 398   {
 399     next = statement->next;
 400     openscop_relation_free(statement->domain);
 401     openscop_relation_free(statement->scattering);
 402     openscop_relation_list_free(statement->read);
 403     openscop_relation_list_free(statement->write);
 404     if (statement->iterators != NULL)
 405     {
 406       for (i = 0; i < statement->nb_iterators; i++)
 407         free(statement->iterators[i]);
 408       free(statement->iterators);
 409     }
 410     if (statement->body != NULL)
 411       free(statement->body);
 412
 413     free(statement);
 414     statement = next;
 415   }
 416 }
 417
 418
 419 /*+***************************************************************************
 420  *                            Processing functions                           *
 421  *****************************************************************************/
 422
 423
 424 /**
 425  * openscop_statement_add function:
 426  * This function adds a statement "statement" at the end of the statement
 427  * list pointed by "location".
 428  * \param location  Address of the first element of the statement list.
 429  * \param statement The statement to add to the list.
 430  */
 431 void
 432 openscop_statement_add(openscop_statement_p * location,
 433                        openscop_statement_p   statement)
 434 {
 435   while (*location != NULL)
 436     location = &((*location)->next);
 437
 438   *location = statement;
 439 }
 440
 441
 442 /**
 443  * openscop_statement_number function:
 444  * This function returns the number of statements in the statement list
 445  * provided as parameter.
 446  * \param statement The first element of the statement list.
 447  * \return The number of statements in the statement list.
 448  */
 449 int
 450 openscop_statement_number(openscop_statement_p statement)
 451 {
 452   int number = 0;
 453
 454   while (statement != NULL)
 455   {
 456     number++;
 457     statement = statement->next;
 458   }
 459   return number;
 460 }
 461
 462
 463 /**
 464  * openscop_statement_copy function:
 465  * This functions builds and returns a "hard copy" (not a pointer copy) of a
 466  * openscop_statement_t data structure provided as parameter.
 467  * \param statement  The pointer to the statement we want to copy.
 468  * \return A pointer to the full copy of the statement provided as parameter.
 469  */
 470 openscop_statement_p
 471 openscop_statement_copy(openscop_statement_p statement)
 472 {
 473   int first = 1;
 474   openscop_statement_p copy = NULL, node, previous = NULL;
 475
 476   while (statement != NULL)
 477   {
 478     node               = openscop_statement_malloc();
 479     node->version      = statement->version;
 480     node->domain       = openscop_relation_copy(statement->domain);
 481     node->scattering   = openscop_relation_copy(statement->scattering);
 482     node->read         = openscop_relation_list_copy(statement->read);
 483     node->write        = openscop_relation_list_copy(statement->write);
 484     node->nb_iterators = statement->nb_iterators;
 485     node->iterators    = openscop_util_copy_strings(statement->iterators,
 486                                                     statement->nb_iterators);
 487     node->body         = strdup(statement->body);
 488     node->next         = NULL;
 489
 490     if (first)
 491     {
 492       first = 0;
 493       copy = node;
 494       previous = node;
 495     }
 496     else
 497     {
 498       previous->next = node;
 499       previous = previous->next;
 500     }
 501
 502     statement = statement->next;
 503   }
 504
 505   return copy;
 506 }
 507
 508
 509 /**
 510  * openscop_statement_equal function:
 511  * This function returns true if the two statements are the same, false
 512  * otherwise (the usr field is not tested).
 513  * \param s1 The first statement.
 514  * \param s2 The second statement.
 515  * \return 1 if s1 and s2 are the same (content-wise), 0 otherwise.
 516  */
 517 int
 518 openscop_statement_equal(openscop_statement_p s1, openscop_statement_p s2)
 519 {
 520   int i;
 521
 522   if (((s1->next != NULL) && (s2->next == NULL)) ||
 523       ((s1->next == NULL) && (s2->next != NULL)))
 524     return 0;
 525
 526   if ((s1->next != NULL) && (s2->next != NULL))
 527     if (!openscop_statement_equal(s1->next, s2->next))
 528       return 0;
 529
 530   if (//(s1->version != s2->version) ||
 531       (s1->nb_iterators != s2->nb_iterators) ||
 532       (!openscop_relation_equal(s1->domain,     s2->domain))     ||
 533       (!openscop_relation_equal(s1->scattering, s2->scattering)) ||
 534       (!openscop_relation_list_equal(s1->read,  s2->read))       ||
 535       (!openscop_relation_list_equal(s1->write, s2->write))      ||
 536       (strcmp(s1->body, s2->body) != 0))
 537     return 0;
 538
 539   for (i = 0; i < s1->nb_iterators; i++)
 540     if (strcmp(s1->iterators[i], s2->iterators[i]) != 0)
 541       return 0;
 542
 543   return 1;
 544 }
 545
 546
 547 /**
 548  * openscop_statement_integrity_check function:
 549  * This function checks that a statement is "well formed" according to some
 550  * expected properties (setting an expected value to OPENSCOP_UNDEFINED means
 551  * that we do not expect a specific value). It returns 0 if the check failed
 552  * or 1 if no problem has been detected.
 553  * \param statement               The statement we want to check.
 554  * \param expected_nb_parameters  Expected number of parameters.
 555  * \return 0 if the integrity check fails, 1 otherwise.
 556  */
 557 int
 558 openscop_statement_integrity_check(openscop_statement_p statement,
 559                                    int expected_nb_parameters)
 560 {
 561   int expected_nb_iterators = OPENSCOP_UNDEFINED;
 562
 563   while (statement != NULL)
 564   {
 565     if (!openscop_relation_integrity_check(statement->domain,
 566                                            OPENSCOP_TYPE_DOMAIN,
 567                                            OPENSCOP_UNDEFINED,
 568                                            0,
 569                                            expected_nb_parameters))
 570       return 0;
 571
 572     // Get the number of iterators.
 573     if (statement->domain != NULL)
 574     {
 575       if (openscop_relation_is_matrix(statement->domain))
 576       {
 577         if (expected_nb_parameters != OPENSCOP_UNDEFINED)
 578           expected_nb_iterators = statement->domain->nb_columns -
 579                                   expected_nb_parameters - 2;
 580         else
 581           expected_nb_iterators = OPENSCOP_UNDEFINED;
 582       }
 583       else
 584         expected_nb_iterators = statement->domain->nb_output_dims;
 585     }
 586
 587     if (!openscop_relation_integrity_check(statement->scattering,
 588                                            OPENSCOP_TYPE_SCATTERING,
 589                                            OPENSCOP_UNDEFINED,
 590                                            expected_nb_iterators,
 591                                            expected_nb_parameters) ||
 592         !openscop_relation_list_integrity_check(statement->read,
 593                                            OPENSCOP_TYPE_ACCESS,
 594                                            OPENSCOP_UNDEFINED,
 595                                            expected_nb_iterators,
 596                                            expected_nb_parameters) ||
 597         !openscop_relation_list_integrity_check(statement->write,
 598                                            OPENSCOP_TYPE_ACCESS,
 599                                            OPENSCOP_UNDEFINED,
 600                                            expected_nb_iterators,
 601                                            expected_nb_parameters))
 602       return 0;
 603
 604     if ((statement->nb_iterators > 0) &&
 605         (statement->nb_iterators < statement->domain->nb_output_dims))
 606     {
 607       fprintf(stderr, "[OpenScop] Warning: not enough original iterator "
 608                       "names.\n");
 609       return 0;
 610     }
 611
 612     statement = statement->next;
 613   }
 614
 615   return 1;
 616 }