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