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/space.h>
18 #include <isl/constraint.h>
20 #include <isl/union_set.h>
21 #include <isl/union_map.h>
22 #include <isl_ast_build_private.h>
23 #include <isl_ast_private.h>
24 #include <isl_config.h>
26 /* Construct a map that isolates the current dimension.
28 * Essentially, the current dimension of "set" is moved to the single output
29 * dimension in the result, with the current dimension in the domain replaced
30 * by an unconstrained variable.
32 __isl_give isl_map
*isl_ast_build_map_to_iterator(
33 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
37 map
= isl_map_from_domain(set
);
38 map
= isl_map_add_dims(map
, isl_dim_out
, 1);
41 return isl_map_free(map
);
43 map
= isl_map_equate(map
, isl_dim_in
, build
->depth
, isl_dim_out
, 0);
44 map
= isl_map_eliminate(map
, isl_dim_in
, build
->depth
, 1);
49 /* Initialize the information derived during the AST generation to default
50 * values for a schedule domain in "space".
52 * We also check that the remaining fields are not NULL so that
53 * the calling functions don't have to perform this test.
55 static __isl_give isl_ast_build
*isl_ast_build_init_derived(
56 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
62 build
= isl_ast_build_cow(build
);
63 if (!build
|| !build
->domain
)
66 ctx
= isl_ast_build_get_ctx(build
);
67 dim
= isl_space_dim(space
, isl_dim_set
);
70 strides
= isl_vec_alloc(ctx
, dim
);
71 strides
= isl_vec_set_si(strides
, 1);
73 isl_vec_free(build
->strides
);
74 build
->strides
= strides
;
76 space
= isl_space_map_from_set(space
);
77 isl_multi_aff_free(build
->offsets
);
78 build
->offsets
= isl_multi_aff_zero(isl_space_copy(space
));
79 isl_multi_aff_free(build
->values
);
80 build
->values
= isl_multi_aff_identity(isl_space_copy(space
));
81 isl_multi_aff_free(build
->internal2input
);
82 build
->internal2input
= isl_multi_aff_identity(space
);
84 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
85 !build
->pending
|| !build
->values
|| !build
->internal2input
||
86 !build
->strides
|| !build
->offsets
|| !build
->options
)
87 return isl_ast_build_free(build
);
91 isl_space_free(space
);
92 return isl_ast_build_free(build
);
95 /* Return an isl_id called "c%d", with "%d" set to "i".
96 * If an isl_id with such a name already appears among the parameters
97 * in build->domain, then adjust the name to "c%d_%d".
99 static __isl_give isl_id
*generate_name(isl_ctx
*ctx
, int i
,
100 __isl_keep isl_ast_build
*build
)
104 isl_set
*dom
= build
->domain
;
106 snprintf(name
, sizeof(name
), "c%d", i
);
108 while (isl_set_find_dim_by_name(dom
, isl_dim_param
, name
) >= 0)
109 snprintf(name
, sizeof(name
), "c%d_%d", i
, j
++);
110 return isl_id_alloc(ctx
, name
, NULL
);
113 /* Create an isl_ast_build with "set" as domain.
115 * The input set is usually a parameter domain, but we currently allow it to
116 * be any kind of set. We set the domain of the returned isl_ast_build
117 * to "set" and initialize all the other fields to default values.
119 __isl_give isl_ast_build
*isl_ast_build_from_context(__isl_take isl_set
*set
)
125 isl_ast_build
*build
;
127 set
= isl_set_compute_divs(set
);
128 n
= isl_set_dim(set
, isl_dim_set
);
132 ctx
= isl_set_get_ctx(set
);
134 build
= isl_calloc_type(ctx
, isl_ast_build
);
140 build
->generated
= isl_set_copy(build
->domain
);
141 build
->pending
= isl_set_universe(isl_set_get_space(build
->domain
));
142 build
->options
= isl_union_map_empty(isl_space_params_alloc(ctx
, 0));
144 build
->iterators
= isl_id_list_alloc(ctx
, n
);
145 for (i
= 0; i
< n
; ++i
) {
147 if (isl_set_has_dim_id(set
, isl_dim_set
, i
))
148 id
= isl_set_get_dim_id(set
, isl_dim_set
, i
);
150 id
= generate_name(ctx
, i
, build
);
151 build
->iterators
= isl_id_list_add(build
->iterators
, id
);
153 space
= isl_set_get_space(set
);
154 if (isl_space_is_params(space
))
155 space
= isl_space_set_from_params(space
);
157 return isl_ast_build_init_derived(build
, space
);
163 /* Create an isl_ast_build with a universe (parametric) context.
165 __isl_give isl_ast_build
*isl_ast_build_alloc(isl_ctx
*ctx
)
170 space
= isl_space_params_alloc(ctx
, 0);
171 context
= isl_set_universe(space
);
173 return isl_ast_build_from_context(context
);
176 __isl_give isl_ast_build
*isl_ast_build_copy(__isl_keep isl_ast_build
*build
)
185 __isl_give isl_ast_build
*isl_ast_build_dup(__isl_keep isl_ast_build
*build
)
193 ctx
= isl_ast_build_get_ctx(build
);
194 dup
= isl_calloc_type(ctx
, isl_ast_build
);
199 dup
->outer_pos
= build
->outer_pos
;
200 dup
->depth
= build
->depth
;
201 dup
->iterators
= isl_id_list_copy(build
->iterators
);
202 dup
->domain
= isl_set_copy(build
->domain
);
203 dup
->generated
= isl_set_copy(build
->generated
);
204 dup
->pending
= isl_set_copy(build
->pending
);
205 dup
->values
= isl_multi_aff_copy(build
->values
);
206 dup
->internal2input
= isl_multi_aff_copy(build
->internal2input
);
207 dup
->value
= isl_pw_aff_copy(build
->value
);
208 dup
->strides
= isl_vec_copy(build
->strides
);
209 dup
->offsets
= isl_multi_aff_copy(build
->offsets
);
210 dup
->executed
= isl_union_map_copy(build
->executed
);
211 dup
->single_valued
= build
->single_valued
;
212 dup
->options
= isl_union_map_copy(build
->options
);
213 dup
->at_each_domain
= build
->at_each_domain
;
214 dup
->at_each_domain_user
= build
->at_each_domain_user
;
215 dup
->before_each_for
= build
->before_each_for
;
216 dup
->before_each_for_user
= build
->before_each_for_user
;
217 dup
->after_each_for
= build
->after_each_for
;
218 dup
->after_each_for_user
= build
->after_each_for_user
;
219 dup
->before_each_mark
= build
->before_each_mark
;
220 dup
->before_each_mark_user
= build
->before_each_mark_user
;
221 dup
->after_each_mark
= build
->after_each_mark
;
222 dup
->after_each_mark_user
= build
->after_each_mark_user
;
223 dup
->create_leaf
= build
->create_leaf
;
224 dup
->create_leaf_user
= build
->create_leaf_user
;
225 dup
->node
= isl_schedule_node_copy(build
->node
);
226 if (build
->loop_type
) {
230 dup
->loop_type
= isl_alloc_array(ctx
,
231 enum isl_ast_loop_type
, dup
->n
);
232 if (dup
->n
&& !dup
->loop_type
)
233 return isl_ast_build_free(dup
);
234 for (i
= 0; i
< dup
->n
; ++i
)
235 dup
->loop_type
[i
] = build
->loop_type
[i
];
238 if (!dup
->iterators
|| !dup
->domain
|| !dup
->generated
||
239 !dup
->pending
|| !dup
->values
||
240 !dup
->strides
|| !dup
->offsets
|| !dup
->options
||
241 (build
->internal2input
&& !dup
->internal2input
) ||
242 (build
->executed
&& !dup
->executed
) ||
243 (build
->value
&& !dup
->value
) ||
244 (build
->node
&& !dup
->node
))
245 return isl_ast_build_free(dup
);
250 /* Align the parameters of "build" to those of "model", introducing
251 * additional parameters if needed.
253 __isl_give isl_ast_build
*isl_ast_build_align_params(
254 __isl_take isl_ast_build
*build
, __isl_take isl_space
*model
)
256 build
= isl_ast_build_cow(build
);
260 build
->domain
= isl_set_align_params(build
->domain
,
261 isl_space_copy(model
));
262 build
->generated
= isl_set_align_params(build
->generated
,
263 isl_space_copy(model
));
264 build
->pending
= isl_set_align_params(build
->pending
,
265 isl_space_copy(model
));
266 build
->values
= isl_multi_aff_align_params(build
->values
,
267 isl_space_copy(model
));
268 build
->offsets
= isl_multi_aff_align_params(build
->offsets
,
269 isl_space_copy(model
));
270 build
->options
= isl_union_map_align_params(build
->options
,
271 isl_space_copy(model
));
272 if (build
->internal2input
) {
273 build
->internal2input
=
274 isl_multi_aff_align_params(build
->internal2input
,
276 if (!build
->internal2input
)
277 return isl_ast_build_free(build
);
279 isl_space_free(model
);
282 if (!build
->domain
|| !build
->values
|| !build
->offsets
||
284 return isl_ast_build_free(build
);
288 isl_space_free(model
);
292 __isl_give isl_ast_build
*isl_ast_build_cow(__isl_take isl_ast_build
*build
)
300 return isl_ast_build_dup(build
);
303 __isl_null isl_ast_build
*isl_ast_build_free(
304 __isl_take isl_ast_build
*build
)
309 if (--build
->ref
> 0)
312 isl_id_list_free(build
->iterators
);
313 isl_set_free(build
->domain
);
314 isl_set_free(build
->generated
);
315 isl_set_free(build
->pending
);
316 isl_multi_aff_free(build
->values
);
317 isl_multi_aff_free(build
->internal2input
);
318 isl_pw_aff_free(build
->value
);
319 isl_vec_free(build
->strides
);
320 isl_multi_aff_free(build
->offsets
);
321 isl_multi_aff_free(build
->schedule_map
);
322 isl_union_map_free(build
->executed
);
323 isl_union_map_free(build
->options
);
324 isl_schedule_node_free(build
->node
);
325 free(build
->loop_type
);
326 isl_set_free(build
->isolated
);
333 isl_ctx
*isl_ast_build_get_ctx(__isl_keep isl_ast_build
*build
)
335 return build
? isl_set_get_ctx(build
->domain
) : NULL
;
338 /* Replace build->options by "options".
340 __isl_give isl_ast_build
*isl_ast_build_set_options(
341 __isl_take isl_ast_build
*build
, __isl_take isl_union_map
*options
)
343 build
= isl_ast_build_cow(build
);
345 if (!build
|| !options
)
348 isl_union_map_free(build
->options
);
349 build
->options
= options
;
353 isl_union_map_free(options
);
354 return isl_ast_build_free(build
);
357 /* Set the iterators for the next code generation.
359 * If we still have some iterators left from the previous code generation
360 * (if any) or if iterators have already been set by a previous
361 * call to this function, then we remove them first.
363 __isl_give isl_ast_build
*isl_ast_build_set_iterators(
364 __isl_take isl_ast_build
*build
, __isl_take isl_id_list
*iterators
)
369 build
= isl_ast_build_cow(build
);
373 dim
= isl_ast_build_dim(build
, isl_dim_set
);
374 n_it
= isl_id_list_n_id(build
->iterators
);
378 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
379 "isl_ast_build in inconsistent state", goto error
);
381 build
->iterators
= isl_id_list_drop(build
->iterators
,
383 build
->iterators
= isl_id_list_concat(build
->iterators
, iterators
);
384 if (!build
->iterators
)
385 return isl_ast_build_free(build
);
389 isl_id_list_free(iterators
);
390 return isl_ast_build_free(build
);
393 /* Set the "at_each_domain" callback of "build" to "fn".
395 __isl_give isl_ast_build
*isl_ast_build_set_at_each_domain(
396 __isl_take isl_ast_build
*build
,
397 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_node
*node
,
398 __isl_keep isl_ast_build
*build
, void *user
), void *user
)
400 build
= isl_ast_build_cow(build
);
405 build
->at_each_domain
= fn
;
406 build
->at_each_domain_user
= user
;
411 /* Set the "before_each_for" callback of "build" to "fn".
413 __isl_give isl_ast_build
*isl_ast_build_set_before_each_for(
414 __isl_take isl_ast_build
*build
,
415 __isl_give isl_id
*(*fn
)(__isl_keep isl_ast_build
*build
,
416 void *user
), void *user
)
418 build
= isl_ast_build_cow(build
);
423 build
->before_each_for
= fn
;
424 build
->before_each_for_user
= user
;
429 /* Set the "after_each_for" callback of "build" to "fn".
431 __isl_give isl_ast_build
*isl_ast_build_set_after_each_for(
432 __isl_take isl_ast_build
*build
,
433 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_node
*node
,
434 __isl_keep isl_ast_build
*build
, void *user
), void *user
)
436 build
= isl_ast_build_cow(build
);
441 build
->after_each_for
= fn
;
442 build
->after_each_for_user
= user
;
447 /* Set the "before_each_mark" callback of "build" to "fn".
449 __isl_give isl_ast_build
*isl_ast_build_set_before_each_mark(
450 __isl_take isl_ast_build
*build
,
451 isl_stat (*fn
)(__isl_keep isl_id
*mark
, __isl_keep isl_ast_build
*build
,
452 void *user
), void *user
)
454 build
= isl_ast_build_cow(build
);
459 build
->before_each_mark
= fn
;
460 build
->before_each_mark_user
= user
;
465 /* Set the "after_each_mark" callback of "build" to "fn".
467 __isl_give isl_ast_build
*isl_ast_build_set_after_each_mark(
468 __isl_take isl_ast_build
*build
,
469 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_node
*node
,
470 __isl_keep isl_ast_build
*build
, void *user
), void *user
)
472 build
= isl_ast_build_cow(build
);
477 build
->after_each_mark
= fn
;
478 build
->after_each_mark_user
= user
;
483 /* Set the "create_leaf" callback of "build" to "fn".
485 __isl_give isl_ast_build
*isl_ast_build_set_create_leaf(
486 __isl_take isl_ast_build
*build
,
487 __isl_give isl_ast_node
*(*fn
)(__isl_take isl_ast_build
*build
,
488 void *user
), void *user
)
490 build
= isl_ast_build_cow(build
);
495 build
->create_leaf
= fn
;
496 build
->create_leaf_user
= user
;
501 /* Clear all information that is specific to this code generation
502 * and that is (probably) not meaningful to any nested code generation.
504 __isl_give isl_ast_build
*isl_ast_build_clear_local_info(
505 __isl_take isl_ast_build
*build
)
509 build
= isl_ast_build_cow(build
);
513 space
= isl_union_map_get_space(build
->options
);
514 isl_union_map_free(build
->options
);
515 build
->options
= isl_union_map_empty(space
);
517 build
->at_each_domain
= NULL
;
518 build
->at_each_domain_user
= NULL
;
519 build
->before_each_for
= NULL
;
520 build
->before_each_for_user
= NULL
;
521 build
->after_each_for
= NULL
;
522 build
->after_each_for_user
= NULL
;
523 build
->before_each_mark
= NULL
;
524 build
->before_each_mark_user
= NULL
;
525 build
->after_each_mark
= NULL
;
526 build
->after_each_mark_user
= NULL
;
527 build
->create_leaf
= NULL
;
528 build
->create_leaf_user
= NULL
;
531 return isl_ast_build_free(build
);
536 /* Have any loops been eliminated?
537 * That is, do any of the original schedule dimensions have a fixed
538 * value that has been substituted?
540 static int any_eliminated(isl_ast_build
*build
)
544 for (i
= 0; i
< build
->depth
; ++i
)
545 if (isl_ast_build_has_affine_value(build
, i
))
551 /* Clear build->schedule_map.
552 * This function should be called whenever anything that might affect
553 * the result of isl_ast_build_get_schedule_map_multi_aff changes.
554 * In particular, it should be called when the depth is changed or
555 * when an iterator is determined to have a fixed value.
557 static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build
*build
)
561 isl_multi_aff_free(build
->schedule_map
);
562 build
->schedule_map
= NULL
;
565 /* Do we need a (non-trivial) schedule map?
566 * That is, is the internal schedule space different from
567 * the external schedule space?
569 * The internal and external schedule spaces are only the same
570 * if code has been generated for the entire schedule and if none
571 * of the loops have been eliminated.
573 isl_bool
isl_ast_build_need_schedule_map(__isl_keep isl_ast_build
*build
)
577 dim
= isl_ast_build_dim(build
, isl_dim_set
);
579 return isl_bool_error
;
580 return build
->depth
!= dim
|| any_eliminated(build
);
583 /* Return a mapping from the internal schedule space to the external
584 * schedule space in the form of an isl_multi_aff.
585 * The internal schedule space originally corresponds to that of the
586 * input schedule. This may change during the code generation if
587 * if isl_ast_build_insert_dim is ever called.
588 * The external schedule space corresponds to the
589 * loops that have been generated.
591 * Currently, the only difference between the internal schedule domain
592 * and the external schedule domain is that some dimensions are projected
593 * out in the external schedule domain. In particular, the dimensions
594 * for which no code has been generated yet and the dimensions that correspond
595 * to eliminated loops.
597 * We cache a copy of the schedule_map in build->schedule_map.
598 * The cache is cleared through isl_ast_build_reset_schedule_map
599 * whenever anything changes that might affect the result of this function.
601 __isl_give isl_multi_aff
*isl_ast_build_get_schedule_map_multi_aff(
602 __isl_keep isl_ast_build
*build
)
610 if (build
->schedule_map
)
611 return isl_multi_aff_copy(build
->schedule_map
);
612 needs_map
= isl_ast_build_need_schedule_map(build
);
616 space
= isl_ast_build_get_space(build
, 1);
617 space
= isl_space_map_from_set(space
);
618 ma
= isl_multi_aff_identity(space
);
621 isl_size dim
= isl_ast_build_dim(build
, isl_dim_set
);
624 ma
= isl_multi_aff_free(ma
);
625 ma
= isl_multi_aff_drop_dims(ma
, isl_dim_out
,
626 build
->depth
, dim
- build
->depth
);
627 for (i
= build
->depth
- 1; i
>= 0; --i
)
628 if (isl_ast_build_has_affine_value(build
, i
))
629 ma
= isl_multi_aff_drop_dims(ma
,
633 build
->schedule_map
= ma
;
634 return isl_multi_aff_copy(build
->schedule_map
);
637 /* Return a mapping from the internal schedule space to the external
638 * schedule space in the form of an isl_map.
640 __isl_give isl_map
*isl_ast_build_get_schedule_map(
641 __isl_keep isl_ast_build
*build
)
645 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
646 return isl_map_from_multi_aff(ma
);
649 /* Return the position of the dimension in build->domain for which
650 * an AST node is currently being generated.
652 int isl_ast_build_get_depth(__isl_keep isl_ast_build
*build
)
654 return build
? build
->depth
: -1;
657 /* Prepare for generating code for the next level.
658 * In particular, increase the depth and reset any information
659 * that is local to the current depth.
661 __isl_give isl_ast_build
*isl_ast_build_increase_depth(
662 __isl_take isl_ast_build
*build
)
664 build
= isl_ast_build_cow(build
);
668 isl_ast_build_reset_schedule_map(build
);
669 build
->value
= isl_pw_aff_free(build
->value
);
673 void isl_ast_build_dump(__isl_keep isl_ast_build
*build
)
678 fprintf(stderr
, "domain: ");
679 isl_set_dump(build
->domain
);
680 fprintf(stderr
, "generated: ");
681 isl_set_dump(build
->generated
);
682 fprintf(stderr
, "pending: ");
683 isl_set_dump(build
->pending
);
684 fprintf(stderr
, "iterators: ");
685 isl_id_list_dump(build
->iterators
);
686 fprintf(stderr
, "values: ");
687 isl_multi_aff_dump(build
->values
);
689 fprintf(stderr
, "value: ");
690 isl_pw_aff_dump(build
->value
);
692 fprintf(stderr
, "strides: ");
693 isl_vec_dump(build
->strides
);
694 fprintf(stderr
, "offsets: ");
695 isl_multi_aff_dump(build
->offsets
);
696 fprintf(stderr
, "internal2input: ");
697 isl_multi_aff_dump(build
->internal2input
);
700 /* Initialize "build" for AST construction in schedule space "space"
701 * in the case that build->domain is a parameter set.
703 * build->iterators is assumed to have been updated already.
705 static __isl_give isl_ast_build
*isl_ast_build_init(
706 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
710 build
= isl_ast_build_cow(build
);
714 set
= isl_set_universe(isl_space_copy(space
));
715 build
->domain
= isl_set_intersect_params(isl_set_copy(set
),
717 build
->pending
= isl_set_intersect_params(isl_set_copy(set
),
719 build
->generated
= isl_set_intersect_params(set
, build
->generated
);
721 return isl_ast_build_init_derived(build
, space
);
723 isl_ast_build_free(build
);
724 isl_space_free(space
);
728 /* Assign "aff" to *user and return -1, effectively extracting
729 * the first (and presumably only) affine expression in the isl_pw_aff
730 * on which this function is used.
732 static isl_stat
extract_single_piece(__isl_take isl_set
*set
,
733 __isl_take isl_aff
*aff
, void *user
)
740 return isl_stat_error
;
743 /* Intersect "set" with the stride constraint of "build", if any.
745 static __isl_give isl_set
*intersect_stride_constraint(__isl_take isl_set
*set
,
746 __isl_keep isl_ast_build
*build
)
751 return isl_set_free(set
);
752 if (!isl_ast_build_has_stride(build
, build
->depth
))
755 stride
= isl_ast_build_get_stride_constraint(build
);
756 return isl_set_intersect(set
, stride
);
759 /* Check if the given bounds on the current dimension (together with
760 * the stride constraint, if any) imply that
761 * this current dimension attains only a single value (in terms of
762 * parameters and outer dimensions).
763 * If so, we record it in build->value.
764 * If, moreover, this value can be represented as a single affine expression,
765 * then we also update build->values, effectively marking the current
766 * dimension as "eliminated".
768 * When computing the gist of the fixed value that can be represented
769 * as a single affine expression, it is important to only take into
770 * account the domain constraints in the original AST build and
771 * not the domain of the affine expression itself.
772 * Otherwise, a [i/3] is changed into a i/3 because we know that i
773 * is a multiple of 3, but then we end up not expressing anywhere
774 * in the context that i is a multiple of 3.
776 static __isl_give isl_ast_build
*update_values(
777 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
780 isl_pw_multi_aff
*pma
;
785 set
= isl_set_from_basic_set(bounds
);
786 set
= isl_set_intersect(set
, isl_set_copy(build
->domain
));
787 set
= intersect_stride_constraint(set
, build
);
788 it_map
= isl_ast_build_map_to_iterator(build
, set
);
790 sv
= isl_map_is_single_valued(it_map
);
792 build
= isl_ast_build_free(build
);
794 isl_map_free(it_map
);
798 pma
= isl_pw_multi_aff_from_map(it_map
);
799 build
->value
= isl_pw_multi_aff_get_pw_aff(pma
, 0);
800 build
->value
= isl_ast_build_compute_gist_pw_aff(build
, build
->value
);
801 build
->value
= isl_pw_aff_coalesce(build
->value
);
802 isl_pw_multi_aff_free(pma
);
805 return isl_ast_build_free(build
);
807 if (isl_pw_aff_n_piece(build
->value
) != 1)
810 isl_pw_aff_foreach_piece(build
->value
, &extract_single_piece
, &aff
);
812 build
->values
= isl_multi_aff_set_aff(build
->values
, build
->depth
, aff
);
814 return isl_ast_build_free(build
);
815 isl_ast_build_reset_schedule_map(build
);
819 /* Update the AST build based on the given loop bounds for
820 * the current dimension and the stride information available in the build.
822 * We first make sure that the bounds do not refer to any iterators
823 * that have already been eliminated.
824 * Then, we check if the bounds imply that the current iterator
826 * If they do and if this fixed value can be expressed as a single
827 * affine expression, we eliminate the iterators from the bounds.
828 * Note that we cannot simply plug in this single value using
829 * isl_basic_set_preimage_multi_aff as the single value may only
830 * be defined on a subset of the domain. Plugging in the value
831 * would restrict the build domain to this subset, while this
832 * restriction may not be reflected in the generated code.
833 * Finally, we intersect build->domain with the updated bounds.
834 * We also add the stride constraint unless we have been able
835 * to find a fixed value expressed as a single affine expression.
837 * Note that the check for a fixed value in update_values requires
838 * us to intersect the bounds with the current build domain.
839 * When we intersect build->domain with the updated bounds in
840 * the final step, we make sure that these updated bounds have
841 * not been intersected with the old build->domain.
842 * Otherwise, we would indirectly intersect the build domain with itself,
843 * which can lead to inefficiencies, in particular if the build domain
844 * contains any unknown divs.
846 * The pending and generated sets are not updated by this function to
847 * match the updated domain.
848 * The caller still needs to call isl_ast_build_set_pending_generated.
850 __isl_give isl_ast_build
*isl_ast_build_set_loop_bounds(
851 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
855 build
= isl_ast_build_cow(build
);
859 build
= update_values(build
, isl_basic_set_copy(bounds
));
862 set
= isl_set_from_basic_set(isl_basic_set_copy(bounds
));
863 if (isl_ast_build_has_affine_value(build
, build
->depth
)) {
864 set
= isl_set_eliminate(set
, isl_dim_set
, build
->depth
, 1);
865 set
= isl_set_compute_divs(set
);
866 build
->pending
= isl_set_intersect(build
->pending
,
868 build
->domain
= isl_set_intersect(build
->domain
, set
);
870 build
->domain
= isl_set_intersect(build
->domain
, set
);
871 build
= isl_ast_build_include_stride(build
);
875 isl_basic_set_free(bounds
);
877 if (!build
->domain
|| !build
->pending
|| !build
->generated
)
878 return isl_ast_build_free(build
);
882 isl_ast_build_free(build
);
883 isl_basic_set_free(bounds
);
887 /* Update the pending and generated sets of "build" according to "bounds".
888 * If the build has an affine value at the current depth,
889 * then isl_ast_build_set_loop_bounds has already set the pending set.
890 * Otherwise, do it here.
892 __isl_give isl_ast_build
*isl_ast_build_set_pending_generated(
893 __isl_take isl_ast_build
*build
, __isl_take isl_basic_set
*bounds
)
895 isl_basic_set
*generated
, *pending
;
900 if (isl_ast_build_has_affine_value(build
, build
->depth
)) {
901 isl_basic_set_free(bounds
);
905 build
= isl_ast_build_cow(build
);
909 pending
= isl_basic_set_copy(bounds
);
910 pending
= isl_basic_set_drop_constraints_involving_dims(pending
,
911 isl_dim_set
, build
->depth
, 1);
912 build
->pending
= isl_set_intersect(build
->pending
,
913 isl_set_from_basic_set(pending
));
915 generated
= isl_basic_set_drop_constraints_not_involving_dims(
916 generated
, isl_dim_set
, build
->depth
, 1);
917 build
->generated
= isl_set_intersect(build
->generated
,
918 isl_set_from_basic_set(generated
));
920 if (!build
->pending
|| !build
->generated
)
921 return isl_ast_build_free(build
);
925 isl_ast_build_free(build
);
926 isl_basic_set_free(bounds
);
930 /* Intersect build->domain with "set", where "set" is specified
931 * in terms of the internal schedule domain.
933 static __isl_give isl_ast_build
*isl_ast_build_restrict_internal(
934 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
936 build
= isl_ast_build_cow(build
);
940 set
= isl_set_compute_divs(set
);
941 build
->domain
= isl_set_intersect(build
->domain
, set
);
942 build
->domain
= isl_set_coalesce(build
->domain
);
945 return isl_ast_build_free(build
);
949 isl_ast_build_free(build
);
954 /* Intersect build->generated and build->domain with "set",
955 * where "set" is specified in terms of the internal schedule domain.
957 __isl_give isl_ast_build
*isl_ast_build_restrict_generated(
958 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
960 set
= isl_set_compute_divs(set
);
961 build
= isl_ast_build_restrict_internal(build
, isl_set_copy(set
));
962 build
= isl_ast_build_cow(build
);
966 build
->generated
= isl_set_intersect(build
->generated
, set
);
967 build
->generated
= isl_set_coalesce(build
->generated
);
969 if (!build
->generated
)
970 return isl_ast_build_free(build
);
974 isl_ast_build_free(build
);
979 /* Replace the set of pending constraints by "guard", which is then
980 * no longer considered as pending.
981 * That is, add "guard" to the generated constraints and clear all pending
982 * constraints, making the domain equal to the generated constraints.
984 __isl_give isl_ast_build
*isl_ast_build_replace_pending_by_guard(
985 __isl_take isl_ast_build
*build
, __isl_take isl_set
*guard
)
987 build
= isl_ast_build_restrict_generated(build
, guard
);
988 build
= isl_ast_build_cow(build
);
992 isl_set_free(build
->domain
);
993 build
->domain
= isl_set_copy(build
->generated
);
994 isl_set_free(build
->pending
);
995 build
->pending
= isl_set_universe(isl_set_get_space(build
->domain
));
998 return isl_ast_build_free(build
);
1003 /* Intersect build->domain with "set", where "set" is specified
1004 * in terms of the external schedule domain.
1006 __isl_give isl_ast_build
*isl_ast_build_restrict(
1007 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
1011 if (isl_set_is_params(set
))
1012 return isl_ast_build_restrict_generated(build
, set
);
1014 needs_map
= isl_ast_build_need_schedule_map(build
);
1019 ma
= isl_ast_build_get_schedule_map_multi_aff(build
);
1020 set
= isl_set_preimage_multi_aff(set
, ma
);
1022 return isl_ast_build_restrict_generated(build
, set
);
1024 isl_ast_build_free(build
);
1029 /* Replace build->executed by "executed".
1031 __isl_give isl_ast_build
*isl_ast_build_set_executed(
1032 __isl_take isl_ast_build
*build
, __isl_take isl_union_map
*executed
)
1034 build
= isl_ast_build_cow(build
);
1038 isl_union_map_free(build
->executed
);
1039 build
->executed
= executed
;
1043 isl_ast_build_free(build
);
1044 isl_union_map_free(executed
);
1048 /* Does "build" point to a band node?
1049 * That is, are we currently handling a band node inside a schedule tree?
1051 int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build
*build
)
1055 return build
->node
!= NULL
;
1058 /* Return a copy of the band node that "build" refers to.
1060 __isl_give isl_schedule_node
*isl_ast_build_get_schedule_node(
1061 __isl_keep isl_ast_build
*build
)
1065 return isl_schedule_node_copy(build
->node
);
1068 /* Extract the loop AST generation types for the members of build->node
1069 * and store them in build->loop_type.
1071 static __isl_give isl_ast_build
*extract_loop_types(
1072 __isl_take isl_ast_build
*build
)
1076 isl_schedule_node
*node
;
1080 ctx
= isl_ast_build_get_ctx(build
);
1082 isl_die(ctx
, isl_error_internal
, "missing AST node",
1083 return isl_ast_build_free(build
));
1085 free(build
->loop_type
);
1086 build
->n
= isl_schedule_node_band_n_member(build
->node
);
1087 build
->loop_type
= isl_alloc_array(ctx
,
1088 enum isl_ast_loop_type
, build
->n
);
1089 if (build
->n
&& !build
->loop_type
)
1090 return isl_ast_build_free(build
);
1092 for (i
= 0; i
< build
->n
; ++i
)
1093 build
->loop_type
[i
] =
1094 isl_schedule_node_band_member_get_ast_loop_type(node
, i
);
1099 /* Replace the band node that "build" refers to by "node" and
1100 * extract the corresponding loop AST generation types.
1102 __isl_give isl_ast_build
*isl_ast_build_set_schedule_node(
1103 __isl_take isl_ast_build
*build
,
1104 __isl_take isl_schedule_node
*node
)
1106 build
= isl_ast_build_cow(build
);
1107 if (!build
|| !node
)
1110 isl_schedule_node_free(build
->node
);
1113 build
= extract_loop_types(build
);
1117 isl_ast_build_free(build
);
1118 isl_schedule_node_free(node
);
1122 /* Remove any reference to a band node from "build".
1124 __isl_give isl_ast_build
*isl_ast_build_reset_schedule_node(
1125 __isl_take isl_ast_build
*build
)
1127 build
= isl_ast_build_cow(build
);
1131 isl_schedule_node_free(build
->node
);
1137 /* Return a copy of the current schedule domain.
1139 __isl_give isl_set
*isl_ast_build_get_domain(__isl_keep isl_ast_build
*build
)
1141 return build
? isl_set_copy(build
->domain
) : NULL
;
1144 /* Return a copy of the set of pending constraints.
1146 __isl_give isl_set
*isl_ast_build_get_pending(
1147 __isl_keep isl_ast_build
*build
)
1149 return build
? isl_set_copy(build
->pending
) : NULL
;
1152 /* Return a copy of the set of generated constraints.
1154 __isl_give isl_set
*isl_ast_build_get_generated(
1155 __isl_keep isl_ast_build
*build
)
1157 return build
? isl_set_copy(build
->generated
) : NULL
;
1160 /* Return a copy of the map from the internal schedule domain
1161 * to the original input schedule domain.
1163 __isl_give isl_multi_aff
*isl_ast_build_get_internal2input(
1164 __isl_keep isl_ast_build
*build
)
1166 return build
? isl_multi_aff_copy(build
->internal2input
) : NULL
;
1169 /* Return the number of variables of the given type
1170 * in the (internal) schedule space.
1172 isl_size
isl_ast_build_dim(__isl_keep isl_ast_build
*build
,
1173 enum isl_dim_type type
)
1176 return isl_size_error
;
1177 return isl_set_dim(build
->domain
, type
);
1180 /* Return the (schedule) space of "build".
1182 * If "internal" is set, then this space is the space of the internal
1183 * representation of the entire schedule, including those parts for
1184 * which no code has been generated yet.
1186 * If "internal" is not set, then this space is the external representation
1187 * of the loops generated so far.
1189 __isl_give isl_space
*isl_ast_build_get_space(__isl_keep isl_ast_build
*build
,
1200 space
= isl_set_get_space(build
->domain
);
1204 needs_map
= isl_ast_build_need_schedule_map(build
);
1206 return isl_space_free(space
);
1210 dim
= isl_ast_build_dim(build
, isl_dim_set
);
1212 return isl_space_free(space
);
1213 space
= isl_space_drop_dims(space
, isl_dim_set
,
1214 build
->depth
, dim
- build
->depth
);
1215 for (i
= build
->depth
- 1; i
>= 0; --i
) {
1216 isl_bool affine
= isl_ast_build_has_affine_value(build
, i
);
1219 return isl_space_free(space
);
1221 space
= isl_space_drop_dims(space
, isl_dim_set
, i
, 1);
1227 /* Return the external representation of the schedule space of "build",
1228 * i.e., a space with a dimension for each loop generated so far,
1229 * with the names of the dimensions set to the loop iterators.
1231 __isl_give isl_space
*isl_ast_build_get_schedule_space(
1232 __isl_keep isl_ast_build
*build
)
1240 space
= isl_ast_build_get_space(build
, 0);
1243 for (i
= 0; i
< build
->depth
; ++i
) {
1246 if (isl_ast_build_has_affine_value(build
, i
)) {
1251 id
= isl_ast_build_get_iterator_id(build
, i
);
1252 space
= isl_space_set_dim_id(space
, isl_dim_set
, i
- skip
, id
);
1258 /* Return the current schedule, as stored in build->executed, in terms
1259 * of the external schedule domain.
1261 __isl_give isl_union_map
*isl_ast_build_get_schedule(
1262 __isl_keep isl_ast_build
*build
)
1265 isl_union_map
*executed
;
1266 isl_union_map
*schedule
;
1268 needs_map
= isl_ast_build_need_schedule_map(build
);
1272 executed
= isl_union_map_copy(build
->executed
);
1274 isl_map
*proj
= isl_ast_build_get_schedule_map(build
);
1275 executed
= isl_union_map_apply_domain(executed
,
1276 isl_union_map_from_map(proj
));
1278 schedule
= isl_union_map_reverse(executed
);
1283 /* Return the iterator attached to the internal schedule dimension "pos".
1285 __isl_give isl_id
*isl_ast_build_get_iterator_id(
1286 __isl_keep isl_ast_build
*build
, int pos
)
1291 return isl_id_list_get_id(build
->iterators
, pos
);
1294 /* Set the stride and offset of the current dimension to the given
1295 * value and expression.
1297 static __isl_give isl_ast_build
*set_stride(__isl_take isl_ast_build
*build
,
1298 __isl_take isl_val
*stride
, __isl_take isl_aff
*offset
)
1302 build
= isl_ast_build_cow(build
);
1303 if (!build
|| !stride
|| !offset
)
1308 build
->strides
= isl_vec_set_element_val(build
->strides
, pos
, stride
);
1309 build
->offsets
= isl_multi_aff_set_aff(build
->offsets
, pos
, offset
);
1310 if (!build
->strides
|| !build
->offsets
)
1311 return isl_ast_build_free(build
);
1315 isl_val_free(stride
);
1316 isl_aff_free(offset
);
1317 return isl_ast_build_free(build
);
1320 /* Return a set expressing the stride constraint at the current depth.
1322 * In particular, if the current iterator (i) is known to attain values
1326 * where f is the offset and s is the stride, then the returned set
1327 * expresses the constraint
1331 __isl_give isl_set
*isl_ast_build_get_stride_constraint(
1332 __isl_keep isl_ast_build
*build
)
1344 if (!isl_ast_build_has_stride(build
, pos
))
1345 return isl_set_universe(isl_ast_build_get_space(build
, 1));
1347 stride
= isl_ast_build_get_stride(build
, pos
);
1348 aff
= isl_ast_build_get_offset(build
, pos
);
1349 aff
= isl_aff_add_coefficient_si(aff
, isl_dim_in
, pos
, -1);
1350 aff
= isl_aff_mod_val(aff
, stride
);
1351 set
= isl_set_from_basic_set(isl_aff_zero_basic_set(aff
));
1356 /* Return the expansion implied by the stride and offset at the current
1359 * That is, return the mapping
1361 * [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1362 * -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]
1364 * where s is the stride at the current depth d and offset(i) is
1365 * the corresponding offset.
1367 __isl_give isl_multi_aff
*isl_ast_build_get_stride_expansion(
1368 __isl_keep isl_ast_build
*build
)
1373 isl_aff
*aff
, *offset
;
1379 pos
= isl_ast_build_get_depth(build
);
1380 space
= isl_ast_build_get_space(build
, 1);
1381 space
= isl_space_map_from_set(space
);
1382 ma
= isl_multi_aff_identity(space
);
1384 if (!isl_ast_build_has_stride(build
, pos
))
1387 offset
= isl_ast_build_get_offset(build
, pos
);
1388 stride
= isl_ast_build_get_stride(build
, pos
);
1389 aff
= isl_multi_aff_get_aff(ma
, pos
);
1390 aff
= isl_aff_scale_val(aff
, stride
);
1391 aff
= isl_aff_add(aff
, offset
);
1392 ma
= isl_multi_aff_set_aff(ma
, pos
, aff
);
1397 /* Add constraints corresponding to any previously detected
1398 * stride on the current dimension to build->domain.
1400 __isl_give isl_ast_build
*isl_ast_build_include_stride(
1401 __isl_take isl_ast_build
*build
)
1407 if (!isl_ast_build_has_stride(build
, build
->depth
))
1409 build
= isl_ast_build_cow(build
);
1413 set
= isl_ast_build_get_stride_constraint(build
);
1415 build
->domain
= isl_set_intersect(build
->domain
, isl_set_copy(set
));
1416 build
->generated
= isl_set_intersect(build
->generated
, set
);
1417 if (!build
->domain
|| !build
->generated
)
1418 return isl_ast_build_free(build
);
1423 /* Check if the constraints in "set" imply any stride on the current
1424 * dimension and, if so, record the stride information in "build"
1425 * and return the updated "build".
1427 * We assume that inner dimensions have been eliminated from "set"
1428 * by the caller. This is needed because the common stride
1429 * may be imposed by different inner dimensions on different parts of
1431 * The assumption ensures that the lower bound does not depend
1432 * on inner dimensions.
1434 __isl_give isl_ast_build
*isl_ast_build_detect_strides(
1435 __isl_take isl_ast_build
*build
, __isl_take isl_set
*set
)
1441 isl_stride_info
*si
;
1446 pos
= isl_ast_build_get_depth(build
);
1447 si
= isl_set_get_stride_info(set
, pos
);
1448 stride
= isl_stride_info_get_stride(si
);
1449 offset
= isl_stride_info_get_offset(si
);
1450 isl_stride_info_free(si
);
1453 no_stride
= isl_val_is_one(stride
);
1454 if (no_stride
>= 0 && !no_stride
)
1455 return set_stride(build
, stride
, offset
);
1456 isl_val_free(stride
);
1457 isl_aff_free(offset
);
1459 return isl_ast_build_free(build
);
1466 struct isl_ast_build_involves_data
{
1471 /* Check if "map" involves the input dimension data->depth.
1473 static isl_stat
involves_depth(__isl_take isl_map
*map
, void *user
)
1475 struct isl_ast_build_involves_data
*data
= user
;
1477 data
->involves
= isl_map_involves_dims(map
, isl_dim_in
, data
->depth
, 1);
1480 if (data
->involves
< 0 || data
->involves
)
1481 return isl_stat_error
;
1485 /* Do any options depend on the value of the dimension at the current depth?
1487 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build
*build
)
1489 struct isl_ast_build_involves_data data
;
1494 data
.depth
= build
->depth
;
1497 if (isl_union_map_foreach_map(build
->options
,
1498 &involves_depth
, &data
) < 0) {
1499 if (data
.involves
< 0 || !data
.involves
)
1503 return data
.involves
;
1506 /* Construct the map
1508 * { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1510 * with "space" the parameter space of the constructed map.
1512 static __isl_give isl_map
*construct_insertion_map(__isl_take isl_space
*space
,
1516 isl_basic_map
*bmap1
, *bmap2
;
1518 space
= isl_space_set_from_params(space
);
1519 space
= isl_space_add_dims(space
, isl_dim_set
, 1);
1520 space
= isl_space_map_from_set(space
);
1521 c
= isl_constraint_alloc_equality(isl_local_space_from_space(space
));
1522 c
= isl_constraint_set_coefficient_si(c
, isl_dim_in
, 0, 1);
1523 c
= isl_constraint_set_coefficient_si(c
, isl_dim_out
, 0, -1);
1524 bmap1
= isl_basic_map_from_constraint(isl_constraint_copy(c
));
1525 c
= isl_constraint_set_constant_si(c
, 1);
1526 bmap2
= isl_basic_map_from_constraint(c
);
1528 bmap1
= isl_basic_map_upper_bound_si(bmap1
, isl_dim_in
, 0, pos
- 1);
1529 bmap2
= isl_basic_map_lower_bound_si(bmap2
, isl_dim_in
, 0, pos
);
1531 return isl_basic_map_union(bmap1
, bmap2
);
1534 static const char *option_str
[] = {
1535 [isl_ast_loop_atomic
] = "atomic",
1536 [isl_ast_loop_unroll
] = "unroll",
1537 [isl_ast_loop_separate
] = "separate"
1540 /* Update the "options" to reflect the insertion of a dimension
1541 * at position "pos" in the schedule domain space.
1542 * "space" is the original domain space before the insertion and
1543 * may be named and/or structured.
1545 * The (relevant) input options all have "space" as domain, which
1546 * has to be mapped to the extended space.
1547 * The values of the ranges also refer to the schedule domain positions
1548 * and they therefore also need to be adjusted. In particular, values
1549 * smaller than pos do not need to change, while values greater than or
1550 * equal to pos need to be incremented.
1551 * That is, we need to apply the following map.
1553 * { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1554 * unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1555 * separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1556 * separation_class[[i] -> [c]]
1557 * -> separation_class[[i] -> [c]] : i < pos;
1558 * separation_class[[i] -> [c]]
1559 * -> separation_class[[i + 1] -> [c]] : i >= pos }
1561 static __isl_give isl_union_map
*options_insert_dim(
1562 __isl_take isl_union_map
*options
, __isl_take isl_space
*space
, int pos
)
1565 isl_union_map
*insertion
;
1566 enum isl_ast_loop_type type
;
1567 const char *name
= "separation_class";
1569 space
= isl_space_map_from_set(space
);
1570 map
= isl_map_identity(space
);
1571 map
= isl_map_insert_dims(map
, isl_dim_out
, pos
, 1);
1572 options
= isl_union_map_apply_domain(options
,
1573 isl_union_map_from_map(map
));
1578 map
= construct_insertion_map(isl_union_map_get_space(options
), pos
);
1580 insertion
= isl_union_map_empty(isl_union_map_get_space(options
));
1582 for (type
= isl_ast_loop_atomic
;
1583 type
<= isl_ast_loop_separate
; ++type
) {
1584 isl_map
*map_type
= isl_map_copy(map
);
1585 const char *name
= option_str
[type
];
1586 map_type
= isl_map_set_tuple_name(map_type
, isl_dim_in
, name
);
1587 map_type
= isl_map_set_tuple_name(map_type
, isl_dim_out
, name
);
1588 insertion
= isl_union_map_add_map(insertion
, map_type
);
1591 map
= isl_map_product(map
, isl_map_identity(isl_map_get_space(map
)));
1592 map
= isl_map_set_tuple_name(map
, isl_dim_in
, name
);
1593 map
= isl_map_set_tuple_name(map
, isl_dim_out
, name
);
1594 insertion
= isl_union_map_add_map(insertion
, map
);
1596 options
= isl_union_map_apply_range(options
, insertion
);
1601 /* If we are generating an AST from a schedule tree (build->node is set),
1602 * then update the loop AST generation types
1603 * to reflect the insertion of a dimension at (global) position "pos"
1604 * in the schedule domain space.
1605 * We do not need to adjust any isolate option since we would not be inserting
1606 * any dimensions if there were any isolate option.
1608 static __isl_give isl_ast_build
*node_insert_dim(
1609 __isl_take isl_ast_build
*build
, int pos
)
1613 enum isl_ast_loop_type
*loop_type
;
1616 build
= isl_ast_build_cow(build
);
1622 ctx
= isl_ast_build_get_ctx(build
);
1623 local_pos
= pos
- build
->outer_pos
;
1624 loop_type
= isl_realloc_array(ctx
, build
->loop_type
,
1625 enum isl_ast_loop_type
, build
->n
+ 1);
1627 return isl_ast_build_free(build
);
1628 build
->loop_type
= loop_type
;
1629 for (i
= build
->n
- 1; i
>= local_pos
; --i
)
1630 loop_type
[i
+ 1] = loop_type
[i
];
1631 loop_type
[local_pos
] = isl_ast_loop_default
;
1637 /* Insert a single dimension in the schedule domain at position "pos".
1638 * The new dimension is given an isl_id with the empty string as name.
1640 * The main difficulty is updating build->options to reflect the
1641 * extra dimension. This is handled in options_insert_dim.
1643 * Note that because of the dimension manipulations, the resulting
1644 * schedule domain space will always be unnamed and unstructured.
1645 * However, the original schedule domain space may be named and/or
1646 * structured, so we have to take this possibility into account
1647 * while performing the transformations.
1649 * Since the inserted schedule dimension is used by the caller
1650 * to differentiate between different domain spaces, there is
1651 * no longer a uniform mapping from the internal schedule space
1652 * to the input schedule space. The internal2input mapping is
1653 * therefore removed.
1655 __isl_give isl_ast_build
*isl_ast_build_insert_dim(
1656 __isl_take isl_ast_build
*build
, int pos
)
1659 isl_space
*space
, *ma_space
;
1663 build
= isl_ast_build_cow(build
);
1667 ctx
= isl_ast_build_get_ctx(build
);
1668 id
= isl_id_alloc(ctx
, "", NULL
);
1670 space
= isl_ast_build_get_space(build
, 1);
1671 build
->iterators
= isl_id_list_insert(build
->iterators
, pos
, id
);
1672 build
->domain
= isl_set_insert_dims(build
->domain
,
1673 isl_dim_set
, pos
, 1);
1674 build
->generated
= isl_set_insert_dims(build
->generated
,
1675 isl_dim_set
, pos
, 1);
1676 build
->pending
= isl_set_insert_dims(build
->pending
,
1677 isl_dim_set
, pos
, 1);
1678 build
->strides
= isl_vec_insert_els(build
->strides
, pos
, 1);
1679 build
->strides
= isl_vec_set_element_si(build
->strides
, pos
, 1);
1680 ma_space
= isl_space_params(isl_multi_aff_get_space(build
->offsets
));
1681 ma_space
= isl_space_set_from_params(ma_space
);
1682 ma_space
= isl_space_add_dims(ma_space
, isl_dim_set
, 1);
1683 ma_space
= isl_space_map_from_set(ma_space
);
1684 ma
= isl_multi_aff_zero(isl_space_copy(ma_space
));
1685 build
->offsets
= isl_multi_aff_splice(build
->offsets
, pos
, pos
, ma
);
1686 ma
= isl_multi_aff_identity(ma_space
);
1687 build
->values
= isl_multi_aff_splice(build
->values
, pos
, pos
, ma
);
1689 build
->options
= options_insert_dim(build
->options
, space
, pos
);
1690 build
->internal2input
= isl_multi_aff_free(build
->internal2input
);
1692 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
1693 !build
->pending
|| !build
->values
||
1694 !build
->strides
|| !build
->offsets
|| !build
->options
)
1695 return isl_ast_build_free(build
);
1697 build
= node_insert_dim(build
, pos
);
1702 /* Scale down the current dimension by a factor of "m".
1703 * "umap" is an isl_union_map that implements the scaling down.
1704 * That is, it is of the form
1706 * { [.... i ....] -> [.... i' ....] : i = m i' }
1708 * This function is called right after the strides have been
1709 * detected, but before any constraints on the current dimension
1710 * have been included in build->domain.
1711 * We therefore only need to update stride, offset, the options and
1712 * the mapping from internal schedule space to the original schedule
1713 * space, if we are still keeping track of such a mapping.
1714 * The latter mapping is updated by plugging in
1715 * { [... i ...] -> [... m i ... ] }.
1717 __isl_give isl_ast_build
*isl_ast_build_scale_down(
1718 __isl_take isl_ast_build
*build
, __isl_take isl_val
*m
,
1719 __isl_take isl_union_map
*umap
)
1725 build
= isl_ast_build_cow(build
);
1726 if (!build
|| !umap
|| !m
)
1729 depth
= build
->depth
;
1731 if (build
->internal2input
) {
1736 space
= isl_multi_aff_get_space(build
->internal2input
);
1737 space
= isl_space_map_from_set(isl_space_domain(space
));
1738 ma
= isl_multi_aff_identity(space
);
1739 aff
= isl_multi_aff_get_aff(ma
, depth
);
1740 aff
= isl_aff_scale_val(aff
, isl_val_copy(m
));
1741 ma
= isl_multi_aff_set_aff(ma
, depth
, aff
);
1742 build
->internal2input
=
1743 isl_multi_aff_pullback_multi_aff(build
->internal2input
, ma
);
1744 if (!build
->internal2input
)
1748 v
= isl_vec_get_element_val(build
->strides
, depth
);
1749 v
= isl_val_div(v
, isl_val_copy(m
));
1750 build
->strides
= isl_vec_set_element_val(build
->strides
, depth
, v
);
1752 aff
= isl_multi_aff_get_aff(build
->offsets
, depth
);
1753 aff
= isl_aff_scale_down_val(aff
, m
);
1754 build
->offsets
= isl_multi_aff_set_aff(build
->offsets
, depth
, aff
);
1755 build
->options
= isl_union_map_apply_domain(build
->options
, umap
);
1756 if (!build
->strides
|| !build
->offsets
|| !build
->options
)
1757 return isl_ast_build_free(build
);
1762 isl_union_map_free(umap
);
1763 return isl_ast_build_free(build
);
1766 /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1767 * If an isl_id with such a name already appears among the parameters
1768 * in build->domain, then adjust the name to "c%d_%d".
1770 static __isl_give isl_id_list
*generate_names(isl_ctx
*ctx
, int n
, int first
,
1771 __isl_keep isl_ast_build
*build
)
1776 names
= isl_id_list_alloc(ctx
, n
);
1777 for (i
= 0; i
< n
; ++i
) {
1780 id
= generate_name(ctx
, first
+ i
, build
);
1781 names
= isl_id_list_add(names
, id
);
1787 /* Embed "options" into the given isl_ast_build space.
1789 * This function is called from within a nested call to
1790 * isl_ast_build_node_from_schedule_map.
1791 * "options" refers to the additional schedule,
1792 * while space refers to both the space of the outer isl_ast_build and
1793 * that of the additional schedule.
1794 * Specifically, space is of the form
1798 * while options lives in the space(s)
1806 * and compose this with options, to obtain the new options
1807 * living in the space(s)
1811 static __isl_give isl_union_map
*embed_options(
1812 __isl_take isl_union_map
*options
, __isl_take isl_space
*space
)
1816 map
= isl_map_universe(isl_space_unwrap(space
));
1817 map
= isl_map_range_map(map
);
1819 options
= isl_union_map_apply_range(
1820 isl_union_map_from_map(map
), options
);
1825 /* Update "build" for use in a (possibly nested) code generation. That is,
1826 * extend "build" from an AST build on some domain O to an AST build
1827 * on domain [O -> S], with S corresponding to "space".
1828 * If the original domain is a parameter domain, then the new domain is
1830 * "iterators" is a list of iterators for S, but the number of elements
1831 * may be smaller or greater than the number of set dimensions of S.
1832 * If "keep_iterators" is set, then any extra ids in build->iterators
1833 * are reused for S. Otherwise, these extra ids are dropped.
1835 * We first update build->outer_pos to the current depth.
1836 * This depth is zero in case this is the outermost code generation.
1838 * We then add additional ids such that the number of iterators is at least
1839 * equal to the dimension of the new build domain.
1841 * If the original domain is parametric, then we are constructing
1842 * an isl_ast_build for the outer code generation and we pass control
1843 * to isl_ast_build_init.
1845 * Otherwise, we adjust the fields of "build" to include "space".
1847 __isl_give isl_ast_build
*isl_ast_build_product(
1848 __isl_take isl_ast_build
*build
, __isl_take isl_space
*space
)
1853 isl_multi_aff
*embedding
;
1854 isl_size dim
, space_dim
;
1857 build
= isl_ast_build_cow(build
);
1861 build
->outer_pos
= build
->depth
;
1863 ctx
= isl_ast_build_get_ctx(build
);
1864 dim
= isl_ast_build_dim(build
, isl_dim_set
);
1865 space_dim
= isl_space_dim(space
, isl_dim_set
);
1866 n_it
= isl_id_list_n_id(build
->iterators
);
1867 if (dim
< 0 || space_dim
< 0)
1872 l
= generate_names(ctx
, dim
- n_it
, n_it
, build
);
1873 build
->iterators
= isl_id_list_concat(build
->iterators
, l
);
1876 if (isl_set_is_params(build
->domain
))
1877 return isl_ast_build_init(build
, space
);
1879 set
= isl_set_universe(isl_space_copy(space
));
1880 build
->domain
= isl_set_product(build
->domain
, isl_set_copy(set
));
1881 build
->pending
= isl_set_product(build
->pending
, isl_set_copy(set
));
1882 build
->generated
= isl_set_product(build
->generated
, set
);
1884 strides
= isl_vec_alloc(ctx
, space_dim
);
1885 strides
= isl_vec_set_si(strides
, 1);
1886 build
->strides
= isl_vec_concat(build
->strides
, strides
);
1888 space
= isl_space_map_from_set(space
);
1889 build
->offsets
= isl_multi_aff_align_params(build
->offsets
,
1890 isl_space_copy(space
));
1891 build
->offsets
= isl_multi_aff_product(build
->offsets
,
1892 isl_multi_aff_zero(isl_space_copy(space
)));
1893 build
->values
= isl_multi_aff_align_params(build
->values
,
1894 isl_space_copy(space
));
1895 embedding
= isl_multi_aff_identity(space
);
1896 build
->values
= isl_multi_aff_product(build
->values
,
1897 isl_multi_aff_copy(embedding
));
1898 if (build
->internal2input
) {
1899 build
->internal2input
=
1900 isl_multi_aff_product(build
->internal2input
, embedding
);
1901 build
->internal2input
=
1902 isl_multi_aff_flatten_range(build
->internal2input
);
1903 if (!build
->internal2input
)
1904 return isl_ast_build_free(build
);
1906 isl_multi_aff_free(embedding
);
1909 space
= isl_ast_build_get_space(build
, 1);
1910 build
->options
= embed_options(build
->options
, space
);
1912 if (!build
->iterators
|| !build
->domain
|| !build
->generated
||
1913 !build
->pending
|| !build
->values
||
1914 !build
->strides
|| !build
->offsets
|| !build
->options
)
1915 return isl_ast_build_free(build
);
1919 isl_ast_build_free(build
);
1920 isl_space_free(space
);
1924 /* Does "aff" only attain non-negative values over build->domain?
1925 * That is, does it not attain any negative values?
1927 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build
*build
,
1928 __isl_keep isl_aff
*aff
)
1936 aff
= isl_aff_copy(aff
);
1937 test
= isl_set_from_basic_set(isl_aff_neg_basic_set(aff
));
1938 test
= isl_set_intersect(test
, isl_set_copy(build
->domain
));
1939 empty
= isl_set_is_empty(test
);
1945 /* Does the dimension at (internal) position "pos" have a non-trivial stride?
1947 isl_bool
isl_ast_build_has_stride(__isl_keep isl_ast_build
*build
, int pos
)
1950 isl_bool has_stride
;
1953 return isl_bool_error
;
1955 v
= isl_vec_get_element_val(build
->strides
, pos
);
1956 has_stride
= isl_bool_not(isl_val_is_one(v
));
1962 /* Given that the dimension at position "pos" takes on values
1966 * with a an integer, return s through *stride.
1968 __isl_give isl_val
*isl_ast_build_get_stride(__isl_keep isl_ast_build
*build
,
1974 return isl_vec_get_element_val(build
->strides
, pos
);
1977 /* Given that the dimension at position "pos" takes on values
1981 * with a an integer, return f.
1983 __isl_give isl_aff
*isl_ast_build_get_offset(
1984 __isl_keep isl_ast_build
*build
, int pos
)
1989 return isl_multi_aff_get_aff(build
->offsets
, pos
);
1992 /* Is the dimension at position "pos" known to attain only a single
1993 * value that, moreover, can be described by a single affine expression
1994 * in terms of the outer dimensions and parameters?
1996 * If not, then the corresponding affine expression in build->values
1997 * is set to be equal to the same input dimension.
1998 * Otherwise, it is set to the requested expression in terms of
1999 * outer dimensions and parameters.
2001 isl_bool
isl_ast_build_has_affine_value(__isl_keep isl_ast_build
*build
,
2008 return isl_bool_error
;
2010 aff
= isl_multi_aff_get_aff(build
->values
, pos
);
2011 involves
= isl_aff_involves_dims(aff
, isl_dim_in
, pos
, 1);
2014 return isl_bool_not(involves
);
2017 /* Plug in the known values (fixed affine expressions in terms of
2018 * parameters and outer loop iterators) of all loop iterators
2019 * in the domain of "umap".
2021 * We simply precompose "umap" with build->values.
2023 __isl_give isl_union_map
*isl_ast_build_substitute_values_union_map_domain(
2024 __isl_keep isl_ast_build
*build
, __isl_take isl_union_map
*umap
)
2026 isl_multi_aff
*values
;
2029 return isl_union_map_free(umap
);
2031 values
= isl_multi_aff_copy(build
->values
);
2032 umap
= isl_union_map_preimage_domain_multi_aff(umap
, values
);
2037 /* Is the current dimension known to attain only a single value?
2039 int isl_ast_build_has_value(__isl_keep isl_ast_build
*build
)
2044 return build
->value
!= NULL
;
2047 /* Simplify the basic set "bset" based on what we know about
2048 * the iterators of already generated loops.
2050 * "bset" is assumed to live in the (internal) schedule domain.
2052 __isl_give isl_basic_set
*isl_ast_build_compute_gist_basic_set(
2053 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
2058 bset
= isl_basic_set_preimage_multi_aff(bset
,
2059 isl_multi_aff_copy(build
->values
));
2060 bset
= isl_basic_set_gist(bset
,
2061 isl_set_simple_hull(isl_set_copy(build
->domain
)));
2065 isl_basic_set_free(bset
);
2069 /* Simplify the set "set" based on what we know about
2070 * the iterators of already generated loops.
2072 * "set" is assumed to live in the (internal) schedule domain.
2074 __isl_give isl_set
*isl_ast_build_compute_gist(
2075 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2080 if (!isl_set_is_params(set
))
2081 set
= isl_set_preimage_multi_aff(set
,
2082 isl_multi_aff_copy(build
->values
));
2083 set
= isl_set_gist(set
, isl_set_copy(build
->domain
));
2091 /* Include information about what we know about the iterators of
2092 * already generated loops to "set".
2094 * We currently only plug in the known affine values of outer loop
2096 * In principle we could also introduce equalities or even other
2097 * constraints implied by the intersection of "set" and build->domain.
2099 __isl_give isl_set
*isl_ast_build_specialize(__isl_keep isl_ast_build
*build
,
2100 __isl_take isl_set
*set
)
2103 return isl_set_free(set
);
2105 return isl_set_preimage_multi_aff(set
,
2106 isl_multi_aff_copy(build
->values
));
2109 /* Plug in the known affine values of outer loop iterators in "bset".
2111 __isl_give isl_basic_set
*isl_ast_build_specialize_basic_set(
2112 __isl_keep isl_ast_build
*build
, __isl_take isl_basic_set
*bset
)
2115 return isl_basic_set_free(bset
);
2117 return isl_basic_set_preimage_multi_aff(bset
,
2118 isl_multi_aff_copy(build
->values
));
2121 /* Simplify the map "map" based on what we know about
2122 * the iterators of already generated loops.
2124 * The domain of "map" is assumed to live in the (internal) schedule domain.
2126 __isl_give isl_map
*isl_ast_build_compute_gist_map_domain(
2127 __isl_keep isl_ast_build
*build
, __isl_take isl_map
*map
)
2132 map
= isl_map_gist_domain(map
, isl_set_copy(build
->domain
));
2140 /* Simplify the affine expression "aff" based on what we know about
2141 * the iterators of already generated loops.
2143 * The domain of "aff" is assumed to live in the (internal) schedule domain.
2145 __isl_give isl_aff
*isl_ast_build_compute_gist_aff(
2146 __isl_keep isl_ast_build
*build
, __isl_take isl_aff
*aff
)
2151 aff
= isl_aff_gist(aff
, isl_set_copy(build
->domain
));
2159 /* Simplify the piecewise affine expression "aff" based on what we know about
2160 * the iterators of already generated loops.
2162 * The domain of "pa" is assumed to live in the (internal) schedule domain.
2164 __isl_give isl_pw_aff
*isl_ast_build_compute_gist_pw_aff(
2165 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_aff
*pa
)
2170 if (!isl_set_is_params(build
->domain
))
2171 pa
= isl_pw_aff_pullback_multi_aff(pa
,
2172 isl_multi_aff_copy(build
->values
));
2173 pa
= isl_pw_aff_gist(pa
, isl_set_copy(build
->domain
));
2177 isl_pw_aff_free(pa
);
2181 /* Simplify the piecewise multi-affine expression "aff" based on what
2182 * we know about the iterators of already generated loops.
2184 * The domain of "pma" is assumed to live in the (internal) schedule domain.
2186 __isl_give isl_pw_multi_aff
*isl_ast_build_compute_gist_pw_multi_aff(
2187 __isl_keep isl_ast_build
*build
, __isl_take isl_pw_multi_aff
*pma
)
2192 pma
= isl_pw_multi_aff_pullback_multi_aff(pma
,
2193 isl_multi_aff_copy(build
->values
));
2194 pma
= isl_pw_multi_aff_gist(pma
, isl_set_copy(build
->domain
));
2198 isl_pw_multi_aff_free(pma
);
2202 /* Extract the schedule domain of the given type from build->options
2203 * at the current depth.
2205 * In particular, find the subset of build->options that is of
2206 * the following form
2208 * schedule_domain -> type[depth]
2210 * and return the corresponding domain, after eliminating inner dimensions
2211 * and divs that depend on the current dimension.
2213 * Note that the domain of build->options has been reformulated
2214 * in terms of the internal build space in embed_options,
2215 * but the position is still that within the current code generation.
2217 __isl_give isl_set
*isl_ast_build_get_option_domain(
2218 __isl_keep isl_ast_build
*build
, enum isl_ast_loop_type type
)
2229 name
= option_str
[type
];
2230 local_pos
= build
->depth
- build
->outer_pos
;
2232 space
= isl_ast_build_get_space(build
, 1);
2233 space
= isl_space_from_domain(space
);
2234 space
= isl_space_add_dims(space
, isl_dim_out
, 1);
2235 space
= isl_space_set_tuple_name(space
, isl_dim_out
, name
);
2237 option
= isl_union_map_extract_map(build
->options
, space
);
2238 option
= isl_map_fix_si(option
, isl_dim_out
, 0, local_pos
);
2240 domain
= isl_map_domain(option
);
2241 domain
= isl_ast_build_eliminate(build
, domain
);
2246 /* How does the user want the current schedule dimension to be generated?
2247 * These choices have been extracted from the schedule node
2248 * in extract_loop_types and stored in build->loop_type.
2249 * They have been updated to reflect any dimension insertion in
2251 * Return isl_ast_domain_error on error.
2253 * If "isolated" is set, then we get the loop AST generation type
2254 * directly from the band node since node_insert_dim cannot have been
2255 * called on a band with the isolate option.
2257 enum isl_ast_loop_type
isl_ast_build_get_loop_type(
2258 __isl_keep isl_ast_build
*build
, int isolated
)
2264 return isl_ast_loop_error
;
2265 ctx
= isl_ast_build_get_ctx(build
);
2267 isl_die(ctx
, isl_error_internal
,
2268 "only works for schedule tree based AST generation",
2269 return isl_ast_loop_error
);
2271 local_pos
= build
->depth
- build
->outer_pos
;
2273 return build
->loop_type
[local_pos
];
2274 return isl_schedule_node_band_member_get_isolate_ast_loop_type(
2275 build
->node
, local_pos
);
2278 /* Extract the isolated set from the isolate option, if any,
2279 * and store in the build.
2280 * If there is no isolate option, then the isolated set is
2281 * set to the empty set.
2283 * The isolate option is of the form
2285 * isolate[[outer bands] -> current_band]
2287 * We flatten this set and then map it back to the internal
2290 * If we have already extracted the isolated set
2291 * or if internal2input is no longer set, then we do not
2292 * need to do anything. In the latter case, we know
2293 * that the current band cannot have any isolate option.
2295 __isl_give isl_ast_build
*isl_ast_build_extract_isolated(
2296 __isl_take isl_ast_build
*build
)
2302 if (!build
->internal2input
)
2304 if (build
->isolated
)
2307 build
= isl_ast_build_cow(build
);
2311 isolated
= isl_schedule_node_band_get_ast_isolate_option(build
->node
);
2312 isolated
= isl_set_flatten(isolated
);
2313 isolated
= isl_set_preimage_multi_aff(isolated
,
2314 isl_multi_aff_copy(build
->internal2input
));
2316 build
->isolated
= isolated
;
2317 if (!build
->isolated
)
2318 return isl_ast_build_free(build
);
2323 /* Does "build" have a non-empty isolated set?
2325 * The caller is assumed to have called isl_ast_build_extract_isolated first.
2327 int isl_ast_build_has_isolated(__isl_keep isl_ast_build
*build
)
2333 if (!build
->internal2input
)
2335 if (!build
->isolated
)
2336 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
2337 "isolated set not extracted yet", return -1);
2339 empty
= isl_set_plain_is_empty(build
->isolated
);
2340 return empty
< 0 ? -1 : !empty
;
2343 /* Return a copy of the isolated set of "build".
2345 * The caller is assume to have called isl_ast_build_has_isolated first,
2346 * with this function returning true.
2347 * In particular, this function should not be called if we are no
2348 * longer keeping track of internal2input (and there therefore could
2349 * not possibly be any isolated set).
2351 __isl_give isl_set
*isl_ast_build_get_isolated(__isl_keep isl_ast_build
*build
)
2355 if (!build
->internal2input
)
2356 isl_die(isl_ast_build_get_ctx(build
), isl_error_internal
,
2357 "build cannot have isolated set", return NULL
);
2359 return isl_set_copy(build
->isolated
);
2362 /* Extract the separation class mapping at the current depth.
2364 * In particular, find and return the subset of build->options that is of
2365 * the following form
2367 * schedule_domain -> separation_class[[depth] -> [class]]
2369 * The caller is expected to eliminate inner dimensions from the domain.
2371 * Note that the domain of build->options has been reformulated
2372 * in terms of the internal build space in embed_options,
2373 * but the position is still that within the current code generation.
2375 __isl_give isl_map
*isl_ast_build_get_separation_class(
2376 __isl_keep isl_ast_build
*build
)
2379 isl_space
*space_sep
, *space
;
2386 local_pos
= build
->depth
- build
->outer_pos
;
2387 ctx
= isl_ast_build_get_ctx(build
);
2388 space_sep
= isl_space_alloc(ctx
, 0, 1, 1);
2389 space_sep
= isl_space_wrap(space_sep
);
2390 space_sep
= isl_space_set_tuple_name(space_sep
, isl_dim_set
,
2391 "separation_class");
2392 space
= isl_ast_build_get_space(build
, 1);
2393 space_sep
= isl_space_align_params(space_sep
, isl_space_copy(space
));
2394 space
= isl_space_map_from_domain_and_range(space
, space_sep
);
2396 res
= isl_union_map_extract_map(build
->options
, space
);
2397 res
= isl_map_fix_si(res
, isl_dim_out
, 0, local_pos
);
2398 res
= isl_map_coalesce(res
);
2403 /* Eliminate dimensions inner to the current dimension.
2405 __isl_give isl_set
*isl_ast_build_eliminate_inner(
2406 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2412 return isl_set_free(set
);
2414 dim
= isl_set_dim(set
, isl_dim_set
);
2415 depth
= build
->depth
;
2416 set
= isl_set_detect_equalities(set
);
2417 set
= isl_set_eliminate(set
, isl_dim_set
, depth
+ 1, dim
- (depth
+ 1));
2422 /* Eliminate unknown divs and divs that depend on the current dimension.
2424 * Note that during the elimination of unknown divs, we may discover
2425 * an explicit representation of some other unknown divs, which may
2426 * depend on the current dimension. We therefore need to eliminate
2427 * unknown divs first.
2429 __isl_give isl_set
*isl_ast_build_eliminate_divs(
2430 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*set
)
2435 return isl_set_free(set
);
2437 set
= isl_set_remove_unknown_divs(set
);
2438 depth
= build
->depth
;
2439 set
= isl_set_remove_divs_involving_dims(set
, isl_dim_set
, depth
, 1);
2444 /* Eliminate dimensions inner to the current dimension as well as
2445 * unknown divs and divs that depend on the current dimension.
2446 * The result then consists only of constraints that are independent
2447 * of the current dimension and upper and lower bounds on the current
2450 __isl_give isl_set
*isl_ast_build_eliminate(
2451 __isl_keep isl_ast_build
*build
, __isl_take isl_set
*domain
)
2453 domain
= isl_ast_build_eliminate_inner(build
, domain
);
2454 domain
= isl_ast_build_eliminate_divs(build
, domain
);
2458 /* Replace build->single_valued by "sv".
2460 __isl_give isl_ast_build
*isl_ast_build_set_single_valued(
2461 __isl_take isl_ast_build
*build
, int sv
)
2465 if (build
->single_valued
== sv
)
2467 build
= isl_ast_build_cow(build
);
2470 build
->single_valued
= sv
;