6 #include <cloog/isl/cloog.h>
8 #include <isl_constraint.h>
11 CloogDomain
*cloog_domain_from_isl_set(struct isl_set
*set
)
13 set
= isl_set_detect_equalities(set
);
14 set
= isl_set_compute_divs(set
);
15 return (CloogDomain
*)set
;
18 CloogScattering
*cloog_scattering_from_isl_map(struct isl_map
*map
)
20 return (CloogScattering
*)map
;
25 * Returns true if each scattering dimension is defined in terms
26 * of the original iterators.
28 int cloog_scattering_fully_specified(CloogScattering
*scattering
,
31 return isl_map_is_single_valued(&scattering
->map
);
35 CloogConstraintSet
*cloog_domain_constraints(CloogDomain
*domain
)
37 assert(domain
->set
.n
== 1);
38 return cloog_constraint_set_from_isl_basic_set(
39 isl_basic_set_copy(domain
->set
.p
[0]));
43 void cloog_domain_print_constraints(FILE *foo
, CloogDomain
*domain
,
47 isl_set_print(&domain
->set
, foo
, 0, ISL_FORMAT_EXT_POLYLIB
);
49 assert(domain
->set
.n
== 1);
50 isl_basic_set_print(domain
->set
.p
[0], foo
,
51 0, NULL
, NULL
, ISL_FORMAT_POLYLIB
);
56 void cloog_scattering_print_constraints(FILE *foo
, CloogScattering
*scattering
,
60 isl_map_print(&scattering
->map
, foo
, 0, ISL_FORMAT_EXT_POLYLIB
);
62 assert(scattering
->map
.n
== 1);
63 isl_basic_map_print(scattering
->map
.p
[0], foo
,
64 0, NULL
, NULL
, ISL_FORMAT_POLYLIB
);
69 void cloog_domain_free(CloogDomain
* domain
)
71 isl_set_free(&domain
->set
);
75 void cloog_scattering_free(CloogScattering
*scatt
)
77 isl_map_free(&scatt
->map
);
81 CloogDomain
* cloog_domain_copy(CloogDomain
* domain
)
83 return cloog_domain_from_isl_set(isl_set_copy(&domain
->set
));
88 * cloog_domain_convex function:
89 * Computes the convex hull of domain.
91 CloogDomain
*cloog_domain_convex(CloogDomain
*domain
)
93 struct isl_set
*set
= &domain
->set
;
94 set
= isl_set_from_basic_set(isl_set_convex_hull(isl_set_copy(set
)));
95 return cloog_domain_from_isl_set(set
);
100 * cloog_domain_simple_convex:
101 * Given a list (union) of polyhedra, this function returns a "simple"
102 * convex hull of this union. In particular, the constraints of the
103 * the returned polyhedron consist of (parametric) lower and upper
104 * bounds on individual variables and constraints that appear in the
105 * original polyhedra.
107 CloogDomain
*cloog_domain_simple_convex(CloogDomain
*domain
)
109 struct isl_basic_set
*hull
;
110 unsigned dim
= isl_set_n_dim(&domain
->set
);
112 if (cloog_domain_isconvex(domain
))
113 return cloog_domain_copy(domain
);
116 return cloog_domain_convex(domain
);
118 hull
= isl_set_bounded_simple_hull(isl_set_copy(&domain
->set
));
119 return cloog_domain_from_isl_set(isl_set_from_basic_set(hull
));
124 * cloog_domain_simplify function:
125 * Given two polyhedral domains (dom1) and (dom2),
126 * this function finds the largest domain set (or the smallest list
127 * of non-redundant constraints), that when intersected with polyhedral
128 * domain (dom2) equals (dom1)intersect(dom2). The output is a new CloogDomain
129 * structure with a polyhedral domain with the "redundant" constraints removed.
130 * NB: the second domain is required not to be a union.
132 CloogDomain
*cloog_domain_simplify(CloogDomain
*dom1
, CloogDomain
*dom2
)
135 set
= isl_set_gist(isl_set_copy(&dom1
->set
), isl_set_copy(&dom2
->set
));
136 return cloog_domain_from_isl_set(set
);
141 * cloog_domain_union function:
142 * This function returns a new polyhedral domain which is the union of
143 * two polyhedral domains (dom1) U (dom2).
144 * Frees dom1 and dom2;
146 CloogDomain
*cloog_domain_union(CloogDomain
*dom1
, CloogDomain
*dom2
)
149 set
= isl_set_union(&dom1
->set
, &dom2
->set
);
150 return cloog_domain_from_isl_set(set
);
156 * cloog_domain_intersection function:
157 * This function returns a new polyhedral domain which is the intersection of
158 * two polyhedral domains (dom1) \cap (dom2).
160 CloogDomain
*cloog_domain_intersection(CloogDomain
*dom1
, CloogDomain
*dom2
)
163 set
= isl_set_intersect(isl_set_copy(&dom1
->set
),
164 isl_set_copy(&dom2
->set
));
165 return cloog_domain_from_isl_set(set
);
170 * cloog_domain_difference function:
171 * Returns the set difference domain \ minus.
173 CloogDomain
*cloog_domain_difference(CloogDomain
*domain
, CloogDomain
*minus
)
176 set
= isl_set_subtract(isl_set_copy(&domain
->set
),
177 isl_set_copy(&minus
->set
));
178 return cloog_domain_from_isl_set(set
);
183 * cloog_domain_sort function:
184 * This function topologically sorts (nb_doms) domains. Here (doms) is an
185 * array of pointers to CloogDomains, (nb_doms) is the number of domains,
186 * (level) is the level to consider for partial ordering (nb_par) is the
187 * parameter space dimension, (permut) if not NULL, is an array of (nb_doms)
188 * integers that contains a permutation specification after call in order to
189 * apply the topological sorting.
191 void cloog_domain_sort(CloogDomain
**doms
, unsigned nb_doms
, unsigned level
,
196 unsigned char **follows
;
200 ctx
= doms
[0]->set
.ctx
;
201 for (i
= 0; i
< nb_doms
; i
++)
202 assert(doms
[i
]->set
.n
== 1);
204 follows
= isl_alloc_array(ctx
, unsigned char *, nb_doms
);
206 for (i
= 0; i
< nb_doms
; ++i
) {
207 follows
[i
] = isl_alloc_array(ctx
, unsigned char, nb_doms
);
209 for (j
= 0; j
< nb_doms
; ++j
)
213 for (i
= 1; i
< nb_doms
; ++i
) {
214 for (j
= 0; j
< i
; ++j
) {
215 if (follows
[i
][j
] || follows
[j
][i
])
217 cmp
= isl_basic_set_compare_at(doms
[i
]->set
.p
[0],
218 doms
[j
]->set
.p
[0], level
-1);
223 for (k
= 0; k
< i
; ++k
)
224 follows
[i
][k
] |= follows
[j
][k
];
227 for (k
= 0; k
< i
; ++k
)
228 follows
[k
][i
] |= follows
[k
][j
];
233 for (i
= 0, j
= 0; i
< nb_doms
; j
= (j
+ 1) % nb_doms
) {
234 for (k
= 0; k
< nb_doms
; ++k
)
239 for (k
= 0; k
< nb_doms
; ++k
)
246 for (i
= 0; i
< nb_doms
; ++i
)
253 * Check whether there is or may be any value of dom1 at the given level
254 * that is greater than or equal to a value of dom2 at the same level.
257 * 1 is there is or may be a greater-than pair.
258 * 0 if there is no greater-than pair, but there may be an equal-to pair
259 * -1 if there is definitely no such pair
261 int cloog_domain_follows(CloogDomain
*dom1
, CloogDomain
*dom2
, unsigned level
)
265 follows
= isl_set_follows_at(&dom1
->set
, &dom2
->set
, level
- 1);
266 assert(follows
>= -1);
273 * cloog_domain_empty function:
274 * Returns an empty domain of the same dimensions as template.
276 CloogDomain
*cloog_domain_empty(CloogDomain
*template)
278 return cloog_domain_from_isl_set(isl_set_empty_like(&template->set
));
283 * Return 1 if the specified dimension has both an upper and a lower bound.
285 int cloog_domain_is_bounded(CloogDomain
*dom
, unsigned level
)
287 return isl_set_dim_is_bounded(&dom
->set
, isl_dim_set
, level
- 1);
291 /******************************************************************************
292 * Structure display function *
293 ******************************************************************************/
297 * cloog_domain_print_structure :
298 * this function is a more human-friendly way to display the CloogDomain data
299 * structure, it only shows the constraint system and includes an indentation
300 * level (level) in order to work with others print_structure functions.
302 void cloog_domain_print_structure(FILE *file
, CloogDomain
*domain
, int level
,
306 struct isl_set
*set
= &domain
->set
;
308 /* Go to the right level. */
309 for (i
= 0; i
< level
; i
++)
310 fprintf(file
, "|\t");
313 fprintf(file
, "+-- Null CloogDomain\n");
316 fprintf(file
, "+-- %s\n", name
);
317 for (i
= 0; i
< level
+1; ++i
)
318 fprintf(file
, "|\t");
320 isl_set_print(set
, file
, 0, ISL_FORMAT_ISL
);
326 /******************************************************************************
327 * Memory deallocation function *
328 ******************************************************************************/
331 void cloog_domain_list_free(CloogDomainList
*list
)
333 CloogDomainList
*next
;
335 for ( ; list
; list
= next
) {
337 cloog_domain_free(list
->domain
);
344 * cloog_scattering_list_free function:
345 * This function frees the allocated memory for a CloogScatteringList structure.
347 void cloog_scattering_list_free(CloogScatteringList
*list
)
349 while (list
!= NULL
) {
350 CloogScatteringList
*temp
= list
->next
;
351 isl_map_free(&list
->scatt
->map
);
358 /******************************************************************************
360 ******************************************************************************/
364 * cloog_domain_read_context function:
365 * Read parameter domain.
367 CloogDomain
*cloog_domain_read_context(CloogState
*state
, FILE *input
)
369 struct isl_ctx
*ctx
= state
->backend
->ctx
;
372 set
= isl_set_read_from_file(ctx
, input
, 0);
373 set
= isl_set_move_dims(set
, isl_dim_param
, 0,
374 isl_dim_set
, 0, isl_set_dim(set
, isl_dim_set
));
376 return cloog_domain_from_isl_set(set
);
381 * cloog_domain_from_context
382 * Reinterpret context by turning parameters into variables.
384 CloogDomain
*cloog_domain_from_context(CloogDomain
*context
)
386 isl_set
*set
= &context
->set
;
388 set
= isl_set_move_dims(set
, isl_dim_set
, 0,
389 isl_dim_param
, 0, isl_set_dim(set
, isl_dim_param
));
391 return cloog_domain_from_isl_set(set
);
396 * cloog_domain_union_read function:
397 * This function reads a union of polyhedra into a file (input) and
398 * returns a pointer to a CloogDomain containing the read information.
400 CloogDomain
*cloog_domain_union_read(CloogState
*state
,
401 FILE *input
, int nb_parameters
)
403 struct isl_ctx
*ctx
= state
->backend
->ctx
;
406 set
= isl_set_read_from_file(ctx
, input
, nb_parameters
);
407 return cloog_domain_from_isl_set(set
);
412 * cloog_domain_read_scattering function:
413 * This function reads in a scattering function from the file input.
415 * We try to read the scattering relation as a map, but if it is
416 * specified in the original PolyLib format, then isl_map_read_from_file
417 * will treat the input as a set return a map with zero input dimensions.
418 * In this case, we need to decompose the set into a map from
419 * scattering dimensions to domain dimensions and then invert the
422 CloogScattering
*cloog_domain_read_scattering(CloogDomain
*domain
, FILE *input
)
424 struct isl_ctx
*ctx
= domain
->set
.ctx
;
425 struct isl_map
*scat
;
430 dim
= isl_set_n_dim(&domain
->set
);
431 nparam
= isl_set_n_param(&domain
->set
);
432 scat
= isl_map_read_from_file(ctx
, input
, nparam
);
433 if (isl_map_dim(scat
, isl_dim_in
) != dim
) {
434 n_scat
= isl_map_dim(scat
, isl_dim_out
) - dim
;
435 scat
= isl_map_move_dims(scat
, isl_dim_in
, 0,
436 isl_dim_out
, n_scat
, dim
);
438 return cloog_scattering_from_isl_map(scat
);
441 /******************************************************************************
442 * CloogMatrix Reading function *
443 ******************************************************************************/
446 * isl_constraint_read_from_matrix:
447 * Convert a single line of a matrix to a isl_constraint.
448 * Returns a pointer to the constraint if successful; NULL otherwise.
450 static struct isl_constraint
*isl_constraint_read_from_matrix(
451 struct isl_dim
*dim
, cloog_int_t
*row
)
453 struct isl_constraint
*constraint
;
455 int nvariables
= isl_dim_size(dim
, isl_dim_set
);
456 int nparam
= isl_dim_size(dim
, isl_dim_param
);
458 if (cloog_int_is_zero(row
[0]))
459 constraint
= isl_equality_alloc(dim
);
461 constraint
= isl_inequality_alloc(dim
);
463 for (j
= 0; j
< nvariables
; ++j
)
464 isl_constraint_set_coefficient(constraint
, isl_dim_out
, j
,
467 for (j
= 0; j
< nparam
; ++j
)
468 isl_constraint_set_coefficient(constraint
, isl_dim_param
, j
,
469 row
[1 + nvariables
+ j
]);
471 isl_constraint_set_constant(constraint
, row
[1 + nvariables
+ nparam
]);
477 * isl_basic_set_read_from_matrix:
478 * Convert matrix to basic_set. The matrix contains nparam parameter columns.
479 * Returns a pointer to the basic_set if successful; NULL otherwise.
481 static struct isl_basic_set
*isl_basic_set_read_from_matrix(struct isl_ctx
*ctx
,
482 CloogMatrix
* matrix
, int nparam
)
485 struct isl_basic_set
*bset
;
487 unsigned nrows
, ncolumns
;
489 nrows
= matrix
->NbRows
;
490 ncolumns
= matrix
->NbColumns
;
491 int nvariables
= ncolumns
- 2 - nparam
;
493 dim
= isl_dim_set_alloc(ctx
, nparam
, nvariables
);
495 bset
= isl_basic_set_universe(isl_dim_copy(dim
));
497 for (i
= 0; i
< nrows
; ++i
) {
498 cloog_int_t
*row
= matrix
->p
[i
];
499 struct isl_constraint
*constraint
=
500 isl_constraint_read_from_matrix(isl_dim_copy(dim
), row
);
501 bset
= isl_basic_set_add_constraint(bset
, constraint
);
510 * cloog_domain_from_cloog_matrix:
511 * Create a CloogDomain containing the constraints described in matrix.
512 * nparam is the number of parameters contained in the domain.
513 * Returns a pointer to the CloogDomain if successful; NULL otherwise.
515 CloogDomain
*cloog_domain_from_cloog_matrix(CloogState
*state
,
516 CloogMatrix
*matrix
, int nparam
)
518 struct isl_ctx
*ctx
= state
->backend
->ctx
;
519 struct isl_basic_set
*bset
;
521 bset
= isl_basic_set_read_from_matrix(ctx
, matrix
, nparam
);
523 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset
));
527 * cloog_scattering_from_cloog_matrix:
528 * Create a CloogScattering containing the constraints described in matrix.
529 * nparam is the number of parameters contained in the domain.
530 * Returns a pointer to the CloogScattering if successful; NULL otherwise.
532 CloogScattering
*cloog_scattering_from_cloog_matrix(CloogState
*state
,
533 CloogMatrix
*matrix
, int nb_scat
, int nb_par
)
535 struct isl_ctx
*ctx
= state
->backend
->ctx
;
536 struct isl_basic_set
*bset
;
537 struct isl_basic_map
*scat
;
538 struct isl_dim
*dims
;
541 bset
= isl_basic_set_read_from_matrix(ctx
, matrix
, nb_par
);
542 dim
= isl_basic_set_n_dim(bset
) - nb_scat
;
543 dims
= isl_dim_alloc(ctx
, nb_par
, nb_scat
, dim
);
545 scat
= isl_basic_map_from_basic_set(bset
, dims
);
546 scat
= isl_basic_map_reverse(scat
);
547 return cloog_scattering_from_isl_map(isl_map_from_basic_map(scat
));
551 /******************************************************************************
552 * Processing functions *
553 ******************************************************************************/
558 * cloog_domain_isempty function:
560 int cloog_domain_isempty(CloogDomain
*domain
)
562 return isl_set_is_empty(&domain
->set
);
567 * cloog_domain_universe function:
568 * This function returns the complete dim-dimensional space.
570 CloogDomain
*cloog_domain_universe(CloogState
*state
, unsigned dim
)
572 struct isl_dim
*dims
;
573 struct isl_basic_set
*bset
;
575 dims
= isl_dim_set_alloc(state
->backend
->ctx
, 0, dim
);
576 bset
= isl_basic_set_universe(dims
);
577 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset
));
582 * cloog_domain_project function:
583 * This function returns the projection of
584 * (domain) on the (level) first dimensions (i.e. outer loops).
586 CloogDomain
*cloog_domain_project(CloogDomain
*domain
, int level
)
588 struct isl_set
*set
= &domain
->set
;
589 set
= isl_set_remove_dims(isl_set_copy(set
), isl_dim_set
,
590 level
, isl_set_n_dim(set
) - level
);
591 set
= isl_set_compute_divs(set
);
593 set
= isl_set_remove_divs_involving_dims(set
,
594 isl_dim_set
, level
- 1, 1);
595 return cloog_domain_from_isl_set(set
);
600 * cloog_domain_extend function:
601 * This function returns the (domain) given as input with (dim)
602 * dimensions and (nb_par) parameters.
603 * This function does not free (domain), and returns a new CloogDomain.
605 CloogDomain
*cloog_domain_extend(CloogDomain
*domain
, int dim
)
607 struct isl_set
*set
= &domain
->set
;
608 set
= isl_set_extend(isl_set_copy(set
), isl_set_n_param(set
), dim
);
609 return cloog_domain_from_isl_set(set
);
614 * cloog_domain_never_integral function:
615 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0.
616 * There is no need to check for such constraints explicitly for the isl
619 int cloog_domain_never_integral(CloogDomain
* domain
)
621 return isl_set_is_empty(&domain
->set
);
626 * Check whether the loop at "level" is executed at most once.
627 * We construct a map that maps all remaining variables to this iterator
628 * and check whether this map is single valued.
630 * Alternatively, we could have mapped the domain through a mapping
631 * [p] -> { [..., i] -> [..., i'] : i' > i }
632 * and then taken the intersection of the original domain and the transformed
633 * domain. If this intersection is empty, then the corresponding
634 * loop is executed at most once.
636 int cloog_domain_is_otl(CloogDomain
*domain
, int level
)
641 map
= isl_map_from_domain(isl_set_copy(&domain
->set
));
642 map
= isl_map_move_dims(map
, isl_dim_out
, 0, isl_dim_in
, level
- 1, 1);
643 otl
= isl_map_is_single_valued(map
);
651 * cloog_domain_stride function:
652 * This function finds the stride imposed to unknown with the column number
653 * 'strided_level' in order to be integral. For instance, if we have a
654 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
655 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
656 * the unknown i. The function returns the imposed stride in a parameter field.
657 * - domain is the set of constraint we have to consider,
658 * - strided_level is the column number of the unknown for which a stride have
660 * - looking_level is the column number of the unknown that impose a stride to
662 * - stride is the stride that is returned back as a function parameter.
663 * - offset is the value of the constant c if the condition is of the shape
664 * (i + c)%s = 0, s being the stride.
666 void cloog_domain_stride(CloogDomain
*domain
, int strided_level
,
667 cloog_int_t
*stride
, cloog_int_t
*offset
)
669 struct isl_set
*set
= &domain
->set
;
670 isl_set_dim_residue_class(set
, strided_level
- 1, stride
, offset
);
671 if (!isl_int_is_zero(*offset
))
672 isl_int_sub(*offset
, *stride
, *offset
);
677 struct cloog_can_stride
{
682 static int constraint_can_stride(__isl_take isl_constraint
*c
, void *user
)
684 struct cloog_can_stride
*ccs
= (struct cloog_can_stride
*)user
;
690 isl_constraint_get_coefficient(c
, isl_dim_set
, ccs
->level
- 1, &v
);
691 if (isl_int_is_pos(v
)) {
692 n_div
= isl_constraint_dim(c
, isl_dim_div
);
693 for (i
= 0; i
< n_div
; ++i
) {
694 isl_constraint_get_coefficient(c
, isl_dim_div
, i
, &v
);
695 if (!isl_int_is_zero(v
))
702 isl_constraint_free(c
);
707 static int basic_set_can_stride(__isl_take isl_basic_set
*bset
, void *user
)
709 struct cloog_can_stride
*ccs
= (struct cloog_can_stride
*)user
;
712 r
= isl_basic_set_foreach_constraint(bset
, constraint_can_stride
, ccs
);
713 isl_basic_set_free(bset
);
719 * Return 1 if CLooG is allowed to perform stride detection on level "level"
721 * Currently, stride detection is only allowed when none of the lower
722 * bound constraints involve any existentially quantified variables.
723 * The reason is that the current isl interface does not make it
724 * easy to construct an integer division that depends on other integer
726 * By not allowing existentially quantified variables in the constraints,
727 * we can ignore them in cloog_domain_stride_lower_bound.
729 int cloog_domain_can_stride(CloogDomain
*domain
, int level
)
731 struct cloog_can_stride ccs
= { level
, 1 };
733 r
= isl_set_foreach_basic_set(&domain
->set
, basic_set_can_stride
, &ccs
);
735 return ccs
.can_stride
;
739 struct cloog_stride_lower
{
743 isl_basic_set
*bounds
;
746 /* If the given constraint is a lower bound on csl->level, then add
747 * a lower bound to csl->bounds that makes sure that the remainder
748 * of the smallest value on division by csl->stride is equal to csl->offset.
750 * In particular, the given lower bound is of the form
754 * where f may depend on the parameters and other iterators.
755 * The stride is s and the offset is d.
756 * The lower bound -f/a may not satisfy the above condition. In fact,
757 * it may not even be integral. We want to round this value of i up
758 * to the nearest value that satisfies the condition and add the corresponding
759 * lower bound constraint. This nearest value is obtained by rounding
760 * i - d up to the nearest multiple of s.
761 * That is, we first subtract d
765 * then we round up to the nearest multiple of s
767 * i'' = s * ceil(i'/s)
769 * and finally, we add d again
773 * and impose the constraint i >= i'''.
777 * i'' = s * ceil((-f - a * d)/(a * s)) = - s * floor((f + a * d)/(a * s))
779 * i >= - s * floor((f + a * d)/(a * s)) + d
782 * i + s * floor((f + a * d)/(a * s)) - d >= 0
784 static int constraint_stride_lower(__isl_take isl_constraint
*c
, void *user
)
786 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
790 isl_constraint
*bound
;
793 unsigned nparam
, nvar
;
796 isl_constraint_get_coefficient(c
, isl_dim_set
, csl
->level
- 1, &v
);
797 if (!isl_int_is_pos(v
)) {
799 isl_constraint_free(c
);
806 nparam
= isl_constraint_dim(c
, isl_dim_param
);
807 nvar
= isl_constraint_dim(c
, isl_dim_set
);
808 bound
= isl_inequality_alloc(isl_basic_set_get_dim(csl
->bounds
));
809 div
= isl_div_alloc(isl_basic_set_get_dim(csl
->bounds
));
810 isl_int_mul(t
, v
, csl
->stride
->stride
);
811 isl_div_set_denominator(div
, t
);
812 for (i
= 0; i
< nparam
; ++i
) {
813 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &t
);
814 isl_div_set_coefficient(div
, isl_dim_param
, i
, t
);
816 for (i
= 0; i
< nvar
; ++i
) {
817 if (i
== csl
->level
- 1)
819 isl_constraint_get_coefficient(c
, isl_dim_set
, i
, &t
);
820 isl_div_set_coefficient(div
, isl_dim_set
, i
, t
);
822 isl_constraint_get_constant(c
, &t
);
823 isl_int_addmul(t
, v
, csl
->stride
->offset
);
824 isl_div_set_constant(div
, t
);
826 bound
= isl_constraint_add_div(bound
, div
, &pos
);
827 isl_int_set_si(t
, 1);
828 isl_constraint_set_coefficient(bound
, isl_dim_set
,
830 isl_constraint_set_coefficient(bound
, isl_dim_div
, pos
,
831 csl
->stride
->stride
);
832 isl_int_neg(t
, csl
->stride
->offset
);
833 isl_constraint_set_constant(bound
, t
);
834 csl
->bounds
= isl_basic_set_add_constraint(csl
->bounds
, bound
);
838 isl_constraint_free(c
);
843 /* This functions performs essentially the same operation as
844 * constraint_stride_lower, the only difference being that the offset d
845 * is not a constant, but an affine expression in terms of the parameters
846 * and earlier variables. In particular the affine expression is equal
847 * to the coefficients of stride->constraint multiplied by stride->factor.
848 * As in constraint_stride_lower, we add an extra bound
850 * i + s * floor((f + a * d)/(a * s)) - d >= 0
852 * for each lower bound
856 * where d is not the aforementioned affine expression.
858 static int constraint_stride_lower_c(__isl_take isl_constraint
*c
, void *user
)
860 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
864 isl_constraint
*bound
;
865 isl_constraint
*csl_c
;
868 unsigned nparam
, nvar
;
871 isl_constraint_get_coefficient(c
, isl_dim_set
, csl
->level
- 1, &v
);
872 if (!isl_int_is_pos(v
)) {
874 isl_constraint_free(c
);
879 csl_c
= &csl
->stride
->constraint
->isl
;
884 nparam
= isl_constraint_dim(c
, isl_dim_param
);
885 nvar
= isl_constraint_dim(c
, isl_dim_set
);
886 bound
= isl_inequality_alloc(isl_basic_set_get_dim(csl
->bounds
));
887 div
= isl_div_alloc(isl_basic_set_get_dim(csl
->bounds
));
888 isl_int_mul(t
, v
, csl
->stride
->stride
);
889 isl_div_set_denominator(div
, t
);
890 for (i
= 0; i
< nparam
; ++i
) {
891 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &t
);
892 isl_constraint_get_coefficient(csl_c
, isl_dim_param
, i
, &u
);
893 isl_int_mul(u
, u
, csl
->stride
->factor
);
894 isl_int_addmul(t
, v
, u
);
895 isl_div_set_coefficient(div
, isl_dim_param
, i
, t
);
897 isl_constraint_set_coefficient(bound
, isl_dim_param
, i
, u
);
899 for (i
= 0; i
< nvar
; ++i
) {
900 if (i
== csl
->level
- 1)
902 isl_constraint_get_coefficient(c
, isl_dim_set
, i
, &t
);
903 isl_constraint_get_coefficient(csl_c
, isl_dim_set
, i
, &u
);
904 isl_int_mul(u
, u
, csl
->stride
->factor
);
905 isl_int_addmul(t
, v
, u
);
906 isl_div_set_coefficient(div
, isl_dim_set
, i
, t
);
908 isl_constraint_set_coefficient(bound
, isl_dim_set
, i
, u
);
910 isl_constraint_get_constant(c
, &t
);
911 isl_constraint_get_constant(csl_c
, &u
);
912 isl_int_mul(u
, u
, csl
->stride
->factor
);
913 isl_int_addmul(t
, v
, u
);
914 isl_div_set_constant(div
, t
);
916 isl_constraint_set_constant(bound
, u
);
918 bound
= isl_constraint_add_div(bound
, div
, &pos
);
919 isl_int_set_si(t
, 1);
920 isl_constraint_set_coefficient(bound
, isl_dim_set
,
922 isl_constraint_set_coefficient(bound
, isl_dim_div
, pos
,
923 csl
->stride
->stride
);
924 csl
->bounds
= isl_basic_set_add_constraint(csl
->bounds
, bound
);
929 isl_constraint_free(c
);
934 static int basic_set_stride_lower(__isl_take isl_basic_set
*bset
, void *user
)
936 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
939 csl
->bounds
= isl_basic_set_universe_like(bset
);
940 if (csl
->stride
->constraint
)
941 r
= isl_basic_set_foreach_constraint(bset
,
942 &constraint_stride_lower_c
, csl
);
944 r
= isl_basic_set_foreach_constraint(bset
,
945 &constraint_stride_lower
, csl
);
946 bset
= isl_basic_set_intersect(bset
, csl
->bounds
);
947 csl
->set
= isl_set_union(csl
->set
, isl_set_from_basic_set(bset
));
953 * Update the lower bounds at level "level" to the given stride information.
954 * That is, make sure that the remainder on division by "stride"
955 * is equal to "offset".
957 CloogDomain
*cloog_domain_stride_lower_bound(CloogDomain
*domain
, int level
,
960 struct cloog_stride_lower csl
;
965 csl
.set
= isl_set_empty_like(&domain
->set
);
967 r
= isl_set_foreach_basic_set(&domain
->set
, basic_set_stride_lower
, &csl
);
970 cloog_domain_free(domain
);
971 return cloog_domain_from_isl_set(csl
.set
);
976 * cloog_domain_lazy_equal function:
977 * This function returns 1 if the domains given as input are the same, 0 if it
978 * is unable to decide.
980 int cloog_domain_lazy_equal(CloogDomain
*d1
, CloogDomain
*d2
)
982 return isl_set_fast_is_equal(&d1
->set
, &d2
->set
);
985 struct cloog_bound_split
{
992 static int constraint_bound_split(__isl_take isl_constraint
*c
, void *user
)
994 struct cloog_bound_split
*cbs
= (struct cloog_bound_split
*)user
;
1000 isl_constraint_get_coefficient(c
, isl_dim_set
, cbs
->level
- 1, &v
);
1001 if (!cbs
->lower
&& isl_int_is_pos(v
))
1002 cbs
->lower
= handle
= 1;
1003 else if (!cbs
->upper
&& isl_int_is_neg(v
))
1004 cbs
->upper
= handle
= 1;
1006 for (i
= 0; i
< isl_set_dim(cbs
->set
, isl_dim_param
); ++i
) {
1007 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &v
);
1008 if (isl_int_is_zero(v
))
1010 cbs
->set
= isl_set_split_dims(cbs
->set
,
1011 isl_dim_param
, i
, 1);
1015 isl_constraint_free(c
);
1017 return (cbs
->lower
&& cbs
->upper
) ? -1 : 0;
1020 static int basic_set_bound_split(__isl_take isl_basic_set
*bset
, void *user
)
1022 struct cloog_bound_split
*cbs
= (struct cloog_bound_split
*)user
;
1027 r
= isl_basic_set_foreach_constraint(bset
, constraint_bound_split
, cbs
);
1028 isl_basic_set_free(bset
);
1029 return ((!cbs
->lower
|| !cbs
->upper
) && r
< 0) ? -1 : 0;
1033 * Return a union of sets S_i such that the convex hull of "dom",
1034 * when intersected with one the sets S_i, will have an upper and
1035 * lower bound for the dimension at "level" (provided "dom" itself
1036 * has such bounds for the dimensions).
1038 * We currently take a very simple approach. For each of the basic
1039 * sets in "dom" we pick a lower and an upper bound and split the
1040 * range of any parameter involved in these two bounds in a
1041 * nonnegative and a negative part. This ensures that the symbolic
1042 * constant in these two constraints are themselves bounded and
1043 * so there will be at least one upper and one lower bound
1044 * in the convex hull.
1046 CloogDomain
*cloog_domain_bound_splitter(CloogDomain
*dom
, int level
)
1048 struct cloog_bound_split cbs
;
1051 cbs
.set
= isl_set_universe_like(&dom
->set
);
1052 r
= isl_set_foreach_basic_set(&dom
->set
, basic_set_bound_split
, &cbs
);
1054 return cloog_domain_from_isl_set(cbs
.set
);
1059 * cloog_scattering_lazy_block function:
1060 * This function returns 1 if the two scattering functions s1 and s2 given
1061 * as input are the same (except possibly for the final dimension, where we
1062 * allow a difference of 1), assuming that the domains on which this
1063 * scatterings are applied are the same.
1064 * In fact this function answers the question "can I
1065 * safely consider the two domains as only one with two statements (a block) ?".
1066 * - s1 and s2 are the two domains to check for blocking,
1067 * - scattering is the linked list of all domains,
1068 * - scattdims is the total number of scattering dimentions.
1070 int cloog_scattering_lazy_block(CloogScattering
*s1
, CloogScattering
*s2
,
1071 CloogScatteringList
*scattering
, int scattdims
)
1074 struct isl_dim
*dim
;
1075 struct isl_map
*rel
;
1076 struct isl_set
*delta
;
1081 n_scat
= isl_map_dim(&s1
->map
, isl_dim_out
);
1082 if (n_scat
!= isl_map_dim(&s2
->map
, isl_dim_out
))
1085 dim
= isl_dim_copy(s1
->map
.dim
);
1086 dim
= isl_dim_domain(dim
);
1087 rel
= isl_map_identity(dim
);
1088 rel
= isl_map_apply_domain(rel
, isl_map_copy(&s1
->map
));
1089 rel
= isl_map_apply_range(rel
, isl_map_copy(&s2
->map
));
1090 delta
= isl_map_deltas(rel
);
1092 for (i
= 0; i
< n_scat
; ++i
) {
1093 fixed
= isl_set_fast_dim_is_fixed(delta
, i
, &cst
);
1096 if (i
+1 < n_scat
&& !isl_int_is_zero(cst
))
1098 if (!isl_int_is_zero(cst
) && !isl_int_is_one(cst
))
1101 block
= i
>= n_scat
;
1103 isl_set_free(delta
);
1109 * cloog_domain_lazy_disjoint function:
1110 * This function returns 1 if the domains given as input are disjoint, 0 if it
1111 * is unable to decide.
1113 int cloog_domain_lazy_disjoint(CloogDomain
*d1
, CloogDomain
*d2
)
1115 return isl_set_fast_is_disjoint(&d1
->set
, &d2
->set
);
1120 * cloog_scattering_list_lazy_same function:
1121 * This function returns 1 if two domains in the list are the same, 0 if it
1122 * is unable to decide.
1124 int cloog_scattering_list_lazy_same(CloogScatteringList
*list
)
1126 CloogScatteringList
*one
, *other
;
1128 for (one
= list
; one
; one
= one
->next
)
1129 for (other
= one
->next
; other
; other
= other
->next
)
1130 if (isl_map_fast_is_equal(&one
->scatt
->map
,
1131 &other
->scatt
->map
))
1136 int cloog_domain_dimension(CloogDomain
* domain
)
1138 return isl_set_n_dim(&domain
->set
);
1141 int cloog_domain_parameter_dimension(CloogDomain
*domain
)
1143 return isl_set_n_param(&domain
->set
);
1146 int cloog_scattering_dimension(CloogScattering
*scatt
, CloogDomain
*domain
)
1148 return isl_map_dim(&scatt
->map
, isl_dim_out
);
1151 int cloog_domain_isconvex(CloogDomain
* domain
)
1153 return domain
->set
.n
<= 1;
1158 * cloog_domain_cut_first function:
1159 * This function splits off and returns the first convex set in the
1160 * union "domain". The remainder of the union is returned in rest.
1161 * The original "domain" itself is destroyed and may not be used
1162 * after a call to this function.
1164 CloogDomain
*cloog_domain_cut_first(CloogDomain
*domain
, CloogDomain
**rest
)
1166 struct isl_set
*set
;
1167 struct isl_basic_set
*first
;
1170 first
= isl_set_copy_basic_set(set
);
1171 set
= isl_set_drop_basic_set(set
, first
);
1172 *rest
= cloog_domain_from_isl_set(set
);
1174 return cloog_domain_from_isl_set(isl_set_from_basic_set(first
));
1179 * Given a union domain, try to find a simpler representation
1180 * using fewer sets in the union.
1181 * The original "domain" itself is destroyed and may not be used
1182 * after a call to this function.
1184 CloogDomain
*cloog_domain_simplify_union(CloogDomain
*domain
)
1186 return cloog_domain_from_isl_set(isl_set_coalesce(&domain
->set
));
1191 * cloog_scattering_lazy_isscalar function:
1192 * this function returns 1 if the scattering dimension 'dimension' in the
1193 * scattering 'scatt' is constant.
1194 * If value is not NULL, then it is set to the constant value of dimension.
1196 int cloog_scattering_lazy_isscalar(CloogScattering
*scatt
, int dimension
,
1199 return isl_map_fast_is_fixed(&scatt
->map
, isl_dim_out
, dimension
, value
);
1204 * cloog_domain_lazy_isconstant function:
1205 * this function returns 1 if the dimension 'dimension' in the
1206 * domain 'domain' is constant.
1207 * If value is not NULL, then it is set to the constant value of dimension.
1209 int cloog_domain_lazy_isconstant(CloogDomain
*domain
, int dimension
)
1211 return isl_set_fast_dim_is_fixed(&domain
->set
, dimension
, NULL
);
1216 * cloog_scattering_erase_dimension function:
1217 * this function returns a CloogDomain structure builds from 'domain' where
1218 * we removed the dimension 'dimension' and every constraint involving this
1221 CloogScattering
*cloog_scattering_erase_dimension(CloogScattering
*domain
,
1224 struct isl_map
*map
;
1225 map
= isl_map_remove_dims(isl_map_copy(&domain
->map
),
1226 isl_dim_out
, dimension
, 1);
1227 return cloog_scattering_from_isl_map(map
);
1231 * cloog_domain_cube:
1232 * Construct and return a dim-dimensional cube, with values ranging
1233 * between min and max in each dimension.
1235 CloogDomain
*cloog_domain_cube(CloogState
*state
,
1236 int dim
, cloog_int_t min
, cloog_int_t max
)
1239 struct isl_basic_set
*cube
;
1240 struct isl_basic_set
*interval
;
1241 struct isl_basic_set_list
*list
;
1244 return cloog_domain_universe(state
, dim
);
1246 interval
= isl_basic_set_interval(state
->backend
->ctx
, min
, max
);
1247 list
= isl_basic_set_list_alloc(state
->backend
->ctx
, dim
);
1248 for (i
= 0; i
< dim
; ++i
)
1249 list
= isl_basic_set_list_add(list
, isl_basic_set_copy(interval
));
1250 isl_basic_set_free(interval
);
1251 cube
= isl_basic_set_product(list
);
1252 return cloog_domain_from_isl_set(isl_set_from_basic_set(cube
));
1257 * cloog_domain_scatter function:
1258 * This function add the scattering (scheduling) informations to a domain.
1260 CloogDomain
*cloog_domain_scatter(CloogDomain
*domain
, CloogScattering
*scatt
)
1262 struct isl_map
*map
;
1264 map
= isl_map_reverse(isl_map_copy(&scatt
->map
));
1265 map
= isl_map_intersect_range(map
, &domain
->set
);
1266 return cloog_domain_from_isl_set(isl_set_from_map(map
));
1269 static int add_domain_from_map(__isl_take isl_map
*map
, void *user
)
1273 CloogDomain
*domain
;
1274 CloogScattering
*scat
;
1275 CloogUnionDomain
**ud
= (CloogUnionDomain
**)user
;
1277 dim
= isl_map_get_dim(map
);
1278 name
= isl_dim_get_tuple_name(dim
, isl_dim_in
);
1279 domain
= cloog_domain_from_isl_set(isl_map_domain(isl_map_copy(map
)));
1280 scat
= cloog_scattering_from_isl_map(map
);
1281 *ud
= cloog_union_domain_add_domain(*ud
, name
, domain
, scat
, NULL
);
1288 * Construct a CloogUnionDomain from an isl_union_map representing
1289 * a global scattering function. The input is a mapping from different
1290 * spaces (different tuple names and possibly different dimensions)
1291 * to a common space. The iteration domains are set to the domains
1292 * in each space. The statement names are set to the names of the
1293 * spaces. The parameter names of the result are set to those of
1294 * the input, but the iterator and scattering dimension names are
1297 CloogUnionDomain
*cloog_union_domain_from_isl_union_map(
1298 __isl_take isl_union_map
*umap
)
1303 CloogUnionDomain
*ud
;
1305 dim
= isl_union_map_get_dim(umap
);
1306 nparam
= isl_dim_size(dim
, isl_dim_param
);
1308 ud
= cloog_union_domain_alloc(nparam
);
1310 for (i
= 0; i
< nparam
; ++i
) {
1311 const char *s
= isl_dim_get_name(dim
, isl_dim_param
, i
);
1312 ud
= cloog_union_domain_set_name(ud
, CLOOG_PARAM
, i
, s
);
1316 if (isl_union_map_foreach_map(umap
, &add_domain_from_map
, &ud
) < 0) {
1317 isl_union_map_free(umap
);
1318 cloog_union_domain_free(ud
);
1322 isl_union_map_free(umap
);
1327 static int add_domain(__isl_take isl_set
*set
, void *user
)
1331 CloogDomain
*domain
;
1332 CloogUnionDomain
**ud
= (CloogUnionDomain
**)user
;
1334 dim
= isl_set_get_dim(set
);
1335 name
= isl_dim_get_tuple_name(dim
, isl_dim_in
);
1336 domain
= cloog_domain_from_isl_set(set
);
1337 *ud
= cloog_union_domain_add_domain(*ud
, name
, domain
, NULL
, NULL
);
1344 * Construct a CloogUnionDomain from an isl_union_set.
1345 * The statement names are set to the names of the
1346 * spaces. The parameter names of the result are set to those of
1347 * the input, but the iterator and scattering dimension names are
1350 CloogUnionDomain
*cloog_union_domain_from_isl_union_set(
1351 __isl_take isl_union_set
*uset
)
1356 CloogUnionDomain
*ud
;
1358 dim
= isl_union_set_get_dim(uset
);
1359 nparam
= isl_dim_size(dim
, isl_dim_param
);
1361 ud
= cloog_union_domain_alloc(nparam
);
1363 for (i
= 0; i
< nparam
; ++i
) {
1364 const char *s
= isl_dim_get_name(dim
, isl_dim_param
, i
);
1365 ud
= cloog_union_domain_set_name(ud
, CLOOG_PARAM
, i
, s
);
1369 if (isl_union_set_foreach_set(uset
, &add_domain
, &ud
) < 0) {
1370 isl_union_set_free(uset
);
1371 cloog_union_domain_free(ud
);
1375 isl_union_set_free(uset
);
1380 /* Computes x, y and g such that g = gcd(a,b) and a*x+b*y = g */
1381 static void Euclid(cloog_int_t a
, cloog_int_t b
,
1382 cloog_int_t
*x
, cloog_int_t
*y
, cloog_int_t
*g
)
1384 cloog_int_t c
, d
, e
, f
, tmp
;
1390 cloog_int_init(tmp
);
1391 cloog_int_abs(c
, a
);
1392 cloog_int_abs(d
, b
);
1393 cloog_int_set_si(e
, 1);
1394 cloog_int_set_si(f
, 0);
1395 while (cloog_int_is_pos(d
)) {
1396 cloog_int_tdiv_q(tmp
, c
, d
);
1397 cloog_int_mul(tmp
, tmp
, f
);
1398 cloog_int_sub(e
, e
, tmp
);
1399 cloog_int_tdiv_q(tmp
, c
, d
);
1400 cloog_int_mul(tmp
, tmp
, d
);
1401 cloog_int_sub(c
, c
, tmp
);
1402 cloog_int_swap(c
, d
);
1403 cloog_int_swap(e
, f
);
1405 cloog_int_set(*g
, c
);
1406 if (cloog_int_is_zero(a
))
1407 cloog_int_set_si(*x
, 0);
1408 else if (cloog_int_is_pos(a
))
1409 cloog_int_set(*x
, e
);
1410 else cloog_int_neg(*x
, e
);
1411 if (cloog_int_is_zero(b
))
1412 cloog_int_set_si(*y
, 0);
1414 cloog_int_mul(tmp
, a
, *x
);
1415 cloog_int_sub(tmp
, c
, tmp
);
1416 cloog_int_divexact(*y
, tmp
, b
);
1422 cloog_int_clear(tmp
);
1425 /* Construct a CloogStride from the given constraint for the given level,
1427 * We first compute the gcd of the coefficients of the existentially
1428 * quantified variables and then remove any common factors it has
1429 * with the coefficient at the given level.
1430 * The result is the value of the stride and if it is not one,
1431 * the it is possible to construct a CloogStride.
1432 * The constraint leading to the stride is stored in the CloogStride
1433 * as well a value (factor) such that the product of this value
1434 * and the coefficient at the given level is equal to -1 modulo the stride.
1436 static CloogStride
*construct_stride(isl_constraint
*c
, int level
)
1439 isl_int v
, m
, gcd
, stride
, factor
;
1448 isl_int_init(factor
);
1449 isl_int_init(stride
);
1451 isl_constraint_get_coefficient(c
, isl_dim_set
, level
- 1, &v
);
1452 sign
= isl_int_sgn(v
);
1455 isl_int_set_si(gcd
, 0);
1456 n
= isl_constraint_dim(c
, isl_dim_div
);
1457 for (i
= 0; i
< n
; ++i
) {
1458 isl_constraint_get_coefficient(c
, isl_dim_div
, i
, &v
);
1459 isl_int_gcd(gcd
, gcd
, v
);
1462 isl_int_gcd(v
, m
, gcd
);
1463 isl_int_divexact(stride
, gcd
, v
);
1465 if (isl_int_is_zero(stride
) || isl_int_is_one(stride
))
1468 Euclid(m
, stride
, &factor
, &v
, &gcd
);
1470 isl_int_neg(factor
, factor
);
1472 c
= isl_constraint_copy(c
);
1473 s
= cloog_stride_alloc_from_constraint(stride
,
1474 cloog_constraint_from_isl_constraint(c
), factor
);
1477 isl_int_clear(stride
);
1478 isl_int_clear(factor
);
1486 struct cloog_isl_find_stride_data
{
1488 CloogStride
*stride
;
1491 /* Check if the given constraint can be used to derive
1492 * a stride on the iterator identified by data->level.
1493 * We first check that there are some existentially quantified variables
1494 * and that the coefficient at data->level is non-zero.
1495 * Then we call construct_stride for further checks and the actual
1496 * construction of the CloogStride.
1498 static int find_stride(__isl_take isl_constraint
*c
, void *user
)
1500 struct cloog_isl_find_stride_data
*data
;
1504 data
= (struct cloog_isl_find_stride_data
*)user
;
1507 isl_constraint_free(c
);
1511 n
= isl_constraint_dim(c
, isl_dim_div
);
1513 isl_constraint_free(c
);
1519 isl_constraint_get_coefficient(c
, isl_dim_set
, data
->level
- 1, &v
);
1520 if (!isl_int_is_zero(v
))
1521 data
->stride
= construct_stride(c
, data
->level
);
1525 isl_constraint_free(c
);
1530 /* Check if the given list of domains has a common stride on the given level.
1531 * If so, return a pointer to a CloogStride object. If not, return NULL.
1533 * We project out all later variables, take the union and compute
1534 * the affine hull of the union. Then we check the (equality)
1535 * constraints in this affine hull for imposing a stride.
1537 CloogStride
*cloog_domain_list_stride(CloogDomainList
*list
, int level
)
1539 struct cloog_isl_find_stride_data data
= { level
, NULL
};
1546 n
= isl_set_dim(&list
->domain
->set
, isl_dim_set
) - first
;
1547 set
= isl_set_project_out(isl_set_copy(&list
->domain
->set
),
1548 isl_dim_set
, first
, n
);
1550 for (list
= list
->next
; list
; list
= list
->next
) {
1552 n
= isl_set_dim(&list
->domain
->set
, isl_dim_set
) - first
;
1553 set_i
= isl_set_project_out(isl_set_copy(&list
->domain
->set
),
1554 isl_dim_set
, first
, n
);
1555 set
= isl_set_union(set
, set_i
);
1557 aff
= isl_set_affine_hull(set
);
1559 r
= isl_basic_set_foreach_constraint(aff
, &find_stride
, &data
);
1562 isl_basic_set_free(aff
);