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 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify 9it under the terms of the GNU General Public License as published by 10the Free Software Foundation; either version 3, or (at your option) 11any later version. 12 13GCC is distributed in the hope that it will be useful, 14but WITHOUT ANY WARRANTY; without even the implied warranty of 15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16GNU General Public License for more details. 17 18You should have received a copy of the GNU General Public License 19along 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#include "ppl_c.h" 30#include "cloog/cloog.h" 31#include "graphite-ppl.h" 32 33/* Translates row ROW of the CloogMatrix MATRIX to a PPL Constraint. */ 34 35static ppl_Constraint_t 36cloog_matrix_to_ppl_constraint (CloogMatrix *matrix, int row) 37{ 38 int j; 39 ppl_Constraint_t cstr; 40 ppl_Coefficient_t coef; 41 ppl_Linear_Expression_t expr; 42 ppl_dimension_type dim = matrix->NbColumns - 2; 43 44 ppl_new_Coefficient (&coef); 45 ppl_new_Linear_Expression_with_dimension (&expr, dim); 46 47 for (j = 1; j < matrix->NbColumns - 1; j++) 48 { 49 ppl_assign_Coefficient_from_mpz_t (coef, matrix->p[row][j]); 50 ppl_Linear_Expression_add_to_coefficient (expr, j - 1, coef); 51 } 52 53 ppl_assign_Coefficient_from_mpz_t (coef, 54 matrix->p[row][matrix->NbColumns - 1]); 55 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef); 56 ppl_delete_Coefficient (coef); 57 58 if (value_zero_p (matrix->p[row][0])) 59 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL); 60 else 61 ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 62 63 ppl_delete_Linear_Expression (expr); 64 return cstr; 65} 66 67/* Creates a PPL constraint system from MATRIX. */ 68 69static void 70new_Constraint_System_from_Cloog_Matrix (ppl_Constraint_System_t *pcs, 71 CloogMatrix *matrix) 72{ 73 int i; 74 75 ppl_new_Constraint_System (pcs); 76 77 for (i = 0; i < matrix->NbRows; i++) 78 { 79 ppl_Constraint_t c = cloog_matrix_to_ppl_constraint (matrix, i); 80 ppl_Constraint_System_insert_Constraint (*pcs, c); 81 ppl_delete_Constraint (c); 82 } 83} 84 85/* Creates a PPL Polyhedron from MATRIX. */ 86 87void 88new_C_Polyhedron_from_Cloog_Matrix (ppl_Polyhedron_t *ph, 89 CloogMatrix *matrix) 90{ 91 ppl_Constraint_System_t cs; 92 new_Constraint_System_from_Cloog_Matrix (&cs, matrix); 93 ppl_new_C_Polyhedron_recycle_Constraint_System (ph, cs); 94} 95 96/* Counts the number of constraints in PCS. */ 97 98static int 99ppl_Constrain_System_number_of_constraints (ppl_const_Constraint_System_t pcs) 100{ 101 ppl_Constraint_System_const_iterator_t cit, end; 102 int num = 0; 103 104 ppl_new_Constraint_System_const_iterator (&cit); 105 ppl_new_Constraint_System_const_iterator (&end); 106 107 for (ppl_Constraint_System_begin (pcs, cit), 108 ppl_Constraint_System_end (pcs, end); 109 !ppl_Constraint_System_const_iterator_equal_test (cit, end); 110 ppl_Constraint_System_const_iterator_increment (cit)) 111 num++; 112 113 ppl_delete_Constraint_System_const_iterator (cit); 114 ppl_delete_Constraint_System_const_iterator (end); 115 return num; 116} 117 118static void 119oppose_constraint (CloogMatrix *m, int row) 120{ 121 int k; 122 123 /* Do not oppose the first column: it is the eq/ineq one. */ 124 for (k = 1; k < m->NbColumns; k++) 125 value_oppose (m->p[row][k], m->p[row][k]); 126} 127 128/* Inserts constraint CSTR at row ROW of matrix M. */ 129 130void 131insert_constraint_into_matrix (CloogMatrix *m, int row, 132 ppl_const_Constraint_t cstr) 133{ 134 ppl_Coefficient_t c; 135 ppl_dimension_type i, dim, nb_cols = m->NbColumns; 136 137 ppl_Constraint_space_dimension (cstr, &dim); 138 ppl_new_Coefficient (&c); 139 140 for (i = 0; i < dim; i++) 141 { 142 ppl_Constraint_coefficient (cstr, i, c); 143 ppl_Coefficient_to_mpz_t (c, m->p[row][i + 1]); 144 } 145 146 for (i = dim; i < nb_cols - 1; i++) 147 value_set_si (m->p[row][i + 1], 0); 148 149 ppl_Constraint_inhomogeneous_term (cstr, c); 150 ppl_Coefficient_to_mpz_t (c, m->p[row][nb_cols - 1]); 151 value_set_si (m->p[row][0], 1); 152 153 switch (ppl_Constraint_type (cstr)) 154 { 155 case PPL_CONSTRAINT_TYPE_LESS_THAN: 156 oppose_constraint (m, row); 157 case PPL_CONSTRAINT_TYPE_GREATER_THAN: 158 value_sub_int (m->p[row][nb_cols - 1], 159 m->p[row][nb_cols - 1], 1); 160 break; 161 162 case PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL: 163 oppose_constraint (m, row); 164 case PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL: 165 break; 166 167 case PPL_CONSTRAINT_TYPE_EQUAL: 168 value_set_si (m->p[row][0], 0); 169 break; 170 171 default: 172 /* Not yet implemented. */ 173 gcc_unreachable(); 174 } 175 176 ppl_delete_Coefficient (c); 177} 178 179/* Creates a CloogMatrix from constraint system PCS. */ 180 181static CloogMatrix * 182new_Cloog_Matrix_from_ppl_Constraint_System (ppl_const_Constraint_System_t pcs) 183{ 184 CloogMatrix *matrix; 185 ppl_Constraint_System_const_iterator_t cit, end; 186 ppl_dimension_type dim; 187 int rows; 188 int row = 0; 189 190 rows = ppl_Constrain_System_number_of_constraints (pcs); 191 ppl_Constraint_System_space_dimension (pcs, &dim); 192 matrix = cloog_matrix_alloc (rows, dim + 2); 193 ppl_new_Constraint_System_const_iterator (&cit); 194 ppl_new_Constraint_System_const_iterator (&end); 195 196 for (ppl_Constraint_System_begin (pcs, cit), 197 ppl_Constraint_System_end (pcs, end); 198 !ppl_Constraint_System_const_iterator_equal_test (cit, end); 199 ppl_Constraint_System_const_iterator_increment (cit)) 200 { 201 ppl_const_Constraint_t c; 202 ppl_Constraint_System_const_iterator_dereference (cit, &c); 203 insert_constraint_into_matrix (matrix, row, c); 204 row++; 205 } 206 207 ppl_delete_Constraint_System_const_iterator (cit); 208 ppl_delete_Constraint_System_const_iterator (end); 209 210 return matrix; 211} 212 213/* Creates a CloogMatrix from polyhedron PH. */ 214 215CloogMatrix * 216new_Cloog_Matrix_from_ppl_Polyhedron (ppl_const_Polyhedron_t ph) 217{ 218 ppl_const_Constraint_System_t pcs; 219 CloogMatrix *res; 220 221 ppl_Polyhedron_get_constraints (ph, &pcs); 222 res = new_Cloog_Matrix_from_ppl_Constraint_System (pcs); 223 224 return res; 225} 226 227/* Creates a CloogDomain from polyhedron PH. */ 228 229CloogDomain * 230new_Cloog_Domain_from_ppl_Polyhedron (ppl_const_Polyhedron_t ph) 231{ 232 CloogMatrix *mat = new_Cloog_Matrix_from_ppl_Polyhedron (ph); 233 CloogDomain *res = cloog_domain_matrix2domain (mat); 234 cloog_matrix_free (mat); 235 return res; 236} 237 238/* Creates a CloogDomain from a pointset powerset PS. */ 239 240CloogDomain * 241new_Cloog_Domain_from_ppl_Pointset_Powerset ( 242 ppl_Pointset_Powerset_C_Polyhedron_t ps) 243{ 244 CloogDomain *res = NULL; 245 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end; 246 247 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it); 248 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end); 249 250 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it), 251 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end); 252 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end); 253 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it)) 254 { 255 ppl_const_Polyhedron_t ph; 256 CloogDomain *tmp; 257 258 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph); 259 tmp = new_Cloog_Domain_from_ppl_Polyhedron (ph); 260 261 if (res == NULL) 262 res = tmp; 263 else 264 res = cloog_domain_union (res, tmp); 265 } 266 267 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it); 268 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end); 269 270 gcc_assert (res != NULL); 271 272 return res; 273} 274 275/* Set the inhomogeneous term of E to X. */ 276 277void 278ppl_set_inhomogeneous_gmp (ppl_Linear_Expression_t e, Value x) 279{ 280 Value v0, v1; 281 ppl_Coefficient_t c; 282 283 value_init (v0); 284 value_init (v1); 285 ppl_new_Coefficient (&c); 286 287 ppl_Linear_Expression_inhomogeneous_term (e, c); 288 ppl_Coefficient_to_mpz_t (c, v1); 289 value_oppose (v1, v1); 290 value_assign (v0, x); 291 value_addto (v0, v0, v1); 292 ppl_assign_Coefficient_from_mpz_t (c, v0); 293 ppl_Linear_Expression_add_to_inhomogeneous (e, c); 294 295 value_clear (v0); 296 value_clear (v1); 297 ppl_delete_Coefficient (c); 298} 299 300/* Set E[I] to X. */ 301 302void 303ppl_set_coef_gmp (ppl_Linear_Expression_t e, ppl_dimension_type i, Value x) 304{ 305 Value v0, v1; 306 ppl_Coefficient_t c; 307 308 value_init (v0); 309 value_init (v1); 310 ppl_new_Coefficient (&c); 311 312 ppl_Linear_Expression_coefficient (e, i, c); 313 ppl_Coefficient_to_mpz_t (c, v1); 314 value_oppose (v1, v1); 315 value_assign (v0, x); 316 value_addto (v0, v0, v1); 317 ppl_assign_Coefficient_from_mpz_t (c, v0); 318 ppl_Linear_Expression_add_to_coefficient (e, i, c); 319 320 value_clear (v0); 321 value_clear (v1); 322 ppl_delete_Coefficient (c); 323} 324 325/* Insert after X NB_NEW_DIMS empty dimensions into PH. 326 327 With x = 3 and nb_new_dims = 4 328 329 | d0 d1 d2 d3 d4 330 331 is transformed to 332 333 | d0 d1 d2 x0 x1 x2 x3 d3 d4 334 335 | map = {0, 1, 2, 7, 8, 3, 4, 5, 6} 336*/ 337 338void 339ppl_insert_dimensions_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ph, int x, 340 int nb_new_dims) 341{ 342 ppl_dimension_type i, dim; 343 ppl_dimension_type *map; 344 ppl_dimension_type x_ppl, nb_new_dims_ppl; 345 346 x_ppl = (ppl_dimension_type) x; 347 nb_new_dims_ppl = (ppl_dimension_type) nb_new_dims; 348 349 ppl_Pointset_Powerset_C_Polyhedron_space_dimension (ph, &dim); 350 ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed (ph, nb_new_dims); 351 352 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim + nb_new_dims); 353 354 for (i = 0; i < x_ppl; i++) 355 map[i] = i; 356 357 for (i = x_ppl; i < x_ppl + nb_new_dims_ppl; i++) 358 map[dim + i - x_ppl] = i; 359 360 for (i = x_ppl + nb_new_dims_ppl; i < dim + nb_new_dims_ppl; i++) 361 map[i - nb_new_dims_ppl] = i; 362 363 ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (ph, map, dim + nb_new_dims); 364 free (map); 365} 366 367/* Insert after X NB_NEW_DIMS empty dimensions into PH. 368 369 With x = 3 and nb_new_dims = 4 370 371 | d0 d1 d2 d3 d4 372 373 is transformed to 374 375 | d0 d1 d2 x0 x1 x2 x3 d3 d4 376 377 | map = {0, 1, 2, 7, 8, 3, 4, 5, 6} 378*/ 379 380void 381ppl_insert_dimensions (ppl_Polyhedron_t ph, int x, 382 int nb_new_dims) 383{ 384 ppl_dimension_type i, dim; 385 ppl_dimension_type *map; 386 ppl_dimension_type x_ppl, nb_new_dims_ppl; 387 388 x_ppl = (ppl_dimension_type) x; 389 nb_new_dims_ppl = (ppl_dimension_type) nb_new_dims; 390 391 ppl_Polyhedron_space_dimension (ph, &dim); 392 ppl_Polyhedron_add_space_dimensions_and_embed (ph, nb_new_dims); 393 394 map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim + nb_new_dims); 395 396 for (i = 0; i < x_ppl; i++) 397 map[i] = i; 398 399 for (i = x_ppl; i < x_ppl + nb_new_dims_ppl; i++) 400 map[dim + i - x_ppl] = i; 401 402 for (i = x_ppl + nb_new_dims_ppl; i < dim + nb_new_dims_ppl; i++) 403 map[i - nb_new_dims_ppl] = i; 404 405 ppl_Polyhedron_map_space_dimensions (ph, map, dim + nb_new_dims); 406 free (map); 407} 408 409/* Based on the original polyhedron PH, returns a new polyhedron with 410 an extra dimension placed at position LOOP + 1 that slices the 411 dimension LOOP into strips of size STRIDE. */ 412 413ppl_Polyhedron_t 414ppl_strip_loop (ppl_Polyhedron_t ph, ppl_dimension_type loop, int stride) 415{ 416 ppl_const_Constraint_System_t pcs; 417 ppl_Constraint_System_const_iterator_t cit, end; 418 ppl_const_Constraint_t cstr; 419 ppl_Linear_Expression_t expr; 420 int v; 421 ppl_dimension_type dim; 422 ppl_Polyhedron_t res; 423 ppl_Coefficient_t c; 424 Value val; 425 426 value_init (val); 427 ppl_new_Coefficient (&c); 428 429 ppl_Polyhedron_space_dimension (ph, &dim); 430 ppl_Polyhedron_get_constraints (ph, &pcs); 431 432 /* Start from a copy of the constraints. */ 433 ppl_new_C_Polyhedron_from_space_dimension (&res, dim + 1, 0); 434 ppl_Polyhedron_add_constraints (res, pcs); 435 436 /* Add an empty dimension for the strip loop. */ 437 ppl_insert_dimensions (res, loop, 1); 438 439 /* Identify the constraints that define the lower and upper bounds 440 of the strip-mined loop, and add them to the strip loop. */ 441 { 442 ppl_Polyhedron_t tmp; 443 444 ppl_new_C_Polyhedron_from_space_dimension (&tmp, dim + 1, 0); 445 ppl_new_Constraint_System_const_iterator (&cit); 446 ppl_new_Constraint_System_const_iterator (&end); 447 448 for (ppl_Constraint_System_begin (pcs, cit), 449 ppl_Constraint_System_end (pcs, end); 450 !ppl_Constraint_System_const_iterator_equal_test (cit, end); 451 ppl_Constraint_System_const_iterator_increment (cit)) 452 { 453 ppl_Constraint_System_const_iterator_dereference (cit, &cstr); 454 ppl_new_Linear_Expression_from_Constraint (&expr, cstr); 455 ppl_Linear_Expression_coefficient (expr, loop, c); 456 ppl_delete_Linear_Expression (expr); 457 ppl_Coefficient_to_mpz_t (c, val); 458 v = value_get_si (val); 459 460 if (0 < v || v < 0) 461 ppl_Polyhedron_add_constraint (tmp, cstr); 462 } 463 ppl_delete_Constraint_System_const_iterator (cit); 464 ppl_delete_Constraint_System_const_iterator (end); 465 466 ppl_insert_dimensions (tmp, loop + 1, 1); 467 ppl_Polyhedron_get_constraints (tmp, &pcs); 468 ppl_Polyhedron_add_constraints (res, pcs); 469 ppl_delete_Polyhedron (tmp); 470 } 471 472 /* Lower bound of a tile starts at "stride * outer_iv". */ 473 { 474 ppl_Constraint_t new_cstr; 475 ppl_new_Linear_Expression_with_dimension (&expr, dim + 1); 476 477 ppl_set_coef (expr, loop + 1, 1); 478 ppl_set_coef (expr, loop, -1 * stride); 479 480 ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 481 ppl_delete_Linear_Expression (expr); 482 ppl_Polyhedron_add_constraint (res, new_cstr); 483 ppl_delete_Constraint (new_cstr); 484 } 485 486 /* Upper bound of a tile stops at "stride * outer_iv + stride - 1", 487 or at the old upper bound that is not modified. */ 488 { 489 ppl_Constraint_t new_cstr; 490 ppl_new_Linear_Expression_with_dimension (&expr, dim + 1); 491 492 ppl_set_coef (expr, loop + 1, -1); 493 ppl_set_coef (expr, loop, stride); 494 ppl_set_inhomogeneous (expr, stride - 1); 495 496 ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL); 497 ppl_delete_Linear_Expression (expr); 498 ppl_Polyhedron_add_constraint (res, new_cstr); 499 ppl_delete_Constraint (new_cstr); 500 } 501 502 value_clear (val); 503 ppl_delete_Coefficient (c); 504 return res; 505} 506 507/* Lexicographically compares two linear expressions A and B and 508 returns negative when A < B, 0 when A == B and positive when A > B. */ 509 510int 511ppl_lexico_compare_linear_expressions (ppl_Linear_Expression_t a, 512 ppl_Linear_Expression_t b) 513{ 514 ppl_dimension_type min_length, length1, length2; 515 ppl_dimension_type i; 516 ppl_Coefficient_t c; 517 int res; 518 Value va, vb; 519 520 ppl_Linear_Expression_space_dimension (a, &length1); 521 ppl_Linear_Expression_space_dimension (b, &length2); 522 ppl_new_Coefficient (&c); 523 value_init (va); 524 value_init (vb); 525 526 if (length1 < length2) 527 min_length = length1; 528 else 529 min_length = length2; 530 531 for (i = 0; i < min_length; i++) 532 { 533 ppl_Linear_Expression_coefficient (a, i, c); 534 ppl_Coefficient_to_mpz_t (c, va); 535 ppl_Linear_Expression_coefficient (b, i, c); 536 ppl_Coefficient_to_mpz_t (c, vb); 537 res = value_compare (va, vb); 538 539 if (res == 0) 540 continue; 541 542 value_clear (va); 543 value_clear (vb); 544 ppl_delete_Coefficient (c); 545 return res; 546 } 547 548 value_clear (va); 549 value_clear (vb); 550 ppl_delete_Coefficient (c); 551 return length1 - length2; 552} 553 554/* Print to FILE the polyhedron PH under its PolyLib matrix form. */ 555 556void 557ppl_print_polyhedron_matrix (FILE *file, ppl_const_Polyhedron_t ph) 558{ 559 CloogMatrix *mat = new_Cloog_Matrix_from_ppl_Polyhedron (ph); 560 cloog_matrix_print (file, mat); 561 cloog_matrix_free (mat); 562} 563 564/* Print to FILE the linear expression LE. */ 565 566void 567ppl_print_linear_expr (FILE *file, ppl_Linear_Expression_t le) 568{ 569 ppl_Constraint_t c; 570 ppl_Polyhedron_t pol; 571 ppl_dimension_type dim; 572 573 ppl_Linear_Expression_space_dimension (le, &dim); 574 ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0); 575 ppl_new_Constraint (&c, le, PPL_CONSTRAINT_TYPE_EQUAL); 576 ppl_Polyhedron_add_constraint (pol, c); 577 ppl_print_polyhedron_matrix (file, pol); 578} 579 580/* Print to STDERR the linear expression LE. */ 581 582void 583debug_ppl_linear_expr (ppl_Linear_Expression_t le) 584{ 585 ppl_print_linear_expr (stderr, le); 586} 587 588/* Print to FILE the powerset PS in its PolyLib matrix form. */ 589 590void 591ppl_print_powerset_matrix (FILE *file, 592 ppl_Pointset_Powerset_C_Polyhedron_t ps) 593{ 594 size_t nb_disjuncts; 595 ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end; 596 597 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it); 598 ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end); 599 600 ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts); 601 fprintf (file, "%d\n", (int) nb_disjuncts); 602 603 for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it), 604 ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end); 605 !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end); 606 ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it)) 607 { 608 ppl_const_Polyhedron_t ph; 609 610 ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph); 611 ppl_print_polyhedron_matrix (file, ph); 612 } 613 614 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it); 615 ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end); 616} 617 618/* Print to STDERR the polyhedron PH under its PolyLib matrix form. */ 619 620void 621debug_ppl_polyhedron_matrix (ppl_Polyhedron_t ph) 622{ 623 ppl_print_polyhedron_matrix (stderr, ph); 624} 625 626/* Print to STDERR the powerset PS in its PolyLib matrix form. */ 627 628void 629debug_ppl_powerset_matrix (ppl_Pointset_Powerset_C_Polyhedron_t ps) 630{ 631 ppl_print_powerset_matrix (stderr, ps); 632} 633 634/* Read from FILE a polyhedron under PolyLib matrix form and return a 635 PPL polyhedron object. */ 636 637void 638ppl_read_polyhedron_matrix (ppl_Polyhedron_t *ph, FILE *file) 639{ 640 CloogMatrix *mat = cloog_matrix_read (file); 641 new_C_Polyhedron_from_Cloog_Matrix (ph, mat); 642 cloog_matrix_free (mat); 643} 644 645/* Return in RES the maximum of the linear expression LE on the 646 pointset powerset of polyhedra PS. */ 647 648void 649ppl_max_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps, 650 ppl_Linear_Expression_t le, Value res) 651{ 652 ppl_Coefficient_t num, denom; 653 Value dv, nv; 654 int maximum, err; 655 656 value_init (nv); 657 value_init (dv); 658 ppl_new_Coefficient (&num); 659 ppl_new_Coefficient (&denom); 660 err = ppl_Pointset_Powerset_C_Polyhedron_maximize (ps, le, num, denom, &maximum); 661 662 if (err > 0) 663 { 664 ppl_Coefficient_to_mpz_t (num, nv); 665 ppl_Coefficient_to_mpz_t (denom, dv); 666 gcc_assert (value_notzero_p (dv)); 667 value_division (res, nv, dv); 668 } 669 670 value_clear (nv); 671 value_clear (dv); 672 ppl_delete_Coefficient (num); 673 ppl_delete_Coefficient (denom); 674} 675 676/* Return in RES the maximum of the linear expression LE on the 677 polyhedron POL. */ 678 679void 680ppl_min_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps, 681 ppl_Linear_Expression_t le, Value res) 682{ 683 ppl_Coefficient_t num, denom; 684 Value dv, nv; 685 int minimum, err; 686 687 value_init (nv); 688 value_init (dv); 689 ppl_new_Coefficient (&num); 690 ppl_new_Coefficient (&denom); 691 err = ppl_Pointset_Powerset_C_Polyhedron_minimize (ps, le, num, denom, &minimum); 692 693 if (err > 0) 694 { 695 ppl_Coefficient_to_mpz_t (num, nv); 696 ppl_Coefficient_to_mpz_t (denom, dv); 697 gcc_assert (value_notzero_p (dv)); 698 value_division (res, nv, dv); 699 } 700 701 value_clear (nv); 702 value_clear (dv); 703 ppl_delete_Coefficient (num); 704 ppl_delete_Coefficient (denom); 705} 706 707/* Builds a constraint in dimension DIM relating dimensions POS1 to 708 POS2 as "POS1 - POS2 + C CSTR_TYPE 0" */ 709 710ppl_Constraint_t 711ppl_build_relation (int dim, int pos1, int pos2, int c, 712 enum ppl_enum_Constraint_Type cstr_type) 713{ 714 ppl_Linear_Expression_t expr; 715 ppl_Constraint_t cstr; 716 ppl_Coefficient_t coef; 717 Value v, v_op, v_c; 718 719 value_init (v); 720 value_init (v_op); 721 value_init (v_c); 722 723 value_set_si (v, 1); 724 value_set_si (v_op, -1); 725 value_set_si (v_c, c); 726 727 ppl_new_Coefficient (&coef); 728 ppl_new_Linear_Expression_with_dimension (&expr, dim); 729 730 ppl_assign_Coefficient_from_mpz_t (coef, v); 731 ppl_Linear_Expression_add_to_coefficient (expr, pos1, coef); 732 ppl_assign_Coefficient_from_mpz_t (coef, v_op); 733 ppl_Linear_Expression_add_to_coefficient (expr, pos2, coef); 734 ppl_assign_Coefficient_from_mpz_t (coef, v_c); 735 ppl_Linear_Expression_add_to_inhomogeneous (expr, coef); 736 737 ppl_new_Constraint (&cstr, expr, cstr_type); 738 739 ppl_delete_Linear_Expression (expr); 740 ppl_delete_Coefficient (coef); 741 value_clear (v); 742 value_clear (v_op); 743 value_clear (v_c); 744 745 return cstr; 746} 747 748#endif 749