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 __isl_give isl_set
*isl_set_from_cloog_domain(CloogDomain
*domain
)
23 CloogScattering
*cloog_scattering_from_isl_map(struct isl_map
*map
)
25 return (CloogScattering
*)map
;
30 * Returns true if each scattering dimension is defined in terms
31 * of the original iterators.
33 int cloog_scattering_fully_specified(CloogScattering
*scattering
,
36 return isl_map_is_single_valued(&scattering
->map
);
40 CloogConstraintSet
*cloog_domain_constraints(CloogDomain
*domain
)
42 assert(domain
->set
.n
== 1);
43 return cloog_constraint_set_from_isl_basic_set(
44 isl_basic_set_copy(domain
->set
.p
[0]));
48 void cloog_domain_print_constraints(FILE *foo
, CloogDomain
*domain
,
52 isl_set_print(&domain
->set
, foo
, 0, ISL_FORMAT_EXT_POLYLIB
);
54 assert(domain
->set
.n
== 1);
55 isl_basic_set_print(domain
->set
.p
[0], foo
,
56 0, NULL
, NULL
, ISL_FORMAT_POLYLIB
);
61 void cloog_scattering_print_constraints(FILE *foo
, CloogScattering
*scattering
,
65 isl_map_print(&scattering
->map
, foo
, 0, ISL_FORMAT_EXT_POLYLIB
);
67 assert(scattering
->map
.n
== 1);
68 isl_basic_map_print(scattering
->map
.p
[0], foo
,
69 0, NULL
, NULL
, ISL_FORMAT_POLYLIB
);
74 void cloog_domain_free(CloogDomain
* domain
)
76 isl_set_free(&domain
->set
);
80 void cloog_scattering_free(CloogScattering
*scatt
)
82 isl_map_free(&scatt
->map
);
86 CloogDomain
* cloog_domain_copy(CloogDomain
* domain
)
88 return cloog_domain_from_isl_set(isl_set_copy(&domain
->set
));
93 * cloog_domain_convex function:
94 * Computes the convex hull of domain.
96 CloogDomain
*cloog_domain_convex(CloogDomain
*domain
)
98 struct isl_set
*set
= &domain
->set
;
99 set
= isl_set_from_basic_set(isl_set_convex_hull(isl_set_copy(set
)));
100 return cloog_domain_from_isl_set(set
);
105 * cloog_domain_simple_convex:
106 * Given a list (union) of polyhedra, this function returns a "simple"
107 * convex hull of this union. In particular, the constraints of the
108 * the returned polyhedron consist of (parametric) lower and upper
109 * bounds on individual variables and constraints that appear in the
110 * original polyhedra.
112 CloogDomain
*cloog_domain_simple_convex(CloogDomain
*domain
)
114 struct isl_basic_set
*hull
;
115 unsigned dim
= isl_set_n_dim(&domain
->set
);
117 if (cloog_domain_isconvex(domain
))
118 return cloog_domain_copy(domain
);
121 return cloog_domain_convex(domain
);
123 hull
= isl_set_bounded_simple_hull(isl_set_copy(&domain
->set
));
124 return cloog_domain_from_isl_set(isl_set_from_basic_set(hull
));
129 * cloog_domain_simplify function:
130 * Given two polyhedral domains (dom1) and (dom2),
131 * this function finds the largest domain set (or the smallest list
132 * of non-redundant constraints), that when intersected with polyhedral
133 * domain (dom2) equals (dom1)intersect(dom2). The output is a new CloogDomain
134 * structure with a polyhedral domain with the "redundant" constraints removed.
135 * NB: the second domain is required not to be a union.
137 CloogDomain
*cloog_domain_simplify(CloogDomain
*dom1
, CloogDomain
*dom2
)
140 set
= isl_set_gist(isl_set_copy(&dom1
->set
), isl_set_copy(&dom2
->set
));
141 return cloog_domain_from_isl_set(set
);
146 * cloog_domain_union function:
147 * This function returns a new polyhedral domain which is the union of
148 * two polyhedral domains (dom1) U (dom2).
149 * Frees dom1 and dom2;
151 CloogDomain
*cloog_domain_union(CloogDomain
*dom1
, CloogDomain
*dom2
)
154 set
= isl_set_union(&dom1
->set
, &dom2
->set
);
155 return cloog_domain_from_isl_set(set
);
161 * cloog_domain_intersection function:
162 * This function returns a new polyhedral domain which is the intersection of
163 * two polyhedral domains (dom1) \cap (dom2).
165 CloogDomain
*cloog_domain_intersection(CloogDomain
*dom1
, CloogDomain
*dom2
)
168 set
= isl_set_intersect(isl_set_copy(&dom1
->set
),
169 isl_set_copy(&dom2
->set
));
170 return cloog_domain_from_isl_set(set
);
175 * cloog_domain_difference function:
176 * Returns the set difference domain \ minus.
178 CloogDomain
*cloog_domain_difference(CloogDomain
*domain
, CloogDomain
*minus
)
181 set
= isl_set_subtract(isl_set_copy(&domain
->set
),
182 isl_set_copy(&minus
->set
));
183 return cloog_domain_from_isl_set(set
);
188 * cloog_domain_sort function:
189 * This function topologically sorts (nb_doms) domains. Here (doms) is an
190 * array of pointers to CloogDomains, (nb_doms) is the number of domains,
191 * (level) is the level to consider for partial ordering (nb_par) is the
192 * parameter space dimension, (permut) if not NULL, is an array of (nb_doms)
193 * integers that contains a permutation specification after call in order to
194 * apply the topological sorting.
196 void cloog_domain_sort(CloogDomain
**doms
, unsigned nb_doms
, unsigned level
,
201 unsigned char **follows
;
205 ctx
= doms
[0]->set
.ctx
;
206 for (i
= 0; i
< nb_doms
; i
++)
207 assert(doms
[i
]->set
.n
== 1);
209 follows
= isl_alloc_array(ctx
, unsigned char *, nb_doms
);
211 for (i
= 0; i
< nb_doms
; ++i
) {
212 follows
[i
] = isl_alloc_array(ctx
, unsigned char, nb_doms
);
214 for (j
= 0; j
< nb_doms
; ++j
)
218 for (i
= 1; i
< nb_doms
; ++i
) {
219 for (j
= 0; j
< i
; ++j
) {
220 if (follows
[i
][j
] || follows
[j
][i
])
222 cmp
= isl_basic_set_compare_at(doms
[i
]->set
.p
[0],
223 doms
[j
]->set
.p
[0], level
-1);
228 for (k
= 0; k
< i
; ++k
)
229 follows
[i
][k
] |= follows
[j
][k
];
232 for (k
= 0; k
< i
; ++k
)
233 follows
[k
][i
] |= follows
[k
][j
];
238 for (i
= 0, j
= 0; i
< nb_doms
; j
= (j
+ 1) % nb_doms
) {
239 for (k
= 0; k
< nb_doms
; ++k
)
244 for (k
= 0; k
< nb_doms
; ++k
)
251 for (i
= 0; i
< nb_doms
; ++i
)
258 * Check whether there is or may be any value of dom1 at the given level
259 * that is greater than or equal to a value of dom2 at the same level.
262 * 1 is there is or may be a greater-than pair.
263 * 0 if there is no greater-than pair, but there may be an equal-to pair
264 * -1 if there is definitely no such pair
266 int cloog_domain_follows(CloogDomain
*dom1
, CloogDomain
*dom2
, unsigned level
)
270 follows
= isl_set_follows_at(&dom1
->set
, &dom2
->set
, level
- 1);
271 assert(follows
>= -1);
278 * cloog_domain_empty function:
279 * Returns an empty domain of the same dimensions as template.
281 CloogDomain
*cloog_domain_empty(CloogDomain
*template)
283 return cloog_domain_from_isl_set(isl_set_empty_like(&template->set
));
288 * Return 1 if the specified dimension has both an upper and a lower bound.
290 int cloog_domain_is_bounded(CloogDomain
*dom
, unsigned level
)
292 return isl_set_dim_is_bounded(&dom
->set
, isl_dim_set
, level
- 1);
296 /******************************************************************************
297 * Structure display function *
298 ******************************************************************************/
302 * cloog_domain_print_structure :
303 * this function is a more human-friendly way to display the CloogDomain data
304 * structure, it only shows the constraint system and includes an indentation
305 * level (level) in order to work with others print_structure functions.
307 void cloog_domain_print_structure(FILE *file
, CloogDomain
*domain
, int level
,
311 struct isl_set
*set
= &domain
->set
;
313 /* Go to the right level. */
314 for (i
= 0; i
< level
; i
++)
315 fprintf(file
, "|\t");
318 fprintf(file
, "+-- Null CloogDomain\n");
321 fprintf(file
, "+-- %s\n", name
);
322 for (i
= 0; i
< level
+1; ++i
)
323 fprintf(file
, "|\t");
325 isl_set_print(set
, file
, 0, ISL_FORMAT_ISL
);
331 /******************************************************************************
332 * Memory deallocation function *
333 ******************************************************************************/
336 void cloog_domain_list_free(CloogDomainList
*list
)
338 CloogDomainList
*next
;
340 for ( ; list
; list
= next
) {
342 cloog_domain_free(list
->domain
);
349 * cloog_scattering_list_free function:
350 * This function frees the allocated memory for a CloogScatteringList structure.
352 void cloog_scattering_list_free(CloogScatteringList
*list
)
354 while (list
!= NULL
) {
355 CloogScatteringList
*temp
= list
->next
;
356 isl_map_free(&list
->scatt
->map
);
363 /******************************************************************************
365 ******************************************************************************/
369 * cloog_domain_read_context function:
370 * Read parameter domain.
372 CloogDomain
*cloog_domain_read_context(CloogState
*state
, FILE *input
)
374 struct isl_ctx
*ctx
= state
->backend
->ctx
;
377 set
= isl_set_read_from_file(ctx
, input
, 0);
378 set
= isl_set_move_dims(set
, isl_dim_param
, 0,
379 isl_dim_set
, 0, isl_set_dim(set
, isl_dim_set
));
381 return cloog_domain_from_isl_set(set
);
386 * cloog_domain_from_context
387 * Reinterpret context by turning parameters into variables.
389 CloogDomain
*cloog_domain_from_context(CloogDomain
*context
)
391 isl_set
*set
= &context
->set
;
393 set
= isl_set_move_dims(set
, isl_dim_set
, 0,
394 isl_dim_param
, 0, isl_set_dim(set
, isl_dim_param
));
396 return cloog_domain_from_isl_set(set
);
401 * cloog_domain_union_read function:
402 * This function reads a union of polyhedra into a file (input) and
403 * returns a pointer to a CloogDomain containing the read information.
405 CloogDomain
*cloog_domain_union_read(CloogState
*state
,
406 FILE *input
, int nb_parameters
)
408 struct isl_ctx
*ctx
= state
->backend
->ctx
;
411 set
= isl_set_read_from_file(ctx
, input
, nb_parameters
);
412 return cloog_domain_from_isl_set(set
);
417 * cloog_domain_read_scattering function:
418 * This function reads in a scattering function from the file input.
420 * We try to read the scattering relation as a map, but if it is
421 * specified in the original PolyLib format, then isl_map_read_from_file
422 * will treat the input as a set return a map with zero input dimensions.
423 * In this case, we need to decompose the set into a map from
424 * scattering dimensions to domain dimensions and then invert the
427 CloogScattering
*cloog_domain_read_scattering(CloogDomain
*domain
, FILE *input
)
429 struct isl_ctx
*ctx
= domain
->set
.ctx
;
430 struct isl_map
*scat
;
435 dim
= isl_set_n_dim(&domain
->set
);
436 nparam
= isl_set_n_param(&domain
->set
);
437 scat
= isl_map_read_from_file(ctx
, input
, nparam
);
438 if (isl_map_dim(scat
, isl_dim_in
) != dim
) {
439 n_scat
= isl_map_dim(scat
, isl_dim_out
) - dim
;
440 scat
= isl_map_move_dims(scat
, isl_dim_in
, 0,
441 isl_dim_out
, n_scat
, dim
);
443 return cloog_scattering_from_isl_map(scat
);
446 /******************************************************************************
447 * CloogMatrix Reading function *
448 ******************************************************************************/
451 * isl_constraint_read_from_matrix:
452 * Convert a single line of a matrix to a isl_constraint.
453 * Returns a pointer to the constraint if successful; NULL otherwise.
455 static struct isl_constraint
*isl_constraint_read_from_matrix(
456 struct isl_dim
*dim
, cloog_int_t
*row
)
458 struct isl_constraint
*constraint
;
460 int nvariables
= isl_dim_size(dim
, isl_dim_set
);
461 int nparam
= isl_dim_size(dim
, isl_dim_param
);
463 if (cloog_int_is_zero(row
[0]))
464 constraint
= isl_equality_alloc(dim
);
466 constraint
= isl_inequality_alloc(dim
);
468 for (j
= 0; j
< nvariables
; ++j
)
469 isl_constraint_set_coefficient(constraint
, isl_dim_out
, j
,
472 for (j
= 0; j
< nparam
; ++j
)
473 isl_constraint_set_coefficient(constraint
, isl_dim_param
, j
,
474 row
[1 + nvariables
+ j
]);
476 isl_constraint_set_constant(constraint
, row
[1 + nvariables
+ nparam
]);
482 * isl_basic_set_read_from_matrix:
483 * Convert matrix to basic_set. The matrix contains nparam parameter columns.
484 * Returns a pointer to the basic_set if successful; NULL otherwise.
486 static struct isl_basic_set
*isl_basic_set_read_from_matrix(struct isl_ctx
*ctx
,
487 CloogMatrix
* matrix
, int nparam
)
490 struct isl_basic_set
*bset
;
492 unsigned nrows
, ncolumns
;
494 nrows
= matrix
->NbRows
;
495 ncolumns
= matrix
->NbColumns
;
496 int nvariables
= ncolumns
- 2 - nparam
;
498 dim
= isl_dim_set_alloc(ctx
, nparam
, nvariables
);
500 bset
= isl_basic_set_universe(isl_dim_copy(dim
));
502 for (i
= 0; i
< nrows
; ++i
) {
503 cloog_int_t
*row
= matrix
->p
[i
];
504 struct isl_constraint
*constraint
=
505 isl_constraint_read_from_matrix(isl_dim_copy(dim
), row
);
506 bset
= isl_basic_set_add_constraint(bset
, constraint
);
515 * cloog_domain_from_cloog_matrix:
516 * Create a CloogDomain containing the constraints described in matrix.
517 * nparam is the number of parameters contained in the domain.
518 * Returns a pointer to the CloogDomain if successful; NULL otherwise.
520 CloogDomain
*cloog_domain_from_cloog_matrix(CloogState
*state
,
521 CloogMatrix
*matrix
, int nparam
)
523 struct isl_ctx
*ctx
= state
->backend
->ctx
;
524 struct isl_basic_set
*bset
;
526 bset
= isl_basic_set_read_from_matrix(ctx
, matrix
, nparam
);
528 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset
));
532 * cloog_scattering_from_cloog_matrix:
533 * Create a CloogScattering containing the constraints described in matrix.
534 * nparam is the number of parameters contained in the domain.
535 * Returns a pointer to the CloogScattering if successful; NULL otherwise.
537 CloogScattering
*cloog_scattering_from_cloog_matrix(CloogState
*state
,
538 CloogMatrix
*matrix
, int nb_scat
, int nb_par
)
540 struct isl_ctx
*ctx
= state
->backend
->ctx
;
541 struct isl_basic_set
*bset
;
542 struct isl_basic_map
*scat
;
543 struct isl_dim
*dims
;
546 bset
= isl_basic_set_read_from_matrix(ctx
, matrix
, nb_par
);
547 dim
= isl_basic_set_n_dim(bset
) - nb_scat
;
548 dims
= isl_dim_alloc(ctx
, nb_par
, nb_scat
, dim
);
550 scat
= isl_basic_map_from_basic_set(bset
, dims
);
551 scat
= isl_basic_map_reverse(scat
);
552 return cloog_scattering_from_isl_map(isl_map_from_basic_map(scat
));
556 /******************************************************************************
557 * Processing functions *
558 ******************************************************************************/
563 * cloog_domain_isempty function:
565 int cloog_domain_isempty(CloogDomain
*domain
)
567 return isl_set_is_empty(&domain
->set
);
572 * cloog_domain_universe function:
573 * This function returns the complete dim-dimensional space.
575 CloogDomain
*cloog_domain_universe(CloogState
*state
, unsigned dim
)
577 struct isl_dim
*dims
;
578 struct isl_basic_set
*bset
;
580 dims
= isl_dim_set_alloc(state
->backend
->ctx
, 0, dim
);
581 bset
= isl_basic_set_universe(dims
);
582 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset
));
587 * cloog_domain_project function:
588 * This function returns the projection of
589 * (domain) on the (level) first dimensions (i.e. outer loops).
591 CloogDomain
*cloog_domain_project(CloogDomain
*domain
, int level
)
593 struct isl_set
*set
= &domain
->set
;
594 set
= isl_set_remove_dims(isl_set_copy(set
), isl_dim_set
,
595 level
, isl_set_n_dim(set
) - level
);
596 set
= isl_set_compute_divs(set
);
598 set
= isl_set_remove_divs_involving_dims(set
,
599 isl_dim_set
, level
- 1, 1);
600 return cloog_domain_from_isl_set(set
);
605 * cloog_domain_extend function:
606 * This function returns the (domain) given as input with (dim)
607 * dimensions and (nb_par) parameters.
608 * This function does not free (domain), and returns a new CloogDomain.
610 CloogDomain
*cloog_domain_extend(CloogDomain
*domain
, int dim
)
612 struct isl_set
*set
= &domain
->set
;
613 set
= isl_set_extend(isl_set_copy(set
), isl_set_n_param(set
), dim
);
614 return cloog_domain_from_isl_set(set
);
619 * cloog_domain_never_integral function:
620 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0.
621 * There is no need to check for such constraints explicitly for the isl
624 int cloog_domain_never_integral(CloogDomain
* domain
)
626 return isl_set_is_empty(&domain
->set
);
631 * Check whether the loop at "level" is executed at most once.
632 * We construct a map that maps all remaining variables to this iterator
633 * and check whether this map is single valued.
635 * Alternatively, we could have mapped the domain through a mapping
636 * [p] -> { [..., i] -> [..., i'] : i' > i }
637 * and then taken the intersection of the original domain and the transformed
638 * domain. If this intersection is empty, then the corresponding
639 * loop is executed at most once.
641 int cloog_domain_is_otl(CloogDomain
*domain
, int level
)
646 map
= isl_map_from_domain(isl_set_copy(&domain
->set
));
647 map
= isl_map_move_dims(map
, isl_dim_out
, 0, isl_dim_in
, level
- 1, 1);
648 otl
= isl_map_is_single_valued(map
);
656 * cloog_domain_stride function:
657 * This function finds the stride imposed to unknown with the column number
658 * 'strided_level' in order to be integral. For instance, if we have a
659 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
660 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
661 * the unknown i. The function returns the imposed stride in a parameter field.
662 * - domain is the set of constraint we have to consider,
663 * - strided_level is the column number of the unknown for which a stride have
665 * - looking_level is the column number of the unknown that impose a stride to
667 * - stride is the stride that is returned back as a function parameter.
668 * - offset is the value of the constant c if the condition is of the shape
669 * (i + c)%s = 0, s being the stride.
671 void cloog_domain_stride(CloogDomain
*domain
, int strided_level
,
672 cloog_int_t
*stride
, cloog_int_t
*offset
)
674 struct isl_set
*set
= &domain
->set
;
675 isl_set_dim_residue_class(set
, strided_level
- 1, stride
, offset
);
676 if (!isl_int_is_zero(*offset
))
677 isl_int_sub(*offset
, *stride
, *offset
);
682 struct cloog_can_stride
{
687 static int constraint_can_stride(__isl_take isl_constraint
*c
, void *user
)
689 struct cloog_can_stride
*ccs
= (struct cloog_can_stride
*)user
;
695 isl_constraint_get_coefficient(c
, isl_dim_set
, ccs
->level
- 1, &v
);
696 if (isl_int_is_pos(v
)) {
697 n_div
= isl_constraint_dim(c
, isl_dim_div
);
698 for (i
= 0; i
< n_div
; ++i
) {
699 isl_constraint_get_coefficient(c
, isl_dim_div
, i
, &v
);
700 if (!isl_int_is_zero(v
))
707 isl_constraint_free(c
);
712 static int basic_set_can_stride(__isl_take isl_basic_set
*bset
, void *user
)
714 struct cloog_can_stride
*ccs
= (struct cloog_can_stride
*)user
;
717 r
= isl_basic_set_foreach_constraint(bset
, constraint_can_stride
, ccs
);
718 isl_basic_set_free(bset
);
724 * Return 1 if CLooG is allowed to perform stride detection on level "level"
726 * Currently, stride detection is only allowed when none of the lower
727 * bound constraints involve any existentially quantified variables.
728 * The reason is that the current isl interface does not make it
729 * easy to construct an integer division that depends on other integer
731 * By not allowing existentially quantified variables in the constraints,
732 * we can ignore them in cloog_domain_stride_lower_bound.
734 int cloog_domain_can_stride(CloogDomain
*domain
, int level
)
736 struct cloog_can_stride ccs
= { level
, 1 };
738 r
= isl_set_foreach_basic_set(&domain
->set
, basic_set_can_stride
, &ccs
);
740 return ccs
.can_stride
;
744 struct cloog_stride_lower
{
748 isl_basic_set
*bounds
;
751 /* If the given constraint is a lower bound on csl->level, then add
752 * a lower bound to csl->bounds that makes sure that the remainder
753 * of the smallest value on division by csl->stride is equal to csl->offset.
755 * In particular, the given lower bound is of the form
759 * where f may depend on the parameters and other iterators.
760 * The stride is s and the offset is d.
761 * The lower bound -f/a may not satisfy the above condition. In fact,
762 * it may not even be integral. We want to round this value of i up
763 * to the nearest value that satisfies the condition and add the corresponding
764 * lower bound constraint. This nearest value is obtained by rounding
765 * i - d up to the nearest multiple of s.
766 * That is, we first subtract d
770 * then we round up to the nearest multiple of s
772 * i'' = s * ceil(i'/s)
774 * and finally, we add d again
778 * and impose the constraint i >= i'''.
782 * i'' = s * ceil((-f - a * d)/(a * s)) = - s * floor((f + a * d)/(a * s))
784 * i >= - s * floor((f + a * d)/(a * s)) + d
787 * i + s * floor((f + a * d)/(a * s)) - d >= 0
789 static int constraint_stride_lower(__isl_take isl_constraint
*c
, void *user
)
791 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
795 isl_constraint
*bound
;
798 unsigned nparam
, nvar
;
801 isl_constraint_get_coefficient(c
, isl_dim_set
, csl
->level
- 1, &v
);
802 if (!isl_int_is_pos(v
)) {
804 isl_constraint_free(c
);
811 nparam
= isl_constraint_dim(c
, isl_dim_param
);
812 nvar
= isl_constraint_dim(c
, isl_dim_set
);
813 bound
= isl_inequality_alloc(isl_basic_set_get_dim(csl
->bounds
));
814 div
= isl_div_alloc(isl_basic_set_get_dim(csl
->bounds
));
815 isl_int_mul(t
, v
, csl
->stride
->stride
);
816 isl_div_set_denominator(div
, t
);
817 for (i
= 0; i
< nparam
; ++i
) {
818 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &t
);
819 isl_div_set_coefficient(div
, isl_dim_param
, i
, t
);
821 for (i
= 0; i
< nvar
; ++i
) {
822 if (i
== csl
->level
- 1)
824 isl_constraint_get_coefficient(c
, isl_dim_set
, i
, &t
);
825 isl_div_set_coefficient(div
, isl_dim_set
, i
, t
);
827 isl_constraint_get_constant(c
, &t
);
828 isl_int_addmul(t
, v
, csl
->stride
->offset
);
829 isl_div_set_constant(div
, t
);
831 bound
= isl_constraint_add_div(bound
, div
, &pos
);
832 isl_int_set_si(t
, 1);
833 isl_constraint_set_coefficient(bound
, isl_dim_set
,
835 isl_constraint_set_coefficient(bound
, isl_dim_div
, pos
,
836 csl
->stride
->stride
);
837 isl_int_neg(t
, csl
->stride
->offset
);
838 isl_constraint_set_constant(bound
, t
);
839 csl
->bounds
= isl_basic_set_add_constraint(csl
->bounds
, bound
);
843 isl_constraint_free(c
);
848 /* This functions performs essentially the same operation as
849 * constraint_stride_lower, the only difference being that the offset d
850 * is not a constant, but an affine expression in terms of the parameters
851 * and earlier variables. In particular the affine expression is equal
852 * to the coefficients of stride->constraint multiplied by stride->factor.
853 * As in constraint_stride_lower, we add an extra bound
855 * i + s * floor((f + a * d)/(a * s)) - d >= 0
857 * for each lower bound
861 * where d is not the aforementioned affine expression.
863 static int constraint_stride_lower_c(__isl_take isl_constraint
*c
, void *user
)
865 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
869 isl_constraint
*bound
;
870 isl_constraint
*csl_c
;
873 unsigned nparam
, nvar
;
876 isl_constraint_get_coefficient(c
, isl_dim_set
, csl
->level
- 1, &v
);
877 if (!isl_int_is_pos(v
)) {
879 isl_constraint_free(c
);
884 csl_c
= &csl
->stride
->constraint
->isl
;
889 nparam
= isl_constraint_dim(c
, isl_dim_param
);
890 nvar
= isl_constraint_dim(c
, isl_dim_set
);
891 bound
= isl_inequality_alloc(isl_basic_set_get_dim(csl
->bounds
));
892 div
= isl_div_alloc(isl_basic_set_get_dim(csl
->bounds
));
893 isl_int_mul(t
, v
, csl
->stride
->stride
);
894 isl_div_set_denominator(div
, t
);
895 for (i
= 0; i
< nparam
; ++i
) {
896 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &t
);
897 isl_constraint_get_coefficient(csl_c
, isl_dim_param
, i
, &u
);
898 isl_int_mul(u
, u
, csl
->stride
->factor
);
899 isl_int_addmul(t
, v
, u
);
900 isl_div_set_coefficient(div
, isl_dim_param
, i
, t
);
902 isl_constraint_set_coefficient(bound
, isl_dim_param
, i
, u
);
904 for (i
= 0; i
< nvar
; ++i
) {
905 if (i
== csl
->level
- 1)
907 isl_constraint_get_coefficient(c
, isl_dim_set
, i
, &t
);
908 isl_constraint_get_coefficient(csl_c
, isl_dim_set
, i
, &u
);
909 isl_int_mul(u
, u
, csl
->stride
->factor
);
910 isl_int_addmul(t
, v
, u
);
911 isl_div_set_coefficient(div
, isl_dim_set
, i
, t
);
913 isl_constraint_set_coefficient(bound
, isl_dim_set
, i
, u
);
915 isl_constraint_get_constant(c
, &t
);
916 isl_constraint_get_constant(csl_c
, &u
);
917 isl_int_mul(u
, u
, csl
->stride
->factor
);
918 isl_int_addmul(t
, v
, u
);
919 isl_div_set_constant(div
, t
);
921 isl_constraint_set_constant(bound
, u
);
923 bound
= isl_constraint_add_div(bound
, div
, &pos
);
924 isl_int_set_si(t
, 1);
925 isl_constraint_set_coefficient(bound
, isl_dim_set
,
927 isl_constraint_set_coefficient(bound
, isl_dim_div
, pos
,
928 csl
->stride
->stride
);
929 csl
->bounds
= isl_basic_set_add_constraint(csl
->bounds
, bound
);
934 isl_constraint_free(c
);
939 static int basic_set_stride_lower(__isl_take isl_basic_set
*bset
, void *user
)
941 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
944 csl
->bounds
= isl_basic_set_universe_like(bset
);
945 if (csl
->stride
->constraint
)
946 r
= isl_basic_set_foreach_constraint(bset
,
947 &constraint_stride_lower_c
, csl
);
949 r
= isl_basic_set_foreach_constraint(bset
,
950 &constraint_stride_lower
, csl
);
951 bset
= isl_basic_set_intersect(bset
, csl
->bounds
);
952 csl
->set
= isl_set_union(csl
->set
, isl_set_from_basic_set(bset
));
958 * Update the lower bounds at level "level" to the given stride information.
959 * That is, make sure that the remainder on division by "stride"
960 * is equal to "offset".
962 CloogDomain
*cloog_domain_stride_lower_bound(CloogDomain
*domain
, int level
,
965 struct cloog_stride_lower csl
;
970 csl
.set
= isl_set_empty_like(&domain
->set
);
972 r
= isl_set_foreach_basic_set(&domain
->set
, basic_set_stride_lower
, &csl
);
975 cloog_domain_free(domain
);
976 return cloog_domain_from_isl_set(csl
.set
);
981 * cloog_domain_lazy_equal function:
982 * This function returns 1 if the domains given as input are the same, 0 if it
983 * is unable to decide.
985 int cloog_domain_lazy_equal(CloogDomain
*d1
, CloogDomain
*d2
)
987 return isl_set_fast_is_equal(&d1
->set
, &d2
->set
);
990 struct cloog_bound_split
{
997 static int constraint_bound_split(__isl_take isl_constraint
*c
, void *user
)
999 struct cloog_bound_split
*cbs
= (struct cloog_bound_split
*)user
;
1005 isl_constraint_get_coefficient(c
, isl_dim_set
, cbs
->level
- 1, &v
);
1006 if (!cbs
->lower
&& isl_int_is_pos(v
))
1007 cbs
->lower
= handle
= 1;
1008 else if (!cbs
->upper
&& isl_int_is_neg(v
))
1009 cbs
->upper
= handle
= 1;
1011 for (i
= 0; i
< isl_set_dim(cbs
->set
, isl_dim_param
); ++i
) {
1012 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &v
);
1013 if (isl_int_is_zero(v
))
1015 cbs
->set
= isl_set_split_dims(cbs
->set
,
1016 isl_dim_param
, i
, 1);
1020 isl_constraint_free(c
);
1022 return (cbs
->lower
&& cbs
->upper
) ? -1 : 0;
1025 static int basic_set_bound_split(__isl_take isl_basic_set
*bset
, void *user
)
1027 struct cloog_bound_split
*cbs
= (struct cloog_bound_split
*)user
;
1032 r
= isl_basic_set_foreach_constraint(bset
, constraint_bound_split
, cbs
);
1033 isl_basic_set_free(bset
);
1034 return ((!cbs
->lower
|| !cbs
->upper
) && r
< 0) ? -1 : 0;
1038 * Return a union of sets S_i such that the convex hull of "dom",
1039 * when intersected with one the sets S_i, will have an upper and
1040 * lower bound for the dimension at "level" (provided "dom" itself
1041 * has such bounds for the dimensions).
1043 * We currently take a very simple approach. For each of the basic
1044 * sets in "dom" we pick a lower and an upper bound and split the
1045 * range of any parameter involved in these two bounds in a
1046 * nonnegative and a negative part. This ensures that the symbolic
1047 * constant in these two constraints are themselves bounded and
1048 * so there will be at least one upper and one lower bound
1049 * in the convex hull.
1051 CloogDomain
*cloog_domain_bound_splitter(CloogDomain
*dom
, int level
)
1053 struct cloog_bound_split cbs
;
1056 cbs
.set
= isl_set_universe_like(&dom
->set
);
1057 r
= isl_set_foreach_basic_set(&dom
->set
, basic_set_bound_split
, &cbs
);
1059 return cloog_domain_from_isl_set(cbs
.set
);
1064 * cloog_scattering_lazy_block function:
1065 * This function returns 1 if the two scattering functions s1 and s2 given
1066 * as input are the same (except possibly for the final dimension, where we
1067 * allow a difference of 1), assuming that the domains on which this
1068 * scatterings are applied are the same.
1069 * In fact this function answers the question "can I
1070 * safely consider the two domains as only one with two statements (a block) ?".
1071 * - s1 and s2 are the two domains to check for blocking,
1072 * - scattering is the linked list of all domains,
1073 * - scattdims is the total number of scattering dimentions.
1075 int cloog_scattering_lazy_block(CloogScattering
*s1
, CloogScattering
*s2
,
1076 CloogScatteringList
*scattering
, int scattdims
)
1079 struct isl_dim
*dim
;
1080 struct isl_map
*rel
;
1081 struct isl_set
*delta
;
1086 n_scat
= isl_map_dim(&s1
->map
, isl_dim_out
);
1087 if (n_scat
!= isl_map_dim(&s2
->map
, isl_dim_out
))
1090 dim
= isl_dim_copy(s1
->map
.dim
);
1091 dim
= isl_dim_domain(dim
);
1092 rel
= isl_map_identity(dim
);
1093 rel
= isl_map_apply_domain(rel
, isl_map_copy(&s1
->map
));
1094 rel
= isl_map_apply_range(rel
, isl_map_copy(&s2
->map
));
1095 delta
= isl_map_deltas(rel
);
1097 for (i
= 0; i
< n_scat
; ++i
) {
1098 fixed
= isl_set_fast_dim_is_fixed(delta
, i
, &cst
);
1101 if (i
+1 < n_scat
&& !isl_int_is_zero(cst
))
1103 if (!isl_int_is_zero(cst
) && !isl_int_is_one(cst
))
1106 block
= i
>= n_scat
;
1108 isl_set_free(delta
);
1114 * cloog_domain_lazy_disjoint function:
1115 * This function returns 1 if the domains given as input are disjoint, 0 if it
1116 * is unable to decide.
1118 int cloog_domain_lazy_disjoint(CloogDomain
*d1
, CloogDomain
*d2
)
1120 return isl_set_fast_is_disjoint(&d1
->set
, &d2
->set
);
1125 * cloog_scattering_list_lazy_same function:
1126 * This function returns 1 if two domains in the list are the same, 0 if it
1127 * is unable to decide.
1129 int cloog_scattering_list_lazy_same(CloogScatteringList
*list
)
1131 CloogScatteringList
*one
, *other
;
1133 for (one
= list
; one
; one
= one
->next
)
1134 for (other
= one
->next
; other
; other
= other
->next
)
1135 if (isl_map_fast_is_equal(&one
->scatt
->map
,
1136 &other
->scatt
->map
))
1141 int cloog_domain_dimension(CloogDomain
* domain
)
1143 return isl_set_n_dim(&domain
->set
);
1146 int cloog_domain_parameter_dimension(CloogDomain
*domain
)
1148 return isl_set_n_param(&domain
->set
);
1151 int cloog_scattering_dimension(CloogScattering
*scatt
, CloogDomain
*domain
)
1153 return isl_map_dim(&scatt
->map
, isl_dim_out
);
1156 int cloog_domain_isconvex(CloogDomain
* domain
)
1158 return domain
->set
.n
<= 1;
1163 * cloog_domain_cut_first function:
1164 * This function splits off and returns the first convex set in the
1165 * union "domain". The remainder of the union is returned in rest.
1166 * The original "domain" itself is destroyed and may not be used
1167 * after a call to this function.
1169 CloogDomain
*cloog_domain_cut_first(CloogDomain
*domain
, CloogDomain
**rest
)
1171 struct isl_set
*set
;
1172 struct isl_basic_set
*first
;
1175 first
= isl_set_copy_basic_set(set
);
1176 set
= isl_set_drop_basic_set(set
, first
);
1177 *rest
= cloog_domain_from_isl_set(set
);
1179 return cloog_domain_from_isl_set(isl_set_from_basic_set(first
));
1184 * Given a union domain, try to find a simpler representation
1185 * using fewer sets in the union.
1186 * The original "domain" itself is destroyed and may not be used
1187 * after a call to this function.
1189 CloogDomain
*cloog_domain_simplify_union(CloogDomain
*domain
)
1191 return cloog_domain_from_isl_set(isl_set_coalesce(&domain
->set
));
1196 * cloog_scattering_lazy_isscalar function:
1197 * this function returns 1 if the scattering dimension 'dimension' in the
1198 * scattering 'scatt' is constant.
1199 * If value is not NULL, then it is set to the constant value of dimension.
1201 int cloog_scattering_lazy_isscalar(CloogScattering
*scatt
, int dimension
,
1204 return isl_map_fast_is_fixed(&scatt
->map
, isl_dim_out
, dimension
, value
);
1209 * cloog_domain_lazy_isconstant function:
1210 * this function returns 1 if the dimension 'dimension' in the
1211 * domain 'domain' is constant.
1212 * If value is not NULL, then it is set to the constant value of dimension.
1214 int cloog_domain_lazy_isconstant(CloogDomain
*domain
, int dimension
)
1216 return isl_set_fast_dim_is_fixed(&domain
->set
, dimension
, NULL
);
1221 * cloog_scattering_erase_dimension function:
1222 * this function returns a CloogDomain structure builds from 'domain' where
1223 * we removed the dimension 'dimension' and every constraint involving this
1226 CloogScattering
*cloog_scattering_erase_dimension(CloogScattering
*domain
,
1229 struct isl_map
*map
;
1230 map
= isl_map_remove_dims(isl_map_copy(&domain
->map
),
1231 isl_dim_out
, dimension
, 1);
1232 return cloog_scattering_from_isl_map(map
);
1236 * cloog_domain_cube:
1237 * Construct and return a dim-dimensional cube, with values ranging
1238 * between min and max in each dimension.
1240 CloogDomain
*cloog_domain_cube(CloogState
*state
,
1241 int dim
, cloog_int_t min
, cloog_int_t max
)
1244 struct isl_basic_set
*cube
;
1245 struct isl_basic_set
*interval
;
1246 struct isl_basic_set_list
*list
;
1249 return cloog_domain_universe(state
, dim
);
1251 interval
= isl_basic_set_interval(state
->backend
->ctx
, min
, max
);
1252 list
= isl_basic_set_list_alloc(state
->backend
->ctx
, dim
);
1253 for (i
= 0; i
< dim
; ++i
)
1254 list
= isl_basic_set_list_add(list
, isl_basic_set_copy(interval
));
1255 isl_basic_set_free(interval
);
1256 cube
= isl_basic_set_product(list
);
1257 return cloog_domain_from_isl_set(isl_set_from_basic_set(cube
));
1262 * cloog_domain_scatter function:
1263 * This function add the scattering (scheduling) informations to a domain.
1265 CloogDomain
*cloog_domain_scatter(CloogDomain
*domain
, CloogScattering
*scatt
)
1267 struct isl_map
*map
;
1269 map
= isl_map_reverse(isl_map_copy(&scatt
->map
));
1270 map
= isl_map_intersect_range(map
, &domain
->set
);
1271 return cloog_domain_from_isl_set(isl_set_from_map(map
));
1274 static int add_domain_from_map(__isl_take isl_map
*map
, void *user
)
1278 CloogDomain
*domain
;
1279 CloogScattering
*scat
;
1280 CloogUnionDomain
**ud
= (CloogUnionDomain
**)user
;
1282 dim
= isl_map_get_dim(map
);
1283 name
= isl_dim_get_tuple_name(dim
, isl_dim_in
);
1284 domain
= cloog_domain_from_isl_set(isl_map_domain(isl_map_copy(map
)));
1285 scat
= cloog_scattering_from_isl_map(map
);
1286 *ud
= cloog_union_domain_add_domain(*ud
, name
, domain
, scat
, NULL
);
1293 * Construct a CloogUnionDomain from an isl_union_map representing
1294 * a global scattering function. The input is a mapping from different
1295 * spaces (different tuple names and possibly different dimensions)
1296 * to a common space. The iteration domains are set to the domains
1297 * in each space. The statement names are set to the names of the
1298 * spaces. The parameter names of the result are set to those of
1299 * the input, but the iterator and scattering dimension names are
1302 CloogUnionDomain
*cloog_union_domain_from_isl_union_map(
1303 __isl_take isl_union_map
*umap
)
1308 CloogUnionDomain
*ud
;
1310 dim
= isl_union_map_get_dim(umap
);
1311 nparam
= isl_dim_size(dim
, isl_dim_param
);
1313 ud
= cloog_union_domain_alloc(nparam
);
1315 for (i
= 0; i
< nparam
; ++i
) {
1316 const char *s
= isl_dim_get_name(dim
, isl_dim_param
, i
);
1317 ud
= cloog_union_domain_set_name(ud
, CLOOG_PARAM
, i
, s
);
1321 if (isl_union_map_foreach_map(umap
, &add_domain_from_map
, &ud
) < 0) {
1322 isl_union_map_free(umap
);
1323 cloog_union_domain_free(ud
);
1327 isl_union_map_free(umap
);
1332 static int add_domain(__isl_take isl_set
*set
, void *user
)
1336 CloogDomain
*domain
;
1337 CloogUnionDomain
**ud
= (CloogUnionDomain
**)user
;
1339 dim
= isl_set_get_dim(set
);
1340 name
= isl_dim_get_tuple_name(dim
, isl_dim_in
);
1341 domain
= cloog_domain_from_isl_set(set
);
1342 *ud
= cloog_union_domain_add_domain(*ud
, name
, domain
, NULL
, NULL
);
1349 * Construct a CloogUnionDomain from an isl_union_set.
1350 * The statement names are set to the names of the
1351 * spaces. The parameter names of the result are set to those of
1352 * the input, but the iterator and scattering dimension names are
1355 CloogUnionDomain
*cloog_union_domain_from_isl_union_set(
1356 __isl_take isl_union_set
*uset
)
1361 CloogUnionDomain
*ud
;
1363 dim
= isl_union_set_get_dim(uset
);
1364 nparam
= isl_dim_size(dim
, isl_dim_param
);
1366 ud
= cloog_union_domain_alloc(nparam
);
1368 for (i
= 0; i
< nparam
; ++i
) {
1369 const char *s
= isl_dim_get_name(dim
, isl_dim_param
, i
);
1370 ud
= cloog_union_domain_set_name(ud
, CLOOG_PARAM
, i
, s
);
1374 if (isl_union_set_foreach_set(uset
, &add_domain
, &ud
) < 0) {
1375 isl_union_set_free(uset
);
1376 cloog_union_domain_free(ud
);
1380 isl_union_set_free(uset
);
1385 /* Computes x, y and g such that g = gcd(a,b) and a*x+b*y = g */
1386 static void Euclid(cloog_int_t a
, cloog_int_t b
,
1387 cloog_int_t
*x
, cloog_int_t
*y
, cloog_int_t
*g
)
1389 cloog_int_t c
, d
, e
, f
, tmp
;
1395 cloog_int_init(tmp
);
1396 cloog_int_abs(c
, a
);
1397 cloog_int_abs(d
, b
);
1398 cloog_int_set_si(e
, 1);
1399 cloog_int_set_si(f
, 0);
1400 while (cloog_int_is_pos(d
)) {
1401 cloog_int_tdiv_q(tmp
, c
, d
);
1402 cloog_int_mul(tmp
, tmp
, f
);
1403 cloog_int_sub(e
, e
, tmp
);
1404 cloog_int_tdiv_q(tmp
, c
, d
);
1405 cloog_int_mul(tmp
, tmp
, d
);
1406 cloog_int_sub(c
, c
, tmp
);
1407 cloog_int_swap(c
, d
);
1408 cloog_int_swap(e
, f
);
1410 cloog_int_set(*g
, c
);
1411 if (cloog_int_is_zero(a
))
1412 cloog_int_set_si(*x
, 0);
1413 else if (cloog_int_is_pos(a
))
1414 cloog_int_set(*x
, e
);
1415 else cloog_int_neg(*x
, e
);
1416 if (cloog_int_is_zero(b
))
1417 cloog_int_set_si(*y
, 0);
1419 cloog_int_mul(tmp
, a
, *x
);
1420 cloog_int_sub(tmp
, c
, tmp
);
1421 cloog_int_divexact(*y
, tmp
, b
);
1427 cloog_int_clear(tmp
);
1430 /* Construct a CloogStride from the given constraint for the given level,
1432 * We first compute the gcd of the coefficients of the existentially
1433 * quantified variables and then remove any common factors it has
1434 * with the coefficient at the given level.
1435 * The result is the value of the stride and if it is not one,
1436 * the it is possible to construct a CloogStride.
1437 * The constraint leading to the stride is stored in the CloogStride
1438 * as well a value (factor) such that the product of this value
1439 * and the coefficient at the given level is equal to -1 modulo the stride.
1441 static CloogStride
*construct_stride(isl_constraint
*c
, int level
)
1444 isl_int v
, m
, gcd
, stride
, factor
;
1453 isl_int_init(factor
);
1454 isl_int_init(stride
);
1456 isl_constraint_get_coefficient(c
, isl_dim_set
, level
- 1, &v
);
1457 sign
= isl_int_sgn(v
);
1460 isl_int_set_si(gcd
, 0);
1461 n
= isl_constraint_dim(c
, isl_dim_div
);
1462 for (i
= 0; i
< n
; ++i
) {
1463 isl_constraint_get_coefficient(c
, isl_dim_div
, i
, &v
);
1464 isl_int_gcd(gcd
, gcd
, v
);
1467 isl_int_gcd(v
, m
, gcd
);
1468 isl_int_divexact(stride
, gcd
, v
);
1470 if (isl_int_is_zero(stride
) || isl_int_is_one(stride
))
1473 Euclid(m
, stride
, &factor
, &v
, &gcd
);
1475 isl_int_neg(factor
, factor
);
1477 c
= isl_constraint_copy(c
);
1478 s
= cloog_stride_alloc_from_constraint(stride
,
1479 cloog_constraint_from_isl_constraint(c
), factor
);
1482 isl_int_clear(stride
);
1483 isl_int_clear(factor
);
1491 struct cloog_isl_find_stride_data
{
1493 CloogStride
*stride
;
1496 /* Check if the given constraint can be used to derive
1497 * a stride on the iterator identified by data->level.
1498 * We first check that there are some existentially quantified variables
1499 * and that the coefficient at data->level is non-zero.
1500 * Then we call construct_stride for further checks and the actual
1501 * construction of the CloogStride.
1503 static int find_stride(__isl_take isl_constraint
*c
, void *user
)
1505 struct cloog_isl_find_stride_data
*data
;
1509 data
= (struct cloog_isl_find_stride_data
*)user
;
1512 isl_constraint_free(c
);
1516 n
= isl_constraint_dim(c
, isl_dim_div
);
1518 isl_constraint_free(c
);
1524 isl_constraint_get_coefficient(c
, isl_dim_set
, data
->level
- 1, &v
);
1525 if (!isl_int_is_zero(v
))
1526 data
->stride
= construct_stride(c
, data
->level
);
1530 isl_constraint_free(c
);
1535 /* Check if the given list of domains has a common stride on the given level.
1536 * If so, return a pointer to a CloogStride object. If not, return NULL.
1538 * We project out all later variables, take the union and compute
1539 * the affine hull of the union. Then we check the (equality)
1540 * constraints in this affine hull for imposing a stride.
1542 CloogStride
*cloog_domain_list_stride(CloogDomainList
*list
, int level
)
1544 struct cloog_isl_find_stride_data data
= { level
, NULL
};
1551 n
= isl_set_dim(&list
->domain
->set
, isl_dim_set
) - first
;
1552 set
= isl_set_project_out(isl_set_copy(&list
->domain
->set
),
1553 isl_dim_set
, first
, n
);
1555 for (list
= list
->next
; list
; list
= list
->next
) {
1557 n
= isl_set_dim(&list
->domain
->set
, isl_dim_set
) - first
;
1558 set_i
= isl_set_project_out(isl_set_copy(&list
->domain
->set
),
1559 isl_dim_set
, first
, n
);
1560 set
= isl_set_union(set
, set_i
);
1562 aff
= isl_set_affine_hull(set
);
1564 r
= isl_basic_set_foreach_constraint(aff
, &find_stride
, &data
);
1567 isl_basic_set_free(aff
);