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_print_debug
= 0;
48 print_result (char *s
, CloogDomain
*d
)
50 if (cloog_print_debug
)
52 fprintf (stderr
, "%s \n", s
);
53 debug_cloog_domain (d
);
58 /* Variables names for pretty printing. */
59 static char wild_name
[200][40];
61 static inline const char*
62 variable_output_function (ppl_dimension_type var
)
65 return wild_name
[var
+ 1];
71 error_handler (enum ppl_enum_error_code code
, const char* description
)
73 fprintf (stderr
, "PPL error code %d\n%s", code
, description
);
78 cloog_initialize (void)
80 sprintf (wild_name
[0], "1");
81 sprintf (wild_name
[1], "a");
82 sprintf (wild_name
[2], "b");
83 sprintf (wild_name
[3], "c");
84 sprintf (wild_name
[4], "d");
85 sprintf (wild_name
[5], "e");
86 sprintf (wild_name
[6], "f");
87 sprintf (wild_name
[7], "g");
88 sprintf (wild_name
[8], "h");
89 sprintf (wild_name
[9], "i");
90 sprintf (wild_name
[10], "j");
91 sprintf (wild_name
[11], "k");
92 sprintf (wild_name
[12], "l");
93 sprintf (wild_name
[13], "m");
94 sprintf (wild_name
[14], "n");
95 sprintf (wild_name
[15], "o");
96 sprintf (wild_name
[16], "p");
97 sprintf (wild_name
[17], "q");
98 sprintf (wild_name
[18], "r");
99 sprintf (wild_name
[19], "s");
100 sprintf (wild_name
[20], "t");
101 sprintf (wild_name
[21], "alpha");
102 sprintf (wild_name
[22], "beta");
103 sprintf (wild_name
[23], "gamma");
104 sprintf (wild_name
[24], "delta");
105 sprintf (wild_name
[25], "tau");
106 sprintf (wild_name
[26], "sigma");
107 sprintf (wild_name
[27], "chi");
108 sprintf (wild_name
[28], "omega");
109 sprintf (wild_name
[29], "pi");
110 sprintf (wild_name
[30], "ni");
111 sprintf (wild_name
[31], "Alpha");
112 sprintf (wild_name
[32], "Beta");
113 sprintf (wild_name
[33], "Gamma");
114 sprintf (wild_name
[34], "Delta");
115 sprintf (wild_name
[35], "Tau");
116 sprintf (wild_name
[36], "Sigma");
117 sprintf (wild_name
[37], "Chi");
118 sprintf (wild_name
[38], "Omega");
119 sprintf (wild_name
[39], "xxx");
121 if (ppl_initialize() < 0)
123 fprintf (stderr
, "Cannot initialize the Parma Polyhedra Library.\n");
127 if (ppl_set_error_handler (error_handler
) < 0)
129 fprintf (stderr
, "Cannot install the custom error handler.\n");
133 if (ppl_io_set_variable_output_function (variable_output_function
) < 0)
135 fprintf (stderr
, "Cannot install the PPL custom variable output function. \n");
140 static inline Polyhedron
*
141 u2p (polyhedra_union upol
)
143 Polyhedron
*res
= Polyhedron_Copy (p_c2p (cloog_upol_polyhedron (upol
)));
148 polyhedra_union next
= cloog_upol_next (upol
);
152 n
= Polyhedron_Copy (p_c2p (cloog_upol_polyhedron (next
)));
164 static inline Polyhedron
*
165 d2p (CloogDomain
* d
)
167 return u2p (cloog_domain_upol (d
));
171 static inline polyhedra_union
174 polyhedra_union u
= cloog_new_upol (p_p2c (p
));
175 polyhedra_union res
= u
;
179 Polyhedron
*next
= p
->next
;
183 n
= cloog_new_upol (p_p2c (next
));
187 cloog_upol_set_next (u
, n
);
197 * The maximal number of rays allowed to be allocated by PolyLib. In fact since
198 * version 5.20, PolyLib automatically tune the number of rays by multiplying
199 * by 2 this number each time the maximum is reached. For unknown reasons
200 * PolyLib makes a segmentation fault if this number is too small. If this
201 * number is too small, performances will be reduced, if it is too high, memory
202 * will be saturated. Note that the option "-rays X" set this number to X.
206 /* Unused in this backend. */
208 int cloog_domain_allocated
= 0;
209 int cloog_domain_freed
= 0;
210 int cloog_domain_max
= 0;
212 /* The same for Value variables since in GMP mode they have to be freed. */
213 int cloog_value_allocated
= 0;
214 int cloog_value_freed
= 0;
215 int cloog_value_max
= 0;
219 cloog_value_leak_up ()
221 cloog_value_allocated
++;
222 if ((cloog_value_allocated
- cloog_value_freed
) > cloog_value_max
)
223 cloog_value_max
= cloog_value_allocated
- cloog_value_freed
;
228 cloog_value_leak_down ()
234 cloog_domain_polyhedron_set (CloogDomain
* d
, polyhedra_union p
)
240 cloog_domain_set_references (CloogDomain
* d
, int i
)
246 cloog_new_domain (polyhedra_union p
)
248 CloogDomain
*domain
= (CloogDomain
*) malloc (sizeof (CloogDomain
));
250 cloog_domain_set_references (domain
, 1);
255 cloog_domain_alloc (polyhedron p
)
257 return print_result ("cloog_domain_alloc", cloog_new_domain (cloog_new_upol (p
)));
261 debug_polyhedron (polyhedron p
)
263 debug_cloog_domain (cloog_domain_alloc (p
));
266 static inline CloogDomain
*
267 cloog_check_domain_id (CloogDomain
*dom
)
272 static inline CloogDomain
*
273 cloog_check_domain (CloogDomain
*dom
)
282 cloog_vector_min_not_zero (Value
* p
, unsigned len
, int *index
, Value
* min
)
285 int i
= cloog_first_non_zero (p
, len
);
289 value_set_si (*min
, 1);
294 value_absolute (*min
, p
[i
]);
297 for (i
= i
+ 1; i
< len
; i
++)
299 if (value_zero_p (p
[i
]))
302 value_absolute (x
, p
[i
]);
303 if (value_lt (x
, *min
))
305 value_assign (*min
, x
);
314 cloog_vector_gcd (Value
* p
, unsigned len
, Value
* gcd
)
317 int i
, non_zero
, min_index
= 0;
319 q
= (Value
*) malloc (len
* sizeof (Value
));
321 for (i
= 0; i
< len
; i
++)
324 for (cp
= p
, cq
= q
, i
= 0; i
< len
; i
++, cq
++, cp
++)
325 value_absolute (*cq
, *cp
);
329 cloog_vector_min_not_zero (q
, len
, &min_index
, gcd
);
331 if (value_notone_p (*gcd
))
333 for (cq
= q
, non_zero
= 0, i
= 0; i
< len
; i
++, cq
++)
336 value_modulus (*cq
, *cq
, *gcd
);
337 non_zero
|= value_notzero_p (*cq
);
346 for (i
= 0; i
< len
; i
++)
353 cloog_matrix_combine (Value
* p1
, Value
* p2
, Value
* p3
, int x
, unsigned len
)
355 Value a1
, a2
, gcd
, b1
, b2
, n1
;
357 value_init (a1
), value_init (a2
), value_init (gcd
),
358 value_init (b1
), value_init (b2
), value_init (n1
);
360 value_assign (a1
, p1
[x
]);
361 value_assign (a2
, p2
[x
]);
363 value_absolute (b1
, a1
);
364 value_absolute (b2
, a2
);
368 value_division (a1
, a1
, gcd
);
369 value_division (a2
, a2
, gcd
);
370 value_oppose (n1
, a1
);
371 cloog_vector_combine (p1
+ 1, p2
+ 1, p3
+ 1, a2
, n1
, len
);
372 cloog_vector_normalize (p3
+ 1, len
);
374 value_clear (a1
), value_clear (a2
), value_clear (gcd
),
375 value_clear (b1
), value_clear (b2
), value_clear (n1
);
378 /* In the matrix representation an equality has a 0 in the first
379 column. When the value of the first column is 1, the row
380 represents an inequality. */
383 cloog_matrix_row_is_eq_p (CloogMatrix
*matrix
, int row
)
385 return value_zero_p (matrix
->p
[row
][0]);
388 static ppl_Constraint_t
389 cloog_build_ppl_cstr (ppl_Linear_Expression_t expr
, int ineq
)
391 ppl_Constraint_t cstr
;
396 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
400 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_THAN_OR_EQUAL
);
404 /* Should not happen. */
411 /* Translates to PPL row I from MATRIX. CST is the constant part that
412 is added to the constraint. When INEQ is 1 the constraint is
413 translated as an inequality, when INEQ is 0 it is translated as an
414 equality, when INEQ has another value, the first column of the
415 matrix is read for determining the type of the constraint. */
417 static ppl_Constraint_t
418 cloog_translate_constraint (CloogMatrix
*matrix
, int i
, int cst
, int ineq
)
421 ppl_Constraint_t res
;
422 ppl_Coefficient_t coef
;
423 ppl_Linear_Expression_t expr
;
424 ppl_dimension_type dim
= matrix
->NbColumns
- 2;
428 ppl_new_Coefficient (&coef
);
429 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
431 for (j
= 1; j
< matrix
->NbColumns
- 1; j
++)
433 ppl_assign_Coefficient_from_mpz_t (coef
, matrix
->p
[i
][j
]);
434 ppl_Linear_Expression_add_to_coefficient (expr
, j
- 1, coef
);
437 value_set_si (val
, cst
);
438 value_addto (val
, matrix
->p
[i
][matrix
->NbColumns
- 1], val
);
439 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
440 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
441 ppl_delete_Coefficient (coef
);
443 if (ineq
!= 0 && ineq
!= 1)
444 ineq
= !cloog_matrix_row_is_eq_p (matrix
, i
);
446 res
= cloog_build_ppl_cstr (expr
, ineq
);
447 ppl_delete_Linear_Expression (expr
);
451 /* Translates to PPL the opposite of row I from MATRIX. When INEQ is
452 1 the constraint is translated as an inequality, when INEQ is 0 it
453 is translated as an equality, when INEQ has another value, the
454 first column of the matrix is read for determining the type of the
457 static ppl_Constraint_t
458 cloog_translate_oppose_constraint (CloogMatrix
*matrix
, int i
, int cst
, int ineq
)
461 ppl_Constraint_t res
;
462 ppl_Coefficient_t coef
;
463 ppl_Linear_Expression_t expr
;
464 ppl_dimension_type dim
= matrix
->NbColumns
- 2;
469 ppl_new_Coefficient (&coef
);
470 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
472 for (j
= 1; j
< matrix
->NbColumns
- 1; j
++)
474 value_oppose (val
, matrix
->p
[i
][j
]);
475 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
476 ppl_Linear_Expression_add_to_coefficient (expr
, j
- 1, coef
);
479 value_oppose (val
, matrix
->p
[i
][matrix
->NbColumns
- 1]);
480 value_set_si (val1
, cst
);
481 value_addto (val
, val
, val1
);
482 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
483 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
484 ppl_delete_Coefficient (coef
);
486 if (ineq
!= 0 && ineq
!= 1)
487 ineq
= !cloog_matrix_row_is_eq_p (matrix
, i
);
489 res
= cloog_build_ppl_cstr (expr
, ineq
);
490 ppl_delete_Linear_Expression (expr
);
494 /* Adds to PPL the constraints from MATRIX. */
497 cloog_translate_constraint_matrix_1 (ppl_Polyhedron_t ppl
, CloogMatrix
*matrix
)
501 for (i
= 0; i
< matrix
->NbRows
; i
++)
503 ppl_Constraint_t c
= cloog_translate_constraint (matrix
, i
, 0, -1);
504 ppl_Polyhedron_add_constraint_and_minimize (ppl
, c
);
505 ppl_delete_Constraint (c
);
509 static ppl_Polyhedron_t
510 cloog_translate_constraint_matrix (CloogMatrix
*matrix
)
512 ppl_Polyhedron_t ppl
;
513 ppl_dimension_type dim
= matrix
->NbColumns
- 2;
515 ppl_new_NNC_Polyhedron_from_dimension (&ppl
, dim
);
516 cloog_translate_constraint_matrix_1 (ppl
, matrix
);
520 /* Put the constraint matrix of polyhedron RES under Cloog's normal
521 form: Cloog expects to see
531 These two forms are equivalent but the expected form uses rightmost
532 indices for inequalities. */
535 cloog_pol_normal_form (polyhedron res
)
537 int dim
= cloog_pol_dim (res
);
538 int nrows
= cloog_pol_nbc (res
);
540 int neqs
= cloog_pol_nbeq (res
);
542 for (j
= 1; j
<= dim
; j
++)
546 for (rank
= 0; rank
< neqs
; rank
++)
547 if (j
- 1 == cloog_first_non_zero (res
->Constraint
[rank
] + 1, dim
))
549 for (i
= neqs
; i
< nrows
; i
++)
550 if (value_notzero_p (res
->Constraint
[i
][j
]))
551 cloog_matrix_combine (res
->Constraint
[i
],
552 res
->Constraint
[rank
],
553 res
->Constraint
[i
], j
, dim
+ 1);
561 cloog_translate_ppl_polyhedron_1 (ppl_Polyhedron_t pol
)
564 ppl_dimension_type dim
;
565 ppl_const_Constraint_System_t pcs
;
566 ppl_Constraint_System_const_iterator_t cit
, end
;
567 int eqs
, orig_ineqs
, ineqs
, row
, i
;
568 ppl_const_Constraint_t pc
;
570 ppl_Polyhedron_minimized_constraints (pol
, &pcs
);
571 ppl_new_Constraint_System_const_iterator (&cit
);
572 ppl_new_Constraint_System_const_iterator (&end
);
574 for (eqs
= 0, ineqs
= 0,
575 ppl_Constraint_System_begin (pcs
, cit
),
576 ppl_Constraint_System_end (pcs
, end
);
577 !ppl_Constraint_System_const_iterator_equal_test (cit
, end
);
578 ppl_Constraint_System_const_iterator_increment (cit
))
580 ppl_Constraint_System_const_iterator_dereference (cit
, &pc
);
581 (ppl_Constraint_type (pc
) == PPL_CONSTRAINT_TYPE_EQUAL
) ? eqs
++ : ineqs
++;
584 ppl_Polyhedron_space_dimension (pol
, &dim
);
587 if (1 || orig_ineqs
== 0)
588 res
= cloog_new_pol (dim
, eqs
+ ineqs
+ 1);
590 res
= cloog_new_pol (dim
, eqs
+ ineqs
);
593 /* Sort constraints: Cloog expects to see in matrices the equalities
594 followed by inequalities. */
597 for (ppl_Constraint_System_begin (pcs
, cit
), ppl_Constraint_System_end (pcs
, end
);
598 !ppl_Constraint_System_const_iterator_equal_test (cit
, end
);
599 ppl_Constraint_System_const_iterator_increment (cit
))
601 ppl_Coefficient_t coef
;
602 ppl_dimension_type col
;
607 ppl_new_Coefficient (&coef
);
608 ppl_Constraint_System_const_iterator_dereference (cit
, &pc
);
610 neg
= (ppl_Constraint_type (pc
) == PPL_CONSTRAINT_TYPE_LESS_THAN
611 || ppl_Constraint_type (pc
) == PPL_CONSTRAINT_TYPE_LESS_THAN_OR_EQUAL
) ? 1 : 0;
612 row
= (ppl_Constraint_type (pc
) == PPL_CONSTRAINT_TYPE_EQUAL
) ? eqs
++ : ineqs
++;
614 for (col
= 0; col
< dim
; col
++)
616 ppl_Constraint_coefficient (pc
, col
, coef
);
617 ppl_Coefficient_to_mpz_t (coef
, val
);
620 value_oppose (val
, val
);
622 value_assign (res
->Constraint
[row
][col
+ 1], val
);
625 ppl_Constraint_inhomogeneous_term (pc
, coef
);
626 ppl_Coefficient_to_mpz_t (coef
, val
);
627 value_assign (res
->Constraint
[row
][dim
+ 1], val
);
628 ppl_delete_Coefficient (coef
);
630 switch (ppl_Constraint_type (pc
))
632 case PPL_CONSTRAINT_TYPE_EQUAL
:
633 value_set_si (res
->Constraint
[row
][0], 0);
636 case PPL_CONSTRAINT_TYPE_LESS_THAN
:
637 case PPL_CONSTRAINT_TYPE_GREATER_THAN
:
638 value_decrement (res
->Constraint
[row
][dim
+ 1],
639 res
->Constraint
[row
][dim
+ 1]);
640 value_set_si (res
->Constraint
[row
][0], 1);
643 case PPL_CONSTRAINT_TYPE_LESS_THAN_OR_EQUAL
:
644 case PPL_CONSTRAINT_TYPE_GREATER_THAN_OR_EQUAL
:
645 value_set_si (res
->Constraint
[row
][0], 1);
649 fprintf (stderr
, "PPL_CONSTRAINT_TYPE_%d not implemented yet\n",
650 ppl_Constraint_type (pc
));
654 ppl_delete_Constraint_System_const_iterator (cit
);
655 ppl_delete_Constraint_System_const_iterator (end
);
657 if (cloog_pol_nbeq (res
) == 2 && cloog_pol_nbc (res
) == 2
658 && cloog_first_non_zero (res
->Constraint
[0], dim
+ 2) == dim
+ 1)
660 cloog_pol_free (res
);
661 return cloog_empty_polyhedron (dim
);
664 /* Add the positivity constraint. */
665 if (1 || orig_ineqs
== 0)
668 value_set_si (res
->Constraint
[row
][0], 1);
669 for (i
= 0; i
< dim
; i
++)
670 value_set_si (res
->Constraint
[row
][i
+ 1], 0);
671 value_set_si (res
->Constraint
[row
][dim
+ 1], 1);
674 /* Put the matrix of RES in normal form. */
675 cloog_pol_normal_form (res
);
677 /* If we do not sort the matrices, Cloog is a random loop
679 cloog_pol_sort_rows (res
);
685 cloog_pol_from_matrix (CloogMatrix
* m
)
688 int ncolumns
= cloog_matrix_ncolumns (m
);
689 int nrows
= cloog_matrix_nrows (m
);
693 return cloog_universe_polyhedron (ncolumns
- 2);
696 p
= cloog_translate_constraint_matrix (m
);
697 res
= cloog_translate_ppl_polyhedron_1 (p
);
698 if (cloog_pol_nbc (res
) < cloog_matrix_nrows (m
))
701 cloog_pol_free (res
);
702 res
= cloog_new_pol (ncolumns
- 2, nrows
);
703 cloog_vector_copy (m
->p
[0], res
->Constraint
[0], m
->NbRows
* m
->NbColumns
);
709 cloog_domain_matrix2domain (CloogMatrix
* matrix
)
711 return print_result ("cloog_domain_matrix2domain", cloog_domain_alloc (cloog_pol_from_matrix (matrix
)));
715 cloog_translate_ppl_polyhedron (ppl_Polyhedron_t p
)
717 polyhedron res
= cloog_translate_ppl_polyhedron_1 (p
);
718 return print_result ("cloog_translate_ppl_polyhedron", cloog_domain_alloc (res
));
721 void debug_poly (Polyhedron
*p
)
723 Polyhedron_Print (stderr
, "%4s ", p
);
726 void debug_new_poly (polyhedron p
)
728 Polyhedron_Print (stderr
, "%4s ", p_c2p (p
));
732 debug_ppl_poly (ppl_Polyhedron_t p
)
734 debug_poly (p_c2p (cloog_domain_polyhedron (cloog_translate_ppl_polyhedron (p
))));
738 cloog_domain_references (CloogDomain
* d
)
740 return d
->_references
;
744 * cloog_domain_print function:
745 * This function prints the content of a CloogDomain structure (domain) into
746 * a file (foo, possibly stdout).
749 cloog_domain_print (FILE * foo
, CloogDomain
* domain
)
751 polyhedra_union upol
= cloog_domain_upol (domain
);
755 Polyhedron_Print (foo
, VALUE_FMT
, p_c2p (cloog_upol_polyhedron (upol
)));
756 upol
= cloog_upol_next (upol
);
759 fprintf (foo
, "Number of active references: %d\n",
760 cloog_domain_references (domain
));
764 * cloog_domain_free function:
765 * This function frees the allocated memory for a CloogDomain structure
766 * (domain). It decrements the number of active references to this structure,
767 * if there are no more references on the structure, it frees it (with the
768 * included list of polyhedra).
771 cloog_domain_free (CloogDomain
* domain
)
775 cloog_domain_set_references (domain
,
776 cloog_domain_references (domain
) - 1);
778 if (cloog_domain_references (domain
) == 0)
781 polyhedra_union upol
= cloog_domain_upol (domain
);
785 Polyhedron_Free (p_c2p (cloog_upol_polyhedron (upol
)));
786 upol
= cloog_upol_next (upol
);
796 * cloog_domain_copy function:
797 * This function returns a copy of a CloogDomain structure (domain). To save
798 * memory this is not a memory copy but we increment a counter of active
799 * references inside the structure, then return a pointer to that structure.
802 cloog_domain_copy (CloogDomain
* domain
)
804 cloog_domain_set_references (domain
, cloog_domain_references (domain
) + 1);
805 return print_result ("cloog_domain_copy", domain
);
809 * cloog_domain_convex function:
810 * Given a polyhedral domain (polyhedron), this function concatenates the lists
811 * of rays and lines of the two (or more) polyhedra in the domain into one
812 * combined list, and find the set of constraints which tightly bound all of
813 * those objects. It returns the corresponding polyhedron.
816 cloog_domain_convex (CloogDomain
* domain
)
820 polyhedra_union upol
= cloog_domain_upol (domain
);
821 CloogMatrix
*m
= cloog_upol_domain2matrix (upol
);
822 ppl_Polyhedron_t p1
= cloog_translate_constraint_matrix (m
);
824 upol
= cloog_upol_next (upol
);
827 ppl_const_Generator_System_t g
;
829 m
= cloog_upol_domain2matrix (upol
);
830 p2
= cloog_translate_constraint_matrix (m
);
831 ppl_Polyhedron_generators (p2
, &g
);
832 ppl_Polyhedron_add_generators_and_minimize (p1
, g
);
833 ppl_delete_Polyhedron (p2
);
835 upol
= cloog_upol_next (upol
);
838 res
= cloog_translate_ppl_polyhedron (p1
);
839 ppl_delete_Polyhedron (p1
);
841 return print_result ("cloog_domain_convex", res
);
845 cloog_domain_isconvex (CloogDomain
* domain
)
847 if (cloog_domain_polyhedron (domain
))
848 return !cloog_upol_next (cloog_domain_upol (domain
));
854 * cloog_domain_simple_convex:
855 * Given a list (union) of polyhedra, this function returns a "simple"
856 * convex hull of this union. In particular, the constraints of the
857 * the returned polyhedron consist of (parametric) lower and upper
858 * bounds on individual variables and constraints that appear in the
859 * original polyhedra.
861 * nb_par is the number of parameters of the domain.
864 cloog_domain_simple_convex (CloogDomain
* domain
, int nb_par
)
866 fprintf (stderr
, "cloog_domain_simple_convex is not implemented yet.\n");
870 /* Returns non-zero when the constraint I in MATRIX is the positivity
871 constraint: "0 >= 0". */
874 cloog_positivity_constraint_p (CloogMatrix
*matrix
, int i
, int dim
)
878 for (j
= 1; j
< dim
; j
++)
879 if (value_notzero_p (matrix
->p
[i
][j
]))
885 /* Returns one when the constraint C is not in P, returns zero when C
889 non_redundant_constraint (ppl_Constraint_t c
, ppl_Polyhedron_t p
)
891 int rel
= ppl_Polyhedron_relation_with_Constraint (p
, c
);
893 if (rel
& PPL_POLY_CON_RELATION_IS_DISJOINT
)
896 if (rel
& PPL_POLY_CON_RELATION_IS_INCLUDED
)
899 if (rel
& PPL_POLY_CON_RELATION_STRICTLY_INTERSECTS
)
901 ppl_Constraint_System_t cs
;
903 ppl_const_Generator_System_t g
;
904 ppl_Generator_System_const_iterator_t git
, end
;
905 ppl_const_Generator_t cg
;
907 ppl_new_Constraint_System_from_Constraint (&cs
, c
);
908 ppl_new_NNC_Polyhedron_from_Constraint_System (&p1
, cs
);
909 ppl_Polyhedron_generators (p1
, &g
);
910 ppl_new_Generator_System_const_iterator (&git
);
911 ppl_new_Generator_System_const_iterator (&end
);
913 for (ppl_Generator_System_begin (g
, git
), ppl_Generator_System_end (g
, end
);
914 !ppl_Generator_System_const_iterator_equal_test (git
, end
);
915 ppl_Generator_System_const_iterator_increment (git
))
917 ppl_Generator_System_const_iterator_dereference (git
, &cg
);
918 rel
= ppl_Polyhedron_relation_with_Generator (p
, cg
);
920 if (!(rel
& PPL_POLY_GEN_RELATION_SUBSUMES
))
923 ppl_delete_Constraint_System (cs
);
924 ppl_delete_Polyhedron (p1
);
925 ppl_delete_Generator_System_const_iterator (git
);
926 ppl_delete_Generator_System_const_iterator (end
);
928 /* All generators are redundant. */
929 if (rel
& PPL_POLY_GEN_RELATION_SUBSUMES
)
936 /* Returns 1 if adding constraint C to polyhedron P changes the number
937 of constraints of P. */
940 changes_constraints (ppl_Constraint_t c
, ppl_Polyhedron_t p
)
942 int a1
= 0, a2
= 0, a3
= 0, a4
= 0, a5
= 0;
943 int b1
= 0, b2
= 0, b3
= 0, b4
= 0, b5
= 0;
945 ppl_const_Constraint_System_t g
;
946 ppl_Constraint_System_const_iterator_t git
, end
;
948 ppl_new_Constraint_System_const_iterator (&git
);
949 ppl_new_Constraint_System_const_iterator (&end
);
950 ppl_Polyhedron_minimized_constraints (p
, &g
);
952 for (ppl_Constraint_System_begin (g
, git
), ppl_Constraint_System_end (g
, end
);
953 !ppl_Constraint_System_const_iterator_equal_test (git
, end
);
954 ppl_Constraint_System_const_iterator_increment (git
))
956 ppl_const_Constraint_t pg
;
958 ppl_Constraint_System_const_iterator_dereference (git
, &pg
);
959 switch (ppl_Constraint_type (pg
))
961 case PPL_CONSTRAINT_TYPE_LESS_THAN
:
965 case PPL_CONSTRAINT_TYPE_LESS_THAN_OR_EQUAL
:
969 case PPL_CONSTRAINT_TYPE_EQUAL
:
973 case PPL_CONSTRAINT_TYPE_GREATER_THAN_OR_EQUAL
:
977 case PPL_CONSTRAINT_TYPE_GREATER_THAN
:
986 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q
, p
);
987 ppl_Polyhedron_add_constraint_and_minimize (q
, c
);
988 ppl_Polyhedron_minimized_constraints (q
, &g
);
990 for (ppl_Constraint_System_begin (g
, git
), ppl_Constraint_System_end (g
, end
);
991 !ppl_Constraint_System_const_iterator_equal_test (git
, end
);
992 ppl_Constraint_System_const_iterator_increment (git
))
994 ppl_const_Constraint_t pg
;
996 ppl_Constraint_System_const_iterator_dereference (git
, &pg
);
997 switch (ppl_Constraint_type (pg
))
999 case PPL_CONSTRAINT_TYPE_LESS_THAN
:
1003 case PPL_CONSTRAINT_TYPE_LESS_THAN_OR_EQUAL
:
1007 case PPL_CONSTRAINT_TYPE_EQUAL
:
1011 case PPL_CONSTRAINT_TYPE_GREATER_THAN_OR_EQUAL
:
1015 case PPL_CONSTRAINT_TYPE_GREATER_THAN
:
1024 ppl_delete_Constraint_System_const_iterator (git
);
1025 ppl_delete_Constraint_System_const_iterator (end
);
1026 ppl_delete_Polyhedron (q
);
1028 if (a1
!= b1
|| a2
!= b2
|| a3
!= b3
|| a4
!= b4
|| a5
!= b5
)
1034 /* Returns 1 if adding constraint C to polyhedron P changes the
1038 changes_generators (ppl_Constraint_t c
, ppl_Polyhedron_t p
)
1043 ppl_const_Generator_System_t g
;
1044 ppl_Generator_System_const_iterator_t git
, end
;
1046 ppl_new_Generator_System_const_iterator (&git
);
1047 ppl_new_Generator_System_const_iterator (&end
);
1048 ppl_Polyhedron_minimized_generators (p
, &g
);
1050 for (ppl_Generator_System_begin (g
, git
), ppl_Generator_System_end (g
, end
);
1051 !ppl_Generator_System_const_iterator_equal_test (git
, end
);
1052 ppl_Generator_System_const_iterator_increment (git
))
1054 ppl_const_Generator_t pg
;
1056 ppl_Generator_System_const_iterator_dereference (git
, &pg
);
1057 switch (ppl_Generator_type (pg
))
1059 case PPL_GENERATOR_TYPE_LINE
:
1060 case PPL_GENERATOR_TYPE_RAY
:
1064 case PPL_GENERATOR_TYPE_POINT
:
1065 case PPL_GENERATOR_TYPE_CLOSURE_POINT
:
1074 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q
, p
);
1075 ppl_Polyhedron_add_constraint (q
, c
);
1076 ppl_Polyhedron_minimized_generators (q
, &g
);
1078 for (ppl_Generator_System_begin (g
, git
), ppl_Generator_System_end (g
, end
);
1079 !ppl_Generator_System_const_iterator_equal_test (git
, end
);
1080 ppl_Generator_System_const_iterator_increment (git
))
1082 ppl_const_Generator_t pg
;
1084 ppl_Generator_System_const_iterator_dereference (git
, &pg
);
1085 switch (ppl_Generator_type (pg
))
1087 case PPL_GENERATOR_TYPE_LINE
:
1088 case PPL_GENERATOR_TYPE_RAY
:
1092 case PPL_GENERATOR_TYPE_POINT
:
1093 case PPL_GENERATOR_TYPE_CLOSURE_POINT
:
1102 ppl_delete_Generator_System_const_iterator (git
);
1103 ppl_delete_Generator_System_const_iterator (end
);
1104 ppl_delete_Polyhedron (q
);
1106 if (a1
>= b1
&& a2
>= b2
)
1112 /* Simplifies DOM1 in the context of DOM2. For example, DOM1 can
1113 contain the following conditions: i >= 0, i <= 5, and DOM2 is a
1114 loop around, i.e. the context of DOM1, that also contains the
1115 conditions i >= 0, i <= 5. So instead of generating a loop like:
1117 | for (i = 0; i < 6; i++)
1119 | if (i >= 0 && i <= 5)
1123 this function allows to detect that in the context of DOM2, the
1124 constraints of DOM1 are redundant, and so the following code should
1127 | for (i = 0; i < 6; i++)
1132 cloog_domain_simplify (CloogDomain
* dom1
, CloogDomain
* dom2
)
1135 CloogDomain
*res
= NULL
;
1136 polyhedra_union u1
, u2
;
1137 unsigned dim
= cloog_domain_dim (dom1
);
1138 CloogDomain
*inter
= cloog_domain_intersection (dom1
, dom2
);
1140 for (u1
= cloog_domain_upol (inter
); u1
; u1
= cloog_upol_next (u1
))
1142 CloogMatrix
*m1
= cloog_upol_domain2matrix (u1
);
1144 for (u2
= cloog_domain_upol (dom2
); u2
; u2
= cloog_upol_next (u2
))
1146 CloogMatrix
*m2
= cloog_upol_domain2matrix (u2
);
1147 ppl_Polyhedron_t p2
= cloog_translate_constraint_matrix (m2
);
1148 ppl_Polyhedron_t p3
;
1150 ppl_new_NNC_Polyhedron_from_dimension (&p3
, dim
);
1152 for (i
= 0; i
< m1
->NbRows
; i
++)
1153 if (!cloog_positivity_constraint_p (m1
, i
, dim
+ 1))
1155 ppl_Constraint_t c1
= cloog_translate_constraint (m1
, i
, 0, -1);
1157 if (non_redundant_constraint (c1
, p2
)
1158 || changes_generators (c1
, p2
)
1159 || changes_constraints (c1
, p2
))
1160 ppl_Polyhedron_add_constraint_and_minimize (p3
, c1
);
1162 ppl_delete_Constraint (c1
);
1165 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (p3
));
1167 ppl_delete_Polyhedron (p2
);
1168 ppl_delete_Polyhedron (p3
);
1172 return print_result ("cloog_domain_simplify", res
);
1176 static polyhedra_union
1177 cloog_upol_copy (polyhedra_union p
)
1179 polyhedra_union res
= cloog_new_upol (p_p2c (Polyhedron_Copy (p_c2p (cloog_upol_polyhedron (p
)))));
1180 polyhedra_union upol
= res
;
1182 while (cloog_upol_next (p
))
1184 cloog_upol_set_next (upol
, cloog_new_upol (p_p2c (Polyhedron_Copy (p_c2p (cloog_upol_polyhedron (p
))))));
1185 upol
= cloog_upol_next (upol
);
1186 p
= cloog_upol_next (p
);
1192 /* Adds to D1 the union of polyhedra from D2, with no checks of
1193 redundancies between polyhedra. */
1196 cloog_domain_add_domain (CloogDomain
*d1
, CloogDomain
*d2
)
1198 polyhedra_union upol
;
1206 upol
= cloog_domain_upol (d1
);
1207 while (cloog_upol_next (upol
))
1208 upol
= cloog_upol_next (upol
);
1210 cloog_upol_set_next (upol
, cloog_domain_upol (d2
));
1215 * cloog_domain_union function:
1216 * This function returns a new CloogDomain structure including a polyhedral
1217 * domain which is the union of two polyhedral domains (pol1) U (pol2) inside
1218 * two CloogDomain structures.
1221 cloog_domain_union (CloogDomain
* dom1
, CloogDomain
* dom2
)
1224 polyhedra_union head1
, head2
, tail1
, tail2
;
1225 polyhedra_union d1
, d2
;
1233 if (cloog_domain_dim (dom1
) != cloog_domain_dim (dom2
))
1235 fprintf (stderr
, "cloog_domain_union should not be called on domains of different dimensions.\n");
1241 for (d1
= cloog_domain_upol (dom1
); d1
; d1
= cloog_upol_next (d1
))
1244 ppl_Polyhedron_t ppl1
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (d1
));
1246 for (d2
= cloog_domain_upol (dom2
); d2
; d2
= cloog_upol_next (d2
))
1248 ppl_Polyhedron_t ppl2
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (d2
));
1250 if (ppl_Polyhedron_contains_Polyhedron (ppl2
, ppl1
))
1252 ppl_delete_Polyhedron (ppl2
);
1256 ppl_delete_Polyhedron (ppl2
);
1258 ppl_delete_Polyhedron (ppl1
);
1264 head1
= cloog_upol_copy (d1
);
1269 cloog_upol_set_next (tail1
, cloog_upol_copy (d1
));
1270 tail1
= cloog_upol_next (tail1
);
1277 for (d2
= cloog_domain_upol (dom2
); d2
; d2
= cloog_upol_next (d2
))
1280 ppl_Polyhedron_t ppl2
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (d2
));
1282 for (d1
= head1
; d1
; d1
= cloog_upol_next (d1
))
1284 ppl_Polyhedron_t ppl1
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (d1
));
1286 if (ppl_Polyhedron_contains_Polyhedron (ppl1
, ppl2
))
1288 ppl_delete_Polyhedron (ppl1
);
1292 ppl_delete_Polyhedron (ppl1
);
1294 ppl_delete_Polyhedron (ppl2
);
1300 head2
= cloog_upol_copy (d2
);
1305 cloog_upol_set_next (tail2
, cloog_upol_copy (d2
));
1306 tail2
= cloog_upol_next (tail2
);
1312 res
= cloog_new_domain (head2
);
1315 cloog_upol_set_next (tail1
, head2
);
1316 res
= cloog_new_domain (head1
);
1319 return print_result ("cloog_domain_union", cloog_check_domain (res
));
1323 * cloog_domain_intersection function:
1324 * This function returns a new CloogDomain structure including a polyhedral
1325 * domain which is the intersection of two polyhedral domains (pol1)inter(pol2)
1326 * inside two CloogDomain structures.
1329 cloog_domain_intersection (CloogDomain
* dom1
, CloogDomain
* dom2
)
1331 CloogDomain
*res
= NULL
;
1332 polyhedra_union p1
, p2
;
1333 ppl_Polyhedron_t ppl1
, ppl2
;
1335 for (p1
= cloog_domain_upol (dom1
); p1
; p1
= cloog_upol_next (p1
))
1337 ppl1
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (p1
));
1339 for (p2
= cloog_domain_upol (dom2
); p2
; p2
= cloog_upol_next (p2
))
1341 ppl2
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (p2
));
1342 ppl_Polyhedron_intersection_assign (ppl2
, ppl1
);
1343 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (ppl2
));
1344 ppl_delete_Polyhedron (ppl2
);
1346 ppl_delete_Polyhedron (ppl1
);
1349 return print_result ("cloog_domain_intersection", res
);
1352 /* Returns d1 minus d2. */
1355 cloog_domain_difference (CloogDomain
* d1
, CloogDomain
* d2
)
1357 CloogDomain
*res
= NULL
, *d
= d1
;
1358 polyhedra_union p1
, p2
;
1360 if (cloog_domain_isempty (d2
))
1361 return print_result ("cloog_domain_difference", cloog_domain_copy (d1
));
1363 for (p2
= cloog_domain_upol (d2
); p2
; p2
= cloog_upol_next (p2
))
1365 CloogMatrix
*matrix
= cloog_upol_domain2matrix (p2
);
1367 for (p1
= cloog_domain_upol (d
); p1
; p1
= cloog_upol_next (p1
))
1370 CloogMatrix
*m1
= cloog_upol_domain2matrix (p1
);
1372 for (i
= 0; i
< matrix
->NbRows
; i
++)
1374 ppl_Polyhedron_t p3
;
1375 ppl_Constraint_t cstr
;
1377 /* Don't handle "0 >= 0". */
1378 if (cloog_positivity_constraint_p (matrix
, i
,
1379 cloog_domain_dim (d
) + 1))
1382 /* Add the constraint "-matrix[i] - 1 >= 0". */
1383 p3
= cloog_translate_constraint_matrix (m1
);
1384 cstr
= cloog_translate_oppose_constraint (matrix
, i
, -1, 1);
1385 ppl_Polyhedron_add_constraint_and_minimize (p3
, cstr
);
1386 ppl_delete_Constraint (cstr
);
1387 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (p3
));
1388 ppl_delete_Polyhedron (p3
);
1390 /* For an equality, add the constraint "matrix[i] - 1 >= 0". */
1391 if (cloog_matrix_row_is_eq_p (matrix
, i
))
1393 p3
= cloog_translate_constraint_matrix (m1
);
1394 cstr
= cloog_translate_constraint (matrix
, i
, -1, 1);
1395 ppl_Polyhedron_add_constraint_and_minimize (p3
, cstr
);
1396 ppl_delete_Constraint (cstr
);
1397 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (p3
));
1398 ppl_delete_Polyhedron (p3
);
1407 res
= cloog_domain_empty (cloog_domain_dim (d2
));
1411 return print_result ("cloog_domain_difference", res
);
1416 * cloog_domain_addconstraints function :
1417 * This function adds source's polyhedron constraints to target polyhedron: for
1418 * each element of the polyhedron inside 'target' (i.e. element of the union
1419 * of polyhedra) it adds the constraints of the corresponding element in
1421 * - August 10th 2002: first version.
1422 * Nota bene for future : it is possible that source and target don't have the
1423 * same number of elements (try iftest2 without non-shared constraint
1424 * elimination in cloog_loop_separate !). This function is yet another part
1425 * of the DomainSimplify patching problem...
1428 cloog_domain_addconstraints (CloogDomain
*domain_source
, CloogDomain
*domain_target
)
1431 ppl_Polyhedron_t ppl
;
1432 polyhedra_union source
, target
, last
;
1433 int dim
= cloog_domain_dim (domain_target
);
1435 source
= cloog_domain_upol (domain_source
);
1436 target
= cloog_domain_upol (domain_target
);
1438 ppl_new_NNC_Polyhedron_from_dimension (&ppl
, dim
);
1439 cloog_translate_constraint_matrix_1 (ppl
, cloog_upol_domain2matrix (target
));
1440 cloog_translate_constraint_matrix_1 (ppl
, cloog_upol_domain2matrix (source
));
1441 res
= cloog_translate_ppl_polyhedron (ppl
);
1442 ppl_delete_Polyhedron (ppl
);
1443 last
= cloog_domain_upol (res
);
1445 source
= cloog_upol_next (source
);
1446 target
= cloog_upol_next (target
);
1450 ppl_new_NNC_Polyhedron_from_dimension (&ppl
, dim
);
1451 cloog_translate_constraint_matrix_1 (ppl
, cloog_upol_domain2matrix (target
));
1455 cloog_translate_constraint_matrix_1 (ppl
, cloog_upol_domain2matrix (source
));
1456 source
= cloog_upol_next (source
);
1460 (last
, cloog_domain_upol (cloog_translate_ppl_polyhedron (ppl
)));
1461 ppl_delete_Polyhedron (ppl
);
1463 last
= cloog_upol_next (last
);
1464 target
= cloog_upol_next (target
);
1467 return print_result ("cloog_domain_addconstraints", res
);
1470 /* Compares P1 to P2: returns 0 when the polyhedra don't overlap,
1471 returns 1 when p1 >= p2, and returns -1 when p1 < p2. The ">"
1472 relation is the "contains" relation. */
1475 cloog_domain_polyhedron_compare (CloogMatrix
*m1
, CloogMatrix
*m2
, int level
, int nb_par
, int dimension
)
1478 ppl_Polyhedron_t q1
, q2
, q3
, q4
, q5
, q
;
1479 ppl_Polyhedron_t p1
, p2
;
1481 p1
= cloog_translate_constraint_matrix (m1
);
1482 if (ppl_Polyhedron_is_empty (p1
))
1484 ppl_delete_Polyhedron (p1
);
1488 p2
= cloog_translate_constraint_matrix (m2
);
1489 if (ppl_Polyhedron_is_empty (p2
))
1491 ppl_delete_Polyhedron (p2
);
1495 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q1
, p1
);
1496 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q2
, p2
);
1498 for (i
= level
; i
< dimension
- nb_par
+ 1; i
++)
1501 ppl_Coefficient_t d
;
1502 ppl_Linear_Expression_t expr
;
1506 value_set_si (val
, 1);
1507 ppl_new_Coefficient_from_mpz_t (&d
, val
);
1508 ppl_new_Linear_Expression_with_dimension (&expr
, dimension
);
1509 ppl_Linear_Expression_add_to_coefficient (expr
, i
- 1, d
);
1510 ppl_new_Generator (&g
, expr
, PPL_GENERATOR_TYPE_LINE
, d
);
1511 ppl_Polyhedron_add_generator (q1
, g
);
1512 ppl_Polyhedron_add_generator (q2
, g
);
1513 ppl_delete_Generator (g
);
1514 ppl_delete_Linear_Expression (expr
);
1515 ppl_delete_Coefficient (d
);
1518 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q
, q1
);
1519 ppl_Polyhedron_intersection_assign (q
, q2
);
1520 ppl_delete_Polyhedron (q1
);
1521 ppl_delete_Polyhedron (q2
);
1523 if (ppl_Polyhedron_is_empty (q
))
1525 ppl_delete_Polyhedron (p1
);
1526 ppl_delete_Polyhedron (p2
);
1527 ppl_delete_Polyhedron (q
);
1531 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q1
, p1
);
1532 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q2
, p2
);
1533 ppl_delete_Polyhedron (p1
);
1534 ppl_delete_Polyhedron (p2
);
1536 ppl_Polyhedron_intersection_assign (q1
, q
);
1537 ppl_Polyhedron_intersection_assign (q2
, q
);
1539 m1
= cloog_upol_domain2matrix (cloog_domain_upol (cloog_translate_ppl_polyhedron (q1
)));
1540 m2
= cloog_upol_domain2matrix (cloog_domain_upol (cloog_translate_ppl_polyhedron (q2
)));
1542 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q4
, q
);
1543 for (i
= 0; i
< m1
->NbRows
; i
++)
1544 if (value_one_p (m1
->p
[i
][0])
1545 && value_pos_p (m1
->p
[i
][level
]))
1547 ppl_Constraint_t c
= cloog_translate_constraint (m1
, i
, 0, 1);
1548 ppl_Polyhedron_add_constraint (q4
, c
);
1549 ppl_delete_Constraint (c
);
1552 for (i
= 0; i
< m2
->NbRows
; i
++)
1553 if (value_one_p (m2
->p
[i
][0])
1554 && value_neg_p (m2
->p
[i
][level
]))
1556 ppl_Constraint_t c
= cloog_translate_constraint (m2
, i
, 0, 1);
1557 ppl_Polyhedron_add_constraint (q4
, c
);
1558 ppl_delete_Constraint (c
);
1561 if (ppl_Polyhedron_is_empty (q4
))
1563 ppl_delete_Polyhedron (q
);
1564 ppl_delete_Polyhedron (q1
);
1565 ppl_delete_Polyhedron (q2
);
1566 ppl_delete_Polyhedron (q4
);
1570 ppl_delete_Polyhedron (q4
);
1571 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q3
, q
);
1572 for (i
= 0; i
< m1
->NbRows
; i
++)
1574 if (value_zero_p (m1
->p
[i
][0]))
1576 if (value_zero_p (m1
->p
[i
][level
]))
1579 else if (value_neg_p (m1
->p
[i
][level
]))
1581 ppl_Constraint_t c
= cloog_translate_oppose_constraint (m1
, i
, 0, 1);
1582 ppl_Polyhedron_add_constraint (q3
, c
);
1583 ppl_delete_Constraint (c
);
1588 ppl_Constraint_t c
= cloog_translate_constraint (m1
, i
, 0, 1);
1589 ppl_Polyhedron_add_constraint (q3
, c
);
1590 ppl_delete_Constraint (c
);
1594 else if (value_neg_p (m1
->p
[i
][level
]))
1596 ppl_Constraint_t c
= cloog_translate_oppose_constraint (m1
, i
, 0, 1);
1597 ppl_Polyhedron_add_constraint (q3
, c
);
1598 ppl_delete_Constraint (c
);
1604 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q5
, q3
);
1605 for (j
= 0; j
< m2
->NbRows
; j
++)
1607 if (value_zero_p (m2
->p
[j
][0]))
1609 if (value_zero_p (m2
->p
[j
][level
]))
1612 else if (value_pos_p (m2
->p
[j
][level
]))
1614 ppl_Constraint_t c
= cloog_translate_oppose_constraint (m2
, j
, 0, 1);
1615 ppl_Polyhedron_add_constraint (q5
, c
);
1616 ppl_delete_Constraint (c
);
1621 ppl_Constraint_t c
= cloog_translate_constraint (m2
, j
, 0, 1);
1622 ppl_Polyhedron_add_constraint (q5
, c
);
1623 ppl_delete_Constraint (c
);
1627 else if (value_pos_p (m2
->p
[j
][level
]))
1629 ppl_Constraint_t c
= cloog_translate_oppose_constraint (m2
, j
, 0, 1);
1630 ppl_Polyhedron_add_constraint (q5
, c
);
1631 ppl_delete_Constraint (c
);
1637 if (!ppl_Polyhedron_is_empty (q5
))
1639 ppl_delete_Polyhedron (q
);
1640 ppl_delete_Polyhedron (q1
);
1641 ppl_delete_Polyhedron (q2
);
1642 ppl_delete_Polyhedron (q3
);
1643 ppl_delete_Polyhedron (q5
);
1647 /* Reinitialize Q5. */
1648 ppl_delete_Polyhedron (q5
);
1649 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q5
, q3
);
1652 /* Reinitialize Q3. */
1653 ppl_delete_Polyhedron (q3
);
1654 ppl_new_NNC_Polyhedron_from_NNC_Polyhedron (&q3
, q
);
1657 ppl_delete_Polyhedron (q
);
1658 ppl_delete_Polyhedron (q1
);
1659 ppl_delete_Polyhedron (q2
);
1660 ppl_delete_Polyhedron (q3
);
1661 ppl_delete_Polyhedron (q5
);
1666 * cloog_domain_sort function:
1667 * This function topologically sorts (nb_pols) polyhedra. Here (pols) is a an
1668 * array of pointers to polyhedra, (nb_pols) is the number of polyhedra,
1669 * (level) is the level to consider for partial ordering (nb_par) is the
1670 * parameter space dimension, (permut) if not NULL, is an array of (nb_pols)
1671 * integers that contains a permutation specification after call in order to
1672 * apply the topological sorting.
1676 cloog_domain_sort (CloogDomain
**doms
, unsigned nb_pols
, unsigned level
,
1677 unsigned nb_par
, int *permut
)
1680 int dim
= cloog_domain_dim (doms
[0]);
1682 for (i
= 0; i
< nb_pols
; i
++)
1685 /* Note that here we do a comparison per tuple of polyhedra.
1686 PolyLib does not do this, but instead it does fewer comparisons
1687 and with a complex reasoning they infer that it some comparisons
1688 are not useful. The result is that PolyLib has wrong permutations.
1690 FIXME: In the PolyLib backend, Cloog should use this algorithm
1691 instead of PolyhedronTSort, and cloog_domain_polyhedron_compare
1692 should be implemented with a simple call to PolyhedronLTQ: these
1693 two functions produce identical answers. */
1694 for (i
= 0; i
< nb_pols
; i
++)
1695 for (j
= i
+ 1; j
< nb_pols
; j
++)
1697 CloogMatrix
*m1
= cloog_upol_domain2matrix (cloog_domain_upol (doms
[i
]));
1698 CloogMatrix
*m2
= cloog_upol_domain2matrix (cloog_domain_upol (doms
[j
]));
1700 if (cloog_domain_polyhedron_compare (m1
, m2
, level
, nb_par
, dim
) == 1)
1703 permut
[i
] = permut
[j
];
1710 * cloog_domain_empty function:
1711 * This function allocates the memory space for a CloogDomain structure and
1712 * sets its polyhedron to an empty polyhedron with 'dimension' dimensions.
1713 * Then it returns a pointer to the allocated space.
1714 * - June 10th 2005: first version.
1717 cloog_domain_empty (int dimension
)
1719 return (cloog_domain_alloc (cloog_empty_polyhedron (dimension
)));
1723 /******************************************************************************
1724 * Structure display function *
1725 ******************************************************************************/
1729 * cloog_domain_print_structure :
1730 * this function is a more human-friendly way to display the CloogDomain data
1731 * structure, it only shows the constraint system and includes an indentation
1732 * level (level) in order to work with others print_structure functions.
1733 * Written by Olivier Chorier, Luc Marchaud, Pierre Martin and Romain Tartiere.
1734 * - April 24th 2005: Initial version.
1735 * - May 26th 2005: Memory leak hunt.
1736 * - June 16th 2005: (Ced) Integration in domain.c.
1739 cloog_domain_print_structure (FILE * file
, CloogDomain
* domain
, int level
)
1742 CloogMatrix
*matrix
;
1744 /* Go to the right level. */
1745 for (i
= 0; i
< level
; i
++)
1746 fprintf (file
, "|\t");
1750 fprintf (file
, "+-- CloogDomain\n");
1752 /* Print the matrix. */
1753 matrix
= cloog_upol_domain2matrix (cloog_domain_upol (domain
));
1754 cloog_matrix_print_structure (file
, matrix
, level
);
1755 cloog_matrix_free (matrix
);
1758 for (i
= 0; i
< level
+ 1; i
++)
1759 fprintf (file
, "|\t");
1760 fprintf (file
, "\n");
1763 fprintf (file
, "+-- Null CloogDomain\n");
1769 * cloog_domain_list_print function:
1770 * This function prints the content of a CloogDomainList structure into a
1771 * file (foo, possibly stdout).
1772 * - November 6th 2001: first version.
1775 cloog_domain_list_print (FILE * foo
, CloogDomainList
* list
)
1777 while (list
!= NULL
)
1779 cloog_domain_print (foo
, cloog_domain (list
));
1780 list
= cloog_next_domain (list
);
1785 /******************************************************************************
1786 * Memory deallocation function *
1787 ******************************************************************************/
1791 * cloog_domain_list_free function:
1792 * This function frees the allocated memory for a CloogDomainList structure.
1793 * - November 6th 2001: first version.
1796 cloog_domain_list_free (CloogDomainList
* list
)
1798 CloogDomainList
*temp
;
1800 while (list
!= NULL
)
1802 temp
= cloog_next_domain (list
);
1803 cloog_domain_free (cloog_domain (list
));
1810 /******************************************************************************
1811 * Reading function *
1812 ******************************************************************************/
1816 * cloog_domain_read function:
1817 * Adaptation from the PolyLib. This function reads a matrix into a file (foo,
1818 * posibly stdin) and returns a pointer to a polyhedron containing the read
1820 * - October 18th 2001: first version.
1823 cloog_domain_read (FILE * foo
)
1825 CloogMatrix
*matrix
;
1826 CloogDomain
*domain
;
1828 matrix
= cloog_matrix_read (foo
);
1829 domain
= cloog_domain_matrix2domain (matrix
);
1830 cloog_matrix_free (matrix
);
1832 return print_result ("cloog_domain_read", domain
);
1837 * cloog_domain_union_read function:
1838 * This function reads a union of polyhedra into a file (foo, posibly stdin) and
1839 * returns a pointer to a Polyhedron containing the read information.
1840 * - September 9th 2002: first version.
1841 * - October 29th 2005: (debug) removal of a leak counting "correction" that
1842 * was just false since ages.
1845 cloog_domain_union_read (FILE * foo
)
1847 int i
, nb_components
;
1849 CloogDomain
*domain
, *temp
, *old
;
1851 /* domain reading: nb_components (constraint matrices). */
1852 while (fgets (s
, MAX_STRING
, foo
) == 0);
1853 while ((*s
== '#' || *s
== '\n') || (sscanf (s
, " %d", &nb_components
) < 1))
1854 fgets (s
, MAX_STRING
, foo
);
1856 if (nb_components
> 0)
1857 { /* 1. first part of the polyhedra union, */
1858 domain
= cloog_domain_read (foo
);
1859 /* 2. and the nexts. */
1860 for (i
= 1; i
< nb_components
; i
++)
1861 { /* Leak counting is OK since next allocated domain is freed here. */
1862 temp
= cloog_domain_read (foo
);
1864 domain
= cloog_domain_union (temp
, old
);
1865 cloog_domain_free (temp
);
1866 cloog_domain_free (old
);
1868 return print_result ("cloog_domain_union_read", cloog_check_domain (domain
));
1876 * cloog_domain_list_read function:
1877 * This function reads a list of polyhedra into a file (foo, posibly stdin) and
1878 * returns a pointer to a CloogDomainList containing the read information.
1879 * - November 6th 2001: first version.
1882 cloog_domain_list_read (FILE * foo
)
1886 CloogDomainList
*list
, *now
, *next
;
1889 /* We read first the number of polyhedra in the list. */
1890 while (fgets (s
, MAX_STRING
, foo
) == 0);
1891 while ((*s
== '#' || *s
== '\n') || (sscanf (s
, " %d", &nb_pols
) < 1))
1892 fgets (s
, MAX_STRING
, foo
);
1894 /* Then we read the polyhedra. */
1898 list
= (CloogDomainList
*) malloc (sizeof (CloogDomainList
));
1899 cloog_set_domain (list
, cloog_domain_read (foo
));
1900 cloog_set_next_domain (list
, NULL
);
1902 for (i
= 1; i
< nb_pols
; i
++)
1904 next
= (CloogDomainList
*) malloc (sizeof (CloogDomainList
));
1905 cloog_set_domain (next
, cloog_domain_read (foo
));
1906 cloog_set_next_domain (next
, NULL
);
1907 cloog_set_next_domain (now
, next
);
1908 now
= cloog_next_domain (now
);
1915 /******************************************************************************
1916 * Processing functions *
1917 ******************************************************************************/
1920 * cloog_domain_isempty function:
1921 * This function returns 1 if the polyhedron given as input is empty, 0
1923 * - October 28th 2001: first version.
1926 cloog_domain_isempty (CloogDomain
* domain
)
1928 if (cloog_domain_polyhedron (domain
) == NULL
)
1931 if (cloog_upol_next (cloog_domain_upol (domain
)))
1934 return ((cloog_domain_dim (domain
) < cloog_domain_nbeq (domain
)) ? 1 : 0);
1938 * cloog_domain_project function:
1939 * From Quillere's LoopGen 0.4. This function returns the projection of
1940 * (domain) on the (level) first dimensions (i.e. outer loops). It returns a
1941 * pointer to the projected Polyhedron.
1942 * - nb_par is the number of parameters.
1944 * - October 27th 2001: first version.
1945 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1949 cloog_domain_project (CloogDomain
* domain
, int level
, int nb_par
)
1951 CloogDomain
*res
= NULL
;
1952 polyhedra_union upol
= cloog_domain_upol (domain
);
1953 int i
, diff
= cloog_domain_dim (domain
) - level
- nb_par
;
1955 ppl_dimension_type
*to_remove
;
1959 fprintf (stderr
, "cloog_domain_project should not be called with"
1960 "cloog_domain_dim (domain) < level + nb_par");
1965 return print_result ("cloog_domain_project", cloog_domain_copy (domain
));
1968 to_remove
= (ppl_dimension_type
*) malloc (n
* sizeof (ppl_dimension_type
));
1970 for (i
= 0; i
< n
; i
++)
1971 to_remove
[i
] = i
+ level
;
1975 ppl_Polyhedron_t ppl
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (upol
));
1977 ppl_Polyhedron_remove_space_dimensions (ppl
, to_remove
, n
);
1978 res
= cloog_domain_add_domain (res
, cloog_translate_ppl_polyhedron (ppl
));
1979 ppl_delete_Polyhedron (ppl
);
1980 upol
= cloog_upol_next (upol
);
1983 return print_result ("cloog_domain_project", res
);
1987 * cloog_domain_extend function:
1988 * From Quillere's LoopGen 0.4. This function returns the (domain) given as
1989 * input with (dim)+(nb_par) dimensions. The new dimensions are added before
1990 * the (nb_par) parameters. This function does not free (domain), and returns
1992 * - nb_par is the number of parameters.
1994 * - October 27th 2001: first version.
1995 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1999 cloog_domain_extend (CloogDomain
* domain
, int dim
, int nb_par
)
2001 CloogDomain
*res
= NULL
;
2002 polyhedra_union upol
= cloog_domain_upol (domain
);
2003 int i
, k
, n
, diff
= dim
+ nb_par
- cloog_domain_dim (domain
);
2004 ppl_dimension_type
*map
;
2005 ppl_dimension_type to_add
= diff
;
2008 return print_result ("cloog_domain_extend", cloog_domain_copy (domain
));
2011 map
= (ppl_dimension_type
*) malloc (n
* sizeof (ppl_dimension_type
));
2013 k
= cloog_domain_dim (domain
) - nb_par
;
2014 for (i
= 0; i
< k
; i
++)
2023 map
[i
] = i
- nb_par
;
2027 ppl_Polyhedron_t ppl
= cloog_translate_constraint_matrix (cloog_upol_domain2matrix (upol
));
2029 ppl_Polyhedron_add_space_dimensions_and_embed (ppl
, to_add
);
2030 ppl_Polyhedron_map_space_dimensions (ppl
, map
, n
);
2031 res
= cloog_domain_add_domain (res
, cloog_translate_ppl_polyhedron (ppl
));
2032 ppl_delete_Polyhedron (ppl
);
2033 upol
= cloog_upol_next (upol
);
2036 return print_result ("cloog_domain_extend", res
);
2040 * cloog_domain_never_integral function:
2041 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0. This
2042 * function returns a boolean set to 1 if there is this kind of 'never true'
2043 * constraint inside a polyhedron, 0 otherwise.
2044 * - domain is the polyhedron to check,
2046 * - November 28th 2001: first version.
2047 * - June 26th 2003: for iterators, more 'never true' constraints are found
2048 * (compare cholesky2 and vivien with a previous version),
2049 * checking for the parameters created (compare using vivien).
2050 * - June 28th 2003: Previously in loop.c and called
2051 * cloog_loop_simplify_nevertrue, now here !
2052 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2054 * - October 14th 2005: Complete rewriting, not faster but code quite shorter.
2057 cloog_domain_never_integral (CloogDomain
* domain
)
2059 int i
, dimension
, nbc
;
2061 Polyhedron
*polyhedron
;
2063 if ((domain
== NULL
) || (cloog_domain_polyhedron (domain
) == NULL
))
2067 value_init_c (modulo
);
2068 polyhedron
= d2p (domain
);
2069 dimension
= cloog_domain_dim (domain
) + 2;
2070 nbc
= cloog_domain_nbconstraints (domain
);
2072 /* For each constraint... */
2073 for (i
= 0; i
< nbc
; i
++)
2074 { /* If we have an equality and the scalar part is not zero... */
2075 if (value_zero_p (polyhedron
->Constraint
[i
][0]) &&
2076 value_notzero_p (polyhedron
->Constraint
[i
][dimension
- 1]))
2077 { /* Then we check whether the scalar can be divided by the gcd of the
2078 * unknown vector (including iterators and parameters) or not. If not,
2079 * there is no integer point in the polyhedron and we return 1.
2081 cloog_vector_gcd (&(polyhedron
->Constraint
[i
][1]), dimension
- 2, &gcd
);
2082 value_modulus (modulo
,
2083 polyhedron
->Constraint
[i
][dimension
- 1],
2086 if (value_notzero_p (modulo
))
2088 value_clear_c (gcd
);
2089 value_clear_c (modulo
);
2090 Polyhedron_Free (polyhedron
);
2096 value_clear_c (gcd
);
2097 value_clear_c (modulo
);
2098 Polyhedron_Free (polyhedron
);
2104 * cloog_domain_stride function:
2105 * This function finds the stride imposed to unknown with the column number
2106 * 'strided_level' in order to be integral. For instance, if we have a
2107 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
2108 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
2109 * the unknown i. The function returns the imposed stride in a parameter field.
2110 * - domain is the set of constraint we have to consider,
2111 * - strided_level is the column number of the unknown for which a stride have
2113 * - looking_level is the column number of the unknown that impose a stride to
2114 * the first unknown.
2115 * - stride is the stride that is returned back as a function parameter.
2116 * - offset is the value of the constant c if the condition is of the shape
2117 * (i + c)%s = 0, s being the stride.
2119 * - June 28th 2003: first version.
2120 * - July 14th 2003: can now look for multiple striding constraints and returns
2121 * the GCD of the strides and the common offset.
2122 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2126 cloog_domain_stride (domain
, strided_level
, nb_par
, stride
, offset
)
2127 CloogDomain
*domain
;
2128 int strided_level
, nb_par
;
2129 Value
*stride
, *offset
;
2132 int n_col
, n_row
, rank
;
2136 Polyhedron
*polyhedron
= d2p (domain
);
2137 int dimension
= cloog_domain_dim (domain
);
2138 int nbeq
= cloog_domain_nbeq (domain
);
2140 /* Look at all equalities involving strided_level and the inner
2141 * iterators. We can ignore the outer iterators and the parameters
2142 * here because the lower bound on strided_level is assumed to
2145 n_col
= (1 + dimension
- nb_par
) - strided_level
;
2146 for (i
= 0, n_row
= 0; i
< nbeq
; i
++)
2147 if (cloog_first_non_zero
2148 (polyhedron
->Constraint
[i
] + strided_level
, n_col
) != -1)
2151 M
= cloog_matrix_alloc (n_row
+ 1, n_col
+ 1);
2152 for (i
= 0, n_row
= 0; i
< nbeq
; i
++)
2154 if (cloog_first_non_zero
2155 (polyhedron
->Constraint
[i
] + strided_level
, n_col
) == -1)
2157 cloog_vector_copy (polyhedron
->Constraint
[i
] + strided_level
,
2158 M
->p
[n_row
], n_col
);
2159 value_assign (M
->p
[n_row
][n_col
],
2160 polyhedron
->Constraint
[i
][1 + dimension
]);
2163 value_set_si (M
->p
[n_row
][n_col
], 1);
2165 /* Then look at the general solution to the above equalities. */
2166 rank
= SolveDiophantine (m_c2p (M
), &U
, &V
);
2167 cloog_matrix_free (M
);
2171 /* There is no solution, so the body of this loop will
2172 * never execute. We just leave the constraints alone here so
2173 * that they will ensure the body will not be executed.
2174 * We should probably propagate this information up so that
2175 * the loop can be removed entirely.
2177 value_set_si (*offset
, 0);
2178 value_set_si (*stride
, 1);
2182 /* Compute the gcd of the coefficients defining strided_level. */
2183 cloog_vector_gcd (U
->p
[0], U
->NbColumns
, stride
);
2184 value_oppose (*offset
, V
->p
[0]);
2185 value_pmodulus (*offset
, *offset
, *stride
);
2189 Polyhedron_Free (polyhedron
);
2195 * cloog_domain_integral_lowerbound function:
2196 * This function returns 1 if the lower bound of an iterator (such as its
2197 * column rank in the constraint set 'domain' is 'level') is integral,
2198 * 0 otherwise. If the lower bound is actually integral, the function fills
2199 * the 'lower' field with the lower bound value.
2200 * - June 29th 2003: first version.
2201 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2205 cloog_domain_integral_lowerbound (domain
, level
, lower
)
2206 CloogDomain
*domain
;
2210 int i
, first_lower
= 1, dimension
, lower_constraint
= -1, nbc
;
2211 Value iterator
, constant
, tmp
;
2212 Polyhedron
*polyhedron
;
2214 polyhedron
= d2p (domain
);
2215 dimension
= cloog_domain_dim (domain
);
2216 nbc
= cloog_domain_nbconstraints (domain
);
2218 /* We want one and only one lower bound (e.g. no equality, no maximum
2221 for (i
= 0; i
< nbc
; i
++)
2222 if (value_zero_p (polyhedron
->Constraint
[i
][0])
2223 && value_notzero_p (polyhedron
->Constraint
[i
][level
]))
2225 Polyhedron_Free (polyhedron
);
2229 for (i
= 0; i
< nbc
; i
++)
2230 if (value_pos_p (polyhedron
->Constraint
[i
][level
]))
2235 lower_constraint
= i
;
2239 Polyhedron_Free (polyhedron
);
2246 Polyhedron_Free (polyhedron
);
2250 /* We want an integral lower bound: no other non-zero entry except the
2251 * iterator coefficient and the constant.
2253 for (i
= 1; i
< level
; i
++)
2255 (polyhedron
->Constraint
[lower_constraint
][i
]))
2257 Polyhedron_Free (polyhedron
);
2261 for (i
= level
+ 1; i
<= dimension
; i
++)
2263 (polyhedron
->Constraint
[lower_constraint
][i
]))
2265 Polyhedron_Free (polyhedron
);
2269 value_init_c (iterator
);
2270 value_init_c (constant
);
2273 /* If all is passed, then find the lower bound and return 1. */
2274 value_assign (iterator
,
2275 polyhedron
->Constraint
[lower_constraint
][level
]);
2276 value_oppose (constant
,
2277 polyhedron
->Constraint
[lower_constraint
][dimension
+ 1]);
2279 value_modulus (tmp
, constant
, iterator
);
2280 value_division (*lower
, constant
, iterator
);
2282 if (!(value_zero_p (tmp
) || value_neg_p (constant
)))
2283 value_increment (*lower
, *lower
);
2285 value_clear_c (iterator
);
2286 value_clear_c (constant
);
2287 value_clear_c (tmp
);
2288 Polyhedron_Free (polyhedron
);
2294 * cloog_domain_lowerbound_update function:
2295 * This function updates the integral lower bound of an iterator (such as its
2296 * column rank in the constraint set 'domain' is 'level') into 'lower'.
2297 * - Jun 29th 2003: first version.
2298 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2302 cloog_domain_lowerbound_update (domain
, level
, lower
)
2303 CloogDomain
*domain
;
2308 int nbc
= cloog_domain_nbconstraints (domain
);
2309 int dim
= cloog_domain_dim (domain
);
2310 polyhedron p
= cloog_domain_polyhedron (domain
);
2312 /* There is only one lower bound, the first one is the good one. */
2313 for (i
= 0; i
< nbc
; i
++)
2314 if (value_pos_p (p
->Constraint
[i
][level
]))
2316 value_set_si (p
->Constraint
[i
][level
], 1);
2317 value_oppose (p
->Constraint
[i
][dim
+ 1], lower
);
2324 * cloog_domain_lazy_equal function:
2325 * This function returns 1 if the domains given as input are the same, 0 if it
2326 * is unable to decide. This function makes an entry-to-entry comparison between
2327 * the constraint systems, if all the entries are the same, the domains are
2328 * obviously the same and it returns 1, at the first difference, it returns 0.
2329 * This is a very fast way to verify this property. It has been shown (with the
2330 * CLooG benchmarks) that operations on equal domains are 17% of all the
2331 * polyhedral computations. For 75% of the actually identical domains, this
2332 * function answer that they are the same and allow to give immediately the
2333 * trivial solution instead of calling the heavy general functions of PolyLib.
2334 * - August 22th 2003: first version.
2335 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2339 cloog_domain_lazy_equal (CloogDomain
* d1
, CloogDomain
* d2
)
2342 polyhedra_union u1
= cloog_domain_upol (d1
);
2343 polyhedra_union u2
= cloog_domain_upol (d2
);
2347 if ((cloog_upol_nbc (u1
) != cloog_upol_nbc (u2
)) ||
2348 (cloog_upol_dim (u1
) != cloog_upol_dim (u2
)))
2351 for (i
= 0; i
< cloog_upol_nbc (u1
); i
++)
2352 for (j
= 0; j
< cloog_upol_dim (u1
) + 2; j
++)
2353 if (value_ne (cloog_upol_polyhedron (u1
)->Constraint
[i
][j
],
2354 cloog_upol_polyhedron (u2
)->Constraint
[i
][j
]))
2357 u1
= cloog_upol_next (u1
);
2358 u2
= cloog_upol_next (u2
);
2369 * cloog_domain_lazy_block function:
2370 * This function returns 1 if the two domains d1 and d2 given as input are the
2371 * same (possibly except for a dimension equal to a constant where we accept
2372 * a difference of 1) AND if we are sure that there are no other domain in
2373 * the code generation problem that may put integral points between those of
2374 * d1 and d2 (0 otherwise). In fact this function answers the question "can I
2375 * safely consider the two domains as only one with two statements (a block) ?".
2376 * This function is lazy: it asks for very standard scattering representation
2377 * (only one constraint per dimension which is an equality, and the constraints
2378 * are ordered per dimension depth: the left hand side of the constraint matrix
2379 * is the identity) and will answer NO at the very first problem.
2380 * - d1 and d2 are the two domains to check for blocking,
2381 * - scattering is the linked list of all domains,
2382 * - scattdims is the total number of scattering dimentions.
2384 * - April 30th 2005: beginning
2385 * - June 9th 2005: first working version.
2386 * - June 10th 2005: debugging.
2387 * - June 21rd 2005: Adaptation for GMP.
2388 * - October 16th 2005: (debug) some false blocks have been removed.
2391 cloog_domain_lazy_block (d1
, d2
, scattering
, scattdims
)
2392 CloogDomain
*d1
, *d2
;
2393 CloogDomainList
*scattering
;
2396 int i
, j
, difference
= 0, different_constraint
= 0, nbc
;
2398 Value date1
, date2
, date3
, temp
;
2399 Polyhedron
*p1
, *p2
;
2401 /* Some basic checks: we only accept convex domains, with same constraint
2402 * and dimension numbers.
2404 if (!cloog_domain_isconvex (d1
) || !cloog_domain_isconvex (d2
) ||
2405 (cloog_domain_nbconstraints (d1
) != cloog_domain_nbconstraints (d2
)) ||
2406 (cloog_domain_dim (d1
) != cloog_domain_dim (d2
)))
2411 nbc
= cloog_domain_nbconstraints (d1
);
2412 dim1
= cloog_domain_dim (d1
);
2413 dim2
= cloog_domain_dim (d2
);
2415 /* There should be only one difference between the two domains, it
2416 * has to be at the constant level and the difference must be of +1,
2417 * moreover, after the difference all domain coefficient has to be 0.
2418 * The matrix shape is:
2420 * |===========|=====|<- 0 line
2421 * |===========|=====|
2422 * |===========|====?|<- different_constraint line (found here)
2423 * |===========|0000=|
2424 * |===========|0000=|<- pX->NbConstraints line
2427 * | | (pX->Dimension + 2) column
2428 * | scattdims column
2432 value_init_c (temp
);
2433 for (i
= 0; i
< nbc
; i
++)
2435 if (difference
== 0)
2436 { /* All elements except scalar must be equal. */
2437 for (j
= 0; j
< dim1
+ 1; j
++)
2438 if (value_ne (p1
->Constraint
[i
][j
],
2439 p2
->Constraint
[i
][j
]))
2441 value_clear_c (temp
);
2442 Polyhedron_Free (p1
);
2443 Polyhedron_Free (p2
);
2446 /* The scalar may differ from +1 (now j=(p1->Dimension + 1)). */
2447 if (value_ne (p1
->Constraint
[i
][j
],
2448 p2
->Constraint
[i
][j
]))
2450 value_increment (temp
, p2
->Constraint
[i
][j
]);
2451 if (value_ne (p1
->Constraint
[i
][j
], temp
))
2453 value_clear_c (temp
);
2454 Polyhedron_Free (p1
);
2455 Polyhedron_Free (p2
);
2461 different_constraint
= i
;
2466 { /* Scattering coefficients must be equal. */
2467 for (j
= 0; j
< (scattdims
+ 1); j
++)
2468 if (value_ne (p1
->Constraint
[i
][j
],
2469 p2
->Constraint
[i
][j
]))
2471 value_clear_c (temp
);
2472 Polyhedron_Free (p1
);
2473 Polyhedron_Free (p2
);
2477 /* Domain coefficients must be 0. */
2478 for (; j
< dim1
+ 1; j
++)
2479 if (value_notzero_p (p1
->Constraint
[i
][j
])
2480 || value_notzero_p (p2
->Constraint
[i
][j
]))
2482 value_clear_c (temp
);
2483 Polyhedron_Free (p1
);
2484 Polyhedron_Free (p2
);
2488 /* Scalar must be equal. */
2489 if (value_ne (p1
->Constraint
[i
][j
],
2490 p2
->Constraint
[i
][j
]))
2492 value_clear_c (temp
);
2493 Polyhedron_Free (p1
);
2494 Polyhedron_Free (p2
);
2499 value_clear_c (temp
);
2501 /* If the domains are exactly the same, this is a block. */
2502 if (difference
== 0)
2504 Polyhedron_Free (p1
);
2505 Polyhedron_Free (p2
);
2509 /* Now a basic check that the constraint with the difference is an
2510 * equality of a dimension with a constant.
2512 for (i
= 0; i
<= different_constraint
; i
++)
2513 if (value_notzero_p (p1
->Constraint
[different_constraint
][i
]))
2515 Polyhedron_Free (p1
);
2516 Polyhedron_Free (p2
);
2520 if (value_notone_p (p1
->Constraint
[different_constraint
][different_constraint
+ 1]))
2522 Polyhedron_Free (p1
);
2523 Polyhedron_Free (p2
);
2527 for (i
= different_constraint
+ 2; i
< dim1
+ 1; i
++)
2528 if (value_notzero_p (p1
->Constraint
[different_constraint
][i
]))
2530 Polyhedron_Free (p1
);
2531 Polyhedron_Free (p2
);
2535 /* For the moment, d1 and d2 are a block candidate. There remains to check
2536 * that there is no other domain that may put an integral point between
2537 * them. In our lazy test we ensure this property by verifying that the
2538 * constraint matrices have a very strict shape: let us consider that the
2539 * dimension with the difference is d. Then the first d dimensions are
2540 * defined in their depth order using equalities (thus the first column begins
2541 * with d zeroes, there is a d*d identity matrix and a zero-matrix for
2542 * the remaining simensions). If a domain can put integral points between the
2543 * domains of the block candidate, this means that the other entries on the
2544 * first d constraints are equal to those of d1 or d2. Thus we are looking for
2545 * such a constraint system, if it exists d1 and d2 is considered to not be
2546 * a block, it is a bock otherwise.
2548 * 1. Only equalities (for the first different_constraint+1 lines).
2549 * | 2. Must be the identity.
2550 * | | 3. Must be zero.
2551 * | | | 4. Elements are equal, the last one is either date1 or 2.
2554 * |0|100|00000|=====|<- 0 line
2555 * |0|010|00000|=====|
2556 * |0|001|00000|====?|<- different_constraint line
2557 * |*|***|*****|*****|
2558 * |*|***|*****|*****|<- pX->NbConstraints line
2561 * | | | (pX->Dimension + 2) column
2562 * | | scattdims column
2563 * | different_constraint+1 column
2567 /* Step 1 and 2. This is only necessary to check one domain because
2568 * we checked that they are equal on this part before.
2570 for (i
= 0; i
<= different_constraint
; i
++)
2572 for (j
= 0; j
< i
+ 1; j
++)
2573 if (value_notzero_p (p1
->Constraint
[i
][j
]))
2575 Polyhedron_Free (p1
);
2576 Polyhedron_Free (p2
);
2580 if (value_notone_p (p1
->Constraint
[i
][i
+ 1]))
2582 Polyhedron_Free (p1
);
2583 Polyhedron_Free (p2
);
2587 for (j
= i
+ 2; j
<= different_constraint
+ 1; j
++)
2588 if (value_notzero_p (p1
->Constraint
[i
][j
]))
2590 Polyhedron_Free (p1
);
2591 Polyhedron_Free (p2
);
2597 for (i
= 0; i
<= different_constraint
; i
++)
2598 for (j
= different_constraint
+ 2; j
<= scattdims
; j
++)
2599 if (value_notzero_p (p1
->Constraint
[i
][j
]))
2601 Polyhedron_Free (p1
);
2602 Polyhedron_Free (p2
);
2606 value_init_c (date1
);
2607 value_init_c (date2
);
2608 value_init_c (date3
);
2610 /* Now we have to check that the two different dates are unique. */
2611 value_assign (date1
, p1
->Constraint
[different_constraint
][dim1
+ 1]);
2612 value_assign (date2
, p2
->Constraint
[different_constraint
][dim2
+ 1]);
2614 /* Step 4. We check all domains except d1 and d2 and we look for at least
2615 * a difference with d1 or d2 on the first different_constraint+1 dimensions.
2617 while (scattering
!= NULL
)
2619 if ((cloog_domain (scattering
) != d1
)
2620 && (cloog_domain (scattering
) != d2
))
2622 CloogDomain
*d3
= cloog_domain (scattering
);
2623 Polyhedron
*p3
= d2p (d3
);
2624 int dim3
= cloog_domain_dim (d3
);
2626 value_assign (date3
,
2627 p3
->Constraint
[different_constraint
][dim3
+ 1]);
2630 if (value_ne (date3
, date2
) && value_ne (date3
, date1
))
2633 for (i
= 0; (i
< different_constraint
) && (!difference
); i
++)
2634 for (j
= 0; (j
< dim3
+ 2) && !difference
; j
++)
2636 (p1
->Constraint
[i
][j
],
2637 p3
->Constraint
[i
][j
]))
2640 for (j
= 0; (j
< dim3
+ 1) && !difference
; j
++)
2642 (p1
->Constraint
[different_constraint
][j
],
2643 p3
->Constraint
[different_constraint
][j
]))
2646 Polyhedron_Free (p3
);
2649 value_clear_c (date1
);
2650 value_clear_c (date2
);
2651 value_clear_c (date3
);
2652 Polyhedron_Free (p1
);
2653 Polyhedron_Free (p2
);
2658 scattering
= cloog_next_domain (scattering
);
2661 Polyhedron_Free (p1
);
2662 Polyhedron_Free (p2
);
2663 value_clear_c (date1
);
2664 value_clear_c (date2
);
2665 value_clear_c (date3
);
2671 * cloog_domain_lazy_disjoint function:
2672 * This function returns 1 if the domains given as input are disjoint, 0 if it
2673 * is unable to decide. This function finds the unknown with fixed values in
2674 * both domains (on a given constraint, their column entry is not zero and
2675 * only the constant coefficient can be different from zero) and verify that
2676 * their values are the same. If not, the domains are obviously disjoint and
2677 * it returns 1, if there is not such case it returns 0. This is a very fast
2678 * way to verify this property. It has been shown (with the CLooG benchmarks)
2679 * that operations on disjoint domains are 36% of all the polyhedral
2680 * computations. For 94% of the actually identical domains, this
2681 * function answer that they are disjoint and allow to give immediately the
2682 * trivial solution instead of calling the heavy general functions of PolyLib.
2683 * - August 22th 2003: first version.
2684 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2688 cloog_domain_lazy_disjoint (CloogDomain
* d1
, CloogDomain
* d2
)
2690 int i1
, j1
, i2
, j2
, scat_dim
, nbc1
, nbc2
;
2693 Polyhedron
*p1
, *p2
;
2695 if (!cloog_domain_isconvex (d1
) || !cloog_domain_isconvex (d2
))
2700 nbc1
= cloog_domain_nbconstraints (d1
);
2701 nbc2
= cloog_domain_nbconstraints (d2
);
2702 dim1
= cloog_domain_dim (d1
);
2703 dim2
= cloog_domain_dim (d2
);
2704 value_init_c (scat_val
);
2706 for (i1
= 0; i1
< nbc1
; i1
++)
2708 if (value_notzero_p (p1
->Constraint
[i1
][0]))
2712 while (value_zero_p (p1
->Constraint
[i1
][scat_dim
]) &&
2716 if (value_notone_p (p1
->Constraint
[i1
][scat_dim
]))
2720 for (j1
= scat_dim
+ 1; j1
<= dim1
; j1
++)
2721 if (value_notzero_p (p1
->Constraint
[i1
][j1
]))
2727 value_assign (scat_val
,
2728 p1
->Constraint
[i1
][dim1
+ 1]);
2730 for (i2
= 0; i2
< nbc2
; i2
++)
2732 for (j2
= 0; j2
< scat_dim
; j2
++)
2733 if (value_notzero_p (p2
->Constraint
[i2
][j2
]))
2736 if ((j2
!= scat_dim
)
2738 value_notone_p (p2
->Constraint
[i2
][scat_dim
]))
2741 for (j2
= scat_dim
+ 1; j2
< dim2
; j2
++)
2742 if (value_notzero_p (p2
->Constraint
[i2
][j2
]))
2749 (p2
->Constraint
[i2
][dim2
+ 1], scat_val
))
2751 value_clear_c (scat_val
);
2758 value_clear_c (scat_val
);
2759 Polyhedron_Free (p1
);
2760 Polyhedron_Free (p2
);
2766 * cloog_domain_list_lazy_same function:
2767 * This function returns 1 if two domains in the list are the same, 0 if it
2768 * is unable to decide.
2769 * - February 9th 2004: first version.
2772 cloog_domain_list_lazy_same (CloogDomainList
* list
)
2773 { /*int i=1, j=1 ; */
2774 CloogDomainList
*current
, *next
;
2777 while (current
!= NULL
)
2779 next
= cloog_next_domain (current
);
2781 while (next
!= NULL
)
2783 if (cloog_domain_lazy_equal (cloog_domain (current
),
2784 cloog_domain (next
)))
2785 { /*printf("Same domains: %d and %d\n",i,j) ; */
2789 next
= cloog_next_domain (next
);
2792 current
= cloog_next_domain (current
);
2799 * cloog_domain_cut_first function:
2800 * this function returns a CloogDomain structure with everything except the
2801 * first part of the polyhedra union of the input domain as domain. After a call
2802 * to this function, there remains in the CloogDomain structure provided as
2803 * input only the first part of the original polyhedra union.
2804 * - April 20th 2005: first version, extracted from different part of loop.c.
2807 cloog_domain_cut_first (CloogDomain
* domain
)
2811 if (domain
&& cloog_domain_polyhedron (domain
))
2813 if (!cloog_upol_next (cloog_domain_upol (domain
)))
2816 rest
= cloog_new_domain (cloog_upol_next (cloog_domain_upol (domain
)));
2817 cloog_upol_set_next (cloog_domain_upol (domain
), NULL
);
2822 return print_result ("cloog_domain_cut_first", cloog_check_domain (rest
));
2827 * cloog_domain_lazy_isscalar function:
2828 * this function returns 1 if the dimension 'dimension' in the domain 'domain'
2829 * is scalar, this means that the only constraint on this dimension must have
2830 * the shape "x.dimension + scalar = 0" with x an integral variable. This
2831 * function is lazy since we only accept x=1 (further calculations are easier
2833 * - June 14th 2005: first version.
2834 * - June 21rd 2005: Adaptation for GMP.
2837 cloog_domain_lazy_isscalar (CloogDomain
* domain
, int dimension
)
2840 Polyhedron
*polyhedron
= d2p (domain
);
2841 int nbc
= cloog_domain_nbconstraints (domain
);
2842 int dim
= cloog_domain_dim (domain
);
2844 /* For each constraint... */
2845 for (i
= 0; i
< nbc
; i
++)
2846 { /* ...if it is concerned by the potentially scalar dimension... */
2848 (polyhedron
->Constraint
[i
][dimension
+ 1]))
2849 { /* ...check that the constraint has the shape "dimension + scalar = 0". */
2850 for (j
= 0; j
<= dimension
; j
++)
2851 if (value_notzero_p (polyhedron
->Constraint
[i
][j
]))
2853 Polyhedron_Free (polyhedron
);
2858 (polyhedron
->Constraint
[i
][dimension
+ 1]))
2860 Polyhedron_Free (polyhedron
);
2864 for (j
= dimension
+ 2; j
< dim
+ 1; j
++)
2865 if (value_notzero_p (polyhedron
->Constraint
[i
][j
]))
2867 Polyhedron_Free (polyhedron
);
2873 Polyhedron_Free (polyhedron
);
2879 * cloog_domain_scalar function:
2880 * when we call this function, we know that "dimension" is a scalar dimension,
2881 * this function finds the scalar value in "domain" and returns it in "value".
2882 * - June 30th 2005: first version.
2885 cloog_domain_scalar (CloogDomain
* domain
, int dimension
, Value
* value
)
2888 Polyhedron
*polyhedron
= d2p (domain
);
2889 int nbc
= cloog_domain_nbconstraints (domain
);
2890 int dim
= cloog_domain_dim (domain
);
2892 /* For each constraint... */
2893 for (i
= 0; i
< nbc
; i
++)
2894 { /* ...if it is the equality defining the scalar dimension... */
2896 (polyhedron
->Constraint
[i
][dimension
+ 1])
2897 && value_zero_p (polyhedron
->Constraint
[i
][0]))
2898 { /* ...Then send the scalar value. */
2899 value_assign (*value
, polyhedron
->Constraint
[i
][dim
+ 1]);
2900 value_oppose (*value
, *value
);
2901 Polyhedron_Free (polyhedron
);
2906 /* We should have found a scalar value: if not, there is an error. */
2907 fprintf (stderr
, "[CLooG]ERROR: dimension %d is not scalar as expected.\n",
2909 Polyhedron_Free (polyhedron
);
2915 * cloog_domain_erase_dimension function:
2916 * this function returns a CloogDomain structure builds from 'domain' where
2917 * we removed the dimension 'dimension' and every constraint considering this
2918 * dimension. This is not a projection ! Every data concerning the
2919 * considered dimension is simply erased.
2920 * - June 14th 2005: first version.
2921 * - June 21rd 2005: Adaptation for GMP.
2924 cloog_domain_erase_dimension (CloogDomain
* domain
, int dimension
)
2926 int i
, j
, mi
, nb_dim
, nbc
;
2927 CloogMatrix
*matrix
;
2928 CloogDomain
*erased
;
2929 Polyhedron
*polyhedron
;
2931 polyhedron
= d2p (domain
);
2932 nb_dim
= cloog_domain_dim (domain
);
2933 nbc
= cloog_domain_nbconstraints (domain
);
2935 /* The matrix is one column less and at least one constraint less. */
2936 matrix
= cloog_matrix_alloc (nbc
- 1, nb_dim
+ 1);
2938 /* mi is the constraint counter for the matrix. */
2940 for (i
= 0; i
< nbc
; i
++)
2941 if (value_zero_p (polyhedron
->Constraint
[i
][dimension
+ 1]))
2943 for (j
= 0; j
<= dimension
; j
++)
2944 value_assign (matrix
->p
[mi
][j
],
2945 polyhedron
->Constraint
[i
][j
]);
2947 for (j
= dimension
+ 2; j
< nb_dim
+ 2; j
++)
2948 value_assign (matrix
->p
[mi
][j
- 1],
2949 polyhedron
->Constraint
[i
][j
]);
2954 erased
= cloog_domain_matrix2domain (matrix
);
2955 cloog_matrix_free (matrix
);
2957 Polyhedron_Free (polyhedron
);
2958 return print_result ("cloog_domain_erase_dimension", cloog_check_domain (erased
));
2961 /* Number of polyhedra inside the union of disjoint polyhedra. */
2964 cloog_domain_nb_polyhedra (CloogDomain
* domain
)
2967 polyhedra_union upol
= cloog_domain_upol (domain
);
2972 upol
= cloog_upol_next (upol
);
2979 cloog_domain_print_polyhedra (FILE * foo
, CloogDomain
* domain
)
2981 polyhedra_union upol
= cloog_domain_upol (domain
);
2983 while (upol
!= NULL
)
2985 CloogMatrix
*matrix
= cloog_upol_domain2matrix (upol
);
2986 cloog_matrix_print (foo
, matrix
);
2987 cloog_matrix_free (matrix
);
2988 upol
= cloog_upol_next (upol
);
2993 debug_cloog_domain (CloogDomain
*domain
)
2995 cloog_domain_print_polyhedra (stderr
, domain
);
2999 debug_cloog_matrix (CloogMatrix
*m
)
3001 cloog_matrix_print (stderr
, m
);