source/matrix.c

   1
   2    /*+------- <| --------------------------------------------------------**
   3     **         A                  Clan/Scop                              **
   4     **---     /.\   -----------------------------------------------------**
   5     **   <|  [""M#                 matrix.c                              **
   6     **-   A   | #   -----------------------------------------------------**
   7     **   /.\ [""M#         First version: 30/04/2008                     **
   8     **- [""M# | #  U"U#U  -----------------------------------------------**
   9          | #  | #  \ .:/
  10          | #  | #___| #
  11  ******  | "--'     .-"  ******************************************************
  12  *     |"-"-"-"-"-#-#-##   Clan : the Chunky Loop Analyzer (experimental)     *
  13  ****  |     # ## ######  *****************************************************
  14  *      \       .::::'/                                                       *
  15  *       \      ::::'/     Copyright (C) 2008 Cedric Bastoul                  *
  16  *     :8a|    # # ##                                                         *
  17  *     ::88a      ###      This is free software; you can redistribute it     *
  18  *    ::::888a  8a ##::.   and/or modify it under the terms of the GNU Lesser *
  19  *  ::::::::888a88a[]:::   General Public License as published by the Free    *
  20  *::8:::::::::SUNDOGa8a::. Software Foundation, either version 2.1 of the     *
  21  *::::::::8::::888:Y8888:: License, or (at your option) any later version.    *
  22  *::::':::88::::888::Y88a::::::::::::...                                      *
  23  *::'::..    .   .....   ..   ...  .                                          *
  24  * This software is distributed in the hope that it will be useful, but       *
  25  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY *
  26  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License   *
  27  * for more details.                                                          *
  28  *                                                                            *
  29  * You should have received a copy of the GNU Lesser General Public License   *
  30  * along with software; if not, write to the Free Software Foundation, Inc.,  *
  31  * 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA                     *
  32  *                                                                            *
  33  * Clan, the Chunky Loop Analyzer                                             *
  34  * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr                         *
  35  *                                                                            *
  36  ******************************************************************************/
  37
  38
  39 # include <stdlib.h>
  40 # include <stdio.h>
  41 # include <string.h>
  42 # include <ctype.h>
  43 # include <scoplib/matrix.h>
  44
  45
  46 /*+****************************************************************************
  47  *                          Structure display function                        *
  48  ******************************************************************************/
  49
  50
  51 /**
  52  * scoplib_matrix_print_structure function:
  53  * Displays a scoplib_matrix_t structure (*matrix) into a file (file, possibly
  54  * stdout) in a way that trends to be understandable without falling in a deep
  55  * depression or, for the lucky ones, getting a headache... It includes an
  56  * indentation level (level) in order to work with others print_structure
  57  * functions.
  58  * \param file   File where informations are printed.
  59  * \param matrix The matrix whose information have to be printed.
  60  * \param level  Number of spaces before printing, for each line.
  61  **
  62  * - 30/04/2008: first version (from CLooG 0.14.0).
  63  */
  64 void
  65 scoplib_matrix_print_structure(FILE * file, scoplib_matrix_p matrix, int level)
  66 {
  67   int i, j;
  68
  69   /* Go to the right level. */
  70   for (j = 0; j < level; j++)
  71     fprintf(file,"|\t");
  72
  73   if (matrix != NULL)
  74   {
  75     fprintf(file,"+-- scoplib_matrix_t\n");
  76
  77     for(j = 0; j <= level; j++)
  78       fprintf(file,"|\t");
  79     fprintf(file,"%d %d\n",matrix->NbRows,matrix->NbColumns);
  80
  81     /* Display the matrix. */
  82     for (i = 0; i < matrix->NbRows; i++)
  83     {
  84       for (j = 0; j <= level; j++)
  85         fprintf(file,"|\t");
  86
  87       fprintf(file,"[ ");
  88
  89       for (j = 0; j < matrix->NbColumns; j++)
  90       {
  91         SCOPVAL_print(file,SCOPLIB_FMT,matrix->p[i][j]);
  92         fprintf(file," ");
  93       }
  94
  95       fprintf(file,"]\n");
  96     }
  97   }
  98   else
  99     fprintf(file,"+-- NULL matrix\n");
 100
 101   /* The last line. */
 102   for (j = 0; j <= level; j++)
 103     fprintf(file,"|\t");
 104   fprintf(file,"\n");
 105 }
 106
 107
 108 /**
 109  * scoplib_matrix_print function:
 110  * This function prints the content of a scoplib_matrix_t structure
 111  * (*matrix) into a file (file, possibly stdout).
 112  * \param file   File where informations are printed.
 113  * \param matrix The matrix whose information have to be printed.
 114  **
 115  * - 30/04/2008: first version (from CLooG 0.14.0).
 116  */
 117 void
 118 scoplib_matrix_print(FILE * file, scoplib_matrix_p matrix)
 119 {
 120   scoplib_matrix_print_structure(file,matrix,0);
 121 }
 122
 123
 124
 125 /**
 126  * scoplib_matrix_expression_element function:
 127  * This function returns a string containing the printing of a value (possibly
 128  * an iterator or a parameter with its coefficient or a constant).
 129  * \param val   The coefficient or constant value.
 130  * \param first Pointer to a boolean set to 1 if the current value is the first
 131  *              of an expresion, 0 otherwise (this function may update it).
 132  * \param cst   A boolean set to 1 if the value is a constant, 0 otherwise.
 133  * \param name  String containing the name of the iterator or of the parameter.
 134  **
 135  * - 03/05/2008: first version (from CLooG 0.14.0, glorious pprint_val).
 136  */
 137 static
 138 char *
 139 scoplib_matrix_expression_element(scoplib_int_t val, int * first, int cst,
 140                                   char * name)
 141 {
 142   char * sval, * body, * temp;
 143
 144   temp = (char *)malloc(SCOPLIB_MAX_STRING * sizeof(char));
 145   body = (char *)malloc(SCOPLIB_MAX_STRING * sizeof(char));
 146   sval = (char *)malloc(SCOPLIB_MAX_STRING * sizeof(char));
 147   body[0] = '\0';
 148   sval[0] = '\0';
 149
 150   /* statements for the 'normal' processing. */
 151   if (SCOPVAL_notzero_p(val) && (!cst))
 152   {
 153     if ((*first) || SCOPVAL_neg_p(val))
 154     {
 155       if (SCOPVAL_one_p(val))           /* case 1 */
 156         sprintf(sval,"%s",name);
 157       else
 158       {
 159         if (SCOPVAL_mone_p(val))        /* case -1 */
 160           sprintf(sval,"-%s",name);
 161         else                         /* default case */
 162         {
 163           SCOPVAL_sprint(sval,SCOPLIB_FMT_TXT,val);
 164           sprintf(temp,"*%s",name);
 165           strcat(sval,temp);
 166         }
 167       }
 168       *first = 0;
 169     }
 170     else
 171     {
 172       if (SCOPVAL_one_p(val))
 173         sprintf(sval,"+%s",name);
 174       else
 175       {
 176         sprintf(sval,"+");
 177         SCOPVAL_sprint(temp,SCOPLIB_FMT_TXT,val);
 178         strcat(sval,temp);
 179         sprintf(temp,"*%s",name);
 180         strcat(sval,temp);
 181       }
 182     }
 183   }
 184   else
 185   {
 186     if (cst)
 187     {
 188       if ((SCOPVAL_zero_p(val) && (*first)) || SCOPVAL_neg_p(val))
 189         SCOPVAL_sprint(sval,SCOPLIB_FMT_TXT,val);
 190       if (SCOPVAL_pos_p(val))
 191       {
 192         if (!(*first))
 193         {
 194           SCOPVAL_sprint(sval,"+"SCOPLIB_FMT_TXT,val); /* Block macro ! */
 195         }
 196         else
 197           SCOPVAL_sprint(sval,SCOPLIB_FMT_TXT,val);
 198       }
 199     }
 200   }
 201   free(temp);
 202   free(body);
 203
 204   return(sval);
 205 }
 206
 207
 208 /**
 209  * scoplib_matrix_expression function:
 210  * This function returns a string corresponding to an affine expression
 211  * stored at the "row"^th row of the matrix pointed by "matrix".
 212  * \param matrix        A set of linear expressions.
 213  * \param row           The row of the matrix corresponding to the expression.
 214  * \param nb_iterators  The number of iterators for the considered statement.
 215  * \param iterators     An array containing iterator names for the statement.
 216  * \param nb_parameters The number of parameters in the SCoP.
 217  * \param parameters    An array containing all parameters names.
 218  **
 219  * - 03/05/2008: first version (from CLooG 0.14.0, glorious pprint_val).
 220  */
 221 static
 222 char *
 223 scoplib_matrix_expression(scoplib_matrix_p matrix, int row,
 224                           int nb_iterators,  char ** iterators,
 225                           int nb_parameters, char ** parameters)
 226 {
 227   int i, first = 1;
 228   char * sline, * sval;
 229
 230   sline = (char *)malloc(SCOPLIB_MAX_STRING * sizeof(char)) ;
 231   sline[0] = '\0' ;
 232
 233   /* First the iterator part. */
 234   for (i = 1; i <= nb_iterators; i++)
 235   {
 236     sval = scoplib_matrix_expression_element(matrix->p[row][i],&first,0,
 237                                              iterators[i-1]);
 238     strcat(sline,sval);
 239     free(sval);
 240   }
 241
 242   /* Next the parameter part. */
 243   for (i = nb_iterators + 1; i <= nb_iterators + nb_parameters; i++)
 244   {
 245     sval = scoplib_matrix_expression_element(matrix->p[row][i],&first,0,
 246                                              parameters[i - nb_iterators - 1]);
 247     strcat(sline,sval);
 248     free(sval);
 249   }
 250
 251   /* Finally the constant part (yes, I reused it). */
 252   sval = scoplib_matrix_expression_element(matrix->p[row][i],&first,1,NULL);
 253   strcat(sline,sval);
 254   free(sval);
 255
 256   return sline;
 257 }
 258
 259
 260 /**
 261  * scoplib_matrix_print_dot_scop function:
 262  * This function prints the content of a scoplib_matrix_t structure
 263  * (*matrix) into a file (file, possibly stdout) for the .scop format.
 264  * \param file          File where informations are printed.
 265  * \param matrix        The matrix whose information have to be printed.
 266  * \param type          A bit of semantic about this matrix (domain, access...).
 267  * \param nb_iterators  The number of iterators for the considered statement.
 268  * \param iterators     An array containing iterator names for the statement.
 269  * \param nb_parameters The number of parameters in the SCoP.
 270  * \param parameters    An array containing all parameters names.
 271  * \param nb_arrays     The number of arrays accessed in the SCoP.
 272  * \param arrays        An array containing all accessed array names.
 273  **
 274  * - 02/05/2008: first version.
 275  */
 276 void
 277 scoplib_matrix_print_dot_scop(FILE * file, scoplib_matrix_p matrix, int type,
 278                               int nb_iterators,  char ** iterators,
 279                               int nb_parameters, char ** parameters,
 280                               int nb_arrays,     char ** arrays)
 281 {
 282   int i, j, k;
 283   char * expression;
 284
 285   if (matrix == NULL)
 286   {
 287     fprintf(file,"0 %d\n",nb_iterators+nb_parameters+2);
 288     return;
 289   }
 290
 291   fprintf(file,"%d %d\n",matrix->NbRows,matrix->NbColumns);
 292
 293   for (i = 0; i < matrix->NbRows; i++)
 294   {
 295     for (j = 0; j < matrix->NbColumns; j++)
 296     {
 297       SCOPVAL_print(file,SCOPLIB_FMT,matrix->p[i][j]);
 298       fprintf(file," ");
 299     }
 300
 301     if (type == SCOPLIB_TYPE_DOMAIN)
 302     {
 303       expression = scoplib_matrix_expression(matrix,i,nb_iterators,iterators,
 304                                              nb_parameters,parameters);
 305       fprintf(file,"   ## %s",expression);
 306       free(expression);
 307       if (SCOPVAL_zero_p(matrix->p[i][0]))
 308         fprintf(file," == 0");
 309       else
 310         fprintf(file," >= 0");
 311     }
 312
 313     if (type == SCOPLIB_TYPE_SCATTERING)
 314     {
 315       expression = scoplib_matrix_expression(matrix,i,nb_iterators,iterators,
 316                                              nb_parameters,parameters);
 317       fprintf(file,"   ## %s",expression);
 318       free(expression);
 319     }
 320
 321     if (type == SCOPLIB_TYPE_ACCESS)
 322     {
 323       if (SCOPVAL_notzero_p(matrix->p[i][0]))
 324       {
 325         if (strncmp(arrays[SCOPVAL_get_si(matrix->p[i][0]) - 1],
 326                     SCOPLIB_FAKE_ARRAY, strlen(SCOPLIB_FAKE_ARRAY)))
 327           fprintf(file,"   ## %s",arrays[SCOPVAL_get_si(matrix->p[i][0]) - 1]);
 328         k = i;
 329         do
 330         {
 331           expression = scoplib_matrix_expression(matrix,k,nb_iterators,
 332                                                  iterators,
 333                                                  nb_parameters,parameters);
 334           fprintf(file,"[%s]",expression);
 335           free(expression);
 336           k++;
 337         }
 338         while ((k < matrix->NbRows) && SCOPVAL_zero_p(matrix->p[k][0]));
 339       }
 340       else
 341         fprintf(file,"   ##");
 342     }
 343
 344     fprintf(file,"\n");
 345   }
 346 }
 347
 348
 349 /**
 350  * scoplib_matrix_list_print_structure function:
 351  * Displays a scoplib_matrix_list_t structure (a list of matrices) into a
 352  * file (file, possibly stdout). See scoplib_matrix_print_structure for
 353  * more details.
 354  * \param file   File where informations are printed.
 355  * \param l      The list of matrices whose information have to be printed.
 356  * \param level  Number of spaces before printing, for each line.
 357  */
 358 void
 359 scoplib_matrix_list_print_structure(FILE * file, scoplib_matrix_list_p l,
 360                                     int level)
 361 {
 362   int j, first = 1;
 363
 364   /* Go to the right level. */
 365   for (j = 0; j < level; j++)
 366     fprintf(file,"|\t");
 367
 368   if (l != NULL)
 369     fprintf(file,"+-- scoplib_matrix_list_t\n");
 370   else
 371     fprintf(file,"+-- NULL matrix list\n");
 372
 373   while (l != NULL)
 374   {
 375     if (!first)
 376     {
 377       /* Go to the right level. */
 378       for (j = 0; j < level; j++)
 379         fprintf(file,"|\t");
 380       fprintf(file,"|   scoplib_matrix_list_t\n");
 381     }
 382     else
 383       first = 0;
 384
 385     /* A blank line. */
 386     for (j = 0; j <= level+1; j++)
 387       fprintf(file,"|\t");
 388     fprintf(file,"\n");
 389
 390     /* Print a matrix. */
 391     scoplib_matrix_print_structure(file,l->elt,level+1);
 392
 393     l = l->next;
 394
 395     /* Next line. */
 396     if (l != NULL)
 397     {
 398       for (j = 0; j <= level; j++)
 399         fprintf(file,"|\t");
 400       fprintf(file,"V\n");
 401     }
 402   }
 403
 404   /* The last line. */
 405   for (j = 0; j <= level; j++)
 406     fprintf(file,"|\t");
 407   fprintf(file,"\n");
 408 }
 409
 410
 411 /**
 412  * scoplib_matrix_list_print function:
 413  * This function prints the content of a scoplib_matrix_list_t into
 414  * a file (file, possibly stdout).
 415  * \param file   File where informations are printed.
 416  * \param list The matrix whose information have to be printed.
 417  **
 418  * - 30/04/2008: first version (from CLooG 0.14.0).
 419  */
 420 void
 421 scoplib_matrix_list_print(FILE * file, scoplib_matrix_list_p list)
 422 {
 423   scoplib_matrix_list_print_structure(file, list, 0);
 424 }
 425
 426
 427 /**
 428  * scoplib_matrix_list_print_dot_scop function:
 429  * This function prints the content of a scoplib_matrix_list_t structure into
 430  * a file (file, possibly stdout) for the .scop format.
 431  * \param file          File where informations are printed.
 432  * \param list          The matrix list whose information have to be printed.
 433  * \param type          A bit of semantic about this matrix (domain, access...).
 434  * \param nb_iterators  The number of iterators for the considered statement.
 435  * \param iterators     An array containing iterator names for the statement.
 436  * \param nb_parameters The number of parameters in the SCoP.
 437  * \param parameters    An array containing all parameters names.
 438  * \param nb_arrays     The number of arrays accessed in the SCoP.
 439  * \param arrays        An array containing all accessed array names.
 440  */
 441 void
 442 scoplib_matrix_list_print_dot_scop(FILE * file, scoplib_matrix_list_p list,
 443                                    int type,
 444                                    int nb_iterators,  char ** iterators,
 445                                    int nb_parameters, char ** parameters,
 446                                    int nb_arrays,     char ** arrays)
 447 {
 448   int i;
 449   scoplib_matrix_list_p head = list;
 450
 451   /* Count the number of elements in the list. */
 452   for (i = 0; list; list = list->next, i++)
 453     ;
 454   /* Print it. */
 455   fprintf(file,"%d\n", i);
 456   /* Print each element of the matrix list. */
 457   while (head)
 458   {
 459     scoplib_matrix_print_dot_scop(file, head->elt, type,
 460                                   nb_iterators, iterators,
 461                                   nb_parameters, parameters,
 462                                   nb_arrays, arrays);
 463     head = head->next;
 464   }
 465 }
 466
 467
 468 /******************************************************************************
 469  *                               Reading function                             *
 470  ******************************************************************************/
 471
 472
 473 /**
 474  * scoplib_matrix_read function:
 475  * Adaptation from the PolyLib. This function reads a matrix into a file (foo,
 476  * posibly stdin) and returns a pointer this matrix.
 477  * October 18th 2001: first version.
 478  * - April 17th 2005: this function moved from domain.c to here.
 479  * - June  21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
 480  *                    CLooG 0.12.1).
 481  * - July 9th 2008: Grabbed from CLooG and adapted for Scoplib.
 482  */
 483 scoplib_matrix_p
 484 scoplib_matrix_read(FILE* foo)
 485 {
 486   unsigned NbRows, NbColumns;
 487   int i, j, n;
 488   char* c, s[SCOPLIB_MAX_STRING], str[SCOPLIB_MAX_STRING];
 489   scoplib_matrix_p matrix;
 490   scoplib_int_t* p;
 491
 492   while (fgets(s, SCOPLIB_MAX_STRING, foo) == 0)
 493     ;
 494   while ((*s=='#' || *s=='\n') ||
 495          (sscanf(s, " %u %u", &NbRows, &NbColumns) < 2))
 496     fgets(s, SCOPLIB_MAX_STRING, foo);
 497
 498   matrix = scoplib_matrix_malloc(NbRows, NbColumns);
 499
 500   p = matrix->p_Init;
 501   for (i = 0; i < matrix->NbRows; i++)
 502     {
 503       do
 504         {
 505           c = fgets(s, SCOPLIB_MAX_STRING, foo);
 506           while ((c != NULL) && isspace(*c) && (*c != '\n'))
 507             c++;
 508         }
 509       while (c != NULL && (*c == '#' || *c == '\n'));
 510
 511       if (c == NULL)
 512         {
 513           fprintf(stderr, "[Scoplib] Error: not enough rows\n");
 514           exit(1);
 515         }
 516       for (j = 0; j < matrix->NbColumns; j++)
 517         {
 518           if (c == NULL || *c == '#' || *c == '\n')
 519             {
 520               fprintf(stderr, "[Scoplib] Error: not enough columns\n");
 521               exit(1);
 522             }
 523           if (sscanf(c, "%s%n", str, &n) == 0)
 524             {
 525               fprintf(stderr, "[Scoplib] Error: not enough rows\n");
 526               exit(1);
 527             }
 528 #if defined(SCOPLIB_INT_T_IS_MP)
 529       long long val;
 530           sscanf(str, "%lld", &val);
 531           mpz_set_si(*p++, val);
 532 #else
 533           sscanf(str, SCOPLIB_FMT_TXT, p++);
 534 #endif
 535           c += n;
 536         }
 537     }
 538
 539   return matrix;
 540 }
 541
 542
 543 /**
 544  * scoplib_matrix_list_read function:
 545  * This function reads a list of matrices into a file (foo,
 546  * posibly stdin) and returns a pointer this matrix list.
 547  * \param file   File where informations are stored.
 548  */
 549 scoplib_matrix_list_p
 550 scoplib_matrix_list_read(FILE* file)
 551 {
 552   char s[SCOPLIB_MAX_STRING];
 553   int i;
 554   scoplib_matrix_list_p list;
 555   scoplib_matrix_list_p res;
 556   int nb_mat;
 557
 558   /* Skip blank/commented lines. */
 559   while (fgets(s, SCOPLIB_MAX_STRING, file) == 0 || s[0] == '#' ||
 560          isspace(s[0]))
 561     ;
 562   /* Read the number of matrices to read. */
 563   sscanf(s, "%d", &nb_mat);
 564
 565   /* Allocate the header of the list. */
 566   res = list = scoplib_matrix_list_malloc();
 567   for (i = 0; i < nb_mat; ++i)
 568     {
 569       list->elt = scoplib_matrix_read(file);
 570       if (i < nb_mat - 1)
 571         list->next = scoplib_matrix_list_malloc();
 572       list = list->next;
 573     }
 574
 575   return res;
 576 }
 577
 578
 579 /**
 580  * scoplib_matrix_read_arrays function:
 581  * This function reads a matrix into a file (foo, posibly stdin) and
 582  * returns a pointer this matrix. In addition, it reads the arrays as
 583  * comments at the end of the line.
 584  */
 585 scoplib_matrix_p
 586 scoplib_matrix_read_arrays(FILE* foo, char*** arrays, int* nb_arr)
 587 {
 588   unsigned NbRows, NbColumns;
 589   int i, j, n;
 590   int count;
 591   char* c, s[SCOPLIB_MAX_STRING], str[SCOPLIB_MAX_STRING],
 592     buff[SCOPLIB_MAX_STRING];
 593   scoplib_matrix_p matrix;
 594   scoplib_int_t* p;
 595
 596   while (fgets(s, SCOPLIB_MAX_STRING, foo) == 0)
 597     ;
 598   while ((*s=='#' || *s=='\n') ||
 599          (sscanf(s, " %u %u", &NbRows, &NbColumns) < 2))
 600     fgets(s, SCOPLIB_MAX_STRING, foo);
 601
 602   matrix = scoplib_matrix_malloc(NbRows, NbColumns);
 603
 604   p = matrix->p_Init;
 605   for (i = 0; i < matrix->NbRows; i++)
 606     {
 607       do
 608         {
 609           c = fgets(s, SCOPLIB_MAX_STRING, foo);
 610           while ((c != NULL) && isspace(*c) && (*c != '\n'))
 611             c++;
 612         }
 613       while (c != NULL && (*c == '#' || *c == '\n'));
 614
 615       if (c == NULL)
 616         {
 617           fprintf(stderr, "[Scoplib] Error: not enough rows\n");
 618           exit(1);
 619         }
 620
 621       for (j = 0; j < matrix->NbColumns; j++)
 622         {
 623           if (c == NULL || *c == '#' || *c == '\n')
 624             {
 625               fprintf(stderr, "[Scoplib] Error: not enough columns\n");
 626               exit(1);
 627             }
 628           if (sscanf(c, "%s%n", str, &n) == 0)
 629             {
 630               fprintf(stderr, "[Scoplib] Error: not enough rows\n");
 631               exit(1);
 632             }
 633 #if defined(SCOPLIB_INT_T_IS_MP)
 634       long long val;
 635           sscanf(str, "%lld", &val);
 636           mpz_set_si(*p++, val);
 637 #else
 638           sscanf(str, SCOPLIB_FMT_TXT, p++);
 639 #endif
 640           c += n;
 641         }
 642       /* Read the array, passed as a comment at the end of the line. */
 643       if (c)
 644         {
 645           while (c && (isspace(*c) || *c == '#'))
 646             ++c;
 647           for (count = 0; c && *c != '[' && *c != '\n'; ++count)
 648             buff[count] = *(c++);
 649           buff[count] = '\0';
 650           if (count && SCOPVAL_get_si(matrix->p[i][0]))
 651             {
 652               /* Increase the buffer size if we run out of space. */
 653               if (SCOPVAL_get_si(matrix->p[i][0]) - 1 > *nb_arr)
 654                 {
 655                   *nb_arr = SCOPVAL_get_si(matrix->p[i][0]) - 1;
 656                   *arrays = (char**) realloc(*arrays,
 657                                              sizeof(char*) * (*nb_arr + 1));
 658                 }
 659               /* Backup the array name. */
 660               (*arrays)[SCOPVAL_get_si(matrix->p[i][0]) - 1] = strdup(buff);
 661             }
 662         }
 663     }
 664
 665   return matrix;
 666 }
 667
 668
 669 /*+****************************************************************************
 670  *                    Memory allocation/deallocation function                 *
 671  ******************************************************************************/
 672
 673 /**
 674  * scoplib_matrix_malloc function:
 675  * This function allocates the memory space for a scoplib_matrix_t structure and
 676  * sets its fields with default values. Then it returns a pointer to the
 677  * allocated space.
 678  * \param NbRows    The number of row of the matrix to allocate.
 679  * \param NbColumns The number of columns of the matrix to allocate.
 680  **
 681  * - 30/04/2008: first version (from PipLib 1.4.0).
 682  */
 683 scoplib_matrix_p
 684 scoplib_matrix_malloc(unsigned NbRows, unsigned NbColumns)
 685 {
 686   scoplib_matrix_p matrix;
 687   scoplib_int_t ** p, * q;
 688   int i, j;
 689
 690   matrix = (scoplib_matrix_p)malloc(sizeof(scoplib_matrix_t));
 691   if (matrix == NULL)
 692   {
 693     fprintf(stderr, "[Scoplib] Memory Overflow.\n");
 694     exit(1);
 695   }
 696   matrix->NbRows = NbRows;
 697   matrix->NbColumns = NbColumns;
 698   matrix->p_Init_size = NbRows * NbColumns;
 699   if (matrix->p_Init_size == 0)
 700   {
 701     matrix->p = NULL;
 702     matrix->p_Init = NULL;
 703   }
 704   else
 705   {
 706     p = (scoplib_int_t **)malloc(NbRows*sizeof(scoplib_int_t *));
 707     if (p == NULL)
 708     {
 709       fprintf(stderr, "[Scoplib] Memory Overflow.\n");
 710       exit(1);
 711     }
 712     q = (scoplib_int_t *)malloc(NbRows * NbColumns * sizeof(scoplib_int_t));
 713     if (q == NULL)
 714     {
 715       fprintf(stderr, "[Scoplib] Memory Overflow.\n");
 716       exit(1);
 717     }
 718     matrix->p = p;
 719     matrix->p_Init = q;
 720     for (i = 0; i < NbRows; i++)
 721     {
 722       *p++ = q;
 723       for (j = 0; j < NbColumns; j++)
 724         SCOPVAL_init_set_si(*(q+j),0);
 725       q += NbColumns;
 726     }
 727   }
 728   return matrix;
 729 }
 730
 731
 732 /**
 733  * scoplib_matrix_free_inside function:
 734  * This function frees the allocated memory for the inside of a
 735  * scoplib_matrix_t structure, i.e. only p and p_Init.
 736  * \param matrix The pointer to the matrix we want to free.
 737  **
 738  * - 02/05/2008: first version.
 739  */
 740 void
 741 scoplib_matrix_free_inside(scoplib_matrix_p matrix)
 742 {
 743   int i;
 744   scoplib_int_t * p;
 745
 746   if (matrix == NULL)
 747     return;
 748
 749   p = matrix->p_Init;
 750   for (i = 0; i < matrix->p_Init_size; i++)
 751     SCOPVAL_clear(*p++);
 752
 753   if (matrix->p_Init != NULL)
 754     free(matrix->p_Init);
 755
 756   if (matrix->p != NULL)
 757     free(matrix->p);
 758 }
 759
 760
 761 /**
 762  * scoplib_matrix_free function:
 763  * This function frees the allocated memory for a scoplib_matrix_t structure.
 764  * \param matrix The pointer to the matrix we want to free.
 765  **
 766  * - 30/04/2008: first version.
 767  * - 02/05/2008: now uses scoplib_matrix_free_inside.
 768  */
 769 void
 770 scoplib_matrix_free(scoplib_matrix_p matrix)
 771 {
 772   if (matrix == NULL)
 773     return;
 774
 775   scoplib_matrix_free_inside(matrix);
 776   free(matrix);
 777 }
 778
 779
 780 /**
 781  * scoplib_matrix_list_malloc function:
 782  * This function allocates the memory space for a scoplib_matrix_list_t
 783  * structure and sets its fields with default values. Then it returns
 784  * a pointer to the allocated space.
 785  */
 786 scoplib_matrix_list_p
 787 scoplib_matrix_list_malloc()
 788 {
 789   scoplib_matrix_list_p res =
 790     (scoplib_matrix_list_p) malloc(sizeof(scoplib_matrix_list_t));
 791
 792   if (res == NULL)
 793     {
 794       fprintf(stderr, "[Scoplib] Memory Overflow.\n");
 795       exit(1);
 796     }
 797
 798   res->elt = NULL;
 799   res->next = NULL;
 800
 801   return res;
 802 }
 803
 804
 805
 806 /**
 807  * scoplib_matrix_list_free function:
 808  * This function frees the allocated memory for a scoplib_matrix_list_t
 809  * structure, and all the matrices stored in the list.
 810  * \param list The pointer to the matrix list we want to free.
 811  */
 812 void
 813 scoplib_matrix_list_free(scoplib_matrix_list_p list)
 814 {
 815   scoplib_matrix_list_p tmp;
 816
 817   if (list == NULL)
 818     return;
 819
 820   while (list)
 821     {
 822       if (list->elt)
 823         scoplib_matrix_free(list->elt);
 824       tmp = list->next;
 825       free(list);
 826       list = tmp;
 827     }
 828 }
 829
 830
 831 /*+****************************************************************************
 832  *                            Processing functions                            *
 833  ******************************************************************************/
 834
 835
 836 /**
 837  * scoplib_matrix_ncopy function:
 838  * this functions builds and returns a "hard copy" (not a pointer copy) of a
 839  * scoplib_matrix_t data structure such that the copy is restricted to the "n"
 840  * first rows of the matrix.
 841  * \param matrix The pointer to the matrix we want to copy.
 842  * \param n      The number of row of the matrix we want to copy.
 843  **
 844  * - 02/05/2008: first version.
 845  */
 846 scoplib_matrix_p
 847 scoplib_matrix_ncopy(scoplib_matrix_p matrix, int n)
 848 {
 849   int i, j;
 850   scoplib_matrix_p copy;
 851
 852   if (matrix == NULL)
 853     return NULL;
 854
 855   if (n > matrix->NbRows)
 856   {
 857     fprintf(stderr,"[Scoplib] Error: not enough rows in the matrix\n");
 858     exit(1);
 859   }
 860
 861   copy = scoplib_matrix_malloc(n,matrix->NbColumns);
 862
 863   for (i = 0; i < n; i++)
 864     for (j = 0; j < matrix->NbColumns; j++)
 865       SCOPVAL_assign(copy->p[i][j],matrix->p[i][j]);
 866
 867   return copy;
 868 }
 869
 870
 871 /**
 872  * scoplib_matrix_copy function:
 873  * this functions builds and returns a "hard copy" (not a pointer copy) of a
 874  * scoplib_matrix_t data structure.
 875  * \param matrix The pointer to the matrix we want to copy.
 876  **
 877  * - 30/04/2008: first version (from CLooG 0.14.0).
 878  * - 02/05/2008: no uses scoplib_matrix_ncopy.
 879  */
 880 scoplib_matrix_p
 881 scoplib_matrix_copy(scoplib_matrix_p matrix)
 882 {
 883   if (matrix == NULL)
 884     return NULL;
 885
 886   return scoplib_matrix_ncopy(matrix,matrix->NbRows);
 887 }
 888
 889
 890 /**
 891  * scoplib_matrix_replace_vector function:
 892  * this function replaces the "row"^th row of a matrix "matrix" with the
 893  * vector "vector". It directly updates "matrix".
 894  * \param matrix The matrix we want to change a row.
 895  * \param vector The vector that will replace a row of the matrix.
 896  * \param row    The row of the matrix to be replaced.
 897  **
 898  * - 02/05/2008: first version.
 899  */
 900 void
 901 scoplib_matrix_replace_vector(scoplib_matrix_p matrix, scoplib_vector_p vector,
 902                               int row)
 903 {
 904   int i;
 905
 906   if ((matrix == NULL) || (vector == NULL) ||
 907       (matrix->NbColumns != vector->Size) ||
 908       (row >= matrix->NbRows) || (row < 0))
 909   {
 910     fprintf(stderr,"[Scoplib] Error: vector cannot replace a matrix row\n");
 911     exit(1);
 912   }
 913
 914   for (i = 0; i < vector->Size; i++)
 915     SCOPVAL_assign(matrix->p[row][i],vector->p[i]);
 916 }
 917
 918
 919 /**
 920  * scoplib_matrix_add_vector function:
 921  * this function adds the "row"^th row of a matrix "matrix" with the
 922  * vector "vector". It directly updates "matrix".
 923  * \param matrix The matrix we want to change a row.
 924  * \param vector The vector that will replace a row of the matrix.
 925  * \param row    The row of the matrix to be replaced.
 926  **
 927  * - 08/28/2008: first version.
 928  */
 929 void
 930 scoplib_matrix_add_vector(scoplib_matrix_p matrix, scoplib_vector_p vector,
 931                           int row)
 932 {
 933   int i;
 934
 935   if ((matrix == NULL) || (vector == NULL) ||
 936       (matrix->NbColumns != vector->Size) ||
 937       (row >= matrix->NbRows) || (row < 0))
 938   {
 939     fprintf(stderr,"[Scoplib] Error: vector cannot replace a matrix row\n");
 940     exit(1);
 941   }
 942
 943   if (SCOPVAL_get_si(matrix->p[row][0]) == 0)
 944     SCOPVAL_assign(matrix->p[row][0],vector->p[0]);
 945   for (i = 1; i < vector->Size; i++)
 946     SCOPVAL_addto(matrix->p[row][i],matrix->p[row][i],vector->p[i]);
 947 }
 948
 949
 950 /**
 951  * scoplib_matrix_sub_vector function:
 952  * this function substracts the vector "vector" to the "row"^th row of
 953  * a matrix "matrix. It directly updates "matrix".
 954  * \param matrix The matrix we want to change a row.
 955  * \param vector The vector that will replace a row of the matrix.
 956  * \param row    The row of the matrix to be replaced.
 957  **
 958  * - 08/28/2008: first version.
 959  */
 960 void
 961 scoplib_matrix_sub_vector(scoplib_matrix_p matrix, scoplib_vector_p vector,
 962                           int row)
 963 {
 964   int i;
 965
 966   if ((matrix == NULL) || (vector == NULL) ||
 967       (matrix->NbColumns != vector->Size) ||
 968       (row >= matrix->NbRows) || (row < 0))
 969   {
 970     fprintf(stderr,"[Scoplib] Error: vector cannot replace a matrix row\n");
 971     exit(1);
 972   }
 973
 974   if (SCOPVAL_get_si(matrix->p[row][0]) == 0)
 975     SCOPVAL_assign(matrix->p[row][0],vector->p[0]);
 976   for (i = 1; i < vector->Size; i++)
 977     SCOPVAL_subtract(matrix->p[row][i],matrix->p[row][i],vector->p[i]);
 978 }
 979
 980
 981 /**
 982  * scoplib_matrix_insert_vector function:
 983  * this function adds a new row corresponding to the vector "vector" to
 984  * the matrix "matrix" by inserting it at the "row"^th row. It directly
 985  * updates "matrix". If "vector" (or "matrix") is NULL, the matrix is left
 986  * unmodified.
 987  * \param matrix The matrix we want to extend.
 988  * \param vector The vector that will be added matrix.
 989  * \param row The row where to insert the vector.
 990  **
 991  * - 02/05/2008: first version.
 992  */
 993 void
 994 scoplib_matrix_insert_vector(scoplib_matrix_p matrix, scoplib_vector_p vector,
 995                              int row)
 996 {
 997   int i, j;
 998   scoplib_matrix_p new;
 999
1000   if ((vector == NULL) || (matrix == NULL))
1001     return;
1002
1003   if ((matrix->NbColumns != vector->Size) ||
1004       (row > matrix->NbRows) || (row < 0))
1005   {
1006     fprintf(stderr,"[Scoplib] Error: vector cannot be inserted\n");
1007     exit(1);
1008   }
1009
1010   /* We use a temporary matrix just to reuse existing functions. Cleaner. */
1011   new = scoplib_matrix_malloc(matrix->NbRows+1,matrix->NbColumns);
1012
1013   for (i = 0; i < row; i++)
1014     for (j = 0; j < matrix->NbColumns; j++)
1015       SCOPVAL_assign(new->p[i][j],matrix->p[i][j]);
1016
1017   scoplib_matrix_replace_vector(new,vector,row);
1018
1019   for (i = row+1; i < matrix->NbRows; i++)
1020     for (j = 0; j < matrix->NbColumns; j++)
1021       SCOPVAL_assign(new->p[i][j],matrix->p[i-1][j]);
1022
1023   scoplib_matrix_free_inside(matrix);
1024
1025   /* Replace the inside of matrix */
1026   matrix->NbRows = new->NbRows;
1027   matrix->NbColumns = new->NbColumns;
1028   matrix->p = new->p;
1029   matrix->p_Init = new->p_Init;
1030   /* Free the new "shell" */
1031   free(new);
1032 }
1033
1034
1035 /**
1036  * scoplib_matrix_from_vector function:
1037  * this function converts a vector "vector" to a matrix with a single row
1038  * and returns a pointer to that matrix.
1039  * \param vector The vector to convert to a matrix.
1040  **
1041  * - 02/05/2008: first version.
1042  */
1043 scoplib_matrix_p
1044 scoplib_matrix_from_vector(scoplib_vector_p vector)
1045 {
1046   scoplib_matrix_p matrix;
1047
1048   if (vector == NULL)
1049     return NULL;
1050
1051   matrix = scoplib_matrix_malloc(1,vector->Size);
1052   scoplib_matrix_replace_vector(matrix,vector,0);
1053   return matrix;
1054 }
1055
1056
1057 /**
1058  * scoplib_matrix_replace_matrix function:
1059  * this function replaces some rows of a matrix "m1" with the rows of
1060  * the matrix "m2". It begins at the "row"^th row of "m1". It directly
1061  * updates "m1".
1062  * \param m1  The matrix we want to change some row1.
1063  * \param m2  The matrix containing the new rows.
1064  * \param row The first row of the matrix m1 to be replaced.
1065  **
1066  * - 02/05/2008: first version.
1067  */
1068 void
1069 scoplib_matrix_replace_matrix(scoplib_matrix_p m1, scoplib_matrix_p m2, int row)
1070 {
1071   int i, j;
1072
1073   if ((m1 == NULL) || (m2 == NULL) ||
1074       (m1->NbColumns != m1->NbColumns) ||
1075       ((row + m2->NbRows) > m1->NbRows) || (row < 0))
1076   {
1077     fprintf(stderr,"[Scoplib] Error: vector cannot replace a matrix row\n");
1078     exit(1);
1079   }
1080
1081   for (i = 0; i < m2->NbRows; i++)
1082     for (j = 0; j < m2->NbColumns; j++)
1083       SCOPVAL_assign(m1->p[i+row][j],m2->p[i][j]);
1084 }
1085
1086
1087 /**
1088  * scoplib_matrix_insert_matrix function:
1089  * this function adds new rows corresponding to the matrix "m1" to
1090  * the matrix "m2" by inserting it at the "row"^th row. It directly
1091  * updates "m1". If "m2" (or "m1") is NULL, the matrix is left
1092  * unmodified.
1093  * \param m1  The matrix we want to extend.
1094  * \param m2  The matrix to be inserted.
1095  * \param row The row where to insert the matrix
1096  **
1097  * - 02/05/2008: first version.
1098  */
1099 void
1100 scoplib_matrix_insert_matrix(scoplib_matrix_p m1, scoplib_matrix_p m2, int row)
1101 {
1102   int i, j;
1103   scoplib_matrix_p new;
1104
1105   if ((m1 == NULL) || (m2 == NULL))
1106     return;
1107
1108   if ((m1->NbColumns != m2->NbColumns) ||
1109       (row > m1->NbRows) || (row < 0))
1110   {
1111     fprintf(stderr,"[Scoplib] Error: matrix cannot be inserted\n");
1112     exit(1);
1113   }
1114
1115   /* We use a temporary matrix just to reuse existing functions. Cleaner. */
1116   new = scoplib_matrix_malloc(m1->NbRows+m2->NbRows,m1->NbColumns);
1117
1118   for (i = 0; i < row; i++)
1119     for (j = 0; j < m1->NbColumns; j++)
1120       SCOPVAL_assign(new->p[i][j],m1->p[i][j]);
1121
1122   scoplib_matrix_replace_matrix(new,m2,row);
1123
1124   for (i = row + m2->NbRows; i < m1->NbRows; i++)
1125     for (j = 0; j < m1->NbColumns; j++)
1126       SCOPVAL_assign(new->p[i][j],m1->p[i-m2->NbRows][j]);
1127
1128   scoplib_matrix_free_inside(m1);
1129
1130   /* Replace the inside of matrix */
1131   m1->NbRows = new->NbRows;
1132   m1->NbColumns = new->NbColumns;
1133   m1->p = new->p;
1134   m1->p_Init = new->p_Init;
1135
1136   /* Free the new "container" */
1137   free(new);
1138 }
1139
1140
1141 /**
1142  * scoplib_matrix_concat function:
1143  * this function builds a new matrix as the concatenation of the rows of
1144  * two other matrices sent as parameters.
1145  * \param m1  The first matrix.
1146  * \param m2  The second matrix.
1147  **
1148  * - 02/05/2008: first version.
1149  */
1150 scoplib_matrix_p
1151 scoplib_matrix_concat(scoplib_matrix_p m1, scoplib_matrix_p m2)
1152 {
1153   scoplib_matrix_p new;
1154
1155   if (m1 == NULL)
1156     return scoplib_matrix_copy(m2);
1157
1158   if (m2 == NULL)
1159     return scoplib_matrix_copy(m1);
1160
1161   if (m1->NbColumns != m2->NbColumns)
1162   {
1163     fprintf(stderr,"[Scoplib] Error: matrices cannot be concatenated\n");
1164     exit(1);
1165   }
1166
1167   new = scoplib_matrix_malloc(m1->NbRows+m2->NbRows,m1->NbColumns);
1168   scoplib_matrix_replace_matrix(new,m1,0);
1169   scoplib_matrix_replace_matrix(new,m2,m1->NbRows);
1170
1171   return new;
1172 }
1173
1174
1175 /**
1176  * scoplib_matrix_equal function:
1177  * this function returns true if the two matrices are the same, false
1178  * otherwise.
1179  * \param m1  The first matrix.
1180  * \param m2  The second matrix.
1181  *
1182  */
1183 int
1184 scoplib_matrix_equal(scoplib_matrix_p m1, scoplib_matrix_p m2)
1185 {
1186   if (m1 == m2)
1187     return 1;
1188   if (m1 == NULL || m2 == NULL)
1189     return 0;
1190   if (m1->NbRows != m2->NbRows || m1->NbColumns != m2->NbColumns)
1191     return 0;
1192   int i, j;
1193   for (i = 0; i < m1->NbRows; ++i)
1194     for (j = 0; j < m1->NbColumns; ++j)
1195       if (SCOPVAL_ne(m1->p[i][j], m2->p[i][j]))
1196         return 0;
1197   return 1;
1198 }