gcc/graphite-cloog-util.c

   1 /* Gimple Represented as Polyhedra.
   2    Copyright (C) 2009, 2010 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <sebastian.pop@inria.fr>
   4    and Tobias Grosser <grosser@fim.uni-passau.de>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25
  26 #ifdef HAVE_cloog
  27
  28 #include "ppl_c.h"
  29 #include "cloog/cloog.h"
  30 #include "graphite-cloog-util.h"
  31 #include "graphite-cloog-compat.h"
  32
  33 /* Counts the number of constraints in PCS.  */
  34
  35 static int
  36 ppl_Constrain_System_number_of_constraints (ppl_const_Constraint_System_t pcs)
  37 {
  38   ppl_Constraint_System_const_iterator_t cit, end;
  39   int num = 0;
  40
  41   ppl_new_Constraint_System_const_iterator (&cit);
  42   ppl_new_Constraint_System_const_iterator (&end);
  43
  44   for (ppl_Constraint_System_begin (pcs, cit),
  45        ppl_Constraint_System_end (pcs, end);
  46        !ppl_Constraint_System_const_iterator_equal_test (cit, end);
  47        ppl_Constraint_System_const_iterator_increment (cit))
  48     num++;
  49
  50   ppl_delete_Constraint_System_const_iterator (cit);
  51   ppl_delete_Constraint_System_const_iterator (end);
  52   return num;
  53 }
  54
  55 static void
  56 oppose_constraint (CloogMatrix *m, int row)
  57 {
  58   int k;
  59
  60   /* Do not oppose the first column: it is the eq/ineq one.  */
  61   /* Cast needed to remove warning that is generated as CLooG isl
  62      is using an unsigned int for NbColumns and CLooG PPL is
  63      using a signed int for NBColumns.  */
  64   for (k = 1; k < (int)m->NbColumns; k++)
  65     mpz_neg (m->p[row][k], m->p[row][k]);
  66 }
  67
  68 /* Inserts constraint CSTR at row ROW of matrix M.  */
  69
  70 static void
  71 insert_constraint_into_matrix (CloogMatrix *m, int row,
  72                                ppl_const_Constraint_t cstr)
  73 {
  74   ppl_Coefficient_t c;
  75   ppl_dimension_type i, dim, nb_cols = m->NbColumns;
  76
  77   ppl_Constraint_space_dimension (cstr, &dim);
  78   ppl_new_Coefficient (&c);
  79
  80   for (i = 0; i < dim; i++)
  81     {
  82       ppl_Constraint_coefficient (cstr, i, c);
  83       ppl_Coefficient_to_mpz_t (c, m->p[row][i + 1]);
  84     }
  85
  86   for (i = dim; i < nb_cols - 1; i++)
  87     mpz_set_si (m->p[row][i + 1], 0);
  88
  89   ppl_Constraint_inhomogeneous_term  (cstr, c);
  90   ppl_Coefficient_to_mpz_t (c, m->p[row][nb_cols - 1]);
  91   mpz_set_si (m->p[row][0], 1);
  92
  93   switch (ppl_Constraint_type (cstr))
  94     {
  95     case PPL_CONSTRAINT_TYPE_LESS_THAN:
  96       oppose_constraint (m, row);
  97     case PPL_CONSTRAINT_TYPE_GREATER_THAN:
  98       mpz_sub_ui (m->p[row][nb_cols - 1],
  99                      m->p[row][nb_cols - 1], 1);
 100       break;
 101
 102     case PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL:
 103       oppose_constraint (m, row);
 104     case PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL:
 105       break;
 106
 107     case PPL_CONSTRAINT_TYPE_EQUAL:
 108       mpz_set_si (m->p[row][0], 0);
 109       break;
 110
 111     default:
 112       /* Not yet implemented.  */
 113       gcc_unreachable();
 114     }
 115
 116   ppl_delete_Coefficient (c);
 117 }
 118
 119 /* Creates a CloogMatrix from constraint system PCS.  */
 120
 121 static CloogMatrix *
 122 new_Cloog_Matrix_from_ppl_Constraint_System (ppl_const_Constraint_System_t pcs)
 123 {
 124   CloogMatrix *matrix;
 125   ppl_Constraint_System_const_iterator_t cit, end;
 126   ppl_dimension_type dim;
 127   int rows;
 128   int row = 0;
 129
 130   rows = ppl_Constrain_System_number_of_constraints (pcs);
 131   ppl_Constraint_System_space_dimension (pcs, &dim);
 132   matrix = cloog_matrix_alloc (rows, dim + 2);
 133   ppl_new_Constraint_System_const_iterator (&cit);
 134   ppl_new_Constraint_System_const_iterator (&end);
 135
 136   for (ppl_Constraint_System_begin (pcs, cit),
 137        ppl_Constraint_System_end (pcs, end);
 138        !ppl_Constraint_System_const_iterator_equal_test (cit, end);
 139        ppl_Constraint_System_const_iterator_increment (cit))
 140     {
 141       ppl_const_Constraint_t c;
 142       ppl_Constraint_System_const_iterator_dereference (cit, &c);
 143       insert_constraint_into_matrix (matrix, row, c);
 144       row++;
 145     }
 146
 147   ppl_delete_Constraint_System_const_iterator (cit);
 148   ppl_delete_Constraint_System_const_iterator (end);
 149
 150   return matrix;
 151 }
 152
 153 /* Creates a CloogMatrix from polyhedron PH.  */
 154
 155 CloogMatrix *
 156 new_Cloog_Matrix_from_ppl_Polyhedron (ppl_const_Polyhedron_t ph)
 157 {
 158   ppl_const_Constraint_System_t pcs;
 159   CloogMatrix *res;
 160
 161   ppl_Polyhedron_get_constraints (ph, &pcs);
 162   res = new_Cloog_Matrix_from_ppl_Constraint_System (pcs);
 163
 164   return res;
 165 }
 166
 167 /* Translates row ROW of the CloogMatrix MATRIX to a PPL Constraint.  */
 168
 169 static ppl_Constraint_t
 170 cloog_matrix_to_ppl_constraint (CloogMatrix *matrix, int row)
 171 {
 172   int j;
 173   ppl_Constraint_t cstr;
 174   ppl_Coefficient_t coef;
 175   ppl_Linear_Expression_t expr;
 176   ppl_dimension_type dim = matrix->NbColumns - 2;
 177
 178   ppl_new_Coefficient (&coef);
 179   ppl_new_Linear_Expression_with_dimension (&expr, dim);
 180
 181   /* Cast needed to remove warning that is generated as CLooG isl
 182      is using an unsigned int for NbColumns and CLooG PPL is
 183      using a signed int for NBColumns.  */
 184   for (j = 1; j < (int)matrix->NbColumns - 1; j++)
 185     {
 186       ppl_assign_Coefficient_from_mpz_t (coef, matrix->p[row][j]);
 187       ppl_Linear_Expression_add_to_coefficient (expr, j - 1, coef);
 188     }
 189
 190   ppl_assign_Coefficient_from_mpz_t (coef,
 191                                      matrix->p[row][matrix->NbColumns - 1]);
 192   ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
 193   ppl_delete_Coefficient (coef);
 194
 195   if (mpz_sgn (matrix->p[row][0]) == 0)
 196     ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
 197   else
 198     ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
 199
 200   ppl_delete_Linear_Expression (expr);
 201   return cstr;
 202 }
 203
 204 /* Creates a PPL constraint system from MATRIX.  */
 205
 206 static void
 207 new_Constraint_System_from_Cloog_Matrix (ppl_Constraint_System_t *pcs,
 208                                          CloogMatrix *matrix)
 209 {
 210   int i;
 211
 212   ppl_new_Constraint_System (pcs);
 213
 214   /* Cast needed to remove warning that is generated as CLooG isl
 215      is using an unsigned int for NbColumns and CLooG PPL is
 216      using a signed int for NBColumns.  */
 217   for (i = 0; i < (int)matrix->NbRows; i++)
 218     {
 219       ppl_Constraint_t c = cloog_matrix_to_ppl_constraint (matrix, i);
 220       ppl_Constraint_System_insert_Constraint (*pcs, c);
 221       ppl_delete_Constraint (c);
 222     }
 223 }
 224
 225 /* Creates a PPL Polyhedron from MATRIX.  */
 226
 227 void
 228 new_C_Polyhedron_from_Cloog_Matrix (ppl_Polyhedron_t *ph,
 229                                       CloogMatrix *matrix)
 230 {
 231   ppl_Constraint_System_t cs;
 232   new_Constraint_System_from_Cloog_Matrix (&cs, matrix);
 233   ppl_new_C_Polyhedron_recycle_Constraint_System (ph, cs);
 234 }
 235
 236 /* Creates a CloogDomain from polyhedron PH.  */
 237
 238 CloogDomain *
 239 new_Cloog_Domain_from_ppl_Polyhedron (ppl_const_Polyhedron_t ph, int nb_params,
 240                                       CloogState *state ATTRIBUTE_UNUSED)
 241 {
 242   CloogMatrix *mat = new_Cloog_Matrix_from_ppl_Polyhedron (ph);
 243   CloogDomain *res = cloog_domain_from_cloog_matrix (state, mat, nb_params);
 244   cloog_matrix_free (mat);
 245   return res;
 246 }
 247
 248 /* Create a CloogScattering from polyhedron PH.  */
 249
 250 CloogScattering *
 251 new_Cloog_Scattering_from_ppl_Polyhedron (ppl_const_Polyhedron_t ph,
 252                                           int nb_params ATTRIBUTE_UNUSED,
 253                                           int nb_scatt ATTRIBUTE_UNUSED,
 254                                           CloogState *state ATTRIBUTE_UNUSED)
 255 {
 256 #ifdef CLOOG_ORG
 257   CloogMatrix *mat = new_Cloog_Matrix_from_ppl_Polyhedron (ph);
 258   CloogScattering *res = cloog_scattering_from_cloog_matrix (state, mat,
 259                                                              nb_scatt,
 260                                                              nb_params);
 261
 262   cloog_matrix_free (mat);
 263   return res;
 264 #else
 265   return new_Cloog_Domain_from_ppl_Polyhedron (ph, nb_params, state);
 266 #endif
 267 }
 268
 269 /* Creates a CloogDomain from a pointset powerset PS.  */
 270
 271 CloogDomain *
 272 new_Cloog_Domain_from_ppl_Pointset_Powerset
 273   (ppl_Pointset_Powerset_C_Polyhedron_t ps, int nb_params,
 274    CloogState *state ATTRIBUTE_UNUSED)
 275 {
 276   CloogDomain *res = NULL;
 277   ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
 278
 279   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
 280   ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
 281
 282   for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
 283        ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
 284        !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
 285        ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
 286     {
 287       ppl_const_Polyhedron_t ph;
 288       CloogDomain *tmp;
 289
 290       ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
 291       tmp = new_Cloog_Domain_from_ppl_Polyhedron (ph, nb_params, state);
 292
 293       if (res == NULL)
 294         res = tmp;
 295       else
 296         res = cloog_domain_union (res, tmp);
 297     }
 298
 299   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
 300   ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
 301
 302   gcc_assert (res != NULL);
 303
 304   return res;
 305 }
 306
 307 /* Print to FILE the matrix MAT in OpenScop format.  OUTPUT is the number
 308    of output dimensions, INPUT is the number of input dimensions, LOCALS
 309    is the number of existentially quantified variables and PARAMS is the
 310    number of parameters.  */
 311
 312 static void
 313 openscop_print_cloog_matrix (FILE *file, CloogMatrix *mat,
 314                              int output, int input, int locals,
 315                              int params)
 316 {
 317   int i, j;
 318
 319   fprintf (file, "%d %d %d %d %d %d \n", cloog_matrix_nrows (mat),
 320            cloog_matrix_ncolumns (mat), output, input, locals, params);
 321
 322   for (i = 0; i < cloog_matrix_nrows (mat); i++)
 323     {
 324       for (j = 0; j < cloog_matrix_ncolumns (mat); j++)
 325         if (j == 0)
 326           fprintf (file, "%ld ", mpz_get_si (mat->p[i][j]));
 327         else
 328           fprintf (file, "%6ld ", mpz_get_si (mat->p[i][j]));
 329
 330       fprintf (file, "\n");
 331     }
 332 }
 333
 334 /* Print to FILE the polyhedron PH in OpenScop format.  OUTPUT is the number
 335    of output dimensions, INPUT is the number of input dimensions, LOCALS is
 336    the number of existentially quantified variables and PARAMS is the number
 337    of parameters.  */
 338
 339 void
 340 openscop_print_polyhedron_matrix (FILE *file, ppl_const_Polyhedron_t ph,
 341                                   int output, int input, int locals,
 342                                   int params)
 343 {
 344   CloogMatrix *mat = new_Cloog_Matrix_from_ppl_Polyhedron (ph);
 345   openscop_print_cloog_matrix (file, mat, output, input, locals, params);
 346   cloog_matrix_free (mat);
 347 }
 348
 349 /* Read from FILE a matrix in OpenScop format.  OUTPUT is the number of
 350    output dimensions, INPUT is the number of input dimensions, LOCALS
 351    is the number of existentially quantified variables and PARAMS is the
 352    number of parameters.  */
 353
 354 static CloogMatrix *
 355 openscop_read_cloog_matrix (FILE *file, int *output, int *input, int *locals,
 356                             int *params)
 357 {
 358   int nb_rows, nb_cols, i, j;
 359   CloogMatrix *mat;
 360   int *openscop_matrix_header, *matrix_line;
 361
 362   openscop_matrix_header = openscop_read_N_int (file, 6);
 363
 364   nb_rows = openscop_matrix_header[0];
 365   nb_cols = openscop_matrix_header[1];
 366   *output = openscop_matrix_header[2];
 367   *input = openscop_matrix_header[3];
 368   *locals = openscop_matrix_header[4];
 369   *params = openscop_matrix_header[5];
 370
 371   free (openscop_matrix_header);
 372
 373   if (nb_rows == 0 || nb_cols == 0)
 374     return NULL;
 375
 376   mat = cloog_matrix_alloc (nb_rows, nb_cols);
 377   mat->NbRows = nb_rows;
 378   mat->NbColumns = nb_cols;
 379
 380   for (i = 0; i < nb_rows; i++)
 381     {
 382       matrix_line = openscop_read_N_int (file, nb_cols);
 383
 384       for (j = 0; j < nb_cols; j++)
 385         mpz_set_si (mat->p[i][j], matrix_line[j]);
 386     }
 387
 388   return mat;
 389 }
 390
 391 /* Read from FILE the polyhedron PH in OpenScop format.  OUTPUT is the number
 392    of output dimensions, INPUT is the number of input dimensions, LOCALS is
 393    the number of existentially quantified variables and PARAMS is the number
 394    of parameters.  */
 395
 396 void
 397 openscop_read_polyhedron_matrix (FILE *file, ppl_Polyhedron_t *ph,
 398                                  int *output, int *input, int *locals,
 399                                  int *params)
 400 {
 401   CloogMatrix *mat;
 402
 403   mat = openscop_read_cloog_matrix (file, output, input, locals, params);
 404
 405   if (!mat)
 406     *ph = NULL;
 407   else
 408     {
 409       new_C_Polyhedron_from_Cloog_Matrix (ph, mat);
 410       cloog_matrix_free (mat);
 411     }
 412 }
 413
 414 #endif