2 * Copyright 2012 Ecole Normale Superieure
3 * Copyright 2014 INRIA Rocquencourt
5 * Use of this software is governed by the MIT license
7 * Written by Sven Verdoolaege,
8 * Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
9 * and Inria Paris - Rocquencourt, Domaine de Voluceau - Rocquencourt,
10 * B.P. 105 - 78153 Le Chesnay, France
16 #include <isl_ast_build_private.h>
17 #include <isl_ast_private.h>
19 /* Construct a map that isolates the current dimension.
21 * Essentially, the current dimension of "set" is moved to the single output
22 * dimension in the result, with the current dimension in the domain replaced
23 * by an unconstrained variable.
25 __isl_give isl_map
*isl_ast_build_map_to_iterator(
26 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
30 map
= isl_map_from_domain(set
);
31 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
34 return isl_map_free(map
);
36 map
= isl_map_equate(map
, isl_dim_in
, build
->depth
, isl_dim_out
, 0);
37 map
= isl_map_eliminate(map
, isl_dim_in
, build
->depth
, 1);
42 /* Initialize the information derived during the AST generation to default
43 * values for a schedule domain in "space".
45 * We also check that the remaining fields are not NULL so that
46 * the calling functions don't have to perform this test.
48 static __isl_give isl_ast_build
*isl_ast_build_init_derived(
49 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
54 build
= isl_ast_build_cow(build
);
55 if (!build
|| !build
->domain
)
58 ctx
= isl_ast_build_get_ctx(build
);
59 strides
= isl_vec_alloc(ctx
, isl_space_dim(space
, isl_dim_set
));
60 strides
= isl_vec_set_si(strides
, 1);
62 isl_vec_free(build
->strides
);
63 build
->strides
= strides
;
65 space
= isl_space_map_from_set(space
);
66 isl_multi_aff_free(build
->offsets
);
67 build
->offsets
= isl_multi_aff_zero(isl_space_copy(space
));
68 isl_multi_aff_free(build
->values
);
69 build
->values
= isl_multi_aff_identity(space
);
71 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
72 !build
->pending
|| !build
->values
||
73 !build
->strides
|| !build
->offsets
|| !build
->options
)
74 return isl_ast_build_free(build
);
78 isl_space_free(space
);
79 return isl_ast_build_free(build
);
82 /* Return an isl_id called "c%d", with "%d" set to "i".
83 * If an isl_id with such a name already appears among the parameters
84 * in build->domain, then adjust the name to "c%d_%d".
86 static __isl_give isl_id
*generate_name(isl_ctx
*ctx
, int i
,
87 __isl_keep isl_ast_build
*build
)
91 isl_set
*dom
= build
->domain
;
93 snprintf(name
, sizeof(name
), "c%d", i
);
95 while (isl_set_find_dim_by_name(dom
, isl_dim_param
, name
) >= 0)
96 snprintf(name
, sizeof(name
), "c%d_%d", i
, j
++);
97 return isl_id_alloc(ctx
, name
, NULL
);
100 /* Create an isl_ast_build with "set" as domain.
102 * The input set is usually a parameter domain, but we currently allow it to
103 * be any kind of set. We set the domain of the returned isl_ast_build
104 * to "set" and initialize all the other fields to default values.
106 __isl_give isl_ast_build
*isl_ast_build_from_context(__isl_take isl_set
*set
)
111 isl_ast_build
*build
;
113 set
= isl_set_compute_divs(set
);
117 ctx
= isl_set_get_ctx(set
);
119 build
= isl_calloc_type(ctx
, isl_ast_build
);
125 build
->generated
= isl_set_copy(build
->domain
);
126 build
->pending
= isl_set_universe(isl_set_get_space(build
->domain
));
127 build
->options
= isl_union_map_empty(isl_space_params_alloc(ctx
, 0));
128 n
= isl_set_dim(set
, isl_dim_set
);
130 build
->iterators
= isl_id_list_alloc(ctx
, n
);
131 for (i
= 0; i
< n
; ++i
) {
133 if (isl_set_has_dim_id(set
, isl_dim_set
, i
))
134 id
= isl_set_get_dim_id(set
, isl_dim_set
, i
);
136 id
= generate_name(ctx
, i
, build
);
137 build
->iterators
= isl_id_list_add(build
->iterators
, id
);
139 space
= isl_set_get_space(set
);
140 if (isl_space_is_params(space
))
141 space
= isl_space_set_from_params(space
);
143 return isl_ast_build_init_derived(build
, space
);
149 /* Create an isl_ast_build with a universe (parametric) context.
151 __isl_give isl_ast_build
*isl_ast_build_alloc(isl_ctx
*ctx
)
156 space
= isl_space_params_alloc(ctx
, 0);
157 context
= isl_set_universe(space
);
159 return isl_ast_build_from_context(context
);
162 __isl_give isl_ast_build
*isl_ast_build_copy(__isl_keep isl_ast_build
*build
)
171 __isl_give isl_ast_build
*isl_ast_build_dup(__isl_keep isl_ast_build
*build
)
179 ctx
= isl_ast_build_get_ctx(build
);
180 dup
= isl_calloc_type(ctx
, isl_ast_build
);
185 dup
->outer_pos
= build
->outer_pos
;
186 dup
->depth
= build
->depth
;
187 dup
->iterators
= isl_id_list_copy(build
->iterators
);
188 dup
->domain
= isl_set_copy(build
->domain
);
189 dup
->generated
= isl_set_copy(build
->generated
);
190 dup
->pending
= isl_set_copy(build
->pending
);
191 dup
->values
= isl_multi_aff_copy(build
->values
);
192 dup
->value
= isl_pw_aff_copy(build
->value
);
193 dup
->strides
= isl_vec_copy(build
->strides
);
194 dup
->offsets
= isl_multi_aff_copy(build
->offsets
);
195 dup
->executed
= isl_union_map_copy(build
->executed
);
196 dup
->single_valued
= build
->single_valued
;
197 dup
->options
= isl_union_map_copy(build
->options
);
198 dup
->at_each_domain
= build
->at_each_domain
;
199 dup
->at_each_domain_user
= build
->at_each_domain_user
;
200 dup
->before_each_for
= build
->before_each_for
;
201 dup
->before_each_for_user
= build
->before_each_for_user
;
202 dup
->after_each_for
= build
->after_each_for
;
203 dup
->after_each_for_user
= build
->after_each_for_user
;
204 dup
->create_leaf
= build
->create_leaf
;
205 dup
->create_leaf_user
= build
->create_leaf_user
;
207 if (!dup
->iterators
|| !dup
->domain
|| !dup
->generated
||
208 !dup
->pending
|| !dup
->values
||
209 !dup
->strides
|| !dup
->offsets
|| !dup
->options
||
210 (build
->executed
&& !dup
->executed
) ||
211 (build
->value
&& !dup
->value
))
212 return isl_ast_build_free(dup
);
217 /* Align the parameters of "build" to those of "model", introducing
218 * additional parameters if needed.
220 __isl_give isl_ast_build
*isl_ast_build_align_params(
221 __isl_take isl_ast_build
*build
, __isl_take isl_space
*model
)
223 build
= isl_ast_build_cow(build
);
227 build
->domain
= isl_set_align_params(build
->domain
,
228 isl_space_copy(model
));
229 build
->generated
= isl_set_align_params(build
->generated
,
230 isl_space_copy(model
));
231 build
->pending
= isl_set_align_params(build
->pending
,
232 isl_space_copy(model
));
233 build
->values
= isl_multi_aff_align_params(build
->values
,
234 isl_space_copy(model
));
235 build
->offsets
= isl_multi_aff_align_params(build
->offsets
,
236 isl_space_copy(model
));
237 build
->options
= isl_union_map_align_params(build
->options
,
238 isl_space_copy(model
));
239 isl_space_free(model
);
241 if (!build
->domain
|| !build
->values
|| !build
->offsets
||
243 return isl_ast_build_free(build
);
247 isl_space_free(model
);
251 __isl_give isl_ast_build
*isl_ast_build_cow(__isl_take isl_ast_build
*build
)
259 return isl_ast_build_dup(build
);
262 __isl_null isl_ast_build
*isl_ast_build_free(
263 __isl_take isl_ast_build
*build
)
268 if (--build
->ref
> 0)
271 isl_id_list_free(build
->iterators
);
272 isl_set_free(build
->domain
);
273 isl_set_free(build
->generated
);
274 isl_set_free(build
->pending
);
275 isl_multi_aff_free(build
->values
);
276 isl_pw_aff_free(build
->value
);
277 isl_vec_free(build
->strides
);
278 isl_multi_aff_free(build
->offsets
);
279 isl_multi_aff_free(build
->schedule_map
);
280 isl_union_map_free(build
->executed
);
281 isl_union_map_free(build
->options
);
288 isl_ctx
*isl_ast_build_get_ctx(__isl_keep isl_ast_build
*build
)
290 return build
? isl_set_get_ctx(build
->domain
) : NULL
;
293 /* Replace build->options by "options".
295 __isl_give isl_ast_build
*isl_ast_build_set_options(
296 __isl_take isl_ast_build
*build
, __isl_take isl_union_map
*options
)
298 build
= isl_ast_build_cow(build
);
300 if (!build
|| !options
)
303 isl_union_map_free(build
->options
);
304 build
->options
= options
;
308 isl_union_map_free(options
);
309 return isl_ast_build_free(build
);
312 /* Set the iterators for the next code generation.
314 * If we still have some iterators left from the previous code generation
315 * (if any) or if iterators have already been set by a previous
316 * call to this function, then we remove them first.
318 __isl_give isl_ast_build
*isl_ast_build_set_iterators(
319 __isl_take isl_ast_build
*build
, __isl_take isl_id_list
*iterators
)
323 build
= isl_ast_build_cow(build
);
327 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
328 n_it
= isl_id_list_n_id(build
->iterators
);
330 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
331 "isl_ast_build in inconsistent state", goto error
);
333 build
->iterators
= isl_id_list_drop(build
->iterators
,
335 build
->iterators
= isl_id_list_concat(build
->iterators
, iterators
);
336 if (!build
->iterators
)
337 return isl_ast_build_free(build
);
341 isl_id_list_free(iterators
);
342 return isl_ast_build_free(build
);
345 /* Set the "at_each_domain" callback of "build" to "fn".
347 __isl_give isl_ast_build
*isl_ast_build_set_at_each_domain(
348 __isl_take isl_ast_build
*build
,
349 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_node
*node
,
350 __isl_keep isl_ast_build
*build
, void *user
), void *user
)
352 build
= isl_ast_build_cow(build
);
357 build
->at_each_domain
= fn
;
358 build
->at_each_domain_user
= user
;
363 /* Set the "before_each_for" callback of "build" to "fn".
365 __isl_give isl_ast_build
*isl_ast_build_set_before_each_for(
366 __isl_take isl_ast_build
*build
,
367 __isl_give isl_id
*(*fn
)(__isl_keep isl_ast_build
*build
,
368 void *user
), void *user
)
370 build
= isl_ast_build_cow(build
);
375 build
->before_each_for
= fn
;
376 build
->before_each_for_user
= user
;
381 /* Set the "after_each_for" callback of "build" to "fn".
383 __isl_give isl_ast_build
*isl_ast_build_set_after_each_for(
384 __isl_take isl_ast_build
*build
,
385 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_node
*node
,
386 __isl_keep isl_ast_build
*build
, void *user
), void *user
)
388 build
= isl_ast_build_cow(build
);
393 build
->after_each_for
= fn
;
394 build
->after_each_for_user
= user
;
399 /* Set the "create_leaf" callback of "build" to "fn".
401 __isl_give isl_ast_build
*isl_ast_build_set_create_leaf(
402 __isl_take isl_ast_build
*build
,
403 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_build
*build
,
404 void *user
), void *user
)
406 build
= isl_ast_build_cow(build
);
411 build
->create_leaf
= fn
;
412 build
->create_leaf_user
= user
;
417 /* Clear all information that is specific to this code generation
418 * and that is (probably) not meaningful to any nested code generation.
420 __isl_give isl_ast_build
*isl_ast_build_clear_local_info(
421 __isl_take isl_ast_build
*build
)
425 build
= isl_ast_build_cow(build
);
429 space
= isl_union_map_get_space(build
->options
);
430 isl_union_map_free(build
->options
);
431 build
->options
= isl_union_map_empty(space
);
433 build
->at_each_domain
= NULL
;
434 build
->at_each_domain_user
= NULL
;
435 build
->before_each_for
= NULL
;
436 build
->before_each_for_user
= NULL
;
437 build
->after_each_for
= NULL
;
438 build
->after_each_for_user
= NULL
;
439 build
->create_leaf
= NULL
;
440 build
->create_leaf_user
= NULL
;
443 return isl_ast_build_free(build
);
448 /* Have any loops been eliminated?
449 * That is, do any of the original schedule dimensions have a fixed
450 * value that has been substituted?
452 static int any_eliminated(isl_ast_build
*build
)
456 for (i
= 0; i
< build
->depth
; ++i
)
457 if (isl_ast_build_has_affine_value(build
, i
))
463 /* Clear build->schedule_map.
464 * This function should be called whenever anything that might affect
465 * the result of isl_ast_build_get_schedule_map_multi_aff changes.
466 * In particular, it should be called when the depth is changed or
467 * when an iterator is determined to have a fixed value.
469 static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build
*build
)
473 isl_multi_aff_free(build
->schedule_map
);
474 build
->schedule_map
= NULL
;
477 /* Do we need a (non-trivial) schedule map?
478 * That is, is the internal schedule space different from
479 * the external schedule space?
481 * The internal and external schedule spaces are only the same
482 * if code has been generated for the entire schedule and if none
483 * of the loops have been eliminated.
485 __isl_give
int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build
*build
)
492 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
493 return build
->depth
!= dim
|| any_eliminated(build
);
496 /* Return a mapping from the internal schedule space to the external
497 * schedule space in the form of an isl_multi_aff.
498 * The internal schedule space originally corresponds to that of the
499 * input schedule. This may change during the code generation if
500 * if isl_ast_build_insert_dim is ever called.
501 * The external schedule space corresponds to the
502 * loops that have been generated.
504 * Currently, the only difference between the internal schedule domain
505 * and the external schedule domain is that some dimensions are projected
506 * out in the external schedule domain. In particular, the dimensions
507 * for which no code has been generated yet and the dimensions that correspond
508 * to eliminated loops.
510 * We cache a copy of the schedule_map in build->schedule_map.
511 * The cache is cleared through isl_ast_build_reset_schedule_map
512 * whenever anything changes that might affect the result of this function.
514 __isl_give isl_multi_aff
*isl_ast_build_get_schedule_map_multi_aff(
515 __isl_keep isl_ast_build
*build
)
522 if (build
->schedule_map
)
523 return isl_multi_aff_copy(build
->schedule_map
);
525 space
= isl_ast_build_get_space(build
, 1);
526 space
= isl_space_map_from_set(space
);
527 ma
= isl_multi_aff_identity(space
);
528 if (isl_ast_build_need_schedule_map(build
)) {
530 int dim
= isl_set_dim(build
->domain
, isl_dim_set
);
531 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
,
532 build
->depth
, dim
- build
->depth
);
533 for (i
= build
->depth
- 1; i
>= 0; --i
)
534 if (isl_ast_build_has_affine_value(build
, i
))
535 ma
= isl_multi_aff_drop_dims(ma
,
539 build
->schedule_map
= ma
;
540 return isl_multi_aff_copy(build
->schedule_map
);
543 /* Return a mapping from the internal schedule space to the external
544 * schedule space in the form of an isl_map.
546 __isl_give isl_map
*isl_ast_build_get_schedule_map(
547 __isl_keep isl_ast_build
*build
)
551 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
552 return isl_map_from_multi_aff(ma
);
555 /* Return the position of the dimension in build->domain for which
556 * an AST node is currently being generated.
558 int isl_ast_build_get_depth(__isl_keep isl_ast_build
*build
)
560 return build
? build
->depth
: -1;
563 /* Prepare for generating code for the next level.
564 * In particular, increase the depth and reset any information
565 * that is local to the current depth.
567 __isl_give isl_ast_build
*isl_ast_build_increase_depth(
568 __isl_take isl_ast_build
*build
)
570 build
= isl_ast_build_cow(build
);
574 isl_ast_build_reset_schedule_map(build
);
575 build
->value
= isl_pw_aff_free(build
->value
);
579 void isl_ast_build_dump(__isl_keep isl_ast_build
*build
)
584 fprintf(stderr
, "domain: ");
585 isl_set_dump(build
->domain
);
586 fprintf(stderr
, "generated: ");
587 isl_set_dump(build
->generated
);
588 fprintf(stderr
, "pending: ");
589 isl_set_dump(build
->pending
);
590 fprintf(stderr
, "iterators: ");
591 isl_id_list_dump(build
->iterators
);
592 fprintf(stderr
, "values: ");
593 isl_multi_aff_dump(build
->values
);
595 fprintf(stderr
, "value: ");
596 isl_pw_aff_dump(build
->value
);
598 fprintf(stderr
, "strides: ");
599 isl_vec_dump(build
->strides
);
600 fprintf(stderr
, "offsets: ");
601 isl_multi_aff_dump(build
->offsets
);
604 /* Initialize "build" for AST construction in schedule space "space"
605 * in the case that build->domain is a parameter set.
607 * build->iterators is assumed to have been updated already.
609 static __isl_give isl_ast_build
*isl_ast_build_init(
610 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
614 build
= isl_ast_build_cow(build
);
618 set
= isl_set_universe(isl_space_copy(space
));
619 build
->domain
= isl_set_intersect_params(isl_set_copy(set
),
621 build
->pending
= isl_set_intersect_params(isl_set_copy(set
),
623 build
->generated
= isl_set_intersect_params(set
, build
->generated
);
625 return isl_ast_build_init_derived(build
, space
);
627 isl_ast_build_free(build
);
628 isl_space_free(space
);
632 /* Assign "aff" to *user and return -1, effectively extracting
633 * the first (and presumably only) affine expression in the isl_pw_aff
634 * on which this function is used.
636 static int extract_single_piece(__isl_take isl_set
*set
,
637 __isl_take isl_aff
*aff
, void *user
)
647 /* Intersect "set" with the stride constraint of "build", if any.
649 static __isl_give isl_set
*intersect_stride_constraint(__isl_take isl_set
*set
,
650 __isl_keep isl_ast_build
*build
)
655 return isl_set_free(set
);
656 if (!isl_ast_build_has_stride(build
, build
->depth
))
659 stride
= isl_ast_build_get_stride_constraint(build
);
660 return isl_set_intersect(set
, stride
);
663 /* Check if the given bounds on the current dimension (together with
664 * the stride constraint, if any) imply that
665 * this current dimension attains only a single value (in terms of
666 * parameters and outer dimensions).
667 * If so, we record it in build->value.
668 * If, moreover, this value can be represented as a single affine expression,
669 * then we also update build->values, effectively marking the current
670 * dimension as "eliminated".
672 * When computing the gist of the fixed value that can be represented
673 * as a single affine expression, it is important to only take into
674 * account the domain constraints in the original AST build and
675 * not the domain of the affine expression itself.
676 * Otherwise, a [i/3] is changed into a i/3 because we know that i
677 * is a multiple of 3, but then we end up not expressing anywhere
678 * in the context that i is a multiple of 3.
680 static __isl_give isl_ast_build
*update_values(
681 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
684 isl_pw_multi_aff
*pma
;
689 set
= isl_set_from_basic_set(bounds
);
690 set
= isl_set_intersect(set
, isl_set_copy(build
->domain
));
691 set
= intersect_stride_constraint(set
, build
);
692 it_map
= isl_ast_build_map_to_iterator(build
, set
);
694 sv
= isl_map_is_single_valued(it_map
);
696 build
= isl_ast_build_free(build
);
698 isl_map_free(it_map
);
702 pma
= isl_pw_multi_aff_from_map(it_map
);
703 build
->value
= isl_pw_multi_aff_get_pw_aff(pma
, 0);
704 build
->value
= isl_ast_build_compute_gist_pw_aff(build
, build
->value
);
705 build
->value
= isl_pw_aff_coalesce(build
->value
);
706 isl_pw_multi_aff_free(pma
);
709 return isl_ast_build_free(build
);
711 if (isl_pw_aff_n_piece(build
->value
) != 1)
714 isl_pw_aff_foreach_piece(build
->value
, &extract_single_piece
, &aff
);
716 build
->values
= isl_multi_aff_set_aff(build
->values
, build
->depth
, aff
);
718 return isl_ast_build_free(build
);
719 isl_ast_build_reset_schedule_map(build
);
723 /* Update the AST build based on the given loop bounds for
724 * the current dimension and the stride information available in the build.
726 * We first make sure that the bounds do not refer to any iterators
727 * that have already been eliminated.
728 * Then, we check if the bounds imply that the current iterator
730 * If they do and if this fixed value can be expressed as a single
731 * affine expression, we eliminate the iterators from the bounds.
732 * Note that we cannot simply plug in this single value using
733 * isl_basic_set_preimage_multi_aff as the single value may only
734 * be defined on a subset of the domain. Plugging in the value
735 * would restrict the build domain to this subset, while this
736 * restriction may not be reflected in the generated code.
737 * Finally, we intersect build->domain with the updated bounds.
738 * We also add the stride constraint unless we have been able
739 * to find a fixed value expressed as a single affine expression.
741 * Note that the check for a fixed value in update_values requires
742 * us to intersect the bounds with the current build domain.
743 * When we intersect build->domain with the updated bounds in
744 * the final step, we make sure that these updated bounds have
745 * not been intersected with the old build->domain.
746 * Otherwise, we would indirectly intersect the build domain with itself,
747 * which can lead to inefficiencies, in particular if the build domain
748 * contains any unknown divs.
750 __isl_give isl_ast_build
*isl_ast_build_set_loop_bounds(
751 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
755 build
= isl_ast_build_cow(build
);
759 bounds
= isl_basic_set_preimage_multi_aff(bounds
,
760 isl_multi_aff_copy(build
->values
));
761 build
= update_values(build
, isl_basic_set_copy(bounds
));
764 set
= isl_set_from_basic_set(isl_basic_set_copy(bounds
));
765 if (isl_ast_build_has_affine_value(build
, build
->depth
)) {
766 set
= isl_set_eliminate(set
, isl_dim_set
, build
->depth
, 1);
767 set
= isl_set_compute_divs(set
);
768 build
->pending
= isl_set_intersect(build
->pending
,
770 build
->domain
= isl_set_intersect(build
->domain
, set
);
772 isl_basic_set
*generated
, *pending
;
774 pending
= isl_basic_set_copy(bounds
);
775 pending
= isl_basic_set_drop_constraints_involving_dims(pending
,
776 isl_dim_set
, build
->depth
, 1);
777 build
->pending
= isl_set_intersect(build
->pending
,
778 isl_set_from_basic_set(pending
));
779 generated
= isl_basic_set_copy(bounds
);
780 generated
= isl_basic_set_drop_constraints_not_involving_dims(
781 generated
, isl_dim_set
, build
->depth
, 1);
782 build
->generated
= isl_set_intersect(build
->generated
,
783 isl_set_from_basic_set(generated
));
784 build
->domain
= isl_set_intersect(build
->domain
, set
);
785 build
= isl_ast_build_include_stride(build
);
789 isl_basic_set_free(bounds
);
791 if (!build
->domain
|| !build
->pending
|| !build
->generated
)
792 return isl_ast_build_free(build
);
796 isl_ast_build_free(build
);
797 isl_basic_set_free(bounds
);
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 /* Replace the set of pending constraints by "guard", which is then
851 * no longer considered as pending.
852 * That is, add "guard" to the generated constraints and clear all pending
853 * constraints, making the domain equal to the generated constraints.
855 __isl_give isl_ast_build
*isl_ast_build_replace_pending_by_guard(
856 __isl_take isl_ast_build
*build
, __isl_take isl_set
*guard
)
858 build
= isl_ast_build_restrict_generated(build
, guard
);
859 build
= isl_ast_build_cow(build
);
863 isl_set_free(build
->domain
);
864 build
->domain
= isl_set_copy(build
->generated
);
865 isl_set_free(build
->pending
);
866 build
->pending
= isl_set_universe(isl_set_get_space(build
->domain
));
869 return isl_ast_build_free(build
);
874 /* Intersect build->pending and build->domain with "set",
875 * where "set" is specified in terms of the internal schedule domain.
877 __isl_give isl_ast_build
*isl_ast_build_restrict_pending(
878 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
880 set
= isl_set_compute_divs(set
);
881 build
= isl_ast_build_restrict_internal(build
, isl_set_copy(set
));
882 build
= isl_ast_build_cow(build
);
886 build
->pending
= isl_set_intersect(build
->pending
, set
);
887 build
->pending
= isl_set_coalesce(build
->pending
);
890 return isl_ast_build_free(build
);
894 isl_ast_build_free(build
);
899 /* Intersect build->domain with "set", where "set" is specified
900 * in terms of the external schedule domain.
902 __isl_give isl_ast_build
*isl_ast_build_restrict(
903 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
905 if (isl_set_is_params(set
))
906 return isl_ast_build_restrict_generated(build
, set
);
908 if (isl_ast_build_need_schedule_map(build
)) {
910 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
911 set
= isl_set_preimage_multi_aff(set
, ma
);
913 return isl_ast_build_restrict_generated(build
, set
);
916 /* Replace build->executed by "executed".
918 __isl_give isl_ast_build
*isl_ast_build_set_executed(
919 __isl_take isl_ast_build
*build
, __isl_take isl_union_map
*executed
)
921 build
= isl_ast_build_cow(build
);
925 isl_union_map_free(build
->executed
);
926 build
->executed
= executed
;
930 isl_ast_build_free(build
);
931 isl_union_map_free(executed
);
935 /* Return a copy of the current schedule domain.
937 __isl_give isl_set
*isl_ast_build_get_domain(__isl_keep isl_ast_build
*build
)
939 return build
? isl_set_copy(build
->domain
) : NULL
;
942 /* Return a copy of the set of pending constraints.
944 __isl_give isl_set
*isl_ast_build_get_pending(
945 __isl_keep isl_ast_build
*build
)
947 return build
? isl_set_copy(build
->pending
) : NULL
;
950 /* Return a copy of the set of generated constraints.
952 __isl_give isl_set
*isl_ast_build_get_generated(
953 __isl_keep isl_ast_build
*build
)
955 return build
? isl_set_copy(build
->generated
) : NULL
;
958 /* Return the number of variables of the given type
959 * in the (internal) schedule space.
961 unsigned isl_ast_build_dim(__isl_keep isl_ast_build
*build
,
962 enum isl_dim_type type
)
966 return isl_set_dim(build
->domain
, type
);
969 /* Return the (schedule) space of "build".
971 * If "internal" is set, then this space is the space of the internal
972 * representation of the entire schedule, including those parts for
973 * which no code has been generated yet.
975 * If "internal" is not set, then this space is the external representation
976 * of the loops generated so far.
978 __isl_give isl_space
*isl_ast_build_get_space(__isl_keep isl_ast_build
*build
,
988 space
= isl_set_get_space(build
->domain
);
992 if (!isl_ast_build_need_schedule_map(build
))
995 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
996 space
= isl_space_drop_dims(space
, isl_dim_set
,
997 build
->depth
, dim
- build
->depth
);
998 for (i
= build
->depth
- 1; i
>= 0; --i
)
999 if (isl_ast_build_has_affine_value(build
, i
))
1000 space
= isl_space_drop_dims(space
, isl_dim_set
, i
, 1);
1005 /* Return the external representation of the schedule space of "build",
1006 * i.e., a space with a dimension for each loop generated so far,
1007 * with the names of the dimensions set to the loop iterators.
1009 __isl_give isl_space
*isl_ast_build_get_schedule_space(
1010 __isl_keep isl_ast_build
*build
)
1018 space
= isl_ast_build_get_space(build
, 0);
1021 for (i
= 0; i
< build
->depth
; ++i
) {
1024 if (isl_ast_build_has_affine_value(build
, i
)) {
1029 id
= isl_ast_build_get_iterator_id(build
, i
);
1030 space
= isl_space_set_dim_id(space
, isl_dim_set
, i
- skip
, id
);
1036 /* Return the current schedule, as stored in build->executed, in terms
1037 * of the external schedule domain.
1039 __isl_give isl_union_map
*isl_ast_build_get_schedule(
1040 __isl_keep isl_ast_build
*build
)
1042 isl_union_map
*executed
;
1043 isl_union_map
*schedule
;
1048 executed
= isl_union_map_copy(build
->executed
);
1049 if (isl_ast_build_need_schedule_map(build
)) {
1050 isl_map
*proj
= isl_ast_build_get_schedule_map(build
);
1051 executed
= isl_union_map_apply_domain(executed
,
1052 isl_union_map_from_map(proj
));
1054 schedule
= isl_union_map_reverse(executed
);
1059 /* Return the iterator attached to the internal schedule dimension "pos".
1061 __isl_give isl_id
*isl_ast_build_get_iterator_id(
1062 __isl_keep isl_ast_build
*build
, int pos
)
1067 return isl_id_list_get_id(build
->iterators
, pos
);
1070 /* Set the stride and offset of the current dimension to the given
1071 * value and expression.
1073 * If we had already found a stride before, then the two strides
1074 * are combined into a single stride.
1076 * In particular, if the new stride information is of the form
1080 * and the old stride information is of the form
1084 * then we compute the extended gcd of s and s2
1088 * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
1089 * and the second with t2 = a s1/g.
1092 * i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
1094 * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
1095 * is the combined stride.
1097 static __isl_give isl_ast_build
*set_stride(__isl_take isl_ast_build
*build
,
1098 __isl_take isl_val
*stride
, __isl_take isl_aff
*offset
)
1102 build
= isl_ast_build_cow(build
);
1103 if (!build
|| !stride
|| !offset
)
1108 if (isl_ast_build_has_stride(build
, pos
)) {
1109 isl_val
*stride2
, *a
, *b
, *g
;
1112 stride2
= isl_vec_get_element_val(build
->strides
, pos
);
1113 g
= isl_val_gcdext(isl_val_copy(stride
), isl_val_copy(stride2
),
1115 a
= isl_val_mul(a
, isl_val_copy(stride
));
1116 a
= isl_val_div(a
, isl_val_copy(g
));
1117 stride2
= isl_val_div(stride2
, g
);
1118 b
= isl_val_mul(b
, isl_val_copy(stride2
));
1119 stride
= isl_val_mul(stride
, stride2
);
1121 offset2
= isl_multi_aff_get_aff(build
->offsets
, pos
);
1122 offset2
= isl_aff_scale_val(offset2
, a
);
1123 offset
= isl_aff_scale_val(offset
, b
);
1124 offset
= isl_aff_add(offset
, offset2
);
1127 build
->strides
= isl_vec_set_element_val(build
->strides
, pos
, stride
);
1128 build
->offsets
= isl_multi_aff_set_aff(build
->offsets
, pos
, offset
);
1129 if (!build
->strides
|| !build
->offsets
)
1130 return isl_ast_build_free(build
);
1134 isl_val_free(stride
);
1135 isl_aff_free(offset
);
1136 return isl_ast_build_free(build
);
1139 /* Return a set expressing the stride constraint at the current depth.
1141 * In particular, if the current iterator (i) is known to attain values
1145 * where f is the offset and s is the stride, then the returned set
1146 * expresses the constraint
1150 __isl_give isl_set
*isl_ast_build_get_stride_constraint(
1151 __isl_keep isl_ast_build
*build
)
1163 if (!isl_ast_build_has_stride(build
, pos
))
1164 return isl_set_universe(isl_ast_build_get_space(build
, 1));
1166 stride
= isl_ast_build_get_stride(build
, pos
);
1167 aff
= isl_ast_build_get_offset(build
, pos
);
1168 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, pos
, -1);
1169 aff
= isl_aff_mod_val(aff
, stride
);
1170 set
= isl_set_from_basic_set(isl_aff_zero_basic_set(aff
));
1175 /* Return the expansion implied by the stride and offset at the current
1178 * That is, return the mapping
1180 * [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1181 * -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]
1183 * where s is the stride at the current depth d and offset(i) is
1184 * the corresponding offset.
1186 __isl_give isl_multi_aff
*isl_ast_build_get_stride_expansion(
1187 __isl_keep isl_ast_build
*build
)
1192 isl_aff
*aff
, *offset
;
1198 pos
= isl_ast_build_get_depth(build
);
1199 space
= isl_ast_build_get_space(build
, 1);
1200 space
= isl_space_map_from_set(space
);
1201 ma
= isl_multi_aff_identity(space
);
1203 if (!isl_ast_build_has_stride(build
, pos
))
1206 offset
= isl_ast_build_get_offset(build
, pos
);
1207 stride
= isl_ast_build_get_stride(build
, pos
);
1208 aff
= isl_multi_aff_get_aff(ma
, pos
);
1209 aff
= isl_aff_scale_val(aff
, stride
);
1210 aff
= isl_aff_add(aff
, offset
);
1211 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
1216 /* Add constraints corresponding to any previously detected
1217 * stride on the current dimension to build->domain.
1219 __isl_give isl_ast_build
*isl_ast_build_include_stride(
1220 __isl_take isl_ast_build
*build
)
1226 if (!isl_ast_build_has_stride(build
, build
->depth
))
1228 build
= isl_ast_build_cow(build
);
1232 set
= isl_ast_build_get_stride_constraint(build
);
1234 build
->domain
= isl_set_intersect(build
->domain
, isl_set_copy(set
));
1235 build
->generated
= isl_set_intersect(build
->generated
, set
);
1236 if (!build
->domain
|| !build
->generated
)
1237 return isl_ast_build_free(build
);
1242 /* Information used inside detect_stride.
1244 * "build" may be updated by detect_stride to include stride information.
1245 * "pos" is equal to build->depth.
1247 struct isl_detect_stride_data
{
1248 isl_ast_build
*build
;
1252 /* Check if constraint "c" imposes any stride on dimension data->pos
1253 * and, if so, update the stride information in data->build.
1255 * In order to impose a stride on the dimension, "c" needs to be an equality
1256 * and it needs to involve the dimension. Note that "c" may also be
1257 * a div constraint and thus an inequality that we cannot use.
1259 * Let c be of the form
1261 * h(p) + g * v * i + g * stride * f(alpha) = 0
1263 * with h(p) an expression in terms of the parameters and outer dimensions
1264 * and f(alpha) an expression in terms of the existentially quantified
1265 * variables. Note that the inner dimensions have been eliminated so
1266 * they do not appear in "c".
1268 * If "stride" is not zero and not one, then it represents a non-trivial stride
1269 * on "i". We compute a and b such that
1271 * a v + b stride = 1
1275 * g v i = -h(p) + g stride f(alpha)
1277 * a g v i = -a h(p) + g stride f(alpha)
1279 * a g v i + b g stride i = -a h(p) + g stride * (...)
1281 * g i = -a h(p) + g stride * (...)
1283 * i = -a h(p)/g + stride * (...)
1285 * The expression "-a h(p)/g" can therefore be used as offset.
1287 static int detect_stride(__isl_take isl_constraint
*c
, void *user
)
1289 struct isl_detect_stride_data
*data
= user
;
1292 isl_val
*v
, *stride
, *m
;
1294 if (!isl_constraint_is_equality(c
) ||
1295 !isl_constraint_involves_dims(c
, isl_dim_set
, data
->pos
, 1)) {
1296 isl_constraint_free(c
);
1300 ctx
= isl_constraint_get_ctx(c
);
1301 stride
= isl_val_zero(ctx
);
1302 n_div
= isl_constraint_dim(c
, isl_dim_div
);
1303 for (i
= 0; i
< n_div
; ++i
) {
1304 v
= isl_constraint_get_coefficient_val(c
, isl_dim_div
, i
);
1305 stride
= isl_val_gcd(stride
, v
);
1308 v
= isl_constraint_get_coefficient_val(c
, isl_dim_set
, data
->pos
);
1309 m
= isl_val_gcd(isl_val_copy(stride
), isl_val_copy(v
));
1310 stride
= isl_val_div(stride
, isl_val_copy(m
));
1311 v
= isl_val_div(v
, isl_val_copy(m
));
1313 if (!isl_val_is_zero(stride
) && !isl_val_is_one(stride
)) {
1315 isl_val
*gcd
, *a
, *b
;
1317 gcd
= isl_val_gcdext(v
, isl_val_copy(stride
), &a
, &b
);
1321 aff
= isl_constraint_get_aff(c
);
1322 for (i
= 0; i
< n_div
; ++i
)
1323 aff
= isl_aff_set_coefficient_si(aff
,
1325 aff
= isl_aff_set_coefficient_si(aff
, isl_dim_in
, data
->pos
, 0);
1327 aff
= isl_aff_scale_val(aff
, a
);
1328 aff
= isl_aff_scale_down_val(aff
, m
);
1329 data
->build
= set_stride(data
->build
, stride
, aff
);
1331 isl_val_free(stride
);
1336 isl_constraint_free(c
);
1340 /* Check if the constraints in "set" imply any stride on the current
1341 * dimension and, if so, record the stride information in "build"
1342 * and return the updated "build".
1344 * We compute the affine hull and then check if any of the constraints
1345 * in the hull imposes any stride on the current dimension.
1347 * We assume that inner dimensions have been eliminated from "set"
1348 * by the caller. This is needed because the common stride
1349 * may be imposed by different inner dimensions on different parts of
1352 __isl_give isl_ast_build
*isl_ast_build_detect_strides(
1353 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
1355 isl_basic_set
*hull
;
1356 struct isl_detect_stride_data data
;
1362 data
.pos
= isl_ast_build_get_depth(build
);
1363 hull
= isl_set_affine_hull(set
);
1365 if (isl_basic_set_foreach_constraint(hull
, &detect_stride
, &data
) < 0)
1366 data
.build
= isl_ast_build_free(data
.build
);
1368 isl_basic_set_free(hull
);
1375 struct isl_ast_build_involves_data
{
1380 /* Check if "map" involves the input dimension data->depth.
1382 static int involves_depth(__isl_take isl_map
*map
, void *user
)
1384 struct isl_ast_build_involves_data
*data
= user
;
1386 data
->involves
= isl_map_involves_dims(map
, isl_dim_in
, data
->depth
, 1);
1389 if (data
->involves
< 0 || data
->involves
)
1394 /* Do any options depend on the value of the dimension at the current depth?
1396 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build
*build
)
1398 struct isl_ast_build_involves_data data
;
1403 data
.depth
= build
->depth
;
1406 if (isl_union_map_foreach_map(build
->options
,
1407 &involves_depth
, &data
) < 0) {
1408 if (data
.involves
< 0 || !data
.involves
)
1412 return data
.involves
;
1415 /* Construct the map
1417 * { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1419 * with "space" the parameter space of the constructed map.
1421 static __isl_give isl_map
*construct_insertion_map(__isl_take isl_space
*space
,
1425 isl_basic_map
*bmap1
, *bmap2
;
1427 space
= isl_space_set_from_params(space
);
1428 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1429 space
= isl_space_map_from_set(space
);
1430 c
= isl_equality_alloc(isl_local_space_from_space(space
));
1431 c
= isl_constraint_set_coefficient_si(c
, isl_dim_in
, 0, 1);
1432 c
= isl_constraint_set_coefficient_si(c
, isl_dim_out
, 0, -1);
1433 bmap1
= isl_basic_map_from_constraint(isl_constraint_copy(c
));
1434 c
= isl_constraint_set_constant_si(c
, 1);
1435 bmap2
= isl_basic_map_from_constraint(c
);
1437 bmap1
= isl_basic_map_upper_bound_si(bmap1
, isl_dim_in
, 0, pos
- 1);
1438 bmap2
= isl_basic_map_lower_bound_si(bmap2
, isl_dim_in
, 0, pos
);
1440 return isl_basic_map_union(bmap1
, bmap2
);
1443 static const char *option_str
[] = {
1444 [atomic
] = "atomic",
1445 [unroll
] = "unroll",
1446 [separate
] = "separate"
1449 /* Update the "options" to reflect the insertion of a dimension
1450 * at position "pos" in the schedule domain space.
1451 * "space" is the original domain space before the insertion and
1452 * may be named and/or structured.
1454 * The (relevant) input options all have "space" as domain, which
1455 * has to be mapped to the extended space.
1456 * The values of the ranges also refer to the schedule domain positions
1457 * and they therefore also need to be adjusted. In particular, values
1458 * smaller than pos do not need to change, while values greater than or
1459 * equal to pos need to be incremented.
1460 * That is, we need to apply the following map.
1462 * { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1463 * unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1464 * separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1465 * separation_class[[i] -> [c]]
1466 * -> separation_class[[i] -> [c]] : i < pos;
1467 * separation_class[[i] -> [c]]
1468 * -> separation_class[[i + 1] -> [c]] : i >= pos }
1470 static __isl_give isl_union_map
*options_insert_dim(
1471 __isl_take isl_union_map
*options
, __isl_take isl_space
*space
, int pos
)
1474 isl_union_map
*insertion
;
1475 enum isl_ast_build_domain_type type
;
1476 const char *name
= "separation_class";
1478 space
= isl_space_map_from_set(space
);
1479 map
= isl_map_identity(space
);
1480 map
= isl_map_insert_dims(map
, isl_dim_out
, pos
, 1);
1481 options
= isl_union_map_apply_domain(options
,
1482 isl_union_map_from_map(map
));
1487 map
= construct_insertion_map(isl_union_map_get_space(options
), pos
);
1489 insertion
= isl_union_map_empty(isl_union_map_get_space(options
));
1491 for (type
= atomic
; type
<= separate
; ++type
) {
1492 isl_map
*map_type
= isl_map_copy(map
);
1493 const char *name
= option_str
[type
];
1494 map_type
= isl_map_set_tuple_name(map_type
, isl_dim_in
, name
);
1495 map_type
= isl_map_set_tuple_name(map_type
, isl_dim_out
, name
);
1496 insertion
= isl_union_map_add_map(insertion
, map_type
);
1499 map
= isl_map_product(map
, isl_map_identity(isl_map_get_space(map
)));
1500 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
1501 map
= isl_map_set_tuple_name(map
, isl_dim_out
, name
);
1502 insertion
= isl_union_map_add_map(insertion
, map
);
1504 options
= isl_union_map_apply_range(options
, insertion
);
1509 /* Insert a single dimension in the schedule domain at position "pos".
1510 * The new dimension is given an isl_id with the empty string as name.
1512 * The main difficulty is updating build->options to reflect the
1513 * extra dimension. This is handled in options_insert_dim.
1515 * Note that because of the dimension manipulations, the resulting
1516 * schedule domain space will always be unnamed and unstructured.
1517 * However, the original schedule domain space may be named and/or
1518 * structured, so we have to take this possibility into account
1519 * while performing the transformations.
1521 __isl_give isl_ast_build
*isl_ast_build_insert_dim(
1522 __isl_take isl_ast_build
*build
, int pos
)
1525 isl_space
*space
, *ma_space
;
1529 build
= isl_ast_build_cow(build
);
1533 ctx
= isl_ast_build_get_ctx(build
);
1534 id
= isl_id_alloc(ctx
, "", NULL
);
1535 space
= isl_ast_build_get_space(build
, 1);
1536 build
->iterators
= isl_id_list_insert(build
->iterators
, pos
, id
);
1537 build
->domain
= isl_set_insert_dims(build
->domain
,
1538 isl_dim_set
, pos
, 1);
1539 build
->generated
= isl_set_insert_dims(build
->generated
,
1540 isl_dim_set
, pos
, 1);
1541 build
->pending
= isl_set_insert_dims(build
->pending
,
1542 isl_dim_set
, pos
, 1);
1543 build
->strides
= isl_vec_insert_els(build
->strides
, pos
, 1);
1544 build
->strides
= isl_vec_set_element_si(build
->strides
, pos
, 1);
1545 ma_space
= isl_space_params(isl_multi_aff_get_space(build
->offsets
));
1546 ma_space
= isl_space_set_from_params(ma_space
);
1547 ma_space
= isl_space_add_dims(ma_space
, isl_dim_set
, 1);
1548 ma_space
= isl_space_map_from_set(ma_space
);
1549 ma
= isl_multi_aff_zero(isl_space_copy(ma_space
));
1550 build
->offsets
= isl_multi_aff_splice(build
->offsets
, pos
, pos
, ma
);
1551 ma
= isl_multi_aff_identity(ma_space
);
1552 build
->values
= isl_multi_aff_splice(build
->values
, pos
, pos
, ma
);
1553 build
->options
= options_insert_dim(build
->options
, space
, pos
);
1555 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
1556 !build
->pending
|| !build
->values
||
1557 !build
->strides
|| !build
->offsets
|| !build
->options
)
1558 return isl_ast_build_free(build
);
1563 /* Scale down the current dimension by a factor of "m".
1564 * "umap" is an isl_union_map that implements the scaling down.
1565 * That is, it is of the form
1567 * { [.... i ....] -> [.... i' ....] : i = m i' }
1569 * This function is called right after the strides have been
1570 * detected, but before any constraints on the current dimension
1571 * have been included in build->domain.
1572 * We therefore only need to update stride, offset and the options.
1574 __isl_give isl_ast_build
*isl_ast_build_scale_down(
1575 __isl_take isl_ast_build
*build
, __isl_take isl_val
*m
,
1576 __isl_take isl_union_map
*umap
)
1582 build
= isl_ast_build_cow(build
);
1583 if (!build
|| !umap
|| !m
)
1586 depth
= build
->depth
;
1588 v
= isl_vec_get_element_val(build
->strides
, depth
);
1589 v
= isl_val_div(v
, isl_val_copy(m
));
1590 build
->strides
= isl_vec_set_element_val(build
->strides
, depth
, v
);
1592 aff
= isl_multi_aff_get_aff(build
->offsets
, depth
);
1593 aff
= isl_aff_scale_down_val(aff
, m
);
1594 build
->offsets
= isl_multi_aff_set_aff(build
->offsets
, depth
, aff
);
1595 build
->options
= isl_union_map_apply_domain(build
->options
, umap
);
1596 if (!build
->strides
|| !build
->offsets
|| !build
->options
)
1597 return isl_ast_build_free(build
);
1602 isl_union_map_free(umap
);
1603 return isl_ast_build_free(build
);
1606 /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1607 * If an isl_id with such a name already appears among the parameters
1608 * in build->domain, then adjust the name to "c%d_%d".
1610 static __isl_give isl_id_list
*generate_names(isl_ctx
*ctx
, int n
, int first
,
1611 __isl_keep isl_ast_build
*build
)
1616 names
= isl_id_list_alloc(ctx
, n
);
1617 for (i
= 0; i
< n
; ++i
) {
1620 id
= generate_name(ctx
, first
+ i
, build
);
1621 names
= isl_id_list_add(names
, id
);
1627 /* Embed "options" into the given isl_ast_build space.
1629 * This function is called from within a nested call to
1630 * isl_ast_build_node_from_schedule_map.
1631 * "options" refers to the additional schedule,
1632 * while space refers to both the space of the outer isl_ast_build and
1633 * that of the additional schedule.
1634 * Specifically, space is of the form
1638 * while options lives in the space(s)
1646 * and compose this with options, to obtain the new options
1647 * living in the space(s)
1651 static __isl_give isl_union_map
*embed_options(
1652 __isl_take isl_union_map
*options
, __isl_take isl_space
*space
)
1656 map
= isl_map_universe(isl_space_unwrap(space
));
1657 map
= isl_map_range_map(map
);
1659 options
= isl_union_map_apply_range(
1660 isl_union_map_from_map(map
), options
);
1665 /* Update "build" for use in a (possibly nested) code generation. That is,
1666 * extend "build" from an AST build on some domain O to an AST build
1667 * on domain [O -> S], with S corresponding to "space".
1668 * If the original domain is a parameter domain, then the new domain is
1670 * "iterators" is a list of iterators for S, but the number of elements
1671 * may be smaller or greater than the number of set dimensions of S.
1672 * If "keep_iterators" is set, then any extra ids in build->iterators
1673 * are reused for S. Otherwise, these extra ids are dropped.
1675 * We first update build->outer_pos to the current depth.
1676 * This depth is zero in case this is the outermost code generation.
1678 * We then add additional ids such that the number of iterators is at least
1679 * equal to the dimension of the new build domain.
1681 * If the original domain is parametric, then we are constructing
1682 * an isl_ast_build for the outer code generation and we pass control
1683 * to isl_ast_build_init.
1685 * Otherwise, we adjust the fields of "build" to include "space".
1687 __isl_give isl_ast_build
*isl_ast_build_product(
1688 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
1693 isl_multi_aff
*embedding
;
1696 build
= isl_ast_build_cow(build
);
1700 build
->outer_pos
= build
->depth
;
1702 ctx
= isl_ast_build_get_ctx(build
);
1703 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
1704 dim
+= isl_space_dim(space
, isl_dim_set
);
1705 n_it
= isl_id_list_n_id(build
->iterators
);
1708 l
= generate_names(ctx
, dim
- n_it
, n_it
, build
);
1709 build
->iterators
= isl_id_list_concat(build
->iterators
, l
);
1712 if (isl_set_is_params(build
->domain
))
1713 return isl_ast_build_init(build
, space
);
1715 set
= isl_set_universe(isl_space_copy(space
));
1716 build
->domain
= isl_set_product(build
->domain
, isl_set_copy(set
));
1717 build
->pending
= isl_set_product(build
->pending
, isl_set_copy(set
));
1718 build
->generated
= isl_set_product(build
->generated
, set
);
1720 strides
= isl_vec_alloc(ctx
, isl_space_dim(space
, isl_dim_set
));
1721 strides
= isl_vec_set_si(strides
, 1);
1722 build
->strides
= isl_vec_concat(build
->strides
, strides
);
1724 space
= isl_space_map_from_set(space
);
1725 build
->offsets
= isl_multi_aff_align_params(build
->offsets
,
1726 isl_space_copy(space
));
1727 build
->offsets
= isl_multi_aff_product(build
->offsets
,
1728 isl_multi_aff_zero(isl_space_copy(space
)));
1729 build
->values
= isl_multi_aff_align_params(build
->values
,
1730 isl_space_copy(space
));
1731 embedding
= isl_multi_aff_identity(space
);
1732 build
->values
= isl_multi_aff_product(build
->values
, embedding
);
1734 space
= isl_ast_build_get_space(build
, 1);
1735 build
->options
= embed_options(build
->options
, space
);
1737 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
1738 !build
->pending
|| !build
->values
||
1739 !build
->strides
|| !build
->offsets
|| !build
->options
)
1740 return isl_ast_build_free(build
);
1744 isl_ast_build_free(build
);
1745 isl_space_free(space
);
1749 /* Does "aff" only attain non-negative values over build->domain?
1750 * That is, does it not attain any negative values?
1752 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build
*build
,
1753 __isl_keep isl_aff
*aff
)
1761 aff
= isl_aff_copy(aff
);
1762 test
= isl_set_from_basic_set(isl_aff_neg_basic_set(aff
));
1763 test
= isl_set_intersect(test
, isl_set_copy(build
->domain
));
1764 empty
= isl_set_is_empty(test
);
1770 /* Does the dimension at (internal) position "pos" have a non-trivial stride?
1772 int isl_ast_build_has_stride(__isl_keep isl_ast_build
*build
, int pos
)
1780 v
= isl_vec_get_element_val(build
->strides
, pos
);
1783 has_stride
= !isl_val_is_one(v
);
1789 /* Given that the dimension at position "pos" takes on values
1793 * with a an integer, return s through *stride.
1795 __isl_give isl_val
*isl_ast_build_get_stride(__isl_keep isl_ast_build
*build
,
1801 return isl_vec_get_element_val(build
->strides
, pos
);
1804 /* Given that the dimension at position "pos" takes on values
1808 * with a an integer, return f.
1810 __isl_give isl_aff
*isl_ast_build_get_offset(
1811 __isl_keep isl_ast_build
*build
, int pos
)
1816 return isl_multi_aff_get_aff(build
->offsets
, pos
);
1819 /* Is the dimension at position "pos" known to attain only a single
1820 * value that, moreover, can be described by a single affine expression
1821 * in terms of the outer dimensions and parameters?
1823 * If not, then the corresponding affine expression in build->values
1824 * is set to be equal to the same input dimension.
1825 * Otherwise, it is set to the requested expression in terms of
1826 * outer dimensions and parameters.
1828 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build
*build
,
1837 aff
= isl_multi_aff_get_aff(build
->values
, pos
);
1838 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, pos
, 1);
1847 /* Plug in the known values (fixed affine expressions in terms of
1848 * parameters and outer loop iterators) of all loop iterators
1849 * in the domain of "umap".
1851 * We simply precompose "umap" with build->values.
1853 __isl_give isl_union_map
*isl_ast_build_substitute_values_union_map_domain(
1854 __isl_keep isl_ast_build
*build
, __isl_take isl_union_map
*umap
)
1856 isl_multi_aff
*values
;
1859 return isl_union_map_free(umap
);
1861 values
= isl_multi_aff_copy(build
->values
);
1862 umap
= isl_union_map_preimage_domain_multi_aff(umap
, values
);
1867 /* Is the current dimension known to attain only a single value?
1869 int isl_ast_build_has_value(__isl_keep isl_ast_build
*build
)
1874 return build
->value
!= NULL
;
1877 /* Simplify the basic set "bset" based on what we know about
1878 * the iterators of already generated loops.
1880 * "bset" is assumed to live in the (internal) schedule domain.
1882 __isl_give isl_basic_set
*isl_ast_build_compute_gist_basic_set(
1883 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
1888 bset
= isl_basic_set_preimage_multi_aff(bset
,
1889 isl_multi_aff_copy(build
->values
));
1890 bset
= isl_basic_set_gist(bset
,
1891 isl_set_simple_hull(isl_set_copy(build
->domain
)));
1895 isl_basic_set_free(bset
);
1899 /* Simplify the set "set" based on what we know about
1900 * the iterators of already generated loops.
1902 * "set" is assumed to live in the (internal) schedule domain.
1904 __isl_give isl_set
*isl_ast_build_compute_gist(
1905 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
1910 if (!isl_set_is_params(set
))
1911 set
= isl_set_preimage_multi_aff(set
,
1912 isl_multi_aff_copy(build
->values
));
1913 set
= isl_set_gist(set
, isl_set_copy(build
->domain
));
1921 /* Include information about what we know about the iterators of
1922 * already generated loops to "set".
1924 * We currently only plug in the known affine values of outer loop
1926 * In principle we could also introduce equalities or even other
1927 * constraints implied by the intersection of "set" and build->domain.
1929 __isl_give isl_set
*isl_ast_build_specialize(__isl_keep isl_ast_build
*build
,
1930 __isl_take isl_set
*set
)
1933 return isl_set_free(set
);
1935 return isl_set_preimage_multi_aff(set
,
1936 isl_multi_aff_copy(build
->values
));
1939 /* Simplify the map "map" based on what we know about
1940 * the iterators of already generated loops.
1942 * The domain of "map" is assumed to live in the (internal) schedule domain.
1944 __isl_give isl_map
*isl_ast_build_compute_gist_map_domain(
1945 __isl_keep isl_ast_build
*build
, __isl_take isl_map
*map
)
1950 map
= isl_map_gist_domain(map
, isl_set_copy(build
->domain
));
1958 /* Simplify the affine expression "aff" based on what we know about
1959 * the iterators of already generated loops.
1961 * The domain of "aff" is assumed to live in the (internal) schedule domain.
1963 __isl_give isl_aff
*isl_ast_build_compute_gist_aff(
1964 __isl_keep isl_ast_build
*build
, __isl_take isl_aff
*aff
)
1969 aff
= isl_aff_gist(aff
, isl_set_copy(build
->domain
));
1977 /* Simplify the piecewise affine expression "aff" based on what we know about
1978 * the iterators of already generated loops.
1980 * The domain of "pa" is assumed to live in the (internal) schedule domain.
1982 __isl_give isl_pw_aff
*isl_ast_build_compute_gist_pw_aff(
1983 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
1988 if (!isl_set_is_params(build
->domain
))
1989 pa
= isl_pw_aff_pullback_multi_aff(pa
,
1990 isl_multi_aff_copy(build
->values
));
1991 pa
= isl_pw_aff_gist(pa
, isl_set_copy(build
->domain
));
1995 isl_pw_aff_free(pa
);
1999 /* Simplify the piecewise multi-affine expression "aff" based on what
2000 * we know about the iterators of already generated loops.
2002 * The domain of "pma" is assumed to live in the (internal) schedule domain.
2004 __isl_give isl_pw_multi_aff
*isl_ast_build_compute_gist_pw_multi_aff(
2005 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
2010 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
,
2011 isl_multi_aff_copy(build
->values
));
2012 pma
= isl_pw_multi_aff_gist(pma
, isl_set_copy(build
->domain
));
2016 isl_pw_multi_aff_free(pma
);
2020 /* Extract the schedule domain of the given type from build->options
2021 * at the current depth.
2023 * In particular, find the subset of build->options that is of
2024 * the following form
2026 * schedule_domain -> type[depth]
2028 * and return the corresponding domain, after eliminating inner dimensions
2029 * and divs that depend on the current dimension.
2031 * Note that the domain of build->options has been reformulated
2032 * in terms of the internal build space in embed_options,
2033 * but the position is still that within the current code generation.
2035 __isl_give isl_set
*isl_ast_build_get_option_domain(
2036 __isl_keep isl_ast_build
*build
,
2037 enum isl_ast_build_domain_type type
)
2048 name
= option_str
[type
];
2049 local_pos
= build
->depth
- build
->outer_pos
;
2051 space
= isl_ast_build_get_space(build
, 1);
2052 space
= isl_space_from_domain(space
);
2053 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
2054 space
= isl_space_set_tuple_name(space
, isl_dim_out
, name
);
2056 option
= isl_union_map_extract_map(build
->options
, space
);
2057 option
= isl_map_fix_si(option
, isl_dim_out
, 0, local_pos
);
2059 domain
= isl_map_domain(option
);
2060 domain
= isl_ast_build_eliminate(build
, domain
);
2065 /* Extract the separation class mapping at the current depth.
2067 * In particular, find and return the subset of build->options that is of
2068 * the following form
2070 * schedule_domain -> separation_class[[depth] -> [class]]
2072 * The caller is expected to eliminate inner dimensions from the domain.
2074 * Note that the domain of build->options has been reformulated
2075 * in terms of the internal build space in embed_options,
2076 * but the position is still that within the current code generation.
2078 __isl_give isl_map
*isl_ast_build_get_separation_class(
2079 __isl_keep isl_ast_build
*build
)
2082 isl_space
*space_sep
, *space
;
2089 local_pos
= build
->depth
- build
->outer_pos
;
2090 ctx
= isl_ast_build_get_ctx(build
);
2091 space_sep
= isl_space_alloc(ctx
, 0, 1, 1);
2092 space_sep
= isl_space_wrap(space_sep
);
2093 space_sep
= isl_space_set_tuple_name(space_sep
, isl_dim_set
,
2094 "separation_class");
2095 space
= isl_ast_build_get_space(build
, 1);
2096 space_sep
= isl_space_align_params(space_sep
, isl_space_copy(space
));
2097 space
= isl_space_map_from_domain_and_range(space
, space_sep
);
2099 res
= isl_union_map_extract_map(build
->options
, space
);
2100 res
= isl_map_fix_si(res
, isl_dim_out
, 0, local_pos
);
2101 res
= isl_map_coalesce(res
);
2106 /* Eliminate dimensions inner to the current dimension.
2108 __isl_give isl_set
*isl_ast_build_eliminate_inner(
2109 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2115 return isl_set_free(set
);
2117 dim
= isl_set_dim(set
, isl_dim_set
);
2118 depth
= build
->depth
;
2119 set
= isl_set_detect_equalities(set
);
2120 set
= isl_set_eliminate(set
, isl_dim_set
, depth
+ 1, dim
- (depth
+ 1));
2125 /* Eliminate unknown divs and divs that depend on the current dimension.
2127 * Note that during the elimination of unknown divs, we may discover
2128 * an explicit representation of some other unknown divs, which may
2129 * depend on the current dimension. We therefore need to eliminate
2130 * unknown divs first.
2132 __isl_give isl_set
*isl_ast_build_eliminate_divs(
2133 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2138 return isl_set_free(set
);
2140 set
= isl_set_remove_unknown_divs(set
);
2141 depth
= build
->depth
;
2142 set
= isl_set_remove_divs_involving_dims(set
, isl_dim_set
, depth
, 1);
2147 /* Eliminate dimensions inner to the current dimension as well as
2148 * unknown divs and divs that depend on the current dimension.
2149 * The result then consists only of constraints that are independent
2150 * of the current dimension and upper and lower bounds on the current
2153 __isl_give isl_set
*isl_ast_build_eliminate(
2154 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*domain
)
2156 domain
= isl_ast_build_eliminate_inner(build
, domain
);
2157 domain
= isl_ast_build_eliminate_divs(build
, domain
);
2161 /* Replace build->single_valued by "sv".
2163 __isl_give isl_ast_build
*isl_ast_build_set_single_valued(
2164 __isl_take isl_ast_build
*build
, int sv
)
2168 if (build
->single_valued
== sv
)
2170 build
= isl_ast_build_cow(build
);
2173 build
->single_valued
= sv
;