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 * The maximal number of rays allowed to be allocated by PolyLib. In fact since
48 * version 5.20, PolyLib automatically tune the number of rays by multiplying
49 * by 2 this number each time the maximum is reached. For unknown reasons
50 * PolyLib makes a segmentation fault if this number is too small. If this
51 * number is too small, performances will be reduced, if it is too high, memory
52 * will be saturated. Note that the option "-rays X" set this number to X.
57 /******************************************************************************
58 * Memory leaks hunting *
59 ******************************************************************************/
63 * These functions and global variables are devoted to memory leaks hunting: we
64 * want to know at each moment how many Polyhedron structures had been allocated
65 * (cloog_domain_allocated) and how many had been freed (cloog_domain_freed).
66 * Each time a Polyhedron structure is allocated, a call to the function
67 * cloog_domain_leak_up() must be carried out, and respectively
68 * cloog_domain_leak_down() when a Polyhedron structure is freed. The special
69 * variable cloog_domain_max gives the maximal number of Polyhedron structures
70 * simultaneously alive (i.e. allocated and non-freed) in memory.
71 * - July 3rd->11th 2003: first version (memory leaks hunt and correction).
75 int cloog_domain_allocated
= 0 ;
76 int cloog_domain_freed
= 0 ;
77 int cloog_domain_max
= 0 ;
80 static void cloog_domain_leak_up()
81 { cloog_domain_allocated
++ ;
82 if ((cloog_domain_allocated
-cloog_domain_freed
) > cloog_domain_max
)
83 cloog_domain_max
= cloog_domain_allocated
- cloog_domain_freed
;
87 static void cloog_domain_leak_down()
88 { cloog_domain_freed
++ ;
92 /* The same for Value variables since in GMP mode they have to be freed. */
93 int cloog_value_allocated
= 0 ;
94 int cloog_value_freed
= 0 ;
95 int cloog_value_max
= 0 ;
98 void cloog_value_leak_up()
99 { cloog_value_allocated
++ ;
100 if ((cloog_value_allocated
-cloog_value_freed
) > cloog_value_max
)
101 cloog_value_max
= cloog_value_allocated
- cloog_value_freed
;
105 void cloog_value_leak_down()
106 { cloog_value_freed
++ ;
110 /******************************************************************************
111 * PolyLib interface *
112 ******************************************************************************/
115 /* CLooG makes an intensive use of polyhedral operations and the PolyLib do
116 * the job. Here are the interfaces to all the PolyLib calls (CLooG uses 19
117 * PolyLib functions), with or without some adaptations. If another polyhedral
118 * library can be used, only these functions have to be changed.
119 * - April 16th 2005: Since PolyLib 5.20, compacting is no more useful and have
120 * been removed. The direct use of the PolyLib's Polyhedron
121 * data structure is also replaced with the CloogDomain data
122 * structure that includes the Polyhedron and an additional
123 * counter on how many pointers point on this structure.
124 * This allows to save memory (cloog_domain_copy now only
125 * increment the counter) while memory leaks are avoided (the
126 * function cloog_domain_free decrements the counter and
127 * actually frees the data structure only when its value
133 * cloog_domain_matrix2domain function:
134 * Given a matrix of constraints (matrix), this function constructs and returns
135 * the corresponding domain (i.e. the CloogDomain structure including the
136 * polyhedron with its double representation: constraint matrix and the set of
139 static CloogDomain
* cloog_domain_matrix2domain(CloogMatrix
* matrix
)
140 { return (cloog_domain_alloc(Constraints2Polyhedron(matrix
,MAX_RAYS
))) ;
145 * cloog_domain_domain2matrix function:
146 * Given a polyhedron (in domain), this function returns its corresponding
147 * matrix of constraints.
149 static CloogMatrix
* cloog_domain_domain2matrix(CloogDomain
* domain
)
151 return cloog_matrix_matrix(Polyhedron2Constraints(domain
->polyhedron
));
156 * cloog_domain_print function:
157 * This function prints the content of a CloogDomain structure (domain) into
158 * a file (foo, possibly stdout).
160 void cloog_domain_print(FILE * foo
, CloogDomain
* domain
)
161 { Polyhedron_Print(foo
,P_VALUE_FMT
,domain
->polyhedron
) ;
162 fprintf(foo
,"Number of active references: %d\n",domain
->references
) ;
167 * cloog_polyhedron_print function:
168 * This function prints the content of a Polyhedron structure (polyhedron) into
169 * a file (foo, possibly stdout). Just there as a development facility.
171 void cloog_polyhedron_print(FILE * foo
, Polyhedron
* polyhedron
)
172 { Polyhedron_Print(foo
,P_VALUE_FMT
,polyhedron
) ;
177 * cloog_domain_free function:
178 * This function frees the allocated memory for a CloogDomain structure
179 * (domain). It decrements the number of active references to this structure,
180 * if there are no more references on the structure, it frees it (with the
181 * included list of polyhedra).
183 void cloog_domain_free(CloogDomain
* domain
)
184 { if (domain
!= NULL
)
185 { domain
->references
-- ;
187 if (domain
->references
== 0)
188 { if (domain
->polyhedron
!= NULL
)
189 { cloog_domain_leak_down() ;
190 Domain_Free(domain
->polyhedron
) ;
199 * cloog_domain_copy function:
200 * This function returns a copy of a CloogDomain structure (domain). To save
201 * memory this is not a memory copy but we increment a counter of active
202 * references inside the structure, then return a pointer to that structure.
204 CloogDomain
* cloog_domain_copy(CloogDomain
* domain
)
205 { domain
->references
++ ;
211 * cloog_domain_image function:
212 * This function returns a CloogDomain structure such that the included
213 * polyhedral domain is computed from the former one into another
214 * domain according to a given affine mapping function (mapping).
216 CloogDomain
* cloog_domain_image(CloogDomain
* domain
, CloogMatrix
* mapping
)
217 { return (cloog_domain_alloc(DomainImage(domain
->polyhedron
,mapping
,MAX_RAYS
)));
222 * cloog_domain_preimage function:
223 * Given a polyhedral domain (polyhedron) inside a CloogDomain structure and a
224 * mapping function (mapping), this function returns a new CloogDomain structure
225 * with a polyhedral domain which when transformed by mapping function (mapping)
226 * gives (polyhedron).
228 CloogDomain
* cloog_domain_preimage(CloogDomain
* domain
, CloogMatrix
* mapping
)
229 { return (cloog_domain_alloc(DomainPreimage(domain
->polyhedron
,
230 mapping
,MAX_RAYS
))) ;
235 * cloog_domain_convex function:
236 * Given a polyhedral domain (polyhedron), this function concatenates the lists
237 * of rays and lines of the two (or more) polyhedra in the domain into one
238 * combined list, and find the set of constraints which tightly bound all of
239 * those objects. It returns the corresponding polyhedron.
241 CloogDomain
* cloog_domain_convex(CloogDomain
* domain
)
242 { return (cloog_domain_alloc(DomainConvex(domain
->polyhedron
,MAX_RAYS
)));
247 * cloog_domain_simplified_hull:
248 * Given a list (union) of polyhedra, this function returns a single
249 * polyhedron that contains this union and uses only contraints that
250 * appear in one or more of the polyhedra in the list.
252 * We simply iterate over all constraints of all polyhedra and test
253 * whether all rays of the other polyhedra satisfy/saturate the constraint.
255 static CloogDomain
*cloog_domain_simplified_hull(CloogDomain
* domain
)
257 int dim
= cloog_domain_dimension(domain
);
259 int nb_pol
= 0, nb_constraints
= 0;
261 CloogMatrix
**rays
, *matrix
;
266 for (P
= domain
->polyhedron
; P
; P
= P
->next
) {
268 nb_constraints
+= P
->NbConstraints
;
270 matrix
= cloog_matrix_alloc(nb_constraints
, 1 + dim
+ 1);
272 rays
= (CloogMatrix
**)malloc(nb_pol
* sizeof(CloogMatrix
*));
273 for (P
= domain
->polyhedron
, i
= 0; P
; P
= P
->next
, ++i
)
274 rays
[i
] = Polyhedron2Rays(P
);
276 for (P
= domain
->polyhedron
, i
= 0; P
; P
= P
->next
, ++i
) {
277 CloogMatrix
*constraints
= Polyhedron2Constraints(P
);
278 for (j
= 0; j
< constraints
->NbRows
; ++j
) {
279 for (k
= 0; k
< nb_pol
; ++k
) {
282 for (l
= 0; l
< rays
[k
]->NbRows
; ++l
) {
283 Inner_Product(constraints
->p
[j
]+1, rays
[k
]->p
[l
]+1, dim
+1, &tmp
);
284 if (value_neg_p(tmp
))
286 if ((value_zero_p(cloog_matrix_element(constraints
, j
, 0)) ||
287 value_zero_p(cloog_matrix_element(rays
[k
], l
, 0))) && value_pos_p(tmp
))
290 if (l
< rays
[k
]->NbRows
)
294 Vector_Copy(constraints
->p
[j
], matrix
->p
[nb_constraints
++], 1+dim
+1);
296 Matrix_Free(constraints
);
299 for (P
= domain
->polyhedron
, i
= 0; P
; P
= P
->next
, ++i
)
300 Matrix_Free(rays
[i
]);
304 matrix
->NbRows
= nb_constraints
;
305 bounds
= cloog_domain_matrix2domain(matrix
);
306 cloog_matrix_free(matrix
);
312 * cloog_domain_bounds:
313 * Given a list (union) of polyhedra "domain", this function returns a single
314 * polyhedron with constraints that reflect the (parametric) lower and
315 * upper bound on dimension "dim".
317 * nb_par is the number of parameters of the domain.
319 static CloogDomain
* cloog_domain_bounds(CloogDomain
* domain
, int dim
, int nb_par
)
321 int row
, nb_rows
, nb_columns
, difference
;
322 CloogDomain
* projected_domain
, *extended_domain
, *bounds
;
323 CloogMatrix
* matrix
;
325 nb_rows
= 1 + nb_par
+ 1;
326 nb_columns
= domain
->polyhedron
->Dimension
+ 1 ;
327 difference
= nb_columns
- nb_rows
;
330 return(cloog_domain_convex(domain
));
332 matrix
= cloog_matrix_alloc(nb_rows
, nb_columns
);
334 cloog_matrix_element_set_si(matrix
, 0, dim
, 1);
335 for (row
= 1; row
< nb_rows
; row
++)
336 cloog_matrix_element_set_si(matrix
, row
, row
+difference
, 1);
338 projected_domain
= cloog_domain_image(domain
,matrix
) ;
339 extended_domain
= cloog_domain_preimage(projected_domain
, matrix
);
340 cloog_domain_free(projected_domain
);
341 cloog_matrix_free(matrix
) ;
342 bounds
= cloog_domain_convex(extended_domain
);
343 cloog_domain_free(extended_domain
);
349 * cloog_domain_simple_convex:
350 * Given a list (union) of polyhedra, this function returns a "simple"
351 * convex hull of this union. In particular, the constraints of the
352 * the returned polyhedron consist of (parametric) lower and upper
353 * bounds on individual variables and constraints that appear in the
354 * original polyhedra.
356 * nb_par is the number of parameters of the domain.
358 CloogDomain
* cloog_domain_simple_convex(CloogDomain
* domain
, int nb_par
)
361 int dim
= cloog_domain_dimension(domain
) - nb_par
;
362 CloogDomain
*convex
= NULL
;
364 if (cloog_domain_isconvex(domain
))
365 return cloog_domain_copy(domain
);
367 for (i
= 0; i
< dim
; ++i
) {
368 CloogDomain
*bounds
= cloog_domain_bounds(domain
, i
, nb_par
);
373 CloogDomain
*temp
= cloog_domain_intersection(convex
, bounds
);
374 cloog_domain_free(bounds
);
375 cloog_domain_free(convex
);
380 CloogDomain
*temp
, *bounds
;
382 bounds
= cloog_domain_simplified_hull(domain
);
383 temp
= cloog_domain_intersection(convex
, bounds
);
384 cloog_domain_free(bounds
);
385 cloog_domain_free(convex
);
394 * cloog_domain_simplify function:
395 * Given two polyhedral domains (pol1) and (pol2) inside two CloogDomain
396 * structures, this function finds the largest domain set (or the smallest list
397 * of non-redundant constraints), that when intersected with polyhedral
398 * domain (pol2) equals (Pol1)intersect(Pol2). The output is a new CloogDomain
399 * structure with a polyhedral domain with the "redundant" constraints removed.
400 * NB: this function do not work as expected with unions of polyhedra...
402 CloogDomain
* cloog_domain_simplify(CloogDomain
* dom1
, CloogDomain
* dom2
)
406 Polyhedron
*P
= dom1
->polyhedron
;
408 /* DomainSimplify doesn't remove all redundant equalities,
409 * so we remove them here first in case both dom1 and dom2
410 * are single polyhedra (i.e., not unions of polyhedra).
412 if (!dom1
->polyhedron
->next
&& !dom2
->polyhedron
->next
&&
413 P
->NbEq
&& dom2
->polyhedron
->NbEq
) {
415 int rows
= P
->NbEq
+ dom2
->polyhedron
->NbEq
;
416 int cols
= P
->Dimension
+2;
418 M
= cloog_matrix_alloc(rows
, cols
);
419 M2
= cloog_matrix_alloc(P
->NbConstraints
, cols
);
420 Vector_Copy(dom2
->polyhedron
->Constraint
[0], M
->p
[0],
421 dom2
->polyhedron
->NbEq
* cols
);
422 rank
= dom2
->polyhedron
->NbEq
;
424 for (i
= 0; i
< P
->NbEq
; ++i
) {
425 Vector_Copy(P
->Constraint
[i
], M
->p
[rank
], cols
);
426 if (Gauss(M
, rank
+1, cols
-1) > rank
) {
427 Vector_Copy(P
->Constraint
[i
], M2
->p
[row
++], cols
);
432 Vector_Copy(P
->Constraint
[P
->NbEq
], M2
->p
[row
],
433 (P
->NbConstraints
- P
->NbEq
) * cols
);
434 P
= Constraints2Polyhedron(M2
, MAX_RAYS
);
436 cloog_matrix_free(M2
);
437 cloog_matrix_free(M
);
439 dom
= cloog_domain_alloc(DomainSimplify(P
, dom2
->polyhedron
,MAX_RAYS
));
440 if (P
!= dom1
->polyhedron
)
447 * cloog_domain_union function:
448 * This function returns a new CloogDomain structure including a polyhedral
449 * domain which is the union of two polyhedral domains (pol1) U (pol2) inside
450 * two CloogDomain structures.
452 CloogDomain
* cloog_domain_union(CloogDomain
* dom1
, CloogDomain
* dom2
)
453 { return (cloog_domain_alloc(DomainUnion(dom1
->polyhedron
,
454 dom2
->polyhedron
,MAX_RAYS
))) ;
459 * cloog_domain_intersection function:
460 * This function returns a new CloogDomain structure including a polyhedral
461 * domain which is the intersection of two polyhedral domains (pol1)inter(pol2)
462 * inside two CloogDomain structures.
464 CloogDomain
* cloog_domain_intersection(CloogDomain
* dom1
, CloogDomain
* dom2
)
465 { return (cloog_domain_alloc(DomainIntersection(dom1
->polyhedron
,
466 dom2
->polyhedron
,MAX_RAYS
))) ;
471 * cloog_domain_difference function:
472 * This function returns a new CloogDomain structure including a polyhedral
473 * domain which is the difference of two polyhedral domains domain \ minus
474 * inside two CloogDomain structures.
475 * - November 8th 2001: first version.
477 CloogDomain
* cloog_domain_difference(CloogDomain
* domain
, CloogDomain
* minus
)
478 { if (cloog_domain_isempty(minus
))
479 return(cloog_domain_copy(domain
)) ;
481 return (cloog_domain_alloc(DomainDifference(domain
->polyhedron
,
482 minus
->polyhedron
,MAX_RAYS
))) ;
487 * cloog_domain_addconstraints function :
488 * This function adds source's polyhedron constraints to target polyhedron: for
489 * each element of the polyhedron inside 'target' (i.e. element of the union
490 * of polyhedra) it adds the constraints of the corresponding element in
492 * - August 10th 2002: first version.
493 * Nota bene for future : it is possible that source and target don't have the
494 * same number of elements (try iftest2 without non-shared constraint
495 * elimination in cloog_loop_separate !). This function is yet another part
496 * of the DomainSimplify patching problem...
498 CloogDomain
* cloog_domain_addconstraints(domain_source
, domain_target
)
499 CloogDomain
* domain_source
, * domain_target
;
500 { unsigned nb_constraint
;
501 Value
* constraints
;
502 Polyhedron
* source
, * target
, * new, * next
, * last
;
504 source
= domain_source
->polyhedron
;
505 target
= domain_target
->polyhedron
;
507 constraints
= source
->p_Init
;
508 nb_constraint
= source
->NbConstraints
;
509 source
= source
->next
;
510 new = AddConstraints(constraints
,nb_constraint
,target
,MAX_RAYS
) ;
512 next
= target
->next
;
515 { /* BUG !!! This is actually a bug. I don't know yet how to cleanly avoid
516 * the situation where source and target do not have the same number of
517 * elements. So this 'if' is an awful trick, waiting for better.
520 { constraints
= source
->p_Init
;
521 nb_constraint
= source
->NbConstraints
;
522 source
= source
->next
;
524 last
->next
= AddConstraints(constraints
,nb_constraint
,next
,MAX_RAYS
) ;
529 return (cloog_domain_alloc(new)) ;
534 * cloog_domain_sort function:
535 * This function topologically sorts (nb_pols) polyhedra. Here (pols) is a an
536 * array of pointers to polyhedra, (nb_pols) is the number of polyhedra,
537 * (level) is the level to consider for partial ordering (nb_par) is the
538 * parameter space dimension, (permut) if not NULL, is an array of (nb_pols)
539 * integers that contains a permutation specification after call in order to
540 * apply the topological sorting.
542 void cloog_domain_sort(pols
, nb_pols
, level
, nb_par
, permut
)
544 unsigned nb_pols
, level
, nb_par
;
548 /* time is an array of (nb_pols) integers to store logical time values. We
549 * do not use it, but it is compulsory for PolyhedronTSort.
551 time
= (int *)malloc(nb_pols
*sizeof(int)) ;
553 /* PolyhedronTSort will fill up permut (and time). */
554 PolyhedronTSort(pols
,nb_pols
,level
,nb_par
,time
,permut
,MAX_RAYS
) ;
561 * cloog_domain_empty function:
562 * This function allocates the memory space for a CloogDomain structure and
563 * sets its polyhedron to an empty polyhedron with 'dimension' dimensions.
564 * Then it returns a pointer to the allocated space.
565 * - June 10th 2005: first version.
567 CloogDomain
* cloog_domain_empty(int dimension
)
568 { return (cloog_domain_alloc(Empty_Polyhedron(dimension
))) ;
572 /******************************************************************************
573 * Structure display function *
574 ******************************************************************************/
578 * cloog_domain_print_structure :
579 * this function is a more human-friendly way to display the CloogDomain data
580 * structure, it only shows the constraint system and includes an indentation
581 * level (level) in order to work with others print_structure functions.
582 * Written by Olivier Chorier, Luc Marchaud, Pierre Martin and Romain Tartiere.
583 * - April 24th 2005: Initial version.
584 * - May 26th 2005: Memory leak hunt.
585 * - June 16th 2005: (Ced) Integration in domain.c.
587 void cloog_domain_print_structure(FILE * file
, CloogDomain
* domain
, int level
)
589 CloogMatrix
* matrix
;
591 /* Go to the right level. */
592 for(i
=0; i
<level
; i
++)
593 fprintf(file
,"|\t") ;
596 { fprintf(file
,"+-- CloogDomain\n") ;
598 /* Print the matrix. */
599 matrix
= cloog_domain_domain2matrix(domain
) ;
600 cloog_matrix_print_structure(file
,matrix
,level
) ;
601 cloog_matrix_free(matrix
) ;
604 for (i
=0; i
<level
+1; i
++)
605 fprintf(file
,"|\t") ;
609 fprintf(file
,"+-- Null CloogDomain\n") ;
615 * cloog_domain_list_print function:
616 * This function prints the content of a CloogDomainList structure into a
617 * file (foo, possibly stdout).
618 * - November 6th 2001: first version.
620 void cloog_domain_list_print(FILE * foo
, CloogDomainList
* list
)
621 { while (list
!= NULL
)
622 { cloog_domain_print(foo
,list
->domain
) ;
628 /******************************************************************************
629 * Memory deallocation function *
630 ******************************************************************************/
634 * cloog_domain_list_free function:
635 * This function frees the allocated memory for a CloogDomainList structure.
636 * - November 6th 2001: first version.
638 void cloog_domain_list_free(CloogDomainList
* list
)
639 { CloogDomainList
* temp
;
642 { temp
= list
->next
;
643 cloog_domain_free(list
->domain
) ;
650 /******************************************************************************
652 ******************************************************************************/
656 * cloog_domain_read function:
657 * Adaptation from the PolyLib. This function reads a matrix into a file (foo,
658 * posibly stdin) and returns a pointer to a polyhedron containing the read
660 * - October 18th 2001: first version.
662 CloogDomain
* cloog_domain_read(FILE * foo
)
663 { CloogMatrix
* matrix
;
664 CloogDomain
* domain
;
666 matrix
= cloog_matrix_read(foo
) ;
667 domain
= cloog_domain_matrix2domain(matrix
) ;
668 cloog_matrix_free(matrix
) ;
675 * cloog_domain_union_read function:
676 * This function reads a union of polyhedra into a file (foo, posibly stdin) and
677 * returns a pointer to a Polyhedron containing the read information.
678 * - September 9th 2002: first version.
679 * - October 29th 2005: (debug) removal of a leak counting "correction" that
680 * was just false since ages.
682 CloogDomain
* cloog_domain_union_read(FILE * foo
)
683 { int i
, nb_components
;
685 CloogDomain
* domain
, * temp
, * old
;
687 /* domain reading: nb_components (constraint matrices). */
688 while (fgets(s
,MAX_STRING
,foo
) == 0) ;
689 while ((*s
=='#' || *s
=='\n') || (sscanf(s
," %d",&nb_components
)<1))
690 fgets(s
,MAX_STRING
,foo
) ;
692 if (nb_components
> 0)
693 { /* 1. first part of the polyhedra union, */
694 domain
= cloog_domain_read(foo
) ;
695 /* 2. and the nexts. */
696 for (i
=1;i
<nb_components
;i
++)
697 { /* Leak counting is OK since next allocated domain is freed here. */
698 temp
= cloog_domain_read(foo
) ;
700 domain
= cloog_domain_union(temp
,old
) ;
701 cloog_domain_free(temp
) ;
702 cloog_domain_free(old
) ;
712 * cloog_domain_list_read function:
713 * This function reads a list of polyhedra into a file (foo, posibly stdin) and
714 * returns a pointer to a CloogDomainList containing the read information.
715 * - November 6th 2001: first version.
717 CloogDomainList
* cloog_domain_list_read(FILE * foo
)
720 CloogDomainList
* list
, * now
, * next
;
723 /* We read first the number of polyhedra in the list. */
724 while (fgets(s
,MAX_STRING
,foo
) == 0) ;
725 while ((*s
=='#' || *s
=='\n') || (sscanf(s
," %d",&nb_pols
)<1))
726 fgets(s
,MAX_STRING
,foo
) ;
728 /* Then we read the polyhedra. */
731 { list
= (CloogDomainList
*)malloc(sizeof(CloogDomainList
)) ;
732 list
->domain
= cloog_domain_read(foo
) ;
735 for (i
=1;i
<nb_pols
;i
++)
736 { next
= (CloogDomainList
*)malloc(sizeof(CloogDomainList
)) ;
737 next
->domain
= cloog_domain_read(foo
) ;
747 /******************************************************************************
748 * Processing functions *
749 ******************************************************************************/
753 * cloog_domain_malloc function:
754 * This function allocates the memory space for a CloogDomain structure and
755 * sets its fields with default values. Then it returns a pointer to the
757 * - November 21th 2005: first version.
759 static CloogDomain
* cloog_domain_malloc()
760 { CloogDomain
* domain
;
762 domain
= (CloogDomain
*)malloc(sizeof(CloogDomain
)) ;
764 { fprintf(stderr
, "[CLooG]ERROR: memory overflow.\n") ;
767 cloog_domain_leak_up() ;
769 /* We set the various fields with default values. */
770 domain
->polyhedron
= NULL
;
771 domain
->references
= 1 ;
778 * cloog_domain_alloc function:
779 * This function allocates the memory space for a CloogDomain structure and
780 * sets its fields with those given as input. Then it returns a pointer to the
782 * - April 19th 2005: first version.
783 * - November 21th 2005: cloog_domain_malloc use.
785 CloogDomain
* cloog_domain_alloc(Polyhedron
* polyhedron
)
786 { CloogDomain
* domain
;
788 if (polyhedron
== NULL
)
791 { domain
= cloog_domain_malloc() ;
792 domain
->polyhedron
= polyhedron
;
800 * cloog_domain_isempty function:
801 * This function returns 1 if the polyhedron given as input is empty, 0
803 * - October 28th 2001: first version.
805 int cloog_domain_isempty(CloogDomain
* domain
)
806 { if (domain
->polyhedron
== NULL
)
809 if (domain
->polyhedron
->next
)
811 return((domain
->polyhedron
->Dimension
< domain
->polyhedron
->NbEq
) ? 1 : 0) ;
816 * cloog_domain_project function:
817 * From Quillere's LoopGen 0.4. This function returns the projection of
818 * (domain) on the (level) first dimensions (i.e. outer loops). It returns a
819 * pointer to the projected Polyhedron.
820 * - nb_par is the number of parameters.
822 * - October 27th 2001: first version.
823 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
826 CloogDomain
* cloog_domain_project(CloogDomain
* domain
, int level
, int nb_par
)
827 { int row
, column
, nb_rows
, nb_columns
, difference
;
828 CloogDomain
* projected_domain
;
829 CloogMatrix
* matrix
;
831 nb_rows
= level
+ nb_par
+ 1 ;
832 nb_columns
= domain
->polyhedron
->Dimension
+ 1 ;
833 difference
= nb_columns
- nb_rows
;
836 return(cloog_domain_copy(domain
)) ;
838 matrix
= cloog_matrix_alloc(nb_rows
,nb_columns
) ;
840 for (row
=0;row
<level
;row
++)
841 for (column
=0;column
<nb_columns
; column
++)
842 cloog_matrix_element_set_si(matrix
, row
, column
, (row
== column
? 1 : 0)) ;
844 for (;row
<nb_rows
;row
++)
845 for (column
=0;column
<nb_columns
;column
++)
846 cloog_matrix_element_set_si (matrix
, row
, column
, (row
+difference
== column
? 1 : 0)) ;
848 projected_domain
= cloog_domain_image(domain
,matrix
) ;
849 cloog_matrix_free(matrix
) ;
851 return(projected_domain
) ;
855 * cloog_domain_extend function:
856 * From Quillere's LoopGen 0.4. This function returns the (domain) given as
857 * input with (dim)+(nb_par) dimensions. The new dimensions are added before
858 * the (nb_par) parameters. This function does not free (domain), and returns
860 * - nb_par is the number of parameters.
862 * - October 27th 2001: first version.
863 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
866 CloogDomain
* cloog_domain_extend(CloogDomain
* domain
, int dim
, int nb_par
)
867 { int row
, column
, nb_rows
, nb_columns
, difference
;
868 CloogDomain
* extended_domain
;
869 CloogMatrix
* matrix
;
871 nb_rows
= 1 + domain
->polyhedron
->Dimension
;
872 nb_columns
= dim
+ nb_par
+ 1 ;
873 difference
= nb_columns
- nb_rows
;
876 return(cloog_domain_copy(domain
)) ;
878 matrix
= cloog_matrix_alloc(nb_rows
,nb_columns
) ;
880 for (row
=0;row
<domain
->polyhedron
->Dimension
-nb_par
;row
++)
881 for (column
=0;column
<nb_columns
;column
++)
882 cloog_matrix_element_set_si(matrix
, row
, column
, (row
== column
? 1 : 0)) ;
884 for (;row
<=domain
->polyhedron
->Dimension
;row
++)
885 for (column
=0;column
<nb_columns
;column
++)
886 cloog_matrix_element_set_si(matrix
, row
, column
, (row
+difference
== column
? 1 : 0)) ;
888 extended_domain
= cloog_domain_preimage(domain
,matrix
) ;
889 cloog_matrix_free(matrix
) ;
891 return(extended_domain
) ;
896 * cloog_domain_never_integral function:
897 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0. This
898 * function returns a boolean set to 1 if there is this kind of 'never true'
899 * constraint inside a polyhedron, 0 otherwise.
900 * - domain is the polyhedron to check,
902 * - November 28th 2001: first version.
903 * - June 26th 2003: for iterators, more 'never true' constraints are found
904 * (compare cholesky2 and vivien with a previous version),
905 * checking for the parameters created (compare using vivien).
906 * - June 28th 2003: Previously in loop.c and called
907 * cloog_loop_simplify_nevertrue, now here !
908 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
910 * - October 14th 2005: Complete rewriting, not faster but code quite shorter.
912 int cloog_domain_never_integral(CloogDomain
* domain
)
915 Polyhedron
* polyhedron
;
917 if ((domain
== NULL
) || (domain
->polyhedron
== NULL
))
921 value_init_c(modulo
) ;
922 polyhedron
= domain
->polyhedron
;
923 dimension
= polyhedron
->Dimension
+ 2 ;
925 /* For each constraint... */
926 for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
927 { /* If we have an equality and the scalar part is not zero... */
928 if (value_zero_p(polyhedron
->Constraint
[i
][0]) &&
929 value_notzero_p(polyhedron
->Constraint
[i
][dimension
-1]))
930 { /* Then we check whether the scalar can be divided by the gcd of the
931 * unknown vector (including iterators and parameters) or not. If not,
932 * there is no integer point in the polyhedron and we return 1.
934 Vector_Gcd(&(polyhedron
->Constraint
[i
][1]),dimension
-2,&gcd
) ;
935 value_modulus(modulo
,polyhedron
->Constraint
[i
][dimension
-1],gcd
) ;
937 if (value_notzero_p(modulo
))
938 { value_clear_c(gcd
) ;
939 value_clear_c(modulo
) ;
946 value_clear_c(modulo
) ;
952 * cloog_domain_stride function:
953 * This function finds the stride imposed to unknown with the column number
954 * 'strided_level' in order to be integral. For instance, if we have a
955 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
956 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
957 * the unknown i. The function returns the imposed stride in a parameter field.
958 * - domain is the set of constraint we have to consider,
959 * - strided_level is the column number of the unknown for which a stride have
961 * - looking_level is the column number of the unknown that impose a stride to
963 * - stride is the stride that is returned back as a function parameter.
964 * - offset is the value of the constant c if the condition is of the shape
965 * (i + c)%s = 0, s being the stride.
967 * - June 28th 2003: first version.
968 * - July 14th 2003: can now look for multiple striding constraints and returns
969 * the GCD of the strides and the common offset.
970 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
973 void cloog_domain_stride(domain
, strided_level
, nb_par
, stride
, offset
)
974 CloogDomain
* domain
;
975 int strided_level
, nb_par
;
976 Value
* stride
, * offset
;
978 Polyhedron
* polyhedron
;
979 int n_col
, n_row
, rank
;
984 polyhedron
= domain
->polyhedron
;
985 dimension
= polyhedron
->Dimension
;
987 /* Look at all equalities involving strided_level and the inner
988 * iterators. We can ignore the outer iterators and the parameters
989 * here because the lower bound on strided_level is assumed to
992 n_col
= (1+dimension
-nb_par
) - strided_level
;
993 for (i
=0, n_row
=0; i
< polyhedron
->NbEq
; i
++)
994 if (First_Non_Zero(polyhedron
->Constraint
[i
]+strided_level
, n_col
) != -1)
997 M
= cloog_matrix_alloc(n_row
+1, n_col
+1);
998 for (i
=0, n_row
= 0; i
< polyhedron
->NbEq
; i
++) {
999 if (First_Non_Zero(polyhedron
->Constraint
[i
]+strided_level
, n_col
) == -1)
1001 Vector_Copy(polyhedron
->Constraint
[i
]+strided_level
, M
->p
[n_row
], n_col
);
1002 cloog_matrix_element_assign(M
, n_row
, n_col
, polyhedron
->Constraint
[i
][1+dimension
]);
1005 cloog_matrix_element_set_si(M
, n_row
, n_col
, 1);
1007 /* Then look at the general solution to the above equalities. */
1008 rank
= SolveDiophantine(M
, &U
, &V
);
1009 cloog_matrix_free(M
);
1012 /* There is no solution, so the body of this loop will
1013 * never execute. We just leave the constraints alone here so
1014 * that they will ensure the body will not be executed.
1015 * We should probably propagate this information up so that
1016 * the loop can be removed entirely.
1018 value_set_si(*offset
, 0);
1019 value_set_si(*stride
, 1);
1021 /* Compute the gcd of the coefficients defining strided_level. */
1022 Vector_Gcd(U
->p
[0], U
->NbColumns
, stride
);
1023 value_oppose(*offset
, V
->p
[0]);
1024 value_pmodulus(*offset
, *offset
, *stride
);
1034 * cloog_domain_integral_lowerbound function:
1035 * This function returns 1 if the lower bound of an iterator (such as its
1036 * column rank in the constraint set 'domain' is 'level') is integral,
1037 * 0 otherwise. If the lower bound is actually integral, the function fills
1038 * the 'lower' field with the lower bound value.
1039 * - June 29th 2003: first version.
1040 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1043 int cloog_domain_integral_lowerbound(domain
, level
, lower
)
1044 CloogDomain
* domain
;
1047 { int i
, first_lower
=1, dimension
, lower_constraint
=-1 ;
1048 Value iterator
, constant
, tmp
;
1049 Polyhedron
* polyhedron
;
1051 polyhedron
= domain
->polyhedron
;
1052 dimension
= polyhedron
->Dimension
;
1054 /* We want one and only one lower bound (e.g. no equality, no maximum
1057 for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
1058 if (value_zero_p(polyhedron
->Constraint
[i
][0]) &&
1059 value_notzero_p(polyhedron
->Constraint
[i
][level
]))
1062 for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
1063 if (value_pos_p(polyhedron
->Constraint
[i
][level
]))
1066 lower_constraint
= i
;
1074 /* We want an integral lower bound: no other non-zero entry except the
1075 * iterator coefficient and the constant.
1077 for (i
=1; i
<level
; i
++)
1078 if (value_notzero_p(polyhedron
->Constraint
[lower_constraint
][i
]))
1080 for (i
=level
+1; i
<=polyhedron
->Dimension
; i
++)
1081 if (value_notzero_p(polyhedron
->Constraint
[lower_constraint
][i
]))
1084 value_init_c(iterator
) ;
1085 value_init_c(constant
) ;
1088 /* If all is passed, then find the lower bound and return 1. */
1089 value_assign(iterator
, polyhedron
->Constraint
[lower_constraint
][level
]) ;
1090 value_oppose(constant
, polyhedron
->Constraint
[lower_constraint
][dimension
+1]);
1092 value_modulus(tmp
, constant
, iterator
) ;
1093 value_division(*lower
, constant
, iterator
) ;
1095 if (!(value_zero_p(tmp
) || value_neg_p(constant
)))
1096 value_increment(*lower
, *lower
) ;
1098 value_clear_c(iterator
) ;
1099 value_clear_c(constant
) ;
1100 value_clear_c(tmp
) ;
1107 * cloog_domain_lowerbound_update function:
1108 * This function updates the integral lower bound of an iterator (such as its
1109 * column rank in the constraint set 'domain' is 'level') into 'lower'.
1110 * - Jun 29th 2003: first version.
1111 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1114 void cloog_domain_lowerbound_update(domain
, level
, lower
)
1115 CloogDomain
* domain
;
1119 Polyhedron
* polyhedron
;
1121 polyhedron
= domain
->polyhedron
;
1123 /* There is only one lower bound, the first one is the good one. */
1124 for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
1125 if (value_pos_p(polyhedron
->Constraint
[i
][level
]))
1126 { value_set_si(polyhedron
->Constraint
[i
][level
], 1) ;
1127 value_oppose(polyhedron
->Constraint
[i
][polyhedron
->Dimension
+1], lower
) ;
1134 * cloog_domain_lazy_equal function:
1135 * This function returns 1 if the domains given as input are the same, 0 if it
1136 * is unable to decide. This function makes an entry-to-entry comparison between
1137 * the constraint systems, if all the entries are the same, the domains are
1138 * obviously the same and it returns 1, at the first difference, it returns 0.
1139 * This is a very fast way to verify this property. It has been shown (with the
1140 * CLooG benchmarks) that operations on equal domains are 17% of all the
1141 * polyhedral computations. For 75% of the actually identical domains, this
1142 * function answer that they are the same and allow to give immediately the
1143 * trivial solution instead of calling the heavy general functions of PolyLib.
1144 * - August 22th 2003: first version.
1145 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1148 int cloog_domain_lazy_equal(CloogDomain
* d1
, CloogDomain
* d2
)
1149 { int i
, nb_elements
;
1150 Polyhedron
* p1
, * p2
;
1152 p1
= d1
->polyhedron
;
1153 p2
= d2
->polyhedron
;
1155 while ((p1
!= NULL
) && (p2
!= NULL
))
1156 { if ((p1
->NbConstraints
!= p2
->NbConstraints
) ||
1157 (p1
->Dimension
!= p2
->Dimension
))
1160 nb_elements
= p1
->NbConstraints
* (p1
->Dimension
+ 2) ;
1162 for (i
=0;i
<nb_elements
;i
++)
1163 if (value_ne(p1
->p_Init
[i
], p2
->p_Init
[i
]))
1170 if ((p1
!= NULL
) || (p2
!= NULL
))
1178 * cloog_domain_lazy_block function:
1179 * This function returns 1 if the two domains d1 and d2 given as input are the
1180 * same (possibly except for a dimension equal to a constant where we accept
1181 * a difference of 1) AND if we are sure that there are no other domain in
1182 * the code generation problem that may put integral points between those of
1183 * d1 and d2 (0 otherwise). In fact this function answers the question "can I
1184 * safely consider the two domains as only one with two statements (a block) ?".
1185 * This function is lazy: it asks for very standard scattering representation
1186 * (only one constraint per dimension which is an equality, and the constraints
1187 * are ordered per dimension depth: the left hand side of the constraint matrix
1188 * is the identity) and will answer NO at the very first problem.
1189 * - d1 and d2 are the two domains to check for blocking,
1190 * - scattering is the linked list of all domains,
1191 * - scattdims is the total number of scattering dimentions.
1193 * - April 30th 2005: beginning
1194 * - June 9th 2005: first working version.
1195 * - June 10th 2005: debugging.
1196 * - June 21rd 2005: Adaptation for GMP.
1197 * - October 16th 2005: (debug) some false blocks have been removed.
1199 int cloog_domain_lazy_block(d1
, d2
, scattering
, scattdims
)
1200 CloogDomain
* d1
, * d2
;
1201 CloogDomainList
* scattering
;
1203 { int i
, j
, difference
=0, different_constraint
=0 ;
1204 Value date1
, date2
, date3
, temp
;
1205 Polyhedron
* p1
, * p2
, * p3
;
1207 p1
= d1
->polyhedron
;
1208 p2
= d2
->polyhedron
;
1210 /* Some basic checks: we only accept convex domains, with same constraint
1211 * and dimension numbers.
1213 if ((p1
->next
!= NULL
) || (p2
->next
!= NULL
) ||
1214 (p1
->NbConstraints
!= p2
->NbConstraints
) ||
1215 (p1
->Dimension
!= p2
->Dimension
))
1218 /* There should be only one difference between the two domains, it
1219 * has to be at the constant level and the difference must be of +1,
1220 * moreover, after the difference all domain coefficient has to be 0.
1221 * The matrix shape is:
1223 * |===========|=====|<- 0 line
1224 * |===========|=====|
1225 * |===========|====?|<- different_constraint line (found here)
1226 * |===========|0000=|
1227 * |===========|0000=|<- pX->NbConstraints line
1230 * | | (pX->Dimension + 2) column
1231 * | scattdims column
1235 value_init_c(temp
) ;
1236 for (i
=0;i
<p1
->NbConstraints
;i
++)
1237 { if (difference
== 0)
1238 { /* All elements except scalar must be equal. */
1239 for (j
=0;j
<(p1
->Dimension
+ 1);j
++)
1240 if (value_ne(p1
->Constraint
[i
][j
],p2
->Constraint
[i
][j
]))
1241 { value_clear_c(temp
) ;
1244 /* The scalar may differ from +1 (now j=(p1->Dimension + 1)). */
1245 if (value_ne(p1
->Constraint
[i
][j
],p2
->Constraint
[i
][j
]))
1246 { value_increment(temp
,p2
->Constraint
[i
][j
]) ;
1247 if (value_ne(p1
->Constraint
[i
][j
],temp
))
1248 { value_clear_c(temp
) ;
1253 different_constraint
= i
;
1258 { /* Scattering coefficients must be equal. */
1259 for (j
=0;j
<(scattdims
+1);j
++)
1260 if (value_ne(p1
->Constraint
[i
][j
],p2
->Constraint
[i
][j
]))
1261 { value_clear_c(temp
) ;
1265 /* Domain coefficients must be 0. */
1266 for (;j
<(p1
->Dimension
+ 1);j
++)
1267 if (value_notzero_p(p1
->Constraint
[i
][j
]) ||
1268 value_notzero_p(p2
->Constraint
[i
][j
]))
1269 { value_clear_c(temp
) ;
1273 /* Scalar must be equal. */
1274 if (value_ne(p1
->Constraint
[i
][j
],p2
->Constraint
[i
][j
]))
1275 { value_clear_c(temp
) ;
1280 value_clear_c(temp
) ;
1282 /* If the domains are exactly the same, this is a block. */
1283 if (difference
== 0)
1286 /* Now a basic check that the constraint with the difference is an
1287 * equality of a dimension with a constant.
1289 for (i
=0;i
<=different_constraint
;i
++)
1290 if (value_notzero_p(p1
->Constraint
[different_constraint
][i
]))
1293 if (value_notone_p(p1
->Constraint
[different_constraint
]
1294 [different_constraint
+1]))
1297 for (i
=different_constraint
+2;i
<(p1
->Dimension
+ 1);i
++)
1298 if (value_notzero_p(p1
->Constraint
[different_constraint
][i
]))
1301 /* For the moment, d1 and d2 are a block candidate. There remains to check
1302 * that there is no other domain that may put an integral point between
1303 * them. In our lazy test we ensure this property by verifying that the
1304 * constraint matrices have a very strict shape: let us consider that the
1305 * dimension with the difference is d. Then the first d dimensions are
1306 * defined in their depth order using equalities (thus the first column begins
1307 * with d zeroes, there is a d*d identity matrix and a zero-matrix for
1308 * the remaining simensions). If a domain can put integral points between the
1309 * domains of the block candidate, this means that the other entries on the
1310 * first d constraints are equal to those of d1 or d2. Thus we are looking for
1311 * such a constraint system, if it exists d1 and d2 is considered to not be
1312 * a block, it is a bock otherwise.
1314 * 1. Only equalities (for the first different_constraint+1 lines).
1315 * | 2. Must be the identity.
1316 * | | 3. Must be zero.
1317 * | | | 4. Elements are equal, the last one is either date1 or 2.
1320 * |0|100|00000|=====|<- 0 line
1321 * |0|010|00000|=====|
1322 * |0|001|00000|====?|<- different_constraint line
1323 * |*|***|*****|*****|
1324 * |*|***|*****|*****|<- pX->NbConstraints line
1327 * | | | (pX->Dimension + 2) column
1328 * | | scattdims column
1329 * | different_constraint+1 column
1333 /* Step 1 and 2. This is only necessary to check one domain because
1334 * we checked that they are equal on this part before.
1336 for (i
=0;i
<=different_constraint
;i
++)
1337 { for (j
=0;j
<i
+1;j
++)
1338 if (value_notzero_p(p1
->Constraint
[i
][j
]))
1341 if (value_notone_p(p1
->Constraint
[i
][i
+1]))
1344 for (j
=i
+2;j
<=different_constraint
+1;j
++)
1345 if (value_notzero_p(p1
->Constraint
[i
][j
]))
1350 for (i
=0;i
<=different_constraint
;i
++)
1351 for (j
=different_constraint
+2;j
<=scattdims
;j
++)
1352 if (value_notzero_p(p1
->Constraint
[i
][j
]))
1355 value_init_c(date1
) ;
1356 value_init_c(date2
) ;
1357 value_init_c(date3
) ;
1359 /* Now we have to check that the two different dates are unique. */
1360 value_assign(date1
, p1
->Constraint
[different_constraint
][p1
->Dimension
+ 1]) ;
1361 value_assign(date2
, p2
->Constraint
[different_constraint
][p2
->Dimension
+ 1]) ;
1363 /* Step 4. We check all domains except d1 and d2 and we look for at least
1364 * a difference with d1 or d2 on the first different_constraint+1 dimensions.
1366 while (scattering
!= NULL
)
1367 { if ((scattering
->domain
!= d1
) && (scattering
->domain
!= d2
))
1368 { p3
= scattering
->domain
->polyhedron
;
1369 value_assign(date3
,p3
->Constraint
[different_constraint
][p3
->Dimension
+1]);
1372 if (value_ne(date3
,date2
) && value_ne(date3
,date1
))
1375 for (i
=0;(i
<different_constraint
)&&(!difference
);i
++)
1376 for (j
=0;(j
<(p3
->Dimension
+ 2))&&(!difference
);j
++)
1377 if (value_ne(p1
->Constraint
[i
][j
],p3
->Constraint
[i
][j
]))
1380 for (j
=0;(j
<(p3
->Dimension
+ 1))&&(!difference
);j
++)
1381 if (value_ne(p1
->Constraint
[different_constraint
][j
],
1382 p3
->Constraint
[different_constraint
][j
]))
1386 { value_clear_c(date1
) ;
1387 value_clear_c(date2
) ;
1388 value_clear_c(date3
) ;
1393 scattering
= scattering
->next
;
1396 value_clear_c(date1
) ;
1397 value_clear_c(date2
) ;
1398 value_clear_c(date3
) ;
1404 * cloog_domain_lazy_disjoint function:
1405 * This function returns 1 if the domains given as input are disjoint, 0 if it
1406 * is unable to decide. This function finds the unknown with fixed values in
1407 * both domains (on a given constraint, their column entry is not zero and
1408 * only the constant coefficient can be different from zero) and verify that
1409 * their values are the same. If not, the domains are obviously disjoint and
1410 * it returns 1, if there is not such case it returns 0. This is a very fast
1411 * way to verify this property. It has been shown (with the CLooG benchmarks)
1412 * that operations on disjoint domains are 36% of all the polyhedral
1413 * computations. For 94% of the actually identical domains, this
1414 * function answer that they are disjoint and allow to give immediately the
1415 * trivial solution instead of calling the heavy general functions of PolyLib.
1416 * - August 22th 2003: first version.
1417 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1420 int cloog_domain_lazy_disjoint(CloogDomain
* d1
, CloogDomain
* d2
)
1421 { int i1
, j1
, i2
, j2
, scat_dim
;
1423 Polyhedron
* p1
, * p2
;
1425 p1
= d1
->polyhedron
;
1426 p2
= d2
->polyhedron
;
1428 if ((p1
->next
!= NULL
) || (p2
->next
!= NULL
))
1431 value_init_c(scat_val
) ;
1433 for (i1
=0; i1
<p1
->NbConstraints
; i1
++)
1434 { if (value_notzero_p(p1
->Constraint
[i1
][0]))
1438 while (value_zero_p(p1
->Constraint
[i1
][scat_dim
]) &&
1439 (scat_dim
< p1
->Dimension
))
1442 if (value_notone_p(p1
->Constraint
[i1
][scat_dim
]))
1445 { for (j1
=scat_dim
+1; j1
<=p1
->Dimension
; j1
++)
1446 if (value_notzero_p(p1
->Constraint
[i1
][j1
]))
1449 if (j1
!= p1
->Dimension
+1)
1452 value_assign(scat_val
,p1
->Constraint
[i1
][p1
->Dimension
+1]) ;
1454 for (i2
=0; i2
<p2
->NbConstraints
; i2
++)
1455 { for (j2
=0;j2
<scat_dim
;j2
++)
1456 if (value_notzero_p(p2
->Constraint
[i2
][j2
]))
1459 if ((j2
!= scat_dim
) || value_notone_p(p2
->Constraint
[i2
][scat_dim
]))
1462 for (j2
=scat_dim
+1; j2
<p2
->Dimension
; j2
++)
1463 if (value_notzero_p(p2
->Constraint
[i2
][j2
]))
1466 if (j2
!= p2
->Dimension
)
1469 if (value_ne(p2
->Constraint
[i2
][p2
->Dimension
+1],scat_val
))
1470 { value_clear_c(scat_val
) ;
1477 value_clear_c(scat_val
) ;
1483 * cloog_domain_list_lazy_same function:
1484 * This function returns 1 if two domains in the list are the same, 0 if it
1485 * is unable to decide.
1486 * - February 9th 2004: first version.
1488 int cloog_domain_list_lazy_same(CloogDomainList
* list
)
1489 { /*int i=1, j=1 ;*/
1490 CloogDomainList
* current
, * next
;
1493 while (current
!= NULL
)
1494 { next
= current
->next
;
1496 while (next
!= NULL
)
1497 { if (cloog_domain_lazy_equal(current
->domain
,next
->domain
))
1498 { /*printf("Same domains: %d and %d\n",i,j) ;*/
1505 current
= current
->next
;
1512 * Those functions are provided for "object encapsulation", to separate as much
1513 * as possible the inside of the CloogDomain structure from the rest of the
1514 * program, in order to ease the change of polyhedral library. For efficiency
1515 * reasons, they are defined and used as macros in domain.h.
1516 * - April 20th 2005: setting.
1518 Polyhedron * cloog_domain_polyhedron(CloogDomain * domain)
1519 { return domain->polyhedron ;
1522 int cloog_domain_dimension(CloogDomain * domain)
1523 { return domain->polyhedron->Dimension ;
1526 int cloog_domain_nbconstraints(CloogDomain * domain)
1527 { return domain->polyhedron->NbConstraints ;
1530 int cloog_domain_isconvex(CloogDomain * domain)
1531 { return (domain->polyhedron->next == NULL)? 1 : 0 ;
1537 * cloog_domain_cut_first function:
1538 * this function returns a CloogDomain structure with everything except the
1539 * first part of the polyhedra union of the input domain as domain. After a call
1540 * to this function, there remains in the CloogDomain structure provided as
1541 * input only the first part of the original polyhedra union.
1542 * - April 20th 2005: first version, extracted from different part of loop.c.
1544 CloogDomain
* cloog_domain_cut_first(CloogDomain
* domain
)
1545 { CloogDomain
* rest
;
1547 if ((domain
!= NULL
) && (domain
->polyhedron
!= NULL
))
1548 { rest
= cloog_domain_alloc(domain
->polyhedron
->next
) ;
1549 domain
->polyhedron
->next
= NULL
;
1559 * cloog_domain_lazy_isscalar function:
1560 * this function returns 1 if the dimension 'dimension' in the domain 'domain'
1561 * is scalar, this means that the only constraint on this dimension must have
1562 * the shape "x.dimension + scalar = 0" with x an integral variable. This
1563 * function is lazy since we only accept x=1 (further calculations are easier
1565 * - June 14th 2005: first version.
1566 * - June 21rd 2005: Adaptation for GMP.
1568 int cloog_domain_lazy_isscalar(CloogDomain
* domain
, int dimension
)
1570 Polyhedron
* polyhedron
;
1572 polyhedron
= domain
->polyhedron
;
1573 /* For each constraint... */
1574 for (i
=0;i
<polyhedron
->NbConstraints
;i
++)
1575 { /* ...if it is concerned by the potentially scalar dimension... */
1576 if (value_notzero_p(polyhedron
->Constraint
[i
][dimension
+1]))
1577 { /* ...check that the constraint has the shape "dimension + scalar = 0". */
1578 for (j
=0;j
<=dimension
;j
++)
1579 if (value_notzero_p(polyhedron
->Constraint
[i
][j
]))
1582 if (value_notone_p(polyhedron
->Constraint
[i
][dimension
+1]))
1585 for (j
=dimension
+2;j
<(polyhedron
->Dimension
+ 1);j
++)
1586 if (value_notzero_p(polyhedron
->Constraint
[i
][j
]))
1596 * cloog_domain_scalar function:
1597 * when we call this function, we know that "dimension" is a scalar dimension,
1598 * this function finds the scalar value in "domain" and returns it in "value".
1599 * - June 30th 2005: first version.
1601 void cloog_domain_scalar(CloogDomain
* domain
, int dimension
, Value
* value
)
1603 Polyhedron
* polyhedron
;
1605 polyhedron
= domain
->polyhedron
;
1606 /* For each constraint... */
1607 for (i
=0;i
<polyhedron
->NbConstraints
;i
++)
1608 { /* ...if it is the equality defining the scalar dimension... */
1609 if (value_notzero_p(polyhedron
->Constraint
[i
][dimension
+1]) &&
1610 value_zero_p(polyhedron
->Constraint
[i
][0]))
1611 { /* ...Then send the scalar value. */
1612 value_assign(*value
,polyhedron
->Constraint
[i
][polyhedron
->Dimension
+1]) ;
1613 value_oppose(*value
,*value
) ;
1618 /* We should have found a scalar value: if not, there is an error. */
1619 fprintf(stderr
, "[CLooG]ERROR: dimension %d is not scalar as expected.\n",
1626 * cloog_domain_erase_dimension function:
1627 * this function returns a CloogDomain structure builds from 'domain' where
1628 * we removed the dimension 'dimension' and every constraint considering this
1629 * dimension. This is not a projection ! Every data concerning the
1630 * considered dimension is simply erased.
1631 * - June 14th 2005: first version.
1632 * - June 21rd 2005: Adaptation for GMP.
1634 CloogDomain
* cloog_domain_erase_dimension(CloogDomain
* domain
, int dimension
)
1635 { int i
, j
, mi
, nb_dim
;
1636 CloogMatrix
* matrix
;
1637 CloogDomain
* erased
;
1638 Polyhedron
* polyhedron
;
1640 polyhedron
= domain
->polyhedron
;
1641 nb_dim
= polyhedron
->Dimension
;
1643 /* The matrix is one column less and at least one constraint less. */
1644 matrix
= cloog_matrix_alloc(polyhedron
->NbConstraints
-1,nb_dim
+1) ;
1646 /* mi is the constraint counter for the matrix. */
1648 for (i
=0;i
<polyhedron
->NbConstraints
;i
++)
1649 if (value_zero_p(polyhedron
->Constraint
[i
][dimension
+1]))
1650 { for (j
=0;j
<=dimension
;j
++)
1651 cloog_matrix_element_assign(matrix
, mi
, j
, polyhedron
->Constraint
[i
][j
]) ;
1653 for (j
=dimension
+2;j
<nb_dim
+2;j
++)
1654 cloog_matrix_element_assign(matrix
, mi
, j
-1, polyhedron
->Constraint
[i
][j
]) ;
1659 erased
= cloog_domain_matrix2domain(matrix
) ;
1660 cloog_matrix_free(matrix
) ;
1666 cloog_simplify_domain_matrix_with_equalities (CloogDomain
*domain
, int level
,
1667 CloogMatrix
*equal
, int nb_parameters
)
1669 CloogMatrix
*temp
, *res
;
1671 temp
= cloog_domain_domain2matrix (domain
);
1672 cloog_matrix_normalize (temp
, level
);
1673 res
= cloog_matrix_simplify (temp
, equal
, level
, nb_parameters
);
1674 cloog_matrix_free(temp
);