6 #include <cloog/isl/cloog.h>
8 #include <isl/constraint.h>
12 CloogDomain
*cloog_domain_from_isl_set(struct isl_set
*set
)
14 set
= isl_set_detect_equalities(set
);
15 set
= isl_set_compute_divs(set
);
16 return (CloogDomain
*)set
;
19 __isl_give isl_set
*isl_set_from_cloog_domain(CloogDomain
*domain
)
21 return (isl_set
*)domain
;
24 CloogScattering
*cloog_scattering_from_isl_map(struct isl_map
*map
)
26 return (CloogScattering
*)map
;
29 __isl_give isl_map
*isl_map_from_cloog_scattering(CloogScattering
*scattering
)
31 return (isl_map
*)scattering
;
36 * Returns true if each scattering dimension is defined in terms
37 * of the original iterators.
39 int cloog_scattering_fully_specified(CloogScattering
*scattering
,
42 isl_map
*map
= isl_map_from_cloog_scattering(scattering
);
43 return isl_map_is_single_valued(map
);
47 CloogConstraintSet
*cloog_domain_constraints(CloogDomain
*domain
)
50 isl_set
*set
= isl_set_from_cloog_domain(domain
);
51 assert(isl_set_n_basic_set(set
) == 1);
52 bset
= isl_set_copy_basic_set(set
);
53 return cloog_constraint_set_from_isl_basic_set(bset
);
57 void cloog_domain_print_constraints(FILE *foo
, CloogDomain
*domain
,
61 isl_set
*set
= isl_set_from_cloog_domain(domain
);
64 isl_set_print(set
, foo
, 0, ISL_FORMAT_EXT_POLYLIB
);
66 assert(isl_set_n_basic_set(set
) == 1);
67 bset
= isl_set_copy_basic_set(set
);
68 isl_basic_set_print(bset
, foo
,
69 0, NULL
, NULL
, ISL_FORMAT_POLYLIB
);
70 isl_basic_set_free(bset
);
75 void cloog_scattering_print_constraints(FILE *foo
, CloogScattering
*scattering
)
77 isl_map
*map
= isl_map_from_cloog_scattering(scattering
);
78 isl_map_print(map
, foo
, 0, ISL_FORMAT_EXT_POLYLIB
);
82 void cloog_domain_free(CloogDomain
* domain
)
84 isl_set
*set
= isl_set_from_cloog_domain(domain
);
89 void cloog_scattering_free(CloogScattering
*scatt
)
91 isl_map
*map
= isl_map_from_cloog_scattering(scatt
);
96 CloogDomain
* cloog_domain_copy(CloogDomain
* domain
)
98 isl_set
*set
= isl_set_from_cloog_domain(domain
);
99 return cloog_domain_from_isl_set(isl_set_copy(set
));
104 * cloog_domain_convex function:
105 * Computes the convex hull of domain.
107 CloogDomain
*cloog_domain_convex(CloogDomain
*domain
)
109 isl_set
*set
= isl_set_from_cloog_domain(domain
);
110 set
= isl_set_from_basic_set(isl_set_convex_hull(isl_set_copy(set
)));
111 return cloog_domain_from_isl_set(set
);
116 * cloog_domain_simple_convex:
117 * Given a list (union) of polyhedra, this function returns a "simple"
118 * convex hull of this union. In particular, the constraints of the
119 * the returned polyhedron consist of (parametric) lower and upper
120 * bounds on individual variables and constraints that appear in the
121 * original polyhedra.
123 CloogDomain
*cloog_domain_simple_convex(CloogDomain
*domain
)
125 struct isl_basic_set
*hull
;
126 isl_set
*set
= isl_set_from_cloog_domain(domain
);
128 if (cloog_domain_isconvex(domain
))
129 return cloog_domain_copy(domain
);
131 hull
= isl_set_bounded_simple_hull(isl_set_copy(set
));
132 return cloog_domain_from_isl_set(isl_set_from_basic_set(hull
));
137 * cloog_domain_simplify function:
138 * Given two polyhedral domains (dom1) and (dom2),
139 * this function finds the largest domain set (or the smallest list
140 * of non-redundant constraints), that when intersected with polyhedral
141 * domain (dom2) equals (dom1)intersect(dom2). The output is a new CloogDomain
142 * structure with a polyhedral domain with the "redundant" constraints removed.
143 * NB: the second domain is required not to be a union.
145 CloogDomain
*cloog_domain_simplify(CloogDomain
*dom1
, CloogDomain
*dom2
)
147 isl_set
*set1
= isl_set_from_cloog_domain(dom1
);
148 isl_set
*set2
= isl_set_from_cloog_domain(dom2
);
149 set1
= isl_set_gist(isl_set_copy(set1
), isl_set_copy(set2
));
150 return cloog_domain_from_isl_set(set1
);
155 * cloog_domain_union function:
156 * This function returns a new polyhedral domain which is the union of
157 * two polyhedral domains (dom1) U (dom2).
158 * Frees dom1 and dom2;
160 CloogDomain
*cloog_domain_union(CloogDomain
*dom1
, CloogDomain
*dom2
)
162 isl_set
*set1
= isl_set_from_cloog_domain(dom1
);
163 isl_set
*set2
= isl_set_from_cloog_domain(dom2
);
164 set1
= isl_set_union(set1
, set2
);
165 return cloog_domain_from_isl_set(set1
);
171 * cloog_domain_intersection function:
172 * This function returns a new polyhedral domain which is the intersection of
173 * two polyhedral domains (dom1) \cap (dom2).
175 CloogDomain
*cloog_domain_intersection(CloogDomain
*dom1
, CloogDomain
*dom2
)
177 isl_set
*set1
= isl_set_from_cloog_domain(dom1
);
178 isl_set
*set2
= isl_set_from_cloog_domain(dom2
);
179 set1
= isl_set_intersect(isl_set_copy(set1
), isl_set_copy(set2
));
180 return cloog_domain_from_isl_set(set1
);
185 * cloog_domain_difference function:
186 * Returns the set difference domain \ minus.
188 CloogDomain
*cloog_domain_difference(CloogDomain
*domain
, CloogDomain
*minus
)
190 isl_set
*set1
= isl_set_from_cloog_domain(domain
);
191 isl_set
*set2
= isl_set_from_cloog_domain(minus
);
192 set1
= isl_set_subtract(isl_set_copy(set1
), isl_set_copy(set2
));
193 return cloog_domain_from_isl_set(set1
);
198 * cloog_domain_sort function:
199 * This function topologically sorts (nb_doms) domains. Here (doms) is an
200 * array of pointers to CloogDomains, (nb_doms) is the number of domains,
201 * (level) is the level to consider for partial ordering (nb_par) is the
202 * parameter space dimension, (permut) if not NULL, is an array of (nb_doms)
203 * integers that contains a permutation specification after call in order to
204 * apply the topological sorting.
206 void cloog_domain_sort(CloogDomain
**doms
, unsigned nb_doms
, unsigned level
,
211 unsigned char **follows
;
212 isl_set
*set_i
, *set_j
;
213 isl_basic_set
*bset_i
, *bset_j
;
217 set_i
= isl_set_from_cloog_domain(doms
[0]);
218 ctx
= isl_set_get_ctx(set_i
);
219 for (i
= 0; i
< nb_doms
; i
++) {
220 set_i
= isl_set_from_cloog_domain(doms
[i
]);
221 assert(isl_set_n_basic_set(set_i
) == 1);
224 follows
= isl_alloc_array(ctx
, unsigned char *, nb_doms
);
226 for (i
= 0; i
< nb_doms
; ++i
) {
227 follows
[i
] = isl_alloc_array(ctx
, unsigned char, nb_doms
);
229 for (j
= 0; j
< nb_doms
; ++j
)
233 for (i
= 1; i
< nb_doms
; ++i
) {
234 for (j
= 0; j
< i
; ++j
) {
235 if (follows
[i
][j
] || follows
[j
][i
])
237 set_i
= isl_set_from_cloog_domain(doms
[i
]);
238 set_j
= isl_set_from_cloog_domain(doms
[j
]);
239 bset_i
= isl_set_copy_basic_set(set_i
);
240 bset_j
= isl_set_copy_basic_set(set_j
);
241 cmp
= isl_basic_set_compare_at(bset_i
, bset_j
, level
-1);
242 isl_basic_set_free(bset_i
);
243 isl_basic_set_free(bset_j
);
248 for (k
= 0; k
< i
; ++k
)
249 follows
[i
][k
] |= follows
[j
][k
];
252 for (k
= 0; k
< i
; ++k
)
253 follows
[k
][i
] |= follows
[k
][j
];
258 for (i
= 0, j
= 0; i
< nb_doms
; j
= (j
+ 1) % nb_doms
) {
259 for (k
= 0; k
< nb_doms
; ++k
)
264 for (k
= 0; k
< nb_doms
; ++k
)
271 for (i
= 0; i
< nb_doms
; ++i
)
278 * Check whether there is or may be any value of dom1 at the given level
279 * that is greater than or equal to a value of dom2 at the same level.
282 * 1 is there is or may be a greater-than pair.
283 * 0 if there is no greater-than pair, but there may be an equal-to pair
284 * -1 if there is definitely no such pair
286 int cloog_domain_follows(CloogDomain
*dom1
, CloogDomain
*dom2
, unsigned level
)
288 isl_set
*set1
= isl_set_from_cloog_domain(dom1
);
289 isl_set
*set2
= isl_set_from_cloog_domain(dom2
);
292 follows
= isl_set_follows_at(set1
, set2
, level
- 1);
293 assert(follows
>= -1);
300 * cloog_domain_empty function:
301 * Returns an empty domain of the same dimensions as template.
303 CloogDomain
*cloog_domain_empty(CloogDomain
*template)
305 isl_set
*set
= isl_set_from_cloog_domain(template);
306 return cloog_domain_from_isl_set(isl_set_empty_like(set
));
311 * Return 1 if the specified dimension has both an upper and a lower bound.
313 int cloog_domain_is_bounded(CloogDomain
*dom
, unsigned level
)
315 isl_set
*set
= isl_set_from_cloog_domain(dom
);
316 return isl_set_dim_is_bounded(set
, isl_dim_set
, level
- 1);
320 /******************************************************************************
321 * Structure display function *
322 ******************************************************************************/
326 * cloog_domain_print_structure :
327 * this function is a more human-friendly way to display the CloogDomain data
328 * structure, it only shows the constraint system and includes an indentation
329 * level (level) in order to work with others print_structure functions.
331 void cloog_domain_print_structure(FILE *file
, CloogDomain
*domain
, int level
,
335 isl_set
*set
= isl_set_from_cloog_domain(domain
);
337 /* Go to the right level. */
338 for (i
= 0; i
< level
; i
++)
339 fprintf(file
, "|\t");
342 fprintf(file
, "+-- Null CloogDomain\n");
345 fprintf(file
, "+-- %s\n", name
);
346 for (i
= 0; i
< level
+1; ++i
)
347 fprintf(file
, "|\t");
349 isl_set_print(set
, file
, 0, ISL_FORMAT_ISL
);
355 /******************************************************************************
356 * Memory deallocation function *
357 ******************************************************************************/
360 void cloog_domain_list_free(CloogDomainList
*list
)
362 CloogDomainList
*next
;
364 for ( ; list
; list
= next
) {
366 cloog_domain_free(list
->domain
);
373 * cloog_scattering_list_free function:
374 * This function frees the allocated memory for a CloogScatteringList structure.
376 void cloog_scattering_list_free(CloogScatteringList
*list
)
378 while (list
!= NULL
) {
379 CloogScatteringList
*temp
= list
->next
;
380 isl_map
*map
= isl_map_from_cloog_scattering(list
->scatt
);
388 /******************************************************************************
390 ******************************************************************************/
394 * cloog_domain_read_context function:
395 * Read parameter domain.
397 CloogDomain
*cloog_domain_read_context(CloogState
*state
, FILE *input
)
399 struct isl_ctx
*ctx
= state
->backend
->ctx
;
402 set
= isl_set_read_from_file(ctx
, input
, 0);
403 set
= isl_set_move_dims(set
, isl_dim_param
, 0,
404 isl_dim_set
, 0, isl_set_dim(set
, isl_dim_set
));
406 return cloog_domain_from_isl_set(set
);
411 * cloog_domain_from_context
412 * Reinterpret context by turning parameters into variables.
414 CloogDomain
*cloog_domain_from_context(CloogDomain
*context
)
416 isl_set
*set
= isl_set_from_cloog_domain(context
);
418 set
= isl_set_move_dims(set
, isl_dim_set
, 0,
419 isl_dim_param
, 0, isl_set_dim(set
, isl_dim_param
));
421 return cloog_domain_from_isl_set(set
);
426 * cloog_domain_union_read function:
427 * This function reads a union of polyhedra into a file (input) and
428 * returns a pointer to a CloogDomain containing the read information.
430 CloogDomain
*cloog_domain_union_read(CloogState
*state
,
431 FILE *input
, int nb_parameters
)
433 struct isl_ctx
*ctx
= state
->backend
->ctx
;
436 set
= isl_set_read_from_file(ctx
, input
, nb_parameters
);
437 return cloog_domain_from_isl_set(set
);
442 * cloog_domain_read_scattering function:
443 * This function reads in a scattering function from the file input.
445 * We try to read the scattering relation as a map, but if it is
446 * specified in the original PolyLib format, then isl_map_read_from_file
447 * will treat the input as a set return a map with zero input dimensions.
448 * In this case, we need to decompose the set into a map from
449 * scattering dimensions to domain dimensions and then invert the
452 CloogScattering
*cloog_domain_read_scattering(CloogDomain
*domain
, FILE *input
)
454 isl_set
*set
= isl_set_from_cloog_domain(domain
);
455 isl_ctx
*ctx
= isl_set_get_ctx(set
);
456 struct isl_map
*scat
;
461 dim
= isl_set_dim(set
, isl_dim_set
);
462 nparam
= isl_set_dim(set
, isl_dim_param
);
463 scat
= isl_map_read_from_file(ctx
, input
, nparam
);
464 if (isl_map_dim(scat
, isl_dim_in
) != dim
) {
465 n_scat
= isl_map_dim(scat
, isl_dim_out
) - dim
;
466 scat
= isl_map_move_dims(scat
, isl_dim_in
, 0,
467 isl_dim_out
, n_scat
, dim
);
469 return cloog_scattering_from_isl_map(scat
);
472 /******************************************************************************
473 * CloogMatrix Reading function *
474 ******************************************************************************/
477 * isl_constraint_read_from_matrix:
478 * Convert a single line of a matrix to a isl_constraint.
479 * Returns a pointer to the constraint if successful; NULL otherwise.
481 static struct isl_constraint
*isl_constraint_read_from_matrix(
482 struct isl_dim
*dim
, cloog_int_t
*row
)
484 struct isl_constraint
*constraint
;
486 int nvariables
= isl_dim_size(dim
, isl_dim_set
);
487 int nparam
= isl_dim_size(dim
, isl_dim_param
);
489 if (cloog_int_is_zero(row
[0]))
490 constraint
= isl_equality_alloc(dim
);
492 constraint
= isl_inequality_alloc(dim
);
494 for (j
= 0; j
< nvariables
; ++j
)
495 isl_constraint_set_coefficient(constraint
, isl_dim_out
, j
,
498 for (j
= 0; j
< nparam
; ++j
)
499 isl_constraint_set_coefficient(constraint
, isl_dim_param
, j
,
500 row
[1 + nvariables
+ j
]);
502 isl_constraint_set_constant(constraint
, row
[1 + nvariables
+ nparam
]);
508 * isl_basic_set_read_from_matrix:
509 * Convert matrix to basic_set. The matrix contains nparam parameter columns.
510 * Returns a pointer to the basic_set if successful; NULL otherwise.
512 static struct isl_basic_set
*isl_basic_set_read_from_matrix(struct isl_ctx
*ctx
,
513 CloogMatrix
* matrix
, int nparam
)
516 struct isl_basic_set
*bset
;
518 unsigned nrows
, ncolumns
;
520 nrows
= matrix
->NbRows
;
521 ncolumns
= matrix
->NbColumns
;
522 int nvariables
= ncolumns
- 2 - nparam
;
524 dim
= isl_dim_set_alloc(ctx
, nparam
, nvariables
);
526 bset
= isl_basic_set_universe(isl_dim_copy(dim
));
528 for (i
= 0; i
< nrows
; ++i
) {
529 cloog_int_t
*row
= matrix
->p
[i
];
530 struct isl_constraint
*constraint
=
531 isl_constraint_read_from_matrix(isl_dim_copy(dim
), row
);
532 bset
= isl_basic_set_add_constraint(bset
, constraint
);
541 * cloog_domain_from_cloog_matrix:
542 * Create a CloogDomain containing the constraints described in matrix.
543 * nparam is the number of parameters contained in the domain.
544 * Returns a pointer to the CloogDomain if successful; NULL otherwise.
546 CloogDomain
*cloog_domain_from_cloog_matrix(CloogState
*state
,
547 CloogMatrix
*matrix
, int nparam
)
549 struct isl_ctx
*ctx
= state
->backend
->ctx
;
550 struct isl_basic_set
*bset
;
552 bset
= isl_basic_set_read_from_matrix(ctx
, matrix
, nparam
);
554 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset
));
558 * cloog_scattering_from_cloog_matrix:
559 * Create a CloogScattering containing the constraints described in matrix.
560 * nparam is the number of parameters contained in the domain.
561 * Returns a pointer to the CloogScattering if successful; NULL otherwise.
563 CloogScattering
*cloog_scattering_from_cloog_matrix(CloogState
*state
,
564 CloogMatrix
*matrix
, int nb_scat
, int nb_par
)
566 struct isl_ctx
*ctx
= state
->backend
->ctx
;
567 struct isl_basic_set
*bset
;
568 struct isl_basic_map
*scat
;
569 struct isl_dim
*dims
;
572 bset
= isl_basic_set_read_from_matrix(ctx
, matrix
, nb_par
);
573 dim
= isl_basic_set_n_dim(bset
) - nb_scat
;
574 dims
= isl_dim_alloc(ctx
, nb_par
, nb_scat
, dim
);
576 scat
= isl_basic_map_from_basic_set(bset
, dims
);
577 scat
= isl_basic_map_reverse(scat
);
578 return cloog_scattering_from_isl_map(isl_map_from_basic_map(scat
));
582 /******************************************************************************
583 * Processing functions *
584 ******************************************************************************/
589 * cloog_domain_isempty function:
591 int cloog_domain_isempty(CloogDomain
*domain
)
593 isl_set
*set
= isl_set_from_cloog_domain(domain
);
594 return isl_set_is_empty(set
);
599 * cloog_domain_universe function:
600 * This function returns the complete dim-dimensional space.
602 CloogDomain
*cloog_domain_universe(CloogState
*state
, unsigned dim
)
604 struct isl_dim
*dims
;
605 struct isl_basic_set
*bset
;
607 dims
= isl_dim_set_alloc(state
->backend
->ctx
, 0, dim
);
608 bset
= isl_basic_set_universe(dims
);
609 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset
));
614 * cloog_domain_project function:
615 * This function returns the projection of
616 * (domain) on the (level) first dimensions (i.e. outer loops).
618 CloogDomain
*cloog_domain_project(CloogDomain
*domain
, int level
)
620 isl_set
*set
= isl_set_from_cloog_domain(domain
);
621 set
= isl_set_remove_dims(isl_set_copy(set
), isl_dim_set
,
622 level
, isl_set_n_dim(set
) - level
);
623 set
= isl_set_compute_divs(set
);
625 set
= isl_set_remove_divs_involving_dims(set
,
626 isl_dim_set
, level
- 1, 1);
627 return cloog_domain_from_isl_set(set
);
632 * cloog_domain_extend function:
633 * This function returns the (domain) given as input with (dim)
634 * dimensions and (nb_par) parameters.
635 * This function does not free (domain), and returns a new CloogDomain.
637 CloogDomain
*cloog_domain_extend(CloogDomain
*domain
, int dim
)
639 isl_set
*set
= isl_set_from_cloog_domain(domain
);
640 set
= isl_set_extend(isl_set_copy(set
), isl_set_n_param(set
), dim
);
641 return cloog_domain_from_isl_set(set
);
646 * cloog_domain_never_integral function:
647 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0.
648 * There is no need to check for such constraints explicitly for the isl
651 int cloog_domain_never_integral(CloogDomain
* domain
)
653 isl_set
*set
= isl_set_from_cloog_domain(domain
);
654 return isl_set_is_empty(set
);
659 * Check whether the loop at "level" is executed at most once.
660 * We construct a map that maps all remaining variables to this iterator
661 * and check whether this map is single valued.
663 * Alternatively, we could have mapped the domain through a mapping
664 * [p] -> { [..., i] -> [..., i'] : i' > i }
665 * and then taken the intersection of the original domain and the transformed
666 * domain. If this intersection is empty, then the corresponding
667 * loop is executed at most once.
669 int cloog_domain_is_otl(CloogDomain
*domain
, int level
)
672 isl_set
*set
= isl_set_from_cloog_domain(domain
);
675 map
= isl_map_from_domain(isl_set_copy(set
));
676 map
= isl_map_move_dims(map
, isl_dim_out
, 0, isl_dim_in
, level
- 1, 1);
677 otl
= isl_map_is_single_valued(map
);
685 * cloog_domain_stride function:
686 * This function finds the stride imposed to unknown with the column number
687 * 'strided_level' in order to be integral. For instance, if we have a
688 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
689 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
690 * the unknown i. The function returns the imposed stride in a parameter field.
691 * - domain is the set of constraint we have to consider,
692 * - strided_level is the column number of the unknown for which a stride have
694 * - looking_level is the column number of the unknown that impose a stride to
696 * - stride is the stride that is returned back as a function parameter.
697 * - offset is the value of the constant c if the condition is of the shape
698 * (i + c)%s = 0, s being the stride.
700 void cloog_domain_stride(CloogDomain
*domain
, int strided_level
,
701 cloog_int_t
*stride
, cloog_int_t
*offset
)
703 isl_set
*set
= isl_set_from_cloog_domain(domain
);
704 isl_set_dim_residue_class(set
, strided_level
- 1, stride
, offset
);
705 if (!isl_int_is_zero(*offset
))
706 isl_int_sub(*offset
, *stride
, *offset
);
711 struct cloog_can_stride
{
716 static int constraint_can_stride(__isl_take isl_constraint
*c
, void *user
)
718 struct cloog_can_stride
*ccs
= (struct cloog_can_stride
*)user
;
724 isl_constraint_get_coefficient(c
, isl_dim_set
, ccs
->level
- 1, &v
);
725 if (isl_int_is_pos(v
)) {
726 n_div
= isl_constraint_dim(c
, isl_dim_div
);
727 for (i
= 0; i
< n_div
; ++i
) {
728 isl_constraint_get_coefficient(c
, isl_dim_div
, i
, &v
);
729 if (!isl_int_is_zero(v
))
736 isl_constraint_free(c
);
741 static int basic_set_can_stride(__isl_take isl_basic_set
*bset
, void *user
)
743 struct cloog_can_stride
*ccs
= (struct cloog_can_stride
*)user
;
746 r
= isl_basic_set_foreach_constraint(bset
, constraint_can_stride
, ccs
);
747 isl_basic_set_free(bset
);
753 * Return 1 if CLooG is allowed to perform stride detection on level "level"
755 * Currently, stride detection is only allowed when none of the lower
756 * bound constraints involve any existentially quantified variables.
757 * The reason is that the current isl interface does not make it
758 * easy to construct an integer division that depends on other integer
760 * By not allowing existentially quantified variables in the constraints,
761 * we can ignore them in cloog_domain_stride_lower_bound.
763 int cloog_domain_can_stride(CloogDomain
*domain
, int level
)
765 struct cloog_can_stride ccs
= { level
, 1 };
766 isl_set
*set
= isl_set_from_cloog_domain(domain
);
768 r
= isl_set_foreach_basic_set(set
, basic_set_can_stride
, &ccs
);
770 return ccs
.can_stride
;
774 struct cloog_stride_lower
{
778 isl_basic_set
*bounds
;
781 /* If the given constraint is a lower bound on csl->level, then add
782 * a lower bound to csl->bounds that makes sure that the remainder
783 * of the smallest value on division by csl->stride is equal to csl->offset.
785 * In particular, the given lower bound is of the form
789 * where f may depend on the parameters and other iterators.
790 * The stride is s and the offset is d.
791 * The lower bound -f/a may not satisfy the above condition. In fact,
792 * it may not even be integral. We want to round this value of i up
793 * to the nearest value that satisfies the condition and add the corresponding
794 * lower bound constraint. This nearest value is obtained by rounding
795 * i - d up to the nearest multiple of s.
796 * That is, we first subtract d
800 * then we round up to the nearest multiple of s
802 * i'' = s * ceil(i'/s)
804 * and finally, we add d again
808 * and impose the constraint i >= i'''.
812 * i'' = s * ceil((-f - a * d)/(a * s)) = - s * floor((f + a * d)/(a * s))
814 * i >= - s * floor((f + a * d)/(a * s)) + d
817 * i + s * floor((f + a * d)/(a * s)) - d >= 0
819 static int constraint_stride_lower(__isl_take isl_constraint
*c
, void *user
)
821 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
825 isl_constraint
*bound
;
828 unsigned nparam
, nvar
;
831 isl_constraint_get_coefficient(c
, isl_dim_set
, csl
->level
- 1, &v
);
832 if (!isl_int_is_pos(v
)) {
834 isl_constraint_free(c
);
841 nparam
= isl_constraint_dim(c
, isl_dim_param
);
842 nvar
= isl_constraint_dim(c
, isl_dim_set
);
843 bound
= isl_inequality_alloc(isl_basic_set_get_dim(csl
->bounds
));
844 div
= isl_div_alloc(isl_basic_set_get_dim(csl
->bounds
));
845 isl_int_mul(t
, v
, csl
->stride
->stride
);
846 isl_div_set_denominator(div
, t
);
847 for (i
= 0; i
< nparam
; ++i
) {
848 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &t
);
849 isl_div_set_coefficient(div
, isl_dim_param
, i
, t
);
851 for (i
= 0; i
< nvar
; ++i
) {
852 if (i
== csl
->level
- 1)
854 isl_constraint_get_coefficient(c
, isl_dim_set
, i
, &t
);
855 isl_div_set_coefficient(div
, isl_dim_set
, i
, t
);
857 isl_constraint_get_constant(c
, &t
);
858 isl_int_addmul(t
, v
, csl
->stride
->offset
);
859 isl_div_set_constant(div
, t
);
861 bound
= isl_constraint_add_div(bound
, div
, &pos
);
862 isl_int_set_si(t
, 1);
863 isl_constraint_set_coefficient(bound
, isl_dim_set
,
865 isl_constraint_set_coefficient(bound
, isl_dim_div
, pos
,
866 csl
->stride
->stride
);
867 isl_int_neg(t
, csl
->stride
->offset
);
868 isl_constraint_set_constant(bound
, t
);
869 csl
->bounds
= isl_basic_set_add_constraint(csl
->bounds
, bound
);
873 isl_constraint_free(c
);
878 /* This functions performs essentially the same operation as
879 * constraint_stride_lower, the only difference being that the offset d
880 * is not a constant, but an affine expression in terms of the parameters
881 * and earlier variables. In particular the affine expression is equal
882 * to the coefficients of stride->constraint multiplied by stride->factor.
883 * As in constraint_stride_lower, we add an extra bound
885 * i + s * floor((f + a * d)/(a * s)) - d >= 0
887 * for each lower bound
891 * where d is not the aforementioned affine expression.
893 static int constraint_stride_lower_c(__isl_take isl_constraint
*c
, void *user
)
895 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
899 isl_constraint
*bound
;
900 isl_constraint
*csl_c
;
903 unsigned nparam
, nvar
;
906 isl_constraint_get_coefficient(c
, isl_dim_set
, csl
->level
- 1, &v
);
907 if (!isl_int_is_pos(v
)) {
909 isl_constraint_free(c
);
914 csl_c
= &csl
->stride
->constraint
->isl
;
919 nparam
= isl_constraint_dim(c
, isl_dim_param
);
920 nvar
= isl_constraint_dim(c
, isl_dim_set
);
921 bound
= isl_inequality_alloc(isl_basic_set_get_dim(csl
->bounds
));
922 div
= isl_div_alloc(isl_basic_set_get_dim(csl
->bounds
));
923 isl_int_mul(t
, v
, csl
->stride
->stride
);
924 isl_div_set_denominator(div
, t
);
925 for (i
= 0; i
< nparam
; ++i
) {
926 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &t
);
927 isl_constraint_get_coefficient(csl_c
, isl_dim_param
, i
, &u
);
928 isl_int_mul(u
, u
, csl
->stride
->factor
);
929 isl_int_addmul(t
, v
, u
);
930 isl_div_set_coefficient(div
, isl_dim_param
, i
, t
);
932 isl_constraint_set_coefficient(bound
, isl_dim_param
, i
, u
);
934 for (i
= 0; i
< nvar
; ++i
) {
935 if (i
== csl
->level
- 1)
937 isl_constraint_get_coefficient(c
, isl_dim_set
, i
, &t
);
938 isl_constraint_get_coefficient(csl_c
, isl_dim_set
, i
, &u
);
939 isl_int_mul(u
, u
, csl
->stride
->factor
);
940 isl_int_addmul(t
, v
, u
);
941 isl_div_set_coefficient(div
, isl_dim_set
, i
, t
);
943 isl_constraint_set_coefficient(bound
, isl_dim_set
, i
, u
);
945 isl_constraint_get_constant(c
, &t
);
946 isl_constraint_get_constant(csl_c
, &u
);
947 isl_int_mul(u
, u
, csl
->stride
->factor
);
948 isl_int_addmul(t
, v
, u
);
949 isl_div_set_constant(div
, t
);
951 isl_constraint_set_constant(bound
, u
);
953 bound
= isl_constraint_add_div(bound
, div
, &pos
);
954 isl_int_set_si(t
, 1);
955 isl_constraint_set_coefficient(bound
, isl_dim_set
,
957 isl_constraint_set_coefficient(bound
, isl_dim_div
, pos
,
958 csl
->stride
->stride
);
959 csl
->bounds
= isl_basic_set_add_constraint(csl
->bounds
, bound
);
964 isl_constraint_free(c
);
969 static int basic_set_stride_lower(__isl_take isl_basic_set
*bset
, void *user
)
971 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
974 csl
->bounds
= isl_basic_set_universe_like(bset
);
975 if (csl
->stride
->constraint
)
976 r
= isl_basic_set_foreach_constraint(bset
,
977 &constraint_stride_lower_c
, csl
);
979 r
= isl_basic_set_foreach_constraint(bset
,
980 &constraint_stride_lower
, csl
);
981 bset
= isl_basic_set_intersect(bset
, csl
->bounds
);
982 csl
->set
= isl_set_union(csl
->set
, isl_set_from_basic_set(bset
));
988 * Update the lower bounds at level "level" to the given stride information.
989 * That is, make sure that the remainder on division by "stride"
990 * is equal to "offset".
992 CloogDomain
*cloog_domain_stride_lower_bound(CloogDomain
*domain
, int level
,
995 struct cloog_stride_lower csl
;
996 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1001 csl
.set
= isl_set_empty_like(set
);
1003 r
= isl_set_foreach_basic_set(set
, basic_set_stride_lower
, &csl
);
1006 cloog_domain_free(domain
);
1007 return cloog_domain_from_isl_set(csl
.set
);
1011 /* Add stride constraint, if any, to domain.
1013 CloogDomain
*cloog_domain_add_stride_constraint(CloogDomain
*domain
,
1014 CloogStride
*stride
)
1019 if (!stride
|| !stride
->constraint
)
1022 set
= isl_set_from_cloog_domain(domain
);
1023 c
= isl_constraint_copy(&stride
->constraint
->isl
);
1025 set
= isl_set_add_constraint(set
, c
);
1027 return cloog_domain_from_isl_set(set
);
1032 * cloog_domain_lazy_equal function:
1033 * This function returns 1 if the domains given as input are the same, 0 if it
1034 * is unable to decide.
1036 int cloog_domain_lazy_equal(CloogDomain
*d1
, CloogDomain
*d2
)
1038 isl_set
*set1
= isl_set_from_cloog_domain(d1
);
1039 isl_set
*set2
= isl_set_from_cloog_domain(d2
);
1040 return isl_set_fast_is_equal(set1
, set2
);
1043 struct cloog_bound_split
{
1050 static int constraint_bound_split(__isl_take isl_constraint
*c
, void *user
)
1052 struct cloog_bound_split
*cbs
= (struct cloog_bound_split
*)user
;
1058 isl_constraint_get_coefficient(c
, isl_dim_set
, cbs
->level
- 1, &v
);
1059 if (!cbs
->lower
&& isl_int_is_pos(v
))
1060 cbs
->lower
= handle
= 1;
1061 else if (!cbs
->upper
&& isl_int_is_neg(v
))
1062 cbs
->upper
= handle
= 1;
1064 for (i
= 0; i
< isl_set_dim(cbs
->set
, isl_dim_param
); ++i
) {
1065 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &v
);
1066 if (isl_int_is_zero(v
))
1068 cbs
->set
= isl_set_split_dims(cbs
->set
,
1069 isl_dim_param
, i
, 1);
1073 isl_constraint_free(c
);
1075 return (cbs
->lower
&& cbs
->upper
) ? -1 : 0;
1078 static int basic_set_bound_split(__isl_take isl_basic_set
*bset
, void *user
)
1080 struct cloog_bound_split
*cbs
= (struct cloog_bound_split
*)user
;
1085 r
= isl_basic_set_foreach_constraint(bset
, constraint_bound_split
, cbs
);
1086 isl_basic_set_free(bset
);
1087 return ((!cbs
->lower
|| !cbs
->upper
) && r
< 0) ? -1 : 0;
1091 * Return a union of sets S_i such that the convex hull of "dom",
1092 * when intersected with one the sets S_i, will have an upper and
1093 * lower bound for the dimension at "level" (provided "dom" itself
1094 * has such bounds for the dimensions).
1096 * We currently take a very simple approach. For each of the basic
1097 * sets in "dom" we pick a lower and an upper bound and split the
1098 * range of any parameter involved in these two bounds in a
1099 * nonnegative and a negative part. This ensures that the symbolic
1100 * constant in these two constraints are themselves bounded and
1101 * so there will be at least one upper and one lower bound
1102 * in the convex hull.
1104 CloogDomain
*cloog_domain_bound_splitter(CloogDomain
*dom
, int level
)
1106 struct cloog_bound_split cbs
;
1107 isl_set
*set
= isl_set_from_cloog_domain(dom
);
1110 cbs
.set
= isl_set_universe_like(set
);
1111 r
= isl_set_foreach_basic_set(set
, basic_set_bound_split
, &cbs
);
1113 return cloog_domain_from_isl_set(cbs
.set
);
1117 /* Check whether the union of scattering functions over all domains
1118 * is obviously injective.
1120 static int injective_scattering(CloogScatteringList
*list
)
1123 isl_union_map
*umap
;
1131 map
= isl_map_copy(isl_map_from_cloog_scattering(list
->scatt
));
1132 snprintf(name
, sizeof(name
), "S%d", i
);
1133 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
1134 umap
= isl_union_map_from_map(map
);
1136 for (list
= list
->next
, ++i
; list
; list
= list
->next
, ++i
) {
1137 map
= isl_map_copy(isl_map_from_cloog_scattering(list
->scatt
));
1138 snprintf(name
, sizeof(name
), "S%d", i
);
1139 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
1140 umap
= isl_union_map_add_map(umap
, map
);
1143 injective
= isl_union_map_plain_is_injective(umap
);
1145 isl_union_map_free(umap
);
1152 * cloog_scattering_lazy_block function:
1153 * This function returns 1 if the two scattering functions s1 and s2 given
1154 * as input are the same (except possibly for the final dimension, where we
1155 * allow a difference of 1), assuming that the domains on which this
1156 * scatterings are applied are the same.
1157 * In fact this function answers the question "can I
1158 * safely consider the two domains as only one with two statements (a block) ?".
1159 * A difference of 1 in the final dimension is only allowed if the
1160 * entire scattering function is injective.
1161 * - s1 and s2 are the two domains to check for blocking,
1162 * - scattering is the linked list of all domains,
1163 * - scattdims is the total number of scattering dimentions.
1165 int cloog_scattering_lazy_block(CloogScattering
*s1
, CloogScattering
*s2
,
1166 CloogScatteringList
*scattering
, int scattdims
)
1169 struct isl_dim
*dim
;
1170 struct isl_map
*rel
;
1171 struct isl_set
*delta
;
1172 isl_map
*map1
= isl_map_from_cloog_scattering(s1
);
1173 isl_map
*map2
= isl_map_from_cloog_scattering(s2
);
1178 n_scat
= isl_map_dim(map1
, isl_dim_out
);
1179 if (n_scat
!= isl_map_dim(map2
, isl_dim_out
))
1182 dim
= isl_map_get_dim(map1
);
1183 dim
= isl_dim_map_from_set(isl_dim_domain(dim
));
1184 rel
= isl_map_identity(dim
);
1185 rel
= isl_map_apply_domain(rel
, isl_map_copy(map1
));
1186 rel
= isl_map_apply_range(rel
, isl_map_copy(map2
));
1187 delta
= isl_map_deltas(rel
);
1189 for (i
= 0; i
< n_scat
; ++i
) {
1190 fixed
= isl_set_fast_dim_is_fixed(delta
, i
, &cst
);
1193 if (isl_int_is_zero(cst
))
1197 if (!isl_int_is_one(cst
))
1199 if (!injective_scattering(scattering
))
1202 block
= i
>= n_scat
;
1204 isl_set_free(delta
);
1210 * cloog_domain_lazy_disjoint function:
1211 * This function returns 1 if the domains given as input are disjoint, 0 if it
1212 * is unable to decide.
1214 int cloog_domain_lazy_disjoint(CloogDomain
*d1
, CloogDomain
*d2
)
1216 isl_set
*set1
= isl_set_from_cloog_domain(d1
);
1217 isl_set
*set2
= isl_set_from_cloog_domain(d2
);
1218 return isl_set_fast_is_disjoint(set1
, set2
);
1223 * cloog_scattering_list_lazy_same function:
1224 * This function returns 1 if two domains in the list are the same, 0 if it
1225 * is unable to decide.
1227 int cloog_scattering_list_lazy_same(CloogScatteringList
*list
)
1229 CloogScatteringList
*one
, *other
;
1230 isl_map
*one_map
, *other_map
;
1232 for (one
= list
; one
; one
= one
->next
) {
1233 one_map
= isl_map_from_cloog_scattering(one
->scatt
);
1234 for (other
= one
->next
; other
; other
= other
->next
) {
1235 other_map
= isl_map_from_cloog_scattering(other
->scatt
);
1236 if (isl_map_fast_is_equal(one_map
, other_map
))
1243 int cloog_domain_dimension(CloogDomain
* domain
)
1245 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1246 return isl_set_dim(set
, isl_dim_set
);
1249 int cloog_domain_parameter_dimension(CloogDomain
*domain
)
1251 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1252 return isl_set_dim(set
, isl_dim_param
);
1255 int cloog_scattering_dimension(CloogScattering
*scatt
, CloogDomain
*domain
)
1257 isl_map
*map
= isl_map_from_cloog_scattering(scatt
);
1258 return isl_map_dim(map
, isl_dim_out
);
1261 int cloog_domain_isconvex(CloogDomain
* domain
)
1263 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1264 return isl_set_n_basic_set(set
) <= 1;
1269 * cloog_domain_cut_first function:
1270 * This function splits off and returns the first convex set in the
1271 * union "domain". The remainder of the union is returned in rest.
1272 * The original "domain" itself is destroyed and may not be used
1273 * after a call to this function.
1275 CloogDomain
*cloog_domain_cut_first(CloogDomain
*domain
, CloogDomain
**rest
)
1277 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1278 struct isl_basic_set
*first
;
1280 first
= isl_set_copy_basic_set(set
);
1281 set
= isl_set_drop_basic_set(set
, first
);
1282 *rest
= cloog_domain_from_isl_set(set
);
1284 return cloog_domain_from_isl_set(isl_set_from_basic_set(first
));
1289 * Given a union domain, try to find a simpler representation
1290 * using fewer sets in the union.
1291 * The original "domain" itself is destroyed and may not be used
1292 * after a call to this function.
1294 CloogDomain
*cloog_domain_simplify_union(CloogDomain
*domain
)
1296 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1297 return cloog_domain_from_isl_set(isl_set_coalesce(set
));
1302 * cloog_scattering_lazy_isscalar function:
1303 * this function returns 1 if the scattering dimension 'dimension' in the
1304 * scattering 'scatt' is constant.
1305 * If value is not NULL, then it is set to the constant value of dimension.
1307 int cloog_scattering_lazy_isscalar(CloogScattering
*scatt
, int dimension
,
1310 isl_map
*map
= isl_map_from_cloog_scattering(scatt
);
1311 return isl_map_fast_is_fixed(map
, isl_dim_out
, dimension
, value
);
1316 * cloog_domain_lazy_isconstant function:
1317 * this function returns 1 if the dimension 'dimension' in the
1318 * domain 'domain' is constant.
1319 * If value is not NULL, then it is set to the constant value of dimension.
1321 int cloog_domain_lazy_isconstant(CloogDomain
*domain
, int dimension
,
1324 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1325 return isl_set_fast_dim_is_fixed(set
, dimension
, value
);
1330 * cloog_scattering_erase_dimension function:
1331 * this function returns a CloogDomain structure builds from 'domain' where
1332 * we removed the dimension 'dimension' and every constraint involving this
1335 CloogScattering
*cloog_scattering_erase_dimension(CloogScattering
*scattering
,
1338 isl_map
*map
= isl_map_from_cloog_scattering(scattering
);
1339 map
= isl_map_remove_dims(isl_map_copy(map
), isl_dim_out
, dimension
, 1);
1340 return cloog_scattering_from_isl_map(map
);
1344 * cloog_domain_cube:
1345 * Construct and return a dim-dimensional cube, with values ranging
1346 * between min and max in each dimension.
1348 CloogDomain
*cloog_domain_cube(CloogState
*state
,
1349 int dim
, cloog_int_t min
, cloog_int_t max
)
1352 struct isl_basic_set
*cube
;
1353 struct isl_basic_set
*interval
;
1354 struct isl_basic_set_list
*list
;
1357 return cloog_domain_universe(state
, dim
);
1359 interval
= isl_basic_set_interval(state
->backend
->ctx
, min
, max
);
1360 list
= isl_basic_set_list_alloc(state
->backend
->ctx
, dim
);
1361 for (i
= 0; i
< dim
; ++i
)
1362 list
= isl_basic_set_list_add(list
, isl_basic_set_copy(interval
));
1363 isl_basic_set_free(interval
);
1364 cube
= isl_basic_set_list_product(list
);
1365 return cloog_domain_from_isl_set(isl_set_from_basic_set(cube
));
1370 * cloog_domain_scatter function:
1371 * This function add the scattering (scheduling) informations to a domain.
1373 CloogDomain
*cloog_domain_scatter(CloogDomain
*domain
, CloogScattering
*scatt
)
1375 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1376 isl_map
*map
= isl_map_from_cloog_scattering(scatt
);
1378 map
= isl_map_reverse(isl_map_copy(map
));
1379 map
= isl_map_intersect_range(map
, set
);
1380 set
= isl_set_flatten(isl_map_wrap(map
));
1381 return cloog_domain_from_isl_set(set
);
1384 static int add_domain_from_map(__isl_take isl_map
*map
, void *user
)
1388 CloogDomain
*domain
;
1389 CloogScattering
*scat
;
1390 CloogUnionDomain
**ud
= (CloogUnionDomain
**)user
;
1392 dim
= isl_map_get_dim(map
);
1393 name
= isl_dim_get_tuple_name(dim
, isl_dim_in
);
1394 domain
= cloog_domain_from_isl_set(isl_map_domain(isl_map_copy(map
)));
1395 scat
= cloog_scattering_from_isl_map(map
);
1396 *ud
= cloog_union_domain_add_domain(*ud
, name
, domain
, scat
, NULL
);
1403 * Construct a CloogUnionDomain from an isl_union_map representing
1404 * a global scattering function. The input is a mapping from different
1405 * spaces (different tuple names and possibly different dimensions)
1406 * to a common space. The iteration domains are set to the domains
1407 * in each space. The statement names are set to the names of the
1408 * spaces. The parameter names of the result are set to those of
1409 * the input, but the iterator and scattering dimension names are
1412 CloogUnionDomain
*cloog_union_domain_from_isl_union_map(
1413 __isl_take isl_union_map
*umap
)
1418 CloogUnionDomain
*ud
;
1420 dim
= isl_union_map_get_dim(umap
);
1421 nparam
= isl_dim_size(dim
, isl_dim_param
);
1423 ud
= cloog_union_domain_alloc(nparam
);
1425 for (i
= 0; i
< nparam
; ++i
) {
1426 const char *s
= isl_dim_get_name(dim
, isl_dim_param
, i
);
1427 ud
= cloog_union_domain_set_name(ud
, CLOOG_PARAM
, i
, s
);
1431 if (isl_union_map_foreach_map(umap
, &add_domain_from_map
, &ud
) < 0) {
1432 isl_union_map_free(umap
);
1433 cloog_union_domain_free(ud
);
1437 isl_union_map_free(umap
);
1442 static int count_same_name(__isl_keep isl_dim
*dim
,
1443 enum isl_dim_type type
, unsigned pos
, const char *name
)
1445 enum isl_dim_type t
;
1448 int len
= strlen(name
);
1450 for (t
= isl_dim_param
; t
<= type
&& t
<= isl_dim_out
; ++t
) {
1451 s
= t
== type
? pos
: isl_dim_size(dim
, t
);
1452 for (p
= 0; p
< s
; ++p
) {
1453 const char *n
= isl_dim_get_name(dim
, t
, p
);
1454 if (n
&& !strncmp(n
, name
, len
))
1461 static int add_domain(__isl_take isl_set
*set
, void *user
)
1468 CloogDomain
*domain
;
1469 CloogUnionDomain
**ud
= (CloogUnionDomain
**)user
;
1471 ctx
= isl_set_get_ctx(set
);
1472 dim
= isl_set_get_dim(set
);
1473 name
= isl_dim_get_tuple_name(dim
, isl_dim_set
);
1474 set
= isl_set_flatten(set
);
1475 set
= isl_set_set_tuple_name(set
, NULL
);
1476 domain
= cloog_domain_from_isl_set(set
);
1477 *ud
= cloog_union_domain_add_domain(*ud
, name
, domain
, NULL
, NULL
);
1479 nvar
= isl_dim_size(dim
, isl_dim_set
);
1480 for (i
= 0; i
< nvar
; ++i
) {
1481 char *long_name
= NULL
;
1484 name
= isl_dim_get_name(dim
, isl_dim_set
, i
);
1486 snprintf(buffer
, sizeof(buffer
), "i%d", i
);
1489 n
= count_same_name(dim
, isl_dim_set
, i
, name
);
1491 int size
= strlen(name
) + 10;
1492 long_name
= isl_alloc_array(ctx
, char, size
);
1494 cloog_die("memory overflow.\n");
1495 snprintf(long_name
, size
, "%s_%d", name
, n
);
1498 *ud
= cloog_union_domain_set_name(*ud
, CLOOG_ITER
, i
, name
);
1507 * Construct a CloogUnionDomain from an isl_union_set.
1508 * The statement names are set to the names of the
1509 * spaces. The parameter and iterator names of the result are set to those of
1510 * the input, but the scattering dimension names are left unspecified.
1512 CloogUnionDomain
*cloog_union_domain_from_isl_union_set(
1513 __isl_take isl_union_set
*uset
)
1518 CloogUnionDomain
*ud
;
1520 dim
= isl_union_set_get_dim(uset
);
1521 nparam
= isl_dim_size(dim
, isl_dim_param
);
1523 ud
= cloog_union_domain_alloc(nparam
);
1525 for (i
= 0; i
< nparam
; ++i
) {
1526 const char *s
= isl_dim_get_name(dim
, isl_dim_param
, i
);
1527 ud
= cloog_union_domain_set_name(ud
, CLOOG_PARAM
, i
, s
);
1531 if (isl_union_set_foreach_set(uset
, &add_domain
, &ud
) < 0) {
1532 isl_union_set_free(uset
);
1533 cloog_union_domain_free(ud
);
1537 isl_union_set_free(uset
);
1542 /* Computes x, y and g such that g = gcd(a,b) and a*x+b*y = g */
1543 static void Euclid(cloog_int_t a
, cloog_int_t b
,
1544 cloog_int_t
*x
, cloog_int_t
*y
, cloog_int_t
*g
)
1546 cloog_int_t c
, d
, e
, f
, tmp
;
1552 cloog_int_init(tmp
);
1553 cloog_int_abs(c
, a
);
1554 cloog_int_abs(d
, b
);
1555 cloog_int_set_si(e
, 1);
1556 cloog_int_set_si(f
, 0);
1557 while (cloog_int_is_pos(d
)) {
1558 cloog_int_tdiv_q(tmp
, c
, d
);
1559 cloog_int_mul(tmp
, tmp
, f
);
1560 cloog_int_sub(e
, e
, tmp
);
1561 cloog_int_tdiv_q(tmp
, c
, d
);
1562 cloog_int_mul(tmp
, tmp
, d
);
1563 cloog_int_sub(c
, c
, tmp
);
1564 cloog_int_swap(c
, d
);
1565 cloog_int_swap(e
, f
);
1567 cloog_int_set(*g
, c
);
1568 if (cloog_int_is_zero(a
))
1569 cloog_int_set_si(*x
, 0);
1570 else if (cloog_int_is_pos(a
))
1571 cloog_int_set(*x
, e
);
1572 else cloog_int_neg(*x
, e
);
1573 if (cloog_int_is_zero(b
))
1574 cloog_int_set_si(*y
, 0);
1576 cloog_int_mul(tmp
, a
, *x
);
1577 cloog_int_sub(tmp
, c
, tmp
);
1578 cloog_int_divexact(*y
, tmp
, b
);
1584 cloog_int_clear(tmp
);
1587 /* Construct a CloogStride from the given constraint for the given level,
1589 * We first compute the gcd of the coefficients of the existentially
1590 * quantified variables and then remove any common factors it has
1591 * with the coefficient at the given level.
1592 * The result is the value of the stride and if it is not one,
1593 * then it is possible to construct a CloogStride.
1594 * The constraint leading to the stride is stored in the CloogStride
1595 * as well a value (factor) such that the product of this value
1596 * and the coefficient at the given level is equal to -1 modulo the stride.
1598 static CloogStride
*construct_stride(isl_constraint
*c
, int level
)
1601 isl_int v
, m
, gcd
, stride
, factor
;
1610 isl_int_init(factor
);
1611 isl_int_init(stride
);
1613 isl_constraint_get_coefficient(c
, isl_dim_set
, level
- 1, &v
);
1614 sign
= isl_int_sgn(v
);
1617 isl_int_set_si(gcd
, 0);
1618 n
= isl_constraint_dim(c
, isl_dim_div
);
1619 for (i
= 0; i
< n
; ++i
) {
1620 isl_constraint_get_coefficient(c
, isl_dim_div
, i
, &v
);
1621 isl_int_gcd(gcd
, gcd
, v
);
1624 isl_int_gcd(v
, m
, gcd
);
1625 isl_int_divexact(stride
, gcd
, v
);
1627 if (isl_int_is_zero(stride
) || isl_int_is_one(stride
))
1630 Euclid(m
, stride
, &factor
, &v
, &gcd
);
1632 isl_int_neg(factor
, factor
);
1634 c
= isl_constraint_copy(c
);
1635 s
= cloog_stride_alloc_from_constraint(stride
,
1636 cloog_constraint_from_isl_constraint(c
), factor
);
1639 isl_int_clear(stride
);
1640 isl_int_clear(factor
);
1648 struct cloog_isl_find_stride_data
{
1650 CloogStride
*stride
;
1653 /* Check if the given constraint can be used to derive
1654 * a stride on the iterator identified by data->level.
1655 * We first check that there are some existentially quantified variables
1656 * and that the coefficient at data->level is non-zero.
1657 * Then we call construct_stride for further checks and the actual
1658 * construction of the CloogStride.
1660 static int find_stride(__isl_take isl_constraint
*c
, void *user
)
1662 struct cloog_isl_find_stride_data
*data
;
1666 data
= (struct cloog_isl_find_stride_data
*)user
;
1669 isl_constraint_free(c
);
1673 n
= isl_constraint_dim(c
, isl_dim_div
);
1675 isl_constraint_free(c
);
1681 isl_constraint_get_coefficient(c
, isl_dim_set
, data
->level
- 1, &v
);
1682 if (!isl_int_is_zero(v
))
1683 data
->stride
= construct_stride(c
, data
->level
);
1687 isl_constraint_free(c
);
1692 /* Check if the given list of domains has a common stride on the given level.
1693 * If so, return a pointer to a CloogStride object. If not, return NULL.
1695 * We project out all later variables, take the union and compute
1696 * the affine hull of the union. Then we check the (equality)
1697 * constraints in this affine hull for imposing a stride.
1699 CloogStride
*cloog_domain_list_stride(CloogDomainList
*list
, int level
)
1701 struct cloog_isl_find_stride_data data
= { level
, NULL
};
1708 set
= isl_set_from_cloog_domain(list
->domain
);
1709 n
= isl_set_dim(set
, isl_dim_set
) - first
;
1710 set
= isl_set_project_out(isl_set_copy(set
), isl_dim_set
, first
, n
);
1712 for (list
= list
->next
; list
; list
= list
->next
) {
1713 isl_set
*set_i
= isl_set_from_cloog_domain(list
->domain
);
1714 n
= isl_set_dim(set_i
, isl_dim_set
) - first
;
1715 set_i
= isl_set_project_out(isl_set_copy(set_i
),
1716 isl_dim_set
, first
, n
);
1717 set
= isl_set_union(set
, set_i
);
1719 aff
= isl_set_affine_hull(set
);
1721 r
= isl_basic_set_foreach_constraint(aff
, &find_stride
, &data
);
1724 isl_basic_set_free(aff
);
1729 struct cloog_can_unroll
{
1736 /* Check if we can still unroll given the presence of the given
1738 * Only lower bounds on the current level have any impact.
1739 * If such a lower bound involves any existentially quantified
1740 * variables, we currently punt.
1741 * Otherwise, if we haven't recorded any other lower bound,
1742 * we record the current one. If we have already recorded another
1743 * bound, then there are at least two lower bounds and we cannot unroll.
1745 static int constraint_can_unroll(__isl_take isl_constraint
*c
, void *user
)
1747 struct cloog_can_unroll
*ccu
= (struct cloog_can_unroll
*)user
;
1752 isl_constraint_get_coefficient(c
, isl_dim_set
, ccu
->level
- 1, &v
);
1753 if (isl_int_is_pos(v
)) {
1754 n_div
= isl_constraint_dim(c
, isl_dim_div
);
1756 isl_constraint_involves_dims(c
, isl_dim_div
, 0, n_div
))
1757 ccu
->can_unroll
= 0;
1759 ccu
->c
= isl_constraint_copy(c
);
1762 isl_constraint_free(c
);
1768 /* Check if we can unroll the domain at the current level.
1769 * If the domain is a union, we cannot. Otherwise, we check the
1772 static int basic_set_can_unroll(__isl_take isl_basic_set
*bset
, void *user
)
1774 struct cloog_can_unroll
*ccu
= (struct cloog_can_unroll
*)user
;
1777 if (ccu
->c
|| !ccu
->can_unroll
)
1778 ccu
->can_unroll
= 0;
1780 bset
= isl_basic_set_remove_redundancies(bset
);
1781 r
= isl_basic_set_foreach_constraint(bset
,
1782 &constraint_can_unroll
, ccu
);
1784 isl_basic_set_free(bset
);
1789 /* Check if we can unroll the given domain at the given level, and
1790 * if so, return the single lower bound in *lb and an upper bound
1791 * on the number of iterations in *n.
1792 * If we cannot unroll, return 0 and set *lb to NULL.
1794 * We can unroll, if we can identify a single lower bound on level
1795 * and if the number of iterations is bounded by a constant.
1796 * We first look for the lower bound, say l, on the iterator i
1797 * and then compute the maximal value of (i - ceil(l) + 1).
1799 int cloog_domain_can_unroll(CloogDomain
*domain
, int level
, cloog_int_t
*n
,
1800 CloogConstraint
**lb
)
1802 struct cloog_can_unroll ccu
= { 1, level
, NULL
};
1803 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1806 enum isl_lp_result res
;
1809 r
= isl_set_foreach_basic_set(set
, &basic_set_can_unroll
, &ccu
);
1813 if (!ccu
.can_unroll
) {
1814 isl_constraint_free(ccu
.c
);
1818 aff
= isl_constraint_get_bound(ccu
.c
, isl_dim_set
, level
- 1);
1819 aff
= isl_aff_ceil(aff
);
1820 aff
= isl_aff_neg(aff
);
1821 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_set
, level
- 1, 1);
1822 res
= isl_set_max(set
, aff
, n
);
1825 if (res
== isl_lp_unbounded
) {
1826 isl_constraint_free(ccu
.c
);
1829 assert(res
== isl_lp_ok
);
1831 cloog_int_add_ui(*n
, *n
, 1);
1833 *lb
= cloog_constraint_from_isl_constraint(ccu
.c
);
1835 return ccu
.can_unroll
;
1839 /* Fix the iterator i at the given level to l + o,
1840 * where l is prescribed by the constraint lb and o is equal to offset.
1841 * In particular, if lb is the constraint
1845 * then l = ceil(f(j)/a).
1847 CloogDomain
*cloog_domain_fixed_offset(CloogDomain
*domain
,
1848 int level
, CloogConstraint
*lb
, cloog_int_t offset
)
1851 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1854 aff
= isl_constraint_get_bound(&lb
->isl
, isl_dim_set
, level
- 1);
1855 aff
= isl_aff_ceil(aff
);
1856 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_set
, level
- 1, -1);
1857 aff
= isl_aff_add_constant(aff
, offset
);
1858 eq
= isl_equality_from_aff(aff
);
1859 set
= isl_set_add_constraint(set
, eq
);
1861 return cloog_domain_from_isl_set(set
);