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