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