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_idump 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_idump(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_idump(file, statement->domain, level+1);
 118
 119     // Print the scattering of the statement.
 120     openscop_relation_idump(file, statement->scattering, level+1);
 121
 122     // Print the array access information of the statement.
 123     openscop_relation_list_idump(file, statement->access, level+1);
 124
 125     // Print the statement body information.
 126     openscop_body_idump(file, statement->body, level+1);
 127
 128     // A blank line.
 129     for (i = 0; i <= level+1; i++)
 130       fprintf(file, "|\t");
 131     fprintf(file, "\n");
 132
 133     statement = statement->next;
 134     number++;
 135
 136     // Next line.
 137     if (statement != NULL) {
 138       for (j = 0; j <= level; j++)
 139         fprintf(file, "|\t");
 140       fprintf(file, "V\n");
 141     }
 142   }
 143
 144   // The last line.
 145   for (j = 0; j <= level; j++)
 146     fprintf(file, "|\t");
 147   fprintf(file, "\n");
 148 }
 149
 150
 151 /**
 152  * openscop_statement_dump function:
 153  * This function prints the content of a openscop_statement_t structure
 154  * (*statement) into  a file (file, possibly stdout).
 155  * \param file      File where informations are printed.
 156  * \param statement The statement whose information have to be printed.
 157  */
 158 void openscop_statement_dump(FILE * file, openscop_statement_p statement) {
 159   openscop_statement_idump(file, statement, 0);
 160 }
 161
 162
 163 /**
 164  * openscop_statement_print function:
 165  * This function prints the content of a openscop_statement_t structure
 166  * (*statement) into a file (file, possibly stdout) in the OpenScop format.
 167  * \param file      File where informations are printed.
 168  * \param statement The statement whose information have to be printed.
 169  * \param names     The textual names of the various elements.
 170  *                  Set to NULL if printing comments is not needed.
 171  */
 172 void openscop_statement_print(FILE * file,
 173                               openscop_statement_p statement,
 174                               openscop_names_p names) {
 175   int nb_relations, number = 1;
 176
 177   while (statement != NULL) {
 178     nb_relations = 0;
 179
 180     fprintf(file, "# =============================================== ");
 181     fprintf(file, "Statement %d\n", number);
 182
 183     fprintf(file, "# Number of relations describing the statement:\n");
 184
 185     if (statement->domain != NULL)
 186       nb_relations ++;
 187     if (statement->scattering != NULL)
 188       nb_relations ++;
 189     nb_relations += openscop_relation_list_count(statement->access);
 190
 191     fprintf(file, "%d\n\n", nb_relations);
 192
 193     fprintf(file, "# ---------------------------------------------- ");
 194     fprintf(file, "%2d.1 Domain\n", number);
 195     openscop_relation_print(file, statement->domain, names);
 196     fprintf(file, "\n");
 197
 198     fprintf(file, "# ---------------------------------------------- ");
 199     fprintf(file, "%2d.2 Scattering\n", number);
 200     openscop_relation_print(file, statement->scattering, names);
 201     fprintf(file, "\n");
 202
 203     fprintf(file, "# ---------------------------------------------- ");
 204     fprintf(file, "%2d.3 Access\n", number);
 205     openscop_relation_list_print_elts(file, statement->access, names);
 206     fprintf(file, "\n");
 207
 208     fprintf(file, "# ---------------------------------------------- ");
 209     fprintf(file, "%2d.4 Body\n", number);
 210     openscop_body_print(file, statement->body);
 211
 212     fprintf(file, "\n\n");
 213     statement = statement->next;
 214     number++;
 215   }
 216 }
 217
 218
 219 /*****************************************************************************
 220  *                               Reading function                            *
 221  *****************************************************************************/
 222
 223
 224 /**
 225  * openscop_statement_dispatch function:
 226  * this function dispatches the relations from a relation list to the
 227  * convenient fields of a statement structure: it extracts the domain,
 228  * the scattering and the access list and store them accordingly in the
 229  * statement structure provided as a parameter.
 230  * \param stmt The statement where to dispatch the relations.
 231  * \param list The "brute" relation list to sort and dispatch (freed).
 232  */
 233 static
 234 void openscop_statement_dispatch(openscop_statement_p stmt,
 235                                  openscop_relation_list_p list) {
 236   openscop_relation_list_p domain_list;
 237   openscop_relation_list_p scattering_list;
 238   int nb_domains, nb_scattering, nb_accesses;
 239
 240   // Domain.
 241   domain_list = openscop_relation_list_filter(list, OPENSCOP_TYPE_DOMAIN);
 242   nb_domains = openscop_relation_list_count(domain_list);
 243   if (nb_domains > 1)
 244     OPENSCOP_error("more than one domain for a statement");
 245
 246   if (domain_list != NULL) {
 247     stmt->domain = domain_list->elt;
 248     domain_list->elt = NULL;
 249     openscop_relation_list_free(domain_list);
 250   }
 251   else {
 252     stmt->domain = NULL;
 253   }
 254
 255   // Scattering.
 256   scattering_list=openscop_relation_list_filter(list,OPENSCOP_TYPE_SCATTERING);
 257   nb_scattering = openscop_relation_list_count(scattering_list);
 258   if (nb_scattering > 1)
 259     OPENSCOP_error("more than one scattering relation for a statement");
 260
 261   if (scattering_list != NULL) {
 262     stmt->scattering = scattering_list->elt;
 263     scattering_list->elt = NULL;
 264     openscop_relation_list_free(scattering_list);
 265   }
 266   else {
 267     stmt->scattering = NULL;
 268   }
 269
 270   // Access.
 271   stmt->access = openscop_relation_list_filter(list, OPENSCOP_TYPE_ACCESS);
 272   nb_accesses = openscop_relation_list_count(stmt->access);
 273
 274   if ((nb_domains + nb_scattering + nb_accesses) !=
 275       (openscop_relation_list_count(list)))
 276     OPENSCOP_error("unexpected relation type to define a statement");
 277
 278   openscop_relation_list_free(list);
 279 }
 280
 281
 282 /**
 283  * openscop_statement_read function:
 284  * This function reads a openscop_statement_t structure from an input stream
 285  * (possibly stdin).
 286  * \param file The input stream.
 287  * \return A pointer to the statement structure that has been read.
 288  */
 289 openscop_statement_p openscop_statement_read(FILE * file) {
 290   openscop_statement_p stmt = openscop_statement_malloc();
 291   openscop_relation_list_p list;
 292   int expected_nb_iterators;
 293
 294   if (file) {
 295     // Read all statement relations.
 296     list = openscop_relation_list_read(file);
 297
 298     // Store relations at the right place according to their type.
 299     openscop_statement_dispatch(stmt, list);
 300
 301     // Read the body information.
 302     if (stmt->domain != NULL) {
 303       expected_nb_iterators = stmt->domain->nb_output_dims;
 304     }
 305     else {
 306       OPENSCOP_warning("no domain, assuming 0 original iterator");
 307       expected_nb_iterators = 0;
 308     }
 309     stmt->body = openscop_body_read(file, expected_nb_iterators);
 310   }
 311
 312   return stmt;
 313 }
 314
 315
 316 /*+***************************************************************************
 317  *                   Memory allocation/deallocation functions                *
 318  *****************************************************************************/
 319
 320
 321 /**
 322  * openscop_statement_malloc function:
 323  * This function allocates the memory space for a openscop_statement_t
 324  * structure and sets its fields with default values. Then it returns a pointer
 325  * to the allocated space.
 326  * \return A pointer to an empty statement with fields set to default values.
 327  */
 328 openscop_statement_p openscop_statement_malloc() {
 329   openscop_statement_p statement;
 330
 331   OPENSCOP_malloc(statement, openscop_statement_p,
 332                   sizeof(openscop_statement_t));
 333   statement->domain     = NULL;
 334   statement->scattering = NULL;
 335   statement->access     = NULL;
 336   statement->body       = NULL;
 337   statement->next       = NULL;
 338
 339   return statement;
 340 }
 341
 342
 343 /**
 344  * openscop_statement_free function:
 345  * This function frees the allocated memory for a openscop_statement_t
 346  * structure.
 347  * \param statement The pointer to the statement we want to free.
 348  */
 349 void openscop_statement_free(openscop_statement_p statement) {
 350   openscop_statement_p next;
 351
 352   while (statement != NULL) {
 353     next = statement->next;
 354     openscop_relation_free(statement->domain);
 355     openscop_relation_free(statement->scattering);
 356     openscop_relation_list_free(statement->access);
 357     openscop_body_free(statement->body);
 358
 359     free(statement);
 360     statement = next;
 361   }
 362 }
 363
 364
 365 /*+***************************************************************************
 366  *                            Processing functions                           *
 367  *****************************************************************************/
 368
 369
 370 /**
 371  * openscop_statement_add function:
 372  * This function adds a statement "statement" at the end of the statement
 373  * list pointed by "location".
 374  * \param location  Address of the first element of the statement list.
 375  * \param statement The statement to add to the list.
 376  */
 377 void openscop_statement_add(openscop_statement_p * location,
 378                             openscop_statement_p   statement) {
 379   while (*location != NULL)
 380     location = &((*location)->next);
 381
 382   *location = statement;
 383 }
 384
 385
 386 /**
 387  * openscop_statement_number function:
 388  * This function returns the number of statements in the statement list
 389  * provided as parameter.
 390  * \param statement The first element of the statement list.
 391  * \return The number of statements in the statement list.
 392  */
 393 int openscop_statement_number(openscop_statement_p statement) {
 394   int number = 0;
 395
 396   while (statement != NULL) {
 397     number++;
 398     statement = statement->next;
 399   }
 400   return number;
 401 }
 402
 403
 404 /**
 405  * openscop_statement_copy function:
 406  * This functions builds and returns a "hard copy" (not a pointer copy) of a
 407  * openscop_statement_t data structure provided as parameter.
 408  * \param statement  The pointer to the statement we want to copy.
 409  * \return A pointer to the full copy of the statement provided as parameter.
 410  */
 411 openscop_statement_p openscop_statement_copy(openscop_statement_p statement) {
 412   int first = 1;
 413   openscop_statement_p copy = NULL, node, previous = NULL;
 414
 415   while (statement != NULL) {
 416     node               = openscop_statement_malloc();
 417     node->domain       = openscop_relation_copy(statement->domain);
 418     node->scattering   = openscop_relation_copy(statement->scattering);
 419     node->access       = openscop_relation_list_copy(statement->access);
 420     node->body         = openscop_body_copy(statement->body);
 421     node->next         = NULL;
 422
 423     if (first) {
 424       first = 0;
 425       copy = node;
 426       previous = node;
 427     }
 428     else {
 429       previous->next = node;
 430       previous = previous->next;
 431     }
 432
 433     statement = statement->next;
 434   }
 435
 436   return copy;
 437 }
 438
 439
 440 /**
 441  * openscop_statement_equal function:
 442  * This function returns true if the two statements are the same, false
 443  * otherwise (the usr field is not tested).
 444  * \param s1 The first statement.
 445  * \param s2 The second statement.
 446  * \return 1 if s1 and s2 are the same (content-wise), 0 otherwise.
 447  */
 448 int openscop_statement_equal(openscop_statement_p s1,
 449                              openscop_statement_p s2) {
 450
 451   if (s1 == s2)
 452     return 1;
 453
 454   if (((s1->next != NULL) && (s2->next == NULL)) ||
 455       ((s1->next == NULL) && (s2->next != NULL)))
 456     return 0;
 457
 458   if ((s1->next != NULL) && (s2->next != NULL))
 459     if (!openscop_statement_equal(s1->next, s2->next))
 460       return 0;
 461
 462   if ((!openscop_relation_equal(s1->domain,      s2->domain))     ||
 463       (!openscop_relation_equal(s1->scattering,  s2->scattering)) ||
 464       (!openscop_relation_list_equal(s1->access, s2->access))     ||
 465       (!openscop_body_equal(s1->body, s2->body)))
 466     return 0;
 467
 468   return 1;
 469 }
 470
 471
 472 /**
 473  * openscop_statement_integrity_check function:
 474  * This function checks that a statement is "well formed" according to some
 475  * expected properties (setting an expected value to OPENSCOP_UNDEFINED means
 476  * that we do not expect a specific value). It returns 0 if the check failed
 477  * or 1 if no problem has been detected.
 478  * \param statement               The statement we want to check.
 479  * \param expected_nb_parameters  Expected number of parameters.
 480  * \return 0 if the integrity check fails, 1 otherwise.
 481  */
 482 int openscop_statement_integrity_check(openscop_statement_p statement,
 483                                        int expected_nb_parameters) {
 484   int expected_nb_iterators;
 485
 486   while (statement != NULL) {
 487     // Check the domain.
 488     if (!openscop_relation_integrity_check(statement->domain,
 489                                            OPENSCOP_TYPE_DOMAIN,
 490                                            OPENSCOP_UNDEFINED,
 491                                            0,
 492                                            expected_nb_parameters)) {
 493       return 0;
 494     }
 495
 496     // Get the number of iterators.
 497     if (statement->domain != NULL)
 498       expected_nb_iterators = statement->domain->nb_output_dims;
 499     else
 500       expected_nb_iterators = OPENSCOP_UNDEFINED;
 501
 502     // Check the scattering relation.
 503     if (!openscop_relation_integrity_check(statement->scattering,
 504                                            OPENSCOP_TYPE_SCATTERING,
 505                                            OPENSCOP_UNDEFINED,
 506                                            expected_nb_iterators,
 507                                            expected_nb_parameters)) {
 508       return 0;
 509     }
 510
 511     // Check the access relations.
 512     if (!openscop_relation_list_integrity_check(statement->access,
 513                                            OPENSCOP_TYPE_ACCESS,
 514                                            OPENSCOP_UNDEFINED,
 515                                            expected_nb_iterators,
 516                                            expected_nb_parameters)) {
 517       return 0;
 518     }
 519
 520     // Check the statement body.
 521     if (!openscop_body_integrity_check(statement->body,
 522                                            expected_nb_iterators)) {
 523       return 0;
 524     }
 525
 526     statement = statement->next;
 527   }
 528
 529   return 1;
 530 }