source/transformation.c

   1
   2    /*--------------------------------------------------------------------+
   3     |                              Clay                                  |
   4     |--------------------------------------------------------------------|
   5     |                           transformation.c                         |
   6     |--------------------------------------------------------------------|
   7     |                    First version: 03/04/2012                       |
   8     +--------------------------------------------------------------------+
   9
  10  +--------------------------------------------------------------------------+
  11  |  / __)(  )    /__\ ( \/ )                                                |
  12  | ( (__  )(__  /(__)\ \  /         Chunky Loop Alteration wizardrY         |
  13  |  \___)(____)(__)(__)(__)                                                 |
  14  +--------------------------------------------------------------------------+
  15  | Copyright (C) 2012 University of Paris-Sud                               |
  16  |                                                                          |
  17  | This library is free software; you can redistribute it and/or modify it  |
  18  | under the terms of the GNU Lesser General Public License as published by |
  19  | the Free Software Foundation; either version 2.1 of the License, or      |
  20  | (at your option) any later version.                                      |
  21  |                                                                          |
  22  | This library is distributed in the hope that it will be useful but       |
  23  | WITHOUT ANY WARRANTY; without even the implied warranty of               |
  24  | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser  |
  25  | General Public License for more details.                                 |
  26  |                                                                          |
  27  | You should have received a copy of the GNU Lesser General Public License |
  28  | along with this software; if not, write to the Free Software Foundation, |
  29  | Inc., 51 Franklin Street, Fifth Floor,                                   |
  30  | Boston, MA  02110-1301  USA                                              |
  31  |                                                                          |
  32  | Clay, the Chunky Loop Alteration wizardrY                                |
  33  | Written by Joel Poudroux, joel.poudroux@u-psud.fr                        |
  34  +--------------------------------------------------------------------------*/
  35
  36 #include <stdio.h>
  37 #include <stdlib.h>
  38 #include <string.h>
  39
  40 #include <osl/macros.h>
  41 #include <osl/scop.h>
  42 #include <osl/body.h>
  43 #include <osl/strings.h>
  44 #include <osl/util.h>
  45 #include <osl/statement.h>
  46 #include <osl/relation.h>
  47 #include <osl/generic.h>
  48 #include <osl/extensions/scatnames.h>
  49 #include <osl/extensions/arrays.h>
  50 #include <osl/extensions/extbody.h>
  51
  52 #include <clay/transformation.h>
  53 #include <clay/array.h>
  54 #include <clay/list.h>
  55 #include <clay/macros.h>
  56 #include <clay/options.h>
  57 #include <clay/errors.h>
  58 #include <clay/beta.h>
  59 #include <clay/util.h>
  60
  61
  62 /*****************************************************************************\
  63  *                     Loop transformations                                   *
  64  `****************************************************************************/
  65
  66
  67 /**
  68  * clay_reorder function:
  69  * Reorders the statements in the loop
  70  * \param[in,out] scop
  71  * \param[in] beta_loop     Loop beta vector
  72  * \param[in] order         Array to reorder the statements
  73  * \param[in] options
  74  * \return                  Status
  75  */
  76 int clay_reorder(osl_scop_p scop,
  77                  clay_array_p beta_loop, clay_array_p neworder,
  78                  clay_options_p options) {
  79
  80   /* Description:
  81    * Modify the beta in function of the values in the neworder array.
  82    */
  83
  84   osl_relation_p scattering;
  85   osl_statement_p statement;
  86   int precision;
  87   const int column = beta_loop->size * 2; // alpha column
  88   int row;
  89   int index;
  90
  91   // important to be sure that the scop normalized first
  92   // because we access to the reorder array in function of the beta value
  93   clay_beta_normalize(scop);
  94
  95   statement = clay_beta_find(scop->statement, beta_loop);
  96   if (!statement)
  97     return CLAY_ERROR_BETA_NOT_FOUND;
  98
  99   CLAY_BETA_IS_LOOP(beta_loop, statement);
 100
 101   precision = statement->scattering->precision;
 102   while (statement != NULL) {
 103     if (clay_beta_check(statement, beta_loop)) {
 104
 105       scattering = statement->scattering;
 106       row = clay_util_relation_get_line(scattering, column);
 107
 108       // get the beta value
 109       index = osl_int_get_si(precision,
 110                              scattering->m[row][scattering->nb_columns-1]);
 111
 112       if (index >= neworder->size)
 113         return CLAY_ERROR_REORDER_ARRAY_TOO_SMALL;
 114
 115       osl_int_set_si(precision,
 116                      &scattering->m[row][scattering->nb_columns-1],
 117                      neworder->data[index]);
 118     }
 119     statement = statement->next;
 120   }
 121
 122   if (options && options->normalize)
 123     clay_beta_normalize(scop);
 124
 125   return CLAY_SUCCESS;
 126 }
 127
 128
 129 /**
 130  * clay_reverse function:
 131  * Reverse the direction of the loop
 132  * \param[in,out] scop
 133  * \param[in] beta          Beta vector
 134  * \param[in] options
 135  * \return                  Status
 136  */
 137 int clay_reverse(osl_scop_p scop, clay_array_p beta, unsigned int depth,
 138                  clay_options_p options) {
 139
 140   /* Description:
 141    * Oppose the output_dims column at the `depth'th level.
 142    */
 143
 144   if (beta->size == 0)
 145     return CLAY_ERROR_BETA_EMPTY;
 146   if (depth <= 0)
 147     return CLAY_ERROR_DEPTH_OVERFLOW;
 148
 149   osl_relation_p scattering;
 150   osl_statement_p statement = scop->statement;
 151   int precision;
 152   int column = depth*2 - 1; // iterator column
 153   int i;
 154
 155   statement = clay_beta_find(statement, beta);
 156   if (!statement)
 157     return CLAY_ERROR_BETA_NOT_FOUND;
 158
 159   CLAY_BETA_CHECK_DEPTH(beta, depth, statement);
 160
 161   precision = statement->scattering->precision;
 162   while (statement != NULL) {
 163     if (clay_beta_check(statement, beta)) {
 164       scattering = statement->scattering;
 165       for(i = 0 ; i < scattering->nb_rows ; i++) {
 166         osl_int_oppose(precision,
 167                        &scattering->m[i][column+1],
 168                        scattering->m[i][column+1]);
 169       }
 170     }
 171     statement = statement->next;
 172   }
 173
 174   return CLAY_SUCCESS;
 175 }
 176
 177
 178 /**
 179  * clay_interchange function:
 180  * On each statement which belongs to the `beta', the loops that match the
 181  * `depth_1'th and the `depth_2' are interchanged
 182  * /!\ If you want to interchange 2 loops, you must give the inner beta loop
 183  * and not the outer !
 184  * \param[in,out] scop
 185  * \param[in] beta          Beta vector (inner loop or statement)
 186  * \param[in] depth_1       >= 1
 187  * \param[in] depth_2       >= 1
 188  * \param[in] pretty        1 or 0 : update the scatnames
 189  * \param[in] options
 190  * \return                  Status
 191  */
 192 int clay_interchange(osl_scop_p scop,
 193                       clay_array_p beta,
 194                       unsigned int depth_1, unsigned int depth_2,
 195                       int pretty,
 196                       clay_options_p options) {
 197   /* Description:
 198    * Swap the two output_dims columns.
 199    */
 200
 201   if (beta->size == 0)
 202     return CLAY_ERROR_BETA_EMPTY;
 203   if (depth_1 <= 0 || depth_2 <= 0)
 204     return CLAY_ERROR_DEPTH_OVERFLOW;
 205
 206   osl_statement_p statement = scop->statement;
 207   osl_relation_p scattering;
 208   int precision;
 209   const int column_1 = depth_1*2 - 1; // iterator column
 210   const int column_2 = depth_2*2 - 1;
 211   int i;
 212   osl_int_t **matrix;
 213   //int nb_rows;
 214
 215   statement = clay_beta_find(statement, beta);
 216   if (!statement)
 217     return CLAY_ERROR_BETA_NOT_FOUND;
 218   if (statement->scattering->nb_output_dims == 1)
 219     return CLAY_ERROR_DEPTH_OVERFLOW;
 220
 221   CLAY_BETA_CHECK_DEPTH(beta, depth_1, statement);
 222   CLAY_BETA_CHECK_DEPTH(beta, depth_2, statement);
 223
 224   // it's not useful to interchange the same line
 225   if (depth_1 == depth_2)
 226     return CLAY_SUCCESS;
 227
 228   precision = statement->scattering->precision;
 229   while (statement != NULL) {
 230
 231     if (clay_beta_check(statement, beta)) {
 232       scattering = statement->scattering;
 233
 234       //nb_rows = scattering->nb_rows;
 235       //if (column_1 >= nb_rows || column_2 >= nb_rows)
 236       //  return CLAY_DEPTH_OVERFLOW;
 237
 238       // swap the two columns
 239       matrix = scattering->m;
 240       for (i = 0 ; i < scattering->nb_rows ; i++)
 241         osl_int_swap(precision,
 242                      &matrix[i][column_1+1],
 243                      &matrix[i][column_2+1]);
 244     }
 245
 246     statement = statement->next;
 247   }
 248
 249   // swap the two variables
 250   if (pretty) {
 251     osl_scatnames_p scat;
 252     osl_strings_p names;
 253     scat = osl_generic_lookup(scop->extension, OSL_URI_SCATNAMES);
 254     names = scat->names;
 255
 256     int ii = 0;
 257     for (ii = 0 ; names->string[ii] ; ii++)
 258       ;
 259
 260     int c1 = depth_1 * 2 - 1;
 261     int c2 = depth_2 * 2 - 1;
 262
 263     if (c1 < ii && c2 < ii) {
 264       char *tmp = names->string[c1];
 265       names->string[c1] = names->string[c2];
 266       names->string[c2] = tmp;
 267     }
 268   }
 269
 270   return CLAY_SUCCESS;
 271 }
 272
 273
 274 /**
 275  * clay_split function:
 276  * Split the loop in two parts at the `depth'th level from the statement
 277  * \param[in,out] scop
 278  * \param[in] beta          Beta vector
 279  * \param[in] depth         >= 1
 280  * \param[in] options
 281  * \return                  Status
 282  */
 283 int clay_split(osl_scop_p scop, clay_array_p beta, unsigned int depth,
 284                clay_options_p options) {
 285
 286   /* Description:
 287    * Add one on the beta at the `depth'th level.
 288    */
 289
 290   if (beta->size == 0)
 291     return CLAY_ERROR_BETA_EMPTY;
 292   if (beta->size <= 1 || depth <= 0 || depth >= beta->size)
 293     return CLAY_ERROR_DEPTH_OVERFLOW;
 294
 295   osl_statement_p statement = scop->statement;
 296   statement = clay_beta_find(statement, beta);
 297   if (!statement)
 298     return CLAY_ERROR_BETA_NOT_FOUND;
 299
 300   clay_beta_shift_after(scop->statement, beta, depth);
 301
 302   if (options && options->normalize)
 303     clay_beta_normalize(scop);
 304
 305   return CLAY_SUCCESS;
 306 }
 307
 308
 309 /**
 310  * clay_fuse function:
 311  * Fuse loop with the first loop after
 312  * \param[in,out] scop
 313  * \param[in] beta_loop     Loop beta vector
 314  * \param[in] options
 315  * \return                  Status
 316  */
 317 int clay_fuse(osl_scop_p scop, clay_array_p beta_loop,
 318               clay_options_p options) {
 319
 320   /* Description:
 321    * Set the same beta (only at the level of the beta_loop) on the next loop.
 322    */
 323
 324   if (beta_loop->size == 0)
 325     return CLAY_ERROR_BETA_EMPTY;
 326
 327   osl_relation_p scattering;
 328   osl_statement_p statement;
 329   clay_array_p beta_max;
 330   clay_array_p beta_next;
 331   int precision;
 332   const int depth = beta_loop->size;
 333   const int column = beta_loop->size*2; // alpha column
 334   int row;
 335
 336   statement = clay_beta_find(scop->statement, beta_loop);
 337   if (!statement)
 338     return CLAY_ERROR_BETA_NOT_FOUND;
 339
 340   CLAY_BETA_IS_LOOP(beta_loop, statement);
 341
 342   precision = statement->scattering->precision;
 343
 344   beta_max = clay_beta_max(statement, beta_loop);
 345   beta_next = clay_beta_next_part(scop->statement, beta_loop);
 346
 347   if (beta_next != NULL) {
 348     beta_next->size = depth;
 349     statement = scop->statement;
 350     while (statement != NULL) {
 351       if (clay_beta_check(statement, beta_next)) {
 352         scattering = statement->scattering;
 353         if (column < scattering->nb_output_dims) {
 354
 355           // Set the loop level
 356           row = clay_util_relation_get_line(scattering, column-2);
 357           osl_int_set_si(precision,
 358                          &scattering->m[row][scattering->nb_columns-1],
 359                          beta_loop->data[depth-1]);
 360
 361           // Reorder the statement
 362           row = clay_util_relation_get_line(scattering, column);
 363           osl_int_add_si(precision,
 364                          &scattering->m[row][scattering->nb_columns-1],
 365                          scattering->m[row][scattering->nb_columns-1],
 366                          beta_max->data[depth]+1);
 367         }
 368       }
 369       statement = statement->next;
 370     }
 371     clay_array_free(beta_next);
 372   }
 373
 374   clay_array_free(beta_max);
 375
 376   if (options && options->normalize)
 377     clay_beta_normalize(scop);
 378
 379   return CLAY_SUCCESS;
 380 }
 381
 382
 383 /**
 384  * clay_skew function:
 385  * Skew the loop (or statement) from the `depth'th loop
 386  * (i, j) -> (i, j+i*coeff) where `depth' is the loop of i
 387  * \param[in,out] scop
 388  * \param[in] beta          Beta vector
 389  * \param[in] depth         >= 1
 390  * \param[in] coeff         != 0
 391  * \param[in] options
 392  * \return                  Status
 393  */
 394 int clay_skew(osl_scop_p scop,
 395               clay_array_p beta, unsigned int depth, unsigned int coeff,
 396               clay_options_p options) {
 397
 398   /* Description:
 399    * This is a special case of shifting, where params and constant
 400    * are equal to zero
 401    */
 402
 403   if (beta->size == 0)
 404     return CLAY_ERROR_BETA_EMPTY;
 405   if (depth <= 0 || depth > beta->size)
 406     return CLAY_ERROR_DEPTH_OVERFLOW;
 407   if (coeff == 0)
 408     return CLAY_ERROR_WRONG_COEFF;
 409
 410   clay_list_p vector;
 411   int i, ret;
 412
 413   // create the vector
 414   vector = clay_list_malloc();
 415
 416   // empty arrays
 417   clay_list_add(vector, clay_array_malloc());
 418   clay_list_add(vector, clay_array_malloc());
 419   clay_list_add(vector, clay_array_malloc());
 420
 421   // set output dims
 422   for (i = 0 ; i < depth-1 ; i++)
 423     clay_array_add(vector->data[0], 0);
 424   clay_array_add(vector->data[0], coeff);
 425
 426   ret = clay_shift(scop, beta, depth, vector, options);
 427   clay_list_free(vector);
 428
 429   return ret;
 430 }
 431
 432
 433 /**
 434  * clay_iss function:
 435  * Split the loop (or statement) depending of an inequation.
 436  * Warning: in the output part, don't put the alpha columns
 437  *          example: if the output dims are : 0 i 0 j 0, just do Ni, Nj
 438  * \param[in,out] scop
 439  * \param[in]  beta_loop         Beta loop
 440  * \param[in]  inequation array  {(([output, ...],) [param, ...],) [const]}
 441  * \param[out] beta_max          If NULL, the beta_max will not be returned.
 442  *                               If function terminated successfully, the last
 443  *                               beta which has the prefix beta_loop, NULL
 444  *                               otherwise
 445  * \param[in]  options
 446  * \return                       Status
 447  */
 448 int clay_iss(osl_scop_p scop,
 449              clay_array_p beta_loop, clay_list_p inequ,
 450              clay_array_p *ret_beta_max,
 451              clay_options_p options) {
 452
 453   /* Description:
 454    * Add the inequality for each statements corresponding to the beta.
 455    * Clone each statements and add the beta on the last beta value
 456    */
 457
 458   if (beta_loop->size == 0)
 459     return CLAY_ERROR_BETA_EMPTY;
 460   if (inequ->size > 3)
 461     return CLAY_ERROR_INEQU;
 462
 463   osl_statement_p statement, newstatement;
 464   osl_relation_p scattering;
 465   clay_array_p beta_max;
 466   const int column = beta_loop->size*2; // beta column
 467   int nb_output_dims, nb_parameters;
 468   int order; // new loop order for the clones
 469
 470   // search a statement
 471   statement = clay_beta_find(scop->statement, beta_loop);
 472   if (!statement)
 473     return CLAY_ERROR_BETA_NOT_FOUND;
 474   if (statement->scattering->nb_input_dims == 0)
 475     return CLAY_ERROR_BETA_NOT_IN_A_LOOP;
 476
 477   CLAY_BETA_IS_LOOP(beta_loop, statement);
 478
 479   // decompose the inequation
 480   nb_parameters = scop->context->nb_parameters;
 481   nb_output_dims = statement->scattering->nb_output_dims;
 482
 483   if (inequ->size == 3) {
 484     // pad zeros
 485     clay_util_array_output_dims_pad_zero(inequ->data[0]);
 486
 487     if (inequ->data[0]->size > nb_output_dims ||
 488         inequ->data[1]->size > nb_parameters ||
 489         inequ->data[2]->size > 1)
 490       return CLAY_ERROR_INEQU;
 491
 492   } else if (inequ->size == 2) {
 493     if (inequ->data[0]->size > nb_parameters ||
 494         inequ->data[1]->size > 1)
 495       return CLAY_ERROR_INEQU;
 496
 497   } else if (inequ->size == 1) {
 498     if (inequ->data[0]->size > 1)
 499       return CLAY_ERROR_INEQU;
 500   }
 501
 502   // set the beginning of 'order'
 503   beta_max = clay_beta_max(statement, beta_loop);
 504   order = beta_max->data[beta_loop->size] + 1;
 505   if (ret_beta_max == NULL) {
 506     clay_array_free(beta_max);
 507   } else {
 508     *ret_beta_max = beta_max;
 509   }
 510
 511   // ensure ret_beta_max is set up before returning success
 512   if (inequ->size == 0)
 513     return CLAY_SUCCESS;
 514
 515   // insert the inequation on each statements
 516   while (statement != NULL) {
 517     if (clay_beta_check(statement, beta_loop)) {
 518
 519       // insert the inequation
 520       clay_util_statement_set_inequation(statement, inequ);
 521
 522       // clone and negate the inequation
 523       newstatement = osl_statement_nclone(statement, 1);
 524       scattering = newstatement->scattering;
 525       clay_util_relation_negate_row(scattering, scattering->nb_rows-1);
 526
 527       statement = clay_util_statement_insert(statement, newstatement,
 528                                              column, order);
 529       order++;
 530     }
 531     statement = statement->next;
 532   }
 533
 534   if (options && options->normalize)
 535     clay_beta_normalize(scop);
 536
 537   return CLAY_SUCCESS;
 538 }
 539
 540
 541 /**
 542  * clay_stripmine function:
 543  * Decompose a single loop into two nested loop
 544  * \param[in,out] scop
 545  * \param[in] beta          Beta vector (loop or statement)
 546  * \param[in] size          Block size of the inner loop
 547  * \param[in] pretty        If true, clay will keep the variables name
 548  * \param[in] options
 549  * \return                  Status
 550  */
 551 int clay_stripmine(osl_scop_p scop, clay_array_p beta,
 552                    unsigned int depth, unsigned int size,
 553                    int pretty, clay_options_p options) {
 554
 555   /* Description:
 556    * Add two inequality for the stripmining.
 557    * The new dependance with the loop is done on an output_dim.
 558    * If pretty is true, we add for each statements (not only the beta) two
 559    * output_dims (one for the iterator and one for the 2*n+1).
 560    */
 561
 562   if (beta->size == 0)
 563     return CLAY_ERROR_BETA_EMPTY;
 564   if (size <= 0)
 565     return CLAY_ERROR_WRONG_BLOCK_SIZE;
 566   if (depth <= 0)
 567     return CLAY_ERROR_DEPTH_OVERFLOW;
 568
 569   osl_relation_p scattering;
 570   osl_statement_p statement = scop->statement;
 571   osl_scatnames_p scat;
 572   osl_strings_p names;
 573   int column = (depth-1)*2; // alpha column
 574   int precision;
 575   int row, row_next;
 576   int i;
 577   int nb_strings;
 578   char buffer[OSL_MAX_STRING];
 579   char *new_var_iter;
 580   char *new_var_beta;
 581
 582   statement = clay_beta_find(statement, beta);
 583   if (!statement)
 584     return CLAY_ERROR_BETA_NOT_FOUND;
 585   if (statement->scattering->nb_output_dims < 3)
 586     return CLAY_ERROR_BETA_NOT_IN_A_LOOP;
 587
 588   CLAY_BETA_CHECK_DEPTH(beta, depth, statement);
 589
 590   precision = statement->scattering->precision;
 591   if (pretty)
 592     statement = scop->statement; // TODO optimization...
 593
 594   while (statement != NULL) {
 595     scattering = statement->scattering;
 596     if (clay_beta_check(statement, beta)) {
 597
 598       // set the strip mine
 599       row = clay_util_relation_get_line(scattering, column);
 600
 601       osl_relation_insert_blank_column(scattering, column+1);
 602       osl_relation_insert_blank_column(scattering, column+1);
 603
 604       osl_relation_insert_blank_row(scattering, column);
 605       osl_relation_insert_blank_row(scattering, column);
 606       osl_relation_insert_blank_row(scattering, column);
 607
 608       // stripmine
 609       osl_int_set_si(precision, &scattering->m[row+0][column+1], -1);
 610       osl_int_set_si(precision, &scattering->m[row+1][column+2], -size);
 611       osl_int_set_si(precision, &scattering->m[row+2][column+2], size);
 612       osl_int_set_si(precision,
 613                      &scattering->m[row+2][scattering->nb_columns-1],
 614                      size-1);
 615
 616       // inequality
 617       osl_int_set_si(precision, &scattering->m[row+1][0], 1);
 618       osl_int_set_si(precision, &scattering->m[row+2][0], 1);
 619
 620       // iterator dependance
 621       osl_int_set_si(precision, &scattering->m[row+1][column+4], 1);
 622       osl_int_set_si(precision, &scattering->m[row+2][column+4], -1);
 623
 624       scattering->nb_output_dims += 2;
 625
 626       // reorder
 627       row_next = clay_util_relation_get_line(scattering, column+2);
 628       osl_int_assign(precision,
 629                      &scattering->m[row][scattering->nb_columns-1],
 630                      scattering->m[row_next][scattering->nb_columns-1]);
 631
 632       osl_int_set_si(precision,
 633                      &scattering->m[row_next][scattering->nb_columns-1],
 634                      0);
 635
 636     } else if (pretty && column < scattering->nb_output_dims) {
 637       // add 2 empty dimensions
 638       row = clay_util_relation_get_line(scattering, column);
 639
 640       osl_relation_insert_blank_column(scattering, column+1);
 641       osl_relation_insert_blank_column(scattering, column+1);
 642
 643       osl_relation_insert_blank_row(scattering, column);
 644       osl_relation_insert_blank_row(scattering, column);
 645
 646       // -Identity
 647       osl_int_set_si(precision, &scattering->m[row][column+1], -1);
 648       osl_int_set_si(precision, &scattering->m[row+1][column+2], -1);
 649
 650       scattering->nb_output_dims += 2;
 651
 652       // reorder
 653       row_next = clay_util_relation_get_line(scattering, column+2);
 654       osl_int_assign(precision,
 655                      &scattering->m[row][scattering->nb_columns-1],
 656                      scattering->m[row_next][scattering->nb_columns-1]);
 657
 658       osl_int_set_si(precision,
 659                      &scattering->m[row_next][scattering->nb_columns-1],
 660                      0);
 661     }
 662     statement = statement->next;
 663   }
 664
 665   // get the list of scatnames
 666   scat = osl_generic_lookup(scop->extension, OSL_URI_SCATNAMES);
 667   names = scat->names;
 668
 669   // generate iterator variable name
 670   i = 0;
 671   do {
 672     sprintf(buffer, "__%s%s%d", names->string[column+1],
 673             names->string[column+1], i);
 674     i++;
 675   } while (clay_util_scatnames_exists(scat, buffer));
 676   new_var_iter = strdup(buffer);
 677
 678   // generate beta variable name
 679   i = 0;
 680   do {
 681     sprintf(buffer, "__b%d", i);
 682     i++;
 683   } while (clay_util_scatnames_exists(scat, buffer));
 684   new_var_beta = strdup(buffer);
 685
 686   // insert the two variables
 687   nb_strings = osl_strings_size(names) + 2;
 688   osl_strings_p newnames = osl_strings_malloc();
 689   CLAY_malloc(newnames->string, char**, sizeof(char**) * (nb_strings + 1));
 690
 691   for (i = 0 ; i < column ; i++)
 692     newnames->string[i] = names->string[i];
 693
 694   newnames->string[i] = new_var_beta;
 695   newnames->string[i+1] = new_var_iter;
 696
 697   for (i = i+2 ; i < nb_strings ; i++)
 698     newnames->string[i] = names->string[i-2];
 699
 700   newnames->string[i] = NULL; // end of the list
 701
 702   // replace the scatnames
 703   free(names->string);
 704   free(names);
 705   scat->names = newnames;
 706
 707   if (options && options->normalize)
 708     clay_beta_normalize(scop);
 709
 710   return CLAY_SUCCESS;
 711 }
 712
 713
 714 /** clay_unroll function: Unroll a loop \param[in,out] scop \param[in]
 715  * beta_loop     Loop beta vector \param[in] factor        > 0 \param[in]
 716  * setepilog     if true the epilog will be added \param[in] options \return
 717  * Status
 718  */
 719 int clay_unroll(osl_scop_p scop, clay_array_p beta_loop, unsigned int factor,
 720                 int setepilog, clay_options_p options) {
 721
 722   /* Description:
 723    * Clone statements in the beta_loop, and recreate the body.
 724    * Generate an epilog where the lower bound was removed.
 725    */
 726
 727   if (beta_loop->size == 0)
 728     return CLAY_ERROR_BETA_EMPTY;
 729   if (factor < 1)
 730     return CLAY_ERROR_WRONG_FACTOR;
 731   if (factor == 1)
 732     return CLAY_SUCCESS;
 733
 734   osl_relation_p scattering;
 735   osl_relation_p domain;
 736   osl_relation_p epilog_domain = NULL;
 737   osl_statement_p statement;
 738   osl_statement_p newstatement;
 739   osl_statement_p original_stmt;
 740   osl_statement_p epilog_stmt;
 741   clay_array_p beta_max;
 742   int column = beta_loop->size*2;
 743   int precision;
 744   int row;
 745   int nb_stmts;
 746   int i;
 747   int max; // last value of beta_max
 748   int order;
 749   int order_epilog = 0; // order juste after the beta_loop
 750   int current_stmt = 0; // counter of statements
 751   int last_level = -1;
 752   int current_level;
 753
 754   osl_body_p body = NULL;
 755   osl_extbody_p ext_body = NULL;
 756   osl_body_p newbody = NULL;
 757   osl_extbody_p newextbody = NULL;
 758   osl_body_p tmpbody = NULL;
 759   osl_generic_p gen = NULL;
 760   char *expression;
 761   char **iterator;
 762   char *substitued;
 763   char *newexpression;
 764   char *replacement;
 765   char substitution[] = "@0@";
 766
 767   int iterator_index = beta_loop->size-1;
 768   int iterator_size;
 769
 770   int is_extbody = 0;
 771
 772   statement = clay_beta_find(scop->statement, beta_loop);
 773   if (!statement)
 774     return CLAY_ERROR_BETA_NOT_FOUND;
 775
 776   CLAY_BETA_IS_LOOP(beta_loop, statement);
 777
 778   precision = statement->scattering->precision;
 779
 780   // alloc an array of string, wich will contain the current iterator and NULL
 781   // used for osl_util_identifier_substitution with only one variable
 782   CLAY_malloc(iterator, char**, sizeof(char*)*2);
 783   iterator[1] = NULL;
 784
 785   // infos used to reorder cloned statements
 786   nb_stmts = clay_beta_nb_parts(statement, beta_loop);
 787   beta_max = clay_beta_max(statement, beta_loop);
 788   max = beta_max->data[beta_max->size-1];
 789   clay_array_free(beta_max);
 790
 791   if (setepilog) {
 792     // shift to let the place for the epilog loop
 793     clay_beta_shift_after(scop->statement, beta_loop, beta_loop->size);
 794     order_epilog = beta_loop->data[beta_loop->size-1] + 1;
 795   }
 796
 797   while (statement != NULL) {
 798     scattering = statement->scattering;
 799
 800     if (clay_beta_check(statement, beta_loop)) {
 801
 802       // create the body with symbols for the substitution
 803       original_stmt = statement;
 804
 805       ext_body = osl_generic_lookup(statement->extension,
 806                                OSL_URI_EXTBODY);
 807       if (ext_body) {
 808         body = ext_body->body;
 809         is_extbody = 1;
 810       }
 811       else {
 812         body = (osl_body_p)osl_generic_lookup(statement->extension,
 813                                 OSL_URI_BODY);
 814       }
 815       if (body==NULL)
 816         CLAY_error("Missing statement body\n");
 817
 818       expression = body->expression->string[0];
 819       iterator[0] = (char*) body->iterators->string[iterator_index];
 820       iterator_size = strlen(iterator[0]);
 821       substitued = osl_util_identifier_substitution(expression, iterator);
 822
 823       CLAY_malloc(replacement, char*, 1 + iterator_size + 1 + 16 + 1 + 1);
 824
 825       if (setepilog) {
 826         // set the epilog from the original statement
 827         epilog_stmt = osl_statement_nclone(original_stmt, 1);
 828         row = clay_util_relation_get_line(original_stmt->scattering, column-2);
 829         scattering = epilog_stmt->scattering;
 830         osl_int_set_si(precision,
 831                        &scattering->m[row][scattering->nb_columns-1],
 832                        order_epilog);
 833
 834         // the order is not important in the statements list
 835         epilog_stmt->next = statement->next;
 836         statement->next = epilog_stmt;
 837         statement = epilog_stmt;
 838       }
 839
 840       // modify the matrix domain
 841       domain = original_stmt->domain;
 842
 843       if (setepilog) {
 844         epilog_domain = epilog_stmt->domain;
 845       }
 846
 847       while (domain != NULL) {
 848
 849         for (i = domain->nb_rows-1 ; i >= 0  ; i--) {
 850           if (!osl_int_zero(precision, domain->m[i][0])) {
 851
 852             // remove the lower bound on the epilog statement
 853             if(setepilog &&
 854                osl_int_pos(precision, domain->m[i][iterator_index+1])) {
 855               osl_relation_remove_row(epilog_domain, i);
 856             }
 857             // remove the upper bound on the original statement
 858             if (osl_int_neg(precision, domain->m[i][iterator_index+1])) {
 859               osl_int_add_si(precision,
 860                              &domain->m[i][domain->nb_columns-1],
 861                              domain->m[i][domain->nb_columns-1],
 862                              -factor);
 863             }
 864           }
 865         }
 866
 867         // add local dim on the original statement
 868         osl_relation_insert_blank_column(domain, domain->nb_output_dims+1);
 869         osl_relation_insert_blank_row(domain, 0);
 870         (domain->nb_local_dims)++;
 871         osl_int_set_si(precision,
 872                        &domain->m[0][domain->nb_output_dims+1],
 873                        -factor);
 874         osl_int_set_si(precision, &domain->m[0][iterator_index+1], 1);
 875
 876         domain = domain->next;
 877
 878         if (setepilog)
 879           epilog_domain = epilog_domain->next;
 880       }
 881
 882       // clone factor-1 times the original statement
 883
 884       row = clay_util_relation_get_line(original_stmt->scattering, column);
 885       current_level = osl_int_get_si(scattering->precision,
 886                                  scattering->m[row][scattering->nb_columns-1]);
 887       if (last_level != current_level) {
 888         current_stmt++;
 889         last_level = current_level;
 890       }
 891
 892       for (i = 0 ; i < factor-1 ; i++) {
 893         newstatement = osl_statement_nclone(original_stmt, 1);
 894         scattering = newstatement->scattering;
 895
 896         // update the body
 897         sprintf(replacement, "(%s+%d)", iterator[0], i+1);
 898         newexpression = clay_util_string_replace(substitution, replacement,
 899                                             substitued);
 900
 901         if (is_extbody) {
 902           newextbody = osl_generic_lookup(newstatement->extension,
 903                            OSL_URI_EXTBODY);
 904           newbody = newextbody->body;
 905         }
 906         else {
 907           newbody = osl_generic_lookup(newstatement->extension, OSL_URI_BODY);
 908         }
 909
 910         free(newbody->expression->string[0]);
 911         newbody->expression->string[0] = newexpression;
 912
 913         // reorder
 914         order = current_stmt + max + nb_stmts*i;
 915         osl_int_set_si(precision,
 916                        &scattering->m[row][scattering->nb_columns-1],
 917                        order);
 918
 919         // synchronize extbody and body (if both are different)
 920         if (is_extbody) {
 921           tmpbody = osl_generic_lookup(newstatement->extension, OSL_URI_BODY);
 922           if (tmpbody) {
 923             osl_generic_remove(&newstatement->extension, OSL_URI_BODY);
 924             tmpbody = osl_body_clone(newbody);
 925             gen = osl_generic_shell(tmpbody, osl_body_interface());
 926             osl_generic_add(&newstatement->extension, gen);
 927           }
 928         }
 929
 930         // the order is not important in the statements list
 931         newstatement->next = statement->next;
 932         statement->next = newstatement;
 933         statement = newstatement;
 934       }
 935       free(substitued);
 936       free(replacement);
 937     }
 938     statement = statement->next;
 939   }
 940   free(iterator);
 941
 942   if (options && options->normalize)
 943     clay_beta_normalize(scop);
 944
 945   return CLAY_SUCCESS;
 946 }
 947
 948
 949 /**
 950  * clay_tile function:
 951  * Apply a stripmine then an interchange.
 952  * The stripmine is at the `depth'th level. Next interchange the level `depth'
 953  * and `depth_outer'
 954  * \param[in,out] scop
 955  * \param[in] beta          Beta vector
 956  * \param[in] depth         >=1
 957  * \param[in] size          >=1
 958  * \param[in] depth_outer   >=1
 959  * \param[in] pretty        See stripmine
 960  * \param[in] options
 961  * \return                  Status
 962  */
 963 int clay_tile(osl_scop_p scop,
 964               clay_array_p beta, unsigned int depth, unsigned int depth_outer,
 965               unsigned int size, int pretty, clay_options_p options) {
 966
 967   /* Description:
 968    * stripmine + interchange
 969    */
 970
 971   if (beta->size == 0)
 972     return CLAY_ERROR_BETA_EMPTY;
 973   if (size <= 0)
 974     return CLAY_ERROR_WRONG_BLOCK_SIZE;
 975   if (depth <= 0 || depth_outer <= 0)
 976     return CLAY_ERROR_DEPTH_OVERFLOW;
 977   if (depth_outer > depth)
 978     return CLAY_ERROR_DEPTH_OUTER;
 979
 980   int ret;
 981   ret = clay_stripmine(scop, beta, depth, size, pretty, options);
 982
 983   if (ret == CLAY_SUCCESS) {
 984     ret = clay_interchange(scop, beta, depth, depth_outer, pretty, options);
 985   }
 986
 987   return ret;
 988 }
 989
 990
 991 /**
 992  * clay_shift function:
 993  * Shift the iteration domain
 994  * Warning: in the output part, don't put the alpha columns
 995  *          example: if the output dims are : 0 i 0 j 0, just do Ni, Nj
 996  * \param[in,out] scop
 997  * \param[in] beta          Beta vector (loop or statement)
 998  * \param[in] depth         >=1
 999  * \param[in] vector        {(([output, ...],) [param, ...],) [const]}
1000  * \param[in] options
1001  * \return                  Status
1002  */
1003 int clay_shift(osl_scop_p scop,
1004                clay_array_p beta, unsigned int depth, clay_list_p vector,
1005                clay_options_p options) {
1006
1007   /* Description:
1008    * Add a vector on each statements.
1009    */
1010
1011   if (beta->size == 0)
1012     return CLAY_ERROR_BETA_EMPTY;
1013   if (vector->size == 0)
1014     return CLAY_ERROR_VECTOR_EMPTY;
1015   if (depth <= 0)
1016     return CLAY_ERROR_DEPTH_OVERFLOW;
1017   if (vector->size > 3)
1018     return CLAY_ERROR_VECTOR;
1019   if (vector->size == 0)
1020     return CLAY_SUCCESS;
1021
1022   osl_statement_p statement;
1023   const int column = depth*2 - 1; // iterator column
1024   int nb_parameters, nb_output_dims;
1025
1026   statement = clay_beta_find(scop->statement, beta);
1027   if (!statement)
1028     return CLAY_ERROR_BETA_NOT_FOUND;
1029   if (statement->scattering->nb_input_dims == 0)
1030     return CLAY_ERROR_BETA_NOT_IN_A_LOOP;
1031
1032   CLAY_BETA_CHECK_DEPTH(beta, depth, statement);
1033
1034   // decompose the vector
1035   nb_parameters = scop->context->nb_parameters;
1036   nb_output_dims = statement->scattering->nb_output_dims;
1037
1038   if (vector->size == 3) {
1039     // pad zeros
1040     clay_util_array_output_dims_pad_zero(vector->data[0]);
1041
1042     if (vector->data[0]->size > nb_output_dims ||
1043         vector->data[1]->size > nb_parameters ||
1044         vector->data[2]->size > 1)
1045       return CLAY_ERROR_VECTOR;
1046
1047   } else if (vector->size == 2) {
1048     if (vector->data[0]->size > nb_parameters ||
1049         vector->data[1]->size > 1)
1050       return CLAY_ERROR_VECTOR;
1051
1052   } else if (vector->size == 1) {
1053     if (vector->data[0]->size > 1)
1054       return CLAY_ERROR_VECTOR;
1055   }
1056
1057   // add the vector for each statements
1058   while (statement != NULL) {
1059     if (clay_beta_check(statement, beta))
1060       clay_util_statement_set_vector(statement, vector, column);
1061     statement = statement->next;
1062   }
1063
1064   if (options && options->normalize)
1065     clay_beta_normalize(scop);
1066
1067   return CLAY_SUCCESS;
1068 }
1069
1070
1071 /**
1072  * clay_peel function:
1073  * Removes the first or last iteration of the loop into separate code.
1074  * This is equivalent to an iss (without output dims) and a spliting
1075  * \param[in,out] scop
1076  * \param[in] beta_loop         Loop beta vector
1077  * \param[in] peeling list      { ([param, ...],) [const] }
1078  * \param[in] options
1079  * \return                      Status
1080  */
1081 int clay_peel(osl_scop_p scop,
1082               clay_array_p beta_loop, clay_list_p peeling,
1083               clay_options_p options) {
1084
1085   if (beta_loop->size == 0)
1086     return CLAY_ERROR_BETA_EMPTY;
1087   if (peeling->size >= 3)
1088     return CLAY_ERROR_INEQU;
1089   if (peeling->size == 0)
1090     return CLAY_SUCCESS;
1091
1092   clay_array_p arr_dims, beta_max;
1093   clay_list_p new_peeling;
1094   int i, ret;
1095
1096   // create output dims
1097   arr_dims = clay_array_malloc();
1098   for (i = 0 ; i < beta_loop->size-1 ; i++)
1099     clay_array_add(arr_dims, 0);
1100   clay_array_add(arr_dims, 1);
1101
1102   // create new peeling list
1103   new_peeling = clay_list_malloc();
1104   clay_list_add(new_peeling, arr_dims);
1105   if (peeling->size == 2) {
1106     clay_list_add(new_peeling, peeling->data[0]);
1107     clay_list_add(new_peeling, peeling->data[1]);
1108   } else {
1109     clay_list_add(new_peeling, clay_array_malloc()); // empty params
1110     clay_list_add(new_peeling, peeling->data[0]);
1111   }
1112
1113   // index-set spliting
1114   ret = clay_iss(scop, beta_loop, new_peeling, &beta_max, options);
1115
1116   // we don't free ALL with clay_list_free, because there are arrays in
1117   // common with `peeling'
1118   clay_array_free(arr_dims);
1119   if (peeling->size == 1)
1120     clay_array_free(new_peeling->data[1]);
1121   free(new_peeling->data);
1122   free(new_peeling);
1123
1124   if (ret == CLAY_SUCCESS) {
1125     // see clay_split
1126     clay_beta_shift_after(scop->statement, beta_max,
1127                           beta_loop->size);
1128     clay_array_free(beta_max);
1129   }
1130
1131   if (options && options->normalize)
1132     clay_beta_normalize(scop);
1133
1134   return ret;
1135 }
1136
1137
1138 /**
1139  * clay_context function:
1140  * Add a line to the context
1141  * \param[in,out] scop
1142  * \param[in] vector        [param1, param2, ..., 1]
1143  * \param[in] options
1144  * \return                  Status
1145  */
1146 int clay_context(osl_scop_p scop, clay_array_p vector,
1147                  clay_options_p options) {
1148
1149   /* Description:
1150    * Add a new line in the context matrix.
1151    */
1152
1153   if (vector->size < 2)
1154     return CLAY_ERROR_VECTOR;
1155   if (scop->context->nb_parameters != vector->size-2)
1156     return CLAY_ERROR_VECTOR;
1157
1158   osl_relation_p context;
1159   int row;
1160   int i, j;
1161   int precision;
1162
1163   context = scop->context;
1164   precision = context->precision;
1165   row = context->nb_rows;
1166   osl_relation_insert_blank_row(context, row);
1167
1168   osl_int_set_si(precision,
1169                  &context->m[row][0],
1170                  vector->data[0]);
1171
1172   j = 1 + context->nb_output_dims + context->nb_input_dims +
1173       context->nb_local_dims;
1174   for (i = 1 ; i < vector->size ; i++) {
1175     osl_int_set_si(precision,
1176                    &context->m[row][j],
1177                    vector->data[i]);
1178     j++;
1179   }
1180
1181   return CLAY_SUCCESS;
1182 }
1183
1184
1185 static int clay_dimreorder_aux(osl_relation_list_p access,
1186                                void *args) {
1187   clay_array_p neworder = args;
1188   osl_relation_p a = access->elt;
1189
1190   if (a->nb_output_dims-1 != neworder->size) {
1191     fprintf(stderr, "[Clay] Warning: can't reorder dims on this statement: ");
1192     return CLAY_ERROR_REORDER_ARRAY_SIZE;
1193   }
1194
1195   osl_relation_p tmp = osl_relation_nclone(a, 1);
1196   int i, j;
1197
1198   for (i = 0 ; i < neworder->size ; i++) {
1199     if (neworder->data[i] < 0 ||
1200         neworder->data[i] >= a->nb_output_dims-1)
1201       return CLAY_ERROR_REORDER_OVERFLOW_VALUE;
1202
1203     if (i+2 != neworder->data[i]+2)
1204       for (j = 0 ; j < a->nb_rows ; j++)
1205         osl_int_assign(a->precision,
1206                        &tmp->m[j][i+2],
1207                        a->m[j][neworder->data[i]+2]);
1208   }
1209
1210   osl_relation_free(a);
1211   access->elt = tmp;
1212
1213   return CLAY_SUCCESS;
1214 }
1215
1216
1217 /**
1218  * clay_dimreorder function:
1219  * Reorder the dimensions of access_ident
1220  * \param[in,out] scop
1221  * \param[in] beta
1222  * \param[in] access_ident   ident of the access array
1223  * \param[in] neworder      reorder the dims
1224  * \param[in] options
1225  * \return                  Status
1226  */
1227 int clay_dimreorder(osl_scop_p scop,
1228                     clay_array_p beta,
1229                     unsigned int access_ident,
1230                     clay_array_p neworder,
1231                     clay_options_p options) {
1232
1233   /* Description
1234    * Swap the columns in the output dims (access arrays)
1235    * The first output dim is not used ( => access name)
1236    */
1237
1238   // core of the function : clay_dimreorder_aux
1239
1240   return clay_util_foreach_access(scop, beta, access_ident,
1241                                   clay_dimreorder_aux, neworder, 1);
1242 }
1243
1244
1245 static int clay_dimprivatize_aux(osl_relation_list_p access, void *args) {
1246   int depth = *((int*) args);
1247   osl_relation_p a = access->elt;
1248
1249   // check if the iterator is not used
1250   int i;
1251   for (i = 0 ; i < a->nb_rows ; i++) {
1252     if (!osl_int_zero(a->precision, a->m[i][a->nb_output_dims + depth])) {
1253       fprintf(stderr,
1254           "[Clay] Warning: can't privatize this statement\n"
1255           "                the dim (depth=%d) seems to be already used\n"
1256           "                the depth is the depth in the loops\n"
1257           "                ", depth);
1258       return CLAY_ERROR_CANT_PRIVATIZE;
1259     }
1260   }
1261
1262   a->nb_output_dims++;
1263
1264   osl_relation_insert_blank_column(a, a->nb_output_dims);
1265   osl_relation_insert_blank_row(a, a->nb_rows);
1266
1267   osl_int_set_si(a->precision,
1268                  &a->m[a->nb_rows-1][a->nb_output_dims],
1269                  -1);
1270
1271   osl_int_set_si(a->precision,
1272                  &a->m[a->nb_rows-1][a->nb_output_dims + depth],
1273                  1);
1274
1275   return CLAY_SUCCESS;
1276 }
1277
1278
1279 /**
1280  * clay_dimprivatize function:
1281  * Privatize an access
1282  * \param[in,out] scop
1283  * \param[in] beta
1284  * \param[in] access_ident   ident of the access array
1285  * \param[in] depth
1286  * \param[in] options
1287  * \return                  Status
1288  */
1289 int clay_dimprivatize(osl_scop_p scop,
1290                       clay_array_p beta,
1291                       unsigned int access_ident,
1292                       unsigned int depth,
1293                       clay_options_p options) {
1294
1295   /* Description
1296    * Add an output dim on each access which are in the beta vector
1297    */
1298
1299   if (depth <= 0)
1300     return CLAY_ERROR_DEPTH_OVERFLOW;
1301
1302   osl_statement_p stmt = clay_beta_find(scop->statement, beta);
1303   if (!stmt)
1304     return CLAY_ERROR_BETA_NOT_FOUND;
1305
1306   CLAY_BETA_CHECK_DEPTH(beta, depth, stmt);
1307
1308   // core of the function : clay_dimprivatize_aux
1309
1310   return clay_util_foreach_access(scop, beta, access_ident,
1311                                   clay_dimprivatize_aux, &depth, 1);
1312 }
1313
1314
1315 static int clay_dimcontract_aux(osl_relation_list_p access, void *args) {
1316   int depth = *((int*) args);
1317   osl_relation_p a = access->elt;
1318
1319   int row = clay_util_relation_get_line(a, depth);
1320   if (row != -1) {
1321     osl_relation_remove_row(a, row);
1322     osl_relation_remove_column(a, depth+1); // remove output dim
1323     a->nb_columns--;
1324     a->nb_output_dims--;
1325   }
1326
1327   return CLAY_SUCCESS;
1328 }
1329
1330
1331 /**
1332  * clay_dimcontract function:
1333  * Contract an access (remove a dimension)
1334  * \param[in,out] scop
1335  * \param[in] beta
1336  * \param[in] access_ident   ident of the access array
1337  * \param[in] depth
1338  * \param[in] options
1339  * \return                  Status
1340  */
1341 int clay_dimcontract(osl_scop_p scop,
1342                      clay_array_p beta,
1343                      unsigned int access_ident,
1344                      unsigned int depth,
1345                      clay_options_p options) {
1346   /* Description
1347    * Remove the line/column at the depth level
1348    */
1349
1350   if (depth <= 0)
1351     return CLAY_ERROR_DEPTH_OVERFLOW;
1352
1353   osl_statement_p stmt = clay_beta_find(scop->statement, beta);
1354   if (!stmt)
1355     return CLAY_ERROR_BETA_NOT_FOUND;
1356
1357   CLAY_BETA_CHECK_DEPTH(beta, depth, stmt);
1358
1359   // core of the function : clay_dimcontract_aux
1360
1361   return clay_util_foreach_access(scop, beta, access_ident,
1362                                   clay_dimcontract_aux, &depth, 1);
1363 }
1364
1365
1366 /**
1367  * clay_add_array function:
1368  * Add a new array in the arrays extensions.
1369  * \param[in,out] scop
1370  * \param[in] name          string name
1371  * \param[in] result        return the new id
1372  * \param[in] options
1373  * \return                  Status
1374  */
1375 int clay_add_array(osl_scop_p scop,
1376                   char *name,
1377                   int *result,
1378                   clay_options_p options) {
1379
1380   osl_arrays_p arrays = osl_generic_lookup(scop->extension, OSL_URI_ARRAYS);
1381   if (!arrays)
1382     return CLAY_ERROR_ARRAYS_EXT_EMPTY;
1383
1384   int i;
1385   int sz = arrays->nb_names;
1386
1387   if (sz == 0)
1388     return CLAY_SUCCESS;
1389
1390   for (i = 0 ; i < sz ; i++)
1391     if (strcmp(arrays->names[i], name) == 0)
1392       return CLAY_ERROR_ID_EXISTS;
1393
1394   int id = arrays->id[0];
1395
1396   for (i = 1 ; i < sz ; i++)
1397     if (arrays->id[i] > id)
1398       id = arrays->id[i];
1399
1400   arrays->nb_names++;
1401
1402   // I don't know why, there is a valgrind warning when I use CLAY_realloc
1403   arrays->id = realloc(arrays->id, sizeof(int) * (sz+1));
1404   arrays->names = realloc(arrays->names, sizeof(char*) * (sz+1));
1405
1406   id++;
1407
1408   arrays->id[sz] = id;
1409   arrays->names[sz] = strdup(name);
1410
1411   *result = id;
1412
1413   return CLAY_SUCCESS;
1414 }
1415
1416 /**
1417  * clay_get_array_id function:
1418  * Search the array name in the arrays extension
1419  * \param[in,out] scop
1420  * \param[in] name          string name
1421  * \param[in] result        return the id
1422  * \param[in] options
1423  * \return                  Status
1424  */
1425 int clay_get_array_id(osl_scop_p scop,
1426                       char *name,
1427                       int *result,
1428                       clay_options_p options) {
1429
1430   osl_arrays_p arrays = osl_generic_lookup(scop->extension, OSL_URI_ARRAYS);
1431   if (!arrays)
1432     return CLAY_ERROR_ARRAYS_EXT_EMPTY;
1433
1434   int i;
1435   int sz = arrays->nb_names;
1436   int id = -1;
1437
1438   for (i = 0 ; i < sz ; i++)
1439     if (strcmp(arrays->names[i], name) == 0) {
1440       id = arrays->id[i];
1441       break;
1442     }
1443
1444   if (id == -1)
1445     return CLAY_ERROR_ARRAY_NOT_FOUND;
1446
1447   *result = id;
1448
1449   return CLAY_SUCCESS;
1450 }
1451
1452
1453 static int clay_replace_array_aux(osl_relation_list_p access, void *args) {
1454   int new_id = *((int*) args);
1455   osl_relation_p a = access->elt;
1456
1457   // here row is != -1, because the function aux shouldn't be called
1458   int row = clay_util_relation_get_line(a, 0);
1459   osl_int_set_si(a->precision, &a->m[row][a->nb_columns-1], new_id);
1460
1461   return CLAY_SUCCESS;
1462 }
1463
1464 /**
1465  * clay_replace_array function:
1466  * Replace an ident array by another in each access
1467  * \param[in,out] scop
1468  * \param[in] last_id
1469  * \param[in] new_id
1470  * \param[in] options
1471  * \return    Status
1472  */
1473 int clay_replace_array(osl_scop_p scop,
1474                        unsigned int last_id,
1475                        unsigned int new_id,
1476                        clay_options_p options) {
1477
1478   // core of the function : clay_replace_array_aux
1479
1480   clay_array_p beta = clay_array_malloc();
1481   int ret = clay_util_foreach_access(scop, beta, last_id,
1482                                      clay_replace_array_aux, &new_id, 1);
1483   clay_array_free(beta);
1484
1485   return ret;
1486 }
1487
1488
1489 /**
1490  * clay_datacopy function:
1491  * This function will generate a loop to copy all data from the array
1492  * `array_id_original' to a new array `array_id_copy'. Use the function
1493  * add_array to insert a new array in the scop. A domain and a scattering
1494  * is needed to generate the loop to copy the data. They is a copy
1495  * from the domain/scattering of the first statement which corresponds
1496  * to the `beta_get_domain'. There is just a modification on the domain to
1497  * remove unused loops (iter >= 1 && iter <= -1 is set). The orignal id or
1498  * the copy id must be in this beta (in the list of access relation). Genarally
1499  * you will use replace_array before calling datacopy, that's why the
1500  * array_id_copy can be in the scop.  The first access relation which is found
1501  * will be used to generate an access for the original id and the copy id.
1502  * \param[in,out] scop
1503  * \param[in] array_id_copy     new variable
1504  * \param[in] array_id_original
1505  * \param[in] beta             the loop is insert after the beta
1506  * \param[in] beta_get_domain  domain/scattering are copied from this beta
1507  *                             the original or copy id must be in the list of
1508  *                             access of this beta
1509  * \param[in] options
1510  * \return                     Status
1511  */
1512 int clay_datacopy(osl_scop_p scop,
1513                   unsigned int array_id_copy,
1514                   unsigned int array_id_original,
1515                   clay_array_p beta_insert,
1516                   int insert_before,
1517                   clay_array_p beta_get_domain,
1518                   clay_options_p options) {
1519
1520   /* Description
1521    * - search the statement S beta_get_domain
1522    * - search the array array_id_original or array_id_copy in the list of
1523    *   access in the given statement
1524    * - clone the found access array
1525    * - reclone this access and put the other array id (it depends which
1526    *   id is found in the second step)
1527    * - search the beta_insert
1528    * - shift all the beta after or before beta_insert to let the place of the
1529    *   new statement
1530    * - copy domain + scattering of S in a new statement (and add this one in
1531    *   the scop)
1532    * - for each unused iterators we put iter >= 1 && iter <= -1 in the domain
1533    *   to remove the loop at the generation of code
1534    * - put the 2 access arrays in this statement
1535    * - generate body
1536    */
1537
1538   osl_relation_p scattering;
1539   int row, i, j;
1540
1541   // TODO : global vars ??
1542   osl_arrays_p arrays;
1543   osl_scatnames_p scatnames;
1544   osl_strings_p params;
1545   osl_body_p body = NULL;
1546   osl_extbody_p extbody = NULL;
1547   int is_extbody = 0;
1548   osl_generic_p gen = NULL;
1549   arrays = osl_generic_lookup(scop->extension, OSL_URI_ARRAYS);
1550   scatnames = osl_generic_lookup(scop->extension, OSL_URI_SCATNAMES);
1551   params = osl_generic_lookup(scop->parameters, OSL_URI_STRINGS);
1552
1553   if (beta_insert->size == 0)
1554     return CLAY_ERROR_BETA_EMPTY;
1555
1556   // search the beta where we have to insert the new loop
1557   osl_statement_p stmt_1 = clay_beta_find(scop->statement, beta_insert);
1558   if (!stmt_1)
1559     return CLAY_ERROR_BETA_NOT_FOUND;
1560
1561   // search the beta which is need to copy the domain and scattering
1562   osl_statement_p stmt_2 = clay_beta_find(scop->statement, beta_get_domain);
1563   if (!stmt_2)
1564     return CLAY_ERROR_BETA_NOT_FOUND;
1565
1566   // copy the domain/scattering
1567   osl_statement_p copy = osl_statement_malloc();
1568   copy->domain = osl_relation_clone(stmt_2->domain);
1569   copy->scattering = osl_relation_clone(stmt_2->scattering);
1570
1571
1572   // create an extbody and copy the original iterators
1573   osl_extbody_p ebody = osl_extbody_malloc();
1574   ebody->body = osl_body_malloc();
1575
1576   // body string (it will be regenerated)
1577   ebody->body->expression = osl_strings_encapsulate(strdup("@ = @;"));
1578
1579   // copy iterators
1580   extbody = osl_generic_lookup(stmt_2->extension, OSL_URI_EXTBODY);
1581   if (extbody) {
1582     ebody->body->iterators = osl_strings_clone(extbody->body->iterators);
1583     is_extbody = 1;
1584   }
1585   else {
1586     body = osl_generic_lookup(stmt_2->extension, OSL_URI_BODY);
1587     ebody->body->iterators = osl_strings_clone(body->iterators);
1588   }
1589
1590   // 2 access coordinates
1591   osl_extbody_add(ebody, 0, 1);
1592   osl_extbody_add(ebody, 4, 1);
1593
1594   gen = osl_generic_shell(ebody, osl_extbody_interface());
1595   osl_generic_add(&copy->extension, gen);
1596   // not creating a ebody's corresponding "body" in the new copy statement
1597
1598
1599   // search the array_id in the beta_get_domain
1600
1601   osl_relation_list_p access = stmt_2->access;
1602   osl_relation_p a;
1603   int id;
1604
1605   while (access) {
1606     a = access->elt;
1607     id = osl_relation_get_array_id(a);
1608     if (id == array_id_original || id == array_id_copy)
1609       break;
1610     access = access->next;
1611   }
1612
1613   if (!access)
1614     return CLAY_ERROR_ARRAY_NOT_FOUND_IN_THE_BETA;
1615
1616   // matrix of the copied array
1617   a = osl_relation_nclone(a, 1);
1618   a->type = OSL_TYPE_WRITE;
1619   osl_int_set_si(a->precision, &a->m[0][a->nb_columns-1], array_id_copy);
1620   copy->access = osl_relation_list_malloc();
1621   copy->access->elt = a;
1622
1623   clay_util_body_regenerate_access(ebody, a, 0, arrays, scatnames, params);
1624
1625   // matrix of the original array
1626   a = osl_relation_nclone(a, 1);
1627   a->type = OSL_TYPE_READ;
1628   copy->access->next = osl_relation_list_malloc();
1629   copy->access->next->elt = a;
1630   copy->access->next->next = NULL;
1631   osl_int_set_si(a->precision, &a->m[0][a->nb_columns-1], array_id_original);
1632
1633   clay_util_body_regenerate_access(ebody, a, 1, arrays, scatnames, params);
1634
1635
1636   // remove the unused dim in the scatterin (modify the domain of the loop)
1637   for (j = 0 ; j < a->nb_input_dims ; j++) {
1638     int found = 0;
1639
1640     // search an unused input dims (if there is only 0 on the row)
1641     for (i = 0 ; i < a->nb_rows ; i++) {
1642       if (!osl_int_zero(a->precision, a->m[i][1 + a->nb_output_dims + j])) {
1643         found = 1;
1644         break;
1645       }
1646     }
1647
1648     // unused
1649     if (!found) {
1650       int k, t;
1651       osl_relation_p domain = copy->domain;
1652       for (i = 0 ; i < domain->nb_rows ; i++) {
1653         t = osl_int_get_si(domain->precision, domain->m[i][1 + j]);
1654
1655         if (t != 0) {
1656           for (k = 1 ; k < domain->nb_columns-1 ; k++)
1657             if (k != 1+j)
1658               osl_int_set_si(domain->precision, &domain->m[i][k], 0);
1659
1660           // set iter <= -1 && iter >= 1  ==> no solutions, so no loop !
1661           if (t > 0)
1662             osl_int_set_si(domain->precision, &domain->m[i][k], -1);
1663           else
1664             osl_int_set_si(domain->precision, &domain->m[i][k], 1);
1665         }
1666       }
1667     }
1668   }
1669
1670
1671   // let the place to the new loop
1672
1673   scattering = copy->scattering;
1674   if (insert_before) {
1675     clay_beta_shift_before(scop->statement, beta_insert, 1);
1676
1677     // set the beta : it's the beta[0]
1678     row = clay_util_relation_get_line(scattering, 0);
1679     osl_int_set_si(scattering->precision,
1680                    &scattering->m[row][scattering->nb_columns-1],
1681                    beta_insert->data[0]);
1682   } else {
1683     clay_beta_shift_after(scop->statement, beta_insert, 1);
1684
1685     // set the beta : it's the beta[0] + 1
1686     row = clay_util_relation_get_line(scattering, 0);
1687     osl_int_set_si(scattering->precision,
1688                    &scattering->m[row][scattering->nb_columns-1],
1689                    beta_insert->data[0]+1);
1690   }
1691
1692   copy->next = scop->statement;
1693   scop->statement = copy;
1694
1695   if (options && options->normalize)
1696     clay_beta_normalize(scop);
1697
1698   return CLAY_SUCCESS;
1699 }
1700
1701
1702 /**
1703  * clay_block function:
1704  * \param[in,out] scop
1705  * \param[in] beta_stmt1
1706  * \param[in] beta_stmt2
1707  * \param[in] options
1708  * \return                     Status
1709  */
1710 int clay_block(osl_scop_p scop,
1711                clay_array_p beta_stmt1,
1712                clay_array_p beta_stmt2,
1713                clay_options_p options) {
1714
1715   /* Description
1716    * concat '{' + body(stmt_1) + body(stmt_2) + '}'
1717    * update extbody if needed
1718    * concat access(stmt_1) + access(stmt_2)
1719    * remove stmt_2
1720    */
1721
1722   if (beta_stmt1->size != beta_stmt2->size)
1723     return CLAY_ERROR_BETAS_NOT_SAME_DIMS;
1724
1725   // search statements and check betas
1726
1727   osl_statement_p stmt_1 = clay_beta_find(scop->statement, beta_stmt1);
1728   if (!stmt_1)
1729     return CLAY_ERROR_BETA_NOT_FOUND;
1730
1731   osl_statement_p stmt_2 = clay_beta_find(scop->statement, beta_stmt2);
1732   if (!stmt_2)
1733     return CLAY_ERROR_BETA_NOT_FOUND;
1734
1735   CLAY_BETA_IS_STMT(beta_stmt1, stmt_1);
1736   CLAY_BETA_IS_STMT(beta_stmt2, stmt_2);
1737
1738   if (!osl_relation_equal(stmt_1->domain, stmt_2->domain))
1739     return CLAY_ERROR_BETAS_NOT_SAME_DOMAIN;
1740
1741   int i;
1742   int is_extbody_1 = 0;
1743   int is_extbody_2 = 0;
1744
1745   char **expr_left;
1746   char **expr_right;
1747   char *new_expr;
1748
1749   osl_extbody_p ebody_1, ebody_2;
1750   osl_body_p body_1, body_2;
1751   osl_generic_p gen = NULL;
1752
1753   // get the body string
1754
1755   ebody_1 = osl_generic_lookup(stmt_1->extension, OSL_URI_EXTBODY);
1756   if (ebody_1) {
1757     is_extbody_1 = 1;
1758   }
1759   else {
1760     body_1 = osl_generic_lookup(stmt_1->extension, OSL_URI_BODY);
1761   }
1762
1763   ebody_2 = osl_generic_lookup(stmt_2->extension, OSL_URI_EXTBODY);
1764   if (ebody_2) {
1765     is_extbody_2 = 1;
1766   }
1767   else {
1768     body_2 = osl_generic_lookup(stmt_2->extension, OSL_URI_BODY);
1769   }
1770
1771   if (is_extbody_1 != is_extbody_2)
1772     return CLAY_ERROR_ONE_HAS_EXTBODY;
1773
1774
1775   expr_left = is_extbody_1
1776     ? ebody_1->body->expression->string
1777     : body_1->expression->string;
1778
1779   expr_right = is_extbody_2
1780     ? ebody_2->body->expression->string
1781     : body_2->expression->string;
1782
1783   // update extbody
1784   if (is_extbody_1) {
1785
1786     // shift for the '{'
1787     for (i = 0 ; i < ebody_1->nb_access ; i++) {
1788       if (ebody_1->start[i] != -1)
1789         ebody_1->start[i]++;
1790     }
1791
1792     int offset = 1 + strlen(expr_left[0]);
1793
1794     // shift the right part
1795     for (i = 0 ; i < ebody_2->nb_access ; i++) {
1796       if (ebody_2->start[i] != -1)
1797         ebody_2->start[i] += offset;
1798
1799       // concat with the extbody 2
1800       osl_extbody_add(ebody_1, ebody_2->start[i], ebody_2->length[i]);
1801     }
1802
1803   }
1804
1805   // generate the new body string
1806   new_expr = (char*) malloc(strlen(expr_left[0]) + strlen(expr_right[0]) + 3);
1807   strcpy(new_expr, "{");
1808   strcat(new_expr, expr_left[0]);
1809   strcat(new_expr, expr_right[0]);
1810   strcat(new_expr, "}");
1811
1812   free(expr_left[0]);
1813   expr_left[0] = new_expr;
1814
1815   // concat all the access array
1816   osl_relation_list_p access = stmt_1->access;
1817   if (access) {
1818     while (access->next)
1819       access = access->next;
1820   }
1821   access->next = stmt_2->access;
1822   stmt_2->access = NULL;
1823
1824   // synchronize extbody with body for stmt_1
1825   if (is_extbody_1) {
1826     body_1 = osl_generic_lookup(stmt_1->extension, OSL_URI_BODY);
1827     if (body_1) {
1828       osl_generic_remove(&stmt_1->extension, OSL_URI_BODY);
1829       body_1 = osl_body_clone(ebody_1->body);
1830       gen = osl_generic_shell(body_1, osl_body_interface());
1831       osl_generic_add(&stmt_1->extension, gen);
1832     }
1833   }
1834
1835   // search the stmt 2 and remove it in the chain list
1836   osl_statement_p s = scop->statement;
1837   if (s) {
1838     while (s->next) {
1839       if (s->next == stmt_2) {
1840         s->next = s->next->next;
1841         stmt_2->next = NULL; // prevent free from removing chained statements
1842         osl_statement_free(stmt_2);
1843         break;
1844       }
1845       s = s->next;
1846     }
1847   }
1848
1849   if (options && options->normalize)
1850     clay_beta_normalize(scop);
1851
1852   return CLAY_SUCCESS;
1853 }