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