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 #if defined(__cplusplus)
  42 extern "C"
  43 {
  44 #endif
  45
  46   extern void cloog_initialize (void);
  47   static inline void cloog_finalize (void)
  48   {
  49     ppl_finalize ();
  50   }
  51
  52   typedef mpz_t Value;
  53 #define VALUE_FMT "%s"
  54
  55 #define value_init(val) mpz_init (val)
  56 #define value_assign(v1, v2) mpz_set (v1, v2)
  57 #define value_set_si(val, i) mpz_set_si (val, i)
  58 #define value_get_si(val) mpz_get_si (val)
  59 #define value_set_double(val, d) mpz_set_d (val, d)
  60 #define value_clear(val) mpz_clear (val)
  61 #define value_read(val, str) mpz_set_str (val, str, 10)
  62 #define value_print(Dst, fmt, val) {char *str; \
  63     void (*gmp_free) (void *, size_t);                         \
  64     str = mpz_get_str(0,10,(val));                             \
  65     fprintf((Dst),(fmt),str);                                           \
  66     mp_get_memory_functions(NULL, NULL, &gmp_free);                     \
  67     (*gmp_free) (str, strlen(str)+1);                                   \
  68                               }
  69 #define value_swap(val1, val2) mpz_swap (val1, val2)
  70 #define value_eq(v1, v2) (mpz_cmp((v1),(v2)) == 0)
  71 #define value_ne(v1,v2) (mpz_cmp((v1),(v2)) != 0)
  72 #define value_gt(v1,v2) (mpz_cmp((v1),(v2))  > 0)
  73 #define value_ge(v1,v2) (mpz_cmp((v1),(v2)) >= 0)
  74 #define value_lt(v1,v2) (mpz_cmp((v1),(v2))  < 0)
  75 #define value_le(v1,v2) (mpz_cmp((v1),(v2)) <= 0)
  76 #define value_abs_eq(v1,v2) (mpz_cmpabs((v1),(v2)) == 0)
  77 #define value_abs_ne(v1,v2) (mpz_cmpabs((v1),(v2)) != 0)
  78 #define value_abs_gt(v1,v2) (mpz_cmpabs((v1),(v2))  > 0)
  79 #define value_abs_ge(v1,v2) (mpz_cmpabs((v1),(v2)) >= 0)
  80 #define value_abs_lt(v1,v2) (mpz_cmpabs((v1),(v2))  < 0)
  81 #define value_abs_le(v1,v2) (mpz_cmpabs((v1),(v2)) <= 0)
  82 #define value_sign(val)      (mpz_sgn(val))
  83 #define value_compare(v1,v2) (mpz_cmp((v1),(v2)))
  84 #define value_addto(ref,val1,val2)     (mpz_add((ref),(val1),(val2)))
  85 #define value_add_int(ref,val,vint)     (mpz_add_ui((ref),(val),(long)(vint)))
  86 #define value_addmul(ref, val1, val2)   (mpz_addmul((ref), (val1), (val2)))
  87 #define value_increment(ref,val)       (mpz_add_ui((ref),(val),1))
  88 #define value_multiply(ref,val1,val2)  (mpz_mul((ref),(val1),(val2)))
  89 #define value_subtract(ref,val1,val2) (mpz_sub((ref),(val1),(val2)))
  90 #define value_sub_int(ref,val,vint)     (mpz_sub_ui((ref),(val),(long)(vint)))
  91 #define value_decrement(ref,val)       (mpz_sub_ui((ref),(val),1))
  92 #define value_division(ref,val1,val2)  (mpz_tdiv_q((ref),(val1),(val2)))
  93 #define value_modulus(ref,val1,val2)   (mpz_tdiv_r((ref),(val1),(val2)))
  94 #define value_pdivision(ref,val1,val2) (mpz_fdiv_q((ref),(val1),(val2)))
  95 #define value_pmodulus(ref,val1,val2)  (mpz_fdiv_r((ref),(val1),(val2)))
  96 #define value_oppose(ref,val)          (mpz_neg((ref),(val)))
  97 #define value_absolute(ref,val)        (mpz_abs((ref),(val)))
  98 #define value_pos_p(val)         (mpz_sgn(val) >  0)
  99 #define value_neg_p(val)         (mpz_sgn(val) <  0)
 100 #define value_zero_p(val)        (mpz_sgn(val) == 0)
 101 #define value_notzero_p(val)     (mpz_sgn(val) != 0)
 102 #define value_one_p(val)         (mpz_cmp_si(val,1) == 0)
 103 #define value_notone_p(val)      (mpz_cmp_si(val,1) != 0)
 104 #define value_mone_p(val)        (mpz_cmp_si(val,-1) ==0)
 105 #define value_notmone_p(val)     (mpz_cmp_si(val,-1) !=0)
 106 #define value_cmp_si(val, n)     (mpz_cmp_si(val,n))
 107
 108 #define value_substract(ref,val1,val2) (value_subtract((ref),(val1),(val2)))
 109
 110   static inline void
 111   cloog_vector_set (Value * ptr, int n, unsigned length)
 112   {
 113     int i;
 114
 115     for (i = 0; i < length; i++, ptr++)
 116       value_set_si (*ptr, n);
 117   }
 118
 119   static inline void cloog_vector_copy (Value * p1, Value * p2, unsigned length)
 120   {
 121     int i;
 122
 123     for (i = 0; i < length; i++)
 124       value_assign (*p2++, *p1++);
 125   }
 126
 127   static inline void Gcd (Value a, Value b, Value * gcd)
 128   {
 129     Value a1, b1;
 130
 131     value_init (a1), value_assign (a1, a);
 132     value_init (b1), value_assign (b1, b);
 133
 134     while (value_notzero_p (a1))
 135       {
 136         value_modulus (*gcd, b1, a1);
 137         value_assign (b1, a1);
 138         value_assign (a1, *gcd);
 139       }
 140
 141     value_absolute (*gcd, b1);
 142     value_clear (a1);
 143     value_clear (b1);
 144   }
 145
 146
 147   typedef struct
 148   {
 149     unsigned Size;
 150     Value *p;
 151   } Vector;
 152
 153
 154   static inline void Vector_Free (Vector * vector)
 155   {
 156     int i;
 157
 158     if (!vector)
 159       return;
 160
 161     for (i = 0; i < vector->Size; i++)
 162       value_clear (vector->p[i]);
 163
 164     free (vector->p);
 165     free (vector);
 166   }
 167
 168   typedef struct polyhedron
 169   {
 170     unsigned Dimension;
 171     unsigned NbConstraints;
 172     Value **Constraint;
 173   } *polyhedron;
 174
 175   static inline unsigned cloog_pol_dim (polyhedron p)
 176   {
 177     return p->Dimension;
 178   }
 179
 180   static inline unsigned cloog_pol_nbc (polyhedron p)
 181   {
 182     return p->NbConstraints;
 183   }
 184
 185   typedef struct polyhedra_union
 186   {
 187     polyhedron _polyhedron;
 188     struct polyhedra_union *_next;
 189   } *polyhedra_union;
 190
 191   static inline polyhedra_union cloog_new_upol (polyhedron p)
 192   {
 193     polyhedra_union ppl =
 194       (polyhedra_union) malloc (sizeof (struct polyhedra_union));
 195     ppl->_polyhedron = p;
 196     ppl->_next = NULL;
 197     return ppl;
 198   }
 199
 200   static inline polyhedra_union cloog_upol_next (polyhedra_union p)
 201   {
 202     return p->_next;
 203   }
 204
 205   static inline void
 206     cloog_upol_set_next (polyhedra_union p, polyhedra_union n)
 207   {
 208     p->_next = n;
 209   }
 210
 211   static inline polyhedron cloog_upol_polyhedron (polyhedra_union upol)
 212   {
 213     return upol->_polyhedron;
 214   }
 215
 216   static inline void
 217     cloog_upol_set_polyhedron (polyhedra_union ppl, polyhedron p)
 218   {
 219     ppl->_polyhedron = p;
 220   }
 221
 222   static inline unsigned cloog_upol_dim (polyhedra_union p)
 223   {
 224     return cloog_pol_dim (cloog_upol_polyhedron (p));
 225   }
 226
 227   static inline unsigned cloog_upol_nbc (polyhedra_union p)
 228   {
 229     return cloog_pol_nbc (cloog_upol_polyhedron (p));
 230   }
 231
 232
 233   typedef struct cloogdomain
 234   {
 235     struct polyhedra_union *_union;
 236     int _references;
 237   } CloogDomain;
 238
 239   extern void debug_cloog_domain (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     int 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   static inline Vector *Vector_Alloc (unsigned length)
 277   {
 278     int i;
 279     Vector *vector = (Vector *) malloc (sizeof (Vector));
 280
 281     vector->Size = length;
 282     vector->p = (Value *) malloc (length * sizeof (Value));
 283
 284     for (i = 0; i < length; i++)
 285       value_init (vector->p[i]);
 286
 287     return vector;
 288   }
 289
 290   typedef struct cloog_matrix
 291   {
 292     int NbRows;
 293     int NbColumns;
 294     Value **p;
 295   } CloogMatrix;
 296
 297   void cloog_matrix_print (FILE *, CloogMatrix *);
 298   void cloog_matrix_free (CloogMatrix *);
 299   CloogMatrix *cloog_matrix_alloc (unsigned, unsigned);
 300   void debug_cloog_matrix (CloogMatrix *);
 301   void cloog_matrix_print_structure (FILE *, CloogMatrix *, int);
 302   CloogMatrix *cloog_matrix_read (FILE *);
 303   void cloog_matrix_normalize (CloogMatrix *, int);
 304   void cloog_matrix_equality_update (CloogMatrix *, int, int);
 305   CloogMatrix *cloog_matrix_copy (CloogMatrix *);
 306   Value *cloog_matrix_vector_copy (Value *, int);
 307   Value *cloog_matrix_vector_simplify (Value *, CloogMatrix *, int, int, int);
 308   CloogMatrix *cloog_matrix_simplify (CloogMatrix *, CloogMatrix *, int, int);
 309   void cloog_matrix_vector_free (Value *, int);
 310
 311   static inline CloogMatrix *cloog_pol_matrix (polyhedron p)
 312   {
 313     int cols = cloog_pol_dim (p) + 2;
 314     int rows = cloog_pol_nbc (p);
 315     int i, j;
 316     CloogMatrix *res = cloog_matrix_alloc (rows, cols);
 317
 318     for (i = 0; i < rows; i++)
 319       for (j = 0; j < cols; j++)
 320         value_assign (res->p[i][j], p->Constraint[i][j]);
 321
 322     return res;
 323   }
 324
 325   static inline int cloog_matrix_ncolumns (CloogMatrix * m)
 326   {
 327     return m->NbColumns;
 328   }
 329
 330   static inline int cloog_matrix_nrows (CloogMatrix * m)
 331   {
 332     return m->NbRows;
 333   }
 334
 335   static inline int cloog_first_non_zero (Value * p, unsigned len)
 336   {
 337     Value *ptr = p;
 338     int i;
 339
 340     for (i = 0; i < len; i++, ptr++)
 341       if (value_notzero_p (*ptr))
 342         break;
 343
 344     return i == len ? -1 : i;
 345   }
 346
 347   static inline polyhedron cloog_new_pol (int dim, int nrows)
 348   {
 349     int i;
 350     polyhedron res = (polyhedron) malloc (sizeof (struct polyhedron));
 351     int ncolumns = dim + 2;
 352     int n = nrows * ncolumns;
 353     Value *p = (Value *) malloc (n * sizeof (Value));
 354
 355     res->Dimension = dim;
 356     res->NbConstraints = nrows;
 357     res->Constraint = (Value **) malloc (nrows * sizeof (Value *));
 358
 359     for (i = 0; i < n; ++i)
 360       value_init (p[i]);
 361
 362     for (i = 0; i < nrows; i++, p += ncolumns)
 363       res->Constraint[i] = p;
 364
 365     return res;
 366   }
 367
 368   static inline polyhedron cloog_universe_polyhedron (unsigned dim)
 369   {
 370     polyhedron res = cloog_new_pol (dim, 1);
 371
 372     cloog_vector_set (res->Constraint[0], 0, dim + 2);
 373     value_set_si (res->Constraint[0][0], 1);
 374     value_set_si (res->Constraint[0][dim + 1], 1);
 375
 376     return res;
 377   }
 378
 379   static inline polyhedron cloog_empty_polyhedron (int dim)
 380   {
 381     int i;
 382     polyhedron res = cloog_new_pol (dim, dim + 1);
 383
 384     cloog_vector_set (res->Constraint[0], 0, (dim + 1) * (dim + 2));
 385
 386     for (i = 0; i <= dim; i++)
 387       value_set_si (res->Constraint[i][i + 1], 1);
 388
 389     return res;
 390   }
 391
 392   static inline void
 393   cloog_matrix_exchange_rows (CloogMatrix * m, int row1, int row2)
 394   {
 395     int i;
 396
 397     for (i = 0; i < m->NbColumns; i++)
 398       value_swap (m->p[row1][i], m->p[row2][i]);
 399   }
 400
 401   static inline void cloog_vector_exchange (Value * p1, Value * p2, int len)
 402   {
 403     for (; len > 0; len--)
 404       value_swap (p1[len - 1], p2[len - 1]);
 405   }
 406
 407   polyhedron cloog_pol_from_matrix (CloogMatrix * m);
 408
 409   static inline void cloog_pol_free (polyhedron pol)
 410   {
 411     int n, i;
 412
 413     if (!pol)
 414       return;
 415
 416     n = (cloog_pol_dim (pol) + 2) * cloog_pol_nbc (pol);
 417
 418     for (i = 0; i < n; i++)
 419       value_clear (pol->Constraint[0][i]);
 420
 421     free (pol->Constraint[0]);
 422     free (pol->Constraint);
 423     free (pol);
 424   }
 425
 426   polyhedron cloog_pol_copy (polyhedron pol);
 427   void cloog_vector_gcd (Value *, unsigned, Value *);
 428
 429   static inline int
 430   cloog_pol_lexico_lt (polyhedron p, int i, int j)
 431   {
 432     int k;
 433     Value a, b;
 434
 435     value_init (a), value_init (b);
 436
 437     for (k = 1; k < cloog_pol_dim (p) + 2; k++)
 438       {
 439         value_absolute (a, p->Constraint[i][k]);
 440         value_absolute (b, p->Constraint[j][k]);
 441
 442         if (value_lt (a, b))
 443           return 1;
 444
 445         if (value_gt (a, b))
 446           return 0;
 447
 448         if (value_lt (p->Constraint[i][k], p->Constraint[j][k]))
 449           return 1;
 450
 451         if (value_gt (p->Constraint[i][k], p->Constraint[j][k]))
 452           return 0;
 453       }
 454
 455     value_clear (a), value_clear (b);
 456
 457     return 0;
 458   }
 459
 460   static inline void
 461   cloog_pol_exchange_rows (polyhedron p, int row1, int row2)
 462   {
 463     int i;
 464
 465     for (i = 0; i < (int) cloog_pol_dim (p) + 2; i++)
 466       value_swap (p->Constraint[row1][i], p->Constraint[row2][i]);
 467   }
 468
 469   static inline void
 470   cloog_pol_sort_rows (polyhedron p)
 471   {
 472     int i, j;
 473     int nbeq = cloog_pol_nbeq (p);
 474
 475     /* First sort the equalities.  The equalities should be the first
 476        rows in the matrix.  */
 477     for (i = 0; i < nbeq; i++)
 478       for (j = i + 1; j < nbeq; j++)
 479         if (cloog_pol_lexico_lt (p, i, j))
 480           cloog_pol_exchange_rows (p, i, j);
 481
 482     /* Sort inequalities.  */
 483     for (i = nbeq; i < cloog_pol_nbc (p); i++)
 484       for (j = i + 1; j < cloog_pol_nbc (p); j++)
 485         if (cloog_pol_lexico_lt (p, i, j))
 486           cloog_pol_exchange_rows (p, i, j);
 487   }
 488
 489   static inline CloogMatrix *
 490   cloog_upol_domain2matrix (polyhedra_union upol)
 491   {
 492     return cloog_pol_matrix (cloog_upol_polyhedron (upol));
 493   }
 494
 495   static inline void
 496   cloog_vector_normalize (Value * p, unsigned len)
 497   {
 498     int i;
 499     Value *ptr, gcd, one;
 500
 501     value_init (gcd);
 502     cloog_vector_gcd (p, len, &gcd);
 503     value_init (one);
 504     value_set_si (one, 1);
 505
 506     if (value_gt (gcd, one))
 507       for (ptr = p, i = 0; i < len; i++, ptr++)
 508         value_division (*ptr, *ptr, gcd);
 509
 510     value_clear (one), value_clear (gcd);
 511   }
 512
 513   static inline void cloog_vector_scale (Value * p1, Value * p2,
 514                                          Value x,
 515                                          unsigned length)
 516   {
 517     int i;
 518
 519     for (i = 0; i < length; i++)
 520       value_multiply (*p2++, *p1++, x);
 521   }
 522
 523   static inline void
 524   cloog_vector_combine (Value * p1, Value * p2, Value * p3, Value x,
 525                         Value y, unsigned length)
 526   {
 527     Value tmp;
 528     int i;
 529
 530     value_init (tmp);
 531
 532     for (i = 0; i < length; i++)
 533       {
 534         value_multiply (tmp, x, p1[i]);
 535         value_addmul (tmp, y, p2[i]);
 536         value_assign (p3[i], tmp);
 537       }
 538
 539     value_clear (tmp);
 540   }
 541
 542 #if defined(__cplusplus)
 543 }
 544 #endif
 545 #endif /* define _H */