isl_map_simplify.c: extract out setup_constraint_index
[isl.git] / isl_ast_build.c
blob381d8f65475d2a75692068d44c01bd3c829493f2
1 /*
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
13 #include <isl/map.h>
14 #include <isl/aff.h>
15 #include <isl/constraint.h>
16 #include <isl/map.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>
21 #include <isl_config.h>
23 /* Construct a map that isolates the current dimension.
25 * Essentially, the current dimension of "set" is moved to the single output
26 * dimension in the result, with the current dimension in the domain replaced
27 * by an unconstrained variable.
29 __isl_give isl_map *isl_ast_build_map_to_iterator(
30 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
32 isl_map *map;
34 map = isl_map_from_domain(set);
35 map = isl_map_add_dims(map, isl_dim_out, 1);
37 if (!build)
38 return isl_map_free(map);
40 map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0);
41 map = isl_map_eliminate(map, isl_dim_in, build->depth, 1);
43 return map;
46 /* Initialize the information derived during the AST generation to default
47 * values for a schedule domain in "space".
49 * We also check that the remaining fields are not NULL so that
50 * the calling functions don't have to perform this test.
52 static __isl_give isl_ast_build *isl_ast_build_init_derived(
53 __isl_take isl_ast_build *build, __isl_take isl_space *space)
55 isl_ctx *ctx;
56 isl_vec *strides;
58 build = isl_ast_build_cow(build);
59 if (!build || !build->domain)
60 goto error;
62 ctx = isl_ast_build_get_ctx(build);
63 strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
64 strides = isl_vec_set_si(strides, 1);
66 isl_vec_free(build->strides);
67 build->strides = strides;
69 space = isl_space_map_from_set(space);
70 isl_multi_aff_free(build->offsets);
71 build->offsets = isl_multi_aff_zero(isl_space_copy(space));
72 isl_multi_aff_free(build->values);
73 build->values = isl_multi_aff_identity(isl_space_copy(space));
74 isl_multi_aff_free(build->internal2input);
75 build->internal2input = isl_multi_aff_identity(space);
77 if (!build->iterators || !build->domain || !build->generated ||
78 !build->pending || !build->values || !build->internal2input ||
79 !build->strides || !build->offsets || !build->options)
80 return isl_ast_build_free(build);
82 return build;
83 error:
84 isl_space_free(space);
85 return isl_ast_build_free(build);
88 /* Return an isl_id called "c%d", with "%d" set to "i".
89 * If an isl_id with such a name already appears among the parameters
90 * in build->domain, then adjust the name to "c%d_%d".
92 static __isl_give isl_id *generate_name(isl_ctx *ctx, int i,
93 __isl_keep isl_ast_build *build)
95 int j;
96 char name[16];
97 isl_set *dom = build->domain;
99 snprintf(name, sizeof(name), "c%d", i);
100 j = 0;
101 while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)
102 snprintf(name, sizeof(name), "c%d_%d", i, j++);
103 return isl_id_alloc(ctx, name, NULL);
106 /* Create an isl_ast_build with "set" as domain.
108 * The input set is usually a parameter domain, but we currently allow it to
109 * be any kind of set. We set the domain of the returned isl_ast_build
110 * to "set" and initialize all the other fields to default values.
112 __isl_give isl_ast_build *isl_ast_build_from_context(__isl_take isl_set *set)
114 int i, n;
115 isl_ctx *ctx;
116 isl_space *space;
117 isl_ast_build *build;
119 set = isl_set_compute_divs(set);
120 if (!set)
121 return NULL;
123 ctx = isl_set_get_ctx(set);
125 build = isl_calloc_type(ctx, isl_ast_build);
126 if (!build)
127 goto error;
129 build->ref = 1;
130 build->domain = set;
131 build->generated = isl_set_copy(build->domain);
132 build->pending = isl_set_universe(isl_set_get_space(build->domain));
133 build->options = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
134 n = isl_set_dim(set, isl_dim_set);
135 build->depth = n;
136 build->iterators = isl_id_list_alloc(ctx, n);
137 for (i = 0; i < n; ++i) {
138 isl_id *id;
139 if (isl_set_has_dim_id(set, isl_dim_set, i))
140 id = isl_set_get_dim_id(set, isl_dim_set, i);
141 else
142 id = generate_name(ctx, i, build);
143 build->iterators = isl_id_list_add(build->iterators, id);
145 space = isl_set_get_space(set);
146 if (isl_space_is_params(space))
147 space = isl_space_set_from_params(space);
149 return isl_ast_build_init_derived(build, space);
150 error:
151 isl_set_free(set);
152 return NULL;
155 /* Create an isl_ast_build with a universe (parametric) context.
157 __isl_give isl_ast_build *isl_ast_build_alloc(isl_ctx *ctx)
159 isl_space *space;
160 isl_set *context;
162 space = isl_space_params_alloc(ctx, 0);
163 context = isl_set_universe(space);
165 return isl_ast_build_from_context(context);
168 __isl_give isl_ast_build *isl_ast_build_copy(__isl_keep isl_ast_build *build)
170 if (!build)
171 return NULL;
173 build->ref++;
174 return build;
177 __isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
179 isl_ctx *ctx;
180 isl_ast_build *dup;
182 if (!build)
183 return NULL;
185 ctx = isl_ast_build_get_ctx(build);
186 dup = isl_calloc_type(ctx, isl_ast_build);
187 if (!dup)
188 return NULL;
190 dup->ref = 1;
191 dup->outer_pos = build->outer_pos;
192 dup->depth = build->depth;
193 dup->iterators = isl_id_list_copy(build->iterators);
194 dup->domain = isl_set_copy(build->domain);
195 dup->generated = isl_set_copy(build->generated);
196 dup->pending = isl_set_copy(build->pending);
197 dup->values = isl_multi_aff_copy(build->values);
198 dup->internal2input = isl_multi_aff_copy(build->internal2input);
199 dup->value = isl_pw_aff_copy(build->value);
200 dup->strides = isl_vec_copy(build->strides);
201 dup->offsets = isl_multi_aff_copy(build->offsets);
202 dup->executed = isl_union_map_copy(build->executed);
203 dup->single_valued = build->single_valued;
204 dup->options = isl_union_map_copy(build->options);
205 dup->at_each_domain = build->at_each_domain;
206 dup->at_each_domain_user = build->at_each_domain_user;
207 dup->before_each_for = build->before_each_for;
208 dup->before_each_for_user = build->before_each_for_user;
209 dup->after_each_for = build->after_each_for;
210 dup->after_each_for_user = build->after_each_for_user;
211 dup->before_each_mark = build->before_each_mark;
212 dup->before_each_mark_user = build->before_each_mark_user;
213 dup->after_each_mark = build->after_each_mark;
214 dup->after_each_mark_user = build->after_each_mark_user;
215 dup->create_leaf = build->create_leaf;
216 dup->create_leaf_user = build->create_leaf_user;
217 dup->node = isl_schedule_node_copy(build->node);
218 if (build->loop_type) {
219 int i;
221 dup->n = build->n;
222 dup->loop_type = isl_alloc_array(ctx,
223 enum isl_ast_loop_type, dup->n);
224 if (dup->n && !dup->loop_type)
225 return isl_ast_build_free(dup);
226 for (i = 0; i < dup->n; ++i)
227 dup->loop_type[i] = build->loop_type[i];
230 if (!dup->iterators || !dup->domain || !dup->generated ||
231 !dup->pending || !dup->values ||
232 !dup->strides || !dup->offsets || !dup->options ||
233 (build->internal2input && !dup->internal2input) ||
234 (build->executed && !dup->executed) ||
235 (build->value && !dup->value) ||
236 (build->node && !dup->node))
237 return isl_ast_build_free(dup);
239 return dup;
242 /* Align the parameters of "build" to those of "model", introducing
243 * additional parameters if needed.
245 __isl_give isl_ast_build *isl_ast_build_align_params(
246 __isl_take isl_ast_build *build, __isl_take isl_space *model)
248 build = isl_ast_build_cow(build);
249 if (!build)
250 goto error;
252 build->domain = isl_set_align_params(build->domain,
253 isl_space_copy(model));
254 build->generated = isl_set_align_params(build->generated,
255 isl_space_copy(model));
256 build->pending = isl_set_align_params(build->pending,
257 isl_space_copy(model));
258 build->values = isl_multi_aff_align_params(build->values,
259 isl_space_copy(model));
260 build->offsets = isl_multi_aff_align_params(build->offsets,
261 isl_space_copy(model));
262 build->options = isl_union_map_align_params(build->options,
263 isl_space_copy(model));
264 if (build->internal2input) {
265 build->internal2input =
266 isl_multi_aff_align_params(build->internal2input,
267 model);
268 if (!build->internal2input)
269 return isl_ast_build_free(build);
270 } else {
271 isl_space_free(model);
274 if (!build->domain || !build->values || !build->offsets ||
275 !build->options)
276 return isl_ast_build_free(build);
278 return build;
279 error:
280 isl_space_free(model);
281 return NULL;
284 __isl_give isl_ast_build *isl_ast_build_cow(__isl_take isl_ast_build *build)
286 if (!build)
287 return NULL;
289 if (build->ref == 1)
290 return build;
291 build->ref--;
292 return isl_ast_build_dup(build);
295 __isl_null isl_ast_build *isl_ast_build_free(
296 __isl_take isl_ast_build *build)
298 if (!build)
299 return NULL;
301 if (--build->ref > 0)
302 return NULL;
304 isl_id_list_free(build->iterators);
305 isl_set_free(build->domain);
306 isl_set_free(build->generated);
307 isl_set_free(build->pending);
308 isl_multi_aff_free(build->values);
309 isl_multi_aff_free(build->internal2input);
310 isl_pw_aff_free(build->value);
311 isl_vec_free(build->strides);
312 isl_multi_aff_free(build->offsets);
313 isl_multi_aff_free(build->schedule_map);
314 isl_union_map_free(build->executed);
315 isl_union_map_free(build->options);
316 isl_schedule_node_free(build->node);
317 free(build->loop_type);
318 isl_set_free(build->isolated);
320 free(build);
322 return NULL;
325 isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build)
327 return build ? isl_set_get_ctx(build->domain) : NULL;
330 /* Replace build->options by "options".
332 __isl_give isl_ast_build *isl_ast_build_set_options(
333 __isl_take isl_ast_build *build, __isl_take isl_union_map *options)
335 build = isl_ast_build_cow(build);
337 if (!build || !options)
338 goto error;
340 isl_union_map_free(build->options);
341 build->options = options;
343 return build;
344 error:
345 isl_union_map_free(options);
346 return isl_ast_build_free(build);
349 /* Set the iterators for the next code generation.
351 * If we still have some iterators left from the previous code generation
352 * (if any) or if iterators have already been set by a previous
353 * call to this function, then we remove them first.
355 __isl_give isl_ast_build *isl_ast_build_set_iterators(
356 __isl_take isl_ast_build *build, __isl_take isl_id_list *iterators)
358 int dim, n_it;
360 build = isl_ast_build_cow(build);
361 if (!build)
362 goto error;
364 dim = isl_set_dim(build->domain, isl_dim_set);
365 n_it = isl_id_list_n_id(build->iterators);
366 if (n_it < dim)
367 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
368 "isl_ast_build in inconsistent state", goto error);
369 if (n_it > dim)
370 build->iterators = isl_id_list_drop(build->iterators,
371 dim, n_it - dim);
372 build->iterators = isl_id_list_concat(build->iterators, iterators);
373 if (!build->iterators)
374 return isl_ast_build_free(build);
376 return build;
377 error:
378 isl_id_list_free(iterators);
379 return isl_ast_build_free(build);
382 /* Set the "at_each_domain" callback of "build" to "fn".
384 __isl_give isl_ast_build *isl_ast_build_set_at_each_domain(
385 __isl_take isl_ast_build *build,
386 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
387 __isl_keep isl_ast_build *build, void *user), void *user)
389 build = isl_ast_build_cow(build);
391 if (!build)
392 return NULL;
394 build->at_each_domain = fn;
395 build->at_each_domain_user = user;
397 return build;
400 /* Set the "before_each_for" callback of "build" to "fn".
402 __isl_give isl_ast_build *isl_ast_build_set_before_each_for(
403 __isl_take isl_ast_build *build,
404 __isl_give isl_id *(*fn)(__isl_keep isl_ast_build *build,
405 void *user), void *user)
407 build = isl_ast_build_cow(build);
409 if (!build)
410 return NULL;
412 build->before_each_for = fn;
413 build->before_each_for_user = user;
415 return build;
418 /* Set the "after_each_for" callback of "build" to "fn".
420 __isl_give isl_ast_build *isl_ast_build_set_after_each_for(
421 __isl_take isl_ast_build *build,
422 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
423 __isl_keep isl_ast_build *build, void *user), void *user)
425 build = isl_ast_build_cow(build);
427 if (!build)
428 return NULL;
430 build->after_each_for = fn;
431 build->after_each_for_user = user;
433 return build;
436 /* Set the "before_each_mark" callback of "build" to "fn".
438 __isl_give isl_ast_build *isl_ast_build_set_before_each_mark(
439 __isl_take isl_ast_build *build,
440 isl_stat (*fn)(__isl_keep isl_id *mark, __isl_keep isl_ast_build *build,
441 void *user), void *user)
443 build = isl_ast_build_cow(build);
445 if (!build)
446 return NULL;
448 build->before_each_mark = fn;
449 build->before_each_mark_user = user;
451 return build;
454 /* Set the "after_each_mark" callback of "build" to "fn".
456 __isl_give isl_ast_build *isl_ast_build_set_after_each_mark(
457 __isl_take isl_ast_build *build,
458 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
459 __isl_keep isl_ast_build *build, void *user), void *user)
461 build = isl_ast_build_cow(build);
463 if (!build)
464 return NULL;
466 build->after_each_mark = fn;
467 build->after_each_mark_user = user;
469 return build;
472 /* Set the "create_leaf" callback of "build" to "fn".
474 __isl_give isl_ast_build *isl_ast_build_set_create_leaf(
475 __isl_take isl_ast_build *build,
476 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_build *build,
477 void *user), void *user)
479 build = isl_ast_build_cow(build);
481 if (!build)
482 return NULL;
484 build->create_leaf = fn;
485 build->create_leaf_user = user;
487 return build;
490 /* Clear all information that is specific to this code generation
491 * and that is (probably) not meaningful to any nested code generation.
493 __isl_give isl_ast_build *isl_ast_build_clear_local_info(
494 __isl_take isl_ast_build *build)
496 isl_space *space;
498 build = isl_ast_build_cow(build);
499 if (!build)
500 return NULL;
502 space = isl_union_map_get_space(build->options);
503 isl_union_map_free(build->options);
504 build->options = isl_union_map_empty(space);
506 build->at_each_domain = NULL;
507 build->at_each_domain_user = NULL;
508 build->before_each_for = NULL;
509 build->before_each_for_user = NULL;
510 build->after_each_for = NULL;
511 build->after_each_for_user = NULL;
512 build->before_each_mark = NULL;
513 build->before_each_mark_user = NULL;
514 build->after_each_mark = NULL;
515 build->after_each_mark_user = NULL;
516 build->create_leaf = NULL;
517 build->create_leaf_user = NULL;
519 if (!build->options)
520 return isl_ast_build_free(build);
522 return build;
525 /* Have any loops been eliminated?
526 * That is, do any of the original schedule dimensions have a fixed
527 * value that has been substituted?
529 static int any_eliminated(isl_ast_build *build)
531 int i;
533 for (i = 0; i < build->depth; ++i)
534 if (isl_ast_build_has_affine_value(build, i))
535 return 1;
537 return 0;
540 /* Clear build->schedule_map.
541 * This function should be called whenever anything that might affect
542 * the result of isl_ast_build_get_schedule_map_multi_aff changes.
543 * In particular, it should be called when the depth is changed or
544 * when an iterator is determined to have a fixed value.
546 static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build *build)
548 if (!build)
549 return;
550 isl_multi_aff_free(build->schedule_map);
551 build->schedule_map = NULL;
554 /* Do we need a (non-trivial) schedule map?
555 * That is, is the internal schedule space different from
556 * the external schedule space?
558 * The internal and external schedule spaces are only the same
559 * if code has been generated for the entire schedule and if none
560 * of the loops have been eliminated.
562 __isl_give int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build *build)
564 int dim;
566 if (!build)
567 return -1;
569 dim = isl_set_dim(build->domain, isl_dim_set);
570 return build->depth != dim || any_eliminated(build);
573 /* Return a mapping from the internal schedule space to the external
574 * schedule space in the form of an isl_multi_aff.
575 * The internal schedule space originally corresponds to that of the
576 * input schedule. This may change during the code generation if
577 * if isl_ast_build_insert_dim is ever called.
578 * The external schedule space corresponds to the
579 * loops that have been generated.
581 * Currently, the only difference between the internal schedule domain
582 * and the external schedule domain is that some dimensions are projected
583 * out in the external schedule domain. In particular, the dimensions
584 * for which no code has been generated yet and the dimensions that correspond
585 * to eliminated loops.
587 * We cache a copy of the schedule_map in build->schedule_map.
588 * The cache is cleared through isl_ast_build_reset_schedule_map
589 * whenever anything changes that might affect the result of this function.
591 __isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(
592 __isl_keep isl_ast_build *build)
594 isl_space *space;
595 isl_multi_aff *ma;
597 if (!build)
598 return NULL;
599 if (build->schedule_map)
600 return isl_multi_aff_copy(build->schedule_map);
602 space = isl_ast_build_get_space(build, 1);
603 space = isl_space_map_from_set(space);
604 ma = isl_multi_aff_identity(space);
605 if (isl_ast_build_need_schedule_map(build)) {
606 int i;
607 int dim = isl_set_dim(build->domain, isl_dim_set);
608 ma = isl_multi_aff_drop_dims(ma, isl_dim_out,
609 build->depth, dim - build->depth);
610 for (i = build->depth - 1; i >= 0; --i)
611 if (isl_ast_build_has_affine_value(build, i))
612 ma = isl_multi_aff_drop_dims(ma,
613 isl_dim_out, i, 1);
616 build->schedule_map = ma;
617 return isl_multi_aff_copy(build->schedule_map);
620 /* Return a mapping from the internal schedule space to the external
621 * schedule space in the form of an isl_map.
623 __isl_give isl_map *isl_ast_build_get_schedule_map(
624 __isl_keep isl_ast_build *build)
626 isl_multi_aff *ma;
628 ma = isl_ast_build_get_schedule_map_multi_aff(build);
629 return isl_map_from_multi_aff(ma);
632 /* Return the position of the dimension in build->domain for which
633 * an AST node is currently being generated.
635 int isl_ast_build_get_depth(__isl_keep isl_ast_build *build)
637 return build ? build->depth : -1;
640 /* Prepare for generating code for the next level.
641 * In particular, increase the depth and reset any information
642 * that is local to the current depth.
644 __isl_give isl_ast_build *isl_ast_build_increase_depth(
645 __isl_take isl_ast_build *build)
647 build = isl_ast_build_cow(build);
648 if (!build)
649 return NULL;
650 build->depth++;
651 isl_ast_build_reset_schedule_map(build);
652 build->value = isl_pw_aff_free(build->value);
653 return build;
656 void isl_ast_build_dump(__isl_keep isl_ast_build *build)
658 if (!build)
659 return;
661 fprintf(stderr, "domain: ");
662 isl_set_dump(build->domain);
663 fprintf(stderr, "generated: ");
664 isl_set_dump(build->generated);
665 fprintf(stderr, "pending: ");
666 isl_set_dump(build->pending);
667 fprintf(stderr, "iterators: ");
668 isl_id_list_dump(build->iterators);
669 fprintf(stderr, "values: ");
670 isl_multi_aff_dump(build->values);
671 if (build->value) {
672 fprintf(stderr, "value: ");
673 isl_pw_aff_dump(build->value);
675 fprintf(stderr, "strides: ");
676 isl_vec_dump(build->strides);
677 fprintf(stderr, "offsets: ");
678 isl_multi_aff_dump(build->offsets);
679 fprintf(stderr, "internal2input: ");
680 isl_multi_aff_dump(build->internal2input);
683 /* Initialize "build" for AST construction in schedule space "space"
684 * in the case that build->domain is a parameter set.
686 * build->iterators is assumed to have been updated already.
688 static __isl_give isl_ast_build *isl_ast_build_init(
689 __isl_take isl_ast_build *build, __isl_take isl_space *space)
691 isl_set *set;
693 build = isl_ast_build_cow(build);
694 if (!build)
695 goto error;
697 set = isl_set_universe(isl_space_copy(space));
698 build->domain = isl_set_intersect_params(isl_set_copy(set),
699 build->domain);
700 build->pending = isl_set_intersect_params(isl_set_copy(set),
701 build->pending);
702 build->generated = isl_set_intersect_params(set, build->generated);
704 return isl_ast_build_init_derived(build, space);
705 error:
706 isl_ast_build_free(build);
707 isl_space_free(space);
708 return NULL;
711 /* Assign "aff" to *user and return -1, effectively extracting
712 * the first (and presumably only) affine expression in the isl_pw_aff
713 * on which this function is used.
715 static isl_stat extract_single_piece(__isl_take isl_set *set,
716 __isl_take isl_aff *aff, void *user)
718 isl_aff **p = user;
720 *p = aff;
721 isl_set_free(set);
723 return isl_stat_error;
726 /* Intersect "set" with the stride constraint of "build", if any.
728 static __isl_give isl_set *intersect_stride_constraint(__isl_take isl_set *set,
729 __isl_keep isl_ast_build *build)
731 isl_set *stride;
733 if (!build)
734 return isl_set_free(set);
735 if (!isl_ast_build_has_stride(build, build->depth))
736 return set;
738 stride = isl_ast_build_get_stride_constraint(build);
739 return isl_set_intersect(set, stride);
742 /* Check if the given bounds on the current dimension (together with
743 * the stride constraint, if any) imply that
744 * this current dimension attains only a single value (in terms of
745 * parameters and outer dimensions).
746 * If so, we record it in build->value.
747 * If, moreover, this value can be represented as a single affine expression,
748 * then we also update build->values, effectively marking the current
749 * dimension as "eliminated".
751 * When computing the gist of the fixed value that can be represented
752 * as a single affine expression, it is important to only take into
753 * account the domain constraints in the original AST build and
754 * not the domain of the affine expression itself.
755 * Otherwise, a [i/3] is changed into a i/3 because we know that i
756 * is a multiple of 3, but then we end up not expressing anywhere
757 * in the context that i is a multiple of 3.
759 static __isl_give isl_ast_build *update_values(
760 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
762 int sv;
763 isl_pw_multi_aff *pma;
764 isl_aff *aff = NULL;
765 isl_map *it_map;
766 isl_set *set;
768 set = isl_set_from_basic_set(bounds);
769 set = isl_set_intersect(set, isl_set_copy(build->domain));
770 set = intersect_stride_constraint(set, build);
771 it_map = isl_ast_build_map_to_iterator(build, set);
773 sv = isl_map_is_single_valued(it_map);
774 if (sv < 0)
775 build = isl_ast_build_free(build);
776 if (!build || !sv) {
777 isl_map_free(it_map);
778 return build;
781 pma = isl_pw_multi_aff_from_map(it_map);
782 build->value = isl_pw_multi_aff_get_pw_aff(pma, 0);
783 build->value = isl_ast_build_compute_gist_pw_aff(build, build->value);
784 build->value = isl_pw_aff_coalesce(build->value);
785 isl_pw_multi_aff_free(pma);
787 if (!build->value)
788 return isl_ast_build_free(build);
790 if (isl_pw_aff_n_piece(build->value) != 1)
791 return build;
793 isl_pw_aff_foreach_piece(build->value, &extract_single_piece, &aff);
795 build->values = isl_multi_aff_set_aff(build->values, build->depth, aff);
796 if (!build->values)
797 return isl_ast_build_free(build);
798 isl_ast_build_reset_schedule_map(build);
799 return build;
802 /* Update the AST build based on the given loop bounds for
803 * the current dimension and the stride information available in the build.
805 * We first make sure that the bounds do not refer to any iterators
806 * that have already been eliminated.
807 * Then, we check if the bounds imply that the current iterator
808 * has a fixed value.
809 * If they do and if this fixed value can be expressed as a single
810 * affine expression, we eliminate the iterators from the bounds.
811 * Note that we cannot simply plug in this single value using
812 * isl_basic_set_preimage_multi_aff as the single value may only
813 * be defined on a subset of the domain. Plugging in the value
814 * would restrict the build domain to this subset, while this
815 * restriction may not be reflected in the generated code.
816 * Finally, we intersect build->domain with the updated bounds.
817 * We also add the stride constraint unless we have been able
818 * to find a fixed value expressed as a single affine expression.
820 * Note that the check for a fixed value in update_values requires
821 * us to intersect the bounds with the current build domain.
822 * When we intersect build->domain with the updated bounds in
823 * the final step, we make sure that these updated bounds have
824 * not been intersected with the old build->domain.
825 * Otherwise, we would indirectly intersect the build domain with itself,
826 * which can lead to inefficiencies, in particular if the build domain
827 * contains any unknown divs.
829 * The pending and generated sets are not updated by this function to
830 * match the updated domain.
831 * The caller still needs to call isl_ast_build_set_pending_generated.
833 __isl_give isl_ast_build *isl_ast_build_set_loop_bounds(
834 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
836 isl_set *set;
838 build = isl_ast_build_cow(build);
839 if (!build)
840 goto error;
842 build = update_values(build, isl_basic_set_copy(bounds));
843 if (!build)
844 goto error;
845 set = isl_set_from_basic_set(bounds);
846 if (isl_ast_build_has_affine_value(build, build->depth)) {
847 set = isl_set_eliminate(set, isl_dim_set, build->depth, 1);
848 set = isl_set_compute_divs(set);
849 build->pending = isl_set_intersect(build->pending,
850 isl_set_copy(set));
851 build->domain = isl_set_intersect(build->domain, set);
852 } else {
853 build->domain = isl_set_intersect(build->domain, set);
854 build = isl_ast_build_include_stride(build);
855 if (!build)
856 goto error;
859 if (!build->domain || !build->pending || !build->generated)
860 return isl_ast_build_free(build);
862 return build;
863 error:
864 isl_ast_build_free(build);
865 isl_basic_set_free(bounds);
866 return NULL;
869 /* Update the pending and generated sets of "build" according to "bounds".
870 * If the build has an affine value at the current depth,
871 * then isl_ast_build_set_loop_bounds has already set the pending set.
872 * Otherwise, do it here.
874 __isl_give isl_ast_build *isl_ast_build_set_pending_generated(
875 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
877 isl_basic_set *generated, *pending;
879 if (!build)
880 goto error;
882 if (isl_ast_build_has_affine_value(build, build->depth)) {
883 isl_basic_set_free(bounds);
884 return build;
887 build = isl_ast_build_cow(build);
888 if (!build)
889 goto error;
891 pending = isl_basic_set_copy(bounds);
892 pending = isl_basic_set_drop_constraints_involving_dims(pending,
893 isl_dim_set, build->depth, 1);
894 build->pending = isl_set_intersect(build->pending,
895 isl_set_from_basic_set(pending));
896 generated = bounds;
897 generated = isl_basic_set_drop_constraints_not_involving_dims(
898 generated, isl_dim_set, build->depth, 1);
899 build->generated = isl_set_intersect(build->generated,
900 isl_set_from_basic_set(generated));
902 if (!build->pending || !build->generated)
903 return isl_ast_build_free(build);
905 return build;
906 error:
907 isl_ast_build_free(build);
908 isl_basic_set_free(bounds);
909 return NULL;
912 /* Intersect build->domain with "set", where "set" is specified
913 * in terms of the internal schedule domain.
915 static __isl_give isl_ast_build *isl_ast_build_restrict_internal(
916 __isl_take isl_ast_build *build, __isl_take isl_set *set)
918 build = isl_ast_build_cow(build);
919 if (!build)
920 goto error;
922 set = isl_set_compute_divs(set);
923 build->domain = isl_set_intersect(build->domain, set);
924 build->domain = isl_set_coalesce(build->domain);
926 if (!build->domain)
927 return isl_ast_build_free(build);
929 return build;
930 error:
931 isl_ast_build_free(build);
932 isl_set_free(set);
933 return NULL;
936 /* Intersect build->generated and build->domain with "set",
937 * where "set" is specified in terms of the internal schedule domain.
939 __isl_give isl_ast_build *isl_ast_build_restrict_generated(
940 __isl_take isl_ast_build *build, __isl_take isl_set *set)
942 set = isl_set_compute_divs(set);
943 build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
944 build = isl_ast_build_cow(build);
945 if (!build)
946 goto error;
948 build->generated = isl_set_intersect(build->generated, set);
949 build->generated = isl_set_coalesce(build->generated);
951 if (!build->generated)
952 return isl_ast_build_free(build);
954 return build;
955 error:
956 isl_ast_build_free(build);
957 isl_set_free(set);
958 return NULL;
961 /* Replace the set of pending constraints by "guard", which is then
962 * no longer considered as pending.
963 * That is, add "guard" to the generated constraints and clear all pending
964 * constraints, making the domain equal to the generated constraints.
966 __isl_give isl_ast_build *isl_ast_build_replace_pending_by_guard(
967 __isl_take isl_ast_build *build, __isl_take isl_set *guard)
969 build = isl_ast_build_restrict_generated(build, guard);
970 build = isl_ast_build_cow(build);
971 if (!build)
972 return NULL;
974 isl_set_free(build->domain);
975 build->domain = isl_set_copy(build->generated);
976 isl_set_free(build->pending);
977 build->pending = isl_set_universe(isl_set_get_space(build->domain));
979 if (!build->pending)
980 return isl_ast_build_free(build);
982 return build;
985 /* Intersect build->pending and build->domain with "set",
986 * where "set" is specified in terms of the internal schedule domain.
988 __isl_give isl_ast_build *isl_ast_build_restrict_pending(
989 __isl_take isl_ast_build *build, __isl_take isl_set *set)
991 set = isl_set_compute_divs(set);
992 build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
993 build = isl_ast_build_cow(build);
994 if (!build)
995 goto error;
997 build->pending = isl_set_intersect(build->pending, set);
998 build->pending = isl_set_coalesce(build->pending);
1000 if (!build->pending)
1001 return isl_ast_build_free(build);
1003 return build;
1004 error:
1005 isl_ast_build_free(build);
1006 isl_set_free(set);
1007 return NULL;
1010 /* Intersect build->domain with "set", where "set" is specified
1011 * in terms of the external schedule domain.
1013 __isl_give isl_ast_build *isl_ast_build_restrict(
1014 __isl_take isl_ast_build *build, __isl_take isl_set *set)
1016 if (isl_set_is_params(set))
1017 return isl_ast_build_restrict_generated(build, set);
1019 if (isl_ast_build_need_schedule_map(build)) {
1020 isl_multi_aff *ma;
1021 ma = isl_ast_build_get_schedule_map_multi_aff(build);
1022 set = isl_set_preimage_multi_aff(set, ma);
1024 return isl_ast_build_restrict_generated(build, set);
1027 /* Replace build->executed by "executed".
1029 __isl_give isl_ast_build *isl_ast_build_set_executed(
1030 __isl_take isl_ast_build *build, __isl_take isl_union_map *executed)
1032 build = isl_ast_build_cow(build);
1033 if (!build)
1034 goto error;
1036 isl_union_map_free(build->executed);
1037 build->executed = executed;
1039 return build;
1040 error:
1041 isl_ast_build_free(build);
1042 isl_union_map_free(executed);
1043 return NULL;
1046 /* Does "build" point to a band node?
1047 * That is, are we currently handling a band node inside a schedule tree?
1049 int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build *build)
1051 if (!build)
1052 return -1;
1053 return build->node != NULL;
1056 /* Return a copy of the band node that "build" refers to.
1058 __isl_give isl_schedule_node *isl_ast_build_get_schedule_node(
1059 __isl_keep isl_ast_build *build)
1061 if (!build)
1062 return NULL;
1063 return isl_schedule_node_copy(build->node);
1066 /* Extract the loop AST generation types for the members of build->node
1067 * and store them in build->loop_type.
1069 static __isl_give isl_ast_build *extract_loop_types(
1070 __isl_take isl_ast_build *build)
1072 int i;
1073 isl_ctx *ctx;
1074 isl_schedule_node *node;
1076 if (!build)
1077 return NULL;
1078 ctx = isl_ast_build_get_ctx(build);
1079 if (!build->node)
1080 isl_die(ctx, isl_error_internal, "missing AST node",
1081 return isl_ast_build_free(build));
1083 free(build->loop_type);
1084 build->n = isl_schedule_node_band_n_member(build->node);
1085 build->loop_type = isl_alloc_array(ctx,
1086 enum isl_ast_loop_type, build->n);
1087 if (build->n && !build->loop_type)
1088 return isl_ast_build_free(build);
1089 node = build->node;
1090 for (i = 0; i < build->n; ++i)
1091 build->loop_type[i] =
1092 isl_schedule_node_band_member_get_ast_loop_type(node, i);
1094 return build;
1097 /* Replace the band node that "build" refers to by "node" and
1098 * extract the corresponding loop AST generation types.
1100 __isl_give isl_ast_build *isl_ast_build_set_schedule_node(
1101 __isl_take isl_ast_build *build,
1102 __isl_take isl_schedule_node *node)
1104 build = isl_ast_build_cow(build);
1105 if (!build || !node)
1106 goto error;
1108 isl_schedule_node_free(build->node);
1109 build->node = node;
1111 build = extract_loop_types(build);
1113 return build;
1114 error:
1115 isl_ast_build_free(build);
1116 isl_schedule_node_free(node);
1117 return NULL;
1120 /* Remove any reference to a band node from "build".
1122 __isl_give isl_ast_build *isl_ast_build_reset_schedule_node(
1123 __isl_take isl_ast_build *build)
1125 build = isl_ast_build_cow(build);
1126 if (!build)
1127 return NULL;
1129 isl_schedule_node_free(build->node);
1130 build->node = NULL;
1132 return build;
1135 /* Return a copy of the current schedule domain.
1137 __isl_give isl_set *isl_ast_build_get_domain(__isl_keep isl_ast_build *build)
1139 return build ? isl_set_copy(build->domain) : NULL;
1142 /* Return a copy of the set of pending constraints.
1144 __isl_give isl_set *isl_ast_build_get_pending(
1145 __isl_keep isl_ast_build *build)
1147 return build ? isl_set_copy(build->pending) : NULL;
1150 /* Return a copy of the set of generated constraints.
1152 __isl_give isl_set *isl_ast_build_get_generated(
1153 __isl_keep isl_ast_build *build)
1155 return build ? isl_set_copy(build->generated) : NULL;
1158 /* Return a copy of the map from the internal schedule domain
1159 * to the original input schedule domain.
1161 __isl_give isl_multi_aff *isl_ast_build_get_internal2input(
1162 __isl_keep isl_ast_build *build)
1164 return build ? isl_multi_aff_copy(build->internal2input) : NULL;
1167 /* Return the number of variables of the given type
1168 * in the (internal) schedule space.
1170 unsigned isl_ast_build_dim(__isl_keep isl_ast_build *build,
1171 enum isl_dim_type type)
1173 if (!build)
1174 return 0;
1175 return isl_set_dim(build->domain, type);
1178 /* Return the (schedule) space of "build".
1180 * If "internal" is set, then this space is the space of the internal
1181 * representation of the entire schedule, including those parts for
1182 * which no code has been generated yet.
1184 * If "internal" is not set, then this space is the external representation
1185 * of the loops generated so far.
1187 __isl_give isl_space *isl_ast_build_get_space(__isl_keep isl_ast_build *build,
1188 int internal)
1190 int i;
1191 int dim;
1192 isl_space *space;
1194 if (!build)
1195 return NULL;
1197 space = isl_set_get_space(build->domain);
1198 if (internal)
1199 return space;
1201 if (!isl_ast_build_need_schedule_map(build))
1202 return space;
1204 dim = isl_set_dim(build->domain, isl_dim_set);
1205 space = isl_space_drop_dims(space, isl_dim_set,
1206 build->depth, dim - build->depth);
1207 for (i = build->depth - 1; i >= 0; --i)
1208 if (isl_ast_build_has_affine_value(build, i))
1209 space = isl_space_drop_dims(space, isl_dim_set, i, 1);
1211 return space;
1214 /* Return the external representation of the schedule space of "build",
1215 * i.e., a space with a dimension for each loop generated so far,
1216 * with the names of the dimensions set to the loop iterators.
1218 __isl_give isl_space *isl_ast_build_get_schedule_space(
1219 __isl_keep isl_ast_build *build)
1221 isl_space *space;
1222 int i, skip;
1224 if (!build)
1225 return NULL;
1227 space = isl_ast_build_get_space(build, 0);
1229 skip = 0;
1230 for (i = 0; i < build->depth; ++i) {
1231 isl_id *id;
1233 if (isl_ast_build_has_affine_value(build, i)) {
1234 skip++;
1235 continue;
1238 id = isl_ast_build_get_iterator_id(build, i);
1239 space = isl_space_set_dim_id(space, isl_dim_set, i - skip, id);
1242 return space;
1245 /* Return the current schedule, as stored in build->executed, in terms
1246 * of the external schedule domain.
1248 __isl_give isl_union_map *isl_ast_build_get_schedule(
1249 __isl_keep isl_ast_build *build)
1251 isl_union_map *executed;
1252 isl_union_map *schedule;
1254 if (!build)
1255 return NULL;
1257 executed = isl_union_map_copy(build->executed);
1258 if (isl_ast_build_need_schedule_map(build)) {
1259 isl_map *proj = isl_ast_build_get_schedule_map(build);
1260 executed = isl_union_map_apply_domain(executed,
1261 isl_union_map_from_map(proj));
1263 schedule = isl_union_map_reverse(executed);
1265 return schedule;
1268 /* Return the iterator attached to the internal schedule dimension "pos".
1270 __isl_give isl_id *isl_ast_build_get_iterator_id(
1271 __isl_keep isl_ast_build *build, int pos)
1273 if (!build)
1274 return NULL;
1276 return isl_id_list_get_id(build->iterators, pos);
1279 /* Set the stride and offset of the current dimension to the given
1280 * value and expression.
1282 * If we had already found a stride before, then the two strides
1283 * are combined into a single stride.
1285 * In particular, if the new stride information is of the form
1287 * i = f + s (...)
1289 * and the old stride information is of the form
1291 * i = f2 + s2 (...)
1293 * then we compute the extended gcd of s and s2
1295 * a s + b s2 = g,
1297 * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
1298 * and the second with t2 = a s1/g.
1299 * This results in
1301 * i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
1303 * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
1304 * is the combined stride.
1306 static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build,
1307 __isl_take isl_val *stride, __isl_take isl_aff *offset)
1309 int pos;
1311 build = isl_ast_build_cow(build);
1312 if (!build || !stride || !offset)
1313 goto error;
1315 pos = build->depth;
1317 if (isl_ast_build_has_stride(build, pos)) {
1318 isl_val *stride2, *a, *b, *g;
1319 isl_aff *offset2;
1321 stride2 = isl_vec_get_element_val(build->strides, pos);
1322 g = isl_val_gcdext(isl_val_copy(stride), isl_val_copy(stride2),
1323 &a, &b);
1324 a = isl_val_mul(a, isl_val_copy(stride));
1325 a = isl_val_div(a, isl_val_copy(g));
1326 stride2 = isl_val_div(stride2, g);
1327 b = isl_val_mul(b, isl_val_copy(stride2));
1328 stride = isl_val_mul(stride, stride2);
1330 offset2 = isl_multi_aff_get_aff(build->offsets, pos);
1331 offset2 = isl_aff_scale_val(offset2, a);
1332 offset = isl_aff_scale_val(offset, b);
1333 offset = isl_aff_add(offset, offset2);
1336 build->strides = isl_vec_set_element_val(build->strides, pos, stride);
1337 build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset);
1338 if (!build->strides || !build->offsets)
1339 return isl_ast_build_free(build);
1341 return build;
1342 error:
1343 isl_val_free(stride);
1344 isl_aff_free(offset);
1345 return isl_ast_build_free(build);
1348 /* Return a set expressing the stride constraint at the current depth.
1350 * In particular, if the current iterator (i) is known to attain values
1352 * f + s a
1354 * where f is the offset and s is the stride, then the returned set
1355 * expresses the constraint
1357 * (f - i) mod s = 0
1359 __isl_give isl_set *isl_ast_build_get_stride_constraint(
1360 __isl_keep isl_ast_build *build)
1362 isl_aff *aff;
1363 isl_set *set;
1364 isl_val *stride;
1365 int pos;
1367 if (!build)
1368 return NULL;
1370 pos = build->depth;
1372 if (!isl_ast_build_has_stride(build, pos))
1373 return isl_set_universe(isl_ast_build_get_space(build, 1));
1375 stride = isl_ast_build_get_stride(build, pos);
1376 aff = isl_ast_build_get_offset(build, pos);
1377 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1);
1378 aff = isl_aff_mod_val(aff, stride);
1379 set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff));
1381 return set;
1384 /* Return the expansion implied by the stride and offset at the current
1385 * depth.
1387 * That is, return the mapping
1389 * [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1390 * -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]
1392 * where s is the stride at the current depth d and offset(i) is
1393 * the corresponding offset.
1395 __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
1396 __isl_keep isl_ast_build *build)
1398 isl_space *space;
1399 isl_multi_aff *ma;
1400 int pos;
1401 isl_aff *aff, *offset;
1402 isl_val *stride;
1404 if (!build)
1405 return NULL;
1407 pos = isl_ast_build_get_depth(build);
1408 space = isl_ast_build_get_space(build, 1);
1409 space = isl_space_map_from_set(space);
1410 ma = isl_multi_aff_identity(space);
1412 if (!isl_ast_build_has_stride(build, pos))
1413 return ma;
1415 offset = isl_ast_build_get_offset(build, pos);
1416 stride = isl_ast_build_get_stride(build, pos);
1417 aff = isl_multi_aff_get_aff(ma, pos);
1418 aff = isl_aff_scale_val(aff, stride);
1419 aff = isl_aff_add(aff, offset);
1420 ma = isl_multi_aff_set_aff(ma, pos, aff);
1422 return ma;
1425 /* Add constraints corresponding to any previously detected
1426 * stride on the current dimension to build->domain.
1428 __isl_give isl_ast_build *isl_ast_build_include_stride(
1429 __isl_take isl_ast_build *build)
1431 isl_set *set;
1433 if (!build)
1434 return NULL;
1435 if (!isl_ast_build_has_stride(build, build->depth))
1436 return build;
1437 build = isl_ast_build_cow(build);
1438 if (!build)
1439 return NULL;
1441 set = isl_ast_build_get_stride_constraint(build);
1443 build->domain = isl_set_intersect(build->domain, isl_set_copy(set));
1444 build->generated = isl_set_intersect(build->generated, set);
1445 if (!build->domain || !build->generated)
1446 return isl_ast_build_free(build);
1448 return build;
1451 /* Information used inside detect_stride.
1453 * "build" may be updated by detect_stride to include stride information.
1454 * "pos" is equal to build->depth.
1456 struct isl_detect_stride_data {
1457 isl_ast_build *build;
1458 int pos;
1461 /* Check if constraint "c" imposes any stride on dimension data->pos
1462 * and, if so, update the stride information in data->build.
1464 * In order to impose a stride on the dimension, "c" needs to be an equality
1465 * and it needs to involve the dimension. Note that "c" may also be
1466 * a div constraint and thus an inequality that we cannot use.
1468 * Let c be of the form
1470 * h(p) + g * v * i + g * stride * f(alpha) = 0
1472 * with h(p) an expression in terms of the parameters and outer dimensions
1473 * and f(alpha) an expression in terms of the existentially quantified
1474 * variables. Note that the inner dimensions have been eliminated so
1475 * they do not appear in "c".
1477 * If "stride" is not zero and not one, then it represents a non-trivial stride
1478 * on "i". We compute a and b such that
1480 * a v + b stride = 1
1482 * We have
1484 * g v i = -h(p) + g stride f(alpha)
1486 * a g v i = -a h(p) + g stride f(alpha)
1488 * a g v i + b g stride i = -a h(p) + g stride * (...)
1490 * g i = -a h(p) + g stride * (...)
1492 * i = -a h(p)/g + stride * (...)
1494 * The expression "-a h(p)/g" can therefore be used as offset.
1496 static isl_stat detect_stride(__isl_take isl_constraint *c, void *user)
1498 struct isl_detect_stride_data *data = user;
1499 int i, n_div;
1500 isl_ctx *ctx;
1501 isl_val *v, *stride, *m;
1503 if (!isl_constraint_is_equality(c) ||
1504 !isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1)) {
1505 isl_constraint_free(c);
1506 return isl_stat_ok;
1509 ctx = isl_constraint_get_ctx(c);
1510 stride = isl_val_zero(ctx);
1511 n_div = isl_constraint_dim(c, isl_dim_div);
1512 for (i = 0; i < n_div; ++i) {
1513 v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
1514 stride = isl_val_gcd(stride, v);
1517 v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
1518 m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
1519 stride = isl_val_div(stride, isl_val_copy(m));
1520 v = isl_val_div(v, isl_val_copy(m));
1522 if (!isl_val_is_zero(stride) && !isl_val_is_one(stride)) {
1523 isl_aff *aff;
1524 isl_val *gcd, *a, *b;
1526 gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);
1527 isl_val_free(gcd);
1528 isl_val_free(b);
1530 aff = isl_constraint_get_aff(c);
1531 for (i = 0; i < n_div; ++i)
1532 aff = isl_aff_set_coefficient_si(aff,
1533 isl_dim_div, i, 0);
1534 aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
1535 a = isl_val_neg(a);
1536 aff = isl_aff_scale_val(aff, a);
1537 aff = isl_aff_scale_down_val(aff, m);
1538 data->build = set_stride(data->build, stride, aff);
1539 } else {
1540 isl_val_free(stride);
1541 isl_val_free(m);
1542 isl_val_free(v);
1545 isl_constraint_free(c);
1546 return isl_stat_ok;
1549 /* Check if the constraints in "set" imply any stride on the current
1550 * dimension and, if so, record the stride information in "build"
1551 * and return the updated "build".
1553 * We compute the affine hull and then check if any of the constraints
1554 * in the hull imposes any stride on the current dimension.
1556 * We assume that inner dimensions have been eliminated from "set"
1557 * by the caller. This is needed because the common stride
1558 * may be imposed by different inner dimensions on different parts of
1559 * the domain.
1561 __isl_give isl_ast_build *isl_ast_build_detect_strides(
1562 __isl_take isl_ast_build *build, __isl_take isl_set *set)
1564 isl_basic_set *hull;
1565 struct isl_detect_stride_data data;
1567 if (!build)
1568 goto error;
1570 data.build = build;
1571 data.pos = isl_ast_build_get_depth(build);
1572 hull = isl_set_affine_hull(set);
1574 if (isl_basic_set_foreach_constraint(hull, &detect_stride, &data) < 0)
1575 data.build = isl_ast_build_free(data.build);
1577 isl_basic_set_free(hull);
1578 return data.build;
1579 error:
1580 isl_set_free(set);
1581 return NULL;
1584 struct isl_ast_build_involves_data {
1585 int depth;
1586 int involves;
1589 /* Check if "map" involves the input dimension data->depth.
1591 static isl_stat involves_depth(__isl_take isl_map *map, void *user)
1593 struct isl_ast_build_involves_data *data = user;
1595 data->involves = isl_map_involves_dims(map, isl_dim_in, data->depth, 1);
1596 isl_map_free(map);
1598 if (data->involves < 0 || data->involves)
1599 return isl_stat_error;
1600 return isl_stat_ok;
1603 /* Do any options depend on the value of the dimension at the current depth?
1605 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build)
1607 struct isl_ast_build_involves_data data;
1609 if (!build)
1610 return -1;
1612 data.depth = build->depth;
1613 data.involves = 0;
1615 if (isl_union_map_foreach_map(build->options,
1616 &involves_depth, &data) < 0) {
1617 if (data.involves < 0 || !data.involves)
1618 return -1;
1621 return data.involves;
1624 /* Construct the map
1626 * { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1628 * with "space" the parameter space of the constructed map.
1630 static __isl_give isl_map *construct_insertion_map(__isl_take isl_space *space,
1631 int pos)
1633 isl_constraint *c;
1634 isl_basic_map *bmap1, *bmap2;
1636 space = isl_space_set_from_params(space);
1637 space = isl_space_add_dims(space, isl_dim_set, 1);
1638 space = isl_space_map_from_set(space);
1639 c = isl_constraint_alloc_equality(isl_local_space_from_space(space));
1640 c = isl_constraint_set_coefficient_si(c, isl_dim_in, 0, 1);
1641 c = isl_constraint_set_coefficient_si(c, isl_dim_out, 0, -1);
1642 bmap1 = isl_basic_map_from_constraint(isl_constraint_copy(c));
1643 c = isl_constraint_set_constant_si(c, 1);
1644 bmap2 = isl_basic_map_from_constraint(c);
1646 bmap1 = isl_basic_map_upper_bound_si(bmap1, isl_dim_in, 0, pos - 1);
1647 bmap2 = isl_basic_map_lower_bound_si(bmap2, isl_dim_in, 0, pos);
1649 return isl_basic_map_union(bmap1, bmap2);
1652 static const char *option_str[] = {
1653 [isl_ast_loop_atomic] = "atomic",
1654 [isl_ast_loop_unroll] = "unroll",
1655 [isl_ast_loop_separate] = "separate"
1658 /* Update the "options" to reflect the insertion of a dimension
1659 * at position "pos" in the schedule domain space.
1660 * "space" is the original domain space before the insertion and
1661 * may be named and/or structured.
1663 * The (relevant) input options all have "space" as domain, which
1664 * has to be mapped to the extended space.
1665 * The values of the ranges also refer to the schedule domain positions
1666 * and they therefore also need to be adjusted. In particular, values
1667 * smaller than pos do not need to change, while values greater than or
1668 * equal to pos need to be incremented.
1669 * That is, we need to apply the following map.
1671 * { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1672 * unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1673 * separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1674 * separation_class[[i] -> [c]]
1675 * -> separation_class[[i] -> [c]] : i < pos;
1676 * separation_class[[i] -> [c]]
1677 * -> separation_class[[i + 1] -> [c]] : i >= pos }
1679 static __isl_give isl_union_map *options_insert_dim(
1680 __isl_take isl_union_map *options, __isl_take isl_space *space, int pos)
1682 isl_map *map;
1683 isl_union_map *insertion;
1684 enum isl_ast_loop_type type;
1685 const char *name = "separation_class";
1687 space = isl_space_map_from_set(space);
1688 map = isl_map_identity(space);
1689 map = isl_map_insert_dims(map, isl_dim_out, pos, 1);
1690 options = isl_union_map_apply_domain(options,
1691 isl_union_map_from_map(map));
1693 if (!options)
1694 return NULL;
1696 map = construct_insertion_map(isl_union_map_get_space(options), pos);
1698 insertion = isl_union_map_empty(isl_union_map_get_space(options));
1700 for (type = isl_ast_loop_atomic;
1701 type <= isl_ast_loop_separate; ++type) {
1702 isl_map *map_type = isl_map_copy(map);
1703 const char *name = option_str[type];
1704 map_type = isl_map_set_tuple_name(map_type, isl_dim_in, name);
1705 map_type = isl_map_set_tuple_name(map_type, isl_dim_out, name);
1706 insertion = isl_union_map_add_map(insertion, map_type);
1709 map = isl_map_product(map, isl_map_identity(isl_map_get_space(map)));
1710 map = isl_map_set_tuple_name(map, isl_dim_in, name);
1711 map = isl_map_set_tuple_name(map, isl_dim_out, name);
1712 insertion = isl_union_map_add_map(insertion, map);
1714 options = isl_union_map_apply_range(options, insertion);
1716 return options;
1719 /* If we are generating an AST from a schedule tree (build->node is set),
1720 * then update the loop AST generation types
1721 * to reflect the insertion of a dimension at (global) position "pos"
1722 * in the schedule domain space.
1723 * We do not need to adjust any isolate option since we would not be inserting
1724 * any dimensions if there were any isolate option.
1726 static __isl_give isl_ast_build *node_insert_dim(
1727 __isl_take isl_ast_build *build, int pos)
1729 int i;
1730 int local_pos;
1731 enum isl_ast_loop_type *loop_type;
1732 isl_ctx *ctx;
1734 build = isl_ast_build_cow(build);
1735 if (!build)
1736 return NULL;
1737 if (!build->node)
1738 return build;
1740 ctx = isl_ast_build_get_ctx(build);
1741 local_pos = pos - build->outer_pos;
1742 loop_type = isl_realloc_array(ctx, build->loop_type,
1743 enum isl_ast_loop_type, build->n + 1);
1744 if (!loop_type)
1745 return isl_ast_build_free(build);
1746 build->loop_type = loop_type;
1747 for (i = build->n - 1; i >= local_pos; --i)
1748 loop_type[i + 1] = loop_type[i];
1749 loop_type[local_pos] = isl_ast_loop_default;
1750 build->n++;
1752 return build;
1755 /* Insert a single dimension in the schedule domain at position "pos".
1756 * The new dimension is given an isl_id with the empty string as name.
1758 * The main difficulty is updating build->options to reflect the
1759 * extra dimension. This is handled in options_insert_dim.
1761 * Note that because of the dimension manipulations, the resulting
1762 * schedule domain space will always be unnamed and unstructured.
1763 * However, the original schedule domain space may be named and/or
1764 * structured, so we have to take this possibility into account
1765 * while performing the transformations.
1767 * Since the inserted schedule dimension is used by the caller
1768 * to differentiate between different domain spaces, there is
1769 * no longer a uniform mapping from the internal schedule space
1770 * to the input schedule space. The internal2input mapping is
1771 * therefore removed.
1773 __isl_give isl_ast_build *isl_ast_build_insert_dim(
1774 __isl_take isl_ast_build *build, int pos)
1776 isl_ctx *ctx;
1777 isl_space *space, *ma_space;
1778 isl_id *id;
1779 isl_multi_aff *ma;
1781 build = isl_ast_build_cow(build);
1782 if (!build)
1783 return NULL;
1785 ctx = isl_ast_build_get_ctx(build);
1786 id = isl_id_alloc(ctx, "", NULL);
1787 if (!build->node)
1788 space = isl_ast_build_get_space(build, 1);
1789 build->iterators = isl_id_list_insert(build->iterators, pos, id);
1790 build->domain = isl_set_insert_dims(build->domain,
1791 isl_dim_set, pos, 1);
1792 build->generated = isl_set_insert_dims(build->generated,
1793 isl_dim_set, pos, 1);
1794 build->pending = isl_set_insert_dims(build->pending,
1795 isl_dim_set, pos, 1);
1796 build->strides = isl_vec_insert_els(build->strides, pos, 1);
1797 build->strides = isl_vec_set_element_si(build->strides, pos, 1);
1798 ma_space = isl_space_params(isl_multi_aff_get_space(build->offsets));
1799 ma_space = isl_space_set_from_params(ma_space);
1800 ma_space = isl_space_add_dims(ma_space, isl_dim_set, 1);
1801 ma_space = isl_space_map_from_set(ma_space);
1802 ma = isl_multi_aff_zero(isl_space_copy(ma_space));
1803 build->offsets = isl_multi_aff_splice(build->offsets, pos, pos, ma);
1804 ma = isl_multi_aff_identity(ma_space);
1805 build->values = isl_multi_aff_splice(build->values, pos, pos, ma);
1806 if (!build->node)
1807 build->options = options_insert_dim(build->options, space, pos);
1808 build->internal2input = isl_multi_aff_free(build->internal2input);
1810 if (!build->iterators || !build->domain || !build->generated ||
1811 !build->pending || !build->values ||
1812 !build->strides || !build->offsets || !build->options)
1813 return isl_ast_build_free(build);
1815 build = node_insert_dim(build, pos);
1817 return build;
1820 /* Scale down the current dimension by a factor of "m".
1821 * "umap" is an isl_union_map that implements the scaling down.
1822 * That is, it is of the form
1824 * { [.... i ....] -> [.... i' ....] : i = m i' }
1826 * This function is called right after the strides have been
1827 * detected, but before any constraints on the current dimension
1828 * have been included in build->domain.
1829 * We therefore only need to update stride, offset, the options and
1830 * the mapping from internal schedule space to the original schedule
1831 * space, if we are still keeping track of such a mapping.
1832 * The latter mapping is updated by plugging in
1833 * { [... i ...] -> [... m i ... ] }.
1835 __isl_give isl_ast_build *isl_ast_build_scale_down(
1836 __isl_take isl_ast_build *build, __isl_take isl_val *m,
1837 __isl_take isl_union_map *umap)
1839 isl_aff *aff;
1840 isl_val *v;
1841 int depth;
1843 build = isl_ast_build_cow(build);
1844 if (!build || !umap || !m)
1845 goto error;
1847 depth = build->depth;
1849 if (build->internal2input) {
1850 isl_space *space;
1851 isl_multi_aff *ma;
1852 isl_aff *aff;
1854 space = isl_multi_aff_get_space(build->internal2input);
1855 space = isl_space_map_from_set(isl_space_domain(space));
1856 ma = isl_multi_aff_identity(space);
1857 aff = isl_multi_aff_get_aff(ma, depth);
1858 aff = isl_aff_scale_val(aff, isl_val_copy(m));
1859 ma = isl_multi_aff_set_aff(ma, depth, aff);
1860 build->internal2input =
1861 isl_multi_aff_pullback_multi_aff(build->internal2input, ma);
1862 if (!build->internal2input)
1863 goto error;
1866 v = isl_vec_get_element_val(build->strides, depth);
1867 v = isl_val_div(v, isl_val_copy(m));
1868 build->strides = isl_vec_set_element_val(build->strides, depth, v);
1870 aff = isl_multi_aff_get_aff(build->offsets, depth);
1871 aff = isl_aff_scale_down_val(aff, m);
1872 build->offsets = isl_multi_aff_set_aff(build->offsets, depth, aff);
1873 build->options = isl_union_map_apply_domain(build->options, umap);
1874 if (!build->strides || !build->offsets || !build->options)
1875 return isl_ast_build_free(build);
1877 return build;
1878 error:
1879 isl_val_free(m);
1880 isl_union_map_free(umap);
1881 return isl_ast_build_free(build);
1884 /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1885 * If an isl_id with such a name already appears among the parameters
1886 * in build->domain, then adjust the name to "c%d_%d".
1888 static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first,
1889 __isl_keep isl_ast_build *build)
1891 int i;
1892 isl_id_list *names;
1894 names = isl_id_list_alloc(ctx, n);
1895 for (i = 0; i < n; ++i) {
1896 isl_id *id;
1898 id = generate_name(ctx, first + i, build);
1899 names = isl_id_list_add(names, id);
1902 return names;
1905 /* Embed "options" into the given isl_ast_build space.
1907 * This function is called from within a nested call to
1908 * isl_ast_build_node_from_schedule_map.
1909 * "options" refers to the additional schedule,
1910 * while space refers to both the space of the outer isl_ast_build and
1911 * that of the additional schedule.
1912 * Specifically, space is of the form
1914 * [I -> S]
1916 * while options lives in the space(s)
1918 * S -> *
1920 * We compute
1922 * [I -> S] -> S
1924 * and compose this with options, to obtain the new options
1925 * living in the space(s)
1927 * [I -> S] -> *
1929 static __isl_give isl_union_map *embed_options(
1930 __isl_take isl_union_map *options, __isl_take isl_space *space)
1932 isl_map *map;
1934 map = isl_map_universe(isl_space_unwrap(space));
1935 map = isl_map_range_map(map);
1937 options = isl_union_map_apply_range(
1938 isl_union_map_from_map(map), options);
1940 return options;
1943 /* Update "build" for use in a (possibly nested) code generation. That is,
1944 * extend "build" from an AST build on some domain O to an AST build
1945 * on domain [O -> S], with S corresponding to "space".
1946 * If the original domain is a parameter domain, then the new domain is
1947 * simply S.
1948 * "iterators" is a list of iterators for S, but the number of elements
1949 * may be smaller or greater than the number of set dimensions of S.
1950 * If "keep_iterators" is set, then any extra ids in build->iterators
1951 * are reused for S. Otherwise, these extra ids are dropped.
1953 * We first update build->outer_pos to the current depth.
1954 * This depth is zero in case this is the outermost code generation.
1956 * We then add additional ids such that the number of iterators is at least
1957 * equal to the dimension of the new build domain.
1959 * If the original domain is parametric, then we are constructing
1960 * an isl_ast_build for the outer code generation and we pass control
1961 * to isl_ast_build_init.
1963 * Otherwise, we adjust the fields of "build" to include "space".
1965 __isl_give isl_ast_build *isl_ast_build_product(
1966 __isl_take isl_ast_build *build, __isl_take isl_space *space)
1968 isl_ctx *ctx;
1969 isl_vec *strides;
1970 isl_set *set;
1971 isl_multi_aff *embedding;
1972 int dim, n_it;
1974 build = isl_ast_build_cow(build);
1975 if (!build)
1976 goto error;
1978 build->outer_pos = build->depth;
1980 ctx = isl_ast_build_get_ctx(build);
1981 dim = isl_set_dim(build->domain, isl_dim_set);
1982 dim += isl_space_dim(space, isl_dim_set);
1983 n_it = isl_id_list_n_id(build->iterators);
1984 if (n_it < dim) {
1985 isl_id_list *l;
1986 l = generate_names(ctx, dim - n_it, n_it, build);
1987 build->iterators = isl_id_list_concat(build->iterators, l);
1990 if (isl_set_is_params(build->domain))
1991 return isl_ast_build_init(build, space);
1993 set = isl_set_universe(isl_space_copy(space));
1994 build->domain = isl_set_product(build->domain, isl_set_copy(set));
1995 build->pending = isl_set_product(build->pending, isl_set_copy(set));
1996 build->generated = isl_set_product(build->generated, set);
1998 strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
1999 strides = isl_vec_set_si(strides, 1);
2000 build->strides = isl_vec_concat(build->strides, strides);
2002 space = isl_space_map_from_set(space);
2003 build->offsets = isl_multi_aff_align_params(build->offsets,
2004 isl_space_copy(space));
2005 build->offsets = isl_multi_aff_product(build->offsets,
2006 isl_multi_aff_zero(isl_space_copy(space)));
2007 build->values = isl_multi_aff_align_params(build->values,
2008 isl_space_copy(space));
2009 embedding = isl_multi_aff_identity(space);
2010 build->values = isl_multi_aff_product(build->values,
2011 isl_multi_aff_copy(embedding));
2012 if (build->internal2input) {
2013 build->internal2input =
2014 isl_multi_aff_product(build->internal2input, embedding);
2015 build->internal2input =
2016 isl_multi_aff_flatten_range(build->internal2input);
2017 if (!build->internal2input)
2018 return isl_ast_build_free(build);
2019 } else {
2020 isl_multi_aff_free(embedding);
2023 space = isl_ast_build_get_space(build, 1);
2024 build->options = embed_options(build->options, space);
2026 if (!build->iterators || !build->domain || !build->generated ||
2027 !build->pending || !build->values ||
2028 !build->strides || !build->offsets || !build->options)
2029 return isl_ast_build_free(build);
2031 return build;
2032 error:
2033 isl_ast_build_free(build);
2034 isl_space_free(space);
2035 return NULL;
2038 /* Does "aff" only attain non-negative values over build->domain?
2039 * That is, does it not attain any negative values?
2041 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
2042 __isl_keep isl_aff *aff)
2044 isl_set *test;
2045 int empty;
2047 if (!build)
2048 return -1;
2050 aff = isl_aff_copy(aff);
2051 test = isl_set_from_basic_set(isl_aff_neg_basic_set(aff));
2052 test = isl_set_intersect(test, isl_set_copy(build->domain));
2053 empty = isl_set_is_empty(test);
2054 isl_set_free(test);
2056 return empty;
2059 /* Does the dimension at (internal) position "pos" have a non-trivial stride?
2061 int isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos)
2063 isl_val *v;
2064 int has_stride;
2066 if (!build)
2067 return -1;
2069 v = isl_vec_get_element_val(build->strides, pos);
2070 if (!v)
2071 return -1;
2072 has_stride = !isl_val_is_one(v);
2073 isl_val_free(v);
2075 return has_stride;
2078 /* Given that the dimension at position "pos" takes on values
2080 * f + s a
2082 * with a an integer, return s through *stride.
2084 __isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build,
2085 int pos)
2087 if (!build)
2088 return NULL;
2090 return isl_vec_get_element_val(build->strides, pos);
2093 /* Given that the dimension at position "pos" takes on values
2095 * f + s a
2097 * with a an integer, return f.
2099 __isl_give isl_aff *isl_ast_build_get_offset(
2100 __isl_keep isl_ast_build *build, int pos)
2102 if (!build)
2103 return NULL;
2105 return isl_multi_aff_get_aff(build->offsets, pos);
2108 /* Is the dimension at position "pos" known to attain only a single
2109 * value that, moreover, can be described by a single affine expression
2110 * in terms of the outer dimensions and parameters?
2112 * If not, then the corresponding affine expression in build->values
2113 * is set to be equal to the same input dimension.
2114 * Otherwise, it is set to the requested expression in terms of
2115 * outer dimensions and parameters.
2117 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,
2118 int pos)
2120 isl_aff *aff;
2121 int involves;
2123 if (!build)
2124 return -1;
2126 aff = isl_multi_aff_get_aff(build->values, pos);
2127 involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);
2128 isl_aff_free(aff);
2130 if (involves < 0)
2131 return -1;
2133 return !involves;
2136 /* Plug in the known values (fixed affine expressions in terms of
2137 * parameters and outer loop iterators) of all loop iterators
2138 * in the domain of "umap".
2140 * We simply precompose "umap" with build->values.
2142 __isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(
2143 __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap)
2145 isl_multi_aff *values;
2147 if (!build)
2148 return isl_union_map_free(umap);
2150 values = isl_multi_aff_copy(build->values);
2151 umap = isl_union_map_preimage_domain_multi_aff(umap, values);
2153 return umap;
2156 /* Is the current dimension known to attain only a single value?
2158 int isl_ast_build_has_value(__isl_keep isl_ast_build *build)
2160 if (!build)
2161 return -1;
2163 return build->value != NULL;
2166 /* Simplify the basic set "bset" based on what we know about
2167 * the iterators of already generated loops.
2169 * "bset" is assumed to live in the (internal) schedule domain.
2171 __isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
2172 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
2174 if (!build)
2175 goto error;
2177 bset = isl_basic_set_preimage_multi_aff(bset,
2178 isl_multi_aff_copy(build->values));
2179 bset = isl_basic_set_gist(bset,
2180 isl_set_simple_hull(isl_set_copy(build->domain)));
2182 return bset;
2183 error:
2184 isl_basic_set_free(bset);
2185 return NULL;
2188 /* Simplify the set "set" based on what we know about
2189 * the iterators of already generated loops.
2191 * "set" is assumed to live in the (internal) schedule domain.
2193 __isl_give isl_set *isl_ast_build_compute_gist(
2194 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2196 if (!build)
2197 goto error;
2199 if (!isl_set_is_params(set))
2200 set = isl_set_preimage_multi_aff(set,
2201 isl_multi_aff_copy(build->values));
2202 set = isl_set_gist(set, isl_set_copy(build->domain));
2204 return set;
2205 error:
2206 isl_set_free(set);
2207 return NULL;
2210 /* Include information about what we know about the iterators of
2211 * already generated loops to "set".
2213 * We currently only plug in the known affine values of outer loop
2214 * iterators.
2215 * In principle we could also introduce equalities or even other
2216 * constraints implied by the intersection of "set" and build->domain.
2218 __isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build,
2219 __isl_take isl_set *set)
2221 if (!build)
2222 return isl_set_free(set);
2224 return isl_set_preimage_multi_aff(set,
2225 isl_multi_aff_copy(build->values));
2228 /* Plug in the known affine values of outer loop iterators in "bset".
2230 __isl_give isl_basic_set *isl_ast_build_specialize_basic_set(
2231 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
2233 if (!build)
2234 return isl_basic_set_free(bset);
2236 return isl_basic_set_preimage_multi_aff(bset,
2237 isl_multi_aff_copy(build->values));
2240 /* Simplify the map "map" based on what we know about
2241 * the iterators of already generated loops.
2243 * The domain of "map" is assumed to live in the (internal) schedule domain.
2245 __isl_give isl_map *isl_ast_build_compute_gist_map_domain(
2246 __isl_keep isl_ast_build *build, __isl_take isl_map *map)
2248 if (!build)
2249 goto error;
2251 map = isl_map_gist_domain(map, isl_set_copy(build->domain));
2253 return map;
2254 error:
2255 isl_map_free(map);
2256 return NULL;
2259 /* Simplify the affine expression "aff" based on what we know about
2260 * the iterators of already generated loops.
2262 * The domain of "aff" is assumed to live in the (internal) schedule domain.
2264 __isl_give isl_aff *isl_ast_build_compute_gist_aff(
2265 __isl_keep isl_ast_build *build, __isl_take isl_aff *aff)
2267 if (!build)
2268 goto error;
2270 aff = isl_aff_gist(aff, isl_set_copy(build->domain));
2272 return aff;
2273 error:
2274 isl_aff_free(aff);
2275 return NULL;
2278 /* Simplify the piecewise affine expression "aff" based on what we know about
2279 * the iterators of already generated loops.
2281 * The domain of "pa" is assumed to live in the (internal) schedule domain.
2283 __isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(
2284 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2286 if (!build)
2287 goto error;
2289 if (!isl_set_is_params(build->domain))
2290 pa = isl_pw_aff_pullback_multi_aff(pa,
2291 isl_multi_aff_copy(build->values));
2292 pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain));
2294 return pa;
2295 error:
2296 isl_pw_aff_free(pa);
2297 return NULL;
2300 /* Simplify the piecewise multi-affine expression "aff" based on what
2301 * we know about the iterators of already generated loops.
2303 * The domain of "pma" is assumed to live in the (internal) schedule domain.
2305 __isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(
2306 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2308 if (!build)
2309 goto error;
2311 pma = isl_pw_multi_aff_pullback_multi_aff(pma,
2312 isl_multi_aff_copy(build->values));
2313 pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain));
2315 return pma;
2316 error:
2317 isl_pw_multi_aff_free(pma);
2318 return NULL;
2321 /* Extract the schedule domain of the given type from build->options
2322 * at the current depth.
2324 * In particular, find the subset of build->options that is of
2325 * the following form
2327 * schedule_domain -> type[depth]
2329 * and return the corresponding domain, after eliminating inner dimensions
2330 * and divs that depend on the current dimension.
2332 * Note that the domain of build->options has been reformulated
2333 * in terms of the internal build space in embed_options,
2334 * but the position is still that within the current code generation.
2336 __isl_give isl_set *isl_ast_build_get_option_domain(
2337 __isl_keep isl_ast_build *build, enum isl_ast_loop_type type)
2339 const char *name;
2340 isl_space *space;
2341 isl_map *option;
2342 isl_set *domain;
2343 int local_pos;
2345 if (!build)
2346 return NULL;
2348 name = option_str[type];
2349 local_pos = build->depth - build->outer_pos;
2351 space = isl_ast_build_get_space(build, 1);
2352 space = isl_space_from_domain(space);
2353 space = isl_space_add_dims(space, isl_dim_out, 1);
2354 space = isl_space_set_tuple_name(space, isl_dim_out, name);
2356 option = isl_union_map_extract_map(build->options, space);
2357 option = isl_map_fix_si(option, isl_dim_out, 0, local_pos);
2359 domain = isl_map_domain(option);
2360 domain = isl_ast_build_eliminate(build, domain);
2362 return domain;
2365 /* How does the user want the current schedule dimension to be generated?
2366 * These choices have been extracted from the schedule node
2367 * in extract_loop_types and stored in build->loop_type.
2368 * They have been updated to reflect any dimension insertion in
2369 * node_insert_dim.
2370 * Return isl_ast_domain_error on error.
2372 * If "isolated" is set, then we get the loop AST generation type
2373 * directly from the band node since node_insert_dim cannot have been
2374 * called on a band with the isolate option.
2376 enum isl_ast_loop_type isl_ast_build_get_loop_type(
2377 __isl_keep isl_ast_build *build, int isolated)
2379 int local_pos;
2380 isl_ctx *ctx;
2382 if (!build)
2383 return isl_ast_loop_error;
2384 ctx = isl_ast_build_get_ctx(build);
2385 if (!build->node)
2386 isl_die(ctx, isl_error_internal,
2387 "only works for schedule tree based AST generation",
2388 return isl_ast_loop_error);
2390 local_pos = build->depth - build->outer_pos;
2391 if (!isolated)
2392 return build->loop_type[local_pos];
2393 return isl_schedule_node_band_member_get_isolate_ast_loop_type(
2394 build->node, local_pos);
2397 /* Extract the isolated set from the isolate option, if any,
2398 * and store in the build.
2399 * If there is no isolate option, then the isolated set is
2400 * set to the empty set.
2402 * The isolate option is of the form
2404 * isolate[[outer bands] -> current_band]
2406 * We flatten this set and then map it back to the internal
2407 * schedule space.
2409 * If we have already extracted the isolated set
2410 * or if internal2input is no longer set, then we do not
2411 * need to do anything. In the latter case, we know
2412 * that the current band cannot have any isolate option.
2414 __isl_give isl_ast_build *isl_ast_build_extract_isolated(
2415 __isl_take isl_ast_build *build)
2417 isl_space *space, *space2;
2418 isl_union_set *options;
2419 int n, n2;
2420 isl_set *isolated;
2422 if (!build)
2423 return NULL;
2424 if (!build->internal2input)
2425 return build;
2426 if (build->isolated)
2427 return build;
2429 build = isl_ast_build_cow(build);
2430 if (!build)
2431 return NULL;
2433 options = isl_schedule_node_band_get_ast_build_options(build->node);
2435 space = isl_multi_aff_get_space(build->internal2input);
2436 space = isl_space_range(space);
2437 space2 = isl_set_get_space(build->domain);
2438 if (isl_space_is_wrapping(space2))
2439 space2 = isl_space_range(isl_space_unwrap(space2));
2440 n2 = isl_space_dim(space2, isl_dim_set);
2441 n = isl_space_dim(space, isl_dim_set);
2442 if (n < n2)
2443 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2444 "total input space dimension cannot be smaller "
2445 "than dimension of innermost band",
2446 space = isl_space_free(space));
2447 space = isl_space_drop_dims(space, isl_dim_set, n - n2, n2);
2448 space = isl_space_map_from_domain_and_range(space, space2);
2449 space = isl_space_wrap(space);
2450 space = isl_space_set_tuple_name(space, isl_dim_set, "isolate");
2451 isolated = isl_union_set_extract_set(options, space);
2452 isl_union_set_free(options);
2454 isolated = isl_set_flatten(isolated);
2455 isolated = isl_set_preimage_multi_aff(isolated,
2456 isl_multi_aff_copy(build->internal2input));
2458 build->isolated = isolated;
2459 if (!build->isolated)
2460 return isl_ast_build_free(build);
2462 return build;
2465 /* Does "build" have a non-empty isolated set?
2467 * The caller is assumed to have called isl_ast_build_extract_isolated first.
2469 int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build)
2471 int empty;
2473 if (!build)
2474 return -1;
2475 if (!build->internal2input)
2476 return 0;
2477 if (!build->isolated)
2478 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2479 "isolated set not extracted yet", return -1);
2481 empty = isl_set_plain_is_empty(build->isolated);
2482 return empty < 0 ? -1 : !empty;
2485 /* Return a copy of the isolated set of "build".
2487 * The caller is assume to have called isl_ast_build_has_isolated first,
2488 * with this function returning true.
2489 * In particular, this function should not be called if we are no
2490 * longer keeping track of internal2input (and there therefore could
2491 * not possibly be any isolated set).
2493 __isl_give isl_set *isl_ast_build_get_isolated(__isl_keep isl_ast_build *build)
2495 if (!build)
2496 return NULL;
2497 if (!build->internal2input)
2498 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2499 "build cannot have isolated set", return NULL);
2501 return isl_set_copy(build->isolated);
2504 /* Extract the separation class mapping at the current depth.
2506 * In particular, find and return the subset of build->options that is of
2507 * the following form
2509 * schedule_domain -> separation_class[[depth] -> [class]]
2511 * The caller is expected to eliminate inner dimensions from the domain.
2513 * Note that the domain of build->options has been reformulated
2514 * in terms of the internal build space in embed_options,
2515 * but the position is still that within the current code generation.
2517 __isl_give isl_map *isl_ast_build_get_separation_class(
2518 __isl_keep isl_ast_build *build)
2520 isl_ctx *ctx;
2521 isl_space *space_sep, *space;
2522 isl_map *res;
2523 int local_pos;
2525 if (!build)
2526 return NULL;
2528 local_pos = build->depth - build->outer_pos;
2529 ctx = isl_ast_build_get_ctx(build);
2530 space_sep = isl_space_alloc(ctx, 0, 1, 1);
2531 space_sep = isl_space_wrap(space_sep);
2532 space_sep = isl_space_set_tuple_name(space_sep, isl_dim_set,
2533 "separation_class");
2534 space = isl_ast_build_get_space(build, 1);
2535 space_sep = isl_space_align_params(space_sep, isl_space_copy(space));
2536 space = isl_space_map_from_domain_and_range(space, space_sep);
2538 res = isl_union_map_extract_map(build->options, space);
2539 res = isl_map_fix_si(res, isl_dim_out, 0, local_pos);
2540 res = isl_map_coalesce(res);
2542 return res;
2545 /* Eliminate dimensions inner to the current dimension.
2547 __isl_give isl_set *isl_ast_build_eliminate_inner(
2548 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2550 int dim;
2551 int depth;
2553 if (!build)
2554 return isl_set_free(set);
2556 dim = isl_set_dim(set, isl_dim_set);
2557 depth = build->depth;
2558 set = isl_set_detect_equalities(set);
2559 set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1));
2561 return set;
2564 /* Eliminate unknown divs and divs that depend on the current dimension.
2566 * Note that during the elimination of unknown divs, we may discover
2567 * an explicit representation of some other unknown divs, which may
2568 * depend on the current dimension. We therefore need to eliminate
2569 * unknown divs first.
2571 __isl_give isl_set *isl_ast_build_eliminate_divs(
2572 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2574 int depth;
2576 if (!build)
2577 return isl_set_free(set);
2579 set = isl_set_remove_unknown_divs(set);
2580 depth = build->depth;
2581 set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1);
2583 return set;
2586 /* Eliminate dimensions inner to the current dimension as well as
2587 * unknown divs and divs that depend on the current dimension.
2588 * The result then consists only of constraints that are independent
2589 * of the current dimension and upper and lower bounds on the current
2590 * dimension.
2592 __isl_give isl_set *isl_ast_build_eliminate(
2593 __isl_keep isl_ast_build *build, __isl_take isl_set *domain)
2595 domain = isl_ast_build_eliminate_inner(build, domain);
2596 domain = isl_ast_build_eliminate_divs(build, domain);
2597 return domain;
2600 /* Replace build->single_valued by "sv".
2602 __isl_give isl_ast_build *isl_ast_build_set_single_valued(
2603 __isl_take isl_ast_build *build, int sv)
2605 if (!build)
2606 return build;
2607 if (build->single_valued == sv)
2608 return build;
2609 build = isl_ast_build_cow(build);
2610 if (!build)
2611 return build;
2612 build->single_valued = sv;
2614 return build;