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 415