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 return (CloogDomain
*)set
;
17 CloogScattering
*cloog_scattering_from_isl_map(struct isl_map
*map
)
19 return (CloogScattering
*)map
;
24 * Returns true if each scattering dimension is defined in terms
25 * of the original iterators.
27 int cloog_scattering_fully_specified(CloogScattering
*scattering
,
30 return isl_map_is_single_valued(&scattering
->map
);
34 CloogConstraintSet
*cloog_domain_constraints(CloogDomain
*domain
)
36 assert(domain
->set
.n
== 1);
37 return cloog_constraint_set_from_isl_basic_set(
38 isl_basic_set_copy(domain
->set
.p
[0]));
42 void cloog_domain_print_constraints(FILE *foo
, CloogDomain
*domain
,
46 isl_set_print(&domain
->set
, foo
, 0, ISL_FORMAT_EXT_POLYLIB
);
48 assert(domain
->set
.n
== 1);
49 isl_basic_set_print(domain
->set
.p
[0], foo
,
50 0, NULL
, NULL
, ISL_FORMAT_POLYLIB
);
55 void cloog_scattering_print_constraints(FILE *foo
, CloogScattering
*scattering
,
59 isl_map_print(&scattering
->map
, foo
, 0, ISL_FORMAT_EXT_POLYLIB
);
61 assert(scattering
->map
.n
== 1);
62 isl_basic_map_print(scattering
->map
.p
[0], foo
,
63 0, NULL
, NULL
, ISL_FORMAT_POLYLIB
);
68 void cloog_domain_free(CloogDomain
* domain
)
70 isl_set_free(&domain
->set
);
74 void cloog_scattering_free(CloogScattering
*scatt
)
76 isl_map_free(&scatt
->map
);
80 CloogDomain
* cloog_domain_copy(CloogDomain
* domain
)
82 return cloog_domain_from_isl_set(isl_set_copy(&domain
->set
));
87 * cloog_domain_convex function:
88 * Computes the convex hull of domain.
90 CloogDomain
*cloog_domain_convex(CloogDomain
*domain
)
92 struct isl_set
*set
= &domain
->set
;
93 set
= isl_set_from_basic_set(isl_set_convex_hull(isl_set_copy(set
)));
94 return cloog_domain_from_isl_set(set
);
99 * cloog_domain_simple_convex:
100 * Given a list (union) of polyhedra, this function returns a "simple"
101 * convex hull of this union. In particular, the constraints of the
102 * the returned polyhedron consist of (parametric) lower and upper
103 * bounds on individual variables and constraints that appear in the
104 * original polyhedra.
106 CloogDomain
*cloog_domain_simple_convex(CloogDomain
*domain
)
108 struct isl_basic_set
*hull
;
109 unsigned dim
= isl_set_n_dim(&domain
->set
);
111 if (cloog_domain_isconvex(domain
))
112 return cloog_domain_copy(domain
);
115 return cloog_domain_convex(domain
);
117 hull
= isl_set_bounded_simple_hull(isl_set_copy(&domain
->set
));
118 return cloog_domain_from_isl_set(isl_set_from_basic_set(hull
));
123 * cloog_domain_simplify function:
124 * Given two polyhedral domains (dom1) and (dom2),
125 * this function finds the largest domain set (or the smallest list
126 * of non-redundant constraints), that when intersected with polyhedral
127 * domain (dom2) equals (dom1)intersect(dom2). The output is a new CloogDomain
128 * structure with a polyhedral domain with the "redundant" constraints removed.
129 * NB: the second domain is required not to be a union.
131 CloogDomain
*cloog_domain_simplify(CloogDomain
*dom1
, CloogDomain
*dom2
)
134 set
= isl_set_gist(isl_set_copy(&dom1
->set
), isl_set_copy(&dom2
->set
));
135 return cloog_domain_from_isl_set(set
);
140 * cloog_domain_union function:
141 * This function returns a new polyhedral domain which is the union of
142 * two polyhedral domains (dom1) U (dom2).
143 * Frees dom1 and dom2;
145 CloogDomain
*cloog_domain_union(CloogDomain
*dom1
, CloogDomain
*dom2
)
148 set
= isl_set_union(&dom1
->set
, &dom2
->set
);
149 return cloog_domain_from_isl_set(set
);
155 * cloog_domain_intersection function:
156 * This function returns a new polyhedral domain which is the intersection of
157 * two polyhedral domains (dom1) \cap (dom2).
159 CloogDomain
*cloog_domain_intersection(CloogDomain
*dom1
, CloogDomain
*dom2
)
162 set
= isl_set_intersect(isl_set_copy(&dom1
->set
),
163 isl_set_copy(&dom2
->set
));
164 return cloog_domain_from_isl_set(set
);
169 * cloog_domain_difference function:
170 * Returns the set difference domain \ minus.
172 CloogDomain
*cloog_domain_difference(CloogDomain
*domain
, CloogDomain
*minus
)
175 set
= isl_set_subtract(isl_set_copy(&domain
->set
),
176 isl_set_copy(&minus
->set
));
177 return cloog_domain_from_isl_set(set
);
182 * cloog_domain_sort function:
183 * This function topologically sorts (nb_doms) domains. Here (doms) is an
184 * array of pointers to CloogDomains, (nb_doms) is the number of domains,
185 * (level) is the level to consider for partial ordering (nb_par) is the
186 * parameter space dimension, (permut) if not NULL, is an array of (nb_doms)
187 * integers that contains a permutation specification after call in order to
188 * apply the topological sorting.
190 void cloog_domain_sort(CloogDomain
**doms
, unsigned nb_doms
, unsigned level
,
195 unsigned char **follows
;
199 ctx
= doms
[0]->set
.ctx
;
200 for (i
= 0; i
< nb_doms
; i
++)
201 assert(doms
[i
]->set
.n
== 1);
203 follows
= isl_alloc_array(ctx
, unsigned char *, nb_doms
);
205 for (i
= 0; i
< nb_doms
; ++i
) {
206 follows
[i
] = isl_alloc_array(ctx
, unsigned char, nb_doms
);
208 for (j
= 0; j
< nb_doms
; ++j
)
212 for (i
= 1; i
< nb_doms
; ++i
) {
213 for (j
= 0; j
< i
; ++j
) {
214 if (follows
[i
][j
] || follows
[j
][i
])
216 cmp
= isl_basic_set_compare_at(doms
[i
]->set
.p
[0],
217 doms
[j
]->set
.p
[0], level
-1);
222 for (k
= 0; k
< i
; ++k
)
223 follows
[i
][k
] |= follows
[j
][k
];
226 for (k
= 0; k
< i
; ++k
)
227 follows
[k
][i
] |= follows
[k
][j
];
232 for (i
= 0, j
= 0; i
< nb_doms
; j
= (j
+ 1) % nb_doms
) {
233 for (k
= 0; k
< nb_doms
; ++k
)
238 for (k
= 0; k
< nb_doms
; ++k
)
245 for (i
= 0; i
< nb_doms
; ++i
)
252 * Check whether there is or may be any value of dom1 at the given level
253 * that is greater than or equal to a value of dom2 at the same level.
256 * 1 is there is or may be a greater-than pair.
257 * 0 if there is no greater-than pair, but there may be an equal-to pair
258 * -1 if there is definitely no such pair
260 int cloog_domain_follows(CloogDomain
*dom1
, CloogDomain
*dom2
, unsigned level
)
264 follows
= isl_set_follows_at(&dom1
->set
, &dom2
->set
, level
- 1);
265 assert(follows
>= -1);
272 * cloog_domain_empty function:
273 * Returns an empty domain of the same dimensions as template.
275 CloogDomain
*cloog_domain_empty(CloogDomain
*template)
277 return cloog_domain_from_isl_set(isl_set_empty_like(&template->set
));
282 * Return 1 if the specified dimension has both an upper and a lower bound.
284 int cloog_domain_is_bounded(CloogDomain
*dom
, unsigned level
)
286 return isl_set_dim_is_bounded(&dom
->set
, isl_dim_set
, level
- 1);
290 /******************************************************************************
291 * Structure display function *
292 ******************************************************************************/
296 * cloog_domain_print_structure :
297 * this function is a more human-friendly way to display the CloogDomain data
298 * structure, it only shows the constraint system and includes an indentation
299 * level (level) in order to work with others print_structure functions.
301 void cloog_domain_print_structure(FILE *file
, CloogDomain
*domain
, int level
,
307 struct isl_set
*set
= &domain
->set
;
309 /* Go to the right level. */
310 for (i
= 0; i
< level
; i
++)
311 fprintf(file
, "|\t");
314 fprintf(file
, "+-- Null CloogDomain\n");
317 fprintf(file
, "+-- %s\n", name
);
318 prefix
= isl_alloc_array(set
->ctx
, char, 2*(level
+1)+3);
320 for (i
= 0; i
< level
+1; ++i
)
321 memcpy(prefix
+2*i
, "|\t", 2);
322 strcpy(prefix
+2*(level
+1), "[ ");
324 for (i
= 0; i
< set
->n
; ++i
) {
325 isl_basic_set_print(set
->p
[i
], file
, 0, prefix
, suffix
,
326 ISL_FORMAT_POLYLIB_CONSTRAINTS
);
327 prefix
[2*(level
+1)] = '\0';
328 fprintf(file
, "%s\n", prefix
);
329 prefix
[2*(level
+1)] = '[';
335 /******************************************************************************
336 * Memory deallocation function *
337 ******************************************************************************/
340 void cloog_domain_list_free(CloogDomainList
*list
)
342 CloogDomainList
*next
;
344 for ( ; list
; list
= next
) {
346 cloog_domain_free(list
->domain
);
353 * cloog_scattering_list_free function:
354 * This function frees the allocated memory for a CloogScatteringList structure.
356 void cloog_scattering_list_free(CloogScatteringList
*list
)
358 while (list
!= NULL
) {
359 CloogScatteringList
*temp
= list
->next
;
360 isl_map_free(&list
->scatt
->map
);
367 /******************************************************************************
369 ******************************************************************************/
373 * cloog_domain_read_context function:
374 * Read parameter domain.
376 CloogDomain
*cloog_domain_read_context(CloogState
*state
, FILE *input
)
378 struct isl_ctx
*ctx
= state
->backend
->ctx
;
381 set
= isl_set_read_from_file(ctx
, input
, 0);
382 set
= isl_set_move_dims(set
, isl_dim_param
, 0,
383 isl_dim_set
, 0, isl_set_dim(set
, isl_dim_set
));
385 return cloog_domain_from_isl_set(set
);
390 * cloog_domain_from_context
391 * Reinterpret context by turning parameters into variables.
393 CloogDomain
*cloog_domain_from_context(CloogDomain
*context
)
395 isl_set
*set
= &context
->set
;
397 set
= isl_set_move_dims(set
, isl_dim_set
, 0,
398 isl_dim_param
, 0, isl_set_dim(set
, isl_dim_param
));
400 return cloog_domain_from_isl_set(set
);
405 * cloog_domain_union_read function:
406 * This function reads a union of polyhedra into a file (input) and
407 * returns a pointer to a CloogDomain containing the read information.
409 CloogDomain
*cloog_domain_union_read(CloogState
*state
,
410 FILE *input
, int nb_parameters
)
412 struct isl_ctx
*ctx
= state
->backend
->ctx
;
415 set
= isl_set_read_from_file(ctx
, input
, nb_parameters
);
416 return cloog_domain_from_isl_set(set
);
421 * cloog_domain_read_scattering function:
422 * This function reads in a scattering function from the file input.
424 * We try to read the scattering relation as a map, but if it is
425 * specified in the original PolyLib format, then isl_map_read_from_file
426 * will treat the input as a set return a map with zero input dimensions.
427 * In this case, we need to decompose the set into a map from
428 * scattering dimensions to domain dimensions and then invert the
431 CloogScattering
*cloog_domain_read_scattering(CloogDomain
*domain
, FILE *input
)
433 struct isl_ctx
*ctx
= domain
->set
.ctx
;
434 struct isl_map
*scat
;
439 dim
= isl_set_n_dim(&domain
->set
);
440 nparam
= isl_set_n_param(&domain
->set
);
441 scat
= isl_map_read_from_file(ctx
, input
, nparam
);
442 if (isl_map_dim(scat
, isl_dim_in
) != dim
) {
443 n_scat
= isl_map_dim(scat
, isl_dim_out
) - dim
;
444 scat
= isl_map_move_dims(scat
, isl_dim_in
, 0,
445 isl_dim_out
, n_scat
, dim
);
447 return cloog_scattering_from_isl_map(scat
);
450 /******************************************************************************
451 * CloogMatrix Reading function *
452 ******************************************************************************/
455 * isl_constraint_read_from_matrix:
456 * Convert a single line of a matrix to a isl_constraint.
457 * Returns a pointer to the constraint if successful; NULL otherwise.
459 static struct isl_constraint
*isl_constraint_read_from_matrix(
460 struct isl_dim
*dim
, cloog_int_t
*row
)
462 struct isl_constraint
*constraint
;
464 int nvariables
= isl_dim_size(dim
, isl_dim_set
);
465 int nparam
= isl_dim_size(dim
, isl_dim_param
);
467 if (cloog_int_is_zero(row
[0]))
468 constraint
= isl_equality_alloc(dim
);
470 constraint
= isl_inequality_alloc(dim
);
472 for (j
= 0; j
< nvariables
; ++j
)
473 isl_constraint_set_coefficient(constraint
, isl_dim_out
, j
,
476 for (j
= 0; j
< nparam
; ++j
)
477 isl_constraint_set_coefficient(constraint
, isl_dim_param
, j
,
478 row
[1 + nvariables
+ j
]);
480 isl_constraint_set_constant(constraint
, row
[1 + nvariables
+ nparam
]);
486 * isl_basic_set_read_from_matrix:
487 * Convert matrix to basic_set. The matrix contains nparam parameter columns.
488 * Returns a pointer to the basic_set if successful; NULL otherwise.
490 static struct isl_basic_set
*isl_basic_set_read_from_matrix(struct isl_ctx
*ctx
,
491 CloogMatrix
* matrix
, int nparam
)
494 struct isl_basic_set
*bset
;
496 unsigned nrows
, ncolumns
;
498 nrows
= matrix
->NbRows
;
499 ncolumns
= matrix
->NbColumns
;
500 int nvariables
= ncolumns
- 2 - nparam
;
502 dim
= isl_dim_set_alloc(ctx
, nparam
, nvariables
);
504 bset
= isl_basic_set_universe(isl_dim_copy(dim
));
506 for (i
= 0; i
< nrows
; ++i
) {
507 cloog_int_t
*row
= matrix
->p
[i
];
508 struct isl_constraint
*constraint
=
509 isl_constraint_read_from_matrix(isl_dim_copy(dim
), row
);
510 bset
= isl_basic_set_add_constraint(bset
, constraint
);
519 * cloog_domain_from_cloog_matrix:
520 * Create a CloogDomain containing the constraints described in matrix.
521 * nparam is the number of parameters contained in the domain.
522 * Returns a pointer to the CloogDomain if successful; NULL otherwise.
524 CloogDomain
*cloog_domain_from_cloog_matrix(CloogState
*state
,
525 CloogMatrix
*matrix
, int nparam
)
527 struct isl_ctx
*ctx
= state
->backend
->ctx
;
528 struct isl_basic_set
*bset
;
530 bset
= isl_basic_set_read_from_matrix(ctx
, matrix
, nparam
);
532 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset
));
536 * cloog_scattering_from_cloog_matrix:
537 * Create a CloogScattering containing the constraints described in matrix.
538 * nparam is the number of parameters contained in the domain.
539 * Returns a pointer to the CloogScattering if successful; NULL otherwise.
541 CloogScattering
*cloog_scattering_from_cloog_matrix(CloogState
*state
,
542 CloogMatrix
*matrix
, int nb_scat
, int nb_par
)
544 struct isl_ctx
*ctx
= state
->backend
->ctx
;
545 struct isl_basic_set
*bset
;
546 struct isl_basic_map
*scat
;
547 struct isl_dim
*dims
;
550 bset
= isl_basic_set_read_from_matrix(ctx
, matrix
, nb_par
);
551 dim
= isl_basic_set_n_dim(bset
) - nb_scat
;
552 dims
= isl_dim_alloc(ctx
, nb_par
, nb_scat
, dim
);
554 scat
= isl_basic_map_from_basic_set(bset
, dims
);
555 scat
= isl_basic_map_reverse(scat
);
556 return cloog_scattering_from_isl_map(isl_map_from_basic_map(scat
));
560 /******************************************************************************
561 * Processing functions *
562 ******************************************************************************/
567 * cloog_domain_isempty function:
569 int cloog_domain_isempty(CloogDomain
*domain
)
571 return isl_set_is_empty(&domain
->set
);
576 * cloog_domain_universe function:
577 * This function returns the complete dim-dimensional space.
579 CloogDomain
*cloog_domain_universe(CloogState
*state
, unsigned dim
)
581 struct isl_dim
*dims
;
582 struct isl_basic_set
*bset
;
584 dims
= isl_dim_set_alloc(state
->backend
->ctx
, 0, dim
);
585 bset
= isl_basic_set_universe(dims
);
586 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset
));
591 * cloog_domain_project function:
592 * This function returns the projection of
593 * (domain) on the (level) first dimensions (i.e. outer loops).
595 CloogDomain
*cloog_domain_project(CloogDomain
*domain
, int level
)
597 struct isl_set
*set
= &domain
->set
;
598 set
= isl_set_remove_dims(isl_set_copy(set
), isl_dim_set
,
599 level
, isl_set_n_dim(set
) - level
);
600 set
= isl_set_compute_divs(set
);
601 return cloog_domain_from_isl_set(set
);
606 * cloog_domain_extend function:
607 * This function returns the (domain) given as input with (dim)
608 * dimensions and (nb_par) parameters.
609 * This function does not free (domain), and returns a new CloogDomain.
611 CloogDomain
*cloog_domain_extend(CloogDomain
*domain
, int dim
)
613 struct isl_set
*set
= &domain
->set
;
614 set
= isl_set_extend(isl_set_copy(set
), isl_set_n_param(set
), dim
);
615 return cloog_domain_from_isl_set(set
);
620 * cloog_domain_never_integral function:
621 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0.
622 * There is no need to check for such constraints explicitly for the isl
625 int cloog_domain_never_integral(CloogDomain
* domain
)
627 return isl_set_is_empty(&domain
->set
);
632 * Check whether the loop at "level" is executed at most once.
633 * We construct a map that maps all remaining variables to this iterator
634 * and check whether this map is single valued.
636 * Alternatively, we could have mapped the domain through a mapping
637 * [p] -> { [..., i] -> [..., i'] : i' > i }
638 * and then taken the intersection of the original domain and the transformed
639 * domain. If this intersection is empty, then the corresponding
640 * loop is executed at most once.
642 int cloog_domain_is_otl(CloogDomain
*domain
, int level
)
647 map
= isl_map_from_domain(isl_set_copy(&domain
->set
));
648 map
= isl_map_move_dims(map
, isl_dim_out
, 0, isl_dim_in
, level
- 1, 1);
649 otl
= isl_map_is_single_valued(map
);
657 * cloog_domain_stride function:
658 * This function finds the stride imposed to unknown with the column number
659 * 'strided_level' in order to be integral. For instance, if we have a
660 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
661 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
662 * the unknown i. The function returns the imposed stride in a parameter field.
663 * - domain is the set of constraint we have to consider,
664 * - strided_level is the column number of the unknown for which a stride have
666 * - looking_level is the column number of the unknown that impose a stride to
668 * - stride is the stride that is returned back as a function parameter.
669 * - offset is the value of the constant c if the condition is of the shape
670 * (i + c)%s = 0, s being the stride.
672 void cloog_domain_stride(CloogDomain
*domain
, int strided_level
,
673 cloog_int_t
*stride
, cloog_int_t
*offset
)
675 struct isl_set
*set
= &domain
->set
;
676 isl_set_dim_residue_class(set
, strided_level
- 1, stride
, offset
);
677 if (!isl_int_is_zero(*offset
))
678 isl_int_sub(*offset
, *stride
, *offset
);
683 struct cloog_can_stride
{
688 static int constraint_can_stride(__isl_take isl_constraint
*c
, void *user
)
690 struct cloog_can_stride
*ccs
= (struct cloog_can_stride
*)user
;
696 isl_constraint_get_coefficient(c
, isl_dim_set
, ccs
->level
- 1, &v
);
697 if (isl_int_is_pos(v
)) {
698 n_div
= isl_constraint_dim(c
, isl_dim_div
);
699 for (i
= 0; i
< n_div
; ++i
) {
700 isl_constraint_get_coefficient(c
, isl_dim_div
, i
, &v
);
701 if (!isl_int_is_zero(v
))
708 isl_constraint_free(c
);
713 static int basic_set_can_stride(__isl_take isl_basic_set
*bset
, void *user
)
715 struct cloog_can_stride
*ccs
= (struct cloog_can_stride
*)user
;
718 r
= isl_basic_set_foreach_constraint(bset
, constraint_can_stride
, ccs
);
719 isl_basic_set_free(bset
);
725 * Return 1 if CLooG is allowed to perform stride detection on level "level"
727 * Currently, stride detection is only allowed when none of the lower
728 * bound constraints involve any existentially quantified variables.
729 * The reason is that the current isl interface does not make it
730 * easy to construct an integer division that depends on other integer
732 * By not allowing existentially quantified variables in the constraints,
733 * we can ignore them in cloog_domain_stride_lower_bound.
735 int cloog_domain_can_stride(CloogDomain
*domain
, int level
)
737 struct cloog_can_stride ccs
= { level
, 1 };
739 r
= isl_set_foreach_basic_set(&domain
->set
, basic_set_can_stride
, &ccs
);
741 return ccs
.can_stride
;
745 struct cloog_stride_lower
{
749 isl_basic_set
*bounds
;
752 /* If the given constraint is a lower bound on csl->level, then add
753 * a lower bound to csl->bounds that makes sure that the remainder
754 * of the smallest value on division by csl->stride is equal to csl->offset.
756 * In particular, the given lower bound is of the form
760 * where f may depend on the parameters and other iterators.
761 * The stride is s and the offset is d.
762 * The lower bound -f/a may not satisfy the above condition. In fact,
763 * it may not even be integral. We want to round this value of i up
764 * to the nearest value that satisfies the condition and add the corresponding
765 * lower bound constraint. This nearest value is obtained by rounding
766 * i - d up to the nearest multiple of s.
767 * That is, we first subtract d
771 * then we round up to the nearest multiple of s
773 * i'' = s * ceil(i'/s)
775 * and finally, we add d again
779 * and impose the constraint i >= i'''.
783 * i'' = s * ceil((-f - a * d)/(a * s)) = - s * floor((f + a * d)/(a * s))
785 * i >= - s * floor((f + a * d)/(a * s)) + d
788 * i + s * floor((f + a * d)/(a * s)) - d >= 0
790 static int constraint_stride_lower(__isl_take isl_constraint
*c
, void *user
)
792 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
796 isl_constraint
*bound
;
799 unsigned nparam
, nvar
;
802 isl_constraint_get_coefficient(c
, isl_dim_set
, csl
->level
- 1, &v
);
803 if (!isl_int_is_pos(v
)) {
805 isl_constraint_free(c
);
812 nparam
= isl_constraint_dim(c
, isl_dim_param
);
813 nvar
= isl_constraint_dim(c
, isl_dim_set
);
814 bound
= isl_inequality_alloc(isl_basic_set_get_dim(csl
->bounds
));
815 div
= isl_div_alloc(isl_basic_set_get_dim(csl
->bounds
));
816 isl_int_mul(t
, v
, csl
->stride
->stride
);
817 isl_div_set_denominator(div
, t
);
818 for (i
= 0; i
< nparam
; ++i
) {
819 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &t
);
820 isl_div_set_coefficient(div
, isl_dim_param
, i
, t
);
822 for (i
= 0; i
< nvar
; ++i
) {
823 if (i
== csl
->level
- 1)
825 isl_constraint_get_coefficient(c
, isl_dim_set
, i
, &t
);
826 isl_div_set_coefficient(div
, isl_dim_set
, i
, t
);
828 isl_constraint_get_constant(c
, &t
);
829 isl_int_addmul(t
, v
, csl
->stride
->offset
);
830 isl_div_set_constant(div
, t
);
832 bound
= isl_constraint_add_div(bound
, div
, &pos
);
833 isl_int_set_si(t
, 1);
834 isl_constraint_set_coefficient(bound
, isl_dim_set
,
836 isl_constraint_set_coefficient(bound
, isl_dim_div
, pos
,
837 csl
->stride
->stride
);
838 isl_int_neg(t
, csl
->stride
->offset
);
839 isl_constraint_set_constant(bound
, t
);
840 csl
->bounds
= isl_basic_set_add_constraint(csl
->bounds
, bound
);
844 isl_constraint_free(c
);
849 /* This functions performs essentially the same operation as
850 * constraint_stride_lower, the only difference being that the offset d
851 * is not a constant, but an affine expression in terms of the parameters
852 * and earlier variables. In particular the affine expression is equal
853 * to the coefficients of stride->constraint multiplied by stride->factor.
854 * As in constraint_stride_lower, we add an extra bound
856 * i + s * floor((f + a * d)/(a * s)) - d >= 0
858 * for each lower bound
862 * where d is not the aforementioned affine expression.
864 static int constraint_stride_lower_c(__isl_take isl_constraint
*c
, void *user
)
866 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
870 isl_constraint
*bound
;
871 isl_constraint
*csl_c
;
874 unsigned nparam
, nvar
;
877 isl_constraint_get_coefficient(c
, isl_dim_set
, csl
->level
- 1, &v
);
878 if (!isl_int_is_pos(v
)) {
880 isl_constraint_free(c
);
885 csl_c
= &csl
->stride
->constraint
->isl
;
890 nparam
= isl_constraint_dim(c
, isl_dim_param
);
891 nvar
= isl_constraint_dim(c
, isl_dim_set
);
892 bound
= isl_inequality_alloc(isl_basic_set_get_dim(csl
->bounds
));
893 div
= isl_div_alloc(isl_basic_set_get_dim(csl
->bounds
));
894 isl_int_mul(t
, v
, csl
->stride
->stride
);
895 isl_div_set_denominator(div
, t
);
896 for (i
= 0; i
< nparam
; ++i
) {
897 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &t
);
898 isl_constraint_get_coefficient(csl_c
, isl_dim_param
, i
, &u
);
899 isl_int_mul(u
, u
, csl
->stride
->factor
);
900 isl_int_addmul(t
, v
, u
);
901 isl_div_set_coefficient(div
, isl_dim_param
, i
, t
);
903 isl_constraint_set_coefficient(bound
, isl_dim_param
, i
, u
);
905 for (i
= 0; i
< nvar
; ++i
) {
906 if (i
== csl
->level
- 1)
908 isl_constraint_get_coefficient(c
, isl_dim_set
, i
, &t
);
909 isl_constraint_get_coefficient(csl_c
, isl_dim_set
, i
, &u
);
910 isl_int_mul(u
, u
, csl
->stride
->factor
);
911 isl_int_addmul(t
, v
, u
);
912 isl_div_set_coefficient(div
, isl_dim_set
, i
, t
);
914 isl_constraint_set_coefficient(bound
, isl_dim_set
, i
, u
);
916 isl_constraint_get_constant(c
, &t
);
917 isl_constraint_get_constant(csl_c
, &u
);
918 isl_int_mul(u
, u
, csl
->stride
->factor
);
919 isl_int_addmul(t
, v
, u
);
920 isl_div_set_constant(div
, t
);
922 isl_constraint_set_constant(bound
, u
);
924 bound
= isl_constraint_add_div(bound
, div
, &pos
);
925 isl_int_set_si(t
, 1);
926 isl_constraint_set_coefficient(bound
, isl_dim_set
,
928 isl_constraint_set_coefficient(bound
, isl_dim_div
, pos
,
929 csl
->stride
->stride
);
930 csl
->bounds
= isl_basic_set_add_constraint(csl
->bounds
, bound
);
935 isl_constraint_free(c
);
940 static int basic_set_stride_lower(__isl_take isl_basic_set
*bset
, void *user
)
942 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
945 csl
->bounds
= isl_basic_set_universe_like(bset
);
946 if (csl
->stride
->constraint
)
947 r
= isl_basic_set_foreach_constraint(bset
,
948 &constraint_stride_lower_c
, csl
);
950 r
= isl_basic_set_foreach_constraint(bset
,
951 &constraint_stride_lower
, csl
);
952 bset
= isl_basic_set_intersect(bset
, csl
->bounds
);
953 csl
->set
= isl_set_union(csl
->set
, isl_set_from_basic_set(bset
));
959 * Update the lower bounds at level "level" to the given stride information.
960 * That is, make sure that the remainder on division by "stride"
961 * is equal to "offset".
963 CloogDomain
*cloog_domain_stride_lower_bound(CloogDomain
*domain
, int level
,
966 struct cloog_stride_lower csl
;
971 csl
.set
= isl_set_empty_like(&domain
->set
);
973 r
= isl_set_foreach_basic_set(&domain
->set
, basic_set_stride_lower
, &csl
);
976 cloog_domain_free(domain
);
977 return cloog_domain_from_isl_set(csl
.set
);
982 * cloog_domain_lazy_equal function:
983 * This function returns 1 if the domains given as input are the same, 0 if it
984 * is unable to decide.
986 int cloog_domain_lazy_equal(CloogDomain
*d1
, CloogDomain
*d2
)
988 return isl_set_fast_is_equal(&d1
->set
, &d2
->set
);
991 struct cloog_bound_split
{
998 static int constraint_bound_split(__isl_take isl_constraint
*c
, void *user
)
1000 struct cloog_bound_split
*cbs
= (struct cloog_bound_split
*)user
;
1006 isl_constraint_get_coefficient(c
, isl_dim_set
, cbs
->level
- 1, &v
);
1007 if (!cbs
->lower
&& isl_int_is_pos(v
))
1008 cbs
->lower
= handle
= 1;
1009 else if (!cbs
->upper
&& isl_int_is_neg(v
))
1010 cbs
->upper
= handle
= 1;
1012 for (i
= 0; i
< isl_set_dim(cbs
->set
, isl_dim_param
); ++i
) {
1013 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &v
);
1014 if (isl_int_is_zero(v
))
1016 cbs
->set
= isl_set_split_dims(cbs
->set
,
1017 isl_dim_param
, i
, 1);
1021 isl_constraint_free(c
);
1023 return (cbs
->lower
&& cbs
->upper
) ? -1 : 0;
1026 static int basic_set_bound_split(__isl_take isl_basic_set
*bset
, void *user
)
1028 struct cloog_bound_split
*cbs
= (struct cloog_bound_split
*)user
;
1033 r
= isl_basic_set_foreach_constraint(bset
, constraint_bound_split
, cbs
);
1034 isl_basic_set_free(bset
);
1035 return ((!cbs
->lower
|| !cbs
->upper
) && r
< 0) ? -1 : 0;
1039 * Return a union of sets S_i such that the convex hull of "dom",
1040 * when intersected with one the sets S_i, will have an upper and
1041 * lower bound for the dimension at "level" (provided "dom" itself
1042 * has such bounds for the dimensions).
1044 * We currently take a very simple approach. For each of the basic
1045 * sets in "dom" we pick a lower and an upper bound and split the
1046 * range of any parameter involved in these two bounds in a
1047 * nonnegative and a negative part. This ensures that the symbolic
1048 * constant in these two constraints are themselves bounded and
1049 * so there will be at least one upper and one lower bound
1050 * in the convex hull.
1052 CloogDomain
*cloog_domain_bound_splitter(CloogDomain
*dom
, int level
)
1054 struct cloog_bound_split cbs
;
1057 cbs
.set
= isl_set_universe_like(&dom
->set
);
1058 r
= isl_set_foreach_basic_set(&dom
->set
, basic_set_bound_split
, &cbs
);
1060 return cloog_domain_from_isl_set(cbs
.set
);
1065 * cloog_scattering_lazy_block function:
1066 * This function returns 1 if the two scattering functions s1 and s2 given
1067 * as input are the same (except possibly for the final dimension, where we
1068 * allow a difference of 1), assuming that the domains on which this
1069 * scatterings are applied are the same.
1070 * In fact this function answers the question "can I
1071 * safely consider the two domains as only one with two statements (a block) ?".
1072 * - s1 and s2 are the two domains to check for blocking,
1073 * - scattering is the linked list of all domains,
1074 * - scattdims is the total number of scattering dimentions.
1076 int cloog_scattering_lazy_block(CloogScattering
*s1
, CloogScattering
*s2
,
1077 CloogScatteringList
*scattering
, int scattdims
)
1080 struct isl_dim
*dim
;
1081 struct isl_map
*rel
;
1082 struct isl_set
*delta
;
1087 n_scat
= isl_map_dim(&s1
->map
, isl_dim_out
);
1088 if (n_scat
!= isl_map_dim(&s2
->map
, isl_dim_out
))
1091 dim
= isl_dim_copy(s1
->map
.dim
);
1092 dim
= isl_dim_domain(dim
);
1093 rel
= isl_map_identity(dim
);
1094 rel
= isl_map_apply_domain(rel
, isl_map_copy(&s1
->map
));
1095 rel
= isl_map_apply_range(rel
, isl_map_copy(&s2
->map
));
1096 delta
= isl_map_deltas(rel
);
1098 for (i
= 0; i
< n_scat
; ++i
) {
1099 fixed
= isl_set_fast_dim_is_fixed(delta
, i
, &cst
);
1102 if (i
+1 < n_scat
&& !isl_int_is_zero(cst
))
1104 if (!isl_int_is_zero(cst
) && !isl_int_is_one(cst
))
1107 block
= i
>= n_scat
;
1109 isl_set_free(delta
);
1115 * cloog_domain_lazy_disjoint function:
1116 * This function returns 1 if the domains given as input are disjoint, 0 if it
1117 * is unable to decide.
1119 int cloog_domain_lazy_disjoint(CloogDomain
*d1
, CloogDomain
*d2
)
1121 return isl_set_fast_is_disjoint(&d1
->set
, &d2
->set
);
1126 * cloog_scattering_list_lazy_same function:
1127 * This function returns 1 if two domains in the list are the same, 0 if it
1128 * is unable to decide.
1130 int cloog_scattering_list_lazy_same(CloogScatteringList
*list
)
1132 CloogScatteringList
*one
, *other
;
1134 for (one
= list
; one
; one
= one
->next
)
1135 for (other
= one
->next
; other
; other
= other
->next
)
1136 if (isl_map_fast_is_equal(&one
->scatt
->map
,
1137 &other
->scatt
->map
))
1142 int cloog_domain_dimension(CloogDomain
* domain
)
1144 return isl_set_n_dim(&domain
->set
);
1147 int cloog_domain_parameter_dimension(CloogDomain
*domain
)
1149 return isl_set_n_param(&domain
->set
);
1152 int cloog_scattering_dimension(CloogScattering
*scatt
, CloogDomain
*domain
)
1154 return isl_map_dim(&scatt
->map
, isl_dim_out
);
1157 int cloog_domain_isconvex(CloogDomain
* domain
)
1159 return domain
->set
.n
<= 1;
1164 * cloog_domain_cut_first function:
1165 * This function splits off and returns the first convex set in the
1166 * union "domain". The remainder of the union is returned in rest.
1167 * The original "domain" itself is destroyed and may not be used
1168 * after a call to this function.
1170 CloogDomain
*cloog_domain_cut_first(CloogDomain
*domain
, CloogDomain
**rest
)
1172 struct isl_set
*set
;
1173 struct isl_basic_set
*first
;
1176 first
= isl_set_copy_basic_set(set
);
1177 set
= isl_set_drop_basic_set(set
, first
);
1178 *rest
= cloog_domain_from_isl_set(set
);
1180 return cloog_domain_from_isl_set(isl_set_from_basic_set(first
));
1185 * Given a union domain, try to find a simpler representation
1186 * using fewer sets in the union.
1187 * The original "domain" itself is destroyed and may not be used
1188 * after a call to this function.
1190 CloogDomain
*cloog_domain_simplify_union(CloogDomain
*domain
)
1192 return cloog_domain_from_isl_set(isl_set_coalesce(&domain
->set
));
1197 * cloog_scattering_lazy_isscalar function:
1198 * this function returns 1 if the scattering dimension 'dimension' in the
1199 * scattering 'scatt' is constant.
1200 * If value is not NULL, then it is set to the constant value of dimension.
1202 int cloog_scattering_lazy_isscalar(CloogScattering
*scatt
, int dimension
,
1205 return isl_map_fast_is_fixed(&scatt
->map
, isl_dim_out
, dimension
, value
);
1210 * cloog_domain_lazy_isconstant function:
1211 * this function returns 1 if the dimension 'dimension' in the
1212 * domain 'domain' is constant.
1213 * If value is not NULL, then it is set to the constant value of dimension.
1215 int cloog_domain_lazy_isconstant(CloogDomain
*domain
, int dimension
)
1217 return isl_set_fast_dim_is_fixed(&domain
->set
, dimension
, NULL
);
1222 * cloog_scattering_erase_dimension function:
1223 * this function returns a CloogDomain structure builds from 'domain' where
1224 * we removed the dimension 'dimension' and every constraint involving this
1227 CloogScattering
*cloog_scattering_erase_dimension(CloogScattering
*domain
,
1230 struct isl_map
*map
;
1231 map
= isl_map_remove_dims(isl_map_copy(&domain
->map
),
1232 isl_dim_out
, dimension
, 1);
1233 return cloog_scattering_from_isl_map(map
);
1237 * cloog_domain_cube:
1238 * Construct and return a dim-dimensional cube, with values ranging
1239 * between min and max in each dimension.
1241 CloogDomain
*cloog_domain_cube(CloogState
*state
,
1242 int dim
, cloog_int_t min
, cloog_int_t max
)
1245 struct isl_basic_set
*cube
;
1246 struct isl_basic_set
*interval
;
1247 struct isl_basic_set_list
*list
;
1250 return cloog_domain_universe(state
, dim
);
1252 interval
= isl_basic_set_interval(state
->backend
->ctx
, min
, max
);
1253 list
= isl_basic_set_list_alloc(state
->backend
->ctx
, dim
);
1254 for (i
= 0; i
< dim
; ++i
)
1255 list
= isl_basic_set_list_add(list
, isl_basic_set_copy(interval
));
1256 isl_basic_set_free(interval
);
1257 cube
= isl_basic_set_product(list
);
1258 return cloog_domain_from_isl_set(isl_set_from_basic_set(cube
));
1263 * cloog_domain_scatter function:
1264 * This function add the scattering (scheduling) informations to a domain.
1266 CloogDomain
*cloog_domain_scatter(CloogDomain
*domain
, CloogScattering
*scatt
)
1268 struct isl_map
*map
;
1270 map
= isl_map_reverse(isl_map_copy(&scatt
->map
));
1271 map
= isl_map_intersect_range(map
, &domain
->set
);
1272 return cloog_domain_from_isl_set(isl_set_from_map(map
));
1275 static int add_domain_from_map(__isl_take isl_map
*map
, void *user
)
1279 CloogDomain
*domain
;
1280 CloogScattering
*scat
;
1281 CloogUnionDomain
**ud
= (CloogUnionDomain
**)user
;
1283 dim
= isl_map_get_dim(map
);
1284 name
= isl_dim_get_tuple_name(dim
, isl_dim_in
);
1285 domain
= cloog_domain_from_isl_set(isl_map_domain(isl_map_copy(map
)));
1286 scat
= cloog_scattering_from_isl_map(map
);
1287 *ud
= cloog_union_domain_add_domain(*ud
, name
, domain
, scat
, NULL
);
1294 * Construct a CloogUnionDomain from an isl_union_map representing
1295 * a global scattering function. The input is a mapping from different
1296 * spaces (different tuple names and possibly different dimensions)
1297 * to a common space. The iteration domains are set to the domains
1298 * in each space. The statement names are set to the names of the
1299 * spaces. The parameter names of the result are set to those of
1300 * the input, but the iterator and scattering dimension names are
1303 CloogUnionDomain
*cloog_union_domain_from_isl_union_map(
1304 __isl_take isl_union_map
*umap
)
1309 CloogUnionDomain
*ud
;
1311 dim
= isl_union_map_get_dim(umap
);
1312 nparam
= isl_dim_size(dim
, isl_dim_param
);
1314 ud
= cloog_union_domain_alloc(nparam
);
1316 for (i
= 0; i
< nparam
; ++i
) {
1317 const char *s
= isl_dim_get_name(dim
, isl_dim_param
, i
);
1318 ud
= cloog_union_domain_set_name(ud
, CLOOG_PARAM
, i
, s
);
1322 if (isl_union_map_foreach_map(umap
, &add_domain_from_map
, &ud
) < 0) {
1323 isl_union_map_free(umap
);
1324 cloog_union_domain_free(ud
);
1328 isl_union_map_free(umap
);
1333 static int add_domain(__isl_take isl_set
*set
, void *user
)
1337 CloogDomain
*domain
;
1338 CloogUnionDomain
**ud
= (CloogUnionDomain
**)user
;
1340 dim
= isl_set_get_dim(set
);
1341 name
= isl_dim_get_tuple_name(dim
, isl_dim_in
);
1342 domain
= cloog_domain_from_isl_set(set
);
1343 *ud
= cloog_union_domain_add_domain(*ud
, name
, domain
, NULL
, NULL
);
1350 * Construct a CloogUnionDomain from an isl_union_set.
1351 * The statement names are set to the names of the
1352 * spaces. The parameter names of the result are set to those of
1353 * the input, but the iterator and scattering dimension names are
1356 CloogUnionDomain
*cloog_union_domain_from_isl_union_set(
1357 __isl_take isl_union_set
*uset
)
1362 CloogUnionDomain
*ud
;
1364 dim
= isl_union_set_get_dim(uset
);
1365 nparam
= isl_dim_size(dim
, isl_dim_param
);
1367 ud
= cloog_union_domain_alloc(nparam
);
1369 for (i
= 0; i
< nparam
; ++i
) {
1370 const char *s
= isl_dim_get_name(dim
, isl_dim_param
, i
);
1371 ud
= cloog_union_domain_set_name(ud
, CLOOG_PARAM
, i
, s
);
1375 if (isl_union_set_foreach_set(uset
, &add_domain
, &ud
) < 0) {
1376 isl_union_set_free(uset
);
1377 cloog_union_domain_free(ud
);
1381 isl_union_set_free(uset
);
1386 /* Computes x, y and g such that g = gcd(a,b) and a*x+b*y = g */
1387 static void Euclid(cloog_int_t a
, cloog_int_t b
,
1388 cloog_int_t
*x
, cloog_int_t
*y
, cloog_int_t
*g
)
1390 cloog_int_t c
, d
, e
, f
, tmp
;
1396 cloog_int_init(tmp
);
1397 cloog_int_abs(c
, a
);
1398 cloog_int_abs(d
, b
);
1399 cloog_int_set_si(e
, 1);
1400 cloog_int_set_si(f
, 0);
1401 while (cloog_int_is_pos(d
)) {
1402 cloog_int_tdiv_q(tmp
, c
, d
);
1403 cloog_int_mul(tmp
, tmp
, f
);
1404 cloog_int_sub(e
, e
, tmp
);
1405 cloog_int_tdiv_q(tmp
, c
, d
);
1406 cloog_int_mul(tmp
, tmp
, d
);
1407 cloog_int_sub(c
, c
, tmp
);
1408 cloog_int_swap(c
, d
);
1409 cloog_int_swap(e
, f
);
1411 cloog_int_set(*g
, c
);
1412 if (cloog_int_is_zero(a
))
1413 cloog_int_set_si(*x
, 0);
1414 else if (cloog_int_is_pos(a
))
1415 cloog_int_set(*x
, e
);
1416 else cloog_int_neg(*x
, e
);
1417 if (cloog_int_is_zero(b
))
1418 cloog_int_set_si(*y
, 0);
1420 cloog_int_mul(tmp
, a
, *x
);
1421 cloog_int_sub(tmp
, c
, tmp
);
1422 cloog_int_divexact(*y
, tmp
, b
);
1428 cloog_int_clear(tmp
);
1431 /* Construct a CloogStride from the given constraint for the given level,
1433 * We first compute the gcd of the coefficients of the existentially
1434 * quantified variables and then remove any common factors it has
1435 * with the coefficient at the given level.
1436 * The result is the value of the stride and if it is not one,
1437 * the it is possible to construct a CloogStride.
1438 * The constraint leading to the stride is stored in the CloogStride
1439 * as well a value (factor) such that the product of this value
1440 * and the coefficient at the given level is equal to -1 modulo the stride.
1442 static CloogStride
*construct_stride(isl_constraint
*c
, int level
)
1445 isl_int v
, m
, gcd
, stride
, factor
;
1454 isl_int_init(factor
);
1455 isl_int_init(stride
);
1457 isl_constraint_get_coefficient(c
, isl_dim_set
, level
- 1, &v
);
1458 sign
= isl_int_sgn(v
);
1461 isl_int_set_si(gcd
, 0);
1462 n
= isl_constraint_dim(c
, isl_dim_div
);
1463 for (i
= 0; i
< n
; ++i
) {
1464 isl_constraint_get_coefficient(c
, isl_dim_div
, i
, &v
);
1465 isl_int_gcd(gcd
, gcd
, v
);
1468 isl_int_gcd(v
, m
, gcd
);
1469 isl_int_divexact(stride
, gcd
, v
);
1471 if (isl_int_is_zero(stride
) || isl_int_is_one(stride
))
1474 Euclid(m
, stride
, &factor
, &v
, &gcd
);
1476 isl_int_neg(factor
, factor
);
1478 c
= isl_constraint_copy(c
);
1479 s
= cloog_stride_alloc_from_constraint(stride
,
1480 cloog_constraint_from_isl_constraint(c
), factor
);
1483 isl_int_clear(stride
);
1484 isl_int_clear(factor
);
1492 struct cloog_isl_find_stride_data
{
1494 CloogStride
*stride
;
1497 /* Check if the given constraint can be used to derive
1498 * a stride on the iterator identified by data->level.
1499 * We first check that there are some existentially quantified variables
1500 * and that the coefficient at data->level is non-zero.
1501 * Then we call construct_stride for further checks and the actual
1502 * construction of the CloogStride.
1504 static int find_stride(__isl_take isl_constraint
*c
, void *user
)
1506 struct cloog_isl_find_stride_data
*data
;
1510 data
= (struct cloog_isl_find_stride_data
*)user
;
1513 isl_constraint_free(c
);
1517 n
= isl_constraint_dim(c
, isl_dim_div
);
1519 isl_constraint_free(c
);
1525 isl_constraint_get_coefficient(c
, isl_dim_set
, data
->level
- 1, &v
);
1526 if (!isl_int_is_zero(v
))
1527 data
->stride
= construct_stride(c
, data
->level
);
1531 isl_constraint_free(c
);
1536 /* Check if the given list of domains has a common stride on the given level.
1537 * If so, return a pointer to a CloogStride object. If not, return NULL.
1539 * We project out all later variables, take the union and compute
1540 * the affine hull of the union. Then we check the (equality)
1541 * constraints in this affine hull for imposing a stride.
1543 CloogStride
*cloog_domain_list_stride(CloogDomainList
*list
, int level
)
1545 struct cloog_isl_find_stride_data data
= { level
, NULL
};
1552 n
= isl_set_dim(&list
->domain
->set
, isl_dim_set
) - first
;
1553 set
= isl_set_project_out(isl_set_copy(&list
->domain
->set
),
1554 isl_dim_set
, first
, n
);
1556 for (list
= list
->next
; list
; list
= list
->next
) {
1558 n
= isl_set_dim(&list
->domain
->set
, isl_dim_set
) - first
;
1559 set_i
= isl_set_project_out(isl_set_copy(&list
->domain
->set
),
1560 isl_dim_set
, first
, n
);
1561 set
= isl_set_union(set
, set_i
);
1563 aff
= isl_set_affine_hull(set
);
1565 r
= isl_basic_set_foreach_constraint(aff
, &find_stride
, &data
);
1568 isl_basic_set_free(aff
);