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