6 #include <cloog/isl/cloog.h>
8 #include <isl/constraint.h>
14 #include <isl/val_gmp.h>
17 #include <osl/macros.h>
18 #include <osl/relation.h>
21 CloogDomain
*cloog_domain_from_isl_set(__isl_take isl_set
*set
)
23 if (isl_set_is_params(set
))
24 set
= isl_set_from_params(set
);
25 set
= isl_set_detect_equalities(set
);
26 set
= isl_set_compute_divs(set
);
27 return (CloogDomain
*)set
;
30 __isl_give isl_set
*isl_set_from_cloog_domain(CloogDomain
*domain
)
32 return (isl_set
*)domain
;
35 CloogScattering
*cloog_scattering_from_isl_map(__isl_take isl_map
*map
)
37 return (CloogScattering
*)map
;
40 __isl_give isl_map
*isl_map_from_cloog_scattering(CloogScattering
*scattering
)
42 return (isl_map
*)scattering
;
47 * Returns true if each scattering dimension is defined in terms
48 * of the original iterators.
50 int cloog_scattering_fully_specified(CloogScattering
*scattering
,
53 isl_map
*map
= isl_map_from_cloog_scattering(scattering
);
54 return isl_map_is_single_valued(map
);
58 CloogConstraintSet
*cloog_domain_constraints(CloogDomain
*domain
)
61 isl_set
*set
= isl_set_from_cloog_domain(domain
);
62 assert(isl_set_n_basic_set(set
) == 1);
63 bset
= isl_set_copy_basic_set(set
);
64 return cloog_constraint_set_from_isl_basic_set(bset
);
68 void cloog_domain_print_constraints(FILE *foo
, CloogDomain
*domain
,
72 isl_set
*set
= isl_set_from_cloog_domain(domain
);
75 isl_set_print(set
, foo
, 0, ISL_FORMAT_EXT_POLYLIB
);
77 assert(isl_set_n_basic_set(set
) == 1);
78 bset
= isl_set_copy_basic_set(set
);
79 isl_basic_set_print(bset
, foo
,
80 0, NULL
, NULL
, ISL_FORMAT_POLYLIB
);
81 isl_basic_set_free(bset
);
86 void cloog_scattering_print_constraints(FILE *foo
, CloogScattering
*scattering
)
88 isl_map
*map
= isl_map_from_cloog_scattering(scattering
);
89 isl_map_print(map
, foo
, 0, ISL_FORMAT_EXT_POLYLIB
);
93 void cloog_domain_free(CloogDomain
* domain
)
95 isl_set
*set
= isl_set_from_cloog_domain(domain
);
100 void cloog_scattering_free(CloogScattering
*scatt
)
102 isl_map
*map
= isl_map_from_cloog_scattering(scatt
);
107 CloogDomain
* cloog_domain_copy(CloogDomain
* domain
)
109 isl_set
*set
= isl_set_from_cloog_domain(domain
);
110 return cloog_domain_from_isl_set(isl_set_copy(set
));
115 * cloog_domain_convex function:
116 * Computes the convex hull of domain.
118 CloogDomain
*cloog_domain_convex(CloogDomain
*domain
)
120 isl_set
*set
= isl_set_from_cloog_domain(domain
);
121 set
= isl_set_from_basic_set(isl_set_convex_hull(isl_set_copy(set
)));
122 return cloog_domain_from_isl_set(set
);
127 * cloog_domain_simple_convex:
128 * Given a list (union) of polyhedra, this function returns a "simple"
129 * convex hull of this union. In particular, the constraints of the
130 * the returned polyhedron consist of (parametric) lower and upper
131 * bounds on individual variables and constraints that appear in the
132 * original polyhedra.
134 CloogDomain
*cloog_domain_simple_convex(CloogDomain
*domain
)
136 struct isl_basic_set
*hull
;
137 isl_set
*set
= isl_set_from_cloog_domain(domain
);
139 if (cloog_domain_isconvex(domain
))
140 return cloog_domain_copy(domain
);
142 hull
= isl_set_bounded_simple_hull(isl_set_copy(set
));
143 return cloog_domain_from_isl_set(isl_set_from_basic_set(hull
));
148 * cloog_domain_simplify function:
149 * Given two polyhedral domains (dom1) and (dom2),
150 * this function finds the largest domain set (or the smallest list
151 * of non-redundant constraints), that when intersected with polyhedral
152 * domain (dom2) equals (dom1)intersect(dom2). The output is a new CloogDomain
153 * structure with a polyhedral domain with the "redundant" constraints removed.
154 * NB: the second domain is required not to be a union.
156 CloogDomain
*cloog_domain_simplify(CloogDomain
*dom1
, CloogDomain
*dom2
)
158 isl_set
*set1
= isl_set_from_cloog_domain(dom1
);
159 isl_set
*set2
= isl_set_from_cloog_domain(dom2
);
160 set1
= isl_set_gist(isl_set_copy(set1
), isl_set_copy(set2
));
161 return cloog_domain_from_isl_set(set1
);
166 * cloog_domain_union function:
167 * This function returns a new polyhedral domain which is the union of
168 * two polyhedral domains (dom1) U (dom2).
169 * Frees dom1 and dom2;
171 CloogDomain
*cloog_domain_union(CloogDomain
*dom1
, CloogDomain
*dom2
)
173 isl_set
*set1
= isl_set_from_cloog_domain(dom1
);
174 isl_set
*set2
= isl_set_from_cloog_domain(dom2
);
175 set1
= isl_set_union(set1
, set2
);
176 return cloog_domain_from_isl_set(set1
);
182 * cloog_domain_intersection function:
183 * This function returns a new polyhedral domain which is the intersection of
184 * two polyhedral domains (dom1) \cap (dom2).
186 CloogDomain
*cloog_domain_intersection(CloogDomain
*dom1
, CloogDomain
*dom2
)
188 isl_set
*set1
= isl_set_from_cloog_domain(dom1
);
189 isl_set
*set2
= isl_set_from_cloog_domain(dom2
);
190 set1
= isl_set_intersect(isl_set_copy(set1
), isl_set_copy(set2
));
191 return cloog_domain_from_isl_set(set1
);
196 * cloog_domain_difference function:
197 * Returns the set difference domain \ minus.
199 CloogDomain
*cloog_domain_difference(CloogDomain
*domain
, CloogDomain
*minus
)
201 isl_set
*set1
= isl_set_from_cloog_domain(domain
);
202 isl_set
*set2
= isl_set_from_cloog_domain(minus
);
203 set1
= isl_set_subtract(isl_set_copy(set1
), isl_set_copy(set2
));
204 return cloog_domain_from_isl_set(set1
);
209 * cloog_domain_sort function:
210 * This function topologically sorts (nb_doms) domains. Here (doms) is an
211 * array of pointers to CloogDomains, (nb_doms) is the number of domains,
212 * (level) is the level to consider for partial ordering (nb_par) is the
213 * parameter space dimension, (permut) if not NULL, is an array of (nb_doms)
214 * integers that contains a permutation specification after call in order to
215 * apply the topological sorting.
217 void cloog_domain_sort(CloogDomain
**doms
, unsigned nb_doms
, unsigned level
,
222 unsigned char **follows
;
223 isl_set
*set_i
, *set_j
;
224 isl_basic_set
*bset_i
, *bset_j
;
228 set_i
= isl_set_from_cloog_domain(doms
[0]);
229 ctx
= isl_set_get_ctx(set_i
);
230 for (i
= 0; i
< nb_doms
; i
++) {
231 set_i
= isl_set_from_cloog_domain(doms
[i
]);
232 assert(isl_set_n_basic_set(set_i
) == 1);
235 follows
= isl_alloc_array(ctx
, unsigned char *, nb_doms
);
237 for (i
= 0; i
< nb_doms
; ++i
) {
238 follows
[i
] = isl_alloc_array(ctx
, unsigned char, nb_doms
);
240 for (j
= 0; j
< nb_doms
; ++j
)
244 for (i
= 1; i
< nb_doms
; ++i
) {
245 for (j
= 0; j
< i
; ++j
) {
246 if (follows
[i
][j
] || follows
[j
][i
])
248 set_i
= isl_set_from_cloog_domain(doms
[i
]);
249 set_j
= isl_set_from_cloog_domain(doms
[j
]);
250 bset_i
= isl_set_copy_basic_set(set_i
);
251 bset_j
= isl_set_copy_basic_set(set_j
);
252 cmp
= isl_basic_set_compare_at(bset_i
, bset_j
, level
-1);
253 isl_basic_set_free(bset_i
);
254 isl_basic_set_free(bset_j
);
259 for (k
= 0; k
< i
; ++k
)
260 follows
[i
][k
] |= follows
[j
][k
];
263 for (k
= 0; k
< i
; ++k
)
264 follows
[k
][i
] |= follows
[k
][j
];
269 for (i
= 0, j
= 0; i
< nb_doms
; j
= (j
+ 1) % nb_doms
) {
270 for (k
= 0; k
< nb_doms
; ++k
)
275 for (k
= 0; k
< nb_doms
; ++k
)
282 for (i
= 0; i
< nb_doms
; ++i
)
289 * Check whether there is or may be any value of dom1 at the given level
290 * that is greater than or equal to a value of dom2 at the same level.
293 * 1 is there is or may be a greater-than pair.
294 * 0 if there is no greater-than pair, but there may be an equal-to pair
295 * -1 if there is definitely no such pair
297 int cloog_domain_follows(CloogDomain
*dom1
, CloogDomain
*dom2
, unsigned level
)
299 isl_set
*set1
= isl_set_from_cloog_domain(dom1
);
300 isl_set
*set2
= isl_set_from_cloog_domain(dom2
);
303 follows
= isl_set_follows_at(set1
, set2
, level
- 1);
304 assert(follows
>= -1);
311 * cloog_domain_empty function:
312 * Returns an empty domain of the same dimensions as template.
314 CloogDomain
*cloog_domain_empty(CloogDomain
*template)
316 isl_set
*set
= isl_set_from_cloog_domain(template);
317 isl_space
*space
= isl_set_get_space(set
);
318 return cloog_domain_from_isl_set(isl_set_empty(space
));
323 * Return 1 if the specified dimension has both an upper and a lower bound.
325 int cloog_domain_is_bounded(CloogDomain
*dom
, unsigned level
)
327 isl_set
*set
= isl_set_from_cloog_domain(dom
);
328 return isl_set_dim_is_bounded(set
, isl_dim_set
, level
- 1);
332 /******************************************************************************
333 * Structure display function *
334 ******************************************************************************/
338 * cloog_domain_print_structure :
339 * this function is a more human-friendly way to display the CloogDomain data
340 * structure, it only shows the constraint system and includes an indentation
341 * level (level) in order to work with others print_structure functions.
343 void cloog_domain_print_structure(FILE *file
, CloogDomain
*domain
, int level
,
347 isl_set
*set
= isl_set_from_cloog_domain(domain
);
349 /* Go to the right level. */
350 for (i
= 0; i
< level
; i
++)
351 fprintf(file
, "|\t");
354 fprintf(file
, "+-- Null CloogDomain\n");
357 fprintf(file
, "+-- %s\n", name
);
358 for (i
= 0; i
< level
+1; ++i
)
359 fprintf(file
, "|\t");
361 isl_set_print(set
, file
, 0, ISL_FORMAT_ISL
);
367 /******************************************************************************
368 * Memory deallocation function *
369 ******************************************************************************/
372 void cloog_domain_list_free(CloogDomainList
*list
)
374 CloogDomainList
*next
;
376 for ( ; list
; list
= next
) {
378 cloog_domain_free(list
->domain
);
385 * cloog_scattering_list_free function:
386 * This function frees the allocated memory for a CloogScatteringList structure.
388 void cloog_scattering_list_free(CloogScatteringList
*list
)
390 while (list
!= NULL
) {
391 CloogScatteringList
*temp
= list
->next
;
392 isl_map
*map
= isl_map_from_cloog_scattering(list
->scatt
);
400 /******************************************************************************
402 ******************************************************************************/
406 * cloog_domain_read_context function:
407 * Read parameter domain.
409 CloogDomain
*cloog_domain_read_context(CloogState
*state
, FILE *input
)
411 struct isl_ctx
*ctx
= state
->backend
->ctx
;
414 set
= isl_set_read_from_file(ctx
, input
);
415 set
= isl_set_move_dims(set
, isl_dim_param
, 0,
416 isl_dim_set
, 0, isl_set_dim(set
, isl_dim_set
));
418 return cloog_domain_from_isl_set(set
);
423 * cloog_domain_from_context
424 * Reinterpret context by turning parameters into variables.
426 CloogDomain
*cloog_domain_from_context(CloogDomain
*context
)
428 isl_set
*set
= isl_set_from_cloog_domain(context
);
430 set
= isl_set_move_dims(set
, isl_dim_set
, 0,
431 isl_dim_param
, 0, isl_set_dim(set
, isl_dim_param
));
433 return cloog_domain_from_isl_set(set
);
438 * cloog_domain_union_read function:
439 * This function reads a union of polyhedra into a file (input) and
440 * returns a pointer to a CloogDomain containing the read information.
442 CloogDomain
*cloog_domain_union_read(CloogState
*state
,
443 FILE *input
, int nb_parameters
)
445 struct isl_ctx
*ctx
= state
->backend
->ctx
;
448 set
= isl_set_read_from_file(ctx
, input
);
449 if (isl_set_dim(set
, isl_dim_param
) != nb_parameters
) {
450 int dim
= isl_set_dim(set
, isl_dim_set
);
451 set
= isl_set_move_dims(set
, isl_dim_param
, 0,
452 isl_dim_set
, dim
- nb_parameters
, nb_parameters
);
454 return cloog_domain_from_isl_set(set
);
459 * cloog_domain_read_scattering function:
460 * This function reads in a scattering function from the file input.
462 * We try to read the scattering relation as a map, but if it is
463 * specified in the original PolyLib format, then isl_map_read_from_file
464 * will treat the input as a set return a map with zero input dimensions.
465 * In this case, we need to decompose the set into a map from
466 * scattering dimensions to domain dimensions and then invert the
469 CloogScattering
*cloog_domain_read_scattering(CloogDomain
*domain
, FILE *input
)
471 isl_set
*set
= isl_set_from_cloog_domain(domain
);
472 isl_ctx
*ctx
= isl_set_get_ctx(set
);
473 struct isl_map
*scat
;
478 dim
= isl_set_dim(set
, isl_dim_set
);
479 nparam
= isl_set_dim(set
, isl_dim_param
);
480 scat
= isl_map_read_from_file(ctx
, input
);
481 if (isl_map_dim(scat
, isl_dim_param
) != nparam
) {
482 int n_out
= isl_map_dim(scat
, isl_dim_out
);
483 scat
= isl_map_move_dims(scat
, isl_dim_param
, 0,
484 isl_dim_out
, n_out
- nparam
, nparam
);
486 if (isl_map_dim(scat
, isl_dim_in
) != dim
) {
487 n_scat
= isl_map_dim(scat
, isl_dim_out
) - dim
;
488 scat
= isl_map_move_dims(scat
, isl_dim_in
, 0,
489 isl_dim_out
, n_scat
, dim
);
491 return cloog_scattering_from_isl_map(scat
);
494 /******************************************************************************
495 * CloogMatrix Reading function *
496 ******************************************************************************/
499 * isl_constraint_read_from_matrix:
500 * Convert a single line of a matrix to a isl_constraint.
501 * Returns a pointer to the constraint if successful; NULL otherwise.
503 static struct isl_constraint
*isl_constraint_read_from_matrix(
504 struct isl_space
*dim
, cloog_int_t
*row
)
506 struct isl_constraint
*constraint
;
508 int nvariables
= isl_space_dim(dim
, isl_dim_set
);
509 int nparam
= isl_space_dim(dim
, isl_dim_param
);
510 isl_local_space
*ls
= isl_local_space_from_space(dim
);
512 if (cloog_int_is_zero(row
[0]))
513 constraint
= isl_equality_alloc(ls
);
515 constraint
= isl_inequality_alloc(ls
);
517 for (j
= 0; j
< nvariables
; ++j
) {
518 isl_val
*val
= cloog_int_to_isl_val(isl_constraint_get_ctx(constraint
), row
[1 + j
]);
519 isl_constraint_set_coefficient_val(constraint
, isl_dim_out
, j
, val
);
522 for (j
= 0; j
< nparam
; ++j
) {
523 isl_val
*val
= cloog_int_to_isl_val(isl_constraint_get_ctx(constraint
), row
[1 + nvariables
+ j
]);
524 isl_constraint_set_coefficient_val(constraint
, isl_dim_param
, j
, val
);
527 isl_val
*val
= cloog_int_to_isl_val(isl_constraint_get_ctx(constraint
), row
[1 + nvariables
+ nparam
]);
528 isl_constraint_set_constant_val(constraint
, val
);
534 * isl_basic_set_read_from_matrix:
535 * Convert matrix to basic_set. The matrix contains nparam parameter columns.
536 * Returns a pointer to the basic_set if successful; NULL otherwise.
538 static struct isl_basic_set
*isl_basic_set_read_from_matrix(struct isl_ctx
*ctx
,
539 CloogMatrix
* matrix
, int nparam
)
541 struct isl_space
*dim
;
542 struct isl_basic_set
*bset
;
544 unsigned nrows
, ncolumns
;
546 nrows
= matrix
->NbRows
;
547 ncolumns
= matrix
->NbColumns
;
548 int nvariables
= ncolumns
- 2 - nparam
;
550 dim
= isl_space_set_alloc(ctx
, nparam
, nvariables
);
552 bset
= isl_basic_set_universe(isl_space_copy(dim
));
554 for (i
= 0; i
< nrows
; ++i
) {
555 cloog_int_t
*row
= matrix
->p
[i
];
556 struct isl_constraint
*constraint
=
557 isl_constraint_read_from_matrix(isl_space_copy(dim
), row
);
558 bset
= isl_basic_set_add_constraint(bset
, constraint
);
567 * cloog_domain_from_cloog_matrix:
568 * Create a CloogDomain containing the constraints described in matrix.
569 * nparam is the number of parameters contained in the domain.
570 * Returns a pointer to the CloogDomain if successful; NULL otherwise.
572 CloogDomain
*cloog_domain_from_cloog_matrix(CloogState
*state
,
573 CloogMatrix
*matrix
, int nparam
)
575 struct isl_ctx
*ctx
= state
->backend
->ctx
;
576 struct isl_basic_set
*bset
;
578 bset
= isl_basic_set_read_from_matrix(ctx
, matrix
, nparam
);
580 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset
));
584 * cloog_scattering_from_cloog_matrix:
585 * Create a CloogScattering containing the constraints described in matrix.
586 * nparam is the number of parameters contained in the domain.
587 * Returns a pointer to the CloogScattering if successful; NULL otherwise.
589 CloogScattering
*cloog_scattering_from_cloog_matrix(CloogState
*state
,
590 CloogMatrix
*matrix
, int nb_scat
, int nb_par
)
592 struct isl_ctx
*ctx
= state
->backend
->ctx
;
593 struct isl_basic_set
*bset
;
594 struct isl_basic_map
*scat
;
595 struct isl_space
*dims
;
598 bset
= isl_basic_set_read_from_matrix(ctx
, matrix
, nb_par
);
599 dim
= isl_basic_set_n_dim(bset
) - nb_scat
;
600 dims
= isl_space_alloc(ctx
, nb_par
, nb_scat
, dim
);
602 scat
= isl_basic_map_from_basic_set(bset
, dims
);
603 scat
= isl_basic_map_reverse(scat
);
604 return cloog_scattering_from_isl_map(isl_map_from_basic_map(scat
));
608 /******************************************************************************
609 * Processing functions *
610 ******************************************************************************/
615 * Converts an openscop relation to a CLooG domain.
616 * \param[in,out] state CLooG state.
617 * \param[in] relation OpenScop relation to convert.
618 * \return A new CloogDomain corresponding to the input OpenScop relation.
620 CloogDomain
*cloog_domain_from_osl_relation(CloogState
*state
,
621 osl_relation_p relation
) {
623 struct isl_ctx
*ctx
= state
->backend
->ctx
;
625 CloogDomain
*domain
= NULL
;
627 if (relation
!= NULL
) {
628 str
= osl_relation_spprint_polylib(relation
, NULL
);
629 set
= isl_set_read_from_str(ctx
, str
);
632 domain
= cloog_domain_from_isl_set(set
);
639 * Converts an openscop scattering relation to a CLooG scattering.
640 * \param[in,out] state CLooG state.
641 * \param[in] relation OpenScop relation to convert.
642 * \return A new CloogScattering corresponding to the input OpenScop relation.
644 CloogScattering
*cloog_scattering_from_osl_relation(CloogState
*state
,
645 osl_relation_p relation
) {
647 struct isl_ctx
*ctx
= state
->backend
->ctx
;
649 CloogScattering
*scattering
= NULL
;
651 if (relation
!= NULL
) {
652 if (relation
->type
!= OSL_TYPE_SCATTERING
)
653 cloog_die("Cannot convert a non-scattering relation to a scattering.\n");
655 str
= osl_relation_spprint_polylib(relation
, NULL
);
656 map
= isl_map_read_from_str(ctx
, str
);
659 scattering
= cloog_scattering_from_isl_map(map
);
667 * cloog_domain_isempty function:
669 int cloog_domain_isempty(CloogDomain
*domain
)
671 isl_set
*set
= isl_set_from_cloog_domain(domain
);
672 return isl_set_is_empty(set
);
677 * cloog_domain_universe function:
678 * This function returns the complete dim-dimensional space.
680 CloogDomain
*cloog_domain_universe(CloogState
*state
, unsigned dim
)
682 struct isl_space
*dims
;
683 struct isl_basic_set
*bset
;
685 dims
= isl_space_set_alloc(state
->backend
->ctx
, 0, dim
);
686 bset
= isl_basic_set_universe(dims
);
687 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset
));
692 * cloog_domain_project function:
693 * This function returns the projection of
694 * (domain) on the (level) first dimensions (i.e. outer loops).
696 CloogDomain
*cloog_domain_project(CloogDomain
*domain
, int level
)
698 isl_set
*set
= isl_set_from_cloog_domain(domain
);
699 set
= isl_set_remove_dims(isl_set_copy(set
), isl_dim_set
,
700 level
, isl_set_n_dim(set
) - level
);
701 set
= isl_set_compute_divs(set
);
703 set
= isl_set_remove_divs_involving_dims(set
,
704 isl_dim_set
, level
- 1, 1);
705 return cloog_domain_from_isl_set(set
);
710 * cloog_domain_extend function:
711 * This function returns the (domain) given as input with (dim)
712 * dimensions and (nb_par) parameters.
713 * This function does not free (domain), and returns a new CloogDomain.
715 CloogDomain
*cloog_domain_extend(CloogDomain
*domain
, int dim
)
717 isl_set
*set
= isl_set_from_cloog_domain(domain
);
718 int n
= isl_set_dim(set
, isl_dim_set
);
719 set
= isl_set_add_dims(isl_set_copy(set
), isl_dim_set
, dim
- n
);
720 return cloog_domain_from_isl_set(set
);
725 * cloog_domain_never_integral function:
726 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0.
727 * There is no need to check for such constraints explicitly for the isl
730 int cloog_domain_never_integral(CloogDomain
* domain
)
732 isl_set
*set
= isl_set_from_cloog_domain(domain
);
733 return isl_set_is_empty(set
);
738 * Check whether the loop at "level" is executed at most once.
739 * We construct a map that maps all remaining variables to this iterator
740 * and check whether this map is single valued.
742 * Alternatively, we could have mapped the domain through a mapping
743 * [p] -> { [..., i] -> [..., i'] : i' > i }
744 * and then taken the intersection of the original domain and the transformed
745 * domain. If this intersection is empty, then the corresponding
746 * loop is executed at most once.
748 int cloog_domain_is_otl(CloogDomain
*domain
, int level
)
751 isl_set
*set
= isl_set_from_cloog_domain(domain
);
754 map
= isl_map_from_domain(isl_set_copy(set
));
755 map
= isl_map_move_dims(map
, isl_dim_out
, 0, isl_dim_in
, level
- 1, 1);
756 otl
= isl_map_is_single_valued(map
);
764 * cloog_domain_stride function:
765 * This function finds the stride imposed to unknown with the column number
766 * 'strided_level' in order to be integral. For instance, if we have a
767 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
768 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
769 * the unknown i. The function returns the imposed stride in a parameter field.
770 * - domain is the set of constraint we have to consider,
771 * - strided_level is the column number of the unknown for which a stride have
773 * - looking_level is the column number of the unknown that impose a stride to
775 * - stride is the stride that is returned back as a function parameter.
776 * - offset is the value of the constant c if the condition is of the shape
777 * (i + c)%s = 0, s being the stride.
779 void cloog_domain_stride(CloogDomain
*domain
, int strided_level
,
780 cloog_int_t
*stride
, cloog_int_t
*offset
)
783 isl_set
*set
= isl_set_from_cloog_domain(domain
);
784 isl_val
*stride_val
= NULL
;
785 isl_val
*offset_val
= NULL
;
786 ret
= isl_set_dim_residue_class_val(set
, strided_level
- 1, &stride_val
, &offset_val
);
788 cloog_die("failure to compute stride.\n");
789 isl_val_to_cloog_int(stride_val
, stride
);
790 isl_val_to_cloog_int(offset_val
, offset
);
792 if (!cloog_int_is_zero(*offset
))
793 cloog_int_sub(*offset
, *stride
, *offset
);
795 isl_val_free(stride_val
);
796 isl_val_free(offset_val
);
802 struct cloog_can_stride
{
807 static int constraint_can_stride(__isl_take isl_constraint
*c
, void *user
)
809 struct cloog_can_stride
*ccs
= (struct cloog_can_stride
*)user
;
814 if (isl_constraint_is_equality(c
)) {
815 isl_constraint_free(c
);
819 v
= isl_constraint_get_coefficient_val(c
, isl_dim_set
, ccs
->level
- 1);
820 if (isl_val_is_pos(v
)) {
821 n_div
= isl_constraint_dim(c
, isl_dim_div
);
823 for (i
= 0; i
< n_div
; ++i
) {
825 v
= isl_constraint_get_coefficient_val(c
, isl_dim_div
, i
);
826 if (!isl_val_is_zero(v
))
834 isl_constraint_free(c
);
838 static int basic_set_can_stride(__isl_take isl_basic_set
*bset
, void *user
)
840 struct cloog_can_stride
*ccs
= (struct cloog_can_stride
*)user
;
843 r
= isl_basic_set_foreach_constraint(bset
, constraint_can_stride
, ccs
);
844 isl_basic_set_free(bset
);
850 * Return 1 if CLooG is allowed to perform stride detection on level "level"
852 * Currently, stride detection is only allowed when none of the lower
853 * bound constraints involve any existentially quantified variables.
854 * The reason is that the current isl interface does not make it
855 * easy to construct an integer division that depends on other integer
857 * By not allowing existentially quantified variables in the constraints,
858 * we can ignore them in cloog_domain_stride_lower_bound.
860 int cloog_domain_can_stride(CloogDomain
*domain
, int level
)
862 struct cloog_can_stride ccs
= { level
, 1 };
863 isl_set
*set
= isl_set_from_cloog_domain(domain
);
865 r
= isl_set_foreach_basic_set(set
, basic_set_can_stride
, &ccs
);
867 return ccs
.can_stride
;
871 struct cloog_stride_lower
{
875 isl_basic_set
*bounds
;
878 /* If the given constraint is a lower bound on csl->level, then add
879 * a lower bound to csl->bounds that makes sure that the remainder
880 * of the smallest value on division by csl->stride is equal to csl->offset.
882 * In particular, the given lower bound is of the form
886 * where f may depend on the parameters and other iterators.
887 * The stride is s and the offset is d.
888 * The lower bound -f/a may not satisfy the above condition. In fact,
889 * it may not even be integral. We want to round this value of i up
890 * to the nearest value that satisfies the condition and add the corresponding
891 * lower bound constraint. This nearest value is obtained by rounding
892 * i - d up to the nearest multiple of s.
893 * That is, we first subtract d
897 * then we round up to the nearest multiple of s
899 * i'' = s * ceil(i'/s)
901 * and finally, we add d again
905 * and impose the constraint i >= i'''.
909 * i'' = s * ceil((-f - a * d)/(a * s)) = - s * floor((f + a * d)/(a * s))
911 * i >= - s * floor((f + a * d)/(a * s)) + d
914 * i + s * floor((f + a * d)/(a * s)) - d >= 0
916 static int constraint_stride_lower(__isl_take isl_constraint
*c
, void *user
)
918 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
920 isl_constraint
*bound
;
923 if (isl_constraint_is_equality(c
)) {
924 isl_constraint_free(c
);
928 v
= isl_constraint_get_coefficient_val(c
, isl_dim_set
, csl
->level
- 1);
929 if (!isl_val_is_pos(v
)) {
931 isl_constraint_free(c
);
937 b
= isl_constraint_get_bound(c
, isl_dim_set
, csl
->level
- 1);
940 b
= isl_aff_add_constant_val(b
, cloog_int_to_isl_val(isl_constraint_get_ctx(c
), csl
->stride
->offset
));
941 b
= isl_aff_scale_down_val(b
, cloog_int_to_isl_val(isl_constraint_get_ctx(c
), csl
->stride
->stride
));
942 b
= isl_aff_floor(b
);
943 b
= isl_aff_scale_val(b
, cloog_int_to_isl_val(isl_constraint_get_ctx(c
), csl
->stride
->stride
));
944 v
= cloog_int_to_isl_val(isl_constraint_get_ctx(c
), csl
->stride
->offset
);
946 b
= isl_aff_add_constant_val(b
, v
);
947 b
= isl_aff_add_coefficient_si(b
, isl_dim_in
, csl
->level
- 1, 1);
949 bound
= isl_inequality_from_aff(b
);
951 csl
->bounds
= isl_basic_set_add_constraint(csl
->bounds
, bound
);
953 isl_constraint_free(c
);
958 /* This functions performs essentially the same operation as
959 * constraint_stride_lower, the only difference being that the offset d
960 * is not a constant, but an affine expression in terms of the parameters
961 * and earlier variables. In particular the affine expression is equal
962 * to the coefficients of stride->constraint multiplied by stride->factor.
963 * As in constraint_stride_lower, we add an extra bound
965 * i + s * floor((f + a * d)/(a * s)) - d >= 0
967 * for each lower bound
971 * where d is not the aforementioned affine expression.
973 static int constraint_stride_lower_c(__isl_take isl_constraint
*c
, void *user
)
975 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
977 isl_constraint
*bound
;
978 isl_constraint
*csl_c
;
981 if (isl_constraint_is_equality(c
)) {
982 isl_constraint_free(c
);
986 v
= isl_constraint_get_coefficient_val(c
, isl_dim_set
, csl
->level
- 1);
987 if (!isl_val_is_pos(v
)) {
989 isl_constraint_free(c
);
994 csl_c
= cloog_constraint_to_isl(csl
->stride
->constraint
);
996 d
= isl_constraint_get_aff(csl_c
);
997 d
= isl_aff_drop_dims(d
, isl_dim_div
, 0, isl_aff_dim(d
, isl_dim_div
));
998 d
= isl_aff_set_coefficient_si(d
, isl_dim_in
, csl
->level
- 1, 0);
999 d
= isl_aff_scale_val(d
, cloog_int_to_isl_val(isl_constraint_get_ctx(csl_c
), csl
->stride
->factor
));
1001 b
= isl_constraint_get_bound(c
, isl_dim_set
, csl
->level
- 1);
1004 b
= isl_aff_add(b
, isl_aff_copy(d
));
1005 b
= isl_aff_scale_down_val(b
, cloog_int_to_isl_val(isl_constraint_get_ctx(csl_c
), csl
->stride
->stride
));
1006 b
= isl_aff_floor(b
);
1007 b
= isl_aff_scale_val(b
, cloog_int_to_isl_val(isl_constraint_get_ctx(csl_c
), csl
->stride
->stride
));
1008 b
= isl_aff_sub(b
, d
);
1009 b
= isl_aff_add_coefficient_si(b
, isl_dim_in
, csl
->level
- 1, 1);
1011 bound
= isl_inequality_from_aff(b
);
1013 csl
->bounds
= isl_basic_set_add_constraint(csl
->bounds
, bound
);
1016 isl_constraint_free(c
);
1021 static int basic_set_stride_lower(__isl_take isl_basic_set
*bset
, void *user
)
1023 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
1026 csl
->bounds
= isl_basic_set_universe(isl_basic_set_get_space(bset
));
1027 if (csl
->stride
->constraint
)
1028 r
= isl_basic_set_foreach_constraint(bset
,
1029 &constraint_stride_lower_c
, csl
);
1031 r
= isl_basic_set_foreach_constraint(bset
,
1032 &constraint_stride_lower
, csl
);
1033 bset
= isl_basic_set_intersect(bset
, csl
->bounds
);
1034 csl
->set
= isl_set_union(csl
->set
, isl_set_from_basic_set(bset
));
1040 * Update the lower bounds at level "level" to the given stride information.
1041 * That is, make sure that the remainder on division by "stride"
1042 * is equal to "offset".
1044 CloogDomain
*cloog_domain_stride_lower_bound(CloogDomain
*domain
, int level
,
1045 CloogStride
*stride
)
1047 struct cloog_stride_lower csl
;
1048 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1051 csl
.stride
= stride
;
1053 csl
.set
= isl_set_empty(isl_set_get_space(set
));
1055 r
= isl_set_foreach_basic_set(set
, basic_set_stride_lower
, &csl
);
1058 cloog_domain_free(domain
);
1059 return cloog_domain_from_isl_set(csl
.set
);
1063 /* Add stride constraint, if any, to domain.
1065 CloogDomain
*cloog_domain_add_stride_constraint(CloogDomain
*domain
,
1066 CloogStride
*stride
)
1071 if (!stride
|| !stride
->constraint
)
1074 set
= isl_set_from_cloog_domain(domain
);
1075 c
= isl_constraint_copy(cloog_constraint_to_isl(stride
->constraint
));
1077 set
= isl_set_add_constraint(set
, c
);
1079 return cloog_domain_from_isl_set(set
);
1084 * cloog_domain_lazy_equal function:
1085 * This function returns 1 if the domains given as input are the same, 0 if it
1086 * is unable to decide.
1088 int cloog_domain_lazy_equal(CloogDomain
*d1
, CloogDomain
*d2
)
1090 isl_set
*set1
= isl_set_from_cloog_domain(d1
);
1091 isl_set
*set2
= isl_set_from_cloog_domain(d2
);
1092 return isl_set_plain_is_equal(set1
, set2
);
1095 struct cloog_bound_split
{
1102 static int constraint_bound_split(__isl_take isl_constraint
*c
, void *user
)
1104 struct cloog_bound_split
*cbs
= (struct cloog_bound_split
*)user
;
1109 v
= isl_constraint_get_coefficient_val(c
, isl_dim_set
, cbs
->level
- 1);
1110 if (!cbs
->lower
&& isl_val_is_pos(v
))
1111 cbs
->lower
= handle
= 1;
1112 else if (!cbs
->upper
&& isl_val_is_neg(v
))
1113 cbs
->upper
= handle
= 1;
1116 for (i
= 0; i
< isl_set_dim(cbs
->set
, isl_dim_param
); ++i
) {
1118 v
= isl_constraint_get_coefficient_val(c
, isl_dim_param
, i
);
1119 if (isl_val_is_zero(v
))
1122 cbs
->set
= isl_set_split_dims(cbs
->set
,
1123 isl_dim_param
, i
, 1);
1128 isl_constraint_free(c
);
1129 return (cbs
->lower
&& cbs
->upper
) ? -1 : 0;
1132 static int basic_set_bound_split(__isl_take isl_basic_set
*bset
, void *user
)
1134 struct cloog_bound_split
*cbs
= (struct cloog_bound_split
*)user
;
1139 r
= isl_basic_set_foreach_constraint(bset
, constraint_bound_split
, cbs
);
1140 isl_basic_set_free(bset
);
1141 return ((!cbs
->lower
|| !cbs
->upper
) && r
< 0) ? -1 : 0;
1145 * Return a union of sets S_i such that the convex hull of "dom",
1146 * when intersected with one the sets S_i, will have an upper and
1147 * lower bound for the dimension at "level" (provided "dom" itself
1148 * has such bounds for the dimensions).
1150 * We currently take a very simple approach. For each of the basic
1151 * sets in "dom" we pick a lower and an upper bound and split the
1152 * range of any parameter involved in these two bounds in a
1153 * nonnegative and a negative part. This ensures that the symbolic
1154 * constant in these two constraints are themselves bounded and
1155 * so there will be at least one upper and one lower bound
1156 * in the convex hull.
1158 CloogDomain
*cloog_domain_bound_splitter(CloogDomain
*dom
, int level
)
1160 struct cloog_bound_split cbs
;
1161 isl_set
*set
= isl_set_from_cloog_domain(dom
);
1164 cbs
.set
= isl_set_universe(isl_set_get_space(set
));
1165 r
= isl_set_foreach_basic_set(set
, basic_set_bound_split
, &cbs
);
1167 return cloog_domain_from_isl_set(cbs
.set
);
1171 /* Check whether the union of scattering functions over all domains
1172 * is obviously injective.
1174 static int injective_scattering(CloogScatteringList
*list
)
1177 isl_union_map
*umap
;
1185 map
= isl_map_copy(isl_map_from_cloog_scattering(list
->scatt
));
1186 snprintf(name
, sizeof(name
), "S%d", i
);
1187 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
1188 umap
= isl_union_map_from_map(map
);
1190 for (list
= list
->next
, ++i
; list
; list
= list
->next
, ++i
) {
1191 map
= isl_map_copy(isl_map_from_cloog_scattering(list
->scatt
));
1192 snprintf(name
, sizeof(name
), "S%d", i
);
1193 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
1194 umap
= isl_union_map_add_map(umap
, map
);
1197 injective
= isl_union_map_plain_is_injective(umap
);
1199 isl_union_map_free(umap
);
1206 * cloog_scattering_lazy_block function:
1207 * This function returns 1 if the two scattering functions s1 and s2 given
1208 * as input are the same (except possibly for the final dimension, where we
1209 * allow a difference of 1), assuming that the domains on which this
1210 * scatterings are applied are the same.
1211 * In fact this function answers the question "can I
1212 * safely consider the two domains as only one with two statements (a block) ?".
1213 * A difference of 1 in the final dimension is only allowed if the
1214 * entire scattering function is injective.
1215 * - s1 and s2 are the two domains to check for blocking,
1216 * - scattering is the linked list of all domains,
1217 * - scattdims is the total number of scattering dimentions.
1219 int cloog_scattering_lazy_block(CloogScattering
*s1
, CloogScattering
*s2
,
1220 CloogScatteringList
*scattering
, int scattdims
)
1223 struct isl_space
*dim
;
1224 struct isl_map
*rel
;
1225 struct isl_set
*delta
;
1226 isl_map
*map1
= isl_map_from_cloog_scattering(s1
);
1227 isl_map
*map2
= isl_map_from_cloog_scattering(s2
);
1232 n_scat
= isl_map_dim(map1
, isl_dim_out
);
1233 if (n_scat
!= isl_map_dim(map2
, isl_dim_out
))
1236 dim
= isl_map_get_space(map1
);
1237 dim
= isl_space_map_from_set(isl_space_domain(dim
));
1238 rel
= isl_map_identity(dim
);
1239 rel
= isl_map_apply_domain(rel
, isl_map_copy(map1
));
1240 rel
= isl_map_apply_range(rel
, isl_map_copy(map2
));
1241 delta
= isl_map_deltas(rel
);
1243 for (i
= 0; i
< n_scat
; ++i
) {
1244 cst
= isl_set_plain_get_val_if_fixed(delta
, isl_dim_set
, i
);
1249 if (isl_val_is_zero(cst
)){
1253 if (i
+ 1 < n_scat
){
1257 if (!isl_val_is_one(cst
)){
1261 if (!injective_scattering(scattering
)){
1268 block
= i
>= n_scat
;
1269 isl_set_free(delta
);
1275 * cloog_domain_lazy_disjoint function:
1276 * This function returns 1 if the domains given as input are disjoint, 0 if it
1277 * is unable to decide.
1279 int cloog_domain_lazy_disjoint(CloogDomain
*d1
, CloogDomain
*d2
)
1281 isl_set
*set1
= isl_set_from_cloog_domain(d1
);
1282 isl_set
*set2
= isl_set_from_cloog_domain(d2
);
1283 return isl_set_plain_is_disjoint(set1
, set2
);
1288 * cloog_scattering_list_lazy_same function:
1289 * This function returns 1 if two domains in the list are the same, 0 if it
1290 * is unable to decide.
1292 int cloog_scattering_list_lazy_same(CloogScatteringList
*list
)
1294 CloogScatteringList
*one
, *other
;
1295 isl_map
*one_map
, *other_map
;
1297 for (one
= list
; one
; one
= one
->next
) {
1298 one_map
= isl_map_from_cloog_scattering(one
->scatt
);
1299 for (other
= one
->next
; other
; other
= other
->next
) {
1300 other_map
= isl_map_from_cloog_scattering(other
->scatt
);
1301 if (isl_map_plain_is_equal(one_map
, other_map
))
1308 int cloog_domain_dimension(CloogDomain
* domain
)
1310 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1311 return isl_set_dim(set
, isl_dim_set
);
1314 int cloog_domain_parameter_dimension(CloogDomain
*domain
)
1316 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1317 return isl_set_dim(set
, isl_dim_param
);
1320 int cloog_scattering_dimension(CloogScattering
*scatt
, CloogDomain
*domain
)
1322 isl_map
*map
= isl_map_from_cloog_scattering(scatt
);
1323 return isl_map_dim(map
, isl_dim_out
);
1326 int cloog_domain_isconvex(CloogDomain
* domain
)
1328 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1329 return isl_set_n_basic_set(set
) <= 1;
1334 * cloog_domain_cut_first function:
1335 * This function splits off and returns the first convex set in the
1336 * union "domain". The remainder of the union is returned in rest.
1337 * The original "domain" itself is destroyed and may not be used
1338 * after a call to this function.
1340 CloogDomain
*cloog_domain_cut_first(CloogDomain
*domain
, CloogDomain
**rest
)
1342 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1343 struct isl_basic_set
*first
;
1345 first
= isl_set_copy_basic_set(set
);
1346 set
= isl_set_drop_basic_set(set
, first
);
1347 *rest
= cloog_domain_from_isl_set(set
);
1349 return cloog_domain_from_isl_set(isl_set_from_basic_set(first
));
1354 * Given a union domain, try to find a simpler representation
1355 * using fewer sets in the union.
1356 * The original "domain" itself is destroyed and may not be used
1357 * after a call to this function.
1359 CloogDomain
*cloog_domain_simplify_union(CloogDomain
*domain
)
1361 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1362 return cloog_domain_from_isl_set(isl_set_coalesce(set
));
1367 * cloog_scattering_lazy_isscalar function:
1368 * this function returns 1 if the scattering dimension 'dimension' in the
1369 * scattering 'scatt' is constant.
1370 * If value is not NULL, then it is set to the constant value of dimension.
1372 int cloog_scattering_lazy_isscalar(CloogScattering
*scatt
, int dimension
,
1375 isl_map
*map
= isl_map_from_cloog_scattering(scatt
);
1376 isl_val
*v
= isl_map_plain_get_val_if_fixed(map
, isl_dim_out
, dimension
);
1378 if (!isl_val_is_nan(v
)){
1380 isl_val_to_cloog_int(v
, value
);
1396 * cloog_domain_lazy_isconstant function:
1397 * this function returns 1 if the dimension 'dimension' in the
1398 * domain 'domain' is constant.
1399 * If value is not NULL, then it is set to the constant value of dimension.
1401 int cloog_domain_lazy_isconstant(CloogDomain
*domain
, int dimension
,
1404 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1405 isl_val
*cst
= isl_set_plain_get_val_if_fixed(set
, isl_dim_set
, dimension
);
1407 if (!isl_val_is_nan(cst
)){
1409 isl_val_to_cloog_int(cst
, value
);
1425 * cloog_scattering_erase_dimension function:
1426 * this function returns a CloogDomain structure builds from 'domain' where
1427 * we removed the dimension 'dimension' and every constraint involving this
1430 CloogScattering
*cloog_scattering_erase_dimension(CloogScattering
*scattering
,
1433 isl_map
*map
= isl_map_from_cloog_scattering(scattering
);
1434 map
= isl_map_remove_dims(isl_map_copy(map
), isl_dim_out
, dimension
, 1);
1435 return cloog_scattering_from_isl_map(map
);
1439 * cloog_domain_cube:
1440 * Construct and return a dim-dimensional cube, with values ranging
1441 * between min and max in each dimension.
1443 CloogDomain
*cloog_domain_cube(CloogState
*state
,
1444 int dim
, cloog_int_t min
, cloog_int_t max
)
1453 return cloog_domain_universe(state
, dim
);
1455 space
= isl_space_set_alloc(state
->backend
->ctx
, 0, dim
);
1456 cube
= isl_set_universe(space
);
1457 for (i
= 0; i
< dim
; ++i
) {
1458 min_v
= cloog_int_to_isl_val(isl_set_get_ctx(cube
), min
);
1459 max_v
= cloog_int_to_isl_val(isl_set_get_ctx(cube
), max
);
1460 cube
= isl_set_lower_bound_val(cube
, isl_dim_set
, i
, min_v
);
1461 cube
= isl_set_upper_bound_val(cube
, isl_dim_set
, i
, max_v
);
1464 return cloog_domain_from_isl_set(cube
);
1469 * cloog_domain_scatter function:
1470 * This function add the scattering (scheduling) informations to a domain.
1472 CloogDomain
*cloog_domain_scatter(CloogDomain
*domain
, CloogScattering
*scatt
)
1474 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1475 isl_map
*map
= isl_map_from_cloog_scattering(scatt
);
1477 map
= isl_map_reverse(isl_map_copy(map
));
1478 map
= isl_map_intersect_range(map
, set
);
1479 set
= isl_set_flatten(isl_map_wrap(map
));
1480 return cloog_domain_from_isl_set(set
);
1483 static int add_domain_from_map(__isl_take isl_map
*map
, void *user
)
1487 CloogDomain
*domain
;
1488 CloogScattering
*scat
;
1489 CloogUnionDomain
**ud
= (CloogUnionDomain
**)user
;
1491 dim
= isl_map_get_space(map
);
1492 name
= isl_space_get_tuple_name(dim
, isl_dim_in
);
1493 domain
= cloog_domain_from_isl_set(isl_map_domain(isl_map_copy(map
)));
1494 scat
= cloog_scattering_from_isl_map(map
);
1495 *ud
= cloog_union_domain_add_domain(*ud
, name
, domain
, scat
, NULL
);
1496 isl_space_free(dim
);
1502 * Construct a CloogUnionDomain from an isl_union_map representing
1503 * a global scattering function. The input is a mapping from different
1504 * spaces (different tuple names and possibly different dimensions)
1505 * to a common space. The iteration domains are set to the domains
1506 * in each space. The statement names are set to the names of the
1507 * spaces. The parameter names of the result are set to those of
1508 * the input, but the iterator and scattering dimension names are
1511 CloogUnionDomain
*cloog_union_domain_from_isl_union_map(
1512 __isl_take isl_union_map
*umap
)
1517 CloogUnionDomain
*ud
;
1519 dim
= isl_union_map_get_space(umap
);
1520 nparam
= isl_space_dim(dim
, isl_dim_param
);
1522 ud
= cloog_union_domain_alloc(nparam
);
1524 for (i
= 0; i
< nparam
; ++i
) {
1525 const char *s
= isl_space_get_dim_name(dim
, isl_dim_param
, i
);
1526 ud
= cloog_union_domain_set_name(ud
, CLOOG_PARAM
, i
, s
);
1528 isl_space_free(dim
);
1530 if (isl_union_map_foreach_map(umap
, &add_domain_from_map
, &ud
) < 0) {
1531 isl_union_map_free(umap
);
1532 cloog_union_domain_free(ud
);
1536 isl_union_map_free(umap
);
1541 static int count_same_name(__isl_keep isl_space
*dim
,
1542 enum isl_dim_type type
, unsigned pos
, const char *name
)
1544 enum isl_dim_type t
;
1547 int len
= strlen(name
);
1549 for (t
= isl_dim_param
; t
<= type
&& t
<= isl_dim_out
; ++t
) {
1550 s
= t
== type
? pos
: isl_space_dim(dim
, t
);
1551 for (p
= 0; p
< s
; ++p
) {
1552 const char *n
= isl_space_get_dim_name(dim
, t
, p
);
1553 if (n
&& !strncmp(n
, name
, len
))
1560 static CloogUnionDomain
*add_domain(__isl_take isl_set
*set
, CloogUnionDomain
*ud
)
1567 CloogDomain
*domain
;
1569 ctx
= isl_set_get_ctx(set
);
1570 dim
= isl_set_get_space(set
);
1571 name
= isl_space_get_tuple_name(dim
, isl_dim_set
);
1572 set
= isl_set_flatten(set
);
1573 set
= isl_set_set_tuple_name(set
, NULL
);
1574 domain
= cloog_domain_from_isl_set(set
);
1575 ud
= cloog_union_domain_add_domain(ud
, name
, domain
, NULL
, NULL
);
1577 nvar
= isl_space_dim(dim
, isl_dim_set
);
1578 for (i
= 0; i
< nvar
; ++i
) {
1579 char *long_name
= NULL
;
1582 name
= isl_space_get_dim_name(dim
, isl_dim_set
, i
);
1584 snprintf(buffer
, sizeof(buffer
), "i%d", i
);
1587 n
= count_same_name(dim
, isl_dim_set
, i
, name
);
1589 int size
= strlen(name
) + 10;
1590 long_name
= isl_alloc_array(ctx
, char, size
);
1592 cloog_die("memory overflow.\n");
1593 snprintf(long_name
, size
, "%s_%d", name
, n
);
1596 ud
= cloog_union_domain_set_name(ud
, CLOOG_ITER
, i
, name
);
1599 isl_space_free(dim
);
1605 * Construct a CloogUnionDomain from an isl_set.
1606 * The statement names are set to the names of the
1607 * spaces. The parameter and iterator names of the result are set to those of
1608 * the input, but the scattering dimension names are left unspecified.
1610 CloogUnionDomain
*cloog_union_domain_from_isl_set(
1611 __isl_take isl_set
*set
)
1616 CloogUnionDomain
*ud
;
1618 dim
= isl_set_get_space(set
);
1619 nparam
= isl_space_dim(dim
, isl_dim_param
);
1621 ud
= cloog_union_domain_alloc(nparam
);
1623 for (i
= 0; i
< nparam
; ++i
) {
1624 const char *s
= isl_space_get_dim_name(dim
, isl_dim_param
, i
);
1625 ud
= cloog_union_domain_set_name(ud
, CLOOG_PARAM
, i
, s
);
1627 isl_space_free(dim
);
1629 ud
= add_domain(set
, ud
);
1634 /* Computes x, y and g such that g = gcd(a,b) and a*x+b*y = g */
1635 static void Euclid(cloog_int_t a
, cloog_int_t b
,
1636 cloog_int_t
*x
, cloog_int_t
*y
, cloog_int_t
*g
)
1638 cloog_int_t c
, d
, e
, f
, tmp
;
1644 cloog_int_init(tmp
);
1645 cloog_int_abs(c
, a
);
1646 cloog_int_abs(d
, b
);
1647 cloog_int_set_si(e
, 1);
1648 cloog_int_set_si(f
, 0);
1649 while (cloog_int_is_pos(d
)) {
1650 cloog_int_tdiv_q(tmp
, c
, d
);
1651 cloog_int_mul(tmp
, tmp
, f
);
1652 cloog_int_sub(e
, e
, tmp
);
1653 cloog_int_tdiv_q(tmp
, c
, d
);
1654 cloog_int_mul(tmp
, tmp
, d
);
1655 cloog_int_sub(c
, c
, tmp
);
1656 cloog_int_swap(c
, d
);
1657 cloog_int_swap(e
, f
);
1659 cloog_int_set(*g
, c
);
1660 if (cloog_int_is_zero(a
))
1661 cloog_int_set_si(*x
, 0);
1662 else if (cloog_int_is_pos(a
))
1663 cloog_int_set(*x
, e
);
1664 else cloog_int_neg(*x
, e
);
1665 if (cloog_int_is_zero(b
))
1666 cloog_int_set_si(*y
, 0);
1668 cloog_int_mul(tmp
, a
, *x
);
1669 cloog_int_sub(tmp
, c
, tmp
);
1670 cloog_int_divexact(*y
, tmp
, b
);
1676 cloog_int_clear(tmp
);
1679 /* Construct a CloogStride from the given constraint for the given level,
1681 * We first compute the gcd of the coefficients of the existentially
1682 * quantified variables and then remove any common factors it has
1683 * with the coefficient at the given level.
1684 * The result is the value of the stride and if it is not one,
1685 * then it is possible to construct a CloogStride.
1686 * The constraint leading to the stride is stored in the CloogStride
1687 * as well a value (factor) such that the product of this value
1688 * and the coefficient at the given level is equal to -1 modulo the stride.
1690 static CloogStride
*construct_stride(isl_constraint
*c
, int level
)
1693 isl_val
*v
, *m
, *gcd
, *stride
;
1694 isl_val
*v_copy
, *m_copy
, *gcd_copy
;
1695 cloog_int_t c_v
, c_m
, c_gcd
, c_stride
, c_factor
;
1697 isl_ctx
*ctx
= isl_constraint_get_ctx(c
);;
1702 v
= isl_constraint_get_coefficient_val(c
, isl_dim_set
, level
- 1);
1704 sign
= isl_val_sgn(v
);
1705 m
= isl_val_abs(v
); /* *takes* v. */
1707 gcd
= isl_val_int_from_si(ctx
, 0);
1708 n
= isl_constraint_dim(c
, isl_dim_div
);
1709 for (i
= 0; i
< n
; ++i
) {
1710 v
= isl_constraint_get_coefficient_val(c
, isl_dim_div
, i
);
1711 gcd
= isl_val_gcd(gcd
, v
);
1714 m_copy
= isl_val_copy(m
);
1715 gcd_copy
= isl_val_copy(gcd
);
1717 v
= isl_val_gcd(m
, gcd
);
1719 v_copy
= isl_val_copy(v
);
1720 gcd
= isl_val_copy(gcd_copy
);
1721 stride
= isl_val_div(gcd
, v
);
1723 if (isl_val_is_zero(stride
) || isl_val_is_one(stride
))
1726 cloog_int_init(c_m
);
1727 cloog_int_init(c_stride
);
1728 cloog_int_init(c_v
);
1729 cloog_int_init(c_gcd
);
1730 cloog_int_init(c_factor
);
1732 isl_val_to_cloog_int(m_copy
, &c_m
);
1733 isl_val_to_cloog_int(stride
, &c_stride
);
1734 isl_val_to_cloog_int(v_copy
, &c_v
);
1735 isl_val_to_cloog_int(gcd_copy
, &c_gcd
);
1737 Euclid(c_m
, c_stride
, &c_factor
, &c_v
, &c_gcd
);
1739 cloog_int_neg(c_factor
, c_factor
);
1741 c
= isl_constraint_copy(c
);
1742 s
= cloog_stride_alloc_from_constraint(c_stride
,
1743 cloog_constraint_from_isl_constraint(c
), c_factor
);
1746 cloog_int_clear(c_m
);
1747 cloog_int_clear(c_stride
);
1748 cloog_int_clear(c_v
);
1749 cloog_int_clear(c_gcd
);
1750 cloog_int_clear(c_factor
);
1753 isl_val_free(stride
);
1754 isl_val_free(gcd_copy
);
1755 isl_val_free(m_copy
);
1756 isl_val_free(v_copy
);
1761 struct cloog_isl_find_stride_data
{
1763 CloogStride
*stride
;
1766 /* Check if the given constraint can be used to derive
1767 * a stride on the iterator identified by data->level.
1768 * We first check that there are some existentially quantified variables
1769 * and that the coefficient at data->level is non-zero.
1770 * Then we call construct_stride for further checks and the actual
1771 * construction of the CloogStride.
1773 static int find_stride(__isl_take isl_constraint
*c
, void *user
)
1775 struct cloog_isl_find_stride_data
*data
;
1779 if (!isl_constraint_is_equality(c
)) {
1780 isl_constraint_free(c
);
1784 data
= (struct cloog_isl_find_stride_data
*)user
;
1787 isl_constraint_free(c
);
1791 n
= isl_constraint_dim(c
, isl_dim_div
);
1793 isl_constraint_free(c
);
1797 v
= isl_constraint_get_coefficient_val(c
, isl_dim_set
, data
->level
- 1);
1798 if (!isl_val_is_zero(v
))
1799 data
->stride
= construct_stride(c
, data
->level
);
1803 isl_constraint_free(c
);
1808 /* Check if the given list of domains has a common stride on the given level.
1809 * If so, return a pointer to a CloogStride object. If not, return NULL.
1811 * We project out all later variables, take the union and compute
1812 * the affine hull of the union. Then we check the (equality)
1813 * constraints in this affine hull for imposing a stride.
1815 CloogStride
*cloog_domain_list_stride(CloogDomainList
*list
, int level
)
1817 struct cloog_isl_find_stride_data data
= { level
, NULL
};
1824 set
= isl_set_from_cloog_domain(list
->domain
);
1825 n
= isl_set_dim(set
, isl_dim_set
) - first
;
1826 set
= isl_set_project_out(isl_set_copy(set
), isl_dim_set
, first
, n
);
1828 for (list
= list
->next
; list
; list
= list
->next
) {
1829 isl_set
*set_i
= isl_set_from_cloog_domain(list
->domain
);
1830 n
= isl_set_dim(set_i
, isl_dim_set
) - first
;
1831 set_i
= isl_set_project_out(isl_set_copy(set_i
),
1832 isl_dim_set
, first
, n
);
1833 set
= isl_set_union(set
, set_i
);
1835 aff
= isl_set_affine_hull(set
);
1837 r
= isl_basic_set_foreach_constraint(aff
, &find_stride
, &data
);
1840 isl_basic_set_free(aff
);
1845 struct cloog_can_unroll
{
1855 * Check if the given lower bound can be used for unrolling
1856 * and, if so, return the unrolling factor/trip count in *v.
1857 * If the lower bound involves any existentially quantified
1858 * variables, we currently punt.
1859 * Otherwise we compute the maximal value of (i - ceil(l) + 1),
1860 * with l the given lower bound and i the iterator identified by level.
1862 static int is_valid_unrolling_lower_bound(struct cloog_can_unroll
*ccu
,
1863 __isl_keep isl_constraint
*c
, isl_val
**v
)
1869 n_div
= isl_constraint_dim(c
, isl_dim_div
);
1870 if (isl_constraint_involves_dims(c
, isl_dim_div
, 0, n_div
))
1873 aff
= isl_constraint_get_bound(c
, isl_dim_set
, ccu
->level
- 1);
1874 aff
= isl_aff_ceil(aff
);
1875 aff
= isl_aff_neg(aff
);
1876 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, ccu
->level
- 1, 1);
1877 *v
= isl_set_max_val(ccu
->set
, aff
);
1880 if (!*v
|| isl_val_is_nan(*v
))
1881 cloog_die("Fail to decide about unrolling (cannot find max)");
1883 if (isl_val_is_infty(*v
) || isl_val_is_neginfty(*v
)){
1889 *v
= isl_val_add_ui(*v
, 1);
1895 /* Check if we can unroll based on the given constraint.
1896 * Only lower bounds can be used.
1897 * Record it if it turns out to be usable and if we haven't recorded
1898 * any other constraint already.
1900 static int constraint_can_unroll(__isl_take isl_constraint
*c
, void *user
)
1902 struct cloog_can_unroll
*ccu
= (struct cloog_can_unroll
*)user
;
1904 isl_val
*count
= NULL
;
1906 v
= isl_constraint_get_coefficient_val(c
, isl_dim_set
, ccu
->level
- 1);
1907 if (isl_val_is_pos(v
) &&
1908 is_valid_unrolling_lower_bound(ccu
, c
, &count
) &&
1909 (!ccu
->c
|| (isl_val_lt(count
, ccu
->n
))) ) {
1910 isl_constraint_free(ccu
->c
);
1911 ccu
->c
= isl_constraint_copy(c
);
1913 isl_val_free(ccu
->n
);
1914 ccu
->n
= isl_val_copy(count
);
1916 isl_val_free(count
);
1918 isl_constraint_free(c
);
1924 /* Check if we can unroll the domain at the current level.
1925 * If the domain is a union, we cannot. Otherwise, we check the
1928 static int basic_set_can_unroll(__isl_take isl_basic_set
*bset
, void *user
)
1930 struct cloog_can_unroll
*ccu
= (struct cloog_can_unroll
*)user
;
1933 if (ccu
->c
|| !ccu
->can_unroll
)
1934 ccu
->can_unroll
= 0;
1936 bset
= isl_basic_set_remove_redundancies(bset
);
1937 r
= isl_basic_set_foreach_constraint(bset
,
1938 &constraint_can_unroll
, ccu
);
1940 isl_basic_set_free(bset
);
1945 /* Check if we can unroll the given domain at the given level, and
1946 * if so, return the single lower bound in *lb and an upper bound
1947 * on the number of iterations in *n.
1948 * If we cannot unroll, return 0 and set *lb to NULL.
1950 * We can unroll, if we can identify a lower bound on level
1951 * such that the number of iterations is bounded by a constant.
1953 int cloog_domain_can_unroll(CloogDomain
*domain
, int level
, cloog_int_t
*n
,
1954 CloogConstraint
**lb
)
1956 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1957 isl_val
*v
= cloog_int_to_isl_val(isl_set_get_ctx(set
), *n
);
1958 struct cloog_can_unroll ccu
= { 1, level
, NULL
, set
, v
};
1962 r
= isl_set_foreach_basic_set(set
, &basic_set_can_unroll
, &ccu
);
1966 if (!ccu
.can_unroll
) {
1967 isl_constraint_free(ccu
.c
);
1971 *lb
= cloog_constraint_from_isl_constraint(ccu
.c
);
1973 isl_val_to_cloog_int(ccu
.n
, n
);
1974 /* Note: we have to free ccu.n and not v because v has been
1975 * freed and replaced in ccu during isl_set_foreach_basic_set
1977 isl_val_free(ccu
.n
);
1978 return ccu
.can_unroll
;
1982 /* Fix the iterator i at the given level to l + o,
1983 * where l is prescribed by the constraint lb and o is equal to offset.
1984 * In particular, if lb is the constraint
1988 * then l = ceil(f(j)/a).
1990 CloogDomain
*cloog_domain_fixed_offset(CloogDomain
*domain
,
1991 int level
, CloogConstraint
*lb
, cloog_int_t offset
)
1994 isl_set
*set
= isl_set_from_cloog_domain(domain
);
1995 isl_ctx
*ctx
= isl_set_get_ctx(set
);
1999 c
= cloog_constraint_to_isl(lb
);
2000 aff
= isl_constraint_get_bound(c
, isl_dim_set
, level
- 1);
2001 aff
= isl_aff_ceil(aff
);
2002 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, level
- 1, -1);
2003 aff
= isl_aff_add_constant_val(aff
, cloog_int_to_isl_val(ctx
, offset
));
2004 eq
= isl_equality_from_aff(aff
);
2005 set
= isl_set_add_constraint(set
, eq
);
2007 return cloog_domain_from_isl_set(set
);