6 #include <cloog/isl/cloog.h>
8 #include <isl_constraint.h>
11 CloogDomain
*cloog_domain_from_isl_set(struct isl_set
*set
)
13 set
= isl_set_detect_equalities(set
);
14 return (CloogDomain
*)set
;
17 CloogScattering
*cloog_scattering_from_isl_map(struct isl_map
*map
)
19 return (CloogScattering
*)map
;
24 * Returns true if each scattering dimension is defined in terms
25 * of the original iterators.
27 int cloog_scattering_fully_specified(CloogScattering
*scattering
,
30 return isl_map_is_single_valued(&scattering
->map
);
34 CloogConstraintSet
*cloog_domain_constraints(CloogDomain
*domain
)
36 assert(domain
->set
.n
== 1);
37 return cloog_constraint_set_from_isl_basic_set(
38 isl_basic_set_copy(domain
->set
.p
[0]));
42 void cloog_domain_print_constraints(FILE *foo
, CloogDomain
*domain
,
46 isl_set_print(&domain
->set
, foo
, 0, ISL_FORMAT_POLYLIB
);
48 assert(domain
->set
.n
== 1);
49 isl_basic_set_print(domain
->set
.p
[0], foo
,
50 0, NULL
, NULL
, ISL_FORMAT_POLYLIB
);
55 void cloog_scattering_print_constraints(FILE *foo
, CloogScattering
*scattering
,
59 isl_map_print(&scattering
->map
, foo
, 0, ISL_FORMAT_POLYLIB
);
61 assert(scattering
->map
.n
== 1);
62 isl_basic_map_print(scattering
->map
.p
[0], foo
,
63 0, NULL
, NULL
, ISL_FORMAT_POLYLIB
);
68 void cloog_domain_free(CloogDomain
* domain
)
70 isl_set_free(&domain
->set
);
74 void cloog_scattering_free(CloogScattering
*scatt
)
76 isl_map_free(&scatt
->map
);
80 CloogDomain
* cloog_domain_copy(CloogDomain
* domain
)
82 return cloog_domain_from_isl_set(isl_set_copy(&domain
->set
));
87 * cloog_domain_convex function:
88 * Computes the convex hull of domain.
90 CloogDomain
*cloog_domain_convex(CloogDomain
*domain
)
92 struct isl_set
*set
= &domain
->set
;
93 set
= isl_set_from_basic_set(isl_set_convex_hull(isl_set_copy(set
)));
94 return cloog_domain_from_isl_set(set
);
99 * cloog_domain_simple_convex:
100 * Given a list (union) of polyhedra, this function returns a "simple"
101 * convex hull of this union. In particular, the constraints of the
102 * the returned polyhedron consist of (parametric) lower and upper
103 * bounds on individual variables and constraints that appear in the
104 * original polyhedra.
106 CloogDomain
*cloog_domain_simple_convex(CloogDomain
*domain
)
108 struct isl_basic_set
*hull
;
109 unsigned dim
= isl_set_n_dim(&domain
->set
);
111 if (cloog_domain_isconvex(domain
))
112 return cloog_domain_copy(domain
);
115 return cloog_domain_convex(domain
);
117 hull
= isl_set_bounded_simple_hull(isl_set_copy(&domain
->set
));
118 return cloog_domain_from_isl_set(isl_set_from_basic_set(hull
));
123 * cloog_domain_simplify function:
124 * Given two polyhedral domains (dom1) and (dom2),
125 * this function finds the largest domain set (or the smallest list
126 * of non-redundant constraints), that when intersected with polyhedral
127 * domain (dom2) equals (dom1)intersect(dom2). The output is a new CloogDomain
128 * structure with a polyhedral domain with the "redundant" constraints removed.
129 * NB: the second domain is required not to be a union.
131 CloogDomain
*cloog_domain_simplify(CloogDomain
*dom1
, CloogDomain
*dom2
)
134 set
= isl_set_gist(isl_set_copy(&dom1
->set
), isl_set_copy(&dom2
->set
));
135 return cloog_domain_from_isl_set(set
);
140 * cloog_domain_union function:
141 * This function returns a new polyhedral domain which is the union of
142 * two polyhedral domains (dom1) U (dom2).
143 * Frees dom1 and dom2;
145 CloogDomain
*cloog_domain_union(CloogDomain
*dom1
, CloogDomain
*dom2
)
148 set
= isl_set_union(&dom1
->set
, &dom2
->set
);
149 return cloog_domain_from_isl_set(set
);
155 * cloog_domain_intersection function:
156 * This function returns a new polyhedral domain which is the intersection of
157 * two polyhedral domains (dom1) \cap (dom2).
159 CloogDomain
*cloog_domain_intersection(CloogDomain
*dom1
, CloogDomain
*dom2
)
162 set
= isl_set_intersect(isl_set_copy(&dom1
->set
),
163 isl_set_copy(&dom2
->set
));
164 return cloog_domain_from_isl_set(set
);
169 * cloog_domain_difference function:
170 * Returns the set difference domain \ minus.
172 CloogDomain
*cloog_domain_difference(CloogDomain
*domain
, CloogDomain
*minus
)
175 set
= isl_set_subtract(isl_set_copy(&domain
->set
),
176 isl_set_copy(&minus
->set
));
177 return cloog_domain_from_isl_set(set
);
182 * cloog_domain_sort function:
183 * This function topologically sorts (nb_doms) domains. Here (doms) is an
184 * array of pointers to CloogDomains, (nb_doms) is the number of domains,
185 * (level) is the level to consider for partial ordering (nb_par) is the
186 * parameter space dimension, (permut) if not NULL, is an array of (nb_doms)
187 * integers that contains a permutation specification after call in order to
188 * apply the topological sorting.
190 void cloog_domain_sort(CloogDomain
**doms
, unsigned nb_doms
, unsigned level
,
195 unsigned char **follows
;
199 ctx
= doms
[0]->set
.ctx
;
200 for (i
= 0; i
< nb_doms
; i
++)
201 assert(doms
[i
]->set
.n
== 1);
203 follows
= isl_alloc_array(ctx
, unsigned char *, nb_doms
);
205 for (i
= 0; i
< nb_doms
; ++i
) {
206 follows
[i
] = isl_alloc_array(ctx
, unsigned char, nb_doms
);
208 for (j
= 0; j
< nb_doms
; ++j
)
212 for (i
= 1; i
< nb_doms
; ++i
) {
213 for (j
= 0; j
< i
; ++j
) {
214 if (follows
[i
][j
] || follows
[j
][i
])
216 cmp
= isl_basic_set_compare_at(doms
[i
]->set
.p
[0],
217 doms
[j
]->set
.p
[0], level
-1);
222 for (k
= 0; k
< i
; ++k
)
223 follows
[i
][k
] |= follows
[j
][k
];
226 for (k
= 0; k
< i
; ++k
)
227 follows
[k
][i
] |= follows
[k
][j
];
232 for (i
= 0, j
= 0; i
< nb_doms
; j
= (j
+ 1) % nb_doms
) {
233 for (k
= 0; k
< nb_doms
; ++k
)
238 for (k
= 0; k
< nb_doms
; ++k
)
245 for (i
= 0; i
< nb_doms
; ++i
)
252 * Check whether there is or may be any value of dom1 at the given level
253 * that is greater than or equal to a value of dom2 at the same level.
256 * 1 is there is or may be a greater-than pair.
257 * 0 if there is no greater-than pair, but there may be an equal-to pair
258 * -1 if there is definitely no such pair
260 int cloog_domain_follows(CloogDomain
*dom1
, CloogDomain
*dom2
, unsigned level
)
264 follows
= isl_set_follows_at(&dom1
->set
, &dom2
->set
, level
- 1);
265 assert(follows
>= -1);
272 * cloog_domain_empty function:
273 * Returns an empty domain of the same dimensions as template.
275 CloogDomain
*cloog_domain_empty(CloogDomain
*template)
277 return cloog_domain_from_isl_set(isl_set_empty_like(&template->set
));
282 * Return 1 if the specified dimension has both an upper and a lower bound.
284 int cloog_domain_is_bounded(CloogDomain
*dom
, unsigned level
)
286 return isl_set_dim_is_bounded(&dom
->set
, isl_dim_set
, level
- 1);
290 /******************************************************************************
291 * Structure display function *
292 ******************************************************************************/
296 * cloog_domain_print_structure :
297 * this function is a more human-friendly way to display the CloogDomain data
298 * structure, it only shows the constraint system and includes an indentation
299 * level (level) in order to work with others print_structure functions.
301 void cloog_domain_print_structure(FILE *file
, CloogDomain
*domain
, int level
,
307 struct isl_set
*set
= &domain
->set
;
309 /* Go to the right level. */
310 for (i
= 0; i
< level
; i
++)
311 fprintf(file
, "|\t");
314 fprintf(file
, "+-- Null CloogDomain\n");
317 fprintf(file
, "+-- %s\n", name
);
318 prefix
= isl_alloc_array(set
->ctx
, char, 2*(level
+1)+3);
320 for (i
= 0; i
< level
+1; ++i
)
321 memcpy(prefix
+2*i
, "|\t", 2);
322 strcpy(prefix
+2*(level
+1), "[ ");
324 for (i
= 0; i
< set
->n
; ++i
) {
325 isl_basic_set_print(set
->p
[i
], file
, 0, prefix
, suffix
,
326 ISL_FORMAT_POLYLIB_CONSTRAINTS
);
327 prefix
[2*(level
+1)] = '\0';
328 fprintf(file
, "%s\n", prefix
);
329 prefix
[2*(level
+1)] = '[';
335 /******************************************************************************
336 * Memory deallocation function *
337 ******************************************************************************/
341 * cloog_scattering_list_free function:
342 * This function frees the allocated memory for a CloogScatteringList structure.
344 void cloog_scattering_list_free(CloogScatteringList
*list
)
346 while (list
!= NULL
) {
347 CloogScatteringList
*temp
= list
->next
;
348 isl_map_free(&list
->scatt
->map
);
355 /******************************************************************************
357 ******************************************************************************/
361 * cloog_domain_read_context function:
362 * Read parameter domain.
364 CloogDomain
*cloog_domain_read_context(CloogState
*state
, FILE *input
)
366 struct isl_ctx
*ctx
= state
->backend
->ctx
;
369 set
= isl_set_read_from_file(ctx
, input
, 0);
370 set
= isl_set_move_dims(set
, isl_dim_param
, 0,
371 isl_dim_set
, 0, isl_set_dim(set
, isl_dim_set
));
373 return cloog_domain_from_isl_set(set
);
378 * cloog_domain_from_context
379 * Reinterpret context by turning parameters into variables.
381 CloogDomain
*cloog_domain_from_context(CloogDomain
*context
)
383 isl_set
*set
= &context
->set
;
385 set
= isl_set_move_dims(set
, isl_dim_set
, 0,
386 isl_dim_param
, 0, isl_set_dim(set
, isl_dim_param
));
388 return cloog_domain_from_isl_set(set
);
393 * cloog_domain_union_read function:
394 * This function reads a union of polyhedra into a file (input) and
395 * returns a pointer to a CloogDomain containing the read information.
397 CloogDomain
*cloog_domain_union_read(CloogState
*state
,
398 FILE *input
, int nb_parameters
)
400 struct isl_ctx
*ctx
= state
->backend
->ctx
;
403 set
= isl_set_read_from_file(ctx
, input
, nb_parameters
);
404 return cloog_domain_from_isl_set(set
);
409 * cloog_domain_read_scattering function:
410 * This function reads in a scattering function from the file input.
412 * We try to read the scattering relation as a map, but if it is
413 * specified in the original PolyLib format, then isl_map_read_from_file
414 * will treat the input as a set return a map with zero input dimensions.
415 * In this case, we need to decompose the set into a map from
416 * scattering dimensions to domain dimensions and then invert the
419 CloogScattering
*cloog_domain_read_scattering(CloogDomain
*domain
, FILE *input
)
421 struct isl_ctx
*ctx
= domain
->set
.ctx
;
422 struct isl_map
*scat
;
427 dim
= isl_set_n_dim(&domain
->set
);
428 nparam
= isl_set_n_param(&domain
->set
);
429 scat
= isl_map_read_from_file(ctx
, input
, nparam
);
430 if (isl_map_dim(scat
, isl_dim_in
) != dim
) {
431 n_scat
= isl_map_dim(scat
, isl_dim_out
) - dim
;
432 scat
= isl_map_move_dims(scat
, isl_dim_in
, 0,
433 isl_dim_out
, n_scat
, dim
);
435 return cloog_scattering_from_isl_map(scat
);
438 /******************************************************************************
439 * CloogMatrix Reading function *
440 ******************************************************************************/
443 * isl_constraint_read_from_matrix:
444 * Convert a single line of a matrix to a isl_constraint.
445 * Returns a pointer to the constraint if successful; NULL otherwise.
447 static struct isl_constraint
*isl_constraint_read_from_matrix(
448 struct isl_dim
*dim
, cloog_int_t
*row
)
450 struct isl_constraint
*constraint
;
452 int nvariables
= isl_dim_size(dim
, isl_dim_set
);
453 int nparam
= isl_dim_size(dim
, isl_dim_param
);
455 if (cloog_int_is_zero(row
[0]))
456 constraint
= isl_equality_alloc(dim
);
458 constraint
= isl_inequality_alloc(dim
);
460 for (j
= 0; j
< nvariables
; ++j
)
461 isl_constraint_set_coefficient(constraint
, isl_dim_out
, j
,
464 for (j
= 0; j
< nparam
; ++j
)
465 isl_constraint_set_coefficient(constraint
, isl_dim_param
, j
,
466 row
[1 + nvariables
+ j
]);
468 isl_constraint_set_constant(constraint
, row
[1 + nvariables
+ nparam
]);
474 * isl_basic_set_read_from_matrix:
475 * Convert matrix to basic_set. The matrix contains nparam parameter columns.
476 * Returns a pointer to the basic_set if successful; NULL otherwise.
478 static struct isl_basic_set
*isl_basic_set_read_from_matrix(struct isl_ctx
*ctx
,
479 CloogMatrix
* matrix
, int nparam
)
482 struct isl_basic_set
*bset
;
484 unsigned nrows
, ncolumns
;
486 nrows
= matrix
->NbRows
;
487 ncolumns
= matrix
->NbColumns
;
488 int nvariables
= ncolumns
- 2 - nparam
;
490 dim
= isl_dim_set_alloc(ctx
, nparam
, nvariables
);
492 bset
= isl_basic_set_universe(isl_dim_copy(dim
));
494 for (i
= 0; i
< nrows
; ++i
) {
495 cloog_int_t
*row
= matrix
->p
[i
];
496 struct isl_constraint
*constraint
=
497 isl_constraint_read_from_matrix(isl_dim_copy(dim
), row
);
498 bset
= isl_basic_set_add_constraint(bset
, constraint
);
507 * cloog_domain_from_cloog_matrix:
508 * Create a CloogDomain containing the constraints described in matrix.
509 * nparam is the number of parameters contained in the domain.
510 * Returns a pointer to the CloogDomain if successful; NULL otherwise.
512 CloogDomain
*cloog_domain_from_cloog_matrix(CloogState
*state
,
513 CloogMatrix
*matrix
, int nparam
)
515 struct isl_ctx
*ctx
= state
->backend
->ctx
;
516 struct isl_basic_set
*bset
;
518 bset
= isl_basic_set_read_from_matrix(ctx
, matrix
, nparam
);
520 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset
));
524 * cloog_scattering_from_cloog_matrix:
525 * Create a CloogScattering containing the constraints described in matrix.
526 * nparam is the number of parameters contained in the domain.
527 * Returns a pointer to the CloogScattering if successful; NULL otherwise.
529 CloogScattering
*cloog_scattering_from_cloog_matrix(CloogState
*state
,
530 CloogMatrix
*matrix
, int nb_scat
, int nb_par
)
532 struct isl_ctx
*ctx
= state
->backend
->ctx
;
533 struct isl_basic_set
*bset
;
534 struct isl_basic_map
*scat
;
535 struct isl_dim
*dims
;
538 bset
= isl_basic_set_read_from_matrix(ctx
, matrix
, nb_par
);
539 dim
= isl_basic_set_n_dim(bset
) - nb_scat
;
540 dims
= isl_dim_alloc(ctx
, nb_par
, nb_scat
, dim
);
542 scat
= isl_basic_map_from_basic_set(bset
, dims
);
543 scat
= isl_basic_map_reverse(scat
);
544 return cloog_scattering_from_isl_map(isl_map_from_basic_map(scat
));
548 /******************************************************************************
549 * Processing functions *
550 ******************************************************************************/
555 * cloog_domain_isempty function:
557 int cloog_domain_isempty(CloogDomain
*domain
)
559 return isl_set_is_empty(&domain
->set
);
564 * cloog_domain_universe function:
565 * This function returns the complete dim-dimensional space.
567 CloogDomain
*cloog_domain_universe(CloogState
*state
, unsigned dim
)
569 struct isl_dim
*dims
;
570 struct isl_basic_set
*bset
;
572 dims
= isl_dim_set_alloc(state
->backend
->ctx
, 0, dim
);
573 bset
= isl_basic_set_universe(dims
);
574 return cloog_domain_from_isl_set(isl_set_from_basic_set(bset
));
579 * cloog_domain_project function:
580 * This function returns the projection of
581 * (domain) on the (level) first dimensions (i.e. outer loops).
583 CloogDomain
*cloog_domain_project(CloogDomain
*domain
, int level
)
585 struct isl_set
*set
= &domain
->set
;
586 set
= isl_set_remove_dims(isl_set_copy(set
),
587 level
, isl_set_n_dim(set
) - level
);
588 set
= isl_set_compute_divs(set
);
589 return cloog_domain_from_isl_set(set
);
594 * cloog_domain_extend function:
595 * This function returns the (domain) given as input with (dim)
596 * dimensions and (nb_par) parameters.
597 * This function does not free (domain), and returns a new CloogDomain.
599 CloogDomain
*cloog_domain_extend(CloogDomain
*domain
, int dim
)
601 struct isl_set
*set
= &domain
->set
;
602 set
= isl_set_extend(isl_set_copy(set
), isl_set_n_param(set
), dim
);
603 return cloog_domain_from_isl_set(set
);
608 * cloog_domain_never_integral function:
609 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0.
610 * There is no need to check for such constraints explicitly for the isl
613 int cloog_domain_never_integral(CloogDomain
* domain
)
615 return isl_set_is_empty(&domain
->set
);
620 * Check whether the loop at "level" is executed at most once.
621 * We construct a map that maps all remaining variables to this iterator
622 * and check whether this map is single valued.
624 * Alternatively, we could have mapped the domain through a mapping
625 * [p] -> { [..., i] -> [..., i'] : i' > i }
626 * and then taken the intersection of the original domain and the transformed
627 * domain. If this intersection is empty, then the corresponding
628 * loop is executed at most once.
630 int cloog_domain_is_otl(CloogDomain
*domain
, int level
)
635 map
= isl_map_from_domain(isl_set_copy(&domain
->set
));
636 map
= isl_map_move_dims(map
, isl_dim_out
, 0, isl_dim_in
, level
- 1, 1);
637 otl
= isl_map_is_single_valued(map
);
645 * cloog_domain_stride function:
646 * This function finds the stride imposed to unknown with the column number
647 * 'strided_level' in order to be integral. For instance, if we have a
648 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
649 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
650 * the unknown i. The function returns the imposed stride in a parameter field.
651 * - domain is the set of constraint we have to consider,
652 * - strided_level is the column number of the unknown for which a stride have
654 * - looking_level is the column number of the unknown that impose a stride to
656 * - stride is the stride that is returned back as a function parameter.
657 * - offset is the value of the constant c if the condition is of the shape
658 * (i + c)%s = 0, s being the stride.
660 void cloog_domain_stride(CloogDomain
*domain
, int strided_level
,
661 cloog_int_t
*stride
, cloog_int_t
*offset
)
663 struct isl_set
*set
= &domain
->set
;
664 isl_set_dim_residue_class(set
, strided_level
- 1, stride
, offset
);
665 if (!isl_int_is_zero(*offset
))
666 isl_int_sub(*offset
, *stride
, *offset
);
671 struct cloog_can_stride
{
676 static int constraint_can_stride(__isl_take isl_constraint
*c
, void *user
)
678 struct cloog_can_stride
*ccs
= (struct cloog_can_stride
*)user
;
684 isl_constraint_get_coefficient(c
, isl_dim_set
, ccs
->level
- 1, &v
);
685 if (isl_int_is_pos(v
)) {
686 n_div
= isl_constraint_dim(c
, isl_dim_div
);
687 for (i
= 0; i
< n_div
; ++i
) {
688 isl_constraint_get_coefficient(c
, isl_dim_div
, i
, &v
);
689 if (!isl_int_is_zero(v
))
696 isl_constraint_free(c
);
701 static int basic_set_can_stride(__isl_take isl_basic_set
*bset
, void *user
)
703 struct cloog_can_stride
*ccs
= (struct cloog_can_stride
*)user
;
706 r
= isl_basic_set_foreach_constraint(bset
, constraint_can_stride
, ccs
);
707 isl_basic_set_free(bset
);
713 * Return 1 if CLooG is allowed to perform stride detection on level "level"
715 * Currently, stride detection is only allowed when none of the lower
716 * bound constraints involve any existentially quantified variables.
717 * The reason is that the current isl interface does not make it
718 * easy to construct an integer division that depends on other integer
720 * By not allowing existentially quantified variables in the constraints,
721 * we can ignore them in cloog_domain_stride_lower_bound.
723 int cloog_domain_can_stride(CloogDomain
*domain
, int level
)
725 struct cloog_can_stride ccs
= { level
, 1 };
727 r
= isl_set_foreach_basic_set(&domain
->set
, basic_set_can_stride
, &ccs
);
729 return ccs
.can_stride
;
733 struct cloog_stride_lower
{
737 isl_basic_set
*bounds
;
740 /* If the given constraint is a lower bound on csl->level, then add
741 * a lower bound to csl->bounds that makes sure that the remainder
742 * of the smallest value on division by csl->stride is equal to csl->offset.
744 * In particular, the given lower bound is of the form
748 * where f may depend on the parameters and other iterators.
749 * The stride is s and the offset is d.
750 * The lower bound -f/a may not satisfy the above condition. In fact,
751 * it may not even be integral. We want to round this value of i up
752 * to the nearest value that satisfies the condition and add the corresponding
753 * lower bound constraint. This nearest value is obtained by rounding
754 * i - d up to the nearest multiple of s.
755 * That is, we first subtract d
759 * then we round up to the nearest multiple of s
761 * i'' = s * ceil(i'/s)
763 * and finally, we add d again
767 * and impose the constraint i >= i'''.
771 * i'' = s * ceil((-f - a * d)/(a * s)) = - s * floor((f + a * d)/(a * s))
773 * i >= - s * floor((f + a * d)/(a * s)) + d
776 * i + s * floor((f + a * d)/(a * s)) - d >= 0
778 static int constraint_stride_lower(__isl_take isl_constraint
*c
, void *user
)
780 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
784 isl_constraint
*bound
;
787 unsigned nparam
, nvar
;
790 isl_constraint_get_coefficient(c
, isl_dim_set
, csl
->level
- 1, &v
);
791 if (!isl_int_is_pos(v
)) {
793 isl_constraint_free(c
);
800 nparam
= isl_constraint_dim(c
, isl_dim_param
);
801 nvar
= isl_constraint_dim(c
, isl_dim_set
);
802 bound
= isl_inequality_alloc(isl_basic_set_get_dim(csl
->bounds
));
803 div
= isl_div_alloc(isl_basic_set_get_dim(csl
->bounds
));
804 isl_int_mul(t
, v
, csl
->stride
->stride
);
805 isl_div_set_denominator(div
, t
);
806 for (i
= 0; i
< nparam
; ++i
) {
807 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &t
);
808 isl_div_set_coefficient(div
, isl_dim_param
, i
, t
);
810 for (i
= 0; i
< nvar
; ++i
) {
811 if (i
== csl
->level
- 1)
813 isl_constraint_get_coefficient(c
, isl_dim_set
, i
, &t
);
814 isl_div_set_coefficient(div
, isl_dim_set
, i
, t
);
816 isl_constraint_get_constant(c
, &t
);
817 isl_int_addmul(t
, v
, csl
->stride
->offset
);
818 isl_div_set_constant(div
, t
);
820 bound
= isl_constraint_add_div(bound
, div
, &pos
);
821 isl_int_set_si(t
, 1);
822 isl_constraint_set_coefficient(bound
, isl_dim_set
,
824 isl_constraint_set_coefficient(bound
, isl_dim_div
, pos
,
825 csl
->stride
->stride
);
826 isl_int_neg(t
, csl
->stride
->offset
);
827 isl_constraint_set_constant(bound
, t
);
828 csl
->bounds
= isl_basic_set_add_constraint(csl
->bounds
, bound
);
832 isl_constraint_free(c
);
837 static int basic_set_stride_lower(__isl_take isl_basic_set
*bset
, void *user
)
839 struct cloog_stride_lower
*csl
= (struct cloog_stride_lower
*)user
;
842 csl
->bounds
= isl_basic_set_universe_like(bset
);
843 r
= isl_basic_set_foreach_constraint(bset
, constraint_stride_lower
, csl
);
844 bset
= isl_basic_set_intersect(bset
, csl
->bounds
);
845 csl
->set
= isl_set_union(csl
->set
, isl_set_from_basic_set(bset
));
851 * Update the lower bounds at level "level" to the given stride information.
852 * That is, make sure that the remainder on division by "stride"
853 * is equal to "offset".
855 CloogDomain
*cloog_domain_stride_lower_bound(CloogDomain
*domain
, int level
,
858 struct cloog_stride_lower csl
;
863 csl
.set
= isl_set_empty_like(&domain
->set
);
865 r
= isl_set_foreach_basic_set(&domain
->set
, basic_set_stride_lower
, &csl
);
868 cloog_domain_free(domain
);
869 return cloog_domain_from_isl_set(csl
.set
);
874 * cloog_domain_lazy_equal function:
875 * This function returns 1 if the domains given as input are the same, 0 if it
876 * is unable to decide.
878 int cloog_domain_lazy_equal(CloogDomain
*d1
, CloogDomain
*d2
)
880 return isl_set_fast_is_equal(&d1
->set
, &d2
->set
);
883 struct cloog_bound_split
{
890 static int constraint_bound_split(__isl_take isl_constraint
*c
, void *user
)
892 struct cloog_bound_split
*cbs
= (struct cloog_bound_split
*)user
;
898 isl_constraint_get_coefficient(c
, isl_dim_set
, cbs
->level
- 1, &v
);
899 if (!cbs
->lower
&& isl_int_is_pos(v
))
900 cbs
->lower
= handle
= 1;
901 else if (!cbs
->upper
&& isl_int_is_neg(v
))
902 cbs
->upper
= handle
= 1;
904 for (i
= 0; i
< isl_set_dim(cbs
->set
, isl_dim_param
); ++i
) {
905 isl_constraint_get_coefficient(c
, isl_dim_param
, i
, &v
);
906 if (isl_int_is_zero(v
))
908 cbs
->set
= isl_set_split_dims(cbs
->set
,
909 isl_dim_param
, i
, 1);
913 isl_constraint_free(c
);
915 return (cbs
->lower
&& cbs
->upper
) ? -1 : 0;
918 static int basic_set_bound_split(__isl_take isl_basic_set
*bset
, void *user
)
920 struct cloog_bound_split
*cbs
= (struct cloog_bound_split
*)user
;
925 r
= isl_basic_set_foreach_constraint(bset
, constraint_bound_split
, cbs
);
926 isl_basic_set_free(bset
);
927 return ((!cbs
->lower
|| !cbs
->upper
) && r
< 0) ? -1 : 0;
931 * Return a union of sets S_i such that the convex hull of "dom",
932 * when intersected with one the sets S_i, will have an upper and
933 * lower bound for the dimension at "level" (provided "dom" itself
934 * has such bounds for the dimensions).
936 * We currently take a very simple approach. For each of the basic
937 * sets in "dom" we pick a lower and an upper bound and split the
938 * range of any parameter involved in these two bounds in a
939 * nonnegative and a negative part. This ensures that the symbolic
940 * constant in these two constraints are themselves bounded and
941 * so there will be at least one upper and one lower bound
942 * in the convex hull.
944 CloogDomain
*cloog_domain_bound_splitter(CloogDomain
*dom
, int level
)
946 struct cloog_bound_split cbs
;
949 cbs
.set
= isl_set_universe_like(&dom
->set
);
950 r
= isl_set_foreach_basic_set(&dom
->set
, basic_set_bound_split
, &cbs
);
952 return cloog_domain_from_isl_set(cbs
.set
);
957 * cloog_scattering_lazy_block function:
958 * This function returns 1 if the two scattering functions s1 and s2 given
959 * as input are the same (except possibly for the final dimension, where we
960 * allow a difference of 1), assuming that the domains on which this
961 * scatterings are applied are the same.
962 * In fact this function answers the question "can I
963 * safely consider the two domains as only one with two statements (a block) ?".
964 * - s1 and s2 are the two domains to check for blocking,
965 * - scattering is the linked list of all domains,
966 * - scattdims is the total number of scattering dimentions.
968 int cloog_scattering_lazy_block(CloogScattering
*s1
, CloogScattering
*s2
,
969 CloogScatteringList
*scattering
, int scattdims
)
974 struct isl_set
*delta
;
979 n_scat
= isl_map_dim(&s1
->map
, isl_dim_out
);
980 if (n_scat
!= isl_map_dim(&s2
->map
, isl_dim_out
))
983 dim
= isl_dim_copy(s1
->map
.dim
);
984 dim
= isl_dim_domain(dim
);
985 rel
= isl_map_identity(dim
);
986 rel
= isl_map_apply_domain(rel
, isl_map_copy(&s1
->map
));
987 rel
= isl_map_apply_range(rel
, isl_map_copy(&s2
->map
));
988 delta
= isl_map_deltas(rel
);
990 for (i
= 0; i
< n_scat
; ++i
) {
991 fixed
= isl_set_fast_dim_is_fixed(delta
, i
, &cst
);
994 if (i
+1 < n_scat
&& !isl_int_is_zero(cst
))
996 if (!isl_int_is_zero(cst
) && !isl_int_is_one(cst
))
1001 isl_set_free(delta
);
1007 * cloog_domain_lazy_disjoint function:
1008 * This function returns 1 if the domains given as input are disjoint, 0 if it
1009 * is unable to decide.
1011 int cloog_domain_lazy_disjoint(CloogDomain
*d1
, CloogDomain
*d2
)
1013 return isl_set_fast_is_disjoint(&d1
->set
, &d2
->set
);
1018 * cloog_scattering_list_lazy_same function:
1019 * This function returns 1 if two domains in the list are the same, 0 if it
1020 * is unable to decide.
1022 int cloog_scattering_list_lazy_same(CloogScatteringList
*list
)
1024 CloogScatteringList
*one
, *other
;
1026 for (one
= list
; one
; one
= one
->next
)
1027 for (other
= one
->next
; other
; other
= other
->next
)
1028 if (isl_map_fast_is_equal(&one
->scatt
->map
,
1029 &other
->scatt
->map
))
1034 int cloog_domain_dimension(CloogDomain
* domain
)
1036 return isl_set_n_dim(&domain
->set
);
1039 int cloog_domain_parameter_dimension(CloogDomain
*domain
)
1041 return isl_set_n_param(&domain
->set
);
1044 int cloog_scattering_dimension(CloogScattering
*scatt
, CloogDomain
*domain
)
1046 return isl_map_dim(&scatt
->map
, isl_dim_out
);
1049 int cloog_domain_isconvex(CloogDomain
* domain
)
1051 return domain
->set
.n
<= 1;
1056 * cloog_domain_cut_first function:
1057 * This function splits off and returns the first convex set in the
1058 * union "domain". The remainder of the union is returned in rest.
1059 * The original "domain" itself is destroyed and may not be used
1060 * after a call to this function.
1062 CloogDomain
*cloog_domain_cut_first(CloogDomain
*domain
, CloogDomain
**rest
)
1064 struct isl_set
*set
;
1065 struct isl_basic_set
*first
;
1068 first
= isl_set_copy_basic_set(set
);
1069 set
= isl_set_drop_basic_set(set
, first
);
1070 *rest
= cloog_domain_from_isl_set(set
);
1072 return cloog_domain_from_isl_set(isl_set_from_basic_set(first
));
1077 * Given a union domain, try to find a simpler representation
1078 * using fewer sets in the union.
1079 * The original "domain" itself is destroyed and may not be used
1080 * after a call to this function.
1082 CloogDomain
*cloog_domain_simplify_union(CloogDomain
*domain
)
1084 return cloog_domain_from_isl_set(isl_set_coalesce(&domain
->set
));
1089 * cloog_scattering_lazy_isscalar function:
1090 * this function returns 1 if the scattering dimension 'dimension' in the
1091 * scattering 'scatt' is constant.
1092 * If value is not NULL, then it is set to the constant value of dimension.
1094 int cloog_scattering_lazy_isscalar(CloogScattering
*scatt
, int dimension
,
1097 return isl_map_fast_is_fixed(&scatt
->map
, isl_dim_out
, dimension
, value
);
1102 * cloog_domain_lazy_isconstant function:
1103 * this function returns 1 if the dimension 'dimension' in the
1104 * domain 'domain' is constant.
1105 * If value is not NULL, then it is set to the constant value of dimension.
1107 int cloog_domain_lazy_isconstant(CloogDomain
*domain
, int dimension
)
1109 return isl_set_fast_dim_is_fixed(&domain
->set
, dimension
, NULL
);
1114 * cloog_scattering_erase_dimension function:
1115 * this function returns a CloogDomain structure builds from 'domain' where
1116 * we removed the dimension 'dimension' and every constraint involving this
1119 CloogScattering
*cloog_scattering_erase_dimension(CloogScattering
*domain
,
1122 struct isl_map
*map
;
1123 map
= isl_map_remove(isl_map_copy(&domain
->map
), isl_dim_out
, dimension
, 1);
1124 return cloog_scattering_from_isl_map(map
);
1128 * cloog_domain_cube:
1129 * Construct and return a dim-dimensional cube, with values ranging
1130 * between min and max in each dimension.
1132 CloogDomain
*cloog_domain_cube(CloogState
*state
,
1133 int dim
, cloog_int_t min
, cloog_int_t max
)
1136 struct isl_basic_set
*cube
;
1137 struct isl_basic_set
*interval
;
1138 struct isl_basic_set_list
*list
;
1141 return cloog_domain_universe(state
, dim
);
1143 interval
= isl_basic_set_interval(state
->backend
->ctx
, min
, max
);
1144 list
= isl_basic_set_list_alloc(state
->backend
->ctx
, dim
);
1145 for (i
= 0; i
< dim
; ++i
)
1146 list
= isl_basic_set_list_add(list
, isl_basic_set_copy(interval
));
1147 isl_basic_set_free(interval
);
1148 cube
= isl_basic_set_product(list
);
1149 return cloog_domain_from_isl_set(isl_set_from_basic_set(cube
));
1154 * cloog_domain_scatter function:
1155 * This function add the scattering (scheduling) informations to a domain.
1157 CloogDomain
*cloog_domain_scatter(CloogDomain
*domain
, CloogScattering
*scatt
)
1159 struct isl_map
*map
;
1161 map
= isl_map_reverse(isl_map_copy(&scatt
->map
));
1162 map
= isl_map_intersect_range(map
, &domain
->set
);
1163 return cloog_domain_from_isl_set(isl_set_from_map(map
));
1166 static int add_domain_from_map(__isl_take isl_map
*map
, void *user
)
1170 CloogDomain
*domain
;
1171 CloogScattering
*scat
;
1172 CloogUnionDomain
**ud
= (CloogUnionDomain
**)user
;
1174 dim
= isl_map_get_dim(map
);
1175 name
= isl_dim_get_tuple_name(dim
, isl_dim_in
);
1176 domain
= cloog_domain_from_isl_set(isl_map_domain(isl_map_copy(map
)));
1177 scat
= cloog_scattering_from_isl_map(map
);
1178 *ud
= cloog_union_domain_add_domain(*ud
, name
, domain
, scat
, NULL
);
1185 * Construct a CloogUnionDomain from an isl_union_map representing
1186 * a global scattering function. The input is a mapping from different
1187 * spaces (different tuple names and possibly different dimensions)
1188 * to a common space. The iteration domains are set to the domains
1189 * in each space. The statement names are set to the names of the
1190 * spaces. The parameter names of the result are set to those of
1191 * the input, but the iterator and scattering dimension names are
1194 CloogUnionDomain
*cloog_union_domain_from_isl_union_map(
1195 __isl_take isl_union_map
*umap
)
1200 CloogUnionDomain
*ud
;
1202 dim
= isl_union_map_get_dim(umap
);
1203 nparam
= isl_dim_size(dim
, isl_dim_param
);
1205 ud
= cloog_union_domain_alloc(nparam
);
1207 for (i
= 0; i
< nparam
; ++i
) {
1208 const char *s
= isl_dim_get_name(dim
, isl_dim_param
, i
);
1209 ud
= cloog_union_domain_set_name(ud
, CLOOG_PARAM
, i
, s
);
1213 if (isl_union_map_foreach_map(umap
, &add_domain_from_map
, &ud
) < 0) {
1214 isl_union_map_free(umap
);
1215 cloog_union_domain_free(ud
);
1219 isl_union_map_free(umap
);
1224 static int add_domain(__isl_take isl_set
*set
, void *user
)
1228 CloogDomain
*domain
;
1229 CloogUnionDomain
**ud
= (CloogUnionDomain
**)user
;
1231 dim
= isl_set_get_dim(set
);
1232 name
= isl_dim_get_tuple_name(dim
, isl_dim_in
);
1233 domain
= cloog_domain_from_isl_set(set
);
1234 *ud
= cloog_union_domain_add_domain(*ud
, name
, domain
, NULL
, NULL
);
1241 * Construct a CloogUnionDomain from an isl_union_set.
1242 * The statement names are set to the names of the
1243 * spaces. The parameter names of the result are set to those of
1244 * the input, but the iterator and scattering dimension names are
1247 CloogUnionDomain
*cloog_union_domain_from_isl_union_set(
1248 __isl_take isl_union_set
*uset
)
1253 CloogUnionDomain
*ud
;
1255 dim
= isl_union_set_get_dim(uset
);
1256 nparam
= isl_dim_size(dim
, isl_dim_param
);
1258 ud
= cloog_union_domain_alloc(nparam
);
1260 for (i
= 0; i
< nparam
; ++i
) {
1261 const char *s
= isl_dim_get_name(dim
, isl_dim_param
, i
);
1262 ud
= cloog_union_domain_set_name(ud
, CLOOG_PARAM
, i
, s
);
1266 if (isl_union_set_foreach_set(uset
, &add_domain
, &ud
) < 0) {
1267 isl_union_set_free(uset
);
1268 cloog_union_domain_free(ud
);
1272 isl_union_set_free(uset
);