source/util.c

   1
   2    /*--------------------------------------------------------------------+
   3     |                              Clay                                  |
   4     |--------------------------------------------------------------------|
   5     |                             util.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 <stdlib.h>
  37 #include <string.h>
  38 #include <clay/array.h>
  39 #include <clay/beta.h>
  40 #include <clay/macros.h>
  41 #include <clay/util.h>
  42 #include <clay/errors.h>
  43
  44 #include <osl/statement.h>
  45 #include <osl/body.h>
  46 #include <osl/extensions/extbody.h>
  47 #include <osl/extensions/scatnames.h>
  48 #include <osl/scop.h>
  49 #include <osl/generic.h>
  50 #include <osl/util.h>
  51 #include <osl/relation.h>
  52 #include <osl/relation_list.h>
  53 #include <osl/macros.h>
  54
  55 /**
  56  * clay_util_statement_insert_inequation function:
  57  * Insert a new inequation at the end of the scattering
  58  * \param[in,out] statement
  59  * \param[in] inequ              [iter1, iter2, ..., param1, param2, ..., const]
  60  * \param[in] nb_input_dims      Nb input dims in the array
  61  * \param[in] nb_params          Nb params in the array
  62  */
  63 /*void clay_util_statement_insert_inequation(osl_statement_p statement,
  64             clay_array_p inequ, int nb_input_dims, int nb_params) {
  65
  66   osl_relation_p scattering = statement->scattering;
  67   int row = scattering->nb_rows;
  68   int i, j;
  69   int precision = scattering->precision;
  70
  71   // insert the inequation spliting (local dims are not in the inequation)
  72   // (at the end)
  73   osl_relation_insert_blank_row(scattering, row);
  74   osl_int_set_si(precision, scattering->m[row], 0, 1); // type inequation
  75
  76   // affects input_dims
  77   i = scattering->nb_output_dims+1;
  78   for (j = 0 ; j < nb_input_dims ; j++) {
  79     osl_int_set_si(precision,
  80                    scattering->m[row], i,
  81                    inequ->data[j]);
  82     i++;
  83   }
  84   // affects parameters
  85   i = 1 + scattering->nb_output_dims + scattering->nb_input_dims +
  86       scattering->nb_local_dims;
  87   for (; j < nb_params + nb_input_dims ; j++) {
  88     osl_int_set_si(precision,
  89                    scattering->m[row], i,
  90                    inequ->data[j]);
  91     i++;
  92   }
  93   // set the constant
  94   osl_int_set_si(precision,
  95                  scattering->m[row], scattering->nb_columns-1,
  96                  inequ->data[inequ->size-1]);
  97 }
  98 */
  99
 100
 101
 102 /**
 103  * clay_util_array_output_dims_pad_zero function:
 104  * Pad zeros for alpha columns
 105  * For example if we have [i, j], the result will be [0, i, 0, j, 0]
 106  * \param[in,out] array
 107  */
 108 void clay_util_array_output_dims_pad_zero(clay_array_p a) {
 109   int i;
 110   int end = a->size*2+1;
 111   int old_size = a->size;
 112
 113   for (i = old_size ; i < end ; i++)
 114     clay_array_add(a, 0);
 115
 116   for (i = old_size - 1 ; i >= 0 ; i--) {
 117     a->data[i*2+1] = a->data[i];
 118     a->data[i] = 0;
 119   }
 120 }
 121
 122 // update the provided part of the beta and leave everything else untouched
 123 void clay_util_scattering_update_beta(osl_relation_p scattering,
 124                                       clay_array_p beta) {
 125   int i, row;
 126   if (!scattering || !beta || beta->size == 0) {
 127     return;
 128   }
 129
 130   for (i = 0; i < OSL_min(beta->size, scattering->nb_output_dims / 2 + 1); i++) {
 131     row = clay_util_relation_get_line(scattering, i * 2);
 132     osl_int_set_si(scattering->precision,
 133                    &scattering->m[row][scattering->nb_columns - 1],
 134                    beta->data[i]);
 135   }
 136 }
 137
 138 // update the provided part of the beta for every part of the scattering relation union
 139 // that matches the given old beta
 140 void clay_util_statement_replace_beta(osl_statement_p statement,
 141                                       clay_array_p old_beta,
 142                                       clay_array_p beta) {
 143   osl_relation_p scattering = statement->scattering;
 144   while (scattering != NULL) {
 145     if (clay_beta_check_relation(scattering, old_beta)) {
 146       clay_util_scattering_update_beta(scattering, beta);
 147     }
 148     scattering = scattering->next;
 149   }
 150 }
 151
 152 void clay_util_relation_insert_inequation(osl_relation_p relation,
 153                                           clay_list_p inequ) {
 154   clay_array_p dims = NULL,
 155                params = NULL,
 156                consts = NULL;
 157   int row = relation->nb_rows;
 158   int precision = relation->precision;
 159   int i, j;
 160
 161   // Insert a blank row at the end and fill it in.
 162   osl_relation_insert_blank_row(relation, row);
 163   osl_int_set_si(precision, &relation->m[row][0], 1); // inequality
 164
 165   if (inequ->size > 3) {
 166     CLAY_error("list with more than 3 arrays not supported");
 167   } else if (inequ->size == 3) {
 168     dims   = inequ->data[0];
 169     params = inequ->data[1];
 170     consts = inequ->data[2];
 171   } else if (inequ->size == 2) {
 172     params = inequ->data[0];
 173     consts = inequ->data[1];
 174   } else {
 175     consts = inequ->data[0];
 176   }
 177
 178   if (consts->size != 1) {
 179     CLAY_error("constant must be a single value");
 180   }
 181
 182   // Decomposition switch, fallthoroughs are _intentional_.
 183   switch (inequ->size) {
 184   case 3:
 185     for (j = 0, i = 1; j < dims->size; j++, i++) {
 186       osl_int_set_si(precision,
 187                      &relation->m[row][i],
 188                      dims->data[j]);
 189     }
 190     // intentional fall through
 191   case 2:
 192     for (j = 0, i = 1 + relation->nb_output_dims +
 193                     relation->nb_input_dims + relation->nb_local_dims;
 194         j < params->size;
 195         j++, i++) {
 196       osl_int_set_si(precision,
 197                      &relation->m[row][i],
 198                      params->data[j]);
 199     }
 200     // intentional fall through
 201   case 1:
 202     osl_int_set_si(precision,
 203                    &relation->m[row][relation->nb_columns-1],
 204                    consts->data[0]);
 205     break;
 206   default:
 207     CLAY_error("list with more than 3 arrays not supported");
 208     break;
 209   }
 210 }
 211
 212 /**
 213  * clay_util_statement_set_inequation function:
 214  * Insert a new inequation at the end of the scattering
 215  * The list must have less or equal than 3 arrays
 216  * Warning: here the output dims are complete
 217  *          example: if the output dims are : 0 i 0 j 0, you have
 218  *                   to give all these numbers
 219  * \param[in,out] statement
 220  * \param[in] inequ              {(([output, ...],) [param, ..],) [const]}
 221  */
 222 void clay_util_statement_set_inequation(
 223                         osl_statement_p statement,
 224                         clay_list_p inequ) {
 225
 226   osl_relation_p scattering = statement->scattering;
 227   clay_array_p arr_dims = NULL, arr_params = NULL, arr_const = NULL;
 228   int row = scattering->nb_rows;
 229   int i, j;
 230   int precision = scattering->precision;
 231
 232   // insert the inequation spliting (local dims are not in the inequation)
 233   // (at the end)
 234   osl_relation_insert_blank_row(scattering, row);
 235   osl_int_set_si(precision, &scattering->m[row][0], 1); // type inequation
 236
 237   if (inequ->size > 3) {
 238     CLAY_error("list with more than 3 arrays not supported");
 239   } else if (inequ->size == 3) {
 240     arr_dims   = inequ->data[0];
 241     arr_params = inequ->data[1];
 242     arr_const  = inequ->data[2];
 243   } else if (inequ->size == 2) {
 244     arr_params = inequ->data[0];
 245     arr_const  = inequ->data[1];
 246   } else {
 247     arr_const  = inequ->data[0];
 248   }
 249
 250   // affects output dims
 251   if (inequ->size == 3) {
 252     i = 1;
 253     for (j = 0 ; j < arr_dims->size ; j++) {
 254       osl_int_set_si(precision,
 255                      &scattering->m[row][i],
 256                      arr_dims->data[j]);
 257       i++;
 258     }
 259   }
 260
 261   // affects parameters
 262   if (inequ->size >= 2) {
 263     i = 1 + scattering->nb_output_dims + scattering->nb_input_dims +
 264         scattering->nb_local_dims;
 265     for (j = 0; j < arr_params->size ; j++) {
 266       osl_int_set_si(precision,
 267                      &scattering->m[row][i],
 268                      arr_params->data[j]);
 269       i++;
 270     }
 271   }
 272
 273   // set the constant
 274   if (inequ->size >= 1 && arr_const->size == 1) {
 275     osl_int_set_si(precision,
 276                    &scattering->m[row][scattering->nb_columns-1],
 277                    arr_const->data[0]);
 278   }
 279 }
 280
 281
 282 /**
 283  * clay_util_statement_set_vector function:
 284  * Set the equation on each line where the column of the output dim is
 285  * different of zero
 286  * \param[in,out] statement
 287  * \param[in] vector           {(([output, ...],) [param, ..],) [const]}
 288  * \param[in] column           column on the output dim
 289  */
 290 void clay_util_relation_set_vector(
 291                         osl_relation_p scattering,
 292                         clay_list_p vector, int column) {
 293
 294   clay_array_p arr_dims = NULL, arr_params = NULL, arr_const = NULL;
 295   int i, j, k;
 296   int precision = scattering->precision;
 297   osl_int_p tmp;
 298
 299   tmp = osl_int_malloc(precision);
 300
 301   if (vector->size > 3) {
 302     CLAY_error("list with more than 3 arrays not supported");
 303   } else if (vector->size == 3) {
 304     arr_dims   = vector->data[0];
 305     arr_params = vector->data[1];
 306     arr_const  = vector->data[2];
 307   } else if (vector->size == 2) {
 308     arr_params = vector->data[0];
 309     arr_const  = vector->data[1];
 310   } else {
 311     arr_const  = vector->data[0];
 312   }
 313
 314   // for each line where there is a number different from zero on the
 315   // column
 316   for (k = 0 ; k < scattering->nb_rows ; k++) {
 317     if (!osl_int_zero(precision, scattering->m[k][1+column])) {
 318
 319       // scattering = coeff_outputdim * shifting
 320
 321       // affect output dims
 322       if (vector->size >= 3) {
 323         i = 1;
 324         for (j = 0 ; j < arr_dims->size ; j++) {
 325           osl_int_mul_si(precision,
 326                          &scattering->m[k][i],
 327                          scattering->m[k][1+column],
 328                          arr_dims->data[j]);
 329           i++;
 330         }
 331       }
 332
 333       // here we add we the last value
 334       // scattering += coeff_outputdim * shifting
 335
 336       // affects parameters
 337       if (vector->size >= 2) {
 338         i = 1 + scattering->nb_output_dims + scattering->nb_input_dims +
 339             scattering->nb_local_dims;
 340         for (j = 0 ; j < arr_params->size ; j++) {
 341           osl_int_mul_si(precision,
 342                          tmp,
 343                          scattering->m[k][1+column],
 344                          arr_params->data[j]);
 345           osl_int_add(precision,
 346                       &scattering->m[k][i],
 347                       scattering->m[k][i],
 348                       *tmp);
 349           i++;
 350         }
 351       }
 352
 353       // set the constant
 354       if (vector->size >= 1 && arr_const->size == 1) {
 355         osl_int_mul_si(precision,
 356                        tmp,
 357                        scattering->m[k][1+column],
 358                        arr_const->data[0]);
 359         osl_int_add(precision,
 360                     &scattering->m[k][scattering->nb_columns-1],
 361                     scattering->m[k][scattering->nb_columns-1],
 362                     *tmp);
 363       }
 364     }
 365   }
 366
 367   osl_int_free(precision, tmp);
 368 }
 369
 370
 371 /**
 372  * clay_util_relation_negate_row function:
 373  * Negate the line at `row' (doesn't affect the e/i column)
 374  * \param[in,out] statement
 375  * \param[in] row                row to negate
 376  */
 377 void clay_util_relation_negate_row(osl_relation_p r, int row) {
 378   int i;
 379   int precision = r->precision;
 380   for (i = 1 ; i < r->nb_columns ; i++) {
 381     osl_int_oppose(precision,
 382                    &r->m[row][i],
 383                    r->m[row][i]);
 384   }
 385   osl_int_decrement(precision,
 386                     &r->m[row][r->nb_columns-1],
 387                     r->m[row][r->nb_columns-1]);
 388 }
 389
 390
 391 /**
 392  * clay_util_statement_insert function:
 393  * Insert `newstatement' before `statement', and set his beta value
 394  * \param[in,out] statement
 395  * \param[in,out] newstatement
 396  * \param[in] column             column on the output dim (where we want to split)
 397  *                               this is a `alpha column' of the 2*d+1
 398  * \param[in] order              new beta value
 399  * \return                       return statement->next (so newtstatement)
 400  */
 401 osl_statement_p clay_util_statement_insert(osl_statement_p statement,
 402                                            osl_statement_p newstatement,
 403                                            int column,
 404                                            int order) {
 405   osl_relation_p scattering = statement->scattering;
 406
 407   // the current statement is after the new statement
 408   int row = clay_util_relation_get_line(scattering, column);
 409   osl_int_set_si(scattering->precision,
 410                  &scattering->m[row][scattering->nb_columns-1],
 411                  order);
 412
 413   // the order is not important in the statements list
 414   newstatement->next = statement->next;
 415   statement->next = newstatement;
 416   statement = statement->next;
 417
 418   return statement;
 419 }
 420
 421
 422 /**
 423  * clay_util_string_replace function:
 424  * Search and replace a string with another string , in a string
 425  * Minor modifications from :
 426  * http://www.binarytides.com/blog/str_replace-for-c/
 427  * \param[in] search
 428  * \param[in] replace
 429  * \param[in] subject
 430  */
 431 char* clay_util_string_replace(char *search, char *replace, char *string) {
 432         char  *ptr = NULL , *old = NULL , *new_string = NULL ;
 433         int count = 0 , search_size;
 434
 435         search_size = strlen(search);
 436
 437         // Count how many occurences
 438         for(ptr = strstr(string , search) ; ptr != NULL ;
 439             ptr = strstr(ptr + search_size , search)) {
 440                 count++;
 441         }
 442
 443         // Final size
 444         count = (strlen(replace) - search_size)*count + strlen(string) + 1;
 445         new_string = calloc(count, 1);
 446
 447         // The start position
 448         old = string;
 449
 450         for(ptr = strstr(string, search) ; ptr != NULL ;
 451             ptr = strstr(ptr + search_size, search)) {
 452                 // move ahead and copy some text from original subject , from a
 453                 // certain position
 454                 strncpy(new_string + strlen(new_string), old , ptr - old);
 455
 456                 // move ahead and copy the replacement text
 457                 strcpy(new_string + strlen(new_string) , replace);
 458
 459                 // The new start position after this search match
 460                 old = ptr + search_size;
 461         }
 462
 463         // Copy the part after the last search match
 464         strcpy(new_string + strlen(new_string) , old);
 465
 466         return new_string;
 467 }
 468
 469
 470 /**
 471  * clay_util_scatnames_exists_iterator_iterator function:
 472  * Return true if the iterator name is already in the scattering.
 473  * \param[in] scattering
 474  * \return
 475  */
 476 bool clay_util_scatnames_exists(osl_scatnames_p scatnames, char *iter) {
 477   osl_strings_p names = scatnames->names;
 478   if (names == NULL || names->string[0] == NULL)
 479     return 0;
 480
 481   char **ptr = names->string;
 482
 483   while (*ptr != NULL) {
 484     if (strcmp(*ptr, iter) == 0)
 485       return 1;
 486     ptr++;
 487   }
 488
 489   return 0;
 490 }
 491
 492
 493 /**
 494  * clay_util_statement_find_iterator function:
 495  * Return the index if iter is found in the original iterators list.
 496  * \param[in] scop
 497  * \param[in] iter       name of the original iterator we want to search
 498  * \return
 499  */
 500 int clay_util_statement_find_iterator(osl_statement_p statement, char *iter) {
 501   osl_body_p body;
 502   osl_extbody_p extbody = NULL;
 503
 504   extbody = osl_generic_lookup(statement->extension, OSL_URI_EXTBODY);
 505   if (extbody)
 506     body = extbody->body;
 507   else
 508     body = osl_generic_lookup(statement->extension, OSL_URI_BODY);
 509
 510   char **ptr = body->iterators->string;
 511   int i = 0;
 512
 513   while (*ptr != NULL) {
 514     if (strcmp(*ptr, iter) == 0)
 515       return i;
 516     ptr++;
 517     i++;
 518   }
 519
 520   return -1;
 521 }
 522
 523
 524 /**
 525  * clay_util_scop_export_body function:
 526  * Convert each extbody to a body structure
 527  * \param[in] scop
 528  */
 529 void clay_util_scop_export_body(osl_scop_p scop) {
 530   if (scop == NULL)
 531     return;
 532
 533   osl_statement_p stmt = scop->statement;
 534   osl_extbody_p ebody = NULL;
 535   osl_body_p body = NULL;
 536   osl_generic_p gen = NULL;
 537
 538   while (stmt) {
 539     ebody = osl_generic_lookup(stmt->extension, OSL_URI_EXTBODY);
 540     if (ebody!=NULL) {
 541
 542       body = osl_generic_lookup(stmt->extension, OSL_URI_BODY);
 543       if (body) {
 544         osl_generic_remove(&stmt->extension, OSL_URI_BODY);
 545       }
 546       body = osl_body_clone(ebody->body);
 547       gen = osl_generic_shell(body, osl_body_interface());
 548       osl_generic_add(&stmt->extension, gen);
 549       osl_generic_remove(&stmt->extension, OSL_URI_EXTBODY);
 550       ebody=NULL;
 551       body=NULL;
 552     }
 553     stmt = stmt->next;
 554   }
 555 }
 556
 557
 558 void static clay_util_name_sprint(char **dst, int *hwm,
 559                                   int *print_plus, int val, char *name) {
 560   if (*print_plus)
 561     osl_util_safe_strcat(dst, " + ", hwm);
 562   else
 563     *print_plus = 1;
 564
 565   char buffer[32];
 566
 567   if (name == NULL) {
 568     snprintf(buffer, 32, "%d", val);
 569     osl_util_safe_strcat(dst, buffer, hwm);
 570   } else {
 571     if (val == 1) {
 572       osl_util_safe_strcat(dst, name, hwm);
 573     } else if (val == -1) {
 574       osl_util_safe_strcat(dst, "-", hwm);
 575       osl_util_safe_strcat(dst, name, hwm);
 576     } else {
 577       snprintf(buffer, 32, "%d*", val);
 578       osl_util_safe_strcat(dst, buffer, hwm);
 579       osl_util_safe_strcat(dst, name, hwm);
 580     }
 581   }
 582 }
 583
 584
 585 /**
 586  * clay_util_body_regenerate_access function:
 587  * Read the access array and re-generate the code in the body
 588  * \param[in] ebody     An extbody structure
 589  * \param[in] access    The relation to regenerate the code
 590  * \param[in] index     nth access (needed to access to the array start and
 591  *                      length of the extbody structure)
 592  */
 593 void clay_util_body_regenerate_access(osl_extbody_p ebody,
 594                                       osl_relation_p access,
 595                                       int index,
 596                                       osl_arrays_p arrays,
 597                                       osl_scatnames_p scatnames,
 598                                       osl_strings_p params) {
 599
 600   if (!arrays || !scatnames || !params || access->nb_output_dims == 0 ||
 601       index >= ebody->nb_access)
 602     return;
 603
 604   const int precision = access->precision;
 605   int i, j, k, row, val, print_plus;
 606
 607   // check if there are no inequ
 608   for (i = 0 ; i < access->nb_rows ; i++) {
 609     if (!osl_int_zero(precision, access->m[i][0]))
 610       CLAY_error("I don't know how to regenerate access with inequalities");
 611   }
 612
 613   // check identity matrix in output dims
 614   int n;
 615   for (j = 0 ; j < access->nb_output_dims ; j++) {
 616     n = 0;
 617     for (i = 0 ; i < access->nb_rows ; i++)
 618       if (!osl_int_zero(precision, access->m[i][j+1])) {
 619         if (n >= 1)
 620           CLAY_error("I don't know how to regenerate access with "
 621                      "dependences in output dims");
 622         n++;
 623       }
 624   }
 625
 626   char *body = ebody->body->expression->string[0];
 627   int body_len = strlen(body);
 628   int start = ebody->start[index];
 629   int len = ebody->length[index];
 630   int is_zero; // if the line contains only zeros
 631
 632   if (start >= body_len || start + len >= body_len || (start == -1 && len == -1))
 633     return;
 634
 635   char *new_body;
 636   char end_body[OSL_MAX_STRING];
 637   int hwm = OSL_MAX_STRING;
 638
 639   CLAY_malloc(new_body, char *, OSL_MAX_STRING * sizeof(char));
 640
 641   // copy the beginning of the body
 642   if (start+1 >= OSL_MAX_STRING)
 643     CLAY_error("memcpy: please recompile osl with a higher OSL_MAX_STRING");
 644   memcpy(new_body, body, start);
 645   new_body[start] = '\0';
 646
 647   // save the end in a buffer
 648   int sz = body_len - start - len;
 649   if (sz + 1 >= OSL_MAX_STRING)
 650     CLAY_error("memcpy: please recompile osl with a higher OSL_MAX_STRING");
 651   memcpy(end_body, body + start + len, sz);
 652   end_body[sz] = '\0';
 653
 654
 655   // copy access name string
 656   val = osl_relation_get_array_id(access);
 657   val = clay_util_arrays_search(arrays, val); // get the index in th array
 658   osl_util_safe_strcat(&new_body, arrays->names[val], &hwm);
 659
 660
 661   // generate each dims
 662   for (i = 1 ; i < access->nb_output_dims ; i++) {
 663     row = clay_util_relation_get_line(access, i);
 664     if (row == -1)
 665       continue;
 666
 667     osl_util_safe_strcat(&new_body, "[", &hwm);
 668
 669     is_zero = 1;
 670     print_plus = 0;
 671     k = 1 + access->nb_output_dims;
 672
 673     // iterators
 674     for (j = 0 ; j < access->nb_input_dims ; j++, k++) {
 675       val = osl_int_get_si(precision, access->m[row][k]);
 676       if (val != 0) {
 677         clay_util_name_sprint(&new_body,
 678                               &hwm,
 679                               &print_plus,
 680                               val,
 681                               scatnames->names->string[j*2+1]);
 682         is_zero = 0;
 683       }
 684     }
 685
 686     // params
 687     for (j = 0 ; j < access->nb_parameters ; j++, k++) {
 688       val = osl_int_get_si(precision, access->m[row][k]);
 689       if (val != 0) {
 690         clay_util_name_sprint(&new_body,
 691                               &hwm,
 692                               &print_plus,
 693                               val,
 694                               params->string[j]);
 695         is_zero = 0;
 696       }
 697     }
 698
 699     // const
 700     val = osl_int_get_si(precision, access->m[row][k]);
 701     if (val != 0 || is_zero)
 702       clay_util_name_sprint(&new_body,
 703                             &hwm,
 704                             &print_plus,
 705                             val,
 706                             NULL);
 707
 708     osl_util_safe_strcat(&new_body, "]", &hwm);
 709   }
 710
 711   // length of the generated access
 712   ebody->length[index] = strlen(new_body) - start;
 713
 714   // concat the end
 715   osl_util_safe_strcat(&new_body, end_body, &hwm);
 716
 717   // update ebody
 718   free(ebody->body->expression->string[0]);
 719   ebody->body->expression->string[0] = new_body;
 720
 721   // shift the start
 722   int diff = ebody->length[index] - len;
 723   for (i = index+1 ; i < ebody->nb_access ; i++)
 724     if (ebody->start[i] != -1)
 725       ebody->start[i] += diff;
 726 }
 727
 728
 729 /**
 730  * clay_util_arrays_search function:
 731  * Search the string which corresponds to id
 732  * arrays is an extension of osl
 733  * \param[in] arrays    An arrays osl structure
 734  * \param[in] id        The id to search
 735  * \return              Return the index in the arrays
 736  */
 737 int clay_util_arrays_search(osl_arrays_p arrays, unsigned int id) {
 738   int i;
 739   for (i = 0 ; i < arrays->nb_names ; i++) {
 740     if (arrays->id[i] == id)
 741       return i;
 742   }
 743   return -1;
 744 }
 745
 746
 747 /**
 748  * clay_util_foreach_access function:
 749  * Execute func on each access which corresponds to access_name
 750  * \param[in,out] scop
 751  * \param[in] beta
 752  * \param[in] access_name      The id to search
 753  * \param[in] func             The function to execute for each access
 754  *                             The function takes an osl_relation_list_p in
 755  *                             parameter (the elt can be modified) and must
 756  *                             return a define error or CLAY_SUCCESS
 757  * \param[in] args             args of `func'
 758  * \param[in] regenerate_body  If 1: after each call to func,
 759  *                             clay_util_body_regenerate_access is also called
 760  * \return                     Return a define error or CLAY_SUCCESS
 761  */
 762 int clay_util_foreach_access(osl_scop_p scop,
 763                              clay_array_p beta,
 764                              unsigned int access_name,
 765                              int (*func)(osl_relation_list_p, void*),
 766                              void *args,
 767                              int regenerate_body) {
 768
 769   osl_statement_p stmt = scop->statement;
 770   osl_relation_list_p access;
 771   osl_relation_p a;
 772   osl_extbody_p ebody = NULL;
 773   osl_body_p body = NULL;
 774   osl_generic_p gen= NULL;
 775   int count_access;
 776   int found = 0;
 777   int ret;
 778
 779   // TODO : global vars ?
 780   osl_arrays_p arrays;
 781   osl_scatnames_p scatnames;
 782   osl_strings_p params;
 783   arrays = osl_generic_lookup(scop->extension, OSL_URI_ARRAYS);
 784   scatnames = osl_generic_lookup(scop->extension, OSL_URI_SCATNAMES);
 785   params = osl_generic_lookup(scop->parameters, OSL_URI_STRINGS);
 786
 787   if (!arrays || !scatnames || !params)
 788     CLAY_warning("no arrays or scatnames extension");
 789
 790   stmt = clay_beta_find(scop->statement, beta);
 791   if (!stmt)
 792     return CLAY_ERROR_BETA_NOT_FOUND;
 793
 794   // for each access in the beta, we search the access_name
 795   while (stmt != NULL) {
 796     if (clay_beta_check(stmt, beta)) {
 797       access = stmt->access;
 798       count_access = 0;
 799
 800       while (access) {
 801         a = access->elt;
 802
 803         if (osl_relation_get_array_id(a) == access_name) {
 804           found = 1;
 805
 806           ebody = osl_generic_lookup(stmt->extension, OSL_URI_EXTBODY);
 807           if (ebody==NULL) {
 808             CLAY_error("extbody uri not found on this statement");
 809             fprintf(stderr, "%s\n",
 810               ebody->body->expression->string[0]);
 811           }
 812
 813           // call the function
 814           ret = (*func)(access, args);
 815           if (ret != CLAY_SUCCESS) {
 816             fprintf(stderr, "%s\n",
 817               ebody->body->expression->string[0]);
 818             return ret;
 819           }
 820
 821           // re-generate the body
 822           if (regenerate_body) {
 823             clay_util_body_regenerate_access(
 824                 ebody,
 825                 access->elt,
 826                 count_access,
 827                 arrays,
 828                 scatnames,
 829                 params);
 830
 831
 832             //synchronize extbody with body
 833             body = osl_generic_lookup(stmt->extension, OSL_URI_BODY);
 834             if (body) {
 835               osl_generic_remove(&stmt->extension, OSL_URI_BODY);
 836               body = osl_body_clone(ebody->body);
 837               gen = osl_generic_shell(body, osl_body_interface());
 838               osl_generic_add(&stmt->extension, gen);
 839             }
 840           }
 841         }
 842
 843         ebody = NULL;
 844         body  = NULL;
 845         access = access->next;
 846         count_access++;
 847       }
 848     }
 849     stmt = stmt->next;
 850   }
 851
 852   if (!found)
 853    fprintf(stderr,"[Clay] Warning: access number %d not found\n", access_name);
 854
 855   return CLAY_SUCCESS;
 856 }
 857
 858
 859 /**
 860  * clay_util_relation_get_line function:
 861  * Because the lines in the scattering matrix may have not ordered, we have to
 862  * search the corresponding line. It returns the first line where the value is
 863  * different from zero in the `column'. `column' is between 0 and
 864  * nb_output_dims-1
 865  * \param[in] relation
 866  * \param[in] column        Line to search
 867  * \return                  Return the real line
 868  */
 869 int clay_util_relation_get_line(osl_relation_p relation, int column) {
 870   if (column < 0 || column > relation->nb_output_dims)
 871     return -1;
 872   int i;
 873   int precision = relation->precision;
 874   for (i = 0 ; i < relation->nb_rows ; i++) {
 875     if (!osl_int_zero(precision, relation->m[i][column+1])) {
 876       break;
 877     }
 878   }
 879   return (i == relation->nb_rows ? -1 : i );
 880 }