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 !
43 # include "../../include/cloog/cloog.h"
47 static int cloog_check_polyhedral_ops
= 1;
48 static int cloog_return_ppl_result
= 0;
50 /* Variables names for pretty printing. */
51 static char wild_name
[200][40];
53 static inline const char*
54 variable_output_function (ppl_dimension_type var
)
57 return wild_name
[var
+ 1];
63 error_handler (enum ppl_enum_error_code code
, const char* description
)
65 fprintf (stderr
, "PPL error code %d\n%s", code
, description
);
70 cloog_initialize (void)
72 sprintf (wild_name
[0], "1");
73 sprintf (wild_name
[1], "a");
74 sprintf (wild_name
[2], "b");
75 sprintf (wild_name
[3], "c");
76 sprintf (wild_name
[4], "d");
77 sprintf (wild_name
[5], "e");
78 sprintf (wild_name
[6], "f");
79 sprintf (wild_name
[7], "g");
80 sprintf (wild_name
[8], "h");
81 sprintf (wild_name
[9], "i");
82 sprintf (wild_name
[10], "j");
83 sprintf (wild_name
[11], "k");
84 sprintf (wild_name
[12], "l");
85 sprintf (wild_name
[13], "m");
86 sprintf (wild_name
[14], "n");
87 sprintf (wild_name
[15], "o");
88 sprintf (wild_name
[16], "p");
89 sprintf (wild_name
[17], "q");
90 sprintf (wild_name
[18], "r");
91 sprintf (wild_name
[19], "s");
92 sprintf (wild_name
[20], "t");
93 sprintf (wild_name
[21], "alpha");
94 sprintf (wild_name
[22], "beta");
95 sprintf (wild_name
[23], "gamma");
96 sprintf (wild_name
[24], "delta");
97 sprintf (wild_name
[25], "tau");
98 sprintf (wild_name
[26], "sigma");
99 sprintf (wild_name
[27], "chi");
100 sprintf (wild_name
[28], "omega");
101 sprintf (wild_name
[29], "pi");
102 sprintf (wild_name
[30], "ni");
103 sprintf (wild_name
[31], "Alpha");
104 sprintf (wild_name
[32], "Beta");
105 sprintf (wild_name
[33], "Gamma");
106 sprintf (wild_name
[34], "Delta");
107 sprintf (wild_name
[35], "Tau");
108 sprintf (wild_name
[36], "Sigma");
109 sprintf (wild_name
[37], "Chi");
110 sprintf (wild_name
[38], "Omega");
111 sprintf (wild_name
[39], "xxx");
113 if (ppl_initialize() < 0)
115 fprintf (stderr
, "Cannot initialize the Parma Polyhedra Library.\n");
119 if (ppl_set_error_handler (error_handler
) < 0)
121 fprintf (stderr
, "Cannot install the custom error handler.\n");
125 if (ppl_io_set_variable_output_function (variable_output_function
) < 0)
127 fprintf (stderr
, "Cannot install the PPL custom variable output function. \n");
133 * The maximal number of rays allowed to be allocated by PolyLib. In fact since
134 * version 5.20, PolyLib automatically tune the number of rays by multiplying
135 * by 2 this number each time the maximum is reached. For unknown reasons
136 * PolyLib makes a segmentation fault if this number is too small. If this
137 * number is too small, performances will be reduced, if it is too high, memory
138 * will be saturated. Note that the option "-rays X" set this number to X.
142 /* Unused in this backend. */
144 int cloog_domain_allocated
= 0;
145 int cloog_domain_freed
= 0;
146 int cloog_domain_max
= 0;
148 /* The same for Value variables since in GMP mode they have to be freed. */
149 int cloog_value_allocated
= 0;
150 int cloog_value_freed
= 0;
151 int cloog_value_max
= 0;
155 cloog_value_leak_up ()
157 cloog_value_allocated
++;
158 if ((cloog_value_allocated
- cloog_value_freed
) > cloog_value_max
)
159 cloog_value_max
= cloog_value_allocated
- cloog_value_freed
;
164 cloog_value_leak_down ()
169 static inline Polyhedron
*
170 cloog_domain_polyhedron_set (CloogDomain
* d
, Polyhedron
* p
)
172 return d
->_polyhedron
= p
;
176 cloog_domain_set_references (CloogDomain
* d
, int i
)
182 * cloog_domain_malloc function:
183 * This function allocates the memory space for a CloogDomain structure and
184 * sets its fields with default values. Then it returns a pointer to the
186 * - November 21th 2005: first version.
189 cloog_domain_malloc ()
193 domain
= (CloogDomain
*) malloc (sizeof (CloogDomain
));
196 fprintf (stderr
, "[CLooG]ERROR: memory overflow.\n");
200 /* We set the various fields with default values. */
201 cloog_domain_polyhedron_set (domain
, NULL
);
202 cloog_domain_set_references (domain
, 1);
209 * cloog_domain_alloc function:
210 * This function allocates the memory space for a CloogDomain structure and
211 * sets its fields with those given as input. Then it returns a pointer to the
213 * - April 19th 2005: first version.
214 * - November 21th 2005: cloog_domain_malloc use.
217 cloog_domain_alloc (Polyhedron
* polyhedron
)
221 if (polyhedron
== NULL
)
225 domain
= cloog_domain_malloc ();
226 cloog_domain_polyhedron_set (domain
, polyhedron
);
234 * cloog_domain_matrix2domain function:
235 * Given a matrix of constraints (matrix), this function constructs and returns
236 * the corresponding domain (i.e. the CloogDomain structure including the
237 * polyhedron with its double representation: constraint matrix and the set of
241 cloog_domain_matrix2domain (CloogMatrix
* matrix
)
243 return (cloog_domain_alloc (Constraints2Polyhedron (matrix
, MAX_RAYS
)));
247 static inline Polyhedron
*
248 cloog_domain_polyhedron (CloogDomain
* domain
)
250 return domain
->_polyhedron
;
254 * cloog_domain_domain2matrix function:
255 * Given a polyhedron (in domain), this function returns its corresponding
256 * matrix of constraints.
259 cloog_domain_domain2matrix (CloogDomain
* domain
)
261 return Polyhedron2Constraints (cloog_domain_polyhedron (domain
));
264 /* In the matrix representation an equality has a 0 in the first
265 column. When the value of the first column is 1, the row
266 represents an inequality. */
269 cloog_matrix_row_is_eq_p (CloogMatrix
*matrix
, int row
)
271 return value_zero_p (matrix
->p
[row
][0]);
274 static ppl_Polyhedron_t
275 cloog_translate_constraint_matrix (CloogMatrix
*matrix
)
278 ppl_Polyhedron_t res
;
279 ppl_Constraint_t cstr
;
280 ppl_Linear_Expression_t expr
;
281 ppl_Coefficient_t coef
;
282 ppl_dimension_type dim
= matrix
->NbColumns
- 2;
284 ppl_new_Coefficient (&coef
);
285 ppl_new_NNC_Polyhedron_from_dimension (&res
, dim
);
287 for (i
= 0; i
< matrix
->NbRows
; i
++)
289 ppl_new_Linear_Expression_with_dimension (&expr
, dim
);
291 for (j
= 1; j
< matrix
->NbColumns
- 1; j
++)
293 ppl_assign_Coefficient_from_mpz_t (coef
, matrix
->p
[i
][j
]);
294 ppl_Linear_Expression_add_to_coefficient (expr
, j
- 1, coef
);
297 ppl_assign_Coefficient_from_mpz_t
298 (coef
, matrix
->p
[i
][matrix
->NbColumns
- 1]);
299 ppl_Linear_Expression_add_to_inhomogeneous (expr
, coef
);
301 if (cloog_matrix_row_is_eq_p (matrix
, i
))
302 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_EQUAL
);
304 ppl_new_Constraint (&cstr
, expr
, PPL_CONSTRAINT_TYPE_GREATER_THAN_OR_EQUAL
);
306 ppl_Polyhedron_add_constraint (res
, cstr
);
309 if (cloog_check_polyhedral_ops
)
310 ppl_Polyhedron_OK (res
);
316 cloog_translate_ppl_polyhedron (ppl_Polyhedron_t pol
)
319 CloogMatrix
*matrix
;
320 ppl_dimension_type dim
;
321 ppl_const_Constraint_System_t pcs
;
322 ppl_Constraint_System_const_iterator_t cit
, end
;
325 ppl_Polyhedron_constraints (pol
, &pcs
);
326 ppl_new_Constraint_System_const_iterator (&cit
);
327 ppl_new_Constraint_System_const_iterator (&end
);
329 for (row
= 0, ppl_Constraint_System_begin (pcs
, cit
), ppl_Constraint_System_end (pcs
, end
);
330 !ppl_Constraint_System_const_iterator_equal_test (cit
, end
);
331 ppl_Constraint_System_const_iterator_increment (cit
), row
++);
333 ppl_Polyhedron_space_dimension (pol
, &dim
);
334 matrix
= cloog_matrix_alloc (row
, dim
+ 2);
336 for (row
= 0, ppl_Constraint_System_begin (pcs
, cit
), ppl_Constraint_System_end (pcs
, end
);
337 !ppl_Constraint_System_const_iterator_equal_test (cit
, end
);
338 ppl_Constraint_System_const_iterator_increment (cit
), row
++)
340 ppl_const_Constraint_t pc
;
341 ppl_Coefficient_t coef
;
342 ppl_dimension_type col
;
347 ppl_new_Coefficient (&coef
);
348 ppl_Constraint_System_const_iterator_dereference (cit
, &pc
);
350 neg
= (ppl_Constraint_type (pc
) == PPL_CONSTRAINT_TYPE_LESS_THAN
351 || ppl_Constraint_type (pc
) == PPL_CONSTRAINT_TYPE_LESS_THAN_OR_EQUAL
) ? 1 : 0;
353 for (col
= 0; col
< dim
; col
++)
355 ppl_Constraint_coefficient (pc
, col
, coef
);
356 ppl_Coefficient_to_mpz_t (coef
, val
);
359 value_oppose (val
, val
);
361 value_assign (matrix
->p
[row
][col
+1], val
);
364 ppl_Constraint_inhomogeneous_term (pc
, coef
);
365 ppl_Coefficient_to_mpz_t (coef
, val
);
366 value_assign (matrix
->p
[row
][dim
+ 1], val
);
368 switch (ppl_Constraint_type (pc
))
370 case PPL_CONSTRAINT_TYPE_EQUAL
:
371 value_set_si (matrix
->p
[row
][0], 0);
374 case PPL_CONSTRAINT_TYPE_LESS_THAN
:
375 case PPL_CONSTRAINT_TYPE_GREATER_THAN
:
376 value_decrement (matrix
->p
[row
][dim
+ 1], matrix
->p
[row
][dim
+ 1]);
377 value_set_si (matrix
->p
[row
][0], 1);
380 case PPL_CONSTRAINT_TYPE_LESS_THAN_OR_EQUAL
:
381 case PPL_CONSTRAINT_TYPE_GREATER_THAN_OR_EQUAL
:
382 value_set_si (matrix
->p
[row
][0], 1);
386 fprintf (stderr
, "PPL_CONSTRAINT_TYPE_%d not implemented yet\n",
387 ppl_Constraint_type (pc
));
392 res
= cloog_domain_matrix2domain (matrix
);
397 cloog_domain_references (CloogDomain
* d
)
399 return d
->_references
;
403 * cloog_domain_print function:
404 * This function prints the content of a CloogDomain structure (domain) into
405 * a file (foo, possibly stdout).
408 cloog_domain_print (FILE * foo
, CloogDomain
* domain
)
410 Polyhedron_Print (foo
, P_VALUE_FMT
, cloog_domain_polyhedron (domain
));
411 fprintf (foo
, "Number of active references: %d\n",
412 cloog_domain_references (domain
));
416 * cloog_domain_free function:
417 * This function frees the allocated memory for a CloogDomain structure
418 * (domain). It decrements the number of active references to this structure,
419 * if there are no more references on the structure, it frees it (with the
420 * included list of polyhedra).
423 cloog_domain_free (CloogDomain
* domain
)
427 cloog_domain_set_references (domain
,
428 cloog_domain_references (domain
) - 1);
430 if (cloog_domain_references (domain
) == 0)
432 if (cloog_domain_polyhedron (domain
) != NULL
)
433 Domain_Free (cloog_domain_polyhedron (domain
));
442 * cloog_domain_copy function:
443 * This function returns a copy of a CloogDomain structure (domain). To save
444 * memory this is not a memory copy but we increment a counter of active
445 * references inside the structure, then return a pointer to that structure.
448 cloog_domain_copy (CloogDomain
* domain
)
450 cloog_domain_set_references (domain
, cloog_domain_references (domain
) + 1);
456 * cloog_domain_image function:
457 * This function returns a CloogDomain structure such that the included
458 * polyhedral domain is computed from the former one into another
459 * domain according to a given affine mapping function (mapping).
462 cloog_domain_image (CloogDomain
* domain
, CloogMatrix
* mapping
)
464 return (cloog_domain_alloc
466 (cloog_domain_polyhedron (domain
), mapping
, MAX_RAYS
)));
471 * cloog_domain_preimage function:
472 * Given a polyhedral domain (polyhedron) inside a CloogDomain structure and a
473 * mapping function (mapping), this function returns a new CloogDomain structure
474 * with a polyhedral domain which when transformed by mapping function (mapping)
475 * gives (polyhedron).
478 cloog_domain_preimage (CloogDomain
* domain
, CloogMatrix
* mapping
)
480 return (cloog_domain_alloc
482 (cloog_domain_polyhedron (domain
), mapping
, MAX_RAYS
)));
487 * cloog_domain_convex function:
488 * Given a polyhedral domain (polyhedron), this function concatenates the lists
489 * of rays and lines of the two (or more) polyhedra in the domain into one
490 * combined list, and find the set of constraints which tightly bound all of
491 * those objects. It returns the corresponding polyhedron.
494 cloog_domain_convex (CloogDomain
* domain
)
496 return (cloog_domain_alloc
497 (DomainConvex (cloog_domain_polyhedron (domain
), MAX_RAYS
)));
500 static inline Polyhedron
*
501 cloog_polyhedron_next (Polyhedron
* p
)
507 cloog_polyhedron_set_next (Polyhedron
* p
, Polyhedron
* n
)
512 static inline Polyhedron
*
513 cloog_domain_polyhedron_next (CloogDomain
* domain
)
515 return cloog_polyhedron_next (cloog_domain_polyhedron (domain
));
519 cloog_domain_polyhedron_set_next (CloogDomain
* d
, Polyhedron
* n
)
521 cloog_polyhedron_set_next (cloog_domain_polyhedron (d
), n
);
524 static inline unsigned
525 cloog_polyhedron_nbc (Polyhedron
* p
)
527 return p
->NbConstraints
;
531 cloog_domain_nbconstraints (CloogDomain
* domain
)
533 return cloog_domain_polyhedron (domain
)->NbConstraints
;
536 static inline unsigned
537 cloog_polyhedron_nbeq (Polyhedron
* p
)
542 static inline unsigned
543 cloog_domain_nbeq (CloogDomain
* d
)
545 return cloog_polyhedron_nbeq (cloog_domain_polyhedron (d
));
548 static inline unsigned
549 cloog_polyhedron_dim (Polyhedron
* p
)
556 cloog_domain_isconvex (CloogDomain
* domain
)
558 return !cloog_domain_polyhedron_next (domain
);
562 cloog_domain_dim (CloogDomain
* d
)
564 return cloog_polyhedron_dim (cloog_domain_polyhedron (d
));
568 * cloog_domain_simple_convex:
569 * Given a list (union) of polyhedra, this function returns a "simple"
570 * convex hull of this union. In particular, the constraints of the
571 * the returned polyhedron consist of (parametric) lower and upper
572 * bounds on individual variables and constraints that appear in the
573 * original polyhedra.
575 * nb_par is the number of parameters of the domain.
578 cloog_domain_simple_convex (CloogDomain
* domain
, int nb_par
)
580 fprintf (stderr
, "cloog_domain_simple_convex is not implemented yet.\n");
586 * cloog_domain_simplify function:
587 * Given two polyhedral domains (pol1) and (pol2) inside two CloogDomain
588 * structures, this function finds the largest domain set (or the smallest list
589 * of non-redundant constraints), that when intersected with polyhedral
590 * domain (pol2) equals (Pol1)intersect(Pol2). The output is a new CloogDomain
591 * structure with a polyhedral domain with the "redundant" constraints removed.
592 * NB: this function do not work as expected with unions of polyhedra...
595 cloog_domain_simplify (CloogDomain
* dom1
, CloogDomain
* dom2
)
599 Polyhedron
*P
= cloog_domain_polyhedron (dom1
);
601 /* DomainSimplify doesn't remove all redundant equalities,
602 * so we remove them here first in case both dom1 and dom2
603 * are single polyhedra (i.e., not unions of polyhedra).
605 if (cloog_domain_isconvex (dom1
)
606 && cloog_domain_isconvex (dom2
)
607 && cloog_polyhedron_nbeq (P
) && cloog_domain_nbeq (dom2
))
610 int rows
= cloog_polyhedron_nbeq (P
) + cloog_domain_nbeq (dom2
);
611 int cols
= cloog_polyhedron_dim (P
) + 2;
613 M
= cloog_matrix_alloc (rows
, cols
);
614 M2
= cloog_matrix_alloc (cloog_polyhedron_nbc (P
), cols
);
615 Vector_Copy (cloog_domain_polyhedron (dom2
)->Constraint
[0],
616 M
->p
[0], cloog_domain_nbeq (dom2
) * cols
);
617 rank
= cloog_domain_nbeq (dom2
);
619 for (i
= 0; i
< cloog_polyhedron_nbeq (P
); ++i
)
621 Vector_Copy (P
->Constraint
[i
], M
->p
[rank
], cols
);
622 if (Gauss (M
, rank
+ 1, cols
- 1) > rank
)
624 Vector_Copy (P
->Constraint
[i
], M2
->p
[row
++], cols
);
628 if (row
< cloog_polyhedron_nbeq (P
))
630 Vector_Copy (P
->Constraint
[cloog_polyhedron_nbeq (P
)],
632 (cloog_polyhedron_nbc (P
) -
633 cloog_polyhedron_nbeq (P
)) * cols
);
634 P
= Constraints2Polyhedron (M2
, MAX_RAYS
);
636 cloog_matrix_free (M2
);
637 cloog_matrix_free (M
);
640 cloog_domain_alloc (DomainSimplify
641 (P
, cloog_domain_polyhedron (dom2
), MAX_RAYS
));
642 if (P
!= cloog_domain_polyhedron (dom1
))
649 * cloog_domain_union function:
650 * This function returns a new CloogDomain structure including a polyhedral
651 * domain which is the union of two polyhedral domains (pol1) U (pol2) inside
652 * two CloogDomain structures.
655 cloog_domain_union (CloogDomain
* dom1
, CloogDomain
* dom2
)
657 if (!cloog_domain_polyhedron (dom1
))
658 return cloog_domain_alloc (cloog_domain_polyhedron (dom2
));
660 if (!cloog_domain_polyhedron (dom2
))
661 return cloog_domain_alloc (cloog_domain_polyhedron (dom1
));
663 return (cloog_domain_alloc (DomainUnion (cloog_domain_polyhedron (dom1
),
664 cloog_domain_polyhedron (dom2
),
669 * cloog_domain_intersection function:
670 * This function returns a new CloogDomain structure including a polyhedral
671 * domain which is the intersection of two polyhedral domains (pol1)inter(pol2)
672 * inside two CloogDomain structures.
675 cloog_domain_intersection (CloogDomain
* dom1
, CloogDomain
* dom2
)
679 ppl_Polyhedron_t ppl1
, ppl2
;
681 res
= cloog_domain_malloc ();
683 for (p1
= cloog_domain_polyhedron (dom1
); p1
; p1
= p1
->next
)
685 ppl1
= cloog_translate_constraint_matrix (Polyhedron2Constraints (p1
));
687 for (p2
= cloog_domain_polyhedron (dom2
); p2
; p2
= p2
->next
)
689 ppl2
= cloog_translate_constraint_matrix (Polyhedron2Constraints (p2
));
690 ppl_Polyhedron_intersection_assign (ppl2
, ppl1
);
692 res
= cloog_domain_union (res
, cloog_translate_ppl_polyhedron (ppl2
));
696 if (cloog_check_polyhedral_ops
)
698 CloogDomain
*ppl
= res
;
699 CloogDomain
*polylib
= cloog_domain_alloc
700 (DomainIntersection (cloog_domain_polyhedron (dom1
),
701 cloog_domain_polyhedron (dom2
),
704 /* Cannot use cloog_domain_lazy_equal (polylib, ppl) here as
705 this function is too dumb: it does not detect permutations of
707 if (!cloog_domain_isempty (cloog_domain_difference (polylib
, ppl
))
708 && !cloog_domain_isempty (cloog_domain_difference (ppl
, polylib
)))
710 fprintf (stderr
, "((\n");
711 cloog_domain_print (stderr
, ppl
);
712 fprintf (stderr
, ")(\n");
713 cloog_domain_print (stderr
, polylib
);
714 fprintf (stderr
, "))\n");
718 if (cloog_return_ppl_result
)
724 if (cloog_return_ppl_result
)
727 return (cloog_domain_alloc
729 (cloog_domain_polyhedron (dom1
), cloog_domain_polyhedron (dom2
),
735 * cloog_domain_difference function:
736 * This function returns a new CloogDomain structure including a polyhedral
737 * domain which is the difference of two polyhedral domains domain \ minus
738 * inside two CloogDomain structures.
739 * - November 8th 2001: first version.
742 cloog_domain_difference (CloogDomain
* domain
, CloogDomain
* minus
)
744 if (cloog_domain_isempty (minus
))
745 return (cloog_domain_copy (domain
));
747 return (cloog_domain_alloc
749 (cloog_domain_polyhedron (domain
),
750 cloog_domain_polyhedron (minus
), MAX_RAYS
)));
755 * cloog_domain_addconstraints function :
756 * This function adds source's polyhedron constraints to target polyhedron: for
757 * each element of the polyhedron inside 'target' (i.e. element of the union
758 * of polyhedra) it adds the constraints of the corresponding element in
760 * - August 10th 2002: first version.
761 * Nota bene for future : it is possible that source and target don't have the
762 * same number of elements (try iftest2 without non-shared constraint
763 * elimination in cloog_loop_separate !). This function is yet another part
764 * of the DomainSimplify patching problem...
767 cloog_domain_addconstraints (domain_source
, domain_target
)
768 CloogDomain
*domain_source
, *domain_target
;
770 unsigned nb_constraint
;
772 Polyhedron
*source
, *target
, *new, *next
, *last
;
774 source
= cloog_domain_polyhedron (domain_source
);
775 target
= cloog_domain_polyhedron (domain_target
);
777 constraints
= source
->p_Init
;
778 nb_constraint
= cloog_polyhedron_nbc (source
);
779 source
= cloog_polyhedron_next (source
);
780 new = AddConstraints (constraints
, nb_constraint
, target
, MAX_RAYS
);
782 next
= cloog_polyhedron_next (target
);
785 { /* BUG !!! This is actually a bug. I don't know yet how to cleanly avoid
786 * the situation where source and target do not have the same number of
787 * elements. So this 'if' is an awful trick, waiting for better.
791 constraints
= source
->p_Init
;
792 nb_constraint
= cloog_polyhedron_nbc (source
);
793 source
= cloog_polyhedron_next (source
);
795 cloog_polyhedron_set_next (last
,
796 AddConstraints (constraints
, nb_constraint
,
798 last
= cloog_polyhedron_next (last
);
799 next
= cloog_polyhedron_next (next
);
802 return (cloog_domain_alloc (new));
807 * cloog_domain_sort function:
808 * This function topologically sorts (nb_pols) polyhedra. Here (pols) is a an
809 * array of pointers to polyhedra, (nb_pols) is the number of polyhedra,
810 * (level) is the level to consider for partial ordering (nb_par) is the
811 * parameter space dimension, (permut) if not NULL, is an array of (nb_pols)
812 * integers that contains a permutation specification after call in order to
813 * apply the topological sorting.
816 cloog_domain_sort (doms
, nb_pols
, level
, nb_par
, permut
)
818 unsigned nb_pols
, level
, nb_par
;
823 (Polyhedron
**) malloc (nb_pols
* sizeof (Polyhedron
*));
825 for (i
= 0; i
< nb_pols
; i
++)
826 pols
[i
] = cloog_domain_polyhedron (doms
[i
]);
828 /* time is an array of (nb_pols) integers to store logical time values. We
829 * do not use it, but it is compulsory for PolyhedronTSort.
831 time
= (int *) malloc (nb_pols
* sizeof (int));
833 /* PolyhedronTSort will fill up permut (and time). */
834 PolyhedronTSort (pols
, nb_pols
, level
, nb_par
, time
, permut
, MAX_RAYS
);
842 * cloog_domain_empty function:
843 * This function allocates the memory space for a CloogDomain structure and
844 * sets its polyhedron to an empty polyhedron with 'dimension' dimensions.
845 * Then it returns a pointer to the allocated space.
846 * - June 10th 2005: first version.
849 cloog_domain_empty (int dimension
)
851 return (cloog_domain_alloc (Empty_Polyhedron (dimension
)));
855 /******************************************************************************
856 * Structure display function *
857 ******************************************************************************/
861 * cloog_domain_print_structure :
862 * this function is a more human-friendly way to display the CloogDomain data
863 * structure, it only shows the constraint system and includes an indentation
864 * level (level) in order to work with others print_structure functions.
865 * Written by Olivier Chorier, Luc Marchaud, Pierre Martin and Romain Tartiere.
866 * - April 24th 2005: Initial version.
867 * - May 26th 2005: Memory leak hunt.
868 * - June 16th 2005: (Ced) Integration in domain.c.
871 cloog_domain_print_structure (FILE * file
, CloogDomain
* domain
, int level
)
876 /* Go to the right level. */
877 for (i
= 0; i
< level
; i
++)
878 fprintf (file
, "|\t");
882 fprintf (file
, "+-- CloogDomain\n");
884 /* Print the matrix. */
885 matrix
= cloog_domain_domain2matrix (domain
);
886 cloog_matrix_print_structure (file
, matrix
, level
);
887 cloog_matrix_free (matrix
);
890 for (i
= 0; i
< level
+ 1; i
++)
891 fprintf (file
, "|\t");
892 fprintf (file
, "\n");
895 fprintf (file
, "+-- Null CloogDomain\n");
901 * cloog_domain_list_print function:
902 * This function prints the content of a CloogDomainList structure into a
903 * file (foo, possibly stdout).
904 * - November 6th 2001: first version.
907 cloog_domain_list_print (FILE * foo
, CloogDomainList
* list
)
911 cloog_domain_print (foo
, cloog_domain (list
));
912 list
= cloog_next_domain (list
);
917 /******************************************************************************
918 * Memory deallocation function *
919 ******************************************************************************/
923 * cloog_domain_list_free function:
924 * This function frees the allocated memory for a CloogDomainList structure.
925 * - November 6th 2001: first version.
928 cloog_domain_list_free (CloogDomainList
* list
)
930 CloogDomainList
*temp
;
934 temp
= cloog_next_domain (list
);
935 cloog_domain_free (cloog_domain (list
));
942 /******************************************************************************
944 ******************************************************************************/
948 * cloog_domain_read function:
949 * Adaptation from the PolyLib. This function reads a matrix into a file (foo,
950 * posibly stdin) and returns a pointer to a polyhedron containing the read
952 * - October 18th 2001: first version.
955 cloog_domain_read (FILE * foo
)
960 matrix
= cloog_matrix_read (foo
);
961 domain
= cloog_domain_matrix2domain (matrix
);
962 cloog_matrix_free (matrix
);
969 * cloog_domain_union_read function:
970 * This function reads a union of polyhedra into a file (foo, posibly stdin) and
971 * returns a pointer to a Polyhedron containing the read information.
972 * - September 9th 2002: first version.
973 * - October 29th 2005: (debug) removal of a leak counting "correction" that
974 * was just false since ages.
977 cloog_domain_union_read (FILE * foo
)
979 int i
, nb_components
;
981 CloogDomain
*domain
, *temp
, *old
;
983 /* domain reading: nb_components (constraint matrices). */
984 while (fgets (s
, MAX_STRING
, foo
) == 0);
985 while ((*s
== '#' || *s
== '\n') || (sscanf (s
, " %d", &nb_components
) < 1))
986 fgets (s
, MAX_STRING
, foo
);
988 if (nb_components
> 0)
989 { /* 1. first part of the polyhedra union, */
990 domain
= cloog_domain_read (foo
);
991 /* 2. and the nexts. */
992 for (i
= 1; i
< nb_components
; i
++)
993 { /* Leak counting is OK since next allocated domain is freed here. */
994 temp
= cloog_domain_read (foo
);
996 domain
= cloog_domain_union (temp
, old
);
997 cloog_domain_free (temp
);
998 cloog_domain_free (old
);
1008 * cloog_domain_list_read function:
1009 * This function reads a list of polyhedra into a file (foo, posibly stdin) and
1010 * returns a pointer to a CloogDomainList containing the read information.
1011 * - November 6th 2001: first version.
1014 cloog_domain_list_read (FILE * foo
)
1018 CloogDomainList
*list
, *now
, *next
;
1021 /* We read first the number of polyhedra in the list. */
1022 while (fgets (s
, MAX_STRING
, foo
) == 0);
1023 while ((*s
== '#' || *s
== '\n') || (sscanf (s
, " %d", &nb_pols
) < 1))
1024 fgets (s
, MAX_STRING
, foo
);
1026 /* Then we read the polyhedra. */
1030 list
= (CloogDomainList
*) malloc (sizeof (CloogDomainList
));
1031 cloog_set_domain (list
, cloog_domain_read (foo
));
1032 cloog_set_next_domain (list
, NULL
);
1034 for (i
= 1; i
< nb_pols
; i
++)
1036 next
= (CloogDomainList
*) malloc (sizeof (CloogDomainList
));
1037 cloog_set_domain (next
, cloog_domain_read (foo
));
1038 cloog_set_next_domain (next
, NULL
);
1039 cloog_set_next_domain (now
, next
);
1040 now
= cloog_next_domain (now
);
1047 /******************************************************************************
1048 * Processing functions *
1049 ******************************************************************************/
1052 * cloog_domain_isempty function:
1053 * This function returns 1 if the polyhedron given as input is empty, 0
1055 * - October 28th 2001: first version.
1058 cloog_domain_isempty (CloogDomain
* domain
)
1060 if (cloog_domain_polyhedron (domain
) == NULL
)
1063 if (cloog_domain_polyhedron_next (domain
))
1066 return ((cloog_domain_dim (domain
) < cloog_domain_nbeq (domain
)) ? 1 : 0);
1071 * cloog_domain_project function:
1072 * From Quillere's LoopGen 0.4. This function returns the projection of
1073 * (domain) on the (level) first dimensions (i.e. outer loops). It returns a
1074 * pointer to the projected Polyhedron.
1075 * - nb_par is the number of parameters.
1077 * - October 27th 2001: first version.
1078 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1082 cloog_domain_project (CloogDomain
* domain
, int level
, int nb_par
)
1084 int row
, column
, nb_rows
, nb_columns
, difference
;
1085 CloogDomain
*projected_domain
;
1086 CloogMatrix
*matrix
;
1088 nb_rows
= level
+ nb_par
+ 1;
1089 nb_columns
= cloog_domain_dim (domain
) + 1;
1090 difference
= nb_columns
- nb_rows
;
1092 if (difference
== 0)
1093 return (cloog_domain_copy (domain
));
1095 matrix
= cloog_matrix_alloc (nb_rows
, nb_columns
);
1097 for (row
= 0; row
< level
; row
++)
1098 for (column
= 0; column
< nb_columns
; column
++)
1099 value_set_si (matrix
->p
[row
][column
], (row
== column
? 1 : 0));
1101 for (; row
< nb_rows
; row
++)
1102 for (column
= 0; column
< nb_columns
; column
++)
1103 value_set_si (matrix
->p
[row
][column
],
1104 (row
+ difference
== column
? 1 : 0));
1106 projected_domain
= cloog_domain_image (domain
, matrix
);
1107 cloog_matrix_free (matrix
);
1109 return (projected_domain
);
1113 * cloog_domain_extend function:
1114 * From Quillere's LoopGen 0.4. This function returns the (domain) given as
1115 * input with (dim)+(nb_par) dimensions. The new dimensions are added before
1116 * the (nb_par) parameters. This function does not free (domain), and returns
1118 * - nb_par is the number of parameters.
1120 * - October 27th 2001: first version.
1121 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1125 cloog_domain_extend (CloogDomain
* domain
, int dim
, int nb_par
)
1127 int row
, column
, nb_rows
, nb_columns
, difference
;
1128 CloogDomain
*extended_domain
;
1129 CloogMatrix
*matrix
;
1131 nb_rows
= 1 + cloog_domain_dim (domain
);
1132 nb_columns
= dim
+ nb_par
+ 1;
1133 difference
= nb_columns
- nb_rows
;
1135 if (difference
== 0)
1136 return (cloog_domain_copy (domain
));
1138 matrix
= cloog_matrix_alloc (nb_rows
, nb_columns
);
1140 for (row
= 0; row
< cloog_domain_dim (domain
) - nb_par
; row
++)
1141 for (column
= 0; column
< nb_columns
; column
++)
1142 value_set_si (matrix
->p
[row
][column
], (row
== column
? 1 : 0));
1144 for (; row
<= cloog_domain_dim (domain
); row
++)
1145 for (column
= 0; column
< nb_columns
; column
++)
1146 value_set_si (matrix
->p
[row
][column
],
1147 (row
+ difference
== column
? 1 : 0));
1149 extended_domain
= cloog_domain_preimage (domain
, matrix
);
1150 cloog_matrix_free (matrix
);
1152 return (extended_domain
);
1157 * cloog_domain_never_integral function:
1158 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0. This
1159 * function returns a boolean set to 1 if there is this kind of 'never true'
1160 * constraint inside a polyhedron, 0 otherwise.
1161 * - domain is the polyhedron to check,
1163 * - November 28th 2001: first version.
1164 * - June 26th 2003: for iterators, more 'never true' constraints are found
1165 * (compare cholesky2 and vivien with a previous version),
1166 * checking for the parameters created (compare using vivien).
1167 * - June 28th 2003: Previously in loop.c and called
1168 * cloog_loop_simplify_nevertrue, now here !
1169 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1171 * - October 14th 2005: Complete rewriting, not faster but code quite shorter.
1174 cloog_domain_never_integral (CloogDomain
* domain
)
1178 Polyhedron
*polyhedron
;
1180 if ((domain
== NULL
) || (cloog_domain_polyhedron (domain
) == NULL
))
1184 value_init_c (modulo
);
1185 polyhedron
= cloog_domain_polyhedron (domain
);
1186 dimension
= cloog_domain_dim (domain
) + 2;
1188 /* For each constraint... */
1189 for (i
= 0; i
< cloog_polyhedron_nbc (polyhedron
); i
++)
1190 { /* If we have an equality and the scalar part is not zero... */
1191 if (value_zero_p (polyhedron
->Constraint
[i
][0]) &&
1192 value_notzero_p (polyhedron
->Constraint
[i
][dimension
- 1]))
1193 { /* Then we check whether the scalar can be divided by the gcd of the
1194 * unknown vector (including iterators and parameters) or not. If not,
1195 * there is no integer point in the polyhedron and we return 1.
1197 Vector_Gcd (&(polyhedron
->Constraint
[i
][1]), dimension
- 2, &gcd
);
1198 value_modulus (modulo
,
1199 polyhedron
->Constraint
[i
][dimension
- 1],
1202 if (value_notzero_p (modulo
))
1204 value_clear_c (gcd
);
1205 value_clear_c (modulo
);
1211 value_clear_c (gcd
);
1212 value_clear_c (modulo
);
1218 * cloog_domain_stride function:
1219 * This function finds the stride imposed to unknown with the column number
1220 * 'strided_level' in order to be integral. For instance, if we have a
1221 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
1222 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
1223 * the unknown i. The function returns the imposed stride in a parameter field.
1224 * - domain is the set of constraint we have to consider,
1225 * - strided_level is the column number of the unknown for which a stride have
1227 * - looking_level is the column number of the unknown that impose a stride to
1228 * the first unknown.
1229 * - stride is the stride that is returned back as a function parameter.
1230 * - offset is the value of the constant c if the condition is of the shape
1231 * (i + c)%s = 0, s being the stride.
1233 * - June 28th 2003: first version.
1234 * - July 14th 2003: can now look for multiple striding constraints and returns
1235 * the GCD of the strides and the common offset.
1236 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1240 cloog_domain_stride (domain
, strided_level
, nb_par
, stride
, offset
)
1241 CloogDomain
*domain
;
1242 int strided_level
, nb_par
;
1243 Value
*stride
, *offset
;
1246 Polyhedron
*polyhedron
;
1247 int n_col
, n_row
, rank
;
1252 polyhedron
= cloog_domain_polyhedron (domain
);
1253 dimension
= cloog_domain_dim (domain
);
1255 /* Look at all equalities involving strided_level and the inner
1256 * iterators. We can ignore the outer iterators and the parameters
1257 * here because the lower bound on strided_level is assumed to
1260 n_col
= (1 + dimension
- nb_par
) - strided_level
;
1261 for (i
= 0, n_row
= 0; i
< cloog_polyhedron_nbeq (polyhedron
); i
++)
1263 (polyhedron
->Constraint
[i
] + strided_level
, n_col
) != -1)
1266 M
= cloog_matrix_alloc (n_row
+ 1, n_col
+ 1);
1267 for (i
= 0, n_row
= 0; i
< cloog_polyhedron_nbeq (polyhedron
); i
++)
1270 (polyhedron
->Constraint
[i
] + strided_level
, n_col
) == -1)
1272 Vector_Copy (polyhedron
->Constraint
[i
] + strided_level
,
1273 M
->p
[n_row
], n_col
);
1274 value_assign (M
->p
[n_row
][n_col
],
1275 polyhedron
->Constraint
[i
][1 + dimension
]);
1278 value_set_si (M
->p
[n_row
][n_col
], 1);
1280 /* Then look at the general solution to the above equalities. */
1281 rank
= SolveDiophantine (M
, &U
, &V
);
1282 cloog_matrix_free (M
);
1286 /* There is no solution, so the body of this loop will
1287 * never execute. We just leave the constraints alone here so
1288 * that they will ensure the body will not be executed.
1289 * We should probably propagate this information up so that
1290 * the loop can be removed entirely.
1292 value_set_si (*offset
, 0);
1293 value_set_si (*stride
, 1);
1297 /* Compute the gcd of the coefficients defining strided_level. */
1298 Vector_Gcd (U
->p
[0], U
->NbColumns
, stride
);
1299 value_oppose (*offset
, V
->p
[0]);
1300 value_pmodulus (*offset
, *offset
, *stride
);
1310 * cloog_domain_integral_lowerbound function:
1311 * This function returns 1 if the lower bound of an iterator (such as its
1312 * column rank in the constraint set 'domain' is 'level') is integral,
1313 * 0 otherwise. If the lower bound is actually integral, the function fills
1314 * the 'lower' field with the lower bound value.
1315 * - June 29th 2003: first version.
1316 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1320 cloog_domain_integral_lowerbound (domain
, level
, lower
)
1321 CloogDomain
*domain
;
1325 int i
, first_lower
= 1, dimension
, lower_constraint
= -1;
1326 Value iterator
, constant
, tmp
;
1327 Polyhedron
*polyhedron
;
1329 polyhedron
= cloog_domain_polyhedron (domain
);
1330 dimension
= cloog_domain_dim (domain
);
1332 /* We want one and only one lower bound (e.g. no equality, no maximum
1335 for (i
= 0; i
< cloog_polyhedron_nbc (polyhedron
); i
++)
1336 if (value_zero_p (polyhedron
->Constraint
[i
][0])
1337 && value_notzero_p (polyhedron
->Constraint
[i
][level
]))
1340 for (i
= 0; i
< cloog_polyhedron_nbc (polyhedron
); i
++)
1341 if (value_pos_p (polyhedron
->Constraint
[i
][level
]))
1346 lower_constraint
= i
;
1355 /* We want an integral lower bound: no other non-zero entry except the
1356 * iterator coefficient and the constant.
1358 for (i
= 1; i
< level
; i
++)
1360 (polyhedron
->Constraint
[lower_constraint
][i
]))
1363 for (i
= level
+ 1; i
<= cloog_polyhedron_dim (polyhedron
); i
++)
1365 (polyhedron
->Constraint
[lower_constraint
][i
]))
1368 value_init_c (iterator
);
1369 value_init_c (constant
);
1372 /* If all is passed, then find the lower bound and return 1. */
1373 value_assign (iterator
,
1374 polyhedron
->Constraint
[lower_constraint
][level
]);
1375 value_oppose (constant
,
1376 polyhedron
->Constraint
[lower_constraint
][dimension
+ 1]);
1378 value_modulus (tmp
, constant
, iterator
);
1379 value_division (*lower
, constant
, iterator
);
1381 if (!(value_zero_p (tmp
) || value_neg_p (constant
)))
1382 value_increment (*lower
, *lower
);
1384 value_clear_c (iterator
);
1385 value_clear_c (constant
);
1386 value_clear_c (tmp
);
1393 * cloog_domain_lowerbound_update function:
1394 * This function updates the integral lower bound of an iterator (such as its
1395 * column rank in the constraint set 'domain' is 'level') into 'lower'.
1396 * - Jun 29th 2003: first version.
1397 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1401 cloog_domain_lowerbound_update (domain
, level
, lower
)
1402 CloogDomain
*domain
;
1407 Polyhedron
*polyhedron
;
1409 polyhedron
= cloog_domain_polyhedron (domain
);
1411 /* There is only one lower bound, the first one is the good one. */
1412 for (i
= 0; i
< cloog_polyhedron_nbc (polyhedron
); i
++)
1413 if (value_pos_p (polyhedron
->Constraint
[i
][level
]))
1415 value_set_si (polyhedron
->Constraint
[i
][level
], 1);
1416 value_oppose (polyhedron
->Constraint
[i
][cloog_polyhedron_dim (polyhedron
) + 1], lower
);
1423 * cloog_domain_lazy_equal function:
1424 * This function returns 1 if the domains given as input are the same, 0 if it
1425 * is unable to decide. This function makes an entry-to-entry comparison between
1426 * the constraint systems, if all the entries are the same, the domains are
1427 * obviously the same and it returns 1, at the first difference, it returns 0.
1428 * This is a very fast way to verify this property. It has been shown (with the
1429 * CLooG benchmarks) that operations on equal domains are 17% of all the
1430 * polyhedral computations. For 75% of the actually identical domains, this
1431 * function answer that they are the same and allow to give immediately the
1432 * trivial solution instead of calling the heavy general functions of PolyLib.
1433 * - August 22th 2003: first version.
1434 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1438 cloog_domain_lazy_equal (CloogDomain
* d1
, CloogDomain
* d2
)
1441 Polyhedron
*p1
, *p2
;
1443 p1
= cloog_domain_polyhedron (d1
);
1444 p2
= cloog_domain_polyhedron (d2
);
1446 while ((p1
!= NULL
) && (p2
!= NULL
))
1448 if ((cloog_polyhedron_nbc (p1
) != cloog_polyhedron_nbc (p2
)) ||
1449 (cloog_polyhedron_dim (p1
) != cloog_polyhedron_dim (p2
)))
1453 cloog_polyhedron_nbc (p1
) * (cloog_polyhedron_dim (p1
) + 2);
1455 for (i
= 0; i
< nb_elements
; i
++)
1456 if (value_ne (p1
->p_Init
[i
], p2
->p_Init
[i
]))
1459 p1
= cloog_polyhedron_next (p1
);
1460 p2
= cloog_polyhedron_next (p2
);
1463 if ((p1
!= NULL
) || (p2
!= NULL
))
1471 * cloog_domain_lazy_block function:
1472 * This function returns 1 if the two domains d1 and d2 given as input are the
1473 * same (possibly except for a dimension equal to a constant where we accept
1474 * a difference of 1) AND if we are sure that there are no other domain in
1475 * the code generation problem that may put integral points between those of
1476 * d1 and d2 (0 otherwise). In fact this function answers the question "can I
1477 * safely consider the two domains as only one with two statements (a block) ?".
1478 * This function is lazy: it asks for very standard scattering representation
1479 * (only one constraint per dimension which is an equality, and the constraints
1480 * are ordered per dimension depth: the left hand side of the constraint matrix
1481 * is the identity) and will answer NO at the very first problem.
1482 * - d1 and d2 are the two domains to check for blocking,
1483 * - scattering is the linked list of all domains,
1484 * - scattdims is the total number of scattering dimentions.
1486 * - April 30th 2005: beginning
1487 * - June 9th 2005: first working version.
1488 * - June 10th 2005: debugging.
1489 * - June 21rd 2005: Adaptation for GMP.
1490 * - October 16th 2005: (debug) some false blocks have been removed.
1493 cloog_domain_lazy_block (d1
, d2
, scattering
, scattdims
)
1494 CloogDomain
*d1
, *d2
;
1495 CloogDomainList
*scattering
;
1498 int i
, j
, difference
= 0, different_constraint
= 0;
1499 Value date1
, date2
, date3
, temp
;
1500 Polyhedron
*p1
, *p2
, *p3
;
1502 p1
= cloog_domain_polyhedron (d1
);
1503 p2
= cloog_domain_polyhedron (d2
);
1505 /* Some basic checks: we only accept convex domains, with same constraint
1506 * and dimension numbers.
1508 if (cloog_polyhedron_next (p1
) || cloog_polyhedron_next (p2
) ||
1509 (cloog_polyhedron_nbc (p1
) != cloog_polyhedron_nbc (p2
)) ||
1510 (cloog_polyhedron_dim (p1
) != cloog_polyhedron_dim (p2
)))
1513 /* There should be only one difference between the two domains, it
1514 * has to be at the constant level and the difference must be of +1,
1515 * moreover, after the difference all domain coefficient has to be 0.
1516 * The matrix shape is:
1518 * |===========|=====|<- 0 line
1519 * |===========|=====|
1520 * |===========|====?|<- different_constraint line (found here)
1521 * |===========|0000=|
1522 * |===========|0000=|<- pX->NbConstraints line
1525 * | | (pX->Dimension + 2) column
1526 * | scattdims column
1530 value_init_c (temp
);
1531 for (i
= 0; i
< cloog_polyhedron_nbc (p1
); i
++)
1533 if (difference
== 0)
1534 { /* All elements except scalar must be equal. */
1535 for (j
= 0; j
< (cloog_polyhedron_dim (p1
) + 1); j
++)
1536 if (value_ne (p1
->Constraint
[i
][j
],
1537 p2
->Constraint
[i
][j
]))
1539 value_clear_c (temp
);
1542 /* The scalar may differ from +1 (now j=(p1->Dimension + 1)). */
1543 if (value_ne (p1
->Constraint
[i
][j
],
1544 p2
->Constraint
[i
][j
]))
1546 value_increment (temp
, p2
->Constraint
[i
][j
]);
1547 if (value_ne (p1
->Constraint
[i
][j
], temp
))
1549 value_clear_c (temp
);
1555 different_constraint
= i
;
1560 { /* Scattering coefficients must be equal. */
1561 for (j
= 0; j
< (scattdims
+ 1); j
++)
1562 if (value_ne (p1
->Constraint
[i
][j
],
1563 p2
->Constraint
[i
][j
]))
1565 value_clear_c (temp
);
1569 /* Domain coefficients must be 0. */
1570 for (; j
< (cloog_polyhedron_dim (p1
) + 1); j
++)
1571 if (value_notzero_p (p1
->Constraint
[i
][j
])
1572 || value_notzero_p (p2
->Constraint
[i
][j
]))
1574 value_clear_c (temp
);
1578 /* Scalar must be equal. */
1579 if (value_ne (p1
->Constraint
[i
][j
],
1580 p2
->Constraint
[i
][j
]))
1582 value_clear_c (temp
);
1587 value_clear_c (temp
);
1589 /* If the domains are exactly the same, this is a block. */
1590 if (difference
== 0)
1593 /* Now a basic check that the constraint with the difference is an
1594 * equality of a dimension with a constant.
1596 for (i
= 0; i
<= different_constraint
; i
++)
1597 if (value_notzero_p (p1
->Constraint
[different_constraint
][i
]))
1600 if (value_notone_p (p1
->Constraint
[different_constraint
][different_constraint
+ 1]))
1603 for (i
= different_constraint
+ 2; i
< (cloog_polyhedron_dim (p1
) + 1); i
++)
1604 if (value_notzero_p (p1
->Constraint
[different_constraint
][i
]))
1607 /* For the moment, d1 and d2 are a block candidate. There remains to check
1608 * that there is no other domain that may put an integral point between
1609 * them. In our lazy test we ensure this property by verifying that the
1610 * constraint matrices have a very strict shape: let us consider that the
1611 * dimension with the difference is d. Then the first d dimensions are
1612 * defined in their depth order using equalities (thus the first column begins
1613 * with d zeroes, there is a d*d identity matrix and a zero-matrix for
1614 * the remaining simensions). If a domain can put integral points between the
1615 * domains of the block candidate, this means that the other entries on the
1616 * first d constraints are equal to those of d1 or d2. Thus we are looking for
1617 * such a constraint system, if it exists d1 and d2 is considered to not be
1618 * a block, it is a bock otherwise.
1620 * 1. Only equalities (for the first different_constraint+1 lines).
1621 * | 2. Must be the identity.
1622 * | | 3. Must be zero.
1623 * | | | 4. Elements are equal, the last one is either date1 or 2.
1626 * |0|100|00000|=====|<- 0 line
1627 * |0|010|00000|=====|
1628 * |0|001|00000|====?|<- different_constraint line
1629 * |*|***|*****|*****|
1630 * |*|***|*****|*****|<- pX->NbConstraints line
1633 * | | | (pX->Dimension + 2) column
1634 * | | scattdims column
1635 * | different_constraint+1 column
1639 /* Step 1 and 2. This is only necessary to check one domain because
1640 * we checked that they are equal on this part before.
1642 for (i
= 0; i
<= different_constraint
; i
++)
1644 for (j
= 0; j
< i
+ 1; j
++)
1645 if (value_notzero_p (p1
->Constraint
[i
][j
]))
1648 if (value_notone_p (p1
->Constraint
[i
][i
+ 1]))
1651 for (j
= i
+ 2; j
<= different_constraint
+ 1; j
++)
1652 if (value_notzero_p (p1
->Constraint
[i
][j
]))
1657 for (i
= 0; i
<= different_constraint
; i
++)
1658 for (j
= different_constraint
+ 2; j
<= scattdims
; j
++)
1659 if (value_notzero_p (p1
->Constraint
[i
][j
]))
1662 value_init_c (date1
);
1663 value_init_c (date2
);
1664 value_init_c (date3
);
1666 /* Now we have to check that the two different dates are unique. */
1667 value_assign (date1
, p1
->Constraint
[different_constraint
][cloog_polyhedron_dim (p1
) + 1]);
1668 value_assign (date2
, p2
->Constraint
[different_constraint
][cloog_polyhedron_dim (p2
) + 1]);
1670 /* Step 4. We check all domains except d1 and d2 and we look for at least
1671 * a difference with d1 or d2 on the first different_constraint+1 dimensions.
1673 while (scattering
!= NULL
)
1675 if ((cloog_domain (scattering
) != d1
)
1676 && (cloog_domain (scattering
) != d2
))
1678 p3
= cloog_domain_polyhedron (cloog_domain (scattering
));
1679 value_assign (date3
,
1680 p3
->Constraint
[different_constraint
][cloog_polyhedron_dim (p3
) + 1]);
1683 if (value_ne (date3
, date2
) && value_ne (date3
, date1
))
1686 for (i
= 0; (i
< different_constraint
) && (!difference
); i
++)
1688 (j
< (cloog_polyhedron_dim (p3
) + 2)) && (!difference
); j
++)
1690 (p1
->Constraint
[i
][j
],
1691 p3
->Constraint
[i
][j
]))
1694 for (j
= 0; (j
< (cloog_polyhedron_dim (p3
) + 1)) && (!difference
);
1697 (p1
->Constraint
[different_constraint
][j
],
1698 p3
->Constraint
[different_constraint
][j
]))
1703 value_clear_c (date1
);
1704 value_clear_c (date2
);
1705 value_clear_c (date3
);
1710 scattering
= cloog_next_domain (scattering
);
1713 value_clear_c (date1
);
1714 value_clear_c (date2
);
1715 value_clear_c (date3
);
1721 * cloog_domain_lazy_disjoint function:
1722 * This function returns 1 if the domains given as input are disjoint, 0 if it
1723 * is unable to decide. This function finds the unknown with fixed values in
1724 * both domains (on a given constraint, their column entry is not zero and
1725 * only the constant coefficient can be different from zero) and verify that
1726 * their values are the same. If not, the domains are obviously disjoint and
1727 * it returns 1, if there is not such case it returns 0. This is a very fast
1728 * way to verify this property. It has been shown (with the CLooG benchmarks)
1729 * that operations on disjoint domains are 36% of all the polyhedral
1730 * computations. For 94% of the actually identical domains, this
1731 * function answer that they are disjoint and allow to give immediately the
1732 * trivial solution instead of calling the heavy general functions of PolyLib.
1733 * - August 22th 2003: first version.
1734 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1738 cloog_domain_lazy_disjoint (CloogDomain
* d1
, CloogDomain
* d2
)
1740 int i1
, j1
, i2
, j2
, scat_dim
;
1742 Polyhedron
*p1
, *p2
;
1744 p1
= cloog_domain_polyhedron (d1
);
1745 p2
= cloog_domain_polyhedron (d2
);
1747 if (cloog_polyhedron_next (p1
) || cloog_polyhedron_next (p2
))
1750 value_init_c (scat_val
);
1752 for (i1
= 0; i1
< cloog_polyhedron_nbc (p1
); i1
++)
1754 if (value_notzero_p (p1
->Constraint
[i1
][0]))
1758 while (value_zero_p (p1
->Constraint
[i1
][scat_dim
]) &&
1759 (scat_dim
< cloog_polyhedron_dim (p1
)))
1762 if (value_notone_p (p1
->Constraint
[i1
][scat_dim
]))
1766 for (j1
= scat_dim
+ 1; j1
<= cloog_polyhedron_dim (p1
); j1
++)
1767 if (value_notzero_p (p1
->Constraint
[i1
][j1
]))
1770 if (j1
!= cloog_polyhedron_dim (p1
) + 1)
1773 value_assign (scat_val
,
1774 p1
->Constraint
[i1
][cloog_polyhedron_dim (p1
) + 1]);
1776 for (i2
= 0; i2
< cloog_polyhedron_nbc (p2
); i2
++)
1778 for (j2
= 0; j2
< scat_dim
; j2
++)
1779 if (value_notzero_p (p2
->Constraint
[i2
][j2
]))
1782 if ((j2
!= scat_dim
)
1784 value_notone_p (p2
->Constraint
[i2
][scat_dim
]))
1787 for (j2
= scat_dim
+ 1; j2
< cloog_polyhedron_dim (p2
); j2
++)
1788 if (value_notzero_p (p2
->Constraint
[i2
][j2
]))
1791 if (j2
!= cloog_polyhedron_dim (p2
))
1795 (p2
->Constraint
[i2
][cloog_polyhedron_dim (p2
) + 1], scat_val
))
1797 value_clear_c (scat_val
);
1804 value_clear_c (scat_val
);
1810 * cloog_domain_list_lazy_same function:
1811 * This function returns 1 if two domains in the list are the same, 0 if it
1812 * is unable to decide.
1813 * - February 9th 2004: first version.
1816 cloog_domain_list_lazy_same (CloogDomainList
* list
)
1817 { /*int i=1, j=1 ; */
1818 CloogDomainList
*current
, *next
;
1821 while (current
!= NULL
)
1823 next
= cloog_next_domain (current
);
1825 while (next
!= NULL
)
1827 if (cloog_domain_lazy_equal (cloog_domain (current
),
1828 cloog_domain (next
)))
1829 { /*printf("Same domains: %d and %d\n",i,j) ; */
1833 next
= cloog_next_domain (next
);
1836 current
= cloog_next_domain (current
);
1843 * cloog_domain_cut_first function:
1844 * this function returns a CloogDomain structure with everything except the
1845 * first part of the polyhedra union of the input domain as domain. After a call
1846 * to this function, there remains in the CloogDomain structure provided as
1847 * input only the first part of the original polyhedra union.
1848 * - April 20th 2005: first version, extracted from different part of loop.c.
1851 cloog_domain_cut_first (CloogDomain
* domain
)
1855 if ((domain
!= NULL
) && (cloog_domain_polyhedron (domain
) != NULL
))
1857 rest
= cloog_domain_alloc (cloog_domain_polyhedron_next (domain
));
1858 cloog_domain_polyhedron_set_next (domain
, NULL
);
1868 * cloog_domain_lazy_isscalar function:
1869 * this function returns 1 if the dimension 'dimension' in the domain 'domain'
1870 * is scalar, this means that the only constraint on this dimension must have
1871 * the shape "x.dimension + scalar = 0" with x an integral variable. This
1872 * function is lazy since we only accept x=1 (further calculations are easier
1874 * - June 14th 2005: first version.
1875 * - June 21rd 2005: Adaptation for GMP.
1878 cloog_domain_lazy_isscalar (CloogDomain
* domain
, int dimension
)
1881 Polyhedron
*polyhedron
;
1883 polyhedron
= cloog_domain_polyhedron (domain
);
1884 /* For each constraint... */
1885 for (i
= 0; i
< cloog_polyhedron_nbc (polyhedron
); i
++)
1886 { /* ...if it is concerned by the potentially scalar dimension... */
1888 (polyhedron
->Constraint
[i
][dimension
+ 1]))
1889 { /* ...check that the constraint has the shape "dimension + scalar = 0". */
1890 for (j
= 0; j
<= dimension
; j
++)
1891 if (value_notzero_p (polyhedron
->Constraint
[i
][j
]))
1895 (polyhedron
->Constraint
[i
][dimension
+ 1]))
1898 for (j
= dimension
+ 2; j
< (cloog_polyhedron_dim (polyhedron
) + 1);
1900 if (value_notzero_p (polyhedron
->Constraint
[i
][j
]))
1910 * cloog_domain_scalar function:
1911 * when we call this function, we know that "dimension" is a scalar dimension,
1912 * this function finds the scalar value in "domain" and returns it in "value".
1913 * - June 30th 2005: first version.
1916 cloog_domain_scalar (CloogDomain
* domain
, int dimension
, Value
* value
)
1919 Polyhedron
*polyhedron
;
1921 polyhedron
= cloog_domain_polyhedron (domain
);
1922 /* For each constraint... */
1923 for (i
= 0; i
< cloog_polyhedron_nbc (polyhedron
); i
++)
1924 { /* ...if it is the equality defining the scalar dimension... */
1926 (polyhedron
->Constraint
[i
][dimension
+ 1])
1927 && value_zero_p (polyhedron
->Constraint
[i
][0]))
1928 { /* ...Then send the scalar value. */
1929 value_assign (*value
, polyhedron
->Constraint
[i
][cloog_polyhedron_dim (polyhedron
) + 1]);
1930 value_oppose (*value
, *value
);
1935 /* We should have found a scalar value: if not, there is an error. */
1936 fprintf (stderr
, "[CLooG]ERROR: dimension %d is not scalar as expected.\n",
1943 * cloog_domain_erase_dimension function:
1944 * this function returns a CloogDomain structure builds from 'domain' where
1945 * we removed the dimension 'dimension' and every constraint considering this
1946 * dimension. This is not a projection ! Every data concerning the
1947 * considered dimension is simply erased.
1948 * - June 14th 2005: first version.
1949 * - June 21rd 2005: Adaptation for GMP.
1952 cloog_domain_erase_dimension (CloogDomain
* domain
, int dimension
)
1954 int i
, j
, mi
, nb_dim
;
1955 CloogMatrix
*matrix
;
1956 CloogDomain
*erased
;
1957 Polyhedron
*polyhedron
;
1959 polyhedron
= cloog_domain_polyhedron (domain
);
1960 nb_dim
= cloog_domain_dim (domain
);
1962 /* The matrix is one column less and at least one constraint less. */
1964 cloog_matrix_alloc (cloog_polyhedron_nbc (polyhedron
) - 1, nb_dim
+ 1);
1966 /* mi is the constraint counter for the matrix. */
1968 for (i
= 0; i
< cloog_polyhedron_nbc (polyhedron
); i
++)
1969 if (value_zero_p (polyhedron
->Constraint
[i
][dimension
+ 1]))
1971 for (j
= 0; j
<= dimension
; j
++)
1972 value_assign (matrix
->p
[mi
][j
],
1973 polyhedron
->Constraint
[i
][j
]);
1975 for (j
= dimension
+ 2; j
< nb_dim
+ 2; j
++)
1976 value_assign (matrix
->p
[mi
][j
- 1],
1977 polyhedron
->Constraint
[i
][j
]);
1982 erased
= cloog_domain_matrix2domain (matrix
);
1983 cloog_matrix_free (matrix
);
1988 /* Number of polyhedra inside the union of disjoint polyhedra. */
1991 cloog_domain_nb_polyhedra (CloogDomain
* domain
)
1994 Polyhedron
*polyhedron
= cloog_domain_polyhedron (domain
);
1996 while (polyhedron
!= NULL
)
1999 polyhedron
= polyhedron
->next
;
2006 cloog_domain_print_polyhedra (FILE * foo
, CloogDomain
* domain
)
2008 Polyhedron
*polyhedron
= cloog_domain_polyhedron (domain
);
2010 while (polyhedron
!= NULL
)
2012 CloogMatrix
*matrix
;
2013 matrix
= Polyhedron2Constraints (polyhedron
);
2014 cloog_matrix_print (foo
, matrix
);
2015 cloog_matrix_free (matrix
);
2016 polyhedron
= polyhedron
->next
;