2 * Copyright 2012 Ecole Normale Superieure
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege,
7 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 #include <isl_ast_build_private.h>
15 #include <isl_ast_private.h>
17 /* Construct a map that isolates the current dimension.
19 * Essentially, the current dimension of "set" is moved to the single output
20 * dimension in the result, with the current dimension in the domain replaced
21 * by an unconstrained variable.
23 __isl_give isl_map
*isl_ast_build_map_to_iterator(
24 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
28 map
= isl_map_from_domain(set
);
29 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
32 return isl_map_free(map
);
34 map
= isl_map_equate(map
, isl_dim_in
, build
->depth
, isl_dim_out
, 0);
35 map
= isl_map_eliminate(map
, isl_dim_in
, build
->depth
, 1);
40 /* Initialize the information derived during the AST generation to default
41 * values for a schedule domain in "space".
43 * We also check that the remaining fields are not NULL so that
44 * the calling functions don't have to perform this test.
46 static __isl_give isl_ast_build
*isl_ast_build_init_derived(
47 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
52 build
= isl_ast_build_cow(build
);
53 if (!build
|| !build
->domain
)
56 ctx
= isl_ast_build_get_ctx(build
);
57 strides
= isl_vec_alloc(ctx
, isl_space_dim(space
, isl_dim_set
));
58 strides
= isl_vec_set_si(strides
, 1);
60 isl_vec_free(build
->strides
);
61 build
->strides
= strides
;
63 space
= isl_space_map_from_set(space
);
64 isl_multi_aff_free(build
->offsets
);
65 build
->offsets
= isl_multi_aff_zero(isl_space_copy(space
));
66 isl_multi_aff_free(build
->values
);
67 build
->values
= isl_multi_aff_identity(space
);
69 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
70 !build
->pending
|| !build
->values
||
71 !build
->strides
|| !build
->offsets
|| !build
->options
)
72 return isl_ast_build_free(build
);
76 isl_space_free(space
);
77 return isl_ast_build_free(build
);
80 /* Return an isl_id called "c%d", with "%d" set to "i".
81 * If an isl_id with such a name already appears among the parameters
82 * in build->domain, then adjust the name to "c%d_%d".
84 static __isl_give isl_id
*generate_name(isl_ctx
*ctx
, int i
,
85 __isl_keep isl_ast_build
*build
)
89 isl_set
*dom
= build
->domain
;
91 snprintf(name
, sizeof(name
), "c%d", i
);
93 while (isl_set_find_dim_by_name(dom
, isl_dim_param
, name
) >= 0)
94 snprintf(name
, sizeof(name
), "c%d_%d", i
, j
++);
95 return isl_id_alloc(ctx
, name
, NULL
);
98 /* Create an isl_ast_build with "set" as domain.
100 * The input set is usually a parameter domain, but we currently allow it to
101 * be any kind of set. We set the domain of the returned isl_ast_build
102 * to "set" and initialize all the other field to default values.
104 __isl_give isl_ast_build
*isl_ast_build_from_context(__isl_take isl_set
*set
)
109 isl_ast_build
*build
;
111 set
= isl_set_compute_divs(set
);
115 ctx
= isl_set_get_ctx(set
);
117 build
= isl_calloc_type(ctx
, isl_ast_build
);
123 build
->generated
= isl_set_copy(build
->domain
);
124 build
->pending
= isl_set_universe(isl_set_get_space(build
->domain
));
125 build
->options
= isl_union_map_empty(isl_space_params_alloc(ctx
, 0));
126 n
= isl_set_dim(set
, isl_dim_set
);
128 build
->iterators
= isl_id_list_alloc(ctx
, n
);
129 for (i
= 0; i
< n
; ++i
) {
131 if (isl_set_has_dim_id(set
, isl_dim_set
, i
))
132 id
= isl_set_get_dim_id(set
, isl_dim_set
, i
);
134 id
= generate_name(ctx
, i
, build
);
135 build
->iterators
= isl_id_list_add(build
->iterators
, id
);
137 space
= isl_set_get_space(set
);
138 if (isl_space_is_params(space
))
139 space
= isl_space_set_from_params(space
);
141 return isl_ast_build_init_derived(build
, space
);
147 __isl_give isl_ast_build
*isl_ast_build_copy(__isl_keep isl_ast_build
*build
)
156 __isl_give isl_ast_build
*isl_ast_build_dup(__isl_keep isl_ast_build
*build
)
164 ctx
= isl_ast_build_get_ctx(build
);
165 dup
= isl_calloc_type(ctx
, isl_ast_build
);
170 dup
->outer_pos
= build
->outer_pos
;
171 dup
->depth
= build
->depth
;
172 dup
->iterators
= isl_id_list_copy(build
->iterators
);
173 dup
->domain
= isl_set_copy(build
->domain
);
174 dup
->generated
= isl_set_copy(build
->generated
);
175 dup
->pending
= isl_set_copy(build
->pending
);
176 dup
->values
= isl_multi_aff_copy(build
->values
);
177 dup
->value
= isl_pw_aff_copy(build
->value
);
178 dup
->strides
= isl_vec_copy(build
->strides
);
179 dup
->offsets
= isl_multi_aff_copy(build
->offsets
);
180 dup
->executed
= isl_union_map_copy(build
->executed
);
181 dup
->single_valued
= build
->single_valued
;
182 dup
->options
= isl_union_map_copy(build
->options
);
183 dup
->at_each_domain
= build
->at_each_domain
;
184 dup
->at_each_domain_user
= build
->at_each_domain_user
;
185 dup
->before_each_for
= build
->before_each_for
;
186 dup
->before_each_for_user
= build
->before_each_for_user
;
187 dup
->after_each_for
= build
->after_each_for
;
188 dup
->after_each_for_user
= build
->after_each_for_user
;
189 dup
->create_leaf
= build
->create_leaf
;
190 dup
->create_leaf_user
= build
->create_leaf_user
;
192 if (!dup
->iterators
|| !dup
->domain
|| !dup
->generated
||
193 !dup
->pending
|| !dup
->values
||
194 !dup
->strides
|| !dup
->offsets
|| !dup
->options
||
195 (build
->executed
&& !dup
->executed
) ||
196 (build
->value
&& !dup
->value
))
197 return isl_ast_build_free(dup
);
202 /* Align the parameters of "build" to those of "model", introducing
203 * additional parameters if needed.
205 __isl_give isl_ast_build
*isl_ast_build_align_params(
206 __isl_take isl_ast_build
*build
, __isl_take isl_space
*model
)
208 build
= isl_ast_build_cow(build
);
212 build
->domain
= isl_set_align_params(build
->domain
,
213 isl_space_copy(model
));
214 build
->generated
= isl_set_align_params(build
->generated
,
215 isl_space_copy(model
));
216 build
->pending
= isl_set_align_params(build
->pending
,
217 isl_space_copy(model
));
218 build
->values
= isl_multi_aff_align_params(build
->values
,
219 isl_space_copy(model
));
220 build
->offsets
= isl_multi_aff_align_params(build
->offsets
,
221 isl_space_copy(model
));
222 build
->options
= isl_union_map_align_params(build
->options
,
223 isl_space_copy(model
));
224 isl_space_free(model
);
226 if (!build
->domain
|| !build
->values
|| !build
->offsets
||
228 return isl_ast_build_free(build
);
232 isl_space_free(model
);
236 __isl_give isl_ast_build
*isl_ast_build_cow(__isl_take isl_ast_build
*build
)
244 return isl_ast_build_dup(build
);
247 void *isl_ast_build_free(__isl_take isl_ast_build
*build
)
252 if (--build
->ref
> 0)
255 isl_id_list_free(build
->iterators
);
256 isl_set_free(build
->domain
);
257 isl_set_free(build
->generated
);
258 isl_set_free(build
->pending
);
259 isl_multi_aff_free(build
->values
);
260 isl_pw_aff_free(build
->value
);
261 isl_vec_free(build
->strides
);
262 isl_multi_aff_free(build
->offsets
);
263 isl_multi_aff_free(build
->schedule_map
);
264 isl_union_map_free(build
->executed
);
265 isl_union_map_free(build
->options
);
272 isl_ctx
*isl_ast_build_get_ctx(__isl_keep isl_ast_build
*build
)
274 return build
? isl_set_get_ctx(build
->domain
) : NULL
;
277 /* Replace build->options by "options".
279 __isl_give isl_ast_build
*isl_ast_build_set_options(
280 __isl_take isl_ast_build
*build
, __isl_take isl_union_map
*options
)
282 build
= isl_ast_build_cow(build
);
284 if (!build
|| !options
)
287 isl_union_map_free(build
->options
);
288 build
->options
= options
;
292 isl_union_map_free(options
);
293 return isl_ast_build_free(build
);
296 /* Set the iterators for the next code generation.
298 * If we still have some iterators left from the previous code generation
299 * (if any) or if iterators have already been set by a previous
300 * call to this function, then we remove them first.
302 __isl_give isl_ast_build
*isl_ast_build_set_iterators(
303 __isl_take isl_ast_build
*build
, __isl_take isl_id_list
*iterators
)
307 build
= isl_ast_build_cow(build
);
311 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
312 n_it
= isl_id_list_n_id(build
->iterators
);
314 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
315 "isl_ast_build in inconsistent state", goto error
);
317 build
->iterators
= isl_id_list_drop(build
->iterators
,
319 build
->iterators
= isl_id_list_concat(build
->iterators
, iterators
);
320 if (!build
->iterators
)
321 return isl_ast_build_free(build
);
325 isl_id_list_free(iterators
);
326 return isl_ast_build_free(build
);
329 /* Set the "at_each_domain" callback of "build" to "fn".
331 __isl_give isl_ast_build
*isl_ast_build_set_at_each_domain(
332 __isl_take isl_ast_build
*build
,
333 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_node
*node
,
334 __isl_keep isl_ast_build
*build
, void *user
), void *user
)
336 build
= isl_ast_build_cow(build
);
341 build
->at_each_domain
= fn
;
342 build
->at_each_domain_user
= user
;
347 /* Set the "before_each_for" callback of "build" to "fn".
349 __isl_give isl_ast_build
*isl_ast_build_set_before_each_for(
350 __isl_take isl_ast_build
*build
,
351 __isl_give isl_id
*(*fn
)(__isl_keep isl_ast_build
*build
,
352 void *user
), void *user
)
354 build
= isl_ast_build_cow(build
);
359 build
->before_each_for
= fn
;
360 build
->before_each_for_user
= user
;
365 /* Set the "after_each_for" callback of "build" to "fn".
367 __isl_give isl_ast_build
*isl_ast_build_set_after_each_for(
368 __isl_take isl_ast_build
*build
,
369 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_node
*node
,
370 __isl_keep isl_ast_build
*build
, void *user
), void *user
)
372 build
= isl_ast_build_cow(build
);
377 build
->after_each_for
= fn
;
378 build
->after_each_for_user
= user
;
383 /* Set the "create_leaf" callback of "build" to "fn".
385 __isl_give isl_ast_build
*isl_ast_build_set_create_leaf(
386 __isl_take isl_ast_build
*build
,
387 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_build
*build
,
388 void *user
), void *user
)
390 build
= isl_ast_build_cow(build
);
395 build
->create_leaf
= fn
;
396 build
->create_leaf_user
= user
;
401 /* Clear all information that is specific to this code generation
402 * and that is (probably) not meaningful to any nested code generation.
404 __isl_give isl_ast_build
*isl_ast_build_clear_local_info(
405 __isl_take isl_ast_build
*build
)
409 build
= isl_ast_build_cow(build
);
413 space
= isl_union_map_get_space(build
->options
);
414 isl_union_map_free(build
->options
);
415 build
->options
= isl_union_map_empty(space
);
417 build
->at_each_domain
= NULL
;
418 build
->at_each_domain_user
= NULL
;
419 build
->before_each_for
= NULL
;
420 build
->before_each_for_user
= NULL
;
421 build
->after_each_for
= NULL
;
422 build
->after_each_for_user
= NULL
;
423 build
->create_leaf
= NULL
;
424 build
->create_leaf_user
= NULL
;
427 return isl_ast_build_free(build
);
432 /* Have any loops been eliminated?
433 * That is, do any of the original schedule dimensions have a fixed
434 * value that has been substituted?
436 static int any_eliminated(isl_ast_build
*build
)
440 for (i
= 0; i
< build
->depth
; ++i
)
441 if (isl_ast_build_has_affine_value(build
, i
))
447 /* Clear build->schedule_map.
448 * This function should be called whenever anything that might affect
449 * the result of isl_ast_build_get_schedule_map_multi_aff changes.
450 * In particular, it should be called when the depth is changed or
451 * when an iterator is determined to have a fixed value.
453 static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build
*build
)
457 isl_multi_aff_free(build
->schedule_map
);
458 build
->schedule_map
= NULL
;
461 /* Do we need a (non-trivial) schedule map?
462 * That is, is the internal schedule space different from
463 * the external schedule space?
465 * The internal and external schedule spaces are only the same
466 * if code has been generated for the entire schedule and if none
467 * of the loops have been eliminated.
469 __isl_give
int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build
*build
)
476 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
477 return build
->depth
!= dim
|| any_eliminated(build
);
480 /* Return a mapping from the internal schedule space to the external
481 * schedule space in the form of an isl_multi_aff.
482 * The internal schedule space originally corresponds to that of the
483 * input schedule. This may change during the code generation if
484 * if isl_ast_build_insert_dim is ever called.
485 * The external schedule space corresponds to the
486 * loops that have been generated.
488 * Currently, the only difference between the internal schedule domain
489 * and the external schedule domain is that some dimensions are projected
490 * out in the external schedule domain. In particular, the dimensions
491 * for which no code has been generated yet and the dimensions that correspond
492 * to eliminated loops.
494 * We cache a copy of the schedule_map in build->schedule_map.
495 * The cache is cleared through isl_ast_build_reset_schedule_map
496 * whenever anything changes that might affect the result of this function.
498 __isl_give isl_multi_aff
*isl_ast_build_get_schedule_map_multi_aff(
499 __isl_keep isl_ast_build
*build
)
506 if (build
->schedule_map
)
507 return isl_multi_aff_copy(build
->schedule_map
);
509 space
= isl_ast_build_get_space(build
, 1);
510 space
= isl_space_map_from_set(space
);
511 ma
= isl_multi_aff_identity(space
);
512 if (isl_ast_build_need_schedule_map(build
)) {
514 int dim
= isl_set_dim(build
->domain
, isl_dim_set
);
515 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
,
516 build
->depth
, dim
- build
->depth
);
517 for (i
= build
->depth
- 1; i
>= 0; --i
)
518 if (isl_ast_build_has_affine_value(build
, i
))
519 ma
= isl_multi_aff_drop_dims(ma
,
523 build
->schedule_map
= ma
;
524 return isl_multi_aff_copy(build
->schedule_map
);
527 /* Return a mapping from the internal schedule space to the external
528 * schedule space in the form of an isl_map.
530 __isl_give isl_map
*isl_ast_build_get_schedule_map(
531 __isl_keep isl_ast_build
*build
)
535 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
536 return isl_map_from_multi_aff(ma
);
539 /* Return the position of the dimension in build->domain for which
540 * an AST node is currently being generated.
542 int isl_ast_build_get_depth(__isl_keep isl_ast_build
*build
)
544 return build
? build
->depth
: -1;
547 /* Prepare for generating code for the next level.
548 * In particular, increase the depth and reset any information
549 * that is local to the current depth.
551 __isl_give isl_ast_build
*isl_ast_build_increase_depth(
552 __isl_take isl_ast_build
*build
)
554 build
= isl_ast_build_cow(build
);
558 isl_ast_build_reset_schedule_map(build
);
559 build
->value
= isl_pw_aff_free(build
->value
);
563 void isl_ast_build_dump(__isl_keep isl_ast_build
*build
)
568 fprintf(stderr
, "domain: ");
569 isl_set_dump(build
->domain
);
570 fprintf(stderr
, "generated: ");
571 isl_set_dump(build
->generated
);
572 fprintf(stderr
, "pending: ");
573 isl_set_dump(build
->pending
);
574 fprintf(stderr
, "iterators: ");
575 isl_id_list_dump(build
->iterators
);
576 fprintf(stderr
, "values: ");
577 isl_multi_aff_dump(build
->values
);
579 fprintf(stderr
, "value: ");
580 isl_pw_aff_dump(build
->value
);
582 fprintf(stderr
, "strides: ");
583 isl_vec_dump(build
->strides
);
584 fprintf(stderr
, "offsets: ");
585 isl_multi_aff_dump(build
->offsets
);
588 /* Initialize "build" for AST construction in schedule space "space"
589 * in the case that build->domain is a parameter set.
591 * build->iterators is assumed to have been updated already.
593 static __isl_give isl_ast_build
*isl_ast_build_init(
594 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
598 build
= isl_ast_build_cow(build
);
602 set
= isl_set_universe(isl_space_copy(space
));
603 build
->domain
= isl_set_intersect_params(isl_set_copy(set
),
605 build
->pending
= isl_set_intersect_params(isl_set_copy(set
),
607 build
->generated
= isl_set_intersect_params(set
, build
->generated
);
609 return isl_ast_build_init_derived(build
, space
);
611 isl_ast_build_free(build
);
612 isl_space_free(space
);
616 /* Assign "aff" to *user and return -1, effectively extracting
617 * the first (and presumably only) affine expression in the isl_pw_aff
618 * on which this function is used.
620 static int extract_single_piece(__isl_take isl_set
*set
,
621 __isl_take isl_aff
*aff
, void *user
)
631 /* Check if the given bounds on the current dimension imply that
632 * this current dimension attains only a single value (in terms of
633 * parameters and outer dimensions).
634 * If so, we record it in build->value.
635 * If, moreover, this value can be represented as a single affine expression,
636 * then we also update build->values, effectively marking the current
637 * dimension as "eliminated".
639 * When computing the gist of the fixed value that can be represented
640 * as a single affine expression, it is important to only take into
641 * account the domain constraints in the original AST build and
642 * not the domain of the affine expression itself.
643 * Otherwise, a [i/3] is changed into a i/3 because we know that i
644 * is a multiple of 3, but then we end up not expressing anywhere
645 * in the context that i is a multiple of 3.
647 static __isl_give isl_ast_build
*update_values(
648 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
651 isl_pw_multi_aff
*pma
;
656 set
= isl_set_from_basic_set(bounds
);
657 set
= isl_set_intersect(set
, isl_set_copy(build
->domain
));
658 it_map
= isl_ast_build_map_to_iterator(build
, set
);
660 sv
= isl_map_is_single_valued(it_map
);
662 build
= isl_ast_build_free(build
);
664 isl_map_free(it_map
);
668 pma
= isl_pw_multi_aff_from_map(it_map
);
669 build
->value
= isl_pw_multi_aff_get_pw_aff(pma
, 0);
670 build
->value
= isl_ast_build_compute_gist_pw_aff(build
, build
->value
);
671 build
->value
= isl_pw_aff_coalesce(build
->value
);
672 isl_pw_multi_aff_free(pma
);
675 return isl_ast_build_free(build
);
677 if (isl_pw_aff_n_piece(build
->value
) != 1)
680 isl_pw_aff_foreach_piece(build
->value
, &extract_single_piece
, &aff
);
682 build
->values
= isl_multi_aff_set_aff(build
->values
, build
->depth
, aff
);
684 return isl_ast_build_free(build
);
685 isl_ast_build_reset_schedule_map(build
);
689 /* Update the AST build based on the given loop bounds for
690 * the current dimension.
692 * We first make sure that the bounds do not refer to any iterators
693 * that have already been eliminated.
694 * Then, we check if the bounds imply that the current iterator
696 * If they do and if this fixed value can be expressed as a single
697 * affine expression, we eliminate the iterators from the bounds.
698 * Note that we cannot simply plug in this single value using
699 * isl_basic_set_preimage_multi_aff as the single value may only
700 * be defined on a subset of the domain. Plugging in the value
701 * would restrict the build domain to this subset, while this
702 * restriction may not be reflected in the generated code.
703 * build->domain may, however, already refer to the current dimension
704 * due an earlier call to isl_ast_build_include_stride. If so, we need
705 * to eliminate the dimension so that we do not introduce it in any other sets.
706 * Finally, we intersect build->domain with the updated bounds.
708 * Note that the check for a fixed value in update_values requires
709 * us to intersect the bounds with the current build domain.
710 * When we intersect build->domain with the updated bounds in
711 * the final step, we make sure that these updated bounds have
712 * not been intersected with the old build->domain.
713 * Otherwise, we would indirectly intersect the build domain with itself,
714 * which can lead to inefficiencies, in particular if the build domain
715 * contains any unknown divs.
717 __isl_give isl_ast_build
*isl_ast_build_set_loop_bounds(
718 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
722 build
= isl_ast_build_cow(build
);
726 bounds
= isl_basic_set_preimage_multi_aff(bounds
,
727 isl_multi_aff_copy(build
->values
));
728 build
= update_values(build
, isl_basic_set_copy(bounds
));
731 set
= isl_set_from_basic_set(isl_basic_set_copy(bounds
));
732 if (isl_ast_build_has_affine_value(build
, build
->depth
)) {
733 set
= isl_set_eliminate(set
, isl_dim_set
, build
->depth
, 1);
734 set
= isl_set_compute_divs(set
);
735 build
->pending
= isl_set_intersect(build
->pending
,
737 if (isl_ast_build_has_stride(build
, build
->depth
)) {
738 build
->domain
= isl_set_eliminate(build
->domain
,
739 isl_dim_set
, build
->depth
, 1);
740 build
->domain
= isl_set_compute_divs(build
->domain
);
743 isl_basic_set
*generated
, *pending
;
745 pending
= isl_basic_set_copy(bounds
);
746 pending
= isl_basic_set_drop_constraints_involving_dims(pending
,
747 isl_dim_set
, build
->depth
, 1);
748 build
->pending
= isl_set_intersect(build
->pending
,
749 isl_set_from_basic_set(pending
));
750 generated
= isl_basic_set_copy(bounds
);
751 generated
= isl_basic_set_drop_constraints_not_involving_dims(
752 generated
, isl_dim_set
, build
->depth
, 1);
753 build
->generated
= isl_set_intersect(build
->generated
,
754 isl_set_from_basic_set(generated
));
756 isl_basic_set_free(bounds
);
758 build
->domain
= isl_set_intersect(build
->domain
, set
);
759 if (!build
->domain
|| !build
->pending
|| !build
->generated
)
760 return isl_ast_build_free(build
);
764 isl_ast_build_free(build
);
765 isl_basic_set_free(bounds
);
769 /* Update build->domain based on the constraints enforced by inner loops.
771 * The constraints in build->pending may end up not getting generated
772 * if they are implied by "enforced". We therefore reconstruct
773 * build->domain from build->generated and build->pending, dropping
774 * those constraint in build->pending that may not get generated.
776 __isl_give isl_ast_build
*isl_ast_build_set_enforced(
777 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*enforced
)
781 build
= isl_ast_build_cow(build
);
785 set
= isl_set_from_basic_set(enforced
);
786 set
= isl_set_gist(isl_set_copy(build
->pending
), set
);
787 set
= isl_set_intersect(isl_set_copy(build
->generated
), set
);
789 isl_set_free(build
->domain
);
793 return isl_ast_build_free(build
);
797 isl_basic_set_free(enforced
);
798 return isl_ast_build_free(build
);
801 /* Intersect build->domain with "set", where "set" is specified
802 * in terms of the internal schedule domain.
804 static __isl_give isl_ast_build
*isl_ast_build_restrict_internal(
805 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
807 build
= isl_ast_build_cow(build
);
811 set
= isl_set_compute_divs(set
);
812 build
->domain
= isl_set_intersect(build
->domain
, set
);
813 build
->domain
= isl_set_coalesce(build
->domain
);
816 return isl_ast_build_free(build
);
820 isl_ast_build_free(build
);
825 /* Intersect build->generated and build->domain with "set",
826 * where "set" is specified in terms of the internal schedule domain.
828 __isl_give isl_ast_build
*isl_ast_build_restrict_generated(
829 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
831 set
= isl_set_compute_divs(set
);
832 build
= isl_ast_build_restrict_internal(build
, isl_set_copy(set
));
833 build
= isl_ast_build_cow(build
);
837 build
->generated
= isl_set_intersect(build
->generated
, set
);
838 build
->generated
= isl_set_coalesce(build
->generated
);
840 if (!build
->generated
)
841 return isl_ast_build_free(build
);
845 isl_ast_build_free(build
);
850 /* Intersect build->pending and build->domain with "set",
851 * where "set" is specified in terms of the internal schedule domain.
853 __isl_give isl_ast_build
*isl_ast_build_restrict_pending(
854 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
856 set
= isl_set_compute_divs(set
);
857 build
= isl_ast_build_restrict_internal(build
, isl_set_copy(set
));
858 build
= isl_ast_build_cow(build
);
862 build
->pending
= isl_set_intersect(build
->pending
, set
);
863 build
->pending
= isl_set_coalesce(build
->pending
);
866 return isl_ast_build_free(build
);
870 isl_ast_build_free(build
);
875 /* Intersect build->domain with "set", where "set" is specified
876 * in terms of the external schedule domain.
878 __isl_give isl_ast_build
*isl_ast_build_restrict(
879 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
881 if (isl_set_is_params(set
))
882 return isl_ast_build_restrict_generated(build
, set
);
884 if (isl_ast_build_need_schedule_map(build
)) {
886 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
887 set
= isl_set_preimage_multi_aff(set
, ma
);
889 return isl_ast_build_restrict_generated(build
, set
);
892 /* Replace build->executed by "executed".
894 __isl_give isl_ast_build
*isl_ast_build_set_executed(
895 __isl_take isl_ast_build
*build
, __isl_take isl_union_map
*executed
)
897 build
= isl_ast_build_cow(build
);
901 isl_union_map_free(build
->executed
);
902 build
->executed
= executed
;
906 isl_ast_build_free(build
);
907 isl_union_map_free(executed
);
911 /* Return a copy of the current schedule domain.
913 __isl_give isl_set
*isl_ast_build_get_domain(__isl_keep isl_ast_build
*build
)
915 return build
? isl_set_copy(build
->domain
) : NULL
;
918 /* Return the (schedule) space of "build".
920 * If "internal" is set, then this space is the space of the internal
921 * representation of the entire schedule, including those parts for
922 * which no code has been generated yet.
924 * If "internal" is not set, then this space is the external representation
925 * of the loops generated so far.
927 __isl_give isl_space
*isl_ast_build_get_space(__isl_keep isl_ast_build
*build
,
937 space
= isl_set_get_space(build
->domain
);
941 if (!isl_ast_build_need_schedule_map(build
))
944 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
945 space
= isl_space_drop_dims(space
, isl_dim_set
,
946 build
->depth
, dim
- build
->depth
);
947 for (i
= build
->depth
- 1; i
>= 0; --i
)
948 if (isl_ast_build_has_affine_value(build
, i
))
949 space
= isl_space_drop_dims(space
, isl_dim_set
, i
, 1);
954 /* Return the external representation of the schedule space of "build",
955 * i.e., a space with a dimension for each loop generated so far,
956 * with the names of the dimensions set to the loop iterators.
958 __isl_give isl_space
*isl_ast_build_get_schedule_space(
959 __isl_keep isl_ast_build
*build
)
967 space
= isl_ast_build_get_space(build
, 0);
970 for (i
= 0; i
< build
->depth
; ++i
) {
973 if (isl_ast_build_has_affine_value(build
, i
)) {
978 id
= isl_ast_build_get_iterator_id(build
, i
);
979 space
= isl_space_set_dim_id(space
, isl_dim_set
, i
- skip
, id
);
985 /* Return the current schedule, as stored in build->executed, in terms
986 * of the external schedule domain.
988 __isl_give isl_union_map
*isl_ast_build_get_schedule(
989 __isl_keep isl_ast_build
*build
)
991 isl_union_map
*executed
;
992 isl_union_map
*schedule
;
997 executed
= isl_union_map_copy(build
->executed
);
998 if (isl_ast_build_need_schedule_map(build
)) {
999 isl_map
*proj
= isl_ast_build_get_schedule_map(build
);
1000 executed
= isl_union_map_apply_domain(executed
,
1001 isl_union_map_from_map(proj
));
1003 schedule
= isl_union_map_reverse(executed
);
1008 /* Return the iterator attached to the internal schedule dimension "pos".
1010 __isl_give isl_id
*isl_ast_build_get_iterator_id(
1011 __isl_keep isl_ast_build
*build
, int pos
)
1016 return isl_id_list_get_id(build
->iterators
, pos
);
1019 /* Set the stride and offset of the current dimension to the given
1020 * value and expression.
1022 * If we had already found a stride before, then the two strides
1023 * are combined into a single stride.
1025 * In particular, if the new stride information is of the form
1029 * and the old stride information is of the form
1033 * then we compute the extended gcd of s and s2
1037 * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
1038 * and the second with t2 = a s1/g.
1041 * i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
1043 * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
1044 * is the combined stride.
1046 static __isl_give isl_ast_build
*set_stride(__isl_take isl_ast_build
*build
,
1047 isl_int stride
, __isl_take isl_aff
*offset
)
1051 build
= isl_ast_build_cow(build
);
1052 if (!build
|| !offset
)
1057 if (isl_ast_build_has_stride(build
, pos
)) {
1058 isl_int stride2
, a
, b
, g
;
1061 isl_int_init(stride2
);
1066 isl_vec_get_element(build
->strides
, pos
, &stride2
);
1067 isl_int_gcdext(g
, a
, b
, stride
, stride2
);
1068 isl_int_mul(a
, a
, stride
);
1069 isl_int_divexact(a
, a
, g
);
1070 isl_int_divexact(stride2
, stride2
, g
);
1071 isl_int_mul(b
, b
, stride2
);
1072 isl_int_mul(stride
, stride
, stride2
);
1074 offset2
= isl_multi_aff_get_aff(build
->offsets
, pos
);
1075 offset2
= isl_aff_scale(offset2
, a
);
1076 offset
= isl_aff_scale(offset
, b
);
1077 offset
= isl_aff_add(offset
, offset2
);
1079 isl_int_clear(stride2
);
1085 build
->strides
= isl_vec_set_element(build
->strides
, pos
, stride
);
1086 build
->offsets
= isl_multi_aff_set_aff(build
->offsets
, pos
, offset
);
1087 if (!build
->strides
|| !build
->offsets
)
1088 return isl_ast_build_free(build
);
1092 isl_aff_free(offset
);
1093 return isl_ast_build_free(build
);
1096 /* Return a set expressing the stride constraint at the current depth.
1098 * In particular, if the current iterator (i) is known to attain values
1102 * where f is the offset and s is the stride, then the returned set
1103 * expresses the constraint
1107 __isl_give isl_set
*isl_ast_build_get_stride_constraint(
1108 __isl_keep isl_ast_build
*build
)
1120 if (!isl_ast_build_has_stride(build
, pos
))
1121 return isl_set_universe(isl_ast_build_get_space(build
, 1));
1123 isl_int_init(stride
);
1125 isl_ast_build_get_stride(build
, pos
, &stride
);
1126 aff
= isl_ast_build_get_offset(build
, pos
);
1127 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, pos
, -1);
1128 aff
= isl_aff_mod(aff
, stride
);
1129 set
= isl_set_from_basic_set(isl_aff_zero_basic_set(aff
));
1131 isl_int_clear(stride
);
1136 /* Return the expansion implied by the stride and offset at the current
1139 * That is, return the mapping
1141 * [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1142 * -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]
1144 * where s is the stride at the current depth d and offset(i) is
1145 * the corresponding offset.
1147 __isl_give isl_multi_aff
*isl_ast_build_get_stride_expansion(
1148 __isl_keep isl_ast_build
*build
)
1153 isl_aff
*aff
, *offset
;
1159 pos
= isl_ast_build_get_depth(build
);
1160 space
= isl_ast_build_get_space(build
, 1);
1161 space
= isl_space_map_from_set(space
);
1162 ma
= isl_multi_aff_identity(space
);
1164 if (!isl_ast_build_has_stride(build
, pos
))
1167 isl_int_init(stride
);
1168 offset
= isl_ast_build_get_offset(build
, pos
);
1169 isl_ast_build_get_stride(build
, pos
, &stride
);
1170 aff
= isl_multi_aff_get_aff(ma
, pos
);
1171 aff
= isl_aff_scale(aff
, stride
);
1172 aff
= isl_aff_add(aff
, offset
);
1173 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
1174 isl_int_clear(stride
);
1179 /* Add constraints corresponding to any previously detected
1180 * stride on the current dimension to build->domain.
1182 __isl_give isl_ast_build
*isl_ast_build_include_stride(
1183 __isl_take isl_ast_build
*build
)
1189 if (!isl_ast_build_has_stride(build
, build
->depth
))
1191 build
= isl_ast_build_cow(build
);
1195 set
= isl_ast_build_get_stride_constraint(build
);
1197 build
->domain
= isl_set_intersect(build
->domain
, isl_set_copy(set
));
1198 build
->generated
= isl_set_intersect(build
->generated
, set
);
1199 if (!build
->domain
|| !build
->generated
)
1200 return isl_ast_build_free(build
);
1205 /* Information used inside detect_stride.
1207 * "build" may be updated by detect_stride to include stride information.
1208 * "pos" is equal to build->depth.
1210 struct isl_detect_stride_data
{
1211 isl_ast_build
*build
;
1215 /* Check if constraint "c" imposes any stride on dimension data->pos
1216 * and, if so, update the stride information in data->build.
1218 * In order to impose a stride on the dimension, "c" needs to be an equality
1219 * and it needs to involve the dimension. Note that "c" may also be
1220 * a div constraint and thus an inequality that we cannot use.
1222 * Let c be of the form
1224 * h(p) + g * v * i + g * stride * f(alpha) = 0
1226 * with h(p) an expression in terms of the parameters and outer dimensions
1227 * and f(alpha) an expression in terms of the existentially quantified
1228 * variables. Note that the inner dimensions have been eliminated so
1229 * they do not appear in "c".
1231 * If "stride" is not zero and not one, then it represents a non-trivial stride
1232 * on "i". We compute a and b such that
1234 * a v + b stride = 1
1238 * g v i = -h(p) + g stride f(alpha)
1240 * a g v i = -a h(p) + g stride f(alpha)
1242 * a g v i + b g stride i = -a h(p) + g stride * (...)
1244 * g i = -a h(p) + g stride * (...)
1246 * i = -a h(p)/g + stride * (...)
1248 * The expression "-a h(p)/g" can therefore be used as offset.
1250 static int detect_stride(__isl_take isl_constraint
*c
, void *user
)
1252 struct isl_detect_stride_data
*data
= user
;
1254 isl_int v
, gcd
, stride
, a
, b
, m
;
1256 if (!isl_constraint_is_equality(c
) ||
1257 !isl_constraint_involves_dims(c
, isl_dim_set
, data
->pos
, 1)) {
1258 isl_constraint_free(c
);
1267 isl_int_init(stride
);
1269 isl_int_set_si(gcd
, 0);
1270 n_div
= isl_constraint_dim(c
, isl_dim_div
);
1271 for (i
= 0; i
< n_div
; ++i
) {
1272 isl_constraint_get_coefficient(c
, isl_dim_div
, i
, &v
);
1273 isl_int_gcd(gcd
, gcd
, v
);
1276 isl_constraint_get_coefficient(c
, isl_dim_set
, data
->pos
, &v
);
1277 isl_int_gcd(m
, v
, gcd
);
1278 isl_int_divexact(stride
, gcd
, m
);
1279 isl_int_divexact(v
, v
, m
);
1281 if (!isl_int_is_zero(stride
) && !isl_int_is_one(stride
)) {
1284 isl_int_gcdext(gcd
, a
, b
, v
, stride
);
1286 aff
= isl_constraint_get_aff(c
);
1287 for (i
= 0; i
< n_div
; ++i
)
1288 aff
= isl_aff_set_coefficient_si(aff
,
1290 aff
= isl_aff_set_coefficient_si(aff
, isl_dim_in
, data
->pos
, 0);
1292 aff
= isl_aff_scale(aff
, a
);
1293 aff
= isl_aff_scale_down(aff
, m
);
1294 data
->build
= set_stride(data
->build
, stride
, aff
);
1297 isl_int_clear(stride
);
1304 isl_constraint_free(c
);
1308 /* Check if the constraints in "set" imply any stride on the current
1309 * dimension and, if so, record the stride information in "build"
1310 * and return the updated "build".
1312 * We compute the affine hull and then check if any of the constraints
1313 * in the hull imposes any stride on the current dimension.
1315 * We assume that inner dimensions have been eliminated from "set"
1316 * by the caller. This is needed because the common stride
1317 * may be imposed by different inner dimensions on different parts of
1320 __isl_give isl_ast_build
*isl_ast_build_detect_strides(
1321 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
1323 isl_basic_set
*hull
;
1324 struct isl_detect_stride_data data
;
1330 data
.pos
= isl_ast_build_get_depth(build
);
1331 hull
= isl_set_affine_hull(set
);
1333 if (isl_basic_set_foreach_constraint(hull
, &detect_stride
, &data
) < 0)
1334 data
.build
= isl_ast_build_free(data
.build
);
1336 isl_basic_set_free(hull
);
1343 struct isl_ast_build_involves_data
{
1348 /* Check if "map" involves the input dimension data->depth.
1350 static int involves_depth(__isl_take isl_map
*map
, void *user
)
1352 struct isl_ast_build_involves_data
*data
= user
;
1354 data
->involves
= isl_map_involves_dims(map
, isl_dim_in
, data
->depth
, 1);
1357 if (data
->involves
< 0 || data
->involves
)
1362 /* Do any options depend on the value of the dimension at the current depth?
1364 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build
*build
)
1366 struct isl_ast_build_involves_data data
;
1371 data
.depth
= build
->depth
;
1374 if (isl_union_map_foreach_map(build
->options
,
1375 &involves_depth
, &data
) < 0) {
1376 if (data
.involves
< 0 || !data
.involves
)
1380 return data
.involves
;
1383 /* Construct the map
1385 * { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1387 * with "space" the parameter space of the constructed map.
1389 static __isl_give isl_map
*construct_insertion_map(__isl_take isl_space
*space
,
1393 isl_basic_map
*bmap1
, *bmap2
;
1395 space
= isl_space_set_from_params(space
);
1396 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1397 space
= isl_space_map_from_set(space
);
1398 c
= isl_equality_alloc(isl_local_space_from_space(space
));
1399 c
= isl_constraint_set_coefficient_si(c
, isl_dim_in
, 0, 1);
1400 c
= isl_constraint_set_coefficient_si(c
, isl_dim_out
, 0, -1);
1401 bmap1
= isl_basic_map_from_constraint(isl_constraint_copy(c
));
1402 c
= isl_constraint_set_constant_si(c
, 1);
1403 bmap2
= isl_basic_map_from_constraint(c
);
1405 bmap1
= isl_basic_map_upper_bound_si(bmap1
, isl_dim_in
, 0, pos
- 1);
1406 bmap2
= isl_basic_map_lower_bound_si(bmap2
, isl_dim_in
, 0, pos
);
1408 return isl_basic_map_union(bmap1
, bmap2
);
1411 static const char *option_str
[] = {
1412 [atomic
] = "atomic",
1413 [unroll
] = "unroll",
1414 [separate
] = "separate"
1417 /* Update the "options" to reflect the insertion of a dimension
1418 * at position "pos" in the schedule domain space.
1419 * "space" is the original domain space before the insertion and
1420 * may be named and/or structured.
1422 * The (relevant) input options all have "space" as domain, which
1423 * has to be mapped to the extended space.
1424 * The values of the ranges also refer to the schedule domain positions
1425 * and they therefore also need to be adjusted. In particular, values
1426 * smaller than pos do not need to change, while values greater than or
1427 * equal to pos need to be incremented.
1428 * That is, we need to apply the following map.
1430 * { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1431 * unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1432 * separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1433 * separation_class[[i] -> [c]]
1434 * -> separation_class[[i] -> [c]] : i < pos;
1435 * separation_class[[i] -> [c]]
1436 * -> separation_class[[i + 1] -> [c]] : i >= pos }
1438 static __isl_give isl_union_map
*options_insert_dim(
1439 __isl_take isl_union_map
*options
, __isl_take isl_space
*space
, int pos
)
1442 isl_union_map
*insertion
;
1443 enum isl_ast_build_domain_type type
;
1444 const char *name
= "separation_class";
1446 space
= isl_space_map_from_set(space
);
1447 map
= isl_map_identity(space
);
1448 map
= isl_map_insert_dims(map
, isl_dim_out
, pos
, 1);
1449 options
= isl_union_map_apply_domain(options
,
1450 isl_union_map_from_map(map
));
1455 map
= construct_insertion_map(isl_union_map_get_space(options
), pos
);
1457 insertion
= isl_union_map_empty(isl_union_map_get_space(options
));
1459 for (type
= atomic
; type
<= separate
; ++type
) {
1460 isl_map
*map_type
= isl_map_copy(map
);
1461 const char *name
= option_str
[type
];
1462 map_type
= isl_map_set_tuple_name(map_type
, isl_dim_in
, name
);
1463 map_type
= isl_map_set_tuple_name(map_type
, isl_dim_out
, name
);
1464 insertion
= isl_union_map_add_map(insertion
, map_type
);
1467 map
= isl_map_product(map
, isl_map_identity(isl_map_get_space(map
)));
1468 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
1469 map
= isl_map_set_tuple_name(map
, isl_dim_out
, name
);
1470 insertion
= isl_union_map_add_map(insertion
, map
);
1472 options
= isl_union_map_apply_range(options
, insertion
);
1477 /* Insert a single dimension in the schedule domain at position "pos".
1478 * The new dimension is given an isl_id with the empty string as name.
1480 * The main difficulty is updating build->options to reflect the
1481 * extra dimension. This is handled in options_insert_dim.
1483 * Note that because of the dimension manipulations, the resulting
1484 * schedule domain space will always be unnamed and unstructured.
1485 * However, the original schedule domain space may be named and/or
1486 * structured, so we have to take this possibility into account
1487 * while performing the transformations.
1489 __isl_give isl_ast_build
*isl_ast_build_insert_dim(
1490 __isl_take isl_ast_build
*build
, int pos
)
1493 isl_space
*space
, *ma_space
;
1497 build
= isl_ast_build_cow(build
);
1501 ctx
= isl_ast_build_get_ctx(build
);
1502 id
= isl_id_alloc(ctx
, "", NULL
);
1503 space
= isl_ast_build_get_space(build
, 1);
1504 build
->iterators
= isl_id_list_insert(build
->iterators
, pos
, id
);
1505 build
->domain
= isl_set_insert_dims(build
->domain
,
1506 isl_dim_set
, pos
, 1);
1507 build
->generated
= isl_set_insert_dims(build
->generated
,
1508 isl_dim_set
, pos
, 1);
1509 build
->pending
= isl_set_insert_dims(build
->pending
,
1510 isl_dim_set
, pos
, 1);
1511 build
->strides
= isl_vec_insert_els(build
->strides
, pos
, 1);
1512 build
->strides
= isl_vec_set_element_si(build
->strides
, pos
, 1);
1513 ma_space
= isl_space_params(isl_multi_aff_get_space(build
->offsets
));
1514 ma_space
= isl_space_set_from_params(ma_space
);
1515 ma_space
= isl_space_add_dims(ma_space
, isl_dim_set
, 1);
1516 ma_space
= isl_space_map_from_set(ma_space
);
1517 ma
= isl_multi_aff_zero(isl_space_copy(ma_space
));
1518 build
->offsets
= isl_multi_aff_splice(build
->offsets
, pos
, pos
, ma
);
1519 ma
= isl_multi_aff_identity(ma_space
);
1520 build
->values
= isl_multi_aff_splice(build
->values
, pos
, pos
, ma
);
1521 build
->options
= options_insert_dim(build
->options
, space
, pos
);
1523 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
1524 !build
->pending
|| !build
->values
||
1525 !build
->strides
|| !build
->offsets
|| !build
->options
)
1526 return isl_ast_build_free(build
);
1531 /* Scale down the current dimension by a factor of "m".
1532 * "umap" is an isl_union_map that implements the scaling down.
1533 * That is, it is of the form
1535 * { [.... i ....] -> [.... i' ....] : i = m i' }
1537 * This function is called right after the strides have been
1538 * detected, but before any constraints on the current dimension
1539 * have been included in build->domain.
1540 * We therefore only need to update stride, offset and the options.
1542 __isl_give isl_ast_build
*isl_ast_build_scale_down(
1543 __isl_take isl_ast_build
*build
, isl_int m
,
1544 __isl_take isl_union_map
*umap
)
1550 build
= isl_ast_build_cow(build
);
1551 if (!build
|| !umap
)
1554 depth
= build
->depth
;
1557 if (isl_vec_get_element(build
->strides
, depth
, &v
) < 0)
1558 build
->strides
= isl_vec_free(build
->strides
);
1559 isl_int_divexact(v
, v
, m
);
1560 build
->strides
= isl_vec_set_element(build
->strides
, depth
, v
);
1563 aff
= isl_multi_aff_get_aff(build
->offsets
, depth
);
1564 aff
= isl_aff_scale_down(aff
, m
);
1565 build
->offsets
= isl_multi_aff_set_aff(build
->offsets
, depth
, aff
);
1566 build
->options
= isl_union_map_apply_domain(build
->options
, umap
);
1567 if (!build
->strides
|| !build
->offsets
|| !build
->options
)
1568 return isl_ast_build_free(build
);
1572 isl_union_map_free(umap
);
1573 return isl_ast_build_free(build
);
1576 /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1577 * If an isl_id with such a name already appears among the parameters
1578 * in build->domain, then adjust the name to "c%d_%d".
1580 static __isl_give isl_id_list
*generate_names(isl_ctx
*ctx
, int n
, int first
,
1581 __isl_keep isl_ast_build
*build
)
1586 names
= isl_id_list_alloc(ctx
, n
);
1587 for (i
= 0; i
< n
; ++i
) {
1590 id
= generate_name(ctx
, first
+ i
, build
);
1591 names
= isl_id_list_add(names
, id
);
1597 /* Embed "options" into the given isl_ast_build space.
1599 * This function is called from within a nested call to
1600 * isl_ast_build_ast_from_schedule.
1601 * "options" refers to the additional schedule,
1602 * while space refers to both the space of the outer isl_ast_build and
1603 * that of the additional schedule.
1604 * Specifically, space is of the form
1608 * while options lives in the space(s)
1616 * and compose this with options, to obtain the new options
1617 * living in the space(s)
1621 static __isl_give isl_union_map
*embed_options(
1622 __isl_take isl_union_map
*options
, __isl_take isl_space
*space
)
1626 map
= isl_map_universe(isl_space_unwrap(space
));
1627 map
= isl_map_range_map(map
);
1629 options
= isl_union_map_apply_range(
1630 isl_union_map_from_map(map
), options
);
1635 /* Update "build" for use in a (possibly nested) code generation. That is,
1636 * extend "build" from an AST build on some domain O to an AST build
1637 * on domain [O -> S], with S corresponding to "space".
1638 * If the original domain is a parameter domain, then the new domain is
1640 * "iterators" is a list of iterators for S, but the number of elements
1641 * may be smaller or greater than the number of set dimensions of S.
1642 * If "keep_iterators" is set, then any extra ids in build->iterators
1643 * are reused for S. Otherwise, these extra ids are dropped.
1645 * We first update build->outer_pos to the current depth.
1646 * This depth is zero in case this is the outermost code generation.
1648 * We then add additional ids such that the number of iterators is at least
1649 * equal to the dimension of the new build domain.
1651 * If the original domain is parametric, then we are constructing
1652 * an isl_ast_build for the outer code generation and we pass control
1653 * to isl_ast_build_init.
1655 * Otherwise, we adjust the fields of "build" to include "space".
1657 __isl_give isl_ast_build
*isl_ast_build_product(
1658 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
1663 isl_multi_aff
*embedding
;
1666 build
= isl_ast_build_cow(build
);
1670 build
->outer_pos
= build
->depth
;
1672 ctx
= isl_ast_build_get_ctx(build
);
1673 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
1674 dim
+= isl_space_dim(space
, isl_dim_set
);
1675 n_it
= isl_id_list_n_id(build
->iterators
);
1678 l
= generate_names(ctx
, dim
- n_it
, n_it
, build
);
1679 build
->iterators
= isl_id_list_concat(build
->iterators
, l
);
1682 if (isl_set_is_params(build
->domain
))
1683 return isl_ast_build_init(build
, space
);
1685 set
= isl_set_universe(isl_space_copy(space
));
1686 build
->domain
= isl_set_product(build
->domain
, isl_set_copy(set
));
1687 build
->pending
= isl_set_product(build
->pending
, isl_set_copy(set
));
1688 build
->generated
= isl_set_product(build
->generated
, set
);
1690 strides
= isl_vec_alloc(ctx
, isl_space_dim(space
, isl_dim_set
));
1691 strides
= isl_vec_set_si(strides
, 1);
1692 build
->strides
= isl_vec_concat(build
->strides
, strides
);
1694 space
= isl_space_map_from_set(space
);
1695 build
->offsets
= isl_multi_aff_align_params(build
->offsets
,
1696 isl_space_copy(space
));
1697 build
->offsets
= isl_multi_aff_product(build
->offsets
,
1698 isl_multi_aff_zero(isl_space_copy(space
)));
1699 build
->values
= isl_multi_aff_align_params(build
->values
,
1700 isl_space_copy(space
));
1701 embedding
= isl_multi_aff_identity(space
);
1702 build
->values
= isl_multi_aff_product(build
->values
, embedding
);
1704 space
= isl_ast_build_get_space(build
, 1);
1705 build
->options
= embed_options(build
->options
, space
);
1707 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
1708 !build
->pending
|| !build
->values
||
1709 !build
->strides
|| !build
->offsets
|| !build
->options
)
1710 return isl_ast_build_free(build
);
1714 isl_ast_build_free(build
);
1715 isl_space_free(space
);
1719 /* Does "aff" only attain non-negative values over build->domain?
1720 * That is, does it not attain any negative values?
1722 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build
*build
,
1723 __isl_keep isl_aff
*aff
)
1731 aff
= isl_aff_copy(aff
);
1732 test
= isl_set_from_basic_set(isl_aff_neg_basic_set(aff
));
1733 test
= isl_set_intersect(test
, isl_set_copy(build
->domain
));
1734 empty
= isl_set_is_empty(test
);
1740 /* Does the dimension at (internal) position "pos" have a non-trivial stride?
1742 int isl_ast_build_has_stride(__isl_keep isl_ast_build
*build
, int pos
)
1751 isl_vec_get_element(build
->strides
, pos
, &v
);
1752 has_stride
= !isl_int_is_one(v
);
1758 /* Given that the dimension at position "pos" takes on values
1762 * with a an integer, return s through *stride.
1764 int isl_ast_build_get_stride(__isl_keep isl_ast_build
*build
, int pos
,
1770 isl_vec_get_element(build
->strides
, pos
, stride
);
1775 /* Given that the dimension at position "pos" takes on values
1779 * with a an integer, return f.
1781 __isl_give isl_aff
*isl_ast_build_get_offset(
1782 __isl_keep isl_ast_build
*build
, int pos
)
1787 return isl_multi_aff_get_aff(build
->offsets
, pos
);
1790 /* Is the dimension at position "pos" known to attain only a single
1791 * value that, moreover, can be described by a single affine expression
1792 * in terms of the outer dimensions and parameters?
1794 * If not, then the correponding affine expression in build->values
1795 * is set to be equal to the same input dimension.
1796 * Otherwise, it is set to the requested expression in terms of
1797 * outer dimensions and parameters.
1799 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build
*build
,
1808 aff
= isl_multi_aff_get_aff(build
->values
, pos
);
1809 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, pos
, 1);
1818 /* Plug in the known values (fixed affine expressions in terms of
1819 * parameters and outer loop iterators) of all loop iterators
1820 * in the domain of "umap".
1822 * We simply precompose "umap" with build->values.
1824 __isl_give isl_union_map
*isl_ast_build_substitute_values_union_map_domain(
1825 __isl_keep isl_ast_build
*build
, __isl_take isl_union_map
*umap
)
1827 isl_multi_aff
*values
;
1830 return isl_union_map_free(umap
);
1832 values
= isl_multi_aff_copy(build
->values
);
1833 umap
= isl_union_map_preimage_domain_multi_aff(umap
, values
);
1838 /* Is the current dimension known to attain only a single value?
1840 int isl_ast_build_has_value(__isl_keep isl_ast_build
*build
)
1845 return build
->value
!= NULL
;
1848 /* Simplify the basic set "bset" based on what we know about
1849 * the iterators of already generated loops.
1851 * "bset" is assumed to live in the (internal) schedule domain.
1853 __isl_give isl_basic_set
*isl_ast_build_compute_gist_basic_set(
1854 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
1859 bset
= isl_basic_set_preimage_multi_aff(bset
,
1860 isl_multi_aff_copy(build
->values
));
1861 bset
= isl_basic_set_gist(bset
,
1862 isl_set_simple_hull(isl_set_copy(build
->domain
)));
1866 isl_basic_set_free(bset
);
1870 /* Simplify the set "set" based on what we know about
1871 * the iterators of already generated loops.
1873 * "set" is assumed to live in the (internal) schedule domain.
1875 __isl_give isl_set
*isl_ast_build_compute_gist(
1876 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
1881 set
= isl_set_preimage_multi_aff(set
,
1882 isl_multi_aff_copy(build
->values
));
1883 set
= isl_set_gist(set
, isl_set_copy(build
->domain
));
1891 /* Simplify the map "map" based on what we know about
1892 * the iterators of already generated loops.
1894 * The domain of "map" is assumed to live in the (internal) schedule domain.
1896 __isl_give isl_map
*isl_ast_build_compute_gist_map_domain(
1897 __isl_keep isl_ast_build
*build
, __isl_take isl_map
*map
)
1902 map
= isl_map_gist_domain(map
, isl_set_copy(build
->domain
));
1910 /* Simplify the affine expression "aff" based on what we know about
1911 * the iterators of already generated loops.
1913 * The domain of "aff" is assumed to live in the (internal) schedule domain.
1915 __isl_give isl_aff
*isl_ast_build_compute_gist_aff(
1916 __isl_keep isl_ast_build
*build
, __isl_take isl_aff
*aff
)
1921 aff
= isl_aff_gist(aff
, isl_set_copy(build
->domain
));
1929 /* Simplify the piecewise affine expression "aff" based on what we know about
1930 * the iterators of already generated loops.
1932 * The domain of "pa" is assumed to live in the (internal) schedule domain.
1934 __isl_give isl_pw_aff
*isl_ast_build_compute_gist_pw_aff(
1935 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
1940 pa
= isl_pw_aff_pullback_multi_aff(pa
,
1941 isl_multi_aff_copy(build
->values
));
1942 pa
= isl_pw_aff_gist(pa
, isl_set_copy(build
->domain
));
1946 isl_pw_aff_free(pa
);
1950 /* Simplify the piecewise multi-affine expression "aff" based on what
1951 * we know about the iterators of already generated loops.
1953 * The domain of "pma" is assumed to live in the (internal) schedule domain.
1955 __isl_give isl_pw_multi_aff
*isl_ast_build_compute_gist_pw_multi_aff(
1956 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
1961 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
,
1962 isl_multi_aff_copy(build
->values
));
1963 pma
= isl_pw_multi_aff_gist(pma
, isl_set_copy(build
->domain
));
1967 isl_pw_multi_aff_free(pma
);
1971 /* Extract the schedule domain of the given type from build->options
1972 * at the current depth.
1974 * In particular, find the subset of build->options that is of
1975 * the following form
1977 * schedule_domain -> type[depth]
1979 * and return the corresponding domain, after eliminating inner dimensions
1980 * and divs that depend on the current dimension.
1982 * Note that the domain of build->options has been reformulated
1983 * in terms of the internal build space in embed_options,
1984 * but the position is still that within the current code generation.
1986 __isl_give isl_set
*isl_ast_build_get_option_domain(
1987 __isl_keep isl_ast_build
*build
,
1988 enum isl_ast_build_domain_type type
)
1999 name
= option_str
[type
];
2000 local_pos
= build
->depth
- build
->outer_pos
;
2002 space
= isl_ast_build_get_space(build
, 1);
2003 space
= isl_space_from_domain(space
);
2004 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
2005 space
= isl_space_set_tuple_name(space
, isl_dim_out
, name
);
2007 option
= isl_union_map_extract_map(build
->options
, space
);
2008 option
= isl_map_fix_si(option
, isl_dim_out
, 0, local_pos
);
2010 domain
= isl_map_domain(option
);
2011 domain
= isl_ast_build_eliminate(build
, domain
);
2016 /* Extract the separation class mapping at the current depth.
2018 * In particular, find and return the subset of build->options that is of
2019 * the following form
2021 * schedule_domain -> separation_class[[depth] -> [class]]
2023 * The caller is expected to eliminate inner dimensions from the domain.
2025 * Note that the domain of build->options has been reformulated
2026 * in terms of the internal build space in embed_options,
2027 * but the position is still that within the current code generation.
2029 __isl_give isl_map
*isl_ast_build_get_separation_class(
2030 __isl_keep isl_ast_build
*build
)
2033 isl_space
*space_sep
, *space
;
2040 local_pos
= build
->depth
- build
->outer_pos
;
2041 ctx
= isl_ast_build_get_ctx(build
);
2042 space_sep
= isl_space_alloc(ctx
, 0, 1, 1);
2043 space_sep
= isl_space_wrap(space_sep
);
2044 space_sep
= isl_space_set_tuple_name(space_sep
, isl_dim_set
,
2045 "separation_class");
2046 space
= isl_ast_build_get_space(build
, 1);
2047 space_sep
= isl_space_align_params(space_sep
, isl_space_copy(space
));
2048 space
= isl_space_map_from_domain_and_range(space
, space_sep
);
2050 res
= isl_union_map_extract_map(build
->options
, space
);
2051 res
= isl_map_fix_si(res
, isl_dim_out
, 0, local_pos
);
2052 res
= isl_map_coalesce(res
);
2057 /* Eliminate dimensions inner to the current dimension.
2059 __isl_give isl_set
*isl_ast_build_eliminate_inner(
2060 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2066 return isl_set_free(set
);
2068 dim
= isl_set_dim(set
, isl_dim_set
);
2069 depth
= build
->depth
;
2070 set
= isl_set_detect_equalities(set
);
2071 set
= isl_set_eliminate(set
, isl_dim_set
, depth
+ 1, dim
- (depth
+ 1));
2076 /* Eliminate unknown divs and divs that depend on the current dimension.
2078 * Note that during the elimination of unknown divs, we may discover
2079 * an explicit representation of some other unknown divs, which may
2080 * depend on the current dimension. We therefore need to eliminate
2081 * unknown divs first.
2083 __isl_give isl_set
*isl_ast_build_eliminate_divs(
2084 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2089 return isl_set_free(set
);
2091 set
= isl_set_remove_unknown_divs(set
);
2092 depth
= build
->depth
;
2093 set
= isl_set_remove_divs_involving_dims(set
, isl_dim_set
, depth
, 1);
2098 /* Eliminate dimensions inner to the current dimension as well as
2099 * unknown divs and divs that depend on the current dimension.
2100 * The result then consists only of constraints that are independent
2101 * of the current dimension and upper and lower bounds on the current
2104 __isl_give isl_set
*isl_ast_build_eliminate(
2105 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*domain
)
2107 domain
= isl_ast_build_eliminate_inner(build
, domain
);
2108 domain
= isl_ast_build_eliminate_divs(build
, domain
);
2112 /* Replace build->single_valued by "sv".
2114 __isl_give isl_ast_build
*isl_ast_build_set_single_valued(
2115 __isl_take isl_ast_build
*build
, int sv
)
2119 if (build
->single_valued
== sv
)
2121 build
= isl_ast_build_cow(build
);
2124 build
->single_valued
= sv
;