2 /**-------------------------------------------------------------------**
4 **-------------------------------------------------------------------**
6 **-------------------------------------------------------------------**
7 ** First version: october 28th 2001 **
8 **-------------------------------------------------------------------**/
11 /******************************************************************************
12 * CLooG : the Chunky Loop Generator (experimental) *
13 ******************************************************************************
15 * Copyright (C) 2001-2005 Cedric Bastoul *
17 * This is free software; you can redistribute it and/or modify it under the *
18 * terms of the GNU General Public License as published by the Free Software *
19 * Foundation; either version 2 of the License, or (at your option) any later *
22 * This software is distributed in the hope that it will be useful, but *
23 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY *
24 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License *
27 * You should have received a copy of the GNU General Public License along *
28 * with software; if not, write to the Free Software Foundation, Inc., *
29 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *
31 * CLooG, the Chunky Loop Generator *
32 * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr *
34 ******************************************************************************/
35 /* CAUTION: the english used for comments is probably the worst you ever read,
36 * please feel free to correct and improve it !
42 # include "../../include/cloog/cloog.h"
45 static int cloog_check_polyhedral_ops
= 1;
46 static int cloog_return_ppl_result
= 0;
47 static int cloog_print_debug
= 0;
50 print_result (char *s
, CloogDomain
*d
)
52 if (cloog_print_debug
)
54 fprintf (stderr
, "%s \n", s
);
55 debug_cloog_domain (d
);
60 /* Variables names for pretty printing. */
61 static char wild_name
[200][40];
63 static inline const char*
64 variable_output_function (ppl_dimension_type var
)
67 return wild_name
[var
+ 1];
73 error_handler (enum ppl_enum_error_code code
, const char* description
)
75 fprintf (stderr
, "PPL error code %d\n%s", code
, description
);
80 cloog_initialize (void)
82 sprintf (wild_name
[0], "1");
83 sprintf (wild_name
[1], "a");
84 sprintf (wild_name
[2], "b");
85 sprintf (wild_name
[3], "c");
86 sprintf (wild_name
[4], "d");
87 sprintf (wild_name
[5], "e");
88 sprintf (wild_name
[6], "f");
89 sprintf (wild_name
[7], "g");
90 sprintf (wild_name
[8], "h");
91 sprintf (wild_name
[9], "i");
92 sprintf (wild_name
[10], "j");
93 sprintf (wild_name
[11], "k");
94 sprintf (wild_name
[12], "l");
95 sprintf (wild_name
[13], "m");
96 sprintf (wild_name
[14], "n");
97 sprintf (wild_name
[15], "o");
98 sprintf (wild_name
[16], "p");
99 sprintf (wild_name
[17], "q");
100 sprintf (wild_name
[18], "r");
101 sprintf (wild_name
[19], "s");
102 sprintf (wild_name
[20], "t");
103 sprintf (wild_name
[21], "alpha");
104 sprintf (wild_name
[22], "beta");
105 sprintf (wild_name
[23], "gamma");
106 sprintf (wild_name
[24], "delta");
107 sprintf (wild_name
[25], "tau");
108 sprintf (wild_name
[26], "sigma");
109 sprintf (wild_name
[27], "chi");
110 sprintf (wild_name
[28], "omega");
111 sprintf (wild_name
[29], "pi");
112 sprintf (wild_name
[30], "ni");
113 sprintf (wild_name
[31], "Alpha");
114 sprintf (wild_name
[32], "Beta");
115 sprintf (wild_name
[33], "Gamma");
116 sprintf (wild_name
[34], "Delta");
117 sprintf (wild_name
[35], "Tau");
118 sprintf (wild_name
[36], "Sigma");
119 sprintf (wild_name
[37], "Chi");
120 sprintf (wild_name
[38], "Omega");
121 sprintf (wild_name
[39], "xxx");
123 if (ppl_initialize() < 0)
125 fprintf (stderr
, "Cannot initialize the Parma Polyhedra Library.\n");
129 if (ppl_set_error_handler (error_handler
) < 0)
131 fprintf (stderr
, "Cannot install the custom error handler.\n");
135 if (ppl_io_set_variable_output_function (variable_output_function
) < 0)
137 fprintf (stderr
, "Cannot install the PPL custom variable output function. \n");
142 static inline Polyhedron
*
143 u2p (ppl_polyhedra_union
* upol
)
145 Polyhedron
*res
= Polyhedron_Copy (cloog_upol_polyhedron (upol
));
150 ppl_polyhedra_union
*next
= cloog_upol_next (upol
);
154 n
= Polyhedron_Copy (cloog_upol_polyhedron (next
));
166 static inline Polyhedron
*
167 d2p (CloogDomain
* d
)
169 return u2p (cloog_domain_upol (d
));
173 static inline ppl_polyhedra_union
*
176 ppl_polyhedra_union
*u
= cloog_new_upol (p
);
177 ppl_polyhedra_union
*res
= u
;
181 Polyhedron
*next
= p
->next
;
182 ppl_polyhedra_union
*n
;
185 n
= cloog_new_upol (next
);
189 cloog_upol_set_next (u
, n
);
199 * The maximal number of rays allowed to be allocated by PolyLib. In fact since
200 * version 5.20, PolyLib automatically tune the number of rays by multiplying
201 * by 2 this number each time the maximum is reached. For unknown reasons
202 * PolyLib makes a segmentation fault if this number is too small. If this
203 * number is too small, performances will be reduced, if it is too high, memory
204 * will be saturated. Note that the option "-rays X" set this number to X.
208 /* Unused in this backend. */
210 int cloog_domain_allocated
= 0;
211 int cloog_domain_freed
= 0;
212 int cloog_domain_max
= 0;
214 /* The same for Value variables since in GMP mode they have to be freed. */
215 int cloog_value_allocated
= 0;
216 int cloog_value_freed
= 0;
217 int cloog_value_max
= 0;
221 cloog_value_leak_up ()
223 cloog_value_allocated
++;
224 if ((cloog_value_allocated
- cloog_value_freed
) > cloog_value_max
)
225 cloog_value_max
= cloog_value_allocated
- cloog_value_freed
;
230 cloog_value_leak_down ()
236 cloog_domain_polyhedron_set (CloogDomain
* d
, ppl_polyhedra_union
* p
)
242 cloog_domain_set_references (CloogDomain
* d
, int i
)
248 cloog_new_domain (ppl_polyhedra_union
*p
)
250 CloogDomain
*domain
= (CloogDomain
*) malloc (sizeof (CloogDomain
));
251 domain
->_polyhedron
= p
;
252 cloog_domain_set_references (domain
, 1);
257 cloog_domain_alloc (Polyhedron
*p
)
259 return print_result ("cloog_domain_alloc", cloog_new_domain (p2u (p
)));
263 debug_polyhedron (Polyhedron
*p
)
265 debug_cloog_domain (cloog_domain_alloc (p
));
268 static inline CloogDomain
*
269 cloog_check_domain_id (CloogDomain
*dom
)
274 static inline CloogDomain
*
275 cloog_check_domain (CloogDomain
*dom
)
280 /* FIXME: Remove this check. */
281 if (cloog_domain_polyhedron (dom
)->next
)
283 fprintf (stderr
, "polyhedra of domains should be convex.\n");
291 * cloog_domain_matrix2domain function:
292 * Given a matrix of constraints (matrix), this function constructs and returns
293 * the corresponding domain (i.e. the CloogDomain structure including the
294 * polyhedron with its double representation: constraint matrix and the set of
298 cloog_domain_matrix2domain (CloogMatrix
* matrix
)
300 return print_result ("cloog_domain_matrix2domain", cloog_check_domain (cloog_domain_alloc (Constraints2Polyhedron (matrix
, MAX_RAYS
))));
303 static inline CloogMatrix
*
304 cloog_upol_domain2matrix (ppl_polyhedra_union
* upol
)
306 return Polyhedron2Constraints (cloog_upol_polyhedron (upol
));
309 /* In the matrix representation an equality has a 0 in the first
310 column. When the value of the first column is 1, the row
311 represents an inequality. */
314 cloog_matrix_row_is_eq_p (CloogMatrix
*matrix
, int row
)
316 return value_zero_p (matrix
->p
[row
][0]);
319 static ppl_Constraint_t
320 cloog_build_ppl_cstr (ppl_Linear_Expression_t expr
, int ineq
)
322 ppl_Constraint_t cstr
;
327 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
331 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_THAN_OR_EQUAL
);
335 /* Should not happen. */
342 /* Translates to PPL row I from MATRIX. CST is the constant part that
343 is added to the constraint. When INEQ is 1 the constraint is
344 translated as an inequality, when INEQ is 0 it is translated as an
345 equality, when INEQ has another value, the first column of the
346 matrix is read for determining the type of the constraint. */
348 static ppl_Constraint_t
349 cloog_translate_constraint (CloogMatrix
*matrix
, int i
, int cst
, int ineq
)
352 ppl_Constraint_t res
;
353 ppl_Coefficient_t coef
;
354 ppl_Linear_Expression_t expr
;
355 ppl_dimension_type dim
= matrix
->NbColumns
- 2;
359 ppl_new_Coefficient (&coef
);
360 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
362 for (j
= 1; j
< matrix
->NbColumns
- 1; j
++)
364 ppl_assign_Coefficient_from_mpz_t (coef
, matrix
->p
[i
][j
]);
365 ppl_Linear_Expression_add_to_coefficient (expr
, j
- 1, coef
);
368 value_set_si (val
, cst
);
369 value_addto (val
, matrix
->p
[i
][matrix
->NbColumns
- 1], val
);
370 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
371 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
372 ppl_delete_Coefficient (coef
);
374 if (ineq
!= 0 && ineq
!= 1)
375 ineq
= !cloog_matrix_row_is_eq_p (matrix
, i
);
377 res
= cloog_build_ppl_cstr (expr
, ineq
);
378 ppl_delete_Linear_Expression (expr
);
382 /* Translates to PPL the opposite of row I from MATRIX. When INEQ is
383 1 the constraint is translated as an inequality, when INEQ is 0 it
384 is translated as an equality, when INEQ has another value, the
385 first column of the matrix is read for determining the type of the
388 static ppl_Constraint_t
389 cloog_translate_oppose_constraint (CloogMatrix
*matrix
, int i
, int cst
, int ineq
)
392 ppl_Constraint_t res
;
393 ppl_Coefficient_t coef
;
394 ppl_Linear_Expression_t expr
;
395 ppl_dimension_type dim
= matrix
->NbColumns
- 2;
400 ppl_new_Coefficient (&coef
);
401 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
403 for (j
= 1; j
< matrix
->NbColumns
- 1; j
++)
405 value_oppose (val
, matrix
->p
[i
][j
]);
406 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
407 ppl_Linear_Expression_add_to_coefficient (expr
, j
- 1, coef
);
410 value_oppose (val
, matrix
->p
[i
][matrix
->NbColumns
- 1]);
411 value_set_si (val1
, cst
);
412 value_addto (val
, val
, val1
);
413 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
414 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
415 ppl_delete_Coefficient (coef
);
417 if (ineq
!= 0 && ineq
!= 1)
418 ineq
= !cloog_matrix_row_is_eq_p (matrix
, i
);
420 res
= cloog_build_ppl_cstr (expr
, ineq
);
421 ppl_delete_Linear_Expression (expr
);
425 /* Adds to PPL the constraints from MATRIX. */
428 cloog_translate_constraint_matrix_1 (ppl_Polyhedron_t ppl
, CloogMatrix
*matrix
)
432 for (i
= 0; i
< matrix
->NbRows
; i
++)
434 ppl_Constraint_t c
= cloog_translate_constraint (matrix
, i
, 0, -1);
435 ppl_Polyhedron_add_constraint (ppl
, c
);
436 ppl_delete_Constraint (c
);
440 static ppl_Polyhedron_t
441 cloog_translate_constraint_matrix (CloogMatrix
*matrix
)
443 ppl_Polyhedron_t ppl
;
444 ppl_dimension_type dim
= matrix
->NbColumns
- 2;
446 ppl_new_NNC_Polyhedron_from_dimension (&ppl
, dim
);
447 cloog_translate_constraint_matrix_1 (ppl
, matrix
);
452 cloog_translate_ppl_polyhedron (ppl_Polyhedron_t pol
)
455 CloogMatrix
*matrix
;
456 ppl_dimension_type dim
;
457 ppl_const_Constraint_System_t pcs
;
458 ppl_Constraint_System_const_iterator_t cit
, end
;
461 ppl_Polyhedron_constraints (pol
, &pcs
);
462 ppl_new_Constraint_System_const_iterator (&cit
);
463 ppl_new_Constraint_System_const_iterator (&end
);
465 for (row
= 0, ppl_Constraint_System_begin (pcs
, cit
), ppl_Constraint_System_end (pcs
, end
);
466 !ppl_Constraint_System_const_iterator_equal_test (cit
, end
);
467 ppl_Constraint_System_const_iterator_increment (cit
), row
++);
469 ppl_Polyhedron_space_dimension (pol
, &dim
);
470 matrix
= cloog_matrix_alloc (row
, dim
+ 2);
472 for (row
= 0, ppl_Constraint_System_begin (pcs
, cit
), ppl_Constraint_System_end (pcs
, end
);
473 !ppl_Constraint_System_const_iterator_equal_test (cit
, end
);
474 ppl_Constraint_System_const_iterator_increment (cit
), row
++)
476 ppl_const_Constraint_t pc
;
477 ppl_Coefficient_t coef
;
478 ppl_dimension_type col
;
483 ppl_new_Coefficient (&coef
);
484 ppl_Constraint_System_const_iterator_dereference (cit
, &pc
);
486 neg
= (ppl_Constraint_type (pc
) == PPL_CONSTRAINT_TYPE_LESS_THAN
487 || ppl_Constraint_type (pc
) == PPL_CONSTRAINT_TYPE_LESS_THAN_OR_EQUAL
) ? 1 : 0;
489 for (col
= 0; col
< dim
; col
++)
491 ppl_Constraint_coefficient (pc
, col
, coef
);
492 ppl_Coefficient_to_mpz_t (coef
, val
);
495 value_oppose (val
, val
);
497 value_assign (matrix
->p
[row
][col
+1], val
);
500 ppl_Constraint_inhomogeneous_term (pc
, coef
);
501 ppl_Coefficient_to_mpz_t (coef
, val
);
502 value_assign (matrix
->p
[row
][dim
+ 1], val
);
503 ppl_delete_Coefficient (coef
);
505 switch (ppl_Constraint_type (pc
))
507 case PPL_CONSTRAINT_TYPE_EQUAL
:
508 value_set_si (matrix
->p
[row
][0], 0);
511 case PPL_CONSTRAINT_TYPE_LESS_THAN
:
512 case PPL_CONSTRAINT_TYPE_GREATER_THAN
:
513 value_decrement (matrix
->p
[row
][dim
+ 1], matrix
->p
[row
][dim
+ 1]);
514 value_set_si (matrix
->p
[row
][0], 1);
517 case PPL_CONSTRAINT_TYPE_LESS_THAN_OR_EQUAL
:
518 case PPL_CONSTRAINT_TYPE_GREATER_THAN_OR_EQUAL
:
519 value_set_si (matrix
->p
[row
][0], 1);
523 fprintf (stderr
, "PPL_CONSTRAINT_TYPE_%d not implemented yet\n",
524 ppl_Constraint_type (pc
));
528 ppl_delete_Constraint_System_const_iterator (cit
);
529 ppl_delete_Constraint_System_const_iterator (end
);
531 res
= cloog_domain_matrix2domain (matrix
);
532 return print_result ("cloog_translate_ppl_polyhedron", cloog_check_domain (res
));
535 void debug_poly (Polyhedron
*p
)
537 Polyhedron_Print (stderr
, P_VALUE_FMT
, p
);
541 debug_ppl_poly (ppl_Polyhedron_t p
)
543 debug_poly (cloog_domain_polyhedron (cloog_translate_ppl_polyhedron (p
)));
547 cloog_domain_references (CloogDomain
* d
)
549 return d
->_references
;
553 * cloog_domain_print function:
554 * This function prints the content of a CloogDomain structure (domain) into
555 * a file (foo, possibly stdout).
558 cloog_domain_print (FILE * foo
, CloogDomain
* domain
)
560 ppl_polyhedra_union
*upol
= cloog_domain_upol (domain
);
564 Polyhedron_Print (foo
, P_VALUE_FMT
, cloog_upol_polyhedron (upol
));
565 upol
= cloog_upol_next (upol
);
568 fprintf (foo
, "Number of active references: %d\n",
569 cloog_domain_references (domain
));
573 * cloog_domain_free function:
574 * This function frees the allocated memory for a CloogDomain structure
575 * (domain). It decrements the number of active references to this structure,
576 * if there are no more references on the structure, it frees it (with the
577 * included list of polyhedra).
580 cloog_domain_free (CloogDomain
* domain
)
584 cloog_domain_set_references (domain
,
585 cloog_domain_references (domain
) - 1);
587 if (cloog_domain_references (domain
) == 0)
590 ppl_polyhedra_union
*upol
= cloog_domain_upol (domain
);
594 Polyhedron_Free (cloog_upol_polyhedron (upol
));
595 upol
= cloog_upol_next (upol
);
605 * cloog_domain_copy function:
606 * This function returns a copy of a CloogDomain structure (domain). To save
607 * memory this is not a memory copy but we increment a counter of active
608 * references inside the structure, then return a pointer to that structure.
611 cloog_domain_copy (CloogDomain
* domain
)
613 cloog_domain_set_references (domain
, cloog_domain_references (domain
) + 1);
614 return print_result ("cloog_domain_copy", domain
);
617 static CloogDomain
*cloog_domain_difference_1 (CloogDomain
*, CloogDomain
*);
620 cloog_check_domains (CloogDomain
*ppl
, CloogDomain
*polylib
)
622 /* Cannot use cloog_domain_lazy_equal (polylib, ppl) here as this
623 function is too dumb: it does not detect permutations of
625 if (!cloog_domain_isempty (cloog_domain_difference_1 (ppl
, polylib
))
626 || !cloog_domain_isempty (cloog_domain_difference_1 (polylib
, ppl
)))
628 fprintf (stderr
, "different domains ( \n ppl (\n");
629 cloog_domain_print (stderr
, ppl
);
630 fprintf (stderr
, ") \n polylib (\n");
631 cloog_domain_print (stderr
, polylib
);
632 fprintf (stderr
, "))\n");
636 if (cloog_return_ppl_result
)
643 * cloog_domain_convex function:
644 * Given a polyhedral domain (polyhedron), this function concatenates the lists
645 * of rays and lines of the two (or more) polyhedra in the domain into one
646 * combined list, and find the set of constraints which tightly bound all of
647 * those objects. It returns the corresponding polyhedron.
650 cloog_domain_convex (CloogDomain
* domain
)
654 ppl_polyhedra_union
*upol
= cloog_domain_upol (domain
);
655 CloogMatrix
*m
= cloog_upol_domain2matrix (upol
);
656 ppl_Polyhedron_t p1
= cloog_translate_constraint_matrix (m
);
658 upol
= cloog_upol_next (upol
);
661 ppl_const_Generator_System_t g
;
663 m
= cloog_upol_domain2matrix (upol
);
664 p2
= cloog_translate_constraint_matrix (m
);
665 ppl_Polyhedron_generators (p2
, &g
);
666 ppl_Polyhedron_add_generators_and_minimize (p1
, g
);
667 ppl_delete_Polyhedron (p2
);
669 upol
= cloog_upol_next (upol
);
672 res
= cloog_translate_ppl_polyhedron (p1
);
673 ppl_delete_Polyhedron (p1
);
675 return print_result ("cloog_domain_convex", res
);
678 static inline unsigned
679 cloog_upol_nbc (ppl_polyhedra_union
* p
)
681 return cloog_upol_polyhedron (p
)->NbConstraints
;
685 cloog_domain_nbconstraints (CloogDomain
* domain
)
687 return cloog_domain_polyhedron (domain
)->NbConstraints
;
690 static inline unsigned
691 cloog_upol_nbeq (ppl_polyhedra_union
* d
)
693 return cloog_upol_polyhedron (d
)->NbEq
;
696 static inline unsigned
697 cloog_domain_nbeq (CloogDomain
* d
)
699 return cloog_domain_polyhedron (d
)->NbEq
;
702 static inline unsigned
703 cloog_upol_dim (ppl_polyhedra_union
* p
)
705 return cloog_upol_polyhedron (p
)->Dimension
;
709 cloog_domain_isconvex (CloogDomain
* domain
)
711 if (cloog_domain_polyhedron (domain
))
712 return !cloog_upol_next (cloog_domain_upol (domain
));
718 cloog_domain_dim (CloogDomain
* d
)
720 return cloog_domain_polyhedron (d
)->Dimension
;
724 * cloog_domain_simple_convex:
725 * Given a list (union) of polyhedra, this function returns a "simple"
726 * convex hull of this union. In particular, the constraints of the
727 * the returned polyhedron consist of (parametric) lower and upper
728 * bounds on individual variables and constraints that appear in the
729 * original polyhedra.
731 * nb_par is the number of parameters of the domain.
734 cloog_domain_simple_convex (CloogDomain
* domain
, int nb_par
)
736 fprintf (stderr
, "cloog_domain_simple_convex is not implemented yet.\n");
740 /* Returns non-zero when the constraint I in MATRIX is the positivity
741 constraint: "0 >= 0". */
744 cloog_positivity_constraint_p (CloogMatrix
*matrix
, int i
, int dim
)
748 for (j
= 1; j
< dim
; j
++)
749 if (value_notzero_p (matrix
->p
[i
][j
]))
755 /* Returns one when the constraint C is not in P, returns zero when C
759 non_redundant_constraint (ppl_Constraint_t c
, ppl_Polyhedron_t p
)
761 int rel
= ppl_Polyhedron_relation_with_Constraint (p
, c
);
763 if (rel
& PPL_POLY_CON_RELATION_IS_DISJOINT
)
766 if (rel
& PPL_POLY_CON_RELATION_IS_INCLUDED
)
769 if (rel
& PPL_POLY_CON_RELATION_STRICTLY_INTERSECTS
)
771 ppl_Constraint_System_t cs
;
773 ppl_const_Generator_System_t g
;
774 ppl_Generator_System_const_iterator_t git
, end
;
775 ppl_const_Generator_t cg
;
777 ppl_new_Constraint_System_from_Constraint (&cs
, c
);
778 ppl_new_NNC_Polyhedron_from_Constraint_System (&p1
, cs
);
779 ppl_Polyhedron_generators (p1
, &g
);
780 ppl_new_Generator_System_const_iterator (&git
);
781 ppl_new_Generator_System_const_iterator (&end
);
783 for (ppl_Generator_System_begin (g
, git
), ppl_Generator_System_end (g
, end
);
784 !ppl_Generator_System_const_iterator_equal_test (git
, end
);
785 ppl_Generator_System_const_iterator_increment (git
))
787 ppl_Generator_System_const_iterator_dereference (git
, &cg
);
788 rel
= ppl_Polyhedron_relation_with_Generator (p
, cg
);
790 if (!(rel
& PPL_POLY_GEN_RELATION_SUBSUMES
))
793 ppl_delete_Constraint_System (cs
);
794 ppl_delete_Polyhedron (p1
);
795 ppl_delete_Generator_System_const_iterator (git
);
796 ppl_delete_Generator_System_const_iterator (end
);
798 /* All generators are redundant. */
799 if (rel
& PPL_POLY_GEN_RELATION_SUBSUMES
)
806 /* Returns 1 if adding constraint C to polyhedron P changes the number
807 of constraints of P. */
810 changes_constraints (ppl_Constraint_t c
, ppl_Polyhedron_t p
)
812 int a1
= 0, a2
= 0, a3
= 0, a4
= 0, a5
= 0;
813 int b1
= 0, b2
= 0, b3
= 0, b4
= 0, b5
= 0;
815 ppl_const_Constraint_System_t g
;
816 ppl_Constraint_System_const_iterator_t git
, end
;
818 ppl_new_Constraint_System_const_iterator (&git
);
819 ppl_new_Constraint_System_const_iterator (&end
);
820 ppl_Polyhedron_minimized_constraints (p
, &g
);
822 for (ppl_Constraint_System_begin (g
, git
), ppl_Constraint_System_end (g
, end
);
823 !ppl_Constraint_System_const_iterator_equal_test (git
, end
);
824 ppl_Constraint_System_const_iterator_increment (git
))
826 ppl_const_Constraint_t pg
;
828 ppl_Constraint_System_const_iterator_dereference (git
, &pg
);
829 switch (ppl_Constraint_type (pg
))
831 case PPL_CONSTRAINT_TYPE_LESS_THAN
:
835 case PPL_CONSTRAINT_TYPE_LESS_THAN_OR_EQUAL
:
839 case PPL_CONSTRAINT_TYPE_EQUAL
:
843 case PPL_CONSTRAINT_TYPE_GREATER_THAN_OR_EQUAL
:
847 case PPL_CONSTRAINT_TYPE_GREATER_THAN
:
856 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q
, p
);
857 ppl_Polyhedron_add_constraint_and_minimize (q
, c
);
858 ppl_Polyhedron_minimized_constraints (q
, &g
);
860 for (ppl_Constraint_System_begin (g
, git
), ppl_Constraint_System_end (g
, end
);
861 !ppl_Constraint_System_const_iterator_equal_test (git
, end
);
862 ppl_Constraint_System_const_iterator_increment (git
))
864 ppl_const_Constraint_t pg
;
866 ppl_Constraint_System_const_iterator_dereference (git
, &pg
);
867 switch (ppl_Constraint_type (pg
))
869 case PPL_CONSTRAINT_TYPE_LESS_THAN
:
873 case PPL_CONSTRAINT_TYPE_LESS_THAN_OR_EQUAL
:
877 case PPL_CONSTRAINT_TYPE_EQUAL
:
881 case PPL_CONSTRAINT_TYPE_GREATER_THAN_OR_EQUAL
:
885 case PPL_CONSTRAINT_TYPE_GREATER_THAN
:
894 ppl_delete_Constraint_System_const_iterator (git
);
895 ppl_delete_Constraint_System_const_iterator (end
);
896 ppl_delete_Polyhedron (q
);
898 if (a1
!= b1
|| a2
!= b2
|| a3
!= b3
|| a4
!= b4
|| a5
!= b5
)
904 /* Returns 1 if adding constraint C to polyhedron P changes the
908 changes_generators (ppl_Constraint_t c
, ppl_Polyhedron_t p
)
913 ppl_const_Generator_System_t g
;
914 ppl_Generator_System_const_iterator_t git
, end
;
916 ppl_new_Generator_System_const_iterator (&git
);
917 ppl_new_Generator_System_const_iterator (&end
);
918 ppl_Polyhedron_minimized_generators (p
, &g
);
920 for (ppl_Generator_System_begin (g
, git
), ppl_Generator_System_end (g
, end
);
921 !ppl_Generator_System_const_iterator_equal_test (git
, end
);
922 ppl_Generator_System_const_iterator_increment (git
))
924 ppl_const_Generator_t pg
;
926 ppl_Generator_System_const_iterator_dereference (git
, &pg
);
927 switch (ppl_Generator_type (pg
))
929 case PPL_GENERATOR_TYPE_LINE
:
930 case PPL_GENERATOR_TYPE_RAY
:
934 case PPL_GENERATOR_TYPE_POINT
:
935 case PPL_GENERATOR_TYPE_CLOSURE_POINT
:
944 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q
, p
);
945 ppl_Polyhedron_add_constraint (q
, c
);
946 ppl_Polyhedron_minimized_generators (q
, &g
);
948 for (ppl_Generator_System_begin (g
, git
), ppl_Generator_System_end (g
, end
);
949 !ppl_Generator_System_const_iterator_equal_test (git
, end
);
950 ppl_Generator_System_const_iterator_increment (git
))
952 ppl_const_Generator_t pg
;
954 ppl_Generator_System_const_iterator_dereference (git
, &pg
);
955 switch (ppl_Generator_type (pg
))
957 case PPL_GENERATOR_TYPE_LINE
:
958 case PPL_GENERATOR_TYPE_RAY
:
962 case PPL_GENERATOR_TYPE_POINT
:
963 case PPL_GENERATOR_TYPE_CLOSURE_POINT
:
972 ppl_delete_Generator_System_const_iterator (git
);
973 ppl_delete_Generator_System_const_iterator (end
);
974 ppl_delete_Polyhedron (q
);
976 if (a1
>= b1
&& a2
>= b2
)
982 /* Simplifies DOM1 in the context of DOM2. For example, DOM1 can
983 contain the following conditions: i >= 0, i <= 5, and DOM2 is a
984 loop around, i.e. the context of DOM1, that also contains the
985 conditions i >= 0, i <= 5. So instead of generating a loop like:
987 | for (i = 0; i < 6; i++)
989 | if (i >= 0 && i <= 5)
993 this function allows to detect that in the context of DOM2, the
994 constraints of DOM1 are redundant, and so the following code should
997 | for (i = 0; i < 6; i++)
1002 cloog_domain_simplify (CloogDomain
* dom1
, CloogDomain
* dom2
)
1005 CloogDomain
*res
= NULL
;
1006 ppl_polyhedra_union
*u1
, *u2
;
1007 unsigned dim
= cloog_domain_dim (dom1
);
1008 CloogDomain
*inter
= cloog_domain_intersection (dom1
, dom2
);
1010 for (u1
= cloog_domain_upol (inter
); u1
; u1
= cloog_upol_next (u1
))
1012 CloogMatrix
*m1
= cloog_upol_domain2matrix (u1
);
1014 for (u2
= cloog_domain_upol (dom2
); u2
; u2
= cloog_upol_next (u2
))
1016 CloogMatrix
*m2
= cloog_upol_domain2matrix (u2
);
1017 ppl_Polyhedron_t p2
= cloog_translate_constraint_matrix (m2
);
1018 ppl_Polyhedron_t p3
;
1020 ppl_new_NNC_Polyhedron_from_dimension (&p3
, dim
);
1022 for (i
= 0; i
< m1
->NbRows
; i
++)
1023 if (!cloog_positivity_constraint_p (m1
, i
, dim
+ 1))
1025 ppl_Constraint_t c1
= cloog_translate_constraint (m1
, i
, 0, -1);
1027 if (non_redundant_constraint (c1
, p2
)
1028 || changes_generators (c1
, p2
)
1029 || changes_constraints (c1
, p2
))
1030 ppl_Polyhedron_add_constraint_and_minimize (p3
, c1
);
1032 ppl_delete_Constraint (c1
);
1035 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (p3
));
1037 ppl_delete_Polyhedron (p2
);
1038 ppl_delete_Polyhedron (p3
);
1042 return print_result ("cloog_domain_simplify", res
);
1046 static ppl_polyhedra_union
*
1047 cloog_upol_copy (ppl_polyhedra_union
*p
)
1049 ppl_polyhedra_union
*res
= cloog_new_upol (Polyhedron_Copy (cloog_upol_polyhedron (p
)));
1050 ppl_polyhedra_union
*upol
= res
;
1052 while (cloog_upol_next (p
))
1054 cloog_upol_set_next (upol
, cloog_new_upol (Polyhedron_Copy (cloog_upol_polyhedron (p
))));
1055 upol
= cloog_upol_next (upol
);
1056 p
= cloog_upol_next (p
);
1062 /* Adds to D1 the union of polyhedra from D2, with no checks of
1063 redundancies between polyhedra. */
1066 cloog_domain_add_domain (CloogDomain
*d1
, CloogDomain
*d2
)
1068 ppl_polyhedra_union
*upol
;
1076 upol
= cloog_domain_upol (d1
);
1077 while (cloog_upol_next (upol
))
1078 upol
= cloog_upol_next (upol
);
1080 cloog_upol_set_next (upol
, cloog_domain_upol (d2
));
1085 * cloog_domain_union function:
1086 * This function returns a new CloogDomain structure including a polyhedral
1087 * domain which is the union of two polyhedral domains (pol1) U (pol2) inside
1088 * two CloogDomain structures.
1091 cloog_domain_union (CloogDomain
* dom1
, CloogDomain
* dom2
)
1094 ppl_polyhedra_union
*head1
, *head2
, *tail1
, *tail2
;
1095 ppl_polyhedra_union
*d1
, *d2
;
1103 if (cloog_domain_dim (dom1
) != cloog_domain_dim (dom2
))
1105 fprintf (stderr
, "cloog_domain_union should not be called on domains of different dimensions.\n");
1111 for (d1
= cloog_domain_upol (dom1
); d1
; d1
= cloog_upol_next (d1
))
1114 ppl_Polyhedron_t ppl1
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (d1
));
1116 for (d2
= cloog_domain_upol (dom2
); d2
; d2
= cloog_upol_next (d2
))
1118 ppl_Polyhedron_t ppl2
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (d2
));
1120 if (ppl_Polyhedron_contains_Polyhedron (ppl2
, ppl1
))
1122 ppl_delete_Polyhedron (ppl2
);
1126 ppl_delete_Polyhedron (ppl2
);
1128 ppl_delete_Polyhedron (ppl1
);
1134 head1
= cloog_upol_copy (d1
);
1139 cloog_upol_set_next (tail1
, cloog_upol_copy (d1
));
1140 tail1
= cloog_upol_next (tail1
);
1147 for (d2
= cloog_domain_upol (dom2
); d2
; d2
= cloog_upol_next (d2
))
1150 ppl_Polyhedron_t ppl2
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (d2
));
1152 for (d1
= head1
; d1
; d1
= cloog_upol_next (d1
))
1154 ppl_Polyhedron_t ppl1
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (d1
));
1156 if (ppl_Polyhedron_contains_Polyhedron (ppl1
, ppl2
))
1158 ppl_delete_Polyhedron (ppl1
);
1162 ppl_delete_Polyhedron (ppl1
);
1164 ppl_delete_Polyhedron (ppl2
);
1170 head2
= cloog_upol_copy (d2
);
1175 cloog_upol_set_next (tail2
, cloog_upol_copy (d2
));
1176 tail2
= cloog_upol_next (tail2
);
1182 res
= cloog_new_domain (head2
);
1185 cloog_upol_set_next (tail1
, head2
);
1186 res
= cloog_new_domain (head1
);
1189 if (cloog_check_polyhedral_ops
)
1191 Polyhedron
*p1
= d2p (dom1
);
1192 Polyhedron
*p2
= d2p (dom2
);
1194 cloog_check_domains (res
, cloog_domain_alloc (DomainUnion (p1
, p2
, MAX_RAYS
)));
1196 Polyhedron_Free (p1
);
1197 Polyhedron_Free (p2
);
1200 return print_result ("cloog_domain_union", cloog_check_domain (res
));
1204 * cloog_domain_intersection function:
1205 * This function returns a new CloogDomain structure including a polyhedral
1206 * domain which is the intersection of two polyhedral domains (pol1)inter(pol2)
1207 * inside two CloogDomain structures.
1210 cloog_domain_intersection (CloogDomain
* dom1
, CloogDomain
* dom2
)
1212 CloogDomain
*res
= NULL
;
1213 ppl_polyhedra_union
*p1
, *p2
;
1214 ppl_Polyhedron_t ppl1
, ppl2
;
1216 for (p1
= cloog_domain_upol (dom1
); p1
; p1
= cloog_upol_next (p1
))
1218 ppl1
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (p1
));
1220 for (p2
= cloog_domain_upol (dom2
); p2
; p2
= cloog_upol_next (p2
))
1222 ppl2
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (p2
));
1223 ppl_Polyhedron_intersection_assign (ppl2
, ppl1
);
1224 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (ppl2
));
1225 ppl_delete_Polyhedron (ppl2
);
1227 ppl_delete_Polyhedron (ppl1
);
1230 if (cloog_check_polyhedral_ops
)
1232 Polyhedron
*a1
= d2p (dom1
);
1233 Polyhedron
*a2
= d2p (dom2
);
1235 res
= cloog_check_domains (res
, cloog_domain_alloc (DomainIntersection (a1
, a2
, MAX_RAYS
)));
1237 Polyhedron_Free (a1
);
1238 Polyhedron_Free (a2
);
1241 return print_result ("cloog_domain_intersection", res
);
1246 * cloog_domain_difference function:
1247 * This function returns a new CloogDomain structure including a polyhedral
1248 * domain which is the difference of two polyhedral domains domain \ minus
1249 * inside two CloogDomain structures.
1250 * - November 8th 2001: first version.
1253 static CloogDomain
*
1254 cloog_domain_difference_1 (CloogDomain
* domain
, CloogDomain
* minus
)
1256 if (cloog_domain_isempty (minus
))
1257 return print_result ("cloog_domain_difference", cloog_domain_copy (domain
));
1260 Polyhedron
*p1
= d2p (domain
);
1261 Polyhedron
*p2
= d2p (minus
);
1262 CloogDomain
*res
= cloog_domain_alloc (DomainDifference (p1
, p2
, MAX_RAYS
));
1263 Polyhedron_Free (p1
);
1264 Polyhedron_Free (p2
);
1265 return print_result ("cloog_domain_difference", res
);
1269 /* Returns d1 minus d2. */
1272 cloog_domain_difference (CloogDomain
* d1
, CloogDomain
* d2
)
1274 CloogDomain
*res
= NULL
, *d
= d1
;
1275 ppl_polyhedra_union
*p1
, *p2
;
1277 if (cloog_domain_isempty (d2
))
1278 return print_result ("cloog_domain_difference", cloog_domain_copy (d1
));
1280 for (p2
= cloog_domain_upol (d2
); p2
; p2
= cloog_upol_next (p2
))
1282 CloogMatrix
*matrix
= cloog_upol_domain2matrix (p2
);
1284 for (p1
= cloog_domain_upol (d
); p1
; p1
= cloog_upol_next (p1
))
1287 CloogMatrix
*m1
= cloog_upol_domain2matrix (p1
);
1289 for (i
= 0; i
< matrix
->NbRows
; i
++)
1291 ppl_Polyhedron_t p3
;
1292 ppl_Constraint_t cstr
;
1294 /* Don't handle "0 >= 0". */
1295 if (cloog_positivity_constraint_p (matrix
, i
,
1296 cloog_domain_dim (d
) + 1))
1299 /* Add the constraint "-matrix[i] - 1 >= 0". */
1300 p3
= cloog_translate_constraint_matrix (m1
);
1301 cstr
= cloog_translate_oppose_constraint (matrix
, i
, -1, 1);
1302 ppl_Polyhedron_add_constraint_and_minimize (p3
, cstr
);
1303 ppl_delete_Constraint (cstr
);
1304 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (p3
));
1305 ppl_delete_Polyhedron (p3
);
1307 /* For an equality, add the constraint "matrix[i] - 1 >= 0". */
1308 if (cloog_matrix_row_is_eq_p (matrix
, i
))
1310 p3
= cloog_translate_constraint_matrix (m1
);
1311 cstr
= cloog_translate_constraint (matrix
, i
, -1, 1);
1312 ppl_Polyhedron_add_constraint_and_minimize (p3
, cstr
);
1313 ppl_delete_Constraint (cstr
);
1314 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (p3
));
1315 ppl_delete_Polyhedron (p3
);
1324 res
= cloog_domain_empty (cloog_domain_dim (d2
));
1328 if (cloog_check_polyhedral_ops
)
1329 return print_result ("cloog_domain_difference", cloog_check_domains
1330 (res
, cloog_domain_difference_1 (d1
, d2
)));
1332 return print_result ("cloog_domain_difference", res
);
1337 * cloog_domain_addconstraints function :
1338 * This function adds source's polyhedron constraints to target polyhedron: for
1339 * each element of the polyhedron inside 'target' (i.e. element of the union
1340 * of polyhedra) it adds the constraints of the corresponding element in
1342 * - August 10th 2002: first version.
1343 * Nota bene for future : it is possible that source and target don't have the
1344 * same number of elements (try iftest2 without non-shared constraint
1345 * elimination in cloog_loop_separate !). This function is yet another part
1346 * of the DomainSimplify patching problem...
1349 cloog_domain_addconstraints (CloogDomain
*domain_source
, CloogDomain
*domain_target
)
1352 ppl_Polyhedron_t ppl
;
1353 ppl_polyhedra_union
*source
, *target
, *last
;
1354 int dim
= cloog_domain_dim (domain_target
);
1356 source
= cloog_domain_upol (domain_source
);
1357 target
= cloog_domain_upol (domain_target
);
1359 ppl_new_NNC_Polyhedron_from_dimension (&ppl
, dim
);
1360 cloog_translate_constraint_matrix_1 (ppl
, cloog_upol_domain2matrix (target
));
1361 cloog_translate_constraint_matrix_1 (ppl
, cloog_upol_domain2matrix (source
));
1362 res
= cloog_translate_ppl_polyhedron (ppl
);
1363 ppl_delete_Polyhedron (ppl
);
1364 last
= cloog_domain_upol (res
);
1366 source
= cloog_upol_next (source
);
1367 target
= cloog_upol_next (target
);
1371 ppl_new_NNC_Polyhedron_from_dimension (&ppl
, dim
);
1372 cloog_translate_constraint_matrix_1 (ppl
, cloog_upol_domain2matrix (target
));
1376 cloog_translate_constraint_matrix_1 (ppl
, cloog_upol_domain2matrix (source
));
1377 source
= cloog_upol_next (source
);
1381 (last
, cloog_domain_upol (cloog_translate_ppl_polyhedron (ppl
)));
1382 ppl_delete_Polyhedron (ppl
);
1384 last
= cloog_upol_next (last
);
1385 target
= cloog_upol_next (target
);
1388 return print_result ("cloog_domain_addconstraints", res
);
1391 /* Compares P1 to P2: returns 0 when the polyhedra don't overlap,
1392 returns 1 when p1 >= p2, and returns -1 when p1 < p2. The ">"
1393 relation is the "contains" relation. */
1396 cloog_domain_polyhedron_compare (CloogMatrix
*m1
, CloogMatrix
*m2
, int level
, int nb_par
, int dimension
)
1399 ppl_Polyhedron_t q1
, q2
, q3
, q4
, q5
, q
;
1400 ppl_Polyhedron_t p1
, p2
;
1402 p1
= cloog_translate_constraint_matrix (m1
);
1403 if (ppl_Polyhedron_is_empty (p1
))
1405 ppl_delete_Polyhedron (p1
);
1409 p2
= cloog_translate_constraint_matrix (m2
);
1410 if (ppl_Polyhedron_is_empty (p2
))
1412 ppl_delete_Polyhedron (p2
);
1416 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q1
, p1
);
1417 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q2
, p2
);
1419 for (i
= level
; i
< dimension
- nb_par
+ 1; i
++)
1422 ppl_Coefficient_t d
;
1423 ppl_Linear_Expression_t expr
;
1427 value_set_si (val
, 1);
1428 ppl_new_Coefficient_from_mpz_t (&d
, val
);
1429 ppl_new_Linear_Expression_with_dimension (&expr
, dimension
);
1430 ppl_Linear_Expression_add_to_coefficient (expr
, i
- 1, d
);
1431 ppl_new_Generator (&g
, expr
, PPL_GENERATOR_TYPE_LINE
, d
);
1432 ppl_Polyhedron_add_generator (q1
, g
);
1433 ppl_Polyhedron_add_generator (q2
, g
);
1434 ppl_delete_Generator (g
);
1435 ppl_delete_Linear_Expression (expr
);
1436 ppl_delete_Coefficient (d
);
1439 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q
, q1
);
1440 ppl_Polyhedron_intersection_assign (q
, q2
);
1441 ppl_delete_Polyhedron (q1
);
1442 ppl_delete_Polyhedron (q2
);
1444 if (ppl_Polyhedron_is_empty (q
))
1446 ppl_delete_Polyhedron (p1
);
1447 ppl_delete_Polyhedron (p2
);
1448 ppl_delete_Polyhedron (q
);
1452 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q1
, p1
);
1453 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q2
, p2
);
1454 ppl_delete_Polyhedron (p1
);
1455 ppl_delete_Polyhedron (p2
);
1457 ppl_Polyhedron_intersection_assign (q1
, q
);
1458 ppl_Polyhedron_intersection_assign (q2
, q
);
1460 m1
= cloog_upol_domain2matrix (cloog_domain_upol (cloog_translate_ppl_polyhedron (q1
)));
1461 m2
= cloog_upol_domain2matrix (cloog_domain_upol (cloog_translate_ppl_polyhedron (q2
)));
1463 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q4
, q
);
1464 for (i
= 0; i
< m1
->NbRows
; i
++)
1465 if (value_one_p (m1
->p
[i
][0])
1466 && value_pos_p (m1
->p
[i
][level
]))
1468 ppl_Constraint_t c
= cloog_translate_constraint (m1
, i
, 0, 1);
1469 ppl_Polyhedron_add_constraint (q4
, c
);
1470 ppl_delete_Constraint (c
);
1473 for (i
= 0; i
< m2
->NbRows
; i
++)
1474 if (value_one_p (m2
->p
[i
][0])
1475 && value_neg_p (m2
->p
[i
][level
]))
1477 ppl_Constraint_t c
= cloog_translate_constraint (m2
, i
, 0, 1);
1478 ppl_Polyhedron_add_constraint (q4
, c
);
1479 ppl_delete_Constraint (c
);
1482 if (ppl_Polyhedron_is_empty (q4
))
1484 ppl_delete_Polyhedron (q
);
1485 ppl_delete_Polyhedron (q1
);
1486 ppl_delete_Polyhedron (q2
);
1487 ppl_delete_Polyhedron (q4
);
1491 ppl_delete_Polyhedron (q4
);
1492 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q3
, q
);
1493 for (i
= 0; i
< m1
->NbRows
; i
++)
1495 if (value_zero_p (m1
->p
[i
][0]))
1497 if (value_zero_p (m1
->p
[i
][level
]))
1500 else if (value_neg_p (m1
->p
[i
][level
]))
1502 ppl_Constraint_t c
= cloog_translate_oppose_constraint (m1
, i
, 0, 1);
1503 ppl_Polyhedron_add_constraint (q3
, c
);
1504 ppl_delete_Constraint (c
);
1509 ppl_Constraint_t c
= cloog_translate_constraint (m1
, i
, 0, 1);
1510 ppl_Polyhedron_add_constraint (q3
, c
);
1511 ppl_delete_Constraint (c
);
1515 else if (value_neg_p (m1
->p
[i
][level
]))
1517 ppl_Constraint_t c
= cloog_translate_oppose_constraint (m1
, i
, 0, 1);
1518 ppl_Polyhedron_add_constraint (q3
, c
);
1519 ppl_delete_Constraint (c
);
1525 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q5
, q3
);
1526 for (j
= 0; j
< m2
->NbRows
; j
++)
1528 if (value_zero_p (m2
->p
[j
][0]))
1530 if (value_zero_p (m2
->p
[j
][level
]))
1533 else if (value_pos_p (m2
->p
[j
][level
]))
1535 ppl_Constraint_t c
= cloog_translate_oppose_constraint (m2
, j
, 0, 1);
1536 ppl_Polyhedron_add_constraint (q5
, c
);
1537 ppl_delete_Constraint (c
);
1542 ppl_Constraint_t c
= cloog_translate_constraint (m2
, j
, 0, 1);
1543 ppl_Polyhedron_add_constraint (q5
, c
);
1544 ppl_delete_Constraint (c
);
1548 else if (value_pos_p (m2
->p
[j
][level
]))
1550 ppl_Constraint_t c
= cloog_translate_oppose_constraint (m2
, j
, 0, 1);
1551 ppl_Polyhedron_add_constraint (q5
, c
);
1552 ppl_delete_Constraint (c
);
1558 if (!ppl_Polyhedron_is_empty (q5
))
1560 ppl_delete_Polyhedron (q
);
1561 ppl_delete_Polyhedron (q1
);
1562 ppl_delete_Polyhedron (q2
);
1563 ppl_delete_Polyhedron (q3
);
1564 ppl_delete_Polyhedron (q5
);
1568 /* Reinitialize Q5. */
1569 ppl_delete_Polyhedron (q5
);
1570 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q5
, q3
);
1573 /* Reinitialize Q3. */
1574 ppl_delete_Polyhedron (q3
);
1575 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q3
, q
);
1578 ppl_delete_Polyhedron (q
);
1579 ppl_delete_Polyhedron (q1
);
1580 ppl_delete_Polyhedron (q2
);
1581 ppl_delete_Polyhedron (q3
);
1582 ppl_delete_Polyhedron (q5
);
1587 * cloog_domain_sort function:
1588 * This function topologically sorts (nb_pols) polyhedra. Here (pols) is a an
1589 * array of pointers to polyhedra, (nb_pols) is the number of polyhedra,
1590 * (level) is the level to consider for partial ordering (nb_par) is the
1591 * parameter space dimension, (permut) if not NULL, is an array of (nb_pols)
1592 * integers that contains a permutation specification after call in order to
1593 * apply the topological sorting.
1597 cloog_domain_sort (CloogDomain
**doms
, unsigned nb_pols
, unsigned level
,
1598 unsigned nb_par
, int *permut
)
1601 int dim
= cloog_domain_dim (doms
[0]);
1603 for (i
= 0; i
< nb_pols
; i
++)
1606 /* Note that here we do a comparison per tuple of polyhedra.
1607 PolyLib does not do this, but instead it does fewer comparisons
1608 and with a complex reasoning they infer that it some comparisons
1609 are not useful. The result is that PolyLib has wrong permutations.
1611 FIXME: In the PolyLib backend, Cloog should use this algorithm
1612 instead of PolyhedronTSort, and cloog_domain_polyhedron_compare
1613 should be implemented with a simple call to PolyhedronLTQ: these
1614 two functions produce identical answers. */
1615 for (i
= 0; i
< nb_pols
; i
++)
1616 for (j
= i
+ 1; j
< nb_pols
; j
++)
1618 CloogMatrix
*m1
= cloog_upol_domain2matrix (cloog_domain_upol (doms
[i
]));
1619 CloogMatrix
*m2
= cloog_upol_domain2matrix (cloog_domain_upol (doms
[j
]));
1621 if (cloog_domain_polyhedron_compare (m1
, m2
, level
, nb_par
, dim
) == 1)
1624 permut
[i
] = permut
[j
];
1631 * cloog_domain_empty function:
1632 * This function allocates the memory space for a CloogDomain structure and
1633 * sets its polyhedron to an empty polyhedron with 'dimension' dimensions.
1634 * Then it returns a pointer to the allocated space.
1635 * - June 10th 2005: first version.
1638 cloog_domain_empty (int dimension
)
1640 return (cloog_domain_alloc (Empty_Polyhedron (dimension
)));
1644 /******************************************************************************
1645 * Structure display function *
1646 ******************************************************************************/
1650 * cloog_domain_print_structure :
1651 * this function is a more human-friendly way to display the CloogDomain data
1652 * structure, it only shows the constraint system and includes an indentation
1653 * level (level) in order to work with others print_structure functions.
1654 * Written by Olivier Chorier, Luc Marchaud, Pierre Martin and Romain Tartiere.
1655 * - April 24th 2005: Initial version.
1656 * - May 26th 2005: Memory leak hunt.
1657 * - June 16th 2005: (Ced) Integration in domain.c.
1660 cloog_domain_print_structure (FILE * file
, CloogDomain
* domain
, int level
)
1663 CloogMatrix
*matrix
;
1665 /* Go to the right level. */
1666 for (i
= 0; i
< level
; i
++)
1667 fprintf (file
, "|\t");
1671 fprintf (file
, "+-- CloogDomain\n");
1673 /* Print the matrix. */
1674 matrix
= cloog_upol_domain2matrix (cloog_domain_upol (domain
));
1675 cloog_matrix_print_structure (file
, matrix
, level
);
1676 cloog_matrix_free (matrix
);
1679 for (i
= 0; i
< level
+ 1; i
++)
1680 fprintf (file
, "|\t");
1681 fprintf (file
, "\n");
1684 fprintf (file
, "+-- Null CloogDomain\n");
1690 * cloog_domain_list_print function:
1691 * This function prints the content of a CloogDomainList structure into a
1692 * file (foo, possibly stdout).
1693 * - November 6th 2001: first version.
1696 cloog_domain_list_print (FILE * foo
, CloogDomainList
* list
)
1698 while (list
!= NULL
)
1700 cloog_domain_print (foo
, cloog_domain (list
));
1701 list
= cloog_next_domain (list
);
1706 /******************************************************************************
1707 * Memory deallocation function *
1708 ******************************************************************************/
1712 * cloog_domain_list_free function:
1713 * This function frees the allocated memory for a CloogDomainList structure.
1714 * - November 6th 2001: first version.
1717 cloog_domain_list_free (CloogDomainList
* list
)
1719 CloogDomainList
*temp
;
1721 while (list
!= NULL
)
1723 temp
= cloog_next_domain (list
);
1724 cloog_domain_free (cloog_domain (list
));
1731 /******************************************************************************
1732 * Reading function *
1733 ******************************************************************************/
1737 * cloog_domain_read function:
1738 * Adaptation from the PolyLib. This function reads a matrix into a file (foo,
1739 * posibly stdin) and returns a pointer to a polyhedron containing the read
1741 * - October 18th 2001: first version.
1744 cloog_domain_read (FILE * foo
)
1746 CloogMatrix
*matrix
;
1747 CloogDomain
*domain
;
1749 matrix
= cloog_matrix_read (foo
);
1750 domain
= cloog_domain_matrix2domain (matrix
);
1751 cloog_matrix_free (matrix
);
1753 return print_result ("cloog_domain_read", domain
);
1758 * cloog_domain_union_read function:
1759 * This function reads a union of polyhedra into a file (foo, posibly stdin) and
1760 * returns a pointer to a Polyhedron containing the read information.
1761 * - September 9th 2002: first version.
1762 * - October 29th 2005: (debug) removal of a leak counting "correction" that
1763 * was just false since ages.
1766 cloog_domain_union_read (FILE * foo
)
1768 int i
, nb_components
;
1770 CloogDomain
*domain
, *temp
, *old
;
1772 /* domain reading: nb_components (constraint matrices). */
1773 while (fgets (s
, MAX_STRING
, foo
) == 0);
1774 while ((*s
== '#' || *s
== '\n') || (sscanf (s
, " %d", &nb_components
) < 1))
1775 fgets (s
, MAX_STRING
, foo
);
1777 if (nb_components
> 0)
1778 { /* 1. first part of the polyhedra union, */
1779 domain
= cloog_domain_read (foo
);
1780 /* 2. and the nexts. */
1781 for (i
= 1; i
< nb_components
; i
++)
1782 { /* Leak counting is OK since next allocated domain is freed here. */
1783 temp
= cloog_domain_read (foo
);
1785 domain
= cloog_domain_union (temp
, old
);
1786 cloog_domain_free (temp
);
1787 cloog_domain_free (old
);
1789 return print_result ("cloog_domain_union_read", cloog_check_domain (domain
));
1797 * cloog_domain_list_read function:
1798 * This function reads a list of polyhedra into a file (foo, posibly stdin) and
1799 * returns a pointer to a CloogDomainList containing the read information.
1800 * - November 6th 2001: first version.
1803 cloog_domain_list_read (FILE * foo
)
1807 CloogDomainList
*list
, *now
, *next
;
1810 /* We read first the number of polyhedra in the list. */
1811 while (fgets (s
, MAX_STRING
, foo
) == 0);
1812 while ((*s
== '#' || *s
== '\n') || (sscanf (s
, " %d", &nb_pols
) < 1))
1813 fgets (s
, MAX_STRING
, foo
);
1815 /* Then we read the polyhedra. */
1819 list
= (CloogDomainList
*) malloc (sizeof (CloogDomainList
));
1820 cloog_set_domain (list
, cloog_domain_read (foo
));
1821 cloog_set_next_domain (list
, NULL
);
1823 for (i
= 1; i
< nb_pols
; i
++)
1825 next
= (CloogDomainList
*) malloc (sizeof (CloogDomainList
));
1826 cloog_set_domain (next
, cloog_domain_read (foo
));
1827 cloog_set_next_domain (next
, NULL
);
1828 cloog_set_next_domain (now
, next
);
1829 now
= cloog_next_domain (now
);
1836 /******************************************************************************
1837 * Processing functions *
1838 ******************************************************************************/
1841 * cloog_domain_isempty function:
1842 * This function returns 1 if the polyhedron given as input is empty, 0
1844 * - October 28th 2001: first version.
1847 cloog_domain_isempty (CloogDomain
* domain
)
1849 if (cloog_domain_polyhedron (domain
) == NULL
)
1852 if (cloog_upol_next (cloog_domain_upol (domain
)))
1855 return ((cloog_domain_dim (domain
) < cloog_domain_nbeq (domain
)) ? 1 : 0);
1859 * cloog_domain_project function:
1860 * From Quillere's LoopGen 0.4. This function returns the projection of
1861 * (domain) on the (level) first dimensions (i.e. outer loops). It returns a
1862 * pointer to the projected Polyhedron.
1863 * - nb_par is the number of parameters.
1865 * - October 27th 2001: first version.
1866 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1870 cloog_domain_project (CloogDomain
* domain
, int level
, int nb_par
)
1872 CloogDomain
*res
= NULL
;
1873 ppl_polyhedra_union
*upol
= cloog_domain_upol (domain
);
1874 int i
, diff
= cloog_domain_dim (domain
) - level
- nb_par
;
1876 ppl_dimension_type
*to_remove
;
1880 fprintf (stderr
, "cloog_domain_project should not be called with"
1881 "cloog_domain_dim (domain) < level + nb_par");
1886 return print_result ("cloog_domain_project", cloog_domain_copy (domain
));
1889 to_remove
= (ppl_dimension_type
*) malloc (n
* sizeof (ppl_dimension_type
));
1891 for (i
= 0; i
< n
; i
++)
1892 to_remove
[i
] = i
+ level
;
1896 ppl_Polyhedron_t ppl
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (upol
));
1898 ppl_Polyhedron_remove_space_dimensions (ppl
, to_remove
, n
);
1899 res
= cloog_domain_add_domain (res
, cloog_translate_ppl_polyhedron (ppl
));
1900 ppl_delete_Polyhedron (ppl
);
1901 upol
= cloog_upol_next (upol
);
1904 return print_result ("cloog_domain_project", res
);
1908 * cloog_domain_extend function:
1909 * From Quillere's LoopGen 0.4. This function returns the (domain) given as
1910 * input with (dim)+(nb_par) dimensions. The new dimensions are added before
1911 * the (nb_par) parameters. This function does not free (domain), and returns
1913 * - nb_par is the number of parameters.
1915 * - October 27th 2001: first version.
1916 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1920 cloog_domain_extend (CloogDomain
* domain
, int dim
, int nb_par
)
1922 CloogDomain
*res
= NULL
;
1923 ppl_polyhedra_union
*upol
= cloog_domain_upol (domain
);
1924 int i
, k
, n
, diff
= dim
+ nb_par
- cloog_domain_dim (domain
);
1925 ppl_dimension_type
*map
;
1926 ppl_dimension_type to_add
= diff
;
1929 return print_result ("cloog_domain_extend", cloog_domain_copy (domain
));
1932 map
= (ppl_dimension_type
*) malloc (n
* sizeof (ppl_dimension_type
));
1934 k
= cloog_domain_dim (domain
) - nb_par
;
1935 for (i
= 0; i
< k
; i
++)
1944 map
[i
] = i
- nb_par
;
1948 ppl_Polyhedron_t ppl
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (upol
));
1950 ppl_Polyhedron_add_space_dimensions_and_embed (ppl
, to_add
);
1951 ppl_Polyhedron_map_space_dimensions (ppl
, map
, n
);
1952 res
= cloog_domain_add_domain (res
, cloog_translate_ppl_polyhedron (ppl
));
1953 ppl_delete_Polyhedron (ppl
);
1954 upol
= cloog_upol_next (upol
);
1957 return print_result ("cloog_domain_extend", res
);
1961 * cloog_domain_never_integral function:
1962 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0. This
1963 * function returns a boolean set to 1 if there is this kind of 'never true'
1964 * constraint inside a polyhedron, 0 otherwise.
1965 * - domain is the polyhedron to check,
1967 * - November 28th 2001: first version.
1968 * - June 26th 2003: for iterators, more 'never true' constraints are found
1969 * (compare cholesky2 and vivien with a previous version),
1970 * checking for the parameters created (compare using vivien).
1971 * - June 28th 2003: Previously in loop.c and called
1972 * cloog_loop_simplify_nevertrue, now here !
1973 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1975 * - October 14th 2005: Complete rewriting, not faster but code quite shorter.
1978 cloog_domain_never_integral (CloogDomain
* domain
)
1980 int i
, dimension
, nbc
;
1982 Polyhedron
*polyhedron
;
1984 if ((domain
== NULL
) || (cloog_domain_polyhedron (domain
) == NULL
))
1988 value_init_c (modulo
);
1989 polyhedron
= d2p (domain
);
1990 dimension
= cloog_domain_dim (domain
) + 2;
1991 nbc
= cloog_domain_nbconstraints (domain
);
1993 /* For each constraint... */
1994 for (i
= 0; i
< nbc
; i
++)
1995 { /* If we have an equality and the scalar part is not zero... */
1996 if (value_zero_p (polyhedron
->Constraint
[i
][0]) &&
1997 value_notzero_p (polyhedron
->Constraint
[i
][dimension
- 1]))
1998 { /* Then we check whether the scalar can be divided by the gcd of the
1999 * unknown vector (including iterators and parameters) or not. If not,
2000 * there is no integer point in the polyhedron and we return 1.
2002 Vector_Gcd (&(polyhedron
->Constraint
[i
][1]), dimension
- 2, &gcd
);
2003 value_modulus (modulo
,
2004 polyhedron
->Constraint
[i
][dimension
- 1],
2007 if (value_notzero_p (modulo
))
2009 value_clear_c (gcd
);
2010 value_clear_c (modulo
);
2011 Polyhedron_Free (polyhedron
);
2017 value_clear_c (gcd
);
2018 value_clear_c (modulo
);
2019 Polyhedron_Free (polyhedron
);
2025 * cloog_domain_stride function:
2026 * This function finds the stride imposed to unknown with the column number
2027 * 'strided_level' in order to be integral. For instance, if we have a
2028 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
2029 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
2030 * the unknown i. The function returns the imposed stride in a parameter field.
2031 * - domain is the set of constraint we have to consider,
2032 * - strided_level is the column number of the unknown for which a stride have
2034 * - looking_level is the column number of the unknown that impose a stride to
2035 * the first unknown.
2036 * - stride is the stride that is returned back as a function parameter.
2037 * - offset is the value of the constant c if the condition is of the shape
2038 * (i + c)%s = 0, s being the stride.
2040 * - June 28th 2003: first version.
2041 * - July 14th 2003: can now look for multiple striding constraints and returns
2042 * the GCD of the strides and the common offset.
2043 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2047 cloog_domain_stride (domain
, strided_level
, nb_par
, stride
, offset
)
2048 CloogDomain
*domain
;
2049 int strided_level
, nb_par
;
2050 Value
*stride
, *offset
;
2053 int n_col
, n_row
, rank
;
2057 Polyhedron
*polyhedron
= d2p (domain
);
2058 int dimension
= cloog_domain_dim (domain
);
2059 int nbeq
= cloog_domain_nbeq (domain
);
2061 /* Look at all equalities involving strided_level and the inner
2062 * iterators. We can ignore the outer iterators and the parameters
2063 * here because the lower bound on strided_level is assumed to
2066 n_col
= (1 + dimension
- nb_par
) - strided_level
;
2067 for (i
= 0, n_row
= 0; i
< nbeq
; i
++)
2069 (polyhedron
->Constraint
[i
] + strided_level
, n_col
) != -1)
2072 M
= cloog_matrix_alloc (n_row
+ 1, n_col
+ 1);
2073 for (i
= 0, n_row
= 0; i
< nbeq
; i
++)
2076 (polyhedron
->Constraint
[i
] + strided_level
, n_col
) == -1)
2078 Vector_Copy (polyhedron
->Constraint
[i
] + strided_level
,
2079 M
->p
[n_row
], n_col
);
2080 value_assign (M
->p
[n_row
][n_col
],
2081 polyhedron
->Constraint
[i
][1 + dimension
]);
2084 value_set_si (M
->p
[n_row
][n_col
], 1);
2086 /* Then look at the general solution to the above equalities. */
2087 rank
= SolveDiophantine (M
, &U
, &V
);
2088 cloog_matrix_free (M
);
2092 /* There is no solution, so the body of this loop will
2093 * never execute. We just leave the constraints alone here so
2094 * that they will ensure the body will not be executed.
2095 * We should probably propagate this information up so that
2096 * the loop can be removed entirely.
2098 value_set_si (*offset
, 0);
2099 value_set_si (*stride
, 1);
2103 /* Compute the gcd of the coefficients defining strided_level. */
2104 Vector_Gcd (U
->p
[0], U
->NbColumns
, stride
);
2105 value_oppose (*offset
, V
->p
[0]);
2106 value_pmodulus (*offset
, *offset
, *stride
);
2110 Polyhedron_Free (polyhedron
);
2116 * cloog_domain_integral_lowerbound function:
2117 * This function returns 1 if the lower bound of an iterator (such as its
2118 * column rank in the constraint set 'domain' is 'level') is integral,
2119 * 0 otherwise. If the lower bound is actually integral, the function fills
2120 * the 'lower' field with the lower bound value.
2121 * - June 29th 2003: first version.
2122 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2126 cloog_domain_integral_lowerbound (domain
, level
, lower
)
2127 CloogDomain
*domain
;
2131 int i
, first_lower
= 1, dimension
, lower_constraint
= -1, nbc
;
2132 Value iterator
, constant
, tmp
;
2133 Polyhedron
*polyhedron
;
2135 polyhedron
= d2p (domain
);
2136 dimension
= cloog_domain_dim (domain
);
2137 nbc
= cloog_domain_nbconstraints (domain
);
2139 /* We want one and only one lower bound (e.g. no equality, no maximum
2142 for (i
= 0; i
< nbc
; i
++)
2143 if (value_zero_p (polyhedron
->Constraint
[i
][0])
2144 && value_notzero_p (polyhedron
->Constraint
[i
][level
]))
2146 Polyhedron_Free (polyhedron
);
2150 for (i
= 0; i
< nbc
; i
++)
2151 if (value_pos_p (polyhedron
->Constraint
[i
][level
]))
2156 lower_constraint
= i
;
2160 Polyhedron_Free (polyhedron
);
2167 Polyhedron_Free (polyhedron
);
2171 /* We want an integral lower bound: no other non-zero entry except the
2172 * iterator coefficient and the constant.
2174 for (i
= 1; i
< level
; i
++)
2176 (polyhedron
->Constraint
[lower_constraint
][i
]))
2178 Polyhedron_Free (polyhedron
);
2182 for (i
= level
+ 1; i
<= dimension
; i
++)
2184 (polyhedron
->Constraint
[lower_constraint
][i
]))
2186 Polyhedron_Free (polyhedron
);
2190 value_init_c (iterator
);
2191 value_init_c (constant
);
2194 /* If all is passed, then find the lower bound and return 1. */
2195 value_assign (iterator
,
2196 polyhedron
->Constraint
[lower_constraint
][level
]);
2197 value_oppose (constant
,
2198 polyhedron
->Constraint
[lower_constraint
][dimension
+ 1]);
2200 value_modulus (tmp
, constant
, iterator
);
2201 value_division (*lower
, constant
, iterator
);
2203 if (!(value_zero_p (tmp
) || value_neg_p (constant
)))
2204 value_increment (*lower
, *lower
);
2206 value_clear_c (iterator
);
2207 value_clear_c (constant
);
2208 value_clear_c (tmp
);
2209 Polyhedron_Free (polyhedron
);
2215 * cloog_domain_lowerbound_update function:
2216 * This function updates the integral lower bound of an iterator (such as its
2217 * column rank in the constraint set 'domain' is 'level') into 'lower'.
2218 * - Jun 29th 2003: first version.
2219 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2223 cloog_domain_lowerbound_update (domain
, level
, lower
)
2224 CloogDomain
*domain
;
2229 int nbc
= cloog_domain_nbconstraints (domain
);
2230 int dim
= cloog_domain_dim (domain
);
2231 Polyhedron
*polyhedron
= cloog_domain_polyhedron (domain
);
2233 /* There is only one lower bound, the first one is the good one. */
2234 for (i
= 0; i
< nbc
; i
++)
2235 if (value_pos_p (polyhedron
->Constraint
[i
][level
]))
2237 value_set_si (polyhedron
->Constraint
[i
][level
], 1);
2238 value_oppose (polyhedron
->Constraint
[i
][dim
+ 1], lower
);
2245 * cloog_domain_lazy_equal function:
2246 * This function returns 1 if the domains given as input are the same, 0 if it
2247 * is unable to decide. This function makes an entry-to-entry comparison between
2248 * the constraint systems, if all the entries are the same, the domains are
2249 * obviously the same and it returns 1, at the first difference, it returns 0.
2250 * This is a very fast way to verify this property. It has been shown (with the
2251 * CLooG benchmarks) that operations on equal domains are 17% of all the
2252 * polyhedral computations. For 75% of the actually identical domains, this
2253 * function answer that they are the same and allow to give immediately the
2254 * trivial solution instead of calling the heavy general functions of PolyLib.
2255 * - August 22th 2003: first version.
2256 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2260 cloog_domain_lazy_equal (CloogDomain
* d1
, CloogDomain
* d2
)
2263 ppl_polyhedra_union
*u1
= cloog_domain_upol (d1
);
2264 ppl_polyhedra_union
*u2
= cloog_domain_upol (d2
);
2268 if ((cloog_upol_nbc (u1
) != cloog_upol_nbc (u2
)) ||
2269 (cloog_upol_dim (u1
) != cloog_upol_dim (u2
)))
2273 cloog_upol_nbc (u1
) * (cloog_upol_dim (u1
) + 2);
2275 for (i
= 0; i
< nb_elements
; i
++)
2276 if (value_ne (cloog_upol_polyhedron (u1
)->p_Init
[i
],
2277 cloog_upol_polyhedron (u2
)->p_Init
[i
]))
2280 u1
= cloog_upol_next (u1
);
2281 u2
= cloog_upol_next (u2
);
2292 * cloog_domain_lazy_block function:
2293 * This function returns 1 if the two domains d1 and d2 given as input are the
2294 * same (possibly except for a dimension equal to a constant where we accept
2295 * a difference of 1) AND if we are sure that there are no other domain in
2296 * the code generation problem that may put integral points between those of
2297 * d1 and d2 (0 otherwise). In fact this function answers the question "can I
2298 * safely consider the two domains as only one with two statements (a block) ?".
2299 * This function is lazy: it asks for very standard scattering representation
2300 * (only one constraint per dimension which is an equality, and the constraints
2301 * are ordered per dimension depth: the left hand side of the constraint matrix
2302 * is the identity) and will answer NO at the very first problem.
2303 * - d1 and d2 are the two domains to check for blocking,
2304 * - scattering is the linked list of all domains,
2305 * - scattdims is the total number of scattering dimentions.
2307 * - April 30th 2005: beginning
2308 * - June 9th 2005: first working version.
2309 * - June 10th 2005: debugging.
2310 * - June 21rd 2005: Adaptation for GMP.
2311 * - October 16th 2005: (debug) some false blocks have been removed.
2314 cloog_domain_lazy_block (d1
, d2
, scattering
, scattdims
)
2315 CloogDomain
*d1
, *d2
;
2316 CloogDomainList
*scattering
;
2319 int i
, j
, difference
= 0, different_constraint
= 0, nbc
;
2321 Value date1
, date2
, date3
, temp
;
2322 Polyhedron
*p1
, *p2
;
2324 /* Some basic checks: we only accept convex domains, with same constraint
2325 * and dimension numbers.
2327 if (!cloog_domain_isconvex (d1
) || !cloog_domain_isconvex (d2
) ||
2328 (cloog_domain_nbconstraints (d1
) != cloog_domain_nbconstraints (d2
)) ||
2329 (cloog_domain_dim (d1
) != cloog_domain_dim (d2
)))
2334 nbc
= cloog_domain_nbconstraints (d1
);
2335 dim1
= cloog_domain_dim (d1
);
2336 dim2
= cloog_domain_dim (d2
);
2338 /* There should be only one difference between the two domains, it
2339 * has to be at the constant level and the difference must be of +1,
2340 * moreover, after the difference all domain coefficient has to be 0.
2341 * The matrix shape is:
2343 * |===========|=====|<- 0 line
2344 * |===========|=====|
2345 * |===========|====?|<- different_constraint line (found here)
2346 * |===========|0000=|
2347 * |===========|0000=|<- pX->NbConstraints line
2350 * | | (pX->Dimension + 2) column
2351 * | scattdims column
2355 value_init_c (temp
);
2356 for (i
= 0; i
< nbc
; i
++)
2358 if (difference
== 0)
2359 { /* All elements except scalar must be equal. */
2360 for (j
= 0; j
< dim1
+ 1; j
++)
2361 if (value_ne (p1
->Constraint
[i
][j
],
2362 p2
->Constraint
[i
][j
]))
2364 value_clear_c (temp
);
2365 Polyhedron_Free (p1
);
2366 Polyhedron_Free (p2
);
2369 /* The scalar may differ from +1 (now j=(p1->Dimension + 1)). */
2370 if (value_ne (p1
->Constraint
[i
][j
],
2371 p2
->Constraint
[i
][j
]))
2373 value_increment (temp
, p2
->Constraint
[i
][j
]);
2374 if (value_ne (p1
->Constraint
[i
][j
], temp
))
2376 value_clear_c (temp
);
2377 Polyhedron_Free (p1
);
2378 Polyhedron_Free (p2
);
2384 different_constraint
= i
;
2389 { /* Scattering coefficients must be equal. */
2390 for (j
= 0; j
< (scattdims
+ 1); j
++)
2391 if (value_ne (p1
->Constraint
[i
][j
],
2392 p2
->Constraint
[i
][j
]))
2394 value_clear_c (temp
);
2395 Polyhedron_Free (p1
);
2396 Polyhedron_Free (p2
);
2400 /* Domain coefficients must be 0. */
2401 for (; j
< dim1
+ 1; j
++)
2402 if (value_notzero_p (p1
->Constraint
[i
][j
])
2403 || value_notzero_p (p2
->Constraint
[i
][j
]))
2405 value_clear_c (temp
);
2406 Polyhedron_Free (p1
);
2407 Polyhedron_Free (p2
);
2411 /* Scalar must be equal. */
2412 if (value_ne (p1
->Constraint
[i
][j
],
2413 p2
->Constraint
[i
][j
]))
2415 value_clear_c (temp
);
2416 Polyhedron_Free (p1
);
2417 Polyhedron_Free (p2
);
2422 value_clear_c (temp
);
2424 /* If the domains are exactly the same, this is a block. */
2425 if (difference
== 0)
2427 Polyhedron_Free (p1
);
2428 Polyhedron_Free (p2
);
2432 /* Now a basic check that the constraint with the difference is an
2433 * equality of a dimension with a constant.
2435 for (i
= 0; i
<= different_constraint
; i
++)
2436 if (value_notzero_p (p1
->Constraint
[different_constraint
][i
]))
2438 Polyhedron_Free (p1
);
2439 Polyhedron_Free (p2
);
2443 if (value_notone_p (p1
->Constraint
[different_constraint
][different_constraint
+ 1]))
2445 Polyhedron_Free (p1
);
2446 Polyhedron_Free (p2
);
2450 for (i
= different_constraint
+ 2; i
< dim1
+ 1; i
++)
2451 if (value_notzero_p (p1
->Constraint
[different_constraint
][i
]))
2453 Polyhedron_Free (p1
);
2454 Polyhedron_Free (p2
);
2458 /* For the moment, d1 and d2 are a block candidate. There remains to check
2459 * that there is no other domain that may put an integral point between
2460 * them. In our lazy test we ensure this property by verifying that the
2461 * constraint matrices have a very strict shape: let us consider that the
2462 * dimension with the difference is d. Then the first d dimensions are
2463 * defined in their depth order using equalities (thus the first column begins
2464 * with d zeroes, there is a d*d identity matrix and a zero-matrix for
2465 * the remaining simensions). If a domain can put integral points between the
2466 * domains of the block candidate, this means that the other entries on the
2467 * first d constraints are equal to those of d1 or d2. Thus we are looking for
2468 * such a constraint system, if it exists d1 and d2 is considered to not be
2469 * a block, it is a bock otherwise.
2471 * 1. Only equalities (for the first different_constraint+1 lines).
2472 * | 2. Must be the identity.
2473 * | | 3. Must be zero.
2474 * | | | 4. Elements are equal, the last one is either date1 or 2.
2477 * |0|100|00000|=====|<- 0 line
2478 * |0|010|00000|=====|
2479 * |0|001|00000|====?|<- different_constraint line
2480 * |*|***|*****|*****|
2481 * |*|***|*****|*****|<- pX->NbConstraints line
2484 * | | | (pX->Dimension + 2) column
2485 * | | scattdims column
2486 * | different_constraint+1 column
2490 /* Step 1 and 2. This is only necessary to check one domain because
2491 * we checked that they are equal on this part before.
2493 for (i
= 0; i
<= different_constraint
; i
++)
2495 for (j
= 0; j
< i
+ 1; j
++)
2496 if (value_notzero_p (p1
->Constraint
[i
][j
]))
2498 Polyhedron_Free (p1
);
2499 Polyhedron_Free (p2
);
2503 if (value_notone_p (p1
->Constraint
[i
][i
+ 1]))
2505 Polyhedron_Free (p1
);
2506 Polyhedron_Free (p2
);
2510 for (j
= i
+ 2; j
<= different_constraint
+ 1; j
++)
2511 if (value_notzero_p (p1
->Constraint
[i
][j
]))
2513 Polyhedron_Free (p1
);
2514 Polyhedron_Free (p2
);
2520 for (i
= 0; i
<= different_constraint
; i
++)
2521 for (j
= different_constraint
+ 2; j
<= scattdims
; j
++)
2522 if (value_notzero_p (p1
->Constraint
[i
][j
]))
2524 Polyhedron_Free (p1
);
2525 Polyhedron_Free (p2
);
2529 value_init_c (date1
);
2530 value_init_c (date2
);
2531 value_init_c (date3
);
2533 /* Now we have to check that the two different dates are unique. */
2534 value_assign (date1
, p1
->Constraint
[different_constraint
][dim1
+ 1]);
2535 value_assign (date2
, p2
->Constraint
[different_constraint
][dim2
+ 1]);
2537 /* Step 4. We check all domains except d1 and d2 and we look for at least
2538 * a difference with d1 or d2 on the first different_constraint+1 dimensions.
2540 while (scattering
!= NULL
)
2542 if ((cloog_domain (scattering
) != d1
)
2543 && (cloog_domain (scattering
) != d2
))
2545 CloogDomain
*d3
= cloog_domain (scattering
);
2546 Polyhedron
*p3
= d2p (d3
);
2547 int dim3
= cloog_domain_dim (d3
);
2549 value_assign (date3
,
2550 p3
->Constraint
[different_constraint
][dim3
+ 1]);
2553 if (value_ne (date3
, date2
) && value_ne (date3
, date1
))
2556 for (i
= 0; (i
< different_constraint
) && (!difference
); i
++)
2557 for (j
= 0; (j
< dim3
+ 2) && !difference
; j
++)
2559 (p1
->Constraint
[i
][j
],
2560 p3
->Constraint
[i
][j
]))
2563 for (j
= 0; (j
< dim3
+ 1) && !difference
; j
++)
2565 (p1
->Constraint
[different_constraint
][j
],
2566 p3
->Constraint
[different_constraint
][j
]))
2569 Polyhedron_Free (p3
);
2572 value_clear_c (date1
);
2573 value_clear_c (date2
);
2574 value_clear_c (date3
);
2575 Polyhedron_Free (p1
);
2576 Polyhedron_Free (p2
);
2581 scattering
= cloog_next_domain (scattering
);
2584 Polyhedron_Free (p1
);
2585 Polyhedron_Free (p2
);
2586 value_clear_c (date1
);
2587 value_clear_c (date2
);
2588 value_clear_c (date3
);
2594 * cloog_domain_lazy_disjoint function:
2595 * This function returns 1 if the domains given as input are disjoint, 0 if it
2596 * is unable to decide. This function finds the unknown with fixed values in
2597 * both domains (on a given constraint, their column entry is not zero and
2598 * only the constant coefficient can be different from zero) and verify that
2599 * their values are the same. If not, the domains are obviously disjoint and
2600 * it returns 1, if there is not such case it returns 0. This is a very fast
2601 * way to verify this property. It has been shown (with the CLooG benchmarks)
2602 * that operations on disjoint domains are 36% of all the polyhedral
2603 * computations. For 94% of the actually identical domains, this
2604 * function answer that they are disjoint and allow to give immediately the
2605 * trivial solution instead of calling the heavy general functions of PolyLib.
2606 * - August 22th 2003: first version.
2607 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2611 cloog_domain_lazy_disjoint (CloogDomain
* d1
, CloogDomain
* d2
)
2613 int i1
, j1
, i2
, j2
, scat_dim
, nbc1
, nbc2
;
2616 Polyhedron
*p1
, *p2
;
2618 if (!cloog_domain_isconvex (d1
) || !cloog_domain_isconvex (d2
))
2623 nbc1
= cloog_domain_nbconstraints (d1
);
2624 nbc2
= cloog_domain_nbconstraints (d2
);
2625 dim1
= cloog_domain_dim (d1
);
2626 dim2
= cloog_domain_dim (d2
);
2627 value_init_c (scat_val
);
2629 for (i1
= 0; i1
< nbc1
; i1
++)
2631 if (value_notzero_p (p1
->Constraint
[i1
][0]))
2635 while (value_zero_p (p1
->Constraint
[i1
][scat_dim
]) &&
2639 if (value_notone_p (p1
->Constraint
[i1
][scat_dim
]))
2643 for (j1
= scat_dim
+ 1; j1
<= dim1
; j1
++)
2644 if (value_notzero_p (p1
->Constraint
[i1
][j1
]))
2650 value_assign (scat_val
,
2651 p1
->Constraint
[i1
][dim1
+ 1]);
2653 for (i2
= 0; i2
< nbc2
; i2
++)
2655 for (j2
= 0; j2
< scat_dim
; j2
++)
2656 if (value_notzero_p (p2
->Constraint
[i2
][j2
]))
2659 if ((j2
!= scat_dim
)
2661 value_notone_p (p2
->Constraint
[i2
][scat_dim
]))
2664 for (j2
= scat_dim
+ 1; j2
< dim2
; j2
++)
2665 if (value_notzero_p (p2
->Constraint
[i2
][j2
]))
2672 (p2
->Constraint
[i2
][dim2
+ 1], scat_val
))
2674 value_clear_c (scat_val
);
2681 value_clear_c (scat_val
);
2682 Polyhedron_Free (p1
);
2683 Polyhedron_Free (p2
);
2689 * cloog_domain_list_lazy_same function:
2690 * This function returns 1 if two domains in the list are the same, 0 if it
2691 * is unable to decide.
2692 * - February 9th 2004: first version.
2695 cloog_domain_list_lazy_same (CloogDomainList
* list
)
2696 { /*int i=1, j=1 ; */
2697 CloogDomainList
*current
, *next
;
2700 while (current
!= NULL
)
2702 next
= cloog_next_domain (current
);
2704 while (next
!= NULL
)
2706 if (cloog_domain_lazy_equal (cloog_domain (current
),
2707 cloog_domain (next
)))
2708 { /*printf("Same domains: %d and %d\n",i,j) ; */
2712 next
= cloog_next_domain (next
);
2715 current
= cloog_next_domain (current
);
2722 * cloog_domain_cut_first function:
2723 * this function returns a CloogDomain structure with everything except the
2724 * first part of the polyhedra union of the input domain as domain. After a call
2725 * to this function, there remains in the CloogDomain structure provided as
2726 * input only the first part of the original polyhedra union.
2727 * - April 20th 2005: first version, extracted from different part of loop.c.
2730 cloog_domain_cut_first (CloogDomain
* domain
)
2734 if (domain
&& cloog_domain_polyhedron (domain
))
2736 if (!cloog_upol_next (cloog_domain_upol (domain
)))
2739 rest
= cloog_new_domain (cloog_upol_next (cloog_domain_upol (domain
)));
2740 cloog_upol_set_next (cloog_domain_upol (domain
), NULL
);
2745 return print_result ("cloog_domain_cut_first", cloog_check_domain (rest
));
2750 * cloog_domain_lazy_isscalar function:
2751 * this function returns 1 if the dimension 'dimension' in the domain 'domain'
2752 * is scalar, this means that the only constraint on this dimension must have
2753 * the shape "x.dimension + scalar = 0" with x an integral variable. This
2754 * function is lazy since we only accept x=1 (further calculations are easier
2756 * - June 14th 2005: first version.
2757 * - June 21rd 2005: Adaptation for GMP.
2760 cloog_domain_lazy_isscalar (CloogDomain
* domain
, int dimension
)
2763 Polyhedron
*polyhedron
= d2p (domain
);
2764 int nbc
= cloog_domain_nbconstraints (domain
);
2765 int dim
= cloog_domain_dim (domain
);
2767 /* For each constraint... */
2768 for (i
= 0; i
< nbc
; i
++)
2769 { /* ...if it is concerned by the potentially scalar dimension... */
2771 (polyhedron
->Constraint
[i
][dimension
+ 1]))
2772 { /* ...check that the constraint has the shape "dimension + scalar = 0". */
2773 for (j
= 0; j
<= dimension
; j
++)
2774 if (value_notzero_p (polyhedron
->Constraint
[i
][j
]))
2776 Polyhedron_Free (polyhedron
);
2781 (polyhedron
->Constraint
[i
][dimension
+ 1]))
2783 Polyhedron_Free (polyhedron
);
2787 for (j
= dimension
+ 2; j
< dim
+ 1; j
++)
2788 if (value_notzero_p (polyhedron
->Constraint
[i
][j
]))
2790 Polyhedron_Free (polyhedron
);
2796 Polyhedron_Free (polyhedron
);
2802 * cloog_domain_scalar function:
2803 * when we call this function, we know that "dimension" is a scalar dimension,
2804 * this function finds the scalar value in "domain" and returns it in "value".
2805 * - June 30th 2005: first version.
2808 cloog_domain_scalar (CloogDomain
* domain
, int dimension
, Value
* value
)
2811 Polyhedron
*polyhedron
= d2p (domain
);
2812 int nbc
= cloog_domain_nbconstraints (domain
);
2813 int dim
= cloog_domain_dim (domain
);
2815 /* For each constraint... */
2816 for (i
= 0; i
< nbc
; i
++)
2817 { /* ...if it is the equality defining the scalar dimension... */
2819 (polyhedron
->Constraint
[i
][dimension
+ 1])
2820 && value_zero_p (polyhedron
->Constraint
[i
][0]))
2821 { /* ...Then send the scalar value. */
2822 value_assign (*value
, polyhedron
->Constraint
[i
][dim
+ 1]);
2823 value_oppose (*value
, *value
);
2824 Polyhedron_Free (polyhedron
);
2829 /* We should have found a scalar value: if not, there is an error. */
2830 fprintf (stderr
, "[CLooG]ERROR: dimension %d is not scalar as expected.\n",
2832 Polyhedron_Free (polyhedron
);
2838 * cloog_domain_erase_dimension function:
2839 * this function returns a CloogDomain structure builds from 'domain' where
2840 * we removed the dimension 'dimension' and every constraint considering this
2841 * dimension. This is not a projection ! Every data concerning the
2842 * considered dimension is simply erased.
2843 * - June 14th 2005: first version.
2844 * - June 21rd 2005: Adaptation for GMP.
2847 cloog_domain_erase_dimension (CloogDomain
* domain
, int dimension
)
2849 int i
, j
, mi
, nb_dim
, nbc
;
2850 CloogMatrix
*matrix
;
2851 CloogDomain
*erased
;
2852 Polyhedron
*polyhedron
;
2854 polyhedron
= d2p (domain
);
2855 nb_dim
= cloog_domain_dim (domain
);
2856 nbc
= cloog_domain_nbconstraints (domain
);
2858 /* The matrix is one column less and at least one constraint less. */
2859 matrix
= cloog_matrix_alloc (nbc
- 1, nb_dim
+ 1);
2861 /* mi is the constraint counter for the matrix. */
2863 for (i
= 0; i
< nbc
; i
++)
2864 if (value_zero_p (polyhedron
->Constraint
[i
][dimension
+ 1]))
2866 for (j
= 0; j
<= dimension
; j
++)
2867 value_assign (matrix
->p
[mi
][j
],
2868 polyhedron
->Constraint
[i
][j
]);
2870 for (j
= dimension
+ 2; j
< nb_dim
+ 2; j
++)
2871 value_assign (matrix
->p
[mi
][j
- 1],
2872 polyhedron
->Constraint
[i
][j
]);
2877 erased
= cloog_domain_matrix2domain (matrix
);
2878 cloog_matrix_free (matrix
);
2880 Polyhedron_Free (polyhedron
);
2881 return print_result ("cloog_domain_erase_dimension", cloog_check_domain (erased
));
2884 /* Number of polyhedra inside the union of disjoint polyhedra. */
2887 cloog_domain_nb_polyhedra (CloogDomain
* domain
)
2890 ppl_polyhedra_union
*upol
= cloog_domain_upol (domain
);
2895 upol
= cloog_upol_next (upol
);
2902 cloog_domain_print_polyhedra (FILE * foo
, CloogDomain
* domain
)
2904 ppl_polyhedra_union
*upol
= cloog_domain_upol (domain
);
2906 while (upol
!= NULL
)
2908 CloogMatrix
*matrix
= cloog_upol_domain2matrix (upol
);
2909 cloog_matrix_print (foo
, matrix
);
2910 cloog_matrix_free (matrix
);
2911 upol
= cloog_upol_next (upol
);
2916 debug_cloog_domain (CloogDomain
*domain
)
2918 cloog_domain_print_polyhedra (stderr
, domain
);
2922 debug_cloog_matrix (CloogMatrix
*m
)
2924 cloog_matrix_print (stderr
, m
);