isl_val.c: fix typo in comment
[isl.git] / isl_ast_build.c
blob1ebdde4fdf51dedc3854c7ebd5ba652b7301ac44
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/val.h>
14 #include <isl/space.h>
15 #include <isl/map.h>
16 #include <isl/aff.h>
17 #include <isl/constraint.h>
18 #include <isl/map.h>
19 #include <isl/union_set.h>
20 #include <isl/union_map.h>
21 #include <isl_ast_build_private.h>
22 #include <isl_ast_private.h>
23 #include <isl_config.h>
25 /* Construct a map that isolates the current dimension.
27 * Essentially, the current dimension of "set" is moved to the single output
28 * dimension in the result, with the current dimension in the domain replaced
29 * by an unconstrained variable.
31 __isl_give isl_map *isl_ast_build_map_to_iterator(
32 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
34 isl_map *map;
36 map = isl_map_from_domain(set);
37 map = isl_map_add_dims(map, isl_dim_out, 1);
39 if (!build)
40 return isl_map_free(map);
42 map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0);
43 map = isl_map_eliminate(map, isl_dim_in, build->depth, 1);
45 return map;
48 /* Initialize the information derived during the AST generation to default
49 * values for a schedule domain in "space".
51 * We also check that the remaining fields are not NULL so that
52 * the calling functions don't have to perform this test.
54 static __isl_give isl_ast_build *isl_ast_build_init_derived(
55 __isl_take isl_ast_build *build, __isl_take isl_space *space)
57 isl_ctx *ctx;
58 isl_vec *strides;
60 build = isl_ast_build_cow(build);
61 if (!build || !build->domain)
62 goto error;
64 ctx = isl_ast_build_get_ctx(build);
65 strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
66 strides = isl_vec_set_si(strides, 1);
68 isl_vec_free(build->strides);
69 build->strides = strides;
71 space = isl_space_map_from_set(space);
72 isl_multi_aff_free(build->offsets);
73 build->offsets = isl_multi_aff_zero(isl_space_copy(space));
74 isl_multi_aff_free(build->values);
75 build->values = isl_multi_aff_identity(isl_space_copy(space));
76 isl_multi_aff_free(build->internal2input);
77 build->internal2input = isl_multi_aff_identity(space);
79 if (!build->iterators || !build->domain || !build->generated ||
80 !build->pending || !build->values || !build->internal2input ||
81 !build->strides || !build->offsets || !build->options)
82 return isl_ast_build_free(build);
84 return build;
85 error:
86 isl_space_free(space);
87 return isl_ast_build_free(build);
90 /* Return an isl_id called "c%d", with "%d" set to "i".
91 * If an isl_id with such a name already appears among the parameters
92 * in build->domain, then adjust the name to "c%d_%d".
94 static __isl_give isl_id *generate_name(isl_ctx *ctx, int i,
95 __isl_keep isl_ast_build *build)
97 int j;
98 char name[16];
99 isl_set *dom = build->domain;
101 snprintf(name, sizeof(name), "c%d", i);
102 j = 0;
103 while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)
104 snprintf(name, sizeof(name), "c%d_%d", i, j++);
105 return isl_id_alloc(ctx, name, NULL);
108 /* Create an isl_ast_build with "set" as domain.
110 * The input set is usually a parameter domain, but we currently allow it to
111 * be any kind of set. We set the domain of the returned isl_ast_build
112 * to "set" and initialize all the other fields to default values.
114 __isl_give isl_ast_build *isl_ast_build_from_context(__isl_take isl_set *set)
116 int i, n;
117 isl_ctx *ctx;
118 isl_space *space;
119 isl_ast_build *build;
121 set = isl_set_compute_divs(set);
122 if (!set)
123 return NULL;
125 ctx = isl_set_get_ctx(set);
127 build = isl_calloc_type(ctx, isl_ast_build);
128 if (!build)
129 goto error;
131 build->ref = 1;
132 build->domain = set;
133 build->generated = isl_set_copy(build->domain);
134 build->pending = isl_set_universe(isl_set_get_space(build->domain));
135 build->options = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
136 n = isl_set_dim(set, isl_dim_set);
137 build->depth = n;
138 build->iterators = isl_id_list_alloc(ctx, n);
139 for (i = 0; i < n; ++i) {
140 isl_id *id;
141 if (isl_set_has_dim_id(set, isl_dim_set, i))
142 id = isl_set_get_dim_id(set, isl_dim_set, i);
143 else
144 id = generate_name(ctx, i, build);
145 build->iterators = isl_id_list_add(build->iterators, id);
147 space = isl_set_get_space(set);
148 if (isl_space_is_params(space))
149 space = isl_space_set_from_params(space);
151 return isl_ast_build_init_derived(build, space);
152 error:
153 isl_set_free(set);
154 return NULL;
157 /* Create an isl_ast_build with a universe (parametric) context.
159 __isl_give isl_ast_build *isl_ast_build_alloc(isl_ctx *ctx)
161 isl_space *space;
162 isl_set *context;
164 space = isl_space_params_alloc(ctx, 0);
165 context = isl_set_universe(space);
167 return isl_ast_build_from_context(context);
170 __isl_give isl_ast_build *isl_ast_build_copy(__isl_keep isl_ast_build *build)
172 if (!build)
173 return NULL;
175 build->ref++;
176 return build;
179 __isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
181 isl_ctx *ctx;
182 isl_ast_build *dup;
184 if (!build)
185 return NULL;
187 ctx = isl_ast_build_get_ctx(build);
188 dup = isl_calloc_type(ctx, isl_ast_build);
189 if (!dup)
190 return NULL;
192 dup->ref = 1;
193 dup->outer_pos = build->outer_pos;
194 dup->depth = build->depth;
195 dup->iterators = isl_id_list_copy(build->iterators);
196 dup->domain = isl_set_copy(build->domain);
197 dup->generated = isl_set_copy(build->generated);
198 dup->pending = isl_set_copy(build->pending);
199 dup->values = isl_multi_aff_copy(build->values);
200 dup->internal2input = isl_multi_aff_copy(build->internal2input);
201 dup->value = isl_pw_aff_copy(build->value);
202 dup->strides = isl_vec_copy(build->strides);
203 dup->offsets = isl_multi_aff_copy(build->offsets);
204 dup->executed = isl_union_map_copy(build->executed);
205 dup->single_valued = build->single_valued;
206 dup->options = isl_union_map_copy(build->options);
207 dup->at_each_domain = build->at_each_domain;
208 dup->at_each_domain_user = build->at_each_domain_user;
209 dup->before_each_for = build->before_each_for;
210 dup->before_each_for_user = build->before_each_for_user;
211 dup->after_each_for = build->after_each_for;
212 dup->after_each_for_user = build->after_each_for_user;
213 dup->before_each_mark = build->before_each_mark;
214 dup->before_each_mark_user = build->before_each_mark_user;
215 dup->after_each_mark = build->after_each_mark;
216 dup->after_each_mark_user = build->after_each_mark_user;
217 dup->create_leaf = build->create_leaf;
218 dup->create_leaf_user = build->create_leaf_user;
219 dup->node = isl_schedule_node_copy(build->node);
220 if (build->loop_type) {
221 int i;
223 dup->n = build->n;
224 dup->loop_type = isl_alloc_array(ctx,
225 enum isl_ast_loop_type, dup->n);
226 if (dup->n && !dup->loop_type)
227 return isl_ast_build_free(dup);
228 for (i = 0; i < dup->n; ++i)
229 dup->loop_type[i] = build->loop_type[i];
232 if (!dup->iterators || !dup->domain || !dup->generated ||
233 !dup->pending || !dup->values ||
234 !dup->strides || !dup->offsets || !dup->options ||
235 (build->internal2input && !dup->internal2input) ||
236 (build->executed && !dup->executed) ||
237 (build->value && !dup->value) ||
238 (build->node && !dup->node))
239 return isl_ast_build_free(dup);
241 return dup;
244 /* Align the parameters of "build" to those of "model", introducing
245 * additional parameters if needed.
247 __isl_give isl_ast_build *isl_ast_build_align_params(
248 __isl_take isl_ast_build *build, __isl_take isl_space *model)
250 build = isl_ast_build_cow(build);
251 if (!build)
252 goto error;
254 build->domain = isl_set_align_params(build->domain,
255 isl_space_copy(model));
256 build->generated = isl_set_align_params(build->generated,
257 isl_space_copy(model));
258 build->pending = isl_set_align_params(build->pending,
259 isl_space_copy(model));
260 build->values = isl_multi_aff_align_params(build->values,
261 isl_space_copy(model));
262 build->offsets = isl_multi_aff_align_params(build->offsets,
263 isl_space_copy(model));
264 build->options = isl_union_map_align_params(build->options,
265 isl_space_copy(model));
266 if (build->internal2input) {
267 build->internal2input =
268 isl_multi_aff_align_params(build->internal2input,
269 model);
270 if (!build->internal2input)
271 return isl_ast_build_free(build);
272 } else {
273 isl_space_free(model);
276 if (!build->domain || !build->values || !build->offsets ||
277 !build->options)
278 return isl_ast_build_free(build);
280 return build;
281 error:
282 isl_space_free(model);
283 return NULL;
286 __isl_give isl_ast_build *isl_ast_build_cow(__isl_take isl_ast_build *build)
288 if (!build)
289 return NULL;
291 if (build->ref == 1)
292 return build;
293 build->ref--;
294 return isl_ast_build_dup(build);
297 __isl_null isl_ast_build *isl_ast_build_free(
298 __isl_take isl_ast_build *build)
300 if (!build)
301 return NULL;
303 if (--build->ref > 0)
304 return NULL;
306 isl_id_list_free(build->iterators);
307 isl_set_free(build->domain);
308 isl_set_free(build->generated);
309 isl_set_free(build->pending);
310 isl_multi_aff_free(build->values);
311 isl_multi_aff_free(build->internal2input);
312 isl_pw_aff_free(build->value);
313 isl_vec_free(build->strides);
314 isl_multi_aff_free(build->offsets);
315 isl_multi_aff_free(build->schedule_map);
316 isl_union_map_free(build->executed);
317 isl_union_map_free(build->options);
318 isl_schedule_node_free(build->node);
319 free(build->loop_type);
320 isl_set_free(build->isolated);
322 free(build);
324 return NULL;
327 isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build)
329 return build ? isl_set_get_ctx(build->domain) : NULL;
332 /* Replace build->options by "options".
334 __isl_give isl_ast_build *isl_ast_build_set_options(
335 __isl_take isl_ast_build *build, __isl_take isl_union_map *options)
337 build = isl_ast_build_cow(build);
339 if (!build || !options)
340 goto error;
342 isl_union_map_free(build->options);
343 build->options = options;
345 return build;
346 error:
347 isl_union_map_free(options);
348 return isl_ast_build_free(build);
351 /* Set the iterators for the next code generation.
353 * If we still have some iterators left from the previous code generation
354 * (if any) or if iterators have already been set by a previous
355 * call to this function, then we remove them first.
357 __isl_give isl_ast_build *isl_ast_build_set_iterators(
358 __isl_take isl_ast_build *build, __isl_take isl_id_list *iterators)
360 int dim, n_it;
362 build = isl_ast_build_cow(build);
363 if (!build)
364 goto error;
366 dim = isl_set_dim(build->domain, isl_dim_set);
367 n_it = isl_id_list_n_id(build->iterators);
368 if (n_it < dim)
369 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
370 "isl_ast_build in inconsistent state", goto error);
371 if (n_it > dim)
372 build->iterators = isl_id_list_drop(build->iterators,
373 dim, n_it - dim);
374 build->iterators = isl_id_list_concat(build->iterators, iterators);
375 if (!build->iterators)
376 return isl_ast_build_free(build);
378 return build;
379 error:
380 isl_id_list_free(iterators);
381 return isl_ast_build_free(build);
384 /* Set the "at_each_domain" callback of "build" to "fn".
386 __isl_give isl_ast_build *isl_ast_build_set_at_each_domain(
387 __isl_take isl_ast_build *build,
388 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
389 __isl_keep isl_ast_build *build, void *user), void *user)
391 build = isl_ast_build_cow(build);
393 if (!build)
394 return NULL;
396 build->at_each_domain = fn;
397 build->at_each_domain_user = user;
399 return build;
402 /* Set the "before_each_for" callback of "build" to "fn".
404 __isl_give isl_ast_build *isl_ast_build_set_before_each_for(
405 __isl_take isl_ast_build *build,
406 __isl_give isl_id *(*fn)(__isl_keep isl_ast_build *build,
407 void *user), void *user)
409 build = isl_ast_build_cow(build);
411 if (!build)
412 return NULL;
414 build->before_each_for = fn;
415 build->before_each_for_user = user;
417 return build;
420 /* Set the "after_each_for" callback of "build" to "fn".
422 __isl_give isl_ast_build *isl_ast_build_set_after_each_for(
423 __isl_take isl_ast_build *build,
424 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
425 __isl_keep isl_ast_build *build, void *user), void *user)
427 build = isl_ast_build_cow(build);
429 if (!build)
430 return NULL;
432 build->after_each_for = fn;
433 build->after_each_for_user = user;
435 return build;
438 /* Set the "before_each_mark" callback of "build" to "fn".
440 __isl_give isl_ast_build *isl_ast_build_set_before_each_mark(
441 __isl_take isl_ast_build *build,
442 isl_stat (*fn)(__isl_keep isl_id *mark, __isl_keep isl_ast_build *build,
443 void *user), void *user)
445 build = isl_ast_build_cow(build);
447 if (!build)
448 return NULL;
450 build->before_each_mark = fn;
451 build->before_each_mark_user = user;
453 return build;
456 /* Set the "after_each_mark" callback of "build" to "fn".
458 __isl_give isl_ast_build *isl_ast_build_set_after_each_mark(
459 __isl_take isl_ast_build *build,
460 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
461 __isl_keep isl_ast_build *build, void *user), void *user)
463 build = isl_ast_build_cow(build);
465 if (!build)
466 return NULL;
468 build->after_each_mark = fn;
469 build->after_each_mark_user = user;
471 return build;
474 /* Set the "create_leaf" callback of "build" to "fn".
476 __isl_give isl_ast_build *isl_ast_build_set_create_leaf(
477 __isl_take isl_ast_build *build,
478 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_build *build,
479 void *user), void *user)
481 build = isl_ast_build_cow(build);
483 if (!build)
484 return NULL;
486 build->create_leaf = fn;
487 build->create_leaf_user = user;
489 return build;
492 /* Clear all information that is specific to this code generation
493 * and that is (probably) not meaningful to any nested code generation.
495 __isl_give isl_ast_build *isl_ast_build_clear_local_info(
496 __isl_take isl_ast_build *build)
498 isl_space *space;
500 build = isl_ast_build_cow(build);
501 if (!build)
502 return NULL;
504 space = isl_union_map_get_space(build->options);
505 isl_union_map_free(build->options);
506 build->options = isl_union_map_empty(space);
508 build->at_each_domain = NULL;
509 build->at_each_domain_user = NULL;
510 build->before_each_for = NULL;
511 build->before_each_for_user = NULL;
512 build->after_each_for = NULL;
513 build->after_each_for_user = NULL;
514 build->before_each_mark = NULL;
515 build->before_each_mark_user = NULL;
516 build->after_each_mark = NULL;
517 build->after_each_mark_user = NULL;
518 build->create_leaf = NULL;
519 build->create_leaf_user = NULL;
521 if (!build->options)
522 return isl_ast_build_free(build);
524 return build;
527 /* Have any loops been eliminated?
528 * That is, do any of the original schedule dimensions have a fixed
529 * value that has been substituted?
531 static int any_eliminated(isl_ast_build *build)
533 int i;
535 for (i = 0; i < build->depth; ++i)
536 if (isl_ast_build_has_affine_value(build, i))
537 return 1;
539 return 0;
542 /* Clear build->schedule_map.
543 * This function should be called whenever anything that might affect
544 * the result of isl_ast_build_get_schedule_map_multi_aff changes.
545 * In particular, it should be called when the depth is changed or
546 * when an iterator is determined to have a fixed value.
548 static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build *build)
550 if (!build)
551 return;
552 isl_multi_aff_free(build->schedule_map);
553 build->schedule_map = NULL;
556 /* Do we need a (non-trivial) schedule map?
557 * That is, is the internal schedule space different from
558 * the external schedule space?
560 * The internal and external schedule spaces are only the same
561 * if code has been generated for the entire schedule and if none
562 * of the loops have been eliminated.
564 __isl_give int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build *build)
566 int dim;
568 if (!build)
569 return -1;
571 dim = isl_set_dim(build->domain, isl_dim_set);
572 return build->depth != dim || any_eliminated(build);
575 /* Return a mapping from the internal schedule space to the external
576 * schedule space in the form of an isl_multi_aff.
577 * The internal schedule space originally corresponds to that of the
578 * input schedule. This may change during the code generation if
579 * if isl_ast_build_insert_dim is ever called.
580 * The external schedule space corresponds to the
581 * loops that have been generated.
583 * Currently, the only difference between the internal schedule domain
584 * and the external schedule domain is that some dimensions are projected
585 * out in the external schedule domain. In particular, the dimensions
586 * for which no code has been generated yet and the dimensions that correspond
587 * to eliminated loops.
589 * We cache a copy of the schedule_map in build->schedule_map.
590 * The cache is cleared through isl_ast_build_reset_schedule_map
591 * whenever anything changes that might affect the result of this function.
593 __isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(
594 __isl_keep isl_ast_build *build)
596 isl_space *space;
597 isl_multi_aff *ma;
599 if (!build)
600 return NULL;
601 if (build->schedule_map)
602 return isl_multi_aff_copy(build->schedule_map);
604 space = isl_ast_build_get_space(build, 1);
605 space = isl_space_map_from_set(space);
606 ma = isl_multi_aff_identity(space);
607 if (isl_ast_build_need_schedule_map(build)) {
608 int i;
609 int dim = isl_set_dim(build->domain, isl_dim_set);
610 ma = isl_multi_aff_drop_dims(ma, isl_dim_out,
611 build->depth, dim - build->depth);
612 for (i = build->depth - 1; i >= 0; --i)
613 if (isl_ast_build_has_affine_value(build, i))
614 ma = isl_multi_aff_drop_dims(ma,
615 isl_dim_out, i, 1);
618 build->schedule_map = ma;
619 return isl_multi_aff_copy(build->schedule_map);
622 /* Return a mapping from the internal schedule space to the external
623 * schedule space in the form of an isl_map.
625 __isl_give isl_map *isl_ast_build_get_schedule_map(
626 __isl_keep isl_ast_build *build)
628 isl_multi_aff *ma;
630 ma = isl_ast_build_get_schedule_map_multi_aff(build);
631 return isl_map_from_multi_aff(ma);
634 /* Return the position of the dimension in build->domain for which
635 * an AST node is currently being generated.
637 int isl_ast_build_get_depth(__isl_keep isl_ast_build *build)
639 return build ? build->depth : -1;
642 /* Prepare for generating code for the next level.
643 * In particular, increase the depth and reset any information
644 * that is local to the current depth.
646 __isl_give isl_ast_build *isl_ast_build_increase_depth(
647 __isl_take isl_ast_build *build)
649 build = isl_ast_build_cow(build);
650 if (!build)
651 return NULL;
652 build->depth++;
653 isl_ast_build_reset_schedule_map(build);
654 build->value = isl_pw_aff_free(build->value);
655 return build;
658 void isl_ast_build_dump(__isl_keep isl_ast_build *build)
660 if (!build)
661 return;
663 fprintf(stderr, "domain: ");
664 isl_set_dump(build->domain);
665 fprintf(stderr, "generated: ");
666 isl_set_dump(build->generated);
667 fprintf(stderr, "pending: ");
668 isl_set_dump(build->pending);
669 fprintf(stderr, "iterators: ");
670 isl_id_list_dump(build->iterators);
671 fprintf(stderr, "values: ");
672 isl_multi_aff_dump(build->values);
673 if (build->value) {
674 fprintf(stderr, "value: ");
675 isl_pw_aff_dump(build->value);
677 fprintf(stderr, "strides: ");
678 isl_vec_dump(build->strides);
679 fprintf(stderr, "offsets: ");
680 isl_multi_aff_dump(build->offsets);
681 fprintf(stderr, "internal2input: ");
682 isl_multi_aff_dump(build->internal2input);
685 /* Initialize "build" for AST construction in schedule space "space"
686 * in the case that build->domain is a parameter set.
688 * build->iterators is assumed to have been updated already.
690 static __isl_give isl_ast_build *isl_ast_build_init(
691 __isl_take isl_ast_build *build, __isl_take isl_space *space)
693 isl_set *set;
695 build = isl_ast_build_cow(build);
696 if (!build)
697 goto error;
699 set = isl_set_universe(isl_space_copy(space));
700 build->domain = isl_set_intersect_params(isl_set_copy(set),
701 build->domain);
702 build->pending = isl_set_intersect_params(isl_set_copy(set),
703 build->pending);
704 build->generated = isl_set_intersect_params(set, build->generated);
706 return isl_ast_build_init_derived(build, space);
707 error:
708 isl_ast_build_free(build);
709 isl_space_free(space);
710 return NULL;
713 /* Assign "aff" to *user and return -1, effectively extracting
714 * the first (and presumably only) affine expression in the isl_pw_aff
715 * on which this function is used.
717 static isl_stat extract_single_piece(__isl_take isl_set *set,
718 __isl_take isl_aff *aff, void *user)
720 isl_aff **p = user;
722 *p = aff;
723 isl_set_free(set);
725 return isl_stat_error;
728 /* Intersect "set" with the stride constraint of "build", if any.
730 static __isl_give isl_set *intersect_stride_constraint(__isl_take isl_set *set,
731 __isl_keep isl_ast_build *build)
733 isl_set *stride;
735 if (!build)
736 return isl_set_free(set);
737 if (!isl_ast_build_has_stride(build, build->depth))
738 return set;
740 stride = isl_ast_build_get_stride_constraint(build);
741 return isl_set_intersect(set, stride);
744 /* Check if the given bounds on the current dimension (together with
745 * the stride constraint, if any) imply that
746 * this current dimension attains only a single value (in terms of
747 * parameters and outer dimensions).
748 * If so, we record it in build->value.
749 * If, moreover, this value can be represented as a single affine expression,
750 * then we also update build->values, effectively marking the current
751 * dimension as "eliminated".
753 * When computing the gist of the fixed value that can be represented
754 * as a single affine expression, it is important to only take into
755 * account the domain constraints in the original AST build and
756 * not the domain of the affine expression itself.
757 * Otherwise, a [i/3] is changed into a i/3 because we know that i
758 * is a multiple of 3, but then we end up not expressing anywhere
759 * in the context that i is a multiple of 3.
761 static __isl_give isl_ast_build *update_values(
762 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
764 int sv;
765 isl_pw_multi_aff *pma;
766 isl_aff *aff = NULL;
767 isl_map *it_map;
768 isl_set *set;
770 set = isl_set_from_basic_set(bounds);
771 set = isl_set_intersect(set, isl_set_copy(build->domain));
772 set = intersect_stride_constraint(set, build);
773 it_map = isl_ast_build_map_to_iterator(build, set);
775 sv = isl_map_is_single_valued(it_map);
776 if (sv < 0)
777 build = isl_ast_build_free(build);
778 if (!build || !sv) {
779 isl_map_free(it_map);
780 return build;
783 pma = isl_pw_multi_aff_from_map(it_map);
784 build->value = isl_pw_multi_aff_get_pw_aff(pma, 0);
785 build->value = isl_ast_build_compute_gist_pw_aff(build, build->value);
786 build->value = isl_pw_aff_coalesce(build->value);
787 isl_pw_multi_aff_free(pma);
789 if (!build->value)
790 return isl_ast_build_free(build);
792 if (isl_pw_aff_n_piece(build->value) != 1)
793 return build;
795 isl_pw_aff_foreach_piece(build->value, &extract_single_piece, &aff);
797 build->values = isl_multi_aff_set_aff(build->values, build->depth, aff);
798 if (!build->values)
799 return isl_ast_build_free(build);
800 isl_ast_build_reset_schedule_map(build);
801 return build;
804 /* Update the AST build based on the given loop bounds for
805 * the current dimension and the stride information available in the build.
807 * We first make sure that the bounds do not refer to any iterators
808 * that have already been eliminated.
809 * Then, we check if the bounds imply that the current iterator
810 * has a fixed value.
811 * If they do and if this fixed value can be expressed as a single
812 * affine expression, we eliminate the iterators from the bounds.
813 * Note that we cannot simply plug in this single value using
814 * isl_basic_set_preimage_multi_aff as the single value may only
815 * be defined on a subset of the domain. Plugging in the value
816 * would restrict the build domain to this subset, while this
817 * restriction may not be reflected in the generated code.
818 * Finally, we intersect build->domain with the updated bounds.
819 * We also add the stride constraint unless we have been able
820 * to find a fixed value expressed as a single affine expression.
822 * Note that the check for a fixed value in update_values requires
823 * us to intersect the bounds with the current build domain.
824 * When we intersect build->domain with the updated bounds in
825 * the final step, we make sure that these updated bounds have
826 * not been intersected with the old build->domain.
827 * Otherwise, we would indirectly intersect the build domain with itself,
828 * which can lead to inefficiencies, in particular if the build domain
829 * contains any unknown divs.
831 * The pending and generated sets are not updated by this function to
832 * match the updated domain.
833 * The caller still needs to call isl_ast_build_set_pending_generated.
835 __isl_give isl_ast_build *isl_ast_build_set_loop_bounds(
836 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
838 isl_set *set;
840 build = isl_ast_build_cow(build);
841 if (!build)
842 goto error;
844 build = update_values(build, isl_basic_set_copy(bounds));
845 if (!build)
846 goto error;
847 set = isl_set_from_basic_set(isl_basic_set_copy(bounds));
848 if (isl_ast_build_has_affine_value(build, build->depth)) {
849 set = isl_set_eliminate(set, isl_dim_set, build->depth, 1);
850 set = isl_set_compute_divs(set);
851 build->pending = isl_set_intersect(build->pending,
852 isl_set_copy(set));
853 build->domain = isl_set_intersect(build->domain, set);
854 } else {
855 build->domain = isl_set_intersect(build->domain, set);
856 build = isl_ast_build_include_stride(build);
857 if (!build)
858 goto error;
860 isl_basic_set_free(bounds);
862 if (!build->domain || !build->pending || !build->generated)
863 return isl_ast_build_free(build);
865 return build;
866 error:
867 isl_ast_build_free(build);
868 isl_basic_set_free(bounds);
869 return NULL;
872 /* Update the pending and generated sets of "build" according to "bounds".
873 * If the build has an affine value at the current depth,
874 * then isl_ast_build_set_loop_bounds has already set the pending set.
875 * Otherwise, do it here.
877 __isl_give isl_ast_build *isl_ast_build_set_pending_generated(
878 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
880 isl_basic_set *generated, *pending;
882 if (!build)
883 goto error;
885 if (isl_ast_build_has_affine_value(build, build->depth)) {
886 isl_basic_set_free(bounds);
887 return build;
890 build = isl_ast_build_cow(build);
891 if (!build)
892 goto error;
894 pending = isl_basic_set_copy(bounds);
895 pending = isl_basic_set_drop_constraints_involving_dims(pending,
896 isl_dim_set, build->depth, 1);
897 build->pending = isl_set_intersect(build->pending,
898 isl_set_from_basic_set(pending));
899 generated = bounds;
900 generated = isl_basic_set_drop_constraints_not_involving_dims(
901 generated, isl_dim_set, build->depth, 1);
902 build->generated = isl_set_intersect(build->generated,
903 isl_set_from_basic_set(generated));
905 if (!build->pending || !build->generated)
906 return isl_ast_build_free(build);
908 return build;
909 error:
910 isl_ast_build_free(build);
911 isl_basic_set_free(bounds);
912 return NULL;
915 /* Intersect build->domain with "set", where "set" is specified
916 * in terms of the internal schedule domain.
918 static __isl_give isl_ast_build *isl_ast_build_restrict_internal(
919 __isl_take isl_ast_build *build, __isl_take isl_set *set)
921 build = isl_ast_build_cow(build);
922 if (!build)
923 goto error;
925 set = isl_set_compute_divs(set);
926 build->domain = isl_set_intersect(build->domain, set);
927 build->domain = isl_set_coalesce(build->domain);
929 if (!build->domain)
930 return isl_ast_build_free(build);
932 return build;
933 error:
934 isl_ast_build_free(build);
935 isl_set_free(set);
936 return NULL;
939 /* Intersect build->generated and build->domain with "set",
940 * where "set" is specified in terms of the internal schedule domain.
942 __isl_give isl_ast_build *isl_ast_build_restrict_generated(
943 __isl_take isl_ast_build *build, __isl_take isl_set *set)
945 set = isl_set_compute_divs(set);
946 build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
947 build = isl_ast_build_cow(build);
948 if (!build)
949 goto error;
951 build->generated = isl_set_intersect(build->generated, set);
952 build->generated = isl_set_coalesce(build->generated);
954 if (!build->generated)
955 return isl_ast_build_free(build);
957 return build;
958 error:
959 isl_ast_build_free(build);
960 isl_set_free(set);
961 return NULL;
964 /* Replace the set of pending constraints by "guard", which is then
965 * no longer considered as pending.
966 * That is, add "guard" to the generated constraints and clear all pending
967 * constraints, making the domain equal to the generated constraints.
969 __isl_give isl_ast_build *isl_ast_build_replace_pending_by_guard(
970 __isl_take isl_ast_build *build, __isl_take isl_set *guard)
972 build = isl_ast_build_restrict_generated(build, guard);
973 build = isl_ast_build_cow(build);
974 if (!build)
975 return NULL;
977 isl_set_free(build->domain);
978 build->domain = isl_set_copy(build->generated);
979 isl_set_free(build->pending);
980 build->pending = isl_set_universe(isl_set_get_space(build->domain));
982 if (!build->pending)
983 return isl_ast_build_free(build);
985 return build;
988 /* Intersect build->domain with "set", where "set" is specified
989 * in terms of the external schedule domain.
991 __isl_give isl_ast_build *isl_ast_build_restrict(
992 __isl_take isl_ast_build *build, __isl_take isl_set *set)
994 if (isl_set_is_params(set))
995 return isl_ast_build_restrict_generated(build, set);
997 if (isl_ast_build_need_schedule_map(build)) {
998 isl_multi_aff *ma;
999 ma = isl_ast_build_get_schedule_map_multi_aff(build);
1000 set = isl_set_preimage_multi_aff(set, ma);
1002 return isl_ast_build_restrict_generated(build, set);
1005 /* Replace build->executed by "executed".
1007 __isl_give isl_ast_build *isl_ast_build_set_executed(
1008 __isl_take isl_ast_build *build, __isl_take isl_union_map *executed)
1010 build = isl_ast_build_cow(build);
1011 if (!build)
1012 goto error;
1014 isl_union_map_free(build->executed);
1015 build->executed = executed;
1017 return build;
1018 error:
1019 isl_ast_build_free(build);
1020 isl_union_map_free(executed);
1021 return NULL;
1024 /* Does "build" point to a band node?
1025 * That is, are we currently handling a band node inside a schedule tree?
1027 int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build *build)
1029 if (!build)
1030 return -1;
1031 return build->node != NULL;
1034 /* Return a copy of the band node that "build" refers to.
1036 __isl_give isl_schedule_node *isl_ast_build_get_schedule_node(
1037 __isl_keep isl_ast_build *build)
1039 if (!build)
1040 return NULL;
1041 return isl_schedule_node_copy(build->node);
1044 /* Extract the loop AST generation types for the members of build->node
1045 * and store them in build->loop_type.
1047 static __isl_give isl_ast_build *extract_loop_types(
1048 __isl_take isl_ast_build *build)
1050 int i;
1051 isl_ctx *ctx;
1052 isl_schedule_node *node;
1054 if (!build)
1055 return NULL;
1056 ctx = isl_ast_build_get_ctx(build);
1057 if (!build->node)
1058 isl_die(ctx, isl_error_internal, "missing AST node",
1059 return isl_ast_build_free(build));
1061 free(build->loop_type);
1062 build->n = isl_schedule_node_band_n_member(build->node);
1063 build->loop_type = isl_alloc_array(ctx,
1064 enum isl_ast_loop_type, build->n);
1065 if (build->n && !build->loop_type)
1066 return isl_ast_build_free(build);
1067 node = build->node;
1068 for (i = 0; i < build->n; ++i)
1069 build->loop_type[i] =
1070 isl_schedule_node_band_member_get_ast_loop_type(node, i);
1072 return build;
1075 /* Replace the band node that "build" refers to by "node" and
1076 * extract the corresponding loop AST generation types.
1078 __isl_give isl_ast_build *isl_ast_build_set_schedule_node(
1079 __isl_take isl_ast_build *build,
1080 __isl_take isl_schedule_node *node)
1082 build = isl_ast_build_cow(build);
1083 if (!build || !node)
1084 goto error;
1086 isl_schedule_node_free(build->node);
1087 build->node = node;
1089 build = extract_loop_types(build);
1091 return build;
1092 error:
1093 isl_ast_build_free(build);
1094 isl_schedule_node_free(node);
1095 return NULL;
1098 /* Remove any reference to a band node from "build".
1100 __isl_give isl_ast_build *isl_ast_build_reset_schedule_node(
1101 __isl_take isl_ast_build *build)
1103 build = isl_ast_build_cow(build);
1104 if (!build)
1105 return NULL;
1107 isl_schedule_node_free(build->node);
1108 build->node = NULL;
1110 return build;
1113 /* Return a copy of the current schedule domain.
1115 __isl_give isl_set *isl_ast_build_get_domain(__isl_keep isl_ast_build *build)
1117 return build ? isl_set_copy(build->domain) : NULL;
1120 /* Return a copy of the set of pending constraints.
1122 __isl_give isl_set *isl_ast_build_get_pending(
1123 __isl_keep isl_ast_build *build)
1125 return build ? isl_set_copy(build->pending) : NULL;
1128 /* Return a copy of the set of generated constraints.
1130 __isl_give isl_set *isl_ast_build_get_generated(
1131 __isl_keep isl_ast_build *build)
1133 return build ? isl_set_copy(build->generated) : NULL;
1136 /* Return a copy of the map from the internal schedule domain
1137 * to the original input schedule domain.
1139 __isl_give isl_multi_aff *isl_ast_build_get_internal2input(
1140 __isl_keep isl_ast_build *build)
1142 return build ? isl_multi_aff_copy(build->internal2input) : NULL;
1145 /* Return the number of variables of the given type
1146 * in the (internal) schedule space.
1148 unsigned isl_ast_build_dim(__isl_keep isl_ast_build *build,
1149 enum isl_dim_type type)
1151 if (!build)
1152 return 0;
1153 return isl_set_dim(build->domain, type);
1156 /* Return the (schedule) space of "build".
1158 * If "internal" is set, then this space is the space of the internal
1159 * representation of the entire schedule, including those parts for
1160 * which no code has been generated yet.
1162 * If "internal" is not set, then this space is the external representation
1163 * of the loops generated so far.
1165 __isl_give isl_space *isl_ast_build_get_space(__isl_keep isl_ast_build *build,
1166 int internal)
1168 int i;
1169 int dim;
1170 isl_space *space;
1172 if (!build)
1173 return NULL;
1175 space = isl_set_get_space(build->domain);
1176 if (internal)
1177 return space;
1179 if (!isl_ast_build_need_schedule_map(build))
1180 return space;
1182 dim = isl_set_dim(build->domain, isl_dim_set);
1183 space = isl_space_drop_dims(space, isl_dim_set,
1184 build->depth, dim - build->depth);
1185 for (i = build->depth - 1; i >= 0; --i)
1186 if (isl_ast_build_has_affine_value(build, i))
1187 space = isl_space_drop_dims(space, isl_dim_set, i, 1);
1189 return space;
1192 /* Return the external representation of the schedule space of "build",
1193 * i.e., a space with a dimension for each loop generated so far,
1194 * with the names of the dimensions set to the loop iterators.
1196 __isl_give isl_space *isl_ast_build_get_schedule_space(
1197 __isl_keep isl_ast_build *build)
1199 isl_space *space;
1200 int i, skip;
1202 if (!build)
1203 return NULL;
1205 space = isl_ast_build_get_space(build, 0);
1207 skip = 0;
1208 for (i = 0; i < build->depth; ++i) {
1209 isl_id *id;
1211 if (isl_ast_build_has_affine_value(build, i)) {
1212 skip++;
1213 continue;
1216 id = isl_ast_build_get_iterator_id(build, i);
1217 space = isl_space_set_dim_id(space, isl_dim_set, i - skip, id);
1220 return space;
1223 /* Return the current schedule, as stored in build->executed, in terms
1224 * of the external schedule domain.
1226 __isl_give isl_union_map *isl_ast_build_get_schedule(
1227 __isl_keep isl_ast_build *build)
1229 isl_union_map *executed;
1230 isl_union_map *schedule;
1232 if (!build)
1233 return NULL;
1235 executed = isl_union_map_copy(build->executed);
1236 if (isl_ast_build_need_schedule_map(build)) {
1237 isl_map *proj = isl_ast_build_get_schedule_map(build);
1238 executed = isl_union_map_apply_domain(executed,
1239 isl_union_map_from_map(proj));
1241 schedule = isl_union_map_reverse(executed);
1243 return schedule;
1246 /* Return the iterator attached to the internal schedule dimension "pos".
1248 __isl_give isl_id *isl_ast_build_get_iterator_id(
1249 __isl_keep isl_ast_build *build, int pos)
1251 if (!build)
1252 return NULL;
1254 return isl_id_list_get_id(build->iterators, pos);
1257 /* Set the stride and offset of the current dimension to the given
1258 * value and expression.
1260 * If we had already found a stride before, then the two strides
1261 * are combined into a single stride.
1263 * In particular, if the new stride information is of the form
1265 * i = f + s (...)
1267 * and the old stride information is of the form
1269 * i = f2 + s2 (...)
1271 * then we compute the extended gcd of s and s2
1273 * a s + b s2 = g,
1275 * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
1276 * and the second with t2 = a s1/g.
1277 * This results in
1279 * i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
1281 * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
1282 * is the combined stride.
1284 static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build,
1285 __isl_take isl_val *stride, __isl_take isl_aff *offset)
1287 int pos;
1289 build = isl_ast_build_cow(build);
1290 if (!build || !stride || !offset)
1291 goto error;
1293 pos = build->depth;
1295 if (isl_ast_build_has_stride(build, pos)) {
1296 isl_val *stride2, *a, *b, *g;
1297 isl_aff *offset2;
1299 stride2 = isl_vec_get_element_val(build->strides, pos);
1300 g = isl_val_gcdext(isl_val_copy(stride), isl_val_copy(stride2),
1301 &a, &b);
1302 a = isl_val_mul(a, isl_val_copy(stride));
1303 a = isl_val_div(a, isl_val_copy(g));
1304 stride2 = isl_val_div(stride2, g);
1305 b = isl_val_mul(b, isl_val_copy(stride2));
1306 stride = isl_val_mul(stride, stride2);
1308 offset2 = isl_multi_aff_get_aff(build->offsets, pos);
1309 offset2 = isl_aff_scale_val(offset2, a);
1310 offset = isl_aff_scale_val(offset, b);
1311 offset = isl_aff_add(offset, offset2);
1314 build->strides = isl_vec_set_element_val(build->strides, pos, stride);
1315 build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset);
1316 if (!build->strides || !build->offsets)
1317 return isl_ast_build_free(build);
1319 return build;
1320 error:
1321 isl_val_free(stride);
1322 isl_aff_free(offset);
1323 return isl_ast_build_free(build);
1326 /* Return a set expressing the stride constraint at the current depth.
1328 * In particular, if the current iterator (i) is known to attain values
1330 * f + s a
1332 * where f is the offset and s is the stride, then the returned set
1333 * expresses the constraint
1335 * (f - i) mod s = 0
1337 __isl_give isl_set *isl_ast_build_get_stride_constraint(
1338 __isl_keep isl_ast_build *build)
1340 isl_aff *aff;
1341 isl_set *set;
1342 isl_val *stride;
1343 int pos;
1345 if (!build)
1346 return NULL;
1348 pos = build->depth;
1350 if (!isl_ast_build_has_stride(build, pos))
1351 return isl_set_universe(isl_ast_build_get_space(build, 1));
1353 stride = isl_ast_build_get_stride(build, pos);
1354 aff = isl_ast_build_get_offset(build, pos);
1355 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1);
1356 aff = isl_aff_mod_val(aff, stride);
1357 set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff));
1359 return set;
1362 /* Return the expansion implied by the stride and offset at the current
1363 * depth.
1365 * That is, return the mapping
1367 * [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1368 * -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]
1370 * where s is the stride at the current depth d and offset(i) is
1371 * the corresponding offset.
1373 __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
1374 __isl_keep isl_ast_build *build)
1376 isl_space *space;
1377 isl_multi_aff *ma;
1378 int pos;
1379 isl_aff *aff, *offset;
1380 isl_val *stride;
1382 if (!build)
1383 return NULL;
1385 pos = isl_ast_build_get_depth(build);
1386 space = isl_ast_build_get_space(build, 1);
1387 space = isl_space_map_from_set(space);
1388 ma = isl_multi_aff_identity(space);
1390 if (!isl_ast_build_has_stride(build, pos))
1391 return ma;
1393 offset = isl_ast_build_get_offset(build, pos);
1394 stride = isl_ast_build_get_stride(build, pos);
1395 aff = isl_multi_aff_get_aff(ma, pos);
1396 aff = isl_aff_scale_val(aff, stride);
1397 aff = isl_aff_add(aff, offset);
1398 ma = isl_multi_aff_set_aff(ma, pos, aff);
1400 return ma;
1403 /* Add constraints corresponding to any previously detected
1404 * stride on the current dimension to build->domain.
1406 __isl_give isl_ast_build *isl_ast_build_include_stride(
1407 __isl_take isl_ast_build *build)
1409 isl_set *set;
1411 if (!build)
1412 return NULL;
1413 if (!isl_ast_build_has_stride(build, build->depth))
1414 return build;
1415 build = isl_ast_build_cow(build);
1416 if (!build)
1417 return NULL;
1419 set = isl_ast_build_get_stride_constraint(build);
1421 build->domain = isl_set_intersect(build->domain, isl_set_copy(set));
1422 build->generated = isl_set_intersect(build->generated, set);
1423 if (!build->domain || !build->generated)
1424 return isl_ast_build_free(build);
1426 return build;
1429 /* Information used inside detect_stride.
1431 * "build" may be updated by detect_stride to include stride information.
1432 * "pos" is equal to build->depth.
1434 struct isl_detect_stride_data {
1435 isl_ast_build *build;
1436 int pos;
1439 /* Check if constraint "c" imposes any stride on dimension data->pos
1440 * and, if so, update the stride information in data->build.
1442 * In order to impose a stride on the dimension, "c" needs to be an equality
1443 * and it needs to involve the dimension. Note that "c" may also be
1444 * a div constraint and thus an inequality that we cannot use.
1446 * Let c be of the form
1448 * h(p) + g * v * i + g * stride * f(alpha) = 0
1450 * with h(p) an expression in terms of the parameters and outer dimensions
1451 * and f(alpha) an expression in terms of the existentially quantified
1452 * variables. Note that the inner dimensions have been eliminated so
1453 * they do not appear in "c".
1455 * If "stride" is not zero and not one, then it represents a non-trivial stride
1456 * on "i". We compute a and b such that
1458 * a v + b stride = 1
1460 * We have
1462 * g v i = -h(p) + g stride f(alpha)
1464 * a g v i = -a h(p) + g stride f(alpha)
1466 * a g v i + b g stride i = -a h(p) + g stride * (...)
1468 * g i = -a h(p) + g stride * (...)
1470 * i = -a h(p)/g + stride * (...)
1472 * The expression "-a h(p)/g" can therefore be used as offset.
1474 static isl_stat detect_stride(__isl_take isl_constraint *c, void *user)
1476 struct isl_detect_stride_data *data = user;
1477 int i, n_div;
1478 isl_ctx *ctx;
1479 isl_val *v, *stride, *m;
1481 if (!isl_constraint_is_equality(c) ||
1482 !isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1)) {
1483 isl_constraint_free(c);
1484 return isl_stat_ok;
1487 ctx = isl_constraint_get_ctx(c);
1488 stride = isl_val_zero(ctx);
1489 n_div = isl_constraint_dim(c, isl_dim_div);
1490 for (i = 0; i < n_div; ++i) {
1491 v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
1492 stride = isl_val_gcd(stride, v);
1495 v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
1496 m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
1497 stride = isl_val_div(stride, isl_val_copy(m));
1498 v = isl_val_div(v, isl_val_copy(m));
1500 if (!isl_val_is_zero(stride) && !isl_val_is_one(stride)) {
1501 isl_aff *aff;
1502 isl_val *gcd, *a, *b;
1504 gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);
1505 isl_val_free(gcd);
1506 isl_val_free(b);
1508 aff = isl_constraint_get_aff(c);
1509 for (i = 0; i < n_div; ++i)
1510 aff = isl_aff_set_coefficient_si(aff,
1511 isl_dim_div, i, 0);
1512 aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
1513 a = isl_val_neg(a);
1514 aff = isl_aff_scale_val(aff, a);
1515 aff = isl_aff_scale_down_val(aff, m);
1516 data->build = set_stride(data->build, stride, aff);
1517 } else {
1518 isl_val_free(stride);
1519 isl_val_free(m);
1520 isl_val_free(v);
1523 isl_constraint_free(c);
1524 return isl_stat_ok;
1527 /* Check if the constraints in "set" imply any stride on the current
1528 * dimension and, if so, record the stride information in "build"
1529 * and return the updated "build".
1531 * We compute the affine hull and then check if any of the constraints
1532 * in the hull imposes any stride on the current dimension.
1534 * We assume that inner dimensions have been eliminated from "set"
1535 * by the caller. This is needed because the common stride
1536 * may be imposed by different inner dimensions on different parts of
1537 * the domain.
1539 __isl_give isl_ast_build *isl_ast_build_detect_strides(
1540 __isl_take isl_ast_build *build, __isl_take isl_set *set)
1542 isl_basic_set *hull;
1543 struct isl_detect_stride_data data;
1545 if (!build)
1546 goto error;
1548 data.build = build;
1549 data.pos = isl_ast_build_get_depth(build);
1550 hull = isl_set_affine_hull(set);
1552 if (isl_basic_set_foreach_constraint(hull, &detect_stride, &data) < 0)
1553 data.build = isl_ast_build_free(data.build);
1555 isl_basic_set_free(hull);
1556 return data.build;
1557 error:
1558 isl_set_free(set);
1559 return NULL;
1562 struct isl_ast_build_involves_data {
1563 int depth;
1564 int involves;
1567 /* Check if "map" involves the input dimension data->depth.
1569 static isl_stat involves_depth(__isl_take isl_map *map, void *user)
1571 struct isl_ast_build_involves_data *data = user;
1573 data->involves = isl_map_involves_dims(map, isl_dim_in, data->depth, 1);
1574 isl_map_free(map);
1576 if (data->involves < 0 || data->involves)
1577 return isl_stat_error;
1578 return isl_stat_ok;
1581 /* Do any options depend on the value of the dimension at the current depth?
1583 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build)
1585 struct isl_ast_build_involves_data data;
1587 if (!build)
1588 return -1;
1590 data.depth = build->depth;
1591 data.involves = 0;
1593 if (isl_union_map_foreach_map(build->options,
1594 &involves_depth, &data) < 0) {
1595 if (data.involves < 0 || !data.involves)
1596 return -1;
1599 return data.involves;
1602 /* Construct the map
1604 * { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1606 * with "space" the parameter space of the constructed map.
1608 static __isl_give isl_map *construct_insertion_map(__isl_take isl_space *space,
1609 int pos)
1611 isl_constraint *c;
1612 isl_basic_map *bmap1, *bmap2;
1614 space = isl_space_set_from_params(space);
1615 space = isl_space_add_dims(space, isl_dim_set, 1);
1616 space = isl_space_map_from_set(space);
1617 c = isl_constraint_alloc_equality(isl_local_space_from_space(space));
1618 c = isl_constraint_set_coefficient_si(c, isl_dim_in, 0, 1);
1619 c = isl_constraint_set_coefficient_si(c, isl_dim_out, 0, -1);
1620 bmap1 = isl_basic_map_from_constraint(isl_constraint_copy(c));
1621 c = isl_constraint_set_constant_si(c, 1);
1622 bmap2 = isl_basic_map_from_constraint(c);
1624 bmap1 = isl_basic_map_upper_bound_si(bmap1, isl_dim_in, 0, pos - 1);
1625 bmap2 = isl_basic_map_lower_bound_si(bmap2, isl_dim_in, 0, pos);
1627 return isl_basic_map_union(bmap1, bmap2);
1630 static const char *option_str[] = {
1631 [isl_ast_loop_atomic] = "atomic",
1632 [isl_ast_loop_unroll] = "unroll",
1633 [isl_ast_loop_separate] = "separate"
1636 /* Update the "options" to reflect the insertion of a dimension
1637 * at position "pos" in the schedule domain space.
1638 * "space" is the original domain space before the insertion and
1639 * may be named and/or structured.
1641 * The (relevant) input options all have "space" as domain, which
1642 * has to be mapped to the extended space.
1643 * The values of the ranges also refer to the schedule domain positions
1644 * and they therefore also need to be adjusted. In particular, values
1645 * smaller than pos do not need to change, while values greater than or
1646 * equal to pos need to be incremented.
1647 * That is, we need to apply the following map.
1649 * { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1650 * unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1651 * separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1652 * separation_class[[i] -> [c]]
1653 * -> separation_class[[i] -> [c]] : i < pos;
1654 * separation_class[[i] -> [c]]
1655 * -> separation_class[[i + 1] -> [c]] : i >= pos }
1657 static __isl_give isl_union_map *options_insert_dim(
1658 __isl_take isl_union_map *options, __isl_take isl_space *space, int pos)
1660 isl_map *map;
1661 isl_union_map *insertion;
1662 enum isl_ast_loop_type type;
1663 const char *name = "separation_class";
1665 space = isl_space_map_from_set(space);
1666 map = isl_map_identity(space);
1667 map = isl_map_insert_dims(map, isl_dim_out, pos, 1);
1668 options = isl_union_map_apply_domain(options,
1669 isl_union_map_from_map(map));
1671 if (!options)
1672 return NULL;
1674 map = construct_insertion_map(isl_union_map_get_space(options), pos);
1676 insertion = isl_union_map_empty(isl_union_map_get_space(options));
1678 for (type = isl_ast_loop_atomic;
1679 type <= isl_ast_loop_separate; ++type) {
1680 isl_map *map_type = isl_map_copy(map);
1681 const char *name = option_str[type];
1682 map_type = isl_map_set_tuple_name(map_type, isl_dim_in, name);
1683 map_type = isl_map_set_tuple_name(map_type, isl_dim_out, name);
1684 insertion = isl_union_map_add_map(insertion, map_type);
1687 map = isl_map_product(map, isl_map_identity(isl_map_get_space(map)));
1688 map = isl_map_set_tuple_name(map, isl_dim_in, name);
1689 map = isl_map_set_tuple_name(map, isl_dim_out, name);
1690 insertion = isl_union_map_add_map(insertion, map);
1692 options = isl_union_map_apply_range(options, insertion);
1694 return options;
1697 /* If we are generating an AST from a schedule tree (build->node is set),
1698 * then update the loop AST generation types
1699 * to reflect the insertion of a dimension at (global) position "pos"
1700 * in the schedule domain space.
1701 * We do not need to adjust any isolate option since we would not be inserting
1702 * any dimensions if there were any isolate option.
1704 static __isl_give isl_ast_build *node_insert_dim(
1705 __isl_take isl_ast_build *build, int pos)
1707 int i;
1708 int local_pos;
1709 enum isl_ast_loop_type *loop_type;
1710 isl_ctx *ctx;
1712 build = isl_ast_build_cow(build);
1713 if (!build)
1714 return NULL;
1715 if (!build->node)
1716 return build;
1718 ctx = isl_ast_build_get_ctx(build);
1719 local_pos = pos - build->outer_pos;
1720 loop_type = isl_realloc_array(ctx, build->loop_type,
1721 enum isl_ast_loop_type, build->n + 1);
1722 if (!loop_type)
1723 return isl_ast_build_free(build);
1724 build->loop_type = loop_type;
1725 for (i = build->n - 1; i >= local_pos; --i)
1726 loop_type[i + 1] = loop_type[i];
1727 loop_type[local_pos] = isl_ast_loop_default;
1728 build->n++;
1730 return build;
1733 /* Insert a single dimension in the schedule domain at position "pos".
1734 * The new dimension is given an isl_id with the empty string as name.
1736 * The main difficulty is updating build->options to reflect the
1737 * extra dimension. This is handled in options_insert_dim.
1739 * Note that because of the dimension manipulations, the resulting
1740 * schedule domain space will always be unnamed and unstructured.
1741 * However, the original schedule domain space may be named and/or
1742 * structured, so we have to take this possibility into account
1743 * while performing the transformations.
1745 * Since the inserted schedule dimension is used by the caller
1746 * to differentiate between different domain spaces, there is
1747 * no longer a uniform mapping from the internal schedule space
1748 * to the input schedule space. The internal2input mapping is
1749 * therefore removed.
1751 __isl_give isl_ast_build *isl_ast_build_insert_dim(
1752 __isl_take isl_ast_build *build, int pos)
1754 isl_ctx *ctx;
1755 isl_space *space, *ma_space;
1756 isl_id *id;
1757 isl_multi_aff *ma;
1759 build = isl_ast_build_cow(build);
1760 if (!build)
1761 return NULL;
1763 ctx = isl_ast_build_get_ctx(build);
1764 id = isl_id_alloc(ctx, "", NULL);
1765 if (!build->node)
1766 space = isl_ast_build_get_space(build, 1);
1767 build->iterators = isl_id_list_insert(build->iterators, pos, id);
1768 build->domain = isl_set_insert_dims(build->domain,
1769 isl_dim_set, pos, 1);
1770 build->generated = isl_set_insert_dims(build->generated,
1771 isl_dim_set, pos, 1);
1772 build->pending = isl_set_insert_dims(build->pending,
1773 isl_dim_set, pos, 1);
1774 build->strides = isl_vec_insert_els(build->strides, pos, 1);
1775 build->strides = isl_vec_set_element_si(build->strides, pos, 1);
1776 ma_space = isl_space_params(isl_multi_aff_get_space(build->offsets));
1777 ma_space = isl_space_set_from_params(ma_space);
1778 ma_space = isl_space_add_dims(ma_space, isl_dim_set, 1);
1779 ma_space = isl_space_map_from_set(ma_space);
1780 ma = isl_multi_aff_zero(isl_space_copy(ma_space));
1781 build->offsets = isl_multi_aff_splice(build->offsets, pos, pos, ma);
1782 ma = isl_multi_aff_identity(ma_space);
1783 build->values = isl_multi_aff_splice(build->values, pos, pos, ma);
1784 if (!build->node)
1785 build->options = options_insert_dim(build->options, space, pos);
1786 build->internal2input = isl_multi_aff_free(build->internal2input);
1788 if (!build->iterators || !build->domain || !build->generated ||
1789 !build->pending || !build->values ||
1790 !build->strides || !build->offsets || !build->options)
1791 return isl_ast_build_free(build);
1793 build = node_insert_dim(build, pos);
1795 return build;
1798 /* Scale down the current dimension by a factor of "m".
1799 * "umap" is an isl_union_map that implements the scaling down.
1800 * That is, it is of the form
1802 * { [.... i ....] -> [.... i' ....] : i = m i' }
1804 * This function is called right after the strides have been
1805 * detected, but before any constraints on the current dimension
1806 * have been included in build->domain.
1807 * We therefore only need to update stride, offset, the options and
1808 * the mapping from internal schedule space to the original schedule
1809 * space, if we are still keeping track of such a mapping.
1810 * The latter mapping is updated by plugging in
1811 * { [... i ...] -> [... m i ... ] }.
1813 __isl_give isl_ast_build *isl_ast_build_scale_down(
1814 __isl_take isl_ast_build *build, __isl_take isl_val *m,
1815 __isl_take isl_union_map *umap)
1817 isl_aff *aff;
1818 isl_val *v;
1819 int depth;
1821 build = isl_ast_build_cow(build);
1822 if (!build || !umap || !m)
1823 goto error;
1825 depth = build->depth;
1827 if (build->internal2input) {
1828 isl_space *space;
1829 isl_multi_aff *ma;
1830 isl_aff *aff;
1832 space = isl_multi_aff_get_space(build->internal2input);
1833 space = isl_space_map_from_set(isl_space_domain(space));
1834 ma = isl_multi_aff_identity(space);
1835 aff = isl_multi_aff_get_aff(ma, depth);
1836 aff = isl_aff_scale_val(aff, isl_val_copy(m));
1837 ma = isl_multi_aff_set_aff(ma, depth, aff);
1838 build->internal2input =
1839 isl_multi_aff_pullback_multi_aff(build->internal2input, ma);
1840 if (!build->internal2input)
1841 goto error;
1844 v = isl_vec_get_element_val(build->strides, depth);
1845 v = isl_val_div(v, isl_val_copy(m));
1846 build->strides = isl_vec_set_element_val(build->strides, depth, v);
1848 aff = isl_multi_aff_get_aff(build->offsets, depth);
1849 aff = isl_aff_scale_down_val(aff, m);
1850 build->offsets = isl_multi_aff_set_aff(build->offsets, depth, aff);
1851 build->options = isl_union_map_apply_domain(build->options, umap);
1852 if (!build->strides || !build->offsets || !build->options)
1853 return isl_ast_build_free(build);
1855 return build;
1856 error:
1857 isl_val_free(m);
1858 isl_union_map_free(umap);
1859 return isl_ast_build_free(build);
1862 /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1863 * If an isl_id with such a name already appears among the parameters
1864 * in build->domain, then adjust the name to "c%d_%d".
1866 static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first,
1867 __isl_keep isl_ast_build *build)
1869 int i;
1870 isl_id_list *names;
1872 names = isl_id_list_alloc(ctx, n);
1873 for (i = 0; i < n; ++i) {
1874 isl_id *id;
1876 id = generate_name(ctx, first + i, build);
1877 names = isl_id_list_add(names, id);
1880 return names;
1883 /* Embed "options" into the given isl_ast_build space.
1885 * This function is called from within a nested call to
1886 * isl_ast_build_node_from_schedule_map.
1887 * "options" refers to the additional schedule,
1888 * while space refers to both the space of the outer isl_ast_build and
1889 * that of the additional schedule.
1890 * Specifically, space is of the form
1892 * [I -> S]
1894 * while options lives in the space(s)
1896 * S -> *
1898 * We compute
1900 * [I -> S] -> S
1902 * and compose this with options, to obtain the new options
1903 * living in the space(s)
1905 * [I -> S] -> *
1907 static __isl_give isl_union_map *embed_options(
1908 __isl_take isl_union_map *options, __isl_take isl_space *space)
1910 isl_map *map;
1912 map = isl_map_universe(isl_space_unwrap(space));
1913 map = isl_map_range_map(map);
1915 options = isl_union_map_apply_range(
1916 isl_union_map_from_map(map), options);
1918 return options;
1921 /* Update "build" for use in a (possibly nested) code generation. That is,
1922 * extend "build" from an AST build on some domain O to an AST build
1923 * on domain [O -> S], with S corresponding to "space".
1924 * If the original domain is a parameter domain, then the new domain is
1925 * simply S.
1926 * "iterators" is a list of iterators for S, but the number of elements
1927 * may be smaller or greater than the number of set dimensions of S.
1928 * If "keep_iterators" is set, then any extra ids in build->iterators
1929 * are reused for S. Otherwise, these extra ids are dropped.
1931 * We first update build->outer_pos to the current depth.
1932 * This depth is zero in case this is the outermost code generation.
1934 * We then add additional ids such that the number of iterators is at least
1935 * equal to the dimension of the new build domain.
1937 * If the original domain is parametric, then we are constructing
1938 * an isl_ast_build for the outer code generation and we pass control
1939 * to isl_ast_build_init.
1941 * Otherwise, we adjust the fields of "build" to include "space".
1943 __isl_give isl_ast_build *isl_ast_build_product(
1944 __isl_take isl_ast_build *build, __isl_take isl_space *space)
1946 isl_ctx *ctx;
1947 isl_vec *strides;
1948 isl_set *set;
1949 isl_multi_aff *embedding;
1950 int dim, n_it;
1952 build = isl_ast_build_cow(build);
1953 if (!build)
1954 goto error;
1956 build->outer_pos = build->depth;
1958 ctx = isl_ast_build_get_ctx(build);
1959 dim = isl_set_dim(build->domain, isl_dim_set);
1960 dim += isl_space_dim(space, isl_dim_set);
1961 n_it = isl_id_list_n_id(build->iterators);
1962 if (n_it < dim) {
1963 isl_id_list *l;
1964 l = generate_names(ctx, dim - n_it, n_it, build);
1965 build->iterators = isl_id_list_concat(build->iterators, l);
1968 if (isl_set_is_params(build->domain))
1969 return isl_ast_build_init(build, space);
1971 set = isl_set_universe(isl_space_copy(space));
1972 build->domain = isl_set_product(build->domain, isl_set_copy(set));
1973 build->pending = isl_set_product(build->pending, isl_set_copy(set));
1974 build->generated = isl_set_product(build->generated, set);
1976 strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
1977 strides = isl_vec_set_si(strides, 1);
1978 build->strides = isl_vec_concat(build->strides, strides);
1980 space = isl_space_map_from_set(space);
1981 build->offsets = isl_multi_aff_align_params(build->offsets,
1982 isl_space_copy(space));
1983 build->offsets = isl_multi_aff_product(build->offsets,
1984 isl_multi_aff_zero(isl_space_copy(space)));
1985 build->values = isl_multi_aff_align_params(build->values,
1986 isl_space_copy(space));
1987 embedding = isl_multi_aff_identity(space);
1988 build->values = isl_multi_aff_product(build->values,
1989 isl_multi_aff_copy(embedding));
1990 if (build->internal2input) {
1991 build->internal2input =
1992 isl_multi_aff_product(build->internal2input, embedding);
1993 build->internal2input =
1994 isl_multi_aff_flatten_range(build->internal2input);
1995 if (!build->internal2input)
1996 return isl_ast_build_free(build);
1997 } else {
1998 isl_multi_aff_free(embedding);
2001 space = isl_ast_build_get_space(build, 1);
2002 build->options = embed_options(build->options, space);
2004 if (!build->iterators || !build->domain || !build->generated ||
2005 !build->pending || !build->values ||
2006 !build->strides || !build->offsets || !build->options)
2007 return isl_ast_build_free(build);
2009 return build;
2010 error:
2011 isl_ast_build_free(build);
2012 isl_space_free(space);
2013 return NULL;
2016 /* Does "aff" only attain non-negative values over build->domain?
2017 * That is, does it not attain any negative values?
2019 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
2020 __isl_keep isl_aff *aff)
2022 isl_set *test;
2023 int empty;
2025 if (!build)
2026 return -1;
2028 aff = isl_aff_copy(aff);
2029 test = isl_set_from_basic_set(isl_aff_neg_basic_set(aff));
2030 test = isl_set_intersect(test, isl_set_copy(build->domain));
2031 empty = isl_set_is_empty(test);
2032 isl_set_free(test);
2034 return empty;
2037 /* Does the dimension at (internal) position "pos" have a non-trivial stride?
2039 isl_bool isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos)
2041 isl_val *v;
2042 isl_bool has_stride;
2044 if (!build)
2045 return isl_bool_error;
2047 v = isl_vec_get_element_val(build->strides, pos);
2048 has_stride = isl_bool_not(isl_val_is_one(v));
2049 isl_val_free(v);
2051 return has_stride;
2054 /* Given that the dimension at position "pos" takes on values
2056 * f + s a
2058 * with a an integer, return s through *stride.
2060 __isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build,
2061 int pos)
2063 if (!build)
2064 return NULL;
2066 return isl_vec_get_element_val(build->strides, pos);
2069 /* Given that the dimension at position "pos" takes on values
2071 * f + s a
2073 * with a an integer, return f.
2075 __isl_give isl_aff *isl_ast_build_get_offset(
2076 __isl_keep isl_ast_build *build, int pos)
2078 if (!build)
2079 return NULL;
2081 return isl_multi_aff_get_aff(build->offsets, pos);
2084 /* Is the dimension at position "pos" known to attain only a single
2085 * value that, moreover, can be described by a single affine expression
2086 * in terms of the outer dimensions and parameters?
2088 * If not, then the corresponding affine expression in build->values
2089 * is set to be equal to the same input dimension.
2090 * Otherwise, it is set to the requested expression in terms of
2091 * outer dimensions and parameters.
2093 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,
2094 int pos)
2096 isl_aff *aff;
2097 int involves;
2099 if (!build)
2100 return -1;
2102 aff = isl_multi_aff_get_aff(build->values, pos);
2103 involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);
2104 isl_aff_free(aff);
2106 if (involves < 0)
2107 return -1;
2109 return !involves;
2112 /* Plug in the known values (fixed affine expressions in terms of
2113 * parameters and outer loop iterators) of all loop iterators
2114 * in the domain of "umap".
2116 * We simply precompose "umap" with build->values.
2118 __isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(
2119 __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap)
2121 isl_multi_aff *values;
2123 if (!build)
2124 return isl_union_map_free(umap);
2126 values = isl_multi_aff_copy(build->values);
2127 umap = isl_union_map_preimage_domain_multi_aff(umap, values);
2129 return umap;
2132 /* Is the current dimension known to attain only a single value?
2134 int isl_ast_build_has_value(__isl_keep isl_ast_build *build)
2136 if (!build)
2137 return -1;
2139 return build->value != NULL;
2142 /* Simplify the basic set "bset" based on what we know about
2143 * the iterators of already generated loops.
2145 * "bset" is assumed to live in the (internal) schedule domain.
2147 __isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
2148 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
2150 if (!build)
2151 goto error;
2153 bset = isl_basic_set_preimage_multi_aff(bset,
2154 isl_multi_aff_copy(build->values));
2155 bset = isl_basic_set_gist(bset,
2156 isl_set_simple_hull(isl_set_copy(build->domain)));
2158 return bset;
2159 error:
2160 isl_basic_set_free(bset);
2161 return NULL;
2164 /* Simplify the set "set" based on what we know about
2165 * the iterators of already generated loops.
2167 * "set" is assumed to live in the (internal) schedule domain.
2169 __isl_give isl_set *isl_ast_build_compute_gist(
2170 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2172 if (!build)
2173 goto error;
2175 if (!isl_set_is_params(set))
2176 set = isl_set_preimage_multi_aff(set,
2177 isl_multi_aff_copy(build->values));
2178 set = isl_set_gist(set, isl_set_copy(build->domain));
2180 return set;
2181 error:
2182 isl_set_free(set);
2183 return NULL;
2186 /* Include information about what we know about the iterators of
2187 * already generated loops to "set".
2189 * We currently only plug in the known affine values of outer loop
2190 * iterators.
2191 * In principle we could also introduce equalities or even other
2192 * constraints implied by the intersection of "set" and build->domain.
2194 __isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build,
2195 __isl_take isl_set *set)
2197 if (!build)
2198 return isl_set_free(set);
2200 return isl_set_preimage_multi_aff(set,
2201 isl_multi_aff_copy(build->values));
2204 /* Plug in the known affine values of outer loop iterators in "bset".
2206 __isl_give isl_basic_set *isl_ast_build_specialize_basic_set(
2207 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
2209 if (!build)
2210 return isl_basic_set_free(bset);
2212 return isl_basic_set_preimage_multi_aff(bset,
2213 isl_multi_aff_copy(build->values));
2216 /* Simplify the map "map" based on what we know about
2217 * the iterators of already generated loops.
2219 * The domain of "map" is assumed to live in the (internal) schedule domain.
2221 __isl_give isl_map *isl_ast_build_compute_gist_map_domain(
2222 __isl_keep isl_ast_build *build, __isl_take isl_map *map)
2224 if (!build)
2225 goto error;
2227 map = isl_map_gist_domain(map, isl_set_copy(build->domain));
2229 return map;
2230 error:
2231 isl_map_free(map);
2232 return NULL;
2235 /* Simplify the affine expression "aff" based on what we know about
2236 * the iterators of already generated loops.
2238 * The domain of "aff" is assumed to live in the (internal) schedule domain.
2240 __isl_give isl_aff *isl_ast_build_compute_gist_aff(
2241 __isl_keep isl_ast_build *build, __isl_take isl_aff *aff)
2243 if (!build)
2244 goto error;
2246 aff = isl_aff_gist(aff, isl_set_copy(build->domain));
2248 return aff;
2249 error:
2250 isl_aff_free(aff);
2251 return NULL;
2254 /* Simplify the piecewise affine expression "aff" based on what we know about
2255 * the iterators of already generated loops.
2257 * The domain of "pa" is assumed to live in the (internal) schedule domain.
2259 __isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(
2260 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2262 if (!build)
2263 goto error;
2265 if (!isl_set_is_params(build->domain))
2266 pa = isl_pw_aff_pullback_multi_aff(pa,
2267 isl_multi_aff_copy(build->values));
2268 pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain));
2270 return pa;
2271 error:
2272 isl_pw_aff_free(pa);
2273 return NULL;
2276 /* Simplify the piecewise multi-affine expression "aff" based on what
2277 * we know about the iterators of already generated loops.
2279 * The domain of "pma" is assumed to live in the (internal) schedule domain.
2281 __isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(
2282 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2284 if (!build)
2285 goto error;
2287 pma = isl_pw_multi_aff_pullback_multi_aff(pma,
2288 isl_multi_aff_copy(build->values));
2289 pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain));
2291 return pma;
2292 error:
2293 isl_pw_multi_aff_free(pma);
2294 return NULL;
2297 /* Extract the schedule domain of the given type from build->options
2298 * at the current depth.
2300 * In particular, find the subset of build->options that is of
2301 * the following form
2303 * schedule_domain -> type[depth]
2305 * and return the corresponding domain, after eliminating inner dimensions
2306 * and divs that depend on the current dimension.
2308 * Note that the domain of build->options has been reformulated
2309 * in terms of the internal build space in embed_options,
2310 * but the position is still that within the current code generation.
2312 __isl_give isl_set *isl_ast_build_get_option_domain(
2313 __isl_keep isl_ast_build *build, enum isl_ast_loop_type type)
2315 const char *name;
2316 isl_space *space;
2317 isl_map *option;
2318 isl_set *domain;
2319 int local_pos;
2321 if (!build)
2322 return NULL;
2324 name = option_str[type];
2325 local_pos = build->depth - build->outer_pos;
2327 space = isl_ast_build_get_space(build, 1);
2328 space = isl_space_from_domain(space);
2329 space = isl_space_add_dims(space, isl_dim_out, 1);
2330 space = isl_space_set_tuple_name(space, isl_dim_out, name);
2332 option = isl_union_map_extract_map(build->options, space);
2333 option = isl_map_fix_si(option, isl_dim_out, 0, local_pos);
2335 domain = isl_map_domain(option);
2336 domain = isl_ast_build_eliminate(build, domain);
2338 return domain;
2341 /* How does the user want the current schedule dimension to be generated?
2342 * These choices have been extracted from the schedule node
2343 * in extract_loop_types and stored in build->loop_type.
2344 * They have been updated to reflect any dimension insertion in
2345 * node_insert_dim.
2346 * Return isl_ast_domain_error on error.
2348 * If "isolated" is set, then we get the loop AST generation type
2349 * directly from the band node since node_insert_dim cannot have been
2350 * called on a band with the isolate option.
2352 enum isl_ast_loop_type isl_ast_build_get_loop_type(
2353 __isl_keep isl_ast_build *build, int isolated)
2355 int local_pos;
2356 isl_ctx *ctx;
2358 if (!build)
2359 return isl_ast_loop_error;
2360 ctx = isl_ast_build_get_ctx(build);
2361 if (!build->node)
2362 isl_die(ctx, isl_error_internal,
2363 "only works for schedule tree based AST generation",
2364 return isl_ast_loop_error);
2366 local_pos = build->depth - build->outer_pos;
2367 if (!isolated)
2368 return build->loop_type[local_pos];
2369 return isl_schedule_node_band_member_get_isolate_ast_loop_type(
2370 build->node, local_pos);
2373 /* Extract the isolated set from the isolate option, if any,
2374 * and store in the build.
2375 * If there is no isolate option, then the isolated set is
2376 * set to the empty set.
2378 * The isolate option is of the form
2380 * isolate[[outer bands] -> current_band]
2382 * We flatten this set and then map it back to the internal
2383 * schedule space.
2385 * If we have already extracted the isolated set
2386 * or if internal2input is no longer set, then we do not
2387 * need to do anything. In the latter case, we know
2388 * that the current band cannot have any isolate option.
2390 __isl_give isl_ast_build *isl_ast_build_extract_isolated(
2391 __isl_take isl_ast_build *build)
2393 isl_set *isolated;
2395 if (!build)
2396 return NULL;
2397 if (!build->internal2input)
2398 return build;
2399 if (build->isolated)
2400 return build;
2402 build = isl_ast_build_cow(build);
2403 if (!build)
2404 return NULL;
2406 isolated = isl_schedule_node_band_get_ast_isolate_option(build->node);
2407 isolated = isl_set_flatten(isolated);
2408 isolated = isl_set_preimage_multi_aff(isolated,
2409 isl_multi_aff_copy(build->internal2input));
2411 build->isolated = isolated;
2412 if (!build->isolated)
2413 return isl_ast_build_free(build);
2415 return build;
2418 /* Does "build" have a non-empty isolated set?
2420 * The caller is assumed to have called isl_ast_build_extract_isolated first.
2422 int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build)
2424 int empty;
2426 if (!build)
2427 return -1;
2428 if (!build->internal2input)
2429 return 0;
2430 if (!build->isolated)
2431 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2432 "isolated set not extracted yet", return -1);
2434 empty = isl_set_plain_is_empty(build->isolated);
2435 return empty < 0 ? -1 : !empty;
2438 /* Return a copy of the isolated set of "build".
2440 * The caller is assume to have called isl_ast_build_has_isolated first,
2441 * with this function returning true.
2442 * In particular, this function should not be called if we are no
2443 * longer keeping track of internal2input (and there therefore could
2444 * not possibly be any isolated set).
2446 __isl_give isl_set *isl_ast_build_get_isolated(__isl_keep isl_ast_build *build)
2448 if (!build)
2449 return NULL;
2450 if (!build->internal2input)
2451 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2452 "build cannot have isolated set", return NULL);
2454 return isl_set_copy(build->isolated);
2457 /* Extract the separation class mapping at the current depth.
2459 * In particular, find and return the subset of build->options that is of
2460 * the following form
2462 * schedule_domain -> separation_class[[depth] -> [class]]
2464 * The caller is expected to eliminate inner dimensions from the domain.
2466 * Note that the domain of build->options has been reformulated
2467 * in terms of the internal build space in embed_options,
2468 * but the position is still that within the current code generation.
2470 __isl_give isl_map *isl_ast_build_get_separation_class(
2471 __isl_keep isl_ast_build *build)
2473 isl_ctx *ctx;
2474 isl_space *space_sep, *space;
2475 isl_map *res;
2476 int local_pos;
2478 if (!build)
2479 return NULL;
2481 local_pos = build->depth - build->outer_pos;
2482 ctx = isl_ast_build_get_ctx(build);
2483 space_sep = isl_space_alloc(ctx, 0, 1, 1);
2484 space_sep = isl_space_wrap(space_sep);
2485 space_sep = isl_space_set_tuple_name(space_sep, isl_dim_set,
2486 "separation_class");
2487 space = isl_ast_build_get_space(build, 1);
2488 space_sep = isl_space_align_params(space_sep, isl_space_copy(space));
2489 space = isl_space_map_from_domain_and_range(space, space_sep);
2491 res = isl_union_map_extract_map(build->options, space);
2492 res = isl_map_fix_si(res, isl_dim_out, 0, local_pos);
2493 res = isl_map_coalesce(res);
2495 return res;
2498 /* Eliminate dimensions inner to the current dimension.
2500 __isl_give isl_set *isl_ast_build_eliminate_inner(
2501 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2503 int dim;
2504 int depth;
2506 if (!build)
2507 return isl_set_free(set);
2509 dim = isl_set_dim(set, isl_dim_set);
2510 depth = build->depth;
2511 set = isl_set_detect_equalities(set);
2512 set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1));
2514 return set;
2517 /* Eliminate unknown divs and divs that depend on the current dimension.
2519 * Note that during the elimination of unknown divs, we may discover
2520 * an explicit representation of some other unknown divs, which may
2521 * depend on the current dimension. We therefore need to eliminate
2522 * unknown divs first.
2524 __isl_give isl_set *isl_ast_build_eliminate_divs(
2525 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2527 int depth;
2529 if (!build)
2530 return isl_set_free(set);
2532 set = isl_set_remove_unknown_divs(set);
2533 depth = build->depth;
2534 set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1);
2536 return set;
2539 /* Eliminate dimensions inner to the current dimension as well as
2540 * unknown divs and divs that depend on the current dimension.
2541 * The result then consists only of constraints that are independent
2542 * of the current dimension and upper and lower bounds on the current
2543 * dimension.
2545 __isl_give isl_set *isl_ast_build_eliminate(
2546 __isl_keep isl_ast_build *build, __isl_take isl_set *domain)
2548 domain = isl_ast_build_eliminate_inner(build, domain);
2549 domain = isl_ast_build_eliminate_divs(build, domain);
2550 return domain;
2553 /* Replace build->single_valued by "sv".
2555 __isl_give isl_ast_build *isl_ast_build_set_single_valued(
2556 __isl_take isl_ast_build *build, int sv)
2558 if (!build)
2559 return build;
2560 if (build->single_valued == sv)
2561 return build;
2562 build = isl_ast_build_cow(build);
2563 if (!build)
2564 return build;
2565 build->single_valued = sv;
2567 return build;