6 #include <cloog/isl/cloog.h>
12 /******************************************************************************
13 * Memory leaks hunting *
14 ******************************************************************************/
18 * These global variables are devoted to memory leaks hunting in the PolyLib
19 * backend. The isl backend has its own memory leak detection facilities.
21 int cloog_domain_allocated
= 0;
22 int cloog_domain_freed
= 0;
23 int cloog_domain_max
= 0;
28 * Returns true if each scattering dimension is defined in terms
29 * of the original iterators.
31 int cloog_scattering_fully_specified(CloogScattering
*scattering
,
35 int scattering_dim
= cloog_scattering_dimension(scattering
, domain
);
36 for (i
= 0; i
< scattering
->n
; ++i
)
37 if (scattering
->p
[i
]->n_eq
< scattering_dim
)
43 CloogConstraintSet
*cloog_domain_constraints(CloogDomain
*domain
)
45 assert(domain
->n
== 1);
46 return isl_basic_set_copy(domain
->p
[0]);
50 void cloog_domain_print_constraints(FILE *foo
, CloogDomain
*domain
,
54 isl_set_print(domain
, foo
, 0, ISL_FORMAT_POLYLIB
);
56 assert(domain
->n
== 1);
57 isl_basic_set_print(domain
->p
[0], foo
,
58 0, NULL
, NULL
, ISL_FORMAT_POLYLIB
);
63 void cloog_domain_free(CloogDomain
* domain
)
69 void cloog_scattering_free(CloogScattering
* domain
)
75 CloogDomain
* cloog_domain_copy(CloogDomain
* domain
)
77 return isl_set_copy(domain
);
82 * cloog_domain_convex function:
83 * Computes the convex hull of domain.
85 CloogDomain
*cloog_domain_convex(CloogDomain
*domain
)
87 return isl_set_from_basic_set(isl_set_convex_hull(isl_set_copy(domain
)));
92 * cloog_domain_simple_convex:
93 * Given a list (union) of polyhedra, this function returns a "simple"
94 * convex hull of this union. In particular, the constraints of the
95 * the returned polyhedron consist of (parametric) lower and upper
96 * bounds on individual variables and constraints that appear in the
99 * nb_par is the number of parameters of the domain.
101 CloogDomain
*cloog_domain_simple_convex(CloogDomain
*domain
, int nb_par
)
103 struct isl_basic_set
*hull
;
104 unsigned dim
= isl_set_n_dim(domain
);
106 if (cloog_domain_isconvex(domain
))
107 return cloog_domain_copy(domain
);
110 return cloog_domain_convex(domain
);
112 hull
= isl_set_bounded_simple_hull(isl_set_copy(domain
));
113 return isl_set_from_basic_set(hull
);
118 * cloog_domain_simplify function:
119 * Given two polyhedral domains (dom1) and (dom2),
120 * this function finds the largest domain set (or the smallest list
121 * of non-redundant constraints), that when intersected with polyhedral
122 * domain (dom2) equals (dom1)intersect(dom2). The output is a new CloogDomain
123 * structure with a polyhedral domain with the "redundant" constraints removed.
124 * NB: the second domain is required not to be a union.
126 CloogDomain
*cloog_domain_simplify(CloogDomain
*dom1
, CloogDomain
*dom2
)
128 assert(dom2
->n
== 1);
129 return isl_set_gist(isl_set_copy(dom1
),
130 isl_basic_set_copy(dom2
->p
[0]));
135 * cloog_domain_union function:
136 * This function returns a new polyhedral domain which is the union of
137 * two polyhedral domains (dom1) U (dom2).
139 CloogDomain
*cloog_domain_union(CloogDomain
*dom1
, CloogDomain
*dom2
)
141 return isl_set_union(isl_set_copy(dom1
), isl_set_copy(dom2
));
147 * cloog_domain_intersection function:
148 * This function returns a new polyhedral domain which is the intersection of
149 * two polyhedral domains (dom1) \cap (dom2).
151 CloogDomain
*cloog_domain_intersection(CloogDomain
*dom1
, CloogDomain
*dom2
)
153 return isl_set_intersect(isl_set_copy(dom1
), isl_set_copy(dom2
));
158 * cloog_domain_difference function:
159 * Returns the set difference domain \ minus.
161 CloogDomain
*cloog_domain_difference(CloogDomain
*domain
, CloogDomain
*minus
)
163 return isl_set_subtract(isl_set_copy(domain
), isl_set_copy(minus
));
168 * cloog_domain_sort function:
169 * This function topologically sorts (nb_doms) domains. Here (doms) is a an
170 * array of pointers to CloogDomains, (nb_doms) is the number of domains,
171 * (level) is the level to consider for partial ordering (nb_par) is the
172 * parameter space dimension, (permut) if not NULL, is an array of (nb_doms)
173 * integers that contains a permutation specification after call in order to
174 * apply the topological sorting.
176 void cloog_domain_sort(CloogDomain
**doms
, unsigned nb_doms
, unsigned level
,
177 unsigned nb_par
, int *permut
)
181 unsigned char **follows
;
186 for (i
= 0; i
< nb_doms
; i
++)
187 assert(doms
[i
]->n
== 1);
189 follows
= isl_alloc_array(ctx
, unsigned char *, nb_doms
);
191 for (i
= 0; i
< nb_doms
; ++i
) {
192 follows
[i
] = isl_alloc_array(ctx
, unsigned char, nb_doms
);
194 for (j
= 0; j
< nb_doms
; ++j
)
198 for (i
= 1; i
< nb_doms
; ++i
) {
199 for (j
= 0; j
< i
; ++j
) {
200 if (follows
[i
][j
] || follows
[j
][i
])
202 cmp
= isl_basic_set_compare_at(doms
[i
]->p
[0],
203 doms
[j
]->p
[0], level
-1);
208 for (k
= 0; k
< i
; ++k
)
209 follows
[i
][k
] |= follows
[j
][k
];
212 for (k
= 0; k
< i
; ++k
)
213 follows
[k
][i
] |= follows
[k
][j
];
218 for (i
= 0, j
= 0; i
< nb_doms
; j
= (j
+ 1) % nb_doms
) {
219 for (k
= 0; k
< nb_doms
; ++k
)
224 for (k
= 0; k
< nb_doms
; ++k
)
231 for (i
= 0; i
< nb_doms
; ++i
)
238 * cloog_domain_empty function:
239 * Returns an empty domain of the same dimensions as template.
241 CloogDomain
*cloog_domain_empty(CloogDomain
*template)
243 return isl_set_empty_like(template);
247 /******************************************************************************
248 * Structure display function *
249 ******************************************************************************/
253 * cloog_domain_print_structure :
254 * this function is a more human-friendly way to display the CloogDomain data
255 * structure, it only shows the constraint system and includes an indentation
256 * level (level) in order to work with others print_structure functions.
258 void cloog_domain_print_structure(FILE *file
, CloogDomain
*domain
, int level
,
265 /* Go to the right level. */
266 for (i
= 0; i
< level
; i
++)
267 fprintf(file
, "|\t");
270 fprintf(file
, "+-- Null CloogDomain\n");
273 fprintf(file
, "+-- %s\n", name
);
274 prefix
= isl_alloc_array(domain
->ctx
, char, 2*(level
+1)+3);
276 for (i
= 0; i
< level
+1; ++i
)
277 memcpy(prefix
+2*i
, "|\t", 2);
278 strcpy(prefix
+2*(level
+1), "[ ");
280 for (i
= 0; i
< domain
->n
; ++i
) {
281 isl_basic_set_print(domain
->p
[i
], file
, 0, prefix
, suffix
,
282 ISL_FORMAT_POLYLIB_CONSTRAINTS
);
283 prefix
[2*(level
+1)] = '\0';
284 fprintf(file
, "%s\n", prefix
);
285 prefix
[2*(level
+1)] = '[';
291 /******************************************************************************
292 * Memory deallocation function *
293 ******************************************************************************/
297 * cloog_scattering_list_free function:
298 * This function frees the allocated memory for a CloogScatteringList structure.
300 void cloog_scattering_list_free(CloogScatteringList
*list
)
302 while (list
!= NULL
) {
303 CloogScatteringList
*temp
= list
->next
;
304 isl_map_free(list
->scatt
);
311 /******************************************************************************
313 ******************************************************************************/
317 * cloog_domain_read_context function:
318 * Read parameter domain.
320 CloogDomain
*cloog_domain_read_context(FILE *input
, CloogOptions
*options
)
322 struct isl_ctx
*ctx
= options
->backend
->ctx
;
323 struct isl_dim
*param_dim
;
324 struct isl_basic_set
*bset
;
325 struct isl_basic_set
*model
;
327 bset
= isl_basic_set_read_from_file(ctx
, input
, 0, ISL_FORMAT_POLYLIB
);
329 param_dim
= isl_dim_set_alloc(ctx
, isl_basic_set_n_dim(bset
), 0);
330 model
= isl_basic_set_empty(param_dim
);
331 bset
= isl_basic_set_from_underlying_set(bset
, model
);
333 return isl_set_from_basic_set(bset
);
338 * cloog_domain_from_context
339 * Reinterpret context by turning parameters into variables.
341 CloogDomain
*cloog_domain_from_context(CloogDomain
*context
)
344 struct isl_basic_set
*model
;
346 dim
= isl_dim_set_alloc(context
->ctx
, 0, isl_set_n_param(context
));
347 model
= isl_basic_set_empty(dim
);
348 context
= isl_set_to_underlying_set(context
);
349 return isl_set_from_underlying_set(context
, model
);
354 * cloog_domain_union_read function:
355 * This function reads a union of polyhedra into a file (input) and
356 * returns a pointer to a CloogDomain containing the read information.
358 CloogDomain
*cloog_domain_union_read(FILE *input
, int nb_parameters
,
359 CloogOptions
*options
)
361 struct isl_ctx
*ctx
= options
->backend
->ctx
;
364 set
= isl_set_read_from_file(ctx
, input
, nb_parameters
,
371 * cloog_scattering_list_read function:
372 * This function reads in a scattering function from the file input.
374 CloogScattering
*cloog_scattering_read(FILE *input
,
375 CloogDomain
*domain
, CloogOptions
*options
)
377 struct isl_ctx
*ctx
= options
->backend
->ctx
;
378 struct isl_basic_set
*bset
;
379 struct isl_basic_map
*scat
;
380 struct isl_dim
*dims
;
385 nparam
= isl_set_n_param(domain
);
386 bset
= isl_basic_set_read_from_file(ctx
, input
, nparam
,
388 dim
= isl_set_n_dim(domain
);
389 n_scat
= isl_basic_set_n_dim(bset
) - dim
;
390 dims
= isl_dim_alloc(ctx
, nparam
, n_scat
, dim
);
391 scat
= isl_basic_map_from_basic_set(bset
, dims
);
392 return isl_map_from_basic_map(scat
);
396 /******************************************************************************
397 * Processing functions *
398 ******************************************************************************/
403 * cloog_domain_isempty function:
405 int cloog_domain_isempty(CloogDomain
*domain
)
407 return isl_set_is_empty(domain
);
412 * cloog_domain_universe function:
413 * This function returns the complete dim-dimensional space.
415 CloogDomain
*cloog_domain_universe(unsigned dim
, CloogOptions
*options
)
417 struct isl_dim
*dims
;
418 struct isl_basic_set
*bset
;
420 dims
= isl_dim_set_alloc(options
->backend
->ctx
, 0, dim
);
421 bset
= isl_basic_set_universe(dims
);
422 return isl_set_from_basic_set(bset
);
427 * cloog_domain_project function:
428 * This function returns the projection of
429 * (domain) on the (level) first dimensions (i.e. outer loops).
431 CloogDomain
*cloog_domain_project(CloogDomain
*domain
, int level
, int nb_par
)
433 return isl_set_remove_dims(isl_set_copy(domain
),
434 level
, isl_set_n_dim(domain
) - level
);
439 * cloog_domain_extend function:
440 * This function returns the (domain) given as input with (dim)
441 * dimensions and (nb_par) parameters.
442 * This function does not free (domain), and returns a new CloogDomain.
444 CloogDomain
*cloog_domain_extend(CloogDomain
*domain
, int dim
, int nb_par
)
446 return isl_set_extend(isl_set_copy(domain
), nb_par
, dim
);
451 * cloog_domain_never_integral function:
452 * For us, an equality like 3*i -4 = 0 is always false since 4%3 != 0.
453 * There is no need to check for such constraints explicitly for the isl
456 int cloog_domain_never_integral(CloogDomain
* domain
)
458 return isl_set_is_empty(domain
);
463 * cloog_domain_stride function:
464 * This function finds the stride imposed to unknown with the column number
465 * 'strided_level' in order to be integral. For instance, if we have a
466 * constraint like -i - 2j + 2k = 0, and we consider k, then k can be integral
467 * only if (i + 2j)%2 = 0. Then only if i%2 = 0. Then k imposes a stride 2 to
468 * the unknown i. The function returns the imposed stride in a parameter field.
469 * - domain is the set of constraint we have to consider,
470 * - strided_level is the column number of the unknown for which a stride have
472 * - looking_level is the column number of the unknown that impose a stride to
474 * - stride is the stride that is returned back as a function parameter.
475 * - offset is the value of the constant c if the condition is of the shape
476 * (i + c)%s = 0, s being the stride.
478 void cloog_domain_stride(CloogDomain
*domain
, int strided_level
, int nb_par
,
479 cloog_int_t
*stride
, cloog_int_t
*offset
)
481 assert(domain
->n
== 1);
482 isl_basic_set_dim_residue_class(domain
->p
[0], strided_level
-1,
484 if (!isl_int_is_zero(*offset
))
485 isl_int_sub(*offset
, *stride
, *offset
);
491 * cloog_domain_integral_lowerbound function:
492 * This function returns 1 if the lower bound of an iterator (such as its
493 * column rank in the constraint set 'domain' is 'level') is integral,
494 * 0 otherwise. If the lower bound is actually integral, the function fills
495 * the 'lower' field with the lower bound value.
497 int cloog_domain_integral_lowerbound(CloogDomain
*domain
, int level
,
500 return isl_set_fast_dim_has_fixed_lower_bound(domain
, level
-1, lower
);
505 * cloog_domain_lowerbound_update function:
506 * This function updates the integral lower bound of an iterator (such as its
507 * column rank in the constraint set 'domain' is 'level') into 'lower'
508 * and returns the updated domain.
510 CloogDomain
*cloog_domain_lowerbound_update(CloogDomain
*domain
, int level
,
513 return isl_set_lower_bound_dim(domain
, level
-1, lower
);
518 * cloog_domain_lazy_equal function:
519 * This function returns 1 if the domains given as input are the same, 0 if it
520 * is unable to decide.
522 int cloog_domain_lazy_equal(CloogDomain
*d1
, CloogDomain
*d2
)
524 return isl_set_fast_is_equal(d1
, d2
);
529 * cloog_scattering_lazy_block function:
530 * This function returns 1 if the two scattering functions s1 and s2 given
531 * as input are the same (except possibly for the final dimension, where we
532 * allow a difference of 1), assuming that the domains on which this
533 * scatterings are applied are the same.
534 * In fact this function answers the question "can I
535 * safely consider the two domains as only one with two statements (a block) ?".
536 * - s1 and s2 are the two domains to check for blocking,
537 * - scattering is the linked list of all domains,
538 * - scattdims is the total number of scattering dimentions.
540 int cloog_scattering_lazy_block(CloogScattering
*s1
, CloogScattering
*s2
,
541 CloogScatteringList
*scattering
, int scattdims
)
544 struct isl_dim
*dims
;
546 struct isl_set
*delta
;
552 n_scat
= isl_map_n_in(s1
);
553 if (n_scat
!= isl_map_n_in(s2
))
556 dim
= isl_map_n_out(s1
);
557 dims
= isl_dim_set_alloc(s1
->ctx
, isl_map_n_param(s1
), dim
);
558 rel
= isl_map_identity(dims
);
559 rel
= isl_map_apply_range(isl_map_copy(s2
), rel
);
560 rel
= isl_map_reverse(rel
);
561 rel
= isl_map_apply_range(isl_map_copy(s1
), rel
);
562 delta
= isl_map_deltas(rel
);
564 for (i
= 0; i
< n_scat
; ++i
) {
565 fixed
= isl_set_fast_dim_is_fixed(delta
, i
, &cst
);
568 if (i
+1 < n_scat
&& !isl_int_is_zero(cst
))
570 if (!isl_int_is_zero(cst
) && !isl_int_is_one(cst
))
581 * cloog_domain_lazy_disjoint function:
582 * This function returns 1 if the domains given as input are disjoint, 0 if it
583 * is unable to decide.
585 int cloog_domain_lazy_disjoint(CloogDomain
*d1
, CloogDomain
*d2
)
587 return isl_set_fast_is_disjoint(d1
, d2
);
592 * cloog_scattering_list_lazy_same function:
593 * This function returns 1 if two domains in the list are the same, 0 if it
594 * is unable to decide.
596 int cloog_scattering_list_lazy_same(CloogScatteringList
*list
)
598 CloogScatteringList
*one
, *other
;
600 for (one
= list
; one
; one
= one
->next
)
601 for (other
= one
->next
; other
; other
= other
->next
)
602 if (isl_map_fast_is_equal(one
->scatt
, other
->scatt
))
607 int cloog_domain_dimension(CloogDomain
* domain
)
609 return isl_set_n_dim(domain
) + isl_set_n_param(domain
);
612 int cloog_scattering_dimension(CloogScattering
*scatt
, CloogDomain
*domain
)
614 return isl_map_n_in(scatt
);
617 int cloog_domain_isconvex(CloogDomain
* domain
)
619 return domain
->n
<= 1;
624 * cloog_domain_cut_first function:
625 * This function splits off and returns the first convex set in the
626 * union "domain". The remainder of the union is returned in rest.
627 * The original "domain" itself is destroyed and may not be used
628 * after a call to this function.
630 CloogDomain
*cloog_domain_cut_first(CloogDomain
*domain
, CloogDomain
**rest
)
632 struct isl_basic_set
*first
;
634 first
= isl_set_copy_basic_set(domain
);
635 domain
= isl_set_drop_basic_set(domain
, first
);
638 return isl_set_from_basic_set(first
);
643 * Given a union domain, try to find a simpler representation
644 * using fewer sets in the union.
645 * The original "domain" itself is destroyed and may not be used
646 * after a call to this function.
648 CloogDomain
*cloog_domain_simplify_union(CloogDomain
*domain
)
650 return isl_set_coalesce(domain
);
655 * cloog_scattering_lazy_isscalar function:
656 * this function returns 1 if the scattering dimension 'dimension' in the
657 * scattering 'scatt' is constant.
658 * If value is not NULL, then it is set to the constant value of dimension.
660 int cloog_scattering_lazy_isscalar(CloogScattering
*scatt
, int dimension
,
663 return isl_map_fast_input_is_fixed(scatt
, dimension
, value
);
668 * cloog_domain_lazy_isconstant function:
669 * this function returns 1 if the dimension 'dimension' in the
670 * domain 'domain' is constant.
671 * If value is not NULL, then it is set to the constant value of dimension.
673 int cloog_domain_lazy_isconstant(CloogDomain
*domain
, int dimension
)
675 return isl_set_fast_dim_is_fixed(domain
, dimension
, NULL
);
680 * cloog_scattering_erase_dimension function:
681 * this function returns a CloogDomain structure builds from 'domain' where
682 * we removed the dimension 'dimension' and every constraint involving this
685 CloogScattering
*cloog_scattering_erase_dimension(CloogScattering
*domain
,
688 return isl_map_remove_inputs(isl_map_copy(domain
), dimension
, 1);
693 * Construct and return a dim-dimensional cube, with values ranging
694 * between min and max in each dimension.
696 CloogDomain
*cloog_domain_cube(int dim
, cloog_int_t min
, cloog_int_t max
,
697 CloogOptions
*options
)
700 struct isl_basic_set
*cube
;
701 struct isl_basic_set
*interval
;
702 struct isl_basic_set_list
*list
;
705 return cloog_domain_universe(dim
, options
);
707 interval
= isl_basic_set_interval(options
->backend
->ctx
, min
, max
);
708 list
= isl_basic_set_list_alloc(options
->backend
->ctx
, dim
);
709 for (i
= 0; i
< dim
; ++i
)
710 list
= isl_basic_set_list_add(list
, isl_basic_set_copy(interval
));
711 isl_basic_set_free(interval
);
712 cube
= isl_basic_set_product(list
);
713 return isl_set_from_basic_set(cube
);
718 * cloog_domain_scatter function:
719 * This function add the scattering (scheduling) informations to a domain.
721 CloogDomain
*cloog_domain_scatter(CloogDomain
*domain
, CloogScattering
*scatt
)
725 map
= isl_map_intersect_range(isl_map_copy(scatt
), domain
);
726 return isl_set_from_map(map
);