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 <cloog/polylib/cloog.h>
45 static CloogDomain
* cloog_domain_polylib_matrix2domain(CloogState
*state
,
46 Matrix
*, int nb_par
);
47 static Matrix
* cloog_domain_domain2polylib_matrix(CloogDomain
*);
50 /******************************************************************************
51 * Memory leaks hunting *
52 ******************************************************************************/
56 * These functions and global variables are devoted to memory leaks hunting: we
57 * want to know at each moment how many Polyhedron structures had been allocated
58 * (cloog_domain_from_polylib_polyhedronated) and how many had been freed (cloog_domain_freed).
59 * Each time a Polyhedron structure is allocated, a call to the function
60 * cloog_domain_leak_up() must be carried out, and respectively
61 * cloog_domain_leak_down() when a Polyhedron structure is freed. The special
62 * variable cloog_domain_max gives the maximal number of Polyhedron structures
63 * simultaneously alive (i.e. allocated and non-freed) in memory.
64 * - July 3rd->11th 2003: first version (memory leaks hunt and correction).
68 static void cloog_domain_leak_up(CloogState
*state
)
70 state
->domain_allocated
++;
71 if ((state
->domain_allocated
- state
->domain_freed
) > state
->domain_max
)
72 state
->domain_max
= state
->domain_allocated
- state
->domain_freed
;
76 static void cloog_domain_leak_down(CloogState
*state
)
78 state
->domain_freed
++;
82 /******************************************************************************
84 ******************************************************************************/
87 /* CLooG makes an intensive use of polyhedral operations and the PolyLib do
88 * the job. Here are the interfaces to all the PolyLib calls (CLooG uses 19
89 * PolyLib functions), with or without some adaptations. If another polyhedral
90 * library can be used, only these functions have to be changed.
91 * - April 16th 2005: Since PolyLib 5.20, compacting is no more useful and have
92 * been removed. The direct use of the PolyLib's Polyhedron
93 * data structure is also replaced with the CloogDomain data
94 * structure that includes the Polyhedron and an additional
95 * counter on how many pointers point on this structure.
96 * This allows to save memory (cloog_domain_copy now only
97 * increment the counter) while memory leaks are avoided (the
98 * function cloog_domain_free decrements the counter and
99 * actually frees the data structure only when its value
104 * Returns true if each scattering dimension is defined in terms
105 * of the original iterators.
107 int cloog_scattering_fully_specified(CloogScattering
*scattering
,
110 int scattering_dim
= cloog_domain_dimension(&scattering
->dom
) -
111 cloog_domain_dimension(domain
);
112 return scattering
->dom
.polyhedron
->NbEq
>= scattering_dim
;
116 * cloog_domain_polylib_matrix2domain function:
117 * Given a matrix of constraints (matrix), this function constructs and returns
118 * the corresponding domain (i.e. the CloogDomain structure including the
119 * polyhedron with its double representation: constraint matrix and the set of
122 CloogDomain
*cloog_domain_polylib_matrix2domain(CloogState
*state
,
123 Matrix
*matrix
, int nb_par
)
125 Polyhedron
*P
= Constraints2Polyhedron(matrix
, state
->backend
->MAX_RAYS
);
126 return cloog_domain_from_polylib_polyhedron(state
, P
, nb_par
);
131 * cloog_domain_domain2polylib_matrix function:
132 * Given a polyhedron (in domain), this function returns its corresponding
133 * matrix of constraints.
135 Matrix
* cloog_domain_domain2polylib_matrix(CloogDomain
* domain
)
137 return cloog_polylib_matrix_matrix(Polyhedron2Constraints(domain
->polyhedron
));
140 CloogConstraintSet
*cloog_domain_constraints(CloogDomain
*domain
)
142 return cloog_domain_domain2polylib_matrix(domain
);
147 * Create duplicate of domain.
149 CloogDomain
*cloog_domain_duplicate(CloogDomain
*domain
)
151 Polyhedron
*P
= Polyhedron_Copy(domain
->polyhedron
);
152 return cloog_domain_from_polylib_polyhedron(domain
->state
, P
, domain
->nb_par
);
157 * cloog_domain_print function:
158 * This function prints the content of a CloogDomain structure (domain) into
159 * a file (foo, possibly stdout).
161 void cloog_domain_print(FILE * foo
, CloogDomain
* domain
)
162 { Polyhedron_Print(foo
,P_VALUE_FMT
,domain
->polyhedron
) ;
163 fprintf(foo
,"Number of active references: %d\n",domain
->references
) ;
166 void cloog_domain_print_constraints(FILE *foo
, CloogDomain
*domain
,
169 Polyhedron
*polyhedron
;
174 /* Number of polyhedron inside the union of disjoint polyhedra. */
175 for (polyhedron
= cloog_domain_polyhedron(domain
); polyhedron
;
176 polyhedron
= polyhedron
->next
)
178 fprintf(foo
, "%d\n", j
);
181 /* The polyhedra themselves. */
182 for (polyhedron
= cloog_domain_polyhedron(domain
); polyhedron
;
183 polyhedron
= polyhedron
->next
) {
184 matrix
= cloog_polylib_matrix_matrix(Polyhedron2Constraints(polyhedron
));
185 cloog_polylib_matrix_print(foo
,matrix
);
186 cloog_polylib_matrix_free(matrix
);
191 * cloog_polyhedron_print function:
192 * This function prints the content of a Polyhedron structure (polyhedron) into
193 * a file (foo, possibly stdout). Just there as a development facility.
195 void cloog_polyhedron_print(FILE * foo
, Polyhedron
* polyhedron
)
196 { Polyhedron_Print(foo
,P_VALUE_FMT
,polyhedron
) ;
201 * cloog_domain_free function:
202 * This function frees the allocated memory for a CloogDomain structure
203 * (domain). It decrements the number of active references to this structure,
204 * if there are no more references on the structure, it frees it (with the
205 * included list of polyhedra).
207 void cloog_domain_free(CloogDomain
* domain
)
208 { if (domain
!= NULL
)
209 { domain
->references
-- ;
211 if (domain
->references
== 0) {
212 if (domain
->polyhedron
!= NULL
) {
213 cloog_domain_leak_down(domain
->state
);
214 Domain_Free(domain
->polyhedron
) ;
221 void cloog_scattering_free(CloogScattering
*scatt
)
223 cloog_domain_free(&scatt
->dom
);
228 * cloog_domain_copy function:
229 * This function returns a copy of a CloogDomain structure (domain). To save
230 * memory this is not a memory copy but we increment a counter of active
231 * references inside the structure, then return a pointer to that structure.
233 CloogDomain
* cloog_domain_copy(CloogDomain
* domain
)
234 { domain
->references
++ ;
240 * cloog_domain_image function:
241 * This function returns a CloogDomain structure such that the included
242 * polyhedral domain is computed from the former one into another
243 * domain according to a given affine mapping function (mapping).
245 CloogDomain
* cloog_domain_image(CloogDomain
* domain
, Matrix
* mapping
)
248 I
= DomainImage(domain
->polyhedron
, mapping
, domain
->state
->backend
->MAX_RAYS
);
249 return cloog_domain_from_polylib_polyhedron(domain
->state
, I
, domain
->nb_par
);
254 * cloog_domain_preimage function:
255 * Given a polyhedral domain (polyhedron) inside a CloogDomain structure and a
256 * mapping function (mapping), this function returns a new CloogDomain structure
257 * with a polyhedral domain which when transformed by mapping function (mapping)
258 * gives (polyhedron).
260 CloogDomain
* cloog_domain_preimage(CloogDomain
* domain
, Matrix
* mapping
)
263 I
= DomainPreimage(domain
->polyhedron
, mapping
, domain
->state
->backend
->MAX_RAYS
);
264 return cloog_domain_from_polylib_polyhedron(domain
->state
, I
, domain
->nb_par
);
269 * cloog_domain_convex function:
270 * Given a polyhedral domain (polyhedron), this function concatenates the lists
271 * of rays and lines of the two (or more) polyhedra in the domain into one
272 * combined list, and find the set of constraints which tightly bound all of
273 * those objects. It returns the corresponding polyhedron.
275 CloogDomain
* cloog_domain_convex(CloogDomain
* domain
)
278 C
= DomainConvex(domain
->polyhedron
, domain
->state
->backend
->MAX_RAYS
);
279 return cloog_domain_from_polylib_polyhedron(domain
->state
, C
, domain
->nb_par
);
284 * cloog_domain_simplified_hull:
285 * Given a list (union) of polyhedra, this function returns a single
286 * polyhedron that contains this union and uses only contraints that
287 * appear in one or more of the polyhedra in the list.
289 * We simply iterate over all constraints of all polyhedra and test
290 * whether all rays of the other polyhedra satisfy/saturate the constraint.
292 static CloogDomain
*cloog_domain_simplified_hull(CloogDomain
* domain
)
294 int dim
= cloog_domain_dimension(domain
) + domain
->nb_par
;
296 int nb_pol
= 0, nb_constraints
= 0;
298 Matrix
**rays
, *matrix
;
303 for (P
= domain
->polyhedron
; P
; P
= P
->next
) {
305 nb_constraints
+= P
->NbConstraints
;
307 matrix
= cloog_polylib_matrix_alloc(nb_constraints
, 1 + dim
+ 1);
309 rays
= (Matrix
**)malloc(nb_pol
* sizeof(Matrix
*));
310 for (P
= domain
->polyhedron
, i
= 0; P
; P
= P
->next
, ++i
)
311 rays
[i
] = Polyhedron2Rays(P
);
313 for (P
= domain
->polyhedron
, i
= 0; P
; P
= P
->next
, ++i
) {
314 Matrix
*constraints
= Polyhedron2Constraints(P
);
315 for (j
= 0; j
< constraints
->NbRows
; ++j
) {
316 for (k
= 0; k
< nb_pol
; ++k
) {
319 for (l
= 0; l
< rays
[k
]->NbRows
; ++l
) {
320 Inner_Product(constraints
->p
[j
]+1, rays
[k
]->p
[l
]+1, dim
+1, &tmp
);
321 if (value_neg_p(tmp
))
323 if ((value_zero_p(constraints
->p
[j
][0]) ||
324 value_zero_p(rays
[k
]->p
[l
][0])) && value_pos_p(tmp
))
327 if (l
< rays
[k
]->NbRows
)
331 Vector_Copy(constraints
->p
[j
], matrix
->p
[nb_constraints
++], 1+dim
+1);
333 Matrix_Free(constraints
);
336 for (P
= domain
->polyhedron
, i
= 0; P
; P
= P
->next
, ++i
)
337 Matrix_Free(rays
[i
]);
341 matrix
->NbRows
= nb_constraints
;
342 bounds
= cloog_domain_polylib_matrix2domain(domain
->state
, matrix
, domain
->nb_par
);
343 cloog_polylib_matrix_free(matrix
);
350 * cloog_domain_simple_convex:
351 * Given a list (union) of polyhedra, this function returns a "simple"
352 * convex hull of this union. In particular, the constraints of the
353 * the returned polyhedron consist of (parametric) lower and upper
354 * bounds on individual variables and constraints that appear in the
355 * original polyhedra.
357 CloogDomain
*cloog_domain_simple_convex(CloogDomain
*domain
)
360 int dim
= cloog_domain_dimension(domain
);
361 CloogDomain
*convex
= NULL
;
363 if (cloog_domain_isconvex(domain
))
364 return cloog_domain_copy(domain
);
366 for (i
= 0; i
< dim
; ++i
) {
367 CloogDomain
*bounds
= cloog_domain_bounds(domain
, i
);
372 CloogDomain
*temp
= cloog_domain_intersection(convex
, bounds
);
373 cloog_domain_free(bounds
);
374 cloog_domain_free(convex
);
379 CloogDomain
*temp
, *bounds
;
381 bounds
= cloog_domain_simplified_hull(domain
);
382 temp
= cloog_domain_intersection(convex
, bounds
);
383 cloog_domain_free(bounds
);
384 cloog_domain_free(convex
);
393 * cloog_domain_simplify function:
394 * Given two polyhedral domains (pol1) and (pol2) inside two CloogDomain
395 * structures, this function finds the largest domain set (or the smallest list
396 * of non-redundant constraints), that when intersected with polyhedral
397 * domain (pol2) equals (Pol1)intersect(Pol2). The output is a new CloogDomain
398 * structure with a polyhedral domain with the "redundant" constraints removed.
399 * NB: this function do not work as expected with unions of polyhedra...
401 CloogDomain
* cloog_domain_simplify(CloogDomain
* dom1
, CloogDomain
* dom2
)
405 Polyhedron
*P
= dom1
->polyhedron
;
406 int MAX_RAYS
= dom1
->state
->backend
->MAX_RAYS
;
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_polylib_matrix_alloc(rows
, cols
);
419 M2
= cloog_polylib_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 if (P
->NbConstraints
> P
->NbEq
)
433 Vector_Copy(P
->Constraint
[P
->NbEq
], M2
->p
[row
],
434 (P
->NbConstraints
- P
->NbEq
) * cols
);
435 P
= Constraints2Polyhedron(M2
, MAX_RAYS
);
437 cloog_polylib_matrix_free(M2
);
438 cloog_polylib_matrix_free(M
);
440 dom
= cloog_domain_from_polylib_polyhedron(dom1
->state
,
441 DomainSimplify(P
, dom2
->polyhedron
, MAX_RAYS
),
443 if (P
!= dom1
->polyhedron
)
450 * cloog_domain_union function:
451 * This function returns a new CloogDomain structure including a polyhedral
452 * domain which is the union of two polyhedral domains (pol1) U (pol2) inside
453 * two CloogDomain structures.
455 CloogDomain
* cloog_domain_union(CloogDomain
* dom1
, CloogDomain
* dom2
)
457 int MAX_RAYS
= dom1
->state
->backend
->MAX_RAYS
;
458 return cloog_domain_from_polylib_polyhedron(dom1
->state
, DomainUnion(dom1
->polyhedron
,
459 dom2
->polyhedron
, MAX_RAYS
),
465 * cloog_domain_intersection function:
466 * This function returns a new CloogDomain structure including a polyhedral
467 * domain which is the intersection of two polyhedral domains (pol1)inter(pol2)
468 * inside two CloogDomain structures.
470 CloogDomain
* cloog_domain_intersection(CloogDomain
* dom1
, CloogDomain
* dom2
)
472 int MAX_RAYS
= dom1
->state
->backend
->MAX_RAYS
;
473 return cloog_domain_from_polylib_polyhedron(dom1
->state
, DomainIntersection(dom1
->polyhedron
,
474 dom2
->polyhedron
, MAX_RAYS
),
480 * cloog_domain_difference function:
481 * This function returns a new CloogDomain structure including a polyhedral
482 * domain which is the difference of two polyhedral domains domain \ minus
483 * inside two CloogDomain structures.
484 * - November 8th 2001: first version.
486 CloogDomain
* cloog_domain_difference(CloogDomain
* domain
, CloogDomain
* minus
)
488 int MAX_RAYS
= domain
->state
->backend
->MAX_RAYS
;
489 if (cloog_domain_isempty(minus
))
490 return(cloog_domain_copy(domain
)) ;
492 return cloog_domain_from_polylib_polyhedron(domain
->state
, DomainDifference(domain
->polyhedron
,
493 minus
->polyhedron
,MAX_RAYS
),
499 * cloog_domain_addconstraints function :
500 * This function adds source's polyhedron constraints to target polyhedron: for
501 * each element of the polyhedron inside 'target' (i.e. element of the union
502 * of polyhedra) it adds the constraints of the corresponding element in
504 * - August 10th 2002: first version.
505 * Nota bene for future : it is possible that source and target don't have the
506 * same number of elements (try iftest2 without non-shared constraint
507 * elimination in cloog_loop_separate !). This function is yet another part
508 * of the DomainSimplify patching problem...
510 CloogDomain
* cloog_domain_addconstraints(domain_source
, domain_target
)
511 CloogDomain
* domain_source
, * domain_target
;
512 { unsigned nb_constraint
;
513 Value
* constraints
;
514 Polyhedron
* source
, * target
, * new, * next
, * last
;
515 int MAX_RAYS
= domain_source
->state
->backend
->MAX_RAYS
;
517 source
= domain_source
->polyhedron
;
518 target
= domain_target
->polyhedron
;
520 constraints
= source
->p_Init
;
521 nb_constraint
= source
->NbConstraints
;
522 source
= source
->next
;
523 new = AddConstraints(constraints
,nb_constraint
,target
,MAX_RAYS
) ;
525 next
= target
->next
;
528 { /* BUG !!! This is actually a bug. I don't know yet how to cleanly avoid
529 * the situation where source and target do not have the same number of
530 * elements. So this 'if' is an awful trick, waiting for better.
533 { constraints
= source
->p_Init
;
534 nb_constraint
= source
->NbConstraints
;
535 source
= source
->next
;
537 last
->next
= AddConstraints(constraints
,nb_constraint
,next
,MAX_RAYS
) ;
542 return cloog_domain_from_polylib_polyhedron(domain_source
->state
, new, domain_source
->nb_par
);
547 * cloog_domain_sort function:
548 * This function topologically sorts (nb_pols) polyhedra. Here (pols) is a an
549 * array of pointers to polyhedra, (nb_pols) is the number of polyhedra,
550 * (level) is the level to consider for partial ordering (nb_par) is the
551 * parameter space dimension, (permut) if not NULL, is an array of (nb_pols)
552 * integers that contains a permutation specification after call in order to
553 * apply the topological sorting.
555 void cloog_domain_sort(CloogDomain
**doms
, unsigned nb_doms
, unsigned level
,
565 nb_par
= doms
[0]->nb_par
;
566 MAX_RAYS
= doms
[0]->state
->backend
->MAX_RAYS
;
568 pols
= (Polyhedron
**) malloc(nb_doms
* sizeof(Polyhedron
*));
570 for (i
= 0; i
< nb_doms
; i
++)
571 pols
[i
] = cloog_domain_polyhedron(doms
[i
]);
573 /* time is an array of (nb_doms) integers to store logical time values. We
574 * do not use it, but it is compulsory for PolyhedronTSort.
576 time
= (int *)malloc(nb_doms
* sizeof(int));
578 /* PolyhedronTSort will fill up permut (and time). */
579 PolyhedronTSort(pols
, nb_doms
, level
, nb_par
, time
, permut
, MAX_RAYS
);
587 * cloog_domain_empty function:
588 * This function allocates the memory space for a CloogDomain structure and
589 * sets its polyhedron to an empty polyhedron with the same dimensions
591 * Then it returns a pointer to the allocated space.
592 * - June 10th 2005: first version.
594 CloogDomain
* cloog_domain_empty(CloogDomain
*template)
596 unsigned dim
= cloog_domain_dimension(template) + template->nb_par
;
597 return cloog_domain_from_polylib_polyhedron(template->state
,
598 Empty_Polyhedron(dim
), template->nb_par
);
602 /******************************************************************************
603 * Structure display function *
604 ******************************************************************************/
607 static void print_structure_prefix(FILE *file
, int level
)
611 for(i
= 0; i
< level
; i
++)
612 fprintf(file
, "|\t");
617 * cloog_domain_print_structure :
618 * this function is a more human-friendly way to display the CloogDomain data
619 * structure, it only shows the constraint system and includes an indentation
620 * level (level) in order to work with others print_structure functions.
621 * Written by Olivier Chorier, Luc Marchaud, Pierre Martin and Romain Tartiere.
622 * - April 24th 2005: Initial version.
623 * - May 26th 2005: Memory leak hunt.
624 * - June 16th 2005: (Ced) Integration in domain.c.
626 void cloog_domain_print_structure(FILE *file
, CloogDomain
*domain
, int level
,
632 print_structure_prefix(file
, level
);
635 { fprintf(file
,"+-- %s\n", name
);
637 /* Print the matrix. */
638 for (P
= domain
->polyhedron
; P
; P
= P
->next
) {
639 matrix
= Polyhedron2Constraints(P
);
640 cloog_polylib_matrix_print_structure(file
, matrix
, level
);
641 cloog_polylib_matrix_free(matrix
);
644 print_structure_prefix(file
, level
+1);
649 fprintf(file
,"+-- Null CloogDomain\n") ;
655 * cloog_scattering_list_print function:
656 * This function prints the content of a CloogScatteringList structure into a
657 * file (foo, possibly stdout).
658 * - November 6th 2001: first version.
660 void cloog_scattering_list_print(FILE * foo
, CloogScatteringList
* list
)
661 { while (list
!= NULL
)
662 { cloog_domain_print(foo
, &list
->scatt
->dom
);
668 /******************************************************************************
669 * Memory deallocation function *
670 ******************************************************************************/
674 * cloog_scattering_list_free function:
675 * This function frees the allocated memory for a CloogScatteringList structure.
676 * - November 6th 2001: first version.
678 void cloog_scattering_list_free(CloogScatteringList
* list
)
679 { CloogScatteringList
* temp
;
682 { temp
= list
->next
;
683 cloog_scattering_free(list
->scatt
);
690 /******************************************************************************
692 ******************************************************************************/
696 * cloog_domain_read function:
697 * Adaptation from the PolyLib. This function reads a matrix into a file (foo,
698 * posibly stdin) and returns a pointer to a polyhedron containing the read
700 * - October 18th 2001: first version.
702 CloogDomain
*cloog_domain_read(CloogState
*state
, FILE *foo
, int nb_parameters
)
704 CloogDomain
* domain
;
706 matrix
= cloog_polylib_matrix_read(foo
) ;
707 domain
= cloog_domain_polylib_matrix2domain(state
, matrix
, nb_parameters
);
708 cloog_polylib_matrix_free(matrix
) ;
715 * cloog_domain_read_context:
716 * Read parameter domain. For the PolyLib backend, a parameter domain
717 * is indistinguishable from a parametric domain.
719 CloogDomain
*cloog_domain_read_context(CloogState
*state
, FILE * foo
)
721 CloogDomain
*context
= cloog_domain_read(state
, foo
, 0);
722 context
->nb_par
= context
->polyhedron
->Dimension
;
728 * cloog_domain_from_context
729 * Reinterpret context by turning parameters into variables.
731 CloogDomain
*cloog_domain_from_context(CloogDomain
*context
)
734 domain
= cloog_domain_duplicate(context
);
735 cloog_domain_free(context
);
742 * cloog_domain_union_read function:
743 * This function reads a union of polyhedra into a file (foo, posibly stdin) and
744 * returns a pointer to a Polyhedron containing the read information.
745 * - September 9th 2002: first version.
746 * - October 29th 2005: (debug) removal of a leak counting "correction" that
747 * was just false since ages.
749 CloogDomain
*cloog_domain_union_read(CloogState
*state
,
750 FILE *foo
, int nb_parameters
)
751 { int i
, nb_components
;
753 CloogDomain
* domain
, * temp
, * old
;
755 /* domain reading: nb_components (constraint matrices). */
756 while (fgets(s
,MAX_STRING
,foo
) == 0) ;
757 while ((*s
=='#' || *s
=='\n') || (sscanf(s
," %d",&nb_components
)<1))
758 fgets(s
,MAX_STRING
,foo
) ;
760 if (nb_components
> 0)
761 { /* 1. first part of the polyhedra union, */
762 domain
= cloog_domain_read(state
, foo
, nb_parameters
);
763 /* 2. and the nexts. */
764 for (i
=1;i
<nb_components
;i
++)
765 { /* Leak counting is OK since next allocated domain is freed here. */
766 temp
= cloog_domain_read(state
, foo
, nb_parameters
);
768 domain
= cloog_domain_union(temp
,old
) ;
769 cloog_domain_free(temp
) ;
770 cloog_domain_free(old
) ;
780 * cloog_domain_read_scattering function:
781 * This function reads in a scattering function fro the file foo.
783 CloogScattering
*cloog_domain_read_scattering(CloogDomain
*domain
, FILE *foo
)
785 return (CloogScattering
*)
786 cloog_domain_read(domain
->state
, foo
, domain
->nb_par
);
790 /******************************************************************************
791 * CloogMatrix Reading function *
792 ******************************************************************************/
795 * Create a CloogDomain containing the constraints described in matrix.
796 * nb_par is the number of parameters contained in the domain.
797 * Returns a pointer to the CloogDomain if successful; NULL otherwise.
799 CloogDomain
*cloog_domain_from_cloog_matrix(CloogState
*state
,
800 CloogMatrix
*matrix
, int nb_par
)
806 pmatrix
= cloog_polylib_matrix_alloc(matrix
->NbRows
,matrix
->NbColumns
);
813 for (i
= 0; i
< pmatrix
->NbRows
; i
++)
814 for (j
= 0; j
< pmatrix
->NbColumns
; j
++)
815 cloog_int_set(p
[i
][j
], matrix
->p
[i
][j
]);
817 return cloog_domain_polylib_matrix2domain(state
, pmatrix
, nb_par
);
821 * Create a CloogScattering containing the constraints described in matrix.
822 * nb_par is the number of parameters contained in the domain.
823 * Returns a pointer to the CloogScattering if successful; NULL otherwise.
825 CloogScattering
*cloog_scattering_from_cloog_matrix(CloogState
*state
,
826 CloogMatrix
*matrix
, int nb_scat
, int nb_par
)
828 CloogDomain
*domain
= cloog_domain_from_cloog_matrix(state
, matrix
, nb_par
);
829 return (CloogScattering
*)domain
;
833 /******************************************************************************
834 * Processing functions *
835 ******************************************************************************/
839 * cloog_domain_malloc function:
840 * This function allocates the memory space for a CloogDomain structure and
841 * sets its fields with default values. Then it returns a pointer to the
843 * - November 21th 2005: first version.
845 CloogDomain
*cloog_domain_malloc(CloogState
*state
)
846 { CloogDomain
* domain
;
848 domain
= (CloogDomain
*)malloc(sizeof(CloogDomain
)) ;
850 cloog_die("memory overflow.\n");
851 cloog_domain_leak_up(state
);
853 /* We set the various fields with default values. */
854 domain
->state
= state
;
855 domain
->polyhedron
= NULL
;
856 domain
->references
= 1 ;
863 * cloog_domain_from_polylib_polyhedron function:
864 * This function allocates the memory space for a CloogDomain structure and
865 * sets its fields with those given as input. Then it returns a pointer to the
867 * - April 19th 2005: first version.
868 * - November 21th 2005: cloog_domain_malloc use.
870 CloogDomain
*cloog_domain_from_polylib_polyhedron(CloogState
*state
,
871 Polyhedron
*polyhedron
, int nb_par
)
872 { CloogDomain
* domain
;
874 if (polyhedron
== NULL
)
877 domain
= cloog_domain_malloc(state
);
878 domain
->polyhedron
= polyhedron
;
879 domain
->nb_par
= nb_par
;
887 * cloog_scattering_from_polylib_polyhedron function:
888 * This function allocates the memory space for a CloogDomain structure and
889 * sets its fields with those given as input. Then it returns a pointer to the
891 * - April 19th 2005: first version.
892 * - November 21th 2005: cloog_domain_malloc use.
894 CloogScattering
*cloog_scattering_from_polylib_polyhedron(CloogState
*state
,
895 Polyhedron
*polyhedron
, int nb_par
)
897 return (CloogScattering
*)
898 cloog_domain_from_polylib_polyhedron(state
, polyhedron
, nb_par
);
903 * cloog_domain_isempty function:
904 * This function returns 1 if the polyhedron given as input is empty, 0
906 * - October 28th 2001: first version.
908 int cloog_domain_isempty(CloogDomain
* domain
)
909 { if (!domain
|| domain
->polyhedron
== NULL
)
912 if (domain
->polyhedron
->next
)
914 return((domain
->polyhedron
->Dimension
< domain
->polyhedron
->NbEq
) ? 1 : 0) ;
919 * cloog_domain_universe function:
920 * This function returns the complete dim-dimensional space.
922 CloogDomain
*cloog_domain_universe(CloogState
*state
, unsigned dim
)
924 return cloog_domain_from_polylib_polyhedron(state
, Universe_Polyhedron(dim
), 0);
929 * cloog_domain_project function:
930 * From Quillere's LoopGen 0.4. This function returns the projection of
931 * (domain) on the (level) first dimensions (i.e. outer loops). It returns a
932 * pointer to the projected Polyhedron.
934 * - October 27th 2001: first version.
935 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
938 CloogDomain
*cloog_domain_project(CloogDomain
*domain
, int level
)
939 { int row
, column
, nb_rows
, nb_columns
, difference
;
940 CloogDomain
* projected_domain
;
943 nb_rows
= level
+ domain
->nb_par
+ 1 ;
944 nb_columns
= domain
->polyhedron
->Dimension
+ 1 ;
945 difference
= nb_columns
- nb_rows
;
948 return(cloog_domain_copy(domain
)) ;
950 matrix
= cloog_polylib_matrix_alloc(nb_rows
,nb_columns
) ;
952 for (row
=0;row
<level
;row
++)
953 for (column
=0;column
<nb_columns
; column
++)
954 value_set_si(matrix
->p
[row
][column
],(row
== column
? 1 : 0)) ;
956 for (;row
<nb_rows
;row
++)
957 for (column
=0;column
<nb_columns
;column
++)
958 value_set_si(matrix
->p
[row
][column
],(row
+difference
== column
? 1 : 0)) ;
960 projected_domain
= cloog_domain_image(domain
,matrix
) ;
961 cloog_polylib_matrix_free(matrix
) ;
963 return(projected_domain
) ;
968 * cloog_domain_bounds:
969 * Given a list (union) of polyhedra "domain", this function returns a single
970 * polyhedron with constraints that reflect the (parametric) lower and
971 * upper bound on dimension "dim".
973 CloogDomain
*cloog_domain_bounds(CloogDomain
*domain
, int dim
)
975 int row
, nb_rows
, nb_columns
, difference
;
976 CloogDomain
* projected_domain
, *extended_domain
, *bounds
;
979 nb_rows
= 1 + domain
->nb_par
+ 1;
980 nb_columns
= domain
->polyhedron
->Dimension
+ 1 ;
981 difference
= nb_columns
- nb_rows
;
984 return(cloog_domain_convex(domain
));
986 matrix
= cloog_polylib_matrix_alloc(nb_rows
, nb_columns
);
988 value_set_si(matrix
->p
[0][dim
], 1);
989 for (row
= 1; row
< nb_rows
; row
++)
990 value_set_si(matrix
->p
[row
][row
+difference
], 1);
992 projected_domain
= cloog_domain_image(domain
,matrix
) ;
993 extended_domain
= cloog_domain_preimage(projected_domain
, matrix
);
994 cloog_domain_free(projected_domain
);
995 cloog_polylib_matrix_free(matrix
) ;
996 bounds
= cloog_domain_convex(extended_domain
);
997 cloog_domain_free(extended_domain
);
1004 * cloog_domain_extend function:
1005 * From Quillere's LoopGen 0.4. This function returns the (domain) given as
1006 * input with (dim)+(nb_par) dimensions. The new dimensions are added before
1007 * the (nb_par) parameters. This function does not free (domain), and returns
1010 * - October 27th 2001: first version.
1011 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1014 CloogDomain
*cloog_domain_extend(CloogDomain
*domain
, int dim
)
1015 { int row
, column
, nb_rows
, nb_columns
, difference
;
1016 CloogDomain
* extended_domain
;
1019 nb_rows
= 1 + domain
->polyhedron
->Dimension
;
1020 nb_columns
= dim
+ domain
->nb_par
+ 1 ;
1021 difference
= nb_columns
- nb_rows
;
1023 if (difference
== 0)
1024 return(cloog_domain_copy(domain
)) ;
1026 matrix
= cloog_polylib_matrix_alloc(nb_rows
,nb_columns
) ;
1028 for (row
= 0; row
< domain
->polyhedron
->Dimension
- domain
->nb_par
; row
++)
1029 for (column
=0;column
<nb_columns
;column
++)
1030 value_set_si(matrix
->p
[row
][column
],(row
== column
? 1 : 0)) ;
1032 for (;row
<=domain
->polyhedron
->Dimension
;row
++)
1033 for (column
=0;column
<nb_columns
;column
++)
1034 value_set_si(matrix
->p
[row
][column
],(row
+difference
== column
? 1 : 0)) ;
1036 extended_domain
= cloog_domain_preimage(domain
,matrix
) ;
1037 cloog_polylib_matrix_free(matrix
) ;
1039 return(extended_domain
) ;
1044 * cloog_domain_never_integral function:
1045 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0. This
1046 * function returns a boolean set to 1 if there is this kind of 'never true'
1047 * constraint inside a polyhedron, 0 otherwise.
1048 * - domain is the polyhedron to check,
1050 * - November 28th 2001: first version.
1051 * - June 26th 2003: for iterators, more 'never true' constraints are found
1052 * (compare cholesky2 and vivien with a previous version),
1053 * checking for the parameters created (compare using vivien).
1054 * - June 28th 2003: Previously in loop.c and called
1055 * cloog_loop_simplify_nevertrue, now here !
1056 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1058 * - October 14th 2005: Complete rewriting, not faster but code quite shorter.
1060 int cloog_domain_never_integral(CloogDomain
* domain
)
1061 { int i
, dimension
;
1063 Polyhedron
* polyhedron
;
1065 if ((domain
== NULL
) || (domain
->polyhedron
== NULL
))
1070 polyhedron
= domain
->polyhedron
;
1071 dimension
= polyhedron
->Dimension
+ 2 ;
1073 /* For each constraint... */
1074 for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
1075 { /* If we have an equality and the scalar part is not zero... */
1076 if (value_zero_p(polyhedron
->Constraint
[i
][0]) &&
1077 value_notzero_p(polyhedron
->Constraint
[i
][dimension
-1]))
1078 { /* Then we check whether the scalar can be divided by the gcd of the
1079 * unknown vector (including iterators and parameters) or not. If not,
1080 * there is no integer point in the polyhedron and we return 1.
1082 Vector_Gcd(&(polyhedron
->Constraint
[i
][1]),dimension
-2,&gcd
) ;
1083 value_modulus(modulo
,polyhedron
->Constraint
[i
][dimension
-1],gcd
) ;
1085 if (value_notzero_p(modulo
)) {
1087 value_clear(modulo
);
1094 value_clear(modulo
);
1100 * cloog_domain_stride function:
1101 * This function finds the stride imposed to unknown with the column number
1102 * 'strided_level' in order to be integral. For instance, if we have a
1103 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
1104 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
1105 * the unknown i. The function returns the imposed stride in a parameter field.
1106 * - domain is the set of constraint we have to consider,
1107 * - strided_level is the column number of the unknown for which a stride have
1109 * - looking_level is the column number of the unknown that impose a stride to
1110 * the first unknown.
1111 * - stride is the stride that is returned back as a function parameter.
1112 * - offset is the value of the constant c if the condition is of the shape
1113 * (i + c)%s = 0, s being the stride.
1115 * - June 28th 2003: first version.
1116 * - July 14th 2003: can now look for multiple striding constraints and returns
1117 * the GCD of the strides and the common offset.
1118 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1121 void cloog_domain_stride(CloogDomain
*domain
, int strided_level
,
1122 Value
*stride
, Value
*offset
)
1124 Polyhedron
* polyhedron
;
1125 int n_col
, n_row
, rank
;
1130 polyhedron
= domain
->polyhedron
;
1131 dimension
= polyhedron
->Dimension
;
1133 /* Look at all equalities involving strided_level and the inner
1134 * iterators. We can ignore the outer iterators and the parameters
1135 * here because the lower bound on strided_level is assumed to
1138 n_col
= (1+dimension
-domain
->nb_par
) - strided_level
;
1139 for (i
=0, n_row
=0; i
< polyhedron
->NbEq
; i
++)
1140 if (First_Non_Zero(polyhedron
->Constraint
[i
]+strided_level
, n_col
) != -1)
1143 M
= cloog_polylib_matrix_alloc(n_row
+1, n_col
+1);
1144 for (i
=0, n_row
= 0; i
< polyhedron
->NbEq
; i
++) {
1145 if (First_Non_Zero(polyhedron
->Constraint
[i
]+strided_level
, n_col
) == -1)
1147 Vector_Copy(polyhedron
->Constraint
[i
]+strided_level
, M
->p
[n_row
], n_col
);
1148 value_assign(M
->p
[n_row
][n_col
], polyhedron
->Constraint
[i
][1+dimension
]);
1151 value_set_si(M
->p
[n_row
][n_col
], 1);
1153 /* Then look at the general solution to the above equalities. */
1154 rank
= SolveDiophantine(M
, &U
, &V
);
1155 cloog_polylib_matrix_free(M
);
1158 /* There is no solution, so the body of this loop will
1159 * never execute. We just leave the constraints alone here so
1160 * that they will ensure the body will not be executed.
1161 * We should probably propagate this information up so that
1162 * the loop can be removed entirely.
1164 value_set_si(*offset
, 0);
1165 value_set_si(*stride
, 1);
1167 value_oppose(*offset
, V
->p
[0]);
1168 /* If rank == M->NbRows, i.e., if there is a unique fixed solution,
1169 * then SolveDiophantine will return a 0x0 U matrix.
1170 * In this case, v = 0 * x + v, so we set stride to 0.
1173 value_set_si(*stride
, 0);
1175 /* Compute the gcd of the coefficients defining strided_level. */
1176 Vector_Gcd(U
->p
[0], U
->NbColumns
, stride
);
1177 value_pmodulus(*offset
, *offset
, *stride
);
1188 * cloog_domain_integral_lowerbound function:
1189 * This function returns 1 if the lower bound of an iterator (such as its
1190 * column rank in the constraint set 'domain' is 'level') is integral,
1191 * 0 otherwise. If the lower bound is actually integral, the function fills
1192 * the 'lower' field with the lower bound value.
1193 * - June 29th 2003: first version.
1194 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1197 int cloog_domain_integral_lowerbound(domain
, level
, lower
)
1198 CloogDomain
* domain
;
1201 { int i
, first_lower
=1, dimension
, lower_constraint
=-1 ;
1202 Value iterator
, constant
, tmp
;
1203 Polyhedron
* polyhedron
;
1205 polyhedron
= domain
->polyhedron
;
1206 dimension
= polyhedron
->Dimension
;
1208 /* We want one and only one lower bound (e.g. no equality, no maximum
1211 for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
1212 if (value_zero_p(polyhedron
->Constraint
[i
][0]) &&
1213 value_notzero_p(polyhedron
->Constraint
[i
][level
]))
1216 for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
1217 if (value_pos_p(polyhedron
->Constraint
[i
][level
]))
1220 lower_constraint
= i
;
1228 /* We want an integral lower bound: no other non-zero entry except the
1229 * iterator coefficient and the constant.
1231 for (i
=1; i
<level
; i
++)
1232 if (value_notzero_p(polyhedron
->Constraint
[lower_constraint
][i
]))
1234 for (i
=level
+1; i
<=polyhedron
->Dimension
; i
++)
1235 if (value_notzero_p(polyhedron
->Constraint
[lower_constraint
][i
]))
1238 value_init(iterator
);
1239 value_init(constant
);
1242 /* If all is passed, then find the lower bound and return 1. */
1243 value_assign(iterator
, polyhedron
->Constraint
[lower_constraint
][level
]) ;
1244 value_oppose(constant
, polyhedron
->Constraint
[lower_constraint
][dimension
+1]);
1246 value_modulus(tmp
, constant
, iterator
) ;
1247 value_division(*lower
, constant
, iterator
) ;
1249 if (!(value_zero_p(tmp
) || value_neg_p(constant
)))
1250 value_increment(*lower
, *lower
) ;
1252 value_clear(iterator
);
1253 value_clear(constant
);
1261 * cloog_domain_lowerbound_update function:
1262 * This function updates the integral lower bound of an iterator (such as its
1263 * column rank in the constraint set 'domain' is 'level') into 'lower'
1264 * and returns the updated domain.
1265 * - Jun 29th 2003: first version.
1266 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1269 CloogDomain
*cloog_domain_lowerbound_update(CloogDomain
*domain
, int level
,
1272 Polyhedron
* polyhedron
;
1274 polyhedron
= domain
->polyhedron
;
1276 /* There is only one lower bound, the first one is the good one. */
1277 for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
1278 if (value_pos_p(polyhedron
->Constraint
[i
][level
]))
1279 { value_set_si(polyhedron
->Constraint
[i
][level
], 1) ;
1280 value_oppose(polyhedron
->Constraint
[i
][polyhedron
->Dimension
+1], lower
) ;
1288 * cloog_domain_lazy_equal function:
1289 * This function returns 1 if the domains given as input are the same, 0 if it
1290 * is unable to decide. This function makes an entry-to-entry comparison between
1291 * the constraint systems, if all the entries are the same, the domains are
1292 * obviously the same and it returns 1, at the first difference, it returns 0.
1293 * This is a very fast way to verify this property. It has been shown (with the
1294 * CLooG benchmarks) that operations on equal domains are 17% of all the
1295 * polyhedral computations. For 75% of the actually identical domains, this
1296 * function answer that they are the same and allow to give immediately the
1297 * trivial solution instead of calling the heavy general functions of PolyLib.
1298 * - August 22th 2003: first version.
1299 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1302 int cloog_domain_lazy_equal(CloogDomain
* d1
, CloogDomain
* d2
)
1303 { int i
, nb_elements
;
1304 Polyhedron
* p1
, * p2
;
1306 p1
= d1
->polyhedron
;
1307 p2
= d2
->polyhedron
;
1309 while ((p1
!= NULL
) && (p2
!= NULL
))
1310 { if ((p1
->NbConstraints
!= p2
->NbConstraints
) ||
1311 (p1
->Dimension
!= p2
->Dimension
))
1314 nb_elements
= p1
->NbConstraints
* (p1
->Dimension
+ 2) ;
1316 for (i
=0;i
<nb_elements
;i
++)
1317 if (value_ne(p1
->p_Init
[i
], p2
->p_Init
[i
]))
1324 if ((p1
!= NULL
) || (p2
!= NULL
))
1332 * cloog_scattering_lazy_block function:
1333 * This function returns 1 if the two domains d1 and d2 given as input are the
1334 * same (possibly except for a dimension equal to a constant where we accept
1335 * a difference of 1) AND if we are sure that there are no other domain in
1336 * the code generation problem that may put integral points between those of
1337 * d1 and d2 (0 otherwise). In fact this function answers the question "can I
1338 * safely consider the two domains as only one with two statements (a block) ?".
1339 * The original implementation had a problem and has therefore been
1340 * (temporarily) replaced by the safest possible implementation: always
1341 * assume that we cannot block the two statements.
1342 * - d1 and d2 are the two domains to check for blocking,
1343 * - scattering is the linked list of all domains,
1344 * - scattdims is the total number of scattering dimentions.
1346 int cloog_scattering_lazy_block(CloogScattering
*d1
, CloogScattering
*d2
,
1347 CloogScatteringList
*scattering
, int scattdims
)
1354 * cloog_domain_lazy_disjoint function:
1355 * This function returns 1 if the domains given as input are disjoint, 0 if it
1356 * is unable to decide. This function finds the unknown with fixed values in
1357 * both domains (on a given constraint, their column entry is not zero and
1358 * only the constant coefficient can be different from zero) and verify that
1359 * their values are the same. If not, the domains are obviously disjoint and
1360 * it returns 1, if there is not such case it returns 0. This is a very fast
1361 * way to verify this property. It has been shown (with the CLooG benchmarks)
1362 * that operations on disjoint domains are 36% of all the polyhedral
1363 * computations. For 94% of the actually identical domains, this
1364 * function answer that they are disjoint and allow to give immediately the
1365 * trivial solution instead of calling the heavy general functions of PolyLib.
1366 * - August 22th 2003: first version.
1367 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1370 int cloog_domain_lazy_disjoint(CloogDomain
* d1
, CloogDomain
* d2
)
1371 { int i1
, j1
, i2
, j2
, scat_dim
;
1373 Polyhedron
* p1
, * p2
;
1375 p1
= d1
->polyhedron
;
1376 p2
= d2
->polyhedron
;
1378 if ((p1
->next
!= NULL
) || (p2
->next
!= NULL
))
1381 value_init(scat_val
);
1383 for (i1
=0; i1
<p1
->NbConstraints
; i1
++)
1384 { if (value_notzero_p(p1
->Constraint
[i1
][0]))
1388 while (value_zero_p(p1
->Constraint
[i1
][scat_dim
]) &&
1389 (scat_dim
< p1
->Dimension
))
1392 if (value_notone_p(p1
->Constraint
[i1
][scat_dim
]))
1395 { for (j1
=scat_dim
+1; j1
<=p1
->Dimension
; j1
++)
1396 if (value_notzero_p(p1
->Constraint
[i1
][j1
]))
1399 if (j1
!= p1
->Dimension
+1)
1402 value_assign(scat_val
,p1
->Constraint
[i1
][p1
->Dimension
+1]) ;
1404 for (i2
=0; i2
<p2
->NbConstraints
; i2
++)
1405 { for (j2
=0;j2
<scat_dim
;j2
++)
1406 if (value_notzero_p(p2
->Constraint
[i2
][j2
]))
1409 if ((j2
!= scat_dim
) || value_notone_p(p2
->Constraint
[i2
][scat_dim
]))
1412 for (j2
=scat_dim
+1; j2
<=p2
->Dimension
; j2
++)
1413 if (value_notzero_p(p2
->Constraint
[i2
][j2
]))
1416 if (j2
!= p2
->Dimension
+1)
1419 if (value_ne(p2
->Constraint
[i2
][p2
->Dimension
+1],scat_val
)) {
1420 value_clear(scat_val
);
1427 value_clear(scat_val
);
1433 * cloog_scattering_list_lazy_same function:
1434 * This function returns 1 if two domains in the list are the same, 0 if it
1435 * is unable to decide.
1436 * - February 9th 2004: first version.
1438 int cloog_scattering_list_lazy_same(CloogScatteringList
* list
)
1439 { /*int i=1, j=1 ;*/
1440 CloogScatteringList
* current
, * next
;
1443 while (current
!= NULL
)
1444 { next
= current
->next
;
1446 while (next
!= NULL
) {
1447 if (cloog_domain_lazy_equal(¤t
->scatt
->dom
, &next
->scatt
->dom
))
1448 { /*printf("Same domains: %d and %d\n",i,j) ;*/
1455 current
= current
->next
;
1463 * Those functions are provided for "object encapsulation", to separate as much
1464 * as possible the inside of the CloogDomain structure from the rest of the
1465 * program, in order to ease the change of polyhedral library. For efficiency
1466 * reasons, they are defined and used as macros in domain.h.
1467 * - April 20th 2005: setting.
1469 Polyhedron * cloog_domain_polyhedron(CloogDomain * domain)
1470 { return domain->polyhedron ;
1473 int cloog_domain_nbconstraints(CloogDomain * domain)
1474 { return domain->polyhedron->NbConstraints ;
1478 int cloog_domain_dimension(CloogDomain
* domain
)
1480 return domain
->polyhedron
->Dimension
- domain
->nb_par
;
1483 int cloog_domain_parameter_dimension(CloogDomain
*domain
)
1485 return domain
->nb_par
;
1488 int cloog_scattering_dimension(CloogScattering
*scatt
, CloogDomain
*domain
)
1490 return cloog_domain_dimension(&scatt
->dom
) - cloog_domain_dimension(domain
);
1493 int cloog_domain_isconvex(CloogDomain
* domain
)
1494 { return (domain
->polyhedron
->next
== NULL
)? 1 : 0 ;
1499 * cloog_domain_cut_first function:
1500 * This function splits off and returns the first convex set in the
1501 * union "domain". The remainder of the union is returned in rest.
1502 * The original "domain" itself is destroyed and may not be used
1503 * after a call to this function.
1505 CloogDomain
*cloog_domain_cut_first(CloogDomain
*domain
, CloogDomain
**rest
)
1507 if (!domain
|| !domain
->polyhedron
|| cloog_domain_isconvex(domain
)) {
1512 if (domain
->references
== 1) {
1513 *rest
= cloog_domain_from_polylib_polyhedron(domain
->state
,
1514 domain
->polyhedron
->next
, domain
->nb_par
);
1515 domain
->polyhedron
->next
= NULL
;
1519 cloog_domain_free(domain
);
1520 *rest
= cloog_domain_from_polylib_polyhedron(domain
->state
, Domain_Copy(domain
->polyhedron
->next
),
1522 return cloog_domain_from_polylib_polyhedron(domain
->state
,
1523 Polyhedron_Copy(domain
->polyhedron
), domain
->nb_par
);
1528 * Given a union domain, try to find a simpler representation
1529 * using fewer sets in the union.
1530 * Since PolyLib does not have a proper implementation for this
1531 * functionality, we compute
1532 * convex(domain) \ (convex(domain) \ domain)
1533 * which usually approximates what we want.
1534 * The original "domain" itself is destroyed and may not be used
1535 * after a call to this function.
1537 CloogDomain
*cloog_domain_simplify_union(CloogDomain
*domain
)
1539 CloogDomain
*convex
, *temp
;
1541 convex
= cloog_domain_convex(domain
);
1542 temp
= cloog_domain_difference(convex
, domain
);
1543 cloog_domain_free(domain
);
1544 domain
= cloog_domain_difference(convex
, temp
);
1545 cloog_domain_free(convex
);
1546 cloog_domain_free(temp
);
1552 static int polyhedron_lazy_isconstant(Polyhedron
*polyhedron
, int dimension
,
1557 /* For each constraint... */
1558 for (i
=0;i
<polyhedron
->NbConstraints
;i
++)
1559 { /* ...if it is concerned by the potentially scalar dimension... */
1560 if (value_notzero_p(polyhedron
->Constraint
[i
][dimension
+1]))
1561 { /* ...check that the constraint has the shape "dimension + scalar = 0". */
1562 for (j
=0;j
<=dimension
;j
++)
1563 if (value_notzero_p(polyhedron
->Constraint
[i
][j
]))
1566 if (value_notone_p(polyhedron
->Constraint
[i
][dimension
+1]))
1569 for (j
=dimension
+2;j
<(polyhedron
->Dimension
+ 1);j
++)
1570 if (value_notzero_p(polyhedron
->Constraint
[i
][j
]))
1574 value_assign(*value
,polyhedron
->Constraint
[i
][polyhedron
->Dimension
+1]);
1575 value_oppose(*value
,*value
);
1586 * cloog_scattering_lazy_isscalar function:
1587 * this function returns 1 if the dimension 'dimension' in the domain 'domain'
1588 * is scalar, this means that the only constraint on this dimension must have
1589 * the shape "x.dimension + scalar = 0" with x an integral variable. This
1590 * function is lazy since we only accept x=1 (further calculations are easier
1592 * If value is not NULL, then it is set to the constant value of dimension.
1593 * - June 14th 2005: first version.
1594 * - June 21rd 2005: Adaptation for GMP.
1596 int cloog_scattering_lazy_isscalar(CloogScattering
*domain
, int dimension
,
1599 return polyhedron_lazy_isconstant(domain
->dom
.polyhedron
, dimension
, value
);
1604 * cloog_domain_lazy_isconstant function:
1605 * this function returns 1 if the dimension 'dimension' in the
1606 * domain 'domain' is constant.
1607 * If value is not NULL, then it is set to the constant value of dimension.
1609 int cloog_domain_lazy_isconstant(CloogDomain
*domain
, int dimension
)
1611 return polyhedron_lazy_isconstant(domain
->polyhedron
, dimension
, NULL
);
1616 * cloog_scattering_erase_dimension function:
1617 * this function returns a CloogDomain structure builds from 'domain' where
1618 * we removed the dimension 'dimension' and every constraint considering this
1619 * dimension. This is not a projection ! Every data concerning the
1620 * considered dimension is simply erased.
1621 * - June 14th 2005: first version.
1622 * - June 21rd 2005: Adaptation for GMP.
1624 CloogScattering
*cloog_scattering_erase_dimension(CloogScattering
*scatt
,
1626 { int i
, j
, mi
, nb_dim
;
1628 CloogDomain
* erased
;
1629 Polyhedron
* polyhedron
;
1630 CloogDomain
*domain
;
1632 domain
= &scatt
->dom
;
1633 polyhedron
= domain
->polyhedron
;
1634 nb_dim
= polyhedron
->Dimension
;
1636 /* The matrix is one column less and at least one constraint less. */
1637 matrix
= cloog_polylib_matrix_alloc(polyhedron
->NbConstraints
-1,nb_dim
+1) ;
1639 /* mi is the constraint counter for the matrix. */
1641 for (i
=0;i
<polyhedron
->NbConstraints
;i
++)
1642 if (value_zero_p(polyhedron
->Constraint
[i
][dimension
+1]))
1643 { for (j
=0;j
<=dimension
;j
++)
1644 value_assign(matrix
->p
[mi
][j
],polyhedron
->Constraint
[i
][j
]) ;
1646 for (j
=dimension
+2;j
<nb_dim
+2;j
++)
1647 value_assign(matrix
->p
[mi
][j
-1],polyhedron
->Constraint
[i
][j
]) ;
1652 erased
= cloog_domain_polylib_matrix2domain(domain
->state
, matrix
, domain
->nb_par
);
1653 cloog_polylib_matrix_free(matrix
) ;
1655 return (CloogScattering
*)erased
;
1660 * cloog_domain_cube:
1661 * Construct and return a dim-dimensional cube, with values ranging
1662 * between min and max in each dimension.
1664 CloogDomain
*cloog_domain_cube(CloogState
*state
,
1665 int dim
, cloog_int_t min
, cloog_int_t max
)
1671 M
= Matrix_Alloc(2*dim
, 2+dim
);
1672 for (i
= 0; i
< dim
; ++i
) {
1673 value_set_si(M
->p
[2*i
][0], 1);
1674 value_set_si(M
->p
[2*i
][1+i
], 1);
1675 value_oppose(M
->p
[2*i
][1+dim
], min
);
1676 value_set_si(M
->p
[2*i
+1][0], 1);
1677 value_set_si(M
->p
[2*i
+1][1+i
], -1);
1678 value_assign(M
->p
[2*i
+1][1+dim
], max
);
1680 P
= Constraints2Polyhedron(M
, state
->backend
->MAX_RAYS
);
1682 return cloog_domain_from_polylib_polyhedron(state
, P
, 0);
1686 * cloog_domain_scatter function:
1687 * This function add the scattering (scheduling) informations in a domain.
1689 CloogDomain
*cloog_domain_scatter(CloogDomain
*domain
, CloogScattering
*scatt
)
1691 CloogDomain
*ext
, *newdom
, *newpart
, *temp
;
1694 scatt_dim
= cloog_scattering_dimension(scatt
, domain
);
1696 /* For each polyhedron of domain (it can be an union of polyhedra). */
1697 while (domain
!= NULL
)
1698 { /* Extend the domain by adding the scattering dimensions as the new
1699 * first domain dimensions.
1701 domain
->nb_par
= domain
->polyhedron
->Dimension
;
1702 ext
= cloog_domain_extend(domain
, scatt_dim
);
1703 ext
->nb_par
= domain
->nb_par
= scatt
->dom
.nb_par
;
1704 /* Then add the scattering constraints. */
1705 newpart
= cloog_domain_addconstraints(&scatt
->dom
, ext
);
1706 cloog_domain_free(ext
) ;
1710 newdom
= cloog_domain_union(newdom
,newpart
) ;
1711 cloog_domain_free(temp
) ;
1712 cloog_domain_free(newpart
) ;
1717 /* We don't want to free the rest of the list. */
1718 temp
= cloog_domain_cut_first(domain
, &domain
);
1719 cloog_domain_free(temp
) ;