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 <osl/statement.h>
  69
  70
  71 /*+***************************************************************************
  72  *                         Structure display functions                       *
  73  *****************************************************************************/
  74
  75
  76 /**
  77  * osl_statement_idump function:
  78  * this function displays an osl_statement_t structure (*statement) into
  79  * a file (file, possibly stdout) in a way that trends to be understandable.
  80  * It includes an indentation level (level) in order to work with others
  81  * dumping functions.
  82  * \param[in] file      File where the information has to be printed.
  83  * \param[in] statement The statement whose information has to be printed.
  84  * \param[in] level     Number of spaces before printing, for each line.
  85  */
  86 void osl_statement_idump(FILE * file, osl_statement_p statement, int level) {
  87   int j, first = 1, number = 1;
  88
  89   // Go to the right level.
  90   for (j = 0; j < level; j++)
  91     fprintf(file, "|\t");
  92
  93   if (statement != NULL)
  94     fprintf(file, "+-- osl_statement_t (S%d)\n", number);
  95   else
  96     fprintf(file, "+-- NULL statement\n");
  97
  98   while (statement != NULL) {
  99     if (!first) {
 100       // Go to the right level.
 101       for (j = 0; j < level; j++)
 102         fprintf(file, "|\t");
 103       fprintf(file, "|   osl_statement_t (S%d)\n", number);
 104     }
 105     else
 106       first = 0;
 107
 108     // A blank line.
 109     for (j = 0; j <= level + 1; j++)
 110       fprintf(file, "|\t");
 111     fprintf(file, "\n");
 112
 113     // Print the domain of the statement.
 114     osl_relation_idump(file, statement->domain, level + 1);
 115
 116     // Print the scattering of the statement.
 117     osl_relation_idump(file, statement->scattering, level + 1);
 118
 119     // Print the array access information of the statement.
 120     osl_relation_list_idump(file, statement->access, level + 1);
 121
 122     // Print the original iterator names.
 123     osl_generic_idump(file, statement->iterators, level + 1);
 124
 125     // Print the original body expression.
 126     osl_generic_idump(file, statement->body, level + 1);
 127
 128     statement = statement->next;
 129     number++;
 130
 131     // Next line.
 132     if (statement != NULL) {
 133       for (j = 0; j <= level; j++)
 134         fprintf(file, "|\t");
 135       fprintf(file, "V\n");
 136     }
 137   }
 138
 139   // The last line.
 140   for (j = 0; j <= level; j++)
 141     fprintf(file, "|\t");
 142   fprintf(file, "\n");
 143 }
 144
 145
 146 /**
 147  * osl_statement_dump function:
 148  * this function prints the content of an osl_statement_t structure
 149  * (*statement) into  a file (file, possibly stdout).
 150  * \param[in] file      The file where the information has to be printed.
 151  * \param[in] statement The statement whose information has to be printed.
 152  */
 153 void osl_statement_dump(FILE * file, osl_statement_p statement) {
 154   osl_statement_idump(file, statement, 0);
 155 }
 156
 157
 158 /**
 159  * osl_statement_print function:
 160  * this function prints the content of an osl_statement_t structure
 161  * (*statement) into a file (file, possibly stdout) in the OpenScop format.
 162  * \param[in] file      The file where the information has to be printed.
 163  * \param[in] statement The statement whose information has to be printed.
 164  */
 165 void osl_statement_print(FILE * file, osl_statement_p statement) {
 166   int nb_relations, number = 1;
 167
 168   while (statement != NULL) {
 169     nb_relations = 0;
 170
 171     fprintf(file, "# =============================================== ");
 172     fprintf(file, "Statement %d\n", number);
 173
 174     fprintf(file, "# Number of relations describing the statement:\n");
 175
 176     if (statement->domain != NULL)
 177       nb_relations ++;
 178     if (statement->scattering != NULL)
 179       nb_relations ++;
 180     nb_relations += osl_relation_list_count(statement->access);
 181
 182     fprintf(file, "%d\n\n", nb_relations);
 183
 184     fprintf(file, "# ---------------------------------------------- ");
 185     fprintf(file, "%2d.1 Domain\n", number);
 186     osl_relation_print(file, statement->domain);
 187     fprintf(file, "\n");
 188
 189     fprintf(file, "# ---------------------------------------------- ");
 190     fprintf(file, "%2d.2 Scattering\n", number);
 191     osl_relation_print(file, statement->scattering);
 192     fprintf(file, "\n");
 193
 194     fprintf(file, "# ---------------------------------------------- ");
 195     fprintf(file, "%2d.3 Access\n", number);
 196     osl_relation_list_print_elts(file, statement->access);
 197     fprintf(file, "\n");
 198
 199     fprintf(file, "# ---------------------------------------------- ");
 200     fprintf(file, "%2d.4 Body\n", number);
 201     if (osl_generic_hasURI(statement->body, OSL_URI_STRINGS)) {
 202       fprintf(file, "# Statement body is provided\n");
 203       fprintf(file, "1\n");
 204       if (osl_generic_hasURI(statement->iterators,OSL_URI_STRINGS)) {
 205         fprintf(file, "# Original iterators\n");
 206         osl_generic_print(file, statement->iterators);
 207       }
 208       fprintf(file, "# Body expression\n");
 209       osl_generic_print(file, statement->body);
 210     }
 211     else {
 212       fprintf(file, "# Statement body is not provided\n");
 213       fprintf(file, "0\n");
 214     }
 215
 216     fprintf(file, "\n\n");
 217     statement = statement->next;
 218     number++;
 219   }
 220 }
 221
 222
 223 /*****************************************************************************
 224  *                               Reading function                            *
 225  *****************************************************************************/
 226
 227
 228 /**
 229  * osl_statement_dispatch function:
 230  * this function dispatches the relations from a relation list to the
 231  * convenient fields of a statement structure: it extracts the domain,
 232  * the scattering and the access list and store them accordingly in the
 233  * statement structure provided as a parameter.
 234  * \param[in,out] stmt The statement where to dispatch the relations.
 235  * \param[in,out] list The "brute" relation list to sort and dispatch (freed).
 236  */
 237 static
 238 void osl_statement_dispatch(osl_statement_p stmt, osl_relation_list_p list) {
 239   osl_relation_list_p domain_list;
 240   osl_relation_list_p scattering_list;
 241   int nb_domains, nb_scattering, nb_accesses;
 242
 243   // Domain.
 244   domain_list = osl_relation_list_filter(list, OSL_TYPE_DOMAIN);
 245   nb_domains = osl_relation_list_count(domain_list);
 246   if (nb_domains > 1)
 247     OSL_error("more than one domain for a statement");
 248
 249   if (domain_list != NULL) {
 250     stmt->domain = domain_list->elt;
 251     domain_list->elt = NULL;
 252     osl_relation_list_free(domain_list);
 253   }
 254   else {
 255     stmt->domain = NULL;
 256   }
 257
 258   // Scattering.
 259   scattering_list=osl_relation_list_filter(list,OSL_TYPE_SCATTERING);
 260   nb_scattering = osl_relation_list_count(scattering_list);
 261   if (nb_scattering > 1)
 262     OSL_error("more than one scattering relation for a statement");
 263
 264   if (scattering_list != NULL) {
 265     stmt->scattering = scattering_list->elt;
 266     scattering_list->elt = NULL;
 267     osl_relation_list_free(scattering_list);
 268   }
 269   else {
 270     stmt->scattering = NULL;
 271   }
 272
 273   // Access.
 274   stmt->access = osl_relation_list_filter(list, OSL_TYPE_ACCESS);
 275   nb_accesses = osl_relation_list_count(stmt->access);
 276
 277   if ((nb_domains + nb_scattering + nb_accesses) !=
 278       (osl_relation_list_count(list)))
 279     OSL_error("unexpected relation type to define a statement");
 280
 281   osl_relation_list_free(list);
 282 }
 283
 284
 285 /**
 286  * osl_statement_read function:
 287  * this function reads an osl_statement_t structure from an input stream
 288  * (possibly stdin).
 289  * \param[in] file The input stream.
 290  * \return A pointer to the statement structure that has been read.
 291  */
 292 osl_statement_p osl_statement_read(FILE * file) {
 293   int nb_iterators;
 294   char buffer[OSL_MAX_STRING], * start, * end;
 295   osl_statement_p stmt = osl_statement_malloc();
 296   osl_relation_list_p list;
 297   osl_interface_p interface;
 298
 299   if (file) {
 300     // Read all statement relations.
 301     list = osl_relation_list_read(file);
 302
 303     // Store relations at the right place according to their type.
 304     osl_statement_dispatch(stmt, list);
 305
 306     // Read the body information.
 307     if (stmt->domain != NULL) {
 308       nb_iterators = stmt->domain->nb_output_dims;
 309     }
 310     else {
 311       OSL_warning("no domain, assuming 0 original iterator");
 312       nb_iterators = 0;
 313     }
 314
 315     if (osl_util_read_int(file, NULL) > 0) {
 316       // Read the original iterator names.
 317       if (nb_iterators > 0) {
 318         interface = osl_strings_interface();
 319         start = osl_util_skip_blank_and_comments(file, buffer);
 320         stmt->iterators = osl_generic_sread(start, interface);
 321         osl_interface_free(interface);
 322       }
 323
 324       // Read the body:
 325       // - Skip blank/commented lines and spaces before the body.
 326       start = osl_util_skip_blank_and_comments(file, buffer);
 327
 328       // - Remove the comments after the body.
 329       end = start;
 330       while ((*end != '#') && (*end != '\n'))
 331         end++;
 332       *end = '\0';
 333
 334       // - Build the body.
 335       stmt->body = osl_generic_malloc();
 336       stmt->body->interface = osl_strings_interface();
 337       stmt->body->data = osl_strings_encapsulate(strdup(start));
 338     }
 339   }
 340
 341   return stmt;
 342 }
 343
 344
 345 /*+***************************************************************************
 346  *                   Memory allocation/deallocation functions                *
 347  *****************************************************************************/
 348
 349
 350 /**
 351  * osl_statement_malloc function:
 352  * this function allocates the memory space for an osl_statement_t
 353  * structure and sets its fields with default values. Then it returns a pointer
 354  * to the allocated space.
 355  * \return A pointer to an empty statement with fields set to default values.
 356  */
 357 osl_statement_p osl_statement_malloc() {
 358   osl_statement_p statement;
 359
 360   OSL_malloc(statement, osl_statement_p, sizeof(osl_statement_t));
 361   statement->domain     = NULL;
 362   statement->scattering = NULL;
 363   statement->access     = NULL;
 364   statement->iterators  = NULL;
 365   statement->body       = NULL;
 366   statement->next       = NULL;
 367
 368   return statement;
 369 }
 370
 371
 372 /**
 373  * osl_statement_free function:
 374  * this function frees the allocated memory for an osl_statement_t
 375  * structure.
 376  * \param[in,out] statement The pointer to the statement we want to free.
 377  */
 378 void osl_statement_free(osl_statement_p statement) {
 379   osl_statement_p next;
 380
 381   while (statement != NULL) {
 382     next = statement->next;
 383     osl_relation_free(statement->domain);
 384     osl_relation_free(statement->scattering);
 385     osl_relation_list_free(statement->access);
 386     osl_generic_free(statement->iterators);
 387     osl_generic_free(statement->body);
 388
 389     free(statement);
 390     statement = next;
 391   }
 392 }
 393
 394
 395 /*+***************************************************************************
 396  *                            Processing functions                           *
 397  *****************************************************************************/
 398
 399
 400 /**
 401  * osl_statement_add function:
 402  * this function adds a statement "statement" at the end of the statement
 403  * list pointed by "location".
 404  * \param[in,out] location  Address of the first element of the statement list.
 405  * \param[in]     statement The statement to add to the list.
 406  */
 407 void osl_statement_add(osl_statement_p * location,
 408                        osl_statement_p   statement) {
 409   while (*location != NULL)
 410     location = &((*location)->next);
 411
 412   *location = statement;
 413 }
 414
 415
 416 /**
 417  * osl_statement_number function:
 418  * this function returns the number of statements in the statement list
 419  * provided as parameter.
 420  * \param[in] statement The first element of the statement list.
 421  * \return The number of statements in the statement list.
 422  */
 423 int osl_statement_number(osl_statement_p statement) {
 424   int number = 0;
 425
 426   while (statement != NULL) {
 427     number++;
 428     statement = statement->next;
 429   }
 430   return number;
 431 }
 432
 433
 434 /**
 435  * osl_statement_clone function:
 436  * This functions builds and returns a "hard copy" (not a pointer copy) of an
 437  * osl_statement_t data structure provided as parameter.
 438  * \param[in] statement The pointer to the statement we want to clone.
 439  * \return A pointer to the clone of the statement provided as parameter.
 440  */
 441 osl_statement_p osl_statement_clone(osl_statement_p statement) {
 442   int first = 1;
 443   osl_statement_p clone = NULL, node, previous = NULL;
 444
 445   while (statement != NULL) {
 446     node             = osl_statement_malloc();
 447     node->domain     = osl_relation_clone(statement->domain);
 448     node->scattering = osl_relation_clone(statement->scattering);
 449     node->access     = osl_relation_list_clone(statement->access);
 450     node->iterators  = osl_generic_clone(statement->iterators);
 451     node->body       = osl_generic_clone(statement->body);
 452     node->next       = NULL;
 453
 454     if (first) {
 455       first = 0;
 456       clone = node;
 457       previous = node;
 458     }
 459     else {
 460       previous->next = node;
 461       previous = previous->next;
 462     }
 463
 464     statement = statement->next;
 465   }
 466
 467   return clone;
 468 }
 469
 470
 471 /**
 472  * osl_statement_equal function:
 473  * this function returns true if the two statements provided as parameters
 474  * are the same, false otherwise (the usr field is not tested).
 475  * \param[in] s1 The first statement.
 476  * \param[in] s2 The second statement.
 477  * \return 1 if s1 and s2 are the same (content-wise), 0 otherwise.
 478  */
 479 int osl_statement_equal(osl_statement_p s1, osl_statement_p s2) {
 480
 481   if (s1 == s2)
 482     return 1;
 483
 484   if (((s1->next != NULL) && (s2->next == NULL)) ||
 485       ((s1->next == NULL) && (s2->next != NULL))) {
 486     OSL_info("statements are not the same");
 487     return 0;
 488   }
 489
 490   if ((s1->next != NULL) && (s2->next != NULL)) {
 491     if (!osl_statement_equal(s1->next, s2->next)) {
 492       OSL_info("number of statements is not the same");
 493       return 0;
 494     }
 495   }
 496
 497   if (!osl_relation_equal(s1->domain, s2->domain)) {
 498     OSL_info("statement domains are not the same");
 499     return 0;
 500   }
 501
 502   if (!osl_relation_equal(s1->scattering, s2->scattering)) {
 503     OSL_info("statement scatterings are not the same");
 504     return 0;
 505   }
 506
 507   if (!osl_relation_list_equal(s1->access, s2->access)) {
 508     OSL_info("statement accesses are not the same");
 509     return 0;
 510   }
 511
 512   if (!osl_generic_equal(s1->iterators, s2->iterators)) {
 513     OSL_info("statement original iterators are not the same");
 514     return 0;
 515   }
 516
 517   if (!osl_generic_equal(s1->body, s2->body)) {
 518     OSL_info("statement bodies are not the same");
 519     return 0;
 520   }
 521
 522   return 1;
 523 }
 524
 525
 526 /**
 527  * osl_statement_integrity_check function:
 528  * this function checks that a statement is "well formed" according to some
 529  * expected properties (setting an expected value to OSL_UNDEFINED means
 530  * that we do not expect a specific value). It returns 0 if the check failed
 531  * or 1 if no problem has been detected.
 532  * \param[in] statement              The statement we want to check.
 533  * \param[in] expected_nb_parameters Expected number of parameters.
 534  * \return 0 if the integrity check fails, 1 otherwise.
 535  */
 536 int osl_statement_integrity_check(osl_statement_p statement,
 537                                   int expected_nb_parameters) {
 538   int expected_nb_iterators;
 539
 540   while (statement != NULL) {
 541     // Check the domain.
 542     if (!osl_relation_integrity_check(statement->domain,
 543                                       OSL_TYPE_DOMAIN,
 544                                       OSL_UNDEFINED,
 545                                       0,
 546                                       expected_nb_parameters)) {
 547       return 0;
 548     }
 549
 550     // Get the number of iterators.
 551     if (statement->domain != NULL)
 552       expected_nb_iterators = statement->domain->nb_output_dims;
 553     else
 554       expected_nb_iterators = OSL_UNDEFINED;
 555
 556     // Check the scattering relation.
 557     if (!osl_relation_integrity_check(statement->scattering,
 558                                       OSL_TYPE_SCATTERING,
 559                                       OSL_UNDEFINED,
 560                                       expected_nb_iterators,
 561                                       expected_nb_parameters)) {
 562       return 0;
 563     }
 564
 565     // Check the access relations.
 566     if (!osl_relation_list_integrity_check(statement->access,
 567                                            OSL_TYPE_ACCESS,
 568                                            OSL_UNDEFINED,
 569                                            expected_nb_iterators,
 570                                            expected_nb_parameters)) {
 571       return 0;
 572     }
 573
 574     // Check the statement body.
 575     if ((expected_nb_iterators != OSL_UNDEFINED) &&
 576         (statement->iterators != NULL) &&
 577         (statement->iterators->interface != NULL) &&
 578         (statement->iterators->interface->URI != NULL) &&
 579         (strcmp(statement->iterators->interface->URI, OSL_URI_STRINGS) == 0) &&
 580         (expected_nb_iterators !=
 581          osl_strings_size(statement->iterators->data))) {
 582       OSL_warning("unexpected number of original iterators");
 583       return 0;
 584     }
 585
 586     statement = statement->next;
 587   }
 588
 589   return 1;
 590 }
 591
 592
 593 /**
 594  * osl_statement_get_nb_iterators function:
 595  * this function returns the number of surroounding iterators of a given
 596  * statement.
 597  * \param statement The statement we want to know the number of iterators.
 598  * \return The number of surrounding iterators for the statement.
 599  */
 600 int osl_statement_get_nb_iterators(osl_statement_p statement) {
 601
 602   if (statement->domain == NULL) {
 603     OSL_warning("no statement domain, assuming 0 iterators");
 604     return 0;
 605   }
 606   else {
 607     return statement->domain->nb_output_dims;
 608   }
 609 }
 610
 611