isl_affine_hull.c: uset_affine_hull: avoid use of isl_basic_set_universe_like
[isl.git] / isl_ast_build.c
blobdc54b9772c9c5061a9d104bfec10d72d0e358e60
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>
22 /* Construct a map that isolates the current dimension.
24 * Essentially, the current dimension of "set" is moved to the single output
25 * dimension in the result, with the current dimension in the domain replaced
26 * by an unconstrained variable.
28 __isl_give isl_map *isl_ast_build_map_to_iterator(
29 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
31 isl_map *map;
33 map = isl_map_from_domain(set);
34 map = isl_map_add_dims(map, isl_dim_out, 1);
36 if (!build)
37 return isl_map_free(map);
39 map = isl_map_equate(map, isl_dim_in, build->depth, isl_dim_out, 0);
40 map = isl_map_eliminate(map, isl_dim_in, build->depth, 1);
42 return map;
45 /* Initialize the information derived during the AST generation to default
46 * values for a schedule domain in "space".
48 * We also check that the remaining fields are not NULL so that
49 * the calling functions don't have to perform this test.
51 static __isl_give isl_ast_build *isl_ast_build_init_derived(
52 __isl_take isl_ast_build *build, __isl_take isl_space *space)
54 isl_ctx *ctx;
55 isl_vec *strides;
57 build = isl_ast_build_cow(build);
58 if (!build || !build->domain)
59 goto error;
61 ctx = isl_ast_build_get_ctx(build);
62 strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
63 strides = isl_vec_set_si(strides, 1);
65 isl_vec_free(build->strides);
66 build->strides = strides;
68 space = isl_space_map_from_set(space);
69 isl_multi_aff_free(build->offsets);
70 build->offsets = isl_multi_aff_zero(isl_space_copy(space));
71 isl_multi_aff_free(build->values);
72 build->values = isl_multi_aff_identity(isl_space_copy(space));
73 isl_multi_aff_free(build->internal2input);
74 build->internal2input = isl_multi_aff_identity(space);
76 if (!build->iterators || !build->domain || !build->generated ||
77 !build->pending || !build->values || !build->internal2input ||
78 !build->strides || !build->offsets || !build->options)
79 return isl_ast_build_free(build);
81 return build;
82 error:
83 isl_space_free(space);
84 return isl_ast_build_free(build);
87 /* Return an isl_id called "c%d", with "%d" set to "i".
88 * If an isl_id with such a name already appears among the parameters
89 * in build->domain, then adjust the name to "c%d_%d".
91 static __isl_give isl_id *generate_name(isl_ctx *ctx, int i,
92 __isl_keep isl_ast_build *build)
94 int j;
95 char name[16];
96 isl_set *dom = build->domain;
98 snprintf(name, sizeof(name), "c%d", i);
99 j = 0;
100 while (isl_set_find_dim_by_name(dom, isl_dim_param, name) >= 0)
101 snprintf(name, sizeof(name), "c%d_%d", i, j++);
102 return isl_id_alloc(ctx, name, NULL);
105 /* Create an isl_ast_build with "set" as domain.
107 * The input set is usually a parameter domain, but we currently allow it to
108 * be any kind of set. We set the domain of the returned isl_ast_build
109 * to "set" and initialize all the other fields to default values.
111 __isl_give isl_ast_build *isl_ast_build_from_context(__isl_take isl_set *set)
113 int i, n;
114 isl_ctx *ctx;
115 isl_space *space;
116 isl_ast_build *build;
118 set = isl_set_compute_divs(set);
119 if (!set)
120 return NULL;
122 ctx = isl_set_get_ctx(set);
124 build = isl_calloc_type(ctx, isl_ast_build);
125 if (!build)
126 goto error;
128 build->ref = 1;
129 build->domain = set;
130 build->generated = isl_set_copy(build->domain);
131 build->pending = isl_set_universe(isl_set_get_space(build->domain));
132 build->options = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
133 n = isl_set_dim(set, isl_dim_set);
134 build->depth = n;
135 build->iterators = isl_id_list_alloc(ctx, n);
136 for (i = 0; i < n; ++i) {
137 isl_id *id;
138 if (isl_set_has_dim_id(set, isl_dim_set, i))
139 id = isl_set_get_dim_id(set, isl_dim_set, i);
140 else
141 id = generate_name(ctx, i, build);
142 build->iterators = isl_id_list_add(build->iterators, id);
144 space = isl_set_get_space(set);
145 if (isl_space_is_params(space))
146 space = isl_space_set_from_params(space);
148 return isl_ast_build_init_derived(build, space);
149 error:
150 isl_set_free(set);
151 return NULL;
154 /* Create an isl_ast_build with a universe (parametric) context.
156 __isl_give isl_ast_build *isl_ast_build_alloc(isl_ctx *ctx)
158 isl_space *space;
159 isl_set *context;
161 space = isl_space_params_alloc(ctx, 0);
162 context = isl_set_universe(space);
164 return isl_ast_build_from_context(context);
167 __isl_give isl_ast_build *isl_ast_build_copy(__isl_keep isl_ast_build *build)
169 if (!build)
170 return NULL;
172 build->ref++;
173 return build;
176 __isl_give isl_ast_build *isl_ast_build_dup(__isl_keep isl_ast_build *build)
178 isl_ctx *ctx;
179 isl_ast_build *dup;
181 if (!build)
182 return NULL;
184 ctx = isl_ast_build_get_ctx(build);
185 dup = isl_calloc_type(ctx, isl_ast_build);
186 if (!dup)
187 return NULL;
189 dup->ref = 1;
190 dup->outer_pos = build->outer_pos;
191 dup->depth = build->depth;
192 dup->iterators = isl_id_list_copy(build->iterators);
193 dup->domain = isl_set_copy(build->domain);
194 dup->generated = isl_set_copy(build->generated);
195 dup->pending = isl_set_copy(build->pending);
196 dup->values = isl_multi_aff_copy(build->values);
197 dup->internal2input = isl_multi_aff_copy(build->internal2input);
198 dup->value = isl_pw_aff_copy(build->value);
199 dup->strides = isl_vec_copy(build->strides);
200 dup->offsets = isl_multi_aff_copy(build->offsets);
201 dup->executed = isl_union_map_copy(build->executed);
202 dup->single_valued = build->single_valued;
203 dup->options = isl_union_map_copy(build->options);
204 dup->at_each_domain = build->at_each_domain;
205 dup->at_each_domain_user = build->at_each_domain_user;
206 dup->before_each_for = build->before_each_for;
207 dup->before_each_for_user = build->before_each_for_user;
208 dup->after_each_for = build->after_each_for;
209 dup->after_each_for_user = build->after_each_for_user;
210 dup->before_each_mark = build->before_each_mark;
211 dup->before_each_mark_user = build->before_each_mark_user;
212 dup->after_each_mark = build->after_each_mark;
213 dup->after_each_mark_user = build->after_each_mark_user;
214 dup->create_leaf = build->create_leaf;
215 dup->create_leaf_user = build->create_leaf_user;
216 dup->node = isl_schedule_node_copy(build->node);
217 if (build->loop_type) {
218 int i;
220 dup->n = build->n;
221 dup->loop_type = isl_alloc_array(ctx,
222 enum isl_ast_loop_type, dup->n);
223 if (dup->n && !dup->loop_type)
224 return isl_ast_build_free(dup);
225 for (i = 0; i < dup->n; ++i)
226 dup->loop_type[i] = build->loop_type[i];
229 if (!dup->iterators || !dup->domain || !dup->generated ||
230 !dup->pending || !dup->values ||
231 !dup->strides || !dup->offsets || !dup->options ||
232 (build->internal2input && !dup->internal2input) ||
233 (build->executed && !dup->executed) ||
234 (build->value && !dup->value) ||
235 (build->node && !dup->node))
236 return isl_ast_build_free(dup);
238 return dup;
241 /* Align the parameters of "build" to those of "model", introducing
242 * additional parameters if needed.
244 __isl_give isl_ast_build *isl_ast_build_align_params(
245 __isl_take isl_ast_build *build, __isl_take isl_space *model)
247 build = isl_ast_build_cow(build);
248 if (!build)
249 goto error;
251 build->domain = isl_set_align_params(build->domain,
252 isl_space_copy(model));
253 build->generated = isl_set_align_params(build->generated,
254 isl_space_copy(model));
255 build->pending = isl_set_align_params(build->pending,
256 isl_space_copy(model));
257 build->values = isl_multi_aff_align_params(build->values,
258 isl_space_copy(model));
259 build->offsets = isl_multi_aff_align_params(build->offsets,
260 isl_space_copy(model));
261 build->options = isl_union_map_align_params(build->options,
262 isl_space_copy(model));
263 if (build->internal2input) {
264 build->internal2input =
265 isl_multi_aff_align_params(build->internal2input,
266 model);
267 if (!build->internal2input)
268 return isl_ast_build_free(build);
269 } else {
270 isl_space_free(model);
273 if (!build->domain || !build->values || !build->offsets ||
274 !build->options)
275 return isl_ast_build_free(build);
277 return build;
278 error:
279 isl_space_free(model);
280 return NULL;
283 __isl_give isl_ast_build *isl_ast_build_cow(__isl_take isl_ast_build *build)
285 if (!build)
286 return NULL;
288 if (build->ref == 1)
289 return build;
290 build->ref--;
291 return isl_ast_build_dup(build);
294 __isl_null isl_ast_build *isl_ast_build_free(
295 __isl_take isl_ast_build *build)
297 if (!build)
298 return NULL;
300 if (--build->ref > 0)
301 return NULL;
303 isl_id_list_free(build->iterators);
304 isl_set_free(build->domain);
305 isl_set_free(build->generated);
306 isl_set_free(build->pending);
307 isl_multi_aff_free(build->values);
308 isl_multi_aff_free(build->internal2input);
309 isl_pw_aff_free(build->value);
310 isl_vec_free(build->strides);
311 isl_multi_aff_free(build->offsets);
312 isl_multi_aff_free(build->schedule_map);
313 isl_union_map_free(build->executed);
314 isl_union_map_free(build->options);
315 isl_schedule_node_free(build->node);
316 free(build->loop_type);
317 isl_set_free(build->isolated);
319 free(build);
321 return NULL;
324 isl_ctx *isl_ast_build_get_ctx(__isl_keep isl_ast_build *build)
326 return build ? isl_set_get_ctx(build->domain) : NULL;
329 /* Replace build->options by "options".
331 __isl_give isl_ast_build *isl_ast_build_set_options(
332 __isl_take isl_ast_build *build, __isl_take isl_union_map *options)
334 build = isl_ast_build_cow(build);
336 if (!build || !options)
337 goto error;
339 isl_union_map_free(build->options);
340 build->options = options;
342 return build;
343 error:
344 isl_union_map_free(options);
345 return isl_ast_build_free(build);
348 /* Set the iterators for the next code generation.
350 * If we still have some iterators left from the previous code generation
351 * (if any) or if iterators have already been set by a previous
352 * call to this function, then we remove them first.
354 __isl_give isl_ast_build *isl_ast_build_set_iterators(
355 __isl_take isl_ast_build *build, __isl_take isl_id_list *iterators)
357 int dim, n_it;
359 build = isl_ast_build_cow(build);
360 if (!build)
361 goto error;
363 dim = isl_set_dim(build->domain, isl_dim_set);
364 n_it = isl_id_list_n_id(build->iterators);
365 if (n_it < dim)
366 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
367 "isl_ast_build in inconsistent state", goto error);
368 if (n_it > dim)
369 build->iterators = isl_id_list_drop(build->iterators,
370 dim, n_it - dim);
371 build->iterators = isl_id_list_concat(build->iterators, iterators);
372 if (!build->iterators)
373 return isl_ast_build_free(build);
375 return build;
376 error:
377 isl_id_list_free(iterators);
378 return isl_ast_build_free(build);
381 /* Set the "at_each_domain" callback of "build" to "fn".
383 __isl_give isl_ast_build *isl_ast_build_set_at_each_domain(
384 __isl_take isl_ast_build *build,
385 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
386 __isl_keep isl_ast_build *build, void *user), void *user)
388 build = isl_ast_build_cow(build);
390 if (!build)
391 return NULL;
393 build->at_each_domain = fn;
394 build->at_each_domain_user = user;
396 return build;
399 /* Set the "before_each_for" callback of "build" to "fn".
401 __isl_give isl_ast_build *isl_ast_build_set_before_each_for(
402 __isl_take isl_ast_build *build,
403 __isl_give isl_id *(*fn)(__isl_keep isl_ast_build *build,
404 void *user), void *user)
406 build = isl_ast_build_cow(build);
408 if (!build)
409 return NULL;
411 build->before_each_for = fn;
412 build->before_each_for_user = user;
414 return build;
417 /* Set the "after_each_for" callback of "build" to "fn".
419 __isl_give isl_ast_build *isl_ast_build_set_after_each_for(
420 __isl_take isl_ast_build *build,
421 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
422 __isl_keep isl_ast_build *build, void *user), void *user)
424 build = isl_ast_build_cow(build);
426 if (!build)
427 return NULL;
429 build->after_each_for = fn;
430 build->after_each_for_user = user;
432 return build;
435 /* Set the "before_each_mark" callback of "build" to "fn".
437 __isl_give isl_ast_build *isl_ast_build_set_before_each_mark(
438 __isl_take isl_ast_build *build,
439 int (*fn)(__isl_keep isl_id *mark, __isl_keep isl_ast_build *build,
440 void *user), void *user)
442 build = isl_ast_build_cow(build);
444 if (!build)
445 return NULL;
447 build->before_each_mark = fn;
448 build->before_each_mark_user = user;
450 return build;
453 /* Set the "after_each_mark" callback of "build" to "fn".
455 __isl_give isl_ast_build *isl_ast_build_set_after_each_mark(
456 __isl_take isl_ast_build *build,
457 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_node *node,
458 __isl_keep isl_ast_build *build, void *user), void *user)
460 build = isl_ast_build_cow(build);
462 if (!build)
463 return NULL;
465 build->after_each_mark = fn;
466 build->after_each_mark_user = user;
468 return build;
471 /* Set the "create_leaf" callback of "build" to "fn".
473 __isl_give isl_ast_build *isl_ast_build_set_create_leaf(
474 __isl_take isl_ast_build *build,
475 __isl_give isl_ast_node *(*fn)(__isl_take isl_ast_build *build,
476 void *user), void *user)
478 build = isl_ast_build_cow(build);
480 if (!build)
481 return NULL;
483 build->create_leaf = fn;
484 build->create_leaf_user = user;
486 return build;
489 /* Clear all information that is specific to this code generation
490 * and that is (probably) not meaningful to any nested code generation.
492 __isl_give isl_ast_build *isl_ast_build_clear_local_info(
493 __isl_take isl_ast_build *build)
495 isl_space *space;
497 build = isl_ast_build_cow(build);
498 if (!build)
499 return NULL;
501 space = isl_union_map_get_space(build->options);
502 isl_union_map_free(build->options);
503 build->options = isl_union_map_empty(space);
505 build->at_each_domain = NULL;
506 build->at_each_domain_user = NULL;
507 build->before_each_for = NULL;
508 build->before_each_for_user = NULL;
509 build->after_each_for = NULL;
510 build->after_each_for_user = NULL;
511 build->before_each_mark = NULL;
512 build->before_each_mark_user = NULL;
513 build->after_each_mark = NULL;
514 build->after_each_mark_user = NULL;
515 build->create_leaf = NULL;
516 build->create_leaf_user = NULL;
518 if (!build->options)
519 return isl_ast_build_free(build);
521 return build;
524 /* Have any loops been eliminated?
525 * That is, do any of the original schedule dimensions have a fixed
526 * value that has been substituted?
528 static int any_eliminated(isl_ast_build *build)
530 int i;
532 for (i = 0; i < build->depth; ++i)
533 if (isl_ast_build_has_affine_value(build, i))
534 return 1;
536 return 0;
539 /* Clear build->schedule_map.
540 * This function should be called whenever anything that might affect
541 * the result of isl_ast_build_get_schedule_map_multi_aff changes.
542 * In particular, it should be called when the depth is changed or
543 * when an iterator is determined to have a fixed value.
545 static void isl_ast_build_reset_schedule_map(__isl_keep isl_ast_build *build)
547 if (!build)
548 return;
549 isl_multi_aff_free(build->schedule_map);
550 build->schedule_map = NULL;
553 /* Do we need a (non-trivial) schedule map?
554 * That is, is the internal schedule space different from
555 * the external schedule space?
557 * The internal and external schedule spaces are only the same
558 * if code has been generated for the entire schedule and if none
559 * of the loops have been eliminated.
561 __isl_give int isl_ast_build_need_schedule_map(__isl_keep isl_ast_build *build)
563 int dim;
565 if (!build)
566 return -1;
568 dim = isl_set_dim(build->domain, isl_dim_set);
569 return build->depth != dim || any_eliminated(build);
572 /* Return a mapping from the internal schedule space to the external
573 * schedule space in the form of an isl_multi_aff.
574 * The internal schedule space originally corresponds to that of the
575 * input schedule. This may change during the code generation if
576 * if isl_ast_build_insert_dim is ever called.
577 * The external schedule space corresponds to the
578 * loops that have been generated.
580 * Currently, the only difference between the internal schedule domain
581 * and the external schedule domain is that some dimensions are projected
582 * out in the external schedule domain. In particular, the dimensions
583 * for which no code has been generated yet and the dimensions that correspond
584 * to eliminated loops.
586 * We cache a copy of the schedule_map in build->schedule_map.
587 * The cache is cleared through isl_ast_build_reset_schedule_map
588 * whenever anything changes that might affect the result of this function.
590 __isl_give isl_multi_aff *isl_ast_build_get_schedule_map_multi_aff(
591 __isl_keep isl_ast_build *build)
593 isl_space *space;
594 isl_multi_aff *ma;
596 if (!build)
597 return NULL;
598 if (build->schedule_map)
599 return isl_multi_aff_copy(build->schedule_map);
601 space = isl_ast_build_get_space(build, 1);
602 space = isl_space_map_from_set(space);
603 ma = isl_multi_aff_identity(space);
604 if (isl_ast_build_need_schedule_map(build)) {
605 int i;
606 int dim = isl_set_dim(build->domain, isl_dim_set);
607 ma = isl_multi_aff_drop_dims(ma, isl_dim_out,
608 build->depth, dim - build->depth);
609 for (i = build->depth - 1; i >= 0; --i)
610 if (isl_ast_build_has_affine_value(build, i))
611 ma = isl_multi_aff_drop_dims(ma,
612 isl_dim_out, i, 1);
615 build->schedule_map = ma;
616 return isl_multi_aff_copy(build->schedule_map);
619 /* Return a mapping from the internal schedule space to the external
620 * schedule space in the form of an isl_map.
622 __isl_give isl_map *isl_ast_build_get_schedule_map(
623 __isl_keep isl_ast_build *build)
625 isl_multi_aff *ma;
627 ma = isl_ast_build_get_schedule_map_multi_aff(build);
628 return isl_map_from_multi_aff(ma);
631 /* Return the position of the dimension in build->domain for which
632 * an AST node is currently being generated.
634 int isl_ast_build_get_depth(__isl_keep isl_ast_build *build)
636 return build ? build->depth : -1;
639 /* Prepare for generating code for the next level.
640 * In particular, increase the depth and reset any information
641 * that is local to the current depth.
643 __isl_give isl_ast_build *isl_ast_build_increase_depth(
644 __isl_take isl_ast_build *build)
646 build = isl_ast_build_cow(build);
647 if (!build)
648 return NULL;
649 build->depth++;
650 isl_ast_build_reset_schedule_map(build);
651 build->value = isl_pw_aff_free(build->value);
652 return build;
655 void isl_ast_build_dump(__isl_keep isl_ast_build *build)
657 if (!build)
658 return;
660 fprintf(stderr, "domain: ");
661 isl_set_dump(build->domain);
662 fprintf(stderr, "generated: ");
663 isl_set_dump(build->generated);
664 fprintf(stderr, "pending: ");
665 isl_set_dump(build->pending);
666 fprintf(stderr, "iterators: ");
667 isl_id_list_dump(build->iterators);
668 fprintf(stderr, "values: ");
669 isl_multi_aff_dump(build->values);
670 if (build->value) {
671 fprintf(stderr, "value: ");
672 isl_pw_aff_dump(build->value);
674 fprintf(stderr, "strides: ");
675 isl_vec_dump(build->strides);
676 fprintf(stderr, "offsets: ");
677 isl_multi_aff_dump(build->offsets);
678 fprintf(stderr, "internal2input: ");
679 isl_multi_aff_dump(build->internal2input);
682 /* Initialize "build" for AST construction in schedule space "space"
683 * in the case that build->domain is a parameter set.
685 * build->iterators is assumed to have been updated already.
687 static __isl_give isl_ast_build *isl_ast_build_init(
688 __isl_take isl_ast_build *build, __isl_take isl_space *space)
690 isl_set *set;
692 build = isl_ast_build_cow(build);
693 if (!build)
694 goto error;
696 set = isl_set_universe(isl_space_copy(space));
697 build->domain = isl_set_intersect_params(isl_set_copy(set),
698 build->domain);
699 build->pending = isl_set_intersect_params(isl_set_copy(set),
700 build->pending);
701 build->generated = isl_set_intersect_params(set, build->generated);
703 return isl_ast_build_init_derived(build, space);
704 error:
705 isl_ast_build_free(build);
706 isl_space_free(space);
707 return NULL;
710 /* Assign "aff" to *user and return -1, effectively extracting
711 * the first (and presumably only) affine expression in the isl_pw_aff
712 * on which this function is used.
714 static int extract_single_piece(__isl_take isl_set *set,
715 __isl_take isl_aff *aff, void *user)
717 isl_aff **p = user;
719 *p = aff;
720 isl_set_free(set);
722 return -1;
725 /* Intersect "set" with the stride constraint of "build", if any.
727 static __isl_give isl_set *intersect_stride_constraint(__isl_take isl_set *set,
728 __isl_keep isl_ast_build *build)
730 isl_set *stride;
732 if (!build)
733 return isl_set_free(set);
734 if (!isl_ast_build_has_stride(build, build->depth))
735 return set;
737 stride = isl_ast_build_get_stride_constraint(build);
738 return isl_set_intersect(set, stride);
741 /* Check if the given bounds on the current dimension (together with
742 * the stride constraint, if any) imply that
743 * this current dimension attains only a single value (in terms of
744 * parameters and outer dimensions).
745 * If so, we record it in build->value.
746 * If, moreover, this value can be represented as a single affine expression,
747 * then we also update build->values, effectively marking the current
748 * dimension as "eliminated".
750 * When computing the gist of the fixed value that can be represented
751 * as a single affine expression, it is important to only take into
752 * account the domain constraints in the original AST build and
753 * not the domain of the affine expression itself.
754 * Otherwise, a [i/3] is changed into a i/3 because we know that i
755 * is a multiple of 3, but then we end up not expressing anywhere
756 * in the context that i is a multiple of 3.
758 static __isl_give isl_ast_build *update_values(
759 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
761 int sv;
762 isl_pw_multi_aff *pma;
763 isl_aff *aff = NULL;
764 isl_map *it_map;
765 isl_set *set;
767 set = isl_set_from_basic_set(bounds);
768 set = isl_set_intersect(set, isl_set_copy(build->domain));
769 set = intersect_stride_constraint(set, build);
770 it_map = isl_ast_build_map_to_iterator(build, set);
772 sv = isl_map_is_single_valued(it_map);
773 if (sv < 0)
774 build = isl_ast_build_free(build);
775 if (!build || !sv) {
776 isl_map_free(it_map);
777 return build;
780 pma = isl_pw_multi_aff_from_map(it_map);
781 build->value = isl_pw_multi_aff_get_pw_aff(pma, 0);
782 build->value = isl_ast_build_compute_gist_pw_aff(build, build->value);
783 build->value = isl_pw_aff_coalesce(build->value);
784 isl_pw_multi_aff_free(pma);
786 if (!build->value)
787 return isl_ast_build_free(build);
789 if (isl_pw_aff_n_piece(build->value) != 1)
790 return build;
792 isl_pw_aff_foreach_piece(build->value, &extract_single_piece, &aff);
794 build->values = isl_multi_aff_set_aff(build->values, build->depth, aff);
795 if (!build->values)
796 return isl_ast_build_free(build);
797 isl_ast_build_reset_schedule_map(build);
798 return build;
801 /* Update the AST build based on the given loop bounds for
802 * the current dimension and the stride information available in the build.
804 * We first make sure that the bounds do not refer to any iterators
805 * that have already been eliminated.
806 * Then, we check if the bounds imply that the current iterator
807 * has a fixed value.
808 * If they do and if this fixed value can be expressed as a single
809 * affine expression, we eliminate the iterators from the bounds.
810 * Note that we cannot simply plug in this single value using
811 * isl_basic_set_preimage_multi_aff as the single value may only
812 * be defined on a subset of the domain. Plugging in the value
813 * would restrict the build domain to this subset, while this
814 * restriction may not be reflected in the generated code.
815 * Finally, we intersect build->domain with the updated bounds.
816 * We also add the stride constraint unless we have been able
817 * to find a fixed value expressed as a single affine expression.
819 * Note that the check for a fixed value in update_values requires
820 * us to intersect the bounds with the current build domain.
821 * When we intersect build->domain with the updated bounds in
822 * the final step, we make sure that these updated bounds have
823 * not been intersected with the old build->domain.
824 * Otherwise, we would indirectly intersect the build domain with itself,
825 * which can lead to inefficiencies, in particular if the build domain
826 * contains any unknown divs.
828 __isl_give isl_ast_build *isl_ast_build_set_loop_bounds(
829 __isl_take isl_ast_build *build, __isl_take isl_basic_set *bounds)
831 isl_set *set;
833 build = isl_ast_build_cow(build);
834 if (!build)
835 goto error;
837 bounds = isl_basic_set_preimage_multi_aff(bounds,
838 isl_multi_aff_copy(build->values));
839 build = update_values(build, isl_basic_set_copy(bounds));
840 if (!build)
841 goto error;
842 set = isl_set_from_basic_set(isl_basic_set_copy(bounds));
843 if (isl_ast_build_has_affine_value(build, build->depth)) {
844 set = isl_set_eliminate(set, isl_dim_set, build->depth, 1);
845 set = isl_set_compute_divs(set);
846 build->pending = isl_set_intersect(build->pending,
847 isl_set_copy(set));
848 build->domain = isl_set_intersect(build->domain, set);
849 } else {
850 isl_basic_set *generated, *pending;
852 pending = isl_basic_set_copy(bounds);
853 pending = isl_basic_set_drop_constraints_involving_dims(pending,
854 isl_dim_set, build->depth, 1);
855 build->pending = isl_set_intersect(build->pending,
856 isl_set_from_basic_set(pending));
857 generated = isl_basic_set_copy(bounds);
858 generated = isl_basic_set_drop_constraints_not_involving_dims(
859 generated, isl_dim_set, build->depth, 1);
860 build->generated = isl_set_intersect(build->generated,
861 isl_set_from_basic_set(generated));
862 build->domain = isl_set_intersect(build->domain, set);
863 build = isl_ast_build_include_stride(build);
864 if (!build)
865 goto error;
867 isl_basic_set_free(bounds);
869 if (!build->domain || !build->pending || !build->generated)
870 return isl_ast_build_free(build);
872 return build;
873 error:
874 isl_ast_build_free(build);
875 isl_basic_set_free(bounds);
876 return NULL;
879 /* Intersect build->domain with "set", where "set" is specified
880 * in terms of the internal schedule domain.
882 static __isl_give isl_ast_build *isl_ast_build_restrict_internal(
883 __isl_take isl_ast_build *build, __isl_take isl_set *set)
885 build = isl_ast_build_cow(build);
886 if (!build)
887 goto error;
889 set = isl_set_compute_divs(set);
890 build->domain = isl_set_intersect(build->domain, set);
891 build->domain = isl_set_coalesce(build->domain);
893 if (!build->domain)
894 return isl_ast_build_free(build);
896 return build;
897 error:
898 isl_ast_build_free(build);
899 isl_set_free(set);
900 return NULL;
903 /* Intersect build->generated and build->domain with "set",
904 * where "set" is specified in terms of the internal schedule domain.
906 __isl_give isl_ast_build *isl_ast_build_restrict_generated(
907 __isl_take isl_ast_build *build, __isl_take isl_set *set)
909 set = isl_set_compute_divs(set);
910 build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
911 build = isl_ast_build_cow(build);
912 if (!build)
913 goto error;
915 build->generated = isl_set_intersect(build->generated, set);
916 build->generated = isl_set_coalesce(build->generated);
918 if (!build->generated)
919 return isl_ast_build_free(build);
921 return build;
922 error:
923 isl_ast_build_free(build);
924 isl_set_free(set);
925 return NULL;
928 /* Replace the set of pending constraints by "guard", which is then
929 * no longer considered as pending.
930 * That is, add "guard" to the generated constraints and clear all pending
931 * constraints, making the domain equal to the generated constraints.
933 __isl_give isl_ast_build *isl_ast_build_replace_pending_by_guard(
934 __isl_take isl_ast_build *build, __isl_take isl_set *guard)
936 build = isl_ast_build_restrict_generated(build, guard);
937 build = isl_ast_build_cow(build);
938 if (!build)
939 return NULL;
941 isl_set_free(build->domain);
942 build->domain = isl_set_copy(build->generated);
943 isl_set_free(build->pending);
944 build->pending = isl_set_universe(isl_set_get_space(build->domain));
946 if (!build->pending)
947 return isl_ast_build_free(build);
949 return build;
952 /* Intersect build->pending and build->domain with "set",
953 * where "set" is specified in terms of the internal schedule domain.
955 __isl_give isl_ast_build *isl_ast_build_restrict_pending(
956 __isl_take isl_ast_build *build, __isl_take isl_set *set)
958 set = isl_set_compute_divs(set);
959 build = isl_ast_build_restrict_internal(build, isl_set_copy(set));
960 build = isl_ast_build_cow(build);
961 if (!build)
962 goto error;
964 build->pending = isl_set_intersect(build->pending, set);
965 build->pending = isl_set_coalesce(build->pending);
967 if (!build->pending)
968 return isl_ast_build_free(build);
970 return build;
971 error:
972 isl_ast_build_free(build);
973 isl_set_free(set);
974 return NULL;
977 /* Intersect build->domain with "set", where "set" is specified
978 * in terms of the external schedule domain.
980 __isl_give isl_ast_build *isl_ast_build_restrict(
981 __isl_take isl_ast_build *build, __isl_take isl_set *set)
983 if (isl_set_is_params(set))
984 return isl_ast_build_restrict_generated(build, set);
986 if (isl_ast_build_need_schedule_map(build)) {
987 isl_multi_aff *ma;
988 ma = isl_ast_build_get_schedule_map_multi_aff(build);
989 set = isl_set_preimage_multi_aff(set, ma);
991 return isl_ast_build_restrict_generated(build, set);
994 /* Replace build->executed by "executed".
996 __isl_give isl_ast_build *isl_ast_build_set_executed(
997 __isl_take isl_ast_build *build, __isl_take isl_union_map *executed)
999 build = isl_ast_build_cow(build);
1000 if (!build)
1001 goto error;
1003 isl_union_map_free(build->executed);
1004 build->executed = executed;
1006 return build;
1007 error:
1008 isl_ast_build_free(build);
1009 isl_union_map_free(executed);
1010 return NULL;
1013 /* Does "build" point to a band node?
1014 * That is, are we currently handling a band node inside a schedule tree?
1016 int isl_ast_build_has_schedule_node(__isl_keep isl_ast_build *build)
1018 if (!build)
1019 return -1;
1020 return build->node != NULL;
1023 /* Return a copy of the band node that "build" refers to.
1025 __isl_give isl_schedule_node *isl_ast_build_get_schedule_node(
1026 __isl_keep isl_ast_build *build)
1028 if (!build)
1029 return NULL;
1030 return isl_schedule_node_copy(build->node);
1033 /* Extract the loop AST generation types for the members of build->node
1034 * and store them in build->loop_type.
1036 static __isl_give isl_ast_build *extract_loop_types(
1037 __isl_take isl_ast_build *build)
1039 int i;
1040 isl_ctx *ctx;
1041 isl_schedule_node *node;
1043 if (!build)
1044 return NULL;
1045 ctx = isl_ast_build_get_ctx(build);
1046 if (!build->node)
1047 isl_die(ctx, isl_error_internal, "missing AST node",
1048 return isl_ast_build_free(build));
1050 free(build->loop_type);
1051 build->n = isl_schedule_node_band_n_member(build->node);
1052 build->loop_type = isl_alloc_array(ctx,
1053 enum isl_ast_loop_type, build->n);
1054 if (build->n && !build->loop_type)
1055 return isl_ast_build_free(build);
1056 node = build->node;
1057 for (i = 0; i < build->n; ++i)
1058 build->loop_type[i] =
1059 isl_schedule_node_band_member_get_ast_loop_type(node, i);
1061 return build;
1064 /* Replace the band node that "build" refers to by "node" and
1065 * extract the corresponding loop AST generation types.
1067 __isl_give isl_ast_build *isl_ast_build_set_schedule_node(
1068 __isl_take isl_ast_build *build,
1069 __isl_take isl_schedule_node *node)
1071 build = isl_ast_build_cow(build);
1072 if (!build || !node)
1073 goto error;
1075 isl_schedule_node_free(build->node);
1076 build->node = node;
1078 build = extract_loop_types(build);
1080 return build;
1081 error:
1082 isl_ast_build_free(build);
1083 isl_schedule_node_free(node);
1084 return NULL;
1087 /* Remove any reference to a band node from "build".
1089 __isl_give isl_ast_build *isl_ast_build_reset_schedule_node(
1090 __isl_take isl_ast_build *build)
1092 build = isl_ast_build_cow(build);
1093 if (!build)
1094 return NULL;
1096 isl_schedule_node_free(build->node);
1097 build->node = NULL;
1099 return build;
1102 /* Return a copy of the current schedule domain.
1104 __isl_give isl_set *isl_ast_build_get_domain(__isl_keep isl_ast_build *build)
1106 return build ? isl_set_copy(build->domain) : NULL;
1109 /* Return a copy of the set of pending constraints.
1111 __isl_give isl_set *isl_ast_build_get_pending(
1112 __isl_keep isl_ast_build *build)
1114 return build ? isl_set_copy(build->pending) : NULL;
1117 /* Return a copy of the set of generated constraints.
1119 __isl_give isl_set *isl_ast_build_get_generated(
1120 __isl_keep isl_ast_build *build)
1122 return build ? isl_set_copy(build->generated) : NULL;
1125 /* Return a copy of the map from the internal schedule domain
1126 * to the original input schedule domain.
1128 __isl_give isl_multi_aff *isl_ast_build_get_internal2input(
1129 __isl_keep isl_ast_build *build)
1131 return build ? isl_multi_aff_copy(build->internal2input) : NULL;
1134 /* Return the number of variables of the given type
1135 * in the (internal) schedule space.
1137 unsigned isl_ast_build_dim(__isl_keep isl_ast_build *build,
1138 enum isl_dim_type type)
1140 if (!build)
1141 return 0;
1142 return isl_set_dim(build->domain, type);
1145 /* Return the (schedule) space of "build".
1147 * If "internal" is set, then this space is the space of the internal
1148 * representation of the entire schedule, including those parts for
1149 * which no code has been generated yet.
1151 * If "internal" is not set, then this space is the external representation
1152 * of the loops generated so far.
1154 __isl_give isl_space *isl_ast_build_get_space(__isl_keep isl_ast_build *build,
1155 int internal)
1157 int i;
1158 int dim;
1159 isl_space *space;
1161 if (!build)
1162 return NULL;
1164 space = isl_set_get_space(build->domain);
1165 if (internal)
1166 return space;
1168 if (!isl_ast_build_need_schedule_map(build))
1169 return space;
1171 dim = isl_set_dim(build->domain, isl_dim_set);
1172 space = isl_space_drop_dims(space, isl_dim_set,
1173 build->depth, dim - build->depth);
1174 for (i = build->depth - 1; i >= 0; --i)
1175 if (isl_ast_build_has_affine_value(build, i))
1176 space = isl_space_drop_dims(space, isl_dim_set, i, 1);
1178 return space;
1181 /* Return the external representation of the schedule space of "build",
1182 * i.e., a space with a dimension for each loop generated so far,
1183 * with the names of the dimensions set to the loop iterators.
1185 __isl_give isl_space *isl_ast_build_get_schedule_space(
1186 __isl_keep isl_ast_build *build)
1188 isl_space *space;
1189 int i, skip;
1191 if (!build)
1192 return NULL;
1194 space = isl_ast_build_get_space(build, 0);
1196 skip = 0;
1197 for (i = 0; i < build->depth; ++i) {
1198 isl_id *id;
1200 if (isl_ast_build_has_affine_value(build, i)) {
1201 skip++;
1202 continue;
1205 id = isl_ast_build_get_iterator_id(build, i);
1206 space = isl_space_set_dim_id(space, isl_dim_set, i - skip, id);
1209 return space;
1212 /* Return the current schedule, as stored in build->executed, in terms
1213 * of the external schedule domain.
1215 __isl_give isl_union_map *isl_ast_build_get_schedule(
1216 __isl_keep isl_ast_build *build)
1218 isl_union_map *executed;
1219 isl_union_map *schedule;
1221 if (!build)
1222 return NULL;
1224 executed = isl_union_map_copy(build->executed);
1225 if (isl_ast_build_need_schedule_map(build)) {
1226 isl_map *proj = isl_ast_build_get_schedule_map(build);
1227 executed = isl_union_map_apply_domain(executed,
1228 isl_union_map_from_map(proj));
1230 schedule = isl_union_map_reverse(executed);
1232 return schedule;
1235 /* Return the iterator attached to the internal schedule dimension "pos".
1237 __isl_give isl_id *isl_ast_build_get_iterator_id(
1238 __isl_keep isl_ast_build *build, int pos)
1240 if (!build)
1241 return NULL;
1243 return isl_id_list_get_id(build->iterators, pos);
1246 /* Set the stride and offset of the current dimension to the given
1247 * value and expression.
1249 * If we had already found a stride before, then the two strides
1250 * are combined into a single stride.
1252 * In particular, if the new stride information is of the form
1254 * i = f + s (...)
1256 * and the old stride information is of the form
1258 * i = f2 + s2 (...)
1260 * then we compute the extended gcd of s and s2
1262 * a s + b s2 = g,
1264 * with g = gcd(s,s2), multiply the first equation with t1 = b s2/g
1265 * and the second with t2 = a s1/g.
1266 * This results in
1268 * i = (b s2 + a s1)/g i = t1 f + t2 f2 + (s s2)/g (...)
1270 * so that t1 f + t2 f2 is the combined offset and (s s2)/g = lcm(s,s2)
1271 * is the combined stride.
1273 static __isl_give isl_ast_build *set_stride(__isl_take isl_ast_build *build,
1274 __isl_take isl_val *stride, __isl_take isl_aff *offset)
1276 int pos;
1278 build = isl_ast_build_cow(build);
1279 if (!build || !stride || !offset)
1280 goto error;
1282 pos = build->depth;
1284 if (isl_ast_build_has_stride(build, pos)) {
1285 isl_val *stride2, *a, *b, *g;
1286 isl_aff *offset2;
1288 stride2 = isl_vec_get_element_val(build->strides, pos);
1289 g = isl_val_gcdext(isl_val_copy(stride), isl_val_copy(stride2),
1290 &a, &b);
1291 a = isl_val_mul(a, isl_val_copy(stride));
1292 a = isl_val_div(a, isl_val_copy(g));
1293 stride2 = isl_val_div(stride2, g);
1294 b = isl_val_mul(b, isl_val_copy(stride2));
1295 stride = isl_val_mul(stride, stride2);
1297 offset2 = isl_multi_aff_get_aff(build->offsets, pos);
1298 offset2 = isl_aff_scale_val(offset2, a);
1299 offset = isl_aff_scale_val(offset, b);
1300 offset = isl_aff_add(offset, offset2);
1303 build->strides = isl_vec_set_element_val(build->strides, pos, stride);
1304 build->offsets = isl_multi_aff_set_aff(build->offsets, pos, offset);
1305 if (!build->strides || !build->offsets)
1306 return isl_ast_build_free(build);
1308 return build;
1309 error:
1310 isl_val_free(stride);
1311 isl_aff_free(offset);
1312 return isl_ast_build_free(build);
1315 /* Return a set expressing the stride constraint at the current depth.
1317 * In particular, if the current iterator (i) is known to attain values
1319 * f + s a
1321 * where f is the offset and s is the stride, then the returned set
1322 * expresses the constraint
1324 * (f - i) mod s = 0
1326 __isl_give isl_set *isl_ast_build_get_stride_constraint(
1327 __isl_keep isl_ast_build *build)
1329 isl_aff *aff;
1330 isl_set *set;
1331 isl_val *stride;
1332 int pos;
1334 if (!build)
1335 return NULL;
1337 pos = build->depth;
1339 if (!isl_ast_build_has_stride(build, pos))
1340 return isl_set_universe(isl_ast_build_get_space(build, 1));
1342 stride = isl_ast_build_get_stride(build, pos);
1343 aff = isl_ast_build_get_offset(build, pos);
1344 aff = isl_aff_add_coefficient_si(aff, isl_dim_in, pos, -1);
1345 aff = isl_aff_mod_val(aff, stride);
1346 set = isl_set_from_basic_set(isl_aff_zero_basic_set(aff));
1348 return set;
1351 /* Return the expansion implied by the stride and offset at the current
1352 * depth.
1354 * That is, return the mapping
1356 * [i_0, ..., i_{d-1}, i_d, i_{d+1}, ...]
1357 * -> [i_0, ..., i_{d-1}, s * i_d + offset(i), i_{d+1}, ...]
1359 * where s is the stride at the current depth d and offset(i) is
1360 * the corresponding offset.
1362 __isl_give isl_multi_aff *isl_ast_build_get_stride_expansion(
1363 __isl_keep isl_ast_build *build)
1365 isl_space *space;
1366 isl_multi_aff *ma;
1367 int pos;
1368 isl_aff *aff, *offset;
1369 isl_val *stride;
1371 if (!build)
1372 return NULL;
1374 pos = isl_ast_build_get_depth(build);
1375 space = isl_ast_build_get_space(build, 1);
1376 space = isl_space_map_from_set(space);
1377 ma = isl_multi_aff_identity(space);
1379 if (!isl_ast_build_has_stride(build, pos))
1380 return ma;
1382 offset = isl_ast_build_get_offset(build, pos);
1383 stride = isl_ast_build_get_stride(build, pos);
1384 aff = isl_multi_aff_get_aff(ma, pos);
1385 aff = isl_aff_scale_val(aff, stride);
1386 aff = isl_aff_add(aff, offset);
1387 ma = isl_multi_aff_set_aff(ma, pos, aff);
1389 return ma;
1392 /* Add constraints corresponding to any previously detected
1393 * stride on the current dimension to build->domain.
1395 __isl_give isl_ast_build *isl_ast_build_include_stride(
1396 __isl_take isl_ast_build *build)
1398 isl_set *set;
1400 if (!build)
1401 return NULL;
1402 if (!isl_ast_build_has_stride(build, build->depth))
1403 return build;
1404 build = isl_ast_build_cow(build);
1405 if (!build)
1406 return NULL;
1408 set = isl_ast_build_get_stride_constraint(build);
1410 build->domain = isl_set_intersect(build->domain, isl_set_copy(set));
1411 build->generated = isl_set_intersect(build->generated, set);
1412 if (!build->domain || !build->generated)
1413 return isl_ast_build_free(build);
1415 return build;
1418 /* Information used inside detect_stride.
1420 * "build" may be updated by detect_stride to include stride information.
1421 * "pos" is equal to build->depth.
1423 struct isl_detect_stride_data {
1424 isl_ast_build *build;
1425 int pos;
1428 /* Check if constraint "c" imposes any stride on dimension data->pos
1429 * and, if so, update the stride information in data->build.
1431 * In order to impose a stride on the dimension, "c" needs to be an equality
1432 * and it needs to involve the dimension. Note that "c" may also be
1433 * a div constraint and thus an inequality that we cannot use.
1435 * Let c be of the form
1437 * h(p) + g * v * i + g * stride * f(alpha) = 0
1439 * with h(p) an expression in terms of the parameters and outer dimensions
1440 * and f(alpha) an expression in terms of the existentially quantified
1441 * variables. Note that the inner dimensions have been eliminated so
1442 * they do not appear in "c".
1444 * If "stride" is not zero and not one, then it represents a non-trivial stride
1445 * on "i". We compute a and b such that
1447 * a v + b stride = 1
1449 * We have
1451 * g v i = -h(p) + g stride f(alpha)
1453 * a g v i = -a h(p) + g stride f(alpha)
1455 * a g v i + b g stride i = -a h(p) + g stride * (...)
1457 * g i = -a h(p) + g stride * (...)
1459 * i = -a h(p)/g + stride * (...)
1461 * The expression "-a h(p)/g" can therefore be used as offset.
1463 static int detect_stride(__isl_take isl_constraint *c, void *user)
1465 struct isl_detect_stride_data *data = user;
1466 int i, n_div;
1467 isl_ctx *ctx;
1468 isl_val *v, *stride, *m;
1470 if (!isl_constraint_is_equality(c) ||
1471 !isl_constraint_involves_dims(c, isl_dim_set, data->pos, 1)) {
1472 isl_constraint_free(c);
1473 return 0;
1476 ctx = isl_constraint_get_ctx(c);
1477 stride = isl_val_zero(ctx);
1478 n_div = isl_constraint_dim(c, isl_dim_div);
1479 for (i = 0; i < n_div; ++i) {
1480 v = isl_constraint_get_coefficient_val(c, isl_dim_div, i);
1481 stride = isl_val_gcd(stride, v);
1484 v = isl_constraint_get_coefficient_val(c, isl_dim_set, data->pos);
1485 m = isl_val_gcd(isl_val_copy(stride), isl_val_copy(v));
1486 stride = isl_val_div(stride, isl_val_copy(m));
1487 v = isl_val_div(v, isl_val_copy(m));
1489 if (!isl_val_is_zero(stride) && !isl_val_is_one(stride)) {
1490 isl_aff *aff;
1491 isl_val *gcd, *a, *b;
1493 gcd = isl_val_gcdext(v, isl_val_copy(stride), &a, &b);
1494 isl_val_free(gcd);
1495 isl_val_free(b);
1497 aff = isl_constraint_get_aff(c);
1498 for (i = 0; i < n_div; ++i)
1499 aff = isl_aff_set_coefficient_si(aff,
1500 isl_dim_div, i, 0);
1501 aff = isl_aff_set_coefficient_si(aff, isl_dim_in, data->pos, 0);
1502 a = isl_val_neg(a);
1503 aff = isl_aff_scale_val(aff, a);
1504 aff = isl_aff_scale_down_val(aff, m);
1505 data->build = set_stride(data->build, stride, aff);
1506 } else {
1507 isl_val_free(stride);
1508 isl_val_free(m);
1509 isl_val_free(v);
1512 isl_constraint_free(c);
1513 return 0;
1516 /* Check if the constraints in "set" imply any stride on the current
1517 * dimension and, if so, record the stride information in "build"
1518 * and return the updated "build".
1520 * We compute the affine hull and then check if any of the constraints
1521 * in the hull imposes any stride on the current dimension.
1523 * We assume that inner dimensions have been eliminated from "set"
1524 * by the caller. This is needed because the common stride
1525 * may be imposed by different inner dimensions on different parts of
1526 * the domain.
1528 __isl_give isl_ast_build *isl_ast_build_detect_strides(
1529 __isl_take isl_ast_build *build, __isl_take isl_set *set)
1531 isl_basic_set *hull;
1532 struct isl_detect_stride_data data;
1534 if (!build)
1535 goto error;
1537 data.build = build;
1538 data.pos = isl_ast_build_get_depth(build);
1539 hull = isl_set_affine_hull(set);
1541 if (isl_basic_set_foreach_constraint(hull, &detect_stride, &data) < 0)
1542 data.build = isl_ast_build_free(data.build);
1544 isl_basic_set_free(hull);
1545 return data.build;
1546 error:
1547 isl_set_free(set);
1548 return NULL;
1551 struct isl_ast_build_involves_data {
1552 int depth;
1553 int involves;
1556 /* Check if "map" involves the input dimension data->depth.
1558 static int involves_depth(__isl_take isl_map *map, void *user)
1560 struct isl_ast_build_involves_data *data = user;
1562 data->involves = isl_map_involves_dims(map, isl_dim_in, data->depth, 1);
1563 isl_map_free(map);
1565 if (data->involves < 0 || data->involves)
1566 return -1;
1567 return 0;
1570 /* Do any options depend on the value of the dimension at the current depth?
1572 int isl_ast_build_options_involve_depth(__isl_keep isl_ast_build *build)
1574 struct isl_ast_build_involves_data data;
1576 if (!build)
1577 return -1;
1579 data.depth = build->depth;
1580 data.involves = 0;
1582 if (isl_union_map_foreach_map(build->options,
1583 &involves_depth, &data) < 0) {
1584 if (data.involves < 0 || !data.involves)
1585 return -1;
1588 return data.involves;
1591 /* Construct the map
1593 * { [i] -> [i] : i < pos; [i] -> [i + 1] : i >= pos }
1595 * with "space" the parameter space of the constructed map.
1597 static __isl_give isl_map *construct_insertion_map(__isl_take isl_space *space,
1598 int pos)
1600 isl_constraint *c;
1601 isl_basic_map *bmap1, *bmap2;
1603 space = isl_space_set_from_params(space);
1604 space = isl_space_add_dims(space, isl_dim_set, 1);
1605 space = isl_space_map_from_set(space);
1606 c = isl_equality_alloc(isl_local_space_from_space(space));
1607 c = isl_constraint_set_coefficient_si(c, isl_dim_in, 0, 1);
1608 c = isl_constraint_set_coefficient_si(c, isl_dim_out, 0, -1);
1609 bmap1 = isl_basic_map_from_constraint(isl_constraint_copy(c));
1610 c = isl_constraint_set_constant_si(c, 1);
1611 bmap2 = isl_basic_map_from_constraint(c);
1613 bmap1 = isl_basic_map_upper_bound_si(bmap1, isl_dim_in, 0, pos - 1);
1614 bmap2 = isl_basic_map_lower_bound_si(bmap2, isl_dim_in, 0, pos);
1616 return isl_basic_map_union(bmap1, bmap2);
1619 static const char *option_str[] = {
1620 [isl_ast_loop_atomic] = "atomic",
1621 [isl_ast_loop_unroll] = "unroll",
1622 [isl_ast_loop_separate] = "separate"
1625 /* Update the "options" to reflect the insertion of a dimension
1626 * at position "pos" in the schedule domain space.
1627 * "space" is the original domain space before the insertion and
1628 * may be named and/or structured.
1630 * The (relevant) input options all have "space" as domain, which
1631 * has to be mapped to the extended space.
1632 * The values of the ranges also refer to the schedule domain positions
1633 * and they therefore also need to be adjusted. In particular, values
1634 * smaller than pos do not need to change, while values greater than or
1635 * equal to pos need to be incremented.
1636 * That is, we need to apply the following map.
1638 * { atomic[i] -> atomic[i] : i < pos; [i] -> [i + 1] : i >= pos;
1639 * unroll[i] -> unroll[i] : i < pos; [i] -> [i + 1] : i >= pos;
1640 * separate[i] -> separate[i] : i < pos; [i] -> [i + 1] : i >= pos;
1641 * separation_class[[i] -> [c]]
1642 * -> separation_class[[i] -> [c]] : i < pos;
1643 * separation_class[[i] -> [c]]
1644 * -> separation_class[[i + 1] -> [c]] : i >= pos }
1646 static __isl_give isl_union_map *options_insert_dim(
1647 __isl_take isl_union_map *options, __isl_take isl_space *space, int pos)
1649 isl_map *map;
1650 isl_union_map *insertion;
1651 enum isl_ast_loop_type type;
1652 const char *name = "separation_class";
1654 space = isl_space_map_from_set(space);
1655 map = isl_map_identity(space);
1656 map = isl_map_insert_dims(map, isl_dim_out, pos, 1);
1657 options = isl_union_map_apply_domain(options,
1658 isl_union_map_from_map(map));
1660 if (!options)
1661 return NULL;
1663 map = construct_insertion_map(isl_union_map_get_space(options), pos);
1665 insertion = isl_union_map_empty(isl_union_map_get_space(options));
1667 for (type = isl_ast_loop_atomic;
1668 type <= isl_ast_loop_separate; ++type) {
1669 isl_map *map_type = isl_map_copy(map);
1670 const char *name = option_str[type];
1671 map_type = isl_map_set_tuple_name(map_type, isl_dim_in, name);
1672 map_type = isl_map_set_tuple_name(map_type, isl_dim_out, name);
1673 insertion = isl_union_map_add_map(insertion, map_type);
1676 map = isl_map_product(map, isl_map_identity(isl_map_get_space(map)));
1677 map = isl_map_set_tuple_name(map, isl_dim_in, name);
1678 map = isl_map_set_tuple_name(map, isl_dim_out, name);
1679 insertion = isl_union_map_add_map(insertion, map);
1681 options = isl_union_map_apply_range(options, insertion);
1683 return options;
1686 /* If we are generating an AST from a schedule tree (build->node is set),
1687 * then update the loop AST generation types
1688 * to reflect the insertion of a dimension at (global) position "pos"
1689 * in the schedule domain space.
1690 * We do not need to adjust any isolate option since we would not be inserting
1691 * any dimensions if there were any isolate option.
1693 static __isl_give isl_ast_build *node_insert_dim(
1694 __isl_take isl_ast_build *build, int pos)
1696 int i;
1697 int local_pos;
1698 enum isl_ast_loop_type *loop_type;
1699 isl_ctx *ctx;
1701 build = isl_ast_build_cow(build);
1702 if (!build)
1703 return NULL;
1704 if (!build->node)
1705 return build;
1707 ctx = isl_ast_build_get_ctx(build);
1708 local_pos = pos - build->outer_pos;
1709 loop_type = isl_realloc_array(ctx, build->loop_type,
1710 enum isl_ast_loop_type, build->n + 1);
1711 if (!loop_type)
1712 return isl_ast_build_free(build);
1713 build->loop_type = loop_type;
1714 for (i = build->n - 1; i >= local_pos; --i)
1715 loop_type[i + 1] = loop_type[i];
1716 loop_type[local_pos] = isl_ast_loop_default;
1717 build->n++;
1719 return build;
1722 /* Insert a single dimension in the schedule domain at position "pos".
1723 * The new dimension is given an isl_id with the empty string as name.
1725 * The main difficulty is updating build->options to reflect the
1726 * extra dimension. This is handled in options_insert_dim.
1728 * Note that because of the dimension manipulations, the resulting
1729 * schedule domain space will always be unnamed and unstructured.
1730 * However, the original schedule domain space may be named and/or
1731 * structured, so we have to take this possibility into account
1732 * while performing the transformations.
1734 * Since the inserted schedule dimension is used by the caller
1735 * to differentiate between different domain spaces, there is
1736 * no longer a uniform mapping from the internal schedule space
1737 * to the input schedule space. The internal2input mapping is
1738 * therefore removed.
1740 __isl_give isl_ast_build *isl_ast_build_insert_dim(
1741 __isl_take isl_ast_build *build, int pos)
1743 isl_ctx *ctx;
1744 isl_space *space, *ma_space;
1745 isl_id *id;
1746 isl_multi_aff *ma;
1748 build = isl_ast_build_cow(build);
1749 if (!build)
1750 return NULL;
1752 ctx = isl_ast_build_get_ctx(build);
1753 id = isl_id_alloc(ctx, "", NULL);
1754 if (!build->node)
1755 space = isl_ast_build_get_space(build, 1);
1756 build->iterators = isl_id_list_insert(build->iterators, pos, id);
1757 build->domain = isl_set_insert_dims(build->domain,
1758 isl_dim_set, pos, 1);
1759 build->generated = isl_set_insert_dims(build->generated,
1760 isl_dim_set, pos, 1);
1761 build->pending = isl_set_insert_dims(build->pending,
1762 isl_dim_set, pos, 1);
1763 build->strides = isl_vec_insert_els(build->strides, pos, 1);
1764 build->strides = isl_vec_set_element_si(build->strides, pos, 1);
1765 ma_space = isl_space_params(isl_multi_aff_get_space(build->offsets));
1766 ma_space = isl_space_set_from_params(ma_space);
1767 ma_space = isl_space_add_dims(ma_space, isl_dim_set, 1);
1768 ma_space = isl_space_map_from_set(ma_space);
1769 ma = isl_multi_aff_zero(isl_space_copy(ma_space));
1770 build->offsets = isl_multi_aff_splice(build->offsets, pos, pos, ma);
1771 ma = isl_multi_aff_identity(ma_space);
1772 build->values = isl_multi_aff_splice(build->values, pos, pos, ma);
1773 if (!build->node)
1774 build->options = options_insert_dim(build->options, space, pos);
1775 build->internal2input = isl_multi_aff_free(build->internal2input);
1777 if (!build->iterators || !build->domain || !build->generated ||
1778 !build->pending || !build->values ||
1779 !build->strides || !build->offsets || !build->options)
1780 return isl_ast_build_free(build);
1782 build = node_insert_dim(build, pos);
1784 return build;
1787 /* Scale down the current dimension by a factor of "m".
1788 * "umap" is an isl_union_map that implements the scaling down.
1789 * That is, it is of the form
1791 * { [.... i ....] -> [.... i' ....] : i = m i' }
1793 * This function is called right after the strides have been
1794 * detected, but before any constraints on the current dimension
1795 * have been included in build->domain.
1796 * We therefore only need to update stride, offset, the options and
1797 * the mapping from internal schedule space to the original schedule
1798 * space, if we are still keeping track of such a mapping.
1799 * The latter mapping is updated by plugging in
1800 * { [... i ...] -> [... m i ... ] }.
1802 __isl_give isl_ast_build *isl_ast_build_scale_down(
1803 __isl_take isl_ast_build *build, __isl_take isl_val *m,
1804 __isl_take isl_union_map *umap)
1806 isl_aff *aff;
1807 isl_val *v;
1808 int depth;
1810 build = isl_ast_build_cow(build);
1811 if (!build || !umap || !m)
1812 goto error;
1814 depth = build->depth;
1816 if (build->internal2input) {
1817 isl_space *space;
1818 isl_multi_aff *ma;
1819 isl_aff *aff;
1821 space = isl_multi_aff_get_space(build->internal2input);
1822 space = isl_space_map_from_set(isl_space_domain(space));
1823 ma = isl_multi_aff_identity(space);
1824 aff = isl_multi_aff_get_aff(ma, depth);
1825 aff = isl_aff_scale_val(aff, isl_val_copy(m));
1826 ma = isl_multi_aff_set_aff(ma, depth, aff);
1827 build->internal2input =
1828 isl_multi_aff_pullback_multi_aff(build->internal2input, ma);
1829 if (!build->internal2input)
1830 goto error;
1833 v = isl_vec_get_element_val(build->strides, depth);
1834 v = isl_val_div(v, isl_val_copy(m));
1835 build->strides = isl_vec_set_element_val(build->strides, depth, v);
1837 aff = isl_multi_aff_get_aff(build->offsets, depth);
1838 aff = isl_aff_scale_down_val(aff, m);
1839 build->offsets = isl_multi_aff_set_aff(build->offsets, depth, aff);
1840 build->options = isl_union_map_apply_domain(build->options, umap);
1841 if (!build->strides || !build->offsets || !build->options)
1842 return isl_ast_build_free(build);
1844 return build;
1845 error:
1846 isl_val_free(m);
1847 isl_union_map_free(umap);
1848 return isl_ast_build_free(build);
1851 /* Return a list of "n" isl_ids called "c%d", with "%d" starting at "first".
1852 * If an isl_id with such a name already appears among the parameters
1853 * in build->domain, then adjust the name to "c%d_%d".
1855 static __isl_give isl_id_list *generate_names(isl_ctx *ctx, int n, int first,
1856 __isl_keep isl_ast_build *build)
1858 int i;
1859 isl_id_list *names;
1861 names = isl_id_list_alloc(ctx, n);
1862 for (i = 0; i < n; ++i) {
1863 isl_id *id;
1865 id = generate_name(ctx, first + i, build);
1866 names = isl_id_list_add(names, id);
1869 return names;
1872 /* Embed "options" into the given isl_ast_build space.
1874 * This function is called from within a nested call to
1875 * isl_ast_build_node_from_schedule_map.
1876 * "options" refers to the additional schedule,
1877 * while space refers to both the space of the outer isl_ast_build and
1878 * that of the additional schedule.
1879 * Specifically, space is of the form
1881 * [I -> S]
1883 * while options lives in the space(s)
1885 * S -> *
1887 * We compute
1889 * [I -> S] -> S
1891 * and compose this with options, to obtain the new options
1892 * living in the space(s)
1894 * [I -> S] -> *
1896 static __isl_give isl_union_map *embed_options(
1897 __isl_take isl_union_map *options, __isl_take isl_space *space)
1899 isl_map *map;
1901 map = isl_map_universe(isl_space_unwrap(space));
1902 map = isl_map_range_map(map);
1904 options = isl_union_map_apply_range(
1905 isl_union_map_from_map(map), options);
1907 return options;
1910 /* Update "build" for use in a (possibly nested) code generation. That is,
1911 * extend "build" from an AST build on some domain O to an AST build
1912 * on domain [O -> S], with S corresponding to "space".
1913 * If the original domain is a parameter domain, then the new domain is
1914 * simply S.
1915 * "iterators" is a list of iterators for S, but the number of elements
1916 * may be smaller or greater than the number of set dimensions of S.
1917 * If "keep_iterators" is set, then any extra ids in build->iterators
1918 * are reused for S. Otherwise, these extra ids are dropped.
1920 * We first update build->outer_pos to the current depth.
1921 * This depth is zero in case this is the outermost code generation.
1923 * We then add additional ids such that the number of iterators is at least
1924 * equal to the dimension of the new build domain.
1926 * If the original domain is parametric, then we are constructing
1927 * an isl_ast_build for the outer code generation and we pass control
1928 * to isl_ast_build_init.
1930 * Otherwise, we adjust the fields of "build" to include "space".
1932 __isl_give isl_ast_build *isl_ast_build_product(
1933 __isl_take isl_ast_build *build, __isl_take isl_space *space)
1935 isl_ctx *ctx;
1936 isl_vec *strides;
1937 isl_set *set;
1938 isl_multi_aff *embedding;
1939 int dim, n_it;
1941 build = isl_ast_build_cow(build);
1942 if (!build)
1943 goto error;
1945 build->outer_pos = build->depth;
1947 ctx = isl_ast_build_get_ctx(build);
1948 dim = isl_set_dim(build->domain, isl_dim_set);
1949 dim += isl_space_dim(space, isl_dim_set);
1950 n_it = isl_id_list_n_id(build->iterators);
1951 if (n_it < dim) {
1952 isl_id_list *l;
1953 l = generate_names(ctx, dim - n_it, n_it, build);
1954 build->iterators = isl_id_list_concat(build->iterators, l);
1957 if (isl_set_is_params(build->domain))
1958 return isl_ast_build_init(build, space);
1960 set = isl_set_universe(isl_space_copy(space));
1961 build->domain = isl_set_product(build->domain, isl_set_copy(set));
1962 build->pending = isl_set_product(build->pending, isl_set_copy(set));
1963 build->generated = isl_set_product(build->generated, set);
1965 strides = isl_vec_alloc(ctx, isl_space_dim(space, isl_dim_set));
1966 strides = isl_vec_set_si(strides, 1);
1967 build->strides = isl_vec_concat(build->strides, strides);
1969 space = isl_space_map_from_set(space);
1970 build->offsets = isl_multi_aff_align_params(build->offsets,
1971 isl_space_copy(space));
1972 build->offsets = isl_multi_aff_product(build->offsets,
1973 isl_multi_aff_zero(isl_space_copy(space)));
1974 build->values = isl_multi_aff_align_params(build->values,
1975 isl_space_copy(space));
1976 embedding = isl_multi_aff_identity(space);
1977 build->values = isl_multi_aff_product(build->values,
1978 isl_multi_aff_copy(embedding));
1979 if (build->internal2input) {
1980 build->internal2input =
1981 isl_multi_aff_product(build->internal2input, embedding);
1982 build->internal2input =
1983 isl_multi_aff_flatten_range(build->internal2input);
1984 if (!build->internal2input)
1985 return isl_ast_build_free(build);
1986 } else {
1987 isl_multi_aff_free(embedding);
1990 space = isl_ast_build_get_space(build, 1);
1991 build->options = embed_options(build->options, space);
1993 if (!build->iterators || !build->domain || !build->generated ||
1994 !build->pending || !build->values ||
1995 !build->strides || !build->offsets || !build->options)
1996 return isl_ast_build_free(build);
1998 return build;
1999 error:
2000 isl_ast_build_free(build);
2001 isl_space_free(space);
2002 return NULL;
2005 /* Does "aff" only attain non-negative values over build->domain?
2006 * That is, does it not attain any negative values?
2008 int isl_ast_build_aff_is_nonneg(__isl_keep isl_ast_build *build,
2009 __isl_keep isl_aff *aff)
2011 isl_set *test;
2012 int empty;
2014 if (!build)
2015 return -1;
2017 aff = isl_aff_copy(aff);
2018 test = isl_set_from_basic_set(isl_aff_neg_basic_set(aff));
2019 test = isl_set_intersect(test, isl_set_copy(build->domain));
2020 empty = isl_set_is_empty(test);
2021 isl_set_free(test);
2023 return empty;
2026 /* Does the dimension at (internal) position "pos" have a non-trivial stride?
2028 int isl_ast_build_has_stride(__isl_keep isl_ast_build *build, int pos)
2030 isl_val *v;
2031 int has_stride;
2033 if (!build)
2034 return -1;
2036 v = isl_vec_get_element_val(build->strides, pos);
2037 if (!v)
2038 return -1;
2039 has_stride = !isl_val_is_one(v);
2040 isl_val_free(v);
2042 return has_stride;
2045 /* Given that the dimension at position "pos" takes on values
2047 * f + s a
2049 * with a an integer, return s through *stride.
2051 __isl_give isl_val *isl_ast_build_get_stride(__isl_keep isl_ast_build *build,
2052 int pos)
2054 if (!build)
2055 return NULL;
2057 return isl_vec_get_element_val(build->strides, pos);
2060 /* Given that the dimension at position "pos" takes on values
2062 * f + s a
2064 * with a an integer, return f.
2066 __isl_give isl_aff *isl_ast_build_get_offset(
2067 __isl_keep isl_ast_build *build, int pos)
2069 if (!build)
2070 return NULL;
2072 return isl_multi_aff_get_aff(build->offsets, pos);
2075 /* Is the dimension at position "pos" known to attain only a single
2076 * value that, moreover, can be described by a single affine expression
2077 * in terms of the outer dimensions and parameters?
2079 * If not, then the corresponding affine expression in build->values
2080 * is set to be equal to the same input dimension.
2081 * Otherwise, it is set to the requested expression in terms of
2082 * outer dimensions and parameters.
2084 int isl_ast_build_has_affine_value(__isl_keep isl_ast_build *build,
2085 int pos)
2087 isl_aff *aff;
2088 int involves;
2090 if (!build)
2091 return -1;
2093 aff = isl_multi_aff_get_aff(build->values, pos);
2094 involves = isl_aff_involves_dims(aff, isl_dim_in, pos, 1);
2095 isl_aff_free(aff);
2097 if (involves < 0)
2098 return -1;
2100 return !involves;
2103 /* Plug in the known values (fixed affine expressions in terms of
2104 * parameters and outer loop iterators) of all loop iterators
2105 * in the domain of "umap".
2107 * We simply precompose "umap" with build->values.
2109 __isl_give isl_union_map *isl_ast_build_substitute_values_union_map_domain(
2110 __isl_keep isl_ast_build *build, __isl_take isl_union_map *umap)
2112 isl_multi_aff *values;
2114 if (!build)
2115 return isl_union_map_free(umap);
2117 values = isl_multi_aff_copy(build->values);
2118 umap = isl_union_map_preimage_domain_multi_aff(umap, values);
2120 return umap;
2123 /* Is the current dimension known to attain only a single value?
2125 int isl_ast_build_has_value(__isl_keep isl_ast_build *build)
2127 if (!build)
2128 return -1;
2130 return build->value != NULL;
2133 /* Simplify the basic set "bset" based on what we know about
2134 * the iterators of already generated loops.
2136 * "bset" is assumed to live in the (internal) schedule domain.
2138 __isl_give isl_basic_set *isl_ast_build_compute_gist_basic_set(
2139 __isl_keep isl_ast_build *build, __isl_take isl_basic_set *bset)
2141 if (!build)
2142 goto error;
2144 bset = isl_basic_set_preimage_multi_aff(bset,
2145 isl_multi_aff_copy(build->values));
2146 bset = isl_basic_set_gist(bset,
2147 isl_set_simple_hull(isl_set_copy(build->domain)));
2149 return bset;
2150 error:
2151 isl_basic_set_free(bset);
2152 return NULL;
2155 /* Simplify the set "set" based on what we know about
2156 * the iterators of already generated loops.
2158 * "set" is assumed to live in the (internal) schedule domain.
2160 __isl_give isl_set *isl_ast_build_compute_gist(
2161 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2163 if (!build)
2164 goto error;
2166 if (!isl_set_is_params(set))
2167 set = isl_set_preimage_multi_aff(set,
2168 isl_multi_aff_copy(build->values));
2169 set = isl_set_gist(set, isl_set_copy(build->domain));
2171 return set;
2172 error:
2173 isl_set_free(set);
2174 return NULL;
2177 /* Include information about what we know about the iterators of
2178 * already generated loops to "set".
2180 * We currently only plug in the known affine values of outer loop
2181 * iterators.
2182 * In principle we could also introduce equalities or even other
2183 * constraints implied by the intersection of "set" and build->domain.
2185 __isl_give isl_set *isl_ast_build_specialize(__isl_keep isl_ast_build *build,
2186 __isl_take isl_set *set)
2188 if (!build)
2189 return isl_set_free(set);
2191 return isl_set_preimage_multi_aff(set,
2192 isl_multi_aff_copy(build->values));
2195 /* Simplify the map "map" based on what we know about
2196 * the iterators of already generated loops.
2198 * The domain of "map" is assumed to live in the (internal) schedule domain.
2200 __isl_give isl_map *isl_ast_build_compute_gist_map_domain(
2201 __isl_keep isl_ast_build *build, __isl_take isl_map *map)
2203 if (!build)
2204 goto error;
2206 map = isl_map_gist_domain(map, isl_set_copy(build->domain));
2208 return map;
2209 error:
2210 isl_map_free(map);
2211 return NULL;
2214 /* Simplify the affine expression "aff" based on what we know about
2215 * the iterators of already generated loops.
2217 * The domain of "aff" is assumed to live in the (internal) schedule domain.
2219 __isl_give isl_aff *isl_ast_build_compute_gist_aff(
2220 __isl_keep isl_ast_build *build, __isl_take isl_aff *aff)
2222 if (!build)
2223 goto error;
2225 aff = isl_aff_gist(aff, isl_set_copy(build->domain));
2227 return aff;
2228 error:
2229 isl_aff_free(aff);
2230 return NULL;
2233 /* Simplify the piecewise affine expression "aff" based on what we know about
2234 * the iterators of already generated loops.
2236 * The domain of "pa" is assumed to live in the (internal) schedule domain.
2238 __isl_give isl_pw_aff *isl_ast_build_compute_gist_pw_aff(
2239 __isl_keep isl_ast_build *build, __isl_take isl_pw_aff *pa)
2241 if (!build)
2242 goto error;
2244 if (!isl_set_is_params(build->domain))
2245 pa = isl_pw_aff_pullback_multi_aff(pa,
2246 isl_multi_aff_copy(build->values));
2247 pa = isl_pw_aff_gist(pa, isl_set_copy(build->domain));
2249 return pa;
2250 error:
2251 isl_pw_aff_free(pa);
2252 return NULL;
2255 /* Simplify the piecewise multi-affine expression "aff" based on what
2256 * we know about the iterators of already generated loops.
2258 * The domain of "pma" is assumed to live in the (internal) schedule domain.
2260 __isl_give isl_pw_multi_aff *isl_ast_build_compute_gist_pw_multi_aff(
2261 __isl_keep isl_ast_build *build, __isl_take isl_pw_multi_aff *pma)
2263 if (!build)
2264 goto error;
2266 pma = isl_pw_multi_aff_pullback_multi_aff(pma,
2267 isl_multi_aff_copy(build->values));
2268 pma = isl_pw_multi_aff_gist(pma, isl_set_copy(build->domain));
2270 return pma;
2271 error:
2272 isl_pw_multi_aff_free(pma);
2273 return NULL;
2276 /* Extract the schedule domain of the given type from build->options
2277 * at the current depth.
2279 * In particular, find the subset of build->options that is of
2280 * the following form
2282 * schedule_domain -> type[depth]
2284 * and return the corresponding domain, after eliminating inner dimensions
2285 * and divs that depend on the current dimension.
2287 * Note that the domain of build->options has been reformulated
2288 * in terms of the internal build space in embed_options,
2289 * but the position is still that within the current code generation.
2291 __isl_give isl_set *isl_ast_build_get_option_domain(
2292 __isl_keep isl_ast_build *build, enum isl_ast_loop_type type)
2294 const char *name;
2295 isl_space *space;
2296 isl_map *option;
2297 isl_set *domain;
2298 int local_pos;
2300 if (!build)
2301 return NULL;
2303 name = option_str[type];
2304 local_pos = build->depth - build->outer_pos;
2306 space = isl_ast_build_get_space(build, 1);
2307 space = isl_space_from_domain(space);
2308 space = isl_space_add_dims(space, isl_dim_out, 1);
2309 space = isl_space_set_tuple_name(space, isl_dim_out, name);
2311 option = isl_union_map_extract_map(build->options, space);
2312 option = isl_map_fix_si(option, isl_dim_out, 0, local_pos);
2314 domain = isl_map_domain(option);
2315 domain = isl_ast_build_eliminate(build, domain);
2317 return domain;
2320 /* How does the user want the current schedule dimension to be generated?
2321 * These choices have been extracted from the schedule node
2322 * in extract_loop_types and stored in build->loop_type.
2323 * They have been updated to reflect any dimension insertion in
2324 * node_insert_dim.
2325 * Return isl_ast_domain_error on error.
2327 * If "isolated" is set, then we get the loop AST generation type
2328 * directly from the band node since node_insert_dim cannot have been
2329 * called on a band with the isolate option.
2331 enum isl_ast_loop_type isl_ast_build_get_loop_type(
2332 __isl_keep isl_ast_build *build, int isolated)
2334 int local_pos;
2335 isl_ctx *ctx;
2337 if (!build)
2338 return isl_ast_loop_error;
2339 ctx = isl_ast_build_get_ctx(build);
2340 if (!build->node)
2341 isl_die(ctx, isl_error_internal,
2342 "only works for schedule tree based AST generation",
2343 return isl_ast_loop_error);
2345 local_pos = build->depth - build->outer_pos;
2346 if (!isolated)
2347 return build->loop_type[local_pos];
2348 return isl_schedule_node_band_member_get_isolate_ast_loop_type(
2349 build->node, local_pos);
2352 /* Extract the isolated set from the isolate option, if any,
2353 * and store in the build.
2354 * If there is no isolate option, then the isolated set is
2355 * set to the empty set.
2357 * The isolate option is of the form
2359 * isolate[[outer bands] -> current_band]
2361 * We flatten this set and then map it back to the internal
2362 * schedule space.
2364 * If we have already extracted the isolated set
2365 * or if internal2input is no longer set, then we do not
2366 * need to do anything. In the latter case, we know
2367 * that the current band cannot have any isolate option.
2369 __isl_give isl_ast_build *isl_ast_build_extract_isolated(
2370 __isl_take isl_ast_build *build)
2372 isl_space *space, *space2;
2373 isl_union_set *options;
2374 int n, n2;
2375 isl_set *isolated;
2377 if (!build)
2378 return NULL;
2379 if (!build->internal2input)
2380 return build;
2381 if (build->isolated)
2382 return build;
2384 build = isl_ast_build_cow(build);
2385 if (!build)
2386 return NULL;
2388 options = isl_schedule_node_band_get_ast_build_options(build->node);
2390 space = isl_multi_aff_get_space(build->internal2input);
2391 space = isl_space_range(space);
2392 space2 = isl_set_get_space(build->domain);
2393 if (isl_space_is_wrapping(space2))
2394 space2 = isl_space_range(isl_space_unwrap(space2));
2395 n2 = isl_space_dim(space2, isl_dim_set);
2396 n = isl_space_dim(space, isl_dim_set);
2397 if (n < n2)
2398 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2399 "total input space dimension cannot be smaller "
2400 "than dimension of innermost band",
2401 space = isl_space_free(space));
2402 space = isl_space_drop_dims(space, isl_dim_set, n - n2, n2);
2403 space = isl_space_map_from_domain_and_range(space, space2);
2404 space = isl_space_wrap(space);
2405 space = isl_space_set_tuple_name(space, isl_dim_set, "isolate");
2406 isolated = isl_union_set_extract_set(options, space);
2407 isl_union_set_free(options);
2409 isolated = isl_set_flatten(isolated);
2410 isolated = isl_set_preimage_multi_aff(isolated,
2411 isl_multi_aff_copy(build->internal2input));
2413 build->isolated = isolated;
2414 if (!build->isolated)
2415 return isl_ast_build_free(build);
2417 return build;
2420 /* Does "build" have a non-empty isolated set?
2422 * The caller is assumed to have called isl_ast_build_extract_isolated first.
2424 int isl_ast_build_has_isolated(__isl_keep isl_ast_build *build)
2426 int empty;
2428 if (!build)
2429 return -1;
2430 if (!build->internal2input)
2431 return 0;
2432 if (!build->isolated)
2433 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2434 "isolated set not extracted yet", return -1);
2436 empty = isl_set_plain_is_empty(build->isolated);
2437 return empty < 0 ? -1 : !empty;
2440 /* Return a copy of the isolated set of "build".
2442 * The caller is assume to have called isl_ast_build_has_isolated first,
2443 * with this function returning true.
2444 * In particular, this function should not be called if we are no
2445 * longer keeping track of internal2input (and there therefore could
2446 * not possibly be any isolated set).
2448 __isl_give isl_set *isl_ast_build_get_isolated(__isl_keep isl_ast_build *build)
2450 if (!build)
2451 return NULL;
2452 if (!build->internal2input)
2453 isl_die(isl_ast_build_get_ctx(build), isl_error_internal,
2454 "build cannot have isolated set", return NULL);
2456 return isl_set_copy(build->isolated);
2459 /* Extract the separation class mapping at the current depth.
2461 * In particular, find and return the subset of build->options that is of
2462 * the following form
2464 * schedule_domain -> separation_class[[depth] -> [class]]
2466 * The caller is expected to eliminate inner dimensions from the domain.
2468 * Note that the domain of build->options has been reformulated
2469 * in terms of the internal build space in embed_options,
2470 * but the position is still that within the current code generation.
2472 __isl_give isl_map *isl_ast_build_get_separation_class(
2473 __isl_keep isl_ast_build *build)
2475 isl_ctx *ctx;
2476 isl_space *space_sep, *space;
2477 isl_map *res;
2478 int local_pos;
2480 if (!build)
2481 return NULL;
2483 local_pos = build->depth - build->outer_pos;
2484 ctx = isl_ast_build_get_ctx(build);
2485 space_sep = isl_space_alloc(ctx, 0, 1, 1);
2486 space_sep = isl_space_wrap(space_sep);
2487 space_sep = isl_space_set_tuple_name(space_sep, isl_dim_set,
2488 "separation_class");
2489 space = isl_ast_build_get_space(build, 1);
2490 space_sep = isl_space_align_params(space_sep, isl_space_copy(space));
2491 space = isl_space_map_from_domain_and_range(space, space_sep);
2493 res = isl_union_map_extract_map(build->options, space);
2494 res = isl_map_fix_si(res, isl_dim_out, 0, local_pos);
2495 res = isl_map_coalesce(res);
2497 return res;
2500 /* Eliminate dimensions inner to the current dimension.
2502 __isl_give isl_set *isl_ast_build_eliminate_inner(
2503 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2505 int dim;
2506 int depth;
2508 if (!build)
2509 return isl_set_free(set);
2511 dim = isl_set_dim(set, isl_dim_set);
2512 depth = build->depth;
2513 set = isl_set_detect_equalities(set);
2514 set = isl_set_eliminate(set, isl_dim_set, depth + 1, dim - (depth + 1));
2516 return set;
2519 /* Eliminate unknown divs and divs that depend on the current dimension.
2521 * Note that during the elimination of unknown divs, we may discover
2522 * an explicit representation of some other unknown divs, which may
2523 * depend on the current dimension. We therefore need to eliminate
2524 * unknown divs first.
2526 __isl_give isl_set *isl_ast_build_eliminate_divs(
2527 __isl_keep isl_ast_build *build, __isl_take isl_set *set)
2529 int depth;
2531 if (!build)
2532 return isl_set_free(set);
2534 set = isl_set_remove_unknown_divs(set);
2535 depth = build->depth;
2536 set = isl_set_remove_divs_involving_dims(set, isl_dim_set, depth, 1);
2538 return set;
2541 /* Eliminate dimensions inner to the current dimension as well as
2542 * unknown divs and divs that depend on the current dimension.
2543 * The result then consists only of constraints that are independent
2544 * of the current dimension and upper and lower bounds on the current
2545 * dimension.
2547 __isl_give isl_set *isl_ast_build_eliminate(
2548 __isl_keep isl_ast_build *build, __isl_take isl_set *domain)
2550 domain = isl_ast_build_eliminate_inner(build, domain);
2551 domain = isl_ast_build_eliminate_divs(build, domain);
2552 return domain;
2555 /* Replace build->single_valued by "sv".
2557 __isl_give isl_ast_build *isl_ast_build_set_single_valued(
2558 __isl_take isl_ast_build *build, int sv)
2560 if (!build)
2561 return build;
2562 if (build->single_valued == sv)
2563 return build;
2564 build = isl_ast_build_cow(build);
2565 if (!build)
2566 return build;
2567 build->single_valued = sv;
2569 return build;