source/beta.c

   1
   2    /*--------------------------------------------------------------------+
   3     |                              Clay                                  |
   4     |--------------------------------------------------------------------|
   5     |                             beta.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
  39 #include <osl/scop.h>
  40 #include <osl/statement.h>
  41 #include <osl/relation.h>
  42
  43 #include <clay/array.h>
  44 #include <clay/beta.h>
  45 #include <clay/macros.h>
  46 #include <clay/util.h>
  47
  48
  49 /*
  50  * clay_beta_sort function:
  51  * The list of statements in the scop is sorted in function of the beta
  52  * \param[in,out] scop
  53  */
  54 void clay_beta_sort(osl_scop_p scop) {
  55   if (scop == NULL || scop->statement == NULL || scop->statement->next == NULL)
  56     return;
  57
  58   clay_array_p beta;
  59   osl_statement_p iter;
  60   osl_statement_p tmp;
  61   int sizebuff = 50;
  62   int nb_stmt = 0;
  63   osl_statement_p *buff;
  64   int i, j;
  65
  66   CLAY_malloc(buff, osl_statement_p* , sizeof(osl_statement_p) * sizebuff);
  67
  68   for (iter = scop->statement ; iter != NULL ; iter = iter->next) {
  69     buff[nb_stmt++] = iter;
  70     if (nb_stmt == sizebuff) {
  71       sizebuff *= 2;
  72       CLAY_realloc(buff, osl_statement_p*, sizeof(osl_statement_p) * sizebuff);
  73     }
  74   }
  75
  76   // Insertion sort
  77   for (i = 1 ; i < nb_stmt ; i++) {
  78     tmp = buff[i];
  79     beta = clay_beta_get(tmp);
  80     for (j = i ; j > 0 && !clay_statement_is_before(buff[j-1], beta) ; j--)
  81       buff[j] = buff[j-1];
  82     buff[j] = tmp;
  83     clay_array_free(beta);
  84   }
  85
  86   scop->statement = buff[0];
  87   for (i = 0 ; i < nb_stmt-1 ; i++) {
  88     buff[i]->next = buff[i+1];
  89   }
  90   buff[i]->next = NULL;
  91
  92   free(buff);
  93
  94   /*
  95   // Insertion sort
  96   // this algo is less well because if the list is already sorted, the
  97   // complexity will be maximal
  98
  99   osl_statement_p current;
 100   osl_statement_p tmp;
 101   osl_statement_p head = scop->statement;
 102   tmp = head;
 103   while (tmp->next != NULL) {
 104     current = tmp->next;
 105     beta = clay_beta_get(current);
 106     if (!clay_statement_is_before(head, beta)) {
 107       tmp->next = current->next;
 108       current->next = head;
 109       head = current;
 110     } else {
 111       for (iter = head ; iter != tmp ; iter = iter->next) {
 112         if (!clay_statement_is_before(iter->next, beta))
 113           break;
 114       }
 115       if (iter != tmp) {
 116         tmp->next = current->next;
 117         iter->next = current;
 118         current->next = tmp;
 119       } else {
 120         tmp = tmp->next;
 121       }
 122     }
 123     clay_array_free(beta);
 124   }
 125   scop->statement = head;*/
 126 }
 127
 128
 129 /*
 130  * clay_beta_normalize function:
 131  * Normalize all the beta
 132  * \param[in,out] scop
 133  */
 134 void clay_beta_normalize(osl_scop_p scop) {
 135   if (!scop)
 136     return;
 137
 138   osl_statement_p sout;
 139   osl_relation_p scattering;
 140   clay_array_p beta;
 141   clay_array_p beta_next;
 142
 143   int counter_loops[CLAY_MAX_BETA_SIZE];
 144   int i, j;
 145   int row;
 146
 147   for (i = 0 ; i < CLAY_MAX_BETA_SIZE ; i++) {
 148     counter_loops[i] = 0;
 149   }
 150
 151   // TODO : we can optimize with clay_beta_sort, instead of looking for the
 152   // following each time
 153
 154   // first statement
 155   beta = clay_array_malloc(); // empty beta
 156   beta_next = clay_beta_next(scop->statement, beta, &sout);
 157
 158   // for each statement, we set the smallest beta
 159   while (beta_next != NULL) {
 160     clay_array_free(beta);
 161     beta = beta_next;
 162
 163     // set the smallest beta
 164     for (j = 0 ; j < beta->size ; j++) {
 165       //beta->data[i] = counter_loops[j];
 166       scattering = sout->scattering;
 167       row = clay_util_relation_get_line(scattering, j*2);
 168       osl_int_set_si(scattering->precision,
 169                      &scattering->m[row][scattering->nb_columns-1],
 170                      counter_loops[j]);
 171     }
 172
 173     beta_next = clay_beta_next(scop->statement, beta, &sout);
 174
 175     if (beta_next == NULL)
 176       break;
 177
 178     // search the first value wich is greater than the beta_last
 179     i = 0;
 180     while (i < beta_next->size && i < beta->size) {
 181       if (beta_next->data[i] > beta->data[i])
 182         break;
 183       i++;
 184     }
 185
 186     // update the counter array for the next step
 187     if (i != beta_next->size)
 188       counter_loops[i]++;
 189
 190     // the rest is set to zero
 191     i++;
 192     while (i < beta->size) {
 193       counter_loops[i] = 0;
 194       i++;
 195     }
 196
 197   }
 198
 199   clay_array_free(beta);
 200 }
 201
 202
 203 /**
 204  * clay_beta_get function:
 205  * \param[in] statement     Current statement
 206  * \return                  Return the real line
 207  */
 208 clay_array_p clay_beta_get(osl_statement_p statement) {
 209   if (statement == NULL)
 210     return NULL;
 211
 212   osl_relation_p scattering = statement->scattering;
 213   clay_array_p beta = clay_array_malloc();
 214   int i, j, row, tmp;
 215   int last_column = scattering->nb_columns-1;
 216   int precision = scattering->precision;
 217
 218   for (j = 1 ; j < scattering->nb_output_dims+1 ; j += 2) {
 219     // search the first non zero
 220     for (i = 0 ; i < scattering->nb_rows ; i++) {
 221       // test if the line is an equality
 222       if (osl_int_zero(precision, scattering->m[i][0])) {
 223         // non zero on the column
 224         if (!osl_int_zero(precision, scattering->m[i][j])) {
 225           // line and column are corrects
 226           if (clay_scattering_check_zeros(statement, i, j)) {
 227             row = clay_util_relation_get_line(scattering, j-1);
 228
 229             tmp = osl_int_get_si(scattering->precision,
 230                                  scattering->m[row][last_column]);
 231
 232             clay_array_add(beta, tmp);
 233             break;
 234           }
 235         }
 236       }
 237     }
 238   }
 239
 240   return beta;
 241 }
 242
 243
 244 /**
 245  * clay_beta_min function:
 246  * Return beta min
 247  * \param[in] statement     List of statements
 248  * \param[in] beta          Beta vector parent
 249  * \return
 250  */
 251 clay_array_p clay_beta_min(osl_statement_p statement, clay_array_p beta) {
 252   statement = clay_beta_find(statement, beta);
 253   if (!statement)
 254     return NULL;
 255
 256   clay_array_p beta_min = clay_beta_get(statement);
 257
 258   while (statement != NULL) {
 259     if (clay_beta_check(statement, beta) &&
 260         clay_statement_is_before(statement, beta_min)) {
 261       clay_array_free(beta_min);
 262       beta_min = clay_beta_get(statement);
 263     }
 264     statement = statement->next;
 265   }
 266
 267   return beta_min;
 268 }
 269
 270
 271 /**
 272  * clay_beta_max function:
 273  * Return the beta max
 274  * \param[in] statement     List of statements
 275  * \param[in] beta          Beta vector parent
 276  * \return
 277  */
 278 clay_array_p clay_beta_max(osl_statement_p statement, clay_array_p beta) {
 279   statement = clay_beta_find(statement, beta);
 280   if (!statement)
 281     return NULL;
 282
 283   clay_array_p beta_max = clay_beta_get(statement);
 284
 285   while (statement != NULL) {
 286     if (clay_beta_check(statement, beta) &&
 287         clay_statement_is_after(statement, beta_max)) {
 288       clay_array_free(beta_max);
 289       beta_max = clay_beta_get(statement);
 290     }
 291     statement = statement->next;
 292   }
 293
 294   return beta_max;
 295 }
 296
 297
 298 /**
 299  * clay_beta_next function:
 300  * Return the beta after the given beta.
 301  * \param[in] statement     List of statements
 302  * \param[in] beta          Beta vector
 303  * \param[out] sout         If not NULL, this is the statement wich corresponds
 304  *                          to the returned beta
 305  * \return
 306  */
 307 clay_array_p clay_beta_next(osl_statement_p statement, clay_array_p beta,
 308                             osl_statement_p *sout) {
 309   if(!statement)
 310     return NULL;
 311   clay_array_p beta_next = NULL;
 312   const int nb_dims = beta->size*2-1;
 313   int is_statement;
 314
 315   // Search the first statement after the beta
 316   while (statement != NULL) {
 317     is_statement = statement->scattering->nb_output_dims <= nb_dims;
 318     if ((!is_statement && !clay_statement_is_before(statement, beta)) ||
 319         (is_statement && clay_statement_is_after(statement, beta))) {
 320       beta_next = clay_beta_get(statement);
 321       if (sout) *sout = statement;
 322       break;
 323     }
 324     statement = statement->next;
 325   }
 326
 327   if (beta_next == NULL) {
 328     if (sout) *sout = NULL;
 329     return NULL;
 330   }
 331   /*if (is_statement &&
 332       statement->scattering->nb_output_dims < beta_next->size*2-1) {
 333     clay_array_free(beta_next);
 334     if (sout) *sout = NULL;
 335     return NULL;
 336   }*/
 337
 338   // Search if there is an another beta before the beta we have found
 339   while (statement != NULL) {
 340     is_statement = statement->scattering->nb_output_dims <= nb_dims;
 341     if (((!is_statement && !clay_statement_is_before(statement, beta)) ||
 342          (is_statement && clay_statement_is_after(statement, beta))) &&
 343         clay_statement_is_before(statement, beta_next)) {
 344       clay_array_free(beta_next);
 345       beta_next = clay_beta_get(statement);
 346       if (sout) *sout = statement;
 347     }
 348     statement = statement->next;
 349   }
 350
 351   return beta_next;
 352 }
 353
 354
 355 /**
 356  * clay_beta_next_part function:
 357  * Return the beta after (strictly) the given beta.
 358  * If the beta is a loop, the next beta is the beta which is after the loop (and
 359  * not the statements inside the loop)
 360  * \param[in] statement     List of statements
 361  * \param[in] beta          Beta vector
 362  * \return
 363  */
 364 clay_array_p clay_beta_next_part(osl_statement_p statement, clay_array_p beta) {
 365   if(!statement)
 366     return NULL;
 367
 368   clay_array_p beta_next = NULL;
 369
 370   // Search the first statement after the beta
 371   while (statement != NULL) {
 372     if (clay_statement_is_after(statement, beta)) {
 373       beta_next = clay_beta_get(statement);
 374       break;
 375     }
 376     statement = statement->next;
 377   }
 378
 379   if (beta_next == NULL)
 380     return NULL;
 381
 382   // Search if there is an another beta before the beta we have found
 383   while (statement != NULL) {
 384     if (clay_statement_is_after(statement, beta) &&
 385         clay_statement_is_before(statement, beta_next)) {
 386       clay_array_free(beta_next);
 387       beta_next = clay_beta_get(statement);
 388     }
 389     statement = statement->next;
 390   }
 391
 392   return beta_next;
 393 }
 394
 395
 396 /**
 397  * clay_beta_find function:
 398  * Return the first statement (the first checked by the beta and not the first
 399  * in the list, use clay_beta_min for this purpose) which corresponds to the
 400  * beta vector
 401  * \param[in] statement     Start statement list
 402  * \param[in] beta          Vector to search
 403  * \return                  Return the first corresponding statement
 404  */
 405 osl_statement_p clay_beta_find(osl_statement_p statement,
 406                                clay_array_p beta) {
 407   while (statement != NULL) {
 408     if (clay_beta_check(statement, beta))
 409       break;
 410     statement = statement->next;
 411   }
 412   return statement;
 413 }
 414
 415
 416 /**
 417  * clay_beta_nb_parts function:
 418  * It doesn't count statements inside sub loops
 419  * Example:
 420  * for(i) {
 421  *   S1(i)
 422  *   for(j) {
 423  *     S2(i,j)
 424  *     S3(i,j)
 425  *   }
 426  * }
 427  * nb_parts in for(i) = 2 (S1 and for(j))
 428  * \param[in] statement     Statements list
 429  * \param[in] beta          Vector to search
 430  * \return
 431  */
 432 int clay_beta_nb_parts(osl_statement_p statement, clay_array_p beta) {
 433   int n = 0;
 434   const int column = beta->size*2;
 435   int last_level = -1;
 436   int current_level;
 437   int row;
 438   osl_relation_p scattering;
 439   while (statement != NULL) {
 440     if (clay_beta_check(statement, beta)) {
 441       scattering = statement->scattering;
 442       if (column < scattering->nb_output_dims) {
 443         row = clay_util_relation_get_line(scattering, column);
 444         current_level = osl_int_get_si(scattering->precision,
 445                                  scattering->m[row][scattering->nb_columns-1]);
 446         if (current_level != last_level) {
 447           n++;
 448           last_level = current_level;
 449         }
 450       } else if (column-2 >= scattering->nb_output_dims-1) {
 451         // it's a statement
 452         return 1;
 453       }
 454     }
 455     statement = statement->next;
 456   }
 457   return n;
 458 }
 459
 460
 461 /**
 462  * clay_beta_shift_before function:
 463  * Shift before the statement wich corresponds to the beta. It's pratically
 464  * the same function as clay_beta_shift_after but it's equal or after, not
 465  * strictly after. If the beta is empty, the function does nothing.
 466  * \param[in,out] statement Statements list
 467  * \param[in] beta          Beta vector
 468  * \param[in] depth         Depth level to shift, >= 1
 469  */
 470 void clay_beta_shift_before(osl_statement_p statement, clay_array_p beta,
 471                            int depth) {
 472   if (beta->size == 0)
 473     return;
 474   osl_relation_p scattering;
 475   const int column = (depth-1)*2;  // alpha column
 476   int row;
 477   int precision = statement->scattering->precision;
 478
 479   clay_array_p beta_parent = clay_array_clone(beta);
 480   (beta_parent)->size = depth-1;
 481
 482   while (statement != NULL) {
 483     if (!clay_statement_is_before(statement, beta)) { // after or equal
 484       if (clay_beta_check(statement, beta_parent)) {
 485         scattering = statement->scattering;
 486         if (column < scattering->nb_output_dims) {
 487           row = clay_util_relation_get_line(scattering, column);
 488           osl_int_increment(precision,
 489                             &scattering->m[row][scattering->nb_columns-1],
 490                             scattering->m[row][scattering->nb_columns-1]);
 491         }
 492       }
 493     }
 494     statement = statement->next;
 495   }
 496   clay_array_free(beta_parent);
 497 }
 498
 499
 500 /**
 501  * clay_beta_shift_after function:
 502  * Shift after (strictly) the statement which corresponds to the beta.
 503  * If the beta is empty, the function does nothing.
 504  * \param[in,out] statement Statements list
 505  * \param[in] beta          Beta vector
 506  * \param[in] depth         Depth level to shift, >= 1
 507  */
 508 void clay_beta_shift_after(osl_statement_p statement, clay_array_p beta,
 509                            int depth) {
 510   if (beta->size == 0)
 511     return;
 512   osl_relation_p scattering;
 513   const int column = (depth-1)*2;  // alpha column
 514   int row;
 515   int precision = statement->scattering->precision;
 516
 517   clay_array_p beta_parent = clay_array_clone(beta);
 518   beta_parent->size = depth-1;
 519
 520   while (statement != NULL) {
 521     if (clay_statement_is_after(statement, beta)) {
 522       scattering = statement->scattering;
 523       if (column < scattering->nb_output_dims) {
 524         row = clay_util_relation_get_line(scattering, column);
 525         osl_int_increment(precision,
 526                           &scattering->m[row][scattering->nb_columns-1],
 527                           scattering->m[row][scattering->nb_columns-1]);
 528       }
 529     }
 530     statement = statement->next;
 531   }
 532   clay_array_free(beta_parent);
 533 }
 534
 535
 536 /**
 537  * clay_statement_is_before function:
 538  * Return true if the statement is before (strictly) the beta
 539  * \param[in] statement
 540  * \param[in] beta
 541  * \return
 542  */
 543 int clay_statement_is_before(osl_statement_p statement, clay_array_p beta) {
 544   osl_relation_p scat = statement->scattering;
 545   int precision = scat->precision;
 546   int row;
 547   int i;
 548   int end;
 549
 550   if (scat->nb_output_dims >= beta->size*2+1)
 551     end = beta->size;
 552   else
 553     end = (scat->nb_output_dims+1)/2;
 554
 555   osl_int_p tmp = osl_int_malloc(precision);
 556
 557   for (i = 0 ; i < end ; i++) {
 558     row = clay_util_relation_get_line(scat, i*2);
 559     osl_int_add_si(precision,
 560                    tmp,
 561                    scat->m[row][scat->nb_columns-1],
 562                    -beta->data[i]); // -> substraction
 563     if (osl_int_pos(precision, *tmp)) {
 564       osl_int_free(precision, tmp);
 565       return 0;
 566     } else if (osl_int_neg(precision, *tmp)) {
 567       osl_int_free(precision, tmp);
 568       return 1;
 569     }
 570   }
 571   osl_int_free(precision, tmp);
 572   return 0;
 573 }
 574
 575
 576 /**
 577  * clay_statement_is_after function:
 578  * Return true if statement is after (strictly) the beta
 579  * \param[in] statement
 580  * \param[in] beta
 581  * \return
 582  */
 583 int clay_statement_is_after(osl_statement_p statement, clay_array_p beta) {
 584   return !clay_beta_check(statement, beta) &&
 585          !clay_statement_is_before(statement, beta);
 586 }
 587
 588
 589 /**
 590  * clay_beta_check function:
 591  * check if the current statement corresponds to the beta vector
 592  * \param[in] statement     Statement to test
 593  * \param[in] beta          Vector to search
 594  * \return                  true if correct
 595  */
 596 int clay_beta_check(osl_statement_p statement, clay_array_p beta) {
 597   if (beta->size == 0)
 598     return 1;
 599
 600   int end;
 601   if (statement->scattering->nb_output_dims >= beta->size*2+1)
 602     end = beta->size;
 603   else
 604     end = (statement->scattering->nb_output_dims+1)/2;
 605
 606   //if (beta->size*2-1 > statement->scattering->nb_output_dims)
 607   //  return 0;
 608
 609   osl_relation_p scattering = statement->scattering;
 610   int last_column = scattering->nb_columns-1;
 611   int i, j = 1, k;
 612   int ok;
 613   int tmp;
 614   int precision = scattering->precision;
 615
 616   for (k = 0 ; k < end ; k++) {
 617     ok = 0;
 618
 619     // search the first non zero
 620     for (i = 0 ; i < scattering->nb_rows ; i++) {
 621
 622       // test if the line is an equality
 623       if (osl_int_zero(precision, scattering->m[i][0])) {
 624
 625         // non zero on the column
 626         if (!osl_int_zero(precision, scattering->m[i][j])) {
 627           tmp = osl_int_get_si(precision, scattering->m[i][last_column]);
 628           if (tmp != beta->data[k]) {
 629             return 0;
 630           }
 631
 632           // line and column are corrects ?
 633           if (!clay_scattering_check_zeros(statement, i, j)) {
 634             // errors should not happen
 635             return 0;
 636           }
 637
 638           ok = 1;
 639           break;
 640         }
 641       }
 642     }
 643
 644     if (!ok)
 645       return 0;
 646
 647     j += 2;
 648   }
 649
 650   return 1;
 651 }
 652
 653
 654 /**
 655  * clay_scattering_check_zeros function:
 656  * check if the scattering on the first statement contains only zero at line i
 657  * and column j, but not on (i,j), on the first column (equality column), and on
 658  * the last column.
 659  * Used to check if the line is a line of a beta vector
 660  * \param[in] statement
 661  * \param[in] i
 662  * \param[in] j
 663  * \return                  true if correct
 664  */
 665 int clay_scattering_check_zeros(osl_statement_p statement, int i, int j) {
 666   osl_relation_p scattering = statement->scattering;
 667   int precision = scattering->precision;
 668   int t;
 669
 670   for (t = i+1 ; t < scattering->nb_rows ; t++) {
 671     if (!osl_int_zero(precision, scattering->m[t][j])) {
 672       fprintf(stderr, "[Clay] Warning: the scattering is incorrect (column %d)\n",
 673               j);
 674       fprintf(stderr, "[Clay] a non-zero value appear\n");
 675       osl_statement_p tmp = statement->next;
 676       statement->next = NULL;
 677       osl_statement_dump(stderr, statement);
 678       statement->next = tmp;
 679       return 0;
 680     }
 681   }
 682   for (t = j+1 ; t < scattering->nb_columns-1 ; t++) {
 683     if (!osl_int_zero(precision, scattering->m[i][t])) {
 684       fprintf(stderr, "[Clay] Warning: the scattering is incorrect (line %d)\n",
 685               i+1);
 686       fprintf(stderr, "[Clay] a non-zero value appear\n");
 687       osl_statement_p tmp = statement->next;
 688       statement->next = NULL;
 689       osl_statement_dump(stderr, statement);
 690       statement->next = tmp;
 691       return 0;
 692     }
 693   }
 694
 695   return 1;
 696 }
 697