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 "cloog/cloog.h"
45 #ifndef USE_PPL_POWERSETS
46 # define USE_PPL_POWERSETS 1
49 /* Variables names for pretty printing. */
50 static char wild_name
[200][40];
52 static inline const char*
53 variable_output_function (ppl_dimension_type var
)
56 return wild_name
[var
+ 1];
62 error_handler (enum ppl_enum_error_code code
, const char* description
)
64 fprintf (stderr
, "PPL error code %d\n%s", code
, description
);
69 cloog_initialize (void)
71 sprintf (wild_name
[0], "1");
72 sprintf (wild_name
[1], "a");
73 sprintf (wild_name
[2], "b");
74 sprintf (wild_name
[3], "c");
75 sprintf (wild_name
[4], "d");
76 sprintf (wild_name
[5], "e");
77 sprintf (wild_name
[6], "f");
78 sprintf (wild_name
[7], "g");
79 sprintf (wild_name
[8], "h");
80 sprintf (wild_name
[9], "i");
81 sprintf (wild_name
[10], "j");
82 sprintf (wild_name
[11], "k");
83 sprintf (wild_name
[12], "l");
84 sprintf (wild_name
[13], "m");
85 sprintf (wild_name
[14], "n");
86 sprintf (wild_name
[15], "o");
87 sprintf (wild_name
[16], "p");
88 sprintf (wild_name
[17], "q");
89 sprintf (wild_name
[18], "r");
90 sprintf (wild_name
[19], "s");
91 sprintf (wild_name
[20], "t");
92 sprintf (wild_name
[21], "alpha");
93 sprintf (wild_name
[22], "beta");
94 sprintf (wild_name
[23], "gamma");
95 sprintf (wild_name
[24], "delta");
96 sprintf (wild_name
[25], "tau");
97 sprintf (wild_name
[26], "sigma");
98 sprintf (wild_name
[27], "chi");
99 sprintf (wild_name
[28], "omega");
100 sprintf (wild_name
[29], "pi");
101 sprintf (wild_name
[30], "ni");
102 sprintf (wild_name
[31], "Alpha");
103 sprintf (wild_name
[32], "Beta");
104 sprintf (wild_name
[33], "Gamma");
105 sprintf (wild_name
[34], "Delta");
106 sprintf (wild_name
[35], "Tau");
107 sprintf (wild_name
[36], "Sigma");
108 sprintf (wild_name
[37], "Chi");
109 sprintf (wild_name
[38], "Omega");
110 sprintf (wild_name
[39], "xxx");
112 if (ppl_initialize() < 0)
114 fprintf (stderr
, "Cannot initialize the Parma Polyhedra Library.\n");
118 if (ppl_restore_pre_PPL_rounding() < 0)
120 fprintf (stderr
, "Cannot restore the pre-PPL rounding mode.\n");
124 if (ppl_set_error_handler (error_handler
) < 0)
126 fprintf (stderr
, "Cannot install the custom error handler.\n");
130 if (ppl_io_set_variable_output_function (variable_output_function
) < 0)
132 fprintf (stderr
, "Cannot install the PPL custom variable output function. \n");
138 cloog_pol_copy (polyhedron pol
)
145 res
= cloog_new_pol (cloog_pol_dim (pol
), cloog_pol_nbc (pol
));
147 if (cloog_pol_nbc (pol
))
148 cloog_vector_copy (pol
->Constraint
[0], res
->Constraint
[0],
149 cloog_pol_nbc (pol
) * (cloog_pol_dim (pol
) + 2));
155 * The maximal number of rays allowed to be allocated by PolyLib. In fact since
156 * version 5.20, PolyLib automatically tune the number of rays by multiplying
157 * by 2 this number each time the maximum is reached. For unknown reasons
158 * PolyLib makes a segmentation fault if this number is too small. If this
159 * number is too small, performances will be reduced, if it is too high, memory
160 * will be saturated. Note that the option "-rays X" set this number to X.
164 /* Unused in this backend. */
166 int cloog_domain_allocated
= 0;
167 int cloog_domain_freed
= 0;
168 int cloog_domain_max
= 0;
170 /* The same for Value variables since in GMP mode they have to be freed. */
171 int cloog_value_allocated
= 0;
172 int cloog_value_freed
= 0;
173 int cloog_value_max
= 0;
177 cloog_domain_polyhedron_set (CloogDomain
* d
, polyhedra_union p
)
183 cloog_domain_set_references (CloogDomain
* d
, int i
)
189 cloog_new_domain (polyhedra_union p
)
191 CloogDomain
*domain
= (CloogDomain
*) malloc (sizeof (CloogDomain
));
193 cloog_domain_set_references (domain
, 1);
198 cloog_domain_alloc (polyhedron p
)
200 return cloog_new_domain (cloog_new_upol (p
));
203 static inline CloogDomain
*
204 cloog_check_domain_id (CloogDomain
*dom
)
209 static inline CloogDomain
*
210 cloog_check_domain (CloogDomain
*dom
)
219 cloog_vector_min_not_zero (Value
* p
, unsigned len
, int *index
, Value
* min
)
222 int i
= cloog_first_non_zero (p
, len
);
226 value_set_si (*min
, 1);
231 value_absolute (*min
, p
[i
]);
234 for (i
= i
+ 1; i
< (int) len
; i
++)
236 if (value_zero_p (p
[i
]))
239 value_absolute (x
, p
[i
]);
240 if (value_lt (x
, *min
))
242 value_assign (*min
, x
);
251 cloog_vector_gcd (Value
* p
, int len
, Value
* gcd
)
254 int i
, non_zero
, min_index
= 0;
256 q
= (Value
*) malloc (len
* sizeof (Value
));
258 for (i
= 0; i
< len
; i
++)
261 for (cp
= p
, cq
= q
, i
= 0; i
< len
; i
++, cq
++, cp
++)
262 value_absolute (*cq
, *cp
);
266 cloog_vector_min_not_zero (q
, len
, &min_index
, gcd
);
268 if (value_notone_p (*gcd
))
270 for (cq
= q
, non_zero
= 0, i
= 0; i
< len
; i
++, cq
++)
273 value_modulus (*cq
, *cq
, *gcd
);
274 non_zero
|= value_notzero_p (*cq
);
283 for (i
= 0; i
< len
; i
++)
290 cloog_matrix_combine (Value
* p1
, Value
* p2
, Value
* p3
, int x
, unsigned len
)
292 Value a1
, a2
, gcd
, b1
, b2
, n1
;
294 value_init (a1
), value_init (a2
), value_init (gcd
),
295 value_init (b1
), value_init (b2
), value_init (n1
);
297 value_assign (a1
, p1
[x
]);
298 value_assign (a2
, p2
[x
]);
300 value_absolute (b1
, a1
);
301 value_absolute (b2
, a2
);
305 value_division (a1
, a1
, gcd
);
306 value_division (a2
, a2
, gcd
);
307 value_oppose (n1
, a1
);
308 cloog_vector_combine (p1
+ 1, p2
+ 1, p3
+ 1, a2
, n1
, len
);
309 cloog_vector_normalize (p3
+ 1, len
);
311 value_clear (a1
), value_clear (a2
), value_clear (gcd
),
312 value_clear (b1
), value_clear (b2
), value_clear (n1
);
315 /* In the matrix representation an equality has a 0 in the first
316 column. When the value of the first column is 1, the row
317 represents an inequality. */
320 cloog_matrix_row_is_eq_p (CloogMatrix
*matrix
, int row
)
322 return value_zero_p (matrix
->p
[row
][0]);
325 static ppl_Constraint_t
326 cloog_build_ppl_cstr (ppl_Linear_Expression_t expr
, int ineq
)
328 ppl_Constraint_t cstr
;
333 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
337 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
);
341 /* Should not happen. */
348 /* Translates to PPL row I from MATRIX. CST is the constant part that
349 is added to the constraint. When INEQ is 1 the constraint is
350 translated as an inequality, when INEQ is 0 it is translated as an
351 equality, when INEQ has another value, the first column of the
352 matrix is read for determining the type of the constraint. */
354 static ppl_Constraint_t
355 cloog_translate_constraint (CloogMatrix
*matrix
, int i
, int cst
, int ineq
)
358 ppl_Constraint_t res
;
359 ppl_Coefficient_t coef
;
360 ppl_Linear_Expression_t expr
;
361 ppl_dimension_type dim
= matrix
->NbColumns
- 2;
365 ppl_new_Coefficient (&coef
);
366 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
368 for (j
= 1; j
< matrix
->NbColumns
- 1; j
++)
370 ppl_assign_Coefficient_from_mpz_t (coef
, matrix
->p
[i
][j
]);
371 ppl_Linear_Expression_add_to_coefficient (expr
, j
- 1, coef
);
374 value_set_si (val
, cst
);
375 value_addto (val
, matrix
->p
[i
][matrix
->NbColumns
- 1], val
);
376 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
378 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
379 ppl_delete_Coefficient (coef
);
381 if (ineq
!= 0 && ineq
!= 1)
382 ineq
= !cloog_matrix_row_is_eq_p (matrix
, i
);
384 res
= cloog_build_ppl_cstr (expr
, ineq
);
385 ppl_delete_Linear_Expression (expr
);
389 /* Translates to PPL the opposite of row I from MATRIX. When INEQ is
390 1 the constraint is translated as an inequality, when INEQ is 0 it
391 is translated as an equality, when INEQ has another value, the
392 first column of the matrix is read for determining the type of the
395 static ppl_Constraint_t
396 cloog_translate_oppose_constraint (CloogMatrix
*matrix
, int i
, int cst
, int ineq
)
399 ppl_Constraint_t res
;
400 ppl_Coefficient_t coef
;
401 ppl_Linear_Expression_t expr
;
402 ppl_dimension_type dim
= matrix
->NbColumns
- 2;
407 ppl_new_Coefficient (&coef
);
408 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
410 for (j
= 1; j
< matrix
->NbColumns
- 1; j
++)
412 value_oppose (val
, matrix
->p
[i
][j
]);
413 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
414 ppl_Linear_Expression_add_to_coefficient (expr
, j
- 1, coef
);
417 value_oppose (val
, matrix
->p
[i
][matrix
->NbColumns
- 1]);
418 value_set_si (val1
, cst
);
419 value_addto (val
, val
, val1
);
420 ppl_assign_Coefficient_from_mpz_t (coef
, val
);
421 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
422 ppl_delete_Coefficient (coef
);
426 if (ineq
!= 0 && ineq
!= 1)
427 ineq
= !cloog_matrix_row_is_eq_p (matrix
, i
);
429 res
= cloog_build_ppl_cstr (expr
, ineq
);
430 ppl_delete_Linear_Expression (expr
);
434 /* Adds to PPL the constraints from MATRIX. */
437 cloog_translate_constraint_matrix_1 (ppl_Polyhedron_t ppl
, CloogMatrix
*matrix
)
441 for (i
= 0; i
< matrix
->NbRows
; i
++)
443 ppl_Constraint_t c
= cloog_translate_constraint (matrix
, i
, 0, -1);
444 ppl_Polyhedron_add_constraint (ppl
, c
);
445 ppl_delete_Constraint (c
);
449 static ppl_Polyhedron_t
450 cloog_translate_constraint_matrix (CloogMatrix
*matrix
)
452 ppl_Polyhedron_t ppl
;
453 ppl_dimension_type dim
= matrix
->NbColumns
- 2;
455 ppl_new_C_Polyhedron_from_space_dimension (&ppl
, dim
, 0);
456 cloog_translate_constraint_matrix_1 (ppl
, matrix
);
460 /* Put the constraint matrix of polyhedron RES under Cloog's normal
461 form: Cloog expects to see
471 These two forms are equivalent but the expected form uses rightmost
472 indices for inequalities. */
475 cloog_pol_normal_form (polyhedron res
)
477 int dim
= cloog_pol_dim (res
);
478 int nrows
= cloog_pol_nbc (res
);
480 int neqs
= cloog_pol_nbeq (res
);
482 for (j
= 1; j
<= dim
; j
++)
486 for (rank
= 0; rank
< neqs
; rank
++)
487 if (j
- 1 == cloog_first_non_zero (res
->Constraint
[rank
] + 1, dim
))
489 for (i
= neqs
; i
< nrows
; i
++)
490 if (value_notzero_p (res
->Constraint
[i
][j
]))
491 cloog_matrix_combine (res
->Constraint
[i
],
492 res
->Constraint
[rank
],
493 res
->Constraint
[i
], j
, dim
+ 1);
501 cloog_translate_ppl_polyhedron_1 (ppl_Polyhedron_t pol
)
504 ppl_dimension_type dim
;
505 ppl_const_Constraint_System_t pcs
;
506 ppl_Constraint_System_const_iterator_t cit
, end
;
507 int eqs
, orig_ineqs
, ineqs
, row
, i
;
508 ppl_const_Constraint_t pc
;
511 ppl_Polyhedron_get_minimized_constraints (pol
, &pcs
);
512 ppl_new_Constraint_System_const_iterator (&cit
);
513 ppl_new_Constraint_System_const_iterator (&end
);
515 for (eqs
= 0, ineqs
= 0,
516 ppl_Constraint_System_begin (pcs
, cit
),
517 ppl_Constraint_System_end (pcs
, end
);
518 !ppl_Constraint_System_const_iterator_equal_test (cit
, end
);
519 ppl_Constraint_System_const_iterator_increment (cit
))
521 ppl_Constraint_System_const_iterator_dereference (cit
, &pc
);
522 (ppl_Constraint_type (pc
) == PPL_CONSTRAINT_TYPE_EQUAL
) ? eqs
++ : ineqs
++;
525 ppl_Polyhedron_space_dimension (pol
, &dim
);
528 if (1 || orig_ineqs
== 0)
529 res
= cloog_new_pol (dim
, eqs
+ ineqs
+ 1);
531 res
= cloog_new_pol (dim
, eqs
+ ineqs
);
534 /* Sort constraints: Cloog expects to see in matrices the equalities
535 followed by inequalities. */
540 for (ppl_Constraint_System_begin (pcs
, cit
), ppl_Constraint_System_end (pcs
, end
);
541 !ppl_Constraint_System_const_iterator_equal_test (cit
, end
);
542 ppl_Constraint_System_const_iterator_increment (cit
))
544 ppl_Coefficient_t coef
;
545 ppl_dimension_type col
;
548 ppl_new_Coefficient (&coef
);
549 ppl_Constraint_System_const_iterator_dereference (cit
, &pc
);
551 neg
= (ppl_Constraint_type (pc
) == PPL_CONSTRAINT_TYPE_LESS_THAN
552 || ppl_Constraint_type (pc
) == PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
) ? 1 : 0;
553 row
= (ppl_Constraint_type (pc
) == PPL_CONSTRAINT_TYPE_EQUAL
) ? eqs
++ : ineqs
++;
555 for (col
= 0; col
< dim
; col
++)
557 ppl_Constraint_coefficient (pc
, col
, coef
);
558 ppl_Coefficient_to_mpz_t (coef
, val
);
561 value_oppose (val
, val
);
563 value_assign (res
->Constraint
[row
][col
+ 1], val
);
566 ppl_Constraint_inhomogeneous_term (pc
, coef
);
567 ppl_Coefficient_to_mpz_t (coef
, val
);
568 value_assign (res
->Constraint
[row
][dim
+ 1], val
);
569 ppl_delete_Coefficient (coef
);
571 switch (ppl_Constraint_type (pc
))
573 case PPL_CONSTRAINT_TYPE_EQUAL
:
574 value_set_si (res
->Constraint
[row
][0], 0);
577 case PPL_CONSTRAINT_TYPE_LESS_THAN
:
578 case PPL_CONSTRAINT_TYPE_GREATER_THAN
:
579 value_decrement (res
->Constraint
[row
][dim
+ 1],
580 res
->Constraint
[row
][dim
+ 1]);
581 value_set_si (res
->Constraint
[row
][0], 1);
584 case PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL
:
585 case PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL
:
586 value_set_si (res
->Constraint
[row
][0], 1);
590 fprintf (stderr
, "PPL_CONSTRAINT_TYPE_%d not implemented yet\n",
591 ppl_Constraint_type (pc
));
597 ppl_delete_Constraint_System_const_iterator (cit
);
598 ppl_delete_Constraint_System_const_iterator (end
);
600 if (cloog_pol_nbeq (res
) == 2 && cloog_pol_nbc (res
) == 2
601 && cloog_first_non_zero (res
->Constraint
[0], dim
+ 2) == (int) dim
+ 1)
603 cloog_pol_free (res
);
604 return cloog_empty_polyhedron (dim
);
607 /* Add the positivity constraint. */
608 if (1 || orig_ineqs
== 0)
611 value_set_si (res
->Constraint
[row
][0], 1);
612 for (i
= 0; i
< (int) dim
; i
++)
613 value_set_si (res
->Constraint
[row
][i
+ 1], 0);
614 value_set_si (res
->Constraint
[row
][dim
+ 1], 1);
617 /* Put the matrix of RES in normal form. */
618 cloog_pol_normal_form (res
);
620 /* If we do not sort the matrices, Cloog is a random loop
622 cloog_pol_sort_rows (res
);
628 cloog_pol_from_matrix (CloogMatrix
* m
)
631 int ncolumns
= cloog_matrix_ncolumns (m
);
632 int nrows
= cloog_matrix_nrows (m
);
636 return cloog_universe_polyhedron (ncolumns
- 2);
639 p
= cloog_translate_constraint_matrix (m
);
640 res
= cloog_translate_ppl_polyhedron_1 (p
);
641 ppl_delete_Polyhedron (p
);
642 if ((int) cloog_pol_nbc (res
) < cloog_matrix_nrows (m
))
645 cloog_pol_free (res
);
646 res
= cloog_new_pol (ncolumns
- 2, nrows
);
647 cloog_vector_copy (m
->p
[0], res
->Constraint
[0], m
->NbRows
* m
->NbColumns
);
653 cloog_domain_matrix2domain (CloogMatrix
* matrix
)
655 return cloog_domain_alloc (cloog_pol_from_matrix (matrix
));
659 cloog_translate_ppl_polyhedron (ppl_Polyhedron_t p
)
661 polyhedron res
= cloog_translate_ppl_polyhedron_1 (p
);
662 return cloog_domain_alloc (res
);
666 cloog_pol_print (FILE * file
, polyhedron pol
)
674 fprintf (file
, "<null polyhedron>\n");
678 dim
= cloog_pol_dim (pol
) + 2;
679 nbc
= cloog_pol_nbc (pol
);
680 fprintf (file
, "POLYHEDRON Dimension:%d\n", cloog_pol_dim (pol
));
682 " Constraints:%d Equations:%d\n",
683 cloog_pol_nbc (pol
), cloog_pol_nbeq (pol
));
684 fprintf (file
, "Constraints %d %d\n", nbc
, dim
);
686 for (i
= 0; i
< (int) nbc
; i
++)
688 p
= pol
->Constraint
[i
];
690 if (value_notzero_p (*p
))
691 fprintf (file
, "Inequality: [");
693 fprintf (file
, "Equality: [");
697 for (j
= 1; j
< (int) dim
; j
++)
698 value_print (file
, "%4s ", *p
++);
700 fprintf (file
, " ]\n");
704 void debug_poly (polyhedron p
)
706 cloog_pol_print (stderr
, p
);
710 debug_ppl_poly (ppl_Polyhedron_t p
)
712 debug_poly (cloog_domain_polyhedron (cloog_translate_ppl_polyhedron (p
)));
716 cloog_domain_references (CloogDomain
* d
)
718 return d
->_references
;
722 * cloog_domain_print function:
723 * This function prints the content of a CloogDomain structure (domain) into
724 * a file (foo, possibly stdout).
727 cloog_domain_print (FILE * foo
, CloogDomain
* domain
)
729 polyhedra_union upol
= cloog_domain_upol (domain
);
733 cloog_pol_print (foo
, cloog_upol_polyhedron (upol
));
734 upol
= cloog_upol_next (upol
);
737 fprintf (foo
, "Number of active references: %d\n",
738 cloog_domain_references (domain
));
742 * cloog_domain_free function:
743 * This function frees the allocated memory for a CloogDomain structure
744 * (domain). It decrements the number of active references to this structure,
745 * if there are no more references on the structure, it frees it (with the
746 * included list of polyhedra).
749 cloog_domain_free (CloogDomain
* domain
)
753 cloog_domain_set_references (domain
,
754 cloog_domain_references (domain
) - 1);
756 if (cloog_domain_references (domain
) == 0)
759 polyhedra_union upol
= cloog_domain_upol (domain
);
763 polyhedra_union next_upol
;
765 cloog_pol_free (cloog_upol_polyhedron (upol
));
766 next_upol
= cloog_upol_next (upol
);
767 cloog_upol_free (upol
);
778 * cloog_domain_copy function:
779 * This function returns a copy of a CloogDomain structure (domain). To save
780 * memory this is not a memory copy but we increment a counter of active
781 * references inside the structure, then return a pointer to that structure.
784 cloog_domain_copy (CloogDomain
* domain
)
786 cloog_domain_set_references (domain
, cloog_domain_references (domain
) + 1);
791 * cloog_domain_convex function:
792 * Given a polyhedral domain (polyhedron), this function concatenates the lists
793 * of rays and lines of the two (or more) polyhedra in the domain into one
794 * combined list, and find the set of constraints which tightly bound all of
795 * those objects. It returns the corresponding polyhedron.
798 cloog_domain_convex (CloogDomain
* domain
)
802 polyhedra_union upol
= cloog_domain_upol (domain
);
803 CloogMatrix
*m
= cloog_upol_domain2matrix (upol
);
804 ppl_Polyhedron_t p1
= cloog_translate_constraint_matrix (m
);
806 cloog_matrix_free (m
);
807 upol
= cloog_upol_next (upol
);
810 m
= cloog_upol_domain2matrix (upol
);
811 p2
= cloog_translate_constraint_matrix (m
);
812 cloog_matrix_free (m
);
813 ppl_Polyhedron_upper_bound_assign (p1
, p2
);
814 ppl_delete_Polyhedron (p2
);
816 upol
= cloog_upol_next (upol
);
819 res
= cloog_translate_ppl_polyhedron (p1
);
820 ppl_delete_Polyhedron (p1
);
826 cloog_domain_isconvex (CloogDomain
* domain
)
828 if (cloog_domain_polyhedron (domain
))
829 return !cloog_upol_next (cloog_domain_upol (domain
));
835 * cloog_domain_simple_convex:
836 * Given a list (union) of polyhedra, this function returns a "simple"
837 * convex hull of this union. In particular, the constraints of the
838 * the returned polyhedron consist of (parametric) lower and upper
839 * bounds on individual variables and constraints that appear in the
840 * original polyhedra.
842 * nb_par is the number of parameters of the domain.
845 cloog_domain_simple_convex (CloogDomain
* domain
, int nb_par
)
847 fprintf (stderr
, "cloog_domain_simple_convex (domain, nb_par = %d) is not implemented yet.\n", nb_par
);
848 fprintf (stderr
, "domain = \n");
849 cloog_domain_print (stderr
, domain
);
853 /* Returns non-zero when the constraint I in MATRIX is the positivity
854 constraint: "0 >= 0". */
857 cloog_positivity_constraint_p (CloogMatrix
*matrix
, int i
, int dim
)
861 for (j
= 1; j
< dim
; j
++)
862 if (value_notzero_p (matrix
->p
[i
][j
]))
868 /* Simplifies DOM1 in the context of DOM2. For example, DOM1 can
869 contain the following conditions: i >= 0, i <= 5, and DOM2 is a
870 loop around, i.e. the context of DOM1, that also contains the
871 conditions i >= 0, i <= 5. So instead of generating a loop like:
873 | for (i = 0; i < 6; i++)
875 | if (i >= 0 && i <= 5)
879 this function allows to detect that in the context of DOM2, the
880 constraints of DOM1 are redundant, and so the following code should
883 | for (i = 0; i < 6; i++)
887 #if USE_PPL_POWERSETS
890 cloog_domain_simplify (CloogDomain
* dom1
, CloogDomain
* dom2
)
897 CloogDomain
*res
= NULL
;
899 ppl_Pointset_Powerset_C_Polyhedron_t ps1
, ps2
;
900 ppl_dimension_type dim
= cloog_domain_dim(dom1
);
901 /* Translate dom1 into PPL powerset ps1. */
903 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension(&ps1
, dim
, 1);
905 for (u1
= cloog_domain_upol (dom1
); u1
; u1
= cloog_upol_next (u1
))
907 CloogMatrix
*m
= cloog_upol_domain2matrix (u1
);
908 ppl_const_Polyhedron_t ph
= cloog_translate_constraint_matrix (m
);
909 ppl_Pointset_Powerset_C_Polyhedron_add_disjunct(ps1
, ph
);
910 ppl_delete_Polyhedron(ph
);
911 cloog_matrix_free (m
);
915 /* Translate dom2 into PPL powerset ps2. */
917 ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension(&ps2
, dim
, 1);
919 for (u2
= cloog_domain_upol (dom2
); u2
; u2
= cloog_upol_next (u2
))
921 CloogMatrix
*m
= cloog_upol_domain2matrix (u2
);
922 ppl_Polyhedron_t ph
= cloog_translate_constraint_matrix (m
);
923 ppl_Pointset_Powerset_C_Polyhedron_add_disjunct(ps2
, ph
);
924 ppl_delete_Polyhedron(ph
);
925 cloog_matrix_free (m
);
929 ppl_Pointset_Powerset_C_Polyhedron_simplify_using_context_assign(ps1
, ps2
);
931 /* Translate back simplified ps1 into res. */
932 ppl_Pointset_Powerset_C_Polyhedron_const_iterator_t i
;
933 ppl_new_Pointset_Powerset_C_Polyhedron_const_iterator(&i
);
934 ppl_Pointset_Powerset_C_Polyhedron_const_iterator_t end
;
935 ppl_new_Pointset_Powerset_C_Polyhedron_const_iterator(&end
);
936 for (ppl_Pointset_Powerset_C_Polyhedron_const_iterator_begin(ps1
, i
),
937 ppl_Pointset_Powerset_C_Polyhedron_const_iterator_end(ps1
, end
);
938 !ppl_Pointset_Powerset_C_Polyhedron_const_iterator_equal_test(i
, end
);
939 ppl_Pointset_Powerset_C_Polyhedron_const_iterator_increment(i
))
941 ppl_const_Polyhedron_t ph
;
942 ppl_Pointset_Powerset_C_Polyhedron_const_iterator_dereference(i
, &ph
);
943 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (ph
));
946 /* Final clean-up. */
947 ppl_delete_Pointset_Powerset_C_Polyhedron_const_iterator(i
);
948 ppl_delete_Pointset_Powerset_C_Polyhedron_const_iterator(end
);
949 ppl_delete_Pointset_Powerset_C_Polyhedron(ps1
);
950 ppl_delete_Pointset_Powerset_C_Polyhedron(ps2
);
954 #else /* !USE_PPL_POWERSETS */
957 cloog_domain_simplify (CloogDomain
* dom1
, CloogDomain
* dom2
)
959 CloogDomain
*res
= NULL
;
960 polyhedra_union u1
, u2
;
961 CloogDomain
*inter
= cloog_domain_intersection (dom1
, dom2
);
963 for (u1
= cloog_domain_upol (inter
); u1
; u1
= cloog_upol_next (u1
))
965 CloogMatrix
*m1
= cloog_upol_domain2matrix (u1
);
966 ppl_Polyhedron_t p1
= cloog_translate_constraint_matrix (m1
);
968 cloog_matrix_free (m1
);
969 for (u2
= cloog_domain_upol (dom2
); u2
; u2
= cloog_upol_next (u2
))
971 CloogMatrix
*m2
= cloog_upol_domain2matrix (u2
);
972 ppl_Polyhedron_t p2
= cloog_translate_constraint_matrix (m2
);
974 cloog_matrix_free (m2
);
975 ppl_Polyhedron_simplify_using_context_assign (p1
, p2
);
976 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (p1
));
977 ppl_delete_Polyhedron (p2
);
984 #endif /* !USE_PPL_POWERSETS */
986 static polyhedra_union
987 cloog_upol_copy (polyhedra_union p
)
989 polyhedra_union res
= cloog_new_upol (cloog_pol_copy (cloog_upol_polyhedron (p
)));
990 polyhedra_union upol
= res
;
992 while (cloog_upol_next (p
))
994 cloog_upol_set_next (upol
, cloog_new_upol (cloog_pol_copy (cloog_upol_polyhedron (p
))));
995 upol
= cloog_upol_next (upol
);
996 p
= cloog_upol_next (p
);
1002 /* Adds to D1 the union of polyhedra from D2, with no checks of
1003 redundancies between polyhedra. */
1005 static CloogDomain
*
1006 cloog_domain_add_domain (CloogDomain
*d1
, CloogDomain
*d2
)
1008 polyhedra_union upol
;
1016 upol
= cloog_domain_upol (d1
);
1017 while (cloog_upol_next (upol
))
1018 upol
= cloog_upol_next (upol
);
1020 cloog_upol_set_next (upol
, cloog_domain_upol (d2
));
1025 * cloog_domain_union function:
1026 * This function returns a new CloogDomain structure including a polyhedral
1027 * domain which is the union of two polyhedral domains (pol1) U (pol2) inside
1028 * two CloogDomain structures.
1031 cloog_domain_union (CloogDomain
* dom1
, CloogDomain
* dom2
)
1034 polyhedra_union head1
, head2
, tail1
, tail2
;
1035 polyhedra_union d1
, d2
;
1043 if (cloog_domain_dim (dom1
) != cloog_domain_dim (dom2
))
1045 fprintf (stderr
, "cloog_domain_union should not be called on domains of different dimensions.\n");
1051 for (d1
= cloog_domain_upol (dom1
); d1
; d1
= cloog_upol_next (d1
))
1054 CloogMatrix
*m1
= cloog_upol_domain2matrix (d1
);
1055 ppl_Polyhedron_t ppl1
= cloog_translate_constraint_matrix (m1
);
1056 cloog_matrix_free (m1
);
1058 for (d2
= cloog_domain_upol (dom2
); d2
; d2
= cloog_upol_next (d2
))
1060 CloogMatrix
*m2
= cloog_upol_domain2matrix (d2
);
1061 ppl_Polyhedron_t ppl2
= cloog_translate_constraint_matrix (m2
);
1062 cloog_matrix_free (m2
);
1064 if (ppl_Polyhedron_contains_Polyhedron (ppl2
, ppl1
))
1066 ppl_delete_Polyhedron (ppl2
);
1070 ppl_delete_Polyhedron (ppl2
);
1072 ppl_delete_Polyhedron (ppl1
);
1078 head1
= cloog_upol_copy (d1
);
1083 cloog_upol_set_next (tail1
, cloog_upol_copy (d1
));
1084 tail1
= cloog_upol_next (tail1
);
1091 for (d2
= cloog_domain_upol (dom2
); d2
; d2
= cloog_upol_next (d2
))
1094 CloogMatrix
*m2
= cloog_upol_domain2matrix (d2
);
1095 ppl_Polyhedron_t ppl2
= cloog_translate_constraint_matrix (m2
);
1096 cloog_matrix_free (m2
);
1098 for (d1
= head1
; d1
; d1
= cloog_upol_next (d1
))
1100 CloogMatrix
*m1
= cloog_upol_domain2matrix (d1
);
1101 ppl_Polyhedron_t ppl1
= cloog_translate_constraint_matrix (m1
);
1102 cloog_matrix_free (m1
);
1104 if (ppl_Polyhedron_contains_Polyhedron (ppl1
, ppl2
))
1106 ppl_delete_Polyhedron (ppl1
);
1110 ppl_delete_Polyhedron (ppl1
);
1112 ppl_delete_Polyhedron (ppl2
);
1118 head2
= cloog_upol_copy (d2
);
1123 cloog_upol_set_next (tail2
, cloog_upol_copy (d2
));
1124 tail2
= cloog_upol_next (tail2
);
1130 res
= cloog_new_domain (head2
);
1133 cloog_upol_set_next (tail1
, head2
);
1134 res
= cloog_new_domain (head1
);
1137 return cloog_check_domain (res
);
1141 * cloog_domain_intersection function:
1142 * This function returns a new CloogDomain structure including a polyhedral
1143 * domain which is the intersection of two polyhedral domains (pol1)inter(pol2)
1144 * inside two CloogDomain structures.
1147 cloog_domain_intersection (CloogDomain
* dom1
, CloogDomain
* dom2
)
1149 CloogDomain
*res
= NULL
;
1150 polyhedra_union p1
, p2
;
1151 ppl_Polyhedron_t ppl1
, ppl2
;
1153 for (p1
= cloog_domain_upol (dom1
); p1
; p1
= cloog_upol_next (p1
))
1155 CloogMatrix
*m1
= cloog_upol_domain2matrix (p1
);
1156 ppl1
= cloog_translate_constraint_matrix (m1
);
1157 cloog_matrix_free (m1
);
1159 for (p2
= cloog_domain_upol (dom2
); p2
; p2
= cloog_upol_next (p2
))
1161 CloogMatrix
*m2
= cloog_upol_domain2matrix (p2
);
1162 ppl2
= cloog_translate_constraint_matrix (m2
);
1163 cloog_matrix_free (m2
);
1164 ppl_Polyhedron_intersection_assign (ppl2
, ppl1
);
1165 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (ppl2
));
1166 ppl_delete_Polyhedron (ppl2
);
1168 ppl_delete_Polyhedron (ppl1
);
1174 /* Returns d1 minus d2. */
1177 cloog_domain_difference (CloogDomain
* d1
, CloogDomain
* d2
)
1179 CloogDomain
*res
= NULL
, *d
= d1
;
1180 polyhedra_union p1
, p2
;
1182 if (cloog_domain_isempty (d2
))
1183 return cloog_domain_copy (d1
);
1185 for (p2
= cloog_domain_upol (d2
); p2
; p2
= cloog_upol_next (p2
))
1187 CloogMatrix
*m2
= cloog_upol_domain2matrix (p2
);
1189 for (p1
= cloog_domain_upol (d
); p1
; p1
= cloog_upol_next (p1
))
1192 CloogMatrix
*m1
= cloog_upol_domain2matrix (p1
);
1194 for (i
= 0; i
< m2
->NbRows
; i
++)
1196 ppl_Polyhedron_t p3
;
1197 ppl_Constraint_t cstr
;
1199 /* Don't handle "0 >= 0". */
1200 if (cloog_positivity_constraint_p (m2
, i
,
1201 cloog_domain_dim (d
) + 1))
1204 /* Add the constraint "-m2[i] - 1 >= 0". */
1205 p3
= cloog_translate_constraint_matrix (m1
);
1206 cstr
= cloog_translate_oppose_constraint (m2
, i
, -1, 1);
1207 ppl_Polyhedron_add_constraint (p3
, cstr
);
1208 ppl_delete_Constraint (cstr
);
1209 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (p3
));
1210 ppl_delete_Polyhedron (p3
);
1212 /* For an equality, add the constraint "m2[i] - 1 >= 0". */
1213 if (cloog_matrix_row_is_eq_p (m2
, i
))
1215 p3
= cloog_translate_constraint_matrix (m1
);
1216 cstr
= cloog_translate_constraint (m2
, i
, -1, 1);
1217 ppl_Polyhedron_add_constraint (p3
, cstr
);
1218 ppl_delete_Constraint (cstr
);
1219 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (p3
));
1220 ppl_delete_Polyhedron (p3
);
1223 cloog_matrix_free (m1
);
1227 cloog_matrix_free (m2
);
1231 res
= cloog_domain_empty (cloog_domain_dim (d2
));
1238 /* Compares P1 to P2: returns 0 when the polyhedra don't overlap,
1239 returns 1 when p1 >= p2, and returns -1 when p1 < p2. The ">"
1240 relation is the "contains" relation. */
1243 cloog_domain_polyhedron_compare (CloogMatrix
*m1
, CloogMatrix
*m2
, int level
, int nb_par
, int dimension
)
1246 ppl_Polyhedron_t q1
, q2
, q3
, q4
, q5
, q
;
1247 ppl_Polyhedron_t p1
, p2
;
1249 p1
= cloog_translate_constraint_matrix (m1
);
1250 if (ppl_Polyhedron_is_empty (p1
))
1252 ppl_delete_Polyhedron (p1
);
1256 p2
= cloog_translate_constraint_matrix (m2
);
1257 if (ppl_Polyhedron_is_empty (p2
))
1259 ppl_delete_Polyhedron (p2
);
1263 ppl_new_C_Polyhedron_from_C_Polyhedron (&q1
, p1
);
1264 ppl_new_C_Polyhedron_from_C_Polyhedron (&q2
, p2
);
1266 for (i
= level
; i
< dimension
- nb_par
+ 1; i
++)
1269 ppl_Coefficient_t d
;
1270 ppl_Linear_Expression_t expr
;
1274 value_set_si (val
, 1);
1275 ppl_new_Coefficient_from_mpz_t (&d
, val
);
1276 ppl_new_Linear_Expression_with_dimension (&expr
, dimension
);
1277 ppl_Linear_Expression_add_to_coefficient (expr
, i
- 1, d
);
1278 ppl_new_Generator (&g
, expr
, PPL_GENERATOR_TYPE_LINE
, d
);
1279 ppl_Polyhedron_add_generator (q1
, g
);
1280 ppl_Polyhedron_add_generator (q2
, g
);
1281 ppl_delete_Generator (g
);
1282 ppl_delete_Linear_Expression (expr
);
1283 ppl_delete_Coefficient (d
);
1286 ppl_new_C_Polyhedron_from_C_Polyhedron (&q
, q1
);
1287 ppl_Polyhedron_intersection_assign (q
, q2
);
1288 ppl_delete_Polyhedron (q1
);
1289 ppl_delete_Polyhedron (q2
);
1291 if (ppl_Polyhedron_is_empty (q
))
1293 ppl_delete_Polyhedron (p1
);
1294 ppl_delete_Polyhedron (p2
);
1295 ppl_delete_Polyhedron (q
);
1299 ppl_new_C_Polyhedron_from_C_Polyhedron (&q1
, p1
);
1300 ppl_new_C_Polyhedron_from_C_Polyhedron (&q2
, p2
);
1301 ppl_delete_Polyhedron (p1
);
1302 ppl_delete_Polyhedron (p2
);
1304 ppl_Polyhedron_intersection_assign (q1
, q
);
1305 ppl_Polyhedron_intersection_assign (q2
, q
);
1307 m1
= cloog_upol_domain2matrix (cloog_domain_upol (cloog_translate_ppl_polyhedron (q1
)));
1308 m2
= cloog_upol_domain2matrix (cloog_domain_upol (cloog_translate_ppl_polyhedron (q2
)));
1310 ppl_new_C_Polyhedron_from_C_Polyhedron (&q4
, q
);
1311 for (i
= 0; i
< m1
->NbRows
; i
++)
1312 if (value_one_p (m1
->p
[i
][0])
1313 && value_pos_p (m1
->p
[i
][level
]))
1315 ppl_Constraint_t c
= cloog_translate_constraint (m1
, i
, 0, 1);
1316 ppl_Polyhedron_add_constraint (q4
, c
);
1317 ppl_delete_Constraint (c
);
1320 for (i
= 0; i
< m2
->NbRows
; i
++)
1321 if (value_one_p (m2
->p
[i
][0])
1322 && value_neg_p (m2
->p
[i
][level
]))
1324 ppl_Constraint_t c
= cloog_translate_constraint (m2
, i
, 0, 1);
1325 ppl_Polyhedron_add_constraint (q4
, c
);
1326 ppl_delete_Constraint (c
);
1329 if (ppl_Polyhedron_is_empty (q4
))
1331 ppl_delete_Polyhedron (q
);
1332 ppl_delete_Polyhedron (q1
);
1333 ppl_delete_Polyhedron (q2
);
1334 ppl_delete_Polyhedron (q4
);
1338 ppl_delete_Polyhedron (q4
);
1339 ppl_new_C_Polyhedron_from_C_Polyhedron (&q3
, q
);
1340 for (i
= 0; i
< m1
->NbRows
; i
++)
1342 if (value_zero_p (m1
->p
[i
][0]))
1344 if (value_zero_p (m1
->p
[i
][level
]))
1347 else if (value_neg_p (m1
->p
[i
][level
]))
1349 ppl_Constraint_t c
= cloog_translate_oppose_constraint (m1
, i
, 0, 1);
1350 ppl_Polyhedron_add_constraint (q3
, c
);
1351 ppl_delete_Constraint (c
);
1356 ppl_Constraint_t c
= cloog_translate_constraint (m1
, i
, 0, 1);
1357 ppl_Polyhedron_add_constraint (q3
, c
);
1358 ppl_delete_Constraint (c
);
1362 else if (value_neg_p (m1
->p
[i
][level
]))
1364 ppl_Constraint_t c
= cloog_translate_oppose_constraint (m1
, i
, 0, 1);
1365 ppl_Polyhedron_add_constraint (q3
, c
);
1366 ppl_delete_Constraint (c
);
1372 ppl_new_C_Polyhedron_from_C_Polyhedron (&q5
, q3
);
1373 for (j
= 0; j
< m2
->NbRows
; j
++)
1375 if (value_zero_p (m2
->p
[j
][0]))
1377 if (value_zero_p (m2
->p
[j
][level
]))
1380 else if (value_pos_p (m2
->p
[j
][level
]))
1382 ppl_Constraint_t c
= cloog_translate_oppose_constraint (m2
, j
, 0, 1);
1383 ppl_Polyhedron_add_constraint (q5
, c
);
1384 ppl_delete_Constraint (c
);
1389 ppl_Constraint_t c
= cloog_translate_constraint (m2
, j
, 0, 1);
1390 ppl_Polyhedron_add_constraint (q5
, c
);
1391 ppl_delete_Constraint (c
);
1395 else if (value_pos_p (m2
->p
[j
][level
]))
1397 ppl_Constraint_t c
= cloog_translate_oppose_constraint (m2
, j
, 0, 1);
1398 ppl_Polyhedron_add_constraint (q5
, c
);
1399 ppl_delete_Constraint (c
);
1405 if (!ppl_Polyhedron_is_empty (q5
))
1407 ppl_delete_Polyhedron (q
);
1408 ppl_delete_Polyhedron (q1
);
1409 ppl_delete_Polyhedron (q2
);
1410 ppl_delete_Polyhedron (q3
);
1411 ppl_delete_Polyhedron (q5
);
1415 /* Reinitialize Q5. */
1416 ppl_delete_Polyhedron (q5
);
1417 ppl_new_C_Polyhedron_from_C_Polyhedron (&q5
, q3
);
1420 /* Reinitialize Q3. */
1421 ppl_delete_Polyhedron (q3
);
1422 ppl_new_C_Polyhedron_from_C_Polyhedron (&q3
, q
);
1425 cloog_matrix_free (m1
);
1426 cloog_matrix_free (m2
);
1427 ppl_delete_Polyhedron (q
);
1428 ppl_delete_Polyhedron (q1
);
1429 ppl_delete_Polyhedron (q2
);
1430 ppl_delete_Polyhedron (q3
);
1431 ppl_delete_Polyhedron (q5
);
1436 * cloog_domain_sort function:
1437 * This function topologically sorts (nb_pols) polyhedra. Here (pols) is a an
1438 * array of pointers to polyhedra, (nb_pols) is the number of polyhedra,
1439 * (level) is the level to consider for partial ordering (nb_par) is the
1440 * parameter space dimension, (permut) if not NULL, is an array of (nb_pols)
1441 * integers that contains a permutation specification after call in order to
1442 * apply the topological sorting.
1446 cloog_domain_sort (CloogDomain
**doms
, unsigned nb_pols
, unsigned level
,
1447 unsigned nb_par
, int *permut
)
1450 int dim
= cloog_domain_dim (doms
[0]);
1452 for (i
= 0; i
< (int) nb_pols
; i
++)
1455 /* Note that here we do a comparison per tuple of polyhedra.
1456 PolyLib does not do this, but instead it does fewer comparisons
1457 and with a complex reasoning they infer that it some comparisons
1458 are not useful. The result is that PolyLib has wrong permutations.
1460 FIXME: In the PolyLib backend, Cloog should use this algorithm
1461 instead of PolyhedronTSort, and cloog_domain_polyhedron_compare
1462 should be implemented with a simple call to PolyhedronLTQ: these
1463 two functions produce identical answers. */
1464 for (i
= 0; i
< (int) nb_pols
; i
++)
1465 for (j
= i
+ 1; j
< (int) nb_pols
; j
++)
1467 CloogMatrix
*m1
= cloog_upol_domain2matrix (cloog_domain_upol (doms
[i
]));
1468 CloogMatrix
*m2
= cloog_upol_domain2matrix (cloog_domain_upol (doms
[j
]));
1470 if (cloog_domain_polyhedron_compare (m1
, m2
, level
, nb_par
, dim
) == 1)
1473 permut
[i
] = permut
[j
];
1477 cloog_matrix_free (m1
);
1478 cloog_matrix_free (m2
);
1483 * cloog_domain_empty function:
1484 * This function allocates the memory space for a CloogDomain structure and
1485 * sets its polyhedron to an empty polyhedron with 'dimension' dimensions.
1486 * Then it returns a pointer to the allocated space.
1487 * - June 10th 2005: first version.
1490 cloog_domain_empty (int dimension
)
1492 return cloog_domain_alloc (cloog_empty_polyhedron (dimension
));
1496 /******************************************************************************
1497 * Structure display function *
1498 ******************************************************************************/
1502 * cloog_domain_print_structure :
1503 * this function is a more human-friendly way to display the CloogDomain data
1504 * structure, it only shows the constraint system and includes an indentation
1505 * level (level) in order to work with others print_structure functions.
1506 * Written by Olivier Chorier, Luc Marchaud, Pierre Martin and Romain Tartiere.
1507 * - April 24th 2005: Initial version.
1508 * - May 26th 2005: Memory leak hunt.
1509 * - June 16th 2005: (Ced) Integration in domain.c.
1512 cloog_domain_print_structure (FILE * file
, CloogDomain
* domain
, int level
)
1515 CloogMatrix
*matrix
;
1517 /* Go to the right level. */
1518 for (i
= 0; i
< level
; i
++)
1519 fprintf (file
, "|\t");
1523 fprintf (file
, "+-- CloogDomain\n");
1525 /* Print the matrix. */
1526 matrix
= cloog_upol_domain2matrix (cloog_domain_upol (domain
));
1527 cloog_matrix_print_structure (file
, matrix
, level
);
1528 cloog_matrix_free (matrix
);
1531 for (i
= 0; i
< level
+ 1; i
++)
1532 fprintf (file
, "|\t");
1533 fprintf (file
, "\n");
1536 fprintf (file
, "+-- Null CloogDomain\n");
1542 * cloog_domain_list_print function:
1543 * This function prints the content of a CloogDomainList structure into a
1544 * file (foo, possibly stdout).
1545 * - November 6th 2001: first version.
1548 cloog_domain_list_print (FILE * foo
, CloogDomainList
* list
)
1550 while (list
!= NULL
)
1552 cloog_domain_print (foo
, cloog_domain (list
));
1553 list
= cloog_next_domain (list
);
1558 /******************************************************************************
1559 * Memory deallocation function *
1560 ******************************************************************************/
1564 * cloog_domain_list_free function:
1565 * This function frees the allocated memory for a CloogDomainList structure.
1566 * - November 6th 2001: first version.
1569 cloog_domain_list_free (CloogDomainList
* list
)
1571 CloogDomainList
*temp
;
1573 while (list
!= NULL
)
1575 temp
= cloog_next_domain (list
);
1576 cloog_domain_free (cloog_domain (list
));
1583 /******************************************************************************
1584 * Reading function *
1585 ******************************************************************************/
1589 * cloog_domain_read function:
1590 * Adaptation from the PolyLib. This function reads a matrix into a file (foo,
1591 * posibly stdin) and returns a pointer to a polyhedron containing the read
1593 * - October 18th 2001: first version.
1596 cloog_domain_read (FILE * foo
)
1598 CloogMatrix
*matrix
;
1599 CloogDomain
*domain
;
1601 matrix
= cloog_matrix_read (foo
);
1602 domain
= cloog_domain_matrix2domain (matrix
);
1603 cloog_matrix_free (matrix
);
1610 * cloog_domain_union_read function:
1611 * This function reads a union of polyhedra into a file (foo, posibly stdin) and
1612 * returns a pointer to a Polyhedron containing the read information.
1613 * - September 9th 2002: first version.
1614 * - October 29th 2005: (debug) removal of a leak counting "correction" that
1615 * was just false since ages.
1618 cloog_domain_union_read (FILE * foo
)
1620 int i
, nb_components
;
1622 CloogDomain
*domain
, *temp
, *old
;
1624 /* domain reading: nb_components (constraint matrices). */
1625 while (fgets (s
, MAX_STRING
, foo
) == 0);
1626 while ((*s
== '#' || *s
== '\n') || (sscanf (s
, " %d", &nb_components
) < 1))
1627 fgets (s
, MAX_STRING
, foo
);
1629 if (nb_components
> 0)
1630 { /* 1. first part of the polyhedra union, */
1631 domain
= cloog_domain_read (foo
);
1632 /* 2. and the nexts. */
1633 for (i
= 1; i
< nb_components
; i
++)
1634 { /* Leak counting is OK since next allocated domain is freed here. */
1635 temp
= cloog_domain_read (foo
);
1637 domain
= cloog_domain_union (temp
, old
);
1638 cloog_domain_free (temp
);
1639 cloog_domain_free (old
);
1641 return cloog_check_domain (domain
);
1649 * cloog_domain_list_read function:
1650 * This function reads a list of polyhedra into a file (foo, posibly stdin) and
1651 * returns a pointer to a CloogDomainList containing the read information.
1652 * - November 6th 2001: first version.
1655 cloog_domain_list_read (FILE * foo
)
1659 CloogDomainList
*list
, *now
, *next
;
1662 /* We read first the number of polyhedra in the list. */
1663 while (fgets (s
, MAX_STRING
, foo
) == 0);
1664 while ((*s
== '#' || *s
== '\n') || (sscanf (s
, " %d", &nb_pols
) < 1))
1665 fgets (s
, MAX_STRING
, foo
);
1667 /* Then we read the polyhedra. */
1671 list
= (CloogDomainList
*) malloc (sizeof (CloogDomainList
));
1672 cloog_set_domain (list
, cloog_domain_read (foo
));
1673 cloog_set_next_domain (list
, NULL
);
1675 for (i
= 1; i
< nb_pols
; i
++)
1677 next
= (CloogDomainList
*) malloc (sizeof (CloogDomainList
));
1678 cloog_set_domain (next
, cloog_domain_read (foo
));
1679 cloog_set_next_domain (next
, NULL
);
1680 cloog_set_next_domain (now
, next
);
1681 now
= cloog_next_domain (now
);
1688 /******************************************************************************
1689 * Processing functions *
1690 ******************************************************************************/
1693 * cloog_domain_isempty function:
1694 * This function returns 1 if the polyhedron given as input is empty, 0
1696 * - October 28th 2001: first version.
1699 cloog_domain_isempty (CloogDomain
* domain
)
1701 if (cloog_domain_polyhedron (domain
) == NULL
)
1704 if (cloog_upol_next (cloog_domain_upol (domain
)))
1707 return (cloog_domain_dim (domain
) < cloog_domain_nbeq (domain
)) ? 1 : 0;
1711 * cloog_domain_project function:
1712 * From Quillere's LoopGen 0.4. This function returns the projection of
1713 * (domain) on the (level) first dimensions (i.e. outer loops). It returns a
1714 * pointer to the projected Polyhedron.
1715 * - nb_par is the number of parameters.
1717 * - October 27th 2001: first version.
1718 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1722 cloog_domain_project (CloogDomain
* domain
, int level
, int nb_par
)
1724 CloogDomain
*res
= NULL
;
1725 polyhedra_union upol
= cloog_domain_upol (domain
);
1726 int i
, diff
= cloog_domain_dim (domain
) - level
- nb_par
;
1728 ppl_dimension_type
*to_remove
;
1732 fprintf (stderr
, "cloog_domain_project should not be called with"
1733 "cloog_domain_dim (domain) < level + nb_par");
1738 return cloog_domain_copy (domain
);
1741 to_remove
= (ppl_dimension_type
*) malloc (n
* sizeof (ppl_dimension_type
));
1743 for (i
= 0; i
< n
; i
++)
1744 to_remove
[i
] = i
+ level
;
1748 CloogMatrix
*m1
= cloog_upol_domain2matrix (upol
);
1749 ppl_Polyhedron_t ppl
= cloog_translate_constraint_matrix (m1
);
1750 cloog_matrix_free (m1
);
1752 ppl_Polyhedron_remove_space_dimensions (ppl
, to_remove
, n
);
1753 res
= cloog_domain_add_domain (res
, cloog_translate_ppl_polyhedron (ppl
));
1754 ppl_delete_Polyhedron (ppl
);
1755 upol
= cloog_upol_next (upol
);
1763 * cloog_domain_extend function:
1764 * From Quillere's LoopGen 0.4. This function returns the (domain) given as
1765 * input with (dim)+(nb_par) dimensions. The new dimensions are added before
1766 * the (nb_par) parameters. This function does not free (domain), and returns
1768 * - nb_par is the number of parameters.
1770 * - October 27th 2001: first version.
1771 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1775 cloog_domain_extend (CloogDomain
* domain
, int dim
, int nb_par
)
1777 CloogDomain
*res
= NULL
;
1778 polyhedra_union upol
= cloog_domain_upol (domain
);
1779 int i
, k
, n
, diff
= dim
+ nb_par
- cloog_domain_dim (domain
);
1780 ppl_dimension_type
*map
;
1781 ppl_dimension_type to_add
= diff
;
1784 return cloog_domain_copy (domain
);
1787 map
= (ppl_dimension_type
*) malloc (n
* sizeof (ppl_dimension_type
));
1789 k
= cloog_domain_dim (domain
) - nb_par
;
1790 for (i
= 0; i
< k
; i
++)
1799 map
[i
] = i
- nb_par
;
1803 CloogMatrix
*mat
= cloog_upol_domain2matrix (upol
);
1804 ppl_Polyhedron_t ppl
= cloog_translate_constraint_matrix (mat
);
1805 cloog_matrix_free (mat
);
1807 ppl_Polyhedron_add_space_dimensions_and_embed (ppl
, to_add
);
1808 ppl_Polyhedron_map_space_dimensions (ppl
, map
, n
);
1809 res
= cloog_domain_add_domain (res
, cloog_translate_ppl_polyhedron (ppl
));
1810 ppl_delete_Polyhedron (ppl
);
1811 upol
= cloog_upol_next (upol
);
1819 * cloog_domain_never_integral function:
1820 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0. This
1821 * function returns a boolean set to 1 if there is this kind of 'never true'
1822 * constraint inside a polyhedron, 0 otherwise.
1823 * - domain is the polyhedron to check,
1825 * - November 28th 2001: first version.
1826 * - June 26th 2003: for iterators, more 'never true' constraints are found
1827 * (compare cholesky2 and vivien with a previous version),
1828 * checking for the parameters created (compare using vivien).
1829 * - June 28th 2003: Previously in loop.c and called
1830 * cloog_loop_simplify_nevertrue, now here !
1831 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1833 * - October 14th 2005: Complete rewriting, not faster but code quite shorter.
1836 cloog_domain_never_integral (CloogDomain
* domain
)
1838 int i
, dimension
, nbc
;
1842 if ((domain
== NULL
) || (cloog_domain_polyhedron (domain
) == NULL
))
1846 value_init_c (modulo
);
1847 p
= cloog_domain_polyhedron (domain
);
1848 dimension
= cloog_domain_dim (domain
) + 2;
1849 nbc
= cloog_domain_nbconstraints (domain
);
1851 /* For each constraint... */
1852 for (i
= 0; i
< nbc
; i
++)
1853 { /* If we have an equality and the scalar part is not zero... */
1854 if (value_zero_p (p
->Constraint
[i
][0]) &&
1855 value_notzero_p (p
->Constraint
[i
][dimension
- 1]))
1856 { /* Then we check whether the scalar can be divided by the gcd of the
1857 * unknown vector (including iterators and parameters) or not. If not,
1858 * there is no integer point in the polyhedron and we return 1.
1860 cloog_vector_gcd (&(p
->Constraint
[i
][1]), dimension
- 2, &gcd
);
1861 value_modulus (modulo
,
1862 p
->Constraint
[i
][dimension
- 1],
1865 if (value_notzero_p (modulo
))
1867 value_clear_c (gcd
);
1868 value_clear_c (modulo
);
1874 value_clear_c (gcd
);
1875 value_clear_c (modulo
);
1880 cloog_vector_matrix_smallest_column (Value
* a
, int n
, int p
, int q
)
1882 int res
, numero
= 0, k
, allzero
;
1888 c
= a
+ q
- 1 + p
* (n
- 1);
1890 value_absolute (comp
, *c
);
1892 for (k
= n
; k
> q
; k
--, c
-= p
, value_absolute (comp
, *c
))
1894 if (value_notzero_p (comp
))
1898 value_assign (minus
, comp
);
1902 else if (value_ge (minus
, comp
))
1904 value_assign (minus
, comp
);
1914 value_absolute (comp
, *c
);
1915 if ((value_notzero_p (comp
)) && (value_ge (minus
, comp
)))
1921 value_clear (minus
);
1928 cloog_vector_matrix_swap_rows (Value
* a
, int i
, int j
, int p
)
1931 Value
*c1
= a
+ (i
- 1) * p
;
1932 Value
*c2
= a
+ (j
- 1) * p
;
1937 for (k
= 1; k
<= p
; k
++)
1939 value_assign (s
, *c1
);
1940 value_assign (*c1
, *c2
);
1941 value_assign (*c2
, s
);
1950 cloog_vector_matrix_swap_columns (Value
* a
, int i
, int j
, int n
, int p
)
1960 for (k
= 1; k
<= n
; k
++)
1962 value_assign (s
, *c1
);
1963 value_assign (*c1
, *c2
);
1964 value_assign (*c2
, s
);
1973 cloog_vector_matrix_oppose_line (Value
* a
, int i
, int p
)
1976 Value
*c
= a
+ (i
- 1) * p
;
1978 for (k
= 1; k
<= p
; k
++, c
++)
1979 value_oppose (*c
, *c
);
1983 cloog_vector_matrix_oppose_column (Value
* a
, int i
, int n
, int p
)
1986 Value
*c
= a
+ (i
- 1);
1988 for (k
= 1; k
<= n
; k
++, c
+= p
)
1989 value_oppose (*c
, *c
);
1993 cloog_vector_matrix_combine_line (Value
* a
, int i
, int j
,
1997 Value
*c1
= a
+ (i
- 1) * p
;
1998 Value
*c2
= a
+ (j
- 1) * p
;
2000 for (k
= 1; k
<= p
; k
++, c1
++, c2
++)
2001 value_addmul (*c1
, x
, *c2
);
2005 cloog_vector_matrix_combine_column (Value
* a
, int i
, int j
, Value x
, int n
, int p
)
2008 Value
*c1
= a
+ (i
- 1);
2009 Value
*c2
= a
+ (j
- 1);
2011 for (k
= 1; k
<= n
; k
++, c1
= c1
+ p
, c2
= c2
+ p
)
2012 value_addmul (*c1
, x
, *c2
);
2016 cloog_matrix_hermite_combine (Value
*a
, Value
*b
, Value c
, Value
*d
, int k
, int n
,
2017 int p
, int q
, Value pivot
, Value x
, Value x_inv
)
2022 value_division (x
, c
, pivot
);
2023 value_modulus (tmp
, c
, pivot
);
2025 if (value_neg_p (tmp
))
2026 value_decrement (x
, x
);
2030 value_oppose (x_inv
, x
);
2031 cloog_vector_matrix_combine_line (a
, k
, q
, x_inv
, p
);
2032 cloog_vector_matrix_combine_column (b
, q
, k
, x
, n
, n
);
2033 cloog_vector_matrix_combine_line (d
, k
, q
, x_inv
, n
);
2037 cloog_matrix_hermite_oppose (Value
*a
, Value
*b
, Value
*d
, int n
, int p
, int q
, Value pivot
)
2039 cloog_vector_matrix_oppose_line (a
, q
, p
);
2040 cloog_vector_matrix_oppose_line (d
, q
, n
);
2041 cloog_vector_matrix_oppose_column (b
, q
, n
, n
);
2042 value_oppose (pivot
, pivot
);
2046 cloog_matrix_hermite_1 (Value
* a
, Value
* b
, Value
* d
, int n
, int p
, int q
)
2049 Value x
, pivot
, x_inv
;
2059 for (i
= cloog_vector_matrix_smallest_column (a
, n
, p
, q
); i
!= 0;
2060 i
= cloog_vector_matrix_smallest_column (a
, n
, p
, q
))
2064 cloog_vector_matrix_swap_rows (a
, i
, q
, p
);
2065 cloog_vector_matrix_swap_columns (b
, i
, q
, n
, n
);
2066 cloog_vector_matrix_swap_rows (d
, i
, q
, n
);
2069 c
= a
+ (q
- 1) * (p
+ 1);
2070 value_assign (pivot
, *c
);
2071 if (value_neg_p (pivot
))
2072 cloog_matrix_hermite_oppose (a
, b
, d
, n
, p
, q
, pivot
);
2074 for (c
+= p
, k
= q
+ 1; k
<= n
; k
++, c
+= p
)
2075 if (value_notzero_p (*c
))
2076 cloog_matrix_hermite_combine (a
, b
, *c
, d
, k
, n
, p
, q
, pivot
, x
, x_inv
);
2080 value_assign (pivot
, *(c
+ (q
- 1) * p
));
2081 if (value_neg_p (pivot
))
2082 cloog_matrix_hermite_oppose (a
, b
, d
, n
, p
, q
, pivot
);
2084 if (value_notzero_p (pivot
))
2085 for (k
= 1; k
< q
; k
++, c
+= p
)
2086 if (value_notzero_p (*c
))
2087 cloog_matrix_hermite_combine (a
, b
, *c
, d
, k
, n
, p
, q
, pivot
, x
, x_inv
);
2089 cloog_matrix_hermite_1 (a
, b
, d
, n
, p
, q
+ 1);
2091 value_clear (pivot
);
2093 value_clear (x_inv
);
2097 static CloogMatrix
*
2098 cloog_matrix_add_null_row (CloogMatrix
* M
)
2101 CloogMatrix
*res
= cloog_matrix_alloc (M
->NbRows
+ 1, M
->NbColumns
);
2103 for (i
= 0; i
< M
->NbRows
; i
++)
2104 for (j
= 0; j
< M
->NbColumns
; j
++)
2105 value_assign (res
->p
[i
][j
], M
->p
[i
][j
]);
2107 for (j
= 0; j
< M
->NbColumns
; j
++)
2108 value_set_si (res
->p
[i
][j
], 0);
2113 static CloogMatrix
*
2114 cloog_matrix_transpose (CloogMatrix
* m
)
2117 CloogMatrix
*res
= cloog_matrix_alloc (m
->NbColumns
, m
->NbRows
);
2119 for (i
= 0; i
< (int) m
->NbRows
; i
++)
2120 for (j
= 0; j
< (int) m
->NbColumns
; j
++)
2121 value_assign (res
->p
[j
][i
], m
->p
[i
][j
]);
2127 cloog_vector_matrix_vectorify (CloogMatrix
* A
)
2130 Value
*res
= (Value
*) malloc (sizeof (Value
) * A
->NbRows
* A
->NbColumns
);
2132 for (i
= 0; i
< A
->NbRows
* A
->NbColumns
; i
++)
2133 value_init (res
[i
]);
2135 for (i
= 0; i
< A
->NbRows
; i
++)
2136 for (j
= 0; j
< A
->NbColumns
; j
++)
2137 value_assign (res
[i
* A
->NbColumns
+ j
], A
->p
[i
][j
]);
2142 static CloogMatrix
*
2143 cloog_vector_matrix_matrixify (Value
* A
, int NbRows
, int NbCols
)
2146 CloogMatrix
*res
= cloog_matrix_alloc (NbRows
, NbCols
);
2148 for (i
= 0; i
< NbRows
; i
++)
2149 for (j
= 0; j
< NbCols
; j
++)
2150 value_assign (res
->p
[i
][j
], A
[i
* NbCols
+ j
]);
2156 cloog_vector_matrix_identity (int n
)
2159 Value
*res
= (Value
*) malloc (sizeof (Value
) * n
* n
);
2162 for (i
= 0; i
< n
* n
; i
++)
2163 value_init (res
[i
]);
2165 for (i
= 1; i
<= n
; i
++)
2166 for (j
= 1; j
<= n
; j
++, ptr
++)
2168 value_set_si (*ptr
, 1);
2170 value_set_si (*ptr
, 0);
2176 cloog_matrix_hermite (CloogMatrix
* a
, CloogMatrix
** H
, CloogMatrix
** U
)
2179 CloogMatrix
*tu
, *transpose
= cloog_matrix_transpose (a
);
2180 Value
*va
= cloog_vector_matrix_vectorify (transpose
);
2181 Value
*vid
= cloog_vector_matrix_identity (a
->NbColumns
);
2182 Value
*vid_inv
= cloog_vector_matrix_identity (a
->NbColumns
);
2184 cloog_matrix_free (transpose
);
2186 cloog_matrix_hermite_1 (va
, vid
, vid_inv
,
2187 a
->NbColumns
, a
->NbRows
, 1);
2189 transpose
= cloog_vector_matrix_matrixify (va
, a
->NbColumns
, a
->NbRows
);
2190 H
[0] = cloog_matrix_transpose (transpose
);
2191 cloog_matrix_free (transpose
);
2193 tu
= cloog_vector_matrix_matrixify (vid
, a
->NbColumns
, a
->NbColumns
);
2194 U
[0] = cloog_matrix_transpose (tu
);
2195 cloog_matrix_free (tu
);
2197 for (i
= 0; i
< a
->NbRows
* a
->NbColumns
; i
++)
2198 value_clear (va
[i
]);
2200 for (i
= 0; i
< a
->NbColumns
* a
->NbColumns
; i
++)
2201 value_clear (vid
[i
]);
2203 for (i
= 0; i
< a
->NbColumns
* a
->NbColumns
; i
++)
2204 value_clear (vid_inv
[i
]);
2212 cloog_exchange_rows (CloogMatrix
* m
, int row1
, int row2
)
2216 for (i
= 0; i
< (int) m
->NbColumns
; i
++)
2217 value_swap (m
->p
[row1
][i
], m
->p
[row2
][i
]);
2220 static CloogMatrix
*
2221 cloog_dio_copy_submatrix (CloogMatrix
* matrix
)
2224 CloogMatrix
* copy
= cloog_matrix_alloc (matrix
->NbRows
- 1, matrix
->NbColumns
- 1) ;
2226 for (i
= 0; i
< copy
->NbRows
; i
++)
2227 for (j
= 0; j
< copy
->NbColumns
; j
++)
2228 value_assign(copy
->p
[i
][j
], matrix
->p
[i
][j
]) ;
2234 cloog_dio_rearrange_redundant_rows (CloogMatrix
* M
)
2236 int i
, end
, row
, rank
= 1;
2237 CloogMatrix
*A
, *L
, *H
, *U
;
2239 L
= cloog_dio_copy_submatrix (M
);
2243 A
= cloog_matrix_alloc (1, L
->NbColumns
);
2244 for (i
= 0; i
< L
->NbColumns
; i
++)
2245 value_assign (A
->p
[0][i
], L
->p
[0][i
]);
2247 end
= L
->NbRows
- 1;
2253 CloogMatrix
*temp
= cloog_matrix_add_null_row (A
);
2255 for (i
= 0; i
< A
->NbColumns
; i
++)
2256 value_assign (temp
->p
[row
][i
], L
->p
[row
][i
]);
2258 cloog_matrix_hermite (temp
, &H
, &U
);
2259 cloog_matrix_free (U
);
2262 for (i
= 0; i
< n
; i
++)
2263 if (value_zero_p (H
->p
[i
][i
]))
2266 cloog_matrix_free (H
);
2270 /* This is a redundant row: put it at the end. */
2271 cloog_exchange_rows (M
, row
, end
);
2278 cloog_matrix_free (A
);
2279 A
= cloog_matrix_copy (temp
);
2280 cloog_matrix_free (temp
);
2283 if (rank
== (end
>= L
->NbColumns
? L
->NbColumns
: end
)
2288 cloog_matrix_free (A
);
2291 cloog_matrix_free (L
);
2296 cloog_matrix_inverse_pivot (CloogMatrix
*m
, int low
, int up
, int i
, int j
,
2297 Value m1
, Value m2
, Value x
, Value piv
)
2301 for (c
= low
; c
< up
; ++c
)
2303 value_multiply (m1
, piv
, m
->p
[j
][c
]);
2304 value_multiply (m2
, x
, m
->p
[i
][c
]);
2305 value_subtract (m
->p
[j
][c
], m1
, m2
);
2310 cloog_matrix_inverse_den (CloogMatrix
*Mat
, CloogMatrix
*MatInv
, int k
, Value
*x
)
2314 Value
*res
= (Value
*) malloc (k
* sizeof (Value
));
2319 value_set_si (*x
, 1);
2321 for (j
= 0; j
< cloog_matrix_nrows (Mat
); ++j
)
2323 value_init (res
[j
]);
2324 value_assign (res
[j
], Mat
->p
[j
][j
]);
2325 cloog_vector_gcd (&MatInv
->p
[j
][0], k
, &gcd
);
2326 Gcd (gcd
, res
[j
], &gcd
);
2328 if (value_neg_p (res
[j
]))
2329 value_oppose (gcd
, gcd
);
2331 if (value_notone_p (gcd
))
2333 for (c
= 0; c
< k
; c
++)
2334 value_division (MatInv
->p
[j
][c
], MatInv
->p
[j
][c
], gcd
);
2335 value_division (res
[j
], res
[j
], gcd
);
2338 Gcd (*x
, res
[j
], &gcd
);
2339 value_division (m1
, res
[j
], gcd
);
2340 value_multiply (*x
, *x
, m1
);
2349 cloog_matrix_inverse_div (CloogMatrix
*MatInv
, Value
*den
, Value m1
, Value x
)
2353 if (value_notone_p (x
))
2354 for (j
= 0; j
< MatInv
->NbRows
; ++j
)
2356 for (c
= 0; c
< MatInv
->NbColumns
; c
++)
2358 value_division (m1
, x
, den
[j
]);
2359 value_multiply (MatInv
->p
[j
][c
], MatInv
->p
[j
][c
], m1
);
2365 cloog_matrix_inverse_triang (CloogMatrix
*Mat
, CloogMatrix
*MatInv
, Value
*m1
, Value
*m2
)
2375 for (i
= 0; i
< cloog_matrix_ncolumns (Mat
); ++i
)
2377 if (value_zero_p (Mat
->p
[i
][i
]))
2379 for (j
= i
; j
< cloog_matrix_nrows (Mat
); ++j
)
2380 if (value_notzero_p (Mat
->p
[j
][i
]))
2383 if (j
== cloog_matrix_nrows (Mat
))
2386 cloog_matrix_exchange_rows (Mat
, i
, j
);
2387 cloog_matrix_exchange_rows (MatInv
, i
, j
);
2390 for (j
= 0; j
< cloog_matrix_nrows (Mat
) ; ++j
)
2393 || !value_notzero_p (Mat
->p
[j
][i
]))
2396 value_assign (x
, Mat
->p
[j
][i
]);
2397 value_assign (piv
, Mat
->p
[i
][i
]);
2399 if (value_notone_p (gcd
))
2401 value_division (x
, x
, gcd
);
2402 value_division (piv
, piv
, gcd
);
2405 cloog_matrix_inverse_pivot (Mat
, ((j
> i
) ? i
: 0),
2406 cloog_matrix_nrows (Mat
),
2407 i
, j
, *m1
, *m2
, x
, piv
);
2408 cloog_matrix_inverse_pivot (MatInv
, 0, cloog_matrix_nrows (Mat
),
2409 i
, j
, *m1
, *m2
, x
, piv
);
2411 cloog_vector_gcd (&MatInv
->p
[j
][0], (unsigned) cloog_matrix_nrows (Mat
), m1
);
2412 cloog_vector_gcd (&Mat
->p
[j
][0], (unsigned) cloog_matrix_nrows (Mat
), m2
);
2413 Gcd (*m1
, *m2
, &gcd
);
2414 if (value_notone_p (gcd
))
2418 for (c
= 0; c
< cloog_matrix_nrows (Mat
); ++c
)
2420 value_division (Mat
->p
[j
][c
], Mat
->p
[j
][c
], gcd
);
2421 value_division (MatInv
->p
[j
][c
], MatInv
->p
[j
][c
], gcd
);
2437 cloog_matrix_inverse (CloogMatrix
* Mat
, CloogMatrix
* MatInv
)
2445 if (Mat
->NbRows
!= Mat
->NbColumns
)
2452 cloog_vector_set (MatInv
->p
[0], 0, cloog_matrix_nrows (Mat
) * cloog_matrix_nrows (Mat
));
2454 for (i
= 0; i
< cloog_matrix_nrows (Mat
); ++i
)
2455 value_set_si (MatInv
->p
[i
][i
], 1);
2457 if (!cloog_matrix_inverse_triang (Mat
, MatInv
, &m1
, &m2
))
2460 den
= cloog_matrix_inverse_den (Mat
, MatInv
, cloog_matrix_nrows (Mat
), &x
);
2461 cloog_matrix_inverse_div (MatInv
, den
, m1
, x
);
2465 for (j
= 0; j
< cloog_matrix_nrows (Mat
); ++j
)
2466 value_clear (den
[j
]);
2478 cloog_dio_copy (CloogMatrix
*m1
, CloogMatrix
*m2
)
2481 int n
= m2
->NbRows
- 1;
2482 int m
= m2
->NbColumns
- 1;
2484 for (i
= 0; i
< n
; i
++)
2485 for (j
= 0; j
< m
; j
++)
2486 value_assign (m1
->p
[i
][j
], m2
->p
[i
][j
]);
2490 cloog_dio_negate_coeffs (CloogMatrix
*m
)
2493 int n
= m
->NbRows
- 1;
2494 int k
= m
->NbColumns
- 1;
2495 Value
*res
= (Value
*) malloc (sizeof (Value
) * (n
));
2497 for (i
= 0; i
< n
; i
++)
2499 value_init (res
[i
]);
2500 value_oppose (res
[i
], m
->p
[i
][k
]);
2507 cloog_dio_get_first_diagonal_zero (CloogMatrix
*m
)
2509 int i
, n
= m
->NbRows
<= m
->NbColumns
? m
->NbRows
: m
->NbColumns
;
2512 for (i
= 0; i
< n
; i
++)
2513 if (value_notzero_p (m
->p
[i
][i
]))
2522 cloog_dio_reduce_diagonal (CloogMatrix
*m
, Value
*coeffs
, int nbc
, int rank
)
2525 Value
*res
= (Value
*) malloc (sizeof (Value
) * nbc
);
2531 for (i
= 0; i
< nbc
; i
++)
2532 value_init (res
[i
]);
2534 for (i
= 0; i
< rank
; i
++)
2536 value_set_si (sum
, 0);
2537 for (j
= 0; j
< i
; j
++)
2538 value_addmul (sum
, res
[j
], m
->p
[i
][j
]);
2540 value_subtract (tmp
, coeffs
[i
], sum
);
2541 value_modulus (tmp
, tmp
, m
->p
[i
][i
]);
2542 if (value_notzero_p (tmp
))
2544 for (i
= 0; i
< nbc
; i
++)
2545 value_clear (res
[i
]);
2554 value_subtract (tmp
, coeffs
[i
], sum
);
2555 value_division (res
[i
], tmp
, m
->p
[i
][i
]);
2558 for (i
= rank
; i
< m
->NbColumns
; i
++)
2559 value_set_si (res
[i
], 0);
2568 cloog_dio_check_coeffs (CloogMatrix
*m
, Value
*T
, Value
*coeffs
, int nbr
, int nbc
, int rank
)
2577 for (i
= rank
; i
< m
->NbRows
; i
++)
2579 value_set_si (sum
, 0);
2580 for (j
= 0; j
< m
->NbColumns
; j
++)
2581 value_addmul (sum
, T
[j
], m
->p
[i
][j
]);
2583 if (value_ne (sum
, coeffs
[i
]))
2585 for (i
= 0; i
< nbr
; i
++)
2586 value_clear (coeffs
[i
]);
2587 for (i
= 0; i
< nbc
; i
++)
2603 static CloogMatrix
*
2604 cloog_dio_init_U (CloogMatrix
*u
, int n
, int rank
)
2610 return cloog_matrix_alloc (0, 0);
2612 res
= cloog_matrix_alloc (n
, n
- rank
);
2614 for (i
= 0; i
< res
->NbRows
; i
++)
2615 for (j
= 0; j
< res
->NbColumns
; j
++)
2616 value_assign (res
->p
[i
][j
], u
->p
[i
][j
+ rank
]);
2622 cloog_dio_init_X (CloogMatrix
*u
, Value
*t
, int n
)
2625 Vector
*res
= Vector_Alloc (n
);
2629 for (i
= 0; i
< u
->NbRows
; i
++)
2631 value_set_si (sum
, 0);
2633 for (j
= 0; j
< u
->NbColumns
; j
++)
2634 value_addmul (sum
, u
->p
[i
][j
], t
[j
]);
2636 value_assign (res
->p
[i
], sum
);
2644 cloog_solve_diophantine (CloogMatrix
* m
, CloogMatrix
** u
, Vector
** x
)
2646 int i
, nbr
, nbc
, rank
;
2647 CloogMatrix
*A
, *temp
, *hermi
, *unimod
, *unimodinv
;
2651 A
= cloog_matrix_copy (m
);
2652 nbr
= A
->NbRows
- 1;
2654 cloog_dio_rearrange_redundant_rows (A
);
2656 temp
= cloog_matrix_alloc (A
->NbRows
- 1, A
->NbColumns
- 1);
2657 cloog_dio_copy (temp
, A
);
2658 coeffs
= cloog_dio_negate_coeffs (A
);
2659 cloog_matrix_free (A
);
2661 cloog_matrix_hermite (temp
, &hermi
, &unimod
);
2662 rank
= cloog_dio_get_first_diagonal_zero (hermi
);
2663 nbc
= temp
->NbColumns
;
2665 T
= cloog_dio_reduce_diagonal (hermi
, coeffs
, nbc
, rank
);
2666 unimodinv
= cloog_matrix_alloc (unimod
->NbRows
, unimod
->NbColumns
);
2669 || !cloog_dio_check_coeffs (hermi
, T
, coeffs
, nbr
, nbc
, rank
)
2670 || !cloog_matrix_inverse (unimod
, unimodinv
))
2672 *u
= cloog_matrix_alloc (0, 0);
2673 *x
= Vector_Alloc (0);
2675 for (i
= 0; i
< nbr
; i
++)
2676 value_clear (coeffs
[i
]);
2682 *u
= cloog_dio_init_U (unimodinv
, hermi
->NbColumns
, rank
);
2683 *x
= cloog_dio_init_X (unimodinv
, T
, m
->NbColumns
- 1);
2685 cloog_matrix_free (unimod
);
2686 cloog_matrix_free (unimodinv
);
2687 cloog_matrix_free (hermi
);
2688 cloog_matrix_free (temp
);
2690 for (i
= 0; i
< nbr
; i
++)
2691 value_clear (coeffs
[i
]);
2693 for (i
= 0; i
< nbc
; i
++)
2702 * cloog_domain_stride function:
2703 * This function finds the stride imposed to unknown with the column number
2704 * 'strided_level' in order to be integral. For instance, if we have a
2705 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
2706 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
2707 * the unknown i. The function returns the imposed stride in a parameter field.
2708 * - domain is the set of constraint we have to consider,
2709 * - strided_level is the column number of the unknown for which a stride have
2711 * - looking_level is the column number of the unknown that impose a stride to
2712 * the first unknown.
2713 * - stride is the stride that is returned back as a function parameter.
2714 * - offset is the value of the constant c if the condition is of the shape
2715 * (i + c)%s = 0, s being the stride.
2717 * - June 28th 2003: first version.
2718 * - July 14th 2003: can now look for multiple striding constraints and returns
2719 * the GCD of the strides and the common offset.
2720 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2724 cloog_domain_stride (CloogDomain
*domain
, int strided_level
, int nb_par
, Value
*stride
, Value
*offset
)
2727 int n_col
, n_row
, rank
;
2731 polyhedron p
= cloog_domain_polyhedron (domain
);
2732 int dimension
= cloog_domain_dim (domain
);
2733 int nbeq
= cloog_domain_nbeq (domain
);
2735 /* Look at all equalities involving strided_level and the inner
2736 * iterators. We can ignore the outer iterators and the parameters
2737 * here because the lower bound on strided_level is assumed to
2740 n_col
= (1 + dimension
- nb_par
) - strided_level
;
2741 for (i
= 0, n_row
= 0; i
< nbeq
; i
++)
2742 if (cloog_first_non_zero
2743 (p
->Constraint
[i
] + strided_level
, n_col
) != -1)
2746 M
= cloog_matrix_alloc (n_row
+ 1, n_col
+ 1);
2747 for (i
= 0, n_row
= 0; i
< nbeq
; i
++)
2749 if (cloog_first_non_zero
2750 (p
->Constraint
[i
] + strided_level
, n_col
) == -1)
2752 cloog_vector_copy (p
->Constraint
[i
] + strided_level
,
2753 M
->p
[n_row
], n_col
);
2754 value_assign (M
->p
[n_row
][n_col
],
2755 p
->Constraint
[i
][1 + dimension
]);
2758 value_set_si (M
->p
[n_row
][n_col
], 1);
2760 /* Then look at the general solution to the above equalities. */
2761 rank
= cloog_solve_diophantine (M
, &U
, &V
);
2762 cloog_matrix_free (M
);
2766 /* There is no solution, so the body of this loop will
2767 * never execute. We just leave the constraints alone here so
2768 * that they will ensure the body will not be executed.
2769 * We should probably propagate this information up so that
2770 * the loop can be removed entirely.
2772 value_set_si (*offset
, 0);
2773 value_set_si (*stride
, 1);
2777 /* Compute the gcd of the coefficients defining strided_level. */
2778 cloog_vector_gcd (U
->p
[0], U
->NbColumns
, stride
);
2779 value_oppose (*offset
, V
->p
[0]);
2780 value_pmodulus (*offset
, *offset
, *stride
);
2783 cloog_matrix_free (U
);
2790 * cloog_domain_integral_lowerbound function:
2791 * This function returns 1 if the lower bound of an iterator (such as its
2792 * column rank in the constraint set 'domain' is 'level') is integral,
2793 * 0 otherwise. If the lower bound is actually integral, the function fills
2794 * the 'lower' field with the lower bound value.
2795 * - June 29th 2003: first version.
2796 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2800 cloog_domain_integral_lowerbound (CloogDomain
*domain
, int level
, Value
*lower
)
2802 int i
, first_lower
= 1, dimension
, lower_constraint
= -1, nbc
;
2803 Value iterator
, constant
, tmp
;
2804 polyhedron p
= cloog_domain_polyhedron (domain
);
2805 dimension
= cloog_domain_dim (domain
);
2806 nbc
= cloog_domain_nbconstraints (domain
);
2808 /* We want one and only one lower bound (e.g. no equality, no maximum
2811 for (i
= 0; i
< nbc
; i
++)
2812 if (value_zero_p (p
->Constraint
[i
][0])
2813 && value_notzero_p (p
->Constraint
[i
][level
]))
2816 for (i
= 0; i
< nbc
; i
++)
2817 if (value_pos_p (p
->Constraint
[i
][level
]))
2822 lower_constraint
= i
;
2831 /* We want an integral lower bound: no other non-zero entry except the
2832 * iterator coefficient and the constant.
2834 for (i
= 1; i
< level
; i
++)
2836 (p
->Constraint
[lower_constraint
][i
]))
2839 for (i
= level
+ 1; i
<= dimension
; i
++)
2841 (p
->Constraint
[lower_constraint
][i
]))
2846 value_init_c (iterator
);
2847 value_init_c (constant
);
2850 /* If all is passed, then find the lower bound and return 1. */
2851 value_assign (iterator
,
2852 p
->Constraint
[lower_constraint
][level
]);
2853 value_oppose (constant
,
2854 p
->Constraint
[lower_constraint
][dimension
+ 1]);
2856 value_modulus (tmp
, constant
, iterator
);
2857 value_division (*lower
, constant
, iterator
);
2859 if (!(value_zero_p (tmp
) || value_neg_p (constant
)))
2860 value_increment (*lower
, *lower
);
2862 value_clear_c (iterator
);
2863 value_clear_c (constant
);
2864 value_clear_c (tmp
);
2870 * cloog_domain_lowerbound_update function:
2871 * This function updates the integral lower bound of an iterator (such as its
2872 * column rank in the constraint set 'domain' is 'level') into 'lower'.
2873 * - Jun 29th 2003: first version.
2874 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2878 cloog_domain_lowerbound_update (CloogDomain
*domain
, int level
, Value lower
)
2881 int nbc
= cloog_domain_nbconstraints (domain
);
2882 int dim
= cloog_domain_dim (domain
);
2883 polyhedron p
= cloog_domain_polyhedron (domain
);
2885 /* There is only one lower bound, the first one is the good one. */
2886 for (i
= 0; i
< nbc
; i
++)
2887 if (value_pos_p (p
->Constraint
[i
][level
]))
2889 value_set_si (p
->Constraint
[i
][level
], 1);
2890 value_oppose (p
->Constraint
[i
][dim
+ 1], lower
);
2897 * cloog_domain_lazy_equal function:
2898 * This function returns 1 if the domains given as input are the same, 0 if it
2899 * is unable to decide. This function makes an entry-to-entry comparison between
2900 * the constraint systems, if all the entries are the same, the domains are
2901 * obviously the same and it returns 1, at the first difference, it returns 0.
2902 * This is a very fast way to verify this property. It has been shown (with the
2903 * CLooG benchmarks) that operations on equal domains are 17% of all the
2904 * polyhedral computations. For 75% of the actually identical domains, this
2905 * function answer that they are the same and allow to give immediately the
2906 * trivial solution instead of calling the heavy general functions of PolyLib.
2907 * - August 22th 2003: first version.
2908 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
2912 cloog_domain_lazy_equal (CloogDomain
* d1
, CloogDomain
* d2
)
2915 polyhedra_union u1
= cloog_domain_upol (d1
);
2916 polyhedra_union u2
= cloog_domain_upol (d2
);
2920 if ((cloog_upol_nbc (u1
) != cloog_upol_nbc (u2
)) ||
2921 (cloog_upol_dim (u1
) != cloog_upol_dim (u2
)))
2924 for (i
= 0; i
< (int) cloog_upol_nbc (u1
); i
++)
2925 for (j
= 0; j
< (int) cloog_upol_dim (u1
) + 2; j
++)
2926 if (value_ne (cloog_upol_polyhedron (u1
)->Constraint
[i
][j
],
2927 cloog_upol_polyhedron (u2
)->Constraint
[i
][j
]))
2930 u1
= cloog_upol_next (u1
);
2931 u2
= cloog_upol_next (u2
);
2942 * cloog_domain_lazy_block function:
2943 * This function returns 1 if the two domains d1 and d2 given as input are the
2944 * same (possibly except for a dimension equal to a constant where we accept
2945 * a difference of 1) AND if we are sure that there are no other domain in
2946 * the code generation problem that may put integral points between those of
2947 * d1 and d2 (0 otherwise). In fact this function answers the question "can I
2948 * safely consider the two domains as only one with two statements (a block) ?".
2949 * This function is lazy: it asks for very standard scattering representation
2950 * (only one constraint per dimension which is an equality, and the constraints
2951 * are ordered per dimension depth: the left hand side of the constraint matrix
2952 * is the identity) and will answer NO at the very first problem.
2953 * - d1 and d2 are the two domains to check for blocking,
2954 * - scattering is the linked list of all domains,
2955 * - scattdims is the total number of scattering dimentions.
2957 * - April 30th 2005: beginning
2958 * - June 9th 2005: first working version.
2959 * - June 10th 2005: debugging.
2960 * - June 21rd 2005: Adaptation for GMP.
2961 * - October 16th 2005: (debug) some false blocks have been removed.
2964 cloog_domain_lazy_block (CloogDomain
*d1
, CloogDomain
*d2
, CloogDomainList
*scattering
, int scattdims
)
2966 int i
, j
, difference
= 0, different_constraint
= 0, nbc
;
2968 Value date1
, date2
, date3
, temp
;
2971 /* Some basic checks: we only accept convex domains, with same constraint
2972 * and dimension numbers.
2974 if (!cloog_domain_isconvex (d1
) || !cloog_domain_isconvex (d2
) ||
2975 (cloog_domain_nbconstraints (d1
) != cloog_domain_nbconstraints (d2
)) ||
2976 (cloog_domain_dim (d1
) != cloog_domain_dim (d2
)))
2979 p1
= cloog_domain_polyhedron (d1
);
2980 p2
= cloog_domain_polyhedron (d2
);
2981 nbc
= cloog_domain_nbconstraints (d1
);
2982 dim1
= cloog_domain_dim (d1
);
2983 dim2
= cloog_domain_dim (d2
);
2985 /* There should be only one difference between the two domains, it
2986 * has to be at the constant level and the difference must be of +1,
2987 * moreover, after the difference all domain coefficient has to be 0.
2988 * The matrix shape is:
2990 * |===========|=====|<- 0 line
2991 * |===========|=====|
2992 * |===========|====?|<- different_constraint line (found here)
2993 * |===========|0000=|
2994 * |===========|0000=|<- pX->NbConstraints line
2997 * | | (pX->Dimension + 2) column
2998 * | scattdims column
3002 value_init_c (temp
);
3003 for (i
= 0; i
< nbc
; i
++)
3005 if (difference
== 0)
3006 { /* All elements except scalar must be equal. */
3007 for (j
= 0; j
< dim1
+ 1; j
++)
3008 if (value_ne (p1
->Constraint
[i
][j
],
3009 p2
->Constraint
[i
][j
]))
3011 value_clear_c (temp
);
3014 /* The scalar may differ from +1 (now j=(p1->Dimension + 1)). */
3015 if (value_ne (p1
->Constraint
[i
][j
],
3016 p2
->Constraint
[i
][j
]))
3018 value_increment (temp
, p2
->Constraint
[i
][j
]);
3019 if (value_ne (p1
->Constraint
[i
][j
], temp
))
3021 value_clear_c (temp
);
3027 different_constraint
= i
;
3032 { /* Scattering coefficients must be equal. */
3033 for (j
= 0; j
< (scattdims
+ 1); j
++)
3034 if (value_ne (p1
->Constraint
[i
][j
],
3035 p2
->Constraint
[i
][j
]))
3037 value_clear_c (temp
);
3041 /* Domain coefficients must be 0. */
3042 for (; j
< dim1
+ 1; j
++)
3043 if (value_notzero_p (p1
->Constraint
[i
][j
])
3044 || value_notzero_p (p2
->Constraint
[i
][j
]))
3046 value_clear_c (temp
);
3050 /* Scalar must be equal. */
3051 if (value_ne (p1
->Constraint
[i
][j
],
3052 p2
->Constraint
[i
][j
]))
3054 value_clear_c (temp
);
3059 value_clear_c (temp
);
3061 /* If the domains are exactly the same, this is a block. */
3062 if (difference
== 0)
3065 /* Now a basic check that the constraint with the difference is an
3066 * equality of a dimension with a constant.
3068 for (i
= 0; i
<= different_constraint
; i
++)
3069 if (value_notzero_p (p1
->Constraint
[different_constraint
][i
]))
3072 if (value_notone_p (p1
->Constraint
[different_constraint
][different_constraint
+ 1]))
3075 for (i
= different_constraint
+ 2; i
< dim1
+ 1; i
++)
3076 if (value_notzero_p (p1
->Constraint
[different_constraint
][i
]))
3079 /* For the moment, d1 and d2 are a block candidate. There remains to check
3080 * that there is no other domain that may put an integral point between
3081 * them. In our lazy test we ensure this property by verifying that the
3082 * constraint matrices have a very strict shape: let us consider that the
3083 * dimension with the difference is d. Then the first d dimensions are
3084 * defined in their depth order using equalities (thus the first column begins
3085 * with d zeroes, there is a d*d identity matrix and a zero-matrix for
3086 * the remaining simensions). If a domain can put integral points between the
3087 * domains of the block candidate, this means that the other entries on the
3088 * first d constraints are equal to those of d1 or d2. Thus we are looking for
3089 * such a constraint system, if it exists d1 and d2 is considered to not be
3090 * a block, it is a bock otherwise.
3092 * 1. Only equalities (for the first different_constraint+1 lines).
3093 * | 2. Must be the identity.
3094 * | | 3. Must be zero.
3095 * | | | 4. Elements are equal, the last one is either date1 or 2.
3098 * |0|100|00000|=====|<- 0 line
3099 * |0|010|00000|=====|
3100 * |0|001|00000|====?|<- different_constraint line
3101 * |*|***|*****|*****|
3102 * |*|***|*****|*****|<- pX->NbConstraints line
3105 * | | | (pX->Dimension + 2) column
3106 * | | scattdims column
3107 * | different_constraint+1 column
3111 /* Step 1 and 2. This is only necessary to check one domain because
3112 * we checked that they are equal on this part before.
3114 for (i
= 0; i
<= different_constraint
; i
++)
3116 for (j
= 0; j
< i
+ 1; j
++)
3117 if (value_notzero_p (p1
->Constraint
[i
][j
]))
3120 if (value_notone_p (p1
->Constraint
[i
][i
+ 1]))
3123 for (j
= i
+ 2; j
<= different_constraint
+ 1; j
++)
3124 if (value_notzero_p (p1
->Constraint
[i
][j
]))
3129 for (i
= 0; i
<= different_constraint
; i
++)
3130 for (j
= different_constraint
+ 2; j
<= scattdims
; j
++)
3131 if (value_notzero_p (p1
->Constraint
[i
][j
]))
3134 value_init_c (date1
);
3135 value_init_c (date2
);
3136 value_init_c (date3
);
3138 /* Now we have to check that the two different dates are unique. */
3139 value_assign (date1
, p1
->Constraint
[different_constraint
][dim1
+ 1]);
3140 value_assign (date2
, p2
->Constraint
[different_constraint
][dim2
+ 1]);
3142 /* Step 4. We check all domains except d1 and d2 and we look for at least
3143 * a difference with d1 or d2 on the first different_constraint+1 dimensions.
3145 while (scattering
!= NULL
)
3147 if ((cloog_domain (scattering
) != d1
)
3148 && (cloog_domain (scattering
) != d2
))
3150 CloogDomain
*d3
= cloog_domain (scattering
);
3151 polyhedron p3
= cloog_domain_polyhedron (d3
);
3152 int dim3
= cloog_domain_dim (d3
);
3154 value_assign (date3
,
3155 p3
->Constraint
[different_constraint
][dim3
+ 1]);
3158 if (value_ne (date3
, date2
) && value_ne (date3
, date1
))
3161 for (i
= 0; (i
< different_constraint
) && (!difference
); i
++)
3162 for (j
= 0; (j
< dim3
+ 2) && !difference
; j
++)
3164 (p1
->Constraint
[i
][j
],
3165 p3
->Constraint
[i
][j
]))
3168 for (j
= 0; (j
< dim3
+ 1) && !difference
; j
++)
3170 (p1
->Constraint
[different_constraint
][j
],
3171 p3
->Constraint
[different_constraint
][j
]))
3176 value_clear_c (date1
);
3177 value_clear_c (date2
);
3178 value_clear_c (date3
);
3183 scattering
= cloog_next_domain (scattering
);
3186 value_clear_c (date1
);
3187 value_clear_c (date2
);
3188 value_clear_c (date3
);
3194 * cloog_domain_lazy_disjoint function:
3195 * This function returns 1 if the domains given as input are disjoint, 0 if it
3196 * is unable to decide. This function finds the unknown with fixed values in
3197 * both domains (on a given constraint, their column entry is not zero and
3198 * only the constant coefficient can be different from zero) and verify that
3199 * their values are the same. If not, the domains are obviously disjoint and
3200 * it returns 1, if there is not such case it returns 0. This is a very fast
3201 * way to verify this property. It has been shown (with the CLooG benchmarks)
3202 * that operations on disjoint domains are 36% of all the polyhedral
3203 * computations. For 94% of the actually identical domains, this
3204 * function answer that they are disjoint and allow to give immediately the
3205 * trivial solution instead of calling the heavy general functions of PolyLib.
3206 * - August 22th 2003: first version.
3207 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
3211 cloog_domain_lazy_disjoint (CloogDomain
* d1
, CloogDomain
* d2
)
3213 int i1
, j1
, i2
, j2
, scat_dim
, nbc1
, nbc2
;
3218 if (!cloog_domain_isconvex (d1
) || !cloog_domain_isconvex (d2
))
3221 p1
= cloog_domain_polyhedron (d1
);
3222 p2
= cloog_domain_polyhedron (d2
);
3223 nbc1
= cloog_domain_nbconstraints (d1
);
3224 nbc2
= cloog_domain_nbconstraints (d2
);
3225 dim1
= cloog_domain_dim (d1
);
3226 dim2
= cloog_domain_dim (d2
);
3227 value_init_c (scat_val
);
3229 for (i1
= 0; i1
< nbc1
; i1
++)
3231 if (value_notzero_p (p1
->Constraint
[i1
][0]))
3235 while (value_zero_p (p1
->Constraint
[i1
][scat_dim
]) &&
3239 if (value_notone_p (p1
->Constraint
[i1
][scat_dim
]))
3243 for (j1
= scat_dim
+ 1; j1
<= dim1
; j1
++)
3244 if (value_notzero_p (p1
->Constraint
[i1
][j1
]))
3250 value_assign (scat_val
,
3251 p1
->Constraint
[i1
][dim1
+ 1]);
3253 for (i2
= 0; i2
< nbc2
; i2
++)
3255 for (j2
= 0; j2
< scat_dim
; j2
++)
3256 if (value_notzero_p (p2
->Constraint
[i2
][j2
]))
3259 if ((j2
!= scat_dim
)
3261 value_notone_p (p2
->Constraint
[i2
][scat_dim
]))
3264 for (j2
= scat_dim
+ 1; j2
< dim2
; j2
++)
3265 if (value_notzero_p (p2
->Constraint
[i2
][j2
]))
3272 (p2
->Constraint
[i2
][dim2
+ 1], scat_val
))
3274 value_clear_c (scat_val
);
3281 value_clear_c (scat_val
);
3287 * cloog_domain_list_lazy_same function:
3288 * This function returns 1 if two domains in the list are the same, 0 if it
3289 * is unable to decide.
3290 * - February 9th 2004: first version.
3293 cloog_domain_list_lazy_same (CloogDomainList
* list
)
3294 { /*int i=1, j=1 ; */
3295 CloogDomainList
*current
, *next
;
3298 while (current
!= NULL
)
3300 next
= cloog_next_domain (current
);
3302 while (next
!= NULL
)
3304 if (cloog_domain_lazy_equal (cloog_domain (current
),
3305 cloog_domain (next
)))
3306 { /*printf("Same domains: %d and %d\n",i,j) ; */
3310 next
= cloog_next_domain (next
);
3313 current
= cloog_next_domain (current
);
3320 * cloog_domain_cut_first function:
3321 * this function returns a CloogDomain structure with everything except the
3322 * first part of the polyhedra union of the input domain as domain. After a call
3323 * to this function, there remains in the CloogDomain structure provided as
3324 * input only the first part of the original polyhedra union.
3325 * - April 20th 2005: first version, extracted from different part of loop.c.
3328 cloog_domain_cut_first (CloogDomain
* domain
)
3332 if (domain
&& cloog_domain_polyhedron (domain
))
3334 if (!cloog_upol_next (cloog_domain_upol (domain
)))
3337 rest
= cloog_new_domain (cloog_upol_next (cloog_domain_upol (domain
)));
3338 cloog_upol_set_next (cloog_domain_upol (domain
), NULL
);
3343 return cloog_check_domain (rest
);
3348 * cloog_domain_lazy_isscalar function:
3349 * this function returns 1 if the dimension 'dimension' in the domain 'domain'
3350 * is scalar, this means that the only constraint on this dimension must have
3351 * the shape "x.dimension + scalar = 0" with x an integral variable. This
3352 * function is lazy since we only accept x=1 (further calculations are easier
3354 * - June 14th 2005: first version.
3355 * - June 21rd 2005: Adaptation for GMP.
3358 cloog_domain_lazy_isscalar (CloogDomain
* domain
, int dimension
)
3361 polyhedron p
= cloog_domain_polyhedron (domain
);
3362 int nbc
= cloog_domain_nbconstraints (domain
);
3363 int dim
= cloog_domain_dim (domain
);
3365 /* For each constraint... */
3366 for (i
= 0; i
< nbc
; i
++)
3367 { /* ...if it is concerned by the potentially scalar dimension... */
3369 (p
->Constraint
[i
][dimension
+ 1]))
3370 { /* ...check that the constraint has the shape "dimension + scalar = 0". */
3371 for (j
= 0; j
<= dimension
; j
++)
3372 if (value_notzero_p (p
->Constraint
[i
][j
]))
3376 (p
->Constraint
[i
][dimension
+ 1]))
3379 for (j
= dimension
+ 2; j
< dim
+ 1; j
++)
3380 if (value_notzero_p (p
->Constraint
[i
][j
]))
3390 * cloog_domain_scalar function:
3391 * when we call this function, we know that "dimension" is a scalar dimension,
3392 * this function finds the scalar value in "domain" and returns it in "value".
3393 * - June 30th 2005: first version.
3396 cloog_domain_scalar (CloogDomain
* domain
, int dimension
, Value
* value
)
3399 polyhedron p
= cloog_domain_polyhedron (domain
);
3400 int nbc
= cloog_domain_nbconstraints (domain
);
3401 int dim
= cloog_domain_dim (domain
);
3403 /* For each constraint... */
3404 for (i
= 0; i
< nbc
; i
++)
3405 { /* ...if it is the equality defining the scalar dimension... */
3407 (p
->Constraint
[i
][dimension
+ 1])
3408 && value_zero_p (p
->Constraint
[i
][0]))
3409 { /* ...Then send the scalar value. */
3410 value_assign (*value
, p
->Constraint
[i
][dim
+ 1]);
3411 value_oppose (*value
, *value
);
3416 /* We should have found a scalar value: if not, there is an error. */
3417 fprintf (stderr
, "[CLooG]ERROR: dimension %d is not scalar as expected.\n",
3424 * cloog_domain_erase_dimension function:
3425 * this function returns a CloogDomain structure builds from 'domain' where
3426 * we removed the dimension 'dimension' and every constraint considering this
3427 * dimension. This is not a projection ! Every data concerning the
3428 * considered dimension is simply erased.
3429 * - June 14th 2005: first version.
3430 * - June 21rd 2005: Adaptation for GMP.
3433 cloog_domain_erase_dimension (CloogDomain
* domain
, int dimension
)
3435 int i
, j
, mi
, nb_dim
, nbc
;
3436 CloogMatrix
*matrix
;
3437 CloogDomain
*erased
;
3438 polyhedron p
= cloog_domain_polyhedron (domain
);
3440 nb_dim
= cloog_domain_dim (domain
);
3441 nbc
= cloog_domain_nbconstraints (domain
);
3443 /* The matrix is one column less and at least one constraint less. */
3444 matrix
= cloog_matrix_alloc (nbc
- 1, nb_dim
+ 1);
3446 /* mi is the constraint counter for the matrix. */
3448 for (i
= 0; i
< nbc
; i
++)
3449 if (value_zero_p (p
->Constraint
[i
][dimension
+ 1]))
3451 for (j
= 0; j
<= dimension
; j
++)
3452 value_assign (matrix
->p
[mi
][j
],
3453 p
->Constraint
[i
][j
]);
3455 for (j
= dimension
+ 2; j
< nb_dim
+ 2; j
++)
3456 value_assign (matrix
->p
[mi
][j
- 1],
3457 p
->Constraint
[i
][j
]);
3462 erased
= cloog_domain_matrix2domain (matrix
);
3463 cloog_matrix_free (matrix
);
3465 return cloog_check_domain (erased
);
3468 /* Number of polyhedra inside the union of disjoint polyhedra. */
3471 cloog_domain_nb_polyhedra (CloogDomain
* domain
)
3474 polyhedra_union upol
= cloog_domain_upol (domain
);
3479 upol
= cloog_upol_next (upol
);
3486 cloog_domain_print_polyhedra (FILE * foo
, CloogDomain
* domain
)
3488 polyhedra_union upol
= cloog_domain_upol (domain
);
3490 while (upol
!= NULL
)
3492 CloogMatrix
*matrix
= cloog_upol_domain2matrix (upol
);
3493 cloog_matrix_print (foo
, matrix
);
3494 cloog_matrix_free (matrix
);
3495 upol
= cloog_upol_next (upol
);
3500 debug_cloog_domain (CloogDomain
*domain
)
3502 cloog_domain_print_polyhedra (stderr
, domain
);
3506 debug_cloog_matrix (CloogMatrix
*m
)
3508 cloog_matrix_print (stderr
, m
);
3512 debug_value (Value v
)
3514 value_print (stderr
, VALUE_FMT
, v
);
3518 debug_values (Value
*p
, int length
)
3521 for (i
= 0; i
< length
; i
++)
3525 polyhedra_union
cloog_new_upol (polyhedron p
)
3527 polyhedra_union ppl
=
3528 (polyhedra_union
) malloc (sizeof (struct polyhedra_union_s
));
3529 ppl
->_polyhedron
= p
;
3534 Vector
*Vector_Alloc (unsigned length
)
3537 Vector
*vector
= (Vector
*) malloc (sizeof (Vector
));
3539 vector
->Size
= length
;
3540 vector
->p
= (Value
*) malloc (length
* sizeof (Value
));
3542 for (i
= 0; i
< length
; i
++)
3543 value_init (vector
->p
[i
]);
3548 polyhedron
cloog_new_pol (int dim
, int nrows
)
3551 polyhedron res
= (polyhedron
) malloc (sizeof (struct polyhedron_s
));
3552 int ncolumns
= dim
+ 2;
3553 int n
= nrows
* ncolumns
;
3554 Value
*p
= (Value
*) malloc (n
* sizeof (Value
));
3556 res
->Dimension
= dim
;
3557 res
->NbConstraints
= nrows
;
3558 res
->Constraint
= (Value
**) malloc (nrows
* sizeof (Value
*));
3560 for (i
= 0; i
< n
; ++i
)
3563 for (i
= 0; i
< nrows
; i
++, p
+= ncolumns
)
3564 res
->Constraint
[i
] = p
;
3571 * cloog_domain_scatter function:
3572 * This function add the scattering (scheduling) informations in a domain.
3574 CloogDomain
*cloog_domain_scatter(CloogDomain
*domain
, CloogDomain
*scatt
)
3576 CloogDomain
*ext
, *newdom
;
3578 scatt_dim
= cloog_domain_dim(scatt
) - cloog_domain_dim (domain
);
3579 ext
= cloog_domain_extend (domain
, scatt_dim
, cloog_domain_dim(domain
));
3580 newdom
= cloog_domain_intersection (ext
, scatt
);
3582 cloog_domain_free(ext
) ;
3583 cloog_domain_free(domain
);