include/cloog/ppl_backend.h

   1    /**-------------------------------------------------------------------**
   2     **                               CLooG                               **
   3     **-------------------------------------------------------------------**
   4     **                            polyhedron.h                           **
   5     **-------------------------------------------------------------------**
   6     **                   First version: July 22th 2008                   **
   7     **-------------------------------------------------------------------**/
   8
   9
  10 /******************************************************************************
  11  *               CLooG : the Chunky Loop Generator (experimental)             *
  12  ******************************************************************************
  13  *                                                                            *
  14  * Copyright (C) 2001-2008 Cedric Bastoul                                     *
  15  *                                                                            *
  16  * This is free software; you can redistribute it and/or modify it under the  *
  17  * terms of the GNU General Public License as published by the Free Software  *
  18  * Foundation; either version 2 of the License, or (at your option) any later *
  19  * version.                                                                   *
  20  *                                                                            *
  21  * This software is distributed in the hope that it will be useful, but       *
  22  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY *
  23  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License   *
  24  * for more details.                                                          *
  25  *                                                                            *
  26  * You should have received a copy of the GNU General Public License along    *
  27  * with software; if not, write to the Free Software Foundation, Inc.,        *
  28  * 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA                     *
  29  *                                                                            *
  30  * CLooG, the Chunky Loop Generator                                           *
  31  *                                                                            *
  32  ******************************************************************************/
  33
  34 #include <ppl_c.h>
  35 #include <gmp.h>
  36 #include <stdlib.h>
  37 #include <string.h>
  38
  39 #ifndef CLOOG_PPL_BACKEND_H
  40 #define CLOOG_PPL_BACKEND_H
  41
  42 #if PPL_VERSION_MAJOR == 0 && PPL_VERSION_MINOR < 10
  43 # error "PPL version 0.10 or following is required"
  44 #endif
  45
  46 #if defined(__cplusplus)
  47 extern "C"
  48 {
  49 #endif
  50
  51   extern void cloog_initialize (void);
  52   static inline void cloog_finalize (void)
  53   {
  54     ppl_finalize ();
  55   }
  56
  57   typedef mpz_t Value;
  58 #define VALUE_FMT "%s"
  59
  60 #define value_init(val) mpz_init (val)
  61 #define value_assign(v1, v2) mpz_set (v1, v2)
  62 #define value_set_si(val, i) mpz_set_si (val, i)
  63 #define value_get_si(val) mpz_get_si (val)
  64 #define value_set_double(val, d) mpz_set_d (val, d)
  65 #define value_clear(val) mpz_clear (val)
  66 #define value_read(val, str) mpz_set_str (val, str, 10)
  67 #define value_print(Dst, fmt, val) {char *str; \
  68     void (*gmp_free) (void *, size_t);                         \
  69     str = mpz_get_str(0,10,(val));                             \
  70     fprintf((Dst),(fmt),str);                                           \
  71     mp_get_memory_functions(NULL, NULL, &gmp_free);                     \
  72     (*gmp_free) (str, strlen(str)+1);                                   \
  73                               }
  74 #define value_swap(val1, val2) mpz_swap (val1, val2)
  75 #define value_eq(v1, v2) (mpz_cmp((v1),(v2)) == 0)
  76 #define value_ne(v1,v2) (mpz_cmp((v1),(v2)) != 0)
  77 #define value_gt(v1,v2) (mpz_cmp((v1),(v2))  > 0)
  78 #define value_ge(v1,v2) (mpz_cmp((v1),(v2)) >= 0)
  79 #define value_lt(v1,v2) (mpz_cmp((v1),(v2))  < 0)
  80 #define value_le(v1,v2) (mpz_cmp((v1),(v2)) <= 0)
  81 #define value_abs_eq(v1,v2) (mpz_cmpabs((v1),(v2)) == 0)
  82 #define value_abs_ne(v1,v2) (mpz_cmpabs((v1),(v2)) != 0)
  83 #define value_abs_gt(v1,v2) (mpz_cmpabs((v1),(v2))  > 0)
  84 #define value_abs_ge(v1,v2) (mpz_cmpabs((v1),(v2)) >= 0)
  85 #define value_abs_lt(v1,v2) (mpz_cmpabs((v1),(v2))  < 0)
  86 #define value_abs_le(v1,v2) (mpz_cmpabs((v1),(v2)) <= 0)
  87 #define value_sign(val)      (mpz_sgn(val))
  88 #define value_compare(v1,v2) (mpz_cmp((v1),(v2)))
  89 #define value_addto(ref,val1,val2)     (mpz_add((ref),(val1),(val2)))
  90 #define value_add_int(ref,val,vint)     (mpz_add_ui((ref),(val),(long)(vint)))
  91 #define value_addmul(ref, val1, val2)   (mpz_addmul((ref), (val1), (val2)))
  92 #define value_increment(ref,val)       (mpz_add_ui((ref),(val),1))
  93 #define value_multiply(ref,val1,val2)  (mpz_mul((ref),(val1),(val2)))
  94 #define value_subtract(ref,val1,val2) (mpz_sub((ref),(val1),(val2)))
  95 #define value_sub_int(ref,val,vint)     (mpz_sub_ui((ref),(val),(long)(vint)))
  96 #define value_decrement(ref,val)       (mpz_sub_ui((ref),(val),1))
  97 #define value_division(ref,val1,val2)  (mpz_tdiv_q((ref),(val1),(val2)))
  98 #define value_modulus(ref,val1,val2)   (mpz_tdiv_r((ref),(val1),(val2)))
  99 #define value_pdivision(ref,val1,val2) (mpz_fdiv_q((ref),(val1),(val2)))
 100 #define value_pmodulus(ref,val1,val2)  (mpz_fdiv_r((ref),(val1),(val2)))
 101 #define value_oppose(ref,val)          (mpz_neg((ref),(val)))
 102 #define value_absolute(ref,val)        (mpz_abs((ref),(val)))
 103 #define value_pos_p(val)         (mpz_sgn(val) >  0)
 104 #define value_neg_p(val)         (mpz_sgn(val) <  0)
 105 #define value_zero_p(val)        (mpz_sgn(val) == 0)
 106 #define value_notzero_p(val)     (mpz_sgn(val) != 0)
 107 #define value_one_p(val)         (mpz_cmp_si(val,1) == 0)
 108 #define value_notone_p(val)      (mpz_cmp_si(val,1) != 0)
 109 #define value_mone_p(val)        (mpz_cmp_si(val,-1) ==0)
 110 #define value_notmone_p(val)     (mpz_cmp_si(val,-1) !=0)
 111 #define value_cmp_si(val, n)     (mpz_cmp_si(val,n))
 112
 113 #define value_substract(ref,val1,val2) (value_subtract((ref),(val1),(val2)))
 114
 115   static inline void
 116   cloog_vector_set (Value * ptr, int n, unsigned length)
 117   {
 118     unsigned i;
 119
 120     for (i = 0; i < length; i++, ptr++)
 121       value_set_si (*ptr, n);
 122   }
 123
 124   static inline void cloog_vector_copy (Value * p1, Value * p2, unsigned length)
 125   {
 126     unsigned i;
 127
 128     for (i = 0; i < length; i++)
 129       value_assign (*p2++, *p1++);
 130   }
 131
 132   static inline void Gcd (Value a, Value b, Value * gcd)
 133   {
 134     Value a1, b1;
 135
 136     value_init (a1), value_assign (a1, a);
 137     value_init (b1), value_assign (b1, b);
 138
 139     while (value_notzero_p (a1))
 140       {
 141         value_modulus (*gcd, b1, a1);
 142         value_assign (b1, a1);
 143         value_assign (a1, *gcd);
 144       }
 145
 146     value_absolute (*gcd, b1);
 147     value_clear (a1);
 148     value_clear (b1);
 149   }
 150
 151
 152   typedef struct
 153   {
 154     unsigned Size;
 155     Value *p;
 156   } Vector;
 157
 158
 159   static inline void Vector_Free (Vector * vector)
 160   {
 161     unsigned i;
 162
 163     if (!vector)
 164       return;
 165
 166     for (i = 0; i < vector->Size; i++)
 167       value_clear (vector->p[i]);
 168
 169     free (vector->p);
 170     free (vector);
 171   }
 172
 173   typedef struct polyhedron
 174   {
 175     unsigned Dimension;
 176     unsigned NbConstraints;
 177     Value **Constraint;
 178   } *polyhedron;
 179
 180   static inline unsigned cloog_pol_dim (polyhedron p)
 181   {
 182     return p->Dimension;
 183   }
 184
 185   static inline unsigned cloog_pol_nbc (polyhedron p)
 186   {
 187     return p->NbConstraints;
 188   }
 189
 190   typedef struct polyhedra_union
 191   {
 192     polyhedron _polyhedron;
 193     struct polyhedra_union *_next;
 194   } *polyhedra_union;
 195
 196   extern polyhedra_union cloog_new_upol (polyhedron);
 197
 198   static inline polyhedra_union cloog_upol_next (polyhedra_union p)
 199   {
 200     return p->_next;
 201   }
 202
 203   static inline void
 204     cloog_upol_set_next (polyhedra_union p, polyhedra_union n)
 205   {
 206     p->_next = n;
 207   }
 208
 209   static inline polyhedron cloog_upol_polyhedron (polyhedra_union upol)
 210   {
 211     return upol->_polyhedron;
 212   }
 213
 214   static inline void
 215     cloog_upol_set_polyhedron (polyhedra_union ppl, polyhedron p)
 216   {
 217     ppl->_polyhedron = p;
 218   }
 219
 220   static inline unsigned cloog_upol_dim (polyhedra_union p)
 221   {
 222     return cloog_pol_dim (cloog_upol_polyhedron (p));
 223   }
 224
 225   static inline unsigned cloog_upol_nbc (polyhedra_union p)
 226   {
 227     return cloog_pol_nbc (cloog_upol_polyhedron (p));
 228   }
 229
 230   static inline void cloog_upol_free (polyhedra_union upol)
 231   {
 232     free (upol);
 233   }
 234
 235   typedef struct cloogdomain
 236   {
 237     struct polyhedra_union *_union;
 238     int _references;
 239   } CloogDomain;
 240
 241   static inline polyhedra_union cloog_domain_upol (CloogDomain * domain)
 242   {
 243     return domain->_union;
 244   }
 245
 246   static inline polyhedron cloog_domain_polyhedron (CloogDomain * domain)
 247   {
 248     return cloog_upol_polyhedron (cloog_domain_upol (domain));
 249   }
 250
 251   static inline unsigned cloog_domain_dim (CloogDomain * d)
 252   {
 253     return cloog_pol_dim (cloog_domain_polyhedron (d));
 254   }
 255
 256   static inline int cloog_domain_nbconstraints (CloogDomain * domain)
 257   {
 258     return cloog_pol_nbc (cloog_domain_polyhedron (domain));
 259   }
 260
 261   static inline unsigned cloog_pol_nbeq (polyhedron p)
 262   {
 263     unsigned i, res = 0;
 264
 265     for (i = 0; i < p->NbConstraints; i++)
 266       res += value_zero_p (p->Constraint[i][0]) ? 1 : 0;
 267
 268     return res;
 269   }
 270
 271   static inline unsigned cloog_domain_nbeq (CloogDomain * d)
 272   {
 273     return cloog_pol_nbeq (cloog_upol_polyhedron (cloog_domain_upol (d)));
 274   }
 275
 276   extern Vector *Vector_Alloc (unsigned);
 277
 278   typedef struct cloog_matrix
 279   {
 280     int NbRows;
 281     int NbColumns;
 282     Value **p;
 283   } CloogMatrix;
 284
 285   void cloog_matrix_print (FILE *, CloogMatrix *);
 286   void cloog_matrix_free (CloogMatrix *);
 287   CloogMatrix *cloog_matrix_alloc (unsigned, unsigned);
 288   void cloog_matrix_print_structure (FILE *, CloogMatrix *, int);
 289   CloogMatrix *cloog_matrix_read (FILE *);
 290   void cloog_matrix_normalize (CloogMatrix *, int);
 291   void cloog_matrix_equality_update (CloogMatrix *, int, int);
 292   CloogMatrix *cloog_matrix_copy (CloogMatrix *);
 293   Value *cloog_matrix_vector_copy (Value *, int);
 294   Value *cloog_matrix_vector_simplify (Value *, CloogMatrix *, int, int, int);
 295   CloogMatrix *cloog_matrix_simplify (CloogMatrix *, CloogMatrix *, int, int);
 296   void cloog_matrix_vector_free (Value *, int);
 297
 298   static inline CloogMatrix *cloog_pol_matrix (polyhedron p)
 299   {
 300     int cols = cloog_pol_dim (p) + 2;
 301     int rows = cloog_pol_nbc (p);
 302     int i, j;
 303     CloogMatrix *res = cloog_matrix_alloc (rows, cols);
 304
 305     for (i = 0; i < rows; i++)
 306       for (j = 0; j < cols; j++)
 307         value_assign (res->p[i][j], p->Constraint[i][j]);
 308
 309     return res;
 310   }
 311
 312   static inline int cloog_matrix_ncolumns (CloogMatrix * m)
 313   {
 314     return m->NbColumns;
 315   }
 316
 317   static inline int cloog_matrix_nrows (CloogMatrix * m)
 318   {
 319     return m->NbRows;
 320   }
 321
 322   static inline int cloog_first_non_zero (Value * p, unsigned len)
 323   {
 324     Value *ptr = p;
 325     unsigned i;
 326
 327     for (i = 0; i < len; i++, ptr++)
 328       if (value_notzero_p (*ptr))
 329         break;
 330
 331     return i == len ? -1 : (int) i;
 332   }
 333
 334   polyhedron cloog_new_pol (int, int);
 335
 336   static inline polyhedron cloog_universe_polyhedron (unsigned dim)
 337   {
 338     polyhedron res = cloog_new_pol (dim, 1);
 339
 340     cloog_vector_set (res->Constraint[0], 0, dim + 2);
 341     value_set_si (res->Constraint[0][0], 1);
 342     value_set_si (res->Constraint[0][dim + 1], 1);
 343
 344     return res;
 345   }
 346
 347   static inline polyhedron cloog_empty_polyhedron (int dim)
 348   {
 349     int i;
 350     polyhedron res = cloog_new_pol (dim, dim + 1);
 351
 352     cloog_vector_set (res->Constraint[0], 0, (dim + 1) * (dim + 2));
 353
 354     for (i = 0; i <= dim; i++)
 355       value_set_si (res->Constraint[i][i + 1], 1);
 356
 357     return res;
 358   }
 359
 360   static inline void
 361   cloog_matrix_exchange_rows (CloogMatrix * m, int row1, int row2)
 362   {
 363     int i;
 364
 365     for (i = 0; i < m->NbColumns; i++)
 366       value_swap (m->p[row1][i], m->p[row2][i]);
 367   }
 368
 369   static inline void cloog_vector_exchange (Value * p1, Value * p2, int len)
 370   {
 371     for (; len > 0; len--)
 372       value_swap (p1[len - 1], p2[len - 1]);
 373   }
 374
 375   polyhedron cloog_pol_from_matrix (CloogMatrix * m);
 376
 377   static inline void cloog_pol_free (polyhedron pol)
 378   {
 379     int n, i;
 380
 381     if (!pol)
 382       return;
 383
 384     n = (cloog_pol_dim (pol) + 2) * cloog_pol_nbc (pol);
 385
 386     for (i = 0; i < n; i++)
 387       value_clear (pol->Constraint[0][i]);
 388
 389     free (pol->Constraint[0]);
 390     free (pol->Constraint);
 391     free (pol);
 392   }
 393
 394   polyhedron cloog_pol_copy (polyhedron pol);
 395   void cloog_vector_gcd (Value *, int, Value *);
 396
 397   static inline int
 398   cloog_pol_lexico_lt (polyhedron p, int i, int j)
 399   {
 400     int res = 0;
 401     unsigned k;
 402     Value a, b;
 403
 404     value_init (a), value_init (b);
 405
 406     for (k = 1; k < cloog_pol_dim (p) + 2; k++)
 407       {
 408         value_absolute (a, p->Constraint[i][k]);
 409         value_absolute (b, p->Constraint[j][k]);
 410
 411         if (value_lt (a, b))
 412           {
 413             res = 1;
 414             goto clear;
 415           }
 416
 417         if (value_gt (a, b))
 418           {
 419             res = 0;
 420             goto clear;
 421           }
 422
 423         if (value_lt (p->Constraint[i][k], p->Constraint[j][k]))
 424           {
 425             res = 1;
 426             goto clear;
 427           }
 428
 429         if (value_gt (p->Constraint[i][k], p->Constraint[j][k]))
 430           {
 431             res = 0;
 432             goto clear;
 433           }
 434       }
 435
 436   clear:
 437     value_clear (a), value_clear (b);
 438     return res;
 439   }
 440
 441   static inline void
 442   cloog_pol_exchange_rows (polyhedron p, int row1, int row2)
 443   {
 444     int i;
 445
 446     for (i = 0; i < (int) cloog_pol_dim (p) + 2; i++)
 447       value_swap (p->Constraint[row1][i], p->Constraint[row2][i]);
 448   }
 449
 450   static inline void
 451   cloog_pol_sort_rows (polyhedron p)
 452   {
 453     unsigned i, j;
 454     unsigned nbeq = cloog_pol_nbeq (p);
 455
 456     /* First sort the equalities.  The equalities should be the first
 457        rows in the matrix.  */
 458     for (i = 0; i < nbeq; i++)
 459       for (j = i + 1; j < nbeq; j++)
 460         if (cloog_pol_lexico_lt (p, i, j))
 461           cloog_pol_exchange_rows (p, i, j);
 462
 463     /* Sort inequalities.  */
 464     for (i = nbeq; i < cloog_pol_nbc (p); i++)
 465       for (j = i + 1; j < cloog_pol_nbc (p); j++)
 466         if (cloog_pol_lexico_lt (p, i, j))
 467           cloog_pol_exchange_rows (p, i, j);
 468   }
 469
 470   static inline CloogMatrix *
 471   cloog_upol_domain2matrix (polyhedra_union upol)
 472   {
 473     return cloog_pol_matrix (cloog_upol_polyhedron (upol));
 474   }
 475
 476   static inline CloogMatrix *
 477   cloog_domain_domain2matrix (CloogDomain *d)
 478   {
 479     return cloog_pol_matrix (cloog_domain_polyhedron (d));
 480   }
 481
 482   static inline void
 483   cloog_vector_normalize (Value * p, unsigned len)
 484   {
 485     unsigned i;
 486     Value *ptr, gcd, one;
 487
 488     value_init (gcd);
 489     cloog_vector_gcd (p, len, &gcd);
 490     value_init (one);
 491     value_set_si (one, 1);
 492
 493     if (value_gt (gcd, one))
 494       for (ptr = p, i = 0; i < len; i++, ptr++)
 495         value_division (*ptr, *ptr, gcd);
 496
 497     value_clear (one), value_clear (gcd);
 498   }
 499
 500   static inline void cloog_vector_scale (Value * p1, Value * p2,
 501                                          Value x,
 502                                          unsigned length)
 503   {
 504     unsigned i;
 505
 506     for (i = 0; i < length; i++)
 507       value_multiply (*p2++, *p1++, x);
 508   }
 509
 510   static inline void
 511   cloog_vector_combine (Value * p1, Value * p2, Value * p3, Value x,
 512                         Value y, unsigned length)
 513   {
 514     Value tmp;
 515     unsigned i;
 516
 517     value_init (tmp);
 518
 519     for (i = 0; i < length; i++)
 520       {
 521         value_multiply (tmp, x, p1[i]);
 522         value_addmul (tmp, y, p2[i]);
 523         value_assign (p3[i], tmp);
 524       }
 525
 526     value_clear (tmp);
 527   }
 528
 529   extern void debug_poly (polyhedron);
 530   extern void debug_ppl_poly (ppl_Polyhedron_t);
 531   extern void debug_cloog_matrix (CloogMatrix *);
 532   extern void debug_cloog_domain (CloogDomain *);
 533   extern void debug_value (Value);
 534   extern void debug_values (Value *, int);
 535
 536 #if defined(__cplusplus)
 537 }
 538 #endif
 539 #endif /* define _H */