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
15 #include <isl/constraint.h>
17 #include <isl/union_set.h>
18 #include <isl/union_map.h>
19 #include <isl_ast_build_private.h>
20 #include <isl_ast_private.h>
22 /* Construct a map that isolates the current dimension.
24 * Essentially, the current dimension of "set" is moved to the single output
25 * dimension in the result, with the current dimension in the domain replaced
26 * by an unconstrained variable.
28 __isl_give isl_map
*isl_ast_build_map_to_iterator(
29 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
33 map
= isl_map_from_domain(set
);
34 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
37 return isl_map_free(map
);
39 map
= isl_map_equate(map
, isl_dim_in
, build
->depth
, isl_dim_out
, 0);
40 map
= isl_map_eliminate(map
, isl_dim_in
, build
->depth
, 1);
45 /* Initialize the information derived during the AST generation to default
46 * values for a schedule domain in "space".
48 * We also check that the remaining fields are not NULL so that
49 * the calling functions don't have to perform this test.
51 static __isl_give isl_ast_build
*isl_ast_build_init_derived(
52 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
57 build
= isl_ast_build_cow(build
);
58 if (!build
|| !build
->domain
)
61 ctx
= isl_ast_build_get_ctx(build
);
62 strides
= isl_vec_alloc(ctx
, isl_space_dim(space
, isl_dim_set
));
63 strides
= isl_vec_set_si(strides
, 1);
65 isl_vec_free(build
->strides
);
66 build
->strides
= strides
;
68 space
= isl_space_map_from_set(space
);
69 isl_multi_aff_free(build
->offsets
);
70 build
->offsets
= isl_multi_aff_zero(isl_space_copy(space
));
71 isl_multi_aff_free(build
->values
);
72 build
->values
= isl_multi_aff_identity(isl_space_copy(space
));
73 isl_multi_aff_free(build
->internal2input
);
74 build
->internal2input
= isl_multi_aff_identity(space
);
76 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
77 !build
->pending
|| !build
->values
|| !build
->internal2input
||
78 !build
->strides
|| !build
->offsets
|| !build
->options
)
79 return isl_ast_build_free(build
);
83 isl_space_free(space
);
84 return isl_ast_build_free(build
);
87 /* Return an isl_id called "c%d", with "%d" set to "i".
88 * If an isl_id with such a name already appears among the parameters
89 * in build->domain, then adjust the name to "c%d_%d".
91 static __isl_give isl_id
*generate_name(isl_ctx
*ctx
, int i
,
92 __isl_keep isl_ast_build
*build
)
96 isl_set
*dom
= build
->domain
;
98 snprintf(name
, sizeof(name
), "c%d", i
);
100 while (isl_set_find_dim_by_name(dom
, isl_dim_param
, name
) >= 0)
101 snprintf(name
, sizeof(name
), "c%d_%d", i
, j
++);
102 return isl_id_alloc(ctx
, name
, NULL
);
105 /* Create an isl_ast_build with "set" as domain.
107 * The input set is usually a parameter domain, but we currently allow it to
108 * be any kind of set. We set the domain of the returned isl_ast_build
109 * to "set" and initialize all the other fields to default values.
111 __isl_give isl_ast_build
*isl_ast_build_from_context(__isl_take isl_set
*set
)
116 isl_ast_build
*build
;
118 set
= isl_set_compute_divs(set
);
122 ctx
= isl_set_get_ctx(set
);
124 build
= isl_calloc_type(ctx
, isl_ast_build
);
130 build
->generated
= isl_set_copy(build
->domain
);
131 build
->pending
= isl_set_universe(isl_set_get_space(build
->domain
));
132 build
->options
= isl_union_map_empty(isl_space_params_alloc(ctx
, 0));
133 n
= isl_set_dim(set
, isl_dim_set
);
135 build
->iterators
= isl_id_list_alloc(ctx
, n
);
136 for (i
= 0; i
< n
; ++i
) {
138 if (isl_set_has_dim_id(set
, isl_dim_set
, i
))
139 id
= isl_set_get_dim_id(set
, isl_dim_set
, i
);
141 id
= generate_name(ctx
, i
, build
);
142 build
->iterators
= isl_id_list_add(build
->iterators
, id
);
144 space
= isl_set_get_space(set
);
145 if (isl_space_is_params(space
))
146 space
= isl_space_set_from_params(space
);
148 return isl_ast_build_init_derived(build
, space
);
154 /* Create an isl_ast_build with a universe (parametric) context.
156 __isl_give isl_ast_build
*isl_ast_build_alloc(isl_ctx
*ctx
)
161 space
= isl_space_params_alloc(ctx
, 0);
162 context
= isl_set_universe(space
);
164 return isl_ast_build_from_context(context
);
167 __isl_give isl_ast_build
*isl_ast_build_copy(__isl_keep isl_ast_build
*build
)
176 __isl_give isl_ast_build
*isl_ast_build_dup(__isl_keep isl_ast_build
*build
)
184 ctx
= isl_ast_build_get_ctx(build
);
185 dup
= isl_calloc_type(ctx
, isl_ast_build
);
190 dup
->outer_pos
= build
->outer_pos
;
191 dup
->depth
= build
->depth
;
192 dup
->iterators
= isl_id_list_copy(build
->iterators
);
193 dup
->domain
= isl_set_copy(build
->domain
);
194 dup
->generated
= isl_set_copy(build
->generated
);
195 dup
->pending
= isl_set_copy(build
->pending
);
196 dup
->values
= isl_multi_aff_copy(build
->values
);
197 dup
->internal2input
= isl_multi_aff_copy(build
->internal2input
);
198 dup
->value
= isl_pw_aff_copy(build
->value
);
199 dup
->strides
= isl_vec_copy(build
->strides
);
200 dup
->offsets
= isl_multi_aff_copy(build
->offsets
);
201 dup
->executed
= isl_union_map_copy(build
->executed
);
202 dup
->single_valued
= build
->single_valued
;
203 dup
->options
= isl_union_map_copy(build
->options
);
204 dup
->at_each_domain
= build
->at_each_domain
;
205 dup
->at_each_domain_user
= build
->at_each_domain_user
;
206 dup
->before_each_for
= build
->before_each_for
;
207 dup
->before_each_for_user
= build
->before_each_for_user
;
208 dup
->after_each_for
= build
->after_each_for
;
209 dup
->after_each_for_user
= build
->after_each_for_user
;
210 dup
->before_each_mark
= build
->before_each_mark
;
211 dup
->before_each_mark_user
= build
->before_each_mark_user
;
212 dup
->after_each_mark
= build
->after_each_mark
;
213 dup
->after_each_mark_user
= build
->after_each_mark_user
;
214 dup
->create_leaf
= build
->create_leaf
;
215 dup
->create_leaf_user
= build
->create_leaf_user
;
216 dup
->node
= isl_schedule_node_copy(build
->node
);
217 if (build
->loop_type
) {
221 dup
->loop_type
= isl_alloc_array(ctx
,
222 enum isl_ast_loop_type
, dup
->n
);
223 if (dup
->n
&& !dup
->loop_type
)
224 return isl_ast_build_free(dup
);
225 for (i
= 0; i
< dup
->n
; ++i
)
226 dup
->loop_type
[i
] = build
->loop_type
[i
];
229 if (!dup
->iterators
|| !dup
->domain
|| !dup
->generated
||
230 !dup
->pending
|| !dup
->values
||
231 !dup
->strides
|| !dup
->offsets
|| !dup
->options
||
232 (build
->internal2input
&& !dup
->internal2input
) ||
233 (build
->executed
&& !dup
->executed
) ||
234 (build
->value
&& !dup
->value
) ||
235 (build
->node
&& !dup
->node
))
236 return isl_ast_build_free(dup
);
241 /* Align the parameters of "build" to those of "model", introducing
242 * additional parameters if needed.
244 __isl_give isl_ast_build
*isl_ast_build_align_params(
245 __isl_take isl_ast_build
*build
, __isl_take isl_space
*model
)
247 build
= isl_ast_build_cow(build
);
251 build
->domain
= isl_set_align_params(build
->domain
,
252 isl_space_copy(model
));
253 build
->generated
= isl_set_align_params(build
->generated
,
254 isl_space_copy(model
));
255 build
->pending
= isl_set_align_params(build
->pending
,
256 isl_space_copy(model
));
257 build
->values
= isl_multi_aff_align_params(build
->values
,
258 isl_space_copy(model
));
259 build
->offsets
= isl_multi_aff_align_params(build
->offsets
,
260 isl_space_copy(model
));
261 build
->options
= isl_union_map_align_params(build
->options
,
262 isl_space_copy(model
));
263 if (build
->internal2input
) {
264 build
->internal2input
=
265 isl_multi_aff_align_params(build
->internal2input
,
267 if (!build
->internal2input
)
268 return isl_ast_build_free(build
);
270 isl_space_free(model
);
273 if (!build
->domain
|| !build
->values
|| !build
->offsets
||
275 return isl_ast_build_free(build
);
279 isl_space_free(model
);
283 __isl_give isl_ast_build
*isl_ast_build_cow(__isl_take isl_ast_build
*build
)
291 return isl_ast_build_dup(build
);
294 __isl_null isl_ast_build
*isl_ast_build_free(
295 __isl_take isl_ast_build
*build
)
300 if (--build
->ref
> 0)
303 isl_id_list_free(build
->iterators
);
304 isl_set_free(build
->domain
);
305 isl_set_free(build
->generated
);
306 isl_set_free(build
->pending
);
307 isl_multi_aff_free(build
->values
);
308 isl_multi_aff_free(build
->internal2input
);
309 isl_pw_aff_free(build
->value
);
310 isl_vec_free(build
->strides
);
311 isl_multi_aff_free(build
->offsets
);
312 isl_multi_aff_free(build
->schedule_map
);
313 isl_union_map_free(build
->executed
);
314 isl_union_map_free(build
->options
);
315 isl_schedule_node_free(build
->node
);
316 free(build
->loop_type
);
317 isl_set_free(build
->isolated
);
324 isl_ctx
*isl_ast_build_get_ctx(__isl_keep isl_ast_build
*build
)
326 return build
? isl_set_get_ctx(build
->domain
) : NULL
;
329 /* Replace build->options by "options".
331 __isl_give isl_ast_build
*isl_ast_build_set_options(
332 __isl_take isl_ast_build
*build
, __isl_take isl_union_map
*options
)
334 build
= isl_ast_build_cow(build
);
336 if (!build
|| !options
)
339 isl_union_map_free(build
->options
);
340 build
->options
= options
;
344 isl_union_map_free(options
);
345 return isl_ast_build_free(build
);
348 /* Set the iterators for the next code generation.
350 * If we still have some iterators left from the previous code generation
351 * (if any) or if iterators have already been set by a previous
352 * call to this function, then we remove them first.
354 __isl_give isl_ast_build
*isl_ast_build_set_iterators(
355 __isl_take isl_ast_build
*build
, __isl_take isl_id_list
*iterators
)
359 build
= isl_ast_build_cow(build
);
363 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
364 n_it
= isl_id_list_n_id(build
->iterators
);
366 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
367 "isl_ast_build in inconsistent state", goto error
);
369 build
->iterators
= isl_id_list_drop(build
->iterators
,
371 build
->iterators
= isl_id_list_concat(build
->iterators
, iterators
);
372 if (!build
->iterators
)
373 return isl_ast_build_free(build
);
377 isl_id_list_free(iterators
);
378 return isl_ast_build_free(build
);
381 /* Set the "at_each_domain" callback of "build" to "fn".
383 __isl_give isl_ast_build
*isl_ast_build_set_at_each_domain(
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
->at_each_domain
= fn
;
394 build
->at_each_domain_user
= user
;
399 /* Set the "before_each_for" callback of "build" to "fn".
401 __isl_give isl_ast_build
*isl_ast_build_set_before_each_for(
402 __isl_take isl_ast_build
*build
,
403 __isl_give isl_id
*(*fn
)(__isl_keep isl_ast_build
*build
,
404 void *user
), void *user
)
406 build
= isl_ast_build_cow(build
);
411 build
->before_each_for
= fn
;
412 build
->before_each_for_user
= user
;
417 /* Set the "after_each_for" callback of "build" to "fn".
419 __isl_give isl_ast_build
*isl_ast_build_set_after_each_for(
420 __isl_take isl_ast_build
*build
,
421 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_node
*node
,
422 __isl_keep isl_ast_build
*build
, void *user
), void *user
)
424 build
= isl_ast_build_cow(build
);
429 build
->after_each_for
= fn
;
430 build
->after_each_for_user
= user
;
435 /* Set the "before_each_mark" callback of "build" to "fn".
437 __isl_give isl_ast_build
*isl_ast_build_set_before_each_mark(
438 __isl_take isl_ast_build
*build
,
439 isl_stat (*fn
)(__isl_keep isl_id
*mark
, __isl_keep isl_ast_build
*build
,
440 void *user
), void *user
)
442 build
= isl_ast_build_cow(build
);
447 build
->before_each_mark
= fn
;
448 build
->before_each_mark_user
= user
;
453 /* Set the "after_each_mark" callback of "build" to "fn".
455 __isl_give isl_ast_build
*isl_ast_build_set_after_each_mark(
456 __isl_take isl_ast_build
*build
,
457 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_node
*node
,
458 __isl_keep isl_ast_build
*build
, void *user
), void *user
)
460 build
= isl_ast_build_cow(build
);
465 build
->after_each_mark
= fn
;
466 build
->after_each_mark_user
= user
;
471 /* Set the "create_leaf" callback of "build" to "fn".
473 __isl_give isl_ast_build
*isl_ast_build_set_create_leaf(
474 __isl_take isl_ast_build
*build
,
475 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_build
*build
,
476 void *user
), void *user
)
478 build
= isl_ast_build_cow(build
);
483 build
->create_leaf
= fn
;
484 build
->create_leaf_user
= user
;
489 /* Clear all information that is specific to this code generation
490 * and that is (probably) not meaningful to any nested code generation.
492 __isl_give isl_ast_build
*isl_ast_build_clear_local_info(
493 __isl_take isl_ast_build
*build
)
497 build
= isl_ast_build_cow(build
);
501 space
= isl_union_map_get_space(build
->options
);
502 isl_union_map_free(build
->options
);
503 build
->options
= isl_union_map_empty(space
);
505 build
->at_each_domain
= NULL
;
506 build
->at_each_domain_user
= NULL
;
507 build
->before_each_for
= NULL
;
508 build
->before_each_for_user
= NULL
;
509 build
->after_each_for
= NULL
;
510 build
->after_each_for_user
= NULL
;
511 build
->before_each_mark
= NULL
;
512 build
->before_each_mark_user
= NULL
;
513 build
->after_each_mark
= NULL
;
514 build
->after_each_mark_user
= NULL
;
515 build
->create_leaf
= NULL
;
516 build
->create_leaf_user
= NULL
;
519 return isl_ast_build_free(build
);
524 /* Have any loops been eliminated?
525 * That is, do any of the original schedule dimensions have a fixed
526 * value that has been substituted?
528 static int any_eliminated(isl_ast_build
*build
)
532 for (i
= 0; i
< build
->depth
; ++i
)
533 if (isl_ast_build_has_affine_value(build
, i
))
539 /* Clear build->schedule_map.
540 * This function should be called whenever anything that might affect
541 * the result of isl_ast_build_get_schedule_map_multi_aff changes.
542 * In particular, it should be called when the depth is changed or
543 * when an iterator is determined to have a fixed value.
545 static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build
*build
)
549 isl_multi_aff_free(build
->schedule_map
);
550 build
->schedule_map
= NULL
;
553 /* Do we need a (non-trivial) schedule map?
554 * That is, is the internal schedule space different from
555 * the external schedule space?
557 * The internal and external schedule spaces are only the same
558 * if code has been generated for the entire schedule and if none
559 * of the loops have been eliminated.
561 __isl_give
int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build
*build
)
568 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
569 return build
->depth
!= dim
|| any_eliminated(build
);
572 /* Return a mapping from the internal schedule space to the external
573 * schedule space in the form of an isl_multi_aff.
574 * The internal schedule space originally corresponds to that of the
575 * input schedule. This may change during the code generation if
576 * if isl_ast_build_insert_dim is ever called.
577 * The external schedule space corresponds to the
578 * loops that have been generated.
580 * Currently, the only difference between the internal schedule domain
581 * and the external schedule domain is that some dimensions are projected
582 * out in the external schedule domain. In particular, the dimensions
583 * for which no code has been generated yet and the dimensions that correspond
584 * to eliminated loops.
586 * We cache a copy of the schedule_map in build->schedule_map.
587 * The cache is cleared through isl_ast_build_reset_schedule_map
588 * whenever anything changes that might affect the result of this function.
590 __isl_give isl_multi_aff
*isl_ast_build_get_schedule_map_multi_aff(
591 __isl_keep isl_ast_build
*build
)
598 if (build
->schedule_map
)
599 return isl_multi_aff_copy(build
->schedule_map
);
601 space
= isl_ast_build_get_space(build
, 1);
602 space
= isl_space_map_from_set(space
);
603 ma
= isl_multi_aff_identity(space
);
604 if (isl_ast_build_need_schedule_map(build
)) {
606 int dim
= isl_set_dim(build
->domain
, isl_dim_set
);
607 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
,
608 build
->depth
, dim
- build
->depth
);
609 for (i
= build
->depth
- 1; i
>= 0; --i
)
610 if (isl_ast_build_has_affine_value(build
, i
))
611 ma
= isl_multi_aff_drop_dims(ma
,
615 build
->schedule_map
= ma
;
616 return isl_multi_aff_copy(build
->schedule_map
);
619 /* Return a mapping from the internal schedule space to the external
620 * schedule space in the form of an isl_map.
622 __isl_give isl_map
*isl_ast_build_get_schedule_map(
623 __isl_keep isl_ast_build
*build
)
627 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
628 return isl_map_from_multi_aff(ma
);
631 /* Return the position of the dimension in build->domain for which
632 * an AST node is currently being generated.
634 int isl_ast_build_get_depth(__isl_keep isl_ast_build
*build
)
636 return build
? build
->depth
: -1;
639 /* Prepare for generating code for the next level.
640 * In particular, increase the depth and reset any information
641 * that is local to the current depth.
643 __isl_give isl_ast_build
*isl_ast_build_increase_depth(
644 __isl_take isl_ast_build
*build
)
646 build
= isl_ast_build_cow(build
);
650 isl_ast_build_reset_schedule_map(build
);
651 build
->value
= isl_pw_aff_free(build
->value
);
655 void isl_ast_build_dump(__isl_keep isl_ast_build
*build
)
660 fprintf(stderr
, "domain: ");
661 isl_set_dump(build
->domain
);
662 fprintf(stderr
, "generated: ");
663 isl_set_dump(build
->generated
);
664 fprintf(stderr
, "pending: ");
665 isl_set_dump(build
->pending
);
666 fprintf(stderr
, "iterators: ");
667 isl_id_list_dump(build
->iterators
);
668 fprintf(stderr
, "values: ");
669 isl_multi_aff_dump(build
->values
);
671 fprintf(stderr
, "value: ");
672 isl_pw_aff_dump(build
->value
);
674 fprintf(stderr
, "strides: ");
675 isl_vec_dump(build
->strides
);
676 fprintf(stderr
, "offsets: ");
677 isl_multi_aff_dump(build
->offsets
);
678 fprintf(stderr
, "internal2input: ");
679 isl_multi_aff_dump(build
->internal2input
);
682 /* Initialize "build" for AST construction in schedule space "space"
683 * in the case that build->domain is a parameter set.
685 * build->iterators is assumed to have been updated already.
687 static __isl_give isl_ast_build
*isl_ast_build_init(
688 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
692 build
= isl_ast_build_cow(build
);
696 set
= isl_set_universe(isl_space_copy(space
));
697 build
->domain
= isl_set_intersect_params(isl_set_copy(set
),
699 build
->pending
= isl_set_intersect_params(isl_set_copy(set
),
701 build
->generated
= isl_set_intersect_params(set
, build
->generated
);
703 return isl_ast_build_init_derived(build
, space
);
705 isl_ast_build_free(build
);
706 isl_space_free(space
);
710 /* Assign "aff" to *user and return -1, effectively extracting
711 * the first (and presumably only) affine expression in the isl_pw_aff
712 * on which this function is used.
714 static isl_stat
extract_single_piece(__isl_take isl_set
*set
,
715 __isl_take isl_aff
*aff
, void *user
)
722 return isl_stat_error
;
725 /* Intersect "set" with the stride constraint of "build", if any.
727 static __isl_give isl_set
*intersect_stride_constraint(__isl_take isl_set
*set
,
728 __isl_keep isl_ast_build
*build
)
733 return isl_set_free(set
);
734 if (!isl_ast_build_has_stride(build
, build
->depth
))
737 stride
= isl_ast_build_get_stride_constraint(build
);
738 return isl_set_intersect(set
, stride
);
741 /* Check if the given bounds on the current dimension (together with
742 * the stride constraint, if any) imply that
743 * this current dimension attains only a single value (in terms of
744 * parameters and outer dimensions).
745 * If so, we record it in build->value.
746 * If, moreover, this value can be represented as a single affine expression,
747 * then we also update build->values, effectively marking the current
748 * dimension as "eliminated".
750 * When computing the gist of the fixed value that can be represented
751 * as a single affine expression, it is important to only take into
752 * account the domain constraints in the original AST build and
753 * not the domain of the affine expression itself.
754 * Otherwise, a [i/3] is changed into a i/3 because we know that i
755 * is a multiple of 3, but then we end up not expressing anywhere
756 * in the context that i is a multiple of 3.
758 static __isl_give isl_ast_build
*update_values(
759 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
762 isl_pw_multi_aff
*pma
;
767 set
= isl_set_from_basic_set(bounds
);
768 set
= isl_set_intersect(set
, isl_set_copy(build
->domain
));
769 set
= intersect_stride_constraint(set
, build
);
770 it_map
= isl_ast_build_map_to_iterator(build
, set
);
772 sv
= isl_map_is_single_valued(it_map
);
774 build
= isl_ast_build_free(build
);
776 isl_map_free(it_map
);
780 pma
= isl_pw_multi_aff_from_map(it_map
);
781 build
->value
= isl_pw_multi_aff_get_pw_aff(pma
, 0);
782 build
->value
= isl_ast_build_compute_gist_pw_aff(build
, build
->value
);
783 build
->value
= isl_pw_aff_coalesce(build
->value
);
784 isl_pw_multi_aff_free(pma
);
787 return isl_ast_build_free(build
);
789 if (isl_pw_aff_n_piece(build
->value
) != 1)
792 isl_pw_aff_foreach_piece(build
->value
, &extract_single_piece
, &aff
);
794 build
->values
= isl_multi_aff_set_aff(build
->values
, build
->depth
, aff
);
796 return isl_ast_build_free(build
);
797 isl_ast_build_reset_schedule_map(build
);
801 /* Update the AST build based on the given loop bounds for
802 * the current dimension and the stride information available in the build.
804 * We first make sure that the bounds do not refer to any iterators
805 * that have already been eliminated.
806 * Then, we check if the bounds imply that the current iterator
808 * If they do and if this fixed value can be expressed as a single
809 * affine expression, we eliminate the iterators from the bounds.
810 * Note that we cannot simply plug in this single value using
811 * isl_basic_set_preimage_multi_aff as the single value may only
812 * be defined on a subset of the domain. Plugging in the value
813 * would restrict the build domain to this subset, while this
814 * restriction may not be reflected in the generated code.
815 * Finally, we intersect build->domain with the updated bounds.
816 * We also add the stride constraint unless we have been able
817 * to find a fixed value expressed as a single affine expression.
819 * Note that the check for a fixed value in update_values requires
820 * us to intersect the bounds with the current build domain.
821 * When we intersect build->domain with the updated bounds in
822 * the final step, we make sure that these updated bounds have
823 * not been intersected with the old build->domain.
824 * Otherwise, we would indirectly intersect the build domain with itself,
825 * which can lead to inefficiencies, in particular if the build domain
826 * contains any unknown divs.
828 * The pending and generated sets are not updated by this function to
829 * match the updated domain.
830 * The caller still needs to call isl_ast_build_set_pending_generated.
832 __isl_give isl_ast_build
*isl_ast_build_set_loop_bounds(
833 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
837 build
= isl_ast_build_cow(build
);
841 build
= update_values(build
, isl_basic_set_copy(bounds
));
844 set
= isl_set_from_basic_set(bounds
);
845 if (isl_ast_build_has_affine_value(build
, build
->depth
)) {
846 set
= isl_set_eliminate(set
, isl_dim_set
, build
->depth
, 1);
847 set
= isl_set_compute_divs(set
);
848 build
->pending
= isl_set_intersect(build
->pending
,
850 build
->domain
= isl_set_intersect(build
->domain
, set
);
852 build
->domain
= isl_set_intersect(build
->domain
, set
);
853 build
= isl_ast_build_include_stride(build
);
858 if (!build
->domain
|| !build
->pending
|| !build
->generated
)
859 return isl_ast_build_free(build
);
863 isl_ast_build_free(build
);
864 isl_basic_set_free(bounds
);
868 /* Update the pending and generated sets of "build" according to "bounds".
869 * If the build has an affine value at the current depth,
870 * then isl_ast_build_set_loop_bounds has already set the pending set.
871 * Otherwise, do it here.
873 __isl_give isl_ast_build
*isl_ast_build_set_pending_generated(
874 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
876 isl_basic_set
*generated
, *pending
;
881 if (isl_ast_build_has_affine_value(build
, build
->depth
)) {
882 isl_basic_set_free(bounds
);
886 build
= isl_ast_build_cow(build
);
890 pending
= isl_basic_set_copy(bounds
);
891 pending
= isl_basic_set_drop_constraints_involving_dims(pending
,
892 isl_dim_set
, build
->depth
, 1);
893 build
->pending
= isl_set_intersect(build
->pending
,
894 isl_set_from_basic_set(pending
));
896 generated
= isl_basic_set_drop_constraints_not_involving_dims(
897 generated
, isl_dim_set
, build
->depth
, 1);
898 build
->generated
= isl_set_intersect(build
->generated
,
899 isl_set_from_basic_set(generated
));
901 if (!build
->pending
|| !build
->generated
)
902 return isl_ast_build_free(build
);
906 isl_ast_build_free(build
);
907 isl_basic_set_free(bounds
);
911 /* Intersect build->domain with "set", where "set" is specified
912 * in terms of the internal schedule domain.
914 static __isl_give isl_ast_build
*isl_ast_build_restrict_internal(
915 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
917 build
= isl_ast_build_cow(build
);
921 set
= isl_set_compute_divs(set
);
922 build
->domain
= isl_set_intersect(build
->domain
, set
);
923 build
->domain
= isl_set_coalesce(build
->domain
);
926 return isl_ast_build_free(build
);
930 isl_ast_build_free(build
);
935 /* Intersect build->generated and build->domain with "set",
936 * where "set" is specified in terms of the internal schedule domain.
938 __isl_give isl_ast_build
*isl_ast_build_restrict_generated(
939 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
941 set
= isl_set_compute_divs(set
);
942 build
= isl_ast_build_restrict_internal(build
, isl_set_copy(set
));
943 build
= isl_ast_build_cow(build
);
947 build
->generated
= isl_set_intersect(build
->generated
, set
);
948 build
->generated
= isl_set_coalesce(build
->generated
);
950 if (!build
->generated
)
951 return isl_ast_build_free(build
);
955 isl_ast_build_free(build
);
960 /* Replace the set of pending constraints by "guard", which is then
961 * no longer considered as pending.
962 * That is, add "guard" to the generated constraints and clear all pending
963 * constraints, making the domain equal to the generated constraints.
965 __isl_give isl_ast_build
*isl_ast_build_replace_pending_by_guard(
966 __isl_take isl_ast_build
*build
, __isl_take isl_set
*guard
)
968 build
= isl_ast_build_restrict_generated(build
, guard
);
969 build
= isl_ast_build_cow(build
);
973 isl_set_free(build
->domain
);
974 build
->domain
= isl_set_copy(build
->generated
);
975 isl_set_free(build
->pending
);
976 build
->pending
= isl_set_universe(isl_set_get_space(build
->domain
));
979 return isl_ast_build_free(build
);
984 /* Intersect build->pending and build->domain with "set",
985 * where "set" is specified in terms of the internal schedule domain.
987 __isl_give isl_ast_build
*isl_ast_build_restrict_pending(
988 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
990 set
= isl_set_compute_divs(set
);
991 build
= isl_ast_build_restrict_internal(build
, isl_set_copy(set
));
992 build
= isl_ast_build_cow(build
);
996 build
->pending
= isl_set_intersect(build
->pending
, set
);
997 build
->pending
= isl_set_coalesce(build
->pending
);
1000 return isl_ast_build_free(build
);
1004 isl_ast_build_free(build
);
1009 /* Intersect build->domain with "set", where "set" is specified
1010 * in terms of the external schedule domain.
1012 __isl_give isl_ast_build
*isl_ast_build_restrict(
1013 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
1015 if (isl_set_is_params(set
))
1016 return isl_ast_build_restrict_generated(build
, set
);
1018 if (isl_ast_build_need_schedule_map(build
)) {
1020 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
1021 set
= isl_set_preimage_multi_aff(set
, ma
);
1023 return isl_ast_build_restrict_generated(build
, set
);
1026 /* Replace build->executed by "executed".
1028 __isl_give isl_ast_build
*isl_ast_build_set_executed(
1029 __isl_take isl_ast_build
*build
, __isl_take isl_union_map
*executed
)
1031 build
= isl_ast_build_cow(build
);
1035 isl_union_map_free(build
->executed
);
1036 build
->executed
= executed
;
1040 isl_ast_build_free(build
);
1041 isl_union_map_free(executed
);
1045 /* Does "build" point to a band node?
1046 * That is, are we currently handling a band node inside a schedule tree?
1048 int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build
*build
)
1052 return build
->node
!= NULL
;
1055 /* Return a copy of the band node that "build" refers to.
1057 __isl_give isl_schedule_node
*isl_ast_build_get_schedule_node(
1058 __isl_keep isl_ast_build
*build
)
1062 return isl_schedule_node_copy(build
->node
);
1065 /* Extract the loop AST generation types for the members of build->node
1066 * and store them in build->loop_type.
1068 static __isl_give isl_ast_build
*extract_loop_types(
1069 __isl_take isl_ast_build
*build
)
1073 isl_schedule_node
*node
;
1077 ctx
= isl_ast_build_get_ctx(build
);
1079 isl_die(ctx
, isl_error_internal
, "missing AST node",
1080 return isl_ast_build_free(build
));
1082 free(build
->loop_type
);
1083 build
->n
= isl_schedule_node_band_n_member(build
->node
);
1084 build
->loop_type
= isl_alloc_array(ctx
,
1085 enum isl_ast_loop_type
, build
->n
);
1086 if (build
->n
&& !build
->loop_type
)
1087 return isl_ast_build_free(build
);
1089 for (i
= 0; i
< build
->n
; ++i
)
1090 build
->loop_type
[i
] =
1091 isl_schedule_node_band_member_get_ast_loop_type(node
, i
);
1096 /* Replace the band node that "build" refers to by "node" and
1097 * extract the corresponding loop AST generation types.
1099 __isl_give isl_ast_build
*isl_ast_build_set_schedule_node(
1100 __isl_take isl_ast_build
*build
,
1101 __isl_take isl_schedule_node
*node
)
1103 build
= isl_ast_build_cow(build
);
1104 if (!build
|| !node
)
1107 isl_schedule_node_free(build
->node
);
1110 build
= extract_loop_types(build
);
1114 isl_ast_build_free(build
);
1115 isl_schedule_node_free(node
);
1119 /* Remove any reference to a band node from "build".
1121 __isl_give isl_ast_build
*isl_ast_build_reset_schedule_node(
1122 __isl_take isl_ast_build
*build
)
1124 build
= isl_ast_build_cow(build
);
1128 isl_schedule_node_free(build
->node
);
1134 /* Return a copy of the current schedule domain.
1136 __isl_give isl_set
*isl_ast_build_get_domain(__isl_keep isl_ast_build
*build
)
1138 return build
? isl_set_copy(build
->domain
) : NULL
;
1141 /* Return a copy of the set of pending constraints.
1143 __isl_give isl_set
*isl_ast_build_get_pending(
1144 __isl_keep isl_ast_build
*build
)
1146 return build
? isl_set_copy(build
->pending
) : NULL
;
1149 /* Return a copy of the set of generated constraints.
1151 __isl_give isl_set
*isl_ast_build_get_generated(
1152 __isl_keep isl_ast_build
*build
)
1154 return build
? isl_set_copy(build
->generated
) : NULL
;
1157 /* Return a copy of the map from the internal schedule domain
1158 * to the original input schedule domain.
1160 __isl_give isl_multi_aff
*isl_ast_build_get_internal2input(
1161 __isl_keep isl_ast_build
*build
)
1163 return build
? isl_multi_aff_copy(build
->internal2input
) : NULL
;
1166 /* Return the number of variables of the given type
1167 * in the (internal) schedule space.
1169 unsigned isl_ast_build_dim(__isl_keep isl_ast_build
*build
,
1170 enum isl_dim_type type
)
1174 return isl_set_dim(build
->domain
, type
);
1177 /* Return the (schedule) space of "build".
1179 * If "internal" is set, then this space is the space of the internal
1180 * representation of the entire schedule, including those parts for
1181 * which no code has been generated yet.
1183 * If "internal" is not set, then this space is the external representation
1184 * of the loops generated so far.
1186 __isl_give isl_space
*isl_ast_build_get_space(__isl_keep isl_ast_build
*build
,
1196 space
= isl_set_get_space(build
->domain
);
1200 if (!isl_ast_build_need_schedule_map(build
))
1203 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
1204 space
= isl_space_drop_dims(space
, isl_dim_set
,
1205 build
->depth
, dim
- build
->depth
);
1206 for (i
= build
->depth
- 1; i
>= 0; --i
)
1207 if (isl_ast_build_has_affine_value(build
, i
))
1208 space
= isl_space_drop_dims(space
, isl_dim_set
, i
, 1);
1213 /* Return the external representation of the schedule space of "build",
1214 * i.e., a space with a dimension for each loop generated so far,
1215 * with the names of the dimensions set to the loop iterators.
1217 __isl_give isl_space
*isl_ast_build_get_schedule_space(
1218 __isl_keep isl_ast_build
*build
)
1226 space
= isl_ast_build_get_space(build
, 0);
1229 for (i
= 0; i
< build
->depth
; ++i
) {
1232 if (isl_ast_build_has_affine_value(build
, i
)) {
1237 id
= isl_ast_build_get_iterator_id(build
, i
);
1238 space
= isl_space_set_dim_id(space
, isl_dim_set
, i
- skip
, id
);
1244 /* Return the current schedule, as stored in build->executed, in terms
1245 * of the external schedule domain.
1247 __isl_give isl_union_map
*isl_ast_build_get_schedule(
1248 __isl_keep isl_ast_build
*build
)
1250 isl_union_map
*executed
;
1251 isl_union_map
*schedule
;
1256 executed
= isl_union_map_copy(build
->executed
);
1257 if (isl_ast_build_need_schedule_map(build
)) {
1258 isl_map
*proj
= isl_ast_build_get_schedule_map(build
);
1259 executed
= isl_union_map_apply_domain(executed
,
1260 isl_union_map_from_map(proj
));
1262 schedule
= isl_union_map_reverse(executed
);
1267 /* Return the iterator attached to the internal schedule dimension "pos".
1269 __isl_give isl_id
*isl_ast_build_get_iterator_id(
1270 __isl_keep isl_ast_build
*build
, int pos
)
1275 return isl_id_list_get_id(build
->iterators
, pos
);
1278 /* Set the stride and offset of the current dimension to the given
1279 * value and expression.
1281 * If we had already found a stride before, then the two strides
1282 * are combined into a single stride.
1284 * In particular, if the new stride information is of the form
1288 * and the old stride information is of the form
1292 * then we compute the extended gcd of s and s2
1296 * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
1297 * and the second with t2 = a s1/g.
1300 * i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
1302 * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
1303 * is the combined stride.
1305 static __isl_give isl_ast_build
*set_stride(__isl_take isl_ast_build
*build
,
1306 __isl_take isl_val
*stride
, __isl_take isl_aff
*offset
)
1310 build
= isl_ast_build_cow(build
);
1311 if (!build
|| !stride
|| !offset
)
1316 if (isl_ast_build_has_stride(build
, pos
)) {
1317 isl_val
*stride2
, *a
, *b
, *g
;
1320 stride2
= isl_vec_get_element_val(build
->strides
, pos
);
1321 g
= isl_val_gcdext(isl_val_copy(stride
), isl_val_copy(stride2
),
1323 a
= isl_val_mul(a
, isl_val_copy(stride
));
1324 a
= isl_val_div(a
, isl_val_copy(g
));
1325 stride2
= isl_val_div(stride2
, g
);
1326 b
= isl_val_mul(b
, isl_val_copy(stride2
));
1327 stride
= isl_val_mul(stride
, stride2
);
1329 offset2
= isl_multi_aff_get_aff(build
->offsets
, pos
);
1330 offset2
= isl_aff_scale_val(offset2
, a
);
1331 offset
= isl_aff_scale_val(offset
, b
);
1332 offset
= isl_aff_add(offset
, offset2
);
1335 build
->strides
= isl_vec_set_element_val(build
->strides
, pos
, stride
);
1336 build
->offsets
= isl_multi_aff_set_aff(build
->offsets
, pos
, offset
);
1337 if (!build
->strides
|| !build
->offsets
)
1338 return isl_ast_build_free(build
);
1342 isl_val_free(stride
);
1343 isl_aff_free(offset
);
1344 return isl_ast_build_free(build
);
1347 /* Return a set expressing the stride constraint at the current depth.
1349 * In particular, if the current iterator (i) is known to attain values
1353 * where f is the offset and s is the stride, then the returned set
1354 * expresses the constraint
1358 __isl_give isl_set
*isl_ast_build_get_stride_constraint(
1359 __isl_keep isl_ast_build
*build
)
1371 if (!isl_ast_build_has_stride(build
, pos
))
1372 return isl_set_universe(isl_ast_build_get_space(build
, 1));
1374 stride
= isl_ast_build_get_stride(build
, pos
);
1375 aff
= isl_ast_build_get_offset(build
, pos
);
1376 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, pos
, -1);
1377 aff
= isl_aff_mod_val(aff
, stride
);
1378 set
= isl_set_from_basic_set(isl_aff_zero_basic_set(aff
));
1383 /* Return the expansion implied by the stride and offset at the current
1386 * That is, return the mapping
1388 * [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1389 * -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]
1391 * where s is the stride at the current depth d and offset(i) is
1392 * the corresponding offset.
1394 __isl_give isl_multi_aff
*isl_ast_build_get_stride_expansion(
1395 __isl_keep isl_ast_build
*build
)
1400 isl_aff
*aff
, *offset
;
1406 pos
= isl_ast_build_get_depth(build
);
1407 space
= isl_ast_build_get_space(build
, 1);
1408 space
= isl_space_map_from_set(space
);
1409 ma
= isl_multi_aff_identity(space
);
1411 if (!isl_ast_build_has_stride(build
, pos
))
1414 offset
= isl_ast_build_get_offset(build
, pos
);
1415 stride
= isl_ast_build_get_stride(build
, pos
);
1416 aff
= isl_multi_aff_get_aff(ma
, pos
);
1417 aff
= isl_aff_scale_val(aff
, stride
);
1418 aff
= isl_aff_add(aff
, offset
);
1419 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
1424 /* Add constraints corresponding to any previously detected
1425 * stride on the current dimension to build->domain.
1427 __isl_give isl_ast_build
*isl_ast_build_include_stride(
1428 __isl_take isl_ast_build
*build
)
1434 if (!isl_ast_build_has_stride(build
, build
->depth
))
1436 build
= isl_ast_build_cow(build
);
1440 set
= isl_ast_build_get_stride_constraint(build
);
1442 build
->domain
= isl_set_intersect(build
->domain
, isl_set_copy(set
));
1443 build
->generated
= isl_set_intersect(build
->generated
, set
);
1444 if (!build
->domain
|| !build
->generated
)
1445 return isl_ast_build_free(build
);
1450 /* Information used inside detect_stride.
1452 * "build" may be updated by detect_stride to include stride information.
1453 * "pos" is equal to build->depth.
1455 struct isl_detect_stride_data
{
1456 isl_ast_build
*build
;
1460 /* Check if constraint "c" imposes any stride on dimension data->pos
1461 * and, if so, update the stride information in data->build.
1463 * In order to impose a stride on the dimension, "c" needs to be an equality
1464 * and it needs to involve the dimension. Note that "c" may also be
1465 * a div constraint and thus an inequality that we cannot use.
1467 * Let c be of the form
1469 * h(p) + g * v * i + g * stride * f(alpha) = 0
1471 * with h(p) an expression in terms of the parameters and outer dimensions
1472 * and f(alpha) an expression in terms of the existentially quantified
1473 * variables. Note that the inner dimensions have been eliminated so
1474 * they do not appear in "c".
1476 * If "stride" is not zero and not one, then it represents a non-trivial stride
1477 * on "i". We compute a and b such that
1479 * a v + b stride = 1
1483 * g v i = -h(p) + g stride f(alpha)
1485 * a g v i = -a h(p) + g stride f(alpha)
1487 * a g v i + b g stride i = -a h(p) + g stride * (...)
1489 * g i = -a h(p) + g stride * (...)
1491 * i = -a h(p)/g + stride * (...)
1493 * The expression "-a h(p)/g" can therefore be used as offset.
1495 static isl_stat
detect_stride(__isl_take isl_constraint
*c
, void *user
)
1497 struct isl_detect_stride_data
*data
= user
;
1500 isl_val
*v
, *stride
, *m
;
1502 if (!isl_constraint_is_equality(c
) ||
1503 !isl_constraint_involves_dims(c
, isl_dim_set
, data
->pos
, 1)) {
1504 isl_constraint_free(c
);
1508 ctx
= isl_constraint_get_ctx(c
);
1509 stride
= isl_val_zero(ctx
);
1510 n_div
= isl_constraint_dim(c
, isl_dim_div
);
1511 for (i
= 0; i
< n_div
; ++i
) {
1512 v
= isl_constraint_get_coefficient_val(c
, isl_dim_div
, i
);
1513 stride
= isl_val_gcd(stride
, v
);
1516 v
= isl_constraint_get_coefficient_val(c
, isl_dim_set
, data
->pos
);
1517 m
= isl_val_gcd(isl_val_copy(stride
), isl_val_copy(v
));
1518 stride
= isl_val_div(stride
, isl_val_copy(m
));
1519 v
= isl_val_div(v
, isl_val_copy(m
));
1521 if (!isl_val_is_zero(stride
) && !isl_val_is_one(stride
)) {
1523 isl_val
*gcd
, *a
, *b
;
1525 gcd
= isl_val_gcdext(v
, isl_val_copy(stride
), &a
, &b
);
1529 aff
= isl_constraint_get_aff(c
);
1530 for (i
= 0; i
< n_div
; ++i
)
1531 aff
= isl_aff_set_coefficient_si(aff
,
1533 aff
= isl_aff_set_coefficient_si(aff
, isl_dim_in
, data
->pos
, 0);
1535 aff
= isl_aff_scale_val(aff
, a
);
1536 aff
= isl_aff_scale_down_val(aff
, m
);
1537 data
->build
= set_stride(data
->build
, stride
, aff
);
1539 isl_val_free(stride
);
1544 isl_constraint_free(c
);
1548 /* Check if the constraints in "set" imply any stride on the current
1549 * dimension and, if so, record the stride information in "build"
1550 * and return the updated "build".
1552 * We compute the affine hull and then check if any of the constraints
1553 * in the hull imposes any stride on the current dimension.
1555 * We assume that inner dimensions have been eliminated from "set"
1556 * by the caller. This is needed because the common stride
1557 * may be imposed by different inner dimensions on different parts of
1560 __isl_give isl_ast_build
*isl_ast_build_detect_strides(
1561 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
1563 isl_basic_set
*hull
;
1564 struct isl_detect_stride_data data
;
1570 data
.pos
= isl_ast_build_get_depth(build
);
1571 hull
= isl_set_affine_hull(set
);
1573 if (isl_basic_set_foreach_constraint(hull
, &detect_stride
, &data
) < 0)
1574 data
.build
= isl_ast_build_free(data
.build
);
1576 isl_basic_set_free(hull
);
1583 struct isl_ast_build_involves_data
{
1588 /* Check if "map" involves the input dimension data->depth.
1590 static isl_stat
involves_depth(__isl_take isl_map
*map
, void *user
)
1592 struct isl_ast_build_involves_data
*data
= user
;
1594 data
->involves
= isl_map_involves_dims(map
, isl_dim_in
, data
->depth
, 1);
1597 if (data
->involves
< 0 || data
->involves
)
1598 return isl_stat_error
;
1602 /* Do any options depend on the value of the dimension at the current depth?
1604 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build
*build
)
1606 struct isl_ast_build_involves_data data
;
1611 data
.depth
= build
->depth
;
1614 if (isl_union_map_foreach_map(build
->options
,
1615 &involves_depth
, &data
) < 0) {
1616 if (data
.involves
< 0 || !data
.involves
)
1620 return data
.involves
;
1623 /* Construct the map
1625 * { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1627 * with "space" the parameter space of the constructed map.
1629 static __isl_give isl_map
*construct_insertion_map(__isl_take isl_space
*space
,
1633 isl_basic_map
*bmap1
, *bmap2
;
1635 space
= isl_space_set_from_params(space
);
1636 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1637 space
= isl_space_map_from_set(space
);
1638 c
= isl_constraint_alloc_equality(isl_local_space_from_space(space
));
1639 c
= isl_constraint_set_coefficient_si(c
, isl_dim_in
, 0, 1);
1640 c
= isl_constraint_set_coefficient_si(c
, isl_dim_out
, 0, -1);
1641 bmap1
= isl_basic_map_from_constraint(isl_constraint_copy(c
));
1642 c
= isl_constraint_set_constant_si(c
, 1);
1643 bmap2
= isl_basic_map_from_constraint(c
);
1645 bmap1
= isl_basic_map_upper_bound_si(bmap1
, isl_dim_in
, 0, pos
- 1);
1646 bmap2
= isl_basic_map_lower_bound_si(bmap2
, isl_dim_in
, 0, pos
);
1648 return isl_basic_map_union(bmap1
, bmap2
);
1651 static const char *option_str
[] = {
1652 [isl_ast_loop_atomic
] = "atomic",
1653 [isl_ast_loop_unroll
] = "unroll",
1654 [isl_ast_loop_separate
] = "separate"
1657 /* Update the "options" to reflect the insertion of a dimension
1658 * at position "pos" in the schedule domain space.
1659 * "space" is the original domain space before the insertion and
1660 * may be named and/or structured.
1662 * The (relevant) input options all have "space" as domain, which
1663 * has to be mapped to the extended space.
1664 * The values of the ranges also refer to the schedule domain positions
1665 * and they therefore also need to be adjusted. In particular, values
1666 * smaller than pos do not need to change, while values greater than or
1667 * equal to pos need to be incremented.
1668 * That is, we need to apply the following map.
1670 * { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1671 * unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1672 * separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1673 * separation_class[[i] -> [c]]
1674 * -> separation_class[[i] -> [c]] : i < pos;
1675 * separation_class[[i] -> [c]]
1676 * -> separation_class[[i + 1] -> [c]] : i >= pos }
1678 static __isl_give isl_union_map
*options_insert_dim(
1679 __isl_take isl_union_map
*options
, __isl_take isl_space
*space
, int pos
)
1682 isl_union_map
*insertion
;
1683 enum isl_ast_loop_type type
;
1684 const char *name
= "separation_class";
1686 space
= isl_space_map_from_set(space
);
1687 map
= isl_map_identity(space
);
1688 map
= isl_map_insert_dims(map
, isl_dim_out
, pos
, 1);
1689 options
= isl_union_map_apply_domain(options
,
1690 isl_union_map_from_map(map
));
1695 map
= construct_insertion_map(isl_union_map_get_space(options
), pos
);
1697 insertion
= isl_union_map_empty(isl_union_map_get_space(options
));
1699 for (type
= isl_ast_loop_atomic
;
1700 type
<= isl_ast_loop_separate
; ++type
) {
1701 isl_map
*map_type
= isl_map_copy(map
);
1702 const char *name
= option_str
[type
];
1703 map_type
= isl_map_set_tuple_name(map_type
, isl_dim_in
, name
);
1704 map_type
= isl_map_set_tuple_name(map_type
, isl_dim_out
, name
);
1705 insertion
= isl_union_map_add_map(insertion
, map_type
);
1708 map
= isl_map_product(map
, isl_map_identity(isl_map_get_space(map
)));
1709 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
1710 map
= isl_map_set_tuple_name(map
, isl_dim_out
, name
);
1711 insertion
= isl_union_map_add_map(insertion
, map
);
1713 options
= isl_union_map_apply_range(options
, insertion
);
1718 /* If we are generating an AST from a schedule tree (build->node is set),
1719 * then update the loop AST generation types
1720 * to reflect the insertion of a dimension at (global) position "pos"
1721 * in the schedule domain space.
1722 * We do not need to adjust any isolate option since we would not be inserting
1723 * any dimensions if there were any isolate option.
1725 static __isl_give isl_ast_build
*node_insert_dim(
1726 __isl_take isl_ast_build
*build
, int pos
)
1730 enum isl_ast_loop_type
*loop_type
;
1733 build
= isl_ast_build_cow(build
);
1739 ctx
= isl_ast_build_get_ctx(build
);
1740 local_pos
= pos
- build
->outer_pos
;
1741 loop_type
= isl_realloc_array(ctx
, build
->loop_type
,
1742 enum isl_ast_loop_type
, build
->n
+ 1);
1744 return isl_ast_build_free(build
);
1745 build
->loop_type
= loop_type
;
1746 for (i
= build
->n
- 1; i
>= local_pos
; --i
)
1747 loop_type
[i
+ 1] = loop_type
[i
];
1748 loop_type
[local_pos
] = isl_ast_loop_default
;
1754 /* Insert a single dimension in the schedule domain at position "pos".
1755 * The new dimension is given an isl_id with the empty string as name.
1757 * The main difficulty is updating build->options to reflect the
1758 * extra dimension. This is handled in options_insert_dim.
1760 * Note that because of the dimension manipulations, the resulting
1761 * schedule domain space will always be unnamed and unstructured.
1762 * However, the original schedule domain space may be named and/or
1763 * structured, so we have to take this possibility into account
1764 * while performing the transformations.
1766 * Since the inserted schedule dimension is used by the caller
1767 * to differentiate between different domain spaces, there is
1768 * no longer a uniform mapping from the internal schedule space
1769 * to the input schedule space. The internal2input mapping is
1770 * therefore removed.
1772 __isl_give isl_ast_build
*isl_ast_build_insert_dim(
1773 __isl_take isl_ast_build
*build
, int pos
)
1776 isl_space
*space
, *ma_space
;
1780 build
= isl_ast_build_cow(build
);
1784 ctx
= isl_ast_build_get_ctx(build
);
1785 id
= isl_id_alloc(ctx
, "", NULL
);
1787 space
= isl_ast_build_get_space(build
, 1);
1788 build
->iterators
= isl_id_list_insert(build
->iterators
, pos
, id
);
1789 build
->domain
= isl_set_insert_dims(build
->domain
,
1790 isl_dim_set
, pos
, 1);
1791 build
->generated
= isl_set_insert_dims(build
->generated
,
1792 isl_dim_set
, pos
, 1);
1793 build
->pending
= isl_set_insert_dims(build
->pending
,
1794 isl_dim_set
, pos
, 1);
1795 build
->strides
= isl_vec_insert_els(build
->strides
, pos
, 1);
1796 build
->strides
= isl_vec_set_element_si(build
->strides
, pos
, 1);
1797 ma_space
= isl_space_params(isl_multi_aff_get_space(build
->offsets
));
1798 ma_space
= isl_space_set_from_params(ma_space
);
1799 ma_space
= isl_space_add_dims(ma_space
, isl_dim_set
, 1);
1800 ma_space
= isl_space_map_from_set(ma_space
);
1801 ma
= isl_multi_aff_zero(isl_space_copy(ma_space
));
1802 build
->offsets
= isl_multi_aff_splice(build
->offsets
, pos
, pos
, ma
);
1803 ma
= isl_multi_aff_identity(ma_space
);
1804 build
->values
= isl_multi_aff_splice(build
->values
, pos
, pos
, ma
);
1806 build
->options
= options_insert_dim(build
->options
, space
, pos
);
1807 build
->internal2input
= isl_multi_aff_free(build
->internal2input
);
1809 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
1810 !build
->pending
|| !build
->values
||
1811 !build
->strides
|| !build
->offsets
|| !build
->options
)
1812 return isl_ast_build_free(build
);
1814 build
= node_insert_dim(build
, pos
);
1819 /* Scale down the current dimension by a factor of "m".
1820 * "umap" is an isl_union_map that implements the scaling down.
1821 * That is, it is of the form
1823 * { [.... i ....] -> [.... i' ....] : i = m i' }
1825 * This function is called right after the strides have been
1826 * detected, but before any constraints on the current dimension
1827 * have been included in build->domain.
1828 * We therefore only need to update stride, offset, the options and
1829 * the mapping from internal schedule space to the original schedule
1830 * space, if we are still keeping track of such a mapping.
1831 * The latter mapping is updated by plugging in
1832 * { [... i ...] -> [... m i ... ] }.
1834 __isl_give isl_ast_build
*isl_ast_build_scale_down(
1835 __isl_take isl_ast_build
*build
, __isl_take isl_val
*m
,
1836 __isl_take isl_union_map
*umap
)
1842 build
= isl_ast_build_cow(build
);
1843 if (!build
|| !umap
|| !m
)
1846 depth
= build
->depth
;
1848 if (build
->internal2input
) {
1853 space
= isl_multi_aff_get_space(build
->internal2input
);
1854 space
= isl_space_map_from_set(isl_space_domain(space
));
1855 ma
= isl_multi_aff_identity(space
);
1856 aff
= isl_multi_aff_get_aff(ma
, depth
);
1857 aff
= isl_aff_scale_val(aff
, isl_val_copy(m
));
1858 ma
= isl_multi_aff_set_aff(ma
, depth
, aff
);
1859 build
->internal2input
=
1860 isl_multi_aff_pullback_multi_aff(build
->internal2input
, ma
);
1861 if (!build
->internal2input
)
1865 v
= isl_vec_get_element_val(build
->strides
, depth
);
1866 v
= isl_val_div(v
, isl_val_copy(m
));
1867 build
->strides
= isl_vec_set_element_val(build
->strides
, depth
, v
);
1869 aff
= isl_multi_aff_get_aff(build
->offsets
, depth
);
1870 aff
= isl_aff_scale_down_val(aff
, m
);
1871 build
->offsets
= isl_multi_aff_set_aff(build
->offsets
, depth
, aff
);
1872 build
->options
= isl_union_map_apply_domain(build
->options
, umap
);
1873 if (!build
->strides
|| !build
->offsets
|| !build
->options
)
1874 return isl_ast_build_free(build
);
1879 isl_union_map_free(umap
);
1880 return isl_ast_build_free(build
);
1883 /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1884 * If an isl_id with such a name already appears among the parameters
1885 * in build->domain, then adjust the name to "c%d_%d".
1887 static __isl_give isl_id_list
*generate_names(isl_ctx
*ctx
, int n
, int first
,
1888 __isl_keep isl_ast_build
*build
)
1893 names
= isl_id_list_alloc(ctx
, n
);
1894 for (i
= 0; i
< n
; ++i
) {
1897 id
= generate_name(ctx
, first
+ i
, build
);
1898 names
= isl_id_list_add(names
, id
);
1904 /* Embed "options" into the given isl_ast_build space.
1906 * This function is called from within a nested call to
1907 * isl_ast_build_node_from_schedule_map.
1908 * "options" refers to the additional schedule,
1909 * while space refers to both the space of the outer isl_ast_build and
1910 * that of the additional schedule.
1911 * Specifically, space is of the form
1915 * while options lives in the space(s)
1923 * and compose this with options, to obtain the new options
1924 * living in the space(s)
1928 static __isl_give isl_union_map
*embed_options(
1929 __isl_take isl_union_map
*options
, __isl_take isl_space
*space
)
1933 map
= isl_map_universe(isl_space_unwrap(space
));
1934 map
= isl_map_range_map(map
);
1936 options
= isl_union_map_apply_range(
1937 isl_union_map_from_map(map
), options
);
1942 /* Update "build" for use in a (possibly nested) code generation. That is,
1943 * extend "build" from an AST build on some domain O to an AST build
1944 * on domain [O -> S], with S corresponding to "space".
1945 * If the original domain is a parameter domain, then the new domain is
1947 * "iterators" is a list of iterators for S, but the number of elements
1948 * may be smaller or greater than the number of set dimensions of S.
1949 * If "keep_iterators" is set, then any extra ids in build->iterators
1950 * are reused for S. Otherwise, these extra ids are dropped.
1952 * We first update build->outer_pos to the current depth.
1953 * This depth is zero in case this is the outermost code generation.
1955 * We then add additional ids such that the number of iterators is at least
1956 * equal to the dimension of the new build domain.
1958 * If the original domain is parametric, then we are constructing
1959 * an isl_ast_build for the outer code generation and we pass control
1960 * to isl_ast_build_init.
1962 * Otherwise, we adjust the fields of "build" to include "space".
1964 __isl_give isl_ast_build
*isl_ast_build_product(
1965 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
1970 isl_multi_aff
*embedding
;
1973 build
= isl_ast_build_cow(build
);
1977 build
->outer_pos
= build
->depth
;
1979 ctx
= isl_ast_build_get_ctx(build
);
1980 dim
= isl_set_dim(build
->domain
, isl_dim_set
);
1981 dim
+= isl_space_dim(space
, isl_dim_set
);
1982 n_it
= isl_id_list_n_id(build
->iterators
);
1985 l
= generate_names(ctx
, dim
- n_it
, n_it
, build
);
1986 build
->iterators
= isl_id_list_concat(build
->iterators
, l
);
1989 if (isl_set_is_params(build
->domain
))
1990 return isl_ast_build_init(build
, space
);
1992 set
= isl_set_universe(isl_space_copy(space
));
1993 build
->domain
= isl_set_product(build
->domain
, isl_set_copy(set
));
1994 build
->pending
= isl_set_product(build
->pending
, isl_set_copy(set
));
1995 build
->generated
= isl_set_product(build
->generated
, set
);
1997 strides
= isl_vec_alloc(ctx
, isl_space_dim(space
, isl_dim_set
));
1998 strides
= isl_vec_set_si(strides
, 1);
1999 build
->strides
= isl_vec_concat(build
->strides
, strides
);
2001 space
= isl_space_map_from_set(space
);
2002 build
->offsets
= isl_multi_aff_align_params(build
->offsets
,
2003 isl_space_copy(space
));
2004 build
->offsets
= isl_multi_aff_product(build
->offsets
,
2005 isl_multi_aff_zero(isl_space_copy(space
)));
2006 build
->values
= isl_multi_aff_align_params(build
->values
,
2007 isl_space_copy(space
));
2008 embedding
= isl_multi_aff_identity(space
);
2009 build
->values
= isl_multi_aff_product(build
->values
,
2010 isl_multi_aff_copy(embedding
));
2011 if (build
->internal2input
) {
2012 build
->internal2input
=
2013 isl_multi_aff_product(build
->internal2input
, embedding
);
2014 build
->internal2input
=
2015 isl_multi_aff_flatten_range(build
->internal2input
);
2016 if (!build
->internal2input
)
2017 return isl_ast_build_free(build
);
2019 isl_multi_aff_free(embedding
);
2022 space
= isl_ast_build_get_space(build
, 1);
2023 build
->options
= embed_options(build
->options
, space
);
2025 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
2026 !build
->pending
|| !build
->values
||
2027 !build
->strides
|| !build
->offsets
|| !build
->options
)
2028 return isl_ast_build_free(build
);
2032 isl_ast_build_free(build
);
2033 isl_space_free(space
);
2037 /* Does "aff" only attain non-negative values over build->domain?
2038 * That is, does it not attain any negative values?
2040 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build
*build
,
2041 __isl_keep isl_aff
*aff
)
2049 aff
= isl_aff_copy(aff
);
2050 test
= isl_set_from_basic_set(isl_aff_neg_basic_set(aff
));
2051 test
= isl_set_intersect(test
, isl_set_copy(build
->domain
));
2052 empty
= isl_set_is_empty(test
);
2058 /* Does the dimension at (internal) position "pos" have a non-trivial stride?
2060 int isl_ast_build_has_stride(__isl_keep isl_ast_build
*build
, int pos
)
2068 v
= isl_vec_get_element_val(build
->strides
, pos
);
2071 has_stride
= !isl_val_is_one(v
);
2077 /* Given that the dimension at position "pos" takes on values
2081 * with a an integer, return s through *stride.
2083 __isl_give isl_val
*isl_ast_build_get_stride(__isl_keep isl_ast_build
*build
,
2089 return isl_vec_get_element_val(build
->strides
, pos
);
2092 /* Given that the dimension at position "pos" takes on values
2096 * with a an integer, return f.
2098 __isl_give isl_aff
*isl_ast_build_get_offset(
2099 __isl_keep isl_ast_build
*build
, int pos
)
2104 return isl_multi_aff_get_aff(build
->offsets
, pos
);
2107 /* Is the dimension at position "pos" known to attain only a single
2108 * value that, moreover, can be described by a single affine expression
2109 * in terms of the outer dimensions and parameters?
2111 * If not, then the corresponding affine expression in build->values
2112 * is set to be equal to the same input dimension.
2113 * Otherwise, it is set to the requested expression in terms of
2114 * outer dimensions and parameters.
2116 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build
*build
,
2125 aff
= isl_multi_aff_get_aff(build
->values
, pos
);
2126 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, pos
, 1);
2135 /* Plug in the known values (fixed affine expressions in terms of
2136 * parameters and outer loop iterators) of all loop iterators
2137 * in the domain of "umap".
2139 * We simply precompose "umap" with build->values.
2141 __isl_give isl_union_map
*isl_ast_build_substitute_values_union_map_domain(
2142 __isl_keep isl_ast_build
*build
, __isl_take isl_union_map
*umap
)
2144 isl_multi_aff
*values
;
2147 return isl_union_map_free(umap
);
2149 values
= isl_multi_aff_copy(build
->values
);
2150 umap
= isl_union_map_preimage_domain_multi_aff(umap
, values
);
2155 /* Is the current dimension known to attain only a single value?
2157 int isl_ast_build_has_value(__isl_keep isl_ast_build
*build
)
2162 return build
->value
!= NULL
;
2165 /* Simplify the basic set "bset" based on what we know about
2166 * the iterators of already generated loops.
2168 * "bset" is assumed to live in the (internal) schedule domain.
2170 __isl_give isl_basic_set
*isl_ast_build_compute_gist_basic_set(
2171 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
2176 bset
= isl_basic_set_preimage_multi_aff(bset
,
2177 isl_multi_aff_copy(build
->values
));
2178 bset
= isl_basic_set_gist(bset
,
2179 isl_set_simple_hull(isl_set_copy(build
->domain
)));
2183 isl_basic_set_free(bset
);
2187 /* Simplify the set "set" based on what we know about
2188 * the iterators of already generated loops.
2190 * "set" is assumed to live in the (internal) schedule domain.
2192 __isl_give isl_set
*isl_ast_build_compute_gist(
2193 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2198 if (!isl_set_is_params(set
))
2199 set
= isl_set_preimage_multi_aff(set
,
2200 isl_multi_aff_copy(build
->values
));
2201 set
= isl_set_gist(set
, isl_set_copy(build
->domain
));
2209 /* Include information about what we know about the iterators of
2210 * already generated loops to "set".
2212 * We currently only plug in the known affine values of outer loop
2214 * In principle we could also introduce equalities or even other
2215 * constraints implied by the intersection of "set" and build->domain.
2217 __isl_give isl_set
*isl_ast_build_specialize(__isl_keep isl_ast_build
*build
,
2218 __isl_take isl_set
*set
)
2221 return isl_set_free(set
);
2223 return isl_set_preimage_multi_aff(set
,
2224 isl_multi_aff_copy(build
->values
));
2227 /* Plug in the known affine values of outer loop iterators in "bset".
2229 __isl_give isl_basic_set
*isl_ast_build_specialize_basic_set(
2230 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
2233 return isl_basic_set_free(bset
);
2235 return isl_basic_set_preimage_multi_aff(bset
,
2236 isl_multi_aff_copy(build
->values
));
2239 /* Simplify the map "map" based on what we know about
2240 * the iterators of already generated loops.
2242 * The domain of "map" is assumed to live in the (internal) schedule domain.
2244 __isl_give isl_map
*isl_ast_build_compute_gist_map_domain(
2245 __isl_keep isl_ast_build
*build
, __isl_take isl_map
*map
)
2250 map
= isl_map_gist_domain(map
, isl_set_copy(build
->domain
));
2258 /* Simplify the affine expression "aff" based on what we know about
2259 * the iterators of already generated loops.
2261 * The domain of "aff" is assumed to live in the (internal) schedule domain.
2263 __isl_give isl_aff
*isl_ast_build_compute_gist_aff(
2264 __isl_keep isl_ast_build
*build
, __isl_take isl_aff
*aff
)
2269 aff
= isl_aff_gist(aff
, isl_set_copy(build
->domain
));
2277 /* Simplify the piecewise affine expression "aff" based on what we know about
2278 * the iterators of already generated loops.
2280 * The domain of "pa" is assumed to live in the (internal) schedule domain.
2282 __isl_give isl_pw_aff
*isl_ast_build_compute_gist_pw_aff(
2283 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
2288 if (!isl_set_is_params(build
->domain
))
2289 pa
= isl_pw_aff_pullback_multi_aff(pa
,
2290 isl_multi_aff_copy(build
->values
));
2291 pa
= isl_pw_aff_gist(pa
, isl_set_copy(build
->domain
));
2295 isl_pw_aff_free(pa
);
2299 /* Simplify the piecewise multi-affine expression "aff" based on what
2300 * we know about the iterators of already generated loops.
2302 * The domain of "pma" is assumed to live in the (internal) schedule domain.
2304 __isl_give isl_pw_multi_aff
*isl_ast_build_compute_gist_pw_multi_aff(
2305 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
2310 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
,
2311 isl_multi_aff_copy(build
->values
));
2312 pma
= isl_pw_multi_aff_gist(pma
, isl_set_copy(build
->domain
));
2316 isl_pw_multi_aff_free(pma
);
2320 /* Extract the schedule domain of the given type from build->options
2321 * at the current depth.
2323 * In particular, find the subset of build->options that is of
2324 * the following form
2326 * schedule_domain -> type[depth]
2328 * and return the corresponding domain, after eliminating inner dimensions
2329 * and divs that depend on the current dimension.
2331 * Note that the domain of build->options has been reformulated
2332 * in terms of the internal build space in embed_options,
2333 * but the position is still that within the current code generation.
2335 __isl_give isl_set
*isl_ast_build_get_option_domain(
2336 __isl_keep isl_ast_build
*build
, enum isl_ast_loop_type type
)
2347 name
= option_str
[type
];
2348 local_pos
= build
->depth
- build
->outer_pos
;
2350 space
= isl_ast_build_get_space(build
, 1);
2351 space
= isl_space_from_domain(space
);
2352 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
2353 space
= isl_space_set_tuple_name(space
, isl_dim_out
, name
);
2355 option
= isl_union_map_extract_map(build
->options
, space
);
2356 option
= isl_map_fix_si(option
, isl_dim_out
, 0, local_pos
);
2358 domain
= isl_map_domain(option
);
2359 domain
= isl_ast_build_eliminate(build
, domain
);
2364 /* How does the user want the current schedule dimension to be generated?
2365 * These choices have been extracted from the schedule node
2366 * in extract_loop_types and stored in build->loop_type.
2367 * They have been updated to reflect any dimension insertion in
2369 * Return isl_ast_domain_error on error.
2371 * If "isolated" is set, then we get the loop AST generation type
2372 * directly from the band node since node_insert_dim cannot have been
2373 * called on a band with the isolate option.
2375 enum isl_ast_loop_type
isl_ast_build_get_loop_type(
2376 __isl_keep isl_ast_build
*build
, int isolated
)
2382 return isl_ast_loop_error
;
2383 ctx
= isl_ast_build_get_ctx(build
);
2385 isl_die(ctx
, isl_error_internal
,
2386 "only works for schedule tree based AST generation",
2387 return isl_ast_loop_error
);
2389 local_pos
= build
->depth
- build
->outer_pos
;
2391 return build
->loop_type
[local_pos
];
2392 return isl_schedule_node_band_member_get_isolate_ast_loop_type(
2393 build
->node
, local_pos
);
2396 /* Extract the isolated set from the isolate option, if any,
2397 * and store in the build.
2398 * If there is no isolate option, then the isolated set is
2399 * set to the empty set.
2401 * The isolate option is of the form
2403 * isolate[[outer bands] -> current_band]
2405 * We flatten this set and then map it back to the internal
2408 * If we have already extracted the isolated set
2409 * or if internal2input is no longer set, then we do not
2410 * need to do anything. In the latter case, we know
2411 * that the current band cannot have any isolate option.
2413 __isl_give isl_ast_build
*isl_ast_build_extract_isolated(
2414 __isl_take isl_ast_build
*build
)
2416 isl_space
*space
, *space2
;
2417 isl_union_set
*options
;
2423 if (!build
->internal2input
)
2425 if (build
->isolated
)
2428 build
= isl_ast_build_cow(build
);
2432 options
= isl_schedule_node_band_get_ast_build_options(build
->node
);
2434 space
= isl_multi_aff_get_space(build
->internal2input
);
2435 space
= isl_space_range(space
);
2436 space2
= isl_set_get_space(build
->domain
);
2437 if (isl_space_is_wrapping(space2
))
2438 space2
= isl_space_range(isl_space_unwrap(space2
));
2439 n2
= isl_space_dim(space2
, isl_dim_set
);
2440 n
= isl_space_dim(space
, isl_dim_set
);
2442 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
2443 "total input space dimension cannot be smaller "
2444 "than dimension of innermost band",
2445 space
= isl_space_free(space
));
2446 space
= isl_space_drop_dims(space
, isl_dim_set
, n
- n2
, n2
);
2447 space
= isl_space_map_from_domain_and_range(space
, space2
);
2448 space
= isl_space_wrap(space
);
2449 space
= isl_space_set_tuple_name(space
, isl_dim_set
, "isolate");
2450 isolated
= isl_union_set_extract_set(options
, space
);
2451 isl_union_set_free(options
);
2453 isolated
= isl_set_flatten(isolated
);
2454 isolated
= isl_set_preimage_multi_aff(isolated
,
2455 isl_multi_aff_copy(build
->internal2input
));
2457 build
->isolated
= isolated
;
2458 if (!build
->isolated
)
2459 return isl_ast_build_free(build
);
2464 /* Does "build" have a non-empty isolated set?
2466 * The caller is assumed to have called isl_ast_build_extract_isolated first.
2468 int isl_ast_build_has_isolated(__isl_keep isl_ast_build
*build
)
2474 if (!build
->internal2input
)
2476 if (!build
->isolated
)
2477 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
2478 "isolated set not extracted yet", return -1);
2480 empty
= isl_set_plain_is_empty(build
->isolated
);
2481 return empty
< 0 ? -1 : !empty
;
2484 /* Return a copy of the isolated set of "build".
2486 * The caller is assume to have called isl_ast_build_has_isolated first,
2487 * with this function returning true.
2488 * In particular, this function should not be called if we are no
2489 * longer keeping track of internal2input (and there therefore could
2490 * not possibly be any isolated set).
2492 __isl_give isl_set
*isl_ast_build_get_isolated(__isl_keep isl_ast_build
*build
)
2496 if (!build
->internal2input
)
2497 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
2498 "build cannot have isolated set", return NULL
);
2500 return isl_set_copy(build
->isolated
);
2503 /* Extract the separation class mapping at the current depth.
2505 * In particular, find and return the subset of build->options that is of
2506 * the following form
2508 * schedule_domain -> separation_class[[depth] -> [class]]
2510 * The caller is expected to eliminate inner dimensions from the domain.
2512 * Note that the domain of build->options has been reformulated
2513 * in terms of the internal build space in embed_options,
2514 * but the position is still that within the current code generation.
2516 __isl_give isl_map
*isl_ast_build_get_separation_class(
2517 __isl_keep isl_ast_build
*build
)
2520 isl_space
*space_sep
, *space
;
2527 local_pos
= build
->depth
- build
->outer_pos
;
2528 ctx
= isl_ast_build_get_ctx(build
);
2529 space_sep
= isl_space_alloc(ctx
, 0, 1, 1);
2530 space_sep
= isl_space_wrap(space_sep
);
2531 space_sep
= isl_space_set_tuple_name(space_sep
, isl_dim_set
,
2532 "separation_class");
2533 space
= isl_ast_build_get_space(build
, 1);
2534 space_sep
= isl_space_align_params(space_sep
, isl_space_copy(space
));
2535 space
= isl_space_map_from_domain_and_range(space
, space_sep
);
2537 res
= isl_union_map_extract_map(build
->options
, space
);
2538 res
= isl_map_fix_si(res
, isl_dim_out
, 0, local_pos
);
2539 res
= isl_map_coalesce(res
);
2544 /* Eliminate dimensions inner to the current dimension.
2546 __isl_give isl_set
*isl_ast_build_eliminate_inner(
2547 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2553 return isl_set_free(set
);
2555 dim
= isl_set_dim(set
, isl_dim_set
);
2556 depth
= build
->depth
;
2557 set
= isl_set_detect_equalities(set
);
2558 set
= isl_set_eliminate(set
, isl_dim_set
, depth
+ 1, dim
- (depth
+ 1));
2563 /* Eliminate unknown divs and divs that depend on the current dimension.
2565 * Note that during the elimination of unknown divs, we may discover
2566 * an explicit representation of some other unknown divs, which may
2567 * depend on the current dimension. We therefore need to eliminate
2568 * unknown divs first.
2570 __isl_give isl_set
*isl_ast_build_eliminate_divs(
2571 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2576 return isl_set_free(set
);
2578 set
= isl_set_remove_unknown_divs(set
);
2579 depth
= build
->depth
;
2580 set
= isl_set_remove_divs_involving_dims(set
, isl_dim_set
, depth
, 1);
2585 /* Eliminate dimensions inner to the current dimension as well as
2586 * unknown divs and divs that depend on the current dimension.
2587 * The result then consists only of constraints that are independent
2588 * of the current dimension and upper and lower bounds on the current
2591 __isl_give isl_set
*isl_ast_build_eliminate(
2592 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*domain
)
2594 domain
= isl_ast_build_eliminate_inner(build
, domain
);
2595 domain
= isl_ast_build_eliminate_divs(build
, domain
);
2599 /* Replace build->single_valued by "sv".
2601 __isl_give isl_ast_build
*isl_ast_build_set_single_valued(
2602 __isl_take isl_ast_build
*build
, int sv
)
2606 if (build
->single_valued
== sv
)
2608 build
= isl_ast_build_cow(build
);
2611 build
->single_valued
= sv
;