clan/source/matrix.c

   1
   2    /*+------- <| --------------------------------------------------------**
   3     **         A                     Clan                                **
   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 3 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 <clan/matrix.h>
  44
  45
  46 /*+****************************************************************************
  47  *                            Processing functions                            *
  48  ******************************************************************************/
  49
  50
  51 /**
  52  * clan_matrix_tag_array function:
  53  * this function tags a matrix to explicit it is describing the array index of
  54  * a given array. This means using SCoP representation that the very first
  55  * element of the very first row will be the array number instead of zero.
  56  * It updates directly the matrix provided as parameter.
  57  * \param matrix The matrix to tag.
  58  * \param array  The array number.
  59  **
  60  * - 02/05/2008: first version.
  61  */
  62 void
  63 clan_matrix_tag_array(scoplib_matrix_p matrix, int array)
  64 {
  65   if ((matrix == NULL) || (matrix->NbRows == 0))
  66   {
  67     fprintf(stderr,"[Clan] Error: matrix cannot be array-tagged\n");
  68     exit(1);
  69   }
  70
  71   SCOPVAL_set_si(matrix->p[0][0],array);
  72 }
  73
  74
  75 /**
  76  * clan_matrix_scheduling function:
  77  * this function builds the scheduling matrix for the clan_statement_t
  78  * structures thanks to the parser current state of parser_scheduling (rank)
  79  * and parser_depth (depth). The "rank" vector gives the "position" of the
  80  * statement for every loop depth (see Feautrier's demonstration of existence
  81  * of a schedule for any SCoP or CLooG's manual for original scattering
  82  * function to understand if necessary). This function just "expands" this
  83  * vector to a (2*n+1)-dimensional schedule for a statement at depth n and
  84  * returns it.
  85  * \param rank  The position of the statement at every loop depth.
  86  * \param depth The depth of the statement.
  87  **
  88  * - 01/05/2008: First version.
  89  */
  90 scoplib_matrix_p
  91 clan_matrix_scheduling(int * rank, int depth)
  92 {
  93   int i, j, nb_rows, nb_columns;
  94   scoplib_matrix_p scheduling;
  95
  96   nb_rows    = 2 * depth + 1;
  97   nb_columns = CLAN_MAX_DEPTH + CLAN_MAX_PARAMETERS + 2;
  98   scheduling = scoplib_matrix_malloc(nb_rows,nb_columns);
  99
 100   j = 0;
 101   for (i = 0; i < depth; i++)
 102   {
 103     SCOPVAL_set_si(scheduling->p[j][nb_columns-1],rank[i]);
 104     SCOPVAL_set_si(scheduling->p[j+1][i+1],1);
 105     j += 2;
 106   }
 107   SCOPVAL_set_si(scheduling->p[nb_rows-1][nb_columns-1],rank[depth]);
 108
 109   return scheduling;
 110 }
 111
 112
 113 /**
 114  * clan_matrix_compact function:
 115  * This function compacts a matrix such that it uses the right number
 116  * of columns (during construction we used CLAN_MAX_DEPTH and
 117  * CLAN_MAX_PARAMETERS to define matrix and vector sizes). It modifies
 118  * directly the matrix provided as parameter.
 119  * \param matrix        The matrix to compact.
 120  * \param nb_iterators  The true number of iterators for this matrix.
 121  * \param nb_parameters The true number of parameters in the SCoP.
 122  **
 123  * - 02/05/2008: first version.
 124  * - 24/05/2008: nice bug fixed (p_Init_size was not copied, segfaulting later).
 125  */
 126 void
 127 clan_matrix_compact(scoplib_matrix_p matrix, int nb_iterators,
 128                     int nb_parameters)
 129 {
 130   int i, j, nb_columns;
 131   scoplib_matrix_p compacted;
 132
 133   if (matrix == NULL)
 134     return;
 135
 136   nb_columns = nb_iterators + nb_parameters + 2;
 137   compacted = scoplib_matrix_malloc(matrix->NbRows,nb_columns);
 138
 139   for (i = 0; i < matrix->NbRows; i++)
 140   {
 141     /* We copy the equality/inequality tag and the iterator coefficients */
 142     for (j = 0; j <= nb_iterators; j++)
 143       SCOPVAL_assign(compacted->p[i][j],matrix->p[i][j]);
 144
 145     /* Then we copy the parameter coefficients */
 146     for (j = 0; j < nb_parameters; j++)
 147       SCOPVAL_assign(compacted->p[i][j + nb_iterators + 1],
 148                      matrix->p[i][j + CLAN_MAX_DEPTH + 1]);
 149
 150     /* Lastly the scalar coefficient */
 151     SCOPVAL_assign(compacted->p[i][nb_columns - 1],
 152                    matrix->p[i][matrix->NbColumns - 1]);
 153   }
 154
 155   scoplib_matrix_free_inside(matrix);
 156
 157   /* Replace the inside of matrix */
 158   matrix->NbRows      = compacted->NbRows;
 159   matrix->NbColumns   = compacted->NbColumns;
 160   matrix->p           = compacted->p;
 161   matrix->p_Init      = compacted->p_Init;
 162   matrix->p_Init_size = compacted->p_Init_size;
 163
 164   /* Free the compacted "container" */
 165   free(compacted);
 166 }