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 #endif