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
  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