2 * Copyright 2012-2013 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(isl_space_copy(space
));
70 isl_multi_aff_free(build
->internal2input
);
71 build
->internal2input
= isl_multi_aff_identity(space
);
73 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
74 !build
->pending
|| !build
->values
|| !build
->internal2input
||
75 !build
->strides
|| !build
->offsets
|| !build
->options
)
76 return isl_ast_build_free(build
);
80 isl_space_free(space
);
81 return isl_ast_build_free(build
);
84 /* Return an isl_id called "c%d", with "%d" set to "i".
85 * If an isl_id with such a name already appears among the parameters
86 * in build->domain, then adjust the name to "c%d_%d".
88 static __isl_give isl_id
*generate_name(isl_ctx
*ctx
, int i
,
89 __isl_keep isl_ast_build
*build
)
93 isl_set
*dom
= build
->domain
;
95 snprintf(name
, sizeof(name
), "c%d", i
);
97 while (isl_set_find_dim_by_name(dom
, isl_dim_param
, name
) >= 0)
98 snprintf(name
, sizeof(name
), "c%d_%d", i
, j
++);
99 return isl_id_alloc(ctx
, name
, NULL
);
102 /* Create an isl_ast_build with "set" as domain.
104 * The input set is usually a parameter domain, but we currently allow it to
105 * be any kind of set. We set the domain of the returned isl_ast_build
106 * to "set" and initialize all the other fields to default values.
108 __isl_give isl_ast_build
*isl_ast_build_from_context(__isl_take isl_set
*set
)
113 isl_ast_build
*build
;
115 set
= isl_set_compute_divs(set
);
119 ctx
= isl_set_get_ctx(set
);
121 build
= isl_calloc_type(ctx
, isl_ast_build
);
127 build
->generated
= isl_set_copy(build
->domain
);
128 build
->pending
= isl_set_universe(isl_set_get_space(build
->domain
));
129 build
->options
= isl_union_map_empty(isl_space_params_alloc(ctx
, 0));
130 n
= isl_set_dim(set
, isl_dim_set
);
132 build
->iterators
= isl_id_list_alloc(ctx
, n
);
133 for (i
= 0; i
< n
; ++i
) {
135 if (isl_set_has_dim_id(set
, isl_dim_set
, i
))
136 id
= isl_set_get_dim_id(set
, isl_dim_set
, i
);
138 id
= generate_name(ctx
, i
, build
);
139 build
->iterators
= isl_id_list_add(build
->iterators
, id
);
141 space
= isl_set_get_space(set
);
142 if (isl_space_is_params(space
))
143 space
= isl_space_set_from_params(space
);
145 return isl_ast_build_init_derived(build
, space
);
151 /* Create an isl_ast_build with a universe (parametric) context.
153 __isl_give isl_ast_build
*isl_ast_build_alloc(isl_ctx
*ctx
)
158 space
= isl_space_params_alloc(ctx
, 0);
159 context
= isl_set_universe(space
);
161 return isl_ast_build_from_context(context
);
164 __isl_give isl_ast_build
*isl_ast_build_copy(__isl_keep isl_ast_build
*build
)
173 __isl_give isl_ast_build
*isl_ast_build_dup(__isl_keep isl_ast_build
*build
)
181 ctx
= isl_ast_build_get_ctx(build
);
182 dup
= isl_calloc_type(ctx
, isl_ast_build
);
187 dup
->outer_pos
= build
->outer_pos
;
188 dup
->depth
= build
->depth
;
189 dup
->iterators
= isl_id_list_copy(build
->iterators
);
190 dup
->domain
= isl_set_copy(build
->domain
);
191 dup
->generated
= isl_set_copy(build
->generated
);
192 dup
->pending
= isl_set_copy(build
->pending
);
193 dup
->values
= isl_multi_aff_copy(build
->values
);
194 dup
->internal2input
= isl_multi_aff_copy(build
->internal2input
);
195 dup
->value
= isl_pw_aff_copy(build
->value
);
196 dup
->strides
= isl_vec_copy(build
->strides
);
197 dup
->offsets
= isl_multi_aff_copy(build
->offsets
);
198 dup
->executed
= isl_union_map_copy(build
->executed
);
199 dup
->single_valued
= build
->single_valued
;
200 dup
->options
= isl_union_map_copy(build
->options
);
201 dup
->at_each_domain
= build
->at_each_domain
;
202 dup
->at_each_domain_user
= build
->at_each_domain_user
;
203 dup
->before_each_for
= build
->before_each_for
;
204 dup
->before_each_for_user
= build
->before_each_for_user
;
205 dup
->after_each_for
= build
->after_each_for
;
206 dup
->after_each_for_user
= build
->after_each_for_user
;
207 dup
->create_leaf
= build
->create_leaf
;
208 dup
->create_leaf_user
= build
->create_leaf_user
;
209 dup
->node
= isl_schedule_node_copy(build
->node
);
210 if (build
->loop_type
) {
214 dup
->loop_type
= isl_alloc_array(ctx
,
215 enum isl_ast_loop_type
, dup
->n
);
216 if (dup
->n
&& !dup
->loop_type
)
217 return isl_ast_build_free(dup
);
218 for (i
= 0; i
< dup
->n
; ++i
)
219 dup
->loop_type
[i
] = build
->loop_type
[i
];
222 if (!dup
->iterators
|| !dup
->domain
|| !dup
->generated
||
223 !dup
->pending
|| !dup
->values
||
224 !dup
->strides
|| !dup
->offsets
|| !dup
->options
||
225 (build
->internal2input
&& !dup
->internal2input
) ||
226 (build
->executed
&& !dup
->executed
) ||
227 (build
->value
&& !dup
->value
) ||
228 (build
->node
&& !dup
->node
))
229 return isl_ast_build_free(dup
);
234 /* Align the parameters of "build" to those of "model", introducing
235 * additional parameters if needed.
237 __isl_give isl_ast_build
*isl_ast_build_align_params(
238 __isl_take isl_ast_build
*build
, __isl_take isl_space
*model
)
240 build
= isl_ast_build_cow(build
);
244 build
->domain
= isl_set_align_params(build
->domain
,
245 isl_space_copy(model
));
246 build
->generated
= isl_set_align_params(build
->generated
,
247 isl_space_copy(model
));
248 build
->pending
= isl_set_align_params(build
->pending
,
249 isl_space_copy(model
));
250 build
->values
= isl_multi_aff_align_params(build
->values
,
251 isl_space_copy(model
));
252 build
->offsets
= isl_multi_aff_align_params(build
->offsets
,
253 isl_space_copy(model
));
254 build
->options
= isl_union_map_align_params(build
->options
,
255 isl_space_copy(model
));
256 if (build
->internal2input
) {
257 build
->internal2input
=
258 isl_multi_aff_align_params(build
->internal2input
,
260 if (!build
->internal2input
)
261 return isl_ast_build_free(build
);
263 isl_space_free(model
);
266 if (!build
->domain
|| !build
->values
|| !build
->offsets
||
268 return isl_ast_build_free(build
);
272 isl_space_free(model
);
276 __isl_give isl_ast_build
*isl_ast_build_cow(__isl_take isl_ast_build
*build
)
284 return isl_ast_build_dup(build
);
287 __isl_null isl_ast_build
*isl_ast_build_free(
288 __isl_take isl_ast_build
*build
)
293 if (--build
->ref
> 0)
296 isl_id_list_free(build
->iterators
);
297 isl_set_free(build
->domain
);
298 isl_set_free(build
->generated
);
299 isl_set_free(build
->pending
);
300 isl_multi_aff_free(build
->values
);
301 isl_multi_aff_free(build
->internal2input
);
302 isl_pw_aff_free(build
->value
);
303 isl_vec_free(build
->strides
);
304 isl_multi_aff_free(build
->offsets
);
305 isl_multi_aff_free(build
->schedule_map
);
306 isl_union_map_free(build
->executed
);
307 isl_union_map_free(build
->options
);
308 isl_schedule_node_free(build
->node
);
309 free(build
->loop_type
);
310 isl_set_free(build
->isolated
);
317 isl_ctx
*isl_ast_build_get_ctx(__isl_keep isl_ast_build
*build
)
319 return build
? isl_set_get_ctx(build
->domain
) : NULL
;
322 /* Replace build->options by "options".
324 __isl_give isl_ast_build
*isl_ast_build_set_options(
325 __isl_take isl_ast_build
*build
, __isl_take isl_union_map
*options
)
327 build
= isl_ast_build_cow(build
);
329 if (!build
|| !options
)
332 isl_union_map_free(build
->options
);
333 build
->options
= options
;
337 isl_union_map_free(options
);
338 return isl_ast_build_free(build
);
341 /* Set the iterators for the next code generation.
343 * If we still have some iterators left from the previous code generation
344 * (if any) or if iterators have already been set by a previous
345 * call to this function, then we remove them first.
347 __isl_give isl_ast_build
*isl_ast_build_set_iterators(
348 __isl_take isl_ast_build
*build
, __isl_take isl_id_list
*iterators
)
352 build
= isl_ast_build_cow(build
);
356 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
357 n_it
= isl_id_list_n_id(build
->iterators
);
359 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
360 "isl_ast_build in inconsistent state", goto error
);
362 build
->iterators
= isl_id_list_drop(build
->iterators
,
364 build
->iterators
= isl_id_list_concat(build
->iterators
, iterators
);
365 if (!build
->iterators
)
366 return isl_ast_build_free(build
);
370 isl_id_list_free(iterators
);
371 return isl_ast_build_free(build
);
374 /* Set the "at_each_domain" callback of "build" to "fn".
376 __isl_give isl_ast_build
*isl_ast_build_set_at_each_domain(
377 __isl_take isl_ast_build
*build
,
378 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_node
*node
,
379 __isl_keep isl_ast_build
*build
, void *user
), void *user
)
381 build
= isl_ast_build_cow(build
);
386 build
->at_each_domain
= fn
;
387 build
->at_each_domain_user
= user
;
392 /* Set the "before_each_for" callback of "build" to "fn".
394 __isl_give isl_ast_build
*isl_ast_build_set_before_each_for(
395 __isl_take isl_ast_build
*build
,
396 __isl_give isl_id
*(*fn
)(__isl_keep isl_ast_build
*build
,
397 void *user
), void *user
)
399 build
= isl_ast_build_cow(build
);
404 build
->before_each_for
= fn
;
405 build
->before_each_for_user
= user
;
410 /* Set the "after_each_for" callback of "build" to "fn".
412 __isl_give isl_ast_build
*isl_ast_build_set_after_each_for(
413 __isl_take isl_ast_build
*build
,
414 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_node
*node
,
415 __isl_keep isl_ast_build
*build
, void *user
), void *user
)
417 build
= isl_ast_build_cow(build
);
422 build
->after_each_for
= fn
;
423 build
->after_each_for_user
= user
;
428 /* Set the "create_leaf" callback of "build" to "fn".
430 __isl_give isl_ast_build
*isl_ast_build_set_create_leaf(
431 __isl_take isl_ast_build
*build
,
432 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_build
*build
,
433 void *user
), void *user
)
435 build
= isl_ast_build_cow(build
);
440 build
->create_leaf
= fn
;
441 build
->create_leaf_user
= user
;
446 /* Clear all information that is specific to this code generation
447 * and that is (probably) not meaningful to any nested code generation.
449 __isl_give isl_ast_build
*isl_ast_build_clear_local_info(
450 __isl_take isl_ast_build
*build
)
454 build
= isl_ast_build_cow(build
);
458 space
= isl_union_map_get_space(build
->options
);
459 isl_union_map_free(build
->options
);
460 build
->options
= isl_union_map_empty(space
);
462 build
->at_each_domain
= NULL
;
463 build
->at_each_domain_user
= NULL
;
464 build
->before_each_for
= NULL
;
465 build
->before_each_for_user
= NULL
;
466 build
->after_each_for
= NULL
;
467 build
->after_each_for_user
= NULL
;
468 build
->create_leaf
= NULL
;
469 build
->create_leaf_user
= NULL
;
472 return isl_ast_build_free(build
);
477 /* Have any loops been eliminated?
478 * That is, do any of the original schedule dimensions have a fixed
479 * value that has been substituted?
481 static int any_eliminated(isl_ast_build
*build
)
485 for (i
= 0; i
< build
->depth
; ++i
)
486 if (isl_ast_build_has_affine_value(build
, i
))
492 /* Clear build->schedule_map.
493 * This function should be called whenever anything that might affect
494 * the result of isl_ast_build_get_schedule_map_multi_aff changes.
495 * In particular, it should be called when the depth is changed or
496 * when an iterator is determined to have a fixed value.
498 static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build
*build
)
502 isl_multi_aff_free(build
->schedule_map
);
503 build
->schedule_map
= NULL
;
506 /* Do we need a (non-trivial) schedule map?
507 * That is, is the internal schedule space different from
508 * the external schedule space?
510 * The internal and external schedule spaces are only the same
511 * if code has been generated for the entire schedule and if none
512 * of the loops have been eliminated.
514 __isl_give
int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build
*build
)
521 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
522 return build
->depth
!= dim
|| any_eliminated(build
);
525 /* Return a mapping from the internal schedule space to the external
526 * schedule space in the form of an isl_multi_aff.
527 * The internal schedule space originally corresponds to that of the
528 * input schedule. This may change during the code generation if
529 * if isl_ast_build_insert_dim is ever called.
530 * The external schedule space corresponds to the
531 * loops that have been generated.
533 * Currently, the only difference between the internal schedule domain
534 * and the external schedule domain is that some dimensions are projected
535 * out in the external schedule domain. In particular, the dimensions
536 * for which no code has been generated yet and the dimensions that correspond
537 * to eliminated loops.
539 * We cache a copy of the schedule_map in build->schedule_map.
540 * The cache is cleared through isl_ast_build_reset_schedule_map
541 * whenever anything changes that might affect the result of this function.
543 __isl_give isl_multi_aff
*isl_ast_build_get_schedule_map_multi_aff(
544 __isl_keep isl_ast_build
*build
)
551 if (build
->schedule_map
)
552 return isl_multi_aff_copy(build
->schedule_map
);
554 space
= isl_ast_build_get_space(build
, 1);
555 space
= isl_space_map_from_set(space
);
556 ma
= isl_multi_aff_identity(space
);
557 if (isl_ast_build_need_schedule_map(build
)) {
559 int dim
= isl_set_dim(build
->domain
, isl_dim_set
);
560 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
,
561 build
->depth
, dim
- build
->depth
);
562 for (i
= build
->depth
- 1; i
>= 0; --i
)
563 if (isl_ast_build_has_affine_value(build
, i
))
564 ma
= isl_multi_aff_drop_dims(ma
,
568 build
->schedule_map
= ma
;
569 return isl_multi_aff_copy(build
->schedule_map
);
572 /* Return a mapping from the internal schedule space to the external
573 * schedule space in the form of an isl_map.
575 __isl_give isl_map
*isl_ast_build_get_schedule_map(
576 __isl_keep isl_ast_build
*build
)
580 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
581 return isl_map_from_multi_aff(ma
);
584 /* Return the position of the dimension in build->domain for which
585 * an AST node is currently being generated.
587 int isl_ast_build_get_depth(__isl_keep isl_ast_build
*build
)
589 return build
? build
->depth
: -1;
592 /* Prepare for generating code for the next level.
593 * In particular, increase the depth and reset any information
594 * that is local to the current depth.
596 __isl_give isl_ast_build
*isl_ast_build_increase_depth(
597 __isl_take isl_ast_build
*build
)
599 build
= isl_ast_build_cow(build
);
603 isl_ast_build_reset_schedule_map(build
);
604 build
->value
= isl_pw_aff_free(build
->value
);
608 void isl_ast_build_dump(__isl_keep isl_ast_build
*build
)
613 fprintf(stderr
, "domain: ");
614 isl_set_dump(build
->domain
);
615 fprintf(stderr
, "generated: ");
616 isl_set_dump(build
->generated
);
617 fprintf(stderr
, "pending: ");
618 isl_set_dump(build
->pending
);
619 fprintf(stderr
, "iterators: ");
620 isl_id_list_dump(build
->iterators
);
621 fprintf(stderr
, "values: ");
622 isl_multi_aff_dump(build
->values
);
624 fprintf(stderr
, "value: ");
625 isl_pw_aff_dump(build
->value
);
627 fprintf(stderr
, "strides: ");
628 isl_vec_dump(build
->strides
);
629 fprintf(stderr
, "offsets: ");
630 isl_multi_aff_dump(build
->offsets
);
631 fprintf(stderr
, "internal2input: ");
632 isl_multi_aff_dump(build
->internal2input
);
635 /* Initialize "build" for AST construction in schedule space "space"
636 * in the case that build->domain is a parameter set.
638 * build->iterators is assumed to have been updated already.
640 static __isl_give isl_ast_build
*isl_ast_build_init(
641 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
645 build
= isl_ast_build_cow(build
);
649 set
= isl_set_universe(isl_space_copy(space
));
650 build
->domain
= isl_set_intersect_params(isl_set_copy(set
),
652 build
->pending
= isl_set_intersect_params(isl_set_copy(set
),
654 build
->generated
= isl_set_intersect_params(set
, build
->generated
);
656 return isl_ast_build_init_derived(build
, space
);
658 isl_ast_build_free(build
);
659 isl_space_free(space
);
663 /* Assign "aff" to *user and return -1, effectively extracting
664 * the first (and presumably only) affine expression in the isl_pw_aff
665 * on which this function is used.
667 static int extract_single_piece(__isl_take isl_set
*set
,
668 __isl_take isl_aff
*aff
, void *user
)
678 /* Intersect "set" with the stride constraint of "build", if any.
680 static __isl_give isl_set
*intersect_stride_constraint(__isl_take isl_set
*set
,
681 __isl_keep isl_ast_build
*build
)
686 return isl_set_free(set
);
687 if (!isl_ast_build_has_stride(build
, build
->depth
))
690 stride
= isl_ast_build_get_stride_constraint(build
);
691 return isl_set_intersect(set
, stride
);
694 /* Check if the given bounds on the current dimension (together with
695 * the stride constraint, if any) imply that
696 * this current dimension attains only a single value (in terms of
697 * parameters and outer dimensions).
698 * If so, we record it in build->value.
699 * If, moreover, this value can be represented as a single affine expression,
700 * then we also update build->values, effectively marking the current
701 * dimension as "eliminated".
703 * When computing the gist of the fixed value that can be represented
704 * as a single affine expression, it is important to only take into
705 * account the domain constraints in the original AST build and
706 * not the domain of the affine expression itself.
707 * Otherwise, a [i/3] is changed into a i/3 because we know that i
708 * is a multiple of 3, but then we end up not expressing anywhere
709 * in the context that i is a multiple of 3.
711 static __isl_give isl_ast_build
*update_values(
712 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
715 isl_pw_multi_aff
*pma
;
720 set
= isl_set_from_basic_set(bounds
);
721 set
= isl_set_intersect(set
, isl_set_copy(build
->domain
));
722 set
= intersect_stride_constraint(set
, build
);
723 it_map
= isl_ast_build_map_to_iterator(build
, set
);
725 sv
= isl_map_is_single_valued(it_map
);
727 build
= isl_ast_build_free(build
);
729 isl_map_free(it_map
);
733 pma
= isl_pw_multi_aff_from_map(it_map
);
734 build
->value
= isl_pw_multi_aff_get_pw_aff(pma
, 0);
735 build
->value
= isl_ast_build_compute_gist_pw_aff(build
, build
->value
);
736 build
->value
= isl_pw_aff_coalesce(build
->value
);
737 isl_pw_multi_aff_free(pma
);
740 return isl_ast_build_free(build
);
742 if (isl_pw_aff_n_piece(build
->value
) != 1)
745 isl_pw_aff_foreach_piece(build
->value
, &extract_single_piece
, &aff
);
747 build
->values
= isl_multi_aff_set_aff(build
->values
, build
->depth
, aff
);
749 return isl_ast_build_free(build
);
750 isl_ast_build_reset_schedule_map(build
);
754 /* Update the AST build based on the given loop bounds for
755 * the current dimension and the stride information available in the build.
757 * We first make sure that the bounds do not refer to any iterators
758 * that have already been eliminated.
759 * Then, we check if the bounds imply that the current iterator
761 * If they do and if this fixed value can be expressed as a single
762 * affine expression, we eliminate the iterators from the bounds.
763 * Note that we cannot simply plug in this single value using
764 * isl_basic_set_preimage_multi_aff as the single value may only
765 * be defined on a subset of the domain. Plugging in the value
766 * would restrict the build domain to this subset, while this
767 * restriction may not be reflected in the generated code.
768 * Finally, we intersect build->domain with the updated bounds.
769 * We also add the stride constraint unless we have been able
770 * to find a fixed value expressed as a single affine expression.
772 * Note that the check for a fixed value in update_values requires
773 * us to intersect the bounds with the current build domain.
774 * When we intersect build->domain with the updated bounds in
775 * the final step, we make sure that these updated bounds have
776 * not been intersected with the old build->domain.
777 * Otherwise, we would indirectly intersect the build domain with itself,
778 * which can lead to inefficiencies, in particular if the build domain
779 * contains any unknown divs.
781 __isl_give isl_ast_build
*isl_ast_build_set_loop_bounds(
782 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
786 build
= isl_ast_build_cow(build
);
790 bounds
= isl_basic_set_preimage_multi_aff(bounds
,
791 isl_multi_aff_copy(build
->values
));
792 build
= update_values(build
, isl_basic_set_copy(bounds
));
795 set
= isl_set_from_basic_set(isl_basic_set_copy(bounds
));
796 if (isl_ast_build_has_affine_value(build
, build
->depth
)) {
797 set
= isl_set_eliminate(set
, isl_dim_set
, build
->depth
, 1);
798 set
= isl_set_compute_divs(set
);
799 build
->pending
= isl_set_intersect(build
->pending
,
801 build
->domain
= isl_set_intersect(build
->domain
, set
);
803 isl_basic_set
*generated
, *pending
;
805 pending
= isl_basic_set_copy(bounds
);
806 pending
= isl_basic_set_drop_constraints_involving_dims(pending
,
807 isl_dim_set
, build
->depth
, 1);
808 build
->pending
= isl_set_intersect(build
->pending
,
809 isl_set_from_basic_set(pending
));
810 generated
= isl_basic_set_copy(bounds
);
811 generated
= isl_basic_set_drop_constraints_not_involving_dims(
812 generated
, isl_dim_set
, build
->depth
, 1);
813 build
->generated
= isl_set_intersect(build
->generated
,
814 isl_set_from_basic_set(generated
));
815 build
->domain
= isl_set_intersect(build
->domain
, set
);
816 build
= isl_ast_build_include_stride(build
);
820 isl_basic_set_free(bounds
);
822 if (!build
->domain
|| !build
->pending
|| !build
->generated
)
823 return isl_ast_build_free(build
);
827 isl_ast_build_free(build
);
828 isl_basic_set_free(bounds
);
832 /* Intersect build->domain with "set", where "set" is specified
833 * in terms of the internal schedule domain.
835 static __isl_give isl_ast_build
*isl_ast_build_restrict_internal(
836 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
838 build
= isl_ast_build_cow(build
);
842 set
= isl_set_compute_divs(set
);
843 build
->domain
= isl_set_intersect(build
->domain
, set
);
844 build
->domain
= isl_set_coalesce(build
->domain
);
847 return isl_ast_build_free(build
);
851 isl_ast_build_free(build
);
856 /* Intersect build->generated and build->domain with "set",
857 * where "set" is specified in terms of the internal schedule domain.
859 __isl_give isl_ast_build
*isl_ast_build_restrict_generated(
860 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
862 set
= isl_set_compute_divs(set
);
863 build
= isl_ast_build_restrict_internal(build
, isl_set_copy(set
));
864 build
= isl_ast_build_cow(build
);
868 build
->generated
= isl_set_intersect(build
->generated
, set
);
869 build
->generated
= isl_set_coalesce(build
->generated
);
871 if (!build
->generated
)
872 return isl_ast_build_free(build
);
876 isl_ast_build_free(build
);
881 /* Replace the set of pending constraints by "guard", which is then
882 * no longer considered as pending.
883 * That is, add "guard" to the generated constraints and clear all pending
884 * constraints, making the domain equal to the generated constraints.
886 __isl_give isl_ast_build
*isl_ast_build_replace_pending_by_guard(
887 __isl_take isl_ast_build
*build
, __isl_take isl_set
*guard
)
889 build
= isl_ast_build_restrict_generated(build
, guard
);
890 build
= isl_ast_build_cow(build
);
894 isl_set_free(build
->domain
);
895 build
->domain
= isl_set_copy(build
->generated
);
896 isl_set_free(build
->pending
);
897 build
->pending
= isl_set_universe(isl_set_get_space(build
->domain
));
900 return isl_ast_build_free(build
);
905 /* Intersect build->pending and build->domain with "set",
906 * where "set" is specified in terms of the internal schedule domain.
908 __isl_give isl_ast_build
*isl_ast_build_restrict_pending(
909 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
911 set
= isl_set_compute_divs(set
);
912 build
= isl_ast_build_restrict_internal(build
, isl_set_copy(set
));
913 build
= isl_ast_build_cow(build
);
917 build
->pending
= isl_set_intersect(build
->pending
, set
);
918 build
->pending
= isl_set_coalesce(build
->pending
);
921 return isl_ast_build_free(build
);
925 isl_ast_build_free(build
);
930 /* Intersect build->domain with "set", where "set" is specified
931 * in terms of the external schedule domain.
933 __isl_give isl_ast_build
*isl_ast_build_restrict(
934 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
936 if (isl_set_is_params(set
))
937 return isl_ast_build_restrict_generated(build
, set
);
939 if (isl_ast_build_need_schedule_map(build
)) {
941 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
942 set
= isl_set_preimage_multi_aff(set
, ma
);
944 return isl_ast_build_restrict_generated(build
, set
);
947 /* Replace build->executed by "executed".
949 __isl_give isl_ast_build
*isl_ast_build_set_executed(
950 __isl_take isl_ast_build
*build
, __isl_take isl_union_map
*executed
)
952 build
= isl_ast_build_cow(build
);
956 isl_union_map_free(build
->executed
);
957 build
->executed
= executed
;
961 isl_ast_build_free(build
);
962 isl_union_map_free(executed
);
966 /* Does "build" point to a band node?
967 * That is, are we currently handling a band node inside a schedule tree?
969 int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build
*build
)
973 return build
->node
!= NULL
;
976 /* Return a copy of the band node that "build" refers to.
978 __isl_give isl_schedule_node
*isl_ast_build_get_schedule_node(
979 __isl_keep isl_ast_build
*build
)
983 return isl_schedule_node_copy(build
->node
);
986 /* Extract the loop AST generation types for the members of build->node
987 * and store them in build->loop_type.
989 static __isl_give isl_ast_build
*extract_loop_types(
990 __isl_take isl_ast_build
*build
)
994 isl_schedule_node
*node
;
998 ctx
= isl_ast_build_get_ctx(build
);
1000 isl_die(ctx
, isl_error_internal
, "missing AST node",
1001 return isl_ast_build_free(build
));
1003 free(build
->loop_type
);
1004 build
->n
= isl_schedule_node_band_n_member(build
->node
);
1005 build
->loop_type
= isl_alloc_array(ctx
,
1006 enum isl_ast_loop_type
, build
->n
);
1007 if (build
->n
&& !build
->loop_type
)
1008 return isl_ast_build_free(build
);
1010 for (i
= 0; i
< build
->n
; ++i
)
1011 build
->loop_type
[i
] =
1012 isl_schedule_node_band_member_get_ast_loop_type(node
, i
);
1017 /* Replace the band node that "build" refers to by "node" and
1018 * extract the corresponding loop AST generation types.
1020 __isl_give isl_ast_build
*isl_ast_build_set_schedule_node(
1021 __isl_take isl_ast_build
*build
,
1022 __isl_take isl_schedule_node
*node
)
1024 build
= isl_ast_build_cow(build
);
1025 if (!build
|| !node
)
1028 isl_schedule_node_free(build
->node
);
1031 build
= extract_loop_types(build
);
1035 isl_ast_build_free(build
);
1036 isl_schedule_node_free(node
);
1040 /* Remove any reference to a band node from "build".
1042 __isl_give isl_ast_build
*isl_ast_build_reset_schedule_node(
1043 __isl_take isl_ast_build
*build
)
1045 build
= isl_ast_build_cow(build
);
1049 isl_schedule_node_free(build
->node
);
1055 /* Return a copy of the current schedule domain.
1057 __isl_give isl_set
*isl_ast_build_get_domain(__isl_keep isl_ast_build
*build
)
1059 return build
? isl_set_copy(build
->domain
) : NULL
;
1062 /* Return a copy of the set of pending constraints.
1064 __isl_give isl_set
*isl_ast_build_get_pending(
1065 __isl_keep isl_ast_build
*build
)
1067 return build
? isl_set_copy(build
->pending
) : NULL
;
1070 /* Return a copy of the set of generated constraints.
1072 __isl_give isl_set
*isl_ast_build_get_generated(
1073 __isl_keep isl_ast_build
*build
)
1075 return build
? isl_set_copy(build
->generated
) : NULL
;
1078 /* Return a copy of the map from the internal schedule domain
1079 * to the original input schedule domain.
1081 __isl_give isl_multi_aff
*isl_ast_build_get_internal2input(
1082 __isl_keep isl_ast_build
*build
)
1084 return build
? isl_multi_aff_copy(build
->internal2input
) : NULL
;
1087 /* Return the number of variables of the given type
1088 * in the (internal) schedule space.
1090 unsigned isl_ast_build_dim(__isl_keep isl_ast_build
*build
,
1091 enum isl_dim_type type
)
1095 return isl_set_dim(build
->domain
, type
);
1098 /* Return the (schedule) space of "build".
1100 * If "internal" is set, then this space is the space of the internal
1101 * representation of the entire schedule, including those parts for
1102 * which no code has been generated yet.
1104 * If "internal" is not set, then this space is the external representation
1105 * of the loops generated so far.
1107 __isl_give isl_space
*isl_ast_build_get_space(__isl_keep isl_ast_build
*build
,
1117 space
= isl_set_get_space(build
->domain
);
1121 if (!isl_ast_build_need_schedule_map(build
))
1124 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
1125 space
= isl_space_drop_dims(space
, isl_dim_set
,
1126 build
->depth
, dim
- build
->depth
);
1127 for (i
= build
->depth
- 1; i
>= 0; --i
)
1128 if (isl_ast_build_has_affine_value(build
, i
))
1129 space
= isl_space_drop_dims(space
, isl_dim_set
, i
, 1);
1134 /* Return the external representation of the schedule space of "build",
1135 * i.e., a space with a dimension for each loop generated so far,
1136 * with the names of the dimensions set to the loop iterators.
1138 __isl_give isl_space
*isl_ast_build_get_schedule_space(
1139 __isl_keep isl_ast_build
*build
)
1147 space
= isl_ast_build_get_space(build
, 0);
1150 for (i
= 0; i
< build
->depth
; ++i
) {
1153 if (isl_ast_build_has_affine_value(build
, i
)) {
1158 id
= isl_ast_build_get_iterator_id(build
, i
);
1159 space
= isl_space_set_dim_id(space
, isl_dim_set
, i
- skip
, id
);
1165 /* Return the current schedule, as stored in build->executed, in terms
1166 * of the external schedule domain.
1168 __isl_give isl_union_map
*isl_ast_build_get_schedule(
1169 __isl_keep isl_ast_build
*build
)
1171 isl_union_map
*executed
;
1172 isl_union_map
*schedule
;
1177 executed
= isl_union_map_copy(build
->executed
);
1178 if (isl_ast_build_need_schedule_map(build
)) {
1179 isl_map
*proj
= isl_ast_build_get_schedule_map(build
);
1180 executed
= isl_union_map_apply_domain(executed
,
1181 isl_union_map_from_map(proj
));
1183 schedule
= isl_union_map_reverse(executed
);
1188 /* Return the iterator attached to the internal schedule dimension "pos".
1190 __isl_give isl_id
*isl_ast_build_get_iterator_id(
1191 __isl_keep isl_ast_build
*build
, int pos
)
1196 return isl_id_list_get_id(build
->iterators
, pos
);
1199 /* Set the stride and offset of the current dimension to the given
1200 * value and expression.
1202 * If we had already found a stride before, then the two strides
1203 * are combined into a single stride.
1205 * In particular, if the new stride information is of the form
1209 * and the old stride information is of the form
1213 * then we compute the extended gcd of s and s2
1217 * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
1218 * and the second with t2 = a s1/g.
1221 * i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
1223 * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
1224 * is the combined stride.
1226 static __isl_give isl_ast_build
*set_stride(__isl_take isl_ast_build
*build
,
1227 __isl_take isl_val
*stride
, __isl_take isl_aff
*offset
)
1231 build
= isl_ast_build_cow(build
);
1232 if (!build
|| !stride
|| !offset
)
1237 if (isl_ast_build_has_stride(build
, pos
)) {
1238 isl_val
*stride2
, *a
, *b
, *g
;
1241 stride2
= isl_vec_get_element_val(build
->strides
, pos
);
1242 g
= isl_val_gcdext(isl_val_copy(stride
), isl_val_copy(stride2
),
1244 a
= isl_val_mul(a
, isl_val_copy(stride
));
1245 a
= isl_val_div(a
, isl_val_copy(g
));
1246 stride2
= isl_val_div(stride2
, g
);
1247 b
= isl_val_mul(b
, isl_val_copy(stride2
));
1248 stride
= isl_val_mul(stride
, stride2
);
1250 offset2
= isl_multi_aff_get_aff(build
->offsets
, pos
);
1251 offset2
= isl_aff_scale_val(offset2
, a
);
1252 offset
= isl_aff_scale_val(offset
, b
);
1253 offset
= isl_aff_add(offset
, offset2
);
1256 build
->strides
= isl_vec_set_element_val(build
->strides
, pos
, stride
);
1257 build
->offsets
= isl_multi_aff_set_aff(build
->offsets
, pos
, offset
);
1258 if (!build
->strides
|| !build
->offsets
)
1259 return isl_ast_build_free(build
);
1263 isl_val_free(stride
);
1264 isl_aff_free(offset
);
1265 return isl_ast_build_free(build
);
1268 /* Return a set expressing the stride constraint at the current depth.
1270 * In particular, if the current iterator (i) is known to attain values
1274 * where f is the offset and s is the stride, then the returned set
1275 * expresses the constraint
1279 __isl_give isl_set
*isl_ast_build_get_stride_constraint(
1280 __isl_keep isl_ast_build
*build
)
1292 if (!isl_ast_build_has_stride(build
, pos
))
1293 return isl_set_universe(isl_ast_build_get_space(build
, 1));
1295 stride
= isl_ast_build_get_stride(build
, pos
);
1296 aff
= isl_ast_build_get_offset(build
, pos
);
1297 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, pos
, -1);
1298 aff
= isl_aff_mod_val(aff
, stride
);
1299 set
= isl_set_from_basic_set(isl_aff_zero_basic_set(aff
));
1304 /* Return the expansion implied by the stride and offset at the current
1307 * That is, return the mapping
1309 * [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1310 * -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]
1312 * where s is the stride at the current depth d and offset(i) is
1313 * the corresponding offset.
1315 __isl_give isl_multi_aff
*isl_ast_build_get_stride_expansion(
1316 __isl_keep isl_ast_build
*build
)
1321 isl_aff
*aff
, *offset
;
1327 pos
= isl_ast_build_get_depth(build
);
1328 space
= isl_ast_build_get_space(build
, 1);
1329 space
= isl_space_map_from_set(space
);
1330 ma
= isl_multi_aff_identity(space
);
1332 if (!isl_ast_build_has_stride(build
, pos
))
1335 offset
= isl_ast_build_get_offset(build
, pos
);
1336 stride
= isl_ast_build_get_stride(build
, pos
);
1337 aff
= isl_multi_aff_get_aff(ma
, pos
);
1338 aff
= isl_aff_scale_val(aff
, stride
);
1339 aff
= isl_aff_add(aff
, offset
);
1340 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
1345 /* Add constraints corresponding to any previously detected
1346 * stride on the current dimension to build->domain.
1348 __isl_give isl_ast_build
*isl_ast_build_include_stride(
1349 __isl_take isl_ast_build
*build
)
1355 if (!isl_ast_build_has_stride(build
, build
->depth
))
1357 build
= isl_ast_build_cow(build
);
1361 set
= isl_ast_build_get_stride_constraint(build
);
1363 build
->domain
= isl_set_intersect(build
->domain
, isl_set_copy(set
));
1364 build
->generated
= isl_set_intersect(build
->generated
, set
);
1365 if (!build
->domain
|| !build
->generated
)
1366 return isl_ast_build_free(build
);
1371 /* Information used inside detect_stride.
1373 * "build" may be updated by detect_stride to include stride information.
1374 * "pos" is equal to build->depth.
1376 struct isl_detect_stride_data
{
1377 isl_ast_build
*build
;
1381 /* Check if constraint "c" imposes any stride on dimension data->pos
1382 * and, if so, update the stride information in data->build.
1384 * In order to impose a stride on the dimension, "c" needs to be an equality
1385 * and it needs to involve the dimension. Note that "c" may also be
1386 * a div constraint and thus an inequality that we cannot use.
1388 * Let c be of the form
1390 * h(p) + g * v * i + g * stride * f(alpha) = 0
1392 * with h(p) an expression in terms of the parameters and outer dimensions
1393 * and f(alpha) an expression in terms of the existentially quantified
1394 * variables. Note that the inner dimensions have been eliminated so
1395 * they do not appear in "c".
1397 * If "stride" is not zero and not one, then it represents a non-trivial stride
1398 * on "i". We compute a and b such that
1400 * a v + b stride = 1
1404 * g v i = -h(p) + g stride f(alpha)
1406 * a g v i = -a h(p) + g stride f(alpha)
1408 * a g v i + b g stride i = -a h(p) + g stride * (...)
1410 * g i = -a h(p) + g stride * (...)
1412 * i = -a h(p)/g + stride * (...)
1414 * The expression "-a h(p)/g" can therefore be used as offset.
1416 static int detect_stride(__isl_take isl_constraint
*c
, void *user
)
1418 struct isl_detect_stride_data
*data
= user
;
1421 isl_val
*v
, *stride
, *m
;
1423 if (!isl_constraint_is_equality(c
) ||
1424 !isl_constraint_involves_dims(c
, isl_dim_set
, data
->pos
, 1)) {
1425 isl_constraint_free(c
);
1429 ctx
= isl_constraint_get_ctx(c
);
1430 stride
= isl_val_zero(ctx
);
1431 n_div
= isl_constraint_dim(c
, isl_dim_div
);
1432 for (i
= 0; i
< n_div
; ++i
) {
1433 v
= isl_constraint_get_coefficient_val(c
, isl_dim_div
, i
);
1434 stride
= isl_val_gcd(stride
, v
);
1437 v
= isl_constraint_get_coefficient_val(c
, isl_dim_set
, data
->pos
);
1438 m
= isl_val_gcd(isl_val_copy(stride
), isl_val_copy(v
));
1439 stride
= isl_val_div(stride
, isl_val_copy(m
));
1440 v
= isl_val_div(v
, isl_val_copy(m
));
1442 if (!isl_val_is_zero(stride
) && !isl_val_is_one(stride
)) {
1444 isl_val
*gcd
, *a
, *b
;
1446 gcd
= isl_val_gcdext(v
, isl_val_copy(stride
), &a
, &b
);
1450 aff
= isl_constraint_get_aff(c
);
1451 for (i
= 0; i
< n_div
; ++i
)
1452 aff
= isl_aff_set_coefficient_si(aff
,
1454 aff
= isl_aff_set_coefficient_si(aff
, isl_dim_in
, data
->pos
, 0);
1456 aff
= isl_aff_scale_val(aff
, a
);
1457 aff
= isl_aff_scale_down_val(aff
, m
);
1458 data
->build
= set_stride(data
->build
, stride
, aff
);
1460 isl_val_free(stride
);
1465 isl_constraint_free(c
);
1469 /* Check if the constraints in "set" imply any stride on the current
1470 * dimension and, if so, record the stride information in "build"
1471 * and return the updated "build".
1473 * We compute the affine hull and then check if any of the constraints
1474 * in the hull imposes any stride on the current dimension.
1476 * We assume that inner dimensions have been eliminated from "set"
1477 * by the caller. This is needed because the common stride
1478 * may be imposed by different inner dimensions on different parts of
1481 __isl_give isl_ast_build
*isl_ast_build_detect_strides(
1482 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
1484 isl_basic_set
*hull
;
1485 struct isl_detect_stride_data data
;
1491 data
.pos
= isl_ast_build_get_depth(build
);
1492 hull
= isl_set_affine_hull(set
);
1494 if (isl_basic_set_foreach_constraint(hull
, &detect_stride
, &data
) < 0)
1495 data
.build
= isl_ast_build_free(data
.build
);
1497 isl_basic_set_free(hull
);
1504 struct isl_ast_build_involves_data
{
1509 /* Check if "map" involves the input dimension data->depth.
1511 static int involves_depth(__isl_take isl_map
*map
, void *user
)
1513 struct isl_ast_build_involves_data
*data
= user
;
1515 data
->involves
= isl_map_involves_dims(map
, isl_dim_in
, data
->depth
, 1);
1518 if (data
->involves
< 0 || data
->involves
)
1523 /* Do any options depend on the value of the dimension at the current depth?
1525 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build
*build
)
1527 struct isl_ast_build_involves_data data
;
1532 data
.depth
= build
->depth
;
1535 if (isl_union_map_foreach_map(build
->options
,
1536 &involves_depth
, &data
) < 0) {
1537 if (data
.involves
< 0 || !data
.involves
)
1541 return data
.involves
;
1544 /* Construct the map
1546 * { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1548 * with "space" the parameter space of the constructed map.
1550 static __isl_give isl_map
*construct_insertion_map(__isl_take isl_space
*space
,
1554 isl_basic_map
*bmap1
, *bmap2
;
1556 space
= isl_space_set_from_params(space
);
1557 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1558 space
= isl_space_map_from_set(space
);
1559 c
= isl_equality_alloc(isl_local_space_from_space(space
));
1560 c
= isl_constraint_set_coefficient_si(c
, isl_dim_in
, 0, 1);
1561 c
= isl_constraint_set_coefficient_si(c
, isl_dim_out
, 0, -1);
1562 bmap1
= isl_basic_map_from_constraint(isl_constraint_copy(c
));
1563 c
= isl_constraint_set_constant_si(c
, 1);
1564 bmap2
= isl_basic_map_from_constraint(c
);
1566 bmap1
= isl_basic_map_upper_bound_si(bmap1
, isl_dim_in
, 0, pos
- 1);
1567 bmap2
= isl_basic_map_lower_bound_si(bmap2
, isl_dim_in
, 0, pos
);
1569 return isl_basic_map_union(bmap1
, bmap2
);
1572 static const char *option_str
[] = {
1573 [isl_ast_loop_atomic
] = "atomic",
1574 [isl_ast_loop_unroll
] = "unroll",
1575 [isl_ast_loop_separate
] = "separate"
1578 /* Update the "options" to reflect the insertion of a dimension
1579 * at position "pos" in the schedule domain space.
1580 * "space" is the original domain space before the insertion and
1581 * may be named and/or structured.
1583 * The (relevant) input options all have "space" as domain, which
1584 * has to be mapped to the extended space.
1585 * The values of the ranges also refer to the schedule domain positions
1586 * and they therefore also need to be adjusted. In particular, values
1587 * smaller than pos do not need to change, while values greater than or
1588 * equal to pos need to be incremented.
1589 * That is, we need to apply the following map.
1591 * { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1592 * unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1593 * separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1594 * separation_class[[i] -> [c]]
1595 * -> separation_class[[i] -> [c]] : i < pos;
1596 * separation_class[[i] -> [c]]
1597 * -> separation_class[[i + 1] -> [c]] : i >= pos }
1599 static __isl_give isl_union_map
*options_insert_dim(
1600 __isl_take isl_union_map
*options
, __isl_take isl_space
*space
, int pos
)
1603 isl_union_map
*insertion
;
1604 enum isl_ast_loop_type type
;
1605 const char *name
= "separation_class";
1607 space
= isl_space_map_from_set(space
);
1608 map
= isl_map_identity(space
);
1609 map
= isl_map_insert_dims(map
, isl_dim_out
, pos
, 1);
1610 options
= isl_union_map_apply_domain(options
,
1611 isl_union_map_from_map(map
));
1616 map
= construct_insertion_map(isl_union_map_get_space(options
), pos
);
1618 insertion
= isl_union_map_empty(isl_union_map_get_space(options
));
1620 for (type
= isl_ast_loop_atomic
;
1621 type
<= isl_ast_loop_separate
; ++type
) {
1622 isl_map
*map_type
= isl_map_copy(map
);
1623 const char *name
= option_str
[type
];
1624 map_type
= isl_map_set_tuple_name(map_type
, isl_dim_in
, name
);
1625 map_type
= isl_map_set_tuple_name(map_type
, isl_dim_out
, name
);
1626 insertion
= isl_union_map_add_map(insertion
, map_type
);
1629 map
= isl_map_product(map
, isl_map_identity(isl_map_get_space(map
)));
1630 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
1631 map
= isl_map_set_tuple_name(map
, isl_dim_out
, name
);
1632 insertion
= isl_union_map_add_map(insertion
, map
);
1634 options
= isl_union_map_apply_range(options
, insertion
);
1639 /* If we are generating an AST from a schedule tree (build->node is set),
1640 * then update the loop AST generation types
1641 * to reflect the insertion of a dimension at (global) position "pos"
1642 * in the schedule domain space.
1643 * We do not need to adjust any isolate option since we would not be inserting
1644 * any dimensions if there were any isolate option.
1646 static __isl_give isl_ast_build
*node_insert_dim(
1647 __isl_take isl_ast_build
*build
, int pos
)
1651 enum isl_ast_loop_type
*loop_type
;
1654 build
= isl_ast_build_cow(build
);
1660 ctx
= isl_ast_build_get_ctx(build
);
1661 local_pos
= pos
- build
->outer_pos
;
1662 loop_type
= isl_realloc_array(ctx
, build
->loop_type
,
1663 enum isl_ast_loop_type
, build
->n
+ 1);
1665 return isl_ast_build_free(build
);
1666 build
->loop_type
= loop_type
;
1667 for (i
= build
->n
- 1; i
>= local_pos
; --i
)
1668 loop_type
[i
+ 1] = loop_type
[i
];
1669 loop_type
[local_pos
] = isl_ast_loop_default
;
1675 /* Insert a single dimension in the schedule domain at position "pos".
1676 * The new dimension is given an isl_id with the empty string as name.
1678 * The main difficulty is updating build->options to reflect the
1679 * extra dimension. This is handled in options_insert_dim.
1681 * Note that because of the dimension manipulations, the resulting
1682 * schedule domain space will always be unnamed and unstructured.
1683 * However, the original schedule domain space may be named and/or
1684 * structured, so we have to take this possibility into account
1685 * while performing the transformations.
1687 * Since the inserted schedule dimension is used by the caller
1688 * to differentiate between different domain spaces, there is
1689 * no longer a uniform mapping from the internal schedule space
1690 * to the input schedule space. The internal2input mapping is
1691 * therefore removed.
1693 __isl_give isl_ast_build
*isl_ast_build_insert_dim(
1694 __isl_take isl_ast_build
*build
, int pos
)
1697 isl_space
*space
, *ma_space
;
1701 build
= isl_ast_build_cow(build
);
1705 ctx
= isl_ast_build_get_ctx(build
);
1706 id
= isl_id_alloc(ctx
, "", NULL
);
1708 space
= isl_ast_build_get_space(build
, 1);
1709 build
->iterators
= isl_id_list_insert(build
->iterators
, pos
, id
);
1710 build
->domain
= isl_set_insert_dims(build
->domain
,
1711 isl_dim_set
, pos
, 1);
1712 build
->generated
= isl_set_insert_dims(build
->generated
,
1713 isl_dim_set
, pos
, 1);
1714 build
->pending
= isl_set_insert_dims(build
->pending
,
1715 isl_dim_set
, pos
, 1);
1716 build
->strides
= isl_vec_insert_els(build
->strides
, pos
, 1);
1717 build
->strides
= isl_vec_set_element_si(build
->strides
, pos
, 1);
1718 ma_space
= isl_space_params(isl_multi_aff_get_space(build
->offsets
));
1719 ma_space
= isl_space_set_from_params(ma_space
);
1720 ma_space
= isl_space_add_dims(ma_space
, isl_dim_set
, 1);
1721 ma_space
= isl_space_map_from_set(ma_space
);
1722 ma
= isl_multi_aff_zero(isl_space_copy(ma_space
));
1723 build
->offsets
= isl_multi_aff_splice(build
->offsets
, pos
, pos
, ma
);
1724 ma
= isl_multi_aff_identity(ma_space
);
1725 build
->values
= isl_multi_aff_splice(build
->values
, pos
, pos
, ma
);
1727 build
->options
= options_insert_dim(build
->options
, space
, pos
);
1728 build
->internal2input
= isl_multi_aff_free(build
->internal2input
);
1730 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
1731 !build
->pending
|| !build
->values
||
1732 !build
->strides
|| !build
->offsets
|| !build
->options
)
1733 return isl_ast_build_free(build
);
1735 build
= node_insert_dim(build
, pos
);
1740 /* Scale down the current dimension by a factor of "m".
1741 * "umap" is an isl_union_map that implements the scaling down.
1742 * That is, it is of the form
1744 * { [.... i ....] -> [.... i' ....] : i = m i' }
1746 * This function is called right after the strides have been
1747 * detected, but before any constraints on the current dimension
1748 * have been included in build->domain.
1749 * We therefore only need to update stride, offset, the options and
1750 * the mapping from internal schedule space to the original schedule
1751 * space, if we are still keeping track of such a mapping.
1752 * The latter mapping is updated by plugging in
1753 * { [... i ...] -> [... m i ... ] }.
1755 __isl_give isl_ast_build
*isl_ast_build_scale_down(
1756 __isl_take isl_ast_build
*build
, __isl_take isl_val
*m
,
1757 __isl_take isl_union_map
*umap
)
1763 build
= isl_ast_build_cow(build
);
1764 if (!build
|| !umap
|| !m
)
1767 depth
= build
->depth
;
1769 if (build
->internal2input
) {
1774 space
= isl_multi_aff_get_space(build
->internal2input
);
1775 space
= isl_space_map_from_set(isl_space_domain(space
));
1776 ma
= isl_multi_aff_identity(space
);
1777 aff
= isl_multi_aff_get_aff(ma
, depth
);
1778 aff
= isl_aff_scale_val(aff
, isl_val_copy(m
));
1779 ma
= isl_multi_aff_set_aff(ma
, depth
, aff
);
1780 build
->internal2input
=
1781 isl_multi_aff_pullback_multi_aff(build
->internal2input
, ma
);
1782 if (!build
->internal2input
)
1786 v
= isl_vec_get_element_val(build
->strides
, depth
);
1787 v
= isl_val_div(v
, isl_val_copy(m
));
1788 build
->strides
= isl_vec_set_element_val(build
->strides
, depth
, v
);
1790 aff
= isl_multi_aff_get_aff(build
->offsets
, depth
);
1791 aff
= isl_aff_scale_down_val(aff
, m
);
1792 build
->offsets
= isl_multi_aff_set_aff(build
->offsets
, depth
, aff
);
1793 build
->options
= isl_union_map_apply_domain(build
->options
, umap
);
1794 if (!build
->strides
|| !build
->offsets
|| !build
->options
)
1795 return isl_ast_build_free(build
);
1800 isl_union_map_free(umap
);
1801 return isl_ast_build_free(build
);
1804 /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1805 * If an isl_id with such a name already appears among the parameters
1806 * in build->domain, then adjust the name to "c%d_%d".
1808 static __isl_give isl_id_list
*generate_names(isl_ctx
*ctx
, int n
, int first
,
1809 __isl_keep isl_ast_build
*build
)
1814 names
= isl_id_list_alloc(ctx
, n
);
1815 for (i
= 0; i
< n
; ++i
) {
1818 id
= generate_name(ctx
, first
+ i
, build
);
1819 names
= isl_id_list_add(names
, id
);
1825 /* Embed "options" into the given isl_ast_build space.
1827 * This function is called from within a nested call to
1828 * isl_ast_build_node_from_schedule_map.
1829 * "options" refers to the additional schedule,
1830 * while space refers to both the space of the outer isl_ast_build and
1831 * that of the additional schedule.
1832 * Specifically, space is of the form
1836 * while options lives in the space(s)
1844 * and compose this with options, to obtain the new options
1845 * living in the space(s)
1849 static __isl_give isl_union_map
*embed_options(
1850 __isl_take isl_union_map
*options
, __isl_take isl_space
*space
)
1854 map
= isl_map_universe(isl_space_unwrap(space
));
1855 map
= isl_map_range_map(map
);
1857 options
= isl_union_map_apply_range(
1858 isl_union_map_from_map(map
), options
);
1863 /* Update "build" for use in a (possibly nested) code generation. That is,
1864 * extend "build" from an AST build on some domain O to an AST build
1865 * on domain [O -> S], with S corresponding to "space".
1866 * If the original domain is a parameter domain, then the new domain is
1868 * "iterators" is a list of iterators for S, but the number of elements
1869 * may be smaller or greater than the number of set dimensions of S.
1870 * If "keep_iterators" is set, then any extra ids in build->iterators
1871 * are reused for S. Otherwise, these extra ids are dropped.
1873 * We first update build->outer_pos to the current depth.
1874 * This depth is zero in case this is the outermost code generation.
1876 * We then add additional ids such that the number of iterators is at least
1877 * equal to the dimension of the new build domain.
1879 * If the original domain is parametric, then we are constructing
1880 * an isl_ast_build for the outer code generation and we pass control
1881 * to isl_ast_build_init.
1883 * Otherwise, we adjust the fields of "build" to include "space".
1885 __isl_give isl_ast_build
*isl_ast_build_product(
1886 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
1891 isl_multi_aff
*embedding
;
1894 build
= isl_ast_build_cow(build
);
1898 build
->outer_pos
= build
->depth
;
1900 ctx
= isl_ast_build_get_ctx(build
);
1901 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
1902 dim
+= isl_space_dim(space
, isl_dim_set
);
1903 n_it
= isl_id_list_n_id(build
->iterators
);
1906 l
= generate_names(ctx
, dim
- n_it
, n_it
, build
);
1907 build
->iterators
= isl_id_list_concat(build
->iterators
, l
);
1910 if (isl_set_is_params(build
->domain
))
1911 return isl_ast_build_init(build
, space
);
1913 set
= isl_set_universe(isl_space_copy(space
));
1914 build
->domain
= isl_set_product(build
->domain
, isl_set_copy(set
));
1915 build
->pending
= isl_set_product(build
->pending
, isl_set_copy(set
));
1916 build
->generated
= isl_set_product(build
->generated
, set
);
1918 strides
= isl_vec_alloc(ctx
, isl_space_dim(space
, isl_dim_set
));
1919 strides
= isl_vec_set_si(strides
, 1);
1920 build
->strides
= isl_vec_concat(build
->strides
, strides
);
1922 space
= isl_space_map_from_set(space
);
1923 build
->offsets
= isl_multi_aff_align_params(build
->offsets
,
1924 isl_space_copy(space
));
1925 build
->offsets
= isl_multi_aff_product(build
->offsets
,
1926 isl_multi_aff_zero(isl_space_copy(space
)));
1927 build
->values
= isl_multi_aff_align_params(build
->values
,
1928 isl_space_copy(space
));
1929 embedding
= isl_multi_aff_identity(space
);
1930 build
->values
= isl_multi_aff_product(build
->values
,
1931 isl_multi_aff_copy(embedding
));
1932 if (build
->internal2input
) {
1933 build
->internal2input
=
1934 isl_multi_aff_product(build
->internal2input
, embedding
);
1935 build
->internal2input
=
1936 isl_multi_aff_flatten_range(build
->internal2input
);
1937 if (!build
->internal2input
)
1938 return isl_ast_build_free(build
);
1940 isl_multi_aff_free(embedding
);
1943 space
= isl_ast_build_get_space(build
, 1);
1944 build
->options
= embed_options(build
->options
, space
);
1946 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
1947 !build
->pending
|| !build
->values
||
1948 !build
->strides
|| !build
->offsets
|| !build
->options
)
1949 return isl_ast_build_free(build
);
1953 isl_ast_build_free(build
);
1954 isl_space_free(space
);
1958 /* Does "aff" only attain non-negative values over build->domain?
1959 * That is, does it not attain any negative values?
1961 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build
*build
,
1962 __isl_keep isl_aff
*aff
)
1970 aff
= isl_aff_copy(aff
);
1971 test
= isl_set_from_basic_set(isl_aff_neg_basic_set(aff
));
1972 test
= isl_set_intersect(test
, isl_set_copy(build
->domain
));
1973 empty
= isl_set_is_empty(test
);
1979 /* Does the dimension at (internal) position "pos" have a non-trivial stride?
1981 int isl_ast_build_has_stride(__isl_keep isl_ast_build
*build
, int pos
)
1989 v
= isl_vec_get_element_val(build
->strides
, pos
);
1992 has_stride
= !isl_val_is_one(v
);
1998 /* Given that the dimension at position "pos" takes on values
2002 * with a an integer, return s through *stride.
2004 __isl_give isl_val
*isl_ast_build_get_stride(__isl_keep isl_ast_build
*build
,
2010 return isl_vec_get_element_val(build
->strides
, pos
);
2013 /* Given that the dimension at position "pos" takes on values
2017 * with a an integer, return f.
2019 __isl_give isl_aff
*isl_ast_build_get_offset(
2020 __isl_keep isl_ast_build
*build
, int pos
)
2025 return isl_multi_aff_get_aff(build
->offsets
, pos
);
2028 /* Is the dimension at position "pos" known to attain only a single
2029 * value that, moreover, can be described by a single affine expression
2030 * in terms of the outer dimensions and parameters?
2032 * If not, then the corresponding affine expression in build->values
2033 * is set to be equal to the same input dimension.
2034 * Otherwise, it is set to the requested expression in terms of
2035 * outer dimensions and parameters.
2037 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build
*build
,
2046 aff
= isl_multi_aff_get_aff(build
->values
, pos
);
2047 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, pos
, 1);
2056 /* Plug in the known values (fixed affine expressions in terms of
2057 * parameters and outer loop iterators) of all loop iterators
2058 * in the domain of "umap".
2060 * We simply precompose "umap" with build->values.
2062 __isl_give isl_union_map
*isl_ast_build_substitute_values_union_map_domain(
2063 __isl_keep isl_ast_build
*build
, __isl_take isl_union_map
*umap
)
2065 isl_multi_aff
*values
;
2068 return isl_union_map_free(umap
);
2070 values
= isl_multi_aff_copy(build
->values
);
2071 umap
= isl_union_map_preimage_domain_multi_aff(umap
, values
);
2076 /* Is the current dimension known to attain only a single value?
2078 int isl_ast_build_has_value(__isl_keep isl_ast_build
*build
)
2083 return build
->value
!= NULL
;
2086 /* Simplify the basic set "bset" based on what we know about
2087 * the iterators of already generated loops.
2089 * "bset" is assumed to live in the (internal) schedule domain.
2091 __isl_give isl_basic_set
*isl_ast_build_compute_gist_basic_set(
2092 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
2097 bset
= isl_basic_set_preimage_multi_aff(bset
,
2098 isl_multi_aff_copy(build
->values
));
2099 bset
= isl_basic_set_gist(bset
,
2100 isl_set_simple_hull(isl_set_copy(build
->domain
)));
2104 isl_basic_set_free(bset
);
2108 /* Simplify the set "set" based on what we know about
2109 * the iterators of already generated loops.
2111 * "set" is assumed to live in the (internal) schedule domain.
2113 __isl_give isl_set
*isl_ast_build_compute_gist(
2114 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2119 if (!isl_set_is_params(set
))
2120 set
= isl_set_preimage_multi_aff(set
,
2121 isl_multi_aff_copy(build
->values
));
2122 set
= isl_set_gist(set
, isl_set_copy(build
->domain
));
2130 /* Include information about what we know about the iterators of
2131 * already generated loops to "set".
2133 * We currently only plug in the known affine values of outer loop
2135 * In principle we could also introduce equalities or even other
2136 * constraints implied by the intersection of "set" and build->domain.
2138 __isl_give isl_set
*isl_ast_build_specialize(__isl_keep isl_ast_build
*build
,
2139 __isl_take isl_set
*set
)
2142 return isl_set_free(set
);
2144 return isl_set_preimage_multi_aff(set
,
2145 isl_multi_aff_copy(build
->values
));
2148 /* Simplify the map "map" based on what we know about
2149 * the iterators of already generated loops.
2151 * The domain of "map" is assumed to live in the (internal) schedule domain.
2153 __isl_give isl_map
*isl_ast_build_compute_gist_map_domain(
2154 __isl_keep isl_ast_build
*build
, __isl_take isl_map
*map
)
2159 map
= isl_map_gist_domain(map
, isl_set_copy(build
->domain
));
2167 /* Simplify the affine expression "aff" based on what we know about
2168 * the iterators of already generated loops.
2170 * The domain of "aff" is assumed to live in the (internal) schedule domain.
2172 __isl_give isl_aff
*isl_ast_build_compute_gist_aff(
2173 __isl_keep isl_ast_build
*build
, __isl_take isl_aff
*aff
)
2178 aff
= isl_aff_gist(aff
, isl_set_copy(build
->domain
));
2186 /* Simplify the piecewise affine expression "aff" based on what we know about
2187 * the iterators of already generated loops.
2189 * The domain of "pa" is assumed to live in the (internal) schedule domain.
2191 __isl_give isl_pw_aff
*isl_ast_build_compute_gist_pw_aff(
2192 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
2197 if (!isl_set_is_params(build
->domain
))
2198 pa
= isl_pw_aff_pullback_multi_aff(pa
,
2199 isl_multi_aff_copy(build
->values
));
2200 pa
= isl_pw_aff_gist(pa
, isl_set_copy(build
->domain
));
2204 isl_pw_aff_free(pa
);
2208 /* Simplify the piecewise multi-affine expression "aff" based on what
2209 * we know about the iterators of already generated loops.
2211 * The domain of "pma" is assumed to live in the (internal) schedule domain.
2213 __isl_give isl_pw_multi_aff
*isl_ast_build_compute_gist_pw_multi_aff(
2214 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
2219 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
,
2220 isl_multi_aff_copy(build
->values
));
2221 pma
= isl_pw_multi_aff_gist(pma
, isl_set_copy(build
->domain
));
2225 isl_pw_multi_aff_free(pma
);
2229 /* Extract the schedule domain of the given type from build->options
2230 * at the current depth.
2232 * In particular, find the subset of build->options that is of
2233 * the following form
2235 * schedule_domain -> type[depth]
2237 * and return the corresponding domain, after eliminating inner dimensions
2238 * and divs that depend on the current dimension.
2240 * Note that the domain of build->options has been reformulated
2241 * in terms of the internal build space in embed_options,
2242 * but the position is still that within the current code generation.
2244 __isl_give isl_set
*isl_ast_build_get_option_domain(
2245 __isl_keep isl_ast_build
*build
, enum isl_ast_loop_type type
)
2256 name
= option_str
[type
];
2257 local_pos
= build
->depth
- build
->outer_pos
;
2259 space
= isl_ast_build_get_space(build
, 1);
2260 space
= isl_space_from_domain(space
);
2261 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
2262 space
= isl_space_set_tuple_name(space
, isl_dim_out
, name
);
2264 option
= isl_union_map_extract_map(build
->options
, space
);
2265 option
= isl_map_fix_si(option
, isl_dim_out
, 0, local_pos
);
2267 domain
= isl_map_domain(option
);
2268 domain
= isl_ast_build_eliminate(build
, domain
);
2273 /* How does the user want the current schedule dimension to be generated?
2274 * These choices have been extracted from the schedule node
2275 * in extract_loop_types and stored in build->loop_type.
2276 * They have been updated to reflect any dimension insertion in
2278 * Return isl_ast_domain_error on error.
2280 * If "isolated" is set, then we get the loop AST generation type
2281 * directly from the band node since node_insert_dim cannot have been
2282 * called on a band with the isolate option.
2284 enum isl_ast_loop_type
isl_ast_build_get_loop_type(
2285 __isl_keep isl_ast_build
*build
, int isolated
)
2291 return isl_ast_loop_error
;
2292 ctx
= isl_ast_build_get_ctx(build
);
2294 isl_die(ctx
, isl_error_internal
,
2295 "only works for schedule tree based AST generation",
2296 return isl_ast_loop_error
);
2298 local_pos
= build
->depth
- build
->outer_pos
;
2300 return build
->loop_type
[local_pos
];
2301 return isl_schedule_node_band_member_get_isolate_ast_loop_type(
2302 build
->node
, local_pos
);
2305 /* Extract the isolated set from the isolate option, if any,
2306 * and store in the build.
2307 * If there is no isolate option, then the isolated set is
2308 * set to the empty set.
2310 * The isolate option is of the form
2312 * isolate[[outer bands] -> current_band]
2314 * We flatten this set and then map it back to the internal
2317 * If we have already extracted the isolated set
2318 * or if internal2input is no longer set, then we do not
2319 * need to do anything. In the latter case, we know
2320 * that the current band cannot have any isolate option.
2322 __isl_give isl_ast_build
*isl_ast_build_extract_isolated(
2323 __isl_take isl_ast_build
*build
)
2325 isl_space
*space
, *space2
;
2326 isl_union_set
*options
;
2332 if (!build
->internal2input
)
2334 if (build
->isolated
)
2337 build
= isl_ast_build_cow(build
);
2341 options
= isl_schedule_node_band_get_ast_build_options(build
->node
);
2343 space
= isl_multi_aff_get_space(build
->internal2input
);
2344 space
= isl_space_range(space
);
2345 space2
= isl_set_get_space(build
->domain
);
2346 if (isl_space_is_wrapping(space2
))
2347 space2
= isl_space_range(isl_space_unwrap(space2
));
2348 n2
= isl_space_dim(space2
, isl_dim_set
);
2349 n
= isl_space_dim(space
, isl_dim_set
);
2351 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
2352 "total input space dimension cannot be smaller "
2353 "than dimension of innermost band",
2354 space
= isl_space_free(space
));
2355 space
= isl_space_drop_dims(space
, isl_dim_set
, n
- n2
, n2
);
2356 space
= isl_space_map_from_domain_and_range(space
, space2
);
2357 space
= isl_space_wrap(space
);
2358 space
= isl_space_set_tuple_name(space
, isl_dim_set
, "isolate");
2359 isolated
= isl_union_set_extract_set(options
, space
);
2360 isl_union_set_free(options
);
2362 isolated
= isl_set_flatten(isolated
);
2363 isolated
= isl_set_preimage_multi_aff(isolated
,
2364 isl_multi_aff_copy(build
->internal2input
));
2366 build
->isolated
= isolated
;
2367 if (!build
->isolated
)
2368 return isl_ast_build_free(build
);
2373 /* Does "build" have a non-empty isolated set?
2375 * The caller is assumed to have called isl_ast_build_extract_isolated first.
2377 int isl_ast_build_has_isolated(__isl_keep isl_ast_build
*build
)
2383 if (!build
->internal2input
)
2385 if (!build
->isolated
)
2386 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
2387 "isolated set not extracted yet", return -1);
2389 empty
= isl_set_plain_is_empty(build
->isolated
);
2390 return empty
< 0 ? -1 : !empty
;
2393 /* Return a copy of the isolated set of "build".
2395 * The caller is assume to have called isl_ast_build_has_isolated first,
2396 * with this function returning true.
2397 * In particular, this function should not be called if we are no
2398 * longer keeping track of internal2input (and there therefore could
2399 * not possibly be any isolated set).
2401 __isl_give isl_set
*isl_ast_build_get_isolated(__isl_keep isl_ast_build
*build
)
2405 if (!build
->internal2input
)
2406 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
2407 "build cannot have isolated set", return NULL
);
2409 return isl_set_copy(build
->isolated
);
2412 /* Extract the separation class mapping at the current depth.
2414 * In particular, find and return the subset of build->options that is of
2415 * the following form
2417 * schedule_domain -> separation_class[[depth] -> [class]]
2419 * The caller is expected to eliminate inner dimensions from the domain.
2421 * Note that the domain of build->options has been reformulated
2422 * in terms of the internal build space in embed_options,
2423 * but the position is still that within the current code generation.
2425 __isl_give isl_map
*isl_ast_build_get_separation_class(
2426 __isl_keep isl_ast_build
*build
)
2429 isl_space
*space_sep
, *space
;
2436 local_pos
= build
->depth
- build
->outer_pos
;
2437 ctx
= isl_ast_build_get_ctx(build
);
2438 space_sep
= isl_space_alloc(ctx
, 0, 1, 1);
2439 space_sep
= isl_space_wrap(space_sep
);
2440 space_sep
= isl_space_set_tuple_name(space_sep
, isl_dim_set
,
2441 "separation_class");
2442 space
= isl_ast_build_get_space(build
, 1);
2443 space_sep
= isl_space_align_params(space_sep
, isl_space_copy(space
));
2444 space
= isl_space_map_from_domain_and_range(space
, space_sep
);
2446 res
= isl_union_map_extract_map(build
->options
, space
);
2447 res
= isl_map_fix_si(res
, isl_dim_out
, 0, local_pos
);
2448 res
= isl_map_coalesce(res
);
2453 /* Eliminate dimensions inner to the current dimension.
2455 __isl_give isl_set
*isl_ast_build_eliminate_inner(
2456 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2462 return isl_set_free(set
);
2464 dim
= isl_set_dim(set
, isl_dim_set
);
2465 depth
= build
->depth
;
2466 set
= isl_set_detect_equalities(set
);
2467 set
= isl_set_eliminate(set
, isl_dim_set
, depth
+ 1, dim
- (depth
+ 1));
2472 /* Eliminate unknown divs and divs that depend on the current dimension.
2474 * Note that during the elimination of unknown divs, we may discover
2475 * an explicit representation of some other unknown divs, which may
2476 * depend on the current dimension. We therefore need to eliminate
2477 * unknown divs first.
2479 __isl_give isl_set
*isl_ast_build_eliminate_divs(
2480 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2485 return isl_set_free(set
);
2487 set
= isl_set_remove_unknown_divs(set
);
2488 depth
= build
->depth
;
2489 set
= isl_set_remove_divs_involving_dims(set
, isl_dim_set
, depth
, 1);
2494 /* Eliminate dimensions inner to the current dimension as well as
2495 * unknown divs and divs that depend on the current dimension.
2496 * The result then consists only of constraints that are independent
2497 * of the current dimension and upper and lower bounds on the current
2500 __isl_give isl_set
*isl_ast_build_eliminate(
2501 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*domain
)
2503 domain
= isl_ast_build_eliminate_inner(build
, domain
);
2504 domain
= isl_ast_build_eliminate_divs(build
, domain
);
2508 /* Replace build->single_valued by "sv".
2510 __isl_give isl_ast_build
*isl_ast_build_set_single_valued(
2511 __isl_take isl_ast_build
*build
, int sv
)
2515 if (build
->single_valued
== sv
)
2517 build
= isl_ast_build_cow(build
);
2520 build
->single_valued
= sv
;