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 names     The textual names of the various elements. Is is important
 201  *                  that names->nb_parameters is exact if the matrix
 202  *                  representation is used. Set to NULL if printing comments
 203  *                  is not needed.
 204  */
 205 void
 206 openscop_statement_print_openscop(FILE * file, openscop_statement_p statement,
 207                                   openscop_names_p names)
 208 {
 209   int i, switched, number = 1;
 210   int tmp_nb_iterators = 0;
 211   char ** tmp_iterators = NULL;
 212
 213   while (statement != NULL)
 214   {
 215     // Switch iterator names to the current statement names if possible.
 216     switched = 0;
 217     if (statement->nb_iterators > 0)
 218     {
 219       tmp_nb_iterators = names->nb_iterators;
 220       tmp_iterators = names->iterators;
 221       names->nb_iterators = statement->nb_iterators;
 222       names->iterators = statement->iterators;
 223       switched = 1;
 224     }
 225
 226     fprintf(file, "# =============================================== ");
 227     fprintf(file, "Statement %d\n", number);
 228
 229     fprintf(file, "# ---------------------------------------------- ");
 230     fprintf(file, "%2d.1 Domain\n", number);
 231     fprintf(file, "# Iteration domain\n");
 232     openscop_relation_print_openscop(file, statement->domain,
 233                                      OPENSCOP_TYPE_DOMAIN, names);
 234     fprintf(file, "\n");
 235
 236     fprintf(file, "# ---------------------------------------------- ");
 237     fprintf(file, "%2d.2 Scattering\n", number);
 238     fprintf(file, "# Scattering function is provided\n");
 239     fprintf(file, "1\n");
 240     fprintf(file, "# Scattering function\n");
 241     openscop_relation_print_openscop(file, statement->scattering,
 242                                      OPENSCOP_TYPE_SCATTERING, names);
 243     fprintf(file, "\n");
 244
 245     fprintf(file, "# ---------------------------------------------- ");
 246     fprintf(file, "%2d.3 Access\n", number);
 247     fprintf(file, "# Access informations are provided\n");
 248     fprintf(file, "1\n");
 249     fprintf(file, "\n# Read access information\n");
 250     openscop_relation_list_print_openscop(file, statement->read,
 251                                           OPENSCOP_TYPE_ACCESS, names);
 252     fprintf(file, "\n# Write access information\n");
 253     openscop_relation_list_print_openscop(file, statement->write,
 254                                           OPENSCOP_TYPE_ACCESS, names);
 255     fprintf(file, "\n");
 256
 257     fprintf(file, "# ---------------------------------------------- ");
 258     fprintf(file, "%2d.4 Body\n", number);
 259     fprintf(file, "# Statement body is provided\n");
 260     fprintf(file, "1\n");
 261     if (statement->nb_iterators > 0)
 262     {
 263       fprintf(file, "# Original iterator names\n");
 264       for (i = 0; i < statement->nb_iterators; i++)
 265         fprintf(file, "%s ", statement->iterators[i]);
 266       fprintf(file, "\n");
 267     }
 268     else
 269       fprintf(file, "# No original iterator names\n");
 270     fprintf(file, "# Statement body\n");
 271     fprintf(file, "%s\n", statement->body);
 272     fprintf(file, "\n\n");
 273
 274     if (switched == 1)
 275     {
 276       statement->nb_iterators = tmp_nb_iterators;
 277       statement->iterators = tmp_iterators;
 278     }
 279     statement = statement->next;
 280     number++;
 281   }
 282 }
 283
 284
 285 /*****************************************************************************
 286  *                               Reading function                            *
 287  *****************************************************************************/
 288
 289
 290 /**
 291  * openscop_statement_read function:
 292  * This function reads a openscop_statement_t structure from an input stream
 293  * (possibly stdin).
 294  * \param file  The input stream.
 295  * \return A pointer to the statement structure that has been read.
 296  */
 297 openscop_statement_p
 298 openscop_statement_read(FILE * file)
 299 {
 300   openscop_statement_p stmt = openscop_statement_malloc();
 301   char buff[OPENSCOP_MAX_STRING], * start, * end;
 302   int nb_iterators;
 303
 304   if (file)
 305   {
 306     // Read the domain matrices.
 307     stmt->domain = openscop_relation_read(file);
 308
 309     // Read the scattering, if any.
 310     if (openscop_util_read_int(file, NULL) > 0)
 311       stmt->scattering = openscop_relation_read(file);
 312
 313     // Read the access functions, if any.
 314     if (openscop_util_read_int(file, NULL) > 0)
 315     {
 316       stmt->read = openscop_relation_list_read(file);
 317       stmt->write = openscop_relation_list_read(file);
 318     }
 319
 320     // Read the body information, if any.
 321     if (openscop_util_read_int(file, NULL) > 0)
 322     {
 323       // Read the original iterator names.
 324       stmt->iterators = openscop_util_strings_read(file, &nb_iterators);
 325       stmt->nb_iterators = nb_iterators;
 326
 327       // Read the body:
 328       // - Skip blank/commented lines and spaces.
 329       start = openscop_util_skip_blank_and_comments(file, buff);
 330
 331       // - Remove the comments.
 332       end = start;
 333       while ((*end != '#') && (*end != '\n'))
 334         end++;
 335       *end = '\0';
 336
 337       // - Copy the body.
 338       stmt->body = strdup(start);
 339     }
 340     else
 341     {
 342       stmt->nb_iterators = OPENSCOP_UNDEFINED;
 343       stmt->iterators = NULL;
 344       stmt->body = strdup("[undefined]");
 345     }
 346   }
 347
 348   return stmt;
 349 }
 350
 351
 352 /*+***************************************************************************
 353  *                   Memory allocation/deallocation functions                *
 354  *****************************************************************************/
 355
 356
 357 /**
 358  * openscop_statement_malloc function:
 359  * This function allocates the memory space for a openscop_statement_t
 360  * structure and sets its fields with default values. Then it returns a pointer
 361  * to the allocated space.
 362  * \return A pointer to an empty statement with fields set to default values.
 363  */
 364 openscop_statement_p
 365 openscop_statement_malloc()
 366 {
 367   openscop_statement_p statement;
 368
 369   statement = (openscop_statement_p)malloc(sizeof(openscop_statement_t));
 370   if (statement == NULL)
 371   {
 372     fprintf(stderr, "[OpenScop] Error: memory overflow.\n");
 373     exit(1);
 374   }
 375
 376   statement->domain     = NULL;
 377   statement->scattering = NULL;
 378   statement->read       = NULL;
 379   statement->write      = NULL;
 380   statement->nb_iterators = 0;
 381   statement->iterators  = NULL;
 382   statement->nb_local_dims = 0;
 383   statement->local_dims = NULL;
 384   statement->body       = NULL;
 385   statement->next       = NULL;
 386
 387   return statement;
 388 }
 389
 390
 391 /**
 392  * openscop_statement_free function:
 393  * This function frees the allocated memory for a openscop_statement_t
 394  * structure.
 395  * \param statement The pointer to the statement we want to free.
 396  */
 397 void
 398 openscop_statement_free(openscop_statement_p statement)
 399 {
 400   int i;
 401   openscop_statement_p next;
 402
 403   while (statement != NULL)
 404   {
 405     next = statement->next;
 406     openscop_relation_free(statement->domain);
 407     openscop_relation_free(statement->scattering);
 408     openscop_relation_list_free(statement->read);
 409     openscop_relation_list_free(statement->write);
 410     if (statement->iterators != NULL)
 411     {
 412       for (i = 0; i < statement->nb_iterators; i++)
 413         free(statement->iterators[i]);
 414       free(statement->iterators);
 415     }
 416     if (statement->body != NULL)
 417       free(statement->body);
 418
 419     free(statement);
 420     statement = next;
 421   }
 422 }
 423
 424
 425 /*+***************************************************************************
 426  *                            Processing functions                           *
 427  *****************************************************************************/
 428
 429
 430 /**
 431  * openscop_statement_add function:
 432  * This function adds a statement "statement" at the end of the statement
 433  * list pointed by "location".
 434  * \param location  Address of the first element of the statement list.
 435  * \param statement The statement to add to the list.
 436  */
 437 void
 438 openscop_statement_add(openscop_statement_p * location,
 439                        openscop_statement_p   statement)
 440 {
 441   while (*location != NULL)
 442     location = &((*location)->next);
 443
 444   *location = statement;
 445 }
 446
 447
 448 /**
 449  * openscop_statement_number function:
 450  * This function returns the number of statements in the statement list
 451  * provided as parameter.
 452  * \param statement The first element of the statement list.
 453  * \return The number of statements in the statement list.
 454  */
 455 int
 456 openscop_statement_number(openscop_statement_p statement)
 457 {
 458   int number = 0;
 459
 460   while (statement != NULL)
 461   {
 462     number++;
 463     statement = statement->next;
 464   }
 465   return number;
 466 }
 467
 468
 469 /**
 470  * openscop_statement_copy function:
 471  * This functions builds and returns a "hard copy" (not a pointer copy) of a
 472  * openscop_statement_t data structure provided as parameter.
 473  * \param statement  The pointer to the statement we want to copy.
 474  * \return A pointer to the full copy of the statement provided as parameter.
 475  */
 476 openscop_statement_p
 477 openscop_statement_copy(openscop_statement_p statement)
 478 {
 479   int first = 1;
 480   openscop_statement_p copy = NULL, node, previous = NULL;
 481
 482   while (statement != NULL)
 483   {
 484     node               = openscop_statement_malloc();
 485     node->version      = statement->version;
 486     node->domain       = openscop_relation_copy(statement->domain);
 487     node->scattering   = openscop_relation_copy(statement->scattering);
 488     node->read         = openscop_relation_list_copy(statement->read);
 489     node->write        = openscop_relation_list_copy(statement->write);
 490     node->nb_iterators = statement->nb_iterators;
 491     node->iterators    = openscop_util_strings_copy(statement->iterators,
 492                                                     statement->nb_iterators);
 493     node->body         = strdup(statement->body);
 494     node->next         = NULL;
 495
 496     if (first)
 497     {
 498       first = 0;
 499       copy = node;
 500       previous = node;
 501     }
 502     else
 503     {
 504       previous->next = node;
 505       previous = previous->next;
 506     }
 507
 508     statement = statement->next;
 509   }
 510
 511   return copy;
 512 }
 513
 514
 515 /**
 516  * openscop_statement_equal function:
 517  * This function returns true if the two statements are the same, false
 518  * otherwise (the usr field is not tested).
 519  * \param s1 The first statement.
 520  * \param s2 The second statement.
 521  * \return 1 if s1 and s2 are the same (content-wise), 0 otherwise.
 522  */
 523 int
 524 openscop_statement_equal(openscop_statement_p s1, openscop_statement_p s2)
 525 {
 526   int i;
 527
 528   if (((s1->next != NULL) && (s2->next == NULL)) ||
 529       ((s1->next == NULL) && (s2->next != NULL)))
 530     return 0;
 531
 532   if ((s1->next != NULL) && (s2->next != NULL))
 533     if (!openscop_statement_equal(s1->next, s2->next))
 534       return 0;
 535
 536   if (//(s1->version != s2->version) ||
 537       (s1->nb_iterators != s2->nb_iterators) ||
 538       (!openscop_relation_equal(s1->domain,     s2->domain))     ||
 539       (!openscop_relation_equal(s1->scattering, s2->scattering)) ||
 540       (!openscop_relation_list_equal(s1->read,  s2->read))       ||
 541       (!openscop_relation_list_equal(s1->write, s2->write))      ||
 542       (strcmp(s1->body, s2->body) != 0))
 543     return 0;
 544
 545   for (i = 0; i < s1->nb_iterators; i++)
 546     if (strcmp(s1->iterators[i], s2->iterators[i]) != 0)
 547       return 0;
 548
 549   return 1;
 550 }
 551
 552
 553 /**
 554  * openscop_statement_integrity_check function:
 555  * This function checks that a statement is "well formed" according to some
 556  * expected properties (setting an expected value to OPENSCOP_UNDEFINED means
 557  * that we do not expect a specific value). It returns 0 if the check failed
 558  * or 1 if no problem has been detected.
 559  * \param statement               The statement we want to check.
 560  * \param expected_nb_parameters  Expected number of parameters.
 561  * \return 0 if the integrity check fails, 1 otherwise.
 562  */
 563 int
 564 openscop_statement_integrity_check(openscop_statement_p statement,
 565                                    int expected_nb_parameters)
 566 {
 567   int expected_nb_iterators = OPENSCOP_UNDEFINED;
 568
 569   while (statement != NULL)
 570   {
 571     if (!openscop_relation_integrity_check(statement->domain,
 572                                            OPENSCOP_TYPE_DOMAIN,
 573                                            OPENSCOP_UNDEFINED,
 574                                            OPENSCOP_UNDEFINED,
 575                                            expected_nb_parameters))
 576       return 0;
 577
 578     // Get the number of iterators.
 579     if (statement->domain != NULL)
 580     {
 581       if (openscop_relation_is_matrix(statement->domain))
 582       {
 583         if (expected_nb_parameters != OPENSCOP_UNDEFINED)
 584           expected_nb_iterators = statement->domain->nb_columns -
 585                                   expected_nb_parameters - 2;
 586         else
 587           expected_nb_iterators = OPENSCOP_UNDEFINED;
 588       }
 589       else
 590         expected_nb_iterators = statement->domain->nb_output_dims;
 591     }
 592
 593     if (!openscop_relation_integrity_check(statement->scattering,
 594                                            OPENSCOP_TYPE_SCATTERING,
 595                                            OPENSCOP_UNDEFINED,
 596                                            expected_nb_iterators,
 597                                            expected_nb_parameters) ||
 598         !openscop_relation_list_integrity_check(statement->read,
 599                                            OPENSCOP_TYPE_ACCESS,
 600                                            OPENSCOP_UNDEFINED,
 601                                            expected_nb_iterators,
 602                                            expected_nb_parameters) ||
 603         !openscop_relation_list_integrity_check(statement->write,
 604                                            OPENSCOP_TYPE_ACCESS,
 605                                            OPENSCOP_UNDEFINED,
 606                                            expected_nb_iterators,
 607                                            expected_nb_parameters))
 608       return 0;
 609
 610     if ((statement->nb_iterators > 0) &&
 611         (statement->nb_iterators < statement->domain->nb_output_dims))
 612     {
 613       fprintf(stderr, "[OpenScop] Warning: not enough original iterator "
 614                       "names.\n");
 615       return 0;
 616     }
 617
 618     statement = statement->next;
 619   }
 620
 621   return 1;
 622 }