1 /* Gimple Represented as Polyhedra. 2 Copyright (C) 2009, 2010 Free Software Foundation, Inc. 3 Contributed by Sebastian Pop <sebastian.pop@amd.com> 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 "graphite-cloog-util.h" 30 #include "graphite-ppl.h" 31 32 /* Set the inhomogeneous term of E to X. */ 33 34 void 35 ppl_set_inhomogeneous_gmp (ppl_Linear_Expression_t e, mpz_t x) 36 { 37 mpz_t v0, v1; 38 ppl_Coefficient_t c; 39 40 mpz_init (v0); 41 mpz_init (v1); 42 ppl_new_Coefficient (&c); 43 44 ppl_Linear_Expression_inhomogeneous_term (e, c); 45 ppl_Coefficient_to_mpz_t (c, v1); 46 mpz_neg (v1, v1); 47 mpz_set (v0, x); 48 mpz_add (v0, v0, v1); 49 ppl_assign_Coefficient_from_mpz_t (c, v0); 50 ppl_Linear_Expression_add_to_inhomogeneous (e, c); 51 52 mpz_clear (v0); 53 mpz_clear (v1); 54 ppl_delete_Coefficient (c); 55 } 56 57 /* Set E[I] to X. */ 58 59 void 60 ppl_set_coef_gmp (ppl_Linear_Expression_t e, ppl_dimension_type i, mpz_t x) 61 { 62 mpz_t v0, v1; 63 ppl_Coefficient_t c; 64 65 mpz_init (v0); 66 mpz_init (v1); 67 ppl_new_Coefficient (&c); 68 69 ppl_Linear_Expression_coefficient (e, i, c); 70 ppl_Coefficient_to_mpz_t (c, v1); 71 mpz_neg (v1, v1); 72 mpz_set (v0, x); 73 mpz_add (v0, v0, v1); 74 ppl_assign_Coefficient_from_mpz_t (c, v0); 75 ppl_Linear_Expression_add_to_coefficient (e, i, c); 76 77 mpz_clear (v0); 78 mpz_clear (v1); 79 ppl_delete_Coefficient (c); 80 } 81 82 /* Insert after X NB_NEW_DIMS empty dimensions into PH. 83 84 With x = 3 and nb_new_dims = 4 85 86 | d0 d1 d2 d3 d4 87 88 is transformed to 89 90 | d0 d1 d2 x0 x1 x2 x3 d3 d4 91 92 | map = {0, 1, 2, 7, 8, 3, 4, 5, 6} 93 */ 94 95 void 96 ppl_insert_dimensions_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ph, int x, 97 int nb_new_dims) 98 { 99 ppl_dimension_type i, dim; 100 ppl_dimension_type *map; 101 ppl_dimension_type x_ppl, nb_new_dims_ppl; 102 103 x_ppl = (ppl_dimension_type) x; 104 nb_new_dims_ppl = (ppl_dimension_type) nb_new_dims; 105 106 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (ph, &dim); 107 ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed (ph, nb_new_dims); 108 109 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim + nb_new_dims); 110 111 for (i = 0; i < x_ppl; i++) 112 map[i] = i; 113 114 for (i = x_ppl; i < x_ppl + nb_new_dims_ppl; i++) 115 map[dim + i - x_ppl] = i; 116 117 for (i = x_ppl + nb_new_dims_ppl; i < dim + nb_new_dims_ppl; i++) 118 map[i - nb_new_dims_ppl] = i; 119 120 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (ph, map, dim + nb_new_dims); 121 free (map); 122 } 123 124 /* Insert after X NB_NEW_DIMS empty dimensions into PH. 125 126 With x = 3 and nb_new_dims = 4 127 128 | d0 d1 d2 d3 d4 129 130 is transformed to 131 132 | d0 d1 d2 x0 x1 x2 x3 d3 d4 133 134 | map = {0, 1, 2, 7, 8, 3, 4, 5, 6} 135 */ 136 137 void 138 ppl_insert_dimensions (ppl_Polyhedron_t ph, int x, 139 int nb_new_dims) 140 { 141 ppl_dimension_type i, dim; 142 ppl_dimension_type *map; 143 ppl_dimension_type x_ppl, nb_new_dims_ppl; 144 145 x_ppl = (ppl_dimension_type) x; 146 nb_new_dims_ppl = (ppl_dimension_type) nb_new_dims; 147 148 ppl_Polyhedron_space_dimension (ph, &dim); 149 ppl_Polyhedron_add_space_dimensions_and_embed (ph, nb_new_dims); 150 151 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim + nb_new_dims); 152 153 for (i = 0; i < x_ppl; i++) 154 map[i] = i; 155 156 for (i = x_ppl; i < x_ppl + nb_new_dims_ppl; i++) 157 map[dim + i - x_ppl] = i; 158 159 for (i = x_ppl + nb_new_dims_ppl; i < dim + nb_new_dims_ppl; i++) 160 map[i - nb_new_dims_ppl] = i; 161 162 ppl_Polyhedron_map_space_dimensions (ph, map, dim + nb_new_dims); 163 free (map); 164 } 165 166 /* Based on the original polyhedron PH, returns a new polyhedron with 167 an extra dimension placed at position LOOP + 1 that slices the 168 dimension LOOP into strips of size STRIDE. */ 169 170 ppl_Polyhedron_t 171 ppl_strip_loop (ppl_Polyhedron_t ph, ppl_dimension_type loop, int stride) 172 { 173 ppl_const_Constraint_System_t pcs; 174 ppl_Constraint_System_const_iterator_t cit, end; 175 ppl_const_Constraint_t cstr; 176 ppl_Linear_Expression_t expr; 177 int v; 178 ppl_dimension_type dim; 179 ppl_Polyhedron_t res; 180 ppl_Coefficient_t c; 181 mpz_t val; 182 183 mpz_init (val); 184 ppl_new_Coefficient (&c); 185 186 ppl_Polyhedron_space_dimension (ph, &dim); 187 ppl_Polyhedron_get_constraints (ph, &pcs); 188 189 /* Start from a copy of the constraints. */ 190 ppl_new_C_Polyhedron_from_space_dimension (&res, dim + 1, 0); 191 ppl_Polyhedron_add_constraints (res, pcs); 192 193 /* Add an empty dimension for the strip loop. */ 194 ppl_insert_dimensions (res, loop, 1); 195 196 /* Identify the constraints that define the lower and upper bounds 197 of the strip-mined loop, and add them to the strip loop. */ 198 { 199 ppl_Polyhedron_t tmp; 200 201 ppl_new_C_Polyhedron_from_space_dimension (&tmp, dim + 1, 0); 202 ppl_new_Constraint_System_const_iterator (&cit); 203 ppl_new_Constraint_System_const_iterator (&end); 204 205 for (ppl_Constraint_System_begin (pcs, cit), 206 ppl_Constraint_System_end (pcs, end); 207 !ppl_Constraint_System_const_iterator_equal_test (cit, end); 208 ppl_Constraint_System_const_iterator_increment (cit)) 209 { 210 ppl_Constraint_System_const_iterator_dereference (cit, &cstr); 211 ppl_new_Linear_Expression_from_Constraint (&expr, cstr); 212 ppl_Linear_Expression_coefficient (expr, loop, c); 213 ppl_delete_Linear_Expression (expr); 214 ppl_Coefficient_to_mpz_t (c, val); 215 v = mpz_get_si (val); 216 217 if (0 < v || v < 0) 218 ppl_Polyhedron_add_constraint (tmp, cstr); 219 } 220 ppl_delete_Constraint_System_const_iterator (cit); 221 ppl_delete_Constraint_System_const_iterator (end); 222 223 ppl_insert_dimensions (tmp, loop + 1, 1); 224 ppl_Polyhedron_get_constraints (tmp, &pcs); 225 ppl_Polyhedron_add_constraints (res, pcs); 226 ppl_delete_Polyhedron (tmp); 227 } 228 229 /* Lower bound of a tile starts at "stride * outer_iv". */ 230 { 231 ppl_Constraint_t new_cstr; 232 ppl_new_Linear_Expression_with_dimension (&expr, dim + 1); 233 234 ppl_set_coef (expr, loop + 1, 1); 235 ppl_set_coef (expr, loop, -1 * stride); 236 237 ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 238 ppl_delete_Linear_Expression (expr); 239 ppl_Polyhedron_add_constraint (res, new_cstr); 240 ppl_delete_Constraint (new_cstr); 241 } 242 243 /* Upper bound of a tile stops at "stride * outer_iv + stride - 1", 244 or at the old upper bound that is not modified. */ 245 { 246 ppl_Constraint_t new_cstr; 247 ppl_new_Linear_Expression_with_dimension (&expr, dim + 1); 248 249 ppl_set_coef (expr, loop + 1, -1); 250 ppl_set_coef (expr, loop, stride); 251 ppl_set_inhomogeneous (expr, stride - 1); 252 253 ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 254 ppl_delete_Linear_Expression (expr); 255 ppl_Polyhedron_add_constraint (res, new_cstr); 256 ppl_delete_Constraint (new_cstr); 257 } 258 259 mpz_clear (val); 260 ppl_delete_Coefficient (c); 261 return res; 262 } 263 264 /* Lexicographically compares two linear expressions A and B and 265 returns negative when A < B, 0 when A == B and positive when A > B. */ 266 267 int 268 ppl_lexico_compare_linear_expressions (ppl_Linear_Expression_t a, 269 ppl_Linear_Expression_t b) 270 { 271 ppl_dimension_type min_length, length1, length2; 272 ppl_dimension_type i; 273 ppl_Coefficient_t c; 274 int res; 275 mpz_t va, vb; 276 277 ppl_Linear_Expression_space_dimension (a, &length1); 278 ppl_Linear_Expression_space_dimension (b, &length2); 279 ppl_new_Coefficient (&c); 280 mpz_init (va); 281 mpz_init (vb); 282 283 if (length1 < length2) 284 min_length = length1; 285 else 286 min_length = length2; 287 288 for (i = 0; i < min_length; i++) 289 { 290 ppl_Linear_Expression_coefficient (a, i, c); 291 ppl_Coefficient_to_mpz_t (c, va); 292 ppl_Linear_Expression_coefficient (b, i, c); 293 ppl_Coefficient_to_mpz_t (c, vb); 294 res = mpz_cmp (va, vb); 295 296 if (res == 0) 297 continue; 298 299 mpz_clear (va); 300 mpz_clear (vb); 301 ppl_delete_Coefficient (c); 302 return res; 303 } 304 305 mpz_clear (va); 306 mpz_clear (vb); 307 ppl_delete_Coefficient (c); 308 return length1 - length2; 309 } 310 311 /* Print to FILE the polyhedron PH under its PolyLib matrix form. */ 312 313 void 314 ppl_print_polyhedron_matrix (FILE *file, ppl_const_Polyhedron_t ph) 315 { 316 CloogMatrix *mat = new_Cloog_Matrix_from_ppl_Polyhedron (ph); 317 cloog_matrix_print (file, mat); 318 cloog_matrix_free (mat); 319 } 320 321 /* Print to FILE the linear expression LE. */ 322 323 void 324 ppl_print_linear_expr (FILE *file, ppl_Linear_Expression_t le) 325 { 326 ppl_Constraint_t c; 327 ppl_Polyhedron_t pol; 328 ppl_dimension_type dim; 329 330 ppl_Linear_Expression_space_dimension (le, &dim); 331 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0); 332 ppl_new_Constraint (&c, le, PPL_CONSTRAINT_TYPE_EQUAL); 333 ppl_Polyhedron_add_constraint (pol, c); 334 ppl_print_polyhedron_matrix (file, pol); 335 } 336 337 /* Print to STDERR the linear expression LE. */ 338 339 DEBUG_FUNCTION void 340 debug_ppl_linear_expr (ppl_Linear_Expression_t le) 341 { 342 ppl_print_linear_expr (stderr, le); 343 } 344 345 /* Print to FILE the powerset PS in its PolyLib matrix form. */ 346 347 void 348 ppl_print_powerset_matrix (FILE *file, 349 ppl_Pointset_Powerset_C_Polyhedron_t ps) 350 { 351 size_t nb_disjuncts; 352 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end; 353 354 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it); 355 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end); 356 357 ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts); 358 fprintf (file, "%d\n", (int) nb_disjuncts); 359 360 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it), 361 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end); 362 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end); 363 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it)) 364 { 365 ppl_const_Polyhedron_t ph; 366 367 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph); 368 ppl_print_polyhedron_matrix (file, ph); 369 } 370 371 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it); 372 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end); 373 } 374 375 /* Print to STDERR the polyhedron PH under its PolyLib matrix form. */ 376 377 DEBUG_FUNCTION void 378 debug_ppl_polyhedron_matrix (ppl_Polyhedron_t ph) 379 { 380 ppl_print_polyhedron_matrix (stderr, ph); 381 } 382 383 /* Print to STDERR the powerset PS in its PolyLib matrix form. */ 384 385 DEBUG_FUNCTION void 386 debug_ppl_powerset_matrix (ppl_Pointset_Powerset_C_Polyhedron_t ps) 387 { 388 ppl_print_powerset_matrix (stderr, ps); 389 } 390 391 /* Read from FILE a polyhedron under PolyLib matrix form and return a 392 PPL polyhedron object. */ 393 394 void 395 ppl_read_polyhedron_matrix (ppl_Polyhedron_t *ph, FILE *file) 396 { 397 CloogMatrix *mat = cloog_matrix_read (file); 398 new_C_Polyhedron_from_Cloog_Matrix (ph, mat); 399 cloog_matrix_free (mat); 400 } 401 402 /* Return in RES the maximum of the linear expression LE on the 403 pointset powerset of polyhedra PS. */ 404 405 void 406 ppl_max_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps, 407 ppl_Linear_Expression_t le, mpz_t res) 408 { 409 ppl_Coefficient_t num, denom; 410 mpz_t dv, nv; 411 int maximum, err; 412 413 mpz_init (nv); 414 mpz_init (dv); 415 ppl_new_Coefficient (&num); 416 ppl_new_Coefficient (&denom); 417 err = ppl_Pointset_Powerset_C_Polyhedron_maximize (ps, le, num, denom, &maximum); 418 419 if (err > 0) 420 { 421 ppl_Coefficient_to_mpz_t (num, nv); 422 ppl_Coefficient_to_mpz_t (denom, dv); 423 gcc_assert (mpz_sgn (dv) != 0); 424 mpz_tdiv_q (res, nv, dv); 425 } 426 427 mpz_clear (nv); 428 mpz_clear (dv); 429 ppl_delete_Coefficient (num); 430 ppl_delete_Coefficient (denom); 431 } 432 433 /* Return in RES the maximum of the linear expression LE on the 434 polyhedron POL. */ 435 436 void 437 ppl_min_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps, 438 ppl_Linear_Expression_t le, mpz_t res) 439 { 440 ppl_Coefficient_t num, denom; 441 mpz_t dv, nv; 442 int minimum, err; 443 444 mpz_init (nv); 445 mpz_init (dv); 446 ppl_new_Coefficient (&num); 447 ppl_new_Coefficient (&denom); 448 err = ppl_Pointset_Powerset_C_Polyhedron_minimize (ps, le, num, denom, &minimum); 449 450 if (err > 0) 451 { 452 ppl_Coefficient_to_mpz_t (num, nv); 453 ppl_Coefficient_to_mpz_t (denom, dv); 454 gcc_assert (mpz_sgn (dv) != 0); 455 mpz_tdiv_q (res, nv, dv); 456 } 457 458 mpz_clear (nv); 459 mpz_clear (dv); 460 ppl_delete_Coefficient (num); 461 ppl_delete_Coefficient (denom); 462 } 463 464 /* Builds a constraint in dimension DIM relating dimensions POS1 to 465 POS2 as "POS1 - POS2 + C CSTR_TYPE 0" */ 466 467 ppl_Constraint_t 468 ppl_build_relation (int dim, int pos1, int pos2, int c, 469 enum ppl_enum_Constraint_Type cstr_type) 470 { 471 ppl_Linear_Expression_t expr; 472 ppl_Constraint_t cstr; 473 ppl_Coefficient_t coef; 474 mpz_t v, v_op, v_c; 475 476 mpz_init (v); 477 mpz_init (v_op); 478 mpz_init (v_c); 479 480 mpz_set_si (v, 1); 481 mpz_set_si (v_op, -1); 482 mpz_set_si (v_c, c); 483 484 ppl_new_Coefficient (&coef); 485 ppl_new_Linear_Expression_with_dimension (&expr, dim); 486 487 ppl_assign_Coefficient_from_mpz_t (coef, v); 488 ppl_Linear_Expression_add_to_coefficient (expr, pos1, coef); 489 ppl_assign_Coefficient_from_mpz_t (coef, v_op); 490 ppl_Linear_Expression_add_to_coefficient (expr, pos2, coef); 491 ppl_assign_Coefficient_from_mpz_t (coef, v_c); 492 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef); 493 494 ppl_new_Constraint (&cstr, expr, cstr_type); 495 496 ppl_delete_Linear_Expression (expr); 497 ppl_delete_Coefficient (coef); 498 mpz_clear (v); 499 mpz_clear (v_op); 500 mpz_clear (v_c); 501 502 return cstr; 503 } 504 505 /* Print to STDERR the GMP value VAL. */ 506 507 DEBUG_FUNCTION void 508 debug_gmp_value (mpz_t val) 509 { 510 char *str = mpz_get_str (0, 10, val); 511 void (*gmp_free) (void *, size_t); 512 513 fprintf (stderr, "%s", str); 514 mp_get_memory_functions (NULL, NULL, &gmp_free); 515 (*gmp_free) (str, strlen (str) + 1); 516 } 517 518 /* Checks for integer feasibility: returns true when the powerset 519 polyhedron PS has no integer solutions. */ 520 521 bool 522 ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps) 523 { 524 ppl_PIP_Problem_t pip; 525 ppl_dimension_type d; 526 ppl_const_Constraint_System_t pcs; 527 ppl_Constraint_System_const_iterator_t first, last; 528 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end; 529 bool has_integer_solutions = false; 530 531 if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (ps)) 532 return true; 533 534 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (ps, &d); 535 ppl_new_Constraint_System_const_iterator (&first); 536 ppl_new_Constraint_System_const_iterator (&last); 537 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it); 538 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end); 539 540 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it), 541 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end); 542 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end); 543 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it)) 544 { 545 ppl_const_Polyhedron_t ph; 546 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph); 547 548 ppl_Polyhedron_get_constraints (ph, &pcs); 549 ppl_Constraint_System_begin (pcs, first); 550 ppl_Constraint_System_end (pcs, last); 551 552 ppl_new_PIP_Problem_from_constraints (&pip, d, first, last, 0, NULL); 553 has_integer_solutions |= ppl_PIP_Problem_is_satisfiable (pip); 554 555 ppl_delete_PIP_Problem (pip); 556 } 557 558 ppl_delete_Constraint_System_const_iterator (first); 559 ppl_delete_Constraint_System_const_iterator (last); 560 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it); 561 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end); 562 563 return !has_integer_solutions; 564 } 565 566 #endif 567