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
13 #include <isl_ast_build_private.h>
14 #include <isl_ast_private.h>
16 /* Construct a map that isolates the current dimension.
18 * Essentially, the current dimension of "set" is moved to the single output
19 * dimension in the result, with the current dimension in the domain replaced
20 * by an unconstrained variable.
22 __isl_give isl_map
*isl_ast_build_map_to_iterator(
23 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
27 map
= isl_map_from_domain(set
);
28 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
31 return isl_map_free(map
);
33 map
= isl_map_equate(map
, isl_dim_in
, build
->depth
, isl_dim_out
, 0);
34 map
= isl_map_eliminate(map
, isl_dim_in
, build
->depth
, 1);
39 /* Initialize the information derived during the AST generation to default
40 * values for a schedule domain in "space".
42 * We also check that the remaining fields are not NULL so that
43 * the calling functions don't have to perform this test.
45 static __isl_give isl_ast_build
*isl_ast_build_init_derived(
46 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
51 build
= isl_ast_build_cow(build
);
55 ctx
= isl_ast_build_get_ctx(build
);
56 strides
= isl_vec_alloc(ctx
, isl_space_dim(space
, isl_dim_set
));
57 strides
= isl_vec_set_si(strides
, 1);
59 isl_vec_free(build
->strides
);
60 build
->strides
= strides
;
62 space
= isl_space_map_from_set(space
);
63 isl_multi_aff_free(build
->offsets
);
64 build
->offsets
= isl_multi_aff_zero(isl_space_copy(space
));
65 isl_multi_aff_free(build
->values
);
66 build
->values
= isl_multi_aff_identity(space
);
68 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
69 !build
->pending
|| !build
->values
||
70 !build
->strides
|| !build
->offsets
|| !build
->options
)
71 return isl_ast_build_free(build
);
75 isl_space_free(space
);
76 return isl_ast_build_free(build
);
79 /* Create an isl_ast_build with "set" as domain.
81 * The input set is usually a parameter domain, but we currently allow it to
82 * be any kind of set. We set the domain of the returned isl_ast_build
83 * to "set" and initialize all the other field to default values.
85 __isl_give isl_ast_build
*isl_ast_build_from_context(__isl_take isl_set
*set
)
92 set
= isl_set_compute_divs(set
);
96 ctx
= isl_set_get_ctx(set
);
98 build
= isl_calloc_type(ctx
, isl_ast_build
);
104 build
->generated
= isl_set_copy(build
->domain
);
105 build
->pending
= isl_set_universe(isl_set_get_space(build
->domain
));
106 build
->options
= isl_union_map_empty(isl_space_params_alloc(ctx
, 0));
107 n
= isl_set_dim(set
, isl_dim_set
);
109 build
->iterators
= isl_id_list_alloc(ctx
, n
);
110 for (i
= 0; i
< n
; ++i
) {
111 isl_id
*id
= isl_set_get_dim_id(set
, isl_dim_set
, i
);
112 build
->iterators
= isl_id_list_add(build
->iterators
, id
);
114 space
= isl_set_get_space(set
);
115 if (isl_space_is_params(space
))
116 space
= isl_space_set_from_params(space
);
118 return isl_ast_build_init_derived(build
, space
);
124 __isl_give isl_ast_build
*isl_ast_build_copy(__isl_keep isl_ast_build
*build
)
133 __isl_give isl_ast_build
*isl_ast_build_dup(__isl_keep isl_ast_build
*build
)
141 ctx
= isl_ast_build_get_ctx(build
);
142 dup
= isl_calloc_type(ctx
, isl_ast_build
);
147 dup
->outer_pos
= build
->outer_pos
;
148 dup
->depth
= build
->depth
;
149 dup
->iterators
= isl_id_list_copy(build
->iterators
);
150 dup
->domain
= isl_set_copy(build
->domain
);
151 dup
->generated
= isl_set_copy(build
->generated
);
152 dup
->pending
= isl_set_copy(build
->pending
);
153 dup
->values
= isl_multi_aff_copy(build
->values
);
154 dup
->value
= isl_pw_aff_copy(build
->value
);
155 dup
->strides
= isl_vec_copy(build
->strides
);
156 dup
->offsets
= isl_multi_aff_copy(build
->offsets
);
157 dup
->executed
= isl_union_map_copy(build
->executed
);
158 dup
->options
= isl_union_map_copy(build
->options
);
159 dup
->at_each_domain
= build
->at_each_domain
;
160 dup
->at_each_domain_user
= build
->at_each_domain_user
;
161 dup
->create_leaf
= build
->create_leaf
;
162 dup
->create_leaf_user
= build
->create_leaf_user
;
164 if (!dup
->iterators
|| !dup
->domain
|| !dup
->generated
||
165 !dup
->pending
|| !dup
->values
||
166 !dup
->strides
|| !dup
->offsets
|| !dup
->options
||
167 (build
->executed
&& !dup
->executed
) ||
168 (build
->value
&& !dup
->value
))
169 return isl_ast_build_free(dup
);
174 /* Align the parameters of "build" to those of "model", introducing
175 * additional parameters if needed.
177 __isl_give isl_ast_build
*isl_ast_build_align_params(
178 __isl_take isl_ast_build
*build
, __isl_take isl_space
*model
)
180 build
= isl_ast_build_cow(build
);
184 build
->domain
= isl_set_align_params(build
->domain
,
185 isl_space_copy(model
));
186 build
->generated
= isl_set_align_params(build
->generated
,
187 isl_space_copy(model
));
188 build
->pending
= isl_set_align_params(build
->pending
,
189 isl_space_copy(model
));
190 build
->values
= isl_multi_aff_align_params(build
->values
,
191 isl_space_copy(model
));
192 build
->offsets
= isl_multi_aff_align_params(build
->offsets
,
193 isl_space_copy(model
));
194 build
->options
= isl_union_map_align_params(build
->options
,
195 isl_space_copy(model
));
196 isl_space_free(model
);
198 if (!build
->domain
|| !build
->values
|| !build
->offsets
||
200 return isl_ast_build_free(build
);
204 isl_space_free(model
);
208 __isl_give isl_ast_build
*isl_ast_build_cow(__isl_take isl_ast_build
*build
)
216 return isl_ast_build_dup(build
);
219 void *isl_ast_build_free(__isl_take isl_ast_build
*build
)
224 if (--build
->ref
> 0)
227 isl_id_list_free(build
->iterators
);
228 isl_set_free(build
->domain
);
229 isl_set_free(build
->generated
);
230 isl_set_free(build
->pending
);
231 isl_multi_aff_free(build
->values
);
232 isl_pw_aff_free(build
->value
);
233 isl_vec_free(build
->strides
);
234 isl_multi_aff_free(build
->offsets
);
235 isl_multi_aff_free(build
->schedule_map
);
236 isl_union_map_free(build
->executed
);
237 isl_union_map_free(build
->options
);
244 isl_ctx
*isl_ast_build_get_ctx(__isl_keep isl_ast_build
*build
)
246 return build
? isl_set_get_ctx(build
->domain
) : NULL
;
249 /* Replace build->options by "options".
251 __isl_give isl_ast_build
*isl_ast_build_set_options(
252 __isl_take isl_ast_build
*build
, __isl_take isl_union_map
*options
)
254 build
= isl_ast_build_cow(build
);
256 if (!build
|| !options
)
259 isl_union_map_free(build
->options
);
260 build
->options
= options
;
264 isl_union_map_free(options
);
265 return isl_ast_build_free(build
);
268 /* Set the iterators for the next code generation.
270 * If we still have some iterators left from the previous code generation
271 * (if any) or if iterators have already been set by a previous
272 * call to this function, then we remove them first.
274 __isl_give isl_ast_build
*isl_ast_build_set_iterators(
275 __isl_take isl_ast_build
*build
, __isl_take isl_id_list
*iterators
)
279 build
= isl_ast_build_cow(build
);
283 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
284 n_it
= isl_id_list_n_id(build
->iterators
);
286 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
287 "isl_ast_build in inconsistent state", goto error
);
289 build
->iterators
= isl_id_list_drop(build
->iterators
,
291 build
->iterators
= isl_id_list_concat(build
->iterators
, iterators
);
292 if (!build
->iterators
)
293 return isl_ast_build_free(build
);
297 isl_id_list_free(iterators
);
298 return isl_ast_build_free(build
);
301 /* Set the "at_each_domain" callback of "build" to "fn".
303 __isl_give isl_ast_build
*isl_ast_build_set_at_each_domain(
304 __isl_take isl_ast_build
*build
,
305 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_node
*node
,
306 __isl_keep isl_ast_build
*build
, void *user
), void *user
)
308 build
= isl_ast_build_cow(build
);
313 build
->at_each_domain
= fn
;
314 build
->at_each_domain_user
= user
;
319 /* Set the "create_leaf" callback of "build" to "fn".
321 __isl_give isl_ast_build
*isl_ast_build_set_create_leaf(
322 __isl_take isl_ast_build
*build
,
323 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_build
*build
,
324 void *user
), void *user
)
326 build
= isl_ast_build_cow(build
);
331 build
->create_leaf
= fn
;
332 build
->create_leaf_user
= user
;
337 /* Clear all information that is specific to this code generation
338 * and that is (probably) not meaningful to any nested code generation.
340 __isl_give isl_ast_build
*isl_ast_build_clear_local_info(
341 __isl_take isl_ast_build
*build
)
345 build
= isl_ast_build_cow(build
);
349 space
= isl_union_map_get_space(build
->options
);
350 isl_union_map_free(build
->options
);
351 build
->options
= isl_union_map_empty(space
);
353 build
->at_each_domain
= NULL
;
354 build
->at_each_domain_user
= NULL
;
355 build
->create_leaf
= NULL
;
356 build
->create_leaf_user
= NULL
;
359 return isl_ast_build_free(build
);
364 /* Have any loops been eliminated?
365 * That is, do any of the original schedule dimensions have a fixed
366 * value that has been substituted?
368 static int any_eliminated(isl_ast_build
*build
)
372 for (i
= 0; i
< build
->depth
; ++i
)
373 if (isl_ast_build_has_affine_value(build
, i
))
379 /* Clear build->schedule_map.
380 * This function should be called whenever anything that might affect
381 * the result of isl_ast_build_get_schedule_map_multi_aff changes.
382 * In particular, it should be called when the depth is changed or
383 * when an iterator is determined to have a fixed value.
385 static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build
*build
)
389 isl_multi_aff_free(build
->schedule_map
);
390 build
->schedule_map
= NULL
;
393 /* Do we need a (non-trivial) schedule map?
394 * That is, is the internal schedule space different from
395 * the external schedule space?
397 * The internal and external schedule spaces are only the same
398 * if code has been generated for the entire schedule and if none
399 * of the loops have been eliminated.
401 __isl_give
int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build
*build
)
408 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
409 return build
->depth
!= dim
|| any_eliminated(build
);
412 /* Return a mapping from the internal schedule space to the external
413 * schedule space in the form of an isl_multi_aff.
414 * The internal schedule space originally corresponds to that of the
415 * input schedule. This may change during the code generation if
416 * if isl_ast_build_insert_dim is ever called.
417 * The external schedule space corresponds to the
418 * loops that have been generated.
420 * Currently, the only difference between the internal schedule domain
421 * and the external schedule domain is that some dimensions are projected
422 * out in the external schedule domain. In particular, the dimensions
423 * for which no code has been generated yet and the dimensions that correspond
424 * to eliminated loops.
426 * We cache a copy of the schedule_map in build->schedule_map.
427 * The cache is cleared through isl_ast_build_reset_schedule_map
428 * whenever anything changes that might affect the result of this function.
430 __isl_give isl_multi_aff
*isl_ast_build_get_schedule_map_multi_aff(
431 __isl_keep isl_ast_build
*build
)
438 if (build
->schedule_map
)
439 return isl_multi_aff_copy(build
->schedule_map
);
441 space
= isl_ast_build_get_space(build
, 1);
442 space
= isl_space_map_from_set(space
);
443 ma
= isl_multi_aff_identity(space
);
444 if (isl_ast_build_need_schedule_map(build
)) {
446 int dim
= isl_set_dim(build
->domain
, isl_dim_set
);
447 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
,
448 build
->depth
, dim
- build
->depth
);
449 for (i
= build
->depth
- 1; i
>= 0; --i
)
450 if (isl_ast_build_has_affine_value(build
, i
))
451 ma
= isl_multi_aff_drop_dims(ma
,
455 build
->schedule_map
= ma
;
456 return isl_multi_aff_copy(build
->schedule_map
);
459 /* Return a mapping from the internal schedule space to the external
460 * schedule space in the form of an isl_map.
462 __isl_give isl_map
*isl_ast_build_get_schedule_map(
463 __isl_keep isl_ast_build
*build
)
467 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
468 return isl_map_from_multi_aff(ma
);
471 /* Return the position of the dimension in build->domain for which
472 * an AST node is currently being generated.
474 int isl_ast_build_get_depth(__isl_keep isl_ast_build
*build
)
476 return build
? build
->depth
: -1;
479 /* Prepare for generating code for the next level.
480 * In particular, increase the depth and reset any information
481 * that is local to the current depth.
483 __isl_give isl_ast_build
*isl_ast_build_increase_depth(
484 __isl_take isl_ast_build
*build
)
486 build
= isl_ast_build_cow(build
);
490 isl_ast_build_reset_schedule_map(build
);
491 build
->value
= isl_pw_aff_free(build
->value
);
495 void isl_ast_build_dump(__isl_keep isl_ast_build
*build
)
500 fprintf(stderr
, "domain: ");
501 isl_set_dump(build
->domain
);
502 fprintf(stderr
, "generated: ");
503 isl_set_dump(build
->generated
);
504 fprintf(stderr
, "pending: ");
505 isl_set_dump(build
->pending
);
506 fprintf(stderr
, "iterators: ");
507 isl_id_list_dump(build
->iterators
);
508 fprintf(stderr
, "values: ");
509 isl_multi_aff_dump(build
->values
);
511 fprintf(stderr
, "value: ");
512 isl_pw_aff_dump(build
->value
);
514 fprintf(stderr
, "strides: ");
515 isl_vec_dump(build
->strides
);
516 fprintf(stderr
, "offsets: ");
517 isl_multi_aff_dump(build
->offsets
);
520 /* Initialize "build" for AST construction in schedule space "space"
521 * in the case that build->domain is a parameter set.
523 * build->iterators is assumed to have been updated already.
525 static __isl_give isl_ast_build
*isl_ast_build_init(
526 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
530 build
= isl_ast_build_cow(build
);
534 set
= isl_set_universe(isl_space_copy(space
));
535 build
->domain
= isl_set_intersect_params(isl_set_copy(set
),
537 build
->pending
= isl_set_intersect_params(isl_set_copy(set
),
539 build
->generated
= isl_set_intersect_params(set
, build
->generated
);
541 return isl_ast_build_init_derived(build
, space
);
543 isl_ast_build_free(build
);
544 isl_space_free(space
);
548 /* Assign "aff" to *user and return -1, effectively extracting
549 * the first (and presumably only) affine expression in the isl_pw_aff
550 * on which this function is used.
552 static int extract_single_piece(__isl_take isl_set
*set
,
553 __isl_take isl_aff
*aff
, void *user
)
563 /* Check if the given bounds on the current dimension imply that
564 * this current dimension attains only a single value (in terms of
565 * parameters and outer dimensions).
566 * If so, we record it in build->value.
567 * If, moreover, this value can be represented as a single affine expression,
568 * then we also update build->values, effectively marking the current
569 * dimension as "eliminated".
571 * When computing the gist of the fixed value that can be represented
572 * as a single affine expression, it is important to only take into
573 * account the domain constraints in the original AST build and
574 * not the domain of the affine expression itself.
575 * Otherwise, a [i/3] is changed into a i/3 because we know that i
576 * is a multiple of 3, but then we end up not expressing anywhere
577 * in the context that i is a multiple of 3.
579 static __isl_give isl_ast_build
*update_values(
580 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
583 isl_pw_multi_aff
*pma
;
588 set
= isl_set_from_basic_set(bounds
);
589 set
= isl_set_intersect(set
, isl_set_copy(build
->domain
));
590 it_map
= isl_ast_build_map_to_iterator(build
, set
);
592 sv
= isl_map_is_single_valued(it_map
);
594 build
= isl_ast_build_free(build
);
596 isl_map_free(it_map
);
600 pma
= isl_pw_multi_aff_from_map(it_map
);
601 build
->value
= isl_pw_multi_aff_get_pw_aff(pma
, 0);
602 build
->value
= isl_ast_build_compute_gist_pw_aff(build
, build
->value
);
603 build
->value
= isl_pw_aff_coalesce(build
->value
);
604 isl_pw_multi_aff_free(pma
);
607 return isl_ast_build_free(build
);
609 if (isl_pw_aff_n_piece(build
->value
) != 1)
612 isl_pw_aff_foreach_piece(build
->value
, &extract_single_piece
, &aff
);
614 build
->values
= isl_multi_aff_set_aff(build
->values
, build
->depth
, aff
);
616 return isl_ast_build_free(build
);
617 isl_ast_build_reset_schedule_map(build
);
621 /* Update the AST build based on the given loop bounds for
622 * the current dimension.
624 * We first make sure that the bounds do not refer to any iterators
625 * that have already been eliminated.
626 * Then, we check if the bounds imply that the current iterator
628 * If they do and if this fixed value can be expressed as a single
629 * affine expression, we eliminate the iterators from the bounds.
630 * Note that we cannot simply plug in this single value using
631 * isl_basic_set_preimage_multi_aff as the single value may only
632 * be defined on a subset of the domain. Plugging in the value
633 * would restrict the build domain to this subset, while this
634 * restriction may not be reflected in the generated code.
635 * build->domain may, however, already refer to the current dimension
636 * due an earlier call to isl_ast_build_include_stride. If so, we need
637 * to eliminate the dimension so that we do not introduce it in any other sets.
638 * Finally, we intersect build->domain with the updated bounds.
640 * Note that the check for a fixed value in update_values requires
641 * us to intersect the bounds with the current build domain.
642 * When we intersect build->domain with the updated bounds in
643 * the final step, we make sure that these updated bounds have
644 * not been intersected with the old build->domain.
645 * Otherwise, we would indirectly intersect the build domain with itself,
646 * which can lead to inefficiencies, in particular if the build domain
647 * contains any unknown divs.
649 __isl_give isl_ast_build
*isl_ast_build_set_loop_bounds(
650 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
654 build
= isl_ast_build_cow(build
);
658 bounds
= isl_basic_set_preimage_multi_aff(bounds
,
659 isl_multi_aff_copy(build
->values
));
660 build
= update_values(build
, isl_basic_set_copy(bounds
));
663 set
= isl_set_from_basic_set(isl_basic_set_copy(bounds
));
664 if (isl_ast_build_has_affine_value(build
, build
->depth
)) {
665 set
= isl_set_eliminate(set
, isl_dim_set
, build
->depth
, 1);
666 set
= isl_set_compute_divs(set
);
667 build
->pending
= isl_set_intersect(build
->pending
,
669 if (isl_ast_build_has_stride(build
, build
->depth
))
670 build
->domain
= isl_set_eliminate(build
->domain
,
671 isl_dim_set
, build
->depth
, 1);
673 isl_basic_set
*generated
, *pending
;
675 pending
= isl_basic_set_copy(bounds
);
676 pending
= isl_basic_set_drop_constraints_involving_dims(pending
,
677 isl_dim_set
, build
->depth
, 1);
678 build
->pending
= isl_set_intersect(build
->pending
,
679 isl_set_from_basic_set(pending
));
680 generated
= isl_basic_set_copy(bounds
);
681 generated
= isl_basic_set_drop_constraints_not_involving_dims(
682 generated
, isl_dim_set
, build
->depth
, 1);
683 build
->generated
= isl_set_intersect(build
->generated
,
684 isl_set_from_basic_set(generated
));
686 isl_basic_set_free(bounds
);
688 build
->domain
= isl_set_intersect(build
->domain
, set
);
689 if (!build
->domain
|| !build
->pending
|| !build
->generated
)
690 return isl_ast_build_free(build
);
694 isl_ast_build_free(build
);
695 isl_basic_set_free(bounds
);
699 /* Update build->domain based on the constraints enforced by inner loops.
701 * The constraints in build->pending may end up not getting generated
702 * if they are implied by "enforced". We therefore reconstruct
703 * build->domain from build->generated and build->pending, dropping
704 * those constraint in build->pending that may not get generated.
706 __isl_give isl_ast_build
*isl_ast_build_set_enforced(
707 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*enforced
)
711 build
= isl_ast_build_cow(build
);
715 set
= isl_set_from_basic_set(enforced
);
716 set
= isl_set_gist(isl_set_copy(build
->pending
), set
);
717 set
= isl_set_intersect(isl_set_copy(build
->generated
), set
);
719 isl_set_free(build
->domain
);
723 return isl_ast_build_free(build
);
727 isl_basic_set_free(enforced
);
728 return isl_ast_build_free(build
);
731 /* Intersect build->domain with "set", where "set" is specified
732 * in terms of the internal schedule domain.
734 static __isl_give isl_ast_build
*isl_ast_build_restrict_internal(
735 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
737 build
= isl_ast_build_cow(build
);
741 set
= isl_set_compute_divs(set
);
742 build
->domain
= isl_set_intersect(build
->domain
, set
);
743 build
->domain
= isl_set_coalesce(build
->domain
);
746 return isl_ast_build_free(build
);
750 isl_ast_build_free(build
);
755 /* Intersect build->generated and build->domain with "set",
756 * where "set" is specified in terms of the internal schedule domain.
758 __isl_give isl_ast_build
*isl_ast_build_restrict_generated(
759 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
761 set
= isl_set_compute_divs(set
);
762 build
= isl_ast_build_restrict_internal(build
, isl_set_copy(set
));
763 build
= isl_ast_build_cow(build
);
767 build
->generated
= isl_set_intersect(build
->generated
, set
);
768 build
->generated
= isl_set_coalesce(build
->generated
);
770 if (!build
->generated
)
771 return isl_ast_build_free(build
);
775 isl_ast_build_free(build
);
780 /* Intersect build->pending and build->domain with "set",
781 * where "set" is specified in terms of the internal schedule domain.
783 __isl_give isl_ast_build
*isl_ast_build_restrict_pending(
784 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
786 set
= isl_set_compute_divs(set
);
787 build
= isl_ast_build_restrict_internal(build
, isl_set_copy(set
));
788 build
= isl_ast_build_cow(build
);
792 build
->pending
= isl_set_intersect(build
->pending
, set
);
793 build
->pending
= isl_set_coalesce(build
->pending
);
796 return isl_ast_build_free(build
);
800 isl_ast_build_free(build
);
805 /* Intersect build->domain with "set", where "set" is specified
806 * in terms of the external schedule domain.
808 __isl_give isl_ast_build
*isl_ast_build_restrict(
809 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
811 if (isl_set_is_params(set
))
812 return isl_ast_build_restrict_generated(build
, set
);
814 if (isl_ast_build_need_schedule_map(build
)) {
816 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
817 set
= isl_set_preimage_multi_aff(set
, ma
);
819 return isl_ast_build_restrict_generated(build
, set
);
822 /* Replace build->executed by "executed".
824 __isl_give isl_ast_build
*isl_ast_build_set_executed(
825 __isl_take isl_ast_build
*build
, __isl_take isl_union_map
*executed
)
827 build
= isl_ast_build_cow(build
);
831 isl_union_map_free(build
->executed
);
832 build
->executed
= executed
;
836 isl_ast_build_free(build
);
837 isl_union_map_free(executed
);
841 /* Return a copy of the current schedule domain.
843 __isl_give isl_set
*isl_ast_build_get_domain(__isl_keep isl_ast_build
*build
)
845 return build
? isl_set_copy(build
->domain
) : NULL
;
848 /* Return the (schedule) space of "build".
850 * If "internal" is set, then this space is the space of the internal
851 * representation of the entire schedule, including those parts for
852 * which no code has been generated yet.
854 * If "internal" is not set, then this space is the external representation
855 * of the loops generated so far.
857 __isl_give isl_space
*isl_ast_build_get_space(__isl_keep isl_ast_build
*build
,
867 space
= isl_set_get_space(build
->domain
);
871 if (!isl_ast_build_need_schedule_map(build
))
874 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
875 space
= isl_space_drop_dims(space
, isl_dim_set
,
876 build
->depth
, dim
- build
->depth
);
877 for (i
= build
->depth
- 1; i
>= 0; --i
)
878 if (isl_ast_build_has_affine_value(build
, i
))
879 space
= isl_space_drop_dims(space
, isl_dim_set
, i
, 1);
884 /* Return the external representation of the schedule space of "build",
885 * i.e., a space with a dimension for each loop generated so far,
886 * with the names of the dimensions set to the loop iterators.
888 __isl_give isl_space
*isl_ast_build_get_schedule_space(
889 __isl_keep isl_ast_build
*build
)
897 space
= isl_ast_build_get_space(build
, 0);
900 for (i
= 0; i
< build
->depth
; ++i
) {
903 if (isl_ast_build_has_affine_value(build
, i
)) {
908 id
= isl_ast_build_get_iterator_id(build
, i
);
909 space
= isl_space_set_dim_id(space
, isl_dim_set
, i
- skip
, id
);
915 /* Return the current schedule, as stored in build->executed, in terms
916 * of the external schedule domain.
918 __isl_give isl_union_map
*isl_ast_build_get_schedule(
919 __isl_keep isl_ast_build
*build
)
921 isl_union_map
*executed
;
922 isl_union_map
*schedule
;
927 executed
= isl_union_map_copy(build
->executed
);
928 if (isl_ast_build_need_schedule_map(build
)) {
929 isl_map
*proj
= isl_ast_build_get_schedule_map(build
);
930 executed
= isl_union_map_apply_domain(executed
,
931 isl_union_map_from_map(proj
));
933 schedule
= isl_union_map_reverse(executed
);
938 /* Return the iterator attached to the internal schedule dimension "pos".
940 __isl_give isl_id
*isl_ast_build_get_iterator_id(
941 __isl_keep isl_ast_build
*build
, int pos
)
946 return isl_id_list_get_id(build
->iterators
, pos
);
949 /* Set the stride and offset of the current dimension to the given
950 * value and expression.
952 static __isl_give isl_ast_build
*set_stride(__isl_take isl_ast_build
*build
,
953 isl_int stride
, __isl_take isl_aff
*offset
)
957 build
= isl_ast_build_cow(build
);
958 if (!build
|| !offset
)
962 build
->strides
= isl_vec_set_element(build
->strides
, pos
, stride
);
963 build
->offsets
= isl_multi_aff_set_aff(build
->offsets
, pos
, offset
);
964 if (!build
->strides
|| !build
->offsets
)
965 return isl_ast_build_free(build
);
969 isl_aff_free(offset
);
970 return isl_ast_build_free(build
);
973 /* Return a set expressing the stride constraint at the current depth.
975 * In particular, if the current iterator (i) is known to attain values
979 * where f is the offset and s is the stride, then the returned set
980 * expresses the constraint
984 __isl_give isl_set
*isl_ast_build_get_stride_constraint(
985 __isl_keep isl_ast_build
*build
)
997 if (!isl_ast_build_has_stride(build
, pos
))
998 return isl_set_universe(isl_ast_build_get_space(build
, 1));
1000 isl_int_init(stride
);
1002 isl_ast_build_get_stride(build
, pos
, &stride
);
1003 aff
= isl_ast_build_get_offset(build
, pos
);
1004 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, pos
, -1);
1005 aff
= isl_aff_mod(aff
, stride
);
1006 set
= isl_set_from_basic_set(isl_aff_zero_basic_set(aff
));
1008 isl_int_clear(stride
);
1013 /* Return the expansion implied by the stride and offset at the current
1016 * That is, return the mapping
1018 * [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1019 * -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]
1021 * where s is the stride at the current depth d and offset(i) is
1022 * the corresponding offset.
1024 __isl_give isl_multi_aff
*isl_ast_build_get_stride_expansion(
1025 __isl_keep isl_ast_build
*build
)
1030 isl_aff
*aff
, *offset
;
1036 pos
= isl_ast_build_get_depth(build
);
1037 space
= isl_ast_build_get_space(build
, 1);
1038 space
= isl_space_map_from_set(space
);
1039 ma
= isl_multi_aff_identity(space
);
1041 if (!isl_ast_build_has_stride(build
, pos
))
1044 isl_int_init(stride
);
1045 offset
= isl_ast_build_get_offset(build
, pos
);
1046 isl_ast_build_get_stride(build
, pos
, &stride
);
1047 aff
= isl_multi_aff_get_aff(ma
, pos
);
1048 aff
= isl_aff_scale(aff
, stride
);
1049 aff
= isl_aff_add(aff
, offset
);
1050 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
1051 isl_int_clear(stride
);
1056 /* Add constraints corresponding to any previously detected
1057 * stride on the current dimension to build->domain.
1059 __isl_give isl_ast_build
*isl_ast_build_include_stride(
1060 __isl_take isl_ast_build
*build
)
1066 if (!isl_ast_build_has_stride(build
, build
->depth
))
1068 build
= isl_ast_build_cow(build
);
1072 set
= isl_ast_build_get_stride_constraint(build
);
1074 build
->domain
= isl_set_intersect(build
->domain
, isl_set_copy(set
));
1075 build
->generated
= isl_set_intersect(build
->generated
, set
);
1076 if (!build
->domain
|| !build
->generated
)
1077 return isl_ast_build_free(build
);
1082 /* Compute x, y and g such that g = gcd(a,b) and a*x+b*y = g */
1083 static void euclid(isl_int a
, isl_int b
, isl_int
*x
, isl_int
*y
, isl_int
*g
)
1085 isl_int c
, d
, e
, f
, tmp
;
1094 isl_int_set_si(e
, 1);
1095 isl_int_set_si(f
, 0);
1096 while (isl_int_is_pos(d
)) {
1097 isl_int_tdiv_q(tmp
, c
, d
);
1098 isl_int_mul(tmp
, tmp
, f
);
1099 isl_int_sub(e
, e
, tmp
);
1100 isl_int_tdiv_q(tmp
, c
, d
);
1101 isl_int_mul(tmp
, tmp
, d
);
1102 isl_int_sub(c
, c
, tmp
);
1107 if (isl_int_is_zero(a
))
1108 isl_int_set_si(*x
, 0);
1109 else if (isl_int_is_pos(a
))
1113 if (isl_int_is_zero(b
))
1114 isl_int_set_si(*y
, 0);
1116 isl_int_mul(tmp
, a
, *x
);
1117 isl_int_sub(tmp
, c
, tmp
);
1118 isl_int_divexact(*y
, tmp
, b
);
1127 /* Information used inside detect_stride.
1129 * "build" may be updated by detect_stride to include stride information.
1130 * "pos" is equal to build->depth.
1132 struct isl_detect_stride_data
{
1133 isl_ast_build
*build
;
1137 /* Check if constraint "c" imposes any stride on dimension data->pos
1138 * and, if so, update the stride information in data->build.
1140 * In order to impose a stride on the dimension, "c" needs to be an equality
1141 * and it needs to involve the dimension. Note that "c" may also be
1142 * a div constraint and thus an inequality that we cannot use.
1144 * Let c be of the form
1146 * h(p) + g * v * i + g * stride * f(alpha) = 0
1148 * with h(p) an expression in terms of the parameters and outer dimensions
1149 * and f(alpha) an expression in terms of the existentially quantified
1150 * variables. Note that the inner dimensions have been eliminated so
1151 * they do not appear in "c".
1153 * If "stride" is not zero and not one, then it represents a non-trivial stride
1154 * on "i". We compute a and b such that
1156 * a v + b stride = 1
1160 * g v i = -h(p) + g stride f(alpha)
1162 * a g v i = -a h(p) + g stride f(alpha)
1164 * a g v i + b g stride i = -a h(p) + g stride * (...)
1166 * g i = -a h(p) + g stride * (...)
1168 * i = -a h(p)/g + stride * (...)
1170 * The expression "-a h(p)/g" can therefore be used as offset.
1172 static int detect_stride(__isl_take isl_constraint
*c
, void *user
)
1174 struct isl_detect_stride_data
*data
= user
;
1176 isl_int v
, gcd
, stride
, a
, b
, m
;
1178 if (!isl_constraint_is_equality(c
) ||
1179 !isl_constraint_involves_dims(c
, isl_dim_set
, data
->pos
, 1)) {
1180 isl_constraint_free(c
);
1189 isl_int_init(stride
);
1191 isl_int_set_si(gcd
, 0);
1192 n_div
= isl_constraint_dim(c
, isl_dim_div
);
1193 for (i
= 0; i
< n_div
; ++i
) {
1194 isl_constraint_get_coefficient(c
, isl_dim_div
, i
, &v
);
1195 isl_int_gcd(gcd
, gcd
, v
);
1198 isl_constraint_get_coefficient(c
, isl_dim_set
, data
->pos
, &v
);
1199 isl_int_gcd(m
, v
, gcd
);
1200 isl_int_divexact(stride
, gcd
, m
);
1201 isl_int_divexact(v
, v
, m
);
1203 if (!isl_int_is_zero(stride
) && !isl_int_is_one(stride
)) {
1206 euclid(v
, stride
, &a
, &b
, &gcd
);
1208 aff
= isl_constraint_get_aff(c
);
1209 for (i
= 0; i
< n_div
; ++i
)
1210 aff
= isl_aff_set_coefficient_si(aff
,
1212 aff
= isl_aff_set_coefficient_si(aff
, isl_dim_in
, data
->pos
, 0);
1214 aff
= isl_aff_scale(aff
, a
);
1215 aff
= isl_aff_scale_down(aff
, m
);
1216 data
->build
= set_stride(data
->build
, stride
, aff
);
1219 isl_int_clear(stride
);
1226 isl_constraint_free(c
);
1230 /* Check if the constraints in "set" imply any stride on the current
1231 * dimension and, if so, record the stride information in "build"
1232 * and return the updated "build".
1234 * We compute the affine hull and then check if any of the constraints
1235 * in the hull imposes any stride on the current dimension.
1237 * We assume that inner dimensions have been eliminated from "set"
1238 * by the caller. This is needed because the common stride
1239 * may be imposed by different inner dimensions on different parts of
1242 __isl_give isl_ast_build
*isl_ast_build_detect_strides(
1243 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
1245 isl_basic_set
*hull
;
1246 struct isl_detect_stride_data data
;
1252 data
.pos
= isl_ast_build_get_depth(build
);
1253 hull
= isl_set_affine_hull(set
);
1255 if (isl_basic_set_foreach_constraint(hull
, &detect_stride
, &data
) < 0)
1256 data
.build
= isl_ast_build_free(data
.build
);
1258 isl_basic_set_free(hull
);
1265 struct isl_ast_build_involves_data
{
1270 /* Check if "map" involves the input dimension data->depth.
1272 static int involves_depth(__isl_take isl_map
*map
, void *user
)
1274 struct isl_ast_build_involves_data
*data
= user
;
1276 data
->involves
= isl_map_involves_dims(map
, isl_dim_in
, data
->depth
, 1);
1279 if (data
->involves
< 0 || data
->involves
)
1284 /* Do any options depend on the value of the dimension at the current depth?
1286 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build
*build
)
1288 struct isl_ast_build_involves_data data
;
1293 data
.depth
= build
->depth
;
1296 if (isl_union_map_foreach_map(build
->options
,
1297 &involves_depth
, &data
) < 0) {
1298 if (data
.involves
< 0 || !data
.involves
)
1302 return data
.involves
;
1305 /* Construct the map
1307 * { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1309 * with "space" the parameter space of the constructed map.
1311 static __isl_give isl_map
*construct_insertion_map(__isl_take isl_space
*space
,
1315 isl_basic_map
*bmap1
, *bmap2
;
1317 space
= isl_space_set_from_params(space
);
1318 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1319 space
= isl_space_map_from_set(space
);
1320 c
= isl_equality_alloc(isl_local_space_from_space(space
));
1321 c
= isl_constraint_set_coefficient_si(c
, isl_dim_in
, 0, 1);
1322 c
= isl_constraint_set_coefficient_si(c
, isl_dim_out
, 0, -1);
1323 bmap1
= isl_basic_map_from_constraint(isl_constraint_copy(c
));
1324 c
= isl_constraint_set_constant_si(c
, 1);
1325 bmap2
= isl_basic_map_from_constraint(c
);
1327 bmap1
= isl_basic_map_upper_bound_si(bmap1
, isl_dim_in
, 0, pos
- 1);
1328 bmap2
= isl_basic_map_lower_bound_si(bmap2
, isl_dim_in
, 0, pos
);
1330 return isl_basic_map_union(bmap1
, bmap2
);
1333 static const char *option_str
[] = {
1334 [atomic
] = "atomic",
1335 [unroll
] = "unroll",
1336 [separate
] = "separate"
1339 /* Update the "options" to reflect the insertion of a dimension
1340 * at position "pos" in the schedule domain space.
1341 * "space" is the original domain space before the insertion and
1342 * may be named and/or structured.
1344 * The (relevant) input options all have "space" as domain, which
1345 * has to be mapped to the extended space.
1346 * The values of the ranges also refer to the schedule domain positions
1347 * and they therefore also need to be adjusted. In particular, values
1348 * smaller than pos do not need to change, while values greater than or
1349 * equal to pos need to be incremented.
1350 * That is, we need to apply the following map.
1352 * { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1353 * unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1354 * separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1355 * separation_class[[i] -> [c]]
1356 * -> separation_class[[i] -> [c]] : i < pos;
1357 * separation_class[[i] -> [c]]
1358 * -> separation_class[[i + 1] -> [c]] : i >= pos }
1360 static __isl_give isl_union_map
*options_insert_dim(
1361 __isl_take isl_union_map
*options
, __isl_take isl_space
*space
, int pos
)
1364 isl_union_map
*insertion
;
1365 enum isl_ast_build_domain_type type
;
1366 const char *name
= "separation_class";
1368 space
= isl_space_map_from_set(space
);
1369 map
= isl_map_identity(space
);
1370 map
= isl_map_insert_dims(map
, isl_dim_out
, pos
, 1);
1371 options
= isl_union_map_apply_domain(options
,
1372 isl_union_map_from_map(map
));
1377 map
= construct_insertion_map(isl_union_map_get_space(options
), pos
);
1379 insertion
= isl_union_map_empty(isl_union_map_get_space(options
));
1381 for (type
= atomic
; type
<= separate
; ++type
) {
1382 isl_map
*map_type
= isl_map_copy(map
);
1383 const char *name
= option_str
[type
];
1384 map_type
= isl_map_set_tuple_name(map_type
, isl_dim_in
, name
);
1385 map_type
= isl_map_set_tuple_name(map_type
, isl_dim_out
, name
);
1386 insertion
= isl_union_map_add_map(insertion
, map_type
);
1389 map
= isl_map_product(map
, isl_map_identity(isl_map_get_space(map
)));
1390 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
1391 map
= isl_map_set_tuple_name(map
, isl_dim_out
, name
);
1392 insertion
= isl_union_map_add_map(insertion
, map
);
1394 options
= isl_union_map_apply_range(options
, insertion
);
1399 /* Insert a single dimension in the schedule domain at position "pos".
1400 * The new dimension is given an isl_id with the empty string as name.
1402 * The main difficulty is updating build->options to reflect the
1403 * extra dimension. This is handled in options_insert_dim.
1405 * Note that because of the dimension manipulations, the resulting
1406 * schedule domain space will always be unnamed and unstructured.
1407 * However, the original schedule domain space may be named and/or
1408 * structured, so we have to take this possibility into account
1409 * while performing the transformations.
1411 __isl_give isl_ast_build
*isl_ast_build_insert_dim(
1412 __isl_take isl_ast_build
*build
, int pos
)
1415 isl_space
*space
, *ma_space
;
1419 build
= isl_ast_build_cow(build
);
1423 ctx
= isl_ast_build_get_ctx(build
);
1424 id
= isl_id_alloc(ctx
, "", NULL
);
1425 space
= isl_ast_build_get_space(build
, 1);
1426 build
->iterators
= isl_id_list_insert(build
->iterators
, pos
, id
);
1427 build
->domain
= isl_set_insert_dims(build
->domain
,
1428 isl_dim_set
, pos
, 1);
1429 build
->generated
= isl_set_insert_dims(build
->generated
,
1430 isl_dim_set
, pos
, 1);
1431 build
->pending
= isl_set_insert_dims(build
->pending
,
1432 isl_dim_set
, pos
, 1);
1433 build
->strides
= isl_vec_insert_els(build
->strides
, pos
, 1);
1434 build
->strides
= isl_vec_set_element_si(build
->strides
, pos
, 1);
1435 ma_space
= isl_space_params(isl_multi_aff_get_space(build
->offsets
));
1436 ma_space
= isl_space_set_from_params(ma_space
);
1437 ma_space
= isl_space_add_dims(ma_space
, isl_dim_set
, 1);
1438 ma_space
= isl_space_map_from_set(ma_space
);
1439 ma
= isl_multi_aff_zero(isl_space_copy(ma_space
));
1440 build
->offsets
= isl_multi_aff_splice(build
->offsets
, pos
, pos
, ma
);
1441 ma
= isl_multi_aff_identity(ma_space
);
1442 build
->values
= isl_multi_aff_splice(build
->values
, pos
, pos
, ma
);
1443 build
->options
= options_insert_dim(build
->options
, space
, pos
);
1445 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
1446 !build
->pending
|| !build
->values
||
1447 !build
->strides
|| !build
->offsets
|| !build
->options
)
1448 return isl_ast_build_free(build
);
1453 /* Scale down the current dimension by a factor of "m".
1454 * "umap" is an isl_union_map that implements the scaling down.
1455 * That is, it is of the form
1457 * { [.... i ....] -> [.... i' ....] : i = m i' }
1459 * This function is called right after the strides have been
1460 * detected, but before any constraints on the current dimension
1461 * have been included in build->domain.
1462 * We therefore only need to update stride, offset and the options.
1464 __isl_give isl_ast_build
*isl_ast_build_scale_down(
1465 __isl_take isl_ast_build
*build
, isl_int m
,
1466 __isl_take isl_union_map
*umap
)
1472 build
= isl_ast_build_cow(build
);
1473 if (!build
|| !umap
)
1476 depth
= build
->depth
;
1479 if (isl_vec_get_element(build
->strides
, depth
, &v
) < 0)
1480 build
->strides
= isl_vec_free(build
->strides
);
1481 isl_int_divexact(v
, v
, m
);
1482 build
->strides
= isl_vec_set_element(build
->strides
, depth
, v
);
1485 aff
= isl_multi_aff_get_aff(build
->offsets
, depth
);
1486 aff
= isl_aff_scale_down(aff
, m
);
1487 build
->offsets
= isl_multi_aff_set_aff(build
->offsets
, depth
, aff
);
1488 build
->options
= isl_union_map_apply_domain(build
->options
, umap
);
1489 if (!build
->strides
|| !build
->offsets
|| !build
->options
)
1490 return isl_ast_build_free(build
);
1494 isl_union_map_free(umap
);
1495 return isl_ast_build_free(build
);
1498 /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1499 * If an isl_id with such a name already appears among the parameters
1500 * in build->domain, then adjust the name to "c%d_%d".
1502 static __isl_give isl_id_list
*generate_names(isl_ctx
*ctx
, int n
, int first
,
1503 __isl_keep isl_ast_build
*build
)
1508 isl_set
*dom
= build
->domain
;
1510 names
= isl_id_list_alloc(ctx
, n
);
1511 for (i
= 0; i
< n
; ++i
) {
1514 snprintf(name
, sizeof(name
), "c%d", first
+ i
);
1516 while (isl_set_find_dim_by_name(dom
, isl_dim_param
, name
) >= 0)
1517 snprintf(name
, sizeof(name
), "c%d_%d", first
+ i
, j
++);
1518 id
= isl_id_alloc(ctx
, name
, NULL
);
1519 names
= isl_id_list_add(names
, id
);
1525 /* Embed "options" into the given isl_ast_build space.
1527 * This function is called from within a nested call to
1528 * isl_ast_build_ast_from_schedule.
1529 * "options" refers to the additional schedule,
1530 * while space refers to both the space of the outer isl_ast_build and
1531 * that of the additional schedule.
1532 * Specifically, space is of the form
1536 * while options lives in the space(s)
1544 * and compose this with options, to obtain the new options
1545 * living in the space(s)
1549 static __isl_give isl_union_map
*embed_options(
1550 __isl_take isl_union_map
*options
, __isl_take isl_space
*space
)
1554 map
= isl_map_universe(isl_space_unwrap(space
));
1555 map
= isl_map_range_map(map
);
1557 options
= isl_union_map_apply_range(
1558 isl_union_map_from_map(map
), options
);
1563 /* Update "build" for use in a (possibly nested) code generation. That is,
1564 * extend "build" from an AST build on some domain O to an AST build
1565 * on domain [O -> S], with S corresponding to "space".
1566 * If the original domain is a parameter domain, then the new domain is
1568 * "iterators" is a list of iterators for S, but the number of elements
1569 * may be smaller or greater than the number of set dimensions of S.
1570 * If "keep_iterators" is set, then any extra ids in build->iterators
1571 * are reused for S. Otherwise, these extra ids are dropped.
1573 * We first update build->outer_pos to the current depth.
1574 * This depth is zero in case this is the outermost code generation.
1576 * We then add additional ids such that the number of iterators is at least
1577 * equal to the dimension of the new build domain.
1579 * If the original domain is parametric, then we are constructing
1580 * an isl_ast_build for the outer code generation and we pass control
1581 * to isl_ast_build_init.
1583 * Otherwise, we adjust the fields of "build" to include "space".
1585 __isl_give isl_ast_build
*isl_ast_build_product(
1586 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
1591 isl_multi_aff
*embedding
;
1594 build
= isl_ast_build_cow(build
);
1598 build
->outer_pos
= build
->depth
;
1600 ctx
= isl_ast_build_get_ctx(build
);
1601 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
1602 dim
+= isl_space_dim(space
, isl_dim_set
);
1603 n_it
= isl_id_list_n_id(build
->iterators
);
1606 l
= generate_names(ctx
, dim
- n_it
, n_it
, build
);
1607 build
->iterators
= isl_id_list_concat(build
->iterators
, l
);
1610 if (isl_set_is_params(build
->domain
))
1611 return isl_ast_build_init(build
, space
);
1613 set
= isl_set_universe(isl_space_copy(space
));
1614 build
->domain
= isl_set_product(build
->domain
, isl_set_copy(set
));
1615 build
->pending
= isl_set_product(build
->pending
, isl_set_copy(set
));
1616 build
->generated
= isl_set_product(build
->generated
, set
);
1618 strides
= isl_vec_alloc(ctx
, isl_space_dim(space
, isl_dim_set
));
1619 strides
= isl_vec_set_si(strides
, 1);
1620 build
->strides
= isl_vec_concat(build
->strides
, strides
);
1622 space
= isl_space_map_from_set(space
);
1623 build
->offsets
= isl_multi_aff_align_params(build
->offsets
,
1624 isl_space_copy(space
));
1625 build
->offsets
= isl_multi_aff_product(build
->offsets
,
1626 isl_multi_aff_zero(isl_space_copy(space
)));
1627 build
->values
= isl_multi_aff_align_params(build
->values
,
1628 isl_space_copy(space
));
1629 embedding
= isl_multi_aff_identity(space
);
1630 build
->values
= isl_multi_aff_product(build
->values
, embedding
);
1632 space
= isl_ast_build_get_space(build
, 1);
1633 build
->options
= embed_options(build
->options
, space
);
1635 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
1636 !build
->pending
|| !build
->values
||
1637 !build
->strides
|| !build
->offsets
|| !build
->options
)
1638 return isl_ast_build_free(build
);
1642 isl_ast_build_free(build
);
1643 isl_space_free(space
);
1647 /* Does "aff" only attain non-negative values over build->domain?
1648 * That is, does it not attain any negative values?
1650 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build
*build
,
1651 __isl_keep isl_aff
*aff
)
1659 aff
= isl_aff_copy(aff
);
1660 test
= isl_set_from_basic_set(isl_aff_neg_basic_set(aff
));
1661 test
= isl_set_intersect(test
, isl_set_copy(build
->domain
));
1662 empty
= isl_set_is_empty(test
);
1668 /* Does the dimension at (internal) position "pos" have a non-trivial stride?
1670 int isl_ast_build_has_stride(__isl_keep isl_ast_build
*build
, int pos
)
1679 isl_vec_get_element(build
->strides
, pos
, &v
);
1680 has_stride
= !isl_int_is_one(v
);
1686 /* Given that the dimension at position "pos" takes on values
1690 * with a an integer, return s through *stride.
1692 int isl_ast_build_get_stride(__isl_keep isl_ast_build
*build
, int pos
,
1698 isl_vec_get_element(build
->strides
, pos
, stride
);
1703 /* Given that the dimension at position "pos" takes on values
1707 * with a an integer, return f.
1709 __isl_give isl_aff
*isl_ast_build_get_offset(
1710 __isl_keep isl_ast_build
*build
, int pos
)
1715 return isl_multi_aff_get_aff(build
->offsets
, pos
);
1718 /* Is the dimension at position "pos" known to attain only a single
1719 * value that, moreover, can be described by a single affine expression
1720 * in terms of the outer dimensions and parameters?
1722 * If not, then the correponding affine expression in build->values
1723 * is set to be equal to the same input dimension.
1724 * Otherwise, it is set to the requested expression in terms of
1725 * outer dimensions and parameters.
1727 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build
*build
,
1736 aff
= isl_multi_aff_get_aff(build
->values
, pos
);
1737 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, pos
, 1);
1746 /* Is the current dimension known to attain only a single value?
1748 int isl_ast_build_has_value(__isl_keep isl_ast_build
*build
)
1753 return build
->value
!= NULL
;
1756 /* Simplify the basic set "bset" based on what we know about
1757 * the iterators of already generated loops.
1759 * "bset" is assumed to live in the (internal) schedule domain.
1761 __isl_give isl_basic_set
*isl_ast_build_compute_gist_basic_set(
1762 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
1767 bset
= isl_basic_set_preimage_multi_aff(bset
,
1768 isl_multi_aff_copy(build
->values
));
1769 bset
= isl_basic_set_gist(bset
,
1770 isl_set_simple_hull(isl_set_copy(build
->domain
)));
1774 isl_basic_set_free(bset
);
1778 /* Simplify the set "set" based on what we know about
1779 * the iterators of already generated loops.
1781 * "set" is assumed to live in the (internal) schedule domain.
1783 __isl_give isl_set
*isl_ast_build_compute_gist(
1784 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
1789 set
= isl_set_preimage_multi_aff(set
,
1790 isl_multi_aff_copy(build
->values
));
1791 set
= isl_set_gist(set
, isl_set_copy(build
->domain
));
1799 /* Simplify the map "map" based on what we know about
1800 * the iterators of already generated loops.
1802 * The domain of "map" is assumed to live in the (internal) schedule domain.
1804 __isl_give isl_map
*isl_ast_build_compute_gist_map_domain(
1805 __isl_keep isl_ast_build
*build
, __isl_take isl_map
*map
)
1810 map
= isl_map_gist_domain(map
, isl_set_copy(build
->domain
));
1818 /* Simplify the affine expression "aff" based on what we know about
1819 * the iterators of already generated loops.
1821 * The domain of "aff" is assumed to live in the (internal) schedule domain.
1823 __isl_give isl_aff
*isl_ast_build_compute_gist_aff(
1824 __isl_keep isl_ast_build
*build
, __isl_take isl_aff
*aff
)
1829 aff
= isl_aff_gist(aff
, isl_set_copy(build
->domain
));
1837 /* Simplify the piecewise affine expression "aff" based on what we know about
1838 * the iterators of already generated loops.
1840 * The domain of "pa" is assumed to live in the (internal) schedule domain.
1842 __isl_give isl_pw_aff
*isl_ast_build_compute_gist_pw_aff(
1843 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
1848 pa
= isl_pw_aff_pullback_multi_aff(pa
,
1849 isl_multi_aff_copy(build
->values
));
1850 pa
= isl_pw_aff_gist(pa
, isl_set_copy(build
->domain
));
1854 isl_pw_aff_free(pa
);
1858 /* Simplify the piecewise multi-affine expression "aff" based on what
1859 * we know about the iterators of already generated loops.
1861 * The domain of "pma" is assumed to live in the (internal) schedule domain.
1863 __isl_give isl_pw_multi_aff
*isl_ast_build_compute_gist_pw_multi_aff(
1864 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
1869 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
,
1870 isl_multi_aff_copy(build
->values
));
1871 pma
= isl_pw_multi_aff_gist(pma
, isl_set_copy(build
->domain
));
1875 isl_pw_multi_aff_free(pma
);
1879 /* Extract the schedule domain of the given type from build->options
1880 * at the current depth.
1882 * In particular, find the subset of build->options that is of
1883 * the following form
1885 * schedule_domain -> type[depth]
1887 * and return the corresponding domain, after eliminating inner dimensions
1888 * and divs that depend on the current dimension.
1890 * Note that the domain of build->options has been reformulated
1891 * in terms of the internal build space in embed_options,
1892 * but the position is still that within the current code generation.
1894 __isl_give isl_set
*isl_ast_build_get_option_domain(
1895 __isl_keep isl_ast_build
*build
,
1896 enum isl_ast_build_domain_type type
)
1907 name
= option_str
[type
];
1908 local_pos
= build
->depth
- build
->outer_pos
;
1910 space
= isl_ast_build_get_space(build
, 1);
1911 space
= isl_space_from_domain(space
);
1912 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
1913 space
= isl_space_set_tuple_name(space
, isl_dim_out
, name
);
1915 option
= isl_union_map_extract_map(build
->options
, space
);
1916 option
= isl_map_fix_si(option
, isl_dim_out
, 0, local_pos
);
1918 domain
= isl_map_domain(option
);
1919 domain
= isl_ast_build_eliminate(build
, domain
);
1924 /* Extract the separation class mapping at the current depth.
1926 * In particular, find and return the subset of build->options that is of
1927 * the following form
1929 * schedule_domain -> separation_class[[depth] -> [class]]
1931 * The caller is expected to eliminate inner dimensions from the domain.
1933 * Note that the domain of build->options has been reformulated
1934 * in terms of the internal build space in embed_options,
1935 * but the position is still that within the current code generation.
1937 __isl_give isl_map
*isl_ast_build_get_separation_class(
1938 __isl_keep isl_ast_build
*build
)
1941 isl_space
*space_sep
, *space
;
1948 local_pos
= build
->depth
- build
->outer_pos
;
1949 ctx
= isl_ast_build_get_ctx(build
);
1950 space_sep
= isl_space_alloc(ctx
, 0, 1, 1);
1951 space_sep
= isl_space_wrap(space_sep
);
1952 space_sep
= isl_space_set_tuple_name(space_sep
, isl_dim_set
,
1953 "separation_class");
1954 space
= isl_ast_build_get_space(build
, 1);
1955 space_sep
= isl_space_align_params(space_sep
, isl_space_copy(space
));
1956 space
= isl_space_map_from_domain_and_range(space
, space_sep
);
1958 res
= isl_union_map_extract_map(build
->options
, space
);
1959 res
= isl_map_fix_si(res
, isl_dim_out
, 0, local_pos
);
1960 res
= isl_map_coalesce(res
);
1965 /* Eliminate dimensions inner to the current dimension.
1967 __isl_give isl_set
*isl_ast_build_eliminate_inner(
1968 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
1974 return isl_set_free(set
);
1976 dim
= isl_set_dim(set
, isl_dim_set
);
1977 depth
= build
->depth
;
1978 set
= isl_set_detect_equalities(set
);
1979 set
= isl_set_eliminate(set
, isl_dim_set
, depth
+ 1, dim
- (depth
+ 1));
1984 /* Eliminate unknown divs and divs that depend on the current dimension.
1986 * Note that during the elimination of unknown divs, we may discover
1987 * an explicit representation of some other unknown divs, which may
1988 * depend on the current dimension. We therefore need to eliminate
1989 * unknown divs first.
1991 __isl_give isl_set
*isl_ast_build_eliminate_divs(
1992 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
1997 return isl_set_free(set
);
1999 set
= isl_set_remove_unknown_divs(set
);
2000 depth
= build
->depth
;
2001 set
= isl_set_remove_divs_involving_dims(set
, isl_dim_set
, depth
, 1);
2006 /* Eliminate dimensions inner to the current dimension as well as
2007 * unknown divs and divs that depend on the current dimension.
2008 * The result then consists only of constraints that are independent
2009 * of the current dimension and upper and lower bounds on the current
2012 __isl_give isl_set
*isl_ast_build_eliminate(
2013 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*domain
)
2015 domain
= isl_ast_build_eliminate_inner(build
, domain
);
2016 domain
= isl_ast_build_eliminate_divs(build
, domain
);