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 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 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 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 CloogMatrix
* cloog_domain_domain2matrix(CloogDomain
* domain
)
150 { cloog_matrix_leak_up() ;
151 return 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_simplify function:
248 * Given two polyhedral domains (pol1) and (pol2) inside two CloogDomain
249 * structures, this function finds the largest domain set (or the smallest list
250 * of non-redundant constraints), that when intersected with polyhedral
251 * domain (pol2) equals (Pol1)intersect(Pol2). The output is a new CloogDomain
252 * structure with a polyhedral domain with the "redundant" constraints removed.
253 * NB: this function do not work as expected with unions of polyhedra...
255 CloogDomain
* cloog_domain_simplify(CloogDomain
* dom1
, CloogDomain
* dom2
)
256 { return (cloog_domain_alloc(DomainSimplify(dom1
->polyhedron
,
257 dom2
->polyhedron
,MAX_RAYS
))) ;
262 * cloog_domain_union function:
263 * This function returns a new CloogDomain structure including a polyhedral
264 * domain which is the union of two polyhedral domains (pol1) U (pol2) inside
265 * two CloogDomain structures.
267 CloogDomain
* cloog_domain_union(CloogDomain
* dom1
, CloogDomain
* dom2
)
268 { return (cloog_domain_alloc(DomainUnion(dom1
->polyhedron
,
269 dom2
->polyhedron
,MAX_RAYS
))) ;
274 * cloog_domain_disjoint function:
275 * This function returns a new CloogDomain structure including a polyhedral
276 * domain represented using union of *disjoint* polyhedra (no intersection
277 * between the different union components).
279 CloogDomain
* cloog_domain_disjoint(CloogDomain
* dom
)
280 { return (cloog_domain_alloc(Disjoint_Domain(dom
->polyhedron
,0,MAX_RAYS
))) ;
285 * cloog_domain_intersection function:
286 * This function returns a new CloogDomain structure including a polyhedral
287 * domain which is the intersection of two polyhedral domains (pol1)inter(pol2)
288 * inside two CloogDomain structures.
290 CloogDomain
* cloog_domain_intersection(CloogDomain
* dom1
, CloogDomain
* dom2
)
291 { return (cloog_domain_alloc(DomainIntersection(dom1
->polyhedron
,
292 dom2
->polyhedron
,MAX_RAYS
))) ;
297 * cloog_domain_difference function:
298 * This function returns a new CloogDomain structure including a polyhedral
299 * domain which is the difference of two polyhedral domains domain \ minus
300 * inside two CloogDomain structures.
301 * - November 8th 2001: first version.
303 CloogDomain
* cloog_domain_difference(CloogDomain
* domain
, CloogDomain
* minus
)
304 { if (cloog_domain_isempty(minus
))
305 return(cloog_domain_copy(domain
)) ;
307 return (cloog_domain_alloc(DomainDifference(domain
->polyhedron
,
308 minus
->polyhedron
,MAX_RAYS
))) ;
313 * cloog_domain_includes function:
314 * This function returns 1 if the polyhedral domain inside 'container' includes
315 * the polyhedral domain inside 'contents', 0 otherwise.
316 * - September 14th 2002: first version.
318 int cloog_domain_includes(CloogDomain
* container
, CloogDomain
* contents
)
320 Polyhedron
* p1
, * p2
;
322 for (p1
=container
->polyhedron
; p1
; p1
=p1
->next
)
325 for (p2
=contents
->polyhedron
; p2
; p2
=p2
->next
)
326 if (PolyhedronIncludes(p1
,p2
))
340 * cloog_domain_addconstraints function :
341 * This function adds source's polyhedron constraints to target polyhedron: for
342 * each element of the polyhedron inside 'target' (i.e. element of the union
343 * of polyhedra) it adds the constraints of the corresponding element in
345 * - August 10th 2002: first version.
346 * Nota bene for future : it is possible that source and target don't have the
347 * same number of elements (try iftest2 without non-shared constraint
348 * elimination in cloog_loop_separate !). This function is yet another part
349 * of the DomainSimplify patching problem...
351 CloogDomain
* cloog_domain_addconstraints(domain_source
, domain_target
)
352 CloogDomain
* domain_source
, * domain_target
;
353 { unsigned nb_constraint
;
354 Value
* constraints
;
355 Polyhedron
* source
, * target
, * new, * next
, * last
;
357 source
= domain_source
->polyhedron
;
358 target
= domain_target
->polyhedron
;
360 constraints
= source
->p_Init
;
361 nb_constraint
= source
->NbConstraints
;
362 source
= source
->next
;
363 new = AddConstraints(constraints
,nb_constraint
,target
,MAX_RAYS
) ;
365 next
= target
->next
;
368 { /* BUG !!! This is actually a bug. I don't know yet how to cleanly avoid
369 * the situation where source and target do not have the same number of
370 * elements. So this 'if' is an awful trick, waiting for better.
373 { constraints
= source
->p_Init
;
374 nb_constraint
= source
->NbConstraints
;
375 source
= source
->next
;
377 last
->next
= AddConstraints(constraints
,nb_constraint
,next
,MAX_RAYS
) ;
382 return (cloog_domain_alloc(new)) ;
387 * cloog_domain_sort function:
388 * This function topologically sorts (nb_pols) polyhedra. Here (pols) is a an
389 * array of pointers to polyhedra, (nb_pols) is the number of polyhedra,
390 * (level) is the level to consider for partial ordering (nb_par) is the
391 * parameter space dimension, (permut) if not NULL, is an array of (nb_pols)
392 * integers that contains a permutation specification after call in order to
393 * apply the topological sorting.
395 void cloog_domain_sort(pols
, nb_pols
, level
, nb_par
, permut
)
397 unsigned nb_pols
, level
, nb_par
;
401 /* time is an array of (nb_pols) integers to store logical time values. We
402 * do not use it, but it is compulsory for PolyhedronTSort.
404 time
= (int *)malloc(nb_pols
*sizeof(int)) ;
406 /* PolyhedronTSort will fill up permut (and time). */
407 PolyhedronTSort(pols
,nb_pols
,level
,nb_par
,time
,permut
,MAX_RAYS
) ;
414 * cloog_domain_empty function:
415 * This function allocates the memory space for a CloogDomain structure and
416 * sets its polyhedron to an empty polyhedron with 'dimension' dimensions.
417 * Then it returns a pointer to the allocated space.
418 * - June 10th 2005: first version.
420 CloogDomain
* cloog_domain_empty(int dimension
)
421 { return (cloog_domain_alloc(Empty_Polyhedron(dimension
))) ;
425 /******************************************************************************
426 * Structure display function *
427 ******************************************************************************/
431 * cloog_domain_print_structure :
432 * this function is a more human-friendly way to display the CloogDomain data
433 * structure, it only shows the constraint system and includes an indentation
434 * level (level) in order to work with others print_structure functions.
435 * Written by Olivier Chorier, Luc Marchaud, Pierre Martin and Romain Tartiere.
436 * - April 24th 2005: Initial version.
437 * - May 26th 2005: Memory leak hunt.
438 * - June 16th 2005: (Ced) Integration in domain.c.
440 void cloog_domain_print_structure(FILE * file
, CloogDomain
* domain
, int level
)
442 CloogMatrix
* matrix
;
444 /* Go to the right level. */
445 for(i
=0; i
<level
; i
++)
446 fprintf(file
,"|\t") ;
449 { fprintf(file
,"+-- CloogDomain\n") ;
451 /* Print the matrix. */
452 matrix
= cloog_domain_domain2matrix(domain
) ;
453 cloog_matrix_print_structure(file
,matrix
,level
) ;
454 cloog_matrix_free(matrix
) ;
457 for (i
=0; i
<level
+1; i
++)
458 fprintf(file
,"|\t") ;
462 fprintf(file
,"+-- Null CloogDomain\n") ;
468 * cloog_domain_list_print function:
469 * This function prints the content of a CloogDomainList structure into a
470 * file (foo, possibly stdout).
471 * - November 6th 2001: first version.
473 void cloog_domain_list_print(FILE * foo
, CloogDomainList
* list
)
474 { while (list
!= NULL
)
475 { cloog_domain_print(foo
,list
->domain
) ;
481 /******************************************************************************
482 * Memory deallocation function *
483 ******************************************************************************/
487 * cloog_domain_list_free function:
488 * This function frees the allocated memory for a CloogDomainList structure.
489 * - November 6th 2001: first version.
491 void cloog_domain_list_free(CloogDomainList
* list
)
492 { CloogDomainList
* temp
;
495 { temp
= list
->next
;
496 cloog_domain_free(list
->domain
) ;
503 /******************************************************************************
505 ******************************************************************************/
509 * cloog_domain_read function:
510 * Adaptation from the PolyLib. This function reads a matrix into a file (foo,
511 * posibly stdin) and returns a pointer to a polyhedron containing the read
513 * - October 18th 2001: first version.
515 CloogDomain
* cloog_domain_read(FILE * foo
)
516 { CloogMatrix
* matrix
;
517 CloogDomain
* domain
;
519 matrix
= cloog_matrix_read(foo
) ;
520 domain
= cloog_domain_matrix2domain(matrix
) ;
521 cloog_matrix_free(matrix
) ;
528 * cloog_domain_union_read function:
529 * This function reads a union of polyhedra into a file (foo, posibly stdin) and
530 * returns a pointer to a Polyhedron containing the read information.
531 * - September 9th 2002: first version.
532 * - October 29th 2005: (debug) removal of a leak counting "correction" that
533 * was just false since ages.
535 CloogDomain
* cloog_domain_union_read(FILE * foo
)
536 { int i
, nb_components
;
538 CloogDomain
* domain
, * temp
, * old
;
540 /* domain reading: nb_components (constraint matrices). */
541 while (fgets(s
,MAX_STRING
,foo
) == 0) ;
542 while ((*s
=='#' || *s
=='\n') || (sscanf(s
," %d",&nb_components
)<1))
543 fgets(s
,MAX_STRING
,foo
) ;
545 if (nb_components
> 0)
546 { /* 1. first part of the polyhedra union, */
547 domain
= cloog_domain_read(foo
) ;
548 /* 2. and the nexts. */
549 for (i
=1;i
<nb_components
;i
++)
550 { /* Leak counting is OK since next allocated domain is freed here. */
551 temp
= cloog_domain_read(foo
) ;
553 domain
= cloog_domain_union(temp
,old
) ;
554 cloog_domain_free(temp
) ;
555 cloog_domain_free(old
) ;
565 * cloog_domain_list_read function:
566 * This function reads a list of polyhedra into a file (foo, posibly stdin) and
567 * returns a pointer to a CloogDomainList containing the read information.
568 * - November 6th 2001: first version.
570 CloogDomainList
* cloog_domain_list_read(FILE * foo
)
573 CloogDomainList
* list
, * now
, * next
;
576 /* We read first the number of polyhedra in the list. */
577 while (fgets(s
,MAX_STRING
,foo
) == 0) ;
578 while ((*s
=='#' || *s
=='\n') || (sscanf(s
," %d",&nb_pols
)<1))
579 fgets(s
,MAX_STRING
,foo
) ;
581 /* Then we read the polyhedra. */
584 { list
= (CloogDomainList
*)malloc(sizeof(CloogDomainList
)) ;
585 list
->domain
= cloog_domain_read(foo
) ;
588 for (i
=1;i
<nb_pols
;i
++)
589 { next
= (CloogDomainList
*)malloc(sizeof(CloogDomainList
)) ;
590 next
->domain
= cloog_domain_read(foo
) ;
600 /******************************************************************************
601 * Processing functions *
602 ******************************************************************************/
606 * cloog_domain_malloc function:
607 * This function allocates the memory space for a CloogDomain structure and
608 * sets its fields with default values. Then it returns a pointer to the
610 * - November 21th 2005: first version.
612 CloogDomain
* cloog_domain_malloc()
613 { CloogDomain
* domain
;
615 domain
= (CloogDomain
*)malloc(sizeof(CloogDomain
)) ;
617 { fprintf(stderr
, "[CLooG]ERROR: memory overflow.\n") ;
620 cloog_domain_leak_up() ;
622 /* We set the various fields with default values. */
623 domain
->polyhedron
= NULL
;
624 domain
->references
= 1 ;
631 * cloog_domain_alloc function:
632 * This function allocates the memory space for a CloogDomain structure and
633 * sets its fields with those given as input. Then it returns a pointer to the
635 * - April 19th 2005: first version.
636 * - November 21th 2005: cloog_domain_malloc use.
638 CloogDomain
* cloog_domain_alloc(Polyhedron
* polyhedron
)
639 { CloogDomain
* domain
;
641 if (polyhedron
== NULL
)
644 { domain
= cloog_domain_malloc() ;
645 domain
->polyhedron
= polyhedron
;
653 * cloog_domain_isempty function:
654 * This function returns 1 if the polyhedron given as input is empty, 0
656 * - October 28th 2001: first version.
658 int cloog_domain_isempty(CloogDomain
* domain
)
659 { if (domain
->polyhedron
== NULL
)
662 if (domain
->polyhedron
->next
)
664 return((domain
->polyhedron
->Dimension
< domain
->polyhedron
->NbEq
) ? 1 : 0) ;
669 * cloog_domain_universe function:
670 * This function returns 1 if the polyhedron given as input describe the
671 * universe of its dimension, 0 otherwise. Nb: the NbBid field of a polyhedron
672 * gives the number of bidirectionnal rays.
673 * - November 19th 2001: first version.
675 int cloog_domain_universe(CloogDomain
* domain
)
676 { if (domain
->polyhedron
->next
)
678 return((domain
->polyhedron
->Dimension
== domain
->polyhedron
->NbBid
) ? 1 : 0) ;
683 * cloog_domain_project function:
684 * From Quillere's LoopGen 0.4. This function returns the projection of
685 * (domain) on the (level) first dimensions (i.e. outer loops). It returns a
686 * pointer to the projected Polyhedron.
687 * - nb_par is the number of parameters.
689 * - October 27th 2001: first version.
690 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
693 CloogDomain
* cloog_domain_project(CloogDomain
* domain
, int level
, int nb_par
)
694 { int row
, column
, nb_rows
, nb_columns
, difference
;
695 CloogDomain
* projected_domain
;
696 CloogMatrix
* matrix
;
698 nb_rows
= level
+ nb_par
+ 1 ;
699 nb_columns
= domain
->polyhedron
->Dimension
+ 1 ;
700 difference
= nb_columns
- nb_rows
;
703 return(cloog_domain_copy(domain
)) ;
705 matrix
= cloog_matrix_alloc(nb_rows
,nb_columns
) ;
707 for (row
=0;row
<level
;row
++)
708 for (column
=0;column
<nb_columns
; column
++)
709 value_set_si(matrix
->p
[row
][column
],(row
== column
? 1 : 0)) ;
711 for (;row
<nb_rows
;row
++)
712 for (column
=0;column
<nb_columns
;column
++)
713 value_set_si(matrix
->p
[row
][column
],(row
+difference
== column
? 1 : 0)) ;
715 projected_domain
= cloog_domain_image(domain
,matrix
) ;
716 cloog_matrix_free(matrix
) ;
718 return(projected_domain
) ;
723 * cloog_domain_extend function:
724 * From Quillere's LoopGen 0.4. This function returns the (domain) given as
725 * input with (dim)+(nb_par) dimensions. The new dimensions are added before
726 * the (nb_par) parameters. This function does not free (domain), and returns
728 * - nb_par is the number of parameters.
730 * - October 27th 2001: first version.
731 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
734 CloogDomain
* cloog_domain_extend(CloogDomain
* domain
, int dim
, int nb_par
)
735 { int row
, column
, nb_rows
, nb_columns
, difference
;
736 CloogDomain
* extended_domain
;
737 CloogMatrix
* matrix
;
739 nb_rows
= 1 + domain
->polyhedron
->Dimension
;
740 nb_columns
= dim
+ nb_par
+ 1 ;
741 difference
= nb_columns
- nb_rows
;
744 return(cloog_domain_copy(domain
)) ;
746 matrix
= cloog_matrix_alloc(nb_rows
,nb_columns
) ;
748 for (row
=0;row
<domain
->polyhedron
->Dimension
-nb_par
;row
++)
749 for (column
=0;column
<nb_columns
;column
++)
750 value_set_si(matrix
->p
[row
][column
],(row
== column
? 1 : 0)) ;
752 for (;row
<=domain
->polyhedron
->Dimension
;row
++)
753 for (column
=0;column
<nb_columns
;column
++)
754 value_set_si(matrix
->p
[row
][column
],(row
+difference
== column
? 1 : 0)) ;
756 extended_domain
= cloog_domain_preimage(domain
,matrix
) ;
757 cloog_matrix_free(matrix
) ;
759 return(extended_domain
) ;
764 * cloog_domain_never_integral function:
765 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0. This
766 * function returns a boolean set to 1 if there is this kind of 'never true'
767 * constraint inside a polyhedron, 0 otherwise.
768 * - domain is the polyhedron to check,
770 * - November 28th 2001: first version.
771 * - June 26th 2003: for iterators, more 'never true' constraints are found
772 * (compare cholesky2 and vivien with a previous version),
773 * checking for the parameters created (compare using vivien).
774 * - June 28th 2003: Previously in loop.c and called
775 * cloog_loop_simplify_nevertrue, now here !
776 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
778 * - October 14th 2005: Complete rewriting, not faster but code quite shorter.
780 int cloog_domain_never_integral(CloogDomain
* domain
)
783 Polyhedron
* polyhedron
;
785 if ((domain
== NULL
) || (domain
->polyhedron
== NULL
))
789 value_init_c(modulo
) ;
790 polyhedron
= domain
->polyhedron
;
791 dimension
= polyhedron
->Dimension
+ 2 ;
793 /* For each constraint... */
794 for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
795 { /* If we have an equality and the scalar part is not zero... */
796 if (value_zero_p(polyhedron
->Constraint
[i
][0]) &&
797 value_notzero_p(polyhedron
->Constraint
[i
][dimension
-1]))
798 { /* Then we check whether the scalar can be divided by the gcd of the
799 * unknown vector (including iterators and parameters) or not. If not,
800 * there is no integer point in the polyhedron and we return 1.
802 Vector_Gcd(&(polyhedron
->Constraint
[i
][1]),dimension
-2,&gcd
) ;
803 value_modulus(modulo
,polyhedron
->Constraint
[i
][dimension
-1],gcd
) ;
805 if (value_notzero_p(modulo
))
806 { value_clear_c(gcd
) ;
807 value_clear_c(modulo
) ;
814 value_clear_c(modulo
) ;
820 * cloog_domain_stride function:
821 * This function finds the stride imposed to unknown with the column number
822 * 'strided_level' in order to be integral. For instance, if we have a
823 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
824 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
825 * the unknown i. The function returns the imposed stride in a parameter field.
826 * - domain is the set of constraint we have to consider,
827 * - strided_level is the column number of the unknown for which a stride have
829 * - looking_level is the column number of the unknown that impose a stride to
831 * - stride is the stride that is returned back as a function parameter.
832 * - offset is the value of the constant c if the condition is of the shape
833 * (i + c)%s = 0, s being the stride.
835 * - June 28th 2003: first version.
836 * - July 14th 2003: can now look for multiple striding constraints and returns
837 * the GCD of the strides and the common offset.
838 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
841 void cloog_domain_stride(domain
, strided_level
, nb_par
, stride
, offset
)
842 CloogDomain
* domain
;
843 int strided_level
, nb_par
;
844 Value
* stride
, * offset
;
845 { int i
, j
, valid
, looking_level
, looking_max
, dimension
;
846 Value looking_coeff
, strided_coeff
, ref_offset
, potential
, constant
, tmp
;
847 Polyhedron
* polyhedron
;
849 value_init_c(looking_coeff
) ;
850 value_init_c(strided_coeff
) ;
851 value_init_c(ref_offset
) ;
852 value_init_c(potential
) ;
853 value_init_c(constant
) ;
856 value_set_si(ref_offset
,0) ;
857 value_set_si(potential
,0) ;
858 value_set_si(*stride
,0) ;
860 polyhedron
= domain
->polyhedron
;
861 dimension
= polyhedron
->Dimension
;
863 /* Looking for a non-unit stride. */
864 looking_max
= dimension
- nb_par
+ 1 ;
865 for (looking_level
=strided_level
+1;looking_level
<looking_max
;looking_level
++)
866 { for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
867 { value_assign(strided_coeff
, polyhedron
->Constraint
[i
][strided_level
]) ;
868 value_assign(looking_coeff
, polyhedron
->Constraint
[i
][looking_level
]) ;
870 /* A potential interesting constraint is an equality such as the
871 * coefficient of the potentially non-unit strided iterator and the
872 * looking one are not zeros, and such as the looking coefficient do
873 * not divide the strided one.
876 if (value_zero_p(polyhedron
->Constraint
[i
][0]) &&
877 value_notzero_p(strided_coeff
) &&
878 value_notzero_p(looking_coeff
))
879 {value_modulus(tmp
, strided_coeff
, looking_coeff
) ;
880 if (value_notzero_p(tmp
))
881 { /* We verify that all the coefficient except the strided and the
882 * looking one give 0 by modulo looking_coef.
884 for (j
=1;j
<strided_level
;j
++)
885 { value_modulus(tmp
, polyhedron
->Constraint
[i
][j
], looking_coeff
) ;
886 if (value_notzero_p(tmp
))
893 for (j
=looking_level
+1; j
<=dimension
; j
++)
894 { value_modulus(tmp
, polyhedron
->Constraint
[i
][j
], looking_coeff
);
895 if (value_notzero_p(tmp
))
901 /* If there is a non-unit stride, we take its absolute value.*/
903 { value_assign(constant
, polyhedron
->Constraint
[i
][dimension
+1]) ;
904 value_modulus(*offset
, constant
, looking_coeff
) ;
906 if (value_pos_p(looking_coeff
))
907 value_assign(potential
, looking_coeff
) ;
909 value_oppose(potential
, looking_coeff
) ;
915 /* If a stride was found, we have to verify that the offset and the
916 * stride values are compatible with previous values (offsets must be the
917 * same, and we have to consider the GCD of the strides.
919 if (value_notzero_p(potential
))
920 { if (value_notzero_p(*stride
))
921 { if (value_ne(*offset
, ref_offset
))
922 { value_set_si(*offset
, 0) ;
923 value_set_si(*stride
, 1) ;
927 Gcd(*stride
,potential
,stride
);/* Gcd(a,b,*result) in polylib/vector.h */
930 { /* We set the reference values. */
931 value_assign(*stride
, potential
) ;
932 value_assign(ref_offset
, *offset
) ;
934 value_set_si(potential
, 0) ;
938 /* If no non-unit stride was found, this is because the stride is 1. */
939 if (value_zero_p(*stride
))
940 { value_set_si(*offset
, 0) ;
941 value_set_si(*stride
, 1) ;
944 value_clear_c(looking_coeff
) ;
945 value_clear_c(strided_coeff
) ;
946 value_clear_c(ref_offset
) ;
947 value_clear_c(potential
) ;
948 value_clear_c(constant
) ;
956 * cloog_domain_integral_lowerbound function:
957 * This function returns 1 if the lower bound of an iterator (such as its
958 * column rank in the constraint set 'domain' is 'level') is integral,
959 * 0 otherwise. If the lower bound is actually integral, the function fills
960 * the 'lower' field with the lower bound value.
961 * - June 29th 2003: first version.
962 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
965 int cloog_domain_integral_lowerbound(domain
, level
, lower
)
966 CloogDomain
* domain
;
969 { int i
, first_lower
=1, dimension
, lower_constraint
=-1 ;
970 Value iterator
, constant
, tmp
;
971 Polyhedron
* polyhedron
;
973 polyhedron
= domain
->polyhedron
;
974 dimension
= polyhedron
->Dimension
;
976 /* We want one and only one lower bound (e.g. no equality, no maximum
979 for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
980 if (value_zero_p(polyhedron
->Constraint
[i
][0]) &&
981 value_notzero_p(polyhedron
->Constraint
[i
][level
]))
984 for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
985 if (value_pos_p(polyhedron
->Constraint
[i
][level
]))
988 lower_constraint
= i
;
996 /* We want an integral lower bound: no other non-zero entry except the
997 * iterator coefficient and the constant.
999 for (i
=1; i
<level
; i
++)
1000 if (value_notzero_p(polyhedron
->Constraint
[lower_constraint
][i
]))
1002 for (i
=level
+1; i
<=polyhedron
->Dimension
; i
++)
1003 if (value_notzero_p(polyhedron
->Constraint
[lower_constraint
][i
]))
1006 value_init_c(iterator
) ;
1007 value_init_c(constant
) ;
1010 /* If all is passed, then find the lower bound and return 1. */
1011 value_assign(iterator
, polyhedron
->Constraint
[lower_constraint
][level
]) ;
1012 value_oppose(constant
, polyhedron
->Constraint
[lower_constraint
][dimension
+1]);
1014 value_modulus(tmp
, constant
, iterator
) ;
1015 value_division(*lower
, constant
, iterator
) ;
1017 if (!(value_zero_p(tmp
) || value_neg_p(constant
)))
1018 value_increment(*lower
, *lower
) ;
1020 value_clear_c(iterator
) ;
1021 value_clear_c(constant
) ;
1022 value_clear_c(tmp
) ;
1029 * cloog_domain_lowerbound_update function:
1030 * This function updates the integral lower bound of an iterator (such as its
1031 * column rank in the constraint set 'domain' is 'level') into 'lower'.
1032 * - Jun 29th 2003: first version.
1033 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1036 void cloog_domain_lowerbound_update(domain
, level
, lower
)
1037 CloogDomain
* domain
;
1041 Polyhedron
* polyhedron
;
1043 polyhedron
= domain
->polyhedron
;
1045 /* There is only one lower bound, the first one is the good one. */
1046 for (i
=0; i
<polyhedron
->NbConstraints
; i
++)
1047 if (value_pos_p(polyhedron
->Constraint
[i
][level
]))
1048 { value_set_si(polyhedron
->Constraint
[i
][level
], 1) ;
1049 value_oppose(polyhedron
->Constraint
[i
][polyhedron
->Dimension
+1], lower
) ;
1056 * cloog_domain_lazy_equal function:
1057 * This function returns 1 if the domains given as input are the same, 0 if it
1058 * is unable to decide. This function makes an entry-to-entry comparison between
1059 * the constraint systems, if all the entries are the same, the domains are
1060 * obviously the same and it returns 1, at the first difference, it returns 0.
1061 * This is a very fast way to verify this property. It has been shown (with the
1062 * CLooG benchmarks) that operations on equal domains are 17% of all the
1063 * polyhedral computations. For 75% of the actually identical domains, this
1064 * function answer that they are the same and allow to give immediately the
1065 * trivial solution instead of calling the heavy general functions of PolyLib.
1066 * - August 22th 2003: first version.
1067 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1070 int cloog_domain_lazy_equal(CloogDomain
* d1
, CloogDomain
* d2
)
1071 { int i
, nb_elements
;
1072 Polyhedron
* p1
, * p2
;
1074 p1
= d1
->polyhedron
;
1075 p2
= d2
->polyhedron
;
1077 while ((p1
!= NULL
) && (p2
!= NULL
))
1078 { if ((p1
->NbConstraints
!= p2
->NbConstraints
) ||
1079 (p1
->Dimension
!= p2
->Dimension
))
1082 nb_elements
= p1
->NbConstraints
* (p1
->Dimension
+ 2) ;
1084 for (i
=0;i
<nb_elements
;i
++)
1085 if (value_ne(p1
->p_Init
[i
], p2
->p_Init
[i
]))
1092 if ((p1
!= NULL
) || (p2
!= NULL
))
1100 * cloog_domain_lazy_block function:
1101 * This function returns 1 if the two domains d1 and d2 given as input are the
1102 * same (possibly except for a dimension equal to a constant where we accept
1103 * a difference of 1) AND if we are sure that there are no other domain in
1104 * the code generation problem that may put integral points between those of
1105 * d1 and d2 (0 otherwise). In fact this function answers the question "can I
1106 * safely consider the two domains as only one with two statements (a block) ?".
1107 * This function is lazy: it asks for very standard scattering representation
1108 * (only one constraint per dimension which is an equality, and the constraints
1109 * are ordered per dimension depth: the left hand side of the constraint matrix
1110 * is the identity) and will answer NO at the very first problem.
1111 * - d1 and d2 are the two domains to check for blocking,
1112 * - scattering is the linked list of all domains,
1113 * - scattdims is the total number of scattering dimentions.
1115 * - April 30th 2005: beginning
1116 * - June 9th 2005: first working version.
1117 * - June 10th 2005: debugging.
1118 * - June 21rd 2005: Adaptation for GMP.
1119 * - October 16th 2005: (debug) some false blocks have been removed.
1121 int cloog_domain_lazy_block(d1
, d2
, scattering
, scattdims
)
1122 CloogDomain
* d1
, * d2
;
1123 CloogDomainList
* scattering
;
1125 { int i
, j
, difference
=0, different_constraint
=0 ;
1126 Value date1
, date2
, date3
, temp
;
1127 Polyhedron
* p1
, * p2
, * p3
;
1129 p1
= d1
->polyhedron
;
1130 p2
= d2
->polyhedron
;
1132 /* Some basic checks: we only accept convex domains, with same constraint
1133 * and dimension numbers.
1135 if ((p1
->next
!= NULL
) || (p2
->next
!= NULL
) ||
1136 (p1
->NbConstraints
!= p2
->NbConstraints
) ||
1137 (p1
->Dimension
!= p2
->Dimension
))
1140 /* There should be only one difference between the two domains, it
1141 * has to be at the constant level and the difference must be of +1,
1142 * moreover, after the difference all domain coefficient has to be 0.
1143 * The matrix shape is:
1145 * |===========|=====|<- 0 line
1146 * |===========|=====|
1147 * |===========|====?|<- different_constraint line (found here)
1148 * |===========|0000=|
1149 * |===========|0000=|<- pX->NbConstraints line
1152 * | | (pX->Dimension + 2) column
1153 * | scattdims column
1157 value_init_c(temp
) ;
1158 for (i
=0;i
<p1
->NbConstraints
;i
++)
1159 { if (difference
== 0)
1160 { /* All elements except scalar must be equal. */
1161 for (j
=0;j
<(p1
->Dimension
+ 1);j
++)
1162 if (value_ne(p1
->Constraint
[i
][j
],p2
->Constraint
[i
][j
]))
1163 { value_clear_c(temp
) ;
1166 /* The scalar may differ from +1 (now j=(p1->Dimension + 1)). */
1167 if (value_ne(p1
->Constraint
[i
][j
],p2
->Constraint
[i
][j
]))
1168 { value_increment(temp
,p2
->Constraint
[i
][j
]) ;
1169 if (value_ne(p1
->Constraint
[i
][j
],temp
))
1170 { value_clear_c(temp
) ;
1175 different_constraint
= i
;
1180 { /* Scattering coefficients must be equal. */
1181 for (j
=0;j
<(scattdims
+1);j
++)
1182 if (value_ne(p1
->Constraint
[i
][j
],p2
->Constraint
[i
][j
]))
1183 { value_clear_c(temp
) ;
1187 /* Domain coefficients must be 0. */
1188 for (;j
<(p1
->Dimension
+ 1);j
++)
1189 if (value_notzero_p(p1
->Constraint
[i
][j
]) ||
1190 value_notzero_p(p2
->Constraint
[i
][j
]))
1191 { value_clear_c(temp
) ;
1195 /* Scalar must be equal. */
1196 if (value_ne(p1
->Constraint
[i
][j
],p2
->Constraint
[i
][j
]))
1197 { value_clear_c(temp
) ;
1202 value_clear_c(temp
) ;
1204 /* If the domains are exactly the same, this is a block. */
1205 if (difference
== 0)
1208 /* Now a basic check that the constraint with the difference is an
1209 * equality of a dimension with a constant.
1211 for (i
=0;i
<=different_constraint
;i
++)
1212 if (value_notzero_p(p1
->Constraint
[different_constraint
][i
]))
1215 if (value_notone_p(p1
->Constraint
[different_constraint
]
1216 [different_constraint
+1]))
1219 for (i
=different_constraint
+2;i
<(p1
->Dimension
+ 1);i
++)
1220 if (value_notzero_p(p1
->Constraint
[different_constraint
][i
]))
1223 /* For the moment, d1 and d2 are a block candidate. There remains to check
1224 * that there is no other domain that may put an integral point between
1225 * them. In our lazy test we ensure this property by verifying that the
1226 * constraint matrices have a very strict shape: let us consider that the
1227 * dimension with the difference is d. Then the first d dimensions are
1228 * defined in their depth order using equalities (thus the first column begins
1229 * with d zeroes, there is a d*d identity matrix and a zero-matrix for
1230 * the remaining simensions). If a domain can put integral points between the
1231 * domains of the block candidate, this means that the other entries on the
1232 * first d constraints are equal to those of d1 or d2. Thus we are looking for
1233 * such a constraint system, if it exists d1 and d2 is considered to not be
1234 * a block, it is a bock otherwise.
1236 * 1. Only equalities (for the first different_constraint+1 lines).
1237 * | 2. Must be the identity.
1238 * | | 3. Must be zero.
1239 * | | | 4. Elements are equal, the last one is either date1 or 2.
1242 * |0|100|00000|=====|<- 0 line
1243 * |0|010|00000|=====|
1244 * |0|001|00000|====?|<- different_constraint line
1245 * |*|***|*****|*****|
1246 * |*|***|*****|*****|<- pX->NbConstraints line
1249 * | | | (pX->Dimension + 2) column
1250 * | | scattdims column
1251 * | different_constraint+1 column
1255 /* Step 1 and 2. This is only necessary to check one domain because
1256 * we checked that they are equal on this part before.
1258 for (i
=0;i
<=different_constraint
;i
++)
1259 { for (j
=0;j
<i
+1;j
++)
1260 if (value_notzero_p(p1
->Constraint
[i
][j
]))
1263 if (value_notone_p(p1
->Constraint
[i
][i
+1]))
1266 for (j
=i
+2;j
<=different_constraint
+1;j
++)
1267 if (value_notzero_p(p1
->Constraint
[i
][j
]))
1272 for (i
=0;i
<=different_constraint
;i
++)
1273 for (j
=different_constraint
+2;j
<=scattdims
;j
++)
1274 if (value_notzero_p(p1
->Constraint
[i
][j
]))
1277 value_init_c(date1
) ;
1278 value_init_c(date2
) ;
1279 value_init_c(date3
) ;
1281 /* Now we have to check that the two different dates are unique. */
1282 value_assign(date1
, p1
->Constraint
[different_constraint
][p1
->Dimension
+ 1]) ;
1283 value_assign(date2
, p2
->Constraint
[different_constraint
][p2
->Dimension
+ 1]) ;
1285 /* Step 4. We check all domains except d1 and d2 and we look for at least
1286 * a difference with d1 or d2 on the first different_constraint+1 dimensions.
1288 while (scattering
!= NULL
)
1289 { if ((scattering
->domain
!= d1
) && (scattering
->domain
!= d2
))
1290 { p3
= scattering
->domain
->polyhedron
;
1291 value_assign(date3
,p3
->Constraint
[different_constraint
][p3
->Dimension
+1]);
1294 if (value_ne(date3
,date2
) && value_ne(date3
,date1
))
1297 for (i
=0;(i
<different_constraint
)&&(!difference
);i
++)
1298 for (j
=0;(j
<(p3
->Dimension
+ 2))&&(!difference
);j
++)
1299 if (value_ne(p1
->Constraint
[i
][j
],p3
->Constraint
[i
][j
]))
1302 for (j
=0;(j
<(p3
->Dimension
+ 1))&&(!difference
);j
++)
1303 if (value_ne(p1
->Constraint
[different_constraint
][j
],
1304 p3
->Constraint
[different_constraint
][j
]))
1308 { value_clear_c(date1
) ;
1309 value_clear_c(date2
) ;
1310 value_clear_c(date3
) ;
1315 scattering
= scattering
->next
;
1318 value_clear_c(date1
) ;
1319 value_clear_c(date2
) ;
1320 value_clear_c(date3
) ;
1326 * cloog_domain_lazy_disjoint function:
1327 * This function returns 1 if the domains given as input are disjoint, 0 if it
1328 * is unable to decide. This function finds the unknown with fixed values in
1329 * both domains (on a given constraint, their column entry is not zero and
1330 * only the constant coefficient can be different from zero) and verify that
1331 * their values are the same. If not, the domains are obviously disjoint and
1332 * it returns 1, if there is not such case it returns 0. This is a very fast
1333 * way to verify this property. It has been shown (with the CLooG benchmarks)
1334 * that operations on disjoint domains are 36% of all the polyhedral
1335 * computations. For 94% of the actually identical domains, this
1336 * function answer that they are disjoint and allow to give immediately the
1337 * trivial solution instead of calling the heavy general functions of PolyLib.
1338 * - August 22th 2003: first version.
1339 * - June 21rd 2005: Adaptation for GMP (based on S. Verdoolaege's version of
1342 int cloog_domain_lazy_disjoint(CloogDomain
* d1
, CloogDomain
* d2
)
1343 { int i1
, j1
, i2
, j2
, scat_dim
;
1345 Polyhedron
* p1
, * p2
;
1347 p1
= d1
->polyhedron
;
1348 p2
= d2
->polyhedron
;
1350 if ((p1
->next
!= NULL
) || (p2
->next
!= NULL
))
1353 value_init_c(scat_val
) ;
1355 for (i1
=0; i1
<p1
->NbConstraints
; i1
++)
1356 { if (value_notzero_p(p1
->Constraint
[i1
][0]))
1360 while (value_zero_p(p1
->Constraint
[i1
][scat_dim
]) &&
1361 (scat_dim
< p1
->Dimension
))
1364 if (value_notone_p(p1
->Constraint
[i1
][scat_dim
]))
1367 { for (j1
=scat_dim
+1; j1
<=p1
->Dimension
; j1
++)
1368 if (value_notzero_p(p1
->Constraint
[i1
][j1
]))
1371 if (j1
!= p1
->Dimension
+1)
1374 value_assign(scat_val
,p1
->Constraint
[i1
][p1
->Dimension
+1]) ;
1376 for (i2
=0; i2
<p2
->NbConstraints
; i2
++)
1377 { for (j2
=0;j2
<scat_dim
;j2
++)
1378 if (value_notzero_p(p2
->Constraint
[i2
][j2
]))
1381 if ((j2
!= scat_dim
) || value_notone_p(p2
->Constraint
[i2
][scat_dim
]))
1384 for (j2
=scat_dim
+1; j2
<p2
->Dimension
; j2
++)
1385 if (value_notzero_p(p2
->Constraint
[i2
][j2
]))
1388 if (j2
!= p2
->Dimension
)
1391 if (value_ne(p2
->Constraint
[i2
][p2
->Dimension
+1],scat_val
))
1392 { value_clear_c(scat_val
) ;
1399 value_clear_c(scat_val
) ;
1405 * cloog_domain_list_lazy_same function:
1406 * This function returns 1 if two domains in the list are the same, 0 if it
1407 * is unable to decide.
1408 * - February 9th 2004: first version.
1410 int cloog_domain_list_lazy_same(CloogDomainList
* list
)
1411 { /*int i=1, j=1 ;*/
1412 CloogDomainList
* current
, * next
;
1415 while (current
!= NULL
)
1416 { next
= current
->next
;
1418 while (next
!= NULL
)
1419 { if (cloog_domain_lazy_equal(current
->domain
,next
->domain
))
1420 { /*printf("Same domains: %d and %d\n",i,j) ;*/
1427 current
= current
->next
;
1435 * cloog_domain_grow function:
1436 * This function extend the polyhedron (domain) onto the dimension (level) by a
1437 * step of 1, if (lower) is 1 then the lower bound of the dimension is the same
1438 * minus one, if (lower) is 0 then the upper bound of the dimension is the
1439 * same plus one. This function frees the Polyhedron structure given as input
1440 * and returns the extended one.
1441 * - March 27th 2004: first version.
1442 * - June 21rd 2005: Adaptation for GMP.
1444 CloogDomain
* cloog_domain_grow(CloogDomain
* domain
, int level
, int lower
)
1445 { int i
, scalar_dim
;
1446 CloogMatrix
* matrix
;
1447 CloogDomain
* grow
;
1449 matrix
= cloog_domain_domain2matrix(domain
) ;
1450 cloog_domain_free(domain
) ;
1451 scalar_dim
= matrix
->NbColumns
- 1 ;
1453 for (i
=0;i
<matrix
->NbRows
;i
++)
1454 if (value_one_p(matrix
->p
[i
][0]))
1455 { if (((lower
== 1) && value_pos_p(matrix
->p
[i
][level
])) ||
1456 ((lower
== 0) && value_neg_p(matrix
->p
[i
][level
])))
1457 value_increment(matrix
->p
[i
][scalar_dim
],matrix
->p
[i
][scalar_dim
]) ;
1460 grow
= cloog_domain_matrix2domain(matrix
) ;
1461 cloog_matrix_free(matrix
) ;
1467 * Those functions are provided for "object encapsulation", to separate as much
1468 * as possible the inside of the CloogDomain structure from the rest of the
1469 * program, in order to ease the change of polyhedral library. For efficiency
1470 * reasons, they are defined and used as macros in domain.h.
1471 * - April 20th 2005: setting.
1473 Polyhedron * cloog_domain_polyhedron(CloogDomain * domain)
1474 { return domain->polyhedron ;
1477 int cloog_domain_dimension(CloogDomain * domain)
1478 { return domain->polyhedron->Dimension ;
1481 int cloog_domain_nbconstraints(CloogDomain * domain)
1482 { return domain->polyhedron->NbConstraints ;
1485 int cloog_domain_isconvex(CloogDomain * domain)
1486 { return (domain->polyhedron->next == NULL)? 1 : 0 ;
1492 * cloog_domain_cut_first function:
1493 * this function returns a CloogDomain structure with everything except the
1494 * first part of the polyhedra union of the input domain as domain. After a call
1495 * to this function, there remains in the CloogDomain structure provided as
1496 * input only the first part of the original polyhedra union.
1497 * - April 20th 2005: first version, extracted from different part of loop.c.
1499 CloogDomain
* cloog_domain_cut_first(CloogDomain
* domain
)
1500 { CloogDomain
* rest
;
1502 if ((domain
!= NULL
) && (domain
->polyhedron
!= NULL
))
1503 { rest
= cloog_domain_alloc(domain
->polyhedron
->next
) ;
1504 domain
->polyhedron
->next
= NULL
;
1514 * cloog_domain_lazy_isscalar function:
1515 * this function returns 1 if the dimension 'dimension' in the domain 'domain'
1516 * is scalar, this means that the only constraint on this dimension must have
1517 * the shape "x.dimension + scalar = 0" with x an integral variable. This
1518 * function is lazy since we only accept x=1 (further calculations are easier
1520 * - June 14th 2005: first version.
1521 * - June 21rd 2005: Adaptation for GMP.
1523 int cloog_domain_lazy_isscalar(CloogDomain
* domain
, int dimension
)
1525 Polyhedron
* polyhedron
;
1527 polyhedron
= domain
->polyhedron
;
1528 /* For each constraint... */
1529 for (i
=0;i
<polyhedron
->NbConstraints
;i
++)
1530 { /* ...if it is concerned by the potentially scalar dimension... */
1531 if (value_notzero_p(polyhedron
->Constraint
[i
][dimension
+1]))
1532 { /* ...check that the constraint has the shape "dimension + scalar = 0". */
1533 for (j
=0;j
<=dimension
;j
++)
1534 if (value_notzero_p(polyhedron
->Constraint
[i
][j
]))
1537 if (value_notone_p(polyhedron
->Constraint
[i
][dimension
+1]))
1540 for (j
=dimension
+2;j
<(polyhedron
->Dimension
+ 1);j
++)
1541 if (value_notzero_p(polyhedron
->Constraint
[i
][j
]))
1551 * cloog_domain_scalar function:
1552 * when we call this function, we know that "dimension" is a scalar dimension,
1553 * this function finds the scalar value in "domain" and returns it in "value".
1554 * - June 30th 2005: first version.
1556 void cloog_domain_scalar(CloogDomain
* domain
, int dimension
, Value
* value
)
1558 Polyhedron
* polyhedron
;
1560 polyhedron
= domain
->polyhedron
;
1561 /* For each constraint... */
1562 for (i
=0;i
<polyhedron
->NbConstraints
;i
++)
1563 { /* ...if it is the equality defining the scalar dimension... */
1564 if (value_notzero_p(polyhedron
->Constraint
[i
][dimension
+1]) &&
1565 value_zero_p(polyhedron
->Constraint
[i
][0]))
1566 { /* ...Then send the scalar value. */
1567 value_assign(*value
,polyhedron
->Constraint
[i
][polyhedron
->Dimension
+1]) ;
1568 value_oppose(*value
,*value
) ;
1573 /* We should have found a scalar value: if not, there is an error. */
1574 fprintf(stderr
, "[CLooG]ERROR: dimension %d is not scalar as expected.\n",
1581 * cloog_domain_erase_dimension function:
1582 * this function returns a CloogDomain structure builds from 'domain' where
1583 * we removed the dimension 'dimension' and every constraint considering this
1584 * dimension. This is not a projection ! Every data concerning the
1585 * considered dimension is simply erased.
1586 * - June 14th 2005: first version.
1587 * - June 21rd 2005: Adaptation for GMP.
1589 CloogDomain
* cloog_domain_erase_dimension(CloogDomain
* domain
, int dimension
)
1590 { int i
, j
, mi
, nb_dim
;
1591 CloogMatrix
* matrix
;
1592 CloogDomain
* erased
;
1593 Polyhedron
* polyhedron
;
1595 polyhedron
= domain
->polyhedron
;
1596 nb_dim
= polyhedron
->Dimension
;
1598 /* The matrix is one column less and at least one constraint less. */
1599 matrix
= cloog_matrix_alloc(polyhedron
->NbConstraints
-1,nb_dim
+1) ;
1601 /* mi is the constraint counter for the matrix. */
1603 for (i
=0;i
<polyhedron
->NbConstraints
;i
++)
1604 if (value_zero_p(polyhedron
->Constraint
[i
][dimension
+1]))
1605 { for (j
=0;j
<=dimension
;j
++)
1606 value_assign(matrix
->p
[mi
][j
],polyhedron
->Constraint
[i
][j
]) ;
1608 for (j
=dimension
+2;j
<nb_dim
+2;j
++)
1609 value_assign(matrix
->p
[mi
][j
-1],polyhedron
->Constraint
[i
][j
]) ;
1614 erased
= cloog_domain_matrix2domain(matrix
) ;
1615 cloog_matrix_free(matrix
) ;
1622 * To change the order of the part of a polyhedral union, for funny results !
1623 * - September 10th 2005.
1625 void cloog_domain_reverse(CloogDomain
* domain
)
1626 { Polyhedron
* polyhedron
, * p
, * q
,* r
;
1628 polyhedron
= domain
->polyhedron
;
1630 if ((polyhedron
== NULL
)||(polyhedron
->next
== NULL
))
1633 q
= polyhedron
->next
;
1634 polyhedron
->next
= NULL
;
1636 q
->next
= polyhedron
;
1643 domain
->polyhedron
= q
;