1 /**-------------------------------------------------------------------**
3 **-------------------------------------------------------------------**
5 **-------------------------------------------------------------------**
6 ** First version: July 22th 2008 **
7 **-------------------------------------------------------------------**/
10 /******************************************************************************
11 * CLooG : the Chunky Loop Generator (experimental) *
12 ******************************************************************************
14 * Copyright (C) 2001-2008 Cedric Bastoul *
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 *
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 *
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 *
30 * CLooG, the Chunky Loop Generator *
32 ******************************************************************************/
39 #ifndef CLOOG_PPL_BACKEND_H
40 #define CLOOG_PPL_BACKEND_H
41 #if defined(__cplusplus)
46 extern void cloog_initialize (void);
47 static inline void cloog_finalize (void)
53 #define VALUE_FMT "%s"
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); \
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))
108 #define value_substract(ref,val1,val2) (value_subtract((ref),(val1),(val2)))
111 debug_value (Value v
)
113 value_print (stderr
, VALUE_FMT
, v
);
117 debug_values (Value
*p
, int length
)
120 for (i
= 0; i
< length
; i
++)
125 check_values (Value
*p3
, Value
*p4
, int length
)
129 for (i
= 0; i
< length
; i
++)
130 if (value_ne (p3
[i
], p4
[i
]))
132 fprintf (stderr
, "vectors not the same\n");
133 debug_values (p3
, length
);
134 debug_values (p4
, length
);
139 cloog_vector_set (Value
* ptr
, int n
, unsigned length
)
143 for (i
= 0; i
< length
; i
++, ptr
++)
144 value_set_si (*ptr
, n
);
147 static inline void cloog_vector_copy (Value
* p1
, Value
* p2
, unsigned length
)
151 for (i
= 0; i
< length
; i
++)
152 value_assign (*p2
++, *p1
++);
155 static inline void Gcd (Value a
, Value b
, Value
* gcd
)
159 value_init (a1
), value_assign (a1
, a
);
160 value_init (b1
), value_assign (b1
, b
);
162 while (value_notzero_p (a1
))
164 value_modulus (*gcd
, b1
, a1
);
165 value_assign (b1
, a1
);
166 value_assign (a1
, *gcd
);
169 value_absolute (*gcd
, b1
);
182 static inline void Vector_Free (Vector
* vector
)
189 for (i
= 0; i
< vector
->Size
; i
++)
190 value_clear (vector
->p
[i
]);
196 typedef struct polyhedron
199 unsigned NbConstraints
;
203 static inline unsigned cloog_pol_dim (polyhedron p
)
208 static inline unsigned cloog_pol_nbc (polyhedron p
)
210 return p
->NbConstraints
;
213 typedef struct polyhedra_union
215 polyhedron _polyhedron
;
216 struct polyhedra_union
*_next
;
219 static inline polyhedra_union
cloog_new_upol (polyhedron p
)
221 polyhedra_union ppl
=
222 (polyhedra_union
) malloc (sizeof (struct polyhedra_union
));
223 ppl
->_polyhedron
= p
;
228 static inline polyhedra_union
cloog_upol_next (polyhedra_union p
)
234 cloog_upol_set_next (polyhedra_union p
, polyhedra_union n
)
239 static inline polyhedron
cloog_upol_polyhedron (polyhedra_union upol
)
241 return upol
->_polyhedron
;
245 cloog_upol_set_polyhedron (polyhedra_union ppl
, polyhedron p
)
247 ppl
->_polyhedron
= p
;
250 static inline unsigned cloog_upol_dim (polyhedra_union p
)
252 return cloog_pol_dim (cloog_upol_polyhedron (p
));
255 static inline unsigned cloog_upol_nbc (polyhedra_union p
)
257 return cloog_pol_nbc (cloog_upol_polyhedron (p
));
261 typedef struct cloogdomain
263 struct polyhedra_union
*_union
;
267 extern void debug_cloog_domain (CloogDomain
*);
269 static inline polyhedra_union
cloog_domain_upol (CloogDomain
* domain
)
271 return domain
->_union
;
274 static inline polyhedron
cloog_domain_polyhedron (CloogDomain
* domain
)
276 return cloog_upol_polyhedron (cloog_domain_upol (domain
));
279 static inline unsigned cloog_domain_dim (CloogDomain
* d
)
281 return cloog_pol_dim (cloog_domain_polyhedron (d
));
284 static inline int cloog_domain_nbconstraints (CloogDomain
* domain
)
286 return cloog_pol_nbc (cloog_domain_polyhedron (domain
));
289 static inline unsigned cloog_pol_nbeq (polyhedron p
)
293 for (i
= 0; i
< p
->NbConstraints
; i
++)
294 res
+= value_zero_p (p
->Constraint
[i
][0]) ? 1 : 0;
299 static inline unsigned cloog_domain_nbeq (CloogDomain
* d
)
301 return cloog_pol_nbeq (cloog_upol_polyhedron (cloog_domain_upol (d
)));
304 static inline Vector
*Vector_Alloc (unsigned length
)
307 Vector
*vector
= (Vector
*) malloc (sizeof (Vector
));
309 vector
->Size
= length
;
310 vector
->p
= (Value
*) malloc (length
* sizeof (Value
));
312 for (i
= 0; i
< length
; i
++)
313 value_init (vector
->p
[i
]);
318 typedef struct cloog_matrix
325 void cloog_matrix_print (FILE *, CloogMatrix
*);
326 void cloog_matrix_free (CloogMatrix
*);
327 CloogMatrix
*cloog_matrix_alloc (unsigned, unsigned);
328 void debug_cloog_matrix (CloogMatrix
*);
329 void cloog_matrix_print_structure (FILE *, CloogMatrix
*, int);
330 CloogMatrix
*cloog_matrix_read (FILE *);
331 void cloog_matrix_normalize (CloogMatrix
*, int);
332 void cloog_matrix_equality_update (CloogMatrix
*, int, int);
333 CloogMatrix
*cloog_matrix_copy (CloogMatrix
*);
334 Value
*cloog_matrix_vector_copy (Value
*, int);
335 Value
*cloog_matrix_vector_simplify (Value
*, CloogMatrix
*, int, int, int);
336 CloogMatrix
*cloog_matrix_simplify (CloogMatrix
*, CloogMatrix
*, int, int);
337 void cloog_matrix_vector_free (Value
*, int);
339 static inline CloogMatrix
*cloog_pol_matrix (polyhedron p
)
341 int cols
= cloog_pol_dim (p
) + 2;
342 int rows
= cloog_pol_nbc (p
);
344 CloogMatrix
*res
= cloog_matrix_alloc (rows
, cols
);
346 for (i
= 0; i
< rows
; i
++)
347 for (j
= 0; j
< cols
; j
++)
348 value_assign (res
->p
[i
][j
], p
->Constraint
[i
][j
]);
353 static inline int cloog_matrix_ncolumns (CloogMatrix
* m
)
358 static inline int cloog_matrix_nrows (CloogMatrix
* m
)
363 static inline int cloog_first_non_zero (Value
* p
, unsigned len
)
368 for (i
= 0; i
< len
; i
++, ptr
++)
369 if (value_notzero_p (*ptr
))
372 return i
== len
? -1 : i
;
375 static inline polyhedron
cloog_new_pol (int dim
, int nrows
)
378 polyhedron res
= (polyhedron
) malloc (sizeof (struct polyhedron
));
379 int ncolumns
= dim
+ 2;
380 int n
= nrows
* ncolumns
;
381 Value
*p
= (Value
*) malloc (n
* sizeof (Value
));
383 res
->Dimension
= dim
;
384 res
->NbConstraints
= nrows
;
385 res
->Constraint
= (Value
**) malloc (nrows
* sizeof (Value
*));
387 for (i
= 0; i
< n
; ++i
)
390 for (i
= 0; i
< nrows
; i
++, p
+= ncolumns
)
391 res
->Constraint
[i
] = p
;
396 static inline polyhedron
cloog_universe_polyhedron (unsigned dim
)
398 polyhedron res
= cloog_new_pol (dim
, 1);
400 cloog_vector_set (res
->Constraint
[0], 0, dim
+ 2);
401 value_set_si (res
->Constraint
[0][0], 1);
402 value_set_si (res
->Constraint
[0][dim
+ 1], 1);
407 static inline polyhedron
cloog_empty_polyhedron (int dim
)
410 polyhedron res
= cloog_new_pol (dim
, dim
+ 1);
412 cloog_vector_set (res
->Constraint
[0], 0, (dim
+ 1) * (dim
+ 2));
414 for (i
= 0; i
<= dim
; i
++)
415 value_set_si (res
->Constraint
[i
][i
+ 1], 1);
421 cloog_matrix_exchange_rows (CloogMatrix
* m
, int row1
, int row2
)
425 for (i
= 0; i
< m
->NbColumns
; i
++)
426 value_swap (m
->p
[row1
][i
], m
->p
[row2
][i
]);
429 static inline void cloog_vector_exchange (Value
* p1
, Value
* p2
, int len
)
431 for (; len
> 0; len
--)
432 value_swap (p1
[len
- 1], p2
[len
- 1]);
435 void cloog_pol_print (FILE *, polyhedron
);
436 polyhedron
cloog_pol_from_matrix (CloogMatrix
* m
);
438 static inline void cloog_pol_free (polyhedron pol
)
445 n
= (cloog_pol_dim (pol
) + 2) * cloog_pol_nbc (pol
);
447 for (i
= 0; i
< n
; i
++)
448 value_clear (pol
->Constraint
[0][i
]);
450 free (pol
->Constraint
[0]);
451 free (pol
->Constraint
);
455 polyhedron
cloog_pol_copy (polyhedron pol
);
456 void cloog_vector_gcd (Value
*, unsigned, Value
*);
457 int cloog_solve_diophantine (CloogMatrix
*, CloogMatrix
**, Vector
**);
458 void cloog_exchange_rows (CloogMatrix
* M
, int Row1
, int Row2
);
461 cloog_pol_lexico_lt (polyhedron p
, int i
, int j
)
466 value_init (a
), value_init (b
);
468 for (k
= 1; k
< cloog_pol_dim (p
) + 2; k
++)
470 value_absolute (a
, p
->Constraint
[i
][k
]);
471 value_absolute (b
, p
->Constraint
[j
][k
]);
479 if (value_lt (p
->Constraint
[i
][k
], p
->Constraint
[j
][k
]))
482 if (value_gt (p
->Constraint
[i
][k
], p
->Constraint
[j
][k
]))
486 value_clear (a
), value_clear (b
);
492 cloog_pol_exchange_rows (polyhedron p
, int row1
, int row2
)
496 for (i
= 0; i
< (int) cloog_pol_dim (p
) + 2; i
++)
497 value_swap (p
->Constraint
[row1
][i
], p
->Constraint
[row2
][i
]);
501 cloog_pol_sort_rows (polyhedron p
)
504 int nbeq
= cloog_pol_nbeq (p
);
506 /* First sort the equalities. The equalities should be the first
507 rows in the matrix. */
508 for (i
= 0; i
< nbeq
; i
++)
509 for (j
= i
+ 1; j
< nbeq
; j
++)
510 if (cloog_pol_lexico_lt (p
, i
, j
))
511 cloog_pol_exchange_rows (p
, i
, j
);
513 /* Sort inequalities. */
514 for (i
= nbeq
; i
< cloog_pol_nbc (p
); i
++)
515 for (j
= i
+ 1; j
< cloog_pol_nbc (p
); j
++)
516 if (cloog_pol_lexico_lt (p
, i
, j
))
517 cloog_pol_exchange_rows (p
, i
, j
);
520 static inline CloogMatrix
*
521 cloog_upol_domain2matrix (polyhedra_union upol
)
523 return cloog_pol_matrix (cloog_upol_polyhedron (upol
));
527 cloog_vector_normalize (Value
* p
, unsigned len
)
530 Value
*ptr
, gcd
, one
;
533 cloog_vector_gcd (p
, len
, &gcd
);
535 value_set_si (one
, 1);
537 if (value_gt (gcd
, one
))
538 for (ptr
= p
, i
= 0; i
< len
; i
++, ptr
++)
539 value_division (*ptr
, *ptr
, gcd
);
541 value_clear (one
), value_clear (gcd
);
546 typedef struct matrix
{
547 unsigned NbRows
, NbColumns
;
550 int p_Init_size
; /* needed to free the memory allocated by mpz_init */
553 int SolveDiophantine(Matrix
*M
, Matrix
**U
, Vector
**X
);
554 Matrix
*Matrix_Alloc(unsigned NbRows
,unsigned NbColumns
);
556 static inline Matrix
*
557 m_c2p (CloogMatrix
*m
)
559 Matrix
*res
= Matrix_Alloc (m
->NbRows
, m
->NbColumns
);
562 for (i
= 0; i
< m
->NbRows
; i
++)
563 for (j
= 0; j
< m
->NbColumns
; j
++)
564 value_assign (res
->p
[i
][j
], m
->p
[i
][j
]);
569 static inline CloogMatrix
*
572 CloogMatrix
*res
= cloog_matrix_alloc (m
->NbRows
, m
->NbColumns
);
575 for (i
= 0; i
< m
->NbRows
; i
++)
576 for (j
= 0; j
< m
->NbColumns
; j
++)
577 value_assign (res
->p
[i
][j
], m
->p
[i
][j
]);
583 typedef struct polyhedron1
{
584 unsigned Dimension
, NbConstraints
, NbRays
, NbEq
, NbBid
;
589 struct polyhedron1
*next
;
590 #define POL_INEQUALITIES 0x00000001
591 #define POL_FACETS 0x00000002
592 #define POL_POINTS 0x00000004
593 #define POL_VERTICES 0x00000008
594 /* The flags field contains "valid" information,
595 * i.e., the structure was created by PolyLib.
597 #define POL_VALID 0x00000010
601 static inline void cloog_vector_scale (Value
* p1
, Value
* p2
,
607 for (i
= 0; i
< length
; i
++)
608 value_multiply (*p2
++, *p1
++, x
);
612 cloog_vector_combine (Value
* p1
, Value
* p2
, Value
* p3
, Value x
,
613 Value y
, unsigned length
)
620 for (i
= 0; i
< length
; i
++)
622 value_multiply (tmp
, x
, p1
[i
]);
623 value_addmul (tmp
, y
, p2
[i
]);
624 value_assign (p3
[i
], tmp
);
630 Polyhedron
* Polyhedron_Alloc(unsigned Dimension
,unsigned NbConstraints
,unsigned NbRays
);
631 Polyhedron
*Polyhedron_Copy(Polyhedron
*Pol
);
632 void Polyhedron_Print(FILE *Dst
,char *Format
,Polyhedron
*Pol
);
633 void Polyhedron_Free(Polyhedron
*Pol
);
634 Polyhedron
*Empty_Polyhedron(unsigned Dimension
);
635 void Matrix_Free(Matrix
*Mat
);
636 void Matrix_Print (FILE * Dst
, char *Format
, CloogMatrix
* Mat
);
639 static inline polyhedron
640 p_p2c (Polyhedron
*p
)
643 polyhedron res
= cloog_new_pol (p
->Dimension
, p
->NbConstraints
);
645 for (i
= 0; i
< p
->NbConstraints
; i
++)
646 for (j
= 0; j
< p
->Dimension
+ 2; j
++)
647 value_assign (res
->Constraint
[i
][j
], p
->Constraint
[i
][j
]);
652 static inline Polyhedron
*
656 Polyhedron
*res
= Polyhedron_Alloc (p
->Dimension
, p
->NbConstraints
, 0);
658 for (i
= 0; i
< p
->NbConstraints
; i
++)
659 for (j
= 0; j
< p
->Dimension
+ 2; j
++)
660 value_assign (res
->Constraint
[i
][j
], p
->Constraint
[i
][j
]);
672 #if defined(__cplusplus)
675 #endif /* define _H */