gcc/graphite-ppl.c

   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 #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
  35 static ppl_Constraint_t
  36 cloog_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
  69 static void
  70 new_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
  87 void
  88 new_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
  98 static int
  99 ppl_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
 118 static void
 119 oppose_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
 130 void
 131 insert_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
 181 static CloogMatrix *
 182 new_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
 215 CloogMatrix *
 216 new_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
 229 CloogDomain *
 230 new_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
 240 CloogDomain *
 241 new_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
 277 void
 278 ppl_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
 302 void
 303 ppl_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
 338 void
 339 ppl_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
 380 void
 381 ppl_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
 413 ppl_Polyhedron_t
 414 ppl_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
 510 int
 511 ppl_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
 556 void
 557 ppl_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
 566 void
 567 ppl_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
 582 void
 583 debug_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
 590 void
 591 ppl_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
 620 void
 621 debug_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
 628 void
 629 debug_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
 637 void
 638 ppl_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
 648 void
 649 ppl_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
 679 void
 680 ppl_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
 710 ppl_Constraint_t
 711 ppl_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